1 
2 //          Copyright Ferdinand Majerech 2011.
3 // Distributed under the Boost Software License, Version 1.0.
4 //    (See accompanying file LICENSE_1_0.txt or copy at
5 //          http://www.boost.org/LICENSE_1_0.txt)
6 
7 /**
8  * Class that processes YAML mappings, sequences and scalars into nodes. This can be
9  * used to add custom data types. A tutorial can be found
10  * $(LINK2 ../tutorials/custom_types.html, here).
11  */
12 module dyaml.constructor;
13 
14 
15 import std.array;
16 import std.algorithm;
17 import std.base64;
18 import std.container;
19 import std.conv;
20 import std.datetime;
21 import std.exception;
22 import std.stdio;
23 import std.regex;
24 import std..string;
25 import std.typecons;
26 import std.utf;
27 
28 import dyaml.node;
29 import dyaml.exception;
30 import dyaml.tag;
31 import dyaml.style;
32 
33 
34 // Exception thrown at constructor errors.
35 package class ConstructorException : YAMLException
36 {
37     /// Construct a ConstructorException.
38     ///
39     /// Params:  msg   = Error message.
40     ///          start = Start position of the error context.
41     ///          end   = End position of the error context.
42     this(string msg, Mark start, Mark end, string file = __FILE__, int line = __LINE__)
43         @safe pure nothrow
44     {
45         super(msg ~ "\nstart: " ~ start.toString() ~ "\nend: " ~ end.toString(),
46               file, line);
47     }
48 }
49 
50 private alias ConstructorException Error;
51 
52 /** Constructs YAML values.
53  *
54  * Each YAML scalar, sequence or mapping has a tag specifying its data type.
55  * Constructor uses user-specifyable functions to create a node of desired
56  * data type from a scalar, sequence or mapping.
57  *
58  *
59  * Each of these functions is associated with a tag, and can process either
60  * a scalar, a sequence, or a mapping. The constructor passes each value to
61  * the function with corresponding tag, which then returns the resulting value
62  * that can be stored in a node.
63  *
64  * If a tag is detected with no known constructor function, it is considered an error.
65  */
66 final class Constructor
67 {
68     private:
69         // Constructor functions from scalars.
70         Node.Value delegate(ref Node)[Tag] fromScalar_;
71         // Constructor functions from sequences.
72         Node.Value delegate(ref Node)[Tag] fromSequence_;
73         // Constructor functions from mappings.
74         Node.Value delegate(ref Node)[Tag] fromMapping_;
75 
76     public:
77         /// Construct a Constructor.
78         ///
79         /// If you don't want to support default YAML tags/data types, you can use
80         /// defaultConstructors to disable constructor functions for these.
81         ///
82         /// Params:  defaultConstructors = Use constructors for default YAML tags?
83         this(const Flag!"useDefaultConstructors" defaultConstructors = Yes.useDefaultConstructors)
84             @safe nothrow
85         {
86             if(!defaultConstructors){return;}
87 
88             addConstructorScalar("tag:yaml.org,2002:null",      &constructNull);
89             addConstructorScalar("tag:yaml.org,2002:bool",      &constructBool);
90             addConstructorScalar("tag:yaml.org,2002:int",       &constructLong);
91             addConstructorScalar("tag:yaml.org,2002:float",     &constructReal);
92             addConstructorScalar("tag:yaml.org,2002:binary",    &constructBinary);
93             addConstructorScalar("tag:yaml.org,2002:timestamp", &constructTimestamp);
94             addConstructorScalar("tag:yaml.org,2002:str",       &constructString);
95 
96             ///In a mapping, the default value is kept as an entry with the '=' key.
97             addConstructorScalar("tag:yaml.org,2002:value",     &constructString);
98 
99             addConstructorSequence("tag:yaml.org,2002:omap",    &constructOrderedMap);
100             addConstructorSequence("tag:yaml.org,2002:pairs",   &constructPairs);
101             addConstructorMapping("tag:yaml.org,2002:set",      &constructSet);
102             addConstructorSequence("tag:yaml.org,2002:seq",     &constructSequence);
103             addConstructorMapping("tag:yaml.org,2002:map",      &constructMap);
104             addConstructorScalar("tag:yaml.org,2002:merge",     &constructMerge);
105         }
106 
107         /// Destroy the constructor.
108         @nogc pure @safe nothrow ~this()
109         {
110             fromScalar_.destroy();
111             fromScalar_ = null;
112             fromSequence_.destroy();
113             fromSequence_ = null;
114             fromMapping_.destroy();
115             fromMapping_ = null;
116         }
117 
118         /** Add a constructor function from scalar.
119          *
120          * The function must take a reference to $(D Node) to construct from.
121          * The node contains a string for scalars, $(D Node[]) for sequences and
122          * $(D Node.Pair[]) for mappings.
123          *
124          * Any exception thrown by this function will be caught by D:YAML and
125          * its message will be added to a $(D YAMLException) that will also tell
126          * the user which type failed to construct, and position in the file.
127          *
128          *
129          * The value returned by this function will be stored in the resulting node.
130          *
131          * Only one constructor function can be set for one tag.
132          *
133          *
134          * Structs and classes must implement the $(D opCmp()) operator for D:YAML
135          * support. The signature of the operator that must be implemented
136          * is $(D const int opCmp(ref const MyStruct s)) for structs where
137          * $(I MyStruct) is the struct type, and $(D int opCmp(Object o)) for
138          * classes. Note that the class $(D opCmp()) should not alter the compared
139          * values - it is not const for compatibility reasons.
140          *
141          * Params:  tag  = Tag for the function to handle.
142          *          ctor = Constructor function.
143          *
144          * Example:
145          *
146          * --------------------
147          * import std.string;
148          *
149          * import dyaml.all;
150          *
151          * struct MyStruct
152          * {
153          *     int x, y, z;
154          *
155          *     //Any D:YAML type must have a custom opCmp operator.
156          *     //This is used for ordering in mappings.
157          *     const int opCmp(ref const MyStruct s)
158          *     {
159          *         if(x != s.x){return x - s.x;}
160          *         if(y != s.y){return y - s.y;}
161          *         if(z != s.z){return z - s.z;}
162          *         return 0;
163          *     }
164          * }
165          *
166          * MyStruct constructMyStructScalar(ref Node node)
167          * {
168          *     //Guaranteed to be string as we construct from scalar.
169          *     //!mystruct x:y:z
170          *     auto parts = node.as!string().split(":");
171          *     // If this throws, the D:YAML will handle it and throw a YAMLException.
172          *     return MyStruct(to!int(parts[0]), to!int(parts[1]), to!int(parts[2]));
173          * }
174          *
175          * void main()
176          * {
177          *     auto loader = Loader("file.yaml");
178          *     auto constructor = new Constructor;
179          *     constructor.addConstructorScalar("!mystruct", &constructMyStructScalar);
180          *     loader.constructor = constructor;
181          *     Node node = loader.load();
182          * }
183          * --------------------
184          */
185         void addConstructorScalar(T)(const string tag, T function(ref Node) ctor)
186             @safe nothrow
187         {
188             const t = Tag(tag);
189             auto deleg = addConstructor!T(t, ctor);
190             (*delegates!string)[t] = deleg;
191         }
192 
193         /** Add a constructor function from sequence.
194          *
195          * See_Also:    addConstructorScalar
196          *
197          * Example:
198          *
199          * --------------------
200          * import std.string;
201          *
202          * import dyaml.all;
203          *
204          * struct MyStruct
205          * {
206          *     int x, y, z;
207          *
208          *     //Any D:YAML type must have a custom opCmp operator.
209          *     //This is used for ordering in mappings.
210          *     const int opCmp(ref const MyStruct s)
211          *     {
212          *         if(x != s.x){return x - s.x;}
213          *         if(y != s.y){return y - s.y;}
214          *         if(z != s.z){return z - s.z;}
215          *         return 0;
216          *     }
217          * }
218          *
219          * MyStruct constructMyStructSequence(ref Node node)
220          * {
221          *     //node is guaranteed to be sequence.
222          *     //!mystruct [x, y, z]
223          *     return MyStruct(node[0].as!int, node[1].as!int, node[2].as!int);
224          * }
225          *
226          * void main()
227          * {
228          *     auto loader = Loader("file.yaml");
229          *     auto constructor = new Constructor;
230          *     constructor.addConstructorSequence("!mystruct", &constructMyStructSequence);
231          *     loader.constructor = constructor;
232          *     Node node = loader.load();
233          * }
234          * --------------------
235          */
236         void addConstructorSequence(T)(const string tag, T function(ref Node) ctor)
237             @safe nothrow
238         {
239             const t = Tag(tag);
240             auto deleg = addConstructor!T(t, ctor);
241             (*delegates!(Node[]))[t] = deleg;
242         }
243 
244         /** Add a constructor function from a mapping.
245          *
246          * See_Also:    addConstructorScalar
247          *
248          * Example:
249          *
250          * --------------------
251          * import std.string;
252          *
253          * import dyaml.all;
254          *
255          * struct MyStruct
256          * {
257          *     int x, y, z;
258          *
259          *     //Any D:YAML type must have a custom opCmp operator.
260          *     //This is used for ordering in mappings.
261          *     const int opCmp(ref const MyStruct s)
262          *     {
263          *         if(x != s.x){return x - s.x;}
264          *         if(y != s.y){return y - s.y;}
265          *         if(z != s.z){return z - s.z;}
266          *         return 0;
267          *     }
268          * }
269          *
270          * MyStruct constructMyStructMapping(ref Node node)
271          * {
272          *     //node is guaranteed to be mapping.
273          *     //!mystruct {"x": x, "y": y, "z": z}
274          *     return MyStruct(node["x"].as!int, node["y"].as!int, node["z"].as!int);
275          * }
276          *
277          * void main()
278          * {
279          *     auto loader = Loader("file.yaml");
280          *     auto constructor = new Constructor;
281          *     constructor.addConstructorMapping("!mystruct", &constructMyStructMapping);
282          *     loader.constructor = constructor;
283          *     Node node = loader.load();
284          * }
285          * --------------------
286          */
287         void addConstructorMapping(T)(const string tag, T function(ref Node) ctor)
288             @safe nothrow
289         {
290             const t = Tag(tag);
291             auto deleg = addConstructor!T(t, ctor);
292             (*delegates!(Node.Pair[]))[t] = deleg;
293         }
294 
295     package:
296         /*
297          * Construct a node.
298          *
299          * Params:  start = Start position of the node.
300          *          end   = End position of the node.
301          *          tag   = Tag (data type) of the node.
302          *          value = Value to construct node from (string, nodes or pairs).
303          *          style = Style of the node (scalar or collection style).
304          *
305          * Returns: Constructed node.
306          */
307         Node node(T, U)(const Mark start, const Mark end, const Tag tag,
308                         T value, U style) @trusted
309             if((is(T : string) || is(T == Node[]) || is(T == Node.Pair[])) &&
310                (is(U : CollectionStyle) || is(U : ScalarStyle)))
311         {
312             enum type = is(T : string)       ? "scalar"   :
313                         is(T == Node[])      ? "sequence" :
314                         is(T == Node.Pair[]) ? "mapping"  :
315                                                "ERROR";
316             enforce((tag in *delegates!T) !is null,
317                     new Error("No constructor function from " ~ type ~
318                               " for tag " ~ tag.get(), start, end));
319 
320             Node node = Node(value);
321             try
322             {
323                 static if(is(U : ScalarStyle))
324                 {
325                     return Node.rawNode((*delegates!T)[tag](node), start, tag,
326                                         style, CollectionStyle.Invalid);
327                 }
328                 else static if(is(U : CollectionStyle))
329                 {
330                     return Node.rawNode((*delegates!T)[tag](node), start, tag,
331                                         ScalarStyle.Invalid, style);
332                 }
333                 else static assert(false);
334             }
335             catch(Exception e)
336             {
337                 throw new Error("Error constructing " ~ typeid(T).toString()
338                                 ~ ":\n" ~ e.msg, start, end);
339             }
340         }
341 
342     private:
343         /*
344          * Add a constructor function.
345          *
346          * Params:  tag  = Tag for the function to handle.
347          *          ctor = Constructor function.
348          */
349         auto addConstructor(T)(const Tag tag, T function(ref Node) ctor)
350             @safe nothrow
351         {
352             assert((tag in fromScalar_) is null &&
353                    (tag in fromSequence_) is null &&
354                    (tag in fromMapping_) is null,
355                    "Constructor function for tag " ~ tag.get ~ " is already "
356                    "specified. Can't specify another one.");
357 
358 
359             return (ref Node n)
360             {
361                 static if(Node.allowed!T){return Node.value(ctor(n));}
362                 else                     {return Node.userValue(ctor(n));}
363             };
364         }
365 
366         //Get the array of constructor functions for scalar, sequence or mapping.
367         @property auto delegates(T)() @safe pure nothrow @nogc
368         {
369             static if(is(T : string))          {return &fromScalar_;}
370             else static if(is(T : Node[]))     {return &fromSequence_;}
371             else static if(is(T : Node.Pair[])){return &fromMapping_;}
372             else static assert(false);
373         }
374 }
375 
376 
377 /// Construct a _null _node.
378 YAMLNull constructNull(ref Node node) @safe pure nothrow @nogc 
379 {
380     return YAMLNull();
381 }
382 
383 /// Construct a merge _node - a _node that merges another _node into a mapping.
384 YAMLMerge constructMerge(ref Node node) @safe pure nothrow @nogc 
385 {
386     return YAMLMerge();
387 }
388 
389 /// Construct a boolean _node.
390 bool constructBool(ref Node node) @safe
391 {
392     static yes = ["yes", "true", "on"];
393     static no = ["no", "false", "off"];
394     string value = node.as!string().toLower();
395     if(yes.canFind(value)){return true;}
396     if(no.canFind(value)) {return false;}
397     throw new Exception("Unable to parse boolean value: " ~ value);
398 }
399 
400 /// Construct an integer (long) _node.
401 long constructLong(ref Node node)
402 {
403     string value = node.as!string().replace("_", "");
404     const char c = value[0];
405     const long sign = c != '-' ? 1 : -1;
406     if(c == '-' || c == '+')
407     {
408         value = value[1 .. $];
409     }
410 
411     enforce(value != "", new Exception("Unable to parse float value: " ~ value));
412 
413     long result;
414     try
415     {
416         //Zero.
417         if(value == "0")               {result = cast(long)0;}
418         //Binary.
419         else if(value.startsWith("0b")){result = sign * to!int(value[2 .. $], 2);}
420         //Hexadecimal.
421         else if(value.startsWith("0x")){result = sign * to!int(value[2 .. $], 16);}
422         //Octal.
423         else if(value[0] == '0')       {result = sign * to!int(value, 8);}
424         //Sexagesimal.
425         else if(value.canFind(":"))
426         {
427             long val = 0;
428             long base = 1;
429             foreach_reverse(digit; value.split(":"))
430             {
431                 val += to!long(digit) * base;
432                 base *= 60;
433             }
434             result = sign * val;
435         }
436         //Decimal.
437         else{result = sign * to!long(value);}
438     }
439     catch(ConvException e)
440     {
441         throw new Exception("Unable to parse integer value: " ~ value);
442     }
443 
444     return result;
445 }
446 unittest
447 {
448     long getLong(string str)
449     {
450         auto node = Node(str);
451         return constructLong(node);
452     }
453 
454     string canonical   = "685230";
455     string decimal     = "+685_230";
456     string octal       = "02472256";
457     string hexadecimal = "0x_0A_74_AE";
458     string binary      = "0b1010_0111_0100_1010_1110";
459     string sexagesimal = "190:20:30";
460 
461     assert(685230 == getLong(canonical));
462     assert(685230 == getLong(decimal));
463     assert(685230 == getLong(octal));
464     assert(685230 == getLong(hexadecimal));
465     assert(685230 == getLong(binary));
466     assert(685230 == getLong(sexagesimal));
467 }
468 
469 /// Construct a floating point (real) _node.
470 real constructReal(ref Node node)
471 {
472     string value = node.as!string().replace("_", "").toLower();
473     const char c = value[0];
474     const real sign = c != '-' ? 1.0 : -1.0;
475     if(c == '-' || c == '+')
476     {
477         value = value[1 .. $];
478     }
479 
480     enforce(value != "" && value != "nan" && value != "inf" && value != "-inf",
481             new Exception("Unable to parse float value: " ~ value));
482 
483     real result;
484     try
485     {
486         //Infinity.
487         if     (value == ".inf"){result = sign * real.infinity;}
488         //Not a Number.
489         else if(value == ".nan"){result = real.nan;}
490         //Sexagesimal.
491         else if(value.canFind(":"))
492         {
493             real val = 0.0;
494             real base = 1.0;
495             foreach_reverse(digit; value.split(":"))
496             {
497                 val += to!real(digit) * base;
498                 base *= 60.0;
499             }
500             result = sign * val;
501         }
502         //Plain floating point.
503         else{result = sign * to!real(value);}
504     }
505     catch(ConvException e)
506     {
507         throw new Exception("Unable to parse float value: \"" ~ value ~ "\"");
508     }
509 
510     return result;
511 }
512 unittest
513 {
514     bool eq(real a, real b, real epsilon = 0.2)
515     {
516         return a >= (b - epsilon) && a <= (b + epsilon);
517     }
518 
519     real getReal(string str)
520     {
521         auto node = Node(str);
522         return constructReal(node);
523     }
524 
525     string canonical   = "6.8523015e+5";
526     string exponential = "685.230_15e+03";
527     string fixed       = "685_230.15";
528     string sexagesimal = "190:20:30.15";
529     string negativeInf = "-.inf";
530     string NaN         = ".NaN";
531 
532     assert(eq(685230.15, getReal(canonical)));
533     assert(eq(685230.15, getReal(exponential)));
534     assert(eq(685230.15, getReal(fixed)));
535     assert(eq(685230.15, getReal(sexagesimal)));
536     assert(eq(-real.infinity, getReal(negativeInf)));
537     assert(to!string(getReal(NaN)) == "nan");
538 }
539 
540 /// Construct a binary (base64) _node.
541 ubyte[] constructBinary(ref Node node)
542 {
543     string value = node.as!string;
544     // For an unknown reason, this must be nested to work (compiler bug?).
545     try
546     {
547         try{return Base64.decode(value.removechars("\n"));}
548         catch(Exception e)
549         {
550             throw new Exception("Unable to decode base64 value: " ~ e.msg);
551         }
552     }
553     catch(UTFException e)
554     {
555         throw new Exception("Unable to decode base64 value: " ~ e.msg);
556     }
557 }
558 unittest
559 {
560     ubyte[] test = cast(ubyte[])"The Answer: 42";
561     char[] buffer;
562     buffer.length = 256;
563     string input = cast(string)Base64.encode(test, buffer);
564     auto node = Node(input);
565     auto value = constructBinary(node);
566     assert(value == test);
567 }
568 
569 /// Construct a timestamp (SysTime) _node.
570 SysTime constructTimestamp(ref Node node)
571 {
572     string value = node.as!string;
573 
574     auto YMDRegexp = regex("^([0-9][0-9][0-9][0-9])-([0-9][0-9]?)-([0-9][0-9]?)");
575     auto HMSRegexp = regex("^[Tt \t]+([0-9][0-9]?):([0-9][0-9]):([0-9][0-9])(\\.[0-9]*)?");
576     auto TZRegexp  = regex("^[ \t]*Z|([-+][0-9][0-9]?)(:[0-9][0-9])?");
577 
578     try
579     {
580         // First, get year, month and day.
581         auto matches = match(value, YMDRegexp);
582 
583         enforce(!matches.empty,
584                 new Exception("Unable to parse timestamp value: " ~ value));
585 
586         auto captures = matches.front.captures;
587         const year  = to!int(captures[1]);
588         const month = to!int(captures[2]);
589         const day   = to!int(captures[3]);
590 
591         // If available, get hour, minute, second and fraction, if present.
592         value = matches.front.post;
593         matches  = match(value, HMSRegexp);
594         if(matches.empty)
595         {
596             return SysTime(DateTime(year, month, day), UTC());
597         }
598 
599         captures = matches.front.captures;
600         const hour            = to!int(captures[1]);
601         const minute          = to!int(captures[2]);
602         const second          = to!int(captures[3]);
603         const hectonanosecond = cast(int)(to!real("0" ~ captures[4]) * 10000000);
604 
605         // If available, get timezone.
606         value = matches.front.post;
607         matches = match(value, TZRegexp);
608         if(matches.empty || matches.front.captures[0] == "Z")
609         {
610             // No timezone.
611             return SysTime(DateTime(year, month, day, hour, minute, second),
612                            hectonanosecond.dur!"hnsecs", UTC());
613         }
614 
615         // We have a timezone, so parse it.
616         captures = matches.front.captures;
617         int sign    = 1;
618         int tzHours = 0;
619         if(!captures[1].empty)
620         {
621             if(captures[1][0] == '-') {sign = -1;}
622             tzHours   = to!int(captures[1][1 .. $]);
623         }
624         const tzMinutes = (!captures[2].empty) ? to!int(captures[2][1 .. $]) : 0;
625         const tzOffset  = dur!"minutes"(sign * (60 * tzHours + tzMinutes));
626 
627         return SysTime(DateTime(year, month, day, hour, minute, second),
628                        hectonanosecond.dur!"hnsecs",
629                        new immutable SimpleTimeZone(tzOffset));
630     }
631     catch(ConvException e)
632     {
633         throw new Exception("Unable to parse timestamp value " ~ value ~ " : " ~ e.msg);
634     }
635     catch(DateTimeException e)
636     {
637         throw new Exception("Invalid timestamp value " ~ value ~ " : " ~ e.msg);
638     }
639 
640     assert(false, "This code should never be reached");
641 }
642 unittest
643 {
644     writeln("D:YAML construction timestamp unittest");
645 
646     string timestamp(string value)
647     {
648         auto node = Node(value);
649         return constructTimestamp(node).toISOString();
650     }
651 
652     string canonical      = "2001-12-15T02:59:43.1Z";
653     string iso8601        = "2001-12-14t21:59:43.10-05:00";
654     string spaceSeparated = "2001-12-14 21:59:43.10 -5";
655     string noTZ           = "2001-12-15 2:59:43.10";
656     string noFraction     = "2001-12-15 2:59:43";
657     string ymd            = "2002-12-14";
658 
659     assert(timestamp(canonical)      == "20011215T025943.1Z");
660     //avoiding float conversion errors
661     assert(timestamp(iso8601)        == "20011214T215943.0999999-05:00" ||
662            timestamp(iso8601)        == "20011214T215943.1-05:00");
663     assert(timestamp(spaceSeparated) == "20011214T215943.0999999-05:00" ||
664            timestamp(spaceSeparated) == "20011214T215943.1-05:00");
665     assert(timestamp(noTZ)           == "20011215T025943.0999999Z" ||
666            timestamp(noTZ)           == "20011215T025943.1Z");
667     assert(timestamp(noFraction)     == "20011215T025943Z");
668     assert(timestamp(ymd)            == "20021214T000000Z");
669 }
670 
671 /// Construct a string _node.
672 string constructString(ref Node node)
673 {
674     return node.as!string;
675 }
676 
677 /// Convert a sequence of single-element mappings into a sequence of pairs.
678 Node.Pair[] getPairs(string type, Node[] nodes)
679 {
680     Node.Pair[] pairs;
681 
682     foreach(ref node; nodes)
683     {
684         enforce(node.isMapping && node.length == 1,
685                 new Exception("While constructing " ~ type ~
686                               ", expected a mapping with single element"));
687 
688         pairs.assumeSafeAppend();
689         pairs ~= node.as!(Node.Pair[]);
690     }
691 
692     return pairs;
693 }
694 
695 /// Construct an ordered map (ordered sequence of key:value pairs without duplicates) _node.
696 Node.Pair[] constructOrderedMap(ref Node node)
697 {
698     auto pairs = getPairs("ordered map", node.as!(Node[]));
699 
700     //Detect duplicates.
701     //TODO this should be replaced by something with deterministic memory allocation.
702     auto keys = redBlackTree!Node();
703     scope(exit){keys.destroy();}
704     foreach(ref pair; pairs)
705     {
706         enforce(!(pair.key in keys),
707                 new Exception("Duplicate entry in an ordered map: "
708                               ~ pair.key.debugString()));
709         keys.insert(pair.key);
710     }
711     return pairs;
712 }
713 unittest
714 {
715     writeln("D:YAML construction ordered map unittest");
716 
717     alias Node.Pair Pair;
718 
719     Node[] alternateTypes(uint length)
720     {
721         Node[] pairs;
722         foreach(long i; 0 .. length)
723         {
724             auto pair = (i % 2) ? Pair(i.to!string, i) : Pair(i, i.to!string);
725             pairs.assumeSafeAppend();
726             pairs ~= Node([pair]);
727         }
728         return pairs;
729     }
730 
731     Node[] sameType(uint length)
732     {
733         Node[] pairs;
734         foreach(long i; 0 .. length)
735         {
736             auto pair = Pair(i.to!string, i);
737             pairs.assumeSafeAppend();
738             pairs ~= Node([pair]);
739         }
740         return pairs;
741     }
742 
743     bool hasDuplicates(Node[] nodes)
744     {
745         auto node = Node(nodes);
746         return null !is collectException(constructOrderedMap(node));
747     }
748 
749     assert(hasDuplicates(alternateTypes(8) ~ alternateTypes(2)));
750     assert(!hasDuplicates(alternateTypes(8)));
751     assert(hasDuplicates(sameType(64) ~ sameType(16)));
752     assert(hasDuplicates(alternateTypes(64) ~ alternateTypes(16)));
753     assert(!hasDuplicates(sameType(64)));
754     assert(!hasDuplicates(alternateTypes(64)));
755 }
756 
757 /// Construct a pairs (ordered sequence of key: value pairs allowing duplicates) _node.
758 Node.Pair[] constructPairs(ref Node node)
759 {
760     return getPairs("pairs", node.as!(Node[]));
761 }
762 
763 /// Construct a set _node.
764 Node[] constructSet(ref Node node)
765 {
766     auto pairs = node.as!(Node.Pair[]);
767 
768     // In future, the map here should be replaced with something with deterministic
769     // memory allocation if possible.
770     // Detect duplicates.
771     ubyte[Node] map;
772     scope(exit){map.destroy();}
773     Node[] nodes;
774     foreach(ref pair; pairs)
775     {
776         enforce((pair.key in map) is null, new Exception("Duplicate entry in a set"));
777         map[pair.key] = 0;
778         nodes.assumeSafeAppend();
779         nodes ~= pair.key;
780     }
781 
782     return nodes;
783 }
784 unittest
785 {
786     writeln("D:YAML construction set unittest");
787 
788     Node.Pair[] set(uint length)
789     {
790         Node.Pair[] pairs;
791         foreach(long i; 0 .. length)
792         {
793             pairs.assumeSafeAppend();
794             pairs ~= Node.Pair(i.to!string, YAMLNull());
795         }
796 
797         return pairs;
798     }
799 
800     auto DuplicatesShort   = set(8) ~ set(2);
801     auto noDuplicatesShort = set(8);
802     auto DuplicatesLong    = set(64) ~ set(4);
803     auto noDuplicatesLong  = set(64);
804 
805     bool eq(Node.Pair[] a, Node[] b)
806     {
807         if(a.length != b.length){return false;}
808         foreach(i; 0 .. a.length)
809         {
810             if(a[i].key != b[i])
811             {
812                 return false;
813             }
814         }
815         return true;
816     }
817 
818     auto nodeDuplicatesShort   = Node(DuplicatesShort.dup);
819     auto nodeNoDuplicatesShort = Node(noDuplicatesShort.dup);
820     auto nodeDuplicatesLong    = Node(DuplicatesLong.dup);
821     auto nodeNoDuplicatesLong  = Node(noDuplicatesLong.dup);
822 
823     assert(null !is collectException(constructSet(nodeDuplicatesShort)));
824     assert(null is  collectException(constructSet(nodeNoDuplicatesShort)));
825     assert(null !is collectException(constructSet(nodeDuplicatesLong)));
826     assert(null is  collectException(constructSet(nodeNoDuplicatesLong)));
827 }
828 
829 /// Construct a sequence (array) _node.
830 Node[] constructSequence(ref Node node)
831 {
832     return node.as!(Node[]);
833 }
834 
835 /// Construct an unordered map (unordered set of key:value _pairs without duplicates) _node.
836 Node.Pair[] constructMap(ref Node node)
837 {
838     auto pairs = node.as!(Node.Pair[]);
839     //Detect duplicates.
840     //TODO this should be replaced by something with deterministic memory allocation.
841     auto keys = redBlackTree!Node();
842     scope(exit){keys.destroy();}
843     foreach(ref pair; pairs)
844     {
845         enforce(!(pair.key in keys),
846                 new Exception("Duplicate entry in a map: " ~ pair.key.debugString()));
847         keys.insert(pair.key);
848     }
849     return pairs;
850 }
851 
852 
853 // Unittests
854 private:
855 
856 import dyaml.loader;
857 
858 struct MyStruct
859 {
860     int x, y, z;
861 
862     int opCmp(ref const MyStruct s) const pure @safe nothrow
863     {
864         if(x != s.x){return x - s.x;}
865         if(y != s.y){return y - s.y;}
866         if(z != s.z){return z - s.z;}
867         return 0;
868     }
869 }
870 
871 MyStruct constructMyStructScalar(ref Node node)
872 {
873     // Guaranteed to be string as we construct from scalar.
874     auto parts = node.as!string().split(":");
875     return MyStruct(to!int(parts[0]), to!int(parts[1]), to!int(parts[2]));
876 }
877 
878 MyStruct constructMyStructSequence(ref Node node)
879 {
880     // node is guaranteed to be sequence.
881     return MyStruct(node[0].as!int, node[1].as!int, node[2].as!int);
882 }
883 
884 MyStruct constructMyStructMapping(ref Node node)
885 {
886     // node is guaranteed to be mapping.
887     return MyStruct(node["x"].as!int, node["y"].as!int, node["z"].as!int);
888 }
889 
890 unittest
891 {
892     char[] data = "!mystruct 1:2:3".dup;
893     auto loader = Loader(data);
894     auto constructor = new Constructor;
895     constructor.addConstructorScalar("!mystruct", &constructMyStructScalar);
896     loader.constructor = constructor;
897     Node node = loader.load();
898 
899     assert(node.as!MyStruct == MyStruct(1, 2, 3));
900 }
901 
902 unittest
903 {
904     char[] data = "!mystruct [1, 2, 3]".dup;
905     auto loader = Loader(data);
906     auto constructor = new Constructor;
907     constructor.addConstructorSequence("!mystruct", &constructMyStructSequence);
908     loader.constructor = constructor;
909     Node node = loader.load();
910 
911     assert(node.as!MyStruct == MyStruct(1, 2, 3));
912 }
913 
914 unittest
915 {
916     char[] data = "!mystruct {x: 1, y: 2, z: 3}".dup;
917     auto loader = Loader(data);
918     auto constructor = new Constructor;
919     constructor.addConstructorMapping("!mystruct", &constructMyStructMapping);
920     loader.constructor = constructor;
921     Node node = loader.load();
922 
923     assert(node.as!MyStruct == MyStruct(1, 2, 3));
924 }