libphobos/src/std/regex/internal/thompson.d

   1 //Written in the D programming language
   2 /*
   3     Implementation of Thompson NFA std.regex engine.
   4     Key point is evaluation of all possible threads (state) at each step
   5     in a breadth-first manner, thereby geting some nice properties:
   6         - looking at each character only once
   7         - merging of equivalent threads, that gives matching process linear time complexity
   8 */
   9 module std.regex.internal.thompson;
  10
  11 package(std.regex):
  12
  13 import std.range.primitives;
  14 import std.regex.internal.ir;
  15
  16 //State of VM thread
  17 struct Thread(DataIndex)
  18 {
  19     Thread* next;    //intrusive linked list
  20     uint pc;
  21     uint counter;    //loop counter
  22     uint uopCounter; //counts micro operations inside one macro instruction (e.g. BackRef)
  23     Group!DataIndex[1] matches;
  24 }
  25
  26 //head-tail singly-linked list
  27 struct ThreadList(DataIndex)
  28 {
  29     Thread!DataIndex* tip = null, toe = null;
  30     //add new thread to the start of list
  31     void insertFront(Thread!DataIndex* t)
  32     {
  33         if (tip)
  34         {
  35             t.next = tip;
  36             tip = t;
  37         }
  38         else
  39         {
  40             t.next = null;
  41             tip = toe = t;
  42         }
  43     }
  44     //add new thread to the end of list
  45     void insertBack(Thread!DataIndex* t)
  46     {
  47         if (toe)
  48         {
  49             toe.next = t;
  50             toe = t;
  51         }
  52         else
  53             tip = toe = t;
  54         toe.next = null;
  55     }
  56     //move head element out of list
  57     Thread!DataIndex* fetch()
  58     {
  59         auto t = tip;
  60         if (tip == toe)
  61             tip = toe = null;
  62         else
  63             tip = tip.next;
  64         return t;
  65     }
  66     //non-destructive iteration of ThreadList
  67     struct ThreadRange
  68     {
  69         const(Thread!DataIndex)* ct;
  70         this(ThreadList tlist){ ct = tlist.tip; }
  71         @property bool empty(){ return ct is null; }
  72         @property const(Thread!DataIndex)* front(){ return ct; }
  73         void popFront()
  74         {
  75             assert(ct);
  76             ct = ct.next;
  77         }
  78     }
  79     @property bool empty()
  80     {
  81         return tip == null;
  82     }
  83     ThreadRange opSlice()
  84     {
  85         return ThreadRange(this);
  86     }
  87 }
  88
  89 template ThompsonOps(E, S, bool withInput:true)
  90 {
  91 @trusted:
  92     static bool op(IR code:IR.End)(E e, S* state)
  93     {
  94         with(e) with(state)
  95         {
  96             finish(t, matches, re.ir[t.pc].data);
  97             //fix endpoint of the whole match
  98             matches[0].end = index;
  99             recycle(t);
 100             //cut off low priority threads
 101             recycle(clist);
 102             recycle(worklist);
 103             debug(std_regex_matcher) writeln("Finished thread ", matches);
 104             return false; // no more state to eval
 105         }
 106     }
 107
 108     static bool op(IR code:IR.Wordboundary)(E e, S* state)
 109     {
 110         with(e) with(state)
 111         {
 112             dchar back;
 113             DataIndex bi;
 114             //at start & end of input
 115             if (atStart && wordMatcher[front])
 116             {
 117                 t.pc += IRL!(IR.Wordboundary);
 118                 return true;
 119             }
 120             else if (atEnd && s.loopBack(index).nextChar(back, bi)
 121                     && wordMatcher[back])
 122             {
 123                 t.pc += IRL!(IR.Wordboundary);
 124                 return true;
 125             }
 126             else if (s.loopBack(index).nextChar(back, bi))
 127             {
 128                 bool af = wordMatcher[front];
 129                 bool ab = wordMatcher[back];
 130                 if (af ^ ab)
 131                 {
 132                     t.pc += IRL!(IR.Wordboundary);
 133                     return true;
 134                 }
 135             }
 136             return popState(e);
 137         }
 138     }
 139
 140     static bool op(IR code:IR.Notwordboundary)(E e, S* state)
 141     {
 142         with(e) with(state)
 143         {
 144             dchar back;
 145             DataIndex bi;
 146             //at start & end of input
 147             if (atStart && wordMatcher[front])
 148             {
 149                 return popState(e);
 150             }
 151             else if (atEnd && s.loopBack(index).nextChar(back, bi)
 152                     && wordMatcher[back])
 153             {
 154                 return popState(e);
 155             }
 156             else if (s.loopBack(index).nextChar(back, bi))
 157             {
 158                 bool af = wordMatcher[front];
 159                 bool ab = wordMatcher[back]  != 0;
 160                 if (af ^ ab)
 161                 {
 162                     return popState(e);
 163                 }
 164             }
 165             t.pc += IRL!(IR.Notwordboundary);
 166         }
 167         return true;
 168     }
 169
 170     static bool op(IR code:IR.Bof)(E e, S* state)
 171     {
 172         with(e) with(state)
 173         {
 174             if (atStart)
 175             {
 176                 t.pc += IRL!(IR.Bof);
 177                 return true;
 178             }
 179             else
 180             {
 181                 return popState(e);
 182             }
 183         }
 184     }
 185
 186     static bool op(IR code:IR.Bol)(E e, S* state)
 187     {
 188         with(e) with(state)
 189         {
 190             dchar back;
 191             DataIndex bi;
 192             if (atStart
 193                 ||(s.loopBack(index).nextChar(back,bi)
 194                 && startOfLine(back, front == '\n')))
 195             {
 196                 t.pc += IRL!(IR.Bol);
 197                 return true;
 198             }
 199             else
 200             {
 201                 return popState(e);
 202             }
 203         }
 204     }
 205
 206     static bool op(IR code:IR.Eof)(E e, S* state)
 207     {
 208         with(e) with(state)
 209         {
 210             if (atEnd)
 211             {
 212                 t.pc += IRL!(IR.Eol);
 213                 return true;
 214             }
 215             else
 216             {
 217                 return popState(e);
 218             }
 219         }
 220     }
 221
 222     static bool op(IR code:IR.Eol)(E e, S* state)
 223     {
 224         with(e) with(state)
 225         {
 226             dchar back;
 227             DataIndex bi;
 228             //no matching inside \r\n
 229             if (atEnd || (endOfLine(front, s.loopBack(index).nextChar(back, bi)
 230                     && back == '\r')))
 231             {
 232                 t.pc += IRL!(IR.Eol);
 233                 return true;
 234             }
 235             else
 236             {
 237                 return popState(e);
 238             }
 239
 240         }
 241     }
 242
 243     static bool op(IR code:IR.InfiniteStart)(E e, S* state)
 244     {
 245         with(e) with(state)
 246             t.pc += re.ir[t.pc].data + IRL!(IR.InfiniteStart);
 247         return op!(IR.InfiniteEnd)(e,state);
 248     }
 249
 250     static bool op(IR code:IR.InfiniteBloomStart)(E e, S* state)
 251     {
 252         with(e) with(state)
 253             t.pc += re.ir[t.pc].data + IRL!(IR.InfiniteBloomStart);
 254         return op!(IR.InfiniteBloomEnd)(e,state);
 255     }
 256
 257     static bool op(IR code:IR.InfiniteQStart)(E e, S* state)
 258     {
 259         with(e) with(state)
 260             t.pc += re.ir[t.pc].data + IRL!(IR.InfiniteQStart);
 261         return op!(IR.InfiniteQEnd)(e,state);
 262     }
 263
 264     static bool op(IR code:IR.RepeatStart)(E e, S* state)
 265     {
 266         with(e) with(state)
 267             t.pc += re.ir[t.pc].data + IRL!(IR.RepeatStart);
 268         return op!(IR.RepeatEnd)(e,state);
 269     }
 270
 271     static bool op(IR code:IR.RepeatQStart)(E e, S* state)
 272     {
 273         with(e) with(state)
 274             t.pc += re.ir[t.pc].data + IRL!(IR.RepeatQStart);
 275         return op!(IR.RepeatQEnd)(e,state);
 276     }
 277
 278     static bool op(IR code)(E e, S* state)
 279     if (code == IR.RepeatEnd || code == IR.RepeatQEnd)
 280     {
 281         with(e) with(state)
 282         {
 283             //len, step, min, max
 284                 uint len = re.ir[t.pc].data;
 285                 uint step =  re.ir[t.pc+2].raw;
 286                 uint min = re.ir[t.pc+3].raw;
 287                 if (t.counter < min)
 288                 {
 289                     t.counter += step;
 290                     t.pc -= len;
 291                     return true;
 292                 }
 293                 if (merge[re.ir[t.pc + 1].raw+t.counter] < genCounter)
 294                 {
 295                     debug(std_regex_matcher) writefln("A thread(pc=%s) passed there : %s ; GenCounter=%s mergetab=%s",
 296                                     t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 297                     merge[re.ir[t.pc + 1].raw+t.counter] = genCounter;
 298                 }
 299                 else
 300                 {
 301                     debug(std_regex_matcher)
 302                         writefln("A thread(pc=%s) got merged there : %s ; GenCounter=%s mergetab=%s",
 303                             t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 304                     return popState(e);
 305                 }
 306                 uint max = re.ir[t.pc+4].raw;
 307                 if (t.counter < max)
 308                 {
 309                     if (re.ir[t.pc].code == IR.RepeatEnd)
 310                     {
 311                         //queue out-of-loop thread
 312                         worklist.insertFront(fork(t, t.pc + IRL!(IR.RepeatEnd),  t.counter % step));
 313                         t.counter += step;
 314                         t.pc -= len;
 315                     }
 316                     else
 317                     {
 318                         //queue into-loop thread
 319                         worklist.insertFront(fork(t, t.pc - len,  t.counter + step));
 320                         t.counter %= step;
 321                         t.pc += IRL!(IR.RepeatEnd);
 322                     }
 323                 }
 324                 else
 325                 {
 326                     t.counter %= step;
 327                     t.pc += IRL!(IR.RepeatEnd);
 328                 }
 329                 return true;
 330         }
 331     }
 332
 333     static bool op(IR code)(E e, S* state)
 334     if (code == IR.InfiniteEnd || code == IR.InfiniteQEnd)
 335     {
 336         with(e) with(state)
 337         {
 338             if (merge[re.ir[t.pc + 1].raw+t.counter] < genCounter)
 339             {
 340                 debug(std_regex_matcher) writefln("A thread(pc=%s) passed there : %s ; GenCounter=%s mergetab=%s",
 341                                 t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 342                 merge[re.ir[t.pc + 1].raw+t.counter] = genCounter;
 343             }
 344             else
 345             {
 346                 debug(std_regex_matcher) writefln("A thread(pc=%s) got merged there : %s ; GenCounter=%s mergetab=%s",
 347                                 t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 348                 return popState(e);
 349             }
 350             uint len = re.ir[t.pc].data;
 351             uint pc1, pc2; //branches to take in priority order
 352             if (re.ir[t.pc].code == IR.InfiniteEnd)
 353             {
 354                 pc1 = t.pc - len;
 355                 pc2 = t.pc + IRL!(IR.InfiniteEnd);
 356             }
 357             else
 358             {
 359                 pc1 = t.pc + IRL!(IR.InfiniteEnd);
 360                 pc2 = t.pc - len;
 361             }
 362             worklist.insertFront(fork(t, pc2, t.counter));
 363             t.pc = pc1;
 364             return true;
 365         }
 366     }
 367
 368     static bool op(IR code)(E e, S* state)
 369     if (code == IR.InfiniteBloomEnd)
 370     {
 371         with(e) with(state)
 372         {
 373             if (merge[re.ir[t.pc + 1].raw+t.counter] < genCounter)
 374             {
 375                 debug(std_regex_matcher) writefln("A thread(pc=%s) passed there : %s ; GenCounter=%s mergetab=%s",
 376                                 t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 377                 merge[re.ir[t.pc + 1].raw+t.counter] = genCounter;
 378             }
 379             else
 380             {
 381                 debug(std_regex_matcher) writefln("A thread(pc=%s) got merged there : %s ; GenCounter=%s mergetab=%s",
 382                                 t.pc, index, genCounter, merge[re.ir[t.pc + 1].raw+t.counter] );
 383                 return popState(e);
 384             }
 385             uint len = re.ir[t.pc].data;
 386             uint pc1, pc2; //branches to take in priority order
 387             pc1 = t.pc - len;
 388             pc2 = t.pc + IRL!(IR.InfiniteBloomEnd);
 389             uint filterIndex = re.ir[t.pc + 2].raw;
 390             if (re.filters[filterIndex][front])
 391                 worklist.insertFront(fork(t, pc2, t.counter));
 392             t.pc = pc1;
 393             return true;
 394         }
 395     }
 396
 397     static bool op(IR code:IR.OrEnd)(E e, S* state)
 398     {
 399         with(e) with(state)
 400         {
 401             if (merge[re.ir[t.pc + 1].raw+t.counter] < genCounter)
 402             {
 403                 debug(std_regex_matcher) writefln("A thread(pc=%s) passed there : %s ; GenCounter=%s mergetab=%s",
 404                                 t.pc, s[index .. s.lastIndex], genCounter, merge[re.ir[t.pc + 1].raw + t.counter] );
 405                 merge[re.ir[t.pc + 1].raw+t.counter] = genCounter;
 406                 t.pc += IRL!(IR.OrEnd);
 407             }
 408             else
 409             {
 410                 debug(std_regex_matcher) writefln("A thread(pc=%s) got merged there : %s ; GenCounter=%s mergetab=%s",
 411                                 t.pc, s[index .. s.lastIndex], genCounter, merge[re.ir[t.pc + 1].raw + t.counter] );
 412                 return popState(e);
 413             }
 414             return true;
 415         }
 416     }
 417
 418     static bool op(IR code:IR.OrStart)(E e, S* state)
 419     {
 420         with(e) with(state)
 421         {
 422             t.pc += IRL!(IR.OrStart);
 423             return op!(IR.Option)(e,state);
 424         }
 425     }
 426
 427     static bool op(IR code:IR.Option)(E e, S* state)
 428     {
 429         with(e) with(state)
 430         {
 431             uint next = t.pc + re.ir[t.pc].data + IRL!(IR.Option);
 432             //queue next Option
 433             if (re.ir[next].code == IR.Option)
 434             {
 435                 worklist.insertFront(fork(t, next, t.counter));
 436             }
 437             t.pc += IRL!(IR.Option);
 438             return true;
 439         }
 440     }
 441
 442     static bool op(IR code:IR.GotoEndOr)(E e, S* state)
 443     {
 444         with(e) with(state)
 445         {
 446             t.pc = t.pc + re.ir[t.pc].data + IRL!(IR.GotoEndOr);
 447             return op!(IR.OrEnd)(e, state);
 448         }
 449     }
 450
 451     static bool op(IR code:IR.GroupStart)(E e, S* state)
 452     {
 453         with(e) with(state)
 454         {
 455             uint n = re.ir[t.pc].data;
 456             t.matches.ptr[n].begin = index;
 457             t.pc += IRL!(IR.GroupStart);
 458             return true;
 459         }
 460     }
 461     static bool op(IR code:IR.GroupEnd)(E e, S* state)
 462     {
 463         with(e) with(state)
 464         {
 465             uint n = re.ir[t.pc].data;
 466             t.matches.ptr[n].end = index;
 467             t.pc += IRL!(IR.GroupEnd);
 468             return true;
 469         }
 470     }
 471
 472     static bool op(IR code:IR.Backref)(E e, S* state)
 473     {
 474         with(e) with(state)
 475         {
 476             uint n = re.ir[t.pc].data;
 477             Group!DataIndex* source = re.ir[t.pc].localRef ? t.matches.ptr : backrefed.ptr;
 478             assert(source);
 479             if (source[n].begin == source[n].end)//zero-width Backref!
 480             {
 481                 t.pc += IRL!(IR.Backref);
 482                 return true;
 483             }
 484             else
 485             {
 486                 size_t idx = source[n].begin + t.uopCounter;
 487                 size_t end = source[n].end;
 488                 if (s[idx .. end].front == front)
 489                 {
 490                     import std.utf : stride;
 491
 492                     t.uopCounter += stride(s[idx .. end], 0);
 493                     if (t.uopCounter + source[n].begin == source[n].end)
 494                     {//last codepoint
 495                         t.pc += IRL!(IR.Backref);
 496                         t.uopCounter = 0;
 497                     }
 498                     nlist.insertBack(t);
 499                 }
 500                 else
 501                     recycle(t);
 502                 t = worklist.fetch();
 503                 return t != null;
 504             }
 505         }
 506     }
 507
 508
 509     static bool op(IR code)(E e, S* state)
 510     if (code == IR.LookbehindStart || code == IR.NeglookbehindStart)
 511     {
 512         with(e) with(state)
 513         {
 514             uint len = re.ir[t.pc].data;
 515             uint ms = re.ir[t.pc + 1].raw, me = re.ir[t.pc + 2].raw;
 516             uint end = t.pc + len + IRL!(IR.LookbehindEnd) + IRL!(IR.LookbehindStart);
 517             bool positive = re.ir[t.pc].code == IR.LookbehindStart;
 518             static if (Stream.isLoopback)
 519                 auto matcher = fwdMatcher(t.pc, end, me - ms, subCounters.get(t.pc, 0));
 520             else
 521                 auto matcher = bwdMatcher(t.pc, end, me - ms, subCounters.get(t.pc, 0));
 522             matcher.backrefed = backrefed.empty ? t.matches : backrefed;
 523             //backMatch
 524             auto mRes = matcher.matchOneShot(t.matches.ptr[ms .. me], IRL!(IR.LookbehindStart));
 525             freelist = matcher.freelist;
 526             subCounters[t.pc] = matcher.genCounter;
 527             if ((mRes != 0 ) ^ positive)
 528             {
 529                 return popState(e);
 530             }
 531             t.pc = end;
 532             return true;
 533         }
 534     }
 535
 536     static bool op(IR code)(E e, S* state)
 537     if (code == IR.LookaheadStart || code == IR.NeglookaheadStart)
 538     {
 539         with(e) with(state)
 540         {
 541             auto save = index;
 542             uint len = re.ir[t.pc].data;
 543             uint ms = re.ir[t.pc+1].raw, me = re.ir[t.pc+2].raw;
 544             uint end = t.pc+len+IRL!(IR.LookaheadEnd)+IRL!(IR.LookaheadStart);
 545             bool positive = re.ir[t.pc].code == IR.LookaheadStart;
 546             static if (Stream.isLoopback)
 547                 auto matcher = bwdMatcher(t.pc, end, me - ms, subCounters.get(t.pc, 0));
 548             else
 549                 auto matcher = fwdMatcher(t.pc, end, me - ms, subCounters.get(t.pc, 0));
 550             matcher.backrefed = backrefed.empty ? t.matches : backrefed;
 551             auto mRes = matcher.matchOneShot(t.matches.ptr[ms .. me], IRL!(IR.LookaheadStart));
 552             freelist = matcher.freelist;
 553             subCounters[t.pc] = matcher.genCounter;
 554             s.reset(index);
 555             next();
 556             if ((mRes != 0) ^ positive)
 557             {
 558                 return popState(e);
 559             }
 560             t.pc = end;
 561             return true;
 562         }
 563     }
 564
 565     static bool op(IR code)(E e, S* state)
 566     if (code == IR.LookaheadEnd || code == IR.NeglookaheadEnd ||
 567         code == IR.LookbehindEnd || code == IR.NeglookbehindEnd)
 568     {
 569         with(e) with(state)
 570         {
 571                 finish(t, matches.ptr[0 .. re.ngroup], re.ir[t.pc].data);
 572                 recycle(t);
 573                 //cut off low priority threads
 574                 recycle(clist);
 575                 recycle(worklist);
 576                 return false; // no more state
 577         }
 578     }
 579
 580     static bool op(IR code:IR.Nop)(E e, S* state)
 581     {
 582         with(state) t.pc += IRL!(IR.Nop);
 583         return true;
 584     }
 585
 586     static bool op(IR code:IR.OrChar)(E e, S* state)
 587     {
 588         with(e) with(state)
 589         {
 590             uint len = re.ir[t.pc].sequence;
 591             uint end = t.pc + len;
 592             static assert(IRL!(IR.OrChar) == 1);
 593             for (; t.pc < end; t.pc++)
 594                 if (re.ir[t.pc].data == front)
 595                     break;
 596             if (t.pc != end)
 597             {
 598                 t.pc = end;
 599                 nlist.insertBack(t);
 600             }
 601             else
 602                 recycle(t);
 603             t = worklist.fetch();
 604             return t != null;
 605         }
 606     }
 607
 608     static bool op(IR code:IR.Char)(E e, S* state)
 609     {
 610         with(e) with(state)
 611         {
 612             if (front == re.ir[t.pc].data)
 613             {
 614                 t.pc += IRL!(IR.Char);
 615                 nlist.insertBack(t);
 616             }
 617             else
 618                 recycle(t);
 619             t = worklist.fetch();
 620             return t != null;
 621         }
 622     }
 623
 624     static bool op(IR code:IR.Any)(E e, S* state)
 625     {
 626         with(e) with(state)
 627         {
 628             t.pc += IRL!(IR.Any);
 629             nlist.insertBack(t);
 630             t = worklist.fetch();
 631             return t != null;
 632         }
 633     }
 634
 635     static bool op(IR code:IR.CodepointSet)(E e, S* state)
 636     {
 637         with(e) with(state)
 638         {
 639             if (re.charsets[re.ir[t.pc].data].scanFor(front))
 640             {
 641                 t.pc += IRL!(IR.CodepointSet);
 642                 nlist.insertBack(t);
 643             }
 644             else
 645             {
 646                 recycle(t);
 647             }
 648             t = worklist.fetch();
 649             return t != null;
 650         }
 651     }
 652
 653     static bool op(IR code:IR.Trie)(E e, S* state)
 654     {
 655         with(e) with(state)
 656         {
 657             if (re.matchers[re.ir[t.pc].data][front])
 658             {
 659                 t.pc += IRL!(IR.Trie);
 660                 nlist.insertBack(t);
 661             }
 662             else
 663             {
 664                 recycle(t);
 665             }
 666             t = worklist.fetch();
 667             return t != null;
 668         }
 669     }
 670
 671 }
 672
 673 template ThompsonOps(E,S, bool withInput:false)
 674 {
 675 @trusted:
 676     // can't match these without input
 677     static bool op(IR code)(E e, S* state)
 678     if (code == IR.Char || code == IR.OrChar || code == IR.CodepointSet
 679         || code == IR.Trie || code == IR.Char || code == IR.Any)
 680     {
 681         return state.popState(e);
 682     }
 683
 684     // special case of zero-width backref
 685     static bool op(IR code:IR.Backref)(E e, S* state)
 686     {
 687         with(e) with(state)
 688         {
 689             uint n = re.ir[t.pc].data;
 690             Group!DataIndex* source = re.ir[t.pc].localRef ? t.matches.ptr : backrefed.ptr;
 691             assert(source);
 692             if (source[n].begin == source[n].end)//zero-width Backref!
 693             {
 694                 t.pc += IRL!(IR.Backref);
 695                 return true;
 696             }
 697             else
 698                 return popState(e);
 699         }
 700     }
 701
 702     // forward all control flow to normal versions
 703     static bool op(IR code)(E e, S* state)
 704     if (code != IR.Char && code != IR.OrChar && code != IR.CodepointSet
 705         && code != IR.Trie && code != IR.Char && code != IR.Any && code != IR.Backref)
 706     {
 707         return ThompsonOps!(E,S,true).op!code(e,state);
 708     }
 709 }
 710
 711 /+
 712    Thomspon matcher does all matching in lockstep,
 713    never looking at the same char twice
 714 +/
 715 @trusted class ThompsonMatcher(Char, StreamType = Input!Char): Matcher!Char
 716 if (is(Char : dchar))
 717 {
 718     alias DataIndex = Stream.DataIndex;
 719     alias Stream = StreamType;
 720     alias OpFunc = bool function(ThompsonMatcher, State*) pure;
 721     alias BackMatcher = ThompsonMatcher!(Char, BackLooper!(Stream));
 722     alias OpBackFunc = bool function(BackMatcher, BackMatcher.State*) pure;
 723     Thread!DataIndex* freelist;
 724     ThreadList!DataIndex clist, nlist;
 725     DataIndex[] merge;
 726     Group!DataIndex[] backrefed;
 727     const Regex!Char re;           //regex program
 728     Stream s;
 729     dchar front;
 730     DataIndex index;
 731     DataIndex genCounter;    //merge trace counter, goes up on every dchar
 732     size_t[size_t] subCounters; //a table of gen counter per sub-engine: PC -> counter
 733     OpFunc[] opCacheTrue;   // pointers to Op!(IR.xyz) for each bytecode
 734     OpFunc[] opCacheFalse;  // ditto
 735     OpBackFunc[] opCacheBackTrue;   // ditto
 736     OpBackFunc[] opCacheBackFalse;  // ditto
 737     size_t threadSize;
 738     size_t _refCount;
 739     int matched;
 740     bool exhausted;
 741
 742 final:
 743     pure
 744     static struct State
 745     {
 746         Thread!DataIndex* t;
 747         ThreadList!DataIndex worklist;
 748         Group!DataIndex[] matches;
 749
 750         bool popState(E)(E e)
 751         {
 752             with(e)
 753             {
 754                 recycle(t);
 755                 t = worklist.fetch();
 756                 return t != null;
 757             }
 758         }
 759
 760     }
 761
 762     enum kicked = __traits(hasMember, Stream, "search");
 763
 764     static size_t getThreadSize(const ref Regex!Char re)
 765     {
 766         return re.ngroup
 767             ? (Thread!DataIndex).sizeof + (re.ngroup-1)*(Group!DataIndex).sizeof
 768             : (Thread!DataIndex).sizeof - (Group!DataIndex).sizeof;
 769     }
 770
 771     static size_t initialMemory(const ref Regex!Char re)
 772     {
 773         return getThreadSize(re)*re.threadCount + re.hotspotTableSize*size_t.sizeof
 774             +4*OpFunc.sizeof*re.ir.length;
 775     }
 776
 777     //true if it's start of input
 778     @property bool atStart(){   return index == 0; }
 779
 780     //true if it's end of input
 781     @property bool atEnd(){  return index == s.lastIndex && s.atEnd; }
 782
 783     override @property ref size_t refCount() @safe { return _refCount; }
 784
 785     override @property ref const(Regex!Char) pattern() @safe { return re; }
 786
 787     bool next()
 788     {
 789         if (!s.nextChar(front, index))
 790         {
 791             index =  s.lastIndex;
 792             return false;
 793         }
 794         return true;
 795     }
 796
 797     static if (kicked)
 798     {
 799         bool search()
 800         {
 801
 802             if (!s.search(re.kickstart, front, index))
 803             {
 804                 index = s.lastIndex;
 805                 return false;
 806             }
 807             return true;
 808         }
 809     }
 810
 811     void initExternalMemory(void[] memory)
 812     {
 813         threadSize = getThreadSize(re);
 814         prepareFreeList(re.threadCount, memory);
 815         if (re.hotspotTableSize)
 816         {
 817             merge = arrayInChunk!(DataIndex)(re.hotspotTableSize, memory);
 818             merge[] = 0;
 819         }
 820         opCacheTrue = arrayInChunk!(OpFunc)(re.ir.length, memory);
 821         opCacheFalse = arrayInChunk!(OpFunc)(re.ir.length, memory);
 822         opCacheBackTrue = arrayInChunk!(OpBackFunc)(re.ir.length, memory);
 823         opCacheBackFalse = arrayInChunk!(OpBackFunc)(re.ir.length, memory);
 824
 825         for (uint pc = 0; pc<re.ir.length; pc += re.ir[pc].length)
 826         {
 827         L_dispatch:
 828             switch (re.ir[pc].code)
 829             {
 830                 foreach (e; __traits(allMembers, IR))
 831                 {
 832             mixin(`case IR.`~e~`:
 833                     opCacheTrue[pc] = &Ops!(true).op!(IR.`~e~`);
 834                     opCacheBackTrue[pc] = &BackOps!(true).op!(IR.`~e~`);
 835                     opCacheFalse[pc] = &Ops!(false).op!(IR.`~e~`);
 836                     opCacheBackFalse[pc] = &BackOps!(false).op!(IR.`~e~`);
 837                 break L_dispatch;
 838                 `);
 839                 }
 840             default:
 841                 assert(0, "Unrecognized instruction "~re.ir[pc].mnemonic);
 842             }
 843         }
 844     }
 845
 846     override Matcher!Char rearm(in Char[] data)
 847     {
 848         exhausted = false;
 849         matched = 0;
 850         s = Stream(data);
 851         return this;
 852     }
 853
 854     this()(ref const Regex!Char program, Stream stream, void[] memory)
 855     {
 856          // We are emplace'd to malloced memory w/o blitting T.init over it\
 857          // make sure we initialize all fields explicitly
 858         _refCount = 1;
 859         subCounters = null;
 860         backrefed = null;
 861         exhausted = false;
 862         matched = 0;
 863         re = program;
 864         s = stream;
 865         initExternalMemory(memory);
 866         genCounter = 0;
 867     }
 868
 869     this(ThompsonMatcher matcher, size_t lo, size_t hi, uint nGroup, Stream stream)
 870     {
 871         _refCount = 1;
 872         subCounters = matcher.subCounters;
 873         s = stream;
 874         auto code = matcher.re.ir[lo .. hi];
 875         re = matcher.re.withCode(code).withNGroup(nGroup);
 876         threadSize = matcher.threadSize;
 877         merge = matcher.merge;
 878         freelist = matcher.freelist;
 879         opCacheTrue = matcher.opCacheTrue[lo .. hi];
 880         opCacheBackTrue = matcher.opCacheBackTrue[lo .. hi];
 881         opCacheFalse = matcher.opCacheFalse[lo .. hi];
 882         opCacheBackFalse = matcher.opCacheBackFalse[lo .. hi];
 883         front = matcher.front;
 884         index = matcher.index;
 885     }
 886
 887     this(BackMatcher matcher, size_t lo, size_t hi, uint nGroup, Stream stream)
 888     {
 889         _refCount = 1;
 890         subCounters = matcher.subCounters;
 891         s = stream;
 892         auto code = matcher.re.ir[lo .. hi];
 893         re = matcher.re.withCode(code).withNGroup(nGroup);
 894         threadSize = matcher.threadSize;
 895         merge = matcher.merge;
 896         freelist = matcher.freelist;
 897         opCacheTrue = matcher.opCacheBackTrue[lo .. hi];
 898         opCacheBackTrue = matcher.opCacheTrue[lo .. hi];
 899         opCacheFalse = matcher.opCacheBackFalse[lo .. hi];
 900         opCacheBackFalse = matcher.opCacheFalse[lo .. hi];
 901         front = matcher.front;
 902         index = matcher.index;
 903     }
 904
 905     auto fwdMatcher()(size_t lo, size_t hi, uint nGroup, size_t counter)
 906     {
 907         auto m = new ThompsonMatcher!(Char, Stream)(this, lo, hi, nGroup, s);
 908         m.genCounter = counter;
 909         return m;
 910     }
 911
 912     auto bwdMatcher()(size_t lo, size_t hi, uint nGroup, size_t counter)
 913     {
 914         alias BackLooper = typeof(s.loopBack(index));
 915         auto m = new ThompsonMatcher!(Char, BackLooper)(this, lo, hi, nGroup, s.loopBack(index));
 916         m.genCounter = counter;
 917         m.next();
 918         return m;
 919     }
 920
 921     override void dupTo(Matcher!Char engine, void[] memory)
 922     {
 923         auto thompson = cast(ThompsonMatcher) engine;
 924         thompson.s = s;
 925         thompson.subCounters = null;
 926         thompson.front = front;
 927         thompson.index = index;
 928         thompson.matched = matched;
 929         thompson.exhausted = exhausted;
 930         thompson.initExternalMemory(memory);
 931     }
 932
 933     override int match(Group!DataIndex[] matches)
 934     {
 935         debug(std_regex_matcher)
 936             writeln("------------------------------------------");
 937         if (exhausted)
 938         {
 939             return false;
 940         }
 941         if (re.flags & RegexInfo.oneShot)
 942         {
 943             next();
 944             exhausted = true;
 945             return matchOneShot(matches);
 946         }
 947         static if (kicked)
 948             if (!re.kickstart.empty)
 949                 return matchImpl!(true)(matches);
 950         return matchImpl!(false)(matches);
 951     }
 952
 953     //match the input and fill matches
 954     int matchImpl(bool withSearch)(Group!DataIndex[] matches)
 955     {
 956         if (!matched && clist.empty)
 957         {
 958            static if (withSearch)
 959                 search();
 960            else
 961                 next();
 962         }
 963         else//char in question is  fetched in prev call to match
 964         {
 965             matched = 0;
 966         }
 967         State state;
 968         state.matches = matches;
 969
 970         if (!atEnd)//if no char
 971             for (;;)
 972             {
 973                 genCounter++;
 974                 debug(std_regex_matcher)
 975                 {
 976                     writefln("Threaded matching threads at  %s", s[index .. s.lastIndex]);
 977                     foreach (t; clist[])
 978                     {
 979                         assert(t);
 980                         writef("pc=%s ",t.pc);
 981                         write(t.matches);
 982                         writeln();
 983                     }
 984                 }
 985                 for (state.t = clist.fetch(); state.t; state.t = clist.fetch())
 986                 {
 987                     eval!true(&state);
 988                 }
 989                 //if we already have match no need to push the engine
 990                 if (!matched)
 991                 {
 992                     state.t = createStart(index);
 993                     eval!true(&state);//new thread staring at this position
 994                 }
 995                 else if (nlist.empty)
 996                 {
 997                     debug(std_regex_matcher) writeln("Stopped  matching before consuming full input");
 998                     break;//not a partial match for sure
 999                 }
1000                 clist = nlist;
1001                 nlist = (ThreadList!DataIndex).init;
1002                 if (clist.tip is null)
1003                 {
1004                     static if (withSearch)
1005                     {
1006                         if (!search())
1007                             break;
1008                     }
1009                     else
1010                     {
1011                         if (!next())
1012                             break;
1013                     }
1014                 }
1015                 else if (!next())
1016                 {
1017                     if (!atEnd) return false;
1018                     exhausted = true;
1019                     break;
1020                 }
1021             }
1022
1023         genCounter++; //increment also on each end
1024         debug(std_regex_matcher) writefln("Threaded matching threads at end");
1025         //try out all zero-width posibilities
1026         for (state.t = clist.fetch(); state.t; state.t = clist.fetch())
1027         {
1028             eval!false(&state);
1029         }
1030         if (!matched)
1031         {
1032             state.t = createStart(index);
1033             eval!false(&state);//new thread starting at end of input
1034         }
1035         if (matched)
1036         {//in case NFA found match along the way
1037          //and last possible longer alternative ultimately failed
1038             s.reset(matches[0].end);//reset to last successful match
1039             next();//and reload front character
1040             //--- here the exact state of stream was restored ---
1041             exhausted = atEnd || !(re.flags & RegexOption.global);
1042             //+ empty match advances the input
1043             if (!exhausted && matches[0].begin == matches[0].end)
1044                 next();
1045         }
1046         return matched;
1047     }
1048
1049     /+
1050         handle succesful threads
1051     +/
1052     void finish(const(Thread!DataIndex)* t, Group!DataIndex[] matches, int code)
1053     {
1054         matches.ptr[0 .. re.ngroup] = t.matches.ptr[0 .. re.ngroup];
1055         debug(std_regex_matcher)
1056         {
1057             writef("FOUND pc=%s prog_len=%s",
1058                     t.pc, re.ir.length);
1059             if (!matches.empty)
1060                 writefln(": %s..%s", matches[0].begin, matches[0].end);
1061             foreach (v; matches)
1062                 writefln("%d .. %d", v.begin, v.end);
1063         }
1064         matched = code;
1065     }
1066
1067     alias Ops(bool withInput) =  ThompsonOps!(ThompsonMatcher, State, withInput);
1068     alias BackOps(bool withInput) =  ThompsonOps!(BackMatcher, BackMatcher.State, withInput);
1069
1070     /+
1071         match thread against codepoint, cutting trough all 0-width instructions
1072         and taking care of control flow, then add it to nlist
1073     +/
1074     void eval(bool withInput)(State* state)
1075     {
1076         debug(std_regex_matcher) writeln("---- Evaluating thread");
1077         static if (withInput)
1078             while (opCacheTrue.ptr[state.t.pc](this, state)){}
1079         else
1080             while (opCacheFalse.ptr[state.t.pc](this, state)){}
1081     }
1082     enum uint RestartPc = uint.max;
1083     //match the input, evaluating IR without searching
1084     int matchOneShot(Group!DataIndex[] matches, uint startPc = 0)
1085     {
1086         debug(std_regex_matcher)
1087         {
1088             writefln("---------------single shot match ----------------- ");
1089         }
1090         alias evalFn = eval;
1091         assert(clist == (ThreadList!DataIndex).init || startPc == RestartPc); // incorrect after a partial match
1092         assert(nlist == (ThreadList!DataIndex).init || startPc == RestartPc);
1093         State state;
1094         state.matches = matches;
1095         if (!atEnd)//if no char
1096         {
1097             debug(std_regex_matcher)
1098             {
1099                 writefln("-- Threaded matching threads at  %s",  s[index .. s.lastIndex]);
1100             }
1101             if (startPc != RestartPc)
1102             {
1103                 state.t = createStart(index, startPc);
1104                 genCounter++;
1105                 evalFn!true(&state);
1106             }
1107             for (;;)
1108             {
1109                 debug(std_regex_matcher) writeln("\n-- Started iteration of main cycle");
1110                 genCounter++;
1111                 debug(std_regex_matcher)
1112                 {
1113                     foreach (t; clist[])
1114                     {
1115                         assert(t);
1116                     }
1117                 }
1118                 for (state.t = clist.fetch(); state.t; state.t = clist.fetch())
1119                 {
1120                     evalFn!true(&state);
1121                 }
1122                 if (nlist.empty)
1123                 {
1124                     debug(std_regex_matcher) writeln("Stopped  matching before consuming full input");
1125                     break;//not a partial match for sure
1126                 }
1127                 clist = nlist;
1128                 nlist = (ThreadList!DataIndex).init;
1129                 if (!next())
1130                     break;
1131                 debug(std_regex_matcher) writeln("-- Ended iteration of main cycle\n");
1132             }
1133         }
1134         genCounter++; //increment also on each end
1135         debug(std_regex_matcher) writefln("-- Matching threads at end");
1136         //try out all zero-width posibilities
1137         for (state.t = clist.fetch(); state.t; state.t = clist.fetch())
1138         {
1139             evalFn!false(&state);
1140         }
1141         if (!matched)
1142         {
1143             state.t = createStart(index, startPc);
1144             evalFn!false(&state);
1145         }
1146         return matched;
1147     }
1148
1149     //get a dirty recycled Thread
1150     Thread!DataIndex* allocate()
1151     {
1152         assert(freelist, "not enough preallocated memory");
1153         Thread!DataIndex* t = freelist;
1154         freelist = freelist.next;
1155         return t;
1156     }
1157
1158     //link memory into a free list of Threads
1159     void prepareFreeList(size_t size, ref void[] memory)
1160     {
1161         void[] mem = memory[0 .. threadSize*size];
1162         memory = memory[threadSize * size .. $];
1163         freelist = cast(Thread!DataIndex*)&mem[0];
1164         size_t i;
1165         for (i = threadSize; i < threadSize*size; i += threadSize)
1166             (cast(Thread!DataIndex*)&mem[i-threadSize]).next = cast(Thread!DataIndex*)&mem[i];
1167         (cast(Thread!DataIndex*)&mem[i-threadSize]).next = null;
1168     }
1169
1170     //dispose a thread
1171     void recycle(Thread!DataIndex* t)
1172     {
1173         t.next = freelist;
1174         freelist = t;
1175     }
1176
1177     //dispose list of threads
1178     void recycle(ref ThreadList!DataIndex list)
1179     {
1180         if (list.tip)
1181         {
1182             // just put this head-tail list in front of freelist
1183             list.toe.next = freelist;
1184             freelist = list.tip;
1185             list = list.init;
1186         }
1187     }
1188
1189     //creates a copy of master thread with given pc
1190     Thread!DataIndex* fork(Thread!DataIndex* master, uint pc, uint counter)
1191     {
1192         auto t = allocate();
1193         t.matches.ptr[0 .. re.ngroup] = master.matches.ptr[0 .. re.ngroup];
1194         t.pc = pc;
1195         t.counter = counter;
1196         t.uopCounter = 0;
1197         return t;
1198     }
1199
1200     //creates a start thread
1201     Thread!DataIndex* createStart(DataIndex index, uint pc = 0)
1202     {
1203         auto t = allocate();
1204         t.matches.ptr[0 .. re.ngroup] = (Group!DataIndex).init;
1205         t.matches[0].begin = index;
1206         t.pc = pc;
1207         t.counter = 0;
1208         t.uopCounter = 0;
1209         return t;
1210     }
1211 }