Index: src/AST/AssertAcyclic.cpp =================================================================== --- src/AST/AssertAcyclic.cpp (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ (revision ) @@ -1,53 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// AssertAcyclic.cpp -- Check that ast::ptr does not form a cycle. -// -// Author : Andrew Beach -// Created On : Thu Jun 06 15:00:00 2019 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jun 07 14:32:00 2019 -// Update Count : 1 -// - -#include "AssertAcyclic.hpp" - -#include "AST/Pass.hpp" - -namespace { - -class NoStrongCyclesCore { - std::vector parents; -public: - void previsit( const ast::Node * node ) { - for (auto & parent : parents) { - assert(parent != node); - } - parents.push_back(node); - } - void postvisit( const ast::Node * ) { - parents.pop_back(); - } -}; - -} - -namespace ast { - -void assertAcyclic( const std::list< ast::ptr< ast::Decl > > & translationUnit ) { - Pass visitor; - for ( auto & decl : translationUnit ) { - decl->accept( visitor ); - } -} - -} - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/AST/AssertAcyclic.hpp =================================================================== --- src/AST/AssertAcyclic.hpp (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ (revision ) @@ -1,35 +1,0 @@ -// -// 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. -// -// AssertAcyclic.hpp -- Check that ast::ptr does not form a cycle. -// -// Author : Andrew Beach -// Created On : Thr Jun 6 15:00:00 2019 -// Last Modified By : Andrew Beach -// Last Modified On : Fri Jun 7 14:32:00 2019 -// Update Count : 1 -// - -#pragma once - -#include - -#include "Node.hpp" -namespace ast { - class Decl; -}; - -namespace ast { - -void assertAcyclic( const std::list< ast::ptr< ast::Decl > > & translationUnit ); - -} - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/AST/Decl.cpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -39,8 +39,11 @@ if ( uniqueId ) return; // ensure only set once uniqueId = ++lastUniqueId; - idMap[ uniqueId ] = this; + // The extra readonly pointer is causing some reference counting issues. + // idMap[ uniqueId ] = this; } readonly Decl::fromId( UniqueId id ) { + // Right now this map is always empty, so don't use it. + assert( false ); IdMapType::const_iterator i = idMap.find( id ); if ( i != idMap.end() ) return i->second; Index: src/AST/Util.cpp =================================================================== --- src/AST/Util.cpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) +++ src/AST/Util.cpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -0,0 +1,68 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Util.hpp -- General utilities for working with the AST. +// +// Author : Andrew Beach +// Created On : Wed Jan 19 9:46:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Feb 18 9:42:00 2022 +// Update Count : 0 +// + +#include "Util.hpp" + +#include "Decl.hpp" +#include "Node.hpp" +#include "Pass.hpp" +#include "TranslationUnit.hpp" +#include "Common/ScopedMap.h" + +#include + +namespace ast { + +namespace { + +/// Check that ast::ptr/strong references do not form a cycle. +struct NoStrongCyclesCore { + std::vector parents; + + void previsit( const Node * node ) { + for ( auto & parent : parents ) { + assert( parent != node ); + } + parents.push_back( node ); + } + + void postvisit( const Node * node ) { + assert( !parents.empty() ); + assert( parents.back() == node ); + parents.pop_back(); + } +}; + +struct InvariantCore { + // To save on the number of visits: this is a kind of composed core. + // None of the passes should make changes so ordering doesn't matter. + NoStrongCyclesCore no_strong_cycles; + + void previsit( const Node * node ) { + no_strong_cycles.previsit( node ); + } + + void postvisit( const Node * node ) { + no_strong_cycles.postvisit( node ); + } +}; + +} // namespace + +void checkInvariants( TranslationUnit & transUnit ) { + ast::Pass::run( transUnit ); +} + +} // namespace ast Index: src/AST/Util.hpp =================================================================== --- src/AST/Util.hpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) +++ src/AST/Util.hpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -0,0 +1,26 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Util.hpp -- General utilities for working with the AST. +// +// Author : Andrew Beach +// Created On : Wed Jan 19 9:37:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Feb 18 9:43:00 2022 +// Update Count : 0 +// + +#pragma once + +namespace ast { + +class TranslationUnit; + +/// Check anything that should always be true of the AST between passes. +/// Insert this whenever you want additional debugging checks. +void checkInvariants( TranslationUnit & transUnit ); + +} Index: src/AST/module.mk =================================================================== --- src/AST/module.mk (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/AST/module.mk (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -16,6 +16,4 @@ SRC_AST = \ - AST/AssertAcyclic.cpp \ - AST/AssertAcyclic.hpp \ AST/Attribute.cpp \ AST/Attribute.hpp \ @@ -64,4 +62,6 @@ AST/TypeSubstitution.cpp \ AST/TypeSubstitution.hpp \ + AST/Util.cpp \ + AST/Util.hpp \ AST/Visitor.hpp Index: src/SymTab/Validate.cc =================================================================== --- src/SymTab/Validate.cc (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/SymTab/Validate.cc (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -194,4 +194,26 @@ }; + // These structs are the sub-sub-passes of ForallPointerDecay_old. + + struct TraitExpander_old final { + void previsit( FunctionType * ); + void previsit( StructDecl * ); + void previsit( UnionDecl * ); + }; + + struct AssertionFixer_old final { + void previsit( FunctionType * ); + void previsit( StructDecl * ); + void previsit( UnionDecl * ); + }; + + struct CheckOperatorTypes_old final { + void previsit( ObjectDecl * ); + }; + + struct FixUniqueIds_old final { + void previsit( DeclarationWithType * ); + }; + struct ReturnChecker : public WithGuards { /// Checks that return statements return nothing if their return type is void @@ -386,5 +408,4 @@ void validate_D( std::list< Declaration * > & translationUnit ) { - PassVisitor fpd; { Stats::Heap::newPass("validate-D"); @@ -394,5 +415,5 @@ }); Stats::Time::TimeBlock("Forall Pointer Decay", [&]() { - acceptAll( translationUnit, fpd ); // must happen before autogenerateRoutines, after Concurrency::applyKeywords because uniqueIds must be set on declaration before resolution + decayForallPointers( translationUnit ); // must happen before autogenerateRoutines, after Concurrency::applyKeywords because uniqueIds must be set on declaration before resolution }); Stats::Time::TimeBlock("Hoist Control Declarations", [&]() { @@ -454,6 +475,29 @@ void decayForallPointers( std::list< Declaration * > & translationUnit ) { - PassVisitor fpd; - acceptAll( translationUnit, fpd ); + PassVisitor te; + acceptAll( translationUnit, te ); + PassVisitor af; + acceptAll( translationUnit, af ); + PassVisitor cot; + acceptAll( translationUnit, cot ); + PassVisitor fui; + acceptAll( translationUnit, fui ); + } + + void decayForallPointersA( std::list< Declaration * > & translationUnit ) { + PassVisitor te; + acceptAll( translationUnit, te ); + } + void decayForallPointersB( std::list< Declaration * > & translationUnit ) { + PassVisitor af; + acceptAll( translationUnit, af ); + } + void decayForallPointersC( std::list< Declaration * > & translationUnit ) { + PassVisitor cot; + acceptAll( translationUnit, cot ); + } + void decayForallPointersD( std::list< Declaration * > & translationUnit ) { + PassVisitor fui; + acceptAll( translationUnit, fui ); } @@ -470,8 +514,14 @@ PassVisitor epc; PassVisitor lrt( indexer ); - PassVisitor fpd; + PassVisitor te; + PassVisitor af; + PassVisitor cot; + PassVisitor fui; type->accept( epc ); type->accept( lrt ); - type->accept( fpd ); + type->accept( te ); + type->accept( af ); + type->accept( cot ); + type->accept( fui ); } @@ -972,4 +1022,36 @@ } + /// Replace all traits in assertion lists with their assertions. + void expandTraits( std::list< TypeDecl * > & forall ) { + for ( TypeDecl * type : forall ) { + std::list< DeclarationWithType * > asserts; + asserts.splice( asserts.end(), type->assertions ); + // expand trait instances into their members + for ( DeclarationWithType * assertion : asserts ) { + if ( TraitInstType * traitInst = dynamic_cast< TraitInstType * >( assertion->get_type() ) ) { + // expand trait instance into all of its members + expandAssertions( traitInst, back_inserter( type->assertions ) ); + delete traitInst; + } else { + // pass other assertions through + type->assertions.push_back( assertion ); + } // if + } // for + } + } + + /// Fix each function in the assertion list and check for invalid void type. + void fixAssertions( + std::list< TypeDecl * > & forall, BaseSyntaxNode * node ) { + for ( TypeDecl * type : forall ) { + for ( DeclarationWithType *& assertion : type->assertions ) { + bool isVoid = fixFunction( assertion ); + if ( isVoid ) { + SemanticError( node, "invalid type void in assertion of function " ); + } // if + } // for + } + } + void ForallPointerDecay_old::previsit( ObjectDecl * object ) { // ensure that operator names only apply to functions or function pointers @@ -994,4 +1076,39 @@ void ForallPointerDecay_old::previsit( UnionDecl * aggrDecl ) { forallFixer( aggrDecl->parameters, aggrDecl ); + } + + void TraitExpander_old::previsit( FunctionType * ftype ) { + expandTraits( ftype->forall ); + } + + void TraitExpander_old::previsit( StructDecl * aggrDecl ) { + expandTraits( aggrDecl->parameters ); + } + + void TraitExpander_old::previsit( UnionDecl * aggrDecl ) { + expandTraits( aggrDecl->parameters ); + } + + void AssertionFixer_old::previsit( FunctionType * ftype ) { + fixAssertions( ftype->forall, ftype ); + } + + void AssertionFixer_old::previsit( StructDecl * aggrDecl ) { + fixAssertions( aggrDecl->parameters, aggrDecl ); + } + + void AssertionFixer_old::previsit( UnionDecl * aggrDecl ) { + fixAssertions( aggrDecl->parameters, aggrDecl ); + } + + void CheckOperatorTypes_old::previsit( ObjectDecl * object ) { + // ensure that operator names only apply to functions or function pointers + if ( CodeGen::isOperator( object->name ) && ! dynamic_cast< FunctionType * >( object->type->stripDeclarator() ) ) { + SemanticError( object->location, toCString( "operator ", object->name.c_str(), " is not a function or function pointer." ) ); + } + } + + void FixUniqueIds_old::previsit( DeclarationWithType * decl ) { + decl->fixUniqueId(); } Index: src/SymTab/Validate.h =================================================================== --- src/SymTab/Validate.h (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/SymTab/Validate.h (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -43,4 +43,8 @@ void validate_F( std::list< Declaration * > &translationUnit ); void decayForallPointers( std::list< Declaration * > & translationUnit ); + void decayForallPointersA( std::list< Declaration * > & translationUnit ); + void decayForallPointersB( std::list< Declaration * > & translationUnit ); + void decayForallPointersC( std::list< Declaration * > & translationUnit ); + void decayForallPointersD( std::list< Declaration * > & translationUnit ); const ast::Type * validateType( Index: src/Validate/ForallPointerDecay.cpp =================================================================== --- src/Validate/ForallPointerDecay.cpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) +++ src/Validate/ForallPointerDecay.cpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -0,0 +1,249 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ForallPointerDecay.cpp -- +// +// Author : Andrew Beach +// Created On : Tue Dec 7 16:15:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Feb 11 10:59:00 2022 +// Update Count : 0 +// + +#include "ForallPointerDecay.hpp" + +#include "AST/Copy.hpp" +#include "AST/Decl.hpp" +#include "AST/DeclReplacer.hpp" +#include "AST/Pass.hpp" +#include "CodeGen/OperatorTable.h" +#include "Common/CodeLocation.h" +#include "SymTab/FixFunction.h" + +#include "AST/Print.hpp" + +namespace Validate { + +namespace { + +// Create a function type only using information on the FunctionDecl. +ast::FunctionType * makeFuncType( const ast::FunctionDecl * decl ) { + auto type = new ast::FunctionType( decl->type->isVarArgs ); + for ( auto & param : decl->params ) { + type->params.emplace_back( param->get_type() ); + } + for ( auto & ret : decl->returns ) { + type->returns.emplace_back( ret->get_type() ); + } + for ( auto & type_param : decl->type_params ) { + type->forall.emplace_back( + new ast::TypeInstType( type_param->name, type_param ) ); + } + for ( auto & assertion : decl->assertions ) { + type->assertions.emplace_back( new ast::VariableExpr( + assertion->location, assertion ) ); + } + return type; +} + +template +void append( std::vector & dst, std::vector & src ) { + dst.reserve( dst.size() + src.size() ); + for ( auto el : src ) { + dst.emplace_back( std::move( el ) ); + } + src.clear(); +} + +// Component Passes: +/// Expand assertions from a trait instance, +/// performing appropriate type variable substitutions. +struct TraitExpander final { + using AssertionList = std::vector>; + + static AssertionList expandTrait( const ast::TraitInstType * inst ) { + assertf( inst->base, "Trait instance not linked to base trait: %s", + toCString( inst ) ); + AssertionList assertions; + // Substitute trait decl parameters for instance parameters. + ast::TypeSubstitution sub( + inst->base->params.begin(), + inst->base->params.end(), + inst->params.begin() + ); + for ( const ast::ptr & decl : inst->base->members ) { + ast::ptr copy = + ast::deepCopy( decl.strict_as() ); + + int count = sub.apply( copy ); + (void)count; + + // Update the type (type substution does not seem to cover it). + if ( auto func = copy.as() ) { + auto mut = ast::mutate( func ); + mut->type = makeFuncType( func ); + copy = mut; + } + assertions.push_back( copy ); + } + return assertions; + } + + static AssertionList expandAssertions( const AssertionList & old ) { + AssertionList assertions; + for ( const ast::ptr & decl : old ) { + if ( auto traitInst = dynamic_cast( + decl->get_type() ) ) { + auto moreAsserts = expandTrait( traitInst ); + append( assertions, moreAsserts ); + } else { + assertions.push_back( decl ); + } + } + return assertions; + } + + using TypeDeclVec = std::vector>; + + static TypeDeclVec expandTypeDecls( const TypeDeclVec & old ) { + TypeDeclVec typeDecls; + for ( const ast::TypeDecl * typeDecl : old ) { + typeDecls.push_back( ast::mutate_field( typeDecl, + &ast::TypeDecl::assertions, + expandAssertions( typeDecl->assertions ) ) ); + } + return typeDecls; + } + + const ast::FunctionDecl * postvisit( const ast::FunctionDecl * decl ) { + if ( decl->assertions.empty() ) { + return decl; + } + auto mut = ast::mutate( decl ); + mut->assertions = expandAssertions( decl->assertions ); + // Update the assertion list on the type as well. + auto mutType = ast::mutate( mut->type.get() ); + mutType->assertions.clear(); + for ( auto & assertion : mut->assertions ) { + mutType->assertions.emplace_back( + new ast::VariableExpr( mut->location, assertion ) ); + } + mut->type = mutType; + return mut; + } + + const ast::StructDecl * previsit( const ast::StructDecl * decl ) { + if ( decl->params.empty() ) { + return decl; + } + return ast::mutate_field( decl, &ast::StructDecl::params, + expandTypeDecls( decl->params ) ); + } + + const ast::UnionDecl * previsit( const ast::UnionDecl * decl ) { + if ( decl->params.empty() ) { + return decl; + } + return ast::mutate_field( decl, &ast::UnionDecl::params, + expandTypeDecls( decl->params ) ); + } +}; + +std::vector> fixAssertionList( + const ast::ParseNode * node, + const std::vector> & assertions ) { + std::vector> ret; + for ( const auto & assn : assertions ) { + bool isVoid = false; + ret.push_back( SymTab::fixFunction( assn, isVoid ) ); + if ( isVoid ) { + SemanticError( node->location, node, + "invalid type void in assertion of function " ); + } + } + return ret; +} + +std::vector> fixTypeDeclList( + const ast::ParseNode * node, + const std::vector> & type_params ) { + std::vector> ret; + ret.reserve( type_params.size() ); + for ( const ast::TypeDecl * type_param : type_params ) { + auto mutParam = ast::mutate( type_param ); + mutParam->assertions = fixAssertionList( node, mutParam->assertions ); + ret.push_back( mutParam ); + } + return ret; +} + +struct AssertionFunctionFixer final { + const ast::FunctionDecl * previsit( const ast::FunctionDecl * decl ) { + if ( decl->assertions.empty() ) { + return decl; + } + return ast::mutate_field( decl, &ast::FunctionDecl::assertions, + fixAssertionList( decl, decl->assertions ) ); + } + + const ast::StructDecl * previsit( const ast::StructDecl * decl ) { + if ( decl->params.empty() ) { + return decl; + } + return ast::mutate_field( decl, &ast::StructDecl::params, + fixTypeDeclList( decl, decl->params ) ); + } + + const ast::UnionDecl * previsit( const ast::UnionDecl * decl ) { + if ( decl->params.empty() ) { + return decl; + } + return ast::mutate_field( decl, &ast::UnionDecl::params, + fixTypeDeclList( decl, decl->params ) ); + } +}; + +struct OberatorChecker final { + void previsit( const ast::ObjectDecl * obj ) { + if ( CodeGen::isOperator( obj->name ) ) { + auto type = obj->type->stripDeclarator(); + if ( ! dynamic_cast< const ast::FunctionType * >( type ) ) { + SemanticError( obj->location, + toCString( "operator ", obj->name.c_str(), " is not " + "a function or function pointer." ) ); + } + } + } +}; + +struct UniqueFixCore final { + const ast::DeclWithType * postvisit( const ast::DeclWithType * decl ) { + if ( decl->uniqueId ) { + return decl; + } else { + auto mut = ast::mutate( decl ); + mut->fixUniqueId(); + return mut; + } + } +}; + +} // namespace + +void decayForallPointers( ast::TranslationUnit & transUnit ) { + ast::Pass::run( transUnit ); + ast::Pass::run( transUnit ); + ast::Pass::run( transUnit ); + ast::Pass::run( transUnit ); +} + +} // namespace Validate + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/ForallPointerDecay.hpp =================================================================== --- src/Validate/ForallPointerDecay.hpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) +++ src/Validate/ForallPointerDecay.hpp (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -0,0 +1,35 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// ForallPointerDecay.hpp -- +// +// Author : Andrew Beach +// Created On : Tue Dec 7 16:15:00 2021 +// Last Modified By : Andrew Beach +// Last Modified On : Tue Dec 8 11:50:00 2021 +// Update Count : 0 +// + +#pragma once + +namespace ast { + class TranslationUnit; +} + +namespace Validate { + +/// Cleans up assertion lists and expands traits. +/// Also checks that operator names are used properly on functions and +/// assigns unique IDs. This is a "legacy" pass. +void decayForallPointers( ast::TranslationUnit & transUnit ); + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Validate/module.mk =================================================================== --- src/Validate/module.mk (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/Validate/module.mk (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -20,4 +20,6 @@ Validate/CompoundLiteral.cpp \ Validate/CompoundLiteral.hpp \ + Validate/ForallPointerDecay.cpp \ + Validate/ForallPointerDecay.hpp \ Validate/HandleAttributes.cc \ Validate/HandleAttributes.h \ Index: src/main.cc =================================================================== --- src/main.cc (revision 5c216b490ffeaa226de500947c2f66ed24b57734) +++ src/main.cc (revision 3a038faa55ea80fb01696622b7506738a82ebec1) @@ -32,4 +32,5 @@ #include "AST/Convert.hpp" +#include "AST/Print.hpp" #include "CompilationState.h" #include "../config.h" // for CFA_LIBDIR @@ -76,4 +77,5 @@ #include "Validate/Autogen.hpp" // for autogenerateRoutines #include "Validate/FindSpecialDecls.h" // for findGlobalDecls +#include "Validate/ForallPointerDecay.hpp" // for decayForallPointers #include "Validate/CompoundLiteral.hpp" // for handleCompoundLiterals #include "Validate/InitializerLength.hpp" // for setLengthFromInitializer @@ -331,6 +333,9 @@ if( useNewAST ) { - PASS( "Apply Concurrent Keywords", Concurrency::applyKeywords( translationUnit ) ); - PASS( "Forall Pointer Decay", SymTab::decayForallPointers( translationUnit ) ); + PASS( "Implement Concurrent Keywords", Concurrency::applyKeywords( translationUnit ) ); + //PASS( "Forall Pointer Decay - A", SymTab::decayForallPointersA( translationUnit ) ); + //PASS( "Forall Pointer Decay - B", SymTab::decayForallPointersB( translationUnit ) ); + //PASS( "Forall Pointer Decay - C", SymTab::decayForallPointersC( translationUnit ) ); + //PASS( "Forall Pointer Decay - D", SymTab::decayForallPointersD( translationUnit ) ); CodeTools::fillLocations( translationUnit ); @@ -342,4 +347,9 @@ forceFillCodeLocations( transUnit ); + + // Must be after implement concurrent keywords; because uniqueIds + // must be set on declaration before resolution. + // Must happen before autogen routines are added. + PASS( "Forall Pointer Decay", Validate::decayForallPointers( transUnit ) ); // Must happen before autogen routines are added.