[Undo]c# unmanagedデータ用の差分Undo

はじめに

なぜ私は連日Undoについての記事を書いているのか。数日前にコマンドパターンでUndoを実装しました。

実際使ってみると綺麗にコマンドにできる物がなく、メメントコマンドばかりを使うことになりました。

これではダメだと思い、そういえばc#は全てのオブジェクトサイズがbyte単位だったなということで、unmanagedの構造体について、byte単位で差分をとってRedo Undo管理するものを作ってみました。

注意

今回私が実装したのは、unmanaged専用のUndoです。少しでも参照(class)が絡んでいるデータを扱うことはできないということです。

対象にしたい事が多いであろう配列は固定長配列を構造体で定義するなど工夫しなければいけません。(テストコードを参考にどうぞ)

コード

public class DiffHistory<T> where T : unmanaged
{
    const int MaxSize = 4;
    // appliedDiffCount は[0,MaxSize]の間を変化する
    // appliedDiffCount = activeCountのとき,最新(もうRedoできない)
    // appliedDiffCount = 0 のとき,適用したコマンドはない(もうUndoできない)
    int appliedDiffCount = 0;
    List<ByteDiff>[] history = new List<ByteDiff>[MaxSize];
    int ringStart;
    int activeCount;
    T current;
    public T Current => current;
    public DiffHistory(in T first)
    {
        current = first;
    }
    public void Add(ref T newState)
    {
        var diffs = GetDiff(ref current, ref newState);
        Apply(diffs, ref current);
        // appliedDiffCount が,0の時も,MaxSizeの時も、[ringStart]を更新する
        history[(appliedDiffCount + ringStart) % MaxSize] = diffs;
        if (appliedDiffCount < MaxSize)//パンパンじゃないとき
        {
            activeCount = ++appliedDiffCount;
        }
        else//パンパンの時
        {
            ringStart = (ringStart + 1) % MaxSize;
        }
    }
    void GetActiveCommand(int index, out List<ByteDiff> diff)
    {
        if (index < activeCount) diff = history[(index + ringStart) % MaxSize];
        else throw new IndexOutOfRangeException();
    }

    public bool Undo(ref T target)
    {
        // 適用したコマンドの数がNなら、N番[N-1]に登録された処理をUndoする。
        if (appliedDiffCount > 0)
        {
            GetActiveCommand(--appliedDiffCount, out var diff);
            Apply(diff, ref target);
            Apply(diff, ref current);
            return true;
        }
        else if (appliedDiffCount == 0)
        {
            return false;
        }
        else throw new Exception("CommandHistoryで、Undo時に不正な状態が発生しました。適用したコマンドの数はマイナスになってはいけません。");
    }
    public bool Redo(ref T target)
    {
        // 適用したコマンドの数が0なら、1番[0]に登録されたコマンドを適用
        // 適用したコマンドの数がNなら、N+1番[N]に登録されたコマンドを適用
        if (appliedDiffCount < activeCount)
        {
            GetActiveCommand(appliedDiffCount++, out var diff);
            Apply(diff, ref target);
            Apply(diff, ref current);
            return true;
        }
        else if (appliedDiffCount == activeCount)
        {
            return false;
        }
        else throw new Exception("CommandHistoryで、Redo時に不正な状態が発生しました。適用したコマンドの数はredo可能サイズを超えてはいけません。");
    }
    static List<ByteDiff> GetDiff(ref T before, ref T after)
    {
        var diffs = new List<ByteDiff>();

        // T を Span<byte> として扱う
        Span<byte> spanBefore = MemoryMarshal.AsBytes(MemoryMarshal.CreateSpan(ref before, 1));
        Span<byte> spanAfter = MemoryMarshal.AsBytes(MemoryMarshal.CreateSpan(ref after, 1));

        for (int i = 0; i < spanBefore.Length; i++)
        {
            byte xor = (byte)(spanBefore[i] ^ spanAfter[i]);
            if (xor != 0)
            {
                diffs.Add(new ByteDiff(i, xor));
            }
        }

        return diffs;
    }
    static void Apply(List<ByteDiff> diffs, ref T target)
    {
        Span<byte> targetSpan = MemoryMarshal.AsBytes(MemoryMarshal.CreateSpan(ref target, 1));
        foreach (var diff in diffs)
        {
            targetSpan[diff.Index] = (byte)(targetSpan[diff.Index] ^ diff.Value);
        }
    }
    readonly struct ByteDiff
    {
        public ByteDiff(int index, byte value)
        {
            Index = index;
            Value = value;
        }

        public int Index { get; }
        public byte Value { get; }
    }
}

テスト用コード

class Program
{
    static void Main()
    {
        TestString str = new();
        DiffHistory<TestString> history = new(str);
        Console.WriteLine($"初期状態 : {str.ToString()}");

        while (true)
        {
            Console.WriteLine("文字列を入力するか、コマンドを入力(z,y,e)");
            var input = Console.ReadLine();
            if (input == "z")
            {
                if (history.Undo(ref str))
                {
                    Console.WriteLine($"undoしました : {str.ToString()}");
                }
                else Console.WriteLine("undoはもうできません");
            }
            else if (input == "y")
            {
                if (history.Redo(ref str))
                {
                    Console.WriteLine($"redoしました : {str.ToString()}");
                }
                else Console.WriteLine("redoできません");
            }
            else if (input == "e") break;
            else
            {
                str.Add(input);
                history.Add(ref str);
                Console.WriteLine($"TRY追加 : {str.ToString()}");
            }
        }
    }
}
public struct TestString
{
    int count;
    char a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
    Span<char> AsSpan() => MemoryMarshal.CreateSpan(ref a0, 20);
    public bool Add(char c)
    {
        if(count != 20)
        {
            AsSpan()[count++] = c;
            return true;
        }
        return false;
    }
    public void Add(string s)
    {
        var chars = s.AsSpan();
        foreach(var c in chars)
        {
            if (!Add(c)) return;
        }
    }
    public override string ToString()
    {
        return new string(AsSpan().Slice(0,count));
    }
}