source: src/AST/TypeEnvironment.hpp @ 2890212

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 2890212 was 2890212, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Startup.cfa now compiles with new ast

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