If there are no field names in the variant, we'll mark it as not sorted.

The spec leaves this pretty ambiguous..

It makes sense to me

Seems fine. Especially since sortedness only matters if there are enough field names that binary search beats linear search (which usually starts around 10-20 entries).

On the other hand... why do the extra work to check for is_empty? The is_sorted will return a correct result either way.

It makes sense to me

It might help to give some more context here like

/// This method pre-populates the field name dictionary in the Variant Metadata 
/// with the specified field names, in order. 
///
/// You can use this to prepopulate a VariantBuilder with a sorted dictionary if 
/// you know the field names before hand somehow. Sorted dictionaries can accelerate
/// field access when reading Variants. 

I also think it would be great to add a note and a link to the documentation of VariantBuilder::build telling about this method

...
/// Note: the builder checks if the metadata dictionary is sorted and if it is
/// marks the metadata as sorted, which can accelerate reading Variant values.
/// Field names are added to the metadata dictionary in the order they are first 
/// encoutered. See [`Self::with_field_names`] to pre-populate field names in 
/// order if you know beforehand the fields that can appear in your objects
fn build(self) -> ...

I agree, thank you for your suggestion. I need to get better at my prose!

I am don't think it is important to verify these internal details of the field_ids -- they key thing is to verify that the object is sorted if the keys are pre-added in sorted order

likewise here, I don't think checking the field ids is important.

field_names?

Also, why impl Iterator instead of the more common impl IntoIterator, out of curiosity? Can also take items that impl Into<String>, for additional flexibility.

Also -- would it make sense to provide an impl FromIterator for MetadataBuilder, instead of or in addition to this constructor? Then people could build a new instance in all the usual rustic ways, e.g.

let builder = MetadataBuilder::from_iter(["a", "b", "c"]);

or

self.metadata_builder = ["a", "b", "c"].into_iter().collect();

I agree switching to IntoIterator would be nicer as would implemeting Extend

If we don't do it in this PR, let's file a ticket to fix follow on PRs

aside: On the off-chance somebody ever managed to insert more than 2**32-1 entries, this would silently produce wrong results. We should consider returning usize and require the caller to do the conversion, since they have a better chance of being able to handle the issue cleanly.

On the other hand, we have two potential sources of "protection" already:

1. Most machines will run out of memory long before they hit u32 overflow, and that will panic. So it would be hard to trigger the bug in the first place.
2. num_field_names returns usize. So we could make the builder's finish method fallible and then check for u32 overflow only once at the end. Downside is, then we did all the work to insert those extra field names even tho we're doomed to fail later.

One option could be to change the code to panic in this unlikely case and deal with it when / if we have an actual issue

As you point out, I don't think this is related to this PR

This is an expensive check, especially for a larger dictionary. Since the builder is append-only (can't change or remove existing entries), we could incrementally maintain an is_sorted flag instead?

Although the total number of operations is the same, it should be cheaper because the bytes of a freshly inserted field name will still be in CPU cache (having just been initialized and/or hashed). So the string comparison will be a lot faster than if it takes a cache miss after not having been accessed for a long time.

fn upsert_field_name(&mut self, field_name: &str) -> u32 {
    let (id, inserted) = self.field_names.insert_full(field_name.to_string());
    if inserted {
        let n = self.field_names.len();
        if n >= 2 && self.field_names[n-2] > self.field_names[n-1] {
            self.is_sorted = false;
        }
    }
    id as u32
}

let mut new_self = Self::new();
for field_name in field_names {
    let _ = new_self.upsert_field_name(field_name);
}
new_self

let mut new_self = Self::new();
new_self.extend(field_names);
new_self

This is an expensive check, especially for a larger dictionary. Since the builder is append-only (can't change or remove existing entries), we could incrementally maintain an is_sorted flag instead?

I am not sure it is all that expensive
https://doc.rust-lang.org/core/iter/trait.Iterator.html#method.is_sorted

I think it simply checks all the elements pariwise (code)

I don't think it is any more/less expensive in theory to check the dictionary on write than to do the checks incrementally as the variant is written. In each case it needs to do N-1 comparisons where N is the number of dictionary entries

Yeah it comes down to CPU caches and memory bandwidth, for larger dictionaries and/or longer strings. Technically constant factors but not necessarily ones we should ignore.

This would wipe out any previously added field names, which seems like an unnecessary footgun?

Also, similar to above -- would it make sense to impl Extend for MetadataBuilder and then extend here instead?

Replacing the metadata builder also invalidates any previously created objects which seems likely to be pretty bad

I agree we should change this to append to (not replace) existing fields

    pub fn with_field_names<'a>(mut self, field_names: impl Iterator<Item = &'a str>) -> Self {
        for field_name in field_names {
          self.metadata_builder.upsert_field_name(field_name)
        }
        self
     }

The Extend is an excellent idea as well, but it is less clear to me that Extend on a VariantBuilder should only extend fields -- I would expect Extend to take Variants and logically extend the in-progress variant 🤔

Oh, Extend (and FromIterator) suggestion was only for the underlying MetadataBuilder. Agree it would be weird to have one for field names only at variant builder level!

This is an expensive check, especially for a larger dictionary. Since the builder is append-only (can't change or remove existing entries), we could incrementally maintain an is_sorted flag instead?

I am not sure it is all that expensive
https://doc.rust-lang.org/core/iter/trait.Iterator.html#method.is_sorted

I think it simply checks all the elements pariwise (code)

I don't think it is any more/less expensive in theory to check the dictionary on write than to do the checks incrementally as the variant is written. In each case it needs to do N-1 comparisons where N is the number of dictionary entries

One option could be to change the code to panic in this unlikely case and deal with it when / if we have an actual issue

As you point out, I don't think this is related to this PR

Replacing the metadata builder also invalidates any previously created objects which seems likely to be pretty bad

I agree we should change this to append to (not replace) existing fields

    pub fn with_field_names<'a>(mut self, field_names: impl Iterator<Item = &'a str>) -> Self {
        for field_name in field_names {
          self.metadata_builder.upsert_field_name(field_name)
        }
        self
     }

The Extend is an excellent idea as well, but it is less clear to me that Extend on a VariantBuilder should only extend fields -- I would expect Extend to take Variants and logically extend the in-progress variant 🤔

I agree switching to IntoIterator would be nicer as would implemeting Extend

If we don't do it in this PR, let's file a ticket to fix follow on PRs

I noticed the variant_interop tests will fail if we mark empty field names as sorted, hence the additional branch.

Some additional assertions that test the constructor methods

this is quite neat

This is pretty neat.

I think we should add tests of some type for this impls

I personally suggest adding to the doc tests for MetadataBuilder, something like

let metadata = MetadataBuilder::from(["foo", "bar" "baz"])

or add a specific test below

Out of curiosity, why AsRef<str> instead of Into<String>? The former forces a copy even when passing owned strings.

Tho IMO this is a messy part of rust... we really want something Cow-flavored that handles all of Deref + Borrow + AsRef + Into... today you have to pick just one, because adding a second causes ambiguity.

That is fair. I chose AsRef<str> since the upsert_field_name took a &str. Since upsert_field_name is a public method, I chose not to update the function header and work around this.

As for using Cows, I think this is a really good idea. There are some areas where I feel like we could really benefit from an owned string. For example:

(&& has short-circuit behavior and avoids the string comparison when we already broke sorting)

Also, a code comment might help here, there's a lot to unpack:

• An empty dictionary is unsorted (ambiguous in spec but required by interop tests)
• A single-entry dictionary is trivially sorted
• Otherwise, an already-sorted dictionary becomes unsorted if the new entry breaks order

👨‍🍳 👌

love it