1 /**
2 	Defines a string based multi-map with conserved insertion order.
3 
4 	Copyright: © 2012-2014 RejectedSoftware e.K.
5 	License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file.
6 	Authors: Sönke Ludwig
7 */
8 module vibe.utils.dictionarylist;
9 
10 import vibe.utils.array : removeFromArrayIdx;
11 import vibe.utils.string : icmp2;
12 import std.exception : enforce;
13 
14 
15 /**
16 	Behaves similar to $(D VALUE[string]) but the insertion order is not changed
17 	and multiple values per key are supported.
18 
19 	This kind of map is used for MIME headers (e.g. for HTTP, see
20 	vibe.inet.message.InetHeaderMap), or for form data
21 	(vibe.inet.webform.FormFields). Note that the map can contain fields with
22 	the same key multiple times if addField is used for insertion. Insertion
23 	order is preserved.
24 
25 	Note that despite case not being relevant for matching keyse, iterating
26 	over the map will yield	the original case of the key that was put in.
27 
28 	Insertion and lookup has O(n) complexity.
29 */
30 struct DictionaryList(VALUE, bool case_sensitive = true, size_t NUM_STATIC_FIELDS = 32, bool USE_HASHSUM = false) {
31 	import std.typecons : Tuple;
32 
33 	private {
34 		alias KeyValue = Tuple!(string, "key", ValueType, "value");
35 
36 		static struct Field {
37 			static if (USE_HASHSUM) uint keyCheckSum;
38 			else {
39 				enum keyCheckSum = 0;
40 				this(uint, string key, VALUE value) { this.key = key; this.value = value; }
41 			}
42 			KeyValue tuple;
43 			@property ref inout(string) key() inout { return tuple.key; }
44 			@property ref inout(VALUE) value() inout { return tuple.value; }
45 		}
46 		Field[NUM_STATIC_FIELDS] m_fields;
47 		size_t m_fieldCount = 0;
48 		Field[] m_extendedFields;
49 
50 		enum bool safeValueCopy = __traits(compiles, (VALUE v) @safe { VALUE vc; vc = v; });
51 		template typedGet(T) {
52 			enum typedGet = __traits(compiles, (VALUE v) { return v.get!T; });
53 		}
54 		template canAssign(T) {
55 			enum canAssign = __traits(compiles, (T t) { VALUE v = t; });
56 		}
57 	}
58 
59 	alias ValueType = VALUE;
60 
61 	struct FieldTuple { string key; ValueType value; }
62 
63 	/** The number of fields present in the map.
64 	*/
65 	@property size_t length() const { return m_fieldCount + m_extendedFields.length; }
66 
67 	/// Supports serialization using vibe.data.serialization.
68 	static DictionaryList fromRepresentation(FieldTuple[] array)
69 	{
70 		DictionaryList ret;
71 		foreach (ref v; array) ret.addField(v.key, v.value);
72 		return ret;
73 	}
74 	/// ditto
75 	FieldTuple[] toRepresentation() {
76 		FieldTuple[] ret;
77 		foreach (k, ref v; this) ret ~= FieldTuple(k, v);
78 		return ret;
79 	}
80 
81 	/** Generates an associative-array equivalent string representation of the dictionary.
82 	*/
83 	void toString(scope void delegate(const(char)[] str) @safe sink)
84 	const {
85 		sink("[");
86 		bool first = true;
87 
88 		foreach (k, v; this.byKeyValue) {
89 			if (!first) sink(", ");
90 			else first = false;
91 			() @trusted {
92 				import std.format : formattedWrite;
93 				string[] ka = (&k)[0 .. 1];
94 				ValueType[] va = (&v)[0 .. 1];
95 				sink.formattedWrite("%(%s%): %(%s%)", ka, va);
96 			} ();
97 		}
98 		sink("]");
99 	}
100 	/// ditto
101 	void toString(scope void delegate(const(char)[] str) @system sink)
102 	const {
103 		toString(cast(void delegate(const(char)[]) @safe)sink);
104 	}
105 	/// ditto
106 	string toString()
107 	const {
108 		import std.array : appender;
109 		auto ret = appender!string();
110 		toString((s) { ret.put(s); });
111 		return ret.data;
112 	}
113 
114 	/** Removes the first field that matches the given key.
115 	*/
116 	void remove(string key)
117 	{
118 		static if (USE_HASHSUM) auto keysum = computeCheckSumI(key);
119 		enum keysum = 0;
120 		auto idx = getIndex(m_fields[0 .. m_fieldCount], key, keysum);
121 		if( idx >= 0 ){
122 			auto slice = m_fields[0 .. m_fieldCount];
123 			removeFromArrayIdx(slice, idx);
124 			m_fieldCount--;
125 		} else {
126 			idx = getIndex(m_extendedFields, key, keysum);
127 			enforce(idx >= 0);
128 			removeFromArrayIdx(m_extendedFields, idx);
129 		}
130 	}
131 
132 	/** Removes all fields that matches the given key.
133 	*/
134 	void removeAll(string key)
135 	{
136 		static if (USE_HASHSUM) auto keysum = computeCheckSumI(key);
137 		else enum keysum = 0;
138 		for (size_t i = 0; i < m_fieldCount;) {
139 			if (m_fields[i].keyCheckSum == keysum && matches(m_fields[i].key, key)) {
140 				auto slice = m_fields[0 .. m_fieldCount];
141 				removeFromArrayIdx(slice, i);
142 				m_fieldCount--;
143 			} else i++;
144 		}
145 
146 		for (size_t i = 0; i < m_extendedFields.length;) {
147 			if (m_fields[i].keyCheckSum == keysum && matches(m_fields[i].key, key))
148 				removeFromArrayIdx(m_extendedFields, i);
149 			else i++;
150 		}
151 	}
152 
153 	/** Adds a new field to the map.
154 
155 		The new field will be added regardless of any existing fields that
156 		have the same key, possibly resulting in duplicates. Use opIndexAssign
157 		if you want to avoid duplicates.
158 	*/
159 	void addField(string key, ValueType value)
160 	{
161 		static if (USE_HASHSUM) auto keysum = computeCheckSumI(key);
162 		else enum keysum = 0;
163 		if (m_fieldCount < m_fields.length)
164 			m_fields[m_fieldCount++] = Field(keysum, key, value);
165 		else m_extendedFields ~= Field(keysum, key, value);
166 	}
167 
168 	void addField(T)(string key, T value)
169 	if (canAssign!T)
170 	{
171 		ValueType convertedValue = value;
172 		addField(key, convertedValue);
173 	}
174 
175 	/** Returns the first field that matches the given key.
176 
177 		If no field is found, def_val is returned.
178 	*/
179 	inout(ValueType) get(string key, lazy inout(ValueType) def_val = ValueType.init)
180 	inout {
181 		if (auto pv = key in this) return *pv;
182 		return def_val;
183 	}
184 
185 	// DMD bug: cannot set T.init as default value for def_val parameter,
186 	// because compilation fails with message:
187 	//      Error: undefined identifier 'T'
188 	/// ditto
189 	inout(T) get(T)(string key, lazy inout(T) def_val)
190 	inout if (typedGet!T) {
191 		if (auto pv = key in this) return (*pv).get!T;
192 		return def_val;
193 	}
194 
195 	/// ditto
196 	inout(T) get(T)(string key) // Work around DMD bug
197 	inout if (typedGet!T) {
198 		return get!T(key, T.init);
199 	}
200 
201 	/** Returns all values matching the given key.
202 
203 		Note that the version returning an array will allocate for each call.
204 	*/
205 	const(ValueType)[] getAll(string key)
206 	const @trusted { // appender
207 		import std.array;
208 		auto ret = appender!(const(ValueType)[])();
209 		getAll(key, (v) @trusted { ret.put(v); });
210 		return ret.data;
211 	}
212 	/// ditto
213 	void getAll(string key, scope void delegate(const(ValueType)) @safe del)
214 	const {
215 		static if (USE_HASHSUM) uint keysum = computeCheckSumI(key);
216 		else enum keysum = 0;
217 		foreach (ref f; m_fields[0 .. m_fieldCount]) {
218 			static if (USE_HASHSUM)
219 				if (f.keyCheckSum != keysum) continue;
220 			if (matches(f.key, key)) del(f.value);
221 		}
222 		foreach (ref f; m_extendedFields) {
223 			static if (USE_HASHSUM)
224 				if (f.keyCheckSum != keysum) continue;
225 			if (matches(f.key, key)) del(f.value);
226 		}
227 	}
228 
229 	/** Returns the first value matching the given key.
230 	*/
231 	inout(ValueType) opIndex(string key)
232 	inout {
233 		auto pitm = key in this;
234 		enforce(pitm !is null, "Accessing non-existent key '"~key~"'.");
235 		return *pitm;
236 	}
237 
238 	/** Adds or replaces the given field with a new value.
239 	*/
240 	ValueType opIndexAssign(ValueType val, string key)
241 	{
242 		static if (USE_HASHSUM) auto keysum = computeCheckSumI(key);
243 		else enum keysum = 0;
244 		auto pitm = key in this;
245 		if (pitm) *pitm = val;
246 		else if (m_fieldCount < m_fields.length) m_fields[m_fieldCount++] = Field(keysum, key, val);
247 		else m_extendedFields ~= Field(keysum, key, val);
248 		return val;
249 	}
250 
251 	/// ditto
252 	ValueType opIndexAssign(T)(T val, string key)
253 	if (canAssign!T)
254 	{
255 		ValueType convertedVal = val;
256 		return opIndexAssign(convertedVal, key);
257 	}
258 
259 	/** Returns a pointer to the first field that matches the given key.
260 	*/
261 	inout(ValueType)* opBinaryRight(string op)(string key) inout if(op == "in")
262 	{
263 		static if (USE_HASHSUM) uint keysum = computeCheckSumI(key);
264 		else enum keysum = 0;
265 		auto idx = getIndex(m_fields[0 .. m_fieldCount], key, keysum);
266 		if (idx >= 0) return &m_fields[idx].tuple[1];
267 		idx = getIndex(m_extendedFields, key, keysum);
268 		if (idx >= 0) return &m_extendedFields[idx].tuple[1];
269 		return null;
270 	}
271 	/// ditto
272 	bool opBinaryRight(string op)(string key) inout if(op == "!in") {
273 		return !(key in this);
274 	}
275 
276 	/** Iterates over all fields, including duplicates.
277 	*/
278 	auto byKeyValue() {return Rng!false(&this, 0); }
279 	/// ditto
280 	auto byKeyValue() const { return Rng!true(&this, 0); }
281 	/// ditto
282 	auto byKey() inout { import std.algorithm.iteration : map; return byKeyValue().map!(p => p[0]); }
283 	/// ditto
284 	auto byValue() inout { import std.algorithm.iteration : map; return byKeyValue().map!(p => p[1]); }
285 
286 	/// Deprecated in favor of `.byKeyValue` - enables foreach iteration over a `DictionaryList` with two loop variables.
287 	deprecated("Iterate over .byKeyValue instead.")
288 	alias byKeyValue this;
289 
290 	static if (is(typeof({ const(ValueType) v; ValueType w; w = v; }))) {
291 		/** Duplicates the header map.
292 		*/
293 		@property DictionaryList dup()
294 		const {
295 			DictionaryList ret;
296 			ret.m_fields[0 .. m_fieldCount] = m_fields[0 .. m_fieldCount];
297 			ret.m_fieldCount = m_fieldCount;
298 			ret.m_extendedFields = m_extendedFields.dup;
299 			return ret;
300 		}
301 	}
302 
303 	private ptrdiff_t getIndex(in Field[] map, string key, uint keysum)
304 	const {
305 		foreach (i, ref const(Field) entry; map) {
306 			static if (USE_HASHSUM) if (entry.keyCheckSum != keysum) continue;
307 			if (matches(entry.key, key)) return i;
308 		}
309 		return -1;
310 	}
311 
312 	private static bool matches(string a, string b)
313 	{
314 		static if (case_sensitive) return a == b;
315 		else return a.length == b.length && icmp2(a, b) == 0;
316 	}
317 
318 	// very simple check sum function with a good chance to match
319 	// strings with different case equal
320 	static if (USE_HASHSUM) private static uint computeCheckSumI(string s)
321 	@trusted {
322 		uint csum = 0;
323 		immutable(char)* pc = s.ptr, pe = s.ptr + s.length;
324 		for (; pc != pe; pc++) {
325 			static if (case_sensitive) csum ^= *pc;
326 			else csum ^= *pc & 0x1101_1111;
327 			csum = (csum << 1) | (csum >> 31);
328 		}
329 		return csum;
330 	}
331 
332 	private static struct Rng(bool CONST) {
333 	@safe nothrow @nogc:
334 		static if (CONST) {
335 			alias KVT = const(KeyValue);
336 			const(DictionaryList)* list;
337 		} else {
338 			alias KVT = KeyValue;
339 			DictionaryList* list;
340 		}
341 		size_t idx;
342 
343 		@property bool empty() const { return idx >= list.length; }
344 		@property ref KVT front() {
345 			if (idx < list.m_fieldCount)
346 				return list.m_fields[idx].tuple;
347 			return list.m_extendedFields[idx - list.m_fieldCount].tuple;
348 		}
349 		void popFront() { idx++; }
350 	}
351 }
352 
353 static assert(DictionaryList!(string, true, 2).safeValueCopy);
354 
355 @safe unittest {
356 	DictionaryList!(int, true) a;
357 	a.addField("a", 1);
358 	a.addField("a", 2);
359 	assert(a["a"] == 1);
360 	assert(a.getAll("a") == [1, 2]);
361 	a["a"] = 3;
362 	assert(a["a"] == 3);
363 	assert(a.getAll("a") == [3, 2]);
364 	a.removeAll("a");
365 	assert(a.getAll("a").length == 0);
366 	assert(a.get("a", 4) == 4);
367 	a.addField("b", 2);
368 	a.addField("b", 1);
369 	a.remove("b");
370 	assert(a.getAll("b") == [1]);
371 
372 	DictionaryList!(int, false) b;
373 	b.addField("a", 1);
374 	b.addField("A", 2);
375 	assert(b["A"] == 1);
376 	assert(b.getAll("a") == [1, 2]);
377 }
378 
379 unittest {
380 	import std.variant : Variant;
381 	DictionaryList!(Variant) c;
382 	c["a"] = true;
383 	c["b"] = "Hello";
384 	assert(c.get("a").type == typeid(bool));
385 	assert(c.get!string("b") == "Hello");
386 	assert(c.get!int("c") == int.init);
387 	c.addField("d", 9);
388 	c.addField("d", "bar");
389 	assert(c.getAll("d") == [ cast(Variant) 9, cast(Variant) "bar" ]);
390 }
391 
392 @safe unittest {
393 	import std.conv : text;
394 	DictionaryList!int l;
395 	l["foo"] = 42;
396 	l["bar"] = 43;
397 	assert(text(l) == `["foo": 42, "bar": 43]`, text(l));
398 	assert(l.toString() == `["foo": 42, "bar": 43]`, l.toString());
399 }