#summary Design doc for GWT simplified collection classes

= Lightweight Collections in GWT =

We've found that the API semantics for the JRE collections classes are not an ideal match for the constraints of running inside browsers, especially mobile browsers, for several reasons.

== Background and Motivation ==
_The JRE collections framework encode assumptions about the relationship between types, objects, and their implementation making them highly coupled, even at the top of the hierarchy._ For example, the `Map` interface has methods such as `values()`, `entrySet()`, `keySet()` that make very specific guarantees about how the returned objects interact with the map from which they derive. These sorts of prescribed dependencies between collection types (e.g. using a `Map` implies the use of `Set` and `Collection`) and the behavior of collection objects themselves prevent simple implementations. Repeated attempts to optimize GWT's emulated JRE collections show a relatively high cost for even minimal usage of JRE collections because, for example, using a `Map` implies using a `Set` and a `Collection`.

_Too few collection types forces runtime enforcement of behaviors that could be more efficiently modeled statically._ A common example is a class `T` that wishes to return a reference an internal list. However, the `List` interface has mutators (e.g. `add()`) which `T` would not want to make possible "from the outside." The traditional best practice of calling `Collections.unmodifiableList()` on the returned list reference requires the allocation of an extra object (which generates extra GC runs that can turn pathological in IE) as well extra code that must be generated simply to implement `throw new UnsupportedOperationException()` when a mutator is called on the wrapper object. If instead there were an `ImmutableList` type that the list collections implement, class `T` could simply have returned an immutable reference, which would ensure attempts to modify the list are caught at compile-time (i.e. because `ImmutableList` has no mutators) and which would prevent extra object allocations and potentially even facilitate inlining at compile time. This 

_Under-specified semantics in JRE collections lead to defensive programming in application code._ Java developers are encouraged to use the least specific type that has the desired semantics. For example, such advice would say use `List` in your code rather than `ArrayList`. However, there is no guarantee that `List#get(int i)` returns in constant time, so a generic algorithm written in terms of `List` cannot even be assured of its expected time complexity. The JRE collections includes the tag interface `RandomAccess` as a way to workaround the ambiguity, but forcing a check such as `myList instanceof RandomAccess` is time consuming at runtime (where time is precious) and, worse, can defeat the GWT compiler's optimizer.

== Goals ==
  * Absolute minimum size of compiled script. It should be impossible to write more succinct !JavaScript by hand.
  * Absolute maximum speed. It should be impossible to faster !JavaScript by hand.
  * Explicit and well-publicized guarantees of time complexity for each operation. By removing fuzziness, developers can feel confident that they need not be defensive (e.g. by cloning collections unnecessarily).
  * The vocabulary of types should be rich enough to avoid the temptation of creating wrapper types. In other words, a method such as `unmodifiableList()` should never even seem to be necessary.
  * Construction and mutation semantics should minimize object creation. Ideally, the collections themselves could enforce patterns such as having only a singleton instance of an empty list.
  * The same set of collection types must work on the client and the server. We must avoid burdening application programmers with the asymmetry of using JRE collections on the server and GWT collections on the client.
  * Collections must be efficiently serializable over GWT RPC.
  * Collections must be able to be `eval()`-ed into existence from JSON.
  * Collections must be pleasant to use, even relative to JRE collections. If developers are still tempted to use JRE collections, we could end up with the worst case of duplicating collection code.
  * When non of the other goals are compromised, individual methods on collections should be source-compatible with JRE collections. This simplifies porting existing code to use the new collections and keeps methods as familiar as possible.

== Non-goals ==
  * We are knowingly sacrificing true compatibility and interop with existing JRE collections. For example, we do not intend to implement the JRE `Map`, `List`, or `Set` interfaces.
  * There is no particular goal of using the same collections implementation for both the client and the server. If we need to use super-source or deferred binding, so be it.
  * Until the GWT compiler can optimize it (which it cannot to date), the new collections will not support the Java enhanced 'for' loop syntax that uses Iterable/Iterator. We do believe such optimizations are possible and will be added, however, at which time, these collections will be retrofitted to implement Iterable.

== Introduction ==
_Note: The collections described here are similar in several respects to Scala 2.8 collections, and where possible, terminology is borrowed to give consistent names to the similar concepts._

We begin by acknowledging that the design of anything as fundamental as collection types is bound to be contentious, so the plan is to start small and establish some patterns for simple, high-value collections: `Array` and `Map`.

=== Principles === 
_Assertions, not exceptions._ Assertions, when turned off, can be compiled away. Code written to defensively check for and throw exceptions is very hard to optimize. Hosted mode always has assertions on, so any well-tested code ought to execute assertions during normal testing.

_Types and methods must be used properly to perform properly._ Lightweight collections are in no way defensive. Improper use generates an assertion failure or, if assertions are disabled, undefined behavior. The corollary is that the API can be designed for maximum efficiency.

_Bending the type system is okay if it's sufficiently hard to detect._ If there are cases in which quietly cross-casting JSOs would be the most efficient thing to do, so it shall be done. However, in such cases, it should be a goal to do "the right thing" in hosted mode (e.g. actually have checked casts) but then silently slip in the trickier cross-casting version during a web mode compile.

_Hosted mode collections implementations can differ, if necessary, from web mode._ This follows from the previous point but is also practical since OOPHM is based on IPC, it may simply be harmfully slow to implement hosted mode collections using JSNI.

_Publish and guarantee time complexity for various operations._

_Keep implementations locked down._ Because it's very tricky to get the implementations for these sorts of collections just right, the plan is to minimize ways in which there could be confusion about the implementation of a given collection type. More concretely, the key types should be classes rather than interfaces so that their implementation can be restricted to the package in which they are defined. If developers cannot trust that a given collection instance is truly optimal and maintains time complexity guarantees -- as might be the case if collections types were interfaces which could have been implemented "anywhere" -- then they may feel compelled to write defensive code. By locking the implementations down, developers can rely on the behavior of a given collection type.

=== !Collections ===
_Unfinished. Other collections, as they are fleshed out, will also be constructed via this class._

{{{
/**
 * The single starting point for interacting with collections from scratch.
 * All collection instances are originally obtained via a method in this class.
 * Using a factory method rather than a constructor for, say, MutableArray<E> 
 * provides convenient inference of the collection's generic type and also provides
 * a way to satisfy the requirement that JSOs cannot have exposed constructors.
 */
public class Collections {
  public <E> MutableArray<E> createMutableArray();
}
}}}

=== Array, !MutableArray, and !ImmutableArray ===

{{{
/**
 * A "root collection" that provides a read-only interface to an array 
 * whose contents may or may not be mutable, making it possible to create read-only
 * library algorithms that work with either mutable or immutable arrays without
 * making calling code paranoid about whether the library routine might mutate it,
 * thus preventing the desire to do defensive wrapping or copying.
 */
public class Array<E> {
  @ConstantTime public E get(int index);
  @ConstantTime public int size();
}

/**
 * A "mutable collection" that is very similar to ArrayList 
 * (and C++ vector, and many others). It has the ability to efficiently 
 * "freeze" itself into an ImmutableArray.
 */
public class MutableArray<E> extends Array<E> {
  // Changes the element at a particular index
  @ConstantTime public void set(int index, E elem);
  
  // Appends an element to the end of the array
  @ConstantTime public void add(E elem);
  
  // Inserts an element into the specified index, lengthening the array by 1
  @LinearTime public void insert(int index, E elem);
  
  // Removes the element at the specified index, shortening the array by 1
  @LinearTime public void remove(int index);
  
  // Removes all elements of the array
  @ConstantTime public void clear();
  
  // Creates an immutable array based on the state of this instance.
  // The returned array may or may not have the same identity as this.
  // After this call, this instance may no longer be used as a MutableArray instance
  // (assertions double-check that no subsequent modifications are made).
  @ConstantTime public ImmutableArray<E> freeze();
}

/**
 * An "immutable collection" that makes that iron-clad guarantee that code 
 * holding a reference to an instance can be certain that its 
 * contents will not change over time.
 */
public class ImmutableArray<E> extends Array<E> {
  // Only inherited members
}
}}}


== Examples of Intended Usage ==

=== Arrays ===
{{{
public <E> void printEach(Array<E> arrToPrint) {
  for (int i = 0, n = arrToPrint.size(); i < n; ++i) {
    Window.alert(arrToPrint.get(i).toString());
  }
}

public MutableArray<String> makeSnackArray() {
  MutableArray<String> a = createMutableArray();
  a.add("apple");  
  a.add("banana");
  a.add("coconut");
  a.add("donut");
  return a;
}

public void exampleOne() {
  MutableArray<String> a = makeSnackArray();
  printEach(a);
}

public void exampleTwo() {
  MutableArray<String> ma = makeSnackArray();
  ImmutableArray<String> ia = ma.freeze();

  // We can't touch 'ma' any more, but we can
  // confidently hand out aliases all over the place.
  new MyView1(ia).show();
  new MyView2(ia).show();
  new MyView3(ia).show();
}
}}}