AnnotationList.FindDepthFirst misses descendants in tied containers depending on insertion order #554

AnnotationList.FindDepthFirst can miss a segment inside equal-range sibling containers solely because their insertion order changes. This is separate from #506's skip-list boundary defect.

Reproduced against Machine 259920414132bdd5a85542722d9af5509aed8943 and again with the proposed first-match-in-search-direction fix applied locally. The latter fixes range traversal but leaves this case unchanged. This report concerns the shared annotation API; no HermitCrab grammar reaching the case has been demonstrated.

Two sibling annotations both cover [n0,n2]; only one owns the three segment annotations. Looking up n1 should return its annotation regardless of which sibling was inserted first. Current results:

ownerAddedFirst=True; found=False; foundSegment=False
ownerAddedFirst=False; found=True; foundSegment=True

The non-found path in src/SIL.Machine/Annotations/AnnotationList.cs::FindDepthFirst descends only into the single candidate returned by Find; it does not search another equal-range container when that candidate cannot supply the descendant. A deterministic layout alone cannot resolve this ownership choice.

Minimal console reproduction (reference src/SIL.Machine/SIL.Machine.csproj; reflection sets only the test instance RNG, with no production hook):

using System.Reflection;
using SIL.Machine.Annotations;
using SIL.Machine.DataStructures;
using SIL.Machine.FeatureModel;

foreach (bool ownerAddedFirst in new[] { true, false })
{
    var annotations = new AnnotationList<ShapeNode>();
    typeof(BidirList<Annotation<ShapeNode>>)
        .GetField("_rand", BindingFlags.Instance | BindingFlags.NonPublic)!
        .SetValue(annotations, new Random(0));
    var shape = new Shape(begin => new ShapeNode(FeatureStruct.New().Value), annotations);
    ShapeNode n0 = shape.Add(FeatureStruct.New().Value);
    ShapeNode n1 = shape.Add(FeatureStruct.New().Value);
    ShapeNode n2 = shape.Add(FeatureStruct.New().Value);
    var owner = new Annotation<ShapeNode>(Range<ShapeNode>.Create(n0, n2), FeatureStruct.New().Value);
    owner.Children.AddRange(new[] { n0.Annotation, n1.Annotation, n2.Annotation });
    var empty = new Annotation<ShapeNode>(Range<ShapeNode>.Create(n0, n2), FeatureStruct.New().Value);
    if (ownerAddedFirst)
    {
        shape.Annotations.Add(owner, false);
        shape.Annotations.Add(empty, false);
    }
    else
    {
        shape.Annotations.Add(empty, false);
        shape.Annotations.Add(owner, false);
    }

    bool found = shape.Annotations.FindDepthFirst(n1, out Annotation<ShapeNode> result);
    Console.WriteLine($"ownerAddedFirst={ownerAddedFirst}; found={found}; foundSegment={ReferenceEquals(result, n1.Annotation)}");
}

Acceptance criteria:

• Find the descendant in both insertion orders and both search directions, with deterministic coverage of tied containers and nested containers.
• Preserve existing direction and boundary semantics, and verify that no unrelated annotation is returned.
• Keep the fix separately reviewable from HermitCrab: investigate unstable zero-width morpheme identities across fresh processes #506. Do not claim a parser-level reproduction without one.

Related: #506, #500. The reproduction was rerun directly during the 2026-10-23 investigation; the first-match boundary fix does not solve this case.