xref: /illumos-gate/usr/src/uts/common/fs/zfs/lua/lstrlib.c (revision 84f27369)
1dfc11533SChris Williamson /*
2dfc11533SChris Williamson ** $Id: lstrlib.c,v 1.178.1.1 2013/04/12 18:48:47 roberto Exp $
3dfc11533SChris Williamson ** Standard library for string operations and pattern-matching
4dfc11533SChris Williamson ** See Copyright Notice in lua.h
5dfc11533SChris Williamson */
6dfc11533SChris Williamson 
7dfc11533SChris Williamson 
8dfc11533SChris Williamson #include <sys/ctype.h>
9dfc11533SChris Williamson #include <sys/zfs_context.h>
10dfc11533SChris Williamson 
11dfc11533SChris Williamson #define lstrlib_c
12dfc11533SChris Williamson #define LUA_LIB
13dfc11533SChris Williamson 
14dfc11533SChris Williamson #include "lua.h"
15dfc11533SChris Williamson 
16dfc11533SChris Williamson #include "lauxlib.h"
17dfc11533SChris Williamson #include "lualib.h"
18dfc11533SChris Williamson 
19dfc11533SChris Williamson 
20dfc11533SChris Williamson /*
21dfc11533SChris Williamson ** maximum number of captures that a pattern can do during
22dfc11533SChris Williamson ** pattern-matching. This limit is arbitrary.
23dfc11533SChris Williamson */
24dfc11533SChris Williamson #if !defined(LUA_MAXCAPTURES)
25dfc11533SChris Williamson #define LUA_MAXCAPTURES		32
26dfc11533SChris Williamson #endif
27dfc11533SChris Williamson 
28dfc11533SChris Williamson 
29dfc11533SChris Williamson /* macro to `unsign' a character */
30dfc11533SChris Williamson #define uchar(c)	((unsigned char)(c))
31dfc11533SChris Williamson 
32dfc11533SChris Williamson /*
33dfc11533SChris Williamson  * PATCHED: add missing character macros.
34dfc11533SChris Williamson  */
35dfc11533SChris Williamson #define tolower(C)	(((C) >= 'A' && (C) <= 'Z') ? (C) - 'A' + 'a' : (C))
36dfc11533SChris Williamson #define toupper(C)      (((C) >= 'a' && (C) <= 'z') ? (C) - 'a' + 'A': (C))
37dfc11533SChris Williamson #define isgraph(C)	((C) >= 0x21 && (C) <= 0x7E)
38dfc11533SChris Williamson #define ispunct(C)	(((C) >= 0x21 && (C) <= 0x2F) || \
39dfc11533SChris Williamson     ((C) >= 0x3A && (C) <= 0x40) || \
40dfc11533SChris Williamson     ((C) >= 0x5B && (C) <= 0x60) || \
41dfc11533SChris Williamson     ((C) >= 0x7B && (C) <= 0x7E))
42dfc11533SChris Williamson 
43dfc11533SChris Williamson /*
44dfc11533SChris Williamson  * The provided version of sprintf returns a char *, but str_format expects
45dfc11533SChris Williamson  * it to return the number of characters printed. This version has the expected
46dfc11533SChris Williamson  * behavior.
47dfc11533SChris Williamson  */
str_sprintf(char * buf,const char * fmt,...)48dfc11533SChris Williamson static size_t str_sprintf(char *buf, const char *fmt, ...) {
49dfc11533SChris Williamson   va_list args;
50dfc11533SChris Williamson   size_t len;
51dfc11533SChris Williamson 
52dfc11533SChris Williamson   va_start(args, fmt);
53dfc11533SChris Williamson   len = vsnprintf(buf, INT_MAX, fmt, args);
54dfc11533SChris Williamson   va_end(args);
55dfc11533SChris Williamson 
56dfc11533SChris Williamson   return len;
57dfc11533SChris Williamson }
58dfc11533SChris Williamson 
59dfc11533SChris Williamson 
str_len(lua_State * L)60dfc11533SChris Williamson static int str_len (lua_State *L) {
61dfc11533SChris Williamson   size_t l;
62dfc11533SChris Williamson   luaL_checklstring(L, 1, &l);
63dfc11533SChris Williamson   lua_pushinteger(L, (lua_Integer)l);
64dfc11533SChris Williamson   return 1;
65dfc11533SChris Williamson }
66dfc11533SChris Williamson 
67dfc11533SChris Williamson 
68dfc11533SChris Williamson /* translate a relative string position: negative means back from end */
posrelat(ptrdiff_t pos,size_t len)69dfc11533SChris Williamson static size_t posrelat (ptrdiff_t pos, size_t len) {
70dfc11533SChris Williamson   if (pos >= 0) return (size_t)pos;
71dfc11533SChris Williamson   else if (0u - (size_t)pos > len) return 0;
72dfc11533SChris Williamson   else return len - ((size_t)-pos) + 1;
73dfc11533SChris Williamson }
74dfc11533SChris Williamson 
75dfc11533SChris Williamson 
str_sub(lua_State * L)76dfc11533SChris Williamson static int str_sub (lua_State *L) {
77dfc11533SChris Williamson   size_t l;
78dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
79dfc11533SChris Williamson   size_t start = posrelat(luaL_checkinteger(L, 2), l);
80dfc11533SChris Williamson   size_t end = posrelat(luaL_optinteger(L, 3, -1), l);
81dfc11533SChris Williamson   if (start < 1) start = 1;
82dfc11533SChris Williamson   if (end > l) end = l;
83dfc11533SChris Williamson   if (start <= end)
84dfc11533SChris Williamson     lua_pushlstring(L, s + start - 1, end - start + 1);
85dfc11533SChris Williamson   else lua_pushliteral(L, "");
86dfc11533SChris Williamson   return 1;
87dfc11533SChris Williamson }
88dfc11533SChris Williamson 
89dfc11533SChris Williamson 
str_reverse(lua_State * L)90dfc11533SChris Williamson static int str_reverse (lua_State *L) {
91dfc11533SChris Williamson   size_t l, i;
92dfc11533SChris Williamson   luaL_Buffer b;
93dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
94dfc11533SChris Williamson   char *p = luaL_buffinitsize(L, &b, l);
95dfc11533SChris Williamson   for (i = 0; i < l; i++)
96dfc11533SChris Williamson     p[i] = s[l - i - 1];
97dfc11533SChris Williamson   luaL_pushresultsize(&b, l);
98dfc11533SChris Williamson   return 1;
99dfc11533SChris Williamson }
100dfc11533SChris Williamson 
101dfc11533SChris Williamson 
str_lower(lua_State * L)102dfc11533SChris Williamson static int str_lower (lua_State *L) {
103dfc11533SChris Williamson   size_t l;
104dfc11533SChris Williamson   size_t i;
105dfc11533SChris Williamson   luaL_Buffer b;
106dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
107dfc11533SChris Williamson   char *p = luaL_buffinitsize(L, &b, l);
108dfc11533SChris Williamson   for (i=0; i<l; i++)
109dfc11533SChris Williamson     p[i] = tolower(uchar(s[i]));
110dfc11533SChris Williamson   luaL_pushresultsize(&b, l);
111dfc11533SChris Williamson   return 1;
112dfc11533SChris Williamson }
113dfc11533SChris Williamson 
114dfc11533SChris Williamson 
str_upper(lua_State * L)115dfc11533SChris Williamson static int str_upper (lua_State *L) {
116dfc11533SChris Williamson   size_t l;
117dfc11533SChris Williamson   size_t i;
118dfc11533SChris Williamson   luaL_Buffer b;
119dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
120dfc11533SChris Williamson   char *p = luaL_buffinitsize(L, &b, l);
121dfc11533SChris Williamson   for (i=0; i<l; i++)
122dfc11533SChris Williamson     p[i] = toupper(uchar(s[i]));
123dfc11533SChris Williamson   luaL_pushresultsize(&b, l);
124dfc11533SChris Williamson   return 1;
125dfc11533SChris Williamson }
126dfc11533SChris Williamson 
127dfc11533SChris Williamson 
128dfc11533SChris Williamson /* reasonable limit to avoid arithmetic overflow */
129dfc11533SChris Williamson #define MAXSIZE		((~(size_t)0) >> 1)
130dfc11533SChris Williamson 
str_rep(lua_State * L)131dfc11533SChris Williamson static int str_rep (lua_State *L) {
132dfc11533SChris Williamson   size_t l, lsep;
133dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
134dfc11533SChris Williamson   int n = luaL_checkint(L, 2);
135dfc11533SChris Williamson   const char *sep = luaL_optlstring(L, 3, "", &lsep);
136dfc11533SChris Williamson   if (n <= 0) lua_pushliteral(L, "");
137dfc11533SChris Williamson   else if (l + lsep < l || l + lsep >= MAXSIZE / n)  /* may overflow? */
138dfc11533SChris Williamson     return luaL_error(L, "resulting string too large");
139dfc11533SChris Williamson   else {
140dfc11533SChris Williamson     size_t totallen = n * l + (n - 1) * lsep;
141dfc11533SChris Williamson     luaL_Buffer b;
142dfc11533SChris Williamson     char *p = luaL_buffinitsize(L, &b, totallen);
143dfc11533SChris Williamson     while (n-- > 1) {  /* first n-1 copies (followed by separator) */
144dfc11533SChris Williamson       memcpy(p, s, l * sizeof(char)); p += l;
145dfc11533SChris Williamson       if (lsep > 0) {  /* avoid empty 'memcpy' (may be expensive) */
146dfc11533SChris Williamson         memcpy(p, sep, lsep * sizeof(char)); p += lsep;
147dfc11533SChris Williamson       }
148dfc11533SChris Williamson     }
149dfc11533SChris Williamson     memcpy(p, s, l * sizeof(char));  /* last copy (not followed by separator) */
150dfc11533SChris Williamson     luaL_pushresultsize(&b, totallen);
151dfc11533SChris Williamson   }
152dfc11533SChris Williamson   return 1;
153dfc11533SChris Williamson }
154dfc11533SChris Williamson 
155dfc11533SChris Williamson 
str_byte(lua_State * L)156dfc11533SChris Williamson static int str_byte (lua_State *L) {
157dfc11533SChris Williamson   size_t l;
158dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &l);
159dfc11533SChris Williamson   size_t posi = posrelat(luaL_optinteger(L, 2, 1), l);
160dfc11533SChris Williamson   size_t pose = posrelat(luaL_optinteger(L, 3, posi), l);
161dfc11533SChris Williamson   int n, i;
162dfc11533SChris Williamson   if (posi < 1) posi = 1;
163dfc11533SChris Williamson   if (pose > l) pose = l;
164dfc11533SChris Williamson   if (posi > pose) return 0;  /* empty interval; return no values */
165dfc11533SChris Williamson   n = (int)(pose -  posi + 1);
166dfc11533SChris Williamson   if (posi + n <= pose)  /* (size_t -> int) overflow? */
167dfc11533SChris Williamson     return luaL_error(L, "string slice too long");
168dfc11533SChris Williamson   luaL_checkstack(L, n, "string slice too long");
169dfc11533SChris Williamson   for (i=0; i<n; i++)
170dfc11533SChris Williamson     lua_pushinteger(L, uchar(s[posi+i-1]));
171dfc11533SChris Williamson   return n;
172dfc11533SChris Williamson }
173dfc11533SChris Williamson 
174dfc11533SChris Williamson 
str_char(lua_State * L)175dfc11533SChris Williamson static int str_char (lua_State *L) {
176dfc11533SChris Williamson   int n = lua_gettop(L);  /* number of arguments */
177dfc11533SChris Williamson   int i;
178dfc11533SChris Williamson   luaL_Buffer b;
179dfc11533SChris Williamson   char *p = luaL_buffinitsize(L, &b, n);
180dfc11533SChris Williamson   for (i=1; i<=n; i++) {
181dfc11533SChris Williamson     int c = luaL_checkint(L, i);
182dfc11533SChris Williamson     luaL_argcheck(L, uchar(c) == c, i, "value out of range");
183dfc11533SChris Williamson     p[i - 1] = uchar(c);
184dfc11533SChris Williamson   }
185dfc11533SChris Williamson   luaL_pushresultsize(&b, n);
186dfc11533SChris Williamson   return 1;
187dfc11533SChris Williamson }
188dfc11533SChris Williamson 
189dfc11533SChris Williamson 
writer(lua_State * L,const void * b,size_t size,void * B)190dfc11533SChris Williamson static int writer (lua_State *L, const void* b, size_t size, void* B) {
191dfc11533SChris Williamson   (void)L;
192dfc11533SChris Williamson   luaL_addlstring((luaL_Buffer*) B, (const char *)b, size);
193dfc11533SChris Williamson   return 0;
194dfc11533SChris Williamson }
195dfc11533SChris Williamson 
196dfc11533SChris Williamson 
str_dump(lua_State * L)197dfc11533SChris Williamson static int str_dump (lua_State *L) {
198dfc11533SChris Williamson   luaL_Buffer b;
199dfc11533SChris Williamson   luaL_checktype(L, 1, LUA_TFUNCTION);
200dfc11533SChris Williamson   lua_settop(L, 1);
201dfc11533SChris Williamson   luaL_buffinit(L,&b);
202dfc11533SChris Williamson   if (lua_dump(L, writer, &b) != 0)
203dfc11533SChris Williamson     return luaL_error(L, "unable to dump given function");
204dfc11533SChris Williamson   luaL_pushresult(&b);
205dfc11533SChris Williamson   return 1;
206dfc11533SChris Williamson }
207dfc11533SChris Williamson 
208dfc11533SChris Williamson 
209dfc11533SChris Williamson 
210dfc11533SChris Williamson /*
211dfc11533SChris Williamson ** {======================================================
212dfc11533SChris Williamson ** PATTERN MATCHING
213dfc11533SChris Williamson ** =======================================================
214dfc11533SChris Williamson */
215dfc11533SChris Williamson 
216dfc11533SChris Williamson 
217dfc11533SChris Williamson #define CAP_UNFINISHED	(-1)
218dfc11533SChris Williamson #define CAP_POSITION	(-2)
219dfc11533SChris Williamson 
220dfc11533SChris Williamson 
221dfc11533SChris Williamson typedef struct MatchState {
222dfc11533SChris Williamson   int matchdepth;  /* control for recursive depth (to avoid C stack overflow) */
223dfc11533SChris Williamson   const char *src_init;  /* init of source string */
224dfc11533SChris Williamson   const char *src_end;  /* end ('\0') of source string */
225dfc11533SChris Williamson   const char *p_end;  /* end ('\0') of pattern */
226dfc11533SChris Williamson   lua_State *L;
227dfc11533SChris Williamson   int level;  /* total number of captures (finished or unfinished) */
228dfc11533SChris Williamson   struct {
229dfc11533SChris Williamson     const char *init;
230dfc11533SChris Williamson     ptrdiff_t len;
231dfc11533SChris Williamson   } capture[LUA_MAXCAPTURES];
232dfc11533SChris Williamson } MatchState;
233dfc11533SChris Williamson 
234dfc11533SChris Williamson 
235dfc11533SChris Williamson /* recursive function */
236dfc11533SChris Williamson static const char *match (MatchState *ms, const char *s, const char *p);
237dfc11533SChris Williamson 
238dfc11533SChris Williamson 
239dfc11533SChris Williamson /* maximum recursion depth for 'match' */
240dfc11533SChris Williamson #if !defined(MAXCCALLS)
241dfc11533SChris Williamson #define MAXCCALLS	200
242dfc11533SChris Williamson #endif
243dfc11533SChris Williamson 
244dfc11533SChris Williamson 
245dfc11533SChris Williamson #define L_ESC		'%'
246dfc11533SChris Williamson #define SPECIALS	"^$*+?.([%-"
247dfc11533SChris Williamson 
248dfc11533SChris Williamson 
check_capture(MatchState * ms,int l)249dfc11533SChris Williamson static int check_capture (MatchState *ms, int l) {
250dfc11533SChris Williamson   l -= '1';
251dfc11533SChris Williamson   if (l < 0 || l >= ms->level || ms->capture[l].len == CAP_UNFINISHED)
252dfc11533SChris Williamson     return luaL_error(ms->L, "invalid capture index %%%d", l + 1);
253dfc11533SChris Williamson   return l;
254dfc11533SChris Williamson }
255dfc11533SChris Williamson 
256dfc11533SChris Williamson 
capture_to_close(MatchState * ms)257dfc11533SChris Williamson static int capture_to_close (MatchState *ms) {
258dfc11533SChris Williamson   int level = ms->level;
259dfc11533SChris Williamson   for (level--; level>=0; level--)
260dfc11533SChris Williamson     if (ms->capture[level].len == CAP_UNFINISHED) return level;
261dfc11533SChris Williamson   return luaL_error(ms->L, "invalid pattern capture");
262dfc11533SChris Williamson }
263dfc11533SChris Williamson 
264dfc11533SChris Williamson 
classend(MatchState * ms,const char * p)265dfc11533SChris Williamson static const char *classend (MatchState *ms, const char *p) {
266dfc11533SChris Williamson   switch (*p++) {
267dfc11533SChris Williamson     case L_ESC: {
268dfc11533SChris Williamson       if (p == ms->p_end)
269dfc11533SChris Williamson         luaL_error(ms->L, "malformed pattern (ends with " LUA_QL("%%") ")");
270dfc11533SChris Williamson       return p+1;
271dfc11533SChris Williamson     }
272dfc11533SChris Williamson     case '[': {
273dfc11533SChris Williamson       if (*p == '^') p++;
274dfc11533SChris Williamson       do {  /* look for a `]' */
275dfc11533SChris Williamson         if (p == ms->p_end)
276dfc11533SChris Williamson           luaL_error(ms->L, "malformed pattern (missing " LUA_QL("]") ")");
277dfc11533SChris Williamson         if (*(p++) == L_ESC && p < ms->p_end)
278dfc11533SChris Williamson           p++;  /* skip escapes (e.g. `%]') */
279dfc11533SChris Williamson       } while (*p != ']');
280dfc11533SChris Williamson       return p+1;
281dfc11533SChris Williamson     }
282dfc11533SChris Williamson     default: {
283dfc11533SChris Williamson       return p;
284dfc11533SChris Williamson     }
285dfc11533SChris Williamson   }
286dfc11533SChris Williamson }
287dfc11533SChris Williamson 
288dfc11533SChris Williamson 
289*84f27369SIgor Kozhukhov static int
iscntrl(int c)290*84f27369SIgor Kozhukhov iscntrl(int c)
291*84f27369SIgor Kozhukhov {
292*84f27369SIgor Kozhukhov 	return ((c < 0x20) || (c == 0x7f));
293*84f27369SIgor Kozhukhov }
294*84f27369SIgor Kozhukhov 
295*84f27369SIgor Kozhukhov 
match_class(int c,int cl)296dfc11533SChris Williamson static int match_class (int c, int cl) {
297dfc11533SChris Williamson   int res;
298dfc11533SChris Williamson   switch (tolower(cl)) {
299dfc11533SChris Williamson     case 'a' : res = isalpha(c); break;
300dfc11533SChris Williamson     case 'c' : res = iscntrl(c); break;
301dfc11533SChris Williamson     case 'd' : res = isdigit(c); break;
302dfc11533SChris Williamson     case 'g' : res = isgraph(c); break;
303dfc11533SChris Williamson     case 'l' : res = islower(c); break;
304dfc11533SChris Williamson     case 'p' : res = ispunct(c); break;
305dfc11533SChris Williamson     case 's' : res = isspace(c); break;
306dfc11533SChris Williamson     case 'u' : res = isupper(c); break;
307dfc11533SChris Williamson     case 'w' : res = isalnum(c); break;
308dfc11533SChris Williamson     case 'x' : res = isxdigit(c); break;
309dfc11533SChris Williamson     case 'z' : res = (c == 0); break;  /* deprecated option */
310dfc11533SChris Williamson     default: return (cl == c);
311dfc11533SChris Williamson   }
312dfc11533SChris Williamson   return (islower(cl) ? res : !res);
313dfc11533SChris Williamson }
314dfc11533SChris Williamson 
315dfc11533SChris Williamson 
matchbracketclass(int c,const char * p,const char * ec)316dfc11533SChris Williamson static int matchbracketclass (int c, const char *p, const char *ec) {
317dfc11533SChris Williamson   int sig = 1;
318dfc11533SChris Williamson   if (*(p+1) == '^') {
319dfc11533SChris Williamson     sig = 0;
320dfc11533SChris Williamson     p++;  /* skip the `^' */
321dfc11533SChris Williamson   }
322dfc11533SChris Williamson   while (++p < ec) {
323dfc11533SChris Williamson     if (*p == L_ESC) {
324dfc11533SChris Williamson       p++;
325dfc11533SChris Williamson       if (match_class(c, uchar(*p)))
326dfc11533SChris Williamson         return sig;
327dfc11533SChris Williamson     }
328dfc11533SChris Williamson     else if ((*(p+1) == '-') && (p+2 < ec)) {
329dfc11533SChris Williamson       p+=2;
330dfc11533SChris Williamson       if (uchar(*(p-2)) <= c && c <= uchar(*p))
331dfc11533SChris Williamson         return sig;
332dfc11533SChris Williamson     }
333dfc11533SChris Williamson     else if (uchar(*p) == c) return sig;
334dfc11533SChris Williamson   }
335dfc11533SChris Williamson   return !sig;
336dfc11533SChris Williamson }
337dfc11533SChris Williamson 
338dfc11533SChris Williamson 
singlematch(MatchState * ms,const char * s,const char * p,const char * ep)339dfc11533SChris Williamson static int singlematch (MatchState *ms, const char *s, const char *p,
340dfc11533SChris Williamson                         const char *ep) {
341dfc11533SChris Williamson   if (s >= ms->src_end)
342dfc11533SChris Williamson     return 0;
343dfc11533SChris Williamson   else {
344dfc11533SChris Williamson     int c = uchar(*s);
345dfc11533SChris Williamson     switch (*p) {
346dfc11533SChris Williamson       case '.': return 1;  /* matches any char */
347dfc11533SChris Williamson       case L_ESC: return match_class(c, uchar(*(p+1)));
348dfc11533SChris Williamson       case '[': return matchbracketclass(c, p, ep-1);
349dfc11533SChris Williamson       default:  return (uchar(*p) == c);
350dfc11533SChris Williamson     }
351dfc11533SChris Williamson   }
352dfc11533SChris Williamson }
353dfc11533SChris Williamson 
354dfc11533SChris Williamson 
matchbalance(MatchState * ms,const char * s,const char * p)355dfc11533SChris Williamson static const char *matchbalance (MatchState *ms, const char *s,
356dfc11533SChris Williamson                                    const char *p) {
357dfc11533SChris Williamson   if (p >= ms->p_end - 1)
358dfc11533SChris Williamson     luaL_error(ms->L, "malformed pattern "
359dfc11533SChris Williamson                       "(missing arguments to " LUA_QL("%%b") ")");
360dfc11533SChris Williamson   if (*s != *p) return NULL;
361dfc11533SChris Williamson   else {
362dfc11533SChris Williamson     int b = *p;
363dfc11533SChris Williamson     int e = *(p+1);
364dfc11533SChris Williamson     int cont = 1;
365dfc11533SChris Williamson     while (++s < ms->src_end) {
366dfc11533SChris Williamson       if (*s == e) {
367dfc11533SChris Williamson         if (--cont == 0) return s+1;
368dfc11533SChris Williamson       }
369dfc11533SChris Williamson       else if (*s == b) cont++;
370dfc11533SChris Williamson     }
371dfc11533SChris Williamson   }
372dfc11533SChris Williamson   return NULL;  /* string ends out of balance */
373dfc11533SChris Williamson }
374dfc11533SChris Williamson 
375dfc11533SChris Williamson 
max_expand(MatchState * ms,const char * s,const char * p,const char * ep)376dfc11533SChris Williamson static const char *max_expand (MatchState *ms, const char *s,
377dfc11533SChris Williamson                                  const char *p, const char *ep) {
378dfc11533SChris Williamson   ptrdiff_t i = 0;  /* counts maximum expand for item */
379dfc11533SChris Williamson   while (singlematch(ms, s + i, p, ep))
380dfc11533SChris Williamson     i++;
381dfc11533SChris Williamson   /* keeps trying to match with the maximum repetitions */
382dfc11533SChris Williamson   while (i>=0) {
383dfc11533SChris Williamson     const char *res = match(ms, (s+i), ep+1);
384dfc11533SChris Williamson     if (res) return res;
385dfc11533SChris Williamson     i--;  /* else didn't match; reduce 1 repetition to try again */
386dfc11533SChris Williamson   }
387dfc11533SChris Williamson   return NULL;
388dfc11533SChris Williamson }
389dfc11533SChris Williamson 
390dfc11533SChris Williamson 
min_expand(MatchState * ms,const char * s,const char * p,const char * ep)391dfc11533SChris Williamson static const char *min_expand (MatchState *ms, const char *s,
392dfc11533SChris Williamson                                  const char *p, const char *ep) {
393dfc11533SChris Williamson   for (;;) {
394dfc11533SChris Williamson     const char *res = match(ms, s, ep+1);
395dfc11533SChris Williamson     if (res != NULL)
396dfc11533SChris Williamson       return res;
397dfc11533SChris Williamson     else if (singlematch(ms, s, p, ep))
398dfc11533SChris Williamson       s++;  /* try with one more repetition */
399dfc11533SChris Williamson     else return NULL;
400dfc11533SChris Williamson   }
401dfc11533SChris Williamson }
402dfc11533SChris Williamson 
403dfc11533SChris Williamson 
start_capture(MatchState * ms,const char * s,const char * p,int what)404dfc11533SChris Williamson static const char *start_capture (MatchState *ms, const char *s,
405dfc11533SChris Williamson                                     const char *p, int what) {
406dfc11533SChris Williamson   const char *res;
407dfc11533SChris Williamson   int level = ms->level;
408dfc11533SChris Williamson   if (level >= LUA_MAXCAPTURES) luaL_error(ms->L, "too many captures");
409dfc11533SChris Williamson   ms->capture[level].init = s;
410dfc11533SChris Williamson   ms->capture[level].len = what;
411dfc11533SChris Williamson   ms->level = level+1;
412dfc11533SChris Williamson   if ((res=match(ms, s, p)) == NULL)  /* match failed? */
413dfc11533SChris Williamson     ms->level--;  /* undo capture */
414dfc11533SChris Williamson   return res;
415dfc11533SChris Williamson }
416dfc11533SChris Williamson 
417dfc11533SChris Williamson 
end_capture(MatchState * ms,const char * s,const char * p)418dfc11533SChris Williamson static const char *end_capture (MatchState *ms, const char *s,
419dfc11533SChris Williamson                                   const char *p) {
420dfc11533SChris Williamson   int l = capture_to_close(ms);
421dfc11533SChris Williamson   const char *res;
422dfc11533SChris Williamson   ms->capture[l].len = s - ms->capture[l].init;  /* close capture */
423dfc11533SChris Williamson   if ((res = match(ms, s, p)) == NULL)  /* match failed? */
424dfc11533SChris Williamson     ms->capture[l].len = CAP_UNFINISHED;  /* undo capture */
425dfc11533SChris Williamson   return res;
426dfc11533SChris Williamson }
427dfc11533SChris Williamson 
428dfc11533SChris Williamson 
match_capture(MatchState * ms,const char * s,int l)429dfc11533SChris Williamson static const char *match_capture (MatchState *ms, const char *s, int l) {
430dfc11533SChris Williamson   size_t len;
431dfc11533SChris Williamson   l = check_capture(ms, l);
432dfc11533SChris Williamson   len = ms->capture[l].len;
433dfc11533SChris Williamson   if ((size_t)(ms->src_end-s) >= len &&
434dfc11533SChris Williamson       memcmp(ms->capture[l].init, s, len) == 0)
435dfc11533SChris Williamson     return s+len;
436dfc11533SChris Williamson   else return NULL;
437dfc11533SChris Williamson }
438dfc11533SChris Williamson 
439dfc11533SChris Williamson 
match(MatchState * ms,const char * s,const char * p)440dfc11533SChris Williamson static const char *match (MatchState *ms, const char *s, const char *p) {
441dfc11533SChris Williamson   if (ms->matchdepth-- == 0)
442dfc11533SChris Williamson     luaL_error(ms->L, "pattern too complex");
443dfc11533SChris Williamson   init: /* using goto's to optimize tail recursion */
444dfc11533SChris Williamson   if (p != ms->p_end) {  /* end of pattern? */
445dfc11533SChris Williamson     switch (*p) {
446dfc11533SChris Williamson       case '(': {  /* start capture */
447dfc11533SChris Williamson         if (*(p + 1) == ')')  /* position capture? */
448dfc11533SChris Williamson           s = start_capture(ms, s, p + 2, CAP_POSITION);
449dfc11533SChris Williamson         else
450dfc11533SChris Williamson           s = start_capture(ms, s, p + 1, CAP_UNFINISHED);
451dfc11533SChris Williamson         break;
452dfc11533SChris Williamson       }
453dfc11533SChris Williamson       case ')': {  /* end capture */
454dfc11533SChris Williamson         s = end_capture(ms, s, p + 1);
455dfc11533SChris Williamson         break;
456dfc11533SChris Williamson       }
457dfc11533SChris Williamson       case '$': {
458dfc11533SChris Williamson         if ((p + 1) != ms->p_end)  /* is the `$' the last char in pattern? */
459dfc11533SChris Williamson           goto dflt;  /* no; go to default */
460dfc11533SChris Williamson         s = (s == ms->src_end) ? s : NULL;  /* check end of string */
461dfc11533SChris Williamson         break;
462dfc11533SChris Williamson       }
463dfc11533SChris Williamson       case L_ESC: {  /* escaped sequences not in the format class[*+?-]? */
464dfc11533SChris Williamson         switch (*(p + 1)) {
465dfc11533SChris Williamson           case 'b': {  /* balanced string? */
466dfc11533SChris Williamson             s = matchbalance(ms, s, p + 2);
467dfc11533SChris Williamson             if (s != NULL) {
468dfc11533SChris Williamson               p += 4; goto init;  /* return match(ms, s, p + 4); */
469dfc11533SChris Williamson             }  /* else fail (s == NULL) */
470dfc11533SChris Williamson             break;
471dfc11533SChris Williamson           }
472dfc11533SChris Williamson           case 'f': {  /* frontier? */
473dfc11533SChris Williamson             const char *ep; char previous;
474dfc11533SChris Williamson             p += 2;
475dfc11533SChris Williamson             if (*p != '[')
476dfc11533SChris Williamson               luaL_error(ms->L, "missing " LUA_QL("[") " after "
477dfc11533SChris Williamson                                  LUA_QL("%%f") " in pattern");
478dfc11533SChris Williamson             ep = classend(ms, p);  /* points to what is next */
479dfc11533SChris Williamson             previous = (s == ms->src_init) ? '\0' : *(s - 1);
480dfc11533SChris Williamson             if (!matchbracketclass(uchar(previous), p, ep - 1) &&
481dfc11533SChris Williamson                matchbracketclass(uchar(*s), p, ep - 1)) {
482dfc11533SChris Williamson               p = ep; goto init;  /* return match(ms, s, ep); */
483dfc11533SChris Williamson             }
484dfc11533SChris Williamson             s = NULL;  /* match failed */
485dfc11533SChris Williamson             break;
486dfc11533SChris Williamson           }
487dfc11533SChris Williamson           case '0': case '1': case '2': case '3':
488dfc11533SChris Williamson           case '4': case '5': case '6': case '7':
489dfc11533SChris Williamson           case '8': case '9': {  /* capture results (%0-%9)? */
490dfc11533SChris Williamson             s = match_capture(ms, s, uchar(*(p + 1)));
491dfc11533SChris Williamson             if (s != NULL) {
492dfc11533SChris Williamson               p += 2; goto init;  /* return match(ms, s, p + 2) */
493dfc11533SChris Williamson             }
494dfc11533SChris Williamson             break;
495dfc11533SChris Williamson           }
496dfc11533SChris Williamson           default: goto dflt;
497dfc11533SChris Williamson         }
498dfc11533SChris Williamson         break;
499dfc11533SChris Williamson       }
500dfc11533SChris Williamson       default: dflt: {  /* pattern class plus optional suffix */
501dfc11533SChris Williamson         const char *ep = classend(ms, p);  /* points to optional suffix */
502dfc11533SChris Williamson         /* does not match at least once? */
503dfc11533SChris Williamson         if (!singlematch(ms, s, p, ep)) {
504dfc11533SChris Williamson           if (*ep == '*' || *ep == '?' || *ep == '-') {  /* accept empty? */
505dfc11533SChris Williamson             p = ep + 1; goto init;  /* return match(ms, s, ep + 1); */
506dfc11533SChris Williamson           }
507dfc11533SChris Williamson           else  /* '+' or no suffix */
508dfc11533SChris Williamson             s = NULL;  /* fail */
509dfc11533SChris Williamson         }
510dfc11533SChris Williamson         else {  /* matched once */
511dfc11533SChris Williamson           switch (*ep) {  /* handle optional suffix */
512dfc11533SChris Williamson             case '?': {  /* optional */
513dfc11533SChris Williamson               const char *res;
514dfc11533SChris Williamson               if ((res = match(ms, s + 1, ep + 1)) != NULL)
515dfc11533SChris Williamson                 s = res;
516dfc11533SChris Williamson               else {
517dfc11533SChris Williamson                 p = ep + 1; goto init;  /* else return match(ms, s, ep + 1); */
518dfc11533SChris Williamson               }
519dfc11533SChris Williamson               break;
520dfc11533SChris Williamson             }
521dfc11533SChris Williamson             case '+':  /* 1 or more repetitions */
522dfc11533SChris Williamson               s++;  /* 1 match already done */
52346ac8fdfSToomas Soome               /* FALLTHROUGH */
524dfc11533SChris Williamson             case '*':  /* 0 or more repetitions */
525dfc11533SChris Williamson               s = max_expand(ms, s, p, ep);
526dfc11533SChris Williamson               break;
527dfc11533SChris Williamson             case '-':  /* 0 or more repetitions (minimum) */
528dfc11533SChris Williamson               s = min_expand(ms, s, p, ep);
529dfc11533SChris Williamson               break;
530dfc11533SChris Williamson             default:  /* no suffix */
531dfc11533SChris Williamson               s++; p = ep; goto init;  /* return match(ms, s + 1, ep); */
532dfc11533SChris Williamson           }
533dfc11533SChris Williamson         }
534dfc11533SChris Williamson         break;
535dfc11533SChris Williamson       }
536dfc11533SChris Williamson     }
537dfc11533SChris Williamson   }
538dfc11533SChris Williamson   ms->matchdepth++;
539dfc11533SChris Williamson   return s;
540dfc11533SChris Williamson }
541dfc11533SChris Williamson 
542dfc11533SChris Williamson 
543dfc11533SChris Williamson 
lmemfind(const char * s1,size_t l1,const char * s2,size_t l2)544dfc11533SChris Williamson static const char *lmemfind (const char *s1, size_t l1,
545dfc11533SChris Williamson                                const char *s2, size_t l2) {
546dfc11533SChris Williamson   if (l2 == 0) return s1;  /* empty strings are everywhere */
547dfc11533SChris Williamson   else if (l2 > l1) return NULL;  /* avoids a negative `l1' */
548dfc11533SChris Williamson   else {
549dfc11533SChris Williamson     const char *init;  /* to search for a `*s2' inside `s1' */
550dfc11533SChris Williamson     l2--;  /* 1st char will be checked by `memchr' */
551dfc11533SChris Williamson     l1 = l1-l2;  /* `s2' cannot be found after that */
552dfc11533SChris Williamson     while (l1 > 0 && (init = (const char *)memchr(s1, *s2, l1)) != NULL) {
553dfc11533SChris Williamson       init++;   /* 1st char is already checked */
554dfc11533SChris Williamson       if (memcmp(init, s2+1, l2) == 0)
555dfc11533SChris Williamson         return init-1;
556dfc11533SChris Williamson       else {  /* correct `l1' and `s1' to try again */
557dfc11533SChris Williamson         l1 -= init-s1;
558dfc11533SChris Williamson         s1 = init;
559dfc11533SChris Williamson       }
560dfc11533SChris Williamson     }
561dfc11533SChris Williamson     return NULL;  /* not found */
562dfc11533SChris Williamson   }
563dfc11533SChris Williamson }
564dfc11533SChris Williamson 
565dfc11533SChris Williamson 
push_onecapture(MatchState * ms,int i,const char * s,const char * e)566dfc11533SChris Williamson static void push_onecapture (MatchState *ms, int i, const char *s,
567dfc11533SChris Williamson                                                     const char *e) {
568dfc11533SChris Williamson   if (i >= ms->level) {
569dfc11533SChris Williamson     if (i == 0)  /* ms->level == 0, too */
570dfc11533SChris Williamson       lua_pushlstring(ms->L, s, e - s);  /* add whole match */
571dfc11533SChris Williamson     else
572dfc11533SChris Williamson       luaL_error(ms->L, "invalid capture index");
573dfc11533SChris Williamson   }
574dfc11533SChris Williamson   else {
575dfc11533SChris Williamson     ptrdiff_t l = ms->capture[i].len;
576dfc11533SChris Williamson     if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture");
577dfc11533SChris Williamson     if (l == CAP_POSITION)
578dfc11533SChris Williamson       lua_pushinteger(ms->L, ms->capture[i].init - ms->src_init + 1);
579dfc11533SChris Williamson     else
580dfc11533SChris Williamson       lua_pushlstring(ms->L, ms->capture[i].init, l);
581dfc11533SChris Williamson   }
582dfc11533SChris Williamson }
583dfc11533SChris Williamson 
584dfc11533SChris Williamson 
push_captures(MatchState * ms,const char * s,const char * e)585dfc11533SChris Williamson static int push_captures (MatchState *ms, const char *s, const char *e) {
586dfc11533SChris Williamson   int i;
587dfc11533SChris Williamson   int nlevels = (ms->level == 0 && s) ? 1 : ms->level;
588dfc11533SChris Williamson   luaL_checkstack(ms->L, nlevels, "too many captures");
589dfc11533SChris Williamson   for (i = 0; i < nlevels; i++)
590dfc11533SChris Williamson     push_onecapture(ms, i, s, e);
591dfc11533SChris Williamson   return nlevels;  /* number of strings pushed */
592dfc11533SChris Williamson }
593dfc11533SChris Williamson 
594dfc11533SChris Williamson 
595dfc11533SChris Williamson /* check whether pattern has no special characters */
nospecials(const char * p,size_t l)596dfc11533SChris Williamson static int nospecials (const char *p, size_t l) {
597dfc11533SChris Williamson   size_t upto = 0;
598dfc11533SChris Williamson   do {
599dfc11533SChris Williamson     if (strpbrk(p + upto, SPECIALS))
600dfc11533SChris Williamson       return 0;  /* pattern has a special character */
601dfc11533SChris Williamson     upto += strlen(p + upto) + 1;  /* may have more after \0 */
602dfc11533SChris Williamson   } while (upto <= l);
603dfc11533SChris Williamson   return 1;  /* no special chars found */
604dfc11533SChris Williamson }
605dfc11533SChris Williamson 
606dfc11533SChris Williamson 
str_find_aux(lua_State * L,int find)607dfc11533SChris Williamson static int str_find_aux (lua_State *L, int find) {
608dfc11533SChris Williamson   size_t ls, lp;
609dfc11533SChris Williamson   const char *s = luaL_checklstring(L, 1, &ls);
610dfc11533SChris Williamson   const char *p = luaL_checklstring(L, 2, &lp);
611dfc11533SChris Williamson   size_t init = posrelat(luaL_optinteger(L, 3, 1), ls);
612dfc11533SChris Williamson   if (init < 1) init = 1;
613dfc11533SChris Williamson   else if (init > ls + 1) {  /* start after string's end? */
614dfc11533SChris Williamson     lua_pushnil(L);  /* cannot find anything */
615dfc11533SChris Williamson     return 1;
616dfc11533SChris Williamson   }
617dfc11533SChris Williamson   /* explicit request or no special characters? */
618dfc11533SChris Williamson   if (find && (lua_toboolean(L, 4) || nospecials(p, lp))) {
619dfc11533SChris Williamson     /* do a plain search */
620dfc11533SChris Williamson     const char *s2 = lmemfind(s + init - 1, ls - init + 1, p, lp);
621dfc11533SChris Williamson     if (s2) {
622dfc11533SChris Williamson       lua_pushinteger(L, s2 - s + 1);
623dfc11533SChris Williamson       lua_pushinteger(L, s2 - s + lp);
624dfc11533SChris Williamson       return 2;
625dfc11533SChris Williamson     }
626dfc11533SChris Williamson   }
627dfc11533SChris Williamson   else {
628dfc11533SChris Williamson     MatchState ms;
629dfc11533SChris Williamson     const char *s1 = s + init - 1;
630dfc11533SChris Williamson     int anchor = (*p == '^');
631dfc11533SChris Williamson     if (anchor) {
632dfc11533SChris Williamson       p++; lp--;  /* skip anchor character */
633dfc11533SChris Williamson     }
634dfc11533SChris Williamson     ms.L = L;
635dfc11533SChris Williamson     ms.matchdepth = MAXCCALLS;
636dfc11533SChris Williamson     ms.src_init = s;
637dfc11533SChris Williamson     ms.src_end = s + ls;
638dfc11533SChris Williamson     ms.p_end = p + lp;
639dfc11533SChris Williamson     do {
640dfc11533SChris Williamson       const char *res;
641dfc11533SChris Williamson       ms.level = 0;
642dfc11533SChris Williamson       lua_assert(ms.matchdepth == MAXCCALLS);
643dfc11533SChris Williamson       if ((res=match(&ms, s1, p)) != NULL) {
644dfc11533SChris Williamson         if (find) {
645dfc11533SChris Williamson           lua_pushinteger(L, s1 - s + 1);  /* start */
646dfc11533SChris Williamson           lua_pushinteger(L, res - s);   /* end */
647dfc11533SChris Williamson           return push_captures(&ms, NULL, 0) + 2;
648dfc11533SChris Williamson         }
649dfc11533SChris Williamson         else
650dfc11533SChris Williamson           return push_captures(&ms, s1, res);
651dfc11533SChris Williamson       }
652dfc11533SChris Williamson     } while (s1++ < ms.src_end && !anchor);
653dfc11533SChris Williamson   }
654dfc11533SChris Williamson   lua_pushnil(L);  /* not found */
655dfc11533SChris Williamson   return 1;
656dfc11533SChris Williamson }
657dfc11533SChris Williamson 
658dfc11533SChris Williamson 
str_find(lua_State * L)659dfc11533SChris Williamson static int str_find (lua_State *L) {
660dfc11533SChris Williamson   return str_find_aux(L, 1);
661dfc11533SChris Williamson }
662dfc11533SChris Williamson 
663dfc11533SChris Williamson 
str_match(lua_State * L)664dfc11533SChris Williamson static int str_match (lua_State *L) {
665dfc11533SChris Williamson   return str_find_aux(