Index: src/AST/Print.hpp =================================================================== --- src/AST/Print.hpp (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/AST/Print.hpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -16,6 +16,6 @@ #pragma once -#include -#include // for forward +#include +#include // for forward #include "AST/Node.hpp" @@ -32,6 +32,14 @@ void printShort( std::ostream & os, const ast::Decl * node, Indenter indent = {} ); -inline void printShort( std::ostream & os, const ast::Decl * node, unsigned int indent ) { - printShort( os, node, Indenter{ indent } ); +/// Print a collection of items +template< typename Coll > +void printAll( std::ostream & os, const Coll & c, Indenter indent = {} ) { + for ( const auto & i : c ) { + if ( ! i ) continue; + + os << indent; + print( os, i, indent ); + os << std::endl; + } } Index: src/AST/porting.md =================================================================== --- src/AST/porting.md (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/AST/porting.md (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -299,4 +299,7 @@ * `openVars` => `open` +`ExplodedActual` => `ExplodedArg` +* `ExplodedActual.h` => `ExplodedArg.hpp` + [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/Makefile.in (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -195,4 +195,5 @@ ResolvExpr/CurrentObject.$(OBJEXT) \ ResolvExpr/ExplodedActual.$(OBJEXT) \ + ResolvExpr/ExplodedArg.$(OBJEXT) \ ResolvExpr/FindOpenVars.$(OBJEXT) ResolvExpr/Occurs.$(OBJEXT) \ ResolvExpr/PolyCost.$(OBJEXT) \ @@ -633,4 +634,5 @@ ResolvExpr/CurrentObject.cc \ ResolvExpr/ExplodedActual.cc \ + ResolvExpr/ExplodedArg.cpp \ ResolvExpr/FindOpenVars.cc \ ResolvExpr/Occurs.cc \ @@ -895,4 +897,6 @@ ResolvExpr/ExplodedActual.$(OBJEXT): ResolvExpr/$(am__dirstamp) \ ResolvExpr/$(DEPDIR)/$(am__dirstamp) +ResolvExpr/ExplodedArg.$(OBJEXT): ResolvExpr/$(am__dirstamp) \ + ResolvExpr/$(DEPDIR)/$(am__dirstamp) ResolvExpr/FindOpenVars.$(OBJEXT): ResolvExpr/$(am__dirstamp) \ ResolvExpr/$(DEPDIR)/$(am__dirstamp) @@ -1277,4 +1281,5 @@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/CurrentObject.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/ExplodedActual.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/ExplodedArg.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/FindOpenVars.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/Occurs.Po@am__quote@ Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/AlternativeFinder.cc (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -116,5 +116,5 @@ /// Finds matching alternatives for a function, given a set of arguments template - void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out ); + void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs_old& args, OutputIterator out ); /// Sets up parameter inference for an output alternative template< typename OutputIterator > @@ -593,5 +593,5 @@ /// Gets the list of exploded alternatives for this pack - const ExplodedActual& getExpl( const ExplodedArgs& args ) const { + const ExplodedActual& getExpl( const ExplodedArgs_old& args ) const { return args[nextArg-1][explAlt]; } @@ -617,5 +617,5 @@ /// Instantiates an argument to match a formal, returns false if no results left bool instantiateArgument( Type* formalType, Initializer* initializer, - const ExplodedArgs& args, std::vector& results, std::size_t& genStart, + const ExplodedArgs_old& args, std::vector& results, std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { if ( TupleType * tupleType = dynamic_cast( formalType ) ) { @@ -889,5 +889,5 @@ template void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func, - FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { + FunctionType *funcType, const ExplodedArgs_old &args, OutputIterator out ) { OpenVarSet funcOpenVars; AssertionSet funcNeed, funcHave; @@ -1021,5 +1021,5 @@ // pre-explode arguments - ExplodedArgs argExpansions; + ExplodedArgs_old argExpansions; argExpansions.reserve( argAlternatives.size() ); Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/AlternativeFinder.h (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -37,5 +37,5 @@ /// First index is which argument, second index is which alternative for that argument, /// third index is which exploded element of that alternative - using ExplodedArgs = std::vector< std::vector< ExplodedActual > >; + using ExplodedArgs_old = std::vector< std::vector< ExplodedActual > >; class AlternativeFinder { Index: src/ResolvExpr/Candidate.hpp =================================================================== --- src/ResolvExpr/Candidate.hpp (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/Candidate.hpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -70,4 +70,17 @@ using CandidateList = std::vector< CandidateRef >; +/// Splice src after dst, clearing src +static inline void splice( CandidateList & dst, CandidateList & src ) { + dst.reserve( dst.size() + src.size() ); + for ( CandidateRef & r : src ) { dst.emplace_back( std::move( r ) ); } + src.clear(); +} + +/// Splice src before dst +static inline void spliceBegin( CandidateList & dst, CandidateList & src ) { + splice( src, dst ); + dst.swap( src ); +} + /// Sum the cost of a list of candidates static inline Cost sumCost( const CandidateList & candidates ) { Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/CandidateFinder.cpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -16,12 +16,15 @@ #include "CandidateFinder.hpp" +#include #include // for back_inserter #include #include #include +#include #include "Candidate.hpp" #include "CompilationState.h" #include "Cost.h" +#include "ExplodedArg.hpp" #include "Resolver.h" #include "SatisfyAssertions.hpp" @@ -33,5 +36,7 @@ #include "AST/Print.hpp" #include "AST/SymbolTable.hpp" +#include "AST/Type.hpp" #include "SymTab/Mangler.h" +#include "Tuples/Tuples.h" // for handleTupleAssignment #define PRINT( text ) if ( resolvep ) { text } @@ -40,4 +45,33 @@ namespace { + + /// First index is which argument, second is which alternative, third is which exploded element + using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; + + /// Returns a list of alternatives with the minimum cost in the given list + CandidateList findMinCost( const CandidateList & candidates ) { + CandidateList out; + Cost minCost = Cost::infinity; + for ( const CandidateRef & r : candidates ) { + if ( r->cost < minCost ) { + minCost = r->cost; + out.clear(); + out.emplace_back( r ); + } else if ( r->cost == minCost ) { + out.emplace_back( r ); + } + } + return out; + } + + /// Computes conversion cost for a given candidate + Cost computeApplicationConversionCost( + const CandidateRef & cand, const ast::SymbolTable & symtab + ) { + #warning unimplemented + (void)cand; (void)symtab; + assert(false); + return Cost::infinity; + } /// Actually visits expressions to find their candidate interpretations @@ -65,8 +99,169 @@ } + /// Builds a list of candidates for a function, storing them in out + void makeFunctionCandidates( + const CandidateRef & func, const ast::FunctionType * funcType, + const ExplodedArgs_new & args, CandidateList & out + ) { + #warning unimplemented + (void)func; (void)funcType; (void)args; (void)out; + assert(false); + } + + /// Adds implicit struct-conversions to the alternative list + void addAnonConversions( const CandidateRef & cand ) { + #warning unimplemented + (void)cand; + assert(false); + } + void postvisit( const ast::UntypedExpr * untypedExpr ) { - #warning unimplemented - (void)untypedExpr; - assert(false); + CandidateFinder funcFinder{ symtab, tenv }; + funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() ); + // short-circuit if no candidates + if ( funcFinder.candidates.empty() ) return; + + std::vector< CandidateFinder > argCandidates = + selfFinder.findSubExprs( untypedExpr->args ); + + // take care of possible tuple assignments + // if not tuple assignment, handled as normal function call + Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); + + // find function operators + ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; + CandidateFinder opFinder{ symtab, tenv }; + // okay if there aren't any function operations + opFinder.find( opExpr, ResolvMode::withoutFailFast() ); + PRINT( + std::cerr << "known function ops:" << std::endl; + print( std::cerr, opFinder.candidates, 1 ); + ) + + // pre-explode arguments + ExplodedArgs_new argExpansions; + for ( const CandidateFinder & args : argCandidates ) { + argExpansions.emplace_back(); + auto & argE = argExpansions.back(); + for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); } + } + + // Find function matches + CandidateList found; + SemanticErrorException errors; + for ( CandidateRef & func : funcFinder ) { + try { + PRINT( + std::cerr << "working on alternative:" << std::endl; + print( std::cerr, *func, 2 ); + ) + + // check if the type is a pointer to function + const ast::Type * funcResult = func->expr->result->stripReferences(); + if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) { + if ( auto function = pointer->base.as< ast::FunctionType >() ) { + CandidateRef newFunc{ new Candidate{ *func } }; + newFunc->expr = + referenceToRvalueConversion( newFunc->expr, newFunc->cost ); + makeFunctionCandidates( newFunc, function, argExpansions, found ); + } + } else if ( + auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) + ) { + if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) { + if ( auto function = clz->bound.as< ast::FunctionType >() ) { + CandidateRef newFunc{ new Candidate{ *func } }; + newFunc->expr = + referenceToRvalueConversion( newFunc->expr, newFunc->cost ); + makeFunctionCandidates( newFunc, function, argExpansions, found ); + } + } + } + } catch ( SemanticErrorException & e ) { errors.append( e ); } + } + + // Find matches on function operators `?()` + if ( ! opFinder.candidates.empty() ) { + // add exploded function alternatives to front of argument list + std::vector< ExplodedArg > funcE; + funcE.reserve( funcFinder.candidates.size() ); + for ( const CandidateRef & func : funcFinder ) { + funcE.emplace_back( *func, symtab ); + } + argExpansions.emplace_front( std::move( funcE ) ); + + for ( const CandidateRef & op : opFinder ) { + try { + // check if type is pointer-to-function + const ast::Type * opResult = op->expr->result->stripReferences(); + if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) { + if ( auto function = pointer->base.as< ast::FunctionType >() ) { + CandidateRef newOp{ new Candidate{ *op} }; + newOp->expr = + referenceToRvalueConversion( newOp->expr, newOp->cost ); + makeFunctionCandidates( newOp, function, argExpansions, found ); + } + } + } catch ( SemanticErrorException & e ) { errors.append( e ); } + } + } + + // Implement SFINAE; resolution errors are only errors if there aren't any non-error + // candidates + if ( found.empty() && ! errors.isEmpty() ) { throw errors; } + + // Compute conversion costs + for ( CandidateRef & withFunc : found ) { + Cost cvtCost = computeApplicationConversionCost( withFunc, symtab ); + + PRINT( + auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >(); + auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); + auto function = pointer->base.strict_as< ast::FunctionType >(); + + std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; + std::cerr << "parameters are:" << std::endl; + ast::printAll( std::cerr, function->params, 2 ); + std::cerr << "arguments are:" << std::endl; + ast::printAll( std::cerr, appExpr->args, 2 ); + std::cerr << "bindings are:" << std::endl; + ast::print( std::cerr, withFunc->env, 2 ); + std::cerr << "cost is: " << withFunc->cost << std::endl; + std::cerr << "cost of conversion is:" << cvtCost << std::endl; + ) + + if ( cvtCost != Cost::infinity ) { + withFunc->cvtCost = cvtCost; + candidates.emplace_back( std::move( withFunc ) ); + } + } + found = std::move( candidates ); + + // use a new list so that candidates are not examined by addAnonConversions twice + CandidateList winners = findMinCost( found ); + promoteCvtCost( winners ); + + // function may return a struct/union value, in which case we need to add candidates + // for implicit conversions to each of the anonymous members, which must happen after + // `findMinCost`, since anon conversions are never the cheapest + for ( const CandidateRef & c : winners ) { + addAnonConversions( c ); + } + spliceBegin( candidates, winners ); + + if ( candidates.empty() && targetType && ! targetType->isVoid() ) { + // If resolution is unsuccessful with a target type, try again without, since it + // will sometimes succeed when it wouldn't with a target type binding. + // For example: + // forall( otype T ) T & ?[]( T *, ptrdiff_t ); + // const char * x = "hello world"; + // unsigned char ch = x[0]; + // Fails with simple return type binding (xxx -- check this!) as follows: + // * T is bound to unsigned char + // * (x: const char *) is unified with unsigned char *, which fails + // xxx -- fix this better + targetType = nullptr; + postvisit( untypedExpr ); + } } @@ -440,20 +635,4 @@ } - /// Returns a list of alternatives with the minimum cost in the given list - CandidateList findMinCost( const CandidateList & candidates ) { - CandidateList out; - Cost minCost = Cost::infinity; - for ( const CandidateRef & r : candidates ) { - if ( r->cost < minCost ) { - minCost = r->cost; - out.clear(); - out.emplace_back( r ); - } else if ( r->cost == minCost ) { - out.emplace_back( r ); - } - } - return out; - } - } // anonymous namespace Index: src/ResolvExpr/ExplodedActual.cc =================================================================== --- src/ResolvExpr/ExplodedActual.cc (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/ExplodedActual.cc (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -5,5 +5,5 @@ // file "LICENCE" distributed with Cforall. // -// Alternative.h -- +// ExplodedActual.cc -- // // Author : Aaron B. Moss @@ -24,2 +24,8 @@ } } + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ExplodedActual.h =================================================================== --- src/ResolvExpr/ExplodedActual.h (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/ExplodedActual.h (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -5,5 +5,5 @@ // file "LICENCE" distributed with Cforall. // -// Alternative.h -- +// ExplodedActual.h -- // // Author : Aaron B. Moss @@ -37,2 +37,8 @@ }; } + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ExplodedArg.cpp =================================================================== --- src/ResolvExpr/ExplodedArg.cpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) +++ src/ResolvExpr/ExplodedArg.cpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -0,0 +1,31 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ExplodedArg.cpp -- +// +// Author : Aaron B. Moss +// Created On : Tue Jun 11 16:18:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Tue Jun 11 16:18:00 2019 +// Update Count : 1 +// + +#include "ExplodedArg.hpp" + +#include "Tuples/Explode.h" // for Tuples::explode + +namespace ResolvExpr { + +ExplodedArg::ExplodedArg( const Candidate & arg, const ast::SymbolTable & symtab ) +: env( arg.env ), cost( arg.cost ), exprs() { Tuples::explode( arg, symtab, *this ); } + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ExplodedArg.hpp =================================================================== --- src/ResolvExpr/ExplodedArg.hpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) +++ src/ResolvExpr/ExplodedArg.hpp (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -0,0 +1,48 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ExplodedArg.hpp -- +// +// Author : Aaron B. Moss +// Created On : Tue Jun 11 16:18:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Tue Jun 11 16:18:00 2019 +// Update Count : 1 +// + +#pragma once + +#include + +#include "Candidate.hpp" // for Candidate, CandidateList +#include "Cost.h" // for Cost +#include "AST/Expr.hpp" +#include "AST/Node.hpp" // for ptr +#include "AST/TypeEnvironment.hpp" // for TypeEnvironment +#include "AST/SymbolTable.hpp" // for SymbolTable + +namespace ResolvExpr { + +/// Pre-exploded argument +struct ExplodedArg { + ast::TypeEnvironment env; + Cost cost; + std::vector< ast::ptr > exprs; + + ExplodedArg() : env(), cost( Cost::zero ), exprs() {} + ExplodedArg( const Candidate & arg, const ast::SymbolTable & symtab ); + + ExplodedArg( ExplodedArg && ) = default; + ExplodedArg & operator= ( ExplodedArg && ) = default; +}; + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/ResolvExpr/module.mk (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -26,4 +26,5 @@ ResolvExpr/CurrentObject.cc \ ResolvExpr/ExplodedActual.cc \ + ResolvExpr/ExplodedArg.cpp \ ResolvExpr/FindOpenVars.cc \ ResolvExpr/Occurs.cc \ Index: src/Tuples/Explode.h =================================================================== --- src/Tuples/Explode.h (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/Tuples/Explode.h (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -19,9 +19,16 @@ #include // for forward +#include "AST/Expr.hpp" #include "ResolvExpr/Alternative.h" // for Alternative, AltList +#include "ResolvExpr/Candidate.hpp" // for Candidate, CandidateList #include "ResolvExpr/ExplodedActual.h" // for ExplodedActual +#include "ResolvExpr/ExplodedArg.hpp" // for ExplodedArg #include "SynTree/Expression.h" // for Expression, UniqueExpr, AddressExpr #include "SynTree/Type.h" // for TupleType, Type #include "Tuples.h" // for maybeImpure + +namespace ast { + class SymbolTable; +} namespace SymTab { @@ -130,4 +137,25 @@ explode( alts.begin(), alts.end(), indexer, std::forward(out), isTupleAssign ); } + +/// helper function used by explode +template< typename Output > +void explodeUnique( + const ast::Expr * expr, const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, + Output && out, bool isTupleAssign +) { + #warning unimplemented + (void)expr; (void)arg; (void)symtab; (void)out; (void)isTupleAssign; + assert(false); +} + +/// expands a tuple-valued candidate into multiple candidates, each with a non-tuple type +template< typename Output > +void explode( + const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, Output && out, + bool isTupleAssign = false +) { + explodeUnique( arg.expr, arg, symtab, std::forward< Output >( out ), isTupleAssign ); +} + } // namespace Tuples Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/Tuples/TupleAssignment.cc (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -377,4 +377,13 @@ } } + + void handleTupleAssignment( + ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, + std::vector< ResolvExpr::CandidateFinder > & args + ) { + #warning unimplmented + (void)finder; (void)assign; (void)args; + assert(false); + } } // namespace Tuples Index: src/Tuples/Tuples.h =================================================================== --- src/Tuples/Tuples.h (revision 4b7cce6773c47bc28d79e42cdc051573f66169d6) +++ src/Tuples/Tuples.h (revision d7a02ae903476ded9a21da3034888ccf8617a83d) @@ -26,4 +26,5 @@ #include "ResolvExpr/AlternativeFinder.h" +#include "ResolvExpr/CandidateFinder.hpp" namespace Tuples { @@ -31,4 +32,7 @@ void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, std::vector< ResolvExpr::AlternativeFinder >& args ); + void handleTupleAssignment( + ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, + std::vector< ResolvExpr::CandidateFinder > & args ); // TupleExpansion.cc