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

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

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