hackerlab/rx/dfa-utf16.c

/* dfa-utf16.c - utf16 functions that manipulate regexps as DFAs
 *
 ****************************************************************
 * Copyright (C) 1998, 2000 Thomas Lord
 *
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */


#include "hackerlab/bugs/panic.h"
#include "hackerlab/rx/escape.h"
#include "hackerlab/rx/super.h"
#include "hackerlab/rx/dfa-utf16.h"


/************************************************************************
 *(h0 "DFA String Comparisons for 16-bit Character Storage Units"
 *    :includes ("rx/dfa.h"
 *		 "rx/dfa_utf16.h"))
 *
 *
 * A common use for regular expressions is to compile them to DFA and
 * compare them to strings using a loop that advances through DFA
 * states.
 *
 * In Rx, the DFA data structure has been heavily optimized for such
 * loops.  The functions in this chapter implement the most common
 * kinds of DFA loop, taking full advantage of the Rx optimizations.
 */
/*(menu)
 */

/************************************************************************
 *(h1 "DFA Comparison Functions for 16-bit Character Storage Units")
 *
 * The functions in this section compare an input string to a regular
 * expression by advancing through DFA states according to the
 * characters in the input string.
 */


/*(c rx_dfa_utf16_fits)
 * int rx_dfa_utf16_fits (struct rx_dfa * frame,
 *		      const t_uint16 * burst,
 *		      size_t len);
 *
 *
 * Compare a DFA to string: is the entire string matched by the DFA?
 * Return a non-zero value (the state-label of the final DFA state) if
 * the string matches, 0 otherwise.
 *
 * This function works by advancing the DFA through all of the
 * characters in the input string and checking the state label of the
 * last state reached.  If that label is not 0, then the string
 * matches.  If that label is 0, or if an illegal input character is
 * reached before the end of the input string, the string does not
 * match.
 *
 * It is possible to asynchronously abort a call to this function.
 * See xref:"Exiting Long-running Matches".
 */
int
rx_dfa_utf16_fits (int * label,
		   struct rx_dfa * frame,
		   const t_uint16 * burst,
		   size_t len)
{
  int adv;
  adv = rx_dfa_utf16_advance (frame, burst, len);
  if (adv < 0)
    return -1;
  else if (!adv)
    {
      *label = 0;
      return 0;
    }
  else
    {
      *label = frame->final_tag;
      return 0;
    }
}


/*(c rx_dfa_utf16_advance)
 * int rx_dfa_advance (struct rx_dfa * frame,
 *		       const t_uint16 * burst,
 *		       size_t len);
 *
 *
 * Advance a DFA, reading characters from the input string.  Stop at
 * the end of the string, returning 1 or when a character is
 * encountered for which no transition is defined, returning 0.
 *
 * This is similar to `rx_dfa_fits', except that in this case, we
 * don't care about the state label of the final state.
 *
 * It is possible to asynchronously abort a call to this function.
 * See xref:"Exiting Long-running Matches".
 */
int
rx_dfa_utf16_advance (struct rx_dfa * frame,
		      const t_uint16 * burst,
		      size_t len)
{
  rx_transition_table inx_table;

  if (!len)
    return 1;

  inx_table = frame->state->transitions;
  rx_unlock_superstate (frame->rx, frame->state);
  frame->state = 0;

  while (len--)
    {
      struct rx_inx * inx;
      rx_transition_table next_table;

      if (rx_poll)
	(*rx_poll)();

      inx = rx_transition16 (inx_table, *burst);
      next_table = (rx_transition_table)inx->data;
      while (!next_table)
	{
	  struct rx_superstate * state;
	  state = rx_transitions_to_suprestate (inx_table);

	  switch ((long)inx->inx)
	    {
	    case rx_huge_char:
	      {
		t_uint16 hi;
		t_uint16 lo;
		t_unicode c;

		hi = *burst;
		if (!len)
		  goto handle_as_backtrack;
		--len;
		++burst;
		lo = *burst;
		if (!uni_is_low_surrogate (lo))
		  goto handle_as_backtrack;

		c = uni_assemble_surrogates (hi, lo);
		inx = rx_transition21 (state->huge_char_transitions, c);
		next_table = (rx_transition_table)inx->data;

		while (!next_table)
		  {
		    switch ((enum rx_opcode)inx->inx)
		      {
		      default:
		      case rx_huge_char:
			goto handle_by_panic;
		      case rx_backtrack:
			goto handle_as_backtrack;
		      case rx_cache_miss:
			inx = rx_handle_cache_miss (frame->rx, state, c, inx->data_2);
			if (!inx)
			  {
			    frame->state = 0;
			    frame->final_tag = 0;
			    return -1;
			  }
			next_table = (rx_transition_table)inx->data;
			continue;
		      }
		  }
		continue;
	      }

	    case rx_backtrack:
	    handle_as_backtrack:
	      /* RX_BACKTRACK means that we've reached the empty
	       * superstate, indicating that match can't succeed
	       * from this point.
	       */
	      frame->state = 0;
	      frame->final_tag = 0;
	      return 0;

	    case rx_cache_miss:
	      /* Because the superstate NFA is lazily constructed,
	       * and in fact may erode from underneath us, we sometimes
	       * have to construct the next instruction from the hard way.
	       * This invokes one step in the lazy-conversion.
	       */
	      inx = rx_handle_cache_miss (frame->rx, state, *burst, inx->data_2);
	      if (!inx)
		{
		  frame->state = 0;
		  frame->final_tag = 0;
		  return -1;
		}
	      next_table = (rx_transition_table)inx->data;
	      continue;


	      /* No other instructions are legal here.
	       */
	    default:
	    handle_by_panic:
	      panic ("unrecognized instruction in rx_dfa_advance");
	  }
	}
      inx_table = next_table;
      ++burst;
    }

  frame->state = rx_transitions_to_suprestate (inx_table);
  frame->final_tag = frame->state->members->state_label;
  rx_lock_superstate (frame->rx, frame->state);
  return 1;
}


/*(c rx_dfa_utf16_advance_to_final)
 * size_t rx_dfa_utf16_advance_to_final (struct rx_dfa * frame,
 *				     const t_uint16 * burst,
 *				     size_t len);
 *
 * Advance a DFA, reading characters from a string.
 *
 * Stop at the end of the string, a character with no transition, or
 * when a superstate is encountered with a non-0 label.  Return the
 * number of characters read from the string.
 *
 * This function stops on a transition *into* a state with a non-0
 * state label.  It doesn't matter if the machine is initially in a
 * state with a non-0 label: the machine will consume the first input
 * character regardless.  That means that if your regular expression
 * can match the empty string, you must detect this condition before
 * calling `rx_dfa_advance_to_final' by checking `dfa->final_tag'
 * after setting the start state of the DFA.
 *
 * If the match stopped in a final state, `dfa->final_tag' contains
 * the non-0 state label of the final state, otherwise, it contains 0.
 * If the match stopped on an illegal character, `dfa->state' is 0,
 * otherwise it is non-0.
 *
 * It is possible to asynchronously abort a call to this function.
 * See xref:"Exiting Long-running Matches".
 */
int
rx_dfa_utf16_advance_to_final (size_t * amt,
			       struct rx_dfa * frame,
			       const t_uint16 * burst,
			       size_t len)
{
  size_t initial_len;
  rx_transition_table inx_table;

  if (!len)
    {
      *amt = 0;
      return 1;
    }

  initial_len = len;
  inx_table = frame->state->transitions;
  rx_unlock_superstate (frame->rx, frame->state);
  frame->state = 0;

  while (len--)
    {
      struct rx_inx * inx;
      rx_transition_table next_table;

      if (rx_poll)
	(*rx_poll)();

      inx = rx_transition16 (inx_table, *burst);
      next_table = (rx_transition_table)inx->data;

      while (!next_table)
	{
	  struct rx_superstate * state;

	  state = rx_transitions_to_suprestate (inx_table);

	  switch ((enum rx_opcode)inx->inx)
	    {
	    case rx_huge_char:
	      {
		t_uint16 hi;
		t_uint16 lo;
		t_unicode c;

		hi = *burst;
		if (!len)
		  goto handle_as_backtrack;
		--len;
		++burst;
		lo = *burst;
		if (!uni_is_low_surrogate (lo))
		  goto handle_as_backtrack;

		c = uni_assemble_surrogates (hi, lo);
		inx = rx_transition21 (state->huge_char_transitions, c);
		next_table = (rx_transition_table)inx->data;

		while (!next_table)
		  {
		    switch ((enum rx_opcode)inx->inx)
		      {
		      default:
		      case rx_huge_char:
			goto handle_by_panic;
		      case rx_backtrack:
			goto handle_as_backtrack;
		      case rx_cache_miss:
			inx = rx_handle_cache_miss (frame->rx, state, c, inx->data_2);
			if (!inx)
			  {
			    frame->state = 0;
			    frame->final_tag = 0;
			    return -1;
			  }
			next_table = (rx_transition_table)inx->data;
			continue;
		      }
		  }
		continue;
	      }

	    case rx_backtrack:
	    handle_as_backtrack:
	      /* RX_BACKTRACK means that we've reached the empty
	       * superstate, indicating that match can't succeed
	       * from this point.
	       */
	      frame->state = 0;
	      frame->final_tag = 0;
	      *amt = (initial_len - len) - 1;
	      return 0;

	    case rx_cache_miss:
	      /* Because the superstate NFA is lazily constructed,
	       * and in fact may erode from underneath us, we sometimes
	       * have to construct the next instruction from the hard way.
	       * This invokes one step in the lazy-conversion.
	       */
	      inx = rx_handle_cache_miss (frame->rx, state, *burst, inx->data_2);
	      if (!inx)
		{
		  frame->state = 0;
		  frame->final_tag = 0;
		  return -1;
		}
	      next_table = (rx_transition_table)inx->data;
	      continue;

	      /* No other instructions are legal here.
	       */
	    default:
	    handle_by_panic:
	      while (1)
		panic ("unrecognized instruction in rx_dfa_advance_to_final");
	  }
	}

      if (inx->data_2)
	{
	  frame->state = rx_transitions_to_suprestate (next_table);
	  rx_lock_superstate (frame->rx, frame->state);
	  frame->final_tag = (long)inx->data_2;
	  *amt = (initial_len - len);
	  return 1;
	}
      inx_table = next_table;
      ++burst;
    }

  /* Consumed all of the characters. */
  frame->state = rx_transitions_to_suprestate (inx_table);
  rx_lock_superstate (frame->rx, frame->state);
  frame->final_tag = 0;
  *amt = initial_len;
  return 0;
}