nip/tests/test_merkle_tree.nim

## Test suite for Merkle Tree implementation

import unittest
import std/[options]
import ../src/nimpak/merkle_tree

suite "Merkle Tree Building":
  test "Build tree from empty file list":
    let files: seq[FileEntry] = @[]
    let result = buildTreeFromFiles(files, "xxh3")

    check result.isOk
    let tree = result.get()
    check tree.nodeCount == 1
    check tree.leafCount == 1
    check tree.root.hash.len > 0

  test "Build tree from single file":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ]
    let result = buildTreeFromFiles(files, "xxh3")

    check result.isOk
    let tree = result.get()
    check tree.nodeCount == 1
    check tree.leafCount == 1
    check tree.root.path == "file1.txt"
    check tree.root.hash == "xxh3-abc123"

  test "Build tree from multiple files":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200),
      FileEntry(path: "file3.txt", hash: "xxh3-ghi789", size: 300)
    ]
    let result = buildTreeFromFiles(files, "xxh3")

    check result.isOk
    let tree = result.get()
    check tree.leafCount == 3
    check tree.nodeCount > 3  # Should have internal nodes
    check tree.root.hash.len > 0

  test "Tree structure is deterministic":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ]

    let result1 = buildTreeFromFiles(files, "xxh3")
    let result2 = buildTreeFromFiles(files, "xxh3")

    check result1.isOk
    check result2.isOk
    check result1.get().root.hash == result2.get().root.hash

  test "Files are sorted by path":
    let files = @[
      FileEntry(path: "zzz.txt", hash: "xxh3-zzz", size: 100),
      FileEntry(path: "aaa.txt", hash: "xxh3-aaa", size: 200),
      FileEntry(path: "mmm.txt", hash: "xxh3-mmm", size: 300)
    ]

    let result = buildTreeFromFiles(files, "xxh3")
    check result.isOk

    let tree = result.get()
    let leaves = getAllLeaves(tree)
    check leaves[0].path == "aaa.txt"
    check leaves[1].path == "mmm.txt"
    check leaves[2].path == "zzz.txt"

suite "Merkle Tree Verification":
  test "Verify valid tree":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ]

    let buildResult = buildTreeFromFiles(files, "xxh3")
    check buildResult.isOk

    let tree = buildResult.get()
    let verifyResult = verifyTree(tree)
    check verifyResult.isOk
    check verifyResult.get() == true

  test "Get verification statistics":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200),
      FileEntry(path: "file3.txt", hash: "xxh3-ghi789", size: 300)
    ]

    let buildResult = buildTreeFromFiles(files, "xxh3")
    check buildResult.isOk

    let tree = buildResult.get()
    let statsResult = verifyTreeWithStats(tree)
    check statsResult.isOk

    let stats = statsResult.get()
    check stats.totalNodes == tree.nodeCount
    check stats.verifiedNodes > 0
    check stats.failedNodes == 0

suite "Merkle Tree Incremental Updates":
  test "Add file to tree":
    var tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let oldRootHash = tree.root.hash
    let result = tree.addFile("file2.txt", "xxh3-def456", 200)

    check result.isOk
    let newRootHash = result.get()
    check newRootHash != oldRootHash
    check tree.leafCount == 2

  test "Update file in tree":
    var tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let oldRootHash = tree.root.hash
    let result = tree.updateFile("file1.txt", "xxh3-newHash", 150)

    check result.isOk
    let newRootHash = result.get()
    check newRootHash != oldRootHash
    check tree.leafCount == 2

  test "Remove file from tree":
    var tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let oldRootHash = tree.root.hash
    let result = tree.removeFile("file1.txt")

    check result.isOk
    let newRootHash = result.get()
    check newRootHash != oldRootHash
    check tree.leafCount == 1

  test "Apply multiple changes":
    var tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let changes = @[
      FileChange(path: "file2.txt", changeType: Added, newHash: some("xxh3-def456"), newSize: some(200'i64)),
      FileChange(path: "file3.txt", changeType: Added, newHash: some("xxh3-ghi789"), newSize: some(300'i64)),
      FileChange(path: "file1.txt", changeType: Modified, newHash: some("xxh3-modified"), newSize: some(150'i64))
    ]

    let result = tree.applyChanges(changes)
    check result.isOk
    check tree.leafCount == 3

  test "Get update statistics":
    var tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let changes = @[
      FileChange(path: "file2.txt", changeType: Added, newHash: some("xxh3-def456"), newSize: some(200'i64))
    ]

    let result = tree.applyChangesWithStats(changes)
    check result.isOk

    let stats = result.get()
    check stats.changesApplied == 1
    check stats.oldRootHash != stats.newRootHash

suite "Merkle Tree Diffing":
  test "Diff identical trees":
    let files = @[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ]

    let tree1 = buildTreeFromFiles(files, "xxh3").get()
    let tree2 = buildTreeFromFiles(files, "xxh3").get()

    let result = diffTrees(tree1, tree2)
    check result.isOk
    check result.get().len == 0

  test "Diff trees with added file":
    let tree1 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let tree2 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let result = diffTrees(tree1, tree2)
    check result.isOk

    let diffs = result.get()
    check diffs.len == 1
    check diffs[0].path == "file2.txt"
    check diffs[0].diffType == OnlyInSecond

  test "Diff trees with removed file":
    let tree1 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let tree2 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let result = diffTrees(tree1, tree2)
    check result.isOk

    let diffs = result.get()
    check diffs.len == 1
    check diffs[0].path == "file2.txt"
    check diffs[0].diffType == OnlyInFirst

  test "Diff trees with modified file":
    let tree1 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let tree2 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-modified", size: 150)
    ], "xxh3").get()

    let result = diffTrees(tree1, tree2)
    check result.isOk

    let diffs = result.get()
    check diffs.len == 1
    check diffs[0].path == "file1.txt"
    check diffs[0].diffType == Different

  test "Get diff statistics":
    let tree1 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let tree2 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-modified", size: 150),
      FileEntry(path: "file3.txt", hash: "xxh3-ghi789", size: 300)
    ], "xxh3").get()

    let result = getDiffStats(tree1, tree2)
    check result.isOk

    let stats = result.get()
    check stats.onlyInFirst == 1  # file2.txt
    check stats.onlyInSecond == 1  # file3.txt
    check stats.different == 1  # file1.txt modified
    check stats.identical == 0

  test "Quick change detection":
    let tree1 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let tree2 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let tree3 = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-modified", size: 150)
    ], "xxh3").get()

    check not hasChanges(tree1, tree2)  # Identical
    check hasChanges(tree1, tree3)  # Different

suite "Merkle Tree Helper Functions":
  test "Find leaf by path":
    let tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200)
    ], "xxh3").get()

    let leaf = findLeafInTree(tree, "file1.txt")
    check leaf.isSome
    check leaf.get().path == "file1.txt"
    check leaf.get().hash == "xxh3-abc123"

  test "Find non-existent leaf":
    let tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let leaf = findLeafInTree(tree, "nonexistent.txt")
    check leaf.isNone

  test "Get all leaves":
    let tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100),
      FileEntry(path: "file2.txt", hash: "xxh3-def456", size: 200),
      FileEntry(path: "file3.txt", hash: "xxh3-ghi789", size: 300)
    ], "xxh3").get()

    let leaves = getAllLeaves(tree)
    check leaves.len == 3

  test "Get root hash":
    let tree = buildTreeFromFiles(@[
      FileEntry(path: "file1.txt", hash: "xxh3-abc123", size: 100)
    ], "xxh3").get()

    let rootHash = getRootHash(tree)
    check rootHash.len > 0
    check rootHash == tree.root.hash