source: src/ResolvExpr/TypeEnvironment.h @ 909aebf

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

Fix TypeEnvironment? bind algorithms

  • Property mode set to 100644
File size: 6.7 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 comparator.
42        //
43        // Note: since this compares pointers for position, minor changes in the source file that affect
44        // memory layout can alter compilation time in unpredictable ways. For example, the placement
45        // of a line directive can reorder type pointers with respect to each other so that assertions
46        // are seen in different orders, causing a potentially different number of unification calls when
47        // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
48        // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
49        // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
50        // this causes some assertions to never be recorded. More investigation is needed.
51        struct AssertCompare {
52                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
53                        int cmp = d1->get_name().compare( d2->get_name() );
54                        return cmp < 0 ||
55                                ( cmp == 0 && d1->get_type() < d2->get_type() );
56                }
57        };
58        struct AssertionSetValue {
59                bool isUsed;
60                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
61                // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
62                // the ID of the assertion that pulled in the current assertion.
63                std::list< UniqueId > idChain;
64        };
65        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
66        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
67
68        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
69        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
70
71        struct EqvClass {
72                std::set< std::string > vars;
73                Type *type;
74                bool allowWidening;
75                TypeDecl::Data data;
76
77                void initialize( const EqvClass &src, EqvClass &dest );
78                void initialize( const EqvClass &src, EqvClass &dest, const Type *ty );
79                EqvClass();
80                EqvClass( const EqvClass &other );
81                EqvClass( const EqvClass &other, const Type *ty );
82                EqvClass( EqvClass &&other );
83                EqvClass &operator=( const EqvClass &other );
84                EqvClass &operator=( EqvClass &&other );
85                ~EqvClass();
86                void print( std::ostream &os, Indenter indent = {} ) const;
87
88                /// Takes ownership of `ty`, freeing old `type`
89                void set_type(Type* ty);
90        };
91
92        class TypeEnvironment {
93          public:
94                const EqvClass* lookup( const std::string &var ) const;
95          private:
96                void add( EqvClass &&eqvClass  );
97          public:
98                void add( const Type::ForallList &tyDecls );
99                void add( const TypeSubstitution & sub );
100                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
101                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
102                void makeSubstitution( TypeSubstitution &result ) const;
103                bool isEmpty() const { return env.empty(); }
104                void print( std::ostream &os, Indenter indent = {} ) const;
105                // void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
106                void simpleCombine( const TypeEnvironment &second );
107                void extractOpenVars( OpenVarSet &openVars ) const;
108                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
109
110                /// Iteratively adds the environment of a new actual (with allowWidening = false),
111                /// and extracts open variables.
112                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
113
114                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add
115                /// the class if needed. Returns false on failure.
116                bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
117               
118                /// Binds the type classes represented by `var1` and `var2` together; will add
119                /// one or both classes if needed. Returns false on failure.
120                bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
121
122                /// Disallows widening for all bindings in the environment
123                void forbidWidening();
124
125                using iterator = std::list< EqvClass >::const_iterator;
126                iterator begin() const { return env.begin(); }
127                iterator end() const { return env.end(); }
128
129          private:
130                std::list< EqvClass > env;
131               
132                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
133        };
134
135        template< typename SynTreeClass >
136        int TypeEnvironment::apply( SynTreeClass *&type ) const {
137                TypeSubstitution sub;
138                makeSubstitution( sub );
139                return sub.apply( type );
140        }
141
142        template< typename SynTreeClass >
143        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
144                TypeSubstitution sub;
145                makeSubstitution( sub );
146                return sub.applyFree( type );
147        }
148
149        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
150} // namespace ResolvExpr
151
152// Local Variables: //
153// tab-width: 4 //
154// mode: c++ //
155// compile-command: "make install" //
156// End: //
Note: See TracBrowser for help on using the repository browser.