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