[Variant] Revisit validation cost of infallible iterators

[scovich]

Yipes... I just realized that the iterator-based validation in this PR does too much validation. It recursively descends into all child objects/arrays and validates all the way to leaf level. Manipulations of deeply nested variant values could easily take on a quadratic flavor!

Originally posted by @scovich in #7704 (comment)

[scovich]

One potential way to break the recursion without sacrificing safety -- the array and object iterators both return &'v [u8] instead of Variant<'m, 'v>, and whoever consumes the iterator can invoke Variant::try_new on it.

Downsides:

• Resulting iterator is definitely less user-friendly
• No easy access to the needed VariantMetadata

[scovich]

I just realized, there's a possible connection with variant (un)shredding operations (#7715). One could easily imagine that a shredding operation would iterate over the fields of an object, looking for the values that need to be pulled out and repacking the remaining values. For efficiency reasons it will likely be important to work with the raw byte slice that contains each variant value, not fully decoded Variant instances.

[alamb]

Copy/pasting a comment from #7757 (comment) and a conversation between @friendlymatthew and @scovich that I think is relevant:

I think there are two distinct usecases and the validation behavior will likely differ between them:

1. Code that wants to programatically traverse Variants in some arbitrary order (e.g. tests, converting to json, etc) that will likely touch most/all of the Variant values and is inconvenient to have to check errors all the time
2. Code that wants to try to select a field from the Variant (eg. a query like variant_field(variant_column, "my.nested.field") or whatever.

I think our current behavior of Validate on construction works well for the first usecase

I think the second usecase will most likely prefer only validating the part of the variant on the path to retrieving the requested fied

Something like this:

// create a variant, validate on read
let variant = Variant::new_no_validation(&metadata, &value);
let field = variant.try_field("foo")?.try_field("bar")?

It would be on the user to choose the API that was appropriate (e.g. use of field() without first validating the variant can panic).

I think there is precident for this with rust slices:

• calling arr[100] when the 100 is out of bounds will panic
• Calling arr.get(100) does the bounds check

[scovich]

I started playing with this and hit a rough spot: There are actually three flavors of validation, not two:

• Full validation. Validates everything (all arrays, all entries, etc).
  • Costs O(n), where n is the size of the object in bytes (recurses into objects and arrays)
  • Highly recommended when dealing with untrusted input, to avoid panics
  • Also recommended if the object is to be traversed repeatedly (better ergonomics with amortized up-front validation cost)
  • The default
• Basic validation. Verifies the basic structure of the object without examining individual entries
  • Costs O(1)
  • A good middle ground when performing selective accesses to only parts of the object.
  • Especially helpful when traversing a deeply nested object (basic validation at every level, triggered lazily only when actually accessing that level)
  • Use try_ versions of accessors to avoid panics
• No validation whatsoever. Takes the bytes entirely at face value with no sanity checks at all.
  • I'm not sure there's a strong benefit to skipping basic validation, given how cheap it is?
  • When it be useful in practice, other than setting up unit tests with hard-wired bytes? (but even there, it seems better to validate those supposedly-correct bytes so we know the rest of the test is doing what we think it does)

I lean heavily toward full vs. basic as the only two choices... but then what to call them? The traditional try_foo vs. foo (or foo vs. foo_checked) strongly suggests that one is fallible and the other is not.

One possibility is to require a boolean full_validation parameter on all the try_new, with doc comments explaining how it works. But that adds complexity to every call site. It seems preferable to have short method names that perform full validation, and longer method names that only do basic validation (nudging people toward the safe approach by default).

Two other worries:

• If we're not careful, the "unchecked" versions will only be thin wrappers that unwrap the result of the checked version -- accepting panic risk for ergonomic reasons only, with no performance advantage whatsoever. We don't want to completely bifurcate the code, tho -- too hard to be sure validation actually captured all invariants (of both the data and the internal code accessing that data)
• None of this recruits the type system, leaving the user fully responsible to track whether validation already happened.

[alamb]

I lean heavily toward full vs. basic as the only two choices... but then what to call them? The traditional try_foo vs. foo (or foo vs. foo_checked) strongly suggests that one is fallible and the other is not.

I agree full and basic are a good target.

I think an important property is that all accesses remain safe in the Rust memory safety sense of the word -- an invalid input with basic checking could cause a panic but not undefined behavior / invalid memory accesses.

One possibility is to require a boolean full_validation parameter on all the try_new, with doc comments explaining how it works. But that adds complexity to every call site. It seems preferable to have short method names that perform full validation, and longer method names that only do basic validation (nudging people toward the safe approach by default).

In terms of naming, I suggest

• `Variant::new -> Variant that does basic checking (and might panic on invalid input)
• Variant::try_new -> Result<Variant> that does full checking and might return Result, but will not panic

Variant::new would be used with the output of VariantBuilder for example where Variant::try_new would be used with bytes that were read out of a parquet file

I think we should reserve the unchecked signifier for unsafe apis (which we can explore if we ever find the bounds checks are causing a significant slow down)

I think we can make the distinction clear on the documentation

Two other worries:

• If we're not careful, the "unchecked" versions will only be thin wrappers that unwrap the result of the checked version -- accepting panic risk for ergonomic reasons only, with no performance advantage whatsoever. We don't want to completely bifurcate the code, tho -- too hard to be sure validation actually captured all invariants (of both the data and the internal code accessing that data)

I agree the major benefit is ergonomics

In my mind the major validation cost we will be skipping is verifying all offsets for VariantObject fields and VariantList indexes even when all elements are not accessed.

• None of this recruits the type system, leaving the user fully responsible to track whether validation already happened.

I think this is ok and is inline with the use of Error vs Panics in this crate: https://github.com/apache/arrow-rs?tab=readme-ov-file#guidelines-for-panic-vs-result

[scovich]

take