search

mcy / best

The Best Library: a C++ STL replacement
Apache License 2.0
165 stars 2 forks source link

Fully generic references #32

Open mcy opened 3 months ago

mcy commented 3 months ago

This is an attempt to design "fully generic references", i.e., a way to manipulate a reference to any C++ type, including void and references.

The Problem

In vanilla C++, all types are in one of four categories:

Of these, objects and void can be cv-qualified. Note that the const in int() const is not cv-qualification: adding const to a function type leaves it unchanged. But, functions are always constants, and so always immutable, so we can treat all functions as always being const.

Objects and tame functions[1] can be the pointees of references. Only objects that are not an unbounded array type can be the element type of an array. Further, the built-in array types, int[4] and int[] are weird because they cannot appear as parameters and arguments to functions (although references to them can).

[1]: A tame function is one that does not have this qualification. int() is tame, but int() const is "abominable".

Type Constructors We Care About

In generic code, we want to require best::ref<T> instead of T, which is T& exactly when that is a valid type. However, best::ref<T&> already presents problems: we cannot write down a constructor for it because we can only take references as function arguments "by value". This necessitates that we add our own custom types for every "storage type constructor":

There are also concepts for identifying pointers, references, and arrays.

These define the following operations:

There's a few small problems with this formulation. First, we need to invent opaque class types to fill in for types like best::ref<T&>. In particular, we need to invent opaque types for the following:

Note that we do not need to define best::as_const<int()> because we have declared all function types as intrinsically const. Also, the array types suck, so we should discourage their use in generic code. Thus, best::array<T&, n> and other invented array types will be non-constructable and non-destructable. Instead, truly general arrays must go through best::value. The same goes for best::as_const<T&>.

Also, type classification traits need to not identify these as class types! Instead, they must respect.

Fat Pointer Types

However, this does not cover everything. First, T(&)[] is a useless type, we want to use best::span instead. Also, we want to have a mechanism for attaching metadata to pointers, a la &[T] and &dyn Tr in Rust. So, a best::box<best::dyn<Blah>> would want to be a void* plus a vtable, and derefing it needs to produce a Blah by value.

This suggests that we need to define an additional best::view<T> type, which may be the same as best::ref<T> but will be something else for so-called "fat pointer" types like arrays and dyns.

We call a type "thin" if best::ptr<T> has no metadata (formally T is NOT thin, if T is an array type or it is a class type satisfying requires { typename T::BestPtrMetadata; }. Otherwise, T is fat. Today, every type specifies a "metadata class":

struct my_meta {
  using pointee;  // `best::raw_ptr<T>` is `pointee*`
  using metadata;  // The public metadata type exposed to users. `my_meta` converts to/from it.

  best::layout layout() const;  // Returns the true layout of a particular value, given its pointer meta.
  auto deref(pointee*) const;  // Dereferences the pointer to obtain its corresponding view type.

  // Other requires functions, see `best::is_ptr_metadata` in ptr.h.
}

deref() must return either a pointer U* or a class type V. This defines the view type for T: if deref() returns a pointer, the view type is U&; otherwise, it is V (this is `best::view). The following are the view types for all types T:

Note that view types are always "lvalue flavored". There is no such thing as an rvalue view. Also, ptr -> view is a lossy operation. Given a view type, it is not possible to obtain a unique pointer type for it.

Then, what makes sense to do is as follows:

What's nice about this is that things like best::ptr<T[]> p; p->size(); Just Work!

Example Generic Code

// Write to a reference reference.
template <typename T>
void store_ref(best::ref<T&> dst, T& src) {
  dst.assign(src);
}

// Load a generic reference to reference, which may itself point to a reference.
// Note that function template deduction won't work here, and it must be called
// as `load_refref<MyType>(my_ref)`
template <typename T>
best::ref<T> load_refref(best::ref<best::ref<T>> r) {
  return r;  // Implicit conversion, just like T& -> T.
}

Corner cases

Some ordinary C++ reference types exist that we are going to pretend did not exist:

For this, we'll introduce best::is_valid<T>, which rejects all types like the above. All generic Best types will include a call to this concept to stop types like best::option<best::ref<int>&> existing and causing shenanigans.