Changeset eff03a94


Ignore:
Timestamp:
Jul 20, 2018, 2:13:20 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
new-env
Children:
f89a111
Parents:
d318a18
Message:

Fixed infinite loop bugs

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/Common/utility.h

    rd318a18 reff03a94  
    294294        aT m_after;
    295295
     296        FuncGuard( aT after ) : m_after( after ) {}
     297
    296298        template< typename bT >
    297299        FuncGuard( bT before, aT after ) : m_after( after ) {
     
    303305        }
    304306};
     307
     308template< typename aT >
     309FuncGuard<aT> makeFuncGuard( aT && after ) { return FuncGuard<aT>( std::forward<aT>(after) ); }
    305310
    306311template< typename bT, typename aT >
  • src/ResolvExpr/TypeEnvironment.cc

    rd318a18 reff03a94  
    3333
    3434namespace ResolvExpr {
    35         #if 1
     35        #if 0
    3636        #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
    3737        #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
  • src/SynTree/TypeSubstitution.cc

    rd318a18 reff03a94  
    1414//
    1515
    16 #include <ostream>  // for ostream, basic_ostream, operator<<, endl
    17 
    18 #include "Type.h"   // for TypeInstType, Type, StructInstType, UnionInstType
     16#include <algorithm>  // for find
     17#include <ostream>    // for ostream, basic_ostream, operator<<, endl
     18
     19#include "Type.h"     // for TypeInstType, Type, StructInstType, UnionInstType
    1920#include "TypeSubstitution.h"
    2021
     
    5960
    6061        // break on not in substitution set
    61         if ( i == typeEnv.end() ) return 0;
     62        if ( i == typeEnv.end() ) return nullptr;
    6263
    6364        // attempt to transitively follow TypeInstType links.
     65        std::vector<std::string> equivNames{ formalType };
    6466        while ( TypeInstType *actualType = dynamic_cast< TypeInstType* >( i->second ) ) {
    6567                const std::string& typeName = actualType->get_name();
    6668
    6769                // break cycles in the transitive follow
    68                 if ( formalType == typeName ) break;
    69 
    70                 // Look for the type this maps to, returning previous mapping if none-such
     70                if ( std::find( equivNames.begin(), equivNames.end(), typeName ) != equivNames.end() ) {
     71                        break;
     72                }
     73                equivNames.emplace_back( typeName );
     74
     75                // Look for the type this maps to, returning previous mapping if none such
    7176                i = typeEnv.find( typeName );
    7277                if ( i == typeEnv.end() ) return actualType;
    7378        }
     79
    7480
    7581        // return type from substitution set
     
    132138                return inst;
    133139        } else {
    134                 // cut off infinite loop for the case where a type is bound to itself.
    135                 // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
    136                 // TODO: investigate preventing type variables from being bound to themselves in the first place.
     140                // clear equivalent variables on exit
     141                auto guard = makeFuncGuard( [&]() { equivVars.clear(); } );
     142
    137143                if ( TypeInstType * replacement = dynamic_cast< TypeInstType * >( i->second ) ) {
    138                         if ( inst->name == replacement->name ) {
    139                                 return inst;
    140                         }
    141                 }
     144                        // cut off infinite loop if type is bound to itself (possibly transitively)
     145                        equivVars.push_back( inst );
     146                        auto equiv = std::find_if( equivVars.begin(), equivVars.end(), [&]( TypeInstType* e ) {
     147                                return e->name == replacement->name;
     148                        } );
     149                        if ( equiv != equivVars.end() ) return *equiv;
     150                }
     151
    142152                // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
    143153                subCount++;
  • src/SynTree/TypeSubstitution.h

    rd318a18 reff03a94  
    126126// definitition must happen after PassVisitor is included so that WithGuards can be used
    127127struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef<Substituter> {
    128                 Substituter( TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
     128                Substituter( TypeSubstitution & sub, bool freeOnly )
     129                        : sub( sub ), freeOnly( freeOnly ), boundVars(), equivVars() {}
    129130
    130131                Type * postmutate( TypeInstType * aggregateUseType );
     
    144145                typedef std::set< std::string > BoundVarsType;
    145146                BoundVarsType boundVars;
     147                std::vector<TypeInstType*> equivVars;  ///< equivalent names of type variables
    146148};
    147149
Note: See TracChangeset for help on using the changeset viewer.