Changeset a32b204 for translator/ResolvExpr/AlternativeFinder.cc
- Timestamp:
- May 17, 2015, 1:19:35 PM (9 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, gc_noraii, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, string, with_gc
- Children:
- 0dd3a2f
- Parents:
- b87a5ed
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
translator/ResolvExpr/AlternativeFinder.cc
rb87a5ed ra32b204 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 // AlternativeFinder.cc -- 8 // 9 // Author : Richard C. Bilson 10 // Created On : Sat May 16 23:52:08 2015 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat May 16 23:55:30 2015 13 // Update Count : 3 14 // 15 1 16 #include <list> 2 17 #include <iterator> … … 30 45 31 46 namespace ResolvExpr { 32 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) { 33 CastExpr *castToVoid = new CastExpr( expr ); 34 35 AlternativeFinder finder( indexer, env ); 36 finder.findWithAdjustment( castToVoid ); 37 38 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0 39 // interpretations, an exception has already been thrown. 40 assert( finder.get_alternatives().size() == 1 ); 41 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr ); 42 assert( newExpr ); 43 env = finder.get_alternatives().front().env; 44 return newExpr->get_arg()->clone(); 45 } 46 47 namespace { 48 void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) { 49 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { 50 i->print( os, indent ); 51 os << std::endl; 52 } 53 } 54 55 void makeExprList( const AltList &in, std::list< Expression* > &out ) { 56 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { 57 out.push_back( i->expr->clone() ); 58 } 59 } 60 61 Cost sumCost( const AltList &in ) { 62 Cost total; 63 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { 64 total += i->cost; 65 } 66 return total; 67 } 68 69 struct PruneStruct { 70 bool isAmbiguous; 71 AltList::iterator candidate; 72 PruneStruct() {} 73 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {} 74 }; 47 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) { 48 CastExpr *castToVoid = new CastExpr( expr ); 49 50 AlternativeFinder finder( indexer, env ); 51 finder.findWithAdjustment( castToVoid ); 52 53 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0 54 // interpretations, an exception has already been thrown. 55 assert( finder.get_alternatives().size() == 1 ); 56 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr ); 57 assert( newExpr ); 58 env = finder.get_alternatives().front().env; 59 return newExpr->get_arg()->clone(); 60 } 61 62 namespace { 63 void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) { 64 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { 65 i->print( os, indent ); 66 os << std::endl; 67 } 68 } 69 70 void makeExprList( const AltList &in, std::list< Expression* > &out ) { 71 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { 72 out.push_back( i->expr->clone() ); 73 } 74 } 75 76 Cost sumCost( const AltList &in ) { 77 Cost total; 78 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { 79 total += i->cost; 80 } 81 return total; 82 } 83 84 struct PruneStruct { 85 bool isAmbiguous; 86 AltList::iterator candidate; 87 PruneStruct() {} 88 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {} 89 }; 90 91 template< typename InputIterator, typename OutputIterator > 92 void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) { 93 // select the alternatives that have the minimum conversion cost for a particular set of result types 94 std::map< std::string, PruneStruct > selected; 95 for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) { 96 PruneStruct current( candidate ); 97 std::string mangleName; 98 for ( std::list< Type* >::const_iterator retType = candidate->expr->get_results().begin(); retType != candidate->expr->get_results().end(); ++retType ) { 99 Type *newType = (*retType)->clone(); 100 candidate->env.apply( newType ); 101 mangleName += SymTab::Mangler::mangle( newType ); 102 delete newType; 103 } 104 std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName ); 105 if ( mapPlace != selected.end() ) { 106 if ( candidate->cost < mapPlace->second.candidate->cost ) { 107 PRINT( 108 std::cout << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl; 109 ) 110 selected[ mangleName ] = current; 111 } else if ( candidate->cost == mapPlace->second.candidate->cost ) { 112 PRINT( 113 std::cout << "marking ambiguous" << std::endl; 114 ) 115 mapPlace->second.isAmbiguous = true; 116 } 117 } else { 118 selected[ mangleName ] = current; 119 } 120 } 121 122 PRINT( 123 std::cout << "there are " << selected.size() << " alternatives before elimination" << std::endl; 124 ) 125 126 // accept the alternatives that were unambiguous 127 for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) { 128 if ( ! target->second.isAmbiguous ) { 129 Alternative &alt = *target->second.candidate; 130 for ( std::list< Type* >::iterator result = alt.expr->get_results().begin(); result != alt.expr->get_results().end(); ++result ) { 131 alt.env.applyFree( *result ); 132 } 133 *out++ = alt; 134 } 135 } 136 137 } 138 139 template< typename InputIterator, typename OutputIterator > 140 void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) { 141 AltList alternatives; 142 143 // select the alternatives that have the minimum parameter cost 144 Cost minCost = Cost::infinity; 145 for ( AltList::iterator i = begin; i != end; ++i ) { 146 if ( i->cost < minCost ) { 147 minCost = i->cost; 148 i->cost = i->cvtCost; 149 alternatives.clear(); 150 alternatives.push_back( *i ); 151 } else if ( i->cost == minCost ) { 152 i->cost = i->cvtCost; 153 alternatives.push_back( *i ); 154 } 155 } 156 std::copy( alternatives.begin(), alternatives.end(), out ); 157 } 158 159 template< typename InputIterator > 160 void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) { 161 while ( begin != end ) { 162 result.simpleCombine( (*begin++).env ); 163 } 164 } 165 166 void renameTypes( Expression *expr ) { 167 for ( std::list< Type* >::iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { 168 (*i)->accept( global_renamer ); 169 } 170 } 171 } 75 172 76 173 template< typename InputIterator, typename OutputIterator > 77 void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) { 78 // select the alternatives that have the minimum conversion cost for a particular set of result types 79 std::map< std::string, PruneStruct > selected; 80 for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) { 81 PruneStruct current( candidate ); 82 std::string mangleName; 83 for ( std::list< Type* >::const_iterator retType = candidate->expr->get_results().begin(); retType != candidate->expr->get_results().end(); ++retType ) { 84 Type *newType = (*retType)->clone(); 85 candidate->env.apply( newType ); 86 mangleName += SymTab::Mangler::mangle( newType ); 87 delete newType; 88 } 89 std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName ); 90 if ( mapPlace != selected.end() ) { 91 if ( candidate->cost < mapPlace->second.candidate->cost ) { 174 void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) { 175 while ( begin != end ) { 176 AlternativeFinder finder( indexer, env ); 177 finder.findWithAdjustment( *begin ); 178 // XXX either this 179 //Designators::fixDesignations( finder, (*begin++)->get_argName() ); 180 // or XXX this 181 begin++; 92 182 PRINT( 93 std::cout << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl; 94 ) 95 selected[ mangleName ] = current; 96 } else if ( candidate->cost == mapPlace->second.candidate->cost ) { 183 std::cout << "findSubExprs" << std::endl; 184 printAlts( finder.alternatives, std::cout ); 185 ) 186 *out++ = finder; 187 } 188 } 189 190 AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ) 191 : indexer( indexer ), env( env ) { 192 } 193 194 void AlternativeFinder::find( Expression *expr, bool adjust ) { 195 expr->accept( *this ); 196 if ( alternatives.empty() ) { 197 throw SemanticError( "No reasonable alternatives for expression ", expr ); 198 } 199 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) { 200 if ( adjust ) { 201 adjustExprTypeList( i->expr->get_results().begin(), i->expr->get_results().end(), i->env, indexer ); 202 } 203 } 204 PRINT( 205 std::cout << "alternatives before prune:" << std::endl; 206 printAlts( alternatives, std::cout ); 207 ) 208 AltList::iterator oldBegin = alternatives.begin(); 209 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer ); 210 if ( alternatives.begin() == oldBegin ) { 211 std::ostrstream stream; 212 stream << "Can't choose between alternatives for expression "; 213 expr->print( stream ); 214 stream << "Alternatives are:"; 215 AltList winners; 216 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); 217 printAlts( winners, stream, 8 ); 218 throw SemanticError( std::string( stream.str(), stream.pcount() ) ); 219 } 220 alternatives.erase( oldBegin, alternatives.end() ); 221 PRINT( 222 std::cout << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; 223 ) 224 } 225 226 void AlternativeFinder::findWithAdjustment( Expression *expr ) { 227 find( expr, true ); 228 } 229 230 template< typename StructOrUnionType > 231 void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const std::string &name ) { 232 std::list< Declaration* > members; 233 aggInst->lookup( name, members ); 234 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) { 235 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) { 236 alternatives.push_back( Alternative( new MemberExpr( dwt->clone(), expr->clone() ), env, newCost ) ); 237 renameTypes( alternatives.back().expr ); 238 } else { 239 assert( false ); 240 } 241 } 242 } 243 244 void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) { 245 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) ); 246 } 247 248 Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) { 249 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( alt.expr ); 250 assert( appExpr ); 251 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); 252 assert( pointer ); 253 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); 254 assert( function ); 255 256 Cost convCost( 0, 0, 0 ); 257 std::list< DeclarationWithType* >& formals = function->get_parameters(); 258 std::list< DeclarationWithType* >::iterator formal = formals.begin(); 259 std::list< Expression* >& actuals = appExpr->get_args(); 260 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { 97 261 PRINT( 98 std::cout << "marking ambiguous" << std::endl; 99 ) 100 mapPlace->second.isAmbiguous = true; 101 } 102 } else { 103 selected[ mangleName ] = current; 104 } 105 } 106 107 PRINT( 108 std::cout << "there are " << selected.size() << " alternatives before elimination" << std::endl; 109 ) 110 111 // accept the alternatives that were unambiguous 112 for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) { 113 if ( !target->second.isAmbiguous ) { 114 Alternative &alt = *target->second.candidate; 115 for ( std::list< Type* >::iterator result = alt.expr->get_results().begin(); result != alt.expr->get_results().end(); ++result ) { 116 alt.env.applyFree( *result ); 117 } 118 *out++ = alt; 119 } 120 } 121 122 } 123 124 template< typename InputIterator, typename OutputIterator > 125 void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) { 126 AltList alternatives; 127 128 // select the alternatives that have the minimum parameter cost 129 Cost minCost = Cost::infinity; 130 for ( AltList::iterator i = begin; i != end; ++i ) { 131 if ( i->cost < minCost ) { 132 minCost = i->cost; 133 i->cost = i->cvtCost; 134 alternatives.clear(); 135 alternatives.push_back( *i ); 136 } else if ( i->cost == minCost ) { 137 i->cost = i->cvtCost; 138 alternatives.push_back( *i ); 139 } 140 } 141 std::copy( alternatives.begin(), alternatives.end(), out ); 142 } 143 144 template< typename InputIterator > 145 void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) { 146 while ( begin != end ) { 147 result.simpleCombine( (*begin++).env ); 148 } 149 } 150 151 void renameTypes( Expression *expr ) { 152 for ( std::list< Type* >::iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { 153 (*i)->accept( global_renamer ); 154 } 155 } 156 } 157 158 template< typename InputIterator, typename OutputIterator > 159 void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) { 160 while ( begin != end ) { 161 AlternativeFinder finder( indexer, env ); 162 finder.findWithAdjustment( *begin ); 163 // XXX either this 164 //Designators::fixDesignations( finder, (*begin++)->get_argName() ); 165 // or XXX this 166 begin++; 167 PRINT( 168 std::cout << "findSubExprs" << std::endl; 169 printAlts( finder.alternatives, std::cout ); 170 ) 171 *out++ = finder; 172 } 173 } 174 175 AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ) 176 : indexer( indexer ), env( env ) { 177 } 178 179 void AlternativeFinder::find( Expression *expr, bool adjust ) { 180 expr->accept( *this ); 181 if ( alternatives.empty() ) { 182 throw SemanticError( "No reasonable alternatives for expression ", expr ); 183 } 184 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) { 185 if ( adjust ) { 186 adjustExprTypeList( i->expr->get_results().begin(), i->expr->get_results().end(), i->env, indexer ); 187 } 188 } 189 PRINT( 190 std::cout << "alternatives before prune:" << std::endl; 191 printAlts( alternatives, std::cout ); 192 ) 193 AltList::iterator oldBegin = alternatives.begin(); 194 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer ); 195 if ( alternatives.begin() == oldBegin ) { 196 std::ostrstream stream; 197 stream << "Can't choose between alternatives for expression "; 198 expr->print( stream ); 199 stream << "Alternatives are:"; 200 AltList winners; 201 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); 202 printAlts( winners, stream, 8 ); 203 throw SemanticError( std::string( stream.str(), stream.pcount() ) ); 204 } 205 alternatives.erase( oldBegin, alternatives.end() ); 206 PRINT( 207 std::cout << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; 208 ) 209 } 210 211 void AlternativeFinder::findWithAdjustment( Expression *expr ) { 212 find( expr, true ); 213 } 214 215 template< typename StructOrUnionType > 216 void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const std::string &name ) { 217 std::list< Declaration* > members; 218 aggInst->lookup( name, members ); 219 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) { 220 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) { 221 alternatives.push_back( Alternative( new MemberExpr( dwt->clone(), expr->clone() ), env, newCost ) ); 222 renameTypes( alternatives.back().expr ); 223 } else { 224 assert( false ); 225 } 226 } 227 } 228 229 void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) { 230 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) ); 231 } 232 233 Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) { 234 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( alt.expr ); 235 assert( appExpr ); 236 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); 237 assert( pointer ); 238 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); 239 assert( function ); 240 241 Cost convCost( 0, 0, 0 ); 242 std::list< DeclarationWithType* >& formals = function->get_parameters(); 243 std::list< DeclarationWithType* >::iterator formal = formals.begin(); 244 std::list< Expression* >& actuals = appExpr->get_args(); 245 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { 246 PRINT( 247 std::cout << "actual expression:" << std::endl; 248 (*actualExpr)->print( std::cout, 8 ); 249 std::cout << "--- results are" << std::endl; 250 printAll( (*actualExpr)->get_results(), std::cout, 8 ); 251 ) 252 std::list< DeclarationWithType* >::iterator startFormal = formal; 253 Cost actualCost; 254 for ( std::list< Type* >::iterator actual = (*actualExpr)->get_results().begin(); actual != (*actualExpr)->get_results().end(); ++actual ) { 255 if ( formal == formals.end() ) { 256 if ( function->get_isVarArgs() ) { 257 convCost += Cost( 1, 0, 0 ); 258 break; 259 } else { 262 std::cout << "actual expression:" << std::endl; 263 (*actualExpr)->print( std::cout, 8 ); 264 std::cout << "--- results are" << std::endl; 265 printAll( (*actualExpr)->get_results(), std::cout, 8 ); 266 ) 267 std::list< DeclarationWithType* >::iterator startFormal = formal; 268 Cost actualCost; 269 for ( std::list< Type* >::iterator actual = (*actualExpr)->get_results().begin(); actual != (*actualExpr)->get_results().end(); ++actual ) { 270 if ( formal == formals.end() ) { 271 if ( function->get_isVarArgs() ) { 272 convCost += Cost( 1, 0, 0 ); 273 break; 274 } else { 275 return Cost::infinity; 276 } 277 } 278 PRINT( 279 std::cout << std::endl << "converting "; 280 (*actual)->print( std::cout, 8 ); 281 std::cout << std::endl << " to "; 282 (*formal)->get_type()->print( std::cout, 8 ); 283 ) 284 Cost newCost = conversionCost( *actual, (*formal)->get_type(), indexer, alt.env ); 285 PRINT( 286 std::cout << std::endl << "cost is" << newCost << std::endl; 287 ) 288 289 if ( newCost == Cost::infinity ) { 290 return newCost; 291 } 292 convCost += newCost; 293 actualCost += newCost; 294 295 convCost += Cost( 0, polyCost( (*formal)->get_type(), alt.env, indexer ) + polyCost( *actual, alt.env, indexer ), 0 ); 296 297 formal++; 298 } 299 if ( actualCost != Cost( 0, 0, 0 ) ) { 300 std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal; 301 startFormalPlusOne++; 302 if ( formal == startFormalPlusOne ) { 303 // not a tuple type 304 Type *newType = (*startFormal)->get_type()->clone(); 305 alt.env.apply( newType ); 306 *actualExpr = new CastExpr( *actualExpr, newType ); 307 } else { 308 TupleType *newType = new TupleType( Type::Qualifiers() ); 309 for ( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) { 310 newType->get_types().push_back( (*i)->get_type()->clone() ); 311 } 312 alt.env.apply( newType ); 313 *actualExpr = new CastExpr( *actualExpr, newType ); 314 } 315 } 316 317 } 318 if ( formal != formals.end() ) { 260 319 return Cost::infinity; 261 } 262 } 320 } 321 322 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { 323 PRINT( 324 std::cout << std::endl << "converting "; 325 assert->second.actualType->print( std::cout, 8 ); 326 std::cout << std::endl << " to "; 327 assert->second.formalType->print( std::cout, 8 ); 328 ) 329 Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); 330 PRINT( 331 std::cout << std::endl << "cost of conversion is " << newCost << std::endl; 332 ) 333 if ( newCost == Cost::infinity ) { 334 return newCost; 335 } 336 convCost += newCost; 337 338 convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 ); 339 } 340 341 return convCost; 342 } 343 344 void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) { 345 for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { 346 unifiableVars[ (*tyvar)->get_name() ] = (*tyvar)->get_kind(); 347 for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { 348 needAssertions[ *assert ] = true; 349 } 350 /// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() ); 351 } 352 } 353 354 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) { 355 std::list< TypeEnvironment > toBeDone; 356 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv ); 357 // make sure we don't widen any existing bindings 358 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) { 359 i->allowWidening = false; 360 } 361 resultEnv.extractOpenVars( openVars ); 362 363 /* 364 Tuples::NameMatcher matcher( formals ); 365 try { 366 matcher.match( actuals ); 367 } catch ( Tuples::NoMatch &e ) { 368 std::cerr << "Alternative doesn't match: " << e.message << std::endl; 369 } 370 */ 371 std::list< DeclarationWithType* >::iterator formal = formals.begin(); 372 for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { 373 for ( std::list< Type* >::iterator actual = actualExpr->expr->get_results().begin(); actual != actualExpr->expr->get_results().end(); ++actual ) { 374 if ( formal == formals.end() ) { 375 return isVarArgs; 376 } 377 PRINT( 378 std::cerr << "formal type is "; 379 (*formal)->get_type()->print( std::cerr ); 380 std::cerr << std::endl << "actual type is "; 381 (*actual)->print( std::cerr ); 382 std::cerr << std::endl; 383 ) 384 if ( ! unify( (*formal)->get_type(), *actual, resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 385 return false; 386 } 387 formal++; 388 } 389 } 390 // Handling of default values 391 while ( formal != formals.end() ) { 392 if ( ObjectDecl *od = dynamic_cast<ObjectDecl *>( *formal ) ) 393 if ( SingleInit *si = dynamic_cast<SingleInit *>( od->get_init() )) 394 // so far, only constant expressions are accepted as default values 395 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) ) 396 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) 397 if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 398 // XXX Don't know if this is right 399 actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) ); 400 formal++; 401 if ( formal == formals.end()) break; 402 } 403 return false; 404 } 405 return true; 406 } 407 408 static const int recursionLimit = 10; 409 410 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) { 411 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) { 412 if ( i->second == true ) { 413 i->first->accept( indexer ); 414 } 415 } 416 } 417 418 template< typename ForwardIterator, typename OutputIterator > 419 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) { 420 if ( begin == end ) { 421 if ( newNeed.empty() ) { 422 *out++ = newAlt; 423 return; 424 } else if ( level >= recursionLimit ) { 425 throw SemanticError( "Too many recursive assertions" ); 426 } else { 427 AssertionSet newerNeed; 428 PRINT( 429 std::cerr << "recursing with new set:" << std::endl; 430 printAssertionSet( newNeed, std::cerr, 8 ); 431 ) 432 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out ); 433 return; 434 } 435 } 436 437 ForwardIterator cur = begin++; 438 if ( ! cur->second ) { 439 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out ); 440 } 441 DeclarationWithType *curDecl = cur->first; 263 442 PRINT( 264 std::cout << std::endl << "converting "; 265 (*actual)->print( std::cout, 8 ); 266 std::cout << std::endl << " to "; 267 (*formal)->get_type()->print( std::cout, 8 ); 268 ) 269 Cost newCost = conversionCost( *actual, (*formal)->get_type(), indexer, alt.env ); 270 PRINT( 271 std::cout << std::endl << "cost is" << newCost << std::endl; 272 ) 273 274 if ( newCost == Cost::infinity ) { 275 return newCost; 276 } 277 convCost += newCost; 278 actualCost += newCost; 279 280 convCost += Cost( 0, polyCost( (*formal)->get_type(), alt.env, indexer ) + polyCost( *actual, alt.env, indexer ), 0 ); 281 282 formal++; 283 } 284 if ( actualCost != Cost( 0, 0, 0 ) ) { 285 std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal; 286 startFormalPlusOne++; 287 if ( formal == startFormalPlusOne ) { 288 // not a tuple type 289 Type *newType = (*startFormal)->get_type()->clone(); 290 alt.env.apply( newType ); 291 *actualExpr = new CastExpr( *actualExpr, newType ); 292 } else { 293 TupleType *newType = new TupleType( Type::Qualifiers() ); 294 for ( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) { 295 newType->get_types().push_back( (*i)->get_type()->clone() ); 296 } 297 alt.env.apply( newType ); 298 *actualExpr = new CastExpr( *actualExpr, newType ); 299 } 300 } 301 302 } 303 if ( formal != formals.end() ) { 304 return Cost::infinity; 305 } 306 307 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { 308 PRINT( 309 std::cout << std::endl << "converting "; 310 assert->second.actualType->print( std::cout, 8 ); 311 std::cout << std::endl << " to "; 312 assert->second.formalType->print( std::cout, 8 ); 313 ) 314 Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); 315 PRINT( 316 std::cout << std::endl << "cost of conversion is " << newCost << std::endl; 317 ) 318 if ( newCost == Cost::infinity ) { 319 return newCost; 320 } 321 convCost += newCost; 322 323 convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 ); 324 } 325 326 return convCost; 327 } 328 329 void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) { 330 for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { 331 unifiableVars[ (*tyvar)->get_name() ] = (*tyvar)->get_kind(); 332 for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { 333 needAssertions[ *assert ] = true; 334 } 335 /// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() ); 336 } 337 } 338 339 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) { 340 std::list< TypeEnvironment > toBeDone; 341 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv ); 342 // make sure we don't widen any existing bindings 343 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) { 344 i->allowWidening = false; 345 } 346 resultEnv.extractOpenVars( openVars ); 347 348 /* 349 Tuples::NameMatcher matcher( formals ); 350 try { 351 matcher.match( actuals ); 352 } catch ( Tuples::NoMatch &e ) { 353 std::cerr << "Alternative doesn't match: " << e.message << std::endl; 354 } 355 */ 356 std::list< DeclarationWithType* >::iterator formal = formals.begin(); 357 for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { 358 for ( std::list< Type* >::iterator actual = actualExpr->expr->get_results().begin(); actual != actualExpr->expr->get_results().end(); ++actual ) { 359 if ( formal == formals.end() ) { 360 return isVarArgs; 361 } 362 PRINT( 363 std::cerr << "formal type is "; 364 (*formal)->get_type()->print( std::cerr ); 365 std::cerr << std::endl << "actual type is "; 366 (*actual)->print( std::cerr ); 367 std::cerr << std::endl; 368 ) 369 if ( !unify( (*formal)->get_type(), *actual, resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 370 return false; 371 } 372 formal++; 373 } 374 } 375 // Handling of default values 376 while ( formal != formals.end() ) { 377 if ( ObjectDecl *od = dynamic_cast<ObjectDecl *>( *formal ) ) 378 if ( SingleInit *si = dynamic_cast<SingleInit *>( od->get_init() )) 379 // so far, only constant expressions are accepted as default values 380 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) ) 381 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) 382 if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 383 // XXX Don't know if this is right 384 actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) ); 385 formal++; 386 if ( formal == formals.end()) break; 387 } 388 return false; 389 } 390 return true; 391 } 392 393 static const int recursionLimit = 10; 394 395 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) { 396 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) { 397 if ( i->second == true ) { 398 i->first->accept( indexer ); 399 } 400 } 401 } 402 403 template< typename ForwardIterator, typename OutputIterator > 404 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) { 405 if ( begin == end ) { 406 if ( newNeed.empty() ) { 407 *out++ = newAlt; 408 return; 409 } else if ( level >= recursionLimit ) { 410 throw SemanticError( "Too many recursive assertions" ); 411 } else { 412 AssertionSet newerNeed; 413 PRINT( 414 std::cerr << "recursing with new set:" << std::endl; 415 printAssertionSet( newNeed, std::cerr, 8 ); 416 ) 417 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out ); 418 return; 419 } 420 } 421 422 ForwardIterator cur = begin++; 423 if ( !cur->second ) { 424 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out ); 425 } 426 DeclarationWithType *curDecl = cur->first; 427 PRINT( 428 std::cerr << "inferRecursive: assertion is "; 429 curDecl->print( std::cerr ); 430 std::cerr << std::endl; 431 ) 432 std::list< DeclarationWithType* > candidates; 433 decls.lookupId( curDecl->get_name(), candidates ); 443 std::cerr << "inferRecursive: assertion is "; 444 curDecl->print( std::cerr ); 445 std::cerr << std::endl; 446 ) 447 std::list< DeclarationWithType* > candidates; 448 decls.lookupId( curDecl->get_name(), candidates ); 434 449 /// if ( candidates.empty() ) { std::cout << "no candidates!" << std::endl; } 435 for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {436 437 std::cout << "inferRecursive: candidate is ";438 (*candidate)->print( std::cout );439 std::cout << std::endl;440 )441 442 443 444 445 446 447 448 std::cerr << "unifying ";449 curDecl->get_type()->print( std::cerr );450 std::cerr << " with ";451 adjType->print( std::cerr );452 std::cerr << std::endl;453 )454 455 PRINT(456 457 458 SymTab::Indexer newDecls( decls );459 addToIndexer( newHave, newDecls );460 Alternative newerAlt( newAlt );461 newerAlt.env = newEnv;462 assert( (*candidate)->get_uniqueId() );463 Expression *varExpr = new VariableExpr( static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) ) );464 deleteAll( varExpr->get_results() );465 varExpr->get_results().clear();466 varExpr->get_results().push_front( adjType->clone() );467 PRINT(468 469 470 471 472 473 474 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );475 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions476 appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );477 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );478 479 delete adjType;480 481 }482 483 484 485 450 for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) { 451 PRINT( 452 std::cout << "inferRecursive: candidate is "; 453 (*candidate)->print( std::cout ); 454 std::cout << std::endl; 455 ) 456 AssertionSet newHave, newerNeed( newNeed ); 457 TypeEnvironment newEnv( newAlt.env ); 458 OpenVarSet newOpenVars( openVars ); 459 Type *adjType = (*candidate)->get_type()->clone(); 460 adjustExprType( adjType, newEnv, indexer ); 461 adjType->accept( global_renamer ); 462 PRINT( 463 std::cerr << "unifying "; 464 curDecl->get_type()->print( std::cerr ); 465 std::cerr << " with "; 466 adjType->print( std::cerr ); 467 std::cerr << std::endl; 468 ) 469 if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) { 470 PRINT( 471 std::cerr << "success!" << std::endl; 472 ) 473 SymTab::Indexer newDecls( decls ); 474 addToIndexer( newHave, newDecls ); 475 Alternative newerAlt( newAlt ); 476 newerAlt.env = newEnv; 477 assert( (*candidate)->get_uniqueId() ); 478 Expression *varExpr = new VariableExpr( static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) ) ); 479 deleteAll( varExpr->get_results() ); 480 varExpr->get_results().clear(); 481 varExpr->get_results().push_front( adjType->clone() ); 482 PRINT( 483 std::cout << "satisfying assertion " << curDecl->get_uniqueId() << " "; 484 curDecl->print( std::cout ); 485 std::cout << " with declaration " << (*candidate)->get_uniqueId() << " "; 486 (*candidate)->print( std::cout ); 487 std::cout << std::endl; 488 ) 489 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr ); 490 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions 491 appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr ); 492 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out ); 493 } else { 494 delete adjType; 495 } 496 } 497 } 498 499 template< typename OutputIterator > 500 void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) { 486 501 // PRINT( 487 502 // std::cout << "inferParameters: assertions needed are" << std::endl; 488 503 // printAll( need, std::cout, 8 ); 489 504 // ) 490 SymTab::Indexer decls( indexer );491 PRINT(492 493 494 495 496 497 addToIndexer( have, decls );498 AssertionSet newNeed;499 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );505 SymTab::Indexer decls( indexer ); 506 PRINT( 507 std::cout << "============= original indexer" << std::endl; 508 indexer.print( std::cout ); 509 std::cout << "============= new indexer" << std::endl; 510 decls.print( std::cout ); 511 ) 512 addToIndexer( have, decls ); 513 AssertionSet newNeed; 514 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out ); 500 515 // PRINT( 501 516 // std::cout << "declaration 14 is "; … … 503 518 // *out++ = newAlt; 504 519 // ) 505 } 506 507 template< typename OutputIterator > 508 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) { 509 OpenVarSet openVars; 510 AssertionSet resultNeed, resultHave; 511 TypeEnvironment resultEnv; 512 makeUnifiableVars( funcType, openVars, resultNeed ); 513 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) { 514 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 515 Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) ); 516 makeExprList( actualAlt, appExpr->get_args() ); 517 PRINT( 518 std::cout << "need assertions:" << std::endl; 519 printAssertionSet( resultNeed, std::cout, 8 ); 520 ) 521 inferParameters( resultNeed, resultHave, newAlt, openVars, out ); 522 } 523 } 524 525 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) { 526 bool doneInit = false; 527 AlternativeFinder funcOpFinder( indexer, env ); 528 529 AlternativeFinder funcFinder( indexer, env ); { 530 NameExpr *fname; 531 if ( ( fname = dynamic_cast<NameExpr *>( untypedExpr->get_function())) 532 && ( fname->get_name() == std::string("LabAddress")) ) { 533 alternatives.push_back( Alternative( untypedExpr, env, Cost()) ); 534 return; 535 } 536 } 537 538 funcFinder.findWithAdjustment( untypedExpr->get_function() ); 539 std::list< AlternativeFinder > argAlternatives; 540 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) ); 541 542 std::list< AltList > possibilities; 543 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); 544 545 Tuples::TupleAssignSpotter tassign( this ); 546 if ( tassign.isTupleAssignment( untypedExpr, possibilities ) ) { 547 // take care of possible tuple assignments, or discard expression 548 return; 549 } // else ... 550 551 AltList candidates; 552 553 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) { 554 PRINT( 555 std::cout << "working on alternative: " << std::endl; 556 func->print( std::cout, 8 ); 557 ) 558 // check if the type is pointer to function 559 PointerType *pointer; 560 if ( func->expr->get_results().size() == 1 && ( pointer = dynamic_cast< PointerType* >( func->expr->get_results().front() ) ) ) { 561 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { 562 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 563 // XXX 564 //Designators::check_alternative( function, *actualAlt ); 565 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); 566 } 567 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) { 568 EqvClass eqvClass; 569 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) { 570 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) { 571 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 572 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); 573 } 574 } 575 } 576 } 577 } else { 578 // seek a function operator that's compatible 579 if ( !doneInit ) { 580 doneInit = true; 581 NameExpr *opExpr = new NameExpr( "?()" ); 582 try { 583 funcOpFinder.findWithAdjustment( opExpr ); 584 } catch( SemanticError &e ) { 585 // it's ok if there aren't any defined function ops 586 } 587 PRINT( 588 std::cout << "known function ops:" << std::endl; 589 printAlts( funcOpFinder.alternatives, std::cout, 8 ); 520 } 521 522 template< typename OutputIterator > 523 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) { 524 OpenVarSet openVars; 525 AssertionSet resultNeed, resultHave; 526 TypeEnvironment resultEnv; 527 makeUnifiableVars( funcType, openVars, resultNeed ); 528 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) { 529 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 530 Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) ); 531 makeExprList( actualAlt, appExpr->get_args() ); 532 PRINT( 533 std::cout << "need assertions:" << std::endl; 534 printAssertionSet( resultNeed, std::cout, 8 ); 535 ) 536 inferParameters( resultNeed, resultHave, newAlt, openVars, out ); 537 } 538 } 539 540 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) { 541 bool doneInit = false; 542 AlternativeFinder funcOpFinder( indexer, env ); 543 544 AlternativeFinder funcFinder( indexer, env ); { 545 NameExpr *fname; 546 if ( ( fname = dynamic_cast<NameExpr *>( untypedExpr->get_function())) 547 && ( fname->get_name() == std::string("LabAddress")) ) { 548 alternatives.push_back( Alternative( untypedExpr, env, Cost()) ); 549 return; 550 } 551 } 552 553 funcFinder.findWithAdjustment( untypedExpr->get_function() ); 554 std::list< AlternativeFinder > argAlternatives; 555 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) ); 556 557 std::list< AltList > possibilities; 558 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); 559 560 Tuples::TupleAssignSpotter tassign( this ); 561 if ( tassign.isTupleAssignment( untypedExpr, possibilities ) ) { 562 // take care of possible tuple assignments, or discard expression 563 return; 564 } // else ... 565 566 AltList candidates; 567 568 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) { 569 PRINT( 570 std::cout << "working on alternative: " << std::endl; 571 func->print( std::cout, 8 ); 572 ) 573 // check if the type is pointer to function 574 PointerType *pointer; 575 if ( func->expr->get_results().size() == 1 && ( pointer = dynamic_cast< PointerType* >( func->expr->get_results().front() ) ) ) { 576 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { 577 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 578 // XXX 579 //Designators::check_alternative( function, *actualAlt ); 580 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); 581 } 582 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) { 583 EqvClass eqvClass; 584 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) { 585 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) { 586 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 587 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) ); 588 } // for 589 } // if 590 } // if 591 } // if 592 } else { 593 // seek a function operator that's compatible 594 if ( ! doneInit ) { 595 doneInit = true; 596 NameExpr *opExpr = new NameExpr( "?()" ); 597 try { 598 funcOpFinder.findWithAdjustment( opExpr ); 599 } catch( SemanticError &e ) { 600 // it's ok if there aren't any defined function ops 601 } 602 PRINT( 603 std::cout << "known function ops:" << std::endl; 604 printAlts( funcOpFinder.alternatives, std::cout, 8 ); 605 ) 606 } 607 608 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { 609 // check if the type is pointer to function 610 PointerType *pointer; 611 if ( funcOp->expr->get_results().size() == 1 612 && ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_results().front() ) ) ) { 613 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { 614 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 615 AltList currentAlt; 616 currentAlt.push_back( *func ); 617 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() ); 618 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) ); 619 } // for 620 } // if 621 } // if 622 } // for 623 } // if 624 } // for 625 626 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { 627 Cost cvtCost = computeConversionCost( *withFunc, indexer ); 628 629 PRINT( 630 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( withFunc->expr ); 631 assert( appExpr ); 632 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); 633 assert( pointer ); 634 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); 635 assert( function ); 636 std::cout << "Case +++++++++++++" << std::endl; 637 std::cout << "formals are:" << std::endl; 638 printAll( function->get_parameters(), std::cout, 8 ); 639 std::cout << "actuals are:" << std::endl; 640 printAll( appExpr->get_args(), std::cout, 8 ); 641 std::cout << "bindings are:" << std::endl; 642 withFunc->env.print( std::cout, 8 ); 643 std::cout << "cost of conversion is:" << cvtCost << std::endl; 644 ) 645 if ( cvtCost != Cost::infinity ) { 646 withFunc->cvtCost = cvtCost; 647 alternatives.push_back( *withFunc ); 648 } // if 649 } // for 650 candidates.clear(); 651 candidates.splice( candidates.end(), alternatives ); 652 653 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) ); 654 } 655 656 bool isLvalue( Expression *expr ) { 657 for ( std::list< Type* >::const_iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { 658 if ( !(*i)->get_isLvalue() ) return false; 659 } // for 660 return true; 661 } 662 663 void AlternativeFinder::visit( AddressExpr *addressExpr ) { 664 AlternativeFinder finder( indexer, env ); 665 finder.find( addressExpr->get_arg() ); 666 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 667 if ( isLvalue( i->expr ) ) { 668 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); 669 } // if 670 } // for 671 } 672 673 void AlternativeFinder::visit( CastExpr *castExpr ) { 674 for ( std::list< Type* >::iterator i = castExpr->get_results().begin(); i != castExpr->get_results().end(); ++i ) { 675 SymTab::validateType( *i, &indexer ); 676 adjustExprType( *i, env, indexer ); 677 } // for 678 679 AlternativeFinder finder( indexer, env ); 680 finder.findWithAdjustment( castExpr->get_arg() ); 681 682 AltList candidates; 683 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 684 AssertionSet needAssertions, haveAssertions; 685 OpenVarSet openVars; 686 687 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a 688 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results 689 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 690 // to. 691 int discardedValues = (*i).expr->get_results().size() - castExpr->get_results().size(); 692 if ( discardedValues < 0 ) continue; 693 std::list< Type* >::iterator candidate_end = (*i).expr->get_results().begin(); 694 std::advance( candidate_end, castExpr->get_results().size() ); 695 if ( ! unifyList( (*i).expr->get_results().begin(), candidate_end, 696 castExpr->get_results().begin(), castExpr->get_results().end(), i->env, needAssertions, haveAssertions, openVars, indexer ) ) continue; 697 Cost thisCost = castCostList( (*i).expr->get_results().begin(), candidate_end, 698 castExpr->get_results().begin(), castExpr->get_results().end(), indexer, i->env ); 699 if ( thisCost != Cost::infinity ) { 700 // count one safe conversion for each value that is thrown away 701 thisCost += Cost( 0, 0, discardedValues ); 702 CastExpr *newExpr = castExpr->clone(); 703 newExpr->set_arg( i->expr->clone() ); 704 candidates.push_back( Alternative( newExpr, i->env, i->cost, thisCost ) ); 705 } // if 706 } // for 707 708 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the 709 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice 710 // selects first based on argument cost, then on conversion cost. 711 AltList minArgCost; 712 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); 713 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); 714 } 715 716 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) { 717 AlternativeFinder funcFinder( indexer, env ); 718 funcFinder.findWithAdjustment( memberExpr->get_aggregate() ); 719 720 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) { 721 if ( agg->expr->get_results().size() == 1 ) { 722 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_results().front() ) ) { 723 addAggMembers( structInst, agg->expr, agg->cost, memberExpr->get_member() ); 724 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_results().front() ) ) { 725 addAggMembers( unionInst, agg->expr, agg->cost, memberExpr->get_member() ); 726 } // if 727 } // if 728 } // for 729 } 730 731 void AlternativeFinder::visit( MemberExpr *memberExpr ) { 732 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) ); 733 } 734 735 void AlternativeFinder::visit( NameExpr *nameExpr ) { 736 std::list< DeclarationWithType* > declList; 737 indexer.lookupId( nameExpr->get_name(), declList ); 738 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; ) 739 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) { 740 VariableExpr newExpr( *i, nameExpr->get_argName() ); 741 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); 742 PRINT( 743 std::cerr << "decl is "; 744 (*i)->print( std::cerr ); 745 std::cerr << std::endl; 746 std::cerr << "newExpr is "; 747 newExpr.print( std::cerr ); 748 std::cerr << std::endl; 749 ) 750 renameTypes( alternatives.back().expr ); 751 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) { 752 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), "" ); 753 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) { 754 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), "" ); 755 } // if 756 } // for 757 } 758 759 void AlternativeFinder::visit( VariableExpr *variableExpr ) { 760 alternatives.push_back( Alternative( variableExpr->clone(), env, Cost::zero ) ); 761 } 762 763 void AlternativeFinder::visit( ConstantExpr *constantExpr ) { 764 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) ); 765 } 766 767 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) { 768 if ( sizeofExpr->get_isType() ) { 769 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) ); 770 } else { 771 // find all alternatives for the argument to sizeof 772 AlternativeFinder finder( indexer, env ); 773 finder.find( sizeofExpr->get_expr() ); 774 // find the lowest cost alternative among the alternatives, otherwise ambiguous 775 AltList winners; 776 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); 777 if ( winners.size() != 1 ) { 778 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() ); 779 } // if 780 // return the lowest cost alternative for the argument 781 Alternative &choice = winners.front(); 782 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); 783 } // if 784 } 785 786 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) { 787 // assume no polymorphism 788 // assume no implicit conversions 789 assert( function->get_parameters().size() == 1 ); 790 PRINT( 791 std::cout << "resolvAttr: funcDecl is "; 792 funcDecl->print( std::cout ); 793 std::cout << " argType is "; 794 argType->print( std::cout ); 795 std::cout << std::endl; 590 796 ) 591 } 592 593 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { 594 // check if the type is pointer to function 595 PointerType *pointer; 596 if ( funcOp->expr->get_results().size() == 1 597 && ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_results().front() ) ) ) { 598 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { 599 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 600 AltList currentAlt; 601 currentAlt.push_back( *func ); 602 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() ); 603 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) ); 604 } 605 } 606 } 607 } 608 } 609 } 610 611 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { 612 Cost cvtCost = computeConversionCost( *withFunc, indexer ); 613 614 PRINT( 615 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( withFunc->expr ); 616 assert( appExpr ); 617 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() ); 618 assert( pointer ); 619 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ); 620 assert( function ); 621 std::cout << "Case +++++++++++++" << std::endl; 622 std::cout << "formals are:" << std::endl; 623 printAll( function->get_parameters(), std::cout, 8 ); 624 std::cout << "actuals are:" << std::endl; 625 printAll( appExpr->get_args(), std::cout, 8 ); 626 std::cout << "bindings are:" << std::endl; 627 withFunc->env.print( std::cout, 8 ); 628 std::cout << "cost of conversion is:" << cvtCost << std::endl; 629 ) 630 if ( cvtCost != Cost::infinity ) { 631 withFunc->cvtCost = cvtCost; 632 alternatives.push_back( *withFunc ); 633 } 634 } 635 candidates.clear(); 636 candidates.splice( candidates.end(), alternatives ); 637 638 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) ); 639 } 640 641 bool isLvalue( Expression *expr ) { 642 for ( std::list< Type* >::const_iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) { 643 if ( !(*i)->get_isLvalue() ) return false; 644 } 645 return true; 646 } 647 648 void AlternativeFinder::visit( AddressExpr *addressExpr ) { 649 AlternativeFinder finder( indexer, env ); 650 finder.find( addressExpr->get_arg() ); 651 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 652 if ( isLvalue( i->expr ) ) { 653 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); 654 } 655 } 656 } 657 658 void AlternativeFinder::visit( CastExpr *castExpr ) { 659 for ( std::list< Type* >::iterator i = castExpr->get_results().begin(); i != castExpr->get_results().end(); ++i ) { 660 SymTab::validateType( *i, &indexer ); 661 adjustExprType( *i, env, indexer ); 662 } 663 664 AlternativeFinder finder( indexer, env ); 665 finder.findWithAdjustment( castExpr->get_arg() ); 666 667 AltList candidates; 668 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 669 AssertionSet needAssertions, haveAssertions; 670 OpenVarSet openVars; 671 672 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a 673 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results 674 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 675 // to. 676 int discardedValues = (*i).expr->get_results().size() - castExpr->get_results().size(); 677 if ( discardedValues < 0 ) continue; 678 std::list< Type* >::iterator candidate_end = (*i).expr->get_results().begin(); 679 std::advance( candidate_end, castExpr->get_results().size() ); 680 if ( !unifyList( (*i).expr->get_results().begin(), candidate_end, 681 castExpr->get_results().begin(), castExpr->get_results().end(), i->env, needAssertions, haveAssertions, openVars, indexer ) ) continue; 682 Cost thisCost = castCostList( (*i).expr->get_results().begin(), candidate_end, 683 castExpr->get_results().begin(), castExpr->get_results().end(), indexer, i->env ); 684 if ( thisCost != Cost::infinity ) { 685 // count one safe conversion for each value that is thrown away 686 thisCost += Cost( 0, 0, discardedValues ); 687 CastExpr *newExpr = castExpr->clone(); 688 newExpr->set_arg( i->expr->clone() ); 689 candidates.push_back( Alternative( newExpr, i->env, i->cost, thisCost ) ); 690 } 691 } 692 693 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the 694 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice 695 // selects first based on argument cost, then on conversion cost. 696 AltList minArgCost; 697 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); 698 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); 699 } 700 701 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) { 702 AlternativeFinder funcFinder( indexer, env ); 703 funcFinder.findWithAdjustment( memberExpr->get_aggregate() ); 704 705 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) { 706 if ( agg->expr->get_results().size() == 1 ) { 707 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_results().front() ) ) { 708 addAggMembers( structInst, agg->expr, agg->cost, memberExpr->get_member() ); 709 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_results().front() ) ) { 710 addAggMembers( unionInst, agg->expr, agg->cost, memberExpr->get_member() ); 711 } 712 } 713 } 714 } 715 716 void AlternativeFinder::visit( MemberExpr *memberExpr ) { 717 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) ); 718 } 719 720 void AlternativeFinder::visit( NameExpr *nameExpr ) { 721 std::list< DeclarationWithType* > declList; 722 indexer.lookupId( nameExpr->get_name(), declList ); 723 PRINT( 724 std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; 725 ) 726 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) { 727 VariableExpr newExpr( *i, nameExpr->get_argName() ); 728 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); 729 PRINT( 730 std::cerr << "decl is "; 731 (*i)->print( std::cerr ); 732 std::cerr << std::endl; 733 std::cerr << "newExpr is "; 734 newExpr.print( std::cerr ); 735 std::cerr << std::endl; 736 ) 737 renameTypes( alternatives.back().expr ); 738 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) { 739 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), "" ); 740 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) { 741 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), "" ); 742 } 743 } 744 } 745 746 void AlternativeFinder::visit( VariableExpr *variableExpr ) { 747 alternatives.push_back( Alternative( variableExpr->clone(), env, Cost::zero ) ); 748 } 749 750 void AlternativeFinder::visit( ConstantExpr *constantExpr ) { 751 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) ); 752 } 753 754 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) { 755 if ( sizeofExpr->get_isType() ) { 756 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) ); 757 } else { 758 // find all alternatives for the argument to sizeof 759 AlternativeFinder finder( indexer, env ); 760 finder.find( sizeofExpr->get_expr() ); 761 // find the lowest cost alternative among the alternatives, otherwise ambiguous 762 AltList winners; 763 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); 764 if ( winners.size() != 1 ) { 765 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() ); 766 } 767 // return the lowest cost alternative for the argument 768 Alternative &choice = winners.front(); 769 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); 770 } 771 } 772 773 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) { 774 // assume no polymorphism 775 // assume no implicit conversions 776 assert( function->get_parameters().size() == 1 ); 777 PRINT( 778 std::cout << "resolvAttr: funcDecl is "; 779 funcDecl->print( std::cout ); 780 std::cout << " argType is "; 781 argType->print( std::cout ); 782 std::cout << std::endl; 783 ) 784 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) { 785 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) ); 786 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) { 787 alternatives.back().expr->get_results().push_back( (*i)->get_type()->clone() ); 788 } 789 } 790 } 791 792 void AlternativeFinder::visit( AttrExpr *attrExpr ) { 793 // assume no 'pointer-to-attribute' 794 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() ); 795 assert( nameExpr ); 796 std::list< DeclarationWithType* > attrList; 797 indexer.lookupId( nameExpr->get_name(), attrList ); 798 if ( attrExpr->get_isType() || attrExpr->get_expr() ) { 799 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { 800 // check if the type is function 801 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) { 802 // assume exactly one parameter 803 if ( function->get_parameters().size() == 1 ) { 804 if ( attrExpr->get_isType() ) { 805 resolveAttr( *i, function, attrExpr->get_type(), env ); 806 } else { 807 AlternativeFinder finder( indexer, env ); 808 finder.find( attrExpr->get_expr() ); 809 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) { 810 if ( choice->expr->get_results().size() == 1 ) { 811 resolveAttr(*i, function, choice->expr->get_results().front(), choice->env ); 812 } 813 } 814 } 815 } 816 } 817 } 818 } else { 819 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { 820 VariableExpr newExpr( *i ); 821 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); 822 renameTypes( alternatives.back().expr ); 823 } 824 } 825 } 826 827 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) { 828 AlternativeFinder firstFinder( indexer, env ); 829 firstFinder.findWithAdjustment( logicalExpr->get_arg1() ); 830 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { 831 AlternativeFinder secondFinder( indexer, first->env ); 832 secondFinder.findWithAdjustment( logicalExpr->get_arg2() ); 833 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { 834 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() ); 835 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) ); 836 } 837 } 838 } 839 840 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) { 841 AlternativeFinder firstFinder( indexer, env ); 842 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() ); 843 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { 844 AlternativeFinder secondFinder( indexer, first->env ); 845 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() ); 846 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { 847 AlternativeFinder thirdFinder( indexer, second->env ); 848 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() ); 849 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) { 850 OpenVarSet openVars; 851 AssertionSet needAssertions, haveAssertions; 852 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost ); 853 std::list< Type* > commonTypes; 854 if ( unifyList( second->expr->get_results().begin(), second->expr->get_results().end(), third->expr->get_results().begin(), third->expr->get_results().end(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) { 855 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() ); 856 std::list< Type* >::const_iterator original = second->expr->get_results().begin(); 857 std::list< Type* >::const_iterator commonType = commonTypes.begin(); 858 for ( ; original != second->expr->get_results().end() && commonType != commonTypes.end(); ++original, ++commonType ) { 859 if ( *commonType ) { 860 newExpr->get_results().push_back( *commonType ); 861 } else { 862 newExpr->get_results().push_back( (*original)->clone() ); 863 } 864 } 865 newAlt.expr = newExpr; 866 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); 867 } 868 } 869 } 870 } 871 } 872 873 void AlternativeFinder::visit( CommaExpr *commaExpr ) { 874 TypeEnvironment newEnv( env ); 875 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv ); 876 AlternativeFinder secondFinder( indexer, newEnv ); 877 secondFinder.findWithAdjustment( commaExpr->get_arg2() ); 878 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) { 879 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) ); 880 } 881 delete newFirstArg; 882 } 883 884 void AlternativeFinder::visit( TupleExpr *tupleExpr ) { 885 std::list< AlternativeFinder > subExprAlternatives; 886 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 887 std::list< AltList > possibilities; 888 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 889 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { 890 TupleExpr *newExpr = new TupleExpr; 891 makeExprList( *i, newExpr->get_exprs() ); 892 for ( std::list< Expression* >::const_iterator resultExpr = newExpr->get_exprs().begin(); resultExpr != newExpr->get_exprs().end(); ++resultExpr ) { 893 for ( std::list< Type* >::const_iterator resultType = (*resultExpr)->get_results().begin(); resultType != (*resultExpr)->get_results().end(); ++resultType ) { 894 newExpr->get_results().push_back( (*resultType)->clone() ); 895 } 896 } 897 898 TypeEnvironment compositeEnv; 899 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 900 alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) ); 901 } 902 } 797 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) { 798 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) ); 799 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) { 800 alternatives.back().expr->get_results().push_back( (*i)->get_type()->clone() ); 801 } // for 802 } // if 803 } 804 805 void AlternativeFinder::visit( AttrExpr *attrExpr ) { 806 // assume no 'pointer-to-attribute' 807 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() ); 808 assert( nameExpr ); 809 std::list< DeclarationWithType* > attrList; 810 indexer.lookupId( nameExpr->get_name(), attrList ); 811 if ( attrExpr->get_isType() || attrExpr->get_expr() ) { 812 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { 813 // check if the type is function 814 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) { 815 // assume exactly one parameter 816 if ( function->get_parameters().size() == 1 ) { 817 if ( attrExpr->get_isType() ) { 818 resolveAttr( *i, function, attrExpr->get_type(), env ); 819 } else { 820 AlternativeFinder finder( indexer, env ); 821 finder.find( attrExpr->get_expr() ); 822 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) { 823 if ( choice->expr->get_results().size() == 1 ) { 824 resolveAttr(*i, function, choice->expr->get_results().front(), choice->env ); 825 } // fi 826 } // for 827 } // if 828 } // if 829 } // if 830 } // for 831 } else { 832 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) { 833 VariableExpr newExpr( *i ); 834 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) ); 835 renameTypes( alternatives.back().expr ); 836 } // for 837 } // if 838 } 839 840 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) { 841 AlternativeFinder firstFinder( indexer, env ); 842 firstFinder.findWithAdjustment( logicalExpr->get_arg1() ); 843 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { 844 AlternativeFinder secondFinder( indexer, first->env ); 845 secondFinder.findWithAdjustment( logicalExpr->get_arg2() ); 846 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { 847 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() ); 848 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) ); 849 } 850 } 851 } 852 853 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) { 854 AlternativeFinder firstFinder( indexer, env ); 855 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() ); 856 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) { 857 AlternativeFinder secondFinder( indexer, first->env ); 858 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() ); 859 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) { 860 AlternativeFinder thirdFinder( indexer, second->env ); 861 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() ); 862 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) { 863 OpenVarSet openVars; 864 AssertionSet needAssertions, haveAssertions; 865 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost ); 866 std::list< Type* > commonTypes; 867 if ( unifyList( second->expr->get_results().begin(), second->expr->get_results().end(), third->expr->get_results().begin(), third->expr->get_results().end(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) { 868 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() ); 869 std::list< Type* >::const_iterator original = second->expr->get_results().begin(); 870 std::list< Type* >::const_iterator commonType = commonTypes.begin(); 871 for ( ; original != second->expr->get_results().end() && commonType != commonTypes.end(); ++original, ++commonType ) { 872 if ( *commonType ) { 873 newExpr->get_results().push_back( *commonType ); 874 } else { 875 newExpr->get_results().push_back( (*original)->clone() ); 876 } // if 877 } // for 878 newAlt.expr = newExpr; 879 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); 880 } // if 881 } // for 882 } // for 883 } // for 884 } 885 886 void AlternativeFinder::visit( CommaExpr *commaExpr ) { 887 TypeEnvironment newEnv( env ); 888 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv ); 889 AlternativeFinder secondFinder( indexer, newEnv ); 890 secondFinder.findWithAdjustment( commaExpr->get_arg2() ); 891 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) { 892 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) ); 893 } // for 894 delete newFirstArg; 895 } 896 897 void AlternativeFinder::visit( TupleExpr *tupleExpr ) { 898 std::list< AlternativeFinder > subExprAlternatives; 899 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 900 std::list< AltList > possibilities; 901 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 902 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { 903 TupleExpr *newExpr = new TupleExpr; 904 makeExprList( *i, newExpr->get_exprs() ); 905 for ( std::list< Expression* >::const_iterator resultExpr = newExpr->get_exprs().begin(); resultExpr != newExpr->get_exprs().end(); ++resultExpr ) { 906 for ( std::list< Type* >::const_iterator resultType = (*resultExpr)->get_results().begin(); resultType != (*resultExpr)->get_results().end(); ++resultType ) { 907 newExpr->get_results().push_back( (*resultType)->clone() ); 908 } // for 909 } // for 910 911 TypeEnvironment compositeEnv; 912 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 913 alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) ); 914 } // for 915 } 903 916 } // namespace ResolvExpr 917 918 // Local Variables: // 919 // tab-width: 4 // 920 // mode: c++ // 921 // compile-command: "make install" // 922 // End: //
Note: See TracChangeset
for help on using the changeset viewer.