source: src/ResolvExpr/CandidateFinder.cpp @ d57e349

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since d57e349 was d57e349, checked in by Aaron Moss <a3moss@…>, 5 years ago

More resolver porting

  • Property mode set to 100644
File size: 7.1 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 <sstream>
19#include <string>
20#include <unordered_map>
21
22#include "Candidate.hpp"
23#include "CompilationState.h"
24#include "Cost.h"
25#include "Resolver.h"
26#include "SatisfyAssertions.hpp"
27#include "typeops.h"              // for adjustExprType
28#include "AST/Expr.hpp"
29#include "AST/Node.hpp"
30#include "AST/Pass.hpp"
31#include "AST/Print.hpp"
32#include "SymTab/Mangler.h"
33
34#define PRINT( text ) if ( resolvep ) { text }
35
36namespace ResolvExpr {
37
38namespace {
39
40        /// Actually visits expressions to find their candidate interpretations
41        struct Finder {
42                CandidateFinder & candFinder;
43                const ast::SymbolTable & symtab;
44                CandidateList & candidates;
45                const ast::TypeEnvironment & tenv;
46                ast::ptr< ast::Type > & targetType;
47
48                Finder( CandidateFinder & f )
49                : candFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
50                  targetType( f.targetType ) {}
51               
52                #warning unimplemented
53        };
54
55        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
56        /// return type. Skips ambiguous candidates.
57        CandidateList pruneCandidates( CandidateList & candidates ) {
58                struct PruneStruct {
59                        CandidateRef candidate;
60                        bool ambiguous;
61
62                        PruneStruct() = default;
63                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
64                };
65
66                // find lowest-cost candidate for each type
67                std::unordered_map< std::string, PruneStruct > selected;
68                for ( CandidateRef & candidate : candidates ) {
69                        std::string mangleName;
70                        {
71                                ast::ptr< ast::Type > newType = candidate->expr->result;
72                                candidate->env.apply( newType );
73                                mangleName = Mangle::mangle( newType );
74                        }
75
76                        auto found = selected.find( mangleName );
77                        if ( found != selected.end() ) {
78                                if ( candidate->cost < found->second.candidate->cost ) {
79                                        PRINT(
80                                                std::cerr << "cost " << candidate->cost << " beats " 
81                                                        << found->second.candidate->cost << std::endl;
82                                        )
83
84                                        found->second = PruneStruct{ candidate };
85                                } else if ( candidate->cost == found->second.candidate->cost ) {
86                                        // if one of the candidates contains a deleted identifier, can pick the other,
87                                        // since deleted expressions should not be ambiguous if there is another option
88                                        // that is at least as good
89                                        if ( findDeletedExpr( candidate->expr ) ) {
90                                                // do nothing
91                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
92                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
93                                                PRINT( std::cerr << "current is deleted" << std::endl; )
94                                                found->second = PruneStruct{ candidate };
95                                        } else {
96                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
97                                                found->second.ambiguous = true;
98                                        }
99                                } else {
100                                        PRINT(
101                                                std::cerr << "cost " << candidate->cost << " loses to " 
102                                                        << found->second.candidate->cost << std::endl;
103                                        )
104                                }
105                        } else {
106                                selected.emplace_hint( found, mangleName, candidate );
107                        }
108                }
109
110                // report unambiguous min-cost candidates
111                CandidateList out;
112                for ( auto & target : selected ) {
113                        if ( target.second.ambiguous ) continue;
114
115                        CandidateRef cand = target.second.candidate;
116                       
117                        ast::ptr< ast::Type > newResult = cand->expr->result;
118                        cand->env.applyFree( newResult );
119                        cand->expr = ast::mutate_field(
120                                cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
121                       
122                        out.emplace_back( cand );
123                }
124                return out;
125        }
126
127        /// Returns a list of alternatives with the minimum cost in the given list
128        CandidateList findMinCost( const CandidateList & candidates ) {
129                CandidateList out;
130                Cost minCost = Cost::infinity;
131                for ( const CandidateRef & r : candidates ) {
132                        if ( r->cost < minCost ) {
133                                minCost = r->cost;
134                                out.clear();
135                                out.emplace_back( r );
136                        } else if ( r->cost == minCost ) {
137                                out.emplace_back( r );
138                        }
139                }
140                return out;
141        }
142
143} // anonymous namespace
144
145void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
146        // Find alternatives for expression
147        ast::Pass<Finder> finder{ *this };
148        expr->accept( finder );
149
150        if ( mode.failFast && candidates.empty() ) {
151                SemanticError( expr, "No reasonable alternatives for expression " );
152        }
153
154        if ( mode.satisfyAssns || mode.prune ) {
155                // trim candidates to just those where the assertions are satisfiable
156                // - necessary pre-requisite to pruning
157                CandidateList satisfied;
158                std::vector< std::string > errors;
159                for ( auto & candidate : candidates ) {
160                        satisfyAssertions( *candidate, symtab, satisfied, errors );
161                }
162
163                // fail early if none such
164                if ( mode.failFast && satisfied.empty() ) {
165                        std::ostringstream stream;
166                        stream << "No alternatives with satisfiable assertions for " << expr << "\n";
167                        for ( const auto& err : errors ) {
168                                stream << err;
169                        }
170                        SemanticError( expr->location, stream.str() );
171                }
172
173                // reset candidates
174                candidates = std::move( satisfied );
175        }
176
177        if ( mode.prune ) {
178                // trim candidates to single best one
179                PRINT(
180                        std::cerr << "alternatives before prune:" << std::endl;
181                        print( std::cerr, candidates );
182                )
183
184                CandidateList pruned = pruneCandidates( candidates );
185               
186                if ( mode.failFast && pruned.empty() ) {
187                        std::ostringstream stream;
188                        CandidateList winners = findMinCost( candidates );
189                        stream << "Cannot choose between " << winners.size() << " alternatives for "
190                                "expression\n";
191                        ast::print( stream, expr );
192                        stream << " Alternatives are:\n";
193                        print( stream, winners, 1 );
194                        SemanticError( expr->location, stream.str() );
195                }
196
197                auto oldsize = candidates.size();
198                candidates = std::move( pruned );
199
200                PRINT(
201                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
202                )
203                PRINT(
204                        std::cerr << "there are " << candidates.size() << " alternatives after elimination" 
205                                << std::endl;
206                )
207        }
208
209        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
210        // adjusted
211        if ( mode.adjust ) {
212                for ( CandidateRef & r : candidates ) {
213                        r->expr = ast::mutate_field( 
214                                r->expr.get(), &ast::Expr::result, 
215                                adjustExprType( r->expr->result, r->env, symtab ) );
216                }
217        }
218
219        // Central location to handle gcc extension keyword, etc. for all expressions
220        for ( CandidateRef & r : candidates ) {
221                if ( r->expr->extension != expr->extension ) {
222                        r->expr.get_and_mutate()->extension = expr->extension;
223                }
224        }
225}
226
227std::vector< CandidateFinder > CandidateFinder::findSubExprs( 
228        const std::vector< ast::ptr< ast::Expr > > & xs
229) {
230        std::vector< CandidateFinder > out;
231
232        for ( const auto & x : xs ) {
233                out.emplace_back( symtab, env );
234                out.back().find( x, ResolvMode::withAdjustment() );
235               
236                PRINT(
237                        std::cerr << "findSubExprs" << std::endl;
238                        print( std::cerr, out.back().candidates );
239                )
240        }
241
242        return out;
243}
244
245} // namespace ResolvExpr
246
247// Local Variables: //
248// tab-width: 4 //
249// mode: c++ //
250// compile-command: "make install" //
251// End: //
Note: See TracBrowser for help on using the repository browser.