summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--packrat_parser_lib_notes.txt64
-rw-r--r--src/packrat-graphs.adb371
-rw-r--r--src/packrat-graphs.ads235
-rw-r--r--src/packrat.ads289
4 files changed, 958 insertions, 1 deletions
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
generated by cgit (git 2.30.0) at 2024-12-22 21:54:16 +0000