amazon-ion / ion-schema-rust

Rust implementation of Ion Schema
https://amazon-ion.github.io/ion-schema/sandbox
Apache License 2.0
13 stars 6 forks source link

Implementation of a `StateMachine` for validation #56

Closed desaikd closed 2 weeks ago

desaikd commented 2 years ago

As part of the validation of ordered_elements constraint, it would require to implement a State Machine which can keep track of occurs constraint and move to another state as per events(e.g. type:int) .

Example: For a constraint ordered_elements: [int, decimal], State Machine constructs an NFA like below:

 InitialState --event1--> IntermediateState --event2--> FinalState
 S1:required --type:int--> S2:required --type:decimal--> S3:optional

Note::By default the occurs constraint would be required meaning range::[1,1]

Given below is a summary tale representing the states and events for a value to be validated:

value: [1, 2.0]

Event State set (each state represented by state:visitCount)
(initial state)
type:int S1:1
type:decimal S2:1 --> matches!

value: [2.0, 1]

Event State set (each state represented by state:visitCount)
(initial state)
type:int S1:0 --> no matches! expected int found decimal value

Prerequisite PR: #55 (contains implementation is required to be used within occurs constraint while ordered_elements constraint validation)

desaikd commented 2 years ago

This is fixed because ordered_elements has been implemented in a simpler way by using a peekable iterator instead with #62.

popematt commented 2 years ago

Reopening because according to https://github.com/amzn/ion-schema/issues/62, ordered_elements should be treated more like a regular expression/language. We will need something other than the peekable iterator to evaluate it. It will probably need a state machine, but it is possible that there is some other solution.

popematt commented 1 year ago

Here is an example of something that should be valid, but is not recognized as valid.