Author Topic: Code completion with partial matching  (Read 48384 times)

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Code completion with partial matching
« on: January 17, 2014, 11:12:24 pm »
See: https://github.com/Valloric/YouCompleteMe/blob/master/README.md

Quote
A critical thing to notice is that the completion filtering is NOT based on the input being a string prefix of the completion (but that works too). The input needs to be a subsequence match of a completion. This is a fancy way of saying that any input characters need to be present in a completion string in the order in which they appear in the input. So abc is a subsequence of xaybgc, but not of xbyxaxxc. After the filter, a complicated sorting system ranks the completion strings so that the most relevant ones rise to the top of the menu (so you usually need to press TAB just once).

The animated GIF has a nice little demonstration. Cool feature IMO.

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #1 on: January 18, 2014, 03:13:45 am »
Enjoy attached hack ;) .  (To cc_interface branch.)

(Edit: Filtering, but no fancy sorting.)
« Last Edit: January 18, 2014, 03:20:16 am by Alpha »

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #2 on: January 18, 2014, 05:05:52 pm »
Nice work! It works nicely with the python cc plugin too!

How much of an issue is the sorting? Does the popup list allow you to control the sort order? The most important thing is that (1) exact prefix matches come first (2) exact infix or suffix matches next and, maybe, (3) other matches by count of neighboring letters that match. Giving priority for the acronym of CamelCase symbols would be a nice touch too. (e.g. return AbstractBaseClass with high priority for abc, and maybe getNextCharacter would be high on the list for gnc)

PS: Seems to be small bug with placement of doc string window. Sometimes it places on left when there clearly isn't room for the whole window on that side. (edited)
« Last Edit: January 18, 2014, 08:15:18 pm by dmoore »

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #3 on: January 18, 2014, 07:46:51 pm »
How much of an issue is the sorting? [...]
It is not really an issue; only that a sort function would need to be written.
Code: close to line 580
m_FilteredTokens.erase(remove_if(m_FilteredTokens.begin(), m_FilteredTokens.end(), Matcher), m_FilteredTokens.end());
std::sort(m_FilteredTokens.begin(), m_FilteredTokens.end(), MyFancySort); // add sorting here
That line (plus the definition of the "MyFancySort" - or whatever name is chosen) should be all that is necessary.

PS: Seems to be small bug with placement of doc string window. Sometimes it places on left when there clearly isn't room for the whole window.
Well, that was supposed to be a feature.  Does it act unexpectedly?

Offline oBFusCATed

  • Developer
  • Lives here!
  • *****
  • Posts: 13413
    • Travis build status
Re: Code completion with partial matching
« Reply #4 on: January 18, 2014, 07:57:27 pm »
It is not really an issue; only that a sort function would need to be written.
Probably it would be better to use some ranking function, converting the string to some integer and then using normal integer sorting.
Probably YouCompleteMe dev won't mind if you use theirs way of sorting.... :)
(most of the time I ignore long posts)
[strangers don't send me private messages, I'll ignore them; post a topic in the forum, but first read the rules!]

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #5 on: January 18, 2014, 08:12:31 pm »
PS: Seems to be small bug with placement of doc string window. Sometimes it places on left when there clearly isn't room for the whole window.
Well, that was supposed to be a feature.  Does it act unexpectedly?

It gets cut off when being displayed on the left side. Maybe the same would have happened on the right side too, but I didn't think so (if that's the case, then maybe the window just needs to be resized). I was using a 1080p display on a dual monitor setup. The 1080p monitor is on the left, the other monitor is something less than 1080p.


Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #6 on: January 18, 2014, 08:17:34 pm »
It is not really an issue; only that a sort function would need to be written.
Probably it would be better to use some ranking function, converting the string to some integer and then using normal integer sorting.
Probably YouCompleteMe dev won't mind if you use theirs way of sorting.... :)

Agree. After all we're using their way of matching. (I am going to steal this for my photo manager's tag completions too!)

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #7 on: January 18, 2014, 08:27:18 pm »
This looks to be the relevant code:

https://github.com/Valloric/YouCompleteMe/blob/master/cpp/ycm/Result.cpp#L141

But I think it would be simpler (and almost certainly faster!) to just compute an integer priority for each item as oBFus mentioned.
« Last Edit: January 18, 2014, 08:29:05 pm by dmoore »

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #8 on: January 19, 2014, 02:46:52 am »
Code: see attached
++hack;
« Last Edit: January 19, 2014, 02:54:16 am by Alpha »

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #9 on: January 19, 2014, 05:12:36 am »
PS: Seems to be small bug with placement of doc string window. Sometimes it places on left when there clearly isn't room for the whole window.
Well, that was supposed to be a feature.  Does it act unexpectedly?
It gets cut off when being displayed on the left side. Maybe the same would have happened on the right side too, but I didn't think so (if that's the case, then maybe the window just needs to be resized). I was using a 1080p display on a dual monitor setup. The 1080p monitor is on the left, the other monitor is something less than 1080p.
Confirmed.  (And also confirmed that it is the fault of this hack interacting with another component of CCManager.)

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #10 on: January 19, 2014, 07:13:08 am »
Code: see attached
++hack;

a very nice hack indeed. Works beautifully.

PS: Seems to be small bug with placement of doc string window. Sometimes it places on left when there clearly isn't room for the whole window.
Well, that was supposed to be a feature.  Does it act unexpectedly?
It gets cut off when being displayed on the left side. Maybe the same would have happened on the right side too, but I didn't think so (if that's the case, then maybe the window just needs to be resized). I was using a 1080p display on a dual monitor setup. The 1080p monitor is on the left, the other monitor is something less than 1080p.
Confirmed.  (And also confirmed that it is the fault of this hack interacting with another component of CCManager.)

hopefully a simple fix.

One more issue: in python cc, I think I need to be able to do async docstring calls. otherwise the gui can freeze for quite a while.

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #11 on: January 19, 2014, 10:01:31 pm »
a very nice hack indeed. Works beautifully.
Until you try to complete wxString.  With my clang plugin, it does not even show up until I have typed the full name, and even then, it is the fifth item. ???



One more issue: in python cc, I think I need to be able to do async docstring calls. otherwise the gui can freeze for quite a while.
I have been attempting to work on that for a while (with cbThreadPool), however, I apparently do not understand threading nearly as well as I had thought; each of my tries immediately crashed while updating the GUI from a cbEVT_THREADTASK_ALLDONE handler.  Looks like more reading for me.

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #12 on: January 19, 2014, 10:20:01 pm »
Nice catch re wxString, just need to sort alphabetically for equal priority items?

Re threads, need to be careful about passing data that is constructed in the worker thread being deleted before it gets handled on the main thread. There are some posts about certain events being unsafe by (i think) ollydbg.

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #13 on: January 20, 2014, 06:43:43 am »
Nice catch re wxString, just need to sort alphabetically for equal priority items?
The problem is, CalcValue() (which is tries to nearly replicate/quantify the algorithm YCM designed) gives wxString a worse value because its word boundary string is only "ws" (whereas wxSTRING_REVERSE_ITERATOR for example is "wsri", more closely matching the input).  (Items with equal priority *should* already be in alphabetical order, assuming my implementation works the way I think it does.)
Unfortunately, re-balancing the weighting algorithm would probably cause it to lose the benefit it gives in most other cases.  (I am tempted to hardcode a small score boost for wxString, because it is rather common in wxWidgets based code... but that could get even uglier if other similar problem tokens show up.)

Re threads, need to be careful about passing data that is constructed in the worker thread being deleted before it gets handled on the main thread. There are some posts about certain events being unsafe by (i think) ollydbg.
Thanks, I will look for those.

Offline oBFusCATed

  • Developer
  • Lives here!
  • *****
  • Posts: 13413
    • Travis build status
Re: Code completion with partial matching
« Reply #14 on: January 20, 2014, 09:36:50 am »
Unfortunately, re-balancing the weighting algorithm would probably cause it to lose the benefit it gives in most other cases.  (I am tempted to hardcode a small score boost for wxString, because it is rather common in wxWidgets based code... but that could get even uglier if other similar problem tokens show up.)
No hardcoding, please, it is ugly and unprofessional:)
(most of the time I ignore long posts)
[strangers don't send me private messages, I'll ignore them; post a topic in the forum, but first read the rules!]