Changeset cde3891 for src/ResolvExpr


Ignore:
Timestamp:
Jan 23, 2019, 4:52:16 PM (7 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
a200795
Parents:
9b086ca (diff), 1d832f4 (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' into cleanup-dtors

Location:
src/ResolvExpr
Files:
4 added
12 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/Alternative.cc

    r9b086ca rcde3891  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sat May 16 23:44:23 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat May 16 23:54:23 2015
    13 // Update Count     : 2
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Thu Oct 11 10:55:00 2018
     13// Update Count     : 3
    1414//
    1515
    … …  
    2020#include <utility>                       // for move
    2121
    22 #include "Common/utility.h"              // for maybeClone
     22#include "Common/utility.h"              // for cloneAll
    2323#include "ResolvExpr/Cost.h"             // for Cost, Cost::zero, operator<<
    2424#include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment
    … …  
    2727
    2828namespace ResolvExpr {
    29         Alternative::Alternative() : cost( Cost::zero ), cvtCost( Cost::zero ), expr( nullptr ) {}
     29        Alternative::Alternative()
     30        : cost( Cost::zero ), cvtCost( Cost::zero ), expr( nullptr ), env(), openVars(), need() {}
    3031
    31         Alternative::Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost )
    32                 : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ) {}
     32        Alternative::Alternative( Expression *expr, const TypeEnvironment &env )
     33        : cost( Cost::zero ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars(), need() {}
     34       
     35        Alternative::Alternative( const Alternative &o, Expression *expr, const Cost &cost )
     36        : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( o.env ), openVars( o.openVars ),
     37          need() { cloneAll( o.need, need ); }
    3338
    34         Alternative::Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost, const Cost &cvtCost )
    35                 : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ) {}
     39        Alternative::Alternative( Expression *expr, const TypeEnvironment &env,
     40                const OpenVarSet& openVars, const AssertionList& oneed, const Cost& cost )
     41        : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars( openVars ),
     42          need() { cloneAll( oneed, need ); }
    3643
    37         Alternative::Alternative( const Alternative &other ) : cost( other.cost ), cvtCost( other.cvtCost ), expr( maybeClone( other.expr ) ), env( other.env ) {
    38         }
     44        Alternative::Alternative( Expression *expr, const TypeEnvironment &env,
     45                const OpenVarSet& openVars, const AssertionList& oneed, const Cost& cost,
     46                const Cost &cvtCost )
     47        : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ), openVars( openVars ),
     48          need() { cloneAll( oneed, need ); }
     49       
     50        Alternative::Alternative( Expression *expr, const TypeEnvironment &env,
     51                const OpenVarSet &openVars, const AssertionSet &oneed, const Cost &cost)
     52        : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars( openVars ),
     53          need() { cloneAll( oneed, need ); }
     54       
     55        Alternative::Alternative( Expression *expr, const TypeEnvironment &env,
     56                const OpenVarSet &openVars, const AssertionSet &oneed, const Cost &cost,
     57                const Cost& cvtCost )
     58        : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ), openVars( openVars ),
     59          need() { cloneAll( oneed, need ); }
     60       
     61        Alternative::Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars,
     62                AssertionSet &&needSet, const Cost &cost )
     63        : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( std::move(env) ),
     64          openVars( std::move(openVars) ), need( needSet.begin(), needSet.end() ) {}
     65       
     66        Alternative::Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars,
     67                AssertionSet &&needSet, const Cost &cost, const Cost &cvtCost )
     68        : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( std::move(env) ),
     69          openVars( std::move(openVars) ), need( needSet.begin(), needSet.end() ) {}
     70
     71        Alternative::Alternative( const Alternative &other )
     72        : cost( other.cost ), cvtCost( other.cvtCost ), expr( maybeClone( other.expr ) ),
     73          env( other.env ), openVars( other.openVars ), need() { cloneAll( other.need, need ); }
    3974
    4075        Alternative &Alternative::operator=( const Alternative &other ) {
    … …  
    4580                expr = maybeClone( other.expr );
    4681                env = other.env;
     82                openVars = other.openVars;
     83                need.clear();
     84                cloneAll( other.need, need );
    4785                return *this;
    4886        }
    4987
    50         Alternative::Alternative( Alternative && other ) : cost( other.cost ), cvtCost( other.cvtCost ), expr( other.expr ), env( std::move( other.env ) ) {
    51                 other.expr = nullptr;
    52         }
     88        Alternative::Alternative( Alternative && other )
     89        : cost( other.cost ), cvtCost( other.cvtCost ), expr( other.expr ),
     90          env( std::move( other.env ) ), openVars( std::move( other.openVars ) ),
     91          need( std::move( other.need ) ) { other.expr = nullptr; }
    5392
    5493        Alternative & Alternative::operator=( Alternative && other ) {
    … …  
    5998                expr = other.expr;
    6099                env = std::move( other.env );
     100                openVars = std::move( other.openVars );
     101                need = std::move( other.need );
    61102                other.expr = nullptr;
    62103                return *this;
    … …  
    64105
    65106        Alternative::~Alternative() {
     107                for ( AssertionItem& n : need ) { delete n.decl; }
    66108                delete expr;
    67109        }
    … …  
    78120                        os << "Null expression!" << std::endl;
    79121                } // if
    80                 os << indent << "Environment: ";
     122                os << indent << "Environment:";
    81123                env.print( os, indent+1 );
    82124                os << std::endl;

  • src/ResolvExpr/Alternative.h

    r9b086ca rcde3891  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sat May 16 23:45:43 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Jul 22 09:36:36 2017
    13 // Update Count     : 3
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Thu Oct 11 10:55:00 2018
     13// Update Count     : 4
    1414//
    1515
    … …  
    2020
    2121#include "Cost.h"             // for Cost
    22 #include "TypeEnvironment.h"  // for TypeEnvironment
     22#include "TypeEnvironment.h"  // for TypeEnvironment, AssertionSetValue
     23
     24#include "Common/utility.h"   // for maybeClone
    2325
    2426class Expression;
    2527
    2628namespace ResolvExpr {
     29        /// One assertion to resolve
     30        struct AssertionItem {
     31                DeclarationWithType* decl;
     32                AssertionSetValue info;
     33               
     34                AssertionItem() = default;
     35                AssertionItem( DeclarationWithType* decl, const AssertionSetValue& info )
     36                : decl(decl), info(info) {}
     37                AssertionItem( const AssertionSet::value_type& e ) : decl(e.first), info(e.second) {}
     38                operator AssertionSet::value_type () const { return { decl, info }; }
     39
     40                // to support cloneAll
     41                AssertionItem clone() const { return { maybeClone(decl), info }; }
     42        };
     43        /// A list of unresolved assertions
     44        using AssertionList = std::vector<AssertionItem>;
     45
     46        /// Clones an assertion list into an assertion set
     47        static inline void cloneAll( const AssertionList& src, AssertionSet& dst ) {
     48                for ( const AssertionItem& item : src ) {
     49                        dst.emplace( maybeClone(item.decl), item.info );
     50                }
     51        }
     52
     53        /// Clones an assertion set into an assertion list
     54        static inline void cloneAll( const AssertionSet& src, AssertionList& dst ) {
     55                dst.reserve( dst.size() + src.size() );
     56                for ( const auto& entry : src ) {
     57                        dst.emplace_back( maybeClone(entry.first), entry.second );
     58                }
     59        }
     60
     61        /// Clones an assertion list into an assertion list
     62        static inline void cloneAll( const AssertionList& src, AssertionList& dst ) {
     63                dst.reserve( dst.size() + src.size() );
     64                for ( const AssertionItem& item : src ) {
     65                        dst.emplace_back( maybeClone(item.decl), item.info );
     66                }
     67        }
     68
     69        /// One option for resolution of an expression
    2770        struct Alternative {
    2871                Alternative();
    29                 Alternative( Expression *expr, const TypeEnvironment &env, const Cost &cost );
    30                 Alternative( Expression *expr, const TypeEnvironment &env, const Cost &cost, const Cost &cvtCost );
     72                Alternative( Expression *expr, const TypeEnvironment &env );
     73                Alternative( const Alternative &o, Expression *expr, const Cost &cost );
     74                Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet& openVars,
     75                        const AssertionList& need, const Cost &cost );
     76                Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet& openVars,
     77                        const AssertionList& need, const Cost &cost, const Cost &cvtCost );
     78                Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet &openVars,
     79                        const AssertionSet &need, const Cost &cost);
     80                Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet &openVars,
     81                        const AssertionSet &need, const Cost &cost, const Cost& cvtCost );
     82                Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars,
     83                        AssertionSet &&need, const Cost &cost );
     84                Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars,
     85                        AssertionSet &&need, const Cost &cost, const Cost &cvtCost );
    3186                Alternative( const Alternative &other );
    3287                Alternative &operator=( const Alternative &other );
    … …  
    4499                }
    45100
    46                 Cost cost;
    47                 Cost cvtCost;
    48                 Expression *expr;
    49                 TypeEnvironment env;
     101                /// Sorts by cost
     102                bool operator< ( const Alternative& o ) const { return cost < o.cost; }
     103
     104                Cost cost;            ///< Cost of the whole expression
     105                Cost cvtCost;         ///< Cost of conversions to the satisfying expression
     106                Expression *expr;     ///< Satisfying expression
     107                TypeEnvironment env;  ///< Containing type environment
     108                OpenVarSet openVars;  ///< Open variables for environment
     109                AssertionList need;   ///< Assertions which need to be resolved
    50110        };
    51111

  • src/ResolvExpr/AlternativeFinder.cc

    r9b086ca rcde3891  
    1010// Created On       : Sat May 16 23:52:08 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Feb 17 11:19:39 2018
    13 // Update Count     : 33
     12// Last Modified On : Thu Nov  1 21:00:56 2018
     13// Update Count     : 35
    1414//
    1515
    … …  
    3434#include "InitTweak/InitTweak.h"   // for getFunctionName
    3535#include "RenameVars.h"            // for RenameVars, global_renamer
     36#include "ResolveAssertions.h"     // for resolveAssertions
    3637#include "ResolveTypeof.h"         // for resolveTypeof
    3738#include "Resolver.h"              // for resolveStmtExpr
    … …  
    102103                void addAnonConversions( const Alternative & alt );
    103104                /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
    104                 template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name );
     105                template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Alternative &alt, const Cost &newCost, const std::string & name );
    105106                /// Adds alternatives for member expressions where the left side has tuple type
    106                 void addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
     107                void addTupleMembers( TupleType *tupleType, Expression *expr, const Alternative &alt, const Cost &newCost, Expression *member );
    107108                /// Adds alternatives for offsetof expressions, given the base type and name of the member
    108109                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
    … …  
    113114                template<typename OutputIterator>
    114115                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
    115                 /// Checks if assertion parameters match for a new alternative
     116                /// Sets up parameter inference for an output alternative
    116117                template< typename OutputIterator >
    117                 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
     118                void inferParameters( Alternative &newAlt, OutputIterator out );
    118119        private:
    119120                AlternativeFinder & altFinder;
    … …  
    244245        }
    245246
    246         void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
     247        void AlternativeFinder::find( Expression *expr, ResolvMode mode ) {
    247248                PassVisitor<Finder> finder( *this );
    248249                expr->accept( finder );
    249                 if ( failFast && alternatives.empty() ) {
     250                if ( mode.failFast && alternatives.empty() ) {
    250251                        PRINT(
    251252                                std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
    … …  
    253254                        SemanticError( expr, "No reasonable alternatives for expression " );
    254255                }
    255                 if ( prune ) {
     256                if ( mode.resolveAssns || mode.prune ) {
     257                        // trim candidates just to those where the assertions resolve
     258                        // - necessary pre-requisite to pruning
     259                        AltList candidates;
     260                        for ( unsigned i = 0; i < alternatives.size(); ++i ) {
     261                                resolveAssertions( alternatives[i], indexer, candidates );
     262                        }
     263                        // fail early if none such
     264                        if ( mode.failFast && candidates.empty() ) {
     265                                std::ostringstream stream;
     266                                stream << "No resolvable alternatives for expression " << expr << "\n"
     267                                       << "Alternatives with failing assertions are:\n";
     268                                printAlts( alternatives, stream, 1 );
     269                                SemanticError( expr->location, stream.str() );
     270                        }
     271                        // reset alternatives
     272                        alternatives = std::move( candidates );
     273                }
     274                if ( mode.prune ) {
    256275                        auto oldsize = alternatives.size();
    257276                        PRINT(
    … …  
    261280                        AltList pruned;
    262281                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
    263                         if ( failFast && pruned.empty() ) {
     282                        if ( mode.failFast && pruned.empty() ) {
    264283                                std::ostringstream stream;
    265284                                AltList winners;
    … …  
    280299                }
    281300                // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
    282                 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
    283                         if ( adjust ) {
    284                                 adjustExprType( i->expr->get_result(), i->env, indexer );
     301                if ( mode.adjust ) {
     302                        for ( Alternative& i : alternatives ) {
     303                                adjustExprType( i.expr->get_result(), i.env, indexer );
    285304                        }
    286305                }
    … …  
    294313
    295314        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
    296                 find( expr, true );
     315                find( expr, ResolvMode::withAdjustment() );
    297316        }
    298317
    299318        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
    300                 find( expr, true, false );
     319                find( expr, ResolvMode::withoutPrune() );
    301320        }
    302321
    303322        void AlternativeFinder::maybeFind( Expression * expr ) {
    304                 find( expr, true, true, false );
     323                find( expr, ResolvMode::withoutFailFast() );
    305324        }
    306325
    … …  
    317336
    318337                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->result ) ) {
    319                         addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, "" );
     338                        addAggMembers( structInst, aggrExpr.get(), alt, alt.cost+Cost::safe, "" );
    320339                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->result ) ) {
    321                         addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, "" );
     340                        addAggMembers( unionInst, aggrExpr.get(), alt, alt.cost+Cost::safe, "" );
    322341                } // if
    323342        }
    324343
    325344        template< typename StructOrUnionType >
    326         void AlternativeFinder::Finder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name ) {
     345        void AlternativeFinder::Finder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Alternative& alt, const Cost &newCost, const std::string & name ) {
    327346                std::list< Declaration* > members;
    328347                aggInst->lookup( name, members );
    … …  
    332351                                // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
    333352                                // can't construct in place and use vector::back
    334                                 Alternative newAlt( new MemberExpr( dwt, expr->clone() ), env, newCost );
     353                                Alternative newAlt{ alt, new MemberExpr{ dwt, expr->clone() }, newCost };
    335354                                renameTypes( newAlt.expr );
    336355                                addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
    … …  
    342361        }
    343362
    344         void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
     363        void AlternativeFinder::Finder::addTupleMembers( TupleType *tupleType, Expression *expr,                        const Alternative &alt, const Cost &newCost, Expression *member ) {
    345364                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
    346365                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
    … …  
    348367                        std::string tmp;
    349368                        if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
    350                                 alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
     369                                alternatives.push_back( Alternative{
     370                                        alt, new TupleIndexExpr( expr->clone(), val ), newCost } );
    351371                        } // if
    352372                } // if
    … …  
    354374
    355375        void AlternativeFinder::Finder::postvisit( ApplicationExpr *applicationExpr ) {
    356                 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
     376                alternatives.push_back( Alternative{ applicationExpr->clone(), env } );
    357377        }
    358378
    … …  
    410430        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
    411431                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
    412                 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
    413                 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
     432                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result );
     433                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base );
    414434
    415435                Cost convCost = Cost::zero;
    416                 std::list< DeclarationWithType* >& formals = function->get_parameters();
     436                std::list< DeclarationWithType* >& formals = function->parameters;
    417437                std::list< DeclarationWithType* >::iterator formal = formals.begin();
    418                 std::list< Expression* >& actuals = appExpr->get_args();
    419 
    420                 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
    421                         Type * actualType = (*actualExpr)->get_result();
     438                std::list< Expression* >& actuals = appExpr->args;
     439
     440                for ( Expression*& actualExpr : actuals ) {
     441                        Type * actualType = actualExpr->result;
    422442                        PRINT(
    423443                                std::cerr << "actual expression:" << std::endl;
    424                                 (*actualExpr)->print( std::cerr, 8 );
     444                                actualExpr->print( std::cerr, 8 );
    425445                                std::cerr << "--- results are" << std::endl;
    426446                                actualType->print( std::cerr, 8 );
    427447                        )
    428448                        if ( formal == formals.end() ) {
    429                                 if ( function->get_isVarArgs() ) {
     449                                if ( function->isVarArgs ) {
    430450                                        convCost.incUnsafe();
    431451                                        PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
    432452                                        // convert reference-typed expressions to value-typed expressions
    433                                         referenceToRvalueConversion( *actualExpr, convCost );
     453                                        referenceToRvalueConversion( actualExpr, convCost );
    434454                                        continue;
    435455                                } else {
    … …  
    437457                                }
    438458                        }
    439                         if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( *actualExpr ) ) {
     459                        if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( actualExpr ) ) {
    440460                                // default arguments should be free - don't include conversion cost.
    441461                                // Unwrap them here because they are not relevant to the rest of the system.
    442                                 *actualExpr = def->expr;
     462                                actualExpr = def->expr;
    443463                                ++formal;
    444464                                continue;
    445465                        }
     466                        // mark conversion cost to formal and also specialization cost of formal type
    446467                        Type * formalType = (*formal)->get_type();
    447                         convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
     468                        convCost += computeExpressionConversionCost( actualExpr, formalType, indexer, alt.env );
     469                        convCost.decSpec( specCost( formalType ) );
    448470                        ++formal; // can't be in for-loop update because of the continue
    449471                }
    … …  
    452474                }
    453475
    454                 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
    455                         convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
     476                // specialization cost of return types can't be accounted for directly, it disables
     477                // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
     478                //
     479                //   forall(otype OS) {
     480                //     void ?|?(OS&, int);  // with newline
     481                //     OS&  ?|?(OS&, int);  // no newline, always chosen due to more specialization
     482                //   }
     483
     484                // mark type variable and specialization cost of forall clause
     485                convCost.incVar( function->forall.size() );
     486                for ( TypeDecl* td : function->forall ) {
     487                        convCost.decSpec( td->assertions.size() );
    456488                }
    457489
    … …  
    466498                                needAssertions[ *assert ].isUsed = true;
    467499                        }
    468 ///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
    469                 }
    470         }
    471 
    472         static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
    473 
    474         void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
    475                 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
    476                         if ( i->second.isUsed ) {
    477                                 indexer.addId( i->first );
    478                         }
    479                 }
    480         }
    481 
    482         template< typename ForwardIterator, typename OutputIterator >
    483         void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) {
    484                 if ( newAlt.cost == Cost::infinity ) return; // don't proceed down this dead end
    485                 if ( begin == end ) {
    486                         if ( newNeed.empty() ) {
    487                                 PRINT(
    488                                         std::cerr << "all assertions satisfied, output alternative: ";
    489                                         newAlt.print( std::cerr );
    490                                         std::cerr << std::endl;
    491                                 );
    492                                 *out++ = newAlt;
    493                                 return;
    494                         } else if ( level >= recursionLimit ) {
    495                                 SemanticError( newAlt.expr->location, "Too many recursive assertions" );
    496                         } else {
    497                                 AssertionSet newerNeed;
    498                                 PRINT(
    499                                         std::cerr << "recursing with new set:" << std::endl;
    500                                         printAssertionSet( newNeed, std::cerr, 8 );
    501                                 )
    502                                 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out );
    503                                 return;
    504                         }
    505                 }
    506 
    507                 ForwardIterator cur = begin++;
    508                 if ( ! cur->second.isUsed ) {
    509                         inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out );
    510                         return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
    511                 }
    512                 DeclarationWithType *curDecl = cur->first;
    513 
    514                 PRINT(
    515                         std::cerr << "inferRecursive: assertion is ";
    516                         curDecl->print( std::cerr );
    517                         std::cerr << std::endl;
    518                 )
    519                 std::list< SymTab::Indexer::IdData > candidates;
    520                 decls.lookupId( curDecl->get_name(), candidates );
    521 ///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
    522                 for ( const auto & data : candidates ) {
    523                         DeclarationWithType * candidate = data.id;
    524                         PRINT(
    525                                 std::cerr << "inferRecursive: candidate is ";
    526                                 candidate->print( std::cerr );
    527                                 std::cerr << std::endl;
    528                         )
    529 
    530                         AssertionSet newHave, newerNeed( newNeed );
    531                         TypeEnvironment newEnv( newAlt.env );
    532                         OpenVarSet newOpenVars( openVars );
    533                         Type *adjType = candidate->get_type()->clone();
    534                         adjustExprType( adjType, newEnv, indexer );
    535                         renameTyVars( adjType );
    536                         PRINT(
    537                                 std::cerr << "unifying ";
    538                                 curDecl->get_type()->print( std::cerr );
    539                                 std::cerr << " with ";
    540                                 adjType->print( std::cerr );
    541                                 std::cerr << std::endl;
    542                         )
    543                         if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
    544                                 PRINT(
    545                                         std::cerr << "success!" << std::endl;
    546                                 )
    547                                 SymTab::Indexer newDecls( decls );
    548                                 addToIndexer( newHave, newDecls );
    549                                 Alternative newerAlt( newAlt );
    550                                 newerAlt.env = newEnv;
    551                                 assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
    552 
    553                                 // everything with an empty idChain was pulled in by the current assertion.
    554                                 // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
    555                                 for ( auto & a : newerNeed ) {
    556                                         if ( a.second.idChain.empty() ) {
    557                                                 a.second.idChain = cur->second.idChain;
    558                                                 a.second.idChain.push_back( curDecl->get_uniqueId() );
    559                                         }
    560                                 }
    561 
    562                                 Expression *varExpr = data.combine( newerAlt.cvtCost );
    563                                 delete varExpr->get_result();
    564                                 varExpr->set_result( adjType->clone() );
    565                                 PRINT(
    566                                         std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
    567                                         curDecl->print( std::cerr );
    568                                         std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
    569                                         candidate->print( std::cerr );
    570                                         std::cerr << std::endl;
    571                                 )
    572                                 // 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).
    573                                 InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
    574                                 for ( UniqueId id : cur->second.idChain ) {
    575                                         inferParameters = (*inferParameters)[ id ].inferParams.get();
    576                                 }
    577                                 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
    578                                 (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
    579                                 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );
    580                         } else {
    581                                 delete adjType;
    582                         }
    583                 }
    584         }
     500                }
     501        }
     502
     503        /// Unique identifier for matching expression resolutions to their requesting expression
     504        UniqueId globalResnSlot = 0;
    585505
    586506        template< typename OutputIterator >
    587         void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
    588 //      PRINT(
    589 //          std::cerr << "inferParameters: assertions needed are" << std::endl;
    590 //          printAll( need, std::cerr, 8 );
    591 //          )
    592                 SymTab::Indexer decls( indexer );
    593                 // PRINT(
    594                 //      std::cerr << "============= original indexer" << std::endl;
    595                 //      indexer.print( std::cerr );
    596                 //      std::cerr << "============= new indexer" << std::endl;
    597                 //      decls.print( std::cerr );
    598                 // )
    599                 addToIndexer( have, decls );
    600                 AssertionSet newNeed;
    601                 PRINT(
    602                         std::cerr << "env is: " << std::endl;
    603                         newAlt.env.print( std::cerr, 0 );
    604                         std::cerr << std::endl;
    605                 )
    606 
    607                 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
    608 //      PRINT(
    609 //          std::cerr << "declaration 14 is ";
    610 //          Declaration::declFromId
    611 //          *out++ = newAlt;
    612 //          )
     507        void AlternativeFinder::Finder::inferParameters( Alternative &newAlt, OutputIterator out ) {
     508                // Set need bindings for any unbound assertions
     509                UniqueId crntResnSlot = 0;  // matching ID for this expression's assertions
     510                for ( auto& assn : newAlt.need ) {
     511                        // skip already-matched assertions
     512                        if ( assn.info.resnSlot != 0 ) continue;
     513                        // assign slot for expression if needed
     514                        if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
     515                        // fix slot to assertion
     516                        assn.info.resnSlot = crntResnSlot;
     517                }
     518                // pair slot to expression
     519                if ( crntResnSlot != 0 ) { newAlt.expr->resnSlots.push_back( crntResnSlot ); }
     520
     521                // add to output list, assertion resolution is deferred
     522                *out++ = newAlt;
    613523        }
    614524
    … …  
    951861                }
    952862                // build and validate new alternative
    953                 Alternative newAlt( appExpr, result.env, cost );
     863                Alternative newAlt{ appExpr, result.env, result.openVars, result.need, cost };
    954864                PRINT(
    955865                        std::cerr << "instantiate function success: " << appExpr << std::endl;
    … …  
    957867                        printAssertionSet( result.need, std::cerr, 8 );
    958868                )
    959                 inferParameters( result.need, result.have, newAlt, result.openVars, out );
     869                inferParameters( newAlt, out );
    960870        }
    961871
    … …  
    12021112
    12031113                // function may return struct or union value, in which case we need to add alternatives
    1204                 // for implicitconversions to each of the anonymous members, must happen after findMinCost
     1114                // for implicit conversions to each of the anonymous members, must happen after findMinCost
    12051115                // since anon conversions are never the cheapest expression
    12061116                for ( const Alternative & alt : winners ) {
    … …  
    12341144                        if ( isLvalue( alt.expr ) ) {
    12351145                                alternatives.push_back(
    1236                                         Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
     1146                                        Alternative{ alt, new AddressExpr( alt.expr->clone() ), alt.cost } );
    12371147                        } // if
    12381148                } // for
    … …  
    12401150
    12411151        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
    1242                 alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
     1152                alternatives.push_back( Alternative{ expr->clone(), env } );
    12431153        }
    12441154
    … …  
    12851195                AltList candidates;
    12861196                for ( Alternative & alt : finder.alternatives ) {
    1287                         AssertionSet needAssertions, haveAssertions;
    1288                         OpenVarSet openVars;
     1197                        AssertionSet needAssertions( alt.need.begin(), alt.need.end() );
     1198                        AssertionSet haveAssertions;
     1199                        OpenVarSet openVars{ alt.openVars };
    12891200
    12901201                        alt.env.extractOpenVars( openVars );
    … …  
    13141225                                // count one safe conversion for each value that is thrown away
    13151226                                thisCost.incSafe( discardedValues );
    1316                                 Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
    1317                                         alt.cost, thisCost );
    1318                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars,
    1319                                         back_inserter( candidates ) );
     1227                                Alternative newAlt{
     1228                                        restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ),
     1229                                        alt.env, openVars, needAssertions, alt.cost, alt.cost + thisCost };
     1230                                inferParameters( newAlt, back_inserter( candidates ) );
    13201231                        } // if
    13211232                } // for
    … …  
    13301241
    13311242        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
    1332                 assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
     1243                assertf( castExpr->get_result(), "Implicit virtual cast targets not yet supported." );
    13331244                AlternativeFinder finder( indexer, env );
    13341245                // don't prune here, since it's guaranteed all alternatives will have the same type
    13351246                finder.findWithoutPrune( castExpr->get_arg() );
    13361247                for ( Alternative & alt : finder.alternatives ) {
    1337                         alternatives.push_back( Alternative(
    1338                                 new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
    1339                                 alt.env, alt.cost ) );
     1248                        alternatives.push_back( Alternative{
     1249                                alt, new VirtualCastExpr{ alt.expr->clone(), castExpr->get_result()->clone() },
     1250                                alt.cost } );
    13401251                }
    13411252        }
    … …  
    13441255                /// Gets name from untyped member expression (member must be NameExpr)
    13451256                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
     1257                        if ( dynamic_cast< ConstantExpr * >( memberExpr->get_member() ) ) {
     1258                                SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
     1259                        } // if
    13461260                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
    13471261                        assert( nameExpr );
    … …  
    13621276                        // find member of the given type
    13631277                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
    1364                                 addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
     1278                                addAggMembers( structInst, aggrExpr, *agg, cost, get_member_name(memberExpr) );
    13651279                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
    1366                                 addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
     1280                                addAggMembers( unionInst, aggrExpr, *agg, cost, get_member_name(memberExpr) );
    13671281                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
    1368                                 addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
     1282                                addTupleMembers( tupleType, aggrExpr, *agg, cost, memberExpr->get_member() );
    13691283                        } // if
    13701284                } // for
    … …  
    13721286
    13731287        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
    1374                 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
     1288                alternatives.push_back( Alternative{ memberExpr->clone(), env } );
    13751289        }
    13761290
    … …  
    13851299                        // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
    13861300                        // can't construct in place and use vector::back
    1387                         Alternative newAlt( newExpr, env, Cost::zero, cost );
     1301                        Alternative newAlt{ newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost };
    13881302                        PRINT(
    13891303                                std::cerr << "decl is ";
    … …  
    14031317                // not sufficient to clone here, because variable's type may have changed
    14041318                // since the VariableExpr was originally created.
    1405                 alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
     1319                alternatives.push_back( Alternative{ new VariableExpr{ variableExpr->var }, env } );
    14061320        }
    14071321
    14081322        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
    1409                 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
     1323                alternatives.push_back( Alternative{ constantExpr->clone(), env } );
    14101324        }
    14111325
    … …  
    14131327                if ( sizeofExpr->get_isType() ) {
    14141328                        Type * newType = sizeofExpr->get_type()->clone();
    1415                         alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
     1329                        alternatives.push_back( Alternative{
     1330                                new SizeofExpr{ resolveTypeof( newType, indexer ) }, env } );
    14161331                } else {
    14171332                        // find all alternatives for the argument to sizeof
    … …  
    14271342                        Alternative &choice = winners.front();
    14281343                        referenceToRvalueConversion( choice.expr, choice.cost );
    1429                         alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
     1344                        alternatives.push_back( Alternative{
     1345                                choice, new SizeofExpr( choice.expr->clone() ), Cost::zero } );
    14301346                } // if
    14311347        }
    … …  
    14341350                if ( alignofExpr->get_isType() ) {
    14351351                        Type * newType = alignofExpr->get_type()->clone();
    1436                         alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
     1352                        alternatives.push_back( Alternative{
     1353                                new AlignofExpr{ resolveTypeof( newType, indexer ) }, env } );
    14371354                } else {
    14381355                        // find all alternatives for the argument to sizeof
    … …  
    14481365                        Alternative &choice = winners.front();
    14491366                        referenceToRvalueConversion( choice.expr, choice.cost );
    1450                         alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
     1367                        alternatives.push_back( Alternative{
     1368                                choice, new AlignofExpr{ choice.expr->clone() }, Cost::zero } );
    14511369                } // if
    14521370        }
    … …  
    14581376                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
    14591377                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
    1460                                 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
     1378                                alternatives.push_back( Alternative{
     1379                                        new OffsetofExpr{ aggInst->clone(), dwt }, env } );
    14611380                                renameTypes( alternatives.back().expr );
    14621381                        } else {
    … …  
    14771396
    14781397        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
    1479                 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
     1398                alternatives.push_back( Alternative{ offsetofExpr->clone(), env } );
    14801399        }
    14811400
    14821401        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
    1483                 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
     1402                alternatives.push_back( Alternative{ offsetPackExpr->clone(), env } );
    14841403        }
    14851404
    … …  
    15011420                                Cost cost = Cost::zero;
    15021421                                Expression * newExpr = data.combine( cost );
    1503                                 alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
     1422                                alternatives.push_back( Alternative{
     1423                                        new AttrExpr{ newExpr, argType->clone() }, env, OpenVarSet{},
     1424                                        AssertionList{}, Cost::zero, cost } );
    15041425                                for ( DeclarationWithType * retVal : function->returnVals ) {
    15051426                                        alternatives.back().expr->result = retVal->get_type()->clone();
    … …  
    15401461                                Cost cost = Cost::zero;
    15411462                                Expression * newExpr = data.combine( cost );
    1542                                 alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
     1463                                alternatives.push_back( Alternative{
     1464                                        newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost } );
    15431465                                renameTypes( alternatives.back().expr );
    15441466                        } // for
    … …  
    15551477                for ( const Alternative & first : firstFinder.alternatives ) {
    15561478                        for ( const Alternative & second : secondFinder.alternatives ) {
    1557                                 TypeEnvironment compositeEnv;
    1558                                 compositeEnv.simpleCombine( first.env );
     1479                                TypeEnvironment compositeEnv{ first.env };
    15591480                                compositeEnv.simpleCombine( second.env );
    1560 
    1561                                 LogicalExpr *newExpr = new LogicalExpr( first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() );
    1562                                 alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
     1481                                OpenVarSet openVars{ first.openVars };
     1482                                mergeOpenVars( openVars, second.openVars );
     1483                                AssertionSet need;
     1484                                cloneAll( first.need, need );
     1485                                cloneAll( second.need, need );
     1486
     1487                                LogicalExpr *newExpr = new LogicalExpr{
     1488                                        first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() };
     1489                                alternatives.push_back( Alternative{
     1490                                        newExpr, std::move(compositeEnv), std::move(openVars),
     1491                                        AssertionList( need.begin(), need.end() ), first.cost + second.cost } );
    15631492                        }
    15641493                }
    … …  
    15811510                        for ( const Alternative & second : secondFinder.alternatives ) {
    15821511                                for ( const Alternative & third : thirdFinder.alternatives ) {
    1583                                         TypeEnvironment compositeEnv;
    1584                                         compositeEnv.simpleCombine( first.env );
     1512                                        TypeEnvironment compositeEnv{ first.env };
    15851513                                        compositeEnv.simpleCombine( second.env );
    15861514                                        compositeEnv.simpleCombine( third.env );
    1587 
     1515                                        OpenVarSet openVars{ first.openVars };
     1516                                        mergeOpenVars( openVars, second.openVars );
     1517                                        mergeOpenVars( openVars, third.openVars );
     1518                                        AssertionSet need;
     1519                                        cloneAll( first.need, need );
     1520                                        cloneAll( second.need, need );
     1521                                        cloneAll( third.need, need );
     1522                                        AssertionSet have;
     1523                                       
    15881524                                        // unify true and false types, then infer parameters to produce new alternatives
    1589                                         OpenVarSet openVars;
    1590                                         AssertionSet needAssertions, haveAssertions;
    1591                                         Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
    15921525                                        Type* commonType = nullptr;
    1593                                         if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
    1594                                                 ConditionalExpr *newExpr = new ConditionalExpr( first.expr->clone(), second.expr->clone(), third.expr->clone() );
     1526                                        if ( unify( second.expr->result, third.expr->result, compositeEnv,
     1527                                                        need, have, openVars, indexer, commonType ) ) {
     1528                                                ConditionalExpr *newExpr = new ConditionalExpr{
     1529                                                        first.expr->clone(), second.expr->clone(), third.expr->clone() };
    15951530                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
    15961531                                                // convert both options to the conditional result type
    1597                                                 newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
    1598                                                 newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
    1599                                                 newAlt.expr = newExpr;
    1600                                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
     1532                                                Cost cost = first.cost + second.cost + third.cost;
     1533                                                cost += computeExpressionConversionCost(
     1534                                                        newExpr->arg2, newExpr->result, indexer, compositeEnv );
     1535                                                cost += computeExpressionConversionCost(
     1536                                                        newExpr->arg3, newExpr->result, indexer, compositeEnv );
     1537                                                // output alternative
     1538                                                Alternative newAlt{
     1539                                                        newExpr, std::move(compositeEnv), std::move(openVars),
     1540                                                        AssertionList( need.begin(), need.end() ), cost };
     1541                                                inferParameters( newAlt, back_inserter( alternatives ) );
    16011542                                        } // if
    16021543                                } // for
    … …  
    16111552                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
    16121553                for ( const Alternative & alt : secondFinder.alternatives ) {
    1613                         alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt.expr->clone() ), alt.env, alt.cost ) );
     1554                        alternatives.push_back( Alternative{
     1555                                alt, new CommaExpr{ newFirstArg->clone(), alt.expr->clone() }, alt.cost } );
    16141556                } // for
    16151557                delete newFirstArg;
    … …  
    16261568                for ( const Alternative & first : firstFinder.alternatives ) {
    16271569                        for ( const Alternative & second : secondFinder.alternatives ) {
    1628                                 TypeEnvironment compositeEnv;
    1629                                 compositeEnv.simpleCombine( first.env );
     1570                                TypeEnvironment compositeEnv{ first.env };
    16301571                                compositeEnv.simpleCombine( second.env );
    1631                                 OpenVarSet openVars;
    1632                                 AssertionSet needAssertions, haveAssertions;
    1633                                 Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
     1572                                OpenVarSet openVars{ first.openVars };
     1573                                mergeOpenVars( openVars, second.openVars );
     1574                                AssertionSet need;
     1575                                cloneAll( first.need, need );
     1576                                cloneAll( second.need, need );
     1577                                AssertionSet have;
     1578
    16341579                                Type* commonType = nullptr;
    1635                                 if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
    1636                                         RangeExpr * newExpr = new RangeExpr( first.expr->clone(), second.expr->clone() );
     1580                                if ( unify( first.expr->result, second.expr->result, compositeEnv, need, have,
     1581                                                openVars, indexer, commonType ) ) {
     1582                                        RangeExpr * newExpr =
     1583                                                new RangeExpr{ first.expr->clone(), second.expr->clone() };
    16371584                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
    1638                                         newAlt.expr = newExpr;
    1639                                         inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
     1585                                        Alternative newAlt{
     1586                                                newExpr, std::move(compositeEnv), std::move(openVars),
     1587                                                AssertionList( need.begin(), need.end() ), first.cost + second.cost };
     1588                                        inferParameters( newAlt, back_inserter( alternatives ) );
    16401589                                } // if
    16411590                        } // for
    … …  
    16551604
    16561605                        TypeEnvironment compositeEnv;
    1657                         simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
    1658                         alternatives.push_back(
    1659                                 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
     1606                        OpenVarSet openVars;
     1607                        AssertionSet need;
     1608                        for ( const Alternative& alt : alts ) {
     1609                                compositeEnv.simpleCombine( alt.env );
     1610                                mergeOpenVars( openVars, alt.openVars );
     1611                                cloneAll( alt.need, need );
     1612                        }
     1613                       
     1614                        alternatives.push_back( Alternative{
     1615                                new TupleExpr{ exprs }, std::move(compositeEnv), std::move(openVars),
     1616                                AssertionList( need.begin(), need.end() ), sumCost( alts ) } );
    16601617                } // for
    16611618        }
    16621619
    16631620        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
    1664                 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
     1621                alternatives.push_back( Alternative{ tupleExpr->clone(), env } );
    16651622        }
    16661623
    16671624        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
    1668                 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
     1625                alternatives.push_back( Alternative{ impCpCtorExpr->clone(), env } );
    16691626        }
    16701627
    … …  
    16751632                finder.findWithoutPrune( ctorExpr->get_callExpr() );
    16761633                for ( Alternative & alt : finder.alternatives ) {
    1677                         alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
     1634                        alternatives.push_back( Alternative{
     1635                                alt, new ConstructorExpr( alt.expr->clone() ), alt.cost } );
    16781636                }
    16791637        }
    16801638
    16811639        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
    1682                 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
     1640                alternatives.push_back( Alternative{ tupleExpr->clone(), env } );
    16831641        }
    16841642
    16851643        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
    1686                 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
     1644                alternatives.push_back( Alternative{ tupleAssignExpr->clone(), env } );
    16871645        }
    16881646
    … …  
    16931651                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
    16941652                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
    1695                         alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
     1653                        alternatives.push_back( Alternative{ alt, newUnqExpr, alt.cost } );
    16961654                }
    16971655        }
    … …  
    17011659                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
    17021660                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
    1703                 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
     1661                alternatives.push_back( Alternative{ newStmtExpr, env } );
    17041662        }
    17051663
    … …  
    17231681                        for ( Alternative & alt : finder.get_alternatives() ) {
    17241682                                TypeEnvironment newEnv( alt.env );
    1725                                 AssertionSet needAssertions, haveAssertions;
    1726                                 OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
     1683                                AssertionSet need;
     1684                                cloneAll( alt.need, need );
     1685                                AssertionSet have;
     1686                                OpenVarSet openVars( alt.openVars ); 
     1687                                // xxx - find things in env that don't have a "representative type" and claim
     1688                                // those are open vars?
    17271689                                PRINT(
    17281690                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
    17291691                                )
    1730                                 // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
    1731                                 // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
    1732                                 // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
    1733                                 // to.
     1692                                // It's possible that a cast can throw away some values in a multiply-valued
     1693                                // expression. (An example is a cast-to-void, which casts from one value to
     1694                                // zero.)  Figure out the prefix of the subexpression results that are cast
     1695                                // directly.  The candidate is invalid if it has fewer results than there are
     1696                                // types to cast to.
    17341697                                int discardedValues = alt.expr->result->size() - toType->size();
    17351698                                if ( discardedValues < 0 ) continue;
    1736                                 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
    1737                                 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
     1699                                // xxx - may need to go into tuple types and extract relevant types and use
     1700                                // unifyList. Note that currently, this does not allow casting a tuple to an
     1701                                // atomic type (e.g. (int)([1, 2, 3]))
     1702                               
    17381703                                // unification run for side-effects
    1739                                 unify( toType, alt.expr->result, newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
     1704                                unify( toType, alt.expr->result, newEnv, need, have, openVars, indexer );
     1705                                // xxx - do some inspecting on this line... why isn't result bound to initAlt.type?
    17401706
    17411707                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
    … …  
    17431709                                        // count one safe conversion for each value that is thrown away
    17441710                                        thisCost.incSafe( discardedValues );
    1745                                         Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
    1746                                         inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
     1711                                        Alternative newAlt{
     1712                                                new InitExpr{
     1713                                                        restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() },
     1714                                                std::move(newEnv), std::move(openVars),
     1715                                                AssertionList( need.begin(), need.end() ), alt.cost, thisCost };
     1716                                        inferParameters( newAlt, back_inserter( candidates ) );
    17471717                                }
    17481718                        }

  • src/ResolvExpr/AlternativeFinder.h

    r9b086ca rcde3891  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sat May 16 23:56:12 2015
    11 // Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Jul 26 11:24:00 2017
    13 // Update Count     : 4
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Fri Oct -5 10:01:00 2018
     13// Update Count     : 5
    1414//
    1515
    … …  
    2424#include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
    2525#include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
     26#include "ResolvMode.h"                  // for ResolvMode
    2627#include "SynTree/Visitor.h"             // for Visitor
    2728#include "SynTree/SynTree.h"             // for Visitor Nodes
    … …  
    6869                }
    6970
    70                 void find( Expression *expr, bool adjust = false, bool prune = true, bool failFast = true );
     71                void find( Expression *expr, ResolvMode mode = ResolvMode{} );
    7172                /// Calls find with the adjust flag set; adjustment turns array and function types into equivalent pointer types
    7273                void findWithAdjustment( Expression *expr );

  • src/ResolvExpr/ConversionCost.cc

    r9b086ca rcde3891  
    2828
    2929namespace ResolvExpr {
    30         const Cost Cost::zero =      Cost(  0,  0,  0,  0 );
    31         const Cost Cost::infinity =  Cost( -1, -1, -1, -1 );
    32         const Cost Cost::unsafe =    Cost(  1,  0,  0,  0 );
    33         const Cost Cost::poly =      Cost(  0,  1,  0,  0 );
    34         const Cost Cost::safe =      Cost(  0,  0,  1,  0 );
    35         const Cost Cost::reference = Cost(  0,  0,  0,  1 );
     30        const Cost Cost::zero =      Cost{  0,  0,  0,  0,  0,  0 };
     31        const Cost Cost::infinity =  Cost{ -1, -1, -1, -1,  1, -1 };
     32        const Cost Cost::unsafe =    Cost{  1,  0,  0,  0,  0,  0 };
     33        const Cost Cost::poly =      Cost{  0,  1,  0,  0,  0,  0 };
     34        const Cost Cost::safe =      Cost{  0,  0,  1,  0,  0,  0 };
     35        const Cost Cost::var =       Cost{  0,  0,  0,  1,  0,  0 };
     36        const Cost Cost::spec =      Cost{  0,  0,  0,  0, -1,  0 };
     37        const Cost Cost::reference = Cost{  0,  0,  0,  0,  0,  1 };
    3638
    3739#if 0

  • src/ResolvExpr/Cost.h

    r9b086ca rcde3891  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 09:39:50 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Jul 22 09:35:55 2017
    13 // Update Count     : 5
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Fri Oct 05 14:32:00 2018
     13// Update Count     : 7
    1414//
    1515
    … …  
    2121        class Cost {
    2222          private:
    23                 Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost );
     23                Cost( int unsafeCost, int polyCost, int safeCost, int varCost, int specCost,
     24                        int referenceCost );
    2425
    2526          public:
    … …  
    2728                Cost & incPoly( int inc = 1 );
    2829                Cost & incSafe( int inc = 1 );
     30                Cost & incVar( int inc = 1 );
     31                Cost & decSpec( int inc = 1 );
    2932                Cost & incReference( int inc = 1 );
    3033
    … …  
    3235                int get_polyCost() const { return polyCost; }
    3336                int get_safeCost() const { return safeCost; }
     37                int get_varCost() const { return varCost; }
     38                int get_specCost() const { return specCost; }
    3439                int get_referenceCost() const { return referenceCost; }
    3540
    … …  
    4146                bool operator!=( const Cost &other ) const;
    4247                friend std::ostream &operator<<( std::ostream &os, const Cost &cost );
     48                // returns negative for *this < other, 0 for *this == other, positive for *this > other
     49                int compare( const Cost &other ) const;
    4350
    4451                static const Cost zero;
    … …  
    4855                static const Cost poly;
    4956                static const Cost safe;
     57                static const Cost var;
     58                static const Cost spec;
    5059                static const Cost reference;
     60
    5161          private:
    52                 int compare( const Cost &other ) const;
    53 
    54                 int unsafeCost;
    55                 int polyCost;
    56                 int safeCost;
    57                 int referenceCost;
     62                int unsafeCost;     ///< Unsafe (narrowing) conversions
     63                int polyCost;       ///< Count of parameters and return values bound to some poly type
     64                int safeCost;       ///< Safe (widening) conversions
     65                int varCost;        ///< Count of polymorphic type variables
     66                int specCost;       ///< Polymorphic type specializations (type assertions), negative cost
     67                int referenceCost;  ///< reference conversions
    5868        };
    5969
    60         inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), referenceCost( referenceCost ) {}
     70        inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int varCost, int specCost,
     71                        int referenceCost )
     72                : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), varCost( varCost ),
     73                  specCost( specCost ), referenceCost( referenceCost ) {}
    6174
    6275        inline Cost & Cost::incUnsafe( int inc ) {
    … …  
    7588                if ( *this == infinity ) return *this;
    7689                safeCost += inc;
     90                return *this;
     91        }
     92
     93        inline Cost & Cost::incVar( int inc ) {
     94                if ( *this == infinity ) return *this;
     95                varCost += inc;
     96                return *this;
     97        }
     98
     99        inline Cost& Cost::decSpec( int dec ) {
     100                if ( *this == infinity ) return *this;
     101                specCost -= dec;
    77102                return *this;
    78103        }
    … …  
    86111        inline Cost Cost::operator+( const Cost &other ) const {
    87112                if ( *this == infinity || other == infinity ) return infinity;
    88                 return Cost( unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost, referenceCost + other.referenceCost );
     113                return Cost{
     114                        unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost,
     115                        varCost + other.varCost, specCost + other.specCost,
     116                        referenceCost + other.referenceCost };
    89117        }
    90118
    91119        inline Cost Cost::operator-( const Cost &other ) const {
    92120                if ( *this == infinity || other == infinity ) return infinity;
    93                 return Cost( unsafeCost - other.unsafeCost, polyCost - other.polyCost, safeCost - other.safeCost, referenceCost - other.referenceCost );
     121                return Cost{
     122                        unsafeCost - other.unsafeCost, polyCost - other.polyCost, safeCost - other.safeCost,
     123                        varCost - other.varCost, specCost - other.specCost,
     124                        referenceCost - other.referenceCost };
    94125        }
    95126
    … …  
    103134                polyCost += other.polyCost;
    104135                safeCost += other.safeCost;
     136                varCost += other.varCost;
     137                specCost += other.specCost;
    105138                referenceCost += other.referenceCost;
    106139                return *this;
    … …  
    123156                } else if ( safeCost < other.safeCost ) {
    124157                        return true;
     158                } else if ( varCost > other.varCost ) {
     159                        return false;
     160                } else if ( varCost < other.varCost ) {
     161                        return true;
     162                } else if ( specCost > other.specCost ) {
     163                        return false;
     164                } else if ( specCost > other.specCost ) {
     165                        return true;
    125166                } else if ( referenceCost > other.referenceCost ) {
    126167                        return false;
    … …  
    130171                        return false;
    131172                } // if
     173        }
     174
     175        inline int Cost::compare( const Cost &other ) const {
     176                if ( *this == infinity ) return +1;
     177                if ( other == infinity ) return -1;
     178
     179                int c = unsafeCost - other.unsafeCost; if ( c ) return c;
     180                c = polyCost - other.polyCost; if ( c ) return c;
     181                c = safeCost - other.safeCost; if ( c ) return c;
     182                c = varCost - other.varCost; if ( c ) return c;
     183                c = specCost - other.specCost; if ( c ) return c;
     184                return referenceCost - other.referenceCost;
    132185        }
    133186
    … …  
    136189                        && polyCost == other.polyCost
    137190                        && safeCost == other.safeCost
     191                        && varCost == other.varCost
     192                        && specCost == other.specCost
    138193                        && referenceCost == other.referenceCost;
    139194        }
    … …  
    144199
    145200        inline std::ostream &operator<<( std::ostream &os, const Cost &cost ) {
    146                 os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " << cost.safeCost << ", " << cost.referenceCost << " )";
    147                 return os;
     201                return os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", "
     202                          << cost.safeCost << ", " << cost.varCost << ", " << cost.specCost << ", "
     203                          << cost.referenceCost << " )";
    148204        }
    149205} // namespace ResolvExpr

  • src/ResolvExpr/ResolveTypeof.cc

    r9b086ca rcde3891  
    6767                std::cerr << std::endl;
    6868#endif
    69                 if ( typeofType->expr ) {
     69                // pass on null expression
     70                if ( ! typeofType->expr ) return typeofType;
     71
     72                bool isBasetypeof = typeofType->is_basetypeof;
     73                auto oldQuals = typeofType->get_qualifiers().val;
     74
     75                Type* newType;
     76                if ( TypeExpr* tyExpr = dynamic_cast<TypeExpr*>(typeofType->expr) ) {
     77                        // typeof wrapping type
     78                        newType = tyExpr->type;
     79                        tyExpr->type = nullptr;
     80                        delete tyExpr;
     81                } else {
     82                        // typeof wrapping expression
    7083                        Expression * newExpr = resolveInVoidContext( typeofType->expr, indexer );
    7184                        assert( newExpr->result && ! newExpr->result->isVoid() );
    72                         Type * newType = newExpr->result;
     85                        newType = newExpr->result;
    7386                        newExpr->result = nullptr;
    7487                        delete typeofType;
    7588                        delete newExpr;
    76                         return newType;
    77                 } // if
    78                 return typeofType;
     89                }
     90
     91                // clear qualifiers for base, combine with typeoftype quals in any case
     92                if ( isBasetypeof ) {
     93                        // replace basetypeof(<enum>) by int
     94                        if ( dynamic_cast<EnumInstType*>(newType) ) {
     95                                Type* newerType =
     96                                        new BasicType{ newType->get_qualifiers(), BasicType::SignedInt,
     97                                        newType->attributes };
     98                                delete newType;
     99                                newType = newerType;
     100                        }
     101                        newType->get_qualifiers().val
     102                                = ( newType->get_qualifiers().val & ~Type::Qualifiers::Mask ) | oldQuals;
     103                } else {
     104                        newType->get_qualifiers().val |= oldQuals;
     105                }
     106               
     107                return newType;
    79108        }
    80109} // namespace ResolvExpr

  • src/ResolvExpr/Resolver.cc

    r9b086ca rcde3891  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 12:17:01 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Feb 17 11:19:40 2018
    13 // Update Count     : 213
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Fri Oct 05 09:43:00 2018
     13// Update Count     : 214
    1414//
    1515
    16 #include <stddef.h>                      // for NULL
    1716#include <cassert>                       // for strict_dynamic_cast, assert
    1817#include <memory>                        // for allocator, allocator_traits<...
    1918#include <tuple>                         // for get
    20 #include <vector>
     19#include <vector>                        // for vector
    2120
    2221#include "Alternative.h"                 // for Alternative, AltList
    … …  
    3130#include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment
    3231#include "Resolver.h"
     32#include "ResolvMode.h"                  // for ResolvMode
     33#include "SymTab/Autogen.h"              // for SizeType
    3334#include "SymTab/Indexer.h"              // for Indexer
    3435#include "SynTree/Declaration.h"         // for ObjectDecl, TypeDecl, Declar...
    … …  
    168169
    169170        namespace {
    170                 void findUnfinishedKindExpression(Expression * untyped, Alternative & alt, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, bool adjust = false, bool prune = true, bool failFast = true) {
     171                void findUnfinishedKindExpression(Expression * untyped, Alternative & alt, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, ResolvMode mode = ResolvMode{} ) {
    171172                        assertf( untyped, "expected a non-null expression." );
     173
     174                        // xxx - this isn't thread-safe, but should work until we parallelize the resolver
     175                        static unsigned recursion_level = 0;
     176
     177                        ++recursion_level;
    172178                        TypeEnvironment env;
    173179                        AlternativeFinder finder( indexer, env );
    174                         finder.find( untyped, adjust, prune, failFast );
     180                        finder.find( untyped, recursion_level == 1 ? mode.atTopLevel() : mode );
     181                        --recursion_level;
    175182
    176183                        #if 0
    … …  
    185192                        #endif
    186193
     194                        // produce filtered list of alternatives
    187195                        AltList candidates;
    188196                        for ( Alternative & alt : finder.get_alternatives() ) {
    … …  
    192200                        }
    193201
    194                         // xxx - if > 1 alternative with same cost, ignore deleted and pick from remaining
    195                         // choose the lowest cost expression among the candidates
     202                        // produce invalid error if no candidates
     203                        if ( candidates.empty() ) {
     204                                SemanticError( untyped, toString( "No reasonable alternatives for ", kindStr, (kindStr != "" ? " " : ""), "expression: ") );
     205                        }
     206
     207                        // search for cheapest candidate
    196208                        AltList winners;
    197                         findMinCost( candidates.begin(), candidates.end(), back_inserter( winners ) );
    198                         if ( winners.size() == 0 ) {
    199                                 SemanticError( untyped, toString( "No reasonable alternatives for ", kindStr, (kindStr != "" ? " " : ""), "expression: ") );
    200                         } else if ( winners.size() != 1 ) {
     209                        bool seen_undeleted = false;
     210                        for ( unsigned i = 0; i < candidates.size(); ++i ) {
     211                                int c = winners.empty() ? -1 : candidates[i].cost.compare( winners.front().cost );
     212
     213                                if ( c > 0 ) continue; // skip more expensive than winner
     214
     215                                if ( c < 0 ) {
     216                                        // reset on new cheapest
     217                                        seen_undeleted = ! findDeletedExpr( candidates[i].expr );
     218                                        winners.clear();
     219                                } else /* if ( c == 0 ) */ {
     220                                        if ( findDeletedExpr( candidates[i].expr ) ) {
     221                                                // skip deleted expression if already seen one equivalent-cost not
     222                                                if ( seen_undeleted ) continue;
     223                                        } else if ( ! seen_undeleted ) {
     224                                                // replace list of equivalent-cost deleted expressions with one non-deleted
     225                                                winners.clear();
     226                                                seen_undeleted = true;
     227                                        }
     228                                }
     229
     230                                winners.emplace_back( std::move( candidates[i] ) );
     231                        }
     232
     233                        // promote alternative.cvtCost to .cost
     234                        // xxx - I don't know why this is done, but I'm keeping the behaviour from findMinCost
     235                        for ( Alternative& winner : winners ) {
     236                                winner.cost = winner.cvtCost;
     237                        }
     238
     239                        // produce ambiguous errors, if applicable
     240                        if ( winners.size() != 1 ) {
    201241                                std::ostringstream stream;
    202242                                stream << "Cannot choose between " << winners.size() << " alternatives for " << kindStr << (kindStr != "" ? " " : "") << "expression\n";
    … …  
    207247                        }
    208248
    209                         // there is one unambiguous interpretation - move the expression into the with statement
    210                         Alternative & choice = winners.front();
    211                         if ( findDeletedExpr( choice.expr ) ) {
     249                        // single selected choice
     250                        Alternative& choice = winners.front();
     251
     252                        // fail on only expression deleted
     253                        if ( ! seen_undeleted ) {
    212254                                SemanticError( untyped->location, choice.expr, "Unique best alternative includes deleted identifier in " );
    213255                        }
     256
     257                        // xxx - check for ambiguous expressions
     258
     259                        // output selected choice
    214260                        alt = std::move( choice );
    215261                }
    216262
    217263                /// resolve `untyped` to the expression whose alternative satisfies `pred` with the lowest cost; kindStr is used for providing better error messages
    218                 void findKindExpression(Expression *& untyped, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, bool adjust = false, bool prune = true, bool failFast = true) {
     264                void findKindExpression(Expression *& untyped, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, ResolvMode mode = ResolvMode{}) {
    219265                        if ( ! untyped ) return;
    220266                        Alternative choice;
    221                         findUnfinishedKindExpression( untyped, choice, indexer, kindStr, pred, adjust, prune, failFast );
     267                        findUnfinishedKindExpression( untyped, choice, indexer, kindStr, pred, mode );
    222268                        finishExpr( choice.expr, choice.env, untyped->env );
    223269                        delete untyped;
    … …  
    250296                untyped.arg = expr;
    251297                Alternative choice;
    252                 findUnfinishedKindExpression( &untyped, choice, indexer, "", standardAlternativeFilter, true );
     298                findUnfinishedKindExpression( &untyped, choice, indexer, "", standardAlternativeFilter, ResolvMode::withAdjustment() );
    253299                CastExpr * castExpr = strict_dynamic_cast< CastExpr * >( choice.expr );
    254300                env = std::move( choice.env );
    … …  
    357403
    358404        void Resolver::previsit( ObjectDecl *objectDecl ) {
    359                 // To handle initialization of routine pointers, e.g., int (*fp)(int) = foo(), means that class-variable
    360                 // initContext is changed multiple time because the LHS is analysed twice. The second analysis changes
    361                 // initContext because of a function type can contain object declarations in the return and parameter types. So
    362                 // each value of initContext is retained, so the type on the first analysis is preserved and used for selecting
    363                 // the RHS.
     405                // To handle initialization of routine pointers, e.g., int (*fp)(int) = foo(), means that
     406                // class-variable initContext is changed multiple time because the LHS is analysed twice.
     407                // The second analysis changes initContext because of a function type can contain object
     408                // declarations in the return and parameter types. So each value of initContext is
     409                // retained, so the type on the first analysis is preserved and used for selecting the RHS.
    364410                GuardValue( currentObject );
    365411                currentObject = CurrentObject( objectDecl->get_type() );
    … …  
    397443
    398444        void Resolver::postvisit( FunctionDecl *functionDecl ) {
    399                 // default value expressions have an environment which shouldn't be there and trips up later passes.
    400                 // xxx - it might be necessary to somehow keep the information from this environment, but I can't currently
    401                 // see how it's useful.
     445                // default value expressions have an environment which shouldn't be there and trips up
     446                // later passes.
     447                // xxx - it might be necessary to somehow keep the information from this environment, but I
     448                // can't currently see how it's useful.
    402449                for ( Declaration * d : functionDecl->type->parameters ) {
    403450                        if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( d ) ) {
    … …  
    749796                initExpr->expr = nullptr;
    750797                std::swap( initExpr->env, newExpr->env );
    751                 // InitExpr may have inferParams in the case where the expression specializes a function pointer,
    752                 // and newExpr may already have inferParams of its own, so a simple swap is not sufficient.
     798                // InitExpr may have inferParams in the case where the expression specializes a function
     799                // pointer, and newExpr may already have inferParams of its own, so a simple swap is not
     800                // sufficient.
    753801                newExpr->spliceInferParams( initExpr );
    754802                delete initExpr;
    755803
    756                 // get the actual object's type (may not exactly match what comes back from the resolver due to conversions)
     804                // get the actual object's type (may not exactly match what comes back from the resolver
     805                // due to conversions)
    757806                Type * initContext = currentObject.getCurrentType();
    758807
    … …  
    766815                                        if ( isCharType( pt->get_base() ) ) {
    767816                                                if ( CastExpr *ce = dynamic_cast< CastExpr * >( newExpr ) ) {
    768                                                         // strip cast if we're initializing a char[] with a char *, e.g.  char x[] = "hello";
     817                                                        // strip cast if we're initializing a char[] with a char *,
     818                                                        // e.g.  char x[] = "hello";
    769819                                                        newExpr = ce->get_arg();
    770820                                                        ce->set_arg( nullptr );
    … …  
    788838                // move cursor into brace-enclosed initializer-list
    789839                currentObject.enterListInit();
    790                 // xxx - fix this so that the list isn't copied, iterator should be used to change current element
     840                // xxx - fix this so that the list isn't copied, iterator should be used to change current
     841                // element
    791842                std::list<Designation *> newDesignations;
    792843                for ( auto p : group_iterate(listInit->get_designations(), listInit->get_initializers()) ) {
    793                         // iterate designations and initializers in pairs, moving the cursor to the current designated object and resolving
    794                         // the initializer against that object.
     844                        // iterate designations and initializers in pairs, moving the cursor to the current
     845                        // designated object and resolving the initializer against that object.
    795846                        Designation * des = std::get<0>(p);
    796847                        Initializer * init = std::get<1>(p);
    … …  
    822873                // fall back on C-style initializer
    823874                delete ctorInit->get_ctor();
    824                 ctorInit->set_ctor( NULL );
     875                ctorInit->set_ctor( nullptr );
    825876                delete ctorInit->get_dtor();
    826                 ctorInit->set_dtor( NULL );
     877                ctorInit->set_dtor( nullptr );
    827878                maybeAccept( ctorInit->get_init(), *visitor );
    828879        }
    … …  
    867918
    868919                // xxx - todo -- what about arrays?
    869                 // if ( dtor == NULL && InitTweak::isIntrinsicCallStmt( ctorInit->get_ctor() ) ) {
     920                // if ( dtor == nullptr && InitTweak::isIntrinsicCallStmt( ctorInit->get_ctor() ) ) {
    870921                //      // can reduce the constructor down to a SingleInit using the
    871922                //      // second argument from the ctor call, since
    872923                //      delete ctorInit->get_ctor();
    873                 //      ctorInit->set_ctor( NULL );
     924                //      ctorInit->set_ctor( nullptr );
    874925
    875926                //      Expression * arg =

  • src/ResolvExpr/TypeEnvironment.cc

    r9b086ca rcde3891  
    120120
    121121        const EqvClass* TypeEnvironment::lookup( const std::string &var ) const {
    122                 for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) {
     122                for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
    123123                        if ( i->vars.find( var ) != i->vars.end() ) return &*i;
    124124                } // for
    … …  
    168168
    169169        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
    170                 for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
     170                for ( ClassList::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
    171171                        for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) {
    172172                                if ( theClass->type ) {
    … …  
    188188        }
    189189
    190         std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
    191                 for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) {
     190        TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
     191                for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
    192192                        if ( i->vars.count( var ) ) return i;
    193193                } // for
    … …  
    199199        }
    200200
     201        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
     202        bool TypeEnvironment::mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     203                if ( from.type ) {
     204                        if ( to.type ) {
     205                                // attempt to unify bound types
     206                                std::unique_ptr<Type> toType{ to.type->clone() }, fromType{ from.type->clone() };
     207                                WidenMode widenMode{ to.allowWidening, from.allowWidening };
     208                                Type* common = nullptr;
     209                                AssertionSet need, have;
     210                                if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widenMode, indexer, common ) ) {
     211                                        // unifies, set common type if necessary
     212                                        if ( common ) {
     213                                                common->get_qualifiers() = Type::Qualifiers{};
     214                                                to.set_type( common );
     215                                        }
     216                                } else return false; // cannot unify
     217                        } else {
     218                                to.type = from.type->clone();
     219                        }
     220                }
     221
     222                // unify widening if matches
     223                to.allowWidening &= from.allowWidening;
     224                return true;
     225        }
     226
     227        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
     228        bool TypeEnvironment::mergeClasses( TypeEnvironment::ClassList::iterator to, TypeEnvironment::ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     229                EqvClass& r = *to;
     230                EqvClass& s = *from;
     231
     232                // ensure bounds match
     233                if ( ! mergeBound( r, s, openVars, indexer ) ) return false;
     234
     235                // check safely bindable
     236                if ( r.type && occursIn( r.type, s.vars.begin(), s.vars.end(), *this ) ) return false;
     237               
     238                // merge classes in
     239                r.vars.insert( s.vars.begin(), s.vars.end() );
     240                r.allowWidening &= s.allowWidening;
     241                env.erase( from );
     242
     243                return true;
     244        }
     245
     246        bool TypeEnvironment::combine( const TypeEnvironment& o, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     247                // short-circuit easy cases
     248                if ( o.isEmpty() ) return true;
     249                if ( isEmpty() ) {
     250                        simpleCombine( o );
     251                        return true;
     252                }
     253
     254                // merge classes
     255                for ( auto ct = o.env.begin(); ct != o.env.end(); ++ct ) {
     256                        const EqvClass& c = *ct;
     257
     258                        // typeclass in local environment bound to c
     259                        auto rt = env.end();
     260
     261                        // look for first existing bound variable
     262                        auto vt = c.vars.begin();
     263                        for ( ; vt != c.vars.end(); ++vt ) {
     264                                rt = internal_lookup( *vt );
     265                                if ( rt != env.end() ) break;
     266                        }
     267
     268                        if ( rt != env.end() ) {  // c needs to be merged into *rt
     269                                EqvClass& r = *rt;
     270                                // merge bindings
     271                                if ( ! mergeBound( r, c, openVars, indexer ) ) return false;
     272                                // merge previous unbound variables into this class, checking occurs if needed
     273                                if ( r.type ) for ( auto ut = c.vars.begin(); ut != vt; ++ut ) {
     274                                        if ( occurs( r.type, *ut, *this ) ) return false;
     275                                        r.vars.insert( *ut );
     276                                } else { r.vars.insert( c.vars.begin(), vt ); }
     277                                // merge subsequent variables into this class (skipping *vt, already there)
     278                                while ( ++vt != c.vars.end() ) {
     279                                        auto st = internal_lookup( *vt );
     280                                        if ( st == env.end() ) {
     281                                                // unbound, safe to add if passes occurs
     282                                                if ( r.type && occurs( r.type, *vt, *this ) ) return false;
     283                                                r.vars.insert( *vt );
     284                                        } else if ( st != rt ) {
     285                                                // bound, but not to the same class
     286                                                if ( ! mergeClasses( rt, st, openVars, indexer ) ) return false;
     287                                        }   // ignore bound into the same class
     288                                }
     289                        } else {  // no variables in c bound; just copy up
     290                                env.push_back( c );
     291                        }
     292                }
     293
     294                // merged all classes
     295                return true;
     296        }
     297
    201298        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
    202                 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
     299                for ( ClassList::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
    203300                        for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) {
    204301                                openVars[ *var ] = eqvClass->data;

  • src/ResolvExpr/TypeEnvironment.h

    r9b086ca rcde3891  
    3939        // declarations.
    4040        //
    41         // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
     41        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
     42        // comparator.
    4243        //
    4344        // Note: since this compares pointers for position, minor changes in the source file that affect
    4445        // memory layout can alter compilation time in unpredictable ways. For example, the placement
    4546        // of a line directive can reorder type pointers with respect to each other so that assertions
    46         // are seen in different orders, causing a potentially different number of unification calls when
    47         // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
    48         // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
    49         // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
    50         // this causes some assertions to never be recorded. More investigation is needed.
     47        // are seen in different orders, causing a potentially different number of unification calls
     48        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
     49        // line directives alone, so it would be nice to fix this comparison so that assertions compare
     50        // more consistently. I've tried to modify this to compare on mangle name instead of type as
     51        // the second comparator, but this causes some assertions to never be recorded. More
     52        // investigation is needed.
    5153        struct AssertCompare {
    5254                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
    … …  
    5759        };
    5860        struct AssertionSetValue {
    59                 bool isUsed;
    60                 // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
    61                 // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
    62                 // the ID of the assertion that pulled in the current assertion.
    63                 std::list< UniqueId > idChain;
     61                bool isUsed;        ///< True if assertion needs to be resolved
     62                UniqueId resnSlot;  ///< ID of slot assertion belongs to
     63
     64                AssertionSetValue() : isUsed(false), resnSlot(0) {}
    6465        };
    6566        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
    6667        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
     68
     69        /// merges one set of open vars into another
     70        static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
     71                for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
     72        }
    6773
    6874        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
    … …  
    9197
    9298        class TypeEnvironment {
     99                using ClassList = std::list< EqvClass >;
    93100          public:
    94101                const EqvClass* lookup( const std::string &var ) const;
    … …  
    103110                bool isEmpty() const { return env.empty(); }
    104111                void print( std::ostream &os, Indenter indent = {} ) const;
    105                 // void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
     112               
     113                /// Simply concatenate the second environment onto this one; no safety checks performed
    106114                void simpleCombine( const TypeEnvironment &second );
     115
     116          private:
     117                /// Unifies the type bound of to with the type bound of from, returning false if fails
     118                bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     119
     120                /// Merges two type classes from local environment, returning false if fails
     121                bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     122
     123          public:
     124                /// Merges the second environment with this one, checking compatibility.
     125                /// Returns false if fails, but does NOT roll back partial changes.
     126                bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     127               
    107128                void extractOpenVars( OpenVarSet &openVars ) const;
    108129                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
    … …  
    123144                void forbidWidening();
    124145
    125                 using iterator = std::list< EqvClass >::const_iterator;
     146                using iterator = ClassList::const_iterator;
    126147                iterator begin() const { return env.begin(); }
    127148                iterator end() const { return env.end(); }
    128149
    129150          private:
    130                 std::list< EqvClass > env;
     151                ClassList env;
    131152               
    132                 std::list< EqvClass >::iterator internal_lookup( const std::string &var );
     153                ClassList::iterator internal_lookup( const std::string &var );
    133154        };
    134155

  • src/ResolvExpr/module.mk

    r9b086ca rcde3891  
    3333       ResolvExpr/TypeEnvironment.cc \
    3434       ResolvExpr/CurrentObject.cc \
    35        ResolvExpr/ExplodedActual.cc
     35       ResolvExpr/ExplodedActual.cc \
     36       ResolvExpr/SpecCost.cc \
     37       ResolvExpr/ResolveAssertions.cc

  • src/ResolvExpr/typeops.h

    r9b086ca rcde3891  
    7272        Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env );
    7373
     74        // in AlternativeFinder.cc
     75        Cost computeConversionCost( Type *actualType, Type *formalType,
     76                const SymTab::Indexer &indexer, const TypeEnvironment &env );
     77
    7478        // in PtrsAssignable.cc
    7579        int ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env );
    … …  
    102106        int polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer );
    103107
     108        // in SpecCost.cc
     109        int specCost( Type *type );
     110
    104111        // in Occurs.cc
    105112        bool occurs( Type *type, std::string varName, const TypeEnvironment &env );
     113
     114        template<typename Iter>
     115        bool occursIn( Type* ty, Iter begin, Iter end, const TypeEnvironment &env ) {
     116                while ( begin != end ) {
     117                        if ( occurs( ty, *begin, env ) ) return true;
     118                        ++begin;
     119                }
     120                return false;
     121        }
    106122
    107123        // in AlternativeFinder.cc
Note: See TracChangeset for help on using the changeset viewer.