1 files changed, 114 insertions, 89 deletions

diff --git a/lib/std/array_list.zig b/lib/std/array_list.zig
index 523d1c810f..c6bb5bf3e7 100644
--- a/lib/std/array_list.zig
+++ b/lib/std/array_list.zig
@@ -20,11 +20,9 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
     return struct {
         const Self = @This();
 
-        /// Use `span` instead of slicing this directly, because if you don't
-        /// specify the end position of the slice, this will potentially give
-        /// you uninitialized memory.
+        /// Content of the ArrayList
         items: Slice,
-        len: usize,
+        capacity: usize,
         allocator: *Allocator,
 
         pub const Slice = if (alignment) |a| ([]align(a) T) else []T;
@@ -34,7 +32,7 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         pub fn init(allocator: *Allocator) Self {
             return Self{
                 .items = &[_]T{},
-                .len = 0,
+                .capacity = 0,
                 .allocator = allocator,
             };
         }
@@ -49,60 +47,55 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
 
         /// Release all allocated memory.
         pub fn deinit(self: Self) void {
-            self.allocator.free(self.items);
+            self.allocator.free(self.allocatedSlice());
         }
 
+        /// Deprecated: use `items` field directly.
         /// Return contents as a slice. Only valid while the list
         /// doesn't change size.
-        pub fn span(self: var) @TypeOf(self.items[0..self.len]) {
-            return self.items[0..self.len];
+        pub fn span(self: var) @TypeOf(self.items) {
+            return self.items;
         }
 
-        /// Deprecated: use `span`.
+        /// Deprecated: use `items` field directly.
         pub fn toSlice(self: Self) Slice {
-            return self.span();
+            return self.items;
         }
 
-        /// Deprecated: use `span`.
+        /// Deprecated: use `items` field directly.
         pub fn toSliceConst(self: Self) SliceConst {
-            return self.span();
+            return self.items;
         }
 
-        /// Deprecated: use `span()[i]`.
+        /// Deprecated: use `list.items[i]`.
         pub fn at(self: Self, i: usize) T {
-            return self.span()[i];
+            return self.items[i];
         }
 
-        /// Deprecated: use `&span()[i]`.
+        /// Deprecated: use `&list.items[i]`.
         pub fn ptrAt(self: Self, i: usize) *T {
-            return &self.span()[i];
+            return &self.items[i];
         }
 
-        /// Deprecated: use `if (i >= list.len) return error.OutOfBounds else span()[i] = item`.
+        /// Deprecated: use `if (i >= list.items.len) return error.OutOfBounds else list.items[i] = item`.
         pub fn setOrError(self: Self, i: usize, item: T) !void {
-            if (i >= self.len) return error.OutOfBounds;
+            if (i >= self.items.len) return error.OutOfBounds;
             self.items[i] = item;
         }
 
-        /// Deprecated: use `list.span()[i] = item`.
+        /// Deprecated: use `list.items[i] = item`.
         pub fn set(self: *Self, i: usize, item: T) void {
-            assert(i < self.len);
+            assert(i < self.items.len);
             self.items[i] = item;
         }
 
-        /// Return the maximum number of items the list can hold
-        /// without allocating more memory.
-        pub fn capacity(self: Self) usize {
-            return self.items.len;
-        }
-
         /// ArrayList takes ownership of the passed in slice. The slice must have been
         /// allocated with `allocator`.
         /// Deinitialize with `deinit` or use `toOwnedSlice`.
         pub fn fromOwnedSlice(allocator: *Allocator, slice: Slice) Self {
             return Self{
                 .items = slice,
-                .len = slice.len,
+                .capacity = slice.len,
                 .allocator = allocator,
             };
         }
@@ -110,7 +103,7 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// The caller owns the returned memory. ArrayList becomes empty.
         pub fn toOwnedSlice(self: *Self) Slice {
             const allocator = self.allocator;
-            const result = allocator.shrink(self.items, self.len);
+            const result = allocator.shrink(self.allocatedSlice(), self.items.len);
             self.* = init(allocator);
             return result;
         }
@@ -118,10 +111,10 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// Insert `item` at index `n`. Moves `list[n .. list.len]`
         /// to make room.
         pub fn insert(self: *Self, n: usize, item: T) !void {
-            try self.ensureCapacity(self.len + 1);
-            self.len += 1;
+            try self.ensureCapacity(self.items.len + 1);
+            self.items.len += 1;
 
-            mem.copyBackwards(T, self.items[n + 1 .. self.len], self.items[n .. self.len - 1]);
+            mem.copyBackwards(T, self.items[n + 1 .. self.items.len], self.items[n .. self.items.len - 1]);
             self.items[n] = item;
         }
 
@@ -129,10 +122,10 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// `list[i .. list.len]` to make room.
         /// This operation is O(N).
         pub fn insertSlice(self: *Self, i: usize, items: SliceConst) !void {
-            try self.ensureCapacity(self.len + items.len);
-            self.len += items.len;
+            try self.ensureCapacity(self.items.len + items.len);
+            self.items.len += items.len;
 
-            mem.copyBackwards(T, self.items[i + items.len .. self.len], self.items[i .. self.len - items.len]);
+            mem.copyBackwards(T, self.items[i + items.len .. self.items.len], self.items[i .. self.items.len - items.len]);
             mem.copy(T, self.items[i .. i + items.len], items);
         }
 
@@ -153,13 +146,13 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// Asserts the array has at least one item.
         /// This operation is O(N).
         pub fn orderedRemove(self: *Self, i: usize) T {
-            const newlen = self.len - 1;
+            const newlen = self.items.len - 1;
             if (newlen == i) return self.pop();
 
-            const old_item = self.at(i);
+            const old_item = self.items[i];
             for (self.items[i..newlen]) |*b, j| b.* = self.items[i + 1 + j];
             self.items[newlen] = undefined;
-            self.len = newlen;
+            self.items.len = newlen;
             return old_item;
         }
 
@@ -167,26 +160,28 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// The empty slot is filled from the end of the list.
         /// This operation is O(1).
         pub fn swapRemove(self: *Self, i: usize) T {
-            if (self.len - 1 == i) return self.pop();
+            if (self.items.len - 1 == i) return self.pop();
 
-            const slice = self.span();
-            const old_item = slice[i];
-            slice[i] = self.pop();
+            const old_item = self.items[i];
+            self.items[i] = self.pop();
             return old_item;
         }
 
-        /// Deprecated: use `if (i >= list.len) return error.OutOfBounds else list.swapRemove(i)`.
+        /// Deprecated: use `if (i >= list.items.len) return error.OutOfBounds else list.swapRemove(i)`.
         pub fn swapRemoveOrError(self: *Self, i: usize) !T {
-            if (i >= self.len) return error.OutOfBounds;
+            if (i >= self.items.len) return error.OutOfBounds;
             return self.swapRemove(i);
         }
 
         /// Append the slice of items to the list. Allocates more
         /// memory as necessary.
         pub fn appendSlice(self: *Self, items: SliceConst) !void {
-            try self.ensureCapacity(self.len + items.len);
-            mem.copy(T, self.items[self.len..], items);
-            self.len += items.len;
+            const oldlen = self.items.len;
+            const newlen = self.items.len + items.len;
+
+            try self.ensureCapacity(newlen);
+            self.items.len = newlen;
+            mem.copy(T, self.items[oldlen..], items);
         }
 
         /// Same as `append` except it returns the number of bytes written, which is always the same
@@ -206,50 +201,58 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// Append a value to the list `n` times.
         /// Allocates more memory as necessary.
         pub fn appendNTimes(self: *Self, value: T, n: usize) !void {
-            const old_len = self.len;
-            try self.resize(self.len + n);
-            mem.set(T, self.items[old_len..self.len], value);
+            const old_len = self.items.len;
+            try self.resize(self.items.len + n);
+            mem.set(T, self.items[old_len..self.items.len], 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.len = 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.len);
-            self.len = new_len;
-            self.items = self.allocator.realloc(self.items, new_len) catch |e| switch (e) {
-                error.OutOfMemory => return, // no problem, capacity is still correct then.
+            assert(new_len <= self.items.len);
+
+            self.items = self.allocator.realloc(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();
+            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;
             }
-            self.items = try self.allocator.realloc(self.items, better_capacity);
+            
+            const new_memory = try self.allocator.realloc(self.allocatedSlice(), better_capacity);
+            self.items.ptr = new_memory.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.len = self.items.len;
+            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) !*T {
-            const new_length = self.len + 1;
-            try self.ensureCapacity(new_length);
+            const newlen = self.items.len + 1;
+            try self.ensureCapacity(newlen);
             return self.addOneAssumeCapacity();
         }
 
@@ -257,25 +260,32 @@ pub fn AlignedArrayList(comptime T: type, comptime alignment: ?u29) type {
         /// 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) *T {
-            assert(self.len < self.capacity());
-            const result = &self.items[self.len];
-            self.len += 1;
-            return result;
+            assert(self.items.len < self.capacity);
+
+            self.items.len += 1;
+            return &self.items[self.items.len - 1];
         }
 
         /// Remove and return the last element from the list.
         /// Asserts the list has at least one item.
         pub fn pop(self: *Self) T {
-            self.len -= 1;
-            return self.items[self.len];
+            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`.
         pub fn popOrNull(self: *Self) ?T {
-            if (self.len == 0) return null;
+            if (self.items.len == 0) return null;
             return self.pop();
         }
+        
+        // For a nicer API, `items.len` is the length, not the capacity.
+        // This requires "unsafe" slicing.
+        fn allocatedSlice(self: Self) Slice {
+            return self.items.ptr[0..self.capacity];
+        }
     };
 }
 
@@ -283,15 +293,15 @@ test "std.ArrayList.init" {
     var list = ArrayList(i32).init(testing.allocator);
     defer list.deinit();
 
-    testing.expect(list.len == 0);
-    testing.expect(list.capacity() == 0);
+    testing.expect(list.items.len == 0);
+    testing.expect(list.capacity == 0);
 }
 
 test "std.ArrayList.initCapacity" {
     var list = try ArrayList(i8).initCapacity(testing.allocator, 200);
     defer list.deinit();
-    testing.expect(list.len == 0);
-    testing.expect(list.capacity() >= 200);
+    testing.expect(list.items.len == 0);
+    testing.expect(list.capacity >= 200);
 }
 
 test "std.ArrayList.basic" {
@@ -315,7 +325,7 @@ test "std.ArrayList.basic" {
         }
     }
 
-    for (list.span()) |v, i| {
+    for (list.items) |v, i| {
         testing.expect(v == @intCast(i32, i + 1));
     }
 
@@ -324,19 +334,19 @@ test "std.ArrayList.basic" {
     }
 
     testing.expect(list.pop() == 10);
-    testing.expect(list.len == 9);
+    testing.expect(list.items.len == 9);
 
     list.appendSlice(&[_]i32{ 1, 2, 3 }) catch unreachable;
-    testing.expect(list.len == 12);
+    testing.expect(list.items.len == 12);
     testing.expect(list.pop() == 3);
     testing.expect(list.pop() == 2);
     testing.expect(list.pop() == 1);
-    testing.expect(list.len == 9);
+    testing.expect(list.items.len == 9);
 
     list.appendSlice(&[_]i32{}) catch unreachable;
-    testing.expect(list.len == 9);
+    testing.expect(list.items.len == 9);
 
-    // can only set on indices < self.len
+    // can only set on indices < self.items.len
     list.set(7, 33);
     list.set(8, 42);
 
@@ -352,8 +362,8 @@ test "std.ArrayList.appendNTimes" {
     defer list.deinit();
 
     try list.appendNTimes(2, 10);
-    testing.expectEqual(@as(usize, 10), list.len);
-    for (list.span()) |element| {
+    testing.expectEqual(@as(usize, 10), list.items.len);
+    for (list.items) |element| {
         testing.expectEqual(@as(i32, 2), element);
     }
 }
@@ -378,17 +388,17 @@ test "std.ArrayList.orderedRemove" {
 
     //remove from middle
     testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
-    testing.expectEqual(@as(i32, 5), list.at(3));
-    testing.expectEqual(@as(usize, 6), list.len);
+    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.len);
+    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.at(0));
-    testing.expectEqual(@as(usize, 4), list.len);
+    testing.expectEqual(@as(i32, 2), list.items[0]);
+    testing.expectEqual(@as(usize, 4), list.items.len);
 }
 
 test "std.ArrayList.swapRemove" {
@@ -405,17 +415,17 @@ test "std.ArrayList.swapRemove" {
 
     //remove from middle
     testing.expect(list.swapRemove(3) == 4);
-    testing.expect(list.at(3) == 7);
-    testing.expect(list.len == 6);
+    testing.expect(list.items[3] == 7);
+    testing.expect(list.items.len == 6);
 
     //remove from end
     testing.expect(list.swapRemove(5) == 6);
-    testing.expect(list.len == 5);
+    testing.expect(list.items.len == 5);
 
     //remove from front
     testing.expect(list.swapRemove(0) == 1);
-    testing.expect(list.at(0) == 5);
-    testing.expect(list.len == 4);
+    testing.expect(list.items[0] == 5);
+    testing.expect(list.items.len == 4);
 }
 
 test "std.ArrayList.swapRemoveOrError" {
@@ -478,7 +488,7 @@ test "std.ArrayList.insertSlice" {
 
     const items = [_]i32{1};
     try list.insertSlice(0, items[0..0]);
-    testing.expect(list.len == 6);
+    testing.expect(list.items.len == 6);
     testing.expect(list.items[0] == 1);
 }
 
@@ -504,3 +514,18 @@ test "std.ArrayList(u8) implements outStream" {
 
     testing.expectEqualSlices(u8, "x: 42\ny: 1234\n", buffer.span());
 }
+
+test "std.ArrayList.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 = ArrayList(i32).init(&arena.allocator);
+
+        try list.append(1);
+        try list.append(2);
+        try list.append(3);
+
+        list.shrink(1);
+        testing.expect(list.items.len == 1);
+}