Create High Performance, Trait Driven 'build your own' Tree Mechanism

[Sewer56]

Improvement

Currently

We have only one FileTree implementation, which is tailored specifically to use in NexusMods.App's LoadoutSynchronizer and FOMOD installer.

We want

When working on the Advanced Installer Functionality, a need to display a file tree of existing game folders arose.

Specifically, displaying existing files in Game directory and Saves directory.

This involves reading the directory structure of the game, and displaying it into UI.

Originally I considered:

• Adding an method into GameInstallation for building a file tree.

  • But that would just essentially be creating a FileTree from folder, which should be in this library.

• Adding an extension method to this library that emits a FileTree from AbsolutePath.

  • But then, a breaking change to library would be introduced once it can be replaced with a better tree.
  • If I use it in App anyway, I'd have to eventually rework app code to adjust to that change.
  • This creates more work in the long run, which is inefficient for business.

Therefore while it's technically not blocking; it's very much blocking in the sense that long term, this will lead to more work.

Design

Here is an example of how you can write trees using traits:

/// <summary>
///     An interface used by Tree implementations to indicate that they have a keyed child.
/// </summary>
/// <typeparam name="TKey">The name of the key used in the File Tree.</typeparam>
/// <typeparam name="TSelf">The type of the child stored in this FileTree.</typeparam>
public interface IHaveChildrenWithKey<TKey, TSelf>
    where TSelf : struct, IHaveChildrenWithKey<TKey, TSelf>
    where TKey : notnull
{
    /// <summary>
    ///     A Dictionary containing all the children of this node.
    /// </summary>
    /// <remarks>
    ///     This should point to an empty dictionary if there are no items.
    /// </remarks>
    public Dictionary<TKey, ChildrenWithKeyBox<TKey, TSelf>> Children { get; }
}

/// <summary>
///     A boxed element that implements <see cref="IHaveChildrenWithKey{TKey,TSelf}" />
/// </summary>
/// <remarks>
///     This is a helper class that boxes a constrained generic structure type.
///     While generic reference types share code (and are thus slower),
///     Generic structures can participate in devirtualization, and thus create
///     zero overhead abstractions.
/// </remarks>
public class ChildrenWithKeyBox<TKey, TSelf>
    where TSelf : struct, IHaveChildrenWithKey<TKey, TSelf>
    where TKey : notnull
{
    /// <summary>
    ///     Contains item deriving from <see cref="IHaveChildrenWithKey{TKey,TSelf}" />
    /// </summary>
    public TSelf Item;

    /// <summary />
    public static implicit operator TSelf(ChildrenWithKeyBox<TKey, TSelf> box)
    {
        return box.Item;
    }

    /// <summary />
    public static implicit operator ChildrenWithKeyBox<TKey, TSelf>(TSelf item)
    {
        return new ChildrenWithKeyBox<TKey, TSelf> { Item = item };
    }
}

/// <summary>
///     Trait methods for <see cref="IHaveChildrenWithKey{TKey,TSelf}" />.
/// </summary>
// ReSharper disable once InconsistentNaming
public static class IHaveChildrenWithKeyExtensions
{
    /// <summary>
    ///     Enumerates all child nodes of the current node in a depth-first manner.
    /// </summary>
    /// <param name="item">The node whose children are to be enumerated.</param>
    /// <typeparam name="TKey">The type of key used to identify children.</typeparam>
    /// <typeparam name="TSelf">The type of child node.</typeparam>
    /// <returns>An IEnumerable of all child nodes of the current node.</returns>
    public static IEnumerable<KeyValuePair<TKey, ChildrenWithKeyBox<TKey, TSelf>>> EnumerateChildren<TSelf, TKey>(
        this TSelf item)
        where TSelf : struct, IHaveChildrenWithKey<TKey, TSelf>
        where TKey : notnull
    {
        foreach (var child in item.Children)
        {
            yield return child;
            foreach (var tuple in child.Value.Item.EnumerateChildren<TSelf, TKey>())
                yield return tuple;
        }
    }

    /// <summary>
    ///     Counts the number of direct child nodes of the current node.
    /// </summary>
    /// <param name="item">The node whose children are to be counted.</param>
    /// <typeparam name="TKey">The type of key used to identify children.</typeparam>
    /// <typeparam name="TSelf">The type of child node.</typeparam>
    /// <returns>The count of direct child nodes.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int CountChildren<TSelf, TKey>(this TSelf item)
        where TSelf : struct, IHaveChildrenWithKey<TKey, TSelf>
        where TKey : notnull
    {
        var result = 0;
        item.CountChildrenRecursive<TSelf, TKey>(ref result);
        return result;
    }

    /// <summary>
    ///     Enumerates all child nodes of this current node.
    /// </summary>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static void CountChildrenRecursive<TSelf, TKey>(this TSelf item, ref int accumulator)
        where TSelf : struct, IHaveChildrenWithKey<TKey, TSelf> where TKey : notnull
    {
        accumulator += item.Children.Count;
        foreach (var child in item.Children)
            child.Value.Item.CountChildrenRecursive<TSelf, TKey>(ref accumulator);
    }
}

To use it, simply create a tree type and implement the interface

public struct TestTree : IHaveChildrenWithKey<RelativePath, TestTree>
{
    public TestTree() { }

    public Dictionary<RelativePath, ChildrenWithKeyBox<RelativePath, TestTree>> Children { get; } = new();
}

And you can now call methods provided by these interfaces:

// Note: We can re-export these methods to avoid need of using generics
item.EnumerateChildren<TestTree, RelativePath>();
item.CountChildren<TestTree, RelativePath>();

Note that this approach is zero overhead. i.e. It's as good as if written directly into class.

[Sewer56]

I already started some work on this when I was experimenting on enhanced-filetree branch.

Here are some notes I took down for myself

❌ means TODO
⚡ means 'requires specialized implementations' (non-traitable)
✅ means already implemented.

- ✅ GetSiblings | IHaveChildrenWithKey, IHaveParent
- ✅ ReconstructPath | IHaveParent, IHavePathSegment
- ✅ GetAllDescendantsAsDictionary | IHaveChildrenWithKey
- ✅ FindNode | IHaveChildrenWithKey, IHavePathSegment, IHaveFullPath
- ✅ FindSubPath | IHaveChildrenWithKey, IHavePathSegment
- ❌ AddChildren | IHaveParent, IHaveDepth, IHaveChildren
- ❌ AddChild | IHaveParent, IHaveDepth, IHaveChildren

- ⚡ CreateTree(IEnumerable<KeyValuePair<TPath, TValue>> files)
- ❓ Deconstruct
- ✅ GetAllChildren a.k.a. GetAllNodes | IHaveChildren, IHaveChildrenWithKey
- ✅ CountFiles | IHaveAFileOrDirectory
- ✅ CountDirectories | IHaveAFileOrDirectory
- ✅ CountDescendants

In any case, this is being delayed till next milestone.

Edit: This is outdated, check the wiki in enhanced-filetree branch for current status