A question concerning re-entrance in the standard library was recently
raised in comp.std.c; the question is even more complicated in C++, and
I'd like some idea of what the final standard will/will not guarantee.

The basic question concerned whether, in C, it was legal for the
comparison function passed to qsort to call qsort; the basic answer was
no, since the standard explicitly states that library functions are not
re-entrant, and can use arbitrary static memory in their implementation.
The question was then raised: can several different functions share
arbitrary static memory.  For example, could a (decidedly strange)
implementation of strcmp share static memory with qsort, so that using
strcmp in the comparison function passed to qsort would fail?

In C, the problem is not too critical, since it only really comes up in
qsort and bsearch.  In all other cases (except signal handling, which is
a recognized special case), once you are in the library, you stay in
library code, and it is the problem of the implementor to make things
work.  In C++, on the other hand, there is a constant alternation
between user and the library, particularly with the template
functions/classes.

Let's start with the C++ variation of the qsort problem:

 string          a[ 10 ] ;
 sort( a.begin() , a.end() ) ;

Note that sort calls operator<( string const& , string const& ) (another
library function) to do the comparison.  I certainly hope that this is
unconditionally legal; I believe that it was the intent of the standards
committee to allow it, but I cannot find any language in the standard
which ensures it.  (To be fair, I cannot find off hand a statement like
that in the C standard which says that the library functions are not
re-entrant.  Requiring total re-entrance, however, leads to other
problems, see below.)

Note that there are potentially two ways that this could fail:

1. The operator< of string and sort use the same common static memory in
an incompatible manner, or

2. The operator< of string calls sort( string::iterator ,
string::iterator );

I mention these here for reference.  In this specific case, for example,
2 is definitly not legal, since it would cause operator<, used alone, to
fail.

All in all, I think that just plain common sense tells us that any
interpretation of the standard which makes the above invalide must be
wrong.

Now consider the following:

 vector< vector< int > >    a( 10 , vector< int >( 10 ) ) ;
 sort( a.begin() , a.end() ) ;

Note that the comparison function, "operator<( vector< vector< int > >
const& , vector< vector< int > > const& )" will invoke "operator<
vector< int > const& , vector< int > const& )".  Now consider an
implementation that derived the template class vector from a
non-template base class (fully legal, I'm sure), and in the template
function "operator<( vector< T > const& , vector< T > const& )", uses a
static member of this base class.  While highly unlikely, I'd be
interesting in knowing what constraint this implementation violated.  I
see nothing in the standard which would forbid this implementation,
except that it causes the above example to fail.  (Note that the
comparison function invoked recursively is an instance of the same
template function as the one which invokes it.)

Note too that while the above examples all involve cases where the
template mechanism generates the additional library calls directly, it
is fairly easy to imagine examples where this is not the case, *AND*
even cases where the invoked function is strictly the same.  For
example, consider "vector< A >", where the class A itself contains one
or more "vector< A >*".  Part of the operator< for A might be:

 struct A
 {
     vector< A >*   pa ;
 } ;

 bool
 operator<( A const& rhs , A const& lhs )
 {
  return (rhs.pa != 0 && lhs.pa != 0)
   ?   (*rhs.pa < *lhs.ps) ;
   :   (lhs.pa != 0) ;
 }

Note that the operator< for vector< A > will call this function, which
in turn calls operator< for vector< A >.  If the template function
operator< for vector uses static data in any way (unlikely, but not
impossible), there is going to be trouble.  Can it?

If the C++ standard has adopted the position of the C standard with
regards to re-entrancy in the library, the above program is definitly
illegal, and the programmer is at fault, not the implementation.  This
looks like a real trap.  Recursive structures are not all that rare, and
if the recursion involves an STL container (e.g.: a tree using set< A* >
children), the problem is potentially present.

I would now like to consider the problem from the opposite side: is the
following legal, and if not, why not?

 void*
 ::operator new( size_t n )
 {
  logFile << "new: " << n << " bytes requested\n" ;
  void*           p = malloc( n ) ;
  if ( p == 0 )
   throw bad_alloc() ;
  return p ;
 }

I would be very surprised to find an implementation where the above
program did not result in an endless recursion (since the first
operator<< will trigger a call to operator new to get memory for the
buffer).  Never the less, any interpretation of the standard which would
make any of the above examples legal would also make this legal.

This is, in general, a rather sticky question.  For obvious reasons, it
should be illegal to use any of the functions in iostream or stdio in
operator new.  On the other hand, I'd sort of like for it to be legal to
use malloc (and the standard does not allow malloc to be implemented in
terms of operator new precisely to admit it).  To be fair, standard
library functions that the user can replace are special, and I have no
problem with the idea that they must conform to additional rules.  I
would like for all of the additional rules to be clearly stated,
however.

The point of the above is simply to say that the standard should contain
some statement concerning the re-entrance of its library functions, and
in particular:

1. Certain functions (e.g.: operator new) must have special
requirements, and

2. The C rule (no function is required to be re-entrant) may be to
constraining in certain cases.  (I see no reason off hand why any of the
functions in the containers, iterators or algorithms sections need not
be re-entrant, but I could easily have missed something.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]