cde/programs/dtksh/ksh93/src/lib/libast/re/reexec.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: reexec.c /main/3 1995/11/01 18:22:33 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 #if !defined(__PROTO__)
  50 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  51 #if defined(__cplusplus)
  52 #define __MANGLE__      "C"
  53 #else
  54 #define __MANGLE__
  55 #endif
  56 #define __STDARG__
  57 #define __PROTO__(x)    x
  58 #define __OTORP__(x)
  59 #define __PARAM__(n,o)  n
  60 #if !defined(__STDC__) && !defined(__cplusplus)
  61 #if !defined(c_plusplus)
  62 #define const
  63 #endif
  64 #define signed
  65 #define void            int
  66 #define volatile
  67 #define __V_            char
  68 #else
  69 #define __V_            void
  70 #endif
  71 #else
  72 #define __PROTO__(x)    ()
  73 #define __OTORP__(x)    x
  74 #define __PARAM__(n,o)  o
  75 #define __MANGLE__
  76 #define __V_            char
  77 #define const
  78 #define signed
  79 #define void            int
  80 #define volatile
  81 #endif
  82 #if defined(__cplusplus) || defined(c_plusplus)
  83 #define __VARARG__      ...
  84 #else
  85 #define __VARARG__
  86 #endif
  87 #if defined(__STDARG__)
  88 #define __VA_START__(p,a)       va_start(p,a)
  89 #else
  90 #define __VA_START__(p,a)       va_start(p)
  91 #endif
  92 #endif
  93 #include "relib.h"
  94
  95 #include <ctype.h>
  96
  97 #define LISTINCREMENT   8
  98
  99 typedef struct
 100 {
 101         Inst_t*         inst;   /* instruction of the thread            */
 102         Subexp_t        se;     /* matched sub-expressions this thread  */
 103 } List_t;
 104
 105 /*
 106  * note optimization in addinst:
 107  *      *p must be pending when addinst called; if *l has been looked
 108  *      at already, the optimization is a bug.
 109  */
 110
 111 static List_t*
 112 newthread __PARAM__((register List_t* p, register Inst_t* ip, register Subexp_t* sep), (p, ip, sep)) __OTORP__(register List_t* p; register Inst_t* ip; register Subexp_t* sep;){
 113         for (; p->inst; p++)
 114                 if (p->inst == ip)
 115                 {
 116                         if (sep->m[0].sp < p->se.m[0].sp) p->se = *sep;
 117                         return(0);
 118                 }
 119         p->inst = ip;
 120         p->se = *sep;
 121         (++p)->inst = 0;
 122         return(p);
 123 }
 124
 125 static void
 126 newmatch __PARAM__((register Subexp_t* mp, register Subexp_t* np), (mp, np)) __OTORP__(register Subexp_t* mp; register Subexp_t* np;){
 127         if (!mp->m[0].sp || np->m[0].sp < mp->m[0].sp || np->m[0].sp == mp->m[0].sp && np->m[0].ep > mp->m[0].ep)
 128                 *mp = *np;
 129 }
 130
 131 int
 132 reexec __PARAM__((Re_program_t* aprogp, const char* starts), (aprogp, starts)) __OTORP__(Re_program_t* aprogp; const char* starts;){
 133         Re_program_t*           progp = (Re_program_t*)aprogp;
 134         register int            flag = 0;
 135         register Inst_t*        inst;
 136         register List_t*        tlp;
 137         register const char*    s;
 138         Subexp_t*               mp;
 139         int                     checkstart;
 140         int                     startchar;
 141
 142         List_t*         tl;     /* this list, next list                 */
 143         List_t*         nl;     /* this list, next list                 */
 144         List_t*         tle;    /* ends of this and next list           */
 145         List_t*         nle;    /* ends of this and next list           */
 146         List_t*         list[2];
 147         List_t*         liste[2];
 148         int             match = 0;
 149
 150         static int      listsize = LISTINCREMENT;
 151         static Subexp_t sempty; /* empty set of matches                 */
 152
 153
 154         startchar = progp->startinst->type < TOKEN ? progp->startinst->type : 0;
 155         mp = (progp->flags & RE_MATCH) ? &progp->subexp : 0;
 156         list[0] = 0;
 157  Restart:
 158         match = 0;
 159         checkstart = startchar;
 160         sempty.m[0].sp = 0;
 161         if (mp) mp->m[0].sp = mp->m[0].ep = 0;
 162         if (!list[0])
 163         {
 164                 if (!(list[0] = newof(0, List_t, 2 * listsize, 0)))
 165                         reerror("list overflow");
 166                 list[1] = list[0] + listsize;
 167                 liste[0] = list[0] + listsize - 1;
 168                 liste[1] = list[1] + listsize - 1;
 169         }
 170         list[0][0].inst = list[1][0].inst = 0;
 171
 172         /*
 173          * execute machine once for each character, including terminal '\0'
 174          */
 175
 176         s = starts;
 177         do
 178         {
 179                 /*
 180                  * fast check for first char
 181                  */
 182
 183                 if (checkstart && *s != startchar) continue;
 184                 tl = list[flag];
 185                 tle = liste[flag];
 186                 nl = list[flag ^= 1];
 187                 nle = liste[flag];
 188                 nl->inst = 0;
 189
 190                 /*
 191                  * add first instruction to this list
 192                  */
 193
 194                 sempty.m[0].sp = (char*)s;
 195                 newthread(tl, progp->startinst, &sempty);
 196
 197                 /*
 198                  * execute machine until this list is empty
 199                  */
 200
 201                 for (tlp = tl; inst = tlp->inst; tlp++)
 202                 {
 203                         /*
 204                          * assignment =
 205                          */
 206  Switchstmt:
 207                         switch (inst->type)
 208                         {
 209                         case LBRA:
 210                                 tlp->se.m[inst->subid].sp = (char*)s;
 211                                 inst = inst->next;
 212                                 goto Switchstmt;
 213                         case RBRA:
 214                                 tlp->se.m[inst->subid].ep = (char*)s;
 215                                 inst = inst->next;
 216                                 goto Switchstmt;
 217                         case ANY:
 218                                 goto Addinst;
 219                         case BOL:
 220                                 if (s == starts)
 221                                 {
 222                                         inst = inst->next;
 223                                         goto Switchstmt;
 224                                 }
 225                                 break;
 226                         case EOL:
 227                                 if (!*s)
 228                                 {
 229                                         inst = inst->next;
 230                                         goto Switchstmt;
 231                                 }
 232                                 break;
 233                         case BID:
 234                                 if (s == starts || !isalnum(*(s - 1)) && *(s - 1) != '_')
 235                                 {
 236                                         inst = inst->next;
 237                                         goto Switchstmt;
 238                                 }
 239                                 break;
 240                         case EID:
 241                                 if (!*s || !isalnum(*s) && *s != '_')
 242                                 {
 243                                         inst = inst->next;
 244                                         goto Switchstmt;
 245                                 }
 246                                 break;
 247                         case CCLASS:
 248                                 if (tstbit(inst->cclass, *s)) goto Addinst;
 249                                 break;
 250                         case OR:
 251                                 /*
 252                                  * evaluate right choice later
 253                                  */
 254
 255                                 if (newthread(tlp, inst->right, &tlp->se) == tle)
 256                                         goto Realloc;
 257
 258                                 /*
 259                                  * efficiency: advance and re-evaluate
 260                                  */
 261
 262                                 inst = inst->left;
 263                                 goto Switchstmt;
 264                         case SUBEXPR:
 265                                 {
 266                                         const char*     ss;
 267                                         const char*     ms = (char*)tlp->se.m[inst->subid].sp;
 268                                         const char*     me = (char*)tlp->se.m[inst->subid].ep;
 269
 270 #if DEBUG
 271                                         {
 272                                                 int     c;
 273
 274                                                 c = *me;
 275                                                 *me = 0;
 276                                                 error(-1, "subexpression %d ref=\"%s\"", inst->subid, ms);
 277                                                 *me = c;
 278                                                 error(-1, "subexpression %d src=\"%s\"", inst->subid, s);
 279                                         }
 280 #endif
 281                                         if (ms == me)
 282                                         {
 283                                                 inst = inst->next;
 284                                                 goto Switchstmt;
 285                                         }
 286                                         for (ss = s; ms < me && *ss++ == *ms; ms++);
 287                                         if (ms == me)
 288                                         {
 289                                                 s = ss - 1;
 290                                                 goto Addinst;
 291                                         }
 292                                 }
 293                                 break;
 294                         case END:
 295                                 /*
 296                                  * match!
 297                                  */
 298
 299                                 match = 1;
 300                                 tlp->se.m[0].ep = (char*)s;
 301                                 if (mp) newmatch(mp, &tlp->se);
 302                                 break;
 303                         default:
 304                                 /*
 305                                  * regular character
 306                                  */
 307
 308                                 if (inst->type == *s)
 309                                 {
 310  Addinst:
 311                                         if (newthread(nl, inst->next, &tlp->se) == nle)
 312                                                 goto Realloc;
 313                                 }
 314                                 break;
 315                         }
 316                 }
 317                 checkstart = startchar && !nl->inst;
 318         } while (*s++);
 319         if (list[0]) free(list[0]);
 320         return(match);
 321  Realloc:
 322         free(list[0]);
 323         list[0] = 0;
 324         listsize += LISTINCREMENT;
 325         goto Restart;
 326 }