Rev 5 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* Copyright (c) 2002-2005 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 "c_types.h"
#include "ctype_ops.h"
#include "etype_ops.h"
#include "ftype_ops.h"
#include "hashid_ops.h"
#include "id_ops.h"
#include "itype_ops.h"
#include "member_ops.h"
#include "type_ops.h"
#include "error.h"
#include "option.h"
#include "basetype.h"
#include "char.h"
#include "chktype.h"
#include "hash.h"
#include "lex.h"
#include "namespace.h"
#include "symbols.h"
#include "syntax.h"
#include "token.h"
#include "ustring.h"
#include "xalloc.h"
/*
HASH TABLES
The hash tables consist of an array of hash identifiers, one for each
hash value. All the hash table entries with the same hash value are
chained into a list using their next field. There are two hash tables,
one for strings and one for types.
*/
HASHID *hash_table;
static HASHID *hash_type_table;
/*
IDENTIFIER NAME HASHING FUNCTION
This routine calculates the hash value associated with the identifier
name s. The main parser routine, read_token, calculates the hash values
of the identifiers it reads on the fly and stores them in token_hash.
Therefore any changes to this routine should also be reflected in
read_token.
*/
unsigned long
hash(string s)
{
character c;
unsigned long h = 0;
while (c = *(s++), c != 0) {
h = HASH_POWER * h + (unsigned long)c;
}
return(h % HASH_SIZE);
}
/*
TYPE NAME HASHING FUNCTION
This routine calculates the hash value associated with the type t.
This is used in the look-up for the conversion function identifier
'operator t'.
*/
static unsigned long
hash_type(TYPE t)
{
unsigned long h = 0;
while (!IS_NULL_type(t)) {
unsigned long sub = 0;
unsigned long tag = (unsigned long)TAG_type(t);
CV_SPEC qual = DEREF_cv(type_qual(t));
switch (tag) {
case type_integer_tag: {
INT_TYPE it = DEREF_itype(type_integer_rep(t));
if (IS_itype_basic(it)) {
BUILTIN_TYPE no =
DEREF_ntype(itype_basic_no(it));
sub = (unsigned long)no;
}
t = NULL_type;
break;
}
case type_floating_tag: {
FLOAT_TYPE ft = DEREF_ftype(type_floating_rep(t));
if (IS_ftype_basic(ft)) {
BUILTIN_TYPE no =
DEREF_ntype(ftype_basic_no(ft));
sub = (unsigned long)no;
}
t = NULL_type;
break;
}
case type_ptr_tag:
case type_ref_tag:
t = DEREF_type(type_ptr_etc_sub(t));
break;
case type_ptr_mem_tag: {
CLASS_TYPE ct = DEREF_ctype(type_ptr_mem_of(t));
IDENTIFIER cid = DEREF_id(ctype_name(ct));
HASHID cnm = DEREF_hashid(id_name(cid));
sub = DEREF_ulong(hashid_hash(cnm));
t = DEREF_type(type_ptr_mem_sub(t));
break;
}
case type_func_tag: {
LIST(TYPE)p = DEREF_list(type_func_ptypes(t));
sub = (unsigned long)LENGTH_list(p);
t = DEREF_type(type_func_ret(t));
break;
}
case type_array_tag:
t = DEREF_type(type_array_sub(t));
break;
case type_bitfield_tag:
t = find_bitfield_type(t);
break;
case type_compound_tag: {
CLASS_TYPE ct = DEREF_ctype(type_compound_defn(t));
IDENTIFIER cid = DEREF_id(ctype_name(ct));
HASHID cnm = DEREF_hashid(id_name(cid));
sub = DEREF_ulong(hashid_hash(cnm));
t = NULL_type;
break;
}
case type_enumerate_tag: {
ENUM_TYPE et = DEREF_etype(type_enumerate_defn(t));
IDENTIFIER eid = DEREF_id(etype_name(et));
HASHID enm = DEREF_hashid(id_name(eid));
sub = DEREF_ulong(hashid_hash(enm));
t = NULL_type;
break;
}
default :
t = NULL_type;
break;
}
h += (64 * sub + 4 * tag + (unsigned long)qual);
}
return(h % HASH_TYPE_SIZE);
}
/*
INITIALISE A HASH TABLE ENTRY
This routine initialises the hash table entry nm by creating a dummy
identifier with lexical token value tok for it to point to.
*/
static void
init_hashid(HASHID nm, int tok)
{
IDENTIFIER id;
MAKE_id_dummy(nm, dspec_none, NULL_nspace, crt_loc, id);
COPY_ulong(id_no(id), (unsigned long)tok);
COPY_id(hashid_id(nm), id);
COPY_id(hashid_cache(nm), id);
return;
}
/*
LOOK UP AN IDENTIFIER NAME IN THE HASH TABLE
This routine looks up the identifier name s in the hash table, creating
it if it does not already exist. h gives the value of hash ( s ) (which
gets checked by an assertion). The argument tok is set to lex_unknown to
indicate that the identifier has just been read by read_token, otherwise
it gives the underlying default lexical token.
*/
HASHID
lookup_name(string s, unsigned long h, int ext, int tok)
{
unsigned tag;
unsigned long len;
HASHID prev = NULL_hashid;
HASHID nm = hash_table[h];
ASSERT(h == hash(s));
/* Search through existing entries */
while (!IS_NULL_hashid(nm)) {
string t = DEREF_string(hashid_name_etc_text(nm));
int c = ustrcmp(t, s);
if (c == 0) {
/* Name matches */
return(nm);
}
if (c > 0) {
break;
}
prev = nm;
nm = DEREF_hashid(hashid_next(nm));
}
/* Create new hash table entry */
len = (unsigned long)ustrlen(s);
if (tok == lex_unknown) {
s = xustrncpy(s, (gen_size)len);
tok = lex_identifier;
}
tag = hashid_name_tag;
if (ext) {
/* Check for extended identifiers */
string t = s;
while (t = ustrchr(t, char_backslash), t != NULL) {
t++;
if (*t == char_u) {
/* '\uxxxx' counts as one character */
len -= 5;
} else {
/* '\Uxxxxxxxx' counts as one character */
len -= 9;
}
}
tag = hashid_ename_tag;
}
MAKE_hashid_name_etc(tag, nm, h, s, nm);
if (IS_NULL_hashid(prev)) {
hash_table[h] = nm;
} else {
COPY_hashid(hashid_next(prev), nm);
}
init_hashid(nm, tok);
if (len >= max_id_length) {
/* Check name length */
IGNORE check_value(OPT_VAL_name_limit, len, nm);
}
return(nm);
}
/*
CREATE A SPECIAL FUNCTION NAME
This routine creates a constructor, destructor or conversion function
name (as indicated by tag) for the non-class type t named id.
*/
static HASHID
lookup_special(TYPE t, IDENTIFIER id, unsigned tag)
{
unsigned long h = hash_type(t);
HASHID prev = hash_type_table[h];
HASHID nm = prev;
/* Search through existing entries */
while (!IS_NULL_hashid(nm)) {
if (TAG_hashid(nm) == tag) {
TYPE s = DEREF_type(hashid_constr_etc_type(nm));
if (eq_type(s, t)) {
COPY_id(hashid_constr_etc_tid(nm), id);
return(nm);
}
}
nm = DEREF_hashid(hashid_next(nm));
}
/* Create new hash table entry */
ASSERT(h < HASH_SIZE);
MAKE_hashid_constr_etc(tag, prev, h, t, id, nm);
init_hashid(nm, lex_identifier);
hash_type_table[h] = nm;
return(nm);
}
/*
CREATE THE CONSTRUCTOR FOR A TYPE
This routine creates the hash table entry for the constructor of type t
and name id.
*/
HASHID
lookup_constr(TYPE t, IDENTIFIER id)
{
HASHID nm;
if (IS_type_compound(t)) {
CLASS_TYPE ct = DEREF_ctype(type_compound_defn(t));
IDENTIFIER cid = DEREF_id(ctype_constr(ct));
if (IS_NULL_id(cid)) {
/* Create class contructor */
NAMESPACE ns = DEREF_nspace(ctype_member(ct));
MAKE_hashid_constr(NULL_hashid, 0, t, id, nm);
init_hashid(nm, lex_identifier);
cid = DEREF_id(hashid_id(nm));
COPY_nspace(id_parent(cid), ns);
COPY_id(ctype_constr(ct), cid);
IGNORE search_member(ns, nm, 1);
} else {
nm = DEREF_hashid(id_name(cid));
}
} else {
nm = lookup_special(t, id, hashid_constr_tag);
}
return(nm);
}
/*
CREATE THE DESTRUCTOR FOR A TYPE
This routine creates the hash table entry for the destructor of type t
and name id.
*/
HASHID
lookup_destr(TYPE t, IDENTIFIER id)
{
HASHID nm;
if (IS_type_compound(t)) {
CLASS_TYPE ct = DEREF_ctype(type_compound_defn(t));
IDENTIFIER cid = DEREF_id(ctype_destr(ct));
if (IS_NULL_id(cid)) {
/* Create class destructor */
NAMESPACE ns = DEREF_nspace(ctype_member(ct));
MAKE_hashid_destr(NULL_hashid, 1, t, id, nm);
init_hashid(nm, lex_identifier);
cid = DEREF_id(hashid_id(nm));
COPY_nspace(id_parent(cid), ns);
COPY_id(ctype_destr(ct), cid);
IGNORE search_member(ns, nm, 1);
} else {
nm = DEREF_hashid(id_name(cid));
}
} else {
nm = lookup_special(t, id, hashid_destr_tag);
}
return(nm);
}
/*
LOOK UP A CONVERSION FUNCTION NAME
This routine returns the hash table entry for the conversion function
corresponding to the type t.
*/
HASHID
lookup_conv(TYPE t)
{
HASHID nm = lookup_special(t, NULL_id, hashid_conv_tag);
return(nm);
}
/*
OVERLOADED OPERATOR LOOK-UP TABLE
This table gives the hash table entries for the overloaded operator
function names, 'operator +' etc. It gives a straight look-up depending
on the lexical token number of the operator. All ISO keyword and
digraphs are represented in their primary form.
*/
HASHID *hash_ops_table;
/*
CREATE AN OPERATOR HASH TABLE ENTRY
This routine creates a hash table entry for 'operator op' when op has
lexical token number t.
*/
static HASHID
make_op(int t)
{
HASHID nm;
unsigned long h = (unsigned long)t;
MAKE_hashid_op(NULL_hashid, (h % HASH_SIZE), t, nm);
init_hashid(nm, lex_identifier);
return(nm);
}
/*
LOOK UP AN ANONYMOUS IDENTIFIER
This routine creates a hash table entry for an anonymous identifier.
Note that each anonymous identifier gives a distinct hash table entry.
*/
HASHID
lookup_anon(void)
{
HASHID nm;
static unsigned long anon_no = 0;
unsigned long a = anon_no++;
MAKE_hashid_anon(NULL_hashid, (a % HASH_SIZE), a, nm);
init_hashid(nm, lex_identifier);
return(nm);
}
/*
EXPAND AN IDENTIFIER NAME
This routine expands the identifier name nm. For example, if t is
a tokenised type defined to be int, then 'operator t' expands to
'operator int'. ct gives the expansion type for constructors and
destructors.
*/
HASHID
expand_name(HASHID nm, CLASS_TYPE ct)
{
switch (TAG_hashid(nm)) {
case hashid_constr_tag:
/* Constructor names */
if (!IS_NULL_ctype(ct)) {
IDENTIFIER id = DEREF_id(ctype_constr(ct));
nm = DEREF_hashid(id_name(id));
} else {
TYPE t = DEREF_type(hashid_constr_type(nm));
TYPE s = expand_type(t, 1);
if (!EQ_type(t, s)) {
nm = lookup_constr(s, NULL_id);
}
}
break;
case hashid_destr_tag:
/* Destructor names */
if (!IS_NULL_ctype(ct)) {
IDENTIFIER id = DEREF_id(ctype_destr(ct));
nm = DEREF_hashid(id_name(id));
} else {
TYPE t = DEREF_type(hashid_destr_type(nm));
TYPE s = expand_type(t, 1);
if (!EQ_type(t, s)) {
nm = lookup_destr(s, NULL_id);
}
}
break;
case hashid_conv_tag: {
/* Conversion function names */
TYPE t = DEREF_type(hashid_conv_type(nm));
TYPE s = expand_type(t, 1);
if (!EQ_type(t, s)) {
nm = lookup_conv(s);
}
break;
}
}
return(nm);
}
/*
FIND NEXT VERSION OF AN EXPANDED IDENTIFIER NAME
There is a complication in the expansion of conversion function names
in that when types are identified more than one name may refer to the
same type. This routine finds the next such possible name returning
the null identifier name to indicate that there are no more.
*/
HASHID
next_expand_name(HASHID nm)
{
if (IS_hashid_conv(nm)) {
int started = 0;
TYPE t = DEREF_type(hashid_conv_type(nm));
unsigned long h = hash_type(t);
HASHID pnm = hash_type_table[h];
while (!IS_NULL_hashid(pnm)) {
if (EQ_hashid(pnm, nm)) {
started = 1;
} else if (started && IS_hashid_conv(pnm)) {
TYPE s = DEREF_type(hashid_conv_type(pnm));
if (eq_type(s, t)) return(pnm);
}
pnm = DEREF_hashid(hashid_next(pnm));
}
}
return(NULL_hashid);
}
/*
FIND A HASH IDENTIFIER NUMBER
This routine finds the lexical token number associated with the hash
identifier nm. For a keyword, whether active or not, this is the
associated value from syntax.h, otherwise it is lex_identifier.
*/
int
find_hashid(HASHID nm)
{
unsigned long lex;
IDENTIFIER id = DEREF_id(hashid_id(nm));
while (!IS_id_dummy(id)) {
/* Scan to last hidden value */
id = DEREF_id(id_alias(id));
}
lex = DEREF_ulong(id_no(id));
return((int)lex);
}
/*
FIND AN UNDERLYING IDENTIFIER
This routine finds the dummy identifier underlying id.
*/
IDENTIFIER
underlying_id(IDENTIFIER id)
{
HASHID nm = DEREF_hashid(id_name(id));
id = DEREF_id(hashid_id(nm));
while (!IS_id_dummy(id)) {
/* Scan to last hidden value */
id = DEREF_id(id_alias(id));
}
return(id);
}
/*
SET THE LOCATION OF A COMPLEX IDENTIFIER
The precise location of the last use of a hash identifier is stored
in the loc field of its associated dummy identifier. For simple
identifiers this is set in read_token, however for more complex
cases this routine sets the location of id to be the location of pid.
*/
void
set_hashid_loc(IDENTIFIER id, IDENTIFIER pid)
{
if (!IS_NULL_id(pid)) {
LOCATION loc;
if (!IS_id_dummy(id)) {
id = underlying_id(id);
}
if (!IS_id_dummy(pid)) {
pid = underlying_id(pid);
}
DEREF_loc(id_loc(pid), loc);
COPY_loc(id_loc(id), loc);
}
return;
}
/*
MODIFY AN IDENTIFIER NAME
This routine modifies the name of the identifier id by adding a prime
to it. This is intended primarily for debugging purposes.
*/
void
prime_name(IDENTIFIER id)
{
if (!IS_NULL_id(id)) {
HASHID nm = DEREF_hashid(id_name(id));
if (IS_hashid_name(nm)) {
string s = DEREF_string(hashid_name_text(nm));
s = xustrcat(s, ustrlit("'"));
nm = lookup_name(s, hash(s), 0, lex_identifier);
}
COPY_hashid(id_name(id), nm);
}
return;
}
/*
KEYWORD HASH TABLE ENTRIES
The table hash_keyword gives the hash table entries for the keywords.
These are numbered from LAST_KEYWORD to FIRST_KEYWORD. The array
should be accessed through the macro KEYWORD defined in hash.h, which
includes the appropriate offset.
*/
HASHID hash_keyword[LAST_KEYWORD - FIRST_KEYWORD + 1];
IDENTIFIER underlying_op = NULL_id;
/*
INITIALISE THE HASH TABLE
This routine allocates space for the hash table and sets all its entries
to NULL. It also sets up the operator look-up table.
*/
void
init_hash(void)
{
int n;
unsigned long i;
/* Set up identifier hash table */
hash_table = xmalloc_nof(HASHID, HASH_SIZE);
for (i = 0; i < HASH_SIZE; i++) {
hash_table[i] = NULL_hashid;
}
/* Set up type hash table */
hash_type_table = xmalloc_nof(HASHID, HASH_TYPE_SIZE);
for (i = 0; i < HASH_TYPE_SIZE; i++) {
hash_type_table[i] = NULL_hashid;
}
/* Set up operator look-up table */
hash_ops_table = xmalloc_nof(HASHID, LAST_TOKEN + 1);
for (n = 0; n <= LAST_TOKEN; n++) {
hash_ops_table[n] = NULL_hashid;
}
/* Allocate hash table entries for all symbols */
for (n = FIRST_C_SYMBOL; n <= LAST_C_SYMBOL; n++) {
hash_ops_table[n] = make_op(n);
}
for (n = FIRST_CPP_SYMBOL; n <= LAST_CPP_SYMBOL; n++) {
hash_ops_table[n] = make_op(n);
}
for (n = FIRST_EXTRA_SYMBOL; n <= LAST_EXTRA_SYMBOL; n++) {
hash_ops_table[n] = make_op(n);
}
hash_ops_table[lex_array_Hop] = make_op(lex_array_Hop);
hash_ops_table[lex_cond_Hop] = make_op(lex_cond_Hop);
hash_ops_table[lex_delete] = make_op(lex_delete);
hash_ops_table[lex_delete_Harray] = make_op(lex_delete_Harray);
hash_ops_table[lex_func_Hop] = make_op(lex_func_Hop);
hash_ops_table[lex_new] = make_op(lex_new);
hash_ops_table[lex_new_Harray] = make_op(lex_new_Harray);
hash_ops_table[lex_alignof] = make_op(lex_alignof);
hash_ops_table[lex_sizeof] = make_op(lex_sizeof);
hash_ops_table[lex_typeid] = make_op(lex_typeid);
hash_ops_table[lex_vtable] = make_op(lex_vtable);
/* Map secondary representations to primary representations */
for (n = FIRST_DIGRAPH; n <= LAST_DIGRAPH; n++) {
int m = primary_form(n);
hash_ops_table[n] = hash_ops_table[m];
}
for (n = FIRST_ISO_KEYWORD; n <= LAST_ISO_KEYWORD; n++) {
int m = primary_form(n);
hash_ops_table[n] = hash_ops_table[m];
}
/* This is necessary for the definition of KEYWORD */
ASSERT(FIRST_KEYWORD == lex_auto);
return;
}