source: src/ResolvExpr/TypeEnvironment.h @ fd642d2

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since fd642d2 was fd642d2, checked in by Andrew Beach <ajbeach@…>, 5 years ago

Added const in a few more places. This should be all the leaf areas need to make unify const.

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