Index: src/Common/InternedString.cc =================================================================== --- src/Common/InternedString.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/Common/InternedString.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -0,0 +1,24 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// InternedString.cc -- +// +// Author : Aaron B. Moss +// Created On : Thu Jun 14 11:15:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Jun 14 11:15:00 2018 +// Update Count : 1 +// + +#include "InternedString.h" + +std::unordered_set< std::string > interned_string::canonical; + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/InternedString.h =================================================================== --- src/Common/InternedString.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/Common/InternedString.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -0,0 +1,78 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// InternedString.h -- +// +// Author : Aaron B. Moss +// Created On : Thu Jun 14 11:15:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Jun 14 11:15:00 2018 +// Update Count : 1 +// + +#pragma once + +#include +#include +#include +#include + +/// Keeps canonical copies of a std::string for quicker comparisons +class interned_string { + /// Shared map of canonical string representations + static std::unordered_set< std::string > canonical; + + /// Canonical representation of empty string + static const std::string* empty_string() { + static const std::string* mt = [](){ + return &*canonical.emplace( "" ).first; + }(); + return mt; + } + + /// Canonicalize string + template + static const std::string* intern( S&& s ) { + return &*canonical.emplace( std::forward(s) ).first; + } + + /// Pointer to stored string + const std::string* s; + +public: + interned_string() : s{empty_string()} {} + interned_string(const char* cs) : s{intern(cs)} {} + interned_string(const std::string& ss) : s{intern(ss)} {} + /// Invalid string + interned_string(std::nullptr_t) : s{nullptr} {} + + operator const std::string& () const { return *s; } + const std::string& str() const { return (const std::string&)*this; } + + bool operator== (const interned_string& o) const { return s == o.s; } + bool operator!= (const interned_string& o) const { return s != o.s; } + + /// Check for invalid string + explicit operator bool () { return s != nullptr; } +}; + +inline std::ostream& operator<< (std::ostream& out, const interned_string& s) { + return out << (const std::string&)s; +} + +namespace std { + template<> struct hash { + std::size_t operator() (const interned_string& s) const { + return std::hash{}( &(const std::string&)s ); + } + }; +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/PersistentDisjointSet.h =================================================================== --- src/Common/PersistentDisjointSet.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/Common/PersistentDisjointSet.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -0,0 +1,439 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PersistentDisjointSet.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 13 16:31:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 13 16:31:00 2018 +// Update Count : 1 +// + +#pragma once + +#include +#include +#include +#include + +#include "GC.h" + +/// Persistent disjoint-set data structure based on the persistent array in +/// Conchon & Filliatre "A Persistent Union-Find Data Structure". Path +/// compression is not performed (to lower cost of persistent rollback). +/// Auxilliary lists are kept for efficient retrieval of class members. +/// Find root should still operate in O(log k), for k the size of an +/// equivalence class. + +template, typename Eq = std::equal_to> +class PersistentDisjointSet : public GC_Object { +public: + /// Type of this class + using Self = PersistentDisjointSet; + + /// Types of version nodes + enum Mode { + BASE, ///< Root node of version tree + ADD, ///< Add key to set + REM, ///< Reverse add operation + ADDTO, ///< Merge one class root under another + REMFROM ///< Reverse addTo operation + }; + +private: + /// Type of node height + using Height = unsigned char; + + /// Disjoint-set node + struct Node { + Elm parent; ///< Parent node in equivalence class + Elm next; ///< Next node in equivalence class + Height height; ///< Tree height of the node + + template + Node(E&& e) : parent(e), next(std::forward(e)), height(0) {} + + template + Node(E&& p, F&& n, Height h) + : parent(std::forward(p)), next(std::forward(n)), height(h) {} + }; + + /// Type of class map + using Base = std::unordered_map; + + /// Node inserted into underlying map as new equivalence class + struct Add { + Self* base; ///< Modified map + Elm root; ///< Element added + + template + Add(Self* b, E&& r) : base(b), root(std::forward(r)) {} + }; + + /// Two classes merged + struct AddTo { + Self* base; ///< Modified map + Elm root; ///< Root node + Elm child; ///< Child node, formerly root of own class + bool new_height; ///< Did the root node's height change? + + template + AddTo(Self* b, R&& r, C&& c, bool h) + : base(b), root(std::forward(r)), child(std::forward(c)), new_height(h) {} + }; + + /// Underlying storage + union Data { + char none; + Base base; + Add add; + AddTo add_to; + + Data() : none('\0') {} + ~Data() {} + } data; + + /// Type of version node + mutable Mode mode; + + /// get mutable reference as T + template + T& as() { return reinterpret_cast(data); } + + /// get const reference as T + template + const T& as() const { return reinterpret_cast(data); } + + /// get rvalue reference as T + template + T&& take_as() { return std::move(as()); } + + /// initialize as T + template + void init( Args&&... args ) { + new( &as() ) T { std::forward(args)... }; + } + + /// reset according to current mode + void reset() { + switch( mode ) { + case BASE: as().~Base(); break; + case ADD: case REM: as().~Add(); break; + case ADDTO: case REMFROM: as().~AddTo(); break; + default: assertf(false, "invalid mode"); + } + } + + PersistentDisjointSet( Mode m, Base&& b ) : data(), mode(m) { + assertf(m == BASE, "invalid mode"); + init(std::move(b)); + } + + template + PersistentDisjointSet( Mode m, const Self* b, R&& r ) : data(), mode(m) { + assertf(m == ADD || m == REM, "invalid mode"); + init(b, std::forward(r)); + } + + template + PersistentDisjointSet( Mode m, const Self* b, R&& r, C&& c, bool h ) : data(), mode(m) { + assertf(m == ADDTO || m == REMFROM, "invalid mode"); + init(b, std::forward(r), std::forward(c), h); + } + + /// Adds (also removes) graph edges. + /// * `from.parent` updated to `new_root`, + /// * `from.next` and `to.next` swapped (splices or un-splices class lists) + /// * `to.height` adjusted by change + template + static void addEdge( Node& from, Node& to, R&& new_root, Height change ) { + from.parent = std::forward(new_root); + std::swap(from.next, to.next); + to.height += change; + } + +protected: + void trace( const GC& gc ) const { + switch( mode ) { + case BASE: { + for (const auto& entry : as()) { + gc << entry.first; + } + return; + } + case ADD: case REM: { + const Add& self = as(); + gc << self.base << self.root; + return; + } + case ADDTO: case REMFROM: { + const AddTo& self = as(); + gc << self.base << self.root << self.child; + return; + } + default: assertf(false, "invalid mode"); + } + } + +public: + using size_type = std::size_t; + + using iterator = typename Base::const_iterator; + + PersistentDisjointSet() : data(), mode(BASE) { init(); } + + PersistentDisjointSet( const Self& o ) = delete; + + Self& operator= ( const Self& o ) = delete; + + ~PersistentDisjointSet() { reset(); } + + /// reroot persistent data structure at current node + void reroot() const { + if ( mode == BASE ) return; + + // reroot base + Self* mut_this = const_cast(this); + Self* base = ( mode == ADD || mode == REM ) ? + mut_this->as().base : + mut_this->as().base; + base->reroot(); + assertf(base->mode == BASE, "reroot results in base"); + + // take map out of base + Base base_map = base->take_as(); + base->reset(); + + // switch base to inverse of self and mutate base map + switch ( mode ) { + case ADD: { + Add& self = mut_this->as(); + + base->init( mut_this, self.root ); + base->mode = REM; + + base_map.emplace( self.root, Node{ std::move(self.root) } ); + } break; + case REM: { + Add& self = mut_this->as(); + + base->init( mut_this, self.root ); + base->mode = ADD; + + base_map.erase( self.root ); + } break; + case ADDTO: { + AddTo& self = mut_this->as(); + + base->init( mut_this, self.root, self.child, self.new_height ); + base->mode = REMFROM; + + auto child_it = base_map.find( self.child ); + auto root_it = base_map.find( self.root ); + assertf(child_it != base_map.end() && root_it != base_map.end(), + "nodes must exist in base"); + Node& child = child_it->second; + Node& root = root_it->second; + + addEdge( child, root, std::move(self.root), Height(self.new_height) ); + } break; + case REMFROM: { + AddTo& self = mut_this->as(); + + base->init( mut_this, self.root, self.child, self.new_height ); + base->mode = ADDTO; + + auto child_it = base_map.find( self.child ); + auto root_it = base_map.find( self.root ); + assertf(child_it != base_map.end() && root_it != base_map.end(), + "nodes must exist in base"); + Node& child = child_it->second; + Node& root = root_it->second; + + addEdge( child, root, std::move(self.child), Height(-1 * self.new_height) ); + } break; + default: assertf(false, "invalid mode"); + } + + // set base map into self + mut_this->reset(); + mut_this->init( std::move(base_map) ); + mode = BASE; + } + +private: + /// Gets the base after rerooting at the current node + const Base& rerooted() const { + reroot(); + return as(); + } + +public: + /// true if the set of sets is empty + bool empty() const { return rerooted().empty(); } + + /// Get number of entries in the map + size_type size() const { return rerooted().size(); } + + /// Get begin iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same chain + iterator begin() const { return rerooted().begin(); } + + /// Get end iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same chain + iterator end() const { return rerooted().end(); } + + /// Check if value is present + size_type count(Elm i) const { return rerooted().count( i ); } + + /// Finds root for element i, assertfs i is present + Elm find(Elm i) const { + const Base& self = rerooted(); + + auto it = self.find( i ); + while (true) { + assertf(it != self.end(), "find target not present"); + + if ( it->first == it->second.parent ) return it->first; + + it = self.find( it->second.parent ); + } + } + + /// Finds root for element i, or default if i is not present + template + Elm find_or_default(Elm i, E&& d) const { + const Base& self = rerooted(); + + auto it = self.find( i ); + if ( it == self.end() ) return d; + + while ( it->first != it->second.parent ) { + it = self.find( it->second.parent ); + + assertf(it != self.end(), "find target not present"); + } + return it->first; + } + + /// Adds fresh class including only one item; returns updated map + template + Self* add(E&& i) { + reroot(); + + // transfer map to new node + Self* ret = new Self{ BASE, take_as() }; + reset(); + + // set self to REM node + init( ret, i ); + mode = REM; + + // add element in returned map + Base& base_map = ret->as(); + bool added = base_map.emplace( i, Node{ std::forward(i) } ).second; + assertf(added, "added element already present in map"); + + return ret; + } + + /// Merges two classes given by their roots; returns updated map. + /// If two classes have same height, `i` is new root. + Self* merge(Elm i, Elm j) { + reroot(); + + // transfer map to new node + Self* ret = new Self{ BASE, take_as() }; + reset(); + + // find set nodes + Base& base_map = ret->as(); + auto it = base_map.find( i ); + auto jt = base_map.find( j ); + assertf(it != base_map.end() && jt != base_map.end(), "nodes must exist in base"); + Node& in = it->second; + Node& jn = jt->second; + + // update returned map and set self to appropriate REMFROM node + if ( in.height < jn.height ) { + addEdge( in, jn, j, 0 ); + init( ret, j, i, false ); + } else if ( jn.height < in.height ) { + addEdge( jn, in, i, 0 ); + init( ret, i, j, false ); + } else /* if ( jn.height == in.height ) */ { + addEdge( jn, in, i, 1 ); + init( ret, i, j, true ); + } + mode = REMFROM; + + return ret; + } + + /// Reports all members of a class to `out`; none if i does not exist in map + template + void find_class(Elm i, OutputIterator&& out) const { + const Base& self = rerooted(); + + // skip empty classes + if ( ! self.count( i ) ) return; + + Elm crnt = i; + do { + *out++ = crnt; + auto it = self.find( crnt ); + assertf( it != self.end(), "current node must exist in base" ); + crnt = it->second.next; + } while ( crnt != i ); + } + + /// Get version node type + Mode get_mode() const { return mode; } + + /// Get next version up the revision tree (self if base node) + const Self* get_base() const { + switch ( mode ) { + case BASE: return this; + case ADD: case REM: return as().base; + case ADDTO: case REMFROM: return as().base; + default: assertf(false, "invalid mode"); + } + } + + /// Get root of new class formed/removed/split (undefined if called on base) + Elm get_root() const { + switch ( mode ) { + case ADD: case REM: return as().root; + case ADDTO: case REMFROM: return as().root; + default: assertf(false, "invalid mode for get_root()"); + } + } + + /// Get child root of new class formed/split (undefined if called on base or add/remove node) + Elm get_child() const { + switch ( mode ) { + case ADDTO: case REMFROM: return as().child; + default: assertf(false, "invalid mode for get_child()"); + } + } + + /// Gets acted-upon key for new class (root unless for add/remove node, child for add to/remove + /// from node, undefined otherwise) + Elm get_key() const { + switch ( mode ) { + case ADD: case REM: return as().root; + case ADDTO: case REMFROM: return as().child; + default: assertf(false, "invalid mode for get_key()"); + } + } +}; + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/PersistentMap.h =================================================================== --- src/Common/PersistentMap.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/Common/PersistentMap.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -0,0 +1,428 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PersistentMap.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 13 16:31:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 13 16:31:00 2018 +// Update Count : 1 +// + +#pragma once + +#include +#include +#include +#include +#include + +#include "GC.h" + +/// Wraps a hash table in a persistent data structure, using a technique based +/// on the persistent array in Conchon & Filliatre "A Persistent Union-Find +/// Data Structure" + +template, typename Eq = std::equal_to> +class PersistentMap : public GC_Object { +public: + /// Type of this class + using Self = PersistentMap; + + /// Types of version nodes + enum Mode { + BASE, ///< Root node of version tree + REM, ///< Key removal node + INS, ///< Key update node + UPD ///< Key update node + }; + +private: + /// Type of underlying hash table + using Base = std::unordered_map; + + /// Node inserted into underlying map + struct Ins { + Self* base; ///< Modified map + Key key; ///< Key inserted + Val val; ///< Value stored + + template + Ins(Self* b, K&& k, V&& v) : base(b), key(std::forward(k)), val(std::forward(v)) {} + }; + + /// Node removed from underlying map + struct Rem { + Self* base; ///< Modified map + Key key; ///< Key removed + + template + Rem(Self* b, K&& k) : base(b), key(std::forward(k)) {} + }; + + /// Underlying storage + union Data { + char def; + Base base; + Ins ins; + Rem rem; + + Data() : def('\0') {} + ~Data() {} + } data; + + // Mode of node + mutable Mode mode; + + /// get mutable reference as T + template + T& as() { return reinterpret_cast(data); } + + /// get const reference as T + template + const T& as() const { return reinterpret_cast(data); } + + /// get rvalue reference as T + template + T&& take_as() { return std::move(as()); } + + /// initialize as T + template + void init( Args&&... args ) { + new( &as() ) T { std::forward(args)... }; + } + + /// reset as current mode + void reset() { + switch( mode ) { + case BASE: as().~Base(); break; + case REM: as().~Rem(); break; + case INS: case UPD: as().~Ins(); break; + default: assertf(false, "invalid mode"); + } + } + + /// reset as base + void reset_as_base() { + assertf( mode == BASE, "can only reset_as_base() on BASE" ); + as().~Base(); + } + + PersistentMap( Mode m, Base&& b ) : data(), mode(m) { + assertf(m == BASE, "invalid mode"); + init(std::move(b)); + } + + template + PersistentMap( Mode m, const Self* o, K&& k, V&& v ) : data(), mode(m) { + assertf(m == INS || m == UPD, "invalid mode"); + init(o, std::forward(k), std::forward(v)); + } + + template + PersistentMap( Mode m, const Self* o, K&& k ) : data(), mode(m) { + assertf(m == REM, "invalid mode"); + init(o, std::forward(k)); + } + +protected: + void trace(const GC& gc) const { + switch( mode ) { + case BASE: { + for (const auto& entry : as()) { + gc << entry.first << entry.second; + } + return; + } + case REM: { + const Rem& self = as(); + gc << self.base << self.key; + return; + } + case INS: case UPD: { + const Ins& self = as(); + gc << self.base << self.key << self.val; + return; + } + default: assertf(false, "invalid mode"); + } + } + +public: + using size_type = std::size_t; + + using iterator = typename Base::const_iterator; + + PersistentMap() : data(), mode(BASE) { init(); } + + PersistentMap( const Self& o ) = delete; + + Self& operator= ( const Self& o ) = delete; + + ~PersistentMap() { reset(); } + + /// reroot persistent map at current node + void reroot() const { + // recursive base case + if ( mode == BASE ) return; + + // reroot base + Self* mut_this = const_cast(this); + Self* base = ( mode == REM ) ? mut_this->as().base : mut_this->as().base; + base->reroot(); + assertf(base->mode == BASE, "reroot results in base"); + + // take map out of base + Base base_map = base->take_as(); + base->reset_as_base(); + + // switch base to inverse of self and mutate base map + switch ( mode ) { + case REM: { + Rem& self = mut_this->as(); + auto it = base_map.find( self.key ); + assertf( it != base_map.end(), "removed node must exist in base"); + + base->init( mut_this, std::move(self.key), std::move(it->second) ); + base->mode = INS; + + base_map.erase( it ); + break; + } + case INS: { + Ins& self = mut_this->as(); + + base->init( mut_this, self.key ); + base->mode = REM; + + base_map.emplace( std::move(self.key), std::move(self.val) ); + break; + } + case UPD: { + Ins& self = mut_this->as(); + auto it = base_map.find( self.key ); + assertf( it != base_map.end(), "updated node must exist in base"); + + base->init( mut_this, std::move(self.key), std::move(it->second) ); + base->mode = UPD; + + it->second = std::move(self.val); + break; + } + default: assertf(false, "invalid mode"); + } + + // set base map into self + mut_this->reset(); + mut_this->init( std::move(base_map) ); + mode = BASE; + } + +private: + /// Gets the base after rerooting at the current node + const Base& rerooted() const { + reroot(); + return as(); + } + +public: + /// true iff the map is empty + bool empty() const { return rerooted().empty(); } + + /// Get number of entries in map + size_type size() const { return rerooted().size(); } + + /// Get begin iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same chain + iterator begin() const { return rerooted().begin(); } + + /// Get end iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same chain + iterator end() const { return rerooted().end(); } + + /// Get underlying map iterator for value + iterator find(const Key& k) const { return rerooted().find( k ); } + + /// Check if value is present + size_type count(const Key& k) const { return rerooted().count( k ); } + + /// Get value; undefined behavior if not present + const Val& get(const Key& k) const { + const Base& self = rerooted(); + auto it = self.find( k ); + assertf(it != self.end(), "get target not present"); + return it->second; + } + + /// Get value; returns default if not present + template + Val get_or_default(const Key& k, V&& d) const { + const Base& self = rerooted(); + auto it = self.find( k ); + if ( it == self.end() ) return d; + else return it->second; + } + + /// Set value, storing new map in output variable + template + Self* set(K&& k, V&& v) { + reroot(); + assertf(mode == BASE, "reroot results in base"); + + // transfer map to new node + Self* ret = new Self{ BASE, take_as() }; + reset_as_base(); + Base& base_map = ret->as(); + + // check if this is update or insert + auto it = base_map.find( k ); + if ( it == base_map.end() ) { + // set self to REM node and insert into base + init( ret, k ); + mode = REM; + + base_map.emplace_hint( it, std::forward(k), std::forward(v) ); + } else { + // set self to UPD node and modify base + init( ret, std::forward(k), std::move(it->second) ); + mode = UPD; + + it->second = std::forward(v); + } + + return ret; + } + + /// Remove value, storing new map in output variable; does nothing if key not in map + Self* erase(const Key& k) { + reroot(); + assertf(mode == BASE, "reroot results in base"); + + // exit early if key does not exist in map + if ( ! as().count( k ) ) return this; + + // transfer map to new node + Self* ret = new Self{ BASE, take_as() }; + reset_as_base(); + Base& base_map = ret->as(); + + // set self to INS node and remove from base + init( ret, k, base_map[k] ); + mode = INS; + + base_map.erase( k ); + + return ret; + } + + /// smart reference for indexing interface + class Entry { + friend PersistentMap; + Self* base; + const Key& key; + + public: + Entry(Self* b, const Key& k) : base(b), key(k) {} + + /// Gets the underlying map instance + Self* get_base() const { return base; } + + /// Gets the key + const Key& get_key() const { return key; } + + /// Checks if the key exists in the map + bool exists() const { return base->count(key); } + + /// Gets the value for the key (if it exists) + const Val& get() const { return base->get(key); } + + /// Cast version of get + operator const Val& () const { return base->get(key); } + + /// Sets the value into the key; returns entry pointing to new set + template + Entry& set(V&& v) { + base = base->set(key, std::forward(v)); + return *this; + } + + /// Assignment version of set + template + Entry& operator= (V&& v) { + base = base->set(key, std::forward(v)); + return *this; + } + + /// Gets value or initializes to new value from args + template + Entry& get_or(Args&&... args) { + base = base->get_or(key, std::forward(args)...); + return *this; + } + }; + + /// Gets smart reference to slot with given key + Entry operator[] (const Key& k) { return { this, k }; } + + /// Gets Entry for key, initializing from args if not present + template + Entry get_or_insert(const Key& k, Args&&... args) { + Base& base_map = rerooted(); + + // check already present + if ( base_map.count(k) ) return { this, k }; + + // otherwise insert based on parameters + base_map.emplace( k, Val{ std::forward(args)... } ); + Self* ret = new Self{ BASE, std::move(base_map) }; + + // update self to point to new base + reset_as_base(); + init( ret, k ); + mode = REM; + + // return entry for new base + return { ret, k }; + } + + /// Get version node type + Mode get_mode() const { return mode; } + + /// Get next version up the revision tree (self if base node) + const Self* get_base() const { + switch ( mode ) { + case BASE: return this; + case REM: return as().base; + case INS: case UPD: return as().base; + default: assertf(false, "invalid mode"); + } + } + + /// Get key of revision node (undefined if called on base) + const Key& get_key() const { + switch ( mode ) { + case REM: return as().key; + case INS: case UPD: return as().key; + default: assertf(false, "invalid mode for get_key()"); + } + } + + /// Get value of insert/update revision node (undefined otherwise) + const Val& get_val() const { + switch ( mode ) { + case INS: case UPD: return as().val; + default: assertf(false, "invalid mode for get_val()"); + } + } +}; + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/module.mk =================================================================== --- src/Common/module.mk (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/Common/module.mk (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -10,7 +10,7 @@ ## Author : Richard C. Bilson ## Created On : Mon Jun 1 17:49:17 2015 -## Last Modified By : Peter A. Buhr -## Last Modified On : Tue Sep 27 11:06:38 2016 -## Update Count : 4 +## Last Modified By : Aaron B. Moss +## Last Modified On : Thu Jun 14 11:15:00 2018 +## Update Count : 5 ############################################################################### @@ -20,3 +20,4 @@ Common/GC.cc \ Common/Assert.cc \ + Common/InternedString.cc \ Common/Heap.cc Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/GenPoly/Box.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -38,5 +38,4 @@ #include "Lvalue.h" // for generalizedLvalue #include "Parser/LinkageSpec.h" // for C, Spec, Cforall, Intrinsic -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass #include "ResolvExpr/typeops.h" // for typesCompatible #include "ScopedSet.h" // for ScopedSet, ScopedSet<>::iter... @@ -592,5 +591,4 @@ // pass size/align for type variables for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) { - ResolvExpr::EqvClass eqvClass; assert( env ); if ( tyParm->second.isComplete ) { Index: src/ResolvExpr/AdjustExprType.cc =================================================================== --- src/ResolvExpr/AdjustExprType.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/AdjustExprType.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -19,5 +19,5 @@ #include "SynTree/Mutator.h" // for Mutator #include "SynTree/Type.h" // for PointerType, TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "TypeEnvironment.h" // for ClassRef, TypeEnvironment namespace ResolvExpr { @@ -74,6 +74,6 @@ Type * AdjustExprType::postmutate( TypeInstType * typeInst ) { - if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) { - if ( eqvClass->data.kind == TypeDecl::Ftype ) { + if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) { + if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) { return new PointerType{ Type::Qualifiers(), typeInst }; } Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/AlternativeFinder.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -1109,6 +1109,6 @@ } } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) - if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) { - if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) { + if ( ClassRef eqvClass = func->env.lookup( typeInst->get_name() ) ) { + if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) { Alternative newFunc( *func ); referenceToRvalueConversion( newFunc.expr, newFunc.cost ); Index: src/ResolvExpr/CastCost.cc =================================================================== --- src/ResolvExpr/CastCost.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/CastCost.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -18,5 +18,5 @@ #include "ConversionCost.h" // for ConversionCost #include "Cost.h" // for Cost, Cost::infinity -#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, EqvClass +#include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, ClassRef #include "SymTab/Indexer.h" // for Indexer #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl @@ -43,7 +43,7 @@ Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { - if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { - if ( eqvClass->type ) { - return castCost( src, eqvClass->type, indexer, env ); + if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { + if ( Type* boundTy = eqvClass.get_bound().type ) { + return castCost( src, boundTy, indexer, env ); } else { return Cost::infinity; Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/ConversionCost.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -22,5 +22,5 @@ #include "Common/GC.h" // for new_static_root #include "ResolvExpr/Cost.h" // for Cost -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment #include "SymTab/Indexer.h" // for Indexer #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl @@ -44,7 +44,7 @@ if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { PRINT( std::cerr << "type inst " << destAsTypeInst->name; ) - if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) { - if ( eqvClass->type ) { - return conversionCost( src, eqvClass->type, indexer, env ); + if ( ClassRef eqvClass = env.lookup( destAsTypeInst->name ) ) { + if ( Type* boundTy = eqvClass.get_bound().type ) { + return conversionCost( src, boundTy, indexer, env ); } else { return Cost::infinity; @@ -360,6 +360,6 @@ void ConversionCost::postvisit( TypeInstType *inst ) { - if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) { - cost = costFunc( eqvClass->type, dest, indexer, env ); + if ( ClassRef eqvClass = env.lookup( inst->name ) ) { + cost = costFunc( eqvClass.get_bound().type, dest, indexer, env ); } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) { if ( inst->name == destAsInst->name ) { Index: src/ResolvExpr/Occurs.cc =================================================================== --- src/ResolvExpr/Occurs.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/Occurs.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -14,10 +14,10 @@ // -#include // for set, _Rb_tree_const_iterator #include // for string +#include // for unordered_set #include "Common/PassVisitor.h" #include "SynTree/Type.h" // for TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "TypeEnvironment.h" // for ClassRef, TypeEnvironment namespace ResolvExpr { @@ -27,5 +27,6 @@ bool result; - std::set< std::string > eqvVars; + using VarSet = std::unordered_set< std::string >; + VarSet eqvVars; const TypeEnvironment &tenv; }; @@ -38,6 +39,6 @@ Occurs::Occurs( std::string varName, const TypeEnvironment & env ) : result( false ), tenv( env ) { - if ( const EqvClass *eqvClass = tenv.lookup( varName ) ) { - eqvVars = eqvClass->vars; + if ( ClassRef eqvClass = tenv.lookup( varName ) ) { + eqvVars = eqvClass.get_vars(); } else { eqvVars.insert( varName ); @@ -51,10 +52,10 @@ if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) { result = true; - } else if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { - if ( eqvClass->type ) { + } else if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) { + if ( Type* boundTy = eqvClass.get_bound().type ) { /// std::cerr << typeInst->get_name() << " is bound to"; -/// eqvClass.type->print( std::cerr ); +/// boundTy->print( std::cerr ); /// std::cerr << std::endl; - eqvClass->type->accept( *visitor ); + boundTy->accept( *visitor ); } // if } // if Index: src/ResolvExpr/PolyCost.cc =================================================================== --- src/ResolvExpr/PolyCost.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/PolyCost.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -17,5 +17,5 @@ #include "SymTab/Indexer.h" // for Indexer #include "SynTree/Type.h" // for TypeInstType, Type -#include "TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "TypeEnvironment.h" // for ClassRef, TypeEnvironment namespace ResolvExpr { @@ -39,7 +39,7 @@ void PolyCost::previsit(TypeInstType * typeInst) { - if ( const EqvClass *eqvClass = tenv.lookup( typeInst->name ) ) { - if ( eqvClass->type ) { - if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass->type ) ) { + if ( ClassRef eqvClass = tenv.lookup( typeInst->name ) ) { + if ( Type* boundTy = eqvClass.get_bound().type ) { + if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( boundTy ) ) { if ( indexer.lookupType( otherTypeInst->name ) ) { // bound to opaque type Index: src/ResolvExpr/PtrsAssignable.cc =================================================================== --- src/ResolvExpr/PtrsAssignable.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/PtrsAssignable.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -15,5 +15,5 @@ #include "Common/PassVisitor.h" -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment #include "SynTree/Type.h" // for TypeInstType, Type, BasicType #include "SynTree/Visitor.h" // for Visitor @@ -51,6 +51,6 @@ // std::cerr << "assignable: " << src << " | " << dest << std::endl; if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { - if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { - return ptrsAssignable( src, eqvClass->type, env ); + if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { + return ptrsAssignable( src, eqvClass.get_bound().type, env ); } // if } // if @@ -94,8 +94,8 @@ void PtrsAssignable::postvisit( __attribute__((unused)) TraitInstType *inst ) {} void PtrsAssignable::postvisit( TypeInstType *inst ) { - if ( const EqvClass *eqvClass = env.lookup( inst->get_name() ) ) { - if ( eqvClass->type ) { + if ( ClassRef eqvClass = env.lookup( inst->get_name() ) ) { + if ( Type* boundTy = eqvClass.get_bound().type ) { // T * = S * for any S depends on the type bound to T - result = ptrsAssignable( eqvClass->type, dest, env ); + result = ptrsAssignable( boundTy, dest, env ); } } // if Index: src/ResolvExpr/PtrsCastable.cc =================================================================== --- src/ResolvExpr/PtrsCastable.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/PtrsCastable.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -15,5 +15,5 @@ #include "Common/PassVisitor.h" -#include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment #include "SymTab/Indexer.h" // for Indexer #include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Kind::Ftype @@ -63,6 +63,6 @@ } // if } //if - } else if ( const EqvClass *eqvClass = env.lookup( typeInst->get_name() ) ) { - if ( eqvClass->data.kind == TypeDecl::Ftype ) { + } else if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) { + if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) { return -1; } // if @@ -78,7 +78,7 @@ int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { - if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { + if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { // xxx - should this be ptrsCastable? - return ptrsAssignable( src, eqvClass->type, env ); + return ptrsAssignable( src, eqvClass.get_bound().type, env ); } // if } // if Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/TypeEnvironment.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -19,10 +19,13 @@ #include // for pair, move +#include "Common/InternedString.h" // for interned_string #include "Common/PassVisitor.h" // for PassVisitor #include "Common/utility.h" // for maybeClone +#include "SymTab/Indexer.h" // for Indexer #include "SynTree/GcTracer.h" // for PassVisitor #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... #include "SynTree/TypeSubstitution.h" // for TypeSubstitution #include "TypeEnvironment.h" +#include "Unify.h" // for unifyInexact namespace ResolvExpr { @@ -45,4 +48,5 @@ } +#if 0 void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { dest.vars = src.vars; @@ -52,6 +56,9 @@ } - EqvClass::EqvClass() : type( 0 ), allowWidening( true ) { - } + EqvClass::EqvClass() : vars(), type( 0 ), allowWidening( true ), data() {} + + EqvClass::EqvClass( std::vector&& vs, BoundType&& bound ) + : vars( vs.begin(), vs.end() ), type( maybeClone( bound.type ) ), + allowWidening( bound.allowWidening ), data( bound.data ) {} EqvClass::EqvClass( const EqvClass &other ) { @@ -91,5 +98,181 @@ return nullptr; } - +#endif + + std::pair TypeEnvironment::mergeClasses( + interned_string root1, interned_string root2 ) { + // merge classes + Classes* newClasses = classes->merge( root1, root2 ); + + // determine new root + assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge"); + auto ret = std::make_pair( classes->get_root(), classes->get_child ); + + // finalize classes + classes = newClasses; + return ret; + } + + ClassRef TypeEnvironment::lookup( interned_string var ) const { + interned_string root = classes->find_or_default( var, nullptr ); + if ( root ) return { this, root }; + else return { nullptr, var }; + } + + bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) { + switch ( data.kind ) { + case TypeDecl::Dtype: + // to bind to an object type variable, the type must not be a function type. + // if the type variable is specified to be a complete type then the incoming + // type must also be complete + // xxx - should this also check that type is not a tuple type and that it's not a ttype? + return ! isFtype( type ) && (! data.isComplete || type->isComplete() ); + case TypeDecl::Ftype: + return isFtype( type ); + case TypeDecl::Ttype: + // ttype unifies with any tuple type + return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type ); + } // switch + return false; + } + + bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo, + const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, + const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) { + // remove references from other, so that type variables can only bind to value types + bindTo = bindTo->stripReferences(); + + auto tyVar = openVars.find( typeInst->get_name() ); + assert( tyVar != openVars.end() ); + if ( ! tyVarCompatible( tyVar->second, other ) ) return false; + + if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false; + + if ( ClassRef curClass = lookup( typeInst->get_name() ) ) { + BoundType curData = curClass.get_bound(); + if ( curData.type ) { + Type* common = nullptr; + // attempt to unify equivalence class type (which needs its qualifiers restored) + // with the target type + Type* newType = curData.type->clone(); + newType->get_qualifiers() = typeInst->get_qualifiers(); + if ( unifyInexact( newType, bindTo, *this, need, have, openVars, + widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) { + if ( common ) { + // update bound type to common type + common->get_qualifiers() = Type::Qualifiers{}; + curData.type = common; + bindings = bindings->set( curClass.update_root(), curData ); + } + return true; + } else return false; + } else { + // update bound type to other type + curData.type = bindTo->clone(); + curData.type->get_qualifiers() = Type::Qualifiers{}; + curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + bindings = bindings->set( curClass.get_root(), curData ); + } + } else { + // make new class consisting entirely of this variable + BoundType curData{ bindTo->clone(), widenMode.first && widenMode.second, data }; + curData.type->get_qualifiers() = Type::Qualifiers{}; + classes = classes->add( curClass.get_root() ); + bindings = bindings->set( curClass.get_root(), curData ); + } + return true; + } + + bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2, + const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, + const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) { + ClassRef class1 = env.lookup( var1->get_name() ); + ClassRef class2 = env.lookup( var2->get_name() ); + + // exit early if variables already bound together + if ( class1 && class2 && class1 == class2 ) { + BoundType data1 = class1.get_bound(); + // narrow the binding if needed + if ( data1.allowWidening && widenMode.first != widenMode.second ) { + data1.allowWidening = false; + bindings = bindings->set( class1.get_root(), data1 ); + } + return true; + } + + BoundType data1 = class1 ? class1.get_bound() : BoundType{}; + BoundType data2 = class2 ? class2.get_bound() : BoundType{}; + + bool widen1 = data1.allowWidening && widenMode.widenFirst; + bool widen2 = data2.allowWidening && widenMode.widenSecond; + + if ( data1.type && data2.type ) { + // attempt to unify bound classes + Type* common = nullptr; + if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have, + openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) { + // merge type variables + interned_string root = mergeClasses( class1.update_root(), class2.update_root() ); + // update bindings + data1.allowWidening = widen1 && widen2; + if ( common ) { + common->get_qualifiers() = Type::Qualifiers{}; + data1.type = common; + } + bindings = bindings->set( root, data1 ); + } else return false; + } else if ( class1 && class2 ) { + // both classes exist, only one bound -- merge type variables + auto merged = mergeClasses( class1.get_root(), class2.get_root() ); + // remove subordinate binding + bindings = bindings->erase( merged.second ); + // update root binding (narrow widening as needed, or set new binding for changed root) + if ( data1.type ) { + if ( data1.allowWidening != widen1 ) { + data1.allowWidening = widen1; + bindings = bindings->set( merged.first, data1 ); + } else if ( merged.first == class2.get_root() ) { + bindings = bindings->set( merged.first, data1 ); + } + } else /* if ( data2.type ) */ { + if ( data2.allowWidening != widen2 ) { + data2.allowWidening = widen2; + bindings = bindings->set( root, data2 ); + } else if ( merged.first == class1.get_root() ) { + bindings = bindings->set( merged.first, data2 ); + } + } + } else if ( class1 ) { + // add unbound var2 to class1 + classes = classes->add( class2.get_root() ); + auto merged = mergeClasses( class1.get_root(), class2.get_root() ); + // update bindings (narrow as needed, or switch binding to root) + if ( merged.first == class2.get_root() ) { + data1.allowWidening = widen1; + bindings = bindings->erase( merged.second )->set( merged.first, data1 ); + } else if ( data1.allowWidening != widen1 ) { + bindings = bindings->set( merged.first, data1 ); + } + } else if ( class2 ) { + // add unbound var1 to class1 + classes = classes->add( class1.get_root() ); + auto merged = mergeClasses( class1.get_root(), class2.get_root() ); + // update bindings (narrow as needed, or switch binding to root) + if ( merged.first == class1.get_root() ) { + data2.allowWidening = widen2; + bindings = bindings->erase( merged.second )->set( merged.first, data2 ); + } else if ( data2.allowWidening != widen2 ) { + bindings = bindings->set( merged.first, data2 ); + } + } else { + // make new class with pair of unbound vars + classes = classes->add( class1.get_root() )->add( class2.get_root() ); + auto merged = mergeClasses( class1.get_root(), class2.get_root() ); + bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } ); + } + return true; + } + +#if !1 /// Removes any class from env that intersects eqvClass void filterOverlappingClasses( std::list &env, const EqvClass &eqvClass ) { @@ -180,32 +363,4 @@ } - void TypeEnvironment::combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ) { - TypeEnvironment secondCopy( second ); - for ( std::list< EqvClass >::iterator firstClass = env.begin(); firstClass != env.end(); ++firstClass ) { - EqvClass &newClass = *firstClass; - std::set< std::string > newVars; - for ( std::set< std::string >::const_iterator var = firstClass->vars.begin(); var != firstClass->vars.end(); ++var ) { - std::list< EqvClass >::iterator secondClass = secondCopy.internal_lookup( *var ); - if ( secondClass != secondCopy.env.end() ) { - newVars.insert( secondClass->vars.begin(), secondClass->vars.end() ); - if ( secondClass->type ) { - if ( newClass.type ) { - newClass.type = combineFunc( newClass.type, secondClass->type ); - newClass.allowWidening = newClass.allowWidening && secondClass->allowWidening; - } else { - newClass.type = secondClass->type->clone(); - newClass.allowWidening = secondClass->allowWidening; - } // if - } // if - secondCopy.env.erase( secondClass ); - } // if - } // for - newClass.vars.insert( newVars.begin(), newVars.end() ); - } // for - for ( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) { - env.push_back( *secondClass ); - } // for - } - void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) { @@ -231,8 +386,9 @@ return out; } +#endif PassVisitor & operator<<( PassVisitor & gc, const TypeEnvironment & env ) { - for ( const EqvClass & c : env ) { - maybeAccept( c.type, gc ); + for ( ClassRef c : env ) { + maybeAccept( c.get_bound().type, gc ); } return gc; Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/TypeEnvironment.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -7,27 +7,33 @@ // TypeEnvironment.h -- // -// Author : Richard C. Bilson +// Author : Aaron B. Moss // Created On : Sun May 17 12:24:58 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:35:45 2017 -// Update Count : 3 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 13 16:31:00 2018 +// Update Count : 4 // #pragma once -#include // for ostream -#include // for list, list<>::iterator, list<>... -#include // for map, map<>::value_compare -#include // for set -#include // for string - -#include "SynTree/Declaration.h" // for TypeDecl::Data, DeclarationWit... -#include "SynTree/SynTree.h" // for UniqueId -#include "SynTree/Type.h" // for Type, Type::ForallList -#include "SynTree/TypeSubstitution.h" // for TypeSubstitution - -template< typename Pass > -class PassVisitor; +#include // for ostream +#include +#include // for list, list<>::iterator, list<>... +#include // for map, map<>::value_compare +#include // for set +#include // for string +#include // for pair +#include // for vector + +#include "Common/InternedString.h" // for interned_string +#include "Common/PersistentDisjointSet.h" // for PersistentDisjointSet +#include "Common/PersistentMap.h" // for PersistentMap +#include "SynTree/Declaration.h" // for TypeDecl::Data, DeclarationWit... +#include "SynTree/SynTree.h" // for UniqueId +#include "SynTree/Type.h" // for Type, TypeInstType, Type::ForallList +#include "SynTree/TypeSubstitution.h" // for TypeSubstitution + +template< typename Pass > class PassVisitor; class GcTracer; +namespace SymTab { class Indexer; } namespace ResolvExpr { @@ -40,14 +46,16 @@ // declarations. // - // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator. + // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this + // comparator. // // Note: since this compares pointers for position, minor changes in the source file that affect // memory layout can alter compilation time in unpredictable ways. For example, the placement // of a line directive can reorder type pointers with respect to each other so that assertions - // are seen in different orders, causing a potentially different number of unification calls when - // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives - // alone, so it would be nice to fix this comparison so that assertions compare more consistently. - // I've tried to modify this to compare on mangle name instead of type as the second comparator, but - // this causes some assertions to never be recorded. More investigation is needed. + // are seen in different orders, causing a potentially different number of unification calls + // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering + // line directives alone, so it would be nice to fix this comparison so that assertions compare + // more consistently. I've tried to modify this to compare on mangle name instead of type as + // the second comparator, but this causes some assertions to never be recorded. More + // investigation is needed. struct AssertCompare { bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const { @@ -59,7 +67,8 @@ struct AssertionSetValue { bool isUsed; - // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type, - // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is - // the ID of the assertion that pulled in the current assertion. + // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID + // of an assertion on the current type, with each successive ID being the ID of an + // assertion pulled in by the previous ID. The last ID in the chain is the ID of the + // assertion that pulled in the current assertion. std::list< UniqueId > idChain; }; @@ -70,4 +79,13 @@ void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 ); + /// A data structure for holding all the necessary information for a type binding + struct BoundType { + Type* type; + bool allowWidening; + TypeDecl::Data data; + }; + +#if 0 + /// An equivalence class, with its binding information struct EqvClass { std::set< std::string > vars; @@ -78,12 +96,114 @@ void initialize( const EqvClass &src, EqvClass &dest ); EqvClass(); + EqvClass( std::vector&& vars, BoundType&& bound ); EqvClass( const EqvClass &other ); EqvClass &operator=( const EqvClass &other ); void print( std::ostream &os, Indenter indent = {} ) const; }; +#endif + + class TypeEnvironment; + + /// A reference to an equivalence class that may be used to constitute one from its environment + class ClassRef { + friend TypeEnvironment; + + const TypeEnvironment* env; ///< Containing environment + interned_string root; ///< Name of root type + + public: + ClassRef() : env(nullptr), root(nullptr) {} + ClassRef( const TypeEnvironment* env, interned_string root ) : env(env), root(root) {} + + /// Gets the root of the reference equivalence class; + interned_string get_root() const { return root; } + + /// Ensures that root is still the representative element of this typeclass; + /// undefined behaviour if called without referenced typeclass; returns new root + inline interned_string update_root(); + + /// Gets the type variables of the referenced equivalence class, empty list for none + template> + inline T get_vars() const; + + /// Gets the bound type information of the referenced equivalence class, default if none + inline BoundType get_bound() const; + +#if 0 + /// Gets the referenced equivalence class + inline EqvClass get_class() const; + EqvClass operator* () const { return get_class(); } +#endif + + // Check that there is a referenced typeclass + explicit operator bool() const { return env != nullptr; } + + bool operator== (const ClassRef& o) const { return env == o.env && root == o.root; } + bool operator!= (const ClassRef& o) const { return !(*this == o); } + }; class TypeEnvironment { + friend ClassRef; + + /// Backing storage for equivalence classes + using Classes = PersistentDisjointSet; + /// Type bindings included in this environment (from class root) + using Bindings = PersistentMap; + + /// Sets of equivalent type variables, stored by name + Classes* classes; + /// Bindings from roots of equivalence classes to type binding information. + /// All roots have a binding so that the list of classes can be reconstituted, though these + /// may be null. + Bindings* bindings; + + /// Merges the classes rooted at root1 and root2, returning a pair containing the root and + /// child of the bound class. Does not check for validity of merge. + std::pair mergeClasses( + interned_string root1, interned_string root2 ); + public: - const EqvClass* lookup( const std::string &var ) const; + class iterator : public std::iterator< + std::forward_iterator_tag, + ClassRef, + std::iterator_traits::difference_type, + ClassRef, + ClassRef> { + friend TypeEnvironment; + + const TypeEnvironment* env; + Bindings::iterator it; + + iterator(const TypeEnvironment* e, Bindings::iterator&& i) : env(e), it(std::move(i)) {} + + ClassRef ref() const { return { env, it->first }; } + public: + iterator() = default; + + reference operator* () { return ref(); } + pointer operator-> () { return ref(); } + + iterator& operator++ () { ++it; return *this; } + iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; } + + bool operator== (const iterator& o) const { return env == o.env && it == o.it; } + bool operator!= (const iterator& o) const { return !(*this == o); } + }; + + /// Finds a reference to the class containing `var`, invalid if none such. + /// returned root variable will be valid regardless + ClassRef lookup( interned_string var ) const; + ClassRef lookup( const std::string &var ) const { return lookup( var ); } + + /// Binds a type variable to a type; returns false if fails + bool bindVar( TypeInstType* typeInst, Type* bindTo, const TypeDecl::Data& data, + AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, + WidenMode widenMode, const SymTab::Indexer& indexer ); + + /// Binds two type variables together; returns false if fails + bool bindVarToVar( TypeInstType* var1, TypeInstType* var2, const TypeDecl::Data& data, + AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, + WidenMode widenMode, const SymTab::Indexer& indexer ); +#if !1 void add( const EqvClass &eqvClass ); void add( EqvClass &&eqvClass ); @@ -93,25 +213,44 @@ template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const; void makeSubstitution( TypeSubstitution &result ) const; - bool isEmpty() const { return env.empty(); } +#endif + bool isEmpty() const { return classes->empty(); } +#if !1 void print( std::ostream &os, Indenter indent = {} ) const; - void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ); void simpleCombine( const TypeEnvironment &second ); void extractOpenVars( OpenVarSet &openVars ) const; +#endif TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } +#if !1 /// Iteratively adds the environment of a new actual (with allowWidening = false), /// and extracts open variables. void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ); - - typedef std::list< EqvClass >::iterator iterator; - iterator begin() { return env.begin(); } - iterator end() { return env.end(); } +#endif + + iterator begin() { return { this, bindings->begin() }; } + iterator end() { return { this, bindings->end() }; } +#if 0 typedef std::list< EqvClass >::const_iterator const_iterator; const_iterator begin() const { return env.begin(); } const_iterator end() const { return env.end(); } - private: - std::list< EqvClass > env; - std::list< EqvClass >::iterator internal_lookup( const std::string &var ); - }; +#endif + }; + + void ClassRef::update_root() { return root = env->classes->find( root ); } + + template + T ClassRef::get_vars() const { + T vars; + env->classes->find_class( root, std::inserter(vars, vars.end()) ); + return vars; + } + + BoundType ClassRef::get_bound() const { + return env->bindings->get_or_default( root, BoundType{} ); + } + +#if 0 + EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; } +#endif template< typename SynTreeClass > @@ -129,5 +268,7 @@ } +#if !1 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); +#endif PassVisitor & operator<<( PassVisitor & gc, const TypeEnvironment & env ); Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 1d7b0a8b3222b5be41c98932430124a3777a31a9) +++ src/ResolvExpr/Unify.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) @@ -31,5 +31,5 @@ #include "SynTree/Visitor.h" // for Visitor #include "Tuples/Tuples.h" // for isTtype -#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet +#include "TypeEnvironment.h" // for ClassRef, AssertionSet, OpenVarSet #include "Unify.h" #include "typeops.h" // for flatten, occurs, commonType @@ -128,21 +128,4 @@ return typeInst->get_isFtype(); } // if - return false; - } - - bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) { - switch ( data.kind ) { - case TypeDecl::Dtype: - // to bind to an object type variable, the type must not be a function type. - // if the type variable is specified to be a complete type then the incoming - // type must also be complete - // xxx - should this also check that type is not a tuple type and that it's not a ttype? - return ! isFtype( type ) && (! data.isComplete || type->isComplete() ); - case TypeDecl::Ftype: - return isFtype( type ); - case TypeDecl::Ttype: - // ttype unifies with any tuple type - return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type ); - } // switch return false; } @@ -525,8 +508,9 @@ void premutate( TypeInstType * ) { visit_children = false; } Type * postmutate( TypeInstType * typeInst ) { - if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { + if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) { // expand ttype parameter into its actual type - if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) { - return eqvClass->type->clone(); + BoundType cBound = eqvClass.get_bound(); + if ( cBound.data.kind == TypeDecl::Ttype && cBound.type ) { + return cBound.type->clone(); } }