Index: src/Parser/TypedefTable.cc =================================================================== --- src/Parser/TypedefTable.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/Parser/TypedefTable.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:20:13 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 13:17:56 2018 -// Update Count : 192 +// Last Modified On : Fri Jun 22 06:14:39 2018 +// Update Count : 206 // @@ -78,11 +78,12 @@ debugPrint( cerr << "Adding current at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl ); auto ret = kindTable.insertAt( scope, identifier, kind ); - if ( ! ret.second ) ret.first->second = kind; // exists => update + //if ( ! ret.second ) ret.first->second = kind; // exists => update + assert( ret.first->second == kind ); // exists } // TypedefTable::addToScope void TypedefTable::addToEnclosingScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) { - assert( kindTable.currentScope() >= 1 ); - auto scope = kindTable.currentScope() - 1; - debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl ); + assert( kindTable.currentScope() >= 1 + level ); + auto scope = kindTable.currentScope() - 1 - level; + debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << " level " << level << endl ); auto ret = kindTable.insertAt( scope, identifier, kind ); if ( ! ret.second ) ret.first->second = kind; // exists => update @@ -91,11 +92,9 @@ void TypedefTable::enterScope() { kindTable.beginScope(); - debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl ); - debugPrint( print() ); + debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl; print() ); } // TypedefTable::enterScope void TypedefTable::leaveScope() { - debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl ); - debugPrint( print() ); + debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl; print() ); kindTable.endScope(); } // TypedefTable::leaveScope @@ -114,7 +113,7 @@ --scope; debugPrint( cerr << endl << "[" << scope << "]" ); - } + } // while debugPrint( cerr << endl ); -} +} // TypedefTable::print // Local Variables: // Index: src/Parser/TypedefTable.h =================================================================== --- src/Parser/TypedefTable.h (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/Parser/TypedefTable.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:24:36 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 12:10:17 2018 -// Update Count : 85 +// Last Modified On : Fri Jun 22 05:29:58 2018 +// Update Count : 86 // @@ -25,4 +25,5 @@ typedef ScopedMap< std::string, int > KindTable; KindTable kindTable; + unsigned int level = 0; public: ~TypedefTable(); @@ -37,4 +38,7 @@ void leaveScope(); + void up() { level += 1; } + void down() { level -= 1; } + void print( void ) const; }; // TypedefTable Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/Parser/lex.ll (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Thu Jun 7 08:27:40 2018 - * Update Count : 679 + * Last Modified On : Wed Jun 20 09:08:28 2018 + * Update Count : 682 */ @@ -25,6 +25,13 @@ //**************************** Includes and Defines **************************** +// trigger before each matching rule's action +#define YY_USER_ACTION \ + yylloc.first_line = yylineno; \ + yylloc.first_column = column; \ + column += yyleng; \ + yylloc.last_column = column; \ + yylloc.last_line = yylineno; \ + yylloc.filename = yyfilename ? yyfilename : ""; unsigned int column = 0; // position of the end of the last token parsed -#define YY_USER_ACTION yylloc.first_line = yylineno; yylloc.first_column = column; column += yyleng; yylloc.last_column = column; yylloc.last_line = yylineno; yylloc.filename = yyfilename ? yyfilename : ""; // trigger before each matching rule's action #include @@ -49,5 +56,5 @@ #define NUMERIC_RETURN(x) rm_underscore(); RETURN_VAL( x ) // numeric constant #define KEYWORD_RETURN(x) RETURN_CHAR( x ) // keyword -#define QKEYWORD_RETURN(x) typedefTable.isKind( yytext ); RETURN_VAL(x); // quasi-keyword +#define QKEYWORD_RETURN(x) RETURN_VAL(x); // quasi-keyword #define IDENTIFIER_RETURN() RETURN_VAL( typedefTable.isKind( yytext ) ) #define ATTRIBUTE_RETURN() RETURN_VAL( ATTR_IDENTIFIER ) Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/Parser/parser.yy (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 10:07:12 2018 -// Update Count : 3527 +// Last Modified On : Sun Jun 24 10:41:10 2018 +// Update Count : 3587 // @@ -136,5 +136,5 @@ } // build_postfix_name -bool forall = false, xxx = false; // aggregate have one or more forall qualifiers ? +bool forall = false, xxx = false, yyy = false; // aggregate have one or more forall qualifiers ? // https://www.gnu.org/software/bison/manual/bison.html#Location-Type @@ -304,5 +304,7 @@ %type enumerator_value_opt -%type exception_declaration external_definition external_definition_list external_definition_list_no_pop_push external_definition_list_opt +%type external_definition external_definition_list external_definition_list_opt + +%type exception_declaration %type field_declaration field_declaration_list_opt field_declarator_opt field_declaring_list @@ -503,9 +505,7 @@ { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $5 ) ), $2 ) ); } | type_name '.' no_attr_identifier // CFA, nested type - // { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; } - { $$ = nullptr; } + { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; } | type_name '.' '[' field_list ']' // CFA, nested type / tuple field selector - // { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; } - { $$ = nullptr; } + { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; } | GENERIC '(' assignment_expression ',' generic_assoc_list ')' // C11 { @@ -1821,23 +1821,26 @@ ; +fred: + // empty + { yyy = false; } + ; + aggregate_type: // struct, union aggregate_key attribute_list_opt '{' field_declaration_list_opt '}' { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), nullptr, $4, true )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt no_attr_identifier + | aggregate_key attribute_list_opt no_attr_identifier fred { typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); // create typedef - //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update forall = false; // reset } '{' field_declaration_list_opt '}' - { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $6, true )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt type_name + { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $7, true )->addQualifiers( $2 ); } + | aggregate_key attribute_list_opt type_name fred { typedefTable.makeTypedef( *$3->type->symbolic.name, forall ? TYPEGENname : TYPEDEFname ); // create typedef - //if ( forall ) typedefTable.changeKind( *$3->type->symbolic.name, TYPEGENname ); // possibly update forall = false; // reset } '{' field_declaration_list_opt '}' - { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $6, true )->addQualifiers( $2 ); } + { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $7, true )->addQualifiers( $2 ); } | aggregate_key attribute_list_opt '(' type_list ')' '{' field_declaration_list_opt '}' // CFA { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), $4, $7, false )->addQualifiers( $2 ); } @@ -1846,12 +1849,11 @@ aggregate_type_nobody: // struct, union - {...} - aggregate_key attribute_list_opt no_attr_identifier + aggregate_key attribute_list_opt no_attr_identifier fred { typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); - //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update forall = false; // reset $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt type_name + | aggregate_key attribute_list_opt type_name fred { // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is @@ -1867,15 +1869,15 @@ aggregate_key: STRUCT - { $$ = DeclarationNode::Struct; } + { yyy = true; $$ = DeclarationNode::Struct; } | UNION - { $$ = DeclarationNode::Union; } + { yyy = true; $$ = DeclarationNode::Union; } | EXCEPTION - { $$ = DeclarationNode::Exception; } + { yyy = true; $$ = DeclarationNode::Exception; } | COROUTINE - { $$ = DeclarationNode::Coroutine; } + { yyy = true; $$ = DeclarationNode::Coroutine; } | MONITOR - { $$ = DeclarationNode::Monitor; } + { yyy = true; $$ = DeclarationNode::Monitor; } | THREAD - { $$ = DeclarationNode::Thread; } + { yyy = true; $$ = DeclarationNode::Thread; } ; @@ -2320,6 +2322,5 @@ translation_unit: - // empty - {} // empty input file + // empty, input file | external_definition_list { parseTree = parseTree ? parseTree->appendList( $1 ) : $1; } @@ -2335,22 +2336,16 @@ ; - // SKULLDUGGERY: Declarations in extern "X" and distribution need to be added to the current lexical scope. - // However, external_definition_list creates a new scope around each external_definition, but the pop loses all the - // types in the extern "X" and distribution at the end of the block. This version of external_definition_list does - - // not do push/pop for declarations at the level of the extern "X" and distribution block. Any recursive uses of - // external_definition_list within the extern "X" and distribution block correctly pushes/pops for that scope level. -external_definition_list_no_pop_push: - external_definition - | external_definition_list_no_pop_push - { forall = xxx; } - external_definition - { $$ = $1 ? $1->appendList( $3 ) : $3; } - ; - external_definition_list_opt: // empty { $$ = nullptr; } - | external_definition_list_no_pop_push + | external_definition_list + ; + +up: + { typedefTable.up(); } + ; + +down: + { typedefTable.down(); } ; @@ -2372,15 +2367,18 @@ linkage = LinkageSpec::linkageUpdate( yylloc, linkage, $2 ); } - '{' external_definition_list_opt '}' + '{' up external_definition_list_opt down '}' { linkage = linkageStack.top(); linkageStack.pop(); - $$ = $5; + $$ = $6; } | type_qualifier_list - { if ( $1->type->forall ) xxx = forall = true; } // remember generic type - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + { + if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2389,11 +2387,14 @@ xxx = false; delete $1; - $$ = $4; + $$ = $5; } | declaration_qualifier_list - { if ( $1->type->forall ) xxx = forall = true; } // remember generic type - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + { + if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2402,14 +2403,14 @@ xxx = false; delete $1; - $$ = $4; + $$ = $5; } | declaration_qualifier_list type_qualifier_list { - // forall must be in the type_qualifier_list - if ( $2->type->forall ) xxx = forall = true; // remember generic type - } - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + if ( ($1->type && $1->type->qualifiers.val) || $2->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( ($1->type && $1->type->forall) || $2->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $6; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) && isMangled( $2->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2420,5 +2421,5 @@ delete $1; delete $2; - $$ = $5; + $$ = $6; } ; Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/AlternativeFinder.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -1099,5 +1099,5 @@ argExpansions.emplace_back(); auto& argE = argExpansions.back(); - argE.reserve( arg.alternatives.size() ); + // argE.reserve( arg.alternatives.size() ); for ( const Alternative& actual : arg ) { Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/CommonType.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -24,5 +24,5 @@ #include "SynTree/Type.h" // for BasicType, BasicType::Kind::... #include "SynTree/Visitor.h" // for Visitor -#include "Unify.h" // for unifyExact, bindVar, WidenMode +#include "Unify.h" // for unifyExact, WidenMode #include "typeops.h" // for isFtype @@ -238,5 +238,5 @@ AssertionSet need, have; WidenMode widen( widenFirst, widenSecond ); - if ( entry != openVars.end() && ! bindVar(var, voidPointer->get_base(), entry->second, env, need, have, openVars, widen, indexer ) ) return; + if ( entry != openVars.end() && ! env.bindVar(var, voidPointer->get_base(), entry->second, need, have, openVars, widen, indexer ) ) return; } } Index: src/ResolvExpr/ExplodedActual.h =================================================================== --- src/ResolvExpr/ExplodedActual.h (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/ExplodedActual.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -32,6 +32,7 @@ ExplodedActual() : env(), cost(Cost::zero), exprs() {} - ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ); + ExplodedActual(ExplodedActual&&) = default; + ExplodedActual& operator= (ExplodedActual&&) = default; }; } Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/Resolver.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -582,8 +582,6 @@ // Make sure we don't widen any existing bindings - for ( auto & i : resultEnv ) { - i.allowWidening = false; - } - + resultEnv.forbidWidening(); + // Find any unbound type variables resultEnv.extractOpenVars( openVars ); Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/TypeEnvironment.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sun May 17 12:19:47 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sun May 17 12:23:36 2015 -// Update Count : 3 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 18 11:58:00 2018 +// Update Count : 4 // @@ -17,4 +17,5 @@ #include // for copy, set_intersection #include // for ostream_iterator, insert_iterator +#include // for unique_ptr #include // for pair, move @@ -22,5 +23,8 @@ #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... #include "SynTree/TypeSubstitution.h" // for TypeSubstitution +#include "Tuples/Tuples.h" // for isTtype #include "TypeEnvironment.h" +#include "typeops.h" // for occurs +#include "Unify.h" // for unifyInexact namespace ResolvExpr { @@ -65,4 +69,10 @@ } + EqvClass::EqvClass( EqvClass &&other ) + : vars{std::move(other.vars)}, type{other.type}, + allowWidening{std::move(other.allowWidening)}, data{std::move(other.data)} { + other.type = nullptr; + } + EqvClass &EqvClass::operator=( const EqvClass &other ) { if ( this == &other ) return *this; @@ -72,6 +82,25 @@ } + EqvClass &EqvClass::operator=( EqvClass &&other ) { + if ( this == &other ) return *this; + delete type; + + vars = std::move(other.vars); + type = other.type; + other.type = nullptr; + allowWidening = std::move(other.allowWidening); + data = std::move(other.data); + + return *this; + } + EqvClass::~EqvClass() { delete type; + } + + void EqvClass::set_type( Type* ty ) { + if ( ty == type ) return; + delete type; + type = ty; } @@ -92,11 +121,5 @@ const EqvClass* TypeEnvironment::lookup( const std::string &var ) const { for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.find( var ) != i->vars.end() ) { -/// std::cout << var << " is in class "; -/// i->print( std::cout ); - return &*i; - } -/// std::cout << var << " is not in class "; -/// i->print( std::cout ); + if ( i->vars.find( var ) != i->vars.end() ) return &*i; } // for return nullptr; @@ -116,9 +139,4 @@ } - void TypeEnvironment::add( const EqvClass &eqvClass ) { - filterOverlappingClasses( env, eqvClass ); - env.push_back( eqvClass ); - } - void TypeEnvironment::add( EqvClass &&eqvClass ) { filterOverlappingClasses( env, eqvClass ); @@ -131,5 +149,5 @@ newClass.vars.insert( (*i)->get_name() ); newClass.data = TypeDecl::Data{ (*i) }; - env.push_back( newClass ); + env.push_back( std::move(newClass) ); } // for } @@ -145,5 +163,5 @@ // transition to TypeSubstitution newClass.data = TypeDecl::Data{ TypeDecl::Dtype, false }; - add( newClass ); + add( std::move(newClass) ); } } @@ -152,13 +170,8 @@ for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) { for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) { -/// std::cerr << "adding " << *theVar; if ( theClass->type ) { -/// std::cerr << " bound to "; -/// theClass->type->print( std::cerr ); -/// std::cerr << std::endl; sub.add( *theVar, theClass->type ); } else if ( theVar != theClass->vars.begin() ) { TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->data.kind == TypeDecl::Ftype ); -/// std::cerr << " bound to variable " << *theClass->vars.begin() << std::endl; sub.add( *theVar, newTypeInst ); delete newTypeInst; @@ -166,8 +179,4 @@ } // for } // for -/// std::cerr << "input env is:" << std::endl; -/// print( std::cerr, 8 ); -/// std::cerr << "sub is:" << std::endl; -/// sub.print( std::cerr, 8 ); sub.normalize(); } @@ -181,7 +190,5 @@ std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) { for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.find( var ) == i->vars.end() ) { - return i; - } // if + if ( i->vars.count( var ) ) return i; } // for return env.end(); @@ -190,34 +197,4 @@ void TypeEnvironment::simpleCombine( const TypeEnvironment &second ) { env.insert( env.end(), second.env.begin(), second.env.end() ); - } - - 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 ) { - Type *newType = combineFunc( newClass.type, secondClass->type ); - delete newClass.type; - newClass.type = newType; - 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 } @@ -241,4 +218,152 @@ } + bool isFtype( Type *type ) { + if ( dynamic_cast< FunctionType* >( type ) ) { + return true; + } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { + 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; + } + + 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(); + OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() ); + assert( tyvar != openVars.end() ); + if ( ! tyVarCompatible( tyvar->second, bindTo ) ) { + return false; + } // if + if ( occurs( bindTo, typeInst->get_name(), *this ) ) { + return false; + } // if + auto curClass = internal_lookup( typeInst->get_name() ); + if ( curClass != env.end() ) { + if ( curClass->type ) { + Type *common = 0; + // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to + std::unique_ptr< Type > newType( curClass->type->clone() ); + newType->get_qualifiers() = typeInst->get_qualifiers(); + if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widenMode & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { + if ( common ) { + common->get_qualifiers() = Type::Qualifiers{}; + curClass->set_type( common ); + } // if + } else return false; + } else { + Type* newType = bindTo->clone(); + newType->get_qualifiers() = Type::Qualifiers{}; + curClass->set_type( newType ); + curClass->allowWidening = widenMode.widenFirst && widenMode.widenSecond; + } // if + } else { + EqvClass newClass; + newClass.vars.insert( typeInst->get_name() ); + newClass.type = bindTo->clone(); + newClass.type->get_qualifiers() = Type::Qualifiers(); + newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + newClass.data = data; + env.push_back( std::move(newClass) ); + } // if + 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 ) { + + auto class1 = internal_lookup( var1->get_name() ); + auto class2 = internal_lookup( var2->get_name() ); + + // exit early if variables already bound together + if ( class1 != env.end() && class1 == class2 ) { + class1->allowWidening &= widenMode; + return true; + } + + bool widen1 = false, widen2 = false; + const Type *type1 = nullptr, *type2 = nullptr; + + // check for existing bindings, perform occurs check + if ( class1 != env.end() ) { + if ( class1->type ) { + if ( occurs( class1->type, var2->get_name(), *this ) ) return false; + type1 = class1->type; + } // if + widen1 = widenMode.widenFirst && class1->allowWidening; + } // if + if ( class2 != env.end() ) { + if ( class2->type ) { + if ( occurs( class2->type, var1->get_name(), *this ) ) return false; + type2 = class2->type; + } // if + widen2 = widenMode.widenSecond && class2->allowWidening; + } // if + + if ( type1 && type2 ) { + // both classes bound, merge if bound types can be unified + std::unique_ptr newType1{ type1->clone() }, newType2{ type2->clone() }; + WidenMode newWidenMode{ widen1, widen2 }; + Type *common = 0; + if ( unifyInexact( newType1.get(), newType2.get(), *this, need, have, openVars, newWidenMode, indexer, common ) ) { + class1->vars.insert( class2->vars.begin(), class2->vars.end() ); + class1->allowWidening = widen1 && widen2; + if ( common ) { + common->get_qualifiers() = Type::Qualifiers{}; + class1->set_type( common ); + } + env.erase( class2 ); + } else return false; + } else if ( class1 != env.end() && class2 != env.end() ) { + // both classes exist, at least one unbound, merge unconditionally + if ( type1 ) { + class1->vars.insert( class2->vars.begin(), class2->vars.end() ); + class1->allowWidening = widen1; + env.erase( class2 ); + } else { + class2->vars.insert( class1->vars.begin(), class1->vars.end() ); + class2->allowWidening = widen2; + env.erase( class1 ); + } // if + } else if ( class1 != env.end() ) { + // var2 unbound, add to class1 + class1->vars.insert( var2->get_name() ); + class1->allowWidening = widen1; + } else if ( class2 != env.end() ) { + // var1 unbound, add to class2 + class2->vars.insert( var1->get_name() ); + class2->allowWidening = widen2; + } else { + // neither var bound, create new class + EqvClass newClass; + newClass.vars.insert( var1->get_name() ); + newClass.vars.insert( var2->get_name() ); + newClass.allowWidening = widen1 && widen2; + newClass.data = data; + env.push_back( std::move(newClass) ); + } // if + return true; + } + + void TypeEnvironment::forbidWidening() { + for ( EqvClass& c : env ) c.allowWidening = false; + } + std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) { env.print( out ); Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/TypeEnvironment.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // 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 : Mon Jun 18 11:58:00 2018 +// Update Count : 4 // @@ -21,4 +21,7 @@ #include // for set #include // for string +#include // for move, swap + +#include "WidenMode.h" // for WidenMode #include "SynTree/Declaration.h" // for TypeDecl::Data, DeclarationWit... @@ -77,7 +80,12 @@ EqvClass( const EqvClass &other ); EqvClass( const EqvClass &other, const Type *ty ); + EqvClass( EqvClass &&other ); EqvClass &operator=( const EqvClass &other ); + EqvClass &operator=( EqvClass &&other ); ~EqvClass(); void print( std::ostream &os, Indenter indent = {} ) const; + + /// Takes ownership of `ty`, freeing old `type` + void set_type(Type* ty); }; @@ -85,6 +93,7 @@ public: const EqvClass* lookup( const std::string &var ) const; - void add( const EqvClass &eqvClass ); + private: void add( EqvClass &&eqvClass ); + public: void add( const Type::ForallList &tyDecls ); void add( const TypeSubstitution & sub ); @@ -94,5 +103,5 @@ bool isEmpty() const { return env.empty(); } void print( std::ostream &os, Indenter indent = {} ) const; - void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ); + // void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ); void simpleCombine( const TypeEnvironment &second ); void extractOpenVars( OpenVarSet &openVars ) const; @@ -103,12 +112,22 @@ void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ); - typedef std::list< EqvClass >::iterator iterator; - iterator begin() { return env.begin(); } - iterator end() { return env.end(); } - typedef std::list< EqvClass >::const_iterator const_iterator; - const_iterator begin() const { return env.begin(); } - const_iterator end() const { return env.end(); } + /// Binds the type class represented by `typeInst` to the type `bindTo`; will add + /// the class if needed. Returns false on failure. + bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + + /// Binds the type classes represented by `var1` and `var2` together; will add + /// one or both classes if needed. Returns false on failure. + bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + + /// Disallows widening for all bindings in the environment + void forbidWidening(); + + using iterator = std::list< EqvClass >::const_iterator; + iterator begin() const { return env.begin(); } + iterator end() const { return env.end(); } + private: std::list< EqvClass > env; + std::list< EqvClass >::iterator internal_lookup( const std::string &var ); }; Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/Unify.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sun May 17 12:27:10 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Mar 16 16:22:54 2017 -// Update Count : 42 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 18 11:58:00 2018 +// Update Count : 43 // @@ -129,152 +129,4 @@ } - bool isFtype( Type *type ) { - if ( dynamic_cast< FunctionType* >( type ) ) { - return true; - } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { - 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; - } - - bool bindVar( TypeInstType *typeInst, Type *other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { - // remove references from other, so that type variables can only bind to value types - other = other->stripReferences(); - OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() ); - assert( tyvar != openVars.end() ); - if ( ! tyVarCompatible( tyvar->second, other ) ) { - return false; - } // if - if ( occurs( other, typeInst->get_name(), env ) ) { - return false; - } // if - if ( const EqvClass *curClass = env.lookup( typeInst->get_name() ) ) { - if ( curClass->type ) { - Type *common = 0; - // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to - std::unique_ptr< Type > newType( curClass->type->clone() ); - newType->get_qualifiers() = typeInst->get_qualifiers(); - if ( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { - if ( common ) { - common->get_qualifiers() = Type::Qualifiers(); - env.add( EqvClass{ *curClass, common } ); - } // if - return true; - } else { - return false; - } // if - } else { - EqvClass newClass { *curClass, other }; - newClass.type->get_qualifiers() = Type::Qualifiers(); - newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; - env.add( std::move(newClass) ); - } // if - } else { - EqvClass newClass; - newClass.vars.insert( typeInst->get_name() ); - newClass.type = other->clone(); - newClass.type->get_qualifiers() = Type::Qualifiers(); - newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; - newClass.data = data; - env.add( newClass ); - } // if - return true; - } - - bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { - bool result = true; - const EqvClass *class1 = env.lookup( var1->get_name() ); - const EqvClass *class2 = env.lookup( var2->get_name() ); - bool widen1 = false, widen2 = false; - Type *type1 = nullptr, *type2 = nullptr; - - if ( class1 ) { - if ( class1->type ) { - if ( occurs( class1->type, var2->get_name(), env ) ) { - return false; - } // if - type1 = class1->type->clone(); - } // if - widen1 = widenMode.widenFirst && class1->allowWidening; - } // if - if ( class2 ) { - if ( class2->type ) { - if ( occurs( class2->type, var1->get_name(), env ) ) { - return false; - } // if - type2 = class2->type->clone(); - } // if - widen2 = widenMode.widenSecond && class2->allowWidening; - } // if - - if ( type1 && type2 ) { -// std::cerr << "has type1 && type2" << std::endl; - WidenMode newWidenMode ( widen1, widen2 ); - Type *common = 0; - if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) { - EqvClass newClass1 = *class1; - newClass1.vars.insert( class2->vars.begin(), class2->vars.end() ); - newClass1.allowWidening = widen1 && widen2; - if ( common ) { - common->get_qualifiers() = Type::Qualifiers(); - delete newClass1.type; - newClass1.type = common; - } // if - env.add( std::move(newClass1) ); - } else { - result = false; - } // if - } else if ( class1 && class2 ) { - if ( type1 ) { - EqvClass newClass1 = *class1; - newClass1.vars.insert( class2->vars.begin(), class2->vars.end() ); - newClass1.allowWidening = widen1; - env.add( std::move(newClass1) ); - } else { - EqvClass newClass2 = *class2; - newClass2.vars.insert( class1->vars.begin(), class1->vars.end() ); - newClass2.allowWidening = widen2; - env.add( std::move(newClass2) ); - } // if - } else if ( class1 ) { - EqvClass newClass1 = *class1; - newClass1.vars.insert( var2->get_name() ); - newClass1.allowWidening = widen1; - env.add( std::move(newClass1) ); - } else if ( class2 ) { - EqvClass newClass2 = *class2; - newClass2.vars.insert( var1->get_name() ); - newClass2.allowWidening = widen2; - env.add( std::move(newClass2) ); - } else { - EqvClass newClass; - newClass.vars.insert( var1->get_name() ); - newClass.vars.insert( var2->get_name() ); - newClass.allowWidening = widen1 && widen2; - newClass.data = data; - env.add( newClass ); - } // if - delete type1; - delete type2; - return result; - } - bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { OpenVarSet closedVars; @@ -321,9 +173,9 @@ if ( isopen1 && isopen2 && entry1->second == entry2->second ) { - result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + result = env.bindVarToVar( var1, var2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer ); } else if ( isopen1 ) { - result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer ); } else if ( isopen2 ) { // TODO: swap widenMode values in call, since type positions are flipped? - result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widenMode, indexer ); } else { PassVisitor comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); Index: src/ResolvExpr/Unify.h =================================================================== --- src/ResolvExpr/Unify.h (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/ResolvExpr/Unify.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sun May 17 13:09:04 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Fri Jul 21 23:09:34 2017 -// Update Count : 3 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 18 11:58:00 2018 +// Update Count : 4 // @@ -21,4 +21,5 @@ #include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data #include "TypeEnvironment.h" // for AssertionSet, OpenVarSet +#include "WidenMode.h" // for WidenMode class Type; @@ -29,19 +30,8 @@ namespace ResolvExpr { - struct WidenMode { - WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {} - WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; } - WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; } - WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; } - WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; } - operator bool() { return widenFirst && widenSecond; } - - bool widenFirst : 1, widenSecond : 1; - }; - - bool bindVar( TypeInstType *typeInst, Type *other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ); bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); + bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ); template< typename Iterator1, typename Iterator2 > Index: src/ResolvExpr/WidenMode.h =================================================================== --- src/ResolvExpr/WidenMode.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) +++ src/ResolvExpr/WidenMode.h (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -0,0 +1,35 @@ +// +// 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. +// +// WidenMode.h -- +// +// Author : Aaron B. Moss +// Created On : Mon Jun 18 11:58:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 18 11:58:00 2018 +// Update Count : 1 +// + +#pragma once + +namespace ResolvExpr { + struct WidenMode { + WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {} + WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; } + WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; } + WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; } + WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; } + operator bool() { return widenFirst && widenSecond; } + + bool widenFirst : 1, widenSecond : 1; + }; +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/SynTree/Type.cc =================================================================== --- src/SynTree/Type.cc (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/SynTree/Type.cc (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Sep 25 15:16:32 2017 -// Update Count : 38 +// Last Modified On : Fri Jun 22 10:17:19 2018 +// Update Count : 39 // #include "Type.h" @@ -69,5 +69,5 @@ // These must remain in the same order as the corresponding bit fields. -const char * Type::FuncSpecifiersNames[] = { "inline", "fortran", "_Noreturn" }; +const char * Type::FuncSpecifiersNames[] = { "inline", "_Noreturn", "fortran" }; const char * Type::StorageClassesNames[] = { "extern", "static", "auto", "register", "_Thread_local" }; const char * Type::QualifiersNames[] = { "const", "restrict", "volatile", "lvalue", "mutex", "_Atomic" }; Index: src/tests/.gitignore =================================================================== --- src/tests/.gitignore (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/tests/.gitignore (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -1,2 +1,3 @@ .out/ .err/ +.type Index: src/tests/concurrent/coroutineYield.c =================================================================== --- src/tests/concurrent/coroutineYield.c (revision a12c81f30d4d4bc145747889f469cda8edb98b21) +++ src/tests/concurrent/coroutineYield.c (revision c653b37a0a370ac84dabe4b28e825c920a425f13) @@ -5,4 +5,5 @@ #include