regcomp.c

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

      }
      else
	n = node->char_len;
      r = add_length(reg, n);
      if (r) return r;
      r = compile_tree(node->target, reg);
    }
    break;

  case ANCHOR_LOOK_BEHIND_NOT:
    {
      int n;
      len = compile_length_tree(node->target, reg);
      r = add_opcode_rel_addr(reg, OP_PUSH_LOOK_BEHIND_NOT,
			   len + SIZE_OP_FAIL_LOOK_BEHIND_NOT);
      if (r) return r;
      if (node->char_len < 0) {
	r = get_char_length_tree(node->target, reg, &n);
	if (r) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
      }
      else
	n = node->char_len;
      r = add_length(reg, n);
      if (r) return r;
      r = compile_tree(node->target, reg);
      if (r) return r;
      r = add_opcode(reg, OP_FAIL_LOOK_BEHIND_NOT);
    }
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return r;
}

static int
compile_length_tree(Node* node, regex_t* reg)
{
  int len, type, r;

  type = NTYPE(node);
  switch (type) {
  case N_LIST:
    len = 0;
    do {
      r = compile_length_tree(NCONS(node).left, reg);
      if (r < 0) return r;
      len += r;
    } while (IS_NOT_NULL(node = NCONS(node).right));
    r = len;
    break;

  case N_ALT:
    {
      int n;

      n = r = 0;
      do {
	r += compile_length_tree(NCONS(node).left, reg);
	n++;
      } while (IS_NOT_NULL(node = NCONS(node).right));
      r += (SIZE_OP_PUSH + SIZE_OP_JUMP) * (n - 1);
    }
    break;

  case N_STRING:
    if (NSTRING_IS_RAW(node))
      r = compile_length_string_raw_node(&(NSTRING(node)), reg);
    else
      r = compile_length_string_node(node, reg);
    break;

  case N_CCLASS:
    r = compile_length_cclass_node(&(NCCLASS(node)), reg);
    break;

  case N_CTYPE:
  case N_ANYCHAR:
    r = SIZE_OPCODE;
    break;

  case N_BACKREF:
    {
      BackrefNode* br = &(NBACKREF(node));

      if (br->back_num == 1) {
	r = ((!IS_IGNORECASE(reg->options) && br->back_static[0] <= 3)
	     ? SIZE_OPCODE : (SIZE_OPCODE + SIZE_MEMNUM));
      }
      else {
	r = SIZE_OPCODE + SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
      }
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    r = SIZE_OP_CALL;
    break;
#endif

  case N_QUALIFIER:
    r = compile_length_qualifier_node(&(NQUALIFIER(node)), reg);
    break;

  case N_EFFECT:
    r = compile_length_effect_node(&NEFFECT(node), reg);
    break;

  case N_ANCHOR:
    r = compile_length_anchor_node(&(NANCHOR(node)), reg);
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return r;
}

static int
compile_tree(Node* node, regex_t* reg)
{
  int n, type, len, pos, r = 0;

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

  case N_ALT:
    {
      Node* x = node;
      len = 0;
      do {
	len += compile_length_tree(NCONS(x).left, reg);
	if (NCONS(x).right != NULL) {
	  len += SIZE_OP_PUSH + SIZE_OP_JUMP;
	}
      } while (IS_NOT_NULL(x = NCONS(x).right));
      pos = reg->used + len;  /* goal position */

      do {
	len = compile_length_tree(NCONS(node).left, reg);
	if (IS_NOT_NULL(NCONS(node).right)) {
	  r = add_opcode_rel_addr(reg, OP_PUSH, len + SIZE_OP_JUMP);
	  if (r) break;
	}
	r = compile_tree(NCONS(node).left, reg);
	if (r) break;
	if (IS_NOT_NULL(NCONS(node).right)) {
	  len = pos - (reg->used + SIZE_OP_JUMP);
	  r = add_opcode_rel_addr(reg, OP_JUMP, len);
	  if (r) break;
	}
      } while (IS_NOT_NULL(node = NCONS(node).right));
    }
    break;

  case N_STRING:
    if (NSTRING_IS_RAW(node))
      r = compile_string_raw_node(&(NSTRING(node)), reg);
    else
      r = compile_string_node(node, reg);
    break;

  case N_CCLASS:
    r = compile_cclass_node(&(NCCLASS(node)), reg);
    break;

  case N_CTYPE:
    {
      int op;

      switch (NCTYPE(node).type) {
      case CTYPE_WORD:            op = OP_WORD;           break;
      case CTYPE_NOT_WORD:        op = OP_NOT_WORD;       break;
      default:
	return ONIGERR_TYPE_BUG;
	break;
      }
      r = add_opcode(reg, op);
    }
    break;

  case N_ANYCHAR:
    if (IS_MULTILINE(reg->options))
      r = add_opcode(reg, OP_ANYCHAR_ML);
    else
      r = add_opcode(reg, OP_ANYCHAR);
    break;

  case N_BACKREF:
    {
      int i;
      BackrefNode* br = &(NBACKREF(node));

      if (br->back_num == 1) {
	n = br->back_static[0];
	if (IS_IGNORECASE(reg->options)) {
	  r = add_opcode(reg, OP_BACKREFN_IC);
	  if (r) return r;
	  r = add_mem_num(reg, n);
	}
	else {
	  switch (n) {
	  case 1:  r = add_opcode(reg, OP_BACKREF1); break;
	  case 2:  r = add_opcode(reg, OP_BACKREF2); break;
	  case 3:  r = add_opcode(reg, OP_BACKREF3); break;
	  default:
	    r = add_opcode(reg, OP_BACKREFN);
	    if (r) return r;
	    r = add_mem_num(reg, n);
	    break;
	  }
	}
      }
      else {
	int* p;

        if (IS_IGNORECASE(reg->options)) {
          add_opcode(reg, OP_BACKREF_MULTI_IC);
        }
        else {
          add_opcode(reg, OP_BACKREF_MULTI);
        }

	if (r) return r;
	add_length(reg, br->back_num);
	if (r) return r;
	p = BACKREFS_P(br);
	for (i = br->back_num - 1; i >= 0; i--) {
	  r = add_mem_num(reg, p[i]);
	  if (r) return r;
	}
      }
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    r = compile_call(&(NCALL(node)), reg);
    break;
#endif

  case N_QUALIFIER:
    r = compile_qualifier_node(&(NQUALIFIER(node)), reg);
    break;

  case N_EFFECT:
    r = compile_effect_node(&NEFFECT(node), reg);
    break;

  case N_ANCHOR:
    r = compile_anchor_node(&(NANCHOR(node)), reg);
    break;

  default:
#ifdef ONIG_DEBUG
    fprintf(stderr, "compile_tree: undefined node type %d\n", NTYPE(node));
#endif
    break;
  }

  return r;
}

#ifdef USE_NAMED_GROUP

static int
noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
{
  int r = 0;
  Node* node = *plink;

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

  case N_QUALIFIER:
    {
      Node** ptarget = &(NQUALIFIER(node).target);
      Node*  old = *ptarget;
      r = noname_disable_map(ptarget, map, counter);
      if (*ptarget != old && NTYPE(*ptarget) == N_QUALIFIER) {
	onig_reduce_nested_qualifier(node, *ptarget);
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      if (en->type == EFFECT_MEMORY) {
	if (IS_EFFECT_NAMED_GROUP(en)) {
	  (*counter)++;
	  map[en->regnum].new_val = *counter;
	  en->regnum = *counter;
	  r = noname_disable_map(&(en->target), map, counter);
	}
	else {
	  *plink = en->target;
	  en->target = NULL_NODE;
	  onig_node_free(node);
	  r = noname_disable_map(plink, map, counter);
	}
      }
      else
	r = noname_disable_map(&(en->target), map, counter);
    }
    break;

  default:
    break;
  }

  return r;
}

static int
renumber_node_backref(Node* node, GroupNumRemap* map)
{
  int i, pos, n, old_num;
  int *backs;
  BackrefNode* bn = &(NBACKREF(node));

  if (! IS_BACKREF_NAME_REF(bn))
    return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;

  old_num = bn->back_num;
  if (IS_NULL(bn->back_dynamic))
    backs = bn->back_static;
  else
    backs = bn->back_dynamic;

  for (i = 0, pos = 0; i < old_num; i++) {
    n = map[backs[i]].new_val;
    if (n > 0) {
      backs[pos] = n;
      pos++;
    }
  }

  bn->back_num = pos;
  return 0;
}

static int
renumber_by_map(Node* node, GroupNumRemap* map)
{
  int r = 0;

  switch (NTYPE(node)) {
  case N_LIST:
  case N_ALT:
    do {
      r = renumber_by_map(NCONS(node).left, map);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;
  case N_QUALIFIER:
    r = renumber_by_map(NQUALIFIER(node).target, map);
    break;
  case N_EFFECT:
    r = renumber_by_map(NEFFECT(node).target, map);
    break;

  case N_BACKREF:
    r = renumber_node_backref(node, map);
    break;

  default:
    break;
  }

  return r;
}

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

  switch (NTYPE(node)) {
  case N_LIST:
  case N_ALT:
    do {
      r = numbered_ref_check(NCONS(node).left);
    } while (r == 0 && IS_NOT_NULL(node = NCONS(node).right));
    break;
  case N_QUALIFIER:
    r = numbered_ref_check(NQUALIFIER(node).target);
    break;
  case N_EFFECT:
    r = numbered_ref_check(NEFFECT(node).target);
    break;

  case N_BACKREF:
    if (! IS_BACKREF_NAME_REF(&(NBACKREF(node))))
      return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
    break;

  default:
    break;
  }

  return r;
}

static int
disable_noname_group_capture(Node** root, regex_t* reg, ScanEnv* env)
{
  int r, i, pos, counter;
  BitStatusType loc;
  GroupNumRemap* map;

  map = (GroupNumRemap* )xalloca(sizeof(GroupNumRemap) * (env->num_mem + 1));
  CHECK_NULL_RETURN_VAL(map, ONIGERR_MEMORY);
  for (i = 1; i <= env->num_mem; i++) {
    map[i].new_val = 0;
  }
  counter = 0;
  r = noname_disable_map(root, map, &counter);
  if (r != 0) return r;

  r = renumber_by_map(*root, map);
  if (r != 0) return r;

  for (i = 1, pos = 1; i <= env->num_mem; i++) {
    if (map[i].new_val > 0) {
      SCANENV_MEM_NODES(env)[pos] = SCANENV_MEM_NODES(env)[i];
      pos++;
    }
  }

  loc = env->capture_history;
  BIT_STATUS_CLEAR(env->capture_history);
  for (i = 1; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
    if (BIT_STATUS_AT(loc, i)) {
      BIT_STATUS_ON_AT_SIMPLE(env->capture_history, map[i].new_val);
    }
  }

  env->num_mem = env->num_named;
  reg->num_mem = env->num_named;

  return onig_renumber_name_table(reg, map);
}
#endif /* USE_NAMED_GROUP */

#ifdef USE_SUBEXP_CALL
static int
unset_addr_list_fix(UnsetAddrList* uslist, regex_t* reg)
{
  int i, offset;
  EffectNode* en;
  AbsAddrType addr;

  for (i = 0; i < uslist->num; i++) {
    en = &(NEFFECT(uslist->us[i].target));
    if (! IS_EFFECT_ADDR_FIXED(en)) return ONIGERR_PARSER_BUG;
    addr = en->call_addr;
    offset = uslist->us[i].offset;

    BBUF_WRITE(reg, offset, &addr, SIZE_ABSADDR);
  }
  return 0;
}
#endif

#ifdef USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
static int
qualifiers_memory_node_info(Node* node)
{
  int r = 0;

  switch (NTYPE(node)) {
  case N_LIST:
  case N_ALT:
    {
      int v;
      do {
	v = qualifiers_memory_node_info(NCONS(node).left);
	if (v > r) r = v;
      } while (v >= 0 && IS_NOT_NULL(node = NCONS(node).right));
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    if (IS_CALL_RECURSION(&NCALL(node))) {
      return NQ_TARGET_IS_EMPTY_REC; /* tiny version */
    }
    else
      r = qualifiers_memory_node_info(NCALL(node).target);
    break;
#endif

  case N_QUALIFIER:
    {
      QualifierNode* qn = &(NQUALIFIER(node));
      if (qn->upper != 0) {
	r = qualifiers_memory_node_info(qn->target);
      }
    }
    break;

  case N_EFFECT:
    {
      EffectNode* en = &(NEFFECT(node));
      switch (en->type) {
      case EFFECT_MEMORY:
	return NQ_TARGET_IS_EMPTY_MEM;
	break;

      case EFFECT_OPTION:
      case EFFECT_STOP_BACKTRACK:
	r = qualifiers_memory_node_info(en->target);
	break;
      default:
	break;
      }
    }
    break;

  case N_BACKREF:
  case N_STRING:
  case N_CTYPE:
  case N_CCLASS:
  case N_ANYCHAR:
  case N_ANCHOR:
  default:
    break;
  }

  return r;
}
#endif /* USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK */

static int
get_min_match_length(Node* node, OnigDistance *min, ScanEnv* env)
{
  OnigDistance tmin;
  int r = 0;

  *min = 0;
  switch (NTYPE(node)) {
  case N_BACKREF:
    {
      int i;
      int* backs;
      Node** nodes = SCANENV_MEM_NODES(env);
      BackrefNode* br = &(NBACKREF(node));
      if (br->state & NST_RECURSION) break;

      backs = BACKREFS_P(br);
      if (backs[0] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
      r = get_min_match_length(nodes[backs[0]], min, env);
      if (r != 0) break;
      for (i = 1; i < br->back_num; i++) {
	if (backs[i] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
	r = get_min_match_length(nodes[backs[i]], &tmin, env);
	if (r != 0) break;
	if (*min > tmin) *min = tmin;
      }
    }
    break;

#ifdef USE_SUBEXP_CALL
  case N_CALL:
    if (IS_CALL_RECURSION(&NCALL(node))) {
      EffectNode* en = &(NEFFECT(NCALL(node).target));
      if (IS_EFFECT_MIN_FIXED(en))
	*min = en->min_len;
    }
    else
      r = get_min_match_length(NCALL(node).target, min, env);
    break;
#endif

  case N_LIST: