glob.cpp

伯克利做的SFTP安全文件传输协议

// glob.cpp
// globber!
// copyright SafeTP Development Group, Inc., 2000  Terms of use are as specified in license.txt

#include "glob.h"      // this module
#include "str.h"       // stringb
#include "xassert.h"   // xassert, xfailure

#include <string.h>    // strchr

// match a prefix; return at first mismatch, or when entire
// match is found
void eatMatching(char const *&str, char const *&pattern)
{
  for (;;) {
    switch (*pattern) {
      case '\0':
      case '*':
        return;

      case '\\':
        if (!strchr("\\*?", pattern[1])) {
          xfailure(stringb("invalid escape sequence in pattern: " << pattern));
        }
        if (pattern[1] != str[0]) {
          return;    // with pattern still pointing at backslash
        }
        pattern++;
        break;

      case '?':
        if (*str == '\0') {
          return;
        }
        break;

      default:
        if (*pattern != *str) {
          return;
        }
        break;
    }
    pattern++;
    str++;
  }
}


bool glob(char const *str, char const *pattern)
{
  // prefix
  eatMatching(str, pattern);
  if (!*pattern && !*str) {
    return true;
  }
  if (*pattern != '*') {
    return false;
  }

  // internal substrings; uses inefficient O(n*m) algorithm,
  // but I don't care!
  for(;;) {
    xassert(*pattern == '*');
    pattern++;

    // find a substring in 'str' that will match with
    // pattern such that the mismatching char of pattern is
    // '*', or both end with '\0'
    for(;;) {
      char const *s = str;
      char const *p = pattern;
      eatMatching(s, p);
      if (*p == '*') {
        pattern = p;
        break;          // matched substring
      }
      if (*p == '\0' && *s == '\0') {
        return true;    // matched whole pattern
      }
      if (*s == '\0') {
        return false;   // failed to match entire pattern
      }
      str++;
    }
  }
}


// --------------------- test code ----------------------------
#ifdef TEST_GLOB

#include "test.h"       // USUAL_MAIN

void entry()
{
  struct S {
    char const *pattern;
    char const *str;
    bool answer;
  } arr[] = {
    { "foo", "foo", true },
    { "foo", "fOo", false },
    { "foo", "foobar", false },
    { "fo?", "foc", true },
    { "fo?", "foz", true },
    { "fo?", "fqz", false },
    { "fo?", "fq", false },
    { "fo?d", "food", true },
    { "fo?d", "fowd", true },
    { "fo?d", "fowc", false },
    { "foo*baz", "foobarbaz", true },
    { "foo*baz", "foobaz", true },
    { "foo*baz", "foobar", false },
    { "foo*baz", "foobazbar", false },
    { "*bar", "foobar", true },
    { "*bar", "bar", true },
    { "*bar", "barbq", false },
    { "*bar*", "barbq", true },
    { "*bar*", "bb_barbq", true },
    { "*bar*", "bb_bar", true },
    { "foo*bar*baz", "foobarbaz", true },
    { "foo*bar*baz", "fooEEbarbaz", true },
    { "foo*bar*baz", "foobarFFbaz", true },
    { "foo*bar*baz", "fooGbarFFbaz", true },
    { "foo*bar*baz", "fooGbarFFbazH", false },
    { "foo*bar*baz", "IfooGbarFFbaz", false },
    { "foo*bar*baz", "fooGbaFFbaz", false },
    { "foo*bar*baz", "fooGbaFFrbaz", false },
    { "a*de*i*klmn*rs*uvw*z", "abcdefghijklmnopqrstuvwxyz", true },
    { "a*de*i*klmn*rs*uvw*", "abcdefghijklmnopqrstuvwxyz", true },
    { "*de*i*klmn*rs*uvw*", "abcdefghijklmnopqrstuvwxyz", true },
    { "*df*i*klmn*rs*uvw*", "abcdefghijklmnopqrstuvwxyz", false },
    { "f\\?r", "f?r", true },
    { "f\\?r", "far", false },
    { "f\\*r", "f*r", true },
    { "f\\*r", "fr", false },
    { "f\\*r", "faar", false },
    { "f\\*r", "far", false },
    { "f\\\\r", "f\\r", true },
    { "f\\\\r", "f\\\\r", false },
    { "f\\\\r", "f\r", false },
  };

  int errors = 0;
  loopi(TABLESIZE(arr)) {
    if (glob(arr[i].str, arr[i].pattern) != arr[i].answer) {
      cout << "glob(\"" << arr[i].str << "\", \""
           << arr[i].pattern << "\") failed to equal "
           << arr[i].answer << endl;
      errors++;
    }
  }

  if (errors == 0) {
    cout << "all tests passed!\n";
  }
  else {
    cout << errors << " errors\n";
  }
}

USUAL_MAIN

#endif // TEST_GLOB