source: src/Tuples/Explode.h

Last change on this file was f53acdf, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Merge branch 'master' into new-ast

  • Property mode set to 100644
File size: 10.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// Explode.h --
8//
9// Author           : Rob Schluntz
10// Created On       : Wed Nov 9 13:12:24 2016
11// Last Modified By : Andrew Beach
12// Last Modified On : Mon Jun 17 14:36:00 2019
13// Update Count     : 4
14//
15
16#pragma once
17
18#include <iterator>                     // for back_inserter, back_insert_iterator
19#include <utility>                      // for forward
20
21#include "AST/Expr.hpp"
22#include "ResolvExpr/Alternative.h"     // for Alternative, AltList
23#include "ResolvExpr/Candidate.hpp"     // for Candidate, CandidateList
24#include "ResolvExpr/ExplodedActual.h"  // for ExplodedActual
25#include "ResolvExpr/ExplodedArg.hpp"   // for ExplodedArg
26#include "SynTree/Expression.h"         // for Expression, UniqueExpr, AddressExpr
27#include "SynTree/Type.h"               // for TupleType, Type
28#include "Tuples.h"                     // for maybeImpure
29
30namespace ast {
31        class SymbolTable;
32}
33
34namespace SymTab {
35class Indexer;
36}  // namespace SymTab
37
38namespace Tuples {
39        Expression * distributeReference( Expression * );
40
41        static inline CastExpr * isReferenceCast( Expression * expr ) {
42                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
43                        if ( dynamic_cast< ReferenceType * >( castExpr->result ) ) {
44                                return castExpr;
45                        }
46                }
47                return nullptr;
48        }
49
50        /// Append alternative to an OutputIterator of Alternatives
51        template<typename OutputIterator>
52        void append( OutputIterator out, Expression* expr, const ResolvExpr::TypeEnvironment& env,
53                        const ResolvExpr::OpenVarSet& openVars, const ResolvExpr::AssertionList& need,
54                        const ResolvExpr::Cost& cost, const ResolvExpr::Cost& cvtCost ) {
55                *out++ = ResolvExpr::Alternative{ expr, env, openVars, need, cost, cvtCost };
56        }
57
58        /// Append alternative to an ExplodedActual
59        static inline void append( ResolvExpr::ExplodedActual& ea, Expression* expr,
60                        const ResolvExpr::TypeEnvironment&, const ResolvExpr::OpenVarSet&,
61                        const ResolvExpr::AssertionList&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
62                ea.exprs.emplace_back( expr );
63                /// xxx -- merge environment, openVars, need, cost?
64        }
65
66        /// helper function used by explode
67        template< typename Output >
68        void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt,
69                        const SymTab::Indexer & indexer, Output&& out, bool isTupleAssign ) {
70                if ( isTupleAssign ) {
71                        // tuple assignment needs CastExprs to be recursively exploded to easily get at all of the components
72                        if ( CastExpr * castExpr = isReferenceCast( expr ) ) {
73                                ResolvExpr::AltList alts;
74                                explodeUnique(
75                                        castExpr->get_arg(), alt, indexer, back_inserter( alts ), isTupleAssign );
76                                for ( ResolvExpr::Alternative & alt : alts ) {
77                                        // distribute reference cast over all components
78                                        append( std::forward<Output>(out), distributeReference( alt.release_expr() ),
79                                                alt.env, alt.openVars, alt.need, alt.cost, alt.cvtCost );
80                                }
81                                // in tuple assignment, still need to handle the other cases, but only if not already handled here (don't want to output too many alternatives)
82                                return;
83                        }
84                }
85                Type * res = expr->get_result()->stripReferences();
86                if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) {
87                        if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) {
88                                // can open tuple expr and dump its exploded components
89                                for ( Expression * expr : tupleExpr->get_exprs() ) {
90                                        explodeUnique( expr, alt, indexer, std::forward<Output>(out), isTupleAssign );
91                                }
92                        } else {
93                                // tuple type, but not tuple expr - recursively index into its components.
94                                // if expr type is reference, convert to value type
95                                Expression * arg = expr->clone();
96                                if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
97                                        // expressions which may contain side effects require a single unique instance of the expression.
98                                        arg = new UniqueExpr( arg );
99                                }
100                                // cast reference to value type to facilitate further explosion
101                                if ( dynamic_cast<ReferenceType *>( arg->get_result() ) ) {
102                                        arg = new CastExpr( arg, tupleType->clone() );
103                                }
104                                for ( unsigned int i = 0; i < tupleType->size(); i++ ) {
105                                        TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i );
106                                        explodeUnique( idx, alt, indexer, std::forward<Output>(out), isTupleAssign );
107                                        delete idx;
108                                }
109                                delete arg;
110                        }
111                } else {
112                        // atomic (non-tuple) type - output a clone of the expression in a new alternative
113                        append( std::forward<Output>(out), expr->clone(), alt.env, alt.openVars, alt.need,
114                                alt.cost, alt.cvtCost );
115                }
116        }
117
118        /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type
119        template< typename Output >
120        void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer,
121                        Output&& out, bool isTupleAssign = false ) {
122                explodeUnique( alt.expr, alt, indexer, std::forward<Output>(out), isTupleAssign );
123        }
124
125        // explode list of alternatives
126        template< typename AltIterator, typename Output >
127        void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer,
128                        Output&& out, bool isTupleAssign = false ) {
129                for ( ; altBegin != altEnd; ++altBegin ) {
130                        explode( *altBegin, indexer, std::forward<Output>(out), isTupleAssign );
131                }
132        }
133
134        template< typename Output >
135        void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, Output&& out,
136                        bool isTupleAssign = false ) {
137                explode( alts.begin(), alts.end(), indexer, std::forward<Output>(out), isTupleAssign );
138        }
139
140const ast::Expr * distributeReference( const ast::Expr * );
141
142/// Append candidate to an OutputIterator of Candidates.
143template<typename OutputIterator>
144void append( OutputIterator out, const ast::Expr * expr, const ast::TypeEnvironment & env,
145                const ast::OpenVarSet & open, const ast::AssertionList & need,
146                const ResolvExpr::Cost & cost, const ResolvExpr::Cost & cvtCost ) {
147        ast::TypeEnvironment copyEnv = env;
148        ast::OpenVarSet copyOpen = open;
149        ast::AssertionSet set;
150        mergeAssertionSet( set, need );
151        *out++ = std::make_shared<ResolvExpr::Candidate>( expr, std::move( copyEnv ),
152                std::move( copyOpen ), std::move( set ), cost, cvtCost );
153}
154
155/// Append candidate to an ExplodedArg.
156static inline void append( ResolvExpr::ExplodedArg& ea, const ast::Expr * expr,
157                const ast::TypeEnvironment&, const ast::OpenVarSet&,
158                const ast::AssertionList&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
159        // I'm not sure why most of the arguments are unused. But they were in the old version.
160        ea.exprs.emplace_back( expr );
161}
162
163/// Check if the expression is a cast to a reference type, return it if it is.
164static inline const ast::CastExpr * isReferenceCast( const ast::Expr * expr ) {
165        if ( const ast::CastExpr * cast = dynamic_cast< const ast::CastExpr * >( expr ) ) {
166                if ( dynamic_cast< const ast::ReferenceType * >( cast->result.get() ) ) {
167                        return cast;
168                }
169        }
170        return nullptr;
171}
172
173/// helper function (indirectely) used by explode
174template< typename Output >
175void explodeRecursive(
176        const ast::CastExpr *, const ResolvExpr::Candidate &,
177        const ast::SymbolTable &, Output &&
178) {
179}
180
181/// helper function used by explode
182template< typename Output >
183void explodeUnique(
184        const ast::ptr< ast::Expr > & expr, const ResolvExpr::Candidate & arg,
185        const ast::SymbolTable & symtab, Output && out, bool isTupleAssign
186) {
187        // Tuple assignment can use a faster method if it is cast. Uses recursive exploding.
188        if ( isTupleAssign ) if ( const ast::CastExpr * castExpr = isReferenceCast( expr ) ) {
189                ResolvExpr::CandidateList candidates;
190                explodeUnique( castExpr->arg, arg, symtab, back_inserter( candidates ), true );
191                for ( ResolvExpr::CandidateRef & cand : candidates ) {
192                        // Distribute the reference cast over all components of the candidate.
193                        append( std::forward<Output>(out), distributeReference( cand->expr ), cand->env,
194                                cand->open, cand->need, cand->cost, cand->cvtCost );
195                }
196                return;
197        }
198        const ast::Type * res = expr->result->stripReferences();
199        if ( const ast::TupleType * tupleType = dynamic_cast< const ast::TupleType * >( res ) ) {
200                if ( const ast::ptr< ast::TupleExpr > & tupleExpr = expr.as< ast::TupleExpr >() ) {
201                        // Open the tuple expr and continue on its components.
202                        for ( const ast::Expr * expr : tupleExpr->exprs ) {
203                                explodeUnique( expr, arg, symtab, std::forward<Output>(out), isTupleAssign );
204                        }
205                } else {
206                        ast::ptr< ast::Expr > local = expr;
207                        // Expressions which may have side effects require a single unique instance.
208                        if ( Tuples::maybeImpureIgnoreUnique( local ) ) {
209                                local = new ast::UniqueExpr( local->location, local );
210                        }
211                        // Cast a reference away to a value-type to allow further explosion.
212                        if ( local->result.as< ast::ReferenceType >() ) {
213                                local = new ast::CastExpr{ local, tupleType };
214                        }
215                        // Now we have to go across the tuple via indexing.
216                        for ( unsigned int i = 0 ; i < tupleType->size() ; ++i ) {
217                                ast::TupleIndexExpr * idx = new ast::TupleIndexExpr( local->location, local, i );
218                                explodeUnique( idx, arg, symtab, std::forward<Output>(out), isTupleAssign );
219                                // TODO: We need more input to figure out the exact lifetimes of these types.
220                                // delete idx;
221                        }
222                }
223        } else {
224                // For atomic/non-tuple types, no explosion is used.
225                append( std::forward<Output>(out), expr, arg.env, arg.open, arg.need, arg.cost,
226                        arg.cvtCost );
227        }
228}
229
230/// expands a tuple-valued candidate into multiple candidates, each with a non-tuple type
231template< typename Output >
232void explode(
233        const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, Output && out,
234        bool isTupleAssign = false
235) {
236        explodeUnique( arg.expr, arg, symtab, std::forward< Output >( out ), isTupleAssign );
237}
238
239/// explode list of candidates into flattened list of candidates
240template< typename Output >
241void explode(
242        const ResolvExpr::CandidateList & cands, const ast::SymbolTable & symtab, Output && out,
243        bool isTupleAssign = false
244) {
245        for ( const ResolvExpr::CandidateRef & cand : cands ) {
246                explode( *cand, symtab, std::forward< Output >( out ), isTupleAssign );
247        }
248}
249
250} // namespace Tuples
251
252// Local Variables: //
253// tab-width: 4 //
254// mode: c++ //
255// compile-command: "make install" //
256// End: //
Note: See TracBrowser for help on using the repository browser.