Commit db1e97d4b1

@@ -12,10 +12,20 @@ const Allocator = mem.Allocator;
 
 /// A contiguous, growable list of items in memory.
 /// This is a wrapper around an array of T values. Initialize with `init`.
+///
+/// This struct internally stores a `std.mem.Allocator` for memory management.
+/// To manually specify an allocator with each method call see `ArrayListUnmanaged`.
 pub fn ArrayList(comptime T: type) type {
     return ArrayListAligned(T, null);
 }
 
+/// A contiguous, growable list of arbitrarily aligned items in memory.
+/// This is a wrapper around an array of T values aligned to `alignment`-byte
+/// addresses. If the specified alignment is `null`, then `@alignOf(T)` is used.
+/// Initialize with `init`.
+///
+/// This struct internally stores a `std.mem.Allocator` for memory management.
+/// To manually specify an allocator with each method call see `ArrayListAlignedUnmanaged`.
 pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
     if (alignment) |a| {
         if (a == @alignOf(T)) {
@@ -24,9 +34,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
     }
     return struct {
         const Self = @This();
-
-        /// Content of the ArrayList
+        /// Contents of the list. Pointers to elements in this slice are
+        /// **invalid after resizing operations** on the ArrayList, unless the
+        /// operation explicitly either: (1) states otherwise or (2) lists the
+        /// invalidated pointers.
+        ///
+        /// The allocator used determines how element pointers are
+        /// invalidated, so the behavior may vary between lists. To avoid
+        /// illegal behavior, take into account the above paragraph plus the
+        /// explicit statements given in each method.
         items: Slice,
+        /// How many T values this list can hold without allocating
+        /// additional memory.
         capacity: usize,
         allocator: *Allocator,
 
@@ -42,7 +61,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
             };
         }
 
-        /// Initialize with capacity to hold at least num elements.
+        /// Initialize with capacity to hold at least `num` elements.
         /// Deinitialize with `deinit` or use `toOwnedSlice`.
         pub fn initCapacity(allocator: *Allocator, num: usize) !Self {
             var self = Self.init(allocator);
@@ -79,11 +98,13 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
             };
         }
 
+        /// Initializes an ArrayListUnmanaged with the `items` and `capacity` fields
+        /// of this ArrayList. This ArrayList retains ownership of underlying memory.
         pub fn toUnmanaged(self: Self) ArrayListAlignedUnmanaged(T, alignment) {
             return .{ .items = self.items, .capacity = self.capacity };
         }
 
-        /// The caller owns the returned memory. ArrayList becomes empty.
+        /// The caller owns the returned memory. Empties this ArrayList.
         pub fn toOwnedSlice(self: *Self) Slice {
             const allocator = self.allocator;
             const result = allocator.shrink(self.allocatedSlice(), self.items.len);
@@ -91,7 +112,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
             return result;
         }
 
-        /// The caller owns the returned memory. ArrayList becomes empty.
+        /// The caller owns the returned memory. Empties this ArrayList.
         pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) ![:sentinel]T {
             try self.append(sentinel);
             const result = self.toOwnedSlice();
@@ -118,9 +139,10 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
             mem.copy(T, self.items[i .. i + items.len], items);
         }
 
-        /// Replace range of elements `list[start..start+len]` with `new_items`
-        /// grows list if `len < new_items.len`. may allocate
-        /// shrinks list if `len > new_items.len`
+        /// Replace range of elements `list[start..start+len]` with `new_items`.
+        /// Grows list if `len < new_items.len`.
+        /// Shrinks list if `len > new_items.len`.
+        /// Invalidates pointers if this ArrayList is resized.
         pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: SliceConst) !void {
             const after_range = start + len;
             const range = self.items[start..after_range];
@@ -151,15 +173,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
             new_item_ptr.* = item;
         }
 
-        /// Extend the list by 1 element, but asserting `self.capacity`
-        /// is sufficient to hold an additional item.
+        /// Extend the list by 1 element, but assert `self.capacity`
+        /// is sufficient to hold an additional item. **Does not**
+        /// invalidate pointers.
         pub fn appendAssumeCapacity(self: *Self, item: T) void {
             const new_item_ptr = self.addOneAssumeCapacity();
             new_item_ptr.* = item;
         }
 
-        /// Remove the element at index `i` from the list and return its value.
+        /// Remove the element at index `i`, shift elements after index
+        /// `i` forward, and return the removed element.
         /// Asserts the array has at least one item.
+        /// Invalidates pointers to end of list.
         /// This operation is O(N).
         pub fn orderedRemove(self: *Self, i: usize) T {
             const newlen = self.items.len - 1;
@@ -191,7 +216,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// Append the slice of items to the list, asserting the capacity is already
-        /// enough to store the new items.
+        /// enough to store the new items. **Does not** invalidate pointers.
         pub fn appendSliceAssumeCapacity(self: *Self, items: SliceConst) void {
             const oldlen = self.items.len;
             const newlen = self.items.len + items.len;
@@ -227,7 +252,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// Append a value to the list `n` times.
-        /// Asserts the capacity is enough.
+        /// Asserts the capacity is enough. **Does not** invalidate pointers.
         pub fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
             const new_len = self.items.len + n;
             assert(new_len <= self.capacity);
@@ -243,7 +268,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// Reduce allocated capacity to `new_len`.
-        /// Invalidates element pointers.
+        /// May invalidate element pointers.
         pub fn shrink(self: *Self, new_len: usize) void {
             assert(new_len <= self.items.len);
 
@@ -257,13 +282,14 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// Reduce length to `new_len`.
-        /// Invalidates element pointers.
-        /// Keeps capacity the same.
+        /// Invalidates pointers for the elements `items[new_len..]`.
         pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
             assert(new_len <= self.items.len);
             self.items.len = new_len;
         }
 
+        /// Modify the array so that it can hold at least `new_capacity` items.
+        /// Invalidates pointers if additional memory is needed.
         pub fn ensureCapacity(self: *Self, new_capacity: usize) !void {
             var better_capacity = self.capacity;
             if (better_capacity >= new_capacity) return;
@@ -280,14 +306,13 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// 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.
+        /// The new elements have `undefined` values. **Does not** invalidate 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.
+        /// The returned pointer becomes invalid when the list resized.
         pub fn addOne(self: *Self) !*T {
             const newlen = self.items.len + 1;
             try self.ensureCapacity(newlen);
@@ -297,6 +322,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         /// 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.
+        /// **Does not** invalidate element pointers.
         pub fn addOneAssumeCapacity(self: *Self) *T {
             assert(self.items.len < self.capacity);
 
@@ -306,6 +332,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
 
         /// Resize the array, adding `n` new elements, which have `undefined` values.
         /// The return value is an array pointing to the newly allocated elements.
+        /// The returned pointer becomes invalid when the list is resized.
+        /// Resizes list if `self.capacity` is not large enough.
         pub fn addManyAsArray(self: *Self, comptime n: usize) !*[n]T {
             const prev_len = self.items.len;
             try self.resize(self.items.len + n);
@@ -315,6 +343,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         /// Resize the array, adding `n` new elements, which have `undefined` values.
         /// The return value is an array pointing to the newly allocated elements.
         /// Asserts that there is already space for the new item without allocating more.
+        /// **Does not** invalidate element pointers.
+        /// The returned pointer becomes invalid when the list is resized.
         pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
             assert(self.items.len + n <= self.capacity);
             const prev_len = self.items.len;
@@ -324,21 +354,23 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
 
         /// Remove and return the last element from the list.
         /// Asserts the list has at least one item.
+        /// Invalidates pointers to the removed element.
         pub fn pop(self: *Self) T {
             const val = self.items[self.items.len - 1];
             self.items.len -= 1;
             return val;
         }
 
-        /// Remove and return the last element from the list.
-        /// If the list is empty, returns `null`.
+        /// Remove and return the last element from the list, or
+        /// return `null` if list is empty.
+        /// Invalidates pointers to the removed element, if any.
         pub fn popOrNull(self: *Self) ?T {
             if (self.items.len == 0) return null;
             return self.pop();
         }
 
         /// Returns a slice of all the items plus the extra capacity, whose memory
-        /// contents are undefined.
+        /// contents are `undefined`.
         pub fn allocatedSlice(self: Self) Slice {
             // For a nicer API, `items.len` is the length, not the capacity.
             // This requires "unsafe" slicing.
@@ -346,7 +378,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
         }
 
         /// Returns a slice of only the extra capacity after items.
-        /// This can be useful for writing directly into an `ArrayList`.
+        /// This can be useful for writing directly into an ArrayList.
         /// Note that such an operation must be followed up with a direct
         /// modification of `self.items.len`.
         pub fn unusedCapacitySlice(self: Self) Slice {
@@ -355,12 +387,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
     };
 }
 
-/// Bring-your-own allocator with every function call.
-/// Initialize directly and deinitialize with `deinit` or use `toOwnedSlice`.
+/// An ArrayList, but the allocator is passed as a parameter to the relevant functions
+/// rather than stored in the struct itself. The same allocator **must** be used throughout
+/// the entire lifetime of an ArrayListUnmanaged. Initialize directly or with
+/// `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`.
 pub fn ArrayListUnmanaged(comptime T: type) type {
     return ArrayListAlignedUnmanaged(T, null);
 }
 
+/// An ArrayListAligned, but the allocator is passed as a parameter to the relevant
+/// functions rather than stored  in the struct itself. The same allocator **must**
+/// be used throughout the entire lifetime of an ArrayListAlignedUnmanaged.
+/// Initialize directly or with `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`.
 pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) type {
     if (alignment) |a| {
         if (a == @alignOf(T)) {
@@ -369,9 +407,18 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
     }
     return struct {
         const Self = @This();
-
-        /// Content of the ArrayList.
+        /// Contents of the list. Pointers to elements in this slice are
+        /// **invalid after resizing operations** on the ArrayList, unless the
+        /// operation explicitly either: (1) states otherwise or (2) lists the
+        /// invalidated pointers.
+        ///
+        /// The allocator used determines how element pointers are
+        /// invalidated, so the behavior may vary between lists. To avoid
+        /// illegal behavior, take into account the above paragraph plus the
+        /// explicit statements given in each method.
         items: Slice = &[_]T{},
+        /// How many T values this list can hold without allocating
+        /// additional memory.
         capacity: usize = 0,
 
         pub const Slice = if (alignment) |a| ([]align(a) T) else []T;
@@ -395,6 +442,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
             self.* = undefined;
         }
 
+        /// Convert this list into an analogous memory-managed one.
+        /// The returned list has ownership of the underlying memory.
         pub fn toManaged(self: *Self, allocator: *Allocator) ArrayListAligned(T, alignment) {
             return .{ .items = self.items, .capacity = self.capacity, .allocator = allocator };
         }
@@ -414,7 +463,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Insert `item` at index `n`. Moves `list[n .. list.len]`
-        /// to make room.
+        /// to higher indices to make room.
+        /// This operation is O(N).
         pub fn insert(self: *Self, allocator: *Allocator, n: usize, item: T) !void {
             try self.ensureCapacity(allocator, self.items.len + 1);
             self.items.len += 1;
@@ -423,8 +473,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
             self.items[n] = item;
         }
 
-        /// Insert slice `items` at index `i`. Moves
-        /// `list[i .. list.len]` to make room.
+        /// Insert slice `items` at index `i`. Moves `list[i .. list.len]` to
+        /// higher indicices make room.
         /// This operation is O(N).
         pub fn insertSlice(self: *Self, allocator: *Allocator, i: usize, items: SliceConst) !void {
             try self.ensureCapacity(allocator, self.items.len + items.len);
@@ -435,8 +485,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Replace range of elements `list[start..start+len]` with `new_items`
-        /// grows list if `len < new_items.len`. may allocate
-        /// shrinks list if `len > new_items.len`
+        /// Grows list if `len < new_items.len`.
+        /// Shrinks list if `len > new_items.len`
+        /// Invalidates pointers if this ArrayList is resized.
         pub fn replaceRange(self: *Self, allocator: *Allocator, start: usize, len: usize, new_items: SliceConst) !void {
             var managed = self.toManaged(allocator);
             try managed.replaceRange(start, len, new_items);
@@ -457,7 +508,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Remove the element at index `i` from the list and return its value.
-        /// Asserts the array has at least one item.
+        /// Asserts the array has at least one item. Invalidates pointers to
+        /// last element.
         /// This operation is O(N).
         pub fn orderedRemove(self: *Self, i: usize) T {
             const newlen = self.items.len - 1;
@@ -472,6 +524,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// Removes the element at the specified index and returns it.
         /// The empty slot is filled from the end of the list.
+        /// Invalidates pointers to last element.
         /// This operation is O(1).
         pub fn swapRemove(self: *Self, i: usize) T {
             if (self.items.len - 1 == i) return self.pop();
@@ -515,6 +568,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Append a value to the list `n` times.
+        /// **Does not** invalidate pointers.
         /// Asserts the capacity is enough.
         pub fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
             const new_len = self.items.len + n;
@@ -524,14 +578,13 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Adjust the list's length to `new_len`.
-        /// Does not initialize added items if any.
+        /// Does not initialize added items, if any.
         pub fn resize(self: *Self, allocator: *Allocator, new_len: usize) !void {
             try self.ensureCapacity(allocator, new_len);
             self.items.len = new_len;
         }
 
         /// Reduce allocated capacity to `new_len`.
-        /// Invalidates element pointers.
         pub fn shrink(self: *Self, allocator: *Allocator, new_len: usize) void {
             assert(new_len <= self.items.len);
 
@@ -545,13 +598,15 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         }
 
         /// Reduce length to `new_len`.
-        /// Invalidates element pointers.
+        /// Invalidates pointers to elements `items[new_len..]`.
         /// Keeps capacity the same.
         pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
             assert(new_len <= self.items.len);
             self.items.len = new_len;
         }
 
+        /// Modify the array so that it can hold at least `new_capacity` items.
+        /// Invalidates pointers if additional memory is needed.
         pub fn ensureCapacity(self: *Self, allocator: *Allocator, new_capacity: usize) !void {
             var better_capacity = self.capacity;
             if (better_capacity >= new_capacity) return;
@@ -568,13 +623,13 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// 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.
+        /// **Does not** invalidate 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.
+        /// The returned pointer becomes invalid when the list resized.
         pub fn addOne(self: *Self, allocator: *Allocator) !*T {
             const newlen = self.items.len + 1;
             try self.ensureCapacity(allocator, newlen);
@@ -583,8 +638,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// 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.
-        /// This operation does not invalidate any element pointers.
+        /// **Does not** invalidate pointers.
+        /// The returned pointer becomes invalid when the list resized.
         pub fn addOneAssumeCapacity(self: *Self) *T {
             assert(self.items.len < self.capacity);
 
@@ -594,6 +649,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// Resize the array, adding `n` new elements, which have `undefined` values.
         /// The return value is an array pointing to the newly allocated elements.
+        /// The returned pointer becomes invalid when the list is resized.
         pub fn addManyAsArray(self: *Self, allocator: *Allocator, comptime n: usize) !*[n]T {
             const prev_len = self.items.len;
             try self.resize(allocator, self.items.len + n);
@@ -603,6 +659,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
         /// Resize the array, adding `n` new elements, which have `undefined` values.
         /// The return value is an array pointing to the newly allocated elements.
         /// Asserts that there is already space for the new item without allocating more.
+        /// **Does not** invalidate pointers.
+        /// The returned pointer becomes invalid when the list is resized.
         pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
             assert(self.items.len + n <= self.capacity);
             const prev_len = self.items.len;
@@ -612,7 +670,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// Remove and return the last element from the list.
         /// Asserts the list has at least one item.
-        /// This operation does not invalidate any element pointers.
+        /// Invalidates pointers to last element.
         pub fn pop(self: *Self) T {
             const val = self.items[self.items.len - 1];
             self.items.len -= 1;
@@ -621,7 +679,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
 
         /// Remove and return the last element from the list.
         /// If the list is empty, returns `null`.
-        /// This operation does not invalidate any element pointers.
+        /// Invalidates pointers to last element.
         pub fn popOrNull(self: *Self) ?T {
             if (self.items.len == 0) return null;
             return self.pop();