include/yaz/nfa.h

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *  $Id: nfa.h,v 1.1 2006-05-03 09:04:33 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 the backref number to a state.
  90  *
  91  *  Each state can be the beginning and/or ending of a backref
  92  *  sequence. This call sets those flags in the states. After matching,
  93  *  we can get hold of the backrefs that matched, and use them in our
  94  *  translations.
  95  *
  96  *  \param n   the nfa
  97  *  \param s   the state to add to
  98  *  \param backref_number is the number of the back reference. 0 for clearing
  99  *  \param is_start is 1 for start of the backref, 0 for end
 100  *  \return
 101  *     0 for OK
 102  *     1 if the backref is already set
 103  *
 104  *
 105  */
 106
 107 int yaz_nfa_set_backref(yaz_nfa *n, yaz_nfa_state *s,
 108         int backref_number,
 109         int is_start );
 110
 111 /** \brief Get the backref number 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(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
 201 /** \brief Get the first state of the NFA.
 202  *
 203  *  \param n   the nfa
 204  *
 205  *  Useful for iterating through all states, probably calling get_result
 206  *  for each, and doing something to the results (freeing memory?)
 207  *
 208  *  \returns a pointer to the first state, or NULL if none.
 209  */
 210 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n);
 211
 212 /** \brief Get the next state of the NFA.
 213  *
 214  *  \param n   the nfa
 215  *  \param s   the state to add to
 216  *  \return the next state, or NULL if no more.
 217  */
 218 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s);
 219
 220 /** \brief Dump the NFA into a file .
 221  *
 222  *  \param F   The file handle to dump into (null => stdout)
 223  *  \param n   the nfa
 224  *  \param strfunc can be used for converting the resultinfo a string.
 225  *
 226  *  strfunc is a function like
 227  *     char *f( void *result);
 228  *  it takes the result, and converts into a printable string (which
 229  *  must be allocated somewhere by the caller). If the results are
 230  *  already printable, passing a null pointer here prints them with a %s
 231  *
 232  */
 233 void yaz_nfa_dump(FILE *F, yaz_nfa *n, char *(*strfunc)(void *) );
 234
 235
 236 YAZ_END_CDECL
 237
 238 #endif