Introducing loops into dependence graph

[dbarowy]

On one of our benchmarks, I am finding a formula loop. My first thought was that we made a mistake in one of two places 1) the parser or 2) the tree construct code. A parser error could introduce a loop if an incorrect parse caused a dereference to the wrong TreeNode. Alternately, the graph constructor could have a bug somewhere that also introduces a loop. This manifests itself with an infinite loop when trying to propagate tree weights.

I wrote a simple function in AnalysisData that finds loops by recursive descent. If it encounters the same TreeNode twice while descending, then you know it's a loop. For the spreadsheet AAAsolution.xls (in Set1), I get the following looping path:

D149 -> D147 D147 -> D136 D136 -> D127 D127 -> D73 D73 -> D68 D68 -> D57 D57 -> D55 D55 -> D48 D48 -> D46 D46 -> D82 D82 -> D149

So, just to rule out a bug in the loop detector, I manually verified this. There really appears to be a loop here. The loop appears on the worksheet titled "Financial Model". Can you double-check this?

I've modified the code to throw a ContainsLoop exception. If there really are loops (which I'm guessing that Excel just didn't catch), then we just can't analyze the spreadsheet.

So, just to be clear: this doesn't appear to be a bug in our code. Once you verify the above loop, we can close this ticket.

[dgochev]

That's correct. I checked it, and this is a loop in the spreadsheet. I'm surprised that Excel doesn't complain about it, but at least our code is not the problem here. Closing.

[jvilk]

After this paper, you guys need to make a "Microsoft Excel: Wat" presentation.

...does Excel refuse to calculate this, or does it actually report something useful?