Sort code autocompletion options by "likeness score" based on input

[Mickeon]

Added in the String class, the algorithm assigns a likeness value between 0.0 and 1.0 to the String calling it, relying on the base String parameter.

If either Strings are empty it returns 0.0. If base is not a subsequence of the String it returns 0.0.

The algorithm aims to give higher scores to shorter Strings that contain the base's characters closer to the beginning of the String, and closer between each other. For example:

String base = "pos"

String("pos").assign_score(base);                        // 1.0
String("post").assign_score(base);                       // 0.938
String("position").assign_score(base);                   // 0.844
String("current_animation_position").assign_score(base); // 0.260
String("potato").assign_score(base);                     // 0.0

Showcase

BEFORE	AFTER
A short example of the options moving as values closer to the base are prioritised:	And a mock-up of how this works, made in GDScript.

I may add more mock-ups at a later time. But I'm only one person, not writing on Godot 4 full-time yet. As such...

I encourage people to please try this out by pulling this branch!

Final notes:

• This PR moves the autocompletion sorting all the way after all options have been filtered out, instead of before. I feel like there's no point sorting values if some are going to be discarded. Please do tell if there is something I'm missing.
• Known issues:
  • This PR no longer highlights the characters that are part of the search. I do not know how to accomplish that right now.
• I do need proper names for the internal function, do suggest, please!
• If necessary I can open a proposal, but this is not stuff most users are particularly "savvy" about.
• Special thanks to @fire and @KoBeWi for helping me using the custom iterator.
• ~See https://github.com/godotengine/godot/pull/65655#issuecomment-1242988659~

[Mickeon]

This compiles locally but it doesn't in the checks...

[RedMser]

This compiles locally but it doesn't in the checks...

I assume because you're including an editor header file from outside of the editor folder. So when making a tools=no build, the editor folder is not included in the compile and the build fails because of that.

[Mickeon]

I assume because you're including an editor header file from outside of the editor folder. So when making a tools=no build, the editor folder is not included in the compile and the build fails because of that.

Ah, oh boy. This one is going to be... interesting to solve. Oh no...

[Mickeon]

Hastily attempting to address it so that this can be tested as soon as possible.

[RedMser]

I'm very glad you're tackling this long standing issue. But this current solution still does not seem ideal and should probably combine multiple methods of assigning score.

For example, in a script extending Node, autocompletion for tree looks like this:

It's great that it finds matches that use the same letters in the same order. But the algorithm should definitely prioritize a full substring match (tree is found as-is in get_tree), as well as further prioritizing begins_with matches (so the tree_* signals should be first).

[Zireael07]

@RedMser how autocompletion should work has been bikeshedded to death or close to it. Some favor 'full matches' as you do, some favor what @Mickeon did here and personally I think it needs a follow-up PR and an option switch

[Mickeon]

It's great that it finds matches that use the same letters in the same order. But the algorithm should definitely prioritize a full substring match (tree is found as-is in get_tree), as well as further prioritizing begins_with matches (so the tree_* signals should be first).

It would somewhat do as you say, if the implementation of https://github.com/godotengine/godot/pull/59633 were to be completely replaced with this method. But instead, I attempted combining the two.

Currently, and before, the order is kind of like this. [Node2D, Node properties], then [Node2D, Node methods], then [Node2D, Node constants] ... So each option is sorted by score only in between the same kind.

What I could experiment with, is something along the lines of... "If the score is high enough, it ignores the kind of option and brings it all the way up the list", But honestly, right now I'm very fearful because some checks just do not compile! Honestly the screenshot you showed me is personally odd already, I think I broke something while attempting to make this compile.

[RedMser]

and personally I think it needs a follow-up PR and an option switch

So each option is sorted by score only in between the same kind and the same class

This indeed is probably the kind of thing that should introduce an editor setting or two (group by inheritance level, group by field/method/constant, etc.). Tbh I had no idea how it currently worked, so maybe my suggestion does not work well and would need a greater rewrite which is a lot to ask for. 😅 Your changes are already a large improvement since the list shows more plausible matches.

right now I'm very fearful because some checks just do not compile

@Mickeon I'm not really well-versed with C++ but you could try removing the _FORCE_INLINE_ for the comparator function and/or putting the function body directly into the header file. Seems like every comparator in the code base is implemented a bit differently in that regard.

[Mickeon]

@RedMser I have updated the calculation. There's a large penalty the further away the base's characters are from each other: The score actually goes below 0.0, which shouldn't be the case (I don't want it to be the case), but it does improve the order of results considerably. At some point later I will experiment with outright discarding any option whose score is below a certain threshold (basically humanly impossible to discern how the base is inside).

[Mickeon]

It used to work this way previously

similarity()is not the algorithm used here, I wrote the function for this PR myself.

[EricEzaM]

It appears Rider also uses some combination. When there is no search 'parameter', it is in alphabetical but with members of the local class first (bold), then everything else (also in alphabetical order)

However once you start typing, the "what is local?" rule takes precedence but can be overridden by the "similarity" of the options? i.e. local to cursor position, but worse similarity is positioned lower...?

I'm not saying we have to do it the same way but I find that rider almost always shows me what I want, and makes sense.

[Mickeon]

I'm not saying we have to do it the same way but I find that rider almost always shows me what I want, and makes sense.

No, no, yeah. This is the idea. It's what would satisfy most users. It's what I was aspiring to achieve with this PR.

[EricEzaM]

I think my original PR #59633 was too complex for its own good. I think we only need two "Locations" for code completion purposes: Local, and Other. Local is all local variables and all methods, properties, etc declared on the class you are inside of. Using this simplification helps with the sorting. That PR also did lose a bit of precision when it came to searching too - your addition here makes it a much better, more well rounded system.

Additionally, I think the scoring system you have is working pretty damn well! I think it can be merged with sorting on the completion kind (i.e. function, property, variable, etc) to have a code completion algorithm that has the important stuff first, but if something 'less important' matches your query really well, it is pushed to the top. Easiest way I thought to do this was just to have a threshold of the score. If score of either item is > threshold, return early, sorting only based on the score. Otherwise, sort on kind, then score, then alphanumeric. Here is what I came up with - this is a diff between this PR and my changes.

https://github.com/Mickeon/godot/compare/editor-autocompletion-sort-by-score...EricEzaM:65655?expand=1 The main part: https://github.com/Mickeon/godot/compare/editor-autocompletion-sort-by-score...EricEzaM:65655?expand=1#diff-6b3879fe8504d721cd9c247489803d697d29ebc128a7288eb620013941b3af65R3063

Setting the threshold to around 0.25 seemed ok. You can ignore the editor setting stuff in the PR - that was just so it was easy to quickly test different threshholds.

In the video you can see the stuff that matches well is high. However, you can also see that lower 'ranked' kinds (like classes) are put above functions (higher ranked) if they match much better (in this case TextServer > bytes_to_var_with_objects). The threshold can be tweaked to give a better result also.

https://user-images.githubusercontent.com/41730826/191033139-2b453202-acb4-42c0-9f3e-db5e181c1cba.mp4

[EricEzaM]

How is this progressing? This is a big QOL improvement for the script editor. I think this should be in one of the 4.0 betas, ideally.

[Mickeon]

This is a big QOL improvement for the script editor. I think this should be in one of the 4.0 betas, ideally.

I'll be working on it in the upcoming days, in that case! My only concern is that PR review meetings are constantly getting rescheduled and the focus is fully on fixing bugs, so there's never a good moment to bring attention to it to the core developers

[EricEzaM]

Eh, don't let me push you one way or another, if there are other things you want to work on go for them. I was just following up as I think this is a good improvement for the editor.

[EricEzaM]

I took a look at this again.

This PR no longer highlights the characters that are part of the search. I do not know how to accomplish that right now.

I can see in the diff that most of the code that performed this functionality was deleted (code_edit.cpp:2929 onwards). That is why it stopped working. After having a quick chat to @Paulb23, it seems something got lost in translation along the way with that code, a few months/years back. It calculates 5 different vectors of completion options but only uses one in the end... so... the other 4 are never used. It is also wrong and makes the code completion case-sensitive and only allow options which start with the search string. I have fixed this in my branch of this PR here https://github.com/godotengine/godot/compare/master...EricEzaM:godot:65655

Additionally I am not sure if the new assign_score method is required. After some testing, the existing similarity method on String does pretty well, and so I used that in my branch (below). If we do want some custom logic for sorting it might be best placed as a local method rather than in string since it is quite specialised (also changing it means you have to basically recompile the whole engine, since most things depend on String 😅) https://github.com/godotengine/godot/compare/master...EricEzaM:godot:65655#diff-6b3879fe8504d721cd9c247489803d697d29ebc128a7288eb620013941b3af65R3118-R3124

similarity uses the Sørensen–Dice coefficient for it's calculation. If we do want some custom logic here, perhaps using Levenshtein distance or a modified version of it will serve well.

My "test" for this stuff is just seeing how much the engine fights me when I want to get thoughts onto the page. If I want to call method X on some object, how long does it take me, using code complete, to achieve that? At the moment the engine fights me a lot (case sensitive, bad order - so I can't use tab completion). But with these changes it is a lot smoother.

[Mickeon]

@EricEzaM I wouldn't mind giving you access to my repository so that we can both push changes directly into this PR, if you're ok with it too. I looked at the code comparison and it looks good to me, although in these upcoming days, I would like to compare my algorithm, similarity() and Levenshtein distance to see if there's something I'm missing or that could be possibly improved upon.

All I do know is that this needs to be addressed as much as it can, because even testing Godot 4 beta is a hassle for how uncollaborative the autocompletion is.

I agree on moving the specialised assign_score() function to the CodeCompletionOptionCompare struct. I was thinking that if its implementation was flawless, that it could be exposed for other uses as well, but since it is not yet, or it may outright be replaced by something else, it's best to move it.

[KoBeWi]

I just hit a rather annoying autocompletion case in my project and gave this PR a try. I have a script with these symbols:

var player_tracker
func apply_player_start()

I tried to complete apply_player_start by typing player

In 3.x it does not appear at all

In VS Code it appears further down, with player_tracker being the top option (which is actually desirable too, just not here)

This PR gives me multiplayer for some reason (undesirable), but at least apply_player_start is on the list:

In vanilla 4.0, none of the results are relevant xd

[Mickeon]

@EricEzaM pushed most of your changes. However, and indeed, I am not convinced using similarity for this yields good results, especially because characters at the beginning of the string are not given priority, so this PR is still worth tweaking a whole bunch.

@KoBeWi The reason you do not see what you're looking for above is because currently autocompletion options are divided in categories, and that would totally need to be re-evaluated.

[EricEzaM]

@KoBeWi With this PR updated I get

Although the Player class does not appear at all 🤔 So multiplayer appears because

• it contains player
• it is a member on the class

Maybe this could be improved by adding one more item to the CodeCompletionLocation, like CodeCompletionLocation::LOCATION_BASE_CLASS or something:

static int _get_property_location(StringName p_class, StringName p_property) {
    if (ClassDB::has_property(p_class, p_property, true)) {
        	return ScriptLanguage::LOCATION_LOCAL;
    }

    /* Add this */
    if (ClassDB::has_property(p_class, p_property, false)) {
        	return ScriptLanguage::LOCATION_BASE_CLASS;
    }
    return ScriptLanguage::LOCATION_OTHER;
}

But with the way the GDSCriptLanguage parses for code completion options, this might be difficult to get right.

With that, apply_player_start should appear ahead of multiplayer

[Mickeon]

@KoBeWi I think the PR is in a good state to be tried again. Namely, it gives much higher priority to options that contain the base string in full. In theory, that makes player_tracker show up as expected:

That, as well as other options like classes being pushed up as a result. Bear with me. It's still better than before.

Also you can write vec2 and it autocompletes completely fine so that is a net positive for me.

[RedMser]

I've taken VSCode's auto completion score code [1][2] (MIT licensed) and implemented it into a GDScript prototype. It works really well from my limited testing (even without having any context for the auto complete items, so no member/class/function info, and no inheritance info)!

(It can also highlight text, but I haven't showcased that in this demo)

But integrating this into Godot should probably wait for a follow-up PR, since it's quite a lot of code to move and adjust to C++. I also don't really understand how it works, so if anything goes wrong it may be difficult to maintain.

[Mickeon]

But integrating this into Godot should probably wait for a follow-up PR, since it's quite a lot of code to move and adjust to C++. I also don't really understand how it works, so if anything goes wrong it may be difficult to maintain.

Yeah, one thing at the time. It seemed like @akien-mga wanted to urgently fix this. Further improvements can be done later, as much as I look forward to them.

[KoBeWi]

I started testing this for real. Can't say yet if there is improvement, but the autocompletion already managed to fail me. I tried to create a Dictionary variable: (this is inside Control script)

Seems weird, because it contradicts what you said before 🤔

[EricEzaM]

Ok I have revisited this again. Found more stuff that I may have overlooked in my initial PR, or has been changed since which messed some things up. diff on this PR: https://github.com/Mickeon/godot/compare/editor-autocompletion-sort-by-score...EricEzaM:65655?expand=1

If you want to test, try the build artefact from here when it finishes: https://github.com/EricEzaM/godot/actions/runs/3874969199 See below for my testing results using peoples responses in this thread. It looks ok to me but there may be some edge cases.

Test results for every example in this thread: [toggle - long image]

Also fixes #71059

P.S. 'Container Sizing' should not be there in 2nd capture. That is a property group. Issue for another PR though.

[ajreckof]

in this screenshot, fourth results seems inappropriate. I don't know why this one was ranked so high. Is it because it ends with te? if so i don't think ending with a match should be ranked as high as starting with a match

[EricEzaM]

@ajreckof it's because it is a local function on the class.

It's true that it might be better for things which are local but are bad matches to be pushed lower.

[ajreckof]

yeah it feels conter productive for them to show when they are not that much pertinent. I think results should first be sorted for match and on same level of match being sorted by scope.

[Kakiroi]

Is there a way to remedy this? I don't think it's that useful for the first match to come up for such common abbreviation. IF I wanted the first match, I would search 'Visual' first. Maybe give more points for entry that has matched letters from the start? (or early?)

Funny because, v3 actually gives Vector3 as first entry. Feels like shortening words give more accurate result.