Prepare syntax tree (ast) to easily perform short circuit operations

Question

What is the best way to prepare a syntax tree containing conditions to allow easy and fast short curcuit usage?

The rules of short circuit in general are very easy:

1. If one component in an and block returns false, the complete block will return false and execution can be exited
2. If one component in an or block returns true, the complete block will return true and execution can be exited

So for example this simple statement will be evaluated to the following syntax tree 1 = 0 and 1 = 1:

       and
    /      \
   =        =
 /  \      /  \
1    0    1    1

In this case it is easy. After executing the first part of the tree (branch), the execution will be exited it only can return false. But if the tree gets more complex, there must be a way to be more efficient. Or is this already the most efficient way?

For example, how does the c# compiler evaluate the syntax tree in this cases?

EDIT

Should I write all conditions in a simple list, and branch to the end if true or false is not possible? So that i have no and and or parts at the end?

Thank you all a lot!

Answer 1

Your definition of short circuiting doesn't quite match that of C# and other languages. In most (presumably all) languages that have short circuiting the behavior depends on the value of the left operand only, that is:

• left && right always evaluates left and only evaluates right if left was true.

• left || right always evaluates left and only evaluates right if left was false.

So the rules of the language guarantee you that the right operand will never be tried first, even if the compiler may think that trying the right operand first would be more efficient. This way you know that list == null || list.IsEmpty() can't ever throw a null pointer exception.

So to answer your question, the compiler won't generate anything more efficient than "evaluate the left operand and then evaluate the right operand only if you have to" because anything else would break the rules of the language.

PS: In theory it would be possible for the compiler to reorder the operands if it can prove that they don't have any side-effects, but to the best of my knowledge that is not done. Either way that would not happen at the AST level.

PPS: The C# compiler does not evaluate the AST, it generates code from it. It's a compiler, not an interpreter.