Skip to content

Update FAR engine to be able to work without having access to all projects at the same time.#54654

Merged
CyrusNajmabadi merged 89 commits intodotnet:mainfrom
CyrusNajmabadi:farOrder2
Jul 15, 2021
Merged

Update FAR engine to be able to work without having access to all projects at the same time.#54654
CyrusNajmabadi merged 89 commits intodotnet:mainfrom
CyrusNajmabadi:farOrder2

Conversation

@CyrusNajmabadi
Copy link
Copy Markdown
Contributor

@CyrusNajmabadi CyrusNajmabadi commented Jul 7, 2021

Note: tehre is a large amount of churn in this PR. I recommend anyone reviewing it potentially discuss things with me first to get a sense of what is going on. I will also attempt to doc what's going on the best that i can.

--

This PR heavily changes the way that the FAR engine works. To help understand what has changed, it's worth going through how the existing engine behaves. Specifically, how it behaves with respect to finding symbols in a particular symbols' inheritance hierarchy.

To see where this occurs, imagine you have:

interface IFoo
{
    void Foo();
}

class C : IFoo
{
    public void Foo() { }
}

When searching for either IFoo.Foo or C.Foo, FAR must 'cascade' to the other as the user may have calls to either in their solution, but all those results should be returned as without htem the user may not know about relevant calls that might end up calling into the member in question they care about.

To support this, teh FAR engine today first walks the entire symbolic inheritance hierarchy for a symbol looking for all these connections. This necessarily mandates looking at all projects to find all of these. Then, once all the symbols are found, we use those to determine our plan for searching all the relevant projects and documents in teh solution for actual matches.

This is two-fold problematic. First, you can't get any results from FAR until we've done that first full solution scan. Second, it requires us to actually be able to see teh whole solution to search it for the inheritance symbols. This is particularly problematic as we work toward the snappy-design (where we will not have projects loaded for code the user isn't directly working with).

--

With that out of the way, here's how the new engine works. Instead of first scanning the entire solution to figure out the inheritance hierarchy, we instead do it piece-meal. Specifically, given a starting symbol we can always trivially find the symbols above it in the inheritance hierarchy. These are the symbols that it inherits from, and it must be in the same project or a project it references (both of which will be loaded for the user). Given those symbols, we can determine the set of dependent projects that could end up referencing these.

We then process those dependent projects individually. As we get to each project we can then scan it to determine what new symbols may be in that project that derive from teh symbols being searched for. Once we've determined that, we can then add that project to the queue of projects that the engine can scan concurrently with the rest.

--

Currently, iterating through the dependent projects is still handled by Roslyn. However, this sets us up for a future where we allow dependent project iteration to be handled by an external service. For example, you could imagine services provided in VS to walk the set of projects loading them, searching them, and then unloading them to keep resource utilization low.

@ghost ghost added the Area-IDE label Jul 7, 2021
Copy link
Copy Markdown
Member

@dibarbet dibarbet left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this is one PR where I wish richnav PR indexing worked!

/// </summary>
/// <remarks>
/// This method is non threadsafe as it mutates the symbol set instance. As such, it should only be
/// called serially. <see cref="GetAllSymbols"/> should not be called concurrently with this.
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

would it be worth implementing these methods with a lock / some kind of assert in here verifying that no one is accidentally calling these methods concurrently, then delegate to other abstract methods?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes. I can add a poor man's assert that only one is being called at a time.

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I like this idea. Maybe only in Debug though?

@CyrusNajmabadi CyrusNajmabadi requested a review from dibarbet July 12, 2021 17:48
Copy link
Copy Markdown
Contributor

@ryzngard ryzngard left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I still need to look at src/Workspaces/Core/Portable/FindSymbols/FindReferences/FindReferencesSearchEngine.cs changes, but brain can only do so much this late

// First find all the projects that could potentially reference this type.
var projectsThatCouldReferenceType = await GetProjectsThatCouldReferenceTypeAsync(
type, solution, searchInMetadata, cancellationToken).ConfigureAwait(false);
List<Project> orderedProjectsToExamine;
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: I know it's generally bad to use IEnumerable<T> instead of a concrete class, but this might be a case where it makes more sense. It would help avoid the ToList call and we only need it to iterate. Is there a reason to use List<T> here instead?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this is a good question. The reason is more philosophical than anything else. I'm generally wary of IEnumerables as it can be very hard to gauge certain things (for example: how expensive htey are, or if they return teh same results when querying them multiple times). A list is a well known construct that i can be sure is computed and will give me consistent results.

/// </summary>
/// <remarks>
/// This method is non threadsafe as it mutates the symbol set instance. As such, it should only be
/// called serially. <see cref="GetAllSymbols"/> should not be called concurrently with this.
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I like this idea. Maybe only in Debug though?

return result;
}

private static async Task<HashSet<ISymbol>> DetermineInitialUpSymbolsAsync(
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Are there cases where we add up symbols that aren't part of the initial? Like through linked symbols?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

yes. a simply example is if you start on an override. The 'initial up' symbols will contain the member that this override overrode (And everything higher).

Copy link
Copy Markdown
Member

@dibarbet dibarbet left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think mainly looks good to me!

@CyrusNajmabadi CyrusNajmabadi enabled auto-merge July 14, 2021 20:26
@CyrusNajmabadi CyrusNajmabadi merged commit debd668 into dotnet:main Jul 15, 2021
@ghost ghost added this to the Next milestone Jul 15, 2021
allisonchou added a commit to allisonchou/roslyn that referenced this pull request Jul 16, 2021
RikkiGibson pushed a commit that referenced this pull request Jul 16, 2021
CyrusNajmabadi added a commit to CyrusNajmabadi/roslyn that referenced this pull request Jul 16, 2021
CyrusNajmabadi added a commit that referenced this pull request Jul 25, 2021
Revert "Revert "Merge pull request #54654 from CyrusNajmabadi/farOrder2" (#54874)"
@allisonchou allisonchou modified the milestones: Next, 17.0.P3 Jul 27, 2021
@CyrusNajmabadi CyrusNajmabadi deleted the farOrder2 branch September 30, 2021 18:02
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Projects

None yet

Development

Successfully merging this pull request may close these issues.

6 participants