Subversion Repositories tendra.SVN

/*

 * Copyright (c) 2002-2006 The TenDRA Project <http://www.tendra.org/>.

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 * 3. Neither the name of The TenDRA Project nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific, prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS

 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,

 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;

 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,

 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR

 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * $Id$

 */

/*

    		 Crown Copyright (c) 1997

    This TenDRA(r) Computer Program is subject to Copyright

    owned by the United Kingdom Secretary of State for Defence

    acting through the Defence Evaluation and Research Agency

    (DERA).  It is made available to Recipients with a

    royalty-free licence for its use, reproduction, transfer

    to other parties and amendment for any purpose not excluding

    product development provided that any such use et cetera

    shall be deemed to be acceptance of the following conditions:-

        (1) Its Recipients shall ensure that this Notice is

        reproduced upon any copies or amended versions of it;

        (2) Any amended version of it shall be clearly marked to

        show both the nature of and the organisation responsible

        for the relevant amendment or amendments;

        (3) Its onward transfer from a recipient to another

        party shall be deemed to be that party's acceptance of

        these conditions;

        (4) DERA gives no warranty or assurance as to its

        quality or suitability for any purpose and DERA accepts

        no liability whatsoever in relation to any use to which

        it may be put.

*/

#include "config.h"

#include <limits.h>

#include "c_types.h"

#include "ctype_ops.h"

#include "etype_ops.h"

#include "exp_ops.h"

#include "graph_ops.h"

#include "hashid_ops.h"

#include "id_ops.h"

#include "member_ops.h"

#include "nspace_ops.h"

#include "off_ops.h"

#include "tok_ops.h"

#include "type_ops.h"

#include "error.h"

#include "catalog.h"

#include "option.h"

#include "access.h"

#include "check.h"

#include "chktype.h"

#include "class.h"

#include "derive.h"

#include "dump.h"

#include "identifier.h"

#include "instance.h"

#include "namespace.h"

#include "redeclare.h"

#include "syntax.h"

#include "template.h"

#include "token.h"

#include "virtual.h"

/*

    ARE TWO GRAPHS EQUAL?

    This routine checks whether the graphs gr and gs are equal.  Allowance

    is made for the equivalence of virtual bases.

*/

int

eq_graph(GRAPH gr, GRAPH gs)

{

	GRAPH hr = gr;

	GRAPH hs = gs;

	while (!IS_NULL_graph(gr)) {

		/* Calculate canonical form for virtual bases */

		hr = gr;

		gr = DEREF_graph(graph_equal(gr));

	}

	while (!IS_NULL_graph(gs)) {

		/* Calculate canonical form for virtual bases */

		hs = gs;

		gs = DEREF_graph(graph_equal(gs));

	}

	return (EQ_graph(hr, hs));

}

/*

    SEARCH A GRAPH FOR A BASE

    This routine searches the graph gr for the base class ct.  It returns

    the first node encountered which matches ct, or the null graph if no

    such match is found.  Note that the search algorithm is based on a

    depth-first left-to-right traversal of the graph.

*/

static GRAPH

search_graph(GRAPH gr, CLASS_TYPE ct)

{

	DECL_SPEC acc;

	/* Check the head of gr */

	CLASS_TYPE cr = DEREF_ctype(graph_head(gr));

	if (eq_ctype(cr, ct)) {

		return (gr);

	}

	/* Only search first instance */

	acc = DEREF_dspec(graph_access(gr));

	if (acc & dspec_defn) {

		/* Search the branches of gr */

		LIST(GRAPH)br = DEREF_list(graph_tails(gr));

		while (!IS_NULL_list(br)) {

			GRAPH gs = DEREF_graph(HEAD_list(br));

			gs = search_graph(gs, ct);

			if (!IS_NULL_graph(gs)) {

				return (gs);

			}

			br = TAIL_list(br);

		}

	}

	return (NULL_graph);

}

/*

    IS ONE GRAPH A SUBGRAPH OF ANOTHER?

    This routine checks whether the graph gs is a subgraph of gr (allowing

    for the identification of virtual bases).

*/

int

is_subgraph(GRAPH gr, GRAPH gs)

{

	unsigned nt, ns;

	CLASS_TYPE ct, cs;

	if (EQ_graph(gr, gs)) {

		return (1);

	}

	ct = DEREF_ctype(graph_head(gr));

	cs = DEREF_ctype(graph_head(gs));

	nt = DEREF_unsigned(ctype_no_bases(ct));

	ns = DEREF_unsigned(ctype_no_bases(cs));

	if (nt == ns) {

		/* Graphs are the same size */

		return (eq_graph(gr, gs));

	}

	if (nt > ns) {

		/* gr is bigger than gs */

		LIST(GRAPH)br = DEREF_list(graph_tails(gr));

		while (!IS_NULL_list(br)) {

			GRAPH gt = DEREF_graph(HEAD_list(br));

			if (is_subgraph(gt, gs)) {

				return (1);

			}

			br = TAIL_list(br);

		}

	}

	return (0);

}

/*

    COPY A GRAPH

    This routine recursively copies the graph gr into the base class graph

    of the current class, with access specifiers adjusted by acc and virtual

    specifier virt.  indir is true if the graph is a subgraph of a virtual

    base and templ is true if the graph represents a template parameter.

*/

static GRAPH

copy_graph(GRAPH gr, OFFSET off, DECL_SPEC acc, int virt, int indir, int templ)

{

	OFFSET offa;

	DECL_SPEC as;

	GRAPH gc, gp, gs;

	LIST(GRAPH)bs;

	/* Decompose head of graph */

	CLASS_TYPE ct = DEREF_ctype(graph_head(gr));

	LIST(GRAPH)bt = DEREF_list(graph_tails(gr));

	/* Adjust access specifiers */

	DECL_SPEC at = DEREF_dspec(graph_access(gr));

	as = join_access(at, acc);

	as |= shadow_access(at);

	if (at & dspec_virtual) {

		virt = 1;

	}

	if (virt) {

		/* Mark virtual bases */

		as |= dspec_virtual;

		indir = 1;

	}

	if (indir) {

		/* Mark indirect bases */

		as |= dspec_mutable;

	}

	if (templ) {

		/* Mark template parameter bases */

		as |= dspec_template;

	}

	as |= dspec_inherit;

	as &= ~dspec_done;

	/* Search existing graph for ct */

	gc = DEREF_graph(ctype_base(crt_class));

	gp = search_graph(gc, ct);

	if (IS_NULL_graph(gp)) {

		as |= dspec_defn;

	}

	/* Copy components */

	bs = NULL_list(GRAPH);

	while (!IS_NULL_list(bt)) {

		GRAPH gt = DEREF_graph(HEAD_list(bt));

		gt = copy_graph(gt, off, as, 0, indir, templ);

		CONS_graph(gt, bs, bs);

		bt = TAIL_list(bt);

	}

	bs = REVERSE_list(bs);

	/* Create new graph */

	MAKE_graph_basic(ct, as, gs);

	COPY_list(graph_tails(gs), bs);

	COPY_graph(graph_top(gs), gc);

	/* Set base offset */

	offa = DEREF_off(graph_off(gr));

	if (!IS_NULL_off(offa)) {

		MAKE_off_deriv(gs, off, offa, off);

	}

	COPY_off(graph_off(gs), off);

	/* Set up-field of bases */

	while (!IS_NULL_list(bs)) {

		GRAPH gt = DEREF_graph(HEAD_list(bs));

		COPY_graph(graph_up(gt), gs);

		bs = TAIL_list(bs);

	}

	return (gs);

}

/*

    FIND A COPY OF A SUBGRAPH

    Given a graph gs, a subgraph hs of gs, and a copy gr of gs (produced

    by copy_graph above), this routine returns the subgraph of gr which is

    the image of hs under this copy operation, i.e. it is the subgraph

    hr which makes the following diagram commutative:

				copy

			    gr ------ gs

			     |        |

			incl |        | incl

			     |        |

			    hr ------ hs

				copy

*/

GRAPH

find_subgraph(GRAPH gr, GRAPH gs, GRAPH hs)

{

	if (EQ_graph(gs, hs)) {

		return (gr);

	}

	if (!IS_NULL_graph(gr)) {

		LIST(GRAPH)br = DEREF_list(graph_tails(gr));

		LIST(GRAPH)bs = DEREF_list(graph_tails(gs));

		while (!IS_NULL_list(br)) {

			GRAPH ar = DEREF_graph(HEAD_list(br));

			GRAPH as = DEREF_graph(HEAD_list(bs));

			GRAPH hr = find_subgraph(ar, as, hs);

			if (!IS_NULL_graph(hr)) {

				return (hr);

			}

			br = TAIL_list(br);

			bs = TAIL_list(bs);

		}

	}

	return (NULL_graph);

}

/*

    IDENTIFY TWO GRAPHS

    This routine identifies the graph gs with the graph gr by linking

    them by means of their equal fields.

*/

static void

identify_graph(GRAPH gr, GRAPH gs)

{

	DECL_SPEC acc;

	LIST(GRAPH)br, bs;

	GRAPH gu = DEREF_graph(graph_equal(gs));

	while (!IS_NULL_graph(gu)) {

		gs = gu;

		gu = DEREF_graph(graph_equal(gs));

	}

	br = DEREF_list(graph_tails(gr));

	bs = DEREF_list(graph_tails(gs));

	while (!IS_NULL_list(br)) {

		GRAPH hr = DEREF_graph(HEAD_list(br));

		GRAPH hs = DEREF_graph(HEAD_list(bs));

		identify_graph(hr, hs);

		br = TAIL_list(br);

		bs = TAIL_list(bs);

	}

	COPY_graph(graph_equal(gs), gr);

	acc = DEREF_dspec(graph_access(gr));

	acc |= dspec_done;

	COPY_dspec(graph_access(gr), acc);

	return;

}

/*

    BASE CLASS INFORMATION

    The variable base_info holds information about the graph being analysed

    by fold_graph, for example, does it have a virtual or an ambiguous base

    class?

*/

static CLASS_INFO base_info = cinfo_none;

static LIST(GRAPH) virtual_bases = NULL_list(GRAPH);

/*

    FOLD A GRAPH

    This routine folds the graph gr by identifying all of its equal virtual

    bases.  It also defines values representing the offset of each base

    from the start of its class.  It returns a list of all the base classes

    in gr (allowing for virtual bases).  All bases added to the list are

    marked as explicit bases.

*/

static LIST(GRAPH)

fold_graph(GRAPH gr, LIST(GRAPH)br)

{

	CLASS_TYPE ct = DEREF_ctype(graph_head(gr));

	DECL_SPEC acc = DEREF_dspec(graph_access(gr));

	/* Scan for previous uses of this base */

	LIST(GRAPH)bs = br;

	while (!IS_NULL_list(bs)) {

		GRAPH gs = DEREF_graph(HEAD_list(bs));

		CLASS_TYPE cs = DEREF_ctype(graph_head(gs));

		if (eq_ctype(cs, ct)) {

			/* Duplicate base found */

			DECL_SPEC acs = DEREF_dspec(graph_access(gs));

			if ((acs & dspec_virtual) && (acc & dspec_virtual)) {

				/* Both bases are virtual */

				if (!eq_graph(gr, gs)) {

					/* Identify graphs if not already

					 * done */

					identify_graph(gr, gs);

				}

				/* Propagate ambiguous bases */

				if (acs & dspec_alias) {

					acc |= dspec_alias;

				} else if (acc & dspec_alias) {

					while (!IS_NULL_graph(gs)) {

						acs = DEREF_dspec(graph_access(gs));

						acs |= dspec_alias;

						COPY_dspec(graph_access(gs),

							   acs);

						gs = DEREF_graph(graph_equal(gs));

					}

				}

				acc |= dspec_done;

				COPY_dspec(graph_access(gr), acc);

				return (br);

			}

			/* Ambiguous base */

			base_info |= cinfo_ambiguous;

			acc |= dspec_alias;

			acs |= dspec_alias;

			COPY_dspec(graph_access(gs), acs);

		}

		bs = TAIL_list(bs);

	}

	/* Add base class to list */

	acc |= (dspec_main | dspec_done);

	COPY_dspec(graph_access(gr), acc);

	CONS_graph(gr, br, br);

	/* Fold subgraphs */

	bs = DEREF_list(graph_tails(gr));

	while (!IS_NULL_list(bs)) {

		GRAPH gs = DEREF_graph(HEAD_list(bs));

		br = fold_graph(gs, br);

		bs = TAIL_list(bs);

	}

	/* Build list of virtual classes */

	if (acc & dspec_virtual) {

		base_info |= cinfo_virtual_base;

		CONS_graph(gr, virtual_bases, virtual_bases);

	}

	return (br);

}

/*

    FIND A SINGLE INHERITANCE BASE CLASS

    This routine returns the single inheritance base class of gr or the

    null graph if there is no such base.  The single inheritance base

    is the first direct base, provided this is not virtual.  Derived

    classes are laid out so that their single inheritance base classes

    are at zero offset from the start of the class, thereby minimising

    the cost of a base class conversion.

*/

static GRAPH

find_first_base(GRAPH gr)

{

	LIST(GRAPH)br = DEREF_list(graph_tails(gr));

	if (!IS_NULL_list(br)) {

		GRAPH gs = DEREF_graph(HEAD_list(br));

		DECL_SPEC acc = DEREF_dspec(graph_access(gs));

		if (!(acc & dspec_virtual)) {

			return (gs);

		}

	}

	return (NULL_graph);

}

/*

    END BASE CLASS DEFINITIONS

    This routine is called after all the base classes of a class have been

    processed.  ok is false for an empty base class list.  The routine

    folds the base class graph of the current class and records the total

    number of bases.  It also initialises the virtual function table.

*/

void

end_base_class(CLASS_TYPE ct, int ok)

{

	if (!IS_NULL_ctype(ct)) {

		/* Scan for virtual bases */

		CLASS_INFO ci = DEREF_cinfo(ctype_info(ct));

		GRAPH gr = DEREF_graph(ctype_base(ct));

		LIST(GRAPH)bs = DEREF_list(graph_tails(gr));

		unsigned nd = LENGTH_list(bs);

		LIST(GRAPH)br = fold_graph(gr, NULL_list(GRAPH));

		unsigned nb = LENGTH_list(br);

		IGNORE check_value(OPT_VAL_base_classes,(ulong)(nb - 1));

		IGNORE check_value(OPT_VAL_direct_bases,(ulong)nd);

		COPY_unsigned(ctype_no_bases(ct), nb);

		while (!IS_NULL_list(br)) {

			GRAPH gs;

			nb--;

			DESTROY_CONS_graph(destroy, gs, br, br);

			do {

				COPY_unsigned(graph_no(gs), nb);

				gs = DEREF_graph(graph_equal(gs));

			} while (!IS_NULL_graph(gs));

		}

		br = REVERSE_list(virtual_bases);

		COPY_list(ctype_vbase(ct), br);

		nd = LENGTH_list(br);

		IGNORE check_value(OPT_VAL_virtual_bases,(ulong)nd);

		virtual_bases = NULL_list(GRAPH);

		/* Mark single inheritance bases */

		do {

			DECL_SPEC acc = DEREF_dspec(graph_access(gr));

			acc |= dspec_ignore;

			COPY_dspec(graph_access(gr), acc);

			gr = find_first_base(gr);

		} while (!IS_NULL_graph(gr));

		/* Set up base class namespaces */

		while (!IS_NULL_list(bs)) {

			GRAPH gs = DEREF_graph(HEAD_list(bs));

			CLASS_TYPE cs = DEREF_ctype(graph_head(gs));

			NAMESPACE ns = DEREF_nspace(ctype_member(cs));

			NAMESPACE nt = DEREF_nspace(ctype_member(ct));

			IGNORE use_namespace(ns, nt, nt);

			uncache_namespace(ns, 0);

			bs = TAIL_list(bs);

		}

		/* Record class information */

		if (!ok) {

			report(crt_loc, ERR_class_derived_empty(ct));

		}

		ci |= base_info;

		COPY_cinfo(ctype_info(ct), ci);

		base_info = cinfo_none;

		if (do_dump) {

			dump_base(ct);

		}

		/* Set up virtual function table */

		begin_virtual(ct);

	}

	return;

}

/*

    ADD A BASE CLASS TO A CLASS DEFINITION

    This routine adds a base class bid with access specifier acc to the

    current class.  virt is true to indicate a virtual base class.

*/

void

add_base_class(IDENTIFIER bid, DECL_SPEC acc, int virt)

{

	GRAPH gt;

	int ok = 1;

	CLASS_INFO cj;

	int templ = 0;

	LIST(GRAPH)bt;

	TYPE s = NULL_type;

	CLASS_TYPE cs = NULL_ctype;

	/* Examine the derived class */

	CLASS_TYPE ct = crt_class;

	CLASS_INFO ci = DEREF_cinfo(ctype_info(ct));

	if (ci & cinfo_union) {

		/* Derived class can't be a union */

		report(crt_loc, ERR_class_union_deriv(ct));

		ok = 0;

	}

	/* Examine the base class */

	if (IS_id_class_name_etc(bid)) {

		s = DEREF_type(id_class_name_etc_defn(bid));

	} else {

		IDENTIFIER tid;

		HASHID bnm = DEREF_hashid(id_name(bid));

		if (crt_id_qualifier == qual_none) {

			tid = find_type_id(bnm, 1);

		} else {

			NAMESPACE bns = DEREF_nspace(id_parent(bid));

			tid = find_qual_id(bns, bnm, 0, 1);

			if (IS_NULL_id(tid)) {

				/* Allow for implicit typename */

				s = check_typename(bns, bid, btype_class);

			}

		}

		if (!IS_NULL_id(tid)) {

			if (IS_id_ambig(tid)) {

				tid = report_ambiguous(tid, 0, 1, 1);

			}

			if (IS_id_class_name_etc(tid)) {

				s = DEREF_type(id_class_name_etc_defn(tid));

				bid = tid;

			}

		}

	}

	if (!IS_NULL_type(s)) {

		/* Declared base type */

		s = expand_type(s, 2);

		if (IS_type_compound(s)) {

			cs = DEREF_ctype(type_compound_defn(s));

		} else if (IS_type_token(s)) {

			/* Allow for template parameters */

			IDENTIFIER pid = DEREF_id(type_token_tok(s));

			cs = find_class(pid);

			templ = 1;

		}

		if (IS_NULL_ctype(cs)) {

			/* Inappropriate base class type */

			if (!IS_type_error(s)) {

				report(crt_loc, ERR_class_derived_class(s));

			}

			ok = 0;

		} else {

			/* Examine base class type */

			bid = DEREF_id(ctype_name(cs));

			cj = DEREF_cinfo(ctype_info(cs));

			if (cj & cinfo_union) {

				/* Base class can't be a union */

				report(crt_loc, ERR_class_union_base(cs));

				ok = 0;

			} else {

				/* Base class must be complete */

				ERROR err = check_incomplete(s);

				if (!IS_NULL_err(err)) {

					ERROR err2 =

					    ERR_class_derived_incompl();

					err = concat_error(err, err2);

					report(crt_loc, err);

					ok = 0;

				}

			}

		}

	} else {

		/* Undeclared base type */

		report(crt_loc, ERR_dcl_type_simple_undef(bid));

		ok = 0;

	}

	/* Check the access specifier */

	if (acc == dspec_none) {

		/* No access specifier given */

		acc = crt_access;

		if (acc != prev_access) {

			/* Warn about 'class C : public A, B' */

			report(crt_loc, ERR_class_access_base_acc(bid, acc));

		}

	}

	prev_access = acc;

	if (virt) {

		prev_access |= dspec_virtual;

	}

	/* Check for duplicate base classes */

	gt = DEREF_graph(ctype_base(ct));

	if (ok) {

		bt = DEREF_list(graph_tails(gt));

		while (!IS_NULL_list(bt)) {

			GRAPH gu = DEREF_graph(HEAD_list(bt));

			CLASS_TYPE cu = DEREF_ctype(graph_head(gu));

			if (eq_ctype(cs, cu)) {

				report(crt_loc, ERR_class_mi_dup(ct, cs));

				ok = 0;

				break;

			}

			bt = TAIL_list(bt);

		}

	}

	/* Add base class to graph */

	if (ok) {

		OFFSET off;

		LIST(GRAPH)bs = NULL_list(GRAPH);

		GRAPH gs = DEREF_graph(ctype_base(cs));

		MAKE_off_base(gs, off);

		gs = copy_graph(gs, off, acc, virt, virt, templ);

		COPY_graph(off_base_graph(off), gs);

		COPY_graph(graph_up(gs), gt);

		CONS_graph(gs, bs, bs);

		bt = DEREF_list(graph_tails(gt));

		if (!IS_NULL_list(bt)) {

			/* Mark multiple inheritance */

			ci |= cinfo_multiple_base;

		}

		bt = APPEND_list(bt, bs);

		COPY_list(graph_tails(gt), bt);

		/* Adjust class information */

		cj = DEREF_cinfo(ctype_info(cs));

		ci = check_class_info(ci, cj, 1, acc);

		COPY_cinfo(ctype_info(ct), ci);

		/* Use class name */

		use_id(bid, 0);

	}

	return;

}

/*

    FIND A BASE CLASS

    This routine finds whether cs is a base class of ct, returning the

    corresponding node of the base class graph, or the null graph.  The

    first guess is based on the fact that if cs is a base class of ct

    then ct has at least as many base classes as cs.   The way to remember

    which way round the arguments go is that 'find_base_class ( ct, cs )'

    checks for 'class ct : public cs {}'.  If ct is a template class

    then def indicates whether this operation implies that ct should

    be defined (not properly implemented yet).

*/

GRAPH

find_base_class(CLASS_TYPE ct, CLASS_TYPE cs, int def)

{

	unsigned nt, ns;

	complete_class(ct, 1);

	nt = DEREF_unsigned(ctype_no_bases(ct));

	ns = DEREF_unsigned(ctype_no_bases(cs));

	if (nt >= ns) {

		/* ct is bigger than cs */

		GRAPH gr = DEREF_graph(ctype_base(ct));

		return (search_graph(gr, cs));

	}

	UNUSED(def);

	return (NULL_graph);

}

/*

    COMPARE TWO CLASSES

    This routine finds whether cs is a base class of ct, or ct is a base

    class of cs.  It returns whichever class is the base class, or the null

    class if the two classes are not so related.  The first guess is based

    on the relative numbers of base classes of each type.  def is as in

    find_base_class.

*/

CLASS_TYPE

compare_base_class(CLASS_TYPE ct, CLASS_TYPE cs, int def)

{

	unsigned nt, ns;

	complete_class(ct, 1);

	complete_class(cs, 1);

	nt = DEREF_unsigned(ctype_no_bases(ct));

	ns = DEREF_unsigned(ctype_no_bases(cs));

	if (nt >= ns) {

		/* ct is bigger than cs */

		GRAPH gr = DEREF_graph(ctype_base(ct));

		gr = search_graph(gr, cs);

		if (!IS_NULL_graph(gr)) {

			return (cs);

		}

	} else {

		/* ct is smaller than cs */

		GRAPH gr = DEREF_graph(ctype_base(cs));

		gr = search_graph(gr, ct);

		if (!IS_NULL_graph(gr)) {

			return (ct);

		}

	}

	UNUSED(def);

	return (NULL_ctype);

}

/*

    CHECK AN AMBIGUOUS BASE CLASS

    This routine checks whether the base class corresponding to the node

    gr is ambiguous.  It returns a suitable error message.

*/

ERROR

check_ambig_base(GRAPH gr)

{

    if (!IS_NULL_graph(gr)) {

	DECL_SPEC acc = DEREF_dspec(graph_access(gr));

	if (acc & dspec_alias) {

	    /* Ambiguous base class */

	    GRAPH gt = DEREF_graph(graph_top(gr));

	    CLASS_TYPE ct = DEREF_ctype(graph_head(gt));

	    CLASS_TYPE cs = DEREF_ctype(graph_head(gr));

	    ERROR err = ERR_class_member_lookup_ambig(cs, ct);

	    return (err);

	}

    }

    return (NULL_err);

}

/*

    CHECK A VIRTUAL BASE CLASS

    This routine checks whether the base class corresponding to the node

    gr is a virtual base of a base class of a virtual base.  It returns a

    suitable error message.

*/

ERROR

check_virt_base(GRAPH gr)

{

	if (!IS_NULL_graph(gr)) {

		DECL_SPEC acc = DEREF_dspec(graph_access(gr));

		if (acc & dspec_mutable) {

			/* Virtual base class */

			GRAPH gt = DEREF_graph(graph_top(gr));

			CLASS_TYPE ct = DEREF_ctype(graph_head(gt));

			CLASS_TYPE cs = DEREF_ctype(graph_head(gr));

			ERROR err = ERR_class_derived_virt(cs, ct);

			return (err);

		}

	}

	return (NULL_err);

}

/*

    FIND A UNIQUE BASE CLASS

    This routine returns the graph representing the unique direct base

    class of ct if this exists.  Otherwise it adds an error to err and

    returns the null graph.

*/

GRAPH

uniq_base_class(CLASS_TYPE ct, ERROR *err)

{

	GRAPH gr = DEREF_graph(ctype_base(ct));

	LIST(GRAPH)br = DEREF_list(graph_tails(gr));

	if (LENGTH_list(br) == 1) {

		GRAPH gs = DEREF_graph(HEAD_list(br));

		return (gs);

	}

	add_error(err, ERR_class_base_init_uniq(ct));

	return (NULL_graph);

}

/*

    FIND THE SHORTEST ROUTE TO A BASE CLASS

    There may be several path for accessing a virtual base class.  This

    routine finds the shortest such path in terms of virtual base

    indirections for reaching the base gr.

*/

GRAPH

min_base_class(GRAPH gr)

{

	GRAPH gs = gr;

	unsigned n = (unsigned)UINT_MAX;

	while (!IS_NULL_graph(gs)) {

		GRAPH gt = gs;

		unsigned m = 0;

		while (!IS_NULL_graph(gt)) {

			/* Find base class depth */

			DECL_SPEC acc = DEREF_dspec(graph_access(gt));

			if (acc & dspec_virtual) {

				m++;

			}

			gt = DEREF_graph(graph_up(gt));

		}

		if (m < n) {

			/* Shortest path so far */