Index: src/ResolvExpr/AdjustExprType.cc =================================================================== --- src/ResolvExpr/AdjustExprType.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/AdjustExprType.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -19,83 +19,6 @@ #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Kind::Ftype -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for PointerType, TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment namespace ResolvExpr { - -namespace { - class AdjustExprType_old final : public WithShortCircuiting { - public: - AdjustExprType_old( const TypeEnvironment & env, const SymTab::Indexer & indexer ); - void premutate( VoidType * ) { visit_children = false; } - void premutate( BasicType * ) { visit_children = false; } - void premutate( PointerType * ) { visit_children = false; } - void premutate( ArrayType * ) { visit_children = false; } - void premutate( FunctionType * ) { visit_children = false; } - void premutate( StructInstType * ) { visit_children = false; } - void premutate( UnionInstType * ) { visit_children = false; } - void premutate( EnumInstType * ) { visit_children = false; } - void premutate( TraitInstType * ) { visit_children = false; } - void premutate( TypeInstType * ) { visit_children = false; } - void premutate( TupleType * ) { visit_children = false; } - void premutate( VarArgsType * ) { visit_children = false; } - void premutate( ZeroType * ) { visit_children = false; } - void premutate( OneType * ) { visit_children = false; } - - Type * postmutate( ArrayType * arrayType ); - Type * postmutate( FunctionType * functionType ); - Type * postmutate( TypeInstType * aggregateUseType ); - - private: - const TypeEnvironment & env; - const SymTab::Indexer & indexer; - }; - - AdjustExprType_old::AdjustExprType_old( const TypeEnvironment &env, const SymTab::Indexer &indexer ) - : env( env ), indexer( indexer ) { - } - - Type * AdjustExprType_old::postmutate( ArrayType * arrayType ) { - PointerType * pointerType = new PointerType{ arrayType->get_qualifiers(), arrayType->base }; - arrayType->base = nullptr; - delete arrayType; - return pointerType; - } - - Type * AdjustExprType_old::postmutate( FunctionType * functionType ) { - return new PointerType{ Type::Qualifiers(), functionType }; - } - - Type * AdjustExprType_old::postmutate( TypeInstType * typeInst ) { - if ( const EqvClass * eqvClass = env.lookup( typeInst->get_name() ) ) { - if ( eqvClass->data.kind == TypeDecl::Ftype ) { - return new PointerType{ Type::Qualifiers(), typeInst }; - } - } else if ( const NamedTypeDecl * ntDecl = indexer.lookupType( typeInst->get_name() ) ) { - if ( const TypeDecl * tyDecl = dynamic_cast< const TypeDecl * >( ntDecl ) ) { - if ( tyDecl->get_kind() == TypeDecl::Ftype ) { - return new PointerType{ Type::Qualifiers(), typeInst }; - } // if - } // if - } // if - return typeInst; - } -} // anonymous namespace - -void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { - PassVisitor adjuster( env, indexer ); - Type * newType = type->acceptMutator( adjuster ); - type = newType; -} - -void adjustExprType( Type *& type ) { - TypeEnvironment env; - SymTab::Indexer indexer; - adjustExprType( type, env, indexer ); -} namespace { Index: src/ResolvExpr/Alternative.cc =================================================================== --- src/ResolvExpr/Alternative.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,133 +1,0 @@ -// -// 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. -// -// Alternative.cc -- -// -// Author : Richard C. Bilson -// Created On : Sat May 16 23:44:23 2015 -// Last Modified By : Aaron B. Moss -// Last Modified On : Thu Oct 11 10:55:00 2018 -// Update Count : 3 -// - -#include "Alternative.h" - -#include // for operator<<, ostream, basic_o... -#include // for operator<<, char_traits, string -#include // for move - -#include "Common/utility.h" // for cloneAll -#include "ResolvExpr/Cost.h" // for Cost, Cost::zero, operator<< -#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment -#include "SynTree/Expression.h" // for Expression -#include "SynTree/Type.h" // for Type - -namespace ResolvExpr { - Alternative::Alternative() - : cost( Cost::zero ), cvtCost( Cost::zero ), expr( nullptr ), env(), openVars(), need() {} - - Alternative::Alternative( Expression *expr, const TypeEnvironment &env ) - : cost( Cost::zero ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars(), need() {} - - Alternative::Alternative( const Alternative &o, Expression *expr, const Cost &cost ) - : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( o.env ), openVars( o.openVars ), - need() { cloneAll( o.need, need ); } - - Alternative::Alternative( Expression *expr, const TypeEnvironment &env, - const OpenVarSet& openVars, const AssertionList& oneed, const Cost& cost ) - : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars( openVars ), - need() { cloneAll( oneed, need ); } - - Alternative::Alternative( Expression *expr, const TypeEnvironment &env, - const OpenVarSet& openVars, const AssertionList& oneed, const Cost& cost, - const Cost &cvtCost ) - : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ), openVars( openVars ), - need() { cloneAll( oneed, need ); } - - Alternative::Alternative( Expression *expr, const TypeEnvironment &env, - const OpenVarSet &openVars, const AssertionSet &oneed, const Cost &cost) - : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ), openVars( openVars ), - need() { cloneAll( oneed, need ); } - - Alternative::Alternative( Expression *expr, const TypeEnvironment &env, - const OpenVarSet &openVars, const AssertionSet &oneed, const Cost &cost, - const Cost& cvtCost ) - : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ), openVars( openVars ), - need() { cloneAll( oneed, need ); } - - Alternative::Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars, - AssertionSet &&needSet, const Cost &cost ) - : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( std::move(env) ), - openVars( std::move(openVars) ), need( needSet.begin(), needSet.end() ) {} - - Alternative::Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars, - AssertionSet &&needSet, const Cost &cost, const Cost &cvtCost ) - : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( std::move(env) ), - openVars( std::move(openVars) ), need( needSet.begin(), needSet.end() ) {} - - Alternative::Alternative( const Alternative &other ) - : cost( other.cost ), cvtCost( other.cvtCost ), expr( maybeClone( other.expr ) ), - env( other.env ), openVars( other.openVars ), need() { cloneAll( other.need, need ); } - - Alternative &Alternative::operator=( const Alternative &other ) { - if ( &other == this ) return *this; - delete expr; - cost = other.cost; - cvtCost = other.cvtCost; - expr = maybeClone( other.expr ); - env = other.env; - openVars = other.openVars; - need.clear(); - cloneAll( other.need, need ); - return *this; - } - - Alternative::Alternative( Alternative && other ) - : cost( other.cost ), cvtCost( other.cvtCost ), expr( other.expr ), - env( std::move( other.env ) ), openVars( std::move( other.openVars ) ), - need( std::move( other.need ) ) { other.expr = nullptr; } - - Alternative & Alternative::operator=( Alternative && other ) { - if ( &other == this ) return *this; - delete expr; - cost = other.cost; - cvtCost = other.cvtCost; - expr = other.expr; - env = std::move( other.env ); - openVars = std::move( other.openVars ); - need = std::move( other.need ); - other.expr = nullptr; - return *this; - } - - Alternative::~Alternative() { - for ( AssertionItem& n : need ) { delete n.decl; } - delete expr; - } - - void Alternative::print( std::ostream &os, Indenter indent ) const { - os << "Cost " << cost << ": "; - if ( expr ) { - expr->print( os, indent+1 ); - os << std::endl << indent << "(types:" << std::endl; - os << indent+1; - expr->result->print( os, indent+1 ); - os << std::endl << indent << ")" << std::endl; - } else { - os << "Null expression!" << std::endl; - } // if - os << indent << "Environment:"; - env.print( os, indent+1 ); - os << std::endl; - } - -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,124 +1,0 @@ -// -// 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. -// -// Alternative.h -- -// -// Author : Richard C. Bilson -// Created On : Sat May 16 23:45:43 2015 -// Last Modified By : Aaron B. Moss -// Last Modified On : Thu Oct 11 10:55:00 2018 -// Update Count : 4 -// - -#pragma once - -#include // for ostream -#include // for vector - -#include "Cost.h" // for Cost -#include "TypeEnvironment.h" // for TypeEnvironment, AssertionSetValue - -#include "Common/utility.h" // for maybeClone - -class Expression; - -namespace ResolvExpr { - /// One assertion to resolve - struct AssertionItem { - const DeclarationWithType* decl; - AssertionSetValue info; - - AssertionItem() = default; - AssertionItem( const DeclarationWithType* decl, const AssertionSetValue& info ) - : decl(decl), info(info) {} - AssertionItem( const AssertionSet::value_type& e ) : decl(e.first), info(e.second) {} - operator AssertionSet::value_type () const { return { decl, info }; } - - // to support cloneAll - AssertionItem clone() const { return { maybeClone(decl), info }; } - }; - /// A list of unresolved assertions - using AssertionList = std::vector; - - /// Clones an assertion list into an assertion set - static inline void cloneAll( const AssertionList& src, AssertionSet& dst ) { - for ( const AssertionItem& item : src ) { - dst.emplace( maybeClone(item.decl), item.info ); - } - } - - /// Clones an assertion set into an assertion list - static inline void cloneAll( const AssertionSet& src, AssertionList& dst ) { - dst.reserve( dst.size() + src.size() ); - for ( const auto& entry : src ) { - dst.emplace_back( maybeClone(entry.first), entry.second ); - } - } - - /// Clones an assertion list into an assertion list - static inline void cloneAll( const AssertionList& src, AssertionList& dst ) { - dst.reserve( dst.size() + src.size() ); - for ( const AssertionItem& item : src ) { - dst.emplace_back( maybeClone(item.decl), item.info ); - } - } - - /// One option for resolution of an expression - struct Alternative { - Alternative(); - Alternative( Expression *expr, const TypeEnvironment &env ); - Alternative( const Alternative &o, Expression *expr, const Cost &cost ); - Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet& openVars, - const AssertionList& need, const Cost &cost ); - Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet& openVars, - const AssertionList& need, const Cost &cost, const Cost &cvtCost ); - Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet &openVars, - const AssertionSet &need, const Cost &cost); - Alternative( Expression *expr, const TypeEnvironment &env, const OpenVarSet &openVars, - const AssertionSet &need, const Cost &cost, const Cost& cvtCost ); - Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars, - AssertionSet &&need, const Cost &cost ); - Alternative( Expression *expr, TypeEnvironment &&env, OpenVarSet &&openVars, - AssertionSet &&need, const Cost &cost, const Cost &cvtCost ); - Alternative( const Alternative &other ); - Alternative &operator=( const Alternative &other ); - Alternative( Alternative && other ); - Alternative &operator=( Alternative && other ); - ~Alternative(); - - void print( std::ostream &os, Indenter indent = {} ) const; - - /// Returns the stored expression, but released from management of this Alternative - Expression* release_expr() { - Expression* tmp = expr; - expr = nullptr; - return tmp; - } - - /// Sorts by cost - bool operator< ( const Alternative& o ) const { return cost < o.cost; } - - Cost cost; ///< Cost of the whole expression - Cost cvtCost; ///< Cost of conversions to the satisfying expression - Expression *expr; ///< Satisfying expression - TypeEnvironment env; ///< Containing type environment - OpenVarSet openVars; ///< Open variables for environment - AssertionList need; ///< Assertions which need to be resolved - }; - - typedef std::vector< Alternative > AltList; - - static inline std::ostream & operator<<(std::ostream & os, const ResolvExpr::Alternative & alt) { - alt.print( os ); - return os; - } -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,1773 +1,0 @@ -// -// 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. -// -// AlternativeFinder.cc -- -// -// Author : Richard C. Bilson -// Created On : Sat May 16 23:52:08 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Thu Aug 8 16:35:00 2019 -// Update Count : 38 -// - -#include "AlternativeFinder.h" - -#include // for copy -#include // for strict_dynamic_cast, assert, assertf -#include // for size_t -#include // for operator<<, cerr, ostream, endl -#include // for back_insert_iterator, back_inserter -#include // for _List_iterator, list, _List_const_... -#include // for _Rb_tree_iterator, map, _Rb_tree_c... -#include // for allocator_traits<>::value_type, unique_ptr -#include // for pair -#include // for vector - -#include "CompilationState.h" // for resolvep -#include "AdjustExprType.hpp" // for adjustExprType -#include "Alternative.h" // for AltList, Alternative -#include "AST/Expr.hpp" -#include "AST/SymbolTable.hpp" -#include "AST/Type.hpp" -#include "CastCost.hpp" // for castCost -#include "Common/SemanticError.h" // for SemanticError -#include "Common/utility.h" // for deleteAll, printAll, CodeLocation -#include "ConversionCost.h" // for conversionCost -#include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... -#include "ExplodedActual.h" // for ExplodedActual -#include "InitTweak/InitTweak.h" // for getFunctionName -#include "PolyCost.hpp" // for polyCost -#include "RenameVars.h" // for RenameVars, global_renamer -#include "ResolveAssertions.h" // for resolveAssertions -#include "ResolveTypeof.h" // for resolveTypeof -#include "Resolver.h" // for resolveStmtExpr -#include "SpecCost.hpp" // for specCost -#include "SymTab/Indexer.h" // for Indexer -#include "SymTab/Mangler.h" // for Mangler -#include "SymTab/ValidateType.h" // for validateType -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec... -#include "SynTree/Expression.h" // for Expression, CastExpr, NameExpr -#include "SynTree/Initializer.h" // for SingleInit, operator<<, Designation -#include "SynTree/SynTree.h" // for UniqueId -#include "SynTree/Type.h" // for Type, FunctionType, PointerType -#include "Tuples/Explode.h" // for explode -#include "Tuples/Tuples.h" // for isTtype, handleTupleAssignment -#include "typeops.h" // for combos -#include "Unify.h" // for unify - -#define PRINT( text ) if ( resolvep ) { text } -//#define DEBUG_COST - -namespace ResolvExpr { - struct AlternativeFinder::Finder : public WithShortCircuiting { - Finder( AlternativeFinder & altFinder ) : altFinder( altFinder ), indexer( altFinder.indexer ), alternatives( altFinder.alternatives ), env( altFinder.env ), targetType( altFinder.targetType ) {} - - void previsit( BaseSyntaxNode * ) { visit_children = false; } - - void postvisit( ApplicationExpr * applicationExpr ); - void postvisit( UntypedExpr * untypedExpr ); - void postvisit( AddressExpr * addressExpr ); - void postvisit( LabelAddressExpr * labelExpr ); - void postvisit( CastExpr * castExpr ); - void postvisit( VirtualCastExpr * castExpr ); - void postvisit( KeywordCastExpr * castExpr ); - void postvisit( UntypedMemberExpr * memberExpr ); - void postvisit( MemberExpr * memberExpr ); - void postvisit( NameExpr * variableExpr ); - void postvisit( VariableExpr * variableExpr ); - void postvisit( ConstantExpr * constantExpr ); - void postvisit( SizeofExpr * sizeofExpr ); - void postvisit( AlignofExpr * alignofExpr ); - void postvisit( UntypedOffsetofExpr * offsetofExpr ); - void postvisit( OffsetofExpr * offsetofExpr ); - void postvisit( OffsetPackExpr * offsetPackExpr ); - void postvisit( LogicalExpr * logicalExpr ); - void postvisit( ConditionalExpr * conditionalExpr ); - void postvisit( CommaExpr * commaExpr ); - void postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ); - void postvisit( ConstructorExpr * ctorExpr ); - void postvisit( RangeExpr * rangeExpr ); - void postvisit( UntypedTupleExpr * tupleExpr ); - void postvisit( TupleExpr * tupleExpr ); - void postvisit( TupleIndexExpr * tupleExpr ); - void postvisit( TupleAssignExpr * tupleExpr ); - void postvisit( UniqueExpr * unqExpr ); - void postvisit( StmtExpr * stmtExpr ); - void postvisit( UntypedInitExpr * initExpr ); - void postvisit( InitExpr * initExpr ); - void postvisit( DeletedExpr * delExpr ); - void postvisit( GenericExpr * genExpr ); - - /// Adds alternatives for anonymous members - void addAnonConversions( const Alternative & alt ); - /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member - template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Alternative &alt, const Cost &newCost, const std::string & name ); - /// Adds alternatives for member expressions where the left side has tuple type - void addTupleMembers( TupleType *tupleType, Expression *expr, const Alternative &alt, const Cost &newCost, Expression *member ); - /// Adds alternatives for offsetof expressions, given the base type and name of the member - template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name ); - /// Takes a final result and checks if its assertions can be satisfied - template - void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector& results, OutputIterator out ); - /// Finds matching alternatives for a function, given a set of arguments - template - void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs_old& args, OutputIterator out ); - /// Sets up parameter inference for an output alternative - template< typename OutputIterator > - void inferParameters( Alternative &newAlt, OutputIterator out ); - private: - AlternativeFinder & altFinder; - const SymTab::Indexer &indexer; - AltList & alternatives; - const TypeEnvironment &env; - Type *& targetType; - }; - - Cost sumCost( const AltList &in ) { - Cost total = Cost::zero; - for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { - total += i->cost; - } - return total; - } - - void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) { - std::vector sorted; - sorted.reserve(list.size()); - for(const auto & c : list) { - std::stringstream ss; - c.print( ss, indentAmt ); - sorted.push_back(ss.str()); - } - - std::sort(sorted.begin(), sorted.end()); - - for ( const auto & s : sorted ) { - os << s << std::endl; - } - } - - namespace { - void makeExprList( const AltList &in, std::list< Expression* > &out ) { - for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { - out.push_back( i->expr->clone() ); - } - } - - struct PruneStruct { - bool isAmbiguous; - AltList::iterator candidate; - PruneStruct() {} - PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {} - }; - - /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations - template< typename InputIterator, typename OutputIterator > - void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) { - // select the alternatives that have the minimum conversion cost for a particular set of result types - std::map< std::string, PruneStruct > selected; - for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) { - PruneStruct current( candidate ); - std::string mangleName; - { - Type * newType = candidate->expr->get_result()->clone(); - candidate->env.apply( newType ); - mangleName = SymTab::Mangler::mangle( newType ); - delete newType; - } - std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName ); - if ( mapPlace != selected.end() ) { - if ( candidate->cost < mapPlace->second.candidate->cost ) { - PRINT( - std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl; - ) - selected[ mangleName ] = current; - } else if ( candidate->cost == mapPlace->second.candidate->cost ) { - // if one of the candidates contains a deleted identifier, can pick the other, since - // deleted expressions should not be ambiguous if there is another option that is at least as good - if ( findDeletedExpr( candidate->expr ) ) { - // do nothing - PRINT( std::cerr << "candidate is deleted" << std::endl; ) - } else if ( findDeletedExpr( mapPlace->second.candidate->expr ) ) { - PRINT( std::cerr << "current is deleted" << std::endl; ) - selected[ mangleName ] = current; - } else { - PRINT( - std::cerr << "marking ambiguous" << std::endl; - ) - mapPlace->second.isAmbiguous = true; - } - } else { - PRINT( - std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl; - ) - } - } else { - selected[ mangleName ] = current; - } - } - - // accept the alternatives that were unambiguous - for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) { - if ( ! target->second.isAmbiguous ) { - Alternative &alt = *target->second.candidate; - alt.env.applyFree( alt.expr->get_result() ); - *out++ = alt; - } - } - } - - void renameTypes( Expression *expr ) { - renameTyVars( expr->result ); - } - } // namespace - - void referenceToRvalueConversion( Expression *& expr, Cost & cost ) { - if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) { - // cast away reference from expr - expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() ); - cost.incReference(); - } - } - - template< typename InputIterator, typename OutputIterator > - void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) { - while ( begin != end ) { - AlternativeFinder finder( indexer, env ); - finder.findWithAdjustment( *begin ); - // XXX either this - //Designators::fixDesignations( finder, (*begin++)->get_argName() ); - // or XXX this - begin++; - PRINT( - std::cerr << "findSubExprs" << std::endl; - printAlts( finder.alternatives, std::cerr ); - ) - *out++ = finder; - } - } - - AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ) - : indexer( indexer ), env( env ) { - } - - void AlternativeFinder::find( Expression *expr, ResolvMode mode ) { - PassVisitor finder( *this ); - expr->accept( finder ); - if ( mode.failFast && alternatives.empty() ) { - PRINT( - std::cerr << "No reasonable alternatives for expression " << expr << std::endl; - ) - SemanticError( expr, "No reasonable alternatives for expression " ); - } - if ( mode.prune ) { - // trim candidates just to those where the assertions resolve - // - necessary pre-requisite to pruning - AltList candidates; - std::list errors; - for ( unsigned i = 0; i < alternatives.size(); ++i ) { - resolveAssertions( alternatives[i], indexer, candidates, errors ); - } - // fail early if none such - if ( mode.failFast && candidates.empty() ) { - std::ostringstream stream; - stream << "No alternatives with satisfiable assertions for " << expr << "\n"; - // << "Alternatives with failing assertions are:\n"; - // printAlts( alternatives, stream, 1 ); - for ( const auto& err : errors ) { - stream << err; - } - SemanticError( expr->location, stream.str() ); - } - // reset alternatives - alternatives = std::move( candidates ); - } - if ( mode.prune ) { - auto oldsize = alternatives.size(); - PRINT( - std::cerr << "alternatives before prune:" << std::endl; - printAlts( alternatives, std::cerr ); - ) - AltList pruned; - pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); - if ( mode.failFast && pruned.empty() ) { - std::ostringstream stream; - AltList winners; - findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); - stream << "Cannot choose between " << winners.size() << " alternatives for expression\n"; - expr->print( stream ); - stream << " Alternatives are:\n"; - printAlts( winners, stream, 1 ); - SemanticError( expr->location, stream.str() ); - } - alternatives = std::move(pruned); - PRINT( - std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; - ) - PRINT( - std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; - ) - } - // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted - if ( mode.adjust ) { - for ( Alternative& i : alternatives ) { - adjustExprType( i.expr->get_result(), i.env, indexer ); - } - } - - // Central location to handle gcc extension keyword, etc. for all expression types. - for ( Alternative &iter: alternatives ) { - iter.expr->set_extension( expr->get_extension() ); - iter.expr->location = expr->location; - } // for - } - - void AlternativeFinder::findWithAdjustment( Expression *expr ) { - find( expr, ResolvMode::withAdjustment() ); - } - - void AlternativeFinder::findWithoutPrune( Expression * expr ) { - find( expr, ResolvMode::withoutPrune() ); - } - - void AlternativeFinder::maybeFind( Expression * expr ) { - find( expr, ResolvMode::withoutFailFast() ); - } - - void AlternativeFinder::Finder::addAnonConversions( const Alternative & alt ) { - // adds anonymous member interpretations whenever an aggregate value type is seen. - // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value - std::unique_ptr aggrExpr( alt.expr->clone() ); - alt.env.apply( aggrExpr->result ); - Type * aggrType = aggrExpr->result; - if ( dynamic_cast< ReferenceType * >( aggrType ) ) { - aggrType = aggrType->stripReferences(); - aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) ); - } - - if ( StructInstType * structInst = dynamic_cast< StructInstType* >( aggrExpr->result ) ) { - addAggMembers( structInst, aggrExpr.get(), alt, alt.cost+Cost::safe, "" ); - } else if ( UnionInstType * unionInst = dynamic_cast< UnionInstType* >( aggrExpr->result ) ) { - addAggMembers( unionInst, aggrExpr.get(), alt, alt.cost+Cost::safe, "" ); - } // if - } - - template< typename StructOrUnionType > - void AlternativeFinder::Finder::addAggMembers( StructOrUnionType * aggInst, Expression * expr, const Alternative& alt, const Cost &newCost, const std::string & name ) { - std::list< Declaration* > members; - aggInst->lookup( name, members ); - - for ( Declaration * decl : members ) { - if ( DeclarationWithType * dwt = dynamic_cast< DeclarationWithType* >( decl ) ) { - // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so - // can't construct in place and use vector::back - Alternative newAlt{ alt, new MemberExpr{ dwt, expr->clone() }, newCost }; - renameTypes( newAlt.expr ); - addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression. - alternatives.push_back( std::move(newAlt) ); - } else { - assert( false ); - } - } - } - - void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression * expr, const Alternative &alt, const Cost &newCost, Expression * member ) { - if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) { - // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning - auto val = constantExpr->intValue(); - std::string tmp; - if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { - alternatives.push_back( Alternative{ - alt, new TupleIndexExpr( expr->clone(), val ), newCost } ); - } // if - } // if - } - - void AlternativeFinder::Finder::postvisit( ApplicationExpr * applicationExpr ) { - alternatives.push_back( Alternative{ applicationExpr->clone(), env } ); - } - - Cost computeConversionCost( Type * actualType, Type * formalType, bool actualIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment & env ) { - PRINT( - std::cerr << std::endl << "converting "; - actualType->print( std::cerr, 8 ); - std::cerr << std::endl << " to "; - formalType->print( std::cerr, 8 ); - std::cerr << std::endl << "environment is: "; - env.print( std::cerr, 8 ); - std::cerr << std::endl; - ) - Cost convCost = conversionCost( actualType, formalType, actualIsLvalue, indexer, env ); - PRINT( - std::cerr << std::endl << "cost is " << convCost << std::endl; - ) - if ( convCost == Cost::infinity ) { - return convCost; - } - convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) ); - PRINT( - std::cerr << "cost with polycost is " << convCost << std::endl; - ) - return convCost; - } - - Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) { - Cost convCost = computeConversionCost( - actualExpr->result, formalType, actualExpr->get_lvalue(), indexer, env ); - - // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion. - // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this - // does not currently work for the reason stated below. - Cost tmpCost = convCost; - tmpCost.incPoly( -tmpCost.get_polyCost() ); - if ( tmpCost != Cost::zero ) { - Type *newType = formalType->clone(); - env.apply( newType ); - actualExpr = new CastExpr( actualExpr, newType ); - // xxx - SHOULD be able to resolve this cast, but at the moment pointers are not castable to zero_t, but are implicitly convertible. This is clearly - // inconsistent, once this is fixed it should be possible to resolve the cast. - // xxx - this isn't working, it appears because type1 (the formal type) is seen as widenable, but it shouldn't be, because this makes the conversion from DT* to DT* since commontype(zero_t, DT*) is DT*, rather than just nothing. - - // AlternativeFinder finder( indexer, env ); - // finder.findWithAdjustment( actualExpr ); - // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." ); - // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." ); - // Alternative & alt = finder.get_alternatives().front(); - // delete actualExpr; - // actualExpr = alt.expr->clone(); - } - return convCost; - } - - Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) { - ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr ); - PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result ); - FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base ); - - Cost convCost = Cost::zero; - std::list< DeclarationWithType* >& formals = function->parameters; - std::list< DeclarationWithType* >::iterator formal = formals.begin(); - std::list< Expression* >& actuals = appExpr->args; - - for ( Expression*& actualExpr : actuals ) { - Type * actualType = actualExpr->result; - PRINT( - std::cerr << "actual expression:" << std::endl; - actualExpr->print( std::cerr, 8 ); - std::cerr << "--- results are" << std::endl; - actualType->print( std::cerr, 8 ); - ) - if ( formal == formals.end() ) { - if ( function->isVarArgs ) { - convCost.incUnsafe(); - PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; ) - // convert reference-typed expressions to value-typed expressions - referenceToRvalueConversion( actualExpr, convCost ); - continue; - } else { - return Cost::infinity; - } - } - if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( actualExpr ) ) { - // default arguments should be free - don't include conversion cost. - // Unwrap them here because they are not relevant to the rest of the system. - actualExpr = def->expr; - ++formal; - continue; - } - // mark conversion cost to formal and also specialization cost of formal type - Type * formalType = (*formal)->get_type(); - convCost += computeExpressionConversionCost( actualExpr, formalType, indexer, alt.env ); - convCost.decSpec( specCost( formalType ) ); - ++formal; // can't be in for-loop update because of the continue - } - if ( formal != formals.end() ) { - return Cost::infinity; - } - - // specialization cost of return types can't be accounted for directly, it disables - // otherwise-identical calls, like this example based on auto-newline in the I/O lib: - // - // forall(otype OS) { - // void ?|?(OS&, int); // with newline - // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization - // } - - // mark type variable and specialization cost of forall clause - convCost.incVar( function->forall.size() ); - for ( TypeDecl* td : function->forall ) { - convCost.decSpec( td->assertions.size() ); - } - - return convCost; - } - - /// Adds type variables to the open variable set and marks their assertions - void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) { - for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { - unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar }; - for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->assertions.begin(); assert != (*tyvar)->assertions.end(); ++assert ) { - needAssertions[ *assert ].isUsed = true; - } - } - } - - /// Unique identifier for matching expression resolutions to their requesting expression (located in CandidateFinder.cpp) - extern UniqueId globalResnSlot; - - template< typename OutputIterator > - void AlternativeFinder::Finder::inferParameters( Alternative &newAlt, OutputIterator out ) { - // Set need bindings for any unbound assertions - UniqueId crntResnSlot = 0; // matching ID for this expression's assertions - for ( auto& assn : newAlt.need ) { - // skip already-matched assertions - if ( assn.info.resnSlot != 0 ) continue; - // assign slot for expression if needed - if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; } - // fix slot to assertion - assn.info.resnSlot = crntResnSlot; - } - // pair slot to expression - if ( crntResnSlot != 0 ) { newAlt.expr->resnSlots.push_back( crntResnSlot ); } - - // add to output list, assertion resolution is deferred - *out++ = newAlt; - } - - /// Gets a default value from an initializer, nullptr if not present - ConstantExpr* getDefaultValue( Initializer* init ) { - if ( SingleInit* si = dynamic_cast( init ) ) { - if ( CastExpr* ce = dynamic_cast( si->value ) ) { - return dynamic_cast( ce->arg ); - } else { - return dynamic_cast( si->value ); - } - } - return nullptr; - } - - /// State to iteratively build a match of parameter expressions to arguments - struct ArgPack { - std::size_t parent; ///< Index of parent pack - std::unique_ptr expr; ///< The argument stored here - Cost cost; ///< The cost of this argument - TypeEnvironment env; ///< Environment for this pack - AssertionSet need; ///< Assertions outstanding for this pack - AssertionSet have; ///< Assertions found for this pack - OpenVarSet openVars; ///< Open variables for this pack - unsigned nextArg; ///< Index of next argument in arguments list - unsigned tupleStart; ///< Number of tuples that start at this index - unsigned nextExpl; ///< Index of next exploded element - unsigned explAlt; ///< Index of alternative for nextExpl > 0 - - ArgPack() - : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), - tupleStart(0), nextExpl(0), explAlt(0) {} - - ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, - const OpenVarSet& openVars) - : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), - openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} - - ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, - AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, - unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0, - unsigned explAlt = 0 ) - : parent(parent), expr(expr->clone()), cost(cost), env(std::move(env)), need(std::move(need)), - have(std::move(have)), openVars(std::move(openVars)), nextArg(nextArg), tupleStart(tupleStart), - nextExpl(nextExpl), explAlt(explAlt) {} - - ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, - OpenVarSet&& openVars, unsigned nextArg, Cost added ) - : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), - env(std::move(env)), need(std::move(need)), have(std::move(have)), openVars(std::move(openVars)), - nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {} - - /// true iff this pack is in the middle of an exploded argument - bool hasExpl() const { return nextExpl > 0; } - - /// Gets the list of exploded alternatives for this pack - const ExplodedActual& getExpl( const ExplodedArgs_old& args ) const { - return args[nextArg-1][explAlt]; - } - - /// Ends a tuple expression, consolidating the appropriate actuals - void endTuple( const std::vector& packs ) { - // add all expressions in tuple to list, summing cost - std::list exprs; - const ArgPack* pack = this; - if ( expr ) { exprs.push_front( expr.release() ); } - while ( pack->tupleStart == 0 ) { - pack = &packs[pack->parent]; - exprs.push_front( pack->expr->clone() ); - cost += pack->cost; - } - // reset pack to appropriate tuple - expr.reset( new TupleExpr( exprs ) ); - tupleStart = pack->tupleStart - 1; - parent = pack->parent; - } - }; - - /// Instantiates an argument to match a formal, returns false if no results left - bool instantiateArgument( Type* formalType, Initializer* initializer, - const ExplodedArgs_old& args, std::vector& results, std::size_t& genStart, - const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { - if ( TupleType * tupleType = dynamic_cast( formalType ) ) { - // formalType is a TupleType - group actuals into a TupleExpr - ++nTuples; - for ( Type* type : *tupleType ) { - // xxx - dropping initializer changes behaviour from previous, but seems correct - // ^^^ need to handle the case where a tuple has a default argument - if ( ! instantiateArgument( - type, nullptr, args, results, genStart, indexer, nTuples ) ) - return false; - nTuples = 0; - } - // re-consititute tuples for final generation - for ( auto i = genStart; i < results.size(); ++i ) { - results[i].endTuple( results ); - } - return true; - } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) { - // formalType is a ttype, consumes all remaining arguments - // xxx - mixing default arguments with variadic?? - - // completed tuples; will be spliced to end of results to finish - std::vector finalResults{}; - - // iterate until all results completed - std::size_t genEnd; - ++nTuples; - do { - genEnd = results.size(); - - // add another argument to results - for ( std::size_t i = genStart; i < genEnd; ++i ) { - auto nextArg = results[i].nextArg; - - // use next element of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedActual& expl = results[i].getExpl( args ); - - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { - nextExpl = 0; - } - - results.emplace_back( - i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), - copy(results[i].need), copy(results[i].have), - copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl, - results[i].explAlt ); - - continue; - } - - // finish result when out of arguments - if ( nextArg >= args.size() ) { - ArgPack newResult{ - results[i].env, results[i].need, results[i].have, - results[i].openVars }; - newResult.nextArg = nextArg; - Type* argType; - - if ( nTuples > 0 || ! results[i].expr ) { - // first iteration or no expression to clone, - // push empty tuple expression - newResult.parent = i; - std::list emptyList; - newResult.expr.reset( new TupleExpr( emptyList ) ); - argType = newResult.expr->get_result(); - } else { - // clone result to collect tuple - newResult.parent = results[i].parent; - newResult.cost = results[i].cost; - newResult.tupleStart = results[i].tupleStart; - newResult.expr.reset( results[i].expr->clone() ); - argType = newResult.expr->get_result(); - - if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { - // the case where a ttype value is passed directly is special, - // e.g. for argument forwarding purposes - // xxx - what if passing multiple arguments, last of which is - // ttype? - // xxx - what would happen if unify was changed so that unifying - // tuple - // types flattened both before unifying lists? then pass in - // TupleType (ttype) below. - --newResult.tupleStart; - } else { - // collapse leftover arguments into tuple - newResult.endTuple( results ); - argType = newResult.expr->get_result(); - } - } - - // check unification for ttype before adding to final - if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, - newResult.openVars, indexer ) ) { - finalResults.push_back( std::move(newResult) ); - } - - continue; - } - - // add each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedActual& expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - TypeEnvironment env = results[i].env; - OpenVarSet openVars = results[i].openVars; - - env.addActual( expl.env, openVars ); - - // skip empty tuple arguments by (near-)cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move(env), copy(results[i].need), - copy(results[i].have), std::move(openVars), nextArg + 1, expl.cost ); - - continue; - } - - // add new result - results.emplace_back( - i, expl.exprs.front().get(), std::move(env), copy(results[i].need), - copy(results[i].have), std::move(openVars), nextArg + 1, - nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - - // reset for next round - genStart = genEnd; - nTuples = 0; - } while ( genEnd != results.size() ); - - // splice final results onto results - for ( std::size_t i = 0; i < finalResults.size(); ++i ) { - results.push_back( std::move(finalResults[i]) ); - } - return ! finalResults.empty(); - } - - // iterate each current subresult - std::size_t genEnd = results.size(); - for ( std::size_t i = genStart; i < genEnd; ++i ) { - auto nextArg = results[i].nextArg; - - // use remainder of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedActual& expl = results[i].getExpl( args ); - Expression* expr = expl.exprs[results[i].nextExpl].get(); - - TypeEnvironment env = results[i].env; - AssertionSet need = results[i].need, have = results[i].have; - OpenVarSet openVars = results[i].openVars; - - Type* actualType = expr->get_result(); - - PRINT( - std::cerr << "formal type is "; - formalType->print( std::cerr ); - std::cerr << std::endl << "actual type is "; - actualType->print( std::cerr ); - std::cerr << std::endl; - ) - - if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { - nextExpl = 0; - } - - results.emplace_back( - i, expr, std::move(env), std::move(need), std::move(have), std::move(openVars), nextArg, - nTuples, Cost::zero, nextExpl, results[i].explAlt ); - } - - continue; - } - - // use default initializers if out of arguments - if ( nextArg >= args.size() ) { - if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { - if ( Constant* cnst = dynamic_cast( cnstExpr->get_constant() ) ) { - TypeEnvironment env = results[i].env; - AssertionSet need = results[i].need, have = results[i].have; - OpenVarSet openVars = results[i].openVars; - - if ( unify( formalType, cnst->get_type(), env, need, have, openVars, - indexer ) ) { - results.emplace_back( - i, new DefaultArgExpr( cnstExpr ), std::move(env), std::move(need), std::move(have), - std::move(openVars), nextArg, nTuples ); - } - } - } - - continue; - } - - // Check each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedActual& expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - TypeEnvironment env = results[i].env; - AssertionSet need = results[i].need, have = results[i].have; - OpenVarSet openVars = results[i].openVars; - - env.addActual( expl.env, openVars ); - - // skip empty tuple arguments by (near-)cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move(env), std::move(need), std::move(have), std::move(openVars), - nextArg + 1, expl.cost ); - - continue; - } - - // consider only first exploded actual - Expression* expr = expl.exprs.front().get(); - Type* actualType = expr->result->clone(); - - PRINT( - std::cerr << "formal type is "; - formalType->print( std::cerr ); - std::cerr << std::endl << "actual type is "; - actualType->print( std::cerr ); - std::cerr << std::endl; - ) - - // attempt to unify types - if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { - // add new result - results.emplace_back( - i, expr, std::move(env), std::move(need), std::move(have), std::move(openVars), nextArg + 1, - nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - } - - // reset for next parameter - genStart = genEnd; - - return genEnd != results.size(); - } - - template - void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, ArgPack& result, - const std::vector& results, OutputIterator out ) { - ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); - // sum cost and accumulate actuals - std::list& args = appExpr->args; - Cost cost = func.cost; - const ArgPack* pack = &result; - while ( pack->expr ) { - args.push_front( pack->expr->clone() ); - cost += pack->cost; - pack = &results[pack->parent]; - } - // build and validate new alternative - Alternative newAlt{ appExpr, result.env, result.openVars, result.need, cost }; - PRINT( - std::cerr << "instantiate function success: " << appExpr << std::endl; - std::cerr << "need assertions:" << std::endl; - printAssertionSet( result.need, std::cerr, 8 ); - ) - inferParameters( newAlt, out ); - } - - template - void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func, - FunctionType *funcType, const ExplodedArgs_old &args, OutputIterator out ) { - OpenVarSet funcOpenVars; - AssertionSet funcNeed, funcHave; - TypeEnvironment funcEnv( func.env ); - makeUnifiableVars( funcType, funcOpenVars, funcNeed ); - // add all type variables as open variables now so that those not used in the parameter - // list are still considered open. - funcEnv.add( funcType->forall ); - - if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) { - // attempt to narrow based on expected target type - Type * returnType = funcType->returnVals.front()->get_type(); - if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, - indexer ) ) { - // unification failed, don't pursue this function alternative - return; - } - } - - // iteratively build matches, one parameter at a time - std::vector results; - results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); - std::size_t genStart = 0; - - for ( DeclarationWithType* formal : funcType->parameters ) { - ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); - if ( ! instantiateArgument( - obj->type, obj->init, args, results, genStart, indexer ) ) - return; - } - - if ( funcType->get_isVarArgs() ) { - // append any unused arguments to vararg pack - std::size_t genEnd; - do { - genEnd = results.size(); - - // iterate results - for ( std::size_t i = genStart; i < genEnd; ++i ) { - auto nextArg = results[i].nextArg; - - // use remainder of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedActual& expl = results[i].getExpl( args ); - - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { - nextExpl = 0; - } - - results.emplace_back( - i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), - copy(results[i].need), copy(results[i].have), - copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl, - results[i].explAlt ); - - continue; - } - - // finish result when out of arguments - if ( nextArg >= args.size() ) { - validateFunctionAlternative( func, results[i], results, out ); - - continue; - } - - // add each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedActual& expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - TypeEnvironment env = results[i].env; - OpenVarSet openVars = results[i].openVars; - - env.addActual( expl.env, openVars ); - - // skip empty tuple arguments by (near-)cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move(env), copy(results[i].need), - copy(results[i].have), std::move(openVars), nextArg + 1, expl.cost ); - - continue; - } - - // add new result - results.emplace_back( - i, expl.exprs.front().get(), std::move(env), copy(results[i].need), - copy(results[i].have), std::move(openVars), nextArg + 1, 0, - expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - - genStart = genEnd; - } while ( genEnd != results.size() ); - } else { - // filter out results that don't use all the arguments - for ( std::size_t i = genStart; i < results.size(); ++i ) { - ArgPack& result = results[i]; - if ( ! result.hasExpl() && result.nextArg >= args.size() ) { - validateFunctionAlternative( func, result, results, out ); - } - } - } - } - - void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) { - AlternativeFinder funcFinder( indexer, env ); - funcFinder.findWithAdjustment( untypedExpr->function ); - // if there are no function alternatives, then proceeding is a waste of time. - // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary. - if ( funcFinder.alternatives.empty() ) return; - - std::vector< AlternativeFinder > argAlternatives; - altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), - back_inserter( argAlternatives ) ); - - // take care of possible tuple assignments - // if not tuple assignment, assignment is taken care of as a normal function call - Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives ); - - // find function operators - static NameExpr *opExpr = new NameExpr( "?()" ); - AlternativeFinder funcOpFinder( indexer, env ); - // it's ok if there aren't any defined function ops - funcOpFinder.maybeFind( opExpr ); - PRINT( - std::cerr << "known function ops:" << std::endl; - printAlts( funcOpFinder.alternatives, std::cerr, 1 ); - ) - - // pre-explode arguments - ExplodedArgs_old argExpansions; - argExpansions.reserve( argAlternatives.size() ); - - for ( const AlternativeFinder& arg : argAlternatives ) { - argExpansions.emplace_back(); - auto& argE = argExpansions.back(); - // argE.reserve( arg.alternatives.size() ); - - for ( const Alternative& actual : arg ) { - argE.emplace_back( actual, indexer ); - } - } - - AltList candidates; - SemanticErrorException errors; - for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) { - try { - PRINT( - std::cerr << "working on alternative: " << std::endl; - func->print( std::cerr, 8 ); - ) - // check if the type is pointer to function - if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->result->stripReferences() ) ) { - if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->base ) ) { - Alternative newFunc( *func ); - referenceToRvalueConversion( newFunc.expr, newFunc.cost ); - makeFunctionAlternatives( newFunc, function, argExpansions, - std::back_inserter( candidates ) ); - } - } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) - if ( const EqvClass *eqvClass = func->env.lookup( typeInst->name ) ) { - if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) { - Alternative newFunc( *func ); - referenceToRvalueConversion( newFunc.expr, newFunc.cost ); - makeFunctionAlternatives( newFunc, function, argExpansions, - std::back_inserter( candidates ) ); - } // if - } // if - } - } catch ( SemanticErrorException &e ) { - errors.append( e ); - } - } // for - - // try each function operator ?() with each function alternative - if ( ! funcOpFinder.alternatives.empty() ) { - // add exploded function alternatives to front of argument list - std::vector funcE; - funcE.reserve( funcFinder.alternatives.size() ); - for ( const Alternative& actual : funcFinder ) { - funcE.emplace_back( actual, indexer ); - } - argExpansions.insert( argExpansions.begin(), std::move(funcE) ); - - for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); - funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { - try { - // check if type is a pointer to function - if ( PointerType* pointer = dynamic_cast( - funcOp->expr->result->stripReferences() ) ) { - if ( FunctionType* function = - dynamic_cast( pointer->base ) ) { - Alternative newFunc( *funcOp ); - referenceToRvalueConversion( newFunc.expr, newFunc.cost ); - makeFunctionAlternatives( newFunc, function, argExpansions, - std::back_inserter( candidates ) ); - } - } - } catch ( SemanticErrorException &e ) { - errors.append( e ); - } - } - } - - // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions - if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; } - - // compute conversionsion costs - for ( Alternative& withFunc : candidates ) { - Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); - - PRINT( - ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); - PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result ); - FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base ); - std::cerr << "Case +++++++++++++ " << appExpr->function << std::endl; - std::cerr << "formals are:" << std::endl; - printAll( function->parameters, std::cerr, 8 ); - std::cerr << "actuals are:" << std::endl; - printAll( appExpr->args, std::cerr, 8 ); - std::cerr << "bindings are:" << std::endl; - withFunc.env.print( std::cerr, 8 ); - std::cerr << "cost is: " << withFunc.cost << std::endl; - std::cerr << "cost of conversion is:" << cvtCost << std::endl; - ) - if ( cvtCost != Cost::infinity ) { - withFunc.cvtCost = cvtCost; - alternatives.push_back( withFunc ); - } // if - } // for - - candidates = std::move(alternatives); - - // use a new list so that alternatives are not examined by addAnonConversions twice. - AltList winners; - findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); - - // function may return struct or union value, in which case we need to add alternatives - // for implicit conversions to each of the anonymous members, must happen after findMinCost - // since anon conversions are never the cheapest expression - for ( const Alternative & alt : winners ) { - addAnonConversions( alt ); - } - spliceBegin( alternatives, winners ); - - if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { - // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a - // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example, - // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t ); - // const char * x = "hello world"; - // unsigned char ch = x[0]; - // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified - // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should - // fix this issue in a more robust way. - targetType = nullptr; - postvisit( untypedExpr ); - } - } - - bool isLvalue( Expression *expr ) { - // xxx - recurse into tuples? - return expr->result && ( expr->get_lvalue() || dynamic_cast< ReferenceType * >( expr->result ) ); - } - - void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) { - AlternativeFinder finder( indexer, env ); - finder.find( addressExpr->get_arg() ); - for ( Alternative& alt : finder.alternatives ) { - if ( isLvalue( alt.expr ) ) { - alternatives.push_back( - Alternative{ alt, new AddressExpr( alt.expr->clone() ), alt.cost } ); - } // if - } // for - } - - void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) { - alternatives.push_back( Alternative{ expr->clone(), env } ); - } - - Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) { - if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast( toType ) ) { - // Argument expression is a tuple and the target type is not void and not a reference type. - // Cast each member of the tuple to its corresponding target type, producing the tuple of those - // cast expressions. If there are more components of the tuple than components in the target type, - // then excess components do not come out in the result expression (but UniqueExprs ensure that - // side effects will still be done). - if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) { - // expressions which may contain side effects require a single unique instance of the expression. - argExpr = new UniqueExpr( argExpr ); - } - std::list< Expression * > componentExprs; - for ( unsigned int i = 0; i < toType->size(); i++ ) { - // cast each component - TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i ); - componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) ); - } - delete argExpr; - assert( componentExprs.size() > 0 ); - // produce the tuple of casts - return new TupleExpr( componentExprs ); - } else { - // handle normally - CastExpr * ret = new CastExpr( argExpr, toType->clone() ); - ret->isGenerated = isGenerated; - return ret; - } - } - - void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) { - Type *& toType = castExpr->get_result(); - assert( toType ); - toType = resolveTypeof( toType, indexer ); - assert(!dynamic_cast(toType)); - SymTab::validateType( toType, &indexer ); - adjustExprType( toType, env, indexer ); - - AlternativeFinder finder( indexer, env ); - finder.targetType = toType; - finder.findWithAdjustment( castExpr->arg ); - - AltList candidates; - for ( Alternative & alt : finder.alternatives ) { - AssertionSet needAssertions( alt.need.begin(), alt.need.end() ); - AssertionSet haveAssertions; - OpenVarSet openVars{ alt.openVars }; - - alt.env.extractOpenVars( openVars ); - - // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a - // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results - // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast - // to. - int discardedValues = alt.expr->result->size() - castExpr->result->size(); - if ( discardedValues < 0 ) continue; - // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not - // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) - // unification run for side-effects - unify( castExpr->result, alt.expr->result, alt.env, needAssertions, - haveAssertions, openVars, indexer ); - Cost thisCost = - castExpr->isGenerated - ? conversionCost( alt.expr->result, castExpr->result, alt.expr->get_lvalue(), indexer, alt.env ) - : castCost( alt.expr->result, castExpr->result, alt.expr->get_lvalue(), indexer, alt.env ); - PRINT( - std::cerr << "working on cast with result: " << castExpr->result << std::endl; - std::cerr << "and expr type: " << alt.expr->result << std::endl; - std::cerr << "env: " << alt.env << std::endl; - ) - if ( thisCost != Cost::infinity ) { - PRINT( - std::cerr << "has finite cost." << std::endl; - ) - // count one safe conversion for each value that is thrown away - thisCost.incSafe( discardedValues ); - Alternative newAlt{ - restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), - alt.env, openVars, needAssertions, alt.cost, alt.cost + thisCost }; - inferParameters( newAlt, back_inserter( candidates ) ); - } // if - } // for - - // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the - // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice - // selects first based on argument cost, then on conversion cost. - AltList minArgCost; - findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); - findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); - } - - void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) { - assertf( castExpr->get_result(), "Implicit virtual cast targets not yet supported." ); - AlternativeFinder finder( indexer, env ); - // don't prune here, since it's guaranteed all alternatives will have the same type - finder.findWithoutPrune( castExpr->get_arg() ); - for ( Alternative & alt : finder.alternatives ) { - alternatives.push_back( Alternative{ - alt, new VirtualCastExpr{ alt.expr->clone(), castExpr->get_result()->clone() }, - alt.cost } ); - } - } - - void AlternativeFinder::Finder::postvisit( KeywordCastExpr * castExpr ) { - assertf( castExpr->get_result(), "Cast target should have been set in Validate." ); - auto ref = dynamic_cast(castExpr->get_result()); - assert(ref); - auto inst = dynamic_cast(ref->base); - assert(inst); - auto target = inst->baseStruct; - - AlternativeFinder finder( indexer, env ); - - auto pick_alternatives = [target, this](AltList & found, bool expect_ref) { - for(auto & alt : found) { - Type * expr = alt.expr->get_result(); - if(expect_ref) { - auto res = dynamic_cast(expr); - if(!res) { continue; } - expr = res->base; - } - - if(auto insttype = dynamic_cast(expr)) { - auto td = alt.env.lookup(insttype->name); - if(!td) { continue; } - expr = td->type; - } - - if(auto base = dynamic_cast(expr)) { - if(base->baseStruct == target) { - alternatives.push_back( - std::move(alt) - ); - } - } - } - }; - - try { - // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd - // Clone is purely for memory management - std::unique_ptr tech1 { new UntypedMemberExpr(new NameExpr(castExpr->concrete_target.field), castExpr->arg->clone()) }; - - // don't prune here, since it's guaranteed all alternatives will have the same type - finder.findWithoutPrune( tech1.get() ); - pick_alternatives(finder.alternatives, false); - - return; - } catch(SemanticErrorException & ) {} - - // Fallback : turn (thread&)X into (thread$&)get_thread(X) - std::unique_ptr fallback { UntypedExpr::createDeref( new UntypedExpr(new NameExpr(castExpr->concrete_target.getter), { castExpr->arg->clone() })) }; - // don't prune here, since it's guaranteed all alternatives will have the same type - finder.findWithoutPrune( fallback.get() ); - - pick_alternatives(finder.alternatives, true); - - // Whatever happens here, we have no more fallbacks - } - - namespace { - /// Gets name from untyped member expression (member must be NameExpr) - const std::string& get_member_name( UntypedMemberExpr *memberExpr ) { - if ( dynamic_cast< ConstantExpr * >( memberExpr->get_member() ) ) { - SemanticError( memberExpr, "Indexed access to struct fields unsupported: " ); - } // if - NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() ); - assert( nameExpr ); - return nameExpr->get_name(); - } - } - - void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) { - AlternativeFinder funcFinder( indexer, env ); - funcFinder.findWithAdjustment( memberExpr->get_aggregate() ); - for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) { - // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value - Cost cost = agg->cost; - Expression * aggrExpr = agg->expr->clone(); - referenceToRvalueConversion( aggrExpr, cost ); - std::unique_ptr guard( aggrExpr ); - - // find member of the given type - if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) { - addAggMembers( structInst, aggrExpr, *agg, cost, get_member_name(memberExpr) ); - } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) { - addAggMembers( unionInst, aggrExpr, *agg, cost, get_member_name(memberExpr) ); - } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) { - addTupleMembers( tupleType, aggrExpr, *agg, cost, memberExpr->get_member() ); - } // if - } // for - } - - void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) { - alternatives.push_back( Alternative{ memberExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) { - std::list< SymTab::Indexer::IdData > declList; - indexer.lookupId( nameExpr->name, declList ); - PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) - for ( auto & data : declList ) { - Cost cost = Cost::zero; - Expression * newExpr = data.combine( cost ); - - // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so - // can't construct in place and use vector::back - Alternative newAlt{ newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost }; - PRINT( - std::cerr << "decl is "; - data.id->print( std::cerr ); - std::cerr << std::endl; - std::cerr << "newExpr is "; - newExpr->print( std::cerr ); - std::cerr << std::endl; - ) - renameTypes( newAlt.expr ); - addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression. - alternatives.push_back( std::move(newAlt) ); - } // for - } - - void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) { - // not sufficient to clone here, because variable's type may have changed - // since the VariableExpr was originally created. - alternatives.push_back( Alternative{ new VariableExpr{ variableExpr->var }, env } ); - } - - void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) { - alternatives.push_back( Alternative{ constantExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) { - if ( sizeofExpr->get_isType() ) { - Type * newType = sizeofExpr->get_type()->clone(); - alternatives.push_back( Alternative{ - new SizeofExpr{ resolveTypeof( newType, indexer ) }, env } ); - } else { - // find all alternatives for the argument to sizeof - AlternativeFinder finder( indexer, env ); - finder.find( sizeofExpr->get_expr() ); - // find the lowest cost alternative among the alternatives, otherwise ambiguous - AltList winners; - findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); - if ( winners.size() != 1 ) { - SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " ); - } // if - // return the lowest cost alternative for the argument - Alternative &choice = winners.front(); - referenceToRvalueConversion( choice.expr, choice.cost ); - alternatives.push_back( Alternative{ - choice, new SizeofExpr( choice.expr->clone() ), Cost::zero } ); - } // if - } - - void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) { - if ( alignofExpr->get_isType() ) { - Type * newType = alignofExpr->get_type()->clone(); - alternatives.push_back( Alternative{ - new AlignofExpr{ resolveTypeof( newType, indexer ) }, env } ); - } else { - // find all alternatives for the argument to sizeof - AlternativeFinder finder( indexer, env ); - finder.find( alignofExpr->get_expr() ); - // find the lowest cost alternative among the alternatives, otherwise ambiguous - AltList winners; - findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); - if ( winners.size() != 1 ) { - SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " ); - } // if - // return the lowest cost alternative for the argument - Alternative &choice = winners.front(); - referenceToRvalueConversion( choice.expr, choice.cost ); - alternatives.push_back( Alternative{ - choice, new AlignofExpr{ choice.expr->clone() }, Cost::zero } ); - } // if - } - - template< typename StructOrUnionType > - void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) { - std::list< Declaration* > members; - aggInst->lookup( name, members ); - for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) { - if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) { - alternatives.push_back( Alternative{ - new OffsetofExpr{ aggInst->clone(), dwt }, env } ); - renameTypes( alternatives.back().expr ); - } else { - assert( false ); - } - } - } - - void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) { - AlternativeFinder funcFinder( indexer, env ); - // xxx - resolveTypeof? - if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) { - addOffsetof( structInst, offsetofExpr->member ); - } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) { - addOffsetof( unionInst, offsetofExpr->member ); - } - } - - void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) { - alternatives.push_back( Alternative{ offsetofExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) { - alternatives.push_back( Alternative{ offsetPackExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( LogicalExpr * logicalExpr ) { - AlternativeFinder firstFinder( indexer, env ); - firstFinder.findWithAdjustment( logicalExpr->get_arg1() ); - if ( firstFinder.alternatives.empty() ) return; - AlternativeFinder secondFinder( indexer, env ); - secondFinder.findWithAdjustment( logicalExpr->get_arg2() ); - if ( secondFinder.alternatives.empty() ) return; - for ( const Alternative & first : firstFinder.alternatives ) { - for ( const Alternative & second : secondFinder.alternatives ) { - TypeEnvironment compositeEnv{ first.env }; - compositeEnv.simpleCombine( second.env ); - OpenVarSet openVars{ first.openVars }; - mergeOpenVars( openVars, second.openVars ); - AssertionSet need; - cloneAll( first.need, need ); - cloneAll( second.need, need ); - - LogicalExpr *newExpr = new LogicalExpr{ - first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() }; - alternatives.push_back( Alternative{ - newExpr, std::move(compositeEnv), std::move(openVars), - AssertionList( need.begin(), need.end() ), first.cost + second.cost } ); - } - } - } - - void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) { - // find alternatives for condition - AlternativeFinder firstFinder( indexer, env ); - firstFinder.findWithAdjustment( conditionalExpr->arg1 ); - if ( firstFinder.alternatives.empty() ) return; - // find alternatives for true expression - AlternativeFinder secondFinder( indexer, env ); - secondFinder.findWithAdjustment( conditionalExpr->arg2 ); - if ( secondFinder.alternatives.empty() ) return; - // find alterantives for false expression - AlternativeFinder thirdFinder( indexer, env ); - thirdFinder.findWithAdjustment( conditionalExpr->arg3 ); - if ( thirdFinder.alternatives.empty() ) return; - for ( const Alternative & first : firstFinder.alternatives ) { - for ( const Alternative & second : secondFinder.alternatives ) { - for ( const Alternative & third : thirdFinder.alternatives ) { - TypeEnvironment compositeEnv{ first.env }; - compositeEnv.simpleCombine( second.env ); - compositeEnv.simpleCombine( third.env ); - OpenVarSet openVars{ first.openVars }; - mergeOpenVars( openVars, second.openVars ); - mergeOpenVars( openVars, third.openVars ); - AssertionSet need; - cloneAll( first.need, need ); - cloneAll( second.need, need ); - cloneAll( third.need, need ); - AssertionSet have; - - // unify true and false types, then infer parameters to produce new alternatives - Type* commonType = nullptr; - if ( unify( second.expr->result, third.expr->result, compositeEnv, - need, have, openVars, indexer, commonType ) ) { - ConditionalExpr *newExpr = new ConditionalExpr{ - first.expr->clone(), second.expr->clone(), third.expr->clone() }; - newExpr->result = commonType ? commonType : second.expr->result->clone(); - // convert both options to the conditional result type - Cost cost = first.cost + second.cost + third.cost; - cost += computeExpressionConversionCost( - newExpr->arg2, newExpr->result, indexer, compositeEnv ); - cost += computeExpressionConversionCost( - newExpr->arg3, newExpr->result, indexer, compositeEnv ); - // output alternative - Alternative newAlt{ - newExpr, std::move(compositeEnv), std::move(openVars), - AssertionList( need.begin(), need.end() ), cost }; - inferParameters( newAlt, back_inserter( alternatives ) ); - } // if - } // for - } // for - } // for - } - - void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) { - TypeEnvironment newEnv( env ); - Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv ); - AlternativeFinder secondFinder( indexer, newEnv ); - secondFinder.findWithAdjustment( commaExpr->get_arg2() ); - for ( const Alternative & alt : secondFinder.alternatives ) { - alternatives.push_back( Alternative{ - alt, new CommaExpr{ newFirstArg->clone(), alt.expr->clone() }, alt.cost } ); - } // for - delete newFirstArg; - } - - void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) { - // resolve low and high, accept alternatives whose low and high types unify - AlternativeFinder firstFinder( indexer, env ); - firstFinder.findWithAdjustment( rangeExpr->low ); - if ( firstFinder.alternatives.empty() ) return; - AlternativeFinder secondFinder( indexer, env ); - secondFinder.findWithAdjustment( rangeExpr->high ); - if ( secondFinder.alternatives.empty() ) return; - for ( const Alternative & first : firstFinder.alternatives ) { - for ( const Alternative & second : secondFinder.alternatives ) { - TypeEnvironment compositeEnv{ first.env }; - compositeEnv.simpleCombine( second.env ); - OpenVarSet openVars{ first.openVars }; - mergeOpenVars( openVars, second.openVars ); - AssertionSet need; - cloneAll( first.need, need ); - cloneAll( second.need, need ); - AssertionSet have; - - Type* commonType = nullptr; - if ( unify( first.expr->result, second.expr->result, compositeEnv, need, have, - openVars, indexer, commonType ) ) { - RangeExpr * newExpr = - new RangeExpr{ first.expr->clone(), second.expr->clone() }; - newExpr->result = commonType ? commonType : first.expr->result->clone(); - Alternative newAlt{ - newExpr, std::move(compositeEnv), std::move(openVars), - AssertionList( need.begin(), need.end() ), first.cost + second.cost }; - inferParameters( newAlt, back_inserter( alternatives ) ); - } // if - } // for - } // for - } - - void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) { - std::vector< AlternativeFinder > subExprAlternatives; - altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), - back_inserter( subExprAlternatives ) ); - std::vector< AltList > possibilities; - combos( subExprAlternatives.begin(), subExprAlternatives.end(), - back_inserter( possibilities ) ); - for ( const AltList& alts : possibilities ) { - std::list< Expression * > exprs; - makeExprList( alts, exprs ); - - TypeEnvironment compositeEnv; - OpenVarSet openVars; - AssertionSet need; - for ( const Alternative& alt : alts ) { - compositeEnv.simpleCombine( alt.env ); - mergeOpenVars( openVars, alt.openVars ); - cloneAll( alt.need, need ); - } - - alternatives.push_back( Alternative{ - new TupleExpr{ exprs }, std::move(compositeEnv), std::move(openVars), - AssertionList( need.begin(), need.end() ), sumCost( alts ) } ); - } // for - } - - void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) { - alternatives.push_back( Alternative{ tupleExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) { - alternatives.push_back( Alternative{ impCpCtorExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) { - AlternativeFinder finder( indexer, env ); - // don't prune here, since it's guaranteed all alternatives will have the same type - // (giving the alternatives different types is half of the point of ConstructorExpr nodes) - finder.findWithoutPrune( ctorExpr->get_callExpr() ); - for ( Alternative & alt : finder.alternatives ) { - alternatives.push_back( Alternative{ - alt, new ConstructorExpr( alt.expr->clone() ), alt.cost } ); - } - } - - void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) { - alternatives.push_back( Alternative{ tupleExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) { - alternatives.push_back( Alternative{ tupleAssignExpr->clone(), env } ); - } - - void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) { - AlternativeFinder finder( indexer, env ); - finder.findWithAdjustment( unqExpr->get_expr() ); - for ( Alternative & alt : finder.alternatives ) { - // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked" - UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() ); - alternatives.push_back( Alternative{ alt, newUnqExpr, alt.cost } ); - } - } - - void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) { - StmtExpr * newStmtExpr = stmtExpr->clone(); - ResolvExpr::resolveStmtExpr( newStmtExpr, indexer ); - // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr... - alternatives.push_back( Alternative{ newStmtExpr, env } ); - } - - void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) { - // handle each option like a cast - AltList candidates; - PRINT( - std::cerr << "untyped init expr: " << initExpr << std::endl; - ) - // O(N^2) checks of d-types with e-types - for ( InitAlternative & initAlt : initExpr->get_initAlts() ) { - Type * toType = resolveTypeof( initAlt.type->clone(), indexer ); - SymTab::validateType( toType, &indexer ); - adjustExprType( toType, env, indexer ); - // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else - // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving - // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal. - AlternativeFinder finder( indexer, env ); - finder.targetType = toType; - finder.findWithAdjustment( initExpr->expr ); - for ( Alternative & alt : finder.get_alternatives() ) { - TypeEnvironment newEnv( alt.env ); - AssertionSet need; - cloneAll( alt.need, need ); - AssertionSet have; - OpenVarSet openVars( alt.openVars ); - // xxx - find things in env that don't have a "representative type" and claim - // those are open vars? - PRINT( - std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; - ) - // It's possible that a cast can throw away some values in a multiply-valued - // expression. (An example is a cast-to-void, which casts from one value to - // zero.) Figure out the prefix of the subexpression results that are cast - // directly. The candidate is invalid if it has fewer results than there are - // types to cast to. - int discardedValues = alt.expr->result->size() - toType->size(); - if ( discardedValues < 0 ) continue; - // xxx - may need to go into tuple types and extract relevant types and use - // unifyList. Note that currently, this does not allow casting a tuple to an - // atomic type (e.g. (int)([1, 2, 3])) - - // unification run for side-effects - bool canUnify = unify( toType, alt.expr->result, newEnv, need, have, openVars, indexer ); - (void) canUnify; - // xxx - do some inspecting on this line... why isn't result bound to initAlt.type? - - Cost thisCost = computeConversionCost( alt.expr->result, toType, alt.expr->get_lvalue(), - indexer, newEnv ); - - PRINT( - Cost legacyCost = castCost( alt.expr->result, toType, alt.expr->get_lvalue(), - indexer, newEnv ); - std::cerr << "Considering initialization:"; - std::cerr << std::endl << " FROM: "; alt.expr->result->print(std::cerr); - std::cerr << std::endl << " TO: "; toType ->print(std::cerr); - std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed"); - std::cerr << std::endl << " Legacy cost " << legacyCost; - std::cerr << std::endl << " New cost " << thisCost; - std::cerr << std::endl; - ) - - if ( thisCost != Cost::infinity ) { - // count one safe conversion for each value that is thrown away - thisCost.incSafe( discardedValues ); - Alternative newAlt{ - new InitExpr{ - restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() }, - std::move(newEnv), std::move(openVars), - AssertionList( need.begin(), need.end() ), alt.cost, thisCost }; - inferParameters( newAlt, back_inserter( candidates ) ); - } - } - } - - // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the - // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice - // selects first based on argument cost, then on conversion cost. - AltList minArgCost; - findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); - findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); - } - - void AlternativeFinder::Finder::postvisit( InitExpr * ) { - assertf( false, "AlternativeFinder should never see a resolved InitExpr." ); - } - - void AlternativeFinder::Finder::postvisit( DeletedExpr * ) { - assertf( false, "AlternativeFinder should never see a DeletedExpr." ); - } - - void AlternativeFinder::Finder::postvisit( GenericExpr * ) { - assertf( false, "_Generic is not yet supported." ); - } -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,150 +1,0 @@ -// -// 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. -// -// AlternativeFinder.h -- -// -// Author : Richard C. Bilson -// Created On : Sat May 16 23:56:12 2015 -// Last Modified By : Aaron B. Moss -// Last Modified On : Fri Oct -5 10:01:00 2018 -// Update Count : 5 -// - -#pragma once - -#include // for copy -#include // for list -#include // for string - -#include "Alternative.h" // for AltList, Alternative -#include "ExplodedActual.h" // for ExplodedActual -#include "ResolvExpr/Cost.h" // for Cost, Cost::infinity -#include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet -#include "ResolvMode.h" // for ResolvMode -#include "SynTree/Visitor.h" // for Visitor -#include "SynTree/SynTree.h" // for Visitor Nodes - -namespace SymTab { -class Indexer; -} // namespace SymTab - -namespace ResolvExpr { - struct ArgPack; - - Cost computeConversionCost( Type * actualType, Type * formalType, bool actualIsLvalue, - const SymTab::Indexer & indexer, const TypeEnvironment & env ); - - void referenceToRvalueConversion( Expression *& expr, Cost & cost ); - - /// First index is which argument, second index is which alternative for that argument, - /// third index is which exploded element of that alternative - using ExplodedArgs_old = std::vector< std::vector< ExplodedActual > >; - - class AlternativeFinder { - public: - AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ); - - AlternativeFinder( const AlternativeFinder& o ) - : indexer(o.indexer), alternatives(o.alternatives), env(o.env), - targetType(o.targetType) {} - - AlternativeFinder( AlternativeFinder&& o ) - : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env), - targetType(o.targetType) {} - - AlternativeFinder& operator= ( const AlternativeFinder& o ) { - if (&o == this) return *this; - - // horrific nasty hack to rebind references... - alternatives.~AltList(); - new(this) AlternativeFinder(o); - return *this; - } - - AlternativeFinder& operator= ( AlternativeFinder&& o ) { - if (&o == this) return *this; - - // horrific nasty hack to rebind references... - alternatives.~AltList(); - new(this) AlternativeFinder(std::move(o)); - return *this; - } - - void find( Expression *expr, ResolvMode mode = ResolvMode{} ); - /// Calls find with the adjust flag set; adjustment turns array and function types into equivalent pointer types - void findWithAdjustment( Expression *expr ); - /// Calls find with the adjust flag set and prune flag unset; pruning ensures there is at most one alternative per result type - void findWithoutPrune( Expression *expr ); - /// Calls find with the adjust and prune flags set, failFast flags unset; fail fast ensures that there is at least one resulting alternative - void maybeFind( Expression *expr ); - AltList &get_alternatives() { return alternatives; } - - // make this look like an STL container so that we can apply generic algorithms - typedef Alternative value_type; - typedef AltList::iterator iterator; - typedef AltList::const_iterator const_iterator; - AltList::iterator begin() { return alternatives.begin(); } - AltList::iterator end() { return alternatives.end(); } - AltList::const_iterator begin() const { return alternatives.begin(); } - AltList::const_iterator end() const { return alternatives.end(); } - - const SymTab::Indexer &get_indexer() const { return indexer; } - const TypeEnvironment &get_environ() const { return env; } - - /// Runs a new alternative finder on each element in [begin, end) - /// and writes each alternative finder to out. - template< typename InputIterator, typename OutputIterator > - void findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ); - private: - struct Finder; - const SymTab::Indexer &indexer; - AltList alternatives; - const TypeEnvironment &env; - Type * targetType = nullptr; - }; // AlternativeFinder - - Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ); - - template< typename InputIterator, typename OutputIterator > - void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) { - AltList alternatives; - - // select the alternatives that have the minimum parameter cost - Cost minCost = Cost::infinity; - for ( InputIterator i = begin; i != end; ++i ) { - if ( i->cost < minCost ) { - minCost = i->cost; - i->cost = i->cvtCost; - alternatives.clear(); - alternatives.push_back( *i ); - } else if ( i->cost == minCost ) { - i->cost = i->cvtCost; - alternatives.push_back( *i ); - } - } - std::copy( alternatives.begin(), alternatives.end(), out ); - } - - Cost sumCost( const AltList &in ); - void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ); - - /// Adds type variables to the open variable set and marks their assertions - void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ); - - template< typename InputIterator > - void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) { - while ( begin != end ) { - result.simpleCombine( (*begin++).env ); - } - } - -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/AlternativePrinter.cc =================================================================== --- src/ResolvExpr/AlternativePrinter.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,49 +1,0 @@ -// -// 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. -// -// AlternativePrinter.cc -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 06:53:19 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sun May 17 06:55:05 2015 -// Update Count : 2 -// - -#include "AlternativePrinter.h" - -#include // for _List_const_iterator, list<>... - -#include "Alternative.h" // for AltList, Alternative -#include "AlternativeFinder.h" // for AlternativeFinder -#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment -#include "SynTree/Expression.h" // for Expression -#include "SynTree/Statement.h" // for ExprStmt -#include "SynTree/Type.h" // for Type - -namespace ResolvExpr { - AlternativePrinter::AlternativePrinter( std::ostream &os ) : os( os ) {} - - void AlternativePrinter::postvisit( ExprStmt *exprStmt ) { - TypeEnvironment env; - AlternativeFinder finder( indexer, env ); - finder.findWithAdjustment( exprStmt->get_expr() ); - int count = 1; - os << "There are " << finder.get_alternatives().size() << " alternatives" << std::endl; - for ( AltList::const_iterator i = finder.get_alternatives().begin(); i != finder.get_alternatives().end(); ++i ) { - os << "Alternative " << count++ << " ==============" << std::endl; - i->expr->get_result()->print( os ); - // i->print( os ); - os << std::endl; - } // for - } // AlternativePrinter::visit -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/AlternativePrinter.h =================================================================== --- src/ResolvExpr/AlternativePrinter.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,39 +1,0 @@ -// -// 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. -// -// AlternativePrinter.h -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 06:55:43 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:37:09 2017 -// Update Count : 4 -// - -#pragma once - -#include // for ostream - -#include "Common/PassVisitor.h" - -class ExprStmt; - -namespace ResolvExpr { - class AlternativePrinter final : public WithIndexer { - public: - AlternativePrinter( std::ostream &os ); - - void postvisit( ExprStmt *exprStmt ); - private: - std::ostream &os; - }; -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/CastCost.cc =================================================================== --- src/ResolvExpr/CastCost.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/CastCost.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -26,10 +26,6 @@ #include "ResolvExpr/ConversionCost.h" // for conversionCost #include "ResolvExpr/PtrsCastable.hpp" // for ptrsCastable -#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, EqvClass #include "ResolvExpr/typeops.h" // for ptrsCastable #include "ResolvExpr/Unify.h" // for typesCompatibleIgnoreQualifiers -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl -#include "SynTree/Type.h" // for PointerType, Type, TypeInstType #if 0 @@ -40,104 +36,4 @@ namespace ResolvExpr { - struct CastCost_old : public ConversionCost { - public: - CastCost_old( const Type * dest, bool srcIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc ); - - using ConversionCost::previsit; - using ConversionCost::postvisit; - void postvisit( const BasicType * basicType ); - void postvisit( const PointerType * pointerType ); - }; - - Cost castCost( const Type * src, const Type * dest, bool srcIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment &env ) { - if ( const TypeInstType * destAsTypeInst = dynamic_cast< const TypeInstType * >( dest ) ) { - if ( const EqvClass * eqvClass = env.lookup( destAsTypeInst->name ) ) { - if ( eqvClass->type ) { - return castCost( src, eqvClass->type, srcIsLvalue, indexer, env ); - } else { - return Cost::infinity; - } - } else if ( const NamedTypeDecl * namedType = indexer.lookupType( destAsTypeInst->name ) ) { - // all typedefs should be gone by this point - const TypeDecl * type = strict_dynamic_cast< const TypeDecl * >( namedType ); - if ( type->base ) { - return castCost( src, type->base, srcIsLvalue, indexer, env ) + Cost::safe; - } // if - } // if - } // if - - PRINT( - std::cerr << "castCost ::: src is "; - src->print( std::cerr ); - std::cerr << std::endl << "dest is "; - dest->print( std::cerr ); - std::cerr << std::endl << "env is" << std::endl; - env.print( std::cerr, 8 ); - ) - - if ( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) { - PRINT( std::cerr << "compatible!" << std::endl; ) - return Cost::zero; - } else if ( dynamic_cast< const VoidType * >( dest ) ) { - return Cost::safe; - } else if ( const ReferenceType * refType = dynamic_cast< const ReferenceType * > ( dest ) ) { - PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; ) - return convertToReferenceCost( src, refType, srcIsLvalue, indexer, env, [](const Type * t1, const Type * t2, const SymTab::Indexer & indexer, const TypeEnvironment & env ) { - return ptrsCastable( t1, t2, env, indexer ); - }); - } else { - PassVisitor converter( - dest, srcIsLvalue, indexer, env, - (Cost (*)( const Type *, const Type *, bool, const SymTab::Indexer &, const TypeEnvironment & )) - castCost ); - src->accept( converter ); - if ( converter.pass.get_cost() == Cost::infinity ) { - return Cost::infinity; - } else { - // xxx - why are we adding cost 0 here? - return converter.pass.get_cost() + Cost::zero; - } // if - } // if - } - - CastCost_old::CastCost_old( const Type * dest, bool srcIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc ) - : ConversionCost( dest, srcIsLvalue, indexer, env, costFunc ) { - } - - void CastCost_old::postvisit( const BasicType * basicType ) { - const PointerType * destAsPointer = dynamic_cast< const PointerType * >( dest ); - if ( destAsPointer && basicType->isInteger() ) { - // necessary for, e.g. unsigned long => void * - cost = Cost::unsafe; - } else { - cost = conversionCost( basicType, dest, srcIsLvalue, indexer, env ); - } // if - } - - void CastCost_old::postvisit( const PointerType * pointerType ) { - if ( const PointerType * destAsPtr = dynamic_cast< const PointerType * >( dest ) ) { - if ( pointerType->tq <= destAsPtr->tq && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) { - cost = Cost::safe; - } else { - TypeEnvironment newEnv( env ); - newEnv.add( pointerType->forall ); - newEnv.add( pointerType->base->forall ); - int castResult = ptrsCastable( pointerType->base, destAsPtr->base, newEnv, indexer ); - if ( castResult > 0 ) { - cost = Cost::safe; - } else if ( castResult < 0 ) { - cost = Cost::infinity; - } // if - } // if - } else if ( const BasicType * destAsBasic = dynamic_cast< const BasicType * >( dest ) ) { - if ( destAsBasic->isInteger() ) { - // necessary for, e.g. void * => unsigned long - cost = Cost::unsafe; - } // if - } - } namespace { @@ -200,6 +96,4 @@ } // anonymous namespace - - Cost castCost( const ast::Type * src, const ast::Type * dst, bool srcIsLvalue, Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/CommonType.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -23,10 +23,4 @@ #include "AST/Pass.hpp" #include "AST/Type.hpp" -#include "Common/PassVisitor.h" -#include "ResolvExpr/TypeEnvironment.h" // for OpenVarSet, AssertionSet -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl (ptr... -#include "SynTree/Type.h" // for BasicType, BasicType::Kind::... -#include "SynTree/Visitor.h" // for Visitor #include "Unify.h" // for unifyExact, WidenMode #include "typeops.h" // for isFtype @@ -41,144 +35,4 @@ namespace ResolvExpr { - struct CommonType_old : public WithShortCircuiting { - CommonType_old( Type * type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); - Type * get_result() const { return result; } - - void previsit( BaseSyntaxNode * ) { visit_children = false; } - - void postvisit( VoidType * voidType ); - void postvisit( BasicType * basicType ); - void postvisit( PointerType * pointerType ); - void postvisit( ArrayType * arrayType ); - void postvisit( ReferenceType * refType ); - void postvisit( FunctionType * functionType ); - void postvisit( StructInstType * aggregateUseType ); - void postvisit( UnionInstType * aggregateUseType ); - void postvisit( EnumInstType * aggregateUseType ); - void postvisit( TraitInstType * aggregateUseType ); - void postvisit( TypeInstType * aggregateUseType ); - void postvisit( TupleType * tupleType ); - void postvisit( VarArgsType * varArgsType ); - void postvisit( ZeroType * zeroType ); - void postvisit( OneType * oneType ); - - private: - template< typename Pointer > void getCommonWithVoidPointer( Pointer * voidPointer, Pointer * otherPointer ); - template< typename RefType > void handleRefType( RefType * inst, Type * other ); - - Type * result; - Type * type2; // inherited - bool widenFirst, widenSecond; - const SymTab::Indexer &indexer; - TypeEnvironment &env; - const OpenVarSet &openVars; - }; - - Type * handleReference( Type * t1, Type * t2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment & env, const OpenVarSet &openVars ) { - Type * common = nullptr; - AssertionSet have, need; - OpenVarSet newOpen( openVars ); - // need unify to bind type variables - if ( unify( t1, t2, env, have, need, newOpen, indexer, common ) ) { - PRINT( - std::cerr << "unify success: " << widenFirst << " " << widenSecond << std::endl; - ) - if ( (widenFirst || t2->tq <= t1->tq) && (widenSecond || t1->tq <= t2->tq) ) { - PRINT( - std::cerr << "widen okay" << std::endl; - ) - common->tq |= t1->tq; - common->tq |= t2->tq; - return common; - } - } - PRINT( - std::cerr << "exact unify failed: " << t1 << " " << t2 << std::endl; - ) - return nullptr; - } - - Type * commonType( Type * type1, Type * type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) { - PassVisitor visitor( type2, widenFirst, widenSecond, indexer, env, openVars ); - - int depth1 = type1->referenceDepth(); - int depth2 = type2->referenceDepth(); - if ( depth1 > 0 || depth2 > 0 ) { - int diff = depth1-depth2; - // TODO: should it be possible for commonType to generate complicated conversions? I would argue no, only conversions that involve types of the same reference level or a difference of 1 should be allowed. - // if ( diff > 1 || diff < -1 ) return nullptr; - - // special case where one type has a reference depth of 1 larger than the other - if ( diff > 0 || diff < 0 ) { - PRINT( - std::cerr << "reference depth diff: " << diff << std::endl; - ) - Type * result = nullptr; - ReferenceType * ref1 = dynamic_cast< ReferenceType * >( type1 ); - ReferenceType * ref2 = dynamic_cast< ReferenceType * >( type2 ); - if ( diff > 0 ) { - // deeper on the left - assert( ref1 ); - result = handleReference( ref1->base, type2, widenFirst, widenSecond, indexer, env, openVars ); - } else { - // deeper on the right - assert( ref2 ); - result = handleReference( type1, ref2->base, widenFirst, widenSecond, indexer, env, openVars ); - } - if ( result && ref1 ) { - // formal is reference, so result should be reference - PRINT( - std::cerr << "formal is reference; result should be reference" << std::endl; - ) - result = new ReferenceType( ref1->tq, result ); - } - PRINT( - std::cerr << "common type of reference [" << type1 << "] and [" << type2 << "] is [" << result << "]" << std::endl; - ) - return result; - } - // otherwise, both are reference types of the same depth and this is handled by the CommonType visitor. - } - - type1->accept( visitor ); - Type * result = visitor.pass.get_result(); - if ( ! result ) { - // this appears to be handling for opaque type declarations - if ( widenSecond ) { - if ( const TypeInstType * inst = dynamic_cast< const TypeInstType * >( type2 ) ) { - if ( const NamedTypeDecl * nt = indexer.lookupType( inst->get_name() ) ) { - const TypeDecl * type = strict_dynamic_cast< const TypeDecl * >( nt ); - if ( type->get_base() ) { - Type::Qualifiers tq1 = type1->tq, tq2 = type2->tq; - AssertionSet have, need; - OpenVarSet newOpen( openVars ); - type1->tq = Type::Qualifiers(); - type->get_base()->tq = tq1; - if ( unifyExact( type1, type->get_base(), env, have, need, newOpen, indexer ) ) { - result = type1->clone(); - result->tq = tq1 | tq2; - } // if - type1->tq = tq1; - type->get_base()->tq = Type::Qualifiers(); - } // if - } // if - } // if - } // if - } // if -#ifdef DEBUG - std::cerr << "============= commonType" << std::endl << "type1 is "; - type1->print( std::cerr ); - std::cerr << " type2 is "; - type2->print( std::cerr ); - if ( result ) { - std::cerr << " common type is "; - result->print( std::cerr ); - } else { - std::cerr << " no common type"; - } // if - std::cerr << std::endl; -#endif - return result; - } // GENERATED START, DO NOT EDIT @@ -488,188 +342,4 @@ "Each basic type kind should have a corresponding row in the combined type matrix" ); - - CommonType_old::CommonType_old( Type * type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) - : result( 0 ), type2( type2 ), widenFirst( widenFirst ), widenSecond( widenSecond ), indexer( indexer ), env( env ), openVars( openVars ) { - } - - void CommonType_old::postvisit( VoidType * ) {} - - void CommonType_old::postvisit( BasicType * basicType ) { - if ( BasicType * otherBasic = dynamic_cast< BasicType * >( type2 ) ) { - BasicType::Kind newType = (BasicType::Kind)(int)commonTypes[ (ast::BasicType::Kind)(int)basicType->get_kind() ][ (ast::BasicType::Kind)(int)otherBasic->get_kind() ]; - if ( ( ( newType == basicType->get_kind() && basicType->tq >= otherBasic->tq ) || widenFirst ) && ( ( newType == otherBasic->get_kind() && basicType->tq <= otherBasic->tq ) || widenSecond ) ) { - result = new BasicType( basicType->tq | otherBasic->tq, newType ); - } // if - } else if ( dynamic_cast< ZeroType * >( type2 ) || dynamic_cast< OneType * >( type2 ) ) { - // use signed int in lieu of the enum/zero/one type - BasicType::Kind newType = (BasicType::Kind)(int)commonTypes[ (ast::BasicType::Kind)(int)basicType->get_kind() ][ ast::BasicType::SignedInt ]; - if ( ( ( newType == basicType->get_kind() && basicType->tq >= type2->tq ) || widenFirst ) && ( ( newType != basicType->get_kind() && basicType->tq <= type2->tq ) || widenSecond ) ) { - result = new BasicType( basicType->tq | type2->tq, newType ); - } // if - } else if ( const EnumInstType * enumInst = dynamic_cast< const EnumInstType * > ( type2 ) ) { - const EnumDecl* enumDecl = enumInst->baseEnum; - if ( const Type* baseType = enumDecl->base ) { - result = baseType->clone(); - } else { - BasicType::Kind newType = (BasicType::Kind)(int)commonTypes[ (ast::BasicType::Kind)(int)basicType->get_kind() ][ ast::BasicType::SignedInt ]; - if ( ( ( newType == basicType->get_kind() && basicType->tq >= type2->tq ) || widenFirst ) && ( ( newType != basicType->get_kind() && basicType->tq <= type2->tq ) || widenSecond ) ) { - result = new BasicType( basicType->tq | type2->tq, newType ); - } // if - } - } - } - - template< typename Pointer > - void CommonType_old::getCommonWithVoidPointer( Pointer * voidPointer, Pointer * otherPointer ) { - if ( TypeInstType * var = dynamic_cast< TypeInstType * >( otherPointer->get_base() ) ) { - OpenVarSet::const_iterator entry = openVars.find( var->get_name() ); - if ( entry != openVars.end() ) { - AssertionSet need, have; - WidenMode widen( widenFirst, widenSecond ); - if ( entry != openVars.end() && ! env.bindVar(var, voidPointer->get_base(), entry->second, need, have, openVars, widen, indexer ) ) return; - } - } - result = voidPointer->clone(); - result->tq |= otherPointer->tq; - } - - void CommonType_old::postvisit( PointerType * pointerType ) { - if ( PointerType * otherPointer = dynamic_cast< PointerType * >( type2 ) ) { - // std::cerr << "commonType: two pointers: " << pointerType << " / " << otherPointer << std::endl; - if ( widenFirst && dynamic_cast< VoidType * >( otherPointer->get_base() ) && ! isFtype(pointerType->get_base()) ) { - getCommonWithVoidPointer( otherPointer, pointerType ); - } else if ( widenSecond && dynamic_cast< VoidType * >( pointerType->get_base() ) && ! isFtype(otherPointer->get_base()) ) { - getCommonWithVoidPointer( pointerType, otherPointer ); - } else if ( ( pointerType->get_base()->tq >= otherPointer->get_base()->tq || widenFirst ) - && ( pointerType->get_base()->tq <= otherPointer->get_base()->tq || widenSecond ) ) { - // std::cerr << "middle case" << std::endl; - Type::Qualifiers tq1 = pointerType->get_base()->tq, tq2 = otherPointer->get_base()->tq; - pointerType->get_base()->tq = Type::Qualifiers(); - otherPointer->get_base()->tq = Type::Qualifiers(); - AssertionSet have, need; - OpenVarSet newOpen( openVars ); - if ( unifyExact( pointerType->get_base(), otherPointer->get_base(), env, have, need, newOpen, indexer ) ) { - // std::cerr << "unifyExact success" << std::endl; - if ( tq1 < tq2 ) { - result = pointerType->clone(); - } else { - result = otherPointer->clone(); - } // if - strict_dynamic_cast(result)->base->tq = tq1 | tq2; - } else { - /// std::cerr << "place for ptr-to-type" << std::endl; - } // if - pointerType->get_base()->tq = tq1; - otherPointer->get_base()->tq = tq2; - } // if - } else if ( widenSecond && dynamic_cast< ZeroType * >( type2 ) ) { - result = pointerType->clone(); - result->tq |= type2->tq; - } // if - } - - void CommonType_old::postvisit( ArrayType * ) {} - - void CommonType_old::postvisit( ReferenceType * refType ) { - if ( ReferenceType * otherRef = dynamic_cast< ReferenceType * >( type2 ) ) { - // std::cerr << "commonType: both references: " << refType << " / " << otherRef << std::endl; - // std::cerr << ( refType->get_base()->tq >= otherRef->get_base()->tq || widenFirst ) << (refType->get_base()->tq <= otherRef->get_base()->tq || widenSecond) << std::endl; - if ( widenFirst && dynamic_cast< VoidType * >( otherRef->get_base() ) && ! isFtype(refType->get_base()) ) { - getCommonWithVoidPointer( otherRef, refType ); - } else if ( widenSecond && dynamic_cast< VoidType * >( refType->get_base() ) && ! isFtype(otherRef->get_base()) ) { - getCommonWithVoidPointer( refType, otherRef ); - } else if ( ( refType->get_base()->tq >= otherRef->get_base()->tq || widenFirst ) - && ( refType->get_base()->tq <= otherRef->get_base()->tq || widenSecond ) ) { - // std::cerr << "middle case" << std::endl; - Type::Qualifiers tq1 = refType->get_base()->tq, tq2 = otherRef->get_base()->tq; - refType->get_base()->tq = Type::Qualifiers(); - otherRef->get_base()->tq = Type::Qualifiers(); - AssertionSet have, need; - OpenVarSet newOpen( openVars ); - if ( unifyExact( refType->get_base(), otherRef->get_base(), env, have, need, newOpen, indexer ) ) { - if ( tq1 < tq2 ) { - result = refType->clone(); - } else { - result = otherRef->clone(); - } // if - strict_dynamic_cast(result)->base->tq = tq1 | tq2; - } else { - /// std::cerr << "place for ptr-to-type" << std::endl; - } // if - refType->get_base()->tq = tq1; - otherRef->get_base()->tq = tq2; - } // if - } else if ( widenSecond && dynamic_cast< ZeroType * >( type2 ) ) { - result = refType->clone(); - result->tq |= type2->tq; - } // if - } - - void CommonType_old::postvisit( FunctionType * ) {} - void CommonType_old::postvisit( StructInstType * ) {} - void CommonType_old::postvisit( UnionInstType * ) {} - - void CommonType_old::postvisit( EnumInstType * enumInstType ) { - if ( dynamic_cast< BasicType * >( type2 ) || dynamic_cast< ZeroType * >( type2 ) || dynamic_cast< OneType * >( type2 ) ) { - // reuse BasicType, EnumInstType code by swapping type2 with enumInstType - result = commonType( type2, enumInstType, widenSecond, widenFirst, indexer, env, openVars ); - } // if - } - - void CommonType_old::postvisit( TraitInstType * ) { - } - - void CommonType_old::postvisit( TypeInstType * inst ) { - if ( widenFirst ) { - const NamedTypeDecl * nt = indexer.lookupType( inst->get_name() ); - if ( nt ) { - const TypeDecl * type = strict_dynamic_cast< const TypeDecl * >( nt ); - if ( type->get_base() ) { - Type::Qualifiers tq1 = inst->tq, tq2 = type2->tq; - AssertionSet have, need; - OpenVarSet newOpen( openVars ); - type2->tq = Type::Qualifiers(); - type->get_base()->tq = tq1; - if ( unifyExact( type->get_base(), type2, env, have, need, newOpen, indexer ) ) { - result = type2->clone(); - result->tq = tq1 | tq2; - } // if - type2->tq = tq2; - type->get_base()->tq = Type::Qualifiers(); - } // if - } // if - } // if - } - - void CommonType_old::postvisit( TupleType * ) {} - void CommonType_old::postvisit( VarArgsType * ) {} - - void CommonType_old::postvisit( ZeroType * zeroType ) { - if ( widenFirst ) { - if ( dynamic_cast< BasicType * >( type2 ) || dynamic_cast< PointerType * >( type2 ) || dynamic_cast< EnumInstType * >( type2 ) ) { - if ( widenSecond || zeroType->tq <= type2->tq ) { - result = type2->clone(); - result->tq |= zeroType->tq; - } - } else if ( widenSecond && dynamic_cast< OneType * >( type2 ) ) { - result = new BasicType( zeroType->tq, BasicType::SignedInt ); - result->tq |= type2->tq; - } - } - } - - void CommonType_old::postvisit( OneType * oneType ) { - if ( widenFirst ) { - if ( dynamic_cast< BasicType * >( type2 ) || dynamic_cast< EnumInstType * >( type2 ) ) { - if ( widenSecond || oneType->tq <= type2->tq ) { - result = type2->clone(); - result->tq |= oneType->tq; - } - } else if ( widenSecond && dynamic_cast< ZeroType * >( type2 ) ) { - result = new BasicType( oneType->tq, BasicType::SignedInt ); - result->tq |= type2->tq; - } - } - } class CommonType_new final : public ast::WithShortCircuiting { Index: src/ResolvExpr/CommonType.hpp =================================================================== --- src/ResolvExpr/CommonType.hpp (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/CommonType.hpp (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -18,18 +18,8 @@ #include "AST/Fwd.hpp" #include "AST/TypeEnvironment.hpp" // for AssertionSet, OpenVarSet -#include "TypeEnvironment.h" // for AssertionSet, OpenVarSet #include "WidenMode.h" // for WidenMode - -class Type; -namespace SymTab { - class Indexer; -} namespace ResolvExpr { -Type * commonType( - Type * type1, Type * type2, bool widenFirst, bool widenSecond, - const SymTab::Indexer & indexer, TypeEnvironment & env, - const OpenVarSet & openVars ); ast::ptr< ast::Type > commonType( const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/ConversionCost.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -21,24 +21,8 @@ #include "ResolvExpr/Cost.h" // for Cost -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment #include "ResolvExpr/Unify.h" // for typesCompatibleIgnoreQualifiers #include "ResolvExpr/PtrsAssignable.hpp" // for ptrsAssignable -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl -#include "SynTree/Type.h" // for Type, BasicType, TypeInstType - namespace ResolvExpr { -#if 0 - const Cost Cost::zero = Cost{ 0, 0, 0, 0, 0, 0, 0 }; - const Cost Cost::infinity = Cost{ -1, -1, -1, -1, -1, 1, -1 }; - const Cost Cost::unsafe = Cost{ 1, 0, 0, 0, 0, 0, 0 }; - const Cost Cost::poly = Cost{ 0, 1, 0, 0, 0, 0, 0 }; - const Cost Cost::safe = Cost{ 0, 0, 1, 0, 0, 0, 0 }; - const Cost Cost::sign = Cost{ 0, 0, 0, 1, 0, 0, 0 }; - const Cost Cost::var = Cost{ 0, 0, 0, 0, 1, 0, 0 }; - const Cost Cost::spec = Cost{ 0, 0, 0, 0, 0, -1, 0 }; - const Cost Cost::reference = Cost{ 0, 0, 0, 0, 0, 0, 1 }; -#endif #if 0 @@ -47,155 +31,4 @@ #define PRINT(x) #endif - - Cost conversionCost( const Type * src, const Type * dest, bool srcIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment &env ) { - if ( const TypeInstType * destAsTypeInst = dynamic_cast< const TypeInstType * >( dest ) ) { - PRINT( std::cerr << "type inst " << destAsTypeInst->name; ) - if ( const EqvClass * eqvClass = env.lookup( destAsTypeInst->name ) ) { - if ( eqvClass->type ) { - return conversionCost( src, eqvClass->type, srcIsLvalue, indexer, env ); - } else { - return Cost::infinity; - } - } else if ( const NamedTypeDecl * namedType = indexer.lookupType( destAsTypeInst->name ) ) { - PRINT( std::cerr << " found" << std::endl; ) - const TypeDecl * type = dynamic_cast< const TypeDecl * >( namedType ); - // all typedefs should be gone by this point - assert( type ); - if ( type->base ) { - return conversionCost( src, type->base, srcIsLvalue, indexer, env ) - + Cost::safe; - } // if - } // if - PRINT( std::cerr << " not found" << std::endl; ) - } // if - PRINT( - std::cerr << "src is "; - src->print( std::cerr ); - std::cerr << std::endl << "dest is "; - dest->print( std::cerr ); - std::cerr << std::endl << "env is" << std::endl; - env.print( std::cerr, 8 ); - ) - if ( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) { - PRINT( std::cerr << "compatible!" << std::endl; ) - return Cost::zero; - } else if ( dynamic_cast< const VoidType * >( dest ) ) { - return Cost::safe; - } else if ( const ReferenceType * refType = dynamic_cast< const ReferenceType * > ( dest ) ) { - PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; ) - return convertToReferenceCost( src, refType, srcIsLvalue, indexer, env, [](const Type * const t1, const Type * t2, const SymTab::Indexer &, const TypeEnvironment & env ){ - return ptrsAssignable( t1, t2, env ); - }); - } else { - PassVisitor converter( - dest, srcIsLvalue, indexer, env, - (Cost (*)(const Type *, const Type *, bool, const SymTab::Indexer&, const TypeEnvironment&)) - conversionCost ); - src->accept( converter ); - if ( converter.pass.get_cost() == Cost::infinity ) { - return Cost::infinity; - } else { - return converter.pass.get_cost() + Cost::zero; - } // if - } // if - } - - static Cost convertToReferenceCost( const Type * src, const Type * dest, bool srcIsLvalue, - int diff, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) { - PRINT( std::cerr << "convert to reference cost... diff " << diff << " " << src << " / " << dest << std::endl; ) - if ( diff > 0 ) { - // TODO: document this - Cost cost = convertToReferenceCost( - strict_dynamic_cast< const ReferenceType * >( src )->base, dest, srcIsLvalue, - diff-1, indexer, env, func ); - cost.incReference(); - return cost; - } else if ( diff < -1 ) { - // TODO: document this - Cost cost = convertToReferenceCost( - src, strict_dynamic_cast< const ReferenceType * >( dest )->base, srcIsLvalue, - diff+1, indexer, env, func ); - cost.incReference(); - return cost; - } else if ( diff == 0 ) { - const ReferenceType * srcAsRef = dynamic_cast< const ReferenceType * >( src ); - const ReferenceType * destAsRef = dynamic_cast< const ReferenceType * >( dest ); - if ( srcAsRef && destAsRef ) { // pointer-like conversions between references - PRINT( std::cerr << "converting between references" << std::endl; ) - Type::Qualifiers tq1 = srcAsRef->base->tq; - Type::Qualifiers tq2 = destAsRef->base->tq; - if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( srcAsRef->base, destAsRef->base, indexer, env ) ) { - PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; ) - if ( tq1 == tq2 ) { - // types are the same - return Cost::zero; - } else { - // types are the same, except otherPointer has more qualifiers - return Cost::safe; - } - } else { // xxx - this discards reference qualifiers from consideration -- reducing qualifiers is a safe conversion; is this right? - int assignResult = func( srcAsRef->base, destAsRef->base, indexer, env ); - PRINT( std::cerr << "comparing references: " << assignResult << " " << srcAsRef << " " << destAsRef << std::endl; ) - if ( assignResult > 0 ) { - return Cost::safe; - } else if ( assignResult < 0 ) { - return Cost::unsafe; - } // if - } // if - } else { - PRINT( std::cerr << "reference to rvalue conversion" << std::endl; ) - PassVisitor converter( - dest, srcIsLvalue, indexer, env, - (Cost (*)(const Type *, const Type *, bool, const SymTab::Indexer&, const TypeEnvironment&)) - conversionCost ); - src->accept( converter ); - return converter.pass.get_cost(); - } // if - } else { - const ReferenceType * destAsRef = dynamic_cast< const ReferenceType * >( dest ); - assert( diff == -1 && destAsRef ); - PRINT( std::cerr << "dest is: " << dest << " / src is: " << src << std::endl; ) - if ( typesCompatibleIgnoreQualifiers( src, destAsRef->base, indexer, env ) ) { - PRINT( std::cerr << "converting compatible base type" << std::endl; ) - if ( srcIsLvalue ) { - PRINT( - std::cerr << "lvalue to reference conversion" << std::endl; - std::cerr << src << " => " << destAsRef << std::endl; - ) - // lvalue-to-reference conversion: cv lvalue T => cv T & - if ( src->tq == destAsRef->base->tq ) { - return Cost::reference; // cost needs to be non-zero to add cast - } if ( src->tq < destAsRef->base->tq ) { - return Cost::safe; // cost needs to be higher than previous cast to differentiate adding qualifiers vs. keeping same - } else { - return Cost::unsafe; - } // if - } else if ( destAsRef->base->get_const() ) { - PRINT( std::cerr << "rvalue to const ref conversion" << std::endl; ) - // rvalue-to-const-reference conversion: T => const T & - return Cost::safe; - } else { - PRINT( std::cerr << "rvalue to non-const reference conversion" << std::endl; ) - // rvalue-to-reference conversion: T => T & - return Cost::unsafe; - } // if - } // if - PRINT( std::cerr << "attempting to convert from incompatible base type -- fail" << std::endl; ) - } - return Cost::infinity; - } - - Cost convertToReferenceCost( const Type * src, const ReferenceType * dest, bool srcIsLvalue, - const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) { - int sdepth = src->referenceDepth(), ddepth = dest->referenceDepth(); - Cost cost = convertToReferenceCost( src, dest, srcIsLvalue, sdepth-ddepth, indexer, env, func ); - PRINT( std::cerr << "convertToReferenceCost result: " << cost << std::endl; ) - return cost; - } - - ConversionCost::ConversionCost( const Type * dest, bool srcIsLvalue, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc ) - : dest( dest ), srcIsLvalue( srcIsLvalue ), indexer( indexer ), cost( Cost::infinity ), env( env ), costFunc( costFunc ) { - } // GENERATED START, DO NOT EDIT @@ -319,186 +152,4 @@ ); - void ConversionCost::postvisit( const VoidType * ) { - cost = Cost::infinity; - } - - // refactor for code resue - void ConversionCost::conversionCostFromBasicToBasic(const BasicType * src, const BasicType * dest) { - int tableResult = costMatrix[ src->kind ][ dest->kind ]; - if ( tableResult == -1 ) { - cost = Cost::unsafe; - } else { - cost = Cost::zero; - cost.incSafe( tableResult ); - cost.incSign( signMatrix[ src->kind ][ dest->kind ] ); - } // if - } // ConversionCost::conversionCostFromBasicToBasic - - void ConversionCost::postvisit(const BasicType * basicType) { - if ( const BasicType * destAsBasic = dynamic_cast< const BasicType * >( dest ) ) { - conversionCostFromBasicToBasic(basicType, destAsBasic); - } else if ( const EnumInstType * enumInst = dynamic_cast< const EnumInstType * >( dest ) ) { - const EnumDecl * base_enum = enumInst->baseEnum; - if ( const Type * base = base_enum->base ) { - if ( const BasicType * enumBaseAstBasic = dynamic_cast< const BasicType *> (base) ) { - conversionCostFromBasicToBasic(basicType, enumBaseAstBasic); - } else { - cost = Cost::infinity; - } // if - } else { - cost = Cost::unsafe; - } // if - } // if - // no cases for zero_t/one_t because it should not be possible to convert int, etc. to zero_t/one_t. - } - - void ConversionCost::postvisit( const PointerType * pointerType ) { - if ( const PointerType * destAsPtr = dynamic_cast< const PointerType * >( dest ) ) { - PRINT( std::cerr << pointerType << " ===> " << destAsPtr << std::endl; ) - Type::Qualifiers tq1 = pointerType->base->tq; - Type::Qualifiers tq2 = destAsPtr->base->tq; - if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) { - PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; ) - if ( tq1 == tq2 ) { - // types are the same - cost = Cost::zero; - } else { - // types are the same, except otherPointer has more qualifiers - cost = Cost::safe; - } // if - } else { - int assignResult = ptrsAssignable( pointerType->base, destAsPtr->base, env ); - PRINT( std::cerr << " :: " << assignResult << std::endl; ) - if ( assignResult > 0 && tq1 <= tq2 ) { - // xxx - want the case where qualifiers are added to be more expensive than the case where qualifiers are the same. Is 1 safe vs. 2 safe correct? - if ( tq1 == tq2 ) { - cost = Cost::safe; - } else if ( tq1 < tq2 ) { - cost = Cost::safe+Cost::safe; - } - } else if ( assignResult < 0 ) { - cost = Cost::unsafe; - } // if - // assignResult == 0 means Cost::Infinity - } // if - // case case for zero_t because it should not be possible to convert pointers to zero_t. - } // if - } - - void ConversionCost::postvisit( const ArrayType * ) {} - - void ConversionCost::postvisit( const ReferenceType * refType ) { - // Note: dest can never be a reference, since it would have been caught in an earlier check - assert( ! dynamic_cast< const ReferenceType * >( dest ) ); - // convert reference to rvalue: cv T1 & => T2 - // recursively compute conversion cost from T1 to T2. - // cv can be safely dropped because of 'implicit dereference' behavior. - cost = costFunc( refType->base, dest, srcIsLvalue, indexer, env ); - if ( refType->base->tq == dest->tq ) { - cost.incReference(); // prefer exact qualifiers - } else if ( refType->base->tq < dest->tq ) { - cost.incSafe(); // then gaining qualifiers - } else { - cost.incUnsafe(); // lose qualifiers as last resort - } - PRINT( std::cerr << refType << " ==> " << dest << " " << cost << std::endl; ) - } - - void ConversionCost::postvisit( const FunctionType * ) {} - - void ConversionCost::postvisit( const EnumInstType * enumInst) { - const EnumDecl * enumDecl = enumInst -> baseEnum; - if ( const Type * enumType = enumDecl -> base ) { // if it is a typed enum - cost = costFunc( enumType, dest, srcIsLvalue, indexer, env ); - } else { - static Type::Qualifiers q; - static BasicType integer( q, BasicType::SignedInt ); - cost = costFunc( &integer, dest, srcIsLvalue, indexer, env ); // safe if dest >= int - } // if - if ( cost < Cost::unsafe ) { - cost.incSafe(); - } // if - } - - void ConversionCost::postvisit( const TraitInstType * ) {} - - void ConversionCost::postvisit( const TypeInstType * inst ) { - if ( const EqvClass * eqvClass = env.lookup( inst->name ) ) { - cost = costFunc( eqvClass->type, dest, srcIsLvalue, indexer, env ); - } else if ( const TypeInstType * destAsInst = dynamic_cast< const TypeInstType * >( dest ) ) { - if ( inst->name == destAsInst->name ) { - cost = Cost::zero; - } - } else if ( const NamedTypeDecl * namedType = indexer.lookupType( inst->name ) ) { - const TypeDecl * type = dynamic_cast< const TypeDecl * >( namedType ); - // all typedefs should be gone by this point - assert( type ); - if ( type->base ) { - cost = costFunc( type->base, dest, srcIsLvalue, indexer, env ) + Cost::safe; - } // if - } // if - } - - void ConversionCost::postvisit( const TupleType * tupleType ) { - Cost c = Cost::zero; - if ( const TupleType * destAsTuple = dynamic_cast< const TupleType * >( dest ) ) { - std::list< Type * >::const_iterator srcIt = tupleType->types.begin(); - std::list< Type * >::const_iterator destIt = destAsTuple->types.begin(); - while ( srcIt != tupleType->types.end() && destIt != destAsTuple->types.end() ) { - Cost newCost = costFunc( * srcIt++, * destIt++, srcIsLvalue, indexer, env ); - if ( newCost == Cost::infinity ) { - return; - } // if - c += newCost; - } // while - if ( destIt != destAsTuple->types.end() ) { - cost = Cost::infinity; - } else { - cost = c; - } // if - } // if - } - - void ConversionCost::postvisit( const VarArgsType * ) { - if ( dynamic_cast< const VarArgsType * >( dest ) ) { - cost = Cost::zero; - } - } - - void ConversionCost::postvisit( const ZeroType * ) { - if ( dynamic_cast< const ZeroType * >( dest ) ) { - cost = Cost::zero; - } else if ( const BasicType * destAsBasic = dynamic_cast< const BasicType * >( dest ) ) { - // copied from visit(BasicType *) for signed int, but +1 for safe conversions - int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->kind ]; - if ( tableResult == -1 ) { - cost = Cost::unsafe; - } else { - cost = Cost::zero; - cost.incSafe( tableResult + 1 ); - cost.incSign( signMatrix[ BasicType::SignedInt ][ destAsBasic->kind ] ); - } // if - } else if ( dynamic_cast< const PointerType * >( dest ) ) { - cost = Cost::zero; - cost.incSafe( maxIntCost + 2 ); // +1 for zero_t -> int, +1 for disambiguation - } // if - } - - void ConversionCost::postvisit( const OneType * ) { - if ( dynamic_cast< const OneType * >( dest ) ) { - cost = Cost::zero; - } else if ( const BasicType * destAsBasic = dynamic_cast< const BasicType * >( dest ) ) { - // copied from visit(BasicType *) for signed int, but +1 for safe conversions - int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->kind ]; - if ( tableResult == -1 ) { - cost = Cost::unsafe; - } else { - cost = Cost::zero; - cost.incSafe( tableResult + 1 ); - cost.incSign( signMatrix[ BasicType::SignedInt ][ destAsBasic->kind ] ); - } // if - } // if - } - namespace { # warning For overload resolution between the two versions. Index: src/ResolvExpr/ConversionCost.h =================================================================== --- src/ResolvExpr/ConversionCost.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/ConversionCost.h (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -22,7 +22,4 @@ #include "AST/Fwd.hpp" #include "AST/Pass.hpp" // for WithShortCircuiting -#include "Common/PassVisitor.h" -#include "SynTree/Visitor.h" // for Visitor -#include "SynTree/SynTree.h" // for Visitor Nodes namespace SymTab { @@ -32,49 +29,4 @@ namespace ResolvExpr { class TypeEnvironment; - - Cost conversionCost( - const Type * src, const Type * dest, bool srcIsLvalue, - const SymTab::Indexer & indexer, const TypeEnvironment & env ); - - typedef std::function CostFunction; - - struct ConversionCost : public WithShortCircuiting { - public: - ConversionCost( const Type * dest, bool srcIsLvalue, - const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction ); - - Cost get_cost() const { return cost; } - - void previsit( const BaseSyntaxNode * ) { visit_children = false; } - - void postvisit( const VoidType * voidType ); - void postvisit( const BasicType * basicType ); - void postvisit( const PointerType * pointerType ); - void postvisit( const ArrayType * arrayType ); - void postvisit( const ReferenceType * refType ); - void postvisit( const FunctionType * functionType ); - void postvisit( const EnumInstType * aggregateUseType ); - void postvisit( const TraitInstType * aggregateUseType ); - void postvisit( const TypeInstType * aggregateUseType ); - void postvisit( const TupleType * tupleType ); - void postvisit( const VarArgsType * varArgsType ); - void postvisit( const ZeroType * zeroType ); - void postvisit( const OneType * oneType ); - protected: - const Type * dest; - bool srcIsLvalue; - const SymTab::Indexer &indexer; - Cost cost; - const TypeEnvironment &env; - CostFunction costFunc; - private: - // refactor for code resue - void conversionCostFromBasicToBasic( const BasicType * src, const BasicType* dest ); - }; - - typedef std::function PtrsFunction; - Cost convertToReferenceCost( const Type * src, const ReferenceType * dest, bool srcIsLvalue, - const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ); // Some function pointer types, differ in return type. Index: src/ResolvExpr/CurrentObject.cc =================================================================== --- src/ResolvExpr/CurrentObject.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/CurrentObject.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -33,10 +33,4 @@ #include "Common/utility.h" // for toString #include "CurrentObject.h" -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Declaration.h" // for ObjectDecl, Declaration, Struc... -#include "SynTree/Expression.h" // for InitAlternative, VariableExpr -#include "SynTree/Initializer.h" // for Designation, operator<< -#include "SynTree/Type.h" // for Type, StructInstType, UnionIns... -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution #if 0 @@ -45,550 +39,4 @@ #define PRINT(x) #endif - -namespace ResolvExpr { - template< typename AggrInst > - TypeSubstitution makeGenericSubstitution( AggrInst * inst ) { - assert( inst ); - assert( inst->get_baseParameters() ); - std::list< TypeDecl * > baseParams = *inst->get_baseParameters(); - std::list< Expression * > typeSubs = inst->get_parameters(); - TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() ); - return subs; - } - - TypeSubstitution makeGenericSubstitution( Type * type ) { - if ( StructInstType * inst = dynamic_cast< StructInstType * >( type ) ) { - return makeGenericSubstitution( inst ); - } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( type ) ) { - return makeGenericSubstitution( inst ); - } else { - return TypeSubstitution(); - } - } - - class MemberIterator { - public: - virtual ~MemberIterator() {} - - /// walks the current object using the given designators as a guide - virtual void setPosition( std::list< Expression * > & designators ) = 0; - - /// retrieve the list of possible Type/Designation pairs for the current position in the currect object - virtual std::list operator*() const = 0; - - /// true if the iterator is not currently at the end - virtual operator bool() const = 0; - - /// moves the iterator by one member in the current object - virtual MemberIterator & bigStep() = 0; - - /// moves the iterator by one member in the current subobject - virtual MemberIterator & smallStep() = 0; - - /// the type of the current object - virtual Type * getType() = 0; - - /// the type of the current subobject - virtual Type * getNext() = 0; - - /// printing for debug - virtual void print( std::ostream & out, Indenter indent ) const = 0; - - /// helper for operator*; aggregates must add designator to each init alternative, but - /// adding designators in operator* creates duplicates. - virtual std::list first() const = 0; // should be protected - }; - - std::ostream & operator<<(std::ostream & out, const MemberIterator & it) { - Indenter indenter; - it.print( out, indenter ); - return out; - } - - /// create a new MemberIterator that traverses a type correctly - MemberIterator * createMemberIterator( Type * type ); - - /// iterates "other" types, e.g. basic types, pointer types, etc. which do not change at list initializer entry - class SimpleIterator : public MemberIterator { - public: - SimpleIterator( Type * type ) : type( type ) {} - - virtual void setPosition( std::list< Expression * > & designators ) { - assertf( designators.empty(), "simple iterator given non-empty designator..." ); // xxx - might be semantic error - } - - virtual std::list operator*() const { return first(); } - virtual operator bool() const { return type; } - - // big step is the same as small step - virtual MemberIterator & bigStep() { return smallStep(); } - virtual MemberIterator & smallStep() { - type = nullptr; // type is nullified on increment since SimpleIterators do not have members - return *this; - } - - virtual void print( std::ostream & out, __attribute__((unused)) Indenter indent ) const { - out << "SimpleIterator(" << type << ")"; - } - - virtual Type * getType() { return type; } - virtual Type * getNext() { return type; } - - protected: - virtual std::list first() const { - if ( type ) return std::list{ { type->clone(), new Designation( {} ) } }; - else return std::list{}; - } - private: - Type * type = nullptr; - }; - - class ArrayIterator : public MemberIterator { - public: - ArrayIterator( ArrayType * at ) : array( at ) { - PRINT( std::cerr << "Creating array iterator: " << at << std::endl; ) - base = at->base; - memberIter = createMemberIterator( base ); - if ( at->isVarLen ) SemanticError( at, "VLA initialization does not support @=: " ); - setSize( at->dimension ); - } - - ~ArrayIterator() { - delete memberIter; - } - - private: - void setSize( Expression * expr ) { - auto res = eval( expr ); - if (res.second) { - size = res.first; - } else { - SemanticError( expr->location, toString("Array designator must be a constant expression: ", expr) ); - } - } - - public: - void setPosition( Expression * expr ) { - // need to permit integer-constant-expressions, including: integer constants, enumeration constants, character constants, sizeof expressions, _Alignof expressions, cast expressions - auto arg = eval( expr ); - index = arg.first; - return; - - // if ( ConstantExpr * constExpr = dynamic_cast< ConstantExpr * >( expr ) ) { - // try { - // index = constExpr->intValue(); - // } catch( SemanticErrorException & ) { - // SemanticError( expr, "Constant expression of non-integral type in array designator: " ); - // } - // } else if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) { - // setPosition( castExpr->get_arg() ); - // } else if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( expr ) ) { - // EnumInstType * inst = dynamic_cast( varExpr->get_result() ); - // assertf( inst, "ArrayIterator given variable that isn't an enum constant : %s", toString( expr ).c_str() ); - // long long int value; - // if ( inst->baseEnum->valueOf( varExpr->var, value ) ) { - // index = value; - // } - // } else if ( dynamic_cast< SizeofExpr * >( expr ) || dynamic_cast< AlignofExpr * >( expr ) ) { - // index = 0; // xxx - get actual sizeof/alignof value? - // } else { - // assertf( false, "4 bad designator given to ArrayIterator: %s", toString( expr ).c_str() ); - // } - } - - virtual void setPosition( std::list< Expression * > & designators ) { - if ( ! designators.empty() ) { - setPosition( designators.front() ); - designators.pop_front(); - memberIter->setPosition( designators ); - } - } - - virtual std::list operator*() const { - return first(); - } - - virtual operator bool() const { return index < size; } - - virtual MemberIterator & bigStep() { - PRINT( std::cerr << "bigStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; ) - ++index; - delete memberIter; - if ( index < size ) memberIter = createMemberIterator( base ); - else memberIter = nullptr; - return *this; - } - - virtual MemberIterator & smallStep() { - PRINT( std::cerr << "smallStep in ArrayIterator (" << index << "/" << size << ")" << std::endl; ) - if ( memberIter ) { - PRINT( std::cerr << "has member iter: " << *memberIter << std::endl; ) - memberIter->smallStep(); - if ( *memberIter ) { - PRINT( std::cerr << "has valid member iter" << std::endl; ) - return *this; - } - } - return bigStep(); - } - - virtual Type * getType() { return array; } - virtual Type * getNext() { return base; } - - virtual std::list first() const { - PRINT( std::cerr << "first in ArrayIterator (" << index << "/" << size << ")" << std::endl; ) - if ( memberIter && *memberIter ) { - std::list ret = memberIter->first(); - for ( InitAlternative & alt : ret ) { - alt.designation->get_designators().push_front( new ConstantExpr( Constant::from_ulong( index ) ) ); - } - return ret; - } - return std::list(); - } - - virtual void print( std::ostream & out, Indenter indent ) const { - out << "ArrayIterator(Array of " << base << ")"; - if ( memberIter ) { - Indenter childIndent = indent+1; - out << std::endl << childIndent; - memberIter->print( out, childIndent ); - } - } - - private: - ArrayType * array = nullptr; - Type * base = nullptr; - size_t index = 0; - size_t size = 0; - MemberIterator * memberIter = nullptr; - }; - - class AggregateIterator : public MemberIterator { - public: - typedef std::list MemberList; - typedef MemberList::const_iterator iterator; - std::string kind = ""; // for debug - std::string name; - Type * inst = nullptr; - const MemberList & members; - iterator curMember; - bool atbegin = true; // false at first {small,big}Step -- this aggr type is only added to the possibilities at the beginning - Type * curType = nullptr; - MemberIterator * memberIter = nullptr; - mutable TypeSubstitution sub; - - AggregateIterator( const std::string & kind, const std::string & name, Type * inst, const MemberList & members ) : kind( kind ), name( name ), inst( inst ), members( members ), curMember( members.begin() ), sub( makeGenericSubstitution( inst ) ) { - PRINT( std::cerr << "Creating " << kind << "(" << name << ")"; ) - init(); - } - - virtual ~AggregateIterator() { - delete memberIter; - } - - bool init() { - PRINT( std::cerr << "--init()--" << members.size() << std::endl; ) - if ( curMember != members.end() ) { - if ( ObjectDecl * field = dynamic_cast< ObjectDecl * >( *curMember ) ) { - PRINT( std::cerr << "incremented to field: " << field << std::endl; ) - curType = field->get_type(); - memberIter = createMemberIterator( curType ); - return true; - } - } - return false; - } - - virtual std::list operator*() const { - if (memberIter && *memberIter) { - std::list ret = memberIter->first(); - PRINT( std::cerr << "sub: " << sub << std::endl; ) - for ( InitAlternative & alt : ret ) { - PRINT( std::cerr << "iterating and adding designators" << std::endl; ) - alt.designation->get_designators().push_front( new VariableExpr( strict_dynamic_cast< ObjectDecl * >( *curMember ) ) ); - // need to substitute for generic types, so that casts are to concrete types - PRINT( std::cerr << " type is: " << alt.type; ) - sub.apply( alt.type ); // also apply to designation?? - PRINT( std::cerr << " ==> " << alt.type << std::endl; ) - } - return ret; - } - return std::list(); - } - - virtual void setPosition( std::list< Expression * > & designators ) { - if ( ! designators.empty() ) { - if ( VariableExpr * varExpr = dynamic_cast< VariableExpr * >( designators.front() ) ) { - for ( curMember = members.begin(); curMember != members.end(); ++curMember ) { - if ( *curMember == varExpr->get_var() ) { - designators.pop_front(); - delete memberIter; - memberIter = createMemberIterator( varExpr->get_result() ); - curType = varExpr->get_result(); - atbegin = curMember == members.begin() && designators.empty(); // xxx - is this the right condition for atbegin?? - memberIter->setPosition( designators ); - return; - } // if - } // for - assertf( false, "could not find member in %s: %s", kind.c_str(), toString( varExpr ).c_str() ); - } else { - assertf( false, "3 bad designator given to %s: %s", kind.c_str(), toString( designators.front() ).c_str() ); - } // if - } // if - } - - virtual MemberIterator & smallStep() { - PRINT( std::cerr << "smallStep in " << kind << std::endl; ) - atbegin = false; - if ( memberIter ) { - PRINT( std::cerr << "has member iter, incrementing..." << std::endl; ) - memberIter->smallStep(); - if ( *memberIter ) { - PRINT( std::cerr << "success!" << std::endl; ) - return *this; - } - } - return bigStep(); - } - - virtual Type * getType() { return inst; } - virtual Type * getNext() { - if ( memberIter && *memberIter ) return memberIter->getType(); // xxx - ??? recursive call??? - return nullptr; - } - - virtual std::list first() const { - std::list ret; - PRINT( std::cerr << "first " << kind << std::endl; ) - if ( memberIter && *memberIter ) { // might not need *memberIter?? - PRINT( std::cerr << "adding children" << std::endl; ) - ret = memberIter->first(); - for ( InitAlternative & alt : ret ) { - PRINT( std::cerr << "iterating and adding designators" << std::endl; ) - alt.designation->get_designators().push_front( new VariableExpr( strict_dynamic_cast< ObjectDecl * >( *curMember ) ) ); - } - } - if ( atbegin ) { - // xxx - what about case of empty struct?? - // only add self if at the very beginning of the structure - PRINT( std::cerr << "adding self" << std::endl; ) - ret.push_front( { inst->clone(), new Designation( {} ) } ); - } - return ret; - } - - virtual void print( std::ostream & out, Indenter indent ) const { - out << kind << "(" << name << ")"; - if ( memberIter ) { - Indenter childIndent = indent+1; - out << std::endl << childIndent; - memberIter->print( out, childIndent ); - } - } - }; - - class UnionIterator : public AggregateIterator { - public: - UnionIterator( UnionInstType * inst ) : AggregateIterator( "UnionIterator", inst->get_name(), inst, inst->get_baseUnion()->get_members() ) {} - - virtual operator bool() const { return (memberIter && *memberIter); } - virtual MemberIterator & bigStep() { - // unions only initialize one member - PRINT( std::cerr << "bigStep in " << kind << std::endl; ) - atbegin = false; - delete memberIter; - memberIter = nullptr; - curType = nullptr; - curMember = members.end(); - return *this; - } - }; - - class StructIterator : public AggregateIterator { - public: - StructIterator( StructInstType * inst ) : AggregateIterator( "StructIterator", inst->get_name(), inst, inst->get_baseStruct()->get_members() ) {} - - virtual operator bool() const { return curMember != members.end() || (memberIter && *memberIter); } - - virtual MemberIterator & bigStep() { - PRINT( std::cerr << "bigStep in " << kind << std::endl; ) - atbegin = false; - delete memberIter; - memberIter = nullptr; - curType = nullptr; - for ( ; curMember != members.end(); ) { - ++curMember; - if ( init() ) { - return *this; - } - } - return *this; - } - }; - - class TupleIterator : public AggregateIterator { - public: - TupleIterator( TupleType * inst ) : AggregateIterator( "TupleIterator", toString("Tuple", inst->size()), inst, inst->get_members() ) {} - - virtual operator bool() const { return curMember != members.end() || (memberIter && *memberIter); } - - virtual MemberIterator & bigStep() { - PRINT( std::cerr << "bigStep in " << kind << std::endl; ) - atbegin = false; - delete memberIter; - memberIter = nullptr; - curType = nullptr; - for ( ; curMember != members.end(); ) { - ++curMember; - if ( init() ) { - return *this; - } - } - return *this; - } - }; - - MemberIterator * createMemberIterator( Type * type ) { - if ( ReferenceToType * aggr = dynamic_cast< ReferenceToType * >( type ) ) { - if ( StructInstType * sit = dynamic_cast< StructInstType * >( aggr ) ) { - return new StructIterator( sit ); - } else if ( UnionInstType * uit = dynamic_cast< UnionInstType * >( aggr ) ) { - return new UnionIterator( uit ); - } else { - assertf( dynamic_cast< EnumInstType * >( type ) || dynamic_cast< TypeInstType * >( type ), "Encountered unhandled ReferenceToType in createMemberIterator: %s", toString( type ).c_str() ); - return new SimpleIterator( type ); - } - } else if ( ArrayType * at = dynamic_cast< ArrayType * >( type ) ) { - return new ArrayIterator( at ); - } else if ( TupleType * tt = dynamic_cast< TupleType * >( type ) ) { - return new TupleIterator( tt ); - } else { - return new SimpleIterator( type ); - } - } - - CurrentObject::CurrentObject() {} - CurrentObject::CurrentObject( Type * type ) { - objStack.push( new SimpleIterator( type ) ); - } - - - void CurrentObject::setNext( Designation * designation ) { - assertf( ! objStack.empty(), "obj stack empty in setNext" ); - PRINT( std::cerr << "____setNext" << designation << std::endl; ) - objStack.top()->setPosition( designation->get_designators() ); - } - - Designation * CurrentObject::findNext( Designation * designation ) { - typedef std::list< Expression * > DesignatorChain; - PRINT( std::cerr << "___findNext" << std::endl; ) - // find all the d's - std::list desigAlts{ { } }, newDesigAlts; - std::list curTypes { (objStack.top())->getType() }, newTypes; - for ( Expression * expr : designation->get_designators() ) { - PRINT( std::cerr << "____untyped: " << expr << std::endl; ) - std::list::iterator dit = desigAlts.begin(); - if ( NameExpr * nexpr = dynamic_cast(expr) ) { - for ( Type * t : curTypes ) { - assert( dit != desigAlts.end() ); - DesignatorChain & d = *dit; - PRINT( std::cerr << "____actual: " << t << std::endl; ) - ReferenceToType * refType = dynamic_cast(t); - std::list members; - if ( refType ) { - refType->lookup( nexpr->get_name(), members ); // concatenate identical field name - // xxx - need to also include anonymous members in this somehow... - for ( Declaration * mem: members ) { - if ( ObjectDecl * field = dynamic_cast(mem) ) { - PRINT( std::cerr << "____alt: " << field->get_type() << std::endl; ) - DesignatorChain newD = d; - newD.push_back( new VariableExpr( field ) ); - newDesigAlts.push_back( newD ); - newTypes.push_back( field->get_type() ); - } // if - } // for - } // if - ++dit; - } // for - } else { - for ( Type * t : curTypes ) { - assert( dit != desigAlts.end() ); - DesignatorChain & d = *dit; - if ( ArrayType * at = dynamic_cast< ArrayType * > ( t ) ) { - PRINT( std::cerr << "____alt: " << at->get_base() << std::endl; ) - d.push_back( expr ); - newDesigAlts.push_back( d ); - newTypes.push_back( at->get_base() ); - } - ++dit; - } // for - } // if - desigAlts = newDesigAlts; - newDesigAlts.clear(); - curTypes = newTypes; - newTypes.clear(); - assertf( desigAlts.size() == curTypes.size(), "Designator alternatives (%zu) and current types (%zu) out of sync", desigAlts.size(), curTypes.size() ); - } // for - if ( desigAlts.size() > 1 ) { - SemanticError( designation, toString("Too many alternatives (", desigAlts.size(), ") for designation: ") ); - } else if ( desigAlts.size() == 0 ) { - SemanticError( designation, "No reasonable alternatives for designation: " ); - } - DesignatorChain & d = desigAlts.back(); - PRINT( for ( Expression * expr : d ) { - std::cerr << "____desig: " << expr << std::endl; - } ) // for - assertf( ! curTypes.empty(), "empty designator chosen"); - - // set new designators - assertf( ! objStack.empty(), "empty object stack when setting designation" ); - Designation * actualDesignation = new Designation( d ); - objStack.top()->setPosition( d ); // destroys d - return actualDesignation; - } - - void CurrentObject::increment() { - PRINT( std::cerr << "____increment" << std::endl; ) - if ( ! objStack.empty() ) { - PRINT( std::cerr << *objStack.top() << std::endl; ) - objStack.top()->smallStep(); - } - } - - void CurrentObject::enterListInit() { - PRINT( std::cerr << "____entering list init" << std::endl; ) - assertf( ! objStack.empty(), "empty obj stack entering list init" ); - Type * type = objStack.top()->getNext(); - if ( type ) { - objStack.push( createMemberIterator( type ) ); - } else { - assertf( false, "not sure about this case..." ); - } - } - - void CurrentObject::exitListInit() { - PRINT( std::cerr << "____exiting list init" << std::endl; ) - assertf( ! objStack.empty(), "objstack empty" ); - delete objStack.top(); - objStack.pop(); - if ( ! objStack.empty() ) { - PRINT( std::cerr << *objStack.top() << std::endl; ) - objStack.top()->bigStep(); - } - } - - std::list< InitAlternative > CurrentObject::getOptions() { - PRINT( std::cerr << "____getting current options" << std::endl; ) - assertf( ! objStack.empty(), "objstack empty in getOptions" ); - return **objStack.top(); - } - - Type * CurrentObject::getCurrentType() { - PRINT( std::cerr << "____getting current type" << std::endl; ) - assertf( ! objStack.empty(), "objstack empty in getCurrentType" ); - return objStack.top()->getNext(); - } -} // namespace ResolvExpr namespace ast { Index: src/ResolvExpr/ExplodedActual.cc =================================================================== --- src/ResolvExpr/ExplodedActual.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,31 +1,0 @@ -// -// 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. -// -// ExplodedActual.cc -- -// -// Author : Aaron B. Moss -// Created On : Tue Nov 22 17:06:00 2017 -// Last Modified By : Aaron B. Moss -// Last Modified On : Tue Nov 22 17:06:00 2017 -// Update Count : 1 -// - -#include "ExplodedActual.h" - -#include "Tuples/Explode.h" // for Tuples::explode - -namespace ResolvExpr { - ExplodedActual::ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ) - : env(actual.env), cost(actual.cost), exprs() { - Tuples::explode( actual, indexer, *this ); - } -} - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/ExplodedActual.h =================================================================== --- src/ResolvExpr/ExplodedActual.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,44 +1,0 @@ -// -// 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. -// -// ExplodedActual.h -- -// -// Author : Aaron B. Moss -// Created On : Tue Nov 22 17:06:00 2017 -// Last Modified By : Aaron B. Moss -// Last Modified On : Tue Nov 22 17:06:00 2017 -// Update Count : 1 -// - -#pragma once - -#include -#include - -#include "Alternative.h" // for Alternative, AltList -#include "Cost.h" // for Cost -#include "TypeEnvironment.h" // for TypeEnvironment -#include "SymTab/Indexer.h" // for Indexer - -namespace ResolvExpr { - /// Pre-exploded actual - struct ExplodedActual { - TypeEnvironment env; - Cost cost; - std::vector< std::unique_ptr > exprs; - - ExplodedActual() : env(), cost(Cost::zero), exprs() {} - ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ); - ExplodedActual(ExplodedActual&&) = default; - ExplodedActual& operator= (ExplodedActual&&) = default; - }; -} - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/FindOpenVars.cc =================================================================== --- src/ResolvExpr/FindOpenVars.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/FindOpenVars.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -16,86 +16,11 @@ #include "FindOpenVars.h" -#include // for _List_const_iterator, list<>::const... -#include // for map<>::mapped_type - #include "AST/Pass.hpp" #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" -#include "SynTree/Declaration.h" // for TypeDecl, DeclarationWithType (ptr ... -#include "SynTree/Type.h" // for Type, Type::ForallList, ArrayType #include namespace ResolvExpr { - struct FindOpenVars_old : public WithGuards { - FindOpenVars_old( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); - - void previsit( const PointerType * pointerType ); - void previsit( const ArrayType * arrayType ); - void previsit( const FunctionType * functionType ); - void previsit( const TupleType * tupleType ); - - void common_action( const Type *type ); - - OpenVarSet &openVars, &closedVars; - AssertionSet &needAssertions, &haveAssertions; - bool nextIsOpen; - }; - - void findOpenVars( const Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) { - PassVisitor finder( openVars, closedVars, needAssertions, haveAssertions, firstIsOpen ); - type->accept( finder ); - } - - FindOpenVars_old::FindOpenVars_old( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) - : openVars( openVars ), closedVars( closedVars ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), nextIsOpen( firstIsOpen ) { - } - - void FindOpenVars_old::common_action( const Type * type ) { - if ( nextIsOpen ) { - for ( Type::ForallList::const_iterator i = type->forall.begin(); i != type->forall.end(); ++i ) { - openVars[ (*i)->get_name() ] = TypeDecl::Data{ (*i) }; - for ( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) { - needAssertions[ *assert ].isUsed = false; - } -/// cloneAll( (*i)->get_assertions(), needAssertions ); -/// needAssertions.insert( needAssertions.end(), (*i)->get_assertions().begin(), (*i)->get_assertions().end() ); - } - } else { - for ( Type::ForallList::const_iterator i = type->forall.begin(); i != type->forall.end(); ++i ) { - closedVars[ (*i)->get_name() ] = TypeDecl::Data{ (*i) }; - for ( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) { - haveAssertions[ *assert ].isUsed = false; - } -/// cloneAll( (*i)->get_assertions(), haveAssertions ); -/// haveAssertions.insert( haveAssertions.end(), (*i)->get_assertions().begin(), (*i)->get_assertions().end() ); - } // for - } // if -/// std::cerr << "type is "; -/// type->print( std::cerr ); -/// std::cerr << std::endl << "need is" << std::endl; -/// printAssertionSet( needAssertions, std::cerr ); -/// std::cerr << std::endl << "have is" << std::endl; -/// printAssertionSet( haveAssertions, std::cerr ); - } - - void FindOpenVars_old::previsit(const PointerType * pointerType) { - common_action( pointerType ); - } - - void FindOpenVars_old::previsit(const ArrayType * arrayType) { - common_action( arrayType ); - } - - void FindOpenVars_old::previsit(const FunctionType * functionType) { - common_action( functionType ); - nextIsOpen = ! nextIsOpen; - GuardAction( [this](){ nextIsOpen = ! nextIsOpen; } ); - } - - void FindOpenVars_old::previsit(const TupleType * tupleType) { - common_action( tupleType ); - } namespace { Index: src/ResolvExpr/FindOpenVars.h =================================================================== --- src/ResolvExpr/FindOpenVars.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/FindOpenVars.h (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -17,7 +17,5 @@ #include "AST/TypeEnvironment.hpp" // for AssertionSet, OpenVarSet -#include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet -class Type; namespace ast { class Type; @@ -25,7 +23,4 @@ namespace ResolvExpr { - // Updates open and closed variables and their associated assertions - void findOpenVars( const Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); - enum FirstMode { FirstClosed, FirstOpen }; Index: src/ResolvExpr/Occurs.cc =================================================================== --- src/ResolvExpr/Occurs.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,68 +1,0 @@ -// -// 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. -// -// Occurs.cc -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 09:47:41 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sun May 17 09:49:26 2015 -// Update Count : 2 -// - -#include // for set, _Rb_tree_const_iterator -#include // for string - -#include "Common/PassVisitor.h" -#include "SynTree/Type.h" // for TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment - -namespace ResolvExpr { - struct Occurs : public WithVisitorRef { - Occurs( std::string varName, const TypeEnvironment &env ); - void previsit( const TypeInstType * typeInst ); - - bool result; - std::set< std::string > eqvVars; - const TypeEnvironment &tenv; - }; - - bool occurs( const Type *type, const std::string & varName, const TypeEnvironment &env ) { - PassVisitor occur( varName, env ); - type->accept( occur ); - return occur.pass.result; - } - - Occurs::Occurs( std::string varName, const TypeEnvironment & env ) : result( false ), tenv( env ) { - if ( const EqvClass *eqvClass = tenv.lookup( varName ) ) { - eqvVars = eqvClass->vars; - } else { - eqvVars.insert( varName ); - } // if - } - - void Occurs::previsit( const TypeInstType * typeInst ) { - /// std::cerr << "searching for vars: "; -/// std::copy( eqvVars.begin(), eqvVars.end(), std::ostream_iterator< std::string >( std::cerr, " " ) ); -/// std::cerr << std::endl; - if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) { - result = true; - } else if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { - if ( eqvClass->type ) { -/// std::cerr << typeInst->get_name() << " is bound to"; -/// eqvClass.type->print( std::cerr ); -/// std::cerr << std::endl; - eqvClass->type->accept( *visitor ); - } // if - } // if - } -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/PolyCost.cc =================================================================== --- src/ResolvExpr/PolyCost.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/PolyCost.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -18,43 +18,6 @@ #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Type.h" // for TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment namespace ResolvExpr { - struct PolyCost { - PolyCost( const TypeEnvironment &env, const SymTab::Indexer &indexer ); - - void previsit( TypeInstType * aggregateUseType ); - int result; - const TypeEnvironment &tenv; - const SymTab::Indexer &indexer; - }; - - int polyCost( Type *type, const TypeEnvironment & env, const SymTab::Indexer &indexer ) { - PassVisitor coster( env, indexer ); - type->accept( coster ); - return (coster.pass.result > 0) ? 1 : 0; - } - - PolyCost::PolyCost( const TypeEnvironment & env, const SymTab::Indexer & indexer ) : result( 0 ), tenv( env ), indexer( indexer ) { - } - - void PolyCost::previsit(TypeInstType * typeInst) { - if ( const EqvClass *eqvClass = tenv.lookup( typeInst->name ) ) { - if ( eqvClass->type ) { - if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass->type ) ) { - if ( indexer.lookupType( otherTypeInst->name ) ) { - // bound to opaque type - result += 1; - } // if - } else { - // bound to concrete type - result += 1; - } // if - } // if - } // if - } // TODO: When the old PolyCost is torn out get rid of the _new suffix. Index: src/ResolvExpr/PtrsAssignable.cc =================================================================== --- src/ResolvExpr/PtrsAssignable.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/PtrsAssignable.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -19,96 +19,6 @@ #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment -#include "SynTree/Type.h" // for TypeInstType, Type, BasicType -#include "SynTree/Visitor.h" // for Visitor - namespace ResolvExpr { - struct PtrsAssignable : public WithShortCircuiting { - PtrsAssignable( const Type * dest, const TypeEnvironment &env ); - - int get_result() const { return result; } - - void previsit( const Type * ) { visit_children = false; } - - void postvisit( const VoidType * voidType ); - void postvisit( const BasicType * basicType ); - void postvisit( const PointerType * pointerType ); - void postvisit( const ArrayType * arrayType ); - void postvisit( const FunctionType * functionType ); - void postvisit( const StructInstType * inst ); - void postvisit( const UnionInstType * inst ); - void postvisit( const EnumInstType * inst ); - void postvisit( const TraitInstType * inst ); - void postvisit( const TypeInstType * inst ); - void postvisit( const TupleType * tupleType ); - void postvisit( const VarArgsType * varArgsType ); - void postvisit( const ZeroType * zeroType ); - void postvisit( const OneType * oneType ); - private: - const Type * dest; - int result; - const TypeEnvironment &env; - }; - - int ptrsAssignable( const Type *src, const Type * dest, const TypeEnvironment &env ) { - // std::cerr << "assignable: " << src << " | " << dest << std::endl; - if ( const TypeInstType * destAsTypeInst = dynamic_cast< const TypeInstType* >( dest ) ) { - if ( const EqvClass * eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { - return ptrsAssignable( src, eqvClass->type, env ); - } // if - } // if - if ( dynamic_cast< const VoidType* >( dest ) ) { - // void * = T * for any T is unsafe - // xxx - this should be safe, but that currently breaks the build - return -1; - } else { - PassVisitor ptrs( dest, env ); - src->accept( ptrs ); - return ptrs.pass.get_result(); - } // if - } - - PtrsAssignable::PtrsAssignable( const Type * dest, const TypeEnvironment &env ) : dest( dest ), result( 0 ), env( env ) {} - - void PtrsAssignable::postvisit( const VoidType * ) { - // T * = void * is disallowed - this is a change from C, where any - // void * can be assigned or passed to a non-void pointer without a cast. - } - - void PtrsAssignable::postvisit( const BasicType * ) {} - void PtrsAssignable::postvisit( const PointerType * ) {} - void PtrsAssignable::postvisit( const ArrayType * ) {} - void PtrsAssignable::postvisit( const FunctionType * ) {} - - void PtrsAssignable::postvisit( const StructInstType * ) {} - void PtrsAssignable::postvisit( const UnionInstType * ) {} - - void PtrsAssignable::postvisit( const EnumInstType * ) { - if ( dynamic_cast< const BasicType* >( dest ) ) { - // int * = E *, etc. is safe. This isn't technically correct, as each - // enum has one basic type that it is compatible with, an that type can - // differ from enum to enum. Without replicating GCC's internal logic, - // there is no way to know which type this particular enum is compatible - // with, so punt on this for now. - result = 1; - } - } - - void PtrsAssignable::postvisit( const TraitInstType * ) {} - void PtrsAssignable::postvisit( const TypeInstType * inst ) { - if ( const EqvClass * eqvClass = env.lookup( inst->name ) ) { - if ( eqvClass->type ) { - // T * = S * for any S depends on the type bound to T - result = ptrsAssignable( eqvClass->type, dest, env ); - } - } // if - } - - void PtrsAssignable::postvisit( const TupleType * ) {} - void PtrsAssignable::postvisit( const VarArgsType * ) {} - void PtrsAssignable::postvisit( const ZeroType * ) {} - void PtrsAssignable::postvisit( const OneType * ) {} // TODO: Get rid of the `_new` suffix when the old version is removed. Index: src/ResolvExpr/PtrsCastable.cc =================================================================== --- src/ResolvExpr/PtrsCastable.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/PtrsCastable.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -20,151 +20,7 @@ #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" #include "ResolvExpr/PtrsAssignable.hpp" // for ptrsAssignable -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment -#include "SymTab/Indexer.h" // for Indexer -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Kind::Ftype -#include "SynTree/Type.h" // for TypeInstType, Type, BasicType -#include "SynTree/Visitor.h" // for Visitor namespace ResolvExpr { - struct PtrsCastable_old : public WithShortCircuiting { - public: - PtrsCastable_old( const Type * dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ); - - int get_result() const { return result; } - - void previsit( const Type * ) { visit_children = false; } - - void postvisit( const VoidType * voidType ); - void postvisit( const BasicType * basicType ); - void postvisit( const PointerType * pointerType ); - void postvisit( const ArrayType * arrayType ); - void postvisit( const FunctionType * functionType ); - void postvisit( const StructInstType * inst ); - void postvisit( const UnionInstType * inst ); - void postvisit( const EnumInstType * inst ); - void postvisit( const TraitInstType * inst ); - void postvisit( const TypeInstType * inst ); - void postvisit( const TupleType * tupleType ); - void postvisit( const VarArgsType * varArgsType ); - void postvisit( const ZeroType * zeroType ); - void postvisit( const OneType * oneType ); - private: - const Type * dest; - int result; - const TypeEnvironment &env; - const SymTab::Indexer &indexer; - }; - - namespace { - int objectCast( const Type * src, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { - if ( dynamic_cast< const FunctionType* >( src ) ) { - return -1; - } else if ( const TypeInstType * typeInst = dynamic_cast< const TypeInstType* >( src ) ) { - if ( const NamedTypeDecl * ntDecl = indexer.lookupType( typeInst->name ) ) { - if ( const TypeDecl * tyDecl = dynamic_cast< const TypeDecl* >( ntDecl ) ) { - if ( tyDecl->kind == TypeDecl::Ftype ) { - return -1; - } // if - } //if - } else if ( const EqvClass * eqvClass = env.lookup( typeInst->get_name() ) ) { - if ( eqvClass->data.kind == TypeDecl::Ftype ) { - return -1; - } // if - } // if - } //if - return 1; - } - int functionCast( const Type * src, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { - return -1 * objectCast( src, env, indexer ); // reverse the sense of objectCast - } - } - - int ptrsCastable( const Type * src, const Type * dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { - if ( const TypeInstType * destAsTypeInst = dynamic_cast< const TypeInstType* >( dest ) ) { - if ( const EqvClass * eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { - // xxx - should this be ptrsCastable? - return ptrsAssignable( src, eqvClass->type, env ); - } // if - } // if - if ( dynamic_cast< const VoidType* >( dest ) ) { - return objectCast( src, env, indexer ); - } else { - PassVisitor ptrs( dest, env, indexer ); - src->accept( ptrs ); - return ptrs.pass.get_result(); - } // if - } - - PtrsCastable_old::PtrsCastable_old( const Type * dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) - : dest( dest ), result( 0 ), env( env ), indexer( indexer ) { - } - - void PtrsCastable_old::postvisit( const VoidType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const BasicType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const PointerType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const ArrayType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const FunctionType * ) { - // result = -1; - result = functionCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const StructInstType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const UnionInstType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const EnumInstType * ) { - if ( dynamic_cast< const EnumInstType * >( dest ) ) { - result = 1; - } else if ( const BasicType * bt = dynamic_cast< const BasicType * >( dest ) ) { - if ( bt->kind == BasicType::SignedInt ) { - result = 0; - } else { - result = 1; - } - } else { - result = objectCast( dest, env, indexer ); - } - } - - void PtrsCastable_old::postvisit( const TraitInstType * ) {} - - void PtrsCastable_old::postvisit( const TypeInstType *inst ) { - //result = objectCast( inst, env, indexer ) > 0 && objectCast( dest, env, indexer ) > 0 ? 1 : -1; - result = objectCast( inst, env, indexer ) == objectCast( dest, env, indexer ) ? 1 : -1; - } - - void PtrsCastable_old::postvisit( const TupleType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const VarArgsType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const ZeroType * ) { - result = objectCast( dest, env, indexer ); - } - - void PtrsCastable_old::postvisit( const OneType * ) { - result = objectCast( dest, env, indexer ); - } namespace { Index: src/ResolvExpr/RenameVars.cc =================================================================== --- src/ResolvExpr/RenameVars.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/RenameVars.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -21,12 +21,7 @@ #include "AST/Pass.hpp" #include "AST/Type.hpp" -#include "Common/PassVisitor.h" #include "Common/ScopedMap.h" #include "Common/SemanticError.h" // for SemanticError #include "RenameVars.h" -#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec... -#include "SynTree/Expression.h" // for Expression -#include "SynTree/Type.h" // for Type, TypeInstType, TraitInstType -#include "SynTree/Visitor.h" // for acceptAll, maybeAccept #include "AST/Copy.hpp" @@ -49,35 +44,6 @@ } - void rename( TypeInstType * type ) { - auto it = nameMap.find( type->name ); - if ( it != nameMap.end() ) { - type->name = it->second; - } - } - void nextUsage() { ++next_usage_id; - } - - void openLevel( Type * type ) { - if ( ! type->forall.empty() ) { - nameMap.beginScope(); - // renames all "forall" type names to `_${level}_${name}' - for ( auto td : type->forall ) { - std::ostringstream output; - output << "_" << resetCount << "_" << level << "_" << td->name; - std::string newname( output.str() ); - nameMap[ td->get_name() ] = newname; - td->name = newname; - // ditto for assertion names, the next level in - level++; - } - } - } - - void closeLevel( Type * type ) { - if ( !type->forall.empty() ) { - nameMap.endScope(); - } } @@ -135,17 +101,4 @@ RenamingData renaming; - struct RenameVars_old { - void previsit( TypeInstType * instType ) { - renaming.openLevel( (Type*)instType ); - renaming.rename( instType ); - } - void previsit( Type * type ) { - renaming.openLevel( type ); - } - void postvisit( Type * type ) { - renaming.closeLevel( type ); - } - }; - struct RenameVars_new : public ast::PureVisitor /*: public ast::WithForallSubstitutor*/ { RenameMode mode; @@ -178,9 +131,4 @@ } // namespace -void renameTyVars( Type * t ) { - PassVisitor renamer; - t->accept( renamer ); -} - const ast::Type * renameTyVars( const ast::Type * t, RenameMode mode, bool reset ) { ast::Pass renamer; Index: src/ResolvExpr/RenameVars.h =================================================================== --- src/ResolvExpr/RenameVars.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/RenameVars.h (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -16,11 +16,4 @@ #pragma once -#include // for list -#include // for map -#include // for string - -#include "SynTree/SynTree.h" // for Visitor Nodes -#include "SynTree/Visitor.h" // for Visitor - namespace ast { class Type; @@ -28,7 +21,4 @@ namespace ResolvExpr { - /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID - void renameTyVars( Type * ); - enum RenameMode { GEN_USAGE, // for type in VariableExpr Index: src/ResolvExpr/ResolveAssertions.cc =================================================================== --- src/ResolvExpr/ResolveAssertions.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,535 +1,0 @@ -// -// 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. -// -// ResolveAssertions.cc -- -// -// Author : Aaron B. Moss -// Created On : Fri Oct 05 13:46:00 2018 -// Last Modified By : Andrew Beach -// Last Modified On : Thu Aug 8 16:47:00 2019 -// Update Count : 3 -// - -#include "ResolveAssertions.h" - -#include // for sort -#include // for assertf -#include // for list -#include // for unique_ptr -#include // for ostringstream -#include // for string -#include // for unordered_map, unordered_multimap -#include // for move -#include // for vector - -#include "AdjustExprType.hpp" // for adjustExprType -#include "Alternative.h" // for Alternative, AssertionItem, AssertionList -#include "Common/FilterCombos.h" // for filterCombos -#include "Common/Indenter.h" // for Indenter -#include "GenPoly/GenPoly.h" // for getFunctionType -#include "ResolvExpr/AlternativeFinder.h" // for computeConversionCost -#include "ResolvExpr/RenameVars.h" // for renameTyVars -#include "SpecCost.hpp" // for specCost -#include "SymTab/Indexer.h" // for Indexer -#include "SymTab/Mangler.h" // for Mangler -#include "SynTree/Expression.h" // for InferredParams -#include "TypeEnvironment.h" // for TypeEnvironment, etc. -#include "Unify.h" // for unify - -namespace ResolvExpr { - /// Unified assertion candidate - struct AssnCandidate { - SymTab::Indexer::IdData cdata; ///< Satisfying declaration - Type* adjType; ///< Satisfying type - TypeEnvironment env; ///< Post-unification environment - AssertionSet have; ///< Post-unification have-set - AssertionSet need; ///< Post-unification need-set - OpenVarSet openVars; ///< Post-unification open-var set - UniqueId resnSlot; ///< Slot for any recursive assertion IDs - - AssnCandidate( const SymTab::Indexer::IdData& cdata, Type* adjType, TypeEnvironment&& env, - AssertionSet&& have, AssertionSet&& need, OpenVarSet&& openVars, UniqueId resnSlot ) - : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), - need(std::move(need)), openVars(std::move(openVars)), resnSlot(resnSlot) {} - }; - - /// List of candidate assertion resolutions - using CandidateList = std::vector; - - /// Reference to single deferred item - struct DeferRef { - const DeclarationWithType* decl; - const AssertionSetValue& info; - const AssnCandidate& match; - }; - - /// Wrapper for the deferred items from a single assertion resolution. - /// Acts like indexed list of DeferRef - struct DeferItem { - const DeclarationWithType* decl; - const AssertionSetValue& info; - CandidateList matches; - - DeferItem( const DeclarationWithType* decl, const AssertionSetValue& info, CandidateList&& matches ) - : decl(decl), info(info), matches(std::move(matches)) {} - - bool empty() const { return matches.empty(); } - - CandidateList::size_type size() const { return matches.size(); } - - DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; } - }; - - /// List of deferred resolution items - using DeferList = std::vector; - - /// Combo iterator that combines candidates into an output list, merging their environments. - /// Rejects an appended candidate if the environments cannot be merged. - class CandidateEnvMerger { - /// Current list of merged candidates - std::vector crnt; - /// Stack of environments to support backtracking - std::vector envs; - /// Stack of open variables to support backtracking - std::vector varSets; - /// Indexer to use for merges - const SymTab::Indexer& indexer; - - public: - /// The merged environment/open variables and the list of candidates - struct OutType { - TypeEnvironment env; - OpenVarSet openVars; - std::vector assns; - Cost cost; - - OutType( const TypeEnvironment& env, const OpenVarSet& openVars, - const std::vector& assns ) - : env(env), openVars(openVars), assns(assns), cost(Cost::infinity) {} - }; - - CandidateEnvMerger( const TypeEnvironment& env, const OpenVarSet& openVars, - const SymTab::Indexer& indexer ) - : crnt(), envs{ env }, varSets{ openVars }, indexer(indexer) {} - - bool append( DeferRef i ) { - TypeEnvironment env = envs.back(); - OpenVarSet openVars = varSets.back(); - mergeOpenVars( openVars, i.match.openVars ); - - if ( ! env.combine( i.match.env, openVars, indexer ) ) return false; - - crnt.emplace_back( i ); - envs.emplace_back( env ); - varSets.emplace_back( openVars ); - return true; - } - - void backtrack() { - crnt.pop_back(); - envs.pop_back(); - varSets.pop_back(); - } - - OutType finalize() { return { envs.back(), varSets.back(), crnt }; } - }; - - /// Comparator for CandidateEnvMerger outputs that sums their costs and caches the stored - /// sums - struct CandidateCost { - using Element = CandidateEnvMerger::OutType; - private: - const SymTab::Indexer& indexer; ///< Indexer for costing - - public: - CandidateCost( const SymTab::Indexer& indexer ) : indexer(indexer) {} - - /// reports the cost of an element - Cost get( Element& x ) const { - // check cached cost - if ( x.cost != Cost::infinity ) return x.cost; - - // generate cost - Cost k = Cost::zero; - for ( const auto& assn : x.assns ) { - // compute conversion cost from satisfying decl to assertion - k += computeConversionCost( - assn.match.adjType, assn.decl->get_type(), false, indexer, x.env ); - - // mark vars+specialization cost on function-type assertions - FunctionType* func = GenPoly::getFunctionType( assn.match.cdata.id->get_type() ); - if ( ! func ) continue; - - for ( DeclarationWithType* formal : func->parameters ) { - k.decSpec( specCost( formal->get_type() ) ); - } - k.incVar( func->forall.size() ); - for ( TypeDecl* td : func->forall ) { - k.decSpec( td->assertions.size() ); - } - } - - // cache and return - x.cost = k; - return k; - } - - /// compares elements by cost - bool operator() ( Element& a, Element& b ) const { - return get( a ) < get( b ); - } - }; - - /// Set of assertion resolutions, grouped by resolution ID - using InferCache = std::unordered_map< UniqueId, InferredParams >; - - /// Lexicographically-ordered vector of costs - using CostVec = std::vector< Cost >; - - int compare( const CostVec & a, const CostVec & b ) { - unsigned i = 0; - do { - // lex-compare where shorter one is less - if ( i == a.size() ) { - return i == b.size() ? 0 : -1; - } - if ( i == b.size() /* && i < a.size() */ ) return 1; - - int c = a[i].compare( b[i] ); - if ( c != 0 ) return c; - } while ( ++i ); - assert(!"unreachable"); - } - - bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; } - - /// Flag for state iteration - enum IterateFlag { IterateState }; - - /// State needed to resolve a set of assertions - struct ResnState { - Alternative alt; ///< Alternative assertion is rooted on - AssertionList need; ///< Assertions to find - AssertionSet newNeed; ///< New assertions for current resolutions - DeferList deferred; ///< Deferred matches - InferCache inferred; ///< Cache of already-inferred parameters - CostVec costs; ///< Costs of recursive assertion satisfaction for disambiguation - SymTab::Indexer& indexer; ///< Name lookup (depends on previous assertions) - - /// Initial resolution state for an alternative - ResnState( Alternative & a, SymTab::Indexer & indexer ) - : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) { - need.swap( a.need ); - } - - /// Updated resolution state with new need-list - ResnState( ResnState && o, IterateFlag ) - : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(), - inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) { - costs.emplace_back( Cost::zero ); - } - }; - - /// Binds a single assertion, updating resolution state - void bindAssertion( const DeclarationWithType * decl, AssertionSetValue info, Alternative & alt, - AssnCandidate & match, InferCache & inferred ) { - - const DeclarationWithType * candidate = match.cdata.id; - assertf( candidate->uniqueId, "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() ); - - Expression * varExpr = match.cdata.combine( alt.cvtCost ); - delete varExpr->result; - varExpr->result = match.adjType->clone(); - if ( match.resnSlot ) { varExpr->resnSlots.push_back( match.resnSlot ); } - - // place newly-inferred assertion in proper place in cache - inferred[ info.resnSlot ][ decl->get_uniqueId() ] = ParamEntry{ - candidate->uniqueId, candidate->clone(), match.adjType->clone(), decl->get_type()->clone(), - varExpr }; - } - - /// Adds a captured assertion to the symbol table - void addToIndexer( AssertionSet & assertSet, SymTab::Indexer & indexer ) { - for ( auto& i : assertSet ) { - if ( i.second.isUsed ) { - indexer.addId( i.first ); - } - } - } - - // in AlternativeFinder.cc; unique ID for assertion resolutions - extern UniqueId globalResnSlot; - - /// Resolve a single assertion, in context - bool resolveAssertion( AssertionItem & assn, ResnState & resn ) { - // skip unused assertions - if ( ! assn.info.isUsed ) return true; - - // lookup candidates for this assertion - std::list< SymTab::Indexer::IdData > candidates; - resn.indexer.lookupId( assn.decl->name, candidates ); - - // find the candidates that unify with the desired type - CandidateList matches; - for ( const auto & cdata : candidates ) { - const DeclarationWithType * candidate = cdata.id; - - // ignore deleted candidates. - // NOTE: this behavior is different from main resolver. - // further investigations might be needed to determine - // if we should implement the same rule here - // (i.e. error if unique best match is deleted) - if (candidate->isDeleted) continue; - - // build independent unification context. for candidate - AssertionSet have, newNeed; - TypeEnvironment newEnv{ resn.alt.env }; - OpenVarSet newOpenVars{ resn.alt.openVars }; - Type * adjType = candidate->get_type()->clone(); - adjustExprType( adjType, newEnv, resn.indexer ); - renameTyVars( adjType ); - - // keep unifying candidates - if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, - resn.indexer ) ) { - // set up binding slot for recursive assertions - UniqueId crntResnSlot = 0; - if ( ! newNeed.empty() ) { - crntResnSlot = ++globalResnSlot; - for ( auto& a : newNeed ) { - a.second.resnSlot = crntResnSlot; - } - } - - matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), - std::move(newNeed), std::move(newOpenVars), crntResnSlot ); - } else { - delete adjType; - } - } - - // break if no suitable assertion - if ( matches.empty() ) return false; - - // defer if too many suitable assertions - if ( matches.size() > 1 ) { - resn.deferred.emplace_back( assn.decl, assn.info, std::move(matches) ); - return true; - } - - // otherwise bind current match in ongoing scope - AssnCandidate& match = matches.front(); - addToIndexer( match.have, resn.indexer ); - resn.newNeed.insert( match.need.begin(), match.need.end() ); - resn.alt.env = std::move(match.env); - resn.alt.openVars = std::move(match.openVars); - - bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred ); - return true; - } - - /// Associates inferred parameters with an expression - struct InferMatcher { - InferCache& inferred; - - InferMatcher( InferCache& inferred ) : inferred( inferred ) {} - - Expression* postmutate( Expression* expr ) { - // defer missing inferred parameters until they are hopefully found later - std::vector missingSlots; - // place inferred parameters into resolution slots - for ( UniqueId slot : expr->resnSlots ) { - // fail if no matching parameters found - auto it = inferred.find( slot ); - if ( it == inferred.end() ) { - missingSlots.push_back( slot ); - continue; - } - InferredParams& inferParams = it->second; - - // place inferred parameters into proper place in expression - for ( auto& entry : inferParams ) { - // recurse on inferParams of resolved expressions - entry.second.expr = postmutate( entry.second.expr ); - // xxx - look at entry.second.inferParams? - auto res = expr->inferParams.emplace( entry.first, entry.second ); - assert(res.second); - } - } - - // clear resolution slots and return - expr->resnSlots.swap( missingSlots ); - return expr; - } - }; - - /// Map of alternative return types to recursive assertion satisfaction costs - using PruneMap = std::unordered_map; - - /// Gets the pruning key for an alternative - std::string pruneKey( const Alternative & alt ) { - Type* resType = alt.expr->result->clone(); - alt.env.apply( resType ); - std::string resKey = SymTab::Mangler::mangleType( resType ); - delete resType; - return resKey; - } - - /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning - /// threshold. - void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) { - // prune if cheaper alternative for same key has already been generated - std::string resKey = pruneKey( resn.alt ); - auto it = pruneThresholds.find( resKey ); - if ( it != pruneThresholds.end() ) { - if ( it->second < resn.costs ) return; - } else { - pruneThresholds.emplace_hint( it, resKey, resn.costs ); - } - - // replace resolution slots with inferred params, add to output - PassVisitor matcher{ resn.inferred }; - resn.alt.expr = resn.alt.expr->acceptMutator( matcher ); - out.emplace_back( resn.alt ); - } - - /// Limit to depth of recursion of assertion satisfaction - static const int recursionLimit = 7; - /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of - static const int deferLimit = 10; - - void resolveAssertions( Alternative& alt, const SymTab::Indexer& indexer, AltList& out, std::list& errors ) { - // finish early if no assertions to resolve - if ( alt.need.empty() ) { - out.emplace_back( alt ); - return; - } - - // build list of possible resolutions - using ResnList = std::vector; - SymTab::Indexer root_indexer{ indexer }; - ResnList resns{ ResnState{ alt, root_indexer } }; - ResnList new_resns{}; - - // Pruning thresholds by result type of the output alternatives. - // Alternatives *should* be generated in sorted order, so no need to retroactively prune - PruneMap thresholds; - - // resolve assertions in breadth-first-order up to a limited number of levels deep - for ( unsigned level = 0; level < recursionLimit; ++level ) { - // scan over all mutually-compatible resolutions - for ( auto& resn : resns ) { - // stop this branch if already found a better option - auto it = thresholds.find( pruneKey( resn.alt ) ); - if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn; - - // make initial pass at matching assertions - for ( auto& assn : resn.need ) { - // fail early if any assertion is not resolvable - if ( ! resolveAssertion( assn, resn ) ) { - Indenter tabs{ 3 }; - std::ostringstream ss; - ss << tabs << "Unsatisfiable alternative:\n"; - resn.alt.print( ss, ++tabs ); - ss << (tabs-1) << "Could not satisfy assertion:\n"; - assn.decl->print( ss, tabs ); - - errors.emplace_back( ss.str() ); - goto nextResn; - } - } - - if ( resn.deferred.empty() ) { - // either add successful match or push back next state - if ( resn.newNeed.empty() ) { - finalizeAssertions( resn, thresholds, out ); - } else { - new_resns.emplace_back( std::move(resn), IterateState ); - } - } else if ( resn.deferred.size() > deferLimit ) { - // too many deferred assertions to attempt mutual compatibility - Indenter tabs{ 3 }; - std::ostringstream ss; - ss << tabs << "Unsatisfiable alternative:\n"; - resn.alt.print( ss, ++tabs ); - ss << (tabs-1) << "Too many non-unique satisfying assignments for " - "assertions:\n"; - for ( const auto& d : resn.deferred ) { - d.decl->print( ss, tabs ); - } - - errors.emplace_back( ss.str() ); - goto nextResn; - } else { - // resolve deferred assertions by mutual compatibility - std::vector compatible = filterCombos( - resn.deferred, - CandidateEnvMerger{ resn.alt.env, resn.alt.openVars, resn.indexer } ); - // fail early if no mutually-compatible assertion satisfaction - if ( compatible.empty() ) { - Indenter tabs{ 3 }; - std::ostringstream ss; - ss << tabs << "Unsatisfiable alternative:\n"; - resn.alt.print( ss, ++tabs ); - ss << (tabs-1) << "No mutually-compatible satisfaction for assertions:\n"; - for ( const auto& d : resn.deferred ) { - d.decl->print( ss, tabs ); - } - - errors.emplace_back( ss.str() ); - goto nextResn; - } - // sort by cost for overall pruning - CandidateCost coster{ resn.indexer }; - std::sort( compatible.begin(), compatible.end(), coster ); - - for ( auto& compat : compatible ) { - ResnState new_resn = resn; - - // add compatible assertions to new resolution state - for ( DeferRef r : compat.assns ) { - AssnCandidate match = r.match; - addToIndexer( match.have, new_resn.indexer ); - new_resn.newNeed.insert( match.need.begin(), match.need.end() ); - - bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred ); - } - - // set mutual environment into resolution state - new_resn.alt.env = std::move(compat.env); - new_resn.alt.openVars = std::move(compat.openVars); - - // mark cost of this path - new_resn.costs.back() += compat.cost; - - // either add sucessful match or push back next state - if ( new_resn.newNeed.empty() ) { - finalizeAssertions( new_resn, thresholds, out ); - } else { - new_resns.emplace_back( std::move(new_resn), IterateState ); - } - } - } - nextResn:; } - - // finish or reset for next round - if ( new_resns.empty() ) return; - resns.swap( new_resns ); - new_resns.clear(); - } - - // exceeded recursion limit if reaches here - if ( out.empty() ) { - SemanticError( alt.expr->location, "Too many recursive assertions" ); - } - } -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/ResolveAssertions.h =================================================================== --- src/ResolvExpr/ResolveAssertions.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,33 +1,0 @@ -// -// 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. -// -// ResolveAssertions.h -- -// -// Author : Aaron B. Moss -// Created On : Fri Oct 05 13:46:00 2018 -// Last Modified By : Aaron B. Moss -// Last Modified On : Fri Oct 05 13:46:00 2018 -// Update Count : 1 -// - -#pragma once - -#include "Alternative.h" // for Alternative, AltList - -namespace SymTab { - class Indexer; -} - -namespace ResolvExpr { - /// Recursively resolves all assertions provided in an alternative; returns true iff succeeds - void resolveAssertions( Alternative& alt, const SymTab::Indexer& indexer, AltList& out, std::list& errors ); -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/ResolveTypeof.cc =================================================================== --- src/ResolvExpr/ResolveTypeof.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/ResolveTypeof.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -24,5 +24,4 @@ #include "AST/Type.hpp" #include "AST/TypeEnvironment.hpp" -#include "Common/PassVisitor.h" // for PassVisitor #include "Common/utility.h" // for copy #include "InitTweak/InitTweak.h" // for isConstExpr @@ -30,91 +29,6 @@ #include "Resolver.h" // for resolveInVoidContext #include "SymTab/Mangler.h" -#include "SynTree/Expression.h" // for Expression -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for TypeofType, Type - -namespace SymTab { -class Indexer; -} // namespace SymTab namespace ResolvExpr { -namespace { -#if 0 - void - printAlts( const AltList &list, std::ostream &os, int indent = 0 ) - { - for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { - i->print( os, indent ); - os << std::endl; - } - } -#endif - } - -class ResolveTypeof_old : public WithShortCircuiting { - public: - ResolveTypeof_old( const SymTab::Indexer &indexer ) : indexer( indexer ) {} - void premutate( TypeofType *typeofType ); - Type * postmutate( TypeofType *typeofType ); - - private: - const SymTab::Indexer &indexer; -}; - - Type * resolveTypeof( Type *type, const SymTab::Indexer &indexer ) { - PassVisitor mutator( indexer ); - return type->acceptMutator( mutator ); - } - - void ResolveTypeof_old::premutate( TypeofType * ) { - visit_children = false; - } - - Type * ResolveTypeof_old::postmutate( TypeofType *typeofType ) { -#if 0 - std::cerr << "resolving typeof: "; - typeofType->print( std::cerr ); - std::cerr << std::endl; -#endif - // pass on null expression - if ( ! typeofType->expr ) return typeofType; - - bool isBasetypeof = typeofType->is_basetypeof; - auto oldQuals = typeofType->get_qualifiers().val; - - Type* newType; - if ( TypeExpr* tyExpr = dynamic_cast(typeofType->expr) ) { - // typeof wrapping type - newType = tyExpr->type; - tyExpr->type = nullptr; - delete tyExpr; - } else { - // typeof wrapping expression - Expression * newExpr = resolveInVoidContext( typeofType->expr, indexer ); - assert( newExpr->result && ! newExpr->result->isVoid() ); - newType = newExpr->result; - newExpr->result = nullptr; - delete typeofType; - delete newExpr; - } - - // clear qualifiers for base, combine with typeoftype quals in any case - if ( isBasetypeof ) { - // replace basetypeof() by int - if ( dynamic_cast(newType) ) { - Type* newerType = - new BasicType{ newType->get_qualifiers(), BasicType::SignedInt, - newType->attributes }; - delete newType; - newType = newerType; - } - newType->get_qualifiers().val - = ( newType->get_qualifiers().val & ~Type::Qualifiers::Mask ) | oldQuals; - } else { - newType->get_qualifiers().val |= oldQuals; - } - - return newType; -} namespace { Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/Resolver.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -19,6 +19,4 @@ #include // for vector -#include "Alternative.h" // for Alternative, AltList -#include "AlternativeFinder.h" // for AlternativeFinder, resolveIn... #include "Candidate.hpp" #include "CandidateFinder.hpp" @@ -40,21 +38,11 @@ #include "Common/Eval.h" // for eval #include "Common/Iterate.hpp" // for group_iterate -#include "Common/PassVisitor.h" // for PassVisitor #include "Common/SemanticError.h" // for SemanticError #include "Common/Stats/ResolveTime.h" // for ResolveTime::start(), ResolveTime::stop() #include "Common/ToString.hpp" // for toCString +#include "Common/UniqueName.h" // for UniqueName #include "InitTweak/GenInit.h" #include "InitTweak/InitTweak.h" // for isIntrinsicSingleArgCallStmt -#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment -#include "SymTab/Autogen.h" // for SizeType -#include "SymTab/Indexer.h" // for Indexer #include "SymTab/Mangler.h" // for Mangler -#include "SynTree/Declaration.h" // for ObjectDecl, TypeDecl, Declar... -#include "SynTree/Expression.h" // for Expression, CastExpr, InitExpr -#include "SynTree/Initializer.h" // for ConstructorInit, SingleInit -#include "SynTree/Statement.h" // for ForStmt, Statement, BranchStmt -#include "SynTree/Type.h" // for Type, BasicType, PointerType -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution -#include "SynTree/Visitor.h" // for acceptAll, maybeAccept #include "Tuples/Tuples.h" #include "Validate/FindSpecialDecls.h" // for SizeType @@ -63,543 +51,4 @@ namespace ResolvExpr { - struct Resolver_old final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { - Resolver_old() {} - Resolver_old( const SymTab::Indexer & other ) { - indexer = other; - } - - void previsit( FunctionDecl * functionDecl ); - void postvisit( FunctionDecl * functionDecl ); - void previsit( ObjectDecl * objectDecll ); - void previsit( EnumDecl * enumDecl ); - void previsit( StaticAssertDecl * assertDecl ); - - void previsit( ArrayType * at ); - void previsit( PointerType * at ); - - void previsit( ExprStmt * exprStmt ); - void previsit( AsmExpr * asmExpr ); - void previsit( AsmStmt * asmStmt ); - void previsit( IfStmt * ifStmt ); - void previsit( WhileDoStmt * whileDoStmt ); - void previsit( ForStmt * forStmt ); - void previsit( SwitchStmt * switchStmt ); - void previsit( CaseStmt * caseStmt ); - void previsit( BranchStmt * branchStmt ); - void previsit( ReturnStmt * returnStmt ); - void previsit( ThrowStmt * throwStmt ); - void previsit( CatchStmt * catchStmt ); - void postvisit( CatchStmt * catchStmt ); - void previsit( WaitForStmt * stmt ); - - void previsit( SingleInit * singleInit ); - void previsit( ListInit * listInit ); - void previsit( ConstructorInit * ctorInit ); - private: - typedef std::list< Initializer * >::iterator InitIterator; - - template< typename PtrType > - void handlePtrType( PtrType * type ); - - void fallbackInit( ConstructorInit * ctorInit ); - - Type * functionReturn = nullptr; - CurrentObject currentObject = nullptr; - bool inEnumDecl = false; - }; - - struct ResolveWithExprs : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { - void previsit( FunctionDecl * ); - void previsit( WithStmt * ); - - void resolveWithExprs( std::list< Expression * > & withExprs, std::list< Statement * > & newStmts ); - }; - - void resolve( std::list< Declaration * > translationUnit ) { - PassVisitor resolver; - acceptAll( translationUnit, resolver ); - } - - void resolveDecl( Declaration * decl, const SymTab::Indexer & indexer ) { - PassVisitor resolver( indexer ); - maybeAccept( decl, resolver ); - } - - namespace { - struct DeleteFinder_old : public WithShortCircuiting { - DeletedExpr * delExpr = nullptr; - void previsit( DeletedExpr * expr ) { - if ( delExpr ) visit_children = false; - else delExpr = expr; - } - - void previsit( Expression * ) { - if ( delExpr ) visit_children = false; - } - }; - } - - DeletedExpr * findDeletedExpr( Expression * expr ) { - PassVisitor finder; - expr->accept( finder ); - return finder.pass.delExpr; - } - - namespace { - struct StripCasts_old { - Expression * postmutate( CastExpr * castExpr ) { - if ( castExpr->isGenerated && ResolvExpr::typesCompatible( castExpr->arg->result, castExpr->result, SymTab::Indexer() ) ) { - // generated cast is to the same type as its argument, so it's unnecessary -- remove it - Expression * expr = castExpr->arg; - castExpr->arg = nullptr; - std::swap( expr->env, castExpr->env ); - return expr; - } - return castExpr; - } - - static void strip( Expression *& expr ) { - PassVisitor stripper; - expr = expr->acceptMutator( stripper ); - } - }; - - void finishExpr( Expression *& expr, const TypeEnvironment & env, TypeSubstitution * oldenv = nullptr ) { - expr->env = oldenv ? oldenv->clone() : new TypeSubstitution; - env.makeSubstitution( *expr->env ); - StripCasts_old::strip( expr ); // remove unnecessary casts that may be buried in an expression - } - - void removeExtraneousCast( Expression *& expr, const SymTab::Indexer & indexer ) { - if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) { - if ( typesCompatible( castExpr->arg->result, castExpr->result, indexer ) ) { - // cast is to the same type as its argument, so it's unnecessary -- remove it - expr = castExpr->arg; - castExpr->arg = nullptr; - std::swap( expr->env, castExpr->env ); - delete castExpr; - } - } - } - } // namespace - - namespace { - void findUnfinishedKindExpression(Expression * untyped, Alternative & alt, const SymTab::Indexer & indexer, const std::string & kindStr, std::function pred, ResolvMode mode = ResolvMode{} ) { - assertf( untyped, "expected a non-null expression." ); - - // xxx - this isn't thread-safe, but should work until we parallelize the resolver - static unsigned recursion_level = 0; - - ++recursion_level; - TypeEnvironment env; - AlternativeFinder finder( indexer, env ); - finder.find( untyped, recursion_level == 1 ? mode.atTopLevel() : mode ); - --recursion_level; - - #if 0 - if ( finder.get_alternatives().size() != 1 ) { - std::cerr << "untyped expr is "; - untyped->print( std::cerr ); - std::cerr << std::endl << "alternatives are:"; - for ( const Alternative & alt : finder.get_alternatives() ) { - alt.print( std::cerr ); - } // for - } // if - #endif - - // produce filtered list of alternatives - AltList candidates; - for ( Alternative & alt : finder.get_alternatives() ) { - if ( pred( alt ) ) { - candidates.push_back( std::move( alt ) ); - } - } - - // produce invalid error if no candidates - if ( candidates.empty() ) { - SemanticError( untyped, toString( "No reasonable alternatives for ", kindStr, (kindStr != "" ? " " : ""), "expression: ") ); - } - - // search for cheapest candidate - AltList winners; - bool seen_undeleted = false; - for ( unsigned i = 0; i < candidates.size(); ++i ) { - int c = winners.empty() ? -1 : candidates[i].cost.compare( winners.front().cost ); - - if ( c > 0 ) continue; // skip more expensive than winner - - if ( c < 0 ) { - // reset on new cheapest - seen_undeleted = ! findDeletedExpr( candidates[i].expr ); - winners.clear(); - } else /* if ( c == 0 ) */ { - if ( findDeletedExpr( candidates[i].expr ) ) { - // skip deleted expression if already seen one equivalent-cost not - if ( seen_undeleted ) continue; - } else if ( ! seen_undeleted ) { - // replace list of equivalent-cost deleted expressions with one non-deleted - winners.clear(); - seen_undeleted = true; - } - } - - winners.emplace_back( std::move( candidates[i] ) ); - } - - // promote alternative.cvtCost to .cost - // xxx - I don't know why this is done, but I'm keeping the behaviour from findMinCost - for ( Alternative& winner : winners ) { - winner.cost = winner.cvtCost; - } - - // produce ambiguous errors, if applicable - if ( winners.size() != 1 ) { - std::ostringstream stream; - stream << "Cannot choose between " << winners.size() << " alternatives for " << kindStr << (kindStr != "" ? " " : "") << "expression\n"; - untyped->print( stream ); - stream << " Alternatives are:\n"; - printAlts( winners, stream, 1 ); - SemanticError( untyped->location, stream.str() ); - } - - // single selected choice - Alternative& choice = winners.front(); - - // fail on only expression deleted - if ( ! seen_undeleted ) { - SemanticError( untyped->location, choice.expr, "Unique best alternative includes deleted identifier in " ); - } - - // xxx - check for ambiguous expressions - - // output selected choice - alt = std::move( choice ); - } - - /// resolve `untyped` to the expression whose alternative satisfies `pred` with the lowest cost; kindStr is used for providing better error messages - void findKindExpression(Expression *& untyped, const SymTab::Indexer & indexer, const std::string & kindStr, std::function pred, ResolvMode mode = ResolvMode{}) { - if ( ! untyped ) return; - Alternative choice; - findUnfinishedKindExpression( untyped, choice, indexer, kindStr, pred, mode ); - finishExpr( choice.expr, choice.env, untyped->env ); - delete untyped; - untyped = choice.expr; - choice.expr = nullptr; - } - - bool standardAlternativeFilter( const Alternative & ) { - // currently don't need to filter, under normal circumstances. - // in the future, this may be useful for removing deleted expressions - return true; - } - } // namespace - - // used in resolveTypeof - Expression * resolveInVoidContext( Expression * expr, const SymTab::Indexer & indexer ) { - TypeEnvironment env; - return resolveInVoidContext( expr, indexer, env ); - } - - Expression * resolveInVoidContext( Expression * expr, const SymTab::Indexer & indexer, TypeEnvironment & env ) { - // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0 - // interpretations, an exception has already been thrown. - assertf( expr, "expected a non-null expression." ); - - CastExpr * untyped = new CastExpr( expr ); // cast to void - untyped->location = expr->location; - - // set up and resolve expression cast to void - Alternative choice; - findUnfinishedKindExpression( untyped, choice, indexer, "", standardAlternativeFilter, ResolvMode::withAdjustment() ); - CastExpr * castExpr = strict_dynamic_cast< CastExpr * >( choice.expr ); - assert( castExpr ); - env = std::move( choice.env ); - - // clean up resolved expression - Expression * ret = castExpr->arg; - castExpr->arg = nullptr; - - // unlink the arg so that it isn't deleted twice at the end of the program - untyped->arg = nullptr; - return ret; - } - - void findVoidExpression( Expression *& untyped, const SymTab::Indexer & indexer ) { - resetTyVarRenaming(); - TypeEnvironment env; - Expression * newExpr = resolveInVoidContext( untyped, indexer, env ); - finishExpr( newExpr, env, untyped->env ); - delete untyped; - untyped = newExpr; - } - - void findSingleExpression( Expression *& untyped, const SymTab::Indexer & indexer ) { - findKindExpression( untyped, indexer, "", standardAlternativeFilter ); - } - - void findSingleExpression( Expression *& untyped, Type * type, const SymTab::Indexer & indexer ) { - assert( untyped && type ); - // transfer location to generated cast for error purposes - CodeLocation location = untyped->location; - untyped = new CastExpr( untyped, type ); - untyped->location = location; - findSingleExpression( untyped, indexer ); - removeExtraneousCast( untyped, indexer ); - } - - namespace { - bool isIntegralType( const Alternative & alt ) { - Type * type = alt.expr->result; - if ( dynamic_cast< EnumInstType * >( type ) ) { - return true; - } else if ( BasicType * bt = dynamic_cast< BasicType * >( type ) ) { - return bt->isInteger(); - } else if ( dynamic_cast< ZeroType* >( type ) != nullptr || dynamic_cast< OneType* >( type ) != nullptr ) { - return true; - } else { - return false; - } // if - } - - void findIntegralExpression( Expression *& untyped, const SymTab::Indexer & indexer ) { - findKindExpression( untyped, indexer, "condition", isIntegralType ); - } - } - - - bool isStructOrUnion( const Alternative & alt ) { - Type * t = alt.expr->result->stripReferences(); - return dynamic_cast< StructInstType * >( t ) || dynamic_cast< UnionInstType * >( t ); - } - - void resolveWithExprs( std::list< Declaration * > & translationUnit ) { - PassVisitor resolver; - acceptAll( translationUnit, resolver ); - } - - void ResolveWithExprs::resolveWithExprs( std::list< Expression * > & withExprs, std::list< Statement * > & newStmts ) { - for ( Expression *& expr : withExprs ) { - // only struct- and union-typed expressions are viable candidates - findKindExpression( expr, indexer, "with statement", isStructOrUnion ); - - // if with expression might be impure, create a temporary so that it is evaluated once - if ( Tuples::maybeImpure( expr ) ) { - static UniqueName tmpNamer( "_with_tmp_" ); - ObjectDecl * tmp = ObjectDecl::newObject( tmpNamer.newName(), expr->result->clone(), new SingleInit( expr ) ); - expr = new VariableExpr( tmp ); - newStmts.push_back( new DeclStmt( tmp ) ); - if ( InitTweak::isConstructable( tmp->type ) ) { - // generate ctor/dtor and resolve them - tmp->init = InitTweak::genCtorInit( tmp ); - tmp->accept( *visitor ); - } - } - } - } - - void ResolveWithExprs::previsit( WithStmt * withStmt ) { - resolveWithExprs( withStmt->exprs, stmtsToAddBefore ); - } - - void ResolveWithExprs::previsit( FunctionDecl * functionDecl ) { - { - // resolve with-exprs with parameters in scope and add any newly generated declarations to the - // front of the function body. - auto guard = makeFuncGuard( [this]() { indexer.enterScope(); }, [this](){ indexer.leaveScope(); } ); - indexer.addFunctionType( functionDecl->type ); - std::list< Statement * > newStmts; - resolveWithExprs( functionDecl->withExprs, newStmts ); - if ( functionDecl->statements ) { - functionDecl->statements->kids.splice( functionDecl->statements->kids.begin(), newStmts ); - } else { - assertf( functionDecl->withExprs.empty() && newStmts.empty(), "Function %s without a body has with-clause and/or generated with declarations.", functionDecl->name.c_str() ); - } - } - } - - void Resolver_old::previsit( ObjectDecl * objectDecl ) { - // To handle initialization of routine pointers, e.g., int (*fp)(int) = foo(), means that - // class-variable initContext is changed multiple time because the LHS is analysed twice. - // The second analysis changes initContext because of a function type can contain object - // declarations in the return and parameter types. So each value of initContext is - // retained, so the type on the first analysis is preserved and used for selecting the RHS. - GuardValue( currentObject ); - currentObject = CurrentObject( objectDecl->get_type() ); - if ( inEnumDecl && dynamic_cast< EnumInstType * >( objectDecl->get_type() ) ) { - // enumerator initializers should not use the enum type to initialize, since - // the enum type is still incomplete at this point. Use signed int instead. - // TODO: BasicType::SignedInt may not longer be true - currentObject = CurrentObject( new BasicType( Type::Qualifiers(), BasicType::SignedInt ) ); - } - } - - template< typename PtrType > - void Resolver_old::handlePtrType( PtrType * type ) { - if ( type->get_dimension() ) { - findSingleExpression( type->dimension, Validate::SizeType->clone(), indexer ); - } - } - - void Resolver_old::previsit( ArrayType * at ) { - handlePtrType( at ); - } - - void Resolver_old::previsit( PointerType * pt ) { - handlePtrType( pt ); - } - - void Resolver_old::previsit( FunctionDecl * functionDecl ) { -#if 0 - std::cerr << "resolver visiting functiondecl "; - functionDecl->print( std::cerr ); - std::cerr << std::endl; -#endif - GuardValue( functionReturn ); - functionReturn = ResolvExpr::extractResultType( functionDecl->type ); - } - - void Resolver_old::postvisit( FunctionDecl * functionDecl ) { - // default value expressions have an environment which shouldn't be there and trips up - // later passes. - // xxx - it might be necessary to somehow keep the information from this environment, but I - // can't currently see how it's useful. - for ( Declaration * d : functionDecl->type->parameters ) { - if ( ObjectDecl * obj = dynamic_cast< ObjectDecl * >( d ) ) { - if ( SingleInit * init = dynamic_cast< SingleInit * >( obj->init ) ) { - delete init->value->env; - init->value->env = nullptr; - } - } - } - } - - void Resolver_old::previsit( EnumDecl * ) { - // in case we decide to allow nested enums - GuardValue( inEnumDecl ); - inEnumDecl = true; - } - - void Resolver_old::previsit( StaticAssertDecl * assertDecl ) { - findIntegralExpression( assertDecl->condition, indexer ); - } - - void Resolver_old::previsit( ExprStmt * exprStmt ) { - visit_children = false; - assertf( exprStmt->expr, "ExprStmt has null Expression in resolver" ); - findVoidExpression( exprStmt->expr, indexer ); - } - - void Resolver_old::previsit( AsmExpr * asmExpr ) { - visit_children = false; - findVoidExpression( asmExpr->operand, indexer ); - } - - void Resolver_old::previsit( AsmStmt * asmStmt ) { - visit_children = false; - acceptAll( asmStmt->get_input(), *visitor ); - acceptAll( asmStmt->get_output(), *visitor ); - } - - void Resolver_old::previsit( IfStmt * ifStmt ) { - findIntegralExpression( ifStmt->condition, indexer ); - } - - void Resolver_old::previsit( WhileDoStmt * whileDoStmt ) { - findIntegralExpression( whileDoStmt->condition, indexer ); - } - - void Resolver_old::previsit( ForStmt * forStmt ) { - if ( forStmt->condition ) { - findIntegralExpression( forStmt->condition, indexer ); - } // if - - if ( forStmt->increment ) { - findVoidExpression( forStmt->increment, indexer ); - } // if - } - - void Resolver_old::previsit( SwitchStmt * switchStmt ) { - GuardValue( currentObject ); - findIntegralExpression( switchStmt->condition, indexer ); - - currentObject = CurrentObject( switchStmt->condition->result ); - } - - void Resolver_old::previsit( CaseStmt * caseStmt ) { - if ( caseStmt->condition ) { - std::list< InitAlternative > initAlts = currentObject.getOptions(); - assertf( initAlts.size() == 1, "SwitchStmt did not correctly resolve an integral expression." ); - // must remove cast from case statement because RangeExpr cannot be cast. - Expression * newExpr = new CastExpr( caseStmt->condition, initAlts.front().type->clone() ); - findSingleExpression( newExpr, indexer ); - // case condition cannot have a cast in C, so it must be removed, regardless of whether it performs a conversion. - // Ideally we would perform the conversion internally here. - if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( newExpr ) ) { - newExpr = castExpr->arg; - castExpr->arg = nullptr; - std::swap( newExpr->env, castExpr->env ); - delete castExpr; - } - caseStmt->condition = newExpr; - } - } - - void Resolver_old::previsit( BranchStmt * branchStmt ) { - visit_children = false; - // must resolve the argument for a computed goto - if ( branchStmt->get_type() == BranchStmt::Goto ) { // check for computed goto statement - if ( branchStmt->computedTarget ) { - // computed goto argument is void * - findSingleExpression( branchStmt->computedTarget, new PointerType( Type::Qualifiers(), new VoidType( Type::Qualifiers() ) ), indexer ); - } // if - } // if - } - - void Resolver_old::previsit( ReturnStmt * returnStmt ) { - visit_children = false; - if ( returnStmt->expr ) { - findSingleExpression( returnStmt->expr, functionReturn->clone(), indexer ); - } // if - } - - void Resolver_old::previsit( ThrowStmt * throwStmt ) { - visit_children = false; - // TODO: Replace *exception type with &exception type. - if ( throwStmt->get_expr() ) { - const StructDecl * exception_decl = indexer.lookupStruct( "__cfaehm_base_exception_t" ); - assert( exception_decl ); - Type * exceptType = new PointerType( noQualifiers, new StructInstType( noQualifiers, const_cast(exception_decl) ) ); - findSingleExpression( throwStmt->expr, exceptType, indexer ); - } - } - - void Resolver_old::previsit( CatchStmt * catchStmt ) { - // Until we are very sure this invarent (ifs that move between passes have then) - // holds, check it. This allows a check for when to decode the mangling. - if ( IfStmt * ifStmt = dynamic_cast( catchStmt->body ) ) { - assert( ifStmt->then ); - } - // Encode the catchStmt so the condition can see the declaration. - if ( catchStmt->cond ) { - IfStmt * ifStmt = new IfStmt( catchStmt->cond, nullptr, catchStmt->body ); - catchStmt->cond = nullptr; - catchStmt->body = ifStmt; - } - } - - void Resolver_old::postvisit( CatchStmt * catchStmt ) { - // Decode the catchStmt so everything is stored properly. - IfStmt * ifStmt = dynamic_cast( catchStmt->body ); - if ( nullptr != ifStmt && nullptr == ifStmt->then ) { - assert( ifStmt->condition ); - assert( ifStmt->else_ ); - catchStmt->cond = ifStmt->condition; - catchStmt->body = ifStmt->else_; - ifStmt->condition = nullptr; - ifStmt->else_ = nullptr; - delete ifStmt; - } - } - template< typename iterator_t > inline bool advance_to_mutex( iterator_t & it, const iterator_t & end ) { @@ -610,362 +59,4 @@ return it != end; } - - void Resolver_old::previsit( WaitForStmt * stmt ) { - visit_children = false; - - // Resolve all clauses first - for( auto& clause : stmt->clauses ) { - - TypeEnvironment env; - AlternativeFinder funcFinder( indexer, env ); - - // Find all alternatives for a function in canonical form - funcFinder.findWithAdjustment( clause.target.function ); - - if ( funcFinder.get_alternatives().empty() ) { - stringstream ss; - ss << "Use of undeclared indentifier '"; - ss << strict_dynamic_cast( clause.target.function )->name; - ss << "' in call to waitfor"; - SemanticError( stmt->location, ss.str() ); - } - - if(clause.target.arguments.empty()) { - SemanticError( stmt->location, "Waitfor clause must have at least one mutex parameter"); - } - - // Find all alternatives for all arguments in canonical form - std::vector< AlternativeFinder > argAlternatives; - funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) ); - - // List all combinations of arguments - std::vector< AltList > possibilities; - combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); - - AltList func_candidates; - std::vector< AltList > args_candidates; - - // For every possible function : - // try matching the arguments to the parameters - // not the other way around because we have more arguments than parameters - SemanticErrorException errors; - for ( Alternative & func : funcFinder.get_alternatives() ) { - try { - PointerType * pointer = dynamic_cast< PointerType* >( func.expr->get_result()->stripReferences() ); - if( !pointer ) { - SemanticError( func.expr->get_result(), "candidate not viable: not a pointer type\n" ); - } - - FunctionType * function = dynamic_cast< FunctionType* >( pointer->get_base() ); - if( !function ) { - SemanticError( pointer->get_base(), "candidate not viable: not a function type\n" ); - } - - - { - auto param = function->parameters.begin(); - auto param_end = function->parameters.end(); - - if( !advance_to_mutex( param, param_end ) ) { - SemanticError(function, "candidate function not viable: no mutex parameters\n"); - } - } - - Alternative newFunc( func ); - // Strip reference from function - referenceToRvalueConversion( newFunc.expr, newFunc.cost ); - - // For all the set of arguments we have try to match it with the parameter of the current function alternative - for ( auto & argsList : possibilities ) { - - try { - // Declare data structures need for resolution - OpenVarSet openVars; - AssertionSet resultNeed, resultHave; - TypeEnvironment resultEnv( func.env ); - makeUnifiableVars( function, openVars, resultNeed ); - // add all type variables as open variables now so that those not used in the parameter - // list are still considered open. - resultEnv.add( function->forall ); - - // Load type variables from arguemnts into one shared space - simpleCombineEnvironments( argsList.begin(), argsList.end(), resultEnv ); - - // Make sure we don't widen any existing bindings - resultEnv.forbidWidening(); - - // Find any unbound type variables - resultEnv.extractOpenVars( openVars ); - - auto param = function->parameters.begin(); - auto param_end = function->parameters.end(); - - int n_mutex_param = 0; - - // For every arguments of its set, check if it matches one of the parameter - // The order is important - for( auto & arg : argsList ) { - - // Ignore non-mutex arguments - if( !advance_to_mutex( param, param_end ) ) { - // We ran out of parameters but still have arguments - // this function doesn't match - SemanticError( function, toString("candidate function not viable: too many mutex arguments, expected ", n_mutex_param, "\n" )); - } - - n_mutex_param++; - - // Check if the argument matches the parameter type in the current scope - if( ! unify( arg.expr->get_result(), (*param)->get_type(), resultEnv, resultNeed, resultHave, openVars, this->indexer ) ) { - // Type doesn't match - stringstream ss; - ss << "candidate function not viable: no known convertion from '"; - (*param)->get_type()->print( ss ); - ss << "' to '"; - arg.expr->get_result()->print( ss ); - ss << "' with env '"; - resultEnv.print(ss); - ss << "'\n"; - SemanticError( function, ss.str() ); - } - - param++; - } - - // All arguments match ! - - // Check if parameters are missing - if( advance_to_mutex( param, param_end ) ) { - do { - n_mutex_param++; - param++; - } while( advance_to_mutex( param, param_end ) ); - - // We ran out of arguments but still have parameters left - // this function doesn't match - SemanticError( function, toString("candidate function not viable: too few mutex arguments, expected ", n_mutex_param, "\n" )); - } - - // All parameters match ! - - // Finish the expressions to tie in the proper environments - finishExpr( newFunc.expr, resultEnv ); - for( Alternative & alt : argsList ) { - finishExpr( alt.expr, resultEnv ); - } - - // This is a match store it and save it for later - func_candidates.push_back( newFunc ); - args_candidates.push_back( argsList ); - - } - catch( SemanticErrorException & e ) { - errors.append( e ); - } - } - } - catch( SemanticErrorException & e ) { - errors.append( e ); - } - } - - // Make sure we got the right number of arguments - if( func_candidates.empty() ) { SemanticErrorException top( stmt->location, "No alternatives for function in call to waitfor" ); top.append( errors ); throw top; } - if( args_candidates.empty() ) { SemanticErrorException top( stmt->location, "No alternatives for arguments in call to waitfor" ); top.append( errors ); throw top; } - if( func_candidates.size() > 1 ) { SemanticErrorException top( stmt->location, "Ambiguous function in call to waitfor" ); top.append( errors ); throw top; } - if( args_candidates.size() > 1 ) { SemanticErrorException top( stmt->location, "Ambiguous arguments in call to waitfor" ); top.append( errors ); throw top; } - // TODO: need to use findDeletedExpr to ensure no deleted identifiers are used. - - // Swap the results from the alternative with the unresolved values. - // Alternatives will handle deletion on destruction - std::swap( clause.target.function, func_candidates.front().expr ); - for( auto arg_pair : group_iterate( clause.target.arguments, args_candidates.front() ) ) { - std::swap ( std::get<0>( arg_pair), std::get<1>( arg_pair).expr ); - } - - // Resolve the conditions as if it were an IfStmt - // Resolve the statments normally - findSingleExpression( clause.condition, this->indexer ); - clause.statement->accept( *visitor ); - } - - - if( stmt->timeout.statement ) { - // Resolve the timeout as an size_t for now - // Resolve the conditions as if it were an IfStmt - // Resolve the statments normally - findSingleExpression( stmt->timeout.time, new BasicType( noQualifiers, BasicType::LongLongUnsignedInt ), this->indexer ); - findSingleExpression( stmt->timeout.condition, this->indexer ); - stmt->timeout.statement->accept( *visitor ); - } - - if( stmt->orelse.statement ) { - // Resolve the conditions as if it were an IfStmt - // Resolve the statments normally - findSingleExpression( stmt->orelse.condition, this->indexer ); - stmt->orelse.statement->accept( *visitor ); - } - } - - bool isCharType( Type * t ) { - if ( BasicType * bt = dynamic_cast< BasicType * >( t ) ) { - return bt->get_kind() == BasicType::Char || bt->get_kind() == BasicType::SignedChar || - bt->get_kind() == BasicType::UnsignedChar; - } - return false; - } - - void Resolver_old::previsit( SingleInit * singleInit ) { - visit_children = false; - // resolve initialization using the possibilities as determined by the currentObject cursor - Expression * newExpr = new UntypedInitExpr( singleInit->value, currentObject.getOptions() ); - findSingleExpression( newExpr, indexer ); - InitExpr * initExpr = strict_dynamic_cast< InitExpr * >( newExpr ); - - // move cursor to the object that is actually initialized - currentObject.setNext( initExpr->get_designation() ); - - // discard InitExpr wrapper and retain relevant pieces - newExpr = initExpr->expr; - initExpr->expr = nullptr; - std::swap( initExpr->env, newExpr->env ); - // InitExpr may have inferParams in the case where the expression specializes a function - // pointer, and newExpr may already have inferParams of its own, so a simple swap is not - // sufficient. - newExpr->spliceInferParams( initExpr ); - delete initExpr; - - // get the actual object's type (may not exactly match what comes back from the resolver - // due to conversions) - Type * initContext = currentObject.getCurrentType(); - - removeExtraneousCast( newExpr, indexer ); - - // check if actual object's type is char[] - if ( ArrayType * at = dynamic_cast< ArrayType * >( initContext ) ) { - if ( isCharType( at->get_base() ) ) { - // check if the resolved type is char * - if ( PointerType * pt = dynamic_cast< PointerType *>( newExpr->get_result() ) ) { - if ( isCharType( pt->get_base() ) ) { - if ( CastExpr * ce = dynamic_cast< CastExpr * >( newExpr ) ) { - // strip cast if we're initializing a char[] with a char *, - // e.g. char x[] = "hello"; - newExpr = ce->get_arg(); - ce->set_arg( nullptr ); - std::swap( ce->env, newExpr->env ); - delete ce; - } - } - } - } - } - - // set initializer expr to resolved express - singleInit->value = newExpr; - - // move cursor to next object in preparation for next initializer - currentObject.increment(); - } - - void Resolver_old::previsit( ListInit * listInit ) { - visit_children = false; - // move cursor into brace-enclosed initializer-list - currentObject.enterListInit(); - // xxx - fix this so that the list isn't copied, iterator should be used to change current - // element - std::list newDesignations; - for ( auto p : group_iterate(listInit->get_designations(), listInit->get_initializers()) ) { - // iterate designations and initializers in pairs, moving the cursor to the current - // designated object and resolving the initializer against that object. - Designation * des = std::get<0>(p); - Initializer * init = std::get<1>(p); - newDesignations.push_back( currentObject.findNext( des ) ); - init->accept( *visitor ); - } - // set the set of 'resolved' designations and leave the brace-enclosed initializer-list - listInit->get_designations() = newDesignations; // xxx - memory management - currentObject.exitListInit(); - - // xxx - this part has not be folded into CurrentObject yet - // } else if ( TypeInstType * tt = dynamic_cast< TypeInstType * >( initContext ) ) { - // Type * base = tt->get_baseType()->get_base(); - // if ( base ) { - // // know the implementation type, so try using that as the initContext - // ObjectDecl tmpObj( "", Type::StorageClasses(), LinkageSpec::Cforall, nullptr, base->clone(), nullptr ); - // currentObject = &tmpObj; - // visit( listInit ); - // } else { - // // missing implementation type -- might be an unknown type variable, so try proceeding with the current init context - // Parent::visit( listInit ); - // } - // } else { - } - - // ConstructorInit - fall back on C-style initializer - void Resolver_old::fallbackInit( ConstructorInit * ctorInit ) { - // could not find valid constructor, or found an intrinsic constructor - // fall back on C-style initializer - delete ctorInit->get_ctor(); - ctorInit->set_ctor( nullptr ); - delete ctorInit->get_dtor(); - ctorInit->set_dtor( nullptr ); - maybeAccept( ctorInit->get_init(), *visitor ); - } - - // needs to be callable from outside the resolver, so this is a standalone function - void resolveCtorInit( ConstructorInit * ctorInit, const SymTab::Indexer & indexer ) { - assert( ctorInit ); - PassVisitor resolver( indexer ); - ctorInit->accept( resolver ); - } - - void resolveStmtExpr( StmtExpr * stmtExpr, const SymTab::Indexer & indexer ) { - assert( stmtExpr ); - PassVisitor resolver( indexer ); - stmtExpr->accept( resolver ); - stmtExpr->computeResult(); - // xxx - aggregate the environments from all statements? Possibly in AlternativeFinder instead? - } - - void Resolver_old::previsit( ConstructorInit * ctorInit ) { - visit_children = false; - // xxx - fallback init has been removed => remove fallbackInit function and remove complexity from FixInit and remove C-init from ConstructorInit - maybeAccept( ctorInit->ctor, *visitor ); - maybeAccept( ctorInit->dtor, *visitor ); - - // found a constructor - can get rid of C-style initializer - delete ctorInit->init; - ctorInit->init = nullptr; - - // intrinsic single parameter constructors and destructors do nothing. Since this was - // implicitly generated, there's no way for it to have side effects, so get rid of it - // to clean up generated code. - if ( InitTweak::isIntrinsicSingleArgCallStmt( ctorInit->ctor ) ) { - delete ctorInit->ctor; - ctorInit->ctor = nullptr; - } - - if ( InitTweak::isIntrinsicSingleArgCallStmt( ctorInit->dtor ) ) { - delete ctorInit->dtor; - ctorInit->dtor = nullptr; - } - - // xxx - todo -- what about arrays? - // if ( dtor == nullptr && InitTweak::isIntrinsicCallStmt( ctorInit->get_ctor() ) ) { - // // can reduce the constructor down to a SingleInit using the - // // second argument from the ctor call, since - // delete ctorInit->get_ctor(); - // ctorInit->set_ctor( nullptr ); - - // Expression * arg = - // ctorInit->set_init( new SingleInit( arg ) ); - // } - } - - /////////////////////////////////////////////////////////////////////////// - // - // *** NEW RESOLVER *** - // - /////////////////////////////////////////////////////////////////////////// namespace { Index: src/ResolvExpr/SatisfyAssertions.cpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.cpp (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/SatisfyAssertions.cpp (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -46,6 +46,4 @@ #include "SymTab/Mangler.h" - - namespace ResolvExpr { Index: src/ResolvExpr/SpecCost.cc =================================================================== --- src/ResolvExpr/SpecCost.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/SpecCost.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -21,99 +21,6 @@ #include "AST/Pass.hpp" #include "AST/Type.hpp" -#include "Common/PassVisitor.h" -#include "SynTree/Declaration.h" -#include "SynTree/Expression.h" -#include "SynTree/Type.h" namespace ResolvExpr { - - /// Counts specializations in a type - class CountSpecs : public WithShortCircuiting, public WithVisitorRef { - int count = -1; ///< specialization count (-1 for none) - - public: - int get_count() const { return count >= 0 ? count : 0; } - - // mark specialization of base type - void postvisit(PointerType*) { if ( count >= 0 ) ++count; } - - // mark specialization of base type - void postvisit(ArrayType*) { if ( count >= 0 ) ++count; } - - // mark specialization of base type - void postvisit(ReferenceType*) { if ( count >= 0 ) ++count; } - - void postvisit(StructInstType*) { if ( count >= 0 ) ++count; } - void postvisit(UnionInstType*) { if ( count >= 0 ) ++count; } - - private: - // takes minimum non-negative count over parameter/return list - void takeminover( int& mincount, std::list& dwts ) { - for ( DeclarationWithType* dwt : dwts ) { - count = -1; - maybeAccept( dwt->get_type(), *visitor ); - if ( count != -1 && count < mincount ) mincount = count; - } - } - - public: - // take minimal specialization value over ->returnVals and ->parameters - void previsit(FunctionType* fty) { - int mincount = std::numeric_limits::max(); - takeminover( mincount, fty->parameters ); - takeminover( mincount, fty->returnVals ); - // add another level to mincount if set - count = mincount < std::numeric_limits::max() ? mincount + 1 : -1; - // already visited children - visit_children = false; - } - - private: - // returns minimum non-negative count + 1 over type parameters (-1 if none such) - int minover( std::list& parms ) { - int mincount = std::numeric_limits::max(); - for ( Expression* parm : parms ) { - count = -1; - maybeAccept( parm->result, *visitor ); - if ( count != -1 && count < mincount ) mincount = count; - } - return mincount < std::numeric_limits::max() ? mincount + 1 : -1; - } - - public: - // look for polymorphic parameters - void previsit(StructInstType* sty) { - count = minover( sty->parameters ); - } - - // look for polymorphic parameters - void previsit(UnionInstType* uty) { - count = minover( uty->parameters ); - } - - // note polymorphic type (which may be specialized) - // xxx - maybe account for open/closed type variables - void postvisit(TypeInstType*) { count = 0; } - - // take minimal specialization over elements - // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize - void previsit(TupleType* tty) { - int mincount = std::numeric_limits::max(); - for ( Type* ty : tty->types ) { - count = -1; - maybeAccept( ty, *visitor ); - if ( count != -1 && count < mincount ) mincount = count; - } - count = mincount < std::numeric_limits::max() ? mincount + 1 : -1; - visit_children = false; - } - }; - - /// Returns the (negated) specialization cost for a given type - int specCost( Type* ty ) { - PassVisitor counter; - maybeAccept( ty, *counter.pass.visitor ); - return counter.pass.get_count(); - } namespace { Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,491 +1,0 @@ -// -// 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. -// -// TypeEnvironment.cc -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 12:19:47 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jun 18 14:27:00 2019 -// Update Count : 5 -// - -#include // for assert -#include // for copy, set_intersection -#include // for ostream_iterator, insert_iterator -#include // for unique_ptr -#include // for pair, move - -#include "CompilationState.h" // for deterministic_output -#include "Common/utility.h" // for maybeClone -#include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution -#include "Tuples/Tuples.h" // for isTtype -#include "TypeEnvironment.h" -#include "typeops.h" // for occurs -#include "Unify.h" // for unifyInexact - -namespace ResolvExpr { - void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) { - for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) { - i->first->print( os, indent ); - if ( i->second.isUsed ) { - os << "(used)"; - } else { - os << "(not used)"; - } // if - } // for - } - - void printOpenVarSet( const OpenVarSet &openVars, std::ostream &os, int indent ) { - os << std::string( indent, ' ' ); - for ( OpenVarSet::const_iterator i = openVars.begin(); i != openVars.end(); ++i ) { - os << i->first << "(" << i->second << ") "; - } // for - } - - void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { - initialize( src, dest, src.type ); - } - - void EqvClass::initialize( const EqvClass &src, EqvClass &dest, const Type *ty ) { - dest.vars = src.vars; - dest.type = maybeClone( ty ); - dest.allowWidening = src.allowWidening; - dest.data = src.data; - } - - EqvClass::EqvClass() : type( nullptr ), allowWidening( true ) { - } - - EqvClass::EqvClass( const EqvClass &other ) { - initialize( other, *this ); - } - - EqvClass::EqvClass( const EqvClass &other, const Type *ty ) { - initialize( other, *this, ty ); - } - - EqvClass::EqvClass( EqvClass &&other ) - : vars{std::move(other.vars)}, type{other.type}, - allowWidening{std::move(other.allowWidening)}, data{std::move(other.data)} { - other.type = nullptr; - } - - EqvClass &EqvClass::operator=( const EqvClass &other ) { - if ( this == &other ) return *this; - delete type; - initialize( other, *this ); - return *this; - } - - EqvClass &EqvClass::operator=( EqvClass &&other ) { - if ( this == &other ) return *this; - delete type; - - vars = std::move(other.vars); - type = other.type; - other.type = nullptr; - allowWidening = std::move(other.allowWidening); - data = std::move(other.data); - - return *this; - } - - EqvClass::~EqvClass() { - delete type; - } - - void EqvClass::set_type( Type* ty ) { - if ( ty == type ) return; - delete type; - type = ty; - } - - void EqvClass::print( std::ostream &os, Indenter indent ) const { - os << "("; - bool first = true; - for(const auto & var : vars) { - if(first) first = false; - else os << " "; - if( deterministic_output && isUnboundType(var) ) os << "[unbound]"; - else os << var; - } - os << ")"; - if ( type ) { - os << " -> "; - type->print( os, indent+1 ); - } // if - if ( ! allowWidening ) { - os << " (no widening)"; - } // if - os << std::endl; - } - - const EqvClass* TypeEnvironment::lookup( const std::string &var ) const { - for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.find( var ) != i->vars.end() ) return &*i; - } // for - return nullptr; - } - - /// Removes any class from env that intersects eqvClass - void filterOverlappingClasses( std::list &env, const EqvClass &eqvClass ) { - for ( auto i = env.begin(); i != env.end(); ) { - auto next = i; - ++next; - std::set intersection; - std::set_intersection( i->vars.begin(), i->vars.end(), eqvClass.vars.begin(), eqvClass.vars.end(), - std::inserter( intersection, intersection.begin() ) ); - if ( ! intersection.empty() ) { env.erase( i ); } - i = next; - } - } - - void TypeEnvironment::add( EqvClass &&eqvClass ) { - filterOverlappingClasses( env, eqvClass ); - env.push_back( std::move(eqvClass) ); - } - - void TypeEnvironment::add( const Type::ForallList &tyDecls ) { - for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) { - EqvClass newClass; - newClass.vars.insert( (*i)->get_name() ); - newClass.data = TypeDecl::Data{ (*i) }; - env.push_back( std::move(newClass) ); - } // for - } - - void TypeEnvironment::add( const TypeSubstitution & sub ) { - EqvClass newClass; - for ( auto p : sub ) { - newClass.vars.insert( p.first ); - newClass.type = p.second->clone(); - newClass.allowWidening = false; - // Minimal assumptions. Not technically correct, but might be good enough, and - // is the best we can do at the moment since information is lost in the - // transition to TypeSubstitution - newClass.data = TypeDecl::Data{ TypeDecl::Dtype, false }; - add( std::move(newClass) ); - } - } - - void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const { - for ( ClassList::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) { - for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) { - if ( theClass->type ) { - sub.add( *theVar, theClass->type ); - } else if ( theVar != theClass->vars.begin() ) { - TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->data.kind == TypeDecl::Ftype ); - sub.add( *theVar, newTypeInst ); - delete newTypeInst; - } // if - } // for - } // for - sub.normalize(); - } - - void TypeEnvironment::print( std::ostream &os, Indenter indent ) const { - for ( const EqvClass & theClass : env ) { - theClass.print( os, indent ); - } // for - } - - TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string &var ) { - for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.count( var ) ) return i; - } // for - return env.end(); - } - - void TypeEnvironment::simpleCombine( const TypeEnvironment &second ) { - env.insert( env.end(), second.env.begin(), second.env.end() ); - } - - // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto) - bool TypeEnvironment::mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) { - if ( from.type ) { - if ( to.type ) { - // attempt to unify bound types - std::unique_ptr toType{ to.type->clone() }, fromType{ from.type->clone() }; - WidenMode widen{ to.allowWidening, from.allowWidening }; - Type* common = nullptr; - AssertionSet need, have; - if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widen, indexer, common ) ) { - // unifies, set common type if necessary - if ( common ) { - common->get_qualifiers() = Type::Qualifiers{}; - to.set_type( common ); - } - } else return false; // cannot unify - } else { - to.type = from.type->clone(); - } - } - - // unify widening if matches - to.allowWidening &= from.allowWidening; - return true; - } - - // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto) - bool TypeEnvironment::mergeClasses( TypeEnvironment::ClassList::iterator to, TypeEnvironment::ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) { - EqvClass& r = *to; - EqvClass& s = *from; - - // ensure bounds match - if ( ! mergeBound( r, s, openVars, indexer ) ) return false; - - // check safely bindable - if ( r.type && occursIn( r.type, s.vars.begin(), s.vars.end(), *this ) ) return false; - - // merge classes in - r.vars.insert( s.vars.begin(), s.vars.end() ); - r.allowWidening &= s.allowWidening; - env.erase( from ); - - return true; - } - - bool TypeEnvironment::combine( const TypeEnvironment& o, OpenVarSet& openVars, const SymTab::Indexer& indexer ) { - // short-circuit easy cases - if ( o.isEmpty() ) return true; - if ( isEmpty() ) { - simpleCombine( o ); - return true; - } - - // merge classes - for ( auto ct = o.env.begin(); ct != o.env.end(); ++ct ) { - const EqvClass& c = *ct; - - // typeclass in local environment bound to c - auto rt = env.end(); - - // look for first existing bound variable - auto vt = c.vars.begin(); - for ( ; vt != c.vars.end(); ++vt ) { - rt = internal_lookup( *vt ); - if ( rt != env.end() ) break; - } - - if ( rt != env.end() ) { // c needs to be merged into *rt - EqvClass& r = *rt; - // merge bindings - if ( ! mergeBound( r, c, openVars, indexer ) ) return false; - // merge previous unbound variables into this class, checking occurs if needed - if ( r.type ) for ( auto ut = c.vars.begin(); ut != vt; ++ut ) { - if ( occurs( r.type, *ut, *this ) ) return false; - r.vars.insert( *ut ); - } else { r.vars.insert( c.vars.begin(), vt ); } - // merge subsequent variables into this class (skipping *vt, already there) - while ( ++vt != c.vars.end() ) { - auto st = internal_lookup( *vt ); - if ( st == env.end() ) { - // unbound, safe to add if passes occurs - if ( r.type && occurs( r.type, *vt, *this ) ) return false; - r.vars.insert( *vt ); - } else if ( st != rt ) { - // bound, but not to the same class - if ( ! mergeClasses( rt, st, openVars, indexer ) ) return false; - } // ignore bound into the same class - } - } else { // no variables in c bound; just copy up - env.push_back( c ); - } - } - - // merged all classes - return true; - } - - void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { - for ( ClassList::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) { - for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) { - openVars[ *var ] = eqvClass->data; - } // for - } // for - } - - void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) { - for ( const EqvClass& c : actualEnv ) { - EqvClass c2 = c; - c2.allowWidening = false; - for ( const std::string& var : c2.vars ) { - openVars[ var ] = c2.data; - } - env.push_back( std::move(c2) ); - } - } - - bool isFtype( const Type * type ) { - if ( dynamic_cast< const FunctionType * >( type ) ) { - return true; - } else if ( const TypeInstType *typeInst = dynamic_cast< const TypeInstType * >( type ) ) { - return typeInst->get_isFtype(); - } // if - return false; - } - - bool tyVarCompatible( const TypeDecl::Data & data, const Type * type ) { - switch ( data.kind ) { - case TypeDecl::Dtype: - // to bind to an object type variable, the type must not be a function type. - // if the type variable is specified to be a complete type then the incoming - // type must also be complete - // xxx - should this also check that type is not a tuple type and that it's not a ttype? - return ! isFtype( type ) && (! data.isComplete || type->isComplete() ); - case TypeDecl::Ftype: - return isFtype( type ); - case TypeDecl::Ttype: - // ttype unifies with any tuple type - return dynamic_cast< const TupleType * >( type ) || Tuples::isTtype( type ); - default: - assertf(false, "Unhandled tyvar kind: %d", data.kind); - } // switch - return false; - } - - bool TypeEnvironment::bindVar( const TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { - - // remove references from other, so that type variables can only bind to value types - bindTo = bindTo->stripReferences(); - OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() ); - assert( tyvar != openVars.end() ); - if ( ! tyVarCompatible( tyvar->second, bindTo ) ) { - return false; - } // if - if ( occurs( bindTo, typeInst->get_name(), *this ) ) { - return false; - } // if - auto curClass = internal_lookup( typeInst->get_name() ); - if ( curClass != env.end() ) { - if ( curClass->type ) { - Type *common = 0; - // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to - std::unique_ptr< Type > newType( curClass->type->clone() ); - newType->tq = typeInst->tq; - if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widen & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { - if ( common ) { - common->get_qualifiers() = Type::Qualifiers{}; - curClass->set_type( common ); - } // if - } else return false; - } else { - Type* newType = bindTo->clone(); - newType->get_qualifiers() = Type::Qualifiers{}; - curClass->set_type( newType ); - curClass->allowWidening = widen.first && widen.second; - } // if - } else { - EqvClass newClass; - newClass.vars.insert( typeInst->get_name() ); - newClass.type = bindTo->clone(); - newClass.type->get_qualifiers() = Type::Qualifiers(); - newClass.allowWidening = widen.first && widen.second; - newClass.data = data; - env.push_back( std::move(newClass) ); - } // if - return true; - } - - bool TypeEnvironment::bindVarToVar( const TypeInstType * var1, const TypeInstType * var2, - TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, - const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { - - auto class1 = internal_lookup( var1->get_name() ); - auto class2 = internal_lookup( var2->get_name() ); - - // exit early if variables already bound together - if ( class1 != env.end() && class1 == class2 ) { - class1->allowWidening &= widen; - return true; - } - - bool widen1 = false, widen2 = false; - const Type *type1 = nullptr, *type2 = nullptr; - - // check for existing bindings, perform occurs check - if ( class1 != env.end() ) { - if ( class1->type ) { - if ( occurs( class1->type, var2->get_name(), *this ) ) return false; - type1 = class1->type; - } // if - widen1 = widen.first && class1->allowWidening; - } // if - if ( class2 != env.end() ) { - if ( class2->type ) { - if ( occurs( class2->type, var1->get_name(), *this ) ) return false; - type2 = class2->type; - } // if - widen2 = widen.second && class2->allowWidening; - } // if - - if ( type1 && type2 ) { - // both classes bound, merge if bound types can be unified - std::unique_ptr newType1{ type1->clone() }, newType2{ type2->clone() }; - WidenMode newWidenMode{ widen1, widen2 }; - Type *common = 0; - if ( unifyInexact( newType1.get(), newType2.get(), *this, need, have, openVars, newWidenMode, indexer, common ) ) { - class1->vars.insert( class2->vars.begin(), class2->vars.end() ); - class1->allowWidening = widen1 && widen2; - if ( common ) { - common->get_qualifiers() = Type::Qualifiers{}; - class1->set_type( common ); - } - class1->data.isComplete |= data.isComplete; - env.erase( class2 ); - } else return false; - } else if ( class1 != env.end() && class2 != env.end() ) { - // both classes exist, at least one unbound, merge unconditionally - if ( type1 ) { - class1->vars.insert( class2->vars.begin(), class2->vars.end() ); - class1->allowWidening = widen1; - class1->data.isComplete |= data.isComplete; - env.erase( class2 ); - } else { - class2->vars.insert( class1->vars.begin(), class1->vars.end() ); - class2->allowWidening = widen2; - class2->data.isComplete |= data.isComplete; - env.erase( class1 ); - } // if - } else if ( class1 != env.end() ) { - // var2 unbound, add to class1 - class1->vars.insert( var2->get_name() ); - class1->allowWidening = widen1; - class1->data.isComplete |= data.isComplete; - } else if ( class2 != env.end() ) { - // var1 unbound, add to class2 - class2->vars.insert( var1->get_name() ); - class2->allowWidening = widen2; - class2->data.isComplete |= data.isComplete; - } else { - // neither var bound, create new class - EqvClass newClass; - newClass.vars.insert( var1->get_name() ); - newClass.vars.insert( var2->get_name() ); - newClass.allowWidening = widen1 && widen2; - newClass.data = data; - env.push_back( std::move(newClass) ); - } // if - return true; - } - - void TypeEnvironment::forbidWidening() { - for ( EqvClass& c : env ) c.allowWidening = false; - } - - std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) { - env.print( out ); - return out; - } -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ (revision ) @@ -1,180 +1,0 @@ -// -// 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. -// -// TypeEnvironment.h -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 12:24:58 2015 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jul 19 17:00:10 2019 -// Update Count : 10 -// - -#pragma once - -#include // for ostream -#include // for list, list<>::iterator, list<>... -#include // for map, map<>::value_compare -#include -#include // for set -#include // for string -#include // for move, swap - -#include "WidenMode.h" // for WidenMode - -#include "SynTree/Declaration.h" // for TypeDecl::Data, DeclarationWit... -#include "SynTree/SynTree.h" // for UniqueId -#include "SynTree/Type.h" // for Type, Type::ForallList -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution - -namespace ResolvExpr { - // adding this comparison operator significantly improves assertion resolution run time for - // some cases. The current resolution algorithm's speed partially depends on the order of - // assertions. Assertions which have fewer possible matches should appear before - // assertions which have more possible matches. This seems to imply that this could - // be further improved by providing an indexer as an additional argument and ordering based - // on the number of matches of the same kind (object, function) for the names of the - // declarations. - // - // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this - // comparator. - // - // Note: since this compares pointers for position, minor changes in the source file that affect - // memory layout can alter compilation time in unpredictable ways. For example, the placement - // of a line directive can reorder type pointers with respect to each other so that assertions - // are seen in different orders, causing a potentially different number of unification calls - // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering - // line directives alone, so it would be nice to fix this comparison so that assertions compare - // more consistently. I've tried to modify this to compare on mangle name instead of type as - // the second comparator, but this causes some assertions to never be recorded. More - // investigation is needed. - struct AssertCompare { - bool operator()( const DeclarationWithType * d1, const DeclarationWithType * d2 ) const { - int cmp = d1->get_name().compare( d2->get_name() ); - return cmp < 0 || - ( cmp == 0 && d1->get_type() < d2->get_type() ); - } - }; - struct AssertionSetValue { - bool isUsed; ///< True if assertion needs to be resolved - UniqueId resnSlot; ///< ID of slot assertion belongs to - - AssertionSetValue() : isUsed(false), resnSlot(0) {} - }; - typedef std::map< const DeclarationWithType *, AssertionSetValue, AssertCompare > AssertionSet; - typedef std::unordered_map< std::string, TypeDecl::Data > OpenVarSet; - - /// merges one set of open vars into another - static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) { - for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; } - } - - void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 ); - void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 ); - - struct EqvClass { - std::set< std::string > vars; - Type * type; - bool allowWidening; - TypeDecl::Data data; - - void initialize( const EqvClass &src, EqvClass &dest ); - void initialize( const EqvClass &src, EqvClass &dest, const Type *ty ); - EqvClass(); - EqvClass( const EqvClass &other ); - EqvClass( const EqvClass &other, const Type *ty ); - EqvClass( EqvClass &&other ); - EqvClass &operator=( const EqvClass &other ); - EqvClass &operator=( EqvClass &&other ); - ~EqvClass(); - void print( std::ostream &os, Indenter indent = {} ) const; - - /// Takes ownership of `ty`, freeing old `type` - void set_type(Type* ty); - }; - - class TypeEnvironment { - using ClassList = std::list< EqvClass >; - public: - const EqvClass* lookup( const std::string &var ) const; - private: - void add( EqvClass &&eqvClass ); - public: - void add( const Type::ForallList &tyDecls ); - void add( const TypeSubstitution & sub ); - template< typename SynTreeClass > int apply( SynTreeClass *&type ) const; - template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const; - void makeSubstitution( TypeSubstitution &result ) const; - bool isEmpty() const { return env.empty(); } - void print( std::ostream &os, Indenter indent = {} ) const; - - /// Simply concatenate the second environment onto this one; no safety checks performed - void simpleCombine( const TypeEnvironment &second ); - - private: - /// Unifies the type bound of to with the type bound of from, returning false if fails - bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer ); - - /// Merges two type classes from local environment, returning false if fails - bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer ); - - public: - /// Merges the second environment with this one, checking compatibility. - /// Returns false if fails, but does NOT roll back partial changes. - bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer ); - - void extractOpenVars( OpenVarSet &openVars ) const; - TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } - - /// Iteratively adds the environment of a new actual (with allowWidening = false), - /// and extracts open variables. - void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ); - - /// Binds the type class represented by `typeInst` to the type `bindTo`; will add - /// the class if needed. Returns false on failure. - bool bindVar( const TypeInstType * typeInst, Type * bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); - - /// Binds the type classes represented by `var1` and `var2` together; will add - /// one or both classes if needed. Returns false on failure. - bool bindVarToVar( const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); - - /// Disallows widening for all bindings in the environment - void forbidWidening(); - - using iterator = ClassList::const_iterator; - iterator begin() const { return env.begin(); } - iterator end() const { return env.end(); } - - auto size() const { return env.size(); } - - private: - ClassList env; - - ClassList::iterator internal_lookup( const std::string &var ); - }; - - template< typename SynTreeClass > - int TypeEnvironment::apply( SynTreeClass *&type ) const { - TypeSubstitution sub; - makeSubstitution( sub ); - return sub.apply( type ); - } - - template< typename SynTreeClass > - int TypeEnvironment::applyFree( SynTreeClass *&type ) const { - TypeSubstitution sub; - makeSubstitution( sub ); - return sub.applyFree( type ); - } - - std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); -} // namespace ResolvExpr - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/Unify.cc (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -33,17 +33,8 @@ #include "AST/TypeEnvironment.hpp" #include "Common/Eval.h" // for eval -#include "Common/PassVisitor.h" // for PassVisitor #include "CommonType.hpp" // for commonType #include "FindOpenVars.h" // for findOpenVars #include "SpecCost.hpp" // for SpecCost -#include "SynTree/LinkageSpec.h" // for C -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati... -#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType -#include "SynTree/Visitor.h" // for Visitor #include "Tuples/Tuples.h" // for isTtype -#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet #include "typeops.h" // for flatten, occurs @@ -52,101 +43,7 @@ } -namespace SymTab { - class Indexer; -} // namespace SymTab - // #define DEBUG namespace ResolvExpr { - -// Template Helpers: -template< typename Iterator1, typename Iterator2 > -bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, std::list< Type* > &commonTypes ) { - for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { - Type *commonType = 0; - if ( ! unify( *list1Begin, *list2Begin, env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) { - return false; - } // if - commonTypes.push_back( commonType ); - } // for - return ( list1Begin == list1End && list2Begin == list2End ); -} - -template< typename Iterator1, typename Iterator2 > -bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { - std::list< Type* > commonTypes; - if ( unifyList( list1Begin, list1End, list2Begin, list2End, env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) { - deleteAll( commonTypes ); - return true; - } else { - return false; - } // if -} - - struct Unify_old : public WithShortCircuiting { - Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); - - bool get_result() const { return result; } - - void previsit( BaseSyntaxNode * ) { visit_children = false; } - - void postvisit( VoidType * voidType ); - void postvisit( BasicType * basicType ); - void postvisit( PointerType * pointerType ); - void postvisit( ArrayType * arrayType ); - void postvisit( ReferenceType * refType ); - void postvisit( FunctionType * functionType ); - void postvisit( StructInstType * aggregateUseType ); - void postvisit( UnionInstType * aggregateUseType ); - void postvisit( EnumInstType * aggregateUseType ); - void postvisit( TraitInstType * aggregateUseType ); - void postvisit( TypeInstType * aggregateUseType ); - void postvisit( TupleType * tupleType ); - void postvisit( VarArgsType * varArgsType ); - void postvisit( ZeroType * zeroType ); - void postvisit( OneType * oneType ); - - private: - template< typename RefType > void handleRefType( RefType *inst, Type *other ); - template< typename RefType > void handleGenericRefType( RefType *inst, Type *other ); - - bool result; - Type *type2; // inherited - TypeEnvironment &env; - AssertionSet &needAssertions; - AssertionSet &haveAssertions; - const OpenVarSet &openVars; - WidenMode widen; - const SymTab::Indexer &indexer; - }; - - /// Attempts an inexact unification of type1 and type2. - /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers) - bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); - bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); - - bool unifyExact( - const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, - ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, - WidenMode widen ); - - bool typesCompatible( const Type * first, const Type * second, const SymTab::Indexer & indexer, const TypeEnvironment & env ) { - TypeEnvironment newEnv; - OpenVarSet openVars, closedVars; // added closedVars - AssertionSet needAssertions, haveAssertions; - Type * newFirst = first->clone(), * newSecond = second->clone(); - env.apply( newFirst ); - env.apply( newSecond ); - - // do we need to do this? Seems like we do, types should be able to be compatible if they - // have free variables that can unify - findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false ); - findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true ); - - bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - delete newFirst; - delete newSecond; - return result; - } bool typesCompatible( @@ -165,20 +62,4 @@ return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() ); - } - - bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { - TypeEnvironment newEnv; - OpenVarSet openVars; - AssertionSet needAssertions, haveAssertions; - Type *newFirst = first->clone(), *newSecond = second->clone(); - env.apply( newFirst ); - env.apply( newSecond ); - newFirst->get_qualifiers() = Type::Qualifiers(); - newSecond->get_qualifiers() = Type::Qualifiers(); - - bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - delete newFirst; - delete newSecond; - return result; } @@ -218,518 +99,4 @@ subSecond, newEnv, need, have, open, noWiden() ); - } - - bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { - OpenVarSet closedVars; - findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false ); - findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true ); - Type *commonType = 0; - if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) { - if ( commonType ) { - delete commonType; - } // if - return true; - } else { - return false; - } // if - } - - bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) { - OpenVarSet closedVars; - findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false ); - findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true ); - return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ); - } - - bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { -#ifdef DEBUG - TypeEnvironment debugEnv( env ); -#endif - if ( type1->get_qualifiers() != type2->get_qualifiers() ) { - return false; - } - - bool result; - TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 ); - TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 ); - OpenVarSet::const_iterator entry1, entry2; - if ( var1 ) { - entry1 = openVars.find( var1->get_name() ); - } // if - if ( var2 ) { - entry2 = openVars.find( var2->get_name() ); - } // if - bool isopen1 = var1 && ( entry1 != openVars.end() ); - bool isopen2 = var2 && ( entry2 != openVars.end() ); - - if ( isopen1 && isopen2 ) { - if ( entry1->second.kind != entry2->second.kind ) { - result = false; - } else { - result = env.bindVarToVar( - var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions, - haveAssertions, openVars, widen, indexer ); - } - } else if ( isopen1 ) { - result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer ); - } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped? - result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer ); - } else { - PassVisitor comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer ); - type1->accept( comparator ); - result = comparator.pass.get_result(); - } // if -#ifdef DEBUG - std::cerr << "============ unifyExact" << std::endl; - std::cerr << "type1 is "; - type1->print( std::cerr ); - std::cerr << std::endl << "type2 is "; - type2->print( std::cerr ); - std::cerr << std::endl << "openVars are "; - printOpenVarSet( openVars, std::cerr, 8 ); - std::cerr << std::endl << "input env is " << std::endl; - debugEnv.print( std::cerr, 8 ); - std::cerr << std::endl << "result env is " << std::endl; - env.print( std::cerr, 8 ); - std::cerr << "result is " << result << std::endl; -#endif - return result; - } - - bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { - return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } - - bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) { - Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers(); - type1->get_qualifiers() = Type::Qualifiers(); - type2->get_qualifiers() = Type::Qualifiers(); - bool result; -#ifdef DEBUG - std::cerr << "unifyInexact type 1 is "; - type1->print( std::cerr ); - std::cerr << " type 2 is "; - type2->print( std::cerr ); - std::cerr << std::endl; -#endif - if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) { -#ifdef DEBUG - std::cerr << "unifyInexact: no exact unification found" << std::endl; -#endif - if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) { - common->tq = tq1.unify( tq2 ); -#ifdef DEBUG - std::cerr << "unifyInexact: common type is "; - common->print( std::cerr ); - std::cerr << std::endl; -#endif - result = true; - } else { -#ifdef DEBUG - std::cerr << "unifyInexact: no common type found" << std::endl; -#endif - result = false; - } // if - } else { - if ( tq1 != tq2 ) { - if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) { - common = type1->clone(); - common->tq = tq1.unify( tq2 ); - result = true; - } else { - result = false; - } // if - } else { - common = type1->clone(); - common->tq = tq1.unify( tq2 ); - result = true; - } // if - } // if - type1->get_qualifiers() = tq1; - type2->get_qualifiers() = tq2; - return result; - } - - Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) - : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) { - } - - void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) { - result = dynamic_cast< VoidType* >( type2 ); - } - - void Unify_old::postvisit(BasicType *basicType) { - if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { - result = basicType->get_kind() == otherBasic->get_kind(); - } // if - } - - void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) { - AssertionSet::iterator i = assertions.find( assert ); - if ( i != assertions.end() ) { - i->second.isUsed = true; - } // if - } - - void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) { - for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { - for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { - markAssertionSet( assertion1, *assert ); - markAssertionSet( assertion2, *assert ); - } // for - } // for - } - - void Unify_old::postvisit(PointerType *pointerType) { - if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) { - result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - markAssertions( haveAssertions, needAssertions, pointerType ); - markAssertions( haveAssertions, needAssertions, otherPointer ); - } // if - } - - void Unify_old::postvisit(ReferenceType *refType) { - if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) { - result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - markAssertions( haveAssertions, needAssertions, refType ); - markAssertions( haveAssertions, needAssertions, otherRef ); - } // if - } - - void Unify_old::postvisit(ArrayType *arrayType) { - ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 ); - // to unify, array types must both be VLA or both not VLA - // and must both have a dimension expression or not have a dimension - if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) { - - if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() && - arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) { - ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() ); - ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() ); - // see C11 Reference Manual 6.7.6.2.6 - // two array types with size specifiers that are integer constant expressions are - // compatible if both size specifiers have the same constant value - if ( ce1 && ce2 ) { - Constant * c1 = ce1->get_constant(); - Constant * c2 = ce2->get_constant(); - - if ( c1->get_value() != c2->get_value() ) { - // does not unify if the dimension is different - return; - } - } - } - - result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } // if - } - - template< typename Iterator, typename Func > - std::unique_ptr combineTypes( Iterator begin, Iterator end, Func & toType ) { - std::list< Type * > types; - for ( ; begin != end; ++begin ) { - // it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple - flatten( toType( *begin ), back_inserter( types ) ); - } - return std::unique_ptr( new TupleType( Type::Qualifiers(), types ) ); - } - - template< typename Iterator1, typename Iterator2 > - bool unifyTypeList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) { - auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); }; - for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { - Type * t1 = (*list1Begin)->get_type(); - Type * t2 = (*list2Begin)->get_type(); - bool isTtype1 = Tuples::isTtype( t1 ); - bool isTtype2 = Tuples::isTtype( t2 ); - // xxx - assumes ttype must be last parameter - // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases. - if ( isTtype1 && ! isTtype2 ) { - // combine all of the things in list2, then unify - return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else if ( isTtype2 && ! isTtype1 ) { - // combine all of the things in list1, then unify - return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) { - return false; - } // if - } // for - // may get to the end of one argument list before the end of the other. This is only okay when the other is a ttype - if ( list1Begin != list1End ) { - // try unifying empty tuple type with ttype - Type * t1 = (*list1Begin)->get_type(); - if ( Tuples::isTtype( t1 ) ) { - return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else return false; - } else if ( list2Begin != list2End ) { - // try unifying empty tuple type with ttype - Type * t2 = (*list2Begin)->get_type(); - if ( Tuples::isTtype( t2 ) ) { - return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else return false; - } else { - return true; - } // if - } - - /// Finds ttypes and replaces them with their expansion, if known. - /// This needs to be done so that satisfying ttype assertions is easier. - /// If this isn't done then argument lists can have wildly different - /// size and structure, when they should be compatible. - struct TtypeExpander_old : public WithShortCircuiting { - TypeEnvironment & tenv; - TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {} - void premutate( TypeInstType * ) { visit_children = false; } - Type * postmutate( TypeInstType * typeInst ) { - if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { - // expand ttype parameter into its actual type - if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) { - delete typeInst; - return eqvClass->type->clone(); - } - } - return typeInst; - } - }; - - /// flattens a list of declarations, so that each tuple type has a single declaration. - /// makes use of TtypeExpander to ensure ttypes are flat as well. - void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) { - dst.clear(); - for ( DeclarationWithType * dcl : src ) { - PassVisitor expander( env ); - dcl->acceptMutator( expander ); - std::list< Type * > types; - flatten( dcl->get_type(), back_inserter( types ) ); - for ( Type * t : types ) { - // outermost const, volatile, _Atomic qualifiers in parameters should not play a role in the unification of function types, since they do not determine whether a function is callable. - // Note: MUST consider at least mutex qualifier, since functions can be overloaded on outermost mutex and a mutex function has different requirements than a non-mutex function. - t->get_qualifiers() -= Type::Qualifiers(Type::Const | Type::Volatile | Type::Atomic); - - dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) ); - } - delete dcl; - } - } - - void Unify_old::postvisit(FunctionType *functionType) { - FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 ); - if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) { - // flatten the parameter lists for both functions so that tuple structure - // doesn't affect unification. Must be a clone so that the types don't change. - std::unique_ptr flatFunc( functionType->clone() ); - std::unique_ptr flatOther( otherFunction->clone() ); - flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env ); - flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env ); - - // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors - if ( - (flatFunc->parameters.size() == flatOther->parameters.size() && - flatFunc->returnVals.size() == flatOther->returnVals.size()) - || flatFunc->isTtype() - || flatOther->isTtype() - ) { - if ( unifyTypeList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { - if ( unifyTypeList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { - - // the original types must be used in mark assertions, since pointer comparisons are used - markAssertions( haveAssertions, needAssertions, functionType ); - markAssertions( haveAssertions, needAssertions, otherFunction ); - - result = true; - } // if - } // if - } // if - } // if - } - - template< typename RefType > - void Unify_old::handleRefType( RefType *inst, Type *other ) { - // check that other type is compatible and named the same - RefType *otherStruct = dynamic_cast< RefType* >( other ); - result = otherStruct && inst->name == otherStruct->name; - } - - template< typename RefType > - void Unify_old::handleGenericRefType( RefType *inst, Type *other ) { - // Check that other type is compatible and named the same - handleRefType( inst, other ); - if ( ! result ) return; - // Check that parameters of types unify, if any - std::list< Expression* > params = inst->parameters; - std::list< Expression* > otherParams = ((RefType*)other)->parameters; - - std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin(); - for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) { - TypeExpr *param = dynamic_cast< TypeExpr* >(*it); - assertf(param, "Aggregate parameters should be type expressions"); - TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt); - assertf(otherParam, "Aggregate parameters should be type expressions"); - - Type* paramTy = param->get_type(); - Type* otherParamTy = otherParam->get_type(); - - bool tupleParam = Tuples::isTtype( paramTy ); - bool otherTupleParam = Tuples::isTtype( otherParamTy ); - - if ( tupleParam && otherTupleParam ) { - ++it; ++jt; // skip ttype parameters for break - } else if ( tupleParam ) { - // bundle other parameters into tuple to match - std::list< Type * > binderTypes; - - do { - binderTypes.push_back( otherParam->get_type()->clone() ); - ++jt; - - if ( jt == otherParams.end() ) break; - - otherParam = dynamic_cast< TypeExpr* >(*jt); - assertf(otherParam, "Aggregate parameters should be type expressions"); - } while (true); - - otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes }; - ++it; // skip ttype parameter for break - } else if ( otherTupleParam ) { - // bundle parameters into tuple to match other - std::list< Type * > binderTypes; - - do { - binderTypes.push_back( param->get_type()->clone() ); - ++it; - - if ( it == params.end() ) break; - - param = dynamic_cast< TypeExpr* >(*it); - assertf(param, "Aggregate parameters should be type expressions"); - } while (true); - - paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes }; - ++jt; // skip ttype parameter for break - } - - if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) { - result = false; - return; - } - - // ttype parameter should be last - if ( tupleParam || otherTupleParam ) break; - } - result = ( it == params.end() && jt == otherParams.end() ); - } - - void Unify_old::postvisit(StructInstType *structInst) { - handleGenericRefType( structInst, type2 ); - } - - void Unify_old::postvisit(UnionInstType *unionInst) { - handleGenericRefType( unionInst, type2 ); - } - - void Unify_old::postvisit(EnumInstType *enumInst) { - handleRefType( enumInst, type2 ); - } - - void Unify_old::postvisit(TraitInstType *contextInst) { - handleRefType( contextInst, type2 ); - } - - void Unify_old::postvisit(TypeInstType *typeInst) { - assert( openVars.find( typeInst->get_name() ) == openVars.end() ); - TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 ); - if ( otherInst && typeInst->get_name() == otherInst->get_name() ) { - result = true; -/// } else { -/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() ); -/// if ( nt ) { -/// TypeDecl *type = dynamic_cast< TypeDecl* >( nt ); -/// assert( type ); -/// if ( type->get_base() ) { -/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); -/// } -/// } - } // if - } - - template< typename Iterator1, typename Iterator2 > - bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) { - auto get_type = [](Type * t) { return t; }; - for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { - Type * t1 = *list1Begin; - Type * t2 = *list2Begin; - bool isTtype1 = Tuples::isTtype( t1 ); - bool isTtype2 = Tuples::isTtype( t2 ); - // xxx - assumes ttype must be last parameter - // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases. - if ( isTtype1 && ! isTtype2 ) { - // combine all of the things in list2, then unify - return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else if ( isTtype2 && ! isTtype1 ) { - // combine all of the things in list1, then unify - return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) { - return false; - } // if - - } // for - if ( list1Begin != list1End ) { - // try unifying empty tuple type with ttype - Type * t1 = *list1Begin; - if ( Tuples::isTtype( t1 ) ) { - return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else return false; - } else if ( list2Begin != list2End ) { - // try unifying empty tuple type with ttype - Type * t2 = *list2Begin; - if ( Tuples::isTtype( t2 ) ) { - return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); - } else return false; - } else { - return true; - } // if - } - - void Unify_old::postvisit(TupleType *tupleType) { - if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) { - std::unique_ptr flat1( tupleType->clone() ); - std::unique_ptr flat2( otherTuple->clone() ); - std::list types1, types2; - - PassVisitor expander( env ); - flat1->acceptMutator( expander ); - flat2->acceptMutator( expander ); - - flatten( flat1.get(), back_inserter( types1 ) ); - flatten( flat2.get(), back_inserter( types2 ) ); - - result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer ); - } // if - } - - void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) { - result = dynamic_cast< VarArgsType* >( type2 ); - } - - void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) { - result = dynamic_cast< ZeroType* >( type2 ); - } - - void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) { - result = dynamic_cast< OneType* >( type2 ); - } - - Type * extractResultType( FunctionType * function ) { - if ( function->get_returnVals().size() == 0 ) { - return new VoidType( Type::Qualifiers() ); - } else if ( function->get_returnVals().size() == 1 ) { - return function->get_returnVals().front()->get_type()->clone(); - } else { - std::list< Type * > types; - for ( DeclarationWithType * decl : function->get_returnVals() ) { - types.push_back( decl->get_type()->clone() ); - } // for - return new TupleType( Type::Qualifiers(), types ); - } } Index: src/ResolvExpr/Unify.h =================================================================== --- src/ResolvExpr/Unify.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/Unify.h (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -20,14 +20,5 @@ #include "AST/Node.hpp" // for ptr #include "AST/TypeEnvironment.hpp" // for TypeEnvironment, AssertionSet, OpenVarSet -#include "Common/utility.h" // for deleteAll -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data -#include "TypeEnvironment.h" // for AssertionSet, OpenVarSet #include "WidenMode.h" // for WidenMode - -class Type; -class TypeInstType; -namespace SymTab { - class Indexer; -} namespace ast { @@ -37,22 +28,4 @@ namespace ResolvExpr { - -bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); -bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ); -bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); -bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); - -bool typesCompatible( const Type *, const Type *, const SymTab::Indexer & indexer, const TypeEnvironment & env ); -bool typesCompatibleIgnoreQualifiers( const Type *, const Type *, const SymTab::Indexer & indexer, const TypeEnvironment & env ); - -inline bool typesCompatible( const Type * t1, const Type * t2, const SymTab::Indexer & indexer ) { - TypeEnvironment env; - return typesCompatible( t1, t2, indexer, env ); -} - -inline bool typesCompatibleIgnoreQualifiers( const Type * t1, const Type * t2, const SymTab::Indexer & indexer ) { - TypeEnvironment env; - return typesCompatibleIgnoreQualifiers( t1, t2, indexer, env ); -} bool unify( @@ -85,7 +58,4 @@ const ast::TypeEnvironment & env = {} ); -/// Creates the type represented by the list of returnVals in a FunctionType. -/// The caller owns the return value. -Type * extractResultType( FunctionType * functionType ); /// Creates or extracts the type represented by returns in a `FunctionType`. ast::ptr extractResultType( const ast::FunctionType * func ); Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/module.mk (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -18,8 +18,4 @@ ResolvExpr/AdjustExprType.cc \ ResolvExpr/AdjustExprType.hpp \ - ResolvExpr/Alternative.cc \ - ResolvExpr/AlternativeFinder.cc \ - ResolvExpr/AlternativeFinder.h \ - ResolvExpr/Alternative.h \ ResolvExpr/Candidate.cpp \ ResolvExpr/CandidateFinder.cpp \ @@ -35,11 +31,8 @@ ResolvExpr/CurrentObject.cc \ ResolvExpr/CurrentObject.h \ - ResolvExpr/ExplodedActual.cc \ - ResolvExpr/ExplodedActual.h \ ResolvExpr/ExplodedArg.cpp \ ResolvExpr/ExplodedArg.hpp \ ResolvExpr/FindOpenVars.cc \ ResolvExpr/FindOpenVars.h \ - ResolvExpr/Occurs.cc \ ResolvExpr/PolyCost.cc \ ResolvExpr/PolyCost.hpp \ @@ -50,6 +43,4 @@ ResolvExpr/RenameVars.cc \ ResolvExpr/RenameVars.h \ - ResolvExpr/ResolveAssertions.cc \ - ResolvExpr/ResolveAssertions.h \ ResolvExpr/Resolver.cc \ ResolvExpr/Resolver.h \ @@ -61,6 +52,4 @@ ResolvExpr/SpecCost.cc \ ResolvExpr/SpecCost.hpp \ - ResolvExpr/TypeEnvironment.cc \ - ResolvExpr/TypeEnvironment.h \ ResolvExpr/typeops.h \ ResolvExpr/Unify.cc \ @@ -69,6 +58,4 @@ SRC += $(SRC_RESOLVEXPR) \ - ResolvExpr/AlternativePrinter.cc \ - ResolvExpr/AlternativePrinter.h \ ResolvExpr/CandidatePrinter.cpp \ ResolvExpr/CandidatePrinter.hpp \ Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision fa761c2aa9a4a9b1a22e28f45f380ba9d9ad36c0) +++ src/ResolvExpr/typeops.h (revision 2da12ae2df22a8ab193e99e082199971510f6663) @@ -19,5 +19,4 @@ #include "AST/Type.hpp" -#include "SynTree/Type.h" namespace SymTab { @@ -52,29 +51,4 @@ std::copy( i.begin(), i.end(), inserter ); *out++ = result; - } - } - - // in Occurs.cc - bool occurs( const Type * type, const std::string & varName, const TypeEnvironment & env ); - // new AST version in TypeEnvironment.cpp (only place it was used in old AST) - - template - bool occursIn( Type* ty, Iter begin, Iter end, const TypeEnvironment & env ) { - while ( begin != end ) { - if ( occurs( ty, *begin, env ) ) return true; - ++begin; - } - return false; - } - - /// flatten tuple type into list of types - template< typename OutputIterator > - void flatten( Type * type, OutputIterator out ) { - if ( TupleType * tupleType = dynamic_cast< TupleType * >( type ) ) { - for ( Type * t : tupleType->get_types() ) { - flatten( t, out ); - } - } else { - *out++ = type->clone(); } } @@ -120,7 +94,4 @@ return tupleFromTypes( tys.begin(), tys.end() ); } - - // in TypeEnvironment.cc - bool isFtype( const Type * type ); } // namespace ResolvExpr