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

オープン 初心者向け
  • 何か問題がありますか？
#638 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
2/5
見積もり時間
1〜3時間
初心者へのやさしさ
76/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
csharp
領域
backend

調査の方向性

文脈を把握するため、src/SIL.Machine/FiniteState/Fst.cs:434-441 の非決定的な比較と、#541 の決定的な変更を読んでください。issue で説明されている、同じスパンを持つ3つの結果を使った単体テストを追加し、zip した要素の後で、Order にフォールバックする前に優先度配列の長さを比較してください。このケースで比較が一貫した順序を返すことを完了条件とします。また、実際の NFA が同じスパンについて長さの異なる優先度配列を生成し得るかも確認してください。

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
C#
スター
29
フォーク
16
平均マージ
4日 11時間
マージ済み PR（30日）
14

環境構築

  • Dockerfile・Docker Compose ファイルなし
  • プルリクエストのテンプレートあり
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

sillsdev/machine のほかの issue

sillsdev/machine の issue をすべて見る

似ている issue

C# の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。