include/yaz/nfa.h

   1 /*  Copyright (C) 2006, Index Data ApS
   2  *  See the file LICENSE for details.
   3  *  $Id: nfa.h,v 1.7 2006-05-10 13:58:46 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  * Separate from this we have converters. Those can often be used
  19  * together with a NFA (think match-pattern and replace-pattern).
  20  *
  21  * A converter is a routine that produces some output. It can translate a
  22  * range of characters into another range, emit a constant string, or
  23  * something like that.
  24  *
  25  */
  26
  27 #ifndef YAZ_NFA_H
  28 #define YAZ_NFA_H
  29
  30 #include <yaz/yconfig.h>
  31
  32 YAZ_BEGIN_CDECL
  33
  34 /** \name return codes and data types*/
  35 /* \{ */
  36 /** \brief Success */
  37 #define YAZ_NFA_SUCCESS 0
  38
  39 /** \brief no match found */
  40 #define YAZ_NFA_NOMATCH 1
  41
  42 /** \brief Need more input */
  43 #define YAZ_NFA_OVERRUN 2
  44
  45 /** \brief The NFA is looping */
  46 #define YAZ_NFA_LOOP 3
  47
  48 /** \brief no room in output buffer */
  49 #define YAZ_NFA_NOSPACE 4
  50
  51 /** \brief tryig to set a result when one already exists*/
  52 #define YAZ_NFA_ALREADY 5
  53
  54 /** \brief Attempting to set an end to a backref that has not been started */
  55 #define YAZ_NFA_NOSTART 6
  56
  57 /** \brief Asking for a non-existing backref */
  58 #define YAZ_NFA_NOSUCHBACKREF 7
  59
  60 /** \brief Internal error, should never happen */
  61 #define YAZ_NFA_INTERNAL 8
  62
  63
  64 /** \brief Internal character type. 32-bit unicode! */
  65 typedef unsigned int yaz_nfa_char;
  66
  67
  68 /** \brief The NFA itself
  69  * The internals are hidden in nfa.c */
  70 typedef struct yaz_nfa yaz_nfa;
  71
  72 /** \brief A state of the NFA  */
  73 typedef struct yaz_nfa_state yaz_nfa_state;
  74
  75 /** \brief Transition from one state to another */
  76 typedef struct yaz_nfa_transition yaz_nfa_transition;
  77
  78 /** \brief  A converter produces some output to a buffer */
  79 typedef struct yaz_nfa_converter yaz_nfa_converter;
  80
  81 /* \} */
  82
  83 /** \name Low-level interface to building the NFA */
  84 /* \{ */
  85
  86 /** \brief Initialize the NFA without any states in it
  87  *
  88  * \return a pointer to the newly created NFA
  89  *
  90  * */
  91 yaz_nfa *yaz_nfa_init();
  92
  93 /** \brief Destroy the whole thing */
  94 void yaz_nfa_destroy(
  95           yaz_nfa *n  /** the nfa to destroy */
  96           );
  97
  98 /** \brief Add a normal state to the NFA.
  99  *
 100  * The first state added will become the starting point.
 101  * Returns a pointer to it, which you can safely ignore, or use in building
 102  * transitions.
 103  */
 104 yaz_nfa_state *yaz_nfa_add_state(
 105         yaz_nfa *n  /** The NFA to add the state to */
 106         );
 107
 108
 109 /** \brief Sets the result pointer to a state
 110  *
 111  * \param n       the NFA itself
 112  * \param s       the state to which the result will be added
 113  * \param result  the result pointer
 114  *
 115  * Sets the result pointer of a state. If already set, returns an error. Call
 116  * with a NULL pointer to clear the result, before setting a new one.
 117  *
 118  *  \retval  YAZ_NFA_SUCCESS  ok
 119  *  \retval  YAZ_NFA_ALREADY The state already has a result!
 120  */
 121 int yaz_nfa_set_result(
 122         yaz_nfa *n,
 123         yaz_nfa_state *s,
 124         void *result
 125         );
 126
 127 /**  \brief Gets the result pointer from a state
 128  *
 129  *   \retval NULL if no result set
 130  */
 131 void *yaz_nfa_get_result(
 132          yaz_nfa *n /** The NFA itself */,
 133          yaz_nfa_state *s /** The state whose result you want */);
 134
 135 /** \brief Set a backref point to a state.
 136  *
 137  *  Each state can be the beginning and/or ending point of a backref
 138  *  sequence. This call sets one of those flags in the state. After
 139  *  matching, we can get hold of the backrefs that matched, and use
 140  *  them in our translations. The numbering of backrefs start at 1,
 141  *  not zero!
 142  *
 143  *  \param n   the nfa
 144  *  \param s   the state to add to
 145  *  \param backref_number is the number of the back reference.
 146  *  \param is_start is 1 for start of the backref, 0 for end
 147  *
 148  *  \retval   YAZ_NFA_SUCCESS for OK
 149  *  \retval   YAZ_NFA_ALREADY if the backref is already set
 150  *  \retval   YAZ_NFA_NOSTART for ending a backref that has not been started
 151  *
 152  */
 153
 154 int yaz_nfa_set_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 155         int backref_number,
 156         int is_start );
 157
 158 /** \brief Get the backref point of a state
 159  *
 160  *  \param n   the nfa
 161  *  \param s   the state to add to
 162  *  \param is_start is 1 for start of the backref, 0 for end
 163  *  \return the backref number associated with the state, or 0 if none.
 164  */
 165
 166 int yaz_nfa_get_backref_point(yaz_nfa *n, yaz_nfa_state *s,
 167         int is_start );
 168
 169 /**  \brief Add a transition to the NFA.
 170  *
 171  *   Add a transition between two existing states. The condition
 172  *   is (as always) a range of yaz_nfa_chars.
 173  *  \param n   the nfa
 174  *  \param from_state  which state the transition is from. null=initial
 175  *  \param to_state    where the transition goes to
 176  *  \param range_start is the beginning of the range of values
 177  *  \param range_end is the end of the range of values
 178  **/
 179 void yaz_nfa_add_transition(yaz_nfa *n,
 180             yaz_nfa_state *from_state,
 181             yaz_nfa_state *to_state,
 182             yaz_nfa_char range_start,
 183             yaz_nfa_char range_end);
 184
 185 /** \brief Add an empty (epsilon) transition.
 186  *
 187  *  \param n   the nfa
 188  *  \param from_state  which state the transition is from
 189  *  \param to_state    where the transition goes to
 190  **/
 191 void yaz_nfa_add_empty_transition( yaz_nfa *n,
 192                 yaz_nfa_state *from_state,
 193                 yaz_nfa_state *to_state);
 194
 195 /** \brief Add a translation from a range to the NFA.
 196  *
 197  *  \param n   the nfa
 198  *  \param st the state to add this to. If null, adds to the initial state
 199  *  \param range_start is the beginning of the range of values
 200  *  \param range_end is the end of the range of values
 201  *
 202  *  Checks if we already have a transition like this. If so, does not add
 203  *  a new one, but returns the target state. Otherwise creates a new state,
 204  *  and a transition to it.
 205  */
 206 yaz_nfa_state *yaz_nfa_add_range( yaz_nfa *n,
 207           yaz_nfa_state *st,
 208           yaz_nfa_char range_start,
 209           yaz_nfa_char range_end );
 210
 211 /** \brief Add a sequence of transitions and states.
 212  *
 213  *  \param n   the nfa
 214  *  \param s   the state to add this to. If null, adds to the initial state
 215  *  \param seq is a sequence of yaz_fna_chars.
 216  *  \param seq_len is the length of the sequence
 217  *  \Return the final state
 218  *
 219  *  Starting from state s (or from the initial state, if s is
 220  *  null), finds as much of seq as possible and inserts the rest.
 221  */
 222 yaz_nfa_state *yaz_nfa_add_sequence( yaz_nfa *n,
 223               yaz_nfa_state *s,
 224               yaz_nfa_char *seq,
 225               size_t seq_len );
 226
 227 /** \} */
 228
 229 /** \name Low-level interface for mathcing the NFA. */
 230 /*
 231  *  These do the actual matching. They know nothing of
 232  *  the type of the result pointers
 233  */
 234 /** \{ */
 235
 236 /** \brief Find the longest possible match.
 237  *
 238  *  \param n   the nfa itself
 239  *  \param inbuff  buffer of input data. Will be incremented when match
 240  *  \param incharsleft   max number of inchars to use from inbuff. decrements.
 241  *  \param result   the result pointer from the nfa (what ever that is)
 242  *
 243  *  In case of errors, returns the best match so far,
 244  *  which the caller is free to ignore.
 245  *
 246  *  \retval YAZ_NFA_SUCCESS success
 247  *  \retval YAZ_NFA_NOMATCH no match found
 248  *  \retval YAZ_NFA_OVERRUN overrun of input buffer
 249  *  \retval YAZ_NFA_LOOP looping too far
 250  *
 251  */
 252
 253 int yaz_nfa_match(yaz_nfa *n, yaz_nfa_char **inbuff, size_t *incharsleft,
 254                 void **result );
 255
 256 /** \brief Get a back reference after a successfull match.
 257  *
 258  *  \param n   the nfa
 259  *  \param backref_no  the number of the backref to get
 260  *  \param start  beginning of the matching substring
 261  *  \param end    end of the matching substring
 262  *
 263  * Returns pointers to the beginning and end of a backref, or null
 264  * pointers if one endpoint not met.  Those pointers point to the
 265  * original buffer that was matched, so the caller will not have to
 266  * worry about freeing anything special.
 267  *
 268  * It is technically possible to create NFAs that meet the start but
 269  * not the end of a backref.  It is up to the caller to decide how
 270  * to handle such a situation.
 271  *
 272  * \retval YAZ_NFA_SUCCESS  OK
 273  * \retval YAZ_NFA_NOMATCH  The NFA hasn't matched anything, no backref
 274  * \retval YAZ_NFA_NOSUCHBACKREF  no such backref
 275  */
 276
 277 int yaz_nfa_get_backref( yaz_nfa *n,
 278         int backref_no,
 279         yaz_nfa_char **start,
 280         yaz_nfa_char **end );
 281
 282 /* \} */
 283
 284 /** \name Low-level interface to the converters */
 285 /*  These produce some output text into a buffer. There are a few
 286  *  kinds of converters, each producing different type of output.
 287  */
 288 /* \{ */
 289
 290 /** \brief Create a string converter.
 291  * \param n  the nfa
 292  * \param string the string to output
 293  * \param length how many chars in the string
 294  *
 295  * This converter produces a constant string in the output
 296  */
 297 yaz_nfa_converter *yaz_nfa_create_string_converter (
 298         yaz_nfa *n,
 299         yaz_nfa_char *string,
 300         size_t length );
 301
 302 /** \brief Create a backref converter
 303  * \param n  the nfa
 304  * \param backref_no   The backreference to reproduce
 305  *
 306  * This converter copies a backref into the output buffer
 307  */
 308 yaz_nfa_converter *yaz_nfa_create_backref_converter (
 309         yaz_nfa *n, int backref_no );
 310
 311
 312 /** \brief Create a charcater range converter
 313  * \param n  the nfa
 314  * \param backref_no   The backreference to reproduce
 315  * \param from_char    the first character of the original range
 316  * \param to_char      the first character of the target range
 317  *
 318  * This converter takes a backreference, and shifts the characters
 319  * by a constant value. For example, translating a-z to A-Z.
 320  * Note that backref 0 is always the last character that matched a
 321  * range, even if no backrefs were defined in teh nfa. This makes
 322  * it pretty useful with this converter.
 323  *
 324  */
 325 yaz_nfa_converter *yaz_nfa_create_range_converter (
 326         yaz_nfa *n, int backref_no,
 327         yaz_nfa_char from_char,
 328         yaz_nfa_char to_char);
 329
 330
 331 /** \brief Connects converters in a chain.
 332  * \param n  the nfa (mostly for nmem access)
 333  * \param startpoint the first converter in the chain
 334  * \param newconverter
 335  *
 336  * Places the new converter at the end of the chain that starts from
 337  * startpoint.
 338  *
 339  */
 340 void yaz_nfa_append_converter (
 341         yaz_nfa *n,
 342         yaz_nfa_converter *startpoint,
 343         yaz_nfa_converter *newconverter);
 344
 345 /** brief Runs the chain of converters.
 346  * \param n  the nfa (mostly for nmem access)
 347  * \param c  the first converter in a chain
 348  * \param outbuff  buffer to write the output in. Increments the ptr.
 349  * \param outcharsleft how many may we write
 350  *
 351  * Runs the converters in the chain, placing output into outbuff
 352  * (and incrementing the pointer).
 353  *
 354  * \retval YAZ_NFA_SUCCESS OK
 355  * \retval YAZ_NFA_NOMATCH no match to get backrefs from
 356  * \retval YAZ_NFA_NOSPACE no room in outbuf
 357  * \retval YAZ_NFA_INTERNAL Should never happen
 358  *
 359  */
 360 int yaz_nfa_run_converters(
 361         yaz_nfa *n,
 362         yaz_nfa_converter *c,
 363         yaz_nfa_char **outbuff,
 364         size_t *outcharsleft);
 365
 366 /** \} */
 367
 368 /** \name  High-level interface to the NFA */
 369 /*  This interface combines the NFA and converters, for ease of
 370  *  access. There are a few calls to build a complete system, and a call
 371  *  to do the actual conversion.
 372  */
 373 /* \{ */
 374
 375 /** \brief Add a rule that converts one string to another  ('IX' -> '9')
 376  *
 377  *  \param n             The nfa itself
 378  *  \param from_string   the string to match
 379  *  \param from_length   length of the from_string
 380  *  \param to_string     the string to write in the output
 381  *  \param to_length     length of the to_string
 382  *
 383  *  Adds a matching rule and a string converter to the NFA.
 384  *  Can be used for converting strings into nothing, for example,
 385  *  to remove markup.
 386  *
 387  *  \retval YAZ_NFA_SUCCESS OK
 388  *  \retval YAZ_NFA_ALREADY Conflict with some other rule
 389  *
 390  */
 391 int yaz_nfa_add_string_rule( yaz_nfa *n,
 392                 yaz_nfa_char *from_string,
 393                 size_t from_length,
 394                 yaz_nfa_char *to_string,
 395                 size_t to_length);
 396
 397 /** brief Just like yaz_nfa_add_string_rule, but takes the strings in ascii
 398  *
 399  *  \param n             The nfa itself
 400  *  \param from_string   the string to match
 401  *  \param to_string     the string to write in the output
 402  *
 403  *  Like yaz_nfa_add_string_rule, this adds a rule to translate a string
 404  *  into another. The only difference is that this one takes the strings as
 405  *  normal char *, which means that no high-valued unicodes can be handled,
 406  *  and that this one uses null-terminated strings. In short, this is a
 407  *  simplified version mostly intended for tests and other small uses.
 408  *
 409  *  \retval YAZ_NFA_SUCCESS OK
 410  *  \retval YAZ_NFA_ALREADY Conflict with some other rule
 411  */
 412 int yaz_nfa_add_ascii_string_rule( yaz_nfa *n,
 413                 char *from_string,
 414                 char *to_string);
 415
 416
 417 /** \brief Add a rule that converts a character range
 418  *
 419  *  \param n             The nfa itself
 420  *  \param range_start   Where the matching range starts
 421  *  \param range_end     Where the matching range ends
 422  *  \param output_range_start Where the resulting range starts
 423  *
 424  *
 425  *  Adds a character range rule to the NFA. The range to be converted
 426  *  is defined by the range_start and range_end parameters. The output
 427  *  range starts at output_range_start, and is automatically as long
 428  *  as the input range.
 429  *
 430  *  Useful for alphabet normalizing [a-z] -> [A-Z]
 431  *
 432  *  \retval YAZ_NFA_SUCCESS OK
 433  *  \retval YAZ_NFA_ALREADY Conflict with some other rule
 434  */
 435 int yaz_nfa_add_char_range_rule (yaz_nfa *n,
 436                 yaz_nfa_char range_start,
 437                 yaz_nfa_char range_end,
 438                 yaz_nfa_char output_range_start);
 439
 440 /** \brief Add a rule that converts a character range to a string
 441  *
 442  *  \param n             The nfa itself
 443  *  \param range_start   Where the matching range starts
 444  *  \param range_end     Where the matching range ends
 445  *  \param to_string     the string to write in the output
 446  *  \param to_length     length of the to_string
 447  *
 448  *  \retval YAZ_NFA_SUCCESS OK
 449  *  \retval YAZ_NFA_ALREADY Conflict with some other rule
 450  *
 451  *  Adds a character range match rule, and a string converter.
 452  *
 453  *  Useful in converting a range of special characters into (short?)
 454  *  strings of whitespace, or even to nothing at all.
 455  */
 456 int yaz_nfa_add_char_string_rule (yaz_nfa *n,
 457                 yaz_nfa_char range_start,
 458                 yaz_nfa_char range_end,
 459                 yaz_nfa_char* to_string,
 460                 size_t to_length);
 461
 462 /** \brief Converts one 'slice' that is, the best matching rule.
 463  *
 464  *  \param n   the nfa itself
 465  *  \param inbuff  buffer of input data. Will be incremented when match
 466  *  \param incharsleft   max number of inchars to use from inbuff. decrements.
 467  *  \param outbuff  buffer for output data. Will be incremented when match
 468  *  \param outcharsleft   max number of chars to write to outbuff.
 469  *
 470  *  \retval YAZ_NFA_SUCCESS    OK
 471  *  \retval YAZ_NFA_OVERRUN    No more input data, some pattern could match
 472  *  \retval YAZ_NFA_NOSPACE    No room in the putput buffer
 473  *  \retval YAZ_NFA_NOSUCHBACKREF  NFA refers to a non-existing backref
 474  *
 475  * Finds the best match at the beginning of inbuf, and fires its converter(s)
 476  * to produce output in outbuff. Increments both inbuf and outbuf pointers and
 477  * decrements the *charsleft values, so all is ready for calling again, until
 478  * the buffer is exhausted. That loop is left to the caller, so he can load
 479  * more data in the buffer in good time.
 480  *
 481  * If no match is found, converts one character into itself. If the matcher
 482  * returns any sort of error, leaves the pointers where they were.
 483  */
 484 int yaz_nfa_convert_slice (yaz_nfa *n,
 485                 yaz_nfa_char **inbuff,
 486                 size_t *incharsleft,
 487                 yaz_nfa_char **outbuff,
 488                 size_t *outcharsleft);
 489
 490
 491 /* \} */
 492
 493 /** \name  Debug routines */
 494 /* These provide a method for traversing all the states defined
 495  * in the NFA, for example to release memory allocated in the results,
 496  * and a simple debug routine to dump the NFA */
 497 /* \{ */
 498
 499
 500 /** \brief Get the first state of the NFA.
 501  *
 502  *  \param n   the nfa
 503  *
 504  *  Useful for iterating through all states, probably calling get_result
 505  *  for each, and doing something to the results (freeing memory?)
 506  *
 507  *  \returns a pointer to the first state, or NULL if none.
 508  */
 509 yaz_nfa_state *yaz_nfa_get_first(yaz_nfa *n);
 510
 511 /** \brief Get the next state of the NFA.
 512  *
 513  *  \param n   the nfa
 514  *  \param s   the state to add to
 515  *  \return the next state, or NULL if no more.
 516  */
 517 yaz_nfa_state *yaz_nfa_get_next(yaz_nfa *n, yaz_nfa_state *s);
 518
 519 /** \brief Dump the NFA into a file .
 520  *
 521  *  \param F   The file handle to dump into (null => stdout)
 522  *  \param n   the nfa
 523  *  \param strfunc can be used for converting the resultinfo a string.
 524  *
 525  *  strfunc is a function like
 526  *     char *f( void *result);
 527  *  it takes the result, and converts into a printable string (which
 528  *  must be allocated somewhere by the caller). If the results are
 529  *  already printable, passing a null pointer here prints them with a %s
 530  *
 531  */
 532 void yaz_nfa_dump(FILE *F, yaz_nfa *n, char *(*strfunc)(void *) );
 533
 534 /* \} */
 535
 536
 537
 538 YAZ_END_CDECL
 539
 540 #endif