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 }