Practice thinking like a compiler tester, part two


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?

Comments (5)

  1. Steve says:

    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

  2. Pascal says:

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

  3. Jon Skeet says:

    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

  4. Eric Lippert says:

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

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

Skip to main content