summaryrefslogblamecommitdiff
path: root/tnet_io/KaldiLib/StkMatch.cc
blob: 4ff4b18f7149bdbfd3d5922f289c9cc838876860 (plain) (tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582





































































































































































































































































































































































































































































































































































































                                                                                                           
/*
 EPSHeader

   File: filmatch.c
   Author: J. Kercheval
   Created: Thu, 03/14/1991  22:22:01
*/

/*
 EPSRevision History
   O. Glembek    Thu, 03/11/2005  01:58:00  Added Mask extraction support (char % does this)
   J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
   J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
   J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
   J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
   J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
   J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
   J. Kercheval  Thu, 03/14/1991  22:22:25  remove '\' for DOS file parsing
   J. Kercheval  Thu, 03/28/1991  20:58:27  include filmatch.h
*/

/*
   Wildcard Pattern Matching
*/


#include "StkMatch.h"
#include "Common.h"

namespace TNet
{
  //#define TEST
  static int matche_after_star (register const char *pattern, register const char *text, register char *s);
  // following function is not defined or used.
  // static int fast_match_after_star (register const char *pattern, register const char *text);

  /*----------------------------------------------------------------------------
  *
  * Return true if PATTERN has any special wildcard characters
  *
  ----------------------------------------------------------------------------*/

  bool is_pattern (const char *p)
  {
      while ( *p ) {
          switch ( *p++ ) {
              case '?':
              case '*':
              case '%':
              case '[':
                return true;
          }
      }
      return false;
  }


  /*----------------------------------------------------------------------------
  *
  * Return true if PATTERN has is a well formed regular expression according
  * to the above syntax
  *
  * error_type is a return code based on the type of pattern error.  Zero is
  * returned in error_type if the pattern is a valid one.  error_type return
  * values are as follows:
  *
  *   PATTERN_VALID - pattern is well formed
  *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  *   PATTERN_EMPTY - [..] construct is empty (ie [])
  *
  ----------------------------------------------------------------------------*/

  bool is_valid_pattern (const char *p, int *error_type)
  {

  /* init error_type */
  *error_type = PATTERN_VALID;

    /* loop through pattern to EOS */
    while ( *p )
    {
      /* determine pattern type */
      switch ( *p )
      {
        /* the [..] construct must be well formed */
        case '[':
        {
          p++;

          /* if the next character is ']' then bad pattern */
          if ( *p == ']' ) {
            *error_type = PATTERN_EMPTY;
            return false;
          }

          /* if end of pattern here then bad pattern */
          if ( !*p )
          {
            *error_type = PATTERN_CLOSE;
            return false;
          }

          /* loop to end of [..] construct */
          while ( *p != ']' )
          {
            /* check for literal escape */
            if ( *p == '\\' )
            {
                p++;

                /* if end of pattern here then bad pattern */
                if ( !*p++ ) {
                    *error_type = PATTERN_ESC;
                    return false;
                }
            }
            else
                p++;

            /* if end of pattern here then bad pattern */
            if ( !*p )
            {
              *error_type = PATTERN_CLOSE;
              return false;
            }

            /* if this a range */
            if ( *p == '-' )
            {
              /* we must have an end of range */
              if ( !*++p || *p == ']' )
              {
                *error_type = PATTERN_RANGE;
                return false;
              }
              else
              {

                /* check for literal escape */
                if ( *p == '\\' )
                    p++;

                /* if end of pattern here then bad pattern */
                if ( !*p++ )
                {
                    *error_type = PATTERN_ESC;
                    return false;
                }
              }
            }
          }
          break;
        } //case '[':


        /* all other characters are valid pattern elements */
        case '*':
        case '?':
        case '%':
        default:
          p++;                              /* "normal" character */
          break;
      } // switch ( *p )
    } // while ( *p )

    return true;
  } //bool is_valid_pattern (const char *p, int *error_type)


  /*----------------------------------------------------------------------------
  *
  *  Match the pattern PATTERN against the string TEXT;
  *
  *  returns MATCH_VALID if pattern matches, or an errorcode as follows
  *  otherwise:
  *
  *            MATCH_PATTERN  - bad pattern
  *            MATCH_RANGE    - match failure on [..] construct
  *            MATCH_ABORT    - premature end of text string
  *            MATCH_END      - premature end of pattern string
  *            MATCH_VALID    - valid match
  *
  *
  *  A match means the entire string TEXT is used up in matching.
  *
  *  In the pattern string:
  *       `*' matches any sequence of characters (zero or more)
  *       `?' matches any character
  *       `%' matches any character and stores it in the s string
  *       [SET] matches any character in the specified set,
  *       [!SET] or [^SET] matches any character not in the specified set.
  *       \ is allowed within a set to escape a character like ']' or '-'
  *
  *  A set is composed of characters or ranges; a range looks like
  *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  *  minimal set of characters allowed in the [..] pattern construct.
  *  Other characters are allowed (ie. 8 bit characters) if your system
  *  will support them.
  *
  *  To suppress the special syntactic significance of any of `[]*?%!^-\',
  *  within a [..] construct and match the character exactly, precede it
  *  with a `\'.
  *
  ----------------------------------------------------------------------------*/

  int matche ( register const char *p, register const char *t, register char *s )
  {
      register char range_start, range_end;  /* start and end in range */

      bool invert;             /* is this [..] or [!..] */
      bool member_match;       /* have I matched the [..] construct? */
      bool loop;               /* should I terminate? */

      for ( ; *p; p++, t++ ) {

          /* if this is the end of the text then this is the end of the match */
          if (!*t) {
              return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
          }

          /* determine and react to pattern type */
          switch ( *p ) {

              /* single any character match */
              case '?':
                  break;

              /* single any character match, with extraction*/
              case '%': {
                  *s++ = *t;
                  *s   = '\0';
                  break;
              }

              /* multiple any character match */
              case '*':
                  return matche_after_star (p, t, s);

              /* [..] construct, single member/exclusion character match */
              case '[': {
                /* move to beginning of range */
                p++;

                /* check if this is a member match or exclusion match */
                invert = false;
                if ( *p == '!' || *p == '^') {
                    invert = true;
                    p++;
                }

                /* if closing bracket here or at range start then we have a
                   malformed pattern */
                if ( *p == ']' ) {
                    return MATCH_PATTERN;
                }

                member_match = false;
                loop = true;

                while ( loop ) {

                    /* if end of construct then loop is done */
                    if (*p == ']') {
                        loop = false;
                        continue;
                    }

                    /* matching a '!', '^', '-', '\' or a ']' */
                    if ( *p == '\\' ) {
                        range_start = range_end = *++p;
                    }
                    else {
                        range_start = range_end = *p;
                    }

                    /* if end of pattern then bad pattern (Missing ']') */
                    if (!*p)
                        return MATCH_PATTERN;

                    /* check for range bar */
                    if (*++p == '-') {

                        /* get the range end */
                        range_end = *++p;

                        /* if end of pattern or construct then bad pattern */
                        if (range_end == '\0' || range_end == ']')
                            return MATCH_PATTERN;

                        /* special character range end */
                        if (range_end == '\\') {
                            range_end = *++p;

                            /* if end of text then we have a bad pattern */
                            if (!range_end)
                                return MATCH_PATTERN;
                        }

                        /* move just beyond this range */
                        p++;
                    }

                    /* if the text character is in range then match found.
                       make sure the range letters have the proper
                       relationship to one another before comparison */
                    if ( range_start < range_end  ) {
                        if (*t >= range_start && *t <= range_end) {
                            member_match = true;
                            loop = false;
                        }
                    }
                    else {
                        if (*t >= range_end && *t <= range_start) {
                            member_match = true;
                            loop = false;
                        }
                    }
                }

                /* if there was a match in an exclusion set then no match */
                /* if there was no match in a member set then no match */
                if ((invert && member_match) ||
                   !(invert || member_match))
                    return MATCH_RANGE;

                /* if this is not an exclusion then skip the rest of the [...]
                    construct that already matched. */
                if (member_match) {
                    while (*p != ']') {

                        /* bad pattern (Missing ']') */
                        if (!*p)
                            return MATCH_PATTERN;

                        /* skip exact match */
                        if (*p == '\\') {
                            p++;

                            /* if end of text then we have a bad pattern */
                            if (!*p)
                                return MATCH_PATTERN;
                        }

                        /* move to next pattern char */
                        p++;
                    }
                }

                break;
            } // case ']'

            /* must match this character exactly */
            default:
                if (*p != *t)
                    return MATCH_LITERAL;
        }
      }

      //*s = '\0';
      /* if end of text not reached then the pattern fails */
      if ( *t )
          return MATCH_END;
      else
          return MATCH_VALID;
  }


  /*----------------------------------------------------------------------------
  *
  * recursively call matche() with final segment of PATTERN and of TEXT.
  *
  ----------------------------------------------------------------------------*/

  static int matche_after_star (register const char *p, register const char *t, register char *s)
  {
      register int match = 0;
      register char nextp;

      /* pass over existing ? and * in pattern */
      while ( *p == '?' || *p == '%' || *p == '*' ) {

          /* take one char for each ? and + */
          if ( *p == '?') {

              /* if end of text then no match */
              if ( !*t++ ) {
                  return MATCH_ABORT;
              }
          }

          if ( *p == '%') {
              *s++ = *t;
              *s   = '\0';
              /* if end of text then no match */
              if ( !*t++ ) {
                  return MATCH_ABORT;
              }
          }

          /* move to next char in pattern */
          p++;
      }

      /* if end of pattern we have matched regardless of text left */
      if ( !*p ) {
          return MATCH_VALID;
      }

      /* get the next character to match which must be a literal or '[' */
      nextp = *p;

      /* Continue until we run out of text or definite result seen */
      do {

          /* a precondition for matching is that the next character
             in the pattern match the next character in the text or that
             the next pattern char is the beginning of a range.  Increment
             text pointer as we go here */
          if ( nextp == *t || nextp == '[' ) {
              match = matche(p, t, s);
          }

          /* if the end of text is reached then no match */
          if ( !*t++ ) match = MATCH_ABORT;

      } while ( match != MATCH_VALID && 
                match != MATCH_ABORT &&
                match != MATCH_PATTERN);

      /* return result */
      return match;
  }


  /*----------------------------------------------------------------------------
  *
  * match() is a shell to matche() to return only bool values.
  *
  ----------------------------------------------------------------------------*/

  bool match(const  char *p, const char *t, char *s)
  {
      int error_type;
      error_type = matche(p,t,s);
      return (error_type != MATCH_VALID ) ? false : true;
  }


  //***************************************************************************
  //***************************************************************************
  bool
  ProcessMask(const std::string & rString,
              const std::string & rWildcard,
                    std::string & rSubstr)
  {
    char *  substr;
    int     percent_count        = 0;
    int     ret ;
    size_t  pos                  = 0;

    // let's find how many % to allocate enough space for the return substring
    while ((pos = rWildcard.find('%', pos)) != rWildcard.npos)
    {
      percent_count++;
      pos++;
    }

    // allocate space for the substring
    substr = new char[percent_count + 1];
    substr[percent_count] = 0;
    substr[0]             = '\0';

    // optionally prepend '*/' to wildcard
    std::string wildcard(rWildcard);
    if(wildcard[0] != '*') {
      wildcard = "*/" + wildcard;
    }

    //optionally prepend '/' to string
    std::string string1(rString);
    if(string1[0] != '/') {
      string1 = "/" + string1;
    }

    // parse the string
    if (0 != (ret = match(wildcard.c_str(), string1.c_str(), substr)))
    {
      rSubstr = substr;
    }
    delete[] substr;
    return ret;
  } // ProcessMask
}


#ifdef TEST

/*
* This test main expects as first arg the pattern and as second arg
* the match string.  Output is yaeh or nay on match.  If nay on
* match then the error code is parsed and written.
*/

#include <stdio.h>

int main(int argc, char *argv[])
{
    int error;
    int is_valid_error;

    char * tmp = argv[0];
    int i = 0;
    for (; *tmp; tmp++)
      if (*tmp=='%') i++;

    char s[i+1];


    if (argc != 3) {
        printf("Usage:  MATCH Pattern Text\n");
    }
    else {
        printf("Pattern: %s\n", argv[1]);
        printf("Text   : %s\n", argv[2]);
        
        if (!is_pattern(argv[1])) {
            printf("    First Argument Is Not A Pattern\n");
        }
        else {
            match(argv[1],argv[2], s) ? printf("true") : printf("false");
            error = matche(argv[1],argv[2], s);
            is_valid_pattern(argv[1],&is_valid_error);

            switch ( error ) {
                case MATCH_VALID:
                    printf("    Match Successful");
                    if (is_valid_error != PATTERN_VALID)
                        printf(" -- is_valid_pattern() is complaining\n");
                    else
                        printf("\n");
                    printf("%s\n", s);

                    break;
                case MATCH_RANGE:
                    printf("    Match Failed on [..]\n");
                    break;
                case MATCH_ABORT:
                    printf("    Match Failed on Early Text Termination\n");
                    break;
                case MATCH_END:
                    printf("    Match Failed on Early Pattern Termination\n");
                    break;
                case MATCH_PATTERN:
                    switch ( is_valid_error ) {
                        case PATTERN_VALID:
                            printf("    Internal Disagreement On Pattern\n");
                            break;
                        case PATTERN_RANGE:
                            printf("    No End of Range in [..] Construct\n");
                            break;
                        case PATTERN_CLOSE:
                            printf("    [..] Construct is Open\n");
                            break;
                        case PATTERN_EMPTY:
                            printf("    [..] Construct is Empty\n");
                            break;
                        default:
                            printf("    Internal Error in is_valid_pattern()\n");
                    }
                    break;
                default:
                    printf("    Internal Error in matche()\n");
                    break;
            }
        }

    }
    return(0);
}

#endif