1 /*
2 ** $Id: lpvm.c $
3 ** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license)
4 */
5
6 #include <limits.h>
7 #include <string.h>
8
9
10 #include "lua.h"
11 #include "lauxlib.h"
12
13 #include "lpcap.h"
14 #include "lptypes.h"
15 #include "lpvm.h"
16 #include "lpprint.h"
17
18
19 /* initial size for call/backtrack stack */
20 #if !defined(INITBACK)
21 #define INITBACK MAXBACK
22 #endif
23
24
25 #define getoffset(p) (((p) + 1)->offset)
26
27 static const Instruction giveup = {{IGiveup, 0, 0}};
28
29
30 /*
31 ** {======================================================
32 ** Virtual Machine
33 ** =======================================================
34 */
35
36
37 typedef struct Stack {
38 const char *s; /* saved position (or NULL for calls) */
39 const Instruction *p; /* next instruction */
40 int caplevel;
41 } Stack;
42
43
44 #define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop)))
45
46
47 /*
48 ** Ensures the size of array 'capture' (with size '*capsize' and
49 ** 'captop' elements being used) is enough to accomodate 'n' extra
50 ** elements plus one. (Because several opcodes add stuff to the capture
51 ** array, it is simpler to ensure the array always has at least one free
52 ** slot upfront and check its size later.)
53 */
growcap(lua_State * L,Capture * capture,int * capsize,int captop,int n,int ptop)54 static Capture *growcap (lua_State *L, Capture *capture, int *capsize,
55 int captop, int n, int ptop) {
56 if (*capsize - captop > n)
57 return capture; /* no need to grow array */
58 else { /* must grow */
59 Capture *newc;
60 int newsize = captop + n + 1; /* minimum size needed */
61 if (newsize < INT_MAX/((int)sizeof(Capture) * 2))
62 newsize *= 2; /* twice that size, if not too big */
63 else if (newsize >= INT_MAX/((int)sizeof(Capture)))
64 luaL_error(L, "too many captures");
65 newc = (Capture *)lua_newuserdata(L, newsize * sizeof(Capture));
66 memcpy(newc, capture, captop * sizeof(Capture));
67 *capsize = newsize;
68 lua_replace(L, caplistidx(ptop));
69 return newc;
70 }
71 }
72
73
74 /*
75 ** Double the size of the stack
76 */
doublestack(lua_State * L,Stack ** stacklimit,int ptop)77 static Stack *doublestack (lua_State *L, Stack **stacklimit, int ptop) {
78 Stack *stack = getstackbase(L, ptop);
79 Stack *newstack;
80 int n = *stacklimit - stack; /* current stack size */
81 int max, newn;
82 lua_getfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX);
83 max = lua_tointeger(L, -1); /* maximum allowed size */
84 lua_pop(L, 1);
85 if (n >= max) /* already at maximum size? */
86 luaL_error(L, "backtrack stack overflow (current limit is %d)", max);
87 newn = 2 * n; /* new size */
88 if (newn > max) newn = max;
89 newstack = (Stack *)lua_newuserdata(L, newn * sizeof(Stack));
90 memcpy(newstack, stack, n * sizeof(Stack));
91 lua_replace(L, stackidx(ptop));
92 *stacklimit = newstack + newn;
93 return newstack + n; /* return next position */
94 }
95
96
97 /*
98 ** Interpret the result of a dynamic capture: false -> fail;
99 ** true -> keep current position; number -> next position.
100 ** Return new subject position. 'fr' is stack index where
101 ** is the result; 'curr' is current subject position; 'limit'
102 ** is subject's size.
103 */
resdyncaptures(lua_State * L,int fr,int curr,int limit)104 static int resdyncaptures (lua_State *L, int fr, int curr, int limit) {
105 lua_Integer res;
106 if (!lua_toboolean(L, fr)) { /* false value? */
107 lua_settop(L, fr - 1); /* remove results */
108 return -1; /* and fail */
109 }
110 else if (lua_isboolean(L, fr)) /* true? */
111 res = curr; /* keep current position */
112 else {
113 res = lua_tointeger(L, fr) - 1; /* new position */
114 if (res < curr || res > limit)
115 luaL_error(L, "invalid position returned by match-time capture");
116 }
117 lua_remove(L, fr); /* remove first result (offset) */
118 return res;
119 }
120
121
122 /*
123 ** Add capture values returned by a dynamic capture to the list
124 ** 'capture', nested inside a group. 'fd' indexes the first capture
125 ** value, 'n' is the number of values (at least 1). The open group
126 ** capture is already in 'capture', before the place for the new entries.
127 */
adddyncaptures(const char * s,Capture * capture,int n,int fd)128 static void adddyncaptures (const char *s, Capture *capture, int n, int fd) {
129 int i;
130 assert(capture[-1].kind == Cgroup && capture[-1].siz == 0);
131 capture[-1].idx = 0; /* make group capture an anonymous group */
132 for (i = 0; i < n; i++) { /* add runtime captures */
133 capture[i].kind = Cruntime;
134 capture[i].siz = 1; /* mark it as closed */
135 capture[i].idx = fd + i; /* stack index of capture value */
136 capture[i].s = s;
137 }
138 capture[n].kind = Cclose; /* close group */
139 capture[n].siz = 1;
140 capture[n].s = s;
141 }
142
143
144 /*
145 ** Remove dynamic captures from the Lua stack (called in case of failure)
146 */
removedyncap(lua_State * L,Capture * capture,int level,int last)147 static int removedyncap (lua_State *L, Capture *capture,
148 int level, int last) {
149 int id = finddyncap(capture + level, capture + last); /* index of 1st cap. */
150 int top = lua_gettop(L);
151 if (id == 0) return 0; /* no dynamic captures? */
152 lua_settop(L, id - 1); /* remove captures */
153 return top - id + 1; /* number of values removed */
154 }
155
156
157 /*
158 ** Opcode interpreter
159 */
match(lua_State * L,const char * o,const char * s,const char * e,Instruction * op,Capture * capture,int ptop)160 const char *match (lua_State *L, const char *o, const char *s, const char *e,
161 Instruction *op, Capture *capture, int ptop) {
162 Stack stackbase[INITBACK];
163 Stack *stacklimit = stackbase + INITBACK;
164 Stack *stack = stackbase; /* point to first empty slot in stack */
165 int capsize = INITCAPSIZE;
166 int captop = 0; /* point to first empty slot in captures */
167 int ndyncap = 0; /* number of dynamic captures (in Lua stack) */
168 const Instruction *p = op; /* current instruction */
169 stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack++;
170 lua_pushlightuserdata(L, stackbase);
171 for (;;) {
172 #if defined(DEBUG)
173 printf("-------------------------------------\n");
174 printcaplist(capture, capture + captop);
175 printf("s: |%s| stck:%d, dyncaps:%d, caps:%d ",
176 s, (int)(stack - getstackbase(L, ptop)), ndyncap, captop);
177 printinst(op, p);
178 #endif
179 assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop);
180 switch ((Opcode)p->i.code) {
181 case IEnd: {
182 assert(stack == getstackbase(L, ptop) + 1);
183 capture[captop].kind = Cclose;
184 capture[captop].s = NULL;
185 return s;
186 }
187 case IGiveup: {
188 assert(stack == getstackbase(L, ptop));
189 return NULL;
190 }
191 case IRet: {
192 assert(stack > getstackbase(L, ptop) && (stack - 1)->s == NULL);
193 p = (--stack)->p;
194 continue;
195 }
196 case IAny: {
197 if (s < e) { p++; s++; }
198 else goto fail;
199 continue;
200 }
201 case ITestAny: {
202 if (s < e) p += 2;
203 else p += getoffset(p);
204 continue;
205 }
206 case IChar: {
207 if ((byte)*s == p->i.aux && s < e) { p++; s++; }
208 else goto fail;
209 continue;
210 }
211 case ITestChar: {
212 if ((byte)*s == p->i.aux && s < e) p += 2;
213 else p += getoffset(p);
214 continue;
215 }
216 case ISet: {
217 int c = (byte)*s;
218 if (testchar((p+1)->buff, c) && s < e)
219 { p += CHARSETINSTSIZE; s++; }
220 else goto fail;
221 continue;
222 }
223 case ITestSet: {
224 int c = (byte)*s;
225 if (testchar((p + 2)->buff, c) && s < e)
226 p += 1 + CHARSETINSTSIZE;
227 else p += getoffset(p);
228 continue;
229 }
230 case IBehind: {
231 int n = p->i.aux;
232 if (n > s - o) goto fail;
233 s -= n; p++;
234 continue;
235 }
236 case ISpan: {
237 for (; s < e; s++) {
238 int c = (byte)*s;
239 if (!testchar((p+1)->buff, c)) break;
240 }
241 p += CHARSETINSTSIZE;
242 continue;
243 }
244 case IJmp: {
245 p += getoffset(p);
246 continue;
247 }
248 case IChoice: {
249 if (stack == stacklimit)
250 stack = doublestack(L, &stacklimit, ptop);
251 stack->p = p + getoffset(p);
252 stack->s = s;
253 stack->caplevel = captop;
254 stack++;
255 p += 2;
256 continue;
257 }
258 case ICall: {
259 if (stack == stacklimit)
260 stack = doublestack(L, &stacklimit, ptop);
261 stack->s = NULL;
262 stack->p = p + 2; /* save return address */
263 stack++;
264 p += getoffset(p);
265 continue;
266 }
267 case ICommit: {
268 assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
269 stack--;
270 p += getoffset(p);
271 continue;
272 }
273 case IPartialCommit: {
274 assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
275 (stack - 1)->s = s;
276 (stack - 1)->caplevel = captop;
277 p += getoffset(p);
278 continue;
279 }
280 case IBackCommit: {
281 assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
282 s = (--stack)->s;
283 captop = stack->caplevel;
284 p += getoffset(p);
285 continue;
286 }
287 case IFailTwice:
288 assert(stack > getstackbase(L, ptop));
289 stack--;
290 /* go through */
291 case IFail:
292 fail: { /* pattern failed: try to backtrack */
293 do { /* remove pending calls */
294 assert(stack > getstackbase(L, ptop));
295 s = (--stack)->s;
296 } while (s == NULL);
297 if (ndyncap > 0) /* is there matchtime captures? */
298 ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
299 captop = stack->caplevel;
300 p = stack->p;
301 #if defined(DEBUG)
302 printf("**FAIL**\n");
303 #endif
304 continue;
305 }
306 case ICloseRunTime: {
307 CapState cs;
308 int rem, res, n;
309 int fr = lua_gettop(L) + 1; /* stack index of first result */
310 cs.reclevel = 0; cs.L = L;
311 cs.s = o; cs.ocap = capture; cs.ptop = ptop;
312 n = runtimecap(&cs, capture + captop, s, &rem); /* call function */
313 captop -= n; /* remove nested captures */
314 ndyncap -= rem; /* update number of dynamic captures */
315 fr -= rem; /* 'rem' items were popped from Lua stack */
316 res = resdyncaptures(L, fr, s - o, e - o); /* get result */
317 if (res == -1) /* fail? */
318 goto fail;
319 s = o + res; /* else update current position */
320 n = lua_gettop(L) - fr + 1; /* number of new captures */
321 ndyncap += n; /* update number of dynamic captures */
322 if (n == 0) /* no new captures? */
323 captop--; /* remove open group */
324 else { /* new captures; keep original open group */
325 if (fr + n >= SHRT_MAX)
326 luaL_error(L, "too many results in match-time capture");
327 /* add new captures + close group to 'capture' list */
328 capture = growcap(L, capture, &capsize, captop, n + 1, ptop);
329 adddyncaptures(s, capture + captop, n, fr);
330 captop += n + 1; /* new captures + close group */
331 }
332 p++;
333 continue;
334 }
335 case ICloseCapture: {
336 const char *s1 = s;
337 assert(captop > 0);
338 /* if possible, turn capture into a full capture */
339 if (capture[captop - 1].siz == 0 &&
340 s1 - capture[captop - 1].s < UCHAR_MAX) {
341 capture[captop - 1].siz = s1 - capture[captop - 1].s + 1;
342 p++;
343 continue;
344 }
345 else {
346 capture[captop].siz = 1; /* mark entry as closed */
347 capture[captop].s = s;
348 goto pushcapture;
349 }
350 }
351 case IOpenCapture:
352 capture[captop].siz = 0; /* mark entry as open */
353 capture[captop].s = s;
354 goto pushcapture;
355 case IFullCapture:
356 capture[captop].siz = getoff(p) + 1; /* save capture size */
357 capture[captop].s = s - getoff(p);
358 /* goto pushcapture; */
359 pushcapture: {
360 capture[captop].idx = p->i.key;
361 capture[captop].kind = getkind(p);
362 captop++;
363 capture = growcap(L, capture, &capsize, captop, 0, ptop);
364 p++;
365 continue;
366 }
367 default: assert(0); return NULL;
368 }
369 }
370 }
371
372 /* }====================================================== */
373
374
375