										Safe STL

								  Cay S. Horstmann
								horstman@cs.sjsu.edu


1. Legalese

These materials build upon the Standard Template Library (STL) code which is

Copyright (c) 1994
Hewlett-Packard Company

That material is provided pursuant to the following permission notice.

Permission to use, copy, modify, distribute and sell this software
and its documentation for any purpose is hereby granted without fee,
provided that the above copyright notice appear in all copies and
that both that copyright notice and this permission notice appear
in supporting documentation.  Hewlett-Packard Company makes no
representations about the suitability of this software for any
purpose.  It is provided "as is" without express or implied warranty.

The Safe STL enhancements are

(C) Horstmann Software Design Corp. 1995. All Rights Reserved.

You may freely use, copy, modify, or distribute these Safe STL enhancements
and this documentation for any purpose, provided (1) you charge NO FEE for
distributing these copyrighted materials and (2) you include both the
copyright notice and permission notice from Hewlett-Packard Company and this
copyright notice and permission notice. Horstmann Software Design Corporation
specifically disclaims that these materials might do anything useful at all.
If they work for you and don't destroy anything, you are in luck.
There is no free technical support available for these materials.


2. Background

STL, the Standard Template Library designed by Alexander Stepanov and Meng
Lee, is slated to become a part of the ANSI/ISO C++ Standard. Reaction to
STL has been mixed. Some programmers applaud its elegance and power, others
find flaws with the interface, naming conventions, multithread support or
safety. While STL may not be the perfect container class library, it is here 
to stay. I designed this small but useful enhancement to make STL safer to use.
Safe STL catches many typical STL programming errors at runtime (and a
few at compile time).


3. What it does

When you compile and link your code with Safe STL, iterators are instrumented
to be checked whenever they are used. There are four kinds of checks.

	1. When an iterator is dereferenced, it must be valid (i.e. belong to
		a container and not be past the end).

	2. When an iterator is incremented, it must be valid before the increment
		and valid or past the end after the increment. When an iterator is
		decremented, it must be valid or past the end before the decrement and
		valid after the decrement.

	3. To compute the difference of two iterators or to compare two iterators
		with <, <=, >, >=, the iterators must point to the same container.

	4. When a container is accessed through an iterator (like c.erase(i)),
		then the iterator must actually point inside the container.

Furthermore, container operations (such as assignment, insertion, removal,
etc.) update all iterators attached to a container.

If an error is detected, then an assertion failure is raised. (See section 6
to see how to change that behavior.)

Of course, checking and updating the iterators takes time. For release versions
of your code, you would probably want to go back to the unchecked version of
STL.

The interface of Safe STL is purposefully left the same as that of regular
STL. It would be an easy matter to add public member functions to the iterators
that check their status, but I believe that it is best not to develop yet 
another nonstandard template library.

Safe STL works better than a debugger or BoundsChecker for a number of reasons.
If your code dies because of a pointer error that is the consequence of an STL
usage error, the debugger will break deep in the bowels of STL code which is 
usually less than illuminating. If your code gets in an infinite loop because of 
an STL usage error, BoundsChecker will not actually complain. Some STL usage errors 
cause subtle inconsistencies in the STL data structures that will not lead to 
immediate failure. See the examples in section 4 for more information.


4. Some typical errors that Safe STL catches

* Runaway iterators

		 list<int> a;
		 list<int> b;
		 // ...

		 list<int>::iterator p
				 = find(a.begin(), b.end(), 100); // oops, should have been a.end()

		 if (p != a.end()) a.erase(p);

This code will loop forever when a.end() is reached.

Of course nobody would make such a dumb coding mistake.

I did several times, when I did some cut and paste and was sloppy
about updating the pasted code.


* Muddled iterators

		 list<int> a;
		 list<int> b;

		 list<int>::iterator pa = a.begin();
		 b.erase(pa);

In the HP implementation, this will erase the first element of a, but
reduce the length of b! Eventually, but not immediately, that will lead to
weird behavior.


* Past the end iterators

		 list<int>::iterator p
				 = find_if(a.begin(), a.end(), condition);

		 cout << *p; // an error if p is past the end


* Uninitialized iterators

		 list<int>::iterator p;
		 cout << *p; // an error


* Iterators to erased elements

		 list<int>::iterator p = a.begin();
		 list<int>::iterator q = p;
		 a.erase(q);

		 cout << *p; // an error


* Iterators to moved elements

		 vector<int>::iterator p = b.begin();
		 b.reserve(1000);
		 cout << *p; // maybe an error


* Iterators to destroyed containers

		 list<int>* pl = new list<int>;
		 list<int>::iterator p = pl->begin();
		 delete pl;
		 cout << *p; // an error


5. How to use it

Get the complete version of regular STL by ftp from butler.hpl.hp.com. Put
all regular STL files in a directory, e.g. /stl. Put the .h files from the
Safe STL distribution

	algobase.h
	vector.h
	deque.h
	list.h
	tree.h

into a separate directory, e.g. /safestl. Then put that directory into the
directory search path, BEFORE the directory that contains the regular STL.
For example,

	bcc -I/safestl;/stl whatnot.cpp

Then compile and link your application.

Note: You must rebuild the ENTIRE application. You cannot have mixed object
files that share STL containers and iterators, some compiled with the regular
and others with the safe headers. I realize that may be impossible if some
of your code is compiled into libraries whose interface references an STL
container or iterator.

Once your application is debugged, simply remove /safestl from the include
path and rebuild the application.

You will notice that Safe STL generates a large number of WARNINGS.
Unfortunately, there is little I can do about that without modifying the
original STL source extensively. Some warnings come from int/unsigned
mismatches--they also occur in regular STL. Others have the form "functions with
property X cannot be inline expanded". I don't want them inline expanded, but
I have no choice--the Borland compiler does not support templates defining
member functions of nested classes. If the Safe STL code becomes popular, I may
rewrite it to eliminate most warnings, but deviating further from the regular
STL code.


6. Changing the error handling

When an STL usage error is detected, an assertion failure is triggered,
using the standard assert macro. It works, and it is portable.

Why didn't I throw an exception when detecting a failure? That would have
changed the interface of the STL classes, which I didn't want to do. Had
the operations thrown exceptions upon failure, then you might write code
catching them. That code would no longer work when you switch back to
regular STL.

However, there is one major disadvantage to using assert. The debugger will
not give you a stack trace at the point of failure, so you can't see what
part of your code caused the problem. (The file and line number reported
by assert are in the Safe STL header.) If your debugger can break on exception
throw (like Turbo Debugger), you can view the stack and locate the offending
code. A brutal but effective way is to turn the assertion failure into an
exception. Before including the Safe STL headers,

	#define assert(X) if (!(X)) throw #X;

After the Safe STL headers, undefine it again.


7. Supported platforms

I have tested most examples from the HP STL site that compile with regular STL
(some require vendor-specific extensions), using both the Borland 4.53 and
Symantec 7.2 compilers. If your compiler supports the HP STL distribution but
chokes on Safe STL, please let me know (see section 8). If you made a
Safe STL version of your compiler and would like to make it available
to the public, I'd be happy to include it with this package,
provided of course that your modifications are freely distributable.

8. Compiler notes

Borland 4.5

Use the files in the BC45 directory. 

Borland 5.0

a) Use the files in the BC50 directory.
b) Copy the file \bc5\include\memory.h into your Safe STL include directory.
Make the following modification to the file: In the destroy template that
starts on line 210, add a &* in the call to destroy to make it read like
	template <class Pointer>
	void destroy (Pointer first, Pointer last)
	{
		 while (first != last)
			  {
						 destroy(&*first); // CSH
						 ++first;
			  }
	}
(I didn't want to distribute that file because it contains Rogue Wave copyrighted
material. So you'll have to edit it manually.)
c) Turn off precompiled headers, or set the "header stop" before any of the
STL header files. (It isn't my fault--the Borland STL headers don't work either.)

Microsoft 4.0

Use the files in the MS40 directory. If you like, make the changes described
in the README file on the STL directory of the CD-ROM to change everything to
the std namespace. Just prefix all ::swap with std.

You also need to make one change in defalloc.h, to comment out the definition of
the placement operator new. Microsoft already provides the definition in new.h.

Thanks to Mario Contestabile for his help with this.

9. Bug reports

Bug reports and suggestions for improvement are very welcome. Please direct
them to horstman@cs.sjsu.edu.

PLEASE, NO REQUESTS FOR HANDHOLDING. If you can't compile the sample programs
of the HP ftp site with regular and safe STL, or you don't know how to set
up the files and the compiler, then I cannot and will not try to fix it for you.

I am particular interested in
	- bugs that Safe STL should find but doesn't
	- false alarms: bug messages in perfectly correct code
	  (PLEASE read the STL documentation first before you report such a bug.
	  For example, did you know that inserting into a deque invalidates ALL
	  iterators to it?)

Before sending a bug report, please check if your bug has been fixed already.
The most current version of this code is available on the World Wide Web:
	http://www.mathcs.sjsu.edu/faculty/horstman/safestl.html


