summaryrefslogtreecommitdiff
path: root/tests/test-grammar-integration.cpp
diff options
context:
space:
mode:
authorHaggai Nuchi <h.nuchi@gmail.com>2024-05-13 22:25:56 -0700
committerGitHub <noreply@github.com>2024-05-14 15:25:56 +1000
commite0f556186b6e1f2b7032a1479edf5e89e2b1bd86 (patch)
treef418b53a5ba7b285b0b3b3c4e1509848ad08b67a /tests/test-grammar-integration.cpp
parent27f65d6267cf22a44c5ccefa7765d53a05bd1259 (diff)
Add left recursion check: quit early instead of going into an infinite loop (#7083)
* Add left recursion check: quit early instead of going into an infinite loop * Remove custom enum, rename left recursion check and move to "grammar internal" section, add handling for edge case where a leftmost nonterminal may be empty * Remove unnecessary declaration
Diffstat (limited to 'tests/test-grammar-integration.cpp')
-rw-r--r--tests/test-grammar-integration.cpp46
1 files changed, 46 insertions, 0 deletions
diff --git a/tests/test-grammar-integration.cpp b/tests/test-grammar-integration.cpp
index 1a4004e2..01c5bb27 100644
--- a/tests/test-grammar-integration.cpp
+++ b/tests/test-grammar-integration.cpp
@@ -28,6 +28,19 @@ static llama_grammar* build_grammar(const std::string & grammar_str) {
return grammar;
}
+static bool test_build_grammar_fails(const std::string & grammar_str) {
+ fprintf(stderr, "⚫ Testing failure for grammar: %s\n", grammar_str.c_str());
+ bool grammar_fails = false;
+ try {
+ build_grammar(grammar_str);
+ fprintf(stderr, " ❌ Expected build failure, but succeeded\n");
+ } catch (const std::exception & err) {
+ grammar_fails = true;
+ fprintf(stdout, " ✅︎\n");
+ }
+ return grammar_fails;
+}
+
static bool match_string(const std::string & input, llama_grammar* grammar) {
auto decoded = decode_utf8(input, {});
@@ -320,6 +333,38 @@ number ::= [0-9]+)""";
fprintf(stderr, " ✅︎ Passed\n");
}
+static void test_failure_left_recursion() {
+ fprintf(stderr, "⚫ Testing left recursion detection:\n");
+
+ // Test simple left recursion detection
+ const std::string simple_str = R"""(root ::= "a" | root "a")""";
+ assert(test_build_grammar_fails(simple_str));
+
+ // Test more complicated left recursion detection
+ const std::string medium_str = R"""(
+root ::= asdf
+asdf ::= "a" | asdf "a"
+)""";
+ assert(test_build_grammar_fails(medium_str));
+
+ // Test even more complicated left recursion detection
+ const std::string hard_str = R"""(
+root ::= asdf
+asdf ::= "a" | foo "b"
+foo ::= "c" | asdf "d" | "e")""";
+ assert(test_build_grammar_fails(hard_str));
+
+ // Test yet even more complicated left recursion detection
+ const std::string hardest_str = R"""(
+root ::= asdf
+asdf ::= "a" | foo "b"
+foo ::= "c" | empty asdf "d" | "e"
+empty ::= "blah" | )""";
+ assert(test_build_grammar_fails(hardest_str));
+
+ fprintf(stderr, " ✅︎ Passed\n");
+}
+
int main() {
fprintf(stdout, "Running grammar integration tests...\n");
test_simple_grammar();
@@ -327,6 +372,7 @@ int main() {
test_quantifiers();
test_failure_missing_root();
test_failure_missing_reference();
+ test_failure_left_recursion();
fprintf(stdout, "All tests passed.\n");
return 0;
}