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

Aperta Adatta ai principianti
  • Qualcosa non va?
#638 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
2/5
Tempo stimato
1-3 ore
Idoneità per principianti
76/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
csharp
Ambito
backend

Direzione di ricerca

Per il contesto, leggi il confronto non deterministico in src/SIL.Machine/FiniteState/Fst.cs:434-441 e la modifica deterministica in #541. Aggiungi un test unitario usando i tre risultati con lo stesso intervallo descritti nell’issue, quindi confronta le lunghezze degli array di priorità dopo gli elementi confrontati a coppie e prima di ricorrere a Order. L’obiettivo è che il confronto produca un ordinamento coerente per quel caso; verifica anche se un NFA reale può produrre array di priorità di lunghezza diversa per lo stesso intervallo.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.

Lingua principale
C#
Stelle
29
Fork
16
Merge medio
4g 11h
PR unite (30g)
14

Preparare l'ambiente

  • Nessun Dockerfile né file Docker Compose
  • Ha un modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di sillsdev/machine

Tutte le issue di sillsdev/machine

Issue simili

Altre issue su C#

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.