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 }