[CLOSED] Fix for #2068: better QuickOpen heuristics #2346
Comments
|
Almost done reviewing -- will wrap up later tonight. |
|
Overall on the heuristic: definitely feels much improved! I'm still feeling like camelcase matches come out a little too low, though I won't say it necessarily needs to be addressed right now -- I think I probably use camelcase search queries with Quick Open more heavily than most users. Here are a few example cases:
I have a few half-formed ideas about how we could fix cases like that. E.g. if two consecutive specials are matched, also give credit for (some fraction of) a contiguous match for the whole range of chars in between. Or, slightly penalize contiguous matches that span a special without starting on one. Anyway, unless you think there's something very easy we could do here, I'm happy to just spin off a bug and then deal with it later :-) |
|
One final thought -- the match heuristic code is getting pretty big. Should it go into its own module? E.g. utils/StringMatch.js. (If so I'd suggest doing the move as its own commit, so that other changes resulting from the code review are easier to see in a diff). Ok, whew! Done reviewing. |
|
The stringMatch code is a bit over 500 lines (out of a 1360 line file). It doesn't seem too unwieldy to me. But, it's possible that the string matching could be useful for things that are not "QuickOpen" (I'm thinking of a command line :) and it may be cleaner to have it separate from that angle. I agree that moving it should be a separate commit. |
|
I've moved StringMatch into its own file. Note that this does break the PHP QuickOpen extension at least: https://github.com/aonic/brackets-QuickOpenPHP/blob/master/main.js I think a good practice in a case like this would be to re-export stringMatch from QuickOpen with a deprecation warning and remove it for good in a couple of sprints. But, we may be early enough in the project now that we can just ask the QuickOpenPHP author to change the extension. What do you think? |
|
Done re-reviewing -- getting close now! Thanks for all the thorough responses and refactorings! |
|
Actually one more thing. I happened to hit an odd bug yesterday that still repros with your latest (if I patch it so Go to Definition works, that is):
It seems like any subset of a query with results should include all those same results. Or at least, I can't think of any reason why "hadledo" wouldn't match "_handleDocumentSelectionChange"... If this turns out to be tricky we can spin off a separate bug to unblock the pull request though -- whatever the issue is here, I'm not seeing it often... |
|
It looks to me like your "hadledo" example above is another example of the need for backtracking. I'll take a look into that in the morning. |
|
The latest commit fixes the "hadledo" problem and also makes "sru" prefer SpecRunnerUtils to SpecRunner.js. nj mentioned forward tracking as an alternative to backtracking, with the possibility of trying multiple paths and locating the one with the best score. I think the new algorithm works well for a large majority of cases, and I believe that it's likely to process many search strings on a single pass through without backtracking. I have spotted one case where testing a couple of paths could make things better (searching for "quickopen" ends up matching QuickOpenCSS/main.js because it searches the last segment first), but it would require a more significant rejiggering to change the way the last segment preference is handled. I did actually consider it when adding the backtracking, but opted to leave that part as is. |
|
Still trying to wrap my head around deadBranches and backtrackTo a little better. Will be back online later tonight to continue reviewing... |
|
I wonder if I can come up with some ASCII art to make them clearer. The key is that the normal pattern prefers the special characters, but in so doing it skips over possible matches. So, I used backtrackTo to keep taking us back one special character at a time (while pulling off every other character that may have matched in between), and then we take it forward consecutively from there. We didn't get a match in the specials, but maybe there's one lurking between those last two specials we checked. But, a problem remains: what happens if we match a consecutive character, then switch back to hitting specials and then hit the end of the string again without a complete match? That's where deadBranches comes in. At the time we set backtrackTo, we also have positively identified that the part of the query after queryCounter does not appear after that special character. If we find ourselves heading down that path again, we need to stop looking for specials because we're not going to find what we're looking for. Without deadBranches, it would keep trying to match up the specials. I did try a simpler approach where it just keeps track of the highest special it should scan to, but it turned out that that approach would actually not do specials scanning when it should. This is akin to dynamic programming, if not exactly that. stringMatch is not exactly a generalized routine... we have some idea how it's used, and I tried to match the algorithm to that. |
|
|
|
Ok, I think it's all starting to make sense to me :-) Here are a few things I think we might want to capture in the docs in some way:
Hopefully that is all correct! If not lmk... |
|
Also needs a (hopefully trivial) merge with master before this is mergeable |
|
Yes, that is how it all works. It's not very important, but there is one minor adjustment. You say:
could be, because those special characters would be traversed, but it does not happen. It doesn't happen because the specials are traversed first and only after that fails does it resort to matching the normal characters. So, as it progresses forward character-by-character it will compare a special if it hits one, but it won't be a match because it had already compared it. Otherwise, everything you said is spot on. Maybe I'll just add your points in directly, because I think that someone else's interpretation of that code (plus the comments that I already have there) can only help someone new who's approaching it for the first time. And, yes, the merge is trivial. I did that merge when I created the branch for the performance improvement yesterday. |
|
Hmm, ok I just ran across another case where it seems to fail to find a match: open StringMatch.js and search for "_computerangesa" (or any longer substring of _computeRangesAndScore) -- it won't show any results. If I take out the "s" ("_computeRangeAndScore") then it matches. |
|
Also one case of funny scoring: if I search for "jsutil," it ranks JSLintUtils.js above JSUtils.js. It seems like both the longer contiguous match and the preference for shorter strings should work in JSUtils' favor, so I'm not sure what's happening... I tried turning on DEBUG_SCORES, but I'm only seeing the total number in the Quick Open results list -- not the breakdown of individual scoring attributes. Is there more to it than just changing the initializer from false to true? |
|
I'll look into the "_computerangesa" case and the scoring. Scoring is easy to tweak and will never be 100% perfect all the time. The current algorithm counts uppercase letters after lowercase ones as special (the camelCase pattern), so JSLintUtils.js has an extra special than JSUtils.js. I'll see if there's something that makes sense to tweak. When DEBUG_SCORES is on, hover over the score to see the individual parts (it's a tooltip). |
|
I haven't been following the algorithm in detail, but I wonder if we should treat all uppercase letters as "special", not just ones after lowercase letters, precisely because of cases like "JSUtils", where conceptually the "U" really is the start of a "word", and arguably the "S" is too (because it's part of an acronymish abbreviation standing in for a word). I think most contiguous strings of uppercase letters in identifier names tend to be abbreviations like this. |
|
So, the fix here actually made things a bit simpler. When we determine that past point X in the string, the last Y parts of the query can't find a match, we just keep track of that. We won't go hunting beyond that point for a match for that part of the query, and if we need to backtrack we'll make sure that we rewind to the previous special before point X. deadBranches is all of the bookkeeping we need. |
|
The code changes all look good. I'm just going to run on this branch for a while longer to make sure I don't hit any other cases that seem off -- and if not, I think we're good to merge! |
|
Awesome. Thanks again for digging into this one and sticking with it. When this merges, I think I'll redo my pull request for the performance improvement. That code is really quite straightforward and I think we should get it in soon, even if not sprint 19. |
|
Alright, played with it a bunch more all all still seems well -- time to merge! |
Wednesday Jan 02, 2013 at 17:10 GMT
Originally opened as adobe/brackets#2462
The new heuristics don't relate so much to longest substring as they do to trying to find contiguous matches around characters in "special" positions in the string.
dangoor included the following code: https://github.com/adobe/brackets/pull/2462/commits
The text was updated successfully, but these errors were encountered: