How do I find all classes that derive from specified class or interface efficiently in Incremental Generator?

[MaxSavenkov]

I have several tasks that require my incremental generator to know if a class is derived from a certain class, or, in another case, an interface. I've tried a number of approaches, but I can't see how to do this efficiently, so maybe I'm missing some idea, or I should go about the whole task differently?

Requirements:

So, let's talk about my requirements first. I have two main tasks I need to solve right now:

1. Generate some code for all classes that implement IUpdatable interface (whether directly, or by inheriting implementation from a base class)
2. Generate some code for all classes that derive from classes marked with [HashRootAttribute] attribute.

I think that both cases can be solved more efficiently by requiring the end-users to mark all derived classes with attributes, but this seems inelegant to me, and I don't want to change the existing codebase. So, I'm looking for a way to quickly check if a type derives from another type or interface.

Naive approach:

At the first glance, the solution is clear: I can walk inheritance tree using symbol.BaseType to check for inheritance from class, and use symbol.AllInterfaces to check inheritance from interface. This works - but is extremely slow, because I need to call it for every type in my project, every time something changes. To put a real number on it, this approach requires whopping 13 seconds on my codebase. It also takes no advantage of result caching in incremental generators, because there is nothing to cache.

Details: UpdatablesCodeGenerator.md (don't mind the Build method - it makes use of my own templating engine, which isn't related to the question, and please excuse the amount of debugging code - I'm in process of learning incremental source generators).

Fast, but broken approach:

It is very unfortunate that SemanticModel only contains backward links to parent types - otherwise, I could easily query a class, or an interface for a list of its descendants. So let's build inheritance graph ourselves! The important thing here is to avoid rebuilding it entirely when only a small portion of code changes.

This is the pipeline I came up with:

• CreateSyntaxProvider that filters type declarations and transforms them into (INamedTypeSymbol, BaseListSyntax) pairs, where the first component is symbol for type, and the second is a list of its bases.
• Comparer that compares fully qualified name for symbol, and SyntaxTree equivalence for BaseListSyntax
• Collect
• Select(BuildTree), see below
• Comparer that checks if inheritance tree changed

BuildTree generates a tree, by creating a Dictionary<INamedTypeSymbol, TreeNode>, and each TreeNode contains INamedTypeSymbol, list of child TreeNodes and integer version (to allow me to track type deletion).

Here, the first problem comes: I desperately want to cache the tree, and only update parts of it that actually change, but ImmutableValueProvider/ImmutableValuesProvider do not provide me with a way to do it, unless I somehow map the tree onto an ImmutableArray. So instead, I implemented my own caching, by saving the tree inside generator instance. This looks very, very dangerous - I have no idea how generator instances are created and disposed, but I see no other way. Then, since I have the previous copy of the tree, I can check if source data changed, e.g. if the tree has TreeNode for symbol, and that it has all the same bases.

Anyway, I checked this approach on my project, and it works - the first tree rebuild takes about 3 seconds, and small changes to it take about 40-100ms. Fast!

The second problem is that this approach is fundamentally broken: it tracks changes only to syntax, by comparing BaseListSyntaxes. Therefore, if list of bases remain the same, but its meanings change, the generator will not detect it. It can happen if a list of usings change, or if I reference a different Assembly that has a type with the same name, or if aliases change. I guess in some limited circumstances this drawbacks could be ignored or worked around (e.g. by making Select(BuildTree) step depend on list of referenced assemblies and on usings, somehow).

Details: InheritanceTreeBasedGenerator.md

Slightly better, but much slower approach:

I can fix the second problem if our Transform step would take semantic meaning of symbols into account. I can do this by making it return (INamedTypeSymbol, List<INamedTypeSymbol>), where the second component is the list of bases types. The slow way to do this is to access BaseType and Interfaces properties of every type declaration, but this gets us back to 10+ seconds - Interfaces accessor is VERY slow.

Instead, I can iterate over type declaration's BaseListSyntax.Types, and call SyntaxModel.GetTypeInfo for every type in list. This is much faster, but still too slow - now, every change only results in 3 seconds, most of which are spent inside GetTypeInfo. And it still doesn't solve the first problem (caching inheritance tree somewhere).

Details: InheritanceTreeBasedGeneratorSym.md

The question:

So. It seems to me that the task - finding all descendants of a type - should be a relatively common one, yet I can't find any solutions to it on the net, aside from naive ones, which don't work well on large codebases. What am I missing? Is there a way to do this efficiently, or should I bite the bullet and just mark every class of interest with an attribute (maybe with an Analyzer that checks if a class derived from a marked class is not marked and adds a diagnostic, to avoid errors)?

[CyrusNajmabadi]

What am I missing? Is there a way to do this efficiently,

There is no way to do this efficiently

or should I bite the bullet and just mark every class of interest with an attribute

Yes. Do this.

(maybe with an Analyzer that checks if a class derived from a marked class is not marked and adds a diagnostic, to avoid errors)?

Yes. Do this.

[CyrusNajmabadi]

It is very unfortunate that SemanticModel only contains backward links to parent types

It's also intentional. We have no magical easy to do better here either. Any sort of edit could entirely change the inheritance tree, and we wouldn't know without doing all the analysis work for each type.

So SemanticModel (and symbols), contain the operations that can be done cheaply. Reverse transitive maps will be expensive and should be avoided as part of any design.