GNUnet  0.11.x
regex_test_graph.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2012 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
25 #include "platform.h"
26 #include "regex_internal_lib.h"
27 #include "regex_test_lib.h"
28 #include "regex_internal.h"
29 
35 {
39  FILE *filep;
40 
45  int verbose;
46 
50  int coloring;
51 };
52 
53 
65 static void
66 scc_tarjan_strongconnect (unsigned int *scc_counter,
67  struct REGEX_INTERNAL_State *v, unsigned int *index,
68  struct REGEX_INTERNAL_State **stack,
69  unsigned int *stack_size)
70 {
71  struct REGEX_INTERNAL_State *w;
73 
74  v->index = *index;
75  v->lowlink = *index;
76  (*index)++;
77  stack[(*stack_size)++] = v;
78  v->contained = 1;
79 
80  for (t = v->transitions_head; NULL != t; t = t->next)
81  {
82  w = t->to_state;
83 
84  if (NULL == w)
85  continue;
86 
87  if (w->index < 0)
88  {
89  scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
90  v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
91  }
92  else if (1 == w->contained)
93  v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
94  }
95 
96  if (v->lowlink == v->index)
97  {
98  (*scc_counter)++;
99  do
100  {
101  w = stack[--(*stack_size)];
102  w->contained = 0;
103  w->scc_id = *scc_counter;
104  }
105  while (w != v);
106  }
107 }
108 
109 
116 static void
118 {
119  unsigned int index;
120  unsigned int scc_counter;
121  struct REGEX_INTERNAL_State *v;
122  struct REGEX_INTERNAL_State *stack[a->state_count];
123  unsigned int stack_size;
124 
125  for (v = a->states_head; NULL != v; v = v->next)
126  {
127  v->contained = 0;
128  v->index = -1;
129  v->lowlink = -1;
130  }
131 
132  stack_size = 0;
133  index = 0;
134  scc_counter = 0;
135 
136  for (v = a->states_head; NULL != v; v = v->next)
137  {
138  if (v->index < 0)
139  scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
140  }
141 }
142 
143 
153 void
154 REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count,
155  struct REGEX_INTERNAL_State *s)
156 {
157  struct REGEX_TEST_Graph_Context *ctx = cls;
158  struct REGEX_INTERNAL_Transition *ctran;
159  char *s_acc = NULL;
160  char *s_tran = NULL;
161  char *name;
162  char *to_name;
163 
164  if (GNUNET_YES == ctx->verbose)
165  GNUNET_asprintf (&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
166  GNUNET_h2s (&s->hash));
167  else
168  GNUNET_asprintf (&name, "%i", s->dfs_id);
169 
170  if (s->accepting)
171  {
172  if (GNUNET_YES == ctx->coloring)
173  {
174  GNUNET_asprintf (&s_acc,
175  "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
176  name, s->scc_id * s->scc_id);
177  }
178  else
179  {
180  GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name,
181  s->scc_id);
182  }
183  }
184  else if (GNUNET_YES == ctx->coloring)
185  {
186  GNUNET_asprintf (&s_acc,
187  "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
188  s->scc_id * s->scc_id);
189  }
190  else
191  {
192  GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
193  }
194 
195  GNUNET_assert (NULL != s_acc);
196 
197  fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
198  GNUNET_free (s_acc);
199  s_acc = NULL;
200 
201  for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
202  {
203  if (NULL == ctran->to_state)
204  {
206  "Transition from State %i has no state for transitioning\n",
207  s->id);
208  continue;
209  }
210 
211  if (GNUNET_YES == ctx->verbose)
212  {
213  GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
214  ctran->to_state->name, ctran->to_state->proof,
215  GNUNET_h2s (&ctran->to_state->hash));
216  }
217  else
218  GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id);
219 
220  if (NULL == ctran->label)
221  {
222  if (GNUNET_YES == ctx->coloring)
223  {
224  GNUNET_asprintf (&s_tran,
225  "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
226  name, to_name, s->scc_id * s->scc_id);
227  }
228  else
229  {
230  GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
231  to_name, s->scc_id);
232  }
233  }
234  else
235  {
236  if (GNUNET_YES == ctx->coloring)
237  {
238  GNUNET_asprintf (&s_tran,
239  "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
240  name, to_name, ctran->label, s->scc_id * s->scc_id);
241  }
242  else
243  {
244  GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
245  to_name, ctran->label, s->scc_id);
246  }
247  }
248 
249  GNUNET_free (to_name);
250 
251  GNUNET_assert (NULL != s_tran);
252 
253  fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
254  GNUNET_free (s_tran);
255  s_tran = NULL;
256  }
257 
258  GNUNET_free (name);
259 }
260 
261 
270 void
272  const char *filename,
274 {
275  char *start;
276  char *end;
277  struct REGEX_TEST_Graph_Context ctx;
278 
279  if (NULL == a)
280  {
281  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
282  return;
283  }
284 
285  if ((NULL == filename) || (strlen (filename) < 1))
286  {
287  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
288  return;
289  }
290 
291  ctx.filep = fopen (filename, "w");
292  ctx.verbose =
293  (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
294  ctx.coloring =
295  (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;
296 
297  if (NULL == ctx.filep)
298  {
299  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
300  filename);
301  return;
302  }
303 
304  /* First add the SCCs to the automaton, so we can color them nicely */
305  if (GNUNET_YES == ctx.coloring)
306  scc_tarjan (a);
307 
308  start = "digraph G {\nrankdir=LR\n";
309  fwrite (start, strlen (start), 1, ctx.filep);
310 
311  REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL,
313  &ctx);
314 
315  end = "\n}\n";
316  fwrite (end, strlen (end), 1, ctx.filep);
317  fclose (ctx.filep);
318 }
unsigned int state_count
Number of states in the automaton.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
struct REGEX_INTERNAL_State * states_head
DLL of states.
FILE * filep
File pointer to the dot file used for output.
int index
Used for SCC detection.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
struct REGEX_INTERNAL_Transition * next
This is a linked list.
Context for graph creation.
struct GNUNET_HashCode hash
Hash of the state.
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
int accepting
If this is an accepting state or not.
The generated graph will include extra information such as the NFA states that were used to generate ...
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static void scc_tarjan_strongconnect(unsigned int *scc_counter, struct REGEX_INTERNAL_State *v, unsigned int *index, struct REGEX_INTERNAL_State **stack, unsigned int *stack_size)
Recursive function doing DFS with &#39;v&#39; as a start, detecting all SCCs inside the subgraph reachable fr...
int contained
Marking the state as contained.
#define GNUNET_NO
Definition: gnunet_common.h:78
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
Automaton representation.
static struct GNUNET_SCHEDULER_Task * t
Main task.
char * proof
Proof for this state.
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
REGEX_TEST_GraphSavingOptions
Options for graph creation function REGEX_TEST_automaton_save_graph.
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
int coloring
Coloring flag, if set to GNUNET_YES SCCs will be colored.
void REGEX_TEST_automaton_save_graph(struct REGEX_INTERNAL_Automaton *a, const char *filename, enum REGEX_TEST_GraphSavingOptions options)
Save the given automaton as a GraphViz dot file.
library to parse regular expressions into dfa
char * name
Human readable name of the state.
static char * filename
Transition between two states.
int verbose
Verbose flag, if it&#39;s set to GNUNET_YES additional info will be printed in the graph.
Enable graph coloring.
struct REGEX_INTERNAL_State * start
First state of the automaton.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
void REGEX_TEST_automaton_save_graph_step(void *cls, unsigned int count, struct REGEX_INTERNAL_State *s)
Save a state to an open file pointer.
library to read regexes representing IP networks from a file.
const char * name
static void scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
Detect all SCCs (Strongly Connected Components) inside the given automaton.
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
#define GNUNET_log(kind,...)
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
common internal definitions for regex library.
int lowlink
Used for SCC detection.
unsigned int id
Unique state id.
#define GNUNET_free(ptr)
Wrapper around free.