[bug #58427] Cost-base optimiser breaks short-circuit evaluation

[Cassio Neri]

URL:
  <https://savannah.gnu.org/bugs/?58427>

                 Summary: Cost-base optimiser breaks short-circuit evaluation
                 Project: findutils
            Submitted by: cassioneri
            Submitted on: Fri 22 May 2020 09:54:36 AM UTC
                Category: find
                Severity: 3 - Normal
              Item Group: Wrong result
                  Status: None
                 Privacy: Public
             Assigned to: None
         Originator Name: Cassio Neri
        Originator Email: 
             Open/Closed: Open
                 Release: 4.7.0
         Discussion Lock: Any
           Fixed Release: None

    _______________________________________________________

Details:

Man and info pages say (in different places with different words)

'EXPR1 EXPR2'
'EXPR1 -a EXPR2'
'EXPR1 -and EXPR2'
     And; EXPR2 is not evaluated if EXPR1 is false.

Some might rely on this short-circuit evaluation to prevent errors. However,
the cost-based optimiser changes the evaluation order and EXPR2 might be
evaluated even when EXPR1 is false. Here is an example:

mkdir some_dir
chmod 333 some_dir
find * -readable ! -empty -printf "yes" -or -printf "no" -prune

which yields

find: ‘some_dir’: Permission denied
no

The "Permission denied" in the output suggests that -readable is false but
find evaluates -empty anyway. (Removing ! -empty from the expression makes the
error go away.) The optimised tree (edited for the sake of brevity and
clarity) is:

(  (  ( ! -empty ) -and -readable ) -and -printf "yes" ) -or ( -printf "no"
-and -prune ) 

In this form, -empty is always evaluated (before -readable).

I hope this not a big diversion from the point but my ruminations on the
problem follow. Find's code assumes that AND and OR are commutative which is
true under pure boolean logic rules. However, with the addition of
short-circuiting these operators loose that property. (Some expressions do
commute but not all.) The code must understand that when EXPR1 affects (for
some definition of "affects") EXPR2, then they don't commute.

I first posted this question here:
https://stackoverflow.com/q/61937006/1137388





    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?58427>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/