Type Erasure in Zig, untested.

erase.zig

pub const erased_runtime_safety = false;
pub const erased_debug_names = false;

/// Returns a struct containing a field named "unique_global".
/// There is exactly one such unique_global for every passed type.
/// The address of `unique_global` is guaranteed to be unique for each type.
/// If `erased_debug_names` is true, unique_global is of type [N:0]u8
/// and its value is the name of the passed type T.  Otherwise unique_global
/// is of type `u8` and its value is meaningless.
fn TypeIdStruct(comptime T: type) type {
    if (erased_debug_names) {
        return struct {
            var unique_global = @typeName(T);
        };
    } else {
        return struct {
            var unique_global: u8 = 0;
        };
    }
}

/// Returns the pointer type backing a potentially optional pointer.
/// If the passed value is not a slice or pointer, returns null
/// *T -> *T
/// ?*T -> *T
/// T -> null (if T is not a pointer)
/// *const T -> *const T
/// ?*const T -> *const T
/// *allowzero T -> *allowzero T
/// ?*allowzero T -> null (not a pointer)
/// [*c]T -> [*c]T
/// ?[*c]T -> null (not a pointer)
/// []T -> []T
/// ?[]T -> null (not a pointer)
fn PointerWithoutOptional(comptime OptT: type) ?type {
    comptime {
        var PtrT = OptT;
        var info = @typeInfo(OptT);
        const is_optional = info == .Optional;
        if (is_optional) {
            PtrT = info.Optional.child;
            info = @typeInfo(PtrT);
        }
        if (info != .Pointer or (is_optional and (info.Pointer.size == .Slice or info.Pointer.size == .C or info.Pointer.is_allowzero))) {
            return null;
        } else {
            return PtrT;
        }
    }
}

fn pointerAlignment(comptime PtrT: type) comptime_int {
    comptime {
        var info = @typeInfo(PtrT);
        assert(info == .Pointer);
        if (info.Pointer.alignment == 0) {
            return @alignOf(info.Pointer.child);
        } else {
            return info.Pointer.alignment;
        }
    }
}

/// A debug identifier that can be used to compare types at runtime.
/// if erased_runtime_safety is false, this has zero size and all
/// of its functions are no-ops.
pub const DebugTypeId = struct {
    /// The unknown type id.  All assert checks will pass with this type id.
    pub const UNKNOWN = mem.zeroes(DebugTypeId);
    
    /// A value that is unique for each type.  If this is zero,
    /// then the type has not been specified.
    unique_value: if (erased_runtime_safety) usize else void,
    
    /// If erased_runtime_safety is true, creates a runtime identifier
    /// for the desired type.  This identifier can be used to compare
    /// this type to other types at runtime.
    pub inline fn init(comptime T: type) DebugTypeId {
        if (erased_runtime_safety) {
            return DebugTypeId {
                .unique_value = @ptrToInt(&TypeIdStruct(T).unique_global),
            };
        } else {
            comptime assert(@sizeOf(DebugTypeId) == 0);
            return undefined;
        }
    }
    
    /// Returns true if this type is valid.  If this returns false,
    /// the type is considered unknown and all safety checks are
    /// disabled for this type.
    pub fn isKnown(self: DebugTypeId) {
        return self.unique_value != UNKNOWN.unique_value;
    }

    /// Asserts that two type ids are the same.
    /// This check can only be performed at runtime.
    pub fn assertSame(self: DebugTypeId, other: DebugTypeId) void {
        if (erased_runtime_safety and self.isKnown() and other.isKnown()) {
            if (self.unique_value != other.unique_value) {
                if (erased_debug_names) {
                    panic("Erased type mismatch! Expected %s but found %s.", .{self.getDebugTypeName(), other.getDebugTypeName()});
                } else {
                    panic("Erased type mismatch! Enable erased_debug_names to get more detailed info.", .{});
                }
            }
        }
    }

    /// Asserts that this type represents the same type as T.
    /// This check can only be performed at runtime.
    pub fn assertSameType(self: DebugTypeId, comptime T: type) void {
        self.assertSame(init(T));
    }
    
    /// Asserts that PtrT is a non-slice pointer to this type.
    /// PtrT may have any modifiers including const and align.
    /// Optional pointers are also allowed.
    /// This check can only be performed at runtime.
    pub fn assertIsPointer(self: DebugTypeId, comptime PtrT: type) {
        if (erased_runtime_safety and self.isKnown()) {
            comptime var info = @typeInfo(PtrT);
            comptime if (info == .Optional) {
                info = @typeInfo(info.child);
            }
            if (info != .Pointer or info.Pointer.size == .Slice) {
                @compileError("Erased type mismatch! Expected non-slice pointer but found "++@typeName(PtrT));
            }
            self.assertSame(init(info.child));
        }
    }
    
    // Asserts that PtrT is a slice pointer to this type.
    // PtrT may have any modifiers including const and align.
    // Optional slices are not allowed.
    // This check can only be performed at runtime.
    pub fn assertIsSlice(self: DebugTypeId, comptime SliceT: type) {
        if (erased_runtime_safety and self.isKnown()) {
            const info = @typeInfo(SliceT);
            if (info != .Pointer or info.Pointer.size != .Slice) {
                @compileError("Erased type mismatch! Expected slice pointer but found "++@typeName(SliceT));
            }
            self.assertSame(init(info.child));
        }
    }

    /// If erased_runtime_safety and erased_debug_names are enabled,
    /// returns the name of a type from its unique id.  Otherwise,
    /// calling this is a compile error.
    pub fn getDebugTypeName(self: DebugTypeId) [:0]const u8 {
        if (erased_debug_names and erased_runtime_safety) {
            if (self.isKnown()) {
                return mem.spanZ(@intToPtr([*:0]u8, self.unique_value));
            } else {
                return "(unknown type)";
            }
        } else {
            @compileError("Runtime type safety is disabled, cannot look up debug type name.");
        }
    }
};

/// A runtime-known type.
/// 16 bytes with safety checks, 8 bytes without.
pub const ErasedType = struct {
    /// The size of a single instance, including padding.
    /// If for some reason you have a type over 4 GB long,
    /// it's not compatible with this type erasure library.
    /// Using a u32 here makes this struct 8 bytes,
    /// which guarantees it won't waste space when packed
    /// alongside a usize.
    size: u32,

    /// Alignment of a single allocation.  If this type backs
    /// an array pointer, this alignment is only the alignment
    /// of the first instance.
    alignment: u29,

    /// Debug type id for safety checks
    debug_id: DebugTypeId = DebugTypeId.UNKNOWN,
    
    /// Creates an ErasedType from a comptime-known type.
    pub fn init(comptime T: type) ErasedType {
        return initAligned(T, @alignOf(T));
    }
    
    /// Creates an ErasedType from the child of a comptime-known
    /// pointer type, using the pointer's alignment.
    pub fn initPointerChild(comptime PtrT: type) ErasedType {
        
    }

    
    /// Creates an ErasedType from a comptime-known type with a specified alignment.
    pub fn initAligned(comptime T: type, alignment: u29) ErasedType {
        if (@sizeOf(T) == 0) {
            @compileError("Cannot create erased type for zero-sized type: " ++ @typeName(T));
        }
        if (T == ErasedType or
            T == ErasedPtr or
            T == ErasedSizedPtr or
            T == ErasedArrayPtr or
            T == ErasedSlice) {
            @compileError(
            \\ Not allowed to erase erased types.
            \\ This would break some of the generic functions in this package.
            \\ If you really need to do this for some reason, you will need to wrap the erased type in a struct.
            );
        }
        return .{
            .size = @sizeOf(T),
            .alignment = alignment,
            .debug_id = debugTypeId(T),
        };
    }
    
    /// Asserts that two type ids are the same.
    /// This check can only be performed at runtime.
    pub fn assertSame(self: ErasedType, other: ErasedType) void {
        self.debug_id.assertSame(other.debug_id);
    }

    /// Asserts that this type represents the same type as T.
    /// This check can only be performed at runtime.
    pub fn assertSameType(self: DebugTypeId, comptime T: type) void {
        self.assertSame(init(T));
    }
    
    /// Asserts that PtrT is a non-slice pointer to this type.
    /// PtrT may have any modifiers including const and align.
    /// Optional pointers are also allowed.
    /// Parts of this check can only be performed at runtime.
    pub fn assertIsPointer(self: DebugTypeId, comptime PtrT: type) {
        const ActualPtrT = comptime PointerWithoutOptional(PtrT) orelse @compileError("Type is not a pointer: "++@typeName(PtrT));
        self.assertSameType();
    }
    
    // Asserts that PtrT is a slice pointer to this type.
    // PtrT may have any modifiers including const and align.
    // Optional slices are not allowed.
    // Parts of this check can only be performed at runtime.
    pub fn assertIsSlice(self: DebugTypeId, comptime SliceT: type) {
        var info = @typeInfo(SliceT);
        if (info == .Pointer and info.Pointer.size == .Slice) {
            self.assertSameType(info.child);
        } else {
            @compileError("Type is not a slice: "++@typeName(SliceT));
        }
    }
};

/// An erased pointer to a single item.
/// With safety turned off, this is the same size as a raw pointer.
/// Does not contain size information.
/// Supports init, as, asPtr
pub const ErasedPtr = struct {
    /// pointer to the data
    ptr: usize,
    
    /// debug type id for safety checks,
    /// compiles to nothing if safety is turned off.
    debug_id: DebugTypeId = DebugTypeId.UNKNOWN,
    
    /// Converts a known pointer to an ErasedPtr.
    /// Will coerce `[*c]T` or `?*T`.
    pub fn init(ptr: var) ErasedPtr {
        const PtrT = @TypeOf(ptr);
        if (PtrT == ErasedPtr) {
            return ptr;
        } else if (PtrT == ErasedSizedPtr) {
            return ptr.strip();
        } else {
            comptime var ptrInfo = @typeInfo(PtrT);
            const is_optional = ptrInfo == .Optional;
            if (is_optional) {
                ptrInfo = @typeInfo(ptrInfo.child);
            }
            if (ptrInfo == .Pointer) {
                if (ptrInfo.Pointer.size == .One or (ptrInfo.Pointer.size == .C and !is_optional)) {
                    const T = ptrInfo.child;
                    return .{
                        .ptr = @ptrToInt(ptr),
                        .debug_id = debugTypeId(T),
                    };
                } else {
                    @compileError("Cannot coerce type to single pointer: "++@typeName(PtrT));
                }
            } else {
                @compileError("Cannot coerce non-pointer type to single pointer: "++@typeName(PtrT));
            }
        }
    }
    
    /// Converts to a pointer of known type
    pub fn as(self: ErasedPtr, comptime T: type) *T {
        return self.asPtr(*T);
    }
    
    /// Converts to a pointer of specified type
    pub fn asPtr(self: ErasedPtr, comptime PtrT: type) PtrT {
        self.debug_id.assertIsPointer(PtrT);
        return @intToPtr(PtrT, self.ptr);
    }
    
    /// Adds size information
    pub fn inflate(self: ErasedPtr, comptime T: type) ErasedSizedPtr {
        self.debug_id.assertIsSameType(T);
        return .{
            .ptr = self.ptr,
            .child = ErasedType.init(T),
        };
    }
    
    /// Adds size information
    pub fn inflate(self: ErasedPtr, child: ErasedType) ErasedSizedPtr {
        self.debug_id.assertIsSame(child.debug_id);
        return .{
            .ptr = self.ptr,
            .child = child,
        };
    }
};

/// An erased pointer to a single item with size information
/// Use strip() to convert to an ErasedPtr
pub const ErasedSizedPtr = struct {
    /// pointer to the data
    ptr: usize,
    
    /// type and size information
    child: ErasedType,
    
    /// Converts a known pointer to an ErasedSizedPtr.
    /// Will coerce `[*c]T` or `?*T`.
    pub fn init(ptr: var) ErasedSizedPtr {
        const PtrT = @TypeOf(ptr);
        if (PtrT == ErasedSizedPtr) {
            return ptr;
        } else {
            comptime var ptrInfo = @typeInfo(PtrT);
            const is_optional = ptrInfo == .Optional;
            if (is_optional) {
                ptrInfo = @typeInfo(ptrInfo.child);
            }
            if (ptrInfo == .Pointer) {
                if (ptrInfo.Pointer.size == .One or (ptrInfo.Pointer.size == .C and !is_optional)) {
                    const T = ptrInfo.child;
                    return .{
                        .ptr = @ptrToInt(ptr),
                        .child = ErasedType.init(T),
                    };
                } else {
                    @compileError("Cannot coerce type to single pointer: "++@typeName(PtrT));
                }
            } else {
                @compileError("Cannot coerce non-pointer type to single pointer: "++@typeName(PtrT));
            }
        }
    }
    
    /// Converts to a pointer of known type
    pub fn as(self: ErasedSizedPtr, comptime T: type) *T {
        return self.asPtr(*T);
    }
    
    /// Converts to a pointer of specified type
    pub fn asPtr(self: ErasedSizedPtr, comptime PtrT: type) PtrT {
        self.child.assertIsPointer(PtrT);
        return @intToPtr(PtrT, self.ptr);
    }
    
    /// Sets the data this pointer points to
    /// `value` can be an ErasedPtr, an ErasedSizedPtr,
    /// or an instance of the backing type.  `undefined`
    /// is also a valid parameter.
    pub fn set(self: ErasedSizedPtr, value: var) void {
        const T = @TypeOf(value);
        if (T == ErasedSizedPtr) {
            self.child.assertSame(value.child);
            @memcpy(@intToPtr([*]u8, self.ptr), @intToPtr([*]u8, value.ptr), self.child.size);
        } else if (T == ErasedPtr) {
            self.child.debug_id.assertSame(value.debug_id);
            @memcpy(@intToPtr([*]u8, self.ptr), @intToPtr([*]u8, value.ptr), self.child.size);
        } else if (T == @TypeOf(undefined)) {
            @memset(@intToPtr([*]u8, self.ptr), undefined, self.child.size);
        } else {
            self.child.assertIsSameType(T);
            self.as(T).* = value;
        }
    }
    
    /// Removes size information
    pub fn strip(self: ErasedSizedPtr) ErasedPtr {
        return .{
            .ptr = self.ptr,
            .debug_id = self.child.debug_id,
        };
    }
};

/// An erased pointer to many items
/// Supports init, as, asPtr, at, add, slice
pub const ErasedArrayPtr = struct {
    /// pointer to the data
    ptr: usize,
    
    /// backing type (for index calculations)
    child: ErasedType,

    /// Creates an erased array pointer from an array pointer
    /// Will coerce *[N]T or [*c]T to [*]T
    pub fn init(ptr: var) ErasedArrayPtr {
        const PtrT = @TypeOf(ptr);
        if (PtrT == ErasedArrayPtr) {
            return ptr;
        } else {
            comptime var ptrInfo = @typeInfo(PtrT);
            const is_optional = ptrInfo == .Optional;
            // Ignore a leading optional
            if (is_optional) {
                ptrInfo = @typeInfo(ptrInfo.Optional.child);
            }
            // Must be a pointer
            if (ptrInfo == .Pointer) {
                if (ptrInfo.Pointer.size == .Many or (ptrInfo.Pointer.size == .C and !is_optional)) {
                    const T = ptrInfo.Pointer.child;
                    return .{
                        .ptr = @ptrToInt(ptr),
                        .item_size = @sizeOf(T),
                        .debug_id = debugTypeId(T),
                    };
                } else if (ptrInfo.Pointer.size == .One) {
                    const childInfo = @typeInfo(ptrInfo.Pointer.child);
                    if (childInfo == .Array) {
                        // coerce *[N]T to [*]T
                        const T = childInfo.Array.child;
                        return .{
                            .ptr = @ptrToInt(ptr),
                            .item_size = @sizeOf(T),
                            .debug_id = debugTypeId(T),
                        };
                    } else {
                        @compileError("Cannot coerce single pointer type to ErasedArrayPtr: "++@typeName(@TypeOf(ptr)));
                    }
                } else {
                    @compileError("Cannot coerce type to ErasedArrayPtr: "++@typeName(@TypeOf(ptr)));
                }
            } else {
                @compileError("Cannot coerce non-pointer type to ErasedArrayPtr: "++@typeName(@TypeOf(ptr)));
            }
        }
    }
    
    /// Converts to a pointer of known type
    pub fn as(self: ErasedArrayPtr, comptime T: type) [*]T {
        return self.asPtr([*]T);
    }

    /// Converts to a pointer of specified type
    pub fn asPtr(self: ErasedArrayPtr, comptime PtrT: type) PtrT {
        self.child.assertIsPointer(PtrT);
        return @intToPtr(PtrT, self.ptr);
    }

    /// Creates an ErasedPtr to the item at the specified index
    pub fn at(self: ErasedArrayPtr, index: usize) ErasedSizedPtr {
        return ErasedSizedPtr{
            .ptr = self.ptr + self.child.size * index,
            .child = self.child,
        };
    }
    
    /// Returns an ErasedArrayPtr offset from this pointer
    pub fn add(self: ErasedArrayPtr, count: isize) ErasedArrayPtr {
        return ErasedArrayPtr{
            .ptr = self.ptr + self.child.size * count,
            .child = self.child,
        };
    }
    
    /// Returns an ErasedSlice of data in this pointer
    pub fn slice(self: ErasedArrayPtr, start: usize, end: usize) ErasedSlice {
        assert(start <= end);
        return ErasedSlice{
            .ptr = self.add(start),
            .len = end - start,
        };
    }
};

/// An erased pointer and length.
/// Supports empty, init, as, asPtr, at, slice
pub const ErasedSlice = struct {
    /// pointer to untyped data
    ptr: ErasedArrayPtr,

    /// number of items in the slice
    len: usize,
    
    /// Creates an empty slice of the given type
    pub fn empty(comptime T: type) ErasedSlice {
        return .{
            .ptr = .{
                .ptr = undefined,
                .child = ErasedType.init(T),
            },
            .len = 0,
        };
    }
    
    /// Creates an empty slice of the given type
    pub fn emptyErased(child: ErasedType) ErasedSlice {
        return .{
            .ptr = .{
                .ptr = undefined,
                .child = child,
            },
            .len = 0,
        };
    }
    
    /// Creates an erased slice from a known slice
    /// Will coerce *[N]T to []T.
    pub fn init(slice: var) ErasedSlice {
        const SliceT = @TypeOf(slice);
        if (SliceT == ErasedSlice) {
            return slice;
        } else {
            const ptrInfo = @typeInfo(SliceT);
            if (ptrInfo == .Pointer) {
                if (ptrInfo.Pointer.size == .Slice) {
                    return .{
                        .ptr = ErasedArrayPtr.init(slice.ptr),
                        .len = slice.len,
                    };
                } else if (ptrInfo.Pointer.size == .One) {
                    const childInfo = @typeInfo(ptrInfo.Pointer.child);
                    if (childInfo == .Array) {
                        return .{
                            .ptr = .{
                                .ptr = @ptrToInt(slice),
                                .child = ErasedType.init(childInfo.Array.child),
                            },
                            .len = childInfo.len,
                        };
                    } else {
                        @compileError("Cannot coerce single pointer type to ErasedSlice: "++@typeName(@TypeOf(slice)));
                    }
                } else {
                    @compileError("Cannot coerce array pointer type to ErasedSlice: "++@typeName(@TypeOf(slice)));
                }
            } else {
                @compileError("Cannot convert non-pointer type to ErasedSlice: "++@typeName(@TypeOf(slice)));
            }
        }
    }

    /// Converts to a typed slice
    pub fn span(self: ErasedSlice, comptime T: type) []T {
        return self.spanSlice([]T);
    }
    
    /// Converts to a specified typed slice
    pub fn spanSlice(self: ErasedSlice, comptime SliceT: type) SliceT {
        self.child.assertIsSlice(SliceT);
        // get the pointer type for this slice
        comptime var ptrInfo = @typeInfo(SliceT);
        comptime ptrInfo.Pointer.size = .Many;
        const PtrT = @Type(ptrInfo);
        // get the slice
        if (self.len != 0) {
            return @intToPtr(PtrT, self.ptr)[0..self.len];
        } else {
            return &[0]ptrInfo.child{};
        }
    }
    
    /// Returns the slice of bytes backing this slice
    pub fn spanBytes(self: ErasedSlice) []u8 {
        return @ptrToInt([*]u8, self.ptr)[0..self.len * self.child.size];
    }

    /// Generic alias for span
    pub const as = span;

    /// Generic alias for spanSlice
    pub const asPtr = spanSlice;

    /// Returns an erased pointer to the item at the given index
    pub fn at(self: ErasedSlice, index: usize) ErasedSizedPtr {
        assert(index < self.len);
        return ptr.at(index);
    }

    /// Returns a sub-slice of this slice
    pub fn slice(self: ErasedSlice, start: usize, end: usize) ErasedSlice {
        assert(end <= self.len);
        return ptr.slice(start, end);
    }
    
    /// Copies from the passed slice into this slice.
    /// The two slices must be the same length.
    /// The two slices may alias as long as their offset is a multiple of the item size.
    pub fn copyForwards(dest: ErasedSlice, src: ErasedSlice) void {
        assert(dest.len == src.len);
        dest.ptr.child.assertSame(src.ptr.child);

        var posDest = @intToPtr([*]u8, dest.ptr.ptr);
        var posSrc = @intToPtr([*]const u8, src.ptr.ptr);
        const stride = src.ptr.child.size;
        const endDest = posDest + stride * dest.len;
        
        // Can't do one big memcpy because the slices are allowed to alias.
        // but this at least guarantees that 
        while (posDest < endDest) {
            @memcpy(posDest, posSrc, stride);
            posDest += stride;
            posSrc += stride;
        }
    }

    /// Copies from the passed slice into this slice.
    /// The two slices must be the same length.
    /// The two slices may alias as long as their offset is a multiple of the item size.
    pub fn copyBackwards(dest: ErasedSlice, src: ErasedSlice) void {
        assert(dest.len == src.len);
        dest.ptr.child.assertSame(src.ptr.child);

        const endDest = @intToPtr([*]u8, dest.ptr.ptr);
        const endSrc = @intToPtr([*]const u8, src.ptr.ptr);
        const stride = src.ptr.child.size;
        var posDest = endDest + stride * dest.len;
        var posSrc = endSrc + stride * dest.len;
        
        // Can't do one big memcpy because the slices are allowed to alias.
        // but this at least guarantees that items don't alias.
        while (posDest > endDest) {
            posDest -= stride;
            posSrc -= stride;
            @memcpy(posDest, posSrc, stride);
        }
    }
    
    /// Copies from the passed slice into this slice.
    /// The two slices must be the same length.
    /// The two slices must not alias
    pub fn copyNoalias(dest: ErasedSlice, src: ErasedSlice) void {
        assert(dest.len == src.len);
        dest.ptr.child.assertSame(src.ptr.child);

        const destPtr = @intToPtr([*]u8, dest.ptr.ptr);
        const srcPtr = @intToPtr([*]const u8, src.ptr.ptr);
        const length = src.ptr.child.size * dest.len;
        @memcpy(destPtr, srcPtr, length);
    }
    
    /// Fills the passed slice with an erased value.
    /// The value can be an instance of the backing type,
    /// an `ErasedSizedPtr` or `ErasedPtr`, or `undefined`.
    /// If the value is an erased pointer, it must not alias the slice.
    pub fn fill(dest: ErasedSlice, value: var) void {
        var i = @as(usize, 0);
        const len = dest.len;
        while (i < len) : (i += 1) {
            dest.at(i).set(value);
        }
    }
};

/// Namespace containing erased allocation functions
pub const allocation = struct {
    /// Allocates memory of the right alignment and size.
    pub fn create(allocator: *Allocator, erased_type: ErasedType) !ErasedSizedPtr {
        const bytes = try allocator.reallocFn(allocator, &[0]u8{}, undefined, erased_type.size, erased_type.alignment);
        return ErasedPtr{
            .ptr = @ptrToInt(bytes.ptr),
            .child = erased_type,
        };
    }
    
    /// Frees memory allocated by create.
    pub fn destroy(allocator: *Allocator, data: ErasedSizedPtr) void {
        if (erased_runtime_safety) {
            assert(mem.isAligned(data.ptr, erased_type.alignment));
        }
        const slice = @ptrToInt([*]u8, data.ptr)[0..data.child.size];
        _ = allocator.shrinkFn(allocator, slice, data.child.alignment, 0, undefined);
    }

    /// Allocates a slice
    pub fn alloc(allocator: *Allocator, erased_type: ErasedType, count: usize) !ErasedSlice {
        const bytes = try allocator.reallocFn(allocator, &[0]u8{}, undefined, erased_type.size * count, erased_type.alignment);
        return .{
            .ptr = .{
                .ptr = @ptrToInt(bytes.ptr),
                .child = erased_type,
            },
            .len = count,
        };
    }
    
    /// Resizes a slice, allowing increasing size
    pub fn realloc(allocator: *Allocator, old_slice: ErasedSlice, new_count: usize) !ErasedSlice {
        const bytes = try allocator.reallocFn(
            allocator,
            old_slice.spanBytes(),
            old_slice.ptr.child.alignment,
            old_slice.ptr.child.size * new_count,
            old_slice.ptr.child.alignment,
        );
        return .{
            .ptr = .{
                .ptr = @ptrToInt(bytes.ptr),
                .child = old_slice.ptr.child,
            },
            .len = count,
        };
    }

    /// Resizes a slice to a smaller size
    pub fn shrink(allocator: *Allocator, old_slice: ErasedSlice, new_len: usize) ErasedSlice {
        assert(new_size <= old_slice.len);
        const bytes = allocator.shrinkFn(
            allocator,
            old_slice.spanBytes(),
            old_slice.ptr.child.alignment,
            old_slice.ptr.child.size * new_len,
            old_slice.ptr.child.alignment,
        );
        return .{
            .ptr = .{
                .ptr = @ptrToInt(bytes.ptr),
                .child = old_slice.ptr.child,
            },
            .len = count,
        };
    }
    
    /// Frees a slice allocated by `alloc`, `realloc`, or `shrink`.
    pub fn free(allocator: *Allocator, slice: ErasedSlice) void {
        _ = allocator.shrinkFn(allocator, slice.spanBytes(), slice.ptr.child.alignment, 0, undefined);
    }
};

erased_array_list.zig

const std = @import("std.zig");
const debug = std.debug;
const testing = std.testing;
const mem = std.mem;
const erase = @import("erase.zig");

const assert = debug.assert;

const Allocator = mem.Allocator;
const ErasedSlice = erase.ErasedSlice; 
const ErasedType = erase.ErasedType;

/// A contiguous, growable list of items in memory.
/// The type of the items is erased, but all items are the same type.
/// If you need a list of erased items which can be different types,
/// use `std.ArrayList(std.erase.ErasedPtr)` instead.
/// The exposed functions are meant for use in an entirely erased context.
/// If you know the comptime type within a scope, use `as(T)` to get a
/// typed view, which can be used more naturally in a typed context.
pub const ErasedArrayList = struct {
    const Self = @This();

    /// The valid items in the list.  Use `as(T)` to get a typed slice,
    /// or `.len` to get the number of valid items.  The allocation
    /// backing this slice is actually of size `capacity`.
    items: ErasedSlice,
    
    /// The size of the allocation backing the `items` slice.
    capacity: usize,
    
    /// The allocator used to allocate the data backing `items`.
    allocator: *Allocator,
    
    /// Deinitialize with `deinit` or use `toOwnedSlice`.
    pub fn init(comptime T: type, allocator: *Allocator) Self {
        return Self{
            .items = ErasedSlice.empty(T),
            .capacity = 0,
            .allocator = allocator,
        };
    }
    
    /// Deinitialize with `deinit` or use `toOwnedSlice`.
    pub fn initErased(child: ErasedType, allocator: *Allocator) Self {
        return Self{
            .items = ErasedSlice.emptyErased(child),
            .capacity = 0,
            .allocator = allocator,
        };
    }

    /// Initialize with capacity to hold at least num elements.
    /// Deinitialize with `deinit` or use `toOwnedSlice`.
    pub fn initCapacity(comptime T: type, allocator: *Allocator, num: usize) !Self {
        var self = Self.init(T, allocator);
        try self.ensureCapacity(num);
        return self;
    }

    /// Release all allocated memory.
    pub fn deinit(self: Self) void {
        erase.allocation.free(self.allocator, self.allocatedSlice());
    }
    
    /// Get a typed view of the array
    pub fn as(self: *Self, comptime T: type) TypedView(T) {
        return TypedView(T).init(self);
    }

    /// ArrayList takes ownership of the passed in slice. The slice must have been
    /// allocated with `allocator`.  Slice must be []T for some T.
    /// Deinitialize with `deinit` or use `toOwnedSlice`.
    pub fn fromOwnedSlice(allocator: *Allocator, slice: var) Self {
        return Self{
            .items = erase.ErasedSlice.init(slice),
            .capacity = slice.len,
            .allocator = allocator,
        };
    }

    /// The caller owns the returned memory. ArrayList becomes empty.
    pub fn toOwnedSlice(self: *Self) ErasedSlice {
        const allocator = self.allocator;
        const result = erase.allocation.shrink(self.allocator, self.allocatedSlice(), self.items.len);
        self.items = ErasedSlice.empty(self.items.ptr.child);
        return result;
    }

    /// Insert `item` at index `n`. Moves `list[n .. list.len]`
    /// to make room.  `item` can be a value of the backing type
    /// or an ErasedPtr or ErasedSizedPtr, or `undefined`.
    pub fn insert(self: *Self, n: usize, item: var) !void {
        try self.ensureCapacity(self.items.len + 1);
        self.items.len += 1;
        
        self.items.slice(n + 1, self.items.len).copyBackwards(self.items.slice(n, self.items.len - 1));
        self.items.at(n).set(item);
    }

    /// Insert slice `items` at index `i`. Moves
    /// `list[i .. list.len]` to make room.
    /// This operation is O(N).
    /// `items` can be a slice or an ErasedSlice.
    /// `items` must not alias the backing slice.
    pub fn insertSlice(self: *Self, i: usize, items: var) !void {
        try self.ensureCapacity(self.items.len + items.len);
        self.items.len += items.len;

        self.items.slice(i + items.len, self.items.len).copyBackwards(self.items.slice(i, self.items.len - items.len));

        const erased_slice = erase.ErasedSlice.init(items);
        self.items.child.assertSame(erased_slice.child);
        self.items.slice(i, i + items.len).copyNoalias(erased_slice);
    }

    /// Extend the list by 1 element. Allocates more memory as necessary.
    /// `item` can be an instance of the backing type or an `ErasedSizedPtr` or `ErasedPtr`, or `undefined`.
    pub fn append(self: *Self, item: var) !void {
        const new_item_ptr = try self.addOne();
        new_item_ptr.set(item);
    }

    /// Extend the list by 1 element, but asserting `self.capacity`
    /// is sufficient to hold an additional item.
    pub fn appendAssumeCapacity(self: *Self, item: var) void {
        const new_item_ptr = self.addOneAssumeCapacity();
        new_item_ptr.set(item);
    }

    /// Remove the element at index `i` from the list.
    /// Asserts the array has at least one item.
    /// This operation is O(N).
    pub fn orderedRemove(self: *Self, i: usize) void {
        const newlen = self.items.len - 1;
        if (newlen == i) return self.pop();

        self.items.slice(i, newlen).copyForwards(self.items.slice(i+1, self.items.len));
        self.items.at(newlen).set(undefined);
        self.items.len = newlen;
    }

    /// Removes the element at the specified index and returns it.
    /// The empty slot is filled from the end of the list.
    /// This operation is O(1).
    pub fn swapRemove(self: *Self, i: usize) void {
        const newlen = self.items.len - 1;
        if (newlen == i) return self.pop();

        self.items.at(i).set(self.items.at(newlen));
        self.items.at(newlen).set(undefined);
        self.items.len = newlen;
    }

    /// Append the slice of items to the list. Allocates more
    /// memory as necessary.  `items` can be a slice of the
    /// backing type or an `ErasedSlice`.
    pub fn appendSlice(self: *Self, items: var) !void {
        const oldlen = self.items.len;
        const newlen = self.items.len + items.len;

        try self.ensureCapacity(newlen);
        self.items.len = newlen;
        self.items.slice(oldlen, newlen).copyNoalias(ErasedSlice.init(items));
    }

    /// Append a value to the list `n` times.
    /// Allocates more memory as necessary.
    /// `value` can be an instance of the backing type,
    /// an `ErasedPtr` or `ErasedSizedPtr`, or `undefined`.
    pub fn appendNTimes(self: *Self, value: var, n: usize) !void {
        const old_len = self.items.len;
        try self.resize(self.items.len + n);
        self.items.slice(old_len, self.items.len).fill(value);
    }

    /// Adjust the list's length to `new_len`.
    /// Does not initialize added items if any.
    pub fn resize(self: *Self, new_len: usize) !void {
        try self.ensureCapacity(new_len);
        self.items.len = new_len;
    }

    /// Reduce allocated capacity to `new_len`.
    /// Invalidates element pointers.
    pub fn shrink(self: *Self, new_len: usize) void {
        assert(new_len <= self.items.len);

        self.items = erase.allocation.realloc(self.allocator, self.allocatedSlice(), new_len) catch |e| switch (e) {
            error.OutOfMemory => { // no problem, capacity is still correct then.
                self.items.len = new_len;
                return;
            },
        };
        self.capacity = new_len;
    }

    pub fn ensureCapacity(self: *Self, new_capacity: usize) !void {
        var better_capacity = self.capacity;
        if (better_capacity >= new_capacity) return;

        while (true) {
            better_capacity += better_capacity / 2 + 8;
            if (better_capacity >= new_capacity) break;
        }

        const new_memory = try erase.allocation.realloc(self.allocator, self.allocatedSlice(), better_capacity);
        self.items.ptr.ptr = new_memory.ptr.ptr;
        self.capacity = new_memory.len;
    }

    /// Increases the array's length to match the full capacity that is already allocated.
    /// The new elements have `undefined` values. This operation does not invalidate any
    /// element pointers.
    pub fn expandToCapacity(self: *Self) void {
        self.items.len = self.capacity;
    }

    /// Increase length by 1, returning pointer to the new item.
    /// The returned pointer becomes invalid when the list is resized.
    pub fn addOne(self: *Self) !ErasedSizedPtr {
        const newlen = self.items.len + 1;
        try self.ensureCapacity(newlen);
        return self.addOneAssumeCapacity();
    }

    /// Increase length by 1, returning pointer to the new item.
    /// Asserts that there is already space for the new item without allocating more.
    /// The returned pointer becomes invalid when the list is resized.
    pub fn addOneAssumeCapacity(self: *Self) ErasedSizedPtr {
        assert(self.items.len < self.capacity);

        self.items.len += 1;
        return self.items.at(self.items.len - 1);
    }

    /// Remove the last element from the list.
    /// Asserts the list has at least one item.
    pub fn pop(self: *Self) void {
        self.items.len -= 1;
    }

    /// Remove the last element from the list and returns true.
    /// If the list is empty, returns false.
    pub fn tryPop(self: *Self) bool {
        if (self.items.len == 0) return false;
        self.pop();
        return true;
    }

    // For a nicer API, `items.len` is the length, not the capacity.
    // This requires "unsafe" slicing.
    fn allocatedSlice(self: Self) ErasedSlice {
        return self.items.ptr.slice(0, self.capacity);
    }
    
    /// A typed view into an erased array.
    /// TypedViews are meant to be temporary in a scope, not stored.
    /// Create a TypedView from an ErasedArrayList by calling `list.as(T)`.
    pub fn TypedView(comptime T: type) type {
        return struct {
            const Slice = []T;
            const SliceConst = []const T;

            /// The backing list
            list: *ErasedArrayList,
            
            /// Creates a typed view over an existing array.
            /// The backing list must not be relocated while
            /// the view is active.
            pub fn init(list: *ErasedArrayList) @This() {
                list.items.ptr.child.assertIsSlice(Slice);
                return .{ .list = list };
            }
            
            /// Returns the items as a typed slice
            pub fn items(self: @This()) Slice {
                return self.list.items.asPtr(Slice);
            }

            /// Returns the current length of the array
            pub fn len(self: @This()) usize {
                return self.list.items.len;
            }

            /// Returns the items as a typed slice
            pub const span = items;

            /// The caller owns the returned memory. This list becomes empty.
            pub fn toOwnedSlice(self: @This()) Slice {
                return self.list.toOwnedSlice().asPtr(Slice);
            }

            /// Insert `item` at index `n`. Moves `list[n .. list.len]`
            /// to make room.
            pub fn insert(self: @This(), n: usize, item: T) !void {
                try self.list.insert(n, item);
            }

            /// Insert slice `items` at index `i`. Moves
            /// `list[i .. list.len]` to make room.
            /// This operation is O(N).
            pub fn insertSlice(self: @This(), i: usize, items: SliceConst) !void {
                try self.list.insertSlice(i, items);
            }

            /// Extend the list by 1 element. Allocates more memory as necessary.
            pub fn append(self: @This(), item: T) !void {
                try self.list.append(item);
            }

            /// Extend the list by 1 element, but asserting `self.capacity`
            /// is sufficient to hold an additional item.
            pub fn appendAssumeCapacity(self: @This(), item: T) void {
                self.list.appendAssumeCapacity(item);
            }

            /// Remove and return the element at index `i` from the list.
            /// Asserts the array has at least one item.
            /// This operation is O(N).
            pub fn orderedRemove(self: @This(), i: usize) T {
                const item = self.items()[i];
                self.list.orderedRemove(i);
                return item;
            }

            /// Removes the element at the specified index and returns it.
            /// The empty slot is filled from the end of the list.
            /// This operation is O(1).
            pub fn swapRemove(self: @This(), i: usize) T {
                const item = self.items()[i];
                self.list.swapRemove(i);
                return item;
            }

            /// Append the slice of items to the list. Allocates more
            /// memory as necessary.
            pub fn appendSlice(self: @This(), items: SliceConst) !void {
                try self.list.appendSlice(items);
            }

            /// Append a value to the list `n` times.
            /// Allocates more memory as necessary.
            pub fn appendNTimes(self: @This(), value: T, n: usize) !void {
                try self.list.appendNTimes(value, n);
            }

            /// Adjust the list's length to `new_len`.
            /// Does not initialize added items if any.
            pub fn resize(self: @This(), new_len: usize) !void {
                try self.list.resize(new_len);
            }

            /// Reduce allocated capacity to `new_len`.
            /// Invalidates element pointers.
            pub fn shrink(self: @This(), new_len: usize) void {
                self.list.shrink(new_len);
            }

            /// After calling this, the capacity of the array is guaranteed
            /// to be greater than or equal to the passed in capacity.
            pub fn ensureCapacity(self: @This(), new_capacity: usize) !void {
                try self.list.ensureCapacity(new_capacity);
            }

            /// Increases the array's length to match the full capacity that is already allocated.
            /// The new elements have `undefined` values. This operation does not invalidate any
            /// element pointers.
            pub fn expandToCapacity(self: @This()) void {
                self.list.expandToCapacity();
            }

            /// Increase length by 1, returning pointer to the new item.
            /// The returned pointer becomes invalid when the list is resized.
            pub fn addOne(self: @This()) !*T {
                return (try self.list.addOne()).as(T);
            }

            /// Increase length by 1, returning pointer to the new item.
            /// Asserts that there is already space for the new item without allocating more.
            /// The returned pointer becomes invalid when the list is resized.
            pub fn addOneAssumeCapacity(self: @This()) *T {
                return self.list.addOneAssumeCapacity().as(T);
            }

            /// Remove the last element from the list.
            /// Asserts the list has at least one item.
            pub fn pop(self: @This()) T {
                const newlen = self.list.items.len-1;
                const item = self.items()[newlen];
                self.list.items.len = newlen;
                return item;
            }

            /// Remove the last element from the list and returns true.
            /// If the list is empty, returns false.
            pub fn tryPop(self: @This()) ?T {
                if (self.list.items.len == 0) return null;
                return self.pop();
            }
        };
    }
};

test "std.ErasedArrayList.init" {
    var list = ErasedArrayList.init(u32, testing.allocator);
    defer list.deinit();

    testing.expect(list.items.len == 0);
    testing.expect(list.capacity == 0);
    list.items.ptr.child.assertSameType(u32);
}

test "std.ErasedArrayList.initCapacity" {
    var list = try ErasedArrayList.initCapacity(u8, testing.allocator, 200);
    defer list.deinit();

    testing.expect(list.items.len == 0);
    testing.expect(list.capacity >= 200);
    list.items.ptr.child.assertSameType(u8);
}

test "std.ErasedArrayList.initErased" {
    var list = try ErasedArrayList.initErased(ErasedType.init(u16), testing.allocator);
    defer list.deinit();

    testing.expect(list.items.len == 0);
    testing.expect(list.capacity == 0);
    list.items.ptr.child.assertSameType(u16);
}

test "std.ErasedArrayList.basic" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    {
        var i: usize = 0;
        while (i < 10) : (i += 1) {
            list.append(@intCast(i32, i + 1)) catch unreachable;
        }
    }

    {
        var i: usize = 0;
        while (i < 10) : (i += 1) {
            testing.expect(list.items.at(i).as(i32).* == @intCast(i32, i + 1));
            testing.expect(list.items.as(i32)[i] == @intCast(i32, i + 1));
        }
    }

    for (list.items.as(i32)) |v, i| {
        testing.expect(v == @intCast(i32, i + 1));
    }

    list.pop();
    testing.expect(list.items.len == 9);

    list.appendSlice(&[_]i32{ 1, 2, 3 }) catch unreachable;
    testing.expect(list.items.len == 12);
    testing.expect(list.items.as(i32)[10] == 1);
    testing.expect(list.items.as(i32)[11] == 2);
    testing.expect(list.items.as(i32)[12] == 3);
    list.pop();
    list.pop();
    list.pop();
    testing.expect(list.items.len == 9);

    list.appendSlice(&[_]i32{}) catch unreachable;
    testing.expect(list.items.len == 9);

    // can only set on indices < self.items.len
    list.items.at(7).set(33);
    list.items.at(8).set(42);

    testing.expect(list.items.at(list.items.len-1).as(i32).* == 42);
    list.pop();
    testing.expect(list.items.at(list.items.len-1).as(i32).* == 33);
    list.pop();
}

test "std.ErasedArrayList.appendNTimes" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    try list.appendNTimes(2, 10);
    testing.expectEqual(@as(usize, 10), list.items.len);
    for (list.items.as(i32)) |element| {
        testing.expectEqual(@as(i32, 2), element);
    }
}

test "std.ErasedArrayList.appendNTimes with failing allocator" {
    var list = ErasedArrayList.init(i32, testing.failing_allocator);
    defer list.deinit();
    testing.expectError(error.OutOfMemory, list.appendNTimes(2, 10));
}

test "std.ErasedArrayList.orderedRemove" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    try list.append(1);
    try list.append(2);
    try list.append(3);
    try list.append(4);
    try list.append(5);
    try list.append(6);
    try list.append(7);

    //remove from middle
    testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
    testing.expectEqual(@as(i32, 5), list.items[3]);
    testing.expectEqual(@as(usize, 6), list.items.len);

    //remove from end
    testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
    testing.expectEqual(@as(usize, 5), list.items.len);

    //remove from front
    testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
    testing.expectEqual(@as(i32, 2), list.items[0]);
    testing.expectEqual(@as(usize, 4), list.items.len);
}

test "std.ErasedArrayList.swapRemove" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    try list.append(1);
    try list.append(2);
    try list.append(3);
    try list.append(4);
    try list.append(5);
    try list.append(6);
    try list.append(7);

    //remove from middle
    testing.expect(list.swapRemove(3) == 4);
    testing.expect(list.items[3] == 7);
    testing.expect(list.items.len == 6);

    //remove from end
    testing.expect(list.swapRemove(5) == 6);
    testing.expect(list.items.len == 5);

    //remove from front
    testing.expect(list.swapRemove(0) == 1);
    testing.expect(list.items[0] == 5);
    testing.expect(list.items.len == 4);
}

test "std.ErasedArrayList.insert" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    try list.append(1);
    try list.append(2);
    try list.append(3);
    try list.insert(0, 5);
    testing.expect(list.items[0] == 5);
    testing.expect(list.items[1] == 1);
    testing.expect(list.items[2] == 2);
    testing.expect(list.items[3] == 3);
}

test "std.ErasedArrayList.insertSlice" {
    var list = ErasedArrayList.init(i32, testing.allocator);
    defer list.deinit();

    try list.append(1);
    try list.append(2);
    try list.append(3);
    try list.append(4);
    try list.insertSlice(1, &[_]i32{ 9, 8 });
    testing.expect(list.items[0] == 1);
    testing.expect(list.items[1] == 9);
    testing.expect(list.items[2] == 8);
    testing.expect(list.items[3] == 2);
    testing.expect(list.items[4] == 3);
    testing.expect(list.items[5] == 4);

    const items = [_]i32{1};
    try list.insertSlice(0, items[0..0]);
    testing.expect(list.items.len == 6);
    testing.expect(list.items[0] == 1);
}

const Item = struct {
    integer: i32,
    sub_items: ErasedArrayList,
};

test "std.ErasedArrayList: ErasedArrayList of struct T" {
    var root = Item{ .integer = 1, .sub_items = ErasedArrayList.init(Item, testing.allocator) };
    defer root.sub_items.deinit();
    try root.sub_items.append(Item{ .integer = 42, .sub_items = ErasedArrayList.init(Item, testing.allocator) });
    testing.expect(root.sub_items.items.as(Item)[0].integer == 42);
}

test "std.ErasedArrayList.shrink still sets length on error.OutOfMemory" {
    // use an arena allocator to make sure realloc returns error.OutOfMemory
    var arena = std.heap.ArenaAllocator.init(testing.allocator);
    defer arena.deinit();

    var list = ErasedArrayList.init(i32, &arena.allocator);

    try list.append(1);
    try list.append(1);
    try list.append(1);

    list.shrink(1);
    testing.expect(list.items.len == 1);
}