Changeset 6c3a988f for src/ResolvExpr

Timestamp:

Jan 5, 2017, 3:47:36 PM (9 years ago)

Author:

Rob Schluntz <rschlunt@…>

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:

f831177

Parents:

1e3d5b6

Message:

fix inferred parameter data structures to correctly associate parameters with the entity that requested them, modify tuple specialization and unification to work with self-recursive assertions

Location:

src/ResolvExpr

Files:

• AdjustExprType.cc (modified) (1 diff)
• AlternativeFinder.cc (modified) (7 diffs)
• FindOpenVars.cc (modified) (2 diffs)
• TypeEnvironment.cc (modified) (1 diff)
• TypeEnvironment.h (modified) (1 diff)
• Unify.cc (modified) (7 diffs)
• typeops.h (modified) (1 diff)

src/ResolvExpr/AdjustExprType.cc

@@ -22 +22 @@
         class AdjustExprType : public Mutator {
                 typedef Mutator Parent;
+                using Parent::mutate;
           public:
                 AdjustExprType( const TypeEnvironment &env, const SymTab::Indexer &indexer );

src/ResolvExpr/AlternativeFinder.cc

@@ -339 +339 @@
                         unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
                         for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
-                                needAssertions[ *assert ] = true;
+                                needAssertions[ *assert ].isUsed = true;
                         }
 ///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
@@ -380 +380 @@
                         }
                         *out++ = arg;
-                        return true;
                 } else if ( actualIt != actualEnd ) {
                         // both actualType and formalType are atomic (non-tuple) types - if they unify
@@ -467 +466 @@
         void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
                 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
-                        if ( i->second == true ) {
+                        if ( i->second.isUsed ) {
                                 i->first->accept( indexer );
                         }
@@ -478 +477 @@
                 if ( begin == end ) {
                         if ( newNeed.empty() ) {
+                                PRINT(
+                                        std::cerr << "all assertions satisfied, output alternative: ";
+                                        newAlt.print( std::cerr );
+                                        std::cerr << std::endl;
+                                );
                                 *out++ = newAlt;
                                 return;
@@ -494 +498 @@
 
                 ForwardIterator cur = begin++;
-                if ( ! cur->second ) {
+                if ( ! cur->second.isUsed ) {
                         inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
                         return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
@@ -538 +542 @@
                                 assert( (*candidate)->get_uniqueId() );
                                 DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
+
+                                // everything with an empty idChain was pulled in by the current assertion.
+                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
+                                for ( auto & a : newerNeed ) {
+                                        if ( a.second.idChain.empty() ) {
+                                                a.second.idChain = cur->second.idChain;
+                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
+                                        }
+                                }
+
                                 //AssertionParentSet newNeedParents( needParents );
                                 // skip repeatingly-self-recursive assertion satisfaction
@@ -553 +567 @@
                                 )
                                 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
+                                // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
+                                InferredParams * inferParameters = &appExpr->get_inferParams();
+                                for ( UniqueId id : cur->second.idChain ) {
+                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
+                                }
                                 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
-                                appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
+                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
                                 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
                         } else {

src/ResolvExpr/FindOpenVars.cc

@@ -50 +50 @@
                                 openVars[ (*i)->get_name() ] = TypeDecl::Data{ (*i) };
                                 for ( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
-                                        needAssertions[ *assert ] = false;
+                                        needAssertions[ *assert ].isUsed = false;
                                 }
 ///       cloneAll( (*i)->get_assertions(), needAssertions );
@@ -59 +59 @@
                                 closedVars[ (*i)->get_name() ] = TypeDecl::Data{ (*i) };
                                 for ( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
-                                        haveAssertions[ *assert ] = false;
+                                        haveAssertions[ *assert ].isUsed = false;
                                 }
 ///       cloneAll( (*i)->get_assertions(), haveAssertions );

src/ResolvExpr/TypeEnvironment.cc

@@ -75 +75 @@
                 for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
                         i->first->print( os, indent );
-                        if ( i->second ) {
+                        if ( i->second.isUsed ) {
                                 os << "(used)";
                         } else {

src/ResolvExpr/TypeEnvironment.h

@@ -31 +31 @@
                 bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const;
         };
-        typedef std::map< DeclarationWithType*, bool, AssertCompare > AssertionSet;
+        struct AssertionSetValue {
+                bool isUsed;
+                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
+                // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
+                // the ID of the assertion that pulled in the current assertion.
+                std::list< UniqueId > idChain;
+        };
+        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
         typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
 

src/ResolvExpr/Unify.cc

@@ -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 eats up any remaining parameters, no matter the type
-                        return true;
+                        // ttype unifies with any tuple type
+                        return dynamic_cast< TupleType * >( type );
                 } // switch
                 return false;
@@ -433 +434 @@
                 if ( i != assertions.end() ) {
 ///     std::cerr << "found it!" << std::endl;
-                        i->second = true;
+                        i->second.isUsed = true;
                 } // if
         }
@@ -488 +489 @@
 
         template< typename Iterator >
-        Type * combineTypes( Iterator begin, Iterator end ) {
+        std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end ) {
                 std::list< Type * > types;
                 for ( ; begin != end; ++begin ) {
@@ -494 +495 @@
                         flatten( (*begin)->get_type(), back_inserter( types ) );
                 }
-                return new TupleType( Type::Qualifiers(), types );
+                return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
         }
 
@@ -504 +505 @@
                         bool isTtype1 = Tuples::isTtype( t1 );
                         bool isTtype2 = Tuples::isTtype( t2 );
-                        // xxx - assumes ttype must be last parameter; needs cleanup; use unique_ptr for combinedType
+                        // 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
-                                Type * combinedType = combineTypes( list2Begin, list2End );
-                                return unifyExact( t1, combinedType, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                                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
-                                Type * combinedType = combineTypes( list1Begin, list1End );
-                                return unifyExact( combinedType, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                                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 ) ) {
-                                Type * combinedType = combineTypes( list2Begin, list2End );
-                                return unifyExact( t1, combinedType, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                                return unifyExact( t1, combineTypes( list2Begin, list2End ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
                         } else return false;
                 } else if ( list2Begin != list2End ) {
@@ -530 +528 @@
                         Type * t2 = (*list2Begin)->get_type();
                         if ( Tuples::isTtype( t2 ) ) {
-                                Type * combinedType = combineTypes( list1Begin, list1End );
-                                return unifyExact( combinedType, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
+                                return unifyExact( combineTypes( list1Begin, list1End ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
                         } else return false;
                 } else {
@@ -538 +535 @@
         }
 
+        /// 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;
+                }
+        }
+
         void Unify::visit(FunctionType *functionType) {
                 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
                 if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
+                        // 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 ( (functionType->get_parameters().size() == otherFunction->get_parameters().size() && functionType->get_returnVals().size() == otherFunction->get_returnVals().size()) || functionType->isTtype() || otherFunction->isTtype() ) {
-                                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 ) ) {
-
+                        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 );

src/ResolvExpr/typeops.h

@@ -164 +164 @@
                         }
                 } else {
-                        *out++ = type;
+                        *out++ = type->clone();
                 }
         }