rom/dos/patternmatching.c

   1 /*
   2     Copyright © 1995-2011, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     Desc: Pattern matching and parsing functionality
   6     Lang: English
   7 */
   8
   9 #include <exec/memory.h>
  10 #include <proto/exec.h>
  11 #include <proto/utility.h>
  12 #include <proto/dos.h>
  13 #include <dos/dosextens.h>
  14 #include <dos/dosasl.h>
  15
  16 #include "dos_intern.h"
  17
  18 /*
  19   A simple method for pattern matching with multiple wildcards:
  20   I use markers that consist of both a pointer into the string
  21   and one into the pattern. The marker simply follows the string
  22   and everytime it hits a wildcard it's split into two new markers
  23   (one to assume that the wildcard match has ended and one to assume
  24   that it continues). If a marker doesn't fit any longer it's
  25   removed and if all of them are gone the pattern mismatches.
  26   OTOH if any of the markers reaches the end of both the string
  27   and the pattern simultaneously the pattern matches the string.
  28 */
  29
  30 /*
  31  * INPUTS
  32  *
  33  *   pat      --  Pattern string (as returned by ParsePatternXXXX())
  34  *   str      --  The string to match against the pattern 'pat'
  35  *   case     --  Determines if the case is important or not
  36  *   DOSBase  --  dos.library base
  37  *
  38  */
  39
  40
  41 BOOL patternMatch(CONST_STRPTR pat, CONST_STRPTR str, BOOL useCase,
  42                   struct DosLibrary *DOSBase)
  43 {
  44     CONST_STRPTR  s;
  45     BOOL    match = FALSE;
  46
  47     struct markerarray   ma;
  48     struct markerarray  *macur = &ma;
  49     struct markerarray  *cur2;
  50
  51     LONG   macnt = 0;
  52     LONG   cnt2;
  53
  54     ULONG  level;
  55     UBYTE  a, b, c, t;
  56
  57     LONG error;
  58
  59 #undef  ERROR
  60 #define ERROR(a) { error = (a); goto end; }
  61
  62     ma.next = ma.prev = NULL;
  63
  64     while(TRUE)
  65     {
  66         switch(*pat)
  67         {
  68         case P_REPBEG: /* _#(_a), _#a_ or _#[_a] */
  69             PUSH(0, ++pat, str);
  70             level = 1;
  71
  72             while(TRUE)
  73             {
  74                 c = *pat++;
  75
  76                 if(c == P_REPBEG)
  77                 {
  78                     level++;
  79                 }
  80                 else if(c == P_REPEND)
  81                 {
  82                     if(!--level)
  83                     {
  84                         break;
  85                     }
  86                 }
  87             }
  88             break;
  89
  90         case P_REPEND: /* #(a_)_ */
  91             level = 1;
  92
  93             while(TRUE)
  94             {
  95                 c = *--pat;
  96
  97                 if(c == P_REPEND)
  98                 {
  99                     level++;
 100                 }
 101                 else if(c == P_REPBEG)
 102                 {
 103                     if(!--level)
 104                     {
 105                         break;
 106                     }
 107                 }
 108             }
 109             break;
 110
 111         case P_NOT: /* _~(_a) */
 112             s = ++pat;
 113             level = 1;
 114
 115             while(TRUE)
 116             {
 117                 c = *s++;
 118
 119                 if(c == P_NOT)
 120                 {
 121                     level++;
 122                 }
 123                 else if(c == P_NOTEND)
 124                 {
 125                     if(!--level)
 126                     {
 127                         break;
 128                     }
 129                 }
 130             }
 131
 132             PUSH(1, s, str);
 133             break;
 134
 135         case P_NOTEND: /* ~(a_)_ */
 136             cnt2 = macnt;
 137             cur2 = macur;
 138
 139             do
 140             {
 141                 cnt2--;
 142
 143                 if(cnt2 < 0)
 144                 {
 145                     cnt2 = 127;
 146                     cur2 = cur2->prev;
 147                 }
 148             }while(!cur2->marker[cnt2].type);
 149
 150             if(!*str++)
 151             {
 152                 macnt = cnt2;
 153                 macur=cur2;
 154             }
 155             else if(str > cur2->marker[cnt2].str)
 156             {
 157                     cur2->marker[cnt2].str = str;
 158             }
 159
 160             POP(t, pat, str);
 161
 162             if(t && *str)
 163             {
 164                 PUSH(1, pat, str + 1);
 165             }
 166
 167             break;
 168
 169         case P_ORSTART: /* ( */
 170             s = ++pat;
 171             level = 1;
 172
 173             while(TRUE)
 174             {
 175                 c = *s++;
 176
 177                 if(c == P_ORSTART)
 178                 {
 179                     level++;
 180                 }
 181                 else if(c == P_ORNEXT)
 182                 {
 183                     if(level == 1)
 184                     {
 185                         PUSH(0, s, str);
 186                     }
 187                 }
 188                 else if(c == P_OREND)
 189                 {
 190                     if(!--level)
 191                     {
 192                         break;
 193                     }
 194                 }
 195             }
 196
 197             break;
 198
 199         case P_ORNEXT: /* | */
 200             pat++;
 201             level = 1;
 202
 203             while(TRUE)
 204             {
 205                 c = *pat++;
 206
 207                 if(c == P_ORSTART)
 208                 {
 209                     level++;
 210                 }
 211                 else if(c == P_OREND)
 212                 {
 213                     if(!--level)
 214                     {
 215                         break;
 216                     }
 217                 }
 218             }
 219
 220             break;
 221
 222         case P_OREND: /* ) */
 223             pat++;
 224             break;
 225
 226         case P_SINGLE: /* ? */
 227             pat++;
 228
 229             if(*str)
 230             {
 231                 str++;
 232             }
 233             else
 234             {
 235                 POP(t, pat, str);
 236
 237                 if(t && *str)
 238                 {
 239                     PUSH(1, pat, str + 1);
 240                 }
 241             }
 242
 243             break;
 244
 245         case P_CLASS: /* [ */
 246             pat++;
 247
 248             while(TRUE)
 249             {
 250                 a = b = *pat++;
 251
 252                 if(a == P_CLASS)
 253                 {
 254                     POP(t, pat, str);
 255
 256                     if(t && *str)
 257                     {
 258                         PUSH(1, pat, str + 1);
 259                     }
 260
 261                     break;
 262                 }
 263
 264                 if(*pat == '-')
 265                 {
 266                     b = *++pat;
 267
 268                     if(b == P_CLASS)
 269                     {
 270                         b = 255;
 271                     }
 272                 }
 273
 274                 if(useCase)
 275                 {
 276                     c = *str;
 277                 }
 278                 else
 279                 {
 280                     c = ToUpper(*str);
 281                 }
 282
 283                 if(c >= a && c <= b)
 284                 {
 285                     str++;
 286
 287                     while(*pat++ != P_CLASS)
 288                         ;
 289
 290                     break;
 291                 }
 292             }
 293
 294             break;
 295
 296         case P_NOTCLASS: /* [~ */
 297             if(!*str)
 298             {
 299                 POP(t, pat, str);
 300
 301                 if(t && *str)
 302                 {
 303                     PUSH(1, pat, str + 1);
 304                 }
 305
 306                 break;
 307             }
 308
 309             pat++;
 310
 311             while(TRUE)
 312             {
 313                 a = b = *pat++;
 314
 315                 if(a == P_CLASS)
 316                 {
 317                     str++;
 318                     break;
 319                 }
 320
 321                 if(*pat == '-')
 322                 {
 323                     b = *++pat;
 324
 325                     if(b == P_CLASS)
 326                     {
 327                         b = 255;
 328                     }
 329                 }
 330
 331                 if(useCase)
 332                 {
 333                     c = *str;
 334                 }
 335                 else
 336                 {
 337                     c = ToUpper(*str);
 338                 }
 339
 340                 if(c >= a && c <= b)
 341                 {
 342                     POP(t, pat, str);
 343
 344                     if(t && *str)
 345                     {
 346                         PUSH(1, pat, str + 1);
 347                     }
 348
 349                     break;
 350                 }
 351             }
 352
 353             break;
 354
 355         case P_ANY: /* #? */
 356             /* This often used pattern has extra treatment to be faster */
 357             if(*str)
 358             {
 359                 PUSH(0, pat, str + 1);
 360             }
 361
 362             pat++;
 363             break;
 364
 365         case 0:
 366             if(!*str)
 367             {
 368                 match = TRUE;
 369                 ERROR(0);
 370             }
 371             else
 372             {
 373                 POP(t, pat, str);
 374
 375                 if(t && *str)
 376                 {
 377                     PUSH(1, pat, str + 1);
 378                 }
 379             }
 380             break;
 381
 382         default:
 383             {
 384                 UBYTE ch;
 385
 386                 if(useCase)
 387                 {
 388                     ch = *str;
 389                 }
 390                 else
 391                 {
 392                     ch = ToUpper(*str);
 393                 }
 394
 395                 if(*pat++ == ch)
 396                 {
 397                     str++;
 398                 }
 399                 else
 400                 {
 401                     POP(t, pat, str);
 402
 403                     if(t && *str)
 404                     {
 405                         PUSH(1, pat, str + 1);
 406                     }
 407                 }
 408             }
 409
 410             break;
 411
 412         } /* switch(*pat) */
 413     } /* while(TRUE) */
 414
 415  end:
 416
 417     macur = ma.next;
 418
 419     while(macur != NULL)
 420     {
 421         struct markerarray *next = macur->next;
 422
 423         FreeMem(macur, sizeof(struct markerarray));
 424         macur = next;
 425     }
 426
 427     SetIoErr(error);
 428
 429     return match;
 430 }
 431
 432
 433 LONG patternParse(CONST_STRPTR Source, STRPTR Dest, LONG DestLength,
 434     BOOL useCase, struct DosLibrary *DOSBase)
 435 {
 436     STRPTR  stack;
 437     STRPTR  end;
 438     UBYTE   a;
 439     LONG    iswild = 0;
 440
 441 #undef ERROR
 442 #define ERROR(a) { SetIoErr(a); return -1; }
 443     stack = end = Dest + DestLength;
 444 #define PUT(a) { if(Dest >= stack) ERROR(ERROR_BUFFER_OVERFLOW); *Dest++ = (a); }
 445
 446     if(!*Source)
 447     {
 448         PUT(0);
 449         return 0;
 450     }
 451
 452     while(*Source)
 453     {
 454         switch(*Source++)
 455         {
 456         case '#':
 457             iswild = 1;
 458
 459             switch(*Source)
 460             {
 461             case '?':
 462                 Source++;
 463                 PUT(P_ANY);
 464                 break;
 465
 466             case ')':
 467             case '\0':
 468                 ERROR(ERROR_BAD_TEMPLATE);
 469                 break;
 470
 471             default:
 472                 PUT(P_REPBEG);
 473                 *--stack = P_REPEND;
 474                 continue;
 475             }
 476
 477             break;
 478
 479         case '~':
 480             switch(*Source)
 481             {
 482             case '\0':
 483                 a = Source[-1];
 484                 PUT(useCase ? a : ToUpper(a));
 485                 break;
 486
 487             case ')':
 488                 ERROR(ERROR_BAD_TEMPLATE);
 489                 break;
 490
 491             default:
 492                 iswild = 1;
 493                 PUT(P_NOT);
 494                 *--stack = P_NOTEND;
 495                 continue;
 496             }
 497
 498             break;
 499
 500         case '?':
 501             iswild = 1;
 502             PUT(P_SINGLE);
 503             continue;
 504
 505         case '(':
 506             PUT(P_ORSTART);
 507             *--stack = P_OREND;
 508             continue;
 509
 510         case '|':
 511             iswild = 1;
 512
 513             if(stack == end)
 514             {
 515                 ERROR(ERROR_BAD_TEMPLATE);
 516             }
 517
 518             while(!(*stack == P_OREND || stack == end))
 519             {
 520                 PUT(*stack++);
 521             }
 522
 523             PUT(P_ORNEXT);
 524             continue;
 525
 526         case ')':
 527             while(!(stack == end || *stack == P_OREND))
 528             {
 529                 PUT(*stack++);
 530             }
 531
 532             if(stack == end)
 533             {
 534                 ERROR(ERROR_BAD_TEMPLATE);
 535             }
 536             else
 537             {
 538                 PUT(*stack++);
 539             }
 540
 541             break;
 542
 543         case '[':
 544             iswild = 1;
 545
 546             if(*Source == '~')
 547             {
 548                 Source++;
 549                 PUT(P_NOTCLASS);
 550             }
 551             else
 552             {
 553                 PUT(P_CLASS);
 554             }
 555
 556             a = *Source++;
 557
 558             if(!a)
 559             {
 560                 ERROR(ERROR_BAD_TEMPLATE);
 561             }
 562
 563             do
 564             {
 565                 if(a == '\'')
 566                 {
 567                     a=*Source++;
 568                 }
 569
 570                 PUT(useCase ? a : ToUpper(a));
 571                 a = *Source++;
 572
 573                 if(!a)
 574                 {
 575                     ERROR(ERROR_BAD_TEMPLATE);
 576                 }
 577             } while(a != ']');
 578
 579             PUT(P_CLASS);
 580             break;
 581
 582         case '*':
 583             if (DOSBase->dl_Root->rn_Flags & RNF_WILDSTAR)
 584             {
 585                 iswild = 1;
 586                 PUT(P_ANY);
 587             }
 588             else
 589             {
 590                 PUT('*');
 591             }
 592
 593             break;
 594
 595         case '%':
 596             continue;
 597
 598         case '\'':
 599             switch(*Source)
 600             {
 601             case '#':
 602             case '*':
 603             case '?':
 604             case '(':
 605             case '|':
 606             case ')':
 607             case '~':
 608             case '[':
 609             case ']':
 610             case '%':
 611             case '\'':
 612                 Source++;
 613             default:
 614                 break;
 615             }
 616
 617             /* Fall through */
 618         default:
 619             a = Source[-1];
 620             PUT(useCase ? a : ToUpper(a));
 621             break;
 622         }
 623
 624         while(stack != end && *stack != P_OREND)
 625         {
 626             PUT(*stack++);
 627         }
 628     }
 629
 630     if(stack != end)
 631     {
 632         ERROR(ERROR_BAD_TEMPLATE);
 633     }
 634
 635     PUT(0);
 636
 637     return iswild;
 638 }