AnnotationList.FindDepthFirst misses descendants in tied containers depending on insertion order
メンテナーはふだん 1 日以内に返信
評価
調査の方向性
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.
索引モデルが issue の本文から書いたものです。
説明
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.
- 主要言語
- C#
- スター
- 29
- フォーク
- 16
- 平均マージ
- 10日 4時間
- マージ済み PR（30日）
- 13
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドなし
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
sillsdev/machine のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
メンテナーはふだん 1 日以内に返信
-
Shape.Remove can leave a spanning annotation anchored to a removed end segment対応中かも このイシューにリンクされたプルリクエストがオープン中、またはマージ済みです。 オープン
難易度 4/5 1〜2日 初心者へのやさしさ 62/100
メンテナーはふだん 1 日以内に返信
-
Hermit Crab
難易度 4/5 3〜5日 初心者へのやさしさ 52/100
sillsdev/machine#552 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
HermitCrab: partial lexical entries switch off final-template pruning for the whole grammar対応中かも @johnml1135 が 2 日前に担当しました。 オープンHermit Crab
難易度 5/5 1週間以上 初心者へのやさしさ 35/100
メンテナーはふだん 1 日以内に返信
-
Hermit Crab
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
メンテナーはふだん 1 日以内に返信
sillsdev/machine の issue をすべて見る
似ている issue
-
track:release
難易度 2/5 1〜3時間 初心者へのやさしさ 80/100
-
[Bug] [Go] Ack returns nil when the server answers with a non-OK status対応中かも @leizhiyuan が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
apache/rocketmq-clients#1465 ·
メンテナーはふだん 2 日以内に返信
-
fix(testing): HeadlessTerminal disposes services synchronously対応中かも @zidad が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 69/100
RazorConsole/RazorConsole#388 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
starlinghq/starling#209 ·
メンテナーはふだん 1 日以内に返信