xref: /illumos-gate/usr/src/uts/common/fs/zfs/lua/lstrlib.c (revision 84f2736904a911587ccd1cf1e4543493fcab31f4)
1 /*
2 ** $Id: lstrlib.c,v 1.178.1.1 2013/04/12 18:48:47 roberto Exp $
3 ** Standard library for string operations and pattern-matching
4 ** See Copyright Notice in lua.h
5 */
6 
7 
8 #include <sys/ctype.h>
9 #include <sys/zfs_context.h>
10 
11 #define lstrlib_c
12 #define LUA_LIB
13 
14 #include "lua.h"
15 
16 #include "lauxlib.h"
17 #include "lualib.h"
18 
19 
20 /*
21 ** maximum number of captures that a pattern can do during
22 ** pattern-matching. This limit is arbitrary.
23 */
24 #if !defined(LUA_MAXCAPTURES)
25 #define LUA_MAXCAPTURES		32
26 #endif
27 
28 
29 /* macro to `unsign' a character */
30 #define uchar(c)	((unsigned char)(c))
31 
32 /*
33  * PATCHED: add missing character macros.
34  */
35 #define tolower(C)	(((C) >= 'A' && (C) <= 'Z') ? (C) - 'A' + 'a' : (C))
36 #define toupper(C)      (((C) >= 'a' && (C) <= 'z') ? (C) - 'a' + 'A': (C))
37 #define isgraph(C)	((C) >= 0x21 && (C) <= 0x7E)
38 #define ispunct(C)	(((C) >= 0x21 && (C) <= 0x2F) || \
39     ((C) >= 0x3A && (C) <= 0x40) || \
40     ((C) >= 0x5B && (C) <= 0x60) || \
41     ((C) >= 0x7B && (C) <= 0x7E))
42 
43 /*
44  * The provided version of sprintf returns a char *, but str_format expects
45  * it to return the number of characters printed. This version has the expected
46  * behavior.
47  */
str_sprintf(char * buf,const char * fmt,...)48 static size_t str_sprintf(char *buf, const char *fmt, ...) {
49   va_list args;
50   size_t len;
51 
52   va_start(args, fmt);
53   len = vsnprintf(buf, INT_MAX, fmt, args);
54   va_end(args);
55 
56   return len;
57 }
58 
59 
str_len(lua_State * L)60 static int str_len (lua_State *L) {
61   size_t l;
62   luaL_checklstring(L, 1, &l);
63   lua_pushinteger(L, (lua_Integer)l);
64   return 1;
65 }
66 
67 
68 /* translate a relative string position: negative means back from end */
posrelat(ptrdiff_t pos,size_t len)69 static size_t posrelat (ptrdiff_t pos, size_t len) {
70   if (pos >= 0) return (size_t)pos;
71   else if (0u - (size_t)pos > len) return 0;
72   else return len - ((size_t)-pos) + 1;
73 }
74 
75 
str_sub(lua_State * L)76 static int str_sub (lua_State *L) {
77   size_t l;
78   const char *s = luaL_checklstring(L, 1, &l);
79   size_t start = posrelat(luaL_checkinteger(L, 2), l);
80   size_t end = posrelat(luaL_optinteger(L, 3, -1), l);
81   if (start < 1) start = 1;
82   if (end > l) end = l;
83   if (start <= end)
84     lua_pushlstring(L, s + start - 1, end - start + 1);
85   else lua_pushliteral(L, "");
86   return 1;
87 }
88 
89 
str_reverse(lua_State * L)90 static int str_reverse (lua_State *L) {
91   size_t l, i;
92   luaL_Buffer b;
93   const char *s = luaL_checklstring(L, 1, &l);
94   char *p = luaL_buffinitsize(L, &b, l);
95   for (i = 0; i < l; i++)
96     p[i] = s[l - i - 1];
97   luaL_pushresultsize(&b, l);
98   return 1;
99 }
100 
101 
str_lower(lua_State * L)102 static int str_lower (lua_State *L) {
103   size_t l;
104   size_t i;
105   luaL_Buffer b;
106   const char *s = luaL_checklstring(L, 1, &l);
107   char *p = luaL_buffinitsize(L, &b, l);
108   for (i=0; i<l; i++)
109     p[i] = tolower(uchar(s[i]));
110   luaL_pushresultsize(&b, l);
111   return 1;
112 }
113 
114 
str_upper(lua_State * L)115 static int str_upper (lua_State *L) {
116   size_t l;
117   size_t i;
118   luaL_Buffer b;
119   const char *s = luaL_checklstring(L, 1, &l);
120   char *p = luaL_buffinitsize(L, &b, l);
121   for (i=0; i<l; i++)
122     p[i] = toupper(uchar(s[i]));
123   luaL_pushresultsize(&b, l);
124   return 1;
125 }
126 
127 
128 /* reasonable limit to avoid arithmetic overflow */
129 #define MAXSIZE		((~(size_t)0) >> 1)
130 
str_rep(lua_State * L)131 static int str_rep (lua_State *L) {
132   size_t l, lsep;
133   const char *s = luaL_checklstring(L, 1, &l);
134   int n = luaL_checkint(L, 2);
135   const char *sep = luaL_optlstring(L, 3, "", &lsep);
136   if (n <= 0) lua_pushliteral(L, "");
137   else if (l + lsep < l || l + lsep >= MAXSIZE / n)  /* may overflow? */
138     return luaL_error(L, "resulting string too large");
139   else {
140     size_t totallen = n * l + (n - 1) * lsep;
141     luaL_Buffer b;
142     char *p = luaL_buffinitsize(L, &b, totallen);
143     while (n-- > 1) {  /* first n-1 copies (followed by separator) */
144       memcpy(p, s, l * sizeof(char)); p += l;
145       if (lsep > 0) {  /* avoid empty 'memcpy' (may be expensive) */
146         memcpy(p, sep, lsep * sizeof(char)); p += lsep;
147       }
148     }
149     memcpy(p, s, l * sizeof(char));  /* last copy (not followed by separator) */
150     luaL_pushresultsize(&b, totallen);
151   }
152   return 1;
153 }
154 
155 
str_byte(lua_State * L)156 static int str_byte (lua_State *L) {
157   size_t l;
158   const char *s = luaL_checklstring(L, 1, &l);
159   size_t posi = posrelat(luaL_optinteger(L, 2, 1), l);
160   size_t pose = posrelat(luaL_optinteger(L, 3, posi), l);
161   int n, i;
162   if (posi < 1) posi = 1;
163   if (pose > l) pose = l;
164   if (posi > pose) return 0;  /* empty interval; return no values */
165   n = (int)(pose -  posi + 1);
166   if (posi + n <= pose)  /* (size_t -> int) overflow? */
167     return luaL_error(L, "string slice too long");
168   luaL_checkstack(L, n, "string slice too long");
169   for (i=0; i<n; i++)
170     lua_pushinteger(L, uchar(s[posi+i-1]));
171   return n;
172 }
173 
174 
str_char(lua_State * L)175 static int str_char (lua_State *L) {
176   int n = lua_gettop(L);  /* number of arguments */
177   int i;
178   luaL_Buffer b;
179   char *p = luaL_buffinitsize(L, &b, n);
180   for (i=1; i<=n; i++) {
181     int c = luaL_checkint(L, i);
182     luaL_argcheck(L, uchar(c) == c, i, "value out of range");
183     p[i - 1] = uchar(c);
184   }
185   luaL_pushresultsize(&b, n);
186   return 1;
187 }
188 
189 
writer(lua_State * L,const void * b,size_t size,void * B)190 static int writer (lua_State *L, const void* b, size_t size, void* B) {
191   (void)L;
192   luaL_addlstring((luaL_Buffer*) B, (const char *)b, size);
193   return 0;
194 }
195 
196 
str_dump(lua_State * L)197 static int str_dump (lua_State *L) {
198   luaL_Buffer b;
199   luaL_checktype(L, 1, LUA_TFUNCTION);
200   lua_settop(L, 1);
201   luaL_buffinit(L,&b);
202   if (lua_dump(L, writer, &b) != 0)
203     return luaL_error(L, "unable to dump given function");
204   luaL_pushresult(&b);
205   return 1;
206 }
207 
208 
209 
210 /*
211 ** {======================================================
212 ** PATTERN MATCHING
213 ** =======================================================
214 */
215 
216 
217 #define CAP_UNFINISHED	(-1)
218 #define CAP_POSITION	(-2)
219 
220 
221 typedef struct MatchState {
222   int matchdepth;  /* control for recursive depth (to avoid C stack overflow) */
223   const char *src_init;  /* init of source string */
224   const char *src_end;  /* end ('\0') of source string */
225   const char *p_end;  /* end ('\0') of pattern */
226   lua_State *L;
227   int level;  /* total number of captures (finished or unfinished) */
228   struct {
229     const char *init;
230     ptrdiff_t len;
231   } capture[LUA_MAXCAPTURES];
232 } MatchState;
233 
234 
235 /* recursive function */
236 static const char *match (MatchState *ms, const char *s, const char *p);
237 
238 
239 /* maximum recursion depth for 'match' */
240 #if !defined(MAXCCALLS)
241 #define MAXCCALLS	200
242 #endif
243 
244 
245 #define L_ESC		'%'
246 #define SPECIALS	"^$*+?.([%-"
247 
248 
check_capture(MatchState * ms,int l)249 static int check_capture (MatchState *ms, int l) {
250   l -= '1';
251   if (l < 0 || l >= ms->level || ms->capture[l].len == CAP_UNFINISHED)
252     return luaL_error(ms->L, "invalid capture index %%%d", l + 1);
253   return l;
254 }
255 
256 
capture_to_close(MatchState * ms)257 static int capture_to_close (MatchState *ms) {
258   int level = ms->level;
259   for (level--; level>=0; level--)
260     if (ms->capture[level].len == CAP_UNFINISHED) return level;
261   return luaL_error(ms->L, "invalid pattern capture");
262 }
263 
264 
classend(MatchState * ms,const char * p)265 static const char *classend (MatchState *ms, const char *p) {
266   switch (*p++) {
267     case L_ESC: {
268       if (p == ms->p_end)
269         luaL_error(ms->L, "malformed pattern (ends with " LUA_QL("%%") ")");
270       return p+1;
271     }
272     case '[': {
273       if (*p == '^') p++;
274       do {  /* look for a `]' */
275         if (p == ms->p_end)
276           luaL_error(ms->L, "malformed pattern (missing " LUA_QL("]") ")");
277         if (*(p++) == L_ESC && p < ms->p_end)
278           p++;  /* skip escapes (e.g. `%]') */
279       } while (*p != ']');
280       return p+1;
281     }
282     default: {
283       return p;
284     }
285   }
286 }
287 
288 
289 static int
iscntrl(int c)290 iscntrl(int c)
291 {
292 	return ((c < 0x20) || (c == 0x7f));
293 }
294 
295 
match_class(int c,int cl)296 static int match_class (int c, int cl) {
297   int res;
298   switch (tolower(cl)) {
299     case 'a' : res = isalpha(c); break;
300     case 'c' : res = iscntrl(c); break;
301     case 'd' : res = isdigit(c); break;
302     case 'g' : res = isgraph(c); break;
303     case 'l' : res = islower(c); break;
304     case 'p' : res = ispunct(c); break;
305     case 's' : res = isspace(c); break;
306     case 'u' : res = isupper(c); break;
307     case 'w' : res = isalnum(c); break;
308     case 'x' : res = isxdigit(c); break;
309     case 'z' : res = (c == 0); break;  /* deprecated option */
310     default: return (cl == c);
311   }
312   return (islower(cl) ? res : !res);
313 }
314 
315 
matchbracketclass(int c,const char * p,const char * ec)316 static int matchbracketclass (int c, const char *p, const char *ec) {
317   int sig = 1;
318   if (*(p+1) == '^') {
319     sig = 0;
320     p++;  /* skip the `^' */
321   }
322   while (++p < ec) {
323     if (*p == L_ESC) {
324       p++;
325       if (match_class(c, uchar(*p)))
326         return sig;
327     }
328     else if ((*(p+1) == '-') && (p+2 < ec)) {
329       p+=2;
330       if (uchar(*(p-2)) <= c && c <= uchar(*p))
331         return sig;
332     }
333     else if (uchar(*p) == c) return sig;
334   }
335   return !sig;
336 }
337 
338 
singlematch(MatchState * ms,const char * s,const char * p,const char * ep)339 static int singlematch (MatchState *ms, const char *s, const char *p,
340                         const char *ep) {
341   if (s >= ms->src_end)
342     return 0;
343   else {
344     int c = uchar(*s);
345     switch (*p) {
346       case '.': return 1;  /* matches any char */
347       case L_ESC: return match_class(c, uchar(*(p+1)));
348       case '[': return matchbracketclass(c, p, ep-1);
349       default:  return (uchar(*p) == c);
350     }
351   }
352 }
353 
354 
matchbalance(MatchState * ms,const char * s,const char * p)355 static const char *matchbalance (MatchState *ms, const char *s,
356                                    const char *p) {
357   if (p >= ms->p_end - 1)
358     luaL_error(ms->L, "malformed pattern "
359                       "(missing arguments to " LUA_QL("%%b") ")");
360   if (*s != *p) return NULL;
361   else {
362     int b = *p;
363     int e = *(p+1);
364     int cont = 1;
365     while (++s < ms->src_end) {
366       if (*s == e) {
367         if (--cont == 0) return s+1;
368       }
369       else if (*s == b) cont++;
370     }
371   }
372   return NULL;  /* string ends out of balance */
373 }
374 
375 
max_expand(MatchState * ms,const char * s,const char * p,const char * ep)376 static const char *max_expand (MatchState *ms, const char *s,
377                                  const char *p, const char *ep) {
378   ptrdiff_t i = 0;  /* counts maximum expand for item */
379   while (singlematch(ms, s + i, p, ep))
380     i++;
381   /* keeps trying to match with the maximum repetitions */
382   while (i>=0) {
383     const char *res = match(ms, (s+i), ep+1);
384     if (res) return res;
385     i--;  /* else didn't match; reduce 1 repetition to try again */
386   }
387   return NULL;
388 }
389 
390 
min_expand(MatchState * ms,const char * s,const char * p,const char * ep)391 static const char *min_expand (MatchState *ms, const char *s,
392                                  const char *p, const char *ep) {
393   for (;;) {
394     const char *res = match(ms, s, ep+1);
395     if (res != NULL)
396       return res;
397     else if (singlematch(ms, s, p, ep))
398       s++;  /* try with one more repetition */
399     else return NULL;
400   }
401 }
402 
403 
start_capture(MatchState * ms,const char * s,const char * p,int what)404 static const char *start_capture (MatchState *ms, const char *s,
405                                     const char *p, int what) {
406   const char *res;
407   int level = ms->level;
408   if (level >= LUA_MAXCAPTURES) luaL_error(ms->L, "too many captures");
409   ms->capture[level].init = s;
410   ms->capture[level].len = what;
411   ms->level = level+1;
412   if ((res=match(ms, s, p)) == NULL)  /* match failed? */
413     ms->level--;  /* undo capture */
414   return res;
415 }
416 
417 
end_capture(MatchState * ms,const char * s,const char * p)418 static const char *end_capture (MatchState *ms, const char *s,
419                                   const char *p) {
420   int l = capture_to_close(ms);
421   const char *res;
422   ms->capture[l].len = s - ms->capture[l].init;  /* close capture */
423   if ((res = match(ms, s, p)) == NULL)  /* match failed? */
424     ms->capture[l].len = CAP_UNFINISHED;  /* undo capture */
425   return res;
426 }
427 
428 
match_capture(MatchState * ms,const char * s,int l)429 static const char *match_capture (MatchState *ms, const char *s, int l) {
430   size_t len;
431   l = check_capture(ms, l);
432   len = ms->capture[l].len;
433   if ((size_t)(ms->src_end-s) >= len &&
434       memcmp(ms->capture[l].init, s, len) == 0)
435     return s+len;
436   else return NULL;
437 }
438 
439 
match(MatchState * ms,const char * s,const char * p)440 static const char *match (MatchState *ms, const char *s, const char *p) {
441   if (ms->matchdepth-- == 0)
442     luaL_error(ms->L, "pattern too complex");
443   init: /* using goto's to optimize tail recursion */
444   if (p != ms->p_end) {  /* end of pattern? */
445     switch (*p) {
446       case '(': {  /* start capture */
447         if (*(p + 1) == ')')  /* position capture? */
448           s = start_capture(ms, s, p + 2, CAP_POSITION);
449         else
450           s = start_capture(ms, s, p + 1, CAP_UNFINISHED);
451         break;
452       }
453       case ')': {  /* end capture */
454         s = end_capture(ms, s, p + 1);
455         break;
456       }
457       case '$': {
458         if ((p + 1) != ms->p_end)  /* is the `$' the last char in pattern? */
459           goto dflt;  /* no; go to default */
460         s = (s == ms->src_end) ? s : NULL;  /* check end of string */
461         break;
462       }
463       case L_ESC: {  /* escaped sequences not in the format class[*+?-]? */
464         switch (*(p + 1)) {
465           case 'b': {  /* balanced string? */
466             s = matchbalance(ms, s, p + 2);
467             if (s != NULL) {
468               p += 4; goto init;  /* return match(ms, s, p + 4); */
469             }  /* else fail (s == NULL) */
470             break;
471           }
472           case 'f': {  /* frontier? */
473             const char *ep; char previous;
474             p += 2;
475             if (*p != '[')
476               luaL_error(ms->L, "missing " LUA_QL("[") " after "
477                                  LUA_QL("%%f") " in pattern");
478             ep = classend(ms, p);  /* points to what is next */
479             previous = (s == ms->src_init) ? '\0' : *(s - 1);
480             if (!matchbracketclass(uchar(previous), p, ep - 1) &&
481                matchbracketclass(uchar(*s), p, ep - 1)) {
482               p = ep; goto init;  /* return match(ms, s, ep); */
483             }
484             s = NULL;  /* match failed */
485             break;
486           }
487           case '0': case '1': case '2': case '3':
488           case '4': case '5': case '6': case '7':
489           case '8': case '9': {  /* capture results (%0-%9)? */
490             s = match_capture(ms, s, uchar(*(p + 1)));
491             if (s != NULL) {
492               p += 2; goto init;  /* return match(ms, s, p + 2) */
493             }
494             break;
495           }
496           default: goto dflt;
497         }
498         break;
499       }
500       default: dflt: {  /* pattern class plus optional suffix */
501         const char *ep = classend(ms, p);  /* points to optional suffix */
502         /* does not match at least once? */
503         if (!singlematch(ms, s, p, ep)) {
504           if (*ep == '*' || *ep == '?' || *ep == '-') {  /* accept empty? */
505             p = ep + 1; goto init;  /* return match(ms, s, ep + 1); */
506           }
507           else  /* '+' or no suffix */
508             s = NULL;  /* fail */
509         }
510         else {  /* matched once */
511           switch (*ep) {  /* handle optional suffix */
512             case '?': {  /* optional */
513               const char *res;
514               if ((res = match(ms, s + 1, ep + 1)) != NULL)
515                 s = res;
516               else {
517                 p = ep + 1; goto init;  /* else return match(ms, s, ep + 1); */
518               }
519               break;
520             }
521             case '+':  /* 1 or more repetitions */
522               s++;  /* 1 match already done */
523               /* FALLTHROUGH */
524             case '*':  /* 0 or more repetitions */
525               s = max_expand(ms, s, p, ep);
526               break;
527             case '-':  /* 0 or more repetitions (minimum) */
528               s = min_expand(ms, s, p, ep);
529               break;
530             default:  /* no suffix */
531               s++; p = ep; goto init;  /* return match(ms, s + 1, ep); */
532           }
533         }
534         break;
535       }
536     }
537   }
538   ms->matchdepth++;
539   return s;
540 }
541 
542 
543 
lmemfind(const char * s1,size_t l1,const char * s2,size_t l2)544 static const char *lmemfind (const char *s1, size_t l1,
545                                const char *s2, size_t l2) {
546   if (l2 == 0) return s1;  /* empty strings are everywhere */
547   else if (l2 > l1) return NULL;  /* avoids a negative `l1' */
548   else {
549     const char *init;  /* to search for a `*s2' inside `s1' */
550     l2--;  /* 1st char will be checked by `memchr' */
551     l1 = l1-l2;  /* `s2' cannot be found after that */
552     while (l1 > 0 && (init = (const char *)memchr(s1, *s2, l1)) != NULL) {
553       init++;   /* 1st char is already checked */
554       if (memcmp(init, s2+1, l2) == 0)
555         return init-1;
556       else {  /* correct `l1' and `s1' to try again */
557         l1 -= init-s1;
558         s1 = init;
559       }
560     }
561     return NULL;  /* not found */
562   }
563 }
564 
565 
push_onecapture(MatchState * ms,int i,const char * s,const char * e)566 static void push_onecapture (MatchState *ms, int i, const char *s,
567                                                     const char *e) {
568   if (i >= ms->level) {
569     if (i == 0)  /* ms->level == 0, too */
570       lua_pushlstring(ms->L, s, e - s);  /* add whole match */
571     else
572       luaL_error(ms->L, "invalid capture index");
573   }
574   else {
575     ptrdiff_t l = ms->capture[i].len;
576     if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture");
577     if (l == CAP_POSITION)
578       lua_pushinteger(ms->L, ms->capture[i].init - ms->src_init + 1);
579     else
580       lua_pushlstring(ms->L, ms->capture[i].init, l);
581   }
582 }
583 
584 
push_captures(MatchState * ms,const char * s,const char * e)585 static int push_captures (MatchState *ms, const char *s, const char *e) {
586   int i;
587   int nlevels = (ms->level == 0 && s) ? 1 : ms->level;
588   luaL_checkstack(ms->L, nlevels, "too many captures");
589   for (i = 0; i < nlevels; i++)
590     push_onecapture(ms, i, s, e);
591   return nlevels;  /* number of strings pushed */
592 }
593 
594 
595 /* check whether pattern has no special characters */
nospecials(const char * p,size_t l)596 static int nospecials (const char *p, size_t l) {
597   size_t upto = 0;
598   do {
599     if (strpbrk(p + upto, SPECIALS))
600       return 0;  /* pattern has a special character */
601     upto += strlen(p + upto) + 1;  /* may have more after \0 */
602   } while (upto <= l);
603   return 1;  /* no special chars found */
604 }
605 
606 
str_find_aux(lua_State * L,int find)607 static int str_find_aux (lua_State *L, int find) {
608   size_t ls, lp;
609   const char *s = luaL_checklstring(L, 1, &ls);
610   const char *p = luaL_checklstring(L, 2, &lp);
611   size_t init = posrelat(luaL_optinteger(L, 3, 1), ls);
612   if (init < 1) init = 1;
613   else if (init > ls + 1) {  /* start after string's end? */
614     lua_pushnil(L);  /* cannot find anything */
615     return 1;
616   }
617   /* explicit request or no special characters? */
618   if (find && (lua_toboolean(L, 4) || nospecials(p, lp))) {
619     /* do a plain search */
620     const char *s2 = lmemfind(s + init - 1, ls - init + 1, p, lp);
621     if (s2) {
622       lua_pushinteger(L, s2 - s + 1);
623       lua_pushinteger(L, s2 - s + lp);
624       return 2;
625     }
626   }
627   else {
628     MatchState ms;
629     const char *s1 = s + init - 1;
630     int anchor = (*p == '^');
631     if (anchor) {
632       p++; lp--;  /* skip anchor character */
633     }
634     ms.L = L;
635     ms.matchdepth = MAXCCALLS;
636     ms.src_init = s;
637     ms.src_end = s + ls;
638     ms.p_end = p + lp;
639     do {
640       const char *res;
641       ms.level = 0;
642       lua_assert(ms.matchdepth == MAXCCALLS);
643       if ((res=match(&ms, s1, p)) != NULL) {
644         if (find) {
645           lua_pushinteger(L, s1 - s + 1);  /* start */
646           lua_pushinteger(L, res - s);   /* end */
647           return push_captures(&ms, NULL, 0) + 2;
648         }
649         else
650           return push_captures(&ms, s1, res);
651       }
652     } while (s1++ < ms.src_end && !anchor);
653   }
654   lua_pushnil(L);  /* not found */
655   return 1;
656 }
657 
658 
str_find(lua_State * L)659 static int str_find (lua_State *L) {
660   return str_find_aux(L, 1);
661 }
662 
663 
str_match(lua_State * L)664 static int str_match (lua_State *L) {
665   return str_find_aux(L, 0);
666 }
667 
668 
gmatch_aux(lua_State * L)669 static int gmatch_aux (lua_State *L) {
670   MatchState ms;
671   size_t ls, lp;
672   const char *s = lua_tolstring(L, lua_upvalueindex(1), &ls);
673   const char *p = lua_tolstring(L, lua_upvalueindex(2), &lp);
674   const char *src;
675   ms.L = L;
676   ms.matchdepth = MAXCCALLS;
677   ms.src_init = s;
678   ms.src_end = s+ls;
679   ms.p_end = p + lp;
680   for (src = s + (size_t)lua_tointeger(L, lua_upvalueindex(3));
681        src <= ms.src_end;
682        src++) {
683     const char *e;
684     ms.level = 0;
685     lua_assert(ms.matchdepth == MAXCCALLS);
686     if ((e = match(&ms, src, p)) != NULL) {
687       lua_Integer newstart = e-s;
688       if (e == src) newstart++;  /* empty match? go at least one position */
689       lua_pushinteger(L, newstart);
690       lua_replace(L, lua_upvalueindex(3));
691       return push_captures(&ms, src, e);
692     }
693   }
694   return 0;  /* not found */
695 }
696 
697 
str_gmatch(lua_State * L)698 static int str_gmatch (lua_State *L) {
699   luaL_checkstring(L, 1);
700   luaL_checkstring(L, 2);
701   lua_settop(L, 2);
702   lua_pushinteger(L, 0);
703   lua_pushcclosure(L, gmatch_aux, 3);
704   return 1;
705 }
706 
707 
add_s(MatchState * ms,luaL_Buffer * b,const char * s,const char * e)708 static void add_s (MatchState *ms, luaL_Buffer *b, const char *s,
709                                                    const char *e) {
710   size_t l, i;
711   const char *news = lua_tolstring(ms->L, 3, &l);
712   for (i = 0; i < l; i++) {
713     if (news[i] != L_ESC)
714       luaL_addchar(b, news[i]);
715     else {
716       i++;  /* skip ESC */
717       if (!isdigit(uchar(news[i]))) {
718         if (news[i] != L_ESC)
719           luaL_error(ms->L, "invalid use of " LUA_QL("%c")
720                            " in replacement string", L_ESC);
721         luaL_addchar(b, news[i]);
722       }
723       else if (news[i] == '0')
724           luaL_addlstring(b, s, e - s);
725       else {
726         push_onecapture(ms, news[i] - '1', s, e);
727         luaL_addvalue(b);  /* add capture to accumulated result */
728       }
729     }
730   }
731 }
732 
733 
add_value(MatchState * ms,luaL_Buffer * b,const char * s,const char * e,int tr)734 static void add_value (MatchState *ms, luaL_Buffer *b, const char *s,
735                                        const char *e, int tr) {
736   lua_State *L = ms->L;
737   switch (tr) {
738     case LUA_TFUNCTION: {
739       int n;
740       lua_pushvalue(L, 3);
741       n = push_captures(ms, s, e);
742       lua_call(L, n, 1);
743       break;
744     }
745     case LUA_TTABLE: {
746       push_onecapture(ms, 0, s, e);
747       lua_gettable(L, 3);
748       break;
749     }
750     default: {  /* LUA_TNUMBER or LUA_TSTRING */
751       add_s(ms, b, s, e);
752       return;
753     }
754   }
755   if (!lua_toboolean(L, -1)) {  /* nil or false? */
756     lua_pop(L, 1);
757     lua_pushlstring(L, s, e - s);  /* keep original text */
758   }
759   else if (!lua_isstring(L, -1))
760     luaL_error(L, "invalid replacement value (a %s)", luaL_typename(L, -1));
761   luaL_addvalue(b);  /* add result to accumulator */
762 }
763 
764 
str_gsub(lua_State * L)765 static int str_gsub (lua_State *L) {
766   size_t srcl, lp;
767   const char *src = luaL_checklstring(L, 1, &srcl);
768   const char *p = luaL_checklstring(L, 2, &lp);
769   int tr = lua_type(L, 3);
770   size_t max_s = luaL_optinteger(L, 4, srcl+1);
771   int anchor = (*p == '^');
772   size_t n = 0;
773   MatchState ms;
774   luaL_Buffer b;
775   luaL_argcheck(L, tr == LUA_TNUMBER || tr == LUA_TSTRING ||
776                    tr == LUA_TFUNCTION || tr == LUA_TTABLE, 3,
777                       "string/function/table expected");
778   luaL_buffinit(L, &b);
779   if (anchor) {
780     p++; lp--;  /* skip anchor character */
781   }
782   ms.L = L;
783   ms.matchdepth = MAXCCALLS;
784   ms.src_init = src;
785   ms.src_end = src+srcl;
786   ms.p_end = p + lp;
787   while (n < max_s) {
788     const char *e;
789     ms.level = 0;
790     lua_assert(ms.matchdepth == MAXCCALLS);
791     e = match(&ms, src, p);
792     if (e) {
793       n++;
794       add_value(&ms, &b, src, e, tr);
795     }
796     if (e && e>src) /* non empty match? */
797       src = e;  /* skip it */
798     else if (src < ms.src_end)
799       luaL_addchar(&b, *src++);
800     else break;
801     if (anchor) break;
802   }
803   luaL_addlstring(&b, src, ms.src_end-src);
804   luaL_pushresult(&b);
805   lua_pushinteger(L, n);  /* number of substitutions */
806   return 2;
807 }
808 
809 /* }====================================================== */
810 
811 
812 
813 /*
814 ** {======================================================
815 ** STRING FORMAT
816 ** =======================================================
817 */
818 
819 /*
820 ** LUA_INTFRMLEN is the length modifier for integer conversions in
821 ** 'string.format'; LUA_INTFRM_T is the integer type corresponding to
822 ** the previous length
823 */
824 #if !defined(LUA_INTFRMLEN)	/* { */
825 #if defined(LUA_USE_LONGLONG)
826 
827 #define LUA_INTFRMLEN		"ll"
828 #define LUA_INTFRM_T		long long
829 
830 #else
831 
832 #define LUA_INTFRMLEN		"l"
833 #define LUA_INTFRM_T		long
834 
835 #endif
836 #endif				/* } */
837 
838 
839 /*
840 ** LUA_FLTFRMLEN is the length modifier for float conversions in
841 ** 'string.format'; LUA_FLTFRM_T is the float type corresponding to
842 ** the previous length
843 */
844 #if !defined(LUA_FLTFRMLEN)
845 
846 #define LUA_FLTFRMLEN		""
847 #define LUA_FLTFRM_T		double
848 
849 #endif
850 
851 
852 /* maximum size of each formatted item (> len(format('%99.99f', -1e308))) */
853 #define MAX_ITEM	512
854 /* valid flags in a format specification */
855 #define FLAGS	"-+ #0"
856 /*
857 ** maximum size of each format specification (such as '%-099.99d')
858 ** (+10 accounts for %99.99x plus margin of error)
859 */
860 #define MAX_FORMAT	(sizeof(FLAGS) + sizeof(LUA_INTFRMLEN) + 10)
861 
862 
addquoted(lua_State * L,luaL_Buffer * b,int arg)863 static void addquoted (lua_State *L, luaL_Buffer *b, int arg) {
864   size_t l;
865   const char *s = luaL_checklstring(L, arg, &l);
866   luaL_addchar(b, '"');
867   while (l--) {
868     if (*s == '"' || *s == '\\' || *s == '\n') {
869       luaL_addchar(b, '\\');
870       luaL_addchar(b, *s);
871     }
872     else if (*s == '\0' || iscntrl(uchar(*s))) {
873       char buff[10];
874       if (!isdigit(uchar(*(s+1))))
875         sprintf(buff, "\\%d", (int)uchar(*s));
876       else
877         sprintf(buff, "\\%03d", (int)uchar(*s));
878       luaL_addstring(b, buff);
879     }
880     else
881       luaL_addchar(b, *s);
882     s++;
883   }
884   luaL_addchar(b, '"');
885 }
886 
scanformat(lua_State * L,const char * strfrmt,char * form)887 static const char *scanformat (lua_State *L, const char *strfrmt, char *form) {
888   const char *p = strfrmt;
889   while (*p != '\0' && strchr(FLAGS, *p) != NULL) p++;  /* skip flags */
890   if ((size_t)(p - strfrmt) >= sizeof(FLAGS)/sizeof(char))
891     luaL_error(L, "invalid format (repeated flags)");
892   if (isdigit(uchar(*p))) p++;  /* skip width */
893   if (isdigit(uchar(*p))) p++;  /* (2 digits at most) */
894   if (*p == '.') {
895     p++;
896     if (isdigit(uchar(*p))) p++;  /* skip precision */
897     if (isdigit(uchar(*p))) p++;  /* (2 digits at most) */
898   }
899   if (isdigit(uchar(*p)))
900     luaL_error(L, "invalid format (width or precision too long)");
901   *(form++) = '%';
902   memcpy(form, strfrmt, (p - strfrmt + 1) * sizeof(char));
903   form += p - strfrmt + 1;
904   *form = '\0';
905   return p;
906 }
907 
908 
909 /*
910 ** add length modifier into formats
911 */
addlenmod(char * form,const char * lenmod)912 static void addlenmod (char *form, const char *lenmod) {
913   size_t l = strlen(form);
914   size_t lm = strlen(lenmod);
915   char spec = form[l - 1];
916   strcpy(form + l - 1, lenmod);
917   form[l + lm - 1] = spec;
918   form[l + lm] = '\0';
919 }
920 
921 
str_format(lua_State * L)922 static int str_format (lua_State *L) {
923   int top = lua_gettop(L);
924   int arg = 1;
925   size_t sfl;
926   const char *strfrmt = luaL_checklstring(L, arg, &sfl);
927   const char *strfrmt_end = strfrmt+sfl;
928   luaL_Buffer b;
929   luaL_buffinit(L, &b);
930   while (strfrmt < strfrmt_end) {
931     if (*strfrmt != L_ESC)
932       luaL_addchar(&b, *strfrmt++);
933     else if (*++strfrmt == L_ESC)
934       luaL_addchar(&b, *strfrmt++);  /* %% */
935     else { /* format item */
936       char form[MAX_FORMAT];  /* to store the format (`%...') */
937       char *buff = luaL_prepbuffsize(&b, MAX_ITEM);  /* to put formatted item */
938       int nb = 0;  /* number of bytes in added item */
939       if (++arg > top)
940         luaL_argerror(L, arg, "no value");
941       strfrmt = scanformat(L, strfrmt, form);
942       switch (*strfrmt++) {
943         case 'c': {
944           nb = str_sprintf(buff, form, luaL_checkint(L, arg));
945           break;
946         }
947         case 'd': case 'i': {
948           lua_Number n = luaL_checknumber(L, arg);
949           LUA_INTFRM_T ni = (LUA_INTFRM_T)n;
950           lua_Number diff = n - (lua_Number)ni;
951           luaL_argcheck(L, -1 < diff && diff < 1, arg,
952                         "not a number in proper range");
953           addlenmod(form, LUA_INTFRMLEN);
954           nb = str_sprintf(buff, form, ni);
955           break;
956         }
957         case 'o': case 'u': case 'x': case 'X': {
958           lua_Number n = luaL_checknumber(L, arg);
959           unsigned LUA_INTFRM_T ni = (unsigned LUA_INTFRM_T)n;
960           lua_Number diff = n - (lua_Number)ni;
961           luaL_argcheck(L, -1 < diff && diff < 1, arg,
962                         "not a non-negative number in proper range");
963           addlenmod(form, LUA_INTFRMLEN);
964           nb = str_sprintf(buff, form, ni);
965           break;
966         }
967 #if defined(LUA_USE_FLOAT_FORMATS)
968         case 'e': case 'E': case 'f':
969 #if defined(LUA_USE_AFORMAT)
970         case 'a': case 'A':
971 #endif
972         case 'g': case 'G': {
973           addlenmod(form, LUA_FLTFRMLEN);
974           nb = str_sprintf(buff, form, (LUA_FLTFRM_T)luaL_checknumber(L, arg));
975           break;
976         }
977 #endif
978         case 'q': {
979           addquoted(L, &b, arg);
980           break;
981         }
982         case 's': {
983           size_t l;
984           const char *s = luaL_tolstring(L, arg, &l);
985           if (!strchr(form, '.') && l >= 100) {
986             /* no precision and string is too long to be formatted;
987                keep original string */
988             luaL_addvalue(&b);
989             break;
990           }
991           else {
992             nb = str_sprintf(buff, form, s);
993             lua_pop(L, 1);  /* remove result from 'luaL_tolstring' */
994             break;
995           }
996         }
997         default: {  /* also treat cases `pnLlh' */
998           return luaL_error(L, "invalid option " LUA_QL("%%%c") " to "
999                                LUA_QL("format"), *(strfrmt - 1));
1000         }
1001       }
1002       luaL_addsize(&b, nb);
1003     }
1004   }
1005   luaL_pushresult(&b);
1006   return 1;
1007 }
1008 
1009 /* }====================================================== */
1010 
1011 
1012 static const luaL_Reg strlib[] = {
1013   {"byte", str_byte},
1014   {"char", str_char},
1015   {"dump", str_dump},
1016   {"find", str_find},
1017   {"format", str_format},
1018   {"gmatch", str_gmatch},
1019   {"gsub", str_gsub},
1020   {"len", str_len},
1021   {"lower", str_lower},
1022   {"match", str_match},
1023   {"rep", str_rep},
1024   {"reverse", str_reverse},
1025   {"sub", str_sub},
1026   {"upper", str_upper},
1027   {NULL, NULL}
1028 };
1029 
1030 
createmetatable(lua_State * L)1031 static void createmetatable (lua_State *L) {
1032   lua_createtable(L, 0, 1);  /* table to be metatable for strings */
1033   lua_pushliteral(L, "");  /* dummy string */
1034   lua_pushvalue(L, -2);  /* copy table */
1035   lua_setmetatable(L, -2);  /* set table as metatable for strings */
1036   lua_pop(L, 1);  /* pop dummy string */
1037   lua_pushvalue(L, -2);  /* get string library */
1038   lua_setfield(L, -2, "__index");  /* metatable.__index = string */
1039   lua_pop(L, 1);  /* pop metatable */
1040 }
1041 
1042 
1043 /*
1044 ** Open string library
1045 */
luaopen_string(lua_State * L)1046 LUAMOD_API int luaopen_string (lua_State *L) {
1047   luaL_newlib(L, strlib);
1048   createmetatable(L);
1049   return 1;
1050 }
1051 
1052