{"action":"created","issue":{"url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/2450","repository_url":"https://api.github.com/repos/quicksilver/Quicksilver","labels_url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/2450/labels{/name}","comments_url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/2450/comments","events_url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/2450/events","html_url":"https://github.com/quicksilver/Quicksilver/issues/2450","id":343905744,"node_id":"MDU6SXNzdWUzNDM5MDU3NDQ=","number":2450,"title":"Three bugs in the QSSense scoring algorithm","user":{"login":"fwextensions","id":61631,"node_id":"MDQ6VXNlcjYxNjMx","avatar_url":"https://avatars2.githubusercontent.com/u/61631?v=4","gravatar_id":"","url":"https://api.github.com/users/fwextensions","html_url":"https://github.com/fwextensions","followers_url":"https://api.github.com/users/fwextensions/followers","following_url":"https://api.github.com/users/fwextensions/following{/other_user}","gists_url":"https://api.github.com/users/fwextensions/gists{/gist_id}","starred_url":"https://api.github.com/users/fwextensions/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fwextensions/subscriptions","organizations_url":"https://api.github.com/users/fwextensions/orgs","repos_url":"https://api.github.com/users/fwextensions/repos","events_url":"https://api.github.com/users/fwextensions/events{/privacy}","received_events_url":"https://api.github.com/users/fwextensions/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-07-24T06:47:11Z","updated_at":"2018-07-25T06:48:33Z","closed_at":null,"author_association":"NONE","body":"I've converted the Quicksilver scoring algorithm to JavaScript for various projects, and I believe I've found a few bugs in `QSSense.m`.  (I've only learned as much Objective-C as I needed to translate the algorithm, but I'm fairly sure these bugs are real.)\r\n\r\nSeveral years ago I started with this [old version](https://web.archive.org/web/20100901004019/http://docs.blacktree.com/quicksilver/development/string_ranking) of the code, which used `NSString`.  That worked well, though I didn't really have a way to verify that the JS version was returning the same scores as the Objective-C version.\r\n\r\nRecently, I found this repo and the `TestQSSense.m` file.  The scores in `testScoreSimpleNS()` from the [initial commit](https://github.com/quicksilver/Quicksilver/commit/0f2b4043fafbfc4b1263b7807504eb1b3baaeab8#diff-86c92ca75387e03f87312001fe115fb9) matched the scores from my JS version, but I couldn't get it to consistently match the new values, even when I added the `/2` to `score -= (matchedRange.location-strRange.location)/2;` (which wasn't in the original code above).  Some of the tests produced the same scores, but others didn't.  As far as I could tell by inspection, they all should've been the same, so it was very confusing.\r\n\r\nI finally just gave in and ran the ObjC code in Xcode to see what was going on.  After stepping through it (and cursing the absurd complexity of simply dumping strings to the console in Cocoa/ObjC), I believe there are three issues:\r\n\r\n1. The [line](https://github.com/quicksilver/Quicksilver/blob/551b8ce027bcd1bbaf150a91a5bc673149bf34a1/Quicksilver/Code-QuickStepFoundation/QSSense.m#L120) where the `/2` was added to increase the scores for longer strings throws away the fractional part of the result, since it's not dividing by `2.0`.  I suppose that could be intentional, like calling `floor()` on the result, but it seemed odd since `score` is a float.  Making the divisor a float brought more of the scores from my code into alignment with the test file.\r\n\r\n2. The [inline buffer](https://github.com/quicksilver/Quicksilver/blob/551b8ce027bcd1bbaf150a91a5bc673149bf34a1/Quicksilver/Code-QuickStepFoundation/QSSense.m#L62) is filled with only part of the string, rather than all of it.  This throws off the [lookup](https://github.com/quicksilver/Quicksilver/blob/551b8ce027bcd1bbaf150a91a5bc673149bf34a1/Quicksilver/Code-QuickStepFoundation/QSSense.m#L99) of the current and previous chars, since the lookup is done from `matchedRange.location`, which is in relation to the start of the entire string.  But `inlineBuffer` is filled from `strRange`, which moves to the right with each recursion.  So the check of whether the previous char was a word separator or the current char is uppercase is looking at the wrong letters, which then causes the score to be adjusted incorrectly.  For instance, an abbreviation matching the initial letters of words will have a lower score than it should, since the previous char in the buffer won't be a space, while it is in the original string.  Fixing this in the ObjC code brought the remainder of the scores into alignment.\r\n\r\n3. The mask of matching letters can contain more matches than there are letters in the abbreviation, which I mentioned recently in a comment on this [old PR](https://github.com/quicksilver/Quicksilver/pull/2342#discussion_r200827959) (someplace probably no one would see it).\r\n\r\n    Consider matching `\"test\"` against the string `\"t e s t tess!\"`.  The full abbreviation doesn't appear as a substring in the first loop, so it's reduced to `\"tes\"` and the function recurses.  That substring is found near the end of the string, and those indices (`[8, 9, 10]`, I think) get set in the mask.   Then it looks for the remaining `\"t\"` in the rest of the string, but only finds `\"s!\"`, so it has to start over and shrink the abbreviation again.  Eventually, it finds the individual letters separated by spaces and returns a score.  But the mask still contains those first hits that it gave up on.\r\n\r\n    My solution was to clear the mask just before the [`return 0;`](https://github.com/quicksilver/Quicksilver/blob/551b8ce027bcd1bbaf150a91a5bc673149bf34a1/Quicksilver/Code-QuickStepFoundation/QSSense.m#L127) at the end of the function.  I believe that's correct, as the 0 score means the algorithm will start over with a shorter abbreviation, and that shorter bit might hit in a different place, rendering the previous hits obsolete.  If the UI isn't underlining all those letters, then something else must be cleaning up the mask.  (I tried clamping it to the length of the abbreviation, but I don't think that gives the correct results in all cases.)\r\n\r\nIt looks like the inline buffer was added [9 years ago](https://github.com/quicksilver/Quicksilver/commit/516ba6f31a96e760e62f42531e070e5e4d741917), so maybe it doesn't make sense to fix the behavior now.  But it should be noticeable if you have two somewhat similar strings and an abbreviation that matches the start of words or uppercase letters in one, and random letters near the beginning of the other.  The first match might score lower than the second when it shouldn't.\r\n\r\nAnyway, I'm just happy to solve the mystery of why my code wasn't returning the same scores when it looked like it should.  My rough test version of `QSSense.m` that I was using to step through the code and print out debug info is in [this gist](https://gist.github.com/fwextensions/2bbdd453bc941dcfa36b06065c760980)."},"comment":{"url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/comments/407651856","html_url":"https://github.com/quicksilver/Quicksilver/issues/2450#issuecomment-407651856","issue_url":"https://api.github.com/repos/quicksilver/Quicksilver/issues/2450","id":407651856,"node_id":"MDEyOklzc3VlQ29tbWVudDQwNzY1MTg1Ng==","user":{"login":"fwextensions","id":61631,"node_id":"MDQ6VXNlcjYxNjMx","avatar_url":"https://avatars2.githubusercontent.com/u/61631?v=4","gravatar_id":"","url":"https://api.github.com/users/fwextensions","html_url":"https://github.com/fwextensions","followers_url":"https://api.github.com/users/fwextensions/followers","following_url":"https://api.github.com/users/fwextensions/following{/other_user}","gists_url":"https://api.github.com/users/fwextensions/gists{/gist_id}","starred_url":"https://api.github.com/users/fwextensions/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fwextensions/subscriptions","organizations_url":"https://api.github.com/users/fwextensions/orgs","repos_url":"https://api.github.com/users/fwextensions/repos","events_url":"https://api.github.com/users/fwextensions/events{/privacy}","received_events_url":"https://api.github.com/users/fwextensions/received_events","type":"User","site_admin":false},"created_at":"2018-07-25T06:48:33Z","updated_at":"2018-07-25T06:48:33Z","author_association":"NONE","body":"I also tried to replicate the results of the `testLongString()` test in [TestQSSense.m](https://github.com/quicksilver/Quicksilver/blob/551b8ce027bcd1bbaf150a91a5bc673149bf34a1/Quicksilver/Tests/Tests-QSFoundation/TestQSSense.m#L77) with my JS version.  Part of the reason the `indexes` set kept growing as `strRange.length` kept increasing was bug 3 above, but the other reason is that the index set is not cleared or reintialized between each test.  That means it ends up with every hit from all the calls to `QSScoreForAbbreviationWithRanges()`, whereas you'd normally call it with a fresh set each time.  "}}
{"actor":{"display_login":"fwextensions"}}