summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2019-01-27 19:08:11 +1100
committerJed Barber <jjbarber@y7mail.com>2019-01-27 19:08:11 +1100
commit6f15340717a5d2dccdcf8de0a03a161c5abeef70 (patch)
tree3c67b46cd243ec72d80eb2388dc7f6e8090d77b3
parentada2593ebd6037cb78ce1ba795f283105d5cff26 (diff)
Iteration specifications added for Parse_Graphs
-rw-r--r--packrat_parser_lib_notes.txt32
-rw-r--r--src/packrat-graphs.adb214
-rw-r--r--src/packrat-graphs.ads180
-rw-r--r--src/packrat.ads84
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