include/yaz/nfa.h

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *  $Id: nfa.h,v 1.3 2006-05-03 13:47:35 heikki Exp $
   4  */
   5
   6 /**
   7  * \file nfa.h
   8  * \brief NFA for character set normalizing
   9  *
  10  * The NFA is a character mathcing device. It consists of states
  11  * and transitions between them. Each transition has a condition, which
  12  * is a range of values.
  13  *
  14  * When matching, we always start at the first state, and find the longest
  15  * possible sequence of input characters that match the ranges in the
  16  * conditions, and that leads into a terminal state.
  17  *
  18  */
  19
  20 #ifndef NFA_H
  21 #define NFA_H
  22
  23 #include <yaz/yconfig.h>
  24
  25 YAZ_BEGIN_CDECL
  26
  27 /** \brief Internal character type */
  28 typedef unsigned int yaz_nfa_char;
  29
  30
  31 /** \brief The NFA itself
  32  * The internals are hidden in nfa.c */
  33 typedef struct yaz_nfa yaz_nfa;
  34
  35 /** \brief A state of the NFA  */
  36 typedef struct yaz_nfa_state yaz_nfa_state;
  37
  38 /** \brief Transition from one state to another */
  39 typedef struct yaz_nfa_transition yaz_nfa_transition;
  40
  41
  42 /** \brief Initialize the NFA without any states in it
  43  *
  44  * \return a pointer to the newly created NFA
  45  *
  46  * */
  47 yaz_nfa *yaz_nfa_init();
  48
  49 /** \brief Destroy the whole thing */
  50 void yaz_nfa_destroy(
  51           yaz_nfa *n  /** the nfa to destroy */
  52           );
  53
  54 /** \brief Add a normal state to the NFA.
  55  *
  56  * The first state added will become the starting point.
  57  * Returns a pointer to it, which you can safely ignore, or use in building
  58  * transitions.
  59  */
  60 yaz_nfa_state *yaz_nfa_add_state(
  61         yaz_nfa *n  /** The NFA to add the state to */
  62         );
  63
  64
  65 /** \brief Sets the result pointer to a state
  66  *
  67  *  Call with null to clear the pointer.
  68  *
  69  *  \retval  0 ok
  70  *  \retval  1 The state already has a result!
  71  */
  72 int yaz_nfa_set_result(
  73         /** The NFA itsef */
  74         yaz_nfa *n,
  75         /** The state to which the result is added */
  76         yaz_nfa_state *s,
  77         /** The result. The NFA does not care what it is, just stores it */
  78         void *result
  79         );
  80
  81 /**  \brief Gets the result pointer from a state
  82  *
  83  *   \retval NULL if no result set
  84  */
  85 void *yaz_nfa_get_result(
  86          yaz_nfa *n /** The NFA itself */,
  87          yaz_nfa_state *s /** The state whose result you want */);
  88
  89 /** \brief Set a backref point to a state.
  90  *
  91  *  Each state can be the beginning and/or ending point of a backref
  92  *  sequence. This call sets one of those flags in the state. After
  93  *  matching, we can get hold of the backrefs that matched, and use
  94  *  them in our translations. The numbering of backrefs start at 1,
  95  *  not zero!
  96  *
  97  *  \param n   the nfa
  98  *  \param s   the state to add to
  99  *  \param backref_number is the number of the back reference. 0 for clearing
 100  *  \param is_start is 1 for start of the backref, 0 for end
 101  *  \retval   0 for OK
 102  *  \retval   1 if the backref is already set
 103  *  \retval   2 for ending a backref that has not been started
 104  *
 105  */
 106
 107 int yaz_nfa_set_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 108         int backref_number,
 109         int is_start );
 110
 111 /** \brief Get the backref point of a state
 112  *
 113  *  \param n   the nfa
 114  *  \param s   the state to add to
 115  *  \param is_start is 1 for start of the backref, 0 for end
 116  *  \return the backref number associated with the state, or 0 if none.
 117  */
 118
 119 int yaz_nfa_get_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 120         int is_start );
 121
 122 /**  \brief Add a transition to the NFA.
 123  *
 124  *   Add a transition between two existing states. The condition
 125  *   is (as always) a range of yaz_nfa_chars.
 126  *  \param n   the nfa
 127  *  \param from_state  which state the transition is from
 128  *  \param to_state    where the transition goes to
 129  *  \param range_start is the beginning of the range of values
 130  *  \param range_end is the end of the range of values
 131  **/
 132 void yaz_nfa_add_transition(yaz_nfa *n,
 133             yaz_nfa_state *from_state,
 134             yaz_nfa_state *to_state,
 135             yaz_nfa_char range_start,
 136             yaz_nfa_char range_end);
 137
 138 /** \brief Add an empty (epsilon) transition.
 139  *
 140  *  \param n   the nfa
 141  *  \param from_state  which state the transition is from
 142  *  \param to_state    where the transition goes to
 143  **/
 144 void yaz_nfa_add_empty_transition( yaz_nfa *n,
 145                 yaz_nfa_state *from_state,
 146                 yaz_nfa_state *to_state);
 147
 148 /** \brief Add a translation from a range to the NFA.
 149  *
 150  *  \param n   the nfa
 151  *  \param st the state to add this to. If null, adds to the initial state
 152  *  \param range_start is the beginning of the range of values
 153  *  \param range_end is the end of the range of values
 154  *
 155  *  Checks if we already have a transition like this. If so, does not add
 156  *  a new one, but returns the target state. Otherwise creates a new state,
 157  *  and a transition to it.
 158  */
 159 yaz_nfa_state *yaz_nfa_add_range( yaz_nfa *n,
 160           yaz_nfa_state *st,
 161           yaz_nfa_char range_start,
 162           yaz_nfa_char range_end );
 163
 164 /** \brief Add a sequence of transitions and states.
 165  *
 166  *  Starting from state s (or from the initial state, if s is
 167  *  null), finds as much of seq as possible and inserts the rest.
 168  *  \Return the final state
 169  */
 170 yaz_nfa_state *yaz_nfa_add_sequence( yaz_nfa *n,
 171               yaz_nfa_state *s,
 172               yaz_nfa_char *seq );
 173
 174
 175 /** \brief Find the longest possible match.
 176  *
 177  *  \param n   the nfa itself
 178  *  \param inbuff  buffer of input data. Will be incremented when match
 179  *  \param incharsleft   max number of inchars to use from inbuff
 180  *  \param result   the result pointer from the nfa (what ever that is)
 181  *
 182  *  In case of errors, returns the best match so far,
 183  *  which the caller is free to ignore.
 184  *
 185  *  \retval 0 success
 186  *  \retval 1 no match found
 187  *  \retval 2 overrun'of input buffer
 188  *  \retval 3 looping too far
 189  *
 190  */
 191
 192 int yaz_nfa_match(yaz_nfa *n, yaz_nfa_char **inbuff, size_t incharsleft,
 193                 void **result );
 194
 195 #define YAZ_NFA_SUCCESS 0
 196 #define YAZ_NFA_NOMATCH 1
 197 #define YAZ_NFA_OVERRUN 2
 198 #define YAZ_NFA_LOOP 3
 199
 200 /** \brief Get a back reference after a successfull match.
 201  *
 202  *  \param n   the nfa
 203  *  \param backref_no  the number of the backref to get
 204  *  \param begin  beginning of the matching substring
 205  *  \param end    end of the matching substring
 206  *
 207  * Returns pointers to the beginning and end of a backref, or null
 208  * pointers if one endpoint not met.  Those pointers point to the
 209  * original buffer that was matched, so the caller will not have to
 210  * worry about freeing anything special.
 211  *
 212  * It is technically possible to create NFAs that meet the start but
 213  * not the end of a backref.  It is up to the caller to decide how
 214  * to handle such a situation.
 215  *
 216  * \retval 0 OK
 217  * \retval 1 no match
 218  * \retval 2 no such backref
 219  */
 220
 221 int yaz_nfa_get_backref( yaz_nfa *n,
 222         int backref_no,
 223         yaz_nfa_char **start,
 224         yaz_nfa_char **end );
 225
 226 /** \brief Get the first state of the NFA.
 227  *
 228  *  \param n   the nfa
 229  *
 230  *  Useful for iterating through all states, probably calling get_result
 231  *  for each, and doing something to the results (freeing memory?)
 232  *
 233  *  \returns a pointer to the first state, or NULL if none.
 234  */
 235 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n);
 236
 237 /** \brief Get the next state of the NFA.
 238  *
 239  *  \param n   the nfa
 240  *  \param s   the state to add to
 241  *  \return the next state, or NULL if no more.
 242  */
 243 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s);
 244
 245 /** \brief Dump the NFA into a file .
 246  *
 247  *  \param F   The file handle to dump into (null => stdout)
 248  *  \param n   the nfa
 249  *  \param strfunc can be used for converting the resultinfo a string.
 250  *
 251  *  strfunc is a function like
 252  *     char *f( void *result);
 253  *  it takes the result, and converts into a printable string (which
 254  *  must be allocated somewhere by the caller). If the results are
 255  *  already printable, passing a null pointer here prints them with a %s
 256  *
 257  */
 258 void yaz_nfa_dump(FILE *F, yaz_nfa *n, char *(*strfunc)(void *) );
 259
 260
 261 YAZ_END_CDECL
 262
 263 #endif