echodict/llama.cpp

1#ifdef NDEBUG2#undef NDEBUG3#endif4 5#include "llama.h"6 7// TODO: shold not include libllama sources8#include "../src/llama-grammar.h"9 10#include <cassert>11 12static const char * type_str(llama_gretype type) {13    switch (type) {14        case LLAMA_GRETYPE_CHAR: return "LLAMA_GRETYPE_CHAR";15        case LLAMA_GRETYPE_CHAR_NOT: return "LLAMA_GRETYPE_CHAR_NOT";16        case LLAMA_GRETYPE_CHAR_ALT: return "LLAMA_GRETYPE_CHAR_ALT";17        case LLAMA_GRETYPE_CHAR_RNG_UPPER: return "LLAMA_GRETYPE_CHAR_RNG_UPPER";18        case LLAMA_GRETYPE_RULE_REF: return "LLAMA_GRETYPE_RULE_REF";19        case LLAMA_GRETYPE_ALT: return "LLAMA_GRETYPE_ALT";20        case LLAMA_GRETYPE_END: return "LLAMA_GRETYPE_END";21        default: return "?";22    }23}24 25static void verify_parsing(const char *grammar_bytes, const std::vector<std::pair<std::string, uint32_t>> expected, const std::vector<llama_grammar_element> &expected_rules) {26    uint32_t index = 0;27    llama_grammar_parser parsed_grammar;28    parsed_grammar.parse(grammar_bytes);29 30    std::map<uint32_t, std::string> symbol_names;31    for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {32        symbol_names[it->second] = it->first;33    }34 35    auto print_all = [&]() {36        fprintf(stderr, "    verify_parsing(R\"\"\"(%s)\"\"\", {\n", grammar_bytes);37        for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {38            fprintf(stderr, "        {\"%s\", %u},\n", it->first.c_str(), it->second);39        }40        fprintf(stderr, "    }, {\n");41        for (size_t i_rule = 0; i_rule < parsed_grammar.rules.size(); i_rule++) {42            fprintf(stderr, "        // %s (index %zu)\n", symbol_names[i_rule].c_str(), i_rule);43            auto & rule = parsed_grammar.rules[i_rule];44            for (uint32_t i = 0; i < rule.size(); i++) {45                std::string rule_str;46                fprintf(stderr, "        {%s, ", type_str(rule[i].type));47                if (rule[i].type == LLAMA_GRETYPE_CHAR || rule[i].type == LLAMA_GRETYPE_CHAR_ALT ||48                    rule[i].type == LLAMA_GRETYPE_CHAR_NOT || rule[i].type == LLAMA_GRETYPE_CHAR_RNG_UPPER) {49                    char c = rule[i].value;50                    if (c == '\n') {51                        fprintf(stderr, "'\\n'");52                    } else if (c == '\t') {53                        fprintf(stderr, "'\\t'");54                    } else if (c == '\r') {55                        fprintf(stderr, "'\\r'");56                    } else if (c == '\0') {57                        fprintf(stderr, "'\\0'");58                    } else {59                        fprintf(stderr, "'%c'", c);60                    }61                } else if (rule[i].type == LLAMA_GRETYPE_RULE_REF) {62                    fprintf(stderr, "/* %s */ %u", symbol_names[rule[i].value].c_str(), rule[i].value);63                } else {64                    fprintf(stderr, "%u", rule[i].value);65                }66                fprintf(stderr, "},\n");67            }68        }69        fprintf(stderr, "    });\n");70    };71 72    if (getenv("TEST_GRAMMAR_PARSER_PRINT_ALL")) {73        print_all();74        fprintf(stderr, "\n");75        return;76    }77 78    fprintf(stderr, "Testing grammar:%s\n", grammar_bytes);79 80    if (parsed_grammar.symbol_ids.size() != expected.size()) {81        fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");82        print_all();83        assert(parsed_grammar.symbol_ids.size() == expected.size());84    }85 86    for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it)87    {88        std::string key = it->first;89        uint32_t value = it->second;90        std::pair<std::string, uint32_t> expected_pair = expected[index];91 92        // pretty print error message before asserting93        if (expected_pair.first != key || expected_pair.second != value)94        {95            fprintf(stderr, "index: %u\n", index);96            fprintf(stderr, "expected_pair: %s, %u\n", expected_pair.first.c_str(), expected_pair.second);97            fprintf(stderr, "actual_pair: %s, %u\n", key.c_str(), value);98            fprintf(stderr, "expected_pair != actual_pair\n");99            fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");100            print_all();101        }102 103        assert(expected_pair.first == key && expected_pair.second == value);104 105        index++;106    }107 108    index = 0;109    for (auto rule : parsed_grammar.rules)110    {111        // compare rule to expected rule112        for (uint32_t i = 0; i < rule.size(); i++)113        {114            llama_grammar_element element = rule[i];115            llama_grammar_element expected_element = expected_rules[index];116 117            // pretty print error message before asserting118            if (expected_element.type != element.type || expected_element.value != element.value)119            {120                fprintf(stderr, "index: %u\n", index);121                fprintf(stderr, "expected_element: %s, %u\n", type_str(expected_element.type), expected_element.value);122                fprintf(stderr, "actual_element: %s, %u\n", type_str(element.type), element.value);123                fprintf(stderr, "expected_element != actual_element\n");124                fprintf(stderr, "all elements:\n");125                fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");126                print_all();127            }128 129            assert(expected_element.type == element.type && expected_element.value == element.value);130            index++;131        }132    }133}134 135static void verify_failure(const char * grammar_bytes) {136    fprintf(stderr, "Testing expected failure:%s\n", grammar_bytes);137    llama_grammar_parser result;138    result.parse(grammar_bytes);139    assert(result.rules.empty() && "should have failed");140}141 142int main()143{144    verify_failure(R"""(145        root ::= "a"{,}"146    )""");147 148    verify_failure(R"""(149        root ::= (((((([^x]*){0,99}){0,99}){0,99}){0,99}){0,99}){0,99}150    )""");151 152    verify_failure(R"""(153        root ::= "a"{,10}"154    )""");155 156    verify_parsing(R"""(157        root  ::= "a"158    )""", {159        {"root", 0},160    }, {161        // root (index 0)162        {LLAMA_GRETYPE_CHAR, 'a'},163        {LLAMA_GRETYPE_END, 0},164    });165 166    verify_parsing(R"""(167        root  ::= "a" | [bdx-z] | [^1-3]168    )""", {169        {"root", 0},170    }, {171        // root (index 0)172        {LLAMA_GRETYPE_CHAR, 'a'},173        {LLAMA_GRETYPE_ALT, 0},174        {LLAMA_GRETYPE_CHAR, 'b'},175        {LLAMA_GRETYPE_CHAR_ALT, 'd'},176        {LLAMA_GRETYPE_CHAR_ALT, 'x'},177        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},178        {LLAMA_GRETYPE_ALT, 0},179        {LLAMA_GRETYPE_CHAR_NOT, '1'},180        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '3'},181        {LLAMA_GRETYPE_END, 0},182    });183 184    verify_parsing(R"""(185        root  ::= a+186        a     ::= "a"187    )""", {188        {"a", 1},189        {"root", 0},190        {"root_2", 2},191    }, {192        // root (index 0)193        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},194        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},195        {LLAMA_GRETYPE_END, 0},196        // a (index 1)197        {LLAMA_GRETYPE_CHAR, 'a'},198        {LLAMA_GRETYPE_END, 0},199        // root_2 (index 2)200        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},201        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},202        {LLAMA_GRETYPE_ALT, 0},203        {LLAMA_GRETYPE_END, 0},204    });205 206    verify_parsing(R"""(207        root  ::= "a"+208    )""", {209        {"root", 0},210        {"root_1", 1},211    }, {212        // root (index 0)213        {LLAMA_GRETYPE_CHAR, 'a'},214        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},215        {LLAMA_GRETYPE_END, 0},216        // root_1 (index 1)217        {LLAMA_GRETYPE_CHAR, 'a'},218        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},219        {LLAMA_GRETYPE_ALT, 0},220        {LLAMA_GRETYPE_END, 0},221    });222 223    verify_parsing(R"""(224        root  ::= a?225        a     ::= "a"226    )""", {227        {"a", 1},228        {"root", 0},229        {"root_2", 2},230    }, {231        // root (index 0)232        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},233        {LLAMA_GRETYPE_END, 0},234        // a (index 1)235        {LLAMA_GRETYPE_CHAR, 'a'},236        {LLAMA_GRETYPE_END, 0},237        // root_2 (index 2)238        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},239        {LLAMA_GRETYPE_ALT, 0},240        {LLAMA_GRETYPE_END, 0},241    });242 243    verify_parsing(R"""(244        root  ::= "a"?245    )""", {246        {"root", 0},247        {"root_1", 1},248    }, {249        // root (index 0)250        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},251        {LLAMA_GRETYPE_END, 0},252        // root_1 (index 1)253        {LLAMA_GRETYPE_CHAR, 'a'},254        {LLAMA_GRETYPE_ALT, 0},255        {LLAMA_GRETYPE_END, 0},256    });257 258    verify_parsing(R"""(259        root  ::= a*260        a     ::= "a"261    )""", {262        {"a", 1},263        {"root", 0},264        {"root_2", 2},265    }, {266        // root (index 0)267        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},268        {LLAMA_GRETYPE_END, 0},269        // a (index 1)270        {LLAMA_GRETYPE_CHAR, 'a'},271        {LLAMA_GRETYPE_END, 0},272        // root_2 (index 2)273        {LLAMA_GRETYPE_RULE_REF, /* a */ 1},274        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},275        {LLAMA_GRETYPE_ALT, 0},276        {LLAMA_GRETYPE_END, 0},277    });278 279    verify_parsing(R"""(280        root  ::= "a"*281    )""", {282        {"root", 0},283        {"root_1", 1},284    }, {285        // root (index 0)286        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},287        {LLAMA_GRETYPE_END, 0},288        // root_1 (index 1)289        {LLAMA_GRETYPE_CHAR, 'a'},290        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},291        {LLAMA_GRETYPE_ALT, 0},292        {LLAMA_GRETYPE_END, 0},293    });294 295    verify_parsing(R"""(296        root  ::= "a"{2}297    )""", {298        {"root", 0},299    }, {300        // root (index 0)301        {LLAMA_GRETYPE_CHAR, 'a'},302        {LLAMA_GRETYPE_CHAR, 'a'},303        {LLAMA_GRETYPE_END, 0},304    });305 306    verify_parsing(R"""(307        root  ::= "a"{2,}308    )""", {309        {"root", 0},310        {"root_1", 1},311    }, {312        // root (index 0)313        {LLAMA_GRETYPE_CHAR, 'a'},314        {LLAMA_GRETYPE_CHAR, 'a'},315        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},316        {LLAMA_GRETYPE_END, 0},317        // root_1 (index 1)318        {LLAMA_GRETYPE_CHAR, 'a'},319        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},320        {LLAMA_GRETYPE_ALT, 0},321        {LLAMA_GRETYPE_END, 0},322    });323 324    verify_parsing(R"""(325        root  ::= "a"{ 4}326    )""", {327        {"root", 0},328    }, {329        // root (index 0)330        {LLAMA_GRETYPE_CHAR, 'a'},331        {LLAMA_GRETYPE_CHAR, 'a'},332        {LLAMA_GRETYPE_CHAR, 'a'},333        {LLAMA_GRETYPE_CHAR, 'a'},334        {LLAMA_GRETYPE_END, 0},335    });336 337    verify_parsing(R"""(338        root  ::= "a"{2,4}339    )""", {340        {"root", 0},341        {"root_1", 1},342        {"root_2", 2},343    }, {344        // root (index 0)345        {LLAMA_GRETYPE_CHAR, 'a'},346        {LLAMA_GRETYPE_CHAR, 'a'},347        {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},348        {LLAMA_GRETYPE_END, 0},349        // root_1 (index 1)350        {LLAMA_GRETYPE_CHAR, 'a'},351        {LLAMA_GRETYPE_ALT, 0},352        {LLAMA_GRETYPE_END, 0},353        // root_2 (index 2)354        {LLAMA_GRETYPE_CHAR, 'a'},355        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},356        {LLAMA_GRETYPE_ALT, 0},357        {LLAMA_GRETYPE_END, 0},358    });359 360    verify_parsing(R"""(361        root  ::= (expr "=" term "\n")+362        expr  ::= term ([-+*/] term)*363        term  ::= [0-9]+364    )""", {365        {"expr", 2},366        {"expr_5", 5},367        {"expr_6", 6},368        {"root", 0},369        {"root_1", 1},370        {"root_4", 4},371        {"term", 3},372        {"term_7", 7},373    }, {374        // root (index 0)375        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},376        {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},377        {LLAMA_GRETYPE_END, 0},378        // root_1 (index 1)379        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},380        {LLAMA_GRETYPE_CHAR, '='},381        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},382        {LLAMA_GRETYPE_CHAR, '\n'},383        {LLAMA_GRETYPE_END, 0},384        // expr (index 2)385        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},386        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},387        {LLAMA_GRETYPE_END, 0},388        // term (index 3)389        {LLAMA_GRETYPE_CHAR, '0'},390        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},391        {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},392        {LLAMA_GRETYPE_END, 0},393        // root_4 (index 4)394        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},395        {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},396        {LLAMA_GRETYPE_ALT, 0},397        {LLAMA_GRETYPE_END, 0},398        // expr_5 (index 5)399        {LLAMA_GRETYPE_CHAR, '-'},400        {LLAMA_GRETYPE_CHAR_ALT, '+'},401        {LLAMA_GRETYPE_CHAR_ALT, '*'},402        {LLAMA_GRETYPE_CHAR_ALT, '/'},403        {LLAMA_GRETYPE_RULE_REF, /* term */ 3},404        {LLAMA_GRETYPE_END, 0},405        // expr_6 (index 6)406        {LLAMA_GRETYPE_RULE_REF, /* expr_5 */ 5},407        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},408        {LLAMA_GRETYPE_ALT, 0},409        {LLAMA_GRETYPE_END, 0},410        // term_7 (index 7)411        {LLAMA_GRETYPE_CHAR, '0'},412        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},413        {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},414        {LLAMA_GRETYPE_ALT, 0},415        {LLAMA_GRETYPE_END, 0},416    });417 418    verify_parsing(R"""(419        root  ::= (expr "=" ws term "\n")+420        expr  ::= term ([-+*/] term)*421        term  ::= ident | num | "(" ws expr ")" ws422        ident ::= [a-z] [a-z0-9_]* ws423        num   ::= [0-9]+ ws424        ws    ::= [ \t\n]*425    )""", {426        {"expr", 2},427        {"expr_6", 6},428        {"expr_7", 7},429        {"ident", 8},430        {"ident_10", 10},431        {"num", 9},432        {"num_11", 11},433        {"root", 0},434        {"root_1", 1},435        {"root_5", 5},436        {"term", 4},437        {"ws", 3},438        {"ws_12", 12},439    }, {440        // root (index 0)441        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},442        {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},443        {LLAMA_GRETYPE_END, 0},444        // root_1 (index 1)445        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},446        {LLAMA_GRETYPE_CHAR, '='},447        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},448        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},449        {LLAMA_GRETYPE_CHAR, '\n'},450        {LLAMA_GRETYPE_END, 0},451        // expr (index 2)452        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},453        {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},454        {LLAMA_GRETYPE_END, 0},455        // ws (index 3)456        {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},457        {LLAMA_GRETYPE_END, 0},458        // term (index 4)459        {LLAMA_GRETYPE_RULE_REF, /* ident */ 8},460        {LLAMA_GRETYPE_ALT, 0},461        {LLAMA_GRETYPE_RULE_REF, /* num */ 9},462        {LLAMA_GRETYPE_ALT, 0},463        {LLAMA_GRETYPE_CHAR, '('},464        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},465        {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},466        {LLAMA_GRETYPE_CHAR, ')'},467        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},468        {LLAMA_GRETYPE_END, 0},469        // root_5 (index 5)470        {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},471        {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},472        {LLAMA_GRETYPE_ALT, 0},473        {LLAMA_GRETYPE_END, 0},474        // expr_6 (index 6)475        {LLAMA_GRETYPE_CHAR, '-'},476        {LLAMA_GRETYPE_CHAR_ALT, '+'},477        {LLAMA_GRETYPE_CHAR_ALT, '*'},478        {LLAMA_GRETYPE_CHAR_ALT, '/'},479        {LLAMA_GRETYPE_RULE_REF, /* term */ 4},480        {LLAMA_GRETYPE_END, 0},481        // expr_7 (index 7)482        {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},483        {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},484        {LLAMA_GRETYPE_ALT, 0},485        {LLAMA_GRETYPE_END, 0},486        // ident (index 8)487        {LLAMA_GRETYPE_CHAR, 'a'},488        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},489        {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},490        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},491        {LLAMA_GRETYPE_END, 0},492        // num (index 9)493        {LLAMA_GRETYPE_CHAR, '0'},494        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},495        {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},496        {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},497        {LLAMA_GRETYPE_END, 0},498        // ident_10 (index 10)499        {LLAMA_GRETYPE_CHAR, 'a'},500        {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},501        {LLAMA_GRETYPE_CHAR_ALT, '0'},502        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},503        {LLAMA_GRETYPE_CHAR_ALT, '_'},504        {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},505        {LLAMA_GRETYPE_ALT, 0},506        {LLAMA_GRETYPE_END, 0},507        // num_11 (index 11)508        {LLAMA_GRETYPE_CHAR, '0'},509        {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},510        {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},511        {LLAMA_GRETYPE_ALT, 0},512        {LLAMA_GRETYPE_END, 0},513        // ws_12 (index 12)514        {LLAMA_GRETYPE_CHAR, ' '},515        {LLAMA_GRETYPE_CHAR_ALT, '\t'},516        {LLAMA_GRETYPE_CHAR_ALT, '\n'},517        {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},518        {LLAMA_GRETYPE_ALT, 0},519        {LLAMA_GRETYPE_END, 0},520    });521 522    // <[1000]> = "<think>"523    // <[1001]> = "</think>"524    verify_parsing(R"""(525        root  ::= <[1000]> !<[1001]> <[1001]>526    )""", {527        {"root", 0}528    }, {529        // root (index 0)530        {LLAMA_GRETYPE_TOKEN, 1000},531        {LLAMA_GRETYPE_TOKEN_NOT, 1001},532        {LLAMA_GRETYPE_TOKEN, 1001},533        {LLAMA_GRETYPE_END, 0},534    });535 536    return 0;537}538