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

Offline oBFusCATed

  • Developer
  • Lives here!
  • *****
  • Posts: 12829
    • Travis build status
Re: Code completion with partial matching
« Reply #15 on: January 20, 2014, 10:32:09 am »
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.
Have you tried to make the docstring API to be consisted of two steps/calls?
For example:
1. CCManager calls a plugin to to start gathering the data. No ui is shown to the user or empty UI is shown, so he can have a chance to cancel it.
2. The CC plugin has gathered the data and then calls CCManager to show the UI or fill the UI.

1 and 2 happen in the main thread. This way you leave the task of threading to the plugin.
(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 #16 on: January 20, 2014, 02:33:55 pm »
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.)

There are almost certainly going to be similar problems, so don't hardcode. How about doing Acronym matching as a separate, alternative calculation that only gets used if it would create a higher score?

example: user types wxs, candidates (and their acronyms) are

wxString -> wS
wxStringHelper -> wSH
wantsXtraStr ->wxS
wxstring0 -> no acronym

You compute a score for wxString (3 matches at the start), a score for wS (no matches) and take the higher score => 3 prefix matches (I'm abstracting from the exact numeric score you might give this)
You compute a score for wxStringHelper (3 matches at the start), a score for wSH (no matches) and take the higher score => 3 prefix matches
You compute a score for wantsXtraStr (3 partial matches), a score for wxS (3 prefix matches) and take the higher score => 3 prefix matches
You compute a score for wxstring (3 matches at the start), there's no acronym so ignore => 3 prefix matches

So in this case all 3 would have an equal score, so they should appear alphabetically (you could also slightly penalize acronym match, because it isn't as intuitive as a straight prefix match).
« Last Edit: January 20, 2014, 02:50:21 pm by dmoore »

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #17 on: January 20, 2014, 11:12:12 pm »
Have you tried to make the docstring API to be consisted of two steps/calls?
For example:
1. CCManager calls a plugin to to start gathering the data. No ui is shown to the user or empty UI is shown, so he can have a chance to cancel it.
2. The CC plugin has gathered the data and then calls CCManager to show the UI or fill the UI.

1 and 2 happen in the main thread. This way you leave the task of threading to the plugin.
Although that would work, I would be hesitant to use it as I have so far designed the interface such that individual CC plugins do not need to know that CCManager exists, nor to talk with it.  They only have to return data when requested.

[...] How about doing Acronym matching as a separate, alternative calculation that only gets used if it would create a higher score?
Hmm, I will experimenting with that...

Offline oBFusCATed

  • Developer
  • Lives here!
  • *****
  • Posts: 12829
    • Travis build status
Re: Code completion with partial matching
« Reply #18 on: January 21, 2014, 12:41:24 am »
Although that would work, I would be hesitant to use it as I have so far designed the interface such that individual CC plugins do not need to know that CCManager exists, nor to talk with it.  They only have to return data when requested.
OK you can make a custom event cbEVT_CC_DOC_STRING_READY or something like that...
(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 Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #19 on: January 21, 2014, 12:45:20 am »
OK you can make a custom event cbEVT_CC_DOC_STRING_READY or something like that...
I think that would be a reasonable solution.  (I was quite literally just typing that same thought, when I saw you had posted.)

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #20 on: March 20, 2014, 08:38:00 pm »
Any progress with this feature? Would like to see a finished version merged into trunk too.

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #21 on: March 20, 2014, 11:38:54 pm »
Any progress with this feature? Would like to see a finished version merged into trunk too.
Unfortunately in the busyness of my life, I have not yet had time to work further on it.  Hopefully I will soon though...

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #22 on: April 11, 2014, 08:49:21 pm »
I have cleaned up this patch somewhat (attached).  No significant functional changes, but it should at least apply to the current trunk.
(Improvements to stability/usability are in progress...)

Offline pieman

  • Multiple posting newcomer
  • *
  • Posts: 31
Re: Code completion with partial matching
« Reply #23 on: April 11, 2014, 09:10:40 pm »
Settings > Editor > Code Completion

"Display info when hovering mouse over a token in the editor"

Is it possible to have this option, excluding the fuck-with-whatever-you're-typing feature?

(Edit: yes it is, but could you please implement it)

Also, make the tooltip instant. Draw --it-- (because I hope you don't intantiate some object every time you need to render a different tip string) at the cursor's position immediately. I'm capable of moving my cursor if it's obstructive. If you keep it how they stick to a fixed position obtained when the tip becomes visible (which is stupid), then obstruction becomes more frustrating. ;)
« Last Edit: April 11, 2014, 09:17:29 pm by pieman »
I like pie.

Offline oBFusCATed

  • Developer
  • Lives here!
  • *****
  • Posts: 12829
    • Travis build status
Re: Code completion with partial matching
« Reply #24 on: April 11, 2014, 09:53:24 pm »
pieman:
You're getting too aggressive lately. Mind your words please (don't use the f** one)! Also don't hijack topics. This topics has nothing to do with the things you've suggested.

If you want something implemented now or tomorrow start coding, else try to be polite and convince the current devs that your proposal are worth our time!
(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 Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #25 on: April 12, 2014, 02:52:32 am »
(Improvements to stability/usability are in progress...)
Updated patch (attached) is fully functional, and stable (as far as I can tell) edit: discovered a crash to work out.

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. ???
Also included in this patch is a potential solution to this.  CCManager records each time you select (hit enter/double click to complete and insert the result) an item that took "too long" to come up in the autocomplete listing.  These entries (stored in a small buffer, to allow older, no longer used, entries to expire) are given a score bonus, so they float to the top faster the next time the same query comes up.

After a bit more testing, and adding the appropriate configuration menu, this feature should be ready to commit.
« Last Edit: April 12, 2014, 03:31:43 am by Alpha »

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #26 on: April 12, 2014, 04:30:54 am »
[...] stable (as far as I can tell) edit: discovered a crash to work out.
Probably working now ::)... (patch attached)

Offline dmoore

  • Developer
  • Lives here!
  • *****
  • Posts: 1576
Re: Code completion with partial matching
« Reply #27 on: April 12, 2014, 05:11:07 am »
While i can see some utility in this approach, to be honest I would prefer something more deterministic. What is the issue with implementing the algorithm I proposed above?

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #28 on: April 12, 2014, 05:58:18 am »
What is the issue with implementing the algorithm I proposed above?
Mostly it was that this "adaption" algorithm was much faster for me to get to a working state.  (To implement your algorithm, I would need to spend some trial-error time, testing different constants.)

Although determinism is, in general, preferential (to me as well), in using this completion algorithm, it bothers me each time something takes longer than with plain alphabetical.  I doubt I could come up with any deterministic algorithm to sufficiently satisfy myself.
That said, there is an easy point in the code to disable adaption, so it can be a configurable option.

Offline Alpha

  • Developer
  • Lives here!
  • *****
  • Posts: 1513
Re: Code completion with partial matching
« Reply #29 on: April 14, 2014, 01:50:19 am »
What is the issue with implementing the algorithm I proposed above?
[...]  To implement your algorithm, I would need to spend some trial-error time, testing different constants.
This seems to work reasonably... (I will need to do more testing though.)
Code: [Select]
    static int CalcPrefixValue(wxString query, wxString token)
    {
        if (query.IsEmpty() || token.IsEmpty())
            return 0;

        int val = 0;
        int shift = sizeof(val) * 8 - 2;

        if (!token.Lower().StartsWith(query.Lower()))
            val += (1 << shift);
        --shift;

        if (!token.StartsWith(query))
            val += (1 << shift);
        --shift;

        int idx = token.Lower().Find(query.Lower());
        if (idx == wxNOT_FOUND)
            val += (1 << shift);
        --shift;
        if (idx > 6)
            val += (1 << shift);
        --shift;
        if (idx > 3)
            val += (1 << shift);
        --shift;

        idx = token.Find(query);
        if (idx == wxNOT_FOUND)
            val += (1 << shift);
        --shift;
        if (idx > 6)
            val += (1 << shift);
        --shift;
        if (idx > 3)
            val += (1 << shift);
        --shift;

        val += (1 << shift);

        val *= std::max<int>(1, 4 - query.Length());

        return val; // lower is better
    }