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