lambdaclass / lambdaclass/lambda_compiler_kit
perf/safety: convert parseStr from recursive to iterative to prevent stack overflow
Personne n'a encore pris cette issue.
- Langage dominant
- Lean
- Étoiles
- 2
- Forks
- 1
- Métriques de merge des PR
- Aucune PR mergée en 30 j
Description
Problem
parseStr in Lck/Json/Tokenizer.lean is written as a recursive CPS function. While the continuation wrapping is proven zero-cost at runtime (proofs are erased), the recursion itself is structural on the input — meaning for a string literal of length n, the Lean runtime creates n stack frames.
For pathologically large string values this can overflow the stack.
Expected fix
Rewrite parseStr as an iterative (tail-recursive or explicit loop) accumulator, maintaining the same CPS interface for callers. The proof structure can be adapted to use an inductive invariant on the loop state.
References
- Flagged by AI code review on PR #8
Guide de contribution
Aucun guide de contribution indexé pour ce dépôt
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Piste de recherche
Commencez dans Lck/Json/Tokenizer.lean, au niveau de l’implémentation CPS récursive de parseStr, puis examinez comment les appelants dépendent de son interface CPS. Réécrivez l’analyse des chaînes sous la forme d’un accumulateur itératif tout en préservant cette interface, adaptez la preuve autour d’un invariant de boucle inductif et vérifiez que les littéraux de chaîne volumineux ne risquent plus de provoquer un dépassement de pile.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
Évaluation
- Domaine
- compilers, performance
- Type d'issue
- Refactorisation
- Difficulté
- 4/5
- Temps estimé
- 3-5 jours
- Activité
- À l'abandon
- Clarté
- Clairement spécifiée
- Accessibilité débutants
- 45/100