Fst.ResultCompare: nondeterministic branch can order results inconsistently when Priorities arrays differ in length

Offen Anfängerfreundlich
  • Stimmt etwas nicht?
#638 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
2/5
Geschätzter Aufwand
1-3 Stunden
Anfängerfreundlichkeit
76/100
Issue-Typ
Bug
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
csharp
Bereich
backend

Rechercherichtung

Lies zum Kontext den nichtdeterministischen Vergleich in src/SIL.Machine/FiniteState/Fst.cs:434-441 und die deterministische Änderung in #541. Füge einen Unit-Test mit den drei Ergebnissen desselben Spans hinzu, die im Issue beschrieben sind, und vergleiche die Längen der Prioritätsarrays nach den Elementen, die paarweise verglichen wurden, bevor auf Order zurückgegriffen wird. Die Vergleichsfunktion soll für diesen Fall eine konsistente Reihenfolge ergeben; prüfe außerdem, ob ein echtes NFA Prioritätsarrays unterschiedlicher Länge für denselben Span erzeugen kann.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

Fst.ResultCompare can still order nondeterministic results inconsistently: when two results cover the same span and one Priorities array is a prefix of the other, the comparison returns 0 and falls through to insertion order, which can form a cycle.

#541 makes the deterministic branch a proper total order; this nondeterministic branch (src/SIL.Machine/FiniteState/Fst.cs:434-441 on the #541 head) is unchanged. It compares x.Priorities.Zip(y.Priorities), and Zip stops at the shorter array.

Example, all with the same span: a = [1] (Order 1), b = [1,2] (Order 0), c = [1,0] (Order 2).

  • a vs b: the zip ties, Order gives b < a.
  • a vs c: the zip ties, Order gives a < c.
  • b vs c: 2 > 0 gives c < b.

That is b < a < c < b, so List.Sort may return any of them first, depending on input order.

Fix: after the zip, compare x.Priorities.Length with y.Priorities.Length before falling back to Order, plus a unit test with the three results above.

Next: confirm whether a real NFA produces priority arrays of different lengths over the same span (paths with different numbers of epsilon arcs); unverified so far. HermitCrab grammars from FieldWorks may never reach it, so this is low priority.

Source

Found in a review of #541 (head 6e9c6955). The deterministic branch and its callers (Fst.Transduce, Matcher) are covered there.

Vorherrschende Sprache
C#
Sterne
29
Forks
16
Ø Merge
4 T. 11 Std.
Gemergte PRs (30 T.)
14

Entwicklungsumgebung

  • Kein Dockerfile und keine Docker-Compose-Datei
  • Hat eine Pull-Request-Vorlage
  • Kein Beitragsleitfaden

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus sillsdev/machine

Alle Issues in sillsdev/machine

Ähnliche Issues

Weitere Issues zu C#

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.