Open pintassilgo opened 1 month ago
Current fuzzy algo is described here https://wiki.freepascal.org/CudaText#Command_Palette what change do you suggest?
Current fuzzy: Searches char by char left to right without caring about how many chars are in between.
ararft
finds caret char left
.Current non fuzzy: Searches char by char left to right, but you need to type spaces to match non-consecutive chars.
car ha ft
finds caret char left
.carhaft
doesn't find caret char left
.Suggestion (VSCode behavior): Searches char by char left to right, but non-consecutive chars should only match when:
Match example: opfol
finds open current folder
. First it finds op
, next char in the match is e
and not the requested f
, but there's a word at right having f
as first letter so it matches. fol
still matches folder
, so we have the final result: opfol
matches open current folder
.
Another match example: qs
finds querySelector
. First it finds q
. Next char in the match is not the requested s
, but there's a upper case S
at the right, so it matches.
It's like searching people names by their initials. AT
should match Alexey Torgashin
and AlexeyTorgashin
.
Relevant: _
should also be treated as word separator, so Alexey_torgashin
should still match.
OK, todo.
Beta updated.
one thing. bug or not? 'basc' cannot find 'Bash script'. but should it? 'bas' matches 3 chars in "Bash" and last 'c' don't match (not at word begin).
Thank you. Could you please make it work in autocomplete? My main use for this feature is to use in JavaScript things such as qs
for querySelector
.
one thing. bug or not? 'basc' cannot find 'Bash script'. but should it?
Good question. Yes, I think it's a bug, it should find.
VSCode doesn't have this issue, see:
Current Cuda wouldn't be able to find this entry, it will stop at A Brea
, so the d
would be a miss.
Thank you. Could you please make it work in autocomplete? My main use for this feature is to use in JavaScript things such as
qs
forquerySelector
.
autocomplete is not the menu-like dlg. it uses plugin (python) fuzzy filter. it is LSP's code. maybe veksha can show me where is this code in LSP?
But what if user don't use LSP but uses Complete_from_text?
Then fuzzy is not supported at all. Complete_from_text don't support it.
I fear the same would be said of LSP, because as I know LSP doesn't autocomplete multiple words.
It would be a great improvement to support this type of fuzzy search, it's the one that can really speed up coding.
So that, for instance, I can type just qall
to get querySelectorAll
.
VSCode:
Sublime:
Kate:
By the way, all these three use full-fuzzy for these autocomplete. The VSCode's "smart fuzzy" is just for Command palette. But I guess this smart fuzzy should be used for autocomplete too.
I fear the same would be said of LSP, because as I know LSP doesn't autocomplete multiple words.
It would be a great improvement to support this type of fuzzy search, it's the one that can really speed up coding.
So that, for instance, I can type just
qall
to getquerySelectorAll
.
Post the new issue, as issue for LSP.
Solved. beta updated. I am not sure it is fully OK.
Current Cuda wouldn't be able to find this entry, it will stop at
A Brea
, so thed
would be a miss.
My last code cannot do it too. too many words I guess. but I already do loop 'from 0 to 255' per each string, it is slow already.
'Add data breakpoint at address' -- my code cannot find it by 'abread'. but it can by 'abreaad'. the 'at' word is messing with my code.
From what I'm seeing, the start of the string needs to be the start of a word for the fuzzy search to become active.
Example: pluman
works to find plugin: Addon Manager: Install...
. But ginman
doesn't work.
Surprisingly, VSCode behaves the same way, so if you think it's fine... But I feel it shouldn't be this way. The start of the string can be any part of a word. Only when you start connecting to a different word that there's the need to start from the first char...
But ginman doesn't work.
works after my new fix.
Last beta 73 works worse ('basc' is not found for 'bash script'), ignore it.
https://wiki.freepascal.org/CudaText#Command_Palette Could you , pls, improve the wiki text? post it here , I will submit to the wiki.
Suggestion for algorithm:
First, internally replace capital letters in items array by adding a white space at the left. So lexer: JavaScript
would become lexer: Java Script
(of course this change is not exposed, it's just for processing the search).
Then, first run a full-fuzzy search. Suppose find input is abcde
, so regex is a.*b.*c.*d.*e
. If there's no match, stop, there's no result.
If there are matches, you collect them and test each pair of chars:
ab|a.*\bb
. If it fails, there's no match. If it matches, go to next step.bc|b.*\bc
. If it fails, there's no match. If it matches, go to next step.cd|c.*\bd
. If it fails, there's no match. If it matches, go to next step.de|d.*\be
. If it fails, there's no match. If it matches, include the item in results list.So Cuda will run n
regex operations, where n
is the number of chars in words >1 length in find string.
Spaces in find input are treated as \s
and single-char-words can be simply copied to the regex.
Word boundary \b
should be improved to include underscore, so each .*\b
in the examples above would actually be .*(\b|_)
.
This code is efficient, shouldn't be slow for any size of find string.
Wait... this algorithm is not complete.
abc
would match ab sbc
, but it shouldn't. Need to think more.
a.b.c.d.e. If there's no match, stop, there's no result. If there are matches, you collect them and test each pair of chars:
Can I collect them all? regex engine allows to find 1st match for given regex, not all possible matches.
The solution can be capturing from regex result and carrying to next regex. I'll say in terms of JavaScript regex, don't know if Pascal is different.
Instead of ab|a.*\bb
, it would be something like (ab)|a.*(\bb)
, carrying the resultant groups to next regex.
Suppose the item about amount boat
. Running the regex above would return two groups: ab
(from "about") and \bb
(from "boat").
So in the next step Cuda would reuse these values in the regex between OR |
operator: ab|\bb
, appending the char from the next pair, which is c
, so abc|\bbc
.
So instead of bc|b.*\bc
that I said in previous comment, would be (abc|\bbc)|(?:ab|\bb).*(\bc)
.
By doing this, abc
wouldn't find ab sbc
, as expected.
But by doing this you're using different regex for each match. So it will be no longer n
regex, but multiplied by number of matches for the full-fuzzy search. Still shouldn't be slow, I guess. Short strings will have many matches, but n
is small. Longer string will have few matches for big n
. So total is never big at the point of being an issue.
Can I collect them all? regex engine allows to find 1st match for given regex, not all possible matches.
The full-fuzzy would be just to discard early items that don't match. It's not needed to find multiple matches for the same item, this step is just to avoid doing useless work in next steps by searching in items you're already sure won't match at the end.
Could you , pls, improve the wiki text?
I can try, but I'm not good with English, result might be bad. Also, I'm not sure how currently algorithm work. I know how it's supposed to be based on what I suggested from the start, but as you know it's not reliable.
For instance, selecaret
should find selection: cancel carets, but keep first caret/selection
but at least with the beta I have it doesn't work. It matches items such as selection: remove first caret
, but I don't know why it doesn't find the other item.
should find
selection: cancel carets, but keep first caret/selection
Yes, I see this issue too. 'cancel' word breaks finding of 'carets'. 'ca' too.
What we need here it the algo (in Pascal) which can find ALL combinations of fuzzy positions in a given text.
If we create this func, later steps are trivial! ie checking combinations for validity. valid combinations here are only 2.
now I reverted fuzzy code to old one (1.214.0). until we write this algo.
Note: example above: must find not 5 items, but much more! because 'c' can be from e.g. 'ca22' and 'a' can be from different next word e.g. '44ca'.
Algorithm that I believe would work.
Example of input string: "folfil". Example item: "open folder containing the current file".
.*
between each char, so f.*o.*l.*f.*i.*l
. Store only the matching strings.open[0],folder[0],containing[0],the[0],current[0],file[0]
.f
, so folder[1],containing[0],the[0],current[0],file[1]
.o
, so folder[2],containing[0],the[0],current[0],file[0]
.Continuing next steps of the given example til the end:
l
→ folder[3],containing[0],the[0],current[0],file[0]
f
→ file[1]
i
→ file[2]
l
→ file[3]
Another example:
Input: seleca
Item: select ca11 ca22 33ca33 44ca c55a55
Steps:
s
→ select[1],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
e
→ select[2],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
l
→ select[3],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
e
→ select[4],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
c
→ select[5],call[1],ca22[1],33ca33[0],44ca[0],c55a55[1]
a
→ call[2],ca22[2],33ca33[0],44ca[0],c55a55[0]
Slightly different example:
Input: selecca
Item: select ca11 ca22 33ca33 44ca c55a55
Steps:
s
→ select[1],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
e
→ select[2],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
l
→ select[3],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
e
→ select[4],call[0],ca22[0],33ca33[0],44ca[0],c55a55[0]
c
→ select[5],call[1],ca22[1],33ca33[0],44ca[0],c55a55[1]
c
→ call[1],ca22[1],33ca33[0],44ca[0],c55a55[1]
a
→ call[2],ca22[2],33ca33[0],44ca[0],c55a55[0]
Other example:
Input: selecaret
Item: selection: cancel carets, but keep first caret/selection
Steps:
s
→ selection[1]:,cancel[0],carets\,[0],but[0],keep[0],first[0],caret/[0],selection[1]
e
→ selection[2]:,cancel[0],carets\,[0],but[0],keep[0],first[0],caret/[0],selection[2]
l
→ selection[3]:,cancel[0],carets\,[0],but[0],keep[0],first[0],caret/[0],selection[3]
e
→ selection[4]:,cancel[0],carets\,[0],but[0],keep[0],first[0],caret/[0],selection[4]
c
→ selection[5]:,cancel[1],carets\,[1],but[0],keep[0],first[0],caret/[1],selection[5]
a
→ cancel[2],carets\,[2],but[0],keep[0],first[0],caret/[2],selection[0]
r
→ carets\,[3],but[0],keep[0],first[0],caret/[3],selection[0]
e
→ carets\,[4],but[0],keep[0],first[0],caret/[4],selection[0]
t
→ carets\,[5],but[0],keep[0],first[0],caret/[5],selection[0]
Non-match example:
Input: abc
Item: ab sbc
Steps:
a
→ ab[1],sbc[0]
b
→ ab[2],sbc[0]
c
→ list of words is empty, so it doesn't match.Maybe I will read your idea in details, but later, in mid-summer. no promise. I must convert the idea to pascal first. only @dinkumoil knows the pascal here, so he may help if he wants.
One thing I like in VSCode is the semi fuzzy search, both in Command palette and in autocomplete suggestions.
I mean, it's fuzzy only for the first letter of the word and for capital letters, and only if it follows left-to-right order.
Examples:
folfil
in Command palette suggestsopen FOLder containing the current FILe
.document.qs
in editor suggestsdocument.querySelector
in autocomplete popup.Current Cuda has
ui_listbox_fuzzy
which is even enabled by default but I disable it as it suggests items very much unrelated to what was typed.Edit: just correcting myself, this semi fuzzy is only used in VSCode for Command palette. For autocomplete in editor, the simple unrestricted fuzzy search is used.