Skeleton of Packrat.Parsers

1 files changed, 436 insertions, 0 deletions

diff --git a/src/packrat-parsers.ads b/src/packrat-parsers.ads
new file mode 100644
index 0000000..8a0f39c
--- /dev/null
+++ b/src/packrat-parsers.ads
@@ -0,0 +1,436 @@
+
+
+with
+
+    Packrat.Traits,
+    Packrat.Parse_Graphs;
+
+private with
+
+    Ada.Containers.Ordered_Maps,
+    Ada.Containers.Ordered_Sets,
+    Ada.Containers.Indefinite_Holders;
+
+
+generic
+
+    with package Traits is new Packrat.Traits (<>);
+    with package Graphs is new Packrat.Parse_Graphs (Traits);
+
+package Packrat.Parsers is
+
+
+    --  Memoize only adds to the Parse_Graph result when it is successful
+    --  so the Parser_Context will need to keep track of unsuccessful combinator
+    --  at given positions
+
+    --  If all combinators are memoized in a memotable then no need to keep track of call stack
+    --  To do that, use start point and function access as the key?
+
+    --  If a combinator at a position is already in the memotable, return result
+    --  Else run combinator, add/update result in memotable, then return result
+    --  As a side effect of this, the entry in the memotable will be updated several times
+    --  while left recursion unwinds
+
+    --  Combinators need to return value strings as well as the finish sets
+
+    --  Two functions, Symbolize and Ignore?, to create a node in the graph and to discard
+    --  the current return value string
+
+    --  Some way to join tokens-of-tokens into just tokens
+
+
+
+
+    type Parser_Context is private;
+
+    Empty_Context : constant Parser_Context;
+
+
+
+
+    type Combinator_Result is private;
+
+    type Combinator is access function
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    type Combinator_Array is array (Positive range <>) of Combinator;
+
+
+
+
+    type Component_Result is private;
+
+    type Component is access function
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Component_Result;
+
+
+
+
+    type With_Input is access function
+        return Traits.Element_Array;
+
+
+
+
+    generic
+        Label : in Traits.Label_Enum;
+        with function Combo
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+    function Root
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Component_Result;
+
+
+
+
+    generic
+        Root_Component : in Component;
+    procedure Parse
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Result  :    out Graphs.Parse_Graph);
+
+    generic
+        Root_Component : in Component;
+    function Parse_Only
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context)
+        return Graphs.Parse_Graph;
+
+    generic
+        Root_Component : in Component;
+    function Parse_With
+           (Input   : in     With_Input;
+            Context : in out Parser_Context)
+        return Graphs.Parse_Graph;
+
+
+
+
+    generic
+        Label : in Traits.Label_Enum;
+        with function Combo
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+    function Stamp
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Combo
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+    function Ignore
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+
+
+
+    generic
+        Params : in Combinator_Array;
+    function Sequence
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        Params : in Combinator_Array;
+    function Choice
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Param
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+        Number : in Positive;
+    function Count
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Param
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+        Minimum : in Natural := 0;
+    function Many
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Param
+               (Input   : in     Traits.Element_Array;
+                Context : in out Parser_Context;
+                Start   : in     Positive)
+            return Combinator_Result;
+        with function Test
+               (Item : in Traits.Element_Type)
+            return Boolean;
+        Minimum : in Natural := 0;
+    function Many_Until
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+
+
+
+    generic
+        with function Test
+               (Item : in Traits.Element_Type)
+            return Boolean;
+    function Satisfy
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Test
+               (Item : in Traits.Element_Type)
+            return Boolean;
+        with function Change
+               (From : in Traits.Element_Type)
+            return Traits.Element_Type;
+    function Satisfy_With
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        Item : in Traits.Element_Type;
+    function Match
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        Item : in Traits.Element_Type;
+        with function Change
+               (From : in Traits.Element_Type)
+            return Traits.Element_Type;
+    function Match_With
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        Items : in Traits.Element_Array;
+    function Multimatch
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        Number : in Positive := 1;
+    function Take
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Test
+               (Item : in Traits.Element_Type)
+            return Boolean;
+    function Take_While
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        with function Test
+               (Item : in Traits.Element_Type)
+            return Boolean;
+    function Take_Until
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+
+
+
+    generic
+        EOL_Item : in Traits.Element_Type;
+    function Line_End
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+    generic
+        EOF_Item : in Traits.Element_Type;
+    function Input_End
+           (Input   : in     Traits.Element_Array;
+            Context : in out Parser_Context;
+            Start   : in     Positive)
+        return Combinator_Result;
+
+
+private
+
+
+    --  refactor Finish_Type from Parse_Graphs into Packrat and use here and in Lexers
+
+    --  does the lexer handle input that doesn't start from 1 at the beginning?
+
+
+    --  results need to record what combinators were curtailed, if any, with leftrec count
+
+    --  choice combinators can be curtailed by multiple combinators at once
+
+    --  results need to deal with tokens to put in the graph somehow
+
+
+    --  Curtail when leftrec count exceeds number of remaining tokens plus 1
+    --  for a given combinator/position
+
+
+    package Elem_Array_Holders is new Ada.Containers.Indefinite_Holders
+       (Element_Type => Traits.Element_Array,
+        "="          => Traits."=");
+
+    package Token_Array_Holders is new Ada.Containers.Indefinite_Holders
+       (Element_Type => Traits.Tokens.Token_Array,
+        "="          => Traits.Tokens."=");
+
+    function "<"
+           (Left, Right : in Elem_Array_Holders.Holder)
+        return Boolean;
+
+    function "<"
+           (Left, Right : in Token_Array_Holders.Holder)
+        return Boolean;
+
+
+
+
+    type Combo_Key is record
+        Start : Positive;
+        Func  : Combinator;
+    end record;
+
+    function "<"
+           (Left, Right : in Combo_Key)
+        return Boolean;
+
+
+
+
+    type Combo_Result_Part is record
+        Finish : Natural;
+        Value  : Elem_Array_Holders.Holder;
+        Tokens : Token_Array_Holders.Holder;
+    end record;
+
+    function "<"
+           (Left, Right : in Combo_Result_Part)
+        return Boolean;
+
+    package Result_Sets is new Ada.Containers.Ordered_Sets
+       (Element_Type => Combo_Result_Part);
+
+
+
+
+    function "<"
+           (Left, Right : in Combinator)
+        return Boolean;
+
+    package Curtail_Maps is new Ada.Containers.Ordered_Maps
+       (Key_Type     => Combinator,
+        Element_Type => Positive);
+
+
+
+
+    --  If there's anything in the Curtails, then Results should be empty
+    --  and vice versa... union?
+    type Combinator_Result is record
+        Results  : Result_Sets.Set;
+        Curtails : Curtail_Maps.Map;
+        Status   : Result_Status;
+    end record;
+
+    type Component_Result is record
+        Status : Result_Status;
+    end record;
+
+
+
+
+    package Memotables is new Ada.Containers.Ordered_Maps
+       (Key_Type     => Combo_Key,
+        Element_Type => Combinator_Result);
+
+    package Leftrectables is new Ada.Containers.Ordered_Maps
+       (Key_Type     => Combo_Key,
+        Element_Type => Positive);
+
+
+
+
+    type Parser_Context is record
+        Result_So_Far    : Graphs.Parse_Graph;
+        Position         : Positive := 1;
+        Offset           : Natural := 0;
+        Status           : Result_Status := Success;
+        Pass_Forward     : Elem_Array_Holders.Holder;
+        Memotable        : Memotables.Map;
+        Leftrectable     : Leftrectables.Map;
+        Allow_Incomplete : Boolean := True;
+    end record;
+
+    Empty_Context : constant Parser_Context :=
+       (Result_So_Far    => Graphs.Empty_Graph,
+        Position         => 1,
+        Offset           => 0,
+        Status           => Success,
+        Pass_Forward     => Elem_Array_Holders.Empty_Holder,
+        Memotable        => Memotables.Empty_Map,
+        Leftrectable     => Leftrectables.Empty_Map,
+        Allow_Incomplete => True);
+
+
+end Packrat.Parsers;
+
+