Incremental Generator Work Tracking APIs

[jkoritzinsky]

Background and Motivation

The Source Generator V2 APIs introduce the concept of "incremental generators". These generators describe their work as a pipeline of transformations and filters, which the generator driver can incrementally run steps of a generator. As part of supporting this, the API allows developers to provide custom comparers to enable using their own custom types between stages. For complex source generators that carry a lot of state, it is desirable to validate that the incrementality for various steps is preserved (a given step in the transform will result in the same value as a prior run, so later results based on this result are pulled from the cache).

This proposal proposes APIs to enable tracking this information without requiring incremental generators to carry state (which is undesired by the Roslyn team to my understanding).

Approved API

namespace Microsoft.CodeAnalysis
{
    public static class IncrementalValueProviderExtensions
    {
+        public static IncrementalValueProvider<TSource> WithTrackingName<TSource>(this IncrementalValueProvider<TSource> source, string name);
+        public static IncrementalValuesProvider<TSource> WithTrackingName<TSource>(this IncrementalValuesProvider<TSource> source, string name);
    }

    public readonly struct GeneratorDriverOptions
    {
+       public readonly bool TrackIncrementalGeneratorSteps;

+       public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs, bool trackIncrementalGeneratorSteps);
    }

    public class GeneratorRunResult
    {
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedSteps { get; }
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedOutputSteps { get; }
    }

+    public static class WellKnownGeneratorInputs
+    {
+        public const string Compilation = nameof(Compilation);
+     
+        public const string MetadataReferences = nameof(MetadataReferences);
+     
+        public const string AdditionalTexts = nameof(AdditionalTexts);
+     
+        public const string ParseOptions = nameof(ParseOptions);
+     
+        public const string AnalyzerConfigOptions = nameof(AnalyzerConfigOptions);
+     
+        public const string SyntaxTrees = nameof(SyntaxTrees);
+    }
 
+    public static class WellKnownGeneratorOutputs
+    {
+        public const string SourceOutput = nameof(SourceOutput);
+     
+        public const string ImplementationSourceOutput = nameof(ImplementationSourceOutput);
+    }

+    public class IncrementalGeneratorRunStep
+    {
+        public string? Name { get; }
+        public ImmutableArray<(IncrementalGeneratorRunStep Source, int OutputIndex)> Inputs { get; }
+        public ImmutableArray<(object Value, IncrementalStepRunReason Reason)> Outputs { get; }
+        public TimeSpan ElapsedTime { get; }
+    }

+    public enum IncrementalStepRunReason
+    {
+        New,
+        Modified,
+        Unchanged,
+        Cached,
+        Removed
+    }
}

Proposed API (Updated based on August 25, 2021 API Review)

namespace Microsoft.CodeAnalysis
{
    public static class IncrementalValueProviderExtensions
    {
+        public static IncrementalValueProvider<TSource> WithTrackingName<TSource>(this IncrementalValueProvider<TSource> source, string name);
+        public static IncrementalValuesProvider<TSource> WithTrackingName<TSource>(this IncrementalValuesProvider<TSource> source, string name);
    }
}

namespace Microsoft.CodeAnalysis
{
     public readonly struct GeneratorDriverOptions
     {
        public readonly IncrementalGeneratorOutputKind DisabledOutputs;
+       public readonly bool TrackIncrementalGeneratorSteps;

        public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs);
+       public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs, bool trackIncrementalGeneratorSteps);
     }

     public class GeneratorRunResult
     {
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedSteps { get; }
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedOutputSteps { get; }
     }

+    public class IncrementalGeneratorRunStep
+    {
+        public const string CompilationStep = "Compilation";
+        public const string ParseOptionsStep = "ParseOptions";
+        public const string AdditionalTextsStep = "AdditionalTexts";
+        public const string SyntaxTreesStep = "SyntaxTrees";
+        public const string AnalyzerConfigOptionsStep = "AnalyzerConfigOptions";
+        public const string MetadataReferencesStep = "MetadataReferences";
+        public const string SourceOutputStep = "SourceOutput";
+        public string? Name { get; }
+        public ImmutableArray<(IncrementalGeneratorRunStep Source, int OutputIndex)> Inputs { get; }
+        public ImmutableArray<(object Value, IncrementalStepOutputStatus Status)> Outputs { get; }
+        public TimeSpan ElapsedTime { get; }
+    }

+    public enum IncrementalStepOutputStatus
+    {
+        New,
+        Modified,
+        Unchanged,
+        Cached,
+        Removed
+    }
}
}

Generators created with a GeneratorDriverOptions instance with TrackIncrementalGeneratorSteps=true would record the results of each of the steps of the various incremental generators run by the driver.

Open Question: Should the recorded steps include unnamed steps and named steps, or just named steps?

Usage Examples

class MyGenerator : IIncrementalGenerator
{
    ...
}
...

GeneratorDriver driver = CSharpGeneratorDriver.Create(new [] { new MyGenerator() }, null, null, null, new GeneratorDriverOptions(IncrementalGeneratorOutputKind.None, true));
Compilation comp1 = ...;

// Run the generators once to set up the baseline cached results.
driver = driver.RunGenerators(comp1);

Compilation comp2 = comp1.AddSyntaxTrees(...);

driver.RunGenerators(comp2);

GeneratorRunResult steps = driver.GetRunResults().Results[0];

Assert.Equal(IncrementalGeneratorRunStepState.InputModifiedOutputUnchanged, steps.ExecutedSteps["Calculate State"][0].Outputs[0].State);

Assert.Equal(IncrementalGeneratorRunStepState.InputUnchangedCachedOutputUsed, steps.ExecutedSteps["Generate Code"][0].Outputs[0].State);

Alternative Designs

The step info could instead be designed as a linked list of step status through the generator chain instead of an array with no well-defined ordering. This design would make it easier to associate two steps together, but provides difficulties around excluding unnamed steps. Additionally, this design may have to "leak" implementation details about how the steps are chained together to efficiently construct the list.

Risks

As the rules around when a generator considers a change a "modify" change vs a "remove/add" change are not well-defined, the determination around how they are codified in this API may risk causing breaking changes in the future if the rules change.

[dotnet-issue-labeler]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[jkoritzinsky]

@chsienki @sharwell @CyrusNajmabadi I decided to throw up an API proposal for the incremental generator testability that we chatted about a week or so ago to keep the conversation going.

cc: @agocke

[sharwell]

Should we also include information about whether the step output changed?

[jkoritzinsky]

That seems reasonable. I think adding that depends on the way the step info is modeled. If we model it as the API proposal currently has, then we definitely should. However, if we move to a model that links the steps together, then it's less compelling since the next step's state would describe the previous step's output state.

[jkoritzinsky]

I've augmented the proposal to add output state tracking.

[jkoritzinsky]

@sharwell @chsienki any more feedback before we mark this api-ready-for-review?

[sharwell]

RunGeneratorsAndGetIncrementalRunResults

I'd love to see this removed, and just get the results from GetRunResult(). We need the ability to disable this state tracking for non-test usage, but that should be easy by adding a GeneratorDriver.WithIncrementalStateTracking(bool) method.

[jkoritzinsky]

I've updated the design to add the step data to the data structure returned by GetRunResult(). I added the trigger bool to be part of the initial generator driver creation instead of being a flag that can be toggled. Would that design be amenable as well? The tracking would be turned off by default and would need to be explicitly enabled at creation.

[jkoritzinsky]

I've moved the run results to live on the GeneratorRunResult object for a given generator instead of on the GeneratorDriverRunResult aggregation object.

[jkoritzinsky]

My notes from API review:

input, output -> should each be ImmutableArray

• Represent "Remove" as "n inputs, 0 outputs"
• Represent input nodes as "0 inputs, n outputs"

input state should be scalar. Even though there may be multiple inputs, we can combine the states (internally already done)

output + state -> ImmutableArray<(,)>

Track "Remove"

Try to model step types as DU (either struct + state or inheritance model)

Look at making a graph model:

Internally is a graph, so is desirable to expose. Would also enable graphviz visualizations of generator runs.

IncrementalGeneratorRunStep? InputSource { get; }

Can make Input {get;} calculated based on InputSource and an index into source outputs.

ExecutedSteps: named nodes should be the only nodes included. ImmutableDictionary<string, ImmutableArray<RunStep>>

Give input nodes well-known names

Don't worry about name collisions. That's the user's problem to handle if they conflict names.

[333fred]

InputSources vs Inputs?
We'll go with Inputs.

Are the IncrementalGeneratorRunStepState names good?
Proposal:
New
Modified
Unchanged
Cached
Removed
Name the enum RunReason instead?

Output documents have an implicit name
"Source Output"
Well-known names go on IncrementalGeneratorRunStep
Could make an analyzer to help ensure no duplication with well-known

Should we just have a property input/output for the start and end of the graph, since they will always be there?
There are non-source outputs as well. Perhaps OutputSteps for all terminal outputs of the graph?
You can compute it from the ExecutedSteps, but that could be confusing

What happens when a name is duplicated?
You get multiple steps. Generators are separated from each other, so we don't need to worry about generators colliding.

Would WithTrackingName make the intention of the method better?
Also TrackedSteps instead of ExecutedSteps.
If we put name on each provider method, it makes naming more discoverable. On the other hand, we don't really want to encourage people to test every intermediate state and name every intermediate step. We should be encouraging just naming a few nodes.

We could add a TimeSpan to the IncrementalGeneratorStep
#55892 is also approved. Use ElapsedTime as the name instead.

We should investigate a diff mechanism for the testing SDK

The only remaining open question is around the API design for the OutputSteps property, and the naming of the well-known constants. These can be done over email.

namespace Microsoft.CodeAnalysis
{
    public static class IncrementalValueProviderExtensions
    {
+        public static IncrementalValueProvider<TSource> WithTrackingName<TSource>(this IncrementalValueProvider<TSource> source, string name);
    }
}

namespace Microsoft.CodeAnalysis
{
     public readonly struct GeneratorDriverOptions
     {
        public readonly IncrementalGeneratorOutputKind DisabledOutputs;
+       public readonly bool TrackIncrementalGeneratorSteps;

        public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs);
+       public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs, bool trackIncrementalGeneratorSteps);
     }

     public class GeneratorRunResult
     {
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedSteps { get; }
     }

+    public class IncrementalGeneratorRunStep
+    {
+        ... const strings of the well-known step names
+        public string? Name { get; }
+        public ImmutableArray<(IncrementalGeneratorRunStep Source, int OutputIndex)> Inputs { get; }
+        public ImmutableArray<(object Value, IncrementalGeneratorRunStepState State)> Outputs { get; }
+        public TimeSpan ElapsedTime { get; }
+    }

+    public enum IncrementalGeneratorRunStepState
+    {
+        New,
+        Modified,
+        Unchanged,
+        Cached,
+        Removed
+    }
}

[jkoritzinsky]

Approved with the following shape after finishing review over email:

namespace Microsoft.CodeAnalysis
{
    public static class IncrementalValueProviderExtensions
    {
+        public static IncrementalValueProvider<TSource> WithTrackingName<TSource>(this IncrementalValueProvider<TSource> source, string name);
+        public static IncrementalValuesProvider<TSource> WithTrackingName<TSource>(this IncrementalValuesProvider<TSource> source, string name);
    }

    public readonly struct GeneratorDriverOptions
    {
+       public readonly bool TrackIncrementalGeneratorSteps;

+       public GeneratorDriverOptions(IncrementalGeneratorOutputKind disabledOutputs, bool trackIncrementalGeneratorSteps);
    }

    public class GeneratorRunResult
    {
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedSteps { get; }
+       public ImmutableDictionary<string, ImmutableArray<IncrementalGeneratorRunStep>> TrackedOutputSteps { get; }
    }

+    public static class WellKnownGeneratorInputs
+    {
+        public const string Compilation = nameof(Compilation);
+     
+        public const string MetadataReferences = nameof(MetadataReferences);
+     
+        public const string AdditionalTexts = nameof(AdditionalTexts);
+     
+        public const string ParseOptions = nameof(ParseOptions);
+     
+        public const string AnalyzerConfigOptions = nameof(AnalyzerConfigOptions);
+     
+        public const string SyntaxTrees = nameof(SyntaxTrees);
+    }
 
+    public static class WellKnownGeneratorOutputs
+    {
+        public const string SourceOutput = nameof(SourceOutput);
+     
+        public const string ImplementationSourceOutput = nameof(ImplementationSourceOutput);
+    }

+    public class IncrementalGeneratorRunStep
+    {
+        public string? Name { get; }
+        public ImmutableArray<(IncrementalGeneratorRunStep Source, int OutputIndex)> Inputs { get; }
+        public ImmutableArray<(object Value, IncrementalStepRunReason Reason)> Outputs { get; }
+        public TimeSpan ElapsedTime { get; }
+    }

+    public enum IncrementalStepRunReason
+    {
+        New,
+        Modified,
+        Unchanged,
+        Cached,
+        Removed
+    }
}