[Rd] Vector underflow [-1] in sort(method="radix", na.last=NA)

[Ivan Krylov]

Hello R-devel,

Some inputs cause sort(method="radix") to try to read vectors at index
-1, which is caught for character vectors on some builds that use clang
-fsanitize=address since r89198:

podman run --rm -it \
 registry.gitlab.com/rdatatable/dockerfiles/r-devel-clang-san \
 R -q -s -e "order(NA_character_, 'c', method = 'radix', na.last = NA)"
# Error in order(NA_character_, "c", method = "radix", na.last = NA) : 
#   attempt access index -1/1 in STRING_ELT

Since savetl_end() did not run, some CHARSXPs retain their altered
TRUELENGTHs. The R session is then likely to crash when it tries to
read a negative-numbered hash bucket (usually during install() while
lazy-loading bytecode for another function call, e.g., when wrapping
the order() call in try()).

This seems to be a matter of catching elements already sorted as NA on
a previous pass:

Index: src/main/radixsort.c
===================================================================
--- src/main/radixsort.c	(revision 89211)
+++ src/main/radixsort.c	(working copy)
@@ -1766,7 +1766,9 @@
 		    // this edge case had to be taken care of
 		    // here.. (see the bottom of this file for
 		    // more explanation)
-		    switch (TYPEOF(x)) {
+		    if (o[i] == 0) { // already sorted as NA
+			isSorted = false;
+		    } else switch (TYPEOF(x)) {
 		    case INTSXP:
 			if (INTEGER(x)[o[i] - 1] == NA_INTEGER) {
 			    isSorted = false;

I don't entirely understand what causes src/main/radixsort.c to call
the non-inlined version of STRING_ELT in some cases.

-- 
Best regards,
Ivan