AnnotationList.FindDepthFirst misses descendants in tied containers depending on insertion order
Maintainers usually reply within 1 day
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 56/100
Research direction
Start with src/SIL.Machine/Annotations/AnnotationList.cs::FindDepthFirst and the minimal reproduction in the issue. Add deterministic tests for tied and nested containers in both insertion orders and search directions; verify the expected descendant is found without returning an unrelated annotation. Keep the change separate from #506.
Written by the indexing model from the issue text.
Description
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 #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.
- Dominant language
- C#
- Stars
- 29
- Forks
- 16
- Avg merge
- 10d 4h
- Merged PRs (30d)
- 13
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- No contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from sillsdev/machine
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
Maintainers usually reply within 1 day
-
Shape.Remove can leave a spanning annotation anchored to a removed end segmentPossibly taken A pull request linked to this issue is open or already merged. Open
Difficulty 4/5 1-2 days Newbie friendliness 62/100
Maintainers usually reply within 1 day
-
Hermit Crab
Difficulty 4/5 3-5 days Newbie friendliness 52/100
sillsdev/machine#552 · 1 comment ·
Maintainers usually reply within 1 day
-
HermitCrab: partial lexical entries switch off final-template pruning for the whole grammarPossibly taken @johnml1135 claimed this 2 days ago. OpenHermit Crab
Difficulty 5/5 Over a week Newbie friendliness 35/100
Maintainers usually reply within 1 day
-
Hermit Crab
Difficulty 5/5 Over a week Newbie friendliness 25/100
Maintainers usually reply within 1 day
All issues in sillsdev/machine
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
unoplatform/uno.check#591 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
weaviate/csharp-client#378 ·
-
confirmed enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
Maintainers usually reply within 1 day
-
agentic-workflows automated testing
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
Azure-Samples/Legacy-Modernization-Agents#194 ·
Maintainers usually reply within 1 day
-
area-encryption area-security p1-recommended technical-debt
Difficulty 2/5 Under an hour Newbie friendliness 85/100
Maintainers usually reply within 1 day