1 module pry.combinators;
2 
3 import pry.traits;
4 import std.meta;
5 
6 private:
7 
8 struct RepImpl(bool collect, size_t minTimes, Parser){
9 	alias Stream = ParserStream!Parser;
10 	static if(collect)
11 		alias Value = ParserValue!Parser[];
12 	else
13 		alias Value = Stream.Range;
14 	Parser parser;
15 
16 	bool parse(ref Stream stream, ref Value value, ref Stream.Error err) {
17 		auto start = stream.mark;
18 		ParserValue!Parser tmp;
19 		for(size_t i = 0; i<minTimes; i++) {
20 			if(!parser.parse(stream, tmp, err)){
21 				stream.restore(start);
22 				return false;
23 			}
24 			static if(collect) value ~= tmp;
25 		}
26 		while(parser.parse(stream, tmp, err)){
27 			static if(collect) value ~= tmp;
28 		}
29 		static if(!collect)
30 			value = stream.slice(start);
31 		return true;
32 	}
33 }
34 
35 
36 /// Apply parser for minTimes times or more and return consumed range.
37 public auto rep(size_t minTimes=1, Parser)(Parser parser)
38 if(isParser!Parser){
39 	return RepImpl!(false, minTimes, Parser)(parser);
40 }
41 
42 /// Apply parser for minTimes times or more and return array of results.
43 public auto array(size_t minTimes=1, Parser)(Parser parser)
44 if(isParser!Parser){
45 	return RepImpl!(true, minTimes, Parser)(parser);
46 }
47 
48 unittest
49 {
50 	import pry.atoms, pry.stream;
51 	alias S = SimpleStream!string;
52 	with(parsers!S)
53 	{
54 		auto p = tk!'a'.rep!2;
55 		string r;
56 		S.Error err;
57 		auto s = S("aaac");
58 		assert(p.parse(s, r, err));
59 		assert(r == "aaa");
60 		
61 		s = S("a");
62 		assert(!p.parse(s, r, err));
63 		assert(err.location == 1);
64 		assert(err.reason == "unexpected end of stream");
65 		
66 		auto p2 = range!('a', 'b').array;
67 		dchar[] r2;
68 		s = S("aba");
69 		assert(p2.parse(s, r2, err));
70 		assert(r2 == "aba"d);
71 		assert(s.empty);
72 	}
73 }
74 
75 
76 struct Map(Parser, alias f) {
77 	alias Stream = ParserStream!Parser;
78 	alias Value = typeof(f(ParserValue!Parser.init));
79 	alias mapper = f;
80 	Parser parser;
81 
82 	bool parse(ref Stream stream, ref Value value, ref Stream.Error err){
83 		ParserValue!Parser tmp;
84 		if(parser.parse(stream, tmp, err)){
85 			value = f(tmp);
86 			return true;
87 		}
88 		else
89 			return false;
90 	}
91 }
92 
93 /// Apply a mapping function to the value of parser.
94 public template map(alias f)
95 {
96 	auto map(Parser)(Parser parser)
97 	if(isParser!Parser){
98 		return Map!(Parser, f)(parser);
99 	}
100 }
101 
102 ///
103 unittest {
104 	import std.conv;
105 	import pry.atoms, pry.stream;
106 	alias S = SimpleStream!string;
107 	with(parsers!S) {
108 		auto digits = range!('0', '9').rep.map!(x=>x.to!int);
109 		S s = S("90");
110 		int r;
111 		S.Error err;
112 		assert(digits.parse(s, r, err));
113 		assert(r == 90);
114 		s = S("a");
115 		assert(!digits.parse(s, r, err));
116 		assert(err.location == 0);
117 	}
118 }
119 
120 
121 
122 struct Seq(P...){
123 	import std.typecons;
124 	alias Stream = ParserStream!(P[0]);
125 	alias Values = staticMap!(ParserValue, P);
126 	P parsers;
127 	
128 	bool parse(ref Stream stream, ref Tuple!Values value, ref Stream.Error err) {
129 		auto save = stream.mark;
130 		foreach(i, ref p; parsers) {
131 			if(!p.parse(stream, value[i], err)){
132 				stream.restore(save);
133 				return false;
134 			}
135 		}
136 		return true;
137 	}
138 }
139 
140 /// Apply multiple parsers one after another as a sequence.
141 public auto seq(P...)(P parsers)
142 if(allSatisfy!(isParser, P)){
143 	static if(P.length == 0)
144 		return Nothing();
145 	else
146 		return Seq!P(parsers);
147 }
148 
149 ///
150 unittest {
151 	import pry.atoms, pry.stream;
152 	import std.range.primitives, std.typecons;
153 	alias S = SimpleStream!string;
154 	with(parsers!S) {
155 		auto elements = seq(tk!'a', range!('a', 'd'), tk!'c');
156 		S s = S("abc");
157 		Tuple!(dchar, dchar, dchar) val;
158 		S.Error err;
159 		assert(elements.parse(s, val, err));
160 		assert(s.empty);
161 		assert(val == tuple('a', 'b', 'c'));
162 		s = S("axc");
163 		assert(!elements.parse(s, val, err));
164 		assert(s.front == 'a');
165 		assert(err.location == 1);
166 	}
167 }
168 
169 struct Nothing{}
170 
171 struct TList(T...){}
172 
173 template commonPrefixLength(T1, T2){
174 	static if(is(T1 == TList!U1, U1...)){
175 		static if(is(T2 == TList!U2, U2...)){
176 			static if(U1.length == 0 || U2.length == 0){
177 				enum commonPrefixLength = 0;
178 			}
179 			else static if(is(U1[0] == U2[0])){
180 				enum commonPrefixLength = 1 +
181 					commonPrefixLength!(TList!(U1[1..$]), TList!(U2[1..$]));
182 			}
183 			else {
184 				enum commonPrefixLength = 0;
185 			}
186 		}
187 	}
188 }
189 
190 auto commonPrefix(P1, P2)(P1 p1, P2 p2){
191 	static if(is(P1 : Seq!U1, U1...)){
192 		enum isSeq = true;
193 		alias T1 = TList!U1;
194 	}
195 	else{
196 		enum isSeq = false;
197 		alias T1 = TList!P1;
198 	}
199 	static if(is(P2 : Seq!U2, U2...)){
200 		alias T2 = TList!U2;
201 	}
202 	else{
203 		alias T2 = TList!P2;
204 	}
205 	enum len = commonPrefixLength!(T1,T2);
206 	static if(isSeq)
207 		return seq(p1.parsers[0..len]);
208 	else static if(len)
209 		return seq(p1);
210 	else
211 		return Nothing();
212 }
213 
214 auto commonPrefix(P...)(P p)
215 if(P.length > 2){
216 	return commonPrefix(commonPrefix(p[0], p[1]), p[2..$]);
217 }
218 
219 unittest {
220 	import pry.atoms, pry.stream;
221 	alias S = SimpleStream!string;
222 	with(parsers!S){
223 		auto p1 = seq(tk!'a', tk!'b');
224 		auto p2 = seq(tk!'a');
225 		auto p3 = tk!'a';
226 		auto p4 = seq(tk!'b', tk!'a');
227 		assert(commonPrefix(p1, p2) == seq(tk!'a'));
228 		assert(commonPrefix(p2, p3) == seq(tk!'a'));
229 		assert(commonPrefix(p3, p3) == seq(tk!'a'));
230 		assert(commonPrefix(p3, p1) == seq(tk!'a'));
231 		assert(commonPrefix(p1, p4) == Nothing());
232 		assert(commonPrefix(p3, p4) == Nothing());
233 		assert(commonPrefix(p4, p3) == Nothing());
234 		assert(commonPrefix(p1, p2, p3) == seq(tk!'a'));
235 		assert(commonPrefix(p1, p2, p3, p4) == Nothing());
236 	}
237 }
238 
239 auto suffix(P1, P2)(P1 prefix, P2 parser)
240 if(isParser!P1 && isParser!P2){
241 	static if(is(P1 : Seq!U1, U1...)){
242 		alias T1 = TList!U1;
243 	}
244 	else{
245 		alias T1 = TList!P1;
246 	}
247 	static if(is(P2 : Seq!U2, U2...)){
248 		enum isSeq = true;
249 		alias T2 = TList!U2;
250 	}
251 	else{
252 		enum isSeq = false;
253 		alias T2 = TList!P2;
254 	}
255 	enum len = commonPrefixLength!(T1,T2);
256 	static if(is(T1 : TList!U, U...)){
257 		static assert(len == U.length);
258 	}
259 	static if(isSeq){
260 		return seq(parser.parsers[len..$]);
261 	}
262 	else{
263 		static if(len > 0)
264 			return Nothing();
265 		else
266 			return seq(parser);
267 	}
268 }
269 
270 unittest{
271 	import pry.atoms, pry.stream;
272 	alias S = SimpleStream!string;
273 	with(parsers!S){
274 		auto p1 = seq(tk!'a', tk!'b');
275 		auto p2 = seq(tk!'a');
276 		auto p3 = tk!'a';
277 		auto p4 = seq(tk!'b', tk!'a');
278 		assert(suffix(p2, p1) == seq(tk!'b'));
279 		assert(suffix(p3, p1) == seq(tk!'b'));
280 		assert(suffix(p2, p3) == Nothing());
281 	}
282 }
283 
284 template Unmap(P){
285 	static if(is(P : Map!(U, f), alias f, U)){
286 		alias Unmap = U;
287 	}
288 	else {
289 		alias Unmap = P;
290 	}
291 }
292 
293 auto unmap(P)(P parser){
294 	static if(is(P : Map!(U, f), alias f, U)){
295 		return parser.parser;
296 	}
297 	else {
298 		return parser;
299 	}
300 }
301 
302 unittest{
303 	import pry.atoms, pry.stream;
304 	alias S = SimpleStream!string;
305 	with(parsers!S){
306 		auto x = tk!'a'.map!(x => 1);
307 		assert(unmap(x) == tk!'a');
308 		assert(unmap(unmap(x)) == tk!'a');
309 	}
310 }
311 
312 struct Any(P...){
313 	import std.variant, std.typecons;
314 	alias Stream = ParserStream!(P[0]);
315 	alias Values = NoDuplicates!(staticMap!(ParserValue, P));
316 
317 	static if(Values.length == 1)
318 		alias Value = Values[0];
319 	else
320 		alias Value = Algebraic!Values;
321 	
322 	P parsers;
323 	alias Prefix = typeof(extractPrefix());
324 	Prefix prefix;
325 
326 	template mapper(size_t i){
327 		static if(is(P[i] == Map!(U, f), U, alias f))
328 			alias mapper = P[i].mapper;
329 		else
330 			alias mapper = x => x;
331 	}
332 
333 	this(P parsers){
334 		this.parsers = parsers;
335 		prefix = extractPrefix();
336 	}
337 
338 	auto extractPrefix(){
339 		staticMap!(Unmap, P) unmapped = void;
340 		foreach(i, ref p; parsers){
341 			unmapped[i] = unmap(p);
342 		}
343 		return commonPrefix(unmapped);
344 	}
345 
346 	auto combine(T1, T2)(T1 prefixValue, T2 suffixValue){
347 		static if(is(T1 == Nothing)){
348 			return suffixValue;
349 		}
350 		else{
351 			return tuple(prefixValue.expand, suffixValue.expand);
352 		}
353 	}
354 
355 	bool parse(ref Stream stream, ref Value value, ref Stream.Error err) {
356 		static if(is(Prefix == Nothing)){
357 			Nothing prefixValue;
358 		}
359 		else{
360 			ParserValue!Prefix prefixValue;
361 			if(!prefix.parse(stream, prefixValue, err)){
362 				return false;
363 			}
364 		}
365 		Stream.Error current, deepest;
366 		bool ret = false;
367 		foreach(i, ref p; parsers) {
368 			static if(is(Prefix == Nothing))
369 				auto sp = unmap(p);
370 			else
371 				auto sp = suffix(prefix, unmap(p));
372 			alias Suffix = typeof(sp);
373 			static if(is(Suffix == Nothing)){
374 				value = mapper!i(prefixValue.expand);
375 				ret = true;
376 				goto L_end;
377 			}
378 			else {
379 				ParserValue!Suffix suffixValue;
380 				static if(i == 0){
381 					if(sp.parse(stream, suffixValue, deepest)){
382 						value = mapper!i(combine(prefixValue, suffixValue));
383 						return true;
384 					}
385 				}
386 				else {
387 					if(sp.parse(stream, suffixValue, current)){
388 						value = mapper!i(combine(prefixValue, suffixValue));
389 						return true;
390 					}
391 					// pick the deeper error
392 					if(deepest.location < current.location){
393 						deepest = current;
394 					}
395 				}
396 			}
397 		}
398 L_end:
399 		err = deepest;
400 		return ret;
401 	}
402 }
403 
404 /// Try each of provided parsers until one succeeds.
405 public auto any(P...)(P parsers)
406 if(allSatisfy!(isParser, P)){
407 	return Any!P(parsers);
408 }
409 
410 ///
411 unittest {
412 	import pry.atoms, pry.stream;
413 	import std.range.primitives, std.conv, std.variant;
414 	alias S = SimpleStream!string;
415 	with(parsers!S) {
416 		auto digits = range!('0', '9').rep.map!(x => x.to!int);
417 		static assert(isParser!(typeof(digits)));
418 		auto parser = any(tk!'a', digits);
419 		S s = "10a";
420 		S.Error err;
421 		Algebraic!(dchar, int) value;
422 		assert(parser.parse(s, value, err));
423 		assert(value == 10);
424 		assert(parser.parse(s, value, err));
425 		assert(value == cast(dchar)'a');
426 		assert(s.empty);
427 	}
428 }
429 
430 unittest {
431 	import pry.atoms, pry.stream;
432 	alias S = SimpleStream!string;
433 	with(parsers!S) {
434 		auto e = dynamic!int;
435 		e = any(
436 			seq(tk!'0', e).map!(x => 1),
437 			tk!'1'.map!(x => 0)
438 		);
439 		S.Error err;
440 		int val;
441 		S s = S("0001");
442 		assert(e.parse(s, val, err));
443 	}
444 }
445 
446 unittest {
447 	import pry.atoms, pry.stream;
448 	import std.typecons;
449 	alias S = SimpleStream!string;
450 	with(parsers!S) {
451 		auto p = any(
452 			seq(tk!'0', tk!'0'),
453 			seq(tk!'1', tk!'1')
454 		);
455 		S s = "01".stream;
456 		Tuple!(dchar, dchar) value;
457 		S.Error err;
458 		assert(!p.parse(s, value, err));
459 		assert(err.location == 1);
460 	}
461 }