Iterators can be Independent “from” Their CollectionsJohn BoylandNanjing University, ChinaUniversity of Wisconsin-Milkaukee, USAb [email protected] Retert Yang ZhaoUniversity of Wisconsin-Milwaukee, [email protected] [email protected] iterators pose problems for alias control mechanisms: theyhave access to collection interals and yet are not accessible fromthe collection; they may be used in contexts that are unaware of thecollection. And yet iterators can benefit from alias control becauseiterators may fail “unexpectedly” when their collections are mod-ified. We explain a novel aliasing annotation “from” that indicateswhen a collection intends to delegate its access to internals to a newobject and how it can be given semantics using a fractional permis-sion system. We sketch how a static analysis using permissions canstatically detect possible concurrent modification exceptions.1. IntroductionIterators in JavaTMand related languages are objects that give se-quential access to collections, while being external to the collec-tion. In particular, multiple iterators can operate on a collection atthe same time, and the collection is not directly involved in theoperation of iterators. Iterators are an improvement over previousrelated concepts, such as cursors, precisely because of this inde-pendence. Typically a collection only had one cursor, and movingthe cursor had an effect on the collection. Multiple cursors are pos-sible but hard to manage. Noble [18] has surveyed a wide varietyof iterator architectures; we focus here on “external iterators.”An iterator is originally created by the collection, but aftercreation, it may be used in contexts in which the collection isneither visible nor in scope. The very independence that makesiterators so powerful also makes programs that use them morecomplex because of the interactions, notably aliasing, between thecollection and the iterators. In particular, an iterator typically haspointers into the internals of the collection representation, and mayeven perform changes on this representation.Figure 1 gives two interface declarations for the kinds of itera-tors that will be discussed in this paper. In Java, these interfaces areconflated by making remove an optional operation. In this work, tomake it easier to reason about iterators and to make the distinctionvisible in the type system, we use separate interfaces. C++ simi-larly makes a type-level distinction between iterators that can beused to modify a collection and those that cannot. Other kinds ofiterators (such as ListIterators that can change an element in acollection) could be defined. We will use the term mutating iteratorto refer to generally to any iterator that can modify the underlyingcollection.Additionally, we have annotated the iterator methods with“method effects” indicating what state the methods are intendedor permitted to access. We will assume that all methods are so an-notated. In this case, the methods are declared as accessing onlythe state of the iterator and not reading or writing any other state.The fact that we can mask away the effects on the collection isnon-trivial and is one of the main discussion topics of this paper.interface Iterator {reads(this.All)boolean hasNext();writes(this.All)Object next();}interface RIteratorextends Iterator {writes(this.All)void remove();}Figure 1. Two classes of iterators.class App {this List list = new List();...writes(All) void run() {Iterator it = list.iterator();... What if we mutate list?if (Util.member(null,it)) { ... }}}Figure 2. Using an iterator.Normally, we will follow standard OO convention and abbreviatethis.All as All , since All is a (model) instance field.Figure 2 shows an example of using iterators. It uses classesList and Util defined in the following section. The example in-cludes some omitted code that may or may not mutate the collec-tion. A collection may be changed directly using a method suchas clear or add, as well as indirectly through a mutating iterator.When this happens, all iterators currently active on the collection(excepting only the iterator through which the mutation took place,if any) are potentially invalid: they may be referring to internals thathave been discarded or are otherwise reorganized. For instance, if alinked list is cleared, then existing iterators may refer to nodes thatare (otherwise) garbage, and indeed in a language such as C++,the node may have already been returned to the memory allocationsystem. If a new entry is added to a hash table, an existing itera-tor may find its node pointer has been rehashed to a new locationand continuing the iteration may result in repeating some elementspreviously encountered, and omitting others. In C++, the program-mer is warned by the documentation that existing iterators may be“invalid” after a mutation.It is possible to implement iterators so that they are robust inthe face of change, albeit with some additional complexity. In Java,rather than following this route or letting a potentially confusing sit-uation emerge, a fail fast semantics is used: an iterator will (almost)always detect when a mutation outside of its control has happened,and throw a ConcurrentModificationException (CME) if it isused afterwards. Typically this is implemented by version stamp-ing the iterator and collection, but the implementation details arenot the focus here. Instead we are interested in how static alias con-trol mechanisms can (1) describe external iterators, (2) explain theeffects of using a (mutating) iterator, (3) explain why and whenconcurrent modification exceptions are thrown, and (4) staticallyprevent these exceptions from occurring.In the following section, we look at a linked list class withiterators annotated to express the design intent of the aliasing. Thenin Sects. 3 and 4, we look at previously described alias controlsystems and evaluate them by these four criteria. In Section 5, wedescribe how the design intent of the example can be expressedusing our “fractional permission” system.2. ExampleFigure 3 defines a simple linked list class with two kinds of itera-tors. The code is annotated (italic words) with “design intent”showing how aliases are intended to be controlled. Except for from(explained below), these annotations have appeared in one form oranother in previous work. The example also uses class parameters(inside < >) to pass objects that may be used in annotations onfields of