regex_internal.h File Reference

#include "regex_internal_lib.h"

Include dependency graph for regex_internal.h:

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

Go to the source code of this file.

Data Structures
struct	REGEX_INTERNAL_Transition
	Transition between two states. More...
struct	REGEX_INTERNAL_StateSet
	Set of states. More...
struct	REGEX_INTERNAL_State
	A state. More...
struct	REGEX_INTERNAL_Automaton
	Automaton representation. More...
struct	REGEX_INTERNAL_Context
	Context that contains an id counter for states and transitions as well as a DLL of automatons used as a stack for NFA construction. More...

Macros
#define	ALLOWED_LITERALS    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
	char array of literals that are allowed inside a regex (apart from the operators)

Typedefs
typedef int(*	REGEX_INTERNAL_traverse_check) (void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)
	Function that gets passed to automaton traversal and is called before each next traversal from state 's' using transition 't' to check if traversal should proceed.
typedef void(*	REGEX_INTERNAL_traverse_action) (void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
	Function that is called with each state, when traversing an automaton.

Enumerations
enum	REGEX_INTERNAL_AutomatonType { NFA , DFA }
	Type of an automaton. More...

Functions
struct REGEX_INTERNAL_Automaton *	REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len)
	Construct an NFA by parsing the regex string of length 'len'.
void	REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *start, REGEX_INTERNAL_traverse_check check, void *check_cls, REGEX_INTERNAL_traverse_action action, void *action_cls)
	Traverses the given automaton using depth-first-search (DFS) from it's start state, visiting all reachable states and calling 'action' on each one of them.
const char *	REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a)
	Get the canonical regex of the given automaton.
unsigned int	REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a)
	Get the number of transitions that are contained in the given automaton.
void	REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx, struct REGEX_INTERNAL_Automaton *dfa, const unsigned int stride_len)
	Adds multi-strided transitions to the given 'dfa'.

Macro Definition Documentation

ALLOWED_LITERALS

#define ALLOWED_LITERALS    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

char array of literals that are allowed inside a regex (apart from the operators)

Definition at line 42 of file regex_internal.h.

{
  struct REGEX_INTERNAL_Transition *prev;
 
  struct REGEX_INTERNAL_Transition *next;
 
  unsigned int id;
 
  char *label;
 
  struct REGEX_INTERNAL_State *to_state;
 
  struct REGEX_INTERNAL_State *from_state;
};
 
 
struct REGEX_INTERNAL_State;
 
 
struct REGEX_INTERNAL_StateSet
{
  struct REGEX_INTERNAL_State **states;
 
  unsigned int off;
 
  unsigned int size;
};
 
 
struct REGEX_INTERNAL_State
{
  struct REGEX_INTERNAL_State *prev;
 
  struct REGEX_INTERNAL_State *next;
 
  struct REGEX_INTERNAL_State *prev_SS;
 
  struct REGEX_INTERNAL_State *next_SS;
 
  struct REGEX_INTERNAL_State *prev_ST;
 
  struct REGEX_INTERNAL_State *next_ST;
 
  unsigned int id;
 
  unsigned int traversal_id;
 
  int accepting;
 
  int marked;
 
  int contained;
 
  unsigned int scc_id;
 
  int index;
 
  int lowlink;
 
  char *name;
 
  struct GNUNET_HashCode hash;
 
  unsigned int dfs_id;
 
  char *proof;
 
  unsigned int transition_count;
 
  struct REGEX_INTERNAL_Transition *transitions_head;
 
  struct REGEX_INTERNAL_Transition *transitions_tail;
 
  unsigned int incoming_transition_count;
 
  struct REGEX_INTERNAL_StateSet nfa_set;
};
 
 
enum REGEX_INTERNAL_AutomatonType
{
  NFA,
  DFA
};
 
 
struct REGEX_INTERNAL_Automaton
{
  struct REGEX_INTERNAL_Automaton *prev;
 
  struct REGEX_INTERNAL_Automaton *next;
 
  struct REGEX_INTERNAL_State *start;
 
  struct REGEX_INTERNAL_State *end;
 
  unsigned int state_count;
 
  struct REGEX_INTERNAL_State *states_head;
 
  struct REGEX_INTERNAL_State *states_tail;
 
  enum REGEX_INTERNAL_AutomatonType type;
 
  char *regex;
 
  char *canonical_regex;
 
  int is_multistrided;
};
 
 
struct REGEX_INTERNAL_Automaton *
REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len);
 
 
typedef int
(*REGEX_INTERNAL_traverse_check) (void *cls,
                                  struct REGEX_INTERNAL_State *s,
                                  struct REGEX_INTERNAL_Transition *t);
 
 
typedef void
(*REGEX_INTERNAL_traverse_action) (void *cls,
                                   const unsigned int count,
                                   struct REGEX_INTERNAL_State *s);
 
 
void
REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a,
                                   struct REGEX_INTERNAL_State *start,
                                   REGEX_INTERNAL_traverse_check check,
                                   void *check_cls,
                                   REGEX_INTERNAL_traverse_action action,
                                   void *action_cls);
 
const char *
REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a);
 
 
unsigned int
REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a);
 
 
struct REGEX_INTERNAL_Context
{
  unsigned int state_id;
 
  unsigned int transition_id;
 
  struct REGEX_INTERNAL_Automaton *stack_head;
 
  struct REGEX_INTERNAL_Automaton *stack_tail;
};
 
 
void
REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx,
                                      struct REGEX_INTERNAL_Automaton *dfa,
                                      const unsigned int stride_len);
 
 
#if 0                           /* keep Emacsens' auto-indent happy */
{
#endif
#ifdef __cplusplus
}
#endif
 
#endif

Typedef Documentation

REGEX_INTERNAL_traverse_check

typedef int(* REGEX_INTERNAL_traverse_check) (void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)

Function that gets passed to automaton traversal and is called before each next traversal from state 's' using transition 't' to check if traversal should proceed.

Return GNUNET_NO to stop traversal or GNUNET_YES to continue.

Parameters

cls	closure for the check.
s	current state in the traversal.
t	current transition from state 's' that will be used for the next step.

Returns

GNUNET_YES to proceed traversal, GNUNET_NO to stop.

Definition at line 343 of file regex_internal.h.

REGEX_INTERNAL_traverse_action

typedef void(* REGEX_INTERNAL_traverse_action) (void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)

Function that is called with each state, when traversing an automaton.

Parameters

cls	closure.
count	current count of the state, from 0 to a->state_count -1.
s	state.

Definition at line 356 of file regex_internal.h.

Enumeration Type Documentation

REGEX_INTERNAL_AutomatonType

enum REGEX_INTERNAL_AutomatonType

Type of an automaton.

Enumerator
NFA
DFA

Definition at line 249 of file regex_internal.h.

{
  NFA,
  DFA
};

Function Documentation

REGEX_INTERNAL_construct_nfa()

struct REGEX_INTERNAL_Automaton * REGEX_INTERNAL_construct_nfa	(	const char *	regex,
		const size_t	len
	)

Construct an NFA by parsing the regex string of length 'len'.

Parameters

regex	regular expression string.
len	length of the string.

Returns

NFA, needs to be freed using REGEX_INTERNAL_automaton_destroy.

Parameters

regex	regular expression string
len	length of the string

Returns

NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton

Definition at line 2795 of file regex_internal.c.

{
  struct REGEX_INTERNAL_Context ctx;
  struct REGEX_INTERNAL_Automaton *nfa;
  const char *regexp;
  char curlabel[2];
  const char *error_msg;
  unsigned int count;
  unsigned int altcount;
  unsigned int atomcount;
  unsigned int poff;
  unsigned int psize;
 
  struct
  {
    int altcount;
    int atomcount;
  } *p;
 
  if ((NULL == regex) || (0 == strlen (regex)) || (0 == len))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Could not parse regex. Empty regex string provided.\n");
 
    return NULL;
  }
  REGEX_INTERNAL_context_init (&ctx);
 
  regexp = regex;
  curlabel[1] = '\0';
  p = NULL;
  error_msg = NULL;
  altcount = 0;
  atomcount = 0;
  poff = 0;
  psize = 0;
 
  for (count = 0; count < len && *regexp; count++, regexp++)
  {
    switch (*regexp)
    {
    case '(':
      if (atomcount > 1)
      {
        --atomcount;
        nfa_add_concatenation (&ctx);
      }
      if (poff == psize)
        GNUNET_array_grow (p, psize, psize * 2 + 4);    /* FIXME why *2 +4? */
      p[poff].altcount = altcount;
      p[poff].atomcount = atomcount;
      poff++;
      altcount = 0;
      atomcount = 0;
      break;
 
    case '|':
      if (0 == atomcount)
      {
        error_msg = "Cannot append '|' to nothing";
        goto error;
      }
      while (--atomcount > 0)
        nfa_add_concatenation (&ctx);
      altcount++;
      break;
 
    case ')':
      if (0 == poff)
      {
        error_msg = "Missing opening '('";
        goto error;
      }
      if (0 == atomcount)
      {
        /* Ignore this: "()" */
        poff--;
        altcount = p[poff].altcount;
        atomcount = p[poff].atomcount;
        break;
      }
      while (--atomcount > 0)
        nfa_add_concatenation (&ctx);
      for (; altcount > 0; altcount--)
        nfa_add_alternation (&ctx);
      poff--;
      altcount = p[poff].altcount;
      atomcount = p[poff].atomcount;
      atomcount++;
      break;
 
    case '*':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '*' to nothing";
        goto error;
      }
      nfa_add_star_op (&ctx);
      break;
 
    case '+':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '+' to nothing";
        goto error;
      }
      nfa_add_plus_op (&ctx);
      break;
 
    case '?':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '?' to nothing";
        goto error;
      }
      nfa_add_question_op (&ctx);
      break;
 
    default:
      if (atomcount > 1)
      {
        --atomcount;
        nfa_add_concatenation (&ctx);
      }
      curlabel[0] = *regexp;
      nfa_add_label (&ctx, curlabel);
      atomcount++;
      break;
    }
  }
  if (0 != poff)
  {
    error_msg = "Unbalanced parenthesis";
    goto error;
  }
  while (--atomcount > 0)
    nfa_add_concatenation (&ctx);
  for (; altcount > 0; altcount--)
    nfa_add_alternation (&ctx);
 
  GNUNET_array_grow (p, psize, 0);
 
  nfa = ctx.stack_tail;
  GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
 
  if (NULL != ctx.stack_head)
  {
    error_msg = "Creating the NFA failed. NFA stack was not empty!";
    goto error;
  }
 
  /* Remember the regex that was used to generate this NFA */
  nfa->regex = GNUNET_strdup (regex);
 
  /* create depth-first numbering of the states for pretty printing */
  REGEX_INTERNAL_automaton_traverse (nfa,
                                     NULL,
                                     NULL,
                                     NULL,
                                     &number_states,
                                     NULL);
 
  /* No multistriding added so far */
  nfa->is_multistrided = GNUNET_NO;
 
  return nfa;
 
error:
  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex);
  if (NULL != error_msg)
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
 
  GNUNET_free (p);
 
  while (NULL != (nfa = ctx.stack_head))
  {
    GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
    REGEX_INTERNAL_automaton_destroy (nfa);
  }
 
  return NULL;
}

References ctx, GNUNET_array_grow, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_NO, GNUNET_strdup, REGEX_INTERNAL_Automaton::is_multistrided, nfa_add_alternation(), nfa_add_concatenation(), nfa_add_label(), nfa_add_plus_op(), nfa_add_question_op(), nfa_add_star_op(), number_states(), p, REGEX_INTERNAL_Automaton::regex, REGEX_INTERNAL_automaton_destroy(), REGEX_INTERNAL_automaton_traverse(), and REGEX_INTERNAL_context_init().

Referenced by REGEX_INTERNAL_construct_dfa().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_automaton_traverse()

void REGEX_INTERNAL_automaton_traverse	(	const struct REGEX_INTERNAL_Automaton *	a,
		struct REGEX_INTERNAL_State *	start,
		REGEX_INTERNAL_traverse_check	check,
		void *	check_cls,
		REGEX_INTERNAL_traverse_action	action,
		void *	action_cls
	)

Traverses the given automaton using depth-first-search (DFS) from it's start state, visiting all reachable states and calling 'action' on each one of them.

Parameters

a	automaton to be traversed.
start	start state, pass a->start or NULL to traverse the whole automaton.
check	function that is checked before advancing on each transition in the DFS.
check_cls	closure for check.
action	action to be performed on each state.
action_cls	closure for action

Definition at line 505 of file regex_internal.c.

{
  if ((NULL == a) || (0 == a->state_count))
    return;
 
  {
    unsigned int count;
    int marks[a->state_count];
    struct REGEX_INTERNAL_State *s;
 
 
    for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
         s = s->next, count++)
    {
      s->traversal_id = count;
      marks[s->traversal_id] = GNUNET_NO;
    }
 
    count = 0;
 
    if (NULL == start)
      s = a->start;
    else
      s = start;
 
    automaton_state_traverse (s,
                              marks,
                              &count,
                              check,
                              check_cls,
                              action,
                              action_cls);
  }
}

References automaton_state_traverse(), GNUNET_NO, REGEX_INTERNAL_State::next, start, REGEX_INTERNAL_Automaton::start, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_State::traversal_id.

Referenced by automaton_create_proofs(), dfa_remove_unreachable_states(), REGEX_INTERNAL_construct_nfa(), REGEX_INTERNAL_dfa_add_multi_strides(), and REGEX_TEST_automaton_save_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_INTERNAL_get_canonical_regex()

const char * REGEX_INTERNAL_get_canonical_regex

(

struct REGEX_INTERNAL_Automaton *

a

)

Get the canonical regex of the given automaton.

When constructing the automaton a proof is computed for each state, consisting of the regular expression leading to this state. A complete regex for the automaton can be computed by combining these proofs. As of now this function is only useful for testing.

Parameters

a	automaton for which the canonical regex should be returned.

Returns

canonical regex string.

Definition at line 3250 of file regex_internal.c.

{
  if (NULL == a)
    return NULL;
 
  return a->canonical_regex;
}

References REGEX_INTERNAL_Automaton::canonical_regex, and REGEX_INTERNAL_StateSet::off.

REGEX_INTERNAL_get_transition_count()

unsigned int REGEX_INTERNAL_get_transition_count

(

struct REGEX_INTERNAL_Automaton *

a

)

Get the number of transitions that are contained in the given automaton.

Parameters

a	automaton for which the number of transitions should be returned.

Returns

number of transitions in the given automaton.

Definition at line 3267 of file regex_internal.c.

{
  unsigned int t_count;
  struct REGEX_INTERNAL_State *s;
 
  if (NULL == a)
    return 0;
 
  t_count = 0;
  for (s = a->states_head; NULL != s; s = s->next)
    t_count += s->transition_count;
 
  return t_count;
}

References REGEX_INTERNAL_State::next, REGEX_INTERNAL_StateSet::off, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_State::transition_count.

REGEX_INTERNAL_dfa_add_multi_strides()

void REGEX_INTERNAL_dfa_add_multi_strides	(	struct REGEX_INTERNAL_Context *	regex_ctx,
		struct REGEX_INTERNAL_Automaton *	dfa,
		const unsigned int	stride_len
	)

Adds multi-strided transitions to the given 'dfa'.

Parameters

regex_ctx	regex context needed to add transitions to the automaton.
dfa	DFA to which the multi strided transitions should be added.
stride_len	length of the strides.

Definition at line 2183 of file regex_internal.c.

{
  struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *t_next;
 
  if ((1 > stride_len) || (GNUNET_YES == dfa->is_multistrided))
    return;
 
  /* Compute the new transitions of given stride_len */
  REGEX_INTERNAL_automaton_traverse (dfa,
                                     dfa->start,
                                     NULL,
                                     NULL,
                                     &dfa_add_multi_strides,
                                     &ctx);
 
  /* Add all the new transitions to the automaton. */
  for (t = ctx.transitions_head; NULL != t; t = t_next)
  {
    t_next = t->next;
    state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
    GNUNET_CONTAINER_DLL_remove (ctx.transitions_head, ctx.transitions_tail, t);
    GNUNET_free (t->label);
    GNUNET_free (t);
  }
 
  /* Mark this automaton as multistrided */
  dfa->is_multistrided = GNUNET_YES;
}

References ctx, dfa_add_multi_strides(), GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_YES, REGEX_INTERNAL_Automaton::is_multistrided, GNUNET_SCHEDULER_Task::next, REGEX_INTERNAL_automaton_traverse(), REGEX_INTERNAL_Automaton::start, state_add_transition(), and t.

Here is the call graph for this function: