ANSI prototype confusion

[Steve Summit]

In article <4559 at idunno.Princeton.EDU> byron at astro.Princeton.EDU (Byron Rakitzis) writes:
>The only ANSI compiler I have is gcc...
>I'm writing my own header file for symbols to be found in libc.

Too bad you have to.  Someone has to have done this for gcc by now.

>I declared qsort as:
>        void qsort(void *, int, int, int (*)(void *, void *));
>This is okay, except that gcc then complains if strcmp or any
>function not taking (void *, void *) as arguments is passed to qsort.

Sometimes even weird, mutant compilers are trying to tell you
something with their error and warning messages :-) .  (No slam
against gcc; once again, it has gotten a subtle point right.)

As Chris Torek pointed out long ago, strong typing in C
(particularly of function pointer arguments) can cause
headaches.  This, however, is not one of them.  In fact, the
qsort/strcmp case is one common problem that function pointer
prototype checking should help to clean up.

It happens that ANSI X3.159 guarantees that a void * is
compatible with a char *, so mixing the two in this way
should perhaps yield warnings, not errors (footnote 1), but
this is a (doubly) red herring in this case.

First of all, the callback function you hand to qsort really is
called with two void *'s.  (Jim Van Zandt was just asking about
this a few weeks ago.)  It is _not_ called with two pointers-to-
whatever-your-datatype is.  Remember that your qsort prototype
(correctly) gives the type of the first argument as void *.  This
means that whether you are sorting an array of characters, or an
array of integers, or an array of structures, or an array of
pointers to characters, qsort gets a pointer-to-void as its
handle on the array, and can't possibly pass pointers to anything
else back to the comparison routine.

Even if the equivalence between void * and char * let you get
away with

	char *array[MAXSTRINGS];
	size_t narray;

	...fill in array...

	qsort(array, narray, sizeof(char *), strcmp);

you would still be making a big mistake.  The comparison function
is called with two pointers to the objects being compared, and
the objects being compared here are pointers to characters.  That
is, the comparison function is called with pointers to pointers
to characters, or char **'s, which is certainly not what strcmp
expects.

You must write a special comparison function

	int pstrcmp(void *p1, void *p2)
	{
	return strcmp(*(char **)p1, *(char **)p2);
	}

which retrieves the char *'s from the original array and passes
them to strcmp.

The only way strcmp could even begin to be used directly as a
comparison function for qsort would be if an array of arrays of
characters (i.e. a two-dimensional array) were being sorted.
It would look something like

	char array2[MAXSTRINGS][MAXLEN];

	...fill in array...

	qsort(array2, narray, MAXLEN, strcmp);

(We could let the compiler figure the right element size for us
by using sizeof(array2[0]) as qsort's third argument; this might
be a good idea, to avoid errors, but it hides what's going on.)

In this case, we could either ignore the message from gcc, or
call it a bug (footnote 1) and fix it, or use a different
intermediary function

	int p2strcmp(void *p1, void *p2)
	{
	return strcmp((char *)p1, (char *)p2);
	}

to make the casts explicit.

Using an array of fixed-size arrays is a poor way of sorting
strings, though, because it either risks truncation (if MAXLEN is
too small) or wastes space (if MAXLEN is too big), or both.  (Of
course, in a real program, both the strings and the array of
pointers to them would be dynamically allocated, eliminating
built-in limitations either on string length or number of
strings.)

I may add qsort/strcmp to the FAQ list one day; it comes up often
enough.

                                            Steve Summit
                                            scs at adam.mit.edu

P.S. to Byron Rakitzis: apologies if you were, in fact, using an
array of arrays, as in the second example.  The array of pointers
(the first example) brings up the more interesting question, and
is (once you get the comparison function right) the more useful
implementation.

Footnote 1.  ANSI X3.159 says (section 3.1.2.5) that "A pointer
to void shall have the same representation and alignment
requirements as a pointer to a character type."  It also says
(section 3.2.2.3) that "A pointer to void may be converted to or
from a pointer to any incomplete or object type."  It is usually
held that these latter conversions should be performed silently,
that is, neither

	extern void *malloc();
	int *ip = malloc(sizeof(int));
nor
	int i; void *p = &i;

should result in any error (or warning) messages.  (Of course,
X3.159 says nothing about what diagnostics a translator must not
produce, only some that it must, so a compiler can issue any
extra messages it wants.)

Should either of these guarantees let us pass an

	int (*)(char *, char *)

(that is, a pointer to a function of two arguments, char * and
char *, returning int) to a function expecting

	int (*)(void *, void *)

?  The first guarantee (bit-level equivalence of void * and char *)
might; the second does not.

Other pointers coerce silently to and from void *'s when the
compiler knows about the coercion.  If we have

	extern void f(int *);

and we call

	int i;
	void *vp = &i;
	f(vp);

the code will work (as long as the prototype is in scope; the
possibility that it might not be is a good reason not to depend
on implicit argument coercions).  The case with function
prototypes "within" function pointers is quite different,
however.  In a call through a pointer to a function expecting a
void * argument, the compiler is going to arrange that a void *
be passed, and the function being called had better expect a void *.
That it does was supposed to be guaranteed when the function
pointer was initialized, which is why modern compilers check
function pointer prototypes, and generate fussy-looking warnings.
(There may be a paragraph in X3.159 that discusses the extra
checking appropriate for function pointer prototypes; I'm not
sure at the moment.)

If we had

	int icmp(int *, int *);

and tried to pass it as the comparison function to qsort, a
complaint from the compiler would certainly be appropriate,
because qsort is going to pass void *'s to that function, not
int *'s, regardless of any implicit coercion between void * and
int * that might occur in other contexts.  Somewhere inside qsort
is code something like

	int (*compar)(void *, void *);
	void *p1, *p2;
	...
	r = compar(p1, p2);

and there is nothing there to tell the compiler that any coercion
of the arguments might be required.