Lines Matching defs:node
41 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
42 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
44 bin_tree_t *node);
45 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
46 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
47 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
53 int node, int root);
119 static void free_token (re_token_t *node);
120 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
121 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
311 int node = init_state->nodes.elems[node_cnt];
312 re_token_type_t type = dfa->nodes[node].type;
316 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
325 *p++ = dfa->nodes[node].opr.c;
326 while (++node < dfa->nodes_len
327 && dfa->nodes[node].type == CHARACTER
328 && dfa->nodes[node].mb_partial)
329 *p++ = dfa->nodes[node].opr.c;
345 bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
354 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
1001 /* Initial states have the epsilon closure of the node which is
1002 the first node of the regular expression. */
1084 int node, i, mb_chars = 0, has_period = 0;
1086 for (node = 0; node < dfa->nodes_len; ++node)
1087 switch (dfa->nodes[node].type)
1090 if (dfa->nodes[node].opr.c >= 0x80)
1094 switch (dfa->nodes[node].opr.ctx_type)
1124 if (dfa->nodes[node].opr.sbcset[i])
1132 for (node = 0; node < dfa->nodes_len; ++node)
1134 if (dfa->nodes[node].type == CHARACTER
1135 && dfa->nodes[node].opr.c >= 0x80)
1136 dfa->nodes[node].mb_partial = 0;
1137 else if (dfa->nodes[node].type == OP_PERIOD)
1138 dfa->nodes[node].type = OP_UTF8_PERIOD;
1219 bin_tree_t *node, *prev;
1221 for (node = root; ; )
1225 while (node->left || node->right)
1226 if (node->left)
1227 node = node->left;
1229 node = node->right;
1233 reg_errcode_t err = fn (extra, node);
1236 if (node->parent == NULL)
1238 prev = node;
1239 node = node->parent;
1241 /* Go up while we have a node that is reached from the right. */
1242 while (node->right == prev || node->right == NULL);
1243 node = node->right;
1251 bin_tree_t *node;
1253 for (node = root; ; )
1255 reg_errcode_t err = fn (extra, node);
1259 /* Go to the left node, or up and to the right. */
1260 if (node->left)
1261 node = node->left;
1265 while (node->right == prev || node->right == NULL)
1267 prev = node;
1268 node = node->parent;
1269 if (!node)
1272 node = node->right;
1281 optimize_subexps (void *extra, bin_tree_t *node)
1285 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1287 int idx = node->token.opr.idx;
1288 node->token.opr.idx = dfa->subexp_map[idx];
1289 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1292 else if (node->token.type == SUBEXP
1293 && node->left && node->left->token.type == SUBEXP)
1295 int other_idx = node->left->token.opr.idx;
1297 node->left = node->left->left;
1298 if (node->left)
1299 node->left->parent = node;
1301 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1309 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1312 lower_subexps (void *extra, bin_tree_t *node)
1317 if (node->left && node->left->token.type == SUBEXP)
1319 node->left = lower_subexp (&err, preg, node->left);
1320 if (node->left)
1321 node->left->parent = node;
1323 if (node->right && node->right->token.type == SUBEXP)
1325 node->right = lower_subexp (&err, preg, node->right);
1326 if (node->right)
1327 node->right->parent = node;
1334 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1337 bin_tree_t *body = node->left;
1345 && node->left != NULL
1346 && (node->token.opr.idx >= BITSET_WORD_BITS
1348 & ((bitset_word_t) 1 << node->token.opr.idx))))
1349 return node->left;
1351 /* Convert the SUBEXP node to the concatenation of an
1363 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1364 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1371 calc_first (void *extra, bin_tree_t *node)
1374 if (node->token.type == CONCAT)
1376 node->first = node->left->first;
1377 node->node_idx = node->left->node_idx;
1381 node->first = node;
1382 node->node_idx = re_dfa_add_node (dfa, node->token);
1383 if (BE (node->node_idx == -1, 0))
1385 if (node->token.type == ANCHOR)
1386 dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1393 calc_next (void *extra, bin_tree_t *node)
1395 switch (node->token.type)
1398 node->left->next = node;
1401 node->left->next = node->right->first;
1402 node->right->next = node->next;
1405 if (node->left)
1406 node->left->next = node->next;
1407 if (node->right)
1408 node->right->next = node->next;
1414 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1416 link_nfa_nodes (void *extra, bin_tree_t *node)
1419 int idx = node->node_idx;
1422 switch (node->token.type)
1428 assert (node->next == NULL);
1436 if (node->left != NULL)
1437 left = node->left->first->node_idx;
1439 left = node->next->node_idx;
1440 if (node->right != NULL)
1441 right = node->right->first->node_idx;
1443 right = node->next->node_idx;
1453 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1457 dfa->nexts[idx] = node->next->node_idx;
1458 if (node->token.type == OP_BACK_REF)
1463 assert (!IS_EPSILON_NODE (node->token.type));
1464 dfa->nexts[idx] = node->next->node_idx;
1471 /* Duplicate the epsilon closure of the node ROOT_NODE.
1503 /* In case of the node can't epsilon-transit, don't duplicate the
1505 destination of the node. */
1511 /* In case of the node can epsilon-transit, and it has only one
1515 /* If the node is root_node itself, it means the epsilon clsoure
1524 /* In case of the node has another constraint, add it. */
1535 /* In case of the node can epsilon-transit, and it has two
1539 /* Search for a duplicated node which satisfies the constraint. */
1543 /* There is no such duplicated node, create a new one. */
1558 /* There is a duplicated node which satisfies the constraint,
1579 /* Search for a node which is duplicated from the node ORG_NODE, and
1596 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1597 Return the index of the new node, or -1 if insufficient storage is
1610 /* Store the index of the original node. */
1637 /* Calculate "eclosure" for all the node in DFA. */
1684 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
1691 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1695 /* This indicates that we are calculating this node now.
1697 dfa->eclosures[node].nelem = -1;
1699 /* If the current node has constraints, duplicate all nodes
1701 if (dfa->nodes[node].constraint
1702 && dfa->edests[node].nelem
1703 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1705 err = duplicate_node_closure (dfa, node, node, node,
1706 dfa->nodes[node].constraint);
1712 if (IS_EPSILON_NODE(dfa->nodes[node].type))
1713 for (i = 0; i < dfa->edests[node].nelem; ++i)
1716 int edest = dfa->edests[node].elems[i];
1739 the epsilon closure of this node is also incomplete. */
1748 ret = re_node_set_insert (&eclosure, node);
1752 dfa->eclosures[node].nelem = 0;
1754 dfa->eclosures[node] = eclosure;
3280 /* Then join them by ALT node. */
3668 /* Then join them by ALT node. */
3736 /* Create a tree node. */
3785 mark_opt_subexp (void *extra, bin_tree_t *node)
3788 if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3789 node->token.opt_subexp = 1;
3797 free_token (re_token_t *node)
3800 if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
3801 free_charset (node->opr.mbcset);
3804 if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
3805 re_free (node->opr.sbcset);
3812 free_tree (void *extra, bin_tree_t *node)
3814 free_token (&node->token);
3819 /* Duplicate the node SRC, and return new node. This is a preorder
3827 const bin_tree_t *node;
3831 for (node = root; ; )
3834 *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
3841 /* Go to the left node, or up and to the right. */
3842 if (node->left)
3844 node = node->left;
3850 while (node->right == prev || node->right == NULL)
3852 prev = node;
3853 node = node->parent;
3855 if (!node)
3858 node = node->right;