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

_ZN20llama_grammar_parser13get_symbol_idEPKcm:
  415|    222|uint32_t llama_grammar_parser::get_symbol_id(const char * src, size_t len) {
  416|    222|    uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());
  417|    222|    auto result = symbol_ids.emplace(std::string(src, len), next_id);
  418|    222|    return result.first->second;
  419|    222|}
_ZN20llama_grammar_parser18generate_symbol_idERKNSt3__112basic_stringIcNS0_11char_traitsIcEENS0_9allocatorIcEEEE:
  421|    344|uint32_t llama_grammar_parser::generate_symbol_id(const std::string & base_name) {
  422|    344|    uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());
  423|    344|    symbol_ids[base_name + '_' + std::to_string(next_id)] = next_id;
  424|    344|    return next_id;
  425|    344|}
_ZN20llama_grammar_parser8add_ruleEjRKNSt3__16vectorI21llama_grammar_elementNS0_9allocatorIS2_EEEE:
  427|    207|void llama_grammar_parser::add_rule(uint32_t rule_id, const llama_grammar_rule & rule) {
  428|    207|    if (rules.size() <= rule_id) {
  ------------------
  |  Branch (428:9): [True: 195, False: 12]
  ------------------
  429|    195|        rules.resize(rule_id + 1);
  430|    195|    }
  431|    207|    rules[rule_id] = rule;
  432|    207|}
_ZN20llama_grammar_parser16parse_alternatesEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEEjb:
  438|    273|        bool                is_nested) {
  439|    273|    llama_grammar_rule rule;
  440|    273|    const char * pos = parse_sequence(src, rule_name, rule, is_nested);
  441|    278|    while (*pos == '|') {
  ------------------
  |  Branch (441:12): [True: 5, False: 273]
  ------------------
  442|      5|        rule.push_back({LLAMA_GRETYPE_ALT, 0});
  443|      5|        pos = parse_space(pos + 1, true);
  444|      5|        pos = parse_sequence(pos, rule_name, rule, is_nested);
  445|      5|    }
  446|    273|    rule.push_back({LLAMA_GRETYPE_END, 0});
  447|    273|    add_rule(rule_id, rule);
  448|    273|    return pos;
  449|    273|}
_ZN20llama_grammar_parser14parse_sequenceEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEERNS2_6vectorI21llama_grammar_elementNS6_ISC_EEEEb:
  455|    278|        bool               is_nested) {
  456|    278|    size_t last_sym_start = rule.size();
  457|    278|    const char * pos = src;
  458|    278|    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|    278|    auto handle_repetitions = [&](uint64_t min_times, uint64_t max_times) {
  463|    278|        bool no_max = max_times == UINT64_MAX;
  464|    278|        if (last_sym_start == rule.size()) {
  465|    278|            throw std::runtime_error(std::string("expecting preceding item to */+/?/{ at ") + pos);
  466|    278|        }
  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|    278|        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|    278|        uint64_t total_rules = 1; // Start with 1 for the original rule
  488|    278|        if (!no_max && max_times > 0) {
  489|    278|            total_rules = max_times;
  490|    278|        } else if (min_times > 0) {
  491|    278|            total_rules = min_times;
  492|    278|        }
  493|       |
  494|    278|        if (n_prev_rules * total_rules >= MAX_REPETITION_THRESHOLD) {
  495|    278|            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|    278|        }
  497|       |
  498|    278|        if (min_times == 0) {
  499|    278|            rule.resize(last_sym_start);
  500|    278|        } else {
  501|       |            // Repeat the previous elements (min_times - 1) times
  502|    278|            for (uint64_t i = 1; i < min_times; i++) {
  503|    278|                rule.insert(rule.end(), prev_rule.begin(), prev_rule.end());
  504|    278|            }
  505|    278|        }
  506|       |
  507|    278|        uint32_t last_rec_rule_id = 0;
  508|    278|        auto n_opt = no_max ? 1 : max_times - min_times;
  509|       |
  510|    278|        llama_grammar_rule rec_rule(prev_rule);
  511|    278|        for (uint64_t i = 0; i < n_opt; i++) {
  512|    278|            rec_rule.resize(prev_rule.size());
  513|    278|            uint32_t rec_rule_id = generate_symbol_id( rule_name);
  514|    278|            if (i > 0 || no_max) {
  515|    278|                rec_rule.push_back({LLAMA_GRETYPE_RULE_REF, no_max ? rec_rule_id : last_rec_rule_id});
  516|    278|            }
  517|    278|            rec_rule.push_back({LLAMA_GRETYPE_ALT, 0});
  518|    278|            rec_rule.push_back({LLAMA_GRETYPE_END, 0});
  519|    278|            add_rule( rec_rule_id, rec_rule);
  520|    278|            last_rec_rule_id = rec_rule_id;
  521|    278|        }
  522|    278|        if (n_opt > 0) {
  523|    278|            rule.push_back({LLAMA_GRETYPE_RULE_REF, last_rec_rule_id});
  524|    278|        }
  525|    278|        n_prev_rules *= total_rules;
  526|    278|        GGML_ASSERT(n_prev_rules >= 1);
  527|    278|    };
  528|       |
  529|    860|    while (*pos) {
  ------------------
  |  Branch (529:12): [True: 664, False: 196]
  ------------------
  530|    664|        if (*pos == '"') { // literal string
  ------------------
  |  Branch (530:13): [True: 2, False: 662]
  ------------------
  531|      2|            pos++;
  532|      2|            last_sym_start = rule.size();
  533|      2|            n_prev_rules = 1;
  534|   222k|            while (*pos != '"') {
  ------------------
  |  Branch (534:20): [True: 222k, False: 1]
  ------------------
  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|      1|            pos = parse_space(pos + 1, is_nested);
  543|    662|        } else if (*pos == '[') { // char range(s)
  ------------------
  |  Branch (543:20): [True: 64, False: 598]
  ------------------
  544|     64|            pos++;
  545|     64|            enum llama_gretype start_type = LLAMA_GRETYPE_CHAR;
  546|     64|            if (*pos == '^') {
  ------------------
  |  Branch (546:17): [True: 0, False: 64]
  ------------------
  547|      0|                pos++;
  548|      0|                start_type = LLAMA_GRETYPE_CHAR_NOT;
  549|      0|            }
  550|     64|            last_sym_start = rule.size();
  551|     64|            n_prev_rules = 1;
  552|   535k|            while (*pos != ']') {
  ------------------
  |  Branch (552:20): [True: 534k, False: 62]
  ------------------
  553|   534k|                if (!*pos) {
  ------------------
  |  Branch (553:21): [True: 2, False: 534k]
  ------------------
  554|      2|                    throw std::runtime_error("unexpected end of input");
  555|      2|                }
  556|   534k|                auto char_pair = parse_char(pos);
  557|   534k|                     pos       = char_pair.second;
  558|   534k|                enum llama_gretype type = last_sym_start < rule.size()
  ------------------
  |  Branch (558:43): [True: 534k, False: 26]
  ------------------
  559|   534k|                    ? LLAMA_GRETYPE_CHAR_ALT
  560|   534k|                    : start_type;
  561|       |
  562|   534k|                rule.push_back({type, char_pair.first});
  563|   534k|                if (pos[0] == '-' && pos[1] != ']') {
  ------------------
  |  Branch (563:21): [True: 35, False: 534k]
  |  Branch (563:38): [True: 35, False: 0]
  ------------------
  564|     35|                    if (!pos[1]) {
  ------------------
  |  Branch (564:25): [True: 0, False: 35]
  ------------------
  565|      0|                        throw std::runtime_error("unexpected end of input");
  566|      0|                    }
  567|     35|                    auto endchar_pair = parse_char(pos + 1);
  568|     35|                         pos          = endchar_pair.second;
  569|     35|                    rule.push_back({LLAMA_GRETYPE_CHAR_RNG_UPPER, endchar_pair.first});
  570|     35|                }
  571|   534k|            }
  572|     62|            pos = parse_space(pos + 1, is_nested);
  573|    598|        } else if (*pos == '<' || *pos == '!') { // token
  ------------------
  |  Branch (573:20): [True: 13, False: 585]
  |  Branch (573:35): [True: 0, False: 585]
  ------------------
  574|     13|            auto type = LLAMA_GRETYPE_TOKEN;
  575|     13|            if (*pos == '!') { // token inverse
  ------------------
  |  Branch (575:17): [True: 0, False: 13]
  ------------------
  576|      0|                type = LLAMA_GRETYPE_TOKEN_NOT;
  577|      0|                pos++;
  578|      0|            }
  579|     13|            auto token_pair = parse_token(vocab, pos);
  580|     13|            const char * token_end  = token_pair.second;
  581|     13|            last_sym_start = rule.size();
  582|     13|            n_prev_rules = 1;
  583|     13|            rule.push_back({type, token_pair.first});
  584|     13|            pos = parse_space(token_end, is_nested);
  585|    585|        } else if (is_word_char(*pos)) { // rule reference
  ------------------
  |  Branch (585:20): [True: 133, False: 452]
  ------------------
  586|    133|            const char * name_end    = parse_name(pos);
  587|    133|            uint32_t ref_rule_id = get_symbol_id(pos, name_end - pos);
  588|    133|            pos = parse_space(name_end, is_nested);
  589|    133|            last_sym_start = rule.size();
  590|    133|            n_prev_rules = 1;
  591|    133|            rule.push_back({LLAMA_GRETYPE_RULE_REF, ref_rule_id});
  592|    452|        } else if (*pos == '(') { // grouping
  ------------------
  |  Branch (592:20): [True: 199, False: 253]
  ------------------
  593|       |            // parse nested alternates into synthesized rule
  594|    199|            pos = parse_space(pos + 1, true);
  595|    199|            uint32_t n_rules_before = symbol_ids.size();
  596|    199|            uint32_t sub_rule_id = generate_symbol_id(rule_name);
  597|    199|            pos = parse_alternates(pos, rule_name, sub_rule_id, true);
  598|    199|            n_prev_rules = std::max(1u, (uint32_t)symbol_ids.size() - n_rules_before);
  599|    199|            last_sym_start = rule.size();
  600|       |            // output reference to synthesized rule
  601|    199|            rule.push_back({LLAMA_GRETYPE_RULE_REF, sub_rule_id});
  602|    199|            if (*pos != ')') {
  ------------------
  |  Branch (602:17): [True: 12, False: 187]
  ------------------
  603|     12|                throw std::runtime_error(std::string("expecting ')' at ") + pos);
  604|     12|            }
  605|    187|            pos = parse_space(pos + 1, is_nested);
  606|    253|        } else if (*pos == '.') { // any char
  ------------------
  |  Branch (606:20): [True: 6, False: 247]
  ------------------
  607|      6|            last_sym_start = rule.size();
  608|      6|            n_prev_rules = 1;
  609|      6|            rule.push_back({LLAMA_GRETYPE_CHAR_ANY, 0});
  610|      6|            pos = parse_space(pos + 1, is_nested);
  611|    247|        } else if (*pos == '*') {
  ------------------
  |  Branch (611:20): [True: 92, False: 155]
  ------------------
  612|     92|            pos = parse_space(pos + 1, is_nested);
  613|     92|            handle_repetitions(0, -1);
  614|    155|        } else if (*pos == '+') {
  ------------------
  |  Branch (614:20): [True: 8, False: 147]
  ------------------
  615|      8|            pos = parse_space(pos + 1, is_nested);
  616|      8|            handle_repetitions(1, -1);
  617|    147|        } else if (*pos == '?') {
  ------------------
  |  Branch (617:20): [True: 51, False: 96]
  ------------------
  618|     51|            pos = parse_space(pos + 1, is_nested);
  619|     51|            handle_repetitions(0, 1);
  620|     96|        } else if (*pos == '{') {
  ------------------
  |  Branch (620:20): [True: 45, False: 51]
  ------------------
  621|     45|            pos = parse_space(pos + 1, is_nested);
  622|       |
  623|     45|            if (!is_digit_char(*pos)) {
  ------------------
  |  Branch (623:17): [True: 0, False: 45]
  ------------------
  624|      0|                throw std::runtime_error(std::string("expecting an int at ") + pos);
  625|      0|            }
  626|     45|            const char * int_end = parse_int(pos);
  627|     45|            uint64_t min_times = std::stoull(std::string(pos, int_end - pos));
  628|     45|            pos = parse_space(int_end, is_nested);
  629|       |
  630|     45|            uint64_t max_times = UINT64_MAX; // default: no max limit
  631|       |
  632|     45|            if (*pos == '}') {
  ------------------
  |  Branch (632:17): [True: 20, False: 25]
  ------------------
  633|     20|                max_times = min_times;
  634|     20|                pos = parse_space(pos + 1, is_nested);
  635|     25|            } else if (*pos == ',') {
  ------------------
  |  Branch (635:24): [True: 9, False: 16]
  ------------------
  636|      9|                pos = parse_space(pos + 1, is_nested);
  637|       |
  638|      9|                if (is_digit_char(*pos)) {
  ------------------
  |  Branch (638:21): [True: 9, False: 0]
  ------------------
  639|      9|                    const char * int_end = parse_int(pos);
  640|      9|                    max_times = std::stoull(std::string(pos, int_end - pos));
  641|      9|                    pos = parse_space(int_end, is_nested);
  642|      9|                }
  643|       |
  644|      9|                if (*pos != '}') {
  ------------------
  |  Branch (644:21): [True: 0, False: 9]
  ------------------
  645|      0|                    throw std::runtime_error(std::string("expecting '}' at ") + pos);
  646|      0|                }
  647|      9|                pos = parse_space(pos + 1, is_nested);
  648|     16|            } else {
  649|     16|                throw std::runtime_error(std::string("expecting ',' at ") + pos);
  650|     16|            }
  651|     29|            bool has_max = max_times != UINT64_MAX;
  652|     29|            if (min_times > MAX_REPETITION_THRESHOLD || (has_max && max_times > MAX_REPETITION_THRESHOLD)) {
  ------------------
  |  |   13|     58|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
                          if (min_times > MAX_REPETITION_THRESHOLD || (has_max && max_times > MAX_REPETITION_THRESHOLD)) {
  ------------------
  |  |   13|     20|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
  |  Branch (652:17): [True: 9, False: 20]
  |  Branch (652:58): [True: 20, False: 0]
  |  Branch (652:69): [True: 0, False: 20]
  ------------------
  653|      0|                throw std::runtime_error(std::string("number of repetitions exceeds sane defaults, please reduce the number of repetitions"));
  654|      0|            }
  655|     29|            handle_repetitions(min_times, max_times);
  656|     51|        } else {
  657|     51|            break;
  658|     51|        }
  659|    664|    }
  660|    247|    return pos;
  661|    278|}
_ZN20llama_grammar_parser10parse_ruleEPKc:
  663|     89|const char * llama_grammar_parser::parse_rule(const char * src) {
  664|     89|    const char * name_end = parse_name(src);
  665|     89|    const char * pos      = parse_space(name_end, false);
  666|     89|    size_t       name_len = name_end - src;
  667|     89|    uint32_t     rule_id  = get_symbol_id(src, name_len);
  668|     89|    const std::string name(src, name_len);
  669|       |
  670|     89|    if (!(pos[0] == ':' && pos[1] == ':' && pos[2] == '=')) {
  ------------------
  |  Branch (670:11): [True: 75, False: 14]
  |  Branch (670:28): [True: 75, False: 0]
  |  Branch (670:45): [True: 74, False: 1]
  ------------------
  671|     15|        throw std::runtime_error(std::string("expecting ::= at ") + pos);
  672|     15|    }
  673|     74|    pos = parse_space(pos + 3, true);
  674|       |
  675|     74|    pos = parse_alternates(pos, name, rule_id, false);
  676|       |
  677|     74|    if (*pos == '\r') {
  ------------------
  |  Branch (677:9): [True: 0, False: 74]
  ------------------
  678|      0|        pos += pos[1] == '\n' ? 2 : 1;
  ------------------
  |  Branch (678:16): [True: 0, False: 0]
  ------------------
  679|     74|    } else if (*pos == '\n') {
  ------------------
  |  Branch (679:16): [True: 4, False: 70]
  ------------------
  680|      4|        pos++;
  681|     70|    } else if (*pos) {
  ------------------
  |  Branch (681:16): [True: 5, False: 65]
  ------------------
  682|      5|        throw std::runtime_error(std::string("expecting newline or end at ") + pos);
  683|      5|    }
  684|     69|    return parse_space(pos, true);
  685|     74|}
_ZN20llama_grammar_parser5parseEPKc:
  687|     88|bool llama_grammar_parser::parse(const char * src) {
  688|     88|    try {
  689|     88|        const char * pos = parse_space(src, true);
  690|    177|        while (*pos) {
  ------------------
  |  Branch (690:16): [True: 89, False: 88]
  ------------------
  691|     89|            pos = parse_rule(pos);
  692|     89|        }
  693|       |        // Validate the state to ensure that all rules are defined
  694|     88|        for (const auto & rule : rules) {
  ------------------
  |  Branch (694:32): [True: 6, False: 82]
  ------------------
  695|      6|            if (rule.empty()) {
  ------------------
  |  Branch (695:17): [True: 0, False: 6]
  ------------------
  696|      0|                throw std::runtime_error("Undefined rule");
  697|      0|            }
  698|      9|            for (const auto & elem : rule) {
  ------------------
  |  Branch (698:36): [True: 9, False: 0]
  ------------------
  699|      9|                if (elem.type == LLAMA_GRETYPE_RULE_REF) {
  ------------------
  |  Branch (699:21): [True: 9, False: 0]
  ------------------
  700|       |                    // Ensure that the rule at that location exists
  701|      9|                    if (elem.value >= rules.size() || rules[elem.value].empty()) {
  ------------------
  |  Branch (701:25): [True: 6, False: 3]
  |  Branch (701:55): [True: 0, False: 3]
  ------------------
  702|       |                        // Get the name of the rule that is missing
  703|     17|                        for (const auto & kv : symbol_ids) {
  ------------------
  |  Branch (703:46): [True: 17, False: 0]
  ------------------
  704|     17|                            if (kv.second == elem.value) {
  ------------------
  |  Branch (704:33): [True: 6, False: 11]
  ------------------
  705|      6|                                throw std::runtime_error("Undefined rule identifier '" + kv.first + "'");
  706|      6|                            }
  707|     17|                        }
  708|      6|                    }
  709|      9|                }
  710|      9|            }
  711|      6|        }
  712|     88|    } catch (const std::exception & err) {
  713|     85|        fprintf(stderr, "%s: error parsing grammar: %s\n\n%s\n", __func__, err.what(), src);
  714|     85|        rules.clear();
  715|     85|        return false;
  716|     85|    }
  717|       |
  718|      3|    return true;
  719|     88|}
llama-grammar.cpp:_ZL11parse_spacePKcb:
  125|    969|static const char * parse_space(const char * src, bool newline_ok) {
  126|    969|    const char * pos = src;
  127|  1.40k|    while (*pos == ' ' || *pos == '\t' || *pos == '#' ||
  ------------------
  |  Branch (127:12): [True: 35, False: 1.36k]
  |  Branch (127:27): [True: 57, False: 1.30k]
  |  Branch (127:43): [True: 38, False: 1.27k]
  ------------------
  128|  1.27k|            (newline_ok && (*pos == '\r' || *pos == '\n'))) {
  ------------------
  |  Branch (128:14): [True: 1.03k, False: 241]
  |  Branch (128:29): [True: 119, False: 911]
  |  Branch (128:45): [True: 183, False: 728]
  ------------------
  129|    432|        if (*pos == '#') {
  ------------------
  |  Branch (129:13): [True: 38, False: 394]
  ------------------
  130|    181|            while (*pos && *pos != '\r' && *pos != '\n') {
  ------------------
  |  Branch (130:20): [True: 178, False: 3]
  |  Branch (130:28): [True: 153, False: 25]
  |  Branch (130:44): [True: 143, False: 10]
  ------------------
  131|    143|                pos++;
  132|    143|            }
  133|    394|        } else {
  134|    394|            pos++;
  135|    394|        }
  136|    432|    }
  137|    969|    return pos;
  138|    969|}
llama-grammar.cpp:_ZL10parse_charPKc:
  162|   757k|static std::pair<uint32_t, const char *> parse_char(const char * src) {
  163|   757k|    if (*src == '\\') {
  ------------------
  |  Branch (163:9): [True: 0, False: 757k]
  ------------------
  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|   757k|    } else if (*src) {
  ------------------
  |  Branch (179:16): [True: 757k, False: 0]
  ------------------
  180|   757k|        return decode_utf8(src);
  181|   757k|    }
  182|      0|    throw std::runtime_error("unexpected end of input");
  183|   757k|}
llama-grammar.cpp:_ZL11decode_utf8PKc:
   19|   757k|static std::pair<uint32_t, const char *> decode_utf8(const char * src) {
   20|   757k|    static const int lookup[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4 };
   21|   757k|    uint8_t  first_byte = static_cast<uint8_t>(*src);
   22|   757k|    uint8_t  highbits   = first_byte >> 4;
   23|   757k|    int      len        = lookup[highbits];
   24|   757k|    uint8_t  mask       = (1 << (8 - len)) - 1;
   25|   757k|    uint32_t value      = first_byte & mask;
   26|   757k|    const char * end    = src + len; // may overrun!
   27|   757k|    const char * pos    = src + 1;
   28|   757k|    for ( ; pos < end && *pos; pos++) {
  ------------------
  |  Branch (28:13): [True: 461, False: 757k]
  |  Branch (28:26): [True: 461, False: 0]
  ------------------
   29|    461|        value = (value << 6) + (static_cast<uint8_t>(*pos) & 0x3F);
   30|    461|    }
   31|   757k|    return std::make_pair(value, pos);
   32|   757k|}
llama-grammar.cpp:_ZL11parse_tokenPK11llama_vocabPKc:
  185|     13|static std::pair<uint32_t, const char *> parse_token(const llama_vocab * vocab, const char * src) {
  186|     13|    const char * pos = src;
  187|     13|    if (*pos != '<') {
  ------------------
  |  Branch (187:9): [True: 0, False: 13]
  ------------------
  188|      0|        throw std::runtime_error(std::string("expecting '<' at ") + pos);
  189|      0|    }
  190|     13|    pos++;
  191|       |
  192|       |    // Parse <[id]>
  193|     13|    if (*pos == '[') {
  ------------------
  |  Branch (193:9): [True: 13, False: 0]
  ------------------
  194|     13|        pos++;
  195|     13|        const char * int_end = parse_int(pos);
  196|     13|        uint32_t token_id = std::stoul(std::string(pos, int_end - pos));
  197|     13|        pos = int_end;
  198|     13|        if (*pos != ']') {
  ------------------
  |  Branch (198:13): [True: 0, False: 13]
  ------------------
  199|      0|            throw std::runtime_error(std::string("expecting ']' at ") + pos);
  200|      0|        }
  201|     13|        pos++;
  202|     13|        if (*pos != '>') {
  ------------------
  |  Branch (202:13): [True: 0, False: 13]
  ------------------
  203|      0|            throw std::runtime_error(std::string("expecting '>' at ") + pos);
  204|      0|        }
  205|     13|        pos++;
  206|     13|        return std::make_pair(token_id, pos);
  207|     13|    }
  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|  18.3M|static bool is_word_char(char c) {
   99|  18.3M|    return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '-' || is_digit_char(c);
  ------------------
  |  Branch (99:13): [True: 8.56M, False: 9.74M]
  |  Branch (99:25): [True: 8.56M, False: 63]
  |  Branch (99:39): [True: 603, False: 9.74M]
  |  Branch (99:51): [True: 508, False: 95]
  |  Branch (99:64): [True: 46, False: 9.74M]
  |  Branch (99:76): [True: 9.74M, False: 674]
  ------------------
  100|  18.3M|}
llama-grammar.cpp:_ZL10parse_namePKc:
  140|    222|static const char * parse_name(const char * src) {
  141|    222|    const char * pos = src;
  142|  18.3M|    while (is_word_char(*pos)) {
  ------------------
  |  Branch (142:12): [True: 18.3M, False: 222]
  ------------------
  143|  18.3M|        pos++;
  144|  18.3M|    }
  145|    222|    if (pos == src) {
  ------------------
  |  Branch (145:9): [True: 0, False: 222]
  ------------------
  146|      0|        throw std::runtime_error(std::string("expecting name at ") + src);
  147|      0|    }
  148|    222|    return pos;
  149|    222|}
llama-grammar.cpp:_ZZN20llama_grammar_parser14parse_sequenceEPKcRKNSt3__112basic_stringIcNS2_11char_traitsIcEENS2_9allocatorIcEEEERNS2_6vectorI21llama_grammar_elementNS6_ISC_EEEEbENK3$_0clEmm:
  462|    171|    auto handle_repetitions = [&](uint64_t min_times, uint64_t max_times) {
  463|    171|        bool no_max = max_times == UINT64_MAX;
  464|    171|        if (last_sym_start == rule.size()) {
  ------------------
  |  Branch (464:13): [True: 6, False: 165]
  ------------------
  465|      6|            throw std::runtime_error(std::string("expecting preceding item to */+/?/{ at ") + pos);
  466|      6|        }
  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|    165|        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|    165|        uint64_t total_rules = 1; // Start with 1 for the original rule
  488|    165|        if (!no_max && max_times > 0) {
  ------------------
  |  Branch (488:13): [True: 70, False: 95]
  |  Branch (488:24): [True: 70, False: 0]
  ------------------
  489|     70|            total_rules = max_times;
  490|     95|        } else if (min_times > 0) {
  ------------------
  |  Branch (490:20): [True: 4, False: 91]
  ------------------
  491|      4|            total_rules = min_times;
  492|      4|        }
  493|       |
  494|    165|        if (n_prev_rules * total_rules >= MAX_REPETITION_THRESHOLD) {
  ------------------
  |  |   13|    165|#define MAX_REPETITION_THRESHOLD 2000
  ------------------
  |  Branch (494:13): [True: 0, False: 165]
  ------------------
  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|    165|        if (min_times == 0) {
  ------------------
  |  Branch (498:13): [True: 141, False: 24]
  ------------------
  499|    141|            rule.resize(last_sym_start);
  500|    141|        } else {
  501|       |            // Repeat the previous elements (min_times - 1) times
  502|  3.52k|            for (uint64_t i = 1; i < min_times; i++) {
  ------------------
  |  Branch (502:34): [True: 3.49k, False: 24]
  ------------------
  503|  3.49k|                rule.insert(rule.end(), prev_rule.begin(), prev_rule.end());
  504|  3.49k|            }
  505|     24|        }
  506|       |
  507|    165|        uint32_t last_rec_rule_id = 0;
  508|    165|        auto n_opt = no_max ? 1 : max_times - min_times;
  ------------------
  |  Branch (508:22): [True: 95, False: 70]
  ------------------
  509|       |
  510|    165|        llama_grammar_rule rec_rule(prev_rule);
  511|    310|        for (uint64_t i = 0; i < n_opt; i++) {
  ------------------
  |  Branch (511:30): [True: 145, False: 165]
  ------------------
  512|    145|            rec_rule.resize(prev_rule.size());
  513|    145|            uint32_t rec_rule_id = generate_symbol_id( rule_name);
  514|    145|            if (i > 0 || no_max) {
  ------------------
  |  Branch (514:17): [True: 0, False: 145]
  |  Branch (514:26): [True: 95, False: 50]
  ------------------
  515|     95|                rec_rule.push_back({LLAMA_GRETYPE_RULE_REF, no_max ? rec_rule_id : last_rec_rule_id});
  ------------------
  |  Branch (515:61): [True: 95, False: 0]
  ------------------
  516|     95|            }
  517|    145|            rec_rule.push_back({LLAMA_GRETYPE_ALT, 0});
  518|    145|            rec_rule.push_back({LLAMA_GRETYPE_END, 0});
  519|    145|            add_rule( rec_rule_id, rec_rule);
  520|    145|            last_rec_rule_id = rec_rule_id;
  521|    145|        }
  522|    165|        if (n_opt > 0) {
  ------------------
  |  Branch (522:13): [True: 145, False: 20]
  ------------------
  523|    145|            rule.push_back({LLAMA_GRETYPE_RULE_REF, last_rec_rule_id});
  524|    145|        }
  525|    165|        n_prev_rules *= total_rules;
  526|    165|        GGML_ASSERT(n_prev_rules >= 1);
  ------------------
  |  |  288|    165|#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: 165]
  |  |  ------------------
  ------------------
  527|    165|    };
llama-grammar.cpp:_ZL13is_digit_charc:
   94|  14.7M|static bool is_digit_char(char c) {
   95|  14.7M|    return '0' <= c && c <= '9';
  ------------------
  |  Branch (95:12): [True: 14.7M, False: 475]
  |  Branch (95:24): [True: 14.7M, False: 266]
  ------------------
   96|  14.7M|}
llama-grammar.cpp:_ZL9parse_intPKc:
  151|     67|static const char * parse_int(const char * src) {
  152|     67|    const char * pos = src;
  153|  5.01M|    while (is_digit_char(*pos)) {
  ------------------
  |  Branch (153:12): [True: 5.01M, False: 67]
  ------------------
  154|  5.01M|        pos++;
  155|  5.01M|    }
  156|     67|    if (pos == src) {
  ------------------
  |  Branch (156:9): [True: 0, False: 67]
  ------------------
  157|      0|        throw std::runtime_error(std::string("expecting integer at ") + src);
  158|      0|    }
  159|     67|    return pos;
  160|     67|}

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