Add more type-erasing wrapper types

[lewissbaker]

We currently have only two type-erasing wrapper types:

• any_unique which always heap-allocates the wrapped object
• any_ref which just holds a pointer/reference to a wrapped object and does not have any ownership

However, there are many more flavours of type-erasing wrappers that we'd like to be able to support for different situations.

Some examples:

• An any_scheduler should be nothrow copyable/movable and equality comparable. Currently it's built on top of any_unique and heap-allocates when it copies.
• We would also like to be able to support small-object optimisations to avoid heap-allocations for small wrapped objects. e.g. for schedulers that are often copied and only require one or two pointers of storage
• And in some cases we'd like to be able to statically guarantee that an object is stored inline (and make the program ill-formed if this is not going to be the case) - e.g. for storing a type-erased operation-state inline in contexts where heap-allocations are prohibitively expensive or prohibited.

There are 5 broad axes on which we can consider the behaviour of type-erasing wrappers:

Object Storage - where and how is the wrapped object stored

• Heap-allocated - object is stored in storage allocated on the heap by an allocator, wrapper holds a pointer to this storage
• Inline - object is stored inline in the wrapper, cannot store objects larger than this type
• Hybrid - Store small objects inline and larger objects on the heap (aka. Small-Object-Optimisation)
• Reference - object is stored in storage not managed by the wrapper, wrapper only stores a pointer to this object

V-Table Storage - how does the wrapper store the vtable for the type-erased object

• Indirect Vtable - vtable is stored as a static object and wrappers hold a pointer to this shared vtable storage.
• Inline Vtable - vtable entries are stored inline in the wrapper. Avoids an indirection when calling a function and also allows cross-casting from one type-erased wrapper to another with a narrower interface, with entries possibly in a different order.
• Hybrid Vtable - Store vtable inline for small vtables and indirect for larger vtables.

Ownership - What kind of ownership relationship does the wrapper have to the wrapped object

• Unique ownership - the wrapped object is uniquely owned by the wrapper object
• Shared ownership / reference counted - the wrapper shares ownership of the wrapped object between one or more instances of the wrapper
• Non-owned - the wrapper does not own the wrapped object but only holds a reference to it. Ownership is managed outside of the wrapper

Copyability - Does the wrapper support move/copy operations

• Non-movable - The wrapper is not copyable/movable.
• Move-only - The wrapper object is moveable but not copyable. Sub variants here on whether move-constructor is noexcept or not.
• Copyable - The wrapper object is copyable (which implies movability). Sub variants here on whether copy-constructor is noexcept or not.

Comparability - Does the wrapper support equality comparisons or not.

• Not equality comparable
• Equality comparable - compare object identity
• Equality comparable - compare for identical types, T, and defer to concrete operator==(const T&, const T&) if types are identical.
• Three-way-comparable - it's not expected that this will be a common case, although it may be useful for being able to sort type-erased objects. Would expect to sort based on type_index first and then dispatch to concrete operator<=> for cases where the types are identical.

Note that not all combinations of these axes make sense. It would be good to expose and give names to certain common combinations of these.

We already have:

• any_ref<typename CPOs...> Reference, Hybrid Vtable, non-owned, noexcept copyable, equality comparable (object identity)
• any_unique<typename CPOs...> Heap-allocated, Hybrid Vtable, unique ownership, noexcept move-only, not equality comparable

I suggest also adding the following:

• any_object<size_t InlineSize, size_t InlineAlignment, bool RequireNoexceptMove, typename... CPOs> Hybrid storage, unique ownership, hybrid vtable, if RequireNoexceptMove then can only type-erase types with noexcept move-constructor.
• any_inplace_object<size_t InlineSize, size_t InlineAlignment, bool RequireNoExceptMove, typename... CPOs> Same as any_object but with always-inline storage. Ill-formed to type-erase an object that doesn't fit inside storage with InlineSize and InlineAlignment.
• any_value<size_t InlineSize, size_t InlineAlignment, bool RequireNoexceptMove, typename CPOs...> Hybrid storage, unique ownership, hybrid vtable, if RequireNoexceptMove then T's move constructor/assignment is required to be noexcept, copy operations are not noexcept since they might allocate.
• any_inplace_value<size_t InlineSize, size_t InlineAlignment, bool RequireNoexceptCopy, bool RequireNoexceptMove, typename CPOs...> Same as any_value but where the object is always stored inline and trying to type-erase an object that does not fit into InlineSize/InlineAlignment is ill-formed.
• any_shared<typename CPOs...> Heap-allocated, shared-ownership, hybrid vtable, nothrow copyable/movable

Each of these could also possibly be made comparable by defining special CPOs for equality-comparisons and/or three-way-comparisons and adding those special CPOs to the list of CPOs to be type-erased.

[lewissbaker]

Some questions:

• What do people think of the suggested semantics of the different type-erasure types?
• What do people think of the suggested naming?
• Should the type-erasing wrappers be default constructible and just construct to an invalid object?

[ericniebler]

I can imagine uses cases for all of these, but the amount of complexity implied seems outsize for the needs of unifex. [Nothrow] copyability/movability can be handled by special CPOs, assuming we augment the type-erasing wrappers with a mixin system -- with I feel like we should do anyway to give type-erasing wrappers named member functions. I wonder if we could even use the CPOs and mixins to implement different storage strategies.

[lewissbaker]

We could certainly look at implementing this using a policy-based design to reduce the number of types. I'll see how I go implementing any_object and any_inplace_object to see what can be factored out.

I know when I'd mentioned the idea of a policy-based design to @kirkshoop in the past his preference was to have specific names for different categories of wrapper (much like we have unique_ptr, shared_ptr, weak_ptr, etc.).

[ericniebler]

If you think of the CPOs as policies, then we already have a policy based design. I'm just suggesting we use it to implement the things you describe here. We'll need to extend the mechanism first, though.

[lewissbaker]

First pass implementation of any_object in #304

[lewissbaker]

The any_object PR and a bunch of refactoring has now been merged.

Next steps: [] any_value - a copyable type erased object with a sbo. [] any_shared - a ref counted heap allocated object [] support for equality comparison