diff options
| -rw-r--r-- | packrat_parser_lib_notes.txt | 32 | ||||
| -rw-r--r-- | src/packrat-graphs.adb | 214 | ||||
| -rw-r--r-- | src/packrat-graphs.ads | 180 | ||||
| -rw-r--r-- | src/packrat.ads | 84 |
4 files changed, 460 insertions, 50 deletions
diff --git a/packrat_parser_lib_notes.txt b/packrat_parser_lib_notes.txt index 333b999..2a8e0cc 100644 --- a/packrat_parser_lib_notes.txt +++ b/packrat_parser_lib_notes.txt @@ -315,9 +315,20 @@ Packrat.Interfaces ends up being necessary for parsing List of interfaces: +Node + - Leaf (constructor) + - Branch (constructor) + - Is_Leaf + - Is_Branch + - Label + - Elements + - Start + - Finish + Cursor - Is_Nothing - Depth + - Is_Node - Is_Root - Is_Branch - Is_Leaf @@ -341,8 +352,7 @@ Cursor Directed_Acyclic_Graph - Contains - - Leaf - - Branch + - Singleton (constructor) - Is_Empty - Is_Ambiguous - Node_Count @@ -363,20 +373,22 @@ Packrat.Graphs - can be replaced with a user-supplied type, assuming proper care is taken to avoid exponential issues List_of_datatypes: -Graph_Cursor - - (implements all of Interfaces.Cursor) -Parse_Graph - - (implements all of Interfaces.Directed_Acyclic_Graph) +Node (implements all of Interfaces.Node) +Node_Reference +Cursor (implements all of Interfaces.Cursor) +Iter_Cursor (wraps a Cursor, necessary for iteration) +Parse_Graph (implements all of Interfaces.Directed_Acyclic_Graph) +Choosing_Function (used in Iterate_Choice) List of funcs: Debug_String +Node_At + +Is_Valid_Node Iterate -Reverse_Iterate +Iterate_Subtree Iterate_Choice -Reverse_Iterate_Choice -Iterate_SUbtree -Iterate_Subtree_Choice diff --git a/src/packrat-graphs.adb b/src/packrat-graphs.adb index 2cf74b3..1206a89 100644 --- a/src/packrat-graphs.adb +++ b/src/packrat-graphs.adb @@ -3,6 +3,86 @@ package body Packrat.Graphs is + + function Leaf + (New_Item : in Element_Array; + Start : in Positive; + Finish : in Natural) + return Node is + begin + return This : Node; + end Leaf; + + + function Branch + (Label : in Label_Enum; + Start : in Positive; + Finish : in Natural) + return Node is + begin + return This : Node; + end Branch; + + + + + + function Is_Leaf + (This : in Node) + return Boolean is + begin + return False; + end Is_Leaf; + + + function Is_Branch + (This : in Node) + return Boolean is + begin + return False; + end Is_Branch; + + + + + + function Label + (This : in Node) + return Label_Enum is + begin + return Label_Enum'First; + end Label; + + + function Elements + (This : in Node) + return Element_Array + is + Empty : Element_Array (1 .. 0); + begin + return Empty; + end Elements; + + + function Start + (This : in Node) + return Positive is + begin + return 1; + end Start; + + + function Finish + (This : in Node) + return Natural is + begin + return 0; + end Finish; + + + + + function Is_Nothing (Position : in Cursor) return Boolean is @@ -22,6 +102,14 @@ package body Packrat.Graphs is end Depth; + function Is_Node + (Position : in Cursor) + return Boolean is + begin + return False; + end Is_Node; + + function Is_Root (Position : in Cursor) return Boolean is @@ -241,24 +329,21 @@ package body Packrat.Graphs is - function Leaf - (New_Item : in Element_Array; - Start : in Positive; - Finish : in Natural) + function Singleton + (Input : in My_Interfaces.Node'Class) return Parse_Graph is begin return This : Parse_Graph; - end Leaf; + end Singleton; - function Branch - (Label : in Label_Enum; - Start : in Positive; - Finish : in Natural) - return Parse_Graph is + function Node_At + (Container : in Parse_Graph; + Position : in My_Interfaces.Cursor'Class) + return Node_Reference is begin - return This : Parse_Graph; - end Branch; + return (Data => No_Node'Unrestricted_Access); + end Node_At; @@ -366,6 +451,111 @@ package body Packrat.Graphs is end Find; + + + + function Is_Valid_Node + (Position : in Iter_Cursor) + return Boolean is + begin + return Position.Data.Is_Node; + end Is_Valid_Node; + + + + + + function Iterate + (This : in Parse_Graph) + return Graph_Iterators.Reversible_Iterator'Class is + begin + return Result : Reversible_Iterator do + Result.My_Container := This'Unrestricted_Access; + Result.My_Position := No_Position; + end return; + end Iterate; + + + function Iterate_Subtree + (This : in Parse_Graph; + Position : in My_Interfaces.Cursor'Class) + return Graph_Iterators.Reversible_Iterator'Class is + begin + return Result : Reversible_Iterator do + Result.My_Container := This'Unrestricted_Access; + Result.My_Position := No_Position; + end return; + end Iterate_Subtree; + + + function Iterate_Choice + (This : in Parse_Graph; + Func : in Choosing_Function) + return Graph_Iterators.Forward_Iterator'Class is + begin + return Result : Forward_Iterator do + Result.My_Container := This'Unrestricted_Access; + Result.My_Position := No_Position; + end return; + end Iterate_Choice; + + + + + + function First + (Object : in Forward_Iterator) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end First; + + function Next + (Object : in Forward_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end Next; + + + + + + function First + (Object : in Reversible_Iterator) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end First; + + + function Next + (Object : in Reversible_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end Next; + + + function Last + (Object : in Reversible_Iterator) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end Last; + + + function Previous + (Object : in Reversible_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor is + begin + return (Data => Object.My_Position'Unrestricted_Access); + end Previous; + + end Packrat.Graphs; diff --git a/src/packrat-graphs.ads b/src/packrat-graphs.ads index 4095360..877be3a 100644 --- a/src/packrat-graphs.ads +++ b/src/packrat-graphs.ads @@ -1,5 +1,10 @@ +with + + Ada.Iterator_Interfaces; + + generic type Label_Enum is (<>); type Element is private; @@ -8,10 +13,70 @@ generic package Packrat.Graphs is + type Node is new My_Interfaces.Node with private; + + type Node_Reference (Data : not null access Node'Class) is limited null record + with Implicit_Dereference => Data; + type Cursor is new My_Interfaces.Cursor with private; - type Parse_Graph is new My_Interfaces.Graph with private; + type Iter_Cursor (Data : not null access Cursor) is private + with Implicit_Dereference => Data; + + + type Parse_Graph is new My_Interfaces.Graph with private + with Default_Iterator => Iterate, + Iterator_Element => Node_Reference, + Variable_Indexing => Node_At; + + + + + No_Position : constant Cursor; + + Empty_Graph : constant Parse_Graph; + + + + + function Leaf + (New_Item : in Element_Array; + Start : in Positive; + Finish : in Natural) + return Node; + + function Branch + (Label : in Label_Enum; + Start : in Positive; + Finish : in Natural) + return Node; + + + function Is_Leaf + (This : in Node) + return Boolean; + + function Is_Branch + (This : in Node) + return Boolean; + + + function Label + (This : in Node) + return Label_Enum; + + function Elements + (This : in Node) + return Element_Array; + + function Start + (This : in Node) + return Positive; + + function Finish + (This : in Node) + return Natural; @@ -27,6 +92,10 @@ package Packrat.Graphs is (Position : in Cursor) return Natural; + function Is_Node + (Position : in Cursor) + return Boolean; + function Is_Root (Position : in Cursor) return Boolean; @@ -39,6 +108,9 @@ package Packrat.Graphs is (Position : in Cursor) return Boolean; + + + function Label (Position : in Cursor) return Label_Enum; @@ -47,9 +119,6 @@ package Packrat.Graphs is (Position : in Cursor) return Element_Array; - - - function Start (Position : in Cursor) return Positive; @@ -145,17 +214,16 @@ package Packrat.Graphs is - function Leaf - (New_Item : in Element_Array; - Start : in Positive; - Finish : in Natural) + function Singleton + (Input : in My_Interfaces.Node'Class) return Parse_Graph; - function Branch - (Label : in Label_Enum; - Start : in Positive; - Finish : in Natural) - return Parse_Graph; + function Node_At + (Container : in Parse_Graph; + Position : in My_Interfaces.Cursor'Class) + return Node_Reference + with Pre => + Position.Is_Node; @@ -221,15 +289,101 @@ package Packrat.Graphs is + function Is_Valid_Node + (Position : in Iter_Cursor) + return Boolean; + + + + + package Graph_Iterators is + new Ada.Iterator_Interfaces (Iter_Cursor, Is_Valid_Node); + + type Choosing_Function is access function + (Position : in Cursor) + return Natural; + + + + + function Iterate + (This : in Parse_Graph) + return Graph_Iterators.Reversible_Iterator'Class; + + function Iterate_Subtree + (This : in Parse_Graph; + Position : in My_Interfaces.Cursor'Class) + return Graph_Iterators.Reversible_Iterator'Class; + + function Iterate_Choice + (This : in Parse_Graph; + Func : in Choosing_Function) + return Graph_Iterators.Forward_Iterator'Class; + + + + private + type Node is new My_Interfaces.Node with null record; + type Cursor is new My_Interfaces.Cursor with null record; + type Iter_Cursor (Data : not null access Cursor) is null record; type Parse_Graph is new My_Interfaces.Graph with null record; + + + No_Node : constant Node := (My_Interfaces.Node with null record); + + No_Position : constant Cursor := (My_Interfaces.Cursor with null record); + + Empty_Graph : constant Parse_Graph := (My_Interfaces.Graph with null record); + + + + + type Forward_Iterator is new Graph_Iterators.Forward_Iterator with record + My_Container : access Parse_Graph; + My_Position : Cursor; + end record; + + overriding function First + (Object : in Forward_Iterator) + return Iter_Cursor; + + overriding function Next + (Object : in Forward_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor; + + type Reversible_Iterator is new Graph_Iterators.Reversible_Iterator with record + My_Container : access Parse_Graph; + My_Position : Cursor; + end record; + + overriding function First + (Object : in Reversible_Iterator) + return Iter_Cursor; + + overriding function Next + (Object : in Reversible_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor; + + overriding function Last + (Object : in Reversible_Iterator) + return Iter_Cursor; + + overriding function Previous + (Object : in Reversible_Iterator; + Place : in Iter_Cursor) + return Iter_Cursor; + + end Packrat.Graphs; diff --git a/src/packrat.ads b/src/packrat.ads index 05a8e6a..d1fc9a0 100644 --- a/src/packrat.ads +++ b/src/packrat.ads @@ -191,6 +191,62 @@ package Packrat is package Interfaces is + type Node is interface; + + + function Leaf + (New_Item : in Element_Array; + Start : in Positive; + Finish : in Natural) + return Node is abstract + with Pre'Class => + Finish + 1 >= Start, + Post'Class => + Is_Leaf (Leaf'Result); + + function Branch + (Label : in Label_Enum; + Start : in Positive; + Finish : in Natural) + return Node is abstract + with Pre'Class => + Finish + 1 >= Start, + Post'Class => + Is_Branch (Branch'Result); + + + function Is_Leaf + (This : in Node) + return Boolean is abstract; + + function Is_Branch + (This : in Node) + return Boolean is abstract; + + + function Label + (This : in Node) + return Label_Enum is abstract + with Pre'Class => + This.Is_Branch; + + function Elements + (This : in Node) + return Element_Array is abstract + with Pre'Class => + This.Is_Leaf; + + function Start + (This : in Node) + return Positive is abstract; + + function Finish + (This : in Node) + return Natural is abstract; + + + + type Cursor is interface; @@ -205,12 +261,20 @@ package Packrat is with Pre'Class => not Position.Is_Nothing; + function Is_Node + (Position : in Cursor) + return Boolean is abstract + with Post'Class => + (if Is_Node'Result then not Position.Is_Nothing); + function Is_Root (Position : in Cursor) return Boolean is abstract with Post'Class => (if Is_Root'Result then - Position.Parent.Is_Nothing and Position.Depth = 0); + not Position.Is_Nothing and + Position.Parent.Is_Nothing and + Position.Depth = 0); function Is_Branch (Position : in Cursor) @@ -224,6 +288,7 @@ package Packrat is with Post'Class => (if Is_Leaf'Result then not Position.Is_Nothing); + function Label (Position : in Cursor) return Label_Enum is abstract @@ -236,7 +301,6 @@ package Packrat is with Pre'Class => Position.Is_Leaf; - function Start (Position : in Cursor) return Positive is abstract @@ -370,21 +434,11 @@ package Packrat is (if Contains'Result then not Position.Is_Nothing); - function Leaf - (New_Item : in Element_Array; - Start : in Positive; - Finish : in Natural) - return Graph is abstract - with Post'Class => - Leaf'Result.Node_Count = 1; - - function Branch - (Label : in Label_Enum; - Start : in Positive; - Finish : in Natural) + function Singleton + (Input : in Node'Class) return Graph is abstract with Post'Class => - Branch'Result.Node_Count = 1; + Singleton'Result.Node_Count = 1; function Is_Empty |