source: src/ResolvExpr/CandidateFinder.cpp @ 4b7cce6

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

Fill in CandidateFinder? boilerplate in resolver port

  • Property mode set to 100644
File size: 17.0 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 <iterator>               // for back_inserter
19#include <sstream>
20#include <string>
21#include <unordered_map>
22
23#include "Candidate.hpp"
24#include "CompilationState.h"
25#include "Cost.h"
26#include "Resolver.h"
27#include "SatisfyAssertions.hpp"
28#include "typeops.h"              // for adjustExprType
29#include "Unify.h"
30#include "AST/Expr.hpp"
31#include "AST/Node.hpp"
32#include "AST/Pass.hpp"
33#include "AST/Print.hpp"
34#include "AST/SymbolTable.hpp"
35#include "SymTab/Mangler.h"
36
37#define PRINT( text ) if ( resolvep ) { text }
38
39namespace ResolvExpr {
40
41namespace {
42
43        /// Actually visits expressions to find their candidate interpretations
44        struct Finder final : public ast::WithShortCircuiting {
45                CandidateFinder & selfFinder;
46                const ast::SymbolTable & symtab;
47                CandidateList & candidates;
48                const ast::TypeEnvironment & tenv;
49                ast::ptr< ast::Type > & targetType;
50
51                Finder( CandidateFinder & f )
52                : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
53                  targetType( f.targetType ) {}
54               
55                void previsit( const ast::Node * ) { visit_children = false; }
56
57                /// Convenience to add candidate to list
58                template<typename... Args>
59                void addCandidate( Args &&... args ) {
60                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
61                }
62
63                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
64                        addCandidate( applicationExpr, tenv );
65                }
66
67                void postvisit( const ast::UntypedExpr * untypedExpr ) {
68                        #warning unimplemented
69                        (void)untypedExpr;
70                        assert(false);
71                }
72
73                /// true if expression is an lvalue
74                static bool isLvalue( const ast::Expr * x ) {
75                        return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
76                }
77
78                void postvisit( const ast::AddressExpr * addressExpr ) {
79                        CandidateFinder finder{ symtab, tenv };
80                        finder.find( addressExpr->arg );
81                        for ( CandidateRef & r : finder.candidates ) {
82                                if ( ! isLvalue( r->expr ) ) continue;
83                                addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
84                        }
85                }
86
87                void postvisit( const ast::LabelAddressExpr * labelExpr ) {
88                        addCandidate( labelExpr, tenv );
89                }
90
91                void postvisit( const ast::CastExpr * castExpr ) {
92                        #warning unimplemented
93                        (void)castExpr;
94                        assert(false);
95                }
96
97                void postvisit( const ast::VirtualCastExpr * castExpr ) {
98                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
99                        CandidateFinder finder{ symtab, tenv };
100                        // don't prune here, all alternatives guaranteed to have same type
101                        finder.find( castExpr->arg, ResolvMode::withoutPrune() );
102                        for ( CandidateRef & r : finder.candidates ) {
103                                addCandidate( 
104                                        *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
105                        }
106                }
107
108                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
109                        #warning unimplemented
110                        (void)memberExpr;
111                        assert(false);
112                }
113
114                void postvisit( const ast::MemberExpr * memberExpr ) {
115                        addCandidate( memberExpr, tenv );
116                }
117
118                void postvisit( const ast::NameExpr * variableExpr ) {
119                        #warning unimplemented
120                        (void)variableExpr;
121                        assert(false);
122                }
123
124                void postvisit( const ast::VariableExpr * variableExpr ) {
125                        // not sufficient to just pass `variableExpr` here, type might have changed since
126                        // creation
127                        addCandidate( 
128                                new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
129                }
130
131                void postvisit( const ast::ConstantExpr * constantExpr ) {
132                        addCandidate( constantExpr, tenv );
133                }
134
135                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
136                        #warning unimplemented
137                        (void)sizeofExpr;
138                        assert(false);
139                }
140
141                void postvisit( const ast::AlignofExpr * alignofExpr ) {
142                        #warning unimplemented
143                        (void)alignofExpr;
144                        assert(false);
145                }
146
147                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
148                        #warning unimplemented
149                        (void)offsetofExpr;
150                        assert(false);
151                }
152
153                void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
154                        addCandidate( offsetofExpr, tenv );
155                }
156
157                void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
158                        addCandidate( offsetPackExpr, tenv );
159                }
160
161                void postvisit( const ast::LogicalExpr * logicalExpr ) {
162                        CandidateFinder finder1{ symtab, tenv };
163                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
164                        if ( finder1.candidates.empty() ) return;
165
166                        CandidateFinder finder2{ symtab, tenv };
167                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
168                        if ( finder2.candidates.empty() ) return;
169
170                        for ( const CandidateRef & r1 : finder1.candidates ) {
171                                for ( const CandidateRef & r2 : finder2.candidates ) {
172                                        ast::TypeEnvironment env{ r1->env };
173                                        env.simpleCombine( r2->env );
174                                        ast::OpenVarSet open{ r1->open };
175                                        mergeOpenVars( open, r2->open );
176                                        ast::AssertionSet need;
177                                        mergeAssertionSet( need, r1->need );
178                                        mergeAssertionSet( need, r2->need );
179
180                                        addCandidate(
181                                                new ast::LogicalExpr{ 
182                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
183                                                std::move( env ), std::move( open ), std::move( need ), 
184                                                r1->cost + r2->cost );
185                                }
186                        }
187                }
188
189                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
190                        // candidates for condition
191                        CandidateFinder finder1{ symtab, tenv };
192                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
193                        if ( finder1.candidates.empty() ) return;
194
195                        // candidates for true result
196                        CandidateFinder finder2{ symtab, tenv };
197                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
198                        if ( finder2.candidates.empty() ) return;
199
200                        // candidates for false result
201                        CandidateFinder finder3{ symtab, tenv };
202                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
203                        if ( finder3.candidates.empty() ) return;
204
205                        for ( const CandidateRef & r1 : finder1.candidates ) {
206                                for ( const CandidateRef & r2 : finder2.candidates ) {
207                                        for ( const CandidateRef & r3 : finder3.candidates ) {
208                                                ast::TypeEnvironment env{ r1->env };
209                                                env.simpleCombine( r2->env );
210                                                env.simpleCombine( r3->env );
211                                                ast::OpenVarSet open{ r1->open };
212                                                mergeOpenVars( open, r2->open );
213                                                mergeOpenVars( open, r3->open );
214                                                ast::AssertionSet need;
215                                                mergeAssertionSet( need, r1->need );
216                                                mergeAssertionSet( need, r2->need );
217                                                mergeAssertionSet( need, r3->need );
218                                                ast::AssertionSet have;
219
220                                                // unify true and false results, then infer parameters to produce new
221                                                // candidates
222                                                ast::ptr< ast::Type > common;
223                                                if ( 
224                                                        unify( 
225                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab, 
226                                                                common ) 
227                                                ) {
228                                                        #warning unimplemented
229                                                        assert(false);
230                                                }
231                                        }
232                                }
233                        }
234                }
235
236                void postvisit( const ast::CommaExpr * commaExpr ) {
237                        ast::TypeEnvironment env{ tenv };
238                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
239                       
240                        CandidateFinder finder2{ symtab, env };
241                        finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
242
243                        for ( const CandidateRef & r2 : finder2.candidates ) {
244                                addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
245                        }
246                }
247
248                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
249                        addCandidate( ctorExpr, tenv );
250                }
251
252                void postvisit( const ast::ConstructorExpr * ctorExpr ) {
253                        CandidateFinder finder{ symtab, tenv };
254                        finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
255                        for ( CandidateRef & r : finder.candidates ) {
256                                addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
257                        }
258                }
259
260                void postvisit( const ast::RangeExpr * rangeExpr ) {
261                        // resolve low and high, accept candidates where low and high types unify
262                        CandidateFinder finder1{ symtab, tenv };
263                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
264                        if ( finder1.candidates.empty() ) return;
265
266                        CandidateFinder finder2{ symtab, tenv };
267                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
268                        if ( finder2.candidates.empty() ) return;
269
270                        for ( const CandidateRef & r1 : finder1.candidates ) {
271                                for ( const CandidateRef & r2 : finder2.candidates ) {
272                                        ast::TypeEnvironment env{ r1->env };
273                                        env.simpleCombine( r2->env );
274                                        ast::OpenVarSet open{ r1->open };
275                                        mergeOpenVars( open, r2->open );
276                                        ast::AssertionSet need;
277                                        mergeAssertionSet( need, r1->need );
278                                        mergeAssertionSet( need, r2->need );
279                                        ast::AssertionSet have;
280
281                                        ast::ptr< ast::Type > common;
282                                        if ( 
283                                                unify( 
284                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab, 
285                                                        common ) 
286                                        ) {
287                                                ast::RangeExpr * newExpr = 
288                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
289                                                newExpr->result = common ? common : r1->expr->result;
290                                               
291                                                #warning unimplemented
292                                                assert(false);
293                                        }
294                                }
295                        }
296                }
297
298                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
299                        std::vector< CandidateFinder > subCandidates = 
300                                selfFinder.findSubExprs( tupleExpr->exprs );
301                        std::vector< CandidateList > possibilities;
302                        combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
303
304                        for ( const CandidateList & subs : possibilities ) {
305                                std::vector< ast::ptr< ast::Expr > > exprs;
306                                exprs.reserve( subs.size() );
307                                for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
308
309                                ast::TypeEnvironment env;
310                                ast::OpenVarSet open;
311                                ast::AssertionSet need;
312                                for ( const CandidateRef & sub : subs ) {
313                                        env.simpleCombine( sub->env );
314                                        mergeOpenVars( open, sub->open );
315                                        mergeAssertionSet( need, sub->need );
316                                }
317
318                                addCandidate(
319                                        new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, 
320                                        std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
321                        }
322                }
323
324                void postvisit( const ast::TupleExpr * tupleExpr ) {
325                        addCandidate( tupleExpr, tenv );
326                }
327
328                void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
329                        addCandidate( tupleExpr, tenv );
330                }
331
332                void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
333                        addCandidate( tupleExpr, tenv );
334                }
335
336                void postvisit( const ast::UniqueExpr * unqExpr ) {
337                        CandidateFinder finder{ symtab, tenv };
338                        finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
339                        for ( CandidateRef & r : finder.candidates ) {
340                                // ensure that the the id is passed on so that the expressions are "linked"
341                                addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
342                        }
343                }
344
345                void postvisit( const ast::StmtExpr * stmtExpr ) {
346                        #warning unimplemented
347                        (void)stmtExpr;
348                        assert(false);
349                }
350
351                void postvisit( const ast::UntypedInitExpr * initExpr ) {
352                        #warning unimplemented
353                        (void)initExpr;
354                        assert(false);
355                }
356
357                void postvisit( const ast::InitExpr * ) {
358                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
359                }
360
361                void postvisit( const ast::DeletedExpr * ) {
362                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
363                }
364
365                void postvisit( const ast::GenericExpr * ) {
366                        assertf( false, "_Generic is not yet supported." );
367                }
368        };
369
370        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
371        /// return type. Skips ambiguous candidates.
372        CandidateList pruneCandidates( CandidateList & candidates ) {
373                struct PruneStruct {
374                        CandidateRef candidate;
375                        bool ambiguous;
376
377                        PruneStruct() = default;
378                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
379                };
380
381                // find lowest-cost candidate for each type
382                std::unordered_map< std::string, PruneStruct > selected;
383                for ( CandidateRef & candidate : candidates ) {
384                        std::string mangleName;
385                        {
386                                ast::ptr< ast::Type > newType = candidate->expr->result;
387                                candidate->env.apply( newType );
388                                mangleName = Mangle::mangle( newType );
389                        }
390
391                        auto found = selected.find( mangleName );
392                        if ( found != selected.end() ) {
393                                if ( candidate->cost < found->second.candidate->cost ) {
394                                        PRINT(
395                                                std::cerr << "cost " << candidate->cost << " beats " 
396                                                        << found->second.candidate->cost << std::endl;
397                                        )
398
399                                        found->second = PruneStruct{ candidate };
400                                } else if ( candidate->cost == found->second.candidate->cost ) {
401                                        // if one of the candidates contains a deleted identifier, can pick the other,
402                                        // since deleted expressions should not be ambiguous if there is another option
403                                        // that is at least as good
404                                        if ( findDeletedExpr( candidate->expr ) ) {
405                                                // do nothing
406                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
407                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
408                                                PRINT( std::cerr << "current is deleted" << std::endl; )
409                                                found->second = PruneStruct{ candidate };
410                                        } else {
411                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
412                                                found->second.ambiguous = true;
413                                        }
414                                } else {
415                                        PRINT(
416                                                std::cerr << "cost " << candidate->cost << " loses to " 
417                                                        << found->second.candidate->cost << std::endl;
418                                        )
419                                }
420                        } else {
421                                selected.emplace_hint( found, mangleName, candidate );
422                        }
423                }
424
425                // report unambiguous min-cost candidates
426                CandidateList out;
427                for ( auto & target : selected ) {
428                        if ( target.second.ambiguous ) continue;
429
430                        CandidateRef cand = target.second.candidate;
431                       
432                        ast::ptr< ast::Type > newResult = cand->expr->result;
433                        cand->env.applyFree( newResult );
434                        cand->expr = ast::mutate_field(
435                                cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
436                       
437                        out.emplace_back( cand );
438                }
439                return out;
440        }
441
442        /// Returns a list of alternatives with the minimum cost in the given list
443        CandidateList findMinCost( const CandidateList & candidates ) {
444                CandidateList out;
445                Cost minCost = Cost::infinity;
446                for ( const CandidateRef & r : candidates ) {
447                        if ( r->cost < minCost ) {
448                                minCost = r->cost;
449                                out.clear();
450                                out.emplace_back( r );
451                        } else if ( r->cost == minCost ) {
452                                out.emplace_back( r );
453                        }
454                }
455                return out;
456        }
457
458} // anonymous namespace
459
460void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
461        // Find alternatives for expression
462        ast::Pass<Finder> finder{ *this };
463        expr->accept( finder );
464
465        if ( mode.failFast && candidates.empty() ) {
466                SemanticError( expr, "No reasonable alternatives for expression " );
467        }
468
469        if ( mode.satisfyAssns || mode.prune ) {
470                // trim candidates to just those where the assertions are satisfiable
471                // - necessary pre-requisite to pruning
472                CandidateList satisfied;
473                std::vector< std::string > errors;
474                for ( auto & candidate : candidates ) {
475                        satisfyAssertions( *candidate, symtab, satisfied, errors );
476                }
477
478                // fail early if none such
479                if ( mode.failFast && satisfied.empty() ) {
480                        std::ostringstream stream;
481                        stream << "No alternatives with satisfiable assertions for " << expr << "\n";
482                        for ( const auto& err : errors ) {
483                                stream << err;
484                        }
485                        SemanticError( expr->location, stream.str() );
486                }
487
488                // reset candidates
489                candidates = std::move( satisfied );
490        }
491
492        if ( mode.prune ) {
493                // trim candidates to single best one
494                PRINT(
495                        std::cerr << "alternatives before prune:" << std::endl;
496                        print( std::cerr, candidates );
497                )
498
499                CandidateList pruned = pruneCandidates( candidates );
500               
501                if ( mode.failFast && pruned.empty() ) {
502                        std::ostringstream stream;
503                        CandidateList winners = findMinCost( candidates );
504                        stream << "Cannot choose between " << winners.size() << " alternatives for "
505                                "expression\n";
506                        ast::print( stream, expr );
507                        stream << " Alternatives are:\n";
508                        print( stream, winners, 1 );
509                        SemanticError( expr->location, stream.str() );
510                }
511
512                auto oldsize = candidates.size();
513                candidates = std::move( pruned );
514
515                PRINT(
516                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
517                )
518                PRINT(
519                        std::cerr << "there are " << candidates.size() << " alternatives after elimination" 
520                                << std::endl;
521                )
522        }
523
524        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
525        // adjusted
526        if ( mode.adjust ) {
527                for ( CandidateRef & r : candidates ) {
528                        r->expr = ast::mutate_field( 
529                                r->expr.get(), &ast::Expr::result, 
530                                adjustExprType( r->expr->result, r->env, symtab ) );
531                }
532        }
533
534        // Central location to handle gcc extension keyword, etc. for all expressions
535        for ( CandidateRef & r : candidates ) {
536                if ( r->expr->extension != expr->extension ) {
537                        r->expr.get_and_mutate()->extension = expr->extension;
538                }
539        }
540}
541
542std::vector< CandidateFinder > CandidateFinder::findSubExprs( 
543        const std::vector< ast::ptr< ast::Expr > > & xs
544) {
545        std::vector< CandidateFinder > out;
546
547        for ( const auto & x : xs ) {
548                out.emplace_back( symtab, env );
549                out.back().find( x, ResolvMode::withAdjustment() );
550               
551                PRINT(
552                        std::cerr << "findSubExprs" << std::endl;
553                        print( std::cerr, out.back().candidates );
554                )
555        }
556
557        return out;
558}
559
560} // namespace ResolvExpr
561
562// Local Variables: //
563// tab-width: 4 //
564// mode: c++ //
565// compile-command: "make install" //
566// End: //
Note: See TracBrowser for help on using the repository browser.