The Road to Immutability

We discuss the Java language, version 8 and higher. We have already indicated that we believe that Java offers too much freedom to programmers. In this section, we impose some limits that are not critical to the substance of the discussion, but facilitate reasoning. Think of them as low-hanging fruit programming guidelines:

The maddi code analyzer warns for many other doubtful practices, as detailed in the user manual.

In this document we will add many annotations to the code fragments shown. We are acutely aware annotations may clutter the code and can make it less readable. Some IDEs, however, like JetBrains' IntelliJ IDEA, have extensive support to make working with annotations visually pleasing.

The maddi code analyzer computes almost all the annotations that we add to the code fragments in this document. The complementary IDE plugin uses them to color code types, methods and fields. Except when the annotations act as a contract, in interfaces, they do not have to be present in your code.

Explicitly adding the annotations to classes can be helpful during software development, however. Say you intend for a class to be immutable, then you can add the corresponding annotation to the type. Each time the code analyzer runs, and the computation finds the type is not immutable, it will raise an error.

Explicit annotations also act as a safe-guard against the changing of semantics by overriding methods. Making the method final, or the type final, merely prohibits overriding, which is typically too strong a mechanism.

The final situation where explicit annotations in the code are important, is for the development of the analyzer. We add them to the code as a means of verification: the analyzer will check if it generates the same annotation at that location.

We will try to make our case using two examples. First, consider Counter and Counters:

The constructor Counters copies every counter in the counterCollection into a new, unmodifiable map. Clearly, external modifications to the collection itself (i.e., adding, removing a new Counter element) made after creation of the Counters object, will have no effect on the object graph of the field counters:

However, consider the following statements executed after creating a Counters object:

An external modification (c.increment()) to an object presented to the constructor as part of the collection has an effect on the object graph of the fields, to the extent that an identical, non-modifying method call returns a different value!

We must conclude that the parameter of the constructor counterCollection is linked to the field counters, even if modifications at the collection level have no effect.

Now we put the Counters example in contrast with the Levels example, where the modifying method increment() has been removed from Counter to obtain Level:

We propose to split the object graph of a field into two parts: its accessible part, and its hidden part.

A type which is transparent can be replaced by an unbound type parameter, which is why we will use the term hidden from now on. Note: if it were not for transparent types, which are clearly accessible but are never accessed, we would not define something "accessible" in terms of "accessed". But we can argue that having transparent types in the code is poor programming practice (to the extent that the analyzer can be configured to raise an error when they are present), and "hidden" is the complement of "accessible".

When a type C extends from a parent type P, we see an instance of C as being composed of two parts: the methods and fields of P, augmented by the methods and fields of C. Whilst the part of the parent, P, can be accessible, the part of the child C may remain hidden. Similarly, when T implements the interface I, but the interface is used as the formal type, then the methods and fields of I are accessible, but the ones augmented by the implementation T remain hidden. In the example of Level, implementations or extensions may be modifiable (such as Counter), but when presented with Level only, there are no modifications to be made. Inside Levels, where we are limited to Level, no such extensions are accessible.

Armed with this definition, we split the combined object graph of the fields of a type into the accessible content, and the hidden content:

Note that we must make this distinction, because every interface is meant to be implemented, and every type, unless explicitly marked final or sealed can be extended in Java. These extensions could be completely outside the control of the current implementation (even though we can use the analyzer to constrain them).

In the first example of this section, LinkExample1, objects of the type X form the hidden content of LinkExample1, while the Set instance is the accessible content. In Counters, Map, String and Counter are accessible, but whatever augments Counter by implementing it remains hidden. Exactly the same applies to Levels: Map, String and Level are accessible, but whatever augments Level by implementing it remains hidden.

One of the central tenets of our definition of immutability will be that

Recall that by definition, any modifications to the hidden content must be external to the type.

We end this section by defining what linking means with respect to the accessible and hidden content of the fields. The definition of linking given in the previous section is absolute, in the sense that it covers the whole object graph of the objects being linked.

When a parameter is linked to a field, we could try to find out if the modifications affect the accessible content, given that we state that modifications to the hidden content are outside the scope of the type anyway. In other words, we could distinguish between different forms of linking:

In other words, a parameter or method return value is dependent when a modification on the argument or returned value has the possibility to cause a modification in the accessible part of the fields.

Linking between parameters or return value and fields which does not involve the accessible part of the fields, is called independence. We will elaborate in More on hidden content. In the following sections, we will often use the term 'independent' when we mean 'not-dependent', i.e., when there is no linking or only linking to the hidden part of the object graph of the fields.

In terms of annotations, dependence will be the default state for objects of types where dependence is possible. We will not annotate it most of the time; if we do, we use the annotation @Independent(absent=true). The annotation @Independent on parameters and methods will be used for absence of linking. When a type is deeply immutable, @Independent is the default state, and therefore it will be omitted. We use @Independent(hc=true) to stress the linking to the hidden part.

Now, all pieces of the puzzle are available to introduce immutability of types.

First, what do we want intuitively? A useful form of immutability, less strong than deeply immutable, but stronger than final fields for many situations. We propose the following description:

Technically, immutability is much harder to define than final fields. We identify three rules, on top of the obvious final fields requirement. The first one prevents the type from making changes to its own fields:

Our friend the Pair satisfies this first rule:

Note that since K and V are unbound generic types, it is not even possible to modify their content from inside Pair, since there are no modifying methods one can call on unbound types. The types K and V are hidden in Pair; it does not have any accessible content.

How does it fit the intuitive rule for immutability? The type Pair holds two objects. The type does not change their content, nor will it exchange these two objects for others, or allow others to do so. It is clear the users of Pair may be able to change the content of the objects they put in the Pair. Summarizing: Pair fits the intuitive definition nicely.

Here is an example which shows the necessity of the first rule more explicitly:

The fields point1 and point2 are effectively final. Without the translation method, the fields would be @NotModified as well. The translation method modifies the fields' content, preventing the type from becoming immutable.

From the restriction of rule 1, that all its fields should remain unmodified, it follows that, excluding external changes, every method call on an immutable container object with the same arguments will render the same result. We note that this statement cannot be bypassed by using static state, i.e., state specific to the type rather than the object. The definitions make no distinction between static and instance fields.

To obtain a useful definition of immutability, one which is not too strict yet follows our intuitive requirements, we should allow modifiable fields, if they are properly shielded from the modifications they intrinsically allow. We will introduce two additional rules to constrain the modifications of this modifiable data. Together with the first rule, and building on final fields, we define:

Rule 2 is there to ensure that the modifiable fields of the object cannot be modified externally by means of direct field access to the non-private fields. Rule 3 ensures that the modifiable fields of the object cannot be modified externally by obtaining or sharing references to the fields via a parameter or return value.

Types which are immutable will be marked @Immutable . When they are containers too, which should be the large majority, we use @ImmutableContainer as a shorthand for the combination of the two annotations.

Note that:

Let us go to examples immediately.

After creation, external changes to the source array ts are effectively modifications to the field data. This construct fails rule 3, as the parameter ts is dependent. The field is a modifiable data structure, and must be shielded from external modifications.

Note the use of @Independent(hc=true) annotation on the return value of stream(), to indicate that modifications to the hidden content are possible on objects obtained from the stream.

Users of this type can modify the content of the array using direct field access! This construct fails rule 2, which applies for the same reasons as in the previous example.

The independence rule enforces the type to have its own modifiable structure, rather than someone else’s. Here is the same group of examples, now with JDK Collections:

The lack of independence of the constructor violates rule 3 in the first example.

Here, the data field is public, which allows for external modification.

Finally, we have an immutable type. The next one is immutable as well:

The section on Dynamic type annotations will explain how the @Immutable annotation travels to the field data.

The independence rule, rule 3, is there to ensure that the type does not expose its modifiable data through parameters and return types:

Note that by decomposing rules 0 and 1, we observe that requiring all fields to be @Final and @NotModified is equivalent to requiring that all non-private fields have the final modifier, and that methods that are not part of the construction phase, are @NotModified. The final example shows a type which violates this rule 1, because a modifying method has been added:

Deriving from an immutable class is the most normal situation: since java.lang.Object is an immutable container, every class will do so. Clearly, the property is not inherited.

Most importantly, in terms of inheritance, is that the analyzer prohibits changing the modification status of methods from non-modifying to modifying in a derived type. This means, for example, that the analyzer will block a modifying equals() or toString() method, in any class. Similarly, no implementation of java.util.Collection.size() will be allowed to be modifying.

The guiding principle here is that of consistency of expectation: software developers are expecting that equals is non-modifying. They know that a setter will make an assignment, but they’ll expect a getter to simply return a value. No getter should ever be modifying.

The other direction is more interesting, while equally simple to explain: deriving from a parent class cannot increase the immutability level. A method overriding one marked @Modified does not have to be modifying, but it is not allowed to be explicitly marked @NotModified:

Following the same principles, we observe that types deriving from a @Container super-type need not be a container themselves. So while we may state that Collection is a container, it is perfectly possible to implement a collection which has public methods which modify their parameters, as long as the methods inherited from Collection do not modify their parameters, and the implementation does not modify the objects linked to the parameters of the Collection methods.

Note that sealed types reject the 'you can always extend' assumptions of Java types. In this case, all subtypes are known, and visible. The single practical consequence is that if the parent type is abstract, its annotations need not be contracted: they can be computed because all implementations are available to the analyzer.

Type parameters are either unbound, in which case they can represent any type, or they explicitly extend a given type. Because the unbound case is simply a way of saying that the type parameter extends java.lang.Object, we can say that all type parameters extend a certain type, say T extends E.

The analyzer simply treats the parameterized type T as if it were the type E. In the case of an unbound parameter type, only the public methods of java.lang.Object are accessible. By definition, the type belongs to the hidden content, as defined in Accessible and hidden content.

The analyzer recognizes types that can be replaced by an unbound parameter type, when they are used transparently, and therefore belong to the hidden content: no methods are called on it, save the ones from java.lang.Object; none of its fields are accessed, and it is not used as an argument to parameters where anything more specific than java.lang.Object is required. It will issue a warning, and internally treat the type as an unbound parameter type, and hence @ImmutableContainer , even if the type is obviously modifiable.

The following trivial example should clarify:

Nowhere in OddPair do we make actual use of the fact that set is of type Set, or sb is of type StringBuilder. The analyzer encourages you to replace Set by some unbound parameter type, say K, and StringBuilder by some other, say V. The result is, of course, the type Pair as defined earlier.

Making a concrete choice for a type parameter may have an effect on the immutability status, as will be explained in More on hidden content. Some examples are easy to see: any @FinalFields type whose fields consist only of types of unbound type parameter, will become immutable when the unbound type parameters are substituted for immutable types. Any immutable type whose hidden content consists only of types of unbound type parameter, will become deeply immutable (i.e., devoid of hidden content) when the unbound type parameters are substituted for deeply immutable types. The Pair mentioned before is a case in point, and an example for both rules: Pair<Integer, Long> is deeply immutable.

Because java.lang.Object is an immutable container, trivial extensions are, too:

Things only become interesting when methods enter the picture. Annotation-wise, we stipulate that

Furthermore, we will also impose special variants of the rules for immutability of an abstract type T, to be obeyed by the abstract methods:

The consequence of these choices is that implementations and extensions of abstract and non-abstract types will have the opportunity to have the same immutability properties. This allows us, e.g., to treat any implementation of Comparable, defined as:

as an immutable type when the only method we can access is compareTo.

As far as the modification status of the parameters of abstract methods is concerned, we also start off with @Modified :

While it is possible to compute the immutability and container status of interface types, using the rules presented above, it often makes more practical sense to use the annotations as contracts: they may save a lot of annotation work on the abstract methods in the interface. We repeat that no implementation of an immutable interface is guaranteed to be immutable itself; nor does this guarantee hold for the container property unless no new non-private methods have been added.

We continue this section with some examples which will form the backbone of the examples in More on hidden content.

If semantically used correctly, types implementing the HasSize interface expose a single numeric aspect of their content:

We extend to:

The Consumer interface is defined and annotated as:

Implementations of the accept method are allowed to be modifying (even though in NonEmptyImmutableList.visit we decide to ignore this modification!). They are also allowed to modify their parameter, as we will demonstrate shortly.

Let’s downgrade from @ImmutableContainer to @FinalFields @Container by adding a modifying method:

Note that the method setFirst promises to keep its parameter unmodified thanks to the @Container annotation on the type. The @Independent(hc=true) annotation states that arguments to setFirst will end up in the hidden content of the NonEmptyList. Implementations can even lose @FinalFields :

Here is a (slightly more convoluted) implementation that remains @FinalFields and @Container :

Obviously, an @ImmutableContainer implementation is not possible: the immutability status of an extension (OneWithOne, One) cannot be better than that of the type it is extending from (NonEmptyList).

We end the section by showing how concrete implementations of the accept method in Consumer can make modifications. First, modifications to the parameter:

The last statement is maybe more easily seen as:

Second, modifications to the fields of the type:

Up to now, we have made no distinction between static fields and instance fields: modifications are modifications. Inside a primary type, we will stick to this rule. In the following example, each call to getK increments a counter, which is a modifying operation because the type owns the counter:

We can explicitly ignore modifications with the contracted @IgnoreModifications annotation, which may make sense from a semantic point of view:

Note that when the modification takes place inside the constructor, it is still not ignored, because for static fields, static code blocks act as the constructor:

Only modifications in a static code block are ignored:

Nevertheless, we introduce the following rule which does distinguish between modifications on static and instance types:

This is still consistent with the rules of immutable types, which only look at the fields and assume that when methods do not modify the fields, they are actually non-modifying. Without an @IgnoreModifications annotation on the field System.out (which we would typically add), printing to the console results in

We leave it up to the programmer or designer to determine whether static calls deserve a @StaticSideEffects warning, or not. In almost all instances, we prefer a singleton instance (see Singleton classes) over a class with modifying static methods. In singletons the normal modification rules apply, unless @IgnoreModifications decorates the static field giving access to the singleton.

The @IgnoreModifications annotation and hidden content (More on hidden content) are two faces of a single idea. Recall why the hidden content of a type never threatens its immutability: by parametricity, an @Immutable(hc=true) type holds only the abstract interface of its hidden content — the type parameter T, or an unbounded generic — and so it cannot express an operation that reaches out of the hidden content into its own accessible state. A client is free to mutate the hidden content (list.get(i).mutate()); the container stays @Immutable(hc=true) . Confinement is guaranteed by erasure.

An @IgnoreModifications field holds a concrete type, which can express such reaching-out operations. The annotation asserts, by hand, the very property erasure would otherwise have derived: modifications to this field’s object are not part of my immutability contract. That is the defining predicate of hidden content.

The two are interchangeable in the immutability lattice; they differ only in the provenance of the "not my concern" judgement — derived (always sound) versus asserted — and that difference is a proof obligation, not an arithmetic one. Which brings us to the guard.

Quoting from the JDK 8 documentation, value-based classes are

Item 1 requires final fields but does not specify any of the restrictions we require for immutability. Item 2 implies that should equals, hashCode or toString make a modification to the object, its state changes, which would then change the object with respect to other objects. We could conclude that these three methods cannot be modifying.

Loosely speaking, objects of a value-based class can be identified by the values of their fields. Immutability is not a requirement to be a value-based class. However, we expect many immutable types will become value-classes. Revisiting the example from the previous section, we can construct a counter-example:

The equals method violates item 2 of the value-class definition, maybe not to the letter but at least in its spirit: the field k is arguably the most important field, and its value is not taken into account when computing equality.

When it is clear a method returns an immutable set, but the formal type is java.util.Set, the @Immutable annotation can 'travel':

Whilst Set in general is not @Immutable , the data field itself is.

The computations that the analyzer needs to track dynamic type annotations, are similar to those it needs to compute eventual immutability. We introduce them in the next chapter.

We start with the well-established builder pattern.

If your code can live with two different types (Polygon.Builder, Polygon) to represent polygons in their different stages (mutable, immutable), the builder paradigm is great. If, on the other hand, you want to hold polygons in a type that spans both stages of the polygon lifecycle, it becomes difficult to do this with an eye on immutability. One solution is the use of an interface that is implemented both by the builder and the immutable type.

The FirstThen type can also assist in this situation: it holds an initial object (the first) until a state change occurs, and it is forced to hold a second object (the then). Once it is in the final state, it cannot change anymore. It is eventually immutable:

We propose a system of eventual immutability based on a single transition of state inside an object.

The analyzer has no problem detecting the presence of preconditions, and observing that one method changes its own precondition. The rules, however, are sufficiently general to support arbitrary preconditions, as shown in the following variant. This example does not require an additional field, but relies on the empty/not-empty state change:

Let us summarize the annotations:

In each of these annotations, the actual value of the …​ in the after= or before= parameters is the name of the field.

In case there are multiple fields involved, their names are represented in a comma-separated fashion.

The @Mark and @Only annotations can also be assigned to parameters, in the event that marked methods are called on a parameter of eventually immutable type. Consider the following utility method for EventuallyFinal, frequently used in the analyzer’s own code:

Here, the setFinal method’s @Mark annotation travels to the parameter, where it is applied to the argument each time the static method is applied.

The support types detailed in Support classes can be used as building blocks to make ever more complex eventually immutable classes. Effectively final fields of eventually immutable type will at some point hold objects that are in their final or after state, in which case they act as immutable fields.

The analyzer itself consists of many eventually immutable classes; we show some examples in Support classes in the analyzer.

A method can return an eventually immutable object, guaranteed to be in its initial or before state. This can be annotated with @BeforeMark . Employing SimpleImmutableSet1 from the example above,

Similarly, the analyzer can compute a parameter to be @BeforeMark , when in the method, at least one before-mark method is called on the parameter.

Finally, a field can even be @BeforeMark , when it is created or arrives in the type as @BeforeMark , and stays in this state. This situation must occur in a type with a @Finalizer , as explained in Finalizers.

When a type is eventually @FinalFields , should the field(s) of the state transition be marked @Final ? Similarly, when a type is eventually immutable, should the analyzer mark the initially mutable or assignable fields @Modified or @NotModified?

Basically, we propose to mark the end state, qualifying with the parameter after:

|== | property | not present | eventually | effectively | finality of field | no annotation, or @Final(absent=true) | @Final(after="mark") | @Final | non-modification of field | @Modified | @NotModified(after="mark") | @NotModified |==

Since in an IDE it is not too easy to have multiple visual markers, it seems best to use the same visuals as the end state.

When a type is effectively @FinalFields (not eventually), all fields are effectively final. The analyzer wants to emphasize the rules needed to obtain (eventual) immutability, by clearly indicating which fields break the immutability rules.

Eventual finality simply adds a @Final(after="mark") annotation to each of these situations.

A fair number of Java frameworks introduce dependency injection and initializer methods. This concept is, in many cases, compatible with the idea of eventual immutability: once dependency injection has taken place, and an initializing method has been called, the framework stops intervening in the value of the fields.

It is therefore not difficult to imagine, and implement in the analyzer, a before state (initialization still ongoing) and an after state (initialization done) associated with the particular framework. The example below shows how this could be done for the Verticle interface of the vertx.io framework.

Currently, contracted eventual immutability has not been implemented yet in the analyzer.

We need to study the situation of seemingly non-modifying methods with modified parameters. Up to now, a method is only modifying when it assigns to a field, calls a modifying method on one of the fields, or directly calls a modifying method on this. However, there could be indirect modifications, as in:

This observation forces us to tighten the definition of a non-modifying method: on top of the definition given above, we have to ensure that none of the modifying methods called on a parameter which is @Modified , call one of 'our' modifying methods. These rules are mostly, but not easily, enforceable when all code is visible.

An additional interface can help to remove the circular dependency between the types. This has the advantage of simplicity, both for the programmer and the analyzer, which at this point doesn’t handle circular dependencies very well. It imposes more annotation work on the programmer, however, because the interface’s methods need contracts.

To compute linking, the analyzer tries to track actual objects, with the aim of knowing if a field links to another field or a parameter. It computes a dependency graph of variables depending on other variables, with the following four basic rules:

Note that saying v links to a is the same as saying that the return value of method links to some field inside A, the type of a. This is especially clear when a == this.

We discern a number of special cases:

Recall that primitives, java.lang.Object, java.lang.String, and unbound parameter types, are @Immutable .

This situation is similar to that of the constructor (rule 3), with a taking the role of v.

Most of the other linking computations are consequences of the basic rules above. For example,

Note: in a method call v = a.method(b, c, d), links between b, c, and d are possible. They are covered by the @Modified annotation: when a parameter is @NotModified, no modifications at all are possible, not even indirectly. The analyzer does not currently compute individual linking between parameters, because we advocate the use of containers: all parameters should be @NotModified. However, extra parameters to the @Independent annotation allow the user to mark them to ensure correct linking computations.

Abstract methods are present in interfaces, and abstract classes. Their very definition is that no implementation is present at the place of definition: only the ins (parameters) and outs (return type) are pre-defined.

Functional interfaces are interfaces with a single abstract method; any other methods in the interface are required to have a default implementation. The following table lists some frequently used ones:

|==

| Name | single abstract method (SAM) | Consumer<T> | void accept(T t); | Function<T,R> | R apply(T t); | BiFunction<T, U, R> | R apply(T t, U u); | Supplier<R> | R get(); | Predicate<T> | boolean test(T t); |==

It is important not to forget that any interface defining a single abstract method can be seen as a functional interface. While the examples above all employ generics (more specifically, unbound type parameters), generics are not a requirement for functional interfaces. The Java language offers syntactic sugar for functional programming, but the types remain normal Java types.

We will not make any distinction between a functional interface and an abstract type. If one were forced to make one, the intention to hold data would be the dividing line between a functional interface, which conveys no such intention, and an abstract type, which does.

In this section we want to discuss a limited application of functional interfaces: the one where the SAMs have a local implementation. The general case, where objects of abstract types come in via a parameter, will be addressed in More on hidden content. Consider the following example:

The fields getAndIncrement and explicitGetAndIncrement hold instances of anonymous inner classes of ApplyLocalFunctions: these inner classes hold data, they have access to the myCounter field. Their concrete implementations of get each modify myCounter. A straightforward application of the rules of modification of fields makes getAndIncrement and explicitGetAndIncrement @Modified : in myIncrementer, a modifying method is applied to getAndIncrement, and in myExplicitIncrementer, a modifying method is applied to explicitGetAndIncrement.

Given that ApplyLocalFunctions is clearly @FinalFields , and the inner classes hold no other data, the inner classes are @FinalFields as well.

Now, if we move away from suppliers, but use consumers, we can discuss:

Using the @Container annotation in a dynamic way allows us to control which abstract types can use the method: when only containers are allowed, then the abstract types must not have implementations which change their parameters.

Let’s go back to NonEmptyImmutableList, first defined in Abstract methods:

We start the discussion with the following immutable implementation of this interface:

According to the interface contract, we need the visit method to be non-modifying, and also not to modify its parameter consumer. However, following the normal definitions of modification, the following two statements hold:

The result of the first statement would violate the @Container property on ImmutableOne, and we’d be very reluctant to do that: according to the intuitive definition in Containers, ImmutableOne is a type that holds data, but does not change the data it has been given. This statement still holds in the presence of a visit method, which is nothing but a way of exposing the object in a way similar to the method first. The second statement would make visit modifying, which again goes against our intuition: looping over elements is, in itself, not modifying.

Luckily, there are two observations that come to the rescue.

First, we believe it is correct to assume that concrete implementations of Consumer are semantically unrelated to ImmutableOne. As a consequence, we could say that the only modifications that concern us in this visit method, are the potential modifications to accept 's parameter t. Other modifications, for example those to the fields of the type in which the implementation is present, may be considered to be outside our scope.

However, if we replace Consumer by Set and accept by add, we encounter a modification that we really do not want to ignore, in an otherwise equal setting. Therefore, it does not look like we can reason away potential modifications by accept. We will have to revert to a contracted @IgnoreModifications annotation on the parameter consumer, if we want to avoid ImmutableOne losing the @Container property.

While we will ignore this second source of modification in the ImmutableOne type, we will defer or propagate it to the place where a concrete implementation of the consumer is presented. We can ignore it here, because t is part of the hidden content of the type; what happens to its content happens outside the zone of control of ImmutableOne. The fact that it is passed as an argument to a method of consumer is reflected by the @Independent annotation. It will take care of the propagation of modifications from the concrete implementation into the hidden content.

This results in the following annotations for visit in ImmutableOne:

Note that we assume that we will need @IgnoreModifications for almost every use of a functional interface from the package java.util.function occurring as a parameter. These types are for generic use; one should never use them to represent some specific data type where modifications are of concern to the current type. Therefore, we make this annotation implicit in exactly this context.

Looking at the more general case of a forEach implementation iterating over a list or array, we therefore end up with:

Modifications to the parameter, made by the concrete implementation, are propagated into the hidden content of list, as shown in the next section. The @Independent annotation appears because hidden content in list is exposed to the consumer parameter. This annotation does not appear for the accessible content of the immutable type.

Recall that parameters of modifiable type can already be shielded from external modification by the @Independent annotation.

Let us apply the visit method of NonEmptyImmutableList to StringBuilder:

It is the second method, addNewLine, that is of importance here. Thanks to the @Modified annotation, we know of a modification to list. It may help to see the for-loop written out, if we temporarily assume that we have added an implementation of Iterable to NonEmptyImmutableList, functionally identical to visit:

Note that while NonEmptyImmutableList is immutable, its concrete instantiation gives access to a modifying method in its hidden content.

We really need the link between sb and list for the modification on sb to propagate to list. Without this propagation, we would not be able to implement the full definition of modification of parameters, as stipulated in Modification, in this relatively straightforward and probably frequently occurring situation.

Moving from NonEmptyImmutableList to NonEmptyList, defined here, which has a modifying method, allows us to contrast two different modifications:

Without storing additional information (e.g., using an as yet undefined parameter like @Modified(hc=true) on list in addNewLine), however, we cannot make the distinction between a modification to the string builders inside list, or a modification to list itself. In other words, applying the two methods further on, we cannot compute

Finally, we mention again the modification to a field from a concrete lambda:

Going back to ImmutableOne, we see that the constructor links the parameter t to the instance’s field by means of assignment. Let us call this binding of parameters of hidden content to the field content linking, and mark it using @Independent(hc=true) , content dependence:

Returning a part of the hidden content of the type, or exposing it as argument, both warrant a @Independent(hc=true) annotation:

Observe that content dependence implies absence of dependence, as described in Linking, dependence and How to compute linking, exactly because we are dealing with type parameters of an immutable type.

Another place where the hidden content linking can be seen, is the for-each statement:

Because the Collection API contains an add method annotated as:

indicating that after calling add, the argument will become part of the hidden content of the collection, we conclude that the local loop variable sb gets content linked to the builders list. Similarly, this loop variable contains hidden content from the list object.

Let us look at a possible implementation of Collection.addAll:

The call to add content links e to this. Because e is also content linked to c, the parameter collection holds content linked to the hidden content of the instance.

We are now properly armed to see how a for-each loop can be implemented using an iterator whose hidden content links to that of a container.

Let us start with the simplest definition of an iterator, without remove method:

Either the next method, or the hasNext method, must make a change to the iterator, because it has to keep track of the next element. As such, we make both @Modified . Following the discussion in the previous section, next is @Independent(hc=true) , because it returns part of the hidden content held by the iterator.

The interface Iterable is a supplier of iterators:

First, creating an iterator should never be a modifying operation on a type. Typically, as we explore in the next section, it implies creating a subtype, static or not, of the type implementing Iterable. Second, the iterator itself is independent of the fields of the implementing type, but has the ability to return its hidden content.

The loop, on a variable list of type implementing Iterable<T>, is expressed as for(T t: list) { …​ }, and can be interpreted as

The iterator it content-links to list; via the next method, it content-links the hidden content of the list to t.

A concrete implementation of an iterator is often a nested type, static or not (inner class), of the iterable type:

For ImmutableArray to be immutable, the iterator() method must be independent of the field elements, in other words, the IteratorImpl object must not expose the ImmutableArray 's fields to the outside world. It cannot be immutable itself, because it needs to hold the state of the iterator. However, it should protect the fields owned by its enclosing type, up to the same standard as required for immutability.

We propose to add a definition for the independence of a type, identical to the "shielding off" part of the definition of immutability. Let’s first go there in a roundabout way:

Clearly, such external modifications are only possible when the constructor, method or field is non-private.

Armed with this definition, we can define the independence of types:

This definition is entirely equivalent to the definition of immutability without rules 0 and 1, and rules 2 and 3 restricted to those fields that are 'exposed' to the outside world via linking or content linking.

Consider the static variant of IteratorImpl, which makes it more obvious that IteratorImpl maintains a reference to the element array of its enclosing type:

The type T is part of the hidden content, the T[] and the counter i are part of the accessible content. No external modification can impact the array or the counter; indeed, only T and a boolean are exposed. The latter is immutable, so does not allow modifications. The former allows modifications on the hidden content, whence the @Independent(hc=true) annotation for IteratorImpl.

Immutable types are independent as a type, but a type does not even have to be immutable to be independent. In fact, any type communicating via immutable types to the outside world is independent:

The following table summarizes the relationship between immutability and independence by means of example types: