1 /**
2    Symbolic (Regular) Expressions and Predicate Logic.
3 
4    Syntax is similar to Emacs' sregex, rx.
5 
6    String patterns are matched by their raw bytes for now.
7 
8    Copyright: Per Nordlöw 2018-.
9    License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
10    Authors: $(WEB Per Nordlöw)
11 
12    TODO
13    Overload operators & (and), ! (not),
14 
15    TODO Add pattern for expressing inference with `infer`
16    (infer
17     ((x instanceOf X) &
18      (X subClassOf Y))
19      (x instaceOf Y))
20 
21    TODO
22    Variables are either
23    - _ (ignore)
24    - _`x`, _`y`, etc
25    - _'x', _'y'
26    - _!0, _!1, ..., _!(n-1)
27 
28    infer(rel!`desire`(_!`x`, _!`y`) &&
29          rel!`madeOf`(_!`z`, _!`y`),
30          rel!`desire`(_!`x`, _!`z`))
31 
32    TODO Support variables of specific types and inference using predicate logic:
33         infer(and(fact(var!'x', rel'desire', var!'y'),
34                   fact(var!'z', opt(rel'madeOf',
35                               rel'instanceOf'), var!'y'))),
36               pred(var!'x', rel'desire', var!'z'
37               ))
38 
39    TODO Make returns from factory functions immutable.
40    TODO Reuse return patterns from Lit
41 
42    TODO
43    const s = seq(`al.`.lit,`pha`.lit);
44    const t = `al`.lit ~ `pha`.lit;
45    assert(s !is t);
46    assert(equal(s, t));
47 
48  */
49 module nxt.symbolic;
50 
51 import std.algorithm: find, all, map, reduce, min, max, joiner, equal, each, filter;
52 import std.range: empty;
53 import std.array: array;
54 import std..string: representation;
55 import std.traits: isSomeString;
56 import nxt.find_ex: findAcronymAt, FindContext;
57 import nxt.dbgio;
58 import nxt.static_bitarray;
59 
60 /** Base Pattern.
61  */
62 class Patt
63 {
64     @safe pure nothrow:
65 
66     /** Match $(D this) with $(D haystack) at Offset $(D soff).
67      Returns: Matched slice or [] if not match.
68     */
69     final auto ref matchU(in ubyte[] haystack, size_t soff = 0) const
70     {
71         const hit = atU(haystack, soff);
72         return hit != hit.max ? haystack[0..hit] : [];
73     }
74     final auto ref match(const scope string haystack, size_t soff = 0) const
75     {
76         return matchU(haystack.representation, soff);
77     }
78 
79     Seq opBinary(string op)(Patt rhs) if (op == `~`) // template can't be overridden
80     {
81         return opCatImpl(rhs);
82     }
83     Alt opBinary(string op)(Patt rhs) if (op == `|`) // template can't be overridden
84     {
85         return opAltImpl(rhs);
86     }
87 
88     Seq opCatImpl(Patt rhs)     // can be overridden
89     {
90         return seq(this, rhs); // TODO check if this and rhs is Seq
91     }
92     Alt opAltImpl(Patt rhs)     // can be overridden
93     {
94         return alt(this, rhs);  // TODO check if this and rhs is Alt
95     }
96 
97     final size_t at(const scope string haystack, size_t soff = 0) const
98     // TODO Activate this
99     /* out (hit) { */
100     /*     assert((!hit) || hit >= minLength); // TODO Is this needed? */
101     /* } */
102     /* do */
103     {
104         return atU(haystack.representation, soff);
105     }
106 
107     size_t atU(in ubyte[] haystack, size_t soff = 0) const
108     {
109         assert(false);
110     }
111 
112     /** Find $(D this) in String $(D haystack) at Offset $(D soff). */
113     final const(ubyte[]) findAt(const scope string haystack, size_t soff = 0) const
114     {
115         return findRawAt(haystack.representation, soff, []); // TODO this is ugly
116     }
117 
118     /** Find $(D this) in Raw Bytes $(D haystack) at Offset $(D soff). */
119     const(ubyte[]) findRawAt(in ubyte[] haystack, size_t soff = 0,
120                              in Patt[] enders = []) const
121     {
122         auto i = soff;
123         while (i < haystack.length) // while bytes left at i
124         {
125             if (haystack.length - i < minLength)  // and bytes left to find pattern
126             {
127                 return [];
128             }
129             const hit = atU(haystack, i);
130             if (hit != size_t.max) // hit at i
131             {
132                 return haystack[i..i + hit];
133             }
134             i++;
135         }
136         return [];
137     }
138 
139     @property:
140     size_t minLength() const { assert(false); } /// Returns: minimum possible instance length.
141     size_t maxLength() const { assert(false); } /// Returns: maximum possible instance length.
142 
143     bool isFixed() const { assert(false); } /// Returns: true if all possible instances have same length.
144     bool isConstant() const { return false; } /// Returns: true if all possible instances have same length.
145 
146     final bool isVariable() const { return !isConstant; }
147     const(ubyte[]) getConstant() const { return []; } /// Returns: data if literal otherwise empty array.
148 
149     /** Get All Literals that must match a given source $(D X) in order for $(D
150         this) to match $(D X) somewhere.
151     */
152     Lit[] mandatories() { assert(false); }
153 
154     /** Get Optional Literals that may match a given source $(D X) if $(D this)
155         matches $(D X) somewhere.
156     */
157     Lit[] optionals() { return mandatories; }
158 
159     protected Patt _parent; /// Parenting (Super) Pattern.
160     bool greedy = false; // Scan as far as possible if true
161 }
162 
163 /** Literal Pattern with Cached Binary Byte Histogram.
164  */
165 class Lit : Patt
166 {
167     @safe pure nothrow:
168 
169     this(string bytes_) { assert(!bytes_.empty); this(bytes_.representation); }
170     this(ubyte ch) { this._bytes ~= ch; }
171     this(ubyte[] bytes_) { this._bytes = bytes_; }
172     this(immutable ubyte[] bytes_) { this._bytes = bytes_.dup; }
173 
174     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
175     {
176         const l = _bytes.length;
177         return (soff + l <= haystack.length && // fits in haystack and
178                 _bytes[] == haystack[soff..soff + l]) ? l : size_t.max; // same contents
179     }
180 
181     override const(ubyte[]) findRawAt(in ubyte[] haystack, size_t soff = 0,
182                                       in Patt[] enders = []) const
183     {
184         return haystack[soff..$].find(_bytes); // reuse std.algorithm: find!
185     }
186 
187     @property:
188 
189     override size_t maxLength() const { return _bytes.length; }
190     override bool isFixed() const { return true; }
191     override bool isConstant() const { return true; }
192     override const(ubyte[]) getConstant() const { return _bytes; }
193 
194     @property auto ref bytes() const { return _bytes; }
195     private ubyte[] _bytes;
196     alias _bytes this;
197 
198     alias SinglesHist = StaticBitArray!(2^^ubyte.sizeof);
199 
200     /// Get (Cached) (Binary) Histogram over single elements contained in this $(D Lit).
201     SinglesHist singlesHist()
202     {
203         if (!_bytes.empty &&
204             _singlesHist.allZero)
205         {
206             foreach (b; _bytes)
207             {
208                 _singlesHist[b] = true;
209             }
210         }
211         return _singlesHist;
212     }
213     private SinglesHist _singlesHist;
214 
215     override Lit[] mandatories() { return [this]; }
216 }
217 
218 auto lit(Args...)(Args args) @safe pure nothrow { return new Lit(args); } // instantiator
219 
220 @safe pure nothrow unittest
221 {
222     immutable ab = `ab`;
223     assert(lit('b').at(`ab`, 1) == 1);
224     const a = lit('a');
225 
226     const ac = lit(`ac`);
227     assert(ac.match(`ac`));
228     assert(ac.match(`ac`).length == 2);
229     assert(!ac.match(`ca`));
230     assert(ac.match(`ca`) == []);
231 
232     assert(a.isFixed);
233     assert(a.isConstant);
234     assert(a.at(ab) == 1);
235     assert(lit(ab).at(`a`) == size_t.max);
236     assert(lit(ab).at(`b`) == size_t.max);
237 
238     assert(a.findAt(`cba`) == cast(immutable ubyte[])`a`);
239     assert(a.findAt(`ba`) == cast(immutable ubyte[])`a`);
240     assert(a.findAt(`a`) == cast(immutable ubyte[])`a`);
241     assert(a.findAt(``) == []);
242     assert(a.findAt(`b`) == []);
243     assert(ac.findAt(`__ac`) == cast(immutable ubyte[])`ac`);
244     assert(a.findAt(`b`).length == 0);
245 
246     auto xyz = lit(`xyz`);
247 }
248 
249 @safe pure nothrow unittest
250 {
251     auto ac = lit(`ac`);
252     assert(ac.mandatories == [ac]);
253     assert(ac.optionals == [ac]);
254 }
255 
256 /** Word/Symbol Acronym Pattern.
257  */
258 class Acronym : Patt
259 {
260     @safe pure nothrow:
261 
262     this(string bytes_, FindContext ctx = FindContext.inSymbol)
263     {
264         assert(!bytes_.empty);
265         this(bytes_.representation, ctx);
266     }
267 
268     this(ubyte ch) { this._acros ~= ch; }
269     this(ubyte[] bytes_, FindContext ctx = FindContext.inSymbol)
270     {
271         this._acros = bytes_;
272         this._ctx = ctx;
273     }
274     this(immutable ubyte[] bytes_, FindContext ctx = FindContext.inSymbol)
275     {
276         this._acros = bytes_.dup;
277         this._ctx = ctx;
278     }
279 
280     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
281     {
282         auto offs = new size_t[_acros.length]; // hit offsets
283         size_t a = 0;         // acronym index
284         foreach(s, ub; haystack[soff..$])  // for each element in source
285         {
286             import std.ascii: isAlpha;
287 
288             // Check context
289             final switch (_ctx)
290             {
291             case FindContext.inWord:
292             case FindContext.asWord:
293                 if (!ub.isAlpha) { return size_t.max; } break;
294             case FindContext.inSymbol:
295             case FindContext.asSymbol:
296                 if (!ub.isAlpha && ub != '_') { return size_t.max; } break;
297             }
298 
299             if (_acros[a] == ub)
300             {
301                 offs[a] = s + soff; // store hit offset
302                 a++; // advance acronym
303                 if (a == _acros.length) // if complete acronym found
304                 {
305                     return s + 1;             // return its length
306                 }
307             }
308         }
309         return size_t.max; // no hit
310     }
311 
312     template Tuple(E...) { alias Tuple = E; }
313 
314     override const(ubyte[]) findRawAt(in ubyte[] haystack, size_t soff = 0,
315                                       in Patt[] enders = []) const
316     {
317         import std..string: CaseSensitive;
318         return haystack.findAcronymAt(_acros, _ctx, CaseSensitive.yes, soff)[0];
319     }
320 
321     @property:
322     override size_t minLength() const { return _acros.length; }
323     override size_t maxLength() const { return size_t.max; }
324     override bool isFixed() const { return false; }
325     override bool isConstant() const { return false; }
326 
327 private:
328     ubyte[] _acros;
329     FindContext _ctx;
330 }
331 
332 @safe pure nothrow
333 {
334     auto inwac(Args...)(Args args) { return new Acronym(args, FindContext.inWord); } // word acronym
335     auto insac(Args...)(Args args) { return new Acronym(args, FindContext.inSymbol); } // symbol acronym
336     auto aswac(Args...)(Args args) { return new Acronym(args, FindContext.asWord); } // word acronym
337     auto assac(Args...)(Args args) { return new Acronym(args, FindContext.asSymbol); } // symbol acronym
338 }
339 
340 @safe pure nothrow unittest
341 {
342     assert(inwac(`a`).at(`a`) == 1);
343     assert(inwac(`ab`).at(`ab`) == 2);
344     assert(inwac(`ab`).at(`a`) == size_t.max);
345     assert(inwac(`abc`).at(`abc`) == 3);
346     assert(inwac(`abc`).at(`aabbcc`) == 5);
347     assert(inwac(`abc`).at(`aaaabbcc`) == 7);
348     assert(inwac(`fpn`).at(`fopen`) == 5);
349 }
350 
351 /** Any Byte.
352  */
353 class Any : Patt
354 {
355     @safe pure nothrow:
356     this() {}
357 
358     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
359     {
360         return soff < haystack.length ? 1 : size_t.max;
361     }
362 
363     @property:
364     override size_t maxLength() const { return 1; }
365     override bool isFixed() const { return true; }
366     override bool isConstant() const { return false; }
367 
368     override Lit[] mandatories() { return []; }
369     override Lit[] optionals()
370     {
371         import std.range: iota;
372         return iota(0, 256).map!(n => (cast(ubyte)n).lit).array;
373     }
374 }
375 
376 auto any(Args...)(Args args) { return new Any(args); } // instantiator
377 
378 /** Abstract Super Pattern.
379  */
380 abstract class SPatt : Patt
381 {
382     @safe pure nothrow:
383 
384     this(Patt[] subs_) { this._subs = subs_; }
385 
386     this(Args...)(Args subs_)
387     {
388         foreach (sub; subs_)
389         {
390             alias Sub = typeof(sub);
391 
392             // TODO functionize to patternFromBuiltinType() or to!Patt
393             static if (is(Sub == string) ||
394                        is(Sub == char))
395             {
396                 _subs ~= new Lit(sub);
397             }
398             else
399             {
400                 _subs ~= sub;
401             }
402             sub._parent = this;
403         }
404     }
405 
406     protected Patt[] _subs;
407 }
408 
409 /** Sequence of Patterns.
410  */
411 class Seq : SPatt
412 {
413     @safe pure nothrow:
414 
415     this(Patt[] subs_) { super(subs_); }
416     this(Args...)(Args subs_) { super(subs_); }
417 
418     @property auto ref inout (Patt[]) elms() inout { return super._subs; }
419 
420     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
421     {
422         assert(!elms.empty); // TODO Move to in contract?
423         const c = getConstant;
424         if (!c.empty)
425         {
426             return (soff + c.length <= haystack.length &&   // if equal size and
427                     c[] == haystack[soff..soff + c.length]); // equal contents
428         }
429         size_t sum = 0;
430         size_t off = soff;
431         foreach (ix, sub; elms) // TODO Reuse std.algorithm instead?
432         {
433             size_t hit = sub.atU(haystack, off);
434             if (hit == size_t.max) { sum = hit; break; } // if any miss skip
435             sum += hit;
436             off += hit;
437         }
438         return sum;
439     }
440 
441     @property:
442     override size_t maxLength() const { assert(false); }
443     override bool isFixed() const { return _subs.all!(a => a.isFixed); }
444     override bool isConstant() const { return _subs.all!(a => a.isConstant); }
445     override const(ubyte[]) getConstant() const { return []; }
446 
447     override Lit[] mandatories()
448     {
449         auto x = _subs.map!(patt => patt.mandatories);
450         return x.joiner.array;
451     }
452 
453     override Lit[] optionals()
454     {
455         auto x = _subs.map!(patt => patt.optionals);
456         return x.joiner.array;
457     }
458 }
459 
460 auto seq(Args...)(Args args) @safe pure nothrow { return new Seq(args); } // instantiator
461 
462 @safe pure nothrow unittest
463 {
464     const s = seq(`al.`.lit,
465                   `pha`.lit);
466     const t = `al`.lit ~ `pha`.lit;
467     assert(s !is t);
468 
469     immutable haystack = `alpha`;
470     assert(s.isFixed);
471     assert(s.isConstant);
472     assert(s.at(haystack));
473     const al = seq(`a`.lit,
474                    `l`.lit);
475     assert(al.at(`a`) == size_t.max);
476 }
477 
478 @safe pure nothrow unittest
479 {
480     auto a = `aa.`.lit;
481     auto b = `bb.`.lit;
482     auto c = `cc.`.lit;
483     auto d = `dd.`.lit;
484     auto s = seq(a.opt, b,
485                  c.opt, d);
486     assert(equal(s.mandatories, [b, d]));
487     assert(equal(s.optionals, [a, b, c, d]));
488 }
489 
490 /** Alternative of Patterns in $(D ALTS).
491  */
492 class Alt : SPatt
493 {
494     @safe pure nothrow:
495 
496     this(Patt[] subs_) { super(subs_); }
497     this(Args...)(Args subs_) { super(subs_); }
498 
499     size_t atIx(const scope string haystack, size_t soff, out size_t alt_hix) const
500     {
501         return atU(haystack.representation, soff, alt_hix);
502     }
503 
504     void opOpAssign(string s : "~")(Patt sub)
505     {
506         super._subs ~= sub;
507     }
508 
509     @property inout(Patt[]) alts() inout { return super._subs; }
510 
511     /** Get Length of hit at index soff in haystack or size_t.max if none.
512      */
513     size_t atU(in ubyte[] haystack, size_t soff, out size_t alt_hix) const
514     {
515         assert(!alts.empty);    // TODO Move to in contract?
516         size_t hit = 0;
517         size_t off = soff;
518         foreach (ix, sub; alts)  // TODO Reuse std.algorithm instead?
519         {
520             hit = sub.atU(haystack[off..$]);                     // match alternative
521             if (hit != size_t.max) { alt_hix = ix; break; } // if any hit were done
522         }
523         return hit;
524     }
525 
526     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
527     {
528         size_t alt_hix;
529         return atU(haystack, soff, alt_hix);
530     }
531 
532     /** Find $(D this) in $(D haystack) at Offset $(D soff).
533     */
534     override const(ubyte[]) findRawAt(in ubyte[] haystack, size_t soff = 0,
535                                       in Patt[] enders = []) const
536     {
537         assert(!alts.empty);    // TODO Move to in contract?
538 
539         import nxt.dbgio;
540 
541         switch (alts.length)
542         {
543             case 1:
544                 const a0 = alts[0].getConstant;
545                 if (!a0.empty)
546                 {
547                     auto hit = haystack[soff..$].find(a0); // Use: second argument to return alt_hix
548                     return hit;
549                 }
550                 else
551                 {
552                     return alts[0].findRawAt(haystack, soff, enders); // recurse to it
553                 }
554             case 2:
555                 const a0 = alts[0].getConstant;
556                 const a1 = alts[1].getConstant;
557                 if (!a0.empty &&
558                     !a1.empty)
559                 {
560                     auto hit = haystack[soff..$].find(a0, a1); // Use: second argument to return alt_hix
561                     return hit[0];
562                 }
563                 break;
564             case 3:
565                 const a0 = alts[0].getConstant;
566                 const a1 = alts[1].getConstant;
567                 const a2 = alts[2].getConstant;
568                 if (!a0.empty &&
569                     !a1.empty &&
570                     !a2.empty)
571                 {
572                     auto hit = haystack[soff..$].find(a0, a1, a2); // Use: second argument to return alt_hix
573                     return hit[0];
574                 }
575                 break;
576             case 4:
577                 const a0 = alts[0].getConstant;
578                 const a1 = alts[1].getConstant;
579                 const a2 = alts[2].getConstant;
580                 const a3 = alts[3].getConstant;
581                 if (!a0.empty &&
582                     !a1.empty &&
583                     !a2.empty &&
584                     !a3.empty)
585                 {
586                     auto hit = haystack[soff..$].find(a0, a1, a2, a3); // Use: second argument to return alt_hix
587                     return hit[0];
588                 }
589                 break;
590             case 5:
591                 const a0 = alts[0].getConstant;
592                 const a1 = alts[1].getConstant;
593                 const a2 = alts[2].getConstant;
594                 const a3 = alts[3].getConstant;
595                 const a4 = alts[4].getConstant;
596                 if (!a0.empty &&
597                     !a1.empty &&
598                     !a2.empty &&
599                     !a3.empty &&
600                     !a4.empty)
601                 {
602                     auto hit = haystack[soff..$].find(a0, a1, a2, a3, a4); // Use: second argument to return alt_hix
603                     return hit[0];
604                 }
605                 break;
606             default:
607                 break;
608         }
609 
610         return super.findRawAt(haystack, soff, enders); // revert to base case
611     }
612 
613     @property:
614     override size_t minLength() const { return reduce!min(size_t.max,
615                                                           _subs.map!(a => a.minLength)); }
616     override size_t maxLength() const { return reduce!max(size_t.min,
617                                                           _subs.map!(a => a.maxLength)); }
618     override bool isFixed() const
619     {
620         // TODO Merge these loops using tuple algorithm.
621         auto mins = _subs.map!(a => a.minLength);
622         auto maxs = _subs.map!(a => a.maxLength);
623         import nxt.predicates: allEqual;
624         return (mins.allEqual &&
625                 maxs.allEqual);
626     }
627     override bool isConstant() const
628     {
629         if (_subs.length == 0)
630         {
631             return true;
632         }
633         else if (_subs.length == 1)
634         {
635             import std.range: front;
636             return _subs.front.isConstant;
637         }
638         else
639         {
640             return false;       // TODO Maybe handle case when _subs are different.
641         }
642     }
643 }
644 
645 auto alt(Args...)(Args args) @safe pure nothrow { return new Alt(args); } // instantiator
646 
647 @safe pure nothrow unittest
648 {
649     immutable a_b = alt(`a`.lit,
650                         `b`.lit);
651 
652     immutable a__b = (`a`.lit |
653                       `b`.lit);
654 
655     assert(a_b.isFixed);
656     assert(!a_b.isConstant);
657     assert(a_b.at(`a`));
658     assert(a_b.at(`b`));
659     assert(a_b.at(`c`) == size_t.max);
660 
661     size_t hix = size_t.max;
662     a_b.atIx(`a`, 0, hix); assert(hix == 0);
663     a_b.atIx(`b`, 0, hix); assert(hix == 1);
664 
665     /* assert(alt.at(`a`) == size_t.max); */
666     /* assert(alt.at(``) == size_t.max); */
667 
668     immutable a = alt(lit(`a`));
669     immutable aa = alt(lit(`aa`));
670     assert(aa.isConstant);
671 
672     immutable aa_bb = alt(lit(`aa`),
673                           lit(`bb`));
674     assert(aa_bb.isFixed);
675     assert(aa_bb.minLength == 2);
676     assert(aa_bb.maxLength == 2);
677 
678     immutable a_bb = alt(lit(`a`),
679                          lit(`bb`));
680     assert(!a_bb.isFixed);
681     assert(a_bb.minLength == 1);
682     assert(a_bb.maxLength == 2);
683 
684     const string _aa = `_aa`;
685     assert(aa_bb.findAt(_aa) == cast(immutable ubyte[])`aa`);
686     assert(&aa_bb.findAt(_aa)[0] - &(cast(immutable ubyte[])_aa)[0] == 1);
687 
688     const string _bb = `_bb`;
689     assert(aa_bb.findAt(_bb) == cast(immutable ubyte[])`bb`);
690     assert(&aa_bb.findAt(_bb)[0] - &(cast(immutable ubyte[])_bb)[0] == 1);
691 
692     assert(a.findAt(`b`) == []);
693     assert(aa.findAt(`cc`) == []);
694     assert(aa_bb.findAt(`cc`) == []);
695     assert(aa_bb.findAt(``) == []);
696 }
697 
698 @safe pure nothrow unittest
699 {
700     auto a_b = alt(`a`.lit);
701     a_b ~= `b`.lit;
702 
703     assert(a_b.isFixed);
704     assert(!a_b.isConstant);
705     assert(a_b.at(`a`));
706     assert(a_b.at(`b`));
707     assert(a_b.at(`c`) == size_t.max);
708 
709     size_t hix = size_t.max;
710     a_b.atIx(`a`, 0, hix); assert(hix == 0);
711     a_b.atIx(`b`, 0, hix); assert(hix == 1);
712 }
713 
714 class Space : Patt
715 {
716     @safe pure nothrow:
717 
718     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
719     {
720         import std.ascii: isWhite;
721         return soff < haystack.length && isWhite(haystack[soff]) ? 1 : size_t.max;
722     }
723 
724     @property:
725     override size_t maxLength() const { return 1; }
726     override bool isFixed() const { return true; }
727     override bool isConstant() const { return false; }
728 }
729 
730 auto ws() @safe pure nothrow { return new Space(); } // instantiator
731 
732 @safe pure nothrow unittest
733 {
734     assert(ws.at(` `) == 1);
735     assert(ws.at("\t") == 1);
736     assert(ws.at("\n") == 1);
737 }
738 
739 /** Abstract Singleton Super Pattern.
740  */
741 abstract class SPatt1 : Patt
742 {
743     @safe pure nothrow:
744 
745     this(Patt sub)
746     {
747         this.sub = sub;
748         sub._parent = this;
749     }
750     protected Patt sub;
751 }
752 
753 /** Optional Sub Pattern $(D count) times.
754  */
755 class Opt : SPatt1
756 {
757     @safe pure nothrow:
758 
759     this(Patt sub) { super(sub); }
760 
761     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
762     {
763         assert(soff <= haystack.length); // include equality because haystack might be empty and size zero
764         const hit = sub.atU(haystack[soff..$]);
765         return hit == size_t.max ? 0 : hit;
766     }
767 
768     @property:
769     override size_t minLength() const { return 0; }
770     override size_t maxLength() const { return sub.maxLength; }
771     override bool isFixed() const { return false; }
772     override bool isConstant() const { return false; }
773 
774     override Lit[] mandatories() { return []; }
775     override Lit[] optionals() { return sub.optionals; }
776 }
777 
778 auto opt(Args...)(Args args) { return new Opt(args); } // optional
779 
780 @safe pure nothrow unittest
781 {
782     assert(`a`.lit.opt.at(`b`) == 0);
783     assert(`a`.lit.opt.at(`a`) == 1);
784 }
785 
786 /** Repetition Sub Pattern $(D count) times.
787  */
788 class Rep : SPatt1
789 {
790     @safe pure nothrow:
791 
792     this(Patt sub, size_t count)
793     in
794     {
795         assert(count >= 2);
796     }
797     do
798     {
799         super(sub);
800         this.countReq = count;
801         this.countOpt = 0; // fixed length repetion
802     }
803 
804     this(Patt sub, size_t countMin, size_t countMax)
805     in
806     {
807         assert(countMax >= 2);
808         assert(countMin <= countMax);
809     }
810     do
811     {
812         super(sub);
813         this.countReq = countMin;
814         this.countOpt = countMax - countMin;
815     }
816 
817     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
818     {
819         size_t sum = 0;
820         size_t off = soff;
821         /* mandatory */
822         foreach (ix; 0..countReq)  // TODO Reuse std.algorithm instead?
823         {
824             size_t hit = sub.atU(haystack[off..$]);
825             if (hit == size_t.max) { return hit; } // if any miss skip
826             off += hit;
827             sum += hit;
828         }
829         /* optional part */
830         foreach (ix; countReq..countReq + countOpt) // TODO Reuse std.algorithm instead?
831         {
832             size_t hit = sub.atU(haystack[off..$]);
833             if (hit == size_t.max) { break; } // if any miss just break
834             off += hit;
835             sum += hit;
836         }
837         return sum;
838     }
839 
840     @property:
841     override size_t minLength() const { return countReq*sub.maxLength; }
842     override size_t maxLength() const { return (countReq + countOpt)*sub.maxLength; }
843     override bool isFixed() const { return minLength == maxLength && sub.isFixed; }
844     override bool isConstant() const { return minLength == maxLength && sub.isConstant; }
845 
846     override Lit[] mandatories() { return sub.mandatories; }
847     override Lit[] optionals() { return sub.optionals; }
848 
849     // invariant { assert(countReq); }
850     size_t countReq; // Required.
851     size_t countOpt; // Optional.
852 }
853 
854 auto rep(Args...)(Args args) { return new Rep(args); } // repetition
855 auto zom(Args...)(Args args) { return new Rep(args, 0, size_t.max); } // zero or more
856 auto oom(Args...)(Args args) { return new Rep(args, 1, size_t.max); } // one or more
857 
858 @safe pure nothrow unittest
859 {
860     auto l = 'a'.lit;
861 
862     const l5 = l.rep(5);
863     assert(l5.isConstant);
864     assert(l5.at(`aaaa`) == size_t.max);
865     assert(l5.at(`aaaaa`));
866     assert(l5.at(`aaaaaaa`));
867     assert(l5.isFixed);
868     assert(l5.maxLength == 5);
869 
870     const l23 = l.rep(2, 3);
871     assert(l23.at(`a`) == size_t.max);
872     assert(l23.at(`aa`) == 2);
873     assert(l23.at(`aaa`) == 3);
874     assert(l23.at(`aaaa`) == 3);
875     assert(!l23.isConstant);
876 }
877 
878 @safe pure nothrow unittest
879 {
880     auto l = 'a'.lit;
881     auto l5 = l.rep(5);
882     assert(l5.mandatories == [l]);
883     assert(l5.optionals == [l]);
884 }
885 
886 @safe pure nothrow unittest
887 {
888     auto l = 'a'.lit;
889     auto l5 = l.opt.rep(5);
890     assert(l5.mandatories == []);
891     assert(l5.optionals == [l]);
892 }
893 
894 class Ctx : Patt
895 {
896     enum Type
897     {
898         bob, /// Beginning Of \em Block/Name/File/String. @b Emacs: `\``
899         eob, /// End       Of \em Block/Name/File/String. @b Emacs: `\'`
900 
901         bol,            /// Beginning Of \em Line. @b Emacs: `^`
902         eol,            /// End       Of \em Line. @b Emacs: `$`
903 
904         bos,            /// Beginning Of \em Symbol. @b Emacs: `\_<`
905         eos,            /// End       Of \em Symbol. @b Emacs: `\_>`
906 
907         bow,            /// Beginning Of \em Word. @b Emacs: `\<`
908         eow,            /// End       Of \em Word. @b Emacs: `\>`
909     }
910 
911     @safe pure nothrow:
912 
913     this(Type type) { this.type = type; }
914 
915     override size_t atU(in ubyte[] haystack, size_t soff = 0) const
916     {
917         assert(soff <= haystack.length); // include equality because haystack might be empty and size zero
918         bool ok = false;
919         import std.ascii : isAlphaNum/* , newline */;
920         final switch (type)
921         {
922             /* buffer */
923         case Type.bob: ok = (soff == 0); break;
924         case Type.eob: ok = (soff == haystack.length); break;
925 
926             /* line */
927         case Type.bol: ok = (soff == 0          || (haystack[soff - 1] == 0x0d ||
928                                                    haystack[soff - 1] == 0x0a)); break;
929         case Type.eol: ok = (soff == haystack.length || (haystack[soff    ] == 0x0d ||
930                                                    haystack[soff    ] == 0x0a)); break;
931 
932             /* symbol */
933         case Type.bos: ok = ((soff == 0         || (!haystack[soff - 1].isAlphaNum &&
934                                                     haystack[soff - 1] != '_')) && // TODO Make '_' language-dependent
935                              (soff < haystack.length &&  haystack[soff].isAlphaNum)) ; break;
936         case Type.eos: ok = ((soff == haystack.length || (!haystack[soff].isAlphaNum &&
937                                                           haystack[soff] != '_')) && // TODO Make '_' language-dependent
938                              (soff >= 1          &&  haystack[soff - 1].isAlphaNum)) ; break;
939 
940             /* word */
941         case Type.bow: ok = ((soff == 0         || !haystack[soff - 1].isAlphaNum) &&
942                              (soff < haystack.length &&  haystack[soff].isAlphaNum)) ; break;
943         case Type.eow: ok = ((soff == haystack.length || !haystack[soff].isAlphaNum) &&
944                              (soff >= 1          &&  haystack[soff - 1].isAlphaNum)) ; break;
945         }
946         return ok ? 0 : size_t.max;
947     }
948 
949     @property:
950     override size_t maxLength() const { return 0; }
951     override bool isFixed() const { return true; }
952     override bool isConstant() const { return true; }
953 
954     protected Type type;
955 }
956 
957 Ctx bob(Args...)(Args args) { return new Ctx(args, Ctx.Type.bob); }
958 Ctx eob(Args...)(Args args) { return new Ctx(args, Ctx.Type.eob); }
959 Ctx bol(Args...)(Args args) { return new Ctx(args, Ctx.Type.bol); }
960 Ctx eol(Args...)(Args args) { return new Ctx(args, Ctx.Type.eol); }
961 Ctx bos(Args...)(Args args) { return new Ctx(args, Ctx.Type.bos); }
962 Ctx eos(Args...)(Args args) { return new Ctx(args, Ctx.Type.eos); }
963 Ctx bow(Args...)(Args args) { return new Ctx(args, Ctx.Type.bow); }
964 Ctx eow(Args...)(Args args) { return new Ctx(args, Ctx.Type.eow); }
965 Seq buf(Args...)(Args args) { return seq(bob, args, eob); }
966 Seq line(Args...)(Args args) { return seq(bol, args, eol); }
967 Seq sym(Args...)(Args args) { return seq(bos, args, eos); }
968 Seq word(Args...)(Args args) { return seq(bow, args, eow); }
969 
970 @safe pure nothrow unittest
971 {
972     const bob_ = bob;
973     const eob_ = eob;
974     assert(bob_.at(`ab`) == 0);
975     assert(eob_.at(`ab`, 2) == 0);
976 
977     const bol_ = bol;
978     assert(bol_.at(`ab`) == 0);
979     assert(bol_.at("a\nb", 2) == 0);
980     assert(bol_.at("a\nb", 1) == size_t.max);
981 
982     const eol_ = eol;
983     assert(eol_.at(`ab`, 2) == 0);
984     assert(eol_.at("a\nb", 1) == 0);
985     assert(eol_.at("a\nb", 2) == size_t.max);
986 
987     const bos_ = bos;
988     const eos_ = eos;
989     assert(bos_.at(`ab`) == 0);
990     assert(bos_.at(` ab`) == size_t.max);
991     assert(eos_.at(`ab`, 2) == 0);
992     assert(eos_.at(`a_b `, 1) == size_t.max);
993     assert(eos_.at(`ab `, 2) == 0);
994 
995     const bow_ = bow;
996     const eow_ = eow;
997 
998     assert(bow_.at(`ab`) == 0);
999     assert(bow_.at(` ab`) == size_t.max);
1000 
1001     assert(eow_.at(`ab`, 2) == 0);
1002     assert(eow_.at(`ab `, 0) == size_t.max);
1003 
1004     assert(bow_.at(` ab `, 1) == 0);
1005     assert(bow_.at(` ab `, 0) == size_t.max);
1006 
1007     assert(eow_.at(` ab `, 3) == 0);
1008     assert(eow_.at(` ab `, 4) == size_t.max);
1009 
1010     auto l = lit(`ab`);
1011     auto w = word(l);
1012     assert(w.at(`ab`) == 2);
1013     assert(w.at(`ab_c`) == 2);
1014 
1015     auto s = sym(l);
1016     assert(s.at(`ab`) == 2);
1017     assert(s.at(`ab_c`) == size_t.max);
1018 
1019     assert(bob_.findAt(`a`) == []);
1020     assert(bob_.findAt(`a`).ptr != null);
1021     assert(eob_.findAt(`a`) == []);
1022 
1023     assert(bol_.findAt(`a`) == []);
1024     assert(bol_.findAt(`a`).ptr != null);
1025     assert(eol_.findAt(`a`) == []);
1026 
1027     assert(bow_.findAt(`a`) == []);
1028     assert(bow_.findAt(`a`).ptr != null);
1029     assert(eow_.findAt(`a`) == []);
1030 
1031     assert(bos_.findAt(`a`) == []);
1032     assert(bos_.findAt(`a`).ptr != null);
1033     assert(eos_.findAt(`a`) == []);
1034     // TODO This fails assert(eos_.findAt(`a`).ptr != null);
1035 }
1036 
1037 /** Keyword $(D arg). */
1038 Seq kwd(Arg)(Arg arg) { return seq(bow, arg, eow); }
1039 
1040 @safe pure nothrow unittest
1041 {
1042     const str = `int`;
1043     auto x = str.lit.kwd;
1044 
1045     assert(x.at(str, 0));
1046     /* TODO assert(!x.at(str, 1)); */
1047 
1048     assert(x.at(` ` ~ str, 1));
1049     /* TODO assert(!x.at(` int`, 0)); */
1050 }
1051 
1052 /** Pattern Paired with Prefix and Suffix.
1053  */
1054 class Clause : SPatt1
1055 {
1056     @safe pure nothrow:
1057 
1058     this(Patt prefix_,
1059          Patt suffix_,
1060          Patt sub)
1061     {
1062         super(sub);
1063         this.prefix = prefix_;
1064         this.suffix = suffix_;
1065     }
1066 
1067     override const(ubyte[]) findRawAt(in ubyte[] haystack, size_t soff = 0,
1068                                       in Patt[] enders = []) const
1069     {
1070         return sub.findRawAt(haystack, soff, enders ~ [suffix]);
1071     }
1072 
1073     Patt prefix, suffix;
1074 }
1075 
1076 Clause paired(Args...)(Patt prefix, Patt suffix, Args args) { return new Clause(prefix, suffix, args); }
1077 Clause parend(Args...)(Args args) { return new Clause(lit('('), lit(')'), args); }
1078 Clause hooked(Args...)(Args args) { return new Clause(lit('['), lit(']'), args); }
1079 Clause braced(Args...)(Args args) { return new Clause(lit('{'), lit('}'), args); }
1080 
1081 import nxt.assert_ex;
1082 
1083 @safe pure nothrow unittest
1084 {
1085     /* auto p = `[alpha]`.lit.parend; */
1086     /* assert(p.at(`([alpha])`) == 7); */
1087 
1088     /* auto h = `[alpha]`.lit.hooked; */
1089     /* assert(h.at(`[[alpha]]`) == 7); */
1090 
1091     /* auto b = `[alpha]`.lit.braced; */
1092     /* assert(b.at(`{[alpha]}`) == 7); */
1093 
1094     /* auto pb = `[alpha]`.lit.parend; */
1095 }
1096 
1097 /** Create Matcher for a UNIX Shell $(LUCKY Shebang) Pattern.
1098     Example: #!/bin/env rdmd
1099     See_Also: https://en.wikipedia.org/wiki/Shebang_(Unix)
1100  */
1101 auto ref shebangLine(Patt interpreter) @safe pure nothrow
1102 {
1103     return seq(`#!`.lit,
1104                `/usr`.lit.opt,
1105                `/bin/env`.lit.opt,
1106                ws.oom,
1107                interpreter);
1108 }
1109 
1110 @safe pure nothrow unittest
1111 {
1112     assert(`rdmd`.lit.shebangLine
1113                  .at(`#!/bin/env rdmd`) == 15);
1114     assert(`rdmd`.lit.shebangLine
1115                  .at(`#!/usr/bin/env rdmd`) == 19);
1116     auto rgdmd = alt(`rdmd`.lit,
1117                      `gdmd`.lit);
1118     assert(rgdmd.shebangLine
1119                 .at(`#!/usr/bin/env rdmd-dev`) == 19);
1120     assert(rgdmd.shebangLine
1121                 .at(`#!/usr/bin/env gdmd`) == 19);
1122 }