From ada2593ebd6037cb78ce1ba795f283105d5cff26 Mon Sep 17 00:00:00 2001
From: Jed Barber <jjbarber@y7mail.com>
Date: Sat, 26 Jan 2019 10:50:36 +1100
Subject: Interfaces for Cursors and Graphs added

---
 packrat_parser_lib_notes.txt |  64 +++++++-
 src/packrat-graphs.adb       | 371 +++++++++++++++++++++++++++++++++++++++++++
 src/packrat-graphs.ads       | 235 +++++++++++++++++++++++++++
 src/packrat.ads              | 289 +++++++++++++++++++++++++++++++++
 4 files changed, 958 insertions(+), 1 deletion(-)
 create mode 100644 src/packrat-graphs.adb
 create mode 100644 src/packrat-graphs.ads

diff --git a/packrat_parser_lib_notes.txt b/packrat_parser_lib_notes.txt
index 1ae9707..333b999 100644
--- a/packrat_parser_lib_notes.txt
+++ b/packrat_parser_lib_notes.txt
@@ -9,7 +9,8 @@ Packrat.Lexer (generic over stamp enum, input item type, array of input items, a
 Packrat.Lexer.Combinators (merged into Packrat.Lexer)
 Packrat.Util
 Packrat.Errors (nested)
-Packrat.Graphs (nested, generic over leaf array type)
+Packrat.Interfaces (nested)
+Packrat.Graphs (generic over leaf array type)
 Packrat.Tokens (nested, generic over contained array)
 Packrat.Text
 Packrat.Text.Std (nested, generic over parser/lexer label enums)
@@ -308,14 +309,75 @@ Finish
 
 
 
+Packrat.Interfaces
+ - nested package, defines interfaces and types that should be used to derive an abstract syntax graph
+ - some of these may be removed from Interfaces and just implemented in Graphs depending on what actually
+   ends up being necessary for parsing
+
+List of interfaces:
+Cursor
+ - Is_Nothing
+ - Depth
+ - Is_Root
+ - Is_Branch
+ - Is_Leaf
+ - Label
+ - Elements
+ - Start
+ - Finish
+ - Choices
+ - Parent
+ - Child_Count
+ - All_Child_Count
+ - First_Child
+ - Last_Child
+ - Next_Sibling
+ - Prev_Sibling
+ - Delete_Children
+ - Delete_All_Children
+ - Equal_Subgraph
+ - Subgraph_Node_Count
+ - Find_In_Subgraph
+
+Directed_Acyclic_Graph
+ - Contains
+ - Leaf
+ - Branch
+ - Is_Empty
+ - Is_Ambiguous
+ - Node_Count
+ - Root_Count
+ - Root
+ - Append
+ - Prepend
+ - Attach_Choice
+ - Clear
+ - Delete_Position
+ - Find
+
+
+
+
 Packrat.Graphs
+ - builds on the interfaces in Packrat.Interfaces
+ - 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)
 
 List of funcs:
 Debug_String
 
+Iterate
+Reverse_Iterate
+Iterate_Choice
+Reverse_Iterate_Choice
+Iterate_SUbtree
+Iterate_Subtree_Choice
+
 
 
 
diff --git a/src/packrat-graphs.adb b/src/packrat-graphs.adb
new file mode 100644
index 0000000..2cf74b3
--- /dev/null
+++ b/src/packrat-graphs.adb
@@ -0,0 +1,371 @@
+
+
+package body Packrat.Graphs is
+
+
+    function Is_Nothing
+           (Position : in Cursor)
+        return Boolean is
+    begin
+        return True;
+    end Is_Nothing;
+
+
+
+
+
+    function Depth
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end Depth;
+
+
+    function Is_Root
+           (Position : in Cursor)
+        return Boolean is
+    begin
+        return False;
+    end Is_Root;
+
+
+    function Is_Branch
+           (Position : in Cursor)
+        return Boolean is
+    begin
+        return False;
+    end Is_Branch;
+
+
+    function Is_Leaf
+           (Position : in Cursor)
+        return Boolean is
+    begin
+        return False;
+    end Is_Leaf;
+
+
+    function Label
+           (Position : in Cursor)
+        return Label_Enum is
+    begin
+        return Label_Enum'First;
+    end Label;
+
+
+    function Elements
+           (Position : in Cursor)
+        return Element_Array
+    is
+        Empty : Element_Array (1 .. 0);
+    begin
+        return Empty;
+    end Elements;
+
+
+
+
+
+    function Start
+           (Position : in Cursor)
+        return Positive is
+    begin
+        return 1;
+    end Start;
+
+
+    function Finish
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end Finish;
+
+
+    function Choices
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end Choices;
+
+
+
+
+
+    function Parent
+           (Position : in Cursor)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Parent;
+
+
+    function Child_Count
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Natural is
+    begin
+        return 0;
+    end Child_Count;
+
+
+    function Child_Count
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end Child_Count;
+
+
+    function All_Child_Count
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end All_Child_Count;
+
+
+    function First_Child
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end First_Child;
+
+
+    function Last_Child
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Last_Child;
+
+
+    function First_Child
+           (Position : in Cursor)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end First_Child;
+
+
+    function Last_Child
+           (Position : in Cursor)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Last_Child;
+
+
+    function Next_Sibling
+           (Position : in Cursor)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Next_Sibling;
+
+
+    function Prev_Sibling
+           (Position : in Cursor)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Prev_Sibling;
+
+
+    procedure Delete_Children
+           (Position : in out Cursor;
+            Choice   : in     Positive) is
+    begin
+        null;
+    end Delete_Children;
+
+
+    procedure Delete_Children
+           (Position : in out Cursor) is
+    begin
+        null;
+    end Delete_Children;
+
+
+    procedure Delete_All_Children
+           (Position : in out Cursor) is
+    begin
+        null;
+    end Delete_All_Children;
+
+
+
+
+
+    function Equal_Subgraph
+           (Left, Right : in Cursor)
+        return Boolean is
+    begin
+        return False;
+    end Equal_Subgraph;
+
+
+    function Subgraph_Node_Count
+           (Position : in Cursor)
+        return Natural is
+    begin
+        return 0;
+    end Subgraph_Node_Count;
+
+
+    function Find_In_Subgraph
+           (Position : in Cursor;
+            Item     : in Element_Array)
+        return Cursor is
+    begin
+        return This : Cursor;
+    end Find_In_Subgraph;
+
+
+
+
+
+    function Contains
+           (Container : in Parse_Graph;
+            Position  : in My_Interfaces.Cursor'Class)
+        return Boolean is
+    begin
+        return False;
+    end Contains;
+
+
+
+
+    function Leaf
+           (New_Item : in Element_Array;
+            Start    : in Positive;
+            Finish   : in Natural)
+        return Parse_Graph is
+    begin
+        return This : Parse_Graph;
+    end Leaf;
+
+
+    function Branch
+           (Label  : in Label_Enum;
+            Start  : in Positive;
+            Finish : in Natural)
+        return Parse_Graph is
+    begin
+        return This : Parse_Graph;
+    end Branch;
+
+
+
+
+
+    function Is_Empty
+           (Container : in Parse_Graph)
+        return Boolean is
+    begin
+        return True;
+    end Is_Empty;
+
+
+    function Is_Ambiguous
+           (Container : in Parse_Graph)
+        return Boolean is
+    begin
+        return False;
+    end Is_Ambiguous;
+
+
+    function Node_Count
+           (Container : in Parse_Graph)
+        return Natural is
+    begin
+        return 0;
+    end Node_Count;
+
+
+
+
+
+    function Root_Count
+           (Container : in Parse_Graph)
+        return Natural is
+    begin
+        return 0;
+    end Root_Count;
+
+
+    function Root
+           (Container : in Parse_Graph;
+            Index     : in Positive)
+        return My_Interfaces.Cursor'Class is
+    begin
+        return This : Cursor;
+    end Root;
+
+
+
+
+
+    procedure Append
+           (Container : in out Parse_Graph;
+            Addition  : in     Parse_Graph) is
+    begin
+        null;
+    end Append;
+
+
+    procedure Prepend
+           (Container : in out Parse_Graph;
+            Addition  : in     Parse_Graph) is
+    begin
+        null;
+    end Prepend;
+
+
+    procedure Attach_Choice
+           (Container : in out Parse_Graph;
+            Position  : in     My_Interfaces.Cursor'Class;
+            Addition  : in     Parse_Graph) is
+    begin
+        null;
+    end Attach_Choice;
+
+
+
+
+
+    procedure Clear
+           (Container : in out Parse_Graph) is
+    begin
+        null;
+    end Clear;
+
+
+    procedure Delete_Position
+           (Container : in out Parse_Graph;
+            Position  : in out My_Interfaces.Cursor'Class) is
+    begin
+        null;
+    end Delete_Position;
+
+
+
+
+
+    function Find
+           (Container : in Parse_Graph;
+            Item      : in Element_Array)
+        return My_Interfaces.Cursor'Class is
+    begin
+        return This : Cursor;
+    end Find;
+
+
+end Packrat.Graphs;
+
+
diff --git a/src/packrat-graphs.ads b/src/packrat-graphs.ads
new file mode 100644
index 0000000..4095360
--- /dev/null
+++ b/src/packrat-graphs.ads
@@ -0,0 +1,235 @@
+
+
+generic
+    type Label_Enum is (<>);
+    type Element is private;
+    type Element_Array is array (Positive range <>) of Element;
+    with package My_Interfaces is new Interfaces (Label_Enum, Element, Element_Array);
+package Packrat.Graphs is
+
+
+
+    type Cursor is new My_Interfaces.Cursor with private;
+
+    type Parse_Graph is new My_Interfaces.Graph with private;
+
+
+
+
+    function Is_Nothing
+           (Position : in Cursor)
+        return Boolean;
+
+
+
+
+    function Depth
+           (Position : in Cursor)
+        return Natural;
+
+    function Is_Root
+           (Position : in Cursor)
+        return Boolean;
+
+    function Is_Branch
+           (Position : in Cursor)
+        return Boolean;
+
+    function Is_Leaf
+           (Position : in Cursor)
+        return Boolean;
+
+    function Label
+           (Position : in Cursor)
+        return Label_Enum;
+
+    function Elements
+           (Position : in Cursor)
+        return Element_Array;
+
+
+
+
+    function Start
+           (Position : in Cursor)
+        return Positive;
+
+    function Finish
+           (Position : in Cursor)
+        return Natural;
+
+    function Choices
+           (Position : in Cursor)
+        return Natural;
+
+
+
+
+    function Parent
+           (Position : in Cursor)
+        return Cursor;
+
+    function Child_Count
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Natural;
+
+    function Child_Count
+           (Position : in Cursor)
+        return Natural;
+
+    function All_Child_Count
+           (Position : in Cursor)
+        return Natural;
+
+    function First_Child
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Cursor;
+
+    function Last_Child
+           (Position : in Cursor;
+            Choice   : in Positive)
+        return Cursor;
+
+    function First_Child
+           (Position : in Cursor)
+        return Cursor;
+
+    function Last_Child
+           (Position : in Cursor)
+        return Cursor;
+
+    function Next_Sibling
+           (Position : in Cursor)
+        return Cursor;
+
+    function Prev_Sibling
+           (Position : in Cursor)
+        return Cursor;
+
+    procedure Delete_Children
+           (Position : in out Cursor;
+            Choice   : in     Positive);
+
+    procedure Delete_Children
+           (Position : in out Cursor);
+
+    procedure Delete_All_Children
+           (Position : in out Cursor);
+
+
+
+
+    function Equal_Subgraph
+           (Left, Right : in Cursor)
+        return Boolean;
+
+    function Subgraph_Node_Count
+           (Position : in Cursor)
+        return Natural;
+
+    function Find_In_Subgraph
+           (Position : in Cursor;
+            Item     : in Element_Array)
+        return Cursor;
+
+
+
+
+    function Contains
+           (Container : in Parse_Graph;
+            Position  : in My_Interfaces.Cursor'Class)
+        return Boolean;
+
+
+
+
+    function Leaf
+           (New_Item : in Element_Array;
+            Start    : in Positive;
+            Finish   : in Natural)
+        return Parse_Graph;
+
+    function Branch
+           (Label  : in Label_Enum;
+            Start  : in Positive;
+            Finish : in Natural)
+        return Parse_Graph;
+
+
+
+
+    function Is_Empty
+           (Container : in Parse_Graph)
+        return Boolean;
+
+    function Is_Ambiguous
+           (Container : in Parse_Graph)
+        return Boolean;
+
+    function Node_Count
+           (Container : in Parse_Graph)
+        return Natural;
+
+
+
+
+    function Root_Count
+           (Container : in Parse_Graph)
+        return Natural;
+
+    function Root
+           (Container : in Parse_Graph;
+            Index     : in Positive)
+        return My_Interfaces.Cursor'Class;
+
+
+
+
+    procedure Append
+           (Container : in out Parse_Graph;
+            Addition  : in     Parse_Graph);
+
+    procedure Prepend
+           (Container : in out Parse_Graph;
+            Addition  : in     Parse_Graph);
+
+    procedure Attach_Choice
+           (Container : in out Parse_Graph;
+            Position  : in     My_Interfaces.Cursor'Class;
+            Addition  : in     Parse_Graph);
+
+
+
+
+    procedure Clear
+           (Container : in out Parse_Graph);
+
+    procedure Delete_Position
+           (Container : in out Parse_Graph;
+            Position  : in out My_Interfaces.Cursor'Class);
+
+
+
+
+    function Find
+           (Container : in Parse_Graph;
+            Item      : in Element_Array)
+        return My_Interfaces.Cursor'Class;
+
+
+
+
+private
+
+
+    type Cursor is new My_Interfaces.Cursor with null record;
+
+
+    type Parse_Graph is new My_Interfaces.Graph with null record;
+
+
+end Packrat.Graphs;
+
+
diff --git a/src/packrat.ads b/src/packrat.ads
index 0ee8463..05a8e6a 100644
--- a/src/packrat.ads
+++ b/src/packrat.ads
@@ -182,6 +182,295 @@ package Packrat is
     end Tokens;
 
 
+
+
+    generic
+        type Label_Enum is (<>);
+        type Element is private;
+        type Element_Array is array (Positive range <>) of Element;
+    package Interfaces is
+
+
+        type Cursor is interface;
+
+
+        function Is_Nothing
+               (Position : in Cursor)
+            return Boolean is abstract;
+
+
+        function Depth
+               (Position : in Cursor)
+            return Natural is abstract
+        with Pre'Class =>
+                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);
+
+        function Is_Branch
+               (Position : in Cursor)
+            return Boolean is abstract
+        with Post'Class =>
+               (if Is_Branch'Result then not Position.Is_Nothing);
+
+        function Is_Leaf
+               (Position : in Cursor)
+            return Boolean is abstract
+        with Post'Class =>
+               (if Is_Leaf'Result then not Position.Is_Nothing);
+
+        function Label
+               (Position : in Cursor)
+            return Label_Enum is abstract
+        with Pre'Class =>
+                Position.Is_Branch;
+
+        function Elements
+               (Position : in Cursor)
+            return Element_Array is abstract
+        with Pre'Class =>
+                Position.Is_Leaf;
+
+
+        function Start
+               (Position : in Cursor)
+            return Positive is abstract
+        with Pre'Class =>
+                not Position.Is_Nothing;
+
+        function Finish
+               (Position : in Cursor)
+            return Natural is abstract
+        with Pre'Class =>
+                not Position.Is_Nothing;
+
+        function Choices
+               (Position : in Cursor)
+            return Natural is abstract;
+
+
+        function Parent
+               (Position : in Cursor)
+            return Cursor is abstract;
+
+        function Child_Count
+               (Position : in Cursor;
+                Choice   : in Positive)
+            return Natural is abstract
+        with Pre'Class =>
+                Choice <= Position.Choices;
+
+        function Child_Count
+               (Position : in Cursor)
+            return Natural is abstract;
+
+        function All_Child_Count
+               (Position : in Cursor)
+            return Natural is abstract;
+
+        function First_Child
+               (Position : in Cursor;
+                Choice   : in Positive)
+            return Cursor is abstract
+        with Pre'Class =>
+                Choice <= Position.Choices,
+            Post'Class =>
+                First_Child'Result.Is_Nothing or
+                First_Child'Result.Parent = Position;
+
+        function Last_Child
+               (Position : in Cursor;
+                Choice   : in Positive)
+            return Cursor is abstract
+        with Pre'Class =>
+                Choice <= Position.Choices,
+            Post'Class =>
+                Last_Child'Result.Is_Nothing or
+                Last_Child'Result.Parent = Position;
+
+        function First_Child
+               (Position : in Cursor)
+            return Cursor is abstract
+        with Post'Class =>
+                First_Child'Result.Is_Nothing or
+                First_Child'Result.Parent = Position;
+
+        function Last_Child
+               (Position : in Cursor)
+            return Cursor is abstract
+        with Post'Class =>
+                Last_Child'Result.Is_Nothing or
+                Last_Child'Result.Parent = Position;
+
+        function Next_Sibling
+               (Position : in Cursor)
+            return Cursor is abstract
+        with Post'Class =>
+                Next_Sibling'Result.Is_Nothing or
+                Next_Sibling'Result.Parent = Position.Parent;
+
+        function Prev_Sibling
+               (Position : in Cursor)
+            return Cursor is abstract
+        with Post'Class =>
+                Prev_Sibling'Result.Is_Nothing or
+                Prev_Sibling'Result.Parent = Position.Parent;
+
+        procedure Delete_Children
+               (Position : in out Cursor;
+                Choice   : in     Positive) is abstract
+        with Pre'Class =>
+                Choice <= Position.Choices,
+            Post'Class =>
+                Position.Child_Count (Choice) = 0;
+
+        procedure Delete_Children
+               (Position : in out Cursor) is abstract
+        with Post'Class =>
+                Position.Child_Count = 0;
+
+        procedure Delete_All_Children
+               (Position : in out Cursor) is abstract
+        with Post'Class =>
+                Position.All_Child_Count = 0;
+
+
+        function Equal_Subgraph
+               (Left, Right : in Cursor)
+            return Boolean is abstract;
+
+        function Subgraph_Node_Count
+               (Position : in Cursor)
+            return Natural is abstract;
+
+        function Find_In_Subgraph
+               (Position : in Cursor;
+                Item     : in Element_Array)
+            return Cursor is abstract
+        with Post'Class =>
+                Find_In_Subgraph'Result.Is_Nothing or
+                Find_In_Subgraph'Result.Is_Leaf;
+
+
+
+
+        type Graph is interface;
+
+
+        function Contains
+               (Container : in Graph;
+                Position  : in Cursor'Class)
+            return Boolean is abstract
+        with Post'Class =>
+               (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)
+            return Graph is abstract
+        with Post'Class =>
+                Branch'Result.Node_Count = 1;
+
+
+        function Is_Empty
+               (Container : in Graph)
+            return Boolean is abstract
+        with Post'Class =>
+                (if Is_Empty'Result then Container.Node_Count = 0 else Container.Node_Count /= 0);
+
+        function Is_Ambiguous
+               (Container : in Graph)
+            return Boolean is abstract;
+
+        function Node_Count
+               (Container : in Graph)
+            return Natural is abstract;
+
+
+        function Root_Count
+               (Container : in Graph)
+            return Natural is abstract
+        with Post'Class =>
+                (if Container.Is_Empty then Root_Count'Result = 0 else Root_Count'Result > 0);
+
+        function Root
+               (Container : in Graph;
+                Index     : in Positive)
+            return Cursor'Class is abstract
+        with Pre'Class =>
+                Index <= Container.Root_Count;
+
+
+        procedure Append
+               (Container : in out Graph;
+                Addition  : in     Graph) is abstract
+        with Pre'Class =>
+                Container.Is_Empty or else Addition.Is_Empty or else
+                Container.Root (Container.Root_Count).Finish <
+                    Addition.Root (1).Start;
+
+        procedure Prepend
+               (Container : in out Graph;
+                Addition  : in     Graph) is abstract
+        with Pre'Class =>
+                Container.Is_Empty or else Addition.Is_Empty or else
+                Container.Root (1).Start >
+                    Addition.Root (Addition.Root_Count).Finish;
+
+        procedure Attach_Choice
+               (Container : in out Graph;
+                Position  : in     Cursor'Class;
+                Addition  : in     Graph) is abstract
+        with Pre'Class =>
+                Container.Contains (Position) and Position.Is_Branch and
+                (Addition.Is_Empty or else
+                   (Position.Start <= Addition.Root (1).Start and
+                    Position.Finish >= Addition.Root (Addition.Root_Count).Finish));
+
+
+        procedure Clear
+               (Container : in out Graph) is abstract
+        with Post'Class =>
+                Container.Is_Empty;
+
+        procedure Delete_Position
+               (Container : in out Graph;
+                Position  : in out Cursor'Class) is abstract
+        with Pre'Class =>
+                Container.Contains (Position),
+            Post'Class =>
+                not Container.Contains (Position);
+
+
+        function Find
+               (Container : in Graph;
+                Item      : in Element_Array)
+            return Cursor'Class is abstract
+        with Post'Class =>
+                Find'Result.Is_Leaf or
+                Find'Result.Is_Nothing;
+
+
+    end Interfaces;
+
+
+
+
 private
 
 
-- 
cgit