[Issue 12537] New: Templatizing opEquals results in infinite recursion in the compiler

Mon Apr 7 04:40:38 PDT 2014

https://d.puremagic.com/issues/show_bug.cgi?id=12537

           Summary: Templatizing opEquals results in infinite recursion in
                    the compiler
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: jmdavisProg at gmx.com

--- Comment #0 from Jonathan M Davis <jmdavisProg at gmx.com> 2014-04-07 04:40:32 PDT ---
I'm currently trying to templatize the free function opEquals in druntime for
issue# 9769, and a compiler bug is blocking me.

This piece of code (taken from dmd's test suite) triggers the problem:

----------------
struct T11875x(C)
{
    C c;
}
class D11875a { D11875b c; alias c this; }
class D11875b { D11875a c; alias c this; }
static assert( is(T11875x!D11875a == T11875x!D, D) && is(D == D11875a));

void main()
{
}
----------------

If all you do is templatize opEquals in object_.d and copy it to object.di
(since currently, object.di holds only the signatures for opEquals), then the
compiler never stops (or if it does, it takes a very long time). i.e.

----------------
bool opEquals()(const Object lhs, const Object rhs)
{
    // A hack for the moment.
    return opEquals(cast()lhs, cast()rhs);
}

bool opEquals()(Object lhs, Object rhs)
{
    // If aliased to the same object or both null => equal
    if (lhs is rhs) return true;

    // If either is null => non-equal
    if (lhs is null || rhs is null) return false;

    // If same exact type => one call to method opEquals
    if (typeid(lhs) is typeid(rhs) || typeid(lhs).opEquals(typeid(rhs)))
        return lhs.opEquals(rhs);

    // General case => symmetric calls to method opEquals
    return lhs.opEquals(rhs) && rhs.opEquals(lhs);
}
----------------

So, all that was added was the () after opEquals. Running in gdb, it looks like
the stack trace goes on pretty much forever. However, the first portion looks
like

#0  0x00000000004284dc in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#1  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#2  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#3  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#4  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#5  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#6  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#7  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#8  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#9  0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#10 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#11 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#12 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#13 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#14 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#15 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#16 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#17 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#18 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#19 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
#20 0x00000000004284e7 in Expression_optimize(Expression*, int,
bool)::OptimizeVisitor::visit(DotVarExp*) ()
...

But for some reason, the stack doesn't actually get blown (probably due to a
tail recursion optimization, but I don't know).

If I use what is currently my actual solution

----------------
/************************
 * Returns true if lhs and rhs are equal.
 */
bool opEquals(T, U)(T lhs, U rhs)
    if (is(T == class) && is(U == class) &&
        is(typeof(lhs.opEquals(rhs)) == bool) &&
        is(typeof(rhs.opEquals(lhs)) == bool))
{
    static if (is(T : U) || is(U : T))
    {
        // If aliased to the same object or both null => equal
        if (lhs is rhs) return true;
    }

    // If either is null => non-equal
    if (lhs is null || rhs is null) return false;

    // If same exact type => one call to method opEquals
    // General case => symmetric calls to method opEquals
    return lhs.opEquals(rhs) &&
           (typeid(lhs) is typeid(lhs) || typeid(lhs).opEquals(typeid(rhs)) ||
rhs.opEquals(lhs));
}

bool opEquals(T, U)(const T lhs, const U rhs)
    if (is(T == class) && is(U == class) &&
        !is(typeof(lhs.opEquals(rhs)) == bool) &&
        !is(typeof(rhs.opEquals(lhs)) == bool))
{
    // FIXME. This is a hack.
    // We shouldn't need to cast away const, and if either lhs' or rhs'
opEquals
    // mutates either object, it's undefined behavior. But before we can remove
    // this, we need to make it so that TypeInfo and friends have the corect
    // definitions for opEquals so that they work with the other overload. And
    // any user code using const objects but which doesn't define opEquals such
    // that it works with const with the other overload will also break once
    // this is removed. So, we need to get rid of this, but we need to be
    // careful about how and when we do it.
    return opEquals(cast()lhs, cast()rhs);
}

// This screwy overload is here to make typedef work, since while it _has_ been
// deprecated for a while now, it has yet to be removed, and typedefs won't
// work with the other two overloads, because bizarrely enough, if T is a
typedefed
// class, then is(T == class) is false (which has got to wreak havoc with
generic
// code).
bool opEquals(T, U)(const T lhs, const U rhs)
    if (!is(T == class) && !is(U == class) &&
        !is(T == struct) && !is(U == struct) &&
        is(T : Object) && is(U : Object))
{
    return opEquals(cast(Object)lhs, cast(Object)rhs);
}
----------------

then the stack _does_ get blown, and dmd segfaults. The top of the stack in
that case looks like

#0  0x00000000004cb9b0 in resolvePropertiesX(Scope*, Expression*, Expression*)
()
#1  0x00000000004d6c30 in DotIdExp::semanticX(Scope*) ()
#2  0x00000000004d7015 in DotIdExp::semanticY(Scope*, int) ()
#3  0x00000000004d7baa in DotIdExp::semantic(Scope*) ()
#4  0x00000000004d4b2d in CastExp::semantic(Scope*) ()
#5  0x00000000004bb8b2 in Expression::trySemantic(Scope*) ()
#6  0x00000000004209ee in op_overload(Expression*,
Scope*)::OpOverload::visit(CastExp*) ()
#7  0x0000000000420476 in op_overload(Expression*, Scope*) ()
#8  0x00000000004d4db2 in CastExp::semantic(Scope*) ()
#9  0x00000000004bb8b2 in Expression::trySemantic(Scope*) ()
#10 0x00000000004209ee in op_overload(Expression*,
Scope*)::OpOverload::visit(CastExp*) ()
#11 0x0000000000420476 in op_overload(Expression*, Scope*) ()
#12 0x00000000004d4db2 in CastExp::semantic(Scope*) ()
#13 0x00000000004bb8b2 in Expression::trySemantic(Scope*) ()
#14 0x00000000004209ee in op_overload(Expression*,
Scope*)::OpOverload::visit(CastExp*) ()
#15 0x0000000000420476 in op_overload(Expression*, Scope*) ()
#16 0x00000000004d4db2 in CastExp::semantic(Scope*) ()
#17 0x00000000004bb8b2 in Expression::trySemantic(Scope*) ()
#18 0x00000000004209ee in op_overload(Expression*,
Scope*)::OpOverload::visit(CastExp*) ()
#19 0x0000000000420476 in op_overload(Expression*, Scope*) ()
#20 0x00000000004d4db2 in CastExp::semantic(Scope*) ()
#21 0x00000000004bb8b2 in Expression::trySemantic(Scope*) ()
#22 0x00000000004209ee in op_overload(Expression*,
Scope*)::OpOverload::visit(CastExp*) ()

Given that the piece of code that triggers this doesn't actually use opEquals
as far as I can tell (it uses == for is, but that's checking types, not
comparing actual objects), I have no idea why templatizing opEquals would
trigger it, but it does.

It's certainly possible that there's a bug in my changes, but simply
templatizing opEquals shouldn't result in the compiler hitting infinite
recursion, so I'm sure that there's a compiler bug here, and until it's fixed,
I can't get my changes working.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------