Provided by: libmarpa-r2-perl_2.086000~dfsg-8build5_amd64 bug

Name

       Marpa::R2::Glade - Low-level interface to Marpa's Abstract Syntax Forests (ASF's)

Synopsis

         my $grammar = Marpa::R2::Scanless::G->new(
             {   source => \(<<'END_OF_SOURCE'),
         :start ::= pair
         pair ::= duple | item item
         duple ::= item item
         item ::= Hesperus | Phosphorus
         Hesperus ::= 'a'
         Phosphorus ::= 'a'
         END_OF_SOURCE
             }
         );

         my $slr = Marpa::R2::Scanless::R->new( { grammar => $grammar } );
         $slr->read( \'aa' );
         my $asf = Marpa::R2::ASF->new( { slr => $slr } );
         die 'No ASF' if not defined $asf;
         my $output_as_array = asf_to_basic_tree($asf);
         my $actual_output   = array_display($output_as_array);

       The code for asf_to_basic_tree() represents a user-supplied call using the interface
       described below.  An full example of ast_to_basic_tree(), which constructs a Perl array
       "tree", is given below.  array_display() displays the tree in a compact form.  The code
       for it is also given below.  The return value of array_display() is as follows:

           Glade 2 has 2 symches
             Glade 2, Symch 0, pair ::= duple
                 Glade 6, duple ::= item item
                     Glade 8 has 2 symches
                       Glade 8, Symch 0, item ::= Hesperus
                           Glade 13, Hesperus ::= 'a'
                               Glade 15, Symbol 'a': "a"
                       Glade 8, Symch 1, item ::= Phosphorus
                           Glade 1, Phosphorus ::= 'a'
                               Glade 17, Symbol 'a': "a"
                     Glade 7 has 2 symches
                       Glade 7, Symch 0, item ::= Hesperus
                           Glade 22, Hesperus ::= 'a'
                               Glade 24, Symbol 'a': "a"
                       Glade 7, Symch 1, item ::= Phosphorus
                           Glade 9, Phosphorus ::= 'a'
                               Glade 26, Symbol 'a': "a"
             Glade 2, Symch 1, pair ::= item item
                 Glade 8 revisited
                 Glade 7 revisited

This INTERFACE is ALPHA and EXPERIMENTAL

       The interface described in this document is very much a work in progress.  It is alpha and
       experimental.  The bad side of this is that it is subject to radical change without
       notice.  The good side is that field is 100% open for users to have feedback into the
       final interface.

About this document

       This document describes the low-level interface to Marpa's abstract syntax forests
       (ASF's).  It assumes that you are already familiar with the high-level interface.  This
       low-level interface allows the maximum flexiblity in building the forest, but requires the
       application to do much of the work.

Ambiguity: factoring versus symches

       An abstract syntax forest (ASF) is similar to an abstract syntax tree (AST), but it has an
       additional ability -- it can represent an ambiguous parse.  Ambiguity in a parse can come
       in two forms, and Marpa's ASF's treat the distinction as important.  An ambiguity can be a
       symbolic choice (a symch), or a factoring.  Symbolic choices are the kind of ambiguity
       that springs first to mind -- a choice between rules, or a choice between a rule and
       token.  Factorings involve only one rule, but the RHS symbols of that rule divide the
       input up ("factor it") in different ways.  I'll give examples below.

       Symches and factorings are treated separately, because they behave very differently:

       •   Symches are less common than factorings.

       •   Factorings are frequently not of interest; symches are almost always of major
           interest.

       •   Symches usually have just a few alternatives; the possible number of factorings easily
           grows into the thousands.

       •   In the worst case, the number of symches is a constant that depends on size of the
           grammar.  In the worst case, the number of factorings grows exponentially with the
           length of the string being factored.

       •   The constant limiting the number of symches will almost always be of manageable size.
           The number of factorings can grow without limit.

   An example of a symch
       Hesperus is Venus's traditional name as an evening star, and Phosphorus (aka Lucifer) is
       its traditional name as a morning star.  For the grammar,

           :start ::= planet
           planet ::= hesperus
           planet ::= phosphorus
           hesperus ::= venus
           phosphorus ::= venus
           venus ~ 'venus'

       and the input string '"venus"', the forest would look like

           Symbol #0 planet has 2 symches
             Symch #0.0
             GL2 Rule 0: planet ::= hesperus
               GL3 Rule 2: hesperus ::= venus
                 GL4 Symbol venus: "venus"
             Symch #0.1
             GL2 Rule 1: planet ::= phosphorus
               GL5 Rule 3: phosphorus ::= venus
                 GL6 Symbol venus: "venus"

       Notice the tags of the form ""GLn"", where n is an integer.  These identify the glade.
       Glades will be described in detail below.

       The rules allow the string '"venus"' to be parsed as either one of two planets:
       '"hesperus"' or '"phosphorus"', depending on whether rule 0 or rule 1 is used.  The
       choice, at glade 2, between rules 0 and 1, is a symch.

   An example of a factoring
       For the grammar,

           :start ::= top
           top ::= b b
           b ::= a a
           b ::= a
           a ~ 'a'

       and the input '"aaa"', a successful parse will always have two "b"'s.  Of these two "b"'s
       one will always be short, deriving a string of length 1: '"a"'.  The other will always be
       long, deriving a string of length 2: '"aa"'.  But they can be in either order, which means
       that the two "b"'s can divide up the input stream in two different ways: long string
       first; or short string first.

       These two different ways of dividing the input stream using the rule

           top ::= b b

       are called a factoring.  Here's Marpa's dump of the forest:

           GL2 Rule 0: top ::= b b
             Factoring #0
               GL3 Rule 2: b ::= a
                 GL4 Symbol a: "a"
               GL5 Rule 1: b ::= a a
                 GL6 Symbol a: "a"
                 GL7 Symbol a: "a"
             Factoring #1
               GL8 Rule 1: b ::= a a
                 GL9 Symbol a: "a"
                 GL10 Symbol a: "a"
               GL11 Rule 2: b ::= a
                 GL12 Symbol a: "a"

The structure of a forest

       An ASF can be pictured as a forest on a mountain.  This mountain forest has glades, and
       there are paths between the glades.  The term "glade" comes from the idea of a glade as a
       distinct place in a forest that is open to light.

       The paths between glades have a direction -- they are always thought of as running one-
       way: downhill.  If a path connects two glades, the one uphill is called an upglade and the
       one downhill is called a downglade.

       There is a glade at the top of mountain called the "peak".  The peak has no upglades.

The glade hierarchy

       Every glade has the same internal structure, which is this hierarchy:

       •   Glades contain symches.  A symch is either for a rule or for a token.

       •   Rule symches contain factorings.

       •   Factorings contain factors.

       •   A factor is the uphill end of a path which leads to a downglade.  That downglade will
           contain a glade hierarchy of its own.

   Glades
       Each glade node represents an instance of a symbol in one of the possible parse trees.
       This means that each glade has a symbol (called the "glade symbol"), and an "input span".
       An input span is an input start location, and a length in characters.  Because it has a
       start location and a length, a span also specifies an end location in the input.

   Symches
       Every glade contains one or more symches.  If a glade has only one symch, that symch is
       said to be trivial.  A symch is either a token symch or a rule symch.  For a token symch,
       the glade symbol is the token symbol.  For a rule symch, the glade symbol is the LHS of
       the rule.

       At most one of the symches in a glade can be a token symch.  There can, however, be many
       rule symches in a glade -- one for every rule with the glade symbol on its LHS.

   Factorings
       Each rule symch contains one or more factorings.  A factoring is a way of dividing up the
       input span of the glade among its RHS symbols, which in this context are called factors.
       If a rule symch has only one factoring, that factoring is said to be trivial.  A token
       symch contains no factorings, which means that token symches are the terminals of an ASF.

       Because the number of factorings can get out of hand, factorings may be omitted.  A symch
       which omits factorings is said to be truncated.  By default, every symch is truncated down
       to its first 42 factorings.

   Factors
       Every factoring has one or more factors.  Each "factor" corresponds to a symbol instance
       on the RHS of the rule.  Each such RHS factor is also a downglade, one which contains its
       own symches.

The glade ID

       Each glade has a glade ID.  This can be relied on to be a non-negative integer.  A glade
       ID may be zero.  Glade ID's are obtained from the "peak()" and "factoring_downglades()"
       methods.

Techniques for traversing ASF's

   Memoization
       When traversing a forest, you should take steps to avoid traversing the same glades twice.
       You can do this by memoizing the result of each glade, perhaps using its glade ID to index
       an array.  When a glade is visited, the array can be checked to see if its result has been
       memoized.  If so, the memoized result should be used.

       This memoization eliminates the need to revisit the downglades of an already visited
       glade.  It does not eliminate multiple visits to a glade, but it does eliminate
       retraversal of the glades downhill from it.  In practice, the improvement in speed can be
       stunning.  It will often be the difference between an program which is unuseably slow even
       for very small inputs, and one which is extremely fast even for large inputs.

       Repeated subtraversals happen when two glades share the same downglades, something that
       occurs frequently in ASF's.  Additionally, some day the SLIF may allow cycles.
       Memoization will prevent a cycle form causing an infinite loop.

       The example in this POD includes a memoization scheme which is very simple, but adequate
       for most purposes.  The main logic of its memoization is shown here.

               my ( $asf, $glade, $seen ) = @_;
               return bless ["Glade $glade revisited"], 'My_Revisit'
                   if $seen->[$glade];
               $seen->[$glade] = 1;

       Putting memoization in one of the very first drafts of your code will save you time and
       trouble.

Forest method

   peak()
           my $peak = $asf->peak();

       Returns the glade ID of the peak.  This may be zero.  All failures are thrown as
       exceptions.

Glade methods

   glade_literal()
               my $literal = $asf->glade_literal($glade);

       Returns the literal substring of the input associated with the glade.  Every glade is
       associated with a span -- a start location in the input, and a length.  On failure, throws
       an exception.

       The literal is determined by the range.  This works as expected if your application reads
       the input characters one-by-one in order.  (We will call applications which read in this
       fashion, monotonic.)  Most applications are monotonic, and yours is, unless you've taken
       special pains to make it otherwise.  Computation of literal substrings for non-monotonic
       applications is addressed in "Literals and G1 spans" in Marpa::R2::Scanless::R.

   glade_span()
           my ( $glade_start, $glade_length ) = $asf->glade_span($glade_id);

       Returns the span of the input associated with the glade.  Every glade is associated with a
       span -- a start location in the input, and a length.  On failure, throws an exception.

       The span will be as expected if your application reads the input characters one-by-one in
       order.  (We will call applications which read in this fashion, monotonic.)  Most
       applications are monotonic, and yours is, unless you've taken special pains to make it
       otherwise.  Computation of literal substrings for non-monotonic applications is addressed
       in "Literals and G1 spans" in Marpa::R2::Scanless::R.

   glade_symch_count()
           my $symch_count = $asf->glade_symch_count($glade);

       Requires a glade ID as its only argument.  Returns the number of symches contained in the
       glade specified by the argument.  On failure, throws an exception.

   glade_symbol_id()
           my $symbol_id    = $asf->glade_symbol_id($glade);
           my $display_form = $grammar->symbol_display_form($symbol_id);

       Requires a glade ID as its only argument.  Returns the symbol ID of the "glade symbol" for
       the glade specified by the argument.  On failure, throws an exception.

Symch methods

   symch_rule_id()
           my $rule_id = $asf->symch_rule_id( $glade, $symch_ix );

       Requires two arguments: a glade ID and a zero-based symch index.  These specify a symch.
       If the symch specified is a rule symch, returns the rule ID.  If it is a token symch,
       returns -1.

       Returns a Perl undef, if the glade exists, but the symch index is too high.  On other
       failure, throws an exception.

   symch_is_truncated()
       [ To be written. ]

   symch_factoring_count()
           my $factoring_count =
               $asf->symch_factoring_count( $glade, $symch_ix );

       Requires two arguments: a glade ID and a zero-based symch index.  These specify a symch.
       Returns the count of factorings if the specified symch is a rule symch.  This count will
       always be one or greater.  Returns zero if the specified symch is a token symch.

       Returns a Perl undef, if the glade exists, but the symch index is too high.  On other
       failure, throws an exception.

Factoring methods

   factoring_downglades()
           my $downglades =
               $asf->factoring_downglades( $glade, $symch_ix,
               $factoring_ix );

       Requires three arguments: a glade ID, the zero-based index of a symch and the zero-based
       index of a factoring.  These specify a factoring.  On success, returns a reference to an
       array.  The array contains the glade IDs of the the downglades in the factoring specified.

       Returns a Perl undef, if the glade and symch exist, but the factoring index is too high.
       On other failure, throws an exception.  In particular, exceptions are thrown if the symch
       is for a token; and if the glade exists, but the symch index is too high.

Methods for reporting ambiguity

           if ( $recce->ambiguity_metric() > 1 ) {
               my $asf = Marpa::R2::ASF->new( { slr => $recce } );
               die 'No ASF' if not defined $asf;
               my $ambiguities = Marpa::R2::Internal::ASF::ambiguities($asf);

               # Only report the first two
               my @ambiguities = grep {defined} @{$ambiguities}[ 0 .. 1 ];

               $actual_value = 'Application grammar is ambiguous';
               $actual_result =
                   Marpa::R2::Internal::ASF::ambiguities_show( $asf, \@ambiguities );
               last PROCESSING;
           } ## end if ( $recce->ambiguity_metric() > 1 )

   ambiguities()
           my $ambiguities = Marpa::R2::Internal::ASF::ambiguities($asf);

       Returns a reference to an array of ambiguity reports in the ASF.  The first and only
       argument must be an ASF object.  The array returned will be be zero length if the parse
       was not ambiguous.  Ambiguity reports are as described below.

       While the ambiguities() method can be called to determine whether or not ambiguities
       exist, it is the more expensive way to do it.  The $slr->ambiguity_metric() method tests
       an already-existing boolean and is therefore extremely fast.  If you are simply testing
       for ambiguity, or if you can save time when you know that a parse is unambiguous, you will
       usually want to test for ambiguity with the ambiguity_metric() method before calling the
       ambiguities() method.

   ambiguities_show()
         $actual_result =
           Marpa::R2::Internal::ASF::ambiguities_show( $asf, \@ambiguities );

       Returns a string which contains a description of the ambiguities in its arguments.  Takes
       two arguments, both required.  The first is an ASF, and the second is a reference to an
       array of ambiguities, in the format returned by the ambiguities() method.

       Major applications will often have their own customized ambiguity formatting routine, one
       which can formulate error messages based, not just on the names of the rules and symbols,
       but on knowledge of the role that the rules and symbols play in the application.  This
       method is intended for applications which do not have their own customized ambiguity
       handling.  For those which do, it can be used as a fallback for handling those reports
       that the customized method does not recognize or that do not need special handling.  The
       format of the returned string is subject to change.

Ambiguity reports

       The ambiguity reports returned by the ambiguities() method are of two kinds: symch reports
       and factoring reports.

   Symch reports
       A symch report is issued whenever, in a top-down traversal of the ASF, an non-trivial
       symch is encountered.  A symch report takes the form

          [ 'symch', $glade ]

       where $glade is the ID of the glade with the symch ambiguity.  With this and the accessor
       methods in this document, an application can report full details of the symch ambiguity.

       Typically, when there is more than one kind of ambiguity in an input span, only one is of
       real interest.  Symch ambiguities are usually of more interest than factorings.  And if
       one ambiguity is uphill from another, the downhill ambiguity is usually a side effect of
       the uphill one and of little interest.

       Accordingly, if a glade has both a symch ambiguity and a factoring ambiguity, only the
       symch ambiguity is reported.  And if two ambiguities in the ASF overlap, only the one
       closest to the peak is reported.

   Factoring reports
       A symch report is issued whenever, in a top-down traversal of the ASF, an sequence of
       symbols is found which has more than one factoring.  Factoring reports are specific --
       they identify not just rules, but the specific sequences within the RHS which are
       differently factored -- multifactored stretches.  Sequence rules especially have long
       stretches where the symbols are in sync with each other, broken by other stretches where
       they are out of sync.  Marpa reports each of the ambiguous stretches.  (A detailed
       definition of multifactored stretches is below.)

       A factoring report takes the form

           [ 'factoring', $glade, $symch_ix, $factor_ix1, $factoring_ix2, $factor_ix2 ];

       where $glade is the ID of the glade with the factoring ambiguity, and $symch_ix is the
       index of the symch involved.  The multifactored stretch is described by two "identifying
       factors".  Both factors are at the beginning of the stretch, and therefore have the same
       input start location.  They differ in length.

       The first of the two identifying factors has factoring index of 0, and its factor index is
       $factor_ix1.  The second identifying factor has a factoring index of $factoring_ix2, and
       its factor index is $factor_ix2.

       The identifying factors will usually be enough for error reporting, which is the usual
       application of these reports.  Full details of the stretch are not given because they can
       be extremely large; are usually not of interest; and can be determined by following up on
       the information in the factoring report using the accessor methods described in this
       document.

       Ambiguities in rules and symbols downhill from an ambiguously factored stretch are not
       reported.  If a glade has both a symch ambiguity and a factoring ambiguity, only the symch
       ambiguity is reported.

The code for the synopsis

   The asf_to_basic_tree() code
         sub asf_to_basic_tree {
             my ( $asf, $glade ) = @_;
             my $peak = $asf->peak();
             return glade_to_basic_tree( $asf, $peak, [] );
         } ## end sub asf_to_basic_tree

         sub glade_to_basic_tree {
             my ( $asf, $glade, $seen ) = @_;
             return bless ["Glade $glade revisited"], 'My_Revisit'
                 if $seen->[$glade];
             $seen->[$glade] = 1;
             my $grammar     = $asf->grammar();
             my @symches     = ();
             my $symch_count = $asf->glade_symch_count($glade);
             SYMCH: for ( my $symch_ix = 0; $symch_ix < $symch_count; $symch_ix++ ) {
                 my $rule_id = $asf->symch_rule_id( $glade, $symch_ix );
                 if ( $rule_id < 0 ) {
                     my $literal      = $asf->glade_literal($glade);
                     my $symbol_id    = $asf->glade_symbol_id($glade);
                     my $display_form = $grammar->symbol_display_form($symbol_id);
                     push @symches,
                         bless [qq{Glade $glade, Symbol $display_form: "$literal"}],
                         'My_Token';
                     next SYMCH;
                 } ## end if ( $rule_id < 0 )

                 # ignore any truncation of the factorings
                 my $factoring_count =
                     $asf->symch_factoring_count( $glade, $symch_ix );
                 my @symch_description = ("Glade $glade");
                 push @symch_description, "Symch $symch_ix" if $symch_count > 1;
                 push @symch_description, $grammar->rule_show($rule_id);
                 my $symch_description = join q{, }, @symch_description;

                 my @factorings = ($symch_description);
                 for (
                     my $factoring_ix = 0;
                     $factoring_ix < $factoring_count;
                     $factoring_ix++
                     )
                 {
                     my $downglades =
                         $asf->factoring_downglades( $glade, $symch_ix,
                         $factoring_ix );
                     push @factorings,
                         bless [ map { glade_to_basic_tree( $asf, $_, $seen ) }
                             @{$downglades} ], 'My_Rule';
                 } ## end for ( my $factoring_ix = 0; $factoring_ix < $factoring_count...)
                 if ( $factoring_count > 1 ) {
                     push @symches,
                         bless [
                         "Glade $glade, symch $symch_ix has $factoring_count factorings",
                         @factorings
                         ],
                         'My_Factorings';
                     next SYMCH;
                 } ## end if ( $factoring_count > 1 )
                 push @symches, bless [ @factorings[ 0, 1 ] ], 'My_Factorings';
             } ## end SYMCH: for ( my $symch_ix = 0; $symch_ix < $symch_count; ...)
             return bless [ "Glade $glade has $symch_count symches", @symches ],
                 'My_Symches'
                 if $symch_count > 1;
             return $symches[0];
         } ## end sub glade_to_basic_tree

   The array_display() code
       Because of the blessings in this example, a standard dump of the output array is too
       cluttered for comfortable reading.  The following code displays the output from
       asf_to_basic_tree() in a more compact form.  Note that this code makes no use of Marpa,
       and works for all Perl arrays.  It is included for completeness, and as a simple example
       of array traversal.

           sub array_display {
               my ($array) = @_;
               my ( undef, @lines ) = @{ array_lines_display($array) };
               my $text = q{};
               for my $line (@lines) {
                   my ( $indent, $body ) = @{$line};
                   $indent -= 6;
                   $text .= ( q{ } x $indent ) . $body . "\n";
               }
               return $text;
           } ## end sub array_display

           sub array_lines_display {
               my ($array) = @_;
               my $reftype = Scalar::Util::reftype($array) // '!undef!';
               return [ [ 0, $array ] ] if $reftype ne 'ARRAY';
               my @lines = ();
               ELEMENT: for my $element ( @{$array} ) {
                   for my $line ( @{ array_lines_display($element) } ) {
                       my ( $indent, $body ) = @{$line};
                       push @lines, [ $indent + 2, $body ];
                   }
               } ## end ELEMENT: for my $element ( @{$array} )
               return \@lines;
           } ## end sub array_lines_display

Details

       This section contains some elaborations of the above, some of them in mathematical terms.
       These details are segregated because they are not essential to using this interface, and
       while some readers find them more helpful than distracting, for many others it is the
       reverse.

   An alternative way of defining glade terminology
       Here's a way of defining some of the above terms which is less intuitive, but more
       precise.  First, define the glade length from glades A to glade B in an ASF as the number
       of glades on the shortest path from A to B, not including glade A.  (Recall that paths are
       directional.)  If there is no path between glades A and B, the glade length is undefined.
       Glade B is a downglade of glade A, and glade A is an upglade of glade B, if and only if
       the glade length from A to B is 1.

       A glade A is uphill with respect to glade B, and a glade B is downhill with respect to
       glade A, if and only if the glade length from A to B is defined.

       A peak of an ASF is a node without upglades.  By construction of the ASF, there is only
       one peak.  A glade with a token symch is trivial if it has no rule symches.  A glade
       without a token symch is trivial if it has exactly one downglade.

       The distance-to-peak of a glade "A" is the glade length from the peak to glade "A".  Glade
       "A" is said to have a higher altitude than glade "B" if the distance-to-peak of glade "A"
       is less than that of glade "B".  Glade "A" has a lower altitude than glade "B" if the
       distance-to-peak of glade "A" is greater than that of glade "B".  Glade "A" has the same
       altitude as glade "B" if the distance-to-peak of glade "A" is equal to that of glade "B".

   Cycles
       In the current SLIF implementation, a forest is a directed acyclic graph (DAG).  (In the
       mathematical literature a DAG is also called a "tree", but that use is confusing in the
       present context.)  The underlying Marpa algorithm allows parse trees with cycles, and
       someday the SLIF probably will as well.  When that happens, ASF's will no longer be
       "acyclic" and therefore will no longer be DAG's.  This document talks about ASF's as if
       that day had already come -- it assumes that the ASF's might contain cycles.

       In an ASF that contains one or more cycles, the concepts of uphill and downhill become
       much less useful for describing the relative positions of glades.  For example, if glade A
       cycles back to itself through glade B, then

       •   Glade A will be uphill from glade B, and

       •   Glade B will be uphill from glade A; so that

       •   Glade B will be downhill from glade A, and

       •   Glade A will be downhill from glade B; and

       •   Glade A will be both downhill and uphill from itself; and

       •   Glade B will be both downhill and uphill from itself.

       ASF's will always be constructed so that the peak has no upglades.  Because of this, the
       peak can never be part of a cycle.  This means that altitude will always be well defined
       in the sense that, for any two glades "A" and "B", one and only one of the following
       statements will be true:

       •   Glade "A" is lower in altitude than glade "B".

       •   Glade "A" is higher in altitude than glade "B".

       •   Glade "A" is equal in altitude to glade "b".

   Token symches
       In the current SLIF implementation, a symbol is always either a token or the LHS of a
       rule.  This means that any glade that contains a token symch cannot contain any rule
       symches.  It also means that any glade that contains a rule symch will not contain a token
       symch.

       However, the underlying Marpa algorithm allows LHS terminals, and someday the SLIF
       probably will as well.  This document is written as if that day has already come, and
       describes glades as if they could contain both rule symches and a token symch.

   Maximum symches per glade
       Above, the point is made that the number of symches in a glade, even in the worst case, is
       a very manageable number.  For a particular case, it is not hard to work out the exact
       maximum.  Here are the details.

       There can be at most one token symch.  There can be only rule symch for every rule.  In
       addition, all rules in a glade must have the glade symbol as their LHS.  Let the number of
       rules with the glade symbol on their LHS be "r".  The maximum number of symches in a glade
       is "r+1".

   Multifactored stretches
       Marpa locates factoring ambiguities, not just by rule, but by RHS symbol.  It finds
       multifactored stretches, input spans where a sequence of symbols within the RHS of a rule
       have multiple factorings.  A multifactored stretch will sometimes encompass the entire RHS
       of a rule.  In other cases, the RHS of a single rule might contain many multifactored
       stretches.  This is often the case with sequence rules.  Sequence rules can have a very
       long RHS, and in those situations narrowing down factoring ambiguities to specific input
       spans is necessary for precise error reporting.

       The main body of this document worked with an intuitive "know one when I see one" idea of
       multifactored stretches.  The exact definition follows.  First we will need a series of
       preliminary definitions.

       Consider the case of a arbitrary rule symch.  Intuitively, a factoring position is a
       location within the factors of one of the factorings of that symch.  It can be seen as a
       duple "<factoring_ix, factor_ix>" where "<factoring_ix>" is the index of a factoring
       within the symch, and "<factor_ix>" is the index of one of the factors of the factoring.

       Let "SP" be a function that maps the symch's set of factoring indexes to the non-negative
       integers, such that for a factoring index "i" and factor index "j", "SP(i)=j", "j" is a
       valid factor index within the factoring "i".  The function "SP" can be called a symch
       position.

       Every symch position is equivalent to a set of factoring positions.  The initial symch
       position is the symch position all of whose factoring positions have a factor index of 0.
       Equivalently, it is the constant function "ISP", where "ISP(i)=0" for all factoring
       indexes "i".

       The factor with index "factor_ix" in the factoring with index "factoring_ix" is said to be
       the factor at factoring position "<factoring_ix, factor_ix>".  A factor is one of the
       factors of a symch position if and only if it is a factor at one of its factoring
       positions.

       An aligned symch position is a factoring position all of whose factors have the same start
       location.  The location of an aligned symch position is that start location.  The initial
       symch position is always an aligned factoring position.  A synced symch position is an
       aligned symch position all of whose factors have the same length and symbol ID.  A
       unsynced symch position is an aligned symch position that is not a synced symch position.

       We are now in a position to define a multifactored stretch.  Intuitively, a multifactored
       stretch is a longest possible input span that contains at least one unsynced symch
       position, but no synced symch positions.  More formally, a multifactored stretch of a
       symch is a span of start locations within that symch, such that:

       •   Its first location is the location of unsynced symch position.

       •   Its first location is the initial symch position, or the first symch positiion after a
           synched symch position.

       •   Its end location is the end location of the symch, or a synced symch position,
           whichever occurs first.

       Note that multifactored stretch are aligned in terms of input locations, but they do not
       have to be aligned in terms of factor indexes.  The factoring positions of a multifactored
       stretch can have many different factor indexes.  This is true of all rules, but it is
       particularly likely for a sequence rule, where the RHS consists of repetitions of a single
       symbol.

Copyright and License

         Copyright 2014 Jeffrey Kegler
         This file is part of Marpa::R2.  Marpa::R2 is free software: you can
         redistribute it and/or modify it under the terms of the GNU Lesser
         General Public License as published by the Free Software Foundation,
         either version 3 of the License, or (at your option) any later version.

         Marpa::R2 is distributed in the hope that it will be useful,
         but WITHOUT ANY WARRANTY; without even the implied warranty of
         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
         Lesser General Public License for more details.

         You should have received a copy of the GNU Lesser
         General Public License along with Marpa::R2.  If not, see
         http://www.gnu.org/licenses/.