[egcs-980321] Recursive death crash

[Hyman Rosen <hymie at prolifics dot com>]

Some of my code which makes heavy use of templates is sending this
version of egcs into a death spin of recursive calling. The stack
trace is

    ...
    make_typename_type (context=0x6506c0, name=0x34e188) at decl.c:4564
    make_implicit_typename (context=0x6506c0, t=0x650498) at decl.c:4623
    make_typename_type (context=0x6506c0, name=0x34e188) at decl.c:4564
    make_implicit_typename (context=0x6506c0, t=0x650498) at decl.c:4623
    lookup_name_real (name=0x34e188, prefer_type=0, nonclass=0) at decl.c:4766
    lookup_name (name=0x34e188, prefer_type=-2) at decl.c:4862
    yylex () at spew.c:306
    yyparse () at /usr/lib/bison.simple:387
    compile_file (name=0xefffeecb "puzzle.ii") at toplev.c:2525
    main (argc=8, argv=0xefffebb4, envp=0xefffebd8) at toplev.c:4330

Here's the C++ code - it's somewhat long:

#include <stl.h>
#include <limits.h>

template <class S>
struct keep
{
	S &s;
	keep(S &_s) : s(_s) { }
	operator S &() { return s; }
};

template <class A>
struct left : public keep<ostream>
{
	left(ostream &_s) : keep<ostream>(_s) { }
	void operator ()(const A &v) { s << v; }
};

template <class A>
struct right : public keep<istream>
{
	right(istream &_s) : keep<istream>(_s) { }
	void operator ()(A &v) { s >> v; }
};

template <class A>
struct perline : public keep<ostream>
{
	perline(ostream &_s) : keep<ostream>(_s) { }
	void operator ()(const A &v) { s << v << endl; }
};

template <class T>
static istream &
operator>>(istream &in, vector<T> &a)
{
	int n;
	in >> n;
	a.reserve(n);
	a.erase(&a[n], a.end());
	return for_each(a.begin(), a.end(), right<T>(in));
}

template <class T>
static ostream &
operator<<(ostream &out, const vector<T> &a)
{
	return for_each(a.begin(), a.end(), perline<T>(out));
}

template <class T>
static ostream &
operator<<(ostream &out, const list<T> &a)
{
	return for_each(a.begin(), a.end(), perline<T>(out));
}

enum spot { sp_none = 0, sp_white = 1, sp_black = 2, sp_either = 3 };

static ostream &
operator<<(ostream &out, const spot &s)
{
	return out << "> *."[s];
}

typedef vector<spot> line_conf;

static ostream &
operator<<(ostream &out, const line_conf &a)
{
	return for_each(a.begin(), a.end(), left<line_conf::value_type>(out));
}

typedef vector<line_conf> solution;
typedef list<solution> solutions;

class line
{
public:

	typedef vector<int> shape;
	typedef list<line_conf> confs;

private:

	shape the_shape;
	line_conf the_poss;
	confs the_confs;

	void generate();
	void genrec(line_conf::iterator, line_conf::iterator,
				shape::const_iterator, shape::const_iterator);
	void color();

	friend class puzzle;

public:

	line() { }
	line(int sz, const shape &shp)
		: the_shape(shp), the_poss(sz, sp_none) { generate(); }
};

void
line::generate()
{
	the_confs.erase(the_confs.begin(), the_confs.end());
	genrec(the_poss.begin(), the_poss.end(),
		   the_shape.begin(), the_shape.end());
	color();
}

void
line::genrec(line_conf::iterator fc, line_conf::iterator lc,
			 shape::const_iterator fs, shape::const_iterator ls)
{
	if (fs == ls)
	{
		fill(fc, lc, sp_white);
		the_confs.push_back(the_poss);
	}
	else
	{
		int npos = lc - fc + 2 - accumulate(fs, ls, ls - fs);
		for (int i = 0; i < npos; ++i)
		{
			line_conf::iterator p = fc;
			fill(p, p + i, sp_white);
			p += i;
			fill(p, p + *fs, sp_black);
			p += *fs;
			if (p != lc)
				*p++ = sp_white;
			genrec(p, lc, fs + 1, ls);
		}
	}
}

void
line::color()
{
	line_conf::iterator pb = the_poss.begin(), pe = the_poss.end(), q;
	confs::const_iterator cb = the_confs.begin(), ce = the_confs.end(), p;
	int n;

	fill(pb, pe, sp_none);
	for (n = 0, q = pb; q != pe; ++q, ++n)
		for (p = cb; p != ce; ++p)
			if ((*q = static_cast<spot>(*q | (*p)[n])) == sp_either)
				break;
}

class puzzle
{
	typedef list<line> side;

	side cols;
	side rows;

	bool step(const side &, side &);
	operator solution();

	enum state { inconsistent, solved, incomplete };
	state done();

	side::iterator min_row();

public:
	void iterate(solutions &);
	puzzle(istream &);
};

puzzle::puzzle(istream &in)
{
	int i, num_rows, num_cols;
	line::shape shape;

	in >> num_cols >> num_rows;
	for (i = 0; i < num_cols; ++i)
	{
		in >> shape;
		cols.push_back(line(num_rows, shape));
	}
	for (i = 0; i < num_rows; ++i)
	{
		in >> shape;
		rows.push_back(line(num_cols, shape));
	}
}

bool
puzzle::step(const side &gen, side &test)
{
	side::iterator tb = test.begin(), te = test.end(), p;
	side::const_iterator gb = gen.begin(), ge = gen.end(), r;
	int k, n;
	bool changed = false;

	for (n = 0, p = tb; p != te; ++p, ++n)
	{
		bool recolor = false;
		line::confs &c = (*p).the_confs;
		for (k = 0, r = gb; r != ge; ++r, ++k)
		{
			spot m = (*r).the_poss[n];
			if (m == sp_either)
				continue;
			line::confs::iterator q = c.begin();
			while (q != c.end())
			{
				line::confs::iterator v = q++;
				if (((*v)[k] & m) == 0)
				{
					c.erase(v);
					changed = true;
					recolor = true;
				}
			}
		}
		if (recolor)
			(*p).color();
	}
	return changed;
}

puzzle::side::iterator
puzzle::min_row()
{
	side::iterator rb = rows.begin(), re = rows.end(), r, s;
	int m = INT_MAX;

	for (r = rb; r != re; ++r)
	{
		int n = (*r).the_confs.size();
		if (n > 1 && n < m)
		{
			s = r;
			m = n;
		}
	}
	return s;
}

void
puzzle::iterate(solutions &results)
{
	for (;;)
	{
		while (step(rows, cols) | step(cols, rows))
		{
		}
		switch (done())
		{
		case inconsistent:
			return;
		case solved:
			results.push_back(*this);
			return;
		}
		puzzle clone(*this);
		side::iterator it_me = min_row(), it_cl = clone.min_row();
		line::confs::iterator i;
		i = (*it_cl).the_confs.begin();
		(*it_cl).the_confs.erase((*it_cl).the_confs.begin(), ++i);
		(*it_cl).color();
		i = (*it_me).the_confs.begin();
		(*it_me).the_confs.erase(++i, (*it_me).the_confs.end());
		(*it_me).color();
		clone.iterate(results);
	}
}

puzzle::state
puzzle::done()
{
	side::const_iterator rb = rows.begin(), re = rows.end(), r;
	for (r = rb; r != re; ++r)
	{
		switch ((*r).the_confs.size())
		{
		case 0: return inconsistent;
		case 1: continue;
		default:return incomplete;
		}
	}
	return solved;
}

puzzle::operator solution()
{
	solution s(rows.size());
	side::const_iterator r = rows.begin(), re = rows.end();
	int n = 0;
	while (r != re)
		s[n++] = (*r++).the_poss;
	return s;
}

int
main(int, char **)
{
	puzzle p(cin);
	solutions results;
	p.iterate(results);
	cout << results;
}