Goose  Artifact [f6f51d72b1]

Artifact f6f51d72b189c538d3a7feb70a29ea7d5cf0708cc3cced5fe34148e6bc20041c:

• File bs/ir/tests/match-tries.cpp — part of check-in [fc6c22b8bc] at 2019-01-05 21:32:43 on branch trunk —
  • Changed the matching scoring system to add 2 to the complexity count for each literal value matched in the pattern.
  • Added hole unification tests.
  • Fixed various hole unification bugs.
  (user: achavasse size: 3490)

#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"
#include "ir/ir.h"

using namespace std;
using namespace empathy;
using namespace empathy::ir;

SCENARIO( "Match works", "[match]" )
{
    WHEN( "Matching various expressions against various patterns stored in a trie" )
    {
        auto pat0 = ANYTERM( a );

        auto pat1 = TVEC(
            TVEC( TSTR( "foo" ), TSTR( "bar" ) ),
            TVEC(),
            TVEC( TSTR( "foo" ), TSTR( "bar" ) ),
            TVEC( TSTR( "foo" ), TSTR( "bar" ) )
        );

        auto expr1 = pat1;

        auto pat2 = TVEC(
            TVEC( ANYTERM( a ), TSTR( "bar" ) ),
            TVEC(),
            TVEC( ANYTERM( a ), TSTR( "bar" ) ),
            TVEC( ANYTERM( a ), TSTR( "bar" ) )
        );

        auto expr2 = TVEC(
            TVEC( TSTR( "meh" ), TSTR( "bar" ) ),
            TVEC(),
            TVEC( TSTR( "meh" ), TSTR( "bar" ) ),
            TVEC( TSTR( "meh" ), TSTR( "bar" ) )
        );

        auto pat3 = TVEC(
            ANYTERM( x ),
            TVEC( ANYTERM( a ), TSTR( "bar" ) ),
            ANYTERM( z ),
            ANYTERM( z )
        );

        auto expr3 = TVEC(
            TSID( a ),
            TVEC( TSTR( "meh" ), TSTR( "bar" ) ),
            TSID( b ),
            TSID( b )
        );

        auto pat4 = TVEC(
            TVEC( ANYTERM( a ), TSTR( "bar" ) ),
            ANYTERM( y ),
            ANYTERM( y ),
            ANYTERM( y )
        );

        auto expr4 = TVEC(
            TVEC( TSTR( "huh" ), TSTR( "bar" ) ),
            TVEC(),
            TVEC(),
            TVEC()
        );

        Trie< string > testPatTrie;
        testPatTrie = Merge( testPatTrie, pat0, []( auto&& ){ return "pat0"s; } );
        testPatTrie = Merge( testPatTrie, pat1, []( auto&& ){ return "pat1"s; } );
        testPatTrie = Merge( testPatTrie, pat2, []( auto&& ){ return "pat2"s; } );
        testPatTrie = Merge( testPatTrie, pat3, []( auto&& ){ return "pat3"s; } );
        testPatTrie = Merge( testPatTrie, pat4, []( auto&& ){ return "pat4"s; } );

        Trie< string > testExprTrie;
        testExprTrie = Merge( testExprTrie, expr1, []( auto&& ){ return "expr1"s; } );
        testExprTrie = Merge( testExprTrie, expr2, []( auto&& ){ return "expr2"s; } );
        testExprTrie = Merge( testExprTrie, expr3, []( auto&& ){ return "expr3"s; } );
        testExprTrie = Merge( testExprTrie, expr4, []( auto&& ){ return "expr4"s; } );

        THEN( "Matching the tries work as expected" )
        {
            vector< tuple< string, string, size_t, size_t > > solutions;
            for( auto&& [sol, str1, str2] : Match( testExprTrie, testPatTrie ) )
                solutions.emplace_back( str1, str2, sol.complexity(), sol.numVars() );

            REQUIRE( solutions.size() == 9 );
            REQUIRE( solutions[0] == make_tuple( "expr3", "pat0", 0, 1 ) );
            REQUIRE( solutions[1] == make_tuple( "expr4", "pat0", 0, 1 ) );
            REQUIRE( solutions[2] == make_tuple( "expr1", "pat0", 0, 1 ) );
            REQUIRE( solutions[3] == make_tuple( "expr2", "pat0", 0, 1 ) );
            REQUIRE( solutions[4] == make_tuple( "expr3", "pat3", 4, 3 ) );
            REQUIRE( solutions[5] == make_tuple( "expr1", "pat1", 17, 0 ) );
            REQUIRE( solutions[6] == make_tuple( "expr4", "pat4", 4, 2 ) );
            REQUIRE( solutions[7] == make_tuple( "expr1", "pat2", 11, 1 ) );
            REQUIRE( solutions[8] == make_tuple( "expr2", "pat2", 11, 1 ) );
        }
    }
}