lambdaclass / lambdaclass/lambda_compiler_kit
perf: fix O(n²) string concatenation in parseStr (Tokenizer.lean)
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 2
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Description
Problem
parseStr in Lck/Json/Tokenizer.lean accumulates the string result with acc ++ s, which is O(n²) for large strings because each concatenation copies the accumulated string.
Suggested Fix
Use String.Builder accumulation or collect into List Char/List String and concatenate once at the close-quote branch to achieve O(n) behavior.
References
Raised in AI code review (Codex #1, medium severity).
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Open Lck/Json/Tokenizer.lean and inspect parseStr, especially its accumulator and close-quote branch. Replace the repeated string concatenation with one of the suggested linear-time accumulation approaches, while preserving parsing behavior and confirming that large strings no longer trigger O(n²) work.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Refactor
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 58/100