invariant_collection

Description:

invariant collection

Invariant Collections #
The repository invariant_collection provides the libraries
invariant_iterable.dart, invariant_list.dart, invariant_set.dart,
invariant_map.dart, and invariant_collection.dart (exporting all the
others). Future versions of this repository may provide similar libraries
for other kinds of collections from 'dart:core'.
invariant_list.dart provides an extension type IList<E> which is
intended to be used as a replacement for types of the form List<E> (where
List is the built-in class of that name). IList<E> is invariant in its
type parameter, whereas List<E> uses dynamically checked covariance. An
easy way to obtain an expression of type IList<T> from an expression e
of type List<T> is to use e.iList.
All other kinds of collections in this package are similar. They use the
same naming scheme and provide the same kind of typing and semantic
properties.
Motivation: Type safety #
The purpose of this package is to improve the static type safety of Dart
programs when they are using collections (List, Map and so on). Without
this package, Dart collection classes (and indeed all Dart classes) are
covariant in their type parameters. For example List<int> is a subtype of
List<num> because int is a subtype of num. This is very convenient,
and it is both natural and safe to treat a List<int> as if it were a
List<num> in many situations.
However, it isn't safe in all situations. In other words, dynamically
checked covariance is not statically type safe: We can have a program with
no compile-time errors which will incur a type error at run time. Example:
void main() {
List<num> xs = <int>[1];
xs.add(1.5); // No compile-time error, yet throws at run time.
}
copied to clipboard
This package provides several extension type declarations which may be used
in order to adapt the static analysis of collection types such that they
are invariant in their type parameters. With that treatment, the above kind
of run-time error does not occur. This is because the step where covariance
is introduced becomes a compile-time error, and we can't have run-time
failures caused by dynamically checked covariance in a program execution
where said covariance hasn't been introduced. Using this approach, the
example above looks as follows:
import 'package:invariant_collection/invariant_list.dart';

void main() {
IList<num> xs = <int>[1].iList; // Compile-time error.
xs.add(1.5); // Irrelevant, `xs` is already an error.
}
copied to clipboard
The other side of the coin is that invariance is less flexible, which means
that it is a non-trivial trade-off: Do you want to continue to use this
collection in the covariant way which is convenient and natural, but which
may give rise to run-time type errors? Or are you ready to take the more
strict invariant route?
In general, collections should be typed invariantly when they are being
mutated (in particular, when new elements are added), because methods like
List.add and Map.addAll and operator []= are unsafe when covariance
is present. Collections that are treated as read-only can be allowed to use
covariance because that is generally safe.
The precise borderline between safe and unsafe relies on the detailed
structure of the types in the member signatures, and on whether or not any
covariant type variables occur in a non-covariant position, but this
document is not the place to unfold all the details.
Preserving a property, not necessarily checking it at each step #
Let's pretend that x should be an even number at all times. Here's a
snippet of code where we can think about this claim and consider whether
it's maintained or violated, and where.
class A {
int next(int i) => i * 2; // Ensure evenness.
}

// This class could be declared in some other library,
// we may not know that it exists.
class B implements A {
int next(int i) => 13; // Destroys evenness!
}

void main() {
var x = 2; // True at first.
A a = ...; // Some complex expression.
x += 14; // Preserves evenness.
x = a.next(x); // OK?
x -= 14; // Preserves evenness (if we still have it).
if (!x.isEven) throw StateError("x is not even!");
}
copied to clipboard
Just like a proof by induction, we can check that the initial state
(at the declaration and initialization of x) satisfies the
requirement, and then check that every subsequent step preserves the
requirement. An inspection of A.next(_) confirms that x remains
even, which is also true for x += 14 and x -= 14.
Hence, a (superficial) static analysis seems to confirm that the evenness
property is preserved all the way.
However, if the value of a is actually an instance of B then
a.next(x) will return a value which isn't even, and then we may stay off
track (such that the evenness requirement is violated) for any number of
steps.
Finally, we can directly check at any particular point in time whether the
evenness requirement is satisfied (isEven), and otherwise take some
recovery or panic steps in response to that failure, e.g., throwing a state
error.
The point is that we can ensure that a property holds if it holds "at the
beginning", and each step that we may execute is guaranteed to preserve
that property.
If some steps are not guaranteed to preserve the property then we can still
ensure that the property holds by checking the property from scratch after
each unsafe step. Assuming that isEven could be a really expensive
computation, we'd very much like to perform these checks only when
necessary; we might even tolerate that the property is violated for some
limited number of steps (so we check after x -= 14 even though that's a
safe step, because we must check at some point after x = a.next(x)).
It is crucial that preservation of a property can be much cheaper than a
from-scratch check at every step. In particular, x.isEven is a run-time
computation, but with x += 14 it can be proven at compile time that it
will preserve the evenness of x, and the cost associated with this
knowledge is zero at run time.
The structure of the guarantees provided by invariant collection types like
IList is very similar. It's all about proving at compile time that the
invariance property is preserved, for all operations that are checked
statically. Some steps are dynamic (e.g., type casts), and they must be
followed up by a from-scratch check (isInvariant).
Here's how it plays out in practice. First consider the initial state.
There's no way we can prevent at compile time that an expression with
static type List<num> has run-time type List<int>, that's just a
property of the Dart List class, and we can't change that. Also, it is
not possible to detect this situation at compile time, due to the
underlying undecidability.
This means that it is always possible to create an IList<num> whose
actual type argument is not num but some subtype of num, even though
the static types imply that no such covariance exists.
void main() {
List<num> xs = <int>[1]; // We can't turn this into an error.
var ys = IList<num>(xs); // Statically OK.
print(ys.isInvariant); // 'false'!
}
copied to clipboard
It is possible to perform a from-scratch check by means of
isInvariant. Another way to establish a safe initial state is to use any
IList constructor that creates a new list, e.g.,
IList<num>.filled(10, 0.1).
Note that the IList constructor IList(_) will throw if assertions
are enabled and the actual argument has a covariant type, because it
asserts that the given list isInvariant.
Now let's assume that we have established the desired invariance property
initially. Subsequent steps may then be statically known to preserve the
property, or they might be unsafe, and we can deal with that just like
'evenness':
import 'package:invariant_collection/invariant_list.dart';

class A {
IList<num> next(IList<num> xs) => xs.take(0).toList().iList;
}

class B implements A {
IList<num> next(IList<num> xs) => (<int>[] as List<num>).iList;
}

void main() {
var xs = <num>[1, 2, 3.5].iList; // Invariant at first.
A a = ...; // Some complex expression.
xs.add(14); // Same `xs`, preserves invariance.
xs = a.next(xs); // OK?
xs.remove(14); // Same `xs`, preserves invariance (if we have it).
if (!xs.isInvariant) throw StateError("xs is not invariant!");
}
copied to clipboard
Again, if a is an instance of B then the invariance property is
violated at xs = a.next(xs), and it takes a from-scratch check
(isInvariant) to determine whether or not we still have it.
Well, the invariant is actually violated in the body of B.next, because
we're using iList on an object whose static type is List<num>, whereas
the run-time type has the type argument int. So we're again checking a
few steps after the problem actually arises, which is enough as long as we
don't forget to perform the check entirely. Of course, B.next is a bug,
and it should be fixed.
The step where an IList<T> is assigned to a variable of type IList<T>
or IIterable<T> is safe (it preserves the invariance). This includes the
step where an IList<num> is returned from B.next, and the value
returned by a.next(xs) in main is assigned to xs. However, this
preserves the invariance, but doesn't check the invariance from scratch,
and this means that we need to verify the invariance after the unsafe step
in the body, which is the cast.
An important special case arises when the invariant is never in doubt: If
the initial state is correct (say, a variable IList<T> x satisfies the
invariance requirement), and no changes are made to the identity of the
object (say, it's a final variable), then the invariance requirement is
trivially guaranteed to hold at all times. Similarly if a variable is only
assigned from sources that are known to satisfy the requirement. And so on.
The point is that preservation of invariance is ensured for most
computational steps, at a zero cost at run time, but it is necessary to
keep an eye on certain steps that are unsafe. The underlying assumption for
invariant_collection is that this is a worthwhile improvement over the
situation where every collection can be covariantly typed in all
situations.
Migration #
Note that IList<T> is a subtype of List<T> for all T. This means that
a given library L can be modified to use IList<T> rather than List<T>
as return types (especially, for lists that are subject to mutation).
Internal computations (using local variables, private methods) can use
IList<T> rather than List<T> everywhere (again, especially for lists
that are mutated). In code that interacts with other libraries, an
IList<T> can be passed when a List<S> is expected whenever T is a
subtype of S. This could occur, say, because the callee hasn't been
updated yet, or because they don't plan to mutate that list. Next, an
IList<T> can of course also be passed to other libraries when an
IList<T> is expected, which would be the case when multiple libraries
have switched to use invariant_collection (and they are now helping each
other to preserve the invariance property for lists that need it).
If a List<T> is available in L, and it should be passed as an actual
argument to a method in some other library which is expecting an
IList<T>, then we will get a compile-time error (List<T> is not
assignable to IList<T>). This is a good kind of breakage because it
most likely indicates that this other library intends to mutate the list,
and hence they need to receive the list with a static type which is
invariant. We may then check that the given list is indeed invariant, and
give it the type IList<T>, and pass it—safely.