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) More...

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. More...
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. More...

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'. More...
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. More...
const char *	REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a)
	Get the canonical regex of the given automaton. More...
unsigned int	REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a)
	Get the number of transitions that are contained in the given automaton. More...
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'. More...

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.

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 2790 of file regex_internal.c.

{
  struct REGEX_INTERNAL_Context ctx;
  struct REGEX_INTERNAL_Automaton *nfa;
  const char *regexp;
  char curlabel[2];
  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.

{
  unsigned int count;
  struct REGEX_INTERNAL_State *s;
 
  if ((NULL == a) || (0 == a->state_count))
    return;
 
  int marks[a->state_count];
 
  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 consensus-simulation::action, 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 3245 of file regex_internal.c.

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

References REGEX_INTERNAL_Automaton::canonical_regex.

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 3262 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_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 2178 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: