Join GitHub today
GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.Sign up
x/tools/gopls: use BFS instead of DFS for deep completions #39113
I suspect that using a breadth-first traversal for deep completions will lead to improvements in the speed with which deep completions finds matching candidates.
I also think this change may allow us to restructure the completions code in way that is a bit clearer by giving completions more defined "phases":
These phases are already exist in the code, but the fact that the deep completions happen in
Somewhat related: We could have the 100ms deep completion timeout apply to phases 1 and 2, always (even without deep completions), with no time limit on 3 to avoid dropping matches that we ran out of time to format.
@muirdm: What do you think? I haven't actually tried implementing any of this, so I'm sure I'm missing a lot, but does this sound reasonable / doable?
I agree breadth first search will typically find the good candidates sooner, so it will give better results when don't have enough time to search all the candidates.
There are cases with a lot of deep candidates (e.g. 100k), so it is important to be able to filter weak candidates as you go. You don't want to end up collecting 100k candidates, sorting and taking the top N since that will be slow. Currently we track the top N=3 deep candidate scores we have seen, and if we find a new candidate not in the top N then we don't collect it.
My original intention was to have the 100ms budget apply to everything as you suggest, but OTOH it would be weird to miss an "obvious" lexical candidate because gopls ran out of budget for whatever reason.
Currently the item formatting can be quite slow due to documentation fetching and type/alias formatting. I don't think we should exclude the time spent formatting until we speed those up.