Subversion Repositories openrisc

------------------------------------------------------------------------------

--                                                                          --

--                         GNAT LIBRARY COMPONENTS                          --

--                                                                          --

--                G N A T . S P I T B O L . P A T T E R N S                 --

--                                                                          --

--                                 B o d y                                  --

--                                                                          --

--                     Copyright (C) 1998-2008, AdaCore                     --

--                                                                          --

-- GNAT is free software;  you can  redistribute it  and/or modify it under --

-- terms of the  GNU General Public License as published  by the Free Soft- --

-- ware  Foundation;  either version 2,  or (at your option) any later ver- --

-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --

-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --

-- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --

-- for  more details.  You should have  received  a copy of the GNU General --

-- Public License  distributed with GNAT;  see file COPYING.  If not, write --

-- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth  Floor, --

-- Boston, MA 02110-1301, USA.                                              --

--                                                                          --

-- As a special exception,  if other files  instantiate  generics from this --

-- unit, or you link  this unit with other files  to produce an executable, --

-- this  unit  does not  by itself cause  the resulting  executable  to  be --

-- covered  by the  GNU  General  Public  License.  This exception does not --

-- however invalidate  any other reasons why  the executable file  might be --

-- covered by the  GNU Public License.                                      --

--                                                                          --

-- GNAT was originally developed  by the GNAT team at  New York University. --

-- Extensive contributions were provided by Ada Core Technologies Inc.      --

--                                                                          --

------------------------------------------------------------------------------

--  Note: the data structures and general approach used in this implementation

--  are derived from the original MINIMAL sources for SPITBOL. The code is not

--  a direct translation, but the approach is followed closely. In particular,

--  we use the one stack approach developed in the SPITBOL implementation.

with Ada.Strings.Unbounded.Aux; use Ada.Strings.Unbounded.Aux;

with GNAT.Debug_Utilities;      use GNAT.Debug_Utilities;

with System;                    use System;

with Ada.Unchecked_Conversion;

with Ada.Unchecked_Deallocation;

package body GNAT.Spitbol.Patterns is

   ------------------------

   -- Internal Debugging --

   ------------------------

   Internal_Debug : constant Boolean := False;

   --  Set this flag to True to activate some built-in debugging traceback

   --  These are all lines output with PutD and Put_LineD.

   procedure New_LineD;

   pragma Inline (New_LineD);

   --  Output new blank line with New_Line if Internal_Debug is True

   procedure PutD (Str : String);

   pragma Inline (PutD);

   --  Output string with Put if Internal_Debug is True

   procedure Put_LineD (Str : String);

   pragma Inline (Put_LineD);

   --  Output string with Put_Line if Internal_Debug is True

   -----------------------------

   -- Local Type Declarations --

   -----------------------------

   subtype String_Ptr is Ada.Strings.Unbounded.String_Access;

   subtype File_Ptr   is Ada.Text_IO.File_Access;

   function To_Address is new Ada.Unchecked_Conversion (PE_Ptr, Address);

   --  Used only for debugging output purposes

   subtype AFC is Ada.Finalization.Controlled;

   N : constant PE_Ptr := null;

   --  Shorthand used to initialize Copy fields to null

   type Natural_Ptr   is access all Natural;

   type Pattern_Ptr   is access all Pattern;

   --------------------------------------------------

   -- Description of Algorithm and Data Structures --

   --------------------------------------------------

   --  A pattern structure is represented as a linked graph of nodes

   --  with the following structure:

   --      +------------------------------------+

   --      I                Pcode               I

   --      +------------------------------------+

   --      I                Index               I

   --      +------------------------------------+

   --      I                Pthen               I

   --      +------------------------------------+

   --      I             parameter(s)           I

   --      +------------------------------------+

   --     Pcode is a code value indicating the type of the pattern node. This

   --     code is used both as the discriminant value for the record, and as

   --     the case index in the main match routine that branches to the proper

   --     match code for the given element.

   --     Index is a serial index number. The use of these serial index

   --     numbers is described in a separate section.

   --     Pthen is a pointer to the successor node, i.e the node to be matched

   --     if the attempt to match the node succeeds. If this is the last node

   --     of the pattern to be matched, then Pthen points to a dummy node

   --     of kind PC_EOP (end of pattern), which initializes pattern exit.

   --     The parameter or parameters are present for certain node types,

   --     and the type varies with the pattern code.

   type Pattern_Code is (

      PC_Arb_Y,

      PC_Assign,

      PC_Bal,

      PC_BreakX_X,

      PC_Cancel,

      PC_EOP,

      PC_Fail,

      PC_Fence,

      PC_Fence_X,

      PC_Fence_Y,

      PC_R_Enter,

      PC_R_Remove,

      PC_R_Restore,

      PC_Rest,

      PC_Succeed,

      PC_Unanchored,

      PC_Alt,

      PC_Arb_X,

      PC_Arbno_S,

      PC_Arbno_X,

      PC_Rpat,

      PC_Pred_Func,

      PC_Assign_Imm,

      PC_Assign_OnM,

      PC_Any_VP,

      PC_Break_VP,

      PC_BreakX_VP,

      PC_NotAny_VP,

      PC_NSpan_VP,

      PC_Span_VP,

      PC_String_VP,

      PC_Write_Imm,

      PC_Write_OnM,

      PC_Null,

      PC_String,

      PC_String_2,

      PC_String_3,

      PC_String_4,

      PC_String_5,

      PC_String_6,

      PC_Setcur,

      PC_Any_CH,

      PC_Break_CH,

      PC_BreakX_CH,

      PC_Char,

      PC_NotAny_CH,

      PC_NSpan_CH,

      PC_Span_CH,

      PC_Any_CS,

      PC_Break_CS,

      PC_BreakX_CS,

      PC_NotAny_CS,

      PC_NSpan_CS,

      PC_Span_CS,

      PC_Arbno_Y,

      PC_Len_Nat,

      PC_Pos_Nat,

      PC_RPos_Nat,

      PC_RTab_Nat,

      PC_Tab_Nat,

      PC_Pos_NF,

      PC_Len_NF,

      PC_RPos_NF,

      PC_RTab_NF,

      PC_Tab_NF,

      PC_Pos_NP,

      PC_Len_NP,

      PC_RPos_NP,

      PC_RTab_NP,

      PC_Tab_NP,

      PC_Any_VF,

      PC_Break_VF,

      PC_BreakX_VF,

      PC_NotAny_VF,

      PC_NSpan_VF,

      PC_Span_VF,

      PC_String_VF);

   type IndexT is range 0 .. +(2 **15 - 1);

   type PE (Pcode : Pattern_Code) is record

      Index : IndexT;

      --  Serial index number of pattern element within pattern

      Pthen : PE_Ptr;

      --  Successor element, to be matched after this one

      case Pcode is

         when PC_Arb_Y      |

              PC_Assign     |

              PC_Bal        |

              PC_BreakX_X   |

              PC_Cancel     |

              PC_EOP        |

              PC_Fail       |

              PC_Fence      |

              PC_Fence_X    |

              PC_Fence_Y    |

              PC_Null       |

              PC_R_Enter    |

              PC_R_Remove   |

              PC_R_Restore  |

              PC_Rest       |

              PC_Succeed    |

              PC_Unanchored => null;

         when PC_Alt        |

              PC_Arb_X      |

              PC_Arbno_S    |

              PC_Arbno_X    => Alt  : PE_Ptr;

         when PC_Rpat       => PP   : Pattern_Ptr;

         when PC_Pred_Func  => BF   : Boolean_Func;

         when PC_Assign_Imm |

              PC_Assign_OnM |

              PC_Any_VP     |

              PC_Break_VP   |

              PC_BreakX_VP  |

              PC_NotAny_VP  |

              PC_NSpan_VP   |

              PC_Span_VP    |

              PC_String_VP  => VP   : VString_Ptr;

         when PC_Write_Imm  |

              PC_Write_OnM  => FP   : File_Ptr;

         when PC_String     => Str  : String_Ptr;

         when PC_String_2   => Str2 : String (1 .. 2);

         when PC_String_3   => Str3 : String (1 .. 3);

         when PC_String_4   => Str4 : String (1 .. 4);

         when PC_String_5   => Str5 : String (1 .. 5);

         when PC_String_6   => Str6 : String (1 .. 6);

         when PC_Setcur     => Var  : Natural_Ptr;

         when PC_Any_CH     |

              PC_Break_CH   |

              PC_BreakX_CH  |

              PC_Char       |

              PC_NotAny_CH  |

              PC_NSpan_CH   |

              PC_Span_CH    => Char : Character;

         when PC_Any_CS     |

              PC_Break_CS   |

              PC_BreakX_CS  |

              PC_NotAny_CS  |

              PC_NSpan_CS   |

              PC_Span_CS    => CS   : Character_Set;

         when PC_Arbno_Y    |

              PC_Len_Nat    |

              PC_Pos_Nat    |

              PC_RPos_Nat   |

              PC_RTab_Nat   |

              PC_Tab_Nat    => Nat  : Natural;

         when PC_Pos_NF     |

              PC_Len_NF     |

              PC_RPos_NF    |

              PC_RTab_NF    |

              PC_Tab_NF     => NF   : Natural_Func;

         when PC_Pos_NP     |

              PC_Len_NP     |

              PC_RPos_NP    |

              PC_RTab_NP    |

              PC_Tab_NP     => NP   : Natural_Ptr;

         when PC_Any_VF     |

              PC_Break_VF   |

              PC_BreakX_VF  |

              PC_NotAny_VF  |

              PC_NSpan_VF   |

              PC_Span_VF    |

              PC_String_VF  => VF   : VString_Func;

      end case;

   end record;

   subtype PC_Has_Alt is Pattern_Code range PC_Alt .. PC_Arbno_X;

   --  Range of pattern codes that has an Alt field. This is used in the

   --  recursive traversals, since these links must be followed.

   EOP_Element : aliased constant PE := (PC_EOP, 0, N);

   --  This is the end of pattern element, and is thus the representation of

   --  a null pattern. It has a zero index element since it is never placed

   --  inside a pattern. Furthermore it does not need a successor, since it

   --  marks the end of the pattern, so that no more successors are needed.

   EOP : constant PE_Ptr := EOP_Element'Unrestricted_Access;

   --  This is the end of pattern pointer, that is used in the Pthen pointer

   --  of other nodes to signal end of pattern.

   --  The following array is used to determine if a pattern used as an

   --  argument for Arbno is eligible for treatment using the simple Arbno

   --  structure (i.e. it is a pattern that is guaranteed to match at least

   --  one character on success, and not to make any entries on the stack.

   OK_For_Simple_Arbno : constant array (Pattern_Code) of Boolean :=

     (PC_Any_CS    |

      PC_Any_CH    |

      PC_Any_VF    |

      PC_Any_VP    |

      PC_Char      |

      PC_Len_Nat   |

      PC_NotAny_CS |

      PC_NotAny_CH |

      PC_NotAny_VF |

      PC_NotAny_VP |

      PC_Span_CS   |

      PC_Span_CH   |

      PC_Span_VF   |

      PC_Span_VP   |

      PC_String    |

      PC_String_2  |

      PC_String_3  |

      PC_String_4  |

      PC_String_5  |

      PC_String_6   => True,

      others        => False);

   -------------------------------

   -- The Pattern History Stack --

   -------------------------------

   --  The pattern history stack is used for controlling backtracking when

   --  a match fails. The idea is to stack entries that give a cursor value

   --  to be restored, and a node to be reestablished as the current node to

   --  attempt an appropriate rematch operation. The processing for a pattern

   --  element that has rematch alternatives pushes an appropriate entry or

   --  entry on to the stack, and the proceeds. If a match fails at any point,

   --  the top element of the stack is popped off, resetting the cursor and

   --  the match continues by accessing the node stored with this entry.

   type Stack_Entry is record

      Cursor : Integer;

      --  Saved cursor value that is restored when this entry is popped

      --  from the stack if a match attempt fails. Occasionally, this

      --  field is used to store a history stack pointer instead of a

      --  cursor. Such cases are noted in the documentation and the value

      --  stored is negative since stack pointer values are always negative.

      Node : PE_Ptr;

      --  This pattern element reference is reestablished as the current

      --  Node to be matched (which will attempt an appropriate rematch).

   end record;

   subtype Stack_Range is Integer range -Stack_Size .. -1;

   type Stack_Type is array (Stack_Range) of Stack_Entry;

   --  The type used for a history stack. The actual instance of the stack

   --  is declared as a local variable in the Match routine, to properly

   --  handle recursive calls to Match. All stack pointer values are negative

   --  to distinguish them from normal cursor values.

   --  Note: the pattern matching stack is used only to handle backtracking.

   --  If no backtracking occurs, its entries are never accessed, and never

   --  popped off, and in particular it is normal for a successful match

   --  to terminate with entries on the stack that are simply discarded.

   --  Note: in subsequent diagrams of the stack, we always place element

   --  zero (the deepest element) at the top of the page, then build the

   --  stack down on the page with the most recent (top of stack) element

   --  being the bottom-most entry on the page.

   --  Stack checking is handled by labeling every pattern with the maximum

   --  number of stack entries that are required, so a single check at the

   --  start of matching the pattern suffices. There are two exceptions.

   --  First, the count does not include entries for recursive pattern

   --  references. Such recursions must therefore perform a specific

   --  stack check with respect to the number of stack entries required

   --  by the recursive pattern that is accessed and the amount of stack

   --  that remains unused.

   --  Second, the count includes only one iteration of an Arbno pattern,

   --  so a specific check must be made on subsequent iterations that there

   --  is still enough stack space left. The Arbno node has a field that

   --  records the number of stack entries required by its argument for

   --  this purpose.

   ---------------------------------------------------

   -- Use of Serial Index Field in Pattern Elements --

   ---------------------------------------------------

   --  The serial index numbers for the pattern elements are assigned as

   --  a pattern is constructed from its constituent elements. Note that there

   --  is never any sharing of pattern elements between patterns (copies are

   --  always made), so the serial index numbers are unique to a particular

   --  pattern as referenced from the P field of a value of type Pattern.

   --  The index numbers meet three separate invariants, which are used for

   --  various purposes as described in this section.

   --  First, the numbers uniquely identify the pattern elements within a

   --  pattern. If Num is the number of elements in a given pattern, then

   --  the serial index numbers for the elements of this pattern will range

   --  from 1 .. Num, so that each element has a separate value.

   --  The purpose of this assignment is to provide a convenient auxiliary

   --  data structure mechanism during operations which must traverse a

   --  pattern (e.g. copy and finalization processing). Once constructed

   --  patterns are strictly read only. This is necessary to allow sharing

   --  of patterns between tasks. This means that we cannot go marking the

   --  pattern (e.g. with a visited bit). Instead we construct a separate

   --  vector that contains the necessary information indexed by the Index

   --  values in the pattern elements. For this purpose the only requirement

   --  is that they be uniquely assigned.

   --  Second, the pattern element referenced directly, i.e. the leading

   --  pattern element, is always the maximum numbered element and therefore

   --  indicates the total number of elements in the pattern. More precisely,

   --  the element referenced by the P field of a pattern value, or the

   --  element returned by any of the internal pattern construction routines

   --  in the body (that return a value of type PE_Ptr) always is this

   --  maximum element,

   --  The purpose of this requirement is to allow an immediate determination

   --  of the number of pattern elements within a pattern. This is used to

   --  properly size the vectors used to contain auxiliary information for

   --  traversal as described above.

   --  Third, as compound pattern structures are constructed, the way in which

   --  constituent parts of the pattern are constructed is stylized. This is

   --  an automatic consequence of the way that these compound structures

   --  are constructed, and basically what we are doing is simply documenting

   --  and specifying the natural result of the pattern construction. The

   --  section describing compound pattern structures gives details of the

   --  numbering of each compound pattern structure.

   --  The purpose of specifying the stylized numbering structures for the

   --  compound patterns is to help simplify the processing in the Image

   --  function, since it eases the task of retrieving the original recursive

   --  structure of the pattern from the flat graph structure of elements.

   --  This use in the Image function is the only point at which the code

   --  makes use of the stylized structures.

   type Ref_Array is array (IndexT range <>) of PE_Ptr;

   --  This type is used to build an array whose N'th entry references the

   --  element in a pattern whose Index value is N. See Build_Ref_Array.

   procedure Build_Ref_Array (E : PE_Ptr; RA : out Ref_Array);

   --  Given a pattern element which is the leading element of a pattern

   --  structure, and a Ref_Array with bounds 1 .. E.Index, fills in the

   --  Ref_Array so that its N'th entry references the element of the

   --  referenced pattern whose Index value is N.

   -------------------------------

   -- Recursive Pattern Matches --

   -------------------------------

   --  The pattern primitive (+P) where P is a Pattern_Ptr or Pattern_Func

   --  causes a recursive pattern match. This cannot be handled by an actual

   --  recursive call to the outer level Match routine, since this would not

   --  allow for possible backtracking into the region matched by the inner

   --  pattern. Indeed this is the classical clash between recursion and

   --  backtracking, and a simple recursive stack structure does not suffice.

   --  This section describes how this recursion and the possible associated

   --  backtracking is handled. We still use a single stack, but we establish

   --  the concept of nested regions on this stack, each of which has a stack

   --  base value pointing to the deepest stack entry of the region. The base

   --  value for the outer level is zero.

   --  When a recursive match is established, two special stack entries are

   --  made. The first entry is used to save the original node that starts

   --  the recursive match. This is saved so that the successor field of

   --  this node is accessible at the end of the match, but it is never

   --  popped and executed.

   --  The second entry corresponds to a standard new region action. A

   --  PC_R_Remove node is stacked, whose cursor field is used to store

   --  the outer stack base, and the stack base is reset to point to

   --  this PC_R_Remove node. Then the recursive pattern is matched and

   --  it can make history stack entries in the normal matter, so now

   --  the stack looks like:

   --     (stack entries made by outer level)

   --     (Special entry, node is (+P) successor

   --      cursor entry is not used)

   --     (PC_R_Remove entry, "cursor" value is (negative)     <-- Stack base

   --      saved base value for the enclosing region)

   --     (stack entries made by inner level)

   --  If a subsequent failure occurs and pops the PC_R_Remove node, it

   --  removes itself and the special entry immediately underneath it,

   --  restores the stack base value for the enclosing region, and then

   --  again signals failure to look for alternatives that were stacked

   --  before the recursion was initiated.

   --  Now we need to consider what happens if the inner pattern succeeds, as

   --  signalled by accessing the special PC_EOP pattern primitive. First we

   --  recognize the nested case by looking at the Base value. If this Base

   --  value is Stack'First, then the entire match has succeeded, but if the

   --  base value is greater than Stack'First, then we have successfully

   --  matched an inner pattern, and processing continues at the outer level.

   --  There are two cases. The simple case is when the inner pattern has made

   --  no stack entries, as recognized by the fact that the current stack

   --  pointer is equal to the current base value. In this case it is fine to

   --  remove all trace of the recursion by restoring the outer base value and

   --  using the special entry to find the appropriate successor node.

   --  The more complex case arises when the inner match does make stack

   --  entries. In this case, the PC_EOP processing stacks a special entry

   --  whose cursor value saves the saved inner base value (the one that

   --  references the corresponding PC_R_Remove value), and whose node

   --  pointer references a PC_R_Restore node, so the stack looks like:

   --     (stack entries made by outer level)

   --     (Special entry, node is (+P) successor,

   --      cursor entry is not used)

   --     (PC_R_Remove entry, "cursor" value is (negative)

   --      saved base value for the enclosing region)

   --     (stack entries made by inner level)

   --     (PC_Region_Replace entry, "cursor" value is (negative)

   --      stack pointer value referencing the PC_R_Remove entry).

   --  If the entire match succeeds, then these stack entries are, as usual,

   --  ignored and abandoned. If on the other hand a subsequent failure

   --  causes the PC_Region_Replace entry to be popped, it restores the

   --  inner base value from its saved "cursor" value and then fails again.

   --  Note that it is OK that the cursor is temporarily clobbered by this

   --  pop, since the second failure will reestablish a proper cursor value.

   ---------------------------------

   -- Compound Pattern Structures --

   ---------------------------------

   --  This section discusses the compound structures used to represent

   --  constructed patterns. It shows the graph structures of pattern

   --  elements that are constructed, and in the case of patterns that

   --  provide backtracking possibilities, describes how the history

   --  stack is used to control the backtracking. Finally, it notes the

   --  way in which the Index numbers are assigned to the structure.

   --  In all diagrams, solid lines (built with minus signs or vertical

   --  bars, represent successor pointers (Pthen fields) with > or V used

   --  to indicate the direction of the pointer. The initial node of the

   --  structure is in the upper left of the diagram. A dotted line is an

   --  alternative pointer from the element above it to the element below

   --  it. See individual sections for details on how alternatives are used.

      -------------------

      -- Concatenation --

      -------------------

      --  In the pattern structures listed in this section, a line that looks

      --  like ----> with nothing to the right indicates an end of pattern

      --  (EOP) pointer that represents the end of the match.

      --  When a pattern concatenation (L & R) occurs, the resulting structure

      --  is obtained by finding all such EOP pointers in L, and replacing

      --  them to point to R. This is the most important flattening that

      --  occurs in constructing a pattern, and it means that the pattern

      --  matching circuitry does not have to keep track of the structure

      --  of a pattern with respect to concatenation, since the appropriate

      --  successor is always at hand.

      --  Concatenation itself generates no additional possibilities for

      --  backtracking, but the constituent patterns of the concatenated

      --  structure will make stack entries as usual. The maximum amount

      --  of stack required by the structure is thus simply the sum of the

      --  maximums required by L and R.

      --  The index numbering of a concatenation structure works by leaving

      --  the numbering of the right hand pattern, R, unchanged and adjusting

      --  the numbers in the left hand pattern, L up by the count of elements

      --  in R. This ensures that the maximum numbered element is the leading

      --  element as required (given that it was the leading element in L).

      -----------------

      -- Alternation --

      -----------------

      --  A pattern (L or R) constructs the structure:

      --    +---+     +---+

      --    | A |---->| L |---->

      --    +---+     +---+

      --      .

      --      .

      --    +---+

      --    | R |---->

      --    +---+

      --  The A element here is a PC_Alt node, and the dotted line represents

      --  the contents of the Alt field. When the PC_Alt element is matched,

      --  it stacks a pointer to the leading element of R on the history stack

      --  so that on subsequent failure, a match of R is attempted.

      --  The A node is the highest numbered element in the pattern. The

      --  original index numbers of R are unchanged, but the index numbers

      --  of the L pattern are adjusted up by the count of elements in R.

      --  Note that the difference between the index of the L leading element

      --  the index of the R leading element (after building the alt structure)

      --  indicates the number of nodes in L, and this is true even after the

      --  structure is incorporated into some larger structure. For example,

      --  if the A node has index 16, and L has index 15 and R has index

      --  5, then we know that L has 10 (15-5) elements in it.

      --  Suppose that we now concatenate this structure to another pattern

      --  with 9 elements in it. We will now have the A node with an index

      --  of 25, L with an index of 24 and R with an index of 14. We still

      --  know that L has 10 (24-14) elements in it, numbered 15-24, and

      --  consequently the successor of the alternation structure has an

      --  index with a value less than 15. This is used in Image to figure

      --  out the original recursive structure of a pattern.

      --  To clarify the interaction of the alternation and concatenation

      --  structures, here is a more complex example of the structure built

      --  for the pattern:

      --      (V or W or X) (Y or Z)

      --  where A,B,C,D,E are all single element patterns:

      --    +---+     +---+       +---+     +---+

      --    I A I---->I V I---+-->I A I---->I Y I---->

      --    +---+     +---+   I   +---+     +---+

      --      .               I     .

      --      .               I     .

      --    +---+     +---+   I   +---+

      --    I A I---->I W I-->I   I Z I---->

      --    +---+     +---+   I   +---+

      --      .               I

      --      .               I

      --    +---+             I

      --    I X I------------>+

      --    +---+

      --  The numbering of the nodes would be as follows:

      --    +---+     +---+       +---+     +---+

      --    I 8 I---->I 7 I---+-->I 3 I---->I 2 I---->

      --    +---+     +---+   I   +---+     +---+

      --      .               I     .

      --      .               I     .

      --    +---+     +---+   I   +---+

      --    I 6 I---->I 5 I-->I   I 1 I---->

      --    +---+     +---+   I   +---+

      --      .               I

      --      .               I

      --    +---+             I

      --    I 4 I------------>+

      --    +---+

      --  Note: The above structure actually corresponds to

      --    (A or (B or C)) (D or E)

      --  rather than

      --    ((A or B) or C) (D or E)

      --  which is the more natural interpretation, but in fact alternation

      --  is associative, and the construction of an alternative changes the

      --  left grouped pattern to the right grouped pattern in any case, so

      --  that the Image function produces a more natural looking output.

      ---------

      -- Arb --

      ---------

      --  An Arb pattern builds the structure

      --    +---+

      --    | X |---->

      --    +---+

      --      .

      --      .

      --    +---+

      --    | Y |---->

      --    +---+

      --  The X node is a PC_Arb_X node, which matches null, and stacks a

      --  pointer to Y node, which is the PC_Arb_Y node that matches one

      --  extra character and restacks itself.

      --  The PC_Arb_X node is numbered 2, and the PC_Arb_Y node is 1

      -------------------------

      -- Arbno (simple case) --

      -------------------------

      --  The simple form of Arbno can be used where the pattern always

      --  matches at least one character if it succeeds, and it is known

      --  not to make any history stack entries. In this case, Arbno (P)

      --  can construct the following structure:

      --      +-------------+

      --      |             ^

      --      V             |

      --    +---+           |

      --    | S |---->      |

      --    +---+           |

      --      .             |

      --      .             |

      --    +---+           |

      --    | P |---------->+

      --    +---+

      --  The S (PC_Arbno_S) node matches null stacking a pointer to the

      --  pattern P. If a subsequent failure causes P to be matched and

      --  this match succeeds, then node A gets restacked to try another

      --  instance if needed by a subsequent failure.

      --  The node numbering of the constituent pattern P is not affected.

      --  The S node has a node number of P.Index + 1.

      --------------------------

      -- Arbno (complex case) --

      --------------------------

      --  A call to Arbno (P), where P can match null (or at least is not

      --  known to require a non-null string) and/or P requires pattern stack

      --  entries, constructs the following structure:

      --      +--------------------------+

      --      |                          ^

      --      V                          |

      --    +---+                        |

      --    | X |---->                   |

      --    +---+                        |

      --      .                          |

      --      .                          |

      --    +---+     +---+     +---+    |

      --    | E |---->| P |---->| Y |--->+

      --    +---+     +---+     +---+

      --  The node X (PC_Arbno_X) matches null, stacking a pointer to the

      --  E-P-X structure used to match one Arbno instance.

      --  Here E is the PC_R_Enter node which matches null and creates two

      --  stack entries. The first is a special entry whose node field is

      --  not used at all, and whose cursor field has the initial cursor.

      --  The second entry corresponds to a standard new region action. A

      --  PC_R_Remove node is stacked, whose cursor field is used to store

      --  the outer stack base, and the stack base is reset to point to

      --  this PC_R_Remove node. Then the pattern P is matched, and it can

      --  make history stack entries in the normal manner, so now the stack

      --  looks like:

      --     (stack entries made before assign pattern)

      --     (Special entry, node field not used,

      --      used only to save initial cursor)

      --     (PC_R_Remove entry, "cursor" value is (negative)  <-- Stack Base

      --      saved base value for the enclosing region)

      --     (stack entries made by matching P)

      --  If the match of P fails, then the PC_R_Remove entry is popped and

      --  it removes both itself and the special entry underneath it,

      --  restores the outer stack base, and signals failure.

      --  If the match of P succeeds, then node Y, the PC_Arbno_Y node, pops

      --  the inner region. There are two possibilities. If matching P left

      --  no stack entries, then all traces of the inner region can be removed.

      --  If there are stack entries, then we push an PC_Region_Replace stack

      --  entry whose "cursor" value is the inner stack base value, and then

      --  restore the outer stack base value, so the stack looks like:

      --     (stack entries made before assign pattern)

      --     (Special entry, node field not used,

      --      used only to save initial cursor)

      --     (PC_R_Remove entry, "cursor" value is (negative)

      --      saved base value for the enclosing region)

      --     (stack entries made by matching P)

      --     (PC_Region_Replace entry, "cursor" value is (negative)

      --      stack pointer value referencing the PC_R_Remove entry).

      --  Now that we have matched another instance of the Arbno pattern,

      --  we need to move to the successor. There are two cases. If the

      --  Arbno pattern matched null, then there is no point in seeking

      --  alternatives, since we would just match a whole bunch of nulls.

      --  In this case we look through the alternative node, and move

      --  directly to its successor (i.e. the successor of the Arbno

      --  pattern). If on the other hand a non-null string was matched,

      --  we simply follow the successor to the alternative node, which

      --  sets up for another possible match of the Arbno pattern.

      --  As noted in the section on stack checking, the stack count (and

      --  hence the stack check) for a pattern includes only one iteration

      --  of the Arbno pattern. To make sure that multiple iterations do not

      --  overflow the stack, the Arbno node saves the stack count required

      --  by a single iteration, and the Concat function increments this to