From 84696069475bfa7732326dee94a2c8a852ece827 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Thu, 12 Nov 2020 17:06:06 +1100 Subject: Outline of tests for Parse_Graphs --- src/packrat-parse_graphs.adb | 1 + src/packrat-parse_graphs.ads | 4 +- src/packrat.ads | 4 + test/rat_tests-parse_graphs.adb | 476 +++++++++++++++++++++++++++++++++++----- test/rat_tests-parse_graphs.ads | 101 ++++++++- test/test_main.adb | 10 +- 6 files changed, 525 insertions(+), 71 deletions(-) diff --git a/src/packrat-parse_graphs.adb b/src/packrat-parse_graphs.adb index 1705d36..eed2eee 100644 --- a/src/packrat-parse_graphs.adb +++ b/src/packrat-parse_graphs.adb @@ -259,6 +259,7 @@ package body Packrat.Parse_Graphs is SU.Delete (Result, SU.Length (Result), SU.Length (Result)); end loop; -- what delete goes here? + SU.Append (Result, Latin.LF); end loop; return SU.To_String (Result); end Debug_String; diff --git a/src/packrat-parse_graphs.ads b/src/packrat-parse_graphs.ads index 2912110..de5e4e9 100644 --- a/src/packrat-parse_graphs.ads +++ b/src/packrat-parse_graphs.ads @@ -68,8 +68,8 @@ package Packrat.Parse_Graphs is (Left, Right : in Finished_Token_Array) return Boolean; - type Token_Group is private with Type_Invariant => - Ada.Containers.">" (Length (Token_Group), 0); + use type Ada.Containers.Count_Type; + type Token_Group is private with Type_Invariant => Length (Token_Group) > 0; type Token_Group_Array is array (Positive range <>) of Token_Group; function "<" diff --git a/src/packrat.ads b/src/packrat.ads index 6032cb1..58afbaa 100644 --- a/src/packrat.ads +++ b/src/packrat.ads @@ -20,6 +20,10 @@ package Packrat is + -- need to restructure all this to separate these nested packages out into their own files + -- and also to add in a Traits package to contain the Enum/Element/Array generic stuff + + package Errors is diff --git a/test/rat_tests-parse_graphs.adb b/test/rat_tests-parse_graphs.adb index 074bc27..701fbfc 100644 --- a/test/rat_tests-parse_graphs.adb +++ b/test/rat_tests-parse_graphs.adb @@ -11,114 +11,470 @@ package body Rat_Tests.Parse_Graphs is Prepositional_Phrase, Verb, Verb_Phrase, Sentence); package String_Tokens is new Packrat.Tokens (My_Labels, Character, String); - package Graphs is new Packrat.Parse_Graphs (My_Labels, Character, String, String_Tokens); + package Graphs is new Packrat.Parse_Graphs (My_Labels, Character, String, "<", String_Tokens); - Paper_Nodes : Graphs.Node_Array := - (1, -- Noun at position 1, value "i" - 2, -- Noun at position 4, value "man" - 3, -- Noun at position 7, value "park" - 4, -- Noun at position 10, value "bat" - 5, -- Determiner at position 3, value "a" - 6, -- Determiner at position 6, value "the" - 7, -- Determiner at position 9, value "a" - 8, -- Noun_Phrase at position 1 - 9, -- Noun_Phrase at position 3 - 10, -- Noun_Phrase at position 6 - 11, -- Noun_Phrase at position 9 - 12, -- Preposition at position 5, value "in" - 13, -- Preposition at position 8, value "with" - 14, -- Prepositional_Phrase at position 5 - 15, -- Prepositional_Phrase at position 8 - 16, -- Verb at position 2, value "saw" - 17, -- Verb_Phrase at position 2 - 18); -- Sentence at position 1 + -- These tokens are defined here purely to reduce verbosity when + -- manually constructing the various test graphs in the package initialisation. + Noun_1 : String_Tokens.Token := String_Tokens.Create (Noun, 1, "i"); + Noun_4 : String_Tokens.Token := String_Tokens.Create (Noun, 4, "man"); + Noun_7 : String_Tokens.Token := String_Tokens.Create (Noun, 7, "park"); + Noun_10 : String_Tokens.Token := String_Tokens.Create (Noun, 10, "bat"); - -- Cursors in Directed Graph library should be tagged - -- This will allow creation of an extended Cursor type in Parse Graphs - -- Edge labels need to contain group, finish, order, and restrict - -- The extended Cursor type should take the restrict into account with its functions + Det_3 : String_Tokens.Token := String_Tokens.Create (Determiner, 3, "a"); + Det_6 : String_Tokens.Token := String_Tokens.Create (Determiner, 6, "the"); + Det_9 : String_Tokens.Token := String_Tokens.Create (Determiner, 9, "a"); - -- There should be a validity checking function for Parse Graphs - -- There should also be a pretty print debug function for Parse Graphs + NP_1 : String_Tokens.Token := String_Tokens.Create (Noun_Phrase, 1, ""); + NP_3 : String_Tokens.Token := String_Tokens.Create (Noun_Phrase, 3, ""); + NP_6 : String_Tokens.Token := String_Tokens.Create (Noun_Phrase, 6, ""); + NP_9 : String_Tokens.Token := String_Tokens.Create (Noun_Phrase, 9, ""); + Prep_5 : String_Tokens.Token := String_Tokens.Create (Preposition, 5, "in"); + Prep_8 : String_Tokens.Token := String_Tokens.Create (Preposition, 8, "with"); + PP_5 : String_Tokens.Token := String_Tokens.Create (Prepositional_Phrase, 5, ""); + PP_8 : String_Tokens.Token := String_Tokens.Create (Prepositional_Phrase, 8, ""); - Paper_Edges : Graphs.Edge_Array := - ((1, 8, 1) -- Finish 2, Order 1 - (2, 9, 5) -- Finish 5, Order 1 - (3, 9, 2); -- Finish 5, Order 2 + Verb_2 : String_Tokens.Token := String_Tokens.Create (Verb, 2, "saw"); - Paper_Graph : Graphs.Parse_Graph := Graphs.To_Graph (Amb_Nodes, Amb_Edges, 18); + VP_2 : String_Tokens.Token := String_Tokens.Create (Verb_Phrase, 2, ""); + Sen_1 : String_Tokens.Token := String_Tokens.Create (Sentence, 1, ""); - function Root_Check + + -- This should be set up to be identical to the example parse in the paper + -- on pages 168-169. + + Paper_Graph : Graphs.Parse_Graph; + + + + + function Debug_String_Check + return String is + begin + return Paper_Graph.Debug_String; + end Debug_String_Check; + + + + + function Assign_Check return Test_Result is begin - end Root_Check; + -- to-do + return Fail; + end Assign_Check; - function Finish_List_Check + function Copy_Check return Test_Result is begin - end Finish_List_Check; + -- to-do + return Fail; + end Copy_Check; + + + function Move_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Move_Check; + + + + + + function Is_Empty_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Empty_Check; - function Sub_Nodes_Check + function Clear_Check return Test_Result is begin - end Sub_Nodes_Check; + -- to-do + return Fail; + end Clear_Check; + + + + + + function Contains_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Contains_Check; + + + function Reachable_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Reachable_Check; + + + function All_Reachable_Check + return Test_Result + is + begin + -- to-do + return Fail; + end All_Reachable_Check; + + + function Valid_Starts_Finishes_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Valid_Starts_Finishes_Check; + + + function No_Loops_Introduced_Check + return Test_Result + is + begin + -- to-do + return Fail; + end No_Loops_Introduced_Check; + + + function Is_Sorted_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Sorted_Check; + + + function No_Duplicates_Check + return Test_Result + is + begin + -- to-do + return Fail; + end No_Duplicates_Check; + + + + + + function Include_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Include_Check; + + + function Connect_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Connect_Check; function Prune_Check return Test_Result is begin + -- to-do + return Fail; end Prune_Check; - function Ambiguous_Check + function Delete_Unreachable_Check return Test_Result is begin - end Ambiguous_Check; + -- to-do + return Fail; + end Delete_Unreachable_Check; -begin - -- Node labels - Paper_Graph.Append_Label (1, String_Tokens.Create (Noun, 1, "i")); - Paper_Graph.Append_Label (2, String_Tokens.Create (Noun, 4, "man")); - Paper_Graph.Append_Label (3, String_Tokens.Create (Noun, 7, "park")); - Paper_Graph.Append_Label (4, String_Tokens.Create (Noun, 10, "bat")); - Paper_Graph.Append_Label (5, String_Tokens.Create (Determiner, 3, "a")); - Paper_Graph.Append_Label (6, String_Tokens.Create (Determiner, 6, "the")); - Paper_Graph.Append_Label (7, String_Tokens.Create (Determiner, 9, "a")); - Paper_Graph.Append_Label (8, String_Tokens.Create (Noun_Phrase, 1, "")); - Paper_Graph.Append_Label (9, String_Tokens.Create (Noun_Phrase, 3, "")); - Paper_Graph.Append_Label (10, String_Tokens.Create (Noun_Phrase, 6, "")); - Paper_Graph.Append_Label (11, String_Tokens.Create (Noun_Phrase, 9, "")); + function Has_Root_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Has_Root_Check; + + + function Set_Root_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Set_Root_Check; + + + function Clear_Root_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Clear_Root_Check; + + + function Root_Token_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Root_Token_Check; + + + function Root_Finish_List_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Root_Finish_List_Check; + + + function Root_Element_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Root_Element_Check; + + + + + + function Finish_List_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Finish_List_Check; + + + function Is_Leaf_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Leaf_Check; + + + function Is_Branch_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Branch_Check; + + - Paper_Graph.Append_Label (12, String_Tokens.Create (Preposition, 5, "in")); - Paper_Graph.Append_Label (13, String_Tokens.Create (Preposition, 8, "with")); - Paper_Graph.Append_Label (14, String_Tokens.Create (Prepositional_Phrase, 5, "")); - Paper_Graph.Append_Label (15, String_Tokens.Create (Prepositional_Phrase, 8, "")); - Paper_Graph.Append_Label (16, String_Tokens.Create (Verb, 2, "saw")); + function Subgroups_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Subgroups_Check; - Paper_Graph.Append_Label (17, String_Tokens.Create (Verb_Phrase, 2, "")); - Paper_Graph.Append_Label (18, String_Tokens.Create (Sentence, 1, "")); + function First_Index_Check + return Test_Result + is + begin + -- to-do + return Fail; + end First_Index_Check; + + + function Last_Index_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Last_Index_Check; + + + function Length_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Length_Check; + + + function Element_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Element_Check; + + + function Elements_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Elements_Check; + + + function Parent_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Parent_Check; + + + function Finish_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Finish_Check; + + + + + + function Is_Root_Ambiguous_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Root_Ambiguous_Check; + + + function Is_Ambiguous_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Is_Ambiguous_Check; + + + function Ambiguities_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Ambiguities_Check; + + + + + + function Isomorphic_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Isomorphic_Check; + + + function Isomorphic_Subgraph_Check + return Test_Result + is + begin + -- to-do + return Fail; + end Isomorphic_Subgraph_Check; + + +begin - -- Edge labels + -- Constructing the various test graphs + + Paper_Graph.Connect ((NP_1, 2), + (1 => Graphs.Finished_Token'(Noun_1, 2))); + Paper_Graph.Connect ((NP_3, 5), + ((Det_3, 4), (Noun_4, 5))); + Paper_Graph.Connect ((NP_3, 8), + ((NP_3, 5), (PP_5, 8))); + Paper_Graph.Connect ((NP_3, 11), + ((NP_3, 5), (PP_5, 11))); + Paper_Graph.Connect ((NP_3, 11), + ((NP_3, 8), (PP_8, 11))); + Paper_Graph.Connect ((NP_6, 8), + ((Det_6, 7), (Noun_7, 8))); + Paper_Graph.Connect ((NP_6, 11), + ((NP_6, 8), (PP_8, 11))); + Paper_Graph.Connect ((NP_9, 11), + ((Det_9, 10), (Noun_10, 11))); + + Paper_Graph.Connect ((PP_5, 8), + ((Prep_5, 6), (NP_6, 8))); + Paper_Graph.Connect ((PP_5, 11), + ((Prep_5, 6), (NP_6, 11))); + Paper_Graph.Connect ((PP_8, 11), + ((Prep_8, 9), (NP_9, 11))); + + Paper_Graph.Connect ((VP_2, 5), + ((Verb_2, 3), (NP_3, 5))); + Paper_Graph.Connect ((VP_2, 8), + ((Verb_2, 3), (NP_3, 8))); + Paper_Graph.Connect ((VP_2, 11), + ((Verb_2, 3), (NP_3, 11))); + + Paper_Graph.Connect ((Sen_1, 5), + ((NP_1, 2), (VP_2, 5))); + Paper_Graph.Connect ((Sen_1, 8), + ((NP_1, 2), (VP_2, 8))); + Paper_Graph.Connect ((Sen_1, 8), + ((Sen_1, 5), (PP_5, 8))); + Paper_Graph.Connect ((Sen_1, 11), + ((NP_1, 2), (VP_2, 11))); + Paper_Graph.Connect ((Sen_1, 11), + ((Sen_1, 5), (PP_5, 11))); + Paper_Graph.Connect ((Sen_1, 11), + ((Sen_1, 8), (PP_8, 11))); end Rat_Tests.Parse_Graphs; diff --git a/test/rat_tests-parse_graphs.ads b/test/rat_tests-parse_graphs.ads index bec4853..ad2e48d 100644 --- a/test/rat_tests-parse_graphs.ads +++ b/test/rat_tests-parse_graphs.ads @@ -7,19 +7,104 @@ use Unit_Tests; package Rat_Tests.Parse_Graphs is - function Root_Check return Test_Result; - function Finish_List_Check return Test_Result; - function Sub_Nodes_Check return Test_Result; + function Debug_String_Check return String; + + + function Assign_Check return Test_Result; + function Copy_Check return Test_Result; + function Move_Check return Test_Result; + + function Is_Empty_Check return Test_Result; + function Clear_Check return Test_Result; + + function Contains_Check return Test_Result; + function Reachable_Check return Test_Result; + function All_Reachable_Check return Test_Result; + function Valid_Starts_Finishes_Check return Test_Result; + function No_Loops_Introduced_Check return Test_Result; + function Is_Sorted_Check return Test_Result; + function No_Duplicates_Check return Test_Result; + + function Include_Check return Test_Result; + function Connect_Check return Test_Result; function Prune_Check return Test_Result; - function Ambiguous_Check return Test_Result; + function Delete_Unreachable_Check return Test_Result; + + function Has_Root_Check return Test_Result; + function Set_Root_Check return Test_Result; + function Clear_Root_Check return Test_Result; + function Root_Token_Check return Test_Result; + function Root_Finish_List_Check return Test_Result; + function Root_Element_Check return Test_Result; + + function Finish_List_Check return Test_Result; + function Is_Leaf_Check return Test_Result; + function Is_Branch_Check return Test_Result; + + function Subgroups_Check return Test_Result; + function First_Index_Check return Test_Result; + function Last_Index_Check return Test_Result; + function Length_Check return Test_Result; + function Element_Check return Test_Result; + function Elements_Check return Test_Result; + function Parent_Check return Test_Result; + function Finish_Check return Test_Result; + + function Is_Root_Ambiguous_Check return Test_Result; + function Is_Ambiguous_Check return Test_Result; + function Ambiguities_Check return Test_Result; + + function Isomorphic_Check return Test_Result; + function Isomorphic_Subgraph_Check return Test_Result; Tests : Test_Array := - ((+"Root getter, setter", Root_Check'Access), - (+"Finish_List", Finish_List_Check'Access), - (+"Sub_Nodes", Sub_Nodes_Check'Access), + ((+"Assign", Assign_Check'Access), + (+"Copy", Copy_Check'Access), + (+"Move", Move_Check'Access), + + (+"Is_Empty", Is_Empty_Check'Access), + (+"Clear", Clear_Check'Access), + + (+"Contains", Contains_Check'Access), + (+"Reachable", Reachable_Check'Access), + (+"All_Reachable", All_Reachable_Check'Access), + (+"Valid_Starts_Finishes", Valid_Starts_Finishes_Check'Access), + (+"No_Loops_Introduced", No_Loops_Introduced_Check'Access), + (+"Is_Sorted", Is_Sorted_Check'Access), + (+"No_Duplicates", No_Duplicates_Check'Access), + + (+"Include", Include_Check'Access), + (+"Connect", Connect_Check'Access), (+"Prune", Prune_Check'Access), - (+"Is_Ambiguous", Ambiguous_Check'Access)); + (+"Delete_Unreachable", Delete_Unreachable_Check'Access), + + (+"Has_Root", Has_Root_Check'Access), + (+"Set_Root", Set_Root_Check'Access), + (+"Clear_Root", Clear_Root_Check'Access), + (+"Root_Token", Root_Token_Check'Access), + (+"Root_Finish_List", Root_Finish_List_Check'Access), + (+"Root_Element", Root_Element_Check'Access), + + (+"Finish_List", Finish_List_Check'Access), + (+"Is_Leaf", Is_Leaf_Check'Access), + (+"Is_Branch", Is_Branch_Check'Access), + + (+"Subgroups", Subgroups_Check'Access), + (+"First_Index", First_Index_Check'Access), + (+"Last_Index", Last_Index_Check'Access), + (+"Length", Length_Check'Access), + (+"Element", Element_Check'Access), + (+"Elements", Elements_Check'Access), + (+"Parent", Parent_Check'Access), + (+"Finish", Finish_Check'Access), + + (+"Is_Root_Ambiguous", Is_Root_Ambiguous_Check'Access), + (+"Is_Ambiguous", Is_Ambiguous_Check'Access), + (+"Ambiguities", Ambiguities_Check'Access), + + (+"Isomorphic", Isomorphic_Check'Access), + (+"Isomorphic_Subgraph", Isomorphic_Subgraph_Check'Access)); end Rat_Tests.Parse_Graphs; diff --git a/test/test_main.adb b/test/test_main.adb index 4cba5ec..7a96cbd 100644 --- a/test/test_main.adb +++ b/test/test_main.adb @@ -10,7 +10,8 @@ with Rat_Tests.Errors, Rat_Tests.Tokens, Rat_Tests.Lexer, - Rat_Tests.Util; + Rat_Tests.Util, + Rat_Tests.Parse_Graphs; use @@ -90,6 +91,13 @@ begin Run_Tests (Rat_Tests.Util.Set_Predicate_Tests, How_Verbose); Put_Line ("Testing ordinary predicates..."); Run_Tests (Rat_Tests.Util.Predicate_Tests, How_Verbose); + New_Line; + + Put_Line ("Running tests for Packrat.Parse_Graphs..."); + Run_Tests (Rat_Tests.Parse_Graphs.Tests, How_Verbose); + New_Line; + Put_Line ("Displaying Parse_Graph debug string output example:"); + Put (Rat_Tests.Parse_Graphs.Debug_String_Check); end Test_Main; -- cgit