Index: translator/ResolvExpr/AdjustExprType.cc =================================================================== --- translator/ResolvExpr/AdjustExprType.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/AdjustExprType.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,136 @@ +/* + * This file is part of the Cforall project + * + * $Id: AdjustExprType.cc,v 1.3 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "SynTree/Type.h" +#include "TypeEnvironment.h" +#include "SymTab/Indexer.h" + +namespace ResolvExpr { + +class AdjustExprType : public Mutator +{ + typedef Mutator Parent; + +public: + AdjustExprType( const TypeEnvironment &env, const SymTab::Indexer &indexer ); + +private: + virtual Type* mutate(VoidType *voidType); + virtual Type* mutate(BasicType *basicType); + virtual Type* mutate(PointerType *pointerType); + virtual Type* mutate(ArrayType *arrayType); + virtual Type* mutate(FunctionType *functionType); + virtual Type* mutate(StructInstType *aggregateUseType); + virtual Type* mutate(UnionInstType *aggregateUseType); + virtual Type* mutate(EnumInstType *aggregateUseType); + virtual Type* mutate(ContextInstType *aggregateUseType); + virtual Type* mutate(TypeInstType *aggregateUseType); + virtual Type* mutate(TupleType *tupleType); + + const TypeEnvironment &env; + const SymTab::Indexer &indexer; +}; + +void +adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) +{ + AdjustExprType adjuster( env, indexer ); + Type *newType = type->acceptMutator( adjuster ); + type = newType; +} + +AdjustExprType::AdjustExprType( const TypeEnvironment &env, const SymTab::Indexer &indexer ) + : env( env ), indexer( indexer ) +{ +} + +Type* +AdjustExprType::mutate(VoidType *voidType) +{ + return voidType; +} + +Type* +AdjustExprType::mutate(BasicType *basicType) +{ + return basicType; +} + +Type* +AdjustExprType::mutate(PointerType *pointerType) +{ + return pointerType; +} + +Type* +AdjustExprType::mutate(ArrayType *arrayType) +{ + PointerType *pointerType = new PointerType( arrayType->get_qualifiers(), arrayType->get_base()->clone() ); + delete arrayType; + return pointerType; +} + +Type* +AdjustExprType::mutate(FunctionType *functionType) +{ + PointerType *pointerType = new PointerType( Type::Qualifiers(), functionType ); + return pointerType; +} + +Type* +AdjustExprType::mutate(StructInstType *aggregateUseType) +{ + return aggregateUseType; +} + +Type* +AdjustExprType::mutate(UnionInstType *aggregateUseType) +{ + return aggregateUseType; +} + +Type* +AdjustExprType::mutate(EnumInstType *aggregateUseType) +{ + return aggregateUseType; +} + +Type* +AdjustExprType::mutate(ContextInstType *aggregateUseType) +{ + return aggregateUseType; +} + +Type* +AdjustExprType::mutate(TypeInstType *typeInst) +{ + EqvClass eqvClass; + if( env.lookup( typeInst->get_name(), eqvClass ) ) { + if( eqvClass.kind == TypeDecl::Ftype ) { + PointerType *pointerType = new PointerType( Type::Qualifiers(), typeInst ); + return pointerType; + } + } else if( NamedTypeDecl *ntDecl = indexer.lookupType( typeInst->get_name() ) ) { + if( TypeDecl *tyDecl = dynamic_cast< TypeDecl* >( ntDecl ) ) { + if( tyDecl->get_kind() == TypeDecl::Ftype ) { + PointerType *pointerType = new PointerType( Type::Qualifiers(), typeInst ); + return pointerType; + } + } + } + return typeInst; +} + +Type* +AdjustExprType::mutate(TupleType *tupleType) +{ + return tupleType; +} + + +} // namespace ResolvExpr Index: translator/ResolvExpr/Alternative.cc =================================================================== --- translator/ResolvExpr/Alternative.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Alternative.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,75 @@ +/* + * This file is part of the Cforall project + * + * $Id: Alternative.cc,v 1.6 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "Alternative.h" +#include "SynTree/Type.h" +#include "SynTree/Expression.h" +#include "utility.h" + +namespace ResolvExpr { + +Alternative::Alternative() + : expr( 0 ) +{ +} + +Alternative::Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost ) + : cost( cost ), cvtCost( Cost::zero ), expr( expr ), env( env ) +{ +} + +Alternative::Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost, const Cost &cvtCost ) + : cost( cost ), cvtCost( cvtCost ), expr( expr ), env( env ) +{ +} + +Alternative::Alternative( const Alternative &other ) +{ + initialize( other, *this ); +} + +Alternative & +Alternative::operator=( const Alternative &other ) +{ + if( &other == this ) return *this; + initialize( other, *this ); + return *this; +} + +void +Alternative::initialize( const Alternative &src, Alternative &dest ) +{ + dest.cost = src.cost; + dest.cvtCost = src.cvtCost; + dest.expr = maybeClone( src.expr ); + dest.env = src.env; +} + +Alternative::~Alternative() +{ + delete expr; +} + +void +Alternative::print( std::ostream &os, int indent ) const +{ + os << std::string( indent, ' ' ) << "Cost " << cost << ": "; + if( expr ) { + expr->print( os, indent ); + os << "(types:" << std::endl; + printAll( expr->get_results(), os, indent + 4 ); + os << ")" << std::endl; + } else { + os << "Null expression!" << std::endl; + } + os << std::string( indent, ' ' ) << "Environment: "; + env.print( os, indent+2 ); + os << std::endl; +} + + +} // namespace ResolvExpr Index: translator/ResolvExpr/Alternative.h =================================================================== --- translator/ResolvExpr/Alternative.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Alternative.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,43 @@ +/* + * This file is part of the Cforall project + * + * $Id: Alternative.h,v 1.9 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_ALTERNATIVE_H +#define RESOLVEXPR_ALTERNATIVE_H + +#include +#include "SynTree/SynTree.h" +#include "Cost.h" +#include "TypeEnvironment.h" + +namespace ResolvExpr { + +struct Alternative; +typedef std::list< Alternative > AltList; + +struct Alternative +{ + Alternative(); + Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost ); + Alternative( Expression *expr, const TypeEnvironment &env, const Cost& cost, const Cost &cvtCost ); + Alternative( const Alternative &other ); + Alternative &operator=( const Alternative &other ); + ~Alternative(); + + void initialize( const Alternative &src, Alternative &dest ); + + void print( std::ostream &os, int indent = 0 ) const; + + Cost cost; + Cost cvtCost; + Expression *expr; + TypeEnvironment env; +}; + + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_ALTERNATIVE_H */ Index: translator/ResolvExpr/AlternativeFinder.cc =================================================================== --- translator/ResolvExpr/AlternativeFinder.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/AlternativeFinder.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,928 @@ +/* + * This file is part of the Cforall project + * + * $Id: AlternativeFinder.cc,v 1.36 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include +#include +#include +#include +#include + +#include "AlternativeFinder.h" +#include "Alternative.h" +#include "Cost.h" +#include "typeops.h" +#include "Unify.h" +#include "RenameVars.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SynTree/Expression.h" +#include "SynTree/Initializer.h" +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" +#include "SymTab/Mangler.h" +#include "SynTree/TypeSubstitution.h" +#include "SymTab/Validate.h" +#include "Designators/Processor.h" +#include "Tuples/TupleAssignment.h" +#include "Tuples/NameMatcher.h" +#include "utility.h" + + +//#define DEBUG_COST + +namespace ResolvExpr { + +Expression * +resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) +{ + CastExpr *castToVoid = new CastExpr( expr ); + + AlternativeFinder finder( indexer, env ); + finder.findWithAdjustment( castToVoid ); + + // 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. + assert( finder.get_alternatives().size() == 1 ); + CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr ); + assert( newExpr ); + env = finder.get_alternatives().front().env; + return newExpr->get_arg()->clone(); +} + +namespace { + + 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; + } + } + + 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() ); + } + } + + Cost + sumCost( const AltList &in ) + { + Cost total; + for( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { + total += i->cost; + } + return total; + } + + struct PruneStruct + { + bool isAmbiguous; + AltList::iterator candidate; + PruneStruct() {} + PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {} + }; + + template< typename InputIterator, typename OutputIterator > + void + pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) + { + // 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; + for( std::list< Type* >::const_iterator retType = candidate->expr->get_results().begin(); retType != candidate->expr->get_results().end(); ++retType ) { + Type *newType = (*retType)->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 ) { +/// std::cout << "cost " << candidate->cost << " beats " << target->second.cost << std::endl; + selected[ mangleName ] = current; + } else if( candidate->cost == mapPlace->second.candidate->cost ) { +/// std::cout << "marking ambiguous" << std::endl; + mapPlace->second.isAmbiguous = true; + } + } else { + selected[ mangleName ] = current; + } + } + +/// std::cout << "there are " << selected.size() << " alternatives before elimination" << std::endl; + + // 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; + for( std::list< Type* >::iterator result = alt.expr->get_results().begin(); result != alt.expr->get_results().end(); ++result ) { + alt.env.applyFree( *result ); + } + *out++ = alt; + } + } + + } + + 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( AltList::iterator 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 ); + } + + template< typename InputIterator > + void + simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) + { + while( begin != end ) { + result.simpleCombine( (*begin++).env ); + } + } + + void + renameTypes( Expression *expr ) + { + for( std::list< Type* >::iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { + (*i)->accept( global_renamer ); + } + } +} + +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++; +/// std::cout << "findSubExprs" << std::endl; +/// printAlts( finder.alternatives, std::cout ); + *out++ = finder; + } +} + +AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ) + : indexer( indexer ), env( env ) +{ +} + +void +AlternativeFinder::find( Expression *expr, bool adjust ) +{ + expr->accept( *this ); + if( alternatives.empty() ) { + throw SemanticError( "No reasonable alternatives for expression ", expr ); + } + for( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) { + if( adjust ) { + adjustExprTypeList( i->expr->get_results().begin(), i->expr->get_results().end(), i->env, indexer ); + } + } +/// std::cout << "alternatives before prune:" << std::endl; +/// printAlts( alternatives, std::cout ); + AltList::iterator oldBegin = alternatives.begin(); + pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer ); + if( alternatives.begin() == oldBegin ) { + std::ostrstream stream; + stream << "Can't choose between alternatives for expression "; + expr->print( stream ); + stream << "Alternatives are:"; + AltList winners; + findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); + printAlts( winners, stream, 8 ); + throw SemanticError( std::string( stream.str(), stream.pcount() ) ); + } + alternatives.erase( oldBegin, alternatives.end() ); +/// std::cout << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; +} + +void +AlternativeFinder::findWithAdjustment( Expression *expr ) +{ + find( expr, true ); +} + +template< typename StructOrUnionType > +void +AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, 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 MemberExpr( dwt->clone(), expr->clone() ), env, newCost ) ); + renameTypes( alternatives.back().expr ); + } else { + assert( false ); + } + } +} + +void +AlternativeFinder::visit(ApplicationExpr *applicationExpr) +{ + alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) ); +} + +Cost +computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) +{ + ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( alt.expr ); + assert( appExpr ); + PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); + assert( pointer ); + FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); + assert( function ); + + Cost convCost( 0, 0, 0 ); + std::list< DeclarationWithType* >& formals = function->get_parameters(); + std::list< DeclarationWithType* >::iterator formal = formals.begin(); + std::list< Expression* >& actuals = appExpr->get_args(); + for( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { +/// std::cout << "actual expression:" << std::endl; +/// (*actualExpr)->print( std::cout, 8 ); +/// std::cout << "--- results are" << std::endl; +/// printAll( (*actualExpr)->get_results(), std::cout, 8 ); + std::list< DeclarationWithType* >::iterator startFormal = formal; + Cost actualCost; + for( std::list< Type* >::iterator actual = (*actualExpr)->get_results().begin(); actual != (*actualExpr)->get_results().end(); ++actual ) { + if( formal == formals.end() ) { + if( function->get_isVarArgs() ) { + convCost += Cost( 1, 0, 0 ); + break; + } else { + return Cost::infinity; + } + } +/// std::cout << std::endl << "converting "; +/// (*actual)->print( std::cout, 8 ); +/// std::cout << std::endl << " to "; +/// (*formal)->get_type()->print( std::cout, 8 ); + Cost newCost = conversionCost( *actual, (*formal)->get_type(), indexer, alt.env ); +/// std::cout << std::endl << "cost is" << newCost << std::endl; + + if( newCost == Cost::infinity ) { + return newCost; + } + convCost += newCost; + actualCost += newCost; + + convCost += Cost( 0, polyCost( (*formal)->get_type(), alt.env, indexer ) + polyCost( *actual, alt.env, indexer), 0 ); + + formal++; + } + if( actualCost != Cost( 0, 0, 0 ) ) { + std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal; + startFormalPlusOne++; + if( formal == startFormalPlusOne ) { + // not a tuple type + Type *newType = (*startFormal)->get_type()->clone(); + alt.env.apply( newType ); + *actualExpr = new CastExpr( *actualExpr, newType ); + } else { + TupleType *newType = new TupleType( Type::Qualifiers() ); + for( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) { + newType->get_types().push_back( (*i)->get_type()->clone() ); + } + alt.env.apply( newType ); + *actualExpr = new CastExpr( *actualExpr, newType ); + } + } + + } + if( formal != formals.end() ) { + return Cost::infinity; + } + + for( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { +/// std::cout << std::endl << "converting "; +/// assert->second.actualType->print( std::cout, 8 ); +/// std::cout << std::endl << " to "; +/// assert->second.formalType->print( std::cout, 8 ); + Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); +/// std::cout << std::endl << "cost of conversion is " << newCost << std::endl; + if( newCost == Cost::infinity ) { + return newCost; + } + convCost += newCost; + + convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer), 0 ); + } + + return convCost; +} + +void +makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) +{ + for( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { + unifiableVars[ (*tyvar)->get_name() ] = (*tyvar)->get_kind(); + for( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { + needAssertions[ *assert ] = true; + } +/// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() ); + } +} + +bool +AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) +{ + std::list< TypeEnvironment > toBeDone; + simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv ); + // make sure we don't widen any existing bindings + for( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) { + i->allowWidening = false; + } + resultEnv.extractOpenVars( openVars ); + + /* + Tuples::NameMatcher matcher( formals ); + try { + matcher.match( actuals ); + } catch ( Tuples::NoMatch &e ) { + std::cerr << "Alternative doesn't match: " << e.message << std::endl; + } + */ + std::list< DeclarationWithType* >::iterator formal = formals.begin(); + for( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { + for( std::list< Type* >::iterator actual = actualExpr->expr->get_results().begin(); actual != actualExpr->expr->get_results().end(); ++actual ) { + if( formal == formals.end() ) { + return isVarArgs; + } +/// std::cerr << "formal type is "; +/// (*formal)->get_type()->print( std::cerr ); +/// std::cerr << std::endl << "actual type is "; +/// (*actual)->print( std::cerr ); +/// std::cerr << std::endl; + if( !unify( (*formal)->get_type(), *actual, resultEnv, resultNeed, resultHave, openVars, indexer ) ) { + return false; + } + formal++; + } + } + // Handling of default values + while( formal != formals.end() ) { + if( ObjectDecl *od = dynamic_cast( *formal ) ) + if( SingleInit *si = dynamic_cast( od->get_init() )) + // so far, only constant expressions are accepted as default values + if ( ConstantExpr *cnstexpr = dynamic_cast(si->get_value()) ) + if ( Constant *cnst = dynamic_cast( cnstexpr->get_constant() ) ) + if( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { + // XXX Don't know if this is right + actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) ); + formal++; + if (formal == formals.end()) break; + } + return false; + } + return true; +} + +static const int recursionLimit = 10; + +void +addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) +{ + for( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) { + if( i->second == true ) { + i->first->accept( indexer ); + } + } +} + +template< typename ForwardIterator, typename OutputIterator > +void +inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) +{ + if( begin == end ) { + if( newNeed.empty() ) { + *out++ = newAlt; + return; + } else if( level >= recursionLimit ) { + throw SemanticError( "Too many recursive assertions" ); + } else { + AssertionSet newerNeed; +/// std::cerr << "recursing with new set:" << std::endl; +/// printAssertionSet( newNeed, std::cerr, 8 ); + inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out ); + return; + } + } + + ForwardIterator cur = begin++; + if( !cur->second ) { + inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out ); + } + DeclarationWithType *curDecl = cur->first; +/// std::cerr << "inferRecursive: assertion is "; +/// curDecl->print( std::cerr ); +/// std::cerr << std::endl; + std::list< DeclarationWithType* > candidates; + decls.lookupId( curDecl->get_name(), candidates ); +/// if( candidates.empty() ) { std::cout << "no candidates!" << std::endl; } + for( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) { +/// std::cout << "inferRecursive: candidate is "; +/// (*candidate)->print( std::cout ); +/// std::cout << std::endl; + AssertionSet newHave, newerNeed( newNeed ); + TypeEnvironment newEnv( newAlt.env ); + OpenVarSet newOpenVars( openVars ); + Type *adjType = (*candidate)->get_type()->clone(); + adjustExprType( adjType, newEnv, indexer ); + adjType->accept( global_renamer ); +/// std::cerr << "unifying "; +/// curDecl->get_type()->print( std::cerr ); +/// std::cerr << " with "; +/// adjType->print( std::cerr ); +/// std::cerr << std::endl; + if( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) { +/// std::cerr << "success!" << std::endl; + SymTab::Indexer newDecls( decls ); + addToIndexer( newHave, newDecls ); + Alternative newerAlt( newAlt ); + newerAlt.env = newEnv; + assert( (*candidate)->get_uniqueId() ); + Expression *varExpr = new VariableExpr( static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) ) ); + deleteAll( varExpr->get_results() ); + varExpr->get_results().clear(); + varExpr->get_results().push_front( adjType->clone() ); +/// std::cout << "satisfying assertion " << curDecl->get_uniqueId() << " "; +/// curDecl->print( std::cout ); +/// std::cout << " with declaration " << (*candidate)->get_uniqueId() << " "; +/// (*candidate)->print( std::cout ); +/// std::cout << std::endl; + ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr ); + // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions + appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr ); + inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out ); + } else { + delete adjType; + } + } +} + +template< typename OutputIterator > +void +AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) +{ +/// std::cout << "inferParameters: assertions needed are" << std::endl; +/// printAll( need, std::cout, 8 ); + SymTab::Indexer decls( indexer ); +/// std::cout << "============= original indexer" << std::endl; +/// indexer.print( std::cout ); +/// std::cout << "============= new indexer" << std::endl; +/// decls.print( std::cout ); + addToIndexer( have, decls ); + AssertionSet newNeed; + inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out ); +/// std::cout << "declaration 14 is "; +/// Declaration::declFromId +/// *out++ = newAlt; +} + +template< typename OutputIterator > +void +AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) +{ + OpenVarSet openVars; + AssertionSet resultNeed, resultHave; + TypeEnvironment resultEnv; + makeUnifiableVars( funcType, openVars, resultNeed ); + if( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) { + ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); + Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) ); + makeExprList( actualAlt, appExpr->get_args() ); +/// std::cout << "need assertions:" << std::endl; +/// printAssertionSet( resultNeed, std::cout, 8 ); + inferParameters( resultNeed, resultHave, newAlt, openVars, out ); + } +} + +void +AlternativeFinder::visit(UntypedExpr *untypedExpr) +{ + bool doneInit = false; + AlternativeFinder funcOpFinder( indexer, env ); + + AlternativeFinder funcFinder( indexer, env ); + { + NameExpr *fname; + if ( (fname = dynamic_cast(untypedExpr->get_function())) + && ( fname->get_name() == std::string("LabAddress")) ) { + alternatives.push_back( Alternative(untypedExpr, env, Cost()) ); + return; + } + } + + funcFinder.findWithAdjustment( untypedExpr->get_function() ); + std::list< AlternativeFinder > argAlternatives; + findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) ); + + std::list< AltList > possibilities; + combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); + + Tuples::TupleAssignSpotter tassign(this); + if ( tassign.isTupleAssignment(untypedExpr, possibilities) ) { + // take care of possible tuple assignments, or discard expression + return; + } // else ... + + AltList candidates; + + for( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) { +/// std::cout << "working on alternative: " << std::endl; +/// func->print( std::cout, 8 ); + // check if the type is pointer to function + PointerType *pointer; + if( func->expr->get_results().size() == 1 && ( pointer = dynamic_cast< PointerType* >( func->expr->get_results().front() ) ) ) { + if( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { + for( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { + // XXX + //Designators::check_alternative( function, *actualAlt ); + makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); + } + } else if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) { + EqvClass eqvClass; + if( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) { + if( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) { + for( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { + makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); + } + } + } + } + } else { + // seek a function operator that's compatible + if( !doneInit ) { + doneInit = true; + NameExpr *opExpr = new NameExpr( "?()" ); + try { + funcOpFinder.findWithAdjustment( opExpr ); + } catch( SemanticError &e ) { + // it's ok if there aren't any defined function ops + } +/// std::cout << "known function ops:" << std::endl; +/// printAlts( funcOpFinder.alternatives, std::cout, 8 ); + } + + for( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { + // check if the type is pointer to function + PointerType *pointer; + if( funcOp->expr->get_results().size() == 1 + && ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_results().front() ) ) ) { + if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { + for( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { + AltList currentAlt; + currentAlt.push_back( *func ); + currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() ); + makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) ); + } + } + } + } + } + } + + for( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { + Cost cvtCost = computeConversionCost( *withFunc, indexer ); + +#ifdef DEBUG_COST + ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( withFunc->expr ); + assert( appExpr ); + PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); + assert( pointer ); + FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); + assert( function ); + std::cout << "Case +++++++++++++" << std::endl; + std::cout << "formals are:" << std::endl; + printAll( function->get_parameters(), std::cout, 8 ); + std::cout << "actuals are:" << std::endl; + printAll( appExpr->get_args(), std::cout, 8 ); + std::cout << "bindings are:" << std::endl; + withFunc->env.print( std::cout, 8 ); + std::cout << "cost of conversion is:" << cvtCost << std::endl; +#endif + + if( cvtCost != Cost::infinity ) { + withFunc->cvtCost = cvtCost; + alternatives.push_back( *withFunc ); + } + } + candidates.clear(); + candidates.splice( candidates.end(), alternatives ); + + findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) ); +} + +bool +isLvalue( Expression *expr ) { + for( std::list< Type* >::const_iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { + if( !(*i)->get_isLvalue() ) return false; + } + return true; +} + +void +AlternativeFinder::visit(AddressExpr *addressExpr) +{ + AlternativeFinder finder( indexer, env ); + finder.find( addressExpr->get_arg() ); + for( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { + if( isLvalue( i->expr ) ) { + alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); + } + } +} + +void +AlternativeFinder::visit(CastExpr *castExpr) +{ + for( std::list< Type* >::iterator i = castExpr->get_results().begin(); i != castExpr->get_results().end(); ++i ) { + SymTab::validateType( *i, &indexer ); + adjustExprType( *i, env, indexer ); + } + + AlternativeFinder finder( indexer, env ); + finder.findWithAdjustment( castExpr->get_arg() ); + + AltList candidates; + for( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { + AssertionSet needAssertions, haveAssertions; + OpenVarSet 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 = (*i).expr->get_results().size() - castExpr->get_results().size(); + if( discardedValues < 0 ) continue; + std::list< Type* >::iterator candidate_end = (*i).expr->get_results().begin(); + std::advance( candidate_end, castExpr->get_results().size() ); + if( !unifyList( (*i).expr->get_results().begin(), candidate_end, + castExpr->get_results().begin(), castExpr->get_results().end(), i->env, needAssertions, haveAssertions, openVars, indexer ) ) continue; + Cost thisCost = castCostList( (*i).expr->get_results().begin(), candidate_end, + castExpr->get_results().begin(), castExpr->get_results().end(), indexer, i->env ); + if( thisCost != Cost::infinity ) { + // count one safe conversion for each value that is thrown away + thisCost += Cost( 0, 0, discardedValues ); + CastExpr *newExpr = castExpr->clone(); + newExpr->set_arg( i->expr->clone() ); + candidates.push_back( Alternative( newExpr, i->env, i->cost, thisCost ) ); + } + } + + // 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::visit(UntypedMemberExpr *memberExpr) +{ + AlternativeFinder funcFinder( indexer, env ); + funcFinder.findWithAdjustment( memberExpr->get_aggregate() ); + + for( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) { + if( agg->expr->get_results().size() == 1 ) { + if( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_results().front() ) ) { + addAggMembers( structInst, agg->expr, agg->cost, memberExpr->get_member() ); + } else if( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_results().front() ) ) { + addAggMembers( unionInst, agg->expr, agg->cost, memberExpr->get_member() ); + } + } + } +} + +void +AlternativeFinder::visit(MemberExpr *memberExpr) +{ + alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) ); +} + +void +AlternativeFinder::visit(NameExpr *nameExpr) +{ + std::list< DeclarationWithType* > declList; + indexer.lookupId( nameExpr->get_name(), declList ); +/// std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; + for( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) { + VariableExpr newExpr( *i, nameExpr->get_argName() ); + alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); +/// std::cerr << "decl is "; +/// (*i)->print( std::cerr ); +/// std::cerr << std::endl; +/// std::cerr << "newExpr is "; +/// newExpr.print( std::cerr ); +/// std::cerr << std::endl; + renameTypes( alternatives.back().expr ); + if( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) { + addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), "" ); + } else if( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) { + addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), "" ); + } + } +} + +void +AlternativeFinder::visit(VariableExpr *variableExpr) +{ + alternatives.push_back( Alternative( variableExpr->clone(), env, Cost::zero ) ); +} + +void +AlternativeFinder::visit(ConstantExpr *constantExpr) +{ + alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) ); +} + +void +AlternativeFinder::visit(SizeofExpr *sizeofExpr) +{ + if( sizeofExpr->get_isType() ) { + alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) ); + } else { + AlternativeFinder finder( indexer, env ); + finder.find( sizeofExpr->get_expr() ); + if( finder.alternatives.size() != 1 ) { + throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() ); + } + Alternative &choice = finder.alternatives.front(); + alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); + } +} + +void +AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) +{ + // assume no polymorphism + // assume no implicit conversions + assert( function->get_parameters().size() == 1 ); +/// std::cout << "resolvAttr: funcDecl is "; +/// funcDecl->print( std::cout ); +/// std::cout << " argType is "; +/// argType->print( std::cout ); +/// std::cout << std::endl; + if( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) { + alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) ); + for( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) { + alternatives.back().expr->get_results().push_back( (*i)->get_type()->clone() ); + } + } +} + +void +AlternativeFinder::visit(AttrExpr *attrExpr) +{ + // assume no 'pointer-to-attribute' + NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() ); + assert( nameExpr ); + std::list< DeclarationWithType* > attrList; + indexer.lookupId( nameExpr->get_name(), attrList ); + if( attrExpr->get_isType() || attrExpr->get_expr() ) { + for( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { + // check if the type is function + if( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) { + // assume exactly one parameter + if( function->get_parameters().size() == 1 ) { + if( attrExpr->get_isType() ) { + resolveAttr( *i, function, attrExpr->get_type(), env ); + } else { + AlternativeFinder finder( indexer, env ); + finder.find( attrExpr->get_expr() ); + for( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) { + if( choice->expr->get_results().size() == 1 ) { + resolveAttr(*i, function, choice->expr->get_results().front(), choice->env ); + } + } + } + } + } + } + } else { + for( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { + VariableExpr newExpr( *i ); + alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); + renameTypes( alternatives.back().expr ); + } + } +} + +void +AlternativeFinder::visit(LogicalExpr *logicalExpr) +{ + AlternativeFinder firstFinder( indexer, env ); + firstFinder.findWithAdjustment( logicalExpr->get_arg1() ); + for( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { + AlternativeFinder secondFinder( indexer, first->env ); + secondFinder.findWithAdjustment( logicalExpr->get_arg2() ); + for( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { + LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() ); + alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) ); + } + } +} + +void +AlternativeFinder::visit(ConditionalExpr *conditionalExpr) +{ + AlternativeFinder firstFinder( indexer, env ); + firstFinder.findWithAdjustment( conditionalExpr->get_arg1() ); + for( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { + AlternativeFinder secondFinder( indexer, first->env ); + secondFinder.findWithAdjustment( conditionalExpr->get_arg2() ); + for( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { + AlternativeFinder thirdFinder( indexer, second->env ); + thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() ); + for( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) { + OpenVarSet openVars; + AssertionSet needAssertions, haveAssertions; + Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost ); + std::list< Type* > commonTypes; + if( unifyList( second->expr->get_results().begin(), second->expr->get_results().end(), third->expr->get_results().begin(), third->expr->get_results().end(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) { + ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() ); + std::list< Type* >::const_iterator original = second->expr->get_results().begin(); + std::list< Type* >::const_iterator commonType = commonTypes.begin(); + for( ; original != second->expr->get_results().end() && commonType != commonTypes.end(); ++original, ++commonType ) { + if( *commonType ) { + newExpr->get_results().push_back( *commonType ); + } else { + newExpr->get_results().push_back( (*original)->clone() ); + } + } + newAlt.expr = newExpr; + inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); + } + } + } + } +} + +void +AlternativeFinder::visit(CommaExpr *commaExpr) +{ + TypeEnvironment newEnv( env ); + Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv ); + AlternativeFinder secondFinder( indexer, newEnv ); + secondFinder.findWithAdjustment( commaExpr->get_arg2() ); + for( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) { + alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) ); + } + delete newFirstArg; +} + +void +AlternativeFinder::visit(TupleExpr *tupleExpr) +{ + std::list< AlternativeFinder > subExprAlternatives; + findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); + std::list< AltList > possibilities; + combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); + for( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { + TupleExpr *newExpr = new TupleExpr; + makeExprList( *i, newExpr->get_exprs() ); + for( std::list< Expression* >::const_iterator resultExpr = newExpr->get_exprs().begin(); resultExpr != newExpr->get_exprs().end(); ++resultExpr ) { + for( std::list< Type* >::const_iterator resultType = (*resultExpr)->get_results().begin(); resultType != (*resultExpr)->get_results().end(); ++resultType ) { + newExpr->get_results().push_back( (*resultType)->clone() ); + } + } + + TypeEnvironment compositeEnv; + simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); + alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) ); + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/AlternativeFinder.h =================================================================== --- translator/ResolvExpr/AlternativeFinder.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/AlternativeFinder.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,79 @@ +/* + * This file is part of the Cforall project + * + * $Id: AlternativeFinder.h,v 1.19 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_ALTERNATIVEFINDER_H +#define RESOLVEXPR_ALTERNATIVEFINDER_H + +#include + +#include "Alternative.h" +#include "Unify.h" +#include "SynTree/SynTree.h" +#include "SymTab/Indexer.h" +#include "SynTree/TypeSubstitution.h" + +namespace ResolvExpr { + +class AlternativeFinder : public Visitor +{ +public: + AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ); + void find( Expression *expr, bool adjust = false ); + void findWithAdjustment( 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; } +private: + virtual void visit(ApplicationExpr *applicationExpr); + virtual void visit(UntypedExpr *untypedExpr); + virtual void visit(AddressExpr *addressExpr); + virtual void visit(CastExpr *castExpr); + virtual void visit(UntypedMemberExpr *memberExpr); + virtual void visit(MemberExpr *memberExpr); + virtual void visit(NameExpr *variableExpr); + virtual void visit(VariableExpr *variableExpr); + virtual void visit(ConstantExpr *constantExpr); + virtual void visit(SizeofExpr *sizeofExpr); + virtual void visit(AttrExpr *attrExpr); + virtual void visit(LogicalExpr *logicalExpr); + virtual void visit(ConditionalExpr *conditionalExpr); + virtual void visit(CommaExpr *commaExpr); + virtual void visit(TupleExpr *tupleExpr); + public: // xxx - temporary hack - should make Tuples::TupleAssignment a friend + template< typename InputIterator, typename OutputIterator > + void findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ); + + private: + template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const std::string &name ); + bool instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ); + template< typename OutputIterator > + void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ); + template< typename OutputIterator > + void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ); + void resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ); + + const SymTab::Indexer &indexer; + AltList alternatives; + const TypeEnvironment &env; +}; + +Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) +; + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_ALTERNATIVEFINDER_H */ Index: translator/ResolvExpr/AlternativePrinter.cc =================================================================== --- translator/ResolvExpr/AlternativePrinter.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/AlternativePrinter.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,39 @@ +/* + * This file is part of the Cforall project + * + * $Id: AlternativePrinter.cc,v 1.5 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "AlternativePrinter.h" +#include "AlternativeFinder.h" +#include "Alternative.h" +#include "SynTree/Statement.h" +#include "SynTree/Type.h" +#include "SynTree/Expression.h" +#include "utility.h" + +namespace ResolvExpr { + +AlternativePrinter::AlternativePrinter( std::ostream &os ) + : SymTab::Indexer( false ), os( os ) +{ +} + +void +AlternativePrinter::visit(ExprStmt *exprStmt) +{ + TypeEnvironment env; + AlternativeFinder finder( *this, 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; + printAll( i->expr->get_results(), os ); +// i->print( os ); + os << std::endl; + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/AlternativePrinter.h =================================================================== --- translator/ResolvExpr/AlternativePrinter.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/AlternativePrinter.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,30 @@ +/* + * This file is part of the Cforall project + * + * $Id: AlternativePrinter.h,v 1.2 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_ALTERNATIVEPRINTER_H +#define RESOLVEXPR_ALTERNATIVEPRINTER_H + +#include + +#include "Alternative.h" +#include "SymTab/Indexer.h" + +namespace ResolvExpr { + +class AlternativePrinter : public SymTab::Indexer +{ +public: + AlternativePrinter( std::ostream &os ); + virtual void visit(ExprStmt *exprStmt); + +private: + std::ostream &os; +}; + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_ALTERNATIVEPRINTER_H */ Index: translator/ResolvExpr/CastCost.cc =================================================================== --- translator/ResolvExpr/CastCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/CastCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,105 @@ +/* + * This file is part of the Cforall project + * + * $Id: CastCost.cc,v 1.11 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "Cost.h" +#include "ConversionCost.h" +#include "SynTree/Type.h" +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" + + +namespace ResolvExpr { + +class CastCost : public ConversionCost +{ +public: + CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ); + + virtual void visit(BasicType *basicType); + virtual void visit(PointerType *pointerType); +}; + +Cost +castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) +{ +// std::cout << "casting" << std::endl; +// src->print( std::cout, 8 ); +// std::cout << std::endl << "to" << std::endl; +// dest->print( std::cout, 8 ); + if( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { + EqvClass eqvClass; + NamedTypeDecl *namedType; + if( env.lookup( destAsTypeInst->get_name(), eqvClass ) ) { + return castCost( src, eqvClass.type, indexer, env ); + } else if( ( namedType = indexer.lookupType( destAsTypeInst->get_name() ) ) ) { + TypeDecl *type = dynamic_cast< TypeDecl* >( namedType ); + // all typedefs should be gone by this point + assert( type ); + if( type->get_base() ) { + return castCost( src, type->get_base(), indexer, env ) + Cost( 0, 0, 1 ); + } + } + } + if( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) { +// std::cout << "types are compatible" << std::endl; + return Cost( 0, 0, 0 ); + } else if( dynamic_cast< VoidType* >( dest ) ) { +// std::cout << "destination is void" << std::endl; + return Cost( 0, 0, 1 ); + } else { + CastCost converter( dest, indexer, env ); + src->accept( converter ); +// std::cout << "cost is " << converter.get_cost() << std::endl; + if( converter.get_cost() == Cost::infinity ) { + return Cost::infinity; + } else { + return converter.get_cost() + Cost( 0, 0, 0 ); + } + } +} + +CastCost::CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) + : ConversionCost( dest, indexer, env ) +{ +} + +void +CastCost::visit(BasicType *basicType) +{ + if( dynamic_cast< PointerType* >( dest ) ) { + cost = Cost( 1, 0, 0 ); + } else { + ConversionCost::visit( basicType ); + } +} + +void +CastCost::visit(PointerType *pointerType) +{ + if( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) { + if( pointerType->get_qualifiers() <= destAsPtr->get_qualifiers() && typesCompatibleIgnoreQualifiers( pointerType->get_base(), destAsPtr->get_base(), indexer, env ) ) { + cost = Cost( 0, 0, 1 ); + } else if( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) { + if( destAsBasic->isInteger() ) { + cost = Cost( 1, 0, 0 ); + } + } else { + TypeEnvironment newEnv( env ); + newEnv.add( pointerType->get_forall() ); + newEnv.add( pointerType->get_base()->get_forall() ); + int assignResult = ptrsCastable( pointerType->get_base(), destAsPtr->get_base(), newEnv, indexer ); + if( assignResult > 0 ) { + cost = Cost( 0, 0, 1 ); + } else if( assignResult < 0 ) { + cost = Cost( 1, 0, 0 ); + } + } + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/CommonType.cc =================================================================== --- translator/ResolvExpr/CommonType.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/CommonType.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,239 @@ +/* + * This file is part of the Cforall project + * + * $Id: CommonType.cc,v 1.6 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "SynTree/Type.h" +#include "Unify.h" + + +/// #define DEBUG + +namespace ResolvExpr { + +class CommonType : public Visitor +{ +public: + CommonType( Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); + + Type *get_result() const { return result; } + +private: + virtual void visit( VoidType *voidType ); + virtual void visit( BasicType *basicType ); + virtual void visit( PointerType *pointerType ); + virtual void visit( ArrayType *arrayType ); + virtual void visit( FunctionType *functionType ); + virtual void visit( StructInstType *aggregateUseType ); + virtual void visit( UnionInstType *aggregateUseType ); + virtual void visit( EnumInstType *aggregateUseType ); + virtual void visit( ContextInstType *aggregateUseType ); + virtual void visit( TypeInstType *aggregateUseType ); + virtual void visit( TupleType *tupleType ); + + 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 * +commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) +{ + CommonType visitor( type2, widenFirst, widenSecond, indexer, env, openVars ); + type1->accept( visitor ); + Type *result = visitor.get_result(); + if( !result ) { + if( widenSecond ) { + TypeInstType *inst = dynamic_cast< TypeInstType* >( type2 ); + if( inst ) { + NamedTypeDecl *nt = indexer.lookupType( inst->get_name() ); + if( nt ) { + TypeDecl *type = dynamic_cast< TypeDecl* >( nt ); + assert( type ); + if( type->get_base() ) { + Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers(); + AssertionSet have, need; + OpenVarSet newOpen( openVars ); + type1->get_qualifiers() = Type::Qualifiers(); + type->get_base()->get_qualifiers() = tq1; + if( unifyExact( type1, type->get_base(), env, have, need, newOpen, indexer ) ) { + result = type1->clone(); + result->get_qualifiers() = tq1 + tq2; + } + type1->get_qualifiers() = tq1; + type->get_base()->get_qualifiers() = Type::Qualifiers(); + } + } + } + } + } +#ifdef DEBUG + std::cout << "============= commonType" << std::endl << "type1 is "; + type1->print( std::cout ); + std::cout << " type2 is "; + type2->print( std::cout ); + if( result ) { + std::cout << " common type is "; + result->print( std::cout ); + } else { + std::cout << " no common type"; + } + std::cout << std::endl; +#endif + return result; +} + +static const BasicType::Kind combinedType[ BasicType::NUMBER_OF_BASIC_TYPES ][ BasicType::NUMBER_OF_BASIC_TYPES ] = +{ +/* Bool Char SignedChar UnsignedChar ShortSignedInt ShortUnsignedInt SignedInt UnsignedInt LongSignedInt LongUnsignedInt LongLongSignedInt LongLongUnsignedInt Float Double LongDouble FloatComplex DoubleComplex LongDoubleComplex FloatImaginary DoubleImaginary LongDoubleImaginary */ +/* Bool */ { BasicType::Bool, BasicType::Char, BasicType::SignedChar, BasicType::UnsignedChar, BasicType::ShortSignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* Char */ { BasicType::Char, BasicType::Char, BasicType::UnsignedChar, BasicType::UnsignedChar, BasicType::ShortSignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* SignedChar */ { BasicType::SignedChar, BasicType::UnsignedChar, BasicType::SignedChar, BasicType::UnsignedChar, BasicType::ShortSignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* UnsignedChar */ { BasicType::UnsignedChar, BasicType::UnsignedChar, BasicType::UnsignedChar, BasicType::UnsignedChar, BasicType::ShortSignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* ShortSignedInt */ { BasicType::ShortSignedInt, BasicType::ShortSignedInt, BasicType::ShortSignedInt, BasicType::ShortSignedInt, BasicType::ShortSignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* ShortUnsignedInt */ { BasicType::ShortUnsignedInt, BasicType::ShortUnsignedInt, BasicType::ShortUnsignedInt, BasicType::ShortUnsignedInt, BasicType::ShortUnsignedInt, BasicType::ShortUnsignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* SignedInt */ { BasicType::SignedInt, BasicType::SignedInt, BasicType::SignedInt, BasicType::SignedInt, BasicType::SignedInt, BasicType::SignedInt, BasicType::SignedInt, BasicType::UnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* UnsignedInt */ { BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::UnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongSignedInt */ { BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongSignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongUnsignedInt */ { BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongUnsignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongLongSignedInt */ { BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongSignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongLongUnsignedInt */ { BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* Float */ { BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Float, BasicType::Double, BasicType::LongDouble, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* Double */ { BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::Double, BasicType::LongDouble, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongDouble */ { BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDouble, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex }, +/* FloatComplex */ { BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* DoubleComplex */ { BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, +/* LongDoubleComplex */ { BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex }, +/* FloatImaginary */ { BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::FloatImaginary, BasicType::DoubleImaginary, BasicType::LongDoubleImaginary }, +/* DoubleImaginary */ { BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::DoubleComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex, BasicType::DoubleImaginary, BasicType::DoubleImaginary, BasicType::LongDoubleImaginary }, +/* LongDoubleImaginary */ { BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleComplex, BasicType::LongDoubleImaginary, BasicType::LongDoubleImaginary, BasicType::LongDoubleImaginary } +}; + +CommonType::CommonType( 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::visit( VoidType *voidType ) +{ +} + +void +CommonType::visit( BasicType *basicType ) +{ + if( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { + BasicType::Kind newType = combinedType[ basicType->get_kind() ][ otherBasic->get_kind() ]; + if( ( ( newType == basicType->get_kind() && basicType->get_qualifiers() >= otherBasic->get_qualifiers() ) || widenFirst ) && ( ( newType == otherBasic->get_kind() && basicType->get_qualifiers() <= otherBasic->get_qualifiers() ) || widenSecond ) ) { + result = new BasicType( basicType->get_qualifiers() + otherBasic->get_qualifiers(), newType ); + } + } +} + +void +CommonType::visit( PointerType *pointerType ) +{ + if( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) { + if( widenFirst && dynamic_cast< VoidType* >( otherPointer->get_base() ) ) { + result = otherPointer->clone(); + result->get_qualifiers() += pointerType->get_qualifiers(); + } else if( widenSecond && dynamic_cast< VoidType* >( pointerType->get_base() ) ) { + result = pointerType->clone(); + result->get_qualifiers() += otherPointer->get_qualifiers(); + } else if( ( pointerType->get_base()->get_qualifiers() >= otherPointer->get_base()->get_qualifiers() || widenFirst ) + && ( pointerType->get_base()->get_qualifiers() <= otherPointer->get_base()->get_qualifiers() || widenSecond ) ) { + Type::Qualifiers tq1 = pointerType->get_base()->get_qualifiers(), tq2 = otherPointer->get_base()->get_qualifiers(); + pointerType->get_base()->get_qualifiers() = Type::Qualifiers(); + otherPointer->get_base()->get_qualifiers() = Type::Qualifiers(); + AssertionSet have, need; + OpenVarSet newOpen( openVars ); + if( unifyExact( pointerType->get_base(), otherPointer->get_base(), env, have, need, newOpen, indexer ) ) { + if( tq1 < tq2 ) { + result = pointerType->clone(); + } else { + result = otherPointer->clone(); + } + result->get_qualifiers() = tq1 + tq2; + } else { + /// std::cout << "place for ptr-to-type" << std::endl; + } + pointerType->get_base()->get_qualifiers() = tq1; + otherPointer->get_base()->get_qualifiers() = tq2; + } + } +} + +void +CommonType::visit( ArrayType *arrayType ) +{ +} + +void +CommonType::visit( FunctionType *functionType ) +{ +} + +template< typename RefType > void +CommonType::handleRefType( RefType *inst, Type *other ) +{ +} + +void +CommonType::visit( StructInstType *aggregateUseType ) +{ +} + +void +CommonType::visit( UnionInstType *aggregateUseType ) +{ +} + +void +CommonType::visit( EnumInstType *aggregateUseType ) +{ +} + +void +CommonType::visit( ContextInstType *aggregateUseType ) +{ +} + +void +CommonType::visit( TypeInstType *inst ) +{ + if( widenFirst ) { + NamedTypeDecl *nt = indexer.lookupType( inst->get_name() ); + if( nt ) { + TypeDecl *type = dynamic_cast< TypeDecl* >( nt ); + assert( type ); + if( type->get_base() ) { + Type::Qualifiers tq1 = inst->get_qualifiers(), tq2 = type2->get_qualifiers(); + AssertionSet have, need; + OpenVarSet newOpen( openVars ); + type2->get_qualifiers() = Type::Qualifiers(); + type->get_base()->get_qualifiers() = tq1; + if( unifyExact( type->get_base(), type2, env, have, need, newOpen, indexer ) ) { + result = type2->clone(); + result->get_qualifiers() = tq1 + tq2; + } + type2->get_qualifiers() = tq2; + type->get_base()->get_qualifiers() = Type::Qualifiers(); + } + } + } +} + +void +CommonType::visit( TupleType *tupleType ) +{ +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/ConversionCost.cc =================================================================== --- translator/ResolvExpr/ConversionCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/ConversionCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,269 @@ +/* + * This file is part of the Cforall project + * + * $Id: ConversionCost.cc,v 1.11 2005/08/29 20:14:15 rcbilson Exp $ + * + */ + +#include "ConversionCost.h" +#include "typeops.h" +#include "SynTree/Type.h" +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" + + +namespace ResolvExpr { + +const Cost Cost::zero = Cost( 0, 0, 0 ); +const Cost Cost::infinity = Cost( -1, -1, -1 ); + +Cost +conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) +{ + if( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { + EqvClass eqvClass; + NamedTypeDecl *namedType; +/// std::cout << "type inst " << destAsTypeInst->get_name(); + if( env.lookup( destAsTypeInst->get_name(), eqvClass ) ) { + return conversionCost( src, eqvClass.type, indexer, env ); + } else if( ( namedType = indexer.lookupType( destAsTypeInst->get_name() ) ) ) { +/// std::cout << " found" << std::endl; + TypeDecl *type = dynamic_cast< TypeDecl* >( namedType ); + // all typedefs should be gone by this point + assert( type ); + if( type->get_base() ) { + return conversionCost( src, type->get_base(), indexer, env ) + Cost( 0, 0, 1 ); + } + } +/// std::cout << " not found" << std::endl; + } +/// std::cout << "src is "; +/// src->print( std::cout ); +/// std::cout << std::endl << "dest is "; +/// dest->print( std::cout ); +/// std::cout << std::endl << "env is" << std::endl; +/// env.print( std::cout, 8 ); + if( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) { +/// std::cout << "compatible!" << std::endl; + return Cost( 0, 0, 0 ); + } else if( dynamic_cast< VoidType* >( dest ) ) { + return Cost( 0, 0, 1 ); + } else { + ConversionCost converter( dest, indexer, env ); + src->accept( converter ); + if( converter.get_cost() == Cost::infinity ) { + return Cost::infinity; + } else { + return converter.get_cost() + Cost( 0, 0, 0 ); + } + } +} + +ConversionCost::ConversionCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) + : dest( dest ), indexer( indexer ), cost( Cost::infinity ), env( env ) +{ +} + +/* +Old +=== + Double + | + Float + | + ULong + / \ + UInt Long + \ / + Int + | + Ushort + | + Short + | + Uchar + / \ + Schar Char + +New +=== + +-----LongDoubleComplex--+ + LongDouble--+ | +-LongDoubleImag + | +---DoubleComplex---+ | + Double------+ | +----DoubleImag + | +-FloatComplex-+ | + Float---------+ +-------FloatImag + | + ULongLong + | + LongLong + | + ULong + / \ + UInt Long + \ / + Int + | + Ushort + | + Short + | + Uchar + / \ + Schar Char + \ / + Bool +*/ + +static const int costMatrix[ BasicType::NUMBER_OF_BASIC_TYPES ][ BasicType::NUMBER_OF_BASIC_TYPES ] = +{ +/* Src \ Dest: Bool Char SChar UChar Short UShort Int UInt Long ULong LLong ULLong Float Double LDbl FCplex DCplex LDCplex FImag DImag LDImag */ +/* Bool */ { 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10, 11, 12, 11, 12, 13, -1, -1, -1 }, +/* Char */ { -1, 0, -1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 10, 11, 12, -1, -1, -1 }, +/* SChar */ { -1, -1, 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 10, 11, 12, -1, -1, -1 }, +/* UChar */ { -1, -1, -1, 0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 9, 10, 11, -1, -1, -1 }, +/* Short */ { -1, -1, -1, -1, 0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 8, 9, 10, -1, -1, -1 }, +/* UShort */ { -1, -1, -1, -1, -1, 0, 1, 2, 2, 3, 4, 5, 6, 7, 8, 7, 8, 9, -1, -1, -1 }, +/* Int */ { -1, -1, -1, -1, -1, -1, 0, 1, 1, 2, 3, 4, 5, 6, 7, 6, 7, 8, -1, -1, -1 }, +/* UInt */ { -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, 2, 3, 4, 5, 6, 5, 6, 7, -1, -1, -1 }, +/* Long */ { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 5, 6, 7, -1, -1, -1 }, +/* ULong */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 4, 5, 6, -1, -1, -1 }, +/* LLong */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 3, 4, 5, -1, -1, -1 }, +/* ULLong */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 2, 3, 4, -1, -1, -1 }, +/* Float */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 1, 2, 3, -1, -1, -1 }, +/* Double */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, 1, 2, -1, -1, -1 }, +/* LDbl */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 1, -1, -1, -1 }, +/* FCplex */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, -1, -1, -1 }, +/* DCplex */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, -1, -1 }, +/* LDCplex */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1 }, +/* FImag */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 3, 0, 1, 2 }, +/* DImag */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, -1, 0, 1 }, +/* LDImag */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, 0 } +}; + +void +ConversionCost::visit(VoidType *voidType) +{ + cost = Cost::infinity; +} + +void +ConversionCost::visit(BasicType *basicType) +{ + if( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) { + int tableResult = costMatrix[ basicType->get_kind() ][ destAsBasic->get_kind() ]; + if( tableResult == -1 ) { + cost = Cost( 1, 0, 0 ); + } else { + cost = Cost( 0, 0, tableResult ); + } + } +} + +void +ConversionCost::visit(PointerType *pointerType) +{ + if( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) { + if( pointerType->get_base()->get_qualifiers() <= destAsPtr->get_base()->get_qualifiers() && typesCompatibleIgnoreQualifiers( pointerType->get_base(), destAsPtr->get_base(), indexer, env ) ) { + cost = Cost( 0, 0, 1 ); + } else { + int assignResult = ptrsAssignable( pointerType->get_base(), destAsPtr->get_base(), env ); + if( assignResult < 0 ) { + cost = Cost( 0, 0, 1 ); + } else if( assignResult > 0 ) { + cost = Cost( 1, 0, 0 ); + } + } + } +} + +void +ConversionCost::visit(ArrayType *arrayType) +{ +} + +void +ConversionCost::visit(FunctionType *functionType) +{ +} + +void +ConversionCost::visit(StructInstType *inst) +{ + if( StructInstType *destAsInst = dynamic_cast< StructInstType* >( dest ) ) { + if( inst->get_name() == destAsInst->get_name() ) { + cost = Cost::zero; + } + } +} + +void +ConversionCost::visit(UnionInstType *inst) +{ + if( StructInstType *destAsInst = dynamic_cast< StructInstType* >( dest ) ) { + if( inst->get_name() == destAsInst->get_name() ) { + cost = Cost::zero; + } + } +} + +void +ConversionCost::visit(EnumInstType *inst) +{ + static Type::Qualifiers q; + static BasicType integer( q, BasicType::SignedInt ); + integer.accept( *this ); + if( cost < Cost( 1, 0, 0 ) ) { + cost.incSafe(); + } +} + +void +ConversionCost::visit(ContextInstType *inst) +{ +} + +void +ConversionCost::visit(TypeInstType *inst) +{ + EqvClass eqvClass; + NamedTypeDecl *namedType; + if( env.lookup( inst->get_name(), eqvClass ) ) { + cost = conversionCost( eqvClass.type, dest, indexer, env ); + } else if( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) { + if( inst->get_name() == destAsInst->get_name() ) { + cost = Cost::zero; + } + } else if( ( namedType = indexer.lookupType( inst->get_name() ) ) ) { + TypeDecl *type = dynamic_cast< TypeDecl* >( namedType ); + // all typedefs should be gone by this point + assert( type ); + if( type->get_base() ) { + cost = conversionCost( type->get_base(), dest, indexer, env ) + Cost( 0, 0, 1 ); + } + } +} + +void +ConversionCost::visit(TupleType *tupleType) +{ + Cost c; + if( TupleType *destAsTuple = dynamic_cast< TupleType* >( dest ) ) { + std::list< Type* >::const_iterator srcIt = tupleType->get_types().begin(); + std::list< Type* >::const_iterator destIt = destAsTuple->get_types().begin(); + while( srcIt != tupleType->get_types().end() ) { + Cost newCost = conversionCost( *srcIt++, *destIt++, indexer, env ); + if( newCost == Cost::infinity ) { + return; + } + c += newCost; + } + if( destIt != destAsTuple->get_types().end() ) { + cost = Cost::infinity; + } else { + cost = c; + } + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/ConversionCost.h =================================================================== --- translator/ResolvExpr/ConversionCost.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/ConversionCost.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,46 @@ +/* + * This file is part of the Cforall project + * + * $Id: ConversionCost.h,v 1.6 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_CONVERSIONCOST_PROTECTED_H +#define RESOLVEXPR_CONVERSIONCOST_PROTECTED_H + +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" +#include "Cost.h" +#include "TypeEnvironment.h" + +namespace ResolvExpr { + +class ConversionCost : public Visitor +{ +public: + ConversionCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ); + + Cost get_cost() const { return cost; } + + virtual void visit(VoidType *voidType); + virtual void visit(BasicType *basicType); + virtual void visit(PointerType *pointerType); + virtual void visit(ArrayType *arrayType); + virtual void visit(FunctionType *functionType); + virtual void visit(StructInstType *aggregateUseType); + virtual void visit(UnionInstType *aggregateUseType); + virtual void visit(EnumInstType *aggregateUseType); + virtual void visit(ContextInstType *aggregateUseType); + virtual void visit(TypeInstType *aggregateUseType); + virtual void visit(TupleType *tupleType); + +protected: + Type *dest; + const SymTab::Indexer &indexer; + Cost cost; + const TypeEnvironment &env; +}; + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_CONVERSIONCOST_PROTECTED_H */ Index: translator/ResolvExpr/Cost.h =================================================================== --- translator/ResolvExpr/Cost.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Cost.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,140 @@ +/* + * This file is part of the Cforall project + * + * $Id: Cost.h,v 1.2 2003/01/27 14:46:59 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_COST_H +#define RESOLVEXPR_COST_H + +#include + +namespace ResolvExpr { + +class Cost +{ +public: + Cost(); + Cost( int unsafe, int poly, int safe ); + + void incUnsafe( int inc = 1 ); + void incPoly( int inc = 1 ); + void incSafe( int inc = 1 ); + + Cost operator+( const Cost &other ) const; + Cost operator-( const Cost &other ) const; + Cost &operator+=( const Cost &other ); + bool operator<( const Cost &other ) const; + bool operator==( const Cost &other ) const; + bool operator!=( const Cost &other ) const; + friend std::ostream &operator<<( std::ostream &os, const Cost &cost ); + + static const Cost zero; + static const Cost infinity; + +private: + int compare( const Cost &other ) const; + + int unsafe; + int poly; + int safe; +}; + +inline +Cost::Cost() + : unsafe( 0 ), poly( 0 ), safe( 0 ) +{ +} + +inline +Cost::Cost( int unsafe, int poly, int safe ) + : unsafe( unsafe ), poly( poly ), safe( safe ) +{ +} + +inline void +Cost::incUnsafe( int inc ) +{ + unsafe += inc; +} + +inline void +Cost::incPoly( int inc ) +{ + unsafe += inc; +} + +inline void +Cost::incSafe( int inc ) +{ + unsafe += inc; +} + +inline Cost +Cost::operator+( const Cost &other ) const +{ + return Cost( unsafe + other.unsafe, poly + other.poly, safe + other.safe ); +} + +inline Cost +Cost::operator-( const Cost &other ) const +{ + return Cost( unsafe - other.unsafe, poly - other.poly, safe - other.safe ); +} + +inline Cost & +Cost::operator+=( const Cost &other ) +{ + unsafe += other.unsafe; + poly += other.poly; + safe += other.safe; + return *this; +} + +inline bool +Cost::operator<( const Cost &other ) const +{ + if( *this == infinity ) return false; + if( other == infinity ) return true; + if( unsafe > other.unsafe ) { + return false; + } else if( unsafe < other.unsafe ) { + return true; + } else if( poly > other.poly ) { + return false; + } else if( poly < other.poly ) { + return true; + } else if( safe > other.safe ) { + return false; + } else if( safe < other.safe ) { + return true; + } else { + return false; + } +} + +inline bool +Cost::operator==( const Cost &other ) const +{ + return unsafe == other.unsafe + && poly == other.poly + && safe == other.safe; +} + +inline bool +Cost::operator!=( const Cost &other ) const +{ + return !( *this == other ); +} + +inline std::ostream & +operator<<( std::ostream &os, const Cost &cost ) +{ + os << "( " << cost.unsafe << ", " << cost.poly << ", " << cost.safe << " )"; + return os; +} + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_COST_H */ Index: translator/ResolvExpr/FindOpenVars.cc =================================================================== --- translator/ResolvExpr/FindOpenVars.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/FindOpenVars.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,105 @@ +/* + * This file is part of the Cforall project + * + * $Id: FindOpenVars.cc,v 1.4 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "FindOpenVars.h" +#include "SynTree/Type.h" +#include "SynTree/Visitor.h" + + +namespace ResolvExpr { + +class FindOpenVars : public Visitor +{ +public: + FindOpenVars( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); + +private: + virtual void visit(PointerType *pointerType); + virtual void visit(ArrayType *arrayType); + virtual void visit(FunctionType *functionType); + virtual void visit(TupleType *tupleType); + + void common_action( Type *type ); + + OpenVarSet &openVars, &closedVars; + AssertionSet &needAssertions, &haveAssertions; + bool nextIsOpen; +}; + +void +findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) +{ + FindOpenVars finder( openVars, closedVars, needAssertions, haveAssertions, firstIsOpen ); + type->accept( finder ); +} + +FindOpenVars::FindOpenVars( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) + : openVars( openVars ), closedVars( closedVars ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), nextIsOpen( firstIsOpen ) +{ +} + +void +FindOpenVars::common_action( Type *type ) +{ + if( nextIsOpen ) { + for( std::list< TypeDecl* >::const_iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) { + openVars[ (*i)->get_name() ] = (*i)->get_kind(); + for( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) { + needAssertions[ *assert ] = false; + } +/// cloneAll( (*i)->get_assertions(), needAssertions ); +/// needAssertions.insert( needAssertions.end(), (*i)->get_assertions().begin(), (*i)->get_assertions().end() ); + } + } else { + for( std::list< TypeDecl* >::const_iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) { + closedVars[ (*i)->get_name() ] = (*i)->get_kind(); + for( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) { + haveAssertions[ *assert ] = false; + } +/// cloneAll( (*i)->get_assertions(), haveAssertions ); +/// haveAssertions.insert( haveAssertions.end(), (*i)->get_assertions().begin(), (*i)->get_assertions().end() ); + } + } +/// std::cout << "type is "; +/// type->print( std::cout ); +/// std::cout << std::endl << "need is" << std::endl; +/// printAssertionSet( needAssertions, std::cout ); +/// std::cout << std::endl << "have is" << std::endl; +/// printAssertionSet( haveAssertions, std::cout ); +} + +void +FindOpenVars::visit(PointerType *pointerType) +{ + common_action( pointerType ); + Visitor::visit( pointerType ); +} + +void +FindOpenVars::visit(ArrayType *arrayType) +{ + common_action( arrayType ); + Visitor::visit( arrayType ); +} + +void +FindOpenVars::visit(FunctionType *functionType) +{ + common_action( functionType ); + nextIsOpen = !nextIsOpen; + Visitor::visit( functionType ); + nextIsOpen = !nextIsOpen; +} + +void +FindOpenVars::visit(TupleType *tupleType) +{ + common_action( tupleType ); + Visitor::visit( tupleType ); +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/FindOpenVars.h =================================================================== --- translator/ResolvExpr/FindOpenVars.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/FindOpenVars.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,20 @@ +/* + * This file is part of the Cforall project + * + * $Id: FindOpenVars.h,v 1.3 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_FINDOPENVARS_H +#define RESOLVEXPR_FINDOPENVARS_H + +#include "Unify.h" +#include "SynTree/SynTree.h" + +namespace ResolvExpr { + +void findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); + +} // namespace ResolvExpr + +#endif // #ifndef RESOLVEXPR_FINDOPENVARS_H Index: translator/ResolvExpr/Occurs.cc =================================================================== --- translator/ResolvExpr/Occurs.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Occurs.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,71 @@ +/* + * This file is part of the Cforall project + * + * $Id: Occurs.cc,v 1.2 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include +#include +#include +#include "SynTree/Type.h" +#include "SynTree/Visitor.h" +#include "TypeEnvironment.h" + + +namespace ResolvExpr { + +class Occurs : public Visitor +{ +public: + Occurs( std::string varName, const TypeEnvironment &env ); + + bool get_result() const { return result; } + + virtual void visit( TypeInstType *typeInst ); + +private: + bool result; + std::set< std::string > eqvVars; + const TypeEnvironment &env; +}; + +bool +occurs( Type *type, std::string varName, const TypeEnvironment &env ) +{ + Occurs occur( varName, env ); + type->accept( occur ); + return occur.get_result(); +} + +Occurs::Occurs( std::string varName, const TypeEnvironment &env ) + : result( false ), env( env ) +{ + EqvClass eqvClass; + if( env.lookup( varName, eqvClass ) ) { + eqvVars = eqvClass.vars; + } else { + eqvVars.insert( varName ); + } +} + +void +Occurs::visit( TypeInstType *typeInst ) +{ + EqvClass eqvClass; +/// std::cout << "searching for vars: "; +/// std::copy( eqvVars.begin(), eqvVars.end(), std::ostream_iterator< std::string >( std::cout, " " ) ); +/// std::cout << std::endl; + if( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) { + result = true; + } else if( env.lookup( typeInst->get_name(), eqvClass ) ) { + if( eqvClass.type ) { +/// std::cout << typeInst->get_name() << " is bound to"; +/// eqvClass.type->print( std::cout ); +/// std::cout << std::endl; + eqvClass.type->accept( *this ); + } + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/PolyCost.cc =================================================================== --- translator/ResolvExpr/PolyCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/PolyCost.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,62 @@ +/* + * This file is part of the Cforall project + * + * $Id: PolyCost.cc,v 1.2 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "SynTree/Type.h" +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" +#include "TypeEnvironment.h" + + +namespace ResolvExpr { + +class PolyCost : public Visitor +{ +public: + PolyCost( const TypeEnvironment &env, const SymTab::Indexer &indexer ); + + int get_result() const { return result; } + +private: + virtual void visit(TypeInstType *aggregateUseType); + + int result; + const TypeEnvironment &env; + const SymTab::Indexer &indexer; +}; + +int +polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) +{ + PolyCost coster( env, indexer ); + type->accept( coster ); + return coster.get_result(); +} + +PolyCost::PolyCost( const TypeEnvironment &env, const SymTab::Indexer &indexer ) + : result( 0 ), env( env ), indexer( indexer ) +{ +} + +void +PolyCost::visit(TypeInstType *typeInst) +{ + EqvClass eqvClass; + if( env.lookup( typeInst->get_name(), eqvClass ) ) { + if( eqvClass.type ) { + if( TypeInstType *otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass.type ) ) { + if( indexer.lookupType( otherTypeInst->get_name() ) ) { + result += 1; + } + } else { + result += 1; + } + } + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/PtrsAssignable.cc =================================================================== --- translator/ResolvExpr/PtrsAssignable.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/PtrsAssignable.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,161 @@ +/* + * This file is part of the Cforall project + * + * $Id: PtrsAssignable.cc,v 1.3 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SynTree/Visitor.h" + + +namespace ResolvExpr { + +class PtrsAssignable : public Visitor +{ +public: + PtrsAssignable( Type *dest, const TypeEnvironment &env ); + + int get_result() const { return result; } + + virtual void visit(VoidType *voidType); + virtual void visit(BasicType *basicType); + virtual void visit(PointerType *pointerType); + virtual void visit(ArrayType *arrayType); + virtual void visit(FunctionType *functionType); + virtual void visit(StructInstType *inst); + virtual void visit(UnionInstType *inst); + virtual void visit(EnumInstType *inst); + virtual void visit(ContextInstType *inst); + virtual void visit(TypeInstType *inst); + virtual void visit(TupleType *tupleType); + +private: + Type *dest; + int result; + const TypeEnvironment &env; +}; + +int +ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env ) +{ + if( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { + EqvClass eqvClass; + if( env.lookup( destAsTypeInst->get_name(), eqvClass ) ) { + return ptrsAssignable( src, eqvClass.type, env ); + } + } + if( dynamic_cast< VoidType* >( dest ) ) { + return 1; + } else { + PtrsAssignable ptrs( dest, env ); + src->accept( ptrs ); + return ptrs.get_result(); + } +} + +PtrsAssignable::PtrsAssignable( Type *dest, const TypeEnvironment &env ) + : dest( dest ), result( 0 ), env( env ) +{ +} + +void +PtrsAssignable::visit(VoidType *voidType) +{ + if( dynamic_cast< FunctionType* >( dest ) ) { + result = 0; + } else { + result = -1; + } +} + +void +PtrsAssignable::visit(BasicType *basicType) +{ +} + +void +PtrsAssignable::visit(PointerType *pointerType) +{ +} + +void +PtrsAssignable::visit(ArrayType *arrayType) +{ +} + +void +PtrsAssignable::visit(FunctionType *functionType) +{ + result = -1; +} + +void +PtrsAssignable::visit(StructInstType *inst) +{ + // I don't think we should be doing anything here, but I'm willing to admit that I might be wrong +} + +void +PtrsAssignable::visit(UnionInstType *inst) +{ + // I don't think we should be doing anything here, but I'm willing to admit that I might be wrong +} + +void +PtrsAssignable::visit(EnumInstType *inst) +{ + if( dynamic_cast< EnumInstType* >( inst ) ) { + result = 1; + } else if( BasicType *bt = dynamic_cast< BasicType* >( inst ) ) { + result = bt->get_kind() == BasicType::SignedInt; + } +} + +void +PtrsAssignable::visit(ContextInstType *inst) +{ + // I definitely don't think we should be doing anything here +} + +void +PtrsAssignable::visit(TypeInstType *inst) +{ + EqvClass eqvClass; + if( env.lookup( inst->get_name(), eqvClass ) ) { + result = ptrsAssignable( eqvClass.type, dest, env ); + } else { + result = 0; + } +} + +void +PtrsAssignable::visit(TupleType *tupleType) +{ +/// // This code doesn't belong here, but it might be useful somewhere else +/// if( TupleType *destAsTuple = dynamic_cast< TupleType* >( dest ) ) { +/// int ret = 0; +/// std::list< Type* >::const_iterator srcIt = tupleType->get_types().begin(); +/// std::list< Type* >::const_iterator destIt = destAsTuple->get_types().begin(); +/// while( srcIt != tupleType->get_types().end() && destIt != destAsTuple->get_types().end() ) { +/// int assignResult = ptrsAssignable( *srcIt++, *destIt++ ); +/// if( assignResult == 0 ) { +/// result = assignResult; +/// return; +/// } else if ( assignResult < 0 ) { +/// ret = -1; +/// } else if ( ret > 0 ) { +/// ret += assignResult; +/// } +/// } +/// if( srcIt == tupleType->get_types().end() && destIt == destAsTuple->get_types().end() ) { +/// result = ret; +/// } else { +/// result = 0; +/// } +/// } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/PtrsCastable.cc =================================================================== --- translator/ResolvExpr/PtrsCastable.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/PtrsCastable.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,164 @@ +/* + * This file is part of the Cforall project + * + * $Id: PtrsCastable.cc,v 1.5 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "typeops.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SynTree/Visitor.h" +#include "SymTab/Indexer.h" + + +namespace ResolvExpr { + +class PtrsCastable : public Visitor +{ +public: + PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ); + + int get_result() const { return result; } + + virtual void visit(VoidType *voidType); + virtual void visit(BasicType *basicType); + virtual void visit(PointerType *pointerType); + virtual void visit(ArrayType *arrayType); + virtual void visit(FunctionType *functionType); + virtual void visit(StructInstType *inst); + virtual void visit(UnionInstType *inst); + virtual void visit(EnumInstType *inst); + virtual void visit(ContextInstType *inst); + virtual void visit(TypeInstType *inst); + virtual void visit(TupleType *tupleType); + +private: + Type *dest; + int result; + const TypeEnvironment &env; + const SymTab::Indexer &indexer; +}; + +int +objectCast( Type *src, const TypeEnvironment &env, const SymTab::Indexer &indexer ) +{ + if( dynamic_cast< FunctionType* >( src ) ) { + return -1; + } else if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( src ) ) { + EqvClass eqvClass; + if( NamedTypeDecl *ntDecl = indexer.lookupType( typeInst->get_name() ) ) { + if( TypeDecl *tyDecl = dynamic_cast< TypeDecl* >( ntDecl ) ) { + if( tyDecl->get_kind() == TypeDecl::Ftype ) { + return -1; + } + } + } else if( env.lookup( typeInst->get_name(), eqvClass ) ) { + if( eqvClass.kind == TypeDecl::Ftype ) { + return -1; + } + } + } + return 1; +} + +int +ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) +{ + if( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { + EqvClass eqvClass; + if( env.lookup( destAsTypeInst->get_name(), eqvClass ) ) { + return ptrsAssignable( src, eqvClass.type, env ); + } + } + if( dynamic_cast< VoidType* >( dest ) ) { + return objectCast( src, env, indexer ); + } else { + PtrsCastable ptrs( dest, env, indexer ); + src->accept( ptrs ); + return ptrs.get_result(); + } +} + +PtrsCastable::PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) + : dest( dest ), result( 0 ), env( env ), indexer( indexer ) +{ +} + +void +PtrsCastable::visit(VoidType *voidType) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(BasicType *basicType) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(PointerType *pointerType) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(ArrayType *arrayType) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(FunctionType *functionType) +{ + result = -1; +} + +void +PtrsCastable::visit(StructInstType *inst) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(UnionInstType *inst) +{ + result = objectCast( dest, env, indexer ); +} + +void +PtrsCastable::visit(EnumInstType *inst) +{ + if( dynamic_cast< EnumInstType* >( inst ) ) { + result = 1; + } else if( BasicType *bt = dynamic_cast< BasicType* >( inst ) ) { + if( bt->get_kind() == BasicType::SignedInt ) { + result = 0; + } else { + result = 1; + } + } else { + result = objectCast( dest, env, indexer ); + } +} + +void +PtrsCastable::visit(ContextInstType *inst) +{ + // I definitely don't think we should be doing anything here +} + +void +PtrsCastable::visit(TypeInstType *inst) +{ + result = objectCast( inst, env, indexer ) && objectCast( dest, env, indexer ) ? 1 : -1; +} + +void +PtrsCastable::visit(TupleType *tupleType) +{ + result = objectCast( dest, env, indexer ); +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/RenameVars.cc =================================================================== --- translator/ResolvExpr/RenameVars.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/RenameVars.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,162 @@ +/* + * This file is part of the Cforall project + * + * $Id: RenameVars.cc,v 1.4 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include + +#include "RenameVars.h" +#include "SynTree/Visitor.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SynTree/Expression.h" + +namespace ResolvExpr { + +RenameVars global_renamer; + +RenameVars::RenameVars() + : level( 0 ) +{ + mapStack.push_front( std::map< std::string, std::string >() ); +} + +void +RenameVars::reset() +{ + level = 0; +} + +void +RenameVars::visit( VoidType *voidType ) +{ + typeBefore( voidType ); + typeAfter( voidType ); +} + +void +RenameVars::visit( BasicType *basicType ) +{ + typeBefore( basicType ); + typeAfter( basicType ); +} + +void +RenameVars::visit( PointerType *pointerType ) +{ + typeBefore( pointerType ); +/// std::cout << "do pointer" << std::endl; + maybeAccept( pointerType->get_base(), *this ); +/// std::cout << "done pointer" << std::endl; + typeAfter( pointerType ); +} + +void +RenameVars::visit( ArrayType *arrayType ) +{ + typeBefore( arrayType ); + maybeAccept( arrayType->get_dimension(), *this ); + maybeAccept( arrayType->get_base(), *this ); + typeAfter( arrayType ); +} + +void +RenameVars::visit( FunctionType *functionType ) +{ + typeBefore( functionType ); +/// std::cout << "return vals" << std::endl; + acceptAll( functionType->get_returnVals(), *this ); +/// std::cout << functionType->get_parameters().size() << " parameters" << std::endl; + acceptAll( functionType->get_parameters(), *this ); +/// std::cout << "done function" << std::endl; + typeAfter( functionType ); +} + +void +RenameVars::visit( StructInstType *aggregateUseType ) +{ + typeBefore( aggregateUseType ); + acceptAll( aggregateUseType->get_parameters(), *this ); + typeAfter( aggregateUseType ); +} + +void +RenameVars::visit( UnionInstType *aggregateUseType ) +{ + typeBefore( aggregateUseType ); + acceptAll( aggregateUseType->get_parameters(), *this ); + typeAfter( aggregateUseType ); +} + +void +RenameVars::visit( EnumInstType *aggregateUseType ) +{ + typeBefore( aggregateUseType ); + acceptAll( aggregateUseType->get_parameters(), *this ); + typeAfter( aggregateUseType ); +} + +void +RenameVars::visit( ContextInstType *aggregateUseType ) +{ + typeBefore( aggregateUseType ); + acceptAll( aggregateUseType->get_parameters(), *this ); + acceptAll( aggregateUseType->get_members(), *this ); + typeAfter( aggregateUseType ); +} + +void +RenameVars::visit( TypeInstType *instType ) +{ + typeBefore( instType ); +/// std::cout << "instance of type " << instType->get_name() << std::endl; + std::map< std::string, std::string >::const_iterator i = mapStack.front().find( instType->get_name() ); + if( i != mapStack.front().end() ) { +/// std::cout << "found name " << i->second << std::endl; + instType->set_name( i->second ); + } else { +/// std::cout << "no name found" << std::endl; + } + acceptAll( instType->get_parameters(), *this ); + typeAfter( instType ); +} + +void +RenameVars::visit( TupleType *tupleType ) +{ + typeBefore( tupleType ); + acceptAll( tupleType->get_types(), *this ); + typeAfter( tupleType ); +} + +void +RenameVars::typeBefore( Type *type ) +{ + if( !type->get_forall().empty() ) { +/// std::cout << "type with forall: "; +/// type->print( std::cout ); +/// std::cout << std::endl; + mapStack.push_front( mapStack.front() ); + for( std::list< TypeDecl* >::iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) { + std::ostrstream output; + output << "_" << level << "_" << (*i)->get_name(); + std::string newname( output.str(), output.pcount() ); + mapStack.front()[ (*i)->get_name() ] = newname; + (*i)->set_name( newname ); + level++; + acceptAll( (*i)->get_assertions(), *this ); + } + } +} + +void +RenameVars::typeAfter( Type *type ) +{ + if( !type->get_forall().empty() ) { + mapStack.pop_front(); + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/RenameVars.h =================================================================== --- translator/ResolvExpr/RenameVars.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/RenameVars.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,49 @@ +/* + * This file is part of the Cforall project + * + * $Id: RenameVars.h,v 1.2 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_RENAMEVARS_H +#define RESOLVEXPR_RENAMEVARS_H + +#include +#include +#include + +#include "SynTree/SynTree.h" +#include "SynTree/Visitor.h" + +namespace ResolvExpr { + +class RenameVars : public Visitor +{ +public: + RenameVars(); + void reset(); + +private: + virtual void visit( VoidType *basicType ); + virtual void visit( BasicType *basicType ); + virtual void visit( PointerType *pointerType ); + virtual void visit( ArrayType *arrayType ); + virtual void visit( FunctionType *functionType ); + virtual void visit( StructInstType *aggregateUseType ); + virtual void visit( UnionInstType *aggregateUseType ); + virtual void visit( EnumInstType *aggregateUseType ); + virtual void visit( ContextInstType *aggregateUseType ); + virtual void visit( TypeInstType *aggregateUseType ); + virtual void visit( TupleType *tupleType ); + + void typeBefore( Type *type ); + void typeAfter( Type *type ); + int level; + std::list< std::map< std::string, std::string > > mapStack; +}; + +extern RenameVars global_renamer; + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_RENAMEVARS_H */ Index: translator/ResolvExpr/ResolveTypeof.cc =================================================================== --- translator/ResolvExpr/ResolveTypeof.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/ResolveTypeof.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,71 @@ +/* + * This file is part of the Cforall project + * + * $Id: ResolveTypeof.cc,v 1.2 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "ResolveTypeof.h" +#include "Alternative.h" +#include "AlternativeFinder.h" +#include "Resolver.h" +#include "TypeEnvironment.h" +#include "SynTree/Expression.h" +#include "SynTree/Type.h" + +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 : public Mutator +{ +public: + ResolveTypeof( const SymTab::Indexer &indexer ) : indexer( indexer ) {} + Type *mutate( TypeofType *typeofType ); + +private: + const SymTab::Indexer &indexer; +}; + +Type * +resolveTypeof( Type *type, const SymTab::Indexer &indexer ) +{ + ResolveTypeof mutator( indexer ); + return type->acceptMutator( mutator ); +} + +Type * +ResolveTypeof::mutate( TypeofType *typeofType ) +{ +/// std::cout << "resolving typeof: "; +/// typeofType->print( std::cout ); +/// std::cout << std::endl; + if( typeofType->get_expr() ) { + Expression *newExpr = resolveInVoidContext( typeofType->get_expr(), indexer ); + assert( newExpr->get_results().size() > 0 ); + Type *newType; + if( newExpr->get_results().size() > 1 ) { + TupleType *tupleType = new TupleType( Type::Qualifiers() ); + cloneAll( newExpr->get_results(), tupleType->get_types() ); + newType = tupleType; + } else { + newType = newExpr->get_results().front()->clone(); + } + delete typeofType; + return newType; + } + return typeofType; +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/ResolveTypeof.h =================================================================== --- translator/ResolvExpr/ResolveTypeof.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/ResolveTypeof.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,20 @@ +/* + * This file is part of the Cforall project + * + * $Id: ResolveTypeof.h,v 1.2 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_RESOLVETYPEOF_H +#define RESOLVEXPR_RESOLVETYPEOF_H + +#include "SynTree/SynTree.h" +#include "SymTab/Indexer.h" + +namespace ResolvExpr { + +Type *resolveTypeof( Type*, const SymTab::Indexer &indexer ); + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_RESOLVETYPEOF_H */ Index: translator/ResolvExpr/Resolver.cc =================================================================== --- translator/ResolvExpr/Resolver.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Resolver.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,290 @@ +/* + * This file is part of the Cforall project + * + * $Id: Resolver.cc,v 1.19 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include "Resolver.h" +#include "AlternativeFinder.h" +#include "Alternative.h" +#include "RenameVars.h" +#include "ResolveTypeof.h" +#include "SynTree/Statement.h" +#include "SynTree/Type.h" +#include "SynTree/Expression.h" +#include "SynTree/Initializer.h" +#include "SymTab/Indexer.h" +#include "utility.h" + +namespace ResolvExpr { + +class Resolver : public SymTab::Indexer +{ +public: + Resolver() : SymTab::Indexer( false ), switchType( 0 ) {} + + virtual void visit( FunctionDecl *functionDecl ); + virtual void visit( ObjectDecl *functionDecl ); + virtual void visit( TypeDecl *typeDecl ); + + virtual void visit( ExprStmt *exprStmt ); + virtual void visit( IfStmt *ifStmt ); + virtual void visit( WhileStmt *whileStmt ); + virtual void visit( ForStmt *forStmt ); + virtual void visit( SwitchStmt *switchStmt ); + virtual void visit( ChooseStmt *switchStmt ); + virtual void visit( CaseStmt *caseStmt ); + virtual void visit( ReturnStmt *returnStmt ); + + virtual void visit( SingleInit *singleInit ); + +private: + std::list< Type* > functionReturn; + Type* initContext; + Type *switchType; +}; + +void +resolve( std::list< Declaration* > translationUnit ) +{ + Resolver resolver; + acceptAll( translationUnit, resolver ); +/// for( std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) { +/// (*i)->print( std::cerr ); +/// (*i)->accept( resolver ); +/// } +} + +Expression * +resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer ) +{ + TypeEnvironment env; + return resolveInVoidContext( expr, indexer, env ); +} + +namespace { + + void + finishExpr( Expression *expr, const TypeEnvironment &env ) + { + expr->set_env( new TypeSubstitution ); + env.makeSubstitution( *expr->get_env() ); + } + + Expression* + findVoidExpression( Expression *untyped, const SymTab::Indexer &indexer ) + { + global_renamer.reset(); + TypeEnvironment env; + Expression *newExpr = resolveInVoidContext( untyped, indexer, env ); + finishExpr( newExpr, env ); + return newExpr; + } + + Expression* + findSingleExpression( Expression *untyped, const SymTab::Indexer &indexer ) + { + TypeEnvironment env; + AlternativeFinder finder( indexer, env ); + finder.find( untyped ); +/// if( finder.get_alternatives().size() != 1 ) { +/// std::cout << "untyped expr is "; +/// untyped->print( std::cout ); +/// std::cout << std::endl << "alternatives are:"; +/// for( std::list< Alternative >::const_iterator i = finder.get_alternatives().begin(); i != finder.get_alternatives().end(); ++i ) { +/// i->print( std::cout ); +/// } +/// } + assert( finder.get_alternatives().size() == 1 ); + Alternative &choice = finder.get_alternatives().front(); + Expression *newExpr = choice.expr->clone(); + finishExpr( newExpr, choice.env ); + return newExpr; + } + + bool + isIntegralType( Type *type ) + { + if( dynamic_cast< EnumInstType* >( type ) ) { + return true; + } else if( BasicType *bt = dynamic_cast< BasicType* >( type ) ) { + return bt->isInteger(); + } else { + return true; + } + } + + Expression* + findIntegralExpression( Expression *untyped, const SymTab::Indexer &indexer ) + { + TypeEnvironment env; + AlternativeFinder finder( indexer, env ); + finder.find( untyped ); +/// if( finder.get_alternatives().size() != 1 ) { +/// std::cout << "untyped expr is "; +/// untyped->print( std::cout ); +/// std::cout << std::endl << "alternatives are:"; +/// for( std::list< Alternative >::const_iterator i = finder.get_alternatives().begin(); i != finder.get_alternatives().end(); ++i ) { +/// i->print( std::cout ); +/// } +/// } + Expression *newExpr = 0; + const TypeEnvironment *newEnv = 0; + for( AltList::const_iterator i = finder.get_alternatives().begin(); i != finder.get_alternatives().end(); ++i ) { + if( i->expr->get_results().size() == 1 && isIntegralType( i->expr->get_results().front() ) ) { + if( newExpr ) { + throw SemanticError( "Too many interpretations for switch control expression", untyped ); + } else { + newExpr = i->expr->clone(); + newEnv = &i->env; + } + } + } + if( !newExpr ) { + throw SemanticError( "Too many interpretations for switch control expression", untyped ); + } + finishExpr( newExpr, *newEnv ); + return newExpr; + } + +} + +void +Resolver::visit( ObjectDecl *objectDecl ) +{ + Type *new_type = resolveTypeof( objectDecl->get_type(), *this ); + objectDecl->set_type( new_type ); + initContext = new_type; + SymTab::Indexer::visit( objectDecl ); +} + +void +Resolver::visit( TypeDecl *typeDecl ) +{ + if( typeDecl->get_base() ) { + Type *new_type = resolveTypeof( typeDecl->get_base(), *this ); + typeDecl->set_base( new_type ); + } + SymTab::Indexer::visit( typeDecl ); +} + +void +Resolver::visit( FunctionDecl *functionDecl ) +{ +/// std::cout << "resolver visiting functiondecl "; +/// functionDecl->print( std::cout ); +/// std::cout << std::endl; + Type *new_type = resolveTypeof( functionDecl->get_type(), *this ); + functionDecl->set_type( new_type ); + std::list< Type* > oldFunctionReturn = functionReturn; + functionReturn.clear(); + for( std::list< DeclarationWithType* >::const_iterator i = functionDecl->get_functionType()->get_returnVals().begin(); i != functionDecl->get_functionType()->get_returnVals().end(); ++i ) { + functionReturn.push_back( (*i)->get_type() ); + } + SymTab::Indexer::visit( functionDecl ); + functionReturn = oldFunctionReturn; +} + +void +Resolver::visit( ExprStmt *exprStmt ) +{ + if( exprStmt->get_expr() ) { + Expression *newExpr = findVoidExpression( exprStmt->get_expr(), *this ); + delete exprStmt->get_expr(); + exprStmt->set_expr( newExpr ); + } +} + +void +Resolver::visit( IfStmt *ifStmt ) +{ + Expression *newExpr = findSingleExpression( ifStmt->get_condition(), *this ); + delete ifStmt->get_condition(); + ifStmt->set_condition( newExpr ); + Visitor::visit( ifStmt ); +} + +void +Resolver::visit( WhileStmt *whileStmt ) +{ + Expression *newExpr = findSingleExpression( whileStmt->get_condition(), *this ); + delete whileStmt->get_condition(); + whileStmt->set_condition( newExpr ); + Visitor::visit( whileStmt ); +} + +void +Resolver::visit( ForStmt *forStmt ) +{ + Expression *newExpr; + if( forStmt->get_condition() ) { + newExpr = findSingleExpression( forStmt->get_condition(), *this ); + delete forStmt->get_condition(); + forStmt->set_condition( newExpr ); + } + + if( forStmt->get_increment() ) { + newExpr = findVoidExpression( forStmt->get_increment(), *this ); + delete forStmt->get_increment(); + forStmt->set_increment( newExpr ); + } + + Visitor::visit( forStmt ); +} + +template< typename SwitchClass > +void +handleSwitchStmt( SwitchClass *switchStmt, SymTab::Indexer &visitor ) +{ + Expression *newExpr; + newExpr = findIntegralExpression( switchStmt->get_condition(), visitor ); + delete switchStmt->get_condition(); + switchStmt->set_condition( newExpr ); + + visitor.Visitor::visit( switchStmt ); +} + +void +Resolver::visit( SwitchStmt *switchStmt ) +{ + handleSwitchStmt( switchStmt, *this ); +} + +void +Resolver::visit( ChooseStmt *switchStmt ) +{ + handleSwitchStmt( switchStmt, *this ); +} + +void +Resolver::visit( CaseStmt *caseStmt ) +{ + Visitor::visit( caseStmt ); +} + +void +Resolver::visit( ReturnStmt *returnStmt ) +{ + if( returnStmt->get_expr() ) { + CastExpr *castExpr = new CastExpr( returnStmt->get_expr() ); + cloneAll( functionReturn, castExpr->get_results() ); + Expression *newExpr = findSingleExpression( castExpr, *this ); + delete castExpr; + returnStmt->set_expr( newExpr ); + } +} + +void +Resolver::visit( SingleInit *singleInit ) +{ + if( singleInit->get_value() ) { + CastExpr *castExpr = new CastExpr( singleInit->get_value(), initContext->clone() ); + Expression *newExpr = findSingleExpression( castExpr, *this ); + delete castExpr; + singleInit->set_value( newExpr ); + } + singleInit->get_value()->accept( *this ); +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/Resolver.h =================================================================== --- translator/ResolvExpr/Resolver.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Resolver.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,21 @@ +/* + * This file is part of the Cforall project + * + * $Id: Resolver.h,v 1.3 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_RESOLVER_H +#define RESOLVEXPR_RESOLVER_H + +#include "SynTree/SynTree.h" +#include "SymTab/Indexer.h" + +namespace ResolvExpr { + +void resolve( std::list< Declaration* > translationUnit ); +Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer ); + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_RESOLVER_H */ Index: translator/ResolvExpr/TypeEnvironment.cc =================================================================== --- translator/ResolvExpr/TypeEnvironment.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/TypeEnvironment.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,223 @@ +/* + * This file is part of the Cforall project + * + * $Id: TypeEnvironment.cc,v 1.7 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include +#include + +#include "TypeEnvironment.h" +#include "SynTree/Type.h" +#include "SynTree/TypeSubstitution.h" +#include "utility.h" + +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 ) { + os << "(used)"; + } else { + os << "(not used)"; + } + } +} + +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 << ") "; + } +} + +void +EqvClass::initialize( const EqvClass &src, EqvClass &dest ) +{ + dest.vars = src.vars; + dest.type = maybeClone( src.type ); + dest.allowWidening = src.allowWidening; + dest.kind = src.kind; +} + +EqvClass::EqvClass() : type( 0 ), allowWidening( true ) +{ +} + +EqvClass::EqvClass( const EqvClass &other ) +{ + initialize( other, *this ); +} + +EqvClass & +EqvClass::operator=( const EqvClass &other ) +{ + if( this == &other ) return *this; + delete type; + initialize( other, *this ); + return *this; +} + +EqvClass::~EqvClass() +{ + delete type; +} + +void +EqvClass::print( std::ostream &os, int indent ) const +{ + os << std::string( indent, ' ' ) << "( "; + std::copy( vars.begin(), vars.end(), std::ostream_iterator< std::string >( os, " " ) ); + os << ")"; + if( type ) { + os << " -> "; + type->print( os, indent ); + } + if( !allowWidening ) { + os << " (no widening)"; + } + os << std::endl; +} + +bool +TypeEnvironment::lookup( const std::string &var, EqvClass &eqvClass ) const +{ + for( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) { + if( i->vars.find( var ) != i->vars.end() ) { +/// std::cout << var << " is in class "; +/// i->print( std::cout ); + eqvClass = *i; + return true; + } +/// std::cout << var << " is not in class "; +/// i->print( std::cout ); + } + return false; +} + +void +TypeEnvironment::add( const EqvClass &eqvClass ) +{ + std::list< EqvClass >::iterator i = env.begin(); + while( i != env.end() ) { + std::list< EqvClass >::iterator next = i; + next++; + std::set< std::string > 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; + } + env.insert( env.end(), eqvClass ); +} + +void +TypeEnvironment::add( const std::list< TypeDecl* > &tyDecls ) +{ + for( std::list< TypeDecl* >::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) { + EqvClass newClass; + newClass.vars.insert( (*i)->get_name() ); + newClass.kind = (*i)->get_kind(); + env.push_back( newClass ); + } +} + +void +TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const +{ + for( std::list< EqvClass >::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 ) { +/// std::cout << "adding " << *theVar; + if( theClass->type ) { +/// std::cout << " bound to "; +/// theClass->type->print( std::cout ); +/// std::cout << std::endl; + sub.add( *theVar, theClass->type ); + } else if( theVar != theClass->vars.begin() ) { + TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->kind == TypeDecl::Ftype ); +/// std::cout << " bound to variable " << *theClass->vars.begin() << std::endl; + sub.add( *theVar, newTypeInst ); + delete newTypeInst; + } + } + } +/// std::cerr << "input env is:" << std::endl; +/// print( std::cerr, 8 ); +/// std::cerr << "sub is:" << std::endl; +/// sub.print( std::cerr, 8 ); + sub.normalize(); +} + +void +TypeEnvironment::print( std::ostream &os, int indent ) const +{ + for( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) { + i->print( os, indent ); + } +} + +std::list< EqvClass >::iterator +TypeEnvironment::internal_lookup( const std::string &var ) +{ + for( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) { + if( i->vars.find( var ) == i->vars.end() ) { + return i; + } + } + return env.end(); +} + +void +TypeEnvironment::simpleCombine( const TypeEnvironment &second ) +{ + env.insert( env.end(), second.env.begin(), second.env.end() ); +} + +void +TypeEnvironment::combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ) +{ + TypeEnvironment secondCopy( second ); + for( std::list< EqvClass >::iterator firstClass = env.begin(); firstClass != env.end(); ++firstClass ) { + EqvClass &newClass = *firstClass; + std::set< std::string > newVars; + for( std::set< std::string >::const_iterator var = firstClass->vars.begin(); var != firstClass->vars.end(); ++var ) { + std::list< EqvClass >::iterator secondClass = secondCopy.internal_lookup( *var ); + if( secondClass != secondCopy.env.end() ) { + newVars.insert( secondClass->vars.begin(), secondClass->vars.end() ); + if( secondClass->type ) { + if( newClass.type ) { + Type *newType = combineFunc( newClass.type, secondClass->type ); + delete newClass.type; + newClass.type = newType; + newClass.allowWidening = newClass.allowWidening && secondClass->allowWidening; + } else { + newClass.type = secondClass->type->clone(); + newClass.allowWidening = secondClass->allowWidening; + } + } + secondCopy.env.erase( secondClass ); + } + } + newClass.vars.insert( newVars.begin(), newVars.end() ); + } + for( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) { + env.push_back( *secondClass ); + } +} + +void +TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const +{ + for( std::list< EqvClass >::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->kind; + } + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/TypeEnvironment.h =================================================================== --- translator/ResolvExpr/TypeEnvironment.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/TypeEnvironment.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,92 @@ +/* + * This file is part of the Cforall project + * + * $Id: TypeEnvironment.h,v 1.8 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef RESOLVEXPR_TYPEENVIRONMENT_H +#define RESOLVEXPR_TYPEENVIRONMENT_H + +#include +#include +#include +#include + +#include "SynTree/SynTree.h" +#include "SynTree/Type.h" +#include "SynTree/TypeSubstitution.h" +#include "SynTree/Declaration.h" + +namespace ResolvExpr { + +typedef std::map< DeclarationWithType*, bool > AssertionSet; +typedef std::map< std::string, TypeDecl::Kind > OpenVarSet; + +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::Kind kind; + + void initialize( const EqvClass &src, EqvClass &dest ); + EqvClass(); + EqvClass( const EqvClass &other ); + EqvClass &operator=( const EqvClass &other ); + ~EqvClass(); + void print( std::ostream &os, int indent = 0 ) const; +}; + +class TypeEnvironment +{ +public: + bool lookup( const std::string &var, EqvClass &eqvClass ) const; + void add( const EqvClass &eqvClass ); + void add( const std::list< TypeDecl* > &tyDecls ); + 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, int indent = 0 ) const; + void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ); + void simpleCombine( const TypeEnvironment &second ); + void extractOpenVars( OpenVarSet &openVars ) const; + TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } + + typedef std::list< EqvClass >::iterator iterator; + iterator begin() { return env.begin(); } + iterator end() { return env.end(); } + typedef std::list< EqvClass >::const_iterator const_iterator; + const_iterator begin() const { return env.begin(); } + const_iterator end() const { return env.end(); } +private: + std::list< EqvClass > env; + + std::list< EqvClass >::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 ); +} + +} // namespace ResolvExpr + +#endif /* #ifndef RESOLVEXPR_TYPEENVIRONMENT_H */ Index: translator/ResolvExpr/Unify.cc =================================================================== --- translator/ResolvExpr/Unify.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Unify.cc (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,568 @@ +/* + * This file is part of the Cforall project + * + * $Id: Unify.cc,v 1.14 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#include +#include + +#include "Unify.h" +#include "TypeEnvironment.h" +#include "typeops.h" +#include "FindOpenVars.h" +#include "SynTree/Visitor.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SymTab/Indexer.h" +#include "utility.h" + + +//#define DEBUG + +namespace ResolvExpr { + +struct WidenMode +{ + WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {} + WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; } + WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; } + WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; } + WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; } + operator bool() { return widenFirst && widenSecond; } + + bool widenFirst : 1, widenSecond : 1; +}; + +class Unify : public Visitor +{ +public: + Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + + bool get_result() const { return result; } + +private: + virtual void visit(VoidType *voidType); + virtual void visit(BasicType *basicType); + virtual void visit(PointerType *pointerType); + virtual void visit(ArrayType *arrayType); + virtual void visit(FunctionType *functionType); + virtual void visit(StructInstType *aggregateUseType); + virtual void visit(UnionInstType *aggregateUseType); + virtual void visit(EnumInstType *aggregateUseType); + virtual void visit(ContextInstType *aggregateUseType); + virtual void visit(TypeInstType *aggregateUseType); + virtual void visit(TupleType *tupleType); + + template< typename RefType > void handleRefType( RefType *inst, Type *other ); + + bool result; + Type *type2; // inherited + TypeEnvironment &env; + AssertionSet &needAssertions; + AssertionSet &haveAssertions; + const OpenVarSet &openVars; + WidenMode widenMode; + Type *commonType; + const SymTab::Indexer &indexer; +}; + +bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ); +bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + +bool +typesCompatible( Type *first, 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 ); + bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); + delete newFirst; + delete newSecond; + return result; +} + +bool +typesCompatibleIgnoreQualifiers( Type *first, 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(); +/// std::cout << "first is "; +/// first->print( std::cout ); +/// std::cout << std::endl << "second is "; +/// second->print( std::cout ); +/// std::cout << std::endl << "newFirst is "; +/// newFirst->print( std::cout ); +/// std::cout << std::endl << "newSecond is "; +/// newSecond->print( std::cout ); +/// std::cout << std::endl; + bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); + delete newFirst; + delete newSecond; + return result; +} + +bool +isFtype( Type *type, const SymTab::Indexer &indexer ) +{ + if( dynamic_cast< FunctionType* >( type ) ) { + return true; + } else if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { + return typeInst->get_isFtype(); + } + return false; +} + +bool +tyVarCompatible( TypeDecl::Kind kind, Type *type, const SymTab::Indexer &indexer ) +{ + switch( kind ) { + case TypeDecl::Any: + case TypeDecl::Dtype: + return !isFtype( type, indexer ); + + case TypeDecl::Ftype: + return isFtype( type, indexer ); + } + assert( false ); + return false; +} + +bool +bindVar( TypeInstType *typeInst, Type *other, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) +{ + OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() ); + assert( tyvar != openVars.end() ); + if( !tyVarCompatible( tyvar->second, other, indexer ) ) { + return false; + } + if( occurs( other, typeInst->get_name(), env ) ) { + return false; + } + EqvClass curClass; + if( env.lookup( typeInst->get_name(), curClass ) ) { + if( curClass.type ) { + Type *common = 0; + std::auto_ptr< Type > newType( curClass.type->clone() ); + if( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) { + if( common ) { + common->get_qualifiers() = Type::Qualifiers(); + delete curClass.type; + curClass.type = common; + env.add( curClass ); + } + return true; + } else { + return false; + } + } else { + curClass.type = other->clone(); + curClass.type->get_qualifiers() = Type::Qualifiers(); + curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + env.add( curClass ); + } + } else { + EqvClass newClass; + newClass.vars.insert( typeInst->get_name() ); + newClass.type = other->clone(); + newClass.type->get_qualifiers() = Type::Qualifiers(); + newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + newClass.kind = kind; + env.add( newClass ); + } + return true; +} + +bool +bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) +{ + bool result = true; + EqvClass class1, class2; + bool hasClass1 = false, hasClass2 = false; + bool widen1 = false, widen2 = false; + Type *type1 = 0, *type2 = 0; + + if( env.lookup( var1->get_name(), class1 ) ) { + hasClass1 = true; + if( class1.type ) { + if( occurs( class1.type, var2->get_name(), env ) ) { + return false; + } + type1 = class1.type->clone(); + } + widen1 = widenMode.widenFirst && class1.allowWidening; + } + if( env.lookup( var2->get_name(), class2 ) ) { + hasClass2 = true; + if( class2.type ) { + if( occurs( class2.type, var1->get_name(), env ) ) { + return false; + } + type2 = class2.type->clone(); + } + widen2 = widenMode.widenSecond && class2.allowWidening; + } + + if( type1 && type2 ) { +// std::cout << "has type1 && type2" << std::endl; + WidenMode newWidenMode ( widen1, widen2 ); + Type *common = 0; + if( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) { + class1.vars.insert( class2.vars.begin(), class2.vars.end() ); + class1.allowWidening = widen1 && widen2; + if( common ) { + common->get_qualifiers() = Type::Qualifiers(); + delete class1.type; + class1.type = common; + } + env.add( class1 ); + } else { + result = false; + } + } else if( hasClass1 && hasClass2 ) { + if( type1 ) { + class1.vars.insert( class2.vars.begin(), class2.vars.end() ); + class1.allowWidening = widen1; + env.add( class1 ); + } else { + class2.vars.insert( class1.vars.begin(), class1.vars.end() ); + class2.allowWidening = widen2; + env.add( class2 ); + } + } else if( hasClass1 ) { + class1.vars.insert( var2->get_name() ); + class1.allowWidening = widen1; + env.add( class1 ); + } else if( hasClass2 ) { + class2.vars.insert( var1->get_name() ); + class2.allowWidening = widen2; + env.add( class2 ); + } else { + EqvClass newClass; + newClass.vars.insert( var1->get_name() ); + newClass.vars.insert( var2->get_name() ); + newClass.allowWidening = widen1 && widen2; + newClass.kind = kind; + env.add( newClass ); + } + delete type1; + delete type2; + return result; +} + +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; + } + return true; + } else { + return false; + } +} + +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 widenMode, const SymTab::Indexer &indexer ) +{ +#ifdef DEBUG + TypeEnvironment debugEnv( env ); +#endif + 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( var2 ) { + entry2 = openVars.find( var2->get_name() ); + } + bool isopen1 = var1 && ( entry1 != openVars.end() ); + bool isopen2 = var2 && ( entry2 != openVars.end() ); + if( type1->get_qualifiers() != type2->get_qualifiers() ) { + return false; + } else if( isopen1 && isopen2 && entry1->second == entry2->second ) { + result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + } else if( isopen1 ) { + result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + } else if( isopen2 ) { + result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + } else { + Unify comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + type1->accept( comparator ); + result = comparator.get_result(); + } +#ifdef DEBUG + std::cout << "============ unifyExact" << std::endl; + std::cout << "type1 is "; + type1->print( std::cout ); + std::cout << std::endl << "type2 is "; + type2->print( std::cout ); + std::cout << std::endl << "openVars are "; + printOpenVarSet( openVars, std::cout, 8 ); + std::cout << std::endl << "input env is " << std::endl; + debugEnv.print( std::cout, 8 ); + std::cout << std::endl << "result env is " << std::endl; + env.print( std::cout, 8 ); + std::cout << "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 widenMode, 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::cout << "unifyInexact type 1 is "; + type1->print( std::cout ); + std::cout << "type 2 is "; + type2->print( std::cout ); + std::cout << std::endl; +#endif + if( !unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) { +#ifdef DEBUG + std::cout << "unifyInexact: no exact unification found" << std::endl; +#endif + if( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) { + common->get_qualifiers() = tq1 + tq2; +#ifdef DEBUG + std::cout << "unifyInexact: common type is "; + common->print( std::cout ); + std::cout << std::endl; +#endif + result = true; + } else { +#ifdef DEBUG + std::cout << "unifyInexact: no common type found" << std::endl; +#endif + result = false; + } + } else { + if( tq1 != tq2 ) { + if( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) { + common = type1->clone(); + common->get_qualifiers() = tq1 + tq2; + result = true; + } else { + result = false; + } + } else { + result = true; + } + } + type1->get_qualifiers() = tq1; + type2->get_qualifiers() = tq2; + return result; +} + +Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) + : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) +{ +} + +void +Unify::visit(VoidType *voidType) +{ + result = dynamic_cast< VoidType* >( type2 ); +} + +void +Unify::visit(BasicType *basicType) +{ + if( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { + result = basicType->get_kind() == otherBasic->get_kind(); + } +} + +void +markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) +{ +/// std::cout << "assertion set is" << std::endl; +/// printAssertionSet( assertions, std::cout, 8 ); +/// std::cout << "looking for "; +/// assert->print( std::cout ); +/// std::cout << std::endl; + AssertionSet::iterator i = assertions.find( assert ); + if( i != assertions.end() ) { +/// std::cout << "found it!" << std::endl; + i->second = true; + } +} + +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 ); + } + } +} + +void +Unify::visit(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 ); + } +} + +void +Unify::visit(ArrayType *arrayType) +{ + // XXX -- compare array dimension + ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 ); + if( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) { + result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); + } +} + +template< typename Iterator1, typename Iterator2 > +bool +unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) { + for( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { + if( !unifyExact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) { + return false; + } + } + if( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } +} + +void +Unify::visit(FunctionType *functionType) +{ + FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 ); + if( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) { + + if( unifyDeclList( functionType->get_parameters().begin(), functionType->get_parameters().end(), otherFunction->get_parameters().begin(), otherFunction->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { + + if( unifyDeclList( functionType->get_returnVals().begin(), functionType->get_returnVals().end(), otherFunction->get_returnVals().begin(), otherFunction->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { + + markAssertions( haveAssertions, needAssertions, functionType ); + markAssertions( haveAssertions, needAssertions, otherFunction ); + + result = true; + } + } + } +} + +template< typename RefType > +void +Unify::handleRefType( RefType *inst, Type *other ) +{ + RefType *otherStruct = dynamic_cast< RefType* >( other ); + result = otherStruct && inst->get_name() == otherStruct->get_name(); +} + +void +Unify::visit(StructInstType *structInst) +{ + handleRefType( structInst, type2 ); +} + +void +Unify::visit(UnionInstType *unionInst) +{ + handleRefType( unionInst, type2 ); +} + +void +Unify::visit(EnumInstType *enumInst) +{ + handleRefType( enumInst, type2 ); +} + +void +Unify::visit(ContextInstType *contextInst) +{ + handleRefType( contextInst, type2 ); +} + +void +Unify::visit(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 ); +/// } +/// } + } +} + +template< typename Iterator1, typename Iterator2 > +bool +unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { + for( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { + Type *commonType = 0; + if( !unifyInexact( *list1Begin, *list2Begin, env, needAssertions, haveAssertions, openVars, widenMode, indexer, commonType ) ) { + return false; + } + delete commonType; + } + if( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } +} + +void +Unify::visit(TupleType *tupleType) +{ + if( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) { + result = unifyList( tupleType->get_types().begin(), tupleType->get_types().end(), otherTuple->get_types().begin(), otherTuple->get_types().end(), env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + } +} + +} // namespace ResolvExpr Index: translator/ResolvExpr/Unify.h =================================================================== --- translator/ResolvExpr/Unify.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/Unify.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,57 @@ +/* + * This file is part of the Cforall project + * + * $Id: Unify.h,v 1.4 2005/08/29 20:14:16 rcbilson Exp $ + * + */ + +#ifndef UNIFY_H +#define UNIFY_H + +#include +#include +#include "SynTree/SynTree.h" +#include "SynTree/Type.h" +#include "SynTree/Declaration.h" +#include "SymTab/Indexer.h" +#include "TypeEnvironment.h" +#include "utility.h" + +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 ); + +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; + } + commonTypes.push_back( commonType ); + } + if( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } +} + +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; + } +} + +} // namespace ResolvExpr + +#endif /* #ifndef UNIFY_H */ Index: translator/ResolvExpr/module.mk =================================================================== --- translator/ResolvExpr/module.mk (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/module.mk (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,18 @@ +SRC += ResolvExpr/AlternativeFinder.cc \ + ResolvExpr/Alternative.cc \ + ResolvExpr/Unify.cc \ + ResolvExpr/PtrsAssignable.cc \ + ResolvExpr/CommonType.cc \ + ResolvExpr/ConversionCost.cc \ + ResolvExpr/CastCost.cc \ + ResolvExpr/PtrsCastable.cc \ + ResolvExpr/AdjustExprType.cc \ + ResolvExpr/AlternativePrinter.cc \ + ResolvExpr/Resolver.cc \ + ResolvExpr/ResolveTypeof.cc \ + ResolvExpr/RenameVars.cc \ + ResolvExpr/FindOpenVars.cc \ + ResolvExpr/PolyCost.cc \ + ResolvExpr/Occurs.cc \ + ResolvExpr/TypeEnvironment.cc + Index: translator/ResolvExpr/typeops.h =================================================================== --- translator/ResolvExpr/typeops.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) +++ translator/ResolvExpr/typeops.h (revision 51b734528489f81a5af985bfee9aa3b6625b9774) @@ -0,0 +1,161 @@ +/* + * This file is part of the Cforall project + * + * $Id: typeops.h,v 1.14 2005/08/29 20:14:17 rcbilson Exp $ + * + */ + +#ifndef TYPEOPS_H +#define TYPEOPS_H + +#include "SynTree/SynTree.h" +#include "SynTree/Type.h" +#include "SymTab/Indexer.h" +#include "Cost.h" +#include "TypeEnvironment.h" + +namespace ResolvExpr { + +// combos: takes a list of sets and returns a set of lists representing +// every possible way of forming a list by picking one element out of each set +template< typename InputIterator, typename OutputIterator > +void +combos( InputIterator begin, InputIterator end, OutputIterator out ) +{ + typedef typename InputIterator::value_type SetType; + typedef typename std::list< typename SetType::value_type > ListType; + + if( begin == end ) + { + *out++ = ListType(); + return; + } + + InputIterator current = begin; + begin++; + + std::list< ListType > recursiveResult; + combos( begin, end, back_inserter( recursiveResult ) ); + + for( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) { + for( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) { + ListType result; + std::back_insert_iterator< ListType > inserter = back_inserter( result ); + *inserter++ = *j; + std::copy( i->begin(), i->end(), inserter ); + *out++ = result; + } + } +} + +// in AdjustExprType.cc +void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ); + +template< typename ForwardIterator > +void +adjustExprTypeList( ForwardIterator begin, ForwardIterator end, const TypeEnvironment &env, const SymTab::Indexer &indexer ) +{ + while( begin != end ) { + adjustExprType( *begin++, env, indexer ); + } +} + +// in CastCost.cc +Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ); + +template< typename SrcIterator, typename DestIterator > +Cost +castCostList( SrcIterator srcBegin, SrcIterator srcEnd, DestIterator destBegin, DestIterator destEnd, const SymTab::Indexer &indexer, const TypeEnvironment &env ) +{ + Cost ret; + if( destBegin == destEnd ) { + if( srcBegin == srcEnd ) { + return Cost::zero; + } else { + return Cost( 0, 0, 1 ); + } + } + while( srcBegin != srcEnd && destBegin != destEnd ) { + Cost thisCost = castCost( *srcBegin++, *destBegin++, indexer, env ); + if( thisCost == Cost::infinity ) { + return Cost::infinity; + } + ret += thisCost; + } + if( srcBegin == srcEnd && destBegin == destEnd ) { + return ret; + } else { + return Cost::infinity; + } +} + +// in ConversionCost.cc +Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ); + +template< typename SrcIterator, typename DestIterator > +Cost +conversionCostList( SrcIterator srcBegin, SrcIterator srcEnd, DestIterator destBegin, DestIterator destEnd, const SymTab::Indexer &indexer, const TypeEnvironment &env ) +{ + Cost ret; + while( srcBegin != srcEnd && destBegin != destEnd ) { + Cost thisCost = conversionCost( *srcBegin++, *destBegin++, indexer, env ); + if( thisCost == Cost::infinity ) { + return Cost::infinity; + } + ret += thisCost; + } + if( srcBegin == srcEnd && destBegin == destEnd ) { + return ret; + } else { + return Cost::infinity; + } +} + +// in PtrsAssignable.cc +int ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env ); + +// in PtrsCastable.cc +int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ); + +// in Unify.cc +bool typesCompatible( Type *, Type *, const SymTab::Indexer &indexer, const TypeEnvironment &env ); +bool typesCompatibleIgnoreQualifiers( Type *, Type *, const SymTab::Indexer &indexer, const TypeEnvironment &env ); + +inline bool typesCompatible( Type *t1, Type *t2, const SymTab::Indexer &indexer ) +{ + TypeEnvironment env; + return typesCompatible( t1, t2, indexer, env ); +} + +inline bool typesCompatibleIgnoreQualifiers( Type *t1, Type *t2, const SymTab::Indexer &indexer ) +{ + TypeEnvironment env; + return typesCompatibleIgnoreQualifiers( t1, t2, indexer, env ); +} + +template< typename Container1, typename Container2 > +bool +typesCompatibleList( Container1 &c1, Container2 &c2, const SymTab::Indexer &indexer, const TypeEnvironment &env ) +{ + typename Container1::iterator i1 = c1.begin(); + typename Container2::iterator i2 = c2.begin(); + for( ; i1 != c1.end() && i2 != c2.end(); ++i1, ++i2 ) { + if( !typesCompatible( *i1, *i2, indexer ) ) { + return false; + } + } + return ( i1 == c1.end() ) && ( i2 == c2.end() ); +} + +// in CommonType.cc +Type *commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); + +// in PolyCost.cc +int polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer ); + +// in Occurs.cc +bool occurs( Type *type, std::string varName, const TypeEnvironment &env ); + +} // namespace ResolvExpr + +#endif /* #ifndef TYPEOPS_H */