Crate slice_dst

Source
Expand description

Support for custom slice-based DSTs.

By handling allocation manually, we can manually allocate the Box for a custom DST. So long as the size lines up with what it should be, once the metadata is created, Rust actually already handles the DSTs it already supports perfectly well, safely! Setting them up is the hard part, which this crate handles for you.

§Examples

We have a tree structure! Each node holds some data and its children array. In normal Rust, you would probably typically implement it something like this:

struct Node {
    data: &'static str,
    children: Vec<Arc<Node>>,
}

let a = Node { data: "a", children: vec![] };
let b = Node { data: "b", children: vec![] };
let c = Node { data: "c", children: vec![] };
let abc = Node { data: "abc", children: vec![a.into(), b.into(), c.into()] };

With this setup, the memory layout looks vaguely like the following diagram:

                                             +--------------+
                                             |Node          |
                                       +---->|data: "a"     |
+------------+    +---------------+    |     |children: none|
|Node        |    |Vec<Arc<Node>> |    |     +--------------+
|data: "abc" |    |[0]: +--------------+     |Node          |
|children: +----->|[1]: +------------------->|data: "b"     |
+------------+    |[2]: +--------------+     |children: none|
                  +---------------|    |     +--------------+
                                       |     |Node          |
                                       +---->|data: "c"     |
                                             |children: none|
                                             +--------------+

With this crate, however, the children array can be stored inline with the node’s data:

struct Node(Arc<SliceWithHeader<&'static str, Node>>);

let a = Node(SliceWithHeader::new("a", None));
let b = Node(SliceWithHeader::new("b", None));
let c = Node(SliceWithHeader::new("c", None));
// this vec is just an easy way to get an ExactSizeIterator
let abc = Node(SliceWithHeader::new("abc", vec![a, b, c]));
                         +-----------+
+-------------+          |Node       |
|Node         |    +---->|length: 0  |
|length: 3    |    |     |header: "a"|
|header: "abc"|    |     +-----------+
|slice: [0]: +-----+     |Node       |
|       [1]: +---------->|length: 0  |
|       [2]: +-----+     |header: "b"|
+-------------+    |     +-----------+
                   |     |Node       |
                   +---->|length: 0  |
                         |header: "c"|
                         +------------

The exact times you will want to use this rather than just standard types varries. This is mostly useful when space optimization is very important. This is still useful when using an arena: it reduces the allocations in the arena in exchange for moving node payloads to the heap alongside the children array.

§But how?

This is possible because of the following key building blocks:

So with these guarantees, we can “just” manually allocate some space, initialize it for some custom repr(C) structure, and convert it into a Box. From that point, Box handles managing the memory, including deallocation or moving it into another smart pointer, such as Arc.

SliceDst defines the capabilities required of the pointee type. It must be able to turn a trailing slice length into a Layout for the whole pointee, and it must provide a way to turn a untyped slice pointer *mut [()] into a correctly typed pointer.

The functions alloc_slice_dst and alloc_slice_dst_in provide a way to allocate space for a SliceDst type via the global allocator.

AllocSliceDst types are owning heap pointers that can create a new slice DST. They take an initialization routine that is responsible for initializing the uninitialized allocated place, and do the ceremony required to allocate the place and turn it into the proper type by delgating to SliceDst and alloc_slice_dst. They also handle panic/unwind safety of the initialization routine and prevent leaking of the allocated place due to an initialization panic.

TryAllocSliceDst is the potentially fallible initialization version.

All of these pieces are the glue, but SliceWithHeader and StrWithHeader put the pieces together into a safe package. They take a header and an iterator (or copyable slice) and put together all of the pieces to allocate a dynamically sized custom type.

Additionaly, though not strictly required, these types store the slice length inline. This gives them the ability to reconstruct pointers from fully type erased pointers via the Erasable trait .

Structs§

Traits§

  • AllocSliceDst
    Types that can allocate a custom slice DST within them.
  • SliceDst
    A custom slice-based dynamically sized type.
  • TryAllocSliceDst
    Types that can allocate a custom slice DST within them, given a fallible initialization function.

Functions§