glibc/regex/regexec.c

149 					  const re_node_set *nodes)
159 static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
668   if (dfa->init_state->nodes.nelem == 0
669       && dfa->init_state_word->nodes.nelem == 0
670       && (dfa->init_state_nl->nodes.nelem == 0
1106 	  err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1112 	      err = transit_state_bkref (mctx, &cur_state->nodes);
1210   re_token_type_t type = dfa->nodes[node].type;
1211   unsigned int constraint = dfa->nodes[node].constraint;
1236   for (i = 0; i < state->nodes.nelem; ++i)
1237     if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1238       return state->nodes.elems[i];
1255   if (IS_EPSILON_NODE (dfa->nodes[node].type))
1257       re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1294       re_token_type_t type = dfa->nodes[node].type;
1297       if (dfa->nodes[node].accept_mb)
1303 	  int subexp_idx = dfa->nodes[node].opr.idx + 1;
1325 	      if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1332 	  || check_node_accept (mctx, dfa->nodes + node, *pidx))
1337 		     || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1523   int type = dfa->nodes[cur_node].type;
1526       int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1537       int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1550 	      if (dfa->nodes[cur_node].opt_subexp
1568    and sift the nodes in each states according to the following rules.
1588   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1603   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1634       /* Add all the nodes which satisfy the following conditions:
1663      (with the epsilon nodes pre-filtered out).  */
1671       re_token_type_t type = dfa->nodes[prev_node].type;
1676       if (dfa->nodes[prev_node].accept_mb)
1684 	  && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1749 	  err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1750 					&src[st_idx]->nodes);
1772 		: &mctx->state_log[str_idx]->nodes);
1780 	  /* At first, add the nodes which can epsilon transit to a node in
1850 	if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1899       subexp_idx = dfa->nodes[ent->node].opr.idx;
1929   /* Else, we are on the boundary: examine the nodes on the epsilon
1934       switch (dfa->nodes[node].type)
1984 	  if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1989 	  if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2028 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2049       subexp_idx = dfa->nodes[ent->node].opr.idx;
2057 	      re_token_type_t type = dfa->nodes[node].type;
2059 		  && subexp_idx == dfa->nodes[node].opr.idx)
2062 		       && subexp_idx == dfa->nodes[node].opr.idx)
2101 	      re_token_type_t type = dfa->nodes[node].type;
2104 		  if (subexp_idx != dfa->nodes[node].opr.idx)
2141       type = dfa->nodes[node].type;
2346       /* Note: We already add the nodes of the initial state,
2366       *err = check_subexp_matching_top (mctx, &next_state->nodes,
2374 	  *err = transit_state_bkref (mctx, &next_state->nodes);
2413 /* From the node set CUR_NODES, pick up the nodes whose types are
2428 	   Because there might be more than one nodes whose types are
2430 	   nodes.
2435       if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2436 	  && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2438 	      & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2462   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2465   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2467       int cur_node = state->nodes.elems[node_cnt];
2468       if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2499   for (i = 0; i < pstate->nodes.nelem; ++i)
2502       int cur_node_idx = pstate->nodes.elems[i];
2507       if (!dfa->nodes[cur_node_idx].accept_mb)
2510       if (dfa->nodes[cur_node_idx].constraint)
2515 	  if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2563 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2570   for (i = 0; i < nodes->nelem; ++i)
2573       int node_idx = nodes->elems[i];
2575       const re_token_t *node = dfa->nodes + node_idx;
2620 			: mctx->state_log[cur_str_idx]->nodes.nelem);
2652 	      && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2694   subexp_num = dfa->nodes[bkref_node].opr.idx;
2704       if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2756       /* Then, search for the other last nodes of the sub expression.  */
2760 	  const re_node_set *nodes;
2785 	  nodes = &mctx->state_log[sl_str]->nodes;
2786 	  cls_node = find_subexp_node (dfa, nodes, subexp_num,
2848 	 Because there might be more than one nodes whose types are
2850 	 nodes.
2855 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2859   for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2861       int cls_node = nodes->elems[cls_idx];
2862       const re_token_t *node = dfa->nodes + cls_node;
2888   subexp_num = dfa->nodes[top_node].opr.idx;
2933 	  err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2967 				   &mctx->state_log[str_idx + 1]->nodes);
3014 	       : &mctx->state_log[last_str]->nodes);
3030 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3052       re_token_type_t type = dfa->nodes[cur_node].type;
3057       if (dfa->nodes[cur_node].accept_mb)
3070 		  err = re_node_set_merge (&union_set, &dest_state->nodes);
3095 	  || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3109 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3110    CUR_NODES, however exclude the nodes which are:
3129   /* Create a new node set NEW_NODES with the nodes which are epsilon
3139 	  /* There are no problematic nodes, just merge them.  */
3149 	  /* There are problematic nodes, re-calculate incrementally.  */
3178       if (dfa->nodes[cur_node].type == type
3179 	  && dfa->nodes[cur_node].opr.idx == ex_subexp)
3268 	      if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3272 					   &mctx->state_log[to_idx]->nodes);
3323   /* We build DFA states which corresponds to the destination nodes
3324      from `state'.  `dests_node[i]' represents the nodes which i-th
3342   /* At first, group all nodes belonging to `state' into several
3523 /* Group all nodes belonging to STATE into several destinations.
3524    Then for all destinations, set the nodes belonging to the destination
3538   const re_node_set *cur_nodes = &state->nodes;
3542   /* For all the nodes belonging to `state',  */
3545       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3710 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3714    This function handles the nodes which can accept one character, or
3715    one collating element like '.', '[a-z]', opposite to the other nodes
3723   const re_token_t *node = dfa->nodes + node_idx;