Spot the bug #2 (Code)

Yesterday we stumbled some odd behavior. Totally logical and well defined, but still odd.

I reduced the classes to it’s essentials. Finder is a base class among other things assuring it’s implementor can rely on being called only once per instance.

The particular implementation uses member variables to detect circles in a tree.

Can you spot the problem? Can you tell me how to solve it?

(Update 12.01.2011: While anonymizing I had introduced another bug. Fixed now.)

public abstract class Finder
{
    private bool _used;
    public IEnumerable<int> GetIds()
    {
        if (_used)
            throw new NotSupportedException("Please do not use twice!");

        _used = true;

        return getIds();
    }

    protected abstract IEnumerable<int> getIds();
}

public class FlatHierarchyIdsFinder : Finder
{
    List<int> _visited = new List<int>();
    protected override IEnumerable<int> getIds()
    {
        if (_visited.Contains(1))
            throw new ApplicationException("Cycle detected!");

        _visited.Add(1);
        yield return 1;
    }
}

It might help you to read this post: Behind the scenes of the C# yield-keyword

Advertisements

22 thoughts on “Spot the bug #2 (Code)

  1. mhm only took a quick look onto this…..

    however…doesn´t that result in the NotSupportedException everytime you initialise the class?

    _used is true by default…..

    well…

  2. When changing “yield return 1;” into “return _visited”;
    it seems to work and should result in the same ienumerable list.

    However, as far as i understand the whole thing, the problem is the yield statement itself.

    Everytime you access the list, due to the yield statement starting all over again, the function tries to add the “1” to the list and runs into the ApplicationException.

  3. How about this – “Cycle detected” exception will never fire because the other “Please do not use twice” exception will fire first on the second use of the GetIds call and the cycling will be not detected?

    Solution – there are probably many, but if the base class constraint could not be removed, it should at least be possible to toggle it off in FlatHierarchyIdsFinder. For example, by setting _used to false in FlatHierarchyIdsFinder.getIds(). Ugly and raises complexity? Yes!. Usable? – It depends.

    • @karu: I manage to trigger Cycle detected. But not because there is a cycle, but because I can run FlatHierarchyIdsFinder.getIds() twice somehow – even if there is a protection in the base class.

  4. Hi Lars,

    ok fine – look better. I do not know if I have understood your requirements correctly, but yes sure yield return is a partial execution statement. Do you want to protect multiple partial execution in your base class?

    public IEnumerable GetIds()
    {
    var used = false;
    foreach (var id in getIds())
    {
    if (used)
    throw new NotSupportedException(“Please do not use twice!”);
    used = true;
    yield return id;
    }
    }

    • Actually i want both protection for retrieving the enumerator, and then only allow one enumeration of it.

      Your code would also not let through more than one item – i over-simplified, maybe.

  5. Mhh, my description for yield return is “partial function excution” or simple “state machine”. I think it’s a better name for yield return statement. What do you mean?

    Cheers, Mike

  6. bool _used;
    public IEnumerable GetIds()
    {
    if (_used)
    throw new NotSupportedException(“Please do not use twice!”);

    var enumerator = getIds().GetEnumerator();
    while (enumerator.MoveNext())
    {
    yield return enumerator.Current;
    _used = true;
    }
    }

    Cheers, Mike

  7. Mhh, now you can simplify in one base class method.

    bool _used;
    readonly List _visited = new List();
    public IEnumerable GetIds()
    {
    if (_used)
    throw new NotSupportedException(“Please do not use twice!”);

    var enumerator = getIds().GetEnumerator();
    while (enumerator.MoveNext())
    {
    if (_visited.Contains(1))
    throw new ApplicationException(“Cycle detected!”);
    _visited.Add(enumerator.Current);
    yield return enumerator.Current;
    _used = true;
    }
    }

    Cheers, Mike

  8. The question is…

    What is this used for? What do you want to do with the resulting list?

    Simply get the Count? or actually iterate through the items and do something with a given id?

  9. Hey Mike,

    but now you are mixing responsibilities of the base class and the derived class.
    The base class must ensure that for all possible derived classes the enumerator can only be retrieved once. Additionally, the base class must ensure that the elements can only be iterated once.

    Sven-Torben

    • I don’t agree.
      Imho LSP is related to interoperability of types in a hierarchy. It states that a provable property about objects (instances of classes) of a given type (class) T should be true for all objects of a given subtype (derived class) S of T.

      It only holds for objects of types, not for types. With respect of LSP, you cannot change the base class (as you stated: “now you can simplify in one base class method”), because this would induce a different type hierarchy.

      Regards,

      Sven-Torben

  10. I think it’s better to solve the requirement with a functional approach – with a extention method for example – instead of OO. You have to many maintenance and design troubles with OO with this requirement.

    Cheers, Mike

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s