Felipe97/llama-cpp-compiled

1#include "trie.h"2 3#include "unicode.h"4 5#include <deque>6 7common_trie::match_result common_trie::check_at(std::string_view sv, size_t start_pos) const {8    size_t current = 0; // Start at root9    size_t pos = start_pos;10 11    // LOG_DBG("%s: checking at pos %zu, sv='%s'\n", __func__, start_pos, std::string(sv).c_str());12 13    while (pos < sv.size()) {14        auto result = common_parse_utf8_codepoint(sv, pos);15        if (result.status != utf8_parse_result::SUCCESS) {16            break;17        }18 19        auto it = nodes[current].children.find(result.codepoint);20        if (it == nodes[current].children.end()) {21            // Can't continue matching22            return match_result{match_result::NO_MATCH};23        }24 25        current = it->second;26        pos += result.bytes_consumed;27 28        // Check if we've matched a complete word29        if (nodes[current].pattern >= 0) {30            return match_result{match_result::COMPLETE_MATCH};31        }32    }33 34    // Reached end of input while still in the trie (not at root)35    if (current != 0) {36        // We're in the middle of a potential match37        return match_result{match_result::PARTIAL_MATCH};38    }39 40    // Reached end at root (no match)41    return match_result{match_result::NO_MATCH};42}43 44int32_t common_trie::insert(const std::string & word) {45    std::vector<uint32_t> symbols;46    size_t pos = 0;47    while (pos < word.length()) {48        auto result = common_parse_utf8_codepoint(word, pos);49        if (result.status != utf8_parse_result::SUCCESS) {50            break;51        }52 53        symbols.push_back(result.codepoint);54        pos += result.bytes_consumed;55    }56    return insert(symbols);57}58 59int32_t common_trie::insert(const std::vector<uint32_t> & symbols) {60    size_t current = 0;61    for (uint32_t ch : symbols) {62        auto it = nodes[current].children.find(ch);63        if (it == nodes[current].children.end()) {64            size_t child = create_node();65            nodes[current].children[ch] = child;66            current = child;67        } else {68            current = it->second;69        }70    }71    if (nodes[current].pattern < 0) {72        nodes[current].pattern = n_patterns++;73    }74    return nodes[current].pattern;75}76 77common_aho_corasick::common_aho_corasick(common_trie trie) : t(std::move(trie)) {78    const auto & nodes = t.nodes;79    const size_t n = nodes.size();80 81    fail.assign(n, 0);82    order.reserve(n);83 84    std::deque<size_t> queue{ 0 };85    while (!queue.empty()) {86        size_t u = queue.front();87        queue.pop_front();88        order.push_back(u);89        for (const auto & [ch, v] : nodes[u].children) {90            if (u != 0) {91                size_t f = fail[u];92                while (f && nodes[f].children.find(ch) == nodes[f].children.end()) {93                    f = fail[f];94                }95                auto it = nodes[f].children.find(ch);96                fail[v] = (it != nodes[f].children.end() && it->second != v) ? it->second : 0;97            }98            queue.push_back(v);99        }100    }101 102    // fail[u] points to a strictly shorter suffix, so the first pattern found on103    // the fail chain (including u itself) is the longest pattern ending at u104    match.assign(n, -1);105    for (size_t u : order) {106        match[u] = nodes[u].pattern >= 0 ? nodes[u].pattern : (u != 0 ? match[fail[u]] : -1);107    }108 109    for (const auto & node : nodes) {110        for (const auto & [ch, v] : node.children) {111            alphabet.insert(ch);112        }113    }114}115 116size_t common_aho_corasick::next(size_t state, uint32_t ch) const {117    const auto & nodes = t.nodes;118    while (state && nodes[state].children.find(ch) == nodes[state].children.end()) {119        state = fail[state];120    }121    auto it = nodes[state].children.find(ch);122    return it != nodes[state].children.end() ? it->second : 0;123}124