source: src/ResolvExpr/CandidateFinder.cpp @ 432ce7a

arm-ehenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 432ce7a was 432ce7a, checked in by Aaron Moss <a3moss@…>, 4 years ago

Port CandidateFinder::postvisit for UntypedExpr?, stub dependencies

  • Property mode set to 100644
File size: 23.8 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// CandidateFinder.cpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Jun 5 14:30:00 2019
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Jun 5 14:30:00 2019
13// Update Count     : 1
14//
15
16#include "CandidateFinder.hpp"
17
18#include <deque>
19#include <iterator>               // for back_inserter
20#include <sstream>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "Candidate.hpp"
26#include "CompilationState.h"
27#include "Cost.h"
28#include "ExplodedArg.hpp"
29#include "Resolver.h"
30#include "SatisfyAssertions.hpp"
31#include "typeops.h"              // for adjustExprType
32#include "Unify.h"
33#include "AST/Expr.hpp"
34#include "AST/Node.hpp"
35#include "AST/Pass.hpp"
36#include "AST/Print.hpp"
37#include "AST/SymbolTable.hpp"
38#include "AST/Type.hpp"
39#include "SymTab/Mangler.h"
40#include "Tuples/Tuples.h"        // for handleTupleAssignment
41
42#define PRINT( text ) if ( resolvep ) { text }
43
44namespace ResolvExpr {
45
46namespace {
47
48        /// First index is which argument, second is which alternative, third is which exploded element
49        using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
50
51        /// Returns a list of alternatives with the minimum cost in the given list
52        CandidateList findMinCost( const CandidateList & candidates ) {
53                CandidateList out;
54                Cost minCost = Cost::infinity;
55                for ( const CandidateRef & r : candidates ) {
56                        if ( r->cost < minCost ) {
57                                minCost = r->cost;
58                                out.clear();
59                                out.emplace_back( r );
60                        } else if ( r->cost == minCost ) {
61                                out.emplace_back( r );
62                        }
63                }
64                return out;
65        }
66
67        /// Computes conversion cost for a given candidate
68        Cost computeApplicationConversionCost( 
69                const CandidateRef & cand, const ast::SymbolTable & symtab
70        ) {
71                #warning unimplemented
72                (void)cand; (void)symtab;
73                assert(false);
74                return Cost::infinity;
75        }
76
77        /// Actually visits expressions to find their candidate interpretations
78        struct Finder final : public ast::WithShortCircuiting {
79                CandidateFinder & selfFinder;
80                const ast::SymbolTable & symtab;
81                CandidateList & candidates;
82                const ast::TypeEnvironment & tenv;
83                ast::ptr< ast::Type > & targetType;
84
85                Finder( CandidateFinder & f )
86                : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
87                  targetType( f.targetType ) {}
88               
89                void previsit( const ast::Node * ) { visit_children = false; }
90
91                /// Convenience to add candidate to list
92                template<typename... Args>
93                void addCandidate( Args &&... args ) {
94                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
95                }
96
97                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
98                        addCandidate( applicationExpr, tenv );
99                }
100
101                /// Builds a list of candidates for a function, storing them in out
102                void makeFunctionCandidates(
103                        const CandidateRef & func, const ast::FunctionType * funcType, 
104                        const ExplodedArgs_new & args, CandidateList & out
105                ) {
106                        #warning unimplemented
107                        (void)func; (void)funcType; (void)args; (void)out;
108                        assert(false);
109                }
110
111                /// Adds implicit struct-conversions to the alternative list
112                void addAnonConversions( const CandidateRef & cand ) {
113                        #warning unimplemented
114                        (void)cand;
115                        assert(false);
116                }
117
118                void postvisit( const ast::UntypedExpr * untypedExpr ) {
119                        CandidateFinder funcFinder{ symtab, tenv };
120                        funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
121                        // short-circuit if no candidates
122                        if ( funcFinder.candidates.empty() ) return;
123
124                        std::vector< CandidateFinder > argCandidates = 
125                                selfFinder.findSubExprs( untypedExpr->args );
126                       
127                        // take care of possible tuple assignments
128                        // if not tuple assignment, handled as normal function call
129                        Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
130
131                        // find function operators
132                        ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
133                        CandidateFinder opFinder{ symtab, tenv };
134                        // okay if there aren't any function operations
135                        opFinder.find( opExpr, ResolvMode::withoutFailFast() );
136                        PRINT(
137                                std::cerr << "known function ops:" << std::endl;
138                                print( std::cerr, opFinder.candidates, 1 );
139                        )
140
141                        // pre-explode arguments
142                        ExplodedArgs_new argExpansions;
143                        for ( const CandidateFinder & args : argCandidates ) {
144                                argExpansions.emplace_back();
145                                auto & argE = argExpansions.back();
146                                for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
147                        }
148
149                        // Find function matches
150                        CandidateList found;
151                        SemanticErrorException errors;
152                        for ( CandidateRef & func : funcFinder ) {
153                                try {
154                                        PRINT(
155                                                std::cerr << "working on alternative:" << std::endl;
156                                                print( std::cerr, *func, 2 );
157                                        )
158
159                                        // check if the type is a pointer to function
160                                        const ast::Type * funcResult = func->expr->result->stripReferences();
161                                        if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
162                                                if ( auto function = pointer->base.as< ast::FunctionType >() ) {
163                                                        CandidateRef newFunc{ new Candidate{ *func } };
164                                                        newFunc->expr = 
165                                                                referenceToRvalueConversion( newFunc->expr, newFunc->cost );
166                                                        makeFunctionCandidates( newFunc, function, argExpansions, found );
167                                                }
168                                        } else if ( 
169                                                auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 
170                                        ) {
171                                                if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
172                                                        if ( auto function = clz->bound.as< ast::FunctionType >() ) {
173                                                                CandidateRef newFunc{ new Candidate{ *func } };
174                                                                newFunc->expr = 
175                                                                        referenceToRvalueConversion( newFunc->expr, newFunc->cost );
176                                                                makeFunctionCandidates( newFunc, function, argExpansions, found );
177                                                        }
178                                                }
179                                        }
180                                } catch ( SemanticErrorException & e ) { errors.append( e ); }
181                        }
182
183                        // Find matches on function operators `?()`
184                        if ( ! opFinder.candidates.empty() ) {
185                                // add exploded function alternatives to front of argument list
186                                std::vector< ExplodedArg > funcE;
187                                funcE.reserve( funcFinder.candidates.size() );
188                                for ( const CandidateRef & func : funcFinder ) { 
189                                        funcE.emplace_back( *func, symtab );
190                                }
191                                argExpansions.emplace_front( std::move( funcE ) );
192
193                                for ( const CandidateRef & op : opFinder ) {
194                                        try {
195                                                // check if type is pointer-to-function
196                                                const ast::Type * opResult = op->expr->result->stripReferences();
197                                                if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
198                                                        if ( auto function = pointer->base.as< ast::FunctionType >() ) {
199                                                                CandidateRef newOp{ new Candidate{ *op} };
200                                                                newOp->expr = 
201                                                                        referenceToRvalueConversion( newOp->expr, newOp->cost );
202                                                                makeFunctionCandidates( newOp, function, argExpansions, found );
203                                                        }
204                                                }
205                                        } catch ( SemanticErrorException & e ) { errors.append( e ); }
206                                }
207                        }
208
209                        // Implement SFINAE; resolution errors are only errors if there aren't any non-error
210                        // candidates
211                        if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
212
213                        // Compute conversion costs
214                        for ( CandidateRef & withFunc : found ) {
215                                Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
216
217                                PRINT(
218                                        auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
219                                        auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
220                                        auto function = pointer->base.strict_as< ast::FunctionType >();
221                                       
222                                        std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
223                                        std::cerr << "parameters are:" << std::endl;
224                                        ast::printAll( std::cerr, function->params, 2 );
225                                        std::cerr << "arguments are:" << std::endl;
226                                        ast::printAll( std::cerr, appExpr->args, 2 );
227                                        std::cerr << "bindings are:" << std::endl;
228                                        ast::print( std::cerr, withFunc->env, 2 );
229                                        std::cerr << "cost is: " << withFunc->cost << std::endl;
230                                        std::cerr << "cost of conversion is:" << cvtCost << std::endl;
231                                )
232
233                                if ( cvtCost != Cost::infinity ) {
234                                        withFunc->cvtCost = cvtCost;
235                                        candidates.emplace_back( std::move( withFunc ) );
236                                }
237                        }
238                        found = std::move( candidates );
239
240                        // use a new list so that candidates are not examined by addAnonConversions twice
241                        CandidateList winners = findMinCost( found );
242                        promoteCvtCost( winners );
243
244                        // function may return a struct/union value, in which case we need to add candidates
245                        // for implicit conversions to each of the anonymous members, which must happen after
246                        // `findMinCost`, since anon conversions are never the cheapest
247                        for ( const CandidateRef & c : winners ) {
248                                addAnonConversions( c );
249                        }
250                        spliceBegin( candidates, winners );
251
252                        if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
253                                // If resolution is unsuccessful with a target type, try again without, since it
254                                // will sometimes succeed when it wouldn't with a target type binding.
255                                // For example:
256                                //   forall( otype T ) T & ?[]( T *, ptrdiff_t );
257                                //   const char * x = "hello world";
258                                //   unsigned char ch = x[0];
259                                // Fails with simple return type binding (xxx -- check this!) as follows:
260                                // * T is bound to unsigned char
261                                // * (x: const char *) is unified with unsigned char *, which fails
262                                // xxx -- fix this better
263                                targetType = nullptr;
264                                postvisit( untypedExpr );
265                        }
266                }
267
268                /// true if expression is an lvalue
269                static bool isLvalue( const ast::Expr * x ) {
270                        return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
271                }
272
273                void postvisit( const ast::AddressExpr * addressExpr ) {
274                        CandidateFinder finder{ symtab, tenv };
275                        finder.find( addressExpr->arg );
276                        for ( CandidateRef & r : finder.candidates ) {
277                                if ( ! isLvalue( r->expr ) ) continue;
278                                addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
279                        }
280                }
281
282                void postvisit( const ast::LabelAddressExpr * labelExpr ) {
283                        addCandidate( labelExpr, tenv );
284                }
285
286                void postvisit( const ast::CastExpr * castExpr ) {
287                        #warning unimplemented
288                        (void)castExpr;
289                        assert(false);
290                }
291
292                void postvisit( const ast::VirtualCastExpr * castExpr ) {
293                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
294                        CandidateFinder finder{ symtab, tenv };
295                        // don't prune here, all alternatives guaranteed to have same type
296                        finder.find( castExpr->arg, ResolvMode::withoutPrune() );
297                        for ( CandidateRef & r : finder.candidates ) {
298                                addCandidate( 
299                                        *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
300                        }
301                }
302
303                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
304                        #warning unimplemented
305                        (void)memberExpr;
306                        assert(false);
307                }
308
309                void postvisit( const ast::MemberExpr * memberExpr ) {
310                        addCandidate( memberExpr, tenv );
311                }
312
313                void postvisit( const ast::NameExpr * variableExpr ) {
314                        #warning unimplemented
315                        (void)variableExpr;
316                        assert(false);
317                }
318
319                void postvisit( const ast::VariableExpr * variableExpr ) {
320                        // not sufficient to just pass `variableExpr` here, type might have changed since
321                        // creation
322                        addCandidate( 
323                                new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
324                }
325
326                void postvisit( const ast::ConstantExpr * constantExpr ) {
327                        addCandidate( constantExpr, tenv );
328                }
329
330                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
331                        #warning unimplemented
332                        (void)sizeofExpr;
333                        assert(false);
334                }
335
336                void postvisit( const ast::AlignofExpr * alignofExpr ) {
337                        #warning unimplemented
338                        (void)alignofExpr;
339                        assert(false);
340                }
341
342                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
343                        #warning unimplemented
344                        (void)offsetofExpr;
345                        assert(false);
346                }
347
348                void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
349                        addCandidate( offsetofExpr, tenv );
350                }
351
352                void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
353                        addCandidate( offsetPackExpr, tenv );
354                }
355
356                void postvisit( const ast::LogicalExpr * logicalExpr ) {
357                        CandidateFinder finder1{ symtab, tenv };
358                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
359                        if ( finder1.candidates.empty() ) return;
360
361                        CandidateFinder finder2{ symtab, tenv };
362                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
363                        if ( finder2.candidates.empty() ) return;
364
365                        for ( const CandidateRef & r1 : finder1.candidates ) {
366                                for ( const CandidateRef & r2 : finder2.candidates ) {
367                                        ast::TypeEnvironment env{ r1->env };
368                                        env.simpleCombine( r2->env );
369                                        ast::OpenVarSet open{ r1->open };
370                                        mergeOpenVars( open, r2->open );
371                                        ast::AssertionSet need;
372                                        mergeAssertionSet( need, r1->need );
373                                        mergeAssertionSet( need, r2->need );
374
375                                        addCandidate(
376                                                new ast::LogicalExpr{ 
377                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
378                                                std::move( env ), std::move( open ), std::move( need ), 
379                                                r1->cost + r2->cost );
380                                }
381                        }
382                }
383
384                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
385                        // candidates for condition
386                        CandidateFinder finder1{ symtab, tenv };
387                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
388                        if ( finder1.candidates.empty() ) return;
389
390                        // candidates for true result
391                        CandidateFinder finder2{ symtab, tenv };
392                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
393                        if ( finder2.candidates.empty() ) return;
394
395                        // candidates for false result
396                        CandidateFinder finder3{ symtab, tenv };
397                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
398                        if ( finder3.candidates.empty() ) return;
399
400                        for ( const CandidateRef & r1 : finder1.candidates ) {
401                                for ( const CandidateRef & r2 : finder2.candidates ) {
402                                        for ( const CandidateRef & r3 : finder3.candidates ) {
403                                                ast::TypeEnvironment env{ r1->env };
404                                                env.simpleCombine( r2->env );
405                                                env.simpleCombine( r3->env );
406                                                ast::OpenVarSet open{ r1->open };
407                                                mergeOpenVars( open, r2->open );
408                                                mergeOpenVars( open, r3->open );
409                                                ast::AssertionSet need;
410                                                mergeAssertionSet( need, r1->need );
411                                                mergeAssertionSet( need, r2->need );
412                                                mergeAssertionSet( need, r3->need );
413                                                ast::AssertionSet have;
414
415                                                // unify true and false results, then infer parameters to produce new
416                                                // candidates
417                                                ast::ptr< ast::Type > common;
418                                                if ( 
419                                                        unify( 
420                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab, 
421                                                                common ) 
422                                                ) {
423                                                        #warning unimplemented
424                                                        assert(false);
425                                                }
426                                        }
427                                }
428                        }
429                }
430
431                void postvisit( const ast::CommaExpr * commaExpr ) {
432                        ast::TypeEnvironment env{ tenv };
433                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
434                       
435                        CandidateFinder finder2{ symtab, env };
436                        finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
437
438                        for ( const CandidateRef & r2 : finder2.candidates ) {
439                                addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
440                        }
441                }
442
443                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
444                        addCandidate( ctorExpr, tenv );
445                }
446
447                void postvisit( const ast::ConstructorExpr * ctorExpr ) {
448                        CandidateFinder finder{ symtab, tenv };
449                        finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
450                        for ( CandidateRef & r : finder.candidates ) {
451                                addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
452                        }
453                }
454
455                void postvisit( const ast::RangeExpr * rangeExpr ) {
456                        // resolve low and high, accept candidates where low and high types unify
457                        CandidateFinder finder1{ symtab, tenv };
458                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
459                        if ( finder1.candidates.empty() ) return;
460
461                        CandidateFinder finder2{ symtab, tenv };
462                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
463                        if ( finder2.candidates.empty() ) return;
464
465                        for ( const CandidateRef & r1 : finder1.candidates ) {
466                                for ( const CandidateRef & r2 : finder2.candidates ) {
467                                        ast::TypeEnvironment env{ r1->env };
468                                        env.simpleCombine( r2->env );
469                                        ast::OpenVarSet open{ r1->open };
470                                        mergeOpenVars( open, r2->open );
471                                        ast::AssertionSet need;
472                                        mergeAssertionSet( need, r1->need );
473                                        mergeAssertionSet( need, r2->need );
474                                        ast::AssertionSet have;
475
476                                        ast::ptr< ast::Type > common;
477                                        if ( 
478                                                unify( 
479                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab, 
480                                                        common ) 
481                                        ) {
482                                                ast::RangeExpr * newExpr = 
483                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
484                                                newExpr->result = common ? common : r1->expr->result;
485                                               
486                                                #warning unimplemented
487                                                assert(false);
488                                        }
489                                }
490                        }
491                }
492
493                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
494                        std::vector< CandidateFinder > subCandidates = 
495                                selfFinder.findSubExprs( tupleExpr->exprs );
496                        std::vector< CandidateList > possibilities;
497                        combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
498
499                        for ( const CandidateList & subs : possibilities ) {
500                                std::vector< ast::ptr< ast::Expr > > exprs;
501                                exprs.reserve( subs.size() );
502                                for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
503
504                                ast::TypeEnvironment env;
505                                ast::OpenVarSet open;
506                                ast::AssertionSet need;
507                                for ( const CandidateRef & sub : subs ) {
508                                        env.simpleCombine( sub->env );
509                                        mergeOpenVars( open, sub->open );
510                                        mergeAssertionSet( need, sub->need );
511                                }
512
513                                addCandidate(
514                                        new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, 
515                                        std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
516                        }
517                }
518
519                void postvisit( const ast::TupleExpr * tupleExpr ) {
520                        addCandidate( tupleExpr, tenv );
521                }
522
523                void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
524                        addCandidate( tupleExpr, tenv );
525                }
526
527                void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
528                        addCandidate( tupleExpr, tenv );
529                }
530
531                void postvisit( const ast::UniqueExpr * unqExpr ) {
532                        CandidateFinder finder{ symtab, tenv };
533                        finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
534                        for ( CandidateRef & r : finder.candidates ) {
535                                // ensure that the the id is passed on so that the expressions are "linked"
536                                addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
537                        }
538                }
539
540                void postvisit( const ast::StmtExpr * stmtExpr ) {
541                        #warning unimplemented
542                        (void)stmtExpr;
543                        assert(false);
544                }
545
546                void postvisit( const ast::UntypedInitExpr * initExpr ) {
547                        #warning unimplemented
548                        (void)initExpr;
549                        assert(false);
550                }
551
552                void postvisit( const ast::InitExpr * ) {
553                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
554                }
555
556                void postvisit( const ast::DeletedExpr * ) {
557                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
558                }
559
560                void postvisit( const ast::GenericExpr * ) {
561                        assertf( false, "_Generic is not yet supported." );
562                }
563        };
564
565        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
566        /// return type. Skips ambiguous candidates.
567        CandidateList pruneCandidates( CandidateList & candidates ) {
568                struct PruneStruct {
569                        CandidateRef candidate;
570                        bool ambiguous;
571
572                        PruneStruct() = default;
573                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
574                };
575
576                // find lowest-cost candidate for each type
577                std::unordered_map< std::string, PruneStruct > selected;
578                for ( CandidateRef & candidate : candidates ) {
579                        std::string mangleName;
580                        {
581                                ast::ptr< ast::Type > newType = candidate->expr->result;
582                                candidate->env.apply( newType );
583                                mangleName = Mangle::mangle( newType );
584                        }
585
586                        auto found = selected.find( mangleName );
587                        if ( found != selected.end() ) {
588                                if ( candidate->cost < found->second.candidate->cost ) {
589                                        PRINT(
590                                                std::cerr << "cost " << candidate->cost << " beats " 
591                                                        << found->second.candidate->cost << std::endl;
592                                        )
593
594                                        found->second = PruneStruct{ candidate };
595                                } else if ( candidate->cost == found->second.candidate->cost ) {
596                                        // if one of the candidates contains a deleted identifier, can pick the other,
597                                        // since deleted expressions should not be ambiguous if there is another option
598                                        // that is at least as good
599                                        if ( findDeletedExpr( candidate->expr ) ) {
600                                                // do nothing
601                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
602                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
603                                                PRINT( std::cerr << "current is deleted" << std::endl; )
604                                                found->second = PruneStruct{ candidate };
605                                        } else {
606                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
607                                                found->second.ambiguous = true;
608                                        }
609                                } else {
610                                        PRINT(
611                                                std::cerr << "cost " << candidate->cost << " loses to " 
612                                                        << found->second.candidate->cost << std::endl;
613                                        )
614                                }
615                        } else {
616                                selected.emplace_hint( found, mangleName, candidate );
617                        }
618                }
619
620                // report unambiguous min-cost candidates
621                CandidateList out;
622                for ( auto & target : selected ) {
623                        if ( target.second.ambiguous ) continue;
624
625                        CandidateRef cand = target.second.candidate;
626                       
627                        ast::ptr< ast::Type > newResult = cand->expr->result;
628                        cand->env.applyFree( newResult );
629                        cand->expr = ast::mutate_field(
630                                cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
631                       
632                        out.emplace_back( cand );
633                }
634                return out;
635        }
636
637} // anonymous namespace
638
639void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
640        // Find alternatives for expression
641        ast::Pass<Finder> finder{ *this };
642        expr->accept( finder );
643
644        if ( mode.failFast && candidates.empty() ) {
645                SemanticError( expr, "No reasonable alternatives for expression " );
646        }
647
648        if ( mode.satisfyAssns || mode.prune ) {
649                // trim candidates to just those where the assertions are satisfiable
650                // - necessary pre-requisite to pruning
651                CandidateList satisfied;
652                std::vector< std::string > errors;
653                for ( auto & candidate : candidates ) {
654                        satisfyAssertions( *candidate, symtab, satisfied, errors );
655                }
656
657                // fail early if none such
658                if ( mode.failFast && satisfied.empty() ) {
659                        std::ostringstream stream;
660                        stream << "No alternatives with satisfiable assertions for " << expr << "\n";
661                        for ( const auto& err : errors ) {
662                                stream << err;
663                        }
664                        SemanticError( expr->location, stream.str() );
665                }
666
667                // reset candidates
668                candidates = std::move( satisfied );
669        }
670
671        if ( mode.prune ) {
672                // trim candidates to single best one
673                PRINT(
674                        std::cerr << "alternatives before prune:" << std::endl;
675                        print( std::cerr, candidates );
676                )
677
678                CandidateList pruned = pruneCandidates( candidates );
679               
680                if ( mode.failFast && pruned.empty() ) {
681                        std::ostringstream stream;
682                        CandidateList winners = findMinCost( candidates );
683                        stream << "Cannot choose between " << winners.size() << " alternatives for "
684                                "expression\n";
685                        ast::print( stream, expr );
686                        stream << " Alternatives are:\n";
687                        print( stream, winners, 1 );
688                        SemanticError( expr->location, stream.str() );
689                }
690
691                auto oldsize = candidates.size();
692                candidates = std::move( pruned );
693
694                PRINT(
695                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
696                )
697                PRINT(
698                        std::cerr << "there are " << candidates.size() << " alternatives after elimination" 
699                                << std::endl;
700                )
701        }
702
703        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
704        // adjusted
705        if ( mode.adjust ) {
706                for ( CandidateRef & r : candidates ) {
707                        r->expr = ast::mutate_field( 
708                                r->expr.get(), &ast::Expr::result, 
709                                adjustExprType( r->expr->result, r->env, symtab ) );
710                }
711        }
712
713        // Central location to handle gcc extension keyword, etc. for all expressions
714        for ( CandidateRef & r : candidates ) {
715                if ( r->expr->extension != expr->extension ) {
716                        r->expr.get_and_mutate()->extension = expr->extension;
717                }
718        }
719}
720
721std::vector< CandidateFinder > CandidateFinder::findSubExprs( 
722        const std::vector< ast::ptr< ast::Expr > > & xs
723) {
724        std::vector< CandidateFinder > out;
725
726        for ( const auto & x : xs ) {
727                out.emplace_back( symtab, env );
728                out.back().find( x, ResolvMode::withAdjustment() );
729               
730                PRINT(
731                        std::cerr << "findSubExprs" << std::endl;
732                        print( std::cerr, out.back().candidates );
733                )
734        }
735
736        return out;
737}
738
739} // namespace ResolvExpr
740
741// Local Variables: //
742// tab-width: 4 //
743// mode: c++ //
744// compile-command: "make install" //
745// End: //
Note: See TracBrowser for help on using the repository browser.