Tuesday, September 8, 2009

ArrayList

The compiler is getting to the point where I can start to sketch out some of the basic container classes. Here's what the ArrayList class looks like:

import tart.core.Math.max;

/** Array-backed list type. */
final class ArrayList[%ElementType] : List[ElementType] {
  private {
    var data:ElementType[];
    var _length:int;

    def grow(amount:int) {
      let nlength = self._length + amount;
      if data.length < nlength {
        let ndata = ElementType[](nlength + nlength / 2 + 16);
        ElementType[].copyElements(ndata, 0, data, 0, self._length);
        self.data = ndata;
      }

      self._length = nlength;
    }
  }

  def construct(data:ElementType...; initialCapacity:int = 0) {
    initialCapacity = max(initialCapacity, data.length);
    self.data = ElementType[](initialCapacity);
    ElementType[].copyElements(self.data, 0, data, 0, data.length);
    _length = data.length;
  }

  def construct(data:Array[ElementType], initialCapacity:int = 0) {
    initialCapacity = max(initialCapacity, data.length);
    self.data = ElementType[](initialCapacity);
    ElementType[].copyElements(self.data, 0, data, 0, data.length);
    _length = data.length;
  }

  def add(e:ElementType) {
  }

  def [index:int]:ElementType {
    get {
      Preconditions.checkIndex(index >= 0);
      Preconditions.checkIndex(index < _length);
      return data[index];
    }

    set {
      Preconditions.checkIndex(index >= 0);
      Preconditions.checkIndex(index < _length);
      data[index] = value;
    }
  }

  def length:int {
    get { return _length; }
  }

  def iterate -> Iterator[ElementType] {
    return ArrayListIterator(self);
  }

  private final class ArrayListIterator : Iterator[ElementType], HasLength {
    private var list:ArrayList;
    private var index:int;
   
    def construct(list:ArrayList) {
      self.list = list;
      self.index = 0;
    }
   
    def next -> ElementType or void {
      if (self.index < self.list.length) {
        return self.list.data[self.index++];
      } else {
        return;
      }
    }

    def length:long { get { return list.length; } }
  }
}

Template Parameter Inference

I made some more good progress this weekend - the compiler can now deduce the template arguments of a class from the parameters of a static method of the template. To give an example:

public final class Array[%ElementType] : Iterable[ElementType] {
  // A function which takes a variable-length list of arguments and
  // returns an array of those arguments.
  static def of(elements:ElementType...) -> Array;
}

def test() {
  let a = Array.of(1, 2, 3);
}
As you can see in the example, the type of the array is deduced from the arguments to the static method 'of'.

Having got this working, I've now implemented array literals - so [1, 2, 3] is merely syntactic sugar for Array.of(1, 2, 3).

The reason for doing it this way is that my type inference engine works on function calls - it tries to find a common ground between the parameters of the function and the arguments of the call, binding template parameter substitutions and adding implicit casts as needed. While I could extend the engine to work on other kinds of language constructs, that would make it more complicated - it's much simpler to transform the other language constructs into function calls. Fortunately, pretty much everything can be transformed into a function call. Thus there is no special logic for, say, arithmetic operators to insure that both terms are promoted to the least common type - instead, we just convert arithmetic operators into function calls, and let the overload resolution process do it's work.

Of course, once the type resolution is done, many of those calls will be replaced with code that is generated inline, so it's not like we are paying any overhead for this.