Skip to content

Commit 883cd18

Browse files
dyphiredyphire
authored
feat: fuzzy search and highlighting based on fzy algorithm (#1148)
1 parent 42660e8 commit 883cd18

File tree

6 files changed

+479
-29
lines changed

6 files changed

+479
-29
lines changed

‎src/uosc.conf

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -152,7 +152,7 @@ text_border=1.2
152152
# Border radius of buttons, menus, and all other rectangles
153153
border_radius=4
154154
# A comma delimited list of color overrides in RGB HEX format. Defaults:
155-
# foreground=ffffff,foreground_text=000000,background=000000,background_text=ffffff,curtain=111111,success=a5e075,error=ff616e
155+
# foreground=ffffff,foreground_text=000000,background=000000,background_text=ffffff,curtain=111111,success=a5e075,error=ff616e,match=69c5ff
156156
color=
157157
# A comma delimited list of opacity overrides for various UI element backgrounds and shapes.
158158
# This does not affect any text, which is always rendered fully opaque. Defaults:

‎src/uosc/elements/Menu.lua

Lines changed: 82 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -836,35 +836,99 @@ end
836836
---@return MenuStackChild[]
837837
function search_items(items, query, recursive, prefix)
838838
local result = {}
839+
local haystacks = {}
840+
local flat_items = {}
839841
local concat = table.concat
842+
local romanization = need_romanization()
843+
840844
for _, item in ipairs(items) do
841845
if item.selectable ~= false then
842846
local prefixed_title = prefix and prefix .. ' / ' .. (item.title or '') or item.title
847+
haystacks[#haystacks + 1] = item.title
848+
flat_items[#flat_items + 1] = item
849+
843850
if item.items and recursive then
844851
itable_append(result, search_items(item.items, query, recursive, prefixed_title))
845-
else
846-
local title = item.title and item.title:lower()
847-
local hint = item.hint and item.hint:lower()
848-
local initials_title = title and concat(initials(title)) --[[@as string]]
849-
local romanization = need_romanization()
850-
if romanization then
851-
ligature_conv_title = title and char_conv(title, true)
852-
initials_conv_title = title and concat(initials(char_conv(title, false)))
852+
end
853+
end
854+
end
855+
856+
local seen = {}
857+
858+
local fuzzy = fzy.filter(query, haystacks, false)
859+
for _, match in ipairs(fuzzy) do
860+
local idx, positions, score = match[1], match[2], match[3]
861+
local matched_title = haystacks[idx]
862+
local item = flat_items[idx]
863+
local prefixed_title = prefix and prefix .. ' / ' .. (item.title or '') or item.title
864+
865+
if item.selectable ~= false and not (item.items and recursive) and not seen[item] then
866+
local bold = item.bold
867+
local font_color = item.active and fgt or bgt
868+
local ass_safe_title = highlight_match(matched_title, positions, font_color, bold) or nil
869+
local new_item = table_assign({}, item)
870+
new_item.title = prefixed_title
871+
new_item.ass_safe_title = prefix and prefix .. ' / ' .. (ass_safe_title or '') or ass_safe_title
872+
new_item.score = score
873+
result[#result + 1] = new_item
874+
seen[item] = true
875+
end
876+
end
877+
878+
for _, item in ipairs(items) do
879+
local title = item.title and item.title:lower()
880+
local hint = item.hint and item.hint:lower()
881+
local bold = item.bold
882+
local font_color = item.active and fgt or bgt
883+
local ass_safe_title = nil
884+
local prefixed_title = prefix and prefix .. ' / ' .. (item.title or '') or item.title
885+
if item.selectable ~= false and not (item.items and recursive) and not seen[item] then
886+
local score = 0
887+
local match = false
888+
889+
if title and romanization then
890+
local ligature_conv_title, ligature_roman = char_conv(title, true)
891+
local initials_arr_conv, initials_roman = char_conv(title, false)
892+
local initials_conv_title = concat(initials(initials_arr_conv))
893+
if ligature_conv_title:find(query, 1, true) then
894+
match = true
895+
score = 1000
896+
local pos = get_roman_match_positions(title, query, "ligature", ligature_roman)
897+
if pos then
898+
ass_safe_title = highlight_match(item.title, pos, font_color, bold)
899+
end
900+
elseif initials_conv_title:find(query, 1, true) then
901+
match = true
902+
score = 900
903+
local pos = get_roman_match_positions(title, query, "initial", initials_roman)
904+
if pos then
905+
ass_safe_title = highlight_match(item.title, pos, font_color, bold)
906+
end
853907
end
854-
if title and title:find(query, 1, true) or
855-
title and romanization and ligature_conv_title:find(query, 1, true) or
856-
hint and hint:find(query, 1, true) or
857-
title and initials_title:find(query, 1, true) or
858-
title and romanization and initials_conv_title:find(query, 1, true) or
859-
hint and concat(initials(hint)):find(query, 1, true) then
860-
item = table_assign({}, item)
861-
item.title = prefixed_title
862-
item.ass_safe_title = nil
863-
result[#result + 1] = item
908+
end
909+
910+
if hint and not match then
911+
if hint:find(query, 1, true) then
912+
match = true
913+
score = 100
914+
elseif concat(initials(hint)):find(query, 1, true) then
915+
match = true
916+
score = 90
864917
end
865918
end
919+
920+
if match then
921+
local new_item = table_assign({}, item)
922+
new_item.title = prefixed_title
923+
new_item.ass_safe_title = prefix and prefix .. ' / ' .. (ass_safe_title or '') or ass_safe_title
924+
new_item.score = score
925+
result[#result + 1] = new_item
926+
end
866927
end
867928
end
929+
930+
table.sort(result, function(a, b) return a.score > b.score end)
931+
868932
return result
869933
end
870934

‎src/uosc/lib/char_conv.lua

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -27,23 +27,22 @@ function char_conv(chars, use_ligature, has_separator)
2727
local separator = has_separator or ' '
2828
local length = 0
2929
local char_conv, sp, cache = {}, {}, {}
30+
local roman_list = {}
3031
local chars_length = utf8_length(chars)
3132
local concat = table.concat
3233
for _, char in utf8_iter(chars) do
34+
local match = romanization[char] or char
35+
roman_list[#roman_list + 1] = match
3336
if use_ligature then
34-
if #char == 1 then
35-
char_conv[#char_conv + 1] = char
36-
else
37-
char_conv[#char_conv + 1] = romanization[char] or char
38-
end
37+
char_conv[#char_conv + 1] = match
3938
else
4039
length = length + 1
4140
if #char <= 2 then
4241
if (char ~= ' ' and length ~= chars_length) then
43-
cache[#cache + 1] = romanization[char] or char
42+
cache[#cache + 1] = match
4443
elseif (char == ' ' or length == chars_length) then
4544
if length == chars_length then
46-
cache[#cache + 1] = romanization[char] or char
45+
cache[#cache + 1] = match
4746
end
4847
sp[#sp + 1] = concat(cache)
4948
itable_clear(cache)
@@ -53,14 +52,14 @@ function char_conv(chars, use_ligature, has_separator)
5352
sp[#sp + 1] = concat(cache)
5453
itable_clear(cache)
5554
end
56-
sp[#sp + 1] = romanization[char] or char
55+
sp[#sp + 1] = match
5756
end
5857
end
5958
end
6059
if use_ligature then
61-
return concat(char_conv)
60+
return concat(char_conv), roman_list
6261
else
63-
return concat(sp, separator)
62+
return concat(sp, separator), roman_list
6463
end
6564
end
6665

0 commit comments

Comments
 (0)