1 /**
2  * An std::vector-like type for deterministic lifetime.
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <ae@cy.md>
12  */
13 
14 module ae.utils.vec;
15 
16 import core.lifetime : move, moveEmplace, copyEmplace;
17 
18 import std.array;
19 import std.meta : allSatisfy;
20 
21 /*
22   An array type with deterministic lifetime.
23 
24   Properties:
25   - Owns its data
26   - Not implicitly copyable
27     - Use pointers / `ref` or `opSlice` to avoid copying
28     - Use `.dup` to copy explicitly
29     - Use `std.typecons.RefCounted` for reference counting
30   - If destroyed, will destroy (clobber) its contents
31   - O(1) indexing
32 
33   Differences from `std.containers.array.Array`:
34   - Memory-safe
35   - Like D arrays, has an initial null state (distinct from the empty state)
36   - No reference counting
37   - Uses the D GC heap
38   - Separates object lifetime from memory lifetime:
39     the latter is still managed by the GC,
40     so `Vec` is always memory-safe regardless of how you try to (mis-)use it
41 
42   Usage notes:
43   - If the type has a destructor, it must be valid to
44     call it on the `.init` value.
45   - `Vec` allows slicing and `ref` access to its members.
46     Due to this, stale pointers do not result in UB;
47     they will simply point to a default value (`.init`).
48 */
49 struct Vec(T)
50 {
51 	private enum elementsHaveDefaultValue = is(typeof({ T t; }));
52 	private enum elementsAreCopyable = is(typeof({ T t = void; T u = t; }));
53 
54 	// Lifetime
55 
56 	/// Construct from a list or slice of values
57 	static if (elementsAreCopyable)
58 	this(scope T[] values...)
59 	{
60 		data = values.dup;
61 	}
62 
63 	private enum bool isConstituent(C) = is(C == T) || is(C == T[]) || is(C == Vec!T);
64 
65 	/// Construct from any combination of values, slices of values, or
66 	/// other `Vec` instances
67 	this(Args...)(auto ref scope Args args)
68 	if (allSatisfy!(isConstituent, Args))
69 	{
70 		size_t length;
71 		foreach (ref arg; args)
72 			static if (is(typeof(arg) == T))
73 				length++;
74 			else
75 				length += arg.length;
76 		data = new T[length];
77 		size_t p = 0;
78 		foreach (ref arg; args)
79 			static if (is(typeof(arg) == T))
80 				data[p++] = arg;
81 			else
82 			{
83 				static if (is(typeof(arg) == Vec!T))
84 					data[p .. p + arg.length] = arg.data[];
85 				else
86 					data[p .. p + arg.length] = arg[];
87 				p += arg.length;
88 			}
89 	}
90 
91 	/// To avoid performance pitfalls, implicit copying is disabled.
92 	/// Use `.dup` instead.
93 	@disable this(this);
94 
95 	/// Create a shallow copy of this `Vec`.
96 	static if (elementsAreCopyable)
97 	Vec!T dup()
98 	{
99 		typeof(return) result;
100 		result.data = data.dup;
101 		return result;
102 	}
103 
104 	~this()
105 	{
106 		data[] = T.init;
107 		data = null;
108 	}
109 
110 	/// Array primitives
111 
112 	private void ensureCapacity(size_t newCapacity)
113 	out(; data.capacity >= newCapacity)
114 	{
115 		if (newCapacity > data.capacity)
116 		{
117 			T[] newData;
118 			newData.reserve(newCapacity);
119 			assert(newData.capacity >= newCapacity);
120 			newData = newData.ptr[0 .. data.length];
121 			newData.assumeSafeAppend();
122 			foreach (i; 0 .. data.length)
123 				moveEmplace(data[i], newData[i]);
124 			data = newData[0 .. data.length];
125 		}
126 	}
127 
128 	private T[] extendUninitialized(size_t howMany)
129 	out(result; result.length == howMany)
130 	{
131 		auto oldLength = data.length;
132 		auto newLength = oldLength + howMany;
133 		ensureCapacity(newLength);
134 		data = data.ptr[0 .. newLength];
135 		return data[oldLength .. newLength];
136 	}
137 
138 	@property size_t length() const { return data.length; }
139 	alias opDollar = length; /// ditto
140 
141 	static if (elementsHaveDefaultValue)
142 	@property size_t length(size_t newLength)
143 	{
144 		if (newLength < data.length)
145 		{
146 			data[newLength .. $] = T.init;
147 			data = data[0 .. newLength];
148 		}
149 		else
150 		if (newLength > data.length)
151 		{
152 			ensureCapacity(newLength);
153 			auto newData = data;
154 			newData.length = newLength;
155 			assert(newData.ptr == data.ptr);
156 			data = newData;
157 		}
158 		return data.length;
159 	} /// ditto
160 
161 	T opCast(T)() const if (is(T == bool))
162 	{
163 		return !!data;
164 	} /// ditto
165 
166 	ref inout(T) opIndex(size_t index) inout
167 	{
168 		return data[index];
169 	} /// ditto
170 
171 	typeof(null) opAssign(typeof(null)) { data[] = T.init; data = null; return null; } /// ditto
172 
173 	static if (elementsAreCopyable)
174 	ref Vec opOpAssign(string op : "~")(scope T[] values...)
175 	{
176 		foreach (i, ref target; extendUninitialized(values.length))
177 			copyEmplace(values[i], target);
178 		return this;
179 	} /// ditto
180 
181 	static if (!elementsAreCopyable)
182 	ref Vec opOpAssign(string op : "~")(T value)
183 	{
184 		moveEmplace(value, extendUninitialized(1)[0]);
185 		return this;
186 	} /// ditto
187 
188 	/// Range-like primitives
189 
190 	@property bool empty() const { return !data.length; }
191 
192 	ref inout(T) front() inout { return data[0]; } /// ditto
193 	ref inout(T) back() inout { return data[$-1]; } /// ditto
194 
195 	void popFront()
196 	{
197 		data[0] = T.init;
198 		data = data[1 .. $];
199 	} /// ditto
200 
201 	void popBack()
202 	{
203 		data[$-1] = T.init;
204 		data = data[0 .. $-1];
205 	} /// ditto
206 
207 	// Other operations
208 
209 	/// Return a slice of the held items.
210 	/// Ownership is unaffected, so this is a "view" into the contents.
211 	/// Can be used to perform range operations and iteration.
212 	inout(T)[] opSlice() inout
213 	{
214 		return data;
215 	}
216 
217 	/// Remove the element with the given `index`, shifting all
218 	/// elements after it to the left.
219 	void remove(size_t index)
220 	{
221 		foreach (i; index + 1 .. data.length)
222 			move(data[i], data[i - 1]);
223 		data = data[0 .. $ - 1];
224 	}
225 
226 private:
227 	T[] data;
228 }
229 
230 // Test object lifetime
231 unittest
232 {
233 	struct S
234 	{
235 		static int numLive;
236 		bool alive;
237 		this(bool) { alive = true; numLive++; }
238 		this(this) { if (alive) numLive++; }
239 		~this() { if (alive) numLive--; }
240 	}
241 
242 	Vec!S v;
243 	assert(S.numLive == 0);
244 	v = Vec!S(S(true));
245 	assert(S.numLive == 1);
246 	v ~= S(true);
247 	assert(S.numLive == 2);
248 	auto v2 = v.dup;
249 	assert(S.numLive == 4);
250 	v2 = null;
251 	assert(S.numLive == 2);
252 	v.popFront();
253 	assert(S.numLive == 1);
254 	v.popBack();
255 	assert(S.numLive == 0);
256 }
257 
258 // Test iteration
259 unittest
260 {
261 	// Ensure iterating twice over a Vec does not consume it.
262 	auto v = Vec!int(1, 2, 3);
263 	foreach (i; v) {}
264 	int sum;
265 	foreach (i; v) sum += i;
266 	assert(sum == 6);
267 }
268 
269 // Test non-copyable elements
270 unittest
271 {
272 	struct S
273 	{
274 		@disable this();
275 		@disable this(this);
276 		this(int) {}
277 	}
278 
279 	Vec!S v;
280 	v ~= S(1);
281 }