char-fork/llama.cpp

git clone https://git.t4t.associates/char-fork/llama.cpp

Aldehir Rojascommon : add support for multiple end sequences in the reasoning budget sampler (#25544)910196f6b

char/aliceai-t5-moe
brancheschar/aliceai-t5-moeall refs →
2.3 KiB73 linesraw
1#pragma once
2
3#include <cstdint>
4#include <map>
5#include <set>
6#include <string>
7#include <string_view>
8#include <vector>
9
10// Trie for matching multiple literals.
11// This is used in common_peg_until_parser and to build a GBNF exclusion grammar
12struct common_trie {
13    struct node {
14        std::map<uint32_t, size_t> children;  // Use uint32_t to store Unicode codepoints
15        int32_t pattern = -1;                 // index of the pattern ending at this node, -1 if none
16    };
17
18    std::vector<node> nodes;
19
20    common_trie() {
21        create_node(); // root node
22    }
23
24    common_trie(const std::vector<std::string> & words) : common_trie() {
25        for (const auto & w : words) {
26            insert(w);
27        }
28    }
29
30    enum match_result { NO_MATCH, PARTIAL_MATCH, COMPLETE_MATCH };
31
32    // Check if a delimiter starts at the given position
33    match_result check_at(std::string_view sv, size_t start_pos) const;
34
35    // Insert a word as a sequence of Unicode codepoints, returns its pattern index
36    int32_t insert(const std::string & word);
37
38    // Insert a raw symbol sequence, returns its pattern index (insertion order,
39    // duplicates keep the first index)
40    int32_t insert(const std::vector<uint32_t> & symbols);
41
42  private:
43    int32_t n_patterns = 0;
44
45    size_t create_node() {
46        size_t index = nodes.size();
47        nodes.emplace_back();
48        return index;
49    }
50};
51
52// Aho-Corasick automaton
53struct common_aho_corasick {
54    common_trie          t;
55    std::vector<size_t>  fail;     // failure links
56    std::vector<size_t>  order;    // states in BFS order
57    std::vector<int32_t> match;    // longest pattern ending at each state (directly or via a suffix link), -1 if none
58    std::set<uint32_t>   alphabet; // every character with a transition
59
60    common_aho_corasick(common_trie trie);
61
62    common_aho_corasick(const std::vector<std::string> & strings)
63        : common_aho_corasick(common_trie(strings)) {}
64
65    size_t num_states()          const { return t.nodes.size(); }
66    bool   is_terminal(size_t s) const { return match[s] >= 0; }
67
68    // index of the longest pattern ending at this state, -1 if none
69    int32_t match_pattern(size_t s) const { return match[s]; }
70
71    // follow failure links until a transition on `ch` exists.
72    size_t next(size_t state, uint32_t ch) const;
73};