Goto anything quick panel list backend bits [$30]

[quarnster]

I've not been thinking about how to implement this at all so it's pretty open. This issue number deals just with the backend management of the quick panel list, not actually filling the list in with content which are dealt with in other issues marked with the goto label.

• Each list item is required to have a title, but can also have optional metadata.
• It should be possible to execute a fuzzy search in the list to get matches
• There should be a event callback when the the current item is changed (think arrow up/arrow down)
• There should be an event callback when an item is selected (think enter)
• There should be an event callback when the panel is dismissed (think esc)

Rather than someone jumping straight in and implementing it with a pull request, I think it'd be wise to brainstorm a bit to draft up the interfaces involved with the different modes possible for the goto anything functionality.

Did you help close this issue? Go claim the $30 bounty on Bountysource.

[FichteFoll]

Also useful: An event callback when the text input has changed with the ability to provide a different list (in case of # and @ goto anything) or to prevent showing the list (:), which could just be an empty list. Maybe also manipulating the actual "fuzzy search value" since everything before @ or # should not matter.

[ryanwersal]

@FichteFoll If I remember correctly, doesn't Sublime Text use the stuff preceding the @/# to filter down the results by searching that specific file? I seem to recall something like file.cpp@functionName working quite well.

[adzenith]

@ryanwersal Yeah, it lets you do that. When you type file.cpp it previews the file you asked for, so I believe @functionName will always search the currently displayed file.

[FichteFoll]

This is correct.

[quarnster]

I had completely forgotten about the file.cpp@/#/:xxx functionality, but you are of course correct. That requires a dynamic data model so that not everything is pulled into the list up front.

I imagine also that the fuzzy filtering is just about poking the underlying data model without other bits being aware of that that's what's going on, or worded differently everything else just knows that the model changed and queries it for the new info.

For the file.cpp@/#/:xxx use case I imagine something like the following data models once a generic data model interface is defined:

• One for providing the @-data (Goto anything: function list #125)
• One for providing the #-data (Goto anything: symbol list [$10] #126)
• One for providing the file list (Goto anything: list files #123)
• One for doing fuzzy filtering
• One "über" model that parses the file.cpp@/#/:xxx input and uses the other ones as appropriate

[jacobgardner]

In terms of the fuzzy searching, I've got a go implementation of textmate's fuzzy searching algorithm on my fork. I'll make a pull-request when it's ready.

https://github.com/jacobgardner/lime/blob/master/backend/util/fuzzy.go

I wrote a python implementation a while back based off of textmate 2's code and compared the output to that and it appears to be identical. Seeing as this is my first go program. It's probably awful go, but it works.

If you glance at the code here's the relevant stuff that'll be returned from rank_word(input, word):

input is whatever the user typed into the quick bar. Word is typically a file path.

The returned value is a score bound between 0 and 1. Where values closer to 1 indicate that the inputted word more closely resembles the path.

Typical usage would be running rank_word against all the paths in the project folders/open in views, sorting them descending by their returned rank and that gives you the same functionality as in sublime_text/textmate.

The matrix returned gives you the letters that should be bolded in word to show the user where the matches occurred at.

Anyway, yes. I'll try to get that pull request done by the end of the week and then start looking at what else I can do.

[quarnster]

Is this a port over from Textmate's source code? Textmate is GPL so I would not be able to accept this code if that is the case.

Or is it a known published algorithm? If so, which one? Please provide links to references.

Once we know if the code can be accepted or not:

in_word should be strings.ContainsRune.
is_uppercase should be unicode.IsUpper.
is_letter should be unicode.IsLetter.
is_digit should be unicode.IsDigit.

Please insert brief comments about what the various for loops in rank_word do.
Please format the code by running go fmt.

How does the algorithm compare to the naive approach of using regexp.FindStringSubmatchIndex where the regular expression is created by inserting .*? between characters in the input string? Please create two benchmark functions comparing the two.

And finally (for now ;)), please create a test to ensure it is functioning as expected.

[jacobgardner]

Whoops. Yes it's based off of GPLed code. Nice catch. I'll still probably make the changes you suggested to get me used to go patterns.

I'll look into writing another fuzzy rank algorithm though. I'll check to see what's out there, but Ialso have a few ideas of my own.

Sent from my HTC

----- Reply message -----
From: "Fredrik Ehnbom" [email protected]
To: "limetext/lime" [email protected]
Cc: "Jacob Gardner" [email protected]
Subject: [lime] Goto anything quick panel list backend bits (#122)
Date: Thu, Nov 21, 2013 2:45 AM

Is this a port over from Textmate's source code? Textmate is GPL so I would not be able to accept this code if that is the case.

Or is it a known published algorithm? If so, which one? Please provide links to references.

Once we know if the code can be accepted or not:

in_word should be strings.ContainsRune.

is_uppercase should be unicode.IsUpper.

is_letter should be unicode.IsLetter.

is_digit should be unicode.IsDigit.

Please insert brief comments about what the various for loops in rank_word do.

Please format the code by running go fmt.

How does the algorithm compare to the naive approach of using regexp.FindStringSubmatchIndex where the regular expression is created by inserting .*? between characters in the input string? Please create two benchmark functions comparing the two.

And finally (for now ;)), please create a test to ensure it is functioning as expected.

—
Reply to this email directly or view it on GitHub.

[quarnster]

https://github.com/mattn/gof might be useful

[derekparker]

I wrote a fuzzy search implementation based on a trie data structure that could potentially be used towards this: https://github.com/Dparker1990/trie.

[quarnster]

I prototyped some generic array code that could help here. And #123, #124, #125, #126

[derekparker]

@quarnster regarding this issue - have you taken a look at https://github.com/derekparker/trie? Each list item could be stored in the trie data structure, and searched with efficient prefix or fuzzy searching. The data structure also allows for arbitrary metadata to be stored alongside each list item, and the title could be the key.

The structure has efficient storage and search properties, and population of the structure is efficient as well. Usage of this package would adhere to the above requirements, and would easily satisfy a callback API - imagine performing a fuzzy search with trie.FuzzySearch as the user is typing, and then once the selected callback happens when a user determins their selection, that entire string of their selection could be passed to trie.Find if the metadata was needed.

[quarnster]

@derekparker Haven't thought about this issue in quite a while but looks like your package would indeed be useful. Thanks for the pointer

[derekparker]

@quarnster cool, I can try and work on a patch for this during the week. I've been absent from this project for a while busy with some other things but I'd like to get back into helping out, I really like this project.

[quarnster]

@derekparker Glad to hear it, all help is highly appreciated. BTW haven't had a chance to look at delve yet but looking forward to it when it works on OSX and I'm in need of some Go debugging in the future :)

[quarnster]

@derekparker Semi-related: delve would be an ideal use case in figuring out where the standard Sublime Text plugin API lacks with regards to creating custom UI elements and how we can improve upon that. But we should probably have that discussion in a separate issue number.

[derekparker]

@quarnster cool I'd love to discuss that more. Delve should be available on OS X soon!

[zoli]

Moved to limetext/backend#105.