Changes in src/ResolvExpr/Unify.cc [a2a77af:6c3a988f]

File:

• src/ResolvExpr/Unify.cc (modified) (12 diffs)

src/ResolvExpr/Unify.cc

@@ -26 +26 @@
 #include "SymTab/Indexer.h"
 #include "Common/utility.h"
-
+#include "Tuples/Tuples.h"
 
 // #define DEBUG
@@ -99 +99 @@
                 newFirst->get_qualifiers() = Type::Qualifiers();
                 newSecond->get_qualifiers() = Type::Qualifiers();
-///   std::cout << "first is ";
-///   first->print( std::cout );
-///   std::cout << std::endl << "second is ";
-///   second->print( std::cout );
-///   std::cout << std::endl << "newFirst is ";
-///   newFirst->print( std::cout );
-///   std::cout << std::endl << "newSecond is ";
-///   newSecond->print( std::cout );
-///   std::cout << std::endl;
+///   std::cerr << "first is ";
+///   first->print( std::cerr );
+///   std::cerr << std::endl << "second is ";
+///   second->print( std::cerr );
+///   std::cerr << std::endl << "newFirst is ";
+///   newFirst->print( std::cerr );
+///   std::cerr << std::endl << "newSecond is ";
+///   newSecond->print( std::cerr );
+///   std::cerr << std::endl;
                 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
                 delete newFirst;
@@ -123 +123 @@
         }
 
-        bool tyVarCompatible( TypeDecl::Kind kind, Type *type, const SymTab::Indexer &indexer ) {
-                switch ( kind ) {
+        struct CompleteTypeChecker : public Visitor {
+                virtual void visit( VoidType *basicType ) { status = false; }
+                virtual void visit( BasicType *basicType ) {}
+                virtual void visit( PointerType *pointerType ) {}
+                virtual void visit( ArrayType *arrayType ) { status = ! arrayType->get_isVarLen(); }
+                virtual void visit( FunctionType *functionType ) {}
+                virtual void visit( StructInstType *aggregateUseType ) { status = aggregateUseType->get_baseStruct()->has_body(); }
+                virtual void visit( UnionInstType *aggregateUseType ) { status = aggregateUseType->get_baseUnion()->has_body(); }
+                // xxx - enum inst does not currently contain a pointer to base, this should be fixed.
+                virtual void visit( EnumInstType *aggregateUseType ) { /* status = aggregateUseType->get_baseEnum()->hasBody(); */ }
+                virtual void visit( TraitInstType *aggregateUseType ) { assert( false ); }
+                virtual void visit( TypeInstType *aggregateUseType ) { status = aggregateUseType->get_baseType()->isComplete(); }
+                virtual void visit( TupleType *tupleType ) {} // xxx - not sure if this is right, might need to recursively check complete-ness
+                virtual void visit( TypeofType *typeofType ) { assert( false ); }
+                virtual void visit( AttrType *attrType ) { assert( false ); } // xxx - not sure what to do here
+                virtual void visit( VarArgsType *varArgsType ){} // xxx - is this right?
+                virtual void visit( ZeroType *zeroType ) {}
+                virtual void visit( OneType *oneType ) {}
+                bool status = true;
+        };
+        bool isComplete( Type * type ) {
+                CompleteTypeChecker checker;
+                assert( type );
+                type->accept( checker );
+                return checker.status;
+        }
+
+        bool tyVarCompatible( const TypeDecl::Data & data, Type *type, const SymTab::Indexer &indexer ) {
+                switch ( data.kind ) {
                   case TypeDecl::Any:
                   case TypeDecl::Dtype:
-                        return ! isFtype( type, indexer );
-
+                        // to bind to an object type variable, the type must not be a function type.
+                        // if the type variable is specified to be a complete type then the incoming
+                        // type must also be complete
+                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
+                        return ! isFtype( type, indexer ) && (! data.isComplete || isComplete( type ));
                   case TypeDecl::Ftype:
                         return isFtype( type, indexer );
+                        case TypeDecl::Ttype:
+                        // ttype unifies with any tuple type
+                        return dynamic_cast< TupleType * >( type );
                 } // switch
-                assert( false );
                 return false;
         }
 
-        bool bindVar( TypeInstType *typeInst, Type *other, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
+        bool bindVar( TypeInstType *typeInst, Type *other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
                 OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
                 assert( tyvar != openVars.end() );
@@ -175 +207 @@
                         newClass.type->get_qualifiers() = Type::Qualifiers();
                         newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
-                        newClass.kind = kind;
+                        newClass.data = data;
                         env.add( newClass );
                 } // if
@@ -181 +213 @@
         }
 
-        bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
+        bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
                 bool result = true;
                 EqvClass class1, class2;
@@ -210 +242 @@
 
                 if ( type1 && type2 ) {
-//    std::cout << "has type1 && type2" << std::endl;
+//    std::cerr << "has type1 && type2" << std::endl;
                         WidenMode newWidenMode ( widen1, widen2 );
                         Type *common = 0;
@@ -248 +280 @@
                         newClass.vars.insert( var2->get_name() );
                         newClass.allowWidening = widen1 && widen2;
-                        newClass.kind = kind;
+                        newClass.data = data;
                         env.add( newClass );
                 } // if
@@ -311 +343 @@
                 } // if
 #ifdef DEBUG
-                std::cout << "============ unifyExact" << std::endl;
-                std::cout << "type1 is ";
-                type1->print( std::cout );
-                std::cout << std::endl << "type2 is ";
-                type2->print( std::cout );
-                std::cout << std::endl << "openVars are ";
-                printOpenVarSet( openVars, std::cout, 8 );
-                std::cout << std::endl << "input env is " << std::endl;
-                debugEnv.print( std::cout, 8 );
-                std::cout << std::endl << "result env is " << std::endl;
-                env.print( std::cout, 8 );
-                std::cout << "result is " << result << std::endl;
+                std::cerr << "============ unifyExact" << std::endl;
+                std::cerr << "type1 is ";
+                type1->print( std::cerr );
+                std::cerr << std::endl << "type2 is ";
+                type2->print( std::cerr );
+                std::cerr << std::endl << "openVars are ";
+                printOpenVarSet( openVars, std::cerr, 8 );
+                std::cerr << std::endl << "input env is " << std::endl;
+                debugEnv.print( std::cerr, 8 );
+                std::cerr << std::endl << "result env is " << std::endl;
+                env.print( std::cerr, 8 );
+                std::cerr << "result is " << result << std::endl;
 #endif
                 return result;
@@ -337 +369 @@
                 bool result;
 #ifdef DEBUG
-                std::cout << "unifyInexact type 1 is ";
-                type1->print( std::cout );
-                std::cout << "type 2 is ";
-                type2->print( std::cout );
-                std::cout << std::endl;
+                std::cerr << "unifyInexact type 1 is ";
+                type1->print( std::cerr );
+                std::cerr << "type 2 is ";
+                type2->print( std::cerr );
+                std::cerr << std::endl;
 #endif
                 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
 #ifdef DEBUG
-                        std::cout << "unifyInexact: no exact unification found" << std::endl;
+                        std::cerr << "unifyInexact: no exact unification found" << std::endl;
 #endif
                         if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
                                 common->get_qualifiers() = tq1 + tq2;
 #ifdef DEBUG
-                                std::cout << "unifyInexact: common type is ";
-                                common->print( std::cout );
-                                std::cout << std::endl;
+                                std::cerr << "unifyInexact: common type is ";
+                                common->print( std::cerr );
+                                std::cerr << std::endl;
 #endif
                                 result = true;
                         } else {
 #ifdef DEBUG
-                                std::cout << "unifyInexact: no common type found" << std::endl;
+                                std::cerr << "unifyInexact: no common type found" << std::endl;
 #endif
                                 result = false;
@@ -394 +426 @@
 
         void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
-///   std::cout << "assertion set is" << std::endl;
-///   printAssertionSet( assertions, std::cout, 8 );
-///   std::cout << "looking for ";
-///   assert->print( std::cout );
-///   std::cout << std::endl;
+///   std::cerr << "assertion set is" << std::endl;
+///   printAssertionSet( assertions, std::cerr, 8 );
+///   std::cerr << "looking for ";
+///   assert->print( std::cerr );
+///   std::cerr << std::endl;
                 AssertionSet::iterator i = assertions.find( assert );
                 if ( i != assertions.end() ) {
-///     std::cout << "found it!" << std::endl;
-                        i->second = true;
+///     std::cerr << "found it!" << std::endl;
+                        i->second.isUsed = true;
                 } // if
         }
@@ -456 +488 @@
         }
 
+        template< typename Iterator >
+        std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end ) {
+                std::list< Type * > types;
+                for ( ; begin != end; ++begin ) {
+                        // it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
+                        flatten( (*begin)->get_type(), back_inserter( types ) );
+                }
+                return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
+        }
+
         template< typename Iterator1, typename Iterator2 >
         bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
                 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
-                        // Type * commonType;
-                        // if ( ! unifyInexact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
-                        if ( ! unifyExact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
+                        Type * t1 = (*list1Begin)->get_type();
+                        Type * t2 = (*list2Begin)->get_type();
+                        bool isTtype1 = Tuples::isTtype( t1 );
+                        bool isTtype2 = Tuples::isTtype( t2 );
+                        // xxx - assumes ttype must be last parameter
+                        // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
+                        if ( isTtype1 && ! isTtype2 ) {
+                                // combine all of the things in list2, then unify
+                                return unifyExact( t1, combineTypes( list2Begin, list2End ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                        } else if ( isTtype2 && ! isTtype1 ) {
+                                // combine all of the things in list1, then unify
+                                return unifyExact( combineTypes( list1Begin, list1End ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                        } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
                                 return false;
                         } // if
                 } // for
-                if ( list1Begin != list1End || list2Begin != list2End ) {
-                        return false;
+                // may get to the end of one argument list before the end of the other. This is only okay when the other is a ttype
+                if ( list1Begin != list1End ) {
+                        // try unifying empty tuple type with ttype
+                        Type * t1 = (*list1Begin)->get_type();
+                        if ( Tuples::isTtype( t1 ) ) {
+                                return unifyExact( t1, combineTypes( list2Begin, list2End ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                        } else return false;
+                } else if ( list2Begin != list2End ) {
+                        // try unifying empty tuple type with ttype
+                        Type * t2 = (*list2Begin)->get_type();
+                        if ( Tuples::isTtype( t2 ) ) {
+                                return unifyExact( combineTypes( list1Begin, list1End ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                        } else return false;
                 } else {
                         return true;
                 } // if
+        }
+
+        /// Finds ttypes and replaces them with their expansion, if known.
+        /// This needs to be done so that satisfying ttype assertions is easier.
+        /// If this isn't done then argument lists can have wildly different
+        /// size and structure, when they should be compatible.
+        struct TtypeExpander : public Mutator {
+                TypeEnvironment & env;
+                TtypeExpander( TypeEnvironment & env ) : env( env ) {}
+                Type * mutate( TypeInstType * typeInst ) {
+                        EqvClass eqvClass;
+                        if ( env.lookup( typeInst->get_name(), eqvClass ) ) {
+                                if ( eqvClass.data.kind == TypeDecl::Ttype ) {
+                                        // expand ttype parameter into its actual type
+                                        if ( eqvClass.type ) {
+                                                delete typeInst;
+                                                return eqvClass.type->clone();
+                                        }
+                                }
+                        }
+                        return typeInst;
+                }
+        };
+
+        /// flattens a list of declarations, so that each tuple type has a single declaration.
+        /// makes use of TtypeExpander to ensure ttypes are flat as well.
+        void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
+                dst.clear();
+                for ( DeclarationWithType * dcl : src ) {
+                        TtypeExpander expander( env );
+                        dcl->acceptMutator( expander );
+                        std::list< Type * > types;
+                        flatten( dcl->get_type(), back_inserter( types ) );
+                        for ( Type * t : types ) {
+                                dst.push_back( new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::C, nullptr, t, nullptr ) );
+                        }
+                        delete dcl;
+                }
         }
 
@@ -475 +576 @@
                 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
                 if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
-                        if ( functionType->get_parameters().size() == otherFunction->get_parameters().size() && functionType->get_returnVals().size() == otherFunction->get_returnVals().size() ) {
-                                if ( unifyDeclList( functionType->get_parameters().begin(), functionType->get_parameters().end(), otherFunction->get_parameters().begin(), otherFunction->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
-                                        if ( unifyDeclList( functionType->get_returnVals().begin(), functionType->get_returnVals().end(), otherFunction->get_returnVals().begin(), otherFunction->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
-
+                        // flatten the parameter lists for both functions so that tuple structure
+                        // doesn't affect unification. Must be a clone so that the types don't change.
+                        std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
+                        std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
+                        flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
+                        flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
+
+                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
+                        if ( (flatFunc->get_parameters().size() == flatOther->get_parameters().size() && flatFunc->get_returnVals().size() == flatOther->get_returnVals().size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
+                                if ( unifyDeclList( flatFunc->get_parameters().begin(), flatFunc->get_parameters().end(), flatOther->get_parameters().begin(), flatOther->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
+                                        if ( unifyDeclList( flatFunc->get_returnVals().begin(), flatFunc->get_returnVals().end(), flatOther->get_returnVals().begin(), flatOther->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
+
+                                                // the original types must be used in mark assertions, since pointer comparisons are used
                                                 markAssertions( haveAssertions, needAssertions, functionType );
                                                 markAssertions( haveAssertions, needAssertions, otherFunction );