created_at2020-01-31 22:27:07.062203
updated_at2020-06-22 00:07:12.092707
descriptionSlice-based custom DSTs
Christopher Durham (CAD97)



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.


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.




  • Added SliceWithHeader::from_slice, which is a specialization of _::new for slices of Copy types that can avoid some bookkeeping overhead.



  • Added the TryAllocSliceDst, a fallible analogue to AllocSliceDst.



  • Added a StrWithHeader type, counterpart to SliceWithHeader, but with a str.


Soundness Fixes

These fixes only have an impact if you are using Rust 1.42 or higher, and do not cause any known miscompilations (nor even fail miri). However, out of an abundance of caution, we have still seen fit to yank all versions of slice-dst in the 1.1 line, and urge you to upgrade to 1.2 as soon as possible.


  • Previously, construction of a thin slice DST would leak the allocated memory if a panic occurred during construction. #44 fixes most cases to clean up properly.


Soundness Fixes

  • alloc_slice_dst(_in) now properly support zero-sized types.

Related Crates

  • erasable: Erase pointers of their concrete type.
  • ptr-union: Pointer unions the size of a pointer.
  • rc-borrow: Borrowed forms of Rc and Arc.
  • rc-box: Known unique forms of Rc and Arc.

Minimum Supported Rust Version

We require a minimum Rust version of 1.41.0. This is for an adjustment of local trait impl checking.

Minimum version support is only guaranteed with minimal version resolution (-Z minimal-versions/--minimal-versions) due to how dependencies are handled. The minimum version of Rust will only be incremented with minor version bumps, not patch version bumps, and will be deliberate and clearly noted in change notes.


Licensed under either of

at your option.

If you are a highly paid worker at any company that prioritises profit over people, you can still use this crate. I simply wish you will unionise and push back against the obsession for growth, control, and power that is rampant in your workplace. Please take a stand against the horrible working conditions they inflict on your lesser paid colleagues, and more generally their disrespect for the very human rights they claim to fight for.


Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Commit count: 180

cargo fmt