Collection<T> and ObservableCollection<T> do not support ranges

[robertmclaws]

Update 10/04/2018

@ianhays and I discussed this and we agree to add this 6 APIs for now:

    // Adds a range to the end of the collection.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Add)
    public void AddRange(IEnumerable<T> collection) => InsertItemsRange(0, collection);

    // Inserts a range
    // Raises CollectionChanged (NotifyCollectionChangedAction.Add)
    public void InsertRange(int index, IEnumerable<T> collection) => InsertItemsRange(index, collection);

    // Removes a range.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Remove)
    public void RemoveRange(int index, int count) => RemoveItemsRange(index, count);

    // Will allow to replace a range with fewer, equal, or more items.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Replace)
    public void ReplaceRange(int index, int count, IEnumerable<T> collection)
    {
         RemoveItemsRange(index, count);
         InsertItemsRange(index, collection);
    }

    #region virtual methods
    protected virtual void InsertItemsRange(int index, IEnumerable<T> collection);
    protected virtual void RemoveItemsRange(int index, int count);
    #endregion

As those are the most commonly used across collection types and the Predicate ones can be achieved through Linq and seem like edge cases.

To answer @terrajobst questions:

Should the methods be virtual? If no, why not? If yes, how does eventing work and how do derived types work?

Yes, we would like to introduce 2 protected virtual methods to stick with the current pattern that we follow with other Insert/Remove apis to give people hability to add their custom removals (like filtering items on a certain condition).

Should some of these methods be pushed down to Collection?

Yes, and then ObservableCollection could just call the base implementation and then trigger the necessary events.

Let's keep the final speclet at the top for easier search

Speclet (Updated 9/23/2016)

Scope

Modernize Collection<T> and ObservableCollection<T> by allowing them to handle operations against multiple items simultaneously.

Rationale

The ObservableCollection is a critical collection when it comes to XAML-based development, though it can also be useful when building API client libraries as well. Because it implements INotifyPropertyChanged and INotifyCollectionChanged, nearly every XAML app in existence uses some form of this collection to bind a set of objects against UI.

However, this class has some shortcomings. Namely, it cannot currently handle adding or removing multiple objects in a single call. Because of that, it also cannot manipulate the collection in such a way that the PropertyChanged events are raised at the very end of the operation.

Consider the following situation:

• You have a XAML app that accesses an API.
• That API call returns 25 objects that need to be bound to the UI.
• In order to get the data displayed into the UI, you likely have to cycle through the results, and add them one at a time to the ObservableCollection.
• This has the side-effect of firing the CollectionChanged event 25 times. If you are also using that event to do other processing on incoming items, then those events are firing 25 times too. This can get very expensive, very quickly.
• Additionally, that event will have ChangedItems Lists that will only ever have 0 or 1 objects in them. That is... not ideal.

This behavior is unnecessary, especially considering that NotifyCollectionChangedEventArgs already has the components necessary to handle firing the event once for multiple items, but that capability is presently not being used at all.

Implementing this properly would allow for better performance in these types of apps, and would negate the need for the plethora of replacements out there (here, here, and here, for example).

Usage

Given the above scenario as an example, usage would look like this pseudocode:

    var observable = new ObservableCollection<SomeObject>();
    var client = new HttpClient();
    var result = client.GetStringAsync("http://someapi.com/someobject");
    var results = JsonConvert.DeserializeObject<SomeObject>(result);
    observable.AddRange(results);

Implementation

This is not the complete implementation, because other *Range functionality would need to be implemented as well. You can see the start of this work in PR dotnet/corefx#10751

    // Adds a range to the end of the collection.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Add)
    public void AddRange(IEnumerable<T> collection)

    // Inserts a range
    // Raises CollectionChanged (NotifyCollectionChangedAction.Add)
    public void InsertRange(int index, IEnumerable<T> collection);

    // Removes a range.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Remove)
    public void RemoveRange(int index, int count);

    // Will allow to replace a range with fewer, equal, or more items.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Replace)
    public void ReplaceRange(int index, int count, IEnumerable<T> collection);

    // Removes any item that matches the search criteria.
    // Raises CollectionChanged (NotifyCollectionChangedAction.Remove)
    // RWM: Excluded for now, will see if possible to add back in after implementation and testing.
    // public int RemoveAll(Predicate<T> match);

Obstacles

Doing this properly, and having the methods intuitively named, could potentially have the side effect of breaking existing classes that inherit from ObservableCollection to solve this problem. A good way to test this would be to make the change, compile something like Template10 against this new assembly, and see if it breaks.

---

So the ObservableCollection is one of the cornerstones of software development, not just in Windows, but on the web. One issue that comes up constantly is that, while the OnCollectionChanged event has a structure and constructors that support signaling the change for multiple items being added, the ObservableCollection does not have a method to support this.

If you look at the web as an example, Knockout has a way to be able to add multiple items to the collection, but not signal the change until the very end. The ObservableCollection needs the same functionality, but does not have it.

If you look at other extension methods to solve this problem, like the one in Template10, they let you add multiple items, but do not solve the signaling problem. That's because the ObservableCollection.InsertItem() method overrides Collection.InsertItem(), and all of the other methods are private. So the only way to fix this properly is in the ObservableCollection itself.

I'm proposing an "AddRange" function that accepts an existing collection as input, optionally clears the collection before adding, and then throws the OnCollectionChanging event AFTER all the objects have been added. I have already implemented this in a PR dotnet/corefx#10751 so you can see what the implementation would look like.

I look forward to your feedback. Thanks!

[thomaslevesque]

The event fired for RemoveAll should be Reset event, and not Remove event - RemoveAll removes items based on a predicate, meaning, the items removed may not be consecutive. The EventArgs for Remove sets the OldItems and OldStartingIndex for tracking the consecutive items. This doesn't apply to RemoveAll.

While I'll understand the reasoning, I don't think Reset is the proper event in this case. The documentation for Reset says:

The content of the collection was cleared.

Which IMO should only happen when Clear is called. RemoveAll could raise multiple Remove events instead (for each range of consecutive removed items).

[robertmclaws]

Which IMO should only happen when Clear is called. RemoveAll could raise multiple Remove events instead (for each range of consecutive removed items).

The only thing I don't like about this is that it could conceivably raise as many events as removing them individually. The point of these new functions is to minimize the number of events raised to maximize efficiency.

I'm having a really hard time thinking of a use case where knowing the index of the removed items is necessary. If it truly is necessary, then it might be better to return a list containing a new type of object that contains the item removed, and the index that particular item was at.

[Priya91]

Which IMO should only happen when Clear is called. RemoveAll could raise multiple Remove events instead (for each range of consecutive removed items).

If this is the intended behavior for firing remove event, then the outcome is no different than calling Remove single item on a loop based on a predicate match from user code. I don't think this should be the behavior of RemoveAll, I still propose Reset event, to differentiate this removal of non-consecutive items Or @robertmclaws idea also sounds good on returning a negative index to differentiate the non-consecutive remove, can discuss with the review board.

[thomaslevesque]

The only thing I don't like about this is that it could conceivably raise as many events as removing them individually.

True, but there's no way around it... The INotifyCollectionChanged API only supports changes to consecutive items. It might be more efficient in some cases to just raise a Reset event, depending on the number of items removed. In light of this dilemma, maybe including RemoveAll in the API isn't such a good idea after all.

I'm having a really hard time thinking of a use case where knowing the index of the removed items is necessary.

It makes removing the corresponding UI items (in a ListBox, ListView etc) more efficient, since there's no need to scan the whole list to find the right ones.

[Priya91]

It makes removing the corresponding UI items (in a ListBox, ListView etc) more efficient, since there's no need to scan the whole list to find the right ones.

That's why Reset event, to say, the collection was dramatically changed, re-parse the collection in the handler.

[robertmclaws]

It makes removing the corresponding UI items (in a ListBox, ListView etc) more efficient, since there's no need to scan the whole list to find the right ones.

If you're binding those items in XAML directly to an ObservableCollection (which really is the point to this change) then that should not be necessary. If this benefits some legacy app framework, so be it. But the change is really to support UWP and modern app development.

The INotifyCollectionChanged API only supports changes to consecutive items.

How so, by intent or by practice? Because of the way NotifyCollectionChangeEventArgs works today? If so, the reality of that is that it's also only designed to work with individual items, so the really isn't anything stopping us from making this new feature work in the simplest and most consistently logical way possible. Even if that means adding new properties/return types on NotifyCollectionChangeEventArgs.

But I honestly don't see how we could intelligently have that discussion until we actually have an implementation that we can look at and see from there what makes the most sense.

[thomaslevesque]

If you're binding those items in XAML directly to an ObservableCollection (which really is the point to this change) then that should not be necessary.

Sorry, I didn't express myself clearly. I didn't mean that you'd have to do it yourself, but that the UI control which is bound to the collection would have to do it.

How so, by intent or by practice? Because of the way NotifyCollectionChangeEventArgs works today? If so, the reality of that is that it's also only designed to work with individual items

No, it can already work with ranges; that's why the NewItems and OldItems properties are collections

[robertmclaws]

Sorry, I didn't express myself clearly. I didn't mean that you'd have to do it yourself, but that the UI control which is bound to the collection would have to do it.

We might need to dig into some of the UWP binding code and see how it handles these things. If that is the case, then "Reset" may indeed be the event that needs to be thrown. I can buit that into my custom implementation that I'm already using and see what happens.

No, it can already work with ranges; that's why the NewItems and OldItems properties are collections

Yes, but based on comments from earlier, I don't believe that is from work that was started but never finished. It certainly wasn't thought out properly. So if we need to change behavior / add functionality to NotifyCollectionChangedEventArgs to make it work in ways that will easily meet developer expectations, then we should be open to discovering what that means.

[robertmclaws]

Hope everyone's had a great week so far. So where are we at with this?

[terrajobst]

@robertmclaws

But I honestly don't see how we could intelligently have that discussion until we actually have an implementation that we can look at and see from there what makes the most sense.

Agreed. How about this:

• Let's excludeRemoveAll for now as this API has the most complicated eventing issues.
• We can then approve this suggestion and you're unblocked with adding a PR.
• We take this learning to decide what we do with RemoveAll
• My concern is still that we can't plumb the batching fully through

How does this sound?

[robertmclaws]

@terrajobst Works for me, let's do it! :)

[robertmclaws]

PS, I updated the speclet at the top, and deleted the speclet in the middle. I'm ready to re-open and update my PR.

[terrajobst]

@robertmclaws

Sounds good. It would be good in the PR to call out how the following elements will be addressed/can be addressed:

• Will/can the APIs live on ObservableCollection<T> or on the base, Collection<T>?
  • If they live on the base, should they be virtual or should we follow the existing pattern where we have non-virtual public methods and protected virtual members.
• It seems some of the APIs in the system assume the ranges contain a single item. That's clearly a design mistake, but it may indicate that we might have trouble forwarding the events as true ranges across all the handlers. Hopefully, test coverage will show that, but I doubt that as many of the consumers live in parts of the stack that isn't part of .NET Core (e.g. WPF)

[karelz]

@robertmclaws just curious if you're still working on it, or we should make it available for grabs ...

[karelz]

@robertmclaws ping?

[robertmclaws]

Sorry, I'm working on it. Will try to have a PR over the holiday break.

[karelz]

Sure, no pressure, just want to make sure we are somewhat up to date on who is working on what.

[groege]

Actually one more thing to think about--> what if we let's say want to add and remove stuff before firing the event? Lets say as mentioned before an --> i want to remove some Items & add some Items, or even insert on different indexes, move things around all at once. My guess is that for this specific it might be better to implement another collection with INotifyCollectionChanged & INotifyPropertyChanged and add some kind of disposable transaction.

i.e.:

var collection = new OmnipotentCollection<string>({"1", "2", "3","4", "5","6","7","8","9","10"});
using(var transaction = collection.MultiUpdate()) {
   transaction.Insert(3, "A");
   transaction.Insert(5, "B");
   transaction.Remove("3");
   transaction.AddRange({"C", "D"});
}

or something like this

collction.Update( x=>
{
    x.Insert(3, "A");
    x.Insert(5, "B");
    x.Remove("3");
    x.AddRange({"C", "D"});
}

I guess something like this would be overkill ^^ - Still maybe someone has a simple idea to do something like that (without over-complicating things like I do)

[jnm2]

I use this pattern with a custom-implemented list type:

using (list.SuppressListChangedEvents())
{
    // mutate list
} // On dispose, fires Reset if events are incompatible

In fact I've found this to be so useful that lists that do it implement a common interface. This allows extensions methods like the following:

public static void Reset<T>(this ICollection<T> collection, IEnumerable<T> replacementItems)
{
    using ((collection as IControlListChangedEvents)?.SuppressListChangedEvents())
    {
        var enumeratedBeforeClear = replacementItems.ToArray();
        collection.Clear();
        collection.AddRange(enumeratedBeforeClear);
    }
}

[robertmclaws]

@jnm2 I wouldn't mind seeing how you've implemented that pattern. It might be an interesting addition to the spec.

[karelz]

We should probably discuss this pattern in a separate issue. If it is common enough and the need is high, we could consider it.

[robertmclaws]

@karelz, I don't know that the pattern @jnm2 is suggesting is actually a separate issue. It's fairly relevant to the implementation here, as that could be the method of bypassing the events internally as well. Since I'm working on the PR right now, I'd like to see his implementation now, to see if it would make sense in the broader context of the work I'm doing.

[karelz]

@robertmclaws wouldn't it change the API shape? -- That would require a new API approval.

[robertmclaws]

If it were made public, yes. However, I could implement the pattern as an internal, and then we can talk about making it external. IF it's worth it. Won't know that until I see it.

[karelz]

Got it, that makes sense.

[groege]

Would it make sense to adapt the changed event to represent all changes without the reset event? So we can add/move/remove items without having to look at the whole collection - and if yes how could this be done in a proper and easy to understand manner.

[jnm2]

@robertmclaws Mine is IBindingList-oriented but this concept could be even more powerful with INotifyCollectionChanged.

Here is how I would design it: https://gist.github.com/jnm2/d950053fd3825818371b87730f208839#file-eventbufferingcollection-cs

[robertmclaws]

Working on my implementation now. As an FYI to @terrajobst @karelz @Priya91 etc, since Collection lives in CoreClr and not CoreFx, this is going to have to be a two-part PR (as mentioned in the referenced issue above this comment).

[robertmclaws]

My initial work is here. Feel free to comment before I open a PR, Or you can wait till after.

[weitzhandler]

Here's my implementation, hopefully it gives some ideas. It's optimized for re-usage of items, and raising lesser Reset events.

[karelz]

Unassigning @robertmclaws and marking it up-for-grabs as it looks like no one is working on it. Next step: Submit PR.

[weitzhandler]

@karelz, thanks. Ok. I'm willing to implement this, and I'd like to include a few changes that I found important and performance impacting on the UI thread. The real time consumer is resetting the collection or not re-using existing items is, which is why:

• Avoid Reset events whenever possible
• Safe-check before raising events or notify properties, and avoid doing so if unnecessary, for example calling Clear when collection already empty
• We should also consider offering the OC act like a HashSet<T> reusing existing items of the provided comparer (maybe we should provide additional boolean property to determine re-usability of items?)
• Because of the above, we might need to change some test cases

Please have a look at my code here, I'm going to reuse some of the code from there.

[robertmclaws]

@karelz, I had an implementation ready to go... I was waiting on comments.

[karelz]

@robertmclaws it wasn't clear if it was just a prototype, or the real thing. If it is the real thing, I would suggest to create a PR out of it. Assigning back to you ...

[robertmclaws]

@karelz Gotcha. If you look at the conversation here: https://github.com/robertmclaws/coreclr/commit/841672090c9245ab961bf25cb682833ef599c358 there was a pretty in-depth discussion about breakage, which was part of the reason this was not implemented yet, and why we didn't go down the route @weitzhandler suggested. We were iterating on how to handle subclasses in a non-breaking way, and then I think the holidays kicked in and it was forgotten about. Happy to look at it with fresh eyes and get it pushed through.

[karelz]

Sounds good! I bet @weitzhandler will be happy to code review it as well. PRs in general get more attention in code reviews, so it will be a good thing. If there are still open design/breaking-changes questions, I would suggest to raise them and address them before creating the PR.

[weitzhandler]

@karelz I think in the ObservableCollection<T> range support will anyway require overriding the range methods if we choose to add them to Collection<T>, what I mean to say is that we can implement the ObservableRangeCollection<T> range methods separately. Though I agree we'd better off starting with overriding appropriate range methods rather than adding them later to Collection<T>. Shame I joined this party late. Sorry if interrupting.

@robertmclaws

and why we didn't go down the route @weitzhandler suggested

What do you mean?

@robertmclaws @karelz Are you working on it? Otherwise I'd like to be assigned.

---

Anyway, here's an initial commit: https://github.com/dotnet/corefx/compare/master...weitzhandler:observable-range-collection I'm gonna create tests for the methods I've added over the next week.

[karelz]

@weitzhandler if you think the API as approved above is insufficient, please make sure you provide enough clear evidence to others. If that's the case (and @robertmclaws agrees with your conclusions), we would have to take it first to a new round of API review.

[robertmclaws]

My plan for this weekend:

• [ ] Review the following implementations:
  • [ ] Xamarin's ObservableRangeCollection
  • [ ] My existing PR to my personal .NET fork
  • [ ] @weitzhandler's implementation
• [ ] Pull the best from all 3 in a way that meets the pre-approved API surface and performs well w/o unnecessary allocations.
• [ ] Submit a PR that includes testing for compatibility scenarios.

My over-arching concern is that we implement this in a way that does not break subclasses that already try to implement this functionality.

Once we establish that this implementation meets the API surface already approved, and doesn't break compatibility at this level, we can decide if the functions can be moved further down the stack without breaking anything else. But I don't think we should confuse the two right now, this whole process has been hard enough to follow ;).

Thoughts?

[weitzhandler]

In my implementation I added the following features:

• Collection avoids raising notifications and events when unnecessary and avoids redundant actions, here's a couple of examples
  • Clearing collection when already empty
  • Added range is an empty collection
• The following methods:
  • public void AddRange(IEnumerable<T> collection)
  • public void InsertRange(int index, IEnumerable<T> collection)
  • public void RemoveRange(IEnumerable<T> collection)
  • public void RemoveRange(int index, int count)
  • public void ReplaceRange(IEnumerable<T> collection) //clears and adds
• Stack events and notifications to the minimum possible

Additionally I'd want to add a new property, something like ReuseItems, which when set to true, adding or inserting an item already in the collection (using a comparer) will result in no action. And you must think 'hey, searching the collection has a performance cost', and you're right, but since adding and resetting slots in ObservableCollection is the major performance issue, because any insert or replace potentially causes template creation and UI change, so the optimization goal in ObservableCollection should be avoiding unnecessary collection changes, even if it comes with an slight cost from the background thread (e.g. ViewModel), especially since it was requested on demand setting that property. But that I'll leave for later.

@robertmclaws Since your last message I backed out to give you the honor of implementing it, also because you're the one who opened the issue and already worked on a PR before. Are you still working on this? Otherwise I'd be happy to be assigned. @karelz

[karelz]

Looks like @robertmclaws didn't have time to work on it. If you have implementation of the approved API surface, feel free to submit a PR @weitzhandler.

[OsirisTerje]

@robertmclaws @weitzhandler @karelz Any progress on this?

[weitzhandler]

API Review 2nd round

In order of appearance in code

See implementation and explanations in PR dotnet/corefx#26482.

• [x] Inserts a range at the end. public void AddRange(IEnumerable<T> collection);
• [x] Inserts a range public void InsertRange(int index, IEnumerable<T> collection);
• [x] Removes a range. public void RemoveRange(int index, int count);
• [ ] Removes the first occurence of each item in the specified collection public void RemoveRange(IEnumerable<T> collection);
• [x] Removes only matching items. public int RemoveAll(Predicate<T> match);
• [ ] Removes only matching items, constraining the search to a specific range in the collection. public int RemoveAll(int index, int count, Predicate<T> match);
• [ ] Clears the current collection and replaces it with the specified collection using default eq. comparer. public void ReplaceRange(IEnumerable<T> collection);
• [ ] Clears the current collection and replaces it with the specified collection using specified comparer. public void ReplaceRange(IEnumerable<T> collection, IEqualityComparer<T> comparer);
• [x] Repalces a range with fewer, equal, or more items, reusing equal items in similar indices. public void ReplaceRange(int index, int count, IEnumerable<T> collection);
• [ ] Repalces a range with fewer, equal, or more items, using the specified comparer to skip equal items in equal indices. public void ReplaceRange(int index, int count, IEnumerable<T> collection, IEqualityComparer<T> comparer);

Legend:

• [x] API approved
• [ ] API proposed

Notes:

• All methods above are implemented and tested, some not as extensively as they should. It's up to you guys to decide what remains here (will add more tests upon API verdict).
• In addition to the proposed API, some optimizations were added to the existing methods, to reduce chance of raising unnecessary events, for example, adding a range with an empty collection will do nothing. Similarly clearing an empty collection will do nothing, and some more situations.
• We would also want to decide whether to make some of the methods virtual, or even bring some of them (specifically does existing in List<T>), down to Collection<T> (The base of ObservableCollection<T>).
• We should decide which of them tunnel down to base and which stand for themselves as virtual/sealed (see this comment).
• Most of the overloaded methods tunnel down to one of the lower level methods, so code is reused rather then just pasted out. After we decide on what API sticks with us, we maybe want to clean down the code even further.

[karelz]

Great, that's useful. Let's first wait on first wave of feedback and when we are in general ok, we can run these new APIs by API review. Thanks for your PR!

[weitzhandler]

@thomaslevesque commented on Sep 16, 2016 public void ReplaceRange(IEnumerable<T> source, IEnumerable<T> replacement) { } //Might not be plausible, but should be attempted.

I'm not sure about this one. It would have to do a linear search for each item in source, which would result in O(m*n) complexity.

First of all, List<T> also exposes a similar method, that also iterates in an O(n) complexity. Secondly, I think that in ObservableCollection<T> that its purpose was initially introduced for XAML based UIs (if I remember correctly), a more important aspect is saving UI performance, and that is made by raising the least Reset events possible, and as more range events, even with a small extra O(m) cost, that that is developer is aware of (as explained in the docs).

The more I think about it, the less I like the idea of ReplaceRange. We already realized that we had very different ideas of how it should work, and anyway, I don't think replacing items by batch like this is a common scenario (at least I can't think of a single time where I needed that).

I have to disagree with you. I have personally bumped in several scenarios where I needed this functionality. For example maintaining a suggestion drop down collection or a filtered list, or plenty other scenarios where this is essential.

[thomaslevesque]

First of all, List also exposes a similar method,

List<T>.RemoveAll isn't similar at all to the proposed ReplaceRange method. It takes a predicate, not a list of items to remove, so it can iterate the list in O(n) to find items to remove. That being said, I was mistaken in saying that the complexity would be O(n*m); by turning source and replacement to a dictionary, it could be done in O(n).

Still, I found the proposed API a bit weird; maybe it should directly accept a dictionary, instead of two collections.

[weitzhandler]

@thomaslevesque commented Jan 21, 2018 List.RemoveAll isn't similar at all to the proposed ReplaceRange method.

Sorry, I was talking about the RemoveAll method, and once that is in, we would want to consider having a ReplaceRange that achieves a similar goal.

Still, I found the proposed API a bit weird; maybe it should directly accept a dictionary, instead of two collections.

Please read this, this is the current implementation of my recent PR (#26482), I implemented and tested them all, for you to decide which remains in, which one gets down to Collection<T> as a virtual method, and which should just become locally virtual.

---

@thomaslevesque commented on Sep 16, 2016 This makes me think... there are lots of possible combination of changes you might want to do on the collection without triggering events for each one. So instead of trying to think of each case and introduce a new method for each, perhaps we should lean toward a more generic solution. Something like this:

using (collection.DeferCollectionChangedNotifications())
{
    collection.Add(...);  // no event raised
    collection.Add(...); // no event raised
    // ...
} // event raised here for all changes

Should I implement this in my PR?

[jnm2]

Should I implement this in my PR?

I don't know, but I certainly make heavy use of that pattern.

[weitzhandler]

@thomaslevesque @jnm2 OK it's been addressed: c06d271.

[thomaslevesque]

Should I implement this in my PR?

I think it's out of scope for this issue. It would certainly be useful, but it should probably be part of a separate proposal.