src/include/gnunet_regex_lib.h

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      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      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file include/gnunet_regex_lib.h
  22  * @brief library to parse regular expressions into dfa
  23  * @author Maximilian Szengel
  24  *
  25  */
  26
  27 #ifndef GNUNET_REGEX_LIB_H
  28 #define GNUNET_REGEX_LIB_H
  29
  30 #include "gnunet_util_lib.h"
  31 #include "gnunet_dht_service.h"
  32 #include "gnunet_statistics_service.h"
  33
  34 #ifdef __cplusplus
  35 extern "C"
  36 {
  37 #if 0                           /* keep Emacsens' auto-indent happy */
  38 }
  39 #endif
  40 #endif
  41
  42
  43 /**
  44  * Constant for how many bytes the initial string regex should have.
  45  */
  46 #define GNUNET_REGEX_INITIAL_BYTES 24
  47
  48
  49 /**
  50  * Maximum regex string length for use with GNUNET_REGEX_ipv4toregex
  51  */
  52 #define GNUNET_REGEX_IPV4_REGEXLEN 32 + 6
  53
  54
  55 /**
  56  * Maximum regex string length for use with GNUNET_REGEX_ipv6toregex
  57  */
  58 #define GNUNET_REGEX_IPV6_REGEXLEN 128 + 6
  59
  60
  61 /**
  62  * Automaton (NFA/DFA) representation.
  63  */
  64 struct GNUNET_REGEX_Automaton;
  65
  66
  67 /**
  68  * Edge representation.
  69  */
  70 struct GNUNET_REGEX_Edge
  71 {
  72   /**
  73    * Label of the edge.  FIXME: might want to not consume exactly multiples of 8 bits, need length?
  74    */
  75   const char *label;
  76
  77   /**
  78    * Destionation of the edge.
  79    */
  80   struct GNUNET_HashCode destination;
  81 };
  82
  83
  84 /**
  85  * Construct DFA for the given 'regex' of length 'len'.
  86  *
  87  * Path compression means, that for example a DFA o -> a -> b -> c -> o will be
  88  * compressed to o -> abc -> o. Note that this parameter influences the
  89  * non-determinism of states of the resulting NFA in the DHT (number of outgoing
  90  * edges with the same label). For example for an application that stores IPv4
  91  * addresses as bitstrings it could make sense to limit the path compression to
  92  * 4 or 8.
  93  *
  94  * @param regex regular expression string.
  95  * @param len length of the regular expression.
  96  * @param max_path_len limit the path compression length to the
  97  *        given value. If set to 1, no path compression is applied. Set to 0 for
  98  *        maximal possible path compression (generally not desireable).
  99  * @return DFA, needs to be freed using GNUNET_REGEX_automaton_destroy.
 100  */
 101 struct GNUNET_REGEX_Automaton *
 102 GNUNET_REGEX_construct_dfa (const char *regex, const size_t len,
 103                             unsigned int max_path_len);
 104
 105
 106 /**
 107  * Free the memory allocated by constructing the GNUNET_REGEX_Automaton.
 108  * data structure.
 109  *
 110  * @param a automaton to be destroyed.
 111  */
 112 void
 113 GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a);
 114
 115
 116 /**
 117  * Options for graph creation function
 118  * GNUNET_REGEX_automaton_save_graph.
 119  */
 120 enum GNUNET_REGEX_GraphSavingOptions
 121 {
 122   /**
 123    * Default. Do nothing special.
 124    */
 125   GNUNET_REGEX_GRAPH_DEFAULT = 0,
 126
 127   /**
 128    * The generated graph will include extra information such as the NFA states
 129    * that were used to generate the DFA state.
 130    */
 131   GNUNET_REGEX_GRAPH_VERBOSE = 1,
 132
 133   /**
 134    * Enable graph coloring. Will color each SCC in a different color.
 135    */
 136   GNUNET_REGEX_GRAPH_COLORING = 2
 137 };
 138
 139
 140 /**
 141  * Save the given automaton as a GraphViz dot file.
 142  *
 143  * @param a the automaton to be saved.
 144  * @param filename where to save the file.
 145  * @param options options for graph generation that include coloring or verbose
 146  *                mode
 147  */
 148 void
 149 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
 150                                    const char *filename,
 151                                    enum GNUNET_REGEX_GraphSavingOptions options);
 152
 153
 154 /**
 155  * Evaluates the given 'string' against the given compiled regex.
 156  *
 157  * @param a automaton.
 158  * @param string string to check.
 159  *
 160  * @return 0 if string matches, non 0 otherwise.
 161  */
 162 int
 163 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a,
 164                    const char *string);
 165
 166
 167 /**
 168  * Get the first key for the given 'input_string'. This hashes
 169  * the first x bits of the 'input_string'.
 170  *
 171  * @param input_string string.
 172  * @param string_len length of the 'input_string'.
 173  * @param key pointer to where to write the hash code.
 174  *
 175  * @return number of bits of 'input_string' that have been consumed
 176  *         to construct the key
 177  */
 178 size_t
 179 GNUNET_REGEX_get_first_key (const char *input_string, size_t string_len,
 180                             struct GNUNET_HashCode * key);
 181
 182
 183 /**
 184  * Check if the given 'proof' matches the given 'key'.
 185  *
 186  * @param proof partial regex of a state.
 187  * @param key hash of a state.
 188  *
 189  * @return GNUNET_OK if the proof is valid for the given key.
 190  */
 191 int
 192 GNUNET_REGEX_check_proof (const char *proof,
 193                           const struct GNUNET_HashCode *key);
 194
 195
 196 /**
 197  * Iterator callback function.
 198  *
 199  * @param cls closure.
 200  * @param key hash for current state.
 201  * @param proof proof for current state.
 202  * @param accepting GNUNET_YES if this is an accepting state, GNUNET_NO if not.
 203  * @param num_edges number of edges leaving current state.
 204  * @param edges edges leaving current state.
 205  */
 206 typedef void (*GNUNET_REGEX_KeyIterator)(void *cls,
 207                                          const struct GNUNET_HashCode *key,
 208                                          const char *proof,
 209                                          int accepting,
 210                                          unsigned int num_edges,
 211                                          const struct GNUNET_REGEX_Edge *edges);
 212
 213
 214 /**
 215  * Iterate over all edges starting from start state of automaton 'a'. Calling
 216  * iterator for each edge.
 217  *
 218  * @param a automaton.
 219  * @param iterator iterator called for each edge.
 220  * @param iterator_cls closure.
 221  */
 222 void
 223 GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
 224                                 GNUNET_REGEX_KeyIterator iterator,
 225                                 void *iterator_cls);
 226
 227
 228 /**
 229  * Create a regex in 'rxstr' from the given 'ip' and 'netmask'.
 230  *
 231  * @param ip IPv4 representation.
 232  * @param netmask netmask for the ip.
 233  * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV4_REGEXLEN
 234  *              bytes long.
 235  */
 236 void
 237 GNUNET_REGEX_ipv4toregex (const struct in_addr *ip, const char *netmask,
 238                           char *rxstr);
 239
 240
 241 /**
 242  * Create a regex in 'rxstr' from the given 'ipv6' and 'prefixlen'.
 243  *
 244  * @param ipv6 IPv6 representation.
 245  * @param prefixlen length of the ipv6 prefix.
 246  * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV6_REGEXLEN
 247  *              bytes long.
 248  */
 249 void
 250 GNUNET_REGEX_ipv6toregex (const struct in6_addr *ipv6,
 251                           unsigned int prefixlen, char *rxstr);
 252
 253
 254
 255 /**
 256  * Handle to store cached data about a regex announce.
 257  */
 258 struct GNUNET_REGEX_announce_handle;
 259
 260 /**
 261  * Handle to store data about a regex search.
 262  */
 263 struct GNUNET_REGEX_search_handle;
 264
 265 /**
 266  * Announce a regular expression: put all states of the automaton in the DHT.
 267  * Does not free resources, must call GNUNET_REGEX_announce_cancel for that.
 268  *
 269  * @param dht An existing and valid DHT service handle.
 270  * @param id ID to announce as provider of regex. Own ID in most cases.
 271  * @param regex Regular expression to announce.
 272  * @param compression How many characters per edge can we squeeze?
 273  * @param stats Optional statistics handle to report usage. Can be NULL.
 274  *
 275  * @return Handle to reuse o free cached resources.
 276  *         Must be freed by calling GNUNET_REGEX_announce_cancel.
 277  */
 278 struct GNUNET_REGEX_announce_handle *
 279 GNUNET_REGEX_announce (struct GNUNET_DHT_Handle *dht,
 280                        struct GNUNET_PeerIdentity *id,
 281                        const char *regex,
 282                        uint16_t compression,
 283                        struct GNUNET_STATISTICS_Handle *stats);
 284
 285 /**
 286  * Announce again a regular expression previously announced.
 287  * Does use caching to speed up process.
 288  *
 289  * @param h Handle returned by a previous GNUNET_REGEX_announce call.
 290  */
 291 void
 292 GNUNET_REGEX_reannounce (struct GNUNET_REGEX_announce_handle *h);
 293
 294
 295 /**
 296  * Clear all cached data used by a regex announce.
 297  * Does not close DHT connection.
 298  *
 299  * @param h Handle returned by a previous GNUNET_REGEX_announce call.
 300  */
 301 void
 302 GNUNET_REGEX_announce_cancel (struct GNUNET_REGEX_announce_handle *h);
 303
 304
 305 /**
 306  * Search callback function.
 307  *
 308  * @param cls Closure provided in GNUNET_REGEX_search.
 309  * @param id Peer providing a regex that matches the string.
 310  * @param get_path Path of the get request.
 311  * @param get_path_length Lenght of get_path.
 312  * @param put_path Path of the put request.
 313  * @param put_path_length Length of the put_path.
 314  */
 315 typedef void (*GNUNET_REGEX_Found)(void *cls,
 316                                    const struct GNUNET_PeerIdentity *id,
 317                                    const struct GNUNET_PeerIdentity *get_path,
 318                                    unsigned int get_path_length,
 319                                    const struct GNUNET_PeerIdentity *put_path,
 320                                    unsigned int put_path_length);
 321
 322
 323 /**
 324  * Search for a peer offering a regex matching certain string in the DHT.
 325  * The search runs until GNUNET_REGEX_search_cancel is called, even if results
 326  * are returned.
 327  *
 328  * @param dht An existing and valid DHT service handle.
 329  * @param string String to match against the regexes in the DHT.
 330  * @param callback Callback for found peers.
 331  * @param callback_cls Closure for @c callback.
 332  * @param stats Optional statistics handle to report usage. Can be NULL.
 333  *
 334  * @return Handle to stop search and free resources.
 335  *         Must be freed by calling GNUNET_REGEX_search_cancel.
 336  */
 337 struct GNUNET_REGEX_search_handle *
 338 GNUNET_REGEX_search (struct GNUNET_DHT_Handle *dht,
 339                      const char *string,
 340                      GNUNET_REGEX_Found callback,
 341                      void *callback_cls,
 342                      struct GNUNET_STATISTICS_Handle *stats);
 343
 344 /**
 345  * Stop search and free all data used by a GNUNET_REGEX_search call.
 346  * Does not close DHT connection.
 347  *
 348  * @param h Handle returned by a previous GNUNET_REGEX_search call.
 349  */
 350 void
 351 GNUNET_REGEX_search_cancel (struct GNUNET_REGEX_search_handle *h);
 352
 353
 354 #if 0                           /* keep Emacsens' auto-indent happy */
 355 {
 356 #endif
 357 #ifdef __cplusplus
 358 }
 359 #endif
 360
 361 /* end of gnunet_regex_lib.h */
 362 #endif