Mantaray manifest's walker is incorrect

[LevilkTheReal]

Context

Bee version: v2.0.0 System info/Environment: The issue is not related to these.

Summary

Mantaray manifest is a trie. By definition when we walk through on each node in the trie it should happen in an order. The current implementation does not care about the order.

At SolarPunk we are working on the ACT feature with Viktor. One of our component in ACT relies on this attribute. Viktor suggested that we should fix the original implementation and not to create our own.

Expected behavior

When we walk through a trie we should visit nodes in an order. The same order every time.

Actual behavior

Location: pkg/manifest/mantaray/walker.go

What's happening?

func walkNode(ctx context.Context, path []byte, l Loader, n *Node, walkFn WalkNodeFunc) error {
    if n.forks == nil {
        if err := n.load(ctx, l); err != nil {
            return err
        }
    }

    err := walkNodeFnCopyBytes(ctx, path, n, nil, walkFn)
    if err != nil {
        return err
    }

    for _, v := range n.forks {
        nextPath := append(path[:0:0], path...)
        nextPath = append(nextPath, v.prefix...)

        err := walkNode(ctx, nextPath, l, v.Node, walkFn)
        if err != nil {
            return err
        }
    }

    return nil
}

Here afor ... range is used to go through on the map[byte]*fork forks. Since Go 1 the runtime randomizes map iteration order. So the order will be different every time. The tests only check the existence of paths and do not care about the order thus the tests did not catch this issue.

Steps to reproduce

To prove this issue you can play with TestWalkNode: pkg/manifest/mantaray/walker_test.go. Check the expected paths and the order will be different based on what range does.

Possible solution

There a couple of solutions. A simple sort of the keys of the forks map seems efficent enough in this case: For instance:

    keys := make([]byte, 0, len(n.forks))
    for k := range n.forks {
        keys = append(keys, k)
    }

    sort.Slice(keys, func(i, j int) bool { return keys[i] < keys[j] })

    for _, k := range keys {
        v := n.forks[k]
        nextPath := append(path[:0:0], path...)
        nextPath = append(nextPath, v.prefix...)

        err := walkNodeInSequence(ctx, nextPath, l, v.Node, walkFn)
        if err != nil {
            return err
        }
    }

P.S: We gonna come up with a fix. Also I'd like to remove this fn:

func (n *Node) Walk(ctx context.Context, root []byte, l Loader, walkFn WalkFunc) error {
    node, err := n.LookupNode(ctx, root, l)
    if err != nil {
        return walkFn(root, false, err)
    }
    return walk(ctx, root, []byte{}, l, node, walkFn)
}

I can't see any reference to this. Seems unused.