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

Abierto Apto para principiantes
  • ¿Algo no está bien?
#638 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
2/5
Tiempo estimado
1-3 horas
Aptitud para principiantes
76/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
csharp
Área
backend

Línea de trabajo

Lee la comparación no determinista en src/SIL.Machine/FiniteState/Fst.cs:434-441 y el cambio determinista en #541 para tener contexto. Añade una prueba unitaria usando los tres resultados con el mismo intervalo descritos en el issue y, después de los elementos emparejados, compara las longitudes de los arrays de prioridad antes de recurrir a Order. El objetivo es que la comparación produzca un orden coherente para ese caso; comprueba también si un NFA real puede producir arrays de prioridad de distinta longitud para el mismo intervalo.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
C#
Estrellas
29
Forks
16
Merge medio
4 d 11 h
PR fusionados (30 d)
14

Preparar el entorno

  • Sin Dockerfile ni archivo de Docker Compose
  • Tiene una plantilla de pull request
  • Sin guía de contribución

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de sillsdev/machine

Todos los issues de sillsdev/machine

Issues similares

Más issues de C#

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.