Unofficial Dub Package Documentation 
1 /**
2 This module is an attempt at introducing pattern-matching in D.
3 
4 Pattern matching is a type- or value-matching present in functional languages like ML or Haskell.
5 
6 The goal here is to obtain code like:
7 
8 ----
9 Pattern!"[ a, b, ... ]" p1; // match any range with at least two elements
10                             // the rest being discarded.
11 
12 auto m1 = p1([0,1,2,3,4]); // match and associate 'a' and 'b' with O and 1.
13 assert(m1.a == 0 && m1.b == 1);
14 auto m2 = p1("abc");
15 assert(m2.a = 'a' && m2.b == 'b');
16 auto m3 = p1(tuple("abc",0)); // not a range, the pattern fails
17 assert(m3 == matchFailure; // predefined constant
18 
19 Pattern!"Tuple!(.,.) t" p2; // match any std.typecons.Tuple with two elements, of any type
20 auto m4 = p2(tuple("abc",0));
21 assert(m4.t = tuple("abc",0); // only the global pattern is named, and hence captured
22 assert(p2(tuple("abc")) == matchFailure); // only one member -> failure
23 assert(p2(tuple("abc",0,1)) == matchFailure); // three members -> failure (the pattern has no trailing ...
24 
25 Pattern!" . { int, double, double }" p3; // match any aggregate (struct, class)
26                                          // with three members being int,double and double, in that order.
27 ----
28 
29 Don't salivate, it's not implemented yet.
30 */
31 module pegged.examples.pattern;
32 
33 import std.range;
34 import std.traits;
35 import std.typecons;
36 import std.typetuple;
37 
38 import pegged.grammar;
39 
40 mixin(grammar(`
41 Pattern:
42     Global     <  Choice :eoi
43     Choice     <  Sequence (:'/' Sequence)*
44     Sequence   <  Primary (:',' Primary)*
45     Primary    <  (Aggregate / Range / Identifier / Literal / REST / ANY) Name?
46 
47     Name       <  identifier
48     Aggregate  <  (Identifier / ANY) (Tuple / Record)
49     Tuple      <  '{' (Choice (:',' Choice)*)? '}'
50     Record     <  '{' Field (','Field)* '}'
51     Field      <  Identifier :'=' Choice
52     Range      <  '[' (Choice (:',' Choice)*)? ']'
53     Identifier <  identifier
54     Literal    <  Number / Char / String/ Bool
55     Number     <~ Digit+ ('.' Digit*)?
56     Digit      <  [0-9]
57     Char       <~ quote . quote # TODO: adding escape chars and Unicode chars
58     String     <~ doublequote (!doublequote .)* doublequote
59     Bool       <  "true" / "false"
60 
61     REST       <  "..."
62     ANY        <  "."
63     Spacing    <: spacing
64 `));
65 
66 template TypeFailure(T...)
67 {
68     enum successful = false;
69     alias TypeTuple!() Types;
70     enum begin = 0;
71     enum end = 0;
72     alias T Rest;
73 }
74 
75 struct TypeAny
76 {
77     template Match(T...)
78     {
79         static if (T.length == 0)
80             mixin TypeFailure!(T);
81         else
82         {
83             enum successful = true;
84             alias T[0..1] Types;
85             enum begin = 0;
86             enum end = 1;
87             alias T[1..$] Rest;
88         }
89     }
90 }
91 
92 struct TypeEnd
93 {
94     template Match(T...)
95     {
96         static if (T.length == 0)
97         {
98             enum successful = true;
99             alias TypeTuple!() Types;
100             enum begin = 0;
101             enum end = 0;
102             alias T Rest;
103         }
104         else
105             mixin TypeFailure!(T);
106     }
107 }
108 
109 struct TypeEps
110 {
111     template Match(T...)
112     {
113         enum successful = true;
114         alias TypeTuple!() Types;
115         enum begin = 0;
116         enum end = 0;
117         alias T Rest;
118     }
119 }
120 
121 struct TypeLiteral(U...)
122 {
123     template Match(T...)
124     {
125         static if (T.length < U.length || !is(T[0..U.length] == U))
126             mixin TypeFailure!(T);
127         else
128         {
129             enum successful = true;
130             alias T[0..U.length] Types;
131             enum begin = 0;
132             enum end = U.length;
133             alias T[U.length..$] Rest;
134         }
135     }
136 }
137 
138 template isSubtype(T...)
139 {
140     static if (T.length == 0)
141         enum isSubtype = true;
142     else static if (is(T[0] : T[$/2]))
143         enum isSubtype = isSubtype!(T[1..$/2],T[$/2+1..$]);
144     else
145         enum isSubtype = false;
146 }
147 
148 struct TypeSubType(U...)
149 {
150     template Match(T...)
151     {
152         static if (T.length < U.length || !isSubtype!(T[0..U.length],U))
153             mixin TypeFailure!(T);
154         else
155         {
156             enum successful = true;
157             alias T[0..U.length] Types;
158             enum begin = 0;
159             enum end = U.length;
160             alias T[U.length..$] Rest;
161         }
162     }
163 }
164 
165 struct TypeOr(alias Pattern1, alias Pattern2)
166 {
167     template Match(T...)
168     {
169         alias Pattern1.Match!(T) P1;
170         static if (P1.successful)
171             alias P1 Match;
172         else
173             alias Pattern2.Match!(T) Match;
174     }
175 }
176 
177 template TypeOr(Patterns...) if (Patterns.length > 2)
178 {
179     alias TypeOr!(Patterns[0], TypeOr!(Patterns[1..$])) TypeOr;
180 }
181 
182 template TypeOr(Patterns...) if (Patterns.length == 1)
183 {
184     alias Patterns[0] TypeOr;
185 }
186 
187 struct TypeAnd(alias Pattern1, alias Pattern2)
188 {
189     template Match(T...)
190     {
191         alias Pattern1.Match!(T) P1;
192         alias Pattern2.Match!(Pattern1.Match!(T).Rest) P2;
193         static if (P1.successful && P2.successful)
194         {
195             enum successful = true;
196             alias TypeTuple!(P1.Types, P2.Types) Types;
197             enum begin = P1.begin;
198             enum end = P2.end;
199             alias P2.Rest Rest;
200         }
201         else
202             mixin TypeFailure!(T);
203     }
204 }
205 
206 template TypeAnd(Patterns...) if (Patterns.length > 2)
207 {
208     alias TypeAnd!(Patterns[0], TypeAnd!(Patterns[1..$])) And;
209 }
210 
211 template TypeAnd(Patterns...) if (Patterns.length == 1)
212 {
213     alias Patterns[0] TypeAnd;
214 }
215 
216 struct TypeOption(alias Pattern)
217 {
218     template Match(T...)
219     {
220         alias Pattern.Match!(T) P;
221         static if (P.successful)
222             alias P Match;
223         else
224         {
225             enum successful = true;
226             alias TypeTuple!() Types;
227             enum begin = 0;
228             enum end = 0;
229             alias T Rest;
230         }
231     }
232 }
233 
234 struct TypeZeroOrMore(alias Pattern)
235 {
236     template Match(T...)
237     {
238         alias Pattern.Match!(T) P;
239         static if (P.successful)
240         {
241             enum successful = true;
242             alias TypeTuple!(P.Types, TypeZeroOrMore!(Pattern).Match!(P.Rest).Types) Types;
243             enum begin = P.begin;
244             alias TypeZeroOrMore!(Pattern).Match!(P.Rest) More;
245             enum end = P.end + More.end;
246             alias TypeZeroOrMore!(Pattern).Match!(P.Rest).Rest Rest;
247         }
248         else
249         {
250             enum successful = true;
251             alias TypeTuple!() Types;
252             enum begin = 0;
253             enum end = 0;
254             alias T Rest;
255         }
256     }
257 }
258 
259 struct TypeOneOrMore(alias Pattern)
260 {
261     template Match(T...)
262     {
263         alias Pattern.Match!(T) P;
264         static if (P.successful)
265         {
266             enum successful = true;
267             alias TypeTuple!(P.Types, TypeZeroOrMore!(Pattern).Match!(P.Rest).Types) Types;
268             enum begin = P.begin;
269             alias TypeZeroOrMore!(Pattern).Match!(P.Rest) More;
270             enum end = P.end + More.end;
271             alias TypeZeroOrMore!(Pattern).Match!(P.Rest).Rest Rest;
272         }
273         else
274             mixin TypeFailure!(T);
275     }
276 }
277 
278 /**
279 Discards the matched types, but propagate the indices.
280 */
281 struct TypeDiscardMatch(alias Pattern)
282 {
283     template Match(T...)
284     {
285         alias Pattern.Match!(T) P;
286         static if (P.successful)
287         {
288             enum successful = true;
289             alias TypeTuple!() Types; // Forget the match,
290             enum begin = P.begin;     // but propagate indices
291             enum end = P.end;         //
292             alias P.Rest Rest;        // and the input
293         }
294         else
295             mixin TypeFailure!(T);
296     }
297 }
298 
299 struct TypePosLookAhead(alias Pattern)
300 {
301     template Match(T...)
302     {
303         alias Pattern.Match!(T) P;
304         static if (P.successful)
305         {
306             enum successful = true;
307             alias TypeTuple!() Types;
308             enum begin = 0;
309             enum end = 0;
310             alias T Rest;
311         }
312         else
313             mixin TypeFailure!(T);
314     }
315 }
316 
317 struct TypeNegLookAhead(alias Pattern)
318 {
319     template Match(T...)
320     {
321         alias Pattern.Match!(T) P;
322         static if (P.successful)
323             mixin TypeFailure!(T);
324         else
325         {
326             enum successful = true;
327             alias TypeTuple!() Types;
328             enum begin = 0;
329             enum end = 0;
330             alias T Rest;
331         }
332     }
333 }
334 
335 struct isRange
336 {
337     template Match(T...)
338     {
339         static if (isInputRange!(T[0]))
340         {
341             enum successful = true;
342             alias T[0] Types;
343             enum begin = 0;
344             enum end = 1;
345             alias T[1..$] Rest;
346         }
347         else
348             mixin TypeFailure!(T);
349     }
350 }
351 
352 struct TypeSatisfy(alias test)
353 {
354     template Match(T...)
355     {
356         static if (test!(T[0]))
357         {
358             enum successful = true;
359             alias T[0] Types;
360             enum begin = 0;
361             enum end = 1;
362             alias T[1..$] Rest;
363         }
364         else
365             mixin TypeFailure!(T);
366     }
367 }
368 
369 struct MatchResult(size_t junction, T...)
370 {
371     bool successful;
372     T[0..junction] match;
373     size_t begin;
374     size_t end;
375     T[junction..$] rest;
376 }
377 
378 struct Success(M...)
379 {
380     M match;
381     size_t begin;
382     size_t end;
383 
384     auto rest(R...)(R rest)
385     {
386         return MatchResult!(M.length, M, R)(true, match, begin, end, rest);
387     }
388 }
389 
390 Success!(M) success(M...)(M match, size_t begin, size_t end)
391 {
392     return Success!(M)(match, begin, end);
393 }
394 
395 auto failure(R...)(R rest)
396 {
397     return MatchResult!(0,R)(false, 0,0, rest);
398 }
399 
400 auto anyValue(Args...)(Args args)
401 {
402     static if (Args.length > 0)
403         return success(args[0],0,1).rest(args[1..$]);
404     else
405         return failure(args);
406 }
407 
408 auto endValue(Args...)(Args args)
409 {
410     static if (Args.length == 0)
411         return success(0,0).rest(args);
412     else
413         return failure(args);
414 }
415 
416 /+
417 template literalValue(values...)
418 {
419     auto literalValue(Args...)(Args args)
420     {
421         if (
422             return success(0,values.length).rest(args[values.length..$]);
423         else
424             return failure(args);
425     }
426 }
427 +/
428 
429 Tuple!(ElementType!R, R) rangeAny(R)(R r) if (isInputRange!R)
430 {
431     if (r.empty)
432         throw new Exception("Empty range, could not pattern-match");
433     else
434     {
435         auto head = r.front();
436         r.popFront();
437         return tuple(head, r);
438     }
439 }
440 
441 Tuple!(R,R) rangeRest(R)(R r) if (isInputRange!R)
442 {
443     if (r.empty)
444         throw new Exception("Empty range, could not pattern-match");
445     else
446         return tuple(r, r); // second r will not be used, but is needed to be compatible with other range patterns: Tuple!(result,rest)
447 }
448 
449 template RangePatternResult(R) if (isInputRange!R)
450 {
451     template RangePatternResult(alias T)
452     {
453         alias ReturnType!(T!R) RangePatternResult;
454     }
455 }
456 
457 template onRange(RangePatterns...)
458 {
459     auto onRange(R)(R r) if (isInputRange!(R))
460     {
461         alias RangePatternResult!R GetType;
462 
463         staticMap!(GetType, RangePatterns) _temp;
464 
465         static if (RangePatterns.length > 0)
466         {
467             _temp[0] = RangePatterns[0](r);
468             foreach(i,pat; RangePatterns[1..$])
469                 _temp[i+1] = RangePatterns[i+1](_temp[i][1]);
470         }
471 
472         struct MatchResult
473         {
474             GetType!(RangePatterns[0]).Types[0] a;
475             GetType!(RangePatterns[1]).Types[0] b;
476             GetType!(RangePatterns[2]).Types[0] c;
477         }
478 
479         return MatchResult(_temp[0][0],_temp[1][0],_temp[2][0]);
480     }
481 }
482

Page generated by adrdox