ListSubject order-unaware?

Topics: Feature Requests and Contributions, Reactive (Rx)
Jun 2, 2012 at 9:41 PM

My thanks to everyone working on the future of Rx.

I've got a question regarding the design of ListSubject: While INotifyCollectionChanged's NotifyCollectionChangedEventArgs knows an insertion index, there appears to be no equivalent in CollectionNotification<T>.

 

In particular, doing an

 

(from n in ls1 from m in n.ToModifications() select m).Subscribe(ls2);

 

doesn't replicate the order of the collection properly.

Since the ordering is very important when binding against the ListSubject from an ItemsControl, this design decision has some disadvantages.

Is there a rationale for it or a planned alternative?

Coordinator
Jul 31, 2012 at 4:33 PM

Hi,

James and I had some related internal discussions about this as well.  Ultimately, the choice was made to yield to the non-deterministic nature of reactive programs when implementing a reactive collection. 

Perhaps the name ListSubject causes some confusion.  The semantics of CollectionNotification<T> is that it represents a change in an ICollection<T>, not an IList<T>.  ICollection<T> represents an unordered list.  In other words, indices are not exposed publicly; there's no indexer.  ListSubject represents a reactive collection that implements IList<T> because it was decided that it may be more useful as an IList<T> than simply an ICollection<T>, when used imperatively.

The reason why there's no ListNotification<T> in Rxx is because in a reactive system there's no guarantee that indexes contained in notifications from some asynchronous sequence are going to match up at all to the actual statefulness of observers.  Assuming they match would imply that the observables know something about their observers.  This assumption could end up very badly for developers that are expecting an API that is completely thread-safe out of the box.

I feel that it's better to design a reactive system that is truly reactive.  In other words, a collection notification simply contains data indicating whether an item was added or removed.  A collection modification simply indicates whether an item should be added or removed.  Neither makes any assumptions about the other.

One could argue that removal in general also implies knowledge of an observer, but I've got two reasons why it's not a problem in Rxx:

  1. Removal notifications and modifications correspond to the behavior of ICollection<T>.Remove, whose contract requires that implementors return false if an item doesn't exist in the collection (as opposed to throwing an exception).  The semantics are "remove the item, if you've got it".  This fits nicely in a reactive world, where concurrency permits a program to statefully remove an item from a ListSubject before it observes a removal modification for the same item.

    Try adding indices into the mix and everything breaks down because removing an item from the ListSubject changes the indices of other items in the list, which may already have removal modifications in flight.  If reactive removal modifications were permitted by index, then it would be possible that the wrong item would be removed if the intended item was already removed (either statefully or by another observable) instead of the guaranteed no-op that occurs when removing by reference.  Furthermore, if the index is invalid then an exception should be thrown (OnError) to mimic the behavior of IList.RemoveAt.
  2. A removal notification indicates that an observable has changed and a removal modification indicates that an observer should change.  They are unrelated.  For example, a sequence of modifications could be generated at random to create a reactively random list.  There's no need for notifications at all.  Thus, a removal modification does not necessarily imply any knowledge of observers.

    If you decide to convert a removal notification into a removal modification, then you're explicitly changing the semantics of the data.  In other words, you're taking data that represents the state of system A and changing it into a signal that will modify system B.  As mentioned previously, in a world with concurrency it's possible that system A and system B may be updated independently of one another, thus removal modifications must be able to adapt to unanticipated changes in the state of system B.  They do so by carrying the semantics of ICollection<T>.Remove, as stated in #1 above.  If indices were to be supported as well, then explicitly converting notifications to modifications implies that system A and system B cannot be modified independently; i.e., concurrency must not be permitted, thus you'd be creating a closed system.  It's of course still possible to ensure that A == B through reactive programming techniques, but the types in Rxx are intended to have broader usage in openly reactive and concurrent systems.

I'm not suggesting that your assumptions about how indices could behave wouldn't be useful in some capacity.  I'd just be concerned about developers using it incorrectly, creating programs that aren't thread-safe under the assumption that Rxx will take care of the thread-safety for them, which of course it can't.

Sorry for the delayed reply.

- Dave

Aug 2, 2012 at 8:42 PM

Hi Dave,

thank you for the detailed response.

I understand your design decisions better now, but it unfortunately renders it useless for a use case I believe to be very common. I have an idea how that could be fixed with the current design.

The use case is to build conceptual collections through building blocks from base collections to have them represented in a user interface. For example, one often has to display filtered, combined, etc. lists of business entities and have the display update automatically when the source collections change. This is usually a single-threaded problem (as it doesn't matter that everything has to go through the UI dispatcher). Currently, there are only tools such as the PagedCollectionView which is a monster that can do too much and too little at the same time. Ideally, one would want some sort of database in-process with live views through linq.

Practically enough, however, would be something like ListSubject to construct and update the desired views reactively - if only one would have control over the collection's order.

So my feature suggestion would be to have a modified OrderedListSubject<T> that gets a comparer by which the list will be ordered.

Actually it would be enough if you offer a virtual function

protected virtual int GetInsertionIndex(T t) { return 0; }

within ListSubject<T> to make it easy for someone else (like me) to implement it without touching the sources.

Thanks again for your time, John

Coordinator
Aug 2, 2012 at 10:41 PM

Hi,

That's an interesting idea, thanks.  I'll add a work item and think about it some more.

Your problem description reminded me of the following discussion.  See my replies near the end for some thoughts on the complexity of synchronizing projected lists by index.  (I'm not sure if this is your intended use, but perhaps it's noteworthy.)

http://social.msdn.microsoft.com/Forums/en-US/rx/thread/c0afaa67-b58b-413b-a92d-cb18126b6293

I assume you've thought about using ObservableCollection<T> instead.  You can make it an observer of an observable sequence:

listChanges.Subscribe(data => collection.InsertAt(data.Index, data.Value));

You can also make it an observable of changes that includes indexes:

var changes = Observable.FromEventPattern<NotifyCollectionChangedEventHandler, NotifyCollectionChangedEventArgs>(
	eh => eh.Invoke, 
	eh => collection.CollectionChanged += eh, 
	eh => collection.CollectionChanged -= eh);

It should be easy to tie them together.

- Dave

Coordinator
Aug 2, 2012 at 10:46 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.