Lists: An Observable List for UIs

This article discusses combining the java.util.List interface with the javax.swing.ListModel interface. That is: suppose you want a list that you can easily interact with, but also that plugs into UI elements.

The Simple Solution

The simplest solution is to implement these two interfaces in one object:

public class MyList implements java.util.List, javax.swing.ListModel {
    ...
}

Several years ago I wrote the WatchableVector with this approach in mind: this class extends the java.util.Stack, so all the data structure logic is built-in. All this class has to do is add support for the listeners.

This list can be plugged directly into a JList, and at the same time you can treat it like it a traditional java.util.List. For example, now if you call java.util.Collections.sort( myList ), the UI will automatically update.

Shortcomings

After working with this class for several years, I started to identify shortcomings in this implementation:

Recursive Listeners. In theory a a observable/observer contract is simple: when a change occurs, then notify the listeners. But in the world of UI: it is my experience that listeners spiral out of control very quickly. Here is a simplified/approximated stack trace diagram of a potential listener problem:

Here the list is represented in blue, and two separate listeners are represented in orange and green. The first listener (orange) is notified that a new file is added to a list, but it knows the list needs to always be alphabetized: so it resorts the list. This ends up triggering the first (orange) listener a second time before the second (green) listener ever hears about the first event. If the second listener actually listens to the described event: it will be confused that elements are being reordered that it doesn't even know exist yet.

This is a contrived example showing a simplified chain reaction. In the real world the first listener might have interacted with a separate data structure, and that structure interacted with another, and another, and as a result: a series of listeners that seemed minimally simple (even elegant?) on paper turn into a nightmare of events. I refer to this as "cascading listeners", but a coworker refers to it as "listener hell".

The Event Dispatch Thread. My ListModel is plugged into a Swing component: so it needs to only ever be updated on the event dispatch thread. But my List is the same as my ListModel: so complex (potentially time-consuming) operations on my list now need to occur on the EDT, or ambiguous "bad things" may happen (in a hard-to-pin-down kind of way).

Multithreading. Consider the illustrated example above: all this is occurring in the event dispatch thread. What happens if another thread wants to access this list? It has to wait, because the call to WatchableVector.add(..) is synchronized, as is the call the WatchableVector.get(index). The operation itself may be relatively fast, but the synchronization lock isn't released until all the listeners have been notified. (Including the potentially recursive listener chain reactions...). If you think of this as an IO-model: there's no reason other threads have to wait to read data from this list while other listeners spin their wheels -- but we should prevent them from write operations.

This weekend I wrote a new class to address these issues: the ObservableList.

Addressing Listener Recursion

The ObservableList continues to support the ListDataListener, but it separates listeners into two categories: synchronized and unsynchronized.

Synchronized Listeners. These listeners are not allowed to modify the list. Because of this contract: it is guaranteed that the ListDataEvent each synchronized listener receives reflects the current state of the list. If both listeners in the previous example were added as synchronized listeners, then the flow of execution will look like the diagram on the right.

Even if the first listener doesn't catch the RecursiveListenerModificationException: the loop that iterates over the listeners will catch it and call e.printStackTrace(), so all the subsequent listeners are guaranteed to carry on as usual.

The downside of this approach is: in a complex environment calls that modify this list should be wrapped with a try/catch clause to catch potential RecursiveListenerModificationExceptions. This will be easy to forget. Hopefully violations will be consistent and easy to identify early in testing. But the positive side is: all the other listeners are protected.

Unsynchronized Listeners. These listeners are allowed to modify the source list, so when you use an unsynchronized listener: you have to accept that the ListDataEvent you receive may be inaccurate. (For example: you may be notified that an element was removed, but in fact a previous listener re-added it! You'll receive that event, too, but probably not in the order you would expect.)

You have the option when adding an unsynchronized listener to also prohibit modification from within that thread. This is intended largely as a safeguard for developers to detect unintended chain reactions.

Addressing Synchronization

My original data structure relied on the synchronized keyword to protect the integrity of the list. But it also kept listener notification inside the synchronization block, so if one thread made a call to modify the list and a second thread later wanted to read from the list: then the second thread could not obtain the synchronization lock until all the listeners had completed.

Here is a crude sequence diagram of what that would look like:

When working with complicated UI elements: sometimes listeners (especially a chain reaction of listeners) can involve very expensive operations. We're blocking thread #2 for no real reason: the actual doAdd() operation is complete, so the list is stable again.

The ObservableList uses Semaphores and not the synchronized keyword. The basic format for all operations that modify the list resemble this:

public Object execute(...) {
 readSemaphore.acquireUninterruptibly( 1 );
 try {
  [ evaluate if this is a null-op, if so: return ]
  readSemaphore.acquireUninterruptibly( MAX-1 );
  try {
   [ do operation ]
  } finally {
   readSemaphore.release( MAX-1 );
  }
  fireSynchronizedEvent(...);
 } finally {
  readSemaphore.release();
 }
 fireUnsynchronizedEvent(...);
 return returnValue;
}

And the format for all operations that retrieve (but do not modify) data from this list resemble:

public Object getSomething() {
 readSemaphore.acquireUninterruptibly();
 try {
  return returnValue;
 } finally {
  readSemaphore.release();
 }
}

Since we already (separately) established that a synchronized listener is forbidden to further modify this list: this provides a safe model for concurrent read operations on this list (including while listeners are being notified). The sequence diagram for the previous example now looks like this:

Now suppose thread #2 is the event dispatch thread, and one of the listeners in thread #1 called: SwingUtilities.invokeAndWait(..). (That is: thread #1 is forcing something to run on the EDT.) In the first model using the synchronized keyword: you will have a deadlock. The EDT is waiting to synchronize against the list, and the thread with that lock is waiting for the EDT. In the second model: there is no deadlock.

Addressing The Event Dispatch Thread

There's probably a reason the java.util.List and javax.swing.ListModel were kept separate: when one class implements both, it's very tempting to forget that object (which may have been pledged to the UI) should never be modified on different threads.

So the ObservableList is designated only as List and not a ListModel. But it has two methods to help UI development:

getListModelEDTMirror(): this returns a separate object that mirrors this list. This object will only be updated in the EDT.

As a result: it may (briefly) be the case that the UI mirror has outdated information, so just because you remove an element from this list doesn't mean it's safe to completely dispose of it. Also if the original list is several thousand elements long: maintaining a copy may be expensive.

getListModelView(): this returns a ListModel with direct access to the parent ObservableList. This is basically the "old-fashioned" solution I previously described. If you use this method: it is your responsibility to only ever modify the ObservableList in the EDT. In most cases: you should not rely on this method, but in some (simple) cases it may be safe.

Other Convenient Features

Here are a few additional features the ObservableList list offers:

Detailed events. The ListDataEvent involves specific list indices to describe operations that occurred.

However sometimes calculating a precise event to describe an operation is as expensive as the operation itself, and sometimes your listener really doesn't care about specific indices.

When you add a listener: you pass an argument indicating whether you want a high level of detail or not. If none of the registered listeners have asked for a high level of detail (or if there simply are no listeners): then an oversimplified CONTENTS_CHANGED events may be used to save time.

ChangeListeners. If you aren't really interested in specifics about ListDataEvents, then it can be cumbersome to add the 3 methods of a ListDataListener. You can instead add a ChangeListener: it has only one method to implement.

The setAll( List ) Method. This is equivalent to calling list.clear() followed by list.addAll( otherList ). However those calls will trigger 2 listener notifications indicating that everything has changed, when it might be the case that a single ListDataEvent.INTERVAL_ADDED event is needed because only 1 element was added. In short: this method can streamline the notifications the listeners receive.

Supplemental Methods with Argument Arrays. Every method that takes a java.util.Collection or java.util.List as an argument now has a supplemental method that accepts an array of elements.

Delegating to an Abstract List. The ObservableList wraps around another java.util.List object. The default constructor creates an ArrayList underneath, but you're welcome to use any other list you prefer.

Conclusion

Usually I try to include an applet with my blog articles to keep your attention, but that really isn't possible with this project. Instead all I can link to this time is the ObservableList itself and the related unit tests.

After years of dealing with (self-inflicted) lessons learned from UI development: I think this list implementation satisfies the need for listeners with safety and efficiency.

Of course I'm not the first person to work on an observable list. Here are some other related efforts that might suit your needs better:

There is an Apache version of the ObservableList, but as far as I can tell it's not optimized for multithreading/safety.

JavaFX has its own ObservableList. They also have a setAll(..) method. (In fact my original implementation named this method "replaceAll(..)", and I changed it based on their example.) But I don't have access to the source for this implementation, so I don't know how optimized it is. Also I don't want to start bundling parts of JavaFX in my apps yet.

The JDesktop project has a static method: ObservableCollections.observableList(java.util.List list). But this implementation does not have a setAll(..) method, and I'm unclear how this is implemented under the hood.

One thing all these approaches do that I appreciate is: they use their own (new) type of listener. The ListDataListener can be a little bit constraining sometimes. (For example: try to describe a List.retainAll( Collection ) operation in terms of a ListDataEvent.) But this listener is how the javax.swing.JList wants to be communicated with, so it's acceptable for my usage.