Context Navigation

source: src/Tuples/TupleAssignment.cc @ 3f219eb

Last change on this file since 3f219eb was 0bd3faf, checked in by Andrew Beach <ajbeach@…>, 12 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
45	namespace Tuples {
46
47	namespace {
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
375	void 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.

Download in other formats: