source: src/AST/TypeEnvironment.hpp @ 93c10de

ADTast-experimental
Last change on this file since 93c10de was 93c10de, checked in by Andrew Beach <ajbeach@…>, 18 months ago

Minimal changes to pull out nested types, TypeInstType::TypeEnvKey? and TypeDecl::Data (now TypeData?) from there parent types. Although they do connect to the parent types they were nested in they are used on their own most of the time.

  • Property mode set to 100644
File size: 8.5 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                auto kind1 = ast::SymbolTable::getSpecialFunctionKind(d1->var->name);
59                auto kind2 = ast::SymbolTable::getSpecialFunctionKind(d2->var->name);
60                // heuristics optimization: force special functions to go last
61                if (kind1 > kind2) return true;
62                else if (kind1 < kind2) return false;
63
64                int cmp = d1->var->name.compare( d2->var->name );
65                return cmp < 0 || ( cmp == 0 && d1->result < d2->result );
66        }
67};
68
69/// Data for pending assertion satisfaction
70struct AssertionSetValue {
71        bool isUsed;        ///< True if assertion needs to be satisfied
72        UniqueId resnSlot;  ///< ID of slot assertion belongs to
73
74        AssertionSetValue() : isUsed(false), resnSlot(0) {}
75};
76
77/// Set of assertions pending satisfaction
78using AssertionSet = std::map< const VariableExpr *, AssertionSetValue, AssertCompare >;
79
80/// Set of open variables
81using OpenVarSet = std::unordered_map< TypeEnvKey, TypeData >;
82
83/// Merges one set of open vars into another
84/// merges one set of open vars into another
85static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
86        for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
87}
88
89/// Print an assertion set
90void print( std::ostream &, const AssertionSet &, Indenter indent = {} );
91/// Print an open variable set
92void print( std::ostream &, const OpenVarSet &, Indenter indent = {} );
93
94/// Represents an equivalence class of bound type variables, optionally with the concrete type
95/// they bind to.
96struct EqvClass {
97        std::unordered_set< TypeEnvKey > vars;
98        ptr<Type> bound;
99        bool allowWidening;
100        TypeData data;
101
102        EqvClass() : vars(), bound(), allowWidening( true ), data() {}
103
104        /// Copy-with-bound constructor
105        EqvClass( const EqvClass & o, const Type * b )
106        : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {}
107
108        /// Singleton class constructor from TypeDecl
109        EqvClass( const TypeInstType * inst )
110        : vars{ *inst }, bound(), allowWidening( true ), data( inst->base ) {}
111
112        /// Singleton class constructor from substitution
113        EqvClass( const TypeEnvKey & v, const Type * b )
114        : vars{ v }, bound( b ), allowWidening( false ), data( TypeDecl::Dtype, false ) {}
115
116        /// Single-var constructor (strips qualifiers from bound type)
117        EqvClass( const TypeEnvKey & v, const Type * b, bool w, const TypeData & d )
118        : vars{ v }, bound( b ), allowWidening( w ), data( d ) {
119                reset_qualifiers( bound );
120        }
121
122        /// Double-var constructor
123        EqvClass( const TypeEnvKey & v, const TypeEnvKey & u, bool w, const TypeData & d )
124        : vars{ v, u }, bound(), allowWidening( w ), data( d ) {}
125
126};
127
128void print( std::ostream & out, const EqvClass & clz, Indenter indent = {} );
129
130/// A partitioning of type variables into equivalence classes
131class TypeEnvironment {
132        /// The underlying list of equivalence classes
133        using ClassList = std::list< EqvClass >;
134
135        ClassList env;
136
137public:
138        /// Finds the equivalence class containing a variable; nullptr for none such
139        const EqvClass * lookup( const TypeEnvKey & var ) const;
140
141        /// Add a new equivalence class for each type variable
142        void add( const FunctionType::ForallList & tyDecls );
143
144        /// Add a new equivalence class for each branch of the substitution, checking for conflicts
145        void add( const TypeSubstitution & sub );
146
147        /// Writes all the substitutions in this environment into a substitution
148        void writeToSubstitution( TypeSubstitution & sub ) const;
149
150        template< typename node_t >
151        auto apply( node_t && type ) const {
152                TypeSubstitution sub;
153                writeToSubstitution( sub );
154                return sub.apply( std::forward<node_t>(type) );
155        }
156
157        template< typename node_t >
158        auto applyFree( node_t && type ) const {
159                TypeSubstitution sub;
160                writeToSubstitution( sub );
161                return sub.applyFree( std::forward<node_t>(type) );
162        }
163
164        bool empty() const { return env.empty(); }
165
166        /// Concatenate environment onto this one; no safety checks performed
167        void simpleCombine( const TypeEnvironment & o );
168
169        /// Merge environment with this one, checking compatibility.
170        /// Returns false if fails, but does NOT roll back partial changes.
171        bool combine( const TypeEnvironment & o, OpenVarSet & openVars, const SymbolTable & symtab );
172
173        /// Add all type variables in environment to open var list
174        void extractOpenVars( OpenVarSet & openVars ) const;
175
176        /// Iteratively adds the environment of a new actual (with allowWidening = false),
177        /// and extracts open variables.
178        void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars );
179
180        /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if
181        /// needed. Returns false on failure.
182        bool bindVar(
183                const TypeInstType * typeInst, const Type * bindTo, const TypeData & data,
184                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
185                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
186
187        /// Binds the type classes represented by `var1` and `var2` together; will add one or both
188        /// classes if needed. Returns false on failure.
189        bool bindVarToVar(
190                const TypeInstType * var1, const TypeInstType * var2, TypeData && data,
191                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
192                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
193
194        /// Disallows widening for all bindings in the environment
195        void forbidWidening();
196
197        using iterator = ClassList::const_iterator;
198        iterator begin() const { return env.begin(); }
199        iterator end() const { return env.end(); }
200
201private:
202        /// Add an equivalence class to the environment, checking for existing conflicting classes
203        void add( EqvClass && eqvClass );
204
205        /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails
206        bool mergeBound(
207                EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab );
208
209        /// Merges two type classes from local environment, returning false if fails
210        bool mergeClasses(
211                ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars,
212                const SymbolTable & symtab );
213
214        /// Private lookup API; returns array index of string, or env.size() for not found
215        ClassList::iterator internal_lookup( const TypeEnvKey & );
216};
217
218void print( std::ostream & out, const TypeEnvironment & env, Indenter indent = {} );
219
220std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
221
222} // namespace ast
223
224// Local Variables: //
225// tab-width: 4 //
226// mode: c++ //
227// compile-command: "make install" //
228// End: //
Note: See TracBrowser for help on using the repository browser.