pattern.cpp

一些unix下的c/c++的util包

    if (j != -1) return j;
  }
  return next->match(str, matcher, curInd);
}

// NFALazyQuantifierNode

NFALazyQuantifierNode::NFALazyQuantifierNode(Pattern * pat, NFANode * internal, const int minMatch, const int maxMatch)
                      : NFAQuantifierNode(pat, internal, minMatch, maxMatch) { }
int NFALazyQuantifierNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int i, j, m = NFAQuantifierNode::match(str, matcher, curInd);

  if (m == -1) return -1;

  for (i = min; i < max; ++i)
  {
    j = next->match(str, matcher, m);
    if (j == -1)
    {
      j = inner->match(str, matcher, m);
      // if j < m, then j is -1, so we bail.
      // if j == m, then we would just go and call next->match on the same index,
      // but it already failed trying to match right there, so we know we can
      // just bail
      if (j <= m) return -1;
      m = j;
    }
    else return j;
  }
  return next->match(str, matcher, m);
}

// NFAPossessiveQuantifierNode

NFAPossessiveQuantifierNode::NFAPossessiveQuantifierNode(Pattern * pat, NFANode * internal, const int minMatch, const int maxMatch)
                            : NFAQuantifierNode(pat, internal, minMatch, maxMatch) { }
int NFAPossessiveQuantifierNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int i, j, m = NFAQuantifierNode::match(str, matcher, curInd);

  if (m == -1) return -1;
  for (i = min; i < max; ++i)
  {
    j = inner->match(str, matcher, m);
    if (j <= m) return next->match(str, matcher, m);
    m = j;
  }
  return next->match(str, matcher, m);
}

// NFAAcceptNode

NFAAcceptNode::NFAAcceptNode() { }
int NFAAcceptNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (!next) return curInd;
  else return next->match(str, matcher, curInd);
}

// NFAClassNode

NFAClassNode::NFAClassNode(const bool invert)
{
  inv = invert;
}
NFAClassNode::NFAClassNode(const std::string & clazz, const bool invert)
{
  inv = invert;
  for (int i = 0; i < (int)clazz.size(); ++i) vals[clazz[i]] = 1;
}
int NFAClassNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd < (int)str.size() && ((vals.find(str[curInd]) != vals.end()) ^ inv))
  {
    return next->match(str, matcher, curInd + 1);
  }
  return -1;
}

// NFACIClassNode

NFACIClassNode::NFACIClassNode(const bool invert)
{
  inv = invert;
}
NFACIClassNode::NFACIClassNode(const std::string & clazz, const bool invert)
{
  inv = invert;
  for (int i = 0; i < (int)clazz.size(); ++i) vals[tolower(clazz[i])] = 1;
}
int NFACIClassNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd < (int)str.size() && ((vals.find(tolower(str[curInd])) != vals.end()) ^ inv))
  {
    return next->match(str, matcher, curInd + 1);
  }
  return -1;
}

#undef to_lower

// NFASubStartNode

NFASubStartNode::NFASubStartNode() { }
int NFASubStartNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  return next->match(str, matcher, curInd);
}

// NFAOrNode

NFAOrNode::NFAOrNode(NFANode * first, NFANode * second) : one(first), two(second) { }
void NFAOrNode::findAllNodes(std::map<NFANode*, bool> & soFar)
{
  if (one) one->findAllNodes(soFar);
  if (two) two->findAllNodes(soFar);
  NFANode::findAllNodes(soFar);
}
int NFAOrNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int ci = one->match(str, matcher, curInd);

  if (ci != -1) ci = next->match(str, matcher, ci);
  if (ci != -1) return ci;
  if (ci == -1) ci = two->match(str, matcher, curInd);
  if (ci != -1) ci = next->match(str, matcher, ci);
  return ci;
}

// NFAQuoteNode

NFAQuoteNode::NFAQuoteNode(const std::string & quoted) : qStr(quoted) { }
int NFAQuoteNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd + qStr.size() > str.size())       return -1;
  if (str.substr(curInd, qStr.size()) != qStr) return -1;
  return next->match(str, matcher, curInd + qStr.size());
}

// NFACIQuoteNode

NFACIQuoteNode::NFACIQuoteNode(const std::string & quoted) : qStr(quoted) { }
int NFACIQuoteNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd + qStr.size() > str.size()) return -1;
  if (str_icmp(str.substr(curInd, qStr.size()).c_str(),  qStr.c_str())) return -1;
  return next->match(str, matcher, qStr.size());
}

// NFALookAheadNode

NFALookAheadNode::NFALookAheadNode(NFANode * internal, const bool positive) : NFANode(), pos(positive), inner(internal) { }
void NFALookAheadNode::findAllNodes(std::map<NFANode*, bool> & soFar)
{
  if (inner) inner->findAllNodes(soFar);
  NFANode::findAllNodes(soFar);
}
int NFALookAheadNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  return ((inner->match(str, matcher, curInd) == -1) ^ pos) ? next->match(str, matcher, curInd) : -1;
}

// NFALookBehindNode

NFALookBehindNode::NFALookBehindNode(const std::string & str, const bool positive) : pos(positive), mStr(str) { }
int NFALookBehindNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (pos)
  {
    if (curInd < (int)mStr.size()) return -1;
    if (str.substr(curInd - mStr.size(), mStr.size()) == mStr) return next->match(str, matcher, curInd);
  }
  else
  {
    if (curInd < (int)mStr.size()) return next->match(str, matcher, curInd);
    if (str.substr(curInd - mStr.size(), mStr.size()) == mStr) return -1;
     return next->match(str, matcher, curInd);
  }
  return -1;
}

// NFAStartOfLineNode

NFAStartOfLineNode::NFAStartOfLineNode() { }
int NFAStartOfLineNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd == 0 || str[curInd - 1] == '\n' || str[curInd - 1] == '\r')
  {
    return next->match(str, matcher, curInd);
  }
  return -1;
}

// NFAEndOfLineNode

NFAEndOfLineNode::NFAEndOfLineNode() { }
int NFAEndOfLineNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd >= (int)str.size() || str[curInd] == '\n' || str[curInd] == '\r')
  {
    return next->match(str, matcher, curInd);
  }
  return -1;
}

// NFAReferenceNode

NFAReferenceNode::NFAReferenceNode(const int groupIndex) : gi(groupIndex) { }
int NFAReferenceNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int len = matcher->ends[gi] - matcher->starts[gi];
  int ni = -1;
  if      (gi < 1 || matcher->ends[gi] < matcher->starts[gi] || len == 0)   ni = curInd;
  else if (curInd + len > (int)str.size())                                  return -1;
  else if (str.substr(curInd, len) != str.substr(matcher->starts[gi], len)) return -1;
  else                                                                      ni = curInd + len;

  return next->match(str, matcher, ni);
}

// NFAStartOfInputNode

NFAStartOfInputNode::NFAStartOfInputNode() { }
int NFAStartOfInputNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd == 0) return next->match(str, matcher, curInd);
  return -1;
}

// NFAEndOfInputNode

NFAEndOfInputNode::NFAEndOfInputNode(const bool lookForTerm) : term(lookForTerm) { }
int NFAEndOfInputNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int len = (int)str.size();
  if      (curInd == len) return next->match(str, matcher, curInd);
  else if (term)
  {
    if      (curInd == len - 1 && (str[curInd] == '\r' || str[curInd] == '\n'))
    {
      return next->match(str, matcher, curInd);
    }
    else if (curInd == len - 2 && str.substr(curInd, 2) == "\r\n")
    {
      return next->match(str, matcher, curInd);
    }
  }
  return -1;
}

// NFAWordBoundaryNode

NFAWordBoundaryNode::NFAWordBoundaryNode(const bool positive) : pos(positive) { }
int NFAWordBoundaryNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  #define is_alpha(x) (((x) >= 'a' && (x) <= 'z') || ((x) >= 'A' && (x) <= 'Z'))

  int len = (int)str.size();
  bool ok = 0;
  char c1 = (curInd - 1 < len) ? str[curInd - 1] : -1;
  char c2 = (curInd     < len) ? str[curInd    ] : -1;

  if      (curInd == len) return next->match(str, matcher, curInd);
  if      (is_alpha(c1) ^ is_alpha(c2)) ok = 1;
  if (ok && pos) return next->match(str, matcher, curInd);
  return -1;

  #undef is_alpha
}

// NFAEndOfMatchNode

NFAEndOfMatchNode::NFAEndOfMatchNode() { }
int NFAEndOfMatchNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  if (curInd == matcher->lm) return next->match(str, matcher, curInd);
  return -1;
}

// NFAGroupHeadNode

NFAGroupHeadNode::NFAGroupHeadNode(const int groupIndex) : gi(groupIndex) { }
int NFAGroupHeadNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int ret, o = matcher->starts[gi];

  matcher->starts[gi] = curInd;
  ret = next->match(str, matcher, curInd);
  if (ret < 0) matcher->starts[gi] = o;

  return ret;
}

// NFAGroupTailNode

NFAGroupTailNode::NFAGroupTailNode(const int groupIndex) : gi(groupIndex) { }
int NFAGroupTailNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int ret, o = matcher->ends[gi];

  matcher->ends[gi] = curInd;
  ret = next->match(str, matcher, curInd);
  if (ret < 0) matcher->ends[gi] = o;

  return ret;
}

// NFAGroupLoopPrologueNode

NFAGroupLoopPrologueNode::NFAGroupLoopPrologueNode(const int groupIndex) : gi(groupIndex) { }
int NFAGroupLoopPrologueNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  int ret, o1 = matcher->groups[gi], o2 = matcher->groupPos[gi], o3 = matcher->groupIndeces[gi];

  matcher->groups[gi] = 0;
  matcher->groupPos[gi] = 0;
  matcher->groupIndeces[gi] = -1;
  ret = next->match(str, matcher, curInd);
  if (ret < 0)
  {
    matcher->groups[gi] = o1;
    matcher->groupPos[gi] = o2;
    matcher->groupIndeces[gi] = o3;
  }

  return ret;
}

// NFAGroupLoopNode

NFAGroupLoopNode::NFAGroupLoopNode(NFANode * internal, const int minMatch, const int maxMatch,
                                   const int groupIndex, const int matchType)
{
  inner = internal;
  min = minMatch;
  max = maxMatch;
  gi = groupIndex;
  type = matchType;
}
void NFAGroupLoopNode::findAllNodes(std::map<NFANode*, bool> & soFar)
{
  if (inner) inner->findAllNodes(soFar);
  NFANode::findAllNodes(soFar);
}
int NFAGroupLoopNode::match(const std::string & str, Matcher * matcher, const int curInd) const
{
  bool b = (curInd > matcher->groupIndeces[gi]);

  if (b && matcher->groups[gi] < min)
  {
    ++matcher->groups[gi];
    int o = matcher->groupIndeces[gi];
    matcher->groupIndeces[gi] = curInd;
    int ret = inner->match(str, matcher, curInd);
    if (ret < 0)
    {
      matcher->groupIndeces[gi] = o;
      --matcher->groups[gi];
    }
    return ret;
  }
  else if (!b || matcher->groups[gi] >= max)
  {
    return next->match(str, matcher, curInd);
  }
  else
  {
    switch (type)
    {
    case 0: return matchGreedy(str, matcher, curInd);
    case 1: return matchLazy(str, matcher, curInd);
    case 2: return matchPossessive(str, matcher, curInd);
    }
  }
  return -1;
}
int NFAGroupLoopNode::matchGreedy(const std::string & str, Matcher * matcher, const int curInd) const
{
  int o = matcher->groupIndeces[gi];            // save our info for backtracking
  matcher->groupIndeces[gi] = curInd;           // move along
  ++matcher->groups[gi];
  int ret = inner->match(str, matcher, curInd); // match internally
  if (ret < 0)
  {                                             // if we failed, then restore info and match next
    --matcher->groups[gi];
    matcher->groupIndeces[gi] = o;
    ret = next->match(str, matcher, curInd);
  }
  return ret;
}
int NFAGroupLoopNode::matchLazy(const std::string & str, Matcher * matcher, const int curInd) const
{
  int ret = next->match(str, matcher, curInd);  // be lazy, just go on
  if (ret < 0)
  {
    int o = matcher->groupIndeces[gi];          // save info for backtracking
    matcher->groupIndeces[gi] = curInd;         // advance our position
    ++matcher->groups[gi];
    ret = inner->match(str, matcher, curInd);   // match our internal stuff
    if (ret < 0)                                // if we failed, then restore the info
    {
      --matcher->groups[gi];
      matcher->groupIndeces[gi] = o;
    }
  }
  return ret;
}
int NFAGroupLoopNode::matchPossessive(const std::string & str, Matcher * matcher, const int curInd) const
{
  int o = matcher->groupIndeces[gi];            // save info for backtracking
  matcher->groupPos[gi] = matcher->groups[gi];  // set a flag stating we have matcher at least this much
  matcher->groupIndeces[gi] = curInd;           // move along
  ++matcher->groups[gi];
  int ret = inner->match(str, matcher, curInd); // try and match again
  if (ret < 0)
  {                                             // if we fail, back off, but to an extent
    --matcher->groups[gi];
    matcher->groupIndeces[gi] = o;
    if (matcher->groups[gi] == matcher->groupPos[gi]) ret = next->match(str, matcher, curInd);
  }
  return ret;
}

#ifdef _WIN32
  #pragma warning(pop)
#endif