Is Stream.findFirst() Short-circuited?

So, the assumption is: if I use findFirst on a stream, none of the items in the stream after the first match are evaluated.

I assumed that it was, and it is, but it's always nice to see this verified in a simple test.

  private List<String> list = new ArrayList<>();

  private boolean add(String message, boolean returnValue) {
    list.add(message);
    return returnValue;
  }

  public boolean check() {
    List<Supplier<Boolean>> checks = new ArrayList<>();
    checks.add(super::onLeave);
    checks.add(() -> {
      list.add("First expression");
      return true;
    });
    checks.add(() -> {
      list.add("Second expression");
      return true;
    });
    checks.add(() -> {
      list.add("Third expression");
      return false;
    });
    checks.add(() -> {
      list.add("Fourth expression");
      return true;
    });
    checks.add(() -> {
      list.add("Fifth expression");
      return true;
    });
    checks.add(() -> {
      list.add("Sixth expression");
      return false;
    });
    return checks.stream()
        .filter(t -> t.get().equals(Boolean.FALSE))
        .findFirst()
        .isEmpty();
  }

  @Test
  public void testShortCircuit() {
    assertThat(check()).isFalse();
    assertThat(list)
        .containsExactly("First expression", "Second expression", "Third expression");
  }

As this test passes, it seems that way.

In the very beginning it took some time for me to wrap my head around it, but the operations you define on a stream (.map, .filter, etc.) are not all processed on every item in the stream.

All operations are processed on the first item of the stream, then on the second item of the stream. From this it follows, that a .findFirst() operation will immediately terminate operations if it finds one and the rest of the stream will be ignored.

Refactoring

So, I saw some code that I didn't like, and I decided to refactor it.

The code was thusly.

public boolean onLeave() {
    boolean valid = super.onLeave();
    Account account = database.getAccount();
    ShoppingList shoppingList = database.getShoppinglist(account);
    if (valid) {
      valid = !shoppingList.isEmpty();
    }
    if (valid) {
      valid = !blockedAccounts.contains(account);
    }
    if (valid) {
      String country = account.getPerson().country();
      valid = webshop.alsoShipsTo(country);
    }
    if (valid) {
      valid = account.hasCreditcardAttached() ||
          account.hasPrepaidcardAttached() ||
          account.hasCash();
    }
    return valid;
  }

And I thought to myself, it's really just a list of expressions, where each one is evaluated until you find one that evaluates to false, and then you stop.

So, that's basically a Stream where you filter out all the "false" values, and get the first one.

So, I decided to refactor it just like that.

public boolean onLeave() {
    Account account = database.getAccount();
    ShoppingList shoppingList = database.getShoppinglist(account);

    List<Supplier<Boolean>> checks = new ArrayList<>();
    checks.add(super::onLeave);
    checks.add(() -> !shoppingList.isEmpty());
    checks.add(() -> !blockedAccounts.contains(account));
    checks.add(
        () -> {
          String country = account.getPerson().country();
          return webshop.alsoShipsTo(country);
        });
    checks.add(() -> account.hasCreditcardAttached() ||
        account.hasPrepaidcardAttached() ||
        account.hasCash());

    return checks.stream()
        .filter(t -> t.get().equals(Boolean.FALSE))
        .findFirst()
        .isEmpty();
  }

I proudly showed this to my colleagues, and they immediately shook their heads in disgust.

Apparently, in my eagerness to use Lambdas and Streams and all that cool stuff, what I really had done is recreated the short-circuit version of an If statement in Streams.

I find myself turning to Lambdas and Streams when in reality these are not needed, and my eventual solution works fine without them.

So, rewriting this as a short-circuited IF statement looks like this:

public boolean onLeave() {
    Account account = database.getAccount();
    ShoppingList shoppingList = database.getShoppinglist(account);

    return super.onLeave() &&
        !shoppingList.isEmpty() &&
        !blockedAccounts.contains(account) &&
        webshop.alsoShipsTo(account.getPerson().country()) &&
        (account.hasCreditcardAttached() ||
            account.hasPrepaidcardAttached() ||
            account.hasCash());
  }

Granted, a few more and my IntelliJ will start to complain about the number of expressions in the if statement, and it's possible to clean it up a little by creating separate methods for some of the expressions. But I feel it looks fine.

So, in conclusion, just because you know something cool and shiny, it's no reason to try and use it everywhere!

It is a corrolary that in order to properly use something, you must have some knowledge or experience of when and where it's best to be used.

On Short Circuit Evaluation

I found the following quote on the Wikipedia page on Short-circuit evaluation¹.

The quote is from Edger W. Dijkstra²

The conditional connectives — "cand" and "cor" for short — are ... less innocent than they might seem at first sight. For instance, cor does not distribute over cand: compare

(A cand B) cor C with (A cor C) cand (B cor C);

in the case ¬A ∧ C , the second expression requires B to be defined, the first one does not. Because the conditional connectives thus complicate the formal reasoning about programs, they are better avoided.

— Edsger W. Dijkstra[2]

“There be a lot of long words in there; and I'm naught but a humble pirate³.”

Let's break it down.

(A && B) || C

(A || C) && (B || C)

Possibilities are:

A	B	C	(A && B) || C	(A || C) && (B || C)
false	false	false	false	false
true	false	false	false	false
false	true	false	false	false
true	true	false	true	true
false	false	true	true	true
true	false	true	true	true
false	true	true	true	true
true	true	true	true	true

So, for A = false and C = true,

(false && B) || true -> does not need to evaluate B

(false || true) && (B || true) -> does need to evaluate B.

And this while (A && B) || C == (A || C) && (B || C) holds true.

So that's interesting.

But I fear Edger W. Dijkstra may have been needlessly dogmatic here.

References

[1] Wikipedia - Short-circuit evaluation

https://en.wikipedia.org/wiki/Short-circuit_evaluation

[2] Texas Univerity - Edger W. Dijkstra

http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1009.PDF

[3] Wikiquote - Pirates of the Caribbean: The Curse of the Black Pearl

https://en.wikiquote.org/wiki/Pirates_of_the_Caribbean:_The_Curse_of_the_Black_Pearl

Making Mistakes In JPQL

Well, crap. My boss mentioned that I introduced a Bug in my JPQL, whilst fixing a Bug.

I think it's a Bug that is easy to create, and is therefore worth a little blogpost.

In Java the || and && operators are short-circuiting operators. This means the expression on the right of the operator will not be evaluated if the expression on the left already makes the entire expression true¹.

When using Hibernate (or any other ORM) I do tend to program JPQL in the same way as I program in Java. As this is translated into JPQL, the translation is sometimes not what you would expect.

The class diagram looked something like the following. Bear in mind that each Class represents a table in the database, as is usual in an ORM.

The problem

The following JPQL had an issue:

//@formatter:off
String queryStr = "SELECT person " +
                  "FROM Person person " +
                  "JOIN FETCH person.function " +
                  "WHERE person.lastname = :lastname " +
                  "AND person.fired = false " +
                  "AND (person.address is null OR person.address.deleted = false) ";
//@formatter:on

The idea here is to provide us with a list of all Persons with a specific last name, who are both not fired and may or may not have an existing address.

It will be translated by Hibernate (in our case) into the following SQL statement:

select * -- a lot of fields here
from Person person0_ inner join Function function1_ on person0_.FUNCTIONID=function1_.FUNCTIONID, Address address2_ 
where person0_.ADDRESSID=address2_.ADDRESSID 
and person0_.LASTNAME=? 
and person0_.FIRED='N' 
and (person0_.ADDRESSID is null or address2_.DELETED='N')

Can you spot the problem?

The Solution

The problem above, apparently, is that besides the explicit inner join (inner join Function) there is an implicit inner join upon the Address table (from Address address2_ where person0_.ADDRESSID=address2_.ADDRESSID). This means that only persons will be shown that have an existing address. The condition in the where at the bottom regarding "person0_.ADDRESSID is null" is ignored.

The following, slightly more complicated, JPQL solves this problem:

//@formatter:off
String queryStr = "SELECT person " +
                  "FROM Person person " +
                  "JOIN FETCH person.function " +
                  "LEFT JOIN person.address address " +
                  "WHERE person.lastname = :lastname " +
                  "AND person.fired = false " +
                  "AND (address is null OR address.deleted = false) ";
//@formatter:on

This will be translated appropriately by Hibernate into the following SQL Query:

SELECT * -- a lot of fields here
FROM Person person0_
   INNER JOIN FUNCTION function1_
      ON person0_.FUNCTIONID=function1_.FUNCTIONID
   LEFT OUTER JOIN Address address2_
      ON person0_.ADDRESSID     =address2_.ADDRESSID
WHERE person0_.LASTNAME   =?
AND person0_.FIRED        ='N'
AND (address2_.ADDRESSID IS NULL OR address2_.DELETED      ='N')

Testing

Of course, I would not have made such a crappy mistake, if I did my tests properly. Apparently, testing is hard, and it is easy to miss to test all eventualities.

In this case it is obvious I forgot to test for the Address==null case.

Well, we live and learn.

References

The Java^TM Tutorials - Equality, Relational, and Conditional Operators

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op2.html

StackOverflow - Explicit vs Implicit SQL Joins

http://stackoverflow.com/questions/44917/explicit-vs-implicit-sql-joins