lambdaclass / lambdaclass/lambda_compiler_kit
perf/safety: convert parseStr from recursive to iterative to prevent stack overflow
まだ誰も着手していません。
- 主要言語
- Lean
- スター
- 2
- フォーク
- 1
- PR マージ指標
- 30日以内にマージされた PR はありません
説明
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
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
調査の方向性
Lck/Json/Tokenizer.lean の parseStr の再帰的な CPS 実装から始め、呼び出し側がその CPS インターフェースにどのように依存しているかを確認します。そのインターフェースを維持したまま、文字列の解析を反復的なアキュムレーターとして書き直し、帰納的なループ不変条件を中心に証明を適用し直し、大きな文字列リテラルでスタックオーバーフローが発生するリスクがなくなったことを検証します。
索引モデルが issue の本文から書いたものです。
評価
- 領域
- compilers, performance
- issue の種類
- リファクタリング
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 活発さ
- 停滞
- 明瞭さ
- 明確に書かれている
- 初心者へのやさしさ
- 45/100