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  * Composes nodes from YAML events provided by parser.
9  * Code based on PyYAML: http://www.pyyaml.org
10  */
11 module dyaml.composer;
12 
13 import core.memory;
14 
15 import std.algorithm;
16 import std.array;
17 import std.conv;
18 import std.exception;
19 import std.range;
20 import std.typecons;
21 
22 import dyaml.constructor;
23 import dyaml.event;
24 import dyaml.exception;
25 import dyaml.node;
26 import dyaml.parser;
27 import dyaml.resolver;
28 
29 
30 package:
31 /**
32  * Exception thrown at composer errors.
33  *
34  * See_Also: MarkedYAMLException
35  */
36 class ComposerException : MarkedYAMLException
37 {
38     mixin MarkedExceptionCtors;
39 }
40 
41 ///Composes YAML documents from events provided by a Parser.
42 final class Composer
43 {
44     private:
45         ///Parser providing YAML events.
46         Parser parser_;
47         ///Resolver resolving tags (data types).
48         Resolver resolver_;
49         ///Constructor constructing YAML values.
50         Constructor constructor_;
51         ///Nodes associated with anchors. Used by YAML aliases.
52         Node[string] anchors_;
53 
54         ///Used to reduce allocations when creating pair arrays.
55         ///
56         ///We need one appender for each nesting level that involves
57         ///a pair array, as the inner levels are processed as a
58         ///part of the outer levels. Used as a stack.
59         Appender!(Node.Pair[])[] pairAppenders_;
60         ///Used to reduce allocations when creating node arrays.
61         ///
62         ///We need one appender for each nesting level that involves
63         ///a node array, as the inner levels are processed as a
64         ///part of the outer levels. Used as a stack.
65         Appender!(Node[])[] nodeAppenders_;
66 
67     public:
68         /**
69          * Construct a composer.
70          *
71          * Params:  parser      = Parser to provide YAML events.
72          *          resolver    = Resolver to resolve tags (data types).
73          *          constructor = Constructor to construct nodes.
74          */
75         this(Parser parser, Resolver resolver, Constructor constructor) @safe
76         {
77             parser_ = parser;
78             resolver_ = resolver;
79             constructor_ = constructor;
80         }
81 
82         ///Destroy the composer.
83         pure @safe nothrow ~this()
84         {
85             parser_ = null;
86             resolver_ = null;
87             constructor_ = null;
88             anchors_.destroy();
89             anchors_ = null;
90         }
91 
92         /**
93          * Determine if there are any nodes left.
94          *
95          * Must be called before loading as it handles the stream start event.
96          */
97         bool checkNode() @safe
98         {
99             // If next event is stream start, skip it
100             parser_.skipOver!"a.id == b"(EventID.StreamStart);
101 
102             //True if there are more documents available.
103             return parser_.front.id != EventID.StreamEnd;
104         }
105 
106         ///Get a YAML document as a node (the root of the document).
107         Node getNode() @safe
108         {
109             //Get the root node of the next document.
110             assert(parser_.front.id != EventID.StreamEnd,
111                    "Trying to get a node from Composer when there is no node to " ~
112                    "get. use checkNode() to determine if there is a node.");
113 
114             return composeDocument();
115         }
116 
117         ///Get single YAML document, throwing if there is more than one document.
118         Node getSingleNode() @safe
119         {
120             assert(parser_.front.id != EventID.StreamEnd,
121                    "Trying to get a node from Composer when there is no node to " ~
122                    "get. use checkNode() to determine if there is a node.");
123 
124             Node document = composeDocument();
125 
126             //Ensure that the stream contains no more documents.
127             enforce(parser_.front.id == EventID.StreamEnd,
128                     new ComposerException("Expected single document in the stream, " ~
129                                           "but found another document.",
130                                           parser_.front.startMark));
131 
132             skipExpected(EventID.StreamEnd);
133             assert(parser_.empty, "Found event after stream end");
134 
135             return document;
136         }
137 
138     private:
139 
140         void skipExpected(const EventID id) @safe
141         {
142             const foundExpected = parser_.skipOver!"a.id == b"(id);
143             assert(foundExpected, text("Expected ", id, " not found."));
144         }
145         ///Ensure that appenders for specified nesting levels exist.
146         ///
147         ///Params:  pairAppenderLevel = Current level in the pair appender stack.
148         ///         nodeAppenderLevel = Current level the node appender stack.
149         void ensureAppendersExist(const uint pairAppenderLevel, const uint nodeAppenderLevel)
150             @safe
151         {
152             while(pairAppenders_.length <= pairAppenderLevel)
153             {
154                 pairAppenders_ ~= appender!(Node.Pair[])();
155             }
156             while(nodeAppenders_.length <= nodeAppenderLevel)
157             {
158                 nodeAppenders_ ~= appender!(Node[])();
159             }
160         }
161 
162         ///Compose a YAML document and return its root node.
163         Node composeDocument() @safe
164         {
165             skipExpected(EventID.DocumentStart);
166 
167             //Compose the root node.
168             Node node = composeNode(0, 0);
169 
170             skipExpected(EventID.DocumentEnd);
171 
172             anchors_.destroy();
173             return node;
174         }
175 
176         /// Compose a node.
177         ///
178         /// Params: pairAppenderLevel = Current level of the pair appender stack.
179         ///         nodeAppenderLevel = Current level of the node appender stack.
180         Node composeNode(const uint pairAppenderLevel, const uint nodeAppenderLevel) @safe
181         {
182             if(parser_.front.id == EventID.Alias)
183             {
184                 const event = parser_.front;
185                 parser_.popFront();
186                 const anchor = event.anchor;
187                 enforce((anchor in anchors_) !is null,
188                         new ComposerException("Found undefined alias: " ~ anchor,
189                                               event.startMark));
190 
191                 //If the node referenced by the anchor is uninitialized,
192                 //it's not finished, i.e. we're currently composing it
193                 //and trying to use it recursively here.
194                 enforce(anchors_[anchor] != Node(),
195                         new ComposerException("Found recursive alias: " ~ anchor,
196                                               event.startMark));
197 
198                 return anchors_[anchor];
199             }
200 
201             const event = parser_.front;
202             const anchor = event.anchor;
203             if((anchor !is null) && (anchor in anchors_) !is null)
204             {
205                 throw new ComposerException("Found duplicate anchor: " ~ anchor,
206                                             event.startMark);
207             }
208 
209             Node result;
210             //Associate the anchor, if any, with an uninitialized node.
211             //used to detect duplicate and recursive anchors.
212             if(anchor !is null)
213             {
214                 anchors_[anchor] = Node();
215             }
216 
217             switch (parser_.front.id)
218             {
219                 case EventID.Scalar:
220                     result = composeScalarNode();
221                     break;
222                 case EventID.SequenceStart:
223                     result = composeSequenceNode(pairAppenderLevel, nodeAppenderLevel);
224                     break;
225                 case EventID.MappingStart:
226                     result = composeMappingNode(pairAppenderLevel, nodeAppenderLevel);
227                     break;
228                 default: assert(false, "This code should never be reached");
229             }
230 
231             if(anchor !is null)
232             {
233                 anchors_[anchor] = result;
234             }
235             return result;
236         }
237 
238         ///Compose a scalar node.
239         Node composeScalarNode() @safe
240         {
241             const event = parser_.front;
242             parser_.popFront();
243             const tag = resolver_.resolve(NodeID.Scalar, event.tag, event.value,
244                                           event.implicit);
245 
246             Node node = constructor_.node(event.startMark, event.endMark, tag,
247                                           event.value, event.scalarStyle);
248 
249             return node;
250         }
251 
252         /// Compose a sequence node.
253         ///
254         /// Params: pairAppenderLevel = Current level of the pair appender stack.
255         ///         nodeAppenderLevel = Current level of the node appender stack.
256         Node composeSequenceNode(const uint pairAppenderLevel, const uint nodeAppenderLevel)
257             @safe
258         {
259             ensureAppendersExist(pairAppenderLevel, nodeAppenderLevel);
260             auto nodeAppender = &(nodeAppenders_[nodeAppenderLevel]);
261 
262             const startEvent = parser_.front;
263             parser_.popFront();
264             const tag = resolver_.resolve(NodeID.Sequence, startEvent.tag, null,
265                                           startEvent.implicit);
266 
267             while(parser_.front.id != EventID.SequenceEnd)
268             {
269                 nodeAppender.put(composeNode(pairAppenderLevel, nodeAppenderLevel + 1));
270             }
271 
272             Node node = constructor_.node(startEvent.startMark, parser_.front.endMark,
273                                           tag, nodeAppender.data.dup, startEvent.collectionStyle);
274             parser_.popFront();
275             nodeAppender.clear();
276 
277             return node;
278         }
279 
280         /**
281          * Flatten a node, merging it with nodes referenced through YAMLMerge data type.
282          *
283          * Node must be a mapping or a sequence of mappings.
284          *
285          * Params:  root              = Node to flatten.
286          *          startMark         = Start position of the node.
287          *          endMark           = End position of the node.
288          *          pairAppenderLevel = Current level of the pair appender stack.
289          *          nodeAppenderLevel = Current level of the node appender stack.
290          *
291          * Returns: Flattened mapping as pairs.
292          */
293         Node.Pair[] flatten(ref Node root, const Mark startMark, const Mark endMark,
294                             const uint pairAppenderLevel, const uint nodeAppenderLevel) @safe
295         {
296             void error(Node node)
297             {
298                 //this is Composer, but the code is related to Constructor.
299                 throw new ConstructorException("While constructing a mapping, " ~
300                                                "expected a mapping or a list of " ~
301                                                "mappings for merging, but found: " ~
302                                                node.type.toString() ~
303                                                " NOTE: line/column shows topmost parent " ~
304                                                "to which the content is being merged",
305                                                startMark, endMark);
306             }
307 
308             ensureAppendersExist(pairAppenderLevel, nodeAppenderLevel);
309             auto pairAppender = &(pairAppenders_[pairAppenderLevel]);
310 
311             if(root.isMapping)
312             {
313                 Node[] toMerge;
314                 toMerge.reserve(root.length);
315                 foreach(ref Node key, ref Node value; root)
316                 {
317                     if(key.isType!YAMLMerge)
318                     {
319                         toMerge ~= value;
320                     }
321                     else
322                     {
323                         auto temp = Node.Pair(key, value);
324                         pairAppender.put(temp);
325                     }
326                 }
327                 foreach(node; toMerge)
328                 {
329                     pairAppender.put(flatten(node, startMark, endMark,
330                                                  pairAppenderLevel + 1, nodeAppenderLevel));
331                 }
332             }
333             //Must be a sequence of mappings.
334             else if(root.isSequence) foreach(ref Node node; root)
335             {
336                 if(!node.isType!(Node.Pair[])){error(node);}
337                 pairAppender.put(flatten(node, startMark, endMark,
338                                              pairAppenderLevel + 1, nodeAppenderLevel));
339             }
340             else
341             {
342                 error(root);
343             }
344 
345             auto flattened = pairAppender.data.dup;
346             pairAppender.clear();
347 
348             return flattened;
349         }
350 
351         /// Compose a mapping node.
352         ///
353         /// Params: pairAppenderLevel = Current level of the pair appender stack.
354         ///         nodeAppenderLevel = Current level of the node appender stack.
355         Node composeMappingNode(const uint pairAppenderLevel, const uint nodeAppenderLevel)
356             @safe
357         {
358             ensureAppendersExist(pairAppenderLevel, nodeAppenderLevel);
359             const startEvent = parser_.front;
360             parser_.popFront();
361             const tag = resolver_.resolve(NodeID.Mapping, startEvent.tag, null,
362                                           startEvent.implicit);
363             auto pairAppender = &(pairAppenders_[pairAppenderLevel]);
364 
365             Tuple!(Node, Mark)[] toMerge;
366             while(parser_.front.id != EventID.MappingEnd)
367             {
368                 auto pair = Node.Pair(composeNode(pairAppenderLevel + 1, nodeAppenderLevel),
369                                       composeNode(pairAppenderLevel + 1, nodeAppenderLevel));
370 
371                 //Need to flatten and merge the node referred by YAMLMerge.
372                 if(pair.key.isType!YAMLMerge)
373                 {
374                     toMerge ~= tuple(pair.value, cast(Mark)parser_.front.endMark);
375                 }
376                 //Not YAMLMerge, just add the pair.
377                 else
378                 {
379                     pairAppender.put(pair);
380                 }
381             }
382             foreach(node; toMerge)
383             {
384                 merge(*pairAppender, flatten(node[0], startEvent.startMark, node[1],
385                                              pairAppenderLevel + 1, nodeAppenderLevel));
386             }
387             auto numUnique = pairAppender.data.dup
388                                 .sort!((x,y) => x.key > y.key)
389                                 .uniq!((x,y) => x.key == y.key)
390                                 .walkLength;
391             enforce(numUnique == pairAppender.data.length,
392                     new ComposerException("Duplicate key found in mapping", parser_.front.startMark));
393 
394             Node node = constructor_.node(startEvent.startMark, parser_.front.endMark,
395                                           tag, pairAppender.data.dup, startEvent.collectionStyle);
396             parser_.popFront();
397 
398             pairAppender.clear();
399             return node;
400         }
401 }