#29 6.4.2 and 7.0.0

[Batch Job 1]

loop-for-count never left a loop ending at the largest integer

What happened. A loop whose range ends at the largest integer ran its body for ever.

(loop-for-count (?index 9223372036854775807 9223372036854775807) (printout t "body ran" crlf))

Built at -O0, that printed body ran 79 million times in fifteen seconds and was still going. Built at -O1 or above it ran the body once and the loop ended.

Section 12.6.4 documents a range from 2 to 4 producing 2, 3 and 4, and a finished loop returning the symbol FALSE. Neither says anything about the optimization level, so one of the two behaviours is wrong, and the one that never returns is wrong under any reading.

Why it is a fix and not a preference. The counter is a long long. The loop body runs while the counter is less than or equal to the end, and the counter is then incremented. When the counter has reached the largest long long, that increment has no result the type can represent, which the C standard leaves undefined.

What the two optimization levels do with it is the ordinary consequence. At -O0 the increment wraps to the most negative integer, the test counter <= end is then true again, and the loop restarts from the bottom of the type. At -O1 and above the compiler is entitled to assume the increment cannot overflow, so it may reason that the counter only grows, and the loop ends.

So this is not undefined behaviour that happens to work. It is undefined behaviour that produces a non-terminating loop in a build CLIPS supports.

Where it came from. LoopForCountFunction in clips_core_source_642/core/prcdrfun.c:

   while ((tmpCounter->loopCounter <= iterationEnd) && …)
     {
      …
      tmpCounter->loopCounter++;
     }

The change. The pass on which the counter has reached the end is the last one, so the loop leaves at the end of that pass rather than incrementing. The loop test would have ended the loop on the following pass anyway, so the body still runs once for every value in the range.

      if (tmpCounter->loopCounter == iterationEnd)
        { break; }

      tmpCounter->loopCounter++;

This is a C break out of the while, not the H/L break action, so the BreakFlag handling after the loop is reached in the state a loop that ran out of range would leave it in.

What was checked. run-fix-tests.sh builds the core twice at -O0 — once as it stands and once with this line put back — and runs the loop above against each under a time limit. The reverted build does not finish; the build as it stands finishes and prints the body once. That is the discriminating evidence, and the runner produces it rather than citing it. It also builds both under -fsanitize=signed-integer-overflow and shows the overflow reported at prcdrfun.c by one and not the other.

tests/range-ends.clp guards the answers: section 12.6.4's own example; an empty range; a single value; both ends of the type as a one-value range; the last two values of the type, by value and not only by count; a finished loop returning FALSE in each of those shapes; a break after three passes over a range covering the whole type; a return out of the pass at the top of the type; a nested loop whose inner range is the top of the type on every outer pass; and a hundred passes ending at the top of the type, which crosses the boundary rather than sitting on it.

Still present upstream. CLIPS 7.0.0 has the same loop in core/prcdrfun.c.

[Batch Job 1]

Input error: title not entered. Report still relevant.