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

Abierto
  • ¿Algo no está bien?
#2,346 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
c
Área
backend-api-design

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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

Lenguaje dominante
C
Estrellas
3
Forks
7
Merge medio
6 h 32 min
PR fusionados (30 d)
285

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de InauguralSystems/EigenScript

Todos los issues de InauguralSystems/EigenScript

Issues similares

Más issues de C

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.