shell/match.c

   1 /*
   2  * ##/%% variable matching code ripped out of ash shell for code sharing
   3  *
   4  * This code is derived from software contributed to Berkeley by
   5  * Kenneth Almquist.
   6  *
   7  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
   8  *
   9  * Copyright (c) 1989, 1991, 1993, 1994
  10  *      The Regents of the University of California.  All rights reserved.
  11  *
  12  * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
  13  * was re-ported from NetBSD and debianized.
  14  */
  15 #ifdef STANDALONE
  16 # include <stdbool.h>
  17 # include <stdio.h>
  18 # include <stdlib.h>
  19 # include <string.h>
  20 # include <unistd.h>
  21 # define FAST_FUNC /* nothing */
  22 # define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
  23 # define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
  24 #else
  25 # include "libbb.h"
  26 #endif
  27 #include <fnmatch.h>
  28 #include "match.h"
  29
  30 #define pmatch(a, b) !fnmatch((a), (b), 0)
  31
  32 char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags)
  33 {
  34         char *loc;
  35         char *end;
  36         unsigned len = strlen(string);
  37         int early_exit;
  38
  39         /* We can stop the scan early only if the string part
  40          * we are matching against is shrinking, and the pattern has
  41          * an unquoted "star" at the corresponding end. There are two cases.
  42          * Case 1:
  43          * "qwerty" does not match against pattern "*zy",
  44          * no point in trying to match "werty", "erty" etc:
  45          */
  46         early_exit = (flags == (SCAN_MOVE_FROM_LEFT + SCAN_MATCH_RIGHT_HALF) && pattern[0] == '*');
  47
  48         if (flags & SCAN_MOVE_FROM_LEFT) {
  49                 loc = string;
  50                 end = string + len + 1;
  51         } else {
  52                 loc = string + len;
  53                 end = string - 1;
  54                 if (flags == (SCAN_MOVE_FROM_RIGHT + SCAN_MATCH_LEFT_HALF)) {
  55                         /* Case 2:
  56                          * "qwerty" does not match against pattern "qz*",
  57                          * no point in trying to match "qwert", "qwer" etc:
  58                          */
  59                         const char *p = pattern + strlen(pattern);
  60                         if (--p >= pattern && *p == '*') {
  61                                 early_exit = 1;
  62                                 while (--p >= pattern && *p == '\\')
  63                                         early_exit ^= 1;
  64                         }
  65                 }
  66         }
  67
  68         while (loc != end) {
  69                 char c;
  70                 int match;
  71
  72                 c = *loc;
  73                 if (flags & SCAN_MATCH_LEFT_HALF) {
  74                         *loc = '\0';
  75                         match = pmatch(pattern, string);
  76                         *loc = c;
  77                 } else {
  78                         match = pmatch(pattern, loc);
  79                 }
  80                 if (match)
  81                         return loc;
  82                 if (early_exit) {
  83 #ifdef STANDALONE
  84                         printf("(early exit) ");
  85 #endif
  86                         break;
  87                 }
  88
  89                 if (flags & SCAN_MOVE_FROM_LEFT) {
  90                         loc++;
  91                 } else {
  92                         loc--;
  93                 }
  94         }
  95         return NULL;
  96 }
  97
  98 #ifdef STANDALONE
  99 int main(int argc, char *argv[])
 100 {
 101         char *string;
 102         char *op;
 103         char *pattern;
 104         char *loc;
 105
 106         setvbuf(stdout, NULL, _IONBF, 0);
 107
 108         if (!argv[1]) {
 109                 puts(
 110                         "Usage: match <test> [test...]\n\n"
 111                         "Where a <test> is the form: <string><op><match>\n"
 112                         "This is to test the shell ${var#val} expression type.\n\n"
 113                         "e.g. `match 'abc#a*'` -> bc"
 114                 );
 115                 return 1;
 116         }
 117
 118         while (*++argv) {
 119                 size_t off;
 120                 unsigned scan_flags;
 121
 122                 string = *argv;
 123                 off = strcspn(string, "#%");
 124                 if (!off) {
 125                         printf("invalid format\n");
 126                         continue;
 127                 }
 128                 op = string + off;
 129                 scan_flags = pick_scan(op[0], op[1]);
 130
 131                 printf("'%s': flags:%x, ", string, scan_flags);
 132                 pattern = op + 1;
 133                 if (op[0] == op[1])
 134                         pattern++;
 135                 op[0] = '\0';
 136
 137                 loc = scan_and_match(string, pattern, scan_flags);
 138
 139                 if (scan_flags & SCAN_MATCH_LEFT_HALF) {
 140                         printf("'%s'\n", loc);
 141                 } else {
 142                         if (loc)
 143                                 *loc = '\0';
 144                         printf("'%s'\n", string);
 145                 }
 146         }
 147
 148         return 0;
 149 }
 150 #endif