[Bug]: SourceList.EditDiff ignores duplicates in new list

オープン
  • 何か問題がありますか？
#1,072 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
35/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
csharp
領域
backend

調査の方向性

Start with the EditDiff tests and the existing SourceList.EditDiff implementation; run the proposed duplicate-item test to confirm the failure. Check how the method handles equality and repeated items, and consider the stated performance tradeoff before choosing an approach. Done means the cache contains both equal items and emits one message for the change.

索引モデルが issue の本文から書いたものです。

説明

bug
Describe the bug 🐞

When calling SourceList.EditDiff with duplicate items which already have an equal item in the SourceList, the new items do not match the wanted items.

Step to reproduce

In the EditDiff tests, add test

[Fact]
public void EditDiffWithDuplicates()
{
    // Person("Name" + 1, 1) already exists in _cache.
    Person[] newPeople = [new Person("Name" + 1, 1), new Person("Name" + 1, 1)];

    _cache.EditDiff(newPeople, Person.NameAgeGenderComparer);

    _cache.Count.Should().Be(2);
    _cache.Items.Should().BeEquivalentTo(newPeople);
    _result.Messages.Count.Should().Be(1);
}

This will fail with: Expected _cache.Count to be 2, but found 1.

Reproduction repository
Expected behavior

AI suggests this implementation based on https://en.wikipedia.org/wiki/Longest_common_subsequence. This would also solve https://github.com/reactivemarbles/DynamicData/issues/402. Though performance will be worse than the current implementation. It might make sense to at least provide a flag which defines whether to use a slower but order- and duplicate-aware implementation.

source.Edit(list =>
{
    var eq = equalityComparer ?? EqualityComparer<T>.Default;
    var oldList = list.AsArray();
    var newList = items.AsArray();

    // Build LCS table
    int oldLen = oldList.Length;
    int newLen = newList.Length;
    var dp = new int[oldLen + 1, newLen + 1];

    for (int i = oldLen - 1; i >= 0; i--)
    {
        for (int j = newLen - 1; j >= 0; j--)
        {
            if (eq.Equals(oldList[i], newList[j]))
                dp[i, j] = dp[i + 1, j + 1] + 1;
            else
                dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j + 1]);
        }
    }

    // Walk the LCS table to produce removes and inserts.
    // We track a `listIndex` which is the current index into
    // the mutating list as we apply operations.
    int oi = 0, ni = 0, listIndex = 0;

    while (oi < oldLen && ni < newLen)
    {
        if (eq.Equals(oldList[oi], newList[ni]))
        {
            // Matched in LCS — keep this item
            oi++;
            ni++;
            listIndex++;
        }
        else if (dp[oi + 1, ni] >= dp[oi, ni + 1])
        {
            // Removing from old list is at least as good
            list.RemoveAt(listIndex);
            oi++;
        }
        else
        {
            // Insert from new list
            list.Insert(listIndex, newList[ni]);
            ni++;
            listIndex++;
        }
    }

    // Remove remaining old items
    while (oi < oldLen)
    {
        list.RemoveAt(listIndex);
        oi++;
    }

    // Insert remaining new items
    while (ni < newLen)
    {
        list.Insert(listIndex, newList[ni]);
        ni++;
        listIndex++;
    }
});
Screenshots 🖼️

No response

IDE

No response

Operating system

No response

Version

No response

Device

No response

DynamicData Version

9.4.31

Additional information ℹ️

No response

主要言語
C#
スター
1.9k
フォーク
194
平均マージ
12分
マージ済み PR（30日）
1

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

reactivemarbles/DynamicData のほかの issue

reactivemarbles/DynamicData の issue をすべて見る

似ている issue

C# の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。