Index: src/AST/Attribute.hpp =================================================================== --- src/AST/Attribute.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Attribute.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -51,4 +51,6 @@ template friend node_t * mutate(const node_t * node); + template + friend node_t * shallowCopy(const node_t * node); }; Index: src/AST/CVQualifiers.hpp =================================================================== --- src/AST/CVQualifiers.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/CVQualifiers.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -27,12 +27,11 @@ Restrict = 1 << 1, Volatile = 1 << 2, - Lvalue = 1 << 3, - Mutex = 1 << 4, - Atomic = 1 << 5, - NumQualifiers = 6 + Mutex = 1 << 3, + Atomic = 1 << 4, + NumQualifiers = 5 }; /// Mask for equivalence-preserving qualfiers - enum { EquivQualifiers = ~(Restrict | Lvalue) }; + enum { EquivQualifiers = ~Restrict }; /// Underlying data for qualifiers @@ -44,5 +43,4 @@ bool is_restrict : 1; bool is_volatile : 1; - bool is_lvalue : 1; bool is_mutex : 1; bool is_atomic : 1; Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Convert.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -620,4 +620,15 @@ tgt->result = get().accept1(src->result); + // Unconditionally use a clone of the result type. + // We know this will leak some objects: much of the immediate conversion result. + // In some cases, using the conversion result directly gives unintended object sharing. + // A parameter (ObjectDecl, a child of a FunctionType) is shared by the weak-ref cache. + // But tgt->result must be fully owned privately by tgt. + // Applying these conservative copies here means + // - weak references point at the declaration's copy, not these expr.result copies (good) + // - we copy more objects than really needed (bad, tolerated) + if (tgt->result) { + tgt->result = tgt->result->clone(); + } return visitBaseExpr_skipResultType(src, tgt); } @@ -2117,5 +2128,6 @@ old->location, GET_ACCEPT_1(member, DeclWithType), - GET_ACCEPT_1(aggregate, Expr) + GET_ACCEPT_1(aggregate, Expr), + ast::MemberExpr::NoOpConstructionChosen ) ); Index: src/AST/Copy.hpp =================================================================== --- src/AST/Copy.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) +++ src/AST/Copy.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -0,0 +1,126 @@ +// +// 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. +// +// Copy.hpp -- Provides functions to copy the AST. +// +// Author : Andrew Beach +// Created On : Wed Jul 10 16:13:00 2019 +// Last Modified By : Andrew Beach +// Last Modified On : Thr Jul 11 10:38:00 2019 +// Update Count : 0 +// + +#include "Decl.hpp" +#include "Expr.hpp" +#include "Pass.hpp" +#include "Stmt.hpp" +#include "Type.hpp" + +namespace ast { + +template +node_t * shallowCopy( const node_t * node ); +/* Create a shallow copy of the node given. + * + * The new node has all the same primitive field values and points to the + * same children nodes as the parent. + */ + +template +node_t * deepCopy( const node_t * localRoot ); +/* Create a deep copy of the tree rooted at localRoot. + * + * This creates a copy of every node in the sub-tree (reachable by strong + * reference from local_root) and updates any readonly pointers on those nodes + * that point to another node in the sub-tree to the new version of that node. + */ + +class DeepCopyCore { + std::unordered_map< const Node *, const Node * > nodeCache; + std::unordered_set< readonly * > readonlyCache; + +public: + template + const node_t * previsit( const node_t * node ) { + const node_t * copy = shallowCopy( node ); + nodeCache.insert( std::make_pair( node, copy ) ); + return copy; + } + + void postvisit( const AggregateDecl * node ) { + readonlyCache.insert( (readonly *) & node->parent ); + } + + void postvisit( const StructInstType * node ) { + readonlyCache.insert( (readonly *) & node->base ); + } + + void postvisit( const UnionInstType * node ) { + readonlyCache.insert( (readonly *) & node->base ); + } + + void postvisit( const EnumInstType * node ) { + readonlyCache.insert( (readonly *) & node->base ); + } + + void postvisit( const TraitInstType * node ) { + readonlyCache.insert( (readonly *) & node->base ); + } + + void postvisit( const TypeInstType * node ) { + readonlyCache.insert( (readonly *) & node->base ); + } + + void postvisit( const ImplicitCtorDtorStmt * node ) { + readonlyCache.insert( (readonly *) & node->callStmt ); + } + + void postvisit( const MemberExpr * node ) { + readonlyCache.insert( (readonly *) & node->member ); + } + + void postvisit( const VariableExpr * node ) { + readonlyCache.insert( (readonly *) & node->var ); + } + + void postvisit( const OffsetofExpr * node ) { + readonlyCache.insert( (readonly *) & node->member ); + } + + void postvisit( const DeletedExpr * node ) { + readonlyCache.insert( (readonly *) & node->deleteStmt ); + } + + void readonlyUpdates() { + for ( readonly * ptr : readonlyCache ) { + auto it = nodeCache.find( ptr->get() ); + if ( nodeCache.end() != it ) { + *ptr = it->second; + } + } + } +}; + +template +node_t * shallowCopy( const node_t * localRoot ) { + return localRoot->clone(); +} + +template +node_t * deepCopy( const node_t * localRoot ) { + Pass< DeepCopyCore > dc; + node_t const * newRoot = localRoot->accept( dc ); + dc.pass.readonlyUpdates(); + return const_cast< node_t * >( newRoot ); +} + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Decl.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -50,5 +50,7 @@ const Type * FunctionDecl::get_type() const { return type.get(); } -void FunctionDecl::set_type(Type * t) { type = strict_dynamic_cast< FunctionType* >( t ); } +void FunctionDecl::set_type( const Type * t ) { + type = strict_dynamic_cast< const FunctionType * >( t ); +} // --- TypeDecl Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Decl.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -33,5 +33,7 @@ // Must be included in *all* AST classes; should be #undef'd at the end of the file -#define MUTATE_FRIEND template friend node_t * mutate(const node_t * node); +#define MUTATE_FRIEND \ + template friend node_t * mutate(const node_t * node); \ + template friend node_t * shallowCopy(const node_t * node); namespace ast { @@ -88,5 +90,5 @@ virtual const Type * get_type() const = 0; /// Set type of this declaration. May be verified by subclass - virtual void set_type(Type *) = 0; + virtual void set_type( const Type * ) = 0; const DeclWithType * accept( Visitor & v ) const override = 0; @@ -111,5 +113,5 @@ const Type* get_type() const override { return type; } - void set_type( Type * ty ) override { type = ty; } + void set_type( const Type * ty ) override { type = ty; } const DeclWithType * accept( Visitor& v ) const override { return v.visit( this ); } @@ -133,5 +135,5 @@ const Type * get_type() const override; - void set_type(Type * t) override; + void set_type( const Type * t ) override; bool has_body() const { return stmts; } @@ -150,6 +152,7 @@ std::vector> assertions; - NamedTypeDecl( const CodeLocation& loc, const std::string& name, Storage::Classes storage, - Type* b, Linkage::Spec spec = Linkage::Cforall ) + NamedTypeDecl( + const CodeLocation & loc, const std::string & name, Storage::Classes storage, + const Type * b, Linkage::Spec spec = Linkage::Cforall ) : Decl( loc, name, storage, spec ), base( b ), params(), assertions() {} @@ -186,8 +189,9 @@ }; - TypeDecl( const CodeLocation & loc, const std::string & name, Storage::Classes storage, Type * b, - Kind k, bool s, Type * i = nullptr ) - : NamedTypeDecl( loc, name, storage, b ), kind( k ), sized( k == Ttype || s ), - init( i ) {} + TypeDecl( + const CodeLocation & loc, const std::string & name, Storage::Classes storage, + const Type * b, TypeVar::Kind k, bool s, const Type * i = nullptr ) + : NamedTypeDecl( loc, name, storage, b ), kind( k ), sized( k == TypeVar::Ttype || s ), + init( i ) {} const char * typeString() const override; Index: src/AST/Eval.hpp =================================================================== --- src/AST/Eval.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) +++ src/AST/Eval.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -0,0 +1,37 @@ +// +// 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. +// +// Eval.hpp -- +// +// Author : Aaron B. Moss +// Created On : Fri Jun 28 14:00:00 2019 +// Last Modified By : Aaron B. Moss +// Created On : Fri Jun 28 14:00:00 2019 +// Update Count : 1 +// + +#include +#include + +#include "Expr.hpp" + +namespace ast { + +/// Create a new UntypedExpr with the given arguments +template< typename... Args > +UntypedExpr * call( const CodeLocation & loc, const std::string & name, Args &&... args ) { + return new UntypedExpr { + loc, new NameExpr { loc, name }, + std::vector< ptr< Expr > > { std::forward< Args >( args )... } }; +} + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/Expr.cpp =================================================================== --- src/AST/Expr.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Expr.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -20,5 +20,8 @@ #include +#include "Copy.hpp" // for shallowCopy +#include "Eval.hpp" // for call #include "GenericSubstitution.hpp" +#include "LinkageSpec.hpp" #include "Stmt.hpp" #include "Type.hpp" @@ -27,9 +30,18 @@ #include "Common/SemanticError.h" #include "GenPoly/Lvalue.h" // for referencesPermissable -#include "InitTweak/InitTweak.h" // for getPointerBase +#include "InitTweak/InitTweak.h" // for getFunction, getPointerBase #include "ResolvExpr/typeops.h" // for extractResultType #include "Tuples/Tuples.h" // for makeTupleType namespace ast { + +namespace { + std::set const lvalueFunctionNames = {"*?", "?[?]"}; +} + +// --- Expr +bool Expr::get_lvalue() const { + return false; +} // --- ApplicationExpr @@ -46,4 +58,11 @@ } +bool ApplicationExpr::get_lvalue() const { + if ( const DeclWithType * func = InitTweak::getFunction( this ) ) { + return func->linkage == Linkage::Intrinsic && lvalueFunctionNames.count( func->name ); + } + return false; +} + // --- UntypedExpr @@ -51,7 +70,5 @@ assert( arg ); - UntypedExpr * ret = new UntypedExpr{ - loc, new NameExpr{loc, "*?"}, std::vector>{ ptr{ arg } } - }; + UntypedExpr * ret = call( loc, "*?", arg ); if ( const Type * ty = arg->result ) { const Type * base = InitTweak::getPointerBase( ty ); @@ -65,8 +82,12 @@ // base type ret->result = base; - add_qualifiers( ret->result, CV::Lvalue ); } } return ret; +} + +bool UntypedExpr::get_lvalue() const { + std::string fname = InitTweak::getFunctionName( this ); + return lvalueFunctionNames.count( fname ); } @@ -74,7 +95,5 @@ assert( lhs && rhs ); - UntypedExpr * ret = new UntypedExpr{ - loc, new NameExpr{loc, "?=?"}, std::vector>{ ptr{ lhs }, ptr{ rhs } } - }; + UntypedExpr * ret = call( loc, "?=?", lhs, rhs ); if ( lhs->result && rhs->result ) { // if both expressions are typed, assumes that this assignment is a C bitwise assignment, @@ -108,8 +127,7 @@ AddressExpr::AddressExpr( const CodeLocation & loc, const Expr * a ) : Expr( loc ), arg( a ) { if ( arg->result ) { - if ( arg->result->is_lvalue() ) { + if ( arg->get_lvalue() ) { // lvalue, retains all levels of reference, and gains a pointer inside the references Type * res = addrType( arg->result ); - res->set_lvalue( false ); // result of & is never an lvalue result = res; } else { @@ -118,5 +136,4 @@ dynamic_cast< const ReferenceType * >( arg->result.get() ) ) { Type * res = addrType( refType->base ); - res->set_lvalue( false ); // result of & is never an lvalue result = res; } else { @@ -139,8 +156,19 @@ : Expr( loc, new VoidType{} ), arg( a ), isGenerated( g ) {} +bool CastExpr::get_lvalue() const { + // This is actually wrong by C, but it works with our current set-up. + return arg->get_lvalue(); +} + // --- KeywordCastExpr const char * KeywordCastExpr::targetString() const { return AggregateDecl::aggrString( target ); +} + +// --- UntypedMemberExpr + +bool UntypedMemberExpr::get_lvalue() const { + return aggregate->get_lvalue(); } @@ -153,10 +181,59 @@ assert( aggregate->result ); - // take ownership of member type - result = mem->get_type(); + // Deep copy on result type avoids mutation on transitively multiply referenced object. + // + // Example, adapted from parts of builtins and bootloader: + // + // forall(dtype T) + // struct __Destructor { + // T * object; + // void (*dtor)(T *); + // }; + // + // forall(dtype S) + // void foo(__Destructor(S) &d) { + // if (d.dtor) { // here + // } + // } + // + // Let e be the "d.dtor" guard espression, which is MemberExpr after resolve. Let d be the + // declaration of member __Destructor.dtor (an ObjectDecl), as accessed via the top-level + // declaration of __Destructor. Consider the types e.result and d.type. In the old AST, one + // is a clone of the other. Ordinary new-AST use would set them up as a multiply-referenced + // object. + // + // e.result: PointerType + // .base: FunctionType + // .params.front(): ObjectDecl, the anonymous parameter of type T* + // .type: PointerType + // .base: TypeInstType + // let x = that + // let y = similar, except start from d.type + // + // Consider two code lines down, genericSubstitution(...).apply(result). + // + // Applying this chosen-candidate's type substitution means modifying x, substituting + // S for T. This mutation should affect x and not y. + + result = deepCopy(mem->get_type()); + // substitute aggregate generic parameters into member type genericSubstitution( aggregate->result ).apply( result ); - // ensure lvalue and appropriate restrictions from aggregate type - add_qualifiers( result, aggregate->result->qualifiers | CV::Lvalue ); + // ensure appropriate restrictions from aggregate type + add_qualifiers( result, aggregate->result->qualifiers ); +} + +MemberExpr::MemberExpr( const CodeLocation & loc, const DeclWithType * mem, const Expr * agg, + MemberExpr::NoOpConstruction overloadSelector ) +: Expr( loc ), member( mem ), aggregate( agg ) { + assert( member ); + assert( aggregate ); + assert( aggregate->result ); + (void) overloadSelector; +} + +bool MemberExpr::get_lvalue() const { + // This is actually wrong by C, but it works with our current set-up. + return true; } @@ -170,6 +247,10 @@ assert( var ); assert( var->get_type() ); - result = var->get_type(); - add_qualifiers( result, CV::Lvalue ); + result = shallowCopy( var->get_type() ); +} + +bool VariableExpr::get_lvalue() const { + // It isn't always an lvalue, but it is never an rvalue. + return true; } @@ -258,4 +339,11 @@ : Expr( loc, new BasicType{ BasicType::SignedInt } ), arg1( a1 ), arg2( a2 ), isAnd( ia ) {} +// --- CommaExpr +bool CommaExpr::get_lvalue() const { + // This is wrong by C, but the current implementation uses it. + // (ex: Specialize, Lvalue and Box) + return arg2->get_lvalue(); +} + // --- ConstructorExpr @@ -276,5 +364,8 @@ assert( t && i ); result = t; - add_qualifiers( result, CV::Lvalue ); +} + +bool CompoundLiteralExpr::get_lvalue() const { + return true; } @@ -293,5 +384,8 @@ // like MemberExpr, TupleIndexExpr is always an lvalue result = type->types[ index ]; - add_qualifiers( result, CV::Lvalue ); +} + +bool TupleIndexExpr::get_lvalue() const { + return tuple->get_lvalue(); } Index: src/AST/Expr.hpp =================================================================== --- src/AST/Expr.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Expr.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -31,5 +31,8 @@ // Must be included in *all* AST classes; should be #undef'd at the end of the file -#define MUTATE_FRIEND template friend node_t * mutate(const node_t * node); +#define MUTATE_FRIEND \ + template friend node_t * mutate(const node_t * node); \ + template friend node_t * shallowCopy(const node_t * node); + class ConverterOldToNew; @@ -185,4 +188,5 @@ Expr * set_extension( bool ex ) { extension = ex; return this; } + virtual bool get_lvalue() const; virtual const Expr * accept( Visitor & v ) const override = 0; @@ -201,4 +205,6 @@ ApplicationExpr( const CodeLocation & loc, const Expr * f, std::vector> && as = {} ); + bool get_lvalue() const final; + const Expr * accept( Visitor & v ) const override { return v.visit( this ); } private: @@ -215,4 +221,6 @@ UntypedExpr( const CodeLocation & loc, const Expr * f, std::vector> && as = {} ) : Expr( loc ), func( f ), args( std::move(as) ) {} + + bool get_lvalue() const final; /// Creates a new dereference expression @@ -291,4 +299,6 @@ CastExpr( const Expr * a ) : CastExpr( a->location, a, GeneratedCast ) {} + bool get_lvalue() const final; + const Expr * accept( Visitor & v ) const override { return v.visit( this ); } private: @@ -338,4 +348,6 @@ : Expr( loc ), member( mem ), aggregate( agg ) { assert( aggregate ); } + bool get_lvalue() const final; + const Expr * accept( Visitor & v ) const override { return v.visit( this ); } private: @@ -352,8 +364,17 @@ MemberExpr( const CodeLocation & loc, const DeclWithType * mem, const Expr * agg ); + bool get_lvalue() const final; + const Expr * accept( Visitor & v ) const override { return v.visit( this ); } private: MemberExpr * clone() const override { return new MemberExpr{ *this }; } MUTATE_FRIEND + + // Custructor overload meant only for AST conversion + enum NoOpConstruction { NoOpConstructionChosen }; + MemberExpr( const CodeLocation & loc, const DeclWithType * mem, const Expr * agg, + NoOpConstruction overloadSelector ); + friend class ::ConverterOldToNew; + friend class ::ConverterNewToOld; }; @@ -365,4 +386,6 @@ VariableExpr( const CodeLocation & loc ); VariableExpr( const CodeLocation & loc, const DeclWithType * v ); + + bool get_lvalue() const final; /// generates a function pointer for a given function @@ -532,5 +555,9 @@ CommaExpr( const CodeLocation & loc, const Expr * a1, const Expr * a2 ) - : Expr( loc ), arg1( a1 ), arg2( a2 ) {} + : Expr( loc ), arg1( a1 ), arg2( a2 ) { + this->result = a2->result; + } + + bool get_lvalue() const final; const Expr * accept( Visitor & v ) const override { return v.visit( this ); } @@ -605,4 +632,6 @@ CompoundLiteralExpr( const CodeLocation & loc, const Type * t, const Init * i ); + bool get_lvalue() const final; + const Expr * accept( Visitor & v ) const override { return v.visit( this ); } private: @@ -660,4 +689,6 @@ TupleIndexExpr( const CodeLocation & loc, const Expr * t, unsigned i ); + + bool get_lvalue() const final; const Expr * accept( Visitor & v ) const override { return v.visit( this ); } Index: src/AST/ForallSubstitutionTable.cpp =================================================================== --- src/AST/ForallSubstitutionTable.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) +++ src/AST/ForallSubstitutionTable.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -0,0 +1,54 @@ +// +// 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. +// +// ForallSubstitutionTable.cpp -- +// +// Author : Aaron B. Moss +// Created On : Thu Jun 27 14:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Jun 27 14:00:00 2019 +// Update Count : 1 +// + +#include "ForallSubstitutionTable.hpp" + +#include +#include + +#include "Copy.hpp" // for shallowCopy +#include "Decl.hpp" +#include "Node.hpp" +#include "Type.hpp" +#include "Visitor.hpp" + +namespace ast { + +std::vector< ptr< TypeDecl > > ForallSubstitutionTable::clone( + const std::vector< ptr< TypeDecl > > & forall, Visitor & v +) { + std::vector< ptr< TypeDecl > > new_forall; + new_forall.reserve( forall.size() ); + + for ( const ast::TypeDecl * d : forall ) { + // create cloned type decl and insert into substitution map before further mutation + auto new_d = shallowCopy( d ); + decls.insert( d, new_d ); + // perform other mutations and add to output + auto newer_d = v.visit( new_d ); + assert( new_d == newer_d && "Newly cloned TypeDecl must retain identity" ); + new_forall.emplace_back( new_d ); + } + + return new_forall; +} + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/ForallSubstitutionTable.hpp =================================================================== --- src/AST/ForallSubstitutionTable.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) +++ src/AST/ForallSubstitutionTable.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -0,0 +1,57 @@ +// +// 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. +// +// ForallSubstitutionTable.hpp -- +// +// Author : Aaron B. Moss +// Created On : Thu Jun 27 14:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Jun 27 14:00:00 2019 +// Update Count : 1 +// + +#pragma once + +#include + +#include "Node.hpp" // for ptr +#include "Common/ScopedMap.h" + +namespace ast { + +class TypeDecl; +class Visitor; + +/// Wrapper for TypeDecl substitution table +class ForallSubstitutionTable { + ScopedMap< const TypeDecl *, const TypeDecl * > decls; + +public: + /// Replaces given declaration with value in the table, if present, otherwise returns argument + const TypeDecl * replace( const TypeDecl * d ) { + auto it = decls.find( d ); + if ( it != decls.end() ) return it->second; + return d; + } + + /// Builds a new forall list mutated according to the given visitor + std::vector< ptr< TypeDecl > > clone( + const std::vector< ptr< TypeDecl > > & forall, Visitor & v ); + + /// Introduces a new lexical scope + void beginScope() { decls.beginScope(); } + + /// Concludes a lexical scope + void endScope() { decls.endScope(); } +}; + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/ForallSubstitutor.hpp =================================================================== --- src/AST/ForallSubstitutor.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) +++ src/AST/ForallSubstitutor.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -0,0 +1,58 @@ +// +// 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. +// +// ForallSubstitutor.hpp -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 26 15:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 26 15:00:00 2019 +// Update Count : 1 +// + +#include "Pass.hpp" + +namespace ast { + +class Expr; + +/// Visitor that correctly substitutes TypeDecl while maintaining TypeInstType bindings. +/// Also has some convenience methods to mutate fields. +struct ForallSubstitutor : public WithForallSubstitutor, public WithVisitorRef { + /// Substitute TypeInstType base type + readonly< TypeDecl > operator() ( const readonly< TypeDecl > & o ) { + return subs.replace( o ); + } + + /// Make new forall-list clone + ParameterizedType::ForallList operator() ( const ParameterizedType::ForallList & o ) { + return subs.clone( o, *visitor ); + } + + /// Substitute parameter/return type + std::vector< ptr< DeclWithType > > operator() ( const std::vector< ptr< DeclWithType > > & o ) { + std::vector< ptr< DeclWithType > > n; + n.reserve( o.size() ); + for ( const DeclWithType * d : o ) { n.emplace_back( d->accept( *visitor ) ); } + return n; + } + + /// Substitute type parameter list + std::vector< ptr< Expr > > operator() ( const std::vector< ptr< Expr > > & o ) { + std::vector< ptr< Expr > > n; + n.reserve( o.size() ); + for ( const Expr * d : o ) { n.emplace_back( d->accept( *visitor ) ); } + return n; + } +}; + +} // namespace ast + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/Init.hpp =================================================================== --- src/AST/Init.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Init.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -25,5 +25,7 @@ // Must be included in *all* AST classes; should be #undef'd at the end of the file -#define MUTATE_FRIEND template friend node_t * mutate(const node_t * node); +#define MUTATE_FRIEND \ + template friend node_t * mutate(const node_t * node); \ + template friend node_t * shallowCopy(const node_t * node); namespace ast { Index: src/AST/Node.cpp =================================================================== --- src/AST/Node.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Node.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -17,4 +17,5 @@ #include "Fwd.hpp" +#include // MEMORY DEBUG -- for raise #include @@ -29,12 +30,33 @@ #include "Print.hpp" -template< typename node_t, enum ast::Node::ref_type ref_t > -void ast::ptr_base::_inc( const node_t * node ) { node->increment(ref_t); } - -template< typename node_t, enum ast::Node::ref_type ref_t > -void ast::ptr_base::_dec( const node_t * node ) { node->decrement(ref_t); } - -template< typename node_t, enum ast::Node::ref_type ref_t > -void ast::ptr_base::_check() const { if(node) assert(node->was_ever_strong == false || node->strong_count > 0); } +/// MEMORY DEBUG -- allows breaking on ref-count changes of dynamically chosen object. +/// Process to use in GDB: +/// break ast::Node::_trap() +/// run +/// set variable MEM_TRAP_OBJ = +/// disable +/// continue +void * MEM_TRAP_OBJ = nullptr; + +void _trap( const void * node ) { + if ( node == MEM_TRAP_OBJ ) std::raise(SIGTRAP); +} + +template< typename node_t, enum ast::Node::ref_type ref_t > +void ast::ptr_base::_inc( const node_t * node ) { + node->increment(ref_t); + _trap( node ); +} + +template< typename node_t, enum ast::Node::ref_type ref_t > +void ast::ptr_base::_dec( const node_t * node, bool do_delete ) { + _trap( node ); + node->decrement(ref_t, do_delete ); +} + +template< typename node_t, enum ast::Node::ref_type ref_t > +void ast::ptr_base::_check() const { + // if(node) assert(node->was_ever_strong == false || node->strong_count > 0); +} template< typename node_t, enum ast::Node::ref_type ref_t > Index: src/AST/Node.hpp =================================================================== --- src/AST/Node.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Node.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -38,5 +38,5 @@ Node& operator= (const Node&) = delete; Node& operator= (Node&&) = delete; - virtual ~Node() = default; + virtual ~Node() {} virtual const Node * accept( Visitor & v ) const = 0; @@ -57,4 +57,6 @@ template friend node_t * mutate(const node_t * node); + template + friend node_t * shallowCopy(const node_t * node); mutable size_t strong_count = 0; @@ -69,5 +71,5 @@ } - void decrement(ast::Node::ref_type ref) const { + void decrement(ast::Node::ref_type ref, bool do_delete = true) const { switch (ref) { case ref_type::strong: strong_count--; break; @@ -75,5 +77,5 @@ } - if(!strong_count && !weak_count) { + if( do_delete && !strong_count && !weak_count) { delete this; } @@ -94,5 +96,5 @@ assertf( node->weak_count == 0, - "Error: mutating node with weak references to it will invalided some references" + "Error: mutating node with weak references to it will invalidate some references" ); return node->clone(); @@ -104,5 +106,5 @@ // skip mutate if equivalent if ( node->*field == val ) return node; - + // mutate and return node_t * ret = mutate( node ); @@ -123,4 +125,13 @@ (ret->*field)[i] = std::forward< field_t >( val ); return ret; +} + +/// Mutate an entire indexed collection by cloning to accepted value +template +const node_t * mutate_each( const node_t * node, coll_t parent_t::* field, Visitor & v ) { + for ( unsigned i = 0; i < (node->*field).size(); ++i ) { + node = mutate_field_index( node, field, i, (node->*field)[i]->accept( v ) ); + } + return node; } @@ -219,4 +230,13 @@ operator const node_t * () const { _check(); return node; } + const node_t * release() { + const node_t * ret = node; + if ( node ) { + _dec(node, false); + node = nullptr; + } + return ret; + } + /// wrapper for convenient access to dynamic_cast template @@ -244,5 +264,5 @@ void _inc( const node_t * other ); - void _dec( const node_t * other ); + void _dec( const node_t * other, bool do_delete = true ); void _check() const; Index: src/AST/Pass.hpp =================================================================== --- src/AST/Pass.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Pass.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -35,4 +35,6 @@ #include "AST/SymbolTable.hpp" +#include "AST/ForallSubstitutionTable.hpp" + // Private prelude header, needed for some of the magic tricks this class pulls off #include "AST/Pass.proto.hpp" @@ -46,20 +48,21 @@ // // Several additional features are available through inheritance -// | WithTypeSubstitution - provides polymorphic const TypeSubstitution * env for the -// current expression -// | WithStmtsToAdd - provides the ability to insert statements before or after the current -// statement by adding new statements into stmtsToAddBefore or -// stmtsToAddAfter respectively. -// | WithDeclsToAdd - provides the ability to insert declarations before or after the current -// declarations by adding new DeclStmt into declsToAddBefore or -// declsToAddAfter respectively. -// | WithShortCircuiting - provides the ability to skip visiting child nodes; set visit_children -// to false in pre{visit,visit} to skip visiting children -// | WithGuards - provides the ability to save/restore data like a LIFO stack; to save, -// call GuardValue with the variable to save, the variable will -// automatically be restored to its previous value after the corresponding -// postvisit/postmutate teminates. -// | WithVisitorRef - provides an pointer to the templated visitor wrapper -// | WithSymbolTable - provides symbol table functionality +// | WithTypeSubstitution - provides polymorphic const TypeSubstitution * env for the +// current expression +// | WithStmtsToAdd - provides the ability to insert statements before or after the current +// statement by adding new statements into stmtsToAddBefore or +// stmtsToAddAfter respectively. +// | WithDeclsToAdd - provides the ability to insert declarations before or after the +// current declarations by adding new DeclStmt into declsToAddBefore or +// declsToAddAfter respectively. +// | WithShortCircuiting - provides the ability to skip visiting child nodes; set visit_children +// to false in pre{visit,visit} to skip visiting children +// | WithGuards - provides the ability to save/restore data like a LIFO stack; to save, +// call GuardValue with the variable to save, the variable will +// automatically be restored to its previous value after the +// corresponding postvisit/postmutate teminates. +// | WithVisitorRef - provides an pointer to the templated visitor wrapper +// | WithSymbolTable - provides symbol table functionality +// | WithForallSubstitutor - maintains links between TypeInstType and TypeDecl under mutation //------------------------------------------------------------------------------------------------- template< typename pass_t > @@ -202,4 +205,8 @@ container_t< ptr > call_accept( const container_t< ptr > & container ); + /// Mutate forall-list, accounting for presence of type substitution map + template + void mutate_forall( const node_t *& ); + public: /// Logic to call the accept and mutate the parent if needed, delegates call to accept @@ -210,6 +217,6 @@ /// Internal RAII guard for symbol table features struct guard_symtab { - guard_symtab( Pass & pass ): pass( pass ) { __pass::symtab::enter(pass, 0); } - ~guard_symtab() { __pass::symtab::leave(pass, 0); } + guard_symtab( Pass & pass ): pass( pass ) { __pass::symtab::enter(pass.pass, 0); } + ~guard_symtab() { __pass::symtab::leave(pass.pass, 0); } Pass & pass; }; @@ -217,7 +224,16 @@ /// Internal RAII guard for scope features struct guard_scope { - guard_scope( Pass & pass ): pass( pass ) { __pass::scope::enter(pass, 0); } - ~guard_scope() { __pass::scope::leave(pass, 0); } + guard_scope( Pass & pass ): pass( pass ) { __pass::scope::enter(pass.pass, 0); } + ~guard_scope() { __pass::scope::leave(pass.pass, 0); } Pass & pass; + }; + + /// Internal RAII guard for forall substitutions + struct guard_forall_subs { + guard_forall_subs( Pass & pass, const ParameterizedType * type ) + : pass( pass ), type( type ) { __pass::forall::enter(pass.pass, 0, type ); } + ~guard_forall_subs() { __pass::forall::leave(pass.pass, 0, type ); } + Pass & pass; + const ParameterizedType * type; }; @@ -314,4 +330,10 @@ SymbolTable symtab; }; + +/// Use when the templated visitor needs to keep TypeInstType instances properly linked to TypeDecl +struct WithForallSubstitutor { + ForallSubstitutionTable subs; +}; + } Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Pass.impl.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -127,8 +127,7 @@ , decltype( node->accept(*this) ) >::type - { __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( expr ); + __pedantic_pass_assert( node ); static_assert( !std::is_base_of::value, "ERROR"); @@ -323,4 +322,20 @@ } + + template< typename pass_t > + template< typename node_t > + void ast::Pass< pass_t >::mutate_forall( const node_t *& node ) { + if ( auto subs = __pass::forall::subs( pass, 0 ) ) { + // tracking TypeDecl substitution, full clone + if ( node->forall.empty() ) return; + + node_t * mut = mutate( node ); + mut->forall = subs->clone( node->forall, *this ); + node = mut; + } else { + // not tracking TypeDecl substitution, just mutate + maybe_accept( node, &node_t::forall ); + } + } } @@ -429,12 +444,12 @@ guard_symtab guard { *this }; // implicit add __func__ identifier as specified in the C manual 6.4.2.2 - static ast::ObjectDecl func( - node->location, "__func__", - new ast::ArrayType( - new ast::BasicType( ast::BasicType::Char, ast::CV::Qualifiers( ast::CV::Const ) ), + static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{ + CodeLocation{}, "__func__", + new ast::ArrayType{ + new ast::BasicType{ ast::BasicType::Char, ast::CV::Const }, nullptr, VariableLen, DynamicDim - ) - ); - __pass::symtab::addId( pass, 0, &func ); + } + } }; + __pass::symtab::addId( pass, 0, func ); VISIT( maybe_accept( node, &FunctionDecl::type ); @@ -610,8 +625,8 @@ VISIT({ // do not enter a new scope if inFunction is true - needs to check old state before the assignment - auto guard1 = makeFuncGuard( [this, inFunction = this->inFunction]() { - if ( ! inFunction ) __pass::symtab::enter(pass, 0); - }, [this, inFunction = this->inFunction]() { - if ( ! inFunction ) __pass::symtab::leave(pass, 0); + auto guard1 = makeFuncGuard( [this, inFunctionCpy = this->inFunction]() { + if ( ! inFunctionCpy ) __pass::symtab::enter(pass, 0); + }, [this, inFunctionCpy = this->inFunction]() { + if ( ! inFunctionCpy ) __pass::symtab::leave(pass, 0); }); ValueGuard< bool > guard2( inFunction ); @@ -951,7 +966,7 @@ // For now this isn't visited, it is unclear if this causes problem // if all tests are known to pass, remove this code - // VISIT( - // maybe_accept( node, &ImplicitCtorDtorStmt::callStmt ); - // ) + VISIT( + maybe_accept( node, &ImplicitCtorDtorStmt::callStmt ); + ) VISIT_END( Stmt, node ); @@ -1679,9 +1694,10 @@ VISIT_START( node ); - VISIT( - maybe_accept( node, &FunctionType::forall ); + VISIT({ + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); maybe_accept( node, &FunctionType::returns ); maybe_accept( node, &FunctionType::params ); - ) + }) VISIT_END( Type, node ); @@ -1698,5 +1714,6 @@ VISIT({ guard_symtab guard { *this }; - maybe_accept( node, &StructInstType::forall ); + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); maybe_accept( node, &StructInstType::params ); }) @@ -1711,11 +1728,12 @@ VISIT_START( node ); - __pass::symtab::addStruct( pass, 0, node->name ); - - { + __pass::symtab::addUnion( pass, 0, node->name ); + + VISIT({ guard_symtab guard { *this }; - maybe_accept( node, &UnionInstType::forall ); + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); maybe_accept( node, &UnionInstType::params ); - } + }) VISIT_END( Type, node ); @@ -1728,8 +1746,9 @@ VISIT_START( node ); - VISIT( - maybe_accept( node, &EnumInstType::forall ); + VISIT({ + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); maybe_accept( node, &EnumInstType::params ); - ) + }) VISIT_END( Type, node ); @@ -1742,8 +1761,9 @@ VISIT_START( node ); - VISIT( - maybe_accept( node, &TraitInstType::forall ); + VISIT({ + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); maybe_accept( node, &TraitInstType::params ); - ) + }) VISIT_END( Type, node ); @@ -1757,6 +1777,11 @@ VISIT( - maybe_accept( node, &TypeInstType::forall ); - maybe_accept( node, &TypeInstType::params ); + { + guard_forall_subs forall_guard { *this, node }; + mutate_forall( node ); + maybe_accept( node, &TypeInstType::params ); + } + // ensure that base re-bound if doing substitution + __pass::forall::replace( pass, 0, node ); ) @@ -1907,5 +1932,5 @@ guard_symtab guard { *this }; auto new_node = p.second->accept( *this ); - if (new_node != p.second) mutated = false; + if (new_node != p.second) mutated = true; new_map.insert({ p.first, new_node }); } @@ -1923,5 +1948,5 @@ guard_symtab guard { *this }; auto new_node = p.second->accept( *this ); - if (new_node != p.second) mutated = false; + if (new_node != p.second) mutated = true; new_map.insert({ p.first, new_node }); } Index: src/AST/Pass.proto.hpp =================================================================== --- src/AST/Pass.proto.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Pass.proto.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -263,12 +263,12 @@ template static inline void leave( pass_t &, long ) {} - }; - - // Finally certain pass desire an up to date symbol table automatically + } // namespace scope + + // Certain passes desire an up to date symbol table automatically // detect the presence of a member name `symtab` and call all the members appropriately namespace symtab { // Some simple scoping rules template - static inline auto enter( pass_t & pass, int ) -> decltype( pass.symtab.enterScope(), void() ) { + static inline auto enter( pass_t & pass, int ) -> decltype( pass.symtab, void() ) { pass.symtab.enterScope(); } @@ -278,5 +278,5 @@ template - static inline auto leave( pass_t & pass, int ) -> decltype( pass.symtab.leaveScope(), void() ) { + static inline auto leave( pass_t & pass, int ) -> decltype( pass.symtab, void() ) { pass.symtab.leaveScope(); } @@ -311,5 +311,5 @@ SYMTAB_FUNC1( addUnion , const UnionDecl * ); SYMTAB_FUNC1( addTrait , const TraitDecl * ); - SYMTAB_FUNC2( addWith , const std::vector< ptr > &, const Node * ); + SYMTAB_FUNC2( addWith , const std::vector< ptr > &, const Decl * ); // A few extra functions have more complicated behaviour, they are hand written @@ -356,5 +356,49 @@ #undef SYMTAB_FUNC1 #undef SYMTAB_FUNC2 - }; -}; -}; + } // namespace symtab + + // Some passes need to mutate TypeDecl and properly update their pointing TypeInstType. + // Detect the presence of a member name `subs` and call all members appropriately + namespace forall { + // Some simple scoping rules + template + static inline auto enter( pass_t & pass, int, const ast::ParameterizedType * type ) + -> decltype( pass.subs, void() ) { + if ( ! type->forall.empty() ) pass.subs.beginScope(); + } + + template + static inline auto enter( pass_t &, long, const ast::ParameterizedType * ) {} + + template + static inline auto leave( pass_t & pass, int, const ast::ParameterizedType * type ) + -> decltype( pass.subs, void() ) { + if ( ! type->forall.empty() ) { pass.subs.endScope(); } + } + + template + static inline auto leave( pass_t &, long, const ast::ParameterizedType * ) {} + + // Get the substitution table, if present + template + static inline auto subs( pass_t & pass, int ) -> decltype( &pass.subs ) { + return &pass.subs; + } + + template + static inline ast::ForallSubstitutionTable * subs( pass_t &, long ) { return nullptr; } + + // Replaces a TypeInstType's base TypeDecl according to the table + template + static inline auto replace( pass_t & pass, int, const ast::TypeInstType *& inst ) + -> decltype( pass.subs, void() ) { + inst = ast::mutate_field( + inst, &ast::TypeInstType::base, pass.subs.replace( inst->base ) ); + } + + template + static inline auto replace( pass_t &, long, const ast::TypeInstType *& ) {} + + } // namespace forall +} // namespace __pass +} // namespace ast Index: src/AST/Stmt.hpp =================================================================== --- src/AST/Stmt.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Stmt.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -27,5 +27,7 @@ // Must be included in *all* AST classes; should be #undef'd at the end of the file -#define MUTATE_FRIEND template friend node_t * mutate(const node_t * node); +#define MUTATE_FRIEND \ + template friend node_t * mutate(const node_t * node); \ + template friend node_t * shallowCopy(const node_t * node); namespace ast { @@ -412,5 +414,5 @@ class ImplicitCtorDtorStmt final : public Stmt { public: - readonly callStmt; + ptr callStmt; ImplicitCtorDtorStmt( const CodeLocation & loc, const Stmt * callStmt, Index: src/AST/Type.cpp =================================================================== --- src/AST/Type.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Type.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -21,5 +21,7 @@ #include "Decl.hpp" +#include "ForallSubstitutor.hpp" // for substituteForall #include "Init.hpp" +#include "Common/utility.h" // for copy, move #include "InitTweak/InitTweak.h" // for getPointerBase #include "Tuples/Tuples.h" // for isTtype @@ -90,5 +92,22 @@ // GENERATED END +// --- ParameterizedType + +void ParameterizedType::initWithSub( + const ParameterizedType & o, Pass< ForallSubstitutor > & sub +) { + forall = sub.pass( o.forall ); +} + // --- FunctionType + +FunctionType::FunctionType( const FunctionType & o ) +: ParameterizedType( o.qualifiers, copy( o.attributes ) ), returns(), params(), + isVarArgs( o.isVarArgs ) { + Pass< ForallSubstitutor > sub; + initWithSub( o, sub ); // initialize substitution map + returns = sub.pass( o.returns ); // apply to return and parameter types + params = sub.pass( o.params ); +} namespace { @@ -106,4 +125,17 @@ // --- ReferenceToType + +void ReferenceToType::initWithSub( const ReferenceToType & o, Pass< ForallSubstitutor > & sub ) { + ParameterizedType::initWithSub( o, sub ); // initialize substitution + params = sub.pass( o.params ); // apply to parameters +} + +ReferenceToType::ReferenceToType( const ReferenceToType & o ) +: ParameterizedType( o.qualifiers, copy( o.attributes ) ), params(), name( o.name ), + hoistType( o.hoistType ) { + Pass< ForallSubstitutor > sub; + initWithSub( o, sub ); +} + std::vector> ReferenceToType::lookup( const std::string& name ) const { assertf( aggr(), "Must have aggregate to perform lookup" ); @@ -118,7 +150,7 @@ // --- StructInstType -StructInstType::StructInstType( const StructDecl * b, CV::Qualifiers q, - std::vector>&& as ) -: ReferenceToType( b->name, q, std::move(as) ), base( b ) {} +StructInstType::StructInstType( + const StructDecl * b, CV::Qualifiers q, std::vector>&& as ) +: ReferenceToType( b->name, q, move(as) ), base( b ) {} bool StructInstType::isComplete() const { return base ? base->body : false; } @@ -126,7 +158,7 @@ // --- UnionInstType -UnionInstType::UnionInstType( const UnionDecl * b, CV::Qualifiers q, - std::vector>&& as ) -: ReferenceToType( b->name, q, std::move(as) ), base( b ) {} +UnionInstType::UnionInstType( + const UnionDecl * b, CV::Qualifiers q, std::vector>&& as ) +: ReferenceToType( b->name, q, move(as) ), base( b ) {} bool UnionInstType::isComplete() const { return base ? base->body : false; } @@ -134,7 +166,7 @@ // --- EnumInstType -EnumInstType::EnumInstType( const EnumDecl * b, CV::Qualifiers q, - std::vector>&& as ) -: ReferenceToType( b->name, q, std::move(as) ), base( b ) {} +EnumInstType::EnumInstType( + const EnumDecl * b, CV::Qualifiers q, std::vector>&& as ) +: ReferenceToType( b->name, q, move(as) ), base( b ) {} bool EnumInstType::isComplete() const { return base ? base->body : false; } @@ -142,9 +174,16 @@ // --- TraitInstType -TraitInstType::TraitInstType( const TraitDecl * b, CV::Qualifiers q, - std::vector>&& as ) -: ReferenceToType( b->name, q, std::move(as) ), base( b ) {} +TraitInstType::TraitInstType( + const TraitDecl * b, CV::Qualifiers q, std::vector>&& as ) +: ReferenceToType( b->name, q, move(as) ), base( b ) {} // --- TypeInstType + +TypeInstType::TypeInstType( const TypeInstType & o ) +: ReferenceToType( o.name, o.qualifiers, copy( o.attributes ) ), base(), kind( o.kind ) { + Pass< ForallSubstitutor > sub; + initWithSub( o, sub ); // initialize substitution + base = sub.pass( o.base ); // apply to base type +} void TypeInstType::set_base( const TypeDecl * b ) { @@ -158,5 +197,5 @@ TupleType::TupleType( std::vector> && ts, CV::Qualifiers q ) -: Type( q ), types( std::move(ts) ), members() { +: Type( q ), types( move(ts) ), members() { // This constructor is awkward. `TupleType` needs to contain objects so that members can be // named, but members without initializer nodes end up getting constructors, which breaks Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/Type.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -29,7 +29,13 @@ // Must be included in *all* AST classes; should be #undef'd at the end of the file -#define MUTATE_FRIEND template friend node_t * mutate(const node_t * node); +#define MUTATE_FRIEND \ + template friend node_t * mutate(const node_t * node); \ + template friend node_t * shallowCopy(const node_t * node); namespace ast { + +template< typename T > class Pass; + +struct ForallSubstitutor; class Type : public Node { @@ -44,5 +50,4 @@ bool is_volatile() const { return qualifiers.is_volatile; } bool is_restrict() const { return qualifiers.is_restrict; } - bool is_lvalue() const { return qualifiers.is_lvalue; } bool is_mutex() const { return qualifiers.is_mutex; } bool is_atomic() const { return qualifiers.is_atomic; } @@ -51,5 +56,4 @@ Type * set_volatile( bool v ) { qualifiers.is_volatile = v; return this; } Type * set_restrict( bool v ) { qualifiers.is_restrict = v; return this; } - Type * set_lvalue( bool v ) { qualifiers.is_lvalue = v; return this; } Type * set_mutex( bool v ) { qualifiers.is_mutex = v; return this; } Type * set_atomic( bool v ) { qualifiers.is_atomic = v; return this; } @@ -163,5 +167,5 @@ static const char *typeNames[]; - BasicType( Kind k, CV::Qualifiers q = {}, std::vector> && as = {} ) + BasicType( Kind k, CV::Qualifiers q = {}, std::vector> && as = {} ) : Type(q, std::move(as)), kind(k) {} @@ -265,4 +269,7 @@ /// Base type for potentially forall-qualified types class ParameterizedType : public Type { +protected: + /// initializes forall with substitutor + void initWithSub( const ParameterizedType & o, Pass< ForallSubstitutor > & sub ); public: using ForallList = std::vector>; @@ -276,4 +283,11 @@ ParameterizedType( CV::Qualifiers q, std::vector> && as = {} ) : Type(q, std::move(as)), forall() {} + + // enforce use of ForallSubstitutor to copy parameterized type + ParameterizedType( const ParameterizedType & ) = delete; + + ParameterizedType( ParameterizedType && ) = default; + + // no need to change destructor, and operator= deleted in Node private: @@ -301,4 +315,6 @@ : ParameterizedType(q), returns(), params(), isVarArgs(va) {} + FunctionType( const FunctionType & o ); + /// true if either the parameters or return values contain a tttype bool isTtype() const; @@ -314,4 +330,7 @@ /// base class for types that refer to types declared elsewhere (aggregates and typedefs) class ReferenceToType : public ParameterizedType { +protected: + /// Initializes forall and parameters based on substitutor + void initWithSub( const ReferenceToType & o, Pass< ForallSubstitutor > & sub ); public: std::vector> params; @@ -319,7 +338,9 @@ bool hoistType = false; - ReferenceToType( const std::string& n, CV::Qualifiers q = {}, - std::vector> && as = {} ) + ReferenceToType( + const std::string& n, CV::Qualifiers q = {}, std::vector> && as = {} ) : ParameterizedType(q, std::move(as)), params(), name(n) {} + + ReferenceToType( const ReferenceToType & o ); /// Gets aggregate declaration this type refers to @@ -338,9 +359,10 @@ readonly base; - StructInstType( const std::string& n, CV::Qualifiers q = {}, - std::vector> && as = {} ) + StructInstType( + const std::string& n, CV::Qualifiers q = {}, std::vector> && as = {} ) : ReferenceToType( n, q, std::move(as) ), base() {} - StructInstType( const StructDecl * b, CV::Qualifiers q = {}, - std::vector> && as = {} ); + + StructInstType( + const StructDecl * b, CV::Qualifiers q = {}, std::vector> && as = {} ); bool isComplete() const override; @@ -359,9 +381,10 @@ readonly base; - UnionInstType( const std::string& n, CV::Qualifiers q = {}, - std::vector> && as = {} ) + UnionInstType( + const std::string& n, CV::Qualifiers q = {}, std::vector> && as = {} ) : ReferenceToType( n, q, std::move(as) ), base() {} - UnionInstType( const UnionDecl * b, CV::Qualifiers q = {}, - std::vector> && as = {} ); + + UnionInstType( + const UnionDecl * b, CV::Qualifiers q = {}, std::vector> && as = {} ); bool isComplete() const override; @@ -380,9 +403,10 @@ readonly base; - EnumInstType( const std::string& n, CV::Qualifiers q = {}, - std::vector> && as = {} ) + EnumInstType( + const std::string& n, CV::Qualifiers q = {}, std::vector> && as = {} ) : ReferenceToType( n, q, std::move(as) ), base() {} - EnumInstType( const EnumDecl * b, CV::Qualifiers q = {}, - std::vector> && as = {} ); + + EnumInstType( + const EnumDecl * b, CV::Qualifiers q = {}, std::vector> && as = {} ); bool isComplete() const override; @@ -401,9 +425,10 @@ readonly base; - TraitInstType( const std::string& n, CV::Qualifiers q = {}, - std::vector> && as = {} ) + TraitInstType( + const std::string& n, CV::Qualifiers q = {}, std::vector> && as = {} ) : ReferenceToType( n, q, std::move(as) ), base() {} - TraitInstType( const TraitDecl * b, CV::Qualifiers q = {}, - std::vector> && as = {} ); + + TraitInstType( + const TraitDecl * b, CV::Qualifiers q = {}, std::vector> && as = {} ); // not meaningful for TraitInstType @@ -424,5 +449,6 @@ TypeDecl::Kind kind; - TypeInstType( const std::string& n, const TypeDecl * b, CV::Qualifiers q = {}, + TypeInstType( + const std::string& n, const TypeDecl * b, CV::Qualifiers q = {}, std::vector> && as = {} ) : ReferenceToType( n, q, std::move(as) ), base( b ), kind( b->kind ) {} @@ -431,4 +457,6 @@ : ReferenceToType( n, q, std::move(as) ), base(), kind( k ) {} + TypeInstType( const TypeInstType & o ); + /// sets `base`, updating `kind` correctly void set_base( const TypeDecl * ); Index: src/AST/TypeEnvironment.hpp =================================================================== --- src/AST/TypeEnvironment.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/TypeEnvironment.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -37,20 +37,20 @@ /// Adding this comparison operator significantly improves assertion satisfaction run time for /// some cases. The current satisfaction algorithm's speed partially depends on the order of -/// assertions. Assertions which have fewer possible matches should appear before assertions -/// which have more possible matches. This seems to imply that this could be further improved -/// by providing an indexer as an additional argument and ordering based on the number of +/// assertions. Assertions which have fewer possible matches should appear before assertions +/// which have more possible matches. This seems to imply that this could be further improved +/// by providing an indexer as an additional argument and ordering based on the number of /// matches of the same kind (object, function) for the names of the declarations. /// -/// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this +/// 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 +/// 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. struct AssertCompare { @@ -86,5 +86,5 @@ void print( std::ostream &, const OpenVarSet &, Indenter indent = {} ); -/// Represents an equivalence class of bound type variables, optionally with the concrete type +/// Represents an equivalence class of bound type variables, optionally with the concrete type /// they bind to. struct EqvClass { @@ -95,7 +95,7 @@ EqvClass() : vars(), bound(), allowWidening( true ), data() {} - + /// Copy-with-bound constructor - EqvClass( const EqvClass & o, const Type * b ) + EqvClass( const EqvClass & o, const Type * b ) : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {} @@ -142,16 +142,16 @@ void writeToSubstitution( TypeSubstitution & sub ) const; - template< typename node_t, enum Node::ref_type ref_t > - int apply( ptr_base< node_t, ref_t > & type ) const { + template< typename node_t > + auto apply( node_t && type ) const { TypeSubstitution sub; writeToSubstitution( sub ); - return sub.apply( type ); - } - - template< typename node_t, enum Node::ref_type ref_t > - int applyFree( ptr_base< node_t, ref_t > & type ) const { + return sub.apply( std::forward(type) ); + } + + template< typename node_t > + auto applyFree( node_t && type ) const { TypeSubstitution sub; writeToSubstitution( sub ); - return sub.applyFree( type ); + return sub.applyFree( std::forward(type) ); } @@ -172,16 +172,16 @@ void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars ); - /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if + /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if /// needed. Returns false on failure. - bool bindVar( - const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, - AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + bool bindVar( + const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, ResolvExpr::WidenMode widen, const SymbolTable & symtab ); - - /// Binds the type classes represented by `var1` and `var2` together; will add one or both + + /// Binds the type classes represented by `var1` and `var2` together; will add one or both /// classes if needed. Returns false on failure. - bool bindVarToVar( - const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, - AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + bool bindVarToVar( + const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, ResolvExpr::WidenMode widen, const SymbolTable & symtab ); @@ -198,10 +198,10 @@ /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails - bool mergeBound( + bool mergeBound( EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab ); /// Merges two type classes from local environment, returning false if fails - bool mergeClasses( - ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, + bool mergeClasses( + ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, const SymbolTable & symtab ); Index: src/AST/TypeSubstitution.cpp =================================================================== --- src/AST/TypeSubstitution.cpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/TypeSubstitution.cpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -92,5 +92,5 @@ namespace { struct EnvTrimmer { - ptr env; + const TypeSubstitution * env; TypeSubstitution * newEnv; EnvTrimmer( const TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){} @@ -108,11 +108,6 @@ if ( env ) { TypeSubstitution * newEnv = new TypeSubstitution(); -#if TIME_TO_CONVERT_PASSES Pass trimmer( env, newEnv ); expr->accept( trimmer ); -#else - (void)expr; - (void)env; -#endif return newEnv; } @@ -121,19 +116,15 @@ void TypeSubstitution::normalize() { -#if TIME_TO_CONVERT_PASSES - PassVisitor sub( *this, true ); + Pass sub( *this, true ); do { sub.pass.subCount = 0; sub.pass.freeOnly = true; for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) { - i->second = i->second->acceptMutator( sub ); + i->second = i->second->accept( sub ); } } while ( sub.pass.subCount ); -#endif -} - -#if TIME_TO_CONVERT_PASSES - -Type * TypeSubstitution::Substituter::postmutate( TypeInstType *inst ) { +} + +const Type * TypeSubstitution::Substituter::postvisit( const TypeInstType *inst ) { BoundVarsType::const_iterator bound = boundVars.find( inst->name ); if ( bound != boundVars.end() ) return inst; @@ -146,5 +137,5 @@ // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here. // TODO: investigate preventing type variables from being bound to themselves in the first place. - if ( TypeInstType * replacement = i->second.as() ) { + if ( const TypeInstType * replacement = i->second.as() ) { if ( inst->name == replacement->name ) { return inst; @@ -153,13 +144,14 @@ // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl; subCount++; - Type * newtype = i->second->clone(); - newtype->get_qualifiers() |= inst->get_qualifiers(); - delete inst; - // Note: need to recursively apply substitution to the new type because normalize does not substitute bound vars, but bound vars must be substituted when not in freeOnly mode. - return newtype->acceptMutator( *visitor ); - } // if -} - -Expression * TypeSubstitution::Substituter::postmutate( NameExpr * nameExpr ) { + ptr newType = i->second; // force clone if needed + add_qualifiers( newType, inst->qualifiers ); + // Note: need to recursively apply substitution to the new type because normalize does not + // substitute bound vars, but bound vars must be substituted when not in freeOnly mode. + newType = newType->accept( *visitor ); + return newType.release(); + } // if +} + +const Expr * TypeSubstitution::Substituter::postvisit( const NameExpr * nameExpr ) { VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name ); if ( i == sub.varEnv.end() ) { @@ -167,46 +159,43 @@ } else { subCount++; - delete nameExpr; - return i->second->clone(); - } // if -} - -void TypeSubstitution::Substituter::premutate( Type * type ) { + return i->second; + } // if +} + +void TypeSubstitution::Substituter::previsit( const ParameterizedType * ptype ) { GuardValue( boundVars ); // bind type variables from forall-qualifiers if ( freeOnly ) { - for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { - boundVars.insert( (*tyvar)->name ); + for ( const TypeDecl * tyvar : ptype->forall ) { + boundVars.insert( tyvar->name ); } // for } // if } -template< typename TypeClass > -void TypeSubstitution::Substituter::handleAggregateType( TypeClass * type ) { +void TypeSubstitution::Substituter::handleAggregateType( const ReferenceToType * type ) { GuardValue( boundVars ); // bind type variables from forall-qualifiers if ( freeOnly ) { - for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { - boundVars.insert( (*tyvar)->name ); + for ( const TypeDecl * tyvar : type->forall ) { + boundVars.insert( tyvar->name ); } // for // bind type variables from generic type instantiations - std::list< TypeDecl* > *baseParameters = type->get_baseParameters(); - if ( baseParameters && ! type->parameters.empty() ) { - for ( std::list< TypeDecl* >::const_iterator tyvar = baseParameters->begin(); tyvar != baseParameters->end(); ++tyvar ) { - boundVars.insert( (*tyvar)->name ); - } // for - } // if - } // if -} - -void TypeSubstitution::Substituter::premutate( StructInstType * aggregateUseType ) { + if ( auto decl = type->aggr() ) { + if ( ! type->params.empty() ) { + for ( const TypeDecl * tyvar : decl->params ) { + boundVars.insert( tyvar->name ); + } // for + } // if + } + } // if +} + +void TypeSubstitution::Substituter::previsit( const StructInstType * aggregateUseType ) { handleAggregateType( aggregateUseType ); } -void TypeSubstitution::Substituter::premutate( UnionInstType *aggregateUseType ) { +void TypeSubstitution::Substituter::previsit( const UnionInstType *aggregateUseType ) { handleAggregateType( aggregateUseType ); } - -#endif } // namespace ast Index: src/AST/TypeSubstitution.hpp =================================================================== --- src/AST/TypeSubstitution.hpp (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/TypeSubstitution.hpp (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -44,13 +44,19 @@ TypeSubstitution &operator=( const TypeSubstitution &other ); - template< typename SynTreeClass > int apply( const SynTreeClass *& input ) const; - template< typename SynTreeClass > int applyFree( const SynTreeClass *& input ) const; + template< typename SynTreeClass > + struct ApplyResult { + const SynTreeClass * node; + int count; + }; + + template< typename SynTreeClass > ApplyResult apply( const SynTreeClass * input ) const; + template< typename SynTreeClass > ApplyResult applyFree( const SynTreeClass * input ) const; template< typename node_t, enum Node::ref_type ref_t > int apply( ptr_base< node_t, ref_t > & input ) const { const node_t * p = input.get(); - int ret = apply(p); - input = p; - return ret; + auto ret = apply(p); + input = ret.node; + return ret.count; } @@ -58,7 +64,7 @@ int applyFree( ptr_base< node_t, ref_t > & input ) const { const node_t * p = input.get(); - int ret = applyFree(p); - input = p; - return ret; + auto ret = applyFree(p); + input = ret.node; + return ret.count; } @@ -155,18 +161,14 @@ Substituter( const TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {} -#if TIME_TO_CONVERT_PASSES - - Type * postmutate( TypeInstType * aggregateUseType ); - Expression * postmutate( NameExpr * nameExpr ); + const Type * postvisit( const TypeInstType * aggregateUseType ); + const Expr * postvisit( const NameExpr * nameExpr ); /// Records type variable bindings from forall-statements - void premutate( Type * type ); + void previsit( const ParameterizedType * type ); /// Records type variable bindings from forall-statements and instantiations of generic types - template< typename TypeClass > void handleAggregateType( TypeClass * type ); - - void premutate( StructInstType * aggregateUseType ); - void premutate( UnionInstType * aggregateUseType ); - -#endif + void handleAggregateType( const ReferenceToType * type ); + + void previsit( const StructInstType * aggregateUseType ); + void previsit( const UnionInstType * aggregateUseType ); const TypeSubstitution & sub; @@ -179,23 +181,17 @@ template< typename SynTreeClass > -int TypeSubstitution::apply( const SynTreeClass *& input ) const { +TypeSubstitution::ApplyResult TypeSubstitution::apply( const SynTreeClass * input ) const { assert( input ); Pass sub( *this, false ); input = strict_dynamic_cast< const SynTreeClass * >( input->accept( sub ) ); -/// std::cerr << "substitution result is: "; -/// newType->print( std::cerr ); -/// std::cerr << std::endl; - return sub.pass.subCount; + return { input, sub.pass.subCount }; } template< typename SynTreeClass > -int TypeSubstitution::applyFree( const SynTreeClass *& input ) const { +TypeSubstitution::ApplyResult TypeSubstitution::applyFree( const SynTreeClass * input ) const { assert( input ); Pass sub( *this, true ); input = strict_dynamic_cast< const SynTreeClass * >( input->accept( sub ) ); -/// std::cerr << "substitution result is: "; -/// newType->print( std::cerr ); -/// std::cerr << std::endl; - return sub.pass.subCount; + return { input, sub.pass.subCount }; } Index: src/AST/module.mk =================================================================== --- src/AST/module.mk (revision 427854baeaba2d97cb23623b6d3c3ad7f7b0dbdd) +++ src/AST/module.mk (revision 7030dab75c493bbd89de53cb88e496019c794ff4) @@ -22,4 +22,5 @@ AST/DeclReplacer.cpp \ AST/Expr.cpp \ + AST/ForallSubstitutionTable.cpp \ AST/GenericSubstitution.cpp \ AST/Init.cpp \