Ayende @ Rahien

Refunds available at head office

Setting out to break the compiler...

I look at a bit of code that dealt with traversing expression an expression tree, using recursion, of course. The edge condition immediate popped to mind was unbounded expression. I decided to see if I can kill the compiler using this. Why? Because.

The first thing to do is to find out how deep a stack we usually need. I wrote this simple test:

class Program
{
	static void Main(string[] args)
	{
		Recursive(1);
	}

	static void Recursive(int i)
	{
		Console.WriteLine(i);
		Recursive(i+1);
	}
}

The last result was: 79994

Obviously this change based on how much stack space each function takes, but it is a good number to go with. I started with this code:

class Program
{
	static void Main(string[] args)
	{
		using(var fw = File.CreateText("text.txt"))
		{
			for (int i = 0; i < 80000; i++)
			{
				fw.Write(" a > "+i +" && ");
				if(i%10==0)
					fw.WriteLine();
			}
		}
	}
}

I then took the file ( slightly over 1 MB in size) and pasted the content to Visual Studio.

That was a mistake:

image

Okay, I can deal with this, let us try a different approach:

class Program
{
	static void Main(string[] args)
	{
		using(var fw = File.CreateText("text.cs"))
		{
			fw.WriteLine("public class Program {");
			fw.WriteLine("	static void Main(string[] args) {");
			fw.WriteLine("		var a = -1;");
			fw.Write    ("		var test = ");
			for (int i = 0; i < 80000; i++)
			{
				fw.Write(" a > "+i +" && ");
				if(i%10==0)
					fw.WriteLine();
			}
			fw.WriteLine(" a < 0;");
			fw.WriteLine("System.Console.WriteLine(test);");
			fw.WriteLine("	}");
			fw.WriteLine("}");

		}
	}
}

Trying to compile that produces:

fatal error CS1647: An expression is too long or complex to compile near ''

The help for CS1647 is:

There was a stack overflow in the compiler processing your code. To resolve this error, simplify your code. If your code is valid, contact Product Support.

The is valid, I guess, just not really reasonable. What is scary is that this is something that was added for 2.0, so at the 1.0 days, someone actually run into this issue.

Some experimentation showed that the C# compiler can handle expressions composed of 23,553 nodes. Now it is the time to get to the next stage, now the code is this:

class Program
{
	static void Main(string[] args)
	{
		using(var fw = File.CreateText("text.cs"))
		{
			fw.WriteLine("using System;");
			fw.WriteLine("using System.Linq.Expressions;");
			fw.WriteLine("public class Program {");
			fw.WriteLine("	static void Main(string[] args) {");
			fw.Write    ("		Expression<Predicate<int>> test = (a) => ");
			for (int i = 0; i < 11700; i++)
			{
				fw.Write(" a > "+i +" && ");
				if(i%10==0)
					fw.WriteLine();
			}
			fw.WriteLine(" a < 0;");
			fw.WriteLine("System.Console.WriteLine(test);");
			fw.WriteLine("	}");
			fw.WriteLine("}");

		}
	}
}

Note that I had to dramatically simplify the expression. Before it handled 23 thousands and change, but now it chokes on merely 12 thousands.

What is really surprising is that after compiling the code, it is running and seems to do the expected thing. Amazing.

Anyway, here is a completely useless post, but now I know that the C# compiler has well defined behavior for stack overflows. :-)

Comments

Avish
08/15/2008 11:52 PM by
Avish

Yay! The C# compiler did the Right Thing once again!

Ayende Rahien
08/16/2008 12:06 AM by
Ayende Rahien

Avish,

But booc doesn't handle this scenario

Comments have been closed on this topic.