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