From e07aa7be550b1ecf557e554f680380dff5eef4cd Mon Sep 17 00:00:00 2001
From: Jed Barber <jjbarber@y7mail.com>
Date: Thu, 3 Dec 2020 00:08:05 +1100
Subject: Revised how root nodes are handled in parse graphs
---
src/packrat-parse_graphs.adb | 208 +++++++++++++++++++++----------------------
src/packrat-parse_graphs.ads | 73 +++++++--------
2 files changed, 131 insertions(+), 150 deletions(-)
(limited to 'src')
diff --git a/src/packrat-parse_graphs.adb b/src/packrat-parse_graphs.adb
index ef425d7..b919cff 100644
--- a/src/packrat-parse_graphs.adb
+++ b/src/packrat-parse_graphs.adb
@@ -20,12 +20,11 @@ package body Packrat.Parse_Graphs is
return Boolean
is
use type Base.Graph;
- use type Finish_Vectors.Vector;
+ use type Finished_Token_Vectors.Vector;
use type Node_Label_Maps.Map;
begin
return Left.Internal_Graph = Right.Internal_Graph and
- Left.Root_Node = Right.Root_Node and
- Left.Root_Finishes = Right.Root_Finishes and
+ Left.Root_Elems = Right.Root_Elems and
Left.Label_Map = Right.Label_Map;
end "=";
@@ -90,13 +89,35 @@ package body Packrat.Parse_Graphs is
end "<";
+ function "<"
+ (Left, Right : in Finished_Token_Vectors.Vector)
+ return Boolean
+ is
+ Left_Index : Positive := Left.First_Index;
+ Right_Index : Positive := Right.First_Index;
+ begin
+ while Left_Index <= Left.Last_Index and Right_Index <= Right.Last_Index loop
+ if Left.Element (Left_Index) < Right.Element (Right_Index) then
+ return True;
+ elsif Left.Element (Left_Index) /= Right.Element (Right_Index) then
+ return False;
+ end if;
+ Left_Index := Left_Index + 1;
+ Right_Index := Right_Index + 1;
+ end loop;
+ return Left.Length < Right.Length;
+ end "<";
+
+
function "<"
(Left, Right : in Token_Group)
- return Boolean is
+ return Boolean
+ is
+ use type Finished_Token_Vectors.Vector;
begin
if Traits.Tokens.Start (Left.Parent.Token) = Traits.Tokens.Start (Right.Parent.Token) then
if Finish (Left) = Finish (Right) then
- return Left.Elems.Element < Right.Elems.Element;
+ return Left.Elems < Right.Elems;
else
return Finish (Left) < Finish (Right);
end if;
@@ -115,8 +136,7 @@ package body Packrat.Parse_Graphs is
Source : in Parse_Graph) is
begin
Target.Internal_Graph.Assign (Source.Internal_Graph);
- Target.Root_Node := Source.Root_Node;
- Target.Root_Finishes.Assign (Source.Root_Finishes);
+ Target.Root_Elems.Assign (Source.Root_Elems);
Target.Label_Map.Assign (Source.Label_Map);
end Assign;
@@ -127,8 +147,7 @@ package body Packrat.Parse_Graphs is
begin
return G : Parse_Graph :=
(Internal_Graph => Source.Internal_Graph.Copy,
- Root_Node => Source.Root_Node,
- Root_Finishes => Source.Root_Finishes.Copy,
+ Root_Elems => Source.Root_Elems.Copy,
Label_Map => Source.Label_Map.Copy);
end Copy;
@@ -137,9 +156,7 @@ package body Packrat.Parse_Graphs is
(Target, Source : in out Parse_Graph) is
begin
Target.Internal_Graph.Move (Source.Internal_Graph);
- Target.Root_Node := Source.Root_Node;
- Source.Root_Node := Base.No_Node;
- Target.Root_Finishes.Move (Source.Root_Finishes);
+ Target.Root_Elems.Move (Source.Root_Elems);
Target.Label_Map.Move (Source.Label_Map);
end Move;
@@ -159,8 +176,7 @@ package body Packrat.Parse_Graphs is
(Container : in out Parse_Graph) is
begin
Container.Internal_Graph.Clear;
- Container.Root_Node := Base.No_Node;
- Container.Root_Finishes.Clear;
+ Container.Root_Elems.Clear;
Container.Label_Map.Clear;
end Clear;
@@ -175,10 +191,16 @@ package body Packrat.Parse_Graphs is
is
Result : Finish_Vectors.Vector;
Current : Finish_Type;
+ Node_Label : Traits.Tokens.Token;
begin
- if Node = Container.Root_Node then
- Result := Container.Root_Finishes;
- end if;
+ Node_Label := Container.Internal_Graph.Label (Node);
+ for Fin_Token of Container.Root_Elems loop
+ if Fin_Token.Token = Node_Label and then
+ not Result.Contains (Fin_Token.Finish)
+ then
+ Result.Append (Fin_Token.Finish);
+ end if;
+ end loop;
for Edge of Container.Internal_Graph.Inbound (Node) loop
Current := Container.Internal_Graph.Label (Edge).Subnode_Finish;
if not Result.Contains (Current) then
@@ -304,14 +326,12 @@ package body Packrat.Parse_Graphs is
if not Container.Contains (Position.Token) then
return False;
end if;
+ for F of Container.Root_Elements loop
+ if F = Position then
+ return True;
+ end if;
+ end loop;
Node := Container.Label_Map.Element (Position.Token);
- if Node = Container.Root_Node then
- for F of Container.Root_Finish_List loop
- if F = Position.Finish then
- return True;
- end if;
- end loop;
- end if;
return (for some Edge of Container.Internal_Graph.Inbound (Node) =>
Container.Internal_Graph.Label (Edge).Subnode_Finish = Position.Finish);
end Contains;
@@ -367,8 +387,7 @@ package body Packrat.Parse_Graphs is
(for some Fin_Token of Elements (Grouping) => Finder (Fin_Token)));
end Finder;
begin
- return (for some Finish of Container.Root_Finish_List =>
- Finder (Container.Root_Element (Finish)));
+ return (for some Fin_Token of Container.Root_Elements => Finder (Fin_Token));
end Reachable;
@@ -411,6 +430,14 @@ package body Packrat.Parse_Graphs is
end All_Reachable;
+ function Valid_Token
+ (Fin_Token : in Finished_Token)
+ return Boolean is
+ begin
+ return Fin_Token.Finish + 1 >= Traits.Tokens.Start (Fin_Token.Token);
+ end Valid_Token;
+
+
function Valid_Starts_Finishes
(Parent : in Finished_Token;
Subtokens : in Finished_Token_Array)
@@ -586,9 +613,11 @@ package body Packrat.Parse_Graphs is
if not Container.Contains (Token) then
return;
end if;
- if Container.Label_Map (Token) = Container.Root_Node then
- Container.Clear_Root;
- end if;
+ for I in reverse 1 .. Container.Root_Elems.Last_Index loop
+ if Container.Root_Elems.Element (I).Token = Token then
+ Container.Root_Elems.Delete (I);
+ end if;
+ end loop;
Container.Internal_Graph.Delete (Container.Label_Map (Token));
Container.Label_Map.Delete (Token);
end Prune;
@@ -603,14 +632,12 @@ package body Packrat.Parse_Graphs is
if not Container.Contains (Position.Token) then
return;
end if;
+ for I in reverse 1 .. Container.Root_Elems.Last_Index loop
+ if Container.Root_Elems.Element (I) = Position then
+ Container.Root_Elems.Delete (I);
+ end if;
+ end loop;
Node := Container.Label_Map.Element (Position.Token);
- if Node = Container.Root_Node then
- for I in reverse 1 .. Container.Root_Finishes.Last_Index loop
- if Container.Root_Finishes.Element (I) = Position.Finish then
- Container.Root_Finishes.Delete (I);
- end if;
- end loop;
- end if;
for Edge of Container.Internal_Graph.Inbound (Node) loop
if Container.Internal_Graph.Label (Edge).Subnode_Finish = Position.Finish then
Container.Internal_Graph.Delete (Edge);
@@ -702,61 +729,40 @@ package body Packrat.Parse_Graphs is
(Container : in Parse_Graph)
return Boolean is
begin
- return Container.Root_Node /= Base.No_Node;
+ return not Container.Root_Elems.Is_Empty;
end Has_Root;
procedure Set_Root
(Container : in out Parse_Graph;
- Token : in Traits.Tokens.Token;
- Finishes : in Finish_Array) is
+ Tokens : in Finished_Token_Array) is
begin
- Container.Root_Node := Container.Label_Map.Element (Token);
- Container.Root_Finishes.Clear;
- for F of Finishes loop
- if not Container.Root_Finishes.Contains (F) then
- Container.Root_Finishes.Append (F);
+ Container.Clear_Root;
+ for Fin_Token of Tokens loop
+ if not Container.Root_Elems.Contains (Fin_Token) then
+ Container.Root_Elems.Append (Fin_Token);
end if;
end loop;
- Finish_Sort.Sort (Container.Root_Finishes);
+ Finished_Token_Sort.Sort (Container.Root_Elems);
end Set_Root;
procedure Clear_Root
(Container : in out Parse_Graph) is
begin
- Container.Root_Node := Base.No_Node;
- Container.Root_Finishes.Clear;
+ Container.Root_Elems.Clear;
end Clear_Root;
- function Root_Token
+ function Root_Elements
(Container : in Parse_Graph)
- return Traits.Tokens.Token is
- begin
- return Container.Internal_Graph.Label (Container.Root_Node);
- end Root_Token;
-
-
- function Root_Finish_List
- (Container : in Parse_Graph)
- return Finish_Array
+ return Finished_Token_Array
is
- function V2A is new Vector_To_Array (Finish_Type, Finish_Array, Finish_Vectors);
- begin
- return V2A (Container.Root_Finishes);
- end Root_Finish_List;
-
-
- function Root_Element
- (Container : in Parse_Graph;
- Finish_At : in Finish_Type)
- return Finished_Token is
+ function V2A is new Vector_To_Array
+ (Finished_Token, Finished_Token_Array, Finished_Token_Vectors);
begin
- return Root : Finished_Token :=
- (Token => Container.Internal_Graph.Label (Container.Root_Node),
- Finish => Finish_At);
- end Root_Element;
+ return V2A (Container.Root_Elems);
+ end Root_Elements;
@@ -770,6 +776,11 @@ package body Packrat.Parse_Graphs is
function V2A is new Vector_To_Array (Finish_Type, Finish_Array, Finish_Vectors);
Result : Finish_Vectors.Vector;
begin
+ for Fin_Token of Container.Root_Elems loop
+ if Fin_Token.Token = Token and not Result.Contains (Fin_Token.Finish) then
+ Result.Append (Fin_Token.Finish);
+ end if;
+ end loop;
for Edge of Container.Internal_Graph.Outbound (Container.Label_Map.Element (Token)) loop
if not Result.Contains (Container.Internal_Graph.Label (Edge).Group_Finish) then
Result.Append (Container.Internal_Graph.Label (Edge).Group_Finish);
@@ -813,8 +824,6 @@ package body Packrat.Parse_Graphs is
Position : in Finished_Token)
return Token_Group_Array
is
- function V2A is new Vector_To_Array
- (Finished_Token, Finished_Token_Array, Finished_Token_Vectors);
function V2A is new Vector_To_Array
(Token_Group, Token_Group_Array, Token_Group_Vectors);
Groupings : Group_Finished_Token_Maps.Map;
@@ -840,7 +849,7 @@ package body Packrat.Parse_Graphs is
Finished_Token_Sort.Sort (Raw_Group);
Result.Append
((Parent => Position,
- Elems => Finished_Token_Array_Holders.To_Holder (V2A (Raw_Group))));
+ Elems => Raw_Group));
end loop;
Token_Group_Sort.Sort (Result);
return V2A (Result);
@@ -851,7 +860,7 @@ package body Packrat.Parse_Graphs is
(Grouping : in Token_Group)
return Positive is
begin
- return Grouping.Elems.Constant_Reference.Element'First;
+ return Grouping.Elems.First_Index;
end First_Index;
@@ -859,7 +868,7 @@ package body Packrat.Parse_Graphs is
(Grouping : in Token_Group)
return Positive is
begin
- return Grouping.Elems.Constant_Reference.Element'Last;
+ return Grouping.Elems.Last_Index;
end Last_Index;
@@ -867,8 +876,7 @@ package body Packrat.Parse_Graphs is
(Grouping : in Token_Group)
return Ada.Containers.Count_Type is
begin
- return Ada.Containers.Count_Type
- (Grouping.Elems.Constant_Reference.Element'Length);
+ return Grouping.Elems.Length;
end Length;
@@ -877,15 +885,18 @@ package body Packrat.Parse_Graphs is
Index : in Positive)
return Finished_Token is
begin
- return Grouping.Elems.Constant_Reference.Element (Index);
+ return Grouping.Elems.Element (Index);
end Element;
function Elements
(Grouping : in Token_Group)
- return Finished_Token_Array is
+ return Finished_Token_Array
+ is
+ function V2A is new Vector_To_Array
+ (Finished_Token, Finished_Token_Array, Finished_Token_Vectors);
begin
- return Grouping.Elems.Element;
+ return V2A (Grouping.Elems);
end Elements;
@@ -913,27 +924,8 @@ package body Packrat.Parse_Graphs is
return Boolean
is
use type Ada.Containers.Count_Type;
- First_Group : Group_ID_Type;
- Seen_Group : Boolean := False;
- Check_Label : Edge_Label_Type;
begin
- if Container.Root_Finishes.Length = 0 then
- return False;
- elsif Container.Root_Finishes.Length > 1 then
- return True;
- end if;
- for Edge of Container.Internal_Graph.Outbound (Container.Root_Node) loop
- Check_Label := Container.Internal_Graph.Label (Edge);
- if Container.Root_Finishes.Contains (Check_Label.Group_Finish) then
- if not Seen_Group then
- Seen_Group := True;
- First_Group := Check_Label.Group_ID;
- elsif Check_Label.Group_ID /= First_Group then
- return True;
- end if;
- end if;
- end loop;
- return False;
+ return Container.Root_Elems.Length /= 1;
end Is_Root_Ambiguous;
@@ -1104,19 +1096,19 @@ package body Packrat.Parse_Graphs is
(Left, Right : in Parse_Graph)
return Boolean
is
+ use type Ada.Containers.Count_Type;
Offset : Integer :=
- Traits.Tokens.Start (Right.Root_Token) - Traits.Tokens.Start (Left.Root_Token);
- Left_Finishes : Finish_Array := Left.Root_Finish_List;
- Right_Finishes : Finish_Array := Right.Root_Finish_List;
+ Traits.Tokens.Start (Right.Root_Elems.Element (1).Token) -
+ Traits.Tokens.Start (Left.Root_Elems.Element (1).Token);
Mapping : Isomorph_Maps.Map;
begin
- if Left_Finishes'Length /= Right_Finishes'Length then
+ if Left.Root_Elems.Length /= Right.Root_Elems.Length then
return False;
end if;
- return (for all Index in Left_Finishes'Range =>
+ return (for all Index in 1 .. Left.Root_Elems.Last_Index =>
Token_Isomorph
- (Left, (Left.Root_Token, Left_Finishes (Index)),
- Right, (Right.Root_Token, Right_Finishes (Index)),
+ (Left, Left.Root_Elems (Index),
+ Right, Right.Root_Elems (Index),
Offset, Mapping));
end Isomorphic;
diff --git a/src/packrat-parse_graphs.ads b/src/packrat-parse_graphs.ads
index fc5861d..4d2d956 100644
--- a/src/packrat-parse_graphs.ads
+++ b/src/packrat-parse_graphs.ads
@@ -7,7 +7,6 @@ with
private with
- Ada.Containers.Indefinite_Holders,
Ada.Containers.Vectors,
Ada.Containers.Ordered_Maps,
Directed_Graphs;
@@ -131,6 +130,10 @@ package Packrat.Parse_Graphs is
return Boolean
with Pre => Container.Has_Root;
+ function Valid_Token
+ (Fin_Token : in Finished_Token)
+ return Boolean;
+
function Valid_Starts_Finishes
(Parent : in Finished_Token;
Subtokens : in Finished_Token_Array)
@@ -214,35 +217,19 @@ package Packrat.Parse_Graphs is
procedure Set_Root
(Container : in out Parse_Graph;
- Token : in Traits.Tokens.Token;
- Finishes : in Finish_Array)
- with Pre => Container.Contains (Token) and
- (for all F of Finishes => F >= Traits.Tokens.Start (Token) - 1),
+ Tokens : in Finished_Token_Array)
+ with Pre => (for all F of Tokens => Container.Contains (F.Token)),
Post => Container.Has_Root;
procedure Clear_Root
(Container : in out Parse_Graph)
with Post => not Container.Has_Root;
- function Root_Token
+ function Root_Elements
(Container : in Parse_Graph)
- return Traits.Tokens.Token
+ return Finished_Token_Array
with Pre => Container.Has_Root;
- function Root_Finish_List
- (Container : in Parse_Graph)
- return Finish_Array
- with Pre => Container.Has_Root,
- Post => Is_Sorted (Root_Finish_List'Result) and
- No_Duplicates (Root_Finish_List'Result);
-
- function Root_Element
- (Container : in Parse_Graph;
- Finish_At : in Finish_Type)
- return Finished_Token
- with Pre => Container.Has_Root and then
- (for some F of Container.Root_Finish_List => F = Finish_At);
-
@@ -408,6 +395,24 @@ private
+
+ package Finished_Token_Vectors is new Ada.Containers.Vectors
+ (Index_Type => Positive,
+ Element_Type => Finished_Token);
+
+ function "<"
+ (Left, Right : in Finished_Token_Vectors.Vector)
+ return Boolean;
+
+ type Token_Group is record
+ Parent : Finished_Token;
+ Elems : Finished_Token_Vectors.Vector;
+ end record;
+
+
+
+
+
package Finish_Vectors is new Ada.Containers.Vectors
(Index_Type => Positive,
Element_Type => Finish_Type);
@@ -419,21 +424,9 @@ private
Element_Type => Node_ID_Type);
type Parse_Graph is tagged record
- Internal_Graph : Base.Graph := Base.Empty_Graph;
- Root_Node : Base.Extended_Node_ID_Type := Base.No_Node;
- Root_Finishes : Finish_Vectors.Vector := Finish_Vectors.Empty_Vector;
- Label_Map : Node_Label_Maps.Map := Node_Label_Maps.Empty_Map;
- end record;
-
-
-
-
- package Finished_Token_Array_Holders is new Ada.Containers.Indefinite_Holders
- (Element_Type => Finished_Token_Array);
-
- type Token_Group is record
- Parent : Finished_Token;
- Elems : Finished_Token_Array_Holders.Holder;
+ Internal_Graph : Base.Graph := Base.Empty_Graph;
+ Root_Elems : Finished_Token_Vectors.Vector := Finished_Token_Vectors.Empty_Vector;
+ Label_Map : Node_Label_Maps.Map := Node_Label_Maps.Empty_Map;
end record;
@@ -448,10 +441,6 @@ private
(Index_Type => Positive,
Element_Type => Group_ID_Type);
- package Finished_Token_Vectors is new Ada.Containers.Vectors
- (Index_Type => Positive,
- Element_Type => Finished_Token);
-
package Token_Group_Vectors is new Ada.Containers.Vectors
(Index_Type => Positive,
Element_Type => Token_Group);
@@ -476,6 +465,7 @@ private
+
package Isomorph_Maps is new Ada.Containers.Ordered_Maps
(Key_Type => Finished_Token,
Element_Type => Finished_Token_Vectors.Vector,
@@ -504,8 +494,7 @@ private
Empty_Graph : constant Parse_Graph :=
(Internal_Graph => Base.Empty_Graph,
- Root_Node => Base.No_Node,
- Root_Finishes => Finish_Vectors.Empty_Vector,
+ Root_Elems => Finished_Token_Vectors.Empty_Vector,
Label_Map => Node_Label_Maps.Empty_Map);
--
cgit