Diffing and Dependency Order

Two helpers for working with sets of related items. DiffWith compares an old and a new version of a collection and tells you what to insert, delete and update, which is what you need to sync a database table, a cache or a UI list. TopologicalSort puts items in an order where each one comes after the things it depends on, such as a build order, a migration order or a service start-up order.

At a glance

Method	What it does
DiffWith	Compares two versions of a collection by key and returns a CollectionDiff<T>.
CollectionDiff<T>.Added	Items whose key exists only in the new version.
CollectionDiff<T>.Removed	Items whose key exists only in the old version.
CollectionDiff<T>.Changed	(Old, New) pairs with the same key whose values differ.
CollectionDiff<T>.Unchanged	(Old, New) pairs with the same key and equal values.
CollectionDiff<T>.HasChanges	true when anything was added, removed or changed.
TopologicalSort	Orders items so that dependencies come first.
CyclicDependencyException	Thrown by TopologicalSort when the dependencies form a cycle.
CyclicDependencyException.Cycle	The items in the cycle; the first item is repeated at the end.

DiffWith and TopologicalSort are extension methods on IEnumerable<T>. They live, together with CollectionDiff<T> and CyclicDependencyException, in the System.Collections.Generic namespace, so they need no extra using.

Diffing two versions

DiffWith

Signature

public static CollectionDiff<T> DiffWith<T, TKey>(
    this IEnumerable<T> oldItems,
    IEnumerable<T> newItems,
    Func<T, TKey> keySelector,
    IEqualityComparer<T>? valueComparer = null,
    IEqualityComparer<TKey>? keyComparer = null)

DiffWith matches the items of two versions by a key, usually the primary key. An item whose key appears only in the new version is added. An item whose key appears only in the old version is removed. When a key appears in both versions, the two items are compared with valueComparer. If they differ, the pair is changed. Otherwise it is unchanged.

What changed in the catalog

public sealed record Product(int Id, string Name);

Product[] saved =
{
    new Product(1, "Keyboard"),
    new Product(2, "Mouse"),
    new Product(3, "Monitor"),
};

Product[] incoming =
{
    new Product(2, "Mouse"),
    new Product(3, "Monitor 27-inch"),
    new Product(4, "Webcam"),
};

CollectionDiff<Product> diff = saved.DiffWith(incoming, p => p.Id);

IEnumerable<string> added = diff.Added.Select(p => p.Name);         // → ["Webcam"]
IEnumerable<string> removed = diff.Removed.Select(p => p.Name);     // → ["Keyboard"]
IEnumerable<(string, string)> changed = diff.Changed
    .Select(pair => (pair.Old.Name, pair.New.Name));                // → [("Monitor", "Monitor 27-inch")]
int unchanged = diff.Unchanged.Count;                               // → 1
bool hasChanges = diff.HasChanges;                                  // → true

Comparing a collection with itself, or two empty collections, gives a diff with no changes:

No changes

CollectionDiff<Product> same = saved.DiffWith(saved, p => p.Id);

bool hasChanges = same.HasChanges;      // → false
int unchanged = same.Unchanged.Count;   // → 3
int added = same.Added.Count;           // → 0

CollectionDiff<Product> empty = Array.Empty<Product>().DiffWith(Array.Empty<Product>(), p => p.Id);
bool emptyHasChanges = empty.HasChanges; // → false

Default equality decides "changed"

Without a valueComparer, DiffWith uses EqualityComparer<T>.Default. Records and structs compare by value, so they work as you expect. A plain class compares by reference, so two separate instances with the same data count as changed. If you load the old version from a database and the new version from a file, every matched item then lands in Changed. Use a record, override Equals, or pass a valueComparer.

Null, duplicates and order

• oldItems, newItems or keySelector being null throws ArgumentNullException with that parameter name.
• A key that appears twice in the same version throws ArgumentException. The parameter name is oldItems or newItems, and the message names the key: The key '1' appears more than once. (Parameter 'oldItems').
• A null key is allowed. Items with a null key in both versions are matched with each other.
• Added, Changed and Unchanged follow the order of the new version. Removed follows the order of the old version.
• The diff is computed right away. Each input is enumerated once, and the result does not change if you modify the inputs afterwards.

Custom comparers

Pass a valueComparer to decide what counts as a change. This comparer ignores the case of the product name, so "Monitor" and "MONITOR" are the same value:

Ignore case when comparing values

public sealed class ProductNameIgnoreCaseComparer : IEqualityComparer<Product>
{
    public bool Equals(Product? x, Product? y)
    {
        return string.Equals(x?.Name, y?.Name, StringComparison.OrdinalIgnoreCase);
    }

    public int GetHashCode(Product obj)
    {
        return StringComparer.OrdinalIgnoreCase.GetHashCode(obj.Name);
    }
}

Product[] before = { new Product(1, "Monitor"), new Product(2, "Mouse") };
Product[] after = { new Product(1, "MONITOR"), new Product(2, "Mouse") };

CollectionDiff<Product> diff = before.DiffWith(after, p => p.Id, new ProductNameIgnoreCaseComparer());

int changed = diff.Changed.Count;       // → 0
int unchanged = diff.Unchanged.Count;   // → 2

Pass a keyComparer to decide which keys are the same. Here SKU codes match without regard to case. A named argument skips valueComparer:

Match keys case-insensitively

public sealed record StockLevel(string Sku, int Quantity);

StockLevel[] yesterday = { new StockLevel("kb-100", 12) };
StockLevel[] today = { new StockLevel("KB-100", 12) };

CollectionDiff<StockLevel> diff = yesterday.DiffWith(
    today,
    s => s.Sku,
    keyComparer: StringComparer.OrdinalIgnoreCase);

int added = diff.Added.Count;       // → 0
int removed = diff.Removed.Count;   // → 0
int changed = diff.Changed.Count;   // → 1

The two items share a key, but record equality sees "kb-100" and "KB-100" as different, so the pair is in Changed. The key comparer only decides which items are matched. The value comparer still decides whether they are equal.

CollectionDiff<T>

DiffWith returns a CollectionDiff<T>. It is a sealed, read-only result. It has no public constructor; only DiffWith creates it.

Member	Type	Contents
Added	IReadOnlyList<T>	Items whose key exists only in the new version, in new-version order.
Removed	IReadOnlyList<T>	Items whose key exists only in the old version, in old-version order.
Changed	IReadOnlyList<(T Old, T New)>	Items present in both versions whose values differ.
Unchanged	IReadOnlyList<(T Old, T New)>	Items present in both versions with equal values.
HasChanges	bool	true when Added, Removed or Changed is not empty. Unchanged does not count.

The pairs are named tuples. Read pair.Old and pair.New, or deconstruct them in a foreach:

Reading the pairs

foreach ((Product old, Product updated) in diff.Changed)
{
    string before = old.Name;      // → "Monitor"
    string after = updated.Name;   // → "Monitor 27-inch"
}

Example: sync to a database

A nightly job receives the full customer list from a CRM. Instead of deleting and re-inserting every row, diff the import against what is stored and write only the differences. ICustomerRepository stands for your own data access code.

Sync an import with the database

public sealed record Customer(int Id, string Email, string Name);

public interface ICustomerRepository
{
    Task<IReadOnlyList<Customer>> GetAllAsync(CancellationToken cancellationToken);
    Task InsertAsync(Customer customer, CancellationToken cancellationToken);
    Task UpdateAsync(Customer customer, CancellationToken cancellationToken);
    Task DeleteAsync(int customerId, CancellationToken cancellationToken);
}

public sealed class CustomerImport
{
    private readonly ICustomerRepository _repository;

    public CustomerImport(ICustomerRepository repository)
    {
        _repository = repository;
    }

    public async Task<int> SyncAsync(IReadOnlyList<Customer> imported, CancellationToken cancellationToken)
    {
        IReadOnlyList<Customer> stored = await _repository.GetAllAsync(cancellationToken);
        CollectionDiff<Customer> diff = stored.DiffWith(imported, c => c.Id);

        if (!diff.HasChanges)
        {
            return 0;
        }

        foreach (Customer customer in diff.Added)
        {
            await _repository.InsertAsync(customer, cancellationToken);
        }

        foreach ((Customer _, Customer updated) in diff.Changed)
        {
            await _repository.UpdateAsync(updated, cancellationToken);
        }

        foreach (Customer customer in diff.Removed)
        {
            await _repository.DeleteAsync(customer.Id, cancellationToken);
        }

        return diff.Added.Count + diff.Changed.Count + diff.Removed.Count;
    }
}

With this data, the sync writes three rows and skips one:

What the sync does

Customer[] stored =
{
    new Customer(1, "ana@example.com", "Ana"),
    new Customer(2, "ben@example.com", "Ben"),
    new Customer(3, "chloe@example.com", "Chloe"),
};

Customer[] imported =
{
    new Customer(1, "ana@example.com", "Ana"),
    new Customer(3, "chloe.m@example.com", "Chloe"),
    new Customer(4, "dev@example.com", "Dev"),
};

CollectionDiff<Customer> diff = stored.DiffWith(imported, c => c.Id);

IEnumerable<int> toInsert = diff.Added.Select(c => c.Id);              // → [4]
IEnumerable<int> toUpdate = diff.Changed.Select(pair => pair.New.Id);  // → [3]
IEnumerable<int> toDelete = diff.Removed.Select(c => c.Id);            // → [2]
int skipped = diff.Unchanged.Count;                                    // → 1

tip

The same pattern works for a UI list (add, remove and refresh rows), a cache (evict removed keys) or an audit log (record each Changed pair with its old and new value). To see which properties of a Changed pair differ, call pair.Old.CompareProperties(pair.New), described in Compare, clone and map.

Dependency order

TopologicalSort

Signature

public static IReadOnlyList<T> TopologicalSort<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>?> dependenciesSelector,
    IEqualityComparer<T>? comparer = null)
    where T : notnull

TopologicalSort returns the items so that every item comes after the items it depends on. dependenciesSelector returns what one item depends on. Return null or an empty sequence for an item with no dependencies. When two items do not depend on each other, they keep the input order.

Order modules by their dependencies

Dictionary<string, string[]> dependsOn = new Dictionary<string, string[]>
{
    ["app"] = new[] { "lib", "log" },
    ["lib"] = new[] { "core" },
    ["log"] = new[] { "core" },
    ["core"] = Array.Empty<string>(),
};

string[] modules = { "app", "lib", "log", "core" };

IReadOnlyList<string> order = modules.TopologicalSort(m => dependsOn[m]);
// → ["core", "lib", "log", "app"]

IReadOnlyList<int> independent = new[] { 3, 1, 2 }.TopologicalSort(_ => null);
// → [3, 1, 2]

Dependencies do not have to be in source. Every item that dependenciesSelector returns is added to the result:

Dependencies outside the source are included

Dictionary<string, string[]> dependsOn = new Dictionary<string, string[]>
{
    ["app"] = new[] { "lib" },
    ["lib"] = new[] { "core" },
};

IReadOnlyList<string> order = new[] { "app" }.TopologicalSort(m => dependsOn.GetValueOrDefault(m));
// → ["core", "lib", "app"]

Pass a comparer when two different values mean the same item. With a case-insensitive comparer, "B" satisfies a dependency on "b", and the result holds each item once:

Treat equal items as one

Dictionary<string, string[]> dependsOn = new Dictionary<string, string[]>(StringComparer.OrdinalIgnoreCase)
{
    ["A"] = new[] { "b" },
    ["B"] = Array.Empty<string>(),
};

IReadOnlyList<string> order = new[] { "B", "A" }.TopologicalSort(
    m => dependsOn[m],
    StringComparer.OrdinalIgnoreCase);
// → ["B", "A"]

Null, equality and deep graphs

• source or dependenciesSelector being null throws ArgumentNullException with that parameter name.
• Items must not be null (where T : notnull). Items are matched with comparer, or with EqualityComparer<T>.Default when it is null. For a plain class that means reference equality, so return the same instances from dependenciesSelector or pass a comparer.
• dependenciesSelector is called once for each distinct item.
• The result is a new list, built right away.
• A cycle throws CyclicDependencyException.
• The sort uses an explicit stack instead of recursion, so a chain of 100,000 dependencies does not overflow the call stack.

CyclicDependencyException

When the dependencies loop back on themselves, no valid order exists, and TopologicalSort throws CyclicDependencyException. Its Cycle property lists the items in the loop in dependency order, with the first item repeated at the end. The message shows the same path.

Finding the cycle

Dictionary<string, string[]> dependsOn = new Dictionary<string, string[]>
{
    ["billing"] = new[] { "invoices" },
    ["invoices"] = new[] { "payments" },
    ["payments"] = new[] { "billing" },
};

try
{
    new[] { "billing" }.TopologicalSort(s => dependsOn[s]);
}
catch (CyclicDependencyException ex)
{
    IReadOnlyList<object> cycle = ex.Cycle;  // → ["billing", "invoices", "payments", "billing"]
    string message = ex.Message;             // → "Cyclic dependency detected: billing -> invoices -> payments -> billing"
}

Cycle holds only the items in the loop. Items that lead into the loop are left out. An item that depends on itself is a loop of one:

Only the loop is reported

Dictionary<string, string[]> dependsOn = new Dictionary<string, string[]>
{
    ["checkout"] = new[] { "cart" },
    ["cart"] = new[] { "pricing" },
    ["pricing"] = new[] { "cart" },
};

try
{
    new[] { "checkout" }.TopologicalSort(s => dependsOn[s]);
}
catch (CyclicDependencyException ex)
{
    IReadOnlyList<object> cycle = ex.Cycle;  // → ["cart", "pricing", "cart"]
}

try
{
    new[] { "orders" }.TopologicalSort(s => new[] { s });
}
catch (CyclicDependencyException ex)
{
    IReadOnlyList<object> cycle = ex.Cycle;  // → ["orders", "orders"]
}

info

• CyclicDependencyException derives from InvalidOperationException, so an existing catch (InvalidOperationException) also catches it.
• Cycle is an IReadOnlyList<object>, because the exception is not generic. Cast the items back to your type, for example ex.Cycle.Cast<string>().
• The message uses each item's ToString(). Override ToString() on your item type to get a readable message.
• The constructor is public: new CyclicDependencyException(cycle). A null cycle gives an empty Cycle.

Example: build order

A solution has projects that reference other projects, and each project must build after its references. Here the projects hold direct references to each other, so default reference equality matches them correctly.

Compute a build order

public sealed class Project
{
    public Project(string name, params Project[] references)
    {
        Name = name;
        References = references;
    }

    public string Name { get; }

    public IReadOnlyList<Project> References { get; }

    public override string ToString()
    {
        return Name;
    }
}

Project domain = new Project("Orders.Domain");
Project data = new Project("Orders.Data", domain);
Project api = new Project("Orders.Api", data, domain);
Project tests = new Project("Orders.Tests", api);

Project[] projects = { tests, api, data, domain };

IReadOnlyList<Project> buildOrder = projects.TopologicalSort(p => p.References);
IEnumerable<string> names = buildOrder.Select(p => p.Name);
// → ["Orders.Domain", "Orders.Data", "Orders.Api", "Orders.Tests"]

When the projects are described by name, for example in a configuration file, sort the names and turn a cycle into a configuration error:

Build order from configuration

public static IReadOnlyList<string> GetBuildOrder(Dictionary<string, string[]> references)
{
    try
    {
        return references.Keys.TopologicalSort(name => references.GetValueOrDefault(name));
    }
    catch (CyclicDependencyException ex)
    {
        throw new InvalidOperationException($"The project references contain a cycle: {ex.Message}", ex);
    }
}

Dictionary<string, string[]> references = new Dictionary<string, string[]>
{
    ["Orders.Tests"] = new[] { "Orders.Api" },
    ["Orders.Api"] = new[] { "Orders.Data", "Shared.Logging" },
    ["Orders.Data"] = Array.Empty<string>(),
};

IReadOnlyList<string> order = GetBuildOrder(references);
// → ["Orders.Data", "Shared.Logging", "Orders.Api", "Orders.Tests"]

Shared.Logging is not a key in the dictionary, but it is still placed before the project that uses it. GetValueOrDefault returns null for it, which means it has no dependencies of its own.

See also

• Transforming sequences for other helpers that reshape sequences.
• Querying sequences for filtering and lookup helpers.
• Compare, clone and map for comparing two objects property by property.
• Exceptions and disposables for more on exception helpers.