contrib/libgnuregex/regexec.c

148 					  const re_node_set *nodes)
158 static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
676   if (dfa->init_state->nodes.nelem == 0
677       && dfa->init_state_word->nodes.nelem == 0
678       && (dfa->init_state_nl->nodes.nelem == 0
1127 	  err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1133 	      err = transit_state_bkref (mctx, &cur_state->nodes);
1232   re_token_type_t type = dfa->nodes[node].type;
1233   unsigned int constraint = dfa->nodes[node].constraint;
1258   for (i = 0; i < state->nodes.nelem; ++i)
1259     if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1260       return state->nodes.elems[i];
1277   if (IS_EPSILON_NODE (dfa->nodes[node].type))
1279       re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1316       re_token_type_t type = dfa->nodes[node].type;
1319       if (dfa->nodes[node].accept_mb)
1325 	  int subexp_idx = dfa->nodes[node].opr.idx + 1;
1347 	      if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1354 	  || check_node_accept (mctx, dfa->nodes + node, *pidx))
1359 		     || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1545   int type = dfa->nodes[cur_node].type;
1548       int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1559       int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1572 	      if (dfa->nodes[cur_node].opt_subexp
1590    and sift the nodes in each states according to the following rules.
1610   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1625   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1656       /* Add all the nodes which satisfy the following conditions:
1685      (with the epsilon nodes pre-filtered out).  */
1693       re_token_type_t type = dfa->nodes[prev_node].type;
1698       if (dfa->nodes[prev_node].accept_mb)
1706 	  && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1772 	  err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1773 					&src[st_idx]->nodes);
1795 		: &mctx->state_log[str_idx]->nodes);
1803 	  /* At first, add the nodes which can epsilon transit to a node in
1877 	if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1926       subexp_idx = dfa->nodes[ent->node].opr.idx;
1956   /* Else, we are on the boundary: examine the nodes on the epsilon
1961       switch (dfa->nodes[node].type)
2011 	  if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2016 	  if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2055 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2076       subexp_idx = dfa->nodes[ent->node].opr.idx;
2084 	      re_token_type_t type = dfa->nodes[node].type;
2086 		  && subexp_idx == dfa->nodes[node].opr.idx)
2089 		       && subexp_idx == dfa->nodes[node].opr.idx)
2128 	      re_token_type_t type = dfa->nodes[node].type;
2131 		  if (subexp_idx != dfa->nodes[node].opr.idx)
2168       type = dfa->nodes[node].type;
2373       /* Note: We already add the nodes of the initial state,
2393       *err = check_subexp_matching_top (mctx, &next_state->nodes,
2401 	  *err = transit_state_bkref (mctx, &next_state->nodes);
2440 /* From the node set CUR_NODES, pick up the nodes whose types are
2455 	   Because there might be more than one nodes whose types are
2457 	   nodes.
2462       if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2463 	  && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2465 	      & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2489   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2492   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2494       int cur_node = state->nodes.elems[node_cnt];
2495       if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2526   for (i = 0; i < pstate->nodes.nelem; ++i)
2529       int cur_node_idx = pstate->nodes.elems[i];
2534       if (!dfa->nodes[cur_node_idx].accept_mb)
2537       if (dfa->nodes[cur_node_idx].constraint)
2542 	  if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2590 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2597   for (i = 0; i < nodes->nelem; ++i)
2600       int node_idx = nodes->elems[i];
2602       const re_token_t *node = dfa->nodes + node_idx;
2647 			: mctx->state_log[cur_str_idx]->nodes.nelem);
2679 	      && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2721   subexp_num = dfa->nodes[bkref_node].opr.idx;
2731       if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2783       /* Then, search for the other last nodes of the sub expression.  */
2787 	  const re_node_set *nodes;
2812 	  nodes = &mctx->state_log[sl_str]->nodes;
2813 	  cls_node = find_subexp_node (dfa, nodes, subexp_num,
2875 	 Because there might be more than one nodes whose types are
2877 	 nodes.
2882 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2886   for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2888       int cls_node = nodes->elems[cls_idx];
2889       const re_token_t *node = dfa->nodes + cls_node;
2915   subexp_num = dfa->nodes[top_node].opr.idx;
2960 	  err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2994 				   &mctx->state_log[str_idx + 1]->nodes);
3041 	       : &mctx->state_log[last_str]->nodes);
3057 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3079       re_token_type_t type = dfa->nodes[cur_node].type;
3084       if (dfa->nodes[cur_node].accept_mb)
3097 		  err = re_node_set_merge (&union_set, &dest_state->nodes);
3122 	  || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3136 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3137    CUR_NODES, however exclude the nodes which are:
3156   /* Create a new node set NEW_NODES with the nodes which are epsilon
3166 	  /* There are no problematic nodes, just merge them.  */
3176 	  /* There are problematic nodes, re-calculate incrementally.  */
3205       if (dfa->nodes[cur_node].type == type
3206 	  && dfa->nodes[cur_node].opr.idx == ex_subexp)
3295 	      if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3299 					   &mctx->state_log[to_idx]->nodes);
3350   /* We build DFA states which corresponds to the destination nodes
3351      from `state'.  `dests_node[i]' represents the nodes which i-th
3369   /* At first, group all nodes belonging to `state' into several
3559 /* Group all nodes belonging to STATE into several destinations.
3560    Then for all destinations, set the nodes belonging to the destination
3574   const re_node_set *cur_nodes = &state->nodes;
3578   /* For all the nodes belonging to `state',  */
3581       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3746 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3750    This function handles the nodes which can accept one character, or
3751    one collating element like '.', '[a-z]', opposite to the other nodes
3759   const re_token_t *node = dfa->nodes + node_idx;