regcomp.c

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

#if 0
        UChar* tmp = sn->s;
	if (! ONIGENC_IS_MBC_AMBIGUOUS(reg->enc, reg->ambig_flag,
                                       &tmp, sn->end))
	  n = node;
#endif
      }
      else {
	n = node;
      }
    }
    break;

  case N_QUALIFIER:
    {
      QualifierNode* qn = &(NQUALIFIER(node));
      if (qn->lower > 0) {
	if (IS_NOT_NULL(qn->head_exact))
	  n = qn->head_exact;
	else
	  n = get_head_value_node(qn->target, exact, reg);
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      switch (en->type) {
      case EFFECT_OPTION:
	{
	  OnigOptionType options = reg->options;

	  reg->options = NEFFECT(node).option;
	  n = get_head_value_node(NEFFECT(node).target, exact, reg);
	  reg->options = options;
	}
	break;

      case EFFECT_MEMORY:
      case EFFECT_STOP_BACKTRACK:
	n = get_head_value_node(en->target, exact, reg);
	break;
      }
    }
    break;

  case N_ANCHOR:
    if (NANCHOR(node).type == ANCHOR_PREC_READ)
      n = get_head_value_node(NANCHOR(node).target, exact, reg);
    break;

  default:
    break;
  }

  return n;
}

static int
check_type_tree(Node* node, int type_mask, int effect_mask, int anchor_mask)
{
  int type, r = 0;

  type = NTYPE(node);
  if ((type & type_mask) == 0)
    return 1;

  switch (type) {
  case N_LIST:
  case N_ALT:
    do {
      r = check_type_tree(NCONS(node).left, type_mask, effect_mask, anchor_mask);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_QUALIFIER:
    r = check_type_tree(NQUALIFIER(node).target, type_mask, effect_mask,
			anchor_mask);
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      if ((en->type & effect_mask) == 0)
	return 1;

      r = check_type_tree(en->target, type_mask, effect_mask, anchor_mask);
    }
    break;

  case N_ANCHOR:
    type = NANCHOR(node).type;
    if ((type & anchor_mask) == 0)
      return 1;

    if (NANCHOR(node).target)
      r = check_type_tree(NANCHOR(node).target,
			  type_mask, effect_mask, anchor_mask);
    break;

  default:
    break;
  }
  return r;
}

#ifdef USE_SUBEXP_CALL

#define RECURSION_EXIST       1
#define RECURSION_INFINITE    2

static int
subexp_inf_recursive_check(Node* node, ScanEnv* env, int head)
{
  int type;
  int r = 0;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
    {
      Node *x;
      OnigDistance min;
      int ret;

      x = node;
      do {
	ret = subexp_inf_recursive_check(NCONS(x).left, env, head);
	if (ret < 0 || ret == RECURSION_INFINITE) return ret;
	r |= ret;
	if (head) {
	  ret = get_min_match_length(NCONS(x).left, &min, env);
	  if (ret != 0) return ret;
	  if (min != 0) head = 0;
	}
      } while (IS_NOT_NULL(x = NCONS(x).right));
    }
    break;

  case N_ALT:
    {
      int ret;
      r = RECURSION_EXIST;
      do {
	ret = subexp_inf_recursive_check(NCONS(node).left, env, head);
	if (ret < 0 || ret == RECURSION_INFINITE) return ret;
	r &= ret;
      } while (IS_NOT_NULL(node = NCONS(node).right));
    }
    break;

  case N_QUALIFIER:
    r = subexp_inf_recursive_check(NQUALIFIER(node).target, env, head);
    break;

  case N_ANCHOR:
    {
      AnchorNode* an = &(NANCHOR(node));
      switch (an->type) {
      case ANCHOR_PREC_READ:
      case ANCHOR_PREC_READ_NOT:
      case ANCHOR_LOOK_BEHIND:
      case ANCHOR_LOOK_BEHIND_NOT:
	r = subexp_inf_recursive_check(an->target, env, head);
	break;
      }
    }
    break;

  case N_CALL:
    r = subexp_inf_recursive_check(NCALL(node).target, env, head);
    break;

  case N_EFFECT:
    if (IS_EFFECT_MARK2(&(NEFFECT(node))))
      return 0;
    else if (IS_EFFECT_MARK1(&(NEFFECT(node))))
      return (head == 0 ? RECURSION_EXIST : RECURSION_INFINITE);
    else {
      SET_EFFECT_STATUS(node, NST_MARK2);
      r = subexp_inf_recursive_check(NEFFECT(node).target, env, head);
      CLEAR_EFFECT_STATUS(node, NST_MARK2);
    }
    break;

  default:
    break;
  }

  return r;
}

static int
subexp_inf_recursive_check_trav(Node* node, ScanEnv* env)
{
  int type;
  int r = 0;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
  case N_ALT:
    do {
      r = subexp_inf_recursive_check_trav(NCONS(node).left, env);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_QUALIFIER:
    r = subexp_inf_recursive_check_trav(NQUALIFIER(node).target, env);
    break;

  case N_ANCHOR:
    {
      AnchorNode* an = &(NANCHOR(node));
      switch (an->type) {
      case ANCHOR_PREC_READ:
      case ANCHOR_PREC_READ_NOT:
      case ANCHOR_LOOK_BEHIND:
      case ANCHOR_LOOK_BEHIND_NOT:
	r = subexp_inf_recursive_check_trav(an->target, env);
	break;
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));

      if (IS_EFFECT_RECURSION(en)) {
	SET_EFFECT_STATUS(node, NST_MARK1);
	r = subexp_inf_recursive_check(en->target, env, 1);
	if (r > 0) return ONIGERR_NEVER_ENDING_RECURSION;
	CLEAR_EFFECT_STATUS(node, NST_MARK1);
      }
      r = subexp_inf_recursive_check_trav(en->target, env);
    }

    break;

  default:
    break;
  }

  return r;
}

static int
subexp_recursive_check(Node* node)
{
  int type;
  int r = 0;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
  case N_ALT:
    do {
      r |= subexp_recursive_check(NCONS(node).left);
    } while (IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_QUALIFIER:
    r = subexp_recursive_check(NQUALIFIER(node).target);
    break;

  case N_ANCHOR:
    {
      AnchorNode* an = &(NANCHOR(node));
      switch (an->type) {
      case ANCHOR_PREC_READ:
      case ANCHOR_PREC_READ_NOT:
      case ANCHOR_LOOK_BEHIND:
      case ANCHOR_LOOK_BEHIND_NOT:
	r = subexp_recursive_check(an->target);
	break;
      }
    }
    break;

  case N_CALL:
    r = subexp_recursive_check(NCALL(node).target);
    if (r != 0) SET_CALL_RECURSION(node);
    break;

  case N_EFFECT:
    if (IS_EFFECT_MARK2(&(NEFFECT(node))))
      return 0;
    else if (IS_EFFECT_MARK1(&(NEFFECT(node))))
      return 1; /* recursion */
    else {
      SET_EFFECT_STATUS(node, NST_MARK2);
      r = subexp_recursive_check(NEFFECT(node).target);
      CLEAR_EFFECT_STATUS(node, NST_MARK2);
    }
    break;

  default:
    break;
  }

  return r;
}


static int
subexp_recursive_check_trav(Node* node, ScanEnv* env)
{
#define FOUND_CALLED_NODE    1

  int type;
  int r = 0;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
  case N_ALT:
    {
      int ret;
      do {
	ret = subexp_recursive_check_trav(NCONS(node).left, env);
	if (ret == FOUND_CALLED_NODE) r = FOUND_CALLED_NODE;
	else if (ret < 0) return ret;
      } while (IS_NOT_NULL(node = NCONS(node).right));
    }
    break;

  case N_QUALIFIER:
    r = subexp_recursive_check_trav(NQUALIFIER(node).target, env);
    if (NQUALIFIER(node).upper == 0) {
      if (r == FOUND_CALLED_NODE)
	NQUALIFIER(node).is_refered = 1;
    }
    break;

  case N_ANCHOR:
    {
      AnchorNode* an = &(NANCHOR(node));
      switch (an->type) {
      case ANCHOR_PREC_READ:
      case ANCHOR_PREC_READ_NOT:
      case ANCHOR_LOOK_BEHIND:
      case ANCHOR_LOOK_BEHIND_NOT:
	r = subexp_recursive_check_trav(an->target, env);
	break;
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));

      if (! IS_EFFECT_RECURSION(en)) {
	if (IS_EFFECT_CALLED(en)) {
	  SET_EFFECT_STATUS(node, NST_MARK1);
	  r = subexp_recursive_check(en->target);
	  if (r != 0) SET_EFFECT_STATUS(node, NST_RECURSION);
	  CLEAR_EFFECT_STATUS(node, NST_MARK1);
	}
      }
      r = subexp_recursive_check_trav(en->target, env);
      if (IS_EFFECT_CALLED(en))
	r |= FOUND_CALLED_NODE;
    }
    break;

  default:
    break;
  }

  return r;
}

static int
setup_subexp_call(Node* node, ScanEnv* env)
{
  int type;
  int r = 0;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
    do {
      r = setup_subexp_call(NCONS(node).left, env);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_ALT:
    do {
      r = setup_subexp_call(NCONS(node).left, env);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;

  case N_QUALIFIER:
    r = setup_subexp_call(NQUALIFIER(node).target, env);
    break;
  case N_EFFECT:
    r = setup_subexp_call(NEFFECT(node).target, env);
    break;

  case N_CALL:
    {
      int n, num, *refs;
      UChar *p;
      CallNode* cn = &(NCALL(node));
      Node** nodes = SCANENV_MEM_NODES(env);

#ifdef USE_NAMED_GROUP
      n = onig_name_to_group_numbers(env->reg, cn->name, cn->name_end, &refs);
#else
      n = -1;
#endif
      if (n <= 0) {
	/* name not found, check group number. (?*ddd) */
	p = cn->name;
	num = onig_scan_unsigned_number(&p, cn->name_end, env->enc);
	if (num <= 0 || p != cn->name_end) {
	  onig_scan_env_set_error_string(env,
		  ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
	  return ONIGERR_UNDEFINED_NAME_REFERENCE;
	}
#ifdef USE_NAMED_GROUP
	if (env->num_named > 0 &&
	    IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
	    !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
	  return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
	}
#endif
	if (num > env->num_mem) {
	  onig_scan_env_set_error_string(env,
		 ONIGERR_UNDEFINED_GROUP_REFERENCE, cn->name, cn->name_end);
	  return ONIGERR_UNDEFINED_GROUP_REFERENCE;
	}
	cn->ref_num = num;
	goto set_call_attr;
      }
      else if (n > 1) {
	onig_scan_env_set_error_string(env,
	       ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL, cn->name, cn->name_end);
	return ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL;
      }
      else {
	cn->ref_num = refs[0];
      set_call_attr:
	cn->target = nodes[cn->ref_num];
	if (IS_NULL(cn->target)) {
	  onig_scan_env_set_error_string(env,
		  ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
	  return ONIGERR_UNDEFINED_NAME_REFERENCE;
	}
	SET_EFFECT_STATUS(cn->target, NST_CALLED);
	BIT_STATUS_ON_AT(env->bt_mem_start, cn->ref_num);
	cn->unset_addr_list = env->unset_addr_list;
      }
    }
    break;

  case N_ANCHOR:
    {
      AnchorNode* an = &(NANCHOR(node));

      switch (an->type) {
      case ANCHOR_PREC_READ:
      case ANCHOR_PREC_READ_NOT:
      case ANCHOR_LOOK_BEHIND:
      case ANCHOR_LOOK_BEHIND_NOT:
	r = setup_subexp_call(an->target, env);
	break;
      }
    }
    break;

  default:
    break;
  }

  return r;
}
#endif

/* divide different length alternatives in look-behind.
  (?<=A|B) ==> (?<=A)|(?<=B)
  (?<!A|B) ==> (?<!A)(?<!B)
*/
static int
divide_look_behind_alternatives(Node* node)
{
  Node tmp_node;
  Node *head, *np, *insert_node;
  AnchorNode* an = &(NANCHOR(node));
  int anc_type = an->type;

  head = an->target;
  np = NCONS(head).left;
  tmp_node = *node; *node = *head; *head = tmp_node;
  NCONS(node).left = head;
  NANCHOR(head).target = np;

  np = node;
  while ((np = NCONS(np).right) != NULL_NODE) {
    insert_node = onig_node_new_anchor(anc_type);
    CHECK_NULL_RETURN_VAL(insert_node, ONIGERR_MEMORY);
    NANCHOR(insert_node).target = NCONS(np).left;
    NCONS(np).left = insert_node;
  }

  if (anc_type == ANCHOR_LOOK_BEHIND_NOT) {
    np = node;
    do {
      np->type = N_LIST;  /* alt -> list */
    } while ((np = NCONS(np).right) != NULL_NODE);
  }
  return 0;
}

static int
setup_look_behind(Node* node, regex_t* reg, ScanEnv* env)
{
  int r, len;
  AnchorNode* an = &(NANCHOR(node));

  r = get_char_length_tree(an->target, reg, &len);
  if (r == 0)
    an->char_len = len;
  else if (r == GET_CHAR_LEN_VARLEN)
    r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
  else if (r == GET_CHAR_LEN_TOP_ALT_VARLEN) {
    if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND))
      r = divide_look_behind_alternatives(node);
    else
      r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
  }

  return r;
}

static int
next_setup(Node* node, Node* next_node, regex_t* reg)
{
  int type;

 retry:
  type = NTYPE(node);
  if (type == N_QUALIFIER) {
    QualifierNode* qn = &(NQUALIFIER(node));
    if (qn->greedy && IS_REPEAT_INFINITE(qn->upper)) {
#ifdef USE_QUALIFIER_PEEK_NEXT
      qn->next_head_exact = get_head_value_node(next_node, 1, reg);
#endif
      /* automatic posseivation a*b ==> (?>a*)b */
      if (qn->lower <= 1) {
	int ttype = NTYPE(qn->target);
	if (IS_NODE_TYPE_SIMPLE(ttype)) {
	  Node *x, *y;
	  x = get_head_value_node(qn->target, 0, reg);
	  if (IS_NOT_NULL(x)) {
	    y = get_head_value_node(next_node,  0, reg);
	    if (IS_NOT_NULL(y) && is_not_included(x, y, reg)) {
	      Node* en = onig_node_new_effect(EFFECT_STOP_BACKTRACK);
	      CHECK_NULL_RETURN_VAL(en, ONIGERR_MEMORY);
	      SET_EFFECT_STATUS(en, NST_STOP_BT_SIMPLE_REPEAT);
	      swap_node(node, en);
	      NEFFECT(node).target = en;
	    }
	  }
	}
      }
    }
  }
  else if (type == N_EFFECT) {
    EffectNode* en = &(NEFFECT(node));
    if (en->type == EFFECT_MEMORY) {
      node = en->target;
      goto retry;
    }
  }
  return 0;
}

static int
divide_ambig_string_node(Node* node, regex_t* reg)
{
  StrNode* sn = &NSTRING(node);
  int ambig, prev_ambig;
  UChar *prev, *p, *end, *prev_start, *start, *tmp, *wp;
  No