usr/src/lib/libast/common/string/fmtmatch.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 #pragma prototyped
  23 /*
  24  * Glenn Fowler
  25  * AT&T Research
  26  *
  27  * return strmatch() expression given REG_AUGMENTED RE
  28  * 0 returned for invalid RE
  29  */
  30
  31 #include <ast.h>
  32
  33 char*
  34 fmtmatch(const char* as)
  35 {
  36         register char*  s = (char*)as;
  37         register int    c;
  38         register char*  t;
  39         register char** p;
  40         register char*  b;
  41         char*           x;
  42         char*           y;
  43         char*           z;
  44         int             a;
  45         int             e;
  46         int             n;
  47         char*           buf;
  48         char*           stack[32];
  49
  50         c = 3 * (strlen(s) + 1);
  51         buf = fmtbuf(c);
  52         t = b = buf + 3;
  53         p = stack;
  54         if (a = *s == '^')
  55                 s++;
  56         e = 0;
  57         for (;;)
  58         {
  59                 switch (c = *s++)
  60                 {
  61                 case 0:
  62                         break;
  63                 case '\\':
  64                         if (!(c = *s++))
  65                                 return 0;
  66                         switch (*s)
  67                         {
  68                         case '*':
  69                         case '+':
  70                         case '?':
  71                                 *t++ = *s++;
  72                                 *t++ = '(';
  73                                 *t++ = '\\';
  74                                 *t++ = c;
  75                                 c = ')';
  76                                 break;
  77                         case '|':
  78                         case '&':
  79                                 if (c == '(')
  80                                 {
  81                                         *t++ = c;
  82                                         c = *s++;
  83                                         goto logical;
  84                                 }
  85                                 break;
  86                         case '{':
  87                         case '}':
  88                                 break;
  89                         default:
  90                                 *t++ = '\\';
  91                                 break;
  92                         }
  93                         *t++ = c;
  94                         continue;
  95                 case '[':
  96                         x = t;
  97                         *t++ = c;
  98                         if ((c = *s++) == '^')
  99                         {
 100                                 *t++ = '!';
 101                                 c = *s++;
 102                         }
 103                         else if (c == '!')
 104                         {
 105                                 *t++ = '\\';
 106                                 *t++ = c;
 107                                 c = *s++;
 108                         }
 109                         for (;;)
 110                         {
 111                                 if (!(*t++ = c))
 112                                         return 0;
 113                                 if (c == '\\')
 114                                         *t++ = c;
 115                                 if ((c = *s++) == ']')
 116                                 {
 117                                         *t++ = c;
 118                                         break;
 119                                 }
 120                         }
 121                         switch (*s)
 122                         {
 123                         case '*':
 124                         case '+':
 125                         case '?':
 126                                 for (y = t + 2, t--; t >= x; t--)
 127                                         *(t + 2) = *t;
 128                                 *++t = *s++;
 129                                 *++t = '(';
 130                                 t = y;
 131                                 *t++ = ')';
 132                                 break;
 133                         }
 134                         continue;
 135                 case '(':
 136                         if (p >= &stack[elementsof(stack)])
 137                                 return 0;
 138                         *p++ = t;
 139                         if (*s == '?')
 140                         {
 141                                 s++;
 142                                 if (*s == 'K' && *(s + 1) == ')')
 143                                 {
 144                                         s += 2;
 145                                         p--;
 146                                         while (*t = *s)
 147                                                 t++, s++;
 148                                         continue;
 149                                 }
 150                                 *t++ = '~';
 151                         }
 152                         else
 153                                 *t++ = '@';
 154                         *t++ = '(';
 155                         continue;
 156                 case ')':
 157                         if (p == stack)
 158                                 return 0;
 159                         p--;
 160                         *t++ = c;
 161                         switch (*s)
 162                         {
 163                         case 0:
 164                                 break;
 165                         case '*':
 166                         case '+':
 167                         case '?':
 168                         case '!':
 169                                 **p = *s++;
 170                                 if (*s == '?')
 171                                 {
 172                                         s++;
 173                                         x = *p + 1;
 174                                         for (y = ++t; y > x; y--)
 175                                                 *y = *(y - 1);
 176                                         *x = '-';
 177                                 }
 178                                 continue;
 179                         case '{':
 180                                 for (z = s; *z != '}'; z++)
 181                                         if (!*z)
 182                                                 return 0;
 183                                 n = z - s;
 184                                 if (*++z == '?')
 185                                         n++;
 186                                 x = *p + n;
 187                                 for (y = t += n; y > x; y--)
 188                                         *y = *(y - n);
 189                                 for (x = *p; s < z; *x++ = *s++);
 190                                 if (*s == '?')
 191                                 {
 192                                         s++;
 193                                         *x++ = '-';
 194                                 }
 195                                 continue;
 196                         default:
 197                                 continue;
 198                         }
 199                         break;
 200                 case '.':
 201                         switch (*s)
 202                         {
 203                         case 0:
 204                                 *t++ = '?';
 205                                 break;
 206                         case '*':
 207                                 s++;
 208                                 *t++ = '*';
 209                                 e = !*s;
 210                                 continue;
 211                         case '+':
 212                                 s++;
 213                                 *t++ = '?';
 214                                 *t++ = '*';
 215                                 continue;
 216                         case '?':
 217                                 s++;
 218                                 *t++ = '?';
 219                                 *t++ = '(';
 220                                 *t++ = '?';
 221                                 *t++ = ')';
 222                                 continue;
 223                         default:
 224                                 *t++ = '?';
 225                                 continue;
 226                         }
 227                         break;
 228                 case '*':
 229                 case '+':
 230                 case '?':
 231                 case '{':
 232                         n = *(t - 1);
 233                         if (t == b || n == '(' || n == '|')
 234                                 return 0;
 235                         *(t - 1) = c;
 236                         if (c == '{')
 237                         {
 238                                 for (z = s; *z != '}'; z++)
 239                                         if (!*z)
 240                                                 return 0;
 241                                 for (; s <= z; *t++ = *s++);
 242                         }
 243                         if (*s == '?')
 244                         {
 245                                 s++;
 246                                 *t++ = '-';
 247                         }
 248                         *t++ = '(';
 249                         *t++ = n;
 250                         *t++ = ')';
 251                         continue;
 252                 case '|':
 253                 case '&':
 254                         if (t == b || *(t - 1) == '(')
 255                                 return 0;
 256                 logical:
 257                         if (!*s || *s == ')')
 258                                 return 0;
 259                         if (p == stack && b == buf + 3)
 260                         {
 261                                 *--b = '(';
 262                                 *--b = '@';
 263                         }
 264                         *t++ = c;
 265                         continue;
 266                 case '$':
 267                         if (e = !*s)
 268                                 break;
 269                         /*FALLTHROUGH*/
 270                 default:
 271                         *t++ = c;
 272                         continue;
 273                 }
 274                 break;
 275         }
 276         if (p != stack)
 277                 return 0;
 278         if (b != buf + 3)
 279                 *t++ = ')';
 280         if (!a && (*b != '*' || *(b + 1) == '(' || (*(b + 1) == '-' || *(b + 1) == '~') && *(b + 2) == '('))
 281                 *--b = '*';
 282         if (!e)
 283                 *t++ = '*';
 284         *t = 0;
 285         return b;
 286 }