Memoize and curtailment for left recursion should be correct now

3 files changed, 61 insertions, 75 deletions

diff --git a/curtail.txt b/curtail.txt
index 38fd238..b9c88b1 100644
--- a/curtail.txt
+++ b/curtail.txt
@@ -20,5 +20,7 @@ when depth of a curtail is less than or equal to remaining tokens of input after
 
 when depth of curtail plus remaining tokens after furthest finish of a result is less than or equal to total input tokens plus one, curtail can be deleted from a result
 
+when depth of curtail plus remaining tokens after furthest finish of a result is less than or equal to remaining tokens at the start of a result, then curtail can be deleted from result, because in that case it is no longer possible for curtail to happen due to excessive combinator recursion
+
 
 
diff --git a/src/packrat-parsers.adb b/src/packrat-parsers.adb
index 7c89984..e4fa97d 100644
--- a/src/packrat-parsers.adb
+++ b/src/packrat-parsers.adb
@@ -120,29 +120,18 @@ package body Packrat.Parsers is
 
     function Reusable
            (Result   : in Combinator_Result;
-            Main_Key : in Combo_Key;
+            Position : in Positive;
             Leftrecs : in Leftrectables.Map)
         return Boolean
     is
-        Position : Positive := Main_Key.Start;
         Working_Key : Combo_Key;
     begin
         for Cursor in Result.Curtails.Iterate loop
             Working_Key := To_Key (Position, Curtail_Maps.Key (Cursor));
-            if Working_Key = Main_Key then
-                if not Leftrecs.Contains (Working_Key) then
-                    if Curtail_Maps.Element (Cursor) > 1 then
-                        return False;
-                    end if;
-                elsif Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key) + 1 then
-                    return False;
-                end if;
-            else
-                if not Leftrecs.Contains (Working_Key) or else
-                    Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key)
-                then
-                    return False;
-                end if;
+            if not Leftrecs.Contains (Working_Key) or else
+                Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key)
+            then
+                return False;
             end if;
         end loop;
         return True;
@@ -159,7 +148,7 @@ package body Packrat.Parsers is
     begin
         if Context.Memotable.Contains (My_Key) then
             Previous := Context.Memotable.Element (My_Key);
-            if Reusable (Previous, My_Key, Context.Leftrectable) then
+            if Reusable (Previous, My_Key.Start, Context.Leftrectable) then
                 return Previous;
             end if;
         end if;
@@ -175,22 +164,17 @@ package body Packrat.Parsers is
                 Combo := Curtail_Maps.Key (C);
                 if Context.Leftrectable.Contains (To_Key (My_Key.Start, Combo)) then
                     Left := Context.Leftrectable.Element (To_Key (My_Key.Start, Combo));
-                    if Combo = My_Key.Func then
-                        Left := Left + 1;
-                    end if;
-                    if Result.Curtails.Contains (Combo) then
+                    if not Result.Results.Is_Empty and then
+                        Result.Results.Last_Element.Finish - Left > My_Key.Start
+                    then
+                        Result.Curtails.Exclude (Combo);
+                    elsif Result.Curtails.Contains (Combo) then
                         Result.Curtails.Replace (Combo, Left);
                     else
                         Result.Curtails.Insert (Combo, Left);
                     end if;
                 else
-                    if Combo = My_Key.Func then
-                        if Result.Curtails.Contains (Combo) then
-                            Result.Curtails.Replace (Combo, 1);
-                        else
-                            Result.Curtails.Insert (Combo, 1);
-                        end if;
-                    end if;
+                    Result.Curtails.Exclude (Combo);
                 end if;
             end loop;
             Context.Memotable.Replace (My_Key, Result);
@@ -272,7 +256,7 @@ package body Packrat.Parsers is
     begin
         for Curse in Add.Iterate loop
             if Target.Contains (Curtail_Maps.Key (Curse)) then
-                if Target.Element (Curtail_Maps.Key (Curse)) > Curtail_Maps.Element (Curse) then
+                if Target.Element (Curtail_Maps.Key (Curse)) < Curtail_Maps.Element (Curse) then
                     Target.Replace (Curtail_Maps.Key (Curse), Curtail_Maps.Element (Curse));
                 end if;
             else
@@ -631,10 +615,10 @@ package body Packrat.Parsers is
             Salt.Results := Processed;
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Stamp'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Stamp'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Stamp'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Stamp'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Stamp;
 
 
@@ -660,10 +644,10 @@ package body Packrat.Parsers is
             Salt.Results := Processed;
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Ignore'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Ignore'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Ignore'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Ignore'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Ignore;
 
 
@@ -726,10 +710,10 @@ package body Packrat.Parsers is
             Complete_Status (Salt, Context.Allow_Incomplete);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Sequence'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Sequence'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Sequence'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Sequence'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Sequence;
 
 
@@ -752,10 +736,10 @@ package body Packrat.Parsers is
             Salt := Cont_Param (Salt, Input, Context);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Sequence_2'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Sequence_2'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Sequence_2'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Sequence_2'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Sequence_2;
 
 
@@ -777,10 +761,10 @@ package body Packrat.Parsers is
             Complete_Status (Salt, Context.Allow_Incomplete);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Choice'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Choice'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Choice'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Choice'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Choice;
 
 
@@ -799,10 +783,10 @@ package body Packrat.Parsers is
                (Choice_One (Input, Context, Start),
                 Choice_Two (Input, Context, Start));
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Choice_2'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Choice_2'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Choice_2'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Choice_2'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Choice_2;
 
 
@@ -836,10 +820,10 @@ package body Packrat.Parsers is
             Complete_Status (Salt, Context.Allow_Incomplete);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Count'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Count'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Count'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Count'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Count;
 
 
@@ -883,10 +867,10 @@ package body Packrat.Parsers is
             Complete_Status (Salt, Context.Allow_Incomplete);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Many'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Many'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Many'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Many'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Many;
 
 
@@ -917,10 +901,10 @@ package body Packrat.Parsers is
                     end return;
             end case;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Followed_By'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Followed_By'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Followed_By'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Followed_By'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Followed_By;
 
 
@@ -955,10 +939,10 @@ package body Packrat.Parsers is
                     end if;
             end case;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Not_Followed_By'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Not_Followed_By'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Not_Followed_By'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Not_Followed_By'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Not_Followed_By;
 
 
@@ -981,10 +965,10 @@ package body Packrat.Parsers is
         begin
             return Sep_End_By (Input, Context, Start);
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Many_Until'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Many_Until'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Many_Until'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Many_Until'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Many_Until;
 
 
@@ -1005,10 +989,10 @@ package body Packrat.Parsers is
             Complete_Status (Salt, Context.Allow_Incomplete);
             return Salt;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Optional'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Optional'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Optional'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Optional'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Optional;
 
 
@@ -1034,10 +1018,10 @@ package body Packrat.Parsers is
                 return Full_Seq (Input, Context, Start);
             end if;
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Separate_By'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Separate_By'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Separate_By'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Separate_By'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Separate_By;
 
 
@@ -1056,10 +1040,10 @@ package body Packrat.Parsers is
         begin
             return End_Seq (Input, Context, Start);
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Separate_End_By'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Separate_End_By'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Separate_End_By'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Separate_End_By'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Separate_End_By;
 
 
@@ -1080,10 +1064,10 @@ package body Packrat.Parsers is
         begin
             return Full_Seq (Input, Context, Start);
         end Actual;
-        function Curt is new Curtailment (To_Key (Start, Between'Access), Input, Actual);
-        function Memo is new Memoize (To_Key (Start, Between'Access), Curt);
+        function Memo is new Memoize (To_Key (Start, Between'Access), Actual);
+        function Curt is new Curtailment (To_Key (Start, Between'Access), Input, Memo);
     begin
-        return Memo (Context);
+        return Curt (Context);
     end Between;
 
 
diff --git a/src/packrat-parsers.ads b/src/packrat-parsers.ads
index 6040f4f..e11d623 100644
--- a/src/packrat-parsers.ads
+++ b/src/packrat-parsers.ads
@@ -599,7 +599,7 @@ private
 
     function Reusable
            (Result   : in Combinator_Result;
-            Main_Key : in Combo_Key;
+            Position : in Positive;
             Leftrecs : in Leftrectables.Map)
         return Boolean;