source: src/ResolvExpr/TypeEnvironment.h @ 8e18b8e

new-envwith_gc
Last change on this file since 8e18b8e was 8e18b8e, checked in by Aaron Moss <a3moss@…>, 4 years ago

stop eagerly copying EqvClass? on lookup

  • Property mode set to 100644
File size: 5.8 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 : Peter A. Buhr
12// Last Modified On : Sat Jul 22 09:35:45 2017
13// Update Count     : 3
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
24#include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
25#include "SynTree/SynTree.h"           // for UniqueId
26#include "SynTree/Type.h"              // for Type, Type::ForallList
27#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
28
29template< typename Pass >
30class PassVisitor;
31class GcTracer;
32
33namespace ResolvExpr {
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        //
42        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 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 when
48        // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
49        // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
50        // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
51        // this causes some assertions to never be recorded. More investigation is needed.
52        struct AssertCompare {
53                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
54                        int cmp = d1->get_name().compare( d2->get_name() );
55                        return cmp < 0 ||
56                                ( cmp == 0 && d1->get_type() < d2->get_type() );
57                }
58        };
59        struct AssertionSetValue {
60                bool isUsed;
61                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
62                // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
63                // the ID of the assertion that pulled in the current assertion.
64                std::list< UniqueId > idChain;
65        };
66        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
67        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
68
69        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
70        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
71
72        struct EqvClass {
73                std::set< std::string > vars;
74                Type *type;
75                bool allowWidening;
76                TypeDecl::Data data;
77
78                void initialize( const EqvClass &src, EqvClass &dest );
79                EqvClass();
80                EqvClass( const EqvClass &other );
81                EqvClass &operator=( const EqvClass &other );
82                void print( std::ostream &os, Indenter indent = {} ) const;
83        };
84
85        class TypeEnvironment {
86          public:
87                const EqvClass* lookup( const std::string &var ) const;
88                void add( const EqvClass &eqvClass );
89                void add( EqvClass &&eqvClass  );
90                void add( const Type::ForallList &tyDecls );
91                void add( const TypeSubstitution & sub );
92                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
93                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
94                void makeSubstitution( TypeSubstitution &result ) const;
95                bool isEmpty() const { return env.empty(); }
96                void print( std::ostream &os, Indenter indent = {} ) const;
97                void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
98                void simpleCombine( const TypeEnvironment &second );
99                void extractOpenVars( OpenVarSet &openVars ) const;
100                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
101
102                /// Iteratively adds the environment of a new actual (with allowWidening = false),
103                /// and extracts open variables.
104                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
105
106                typedef std::list< EqvClass >::iterator iterator;
107                iterator begin() { return env.begin(); }
108                iterator end() { return env.end(); }
109                typedef std::list< EqvClass >::const_iterator const_iterator;
110                const_iterator begin() const { return env.begin(); }
111                const_iterator end() const { return env.end(); }
112          private:
113                std::list< EqvClass > env;
114                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
115        };
116
117        template< typename SynTreeClass >
118        int TypeEnvironment::apply( SynTreeClass *&type ) const {
119                TypeSubstitution sub;
120                makeSubstitution( sub );
121                return sub.apply( type );
122        }
123
124        template< typename SynTreeClass >
125        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
126                TypeSubstitution sub;
127                makeSubstitution( sub );
128                return sub.applyFree( type );
129        }
130
131        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
132
133        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );
134} // namespace ResolvExpr
135
136// Local Variables: //
137// tab-width: 4 //
138// mode: c++ //
139// compile-command: "make install" //
140// End: //
Note: See TracBrowser for help on using the repository browser.