このスキーマでJSONスキーマのバリデータを削除できますか？

Question

いくつかのJSONスキーマバリデーターでこれを試してみましたが、いくつかは失敗しましたが、問題はチョークして殺す原因となるバリデーターの使用量を調べることです。

JSONスキーマで有限状態マシンを実装できることが判明しました。これを行うために、FSMノードはオブジェクトスキーマであり、FSMエッジはanyOfにラップされた一連のJSONポインタです。全体としてはやや単純ですが、これを行うことができるのはいくつかの結果をもたらします.JSONスキーマが与えられたときに、2^Nの時間またはメモリを必要とするFSMを作成した場合（深さの最初の検索または幅の広い最初の検索） N定義といくつかの入力を検証する？

それでは、二つのシンボルaとbのアルファベットの上に非決定性有限状態機械（NFA）を実装するN定義でJSONスキーマを作成してみましょう。正規表現 (a{N}|a(a|b+){0,N-1}b)*xをエンコードするだけで済みます。xは最後を表します。最悪の場合、この正規表現のNFAは、テキストに一致する時間が2^N、メモリが2^N（たとえば、確定的な有限状態マシンに変換されたとき）です。ここで、単語abbxは、JSONポインタa/b/b/xで表現できます。これは、JSONで{"a":{"b":{"b":{"x":true}}}}に相当します。スキーマこのNFAを符号化するために

、我々は最初の状態「0」の定義を追加する：

{ 
    "$schema": "http://json-schema.org/draft-04/schema#", 
    "$ref": "#/definitions/0", 
    "definitions": { 
    "0": { 
     "type": "object", 
     "properties": { 
     "a": { "$ref": "#/definitions/1" }, 
     "x": { "type": "boolean" } 
     }, 
     "additionalProperties": false 
    }, 

その後、我々はNを追加-1各状態<DEF>の定義を<DEF>が列挙されているスキーマに"1"、 "2"、 "3"、... "N -1"：

"<DEF>": { 
     "type": "object", 
     "properties": { 
     "a": { "$ref": "#/definitions/<DEF>+1" }, 
     "b": { 
      "anyOf": [ 
      { "$ref": "#/definitions/0" }, 
      { "$ref": "#/definitions/<DEF>" } 
      ] 
     } 
     }, 
     "additionalProperties": false 
    }, 

"<DEF> +1は、" 戻る "0" に折り返さはN -1に等しい。

2文字のアルファベットのこの「NFA」は、N州、唯一のイニシャルと 最終状態を持っています。等価な最小DFAは2^N（2からべき乗N）の状態です。

これは最悪の場合、2^N時間を割いたり、入力を検証するために、2^Nメモリ「セル」を使用しなければならないのいずれか、このスキーマを使用してバリデータであることを意味します。

バリデータが妥当性チェックに近づくためのショートカットを使用しない限り、このロジックがどこに間違っているのかわかりません。

見つかったthis here。

Answer 1

原則としてあなたは正しいと思います。私はあなたが記述したスキーマ構築について100％確信しているわけではありませんが、理論的にはあなたが記述する理由のために^ N時間またはスペースを必要とするスキーマを構築することが可能でなければなりません。

ほとんどのスキーマプロセッサはおそらく、再帰的にanyOfを検証しようとします。だから、指数関数的な時間になります。