Felipe97/llama-cpp-compiled
01.1k
1#include "llama-grammar.h"2 3#include "llama-impl.h"4#include "llama-vocab.h"5#include "llama-sampler.h"6 7#include <cmath>8#include <algorithm>9#include <cstdint>10#include <set>11#include <stdexcept>12 13#define MAX_REPETITION_THRESHOLD 200014//15// helpers16//17 18// NOTE: assumes valid utf8 (but checks for overrun)19static std::pair<uint32_t, const char *> decode_utf8(const char * src) {20 static const int lookup[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4 };21 uint8_t first_byte = static_cast<uint8_t>(*src);22 uint8_t highbits = first_byte >> 4;23 int len = lookup[highbits];24 uint8_t mask = (1 << (8 - len)) - 1;25 uint32_t value = first_byte & mask;26 const char * end = src + len; // may overrun!27 const char * pos = src + 1;28 for ( ; pos < end && *pos; pos++) {29 value = (value << 6) + (static_cast<uint8_t>(*pos) & 0x3F);30 }31 return std::make_pair(value, pos);32}33 34static std::pair<std::vector<uint32_t>, llama_partial_utf8> decode_utf8(35 const std::string & src,36 llama_partial_utf8 partial_start) {37 static const int lookup[] = { 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 3, 4 };38 const char * pos = src.c_str();39 std::vector<uint32_t> code_points;40 41 // common english strings have the same number of codepoints and bytes. `+ 1` for the terminating 0.42 code_points.reserve(src.size() + 1);43 uint32_t value = partial_start.value;44 int n_remain = partial_start.n_remain;45 46 // continue previous decode, if applicable47 while (*pos != 0 && n_remain > 0) {48 uint8_t next_byte = static_cast<uint8_t>(*pos);49 if ((next_byte >> 6) != 2) {50 // invalid sequence, abort51 code_points.push_back(0);52 return std::make_pair(std::move(code_points), llama_partial_utf8{ 0, -1 });53 }54 value = (value << 6) + (next_byte & 0x3F);55 ++pos;56 --n_remain;57 }58 59 if (partial_start.n_remain > 0 && n_remain == 0) {60 code_points.push_back(value);61 }62 63 // decode any subsequent utf-8 sequences, which may end in an incomplete one64 while (*pos != 0) {65 uint8_t first_byte = static_cast<uint8_t>(*pos);66 uint8_t highbits = first_byte >> 4;67 n_remain = lookup[highbits] - 1;68 69 if (n_remain < 0) {70 // invalid sequence, abort71 code_points.clear();72 code_points.push_back(0);73 return std::make_pair(std::move(code_points), llama_partial_utf8{ 0, n_remain });74 }75 76 uint8_t mask = (1 << (7 - n_remain)) - 1;77 value = first_byte & mask;78 79 ++pos;80 while (*pos != 0 && n_remain > 0) {81 value = (value << 6) + (static_cast<uint8_t>(*pos) & 0x3F);82 ++pos;83 --n_remain;84 }85 if (n_remain == 0) {86 code_points.push_back(value);87 }88 }89 code_points.push_back(0);90 91 return std::make_pair(std::move(code_points), llama_partial_utf8{ value, n_remain });92}93 94static bool is_digit_char(char c) {95 return '0' <= c && c <= '9';96}97 98static bool is_word_char(char c) {99 return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '-' || is_digit_char(c);100}101 102static std::pair<uint32_t, const char *> parse_hex(const char * src, int size) {103 const char * pos = src;104 const char * end = src + size;105 uint32_t value = 0;106 for ( ; pos < end && *pos; pos++) {107 value <<= 4;108 char c = *pos;109 if ('a' <= c && c <= 'f') {110 value += c - 'a' + 10;111 } else if ('A' <= c && c <= 'F') {112 value += c - 'A' + 10;113 } else if ('0' <= c && c <= '9') {114 value += c - '0';115 } else {116 break;117 }118 }119 if (pos != end) {120 throw std::runtime_error("expecting " + std::to_string(size) + " hex chars at " + src);121 }122 return std::make_pair(value, pos);123}124 125static const char * parse_space(const char * src, bool newline_ok) {126 const char * pos = src;127 while (*pos == ' ' || *pos == '\t' || *pos == '#' ||128 (newline_ok && (*pos == '\r' || *pos == '\n'))) {129 if (*pos == '#') {130 while (*pos && *pos != '\r' && *pos != '\n') {131 pos++;132 }133 } else {134 pos++;135 }136 }137 return pos;138}139 140static const char * parse_name(const char * src) {141 const char * pos = src;142 while (is_word_char(*pos)) {143 pos++;144 }145 if (pos == src) {146 throw std::runtime_error(std::string("expecting name at ") + src);147 }148 return pos;149}150 151static const char * parse_int(const char * src) {152 const char * pos = src;153 while (is_digit_char(*pos)) {154 pos++;155 }156 if (pos == src) {157 throw std::runtime_error(std::string("expecting integer at ") + src);158 }159 return pos;160}161 162static std::pair<uint32_t, const char *> parse_char(const char * src) {163 if (*src == '\\') {164 switch (src[1]) {165 case 'x': return parse_hex(src + 2, 2);166 case 'u': return parse_hex(src + 2, 4);167 case 'U': return parse_hex(src + 2, 8);168 case 't': return std::make_pair('\t', src + 2);169 case 'r': return std::make_pair('\r', src + 2);170 case 'n': return std::make_pair('\n', src + 2);171 case '\\':172 case '"':173 case '[':174 case ']':175 case '-':176 return std::make_pair(src[1], src + 2);177 default:178 throw std::runtime_error(std::string("unknown escape at ") + src);179 }180 } else if (*src) {181 return decode_utf8(src);182 }183 throw std::runtime_error("unexpected end of input");184}185 186static std::pair<uint32_t, const char *> parse_token(const llama_vocab * vocab, const char * src) {187 const char * pos = src;188 if (*pos != '<') {189 throw std::runtime_error(std::string("expecting '<' at ") + pos);190 }191 pos++;192 193 // Parse <[id]>194 if (*pos == '[') {195 pos++;196 const char * int_end = parse_int(pos);197 uint32_t token_id = std::stoul(std::string(pos, int_end - pos));198 pos = int_end;199 if (*pos != ']') {200 throw std::runtime_error(std::string("expecting ']' at ") + pos);201 }202 pos++;203 if (*pos != '>') {204 throw std::runtime_error(std::string("expecting '>' at ") + pos);205 }206 pos++;207 return std::make_pair(token_id, pos);208 }209 210 if (vocab == nullptr) {211 throw std::runtime_error(std::string("no vocab to parse token at ") + src);212 }213 214 // Parse <token> and tokenize to obtain the token id215 while (*pos != 0 && *pos != '>') {216 pos++;217 }218 if (*pos != '>') {219 throw std::runtime_error(std::string("expecting '>' at ") + pos);220 }221 pos++;222 223 llama_token tokens[2];224 int32_t n_tokens = vocab->tokenize(src, static_cast<int32_t>(pos - src), tokens, 2, false, true);225 if (n_tokens != 1) {226 // must tokenize to exactly 1 token227 throw std::runtime_error("invalid token '" + std::string(src, pos - src) + "'");228 }229 return std::make_pair(tokens[0], pos);230}231 232static void print_grammar_char(FILE * file, uint32_t c) {233 if (0x20 <= c && c <= 0x7f) {234 fprintf(file, "%c", static_cast<char>(c));235 } else {236 // cop out of encoding UTF-8237 fprintf(file, "<U+%04X>", c);238 }239}240 241static bool is_char_element(llama_grammar_element elem) {242 switch (elem.type) {243 case LLAMA_GRETYPE_CHAR: return true;244 case LLAMA_GRETYPE_CHAR_NOT: return true;245 case LLAMA_GRETYPE_CHAR_ALT: return true;246 case LLAMA_GRETYPE_CHAR_RNG_UPPER: return true;247 case LLAMA_GRETYPE_CHAR_ANY: return true;248 default: return false;249 }250}251 252static void print_rule_binary(FILE * file, const llama_grammar_rule & rule) {253 for (auto elem : rule) {254 switch (elem.type) {255 case LLAMA_GRETYPE_END: fprintf(file, "END"); break;256 case LLAMA_GRETYPE_ALT: fprintf(file, "ALT"); break;257 case LLAMA_GRETYPE_RULE_REF: fprintf(file, "RULE_REF"); break;258 case LLAMA_GRETYPE_CHAR: fprintf(file, "CHAR"); break;259 case LLAMA_GRETYPE_CHAR_NOT: fprintf(file, "CHAR_NOT"); break;260 case LLAMA_GRETYPE_CHAR_RNG_UPPER: fprintf(file, "CHAR_RNG_UPPER"); break;261 case LLAMA_GRETYPE_CHAR_ALT: fprintf(file, "CHAR_ALT"); break;262 case LLAMA_GRETYPE_CHAR_ANY: fprintf(file, "CHAR_ANY"); break;263 case LLAMA_GRETYPE_TOKEN: fprintf(file, "TOKEN"); break;264 case LLAMA_GRETYPE_TOKEN_NOT: fprintf(file, "TOKEN_NOT"); break;265 }266 switch (elem.type) {267 case LLAMA_GRETYPE_END:268 case LLAMA_GRETYPE_ALT:269 case LLAMA_GRETYPE_RULE_REF:270 fprintf(file, "(%u) ", elem.value);271 break;272 case LLAMA_GRETYPE_CHAR:273 case LLAMA_GRETYPE_CHAR_NOT:274 case LLAMA_GRETYPE_CHAR_RNG_UPPER:275 case LLAMA_GRETYPE_CHAR_ALT:276 case LLAMA_GRETYPE_CHAR_ANY:277 fprintf(file, "(\"");278 print_grammar_char(file, elem.value);279 fprintf(file, "\") ");280 break;281 case LLAMA_GRETYPE_TOKEN:282 fprintf(file, "<[");283 fprintf(file, "%u", elem.value);284 fprintf(file, "]> ");285 break;286 case LLAMA_GRETYPE_TOKEN_NOT:287 fprintf(file, "!");288 fprintf(file, "<[");289 fprintf(file, "%u", elem.value);290 fprintf(file, "]> ");291 break;292 }293 }294 fprintf(file, "\n");295}296 297static void print_rule(298 FILE * file,299 uint32_t rule_id,300 const llama_grammar_rule & rule,301 const std::map<uint32_t, std::string> & symbol_id_names) {302 if (rule.empty() || rule.back().type != LLAMA_GRETYPE_END) {303 throw std::runtime_error(304 "malformed rule, does not end with LLAMA_GRETYPE_END: " + std::to_string(rule_id));305 }306 fprintf(file, "%s ::= ", symbol_id_names.at(rule_id).c_str());307 for (size_t i = 0, end = rule.size() - 1; i < end; i++) {308 llama_grammar_element elem = rule[i];309 switch (elem.type) {310 case LLAMA_GRETYPE_END:311 throw std::runtime_error(312 "unexpected end of rule: " + std::to_string(rule_id) + "," +313 std::to_string(i));314 case LLAMA_GRETYPE_ALT:315 fprintf(file, "| ");316 break;317 case LLAMA_GRETYPE_RULE_REF:318 fprintf(file, "%s ", symbol_id_names.at(elem.value).c_str());319 break;320 case LLAMA_GRETYPE_CHAR:321 fprintf(file, "[");322 print_grammar_char(file, elem.value);323 break;324 case LLAMA_GRETYPE_CHAR_NOT:325 fprintf(file, "[^");326 print_grammar_char(file, elem.value);327 break;328 case LLAMA_GRETYPE_CHAR_RNG_UPPER:329 if (i == 0 || !is_char_element(rule[i - 1])) {330 throw std::runtime_error(331 "LLAMA_GRETYPE_CHAR_RNG_UPPER without preceding char: " +332 std::to_string(rule_id) + "," + std::to_string(i));333 }334 fprintf(file, "-");335 print_grammar_char(file, elem.value);336 break;337 case LLAMA_GRETYPE_CHAR_ALT:338 if (i == 0 || !is_char_element(rule[i - 1])) {339 throw std::runtime_error(340 "LLAMA_GRETYPE_CHAR_ALT without preceding char: " +341 std::to_string(rule_id) + "," + std::to_string(i));342 }343 print_grammar_char(file, elem.value);344 break;345 case LLAMA_GRETYPE_CHAR_ANY:346 fprintf(file, ".");347 break;348 case LLAMA_GRETYPE_TOKEN:349 fprintf(file, "<[");350 fprintf(file, "%u", elem.value);351 fprintf(file, "]> ");352 break;353 case LLAMA_GRETYPE_TOKEN_NOT:354 fprintf(file, "!");355 fprintf(file, "<[");356 fprintf(file, "%u", elem.value);357 fprintf(file, "]> ");358 break;359 }360 if (is_char_element(elem)) {361 switch (rule[i + 1].type) {362 case LLAMA_GRETYPE_CHAR_ALT:363 case LLAMA_GRETYPE_CHAR_RNG_UPPER:364 case LLAMA_GRETYPE_CHAR_ANY:365 break;366 default:367 fprintf(file, "] ");368 }369 }370 }371 fprintf(file, "\n");372}373 374//375// Regex utilities376//377 378size_t llama_grammar_trigger_pattern::find(const std::string & input) const {379 auto find_start_pos = [](const std::smatch & match) {380 // get from the first matched capturing group to the end of the string381 size_t start = std::string::npos;382 for (auto i = 1u; i < match.size(); i++) {383 if (match.length(i) > 0) {384 start = match.position(i);385 break;386 }387 }388 if (start == std::string::npos) {389 start = match.position(0);390 }391 return start;392 };393 394 if (!pattern.empty() && pattern.front() == '^' && pattern.back() == '$') {395 // match against the entire input396 std::smatch match;397 if (std::regex_match(input, match, regex)) {398 return find_start_pos(match);399 }400 }401 402 // search anywhere403 std::smatch match;404 if (std::regex_search(input, match, regex)) {405 return find_start_pos(match);406 }407 408 return std::string::npos;409}410 411 412//413// implementation414//415 416uint32_t llama_grammar_parser::get_symbol_id(const char * src, size_t len) {417 uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());418 auto result = symbol_ids.emplace(std::string(src, len), next_id);419 return result.first->second;420}421 422uint32_t llama_grammar_parser::generate_symbol_id(const std::string & base_name) {423 uint32_t next_id = static_cast<uint32_t>(symbol_ids.size());424 symbol_ids[base_name + '_' + std::to_string(next_id)] = next_id;425 return next_id;426}427 428void llama_grammar_parser::add_rule(uint32_t rule_id, const llama_grammar_rule & rule) {429 if (rules.size() <= rule_id) {430 rules.resize(rule_id + 1);431 }432 rules[rule_id] = rule;433}434 435const char * llama_grammar_parser::parse_alternates(436 const char * src,437 const std::string & rule_name,438 uint32_t rule_id,439 bool is_nested) {440 llama_grammar_rule rule;441 const char * pos = parse_sequence(src, rule_name, rule, is_nested);442 while (*pos == '|') {443 rule.push_back({LLAMA_GRETYPE_ALT, 0});444 pos = parse_space(pos + 1, true);445 pos = parse_sequence(pos, rule_name, rule, is_nested);446 }447 rule.push_back({LLAMA_GRETYPE_END, 0});448 add_rule(rule_id, rule);449 return pos;450}451 452const char * llama_grammar_parser::parse_sequence(453 const char * src,454 const std::string & rule_name,455 llama_grammar_rule & rule,456 bool is_nested) {457 size_t last_sym_start = rule.size();458 const char * pos = src;459 uint64_t n_prev_rules = 1;460 461 // use UINT64_MAX as the empty value because we aligned to the proper uint64_t type so -1 can't be used462 // (though it's technically the same as -1 now)463 auto handle_repetitions = [&](uint64_t min_times, uint64_t max_times) {464 bool no_max = max_times == UINT64_MAX;465 if (last_sym_start == rule.size()) {466 throw std::runtime_error(std::string("expecting preceding item to */+/?/{ at ") + pos);467 }468 469 // apply transformation to previous symbol (last_sym_start to end) according to470 // the following rewrite rules:471 // S{m,n} --> S S S (m times) S'(n-m)472 // S'(x) ::= S S'(x-1) |473 // (... n-m definitions of these S' rules ...)474 // S'(1) ::= S |475 // S{m,} --> S S S (m times) S'476 // S' ::= S S' |477 // S* --> S{0,}478 // --> S' ::= S S' |479 // S+ --> S{1,}480 // --> S S'481 // S' ::= S S' |482 // S? --> S{0,1}483 // --> S'484 // S' ::= S |485 486 llama_grammar_rule prev_rule(rule.begin() + last_sym_start, rule.end());487 // Calculate the total number of rules that will be generated by this repetition488 uint64_t total_rules = 1; // Start with 1 for the original rule489 if (!no_max && max_times > 0) {490 total_rules = max_times;491 } else if (min_times > 0) {492 total_rules = min_times;493 }494 495 if (n_prev_rules * total_rules > MAX_REPETITION_THRESHOLD) {496 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");497 }498 499 if (min_times == 0) {500 rule.resize(last_sym_start);501 } else {502 // Repeat the previous elements (min_times - 1) times503 for (uint64_t i = 1; i < min_times; i++) {504 rule.insert(rule.end(), prev_rule.begin(), prev_rule.end());505 }506 }507 508 uint32_t last_rec_rule_id = 0;509 auto n_opt = no_max ? 1 : max_times - min_times;510 511 llama_grammar_rule rec_rule(prev_rule);512 for (uint64_t i = 0; i < n_opt; i++) {513 rec_rule.resize(prev_rule.size());514 uint32_t rec_rule_id = generate_symbol_id( rule_name);515 if (i > 0 || no_max) {516 rec_rule.push_back({LLAMA_GRETYPE_RULE_REF, no_max ? rec_rule_id : last_rec_rule_id});517 }518 rec_rule.push_back({LLAMA_GRETYPE_ALT, 0});519 rec_rule.push_back({LLAMA_GRETYPE_END, 0});520 add_rule( rec_rule_id, rec_rule);521 last_rec_rule_id = rec_rule_id;522 }523 if (n_opt > 0) {524 rule.push_back({LLAMA_GRETYPE_RULE_REF, last_rec_rule_id});525 }526 n_prev_rules *= total_rules;527 GGML_ASSERT(n_prev_rules >= 1);528 };529 530 while (*pos) {531 if (*pos == '"') { // literal string532 pos++;533 last_sym_start = rule.size();534 n_prev_rules = 1;535 while (*pos != '"') {536 if (!*pos) {537 throw std::runtime_error("unexpected end of input");538 }539 auto char_pair = parse_char(pos);540 pos = char_pair.second;541 rule.push_back({LLAMA_GRETYPE_CHAR, char_pair.first});542 }543 pos = parse_space(pos + 1, is_nested);544 } else if (*pos == '[') { // char range(s)545 pos++;546 enum llama_gretype start_type = LLAMA_GRETYPE_CHAR;547 if (*pos == '^') {548 pos++;549 start_type = LLAMA_GRETYPE_CHAR_NOT;550 }551 last_sym_start = rule.size();552 n_prev_rules = 1;553 while (*pos != ']') {554 if (!*pos) {555 throw std::runtime_error("unexpected end of input");556 }557 auto char_pair = parse_char(pos);558 pos = char_pair.second;559 enum llama_gretype type = last_sym_start < rule.size()560 ? LLAMA_GRETYPE_CHAR_ALT561 : start_type;562 563 rule.push_back({type, char_pair.first});564 if (pos[0] == '-' && pos[1] != ']') {565 if (!pos[1]) {566 throw std::runtime_error("unexpected end of input");567 }568 auto endchar_pair = parse_char(pos + 1);569 pos = endchar_pair.second;570 rule.push_back({LLAMA_GRETYPE_CHAR_RNG_UPPER, endchar_pair.first});571 }572 }573 pos = parse_space(pos + 1, is_nested);574 } else if (*pos == '<' || *pos == '!') { // token575 auto type = LLAMA_GRETYPE_TOKEN;576 if (*pos == '!') { // token inverse577 type = LLAMA_GRETYPE_TOKEN_NOT;578 pos++;579 }580 auto token_pair = parse_token(vocab, pos);581 const char * token_end = token_pair.second;582 last_sym_start = rule.size();583 n_prev_rules = 1;584 rule.push_back({type, token_pair.first});585 pos = parse_space(token_end, is_nested);586 } else if (is_word_char(*pos)) { // rule reference587 const char * name_end = parse_name(pos);588 uint32_t ref_rule_id = get_symbol_id(pos, name_end - pos);589 pos = parse_space(name_end, is_nested);590 last_sym_start = rule.size();591 n_prev_rules = 1;592 rule.push_back({LLAMA_GRETYPE_RULE_REF, ref_rule_id});593 } else if (*pos == '(') { // grouping594 // parse nested alternates into synthesized rule595 pos = parse_space(pos + 1, true);596 uint32_t n_rules_before = symbol_ids.size();597 uint32_t sub_rule_id = generate_symbol_id(rule_name);598 pos = parse_alternates(pos, rule_name, sub_rule_id, true);599 n_prev_rules = std::max(1u, (uint32_t)symbol_ids.size() - n_rules_before);600 last_sym_start = rule.size();601 // output reference to synthesized rule602 rule.push_back({LLAMA_GRETYPE_RULE_REF, sub_rule_id});603 if (*pos != ')') {604 throw std::runtime_error(std::string("expecting ')' at ") + pos);605 }606 pos = parse_space(pos + 1, is_nested);607 } else if (*pos == '.') { // any char608 last_sym_start = rule.size();609 n_prev_rules = 1;610 rule.push_back({LLAMA_GRETYPE_CHAR_ANY, 0});611 pos = parse_space(pos + 1, is_nested);612 } else if (*pos == '*') {613 pos = parse_space(pos + 1, is_nested);614 handle_repetitions(0, -1);615 } else if (*pos == '+') {616 pos = parse_space(pos + 1, is_nested);617 handle_repetitions(1, -1);618 } else if (*pos == '?') {619 pos = parse_space(pos + 1, is_nested);620 handle_repetitions(0, 1);621 } else if (*pos == '{') {622 pos = parse_space(pos + 1, is_nested);623 624 if (!is_digit_char(*pos)) {625 throw std::runtime_error(std::string("expecting an int at ") + pos);626 }627 const char * int_end = parse_int(pos);628 uint64_t min_times = std::stoull(std::string(pos, int_end - pos));629 pos = parse_space(int_end, is_nested);630 631 uint64_t max_times = UINT64_MAX; // default: no max limit632 633 if (*pos == '}') {634 max_times = min_times;635 pos = parse_space(pos + 1, is_nested);636 } else if (*pos == ',') {637 pos = parse_space(pos + 1, is_nested);638 639 if (is_digit_char(*pos)) {640 const char * int_end = parse_int(pos);641 max_times = std::stoull(std::string(pos, int_end - pos));642 pos = parse_space(int_end, is_nested);643 }644 645 if (*pos != '}') {646 throw std::runtime_error(std::string("expecting '}' at ") + pos);647 }648 pos = parse_space(pos + 1, is_nested);649 } else {650 throw std::runtime_error(std::string("expecting ',' at ") + pos);651 }652 if (min_times > MAX_REPETITION_THRESHOLD) {653 throw std::runtime_error(std::string("number of repetitions exceeds sane defaults, please reduce the number of repetitions"));654 }655 if (max_times != UINT64_MAX && max_times > MAX_REPETITION_THRESHOLD) {656 max_times = UINT64_MAX;657 }658 handle_repetitions(min_times, max_times);659 } else {660 break;661 }662 }663 return pos;664}665 666const char * llama_grammar_parser::parse_rule(const char * src) {667 const char * name_end = parse_name(src);668 const char * pos = parse_space(name_end, false);669 size_t name_len = name_end - src;670 uint32_t rule_id = get_symbol_id(src, name_len);671 const std::string name(src, name_len);672 673 if (!(pos[0] == ':' && pos[1] == ':' && pos[2] == '=')) {674 throw std::runtime_error(std::string("expecting ::= at ") + pos);675 }676 pos = parse_space(pos + 3, true);677 678 pos = parse_alternates(pos, name, rule_id, false);679 680 if (*pos == '\r') {681 pos += pos[1] == '\n' ? 2 : 1;682 } else if (*pos == '\n') {683 pos++;684 } else if (*pos) {685 throw std::runtime_error(std::string("expecting newline or end at ") + pos);686 }687 return parse_space(pos, true);688}689 690bool llama_grammar_parser::parse(const char * src) {691 try {692 const char * pos = parse_space(src, true);693 while (*pos) {694 pos = parse_rule(pos);695 }696 // Validate the state to ensure that all rules are defined697 for (const auto & rule : rules) {698 if (rule.empty()) {699 throw std::runtime_error("Undefined rule");700 }701 for (const auto & elem : rule) {702 if (elem.type == LLAMA_GRETYPE_RULE_REF) {703 // Ensure that the rule at that location exists704 if (elem.value >= rules.size() || rules[elem.value].empty()) {705 // Get the name of the rule that is missing706 for (const auto & kv : symbol_ids) {707 if (kv.second == elem.value) {708 throw std::runtime_error("Undefined rule identifier '" + kv.first + "'");709 }710 }711 }712 }713 }714 }715 } catch (const std::exception & err) {716 fprintf(stderr, "%s: error parsing grammar: %s\n\n%s\n", __func__, err.what(), src);717 rules.clear();718 return false;719 }720 721 return true;722}723 724void llama_grammar_parser::print(FILE * file) {725 try {726 std::map<uint32_t, std::string> symbol_id_names;727 for (const auto & kv : symbol_ids) {728 symbol_id_names[kv.second] = kv.first;729 }730 for (size_t i = 0, end = rules.size(); i < end; i++) {731 // fprintf(file, "%zu: ", i);732 // print_rule_binary(file, rules[i]);733 print_rule(file, uint32_t(i), rules[i], symbol_id_names);734 // fprintf(file, "\n");735 }736 } catch (const std::exception & err) {737 fprintf(stderr, "\n%s: error printing grammar: %s\n", __func__, err.what());738 }739}740 741llama_grammar_stack llama_grammar_parser::c_rules() const {742 llama_grammar_stack ret;743 ret.reserve(rules.size());744 for (const auto & rule : rules) {745 ret.push_back(rule.data());746 }747 return ret;748}749 750// returns true iff pos points to the end of one of the definitions of a rule751static bool llama_grammar_is_end_of_sequence(const llama_grammar_element * pos) {752 switch (pos->type) {753 case LLAMA_GRETYPE_END: return true; // NOLINT754 case LLAMA_GRETYPE_ALT: return true; // NOLINT755 default: return false;756 }757}758 759// returns true iff chr satisfies the char range at pos (regular or inverse range)760// asserts that pos is pointing to a char range element761static std::pair<bool, const llama_grammar_element *> llama_grammar_match_char(762 const llama_grammar_element * pos,763 const uint32_t chr) {764 bool found = false;765 bool is_positive_char = pos->type == LLAMA_GRETYPE_CHAR || pos->type == LLAMA_GRETYPE_CHAR_ANY;766 767 GGML_ASSERT(is_positive_char || pos->type == LLAMA_GRETYPE_CHAR_NOT); // NOLINT768 769 do {770 if (pos[1].type == LLAMA_GRETYPE_CHAR_RNG_UPPER) {771 // inclusive range, e.g. [a-z]772 found = found || (pos->value <= chr && chr <= pos[1].value);773 pos += 2;774 } else if (pos->type == LLAMA_GRETYPE_CHAR_ANY) {775 // Any character matches "."776 found = true;777 pos += 1;778 } else {779 // exact char match, e.g. [a] or "a"780 found = found || pos->value == chr;781 pos += 1;782 }783 } while (pos->type == LLAMA_GRETYPE_CHAR_ALT);784 785 return std::make_pair(found == is_positive_char, pos);786}787 788// returns true iff some continuation of the given partial UTF-8 sequence could satisfy the char789// range at pos (regular or inverse range)790// asserts that pos is pointing to a char range element791static bool llama_grammar_match_partial_char(792 const llama_grammar_element * pos,793 const llama_partial_utf8 partial_utf8) {794 bool is_positive_char = pos->type == LLAMA_GRETYPE_CHAR || pos->type == LLAMA_GRETYPE_CHAR_ANY;795 GGML_ASSERT(is_positive_char || pos->type == LLAMA_GRETYPE_CHAR_NOT);796 797 uint32_t partial_value = partial_utf8.value;798 int n_remain = partial_utf8.n_remain;799 800 // invalid sequence or 7-bit char split across 2 bytes (overlong)801 if (n_remain < 0 || (n_remain == 1 && partial_value < 2)) {802 return false;803 }804 805 // range of possible code points this partial UTF-8 sequence could complete to806 uint32_t low = partial_value << (n_remain * 6);807 uint32_t high = low | ((1 << (n_remain * 6)) - 1);808 809 if (low == 0) {810 if (n_remain == 2) {811 low = 1 << 11;812 } else if (n_remain == 3) {813 low = 1 << 16;814 }815 }816 817 do {818 if (pos[1].type == LLAMA_GRETYPE_CHAR_RNG_UPPER) {819 // inclusive range, e.g. [a-z]820 if (pos->value <= high && low <= pos[1].value) {821 return is_positive_char;822 }823 pos += 2;824 } else if (pos->type == LLAMA_GRETYPE_CHAR_ANY) {825 // Any character matches "."826 return true;827 } else {828 // exact char match, e.g. [a] or "a"829 if (low <= pos->value && pos->value <= high) {830 return is_positive_char;831 }832 pos += 1;833 }834 } while (pos->type == LLAMA_GRETYPE_CHAR_ALT);835 836 return !is_positive_char;837}838 839// returns true iff token matches the rule at pos (regular or inverse)840// asserts that pos is pointing to a token element841static bool llama_grammar_match_token(842 const llama_grammar_element * pos,843 const llama_token token) {844 GGML_ASSERT(pos->type == LLAMA_GRETYPE_TOKEN || pos->type == LLAMA_GRETYPE_TOKEN_NOT);845 if (pos->type == LLAMA_GRETYPE_TOKEN) {846 return pos->value == static_cast<uint32_t>(token);847 }848 if (pos->type == LLAMA_GRETYPE_TOKEN_NOT) {849 return pos->value != static_cast<uint32_t>(token);850 }851 return false;852}853 854// transforms a grammar pushdown stack into N possible stacks, all ending855// at a character range (terminal element)856static void llama_grammar_advance_stack(857 const llama_grammar_rules & rules,858 const llama_grammar_stack & stack,859 llama_grammar_stacks & new_stacks) {860 std::vector<llama_grammar_stack> todo;861 todo.push_back(stack);862 863 auto stack_cmp = [](const llama_grammar_stack & a, const llama_grammar_stack & b) {864 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),865 [](const llama_grammar_element * pa, const llama_grammar_element * pb) {866 return pa < pb; // Compare pointer addresses867 }868 );869 };870 871 std::set<llama_grammar_stack, decltype(stack_cmp)> seen(stack_cmp);872 873 while (!todo.empty()) {874 llama_grammar_stack curr_stack_candidate = std::move(todo.back());875 todo.pop_back();876 877 auto [curr_stack_it, inserted] = seen.insert(std::move(curr_stack_candidate));878 if (!inserted) {879 continue;880 }881 const llama_grammar_stack & curr_stack = *curr_stack_it;882 883 if (curr_stack.empty()) {884 if (std::find(new_stacks.begin(), new_stacks.end(), curr_stack) == new_stacks.end()) {885 new_stacks.emplace_back(curr_stack);886 }887 continue;888 }889 890 const llama_grammar_element * pos = curr_stack.back();891 892 switch (pos->type) {893 case LLAMA_GRETYPE_RULE_REF: {894 const size_t rule_id = static_cast<size_t>(pos->value);895 const llama_grammar_element * subpos = rules[rule_id].data();896 do {897 // init new stack without the top (pos)898 llama_grammar_stack next_stack(curr_stack.begin(), curr_stack.end() - 1);899 if (!llama_grammar_is_end_of_sequence(pos + 1)) {900 // if this rule ref is followed by another element, add that to stack901 next_stack.push_back(pos + 1);902 }903 if (!llama_grammar_is_end_of_sequence(subpos)) {904 // if alternate is nonempty, add to stack905 next_stack.push_back(subpos);906 }907 todo.push_back(std::move(next_stack));908 while (!llama_grammar_is_end_of_sequence(subpos)) {909 // scan to end of alternate def910 subpos++;911 }912 if (subpos->type == LLAMA_GRETYPE_ALT) {913 // there's another alternate def of this rule to process914 subpos++;915 } else {916 break;917 }918 } while (true);919 break;920 }921 case LLAMA_GRETYPE_CHAR:922 case LLAMA_GRETYPE_CHAR_NOT:923 case LLAMA_GRETYPE_CHAR_ANY:924 case LLAMA_GRETYPE_TOKEN:925 case LLAMA_GRETYPE_TOKEN_NOT:926 if (std::find(new_stacks.begin(), new_stacks.end(), curr_stack) == new_stacks.end()) {927 // only add the stack if it's not a duplicate of one we already have928 new_stacks.emplace_back(curr_stack);929 }930 break;931 default:932 // end of alternate (LLAMA_GRETYPE_END, LLAMA_GRETYPE_ALT) or middle of char range933 // (LLAMA_GRETYPE_CHAR_ALT, LLAMA_GRETYPE_CHAR_RNG_UPPER); stack should never be left on934 // those935 GGML_ABORT("fatal error");936 }937 }938}939 940static llama_grammar_candidates llama_grammar_reject_candidates(941 const llama_grammar_rules & rules,942 const llama_grammar_stacks & stacks,943 const llama_grammar_candidates & candidates) {944 GGML_ASSERT(!stacks.empty()); // REVIEW945 946 if (candidates.empty()) {947 return {};948 }949 950 auto rejects = llama_grammar_reject_candidates_for_stack(rules, stacks.front(), candidates);951 952 for (size_t i = 1, size = stacks.size(); i < size; ++i) {953 rejects = llama_grammar_reject_candidates_for_stack(rules, stacks[i], rejects);954 }955 956 return rejects;957}958 959static bool llama_grammar_detect_left_recursion(960 const llama_grammar_rules & rules,961 size_t rule_index,962 std::vector<bool> * rules_visited,963 std::vector<bool> * rules_in_progress,964 std::vector<bool> * rules_may_be_empty) {965 if ((*rules_in_progress)[rule_index]) {966 return true;967 }968 969 (*rules_in_progress)[rule_index] = true;970 971 const llama_grammar_rule & rule = rules[rule_index];972 973 // First check if the rule might produce the empty string. This could be done combined with the second974 // step but it's more readable as two steps.975 bool at_rule_start = true;976 for (size_t i = 0; i < rule.size(); i++) {977 if (llama_grammar_is_end_of_sequence(&rule[i])) {978 if (at_rule_start) {979 (*rules_may_be_empty)[rule_index] = true;980 break;981 }982 at_rule_start = true;983 } else {984 at_rule_start = false;985 }986 }987 988 // Second, recurse into leftmost nonterminals (or next-leftmost as long as the previous nonterminal may989 // be empty)990 bool recurse_into_nonterminal = true;991 for (size_t i = 0; i < rule.size(); i++) {992 if (rule[i].type == LLAMA_GRETYPE_RULE_REF && recurse_into_nonterminal) {993 if (llama_grammar_detect_left_recursion(rules, (size_t)rule[i].value, rules_visited, rules_in_progress, rules_may_be_empty)) {994 return true;995 }996 if (!((*rules_may_be_empty)[(size_t)rule[i].value])) {997 recurse_into_nonterminal = false;998 }999 } else if (llama_grammar_is_end_of_sequence(&rule[i])) {1000 recurse_into_nonterminal = true;1001 } else {1002 recurse_into_nonterminal = false;1003 }1004 }1005 1006 (*rules_in_progress)[rule_index] = false;1007 (*rules_visited)[rule_index] = true;1008 1009 return false;1010}1011 1012const llama_grammar_rules & llama_grammar_get_rules(const struct llama_grammar * grammar) {1013 return grammar->rules;1014}1015 1016llama_grammar_stacks & llama_grammar_get_stacks(struct llama_grammar * grammar) {1017 return grammar->stacks;1018}1019 1020static void llama_grammar_accept_chr(1021 struct llama_grammar & grammar,1022 const llama_grammar_stack & stack,1023 uint32_t chr,1024 llama_grammar_stacks & new_stacks) {1025 if (stack.empty()) {1026 return;1027 }1028 1029 const llama_grammar_element * pos = stack.back();1030 1031 // ignore if this turns into a token1032 if (pos->type == LLAMA_GRETYPE_TOKEN || pos->type == LLAMA_GRETYPE_TOKEN_NOT) {1033 return;1034 }1035 1036 auto match = llama_grammar_match_char(pos, chr);1037 if (match.first) {1038 llama_grammar_stack new_stack(stack.begin(), stack.end() - 1);1039 if (!llama_grammar_is_end_of_sequence(match.second)) {1040 new_stack.push_back(match.second);1041 }1042 llama_grammar_advance_stack(grammar.rules, new_stack, new_stacks);1043 }1044}1045 1046void llama_grammar_accept(struct llama_grammar * grammar, uint32_t chr) {1047 llama_grammar_stacks stacks_new;1048 stacks_new.reserve(grammar->stacks.size());1049 1050 for (const auto & stack : grammar->stacks) {1051 llama_grammar_accept_chr(*grammar, stack, chr, stacks_new);1052 }1053 1054 grammar->stacks = std::move(stacks_new);1055}1056 1057llama_grammar_candidates llama_grammar_reject_candidates_for_stack(1058 const llama_grammar_rules & rules,1059 const llama_grammar_stack & stack,1060 const llama_grammar_candidates & candidates) {1061 1062 llama_grammar_candidates rejects;1063 rejects.reserve(candidates.size());1064 1065 if (stack.empty()) {1066 for (const auto & tok : candidates) {1067 if (*tok.code_points != 0 || tok.partial_utf8.n_remain != 0) {1068 rejects.push_back(tok);1069 }1070 }1071 return rejects;1072 }1073 1074 const llama_grammar_element * stack_pos = stack.back();1075 1076 // if the top of the stack is a token rule, then we only need to check the token id1077 if (stack_pos->type == LLAMA_GRETYPE_TOKEN || stack_pos->type == LLAMA_GRETYPE_TOKEN_NOT) {1078 for (const auto & tok : candidates) {1079 if (*tok.code_points == 0) {1080 // reached the end of a token consumed by char rules, reject iff it ended1081 // in a partial response1082 if (tok.partial_utf8.n_remain != 0) {1083 rejects.push_back(tok);1084 }1085 } else if (!llama_grammar_match_token(stack_pos, tok.id)) {1086 rejects.push_back(tok);1087 }1088 }1089 return rejects;1090 }1091 1092 llama_grammar_candidates next_candidates;1093 next_candidates.reserve(candidates.size());1094 1095 for (const auto & tok : candidates) {1096 if (*tok.code_points == 0) {1097 // reached end of full codepoints in token, reject iff it ended in a partial sequence1098 // that cannot satisfy this position in grammar1099 if (tok.partial_utf8.n_remain != 0 &&1100 !llama_grammar_match_partial_char(stack_pos, tok.partial_utf8)) {1101 rejects.push_back(tok);1102 }1103 } else if (llama_grammar_match_char(stack_pos, *tok.code_points).first) {1104 next_candidates.push_back({ tok.index, tok.code_points + 1, tok.partial_utf8, tok.id });1105 } else {1106 rejects.push_back(tok);1107 }1108 }1109 1110 const auto * stack_pos_after = llama_grammar_match_char(stack_pos, 0).second;1111 1112 // update top of stack to next element, if any1113 llama_grammar_stack stack_after(stack.begin(), stack.end() - 1);1114 if (!llama_grammar_is_end_of_sequence(stack_pos_after)) {1115 stack_after.push_back(stack_pos_after);1116 }1117 llama_grammar_stacks next_stacks;1118 llama_grammar_advance_stack(rules, stack_after, next_stacks);1119 1120 auto next_rejects = llama_grammar_reject_candidates(rules, next_stacks, next_candidates);1121 for (const auto & tok : next_rejects) {1122 rejects.push_back({ tok.index, tok.code_points - 1, tok.partial_utf8, tok.id });1123 }1124 1125 return rejects;1126}1127 1128////////////////////1129 1130struct llama_grammar * llama_grammar_init_impl(1131 const struct llama_vocab * vocab,1132 const llama_grammar_element ** rules,1133 size_t n_rules,1134 size_t start_rule_index) {1135 const llama_grammar_element * pos;1136 1137 // copy rule definitions into vectors1138 llama_grammar_rules vec_rules(n_rules);1139 for (size_t i = 0; i < n_rules; i++) {1140 for (pos = rules[i]; pos->type != LLAMA_GRETYPE_END; pos++) {1141 vec_rules[i].push_back(*pos);1142 }1143 vec_rules[i].push_back({LLAMA_GRETYPE_END, 0});1144 }1145 1146 // Validate that all rule references point to valid rules1147 for (size_t i = 0; i < n_rules; i++) {1148 for (const auto & elem : vec_rules[i]) {1149 if (elem.type == LLAMA_GRETYPE_RULE_REF) {1150 if (elem.value >= n_rules || vec_rules[elem.value].empty()) {1151 LLAMA_LOG_ERROR("invalid grammar: rule %zu references undefined rule %u\n", i, elem.value);1152 return nullptr;1153 }1154 }1155 }1156 }1157 1158 // Check for left recursion1159 std::vector<bool> rules_visited(n_rules);1160 std::vector<bool> rules_in_progress(n_rules);1161 std::vector<bool> rules_may_be_empty(n_rules);1162 for (size_t i = 0; i < n_rules; i++) {1163 if (rules_visited[i]) {1164 continue;1165 }1166 if (llama_grammar_detect_left_recursion(vec_rules, i, &rules_visited, &rules_in_progress, &rules_may_be_empty)) {1167 LLAMA_LOG_ERROR("unsupported grammar, left recursion detected for nonterminal at index %zu", i);1168 return nullptr;1169 }1170 }1171 1172 // loop over alternates of start rule to build initial stacks1173 llama_grammar_stacks stacks;1174 pos = vec_rules[start_rule_index].data();1175 do {1176 llama_grammar_stack stack;1177 if (!llama_grammar_is_end_of_sequence(pos)) {1178 // if alternate is nonempty, add to stack1179 stack.push_back(pos);1180 }1181 llama_grammar_advance_stack(vec_rules, stack, stacks);1182 while (!llama_grammar_is_end_of_sequence(pos)) {1183 // scan to end of alternate def1184 pos++;1185 }1186 if (pos->type == LLAMA_GRETYPE_ALT) {1187 // there's another alternate def of this rule to process1188 pos++;1189 } else {1190 break;1191 }1192 } while (true);1193 1194 // Important: vec_rules has to be moved here, not copied, because stacks contains1195 // pointers to elements of vec_rules. If vec_rules were copied into llama_grammar1196 // then the pointers would be invalidated when the local vec_rules goes out of scope.1197 return new llama_grammar {1198 vocab,1199 std::move(vec_rules),1200 std::move(stacks),