Issue

This change includes support for nix-based environments in the project via a nix shell file.

There is not currently an issue for this item.

I am not sure if the submodules are updated correctly. Thanks!

Checklist

All of these should be ticked off before you submit the PR.

• [X] I ran just verify locally and it succeeded.
• [x] Issue was given go ahead and is linked above OR I have included justification for a minor change.
• [X] Unit tests for my changes are not included because no functionality was changed.

Issue

This PR implements descendant wildcard search.

Resolves: #68 #69 #70 #71 #72

Checklist

• [X] I ran just verify locally and it succeeded.
• [X] Issue was given go ahead and is linked above
• [X] Unit tests for my changes are included

Describe the bug A clear and concise description of what the bug is.

I am trying to run rson vs jsonski benchmark facing this error where I am unable to debug since I am not experienced with Rust. I have attached the image.

Proposed solution (optional) Idea on an appropriate fix.

Desktop (please complete the following information):

• MacOS - i9
• rustc 1.64.0 (a55dd71d5 2022-09-19)

Additional context Add any other context about the problem here.

Describe the bug panic message when reading incorrect value.

The application panicked (crashed).
Message:  index out of bounds: the len is 128 but the index is 18446744073709551615
Location: /home/cha/git/rust/rsonpath/rsonpath/src/stackless.rs:297
``

**MRE**
Example of incorrectly formatted document:

{'a': {'b': 'c', 'e': 'f'}, 'g': 'h'}

(Python dict not Jsonified)

**Expected behavior**
If the formatting error is detectable, throw an incorrect input error.

Describe the bug Reported in https://github.com/NixOS/nixpkgs/pull/223333

Build fails on architectures not supporting SIMD because aligners is compiled with the simd feature unconditionally.

The real riddle here is why the CI pipeline for aarch64-unknown-linux-gnu succeeds. No idea as of now.

MRE Repro is hard currently, but it can be seen here: https://github.com/NixOS/nixpkgs/pull/223333#discussion_r1150897852

Expected behavior

1. Code compiles with aligners/simd disabled.
2. Issues like these are caught during release.

Workarounds (optional) I don't think there is one? You can enable features of a dependency by passing --features dep/feat, but there doesn't seem to be a flag to disable default features of a dependency.

Proposed solution (optional) Fix is simple, pass the feature flag to aligners in Cargo.toml, BUT before merging that we absolutely need to get a repro in the CI pipeline. That this wasn't caught earlier is weird and unacceptable.

Desktop (please complete the following information):

• Rust version: 1.68.1
• Target triple: aarch64-unknown-linux-gnu
• Features: --no-default-features --features=default-optimizations
• Version: v0.3.2

Is your feature request related to a problem? Please describe. When implementing new selectors or just diagnosing bugs with a particular query, we often have to look at the compilation itself and the resulting automaton. It would be nice to have a way to run the binary only to the point of compilation, and not involve any of the engines.

Describe the solution you'd like A new variant to the --engine switch sounds ideal. Example run:

just r '$..a.b' -e compiler -v

DEBUG [rsonpath_lib::query::parser] Parsed tokens: $(Descendant("a"))(Child("b"))
INFO  [rsonpath] Preparing query: `$..['a']['b']`

DEBUG [rsonpath_lib::query::automaton] NFA: r1 --a-> d1 --b-> acc
DEBUG [rsonpath_lib::query::automaton::minimizer] New superstate created: {NfaStateId(0)} DFA(1)
DEBUG [rsonpath_lib::query::automaton::minimizer] Expanding superstate: {NfaStateId(0)}, last checkpoint is Some(NfaStateId(0))
DEBUG [rsonpath_lib::query::automaton::minimizer] Considering transition NFA(0) --"a"-> NFA(1)
DEBUG [rsonpath_lib::query::automaton::minimizer] Raw transitions: {"a": {NfaStateId(1)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] New superstate created: {NfaStateId(0), NfaStateId(1)} DFA(2)
DEBUG [rsonpath_lib::query::automaton::minimizer] Normalized transitions: {"a": {NfaStateId(0), NfaStateId(1)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] Translated transitions: [("a", State(2))]
DEBUG [rsonpath_lib::query::automaton::minimizer] Expanding superstate: {NfaStateId(0), NfaStateId(1)}, last checkpoint is Some(NfaStateId(0))
DEBUG [rsonpath_lib::query::automaton::minimizer] Considering transition NFA(0) --"a"-> NFA(1)
DEBUG [rsonpath_lib::query::automaton::minimizer] Considering transition NFA(1) --"b"-> NFA(2)
DEBUG [rsonpath_lib::query::automaton::minimizer] Raw transitions: {"a": {NfaStateId(1)}, "b": {NfaStateId(2)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] New superstate created: {NfaStateId(0), NfaStateId(2)} DFA(3)
DEBUG [rsonpath_lib::query::automaton::minimizer] Normalized transitions: {"a": {NfaStateId(0), NfaStateId(1)}, "b": {NfaStateId(0), NfaStateId(2)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] Translated transitions: [("a", State(2)), ("b", State(3))]
DEBUG [rsonpath_lib::query::automaton::minimizer] Expanding superstate: {NfaStateId(0), NfaStateId(2)}, last checkpoint is Some(NfaStateId(0))
DEBUG [rsonpath_lib::query::automaton::minimizer] Considering transition NFA(0) --"a"-> NFA(1)
DEBUG [rsonpath_lib::query::automaton::minimizer] Raw transitions: {"a": {NfaStateId(1)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] Normalized transitions: {"a": {NfaStateId(0), NfaStateId(1)}}
DEBUG [rsonpath_lib::query::automaton::minimizer] Translated transitions: [("a", State(2))]
DEBUG [rsonpath_lib::stackless] DFA:
 digraph {
  0 -> 0 [label="*"]
  1 -> 2 [label="a"]
  1 -> 1 [label="*"]
  2 -> 2 [label="a"]
  2 -> 3 [label="b"]
  2 -> 1 [label="*"]
  3 -> 2 [label="a"]
  3 -> 1 [label="*"]
}
INFO  [rsonpath] Compilation finished.

Describe alternatives you've considered A dedicated flag could be used, --compile (short -c). It would be mutually exclusive with -e. Since the run would be completely different we could have the binary just output the compiled automaton to stdout in .dot format, which would make inspecting it easier.

Is your feature request related to a problem? Please describe. The wildcard descendant selector should be recognized by the parser and parsed into an appropriate JsonPathQueryNode. Note that this means both the ..* and ..[*] patterns. The index and non-index version have identical semantics.

Describe the solution you'd like This should follow the same approach as #6, which should be completed first.

Additional context Find the syntax for the selectors in the RFC:

• descendant-wildcard/descendant-index-wildcard: RFC Draft 3.5.7

Is your feature request related to a problem? Please describe. The datasets described in the JSONSki paper are available on Google Drive, but are not incorporated into our benchmarks.

Describe the solution you'd like We need the datasets included and experiments configured for those datasets. If wildcard selectors get implemented (#9), we can take the queries as-is. However, it is still beneficial to consider rewrites of these queries using the descendant selector not available to JSONSki for potential performance gains (and easier query formulations). This needs to be investigated.

Bumps test-case from 3.0.0 to 3.1.0.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Is your feature request related to a problem? Please describe. The jsonpath-rust crate is arguably the most potent competitor as a Rust-native JSONPath crate. Other JSONPath crates for Rust exist, but are umaintained. This one is frequently updated and has a lot of users. We need to integrate it with the benches and run performance comparisons.

Is your feature request related to a problem? Please describe. TIL there exists serde_json_path, a crate for JSONPath integrated to serde, which makes it a viable competitor as a Rust-native DOM-building competitor. We need to add it as a benchmark target and gather performance results.

Is your feature request related to a problem? Please describe. The engine currently violates the JSON spec by not normalizing Unicode escapes. We do this for performance purposes, since ordinal comparison can be easily SIMDified, but it's not correct.

For a simple example, the UTF-8 codepoint for the letter "a" is 0x0061. These JSONs are equivalent under RFC 8259:

{"a":42}

{"\u0061":42}

Therefore the query $["a"] should in both cases match the value 42.

Quite sensibly, and indeed officially under the current JSONPath RFC Draft, the queries $["a"] and $["\u0061"] must also be equivalent. All four combinations of the two documents above and the two queries must yield the same result -- the value 42.

Describe the solution you'd like The tradeoff here is important. We expect the difference in performance to be staggering, especially since the head-skip optimisation is by design incompatible with this. We need a flag that will toggle this behaviour. I propose we make this the optional behaviour – we expect the vast majority of labels to be ASCII, if a user wants to match unicode they can use the flag.

Is your feature request related to a problem? Please describe. Currently our approach was to bundle parsing JSONPath selectors a part of enabling support for them entirely, as the first step in the process.

Pros of the current approach

The pros of that approach is that we're rather immune to any syntax changes that could be proposed in further refinements of the JSONPath RFC, and the parser is relatively small.

Cons of the current approach

The cons are threefold, engineering-wise, UX-wise, and from the usability of rsonpath-lib as an API.

UX

As of this writing we don't have descendant wildcards yet (#68), but we do have child wildcards. What happens if a user tries to query for $.data[*]..*.value?

That's technically correct, but utterly useless. Without that one dot token it compiles, yes, but the true issue here is that this is valid JSONPath, we just don't support the ..* construct yet. Writing proper error messages for this would require the parser to understand ..*, and then an error from the compiler saying "we can't handle this yet".

Engineering

We need to basically maintain a second JSONPath grammar. While it's essentially a subset, we need to document the differences and any additions will result in an effective change of the public API and the CLI experience. It's also hard to maintain the parser's error messages consistent, since what is now an "invalid token" with no further explanation could be a valid token later.

Library

The query and engine modules are separate, and query has a clearly designated compiler part (automaton). We strive to be a comprehensive JSONPath library, which means that the query module should recognise as much of JSONPath as it can without relying on the engine to understand that. That way we make extensibility easier – say we wanted to roll out a DOM-based engine for all of JSONPath tomorrow, because it's vastly easier than a streaming one and still useful. It makes no modular sense to restrict the query API based on what the consumer of that API, automaton and engine, support at the moment.

Describe the solution you'd like

1. Take the newest RFC proposal and produce a syntax file. Unfortunately the grammar is scattered around the doc and needs to be assembled together. We want the explicit EBNF grammar as part of our docs.

2. Implement the parser to fulfill that grammar and extend JsonPathQuery to support all constructs. Extensive testing is needed here.

3. Make error messages nice.

Describe alternatives you've considered We can just do nothing and take these in stride as new selectors come, but with all the cons it entails (described above).

Is your feature request related to a problem? Please describe. SIMD acceleration is implemented for x86 and tracked in #21 for 32-bit ARM. We also need support for 64-bit ARM.

Describe the solution you'd like We expect most of the design around extracting architecture-specific bits to be done in #14. After that, a similar approach can be used here and in #21.

Additional context Find NEON intrinsics documentation here.

I am not knowledgable in NEON and I don't even know how to emulate an ARM system locally, so help here is really needed.

Is your feature request related to a problem? Please describe. After #7 the compiler no longer necessarily outputs a minimal DFA. It's still a correct DFA, just not minimal.

Describe the solution you'd like The algorithm in query::automaton::minimizer needs to be rewritten to minimize the automaton.

Describe alternatives you've considered A clear and concise description of any alternative solutions or features you've considered.

Additional context Example query that produces a non-minimal automaton: $..a.*.*..b.*.*. In the resulting automaton below states 3 and 4 are equivalent.

Is your feature request related to a problem? Please describe. Extend the support for the index selector intriduced in #60 to negative values. The negative value selects from the end of the list.

Describe the solution you'd like The error message introduced in #60 should be replaced with actual parsing code.

Additional context Syntax formulation in the RFS.

Tracking issue for the list Index Selector [n], where n is a positive constant. Support for negative (selecting from array end) is tracked at TODO.

• [ ] Parser #60
• [ ] Compiler #61
• [ ] Engine (recursive) #62
• [ ] Engine (main) #63