Stack WTF

Renan

This is in .NET. If you decompile the Stack class (System.Collections.Stack), you'll notice it has a private field called _version.

There is no method nor property which exposes the value of this field. All it does is being incremented whenever you call the stack's Peek, Push and Pop methods if the stack is not empty. Yeah, you read it right. All the three methods start with something like this...

{

if (this.Count == 0) //throw some Exception...

_version++;

}

So, you can't use it, but it's harmless anyway. Right? Well, kinda... Unless someone happens to use the stack 2,147,483,648 times, in which case _version overflows. Since it's a 32-bit signed integer, and that value is one unity greater than the maximum value for Int32.

Alright, so you have to be an ubber-bastard to use a single stack that amount of times. But given the Law of Murphy and the destructive power of some bastard users, I'm never using a stack outside a try block anymore.

Talchas

I think that java has something like that so that it can have Iterators fail if you do any operations while iterating. Does C# have anything similar that could be magically accessing it somehow?

Renan

No. I don't see any other methods using this field, and for any other class to be able to use it, even the ones from the framework, it'd have to be declared as internal instead of private. It's also not using pointers, so I don't see any way this could be read or written from outside.

filthpig

Code Monkey use Stack, no worry about OverflowException.

Code Monkey should change middle name.

In C# neither int objects nor Int32 objects will throw an OverflowException unless the operation is in a checked context (a checked block). The default is unchecked, I assume to be (backwards?) compatible with C and C++.

Since the checked context doesn't survive a method invocation, and there is no checked operator around the increment statements, it overflows silently. This is not a problem, because this field is only used in the inner class StackEnumerator (as assumed correctly by Talchas) and compared for equality, to make sure that the Enumerator becomes invalid when the contents of the stack have changed.

Renan

Thanks for the info on checked and uncheked contexts, that is new to me. I had no idea, but just now I made a quick app to check and it surprised me.

But still, there is no enumerator being used internally. There is no StackEnumerator.

The actual code I saw extracted from the Stack class goes like this:

public virtual object Pop()
{
 if (this._size == 0)
 {
 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
 }
 this._version++;
 object obj2 = this._array[--this._size];
 this._array[this._size] = null;
 return obj2;
}

public virtual void Push(object obj)
{
 if (this._size == this._array.Length)
 {
 object[] destinationArray = new object[2 * this._array.Length];
 Array.Copy(this._array, 0, destinationArray, 0,this._size);
 this._array = destinationArray;
 }
 this._array[this._size++] = obj;
 this._version++;
}

And the only method that actually does something else with _version is Clone, which copies it to the new stack.

public virtual object Clone()
{
 Stack stack = new Stack(this._size);
 stack._size = this._size;
 Array.Copy(this._array, 0, stack._array, 0, this._size);
 stack._version = this._version;
 return stack;
}

So it doesn't use an enumerator internally, and an "outside" enumerator won't be able to touch _version.

j_johnso

There is a StackEnumerator class nested inside of the stack class. Look at the GetEnumerator() method of the Stack.

Inside of the StackEnumerator, there is the following code in several places.

if (this._version != this._stack._version) { throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion")); }

random_garbage

[quote user="Renan "C#" Sousa"]

So, you can't use it, but it's harmless anyway. Right? Well, kinda...
Unless someone happens to use the stack 2,147,483,648 times, in which
case _version overflows. Since it's a 32-bit signed integer, and that
value is one unity greater than the maximum value for Int32.

Alright, so you have to be an ubber-bastard to use a single stack that
amount of times. But given the Law of Murphy and the destructive power
of some bastard users, I'm never using a stack outside a try block
anymore.

[/quote] @j_johnso said:

There is a StackEnumerator class nested inside of the stack class. Look at the GetEnumerator() method of the Stack.
Inside of the StackEnumerator, there is the following code in several places.
if (this._version != this._stack._version)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
}

So The Real WTF is that some BOFH-esque type might perform ~2billion Stack manipulations between successive calls to StackEnumerator.next(), and the Enumerator won't be able to tell?

salandur

no, if your are iterating over the collection the collection must not change. so if there is a change in de collection the iterator is invalid. the version check makes sure that the iterator fails when the collection change

XIU

First of all, all collections do that, its for the exception you get when changing something in a collection while using it with a foreach (or anything that uses GetEnumerator()).

Second, by default it just goes to int.MinValue after int.MaxValue of you have to explicitly wrap it in a checked { }.

dlikhten

I GUESS some microslop "dude" *cought* i mean "guru" decided that they might want to let the users know how many times this class was used. What? Publicly exposed? NOTHING IN MICROSOFT IS PUBLICLY EXPOSED!

BTW do you not see another problem? Every time you call a push/pop/peek you do an extra increment operation for absolutely no good reason, sure its a little bit of cpu time, but why, why, why, why, why?

ShadowWolf

I didn't have any issues doing 4,294,967,298 operations on a stack :)

XIU

@dlikhten said:

I GUESS some microslop "dude" cought i mean "guru" decided that they might want to let the users know how many times this class was used. What? Publicly exposed? NOTHING IN MICROSOFT IS PUBLICLY EXPOSED!
BTW do you not see another problem? Every time you call a push/pop/peek you do an extra increment operation for absolutely no good reason, sure its a little bit of cpu time, but why, why, why, why, why?

Only Pop/Push/Clear do this, ie when you collection is changed.

Stack someStack = new Stack();
someStack.Push("String 1");
someStack.Push("String 2");
someStack.Push("String 3");
foreach (string str in someStack)
{
if (str == "String 2")
someStack.Clear();
}

This will throw an exception because the stack is changed while looping through it and it has no idea what it should do, and how is this checked? With the version :)

@dlikhten said:

I GUESS some microslop "dude" cought i mean "guru" decided that they might want to let the users know how many times this class was used. What? Publicly exposed? NOTHING IN MICROSOFT IS PUBLICLY EXPOSED!
BTW do you not see another problem? Every time you call a push/pop/peek you do an extra increment operation for absolutely no good reason, sure its a little bit of cpu time, but why, why, why, why, why?

Just because you are not smart enough to understand it doesn't mean that they are stupid or sloppy. Read all the replies about the enumerator to understand whey this exists. It is very important and the extra clock cycles won't be noticed.... honestly, do you know how many clock cycles it takes to do a pop or pull as compared to an increment?

dlikhten

@XIU said:

@dlikhten said:
I GUESS some microslop "dude" cought i mean "guru" decided that they might want to let the users know how many times this class was used. What? Publicly exposed? NOTHING IN MICROSOFT IS PUBLICLY EXPOSED!
BTW do you not see another problem? Every time you call a push/pop/peek you do an extra increment operation for absolutely no good reason, sure its a little bit of cpu time, but why, why, why, why, why?

Only Pop/Push/Clear do this, ie when you collection is changed.

Stack someStack = new Stack();
someStack.Push("String 1");
someStack.Push("String 2");
someStack.Push("String 3");
foreach (string str in someStack)
{
if (str == "String 2")
someStack.Clear();
}
This will throw an exception because the stack is changed while looping through it and it has no idea what it should do, and how is this checked? With the version :)

Thinking about it further... I guess a version counter is cheaper than the alternatives of a "listener" pattern, where all iterators are notified. I was wrong...

Renan

... I absolutely hadn't noticed the GetEnumerator method.

I learned two good lessons in this thread. Thank you guys.

XIU

[quote user="Renan "C#" Sousa"]

... I absolutely hadn't noticed the GetEnumerator method.

I learned two good lessons in this thread. Thank you guys.

[/quote]

Damn it, people learn from their mistakes, now this isn't a wtf anymore :P