source: src/Tuples/TupleAssignment.cc@ 8d182b1

Last change on this file since 8d182b1 was 0bd3faf, checked in by Andrew Beach <ajbeach@…>, 23 months ago

Removed forward declarations missed in the BaseSyntaxNode removal. Removed code and modified names to support two versions of the ast.
  • Property mode set to 100644
File size: 13.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// TupleAssignment.cc --
8//
9// Author : Rodolfo G. Esteves
10// Created On : Mon May 18 07:44:20 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Wed Mar 16 14:06:00 2022
13// Update Count : 10
14//
15
16#include <algorithm> // for transform
17#include <cassert> // for assert
18#include <iterator> // for back_insert_iterator, back...
19#include <list> // for _List_const_iterator, _Lis...
20#include <memory> // for unique_ptr, allocator_trai...
21#include <string> // for string
22#include <vector>
23
24#include "AST/Decl.hpp"
25#include "AST/Init.hpp"
26#include "AST/Pass.hpp"
27#include "AST/Stmt.hpp"
28#include "AST/TypeEnvironment.hpp"
29#include "CodeGen/OperatorTable.h"
30#include "Common/UniqueName.h" // for UniqueName
31#include "Common/utility.h" // for splice, zipWith
32#include "Explode.h" // for explode
33#include "InitTweak/GenInit.h" // for genCtorInit
34#include "InitTweak/InitTweak.h" // for getPointerBase, isAssignment
35#include "ResolvExpr/Cost.h" // for Cost
36#include "ResolvExpr/Resolver.h" // for resolveCtorInit
37#include "ResolvExpr/typeops.h" // for combos
38
39#if 0
40#define PRINT(x) x
41#else
42#define PRINT(x)
43#endif
44
45namespace Tuples {
46
47namespace {
48 /// true if `expr` is of tuple type
49 bool isTuple( const ast::Expr * expr ) {
50 if ( ! expr ) return false;
51 assert( expr->result );
52 return dynamic_cast< const ast::TupleType * >( expr->result->stripReferences() );
53 }
54
55 /// true if `expr` is of tuple type or a reference to one
56 bool refToTuple( const ast::Expr * expr ) {
57 assert( expr->result );
58 // check for function returning tuple of reference types
59 if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
60 return refToTuple( castExpr->arg );
61 } else {
62 return isTuple( expr );
63 }
64 }
65
66 /// Dispatcher for tuple (multiple and mass) assignment operations
67 class TupleAssignSpotter final {
68 /// Actually finds tuple assignment operations, by subclass
69 struct Matcher {
70 ResolvExpr::CandidateList lhs, rhs;
71 TupleAssignSpotter & spotter;
72 CodeLocation location;
73 ResolvExpr::Cost baseCost;
74 std::vector< ast::ptr< ast::ObjectDecl > > tmpDecls;
75 ast::TypeEnvironment env;
76 ast::OpenVarSet open;
77 ast::AssertionSet need;
78
79 void combineState( const ResolvExpr::Candidate & cand ) {
80 env.simpleCombine( cand.env );
81 ast::mergeOpenVars( open, cand.open );
82 need.insert( cand.need.begin(), cand.need.end() );
83 }
84
85 Matcher(
86 TupleAssignSpotter & s, const CodeLocation & loc,
87 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
88 : lhs( l ), rhs( r ), spotter( s ), location( loc ),
89 baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ), tmpDecls(),
90 env(), open(), need() {
91 for ( auto & cand : lhs ) combineState( *cand );
92 for ( auto & cand : rhs ) combineState( *cand );
93 }
94 virtual ~Matcher() = default;
95
96 virtual std::vector< ast::ptr< ast::Expr > > match() = 0;
97
98 /// removes environments from subexpressions within statement expressions, which could
99 /// throw off later passes like those in Box which rely on PolyMutator, and adds the
100 /// bindings to the env
101 struct EnvRemover {
102 /// environment to hoist ExprStmt environments to
103 ast::TypeEnvironment & tenv;
104
105 EnvRemover( ast::TypeEnvironment & e ) : tenv( e ) {}
106
107 const ast::ExprStmt * previsit( const ast::ExprStmt * stmt ) {
108 if ( stmt->expr->env ) {
109 tenv.add( *stmt->expr->env );
110 ast::ExprStmt * mut = mutate( stmt );
111 mut->expr.get_and_mutate()->env = nullptr;
112 return mut;
113 }
114 return stmt;
115 }
116 };
117
118 ast::ObjectDecl * newObject( UniqueName & namer, const ast::Expr * expr ) {
119 assert( expr->result && ! expr->result->isVoid() );
120
121 ast::ObjectDecl * ret = new ast::ObjectDecl{
122 location, namer.newName(), expr->result, new ast::SingleInit{ location, expr },
123 ast::Storage::Classes{}, ast::Linkage::Cforall };
124
125 // if expression type is a reference, just need an initializer, otherwise construct
126 if ( ! expr->result.as< ast::ReferenceType >() ) {
127 // resolve ctor/dtor for the new object
128 ast::ptr< ast::Init > ctorInit = ResolvExpr::resolveCtorInit(
129 InitTweak::genCtorInit( location, ret ), spotter.crntFinder.context );
130 // remove environments from subexpressions of stmtExpr
131 ast::Pass< EnvRemover > rm{ env };
132 ret->init = ctorInit->accept( rm );
133 }
134
135 PRINT( std::cerr << "new object: " << ret << std::endl; )
136 return ret;
137 }
138
139 ast::UntypedExpr * createFunc(
140 const std::string & fname, const ast::ObjectDecl * left,
141 const ast::ObjectDecl * right
142 ) {
143 assert( left );
144 std::vector< ast::ptr< ast::Expr > > args;
145 args.emplace_back( new ast::VariableExpr{ location, left } );
146 if ( right ) { args.emplace_back( new ast::VariableExpr{ location, right } ); }
147
148 if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
149 args.front() = new ast::AddressExpr{ location, args.front() };
150 if ( right ) { args.back() = new ast::AddressExpr{ location, args.back() }; }
151 return new ast::UntypedExpr{
152 location, new ast::NameExpr{ location, "?=?" }, std::move(args) };
153 } else {
154 return new ast::UntypedExpr{
155 location, new ast::NameExpr{ location, fname }, std::move(args) };
156 }
157 }
158 };
159
160 /// Finds mass-assignment operations
161 struct MassAssignMatcher final : public Matcher {
162 MassAssignMatcher(
163 TupleAssignSpotter & s, const CodeLocation & loc,
164 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
165 : Matcher( s, loc, l, r ) {}
166
167 std::vector< ast::ptr< ast::Expr > > match() override {
168 static UniqueName lhsNamer( "__massassign_L" );
169 static UniqueName rhsNamer( "__massassign_R" );
170 // empty tuple case falls into this matcher
171 assert( lhs.empty() ? rhs.empty() : rhs.size() <= 1 );
172
173 ast::ptr< ast::ObjectDecl > rtmp =
174 rhs.size() == 1 ? newObject( rhsNamer, rhs.front()->expr ) : nullptr;
175
176 std::vector< ast::ptr< ast::Expr > > out;
177 for ( ResolvExpr::CandidateRef & lhsCand : lhs ) {
178 // create a temporary object for each value in the LHS and create a call
179 // involving the RHS
180 ast::ptr< ast::ObjectDecl > ltmp = newObject( lhsNamer, lhsCand->expr );
181 out.emplace_back( createFunc( spotter.fname, ltmp, rtmp ) );
182 tmpDecls.emplace_back( std::move( ltmp ) );
183 }
184 if ( rtmp ) tmpDecls.emplace_back( std::move( rtmp ) );
185
186 return out;
187 }
188 };
189
190 /// Finds multiple-assignment operations
191 struct MultipleAssignMatcher final : public Matcher {
192 MultipleAssignMatcher(
193 TupleAssignSpotter & s, const CodeLocation & loc,
194 const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
195 : Matcher( s, loc, l, r ) {}
196
197 std::vector< ast::ptr< ast::Expr > > match() override {
198 static UniqueName lhsNamer( "__multassign_L" );
199 static UniqueName rhsNamer( "__multassign_R" );
200
201 if ( lhs.size() != rhs.size() ) return {};
202
203 // produce a new temporary object for each value in the LHS and RHS and pairwise
204 // create the calls
205 std::vector< ast::ptr< ast::ObjectDecl > > ltmp, rtmp;
206
207 std::vector< ast::ptr< ast::Expr > > out;
208 for ( unsigned i = 0; i < lhs.size(); ++i ) {
209 ResolvExpr::CandidateRef & lhsCand = lhs[i];
210 ResolvExpr::CandidateRef & rhsCand = rhs[i];
211
212 // convert RHS to LHS type minus one reference -- important for case where LHS
213 // is && and RHS is lvalue
214 auto lhsType = lhsCand->expr->result.strict_as< ast::ReferenceType >();
215 rhsCand->expr = new ast::CastExpr{ rhsCand->expr, lhsType->base };
216 ast::ptr< ast::ObjectDecl > lobj = newObject( lhsNamer, lhsCand->expr );
217 ast::ptr< ast::ObjectDecl > robj = newObject( rhsNamer, rhsCand->expr );
218 out.emplace_back( createFunc( spotter.fname, lobj, robj ) );
219 ltmp.emplace_back( std::move( lobj ) );
220 rtmp.emplace_back( std::move( robj ) );
221
222 // resolve the cast expression so that rhsCand return type is bound by the cast
223 // type as needed, and transfer the resulting environment
224 ResolvExpr::CandidateFinder finder( spotter.crntFinder.context, env );
225 finder.find( rhsCand->expr, ResolvExpr::ResolvMode::withAdjustment() );
226 assert( finder.candidates.size() == 1 );
227 env = std::move( finder.candidates.front()->env );
228 }
229
230 splice( tmpDecls, ltmp );
231 splice( tmpDecls, rtmp );
232
233 return out;
234 }
235 };
236
237 ResolvExpr::CandidateFinder & crntFinder;
238 std::string fname;
239 std::unique_ptr< Matcher > matcher;
240
241 public:
242 TupleAssignSpotter( ResolvExpr::CandidateFinder & f )
243 : crntFinder( f ), fname(), matcher() {}
244
245 // find left- and right-hand-sides for mass or multiple assignment
246 void spot(
247 const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args
248 ) {
249 if ( auto op = expr->func.as< ast::NameExpr >() ) {
250 // skip non-assignment functions
251 if ( ! CodeGen::isCtorDtorAssign( op->name ) ) return;
252 fname = op->name;
253
254 // handled by CandidateFinder if applicable (both odd cases)
255 if ( args.empty() || ( args.size() == 1 && CodeGen::isAssignment( fname ) ) ) {
256 return;
257 }
258
259 // look over all possible left-hand-side
260 for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) {
261 // skip non-tuple LHS
262 if ( ! refToTuple( lhsCand->expr ) ) continue;
263
264 // explode is aware of casts - ensure every LHS is sent into explode with a
265 // reference cast
266 if ( ! lhsCand->expr.as< ast::CastExpr >() ) {
267 lhsCand->expr = new ast::CastExpr{
268 lhsCand->expr, new ast::ReferenceType{ lhsCand->expr->result } };
269 }
270
271 // explode the LHS so that each field of a tuple-valued expr is assigned
272 ResolvExpr::CandidateList lhs;
273 explode( *lhsCand, crntFinder.context.symtab, back_inserter(lhs), true );
274 for ( ResolvExpr::CandidateRef & cand : lhs ) {
275 // each LHS value must be a reference - some come in with a cast, if not
276 // just cast to reference here
277 if ( ! cand->expr->result.as< ast::ReferenceType >() ) {
278 cand->expr = new ast::CastExpr{
279 cand->expr, new ast::ReferenceType{ cand->expr->result } };
280 }
281 }
282
283 if ( args.size() == 1 ) {
284 // mass default-initialization/destruction
285 ResolvExpr::CandidateList rhs{};
286 matcher.reset( new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
287 match();
288 } else if ( args.size() == 2 ) {
289 for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) {
290 ResolvExpr::CandidateList rhs;
291 if ( isTuple( rhsCand->expr ) ) {
292 // multiple assignment
293 explode( *rhsCand, crntFinder.context.symtab, back_inserter(rhs), true );
294 matcher.reset(
295 new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
296 } else {
297 // mass assignment
298 rhs.emplace_back( rhsCand );
299 matcher.reset(
300 new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
301 }
302 match();
303 }
304 } else {
305 // expand all possible RHS possibilities
306 std::vector< ResolvExpr::CandidateList > rhsCands;
307 combos(
308 std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) );
309 for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) {
310 // multiple assignment
311 ResolvExpr::CandidateList rhs;
312 explode( rhsCand, crntFinder.context.symtab, back_inserter(rhs), true );
313 matcher.reset(
314 new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
315 match();
316 }
317 }
318 }
319 }
320 }
321
322 void match() {
323 assert( matcher );
324
325 std::vector< ast::ptr< ast::Expr > > newAssigns = matcher->match();
326
327 if ( ! ( matcher->lhs.empty() && matcher->rhs.empty() ) ) {
328 // if both LHS and RHS are empty than this is the empty tuple case, wherein it's
329 // okay for newAssigns to be empty. Otherwise, return early so that no new
330 // candidates are generated
331 if ( newAssigns.empty() ) return;
332 }
333
334 ResolvExpr::CandidateList crnt;
335 // now resolve new assignments
336 for ( const ast::Expr * expr : newAssigns ) {
337 PRINT(
338 std::cerr << "== resolving tuple assign ==" << std::endl;
339 std::cerr << expr << std::endl;
340 )
341
342 ResolvExpr::CandidateFinder finder( crntFinder.context, matcher->env );
343 finder.allowVoid = true;
344
345 try {
346 finder.find( expr, ResolvExpr::ResolvMode::withAdjustment() );
347 } catch (...) {
348 // no match is not failure, just that this tuple assignment is invalid
349 return;
350 }
351
352 ResolvExpr::CandidateList & cands = finder.candidates;
353 assert( cands.size() == 1 );
354 assert( cands.front()->expr );
355 crnt.emplace_back( std::move( cands.front() ) );
356 }
357
358 // extract expressions from the assignment candidates to produce a list of assignments
359 // that together form a sigle candidate
360 std::vector< ast::ptr< ast::Expr > > solved;
361 for ( ResolvExpr::CandidateRef & cand : crnt ) {
362 solved.emplace_back( cand->expr );
363 matcher->combineState( *cand );
364 }
365
366 crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >(
367 new ast::TupleAssignExpr{
368 matcher->location, std::move( solved ), std::move( matcher->tmpDecls ) },
369 std::move( matcher->env ), std::move( matcher->open ), std::move( matcher->need ),
370 ResolvExpr::sumCost( crnt ) + matcher->baseCost ) );
371 }
372 };
373} // anonymous namespace
374
375void handleTupleAssignment(
376 ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign,
377 std::vector< ResolvExpr::CandidateFinder > & args
378) {
379 TupleAssignSpotter spotter{ finder };
380 spotter.spot( assign, args );
381}
382
383} // namespace Tuples
384
385// Local Variables: //
386// tab-width: 4 //
387// mode: c++ //
388// compile-command: "make install" //
389// End: //
Note: See TracBrowser for help on using the repository browser.