Changeset eff03a94 for src/SynTree/TypeSubstitution.cc

Timestamp:

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

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

f89a111

Parents:

d318a18

Message:

Fixed infinite loop bugs

File:

• src/SynTree/TypeSubstitution.cc (modified) (3 diffs)

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++;