Rust-only JSON schema construction

[brandonwillard]

This issue is about converting the outlines JSON schema-to-regex logic to Rust.

First, let's determine how much needs to be converted and what the expected entry point(s) is(are)?

Second, we need to move to CFG-based schemas eventually. This conversion could serve as the beginning of that (open-source) effort. One way that could manifest: create CFGs for schemas and convert them to regex form. We could also consider an intermediate form that works for both targets.

[rlouf]

Rust's regex crate does not support advanced constructs like negative lookahead, which limits our ability to fully implement certain JSON Schema features (e.g., oneOf, anyOf). These constructs require more complex logic that would be more easily handled by defining the DFA rather than writing a regex.

I would shift from a regex-based approach to a DFA-based one, and use the data structures already present in the regex-automata crate. So JSON schemas would be translated into DFAs directly.

[brandonwillard]

Rust's regex crate does not support advanced constructs like negative lookahead, which limits our ability to fully implement certain JSON Schema features (e.g., oneOf, anyOf). These constructs require more complex logic that would be more easily handled by defining the DFA rather than writing a regex.

Where are these missing constructs employed in outlines? We might need to explicitly list them out as requirements in this issue.

I would shift from a regex-based approach to a DFA-based one, and use the data structures already present in the regex-automata crate. So JSON schemas would be translated into DFAs directly.

Yeah, we don't want to have to rewrite any of the interegular logic involving regex parsing and DFAs. regex-automata looks likes a viable replacement for interegular; we just need to make sure that it actually provides all the necessary regex features and DFA information (e.g. easily enumerable states and transitions). See #10.

[brandonwillard]

We should also move any discussions about Rust regex and DFA features to #10.

[ErikKaum]

I added #15 which is a port of the build_regex_from_schema function I wrote a while ago. Back then I essentially wrote it with the intention of being a 1-to-1 port. It's not 100% functional but, I estimate I could get it working without too much work. Currently 18 tests fail and 45 pass.

This PR doesn't take into account the DFA-based approach, so it wouldn't necessarily serve towards that goal.

So I think the concrete question would be:

• should I continue working on this --> we could replace build_regex_from_schema with a rust version quite soon, but it wouldn't necessarily serve as a spring board for the DFA-based approach
• or instead go for an approach where the JSON schemas would be translated into DFAs directly like Rémi mentioned, using most likely the regex-automata crate --> might take longer but most likely more useful long term

[brandonwillard]

• should I continue working on this --> we could replace build_regex_from_schema with a rust version quite soon, but it wouldn't necessarily serve as a spring board for the DFA-based approach

Yes, let's get your code working and move from there.

[ErikKaum]

Awesome, I'll get to work 🙌🏽