source: src/GenPoly/Box.cc @ b10c9959

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newstringwith_gc
Last change on this file since b10c9959 was b10c9959, checked in by Aaron Moss <a3moss@…>, 9 years ago

First draft of fixing polymorphic generic return types
  • Property mode set to 100644
File size: 66.5 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Box.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Rob Schluntz
12// Last Modified On : Fri Dec 18 14:53:08 2015
13// Update Count     : 217
14//
15
16#include <set>
17#include <stack>
18#include <string>
19#include <iterator>
20#include <algorithm>
21#include <cassert>
22
23#include "Box.h"
24#include "InstantiateGeneric.h"
25#include "PolyMutator.h"
26#include "FindFunction.h"
27#include "ScopedMap.h"
28#include "ScrubTyVars.h"
29
30#include "Parser/ParseNode.h"
31
32#include "SynTree/Constant.h"
33#include "SynTree/Type.h"
34#include "SynTree/Expression.h"
35#include "SynTree/Initializer.h"
36#include "SynTree/Statement.h"
37#include "SynTree/Mutator.h"
38
39#include "ResolvExpr/TypeEnvironment.h"
40
41#include "SymTab/Mangler.h"
42
43#include "Common/SemanticError.h"
44#include "Common/UniqueName.h"
45#include "Common/utility.h"
46
47#include <ext/functional> // temporary
48
49namespace GenPoly {
50        namespace {
51                const std::list<Label> noLabels;
52
53                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
54
55                /// Replaces polymorphic return types with out-parameters, replaces calls to polymorphic functions with adapter calls as needed, and adds appropriate type variables to the function call
56                class Pass1 : public PolyMutator {
57                  public:
58                        Pass1();
59                        virtual Expression *mutate( ApplicationExpr *appExpr );
60                        virtual Expression *mutate( AddressExpr *addrExpr );
61                        virtual Expression *mutate( UntypedExpr *expr );
62                        virtual DeclarationWithType* mutate( FunctionDecl *functionDecl );
63                        virtual TypeDecl *mutate( TypeDecl *typeDecl );
64                        virtual Expression *mutate( CommaExpr *commaExpr );
65                        virtual Expression *mutate( ConditionalExpr *condExpr );
66                        virtual Statement * mutate( ReturnStmt *returnStmt );
67                        virtual Type *mutate( PointerType *pointerType );
68                        virtual Type * mutate( FunctionType *functionType );
69
70                        virtual void doBeginScope();
71                        virtual void doEndScope();
72                  private:
73                        /// Makes a new temporary array holding the offsets of the fields of `type`, and returns a new variable expression referencing it
74                        Expression *makeOffsetArray( StructInstType *type );
75                        /// passes extra type parameters into a polymorphic function application
76                        void passTypeVars( ApplicationExpr *appExpr, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
77                        /// wraps a function application with a new temporary for the out-parameter return value
78                        Expression *addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg );
79                        /// Replaces all the type parameters of a generic type with their concrete equivalents under the current environment
80                        void replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params );
81                        /// Replaces a polymorphic type with its concrete equivalant under the current environment (returns itself if concrete).
82                        /// If `doClone` is set to false, will not clone interior types
83                        Type *replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone = true );
84                        /// wraps a function application returning a polymorphic type with a new temporary for the out-parameter return value
85                        Expression *addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg );
86                        Expression *applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
87                        void boxParam( Type *formal, Expression *&arg, const TyVarMap &exprTyVars );
88                        void boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars );
89                        void addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars );
90                        /// Stores assignment operators from assertion list in local map of assignment operations
91                        void findAssignOps( const std::list< TypeDecl *> &forall );
92                        void passAdapters( ApplicationExpr *appExpr, FunctionType *functionType, const TyVarMap &exprTyVars );
93                        FunctionDecl *makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars );
94                        /// Replaces intrinsic operator functions with their arithmetic desugaring
95                        Expression *handleIntrinsics( ApplicationExpr *appExpr );
96                        /// Inserts a new temporary variable into the current scope with an auto-generated name
97                        ObjectDecl *makeTemporary( Type *type );
98
99                        typedef std::map< std::string, DeclarationWithType *> AdapterMap;
100                        std::map< std::string, DeclarationWithType *> assignOps;
101                        ScopedMap< std::string, DeclarationWithType *> scopedAssignOps;
102                        std::stack< AdapterMap > adapters;
103                        DeclarationWithType *retval;
104                        bool useRetval;
105                        UniqueName tempNamer;
106                };
107
108                /// Moves polymorphic returns in function types to pointer-type parameters, adds type size and assertion parameters to parameter lists as well
109                class Pass2 : public PolyMutator {
110                  public:
111                        template< typename DeclClass >
112                        DeclClass *handleDecl( DeclClass *decl, Type *type );
113                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
114                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
115                        virtual TypeDecl *mutate( TypeDecl *typeDecl );
116                        virtual TypedefDecl *mutate( TypedefDecl *typedefDecl );
117                        virtual Type *mutate( PointerType *pointerType );
118                        virtual Type *mutate( FunctionType *funcType );
119                  private:
120                        void addAdapters( FunctionType *functionType );
121
122                        std::map< UniqueId, std::string > adapterName;
123                };
124
125                /// Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference;
126                /// also fixes offsetof expressions.
127                class MemberExprFixer : public PolyMutator {
128                  public:
129                        template< typename DeclClass >
130                        DeclClass *handleDecl( DeclClass *decl, Type *type );
131                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
132                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
133                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl );
134                        virtual TypeDecl *mutate( TypeDecl *objectDecl );
135                        virtual Statement *mutate( DeclStmt *declStmt );
136                        virtual Type *mutate( PointerType *pointerType );
137                        virtual Type *mutate( FunctionType *funcType );
138                        virtual Expression *mutate( MemberExpr *memberExpr );
139                        virtual Expression *mutate( OffsetofExpr *offsetofExpr );
140                };
141               
142                /// Replaces initialization of polymorphic values with alloca, declaration of dtype/ftype with appropriate void expression, and sizeof expressions of polymorphic types with the proper variable
143                class Pass3 : public PolyMutator {
144                  public:
145                        template< typename DeclClass >
146                        DeclClass *handleDecl( DeclClass *decl, Type *type );
147                        virtual DeclarationWithType *mutate( FunctionDecl *functionDecl );
148                        virtual ObjectDecl *mutate( ObjectDecl *objectDecl );
149                        virtual TypedefDecl *mutate( TypedefDecl *objectDecl );
150                        virtual TypeDecl *mutate( TypeDecl *objectDecl );
151                        virtual Type *mutate( PointerType *pointerType );
152                        virtual Type *mutate( FunctionType *funcType );
153                  private:
154                };
155
156        } // anonymous namespace
157
158        void printAllNotBuiltin( const std::list< Declaration *>& translationUnit, std::ostream &os ) {
159                for ( std::list< Declaration *>::const_iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
160                        if ( ! LinkageSpec::isBuiltin( (*i)->get_linkage() ) ) {
161                                (*i)->print( os );
162                                os << std::endl;
163                        } // if
164                } // for
165        }
166
167        /// version of mutateAll with special handling for translation unit so you can check the end of the prelude when debugging
168        template< typename MutatorType >
169        inline void mutateTranslationUnit( std::list< Declaration* > &translationUnit, MutatorType &mutator ) {
170                bool seenIntrinsic = false;
171                SemanticError errors;
172                for ( typename std::list< Declaration* >::iterator i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
173                        try {
174                                if ( *i ) {
175                                        if ( (*i)->get_linkage() == LinkageSpec::Intrinsic ) {
176                                                seenIntrinsic = true;
177                                        } else if ( seenIntrinsic ) {
178                                                seenIntrinsic = false; // break on this line when debugging for end of prelude
179                                        }
180                                       
181                                        *i = dynamic_cast< Declaration* >( (*i)->acceptMutator( mutator ) );
182                                        assert( *i );
183                                } // if
184                        } catch( SemanticError &e ) {
185                                errors.append( e );
186                        } // try
187                } // for
188                if ( ! errors.isEmpty() ) {
189                        throw errors;
190                } // if
191        }
192
193        void box( std::list< Declaration *>& translationUnit ) {
194                Pass1 pass1;
195                Pass2 pass2;
196                MemberExprFixer memberFixer;
197                Pass3 pass3;
198                mutateTranslationUnit/*All*/( translationUnit, pass1 );
199                mutateTranslationUnit/*All*/( translationUnit, pass2 );
200                instantiateGeneric( translationUnit );
201                mutateTranslationUnit/*All*/( translationUnit, memberFixer );
202                mutateTranslationUnit/*All*/( translationUnit, pass3 );
203        }
204
205        ////////////////////////////////////////// Pass1 ////////////////////////////////////////////////////
206
207        namespace {
208                std::string makePolyMonoSuffix( FunctionType * function, const TyVarMap &tyVars ) {
209                        std::stringstream name;
210
211                        // NOTE: this function previously used isPolyObj, which failed to produce
212                        // the correct thing in some situations. It's not clear to me why this wasn't working.
213
214                        // if the return type or a parameter type involved polymorphic types, then the adapter will need
215                        // to take those polymorphic types as pointers. Therefore, there can be two different functions
216                        // with the same mangled name, so we need to further mangle the names.
217                        for ( std::list< DeclarationWithType *>::iterator retval = function->get_returnVals().begin(); retval != function->get_returnVals().end(); ++retval ) {
218                                if ( isPolyType( (*retval)->get_type(), tyVars ) ) {
219                                        name << "P";
220                                } else {
221                                        name << "M";
222                                }
223                        }
224                        name << "_";
225                        std::list< DeclarationWithType *> &paramList = function->get_parameters();
226                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
227                                if ( isPolyType( (*arg)->get_type(), tyVars ) ) {
228                                        name << "P";
229                                } else {
230                                        name << "M";
231                                }
232                        } // for
233                        return name.str();
234                }
235
236                std::string mangleAdapterName( FunctionType * function, const TyVarMap &tyVars ) {
237                        return SymTab::Mangler::mangle( function ) + makePolyMonoSuffix( function, tyVars );
238                }
239
240                std::string makeAdapterName( const std::string &mangleName ) {
241                        return "_adapter" + mangleName;
242                }
243
244                Pass1::Pass1() : useRetval( false ), tempNamer( "_temp" ) {
245                        adapters.push(AdapterMap());
246                }
247
248                /// returns T if the given declaration is: (*?=?)(T *, T) for some T (return not checked, but maybe should be), NULL otherwise
249                ReferenceToType *isAssignment( DeclarationWithType *decl ) {
250                        if ( decl->get_name() == "?=?" ) {
251                                if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) {
252                                        if ( funType->get_parameters().size() == 2 ) {
253                                                if ( PointerType *pointer = dynamic_cast< PointerType *>( funType->get_parameters().front()->get_type() ) ) {
254                                                        if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( pointer->get_base() ) ) {
255                                                                if ( ReferenceToType *refType2 = dynamic_cast< ReferenceToType *>( funType->get_parameters().back()->get_type() ) ) {
256                                                                        if ( refType->get_name() == refType2->get_name() ) {
257                                                                                return refType;
258                                                                        } // if
259                                                                } // if
260                                                        } // if
261                                                } // if
262                                        } // if
263                                } // if
264                        } // if
265                        return 0;
266                }
267
268                void Pass1::findAssignOps( const std::list< TypeDecl *> &forall ) {
269                        // what if a nested function uses an assignment operator?
270                        // assignOps.clear();
271                        for ( std::list< TypeDecl *>::const_iterator i = forall.begin(); i != forall.end(); ++i ) {
272                                for ( std::list< DeclarationWithType *>::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) {
273                                        std::string typeName;
274                                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( isAssignment( *assert ) ) ) {
275                                                assignOps[ typeInst->get_name() ] = *assert;
276                                        } // if
277                                } // for
278                        } // for
279                }
280
281                DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) {
282                        // if this is a polymorphic assignment function, put it in the map for this scope
283                        if ( ReferenceToType *refType = isAssignment( functionDecl ) ) {
284                                if ( ! dynamic_cast< TypeInstType* >( refType ) ) {
285                                        scopedAssignOps.insert( refType->get_name(), functionDecl );
286                                }
287                        }
288                       
289                        if ( functionDecl->get_statements() ) {         // empty routine body ?
290                                doBeginScope();
291                                TyVarMap oldtyVars = scopeTyVars;
292                                std::map< std::string, DeclarationWithType *> oldassignOps = assignOps;
293                                DeclarationWithType *oldRetval = retval;
294                                bool oldUseRetval = useRetval;
295
296                                // process polymorphic return value
297                                retval = 0;
298                                if ( isPolyRet( functionDecl->get_functionType() ) && functionDecl->get_linkage() == LinkageSpec::Cforall ) {
299                                        retval = functionDecl->get_functionType()->get_returnVals().front();
300
301                                        // give names to unnamed return values
302                                        if ( retval->get_name() == "" ) {
303                                                retval->set_name( "_retparm" );
304                                                retval->set_linkage( LinkageSpec::C );
305                                        } // if
306                                } // if
307
308                                FunctionType *functionType = functionDecl->get_functionType();
309                                makeTyVarMap( functionDecl->get_functionType(), scopeTyVars );
310                                findAssignOps( functionDecl->get_functionType()->get_forall() );
311
312                                std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
313                                std::list< FunctionType *> functions;
314                                for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
315                                        for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
316                                                findFunction( (*assert)->get_type(), functions, scopeTyVars, needsAdapter );
317                                        } // for
318                                } // for
319                                for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
320                                        findFunction( (*arg)->get_type(), functions, scopeTyVars, needsAdapter );
321                                } // for
322                               
323                                AdapterMap & adapters = Pass1::adapters.top();
324                                for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
325                                        std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
326                                        if ( adapters.find( mangleName ) == adapters.end() ) {
327                                                std::string adapterName = makeAdapterName( mangleName );
328                                                adapters.insert( std::pair< std::string, DeclarationWithType *>( mangleName, new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) ) );
329                                        } // if
330                                } // for
331
332                                functionDecl->set_statements( functionDecl->get_statements()->acceptMutator( *this ) );
333
334                                scopeTyVars = oldtyVars;
335                                assignOps = oldassignOps;
336                                // std::cerr << "end FunctionDecl: ";
337                                // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
338                                //      std::cerr << i->first << " ";
339                                // }
340                                // std::cerr << "\n";
341                                retval = oldRetval;
342                                useRetval = oldUseRetval;
343                                doEndScope();
344                        } // if
345                        return functionDecl;
346                }
347
348                TypeDecl *Pass1::mutate( TypeDecl *typeDecl ) {
349                        scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
350                        return Mutator::mutate( typeDecl );
351                }
352
353                Expression *Pass1::mutate( CommaExpr *commaExpr ) {
354                        bool oldUseRetval = useRetval;
355                        useRetval = false;
356                        commaExpr->set_arg1( maybeMutate( commaExpr->get_arg1(), *this ) );
357                        useRetval = oldUseRetval;
358                        commaExpr->set_arg2( maybeMutate( commaExpr->get_arg2(), *this ) );
359                        return commaExpr;
360                }
361
362                Expression *Pass1::mutate( ConditionalExpr *condExpr ) {
363                        bool oldUseRetval = useRetval;
364                        useRetval = false;
365                        condExpr->set_arg1( maybeMutate( condExpr->get_arg1(), *this ) );
366                        useRetval = oldUseRetval;
367                        condExpr->set_arg2( maybeMutate( condExpr->get_arg2(), *this ) );
368                        condExpr->set_arg3( maybeMutate( condExpr->get_arg3(), *this ) );
369                        return condExpr;
370
371                }
372
373                Expression *Pass1::makeOffsetArray( StructInstType *ty ) {
374                        std::list< Declaration* > &baseMembers = ty->get_baseStruct()->get_members();
375                       
376                        // make a new temporary array
377                        Type *offsetType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
378                        std::stringstream lenGen;
379                        lenGen << baseMembers.size();
380                        ConstantExpr *lenExpr = new ConstantExpr( Constant( offsetType->clone(), lenGen.str() ) );
381                        ObjectDecl *arrayTemp = makeTemporary( new ArrayType( Type::Qualifiers(), offsetType, lenExpr, false, false ) );
382
383                        // build initializer list for temporary
384                        std::list< Initializer* > inits;
385                        for ( std::list< Declaration* >::const_iterator member = baseMembers.begin(); member != baseMembers.end(); ++member ) {
386                                DeclarationWithType *memberDecl;
387                                if ( DeclarationWithType *origMember = dynamic_cast< DeclarationWithType* >( *member ) ) {
388                                        memberDecl = origMember->clone();
389                                } else {
390                                        memberDecl = new ObjectDecl( (*member)->get_name(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, offsetType->clone(), 0 );
391                                }
392                                inits.push_back( new SingleInit( new OffsetofExpr( ty->clone(), memberDecl ) ) );
393                        }
394                        arrayTemp->set_init( new ListInit( inits ) );
395
396                        // return variable pointing to temporary
397                        return new VariableExpr( arrayTemp );
398                }
399               
400                void Pass1::passTypeVars( ApplicationExpr *appExpr, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
401                        // pass size/align for type variables
402                        for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
403                                ResolvExpr::EqvClass eqvClass;
404                                assert( env );
405                                if ( tyParm->second == TypeDecl::Any ) {
406                                        Type *concrete = env->lookup( tyParm->first );
407                                        if ( concrete ) {
408                                                arg = appExpr->get_args().insert( arg, new SizeofExpr( concrete->clone() ) );
409                                                arg++;
410                                                arg = appExpr->get_args().insert( arg, new AlignofExpr( concrete->clone() ) );
411                                                arg++;
412                                        } else {
413                                                throw SemanticError( "unbound type variable in application ", appExpr );
414                                        } // if
415                                } // if
416                        } // for
417
418                        // add size/align for generic types to parameter list
419                        if ( appExpr->get_function()->get_results().empty() ) return;
420                        FunctionType *funcType = getFunctionType( appExpr->get_function()->get_results().front() );
421                        assert( funcType );
422
423                        std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
424                        std::list< Expression* >::const_iterator fnArg = arg;
425                        std::set< std::string > seenTypes; //< names for generic types we've seen
426                        for ( ; fnParm != funcType->get_parameters().end() && fnArg != appExpr->get_args().end(); ++fnParm, ++fnArg ) {
427                                Type *polyBase = hasPolyBase( (*fnParm)->get_type(), exprTyVars );
428                                if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
429                                        std::string sizeName = sizeofName( polyBase );
430                                        if ( seenTypes.count( sizeName ) ) continue;
431
432                                        VariableExpr *fnArgBase = getBaseVar( *fnArg );
433                                        assert( fnArgBase && ! fnArgBase->get_results().empty() );
434                                        Type *argBaseType = fnArgBase->get_results().front();
435                                        arg = appExpr->get_args().insert( arg, new SizeofExpr( argBaseType->clone() ) );
436                                        arg++;
437                                        arg = appExpr->get_args().insert( arg, new AlignofExpr( argBaseType->clone() ) );
438                                        arg++;
439                                        if ( dynamic_cast< StructInstType* >( polyBase ) ) {
440                                                if ( StructInstType *argBaseStructType = dynamic_cast< StructInstType* >( argBaseType ) ) {
441                                                        arg = appExpr->get_args().insert( arg, makeOffsetArray( argBaseStructType ) );
442                                                        arg++;
443                                                } else {
444                                                        throw SemanticError( "Cannot pass non-struct type for generic struct" );
445                                                }
446                                        }
447
448                                        seenTypes.insert( sizeName );
449                                }
450                        }
451                }
452
453                ObjectDecl *Pass1::makeTemporary( Type *type ) {
454                        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, type, 0 );
455                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
456                        return newObj;
457                }
458
459                Expression *Pass1::addRetParam( ApplicationExpr *appExpr, FunctionType *function, Type *retType, std::list< Expression *>::iterator &arg ) {
460                        // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
461                        // if ( useRetval ) {
462                        //      assert( retval );
463                        //      arg = appExpr->get_args().insert( arg, new VariableExpr( retval ) );
464                        //      arg++;
465                        // } else {
466
467                        // Create temporary to hold return value of polymorphic function and produce that temporary as a result
468                        // using a comma expression.  Possibly change comma expression into statement expression "{}" for multiple
469                        // return values.
470                        ObjectDecl *newObj = makeTemporary( retType->clone() );
471                        Expression *paramExpr = new VariableExpr( newObj );
472                        // If the type of the temporary is not polymorphic, box temporary by taking its address; otherwise the
473                        // temporary is already boxed and can be used directly.
474                        if ( ! isPolyType( newObj->get_type(), scopeTyVars, env ) ) {
475                                paramExpr = new AddressExpr( paramExpr );
476                        } // if
477                        arg = appExpr->get_args().insert( arg, paramExpr ); // add argument to function call
478                        arg++;
479                        // Build a comma expression to call the function and emulate a normal return.
480                        CommaExpr *commaExpr = new CommaExpr( appExpr, new VariableExpr( newObj ) );
481                        commaExpr->set_env( appExpr->get_env() );
482                        appExpr->set_env( 0 );
483                        return commaExpr;
484                        // } // if
485                        // return appExpr;
486                }
487
488                void Pass1::replaceParametersWithConcrete( ApplicationExpr *appExpr, std::list< Expression* >& params ) {
489                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
490                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
491                                assert(paramType && "Aggregate parameters should be type expressions");
492                                paramType->set_type( replaceWithConcrete( appExpr, paramType->get_type(), false ) );
493                        }
494                }
495               
496                Type *Pass1::replaceWithConcrete( ApplicationExpr *appExpr, Type *type, bool doClone ) {
497                        if ( TypeInstType *typeInst = dynamic_cast< TypeInstType * >( type ) ) {
498                                Type *concrete = env->lookup( typeInst->get_name() );
499                                if ( concrete == 0 ) {
500                                        throw SemanticError( "Unbound type variable " + typeInst->get_name() + " in ", appExpr );
501                                } // if
502                                return concrete;
503                        } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
504                                if ( doClone ) {
505                                        structType = structType->clone();
506                                }
507                                replaceParametersWithConcrete( appExpr, structType->get_parameters() );
508                                return structType;
509                        } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
510                                if ( doClone ) {
511                                        unionType = unionType->clone();
512                                }
513                                replaceParametersWithConcrete( appExpr, unionType->get_parameters() );
514                                return unionType;
515                        }
516                        return type;
517                }
518
519                Expression *Pass1::addPolyRetParam( ApplicationExpr *appExpr, FunctionType *function, ReferenceToType *polyType, std::list< Expression *>::iterator &arg ) {
520                        assert( env );
521                        Type *concrete = replaceWithConcrete( appExpr, polyType );
522                        return addRetParam( appExpr, function, concrete, arg );
523                }
524
525                Expression *Pass1::applyAdapter( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
526                        Expression *ret = appExpr;
527                        if ( ! function->get_returnVals().empty() && isPolyType( function->get_returnVals().front()->get_type(), tyVars ) ) {
528                                ret = addRetParam( appExpr, function, function->get_returnVals().front()->get_type(), arg );
529                        } // if
530                        std::string mangleName = mangleAdapterName( function, tyVars );
531                        std::string adapterName = makeAdapterName( mangleName );
532
533                        appExpr->get_args().push_front( appExpr->get_function() );
534                        appExpr->set_function( new NameExpr( adapterName ) );
535
536                        return ret;
537                }
538
539                void Pass1::boxParam( Type *param, Expression *&arg, const TyVarMap &exprTyVars ) {
540                        assert( ! arg->get_results().empty() );
541                        if ( isPolyType( param, exprTyVars ) ) {
542                                if ( dynamic_cast< TypeInstType *>( arg->get_results().front() ) ) {
543                                        // if the argument's type is a type parameter, we don't need to box again!
544                                        return;
545                                } else if ( arg->get_results().front()->get_isLvalue() ) {
546                                        // VariableExpr and MemberExpr are lvalues
547                                        arg = new AddressExpr( arg );
548                                } else {
549                                        ObjectDecl *newObj = new ObjectDecl( tempNamer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::C, 0, arg->get_results().front()->clone(), 0 );
550                                        newObj->get_type()->get_qualifiers() = Type::Qualifiers(); // TODO: is this right???
551                                        stmtsToAdd.push_back( new DeclStmt( noLabels, newObj ) );
552                                        UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
553                                        assign->get_args().push_back( new VariableExpr( newObj ) );
554                                        assign->get_args().push_back( arg );
555                                        stmtsToAdd.push_back( new ExprStmt( noLabels, assign ) );
556                                        arg = new AddressExpr( new VariableExpr( newObj ) );
557                                } // if
558                        } // if
559                }
560
561                void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
562                        Type *newType = formal->clone();
563                        std::list< FunctionType *> functions;
564                        // instead of functions needing adapters, this really ought to look for
565                        // any function mentioning a polymorphic type
566                        findAndReplaceFunction( newType, functions, tyVars, needsAdapter );
567                        if ( ! functions.empty() ) {
568                                actual = new CastExpr( actual, newType );
569                        } else {
570                                delete newType;
571                        } // if
572                }
573
574                void Pass1::boxParams( ApplicationExpr *appExpr, FunctionType *function, std::list< Expression *>::iterator &arg, const TyVarMap &exprTyVars ) {
575                        for ( std::list< DeclarationWithType *>::const_iterator param = function->get_parameters().begin(); param != function->get_parameters().end(); ++param, ++arg ) {
576                                assert( arg != appExpr->get_args().end() );
577                                addCast( *arg, (*param)->get_type(), exprTyVars );
578                                boxParam( (*param)->get_type(), *arg, exprTyVars );
579                        } // for
580                }
581
582                void Pass1::addInferredParams( ApplicationExpr *appExpr, FunctionType *functionType, std::list< Expression *>::iterator &arg, const TyVarMap &tyVars ) {
583                        std::list< Expression *>::iterator cur = arg;
584                        for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
585                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
586                                        InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
587                                        assert( inferParam != appExpr->get_inferParams().end() && "NOTE: Explicit casts of polymorphic functions to compatible monomorphic functions are currently unsupported" );
588                                        Expression *newExpr = inferParam->second.expr->clone();
589                                        addCast( newExpr, (*assert)->get_type(), tyVars );
590                                        boxParam( (*assert)->get_type(), newExpr, tyVars );
591                                        appExpr->get_args().insert( cur, newExpr );
592                                } // for
593                        } // for
594                }
595
596                void makeRetParm( FunctionType *funcType ) {
597                        DeclarationWithType *retParm = funcType->get_returnVals().front();
598
599                        // make a new parameter that is a pointer to the type of the old return value
600                        retParm->set_type( new PointerType( Type::Qualifiers(), retParm->get_type() ) );
601                        funcType->get_parameters().push_front( retParm );
602
603                        // we don't need the return value any more
604                        funcType->get_returnVals().clear();
605                }
606
607                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars ) {
608                        // actually make the adapter type
609                        FunctionType *adapter = adaptee->clone();
610                        if ( ! adapter->get_returnVals().empty() && isPolyType( adapter->get_returnVals().front()->get_type(), tyVars ) ) {
611                                makeRetParm( adapter );
612                        } // if
613                        adapter->get_parameters().push_front( new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 ) );
614                        return adapter;
615                }
616
617                Expression *makeAdapterArg( DeclarationWithType *param, DeclarationWithType *arg, DeclarationWithType *realParam, const TyVarMap &tyVars ) {
618                        assert( param );
619                        assert( arg );
620                        if ( isPolyType( realParam->get_type(), tyVars ) ) {
621                                if ( dynamic_cast<TypeInstType *>(arg->get_type()) == NULL ) {
622                                        UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
623                                        deref->get_args().push_back( new CastExpr( new VariableExpr( param ), new PointerType( Type::Qualifiers(), arg->get_type()->clone() ) ) );
624                                        deref->get_results().push_back( arg->get_type()->clone() );
625                                        return deref;
626                                } // if
627                        } // if
628                        return new VariableExpr( param );
629                }
630
631                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 ) {
632                        UniqueName paramNamer( "_p" );
633                        for ( ; param != paramEnd; ++param, ++arg, ++realParam ) {
634                                if ( (*param)->get_name() == "" ) {
635                                        (*param)->set_name( paramNamer.newName() );
636                                        (*param)->set_linkage( LinkageSpec::C );
637                                } // if
638                                adapteeApp->get_args().push_back( makeAdapterArg( *param, *arg, *realParam, tyVars ) );
639                        } // for
640                }
641
642
643
644                FunctionDecl *Pass1::makeAdapter( FunctionType *adaptee, FunctionType *realType, const std::string &mangleName, const TyVarMap &tyVars ) {
645                        FunctionType *adapterType = makeAdapterType( adaptee, tyVars );
646                        adapterType = ScrubTyVars::scrub( adapterType, tyVars );
647                        DeclarationWithType *adapteeDecl = adapterType->get_parameters().front();
648                        adapteeDecl->set_name( "_adaptee" );
649                        ApplicationExpr *adapteeApp = new ApplicationExpr( new CastExpr( new VariableExpr( adapteeDecl ), new PointerType( Type::Qualifiers(), realType ) ) );
650                        Statement *bodyStmt;
651
652                        std::list< TypeDecl *>::iterator tyArg = realType->get_forall().begin();
653                        std::list< TypeDecl *>::iterator tyParam = adapterType->get_forall().begin();
654                        std::list< TypeDecl *>::iterator realTyParam = adaptee->get_forall().begin();
655                        for ( ; tyParam != adapterType->get_forall().end(); ++tyArg, ++tyParam, ++realTyParam ) {
656                                assert( tyArg != realType->get_forall().end() );
657                                std::list< DeclarationWithType *>::iterator assertArg = (*tyArg)->get_assertions().begin();
658                                std::list< DeclarationWithType *>::iterator assertParam = (*tyParam)->get_assertions().begin();
659                                std::list< DeclarationWithType *>::iterator realAssertParam = (*realTyParam)->get_assertions().begin();
660                                for ( ; assertParam != (*tyParam)->get_assertions().end(); ++assertArg, ++assertParam, ++realAssertParam ) {
661                                        assert( assertArg != (*tyArg)->get_assertions().end() );
662                                        adapteeApp->get_args().push_back( makeAdapterArg( *assertParam, *assertArg, *realAssertParam, tyVars ) );
663                                } // for
664                        } // for
665
666                        std::list< DeclarationWithType *>::iterator arg = realType->get_parameters().begin();
667                        std::list< DeclarationWithType *>::iterator param = adapterType->get_parameters().begin();
668                        std::list< DeclarationWithType *>::iterator realParam = adaptee->get_parameters().begin();
669                        param++;                // skip adaptee parameter
670                        if ( realType->get_returnVals().empty() ) {
671                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
672                                bodyStmt = new ExprStmt( noLabels, adapteeApp );
673                        } else if ( isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
674                                if ( (*param)->get_name() == "" ) {
675                                        (*param)->set_name( "_ret" );
676                                        (*param)->set_linkage( LinkageSpec::C );
677                                } // if
678                                UntypedExpr *assign = new UntypedExpr( new NameExpr( "?=?" ) );
679                                UntypedExpr *deref = new UntypedExpr( new NameExpr( "*?" ) );
680                                deref->get_args().push_back( new CastExpr( new VariableExpr( *param++ ), new PointerType( Type::Qualifiers(), realType->get_returnVals().front()->get_type()->clone() ) ) );
681                                assign->get_args().push_back( deref );
682                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
683                                assign->get_args().push_back( adapteeApp );
684                                bodyStmt = new ExprStmt( noLabels, assign );
685                        } else {
686                                // adapter for a function that returns a monomorphic value
687                                addAdapterParams( adapteeApp, arg, param, adapterType->get_parameters().end(), realParam, tyVars );
688                                bodyStmt = new ReturnStmt( noLabels, adapteeApp );
689                        } // if
690                        CompoundStmt *adapterBody = new CompoundStmt( noLabels );
691                        adapterBody->get_kids().push_back( bodyStmt );
692                        std::string adapterName = makeAdapterName( mangleName );
693                        return new FunctionDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, adapterType, adapterBody, false, false );
694                }
695
696                void Pass1::passAdapters( ApplicationExpr * appExpr, FunctionType * functionType, const TyVarMap & exprTyVars ) {
697                        // collect a list of function types passed as parameters or implicit parameters (assertions)
698                        std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
699                        std::list< FunctionType *> functions;
700                        for ( std::list< TypeDecl *>::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
701                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->get_assertions().begin(); assert != (*tyVar)->get_assertions().end(); ++assert ) {
702                                        findFunction( (*assert)->get_type(), functions, exprTyVars, needsAdapter );
703                                } // for
704                        } // for
705                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
706                                findFunction( (*arg)->get_type(), functions, exprTyVars, needsAdapter );
707                        } // for
708
709                        // parameter function types for which an appropriate adapter has been generated.  we cannot use the types
710                        // after applying substitutions, since two different parameter types may be unified to the same type
711                        std::set< std::string > adaptersDone;
712
713                        for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
714                                FunctionType *originalFunction = (*funType)->clone();
715                                FunctionType *realFunction = (*funType)->clone();
716                                std::string mangleName = SymTab::Mangler::mangle( realFunction );
717
718                                // only attempt to create an adapter or pass one as a parameter if we haven't already done so for this
719                                // pre-substitution parameter function type.
720                                if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
721                                        adaptersDone.insert( adaptersDone.begin(), mangleName );
722
723                                        // apply substitution to type variables to figure out what the adapter's type should look like
724                                        assert( env );
725                                        env->apply( realFunction );
726                                        mangleName = SymTab::Mangler::mangle( realFunction );
727                                        mangleName += makePolyMonoSuffix( originalFunction, exprTyVars );
728
729                                        AdapterMap & adapters = Pass1::adapters.top();
730                                        AdapterMap::iterator adapter = adapters.find( mangleName );
731                                        if ( adapter == adapters.end() ) {
732                                                // adapter has not been created yet in the current scope, so define it
733                                                FunctionDecl *newAdapter = makeAdapter( *funType, realFunction, mangleName, exprTyVars );
734                                                adapter = adapters.insert( adapters.begin(), std::pair< std::string, DeclarationWithType *>( mangleName, newAdapter ) );
735                                                stmtsToAdd.push_back( new DeclStmt( noLabels, newAdapter ) );
736                                        } // if
737                                        assert( adapter != adapters.end() );
738
739                                        // add the appropriate adapter as a parameter
740                                        appExpr->get_args().push_front( new VariableExpr( adapter->second ) );
741                                } // if
742                        } // for
743                } // passAdapters
744
745                Expression *makeIncrDecrExpr( ApplicationExpr *appExpr, Type *polyType, bool isIncr ) {
746                        NameExpr *opExpr;
747                        if ( isIncr ) {
748                                opExpr = new NameExpr( "?+=?" );
749                        } else {
750                                opExpr = new NameExpr( "?-=?" );
751                        } // if
752                        UntypedExpr *addAssign = new UntypedExpr( opExpr );
753                        if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
754                                addAssign->get_args().push_back( address->get_arg() );
755                        } else {
756                                addAssign->get_args().push_back( appExpr->get_args().front() );
757                        } // if
758                        addAssign->get_args().push_back( new NameExpr( sizeofName( polyType ) ) );
759                        addAssign->get_results().front() = appExpr->get_results().front()->clone();
760                        if ( appExpr->get_env() ) {
761                                addAssign->set_env( appExpr->get_env() );
762                                appExpr->set_env( 0 );
763                        } // if
764                        appExpr->get_args().clear();
765                        delete appExpr;
766                        return addAssign;
767                }
768
769                Expression *Pass1::handleIntrinsics( ApplicationExpr *appExpr ) {
770                        if ( VariableExpr *varExpr = dynamic_cast< VariableExpr *>( appExpr->get_function() ) ) {
771                                if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic ) {
772                                        if ( varExpr->get_var()->get_name() == "?[?]" ) {
773                                                assert( ! appExpr->get_results().empty() );
774                                                assert( appExpr->get_args().size() == 2 );
775                                                Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
776                                                Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
777                                                assert( ! baseType1 || ! baseType2 ); // the arguments cannot both be polymorphic pointers
778                                                UntypedExpr *ret = 0;
779                                                if ( baseType1 || baseType2 ) { // one of the arguments is a polymorphic pointer
780                                                        ret = new UntypedExpr( new NameExpr( "?+?" ) );
781                                                } // if
782                                                if ( baseType1 ) {
783                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
784                                                        multiply->get_args().push_back( appExpr->get_args().back() );
785                                                        multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
786                                                        ret->get_args().push_back( appExpr->get_args().front() );
787                                                        ret->get_args().push_back( multiply );
788                                                } else if ( baseType2 ) {
789                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
790                                                        multiply->get_args().push_back( appExpr->get_args().front() );
791                                                        multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
792                                                        ret->get_args().push_back( multiply );
793                                                        ret->get_args().push_back( appExpr->get_args().back() );
794                                                } // if
795                                                if ( baseType1 || baseType2 ) {
796                                                        ret->get_results().push_front( appExpr->get_results().front()->clone() );
797                                                        if ( appExpr->get_env() ) {
798                                                                ret->set_env( appExpr->get_env() );
799                                                                appExpr->set_env( 0 );
800                                                        } // if
801                                                        appExpr->get_args().clear();
802                                                        delete appExpr;
803                                                        return ret;
804                                                } // if
805                                        } else if ( varExpr->get_var()->get_name() == "*?" ) {
806                                                assert( ! appExpr->get_results().empty() );
807                                                assert( ! appExpr->get_args().empty() );
808                                                if ( isPolyType( appExpr->get_results().front(), scopeTyVars, env ) ) {
809                                                        Expression *ret = appExpr->get_args().front();
810                                                        delete ret->get_results().front();
811                                                        ret->get_results().front() = appExpr->get_results().front()->clone();
812                                                        if ( appExpr->get_env() ) {
813                                                                ret->set_env( appExpr->get_env() );
814                                                                appExpr->set_env( 0 );
815                                                        } // if
816                                                        appExpr->get_args().clear();
817                                                        delete appExpr;
818                                                        return ret;
819                                                } // if
820                                        } else if ( varExpr->get_var()->get_name() == "?++" || varExpr->get_var()->get_name() == "?--" ) {
821                                                assert( ! appExpr->get_results().empty() );
822                                                assert( appExpr->get_args().size() == 1 );
823                                                if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
824                                                        Type *tempType = appExpr->get_results().front()->clone();
825                                                        if ( env ) {
826                                                                env->apply( tempType );
827                                                        } // if
828                                                        ObjectDecl *newObj = makeTemporary( tempType );
829                                                        VariableExpr *tempExpr = new VariableExpr( newObj );
830                                                        UntypedExpr *assignExpr = new UntypedExpr( new NameExpr( "?=?" ) );
831                                                        assignExpr->get_args().push_back( tempExpr->clone() );
832                                                        if ( AddressExpr *address = dynamic_cast< AddressExpr *>( appExpr->get_args().front() ) ) {
833                                                                assignExpr->get_args().push_back( address->get_arg()->clone() );
834                                                        } else {
835                                                                assignExpr->get_args().push_back( appExpr->get_args().front()->clone() );
836                                                        } // if
837                                                        CommaExpr *firstComma = new CommaExpr( assignExpr, makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "?++" ) );
838                                                        return new CommaExpr( firstComma, tempExpr );
839                                                } // if
840                                        } else if ( varExpr->get_var()->get_name() == "++?" || varExpr->get_var()->get_name() == "--?" ) {
841                                                assert( ! appExpr->get_results().empty() );
842                                                assert( appExpr->get_args().size() == 1 );
843                                                if ( Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env ) ) {
844                                                        return makeIncrDecrExpr( appExpr, baseType, varExpr->get_var()->get_name() == "++?" );
845                                                } // if
846                                        } else if ( varExpr->get_var()->get_name() == "?+?" || varExpr->get_var()->get_name() == "?-?" ) {
847                                                assert( ! appExpr->get_results().empty() );
848                                                assert( appExpr->get_args().size() == 2 );
849                                                Type *baseType1 = isPolyPtr( appExpr->get_args().front()->get_results().front(), scopeTyVars, env );
850                                                Type *baseType2 = isPolyPtr( appExpr->get_args().back()->get_results().front(), scopeTyVars, env );
851                                                if ( baseType1 && baseType2 ) {
852                                                        UntypedExpr *divide = new UntypedExpr( new NameExpr( "?/?" ) );
853                                                        divide->get_args().push_back( appExpr );
854                                                        divide->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
855                                                        divide->get_results().push_front( appExpr->get_results().front()->clone() );
856                                                        if ( appExpr->get_env() ) {
857                                                                divide->set_env( appExpr->get_env() );
858                                                                appExpr->set_env( 0 );
859                                                        } // if
860                                                        return divide;
861                                                } else if ( baseType1 ) {
862                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
863                                                        multiply->get_args().push_back( appExpr->get_args().back() );
864                                                        multiply->get_args().push_back( new NameExpr( sizeofName( baseType1 ) ) );
865                                                        appExpr->get_args().back() = multiply;
866                                                } else if ( baseType2 ) {
867                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
868                                                        multiply->get_args().push_back( appExpr->get_args().front() );
869                                                        multiply->get_args().push_back( new NameExpr( sizeofName( baseType2 ) ) );
870                                                        appExpr->get_args().front() = multiply;
871                                                } // if
872                                        } else if ( varExpr->get_var()->get_name() == "?+=?" || varExpr->get_var()->get_name() == "?-=?" ) {
873                                                assert( ! appExpr->get_results().empty() );
874                                                assert( appExpr->get_args().size() == 2 );
875                                                Type *baseType = isPolyPtr( appExpr->get_results().front(), scopeTyVars, env );
876                                                if ( baseType ) {
877                                                        UntypedExpr *multiply = new UntypedExpr( new NameExpr( "?*?" ) );
878                                                        multiply->get_args().push_back( appExpr->get_args().back() );
879                                                        multiply->get_args().push_back( new NameExpr( sizeofName( baseType ) ) );
880                                                        appExpr->get_args().back() = multiply;
881                                                } // if
882                                        } // if
883                                        return appExpr;
884                                } // if
885                        } // if
886                        return 0;
887                }
888
889                Expression *Pass1::mutate( ApplicationExpr *appExpr ) {
890                        // std::cerr << "mutate appExpr: ";
891                        // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
892                        //      std::cerr << i->first << " ";
893                        // }
894                        // std::cerr << "\n";
895                        bool oldUseRetval = useRetval;
896                        useRetval = false;
897                        appExpr->get_function()->acceptMutator( *this );
898                        mutateAll( appExpr->get_args(), *this );
899                        useRetval = oldUseRetval;
900
901                        assert( ! appExpr->get_function()->get_results().empty() );
902                        PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
903                        assert( pointer );
904                        FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
905                        assert( function );
906
907                        if ( Expression *newExpr = handleIntrinsics( appExpr ) ) {
908                                return newExpr;
909                        } // if
910
911                        Expression *ret = appExpr;
912
913                        std::list< Expression *>::iterator arg = appExpr->get_args().begin();
914                        std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin();
915
916                        if ( ReferenceToType *polyType = isPolyRet( function ) ) {
917                                ret = addPolyRetParam( appExpr, function, polyType, arg );
918                        } else if ( needsAdapter( function, scopeTyVars ) ) {
919                                // std::cerr << "needs adapter: ";
920                                // for ( TyVarMap::iterator i = scopeTyVars.begin(); i != scopeTyVars.end(); ++i ) {
921                                //      std::cerr << i->first << " ";
922                                // }
923                                // std::cerr << "\n";
924                                // change the application so it calls the adapter rather than the passed function
925                                ret = applyAdapter( appExpr, function, arg, scopeTyVars );
926                        } // if
927                        arg = appExpr->get_args().begin();
928
929                        TyVarMap exprTyVars;
930                        makeTyVarMap( function, exprTyVars );
931
932                        passTypeVars( appExpr, arg, exprTyVars );
933                        addInferredParams( appExpr, function, arg, exprTyVars );
934
935                        arg = paramBegin;
936
937                        boxParams( appExpr, function, arg, exprTyVars );
938
939                        passAdapters( appExpr, function, exprTyVars );
940
941                        return ret;
942                }
943
944                Expression *Pass1::mutate( UntypedExpr *expr ) {
945                        if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
946                                if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
947                                        if ( name->get_name() == "*?" ) {
948                                                Expression *ret = expr->get_args().front();
949                                                expr->get_args().clear();
950                                                delete expr;
951                                                return ret->acceptMutator( *this );
952                                        } // if
953                                } // if
954                        } // if
955                        return PolyMutator::mutate( expr );
956                }
957
958                Expression *Pass1::mutate( AddressExpr *addrExpr ) {
959                        assert( ! addrExpr->get_arg()->get_results().empty() );
960
961                        bool needs = false;
962                        if ( UntypedExpr *expr = dynamic_cast< UntypedExpr *>( addrExpr->get_arg() ) ) {
963                                if ( ! expr->get_results().empty() && isPolyType( expr->get_results().front(), scopeTyVars, env ) ) {
964                                        if ( NameExpr *name = dynamic_cast< NameExpr *>( expr->get_function() ) ) {
965                                                if ( name->get_name() == "*?" ) {
966                                                        if ( ApplicationExpr * appExpr = dynamic_cast< ApplicationExpr * >( expr->get_args().front() ) ) {
967                                                                assert( ! appExpr->get_function()->get_results().empty() );
968                                                                PointerType *pointer = dynamic_cast< PointerType *>( appExpr->get_function()->get_results().front() );
969                                                                assert( pointer );
970                                                                FunctionType *function = dynamic_cast< FunctionType *>( pointer->get_base() );
971                                                                assert( function );
972                                                                needs = needsAdapter( function, scopeTyVars );
973                                                        } // if
974                                                } // if
975                                        } // if
976                                } // if
977                        } // if
978                        addrExpr->set_arg( mutateExpression( addrExpr->get_arg() ) );
979                        if ( isPolyType( addrExpr->get_arg()->get_results().front(), scopeTyVars, env ) || needs ) {
980                                Expression *ret = addrExpr->get_arg();
981                                delete ret->get_results().front();
982                                ret->get_results().front() = addrExpr->get_results().front()->clone();
983                                addrExpr->set_arg( 0 );
984                                delete addrExpr;
985                                return ret;
986                        } else {
987                                return addrExpr;
988                        } // if
989                }
990
991                /// Wraps a function declaration in a new pointer-to-function variable expression
992                VariableExpr *wrapFunctionDecl( DeclarationWithType *functionDecl ) {
993                        // line below cloned from FixFunction.cc
994                        ObjectDecl *functionObj = new ObjectDecl( functionDecl->get_name(), functionDecl->get_storageClass(), functionDecl->get_linkage(), 0,
995                                                                  new PointerType( Type::Qualifiers(), functionDecl->get_type()->clone() ), 0 );
996                        functionObj->set_mangleName( functionDecl->get_mangleName() );
997                        return new VariableExpr( functionObj );
998                }
999               
1000                Statement * Pass1::mutate( ReturnStmt *returnStmt ) {
1001                        if ( retval && returnStmt->get_expr() ) {
1002                                assert( ! returnStmt->get_expr()->get_results().empty() );
1003                                // ***** Code Removal ***** After introducing a temporary variable for all return expressions, the following code appears superfluous.
1004                                // if ( returnStmt->get_expr()->get_results().front()->get_isLvalue() ) {
1005                                // by this point, a cast expr on a polymorphic return value is redundant
1006                                while ( CastExpr *castExpr = dynamic_cast< CastExpr *>( returnStmt->get_expr() ) ) {
1007                                        returnStmt->set_expr( castExpr->get_arg() );
1008                                        returnStmt->get_expr()->set_env( castExpr->get_env() );
1009                                        castExpr->set_env( 0 );
1010                                        castExpr->set_arg( 0 );
1011                                        delete castExpr;
1012                                } //while
1013
1014                                // find assignment operator for (polymorphic) return type
1015                                ApplicationExpr *assignExpr = 0;
1016                                if ( TypeInstType *typeInst = dynamic_cast< TypeInstType *>( retval->get_type() ) ) {
1017                                        // find assignment operator for type variable
1018                                        std::map< std::string, DeclarationWithType *>::const_iterator assignIter = assignOps.find( typeInst->get_name() );
1019                                        if ( assignIter == assignOps.end() ) {
1020                                                throw SemanticError( "Attempt to return dtype or ftype object in ", returnStmt->get_expr() );
1021                                        } // if
1022                                        assignExpr = new ApplicationExpr( new VariableExpr( assignIter->second ) );
1023                                } else if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( retval->get_type() ) ) {
1024                                        // find assignment operator for generic type
1025                                        ScopedMap< std::string, DeclarationWithType *>::const_iterator assignIter = scopedAssignOps.find( refType->get_name() );
1026                                        if ( assignIter == scopedAssignOps.end() ) {
1027                                                throw SemanticError( "Attempt to return dtype or ftype generic object in ", returnStmt->get_expr() );
1028                                        }
1029
1030                                        // wrap it up in an application expression
1031                                        DeclarationWithType *functionDecl = assignIter->second;
1032                                        assignExpr = new ApplicationExpr( wrapFunctionDecl( functionDecl ) );
1033                                        assignExpr->set_env( env->clone() );
1034
1035                                        // find each of its needed secondary assignment operators
1036                                        std::list< Expression* > &tyParams = refType->get_parameters();
1037                                        std::list< TypeDecl* > &forallParams = functionDecl->get_type()->get_forall();
1038                                        std::list< Expression* >::const_iterator tyIt = tyParams.begin();
1039                                        std::list< TypeDecl* >::const_iterator forallIt = forallParams.begin();
1040                                        for ( ; tyIt != tyParams.end() && forallIt != forallParams.end(); ++tyIt, ++forallIt ) {
1041                                                if ( (*forallIt)->get_kind() != TypeDecl::Any ) continue; // skip types with no assign op (ftype/dtype)
1042
1043                                                std::list< DeclarationWithType* > &asserts = (*forallIt)->get_assertions();
1044                                                assert( ! asserts.empty() && "Type param needs assignment operator assertion" );
1045                                                DeclarationWithType *actualDecl = asserts.front();
1046                                                ReferenceToType *actualType = isAssignment( actualDecl );
1047                                                assert( actualType && "First assertion of type with assertions should be assignment operator" );
1048                                                TypeExpr *formalTypeExpr = dynamic_cast< TypeExpr* >( *tyIt );
1049                                                assert( formalTypeExpr && "type parameters must be type expressions" );
1050                                                Type *formalType = formalTypeExpr->get_type();
1051                                                assignExpr->get_env()->add( actualType->get_name(), formalType );
1052                                               
1053                                                DeclarationWithType *assertAssign = 0;
1054                                                if ( TypeInstType *formalTypeInstType = dynamic_cast< TypeInstType* >( formalType ) ) {
1055                                                        std::map< std::string, DeclarationWithType *>::const_iterator assertAssignIt = assignOps.find( formalTypeInstType->get_name() );
1056                                                        if ( assertAssignIt == assignOps.end() ) {
1057                                                                throw SemanticError( "No assignment operation found for ", formalTypeInstType );
1058                                                        }
1059                                                        assertAssign = assertAssignIt->second;
1060                                                        //assignExpr->get_env()->add( formalTypeInstType->get_name(), actualType );
1061                                                } else if ( ReferenceToType *formalReferenceType = dynamic_cast< ReferenceToType* >( formalType ) )  {
1062                                                        ScopedMap< std::string, DeclarationWithType *>::const_iterator assertAssignIt = scopedAssignOps.find( formalReferenceType->get_name() );
1063                                                        if ( assertAssignIt == scopedAssignOps.end() ) {
1064                                                                throw SemanticError( "No assignment operation found for ", formalReferenceType );
1065                                                        }
1066                                                        assertAssign = assertAssignIt->second;
1067                                                } else assert( false && "returning polymorphic types with non struct/polymorphic parameters not yet supported" );
1068                                               
1069
1070                                                assignExpr->get_inferParams()[ actualDecl->get_uniqueId() ]
1071                                                        = ParamEntry( assertAssign->get_uniqueId(), assertAssign->get_type()->clone(), actualDecl->get_type()->clone(), wrapFunctionDecl( assertAssign ) );
1072                                        }
1073                                }
1074                                assert( assignExpr );
1075
1076                                // replace return statement with appropriate assignment to out parameter
1077                                Expression *retParm = new NameExpr( retval->get_name() );
1078                                retParm->get_results().push_back( new PointerType( Type::Qualifiers(), retval->get_type()->clone() ) );
1079                                assignExpr->get_args().push_back( retParm );
1080                                assignExpr->get_args().push_back( returnStmt->get_expr() );
1081                                stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( assignExpr ) ) );
1082                                // } else {
1083                                //      useRetval = true;
1084                                //      stmtsToAdd.push_back( new ExprStmt( noLabels, mutateExpression( returnStmt->get_expr() ) ) );
1085                                //      useRetval = false;
1086                                // } // if
1087                                returnStmt->set_expr( 0 );
1088                        } else {
1089                                returnStmt->set_expr( mutateExpression( returnStmt->get_expr() ) );
1090                        } // if
1091                        return returnStmt;
1092                }
1093
1094                Type * Pass1::mutate( PointerType *pointerType ) {
1095                        TyVarMap oldtyVars = scopeTyVars;
1096                        makeTyVarMap( pointerType, scopeTyVars );
1097
1098                        Type *ret = Mutator::mutate( pointerType );
1099
1100                        scopeTyVars = oldtyVars;
1101                        return ret;
1102                }
1103
1104                Type * Pass1::mutate( FunctionType *functionType ) {
1105                        TyVarMap oldtyVars = scopeTyVars;
1106                        makeTyVarMap( functionType, scopeTyVars );
1107
1108                        Type *ret = Mutator::mutate( functionType );
1109
1110                        scopeTyVars = oldtyVars;
1111                        return ret;
1112                }
1113
1114                void Pass1::doBeginScope() {
1115                        // push a copy of the current map
1116                        adapters.push(adapters.top());
1117                        scopedAssignOps.beginScope();
1118                }
1119
1120                void Pass1::doEndScope() {
1121                        adapters.pop();
1122                        scopedAssignOps.endScope();
1123                }
1124
1125////////////////////////////////////////// Pass2 ////////////////////////////////////////////////////
1126
1127                void Pass2::addAdapters( FunctionType *functionType ) {
1128                        std::list< DeclarationWithType *> &paramList = functionType->get_parameters();
1129                        std::list< FunctionType *> functions;
1130                        for ( std::list< DeclarationWithType *>::iterator arg = paramList.begin(); arg != paramList.end(); ++arg ) {
1131                                Type *orig = (*arg)->get_type();
1132                                findAndReplaceFunction( orig, functions, scopeTyVars, needsAdapter );
1133                                (*arg)->set_type( orig );
1134                        }
1135                        std::set< std::string > adaptersDone;
1136                        for ( std::list< FunctionType *>::iterator funType = functions.begin(); funType != functions.end(); ++funType ) {
1137                                std::string mangleName = mangleAdapterName( *funType, scopeTyVars );
1138                                if ( adaptersDone.find( mangleName ) == adaptersDone.end() ) {
1139                                        std::string adapterName = makeAdapterName( mangleName );
1140                                        paramList.push_front( new ObjectDecl( adapterName, DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new PointerType( Type::Qualifiers(), makeAdapterType( *funType, scopeTyVars ) ), 0 ) );
1141                                        adaptersDone.insert( adaptersDone.begin(), mangleName );
1142                                }
1143                        }
1144//  deleteAll( functions );
1145                }
1146
1147                template< typename DeclClass >
1148                DeclClass * Pass2::handleDecl( DeclClass *decl, Type *type ) {
1149                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1150
1151                        return ret;
1152                }
1153
1154                DeclarationWithType * Pass2::mutate( FunctionDecl *functionDecl ) {
1155                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1156                }
1157
1158                ObjectDecl * Pass2::mutate( ObjectDecl *objectDecl ) {
1159                        return handleDecl( objectDecl, objectDecl->get_type() );
1160                }
1161
1162                TypeDecl * Pass2::mutate( TypeDecl *typeDecl ) {
1163                        scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1164                        if ( typeDecl->get_base() ) {
1165                                return handleDecl( typeDecl, typeDecl->get_base() );
1166                        } else {
1167                                return Mutator::mutate( typeDecl );
1168                        }
1169                }
1170
1171                TypedefDecl * Pass2::mutate( TypedefDecl *typedefDecl ) {
1172                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1173                }
1174
1175                Type * Pass2::mutate( PointerType *pointerType ) {
1176                        TyVarMap oldtyVars = scopeTyVars;
1177                        makeTyVarMap( pointerType, scopeTyVars );
1178
1179                        Type *ret = Mutator::mutate( pointerType );
1180
1181                        scopeTyVars = oldtyVars;
1182                        return ret;
1183                }
1184
1185                Type *Pass2::mutate( FunctionType *funcType ) {
1186                        TyVarMap oldtyVars = scopeTyVars;
1187                        makeTyVarMap( funcType, scopeTyVars );
1188
1189                        // move polymorphic return type to parameter list
1190                        if ( isPolyRet( funcType ) ) {
1191                                DeclarationWithType *ret = funcType->get_returnVals().front();
1192                                ret->set_type( new PointerType( Type::Qualifiers(), ret->get_type() ) );
1193                                funcType->get_parameters().push_front( ret );
1194                                funcType->get_returnVals().pop_front();
1195                        }
1196
1197                        // add size/align and assertions for type parameters to parameter list
1198                        std::list< DeclarationWithType *>::iterator last = funcType->get_parameters().begin();
1199                        std::list< DeclarationWithType *> inferredParams;
1200                        ObjectDecl newObj( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), 0 );
1201                        ObjectDecl newPtr( "", DeclarationNode::NoStorageClass, LinkageSpec::C, 0,
1202                                           new PointerType( Type::Qualifiers(), new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ) ), 0 );
1203//   ObjectDecl *newFunPtr = new ObjectDecl( "", DeclarationNode::NoStorageClass, LinkageSpec::Cforall, 0, new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ), 0 );
1204                        for ( std::list< TypeDecl *>::const_iterator tyParm = funcType->get_forall().begin(); tyParm != funcType->get_forall().end(); ++tyParm ) {
1205                                ObjectDecl *sizeParm, *alignParm;
1206                                // add all size and alignment parameters to parameter list
1207                                if ( (*tyParm)->get_kind() == TypeDecl::Any ) {
1208                                        TypeInstType parmType( Type::Qualifiers(), (*tyParm)->get_name(), *tyParm );
1209
1210                                        sizeParm = newObj.clone();
1211                                        sizeParm->set_name( sizeofName( &parmType ) );
1212                                        last = funcType->get_parameters().insert( last, sizeParm );
1213                                        ++last;
1214
1215                                        alignParm = newObj.clone();
1216                                        alignParm->set_name( alignofName( &parmType ) );
1217                                        last = funcType->get_parameters().insert( last, alignParm );
1218                                        ++last;
1219                                }
1220                                // move all assertions into parameter list
1221                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyParm)->get_assertions().begin(); assert != (*tyParm)->get_assertions().end(); ++assert ) {
1222//      *assert = (*assert)->acceptMutator( *this );
1223                                        inferredParams.push_back( *assert );
1224                                }
1225                                (*tyParm)->get_assertions().clear();
1226                        }
1227
1228                        // add size/align for generic types to parameter list
1229                        std::set< std::string > seenTypes; // sizeofName for generic types we've seen
1230                        for ( std::list< DeclarationWithType* >::const_iterator fnParm = last; fnParm != funcType->get_parameters().end(); ++fnParm ) {
1231                                Type *polyBase = hasPolyBase( (*fnParm)->get_type(), scopeTyVars );
1232                                if ( polyBase && ! dynamic_cast< TypeInstType* >( polyBase ) ) {
1233                                        std::string sizeName = sizeofName( polyBase );
1234                                        if ( seenTypes.count( sizeName ) ) continue;
1235
1236                                        ObjectDecl *sizeParm, *alignParm, *offsetParm;
1237                                        sizeParm = newObj.clone();
1238                                        sizeParm->set_name( sizeName );
1239                                        last = funcType->get_parameters().insert( last, sizeParm );
1240                                        ++last;
1241
1242                                        alignParm = newObj.clone();
1243                                        alignParm->set_name( alignofName( polyBase ) );
1244                                        last = funcType->get_parameters().insert( last, alignParm );
1245                                        ++last;
1246
1247                                        if ( dynamic_cast< StructInstType* >( polyBase ) ) {
1248                                                offsetParm = newPtr.clone();
1249                                                offsetParm->set_name( offsetofName( polyBase ) );
1250                                                last = funcType->get_parameters().insert( last, offsetParm );
1251                                                ++last;
1252                                        }
1253
1254                                        seenTypes.insert( sizeName );
1255                                }
1256                        }
1257
1258                        // splice assertion parameters into parameter list
1259                        funcType->get_parameters().splice( last, inferredParams );
1260                        addAdapters( funcType );
1261                        mutateAll( funcType->get_returnVals(), *this );
1262                        mutateAll( funcType->get_parameters(), *this );
1263
1264                        scopeTyVars = oldtyVars;
1265                        return funcType;
1266                }
1267
1268////////////////////////////////////////// MemberExprFixer ////////////////////////////////////////////////////
1269
1270                template< typename DeclClass >
1271                DeclClass * MemberExprFixer::handleDecl( DeclClass *decl, Type *type ) {
1272                        TyVarMap oldtyVars = scopeTyVars;
1273                        makeTyVarMap( type, scopeTyVars );
1274
1275                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1276
1277                        scopeTyVars = oldtyVars;
1278                        return ret;
1279                }
1280
1281                ObjectDecl * MemberExprFixer::mutate( ObjectDecl *objectDecl ) {
1282                        return handleDecl( objectDecl, objectDecl->get_type() );
1283                }
1284
1285                DeclarationWithType * MemberExprFixer::mutate( FunctionDecl *functionDecl ) {
1286                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1287                }
1288
1289                TypedefDecl * MemberExprFixer::mutate( TypedefDecl *typedefDecl ) {
1290                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1291                }
1292
1293                TypeDecl * MemberExprFixer::mutate( TypeDecl *typeDecl ) {
1294                        scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1295                        return Mutator::mutate( typeDecl );
1296                }
1297
1298                Type * MemberExprFixer::mutate( PointerType *pointerType ) {
1299                        TyVarMap oldtyVars = scopeTyVars;
1300                        makeTyVarMap( pointerType, scopeTyVars );
1301
1302                        Type *ret = Mutator::mutate( pointerType );
1303
1304                        scopeTyVars = oldtyVars;
1305                        return ret;
1306                }
1307
1308                Type * MemberExprFixer::mutate( FunctionType *functionType ) {
1309                        TyVarMap oldtyVars = scopeTyVars;
1310                        makeTyVarMap( functionType, scopeTyVars );
1311
1312                        Type *ret = Mutator::mutate( functionType );
1313
1314                        scopeTyVars = oldtyVars;
1315                        return ret;
1316                }
1317
1318                Statement *MemberExprFixer::mutate( DeclStmt *declStmt ) {
1319                        if ( ObjectDecl *objectDecl = dynamic_cast< ObjectDecl *>( declStmt->get_decl() ) ) {
1320                                if ( isPolyType( objectDecl->get_type(), scopeTyVars ) ) {
1321                                        // change initialization of a polymorphic value object
1322                                        // to allocate storage with alloca
1323                                        Type *declType = objectDecl->get_type();
1324                                        UntypedExpr *alloc = new UntypedExpr( new NameExpr( "__builtin_alloca" ) );
1325                                        alloc->get_args().push_back( new NameExpr( sizeofName( declType ) ) );
1326
1327                                        delete objectDecl->get_init();
1328
1329                                        std::list<Expression*> designators;
1330                                        objectDecl->set_init( new SingleInit( alloc, designators ) );
1331                                }
1332                        }
1333                        return Mutator::mutate( declStmt );
1334                }
1335
1336                /// Finds the member in the base list that matches the given declaration; returns its index, or -1 if not present
1337                long findMember( DeclarationWithType *memberDecl, std::list< Declaration* > &baseDecls ) {
1338                        long i = 0;
1339                        for(std::list< Declaration* >::const_iterator decl = baseDecls.begin(); decl != baseDecls.end(); ++decl, ++i ) {
1340                                if ( memberDecl->get_name() != (*decl)->get_name() ) continue;
1341
1342                                if ( DeclarationWithType *declWithType = dynamic_cast< DeclarationWithType* >( *decl ) ) {
1343                                        if ( memberDecl->get_mangleName() == declWithType->get_mangleName() ) return i;
1344                                        else continue;
1345                                } else return i;
1346                        }
1347                        return -1;
1348                }
1349
1350                /// Returns an index expression into the offset array for a type
1351                Expression *makeOffsetIndex( Type *objectType, long i ) {
1352                        std::stringstream offset_namer;
1353                        offset_namer << i;
1354                        ConstantExpr *fieldIndex = new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), offset_namer.str() ) );
1355                        UntypedExpr *fieldOffset = new UntypedExpr( new NameExpr( "?[?]" ) );
1356                        fieldOffset->get_args().push_back( new NameExpr( offsetofName( objectType ) ) );
1357                        fieldOffset->get_args().push_back( fieldIndex );
1358                        return fieldOffset;
1359                }
1360
1361                /// Returns an expression dereferenced n times
1362                Expression *makeDerefdVar( Expression *derefdVar, long n ) {
1363                        for ( int i = 1; i < n; ++i ) {
1364                                UntypedExpr *derefExpr = new UntypedExpr( new NameExpr( "*?" ) );
1365                                derefExpr->get_args().push_back( derefdVar );
1366                                derefdVar = derefExpr;
1367                        }
1368                        return derefdVar;
1369                }
1370               
1371                Expression *MemberExprFixer::mutate( MemberExpr *memberExpr ) {
1372                        // mutate, exiting early if no longer MemberExpr
1373                        Expression *expr = Mutator::mutate( memberExpr );
1374                        memberExpr = dynamic_cast< MemberExpr* >( expr );
1375                        if ( ! memberExpr ) return expr;
1376
1377                        // get declaration for base struct, exiting early if not found
1378                        int varDepth;
1379                        VariableExpr *varExpr = getBaseVar( memberExpr->get_aggregate(), &varDepth );
1380                        if ( ! varExpr ) return memberExpr;
1381                        ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
1382                        if ( ! objectDecl ) return memberExpr;
1383
1384                        // only mutate member expressions for polymorphic types
1385                        int tyDepth;
1386                        Type *objectType = hasPolyBase( objectDecl->get_type(), scopeTyVars, &tyDepth );
1387                        if ( ! objectType ) return memberExpr;
1388
1389                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
1390                                // look up offset index
1391                                long i = findMember( memberExpr->get_member(), structType->get_baseStruct()->get_members() );
1392                                if ( i == -1 ) return memberExpr;
1393
1394                                // replace member expression with pointer to base plus offset
1395                                UntypedExpr *fieldLoc = new UntypedExpr( new NameExpr( "?+?" ) );
1396                                fieldLoc->get_args().push_back( makeDerefdVar( varExpr->clone(), varDepth ) );
1397                                fieldLoc->get_args().push_back( makeOffsetIndex( objectType, i ) );
1398
1399                                delete memberExpr;
1400                                return fieldLoc;
1401                        } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType ) ) {
1402                                // union members are all at offset zero, so build appropriately-dereferenced variable
1403                                Expression *derefdVar = makeDerefdVar( varExpr->clone(), varDepth );
1404                                delete memberExpr;
1405                                return derefdVar;
1406                        } else return memberExpr;
1407                }
1408
1409                Expression *MemberExprFixer::mutate( OffsetofExpr *offsetofExpr ) {
1410                        // mutate, exiting early if no longer OffsetofExpr
1411                        Expression *expr = Mutator::mutate( offsetofExpr );
1412                        offsetofExpr = dynamic_cast< OffsetofExpr* >( expr );
1413                        if ( ! offsetofExpr ) return expr;
1414
1415                        // only mutate expressions for polymorphic structs/unions
1416                        Type *ty = isPolyType( offsetofExpr->get_type(), scopeTyVars );
1417                        if ( ! ty ) return offsetofExpr;
1418
1419                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( ty ) ) {
1420                                // replace offsetof expression by index into offset array
1421                                long i = findMember( offsetofExpr->get_member(), structType->get_baseStruct()->get_members() );
1422                                if ( i == -1 ) return offsetofExpr;
1423
1424                                Expression *offsetInd = makeOffsetIndex( ty, i );
1425                                delete offsetofExpr;
1426                                return offsetInd;
1427                        } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( ty ) ) {
1428                                // all union members are at offset zero
1429                                delete offsetofExpr;
1430                                return new ConstantExpr( Constant( new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt ), std::string("0") ) );
1431                        } else return offsetofExpr;
1432                }
1433
1434////////////////////////////////////////// Pass3 ////////////////////////////////////////////////////
1435
1436                template< typename DeclClass >
1437                DeclClass * Pass3::handleDecl( DeclClass *decl, Type *type ) {
1438                        TyVarMap oldtyVars = scopeTyVars;
1439                        makeTyVarMap( type, scopeTyVars );
1440
1441                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
1442                        ScrubTyVars::scrub( decl, scopeTyVars );
1443
1444                        scopeTyVars = oldtyVars;
1445                        return ret;
1446                }
1447
1448                ObjectDecl * Pass3::mutate( ObjectDecl *objectDecl ) {
1449                        return handleDecl( objectDecl, objectDecl->get_type() );
1450                }
1451
1452                DeclarationWithType * Pass3::mutate( FunctionDecl *functionDecl ) {
1453                        return handleDecl( functionDecl, functionDecl->get_functionType() );
1454                }
1455
1456                TypedefDecl * Pass3::mutate( TypedefDecl *typedefDecl ) {
1457                        return handleDecl( typedefDecl, typedefDecl->get_base() );
1458                }
1459
1460                TypeDecl * Pass3::mutate( TypeDecl *typeDecl ) {
1461//   Initializer *init = 0;
1462//   std::list< Expression *> designators;
1463//   scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1464//   if ( typeDecl->get_base() ) {
1465//     init = new SimpleInit( new SizeofExpr( handleDecl( typeDecl, typeDecl->get_base() ) ), designators );
1466//   }
1467//   return new ObjectDecl( typeDecl->get_name(), Declaration::Extern, LinkageSpec::C, 0, new BasicType( Type::Qualifiers(), BasicType::UnsignedInt ), init );
1468
1469                        scopeTyVars[ typeDecl->get_name() ] = typeDecl->get_kind();
1470                        return Mutator::mutate( typeDecl );
1471                }
1472
1473                Type * Pass3::mutate( PointerType *pointerType ) {
1474                        TyVarMap oldtyVars = scopeTyVars;
1475                        makeTyVarMap( pointerType, scopeTyVars );
1476
1477                        Type *ret = Mutator::mutate( pointerType );
1478
1479                        scopeTyVars = oldtyVars;
1480                        return ret;
1481                }
1482
1483                Type * Pass3::mutate( FunctionType *functionType ) {
1484                        TyVarMap oldtyVars = scopeTyVars;
1485                        makeTyVarMap( functionType, scopeTyVars );
1486
1487                        Type *ret = Mutator::mutate( functionType );
1488
1489                        scopeTyVars = oldtyVars;
1490                        return ret;
1491                }
1492        } // anonymous namespace
1493} // namespace GenPoly
1494
1495// Local Variables: //
1496// tab-width: 4 //
1497// mode: c++ //
1498// compile-command: "make install" //
1499// End: //
Note: See TracBrowser for help on using the repository browser.