Bill Sithiro

Every year Microsoft organises a great conference named MIX that is about web design and development. It’s probably better you visit the official site for a better description, as what I want to blog about is the little competition the MIX09 organisers launched last month (December 2008). The idea behind the competition is to create ”something for the web” in Silverlight, WPF browser application or WPF Click Once application in under 10kB of code. As the competition is now over, I thought I would post a blog on my competition entry, CalcLight.

But before I begin, let’s travel back in time to the days of the console and DOS and look at the source code for a spreadsheet written for Turbo Pascal 3. Borland used to release little samples like MicroCalc in their Pascal and C++ development IDE’s. Now, the point of this is to look at the amount of code required to handle a formula. Keep in mind, that there’s is no UI in the MicroCalc sample and you could write a better expression parser now days, but the things that could go wrong in terms of data entry still remain numerous. In fact, to do it properly just a decent parser itself would exceed the 10kB limit. So, how on Earth do you then create a fully functional spreadsheet application with a UI plus all the spreadsheet plumbing in under 10Kb? And the answer is… by taking shortcuts. Enter JavaScript!

When I decided to make CalcLight, my software estimation skills told me that no way I could make it handle formulas plus the UI under the contest’s size limit (although perhaps with just a few more kilobytes it might have been possible). However, I did notice that nothing was stopping me from using JavaScript to handle the expressions. In that case, all I needed to do was simply parse the formula for direct cell values and then simply pass the parsed formula to JavaScript to evaluate. Here’s some sample code to setup usage with JavaScript within Silverlight:

   1: HtmlElement scriptHost=HtmlPage.Document.CreateElement("script");

   2: scriptHost.SetAttribute("type","text/javascript");

   3: scriptHost.SetProperty("text","function Evaluate(exp){try{return eval(exp);}catch(e){return "#VALUE!";}}");

   4: HtmlPage.Document.DocumentElement.AppendChild(scriptHost);

Our Silverlight application is now ready to execute the Evaluate function. But we’re not quite done yet, although this would work nicely for something like this:

   1: HtmlPage.Window.Invoke("Evaluate", "((10 * 3.5) / (234 + 123 + 232.23)) * 2");

However, what we’re hoping to do is also pass cell names instead of just direct values. And these cells may just as well contain other formulas pointing to other cells and so on. Things are getting a little more complicated, but nothing out of hand. The way CalcLight works, every cell is a class. The Cell class contains three methods to help us solve the above problem. Additionally, we have an instance (named Cells) of a static Dictionary<String,Cell> with all our cell instances to assist us:

   1: string[] symb = { "=", "+", "-", "/", "*", "(", ")", ",", "?", ":", "<", ">" };

   2:

   3: string Parse(string x)

   4: {

   5:     x = x.Replace(" ", "");

   6:     var arr = x.Split(symb, StringSplitOptions.RemoveEmptyEntries);

   7:     var d = from i in arr orderby i descending select i;

   8:     foreach(var item in d)

   9:     {

  10:         var v = Regex.Replace(item, "^[A-Z]{1,2}[0-9]{1,3}$", Cell.GetValue(item, this), RegexOptions.None);

  11:         x = x.Replace(item, v);

  12:     }

  13:     return x;

  14: }

  15:

  16: static string GetValue(string cid, Cell cell)

  17: {

  18:     if (Cells.ContainsKey(cid))

  19:     {

  20:         var c = Cells[cid];

  21:         if (c != null)

  22:         {

  23:             if (c != cell)

  24:                 return c.Evaluate(c.Text);

  25:             else

  26:                 return "!CIRCULAR!";

  27:         }

  28:         else

  29:             return cid;

  30:     }

  31:     else

  32:         return cid;

  33: }

  34:

  35: string Evaluate(string x)

  36: {

  37:     if (x.StartsWith("="))

  38:     {

  39:         try

  40:         {

  41:             return HtmlPage.Window.Invoke("Evaluate", Parse(x).Replace("=", "")).ToString();

  42:         }

  43:         catch (Exception)

  44:         {

  45:             return "#VALUE!";

  46:         }

  47:     }

  48:     else

  49:         return x;

  50: }

The entry point of the above snippet is the Evaluate function. We pass a formula to the Evaluate function (e.g. =A1+B1) which in turn calls Parse with the formula and will enter a state of recursion for each cell in the formula until the entire formula(s) are evaluated. Notice, we also check for situations where a cell references itself . This is known as a circular reference. However, there is also the case of one cell reference another that in turn references the first. This is also a circular reference. To make a long story short it results in a stack overflow, something not handled very gracefully in Silverlight and when I first tested for that, it crashed every single browser I checked it with! Luckily, we can fix this easily, and you can use this technique elsewhere as well. But we need to make some slight modifications:

First, we need a static variable to keep count of how many iterations the GetValue method is being called. We’ll just call it ITR for iteration:

   1: static int ITR = 0;

Next, we need to re-initialise it in the exit point (finally clause) of the Evaluate method:

   1: string Evaluate(string x)

   2: {

   3:     if (x.StartsWith("="))

   4:     {

   5:         try

   6:         {

   7:             return HtmlPage.Window.Invoke("Evaluate", Parse(x).Replace("=", "")).ToString();

   8:         }

   9:         catch (Exception)

  10:         {

  11:             return "#VALUE!";

  12:         }

  13:         finally

  14:         {

  15:             ITR = 0;

  16:         }

  17:     }

  18:     else

  19:         return x;

  20: }

Secondly, we’re incrementing the counter every time GetValue is called.

   1: static string GetValue(string cid, Cell cell)

   2: {

   3:     ITR++;

   4:

   5:     if (Cells.ContainsKey(cid))

   6:     {

   7:         var c = Cells[cid];

   8:         if (c != null)

   9:         {

  10:             if (c != cell)

  11:                 return c.Evaluate(c.Text);

  12:             else

  13:                 return "!CIRCULAR!";

  14:         }

  15:         else

  16:             return cid;

  17:     }

  18:     else

  19:         return cid;

  20: }

Now, all we need is a switch that will make sense as an indication that we’re ‘cruising for a bruising’ (stack overflow). We do this in the Parse function and we simply add the following line:

   1: string Parse(string x)

   2: {

   3:     if (ITR > 3000)

   4:     {

   5:         ITR=0;

   6:         return "!OVERFLOW!";

   7:     }

   8:

   9:     x = x.Replace(" ", "");

  10:     var arr = x.Split(symb, StringSplitOptions.RemoveEmptyEntries);

  11:     var d = from i in arr orderby i descending select i;

  12:     foreach(var item in d)

  13:     {

  14:         var v = Regex.Replace(item,"^[A-Z]{1,2}[0-9]{1,3}$", Cell.GetValue(item, this), RegexOptions.None);

  15:         x = x.Replace(item, v);

  16:     }

  17:     return x;

  18: }

Basically, if our counter has exceeded 3000 iterations it’s time to call it quits and return an error. Now, 3000 is just a guess, it could work just as well with 5 or maybe 10 thousand iterations. I’m not sure, I haven’t really tested it to that detail, but do note however that the larger this number is the larger the amount of formulas you can resolve i.e. recursion deep resolving (e.g. cell 1 points to cell 2, cell 2 points to cell 3 and so on). We want to keep at something practical and remember our primary goal is trying to catch circular references with the less amount of code as possible.

The Parse method is very interesting as this is where we do the actual formula parsing. This is how it works, we give it an expression and we strip out all the whitespace. Secondly, we split the formula from symbols and are left with an array of strings. Now these strings, maybe cell names, maybe number values, maybe function names, or simply text, but all we care about is cell names. We apply a regular expression pattern to test for exactly that, and call GetValue to evaluate the cell’s value. But what’s that LINQ statement you might ask? Why is it important to sort the array in descending order? This catches formulas where we have something like this: =B1+B11. This helps our Regex pattern matching distinguish from B1 and B11 by first evaluating the later cell first.

And that’s about it regarding CalcLight’s formula parsing shortcut. Use JavaScript in your SilverLight projects whenever you can; it’s easier to add functionality and avoid caching problems in browsers with .xap’s. However, also note Silverlight features like Regular Expressions and LINQ that made the formula parsing not only a breeze but in a fraction of code! Compare it with the old-school Pascal source code shown above to appreciate today’s modern coding features.

Finally, one feature I didn’t manage to get in the size limit, sadly, is range cells (e.g. A1:C10) but hey, it’s time to worry about the UI now. And no JavaScript is going to help us pull off the next stunt of visualising 10 thousand cells!

Launch CalcLight here

Thank You,

-Bill Sithiro