[Bug]: Moving items behaves differently when using Filter

[luizzeroxis]

Describe the bug 🐞

Probably easier to understand just by looking at the code below but I'll try explaining in text anyway. When using Filter() on a chain starting with a ToObservableChangeSet() on a ObservableCollection, it seems that it changes the way that changes are being handled down the chain, even when the filter does nothing. If you call Move() on the initial collection it does not move the items on the resulting bound ReadOnlyObservableCollection. Some issue also seems to happen if you simply try to swap the places of the items, the index of the change seems to be lost so nothing happens. It makes sense that those things would do nothing when you set a key, since it would be like a dictionary, but it's a list in this case.

Step to reproduce

Simple repro:

ObservableCollection<string> input = new();

input.ToObservableChangeSet()
    .Filter(x => true) // If you remove this line it works as expected
    .Bind(out ReadOnlyObservableCollection<string> output)
    .Subscribe();

input.Add("c");
input.Add("a");
input.Add("b");

input.Move(0, 2); // Move c to last position

Debug.WriteLine($"input:  {String.Join(',', input)}");  // input:  a,b,c
Debug.WriteLine($"output: {String.Join(',', output)}"); // output: c,a,b

Similarly with a swap:

ObservableCollection<string> input = new();

input.ToObservableChangeSet()
    .Filter(x => true) // If you remove this line it works as expected
    .Bind(out ReadOnlyObservableCollection<string> output)
    .Subscribe();

input.Add("c");
input.Add("b");
input.Add("a");

// Swap a and c (curiously if you swap the other way around it works fine)
var temp = input[0];
input[0] = input[2];
input[2] = temp;

Debug.WriteLine($"input:  {String.Join(',', input)}");  // input:  a,b,c
Debug.WriteLine($"output: {String.Join(',', output)}"); // output: c,b,a

Reproduction repository

N/A

Expected behavior

Filter should pass down moves and swaps properly the same as if it wasn't there

Screenshots 🖼️

No response

IDE

Visual Studio 2022

Operating system

Windows

Version

10

Device

No response

DynamicData Version

9.4.1

Additional information ℹ️

Maybe I'm just misunderstanding how this is supposed to work, I'm sorry in advance if I missed something.

[JakenVeina]

This is actually intentional, yeah.

DynamicData/src/DynamicData/List/ObservableListEx.cs

Line 703 in 3d72c9e

public static IObservable<IChangeSet<T>> Filter<T>(this IObservable<IChangeSet<T>> source, IObservable<Func<T, bool>> predicate, ListFilterPolicy filterPolicy = ListFilterPolicy.CalculateDiff)

DynamicData/src/DynamicData/List/ListFilterPolicy.cs

Line 10 in 3d72c9e

public enum ListFilterPolicy

The List filter operators do not preserve ordering, by default. Preserving ordering through a filter operation amounts to having to maintain a map between upstream indexes and downstream indexes, internally, which means frequently having to re-calculate that whole map when items are added/removed/moved within the middle of the list. It's quite inefficient, and ultimately, deemed not worth it to implement by default, when it's very often the case that items are sorted downstream anyway. Having learned about what works well and what doesn't, over the lifetime of the project, we'd probably elect to drop filtering operators entirely from List-land, if we could. We've definitely taken a route more-recently to discourage use of sorted data in the upstream, and always specify sorting as a final-step operation when desired, as per the new .SortAndBind() and similar operators released in the past year.

It IS still possible to just specify the filtering policy as ClearAndReplace in your operators, to have ordering preserved. As the name suggests though, this is going to be the equivalent of fully clearing and resetting the downstream list, on every change, so that could end up making things worse, for performance. I'd definitely recommend just putting in a .Sort() or .SortAndBind() at the bottom of your query, instead.

[luizzeroxis]

I see, it's intentional, but it's not very intuitive that Filter doesn't preserve order by default. Still, even your solution doesn't seem to be working. Replacing the filter line with the following still has the same result.

.Filter(new BehaviorSubject<Func<string, bool>>(x => true), filterPolicy: ListFilterPolicy.ClearAndReplace)

I had to make it an observable since I don't think filterPolicy exists in the simple Func version.

In regards to sorting, I'm not sure that would work in my case, since I require that the exact positions of items stay where they are, the items themselves don't have any information that would determine their positions. Perhaps if somehow the original index could eventually be known in the sort function? That seems unlikely since a change in one place would change all the indexes after it.

[JakenVeina]

Replacing the filter line with the following still has the same result.

Yup, it sure does, doesn't it? Looks like .Filter() just straight-up ignores .Moved changes, no matter what.

I didn't look closely enough at what ListFilterPolicy is actually doing. It doesn't FULLY preserve ordering, as I said it does, it only describes what happens when a RE-filtering is required, I.E. when the entire filter predicate changes, and every item needs to be re-evaluated for whether to be re-added or removed. That's why the version of the operator that takes only a static predicate doesn't take that parameter, a full re-filtering can't actually happen.

The rest of my description above still pretty much applies. Adding support for .Moved changes would add a LOT of inefficiency to the operator. Either the operator needs to maintain a complete map of all item indexes, or it has to do linear searches, internally, to figure out an item's indexes each time it's needed. Either way, it means any add/remove/move changes potentially have to do linear scans of the entire list.

All of that is theoretically doable, but probably not worth a full implementation, when there's alternatives already in place.

That seems unlikely since a change in one place would change all the indexes after it.

That is indeed the core problem of preserving order in a filter operation.

the items themselves don't have any information that would determine their positions.

I think your best bet is going to be to figure out how to add something that you can use to determine order, and then sort on that. In this context, you can probably work around the problem of having to track specific indexes, because you don't really NEED the precise index, you just need something that can determine relative position compared to other items. For example, if you have values 1, 2, 3, 4, and 5, you can remove 3 without having to update 4 and 4 to be 3 and 4, 4 is still greater than 2 and less than 5. And if you were to want to move an item in between 1 and 2, you could set it to 1.5. Obviously, this approach would eventually have a resolution underflow problem, and break, but it might be good enough if you can reasonably assume that your lists will never be too large or too long-lived. You could also implement a full refresh of the sort values after maybe every 100 operations.

I suppose it's possible that this could be used inside DynamicData itself, to support order preservation. I'd want to do some analysis and see how effective it really is, performance-wise. I suspect if you put this together with downstream .Sort()ing, you're still not coming out very well, but for a quick-and-dirty implementation on your end, it seems like it could work.

Alternatively, it wouldn't be THAT much work to write your own .FilterWithOrderingPreserved() operator on your end. You can possibly do things more efficiently than we can, if there's assumptions you can make about your specific data (like not needing to support .Refresh changes, or knowing that your items are immutable). DynamicData is built to be extensible, as long as you can spit out valid IChangeSet<>s for downstream operators.

[luizzeroxis]

Thank you for the insight. I get that you don't want to add such performance heavy stuff to the library, I just wish that it was more clear that ordering isn't generally preserved, since it really caught me off guard in my code, so much that it's why I filed this as a bug. Probably not much that can be done as I imagine the API is quite set in stone at this point.

About adding data that determines the order, well, I don't really like the idea of using fractional and non-consecutive indexes, it's one of those things you do when you want maximum performance regardless of nicety, which I don't think will be a problem in my case. Also, wouldn't this require changing the original ObservableCollection? That's not really possible in my situation since that already comes a library I can't change. Maybe with some in between proxies of some kind, I don't know.

Alternatively, it wouldn't be THAT much work to write your own .FilterWithOrderingPreserved() operator on your end.

It certainly would be a lot of work for me! Since I don't really understand much about how Reactive extensions work or even this library... for example, how do you get the original list? Is that even possible? I'll have to read a lot of code and documentation to write that I guess.

Anyway thanks for replying, it has helped me a lot.

[JakenVeina]

I just wish that it was more clear that ordering isn't generally preserved, since it really caught me off guard in my code

Entirely understandable. I'll see about updating the docs for these operators, specifically, to help clarify.

how do you get the original list? Is that even possible?

Nope, not generally. Changesets only include copies of the items that changed, so If you need to access any arbitrary item in the collection, you have to keep your own cache of the full collection. Most DynamicData operators do this, internally.

When it comes to writing a custom DynamicData operator, you can pretty much always start with...

public static IObservable<IChangeSet<T>> FilterWithOrderingPreserved(
        this    IObservable<IChangeSet<T>>  source,
                Func<T, bool>               predicate)
    => Observable.Create<IChangeSet<T>>(downstreamObserver =>
    {
        var upstreamItems = new List<T>();
        var downstreamItems = new ChangeAwareList<T>();

        return source.SubscribeSafe(Observer.Create<IChangeSet<T>>(
            onNext:         upstreamChangeSet =>
            {
                upstreamItems.Clone(upstreamChangeSet);

                // Inspect the changeset, to decide how to apply each change to downstreamItems.

                return downstreamItems.CaptureChanges();
            },
            onError:        downstreamObserver.OnError,
            onCompleted:    downstreamObserver.OnCompleted);
    });

Probably not much that can be done as I imagine the API is quite set in stone at this point.

Sort of, when it comes to existing operators, but adding new operators is entirely doable. It's just a question of whether it's worth the work, I.E. how much use it would get.