Changes in / [9f10d1f2:88ef2af]


Ignore:
Location:
src
Files:
2 added
13 edited

Legend:

Unmodified
Added
Removed

  • src/Makefile.in

    r9f10d1f2 r88ef2af  
    210210        ResolvExpr/driver_cfa_cpp-TypeEnvironment.$(OBJEXT) \
    211211        ResolvExpr/driver_cfa_cpp-CurrentObject.$(OBJEXT) \
     212        ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT) \
    212213        SymTab/driver_cfa_cpp-Indexer.$(OBJEXT) \
    213214        SymTab/driver_cfa_cpp-Mangler.$(OBJEXT) \
    … …  
    511512        ResolvExpr/FindOpenVars.cc ResolvExpr/PolyCost.cc \
    512513        ResolvExpr/Occurs.cc ResolvExpr/TypeEnvironment.cc \
    513         ResolvExpr/CurrentObject.cc SymTab/Indexer.cc \
    514         SymTab/Mangler.cc SymTab/Validate.cc SymTab/FixFunction.cc \
    515         SymTab/ImplementationType.cc SymTab/TypeEquality.cc \
    516         SymTab/Autogen.cc SynTree/Type.cc SynTree/VoidType.cc \
    517         SynTree/BasicType.cc SynTree/PointerType.cc \
    518         SynTree/ArrayType.cc SynTree/ReferenceType.cc \
    519         SynTree/FunctionType.cc SynTree/ReferenceToType.cc \
    520         SynTree/TupleType.cc SynTree/TypeofType.cc SynTree/AttrType.cc \
     514        ResolvExpr/CurrentObject.cc ResolvExpr/ExplodedActual.cc \
     515        SymTab/Indexer.cc SymTab/Mangler.cc SymTab/Validate.cc \
     516        SymTab/FixFunction.cc SymTab/ImplementationType.cc \
     517        SymTab/TypeEquality.cc SymTab/Autogen.cc SynTree/Type.cc \
     518        SynTree/VoidType.cc SynTree/BasicType.cc \
     519        SynTree/PointerType.cc SynTree/ArrayType.cc \
     520        SynTree/ReferenceType.cc SynTree/FunctionType.cc \
     521        SynTree/ReferenceToType.cc SynTree/TupleType.cc \
     522        SynTree/TypeofType.cc SynTree/AttrType.cc \
    521523        SynTree/VarArgsType.cc SynTree/ZeroOneType.cc \
    522524        SynTree/Constant.cc SynTree/Expression.cc SynTree/TupleExpr.cc \
    … …  
    825827        ResolvExpr/$(am__dirstamp) \
    826828        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
     829ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT):  \
     830        ResolvExpr/$(am__dirstamp) \
     831        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
    827832SymTab/$(am__dirstamp):
    828833        @$(MKDIR_P) SymTab
    … …  
    10221027@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ConversionCost.Po@am__quote@
    10231028@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-CurrentObject.Po@am__quote@
     1029@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po@am__quote@
    10241030@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-FindOpenVars.Po@am__quote@
    10251031@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-Occurs.Po@am__quote@
    … …  
    19641970@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-CurrentObject.obj `if test -f 'ResolvExpr/CurrentObject.cc'; then $(CYGPATH_W) 'ResolvExpr/CurrentObject.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/CurrentObject.cc'; fi`
    19651971
     1972ResolvExpr/driver_cfa_cpp-ExplodedActual.o: ResolvExpr/ExplodedActual.cc
     1973@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.o -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc
     1974@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po
     1975@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.o' libtool=no @AMDEPBACKSLASH@
     1976@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1977@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc
     1978
     1979ResolvExpr/driver_cfa_cpp-ExplodedActual.obj: ResolvExpr/ExplodedActual.cc
     1980@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.obj -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi`
     1981@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po
     1982@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.obj' libtool=no @AMDEPBACKSLASH@
     1983@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1984@am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi`
     1985
    19661986SymTab/driver_cfa_cpp-Indexer.o: SymTab/Indexer.cc
    19671987@am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT SymTab/driver_cfa_cpp-Indexer.o -MD -MP -MF SymTab/$(DEPDIR)/driver_cfa_cpp-Indexer.Tpo -c -o SymTab/driver_cfa_cpp-Indexer.o `test -f 'SymTab/Indexer.cc' || echo '$(srcdir)/'`SymTab/Indexer.cc

  • src/Parser/DeclarationNode.cc

    r9f10d1f2 r88ef2af  
    1010// Created On       : Sat May 16 12:34:05 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Sep 23 18:16:48 2017
    13 // Update Count     : 1024
     12// Last Modified On : Mon Nov 20 09:21:52 2017
     13// Update Count     : 1031
    1414//
    1515
    … …  
    509509
    510510DeclarationNode * DeclarationNode::addQualifiers( DeclarationNode * q ) {
    511         if ( ! q ) { delete q; return this; }
     511        if ( ! q ) { delete q; return this; }                           // empty qualifier
    512512
    513513        checkSpecifiers( q );
    514514        copySpecifiers( q );
    515515
    516         if ( ! q->type ) {
    517                 delete q;
    518                 return this;
    519         } // if
     516        if ( ! q->type ) { delete q; return this; }
    520517
    521518        if ( ! type ) {
    522                 type = q->type;                                                                 // reuse this structure
     519                type = q->type;                                                                 // reuse structure
    523520                q->type = nullptr;
    524521                delete q;
    … …  
    526523        } // if
    527524
    528         if ( q->type->forall ) {
    529                 if ( type->forall ) {
    530                         type->forall->appendList( q->type->forall );
     525        if ( q->type->forall ) {                                                        // forall qualifier ?
     526                if ( type->forall ) {                                                   // polymorphic routine ?
     527                        type->forall->appendList( q->type->forall ); // augment forall qualifier
    531528                } else {
    532                         if ( type->kind == TypeData::Aggregate ) {
    533                                 type->aggregate.params = q->type->forall;
    534                                 // change implicit typedef from TYPEDEFname to TYPEGENname
    535                                 typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG );
    536                         } else {
    537                                 type->forall = q->type->forall;
     529                        if ( type->kind == TypeData::Aggregate ) {      // struct/union ?
     530                                if ( type->aggregate.params ) {                 // polymorphic ?
     531                                        type->aggregate.params->appendList( q->type->forall ); // augment forall qualifier
     532                                } else {                                                                // not polymorphic
     533                                        type->aggregate.params = q->type->forall; // make polymorphic type
     534                                        // change implicit typedef from TYPEDEFname to TYPEGENname
     535                                        typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG );
     536                                } // if
     537                        } else {                                                                        // not polymorphic
     538                                type->forall = q->type->forall;                 // make polymorphic routine
    538539                        } // if
    539540                } // if
    540                 q->type->forall = nullptr;
     541                q->type->forall = nullptr;                                              // forall qualifier moved
    541542        } // if
    542543

  • src/Parser/parser.yy

    r9f10d1f2 r88ef2af  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Oct 25 12:28:54 2017
    13 // Update Count     : 2893
     12// Last Modified On : Mon Nov 20 09:45:36 2017
     13// Update Count     : 2945
    1414//
    1515
    … …  
    114114        } // for
    115115} // distExt
     116
     117// There is an ambiguity for inline generic-routine return-types and generic routines.
     118//   forall( otype T ) struct S { int i; } bar( T ) {}
     119// Does the forall bind to the struct or the routine, and how would it be possible to explicitly specify the binding.
     120//   forall( otype T ) struct S { int T; } forall( otype W ) bar( W ) {}
     121
     122void rebindForall( DeclarationNode * declSpec, DeclarationNode * funcDecl ) {
     123        if ( declSpec->type->kind == TypeData::Aggregate ) { // return is aggregate definition
     124                funcDecl->type->forall = declSpec->type->aggregate.params; // move forall from aggregate to function type
     125                declSpec->type->aggregate.params = nullptr;
     126        } // if
     127} // rebindForall
    116128
    117129bool forall = false;                                                                    // aggregate have one or more forall qualifiers ?
    … …  
    348360
    349361
    350 // Handle single shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string
    351 // is ambiguous:
    352 // .---------.                          matches IF '(' comma_expression ')' statement . (reduce)
    353 // if ( C ) S1 else S2
    354 // `-----------------'          matches IF '(' comma_expression ')' statement . (shift) ELSE statement */
     362// Handle shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string is ambiguous:
     363//   .---------.                                matches IF '(' comma_expression ')' statement . (reduce)
     364//   if ( C ) S1 else S2
     365//   `-----------------'                matches IF '(' comma_expression ')' statement . (shift) ELSE statement */
    355366// Similar issues exit with the waitfor statement.
    356367
    … …  
    361372%precedence TIMEOUT     // token precedence for start of TIMEOUT in WAITFOR statement
    362373%precedence ELSE        // token precedence for start of else clause in IF/WAITFOR statement
     374
     375// Handle shift/reduce conflict for generic type by shifting the '(' token. For example, this string is ambiguous:
     376//   forall( otype T ) struct Foo { T v; };
     377//       .-----.                                matches pointer to function returning a generic (which is impossible without a type)
     378//   Foo ( *fp )( int );
     379//   `---'                                              matches start of TYPEGENname '('
     380// Must be:
     381// Foo( int ) ( *fp )( int );
     382
     383// Order of these lines matters (low-to-high precedence).
     384%precedence TYPEGENname
     385%precedence '('
    363386
    364387%locations                      // support location tracking for error messages
    … …  
    17651788
    17661789typegen_name:                                                                                   // CFA
    1767         TYPEGENname '(' ')'
     1790        TYPEGENname
     1791                { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); }
     1792        | TYPEGENname '(' ')'
    17681793                { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); }
    17691794        | TYPEGENname '(' type_list ')'
    … …  
    18091834                }
    18101835        | aggregate_key attribute_list_opt typegen_name         // CFA
    1811                 { $$ = $3->addQualifiers( $2 ); }
     1836                {
     1837                        // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is
     1838                        // switched to a TYPEGENname. Link any generic arguments from typegen_name to new generic declaration and
     1839                        // delete newFromTypeGen.
     1840                        $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $3->type->symbolic.actuals, nullptr, false )->addQualifiers( $2 );
     1841                        $3->type->symbolic.name = nullptr;
     1842                        $3->type->symbolic.actuals = nullptr;
     1843                        delete $3;
     1844                }
    18121845        ;
    18131846
    … …  
    23802413        | declaration_specifier function_declarator with_clause_opt compound_statement
    23812414                {
     2415                        rebindForall( $1, $2 );
    23822416                        typedefTable.addToEnclosingScope( TypedefTable::ID );
    23832417                        typedefTable.leaveScope();
    … …  
    24062440        | declaration_specifier KR_function_declarator KR_declaration_list_opt with_clause_opt compound_statement
    24072441                {
     2442                        rebindForall( $1, $2 );
    24082443                        typedefTable.addToEnclosingScope( TypedefTable::ID );
    24092444                        typedefTable.leaveScope();

  • src/ResolvExpr/Alternative.cc

    r9f10d1f2 r88ef2af  
    1818#include <ostream>                       // for operator<<, ostream, basic_o...
    1919#include <string>                        // for operator<<, char_traits, string
     20#include <utility>                       // for move
    2021
    2122#include "Common/utility.h"              // for maybeClone
    … …  
    8182                os << std::endl;
    8283        }
     84
     85        void splice( AltList& dst, AltList& src ) {
     86                dst.reserve( dst.size() + src.size() );
     87                for ( Alternative& alt : src ) {
     88                        dst.push_back( std::move(alt) );
     89                }
     90                src.clear();
     91        }
     92
     93        void spliceBegin( AltList& dst, AltList& src ) {
     94                splice( src, dst );
     95                dst.swap( src );
     96        }
     97
    8398} // namespace ResolvExpr
    8499

  • src/ResolvExpr/Alternative.h

    r9f10d1f2 r88ef2af  
    1717
    1818#include <iosfwd>             // for ostream
    19 #include <list>               // for list
     19#include <vector>             // for vector
    2020
    2121#include "Cost.h"             // for Cost
    … …  
    2525
    2626namespace ResolvExpr {
    27         struct Alternative;
    28 
    29         typedef std::list< Alternative > AltList;
    30 
    3127        struct Alternative {
    3228                Alternative();
    … …  
    4642                TypeEnvironment env;
    4743        };
     44
     45        typedef std::vector< Alternative > AltList;
     46
     47        /// Moves all elements from src to the end of dst
     48        void splice( AltList& dst, AltList& src );
     49
     50        /// Moves all elements from src to the beginning of dst
     51        void spliceBegin( AltList& dst, AltList& src );
    4852} // namespace ResolvExpr
    4953

  • src/ResolvExpr/AlternativeFinder.cc

    r9f10d1f2 r88ef2af  
    1616#include <algorithm>               // for copy
    1717#include <cassert>                 // for strict_dynamic_cast, assert, assertf
     18#include <cstddef>                 // for size_t
    1819#include <iostream>                // for operator<<, cerr, ostream, endl
    1920#include <iterator>                // for back_insert_iterator, back_inserter
    2021#include <list>                    // for _List_iterator, list, _List_const_...
    2122#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
    22 #include <memory>                  // for allocator_traits<>::value_type
     23#include <memory>                  // for allocator_traits<>::value_type, unique_ptr
    2324#include <utility>                 // for pair
    2425#include <vector>                  // for vector
    … …  
    2930#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
    3031#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
     32#include "ExplodedActual.h"        // for ExplodedActual
    3133#include "InitTweak/InitTweak.h"   // for getFunctionName
    3234#include "RenameVars.h"            // for RenameVars, global_renamer
    … …  
    5052#define PRINT( text ) if ( resolvep ) { text }
    5153//#define DEBUG_COST
     54
     55using std::move;
     56
     57/// copies any copyable type
     58template<typename T>
     59T copy(const T& x) { return x; }
    5260
    5361namespace ResolvExpr {
    … …  
    187195                                printAlts( alternatives, std::cerr );
    188196                        )
    189                         AltList::iterator oldBegin = alternatives.begin();
    190                         pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
    191                         if ( failFast && alternatives.begin() == oldBegin ) {
     197                        AltList pruned;
     198                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
     199                        if ( failFast && pruned.empty() ) {
    192200                                std::ostringstream stream;
    193201                                AltList winners;
    … …  
    199207                                throw SemanticError( stream.str() );
    200208                        }
    201                         alternatives.erase( oldBegin, alternatives.end() );
     209                        alternatives = move(pruned);
    202210                        PRINT(
    203211                                std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
    … …  
    571579        /// State to iteratively build a match of parameter expressions to arguments
    572580        struct ArgPack {
    573                 AltList actuals;                 ///< Arguments included in this pack
    574                 TypeEnvironment env;             ///< Environment for this pack
    575                 AssertionSet need;               ///< Assertions outstanding for this pack
    576                 AssertionSet have;               ///< Assertions found for this pack
    577                 OpenVarSet openVars;             ///< Open variables for this pack
    578                 unsigned nextArg;                ///< Index of next argument in arguments list
    579                 std::vector<Alternative> expls;  ///< Exploded actuals left over from last match
    580                 unsigned nextExpl;               ///< Index of next exploded alternative to use
    581                 std::vector<unsigned> tupleEls;  /// Number of elements in current tuple element(s)
    582 
    583                 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
     581                std::size_t parent;                ///< Index of parent pack
     582                std::unique_ptr<Expression> expr;  ///< The argument stored here
     583                Cost cost;                         ///< The cost of this argument
     584                TypeEnvironment env;               ///< Environment for this pack
     585                AssertionSet need;                 ///< Assertions outstanding for this pack
     586                AssertionSet have;                 ///< Assertions found for this pack
     587                OpenVarSet openVars;               ///< Open variables for this pack
     588                unsigned nextArg;                  ///< Index of next argument in arguments list
     589                unsigned tupleStart;               ///< Number of tuples that start at this index
     590                unsigned nextExpl;                 ///< Index of next exploded element
     591                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
     592               
     593                ArgPack()
     594                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
     595                          tupleStart(0), nextExpl(0), explAlt(0) {}
     596               
     597                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
    584598                                const OpenVarSet& openVars)
    585                         : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),
    586                           expls(), nextExpl(0), tupleEls() {}
    587 
    588                 /// Starts a new tuple expression
    589                 void beginTuple() {
    590                         if ( ! tupleEls.empty() ) ++tupleEls.back();
    591                         tupleEls.push_back(0);
    592                 }
    593 
     599                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
     600                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
     601               
     602                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
     603                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
     604                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
     605                                unsigned explAlt = 0 )
     606                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
     607                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
     608                          nextExpl(nextExpl), explAlt(explAlt) {}
     609               
     610                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
     611                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
     612                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
     613                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
     614                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
     615               
     616                /// true iff this pack is in the middle of an exploded argument
     617                bool hasExpl() const { return nextExpl > 0; }
     618
     619                /// Gets the list of exploded alternatives for this pack
     620                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
     621                        return args[nextArg-1][explAlt];
     622                }
     623                         
    594624                /// Ends a tuple expression, consolidating the appropriate actuals
    595                 void endTuple() {
    596                         // set up new Tuple alternative
     625                void endTuple( const std::vector<ArgPack>& packs ) {
     626                        // add all expressions in tuple to list, summing cost
    597627                        std::list<Expression*> exprs;
    598                         Cost cost = Cost::zero;
    599 
    600                         // transfer elements into alternative
    601                         for (unsigned i = 0; i < tupleEls.back(); ++i) {
    602                                 exprs.push_front( actuals.back().expr );
    603                                 actuals.back().expr = nullptr;
    604                                 cost += actuals.back().cost;
    605                                 actuals.pop_back();
    606                         }
    607                         tupleEls.pop_back();
    608 
    609                         // build new alternative
    610                         actuals.emplace_back( new TupleExpr( exprs ), this->env, cost );
    611                 }
    612 
    613                 /// Clones and adds an actual, returns this
    614                 ArgPack& withArg( Expression* expr, Cost cost = Cost::zero ) {
    615                         actuals.emplace_back( expr->clone(), this->env, cost );
    616                         if ( ! tupleEls.empty() ) ++tupleEls.back();
    617                         return *this;
     628                        const ArgPack* pack = this;
     629                        if ( expr ) { exprs.push_front( expr.release() ); }
     630                        while ( pack->tupleStart == 0 ) {
     631                                pack = &packs[pack->parent];
     632                                exprs.push_front( pack->expr->clone() );
     633                                cost += pack->cost;
     634                        }
     635                        // reset pack to appropriate tuple
     636                        expr.reset( new TupleExpr( exprs ) );
     637                        tupleStart = pack->tupleStart - 1;
     638                        parent = pack->parent;
    618639                }
    619640        };
    620641
    621642        /// Instantiates an argument to match a formal, returns false if no results left
    622         bool instantiateArgument( Type* formalType, Initializer* initializer,
    623                         const std::vector< AlternativeFinder >& args,
    624                         std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults,
    625                         const SymTab::Indexer& indexer ) {
     643        bool instantiateArgument( Type* formalType, Initializer* initializer,
     644                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
     645                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
    626646                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
    627647                        // formalType is a TupleType - group actuals into a TupleExpr
    628                         for ( ArgPack& result : results ) { result.beginTuple(); }
     648                        ++nTuples;
    629649                        for ( Type* type : *tupleType ) {
    630650                                // xxx - dropping initializer changes behaviour from previous, but seems correct
    631                                 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) )
     651                                if ( ! instantiateArgument(
     652                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
    632653                                        return false;
    633                         }
    634                         for ( ArgPack& result : results ) { result.endTuple(); }
     654                                nTuples = 0;
     655                        }
     656                        // re-consititute tuples for final generation
     657                        for ( auto i = genStart; i < results.size(); ++i ) {
     658                                results[i].endTuple( results );
     659                        }
    635660                        return true;
    636661                } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
    637662                        // formalType is a ttype, consumes all remaining arguments
    638663                        // xxx - mixing default arguments with variadic??
    639                         std::vector<ArgPack> finalResults{};  /// list of completed tuples
    640                         // start tuples
    641                         for ( ArgPack& result : results ) {
    642                                 result.beginTuple();
    643 
    644                                 // use rest of exploded tuple if present
    645                                 while ( result.nextExpl < result.expls.size() ) {
    646                                         const Alternative& actual = result.expls[result.nextExpl];
    647                                         result.env.addActual( actual.env, result.openVars );
    648                                         result.withArg( actual.expr );
    649                                         ++result.nextExpl;
    650                                 }
    651                         }
     664
     665                        // completed tuples; will be spliced to end of results to finish
     666                        std::vector<ArgPack> finalResults{};
     667
    652668                        // iterate until all results completed
    653                         while ( ! results.empty() ) {
     669                        std::size_t genEnd;
     670                        ++nTuples;
     671                        do {
     672                                genEnd = results.size();
     673
    654674                                // add another argument to results
    655                                 for ( ArgPack& result : results ) {
    656                                         // finish result when out of arguments
    657                                         if ( result.nextArg >= args.size() ) {
    658                                                 Type* argType = result.actuals.back().expr->get_result();
    659                                                 if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) {
    660                                                         // the case where a ttype value is passed directly is special, e.g. for
    661                                                         // argument forwarding purposes
    662                                                         // xxx - what if passing multiple arguments, last of which is ttype?
    663                                                         // xxx - what would happen if unify was changed so that unifying tuple
    664                                                         // types flattened both before unifying lists? then pass in TupleType
    665                                                         // (ttype) below.
    666                                                         result.tupleEls.pop_back();
    667                                                 } else {
    668                                                         // collapse leftover arguments into tuple
    669                                                         result.endTuple();
    670                                                         argType = result.actuals.back().expr->get_result();
     675                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     676                                        auto nextArg = results[i].nextArg;
     677
     678                                        // use remainder of exploded tuple if present
     679                                        if ( results[i].hasExpl() ) {
     680                                                const ExplodedActual& expl = results[i].getExpl( args );
     681                                                const Alternative& actual = expl.alts[results[i].nextExpl];
     682                                               
     683                                                TypeEnvironment env = results[i].env;
     684                                                OpenVarSet openVars = results[i].openVars;
     685
     686                                                env.addActual( actual.env, openVars );
     687
     688                                                unsigned nextExpl = results[i].nextExpl + 1;
     689                                                if ( nextExpl == expl.alts.size() ) {
     690                                                        nextExpl = 0;
    671691                                                }
    672                                                 // check unification for ttype before adding to final
    673                                                 if ( unify( ttype, argType, result.env, result.need, result.have,
    674                                                                 result.openVars, indexer ) ) {
    675                                                         finalResults.push_back( std::move(result) );
    676                                                 }
     692
     693                                                results.emplace_back(
     694                                                        i, actual.expr, move(env), copy(results[i].need),
     695                                                        copy(results[i].have), move(openVars), nextArg, nTuples,
     696                                                        Cost::zero, nextExpl, results[i].explAlt );
     697                                               
    677698                                                continue;
    678699                                        }
     700                                       
     701                                        // finish result when out of arguments
     702                                        if ( nextArg >= args.size() ) {
     703                                                ArgPack newResult{
     704                                                        results[i].env, results[i].need, results[i].have,
     705                                                        results[i].openVars };
     706                                                newResult.nextArg = nextArg;
     707                                                Type* argType;
     708
     709                                                if ( nTuples > 0 ) {
     710                                                        // first iteration, push empty tuple expression
     711                                                        newResult.parent = i;
     712                                                        std::list<Expression*> emptyList;
     713                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
     714                                                        argType = newResult.expr->get_result();
     715                                                } else {
     716                                                        // clone result to collect tuple
     717                                                        newResult.parent = results[i].parent;
     718                                                        newResult.cost = results[i].cost;
     719                                                        newResult.tupleStart = results[i].tupleStart;
     720                                                        newResult.expr.reset( results[i].expr->clone() );
     721                                                        argType = newResult.expr->get_result();
     722
     723                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
     724                                                                // the case where a ttype value is passed directly is special,
     725                                                                // e.g. for argument forwarding purposes
     726                                                                // xxx - what if passing multiple arguments, last of which is
     727                                                                //       ttype?
     728                                                                // xxx - what would happen if unify was changed so that unifying
     729                                                                //       tuple
     730                                                                // types flattened both before unifying lists? then pass in
     731                                                                // TupleType (ttype) below.
     732                                                                --newResult.tupleStart;
     733                                                        } else {
     734                                                                // collapse leftover arguments into tuple
     735                                                                newResult.endTuple( results );
     736                                                                argType = newResult.expr->get_result();
     737                                                        }
     738                                                }
     739
     740                                                // check unification for ttype before adding to final
     741                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
     742                                                                newResult.openVars, indexer ) ) {
     743                                                        finalResults.push_back( move(newResult) );
     744                                                }
     745                                               
     746                                                continue;
     747                                        }
    679748
    680749                                        // add each possible next argument
    681                                         for ( const Alternative& actual : args[result.nextArg] ) {
    682                                                 ArgPack aResult = result;  // copy to clone everything
    683                                                 // add details of actual to result
    684                                                 aResult.env.addActual( actual.env, aResult.openVars );
    685                                                 Cost cost = actual.cost;
    686 
    687                                                 // explode argument
    688                                                 std::vector<Alternative> exploded;
    689                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    690 
    691                                                 // add exploded argument to tuple
    692                                                 for ( Alternative& aActual : exploded ) {
    693                                                         aResult.withArg( aActual.expr, cost );
    694                                                         cost = Cost::zero;
     750                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     751                                                const ExplodedActual& expl = args[nextArg][j];
     752                                       
     753                                                // fresh copies of parent parameters for this iteration
     754                                                TypeEnvironment env = results[i].env;
     755                                                OpenVarSet openVars = results[i].openVars;
     756
     757                                                env.addActual( expl.env, openVars );
     758
     759                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     760                                                if ( expl.alts.empty() ) {
     761                                                        results.emplace_back(
     762                                                                results[i], move(env), copy(results[i].need),
     763                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
     764                                                       
     765                                                        continue;
    695766                                                }
    696                                                 ++aResult.nextArg;
    697                                                 nextResults.push_back( std::move(aResult) );
     767
     768                                                // add new result
     769                                                results.emplace_back(
     770                                                        i, expl.alts.front().expr, move(env), copy(results[i].need),
     771                                                        copy(results[i].have), move(openVars), nextArg + 1,
     772                                                        nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
    698773                                        }
    699774                                }
    700775
    701776                                // reset for next round
    702                                 results.swap( nextResults );
    703                                 nextResults.clear();
    704                         }
    705                         results.swap( finalResults );
    706                         return ! results.empty();
     777                                genStart = genEnd;
     778                                nTuples = 0;
     779                        } while ( genEnd != results.size() );
     780
     781                        // splice final results onto results
     782                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
     783                                results.push_back( move(finalResults[i]) );
     784                        }
     785                        return ! finalResults.empty();
    707786                }
    708787
    709788                // iterate each current subresult
    710                 for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) {
    711                         ArgPack& result = results[iResult];
    712 
    713                         if ( result.nextExpl < result.expls.size() ) {
    714                                 // use remainder of exploded tuple if present
    715                                 const Alternative& actual = result.expls[result.nextExpl];
    716                                 result.env.addActual( actual.env, result.openVars );
     789                std::size_t genEnd = results.size();
     790                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     791                        auto nextArg = results[i].nextArg;
     792
     793                        // use remainder of exploded tuple if present
     794                        if ( results[i].hasExpl() ) {
     795                                const ExplodedActual& expl = results[i].getExpl( args );
     796                                const Alternative& actual = expl.alts[results[i].nextExpl];
     797                               
     798                                TypeEnvironment env = results[i].env;
     799                                AssertionSet need = results[i].need, have = results[i].have;
     800                                OpenVarSet openVars = results[i].openVars;
     801
     802                                env.addActual( actual.env, openVars );
    717803                                Type* actualType = actual.expr->get_result();
    718804
    … …  
    724810                                        std::cerr << std::endl;
    725811                                )
    726 
    727                                 if ( unify( formalType, actualType, result.env, result.need, result.have,
    728                                                 result.openVars, indexer ) ) {
    729                                         ++result.nextExpl;
    730                                         nextResults.push_back( std::move(result.withArg( actual.expr )) );
     812                               
     813                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     814                                        unsigned nextExpl = results[i].nextExpl + 1;
     815                                        if ( nextExpl == expl.alts.size() ) {
     816                                                nextExpl = 0;
     817                                        }
     818                                       
     819                                        results.emplace_back(
     820                                                i, actual.expr, move(env), move(need), move(have), move(openVars),
     821                                                nextArg, nTuples, Cost::zero, nextExpl, results[i].explAlt );
    731822                                }
    732823
    733824                                continue;
    734                         } else if ( result.nextArg >= args.size() ) {
    735                                 // use default initializers if out of arguments
     825                        }
     826                       
     827                        // use default initializers if out of arguments
     828                        if ( nextArg >= args.size() ) {
    736829                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
    737830                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
    738                                                 if ( unify( formalType, cnst->get_type(), result.env, result.need,
    739                                                                 result.have, result.openVars, indexer ) ) {
    740                                                         nextResults.push_back( std::move(result.withArg( cnstExpr )) );
     831                                                TypeEnvironment env = results[i].env;
     832                                                AssertionSet need = results[i].need, have = results[i].have;
     833                                                OpenVarSet openVars = results[i].openVars;
     834
     835                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
     836                                                                indexer ) ) {
     837                                                        results.emplace_back(
     838                                                                i, cnstExpr, move(env), move(need), move(have),
     839                                                                move(openVars), nextArg, nTuples );
    741840                                                }
    742841                                        }
    743842                                }
     843
    744844                                continue;
    745845                        }
    746846
    747847                        // Check each possible next argument
    748                         for ( const Alternative& actual : args[result.nextArg] ) {
    749                                 ArgPack aResult = result;  // copy to clone everything
    750                                 // add details of actual to result
    751                                 aResult.env.addActual( actual.env, aResult.openVars );
    752 
    753                                 // explode argument
    754                                 std::vector<Alternative> exploded;
    755                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    756                                 if ( exploded.empty() ) {
    757                                         // skip empty tuple arguments
    758                                         ++aResult.nextArg;
    759                                         results.push_back( std::move(aResult) );
     848                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     849                                const ExplodedActual& expl = args[nextArg][j];
     850
     851                                // fresh copies of parent parameters for this iteration
     852                                TypeEnvironment env = results[i].env;
     853                                AssertionSet need = results[i].need, have = results[i].have;
     854                                OpenVarSet openVars = results[i].openVars;
     855
     856                                env.addActual( expl.env, openVars );
     857                               
     858                                // skip empty tuple arguments by (near-)cloning parent into next gen
     859                                if ( expl.alts.empty() ) {
     860                                        results.emplace_back(
     861                                                results[i], move(env), move(need), move(have), move(openVars),
     862                                                nextArg + 1, expl.cost );
     863
    760864                                        continue;
    761865                                }
    762866
    763867                                // consider only first exploded actual
    764                                 const Alternative& aActual = exploded.front();
    765                                 Type* actualType = aActual.expr->get_result()->clone();
     868                                const Alternative& actual = expl.alts.front();
     869                                Type* actualType = actual.expr->get_result()->clone();
    766870
    767871                                PRINT(
    … …  
    774878
    775879                                // attempt to unify types
    776                                 if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) {
    777                                         // add argument
    778                                         aResult.withArg( aActual.expr, actual.cost );
    779                                         ++aResult.nextArg;
    780                                         if ( exploded.size() > 1 ) {
    781                                                 // other parts of tuple left over
    782                                                 aResult.expls = std::move( exploded );
    783                                                 aResult.nextExpl = 1;
    784                                         }
    785                                         nextResults.push_back( std::move(aResult) );
     880                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     881                                        // add new result
     882                                        results.emplace_back(
     883                                                i, actual.expr, move(env), move(need), move(have), move(openVars),
     884                                                nextArg + 1, nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
    786885                                }
    787886                        }
    … …  
    789888
    790889                // reset for next parameter
    791                 results.swap( nextResults );
    792                 nextResults.clear();
    793 
    794                 return ! results.empty();
     890                genStart = genEnd;
     891               
     892                return genEnd != results.size();
     893        }
     894
     895        template<typename OutputIterator>
     896        void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
     897                        const std::vector<ArgPack>& results, OutputIterator out ) {
     898                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
     899                // sum cost and accumulate actuals
     900                std::list<Expression*>& args = appExpr->get_args();
     901                Cost cost = Cost::zero;
     902                const ArgPack* pack = &result;
     903                while ( pack->expr ) {
     904                        args.push_front( pack->expr->clone() );
     905                        cost += pack->cost;
     906                        pack = &results[pack->parent];
     907                }
     908                // build and validate new alternative
     909                Alternative newAlt( appExpr, result.env, cost );
     910                PRINT(
     911                        std::cerr << "instantiate function success: " << appExpr << std::endl;
     912                        std::cerr << "need assertions:" << std::endl;
     913                        printAssertionSet( result.need, std::cerr, 8 );
     914                )
     915                inferParameters( result.need, result.have, newAlt, result.openVars, out );
    795916        }
    796917
    797918        template<typename OutputIterator>
    798919        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
    799                         FunctionType *funcType, const std::vector< AlternativeFinder > &args,
    800                         OutputIterator out ) {
     920                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
    801921                OpenVarSet funcOpenVars;
    802922                AssertionSet funcNeed, funcHave;
    … …  
    818938
    819939                // iteratively build matches, one parameter at a time
    820                 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } };
    821                 std::vector<ArgPack> nextResults{};
     940                std::vector<ArgPack> results;
     941                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
     942                std::size_t genStart = 0;
     943
    822944                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
    823945                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
    824                         if ( ! instantiateArgument(
    825                                         obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )
     946                        if ( ! instantiateArgument( 
     947                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
    826948                                return;
    827949                }
    828950
    829                 // filter out results that don't use all the arguments, and aren't variadic
    830                 std::vector<ArgPack> finalResults{};
    831951                if ( funcType->get_isVarArgs() ) {
    832                         for ( ArgPack& result : results ) {
    833                                 // use rest of exploded tuple if present
    834                                 while ( result.nextExpl < result.expls.size() ) {
    835                                         const Alternative& actual = result.expls[result.nextExpl];
    836                                         result.env.addActual( actual.env, result.openVars );
    837                                         result.withArg( actual.expr );
    838                                         ++result.nextExpl;
    839                                 }
    840                         }
    841 
    842                         while ( ! results.empty() ) {
    843                                 // build combinations for all remaining arguments
    844                                 for ( ArgPack& result : results ) {
    845                                         // keep if used all arguments
    846                                         if ( result.nextArg >= args.size() ) {
    847                                                 finalResults.push_back( std::move(result) );
     952                        // append any unused arguments to vararg pack
     953                        std::size_t genEnd;
     954                        do {
     955                                genEnd = results.size();
     956
     957                                // iterate results
     958                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     959                                        auto nextArg = results[i].nextArg;
     960
     961                                        // use remainder of exploded tuple if present
     962                                        if ( results[i].hasExpl() ) {
     963                                                const ExplodedActual& expl = results[i].getExpl( args );
     964                                                const Alternative& actual = expl.alts[results[i].nextExpl];
     965                                               
     966                                                TypeEnvironment env = results[i].env;
     967                                                OpenVarSet openVars = results[i].openVars;
     968
     969                                                env.addActual( actual.env, openVars );
     970
     971                                                unsigned nextExpl = results[i].nextExpl + 1;
     972                                                if ( nextExpl == expl.alts.size() ) {
     973                                                        nextExpl = 0;
     974                                                }
     975
     976                                                results.emplace_back(
     977                                                        i, actual.expr, move(env), copy(results[i].need),
     978                                                        copy(results[i].have), move(openVars), nextArg, 0,
     979                                                        Cost::zero, nextExpl, results[i].explAlt );
     980                                               
    848981                                                continue;
    849982                                        }
    850983
     984                                        // finish result when out of arguments
     985                                        if ( nextArg >= args.size() ) {
     986                                                validateFunctionAlternative( func, results[i], results, out );
     987
     988                                                continue;
     989                                        }
     990
    851991                                        // add each possible next argument
    852                                         for ( const Alternative& actual : args[result.nextArg] ) {
    853                                                 ArgPack aResult = result; // copy to clone everything
    854                                                 // add details of actual to result
    855                                                 aResult.env.addActual( actual.env, aResult.openVars );
    856                                                 Cost cost = actual.cost;
    857 
    858                                                 // explode argument
    859                                                 std::vector<Alternative> exploded;
    860                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    861 
    862                                                 // add exploded argument to arg list
    863                                                 for ( Alternative& aActual : exploded ) {
    864                                                         aResult.withArg( aActual.expr, cost );
    865                                                         cost = Cost::zero;
     992                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     993                                                const ExplodedActual& expl = args[nextArg][j];
     994
     995                                                // fresh copies of parent parameters for this iteration
     996                                                TypeEnvironment env = results[i].env;
     997                                                OpenVarSet openVars = results[i].openVars;
     998
     999                                                env.addActual( expl.env, openVars );
     1000
     1001                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     1002                                                if ( expl.alts.empty() ) {
     1003                                                        results.emplace_back(
     1004                                                                results[i], move(env), copy(results[i].need),
     1005                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
     1006                                                       
     1007                                                        continue;
    8661008                                                }
    867                                                 ++aResult.nextArg;
    868                                                 nextResults.push_back( std::move(aResult) );
     1009
     1010                                                // add new result
     1011                                                results.emplace_back(
     1012                                                        i, expl.alts.front().expr, move(env), copy(results[i].need),
     1013                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
     1014                                                        expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
    8691015                                        }
    8701016                                }
    8711017
    872                                 // reset for next round
    873                                 results.swap( nextResults );
    874                                 nextResults.clear();
    875                         }
     1018                                genStart = genEnd;
     1019                        } while ( genEnd != results.size() );
    8761020                } else {
    8771021                        // filter out results that don't use all the arguments
    878                         for ( ArgPack& result : results ) {
    879                                 if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) {
    880                                         finalResults.push_back( std::move(result) );
     1022                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
     1023                                ArgPack& result = results[i];
     1024                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
     1025                                        validateFunctionAlternative( func, result, results, out );
    8811026                                }
    8821027                        }
    883                 }
    884 
    885                 // validate matching combos, add to final result list
    886                 for ( ArgPack& result : finalResults ) {
    887                         ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
    888                         Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) );
    889                         makeExprList( result.actuals, appExpr->get_args() );
    890                         PRINT(
    891                                 std::cerr << "instantiate function success: " << appExpr << std::endl;
    892                                 std::cerr << "need assertions:" << std::endl;
    893                                 printAssertionSet( result.need, std::cerr, 8 );
    894                         )
    895                         inferParameters( result.need, result.have, newAlt, result.openVars, out );
    8961028                }
    8971029        }
    … …  
    9201052                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
    9211053                )
     1054
     1055                // pre-explode arguments
     1056                ExplodedArgs argExpansions;
     1057                argExpansions.reserve( argAlternatives.size() );
     1058
     1059                for ( const AlternativeFinder& arg : argAlternatives ) {
     1060                        argExpansions.emplace_back();
     1061                        auto& argE = argExpansions.back();
     1062                        argE.reserve( arg.alternatives.size() );
     1063                       
     1064                        for ( const Alternative& actual : arg ) {
     1065                                argE.emplace_back( actual, indexer );
     1066                        }
     1067                }
    9221068
    9231069                AltList candidates;
    … …  
    9341080                                                Alternative newFunc( *func );
    9351081                                                referenceToRvalueConversion( newFunc.expr );
    936                                                 makeFunctionAlternatives( newFunc, function, argAlternatives,
     1082                                                makeFunctionAlternatives( newFunc, function, argExpansions,
    9371083                                                        std::back_inserter( candidates ) );
    9381084                                        }
    … …  
    9431089                                                        Alternative newFunc( *func );
    9441090                                                        referenceToRvalueConversion( newFunc.expr );
    945                                                         makeFunctionAlternatives( newFunc, function, argAlternatives,
     1091                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
    9461092                                                                std::back_inserter( candidates ) );
    9471093                                                } // if
    … …  
    9551101                // try each function operator ?() with each function alternative
    9561102                if ( ! funcOpFinder.alternatives.empty() ) {
    957                         // add function alternatives to front of argument list
    958                         argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );
     1103                        // add exploded function alternatives to front of argument list
     1104                        std::vector<ExplodedActual> funcE;
     1105                        funcE.reserve( funcFinder.alternatives.size() );
     1106                        for ( const Alternative& actual : funcFinder ) {
     1107                                funcE.emplace_back( actual, indexer );
     1108                        }
     1109                        argExpansions.insert( argExpansions.begin(), move(funcE) );
    9591110
    9601111                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
    … …  
    9681119                                                        Alternative newFunc( *funcOp );
    9691120                                                        referenceToRvalueConversion( newFunc.expr );
    970                                                         makeFunctionAlternatives( newFunc, function, argAlternatives,
     1121                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
    9711122                                                                std::back_inserter( candidates ) );
    9721123                                                }
    … …  
    9821133
    9831134                // compute conversionsion costs
    984                 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
    985                         Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
     1135                for ( Alternative& withFunc : candidates ) {
     1136                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
    9861137
    9871138                        PRINT(
    988                                 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
     1139                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
    9891140                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
    9901141                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
    … …  
    9951146                                printAll( appExpr->get_args(), std::cerr, 8 );
    9961147                                std::cerr << "bindings are:" << std::endl;
    997                                 withFunc->env.print( std::cerr, 8 );
     1148                                withFunc.env.print( std::cerr, 8 );
    9981149                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
    9991150                        )
    10001151                        if ( cvtCost != Cost::infinity ) {
    1001                                 withFunc->cvtCost = cvtCost;
    1002                                 alternatives.push_back( *withFunc );
     1152                                withFunc.cvtCost = cvtCost;
     1153                                alternatives.push_back( withFunc );
    10031154                        } // if
    10041155                } // for
    10051156
    1006                 candidates.clear();
    1007                 candidates.splice( candidates.end(), alternatives );
     1157                candidates = move(alternatives);
    10081158
    10091159                // use a new list so that alternatives are not examined by addAnonConversions twice.
    … …  
    10111161                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
    10121162
    1013                 // function may return struct or union value, in which case we need to add alternatives for implicit
    1014                 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
    1015                 // are never the cheapest expression
     1163                // function may return struct or union value, in which case we need to add alternatives
     1164                // for implicitconversions to each of the anonymous members, must happen after findMinCost
     1165                // since anon conversions are never the cheapest expression
    10161166                for ( const Alternative & alt : winners ) {
    10171167                        addAnonConversions( alt );
    10181168                }
    1019                 alternatives.splice( alternatives.begin(), winners );
     1169                spliceBegin( alternatives, winners );
    10201170
    10211171                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
    … …  
    10411191                AlternativeFinder finder( indexer, env );
    10421192                finder.find( addressExpr->get_arg() );
    1043                 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
    1044                         if ( isLvalue( i->expr ) ) {
    1045                                 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
     1193                for ( Alternative& alt : finder.alternatives ) {
     1194                        if ( isLvalue( alt.expr ) ) {
     1195                                alternatives.push_back(
     1196                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
    10461197                        } // if
    10471198                } // for
    … …  
    10491200
    10501201        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
    1051                 alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
     1202                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
    10521203        }
    10531204
    … …  
    10911242
    10921243                AltList candidates;
    1093                 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
     1244                for ( Alternative& alt : finder.alternatives ) {
    10941245                        AssertionSet needAssertions, haveAssertions;
    10951246                        OpenVarSet openVars;
    … …  
    10991250                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
    11001251                        // to.
    1101                         int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
     1252                        int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
    11021253                        if ( discardedValues < 0 ) continue;
    11031254                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
    11041255                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
    11051256                        // unification run for side-effects
    1106                         unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
    1107                         Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
     1257                        unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
     1258                                haveAssertions, openVars, indexer );
     1259                        Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
     1260                                alt.env );
    11081261                        if ( thisCost != Cost::infinity ) {
    11091262                                // count one safe conversion for each value that is thrown away
    11101263                                thisCost.incSafe( discardedValues );
    1111                                 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
    1112                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
     1264                                Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
     1265                                        alt.cost, thisCost );
     1266                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
     1267                                        back_inserter( candidates ) );
    11131268                        } // if
    11141269                } // for
    … …  
    13971552
    13981553        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
    1399                 std::list< AlternativeFinder > subExprAlternatives;
    1400                 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
    1401                 std::list< AltList > possibilities;
    1402                 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
    1403                 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
     1554                std::vector< AlternativeFinder > subExprAlternatives;
     1555                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
     1556                        back_inserter( subExprAlternatives ) );
     1557                std::vector< AltList > possibilities;
     1558                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
     1559                        back_inserter( possibilities ) );
     1560                for ( const AltList& alts : possibilities ) {
    14041561                        std::list< Expression * > exprs;
    1405                         makeExprList( *i, exprs );
     1562                        makeExprList( alts, exprs );
    14061563
    14071564                        TypeEnvironment compositeEnv;
    1408                         simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
    1409                         alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
     1565                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
     1566                        alternatives.push_back(
     1567                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
    14101568                } // for
    14111569        }

  • src/ResolvExpr/AlternativeFinder.h

    r9f10d1f2 r88ef2af  
    2121
    2222#include "Alternative.h"                 // for AltList, Alternative
     23#include "ExplodedActual.h"              // for ExplodedActual
    2324#include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
    2425#include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
    … …  
    3132
    3233namespace ResolvExpr {
     34        class ArgPack;
     35       
     36        /// First index is which argument, second index is which alternative for that argument,
     37        /// third index is which exploded element of that alternative
     38        using ExplodedArgs = std::vector< std::vector< ExplodedActual > >;
     39       
    3340        class AlternativeFinder : public Visitor {
    3441          public:
    … …  
    126133                /// Adds alternatives for offsetof expressions, given the base type and name of the member
    127134                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
     135                /// Takes a final result and checks if its assertions can be satisfied
    128136                template<typename OutputIterator>
    129                 void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out );
     137                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
     138                /// Finds matching alternatives for a function, given a set of arguments
     139                template<typename OutputIterator>
     140                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
     141                /// Checks if assertion parameters match for a new alternative
    130142                template< typename OutputIterator >
    131143                void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );

  • src/ResolvExpr/Resolver.cc

    r9f10d1f2 r88ef2af  
    1818#include <memory>                        // for allocator, allocator_traits<...
    1919#include <tuple>                         // for get
     20#include <vector>
    2021
    2122#include "Alternative.h"                 // for Alternative, AltList
    … …  
    411412
    412413                        // Find all alternatives for all arguments in canonical form
    413                         std::list< AlternativeFinder > argAlternatives;
     414                        std::vector< AlternativeFinder > argAlternatives;
    414415                        funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) );
    415416
    416417                        // List all combinations of arguments
    417                         std::list< AltList > possibilities;
     418                        std::vector< AltList > possibilities;
    418419                        combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
    419420

  • src/ResolvExpr/module.mk

    r9f10d1f2 r88ef2af  
    3232       ResolvExpr/Occurs.cc \
    3333       ResolvExpr/TypeEnvironment.cc \
    34        ResolvExpr/CurrentObject.cc
     34       ResolvExpr/CurrentObject.cc \
     35       ResolvExpr/ExplodedActual.cc

  • src/ResolvExpr/typeops.h

    r9f10d1f2 r88ef2af  
    1616#pragma once
    1717
     18#include <vector>
     19
    1820#include "SynTree/SynTree.h"
    1921#include "SynTree/Type.h"
    … …  
    2830        void combos( InputIterator begin, InputIterator end, OutputIterator out ) {
    2931                typedef typename InputIterator::value_type SetType;
    30                 typedef typename std::list< typename SetType::value_type > ListType;
     32                typedef typename std::vector< typename SetType::value_type > ListType;
    3133
    3234                if ( begin == end )     {
    … …  
    3840                begin++;
    3941
    40                 std::list< ListType > recursiveResult;
     42                std::vector< ListType > recursiveResult;
    4143                combos( begin, end, back_inserter( recursiveResult ) );
    4244
    43                 for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) {
    44                         for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) {
    45                                 ListType result;
    46                                 std::back_insert_iterator< ListType > inserter = back_inserter( result );
    47                                 *inserter++ = *j;
    48                                 std::copy( i->begin(), i->end(), inserter );
    49                                 *out++ = result;
    50                         } // for
    51                 } // for
     45                for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) {
     46                        ListType result;
     47                        std::back_insert_iterator< ListType > inserter = back_inserter( result );
     48                        *inserter++ = j;
     49                        std::copy( i.begin(), i.end(), inserter );
     50                        *out++ = result;
     51                }
    5252        }
    5353

  • src/SymTab/Validate.cc

    r9f10d1f2 r88ef2af  
    423423        }
    424424
     425        void checkGenericParameters( ReferenceToType * inst ) {
     426                for ( Expression * param : inst->parameters ) {
     427                        if ( ! dynamic_cast< TypeExpr * >( param ) ) {
     428                                throw SemanticError( "Expression parameters for generic types are currently unsupported: ", inst );
     429                        }
     430                }
     431        }
     432
    425433        void LinkReferenceToTypes::postvisit( StructInstType *structInst ) {
    426434                StructDecl *st = local_indexer->lookupStruct( structInst->get_name() );
    … …  
    434442                        forwardStructs[ structInst->get_name() ].push_back( structInst );
    435443                } // if
     444                checkGenericParameters( structInst );
    436445        }
    437446
    … …  
    446455                        forwardUnions[ unionInst->get_name() ].push_back( unionInst );
    447456                } // if
     457                checkGenericParameters( unionInst );
    448458        }
    449459
    … …  
    525535                // need to carry over the 'sized' status of each decl in the instance
    526536                for ( auto p : group_iterate( traitDecl->get_parameters(), traitInst->get_parameters() ) ) {
    527                         TypeExpr * expr = strict_dynamic_cast< TypeExpr * >( std::get<1>(p) );
     537                        TypeExpr * expr = dynamic_cast< TypeExpr * >( std::get<1>(p) );
     538                        if ( ! expr ) {
     539                                throw SemanticError( "Expression parameters for trait instances are currently unsupported: ", std::get<1>(p) );
     540                        }
    528541                        if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( expr->get_type() ) ) {
    529542                                TypeDecl * formalDecl = std::get<0>(p);

  • src/Tuples/TupleAssignment.cc

    r9f10d1f2 r88ef2af  
    251251                // combine assignment environments into combined expression environment
    252252                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
    253                 currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(
     253                // xxx -- was push_front
     254                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
    254255                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
    255256                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );

  • src/tests/.expect/castError.txt

    r9f10d1f2 r88ef2af  
    55  charAlternatives are:
    66Cost ( 1, 0, 0, 0 ): Cast of:
    7      Variable Expression: f: signed int
     7     Variable Expression: f: function
     8       accepting unspecified arguments
     9     ... returning nothing
     10
    811   ... to:
    912     char
    … …  
    2326
    2427Cost ( 1, 0, 0, 0 ): Cast of:
    25      Variable Expression: f: function
    26        accepting unspecified arguments
    27      ... returning nothing
    28 
     28     Variable Expression: f: signed int
    2929   ... to:
    3030     char
Note: See TracChangeset for help on using the changeset viewer.