[src/trunk]: src/bin/ksh Use backtracking for regular patterns, but not ksh-s...

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/7b7940dd5a81
branches:  trunk
changeset: 353347:7b7940dd5a81
user:      christos <christos%NetBSD.org@localhost>
date:      Sun Apr 30 17:34:29 2017 +0000

description:
Use backtracking for regular patterns, but not ksh-specific ones [*?!+@](...)
which still use recursion.

diffstat:

 bin/ksh/misc.c |  90 ++++++++++++++++++++++++++++++++-------------------------
 1 files changed, 51 insertions(+), 39 deletions(-)

diffs (182 lines):

diff -r 506c7b0d2489 -r 7b7940dd5a81 bin/ksh/misc.c
--- a/bin/ksh/misc.c    Sun Apr 30 16:56:30 2017 +0000
+++ b/bin/ksh/misc.c    Sun Apr 30 17:34:29 2017 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: misc.c,v 1.15 2011/10/16 17:12:11 joerg Exp $  */
+/*     $NetBSD: misc.c,v 1.16 2017/04/30 17:34:29 christos Exp $       */
 
 /*
  * Miscellaneous functions
@@ -6,7 +6,7 @@
 #include <sys/cdefs.h>
 
 #ifndef lint
-__RCSID("$NetBSD: misc.c,v 1.15 2011/10/16 17:12:11 joerg Exp $");
+__RCSID("$NetBSD: misc.c,v 1.16 2017/04/30 17:34:29 christos Exp $");
 #endif
 
 
@@ -631,46 +631,50 @@
        const unsigned char *se, *pe;
        int isfile;
 {
-       register int sc, pc;
+       int sc, pc;
        const unsigned char *prest, *psub, *pnext;
        const unsigned char *srest;
+       const unsigned char *sNext, *pNext, *sStart;
 
        if (s == NULL || p == NULL)
                return 0;
-       while (p < pe) {
-               pc = *p++;
+       sNext = sStart = s;
+       pNext = p;
+       while (p < pe || s < se) {
+               pc = *p;
                sc = s < se ? *s : '\0';
-               s++;
                if (isfile) {
                        sc = FILECHCONV((unsigned char)sc);
                        pc = FILECHCONV((unsigned char)pc);
                }
                if (!ISMAGIC(pc)) {
                        if (sc != pc)
-                               return 0;
+                               goto backtrack;
+                       p++;
+                       s++;
                        continue;
-               }
-               switch (*p++) {
+               } else
+                       pc = *++p;
+               switch (pc) {
                  case '[':
+                       p++;
+                       s++;
                        if (sc == 0 || (p = cclass(p, sc)) == NULL)
-                               return 0;
-                       break;
+                               break;
+                       continue;
 
                  case '?':
                        if (sc == 0)
-                               return 0;
-                       break;
+                               break;
+                       p++;
+                       s++;
+                       continue;
 
                  case '*':
-                       if (p == pe)
-                               return 1;
-                       s--;
-                       do {
-                               if (do_gmatch(s, se, p, pe, isfile))
-                                       return 1;
-                       } while (s++ < se);
-                       return 0;
-
+                       pNext = p - 1;
+                       sNext = s + 1;
+                       p++;
+                       continue;
                  /*
                   * [*+?@!](pattern|pattern|..)
                   *
@@ -678,13 +682,13 @@
                   */
                  case 0x80|'+': /* matches one or more times */
                  case 0x80|'*': /* matches zero or more times */
-                       if (!(prest = pat_scan(p, pe, 0)))
-                               return 0;
+                       if (!(prest = pat_scan(++p, pe, 0)))
+                               break;
                        s--;
                        /* take care of zero matches */
                        if (p[-1] == (0x80 | '*')
                            && do_gmatch(s, se, prest, pe, isfile))
-                               return 1;
+                               continue;
                        for (psub = p; ; psub = pnext) {
                                pnext = pat_scan(psub, pe, 1);
                                for (srest = s; srest <= se; srest++) {
@@ -700,18 +704,18 @@
                                if (pnext == prest)
                                        break;
                        }
-                       return 0;
+                       break;
 
                  case 0x80|'?': /* matches zero or once */
                  case 0x80|'@': /* matches one of the patterns */
                  case 0x80|' ': /* simile for @ */
-                       if (!(prest = pat_scan(p, pe, 0)))
-                               return 0;
+                       if (!(prest = pat_scan(++p, pe, 0)))
+                               break;
                        s--;
                        /* Take care of zero matches */
                        if (p[-1] == (0x80 | '?')
                            && do_gmatch(s, se, prest, pe, isfile))
-                               return 1;
+                               continue;
                        for (psub = p; ; psub = pnext) {
                                pnext = pat_scan(psub, pe, 1);
                                srest = prest == pe ? se : s;
@@ -720,16 +724,16 @@
                                                      psub, pnext - 2, isfile)
                                            && do_gmatch(srest, se,
                                                         prest, pe, isfile))
-                                               return 1;
+                                               continue;
                                }
                                if (pnext == prest)
                                        break;
                        }
-                       return 0;
+                       break;
 
                  case 0x80|'!': /* matches none of the patterns */
-                       if (!(prest = pat_scan(p, pe, 0)))
-                               return 0;
+                       if (!(prest = pat_scan(++p, pe, 0)))
+                               break;
                        s--;
                        for (srest = s; srest <= se; srest++) {
                                int matched = 0;
@@ -747,17 +751,25 @@
                                }
                                if (!matched && do_gmatch(srest, se,
                                                          prest, pe, isfile))
-                                       return 1;
+                                       continue;
                        }
-                       return 0;
+                       break;
 
                  default:
-                       if (sc != p[-1])
-                               return 0;
-                       break;
+                       if (sc != pc)
+                               break;
+                       p++;
+                       s++;
+                       continue;
                }
+backtrack:     if (sNext != sStart && sNext <= se) {
+                       p = pNext;
+                       s = sNext;
+                       continue;
+               }
+               return 0;
        }
-       return s == se;
+       return 1;
 }
 
 static const unsigned char *