diff options
Diffstat (limited to 'src/packrat-parse_graphs.adb')
| -rw-r--r-- | src/packrat-parse_graphs.adb | 208 |
1 files changed, 100 insertions, 108 deletions
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 "="; @@ -91,12 +90,34 @@ package body Packrat.Parse_Graphs is 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); @@ -814,8 +825,6 @@ package body Packrat.Parse_Graphs is 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; Edge_Label : Edge_Label_Type; @@ -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; |