SortChecker++ verifies that comparators in C++ APIs like std::sort or std::binary_search satisfy the Strict Weak Ordering axioms. Violation of these axioms is undefined behavior and may lead to all sorts of runtime errors including aborts (also here, see this answer for explanations).

SortChecker++ is an extension of SortChecker tool which does similar job to C sorting APIs.

The tool has been tested on LLVM 6.0 (Ubuntu 18.04), 10.0 (Ubuntu 20.04) and 14.0 (Ubuntu 22.04).

List of found issues:

• Libosmium: Missing prepare_for_lookup in test_members_database.cpp (fixed)
• ZeroC Ice: Unsorted array in lookupKwd (fixed)
• GiNaC: Potential issue in comparator in test_antipode (fixed)
• ArrayFire: Irreflexive comparator (already fixed in latest)
• Giac: Non-asymmetric comparator in polynome_less (already fixed in latest)

How to build

To use, first install dependencies:

$ sudo apt install libclang-dev llvm-dev

and then build the tool

$ make clean all

How to use

SortChecker works by instrumenting the input file, i.e. inserting additional checking code into it. You can run it manually via

$ SortChecker file.cpp -- $CXXFLAGS

and then compile via

$ g++ file.cpp $CXXFLAGS -Ipath/to/sortcheck.h

You could also use compiler wrappers in scripts/ folder to combine instrumentation and compilation:

$ PATH=path/to/scripts:$PATH make clean all

Instrumented program may be controlled with environment variables:

• SORTCHECK_VERBOSE=N - verbosity (N is an integer)
• SORTCHECK_SYSLOG=1 - dump messages to syslog (in addition to stderr)
• SORTCHECK_ABORT_ON_ERROR=1 - call abort() on detected error
• SORTCHECK_EXIT_CODE=N - call exit(CODE) on detected error (N is an integer)
• SORTCHECK_OUTPUT=path/to/logfile - write detected errors to file instead of stdout
• SORTCHECK_CHECKS=mask - set which checks are enabled via bitmask (e.g. mask=0xfffe would disable the generally uninteresting irreflexivity checks)

Interpreting the error messages

tbd