Index: src/ResolvExpr/AdjustExprType.cc =================================================================== --- src/ResolvExpr/AdjustExprType.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/AdjustExprType.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,119 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// AdjustExprType.cc -- +// +// Author : Richard C. Bilson +// Created On : Sat May 16 23:41:42 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat May 16 23:54:02 2015 +// Update Count : 3 +// + +#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; + } // if + } // if + } // if + return typeInst; + } + + Type *AdjustExprType::mutate( TupleType *tupleType ) { + return tupleType; + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Alternative.cc =================================================================== --- src/ResolvExpr/Alternative.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Alternative.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,71 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Alternative.cc -- +// +// Author : Richard C. Bilson +// Created On : Sat May 16 23:44:23 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat May 16 23:54:23 2015 +// Update Count : 2 +// + +#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; + } // if + os << std::string( indent, ' ' ) << "Environment: "; + env.print( os, indent+2 ); + os << std::endl; + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Alternative.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,53 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Alternative.h -- +// +// Author : Richard C. Bilson +// Created On : Sat May 16 23:45:43 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat May 16 23:54:39 2015 +// Update Count : 2 +// + +#ifndef ALTERNATIVE_H +#define 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 // ALTERNATIVE_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/AlternativeFinder.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,922 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// AlternativeFinder.cc -- +// +// Author : Richard C. Bilson +// Created On : Sat May 16 23:52:08 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat May 16 23:55:30 2015 +// Update Count : 3 +// + +#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" + +extern bool resolvep; +#define PRINT( text ) if ( resolvep ) { text } +//#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 ) { + PRINT( + std::cout << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl; + ) + selected[ mangleName ] = current; + } else if ( candidate->cost == mapPlace->second.candidate->cost ) { + PRINT( + std::cout << "marking ambiguous" << std::endl; + ) + mapPlace->second.isAmbiguous = true; + } + } else { + selected[ mangleName ] = current; + } + } + + PRINT( + 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++; + PRINT( + 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 ); + } + } + PRINT( + 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() ); + PRINT( + 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 ) { + PRINT( + 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; + } + } + PRINT( + 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 ); + PRINT( + 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 ) { + PRINT( + 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 ); + PRINT( + 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; + } + PRINT( + 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; + PRINT( + 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; + PRINT( + 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 ) { + PRINT( + 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 ); + PRINT( + 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 ) ) { + PRINT( + 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() ); + PRINT( + 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 ) { +// PRINT( +// std::cout << "inferParameters: assertions needed are" << std::endl; +// printAll( need, std::cout, 8 ); +// ) + SymTab::Indexer decls( indexer ); + PRINT( + 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 ); +// PRINT( +// 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() ); + PRINT( + 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 ) { + PRINT( + 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 ) ); + } // for + } // if + } // if + } // if + } 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 + } + PRINT( + 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 + } // if + } // if + } // for + } // if + } // for + + for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { + Cost cvtCost = computeConversionCost( *withFunc, indexer ); + + PRINT( + 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; + ) + if ( cvtCost != Cost::infinity ) { + withFunc->cvtCost = cvtCost; + alternatives.push_back( *withFunc ); + } // if + } // for + 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; + } // for + 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 ) ); + } // if + } // for + } + + 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 ); + } // for + + 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 ) ); + } // if + } // for + + // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the + // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice + // selects first based on argument cost, then on conversion cost. + AltList minArgCost; + findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); + findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); + } + + void AlternativeFinder::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() ); + } // if + } // if + } // for + } + + 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 ); + PRINT( 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() ) ); + PRINT( + 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 ), "" ); + } // if + } // for + } + + 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 { + // find all alternatives for the argument to sizeof + AlternativeFinder finder( indexer, env ); + finder.find( sizeofExpr->get_expr() ); + // find the lowest cost alternative among the alternatives, otherwise ambiguous + AltList winners; + findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); + if ( winners.size() != 1 ) { + throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() ); + } // if + // return the lowest cost alternative for the argument + Alternative &choice = winners.front(); + alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); + } // if + } + + 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 ); + PRINT( + 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() ); + } // for + } // if + } + + 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 ); + } // fi + } // for + } // if + } // if + } // if + } // for + } 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 ); + } // for + } // if + } + + 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() ); + } // if + } // for + newAlt.expr = newExpr; + inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); + } // if + } // for + } // for + } // for + } + + 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 ) ); + } // for + 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() ); + } // for + } // for + + TypeEnvironment compositeEnv; + simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); + alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) ); + } // for + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/AlternativeFinder.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,89 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// AlternativeFinder.h -- +// +// Author : Richard C. Bilson +// Created On : Sat May 16 23:56:12 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat May 16 23:58:43 2015 +// Update Count : 2 +// + +#ifndef ALTERNATIVEFINDER_H +#define 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; + }; // AlternativeFinder + + Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ); +} // namespace ResolvExpr + +#endif // ALTERNATIVEFINDER_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/AlternativePrinter.cc =================================================================== --- src/ResolvExpr/AlternativePrinter.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/AlternativePrinter.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,46 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// AlternativePrinter.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 06:53:19 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 06:55:05 2015 +// Update Count : 2 +// + +#include "AlternativePrinter.h" +#include "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; + } // for + } // AlternativePrinter::visit +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/AlternativePrinter.h =================================================================== --- src/ResolvExpr/AlternativePrinter.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/AlternativePrinter.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,40 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// AlternativePrinter.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 06:55:43 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 06:57:12 2015 +// Update Count : 3 +// + +#ifndef ALTERNATIVEPRINTER_H +#define 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 // ALTERNATIVEPRINTER_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/CastCost.cc =================================================================== --- src/ResolvExpr/CastCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/CastCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,102 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// CastCost.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 06:57:43 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 06:59:10 2015 +// Update Count : 2 +// + +#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 ) { + 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 + } // if + } // if + if ( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) { + return Cost( 0, 0, 0 ); + } else if ( dynamic_cast< VoidType* >( dest ) ) { + return Cost( 0, 0, 1 ); + } else { + CastCost 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 ); + } // if + } // if + } + + 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 ); + } // if + } + + 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 ); + } // if + } 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 ); + } // if + } // if + } // if + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/CommonType.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,221 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// CommonType.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 06:59:27 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 07:04:50 2015 +// Update Count : 2 +// + +#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; + } // if + type1->get_qualifiers() = tq1; + type->get_base()->get_qualifiers() = Type::Qualifiers(); + } // if + } // if + } // if + } // if + } // if +#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"; + } // if + 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 ); + } // if + } // if + } + + 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(); + } // if + result->get_qualifiers() = tq1 + tq2; + } else { + /// std::cout << "place for ptr-to-type" << std::endl; + } // if + pointerType->get_base()->get_qualifiers() = tq1; + otherPointer->get_base()->get_qualifiers() = tq2; + } // if + } // if + } + + 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; + } // if + type2->get_qualifiers() = tq2; + type->get_base()->get_qualifiers() = Type::Qualifiers(); + } // if + } // if + } // if + } + + void CommonType::visit( TupleType *tupleType ) { + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/ConversionCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,255 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ConversionCost.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 07:06:19 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 07:22:19 2015 +// Update Count : 4 +// + +#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 ); + } // if + } // if +/// std::cout << " not found" << std::endl; + } // if +/// 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 ); + } // if + } // if + } + + 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 ); + } // if + } // if + } + + 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 ); + } // if + } // if + } // if + } + + 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; + } // if + } // if + } + + void ConversionCost::visit(UnionInstType *inst) { + if ( StructInstType *destAsInst = dynamic_cast< StructInstType* >( dest ) ) { + if ( inst->get_name() == destAsInst->get_name() ) { + cost = Cost::zero; + } // if + } // if + } + + 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(); + } // if + } + + 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 ); + } // if + } // if + } + + 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; + } // if + c += newCost; + } // while + if ( destIt != destAsTuple->get_types().end() ) { + cost = Cost::infinity; + } else { + cost = c; + } // if + } // if + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ConversionCost.h =================================================================== --- src/ResolvExpr/ConversionCost.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/ConversionCost.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,56 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ConversionCost.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:37:28 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:39:23 2015 +// Update Count : 2 +// + +#ifndef CONVERSIONCOST_H +#define CONVERSIONCOST_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 // CONVERSIONCOST_H */ + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Cost.h =================================================================== --- src/ResolvExpr/Cost.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Cost.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,122 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Cost.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:39:50 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:42:04 2015 +// Update Count : 3 +// + +#ifndef COST_H +#define 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; + } // if + } + + 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 // COST_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/FindOpenVars.cc =================================================================== --- src/ResolvExpr/FindOpenVars.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/FindOpenVars.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,102 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// FindOpenVars.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:42:48 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:45:25 2015 +// Update Count : 3 +// + +#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() ); + } // for + } // if +/// 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 + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/FindOpenVars.h =================================================================== --- src/ResolvExpr/FindOpenVars.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/FindOpenVars.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,32 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// FindOpenVars.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:46:04 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:47:20 2015 +// Update Count : 2 +// + +#ifndef FINDOPENVARS_H +#define 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 // FINDOPENVARS_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Occurs.cc =================================================================== --- src/ResolvExpr/Occurs.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Occurs.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,72 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Occurs.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:47:41 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:49:26 2015 +// Update Count : 2 +// + +#include +#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 ); + } // if + } + + 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 ); + } // if + } // if + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/PolyCost.cc =================================================================== --- src/ResolvExpr/PolyCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/PolyCost.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,64 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PolyCost.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 09:50:12 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 09:52:02 2015 +// Update Count : 3 +// + +#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; + } // if + } else { + result += 1; + } // if + } // if + } // if + } + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/PtrsAssignable.cc =================================================================== --- src/ResolvExpr/PtrsAssignable.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/PtrsAssignable.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,145 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PtrsAssignable.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 11:44:11 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 11:47:36 2015 +// Update Count : 2 +// + +#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 + } // if + if ( dynamic_cast< VoidType* >( dest ) ) { + return 1; + } else { + PtrsAssignable ptrs( dest, env ); + src->accept( ptrs ); + return ptrs.get_result(); + } // if + } + + 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; + } // if + } + + 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; + } // if + } + + 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 + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/PtrsCastable.cc =================================================================== --- src/ResolvExpr/PtrsCastable.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/PtrsCastable.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,147 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PtrsCastable.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 11:48:00 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 11:51:17 2015 +// Update Count : 2 +// + +#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; + } // if + } //if + } else if ( env.lookup( typeInst->get_name(), eqvClass ) ) { + if ( eqvClass.kind == TypeDecl::Ftype ) { + return -1; + } // if + } // if + } //if + 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 + } // if + if ( dynamic_cast< VoidType* >( dest ) ) { + return objectCast( src, env, indexer ); + } else { + PtrsCastable ptrs( dest, env, indexer ); + src->accept( ptrs ); + return ptrs.get_result(); + } // if + } + + 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 + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/RenameVars.cc =================================================================== --- src/ResolvExpr/RenameVars.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/RenameVars.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,145 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// RenameVars.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:05:18 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:07:59 2015 +// Update Count : 2 +// + +#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; + } // if + 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 ); + } // for + } // if + } + + void RenameVars::typeAfter( Type *type ) { + if ( ! type->get_forall().empty() ) { + mapStack.pop_front(); + } // if + } + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/RenameVars.h =================================================================== --- src/ResolvExpr/RenameVars.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/RenameVars.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,59 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// RenameVars.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:10:28 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:11:53 2015 +// Update Count : 2 +// + +#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 // RENAMEVARS_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ResolveTypeof.cc =================================================================== --- src/ResolvExpr/ResolveTypeof.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/ResolveTypeof.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,80 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ResolveTypeof.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:12:20 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Tue May 19 16:49:04 2015 +// Update Count : 3 +// + +#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 ) { +#if 0 + std::cout << "resolving typeof: "; + typeofType->print( std::cout ); + std::cout << std::endl; +#endif + 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(); + } // if + delete typeofType; + return newType; + } // if + return typeofType; + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ResolveTypeof.h =================================================================== --- src/ResolvExpr/ResolveTypeof.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/ResolveTypeof.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,32 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ResolveTypeof.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:14:53 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:16:29 2015 +// Update Count : 2 +// + +#ifndef RESOLVETYPEOF_H +#define RESOLVETYPEOF_H + +#include "SynTree/SynTree.h" +#include "SymTab/Indexer.h" + +namespace ResolvExpr { + Type *resolveTypeof( Type*, const SymTab::Indexer &indexer ); +} // namespace ResolvExpr + +#endif // RESOLVETYPEOF_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Resolver.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,351 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Resolver.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:17:01 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:18:17 2015 +// Update Count : 2 +// + +#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" + +#include +using namespace std; + +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 ); + virtual void visit( ListInit *listInit ); + private: + std::list< Type * > functionReturn; + Type *initContext; + Type *switchType; + }; + + void resolve( std::list< Declaration * > translationUnit ) { + Resolver resolver; + acceptAll( translationUnit, resolver ); +#if 0 + resolver.print( cerr ); + for ( std::list< Declaration * >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) { + (*i)->print( std::cerr ); + (*i)->accept( resolver ); + } // for +#endif + } + + 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 0 + 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 ); + } // for + } // if +#endif + 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 false; + } // if + } + + Expression *findIntegralExpression( Expression *untyped, const SymTab::Indexer &indexer ) { + TypeEnvironment env; + AlternativeFinder finder( indexer, env ); + finder.find( untyped ); +#if 0 + 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 ); + } // for + } // if +#endif + 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 case control expression", untyped ); + } else { + newExpr = i->expr->clone(); + newEnv = &i->env; + } // if + } // if + } // for + if ( ! newExpr ) { + throw SemanticError( "No interpretations for case control expression", untyped ); + } // if + 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 ); + } // if + SymTab::Indexer::visit( typeDecl ); + } + + void Resolver::visit( FunctionDecl *functionDecl ) { +#if 0 + std::cout << "resolver visiting functiondecl "; + functionDecl->print( std::cout ); + std::cout << std::endl; +#endif + 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() ); + } // for + 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 ); + } // if + } + + 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 ) { + // SymTab::Indexer::visit( forStmt ); + Expression *newExpr; + // for statements introduce a level of scope + enterScope(); + maybeAccept( forStmt->get_initialization(), *this ); + if ( forStmt->get_condition() ) { + newExpr = findSingleExpression( forStmt->get_condition(), *this ); + delete forStmt->get_condition(); + forStmt->set_condition( newExpr ); + } // if + + if ( forStmt->get_increment() ) { + newExpr = findVoidExpression( forStmt->get_increment(), *this ); + delete forStmt->get_increment(); + forStmt->set_increment( newExpr ); + } // if + + maybeAccept( forStmt->get_condition(), *this ); + maybeAccept( forStmt->get_increment(), *this ); + maybeAccept( forStmt->get_body(), *this ); + leaveScope(); + } + + 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 ); + } // if + } + + void Resolver::visit( SingleInit *singleInit ) { + if ( singleInit->get_value() ) { +#if 0 + if (NameExpr * ne = dynamic_cast(singleInit->get_value())) { + string n = ne->get_name(); + if (n == "0") { + initContext = new BasicType(Type::Qualifiers(), + BasicType::SignedInt); + } else { + DeclarationWithType * decl = lookupId(n); + initContext = decl->get_type(); + } + } else if (ConstantExpr * e = + dynamic_cast(singleInit->get_value())) { + Constant *c = e->get_constant(); + initContext = c->get_type(); + } else { + assert(0); + } +#endif + CastExpr *castExpr = new CastExpr( singleInit->get_value(), initContext->clone() ); + Expression *newExpr = findSingleExpression( castExpr, *this ); + delete castExpr; + singleInit->set_value( newExpr ); + } // if +// singleInit->get_value()->accept( *this ); + } + + void Resolver::visit( ListInit *listInit ) { + Visitor::visit(listInit); +#if 0 + if ( ArrayType *at = dynamic_cast(initContext) ) { + std::list::iterator iter( listInit->begin_initializers() ); + for ( ; iter != listInit->end_initializers(); ++iter ) { + initContext = at->get_base(); + (*iter)->accept( *this ); + } // for + } else if ( StructInstType *st = dynamic_cast(initContext) ) { + StructDecl *baseStruct = st->get_baseStruct(); + std::list::iterator iter1( baseStruct->get_members().begin() ); + std::list::iterator iter2( listInit->begin_initializers() ); + for ( ; iter1 != baseStruct->get_members().end() && iter2 != listInit->end_initializers(); ++iter2 ) { + if ( (*iter2)->get_designators().empty() ) { + DeclarationWithType *dt = dynamic_cast( *iter1 ); + initContext = dt->get_type(); + (*iter2)->accept( *this ); + ++iter1; + } else { + StructDecl *st = baseStruct; + iter1 = st->get_members().begin(); + std::list::iterator iter3( (*iter2)->get_designators().begin() ); + for ( ; iter3 != (*iter2)->get_designators().end(); ++iter3 ) { + NameExpr *key = dynamic_cast( *iter3 ); + assert( key ); + for ( ; iter1 != st->get_members().end(); ++iter1 ) { + if ( key->get_name() == (*iter1)->get_name() ) { + (*iter1)->print( cout ); + cout << key->get_name() << endl; + ObjectDecl *fred = dynamic_cast( *iter1 ); + assert( fred ); + StructInstType *mary = dynamic_cast( fred->get_type() ); + assert( mary ); + st = mary->get_baseStruct(); + iter1 = st->get_members().begin(); + break; + } // if + } // for + } // for + ObjectDecl *fred = dynamic_cast( *iter1 ); + assert( fred ); + initContext = fred->get_type(); + (*listInit->begin_initializers())->accept( *this ); + } // if + } // for + } else if ( UnionInstType *st = dynamic_cast(initContext) ) { + DeclarationWithType *dt = dynamic_cast( *st->get_baseUnion()->get_members().begin() ); + initContext = dt->get_type(); + (*listInit->begin_initializers())->accept( *this ); + } // if +#endif + } +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Resolver.h =================================================================== --- src/ResolvExpr/Resolver.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Resolver.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,33 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Resolver.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:18:34 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:19:32 2015 +// Update Count : 2 +// + +#ifndef RESOLVER_H +#define 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 // RESOLVER_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/TypeEnvironment.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,207 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeEnvironment.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:19:47 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:23:36 2015 +// Update Count : 3 +// + +#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)"; + } // if + } // for + } + + void printOpenVarSet( const OpenVarSet &openVars, std::ostream &os, int indent ) { + os << std::string( indent, ' ' ); + for ( OpenVarSet::const_iterator i = openVars.begin(); i != openVars.end(); ++i ) { + os << i->first << "(" << i->second << ") "; + } // for + } + + void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { + 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 + if ( ! allowWidening ) { + os << " (no widening)"; + } // if + 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 ); + } // for + 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 ); + } // if + i = next; + } // while + 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 ); + } // for + } + + 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; + } // if + } // for + } // for +/// 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 ); + } // for + } + + 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; + } // if + } // for + 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; + } // if + } // if + secondCopy.env.erase( secondClass ); + } // if + } // for + newClass.vars.insert( newVars.begin(), newVars.end() ); + } // for + for ( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) { + env.push_back( *secondClass ); + } // for + } + + 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; + } // for + } // for + } + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/TypeEnvironment.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,97 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeEnvironment.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:24:58 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 12:26:52 2015 +// Update Count : 2 +// + +#ifndef TYPEENVIRONMENT_H +#define 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 // TYPEENVIRONMENT_H */ + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Unify.cc (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,525 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Unify.cc -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 12:27:10 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 13:08:48 2015 +// Update Count : 6 +// + +#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(); + } // if + 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 ); + } // switch + 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 + if ( occurs( other, typeInst->get_name(), env ) ) { + return false; + } // if + 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 ); + } // if + return true; + } else { + return false; + } // if + } else { + curClass.type = other->clone(); + curClass.type->get_qualifiers() = Type::Qualifiers(); + curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + env.add( curClass ); + } // if + } 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 ); + } // if + 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; + } // if + type1 = class1.type->clone(); + } // if + widen1 = widenMode.widenFirst && class1.allowWidening; + } // if + if ( env.lookup( var2->get_name(), class2 ) ) { + hasClass2 = true; + if ( class2.type ) { + if ( occurs( class2.type, var1->get_name(), env ) ) { + return false; + } // if + type2 = class2.type->clone(); + } // if + widen2 = widenMode.widenSecond && class2.allowWidening; + } // if + + 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; + } // if + env.add( class1 ); + } else { + result = false; + } // if + } 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 ); + } // if + } 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 ); + } // if + 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; + } // if + return true; + } else { + return false; + } // if + } + + bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) { + OpenVarSet closedVars; + findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false ); + findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true ); + return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ); + } + + bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode 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 + if ( var2 ) { + entry2 = openVars.find( var2->get_name() ); + } // if + 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(); + } // if +#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; + } // if + } 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; + } // if + } else { + result = true; + } // if + } // if + 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(); + } // if + } + + 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; + } // if + } + + void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) { + for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { + for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { + markAssertionSet( assertion1, *assert ); + markAssertionSet( assertion2, *assert ); + } // for + } // for + } + + void Unify::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 ); + } // if + } + + 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 ); + } // if + } + + 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 + } // for + if ( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } // if + } + + 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; + } // if + } // if + } // if + } + + 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 ); +/// } +/// } + } // if + } + + template< typename Iterator1, typename Iterator2 > + bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, 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; + } // for + if ( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } //if + } + + 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 ); + } // if + } + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Unify.h =================================================================== --- src/ResolvExpr/Unify.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/Unify.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,68 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Unify.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 13:09:04 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 13:10:34 2015 +// Update Count : 2 +// + +#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; + } // if + commonTypes.push_back( commonType ); + } // for + if ( list1Begin != list1End || list2Begin != list2End ) { + return false; + } else { + return true; + } // if + } + + template< typename Iterator1, typename Iterator2 > + bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { + std::list< Type* > commonTypes; + if ( unifyList( list1Begin, list1End, list2Begin, list2End, env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) { + deleteAll( commonTypes ); + return true; + } else { + return false; + } // if + } + +} // namespace ResolvExpr + +#endif // UNIFY_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/module.mk (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -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: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) +++ src/ResolvExpr/typeops.h (revision 843054c23fcb725d2486e5e42e91b3741bc523b8) @@ -0,0 +1,160 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// typeops.h -- +// +// Author : Richard C. Bilson +// Created On : Sun May 17 07:28:22 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun May 17 07:33:11 2015 +// Update Count : 2 +// + +#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; + } // if + + 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; + } // for + } // for + } + + // 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 ); + } // while + } + + // 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 ); + } // if + } // if + while ( srcBegin != srcEnd && destBegin != destEnd ) { + Cost thisCost = castCost( *srcBegin++, *destBegin++, indexer, env ); + if ( thisCost == Cost::infinity ) { + return Cost::infinity; + } // if + ret += thisCost; + } // while + if ( srcBegin == srcEnd && destBegin == destEnd ) { + return ret; + } else { + return Cost::infinity; + } // if + } + + // 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; + } // if + ret += thisCost; + } // while + if ( srcBegin == srcEnd && destBegin == destEnd ) { + return ret; + } else { + return Cost::infinity; + } // if + } + + // 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; + } // if + } + 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 // TYPEOPS_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: //