Changeset eff03a94 for src

Timestamp:

Jul 20, 2018, 2:13:20 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

f89a111

Parents:

d318a18

Message:

Fixed infinite loop bugs

Location:

src

Files:

• Common/utility.h (modified) (2 diffs)
• ResolvExpr/TypeEnvironment.cc (modified) (1 diff)
• SynTree/TypeSubstitution.cc (modified) (3 diffs)
• SynTree/TypeSubstitution.h (modified) (2 diffs)

src/Common/utility.h

@@ -294 +294 @@
         aT m_after;
 
+        FuncGuard( aT after ) : m_after( after ) {}
+
         template< typename bT >
         FuncGuard( bT before, aT after ) : m_after( after ) {
@@ -303 +305 @@
         }
 };
+
+template< typename aT >
+FuncGuard<aT> makeFuncGuard( aT && after ) { return FuncGuard<aT>( std::forward<aT>(after) ); }
 
 template< typename bT, typename aT >

src/ResolvExpr/TypeEnvironment.cc

@@ -33 +33 @@
 
 namespace ResolvExpr {
-        #if 1
+        #if 0
         #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
         #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};

src/SynTree/TypeSubstitution.cc

@@ -14 +14 @@
 //
 
-#include <ostream>  // for ostream, basic_ostream, operator<<, endl
-
-#include "Type.h"   // for TypeInstType, Type, StructInstType, UnionInstType
+#include <algorithm>  // for find
+#include <ostream>    // for ostream, basic_ostream, operator<<, endl
+
+#include "Type.h"     // for TypeInstType, Type, StructInstType, UnionInstType
 #include "TypeSubstitution.h"
 
@@ -59 +60 @@
 
         // break on not in substitution set
-        if ( i == typeEnv.end() ) return 0;
+        if ( i == typeEnv.end() ) return nullptr;
 
         // attempt to transitively follow TypeInstType links.
+        std::vector<std::string> equivNames{ formalType };
         while ( TypeInstType *actualType = dynamic_cast< TypeInstType* >( i->second ) ) {
                 const std::string& typeName = actualType->get_name();
 
                 // break cycles in the transitive follow
-                if ( formalType == typeName ) break;
-
-                // Look for the type this maps to, returning previous mapping if none-such
+                if ( std::find( equivNames.begin(), equivNames.end(), typeName ) != equivNames.end() ) {
+                        break;
+                }
+                equivNames.emplace_back( typeName );
+
+                // Look for the type this maps to, returning previous mapping if none such
                 i = typeEnv.find( typeName );
                 if ( i == typeEnv.end() ) return actualType;
         }
+
 
         // return type from substitution set
@@ -132 +138 @@
                 return inst;
         } else {
-                // cut off infinite loop for the case where a type is bound to itself.
-                // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
-                // TODO: investigate preventing type variables from being bound to themselves in the first place.
+                // clear equivalent variables on exit
+                auto guard = makeFuncGuard( [&]() { equivVars.clear(); } );
+
                 if ( TypeInstType * replacement = dynamic_cast< TypeInstType * >( i->second ) ) {
-                        if ( inst->name == replacement->name ) {
-                                return inst;
-                        }
-                }
+                        // cut off infinite loop if type is bound to itself (possibly transitively)
+                        equivVars.push_back( inst );
+                        auto equiv = std::find_if( equivVars.begin(), equivVars.end(), [&]( TypeInstType* e ) {
+                                return e->name == replacement->name;
+                        } );
+                        if ( equiv != equivVars.end() ) return *equiv;
+                }
+
                 // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
                 subCount++;

src/SynTree/TypeSubstitution.h

@@ -126 +126 @@
 // definitition must happen after PassVisitor is included so that WithGuards can be used
 struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef<Substituter> {
-                Substituter( TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
+                Substituter( TypeSubstitution & sub, bool freeOnly )
+                        : sub( sub ), freeOnly( freeOnly ), boundVars(), equivVars() {}
 
                 Type * postmutate( TypeInstType * aggregateUseType );
@@ -144 +145 @@
                 typedef std::set< std::string > BoundVarsType;
                 BoundVarsType boundVars;
+                std::vector<TypeInstType*> equivVars;  ///< equivalent names of type variables
 };