include/yaz/nfa.h

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