source: translator/GenPoly/Box.cc @ 51b7345

/*
 * This file is part of the Cforall project
 *
 * $Id: Box.cc,v 1.20 2005/08/29 20:14:13 rcbilson Exp $
 *
 */

#include <set>
#include <string>
#include <iterator>
#include <algorithm>
#include <cassert>

#include "Box.h"
#include "PolyMutator.h"
#include "FindFunction.h"
#include "ScrubTyVars.h"

#include "SynTree/Declaration.h"
#include "SynTree/Type.h"
#include "SynTree/Expression.h"
#include "SynTree/Initializer.h"
#include "SynTree/Statement.h"
#include "SynTree/Mutator.h"
#include "ResolvExpr/TypeEnvironment.h"
#include "SymTab/Mangler.h"

#include "SemanticError.h"
#include "UniqueName.h"
#include "utility.h"

#include <ext/functional> // temporary

namespace GenPoly {

namespace {

const std::list<Label> noLabels;

class Pass1 : public PolyMutator
{
public:
  Pass1();
  virtual Expression *mutate( ApplicationExpr *appExpr );
  virtual Expression *mutate( AddressExpr *addrExpr );
  virtual Expression *mutate( UntypedExpr *expr );
  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
  virtual TypeDecl* mutate( TypeDecl *typeDecl );
  virtual Expression *mutate( CommaExpr *commaExpr );
  virtual Expression *mutate( ConditionalExpr *condExpr );
  virtual Statement* mutate(ReturnStmt *catchStmt);
  virtual Type* mutate( PointerType *pointerType );
  virtual Type* mutate( FunctionType *pointerType );
  
  virtual void doEndScope();
  
private:
  void passTypeVars( ApplicationExpr* appExpr, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
  Expression* addRetParam( ApplicationExpr* appExpr, FunctionType *function, Type *retType, std::list< Expression* >::iterator &arg );
  Expression* addPolyRetParam( ApplicationExpr* appExpr, FunctionType *function, std::string typeName, std::list< Expression* >::iterator &arg );
  Expression* applyAdapter( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
  void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
  void boxParams( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars );
  void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars );
  void findAssignOps( const std::list< TypeDecl* > &forall );
  void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
  FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
  Expression *handleIntrinsics( ApplicationExpr *appExpr );
  ObjectDecl *makeTemporary( Type *type );
  
  std::map< std::string, DeclarationWithType* > assignOps;
  std::map< std::string, FunctionDecl* > adapters;
  DeclarationWithType* retval;
  bool useRetval;
  UniqueName tempNamer;
};

class Pass2 : public PolyMutator
{
public:
  Pass2();
  template< typename DeclClass >
  DeclClass* handleDecl( DeclClass *decl, Type *type );
  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
  virtual ObjectDecl* mutate( ObjectDecl *objectDecl );
  virtual TypeDecl* mutate( TypeDecl *typeDecl );
  virtual TypedefDecl* mutate( TypedefDecl *typedefDecl );
  virtual Type* mutate( PointerType *pointerType );
  virtual Type* mutate( FunctionType *funcType );

private:
  void addAdapters( FunctionType *functionType );
  
  std::map< UniqueId, std::string > adapterName;
};

class Pass3 : public PolyMutator
{
public:
  template< typename DeclClass >
  DeclClass* handleDecl( DeclClass *decl, Type *type );
  virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
  virtual ObjectDecl* mutate( ObjectDecl *objectDecl );
  virtual TypedefDecl* mutate( TypedefDecl *objectDecl );
  virtual TypeDecl* mutate( TypeDecl *objectDecl );
  virtual Statement* mutate( DeclStmt *declStmt );
  virtual Type* mutate( PointerType *pointerType );
  virtual Type* mutate( FunctionType *funcType );

private:
};

} // anonymous namespace

void
printAllNotBuiltin( const std::list< Declaration* >& translationUnit, std::ostream &os )
{
  for( std::list< Declaration* >::const_iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
    if( !LinkageSpec::isBuiltin( (*i)->get_linkage() ) ) {
      (*i)->print( os );
      os << std::endl;
    }
  }
}

void
box( std::list< Declaration* >& translationUnit )
{
  Pass1 pass1;
  Pass2 pass2;
  Pass3 pass3;
  mutateAll( translationUnit, pass1 );
  mutateAll( translationUnit, pass2 );
  mutateAll( translationUnit, pass3 );
}

////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////

namespace {

bool
isPolyRet( FunctionType *function, std::string &name, const TyVarMap &otherTyVars )
{
  bool doTransform = false;
  if( !function->get_returnVals().empty() ) {
    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( function->get_returnVals().front()->get_type() ) ) {
    
      // figure out if the return type is specified by a type parameter
      for( std::list< TypeDecl* >::const_iterator tyVar = function->get_forall().begin(); tyVar != function->get_forall().end(); ++tyVar ) {
        if( (*tyVar)->get_name() == typeInst->get_name() ) {
          doTransform = true;
          name = typeInst->get_name();
          break;
        }
      }
      if( !doTransform && otherTyVars.find( typeInst->get_name() ) != otherTyVars.end() ) {
        doTransform = true;
      }
    }
  }
  return doTransform;
}

bool
isPolyRet( FunctionType *function, std::string &name )
{
  TyVarMap dummyTyVars;
  return isPolyRet( function, name, dummyTyVars );
}

Pass1::Pass1()
  : useRetval( false ), tempNamer( "_temp" )
{
}

bool
checkAssignment( DeclarationWithType *decl, std::string &name )
{
  if( decl->get_name() == "?=?" ) {
    if( PointerType *ptrType = dynamic_cast< PointerType* >( decl->get_type() ) ) {
      if( FunctionType *funType = dynamic_cast< FunctionType* >( ptrType->get_base() ) ) {
        if( funType->get_parameters().size() == 2 ) {
          if( PointerType *pointer = dynamic_cast< PointerType* >( funType->get_parameters().front()->get_type() ) ) {
            if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
              name = typeInst->get_name();
              return true;
            }
          }
        }
      }
    }
  }
  return false;
}

void 
Pass1::findAssignOps( const std::list< TypeDecl* > &forall )
{
  assignOps.clear();
  for( std::list< TypeDecl* >::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
    for( std::list< DeclarationWithType* >::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
      std::string typeName;
      if( checkAssignment( *assert, typeName ) ) {
        assignOps[ typeName ] = *assert;
      }
    }
  }
}

DeclarationWithType* 
Pass1::mutate( FunctionDecl *functionDecl )
{
  if( functionDecl->get_statements() ) {
    TyVarMap oldtyVars = scopeTyVars;
    DeclarationWithType *oldRetval = retval;
    bool oldUseRetval = useRetval;
    
    retval = 0;
    std::string typeName;
    if( isPolyRet( functionDecl->get_functionType(), typeName ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
      retval = functionDecl->get_functionType()->get_returnVals().front();
  
      // give names to unnamed return values
      if( retval->get_name() == "" ) {
        retval->set_name( "_retparm" );
        retval->set_linkage( LinkageSpec::C );
      }
    }
    
    scopeTyVars.clear();
///     std::cerr << "clear\n";
    makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
    findAssignOps( functionDecl->get_functionType()->get_forall() );
    functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
  
    scopeTyVars = oldtyVars;
///     std::cerr << "end FunctionDecl: ";
///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
///       std::cerr << i->first << " ";
///     }
///     std::cerr << "\n";
    retval = oldRetval;
    useRetval = oldUseRetval;
    doEndScope();
  }
  return functionDecl;
}

TypeDecl*
Pass1::mutate( TypeDecl *typeDecl )
{
///     std::cerr << "add " << typeDecl->get_name() << "\n";
  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
  return Mutator::mutate( typeDecl );
}

Expression *
Pass1::mutate( CommaExpr *commaExpr )
{
  bool oldUseRetval = useRetval;
  useRetval = false;
  commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
  useRetval = oldUseRetval;
  commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
  return commaExpr;
}

Expression *
Pass1::mutate( ConditionalExpr *condExpr )
{
  bool oldUseRetval = useRetval;
  useRetval = false;
  condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
  useRetval = oldUseRetval;
  condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
  condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
  return condExpr;

}

void
Pass1::passTypeVars( ApplicationExpr* appExpr, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars )
{
  for( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
    ResolvExpr::EqvClass eqvClass;
    assert( env );
    if( tyParm->second == TypeDecl::Any ) {
      Type *concrete = env->lookup( tyParm->first );
      if( concrete ) {
        arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
        arg++;
      } else {
        throw SemanticError( "unbound type variable in application ", appExpr );
      }
    }
  }
}

ObjectDecl*
Pass1::makeTemporary( Type *type )
{
  ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Declaration::NoStorageClass, LinkageSpec::C, 0, type, 0 );
  stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
  return newObj;
}

TypeInstType *
isPolyType( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
{
  if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
    if( env ) {
      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
        return isPolyType( newType, env, tyVars );
      }
    }
    if( tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
      return typeInst;
    } else {
      return 0;
    }
  } else {
    return 0;
  }
}

Expression*
Pass1::addRetParam( ApplicationExpr* appExpr, FunctionType *function, Type *retType, std::list< Expression* >::iterator &arg )
{
  if( useRetval ) {
    assert( retval );
    arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
    arg++;
  } else {
    ObjectDecl *newObj = makeTemporary( retType->clone() );
    Expression *paramExpr = new VariableExpr( newObj );
    if( !isPolyType( newObj->get_type(), env, scopeTyVars ) ) {
      paramExpr = new AddressExpr( paramExpr );
    }
    arg = appExpr->get_args().insert( arg, paramExpr );
    arg++;
///     stmtsToAdd.push_back( new ExprStmt( noLabels, appExpr ) );
    CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
    commaExpr->set_env( appExpr->get_env() );
    appExpr->set_env( 0 );
    return commaExpr;
  }
  return appExpr;
}

Expression*
Pass1::addPolyRetParam( ApplicationExpr* appExpr, FunctionType *function, std::string typeName, std::list< Expression* >::iterator &arg )
{
  ResolvExpr::EqvClass eqvClass;
  assert( env );
  Type *concrete = env->lookup( typeName );
  if( concrete == 0 ) {
    throw SemanticError( "Unbound type variable " + typeName + " in", appExpr );
  }
  return addRetParam( appExpr, function, concrete, arg );
}

Expression*
Pass1::applyAdapter( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars )
{
  Expression *ret = appExpr;
  if( !function->get_returnVals().empty() && isPolyVal( function->get_returnVals().front()->get_type(), tyVars ) ) {
    ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
  }
  appExpr->get_args().push_front( appExpr->get_function() );
  appExpr->set_function( new NameExpr( "_adapter" + SymTab::Mangler::mangle( function ) ) );
  
  return ret;
}

void
Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars )
{
  assert( !arg->get_results().empty() );
///   if( !dynamic_cast< PointerType* >( arg->get_results().front() ) ) {
    TypeInstType *typeInst = dynamic_cast< TypeInstType* >( param );
    if( typeInst && exprTyVars.find( typeInst->get_name() ) != exprTyVars.end() ) {
      if( arg->get_results().front()->get_isLvalue() ) {
        arg = new AddressExpr( arg );
      } else {
        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), Declaration::NoStorageClass, LinkageSpec::C, 0, arg->get_results().front()->clone(), 0 );
        newObj->get_type()->get_qualifiers() = Type::Qualifiers();
        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
        UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
        assign->get_args().push_back( new VariableExpr( newObj ) );
        assign->get_args().push_back( arg );
        stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
        arg = new AddressExpr( new VariableExpr( newObj ) );
      }
    }
///   }
}

void
addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars )
{
  Type *newType = formal->clone();
  std::list< FunctionType* > functions;
  // instead of functions needing adapters, this really ought to look for
  // any function mentioning a polymorphic type
  findAndReplaceFunction( newType, functions, tyVars, needsAdapter );
  if( !functions.empty() ) {
    actual = new CastExpr( actual, newType );
  } else {
    delete newType;
  }
}

void
Pass1::boxParams( ApplicationExpr* appExpr, FunctionType *function, std::list< Expression* >::iterator &arg, const TyVarMap &exprTyVars )
{
///   std::cout << "function is ";
///   function->print( std::cout );
  for( std::list< DeclarationWithType* >::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
///     std::cout << "parameter is ";
///     (*param)->print( std::cout );
///     std::cout << std::endl << "argument is ";
///     (*arg)->print( std::cout );
    assert( arg != appExpr->get_args().end() );
    addCast( *arg, (*param)->get_type(), exprTyVars );
    boxParam( (*param)->get_type(), *arg, exprTyVars );
  }
}

void
Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression* >::iterator &arg, const TyVarMap &tyVars )
{
  std::list< Expression* >::iterator cur = arg;
  for( std::list< TypeDecl* >::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
    for( std::list< DeclarationWithType* >::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
      InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
      assert( inferParam != appExpr->get_inferParams().end() );
      Expression *newExpr = inferParam->second.expr->clone();
      addCast( newExpr, (*assert)->get_type(), tyVars );
      boxParam( (*assert)->get_type(), newExpr, tyVars );
      appExpr->get_args().insert( cur, newExpr );
    }
  }
}

void
makeRetParm( FunctionType *funcType )
{
  DeclarationWithType *retParm = funcType->get_returnVals().front();

  // make a new parameter that is a pointer to the type of the old return value
  retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
  funcType->get_parameters().push_front( retParm );

  // we don't need the return value any more
  funcType->get_returnVals().clear();
}

FunctionType *
makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars )
{
  // actually make the adapter type
  FunctionType *adapter = adaptee->clone();
  if( !adapter->get_returnVals().empty() && isPolyVal( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
    makeRetParm( adapter );
  }
  adapter->get_parameters().push_front( new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
  return adapter;
}

Expression*
makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars )
{
  assert( param );
  assert( arg );
///   std::cout << "arg type is ";
///   arg->get_type()->print( std::cout );
///   std::cout << "param type is ";
///   param->get_type()->print( std::cout );
///   std::cout << " tyVars are: ";
///   printTyVarMap( std::cout, tyVars );
  if( isPolyVal( realParam->get_type(), tyVars ) ) {
///     if( dynamic_cast< PointerType* >( arg->get_type() ) ) {
///       return new CastExpr( new VariableExpr( param ), arg->get_type()->clone() );
///     } else {
      UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
      deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
      deref->get_results().push_back( arg->get_type()->clone() );
      return deref;
///     }
  }
  return new VariableExpr( param );
}

void
addAdapterParams( ApplicationExpr *adapteeApp, std::list< DeclarationWithType* >::iterator arg, std::list< DeclarationWithType* >::iterator param, std::list< DeclarationWithType* >::iterator paramEnd, std::list< DeclarationWithType* >::iterator realParam, const TyVarMap &tyVars )
{
  UniqueName paramNamer( "_p" );
  for( ; param != paramEnd; ++param, ++arg, ++realParam ) {
    if( (*param)->get_name() == "" ) {
      (*param)->set_name( paramNamer.newName() );
      (*param)->set_linkage( LinkageSpec::C );
    }
    adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
  }
}

FunctionDecl *
Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars )
{
  FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
  adapterType = ScrubTyVars::scrub( adapterType, tyVars );
  DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
  adapteeDecl->set_name( "_adaptee" );
  ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
  Statement *bodyStmt;
  
  std::list< TypeDecl* >::iterator tyArg = realType->get_forall().begin();
  std::list< TypeDecl* >::iterator tyParam = adapterType->get_forall().begin();
  std::list< TypeDecl* >::iterator realTyParam = adaptee->get_forall().begin();
  for( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
    assert( tyArg != realType->get_forall().end() );
    std::list< DeclarationWithType* >::iterator assertArg = (*tyArg)->get_assertions().begin();
    std::list< DeclarationWithType* >::iterator assertParam = (*tyParam)->get_assertions().begin();
    std::list< DeclarationWithType* >::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
    for( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
      assert( assertArg != (*tyArg)->get_assertions().end() );
      adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
    }
  }
  
  std::list< DeclarationWithType* >::iterator arg = realType->get_parameters().begin();
  std::list< DeclarationWithType* >::iterator param = adapterType->get_parameters().begin();
  std::list< DeclarationWithType* >::iterator realParam = adaptee->get_parameters().begin();
  param++;              // skip adaptee parameter
  if( realType->get_returnVals().empty() ) {
    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
    bodyStmt = new ExprStmt( noLabels, adapteeApp );
  } else if( isPolyVal( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
    if( (*param)->get_name() == "" ) {
      (*param)->set_name( "_ret" );
      (*param)->set_linkage( LinkageSpec::C );
    }
    UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
    UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
    deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
    assign->get_args().push_back( deref );
    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
    assign->get_args().push_back( adapteeApp );
    bodyStmt = new ExprStmt( noLabels, assign );
  } else {
    // adapter for a function that returns a monomorphic value
    addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
    bodyStmt = new ReturnStmt( noLabels, adapteeApp );
  }
  CompoundStmt *adapterBody = new CompoundStmt( noLabels );
  adapterBody->get_kids().push_back( bodyStmt );
  return new FunctionDecl( "_adapter" + mangleName, Declaration::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false );
}

void
Pass1::passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars )
{
  std::list< DeclarationWithType* > &paramList = functionType->get_parameters();
  std::list< FunctionType* > functions;
  for( std::list< TypeDecl* >::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
    for( std::list< DeclarationWithType* >::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
      findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
    }
  }
  for( std::list< DeclarationWithType* >::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
    findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
  }
  std::set< std::string > adaptersDone;
  for( std::list< FunctionType* >::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
    FunctionType *realFunction = (*funType)->clone();
    assert( env );
    env->apply( realFunction );
    std::string mangleName = SymTab::Mangler::mangle( realFunction );
    if( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
      std::map< std::string, FunctionDecl* >::iterator adapter = adapters.find( mangleName );
      if( adapter == adapters.end() ) {
        FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
        adapter = adapters.insert( adapters.begin(), std::pair< std::string, FunctionDecl* >( mangleName, newAdapter ) );
        stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
      }
      assert( adapter != adapters.end() );
      appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
      adaptersDone.insert( adaptersDone.begin(), mangleName );
    }
  }
}

TypeInstType*
isPolyPtr( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
{
  if( PointerType *ptr = dynamic_cast< PointerType* >( type ) ) {
    return isPolyType( ptr->get_base(), env, tyVars );
  } else if( env ) {
    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
        return isPolyPtr( newType, env, tyVars );
      }
    }
  }
  return 0;
}

TypeInstType*
isPolyPtrPtr( Type *type, const TypeSubstitution *env, const TyVarMap &tyVars )
{
  if( PointerType *ptr = dynamic_cast< PointerType* >( type ) ) {
    return isPolyPtr( ptr->get_base(), env, tyVars );
  } else if( env ) {
    if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
      if( Type *newType = env->lookup( typeInst->get_name() ) ) {
        return isPolyPtrPtr( newType, env, tyVars );
      }
    }
  }
  return 0;
}

Expression *
makeIncrDecrExpr( ApplicationExpr *appExpr, std::string polyName, bool isIncr )
{
  NameExpr *opExpr;
  if( isIncr ) {
    opExpr = new NameExpr( "?+=?" );
  } else {
    opExpr = new NameExpr( "?-=?" );
  }
  UntypedExpr *addAssign = new UntypedExpr( opExpr );
  if( AddressExpr *address = dynamic_cast< AddressExpr* >( appExpr->get_args().front() ) ) {
    addAssign->get_args().push_back( address->get_arg() );
  } else {
    addAssign->get_args().push_back( appExpr->get_args().front() );
  }
  addAssign->get_args().push_back( new NameExpr( polyName ) );
  addAssign->get_results().front() = appExpr->get_results().front()->clone();
  if( appExpr->get_env() ) {
    addAssign->set_env( appExpr->get_env() );
    appExpr->set_env( 0 );
  }
  appExpr->get_args().clear();
  delete appExpr;
  return addAssign;
}

Expression*
Pass1::handleIntrinsics( ApplicationExpr *appExpr )
{
  if( VariableExpr *varExpr = dynamic_cast< VariableExpr* >( appExpr->get_function() ) ) {
    if( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
      if( varExpr->get_var()->get_name() == "?[?]" ) {
        assert( !appExpr->get_results().empty() );
        assert( appExpr->get_args().size() == 2 );
        TypeInstType *typeInst1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), env, scopeTyVars );
        TypeInstType *typeInst2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), env, scopeTyVars );
        assert( !typeInst1 || !typeInst2 );
        UntypedExpr *ret = 0;
        if( typeInst1 || typeInst2 ) {
          ret = new UntypedExpr( new NameExpr( "?+?" ) );
        }
        if( typeInst1 ) {
          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
          multiply->get_args().push_back( appExpr->get_args().back() );
          multiply->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
          ret->get_args().push_back( appExpr->get_args().front() );
          ret->get_args().push_back( multiply );
        } else if( typeInst2 ) {
          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
          multiply->get_args().push_back( appExpr->get_args().front() );
          multiply->get_args().push_back( new NameExpr( typeInst2->get_name() ) );
          ret->get_args().push_back( multiply );
          ret->get_args().push_back( appExpr->get_args().back() );
        }
        if( typeInst1 || typeInst2 ) {
          ret->get_results().push_front( appExpr->get_results().front()->clone() );
          if( appExpr->get_env() ) {
            ret->set_env( appExpr->get_env() );
            appExpr->set_env( 0 );
          }
          appExpr->get_args().clear();
          delete appExpr;
          return ret;
        }
      } else if( varExpr->get_var()->get_name() == "*?" ) {
        assert( !appExpr->get_results().empty() );
        assert( !appExpr->get_args().empty() );
        if( isPolyType( appExpr->get_results().front(), env, scopeTyVars ) ) {
          Expression *ret = appExpr->get_args().front();
          delete ret->get_results().front();
          ret->get_results().front() = appExpr->get_results().front()->clone();
          if( appExpr->get_env() ) {
            ret->set_env( appExpr->get_env() );
            appExpr->set_env( 0 );
          }
          appExpr->get_args().clear();
          delete appExpr;
          return ret;
        }
      } else if( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
        assert( !appExpr->get_results().empty() );
        assert( appExpr->get_args().size() == 1 );
        if( TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars ) ) {
          Type *tempType = appExpr->get_results().front()->clone();
          if( env ) {
            env->apply( tempType );
          }
          ObjectDecl *newObj = makeTemporary( tempType );
          VariableExpr *tempExpr = new VariableExpr( newObj );
          UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
          assignExpr->get_args().push_back( tempExpr->clone() );
          if( AddressExpr *address = dynamic_cast< AddressExpr* >( appExpr->get_args().front() ) ) {
            assignExpr->get_args().push_back( address->get_arg()->clone() );
          } else {
            assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
          }
          CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, typeInst->get_name(), varExpr->get_var()->get_name() == "?++" ) );
          return new CommaExpr( firstComma, tempExpr );
        }
      } else if( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
        assert( !appExpr->get_results().empty() );
        assert( appExpr->get_args().size() == 1 );
        if( TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars ) ) {
           return makeIncrDecrExpr( appExpr, typeInst->get_name(), varExpr->get_var()->get_name() == "++?" );
        }
      } else if( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
        assert( !appExpr->get_results().empty() );
        assert( appExpr->get_args().size() == 2 );
        TypeInstType *typeInst1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), env, scopeTyVars );
        TypeInstType *typeInst2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), env, scopeTyVars );
        if( typeInst1 && typeInst2 ) {
          UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
          divide->get_args().push_back( appExpr );
          divide->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
          divide->get_results().push_front( appExpr->get_results().front()->clone() );
          if( appExpr->get_env() ) {
            divide->set_env( appExpr->get_env() );
            appExpr->set_env( 0 );
          }
          return divide;
        } else if( typeInst1 ) {
          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
          multiply->get_args().push_back( appExpr->get_args().back() );
          multiply->get_args().push_back( new NameExpr( typeInst1->get_name() ) );
          appExpr->get_args().back() = multiply;
        } else if( typeInst2 ) {
          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
          multiply->get_args().push_back( appExpr->get_args().front() );
          multiply->get_args().push_back( new NameExpr( typeInst2->get_name() ) );
          appExpr->get_args().front() = multiply;
        }
      } else if( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
        assert( !appExpr->get_results().empty() );
        assert( appExpr->get_args().size() == 2 );
        TypeInstType *typeInst = isPolyPtr( appExpr->get_results().front(), env, scopeTyVars );
        if( typeInst ) {
          UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
          multiply->get_args().push_back( appExpr->get_args().back() );
          multiply->get_args().push_back( new NameExpr( typeInst->get_name() ) );
          appExpr->get_args().back() = multiply;
        }
      }
      return appExpr;
    }
  }
  return 0;
}

Expression*
Pass1::mutate( ApplicationExpr *appExpr )
{
///     std::cerr << "mutate appExpr: ";
///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
///       std::cerr << i->first << " ";
///     }
///     std::cerr << "\n";
  bool oldUseRetval = useRetval;
  useRetval = false;
  appExpr->get_function()->acceptMutator( *this );
  mutateAll( appExpr->get_args(), *this );
  useRetval = oldUseRetval;
  
  assert( !appExpr->get_function()->get_results().empty() );
  PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
  assert( pointer );
  FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
  assert( function );
  
  if( Expression *newExpr = handleIntrinsics( appExpr ) ) {
    return newExpr;
  }
  
  Expression *ret = appExpr;
  
  std::list< Expression* >::iterator arg = appExpr->get_args().begin();
  std::list< Expression* >::iterator paramBegin = appExpr->get_args().begin();
  
  std::string typeName;
  if( isPolyRet( function, typeName ) ) {
    ret = addPolyRetParam( appExpr, function, typeName, arg );
  } else if( needsAdapter( function, scopeTyVars ) ) {
///     std::cerr << "needs adapter: ";
///     for( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
///       std::cerr << i->first << " ";
///     }
///     std::cerr << "\n";
    // change the application so it calls the adapter rather than the passed function
    ret = applyAdapter( appExpr, function, arg, scopeTyVars );
  }
  arg = appExpr->get_args().begin();
  
  TyVarMap exprTyVars;
  makeTyVarMap( function, exprTyVars );
  
  passTypeVars( appExpr, arg, exprTyVars );
  addInferredParams( appExpr, function, arg, exprTyVars );

  arg = paramBegin;
  
  boxParams( appExpr, function, arg, exprTyVars );

  passAdapters( appExpr, function, exprTyVars );

  return ret;
}

Expression *
Pass1::mutate( UntypedExpr *expr )
{
  if( !expr->get_results().empty() && isPolyType( expr->get_results().front(), env, scopeTyVars ) ) {
    if( NameExpr *name = dynamic_cast< NameExpr* >( expr->get_function() ) ) {
      if( name->get_name() == "*?" ) {
        Expression *ret = expr->get_args().front();
        expr->get_args().clear();
        delete expr;
        return ret->acceptMutator( *this );
      }
    }
  }
  return PolyMutator::mutate( expr );
}

Expression *
Pass1::mutate( AddressExpr *addrExpr )
{
  assert( !addrExpr->get_arg()->get_results().empty() );
  mutateExpression( addrExpr->get_arg() );
  if( isPolyType( addrExpr->get_arg()->get_results().front(), env, scopeTyVars ) ) {
    Expression *ret = addrExpr->get_arg();
    delete ret->get_results().front();
    ret->get_results().front() = addrExpr->get_results().front()->clone();
    addrExpr->set_arg( 0 );
    delete addrExpr;
    return ret;
  } else {
    return addrExpr;
  }
}

Statement* 
Pass1::mutate(ReturnStmt *retStmt)
{
  // a cast expr on a polymorphic return value is either redundant or invalid
  while( CastExpr *castExpr = dynamic_cast< CastExpr* >( retStmt->get_expr() ) ) {
    retStmt->set_expr( castExpr->get_arg() );
    retStmt->get_expr()->set_env( castExpr->get_env() );
    castExpr->set_env( 0 );
    castExpr->set_arg( 0 );
    delete castExpr;
  }
  if( retval && retStmt->get_expr() ) {
    assert( !retStmt->get_expr()->get_results().empty() );
    if( retStmt->get_expr()->get_results().front()->get_isLvalue() ) {
///       retStmt->set_expr( mutateExpression( retStmt->get_expr() ) );
      TypeInstType *typeInst = dynamic_cast< TypeInstType* >( retval->get_type() );
      assert( typeInst );
      std::map< std::string, DeclarationWithType* >::const_iterator assignIter = assignOps.find( typeInst->get_name() );
      if( assignIter == assignOps.end() ) {
        throw SemanticError( "Attempt to return dtype or ftype object in ", retStmt->get_expr() );
      }
      ApplicationExpr *assignExpr = new ApplicationExpr( new VariableExpr( assignIter->second ) );
      Expression *retParm = new NameExpr( retval->get_name() );
      retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
      assignExpr->get_args().push_back( retParm );
      assignExpr->get_args().push_back( retStmt->get_expr() );
      stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
    } else {
      useRetval = true;
      stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( retStmt->get_expr() ) ) );
      useRetval = false;
    }
    retStmt->set_expr( 0 );
  } else {
    retStmt->set_expr( mutateExpression( retStmt->get_expr() ) );
  }
  return retStmt;
}

Type* 
Pass1::mutate( PointerType *pointerType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( pointerType, scopeTyVars );
  
  Type* ret = Mutator::mutate( pointerType );
  
  scopeTyVars = oldtyVars;
  return ret;
}

Type* 
Pass1::mutate( FunctionType *functionType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( functionType, scopeTyVars );
  
  Type* ret = Mutator::mutate( functionType );
  
  scopeTyVars = oldtyVars;
  return ret;
}

void
Pass1::doEndScope()
{
  adapters.clear();
}

////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////

Pass2::Pass2()
{
}

void 
Pass2::addAdapters( FunctionType *functionType )
{
  std::list< DeclarationWithType* > &paramList = functionType->get_parameters();
  std::list< FunctionType* > functions;
  for( std::list< DeclarationWithType* >::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
    Type *orig = (*arg)->get_type();
    findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
    (*arg)->set_type( orig );
  }
  std::set< std::string > adaptersDone;
  for( std::list< FunctionType* >::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
    std::string mangleName = SymTab::Mangler::mangle( *funType );
    if( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
      paramList.push_front( new ObjectDecl( "_adapter" + mangleName, Declaration::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
      adaptersDone.insert( adaptersDone.begin(), mangleName );
    }
  }
///  deleteAll( functions );
}

template< typename DeclClass >
DeclClass* 
Pass2::handleDecl( DeclClass *decl, Type *type )
{
  DeclClass *ret = static_cast< DeclClass* >( Mutator::mutate( decl ) );

  return ret;
}

DeclarationWithType* 
Pass2::mutate( FunctionDecl *functionDecl )
{
  return handleDecl( functionDecl, functionDecl->get_functionType() );
}

ObjectDecl* 
Pass2::mutate( ObjectDecl *objectDecl )
{
  return handleDecl( objectDecl, objectDecl->get_type() );
}

TypeDecl* 
Pass2::mutate( TypeDecl *typeDecl )
{
  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
  if( typeDecl->get_base() ) {
    return handleDecl( typeDecl, typeDecl->get_base() );
  } else {
    return Mutator::mutate( typeDecl );
  }
}

TypedefDecl* 
Pass2::mutate( TypedefDecl *typedefDecl )
{
  return handleDecl( typedefDecl, typedefDecl->get_base() );
}

Type* 
Pass2::mutate( PointerType *pointerType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( pointerType, scopeTyVars );
  
  Type* ret = Mutator::mutate( pointerType );
  
  scopeTyVars = oldtyVars;
  return ret;
}

Type *
Pass2::mutate( FunctionType *funcType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( funcType, scopeTyVars );
  
  std::string typeName;
  if( isPolyRet( funcType, typeName ) ) {
    DeclarationWithType *ret = funcType->get_returnVals().front();
    ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
    funcType->get_parameters().push_front( ret );
    funcType->get_returnVals().pop_front();
  }
  
  std::list< DeclarationWithType* >::iterator last = funcType->get_parameters().begin();
  std::list< DeclarationWithType* > inferredParams;
  ObjectDecl *newObj = new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
///   ObjectDecl *newFunPtr = new ObjectDecl( "", Declaration::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
  for( std::list< TypeDecl* >::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
    ObjectDecl *thisParm;
    if( (*tyParm)->get_kind() == TypeDecl::Any ) {
      thisParm = newObj->clone();
      thisParm->set_name( (*tyParm)->get_name() );
      last = funcType->get_parameters().insert( last, thisParm );
      ++last;
    }
    for( std::list< DeclarationWithType* >::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
///       *assert = (*assert)->acceptMutator( *this );
      inferredParams.push_back( *assert );
    }
    (*tyParm)->get_assertions().clear();
  }
  delete newObj;
  funcType->get_parameters().splice( last, inferredParams );
  addAdapters( funcType );
  mutateAll( funcType->get_returnVals(), *this );
  mutateAll( funcType->get_parameters(), *this );
  
  scopeTyVars = oldtyVars;
  return funcType;
}

////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////

template< typename DeclClass >
DeclClass* 
Pass3::handleDecl( DeclClass *decl, Type *type )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( type, scopeTyVars );
  
  DeclClass *ret = static_cast< DeclClass* >( Mutator::mutate( decl ) );
  ScrubTyVars::scrub( decl, scopeTyVars );

  scopeTyVars = oldtyVars;
  return ret;
}

ObjectDecl* 
Pass3::mutate( ObjectDecl *objectDecl )
{
  return handleDecl( objectDecl, objectDecl->get_type() );
}

DeclarationWithType* 
Pass3::mutate( FunctionDecl *functionDecl )
{
  return handleDecl( functionDecl, functionDecl->get_functionType() );
}

TypedefDecl* 
Pass3::mutate( TypedefDecl *typedefDecl )
{
  return handleDecl( typedefDecl, typedefDecl->get_base() );
}

TypeDecl* 
Pass3::mutate( TypeDecl *typeDecl )
{
///   Initializer *init = 0;
///   std::list< Expression *> designators;
///   scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
///   if( typeDecl->get_base() ) {
///     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
///   }
///   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );

  scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
  return Mutator::mutate( typeDecl );
}

Type* 
Pass3::mutate( PointerType *pointerType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( pointerType, scopeTyVars );
  
  Type* ret = Mutator::mutate( pointerType );
  
  scopeTyVars = oldtyVars;
  return ret;
}

Type* 
Pass3::mutate( FunctionType *functionType )
{
  TyVarMap oldtyVars = scopeTyVars;
  makeTyVarMap( functionType, scopeTyVars );
  
  Type* ret = Mutator::mutate( functionType );
  
  scopeTyVars = oldtyVars;
  return ret;
}

Statement*
Pass3::mutate( DeclStmt *declStmt )
{
  if( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( declStmt->get_decl() ) ) {
    if( isPolyVal( objectDecl->get_type(), scopeTyVars ) ) {
      TypeInstType *typeInst = dynamic_cast< TypeInstType* >( objectDecl->get_type() );
      assert( typeInst );
      UntypedExpr *alloc = new UntypedExpr( new NameExpr( "alloca" ) );
      alloc->get_args().push_back( new NameExpr( typeInst->get_name() ) );
      UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
      assign->get_args().push_back( new VariableExpr( objectDecl ) );
      assign->get_args().push_back( alloc );
      stmtsToAddAfter.push_back( new ExprStmt( noLabels, assign ) );
    }
  }
  return Mutator::mutate( declStmt );
}
    
} // anonymous namespace

} // namespace GenPoly