+ // $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
+ // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
+
+ R_cur_r = NULL;
+ R_cur_l = NULL;
+
+ // cache results from strcmp, we might need these many times
+ ij_kj_cmp = nullstrcmp (R_last_ij, R_last_kj);
+ ij_ik_cmp = nullstrcmp (R_last_ij, R_last_ik);
+ ik_kk_cmp = nullstrcmp (R_last_ik, R_last_kk);
+ kk_kj_cmp = nullstrcmp (R_last_kk, R_last_kj);
+
+ // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
+ // as parentheses, so we can better compare the contents
+ R_temp_ik = remove_parentheses (remove_epsilon (R_last_ik));
+ R_temp_kk = remove_parentheses (remove_epsilon (R_last_kk));
+ R_temp_kj = remove_parentheses (remove_epsilon (R_last_kj));
+
+ clean_ik_kk_cmp = nullstrcmp (R_last_ik, R_temp_kk);
+ clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last_kj);
+
+ // construct R_cur_l (and, if necessary R_cur_r)
+ if (NULL != R_last_ij)
+ {
+ // Assign R_temp_ij to R_last_ij and remove epsilon as well
+ // as parentheses, so we can better compare the contents
+ R_temp_ij = remove_parentheses (remove_epsilon (R_last_ij));
+
+ if (0 == strcmp (R_temp_ij, R_temp_ik) && 0 == strcmp (R_temp_ik, R_temp_kk)
+ && 0 == strcmp (R_temp_kk, R_temp_kj))
+ {
+ if (0 == strlen (R_temp_ij))
+ {
+ R_cur_r = GNUNET_strdup ("");
+ }
+ else if ((0 == strncmp (R_last_ij, "(|", 2)) ||
+ (0 == strncmp (R_last_ik, "(|", 2) &&
+ 0 == strncmp (R_last_kj, "(|", 2)))
+ {
+ // a|(e|a)a*(e|a) = a*
+ // a|(e|a)(e|a)*(e|a) = a*
+ // (e|a)|aa*a = a*
+ // (e|a)|aa*(e|a) = a*
+ // (e|a)|(e|a)a*a = a*
+ // (e|a)|(e|a)a*(e|a) = a*
+ // (e|a)|(e|a)(e|a)*(e|a) = a*
+ if (GNUNET_YES == needs_parentheses (R_temp_ij))
+ GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s*", R_temp_ij);
+ }
+ else
+ {
+ // a|aa*a = a+
+ // a|(e|a)a*a = a+
+ // a|aa*(e|a) = a+
+ // a|(e|a)(e|a)*a = a+
+ // a|a(e|a)*(e|a) = a+
+ if (GNUNET_YES == needs_parentheses (R_temp_ij))
+ GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s+", R_temp_ij);
+ }
+ }
+ else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp && 0 != clean_ik_kk_cmp)
+ {
+ // a|ab*b = ab*
+ if (strlen (R_last_kk) < 1)
+ R_cur_r = GNUNET_strdup (R_last_ij);
+ else if (GNUNET_YES == needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ij, R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s%s*", R_last_ij, R_last_kk);
+
+ R_cur_l = NULL;
+ }
+ else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp && 0 != clean_kk_kj_cmp)
+ {
+ // a|bb*a = b*a
+ if (strlen (R_last_kk) < 1)
+ R_cur_r = GNUNET_strdup (R_last_kj);
+ else if (GNUNET_YES == needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_kj);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last_kj);
+
+ R_cur_l = NULL;
+ }
+ else if (0 == ij_ik_cmp && 0 == kk_kj_cmp && !has_epsilon (R_last_ij) &&
+ has_epsilon (R_last_kk))
+ {
+ // a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab*
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ij, R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s%s*", R_last_ij, R_temp_kk);
+
+ R_cur_l = NULL;
+ }
+ else if (0 == ij_kj_cmp && 0 == ik_kk_cmp && !has_epsilon (R_last_ij) &&
+ has_epsilon (R_last_kk))
+ {
+ // a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_ij);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last_ij);
+
+ R_cur_l = NULL;
+ }
+ else
+ {
+ temp_a = (NULL == R_last_ij) ? NULL : GNUNET_strdup (R_last_ij);
+ temp_a = remove_parentheses (temp_a);
+ R_cur_l = temp_a;
+ }
+
+ GNUNET_free_non_null (R_temp_ij);
+ }
+ else
+ {
+ // we have no left side
+ R_cur_l = NULL;
+ }
+
+ // construct R_cur_r, if not already constructed
+ if (NULL == R_cur_r)
+ {
+ length = strlen (R_temp_kk) - strlen (R_last_ik);
+
+ // a(ba)*bx = (ab)+x
+ if (length > 0 && NULL != R_last_kk && 0 < strlen (R_last_kk) &&
+ NULL != R_last_kj && 0 < strlen (R_last_kj) && NULL != R_last_ik &&
+ 0 < strlen (R_last_ik) && 0 == strkcmp (R_temp_kk, R_last_ik, length) &&
+ 0 == strncmp (R_temp_kk, R_last_kj, length))
+ {
+ temp_a = GNUNET_malloc (length + 1);
+ temp_b = GNUNET_malloc ((strlen (R_last_kj) - length) + 1);
+
+ length_l = 0;
+ length_r = 0;
+
+ for (cnt = 0; cnt < strlen (R_last_kj); cnt++)
+ {
+ if (cnt < length)
+ {
+ temp_a[length_l] = R_last_kj[cnt];
+ length_l++;
+ }
+ else
+ {
+ temp_b[length_r] = R_last_kj[cnt];
+ length_r++;
+ }
+ }
+ temp_a[length_l] = '\0';
+ temp_b[length_r] = '\0';
+
+ // e|(ab)+ = (ab)*
+ if (NULL != R_cur_l && 0 == strlen (R_cur_l) && 0 == strlen (temp_b))
+ {
+ GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last_ik, temp_a);
+ GNUNET_free (R_cur_l);
+ R_cur_l = NULL;
+ }
+ else
+ {
+ GNUNET_asprintf (&R_cur_r, "(%s%s)+%s", R_last_ik, temp_a, temp_b);
+ }
+ GNUNET_free (temp_a);
+ GNUNET_free (temp_b);
+ }
+ else if (0 == strcmp (R_temp_ik, R_temp_kk) &&
+ 0 == strcmp (R_temp_kk, R_temp_kj))
+ {
+ // (e|a)a*(e|a) = a*
+ // (e|a)(e|a)*(e|a) = a*
+ if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj))
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk);
+ }
+ // aa*a = a+a
+ else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp &&
+ !has_epsilon (R_last_ik))
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
+ }
+ // (e|a)a*a = a+
+ // aa*(e|a) = a+
+ // a(e|a)*(e|a) = a+
+ // (e|a)a*a = a+
+ else
+ {
+ eps_check =
+ (has_epsilon (R_last_ik) + has_epsilon (R_last_kk) +
+ has_epsilon (R_last_kj));
+
+ if (eps_check == 1)
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s+", R_temp_kk);
+ }
+ }
+ }
+ // aa*b = a+b
+ // (e|a)(e|a)*b = a*b
+ else if (0 == strcmp (R_temp_ik, R_temp_kk))
+ {
+ if (has_epsilon (R_last_ik))
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_kj);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s*%s", R_temp_kk, R_last_kj);
+ }
+ else
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_last_kj);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last_kj);
+ }
+ }
+ // ba*a = ba+
+ // b(e|a)*(e|a) = ba*
+ else if (0 == strcmp (R_temp_kk, R_temp_kj))
+ {
+ if (has_epsilon (R_last_kj))
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ik, R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s%s*", R_last_ik, R_temp_kk);
+ }
+ else
+ {
+ if (needs_parentheses (R_temp_kk))
+ GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_last_ik, R_temp_kk);
+ else
+ GNUNET_asprintf (&R_cur_r, "%s+%s", R_last_ik, R_temp_kk);
+ }
+ }
+ else
+ {
+ if (strlen (R_temp_kk) > 0)
+ {
+ if (needs_parentheses (R_temp_kk))
+ {
+ GNUNET_asprintf (&R_cur_r, "%s(%s)*%s", R_last_ik, R_temp_kk,
+ R_last_kj);
+ }
+ else
+ {
+ GNUNET_asprintf (&R_cur_r, "%s%s*%s", R_last_ik, R_temp_kk,
+ R_last_kj);
+ }
+ }
+ else
+ {
+ GNUNET_asprintf (&R_cur_r, "%s%s", R_last_ik, R_last_kj);
+ }
+ }
+ }
+
+ GNUNET_free_non_null (R_temp_ik);
+ GNUNET_free_non_null (R_temp_kk);
+ GNUNET_free_non_null (R_temp_kj);
+
+ if (NULL == R_cur_l && NULL == R_cur_r)
+ {
+ *R_cur_ij = NULL;
+ return;
+ }
+
+ if (NULL != R_cur_l && NULL == R_cur_r)
+ {
+ *R_cur_ij = R_cur_l;
+ return;
+ }
+
+ if (NULL == R_cur_l && NULL != R_cur_r)
+ {
+ *R_cur_ij = R_cur_r;
+ return;
+ }
+
+ if (0 == nullstrcmp (R_cur_l, R_cur_r))
+ {
+ *R_cur_ij = R_cur_l;
+ GNUNET_free (R_cur_r);
+ return;
+ }
+
+ GNUNET_asprintf (R_cur_ij, "(%s|%s)", R_cur_l, R_cur_r);
+
+ GNUNET_free (R_cur_l);
+ GNUNET_free (R_cur_r);
+}
+
+
+/**
+ * create proofs for all states in the given automaton. Implementation of the
+ * algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and
+ * Computation 3rd Edition" by Hopcroft, Motwani and Ullman.
+ *
+ * @param a automaton.
+ */
+static void
+automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
+{
+ unsigned int n = a->state_count;
+ struct GNUNET_REGEX_State *states[n];
+ char *R_last[n][n];
+ char *R_cur[n][n];
+ char *temp;
+ struct GNUNET_REGEX_Transition *t;
+ char *complete_regex;
+ unsigned int i;
+ unsigned int j;
+ unsigned int k;
+
+
+ /* create depth-first numbering of the states, initializes 'state' */
+ GNUNET_REGEX_automaton_traverse (a, &number_states, states);
+
+ /* Compute regular expressions of length "1" between each pair of states */
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < n; j++)
+ {
+ R_cur[i][j] = NULL;
+ R_last[i][j] = NULL;
+ }
+ for (t = states[i]->transitions_head; NULL != t; t = t->next)
+ {
+ j = t->to_state->proof_id;
+ if (NULL == R_last[i][j])
+ GNUNET_asprintf (&R_last[i][j], "%c", t->label);
+ else
+ {
+ temp = R_last[i][j];
+ GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
+ GNUNET_free (temp);
+ }
+ }
+ if (NULL == R_last[i][i])
+ GNUNET_asprintf (&R_last[i][i], "");
+ else
+ {
+ temp = R_last[i][i];
+ GNUNET_asprintf (&R_last[i][i], "(|%s)", R_last[i][i]);
+ GNUNET_free (temp);
+ }
+ }
+ for (i = 0; i < n; i++)
+ for (j = 0; j < n; j++)
+ if (needs_parentheses (R_last[i][j]))
+ {
+ temp = R_last[i][j];
+ GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
+ GNUNET_free (temp);
+ }
+
+ /* Compute regular expressions of length "k" between each pair of states per induction */
+ for (k = 0; k < n; k++)
+ {
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < n; j++)
+ {
+ // Basis for the recursion:
+ // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
+ // R_last == R^{(k-1)}, R_cur == R^{(k)}
+
+ // Create R_cur[i][j] and simplify the expression
+ automaton_create_proofs_simplify (R_last[i][j], R_last[i][k],
+ R_last[k][k], R_last[k][j],
+ &R_cur[i][j]);
+ }
+ }
+
+ // set R_last = R_cur
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < n; j++)
+ {
+ GNUNET_free_non_null (R_last[i][j]);
+ R_last[i][j] = R_cur[i][j];
+ R_cur[i][j] = NULL;
+ }
+ }
+ }
+
+ // assign proofs and hashes
+ for (i = 0; i < n; i++)
+ {
+ if (NULL != R_last[a->start->proof_id][i])
+ {
+ states[i]->proof = GNUNET_strdup (R_last[a->start->proof_id][i]);
+ GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof),
+ &states[i]->hash);
+ }
+ }
+
+ // complete regex for whole DFA: union of all pairs (start state/accepting state(s)).
+ complete_regex = NULL;
+ for (i = 0; i < n; i++)
+ {
+ if (states[i]->accepting)
+ {
+ if (NULL == complete_regex && 0 < strlen (R_last[a->start->proof_id][i]))
+ {
+ GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->proof_id][i]);
+ }
+ else if (NULL != R_last[a->start->proof_id][i] &&
+ 0 < strlen (R_last[a->start->proof_id][i]))
+ {
+ temp = complete_regex;
+ GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex,
+ R_last[a->start->proof_id][i]);
+ GNUNET_free (temp);
+ }
+ }
+ }
+ a->canonical_regex = complete_regex;
+
+ // cleanup
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < n; j++)
+ GNUNET_free_non_null (R_last[i][j]);
+ }
+}
+
+
+/**
+ * Creates a new DFA state based on a set of NFA states. Needs to be freed using
+ * automaton_destroy_state.
+ *
+ * @param ctx context
+ * @param nfa_states set of NFA states on which the DFA should be based on
+ *
+ * @return new DFA state
+ */
+static struct GNUNET_REGEX_State *
+dfa_state_create (struct GNUNET_REGEX_Context *ctx,
+ struct GNUNET_REGEX_StateSet *nfa_states)
+{
+ struct GNUNET_REGEX_State *s;
+ char *name;
+ int len = 0;
+ struct GNUNET_REGEX_State *cstate;
+ struct GNUNET_REGEX_Transition *ctran;
+ unsigned int i;
+
+ s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
+ s->id = ctx->state_id++;
+ s->accepting = 0;
+ s->marked = 0;
+ s->name = NULL;
+ s->scc_id = 0;
+ s->index = -1;
+ s->lowlink = -1;
+ s->contained = 0;
+ s->proof = NULL;
+
+ if (NULL == nfa_states)
+ {
+ GNUNET_asprintf (&s->name, "s%i", s->id);
+ return s;
+ }
+
+ s->nfa_set = nfa_states;
+
+ if (nfa_states->len < 1)
+ return s;
+
+ // Create a name based on 'sset'
+ s->name = GNUNET_malloc (sizeof (char) * 2);
+ strcat (s->name, "{");
+ name = NULL;
+
+ for (i = 0; i < nfa_states->len; i++)
+ {
+ cstate = nfa_states->states[i];
+ GNUNET_asprintf (&name, "%i,", cstate->id);
+
+ if (NULL != name)
+ {
+ len = strlen (s->name) + strlen (name) + 1;
+ s->name = GNUNET_realloc (s->name, len);
+ strcat (s->name, name);
+ GNUNET_free (name);
+ name = NULL;
+ }
+
+ // Add a transition for each distinct label to NULL state
+ for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
+ {
+ if (0 != ctran->label)
+ state_add_transition (ctx, s, ctran->label, NULL);
+ }
+
+ // If the nfa_states contain an accepting state, the new dfa state is also
+ // accepting
+ if (cstate->accepting)
+ s->accepting = 1;
+ }
+
+ s->name[strlen (s->name) - 1] = '}';
+
+ return s;
+}
+
+
+/**
+ * Move from the given state 's' to the next state on transition 'label'
+ *
+ * @param s starting state
+ * @param label edge label to follow
+ *
+ * @return new state or NULL, if transition on label not possible
+ */
+static struct GNUNET_REGEX_State *
+dfa_move (struct GNUNET_REGEX_State *s, const char label)
+{
+ struct GNUNET_REGEX_Transition *t;
+ struct GNUNET_REGEX_State *new_s;
+
+ if (NULL == s)
+ return NULL;
+
+ new_s = NULL;
+
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ {
+ if (label == t->label)
+ {
+ new_s = t->to_state;
+ break;
+ }
+ }
+
+ return new_s;
+}
+
+
+/**
+ * Remove all unreachable states from DFA 'a'. Unreachable states are those
+ * states that are not reachable from the starting state.
+ *
+ * @param a DFA automaton
+ */
+static void
+dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
+{
+ struct GNUNET_REGEX_State *s;
+ struct GNUNET_REGEX_State *s_next;
+
+ // 1. unmark all states
+ for (s = a->states_head; NULL != s; s = s->next)
+ s->marked = GNUNET_NO;
+
+ // 2. traverse dfa from start state and mark all visited states
+ GNUNET_REGEX_automaton_traverse (a, NULL, NULL);
+
+ // 3. delete all states that were not visited
+ for (s = a->states_head; NULL != s; s = s_next)
+ {
+ s_next = s->next;
+ if (GNUNET_NO == s->marked)
+ automaton_remove_state (a, s);
+ }
+}
+
+
+/**
+ * Remove all dead states from the DFA 'a'. Dead states are those states that do
+ * not transition to any other state but themselves.
+ *
+ * @param a DFA automaton
+ */
+static void
+dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
+{
+ struct GNUNET_REGEX_State *s;
+ struct GNUNET_REGEX_Transition *t;
+ int dead;
+
+ GNUNET_assert (DFA == a->type);
+
+ for (s = a->states_head; NULL != s; s = s->next)
+ {
+ if (s->accepting)
+ continue;
+
+ dead = 1;
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ {
+ if (NULL != t->to_state && t->to_state != s)
+ {
+ dead = 0;
+ break;
+ }
+ }
+
+ if (0 == dead)
+ continue;
+
+ // state s is dead, remove it
+ automaton_remove_state (a, s);
+ }
+}
+
+
+/**
+ * Merge all non distinguishable states in the DFA 'a'
+ *
+ * @param ctx context
+ * @param a DFA automaton
+ */
+static void
+dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
+ struct GNUNET_REGEX_Automaton *a)
+{
+ unsigned int i;
+ int table[a->state_count][a->state_count];
+ struct GNUNET_REGEX_State *s1;
+ struct GNUNET_REGEX_State *s2;
+ struct GNUNET_REGEX_Transition *t1;
+ struct GNUNET_REGEX_Transition *t2;
+ struct GNUNET_REGEX_State *s1_next;
+ struct GNUNET_REGEX_State *s2_next;
+ int change;
+ unsigned int num_equal_edges;
+
+ for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1;
+ i++, s1 = s1->next)
+ {
+ s1->marked = i;
+ }
+
+ // Mark all pairs of accepting/!accepting states
+ for (s1 = a->states_head; NULL != s1; s1 = s1->next)
+ {
+ for (s2 = a->states_head; NULL != s2; s2 = s2->next)
+ {
+ table[s1->marked][s2->marked] = 0;
+
+ if ((s1->accepting && !s2->accepting) ||
+ (!s1->accepting && s2->accepting))
+ {
+ table[s1->marked][s2->marked] = 1;
+ }
+ }
+ }
+
+ // Find all equal states
+ change = 1;
+ while (0 != change)
+ {
+ change = 0;
+ for (s1 = a->states_head; NULL != s1; s1 = s1->next)
+ {
+ for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
+ {
+ if (0 != table[s1->marked][s2->marked])
+ continue;
+
+ num_equal_edges = 0;
+ for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
+ {
+ for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
+ {
+ if (t1->label == t2->label)
+ {
+ num_equal_edges++;
+ if (0 != table[t1->to_state->marked][t2->to_state->marked] ||
+ 0 != table[t2->to_state->marked][t1->to_state->marked])
+ {
+ table[s1->marked][s2->marked] = t1->label != 0 ? t1->label : 1;
+ change = 1;
+ }
+ }
+ }
+ }
+ if (num_equal_edges != s1->transition_count ||
+ num_equal_edges != s2->transition_count)
+ {
+ // Make sure ALL edges of possible equal states are the same
+ table[s1->marked][s2->marked] = -2;
+ }
+ }
+ }
+ }
+
+ // Merge states that are equal
+ for (s1 = a->states_head; NULL != s1; s1 = s1_next)
+ {
+ s1_next = s1->next;
+ for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
+ {
+ s2_next = s2->next;
+ if (table[s1->marked][s2->marked] == 0)
+ automaton_merge_states (ctx, a, s1, s2);
+ }
+ }
+}
+
+
+/**
+ * Minimize the given DFA 'a' by removing all unreachable states, removing all
+ * dead states and merging all non distinguishable states
+ *
+ * @param ctx context
+ * @param a DFA automaton
+ */
+static void
+dfa_minimize (struct GNUNET_REGEX_Context *ctx,
+ struct GNUNET_REGEX_Automaton *a)
+{
+ if (NULL == a)
+ return;
+
+ GNUNET_assert (DFA == a->type);
+
+ // 1. remove unreachable states
+ dfa_remove_unreachable_states (a);
+
+ // 2. remove dead states
+ dfa_remove_dead_states (a);
+
+ // 3. Merge nondistinguishable states
+ dfa_merge_nondistinguishable_states (ctx, a);
+}
+
+
+/**
+ * Creates a new NFA fragment. Needs to be cleared using
+ * automaton_fragment_clear.
+ *
+ * @param start starting state
+ * @param end end state
+ *
+ * @return new NFA fragment
+ */
+static struct GNUNET_REGEX_Automaton *
+nfa_fragment_create (struct GNUNET_REGEX_State *start,
+ struct GNUNET_REGEX_State *end)
+{
+ struct GNUNET_REGEX_Automaton *n;
+
+ n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
+
+ n->type = NFA;
+ n->start = NULL;
+ n->end = NULL;
+
+ if (NULL == start || NULL == end)
+ return n;
+
+ automaton_add_state (n, end);
+ automaton_add_state (n, start);
+
+ n->start = start;
+ n->end = end;
+
+ return n;
+}
+
+
+/**
+ * Adds a list of states to the given automaton 'n'.
+ *
+ * @param n automaton to which the states should be added
+ * @param states_head head of the DLL of states
+ * @param states_tail tail of the DLL of states
+ */
+static void
+nfa_add_states (struct GNUNET_REGEX_Automaton *n,
+ struct GNUNET_REGEX_State *states_head,
+ struct GNUNET_REGEX_State *states_tail)
+{
+ struct GNUNET_REGEX_State *s;
+
+ if (NULL == n || NULL == states_head)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
+ return;
+ }
+
+ if (NULL == n->states_head)
+ {
+ n->states_head = states_head;
+ n->states_tail = states_tail;
+ return;
+ }
+
+ if (NULL != states_head)
+ {
+ n->states_tail->next = states_head;
+ n->states_tail = states_tail;
+ }
+
+ for (s = states_head; NULL != s; s = s->next)
+ n->state_count++;
+}
+
+
+/**
+ * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
+ *
+ * @param ctx context
+ * @param accepting is it an accepting state or not
+ *
+ * @return new NFA state
+ */
+static struct GNUNET_REGEX_State *
+nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
+{
+ struct GNUNET_REGEX_State *s;
+
+ s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
+ s->id = ctx->state_id++;
+ s->accepting = accepting;
+ s->marked = 0;
+ s->contained = 0;
+ s->index = -1;
+ s->lowlink = -1;
+ s->scc_id = 0;
+ s->name = NULL;
+ GNUNET_asprintf (&s->name, "s%i", s->id);
+
+ return s;
+}
+
+
+/**
+ * Calculates the NFA closure set for the given state.
+ *
+ * @param nfa the NFA containing 's'
+ * @param s starting point state
+ * @param label transitioning label on which to base the closure on,
+ * pass 0 for epsilon transition
+ *
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ */
+static struct GNUNET_REGEX_StateSet *
+nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa,
+ struct GNUNET_REGEX_State *s, const char label)
+{
+ struct GNUNET_REGEX_StateSet *cls;
+ struct GNUNET_REGEX_StateSet *cls_check;
+ struct GNUNET_REGEX_State *clsstate;
+ struct GNUNET_REGEX_State *currentstate;
+ struct GNUNET_REGEX_Transition *ctran;
+
+ if (NULL == s)
+ return NULL;
+
+ cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
+ cls_check = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
+
+ for (clsstate = nfa->states_head; NULL != clsstate; clsstate = clsstate->next)
+ clsstate->contained = 0;
+
+ // Add start state to closure only for epsilon closure
+ if (0 == label)
+ GNUNET_array_append (cls->states, cls->len, s);
+
+ GNUNET_array_append (cls_check->states, cls_check->len, s);
+ while (cls_check->len > 0)
+ {
+ currentstate = cls_check->states[cls_check->len - 1];
+ GNUNET_array_grow (cls_check->states, cls_check->len, cls_check->len - 1);
+
+ for (ctran = currentstate->transitions_head; NULL != ctran;
+ ctran = ctran->next)
+ {
+ if (NULL != ctran->to_state && label == ctran->label)
+ {
+ clsstate = ctran->to_state;
+
+ if (NULL != clsstate && 0 == clsstate->contained)
+ {
+ GNUNET_array_append (cls->states, cls->len, clsstate);
+ GNUNET_array_append (cls_check->states, cls_check->len, clsstate);
+ clsstate->contained = 1;
+ }
+ }
+ }
+ }
+ GNUNET_assert (0 == cls_check->len);
+ GNUNET_free (cls_check);
+
+ // sort the states
+ if (cls->len > 1)
+ qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *),
+ state_compare);
+
+ return cls;
+}
+
+
+/**
+ * Calculates the closure set for the given set of states.
+ *
+ * @param nfa the NFA containing 's'
+ * @param states list of states on which to base the closure on
+ * @param label transitioning label for which to base the closure on,
+ * pass 0 for epsilon transition
+ *
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ */
+static struct GNUNET_REGEX_StateSet *
+nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa,
+ struct GNUNET_REGEX_StateSet *states, const char label)
+{
+ struct GNUNET_REGEX_State *s;
+ struct GNUNET_REGEX_StateSet *sset;
+ struct GNUNET_REGEX_StateSet *cls;
+ unsigned int i;
+ unsigned int j;
+ unsigned int k;
+ unsigned int contains;
+
+ if (NULL == states)
+ return NULL;