Struggles with the Dart type system

How it began: dart_apitool bug fix

It all started with a bug fix in dart_apitool.
The bug was that dart_apitool detected a breaking change on any parameter type change. Most of the time this is correct but consider this change:

/// version 1
void someMethod(String someParameter);

/// version 2a
void someMethod(String? someParameter);

/// version 2b
void someMethod(Object someParameter);

Here the type of the parameter gets changed but in a non-breaking way.
Any already existing call to someMethod will work with version 2a and version 2b.
The reason for this is that widening the type makes the old type part of the supported type space for that parameter.
Of course this is only valid for types passed in (which is the case for this bug as it describes method parameters).

So the goal was clear: dart_apitool has to check if the old type is assignable to the new type to decide if that change is a breaking change or not.

Dart type system

The Dart type system is not as strict and tight as you might know from languages like C# or Java. It is not as loose as in TypeScript also. It is somewhere between those two extremes leaning a bit more to the C# / Java side.
But there are places where you can see that more loose approach.
One such place that got in my way implementing the mentioned fix for dart_apitool is the concept of “type IDs” (or more the lack of such a concept in Dart).

For that we have to have a short look into languages like C#.

In C# every type has a reproducible, unique identifier.
It consists of the type name itself and its namespace. The combination of namespace and the type makes a unique identifier for a type that ID valid and stable in any context. A global::System.String is always a global::System.String. You can also alias namespaces in C# but the type ID in the back stays the same.

In Dart there is no comparable mechanism. Dart has the concept of “libraries” but they really don’t mean that much.
You can have the same type name in different dart files and depending on what you import you can use one of them. If you need to use both then this is the consumers problem and has to be solved by specifying a prefix on library import.
This prefix is only valid inside that one importing dart file. So a Dart prefix is like a C# alias.
This means that there is no way of producing a unique “type ID” to refer to a type in Dart that is not directly bound to the source file that contains the type.
What makes the whole matter even more complicated is that you can export types from other libraries in your library making that type part of your library.

What does dart_apitool need?

In order to detect if a type (the old one) is assignable to another type (the new one) dart_apitool needs to

1. have access to the type system to do those checks
2. use the types from different analysis runs (old and new) and relate them

During an analysis run there is a type ID (an integer) that is stable and can be used to refer to exactly the same type. The problem? This ID is only valid for that analysis run.
Dart_apitool can’t use that ID to relate to the old type in the new analysis context.

So I needed to come up with an approximation to something similar to a “type ID” in Dart.

The path

Collect the type system

The easiest part was to extend the analysis run to collect a “type system”. Basically every type that gets encountered gets stored in a TypeSystem class together with its ID and base types.
This allows dart_apitool to relate two types and test if Type A is assignable by Type B.
The main problem is: How to find the type of analysis run 1 in the context of analysis run 2.

Type name

The type name is a good candidate for finding a type in the collected type system. Most of the time this is enough. The problem starts if a type name is used multiple times and therefore makes resolving that type from only its name ambiguous.
For those occasions the “type ID” needs to be more specific so that the referenced type can be resolved.

First approach: namespace

Coming from a C# background the first reaction was: Namespaces.
It took me quite some time to realize that C# namespaces and Dart import prefixes are completely different concepts and that a Dart prefix is a consumer side decision that has nothing to do with the type itself and therefore can’t be used in a “type ID”.

Second approach: libraries

My second approach was to use the libraries. The problem is - as stated before - that libraries are a very loose concept in Dart. Most of the time the library you get from the analysis run is just the dart file that defines the type (for local references).
This would be fine if we would not have to deal with the “path dependency” special case.
Dart_apitool supports a mode where two packages from a mono repo relate to each other via path dependencies but the released variant that gets compared to is an isolated package referencing the other package via a normal pub reference.
This means that in order to get a stable library as a “type ID” all the places in dart_apitool that need to calculate that “type ID” need a way to calculate the package-relative path for a library.
And even then this approach is not stable as Dart types can be exported in different libraries (or dart files) and therefore end up with different libraries for the same type.

I implemented that solution, and it worked well for the test cases I had, but I was not happy with it.
It doesn’t feel right that a file-level refactoring breaks that “type ID” approach.
So I decided to use the library part as a “type ID” only if there are two occasions of the same type name. Otherwise, the name is enough.

The instability of that approach stuck with me and didn’t let me rest, so I had to think more to find a better solution.

Third approach: package name and library

The third and current approach was to use the package name as a second “type ID” level and use the library only as a fallback.
The reasoning behind that is that in most cases the name and the package should be unique. For the remaining cases we use the library and that case is so rare that living with the problem of instability for this small set of occasions is fine.
Dart_apitool now tries to find the type in the TypeSystem class via its name and package.
If this yields more than one hit then the library is used to find the exact matching type.
If this library lookup fails then the “is assignable” question gets answered with “no” leading to a potentially wrong breaking change detection. As the condition for this to happen is a refactoring of the code the assumption is that it is very likely that in that case we already have breaking changes (entry point changed for example) and having an additional wrong breaking change detected doesn’t hurt too much.
In 99.9% of the cases this approach should be totally fine.

So the TypeIdentifier class that I used looks like this (simplified):

class TypeIdentifier {
    /// the name of the type
    final String typeName,
    
    /// the name of the package defining that type
    final String packageName,
    
    /// the library path inside the package defining that type
    final String packageRelativeLibraryPath,

    /// returns a String containing the package name and the type name
    String get packageAndTypeName => '$packageName:$typeName';

    TypeIdentifier({
        required this.typeName,
        required this.packageName,
        required this.packageRelativeLibraryPath,
    });

    @override
    String toString() {
    return '$packageName:$typeName ($packageRelativeLibraryPath)';
    }

// ... additional tools to get the TypeIdentifier from a name and a library path
}

The TypeHierarchy class then tries to match packageAndTypeName. If this yields only one hit, it continues and only if it gets more than one hit packageRelativeLibraryPath is used to further search for the correct TypeIdentifier.

Conclusion

The Dart type system is not as strict as in other languages making it harder for tools to reason about the code.
Of course: dart_apitool’s requirements are quite special as it has to compare different variants of the same code, and therefore it needs to correlate between those two environments making generated type IDs useless.

I’m quite happy with the approach I found, and I think that this will be enough for almost all use cases.

If you have a better idea for computing a unique type ID in Dart then let me know!
Any hint for making this more robust is very welcome!