Goto anything quick panel list backend bits [$30]

quarnster commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

@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 commented 10 years ago

@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 commented 10 years ago

This is correct.

quarnster commented 10 years ago

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 (#125)
One for providing the #-data (#126)
One for providing the file list (#123)
One for doing fuzzy filtering
One "über" model that parses the file.cpp@/#/:xxx input and uses the other ones as appropriate

jacobgardner commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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" notifications@github.com To: "limetext/lime" lime@noreply.github.com Cc: "Jacob Gardner" jacob.v.gardner@gmail.com 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 commented 10 years ago

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

derekparker commented 10 years ago

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 commented 10 years ago

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

derekparker commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

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

zoli commented 8 years ago

Moved to https://github.com/limetext/backend/issues/105.

limetext / lime

Goto anything quick panel list backend bits [$30] #122