kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

ranked_match.cc (11008B)


      1 #include "ranked_match.hh"
      2 
      3 #include "flags.hh"
      4 #include "unit_tests.hh"
      5 #include "utf8_iterator.hh"
      6 #include "optional.hh"
      7 #include "ranges.hh"
      8 #include "word_splitter.hh"
      9 
     10 #include <algorithm>
     11 
     12 namespace Kakoune
     13 {
     14 
     15 UsedLetters used_letters(StringView str)
     16 {
     17     UsedLetters res = 0;
     18     for (auto c : str)
     19     {
     20         if (c >= 'a' and c <= 'z')
     21             res |= 1uLL << (c - 'a');
     22         else if (c >= 'A' and c <= 'Z')
     23             res |= 1uLL << (c - 'A' + 26);
     24         else if (c == '_')
     25             res |= 1uLL << 53;
     26         else if (c == '-')
     27             res |= 1uLL << 54;
     28         else
     29             res |= 1uLL << 63;
     30     }
     31     return res;
     32 }
     33 
     34 bool matches(UsedLetters query, UsedLetters letters)
     35 {
     36     return (query & letters) == query;
     37 }
     38 
     39 using Utf8It = utf8::iterator<const char*>;
     40 
     41 static int count_word_boundaries_match(StringView candidate, StringView query)
     42 {
     43     int count = 0;
     44     Utf8It query_it{query.begin(), query};
     45     Codepoint prev = 0;
     46     for (Utf8It it{candidate.begin(), candidate}; it != candidate.end(); ++it)
     47     {
     48         const Codepoint c = *it;
     49         const bool is_word_boundary = prev == 0 or
     50                                       (not is_word(prev, {}) and is_word(c, {})) or
     51                                       (is_lower(prev) and is_upper(c));
     52         prev = c;
     53 
     54         if (not is_word_boundary)
     55             continue;
     56 
     57         const Codepoint lc = to_lower(c);
     58         for (auto qit = query_it; qit != query.end(); ++qit)
     59         {
     60             const Codepoint qc = *qit;
     61             if (qc == (is_lower(qc) ? lc  : c))
     62             {
     63                 ++count;
     64                 query_it = qit+1;
     65                 break;
     66             }
     67         }
     68         if (query_it == query.end())
     69             break;
     70     }
     71     return count;
     72 }
     73 
     74 static int count_full_word_match(StringView candidate, StringView query)
     75 {
     76     int count = 0;
     77     WordSplitter query_words{query, {}};
     78     WordSplitter candidate_words{candidate, {}};
     79     for (auto query_word : query_words)
     80     {
     81         for (auto word : candidate_words)
     82         {
     83             if (word == query_word)
     84             {
     85                 ++count;
     86                 break;
     87             }
     88         }
     89     }
     90     return count;
     91 }
     92 
     93 static bool smartcase_eq(Codepoint candidate, Codepoint query)
     94 {
     95     return query == (is_lower(query) ? to_lower(candidate) : candidate);
     96 }
     97 
     98 struct SubseqRes
     99 {
    100     int max_index;
    101     bool single_word;
    102 };
    103 
    104 static Optional<SubseqRes> subsequence_match_smart_case(StringView str, StringView subseq)
    105 {
    106     bool single_word = true;
    107     int max_index = -1;
    108     auto it = str.begin();
    109     int index = 0;
    110     for (auto subseq_it = subseq.begin(); subseq_it != subseq.end();)
    111     {
    112         if (it == str.end())
    113             return {};
    114         const Codepoint c = utf8::read_codepoint(subseq_it, subseq.end());
    115         if (single_word and not is_word(c))
    116             single_word = false;
    117         while (true)
    118         {
    119             auto str_c = utf8::read_codepoint(it, str.end());
    120             if (smartcase_eq(str_c, c))
    121                 break;
    122 
    123             if (max_index != -1 and single_word and not is_word(str_c))
    124                 single_word = false;
    125 
    126             ++index;
    127             if (it == str.end())
    128                 return {};
    129         }
    130         max_index = index++;
    131     }
    132     return SubseqRes{max_index, single_word};
    133 }
    134 
    135 template<typename TestFunc>
    136 RankedMatch::RankedMatch(StringView candidate, StringView query, TestFunc func)
    137 {
    138     if (query.length() > candidate.length())
    139         return;
    140 
    141     if (query.empty())
    142     {
    143         m_candidate = candidate;
    144         m_matches = true;
    145         return;
    146     }
    147 
    148     if (not func())
    149         return;
    150 
    151     auto res = subsequence_match_smart_case(candidate, query);
    152     if (not res)
    153         return;
    154 
    155     m_candidate = candidate;
    156     m_matches = true;
    157     m_max_index = res->max_index;
    158 
    159     if (res->single_word)
    160         m_flags |= Flags::SingleWord;
    161 
    162     if (auto it = find(candidate | reverse() | skip(1), '/').base();
    163         it == candidate.begin() or subsequence_match_smart_case({it, candidate.end()}, query))
    164     {
    165         m_flags |= Flags::BaseName;
    166         if ((candidate.end() - it) >= query.length() and
    167             std::equal(Utf8It{query.begin(), query}, Utf8It{query.end(), query}, Utf8It{it, candidate},
    168                        [](Codepoint query, Codepoint candidate) { return smartcase_eq(candidate, query); }))
    169             m_flags |= Flags::Prefix;
    170     }
    171 
    172     auto it = std::search(candidate.begin(), candidate.end(),
    173                           query.begin(), query.end(), smartcase_eq);
    174     if (it != candidate.end())
    175     {
    176         m_flags |= Flags::Contiguous;
    177         if (std::all_of(Utf8It{query.begin(), query}, Utf8It{query.end(), query}, [](auto cp) { return is_word(cp); }))
    178             m_flags |= Flags::SingleWord;
    179         if (it == candidate.begin())
    180         {
    181             m_flags |= Flags::Prefix;
    182             if (query.length() == candidate.length())
    183             {
    184                 m_flags |= Flags::SmartFullMatch;
    185                 if (candidate == query)
    186                     m_flags |= Flags::FullMatch;
    187             }
    188         }
    189     }
    190 
    191     m_full_word_match_count = count_full_word_match(candidate, query);
    192     m_word_boundary_match_count = count_word_boundaries_match(candidate, query);
    193     if (m_word_boundary_match_count == query.length())
    194         m_flags |= Flags::OnlyWordBoundary;
    195 }
    196 
    197 RankedMatch::RankedMatch(StringView candidate, UsedLetters candidate_letters,
    198                          StringView query, UsedLetters query_letters)
    199     : RankedMatch{candidate, query, [&] {
    200         return matches(to_lower(query_letters), to_lower(candidate_letters)) and
    201                matches(query_letters & upper_mask, candidate_letters & upper_mask);
    202     }} {}
    203 
    204 
    205 RankedMatch::RankedMatch(StringView candidate, StringView query)
    206     : RankedMatch{candidate, query, [] { return true; }}
    207 {
    208 }
    209 
    210 static bool is_word_boundary(Codepoint prev, Codepoint c)
    211 {
    212     return (is_word(prev, {})) != is_word(c, {}) or
    213            (is_lower(prev) != is_lower(c));
    214 }
    215 
    216 bool RankedMatch::operator<(const RankedMatch& other) const
    217 {
    218     kak_assert((bool)*this and (bool)other);
    219 
    220     const auto diff = m_flags ^ other.m_flags;
    221     // flags are different, use their ordering to return the first match
    222     if (diff != Flags::None)
    223         return (int)(m_flags & diff) > (int)(other.m_flags & diff);
    224 
    225     // If we are SingleWord, we dont want to take word boundaries from other
    226     // words into account.
    227     if (not (m_flags & (Flags::Prefix | Flags::SingleWord)) and
    228         m_word_boundary_match_count != other.m_word_boundary_match_count)
    229         return m_word_boundary_match_count > other.m_word_boundary_match_count;
    230 
    231     if (m_full_word_match_count != other.m_full_word_match_count)
    232         return m_full_word_match_count > other.m_full_word_match_count;
    233 
    234     if (m_max_index != other.m_max_index)
    235         return m_max_index < other.m_max_index;
    236 
    237     if (m_input_sequence_number != other.m_input_sequence_number)
    238         return m_input_sequence_number < other.m_input_sequence_number;
    239 
    240     // Reorder codepoints to improve matching behaviour
    241     auto order = [](Codepoint cp) { return cp == '/' ? 0 : cp; };
    242 
    243     auto it1 = m_candidate.begin(), it2 = other.m_candidate.begin();
    244     const auto begin1 = it1, begin2 = it2;
    245     const auto end1 = m_candidate.end(), end2 = other.m_candidate.end();
    246     auto last1 = it1, last2 = it2;
    247     while (true)
    248     {
    249         // find next mismatch
    250         while (it1 != end1 and it2 != end2 and *it1 == *it2)
    251             ++it1, ++it2;
    252 
    253         if (it1 == end1 or it2 == end2)
    254             return it1 == end1 and it2 != end2;
    255 
    256         // compare codepoints
    257         it1 = utf8::character_start(it1, last1);
    258         it2 = utf8::character_start(it2, last2);
    259         const auto itsave1 = it1, itsave2 = it2;
    260         const auto cp1 = utf8::read_codepoint(it1, end1);
    261         const auto cp2 = utf8::read_codepoint(it2, end2);
    262         if (cp1 != cp2)
    263         {
    264             const auto cplast1 = utf8::prev_codepoint(itsave1, begin1);
    265             const auto cplast2 = utf8::prev_codepoint(itsave2, begin2);
    266             const bool is_wb1 = is_word_boundary(cplast1, cp1);
    267             const bool is_wb2 = is_word_boundary(cplast2, cp2);
    268             if (is_wb1 != is_wb2)
    269                 return is_wb1;
    270 
    271             const bool low1 = is_lower(cp1);
    272             const bool low2 = is_lower(cp2);
    273             if (low1 != low2)
    274                 return low1;
    275 
    276             return order(cp1) < order(cp2);
    277         }
    278         last1 = it1; last2 = it2;
    279     }
    280 }
    281 
    282 UnitTest test_ranked_match{[] {
    283     auto preferred = [](StringView query, StringView better, StringView worse) {
    284         return RankedMatch{better, query} < RankedMatch{worse, query};
    285     };
    286 
    287     kak_assert(count_word_boundaries_match("run_all_tests", "rat") == 3);
    288     kak_assert(count_word_boundaries_match("run_all_tests", "at") == 2);
    289     kak_assert(count_word_boundaries_match("countWordBoundariesMatch", "wm") == 2);
    290     kak_assert(count_word_boundaries_match("countWordBoundariesMatch", "cobm") == 3);
    291     kak_assert(count_word_boundaries_match("countWordBoundariesMatch", "cWBM") == 4);
    292     kak_assert(preferred("so", "source", "source_data"));
    293     kak_assert(not preferred("so", "source_data", "source"));
    294     kak_assert(not preferred("so", "source", "source"));
    295     kak_assert(preferred("wo", "single/word", "multiw/ord"));
    296     kak_assert(preferred("foobar", "foo/bar/foobar", "foo/bar/baz"));
    297     kak_assert(preferred("db", "delete-buffer", "debug"));
    298     kak_assert(preferred("ct", "create_task", "constructor"));
    299     kak_assert(preferred("cla", "class", "class::attr"));
    300     kak_assert(preferred("meta", "meta/", "meta-a/"));
    301     kak_assert(preferred("find", "find(1p)", "findfs(8)"));
    302     kak_assert(preferred("fin", "find(1p)", "findfs(8)"));
    303     kak_assert(preferred("sys_find", "sys_find(1p)", "sys_findfs(8)"));
    304     kak_assert(preferred("", "init", "__init__"));
    305     kak_assert(preferred("ini", "init", "__init__"));
    306     kak_assert(preferred("", "a", "b"));
    307     kak_assert(preferred("expresins", "expresions", "expressionism's"));
    308     kak_assert(preferred("foo_b", "foo/bar/foo_bar.baz", "test/test_foo_bar.baz"));
    309     kak_assert(preferred("foo_b", "bar/bar_qux/foo_bar.baz", "foo/test_foo_bar.baz"));
    310     kak_assert(preferred("foo_bar", "bar/foo_bar.baz", "foo_bar/qux.baz"));
    311     kak_assert(preferred("fb", "foo_bar/", "foo.bar"));
    312     kak_assert(preferred("foo_bar", "test_foo_bar", "foo_test_bar"));
    313     kak_assert(preferred("rm.cc", "src/ranked_match.cc", "test/README.asciidoc"));
    314     kak_assert(preferred("luaremote", "src/script/LuaRemote.cpp", "tests/TestLuaRemote.cpp"));
    315     kak_assert(preferred("lang/haystack/needle.c", "git.evilcorp.com/language/haystack/aaa/needle.c", "git.evilcorp.com/aaa/ng/wrong-haystack/needle.cpp"));
    316     kak_assert(preferred("evilcorp-lint/bar.go", "scripts/evilcorp-lint/foo/bar.go", "src/evilcorp-client/foo/bar.go"));
    317 }};
    318 
    319 UnitTest test_used_letters{[]()
    320 {
    321     kak_assert(used_letters("abcd") == to_lower(used_letters("abcdABCD")));
    322 }};
    323 
    324 }