DoubleArray::new() does not check untrusted source

[vbkaisetsu]

DoubleArray::get_unit() calls slice::get_unchecked() internally, but this slice is not checked in DoubleArray::new().
So, it is possible to cause a segmentation fault even though the caller does not use unsafe blocks.

use yada::DoubleArray;

fn main() {
    let da = DoubleArray::new(vec![]);
    if let Some(index) = da.exact_match_search("example input") {
        dbg!(index);
    }
}

$ cargo run --release
...
[1]    81236 segmentation fault  cargo run --release

Solution 1: Change DoubleArray::new() to an unsafe function

This solution does not pay the additional runtime cost, but requires callers to be responsible for using the correct slice.

let da = unsafe { DoubleArray::new(trusted_bytes) };

Solution 2: Change slice::get_unchecked() to a checked function

The opposite of Solution 1.

let b = &self.0[index * UNIT_SIZE..(index + 1) * UNIT_SIZE];

or

let b = self.0.get(index * UNIT_SIZE..(index + 1) * UNIT_SIZE)
          .ok_or_else(|| ...)?;

Solution 3: Check the argument of DoubleArray::new()

This is too much work, but it does not require any responsibility on callers and does not pay any additional costs during the search.

[takuyaa]

@vbkaisetsu Thanks for raising this issue. This behavior that might cause unexpected SIGSEGV should be fixed to avoid user confusion.

The policy of the fix I would like to propose is as follows:

1. Introduce validate function that checks whether an array is valid or not as a representation of a double array.
   • The validation needs to check carefully so that all transitions of a double array are safe.
2. Add a procedure that calls validate function to check a given array of DoubleArray::new.
   • This means DoubleArray::new will be a safe method as far as we validated.
3. Introduce unsafe DoubleArray::new_without_verification method for expert users.
   • This method doesn't check an array at initialization. The behavior is the same as the current DoubleArray::new method.
   • Some users who are sure their array is valid might want this feature for faster initialization.

Does this proposal make sense to you?

[vbkaisetsu]

SGTM.