Goose  Artifact [660a8b94bf]

Artifact 660a8b94bf37f0486c5cd040795b7aa80f8f278da510a1049015c99c23d4f2ce:

• File bs/sema/utrie.h — part of check-in [947b9d7cfc] at 2020-06-13 22:59:24 on branch trunk —
  • Implemented Initialize overloads for tuples.
  • Lots of cleanup.
  (user: achavasse size: 2347)

#ifndef GOOSE_SEMA_UTRIE_H
#define GOOSE_SEMA_UTRIE_H

namespace goose::sema
{
    // Similar to an ir trie, but instead of being used to find the best pattern among a set of patterns,
    // it is used to find the best unification among a set of vector terms.
    // This is used to construct overload sets and to efficiently resolve overloads.
    template< typename U >
    class UTrie
    {
        public:
            template< typename F >
            ptr< UTrie > merge( const Vector& v, F&& func ) const;

            template< typename T >
            using UniGen = Generator< tuple< Vector, Vector, const T&, UnificationContext > >;

            UniGen< U > unify( const Vector& rhs, UnificationContext c ) const;
            UniGen< U > halfUnify( UnificationContext c ) const;

        private:
            struct Node;
            struct RepetitionNode;
            using branch_t = variant< ptr< Node >, any >;

            template< typename T, typename IT, typename F >
            static branch_t Merge( const branch_t& b, const IT& it, const IT& end, F&& next );

            template< typename F >
            static ptr< RepetitionNode > Merge( const ptr< RepetitionNode >& lhs, const Term& rhs, F&& next );

            static UniGen< U > UnifyRepetition( VecGenerator vgen, const Vector& lhsVec, const Vector& solutionVec,
                const RepetitionNode& rptNode, const UnificationContext& c );

            template< typename T > static Generator< tuple< Vector, Vector, const T&, UnificationContext, VecGenerator > >
            Unify( VecGenerator vgen, const Vector& lhsVec, const Vector& solutionVec, const branch_t& branch, const UnificationContext& c );

            template< typename T > static UniGen< T >
            HalfUnify( const Vector& lhsVec, const Vector& solutionVec, const branch_t& branch, const UnificationContext& c );

            struct Node
            {
                Trie< branch_t > m_trie;
            };

            struct RepetitionNode
            {
                Trie<> m_repetition;
                U m_next;
            };

            // All fixed length branches, by length.
            map< size_t, branch_t > m_fixedLengthBranches;

            // All variable length branches, by min length.
            map< size_t, branch_t > m_variableLengthBranches;
    };
}

#endif