Question about short-circuit evaluation in C++

[ghantauke]

Consider the following line of code.

if ( a || b || c )
//other bits don't matter 

My question is, if a is true, would the compiler evaluate the value of b (and c)?
I know for sure that if it had just been

if ( a || b )

and if a is true, the compiler wouldn't evaluate the value of b. But in case of three or more arguments, is the same?


I guess another way of putting the question is, does the compiler know in advance that there's only logical ORs in the conditional statement? (because if it did, it'd skip evaluation of the rest of the conditional statment as soon as one of the operand evaluates to true) Or does the compiler only know what the next logical operation is and if the next operand is the last argument.

[vlad from moscow]

From the point of view of the compiler the expression looks the following way


if ( ( a || b ) || c )

So it tries to eavluate the left operand ( a || b ). If a is true then the left operand ( a || b ) is also true and the whole expression ( a || b ) || c is also is true. So operands b and c are not checked whether they are true or false.

[andywestken]

if a is true, would the compiler evaluate the value of b (and c)?

No.

As you said, if a is true then the compiler (or rather, the compiiled object code) won't bother to evaluate anything to the right of it.

But these is a gotcha -- this is only the case when you use the built-in operator|| and operator&&. If you override them, then the behaviour changes. See following post for further info.

(Due to the change in behaviour, it is strong recommended you do not overload these operators. Or operator, -- the comma (or seqence) operator.)

To see what's up, you can implement a Boolean class which provided a bool cast overator, but not it's own comparison methods. (see below.)

does the compiler know in advance that there's only logical ORs

You can mix ||s and &&s and short-circuit evaluation still applies. Though not usually as efficently.

Andy

PS See 20 -- "Avoid Overloadinf &&, || or , (comma)" in C++ Coding Standards by Sutter and Alexandrescu

#define DEBUG
#include <iostream>
#include <iomanip>
using namespace std;

class Boolean {
private:
	char m_name;
	bool m_val;

public:
	Boolean(char name) : m_name(name), m_val(false) {
	}

	Boolean(char name, bool val) : m_name(name), m_val(val) {
	}

	Boolean(const Boolean& that) : m_name(that.m_name), m_val(that.m_val) {
	}

	Boolean& operator=(const Boolean& that) {
		m_name = that.m_name;
		m_val  = that.m_val;
		return *this;
	}

	operator bool() const {
#ifdef DEBUG
		cout << "operator bool() for " << m_name << " returns " << m_val << endl;
#endif
		return m_val;
	}
};

int main(){
	cout << boolalpha;

	Boolean a('a', true);
	Boolean b('b', true);
	Boolean c('c', true);

	std::cout << "a || b || c" << endl;
	if ( a || b || c ) {
		std::cout << "as least one of a, b, c is true" << endl;
	} else {
		std::cout << "a, b, c are all false" << endl;
	}
	std::cout << endl;

	std::cout << "a && b && c" << endl;
	if ( a && b && c ) {
		std::cout << "all a, b, c are true" << endl;
	} else {
		std::cout << "as least one of a, b, c is false" << endl;
	}
	std::cout << endl;

	return 0;
}

Results (for built-in operator|| and operator&&):

a || b || c
operator bool() for a returns true
as least one of a, b, c is true

a && b && c
operator bool() for a returns true
operator bool() for b returns true
operator bool() for c returns true
all a, b, c are true

As you can see, in the first, || case only a is asked what it's value is. Whereas in the latter, && case, all Boolean variables are asked to give their value.

[andywestken]

Same code modified to use overridden operator|| and operator&& (even though it's really a bad idea...)

As you can see, short circuit evaluation is not used with the custom operator|| and operator&&.

Andy

Results (overloaded operator|| and operator&&): here the values with name 'n' are the temporary Booleans returned by operator|| and operator&&.

a || b || c
  getVal for a returns true
  getName for b returns b
  getName for a returns a
operator||() with a and b returns true
  getVal for n returns true
  getName for c returns c
  getName for n returns n
operator||() with n and c returns true
operator bool() for n returns true
as least one of a, b, c is true

a && b && c
  getVal for a returns true
  getVal for b returns true
  getName for b returns b
  getName for a returns a
operator&&() with a and b returns true
  getVal for n returns true
  getVal for c returns true
  getName for c returns c
  getName for n returns n
operator&&() with n and c returns true
operator bool() for n returns true
all a, b, c are true

#define DEBUG
#define USE_OVERLOADED_OPERATORS
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

// order of val and name swapped so can handle anon/no-name ('n')
// Boolean temporaries created when a bool value is passed to
// Boolean overloads of operator|| an operator&&
// name changed from char to string for related reasons.
class Boolean {
private:
	bool m_val;
	char m_name;

public:
	Boolean(bool val, char name = 'n') : m_val(val), m_name(name) {
	}

	Boolean(char name) :  m_val(false), m_name(name) {
	}

	Boolean(const Boolean& that) : m_val(that.m_val), m_name(that.m_name) {
	}

	Boolean& operator=(const Boolean& that) {
		m_val  = that.m_val;
		m_name = that.m_name;
		return *this;
	}

	bool getVal() const {
#ifdef DEBUG
		cout << "  getVal for " << m_name << " returns " << m_val << endl;
#endif
		return m_val;
	}

	char getName() const {
#ifdef DEBUG
		cout << "  getName for " << m_name << " returns " << m_name << endl;
#endif
		return m_name;
	}

	operator bool() const {
#ifdef DEBUG
		cout << "operator bool() for " << m_name << " returns " << m_val << endl;
#endif
		return m_val;
	}
};

#ifdef USE_OVERLOADED_OPERATORS
Boolean operator||(const Boolean& lhs, const Boolean& rhs) {
	bool retVal = lhs.getVal() || rhs.getVal();
#ifdef DEBUG
	cout << "operator||() with " << lhs.getName() << " and " << rhs.getName()
		 << " returns " << retVal << endl;
#endif
	return retVal;
}

Boolean operator&&(const Boolean& lhs, const Boolean& rhs) {
	bool retVal = lhs.getVal() && rhs.getVal();
#ifdef DEBUG
	cout << "operator&&() with " << lhs.getName() << " and " << rhs.getName()
		 << " returns " << retVal << endl;
#endif
	return retVal;
}
#endif

int main(){
	cout << boolalpha;

	Boolean a(true, 'a');
	Boolean b(true, 'b');
	Boolean c(true, 'c');

	std::cout << "a || b || c" << endl;
	if ( a || b || c ) {
		std::cout << "as least one of a, b, c is true" << endl;
	} else {
		std::cout << "a, b, c are all false" << endl;
	}
	std::cout << endl;

	std::cout << "a && b && c" << endl;
	if ( a && b && c ) {
		std::cout << "all a, b, c are true" << endl;
	} else {
		std::cout << "as least one of a, b, c is false" << endl;
	}
	std::cout << endl;

	return 0;
}

And this code

	std::cout << "a || ((a && b) || (b && c) || (c && a))" << endl;
	if ( a || ((a && b) || (b && c) || (c && a)) ) {
		std::cout << "whatever it is is true" << endl;
	} else {
		std::cout << "whatever it is is false" << endl;
	}
	std::cout << endl;

produces this output for the built-in operators

a || ((a && b) || (b && c) || (c && a))
operator bool() for a returns true
whatever it is is true

but this for the overloaded ones

a || ((a && b) || (b && c) || (c && a))
  getVal for c returns true
  getVal for a returns true
  getName for a returns a
  getName for c returns c
operator&&() with c and a returns true
  getVal for b returns true
  getVal for c returns true
  getName for c returns c
  getName for b returns b
operator&&() with b and c returns true
  getVal for a returns true
  getVal for b returns true
  getName for b returns b
  getName for a returns a
operator&&() with a and b returns true
  getVal for n returns true
  getName for n returns n
  getName for n returns n
operator||() with n and n returns true
  getVal for n returns true
  getName for n returns n
  getName for n returns n
operator||() with n and n returns true
  getVal for a returns true
  getName for n returns n
  getName for a returns a
operator||() with a and n returns true
operator bool() for n returns true
whatever it is is true

[JLBorges]

> does the compiler know in advance that there's only logical ORs in the conditional statement?
> Or does the compiler only know what the next logical operation is

1. The compiler parses the full expression, taking into account operator precedence and associativity.

2. Order of evaluation of sub-expressions in the full expression is governed by the 'sequenced-before rules' specified in the standard.
http://en.cppreference.com/w/cpp/language/eval_order

For the built-in && and || operators, rule 6) is the relevant one.

3. The operands of && and || are evaluated only to the extent that is necessary (' short-circuit evaluation').

#include <iostream>

int main()
{
    static const auto a = [] ()->bool { return std::cout << 'A' ; } ;
    static const auto b = [] ()->bool { return std::cout << 'B' ; } ;
    static const auto c = [] ()->bool { return std::cout << 'C' ; } ;
    static const auto newline = [] { std::cout << '\n' ; } ;

    ( a() || b() || c() ) ; newline() ; // A
    ( !a() || b() || c() ) ; newline() ; // AB
    ( !a() || !b() || c() ) ; newline() ; // ABC
    newline() ;

    ( a() && b() && c() ) ; newline() ; // ABC
    ( a() && !b() && c() ) ; newline() ; // AB
    ( !a() && b() && c() ) ; newline() ; // A
    newline() ;

    // && has higher precedence; in x || y&&z, x is sequenced before y&&z
    ( a() || b() && c() ) ; newline() ; // A
    ( !a() || b() && c() ) ; newline() ; // ABC
    ( !a() || !b() && c() ) ; newline() ; // AB
    newline() ;

    // && has higher precedence; in x&&y || z, x&&y is sequenced before z
    ( a() && b() || c() ) ; newline() ; // AB
    ( !a() && b() || c() ) ; newline() ; // AC
    ( a() && !b() || c() ) ; newline() ; // ABC
}

http://ideone.com/gYGfQa