Converting StrongInject to incremental generators

[YairHalberstadt]

I am the author of StrongInject, a source generator which provides a compile time IOC container.

It is one of the most popular SourceGenerators, and also one of the largest, and most production ready. As such it serves as a useful testcase for the practicality of IncrementalGenerators.

@sharwell reported in YairHalberstadt/stronginject#179 that StrongInject was causing performance issues in @jnm2's solution in VS. This is because running StrongInject took a long time on this particular very large project, and it was rerunning on every single edit. @sharwell suggested moving to Incremental Generators to alleviate this issue.

This discussion serves as an overview of the challenges involved in this, the suggested paths I looked into, the current approach I took, my future ideas for how to improve this, and a plea for suggestions as to how I can do better, possibly with the help of additional APIs provided by roslyn.

StrongInject overview

Every time StrongInject runs it runs the following stages (high level, and details not one hundred percent accurate):

1. Looks at all classes to see if any are modules or containers.
2. Visit any modules or containers to validate registrations and build a Dictionary<ITypeSymbol, Registration>
3. Visits any containers and builds a graph describing how to resolve the container targets.
4. Lowers the graph into C# code.

A module might look like this:

public record Service(Config config) : IService;

[Register<Service, IService>]
public class Module
{
    [Factory] Config LoadConfig() => null;
}

A Container might look like this:

[RegisterModule(typeof(Module))]
public class Container : IContainer<IService> {}

Stronginject would then generate a graph that represented something like this:

IService -> Register<Service, IService> -> new Service(Config) -> [Factory] Config LoadConfig() -> LoadConfig()

And lower that into code:

IService Resolve() => new Service(LoadConfig());

Investigated incremental approaches

Running stages 3 and 4 incrementally seems particularly tricky, since small changes to registrations can cause large changes to the resolution graph.

Instead my approach focused on reducing how often stages 3 and 4 have to run at all, by only rerunning when relevant changes were made to registrations or the registered types.

1. Check for changes in the Dictionary<ITypeSymbol, Registration>

This approach runs stages 1 and 2 on every edit, and checks if the output of stage 2 has changed at all. If not it doesn't need to rerun stages 3 and 4.

pseudocode:

var registrations = context.CreateSyntaxProvider(
     x => x.IsModuleOrContainer(),
     x => x.CreateRegistrationsDictionary(),
)

context.RegisterSourceOutput(registrations, (ctx, registrations) => ctx.AddSource(GenerateSource(registrations))); 

Unfortunately this approach is dead in the water because Symbols cannot be compared between compilations.

Also calculating the Dictionary is still somewhat expensive and doing that on every change is undesirable.

There are a couple of related approaches that solve the problem that symbols cannot be compared between compilations:

1.1 Convert symbols to custom StrongInject specific types.

Instead of working with symbols directly, we could convert the symbols to some stronginject specific type, which just stored the information necessary to be able to generate code, and could be compared across compilations.

E.g.

record StrongInjectNamedTypeSymbol(string Name, string Namespace, StrongInjectTypeSymbol[] TypeArguments) : StrongInjectTypeSymbol();

This unfortunately suffers from a number of issues.

The main problem is that the amount of information required is actually quite high. StrongInject needs to know:

• constructors
• base types
• interfaces
• type arguments
• type parameters
• type parameter constraints

This leads to a number of issues:

1. Creating these type symbols is quite expensive and has to be done on every change.
2. Creating these symbols is complex, and can easily lead to infinite loops due to recursion (e.g. class A : IEquatable<A>).
3. Comparing these symbols for changes is complex and can easily lead to infinite loops due to recursion.
4. Doing this takes a huge amount of dev time.

It also leads to the problem that I can't use roslyn APIs any more. For example, I need to be able to check if List<string> can be cast to IEnumerable<object>. Reimplementing this code for StrongInjectTypeSymbols is error prone.

1.2 Use a custom comparer to compare the symbols across compilations

We could use a custom comparer to check whether any changes have been made to the symbols in the Dictionary that StrongInject cares about, and continue using the actual roslyn symbols in future steps.

This alleviates problems 1 and 2, and mitigates problem 4.

Comparing the symbols for changes is still complex, and still leads to the risk of infinite recursion.

This also creates some new problems:

1. It's easy to miss something that matters and not rerun when a significant change has been made.
2. It's easy to check something that doesn't matter, and rerun when there's no need to do so.
3. We're keeping old symbols alive. This may impact correctness in weird ways - especially if we end up accidentally using symbols from multiple compilations somehow. It also means old compilations can't be GC'ed which is bad for memory usage.

2. Look for changes in classes that may be relevant.

Instead of building up a Dictionary<ITypeSymbol, Registration> on every single change, what if instead we find a way to cheaply look for any changes that might be relevant to StrongInject, ideally in an incremental fashion. Once we know that somethings changed, we find a way to to rerun all 4 changes from scratch, and simply discard any of the information we used to find out what changed.

Ideally we want to have an API that looks something like this:

context.CheckForChanges(new MyChangeChecker());

context.GeneratorToRunOnChanges(new MyV1SourceGenerator());

The advantage of this is we don't need to tie how we check for changes to how we run the generator afterwards. This makes it easier for us to design change checking to be incremental, and also means we don't need to calculate and cache all the information we might possibly need in the future. We only need to store information relevant to checking whether any relevant changes have in fact occurred.

To do this we need to check whether any of the following has changed:

1. Any changes to a module or container at all.
2. Any of the following changes to a type declaration:
   • Addition/deletion of a class or struct.
   • Changing the name or namespace.
   • Changing the base classes, interfaces, type parameters, type parameter constraints.
   • Changing the signature of a delegate type
   • Addition or removal of constructors.
   • Changing the signature of a constructor.
3. This include changes to modules or type declarations in MetadataReferences as well as the current compilation.

Checking for any changes to a module or container is easy - checking whether the SyntaxTree has changed is a good way to do this.

In order to do number 2 efficiently we want to restrict ourselves to only checking syntactic changes as much as possible. Purely syntactic checks only need to rerun when their SyntaxTree changes, whilst semantic checks need to rerun on every change.

The ideal algorithm would look something like this:

Whenever a SyntaxTree changes:
  Check if the SyntaxTree has any changes to:
    Imports:
      Semantically check if all relevant TypeReferences in the tree still bind to symbols with the same fullly qualified name as before.
    Constructors:
      Semantically check if the same number of constructors exist, and that they have the same signature as before.
    Type Declarations:
       Check if the type signature (i.e. names, base classes, type parameters etc.) has changed.

Doing this in the current API is tricky:

var syntaxTrees = context.CreateSyntaxProvider(
    node => node.IsSyntaxRoot(),
    (node, compilation) => node
)

syntaxTrees.MagicallyCombineWithCompilationInAWayThatOnlyRerunsTheChangedSyntaxTreesEvenIfTheCompilationChanges()
.Select(
   (tree, compilation) => CreateDataClassContainingOnlyThingsWeCareAboutIfTheyveChanged(tree, compilation);
)

I'll show you how I do the magic in the section below on the current solution.

CreateDataClassContainingOnlyThingsWeCareAboutIfTheyveChanged has many of the same problems as earlier solutions:

1. Creating this DataClass is complex, and can easily lead to infinite loops due to recursion.
2. Doing this takes a lot of dev time.
3. It's easy to miss something that matters and not rerun when a significant change has been made.
4. It's easy to check something that doesn't matter, and rerun when there's no need to do so.

Checking whether there's changes to type declarations in MetadataReferences is easy when the MetadataReference is a PortableExecutableReference reference or similar - these change infrequently, so it's fine to rerun whenever they change, So we can store a list of MetadataIDs and rerun if those ever change.

What's more complec is checking whether a CompilationReference has changed. These change all the time. What we will have to do is again store a list of all trees in the referenced compilation, and rerun whenever there's any relevant changes to referenced compilations too.

Current Solution

The current solution is similar to solution 2. but sacrifices correctness for the purpose of simplicity.

StrongInject will only ever report diagnostics on the module or container classes. So even though changes to other classes may effect those diagnostics, the use probably doesn't mind if the diagnostics don't immediately update if they're not focused on the module/container files.

As a proxy for whether the user is focused on the module/container files, StrongInject checks whether any of those files have been edited, and only reruns if so.

This solution aims to create a reasonable user experience at the sacrifice of correctness. For example imagine StrongInject reported an error because a user registered Service as IService but Service doesn't implement IService. Then if the user fixed that StrongInject wouldn't update the diagnostic until the user edited the module where it was registered.

This is okish in an IDE, but will lead to problems in hot reload for example. This always works in actual builds since builds are never incremental - at least for now.

Tricking the compiler

Generating StrongInject code requires the use of a compilation. And if our code relies on a Compilation, the IncrementalGenerator API will rerun it on every single change.

In order to avoid this happening we use this lovely hack:

var compilationWrapper = context.CompilationProvider.Select((x, _) => new CompilationWrapper(x));
context.RegisterSourceOutput(trees.Combine(compilationWrapper)

CompilationWrapper is a type defined here.

It stores a Compilation, and implements IEqualityComparer. Equals always returns true, ensuring that changes to the compilation won't cause the generator to rerun. However it's important to always run with the latest compilation when the generator needs to rerun for another reason, so on every equals comparison it swaps out the compilation of whichever CompilationWrapper is earlier with the compilation from the later CompilationWrapper.

This seems to work well but is of course risky. For example it could theoretically fail in a concurrent environment, where a CompilationWrapper might be created for an earlier Compilation after a CompilationWrapper is created for a later Compilation, leading to us swapping out the later compilation for the earlier compilation on an Equality comparison, rather than the other way round.

Desired API

It would be useful if Roslyn provided a way to separate out the question of whether a generator should rerun, from what it uses when it runs. This does require trusting the user to get this right, unlike the current API which is correct by design, but I think is necessary for implementing something like StrongInject incrementally in an efficient fashion.

Conclusion

I hope it's clear from this:

1. What StrongInject does.
2. How StrongInject is designed.
3. The challenges involved with running StrongInject incrementally.
4. Some of the avenues I've explored to do this, their benefits, and their pitfalls.
5. What my current solution looks like.
6. The desire for alternative APIs.
7. That even with alternative APIs the best solution I can think of will be far from perfect.

If any of that isn't clear, I'm happy to clarify further.

I would also love to hear any suggestions you have for alternative designs to run StrongInject incrementally!

Thanks!

cc @CyrusNajmabadi

[sharwell]

It stores a Compilation, and implements IEqualityComparer. Equals always returns true, ensuring that changes to the compilation won't cause the generator to rerun.

This absolutely must not happen.

The compiler intends to cache source generator outputs across passes of the command line compiler. The approach seen here would reuse stale (and potentially invalid) outputs from a previous run of the compiler, producing unspecified behavior of the compiler and the resulting assembly.

I have a longer reply for the other items separately.

[YairHalberstadt]

The hack ensures that:

1. The generator doesn't always rerun when the compilation changes.
2. If it does change the latest compilation will be used.

I agree it's a hack, I'm just not sure what will go wrong in practice if I use it (other than stale source being generated, which is bad, but so long as for an actual build a full run always occurs, not critical).

[sharwell]

but so long as for an actual build a full run always occurs

This is not only not guaranteed by the compiler, but there are active plans to ensure it will not run a full pass. At that point, the source generator will start producing output assemblies on disk with unknown/stale content.

[YairHalberstadt]

This is not only not guaranteed by the compiler, but there are active plans to ensure it will not run a full pass. At that point, the source generator will start producing output assemblies on disk with unknown/stale content.

Ok. This suggest that if I want to use this hack I'll have to go with the full approach outlined in 2. where I make sure to catch all possible changes that could affect the final generated output, rather than go with a heuristic.

I'm thinking of just being super conservative and rerunning on any of the following syntactic changes:

Changing or adding/removing an import.
Changing or adding/removing a Type Signature
Changing or adding/removing a Constructor
Changing or adding/removing a module/container.

This seems to me relatively simple to implement, and avoids rerunning every time a method body changes, which should hopefully significantly alleviate the main performance problems with StrongInject.

[sharwell]

If implemented correctly (i.e. the comparison captures all possible changes that can affect the output), this is a working/correct solution. It is not a solution I recommend because it's impossible to prove correctness and would be very to introduce a change in the future which is not captured by the equality comparer, and it would be extremely difficult to detect this situation.

[CyrusNajmabadi]

here's the problem. i think yair laid out very well why a correct solution is simultaneously extraordinarily complex and difficult to provide with the primitives we offer. In particular 1.1 Convert symbols to custom StrongInject specific types captures why this is so hard today.

First, all the data must be captured and transformed. And then all the logic must be written to support those transformations and data types to work properly in our system.

When the data is trivial like simple strings and whatnot, then this is fine. When the data is much more complex things like signatures and relationships, this incurs an extremely high burden on the SG author.

We should see what we can do here to make it much easier to do things like capture(s) all possible changes that can affect the output. When dealing with symbolic information, for example, it gets decidedly non-trivial. To the point that the solution is so complex that it itself becomes very hard to reason about correctness.

[sharwell]

The primary problem with the above presentation is the manner in which the problem was approached. The approach I've been recommending for incremental source generators is the following:

1. Identify the desired output(s) for the source generator.
2. For each output, define a self-contained domain model containing information sufficient to produce that output. This model should not have strong references to Roslyn types (e.g. ISymbol or Compilation), but should instead have its own representation of the data. The closer this model is to necessary, the better the generator will perform.
3. The incremental stages of the pipeline serve only to convert Roslyn's representation of a compilation to the domain model(s) used for producing the source generator output.

This approach has many benefits in practice. It's easy to see that it completely eliminates the original problem where the compilation changing leads to re-running the output step (the output generation now only runs when the model changes, which means the output itself may have changed). It also allows the generator author to optimize the incremental data extraction over time (e.g. adopting future compiler APIs for more efficient semantic filtering) without requiring changes to the source generation step itself.

In practice, this approach has proven relatively straightforward for new source generators. It's much more complex for converting an existing ISourceGenerator to IIncrementalGenerator, but over time this will fade away as the former is not recommended for most new development.

[YairHalberstadt]

It's possible this might be doable with enough effort, and next time I have a significant amount of time I'll give this a real shot (I've tried a couple of times but given up quite early).

However I still think it's less than ideal that Roslyn provides such an excellent API, but you basically have to implement everything from scratch when writing IncrementalGenerators.

[sharwell]

but you basically have to implement everything from scratch when writing IncrementalGenerators.

You aren't required to implement everything from scratch. Passing in the compilation and allowing the output to generate again after every change is sufficient for correctness. The reimplementation on a domain model is a careful reduction in scope moving from sufficient towards necessary. The amount of work required varies by the design and complexity of the generator itself. Roslyn can't provide this automatically without creating a unique API for each potential generator.

This isn't to say Roslyn can't help here. We're certainly interested in APIs that simplify the production of domain models for common scenarios.

[CyrusNajmabadi]

This model should not have strong references to Roslyn types (e.g. ISymbol or Compilation)

The problem here is that that means that if those entities can only be referenced on Step 1 of the transformation pass, that all information that might be needed for generation must be extracted from that on every edit no matter what.

That is inherently quite costly and wasteful, especially as most edits won't actually produce a change that would affect final compilation.

I get what you are saying is not incorrect sam. It is a precise and well formed design that has benefits. But it also ramps up the complexity and difficulty of incremental generation to the point of making it either/both:

1. so complex that trying to implement it properly will likely have it's own issues as the complexity will introduce it's own problems as well.
2. very expensive as the generator has to collect and do so much work up front on every edit to form their own full domain model that incremental barely even buys you anything.

We are missing a good middle ground here. One where the generator can work with simpler models that are reasonable to produce per-edit, and which can be used to solve the problem of avoiding more expensive later work. StrongInject is a popular and powerful system that helps demonstrate the issues with the current system. It can either avoid incremental today (giving a a very costly experience) or it can use incremental, but it still is very costly as it still must do all its work up-front to generate everything it needs for its model. In this case, incremental is inherently not solving anything for it because it's just shuffling costs around, and not actually providing the necessary pieces so that non-important edits can be filtered out almost instantly (which is the desirable outcome for all generators).

[YairHalberstadt]

You aren't required to implement everything from scratch. Passing in the compilation and allowing the output to generate again after every change is sufficient for correctness.

Passing in the Compilation isn't really an option for large projects, as @jnm2 discovered.

The reimplementation on a domain model is a careful reduction in scope moving from sufficient towards necessary.

I'm not sure what you're saying here, but there's no way to slowly make this change and reduce the reliance on compilation bit by bit. I would have to literally re-implement the entire thing from scratch in terms of StrongInject specific symbols.

and next time I have a significant amount of time I'll give this a real shot

I've started this, and I'm just looking at what I'm doing and going "I've re-implemented roslyn". This doesn't feel like it should be a requirement for writing any reasonably complex source generator.

To be clear I don't actually have any better ideas. I understand very well why the API is like it is, and I think it's great for some problem classes - for example I think it might fit my SpanLinq generator quite well with a small refactoring. I just don't think this is a sufficient solution for many use cases, and I would really like for there to be one!

[sharwell]

This doesn't feel like it should be a requirement for writing any reasonably complex source generator.

To me, it doesn't feel like an unrealistic requirement. In terms of the history of writing efficient incremental IDE features, the path described here does not seem unreasonable. While it's a significant amount of work, the steps are relatively straightforward so with a bit of time you can be confident the output will work as desired.

My concern here is we're presented with one "easy" option, and one "efficient" option. Several people indicated they wish the efficient option was also easy, but I haven't seen any details that would suggest it's a viable outcome.

[CyrusNajmabadi]

Tagging @jasonmalinowski and @chsienki here. I think IGs were a good start and certainly suitable for certain classes of generators. However, its (understandable) restrictions really make it non-suitable precisely for the types of expensive generators we would want it to be most viable for.

Yair isn't doing something strange or undesirable. Indeed, i think StrongInject is a poster child for a great place to do some very interesting generation work. Unfortunately, the current design of generators (incremental or otherwise) seem to make it nigh impossible to get good perf and not cause huge complexity in the generator itself.

I would like us all to brainstorm what is possible here, and what we think may be acceptable to expose if we think have a desire for highly powerful generators like this to be possible without huge complexity for the author, and with great perf for the user.

Importantly, i think this means brainstorming new options. The current IG system is good at some thigns, but has shortcomings elsewhere. Unless there is an amazing idea on how stronginject could work with those shortcomings, we should focus on what we can do to make generators like that viable in a way we feel is sensible.

[sharwell]

One hypothetical design would involve the ability to write a GraphQL (or similar) query against the symbol model, which produces wrapped symbol instances that throw if any attempt is made to access a property which has not been captured in the query. The internal implementation of this functionality would dynamically create an equality comparer that only considered properties from the query in determining whether the symbol model changed.

While certainly general enough to meet a variety of needs, it's not clear that this model would perform well enough to have negligible overhead compared to the custom domain model described earlier.

It could certainly be implemented as a library if someone wanted to create a proof of concept.

[YairHalberstadt]

Whilst I don't think it's at all practical for roslyn at this stage (it would probably require a complete rewrite) it's interesting to look at the rust compiler which is query driven: https://rustc-dev-guide.rust-lang.org/query.html

Everything the compiler does is defined as a bunch of queries which rely on other queries, etc. and it's designed so that most queries can be cached between runs. This is actually pretty similar to the IncrementalGenerator model - the problem is that the inputs are too course grained as it doesn't implement queries all the way down, so you can't for example reference a particular property of a particular symbol and only rerun if that exact property changed.

[jasonmalinowski]

First off @YairHalberstadt just wanted to give a huge shout-out for your writeup to kick this whole conversation off; it's a great explanation of your problem space and also why various things fall over, so aweseome job.

One hypothetical design would involve the ability to write a GraphQL (or similar) query against the symbol model, which produces wrapped symbol instances that throw if any attempt is made to access a property which has not been captured in the query.

We did discuss this awhile back, I don't recall @chsienki did we reject this for a specific reason or did we generally decide to go with our current model, and assumed the "extract to your custom type" was good enough for that case?

I also recall having one idea that rather than having to explicitly state what you use, whether we could track what a generator read and automatically know what it depended upon, i.e. a generator that doesn't read BaseType anywhere probably doesn't depend on it changing. I have zero idea how to implement that though. 😄

One thing I didn't quite see discussed -- is this a place we should be using "implementation only" generated output? StrongInject obviously needs to walk everything to figure out the graph, but I what are the required inputs for the API surface that StrongInject must produce in the IDE? Because if we can split this into two pieces, and that's a lot cheaper, then we could restrict the more expensive part to the implementation output and that'll run a lot less. (Caveat: we haven't actually done the work to light that up in the IDE, but this would be a great example to actually test the end-to-end.)

[YairHalberstadt]

One thing I didn't quite see discussed -- is this a place we should be using "implementation only" generated output?

StrongInject still needs to report diagnostics, which means it has to do stages 1,2 and 3 but could skip 4. This could possibly half the time taken, but won't significantly reduce the required inputs, and won't be enough to make @jnm2's project performance. So definitely worth doing once the API becomes available, but not really a solution.