Index: src/Common/GC.h =================================================================== --- src/Common/GC.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Common/GC.h (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -69,4 +69,27 @@ bool mark; ///< The current collection's mark bit unsigned g; ///< The current number generation in use + + /// Trace a traceable object (enabled by SFINAE) + template + static inline auto do_trace(const GC& gc, T& obj, int) -> decltype(gc << obj, void()) { + gc << obj; + } + + /// Do not trace an untraceable object + template + static inline auto do_trace(const GC&, T&, long) -> void {} + + /// Base case for maybe_trace + void maybe_trace() const {} + +public: + /// Trace any objects that are traceable + template + void maybe_trace(T& obj, Args&... args) const { + // uses SFINAE trick to select proper overload; prefers actually tracing version + // (because of int->long conversion), but will fall back to non-tracing + do_trace(*this, obj, 0); + maybe_trace(args...); + } }; Index: src/Common/PersistentDisjointSet.h =================================================================== --- src/Common/PersistentDisjointSet.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Common/PersistentDisjointSet.h (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -129,4 +129,10 @@ } + /// reset as base + void reset_as_base() { + assertf( mode == BASE, "can only reset_as_base() on BASE" ); + as().~Base(); + } + /// Non-initializing constructor; should call init() before use PersistentDisjointSet( Mode m ) : data(), mode(m) {} @@ -165,5 +171,5 @@ case BASE: { for (const auto& entry : as()) { - gc << entry.first; + gc.maybe_trace( entry.first ); } return; @@ -171,10 +177,12 @@ case ADD: case REM: { const Add& self = as(); - gc << self.base << self.root; + gc << self.base; + gc.maybe_trace( self.root ); return; } case ADDTO: case REMFROM: { const AddTo& self = as(); - gc << self.base << self.root << self.child; + gc << self.base; + gc.maybe_trace( self.root, self.child ); return; } @@ -210,5 +218,5 @@ // take map out of base Base base_map = base->take_as(); - base->reset(); + base->reset_as_base(); // switch base to inverse of self and mutate base map @@ -331,5 +339,5 @@ // transfer map to new node Self* ret = new Self{ BASE, take_as() }; - reset(); + reset_as_base(); // set self to REM node @@ -352,5 +360,5 @@ // transfer map to new node Self* ret = new Self{ BASE, take_as() }; - reset(); + reset_as_base(); // find set nodes @@ -449,5 +457,5 @@ /// `f` should take members by const reference or copy template - void apply_to_class(Elm i, F&& f) const { + void for_class(Elm i, F&& f) const { const Base& self = rerooted(); Index: src/Common/PersistentMap.h =================================================================== --- src/Common/PersistentMap.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Common/PersistentMap.h (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -139,5 +139,5 @@ case BASE: { for (const auto& entry : as()) { - gc << entry.first << entry.second; + gc.maybe_trace( entry.first, entry.second ); } return; @@ -145,10 +145,12 @@ case REM: { const Rem& self = as(); - gc << self.base << self.key; + gc << self.base; + gc.maybe_trace( self.key ); return; } case INS: case UPD: { const Ins& self = as(); - gc << self.base << self.key << self.val; + gc << self.base; + gc.maybe_trace( self.key, self.val ); return; } @@ -424,4 +426,11 @@ } + /// Applies the function `f` to all elements of the map. + /// `f` should take two parameters, `const Key&` and `const Val&`. + template + void for_each(F&& f) const { + for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); } + } + /// Applies the function `f` to all elements of the map, returning a pointer to the updated map. /// `f` should take two parameters, `const Key&` and `Val&`, returning option filled with @@ -429,5 +438,5 @@ /// NOTE: when porting to C++17, this should work fine with std::optional template - Self* apply_to_all(F&& f) { + Self* mutate_each(F&& f) { // reset to root and exit early if no change if ( rerooted().empty() ) return this; @@ -454,11 +463,4 @@ return next_edit; } - - /// Applies the function `f` to all elements of the map. - /// `f` should take two parameters, `const Key&` and `const Val&`. - template - void apply_to_all(F&& f) const { - for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); } - } }; Index: src/Common/option.h =================================================================== --- src/Common/option.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Common/option.h (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -16,9 +16,8 @@ #pragma once +#include #include #include #include - -#include "debug.h" using std::move; @@ -121,8 +120,8 @@ /// Get contained value (checked) - T& value() & { assume(filled, "checked get failed"); return get(); } - const T& value() const& { assume(filled, "checked get failed"); return get(); } - T&& value() && { assume(filled, "checked get failed"); return move(get()); } - const T&& value() const&& { assume(filled, "checked get failed"); return move(get()); } + T& value() & { assertf(filled, "checked get failed"); return get(); } + const T& value() const& { assertf(filled, "checked get failed"); return get(); } + T&& value() && { assertf(filled, "checked get failed"); return move(get()); } + const T&& value() const&& { assertf(filled, "checked get failed"); return move(get()); } /// Get contained or default value Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Makefile.in (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -165,4 +165,5 @@ Common/driver_cfa_cpp-GC.$(OBJEXT) \ Common/driver_cfa_cpp-Assert.$(OBJEXT) \ + Common/driver_cfa_cpp-InternedString.$(OBJEXT) \ Common/driver_cfa_cpp-Heap.$(OBJEXT) \ ControlStruct/driver_cfa_cpp-LabelGenerator.$(OBJEXT) \ @@ -489,5 +490,5 @@ Concurrency/Waitfor.cc Common/SemanticError.cc \ Common/UniqueName.cc Common/DebugMalloc.cc Common/GC.cc \ - Common/Assert.cc Common/Heap.cc \ + Common/Assert.cc Common/InternedString.cc Common/Heap.cc \ ControlStruct/LabelGenerator.cc ControlStruct/LabelFixer.cc \ ControlStruct/MLEMutator.cc ControlStruct/Mutate.cc \ @@ -680,4 +681,6 @@ Common/driver_cfa_cpp-Assert.$(OBJEXT): Common/$(am__dirstamp) \ Common/$(DEPDIR)/$(am__dirstamp) +Common/driver_cfa_cpp-InternedString.$(OBJEXT): \ + Common/$(am__dirstamp) Common/$(DEPDIR)/$(am__dirstamp) Common/driver_cfa_cpp-Heap.$(OBJEXT): Common/$(am__dirstamp) \ Common/$(DEPDIR)/$(am__dirstamp) @@ -986,4 +989,5 @@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-GC.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-Heap.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-SemanticError.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@Common/$(DEPDIR)/driver_cfa_cpp-UniqueName.Po@am__quote@ @@ -1336,4 +1340,18 @@ @am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-Assert.obj `if test -f 'Common/Assert.cc'; then $(CYGPATH_W) 'Common/Assert.cc'; else $(CYGPATH_W) '$(srcdir)/Common/Assert.cc'; fi` +Common/driver_cfa_cpp-InternedString.o: Common/InternedString.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT Common/driver_cfa_cpp-InternedString.o -MD -MP -MF Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Tpo -c -o Common/driver_cfa_cpp-InternedString.o `test -f 'Common/InternedString.cc' || echo '$(srcdir)/'`Common/InternedString.cc +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Tpo Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='Common/InternedString.cc' object='Common/driver_cfa_cpp-InternedString.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-InternedString.o `test -f 'Common/InternedString.cc' || echo '$(srcdir)/'`Common/InternedString.cc + +Common/driver_cfa_cpp-InternedString.obj: Common/InternedString.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT Common/driver_cfa_cpp-InternedString.obj -MD -MP -MF Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Tpo -c -o Common/driver_cfa_cpp-InternedString.obj `if test -f 'Common/InternedString.cc'; then $(CYGPATH_W) 'Common/InternedString.cc'; else $(CYGPATH_W) '$(srcdir)/Common/InternedString.cc'; fi` +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Tpo Common/$(DEPDIR)/driver_cfa_cpp-InternedString.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='Common/InternedString.cc' object='Common/driver_cfa_cpp-InternedString.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o Common/driver_cfa_cpp-InternedString.obj `if test -f 'Common/InternedString.cc'; then $(CYGPATH_W) 'Common/InternedString.cc'; else $(CYGPATH_W) '$(srcdir)/Common/InternedString.cc'; fi` + Common/driver_cfa_cpp-Heap.o: Common/Heap.cc @am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT Common/driver_cfa_cpp-Heap.o -MD -MP -MF Common/$(DEPDIR)/driver_cfa_cpp-Heap.Tpo -c -o Common/driver_cfa_cpp-Heap.o `test -f 'Common/Heap.cc' || echo '$(srcdir)/'`Common/Heap.cc Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/ResolvExpr/AlternativeFinder.cc (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -454,5 +454,5 @@ } - #if 0 // cost of assertions accounted for in function creation + #if 1 // cost of assertions accounted for in function creation for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); @@ -584,4 +584,5 @@ } +#if !1 namespace { /// Information required to defer resolution of an expression @@ -700,4 +701,5 @@ } } +#endif template< typename OutputIterator > @@ -715,5 +717,5 @@ // ) addToIndexer( have, decls ); - +#if !1 AssertionResnState resn{ newAlt, openVars, indexer }; @@ -752,5 +754,5 @@ *out++ = newAlt; -#if 0 +#else AssertionSet newNeed; PRINT( @@ -1093,4 +1095,5 @@ } +#if !1 namespace { @@ -1230,4 +1233,5 @@ } } +#endif template @@ -1276,5 +1280,9 @@ // calculate declaration cost of function (+vars-spec) +#if !1 Cost funcCost = declCost( funcType ); +#else + Cost funcCost = Cost::zero; +#endif // iteratively build matches, one parameter at a time Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/ResolvExpr/TypeEnvironment.cc (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -27,4 +27,5 @@ #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 @@ -104,5 +105,5 @@ auto tyVar = openVars.find( typeInst->get_name() ); assert( tyVar != openVars.end() ); - if ( ! tyVarCompatible( tyVar->second, other ) ) return false; + if ( ! tyVarCompatible( tyVar->second, bindTo ) ) return false; if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false; @@ -135,5 +136,6 @@ } else { // make new class consisting entirely of this variable - BoundType curData{ bindTo->clone(), widenMode.first && widenMode.second, data }; + BoundType curData{ + bindTo->clone(), widenMode.widenFirst && widenMode.widenSecond, data }; curData.type->get_qualifiers() = Type::Qualifiers{}; classes = classes->add( curClass.get_root() ); @@ -146,6 +148,6 @@ const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) { - ClassRef class1 = env.lookup( var1->get_name() ); - ClassRef class2 = env.lookup( var2->get_name() ); + ClassRef class1 = lookup( var1->get_name() ); + ClassRef class2 = lookup( var2->get_name() ); // exit early if variables already bound together @@ -153,5 +155,5 @@ BoundType data1 = class1.get_bound(); // narrow the binding if needed - if ( data1.allowWidening && widenMode.first != widenMode.second ) { + if ( data1.allowWidening && widenMode.widenFirst != widenMode.widenSecond ) { data1.allowWidening = false; bindings = bindings->set( class1.get_root(), data1 ); @@ -172,5 +174,6 @@ openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) { // merge type variables - interned_string root = mergeClasses( class1.update_root(), class2.update_root() ); + interned_string root = + mergeClasses( class1.update_root(), class2.update_root() ).first; // update bindings data1.allowWidening = widen1 && widen2; @@ -197,5 +200,5 @@ if ( data2.allowWidening != widen2 ) { data2.allowWidening = widen2; - bindings = bindings->set( root, data2 ); + bindings = bindings->set( merged.first, data2 ); } else if ( merged.first == class1.get_root() ) { bindings = bindings->set( merged.first, data2 ); @@ -249,5 +252,5 @@ // filter overlapping classes out of existing environment // (this is a very shady assumption, but has worked for a long time...) - interned_string root = classes->find_or_default( v, not_found ); + interned_string root = classes->find_or_default( var, not_found ); if ( root != not_found ) { classes = classes->remove_class( root ); @@ -262,11 +265,11 @@ // add variable to class and bindings classes = classes->add( var ); - bindings = bindings->set( var, BoundType{ p.second->clone, false, data } ); + bindings = bindings->set( var, BoundType{ p.second->clone(), false, data } ); } } void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const { - bindings->apply_to_all([classes, &sub]( interned_string root, const BoundType& bound ){ - classes->apply_to_class(root, [&]( interned_string var ) { + bindings->for_each([&]( interned_string root, const BoundType& bound ){ + classes->for_class(root, [&]( interned_string var ) { if ( bound.type ) { sub.add( var, bound.type ); @@ -282,11 +285,11 @@ void TypeEnvironment::print( std::ostream &os, Indenter indent ) const { - bindings->apply_to_all([classes,&]( interned_string root, const BoundType& bound ) { + bindings->for_each([&]( interned_string root, const BoundType& bound ) { os << "( "; - classes->apply_to_class( root, [&os]( interned_string var ) { os << var << " "; } ); + classes->for_class( root, [&os]( interned_string var ) { os << var << " "; } ); os << ")"; if ( bound.type ) { os << " -> "; - type->print( os, indent+1 ); + bound.type->print( os, indent+1 ); } if ( ! bound.allowWidening ) { @@ -298,8 +301,8 @@ void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) { - o.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) { + o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) { // add members of new class interned_string new_root{nullptr}; - o.classes->apply_to_class( root, [this,&new_root]( interned_string var ) { + o.classes->for_class( root, [this,&new_root]( interned_string var ) { classes = classes->add( var ); new_root = new_root ? mergeClasses( new_root, var ).first : var; @@ -311,6 +314,6 @@ void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { - bindings->apply_to_all( [classes,&openVars]( interned_string root, const BoundType& bound ) { - classes->apply_to_class( root, [&openVars,&bound]( interned_string var ) { + bindings->for_each( [&]( interned_string root, const BoundType& bound ) { + classes->for_class( root, [&openVars,&bound]( interned_string var ) { openVars[ var ] = bound.data; } ); @@ -319,8 +322,8 @@ void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) { - actualEnv.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) { + actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) { // add members of new class, setting openVars concurrently interned_string new_root{nullptr}; - actualEnv.classes->apply_to_class( root, [&]( interned_string var ) { + actualEnv.classes->for_class( root, [&]( interned_string var ) { classes = classes->add( var ); new_root = new_root ? mergeClasses( new_root, var ).first : var; @@ -334,5 +337,5 @@ void TypeEnvironment::forbidWidening() { - bindings = bindings->apply_to_all([]( const interned_string& k, BoundType& c ) { + bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) { if ( c.allowWidening ) { option ret = c; Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/ResolvExpr/TypeEnvironment.h (revision 5c140301192225f6a3f669eb918000f25962a75e) @@ -189,5 +189,4 @@ /// returned root variable will be valid regardless ClassRef lookup( interned_string var ) const; - ClassRef lookup( const std::string &var ) const { return lookup( var ); } /// Binds a type variable to a type; returns false if fails @@ -202,4 +201,6 @@ public: + TypeEnvironment() : classes{ new Classes{} }, bindings{ new Bindings{} } {} + void add( const Type::ForallList &tyDecls ); void add( const TypeSubstitution & sub ); @@ -224,6 +225,6 @@ void forbidWidening(); - iterator begin() { return { this, bindings->begin() }; } - iterator end() { return { this, bindings->end() }; } + iterator begin() const { return { this, bindings->begin() }; } + iterator end() const { return { this, bindings->end() }; } }; @@ -234,5 +235,5 @@ T vars; if ( ! env->classes->count( root ) ) return vars; - env->classes->apply_to_class( root, [&vars]( interned_string var ) { + env->classes->for_class( root, [&vars]( interned_string var ) { vars.insert( vars.end(), var ); } );