#47 CLIPS 6.4.2 core sources with our reported bugs fixed and optimizations applied

[Batch Job 1]

CLIPS 6.4.2 core sources with our reported bugs fixed and optimizations applied

The attached .zip file contains CLIPS 6.4.2 core sources with the changes below applied. Every fix answers a bug report we filed on the CLIPS tracker at https://sourceforge.net/p/clipsrules/bugs/ and is cited by its ticket number. The optimizations change no answers; two of them are filed at https://sourceforge.net/p/clipsrules/patches/ and the rest were not filed but should be clear from the descriptions: they make CLIPS run faster and leaner.

Nothing else was changed. No file outside this directory is needed to build it, and the makefiles are as shipped.

We hope you can make good use of these. Since each bug report includes test code to reproduce the bug, they can be verified manually.

While we will refrain from filing further reports to avoid overwhelming the maintainers' time, we hope that this set of bug fixes will be of use.

FIXES

24 A constraint after a multifield wildcard read outside the slot.

 A wildcard inside a slot compiles to a count of the fields after it rather than to
 a pattern node, so no multifield marker is built and the constraint was evaluated at
 a field position that does not follow the wildcard's length. CLIPS already has the
 accessor that reads a position relative to the slot's own length - FactPNGetVar3 and
 its join network and object network counterparts - and the constraint was not being
 sent to it, because RETURN_VALUE_CONSTRAINT_NODE was absent from the condition that
 selects it. Admitted at the seven places that make that choice.
 factgen.c, objrtgen.c

25 A pattern's own fact address was read as a slot number.

 FactReplaceGetfield chose the slot-indexing accessor for a node that names no slot,
 and 0 - 1 in an unsigned short made that slot 65535. A node naming no slot belongs
 to FactGetVarPN1, which returns the fact being matched; the sibling function makes
 that test twenty lines earlier in the same file.
 factgen.c

26 read-number read from the wrong position after the first call on a file.

 The read position came from CommandBufferInputCount, which belongs to the command
 prompt, so a second read on a file began writing wherever the previous read had
 finished. Anything other than stdin now gets a position of its own, which is the
 split ReadlineFunction already makes.
 iofun.c

27 CLIPS never returned after standard input was exhausted.

 End of file on stdin was turned into a newline, which the next pass appended again,
 so CommandLoop asked forever and the command string grew without bound. End of input
 is recorded in a flag that CommandLoop reads and leaves on, which is what
 CommandLoopBatchDriver already does at the end of its own input. main returns
 EXIT_SUCCESS rather than -1.
 commline.c, commline.h, main.c

28 random computed a span wider than the integer type.

 end - begin overflows for (random -9223372036854775808 9223372036854775807) and the

 + 1 overflows on its own for (random 0 9223372036854775807). The span is computed in
 unsigned arithmetic, where both are defined, and a span that wraps to zero covers
 the whole type so the generated value is used as it stands.
 miscfun.c

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

 The counter was incremented past the end value. The pass where it has reached the end
 is the last one, so the loop leaves there rather than incrementing; the body still
 runs once for every value in the range.
 prcdrfun.c

31 HashInteger negated the most negative integer.

 Both branches were undefined for -9223372036854775808: direct negation on WIN_MVC and
 llabs everywhere else. The negation is carried through unsigned long long, which is
 defined and gives the same magnitude llabs gives for every value llabs can handle, so
 one path now serves every platform. The remainder is also taken after the range guard
 rather than before it, which is the order 7.0.0 uses.
 symbol.c
 (#30 is the same report filed twice.)

32 HashFact multiplied a bit-field in int.

 bucket is an unsigned int bit-field of 29 bits, which the integer promotions turn into
 an int, so the product with 73981 overflowed for any template name whose bucket is
 above 29027. Multiplied as a size_t.
 facthsh.c

33 Hashing a fact converted a float's value as well as its bits.

 The float case added (unsigned long) of the float's value alongside the bits of its
 representation, which is undefined for every negative float and for every magnitude
 of 2^64 or more. The union already carries every bit of the double, so the value
 conversion is dropped; GetAtomicHashValue and HashFloat hash a float the same way.
 multifld.c

34 A method index was narrowed before its range was tested.

 The index was converted to the unsigned short of Defmethod.index before being tested,
 which turns -1 into 65535 and 65537 into 1, and both then pass every test after it.
 Tested as the long long it was read as, against a new MAX_DEFMETHOD_INDEX, in
 defmethod, undefmethod, ppdefmethod, get-method-restrictions, call-specific-method and
 the preview path.
 genrccom.c, genrcexe.c, genrcfun.c, genrcfun.h, genrcpsr.c

35 Salience was narrowed before its range was tested.

 The declared salience was cast to int before the test against -10000 to 10000, so on a
 host with a four-byte int, 4294967296 became 0 and 4294977296 became 10000, and both
 passed. Tested as a long long and narrowed after, which is what EvaluateSalience
 already does for the dynamic case.
 rulelhs.c

36 delete-member$ deleted the wrong field and wrote past its own block.

 FindValueInMultifield returned an index into contents for a scalar sought value and an
 offset from the start of the slice for a multifield one. The caller compared the two
 kinds, so it deleted the wrong field and wrote past the block it had allocated. Both
 branches now answer an index into contents, and member$ subtracts begin to report the
 position within the multifield it was given.
 multifun.c

37 fetch lost a subtopic whose level overflowed an int.

 The level was accumulated in an int with no bound, so a level of 2147483648 arrived as
 -2147483648 and a topic written as a subtopic of a level 0 menu was attached as a
 second root, out of reach of get-region. Accumulated in a long long and bounded, with a
 level the entry node cannot hold reported as an invalid delimiter string.
 textpro.c

38 read-number read an out-of-range numeral as a success.

 strtoll leaves LLONG_MAX or LLONG_MIN with ERANGE in errno, and that clamped value was
 returned as a successful read with nothing said. errno is now cleared around the call
 and ERANGE reported, which is the condition ScanNumber already warns on. The float
 branch is unchanged, because ScanNumber converts a float with atof and inspects
 nothing, so a source literal of 1e400 is an infinity throughout CLIPS.
 iofun.c

39 gensym counted past the largest integer.

 The index was incremented after use, so the call after (setgen 9223372036854775807)
 incremented the largest long long and returned gen-9223372036854775808. An exhausted
 index is recorded in its own flag and reported; setgen clears it and starts a new
 sequence.
 miscfun.c

40 format wrote past the buffer it allocated.

 The buffer was sized as the conversion string plus the argument plus 200, which leaves
 out the minimum field width and the precision: "%1000s" on one character allocated 207
 bytes and vsprintf wrote 1001. The width and precision are in the sum. They are also
 accumulated in a size_t and held to INT_MAX, because each reaches vsprintf as an int -
 accumulating the width in an int is what made "%2147483648s" come back empty, with the
 padding gone and the argument dropped with it. A width or precision wider than an int
 is reported as an invalid flag before any argument is converted.
 iofun.c

41 round, format and a derived default clamped a float outside the integer range.

 A float whose integral part is outside long long has no integer to become, and the cast
 has no result for it. round reports it rather than casting; a d, o, x or u conversion in
 format reports it; and a float range bound that cannot supply an integer slot default is
 passed over, so the next candidate is tried and the standard default of step 4 of
 section 11.5 is reached.
 emathfun.c, iofun.c, default.c

42 integer and div clamped a float outside the integer range.

 The same cast, reported the way div and mod already report an integer result they cannot
 represent.
 bmathfun.c

43 +, * and - wrapped out of the integer range.

 Each accumulated in a long long without testing, so a sum, product or difference outside
 the type was undefined. Tested from the operands before the operation, because an
 operation whose result is outside the type has no result to inspect.
 bmathfun.c

44 abs returned a negative absolute value.

 The most negative long long has no positive counterpart, and strtoll accepts the
 numeral so the scanner stores it. Reported rather than negated.
 bmathfun.c

45 progn$ freed a value the loop had not reached.

 A multifield in the garbage list does not own its contents, and an action that rebinds a
 variable releases the value it held - one integer or symbol reached from two places is
 one reference counted object - so the garbage collection the loop runs on each pass freed
 a value the loop had not reached. The multifield and its atomic values are held for as
 long as the loop runs. Fact and instance addresses are left out: the garbage fact and
 instance lists together with the loop's own GCBlock already keep those alive, and holding
 them here as well made (progn$ (?f (find-all-facts ...)) (retract ?f)) quadratic. The
 field types are recorded at retain time rather than read back at release time, because a
 fact the loop retracted can be freed before the loop ends.
 multifun.c

46 batch* evaluated one command per line.

 CompleteCommand reports a command only at the end of a line, so a line holding several
 commands arrived as one string and routing the whole string evaluated the first and
 discarded the rest. A new FirstCommandLength measures the first complete command using
 the same lexical rules, so they are routed one at a time.
 fileutil.c, commline.c, commline.h

41, #42 and #40 share one new helper, FloatFitsInInteger, which reports whether the integral

part of a double is a value long long can represent. Both of its bounds are exact: 2^63 is the
smallest double above LLONG_MAX, and -2^63 is LLONG_MIN itself with the next double below it
at -2^63 - 2048. A NaN or an infinity fails both comparisons.
evaluatn.c, evaluatn.h

OPTIMIZATIONS

Each of these was measured against this tree with that one change put back, rather than
against unmodified 6.4.2, so each figure is what that change is worth where it sits. The
figures for CompleteCommand and for the fact index lookup were re-measured for this package,
at -O3 on an Apple silicon machine; the rest are carried over from the runs that established
them and were not re-measured here.

CompleteCommand was asked once per character.
BatchStar appended one character and then asked CompleteCommand, which scans the whole
buffer from the start, so reading one line cost the square of its length - and a line
here is everything up to the first newline at parenthesis depth zero, so a construct
spread over a hundred lines is one line to this loop. Each of CompleteCommand's three
non-zero returns needs a newline in the string it is given, and appending a character
that is not a newline can neither produce one nor change the verdict at a newline
already there. The call is made only when the character just appended ends a line.
Reading a one-million-character line through batch*: 194.4 s to 0.03 s, with the growth
change below also in. Alone it reaches 4.601 s, because a second quadratic sits behind
this one on the same path.
fileutil.c

String buffers grew by exactly what was asked for.
EnlargeString sized the new buffer to exactly the text being appended, and the callers
of ExpandStringWithChar that add a character at a time pass the current maximum plus
eighty, so a token of n characters was copied 80 + 160 + ... + n bytes. Both now grow to
at least twice the current size, with the doubling guarded against overflowing size_t.
The size actually reached is still reported through oldMax and max, so a caller that
frees with it frees what was allocated. A one-million-character line: 4.490 s to 0.084 s.
utility.c

genrealloc copied one byte an iteration.
The shared prefix was copied one char per iteration and the tail zero-filled by a second
loop of the same shape. memcpy and memset, with the null-destination case guarded, since
the old loops handled it by not running. Worth fourteen times where the copying dominates
and about four per cent on top of the growth change above.
memalloc.c

A fact index was looked up by walking the whole fact list. (patch #6)
FindIndexedFact walked from the first fact to the last on every call, so reaching a fact
cost the number of facts before it and the newest fact - which (modify N), (duplicate N)
and reading back a fact just asserted all name - was the furthest away. The fact list
ascends by index and both ends are kept, so an index outside the ends is answered without
a walk, an index at either end in one step, and anything else from the nearer end,
stopping as soon as the walk passes the index sought. Two copies of the same walk open
coded in modify and duplicate now call it. Two thousand reads of the newest slot: with
500 facts held, 0.0074 s to 0.0081 s, and with 4000, 0.0246 s to 0.0069 s. The shape is
the point - the walk's cost grows with the number of facts and the lookup's does not,
so at 500 facts the walk is short enough that the two are the same within noise.
factmngr.c, tmpltfun.c

Retracting a fact hashed it a second time. (patch #7)
RemoveHashedFact found its bucket by calling HashFact again, which walks the deftemplate
name and then every field of every slot. The assertion had already done that walk and
already saved the answer on the fact. The bucket comes from the stored value;
ResizeFactHashTable relocates entries by that same value, so its agreeing with the fact's
contents is an invariant this relies on rather than one it introduces. Two thousand facts
of a sixty-field multislot, timing the retractions: 0.0223 s to 0.0148 s.
facthsh.c

Multifield set operations rescanned the other multifield.
subsetp, intersection$, union$ and difference$ test whether two fields hold the same
value by comparing value pointers, which is sound because every value a multifield can
hold is interned, and each made that test by walking - so each cost the product of the
lengths. A pointer-keyed set, open addressed with linear probing, is built once where a
walk used to run per element. Its capacity is twice the largest number of values that can
go in, known from the multifield lengths before anything is added, so the table never
passes half full and never has to grow. Two multifields of 64 000 each: 3.068 s to
0.0011 s. It costs 5.6 nanoseconds on a four-element call that took 36.5.
multifun.c

delete-member$ copied the whole multifield once a match.
Each removal allocated a new multifield, copied every field but one into it, and searched
the copy again from the start, so a multifield in which half the fields match cost the
square of the length. A scalar sought value is removed in one pass: each removal takes one
field away, so it cannot bring two fields together into a match that was not already
there. A sought multifield keeps the old loop, because removing a run can put the field
before it next to the field after it and make a match across the join. 8000 fields, half
matching: 0.0211 s to 0.0000100 s.
multifun.c

A hashed beta memory grew at a load of eleven.
UpdateBetaPMLinks resized when the count passed eleven times the table size, so the
average bucket held eleven matches and NetworkAssertRight chased a pointer per step.
Resized at four times instead. Two hundred thousand partial matches in the left memory of
a two-pattern join, probed by as many assertions: 1 871 716 compares to 712 176, and
0.1444 s to 0.1089 s, for 0.8 per cent more memory in use.
reteutil.c

lex and mea sorted the new activation once a comparison.
ComparePartialMatches called SortPartialMatch on both activations, which allocates an
array, copies a timetag out of each bind, bubble-sorts it and frees it again. The
placement functions call the comparison once against the tail of the salience group and
then once per step of the walk, so the new activation was copied, sorted and freed per
comparison with nothing about it changed between them. The comparison now takes the new
activation's sorted timetags as an argument and sorts only the activation already on the
agenda; both placement functions sort the new one once before the search. Four thousand
activations created by one assertion: 5 per cent under lex, 9 per cent under mea. The
agenda comes out in the same order under all six strategies.
crstrtgy.c

sort allocated two expression nodes a comparison.
DefaultCompareSwapFunction built the comparison's two argument nodes from scratch and
freed them again on every call, and MergeSort asks for a comparison n log n times.
Nothing in a node survived between calls that had to be rebuilt - only the type and the
value differ - so they are built on the first comparison and written over on every later
one, and freed with the rest of the comparison expression by the ReturnExpression in
SortFunction. The install and deinstall stay inside each comparison, holding a reference
to the two values for as long as it runs. Four thousand values sorted twenty times:
0.0290 s to 0.0269 s.
sortfun.c

HOW THIS WAS CHECKED

Built with the shipped makefile at -O3 under -Wall -Wundef -Wpointer-arith -Wshadow
-Wstrict-aliasing -Winline -Wmissing-declarations -Wredundant-decls -Wmissing-prototypes
-Wnested-externs -Wstrict-prototypes -Waggregate-return: no errors and no warnings.

The CLIPS 7.0.0 test suite was run against this tree and against unmodified 6.4.2, built
from the same makefile with the same flags, and its 138 dribble comparisons were diffed.
Five differ. Three of the five are a heap pointer address in drtest10, a timestamp in
instance and a wall clock reading in miscfnx, and all three also differ between two runs of
one binary - as does drtest09, which happened to agree across the two trees. So two of the
138 differ for a reason.

Those two are drtest11 and tmplv700, which no longer end in a segmentation fault:
unmodified 6.4.2 stops at exactly 8192 bytes of output on each, one buffer, and this tree
runs both to completion. #24 is what drtest11 reaches and #25 is what tmplv700 carries under
a comment reading "; Crash".

drtest11's output is then identical to the 7.0.0 expectation apart from four error
identifiers 7.0.0 renumbered - TMPLTFUN2 to TMPLTUTL2 and TMPLTDEF2 to TMPLTUTL4, with the
same message text. tmplv700's remaining differences are 7.0.0 language features.

Each fix carries its own tests. Where a behavioural check cannot tell the difference - #45
removed a read of freed memory rather than a wrong answer, so its tests pass either way -
the evidence is a sanitizer report, or whether the process terminates inside a time limit,
instead.

Under -fsanitize=undefined at -O0, each of the following reports on unmodified 6.4.2 at the
line named and reports nothing on this tree. Each is reached by a program of a few lines;

37 needs a text file as well, holding a subtopic written at level 2147483648.

 #28  miscfun.c:430    9223372036854775807 + 1 outside long long
 #31  symbol.c:855     negation of -9223372036854775808
 #32  facthsh.c:100    41988 * 73981 outside int, from (assert (person (name alice)))
 #33  multifld.c:800   -1 outside unsigned long, from (assert (d -1.0))
 #41  emathfun.c:1149  1e300 outside long long, from (round 1e300)
 #41  iofun.c:1870     1e300 outside long long, from (format nil "%d" 1e300)
 #42  bmathfun.c:400   1e300 outside long long, from (integer 1e300)
 #42  bmathfun.c:336   1e300 outside long long, from (div 1e300 2)
 #43  bmathfun.c:116   9223372036854775807 + 1 outside long long
 #43  bmathfun.c:167   9223372036854775807 * 2 outside long long
 #43  bmathfun.c:235   -9223372036854775807 - 2 outside long long
 #44  bmathfun.c:452   negation of -9223372036854775808
 #37  textpro.c:664    2147483640 + 8 outside int, loading a level of 2147483648
 #37  textpro.c:675    negation of -2147483648, the level that overflow produced
 #39  miscfun.c:323    9223372036854775807 + 1 outside long long, from gensym

37 also changes an answer, which is the defect the ticket is about: loading a file whose

subtopic is written at level 2147483648, unmodified 6.4.2 reports two entries and then
(get-region <file> SUB) returns the empty string, because the level arrived as -2147483648
and SUB was attached as a second root. This tree names the line, reports TEXTPRO5 and
returns FALSE from fetch, which is what section 13.17.2 says fetch does for a file it could
not load.</file>

32 depends on where the template name lands in the symbol table: person, alice and

diagnosis each reach it, widget, customer, inventory and measurement do not.

Under -fsanitize=address, (format nil "%1000s" "x") is a heap-buffer-overflow on unmodified
6.4.2 and reports nothing here, which is #40.

This is not a clean sanitizer run. -fsanitize=undefined also reports null-pointer member
accesses that are present in both trees and are not among these fixes - classcom.c:356 and
genrccom.c:467 at startup, tmpltdef.c:291 on a defrule, dffnxfun.c:465 on a defgeneric -
and that list is what four short programs happened to reach rather than a survey.

24 and #25 are the two segmentation faults above, so the suite is their evidence. #34 and

35 are narrowing that no sanitizer flags, and the evidence for each is the answer it

changes: unmodified 6.4.2 accepts 4294977296 as a salience and 65537 as a method index, and
this tree rejects both.