/*****
* entry.cc
* Andy Hammerlindl 2002/08/29
*
* All variables, built-in functions and user-defined functions reside
* within the same namespace. To keep track of all these, table of
* "entries" is used.
*****/
#include <iostream>
#include <cmath>
#include <cstring>
#include <utility>
#include "entry.h"
#include "coder.h"
using std::memset;
using types::ty;
using types::signature;
using types::overloaded;
using types::ty_vector;
using types::ty_iterator;
namespace trans {
bool entry::pr::check(action act, coder &c) {
// We assume PUBLIC permissions and one's without an associated record are not
// stored.
assert(perm!=PUBLIC && r!=0);
return c.inTranslation(r->getLevel()) ||
(perm == RESTRICTED && act != WRITE);
}
void entry::pr::report(action act, position pos, coder &c) {
if (!c.inTranslation(r->getLevel())) {
if (perm == PRIVATE) {
em.error(pos);
em << "accessing private field outside of structure";
}
else if (perm == RESTRICTED && act == WRITE) {
em.error(pos);
em << "modifying non-public field outside of structure";
}
}
}
entry::entry(entry &e1, entry &e2) : where(e2.where), pos(e2.pos) {
perms.insert(perms.end(), e1.perms.begin(), e1.perms.end());
perms.insert(perms.end(), e2.perms.begin(), e2.perms.end());
}
entry::entry(entry &base, permission perm, record *r)
: where(base.where), pos(base.pos) {
perms.insert(perms.end(), base.perms.begin(), base.perms.end());
addPerm(perm, r);
}
bool entry::checkPerm(action act, coder &c) {
for (mem::list<pr>::iterator p=perms.begin(); p != perms.end(); ++p)
if (!p->check(act, c))
return false;
return true;
}
void entry::reportPerm(action act, position pos, coder &c) {
for (mem::list<pr>::iterator p=perms.begin(); p != perms.end(); ++p)
p->report(act, pos, c);
}
varEntry::varEntry(varEntry &qv, varEntry &v)
: entry(qv,v), t(v.t),
location(new qualifiedAccess(qv.location, qv.getLevel(), v.location)) {}
frame *varEntry::getLevel() {
record *r=dynamic_cast<record *>(t);
assert(r);
return r->getLevel();
}
void varEntry::encode(action act, position pos, coder &c) {
reportPerm(act, pos, c);
getLocation()->encode(act, pos, c);
}
void varEntry::encode(action act, position pos, coder &c, frame *top) {
reportPerm(act, pos, c);
getLocation()->encode(act, pos, c, top);
}
varEntry *qualifyVarEntry(varEntry *qv, varEntry *v)
{
return qv ? (v ? new varEntry(*qv,*v) : qv) : v;
}
bool tenv::add(symbol dest,
names_t::value_type &x, varEntry *qualifier, coder &c)
{
if (!x.second.empty()) {
tyEntry *ent=x.second.front();
if (ent->checkPerm(READ, c)) {
enter(dest, qualifyTyEntry(qualifier, ent));
return true;
}
}
return false;
}
void tenv::add(tenv& source, varEntry *qualifier, coder &c) {
// Enter each distinct (unshadowed) name,type pair.
for(names_t::iterator p = source.names.begin(); p != source.names.end(); ++p)
add(p->first, *p, qualifier, c);
}
bool tenv::add(symbol src, symbol dest,
tenv& source, varEntry *qualifier, coder &c) {
names_t::iterator p = source.names.find(src);
if (p != source.names.end())
return add(dest, *p, qualifier, c);
else
return false;
}
// To avoid writing qualifiers everywhere.
typedef core_venv::cell cell;
void core_venv::initTable(size_t capacity) {
// Assert that capacity is a power of two.
assert((capacity & (capacity-1)) == 0);
this->capacity = capacity;
size = 0;
mask = capacity - 1;
table = new (UseGC) cell[capacity];
memset(table, 0, sizeof(cell) * capacity);
}
void core_venv::clear() {
if (size != 0) {
memset(table, 0, sizeof(cell) * capacity);
size = 0;
}
}
void core_venv::resize() {
size_t oldCapacity = capacity;
size_t oldSize = size;
cell *oldTable = table;
initTable(capacity * 4);
for (size_t i = 0; i < oldCapacity; ++i) {
cell& b = oldTable[i];
if (!b.empty() && !b.isATomb()) {
varEntry *old = store(b.name, b.ent);
// We should not be shadowing anything when reconstructing the table.
DEBUG_CACHE_ASSERT(old == 0);
}
}
assert(size == oldSize);
#if DEBUG_CACHE
confirm_size();
for (size_t i = 0; i < oldCapacity; ++i) {
cell& b = oldTable[i];
if (!b.empty() && !b.isATomb()) {
assert(lookup(b.name, b.ent->getType()) == b.ent);
}
}
#endif
//cout << "resized from " << oldCapacity << " to " << capacity << endl;
}
cell& core_venv::cellByIndex(size_t i) {
return table[i & mask];
}
const cell& core_venv::cellByIndex(size_t i) const {
return table[i & mask];
}
void core_venv::confirm_size() {
size_t sum = 0;
for (size_t i = 0; i < capacity; ++i) {
cell& b = table[i];
if (!b.empty() && !b.isATomb())
++sum;
}
assert(sum == size);
}
varEntry *core_venv::storeNew(cell& cell, symbol name, varEntry *ent) {
// Store the value into the cell.
cell.storeNew(name, ent);
// We now have a new entry. Update the size.
++size;
// Check if the hash table has grown too big and needs to be expanded.
if (2*size > capacity)
resize();
// Nothing is shadowed.
return 0;
}
varEntry *core_venv::storeNonSpecialAfterTomb(size_t tombIndex,
symbol name, varEntry *ent) {
DEBUG_CACHE_ASSERT(name.notSpecial());
DEBUG_CACHE_ASSERT(ent);
DEBUG_CACHE_ASSERT(ent->getType());
signature *sig = ent->getSignature();
for (size_t i = tombIndex+1; ; ++i)
{
cell& b = cellByIndex(i);
if (b.empty())
return storeNew(cellByIndex(tombIndex), name, ent);
if (b.matches(name, sig))
return b.replaceWith(name, ent);
}
}
varEntry *core_venv::storeSpecialAfterTomb(size_t tombIndex,
symbol name, varEntry *ent) {
DEBUG_CACHE_ASSERT(name.special());
DEBUG_CACHE_ASSERT(ent);
DEBUG_CACHE_ASSERT(ent->getType());
ty *t = ent->getType();
for (size_t i = tombIndex+1; ; ++i)
{
cell& b = cellByIndex(i);
if (b.empty())
return storeNew(cellByIndex(tombIndex), name, ent);
if (b.matches(name, t))
return b.replaceWith(name, ent);
}
}
size_t hashSig(const signature *sig) {
return sig ? sig->hash() : 0;
}
size_t nonSpecialHash(symbol name, const signature *sig) {
return name.hash() * 107 + hashSig(sig);
}
size_t nonSpecialHash(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(t);
return nonSpecialHash(name, t->getSignature());
}
size_t specialHash(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(t);
return name.hash() * 107 + t->hash();
}
varEntry *core_venv::storeNonSpecial(symbol name, varEntry *ent) {
DEBUG_CACHE_ASSERT(name.notSpecial());
DEBUG_CACHE_ASSERT(ent);
DEBUG_CACHE_ASSERT(ent->getType());
signature *sig = ent->getSignature();
for (size_t i = nonSpecialHash(name, sig); ; ++i)
{
cell& b = cellByIndex(i);
if (b.empty())
return storeNew(b, name, ent);
if (b.matches(name, sig))
return b.replaceWith(name, ent);
if (b.isATomb())
return storeNonSpecialAfterTomb(i, name, ent);
}
}
varEntry *core_venv::storeSpecial(symbol name, varEntry *ent) {
DEBUG_CACHE_ASSERT(name.special());
DEBUG_CACHE_ASSERT(ent);
DEBUG_CACHE_ASSERT(ent->getType());
ty *t = ent->getType();
for (size_t i = specialHash(name, t); ; ++i)
{
cell& b = cellByIndex(i);
if (b.empty())
return storeNew(b, name, ent);
if (b.matches(name, t))
return b.replaceWith(name, ent);
if (b.isATomb())
return storeSpecialAfterTomb(i, name, ent);
}
}
varEntry *core_venv::store(symbol name, varEntry *ent) {
DEBUG_CACHE_ASSERT(ent);
DEBUG_CACHE_ASSERT(ent->getType());
return name.special() ? storeSpecial(name, ent) :
storeNonSpecial(name, ent);
}
varEntry *core_venv::lookupSpecial(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(name.special());
DEBUG_CACHE_ASSERT(t);
for (size_t i = specialHash(name, t); ; ++i)
{
cell& b = cellByIndex(i);
if (b.matches(name, t))
return b.ent;
if (b.empty())
return 0;
}
}
varEntry *core_venv::lookupNonSpecial(symbol name, const signature *sig) {
DEBUG_CACHE_ASSERT(name.notSpecial());
for (size_t i = nonSpecialHash(name, sig); ; ++i)
{
cell& b = cellByIndex(i);
if (b.matches(name, sig))
return b.ent;
if (b.empty())
return 0;
}
}
varEntry *core_venv::lookup(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(t);
return name.special() ? lookupSpecial(name, t) :
lookupNonSpecial(name, t->getSignature());
}
void core_venv::removeNonSpecial(symbol name, const signature *sig) {
DEBUG_CACHE_ASSERT(name.notSpecial());
for (size_t i = nonSpecialHash(name, sig); ; ++i)
{
cell& b = cellByIndex(i);
if (b.matches(name, sig)) {
b.remove();
--size;
return;
}
DEBUG_CACHE_ASSERT(!b.empty());
}
}
void core_venv::removeSpecial(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(name.special());
DEBUG_CACHE_ASSERT(t);
for (size_t i = specialHash(name, t); ; ++i)
{
cell& b = cellByIndex(i);
if (b.matches(name, t)) {
b.remove();
--size;
return;
}
DEBUG_CACHE_ASSERT(!b.empty());
}
}
void core_venv::remove(symbol name, const ty *t) {
DEBUG_CACHE_ASSERT(t);
if (name.special())
removeSpecial(name, t);
else
removeNonSpecial(name, t->getSignature());
}
size_t numFormals(ty *t) {
signature *sig = t->getSignature();
return sig ? sig->getNumFormals() : 0;
}
void venv::checkName(symbol name)
{
#if 0
// This size test is too slow, even for DEBUG_CACHE.
core.confirm_size();
#endif
// Get the type, and make it overloaded if it is not (for uniformity).
overloaded o;
ty *t = getType(name);
if (!t)
t = &o;
if (!t->isOverloaded()) {
o.add(t);
t = &o;
}
assert(t->isOverloaded());
size_t maxFormals = names[name].maxFormals;
size_t size = 0;
for (ty_iterator i = t->begin(); i != t->end(); ++i) {
assert(numFormals(*i) <= maxFormals);
varEntry *v = lookByType(name, *i);
assert(v);
assert(equivalent(v->getType(), *i));
++size;
}
size_t matches = 0;
core_venv::const_iterator end = core.end();
for (core_venv::const_iterator p = core.begin(); p != end; ++p) {
if (p->name == name) {
++matches;
varEntry *v=p->ent;
assert(v);
assert(equivalent(t, v->getType()));
}
}
assert(matches == size);
}
void rightKind(ty *t) {
if (t && t->isOverloaded()) {
ty_vector& set=((overloaded *)t)->sub;
assert(set.size() > 1);
}
}
#ifdef DEBUG_CACHE
#define RIGHTKIND(t) (rightKind(t))
#define CHECKNAME(name) (checkName(name))
#else
#define RIGHTKIND(t) (void)(t)
#define CHECKNAME(name) (void)(name)
#endif
void venv::namevalue::addType(ty *s) {
RIGHTKIND(t);
#ifdef DEBUG_CACHE
assert(!s->isOverloaded());
#endif
if (t == 0) {
maxFormals = numFormals(s);
t = s;
} else {
if (!t->isOverloaded())
t = new overloaded(t);
#ifdef DEBUG_CACHE
assert(t->isOverloaded());
assert(!equivalent(t, s));
#endif
((overloaded *)t)->add(s);
size_t n = numFormals(s);
if (n > maxFormals)
maxFormals = n;
}
RIGHTKIND(t);
}
void venv::namevalue::replaceType(ty *new_t, ty *old_t) {
#ifdef DEBUG_CACHE
assert(t != 0);
RIGHTKIND(t);
#endif
// TODO: Test for equivalence.
if (t->isOverloaded()) {
for (ty_iterator i = t->begin(); i != t->end(); ++i) {
if (equivalent(old_t, *i)) {
*i = new_t;
return;
}
}
// An error, the type was not found.
assert("unreachable code" == 0);
} else {
#ifdef DEBUG_CACHE
assert(equivalent(old_t, t));
#endif
t = new_t;
}
#ifdef DEBUG_CACHE
assert(t != 0);
RIGHTKIND(t);
#endif
}
#ifdef DEBUG_CACHE
void venv::namevalue::popType(ty *s)
#else
void venv::namevalue::popType()
#endif
{
#ifdef DEBUG_CACHE
assert(t);
RIGHTKIND(t);
assert(!s->isOverloaded());
#endif
if (t->isOverloaded()) {
ty_vector& set=((overloaded *)t)->sub;
#ifdef DEBUG_CACHE
assert(set.size() > 0);
assert(equivalent(set.back(), s));
#endif
// We are relying on the fact that this was the last type added to t, and
// that type are added by pushing them on the end of the vector.
set.pop_back();
if (set.size() == 1)
t = set.front();
} else {
#ifdef DEBUG_CACHE
assert(equivalent(t, s));
#endif
t = 0;
}
RIGHTKIND(t);
// Don't try to reduce numFormals as I doubt it is worth the cost of
// recalculating.
}
void venv::remove(const addition& a) {
CHECKNAME(a.name);
if (a.shadowed) {
varEntry *popEnt = core.store(a.name, a.shadowed);
DEBUG_CACHE_ASSERT(popEnt);
// Unshadow the previously shadowed varEntry.
names[a.name].replaceType(a.shadowed->getType(), popEnt->getType());
}
else {
// Remove the (name,sig) key completely.
#if DEBUG_CACHE
varEntry *popEnt = core.lookup(a.name, a.t);
assert(popEnt);
names[a.name].popType(popEnt->getType());
#else
names[a.name].popType();
#endif
core.remove(a.name, a.t);
}
CHECKNAME(a.name);
}
void venv::beginScope() {
if (core.empty()) {
assert(scopesizes.empty());
++empty_scopes;
} else {
scopesizes.push(additions.size());
}
}
void venv::endScope() {
if (scopesizes.empty()) {
// The corresponding beginScope happened when the venv was empty, so
// clear the hash tables to return to that state.
core.clear();
names.clear();
assert(empty_scopes > 0);
--empty_scopes;
} else {
size_t scopesize = scopesizes.top();
assert(additions.size() >= scopesize);
while (additions.size() > scopesize) {
remove(additions.top());
additions.pop();
}
scopesizes.pop();
}
}
// Adds the definitions of the top-level scope to the level underneath,
// and then removes the top scope.
void venv::collapseScope() {
if (scopesizes.empty()) {
// Collapsing an empty scope.
assert(empty_scopes > 0);
--empty_scopes;
} else {
// As scopes are stored solely by the number of entries at the beginning
// of the scope, popping the top size will put all of the entries into the
// next scope down.
scopesizes.pop();
}
}
void venv::enter(symbol name, varEntry *v)
{
CHECKNAME(name);
// Store the new variable. If it shadows an older variable, that varEntry
// will be returned.
varEntry *shadowed = core.store(name, v);
ty *t = v->getType();
// Record the addition, so it can be undone during endScope.
if (!scopesizes.empty())
additions.push(addition(name, t, shadowed));
if (shadowed)
// The new value shadows an old value. They have the same signature, but
// possibly different return types. If necessary, update the type stored
// by name.
names[name].replaceType(t, shadowed->getType());
else
// Add to the names hash table.
names[name].addType(t);
CHECKNAME(name);
}
varEntry *venv::lookBySignature(symbol name, signature *sig) {
// Rest arguments are complicated and rare. Don't handle them here.
if (sig->hasRest())
return 0;
// Likewise with the special operators.
if (name.special())
return 0;
namevalue& nv = names[name];
// Avoid ambiguities with default parameters.
if (nv.maxFormals != sig->getNumFormals())
return 0;
// See if this exactly matches a function in the table.
varEntry *ve = core.lookupNonSpecial(name, sig);
if (!ve)
return 0;
// Keyword-only arguments may cause matching to fail.
if (ve->getSignature()->numKeywordOnly > 0)
return 0;
// At this point, any function with an equivalent signature will be equal
// to the result of the normal overloaded function resolution. We may
// safely return it.
return ve;
}
void venv::add(venv& source, varEntry *qualifier, coder &c)
{
core_venv::const_iterator end = source.core.end();
for (core_venv::const_iterator p = source.core.begin(); p != end; ++p)
{
DEBUG_CACHE_ASSERT(p->filled());
varEntry *v=p->ent;
if (v->checkPerm(READ, c)) {
enter(p->name, qualifyVarEntry(qualifier, v));
}
}
}
bool venv::add(symbol src, symbol dest,
venv& source, varEntry *qualifier, coder &c)
{
ty *t=source.getType(src);
if (!t)
return false;
if (t->isOverloaded()) {
bool added=false;
for (ty_iterator i = t->begin(); i != t->end(); ++i)
{
varEntry *v=source.lookByType(src, *i);
if (v->checkPerm(READ, c)) {
enter(dest, qualifyVarEntry(qualifier, v));
added=true;
}
}
return added;
}
else {
varEntry *v=source.lookByType(src, t);
if (v->checkPerm(READ, c)) {
enter(dest, qualifyVarEntry(qualifier, v));
return true;
}
return false;
}
}
ty *venv::getType(symbol name)
{
return names[name].t;
}
void listValue(symbol name, varEntry *v, record *module)
{
if (!module || v->whereDefined() == module)
{
if (settings::getSetting<bool>("where"))
cout << v->getPos();
v->getType()->printVar(cout, name);
cout << ";\n";
}
}
void venv::listValues(symbol name, record *module)
{
ty *t=getType(name);
if (t->isOverloaded())
for (ty_iterator i = t->begin(); i != t->end(); ++i)
listValue(name, lookByType(name, *i), module);
else
listValue(name, lookByType(name, t), module);
flush(cout);
}
void venv::list(record *module)
{
// List all functions and variables.
for (namemap::iterator N = names.begin(); N != names.end(); ++N)
listValues(N->first, module);
}
void venv::completions(mem::list<symbol >& l, string start)
{
for(namemap::iterator N = names.begin(); N != names.end(); ++N)
if (prefix(start, N->first) && N->second.t)
l.push_back(N->first);
}
} // namespace trans