source: src/AST/TypeEnvironment.hpp @ 3e5dd913

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 3e5dd913 was 3e5dd913, checked in by Fangren Yu <f37yu@…>, 10 months ago

reimplement function type and eliminate deep copy

  • Property mode set to 100644
File size: 8.4 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// TypeEnvironment.hpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed May 29 11:00:00 2019
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Dec 11 21:55:54 2019
13// Update Count     : 3
14//
15
16#pragma once
17
18#include <iostream>
19#include <map>
20#include <set>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "Decl.hpp"
26#include "Node.hpp"                // for ptr_base, ptr, readonly
27#include "SymbolTable.hpp"
28#include "Type.hpp"
29#include "TypeSubstitution.hpp"
30#include "Common/Indenter.h"
31#include "ResolvExpr/WidenMode.h"
32
33namespace ast {
34
35/// Comparator/uniqueness operator for assertion sets.
36///
37/// Adding this comparison operator significantly improves assertion satisfaction run time for
38/// some cases. The current satisfaction algorithm's speed partially depends on the order of
39/// assertions. Assertions which have fewer possible matches should appear before assertions
40/// which have more possible matches. This seems to imply that this could be further improved
41/// by providing an indexer as an additional argument and ordering based on the number of
42/// matches of the same kind (object, function) for the names of the declarations.
43///
44/// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
45/// comparator.
46///
47/// Note: since this compares pointers for position, minor changes in the source file that
48/// affect memory layout can alter compilation time in unpredictable ways. For example, the
49/// placement of a line directive can reorder type pointers with respect to each other so that
50/// assertions are seen in different orders, causing a potentially different number of
51/// unification calls when resolving assertions. I've seen a TU go from 36 seconds to 27
52/// seconds by reordering line directives alone, so it would be nice to fix this comparison so
53/// that assertions compare more consistently. I've tried to modify this to compare on mangle
54/// name instead of type as the second comparator, but this causes some assertions to never be
55/// recorded. More investigation is needed.
56struct AssertCompare {
57        bool operator()( const VariableExpr * d1, const VariableExpr * d2 ) const {
58                int cmp = d1->var->name.compare( d2->var->name );
59                return cmp < 0 || ( cmp == 0 && d1->result < d2->result );
60        }
61};
62
63/// Data for pending assertion satisfaction
64struct AssertionSetValue {
65        bool isUsed;        ///< True if assertion needs to be satisfied
66        UniqueId resnSlot;  ///< ID of slot assertion belongs to
67
68        AssertionSetValue() : isUsed(false), resnSlot(0) {}
69};
70
71/// Set of assertions pending satisfaction
72using AssertionSet = std::map< const VariableExpr *, AssertionSetValue, AssertCompare >;
73
74/// Set of open variables
75using OpenVarSet = std::unordered_map< TypeInstType::TypeEnvKey, TypeDecl::Data >;
76
77/// Merges one set of open vars into another
78/// merges one set of open vars into another
79static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
80        for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
81}
82
83/// Print an assertion set
84void print( std::ostream &, const AssertionSet &, Indenter indent = {} );
85/// Print an open variable set
86void print( std::ostream &, const OpenVarSet &, Indenter indent = {} );
87
88/// Represents an equivalence class of bound type variables, optionally with the concrete type
89/// they bind to.
90struct EqvClass {
91        std::unordered_set< TypeInstType::TypeEnvKey > vars;
92        ptr<Type> bound;
93        bool allowWidening;
94        TypeDecl::Data data;
95
96        EqvClass() : vars(), bound(), allowWidening( true ), data() {}
97
98        /// Copy-with-bound constructor
99        EqvClass( const EqvClass & o, const Type * b )
100        : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {}
101
102        /// Singleton class constructor from TypeDecl
103        EqvClass( const TypeInstType * inst )
104        : vars{ *inst }, bound(), allowWidening( true ), data( inst->base ) {}
105
106        /// Singleton class constructor from substitution
107        EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b )
108        : vars{ v }, bound( b ), allowWidening( false ), data( TypeDecl::Dtype, false ) {}
109
110        /// Single-var constructor (strips qualifiers from bound type)
111        EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b, bool w, const TypeDecl::Data & d )
112        : vars{ v }, bound( b ), allowWidening( w ), data( d ) {
113                reset_qualifiers( bound );
114        }
115
116        /// Double-var constructor
117        EqvClass( const TypeInstType::TypeEnvKey & v, const TypeInstType::TypeEnvKey & u, bool w, const TypeDecl::Data & d )
118        : vars{ v, u }, bound(), allowWidening( w ), data( d ) {}
119
120};
121
122void print( std::ostream & out, const EqvClass & clz, Indenter indent = {} );
123
124/// A partitioning of type variables into equivalence classes
125class TypeEnvironment {
126        /// The underlying list of equivalence classes
127        using ClassList = std::list< EqvClass >;
128
129        ClassList env;
130
131public:
132        /// Finds the equivalence class containing a variable; nullptr for none such
133        const EqvClass * lookup( const TypeInstType::TypeEnvKey & var ) const;
134
135        /// Add a new equivalence class for each type variable
136        void add( const FunctionType::ForallList & tyDecls );
137
138        /// Add a new equivalence class for each branch of the substitution, checking for conflicts
139        void add( const TypeSubstitution & sub );
140
141        /// Writes all the substitutions in this environment into a substitution
142        void writeToSubstitution( TypeSubstitution & sub ) const;
143
144        template< typename node_t >
145        auto apply( node_t && type ) const {
146                TypeSubstitution sub;
147                writeToSubstitution( sub );
148                return sub.apply( std::forward<node_t>(type) );
149        }
150
151        template< typename node_t >
152        auto applyFree( node_t && type ) const {
153                TypeSubstitution sub;
154                writeToSubstitution( sub );
155                return sub.applyFree( std::forward<node_t>(type) );
156        }
157
158        bool empty() const { return env.empty(); }
159
160        /// Concatenate environment onto this one; no safety checks performed
161        void simpleCombine( const TypeEnvironment & o );
162
163        /// Merge environment with this one, checking compatibility.
164        /// Returns false if fails, but does NOT roll back partial changes.
165        bool combine( const TypeEnvironment & o, OpenVarSet & openVars, const SymbolTable & symtab );
166
167        /// Add all type variables in environment to open var list
168        void extractOpenVars( OpenVarSet & openVars ) const;
169
170        /// Iteratively adds the environment of a new actual (with allowWidening = false),
171        /// and extracts open variables.
172        void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars );
173
174        /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if
175        /// needed. Returns false on failure.
176        bool bindVar(
177                const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data,
178                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
179                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
180
181        /// Binds the type classes represented by `var1` and `var2` together; will add one or both
182        /// classes if needed. Returns false on failure.
183        bool bindVarToVar(
184                const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data,
185                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
186                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
187
188        /// Disallows widening for all bindings in the environment
189        void forbidWidening();
190
191        using iterator = ClassList::const_iterator;
192        iterator begin() const { return env.begin(); }
193        iterator end() const { return env.end(); }
194
195private:
196        /// Add an equivalence class to the environment, checking for existing conflicting classes
197        void add( EqvClass && eqvClass );
198
199        /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails
200        bool mergeBound(
201                EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab );
202
203        /// Merges two type classes from local environment, returning false if fails
204        bool mergeClasses(
205                ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars,
206                const SymbolTable & symtab );
207
208        /// Private lookup API; returns array index of string, or env.size() for not found
209        ClassList::iterator internal_lookup( const TypeInstType::TypeEnvKey & );
210};
211
212void print( std::ostream & out, const TypeEnvironment & env, Indenter indent = {} );
213
214std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
215
216} // namespace ast
217
218// Local Variables: //
219// tab-width: 4 //
220// mode: c++ //
221// compile-command: "make install" //
222// End: //
Note: See TracBrowser for help on using the repository browser.