regcomp.c

PHP v6.0 For Linux 运行环境：Win9X/ WinME/ WinNT/ Win2K/ WinXP

    do {
      r = get_min_match_length(NCONS(node).left, &tmin, env);
      if (r == 0) *min += tmin;
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_ALT:
    {
      Node *x, *y;
      y = node;
      do {
	x = NCONS(y).left;
	r = get_min_match_length(x, &tmin, env);
	if (r != 0) break;
	if (y == node) *min = tmin;
	else if (*min > tmin) *min = tmin;
      } while (r == 0 && IS_NOT_NULL(y = NCONS(y).right));
    }
    break;

  case N_STRING:
    {
      StrNode* sn = &(NSTRING(node));
      *min = sn->end - sn->s;
    }
    break;

  case N_CTYPE:
    switch (NCTYPE(node).type) {
    case CTYPE_WORD:     *min = 1; break;
    case CTYPE_NOT_WORD: *min = 1; break;
    default:
      break;
    }
    break;

  case N_CCLASS:
  case N_ANYCHAR:
    *min = 1;
    break;

  case N_QUALIFIER:
    {
      QualifierNode* qn = &(NQUALIFIER(node));

      if (qn->lower > 0) {
	r = get_min_match_length(qn->target, min, env);
	if (r == 0)
	  *min = distance_multiply(*min, qn->lower);
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      switch (en->type) {
      case EFFECT_MEMORY:
#ifdef USE_SUBEXP_CALL
	if (IS_EFFECT_MIN_FIXED(en))
	  *min = en->min_len;
	else {
	  r = get_min_match_length(en->target, min, env);
	  if (r == 0) {
	    en->min_len = *min;
	    SET_EFFECT_STATUS(node, NST_MIN_FIXED);
	  }
	}
	break;
#endif
      case EFFECT_OPTION:
      case EFFECT_STOP_BACKTRACK:
	r = get_min_match_length(en->target, min, env);
	break;
      }
    }
    break;

  case N_ANCHOR:
  default:
    break;
  }

  return r;
}

static int
get_max_match_length(Node* node, OnigDistance *max, ScanEnv* env)
{
  OnigDistance tmax;
  int r = 0;

  *max = 0;
  switch (NTYPE(node)) {
  case N_LIST:
    do {
      r = get_max_match_length(NCONS(node).left, &tmax, env);
      if (r == 0)
	*max = distance_add(*max, tmax);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_ALT:
    do {
      r = get_max_match_length(NCONS(node).left, &tmax, env);
      if (r == 0 && *max < tmax) *max = tmax;
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_STRING:
    {
      StrNode* sn = &(NSTRING(node));
      *max = sn->end - sn->s;
    }
    break;

  case N_CTYPE:
    switch (NCTYPE(node).type) {
    case CTYPE_WORD:
    case CTYPE_NOT_WORD:
      *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
      break;

    default:
      break;
    }
    break;

  case N_CCLASS:
  case N_ANYCHAR:
    *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
    break;

  case N_BACKREF:
    {
      int i;
      int* backs;
      Node** nodes = SCANENV_MEM_NODES(env);
      BackrefNode* br = &(NBACKREF(node));
      if (br->state & NST_RECURSION) {
	*max = ONIG_INFINITE_DISTANCE;
	break;
      }
      backs = BACKREFS_P(br);
      for (i = 0; i < br->back_num; i++) {
	if (backs[i] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
	r = get_max_match_length(nodes[backs[i]], &tmax, env);
	if (r != 0) break;
	if (*max < tmax) *max = tmax;
      }
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    if (! IS_CALL_RECURSION(&(NCALL(node))))
      r = get_max_match_length(NCALL(node).target, max, env);
    else
      *max = ONIG_INFINITE_DISTANCE;
    break;
#endif

  case N_QUALIFIER:
    {
      QualifierNode* qn = &(NQUALIFIER(node));

      if (qn->upper != 0) {
	r = get_max_match_length(qn->target, max, env);
	if (r == 0 && *max != 0) {
	  if (! IS_REPEAT_INFINITE(qn->upper))
	    *max = distance_multiply(*max, qn->upper);
	  else
	    *max = ONIG_INFINITE_DISTANCE;
	}
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      switch (en->type) {
      case EFFECT_MEMORY:
#ifdef USE_SUBEXP_CALL
	if (IS_EFFECT_MAX_FIXED(en))
	  *max = en->max_len;
	else {
	  r = get_max_match_length(en->target, max, env);
	  if (r == 0) {
	    en->max_len = *max;
	    SET_EFFECT_STATUS(node, NST_MAX_FIXED);
	  }
	}
	break;
#endif
      case EFFECT_OPTION:
      case EFFECT_STOP_BACKTRACK:
	r = get_max_match_length(en->target, max, env);
	break;
      }
    }
    break;

  case N_ANCHOR:
  default:
    break;
  }

  return r;
}

#define GET_CHAR_LEN_VARLEN           -1
#define GET_CHAR_LEN_TOP_ALT_VARLEN   -2

/* fixed size pattern node only */
static int
get_char_length_tree1(Node* node, regex_t* reg, int* len, int level)
{
  int tlen;
  int r = 0;

  level++;
  *len = 0;
  switch (NTYPE(node)) {
  case N_LIST:
    do {
      r = get_char_length_tree1(NCONS(node).left, reg, &tlen, level);
      if (r == 0)
	*len = distance_add(*len, tlen);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_ALT:
    {
      int tlen2;
      int varlen = 0;

      r = get_char_length_tree1(NCONS(node).left, reg, &tlen, level);
      while (r == 0 && IS_NOT_NULL(node = NCONS(node).right)) {
	r = get_char_length_tree1(NCONS(node).left, reg, &tlen2, level);
	if (r == 0) {
	  if (tlen != tlen2)
	    varlen = 1;
	}
      }
      if (r == 0) {
	if (varlen != 0) {
	  if (level == 1)
	    r = GET_CHAR_LEN_TOP_ALT_VARLEN;
	  else
	    r = GET_CHAR_LEN_VARLEN;
	}
	else
	  *len = tlen;
      }
    }
    break;

  case N_STRING:
    {
      StrNode* sn = &(NSTRING(node));
      UChar *s = sn->s;
      while (s < sn->end) {
	s += enc_len(reg->enc, s);
	(*len)++;
      }
    }
    break;

  case N_QUALIFIER:
    {
      QualifierNode* qn = &(NQUALIFIER(node));
      if (qn->lower == qn->upper) {
	r = get_char_length_tree1(qn->target, reg, &tlen, level);
	if (r == 0)
	  *len = distance_multiply(tlen, qn->lower);
      }
      else
	r = GET_CHAR_LEN_VARLEN;
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    if (! IS_CALL_RECURSION(&(NCALL(node))))
      r = get_char_length_tree1(NCALL(node).target, reg, len, level);
    else
      r = GET_CHAR_LEN_VARLEN;
    break;
#endif

  case N_CTYPE:
    switch (NCTYPE(node).type) {
    case CTYPE_WORD:
    case CTYPE_NOT_WORD:
      *len = 1;
      break;
    }
    break;

  case N_CCLASS:
  case N_ANYCHAR:
    *len = 1;
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      switch (en->type) {
      case EFFECT_MEMORY:
#ifdef USE_SUBEXP_CALL
	if (IS_EFFECT_CLEN_FIXED(en))
	  *len = en->char_len;
	else {
	  r = get_char_length_tree1(en->target, reg, len, level);
	  if (r == 0) {
	    en->char_len = *len;
	    SET_EFFECT_STATUS(node, NST_CLEN_FIXED);
	  }
	}
	break;
#endif
      case EFFECT_OPTION:
      case EFFECT_STOP_BACKTRACK:
	r = get_char_length_tree1(en->target, reg, len, level);
	break;
      default:
	break;
      }
    }
    break;

  case N_ANCHOR:
    break;

  default:
    r = GET_CHAR_LEN_VARLEN;
    break;
  }

  return r;
}

static int
get_char_length_tree(Node* node, regex_t* reg, int* len)
{
  return get_char_length_tree1(node, reg, len, 0);
}

extern int
onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code, CClassNode* cc)
{
  int found;

  if (ONIGENC_MBC_MINLEN(enc) > 1 || (code >= SINGLE_BYTE_SIZE)) {
    if (IS_NULL(cc->mbuf)) {
      found = 0;
    }
    else {
      found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
    }
  }
  else {
    found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
  }

  if (IS_CCLASS_NOT(cc))
    return !found;
  else
    return found;
}

/* x is not included y ==>  1 : 0 */
static int
is_not_included(Node* x, Node* y, regex_t* reg)
{
  int i, len;
  OnigCodePoint code;
  UChar *p, c;
  int ytype;

 retry:
  ytype = NTYPE(y);
  switch (NTYPE(x)) {
  case N_CTYPE:
    {
      switch (ytype) {
      case N_CTYPE:
	switch (NCTYPE(x).type) {
	case CTYPE_WORD:
	  if (NCTYPE(y).type == CTYPE_NOT_WORD)
	    return 1;
	  else
	    return 0;
	  break;
	case CTYPE_NOT_WORD:
	  if (NCTYPE(y).type == CTYPE_WORD)
	    return 1;
	  else
	    return 0;
	  break;
	default:
	  break;
	}
	break;

      case N_CCLASS:
      swap:
	{
	  Node* tmp;
	  tmp = x; x = y; y = tmp;
	  goto retry;
	}
	break;

      case N_STRING:
	goto swap;
	break;

      default:
	break;
      }
    }
    break;

  case N_CCLASS:
    {
      CClassNode* xc = &(NCCLASS(x));
      switch (ytype) {
      case N_CTYPE:
	switch (NCTYPE(y).type) {
	case CTYPE_WORD:
	  if (IS_NULL(xc->mbuf) && !IS_CCLASS_NOT(xc)) {
	    for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
	      if (BITSET_AT(xc->bs, i)) {
		if (ONIGENC_IS_CODE_SB_WORD(reg->enc, i)) return 0;
	      }
	    }
	    return 1;
	  }
	  return 0;
	  break;
	case CTYPE_NOT_WORD:
	  for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
	    if (! ONIGENC_IS_CODE_SB_WORD(reg->enc, i)) {
	      if (!IS_CCLASS_NOT(xc)) {
		if (BITSET_AT(xc->bs, i))
		  return 0;
	      }
	      else {
		if (! BITSET_AT(xc->bs, i))
		  return 0;
	      }
	    }
	  }
	  return 1;
	  break;

	default:
	  break;
	}
	break;

      case N_CCLASS:
	{
	  int v;
	  CClassNode* yc = &(NCCLASS(y));

	  for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
	    v = BITSET_AT(xc->bs, i);
	    if ((v != 0 && !IS_CCLASS_NOT(xc)) ||
                (v == 0 && IS_CCLASS_NOT(xc))) {
	      v = BITSET_AT(yc->bs, i);
	      if ((v != 0 && !IS_CCLASS_NOT(yc)) ||
                  (v == 0 && IS_CCLASS_NOT(yc)))
		return 0;
	    }
	  }
	  if ((IS_NULL(xc->mbuf) && !IS_CCLASS_NOT(xc)) ||
	      (IS_NULL(yc->mbuf) && !IS_CCLASS_NOT(yc)))
	    return 1;
	  return 0;
	}
	break;

      case N_STRING:
	goto swap;
	break;

      default:
	break;
      }
    }
    break;

  case N_STRING:
    {
      StrNode* xs = &(NSTRING(x));
      if (NSTRING_LEN(x) == 0)
	break;

      c = *(xs->s);
      switch (ytype) {
      case N_CTYPE:
	switch (NCTYPE(y).type) {
	case CTYPE_WORD:
	  return (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end) ? 0 : 1);
	  break;
	case CTYPE_NOT_WORD:
	  return (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end) ? 1 : 0);
	  break;
	default:
	  break;
	}
	break;

      case N_CCLASS:
	{
	  CClassNode* cc = &(NCCLASS(y));

	  code = ONIGENC_MBC_TO_CODE(reg->enc, xs->s,
				     xs->s + ONIGENC_MBC_MAXLEN(reg->enc));
	  return (onig_is_code_in_cc(reg->enc, code, cc) != 0 ? 0 : 1);
	}
	break;

      case N_STRING:
	{
	  UChar *q;
	  StrNode* ys = &(NSTRING(y));
	  len = NSTRING_LEN(x);
	  if (len > NSTRING_LEN(y)) len = NSTRING_LEN(y);
	  if (NSTRING_IS_AMBIG(x) || NSTRING_IS_AMBIG(y)) {
            /* tiny version */
            return 0;
	  }
	  else {
	    for (i = 0, p = ys->s, q = xs->s; i < len; i++, p++, q++) {
	      if (*p != *q) return 1;
	    }
	  }
	}
	break;
	
      default:
	break;
      }
    }
    break;

  default:
    break;
  }

  return 0;
}

static Node*
get_head_value_node(Node* node, int exact, regex_t* reg)
{
  Node* n = NULL_NODE;

  switch (NTYPE(node)) {
  case N_BACKREF:
  case N_ALT:
  case N_ANYCHAR:
#ifdef USE_SUBEXP_CALL
  case N_CALL:
#endif
    break;

  case N_CTYPE:
  case N_CCLASS:
    if (exact == 0) {
      n = node;
    }
    break;

  case N_LIST:
    n = get_head_value_node(NCONS(node).left, exact, reg);
    break;

  case N_STRING:
    {
      StrNode* sn = &(NSTRING(node));

      if (sn->end <= sn->s)
	break;

      if (exact != 0 &&
	  !NSTRING_IS_RAW(node) && IS_IGNORECASE(reg->options)) {