Ayende @ Rahien

Hi!
My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:

ayende@ayende.com

+972 52-548-6969

, @ Q c

Posts: 10 | Comments: 37

filter by tags archive

Setting out to break the compiler...

time to read 3 min | 548 words

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

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

Ayende Rahien

Avish,

But booc doesn't handle this scenario

Comment preview

Comments have been closed on this topic.

FUTURE POSTS

  1. Production postmortem: The case of the memory eater and high load - 10 hours from now
  2. Production postmortem: The case of the lying configuration file - about one day from now
  3. Production postmortem: The industry at large - 2 days from now
  4. The insidious cost of allocations - 3 days from now
  5. Find the bug: The concurrent memory buster - 4 days from now

And 4 more posts are pending...

There are posts all the way to Sep 10, 2015

RECENT SERIES

  1. Find the bug (5):
    20 Apr 2011 - Why do I get a Null Reference Exception?
  2. Production postmortem (10):
    14 Aug 2015 - The case of the man in the middle
  3. What is new in RavenDB 3.5 (7):
    12 Aug 2015 - Monitoring support
  4. Career planning (6):
    24 Jul 2015 - The immortal choices aren't
View all series

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats