Changeset aefcc3b for src/ResolvExpr

Timestamp:

Sep 20, 2016, 4:14:13 PM (8 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:

23b6643f

Parents:

8c49c0e

Message:

major change to instantiateFunction to match arguments against the formal parameter's structure rather than the reverse

Location:

src/ResolvExpr

Files:

• Alternative.cc (modified) (1 diff)
• Alternative.h (modified) (5 diffs)
• AlternativeFinder.cc (modified) (3 diffs)
• AlternativeFinder.h (modified) (1 diff)
• Unify.cc (modified) (1 diff)

src/ResolvExpr/Alternative.cc

@@ -38 +38 @@
         }
 
+        Alternative::Alternative( Alternative && other ) : cost( other.cost ), cvtCost( other.cvtCost ), expr( other.expr ), env( other.env ) {
+                other.expr = nullptr;
+        }
+
+        Alternative & Alternative::operator=( Alternative && other ) {
+                if ( &other == this )  return *this;
+                delete expr;
+                cost = other.cost;
+                cvtCost = other.cvtCost;
+                expr = other.expr;
+                env = other.env;
+                other.expr = nullptr;
+                return *this;
+        }
+
         void Alternative::initialize( const Alternative &src, Alternative &dest ) {
                 dest.cost = src.cost;

src/ResolvExpr/Alternative.h

@@ -32 +32 @@
                 Alternative( const Alternative &other );
                 Alternative &operator=( const Alternative &other );
+                Alternative( Alternative && other );
+                Alternative &operator=( Alternative && other );
                 ~Alternative();
 
@@ -49 +51 @@
                 Type * res = expr->get_result();
                 if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) {
-                        if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( alt.expr ) ) {
+                        if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) {
+                                // can open tuple expr and dump its exploded components
                                 for ( Expression * expr : tupleExpr->get_exprs() ) {
                                         explodeUnique( expr, alt, out );
                                 }
                         } else {
+                                // tuple type, but not tuple expr - need to refer to single instance of the argument
+                                // expression and index into its components
                                 UniqueExpr * unq = new UniqueExpr( expr->clone() );
                                 for ( unsigned int i = 0; i < tupleType->size(); i++ ) {
@@ -63 +68 @@
                         }
                 } else {
+                        // atomic (non-tuple) type - output a clone of the expression in a new alternative
                         *out++ = Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost );
                 }
@@ -69 +75 @@
         /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type
         template< typename OutputIterator >
-        void explode( Alternative &alt, OutputIterator out ) {
+        void explode( const Alternative &alt, OutputIterator out ) {
                 explodeUnique( alt.expr, alt, out );
         }
@@ -75 +81 @@
         // explode list of alternatives
         template< typename OutputIterator >
-        void explode( AltList & alts, OutputIterator out ) {
-                for ( Alternative & alt : alts ) {
+        void explode( const AltList & alts, OutputIterator out ) {
+                for ( const Alternative & alt : alts ) {
                         explode( alt, out );
                 }

src/ResolvExpr/AlternativeFinder.cc

@@ -371 +371 @@
         }
 
-        bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) {
+        /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
+        /// producing expression(s) in out and their total cost in cost.
+        template< typename AltIterator, typename OutputIterator >
+        bool instantiateArgument( Type * formalType, Initializer * defaultValue, AltIterator & actualIt, AltIterator actualEnd, OpenVarSet & openVars, TypeEnvironment & resultEnv, AssertionSet & resultNeed, AssertionSet & resultHave, const SymTab::Indexer & indexer, Cost & cost, OutputIterator out ) {
+                if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
+                        // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
+                        TupleExpr * tupleExpr = new TupleExpr();
+                        for ( Type * type : *tupleType ) {
+                                if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( tupleExpr->get_exprs() ) ) ) {
+                                        delete tupleExpr;
+                                        return false;
+                                }
+                        }
+                        tupleExpr->set_result( Tuples::makeTupleType( tupleExpr->get_exprs() ) );
+                        *out++ = tupleExpr;
+                } else if ( actualIt != actualEnd ) {
+                        // both actualType and formalType are atomic (non-tuple) types - if they unify
+                        // then accept actual as an argument, otherwise return false (fail to instantiate argument)
+                        Expression * actual = actualIt->expr;
+                        Type * actualType = actual->get_result();
+                        PRINT(
+                                std::cerr << "formal type is ";
+                                formalType->print( std::cerr );
+                                std::cerr << std::endl << "actual type is ";
+                                actualType->print( std::cerr );
+                                std::cerr << std::endl;
+                        )
+                        if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
+                                return false;
+                        }
+                        // move the expression from the alternative to the output iterator
+                        *out++ = actual;
+                        actualIt->expr = nullptr;
+                        cost += actualIt->cost;
+                        ++actualIt;
+                } else {
+                        // End of actuals - Handle default values
+                        if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
+                                // so far, only constant expressions are accepted as default values
+                                if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) ) {
+                                        if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
+                                                if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
+                                                        // xxx - Don't know if this is right
+                                                        *out++ = cnstexpr->clone();
+                                                        return true;
+                                                } // if
+                                        } // if
+                                } // if
+                        } // if
+                        return false;
+                } // if
+                return true;
+        }
+
+        bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
                 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
                 // make sure we don't widen any existing bindings
@@ -379 +433 @@
                 resultEnv.extractOpenVars( openVars );
 
-                std::list< DeclarationWithType* >::iterator formal = formals.begin();
-
-                AltList newActuals;
-                explode( actuals, back_inserter( newActuals ) );
-
-                std::list< Type * > formalTypes;
-                std::list< Type * >::iterator formalType = formalTypes.end();
-
-                for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
-                        std::list< Type * > flatActualTypes;
-                        flatten( actualExpr->expr->get_result(), back_inserter( flatActualTypes ) );
-                        for ( std::list< Type* >::iterator actualType = flatActualTypes.begin(); actualType != flatActualTypes.end(); ++actualType, ++formalType ) {
-                                if ( formalType == formalTypes.end() ) {
-                                        // the type of the formal parameter may be a tuple type. To make this easier to work with,
-                                        // flatten the tuple type and traverse the resulting list of types, incrementing the formal
-                                        // iterator once its types have been extracted. Once a particular formal parameter's type has
-                                        // been exhausted load the next formal parameter's type.
-                                        if ( formal == formals.end() ) {
-                                                return isVarArgs;
-                                        }
-                                        formalTypes.clear();
-                                        flatten( (*formal)->get_type(), back_inserter( formalTypes ) );
-                                        formalType = formalTypes.begin();
-                                        ++formal;
-                                }
-                                PRINT(
-                                        std::cerr << "formal type is ";
-                                        (*formalType)->print( std::cerr );
-                                        std::cerr << std::endl << "actual type is ";
-                                        (*actualType)->print( std::cerr );
-                                        std::cerr << std::endl;
-                                )
-                                if ( ! unify( *formalType, *actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
-                                        return false;
-                                }
-                        }
-                }
-
-                // xxx - a tuple type was not completely matched
-                // partially handle the tuple with default arguments??
-                if ( formalType != formalTypes.end() ) return false;
-
-                // Handling of default values
-                while ( formal != formals.end() ) {
-                        if ( ObjectDecl *od = dynamic_cast<ObjectDecl *>( *formal ) )
-                                if ( SingleInit *si = dynamic_cast<SingleInit *>( od->get_init() ))
-                                        // so far, only constant expressions are accepted as default values
-                                        if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) )
-                                                if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) )
-                                                        if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
-                                                                // XXX Don't know if this is right
-                                                                actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) );
-                                                                formal++;
-                                                                if ( formal == formals.end()) break;
-                                                        }
-                        return false;
+                // flatten actuals so that each actual has an atomic (non-tuple) type
+                AltList exploded;
+                explode( actuals, back_inserter( exploded ) );
+
+                AltList::iterator actualExpr = exploded.begin();
+                AltList::iterator actualEnd = exploded.end();
+                for ( DeclarationWithType * formal : formals ) {
+                        // match flattened actuals with formal parameters - actuals will be grouped to match
+                        // with formals as appropriate
+                        Cost cost;
+                        std::list< Expression * > newExprs;
+                        ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
+                        if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
+                                deleteAll( newExprs );
+                                return false;
+                        }
+                        // success - produce argument as a new alternative
+                        assert( newExprs.size() == 1 );
+                        out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
+                }
+                if ( actualExpr != actualEnd ) {
+                        // there are still actuals remaining, but we've run out of formal parameters to match against
+                        // this is okay only if the function is variadic
+                        if ( ! isVarArgs ) {
+                                return false;
+                        }
+                        out.splice( out.end(), exploded, actualExpr, actualEnd );
                 }
                 return true;
@@ -565 +590 @@
 
         template< typename OutputIterator >
-        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) {
+        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
                 OpenVarSet openVars;
                 AssertionSet resultNeed, resultHave;
                 TypeEnvironment resultEnv;
                 makeUnifiableVars( funcType, openVars, resultNeed );
-                if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) {
+                AltList instantiatedActuals; // filled by instantiate function
+                if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
                         ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
-                        Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) );
-                        makeExprList( actualAlt, appExpr->get_args() );
+                        Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
+                        makeExprList( instantiatedActuals, appExpr->get_args() );
                         PRINT(
                                 std::cerr << "need assertions:" << std::endl;

src/ResolvExpr/AlternativeFinder.h

@@ -78 +78 @@
                 /// Adds alternatives for offsetof expressions, given the base type and name of the member
                 template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
-                bool instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave );
+                bool instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out );
                 template< typename OutputIterator >
-                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out );
+                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out );
                 template< typename OutputIterator >
                 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );

src/ResolvExpr/Unify.cc

@@ -416 +416 @@
 
         void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
-                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
+                for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
                         for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
                                 markAssertionSet( assertion1, *assert );