LLVMFuzzerTestOneInput:
   17|     45|extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
   18|     45|  std::string payload(reinterpret_cast<const char *>(data), size);
   19|       |
   20|     45|  llama_grammar_parser parsed_grammar;
   21|     45|  parsed_grammar.parse(payload.c_str());
   22|       |
   23|     45|  return 0;
   24|     45|}

_ZN20llama_grammar_parser13get_symbol_idEPKcm:
  415|     93|uint32_t llama_grammar_parser::get_symbol_id(const char * src, size_t len) {
  416|     93|    uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());
  417|     93|    auto result = symbol_ids.emplace(std::string(src, len), next_id);
  418|     93|    return result.first->second;
  419|     93|}
_ZN20llama_grammar_parser18generate_symbol_idERKNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEE:
  421|     78|uint32_t llama_grammar_parser::generate_symbol_id(const std::string & base_name) {
  422|     78|    uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());
  423|     78|    symbol_ids[base_name + '_' + std::to_string(next_id)] = next_id;
  424|     78|    return next_id;
  425|     78|}
_ZN20llama_grammar_parser8add_ruleEjRKNSt3__16vectorI21llama_grammar_elementNS0_9allocatorIS2_EEEE:
  427|     59|void llama_grammar_parser::add_rule(uint32_t rule_id, const llama_grammar_rule & rule) {
  428|     59|    if (rules.size() <= rule_id) {
  ------------------
  |  Branch (428:9): [True: 56, False: 3]
  ------------------
  429|     56|        rules.resize(rule_id + 1);
  430|     56|    }
  431|     59|    rules[rule_id] = rule;
  432|     59|}
_ZN20llama_grammar_parser16parse_alternatesEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEEjb:
  438|     82|        bool                is_nested) {
  439|     82|    llama_grammar_rule rule;
  440|     82|    const char * pos = parse_sequence(src, rule_name, rule, is_nested);
  441|     82|    while (*pos == '|') {
  ------------------
  |  Branch (441:12): [True: 0, False: 82]
  ------------------
  442|      0|        rule.push_back({LLAMA_GRETYPE_ALT, 0});
  443|      0|        pos = parse_space(pos + 1, true);
  444|      0|        pos = parse_sequence(pos, rule_name, rule, is_nested);
  445|      0|    }
  446|     82|    rule.push_back({LLAMA_GRETYPE_END, 0});
  447|     82|    add_rule(rule_id, rule);
  448|     82|    return pos;
  449|     82|}
_ZN20llama_grammar_parser14parse_sequenceEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEERNS2_6vectorI21llama_grammar_elementNS6_ISC_EEEEb:
  455|     82|        bool               is_nested) {
  456|     82|    size_t last_sym_start = rule.size();
  457|     82|    const char * pos = src;
  458|     82|    uint64_t n_prev_rules = 1;
  459|       |
  460|       |    // use UINT64_MAX as the empty value because we aligned to the proper uint64_t type so -1 can't be used
  461|       |    // (though it's technically the same as -1 now)
  462|     82|    auto handle_repetitions = [&](uint64_t min_times, uint64_t max_times) {
  463|     82|        bool no_max = max_times == UINT64_MAX;
  464|     82|        if (last_sym_start == rule.size()) {
  465|     82|            throw std::runtime_error(std::string("expecting preceding item to */+/?/{ at ") + pos);
  466|     82|        }
  467|       |
  468|       |        // apply transformation to previous symbol (last_sym_start to end) according to
  469|       |        // the following rewrite rules:
  470|       |        // S{m,n} --> S S S (m times) S'(n-m)
  471|       |        //            S'(x)   ::= S S'(x-1) |
  472|       |        //            (... n-m definitions of these S' rules ...)
  473|       |        //            S'(1)   ::= S |
  474|       |        // S{m,} -->  S S S (m times) S'
  475|       |        //            S'     ::= S S' |
  476|       |        // S*     --> S{0,}
  477|       |        //        --> S'     ::= S S' |
  478|       |        // S+     --> S{1,}
  479|       |        //        --> S S'
  480|       |        //            S'     ::= S S' |
  481|       |        // S?     --> S{0,1}
  482|       |        //        --> S'
  483|       |        //            S'     ::= S |
  484|       |
  485|     82|        llama_grammar_rule prev_rule(rule.begin() + last_sym_start, rule.end());
  486|       |        // Calculate the total number of rules that will be generated by this repetition
  487|     82|        uint64_t total_rules = 1; // Start with 1 for the original rule
  488|     82|        if (!no_max && max_times > 0) {
  489|     82|            total_rules = max_times;
  490|     82|        } else if (min_times > 0) {
  491|     82|            total_rules = min_times;
  492|     82|        }
  493|       |
  494|     82|        if (n_prev_rules * total_rules >= MAX_REPETITION_THRESHOLD) {
  495|     82|            throw std::runtime_error("number of rules that are going to be repeated multiplied by the new repetition exceeds sane defaults, please reduce the number of repetitions or rule complexity");
  496|     82|        }
  497|       |
  498|     82|        if (min_times == 0) {
  499|     82|            rule.resize(last_sym_start);
  500|     82|        } else {
  501|       |            // Repeat the previous elements (min_times - 1) times
  502|     82|            for (uint64_t i = 1; i < min_times; i++) {
  503|     82|                rule.insert(rule.end(), prev_rule.begin(), prev_rule.end());
  504|     82|            }
  505|     82|        }
  506|       |
  507|     82|        uint32_t last_rec_rule_id = 0;
  508|     82|        auto n_opt = no_max ? 1 : max_times - min_times;
  509|       |
  510|     82|        llama_grammar_rule rec_rule(prev_rule);
  511|     82|        for (uint64_t i = 0; i < n_opt; i++) {
  512|     82|            rec_rule.resize(prev_rule.size());
  513|     82|            uint32_t rec_rule_id = generate_symbol_id( rule_name);
  514|     82|            if (i > 0 || no_max) {
  515|     82|                rec_rule.push_back({LLAMA_GRETYPE_RULE_REF, no_max ? rec_rule_id : last_rec_rule_id});
  516|     82|            }
  517|     82|            rec_rule.push_back({LLAMA_GRETYPE_ALT, 0});
  518|     82|            rec_rule.push_back({LLAMA_GRETYPE_END, 0});
  519|     82|            add_rule( rec_rule_id, rec_rule);
  520|     82|            last_rec_rule_id = rec_rule_id;
  521|     82|        }
  522|     82|        if (n_opt > 0) {
  523|     82|            rule.push_back({LLAMA_GRETYPE_RULE_REF, last_rec_rule_id});
  524|     82|        }
  525|     82|        n_prev_rules *= total_rules;
  526|     82|        GGML_ASSERT(n_prev_rules >= 1);
  527|     82|    };
  528|       |
  529|    217|    while (*pos) {
  ------------------
  |  Branch (529:12): [True: 175, False: 42]
  ------------------
  530|    175|        if (*pos == '"') { // literal string
  ------------------
  |  Branch (530:13): [True: 1, False: 174]
  ------------------
  531|      1|            pos++;
  532|      1|            last_sym_start = rule.size();
  533|      1|            n_prev_rules = 1;
  534|   222k|            while (*pos != '"') {
  ------------------
  |  Branch (534:20): [True: 222k, False: 0]
  ------------------
  535|   222k|                if (!*pos) {
  ------------------
  |  Branch (535:21): [True: 1, False: 222k]
  ------------------
  536|      1|                    throw std::runtime_error("unexpected end of input");
  537|      1|                }
  538|   222k|                auto char_pair = parse_char(pos);
  539|   222k|                     pos       = char_pair.second;
  540|   222k|                rule.push_back({LLAMA_GRETYPE_CHAR, char_pair.first});
  541|   222k|            }
  542|      0|            pos = parse_space(pos + 1, is_nested);
  543|    174|        } else if (*pos == '[') { // char range(s)
  ------------------
  |  Branch (543:20): [True: 0, False: 174]
  ------------------
  544|      0|            pos++;
  545|      0|            enum llama_gretype start_type = LLAMA_GRETYPE_CHAR;
  546|      0|            if (*pos == '^') {
  ------------------
  |  Branch (546:17): [True: 0, False: 0]
  ------------------
  547|      0|                pos++;
  548|      0|                start_type = LLAMA_GRETYPE_CHAR_NOT;
  549|      0|            }
  550|      0|            last_sym_start = rule.size();
  551|      0|            n_prev_rules = 1;
  552|      0|            while (*pos != ']') {
  ------------------
  |  Branch (552:20): [True: 0, False: 0]
  ------------------
  553|      0|                if (!*pos) {
  ------------------
  |  Branch (553:21): [True: 0, False: 0]
  ------------------
  554|      0|                    throw std::runtime_error("unexpected end of input");
  555|      0|                }
  556|      0|                auto char_pair = parse_char(pos);
  557|      0|                     pos       = char_pair.second;
  558|      0|                enum llama_gretype type = last_sym_start < rule.size()
  ------------------
  |  Branch (558:43): [True: 0, False: 0]
  ------------------
  559|      0|                    ? LLAMA_GRETYPE_CHAR_ALT
  560|      0|                    : start_type;
  561|       |
  562|      0|                rule.push_back({type, char_pair.first});
  563|      0|                if (pos[0] == '-' && pos[1] != ']') {
  ------------------
  |  Branch (563:21): [True: 0, False: 0]
  |  Branch (563:38): [True: 0, False: 0]
  ------------------
  564|      0|                    if (!pos[1]) {
  ------------------
  |  Branch (564:25): [True: 0, False: 0]
  ------------------
  565|      0|                        throw std::runtime_error("unexpected end of input");
  566|      0|                    }
  567|      0|                    auto endchar_pair = parse_char(pos + 1);
  568|      0|                         pos          = endchar_pair.second;
  569|      0|                    rule.push_back({LLAMA_GRETYPE_CHAR_RNG_UPPER, endchar_pair.first});
  570|      0|                }
  571|      0|            }
  572|      0|            pos = parse_space(pos + 1, is_nested);
  573|    174|        } else if (*pos == '<' || *pos == '!') { // token
  ------------------
  |  Branch (573:20): [True: 5, False: 169]
  |  Branch (573:35): [True: 0, False: 169]
  ------------------
  574|      5|            auto type = LLAMA_GRETYPE_TOKEN;
  575|      5|            if (*pos == '!') { // token inverse
  ------------------
  |  Branch (575:17): [True: 0, False: 5]
  ------------------
  576|      0|                type = LLAMA_GRETYPE_TOKEN_NOT;
  577|      0|                pos++;
  578|      0|            }
  579|      5|            auto token_pair = parse_token(vocab, pos);
  580|      5|            const char * token_end  = token_pair.second;
  581|      5|            last_sym_start = rule.size();
  582|      5|            n_prev_rules = 1;
  583|      5|            rule.push_back({type, token_pair.first});
  584|      5|            pos = parse_space(token_end, is_nested);
  585|    169|        } else if (is_word_char(*pos)) { // rule reference
  ------------------
  |  Branch (585:20): [True: 50, False: 119]
  ------------------
  586|     50|            const char * name_end    = parse_name(pos);
  587|     50|            uint32_t ref_rule_id = get_symbol_id(pos, name_end - pos);
  588|     50|            pos = parse_space(name_end, is_nested);
  589|     50|            last_sym_start = rule.size();
  590|     50|            n_prev_rules = 1;
  591|     50|            rule.push_back({LLAMA_GRETYPE_RULE_REF, ref_rule_id});
  592|    119|        } else if (*pos == '(') { // grouping
  ------------------
  |  Branch (592:20): [True: 51, False: 68]
  ------------------
  593|       |            // parse nested alternates into synthesized rule
  594|     51|            pos = parse_space(pos + 1, true);
  595|     51|            uint32_t n_rules_before = symbol_ids.size();
  596|     51|            uint32_t sub_rule_id = generate_symbol_id(rule_name);
  597|     51|            pos = parse_alternates(pos, rule_name, sub_rule_id, true);
  598|     51|            n_prev_rules = std::max(1u, (uint32_t)symbol_ids.size() - n_rules_before);
  599|     51|            last_sym_start = rule.size();
  600|       |            // output reference to synthesized rule
  601|     51|            rule.push_back({LLAMA_GRETYPE_RULE_REF, sub_rule_id});
  602|     51|            if (*pos != ')') {
  ------------------
  |  Branch (602:17): [True: 3, False: 48]
  ------------------
  603|      3|                throw std::runtime_error(std::string("expecting ')' at ") + pos);
  604|      3|            }
  605|     48|            pos = parse_space(pos + 1, is_nested);
  606|     68|        } else if (*pos == '.') { // any char
  ------------------
  |  Branch (606:20): [True: 0, False: 68]
  ------------------
  607|      0|            last_sym_start = rule.size();
  608|      0|            n_prev_rules = 1;
  609|      0|            rule.push_back({LLAMA_GRETYPE_CHAR_ANY, 0});
  610|      0|            pos = parse_space(pos + 1, is_nested);
  611|     68|        } else if (*pos == '*') {
  ------------------
  |  Branch (611:20): [True: 0, False: 68]
  ------------------
  612|      0|            pos = parse_space(pos + 1, is_nested);
  613|      0|            handle_repetitions(0, -1);
  614|     68|        } else if (*pos == '+') {
  ------------------
  |  Branch (614:20): [True: 0, False: 68]
  ------------------
  615|      0|            pos = parse_space(pos + 1, is_nested);
  616|      0|            handle_repetitions(1, -1);
  617|     68|        } else if (*pos == '?') {
  ------------------
  |  Branch (617:20): [True: 27, False: 41]
  ------------------
  618|     27|            pos = parse_space(pos + 1, is_nested);
  619|     27|            handle_repetitions(0, 1);
  620|     41|        } else if (*pos == '{') {
  ------------------
  |  Branch (620:20): [True: 16, False: 25]
  ------------------
  621|     16|            pos = parse_space(pos + 1, is_nested);
  622|       |
  623|     16|            if (!is_digit_char(*pos)) {
  ------------------
  |  Branch (623:17): [True: 0, False: 16]
  ------------------
  624|      0|                throw std::runtime_error(std::string("expecting an int at ") + pos);
  625|      0|            }
  626|     16|            const char * int_end = parse_int(pos);
  627|     16|            uint64_t min_times = std::stoull(std::string(pos, int_end - pos));
  628|     16|            pos = parse_space(int_end, is_nested);
  629|       |
  630|     16|            uint64_t max_times = UINT64_MAX; // default: no max limit
  631|       |
  632|     16|            if (*pos == '}') {
  ------------------
  |  Branch (632:17): [True: 0, False: 16]
  ------------------
  633|      0|                max_times = min_times;
  634|      0|                pos = parse_space(pos + 1, is_nested);
  635|     16|            } else if (*pos == ',') {
  ------------------
  |  Branch (635:24): [True: 5, False: 11]
  ------------------
  636|      5|                pos = parse_space(pos + 1, is_nested);
  637|       |
  638|      5|                if (is_digit_char(*pos)) {
  ------------------
  |  Branch (638:21): [True: 5, False: 0]
  ------------------
  639|      5|                    const char * int_end = parse_int(pos);
  640|      5|                    max_times = std::stoull(std::string(pos, int_end - pos));
  641|      5|                    pos = parse_space(int_end, is_nested);
  642|      5|                }
  643|       |
  644|      5|                if (*pos != '}') {
  ------------------
  |  Branch (644:21): [True: 0, False: 5]
  ------------------
  645|      0|                    throw std::runtime_error(std::string("expecting '}' at ") + pos);
  646|      0|                }
  647|      5|                pos = parse_space(pos + 1, is_nested);
  648|     11|            } else {
  649|     11|                throw std::runtime_error(std::string("expecting ',' at ") + pos);
  650|     11|            }
  651|      5|            bool has_max = max_times != UINT64_MAX;
  652|      5|            if (min_times > MAX_REPETITION_THRESHOLD || (has_max && max_times > MAX_REPETITION_THRESHOLD)) {
  ------------------
  |  |   13|     10|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
                          if (min_times > MAX_REPETITION_THRESHOLD || (has_max && max_times > MAX_REPETITION_THRESHOLD)) {
  ------------------
  |  |   13|      0|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
  |  Branch (652:17): [True: 5, False: 0]
  |  Branch (652:58): [True: 0, False: 0]
  |  Branch (652:69): [True: 0, False: 0]
  ------------------
  653|      0|                throw std::runtime_error(std::string("number of repetitions exceeds sane defaults, please reduce the number of repetitions"));
  654|      0|            }
  655|      5|            handle_repetitions(min_times, max_times);
  656|     25|        } else {
  657|     25|            break;
  658|     25|        }
  659|    175|    }
  660|     67|    return pos;
  661|     82|}
_ZN20llama_grammar_parser10parse_ruleEPKc:
  663|     43|const char * llama_grammar_parser::parse_rule(const char * src) {
  664|     43|    const char * name_end = parse_name(src);
  665|     43|    const char * pos      = parse_space(name_end, false);
  666|     43|    size_t       name_len = name_end - src;
  667|     43|    uint32_t     rule_id  = get_symbol_id(src, name_len);
  668|     43|    const std::string name(src, name_len);
  669|       |
  670|     43|    if (!(pos[0] == ':' && pos[1] == ':' && pos[2] == '=')) {
  ------------------
  |  Branch (670:11): [True: 33, False: 10]
  |  Branch (670:28): [True: 32, False: 1]
  |  Branch (670:45): [True: 31, False: 1]
  ------------------
  671|     12|        throw std::runtime_error(std::string("expecting ::= at ") + pos);
  672|     12|    }
  673|     31|    pos = parse_space(pos + 3, true);
  674|       |
  675|     31|    pos = parse_alternates(pos, name, rule_id, false);
  676|       |
  677|     31|    if (*pos == '\r') {
  ------------------
  |  Branch (677:9): [True: 0, False: 31]
  ------------------
  678|      0|        pos += pos[1] == '\n' ? 2 : 1;
  ------------------
  |  Branch (678:16): [True: 0, False: 0]
  ------------------
  679|     31|    } else if (*pos == '\n') {
  ------------------
  |  Branch (679:16): [True: 0, False: 31]
  ------------------
  680|      0|        pos++;
  681|     31|    } else if (*pos) {
  ------------------
  |  Branch (681:16): [True: 2, False: 29]
  ------------------
  682|      2|        throw std::runtime_error(std::string("expecting newline or end at ") + pos);
  683|      2|    }
  684|     29|    return parse_space(pos, true);
  685|     31|}
_ZN20llama_grammar_parser5parseEPKc:
  687|     45|bool llama_grammar_parser::parse(const char * src) {
  688|     45|    try {
  689|     45|        const char * pos = parse_space(src, true);
  690|     88|        while (*pos) {
  ------------------
  |  Branch (690:16): [True: 43, False: 45]
  ------------------
  691|     43|            pos = parse_rule(pos);
  692|     43|        }
  693|       |        // Validate the state to ensure that all rules are defined
  694|     45|        for (const auto & rule : rules) {
  ------------------
  |  Branch (694:32): [True: 4, False: 41]
  ------------------
  695|      4|            if (rule.empty()) {
  ------------------
  |  Branch (695:17): [True: 0, False: 4]
  ------------------
  696|      0|                throw std::runtime_error("Undefined rule");
  697|      0|            }
  698|      5|            for (const auto & elem : rule) {
  ------------------
  |  Branch (698:36): [True: 5, False: 0]
  ------------------
  699|      5|                if (elem.type == LLAMA_GRETYPE_RULE_REF) {
  ------------------
  |  Branch (699:21): [True: 5, False: 0]
  ------------------
  700|       |                    // Ensure that the rule at that location exists
  701|      5|                    if (elem.value >= rules.size() || rules[elem.value].empty()) {
  ------------------
  |  Branch (701:25): [True: 4, False: 1]
  |  Branch (701:55): [True: 0, False: 1]
  ------------------
  702|       |                        // Get the name of the rule that is missing
  703|     10|                        for (const auto & kv : symbol_ids) {
  ------------------
  |  Branch (703:46): [True: 10, False: 0]
  ------------------
  704|     10|                            if (kv.second == elem.value) {
  ------------------
  |  Branch (704:33): [True: 4, False: 6]
  ------------------
  705|      4|                                throw std::runtime_error("Undefined rule identifier '" + kv.first + "'");
  706|      4|                            }
  707|     10|                        }
  708|      4|                    }
  709|      5|                }
  710|      5|            }
  711|      4|        }
  712|     45|    } catch (const std::exception & err) {
  713|     43|        fprintf(stderr, "%s: error parsing grammar: %s\n\n%s\n", __func__, err.what(), src);
  714|     43|        rules.clear();
  715|     43|        return false;
  716|     43|    }
  717|       |
  718|      2|    return true;
  719|     45|}
llama-grammar.cpp:_ZL11parse_spacePKcb:
  125|    311|static const char * parse_space(const char * src, bool newline_ok) {
  126|    311|    const char * pos = src;
  127|    395|    while (*pos == ' ' || *pos == '\t' || *pos == '#' ||
  ------------------
  |  Branch (127:12): [True: 10, False: 385]
  |  Branch (127:27): [True: 25, False: 360]
  |  Branch (127:43): [True: 5, False: 355]
  ------------------
  128|    355|            (newline_ok && (*pos == '\r' || *pos == '\n'))) {
  ------------------
  |  Branch (128:14): [True: 266, False: 89]
  |  Branch (128:29): [True: 41, False: 225]
  |  Branch (128:45): [True: 3, False: 222]
  ------------------
  129|     84|        if (*pos == '#') {
  ------------------
  |  Branch (129:13): [True: 5, False: 79]
  ------------------
  130|     10|            while (*pos && *pos != '\r' && *pos != '\n') {
  ------------------
  |  Branch (130:20): [True: 10, False: 0]
  |  Branch (130:28): [True: 5, False: 5]
  |  Branch (130:44): [True: 5, False: 0]
  ------------------
  131|      5|                pos++;
  132|      5|            }
  133|     79|        } else {
  134|     79|            pos++;
  135|     79|        }
  136|     84|    }
  137|    311|    return pos;
  138|    311|}
llama-grammar.cpp:_ZL10parse_charPKc:
  162|   222k|static std::pair<uint32_t, const char *> parse_char(const char * src) {
  163|   222k|    if (*src == '\\') {
  ------------------
  |  Branch (163:9): [True: 0, False: 222k]
  ------------------
  164|      0|        switch (src[1]) {
  165|      0|            case 'x': return parse_hex(src + 2, 2);
  ------------------
  |  Branch (165:13): [True: 0, False: 0]
  ------------------
  166|      0|            case 'u': return parse_hex(src + 2, 4);
  ------------------
  |  Branch (166:13): [True: 0, False: 0]
  ------------------
  167|      0|            case 'U': return parse_hex(src + 2, 8);
  ------------------
  |  Branch (167:13): [True: 0, False: 0]
  ------------------
  168|      0|            case 't': return std::make_pair('\t', src + 2);
  ------------------
  |  Branch (168:13): [True: 0, False: 0]
  ------------------
  169|      0|            case 'r': return std::make_pair('\r', src + 2);
  ------------------
  |  Branch (169:13): [True: 0, False: 0]
  ------------------
  170|      0|            case 'n': return std::make_pair('\n', src + 2);
  ------------------
  |  Branch (170:13): [True: 0, False: 0]
  ------------------
  171|      0|            case '\\':
  ------------------
  |  Branch (171:13): [True: 0, False: 0]
  ------------------
  172|      0|            case '"':
  ------------------
  |  Branch (172:13): [True: 0, False: 0]
  ------------------
  173|      0|            case '[':
  ------------------
  |  Branch (173:13): [True: 0, False: 0]
  ------------------
  174|      0|            case ']':
  ------------------
  |  Branch (174:13): [True: 0, False: 0]
  ------------------
  175|      0|                      return std::make_pair(src[1], src + 2);
  176|      0|            default:
  ------------------
  |  Branch (176:13): [True: 0, False: 0]
  ------------------
  177|      0|                      throw std::runtime_error(std::string("unknown escape at ") + src);
  178|      0|        }
  179|   222k|    } else if (*src) {
  ------------------
  |  Branch (179:16): [True: 222k, False: 0]
  ------------------
  180|   222k|        return decode_utf8(src);
  181|   222k|    }
  182|      0|    throw std::runtime_error("unexpected end of input");
  183|   222k|}
llama-grammar.cpp:_ZL11decode_utf8PKc:
   19|   222k|static std::pair<uint32_t, const char *> decode_utf8(const char * src) {
   20|   222k|    static const int lookup[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4 };
   21|   222k|    uint8_t  first_byte = static_cast<uint8_t>(*src);
   22|   222k|    uint8_t  highbits   = first_byte >> 4;
   23|   222k|    int      len        = lookup[highbits];
   24|   222k|    uint8_t  mask       = (1 << (8 - len)) - 1;
   25|   222k|    uint32_t value      = first_byte & mask;
   26|   222k|    const char * end    = src + len; // may overrun!
   27|   222k|    const char * pos    = src + 1;
   28|   222k|    for ( ; pos < end && *pos; pos++) {
  ------------------
  |  Branch (28:13): [True: 90, False: 222k]
  |  Branch (28:26): [True: 90, False: 0]
  ------------------
   29|     90|        value = (value << 6) + (static_cast<uint8_t>(*pos) & 0x3F);
   30|     90|    }
   31|   222k|    return std::make_pair(value, pos);
   32|   222k|}
llama-grammar.cpp:_ZL11parse_tokenPK11llama_vocabPKc:
  185|      5|static std::pair<uint32_t, const char *> parse_token(const llama_vocab * vocab, const char * src) {
  186|      5|    const char * pos = src;
  187|      5|    if (*pos != '<') {
  ------------------
  |  Branch (187:9): [True: 0, False: 5]
  ------------------
  188|      0|        throw std::runtime_error(std::string("expecting '<' at ") + pos);
  189|      0|    }
  190|      5|    pos++;
  191|       |
  192|       |    // Parse <[id]>
  193|      5|    if (*pos == '[') {
  ------------------
  |  Branch (193:9): [True: 5, False: 0]
  ------------------
  194|      5|        pos++;
  195|      5|        const char * int_end = parse_int(pos);
  196|      5|        uint32_t token_id = std::stoul(std::string(pos, int_end - pos));
  197|      5|        pos = int_end;
  198|      5|        if (*pos != ']') {
  ------------------
  |  Branch (198:13): [True: 0, False: 5]
  ------------------
  199|      0|            throw std::runtime_error(std::string("expecting ']' at ") + pos);
  200|      0|        }
  201|      5|        pos++;
  202|      5|        if (*pos != '>') {
  ------------------
  |  Branch (202:13): [True: 0, False: 5]
  ------------------
  203|      0|            throw std::runtime_error(std::string("expecting '>' at ") + pos);
  204|      0|        }
  205|      5|        pos++;
  206|      5|        return std::make_pair(token_id, pos);
  207|      5|    }
  208|       |
  209|      0|    if (vocab == nullptr) {
  ------------------
  |  Branch (209:9): [True: 0, False: 0]
  ------------------
  210|      0|        throw std::runtime_error(std::string("no vocab to parse token at ") + src);
  211|      0|    }
  212|       |
  213|       |    // Parse <token> and tokenize to obtain the token id
  214|      0|    while (*pos != 0 && *pos != '>') {
  ------------------
  |  Branch (214:12): [True: 0, False: 0]
  |  Branch (214:25): [True: 0, False: 0]
  ------------------
  215|      0|        pos++;
  216|      0|    }
  217|      0|    if (*pos != '>') {
  ------------------
  |  Branch (217:9): [True: 0, False: 0]
  ------------------
  218|      0|        throw std::runtime_error(std::string("expecting '>' at ") + pos);
  219|      0|    }
  220|      0|    pos++;
  221|       |
  222|      0|    llama_token tokens[2];
  223|      0|    int32_t n_tokens = vocab->tokenize(src, static_cast<int32_t>(pos - src), tokens, 2, false, true);
  224|      0|    if (n_tokens != 1) {
  ------------------
  |  Branch (224:9): [True: 0, False: 0]
  ------------------
  225|       |        // must tokenize to exactly 1 token
  226|      0|        throw std::runtime_error("invalid token '" + std::string(src, pos - src) + "'");
  227|      0|    }
  228|      0|    return std::make_pair(tokens[0], pos);
  229|      0|}
llama-grammar.cpp:_ZL12is_word_charc:
   98|  15.7M|static bool is_word_char(char c) {
   99|  15.7M|    return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '-' || is_digit_char(c);
  ------------------
  |  Branch (99:13): [True: 7.22M, False: 8.55M]
  |  Branch (99:25): [True: 7.22M, False: 27]
  |  Branch (99:39): [True: 99, False: 8.55M]
  |  Branch (99:51): [True: 72, False: 27]
  |  Branch (99:64): [True: 27, False: 8.55M]
  |  Branch (99:76): [True: 8.55M, False: 212]
  ------------------
  100|  15.7M|}
llama-grammar.cpp:_ZL10parse_namePKc:
  140|     93|static const char * parse_name(const char * src) {
  141|     93|    const char * pos = src;
  142|  15.7M|    while (is_word_char(*pos)) {
  ------------------
  |  Branch (142:12): [True: 15.7M, False: 93]
  ------------------
  143|  15.7M|        pos++;
  144|  15.7M|    }
  145|     93|    if (pos == src) {
  ------------------
  |  Branch (145:9): [True: 0, False: 93]
  ------------------
  146|      0|        throw std::runtime_error(std::string("expecting name at ") + src);
  147|      0|    }
  148|     93|    return pos;
  149|     93|}
llama-grammar.cpp:_ZZN20llama_grammar_parser14parse_sequenceEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEERNS2_6vectorI21llama_grammar_elementNS6_ISC_EEEEbENK3$_0clEmm:
  462|     27|    auto handle_repetitions = [&](uint64_t min_times, uint64_t max_times) {
  463|     27|        bool no_max = max_times == UINT64_MAX;
  464|     27|        if (last_sym_start == rule.size()) {
  ------------------
  |  Branch (464:13): [True: 0, False: 27]
  ------------------
  465|      0|            throw std::runtime_error(std::string("expecting preceding item to */+/?/{ at ") + pos);
  466|      0|        }
  467|       |
  468|       |        // apply transformation to previous symbol (last_sym_start to end) according to
  469|       |        // the following rewrite rules:
  470|       |        // S{m,n} --> S S S (m times) S'(n-m)
  471|       |        //            S'(x)   ::= S S'(x-1) |
  472|       |        //            (... n-m definitions of these S' rules ...)
  473|       |        //            S'(1)   ::= S |
  474|       |        // S{m,} -->  S S S (m times) S'
  475|       |        //            S'     ::= S S' |
  476|       |        // S*     --> S{0,}
  477|       |        //        --> S'     ::= S S' |
  478|       |        // S+     --> S{1,}
  479|       |        //        --> S S'
  480|       |        //            S'     ::= S S' |
  481|       |        // S?     --> S{0,1}
  482|       |        //        --> S'
  483|       |        //            S'     ::= S |
  484|       |
  485|     27|        llama_grammar_rule prev_rule(rule.begin() + last_sym_start, rule.end());
  486|       |        // Calculate the total number of rules that will be generated by this repetition
  487|     27|        uint64_t total_rules = 1; // Start with 1 for the original rule
  488|     27|        if (!no_max && max_times > 0) {
  ------------------
  |  Branch (488:13): [True: 27, False: 0]
  |  Branch (488:24): [True: 27, False: 0]
  ------------------
  489|     27|            total_rules = max_times;
  490|     27|        } else if (min_times > 0) {
  ------------------
  |  Branch (490:20): [True: 0, False: 0]
  ------------------
  491|      0|            total_rules = min_times;
  492|      0|        }
  493|       |
  494|     27|        if (n_prev_rules * total_rules >= MAX_REPETITION_THRESHOLD) {
  ------------------
  |  |   13|     27|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
  |  Branch (494:13): [True: 0, False: 27]
  ------------------
  495|      0|            throw std::runtime_error("number of rules that are going to be repeated multiplied by the new repetition exceeds sane defaults, please reduce the number of repetitions or rule complexity");
  496|      0|        }
  497|       |
  498|     27|        if (min_times == 0) {
  ------------------
  |  Branch (498:13): [True: 27, False: 0]
  ------------------
  499|     27|            rule.resize(last_sym_start);
  500|     27|        } else {
  501|       |            // Repeat the previous elements (min_times - 1) times
  502|      0|            for (uint64_t i = 1; i < min_times; i++) {
  ------------------
  |  Branch (502:34): [True: 0, False: 0]
  ------------------
  503|      0|                rule.insert(rule.end(), prev_rule.begin(), prev_rule.end());
  504|      0|            }
  505|      0|        }
  506|       |
  507|     27|        uint32_t last_rec_rule_id = 0;
  508|     27|        auto n_opt = no_max ? 1 : max_times - min_times;
  ------------------
  |  Branch (508:22): [True: 0, False: 27]
  ------------------
  509|       |
  510|     27|        llama_grammar_rule rec_rule(prev_rule);
  511|     54|        for (uint64_t i = 0; i < n_opt; i++) {
  ------------------
  |  Branch (511:30): [True: 27, False: 27]
  ------------------
  512|     27|            rec_rule.resize(prev_rule.size());
  513|     27|            uint32_t rec_rule_id = generate_symbol_id( rule_name);
  514|     27|            if (i > 0 || no_max) {
  ------------------
  |  Branch (514:17): [True: 0, False: 27]
  |  Branch (514:26): [True: 0, False: 27]
  ------------------
  515|      0|                rec_rule.push_back({LLAMA_GRETYPE_RULE_REF, no_max ? rec_rule_id : last_rec_rule_id});
  ------------------
  |  Branch (515:61): [True: 0, False: 0]
  ------------------
  516|      0|            }
  517|     27|            rec_rule.push_back({LLAMA_GRETYPE_ALT, 0});
  518|     27|            rec_rule.push_back({LLAMA_GRETYPE_END, 0});
  519|     27|            add_rule( rec_rule_id, rec_rule);
  520|     27|            last_rec_rule_id = rec_rule_id;
  521|     27|        }
  522|     27|        if (n_opt > 0) {
  ------------------
  |  Branch (522:13): [True: 27, False: 0]
  ------------------
  523|     27|            rule.push_back({LLAMA_GRETYPE_RULE_REF, last_rec_rule_id});
  524|     27|        }
  525|     27|        n_prev_rules *= total_rules;
  526|     27|        GGML_ASSERT(n_prev_rules >= 1);
  ------------------
  |  |  288|     27|#define GGML_ASSERT(x) if (!(x)) GGML_ABORT("GGML_ASSERT(%s) failed", #x)
  |  |  ------------------
  |  |  |  |  287|      0|#define GGML_ABORT(...) ggml_abort(__FILE__, __LINE__, __VA_ARGS__)
  |  |  ------------------
  |  |  |  Branch (288:28): [True: 0, False: 27]
  |  |  ------------------
  ------------------
  527|     27|    };
llama-grammar.cpp:_ZL13is_digit_charc:
   94|  11.6M|static bool is_digit_char(char c) {
   95|  11.6M|    return '0' <= c && c <= '9';
  ------------------
  |  Branch (95:12): [True: 11.6M, False: 134]
  |  Branch (95:24): [True: 11.6M, False: 104]
  ------------------
   96|  11.6M|}
llama-grammar.cpp:_ZL9parse_intPKc:
  151|     26|static const char * parse_int(const char * src) {
  152|     26|    const char * pos = src;
  153|  3.11M|    while (is_digit_char(*pos)) {
  ------------------
  |  Branch (153:12): [True: 3.11M, False: 26]
  ------------------
  154|  3.11M|        pos++;
  155|  3.11M|    }
  156|     26|    if (pos == src) {
  ------------------
  |  Branch (156:9): [True: 0, False: 26]
  ------------------
  157|      0|        throw std::runtime_error(std::string("expecting integer at ") + src);
  158|      0|    }
  159|     26|    return pos;
  160|     26|}

_ZN20llama_grammar_parserC2EPK11llama_vocab:
   92|     45|    llama_grammar_parser(const struct llama_vocab * vocab = nullptr) : vocab(vocab) {}