No string search from an offset: a linear scanner must split or slice (found in #2344)

Ouverte
  • Quelque chose ne va pas ?
#2,346 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
25/100
Type d'issue
Fonctionnalité
Clarté
Clairement spécifiée
Activité
Active
Stack technique
c
Domaine
backend-api-design

Piste de recherche

Start with index_of and string handling in the interpreter, then read lib/template.eigs render and the linked #2345 benchmarks. Define and test the start-position behavior, including byte offsets inside multibyte characters and both strict modes; compare timings at two sizes. Update docs/SPEC.md, docs/llms.txt, API output, and a changelog fragment, then verify the old-versus-new render cases and four delimiter benchmarks.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

area:stdlib enhancement

What is missing. index_of of [haystack, needle] always searches from the start of the string. There is no way to ask for the first match at or after a position. A scanner that walks a string therefore has two choices: cut the rest of the string off at each step, which copies it each time and is quadratic over the string, or split the whole string on the delimiter and stitch the pieces back together.

Minimal repro

s is "a{{b{{c"
print of (index_of of [s, "{{"])
print of (index_of of [s, "{{", 2])

The first call prints 1. The second raises index_of: expected a fixed-shape list with at most 2 elements. There is no call that returns 4, the second match, without slicing s.

Where it was found. #2344 and its fix #2345, in lib/template.eigs render. The old render sliced, and was quadratic in the number of placeholders: 30 seconds at 200,001. The new one splits on {{ and }}. It is linear, but a template dense with delimiters that do not pair up now costs interpreted work for each of them, where the old code skipped them in native code. At 100,000 delimiters the four shapes measured take 161 to 299 ms, against 0.3 to 0.6 ms on main (the table under "What it costs" in #2345's description). A search that starts at an offset would let render scan natively and stay linear.

Indexes are bytes today: for "é{{b", index_of gives 2 and len gives 5.

Done when

  • A string search can start at a position: either a third argument to index_of or a new builtin, decided in the pull request with the reason. It returns the index of the first match at or after the start, in the unit index_of returns today, and -1 when there is none.
  • A start that is negative, past the end, not an integer, or inside a multi-byte character has a stated behaviour, with a test for each. A haystack or needle that is not a string raises, in the default mode and with EIGS_STRICT=0.
  • It does not copy the haystack: n searches over a string of n bytes with n matches run in time linear in n, shown by timings at two sizes.
  • docs/SPEC.md, docs/llms.txt and eigenscript --api show it, and a changelog fragment is added.
  • lib/template.eigs render uses it: the exhaustive old-against-new test of #2345 still passes, and the four shapes of #2345's "What it costs" are within noise of main at 100,000 delimiters. If the pull request grows large, split this box into its own issue and link it here.

Found while fixing #2344; out of that change's scope, so it is filed and not worked around.

— Claude DevBox

Langage dominant
C
Étoiles
3
Forks
7
Merge moyen
6 h 32 min
PR mergées (30 j)
285

Préparer son environnement

Ouvrir dans Codespaces

Lance le conteneur de développement du projet dans votre navigateur, avec votre propre compte GitHub.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de InauguralSystems/EigenScript

Toutes les issues de InauguralSystems/EigenScript

Issues similaires

Plus d'issues C

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.