Panic when head-skipping to the key { or [

[V0ldek]

Package

CLI

Describe the bug

Head skipping looking for the key { or [ on specific inputs causes a panic.

Minimal Reproducible Example

$ rq '$..["{"]'
$ {"":null}
The application panicked (crashed).
Message:  attempt to subtract with overflow
Location: /home/mat/rsonpath/crates/rsonpath-lib/src/classification/memmem/shared/mask_64.rs:16

  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ BACKTRACE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
                                ⋮ 8 frames hidden ⋮
   9: core::panicking::panic::hf53fd8b0bfa5848e
      at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/core/src/panicking.rs:117
  10: rsonpath::classification::memmem::shared::mask_64::find_in_mask::h6090a57bcdca680d
      at /home/mat/rsonpath/crates/rsonpath-lib/src/classification/memmem/shared/mask_64.rs:16
        14 │         let idx = result.trailing_zeros() as usize;
        15 │         debug!("{offset} + {idx} - 2 to {offset} + {idx} + {label_size} - 3");
        16 >         if input.is_member_match(offset + idx - 2, offset + idx + label_size - 3, label) {
        17 │             return Some(offset + idx - 2);
        18 │         }
  11: rsonpath::classification::memmem::avx2_64::Avx2MemmemClassifier64<I,R>::find_letter::h879eab4884c6798b
      at /home/mat/rsonpath/crates/rsonpath-lib/src/classification/memmem/avx2_64.rs:110
       108 │
       109 │             if let Some(res) =
       110 >                 mask_64::find_in_mask(self.input, label, previous_block, first_bitmask, second_bitmask, offset)
       111 │             {
       112 │                 return Ok(Some((res, block)));
  12: rsonpath::classification::memmem::avx2_64::Avx2MemmemClassifier64<I,R>::find_label_avx2::h04835315ed5dfd87
      at /home/mat/rsonpath/crates/rsonpath-lib/src/classification/memmem/avx2_64.rs:132
       130 │             return self.find_empty(label, offset);
       131 │         } else if label.bytes().len() == 1 {
       132 >             return self.find_letter(label, offset);
       133 │         }
       134 │
  13: <rsonpath::classification::memmem::avx2_64::Avx2MemmemClassifier64<I,R> as rsonpath::classification::memmem::Memmem<I,_>>::find_label::h00c73b020ffab4e3
      at /home/mat/rsonpath/crates/rsonpath-lib/src/classification/memmem/avx2_64.rs:180
       178 │         let next_block_offset = self.iter.get_offset();
       179 │         // SAFETY: target feature invariant
       180 >         unsafe { self.find_label_avx2(label, next_block_offset) }
       181 │     }
       182 │ }
  14: rsonpath::engine::head_skipping::HeadSkip<I,V,_>::run_head_skipping::h90ea9413f393a1d1
      at /home/mat/rsonpath/crates/rsonpath-lib/src/engine/head_skipping.rs:134
       132 │             debug!("Starting memmem search from {idx}");
       133 │
       134 >             if let Some((starting_quote_idx, last_block)) = memmem.find_label(first_block, idx, self.member_name)? {
       135 │                 drop(memmem);
       136 │
  15: rsonpath::engine::main::Executor<I,R,V>::run::hff9e7119aa9f7a11
      at /home/mat/rsonpath/crates/rsonpath-lib/src/engine/main.rs:247
       245 │
       246 │         match mb_head_skip {
       247 >             Some(head_skip) => head_skip.run_head_skipping(&mut self),
       248 │             None => self.run_and_exit(),
       249 │         }
  16: <rsonpath::engine::main::MainEngine as rsonpath::engine::Engine>::matches::he96a3bc19aa701ef
      at /home/mat/rsonpath/crates/rsonpath-lib/src/engine/main.rs:139
       137 │         simd_dispatch!(self.simd => |simd| {
       138 │             let executor = query_executor(&self.automaton, input, &recorder, simd);
       139 >             executor.run()?;
       140 │         });
       141 │
  17: rq::runner::ResolvedOutput::run_and_output::run_impl::hd3b0c6a791b4f9f4
      at /home/mat/rsonpath/crates/rsonpath/./src/runner.rs:160
       158 │                 ResolvedOutput::Nodes => {
       159 │                     let mut sink = MatchWriter::from(io::stdout().lock());
       160 >                     engine.matches(&input, &mut sink)?;
       161 │                 }
       162 │             }
  18: rq::runner::ResolvedOutput::run_and_output::h441e73314b4e9e0c
      at /home/mat/rsonpath/crates/rsonpath/./src/runner.rs:167
       165 │         }
       166 │
       167 >         run_impl(self, engine, input).map_err(|err| report_engine_error(err).wrap_err("Error executing the query."))
       168 │     }
       169 │ }
  19: rq::runner::ResolvedInput<S>::run_engine::hfdb3001cc3e300e0
      at /home/mat/rsonpath/crates/rsonpath/./src/runner.rs:140
       138 │                     .ok_or_else(|| eyre::eyre!("Attempt to buffer reads on inline JSON input."))?;
       139 │                 let input = BufferedInput::new(read);
       140 >                 with_output.run_and_output(engine, input)
       141 │             }
       142 │         }
  20: rq::runner::Runner<S>::run::hb2a5b400bff75332
      at /home/mat/rsonpath/crates/rsonpath/./src/runner.rs:32
        30 │             ResolvedEngine::Main => {
        31 │                 let engine = MainEngine::from_compiled_query(self.with_compiled_query);
        32 >                 self.with_input
        33 │                     .run_engine(engine, self.with_output)
        34 │                     .wrap_err("Error running the main engine.")
  21: rq::run_with_args::h0dba400739873a03
      at /home/mat/rsonpath/crates/rsonpath/./src/main.rs:48
        46 │         let output = runner::resolve_output(args.result);
        47 │
        48 >         Runner {
        49 │             with_compiled_query: automaton,
        50 │             with_engine: engine,
  22: rq::main::hf05b48e800a06f7c
      at /home/mat/rsonpath/crates/rsonpath/./src/main.rs:24
        22 │     logger::configure(args.verbose)?;
        23 │
        24 >     run_with_args(&args).map_err(|err| err.with_note(|| format!("Query string: '{}'.", args.query.dimmed())))
        25 │ }
        26 │
  23: core::ops::function::FnOnce::call_once::hd46012c9c7a0e454
      at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/core/src/ops/function.rs:250
                                ⋮ 16 frames hidden ⋮

The same panic happens for a similar input with square brackets:

$ rq '$["["]'
$ [""]

Expected behavior

Doesn't panic.

Workarounds (optional)

No response

Proposed solution (optional)

No response

Version of the release

v0.8.1

Rust version

1.72.1

Target triple

x86_64-unkown-linux-gnu

Features enabled

default

Codegen options

link-arg=-fuse-ld=lld

Additional context (optional)

Caught by the batch fuzzer!
https://github.com/V0ldek/rsonpath/actions/runs/6256645027/job/16987800097

[github-actions]

Tagging @V0ldek for notifications

[V0ldek]

Root cause:

For a single-byte key we look for the single byte followed by a double quote, if the input starts with {" or [" head-skipping will report this as a potential match and attempt to check the input if the label matches. This requires looking one character back for the opening double quote, but since we are at byte 0 already, this crashes.

[V0ldek]

Fixed in v0.8.2