Changeset 2162c2c for src/ResolvExpr/Unify.cc

Timestamp:

Jan 11, 2017, 4:11:02 PM (9 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

075734f

Parents:

bb82c03 (diff), d3a85240 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

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

src/ResolvExpr/Unify.cc

@@ -26 +26 @@
 #include "SymTab/Indexer.h"
 #include "Common/utility.h"
-
+#include "Tuples/Tuples.h"
 
 // #define DEBUG
@@ -157 +157 @@
                         // 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;
         }
@@ -431 +434 @@
                 if ( i != assertions.end() ) {
 ///     std::cerr << "found it!" << std::endl;
-                        i->second = true;
+                        i->second.isUsed = true;
                 } // if
         }
@@ -485 +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;
+                }
         }
 
@@ -504 +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 );