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  }
182  }
183  else if (GNUNET_YES == ctx->coloring)
184  {
185  GNUNET_asprintf (&s_acc,
186  "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
187  s->scc_id * s->scc_id);
188  }
189  else
190  {
191  GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name);
192  }
193 
194  GNUNET_assert (NULL != s_acc);
195 
196  fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
197  GNUNET_free (s_acc);
198  s_acc = NULL;
199 
200  for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
201  {
202  if (NULL == ctran->to_state)
203  {
205  "Transition from State %i has no state for transitioning\n",
206  s->id);
207  continue;
208  }
209 
210  if (GNUNET_YES == ctx->verbose)
211  {
212  GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
213  ctran->to_state->name, ctran->to_state->proof,
214  GNUNET_h2s (&ctran->to_state->hash));
215  }
216  else
217  GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id);
218 
219  if (NULL == ctran->label)
220  {
221  if (GNUNET_YES == ctx->coloring)
222  {
223  GNUNET_asprintf (&s_tran,
224  "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
225  name, to_name, s->scc_id * s->scc_id);
226  }
227  else
228  {
229  GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
230  to_name);
231  }
232  }
233  else
234  {
235  if (GNUNET_YES == ctx->coloring)
236  {
237  GNUNET_asprintf (&s_tran,
238  "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
239  name, to_name, ctran->label, s->scc_id * s->scc_id);
240  }
241  else
242  {
243  GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
244  to_name, ctran->label);
245  }
246  }
247 
248  GNUNET_free (to_name);
249 
250  GNUNET_assert (NULL != s_tran);
251 
252  fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
253  GNUNET_free (s_tran);
254  s_tran = NULL;
255  }
256 
257  GNUNET_free (name);
258 }
259 
260 
269 void
271  const char *filename,
273 {
274  char *start;
275  char *end;
277 
278  if (NULL == a)
279  {
280  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
281  return;
282  }
283 
284  if ((NULL == filename) || (strlen (filename) < 1))
285  {
286  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
287  return;
288  }
289 
290  ctx.filep = fopen (filename, "w");
291  ctx.verbose =
293  ctx.coloring =
295 
296  if (NULL == ctx.filep)
297  {
298  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
299  filename);
300  return;
301  }
302 
303  /* First add the SCCs to the automaton, so we can color them nicely */
304  if (GNUNET_YES == ctx.coloring)
305  scc_tarjan (a);
306 
307  start = "digraph G {\nrankdir=LR\n";
308  fwrite (start, strlen (start), 1, ctx.filep);
309 
310  REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL,
312  &ctx);
313 
314  end = "\n}\n";
315  fwrite (end, strlen (end), 1, ctx.filep);
316  fclose (ctx.filep);
317 }
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static char * filename
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
static struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_log(kind,...)
@ GNUNET_YES
Definition: gnunet_common.h:97
@ GNUNET_NO
Definition: gnunet_common.h:94
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_ERROR
int int GNUNET_asprintf(char **buf, const char *format,...) __attribute__((format(printf
Like asprintf, just portable.
#define GNUNET_free(ptr)
Wrapper around free.
const char * name
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,...
common internal definitions for regex library.
library to parse regular expressions into dfa
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.
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 'v' as a start, detecting all SCCs inside the subgraph reachable fr...
static void scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
Detect all SCCs (Strongly Connected Components) inside the given automaton.
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 read regexes representing IP networks from a file.
REGEX_TEST_GraphSavingOptions
Options for graph creation function REGEX_TEST_automaton_save_graph.
@ REGEX_TEST_GRAPH_COLORING
Enable graph coloring.
@ REGEX_TEST_GRAPH_VERBOSE
The generated graph will include extra information such as the NFA states that were used to generate ...
struct GNUNET_SCHEDULER_Task * next
This is a linked list.
Definition: scheduler.c:139
Automaton representation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
char * proof
Proof for this state.
unsigned int dfs_id
Linear state ID acquired by depth-first-search.
char * name
Human readable name of the state.
unsigned int id
Unique state id.
int accepting
If this is an accepting state or not.
int lowlink
Used for SCC detection.
int contained
Marking the state as contained.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct GNUNET_HashCode hash
Hash of the state.
int index
Used for SCC detection.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
char * label
Label for this transition.
Context for graph creation.
int verbose
Verbose flag, if it's set to GNUNET_YES additional info will be printed in the graph.
int coloring
Coloring flag, if set to GNUNET_YES SCCs will be colored.
FILE * filep
File pointer to the dot file used for output.