source: src/ResolvExpr/RenameVars.cc @ 7583c02

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 7583c02 was 7583c02, checked in by Fangren Yu <f37yu@…>, 2 years ago

partially improve #226: resolver environment size reduced to O(n)

generated code still has exponential size. should cache resolved implicits
and reuse thunks to reduce generated code size.
assertion fails cannot exit early and may have a minor performance
reduction.

  • Property mode set to 100644
File size: 5.6 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// RenameVars.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 12:05:18 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Thr Jun 20 17:39:00 2019
13// Update Count     : 8
14//
15
16#include <ext/alloc_traits.h>      // for __alloc_traits<>::value_type
17#include <memory>                  // for allocator_traits<>::value_type
18#include <sstream>                 // for operator<<, basic_ostream, ostring...
19#include <utility>                 // for pair
20
21#include "AST/Pass.hpp"
22#include "AST/Type.hpp"
23#include "Common/PassVisitor.h"
24#include "Common/ScopedMap.h"
25#include "Common/SemanticError.h"  // for SemanticError
26#include "RenameVars.h"
27#include "SynTree/Declaration.h"   // for DeclarationWithType, TypeDecl, Dec...
28#include "SynTree/Expression.h"    // for Expression
29#include "SynTree/Type.h"          // for Type, TypeInstType, TraitInstType
30#include "SynTree/Visitor.h"       // for acceptAll, maybeAccept
31
32#include "AST/Copy.hpp"
33
34namespace ResolvExpr {
35
36namespace {
37        class RenamingData {
38                int level = 0;
39                int resetCount = 0;
40
41                int next_expr_id = 1;
42                int next_usage_id = 1;
43                ScopedMap< std::string, std::string > nameMap;
44                ScopedMap< std::string, ast::TypeInstType::TypeEnvKey > idMap;
45        public:
46                void reset() {
47                        level = 0;
48                        ++resetCount;
49                }
50
51                void rename( TypeInstType * type ) {
52                        auto it = nameMap.find( type->name );
53                        if ( it != nameMap.end() ) {
54                                type->name = it->second;
55                        }
56                }
57
58                void nextUsage() {
59                        ++next_usage_id;
60                }
61
62                void openLevel( Type * type ) {
63                        if ( ! type->forall.empty() ) {
64                                nameMap.beginScope();
65                                // renames all "forall" type names to `_${level}_${name}'
66                                for ( auto td : type->forall ) {
67                                        std::ostringstream output;
68                                        output << "_" << resetCount << "_" << level << "_" << td->name;
69                                        std::string newname( output.str() );
70                                        nameMap[ td->get_name() ] = newname;
71                                        td->name = newname;
72                                        // ditto for assertion names, the next level in
73                                        level++;
74                                }
75                        }
76                }
77
78                void closeLevel( Type * type ) {
79                        if ( !type->forall.empty() ) {
80                                nameMap.endScope();
81                        }
82                }
83
84                const ast::TypeInstType * rename( const ast::TypeInstType * type ) {
85                        // rename
86                        auto it = idMap.find( type->name );
87                        if ( it != idMap.end() ) {
88                                // unconditionally mutate because map will *always* have different name
89                                ast::TypeInstType * mut = ast::shallowCopy( type );
90                                // reconcile base node since some copies might have been made
91                                mut->base = it->second.base;
92                                mut->formal_usage = it->second.formal_usage;
93                                mut->expr_id = it->second.expr_id;
94                    type = mut;
95                        }
96
97                        return type;
98                }
99
100                const ast::FunctionType * openLevel( const ast::FunctionType * type, RenameMode mode ) {
101                        if ( type->forall.empty() ) return type;
102                        idMap.beginScope();
103
104                        // Load new names from this forall clause and perform renaming.
105                        auto mutType = ast::shallowCopy( type );
106                        // assert( type == mutType && "mutated type must be unique from ForallSubstitutor" );
107                        for ( auto & td : mutType->forall ) {
108                                auto mut = ast::shallowCopy( td.get() );
109                                // assert( td == mutDecl && "mutated decl must be unique from ForallSubstitutor" );
110
111                                if (mode == GEN_EXPR_ID) {
112                                        mut->expr_id = next_expr_id;
113                                        mut->formal_usage = -1;
114                                        ++next_expr_id;
115                                }
116                                else if (mode == GEN_USAGE) {
117                                        assertf(mut->expr_id, "unfilled expression id in generating candidate type");
118                                        mut->formal_usage = next_usage_id;
119                                }
120                                else {
121                                        assert(false);
122                                }
123                                idMap[ td->name ] = ast::TypeInstType::TypeEnvKey(*mut);
124                               
125                                td = mut;
126                        }
127
128                        return mutType;
129                }
130
131                void closeLevel( const ast::FunctionType * type ) {
132                        if ( type->forall.empty() ) return;
133                        idMap.endScope();
134                }
135        };
136
137        // Global State:
138        RenamingData renaming;
139
140        struct RenameVars_old {
141                void previsit( TypeInstType * instType ) {
142                        renaming.openLevel( (Type*)instType );
143                        renaming.rename( instType );
144                }
145                void previsit( Type * type ) {
146                        renaming.openLevel( type );
147                }
148                void postvisit( Type * type ) {
149                        renaming.closeLevel( type );
150                }
151        };
152
153        struct RenameVars_new : public ast::PureVisitor /*: public ast::WithForallSubstitutor*/ {
154                RenameMode mode;
155
156                const ast::FunctionType * previsit( const ast::FunctionType * type ) {
157                        return renaming.openLevel( type, mode );
158                }
159
160                /*
161                const ast::StructInstType * previsit( const ast::StructInstType * type ) {
162                        return renaming.openLevel( type );
163                }
164                const ast::UnionInstType * previsit( const ast::UnionInstType * type ) {
165                        return renaming.openLevel( type );
166                }
167                const ast::TraitInstType * previsit( const ast::TraitInstType * type ) {
168                        return renaming.openLevel( type );
169                }
170                */
171
172                const ast::TypeInstType * previsit( const ast::TypeInstType * type ) {
173                        if (mode == GEN_USAGE && !type->formal_usage) return type; // do not rename an actual type
174                        return renaming.rename( type );
175                }
176                void postvisit( const ast::FunctionType * type ) {
177                        renaming.closeLevel( type );
178                }
179        };
180
181} // namespace
182
183void renameTyVars( Type * t ) {
184        PassVisitor<RenameVars_old> renamer;
185        t->accept( renamer );
186}
187
188const ast::Type * renameTyVars( const ast::Type * t, RenameMode mode, bool reset ) {
189        // ast::Type *tc = ast::deepCopy(t);
190        ast::Pass<RenameVars_new> renamer;
191        renamer.core.mode = mode;
192        if (mode == GEN_USAGE && reset) {
193                renaming.nextUsage();
194        }
195        return t->accept( renamer );
196}
197
198void resetTyVarRenaming() {
199        renaming.reset();
200        renaming.nextUsage();
201}
202
203} // namespace ResolvExpr
204
205// Local Variables: //
206// tab-width: 4 //
207// mode: c++ //
208// compile-command: "make install" //
209// End: //
Note: See TracBrowser for help on using the repository browser.