path: root/src/packrat-parsers.ads

with

    Packrat.Traits,
    Packrat.Parse_Graphs;

private with

    Ada.Containers.Vectors,
    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
        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 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 Param
               (Input   : in     Traits.Element_Array;
                Context : in out Parser_Context;
                Start   : in     Positive)
            return Combinator_Result;
    function Optional
           (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;




    function Empty
           (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 Not_Empty
           (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_Holds is new Ada.Containers.Indefinite_Holders
       (Element_Type => Traits.Element_Array,
        "="          => Traits."=");

    package Tok_Holds is new Ada.Containers.Indefinite_Holders
       (Element_Type => Graphs.Finished_Token_Array,
        "="          => Graphs."=");

    function "<"
           (Left, Right : in Elem_Holds.Holder)
        return Boolean;

    function "<"
           (Left, Right : in Tok_Holds.Holder)
        return Boolean;




    type Combo_Key is record
        Start : Positive;
        Func  : Combinator;
    end record;

    function "<"
           (Left, Right : in Combo_Key)
        return Boolean;

    package Combo_Key_Vectors is new Ada.Containers.Vectors
       (Index_Type   => Positive,
        Element_Type => Combo_Key);

    --  This is needed to avoid some issues with using non-anonymous
    --  access values in a generic subprogram instantiation.
    function To_Key
           (Start : in Positive;
            Func  : access function
                   (Input   : in     Traits.Element_Array;
                    Context : in out Parser_Context;
                    Start   : in     Positive)
                return Combinator_Result)
        return Combo_Key;




    type Combo_Result_Part is record
        Finish : Natural := 0;
        Value  : Elem_Holds.Holder := Elem_Holds.Empty_Holder;
        Tokens : Tok_Holds.Holder := Tok_Holds.Empty_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?

    --  need to add a record of the total length of input available when
    --  result was computed, to allow for knowing when to recompute
    --  optional_more/need_more results

    --  actually no, just not putting optional/needmore results in the
    --  memotable will work fine, but how to figure out how much to pass forward?
    type Combinator_Result is record
        Results  : Result_Sets.Set := Result_Sets.Empty_Set;
        Curtails : Curtail_Maps.Map := Curtail_Maps.Empty_Map;
        Status   : Result_Status := Failure;
    end record;

    type Component_Result is record
        Status : Result_Status;
    end record;

    Empty_Fail : constant Combinator_Result :=
       (Results  => Result_Sets.Empty_Set,
        Curtails => Curtail_Maps.Empty_Map,
        Status   => Failure);




    package Needs_Sets is new Ada.Containers.Ordered_Sets
       (Element_Type => Positive);

    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;
        Used_Before      : Boolean := False;
        Global_Start     : Positive := 1;
        Current_Position : Positive := 1;
        Needs_More       : Needs_Sets.Set;
        Pass_Forward     : Elem_Holds.Holder;
        Memotable        : Memotables.Map;
        Leftrectable     : Leftrectables.Map;
        Allow_Incomplete : Boolean := True;
    end record;

    Empty_Context : constant Parser_Context :=
       (Result_So_Far    => Graphs.Empty_Graph,
        Used_Before      => False,
        Global_Start     => 1,
        Current_Position => 1,
        Needs_More       => Needs_Sets.Empty_Set,
        Pass_Forward     => Elem_Holds.Empty_Holder,
        Memotable        => Memotables.Empty_Map,
        Leftrectable     => Leftrectables.Empty_Map,
        Allow_Incomplete => True);




    function Reusable
           (Result   : in Combinator_Result;
            Position : in Positive;
            Leftrecs : in Leftrectables.Map)
        return Boolean;

    generic
        My_Key : in Combo_Key;
        with function Actual
               (Context : in out Parser_Context)
            return Combinator_Result;
    function Memoize
           (Context : in out Parser_Context)
        return Combinator_Result;




    procedure Inc_Leftrec
           (Key      : in     Combo_Key;
            Leftrecs : in out Leftrectables.Map);

    procedure Dec_Leftrec
           (Key      : in     Combo_Key;
            Leftrecs : in out Leftrectables.Map);

    function Exceeds_Curtail
           (Key      : in Combo_Key;
            Leftrecs : in Leftrectables.Map;
            Input    : in Traits.Element_Array)
        return Boolean;

    generic
        My_Key : in Combo_Key;
        Input  : in Traits.Element_Array;
        with function Actual
               (Context : in out Parser_Context)
            return Combinator_Result;
    function Curtailment
           (Context : in out Parser_Context)
        return Combinator_Result;




    procedure Merge
           (Target : in out Curtail_Maps.Map;
            Add    : in     Curtail_Maps.Map);

    function Merge
           (Left, Right : in Curtail_Maps.Map)
        return Curtail_Maps.Map;

    --  Should only be used to merge results obtained from
    --  the same input location.
    procedure Merge
           (Target : in out Combinator_Result;
            Add    : in     Combinator_Result);

    function Merge
           (Left, Right : in Combinator_Result)
        return Combinator_Result;

    generic
        with function Next
               (Input   : in     Traits.Element_Array;
                Context : in out Parser_Context;
                Start   : in     Positive)
            return Combinator_Result;
    function Continue
           (From    : in     Combinator_Result;
            Input   : in     Traits.Element_Array;
            Context : in out Parser_Context)
        return Combinator_Result;




    procedure Complete_Status
           (Result : in out Combinator_Result;
            Allow  : in     Boolean);




    function Slide
           (Input    : in Traits.Element_Array;
            Position : in Positive)
        return Traits.Element_Array;


end Packrat.Parsers;