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

Aberta
  • Algo errado?
#554 0 comentários 0 reações 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 1 dia

@johnml1135 já está trabalhando nisso.

Desde 26/10/2026.

  • #556 de @johnml1135 — aberto
  • #557 de @johnml1135 — aberto

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
56/100
Tipo de issue
Bug
Clareza
Claramente especificada
Status de atividade
Ativa
Stack de tecnologia
csharp
Domínio
backend

Direção de pesquisa

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.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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.

Linguagem predominante
C#
Estrelas
29
Forks
16
Merge médio
5d 11h
PRs com merge (30d)
15

Preparar o ambiente

  • Sem Dockerfile nem arquivo Docker Compose
  • Tem um modelo de pull request
  • Sem guia de contribuição

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de sillsdev/machine

Todas as issues de sillsdev/machine

Issues semelhantes

Mais issues de C#

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.