BiBounded{Vec,BTreeMap}

[benluelo]

The current Bounded* types are incredibly useful, but sometimes it is necessary to have a minimum amount of items as well as a max. We currently maintain our own BiBoundedVec in-house, but I think that other people would find this useful as well.

Two ideas:

• Two separate types, with the BiBounded* type a wrapper over the Bounded* type to reuse immutable methods:

  struct BiBoundedBTreeMap<K, V, Min: Get<u32>, Max: Get<u32>>(BoundedBTreeMap<K, V, Max>, PhantomData<fn() -> Min>>;
  

• Only one type BiBounded* with a type alias filling in the minimum with 0:

  struct BiBoundedBTreeMap<K, V, Min: Get<u32>, Max: Get<u32>>(BTreeMap<K, V>, PhantomData<fn() -> (Min, Max)>>;
  
  type BoundedBTreeMap<K, V, Max> = BiBoundedBTreeMap<K, V, ConstU32<0>, Max>;
  

  An issue with this option is that infallible methods on the Bounded* type (like remove) would have to be fallible (if only specialization was stable :cry:)

(I'm leaning towards the former personally)

Again, happy to take this on if it's accepted!

[shawntabrizi]

Maybe we should just use a third party bounded vec crate which already supports upper and lower bound?

https://docs.rs/bounded-vec/latest/bounded_vec/

In any case, I think we can support upper and lower bound, where the lower bound generic is default to 0, and then it would be completely backwards compatible with the existing bounded vec structure.

I dont like introducing a new type here.

[benluelo]

I was going to suggest a third-party crate, but they all seem to use const generics (logically). There is #10613, but it hasn't been touched since January; I think it could use some love.

There also doesn't seem to be a good bounded map crate (from what I could find), so I think keeping the current bounded structures would be good.

In any case, I think we can support upper and lower bound, where the lower bound generic is default to 0, and then it would be completely backwards compatible with the existing bounded vec structure.

I considered this, but it has the same issue as the second option I suggested - infallible methods on a Bounded<0, Max> (currently just Bounded<Max>) structure that remove elements (pop, remove, drain, retain, clear, etc) will have to be made fallible, so it isn't entirely backwards compatible to just add the lower bound to the existing types.

(Also, generic parameters with a default must be trailing, so the types would have to be defined as Bounded<Max, Min = 0> which would be somewhat counterintuitive in my opinion)

[kianenigma]

I think unfortunately we have to re-implement new types. Reusing the same type for lower bound will be an issue, since operations that reduce the size are currently infallible.

What would be the main benefit of bringing the types here to substrate? I am not against it, but it can also be an independent crate, kinda like https://github.com/encointer/substrate-fixed/blob/master/RELEASES.md, which extends our "basic" arithmetic types, and is still usable by the ecosystem.

That being said, I am not against adding them to substrate either.

[benluelo]

I think extracting this out into a separate crate would be a good move, could be done in tandem with https://github.com/paritytech/substrate/issues/10613 too. Would this be something kept under the paritytech organization?

[kianenigma]

not necessarily, it can be under any org.

[shawntabrizi]

@benluelo thanks for the thoughtfulness you put into this.

I think with your comments in mind, I would be open to creating a new type, and adding it to Substrate.

If we plan to migrate it somewhere else in the future or whatever else, we can deal with that, but if you are interested to make the crate, sounds good to me.

Could we then also make BoundedVec a BiBoundedVec<Max, Min = 0> and handle all the infallible cases?

[benluelo]

Awesome! I don't think I can commit to maintaining this as a separate crate right now, but if it were to be made somewhere else I would absolutely contribute to it.

As for right now, Bounded*<Max> collections would have to be a wrapper around their BiBounded*<Max, Min = 0> counterparts, and just delegate the methods that are fallible for both to the wrapped type (this boilerplate could of course be reduced with a simple macro_rules! if it becomes too much).

Would we want to do #10613 at the same time as well?