Add API to incrementally find usages of a type.

[YairHalberstadt]

Background and Motivation

In https://github.com/dotnet/roslyn/discussions/59105 I discussed the difficulties converting StrongInject to incremental generators.

That however focused mainly on the stage once StrongInject has already found the relevant modules and containers, and needs to check them and generate code. I assumed that the first stage of finding all modules and containers would be quick.

After further performance analysis I discovered that this isn't actually the case.

StrongInject finds all classes which:

• Implement StrongInject.Container
• Or have a Stronginject attribute
• Or any of their members have a Stronginject attribute

To do this it has to visit all classes, and call GetAllInterfaces, GetAllMembers, and GetAttributes on every member. This turns out to be incredibly expensive even when StrongInject isn't used at all.

For example, when I simply added a reference to StrongInject to Microsoft.CodeAnalysis it increased compilation times by 10-20%:

Because checking if an attribute is of a particular type requires access to the actual symbol, this can't be done incrementally either - on every single edit we must visit all attributes. And this is something that the a large percentage of generators will need to go through - finding all usages of an attribute.

It would however be possible for roslyn to provide e.g. all attributes of a given type incrementally. I will attempt to sketch out how this could be done.

Proposed API

namespace Microsoft.CodeAnalysis
{
     public struct IncrementalGeneratorInitializationContext
     {
+        public TypeUsagesProvider TypeUsagesProvider { get; }
     }

+   public struct TypeUsagesProvider
+   {
+       /// Creates an IncrementalValuesProvider<AttributeSyntax> that returns all attributes where the attribute class name matches any of fullAttributeNames.
+       public IncrementalValuesProvider<AttributeSyntax> CreateAttributesProvider(params string[] fullAttributeNames);
+       /// Creates an IncrementalValuesProvider<BaseTypeSyntax> that returns all base types where the type name matches any of fullTypeNames.
+       public IncrementalValuesProvider<BaseTypeSyntax> CreateBaseTypesProvider(params string[] fullTypeNames);
+       /// Creates an IncrementalValuesProvider<BaseParameterSyntax> that returns all parameters where the type name matches any of fullTypeNames.
+       public IncrementalValuesProvider<BaseParameterSyntax> CreateParametersProvider(params string[] fullTypeNames);
+   }
}

Of course there's plenty more members that could be added - attributes, base lists, and parameters are just given as an example. Attributes however are the most critical.

Implementation

Roslyn will incrementally maintain a list of all global aliases. This can be done similarly to how it does this for DeclarationTable.Cache - most files stay the same, and one file is updated with the changed aliases.

It will then visit every file and recursively visit all namespace declarations in the file. It will check which aliases are in scope within each namespace declaration.

This should allow it to know at each point which identifiers could possibly refer to the requested type (candidates).

It will maintain an incremental list of candidates. When no global using aliases have changed (i.e. 99.99% of the time) only a single file will need to be visited to update the candidate list.

On every edit it then requests semantic information for each of those candidates and checks whether they indeed refer to the requested type.

This should be orders of magnitude more efficient than requesting semantic information for every single member on every single edit.

I believe that doing this is impossible to do with the current Incremental Generators API, because only syntactical filtering can be done incrementally by the SyntaxProvider, and the syntactical filtering doesn't allow us to know which global usings exist.

Usage Examples

StrongInject would initially use this as follows:

modules = context.TypeUsagesProvider.CreateAttributesProvider(allStrongInjectAttributes)
    .Collect().SelectMany(x => x.Select(x => GetContainingType(x)).Distinct);

With a bit of effort it might be possible to use each attribute individually too rather than just using them to find the containing type, but just doing this should already be a huge performance boost.

Alternative Designs

StrongInject could require all containers and modules to mark themselves with a specific attribute, removing the need to visit interfaces and members. this would still have less than ideal performance characteristics.

It could also say it doesn't support global aliases, and implement this API itself.

However I think this sounds like a general problem which requires a performant solution for everyone, and ideally one which is semantically accurate and doesn't just ignore global aliases.

Risks

The biggest risk is this API would need to duplicate the logic for how aliases work. For example it needs to know that in:

using X = System;
namespace N
{
    using Y = X.String;
    public record C(Y y);
}

Y is a candidate for System.String.

Any differences in the implementation could lead to incorrect results.

However I think this is actually a relatively small amount of logic, and shouldn't be too difficult to get right.

[YairHalberstadt]

cc @CyrusNajmabadi, @sharwell, @chsienki

I would be happy to implement this if the API is accepted.

[CyrusNajmabadi]

This sounds reasonable, and I think can be done syntactically pretty safely. I agree that the vast majority of the time, only one file would be visited if implemented properly.

[chsienki]

Related https://github.com/dotnet/roslyn/issues/54725

[jcouv]

Assigned to @chsienki as area owner for source generators to drive API review and/or re-triage.

[CyrusNajmabadi]

@chsienki I'm interested in this. If you do any work/designs here, can you include me? Thanks!