Implementation of JavaFX sequence triggers

The presence of an on-replace trigger complicates JavaFX sequence updating. Specifically, it makes it difficult to implement copy-on-assignment or copy-when-shared efficiently.

In JavaFX a trigger is a kind of function that gets called after an update. It has up to four (optional) parameters: The old value of the sequence variable, the start and end position of the replaced slice (relative to the old value), and the new elements that replaced the slice.

However, when we modify an ArraySequence in-place, the old value doesn't exist: We'd have to make a copy before we do the modification, which negates the whole point of in-place modification. Likewise, on a single-element insert or replace we don't have the new elements as a separate sequence value.

What saves us is that most of the time a trigger doesn't actually use the old-value or the new-elements, except perhaps to read a single item. So we can design an internal API where we don't create these as separate sequence values unless we have to. The idea is that a trigger gets compiled to a method with the following interface:

  public abstract void onChange(ArraySequence buffer,
           Sequence oldValue,
           int startPos, int endPos /* exclusive*/,
           Sequence newElements);

The trick is that one or both of oldValue and newElements may be null. In that case buffer must be non-null, and there is an algorithm (to be described) for extracting oldValue and newElements from the buffer, if needed.

First, the trivial case when we replace the sequence wholesale:

v = newElements

In that case we save the oldValue before doing the update, and pass buffer=null, startPos=0, and endPos=oldValue.size().

Next consider the case when the oldValue is an unshared ArraySequence. This is the case we want to optimize - we want to modify it in-place, and avoid creating a new object unnecessary. The trick is to store the deleted/replaced elements in the gap of the ArraySequence. Specifically, for:

seq[loIndex..<hiIndex] = newElements

the algorithm is:

If the available space (i.e., size of the gap) is less than the number of new elements, allocate a larger buffer (maybe twice the size of the old buffer), and copy the elements, leaving the gap at index loIndex.
Otherwise, adjust the gap if necessary to start at loIndex.

Insert newElements at the start of gap. Adjust the start of the gap to follow the inserted elements, and the end of the gap to be after the deleted elements. Note at this point the deleted/replaced elements are at the end of the gap, as in this diagram:

+-------------------------+ 0
| Preserved elements      |
+-------------------------+ loIndex
| Newly-inserted elements |
+-------------------------+ gapStart
| Unused (gap)            |
+-------------------------+ gapEnd-hiIndex+loIndex
| Newly-deleted elements  |
+-------------------------+ gapEnd
| Preserved elements      |
+-------------------------+ buffer.length

[Layout of an ArraySequence buffer just after an update, while the triggers are running.]

Invoke the triggers, passing the ArraySequence as the buffer. oldValue is null. If newElements exists as a Sequence object, pass that; if we're inserting or replacing a single item we don't have newElements, so pass newElements=null.
If the buffer is an object type, null out the elements in the gap corresponding to the deleted elements (to avoid memory leaks).

If the old value is not an ArraySequence, or it is a shared ArraySequence, first copy the old value into a fresh unshared ArraySequence, and proceed as above, except for oldValue we can pass the old value instead of null.

(The rationale for this algorithm (and specifically that we insert at the start of the gap) is that it is well-behaved for updates in a forwards direction: After an update that replaces the range [i..<j] by n elements the start of the gap will be at (i+n). It is likely that the next operation will be replace a range starting at (i+n) - that is certainly the case for an algorithm that replaces the elements in sequential order (when n==1 for each iteration). So that gap will be correctly positioned in that very common case.)

(A possible concern is that requiring the buffer to have room for both deleted and inserted elements might mean that we have to re-allocate the buffer just to remember the deleted elements for the triggers, and then have excess space after running the triggers. But this isn't an issue for plain deletion or insertion, only replacement, and the most common replacement is a single element, so the extra space needed is just enough for one element.)

Compile-time

First we assume a simple non-optimized implementation:

Compile:

var v : T[] on replace oldV[i..j] = newV { triggerBody }

to (mix of Java and JavaFX pseudo-code):

 new SequenceChangeListener() {
     public void onChange(ArraySequence $buffer,
           Sequence $oldValue,
           int i, int $j,
           Sequence $newElements) {
        def j = $j-1;
        def oldV = Sequences.getOldValue($buffer, $oldValue, i, $j);
        def newV = Sequences.getNewElements($buffer, i, $newElements);
        triggerBody;
     }

The library method Sequences.getOldValue tests if the $oldValue argument is null, in which case it creates a fresh sequence value by copying the old values from the buffer gap of the $buffer. The library method Sequences.getNewElements similarly handles the case when $newElements is null.

Of course the whole point is to only do the copying if the application actually needs these values. So the first obvious optimization: If the trigger doesn't reference oldV or newV then we don't need to call Sequences.getOldValue or Sequences.getNewElements, respectively.

We can do even better: Most triggers only use newV in the context of indexing newV[i], or sizeof newV or for (x in newV) {...}. In that case we don't need to call Sequences.getNewElements. For example instead of newV[i], we extract (ignoring bounds-checking):

buffer.array[loIndex + i]

See Sequences.st for the actual code. More generally, the compiler makes the following mappings:

   oldV[j] => Sequences.extractOldElement($buffer, $oldValue, i, $j, k)
   sizeof oldV => Sequences.extractOldSize($buffer, $oldValue, $j)
   newV[k] => Sequences.extractOldElement($buffer, i, $newElements, k)
   sizeof newV => Sequences.extractNewSize($buffer, i, $newElements)

Tags: JavaFX

Links: JavaFX-sequence-basics JavaFX-sequence-updating

Per Bothner's blog

Implementation of JavaFX sequence triggers

Compile-time