FIC: Fast Immutable Collections, for Dart

Have you ever wondered if there was a way of getting rid of the plague of mutability in OOP and imperative languages? Or maybe restrict it? If you did, you're not alone.

Managing many objects each inside their respective architectural layers can be an even bigger challenge if they keep unexpectedly changing throughout their respective lifetimes. Joshua Bloch even goes as far as to state:

Classes should be immutable unless there’s a very good reason to make them mutable.

Effective Java, by Joshua Bloch.
Chapter 4: Classes and Interfaces, page 86 of the 3rd Edition.

Interestingly, if you're a Java programmer, one of the main raisons d'êtres of the language itself is to abstract away the use of pointers, which is a lower level manifestation of mutability. James Gosling, the main developer/creator of Java, deliberately set out to make it very difficult for people to deal with pointers and direct memory allocation because they were the #1 source of bugs in lower level languages like C — that's also the reason for garbage-collection's existence.

If you wanna go down the rabbit hole... this is such a major topic there are those who have dedicated decades of their careers to completely avoiding or bypassing state.

Pure functional programming languages try to respect mathematical functions, which, by definition, need to be deterministic, meaning, if you input something, the output needs to always be the same.

But how can anything be useful in the real world without any state? Well, it's a bit complicated and counter-intuitive, but there's a solution for abstracting state and still remaining pure, namely, Monads.

If you're interested, I suggest checking out Haskell, Coq, Clojure or Elm, though there's an endless sea of — largely unknown — programming languages in this area.

Dart doesn't feature native immutable collections — unlike other modern OOP languages, like Kotlin — every object has its own equals operator (==) defaulting to reference equality (identity). In the end, they are actually more or less like sealed pointers to memory locations. This means that doing something like Person("Bob") == Person("Bob") will yield false, since those objects are not the same instance or memory location. However you can override this behavior, despite it being annoying boilerplate:

You can find the whole code used in this article , or, alternatively, inside this gist. You can also test it out live through DartPad, however it uses some packages which are not available on DartPad.

          @immutable
class Person {
  final String name;

  const Person(this.name);

  @override
  bool operator ==(Object other) =>
      identical(this, other) ||
      other is Person &&
      runtimeType == other.runtimeType &&
      name == other.name;

  @override
  int get hashCode => name.hashCode;
}
        

Overriding equals (==) and hashCode is an annoyance we can't really fully get around. But for these types of atomic, entity, data or value objects, it isn't such a big deal. Most of your architectural work — and grunt work — will actually be orchestrating them, which is where FIC comes in.

In your next layer of abstraction, it is very likely you might end up with a collection of these simple objects, like a set, list or map of Person. Once you get there, you might want to deploy the same tactic you used for layer one, meaning the collections themselves will be immutable. If you don't, changes to the objects in the collections might happen without your knowledge, because there will be no programmatic way of detecting them — static analysis, for instance, won't point it out it because it is a valid feature.

Now that you've hopefully decided to also make your collection objects immutable, you're gonna have to solve the problem of internally dealing with mutable operations on top of mutable collections, such as Dart's List, Set and Map. Eventually, you might come up with the typical pattern of creating a private constructor to help manage the endless and dangerous collection copies you're gonna have to manage inside the object's state:

          @immutable
class People {
  final List<Person> _people;

  People(List<Person> people): _people = List.of(people);

  /// Since there are no references to the list once it is inside
  /// the object, there's no need for copying.
  People._(this._people);

  // An example of immutable operaton on a mutable collection
  // (List). Now imagine dozens of these operations, each needing
  // extra care from you in order to not cause any side effects.
  People add(Person person) {
    var newPeopleList = List.of(_people)..add(person);
    return People._(newPeopleList);
  } 

  // If you want to create value equality for this class, you will
  // need to override reference equality. The simplest way is to 
  // do this is to use the `collection` package.
  @override
  bool operator ==(Object other) => 
      identical(this, other) ||
      other is People &&
      runtimeType == other.runtimeType &&
      const ListEquality().equals(_people, other._people);

  @override
  int get hashCode => const ListEquality().hash(_people);

  @override
  String toString() => _people.toString();

  // Optionally, you could also write your own list equality. 
  // Something close to this:
  bool _listEquals<T>(List<T> a, List<T> b) {
    if (a == null)
      return b == null;
    if (b == null || a.length != b.length)
      return false;
    if (identical(a, b))
      return true;
    // Don't write this recursively, you might end up with 
    // space leaks. For more info on this, check out 
    // Tail Call Optimization (TCO).
    for (int index = 0; index < a.length; index += 1) {
      if (a[index] != b[index]) return false;
    }
    return true;
  }
}
        

Pay close attention! It's very important that all of the items in the supposedly immutable collection are all immutable. You absolutely cannot have items changing state in a supposedly immutable collection, all the more because static analysis will not typically warn you at any point about any of the changes.

The People._ constructor avoids wasteful recopying of the _people list through the public constructor, since you've already copied it inside the "mutation" method (People.add). But this type of pattern is clunky and needs a lot of boilerplate. Not to mention that, even though, from the outside, programmers can't change the inner list, whoever is working inside the object still has a ton of room for mistakes.

This situation is where FIC shines. Its collections are already programmatically sealed for mutable operations. There is no room for the programmer to mutate its collections, and all that while minimizing boilerplate and arguably vastly simplifying the code:

          @immutable
class PeopleWithFic {
  final IList<Person> people;

  PeopleWithFic(this.people);

  PeopleWithFic add(Person person) => 
      PeopleWithFic(people.add(person));

  @override
  bool operator ==(Object other) =>
      identical(this, other) ||
      other is People &&
      runtimeType == other.runtimeType &&
      people == other.people;

  @override
  int get hashCode => people.hashCode;
}
        

FIC uses deep equality by default, which makes dealing with collections of values much more natural and concise. And now you can treat the whole inner list as a value, people == other.people actually works safely and as most people would expect. The whole list is immutable and locked so, if you wish, you can now expose the people attribute/property publicly.

The native List in Dart features a handy constructor/factory called unmodifiable which seemingly does exactly everything you need for basic immutability. So why on Earth would anyone go on as big a rant as we did?

The 2 main reasons for not being satisfied are the insufficiency and clunkiness of that constructor/factory.

List.unmodifiable will offer immutability or at least level 1 immutability, which is actually what FIC offers as well. Take a brief look at or — that code is also available in the same Gist as the other part of the code — what's below:

          // 1) This is ok. Immutability does work in this case.
//    (This is covered in the `List.unmodifiable` docs.)
print("1) Direct Immutability\n\n");

var list = [1, 2, 3];

var unmodifiableList1 = List.unmodifiable(list);

list.add(4);

print("Original List: $list"); // [1, 2, 3]
print("Unmodifiable List 1: $unmodifiableList1"); // Still [1, 2, 3]

print("\n\n---------------------------------------------------------\n\n");

// 2) This is not ok. Immutability doens't work because the nested elements
//    are not themselves immutable.
//    (This is also covered in the `List.unmodifiable` docs.)
print("2) Nested Immutability\n\n");

var list1 = [1, 2];
var list2 = [1, 2, 3];
var nestedList = [list1, list2];

var unmodifiableList2 = List.unmodifiable(nestedList);

list1.add(10);

print("Original List 1: $list1"); // [1, 2, 10]
print("Original List 2: $list2"); // [1, 2, 3]
print("UnmodifiableList 2: $unmodifiableList2"); // [[1, 2, 10], [1, 2, 3]]
        

All of that seems enough for most people but the real problem starts when you actually want to apply changes to the collections. With that unmodifiable interface, you can only resort to copying it on the outside and then, once you're done with the dangerous mutable operations, retransform the result into a new unmodifiable object.

That's very problematic because you're copying stuff, which is very error prone and slow, and the process itself isn't really as clean as using an API that's made for this type of operation. Besides all that, using operations such as add on the unmodifiable object will only get flagged during runtime, which will make catching bugs more difficult.

Take a look at the difference:

          // 3) How would you modify, add, remove, etc. this 
//    `List.unmodifiable` object?
//    FIC makes it much simpler and less error prone...
//    And copying things to make changes will make `List.unmodifiable`
//    unbearably slow.
print("3) Clunky modifications natively | FIC makes it easy!\n\n");

var list3 = [1, 2, 3];
var unmodifiableList3 = List.unmodifiable(list3);
var ilist3 = list3.lock;

var newUnmodifiableList3 =
    List.unmodifiable(unmodifiableList3.toList()..add(4));
var newIlist3 = ilist3.add(4);

print("New UnmodifiableList 3: $newUnmodifiableList3");
print("New IList 3: $newIlist3");
        

Both built_collection and kt.dart are excellent packages, you could use either of them instead of FIC and live happily ever after. Nonetheless, when it comes to the end user, the programmer, FIC offers some valuable contributions/improvements:

• The built_collection package is based on the Builder Design Pattern, which helps in making it very fast, since operations on collections will only complete when you "rebuild" the collection, almost like lazy collections. However, going through the builder pattern as an API leads to somewhat cumbersome code, and you have to remember when to rebuild your collections. FIC offers a much more natural API with near-equal performance, something we will discuss in the next section.
• On the other side of the spectrum, kt.dart brings the easier Kotlin Collections API while making some sacrifices in performance, since it mostly copies the collection on every "mutable" operation. FIC brings in the regular, intuitive OOP collection API and plenty of functional operations, while avoiding copies and preserving performance.

FIC's whole implementation is complicated. There are a lot of details. But one of those details is worth knowing even for those who don't want to have anything to do with developing this package.

The major detail is that FIC doesn't actually copy everything whenever the user attempts a mutable operation. For example, when adding elements to a list, FIC will sort of "create an internal variable" that points to those elements. This is similar to the structure of data in many functional programming languages: in the end it becomes something like a (recursive) tree or a trie.

If the data you're trying to add is a single item or an immutable collection, FIC will create a recursive branch in its structure. So, in the end, if you're adding a huge immutable IList to another IList, the change will be virtually immediate, much faster than the native Lists actually. If you add a regular List to an IList, then FIC will need to make an immutable, safe copy though, that's why we recommend that, once you decide to go for FIC, we recommend sticking to it throughout the whole process, algorithm or application.

FIC features two other inner packages: benchmark and benchmark_app — they are now inside the example folder. The benchmark app package uses the benchmark package to run many of the typical collection operations and compare the different collection packages to each other.

Overall, FIC performs very well. In most cases, it is on par with the native collections, and sometimes it even beats them, as in the case of IList.addAll. But sometimes it is indeed slower than expected, even though not by that much — some operations on maps and sets did not end up being so optimal within FIC's design context.

• IList, an immutable list
• ISet, an immutable set
• IMap, an immutable map
• IMapOfSets, an immutable map of sets (a multimap)
• Lock and unlock extensions, so you can easily transform mutable collections into immutable ones, and vice-versa. For example: [1, 2].lock.
• Global and local configurations that alter how your immutable collections behave with respect to equality, sorting, caching, and flushing.
• Optional deep equalities and cached hash codes, which let you treat your collections as value-objects.
• Mixins for you to build your own immutable collections or objects.
• View wrappers, so that you can work with immutable collection as if they were mutable.

• ListSet, a very efficient fixed-size mutable collection which is at the same time an ordered Set and a List.

• ListMap is a mutable, fixed-sized, and ordered map which has some very efficient List methods, like sort and shuffle, and lets you efficiently read its information by index.

• General purpose extensions to the native collections: List, Set, Map. See classes FicListExtension, FicSetExtension, and FicMapExtension. For example: [1, 2, 1].removeDuplicates()

• Other extensions: IterableExtension, IteratorExtension, MapIteratorExtension, FicComparatorExtension, FicComparableExtension and FicBooleanExtension. For example: false.compareTo(true)

• Comparators and related helpers to be used with native or immutable collections, or any sort algorithms, such as compareObject, sortBy, sortLike, if0, in sort.dart.

Developing FIC took way longer than both I and Marcelo Glasberg expected. Marcelo is a much more experienced and savvy programmer and the one responsible for 90% of the design and implementation. My work was about 90% testing and trying to poke holes into his code to find bugs, and 10% giving back feedback.

So far, since publishing this package on pub.dev, we've found very few problems. And Marcelo and I have been using it internally in his own company, so we believe FIC is ready for whatever its use may be. But you never know... if you ever face any bug, please do us and the community a favor and report them here.

Regardless of each person's attributions, we both had to research and read a ton of articles to complete this project. I took the time of cataloguing all of these resources in the bibliography section of the documentation, but some of the other final sections also feature these resources indirectly.

If we ever come back to redesign this project or create something similar, we plan on diving deeper into Hash Array Mapped Tries (HAMT), which is a very important data structure for functional programming languages' implementations — you can watch Rich Hickey, the author of Clojure, explain a little bit a about this data structure here.

Follow the discussion on Reddit if you wish.