Practice thinking like a compiler tester, part two

Practice thinking like a compiler tester, part two

Rate This
  • Comments 5

Reader RichM found the same solution to the puzzle I posed yesterday that I did:

public class V : S.T {}
public class S {
    public class T{}
}

The control flow of the emitter from the start to the point of the bug goes like this:

Emit(V)
    Emit (S.T) // V base class
        Emit(null) // S.T base class
        Emit(S) // S.T outer class
            Emit(null) // S base class
            Emit(null) // S outer class
            ReallyEmit(S)
            S.emitted = true
            Emit(S.T) // S's first inner class
                Emit(S) // S.T's outer class.
                    // Take the early out because S.emitted is true
                ReallyEmit(S.T)
                S.T.emitted = true
                // T has no inner classes, so return
            // S has no more inner classes, so return
        ReallyEmit(S.T) // oops, we already did this. Bug!

Of course this was not what the emitting code actually looked like. What it actually looked like was something like:

void Emit(Class c)
{
    if (c == null || c.Emitted) return; // don’t emit twice!
    Emit(c.BaseClass);
    Emit(c.OuterClass);
    // If somehow Emit was called on this class before our outer class, then
    // we just caused ourselves to be emitted when we emitted the outer class.
    // (The outer class emits its inner classes, ie, the current
    // class, before it returns.)
    // If we are already emitted then we have no more work to do.
    if (c.Emitted) {
        Debug.Assert(c.OuterClass != null && c.OuterClass.Emitted);
        return;
    }
    ReallyEmit(c); 
    c.Emitted = true;
    foreach(Class i in c.InnerClasses)
        Emit(i);
}

This algorithm is correct. However, the comment and the assertion are not correct. (This is why I was looking at this code in the first place, because the assertion was firing. I fixed it by updating the comment and removing the assertion.)

Can you find a legal set of C# classes which are correctly emitted but cause the assertion to fire?

  • class A : B {}

    class B { class C : A {} }

    Emit(A)

     Emit(B) // base

       Emit(null) // base

       Emit(null) // outer

       ReallyEmit(B)

       B.Emitted = true

       Emit(B.C) // inner

         Emit(A) // base

           Emit(B) // base, returns immediately

           Emit(null) // outer

           ReallyEmit(A) // !!! uh-oh

           A.Emitted = true

         Emit(B) // outer, returns immediately

         ReallyEmit(B.C)

         B.C.Emitted = true

     Emit(null) // outer

     Debug.Assert(A.OuterClass != null && ...) // assertion failure

  • I wrote a small vb.net console app to answer your puzzle and test your problem.

  • Steve's example seems to be correct to me. Presumably you *could* put in an assertion:

    Debug.Assert( (c.OuterClass != null && c.OuterClass.Emitted)

                         || (c.BaseClass != null && c.BaseClass.Emitted));

    In other words "Either our base class, or our outer class, caused us to be emitted just now."

    I'm not sure how useful it would be as an assertion though.

    Jon

  • Steve is correct, yes.  And yes, the assertion is useless.  I simply removed it entirely rather than trying to replace it with something else.

  • Yesterday I posed a slightly harder version of the puzzle I posted the day before . Reader Steve found

Page 1 of 1 (5 items)