AI Changelog Aggregator

common/grammar: fix grammar parsing issues to prevent stack overflow and hangs (#18604)

grammar: add test case for nullable symbol loop

Reproduce stack overflow (or OOM) with ( [x]* )* found while adding GBNF support to ripgrep-edit.

llama-server reproducer:

curl
-X POST
-d '{ "messages": [{ "role": "user", "content": "write yes" }], "grammar": "root ::= ( [x]* )*" }'
-H "Content-Type: application/json"
http://localhost:8811/v1/chat/completions

grammar: prevent stack overflow with nullable symbol loop

Fix a potential stack overflow in llama_grammar_advance_stack that could occur when processing grammars with nullable symbols that lead to infinite derivations of empty strings. The fix introduces cycle detection by tracking visited stacks to prevent infinite recursion.

rg-edit regexp: llama_grammar_advance_stack rg-edit extra-args: -A20 rg-edit directive: """Rewrite: fix the following segfault:

[..] ⚫ Testing segfault. Grammar: root ::= ( [x]* )*

        root ::= ( [x]* )*

Segmentation fault build/bin/test-grammar-integration"""

gptel-context: (("/llama.cpp/src/llama-grammar.cpp") ("/llama.cpp/tests/test-grammar-integration.cpp") ("/llama.cpp/grammars/./list.gbnf") ("/llama.cpp/grammars/./json_arr.gbnf") ("/llama.cpp/grammars/./json.gbnf") ("/llama.cpp/grammars/./japanese.gbnf") ("/llama.cpp/grammars/./english.gbnf") ("/llama.cpp/grammars/./chess.gbnf") ("/llama.cpp/grammars/./c.gbnf") ("/llama.cpp/grammars/./arithmetic.gbnf") ("~/llama.cpp/grammars/./README.md"))

grammar: convert recursive llama_grammar_advance_stack to iterative

This change converts the function to an iterative approach using explicit stacks, which prevents deep recursion and eliminates the risk of stack overflow.

rg-edit regexp: llama_grammar_advance_stack rg-edit extra-args: -A30 rg-edit directive: """Rewrite: fix the following segfault:

[..] ⚫ Testing segfault. Grammar: root ::= ( [x]* )*

        root ::= ( [x]* )*

Segmentation fault build/bin/test-grammar-integration

convert from recursive to interactive"""

v2: Added a std::set to perform tree-based lookups with O(N log N) complexity. Testing with a parallel run of test-grammar-integration shows a double-digit percentage increase in runtime. An unordered_set with O(1) hashing was also evaluated, but the overhead of constructing hash keys from pointers made it significantly slower than the rbtree implementation that only requires an ordering operator. The performance regression in the test suite appears justified by the overall reduction in algorithmic complexity.

Co-developed-by: Piotr Wilkin (ilintar) piotr.wilkin@syndatis.com

grammar: add test case for hang in repetition grammar processing

This commit adds a new test case to the grammar integration tests that specifically targets a hang scenario in the repetition grammar parser found while adding GBNF support to ripgrep-edit.

llama-server reproducer:

curl
-X POST
-d '{ "messages": [{ "role": "user", "content": "write yes" }], "grammar": "root ::= (([^x]*){0,99}){0,99}" }'
-H "Content-Type: application/json"
http://localhost:8811/v1/chat/completions

grammar: add repetition threshold check

The change introduces a maximum repetition threshold to avoid excessive rule expansion during grammar parsing. When parsing repetition patterns like {m,n}, the parser now calculates the potential number of rules that would be generated and throws an error if the product of previous rules and new rules exceeds the threshold.

A test case was added to verify the threshold is properly enforced for deeply nested repetition patterns that would otherwise cause hangs.

macOS/iOS:

Linux:

Windows:

openEuler: