Goose  Artifact [b14e6e299c]

Artifact b14e6e299c5c0c9082cf14bc260695b759b3661159a1c3074edf53722565d7d5:

• File bs/ir/match.cpp — part of check-in [fc368bcd5c] at 2018-11-12 20:13:48 on branch trunk — Handle AnyTerm and VecOfLength in term/trie pattern matching. (user: achavasse size: 5775)

#include "ir.h"

namespace empathy::ir
{
    size_t MatchSolution::numVars() const
    {
        if( !m_pVars )
            return 0;

        return m_pVars->size();
    }

    void MatchSolution::setupVars()
    {
        if( !m_pVars )
            m_pVars = make_shared< unordered_map< StringId, any > >();
        else if( m_pVars.use_count() > 1 )
            m_pVars = make_shared< unordered_map< StringId, any > >( *m_pVars );
    }

    Generator< MatchSolution > Match( const Term& expression, const Trie<>& patterns )
    {
        for( auto&& [s,p] : Match<>( expression, patterns ) )
            co_yield move( s );
    }

    optional< MatchSolution > Match( MatchSolution&& currentSolution, const Term& expression, const Term& pattern );

    //--------------------------------------------------------------------------------------------
    // AnyTerm
    //--------------------------------------------------------------------------------------------
    optional< MatchSolution > MatchAnyTerm( MatchSolution&& currentSolution, const Term& expression, const AnyTerm& pattern )
    {
        if( currentSolution.setVar( pattern.varName(), expression ) )
            return move( currentSolution );

        return nullopt;
    }

    //--------------------------------------------------------------------------------------------
    // VecOfLength
    //--------------------------------------------------------------------------------------------
    optional< MatchSolution > MatchVecOfLength( MatchSolution&& currentSolution, const Term& expression, const VecOfLength& pattern )
    {
        if( !holds_alternative< pvec >( expression.content() ) )
            return nullopt;

        // When a repetition appears in the expression vector, consider it to be an extra element at the end.
        const auto& vec = *get< pvec >( expression.content() );
        const auto exprLength = vec.length();

        size_t exprSize = exprLength.minLength();
        if( exprLength.isVariable() )
            ++exprSize;

        if( currentSolution.setVar( pattern.varName(), exprSize ) )
        {
            currentSolution.incComplexity();
            return move( currentSolution );
        }

        return nullopt;
    }

    //--------------------------------------------------------------------------------------------
    // Vec
    //--------------------------------------------------------------------------------------------
    optional< MatchSolution > MatchVec( MatchSolution&& currentSolution, const Term& expression, const pvec& pattern )
    {
        if( !holds_alternative< pvec >( expression.content() ) )
            return nullopt;

        // When a repetition appears in the expression vector, consider it to be an extra element at the end.
        const auto& vec = *get< pvec >( expression.content() );
        const auto exprLength = vec.length();
        const auto patLength = pattern->length();

        size_t exprSize = exprLength.minLength();
        if( exprLength.isVariable() )
            ++exprSize;

        if( exprSize < patLength.minLength() )
            return nullopt;

        if( !patLength.isVariable() && patLength.minLength() < exprSize )
            return nullopt;

        auto gen = vec.ForEachTerm();
        auto it = gen.begin();

        auto curSolution = move( currentSolution );

        for( auto&& pat : pattern->terms() )
        {
            assert( it != gen.end() );

            auto sol = Match( move( curSolution ), *it, pat );
            if( !sol )
                return nullopt;

            curSolution = move( *sol );
            ++it;
        }

        assert( it == gen.end() || pattern->repetitionTerm() );

        while( it != gen.end() )
        {
            auto sol = Match( move( curSolution ), *it, *pattern->repetitionTerm() );
            if( !sol )
                return nullopt;

            curSolution = move( *sol );
            ++it;
        }

        curSolution.incComplexity();
        return move( curSolution );
    }

    //--------------------------------------------------------------------------------------------
    // Value
    //--------------------------------------------------------------------------------------------
    template< typename T >
    optional< MatchSolution > MatchValue( MatchSolution&& currentSolution, const Term& expression, const T& pattern )
    {
        using TT = remove_constref_t< decltype( pattern ) >;

        const auto* pVal = get_if< TT >( &expression.content() );
        if( pVal && *pVal == pattern )
            return move( currentSolution );

        return nullopt;
    }

    //--------------------------------------------------------------------------------------------
    // Terms
    //--------------------------------------------------------------------------------------------
    optional< MatchSolution > Match( MatchSolution&& currentSolution, const Term& expression, const Term& pattern )
    {
        return visit( [&]( auto&& t )
        {
            using T = remove_constref_t< decltype( t ) >;

            if constexpr( is_same_v< T, AnyTerm > )
                return MatchAnyTerm( move( currentSolution ), expression, t );
            else if constexpr( is_same_v< T, VecOfLength > )
                return MatchVecOfLength( move( currentSolution ), expression, t );
            else if constexpr( is_same_v< T, pvec > )
                return MatchVec( move( currentSolution ), expression, t );
            else
                return MatchValue( move( currentSolution ), expression, t );
        }, pattern.content() );
    }

    optional< MatchSolution > Match( const Term& expression, const Term& pattern )
    {
        return Match( MatchSolution(), expression, pattern );
    }
}