1 /*
2 ** $Id: lpcode.c $
3 ** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license)
4 */
5
6 #include <limits.h>
7
8
9 #include "lua.h"
10 #include "lauxlib.h"
11
12 #include "lptypes.h"
13 #include "lpcode.h"
14
15
16 /* signals a "no-instruction */
17 #define NOINST -1
18
19
20
21 static const Charset fullset_ =
22 {{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
23 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
24 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
25 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}};
26
27 static const Charset *fullset = &fullset_;
28
29 /*
30 ** {======================================================
31 ** Analysis and some optimizations
32 ** =======================================================
33 */
34
35 /*
36 ** Check whether a charset is empty (returns IFail), singleton (IChar),
37 ** full (IAny), or none of those (ISet). When singleton, '*c' returns
38 ** which character it is. (When generic set, the set was the input,
39 ** so there is no need to return it.)
40 */
charsettype(const byte * cs,int * c)41 static Opcode charsettype (const byte *cs, int *c) {
42 int count = 0; /* number of characters in the set */
43 int i;
44 int candidate = -1; /* candidate position for the singleton char */
45 for (i = 0; i < CHARSETSIZE; i++) { /* for each byte */
46 int b = cs[i];
47 if (b == 0) { /* is byte empty? */
48 if (count > 1) /* was set neither empty nor singleton? */
49 return ISet; /* neither full nor empty nor singleton */
50 /* else set is still empty or singleton */
51 }
52 else if (b == 0xFF) { /* is byte full? */
53 if (count < (i * BITSPERCHAR)) /* was set not full? */
54 return ISet; /* neither full nor empty nor singleton */
55 else count += BITSPERCHAR; /* set is still full */
56 }
57 else if ((b & (b - 1)) == 0) { /* has byte only one bit? */
58 if (count > 0) /* was set not empty? */
59 return ISet; /* neither full nor empty nor singleton */
60 else { /* set has only one char till now; track it */
61 count++;
62 candidate = i;
63 }
64 }
65 else return ISet; /* byte is neither empty, full, nor singleton */
66 }
67 switch (count) {
68 case 0: return IFail; /* empty set */
69 case 1: { /* singleton; find character bit inside byte */
70 int b = cs[candidate];
71 *c = candidate * BITSPERCHAR;
72 if ((b & 0xF0) != 0) { *c += 4; b >>= 4; }
73 if ((b & 0x0C) != 0) { *c += 2; b >>= 2; }
74 if ((b & 0x02) != 0) { *c += 1; }
75 return IChar;
76 }
77 default: {
78 assert(count == CHARSETSIZE * BITSPERCHAR); /* full set */
79 return IAny;
80 }
81 }
82 }
83
84
85 /*
86 ** A few basic operations on Charsets
87 */
cs_complement(Charset * cs)88 static void cs_complement (Charset *cs) {
89 loopset(i, cs->cs[i] = ~cs->cs[i]);
90 }
91
cs_equal(const byte * cs1,const byte * cs2)92 static int cs_equal (const byte *cs1, const byte *cs2) {
93 loopset(i, if (cs1[i] != cs2[i]) return 0);
94 return 1;
95 }
96
cs_disjoint(const Charset * cs1,const Charset * cs2)97 static int cs_disjoint (const Charset *cs1, const Charset *cs2) {
98 loopset(i, if ((cs1->cs[i] & cs2->cs[i]) != 0) return 0;)
99 return 1;
100 }
101
102
103 /*
104 ** If 'tree' is a 'char' pattern (TSet, TChar, TAny), convert it into a
105 ** charset and return 1; else return 0.
106 */
tocharset(TTree * tree,Charset * cs)107 int tocharset (TTree *tree, Charset *cs) {
108 switch (tree->tag) {
109 case TSet: { /* copy set */
110 loopset(i, cs->cs[i] = treebuffer(tree)[i]);
111 return 1;
112 }
113 case TChar: { /* only one char */
114 assert(0 <= tree->u.n && tree->u.n <= UCHAR_MAX);
115 loopset(i, cs->cs[i] = 0); /* erase all chars */
116 setchar(cs->cs, tree->u.n); /* add that one */
117 return 1;
118 }
119 case TAny: {
120 loopset(i, cs->cs[i] = 0xFF); /* add all characters to the set */
121 return 1;
122 }
123 default: return 0;
124 }
125 }
126
127
128 /*
129 ** Visit a TCall node taking care to stop recursion. If node not yet
130 ** visited, return 'f(sib2(tree))', otherwise return 'def' (default
131 ** value)
132 */
callrecursive(TTree * tree,int f (TTree * t),int def)133 static int callrecursive (TTree *tree, int f (TTree *t), int def) {
134 int key = tree->key;
135 assert(tree->tag == TCall);
136 assert(sib2(tree)->tag == TRule);
137 if (key == 0) /* node already visited? */
138 return def; /* return default value */
139 else { /* first visit */
140 int result;
141 tree->key = 0; /* mark call as already visited */
142 result = f(sib2(tree)); /* go to called rule */
143 tree->key = key; /* restore tree */
144 return result;
145 }
146 }
147
148
149 /*
150 ** Check whether a pattern tree has captures
151 */
hascaptures(TTree * tree)152 int hascaptures (TTree *tree) {
153 tailcall:
154 switch (tree->tag) {
155 case TCapture: case TRunTime:
156 return 1;
157 case TCall:
158 return callrecursive(tree, hascaptures, 0);
159 case TRule: /* do not follow siblings */
160 tree = sib1(tree); goto tailcall;
161 case TOpenCall: assert(0);
162 default: {
163 switch (numsiblings[tree->tag]) {
164 case 1: /* return hascaptures(sib1(tree)); */
165 tree = sib1(tree); goto tailcall;
166 case 2:
167 if (hascaptures(sib1(tree)))
168 return 1;
169 /* else return hascaptures(sib2(tree)); */
170 tree = sib2(tree); goto tailcall;
171 default: assert(numsiblings[tree->tag] == 0); return 0;
172 }
173 }
174 }
175 }
176
177
178 /*
179 ** Checks how a pattern behaves regarding the empty string,
180 ** in one of two different ways:
181 ** A pattern is *nullable* if it can match without consuming any character;
182 ** A pattern is *nofail* if it never fails for any string
183 ** (including the empty string).
184 ** The difference is only for predicates and run-time captures;
185 ** for other patterns, the two properties are equivalent.
186 ** (With predicates, &'a' is nullable but not nofail. Of course,
187 ** nofail => nullable.)
188 ** These functions are all convervative in the following way:
189 ** p is nullable => nullable(p)
190 ** nofail(p) => p cannot fail
191 ** The function assumes that TOpenCall is not nullable;
192 ** this will be checked again when the grammar is fixed.
193 ** Run-time captures can do whatever they want, so the result
194 ** is conservative.
195 */
checkaux(TTree * tree,int pred)196 int checkaux (TTree *tree, int pred) {
197 tailcall:
198 switch (tree->tag) {
199 case TChar: case TSet: case TAny:
200 case TFalse: case TOpenCall:
201 return 0; /* not nullable */
202 case TRep: case TTrue:
203 return 1; /* no fail */
204 case TNot: case TBehind: /* can match empty, but can fail */
205 if (pred == PEnofail) return 0;
206 else return 1; /* PEnullable */
207 case TAnd: /* can match empty; fail iff body does */
208 if (pred == PEnullable) return 1;
209 /* else return checkaux(sib1(tree), pred); */
210 tree = sib1(tree); goto tailcall;
211 case TRunTime: /* can fail; match empty iff body does */
212 if (pred == PEnofail) return 0;
213 /* else return checkaux(sib1(tree), pred); */
214 tree = sib1(tree); goto tailcall;
215 case TSeq:
216 if (!checkaux(sib1(tree), pred)) return 0;
217 /* else return checkaux(sib2(tree), pred); */
218 tree = sib2(tree); goto tailcall;
219 case TChoice:
220 if (checkaux(sib2(tree), pred)) return 1;
221 /* else return checkaux(sib1(tree), pred); */
222 tree = sib1(tree); goto tailcall;
223 case TCapture: case TGrammar: case TRule:
224 /* return checkaux(sib1(tree), pred); */
225 tree = sib1(tree); goto tailcall;
226 case TCall: /* return checkaux(sib2(tree), pred); */
227 tree = sib2(tree); goto tailcall;
228 default: assert(0); return 0;
229 }
230 }
231
232
233 /*
234 ** number of characters to match a pattern (or -1 if variable)
235 */
fixedlen(TTree * tree)236 int fixedlen (TTree *tree) {
237 int len = 0; /* to accumulate in tail calls */
238 tailcall:
239 switch (tree->tag) {
240 case TChar: case TSet: case TAny:
241 return len + 1;
242 case TFalse: case TTrue: case TNot: case TAnd: case TBehind:
243 return len;
244 case TRep: case TRunTime: case TOpenCall:
245 return -1;
246 case TCapture: case TRule: case TGrammar:
247 /* return fixedlen(sib1(tree)); */
248 tree = sib1(tree); goto tailcall;
249 case TCall: {
250 int n1 = callrecursive(tree, fixedlen, -1);
251 if (n1 < 0)
252 return -1;
253 else
254 return len + n1;
255 }
256 case TSeq: {
257 int n1 = fixedlen(sib1(tree));
258 if (n1 < 0)
259 return -1;
260 /* else return fixedlen(sib2(tree)) + len; */
261 len += n1; tree = sib2(tree); goto tailcall;
262 }
263 case TChoice: {
264 int n1 = fixedlen(sib1(tree));
265 int n2 = fixedlen(sib2(tree));
266 if (n1 != n2 || n1 < 0)
267 return -1;
268 else
269 return len + n1;
270 }
271 default: assert(0); return 0;
272 };
273 }
274
275
276 /*
277 ** Computes the 'first set' of a pattern.
278 ** The result is a conservative aproximation:
279 ** match p ax -> x (for some x) ==> a belongs to first(p)
280 ** or
281 ** a not in first(p) ==> match p ax -> fail (for all x)
282 **
283 ** The set 'follow' is the first set of what follows the
284 ** pattern (full set if nothing follows it).
285 **
286 ** The function returns 0 when this resulting set can be used for
287 ** test instructions that avoid the pattern altogether.
288 ** A non-zero return can happen for two reasons:
289 ** 1) match p '' -> '' ==> return has bit 1 set
290 ** (tests cannot be used because they would always fail for an empty input);
291 ** 2) there is a match-time capture ==> return has bit 2 set
292 ** (optimizations should not bypass match-time captures).
293 */
getfirst(TTree * tree,const Charset * follow,Charset * firstset)294 static int getfirst (TTree *tree, const Charset *follow, Charset *firstset) {
295 tailcall:
296 switch (tree->tag) {
297 case TChar: case TSet: case TAny: {
298 tocharset(tree, firstset);
299 return 0;
300 }
301 case TTrue: {
302 loopset(i, firstset->cs[i] = follow->cs[i]);
303 return 1; /* accepts the empty string */
304 }
305 case TFalse: {
306 loopset(i, firstset->cs[i] = 0);
307 return 0;
308 }
309 case TChoice: {
310 Charset csaux;
311 int e1 = getfirst(sib1(tree), follow, firstset);
312 int e2 = getfirst(sib2(tree), follow, &csaux);
313 loopset(i, firstset->cs[i] |= csaux.cs[i]);
314 return e1 | e2;
315 }
316 case TSeq: {
317 if (!nullable(sib1(tree))) {
318 /* when p1 is not nullable, p2 has nothing to contribute;
319 return getfirst(sib1(tree), fullset, firstset); */
320 tree = sib1(tree); follow = fullset; goto tailcall;
321 }
322 else { /* FIRST(p1 p2, fl) = FIRST(p1, FIRST(p2, fl)) */
323 Charset csaux;
324 int e2 = getfirst(sib2(tree), follow, &csaux);
325 int e1 = getfirst(sib1(tree), &csaux, firstset);
326 if (e1 == 0) return 0; /* 'e1' ensures that first can be used */
327 else if ((e1 | e2) & 2) /* one of the children has a matchtime? */
328 return 2; /* pattern has a matchtime capture */
329 else return e2; /* else depends on 'e2' */
330 }
331 }
332 case TRep: {
333 getfirst(sib1(tree), follow, firstset);
334 loopset(i, firstset->cs[i] |= follow->cs[i]);
335 return 1; /* accept the empty string */
336 }
337 case TCapture: case TGrammar: case TRule: {
338 /* return getfirst(sib1(tree), follow, firstset); */
339 tree = sib1(tree); goto tailcall;
340 }
341 case TRunTime: { /* function invalidates any follow info. */
342 int e = getfirst(sib1(tree), fullset, firstset);
343 if (e) return 2; /* function is not "protected"? */
344 else return 0; /* pattern inside capture ensures first can be used */
345 }
346 case TCall: {
347 /* return getfirst(sib2(tree), follow, firstset); */
348 tree = sib2(tree); goto tailcall;
349 }
350 case TAnd: {
351 int e = getfirst(sib1(tree), follow, firstset);
352 loopset(i, firstset->cs[i] &= follow->cs[i]);
353 return e;
354 }
355 case TNot: {
356 if (tocharset(sib1(tree), firstset)) {
357 cs_complement(firstset);
358 return 1;
359 }
360 /* else go through */
361 }
362 case TBehind: { /* instruction gives no new information */
363 /* call 'getfirst' only to check for math-time captures */
364 int e = getfirst(sib1(tree), follow, firstset);
365 loopset(i, firstset->cs[i] = follow->cs[i]); /* uses follow */
366 return e | 1; /* always can accept the empty string */
367 }
368 default: assert(0); return 0;
369 }
370 }
371
372
373 /*
374 ** If 'headfail(tree)' true, then 'tree' can fail only depending on the
375 ** next character of the subject.
376 */
headfail(TTree * tree)377 static int headfail (TTree *tree) {
378 tailcall:
379 switch (tree->tag) {
380 case TChar: case TSet: case TAny: case TFalse:
381 return 1;
382 case TTrue: case TRep: case TRunTime: case TNot:
383 case TBehind:
384 return 0;
385 case TCapture: case TGrammar: case TRule: case TAnd:
386 tree = sib1(tree); goto tailcall; /* return headfail(sib1(tree)); */
387 case TCall:
388 tree = sib2(tree); goto tailcall; /* return headfail(sib2(tree)); */
389 case TSeq:
390 if (!nofail(sib2(tree))) return 0;
391 /* else return headfail(sib1(tree)); */
392 tree = sib1(tree); goto tailcall;
393 case TChoice:
394 if (!headfail(sib1(tree))) return 0;
395 /* else return headfail(sib2(tree)); */
396 tree = sib2(tree); goto tailcall;
397 default: assert(0); return 0;
398 }
399 }
400
401
402 /*
403 ** Check whether the code generation for the given tree can benefit
404 ** from a follow set (to avoid computing the follow set when it is
405 ** not needed)
406 */
needfollow(TTree * tree)407 static int needfollow (TTree *tree) {
408 tailcall:
409 switch (tree->tag) {
410 case TChar: case TSet: case TAny:
411 case TFalse: case TTrue: case TAnd: case TNot:
412 case TRunTime: case TGrammar: case TCall: case TBehind:
413 return 0;
414 case TChoice: case TRep:
415 return 1;
416 case TCapture:
417 tree = sib1(tree); goto tailcall;
418 case TSeq:
419 tree = sib2(tree); goto tailcall;
420 default: assert(0); return 0;
421 }
422 }
423
424 /* }====================================================== */
425
426
427
428 /*
429 ** {======================================================
430 ** Code generation
431 ** =======================================================
432 */
433
434
435 /*
436 ** size of an instruction
437 */
sizei(const Instruction * i)438 int sizei (const Instruction *i) {
439 switch((Opcode)i->i.code) {
440 case ISet: case ISpan: return CHARSETINSTSIZE;
441 case ITestSet: return CHARSETINSTSIZE + 1;
442 case ITestChar: case ITestAny: case IChoice: case IJmp: case ICall:
443 case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit:
444 return 2;
445 default: return 1;
446 }
447 }
448
449
450 /*
451 ** state for the compiler
452 */
453 typedef struct CompileState {
454 Pattern *p; /* pattern being compiled */
455 int ncode; /* next position in p->code to be filled */
456 lua_State *L;
457 } CompileState;
458
459
460 /*
461 ** code generation is recursive; 'opt' indicates that the code is being
462 ** generated as the last thing inside an optional pattern (so, if that
463 ** code is optional too, it can reuse the 'IChoice' already in place for
464 ** the outer pattern). 'tt' points to a previous test protecting this
465 ** code (or NOINST). 'fl' is the follow set of the pattern.
466 */
467 static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
468 const Charset *fl);
469
470
realloccode(lua_State * L,Pattern * p,int nsize)471 void realloccode (lua_State *L, Pattern *p, int nsize) {
472 void *ud;
473 lua_Alloc f = lua_getallocf(L, &ud);
474 void *newblock = f(ud, p->code, p->codesize * sizeof(Instruction),
475 nsize * sizeof(Instruction));
476 if (newblock == NULL && nsize > 0)
477 luaL_error(L, "not enough memory");
478 p->code = (Instruction *)newblock;
479 p->codesize = nsize;
480 }
481
482
nextinstruction(CompileState * compst)483 static int nextinstruction (CompileState *compst) {
484 int size = compst->p->codesize;
485 if (compst->ncode >= size)
486 realloccode(compst->L, compst->p, size * 2);
487 return compst->ncode++;
488 }
489
490
491 #define getinstr(cs,i) ((cs)->p->code[i])
492
493
addinstruction(CompileState * compst,Opcode op,int aux)494 static int addinstruction (CompileState *compst, Opcode op, int aux) {
495 int i = nextinstruction(compst);
496 getinstr(compst, i).i.code = op;
497 getinstr(compst, i).i.aux = aux;
498 return i;
499 }
500
501
502 /*
503 ** Add an instruction followed by space for an offset (to be set later)
504 */
addoffsetinst(CompileState * compst,Opcode op)505 static int addoffsetinst (CompileState *compst, Opcode op) {
506 int i = addinstruction(compst, op, 0); /* instruction */
507 addinstruction(compst, (Opcode)0, 0); /* open space for offset */
508 assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2);
509 return i;
510 }
511
512
513 /*
514 ** Set the offset of an instruction
515 */
setoffset(CompileState * compst,int instruction,int offset)516 static void setoffset (CompileState *compst, int instruction, int offset) {
517 getinstr(compst, instruction + 1).offset = offset;
518 }
519
520
521 /*
522 ** Add a capture instruction:
523 ** 'op' is the capture instruction; 'cap' the capture kind;
524 ** 'key' the key into ktable; 'aux' is the optional capture offset
525 **
526 */
addinstcap(CompileState * compst,Opcode op,int cap,int key,int aux)527 static int addinstcap (CompileState *compst, Opcode op, int cap, int key,
528 int aux) {
529 int i = addinstruction(compst, op, joinkindoff(cap, aux));
530 getinstr(compst, i).i.key = key;
531 return i;
532 }
533
534
535 #define gethere(compst) ((compst)->ncode)
536
537 #define target(code,i) ((i) + code[i + 1].offset)
538
539
540 /*
541 ** Patch 'instruction' to jump to 'target'
542 */
jumptothere(CompileState * compst,int instruction,int target)543 static void jumptothere (CompileState *compst, int instruction, int target) {
544 if (instruction >= 0)
545 setoffset(compst, instruction, target - instruction);
546 }
547
548
549 /*
550 ** Patch 'instruction' to jump to current position
551 */
jumptohere(CompileState * compst,int instruction)552 static void jumptohere (CompileState *compst, int instruction) {
553 jumptothere(compst, instruction, gethere(compst));
554 }
555
556
557 /*
558 ** Code an IChar instruction, or IAny if there is an equivalent
559 ** test dominating it
560 */
codechar(CompileState * compst,int c,int tt)561 static void codechar (CompileState *compst, int c, int tt) {
562 if (tt >= 0 && getinstr(compst, tt).i.code == ITestChar &&
563 getinstr(compst, tt).i.aux == c)
564 addinstruction(compst, IAny, 0);
565 else
566 addinstruction(compst, IChar, c);
567 }
568
569
570 /*
571 ** Add a charset posfix to an instruction
572 */
addcharset(CompileState * compst,const byte * cs)573 static void addcharset (CompileState *compst, const byte *cs) {
574 int p = gethere(compst);
575 int i;
576 for (i = 0; i < (int)CHARSETINSTSIZE - 1; i++)
577 nextinstruction(compst); /* space for buffer */
578 /* fill buffer with charset */
579 loopset(j, getinstr(compst, p).buff[j] = cs[j]);
580 }
581
582
583 /*
584 ** code a char set, optimizing unit sets for IChar, "complete"
585 ** sets for IAny, and empty sets for IFail; also use an IAny
586 ** when instruction is dominated by an equivalent test.
587 */
codecharset(CompileState * compst,const byte * cs,int tt)588 static void codecharset (CompileState *compst, const byte *cs, int tt) {
589 int c = 0; /* (=) to avoid warnings */
590 Opcode op = charsettype(cs, &c);
591 switch (op) {
592 case IChar: codechar(compst, c, tt); break;
593 case ISet: { /* non-trivial set? */
594 if (tt >= 0 && getinstr(compst, tt).i.code == ITestSet &&
595 cs_equal(cs, getinstr(compst, tt + 2).buff))
596 addinstruction(compst, IAny, 0);
597 else {
598 addinstruction(compst, ISet, 0);
599 addcharset(compst, cs);
600 }
601 break;
602 }
603 default: addinstruction(compst, op, c); break;
604 }
605 }
606
607
608 /*
609 ** code a test set, optimizing unit sets for ITestChar, "complete"
610 ** sets for ITestAny, and empty sets for IJmp (always fails).
611 ** 'e' is true iff test should accept the empty string. (Test
612 ** instructions in the current VM never accept the empty string.)
613 */
codetestset(CompileState * compst,Charset * cs,int e)614 static int codetestset (CompileState *compst, Charset *cs, int e) {
615 if (e) return NOINST; /* no test */
616 else {
617 int c = 0;
618 Opcode op = charsettype(cs->cs, &c);
619 switch (op) {
620 case IFail: return addoffsetinst(compst, IJmp); /* always jump */
621 case IAny: return addoffsetinst(compst, ITestAny);
622 case IChar: {
623 int i = addoffsetinst(compst, ITestChar);
624 getinstr(compst, i).i.aux = c;
625 return i;
626 }
627 case ISet: {
628 int i = addoffsetinst(compst, ITestSet);
629 addcharset(compst, cs->cs);
630 return i;
631 }
632 default: assert(0); return 0;
633 }
634 }
635 }
636
637
638 /*
639 ** Find the final destination of a sequence of jumps
640 */
finaltarget(Instruction * code,int i)641 static int finaltarget (Instruction *code, int i) {
642 while (code[i].i.code == IJmp)
643 i = target(code, i);
644 return i;
645 }
646
647
648 /*
649 ** final label (after traversing any jumps)
650 */
finallabel(Instruction * code,int i)651 static int finallabel (Instruction *code, int i) {
652 return finaltarget(code, target(code, i));
653 }
654
655
656 /*
657 ** <behind(p)> == behind n; <p> (where n = fixedlen(p))
658 */
codebehind(CompileState * compst,TTree * tree)659 static void codebehind (CompileState *compst, TTree *tree) {
660 if (tree->u.n > 0)
661 addinstruction(compst, IBehind, tree->u.n);
662 codegen(compst, sib1(tree), 0, NOINST, fullset);
663 }
664
665
666 /*
667 ** Choice; optimizations:
668 ** - when p1 is headfail or
669 ** when first(p1) and first(p2) are disjoint, than
670 ** a character not in first(p1) cannot go to p1, and a character
671 ** in first(p1) cannot go to p2 (at it is not in first(p2)).
672 ** (The optimization is not valid if p1 accepts the empty string,
673 ** as then there is no character at all...)
674 ** - when p2 is empty and opt is true; a IPartialCommit can reuse
675 ** the Choice already active in the stack.
676 */
codechoice(CompileState * compst,TTree * p1,TTree * p2,int opt,const Charset * fl)677 static void codechoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
678 const Charset *fl) {
679 int emptyp2 = (p2->tag == TTrue);
680 Charset cs1, cs2;
681 int e1 = getfirst(p1, fullset, &cs1);
682 if (headfail(p1) ||
683 (!e1 && (getfirst(p2, fl, &cs2), cs_disjoint(&cs1, &cs2)))) {
684 /* <p1 / p2> == test (fail(p1)) -> L1 ; p1 ; jmp L2; L1: p2; L2: */
685 int test = codetestset(compst, &cs1, 0);
686 int jmp = NOINST;
687 codegen(compst, p1, 0, test, fl);
688 if (!emptyp2)
689 jmp = addoffsetinst(compst, IJmp);
690 jumptohere(compst, test);
691 codegen(compst, p2, opt, NOINST, fl);
692 jumptohere(compst, jmp);
693 }
694 else if (opt && emptyp2) {
695 /* p1? == IPartialCommit; p1 */
696 jumptohere(compst, addoffsetinst(compst, IPartialCommit));
697 codegen(compst, p1, 1, NOINST, fullset);
698 }
699 else {
700 /* <p1 / p2> ==
701 test(first(p1)) -> L1; choice L1; <p1>; commit L2; L1: <p2>; L2: */
702 int pcommit;
703 int test = codetestset(compst, &cs1, e1);
704 int pchoice = addoffsetinst(compst, IChoice);
705 codegen(compst, p1, emptyp2, test, fullset);
706 pcommit = addoffsetinst(compst, ICommit);
707 jumptohere(compst, pchoice);
708 jumptohere(compst, test);
709 codegen(compst, p2, opt, NOINST, fl);
710 jumptohere(compst, pcommit);
711 }
712 }
713
714
715 /*
716 ** And predicate
717 ** optimization: fixedlen(p) = n ==> <&p> == <p>; behind n
718 ** (valid only when 'p' has no captures)
719 */
codeand(CompileState * compst,TTree * tree,int tt)720 static void codeand (CompileState *compst, TTree *tree, int tt) {
721 int n = fixedlen(tree);
722 if (n >= 0 && n <= MAXBEHIND && !hascaptures(tree)) {
723 codegen(compst, tree, 0, tt, fullset);
724 if (n > 0)
725 addinstruction(compst, IBehind, n);
726 }
727 else { /* default: Choice L1; p1; BackCommit L2; L1: Fail; L2: */
728 int pcommit;
729 int pchoice = addoffsetinst(compst, IChoice);
730 codegen(compst, tree, 0, tt, fullset);
731 pcommit = addoffsetinst(compst, IBackCommit);
732 jumptohere(compst, pchoice);
733 addinstruction(compst, IFail, 0);
734 jumptohere(compst, pcommit);
735 }
736 }
737
738
739 /*
740 ** Captures: if pattern has fixed (and not too big) length, and it
741 ** has no nested captures, use a single IFullCapture instruction
742 ** after the match; otherwise, enclose the pattern with OpenCapture -
743 ** CloseCapture.
744 */
codecapture(CompileState * compst,TTree * tree,int tt,const Charset * fl)745 static void codecapture (CompileState *compst, TTree *tree, int tt,
746 const Charset *fl) {
747 int len = fixedlen(sib1(tree));
748 if (len >= 0 && len <= MAXOFF && !hascaptures(sib1(tree))) {
749 codegen(compst, sib1(tree), 0, tt, fl);
750 addinstcap(compst, IFullCapture, tree->cap, tree->key, len);
751 }
752 else {
753 addinstcap(compst, IOpenCapture, tree->cap, tree->key, 0);
754 codegen(compst, sib1(tree), 0, tt, fl);
755 addinstcap(compst, ICloseCapture, Cclose, 0, 0);
756 }
757 }
758
759
coderuntime(CompileState * compst,TTree * tree,int tt)760 static void coderuntime (CompileState *compst, TTree *tree, int tt) {
761 addinstcap(compst, IOpenCapture, Cgroup, tree->key, 0);
762 codegen(compst, sib1(tree), 0, tt, fullset);
763 addinstcap(compst, ICloseRunTime, Cclose, 0, 0);
764 }
765
766
767 /*
768 ** Repetion; optimizations:
769 ** When pattern is a charset, can use special instruction ISpan.
770 ** When pattern is head fail, or if it starts with characters that
771 ** are disjoint from what follows the repetions, a simple test
772 ** is enough (a fail inside the repetition would backtrack to fail
773 ** again in the following pattern, so there is no need for a choice).
774 ** When 'opt' is true, the repetion can reuse the Choice already
775 ** active in the stack.
776 */
coderep(CompileState * compst,TTree * tree,int opt,const Charset * fl)777 static void coderep (CompileState *compst, TTree *tree, int opt,
778 const Charset *fl) {
779 Charset st;
780 if (tocharset(tree, &st)) {
781 addinstruction(compst, ISpan, 0);
782 addcharset(compst, st.cs);
783 }
784 else {
785 int e1 = getfirst(tree, fullset, &st);
786 if (headfail(tree) || (!e1 && cs_disjoint(&st, fl))) {
787 /* L1: test (fail(p1)) -> L2; <p>; jmp L1; L2: */
788 int jmp;
789 int test = codetestset(compst, &st, 0);
790 codegen(compst, tree, 0, test, fullset);
791 jmp = addoffsetinst(compst, IJmp);
792 jumptohere(compst, test);
793 jumptothere(compst, jmp, test);
794 }
795 else {
796 /* test(fail(p1)) -> L2; choice L2; L1: <p>; partialcommit L1; L2: */
797 /* or (if 'opt'): partialcommit L1; L1: <p>; partialcommit L1; */
798 int commit, l2;
799 int test = codetestset(compst, &st, e1);
800 int pchoice = NOINST;
801 if (opt)
802 jumptohere(compst, addoffsetinst(compst, IPartialCommit));
803 else
804 pchoice = addoffsetinst(compst, IChoice);
805 l2 = gethere(compst);
806 codegen(compst, tree, 0, NOINST, fullset);
807 commit = addoffsetinst(compst, IPartialCommit);
808 jumptothere(compst, commit, l2);
809 jumptohere(compst, pchoice);
810 jumptohere(compst, test);
811 }
812 }
813 }
814
815
816 /*
817 ** Not predicate; optimizations:
818 ** In any case, if first test fails, 'not' succeeds, so it can jump to
819 ** the end. If pattern is headfail, that is all (it cannot fail
820 ** in other parts); this case includes 'not' of simple sets. Otherwise,
821 ** use the default code (a choice plus a failtwice).
822 */
codenot(CompileState * compst,TTree * tree)823 static void codenot (CompileState *compst, TTree *tree) {
824 Charset st;
825 int e = getfirst(tree, fullset, &st);
826 int test = codetestset(compst, &st, e);
827 if (headfail(tree)) /* test (fail(p1)) -> L1; fail; L1: */
828 addinstruction(compst, IFail, 0);
829 else {
830 /* test(fail(p))-> L1; choice L1; <p>; failtwice; L1: */
831 int pchoice = addoffsetinst(compst, IChoice);
832 codegen(compst, tree, 0, NOINST, fullset);
833 addinstruction(compst, IFailTwice, 0);
834 jumptohere(compst, pchoice);
835 }
836 jumptohere(compst, test);
837 }
838
839
840 /*
841 ** change open calls to calls, using list 'positions' to find
842 ** correct offsets; also optimize tail calls
843 */
correctcalls(CompileState * compst,int * positions,int from,int to)844 static void correctcalls (CompileState *compst, int *positions,
845 int from, int to) {
846 int i;
847 Instruction *code = compst->p->code;
848 for (i = from; i < to; i += sizei(&code[i])) {
849 if (code[i].i.code == IOpenCall) {
850 int n = code[i].i.key; /* rule number */
851 int rule = positions[n]; /* rule position */
852 assert(rule == from || code[rule - 1].i.code == IRet);
853 if (code[finaltarget(code, i + 2)].i.code == IRet) /* call; ret ? */
854 code[i].i.code = IJmp; /* tail call */
855 else
856 code[i].i.code = ICall;
857 jumptothere(compst, i, rule); /* call jumps to respective rule */
858 }
859 }
860 assert(i == to);
861 }
862
863
864 /*
865 ** Code for a grammar:
866 ** call L1; jmp L2; L1: rule 1; ret; rule 2; ret; ...; L2:
867 */
codegrammar(CompileState * compst,TTree * grammar)868 static void codegrammar (CompileState *compst, TTree *grammar) {
869 int positions[MAXRULES];
870 int rulenumber = 0;
871 TTree *rule;
872 int firstcall = addoffsetinst(compst, ICall); /* call initial rule */
873 int jumptoend = addoffsetinst(compst, IJmp); /* jump to the end */
874 int start = gethere(compst); /* here starts the initial rule */
875 jumptohere(compst, firstcall);
876 for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) {
877 positions[rulenumber++] = gethere(compst); /* save rule position */
878 codegen(compst, sib1(rule), 0, NOINST, fullset); /* code rule */
879 addinstruction(compst, IRet, 0);
880 }
881 assert(rule->tag == TTrue);
882 jumptohere(compst, jumptoend);
883 correctcalls(compst, positions, start, gethere(compst));
884 }
885
886
codecall(CompileState * compst,TTree * call)887 static void codecall (CompileState *compst, TTree *call) {
888 int c = addoffsetinst(compst, IOpenCall); /* to be corrected later */
889 getinstr(compst, c).i.key = sib2(call)->cap; /* rule number */
890 assert(sib2(call)->tag == TRule);
891 }
892
893
894 /*
895 ** Code first child of a sequence
896 ** (second child is called in-place to allow tail call)
897 ** Return 'tt' for second child
898 */
codeseq1(CompileState * compst,TTree * p1,TTree * p2,int tt,const Charset * fl)899 static int codeseq1 (CompileState *compst, TTree *p1, TTree *p2,
900 int tt, const Charset *fl) {
901 if (needfollow(p1)) {
902 Charset fl1;
903 getfirst(p2, fl, &fl1); /* p1 follow is p2 first */
904 codegen(compst, p1, 0, tt, &fl1);
905 }
906 else /* use 'fullset' as follow */
907 codegen(compst, p1, 0, tt, fullset);
908 if (fixedlen(p1) != 0) /* can 'p1' consume anything? */
909 return NOINST; /* invalidate test */
910 else return tt; /* else 'tt' still protects sib2 */
911 }
912
913
914 /*
915 ** Main code-generation function: dispatch to auxiliar functions
916 ** according to kind of tree. ('needfollow' should return true
917 ** only for consructions that use 'fl'.)
918 */
codegen(CompileState * compst,TTree * tree,int opt,int tt,const Charset * fl)919 static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
920 const Charset *fl) {
921 tailcall:
922 switch (tree->tag) {
923 case TChar: codechar(compst, tree->u.n, tt); break;
924 case TAny: addinstruction(compst, IAny, 0); break;
925 case TSet: codecharset(compst, treebuffer(tree), tt); break;
926 case TTrue: break;
927 case TFalse: addinstruction(compst, IFail, 0); break;
928 case TChoice: codechoice(compst, sib1(tree), sib2(tree), opt, fl); break;
929 case TRep: coderep(compst, sib1(tree), opt, fl); break;
930 case TBehind: codebehind(compst, tree); break;
931 case TNot: codenot(compst, sib1(tree)); break;
932 case TAnd: codeand(compst, sib1(tree), tt); break;
933 case TCapture: codecapture(compst, tree, tt, fl); break;
934 case TRunTime: coderuntime(compst, tree, tt); break;
935 case TGrammar: codegrammar(compst, tree); break;
936 case TCall: codecall(compst, tree); break;
937 case TSeq: {
938 tt = codeseq1(compst, sib1(tree), sib2(tree), tt, fl); /* code 'p1' */
939 /* codegen(compst, p2, opt, tt, fl); */
940 tree = sib2(tree); goto tailcall;
941 }
942 default: assert(0);
943 }
944 }
945
946
947 /*
948 ** Optimize jumps and other jump-like instructions.
949 ** * Update labels of instructions with labels to their final
950 ** destinations (e.g., choice L1; ... L1: jmp L2: becomes
951 ** choice L2)
952 ** * Jumps to other instructions that do jumps become those
953 ** instructions (e.g., jump to return becomes a return; jump
954 ** to commit becomes a commit)
955 */
peephole(CompileState * compst)956 static void peephole (CompileState *compst) {
957 Instruction *code = compst->p->code;
958 int i;
959 for (i = 0; i < compst->ncode; i += sizei(&code[i])) {
960 redo:
961 switch (code[i].i.code) {
962 case IChoice: case ICall: case ICommit: case IPartialCommit:
963 case IBackCommit: case ITestChar: case ITestSet:
964 case ITestAny: { /* instructions with labels */
965 jumptothere(compst, i, finallabel(code, i)); /* optimize label */
966 break;
967 }
968 case IJmp: {
969 int ft = finaltarget(code, i);
970 switch (code[ft].i.code) { /* jumping to what? */
971 case IRet: case IFail: case IFailTwice:
972 case IEnd: { /* instructions with unconditional implicit jumps */
973 code[i] = code[ft]; /* jump becomes that instruction */
974 code[i + 1].i.code = IAny; /* 'no-op' for target position */
975 break;
976 }
977 case ICommit: case IPartialCommit:
978 case IBackCommit: { /* inst. with unconditional explicit jumps */
979 int fft = finallabel(code, ft);
980 code[i] = code[ft]; /* jump becomes that instruction... */
981 jumptothere(compst, i, fft); /* but must correct its offset */
982 goto redo; /* reoptimize its label */
983 }
984 default: {
985 jumptothere(compst, i, ft); /* optimize label */
986 break;
987 }
988 }
989 break;
990 }
991 default: break;
992 }
993 }
994 assert(code[i - 1].i.code == IEnd);
995 }
996
997
998 /*
999 ** Compile a pattern
1000 */
compile(lua_State * L,Pattern * p)1001 Instruction *compile (lua_State *L, Pattern *p) {
1002 CompileState compst;
1003 compst.p = p; compst.ncode = 0; compst.L = L;
1004 realloccode(L, p, 2); /* minimum initial size */
1005 codegen(&compst, p->tree, 0, NOINST, fullset);
1006 addinstruction(&compst, IEnd, 0);
1007 realloccode(L, p, compst.ncode); /* set final size */
1008 peephole(&compst);
1009 return p->code;
1010 }
1011
1012
1013 /* }====================================================== */
1014
1015