source: src/ResolvExpr/TypeEnvironment.h @ aeb8f70

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since aeb8f70 was 0b00df0, checked in by Aaron Moss <a3moss@…>, 5 years ago

First draft of deferred expression resolution; DOES NOT BUILD

  • Property mode set to 100644
File size: 7.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.h --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 12:24:58 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Mon Jun 18 11:58:00 2018
13// Update Count     : 4
14//
15
16#pragma once
17
18#include <iostream>                    // for ostream
19#include <list>                        // for list, list<>::iterator, list<>...
20#include <map>                         // for map, map<>::value_compare
21#include <set>                         // for set
22#include <string>                      // for string
23#include <utility>                     // for move, swap
24
25#include "WidenMode.h"                 // for WidenMode
26
27#include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
28#include "SynTree/SynTree.h"           // for UniqueId
29#include "SynTree/Type.h"              // for Type, Type::ForallList
30#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
31
32namespace ResolvExpr {
33        // adding this comparison operator significantly improves assertion resolution run time for
34        // some cases. The current resolution algorithm's speed partially depends on the order of
35        // assertions. Assertions which have fewer possible matches should appear before
36        // assertions which have more possible matches. This seems to imply that this could
37        // be further improved by providing an indexer as an additional argument and ordering based
38        // on the number of matches of the same kind (object, function) for the names of the
39        // declarations.
40        //
41        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
42        // comparator.
43        //
44        // Note: since this compares pointers for position, minor changes in the source file that affect
45        // memory layout can alter compilation time in unpredictable ways. For example, the placement
46        // of a line directive can reorder type pointers with respect to each other so that assertions
47        // are seen in different orders, causing a potentially different number of unification calls
48        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
49        // line directives alone, so it would be nice to fix this comparison so that assertions compare
50        // more consistently. I've tried to modify this to compare on mangle name instead of type as
51        // the second comparator, but this causes some assertions to never be recorded. More
52        // investigation is needed.
53        struct AssertCompare {
54                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
55                        int cmp = d1->get_name().compare( d2->get_name() );
56                        return cmp < 0 ||
57                                ( cmp == 0 && d1->get_type() < d2->get_type() );
58                }
59        };
60        struct AssertionSetValue {
61                bool isUsed;        ///< True if assertion needs to be resolved
62                UniqueId resnSlot;  ///< ID of slot assertion belongs to
63
64                AssertionSetValue() : isUsed(false), resnSlot(0) {}
65        };
66        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
67        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
68
69        /// merges one set of open vars into another
70        static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
71                for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
72        }
73
74        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
75        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
76
77        struct EqvClass {
78                std::set< std::string > vars;
79                Type *type;
80                bool allowWidening;
81                TypeDecl::Data data;
82
83                void initialize( const EqvClass &src, EqvClass &dest );
84                void initialize( const EqvClass &src, EqvClass &dest, const Type *ty );
85                EqvClass();
86                EqvClass( const EqvClass &other );
87                EqvClass( const EqvClass &other, const Type *ty );
88                EqvClass( EqvClass &&other );
89                EqvClass &operator=( const EqvClass &other );
90                EqvClass &operator=( EqvClass &&other );
91                ~EqvClass();
92                void print( std::ostream &os, Indenter indent = {} ) const;
93
94                /// Takes ownership of `ty`, freeing old `type`
95                void set_type(Type* ty);
96        };
97
98        class TypeEnvironment {
99                using ClassList = std::list< EqvClass >;
100          public:
101                const EqvClass* lookup( const std::string &var ) const;
102          private:
103                void add( EqvClass &&eqvClass  );
104          public:
105                void add( const Type::ForallList &tyDecls );
106                void add( const TypeSubstitution & sub );
107                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
108                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
109                void makeSubstitution( TypeSubstitution &result ) const;
110                bool isEmpty() const { return env.empty(); }
111                void print( std::ostream &os, Indenter indent = {} ) const;
112               
113                /// Simply concatenate the second environment onto this one; no safety checks performed
114                void simpleCombine( const TypeEnvironment &second );
115
116          private:
117                /// Unifies the type bound of to with the type bound of from, returning false if fails
118                bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
119
120                /// Merges two type classes from local environment, returning false if fails
121                bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
122
123          public:
124                /// Merges the second environment with this one, checking compatibility.
125                /// Returns false if fails, but does NOT roll back partial changes.
126                bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer );
127               
128                void extractOpenVars( OpenVarSet &openVars ) const;
129                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
130
131                /// Iteratively adds the environment of a new actual (with allowWidening = false),
132                /// and extracts open variables.
133                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
134
135                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add
136                /// the class if needed. Returns false on failure.
137                bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
138               
139                /// Binds the type classes represented by `var1` and `var2` together; will add
140                /// one or both classes if needed. Returns false on failure.
141                bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
142
143                /// Disallows widening for all bindings in the environment
144                void forbidWidening();
145
146                using iterator = ClassList::const_iterator;
147                iterator begin() const { return env.begin(); }
148                iterator end() const { return env.end(); }
149
150          private:
151                ClassList env;
152               
153                ClassList::iterator internal_lookup( const std::string &var );
154        };
155
156        template< typename SynTreeClass >
157        int TypeEnvironment::apply( SynTreeClass *&type ) const {
158                TypeSubstitution sub;
159                makeSubstitution( sub );
160                return sub.apply( type );
161        }
162
163        template< typename SynTreeClass >
164        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
165                TypeSubstitution sub;
166                makeSubstitution( sub );
167                return sub.applyFree( type );
168        }
169
170        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
171} // namespace ResolvExpr
172
173// Local Variables: //
174// tab-width: 4 //
175// mode: c++ //
176// compile-command: "make install" //
177// End: //
Note: See TracBrowser for help on using the repository browser.