regex_internal_lib.h File Reference

library to parse regular expressions into dfa More...

#include "../../plugin/regex/regex_block_lib.h"
#include "gnunet_util_lib.h"
#include "gnunet_dht_service.h"
#include "gnunet_statistics_service.h"

Include dependency graph for regex_internal_lib.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef void(*	REGEX_INTERNAL_KeyIterator) (void *cls, const struct GNUNET_HashCode *key, const char *proof, int accepting, unsigned int num_edges, const struct REGEX_BLOCK_Edge *edges)
	Iterator callback function. More...
typedef void(*	REGEX_INTERNAL_Found) (void *cls, const struct GNUNET_PeerIdentity *id, const struct GNUNET_DHT_PathElement *get_path, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *put_path, unsigned int put_path_length)
	Search callback function. More...

Functions
struct REGEX_INTERNAL_Automaton *	REGEX_INTERNAL_construct_dfa (const char *regex, const size_t len, unsigned int max_path_len)
	Construct DFA for the given 'regex' of length 'len'. More...
void	REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a)
	Free the memory allocated by constructing the REGEX_INTERNAL_Automaton. More...
int	REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string)
	Evaluates the given 'string' against the given compiled regex. More...
size_t	REGEX_INTERNAL_get_first_key (const char *input_string, size_t string_len, struct GNUNET_HashCode *key)
	Get the first key for the given input_string. More...
void	REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a, REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
	Iterate over all edges starting from start state of automaton 'a'. More...
void	REGEX_INTERNAL_iterate_reachable_edges (struct REGEX_INTERNAL_Automaton *a, REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
	Iterate over all edges of automaton 'a' that are reachable from a state with a proof of at least GNUNET_REGEX_INITIAL_BYTES characters. More...
struct REGEX_INTERNAL_Announcement *	REGEX_INTERNAL_announce (struct GNUNET_DHT_Handle *dht, const struct GNUNET_CRYPTO_EddsaPrivateKey *priv, const char *regex, uint16_t compression, struct GNUNET_STATISTICS_Handle *stats)
	Announce a regular expression: put all states of the automaton in the DHT. More...
void	REGEX_INTERNAL_reannounce (struct REGEX_INTERNAL_Announcement *h)
	Announce again a regular expression previously announced. More...
void	REGEX_INTERNAL_announce_cancel (struct REGEX_INTERNAL_Announcement *h)
	Clear all cached data used by a regex announce. More...
struct REGEX_INTERNAL_Search *	REGEX_INTERNAL_search (struct GNUNET_DHT_Handle *dht, const char *string, REGEX_INTERNAL_Found callback, void *callback_cls, struct GNUNET_STATISTICS_Handle *stats)
	Search for a peer offering a regex matching certain string in the DHT. More...
void	REGEX_INTERNAL_search_cancel (struct REGEX_INTERNAL_Search *h)
	Stop search and free all data used by a REGEX_INTERNAL_search() call. More...

Detailed Description

library to parse regular expressions into dfa

Author

Maximilian Szengel

Definition in file regex_internal_lib.h.

Typedef Documentation

REGEX_INTERNAL_KeyIterator

typedef void(* REGEX_INTERNAL_KeyIterator) (void *cls, const struct GNUNET_HashCode *key, const char *proof, int accepting, unsigned int num_edges, const struct REGEX_BLOCK_Edge *edges)

Iterator callback function.

Parameters

cls	closure.
key	hash for current state.
proof	proof for current state
accepting	GNUNET_YES if this is an accepting state, GNUNET_NO if not.
num_edges	number of edges leaving current state.
edges	edges leaving current state.

Definition at line 121 of file regex_internal_lib.h.

REGEX_INTERNAL_Found

typedef void(* REGEX_INTERNAL_Found) (void *cls, const struct GNUNET_PeerIdentity *id, const struct GNUNET_DHT_PathElement *get_path, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *put_path, unsigned int put_path_length)

Search callback function.

Parameters

cls	Closure provided in REGEX_INTERNAL_search().
id	Peer providing a regex that matches the string.
get_path	Path of the get request.
get_path_length	Length of get_path.
put_path	Path of the put request.
put_path_length	Length of the put_path.

Definition at line 221 of file regex_internal_lib.h.

Function Documentation

REGEX_INTERNAL_construct_dfa()

struct REGEX_INTERNAL_Automaton * REGEX_INTERNAL_construct_dfa	(	const char *	regex,
		const size_t	len,
		unsigned int	max_path_len
	)

Construct DFA for the given 'regex' of length 'len'.

Path compression means, that for example a DFA o -> a -> b -> c -> o will be compressed to o -> abc -> o. Note that this parameter influences the non-determinism of states of the resulting NFA in the DHT (number of outgoing edges with the same label). For example for an application that stores IPv4 addresses as bitstrings it could make sense to limit the path compression to 4 or 8.

Parameters

regex	regular expression string.
len	length of the regular expression.
max_path_len	limit the path compression length to the given value. If set to 1, no path compression is applied. Set to 0 for maximal possible path compression (generally not desirable).

Returns

DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy().

Definition at line 3037 of file regex_internal.c.

{
  struct REGEX_INTERNAL_Context ctx;
  struct REGEX_INTERNAL_Automaton *dfa;
  struct REGEX_INTERNAL_Automaton *nfa;
  struct REGEX_INTERNAL_StateSet nfa_start_eps_cls;
  struct REGEX_INTERNAL_StateSet singleton_set;
 
  REGEX_INTERNAL_context_init (&ctx);
 
  /* Create NFA */
  nfa = REGEX_INTERNAL_construct_nfa (regex, len);
 
  if (NULL == nfa)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Could not create DFA, because NFA creation failed\n");
    return NULL;
  }
 
  dfa = GNUNET_new (struct REGEX_INTERNAL_Automaton);
  dfa->type = DFA;
  dfa->regex = GNUNET_strdup (regex);
 
  /* Create DFA start state from epsilon closure */
  memset (&singleton_set, 0, sizeof(struct REGEX_INTERNAL_StateSet));
  state_set_append (&singleton_set, nfa->start);
  nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL);
  state_set_clear (&singleton_set);
  dfa->start = dfa_state_create (&ctx, &nfa_start_eps_cls);
  automaton_add_state (dfa, dfa->start);
 
  construct_dfa_states (&ctx, nfa, dfa, dfa->start);
  REGEX_INTERNAL_automaton_destroy (nfa);
 
  /* Minimize DFA */
  if (GNUNET_OK != dfa_minimize (&ctx, dfa))
  {
    REGEX_INTERNAL_automaton_destroy (dfa);
    return NULL;
  }
 
  /* Create proofs and hashes for all states */
  if (GNUNET_OK != automaton_create_proofs (dfa))
  {
    REGEX_INTERNAL_automaton_destroy (dfa);
    return NULL;
  }
 
  /* Compress linear DFA paths */
  if (1 != max_path_len)
    dfa_compress_paths (&ctx, dfa, max_path_len);
 
  return dfa;
}

References automaton_add_state(), automaton_create_proofs(), construct_dfa_states(), ctx, DFA, dfa_compress_paths(), dfa_minimize(), dfa_state_create(), GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_new, GNUNET_OK, GNUNET_strdup, nfa_closure_set_create(), REGEX_INTERNAL_Automaton::regex, REGEX_INTERNAL_automaton_destroy(), REGEX_INTERNAL_construct_nfa(), REGEX_INTERNAL_context_init(), REGEX_INTERNAL_Automaton::start, state_set_append(), state_set_clear(), and REGEX_INTERNAL_Automaton::type.

Referenced by main(), and REGEX_INTERNAL_announce().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_automaton_destroy()

void REGEX_INTERNAL_automaton_destroy

(

struct REGEX_INTERNAL_Automaton *

a

)

Free the memory allocated by constructing the REGEX_INTERNAL_Automaton.

data structure.

Parameters

a	automaton to be destroyed.

Definition at line 3097 of file regex_internal.c.

{
  struct REGEX_INTERNAL_State *s;
  struct REGEX_INTERNAL_State *next_state;
 
  if (NULL == a)
    return;
 
  GNUNET_free (a->regex);
  GNUNET_free (a->canonical_regex);
 
  for (s = a->states_head; NULL != s; s = next_state)
  {
    next_state = s->next;
    GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
    automaton_destroy_state (s);
  }
 
  GNUNET_free (a);
}

References automaton_destroy_state(), REGEX_INTERNAL_Automaton::canonical_regex, GNUNET_CONTAINER_DLL_remove, GNUNET_free, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::regex, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by main(), REGEX_INTERNAL_announce_cancel(), REGEX_INTERNAL_construct_dfa(), and REGEX_INTERNAL_construct_nfa().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_eval()

int REGEX_INTERNAL_eval	(	struct REGEX_INTERNAL_Automaton *	a,
		const char *	string
	)

Evaluates the given 'string' against the given compiled regex.

Parameters

a	automaton.
string	string to check.

Returns

0 if string matches, non 0 otherwise.

Definition at line 3224 of file regex_internal.c.

{
  int result;
 
  switch (a->type)
  {
  case DFA:
    result = evaluate_dfa (a, string);
    break;
 
  case NFA:
    result = evaluate_nfa (a, string);
    break;
 
  default:
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Evaluating regex failed, automaton has no type!\n");
    result = GNUNET_SYSERR;
    break;
  }
 
  return result;
}

References DFA, evaluate_dfa(), evaluate_nfa(), GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_SYSERR, NFA, result, and REGEX_INTERNAL_Automaton::type.

Here is the call graph for this function:

REGEX_INTERNAL_get_first_key()

size_t REGEX_INTERNAL_get_first_key	(	const char *	input_string,
		size_t	string_len,
		struct GNUNET_HashCode *	key
	)

Get the first key for the given input_string.

This hashes the first x bits of the input_string.

Parameters

input_string	string.
string_len	length of the input_string.
key	pointer to where to write the hash code.

Returns

number of bits of input_string that have been consumed to construct the key

Definition at line 3294 of file regex_internal.c.

{
  size_t size;
 
  size = string_len < GNUNET_REGEX_INITIAL_BYTES ? string_len
         : GNUNET_REGEX_INITIAL_BYTES;
  if (NULL == input_string)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n");
    return 0;
  }
  GNUNET_CRYPTO_hash (input_string, size, key);
 
  return size;
}

References GNUNET_CRYPTO_hash(), GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_REGEX_INITIAL_BYTES, key, and size.

Referenced by REGEX_INTERNAL_search().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_iterate_all_edges()

void REGEX_INTERNAL_iterate_all_edges	(	struct REGEX_INTERNAL_Automaton *	a,
		REGEX_INTERNAL_KeyIterator	iterator,
		void *	iterator_cls
	)

Iterate over all edges starting from start state of automaton 'a'.

Calling iterator for each edge.

Parameters

a	automaton.
iterator	iterator called for each edge.
iterator_cls	closure.

Definition at line 3438 of file regex_internal.c.

{
  struct REGEX_INTERNAL_State *s;
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating over starting edges\n");
  iterate_initial_edge (GNUNET_REGEX_INITIAL_BYTES,
                        GNUNET_REGEX_INITIAL_BYTES,
                        NULL,
                        a->start,
                        iterator,
                        iterator_cls);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating over DFA edges\n");
  for (s = a->states_head; NULL != s; s = s->next)
  {
    struct REGEX_BLOCK_Edge edges[s->transition_count];
    unsigned int num_edges;
 
    num_edges = state_get_edges (s, edges);
    if (((NULL != s->proof) && (0 < strlen (s->proof))) || s->accepting)
    {
      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                  "Creating DFA edges at `%s' under key %s\n",
                  s->proof,
                  GNUNET_h2s (&s->hash));
      iterator (iterator_cls,
                &s->hash,
                s->proof,
                s->accepting,
                num_edges,
                edges);
    }
    s->marked = GNUNET_NO;
  }
}

References GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_NO, GNUNET_REGEX_INITIAL_BYTES, iterate_initial_edge(), REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::start, state_get_edges(), and REGEX_INTERNAL_Automaton::states_head.

Referenced by main(), and REGEX_INTERNAL_iterate_reachable_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_iterate_reachable_edges()

void REGEX_INTERNAL_iterate_reachable_edges	(	struct REGEX_INTERNAL_Automaton *	a,
		REGEX_INTERNAL_KeyIterator	iterator,
		void *	iterator_cls
	)

Iterate over all edges of automaton 'a' that are reachable from a state with a proof of at least GNUNET_REGEX_INITIAL_BYTES characters.

Call the iterator for each such edge.

Parameters

a	automaton.
iterator	iterator called for each reachable edge.
iterator_cls	closure.

Definition at line 3640 of file regex_internal.c.

{
  struct GNUNET_CONTAINER_MultiHashMap *hm;
  struct client_iterator ci;
 
  hm = GNUNET_CONTAINER_multihashmap_create (a->state_count * 2, GNUNET_NO);
  ci.iterator = iterator;
  ci.iterator_cls = iterator_cls;
 
  REGEX_INTERNAL_iterate_all_edges (a, &store_all_states, hm);
  GNUNET_CONTAINER_multihashmap_iterate (hm, &reachability_iterator, hm);
  GNUNET_CONTAINER_multihashmap_iterate (hm, &iterate_reachables, &ci);
 
  GNUNET_CONTAINER_multihashmap_destroy (hm);
}

References GNUNET_CONTAINER_multihashmap_create(), GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_NO, iterate_reachables(), client_iterator::iterator, client_iterator::iterator_cls, reachability_iterator(), REGEX_INTERNAL_iterate_all_edges(), REGEX_INTERNAL_Automaton::state_count, and store_all_states().

Referenced by main(), and REGEX_INTERNAL_reannounce().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_announce()

struct REGEX_INTERNAL_Announcement * REGEX_INTERNAL_announce	(	struct GNUNET_DHT_Handle *	dht,
		const struct GNUNET_CRYPTO_EddsaPrivateKey *	priv,
		const char *	regex,
		uint16_t	compression,
		struct GNUNET_STATISTICS_Handle *	stats
	)

Announce a regular expression: put all states of the automaton in the DHT.

Does not free resources, must call REGEX_INTERNAL_announce_cancel() for that.

Parameters

dht	An existing and valid DHT service handle. CANNOT be NULL.
priv	our private key, must remain valid until the announcement is cancelled
regex	Regular expression to announce.
compression	How many characters per edge can we squeeze?
stats	Optional statistics handle to report usage. Can be NULL.

Returns

Handle to reuse o free cached resources. Must be freed by calling REGEX_INTERNAL_announce_cancel().

Definition at line 198 of file regex_internal_dht.c.

{
  struct REGEX_INTERNAL_Announcement *h;
 
  GNUNET_assert (NULL != dht);
  h = GNUNET_new (struct REGEX_INTERNAL_Announcement);
  h->regex = regex;
  h->dht = dht;
  h->stats = stats;
  h->priv = priv;
  h->dfa = REGEX_INTERNAL_construct_dfa (regex, strlen (regex), compression);
  REGEX_INTERNAL_reannounce (h);
  return h;
}

References dht, GNUNET_assert, GNUNET_new, h, REGEX_INTERNAL_Announcement::priv, REGEX_INTERNAL_Announcement::regex, REGEX_INTERNAL_construct_dfa(), REGEX_INTERNAL_reannounce(), and stats.

Referenced by handle_announce(), and reannounce_regex().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_reannounce()

void REGEX_INTERNAL_reannounce

(

struct REGEX_INTERNAL_Announcement *

h

)

Announce again a regular expression previously announced.

Does use caching to speed up process.

Parameters

h	Handle returned by a previous REGEX_INTERNAL_announce() call.

Definition at line 219 of file regex_internal_dht.c.

{
  GNUNET_assert (NULL != h->dfa);  /* make sure to call announce first */
  LOG (GNUNET_ERROR_TYPE_INFO,
       "REGEX_INTERNAL_reannounce: %s\n",
       h->regex);
  REGEX_INTERNAL_iterate_reachable_edges (h->dfa,
                                          &regex_iterator,
                                          h);
}

References GNUNET_assert, GNUNET_ERROR_TYPE_INFO, h, LOG, REGEX_INTERNAL_iterate_reachable_edges(), and regex_iterator().

Referenced by reannounce(), reannounce_regex(), and REGEX_INTERNAL_announce().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_announce_cancel()

void REGEX_INTERNAL_announce_cancel

(

struct REGEX_INTERNAL_Announcement *

h

)

Clear all cached data used by a regex announce.

Does not close DHT connection.

Parameters

h	Handle returned by a previous REGEX_INTERNAL_announce() call.

Definition at line 238 of file regex_internal_dht.c.

{
  REGEX_INTERNAL_automaton_destroy (h->dfa);
  GNUNET_free (h);
}

References GNUNET_free, h, and REGEX_INTERNAL_automaton_destroy().

Referenced by client_disconnect_cb(), and shutdown_task().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_search()

struct REGEX_INTERNAL_Search * REGEX_INTERNAL_search	(	struct GNUNET_DHT_Handle *	dht,
		const char *	string,
		REGEX_INTERNAL_Found	callback,
		void *	callback_cls,
		struct GNUNET_STATISTICS_Handle *	stats
	)

Search for a peer offering a regex matching certain string in the DHT.

The search runs until REGEX_INTERNAL_search_cancel() is called, even if results are returned.

Parameters

dht	An existing and valid DHT service handle.
string	String to match against the regexes in the DHT.
callback	Callback for found peers.
callback_cls	Closure for callback.
stats	Optional statistics handle to report usage. Can be NULL.

Returns

Handle to stop search and free resources. Must be freed by calling REGEX_INTERNAL_search_cancel().

Definition at line 698 of file regex_internal_dht.c.

{
  struct REGEX_INTERNAL_Search *h;
  struct GNUNET_DHT_GetHandle *get_h;
  struct RegexSearchContext *ctx;
  struct GNUNET_HashCode key;
  size_t size;
  size_t len;
 
  /* Initialize handle */
  GNUNET_assert (NULL != dht);
  GNUNET_assert (NULL != callback);
  h = GNUNET_new (struct REGEX_INTERNAL_Search);
  h->dht = dht;
  h->description = GNUNET_strdup (string);
  h->callback = callback;
  h->callback_cls = callback_cls;
  h->stats = stats;
  h->dht_get_handles = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO);
  h->dht_get_results = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO);
 
  /* Initialize context */
  len = strlen (string);
  size = REGEX_INTERNAL_get_first_key (string, len, &key);
  LOG (GNUNET_ERROR_TYPE_INFO,
       "Initial key for `%s' is %s (based on `%.*s')\n",
       string,
       GNUNET_h2s (&key),
       (int) size,
       string);
  ctx = GNUNET_new (struct RegexSearchContext);
  ctx->position = size;
  ctx->info = h;
  GNUNET_array_append (h->contexts,
                       h->n_contexts,
                       ctx);
  /* Start search in DHT */
  get_h = GNUNET_DHT_get_start (h->dht,     /* handle */
                                GNUNET_BLOCK_TYPE_REGEX, /* type */
                                &key,     /* key to search */
                                DHT_REPLICATION, /* replication level */
                                DHT_OPT,
                                &h->description[size],           /* xquery */
                                // FIXME add BLOOMFILTER to exclude filtered peers
                                len + 1 - size,                /* xquery bits */
                                // FIXME add BLOOMFILTER SIZE
                                &dht_get_string_handler, ctx);
  GNUNET_break (
    GNUNET_OK ==
    GNUNET_CONTAINER_multihashmap_put (h->dht_get_handles,
                                       &key,
                                       get_h,
                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)
    );
 
  return h;
}

References ctx, dht, dht_get_string_handler(), DHT_OPT, DHT_REPLICATION, GNUNET_array_append, GNUNET_assert, GNUNET_BLOCK_TYPE_REGEX, GNUNET_break, GNUNET_CONTAINER_multihashmap_create(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST, GNUNET_DHT_get_start(), GNUNET_ERROR_TYPE_INFO, GNUNET_h2s(), GNUNET_new, GNUNET_NO, GNUNET_OK, GNUNET_strdup, h, key, LOG, REGEX_INTERNAL_get_first_key(), size, and stats.

Referenced by dht_connect_cb(), and handle_search().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_search_cancel()

void REGEX_INTERNAL_search_cancel

(

struct REGEX_INTERNAL_Search *

h

)

Stop search and free all data used by a REGEX_INTERNAL_search() call.

Does not close DHT connection.

Parameters

h	Handle returned by a previous REGEX_INTERNAL_search() call.

Stop search and free all data used by a REGEX_INTERNAL_search() call.

Parameters

h	the search context.

Definition at line 809 of file regex_internal_dht.c.

{
  unsigned int i;
 
  GNUNET_free (h->description);
  GNUNET_CONTAINER_multihashmap_iterate (h->dht_get_handles,
                                         &regex_cancel_dht_get, NULL);
  GNUNET_CONTAINER_multihashmap_iterate (h->dht_get_results,
                                         &regex_free_result, NULL);
  GNUNET_CONTAINER_multihashmap_destroy (h->dht_get_results);
  GNUNET_CONTAINER_multihashmap_destroy (h->dht_get_handles);
  if (0 < h->n_contexts)
  {
    for (i = 0; i < h->n_contexts; i++)
      GNUNET_free (h->contexts[i]);
    GNUNET_free (h->contexts);
  }
  GNUNET_free (h);
}

References GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_free, h, regex_cancel_dht_get(), and regex_free_result().

Referenced by client_disconnect_cb(), and dht_da().

Here is the call graph for this function:

Here is the caller graph for this function: