Changes in / [fbcb354:2ad507b8]

Location:

src

Files:

• ResolvExpr/AlternativeFinder.cc (modified) (2 diffs)
• ResolvExpr/RenameVars.cc (modified) (1 diff)
• ResolvExpr/TypeEnvironment.cc (modified) (1 diff)
• ResolvExpr/TypeEnvironment.h (modified) (1 diff)
• SymTab/Indexer.cc (modified) (1 diff)
• SymTab/Validate.cc (modified) (4 diffs)
• SynTree/Mutator.cc (modified) (1 diff)
• SynTree/ReferenceToType.cc (modified) (1 diff)
• SynTree/Type.h (modified) (1 diff)
• SynTree/TypeSubstitution.h (modified) (1 diff)
• SynTree/Visitor.cc (modified) (1 diff)
• prelude/prelude.cf (modified) (1 diff)
• tests/.expect/function-operator.txt (deleted)
• tests/function-operator.c (deleted)

src/ResolvExpr/AlternativeFinder.cc

@@ -749 +749 @@
                                 if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
                                         if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
-                                                Alternative newFunc( *func );
-                                                referenceToRvalueConversion( newFunc.expr );
+                                                referenceToRvalueConversion( func->expr );
                                                 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
                                                         // XXX
                                                         //Designators::check_alternative( function, *actualAlt );
-                                                        makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
+                                                        makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
                                                 }
                                         }
                                 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
+                                        referenceToRvalueConversion( func->expr );
                                         EqvClass eqvClass;
                                         if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
                                                 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
-                                                        Alternative newFunc( *func );
-                                                        referenceToRvalueConversion( newFunc.expr );
                                                         for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
-                                                                makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
+                                                                makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
                                                         } // for
                                                 } // if
@@ -775 +773 @@
                                         if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) {
                                                 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
-                                                        Alternative newFunc( *funcOp );
-                                                        referenceToRvalueConversion( newFunc.expr );
+                                                        referenceToRvalueConversion( funcOp->expr );
                                                         for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
                                                                 AltList currentAlt;
                                                                 currentAlt.push_back( *func );
                                                                 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
-                                                                makeFunctionAlternatives( newFunc, function, currentAlt, std::back_inserter( candidates ) );
+                                                                makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
                                                         } // for
                                                 } // if

src/ResolvExpr/RenameVars.cc

@@ -88 +88 @@
                 typeBefore( aggregateUseType );
                 acceptAll( aggregateUseType->get_parameters(), *this );
+                acceptAll( aggregateUseType->get_members(), *this );
                 typeAfter( aggregateUseType );
         }

src/ResolvExpr/TypeEnvironment.cc

@@ -25 +25 @@
 
 namespace ResolvExpr {
+        // adding this comparison operator significantly improves assertion resolution run time for
+        // some cases. The current resolution 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 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 comparator.
+        bool AssertCompare::operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
+                        // Objects are always less than functions
+                        if ( ObjectDecl * objectDecl1 = dynamic_cast< ObjectDecl * >( d1 ) ) {
+                                if ( ObjectDecl * objectDecl2 = dynamic_cast< ObjectDecl * >( d2 ) ) {
+                                        // objects are ordered by name then type pointer, in that order
+                                        int cmp = objectDecl1->get_name().compare( objectDecl2->get_name() );
+                                        return cmp < 0 ||
+                                                ( cmp == 0 && objectDecl1->get_type() < objectDecl2->get_type() );
+                                } else {
+                                        return true;
+                                }
+                        } else if ( FunctionDecl * funcDecl1 = dynamic_cast< FunctionDecl * >( d1 ) ) {
+                                if ( FunctionDecl * funcDecl2 = dynamic_cast< FunctionDecl * >( d2 ) ) {
+                                        // functions are ordered by name, # parameters, # returnVals, type pointer in that order
+                                        FunctionType * ftype1 = funcDecl1->get_functionType();
+                                        FunctionType * ftype2 = funcDecl2->get_functionType();
+                                        int numThings1 = ftype1->get_parameters().size() + ftype1->get_returnVals().size();
+                                        int numThings2 = ftype2->get_parameters().size() + ftype2->get_returnVals().size();
+                                        if ( numThings1 < numThings2 ) return true;
+                                        if ( numThings1 > numThings2 ) return false;
+
+                                        // if ( ftype1->get_parameters().size() < ftype2->get_parameters().size() ) return true;
+                                        // else if ( ftype1->get_parameters().size() > ftype2->get_parameters().size() ) return false;
+                                        // // same number of parameters
+                                        // if ( ftype1->get_returnVals().size() < ftype2->get_returnVals().size() ) return true;
+                                        // else if ( ftype1->get_returnVals().size() > ftype2->get_returnVals().size() ) return false;
+                                        // same number of return vals
+                                        // int cmp = funcDecl1->get_name().compare( funcDecl2->get_name() );
+                                        // if ( cmp < 0 ) return true;
+                                        // else if ( cmp > 0 ) return false;
+                                        // // same name
+                                        return ftype1 < ftype2;
+                                } else {
+                                        return false;
+                                }
+                        } else {
+                                assert( false );
+                        }
+                }
+
         void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
                 for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {

src/ResolvExpr/TypeEnvironment.h

@@ -28 +28 @@
 
 namespace ResolvExpr {
-        // adding this comparison operator significantly improves assertion resolution run time for
-        // some cases. The current resolution 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 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 comparator.
         struct AssertCompare {
-                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
-                        int cmp = d1->get_name().compare( d2->get_name() );
-                        return cmp < 0 ||
-                                ( cmp == 0 && d1->get_type() < d2->get_type() );
-                }
+                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const;
         };
         struct AssertionSetValue {

src/SymTab/Indexer.cc

@@ -554 +554 @@
 
 
-        void Indexer::visit( TraitInstType *traitInst ) {
-                acceptAll( traitInst->get_parameters(), *this );
+        void Indexer::visit( TraitInstType *contextInst ) {
+                acceptAll( contextInst->get_parameters(), *this );
+                acceptAll( contextInst->get_members(), *this );
         }
 

src/SymTab/Validate.cc

@@ -127 +127 @@
           public:
                 LinkReferenceToTypes( bool doDebug, const Indexer *indexer );
-                using Parent::visit;
-                void visit( TypeInstType *typeInst ) final;
-
+                using Parent::visit;
                 void visit( EnumInstType *enumInst ) final;
                 void visit( StructInstType *structInst ) final;
                 void visit( UnionInstType *unionInst ) final;
-                void visit( TraitInstType *traitInst ) final;
-
+                void visit( TraitInstType *contextInst ) final;
                 void visit( EnumDecl *enumDecl ) final;
                 void visit( StructDecl *structDecl ) final;
                 void visit( UnionDecl *unionDecl ) final;
-                void visit( TraitDecl * traitDecl ) final;
-
+                void visit( TypeInstType *typeInst ) final;
           private:
                 const Indexer *indexer;
@@ -457 +453 @@
         }
 
-        template< typename Decl >
-        void normalizeAssertions( std::list< Decl * > & assertions ) {
-                // ensure no duplicate trait members after the clone
-                auto pred = [](Decl * d1, Decl * d2) {
-                        // only care if they're equal
-                        DeclarationWithType * dwt1 = dynamic_cast<DeclarationWithType *>( d1 );
-                        DeclarationWithType * dwt2 = dynamic_cast<DeclarationWithType *>( d2 );
-                        if ( dwt1 && dwt2 ) {
-                                if ( dwt1->get_name() == dwt2->get_name() && ResolvExpr::typesCompatible( dwt1->get_type(), dwt2->get_type(), SymTab::Indexer() ) ) {
-                                        // std::cerr << "=========== equal:" << std::endl;
-                                        // std::cerr << "d1: " << d1 << std::endl;
-                                        // std::cerr << "d2: " << d2 << std::endl;
-                                        return false;
-                                }
+        void LinkReferenceToTypes::visit( TraitInstType *traitInst ) {
+                Parent::visit( traitInst );
+                if ( traitInst->get_name() == "sized" ) {
+                        // "sized" is a special trait with no members - just flick the sized status on for the type variable
+                        if ( traitInst->get_parameters().size() != 1 ) {
+                                throw SemanticError( "incorrect number of trait parameters: ", traitInst );
                         }
-                        return d1 < d2;
-                };
-                std::set<Decl *, decltype(pred)> unique_members( assertions.begin(), assertions.end(), pred );
-                // if ( unique_members.size() != assertions.size() ) {
-                //      std::cerr << "============different" << std::endl;
-                //      std::cerr << unique_members.size() << " " << assertions.size() << std::endl;
-                // }
-
-                std::list< Decl * > order;
-                order.splice( order.end(), assertions );
-                std::copy_if( order.begin(), order.end(), back_inserter( assertions ), [&]( Decl * decl ) {
-                        return unique_members.count( decl );
-                });
-        }
-
-        // expand assertions from trait instance, performing the appropriate type variable substitutions
-        template< typename Iterator >
-        void expandAssertions( TraitInstType * inst, Iterator out ) {
-                assertf( inst->baseTrait, "Trait instance not linked to base trait: %s", toString( inst ).c_str() );
-                std::list< DeclarationWithType * > asserts;
-                for ( Declaration * decl : inst->baseTrait->members ) {
-                        asserts.push_back( safe_dynamic_cast<DeclarationWithType *>( decl->clone() ) );
-                }
-                // substitute trait decl parameters for instance parameters
-                applySubstitution( inst->baseTrait->parameters.begin(), inst->baseTrait->parameters.end(), inst->parameters.begin(), asserts.begin(), asserts.end(), out );
-        }
-
-        void LinkReferenceToTypes::visit( TraitDecl * traitDecl ) {
-                Parent::visit( traitDecl );
-
-                if ( traitDecl->name == "sized" ) {
-                        // "sized" is a special trait - flick the sized status on for the type variable
-                        assertf( traitDecl->parameters.size() == 1, "Built-in trait 'sized' has incorrect number of parameters: %zd", traitDecl->parameters.size() );
-                        TypeDecl * td = traitDecl->parameters.front();
-                        td->set_sized( true );
-                }
-
-                // move assertions from type parameters into the body of the trait
-                for ( TypeDecl * td : traitDecl->parameters ) {
-                        for ( DeclarationWithType * assert : td->assertions ) {
-                                if ( TraitInstType * inst = dynamic_cast< TraitInstType * >( assert->get_type() ) ) {
-                                        expandAssertions( inst, back_inserter( traitDecl->members ) );
-                                } else {
-                                        traitDecl->members.push_back( assert->clone() );
-                                }
-                        }
-                        deleteAll( td->assertions );
-                        td->assertions.clear();
-                } // for
-        }
-
-        void LinkReferenceToTypes::visit( TraitInstType * traitInst ) {
-                Parent::visit( traitInst );
+                        TypeExpr * param = safe_dynamic_cast< TypeExpr * > ( traitInst->get_parameters().front() );
+                        TypeInstType * inst = safe_dynamic_cast< TypeInstType * > ( param->get_type() );
+                        TypeDecl * decl = inst->get_baseType();
+                        decl->set_sized( true );
+                        // since "sized" is special, the next few steps don't apply
+                        return;
+                }
+
                 // handle other traits
-                TraitDecl *traitDecl = indexer->lookupTrait( traitInst->name );
+                TraitDecl *traitDecl = indexer->lookupTrait( traitInst->get_name() );
                 if ( ! traitDecl ) {
-                        throw SemanticError( "use of undeclared trait " + traitInst->name );
+                        throw SemanticError( "use of undeclared trait " + traitInst->get_name() );
                 } // if
                 if ( traitDecl->get_parameters().size() != traitInst->get_parameters().size() ) {
                         throw SemanticError( "incorrect number of trait parameters: ", traitInst );
                 } // if
-                traitInst->baseTrait = traitDecl;
+
+                for ( TypeDecl * td : traitDecl->get_parameters() ) {
+                        for ( DeclarationWithType * assert : td->get_assertions() ) {
+                                traitInst->get_members().push_back( assert->clone() );
+                        } // for
+                } // for
+
+                // need to clone members of the trait for ownership purposes
+                std::list< Declaration * > members;
+                std::transform( traitDecl->get_members().begin(), traitDecl->get_members().end(), back_inserter( members ), [](Declaration * dwt) { return dwt->clone(); } );
+
+                applySubstitution( traitDecl->get_parameters().begin(), traitDecl->get_parameters().end(), traitInst->get_parameters().begin(), members.begin(), members.end(), back_inserter( traitInst->get_members() ) );
 
                 // need to carry over the 'sized' status of each decl in the instance
@@ -544 +498 @@
                         }
                 }
-                // normalizeAssertions( traitInst->members );
         }
 
@@ -608 +561 @@
         void forallFixer( Type * func ) {
                 for ( TypeDecl * type : func->get_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
-                        // apply FixFunction to every assertion to check for invalid void type
-                        for ( DeclarationWithType *& assertion : type->assertions ) {
-                                FixFunction fixer;
-                                assertion = assertion->acceptMutator( fixer );
-                                if ( fixer.get_isVoid() ) {
-                                        throw SemanticError( "invalid type void in assertion of function ", func );
-                                } // if
-                        } // for
-                        // normalizeAssertions( type->assertions );
+                        std::list< DeclarationWithType * > toBeDone, nextRound;
+                        toBeDone.splice( toBeDone.end(), type->get_assertions() );
+                        while ( ! toBeDone.empty() ) {
+                                for ( DeclarationWithType * assertion : toBeDone ) {
+                                        if ( TraitInstType *traitInst = dynamic_cast< TraitInstType * >( assertion->get_type() ) ) {
+                                                // expand trait instance into all of its members
+                                                for ( Declaration * member : traitInst->get_members() ) {
+                                                        DeclarationWithType *dwt = safe_dynamic_cast< DeclarationWithType * >( member );
+                                                        nextRound.push_back( dwt->clone() );
+                                                }
+                                                delete traitInst;
+                                        } else {
+                                                // pass assertion through
+                                                FixFunction fixer;
+                                                assertion = assertion->acceptMutator( fixer );
+                                                if ( fixer.get_isVoid() ) {
+                                                        throw SemanticError( "invalid type void in assertion of function ", func );
+                                                }
+                                                type->get_assertions().push_back( assertion );
+                                        } // if
+                                } // for
+                                toBeDone.clear();
+                                toBeDone.splice( toBeDone.end(), nextRound );
+                        } // while
                 } // for
         }

src/SynTree/Mutator.cc

@@ -538 +538 @@
 Type * Mutator::mutate( TraitInstType *aggregateUseType ) {
         handleReferenceToType( aggregateUseType );
+        mutateAll( aggregateUseType->get_members(), *this );
         return aggregateUseType;
 }

src/SynTree/ReferenceToType.cc

@@ -132 +132 @@
 std::string TraitInstType::typeString() const { return "trait"; }
 
-TraitInstType::TraitInstType( const Type::Qualifiers & tq, TraitDecl * baseTrait, const std::list< Attribute * > & attributes ) : Parent( tq, baseTrait->name, attributes ), baseTrait( baseTrait ) {}
-
-TraitInstType::TraitInstType( const TraitInstType &other ) : Parent( other ), baseTrait( other.baseTrait ) {
+TraitInstType::TraitInstType( const TraitInstType &other ) : Parent( other ) {
+        cloneAll( other.members, members );
 }
 
 TraitInstType::~TraitInstType() {
+        deleteAll( members );
 }
 

src/SynTree/Type.h

@@ -471 +471 @@
         typedef ReferenceToType Parent;
   public:
-        // this decl is not "owned" by the trait inst; it is merely a pointer to elsewhere in the tree,
-        // where the trait used in this type is actually defined
-        TraitDecl * baseTrait = nullptr;
-
-        TraitInstType( const Type::Qualifiers & tq, const std::string & name, const std::list< Attribute * > & attributes = std::list< Attribute * >() ) : Parent( tq, name, attributes ) {}
-        TraitInstType( const Type::Qualifiers & tq, TraitDecl * baseTrait, const std::list< Attribute * > & attributes = std::list< Attribute * >() );
+        // this member is filled in by the validate pass, which instantiates the members of the correponding
+        // aggregate with the actual type parameters specified for this use of the context
+        std::list< Declaration* > members;
+
+        TraitInstType( const Type::Qualifiers & tq, const std::string & name, const std::list< Attribute * > & attributes = std::list< Attribute * >()  ) : Parent( tq, name, attributes ) {}
         TraitInstType( const TraitInstType & other );
         ~TraitInstType();
+
+        std::list< Declaration* >& get_members() { return members; }
 
         virtual bool isComplete() const;

src/SynTree/TypeSubstitution.h

@@ -177 +177 @@
 void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) {
         TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual );
-        for ( auto i = memberBegin; i != memberEnd; ++i ) {
+        for ( std::list< Declaration* >::iterator i = memberBegin; i != memberEnd; ++i ) {
                 sub.apply( *i );
                 *out++ = *i;

src/SynTree/Visitor.cc

@@ -429 +429 @@
 void Visitor::visit( TraitInstType *aggregateUseType ) {
         handleReferenceToType( static_cast< ReferenceToType * >( aggregateUseType ) );
+        acceptAll( aggregateUseType->get_members(), *this );
 }
 

src/prelude/prelude.cf

@@ -14 +14 @@
 
 // Section numbers from: http://plg.uwaterloo.ca/~cforall/refrat.pdf
-
-// ------------------------------------------------------------
-//
-// Section 6.7.11 Trait Declarations
-// Note: the sized trait is used in declarations later in this
-// file, so it must be out of order.
-//
-// ------------------------------------------------------------
-
-trait sized(dtype T) {};
 
 // ------------------------------------------------------------