From 4e8485b0ddecb55f72929dd6233f254a1e7bf5b0 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sun, 11 Jul 2010 22:39:53 +0000 Subject: asy 2.02 git-svn-id: svn://tug.org/texlive/trunk@19378 c570f23f-e606-0410-a88d-b1316a301751 --- Build/source/utils/asymptote/entry.cc | 441 ++++++++++++++++++++++++++-------- 1 file changed, 341 insertions(+), 100 deletions(-) (limited to 'Build/source/utils/asymptote/entry.cc') diff --git a/Build/source/utils/asymptote/entry.cc b/Build/source/utils/asymptote/entry.cc index 325438f48d3..d133571f136 100644 --- a/Build/source/utils/asymptote/entry.cc +++ b/Build/source/utils/asymptote/entry.cc @@ -10,10 +10,12 @@ #include #include +#include #include #include "entry.h" #include "coder.h" +using std::memset; using types::ty; using types::signature; using types::overloaded; @@ -121,7 +123,7 @@ bool tenv::add(symbol src, symbol dest, return false; } -#ifdef NOHASH //{{{ +#if 0 //{{{ /*NOHASH*/ void venv::add(venv& source, varEntry *qualifier, coder &c) /*NOHASH*/ { /*NOHASH*/ // Enter each distinct (unshadowed) name,type pair. @@ -205,38 +207,283 @@ bool tenv::add(symbol src, symbol dest, // }}} #else -ostream& operator<< (ostream& out, const venv::key &k) { - if(k.special) - k.u.t->printVar(out, k.name); - else { - out << k.name; - if (k.u.sig) - out << *k.u.sig; +// 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; } - return out; } -#if TEST_COLLISION -bool venv::keyeq::operator()(const key k, const key l) const { - keyhash kh; - if (kh(k)==kh(l)) { - if (base(k,l)) - return true; - else { - cerr << "collision: " << endl; - cerr << " " << k << " -> " << kh(k) << endl; - cerr << " " << l << " -> " << kh(l) << endl; +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); } } - return false; + + 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; } -#else -bool venv::keyeq::operator()(const key k, const key l) const { - return k.name==l.name && - (k.special ? equivalent(k.u.t, l.u.t) : - equivalent(k.u.sig, l.u.sig)); + +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()); + } } -#endif + +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()); +} + #ifdef CALLEE_SEARCH size_t numFormals(ty *t) { @@ -247,7 +494,10 @@ size_t numFormals(ty *t) { void venv::checkName(symbol name) { - // TODO: test maxFormals +#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; @@ -260,8 +510,11 @@ void venv::checkName(symbol name) } 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)); @@ -269,11 +522,12 @@ void venv::checkName(symbol name) } size_t matches = 0; - for (keymap::iterator p = all.begin(); p != all.end(); ++p) { - if (p->first.name == name) { + 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->second.v; + varEntry *v=p->ent; assert(v); assert(equivalent(t, v->getType())); } @@ -334,6 +588,8 @@ void venv::namevalue::replaceType(ty *new_t, ty *old_t) { assert(t != 0); RIGHTKIND(t); #endif + + // TODO: Test for equivalence. if (t->isOverloaded()) { for (ty_iterator i = t->begin(); i != t->end(); ++i) { @@ -399,33 +655,34 @@ void venv::namevalue::popType() } void venv::remove(const addition& a) { - CHECKNAME(a.k.name); + CHECKNAME(a.name); - value &val=all[a.k]; + if (a.shadowed) { + varEntry *popEnt = core.store(a.name, a.shadowed); -#ifdef DEBUG_CACHE - assert(val); -#endif + DEBUG_CACHE_ASSERT(popEnt); - if (a.shadowed) { // Unshadow the previously shadowed varEntry. - names[a.k.name].replaceType(a.shadowed->getType(), val.v->getType()); - val.v = a.shadowed; - } else { + names[a.name].replaceType(a.shadowed->getType(), popEnt->getType()); + } + else { // Remove the (name,sig) key completely. #if DEBUG_CACHE - names[a.k.name].popType(val.v->getType()); + varEntry *popEnt = core.lookup(a.name, a.t); + assert(popEnt); + names[a.name].popType(popEnt->getType()); #else - names[a.k.name].popType(); + names[a.name].popType(); #endif - all.erase(a.k); + + core.remove(a.name, a.t); } - CHECKNAME(a.k.name); + CHECKNAME(a.name); } void venv::beginScope() { - if (all.empty()) { + if (core.empty()) { assert(scopesizes.empty()); ++empty_scopes; } else { @@ -437,7 +694,7 @@ 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. - all.clear(); + core.clear(); names.clear(); assert(empty_scopes > 0); @@ -461,6 +718,9 @@ void venv::collapseScope() { 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(); } } @@ -470,30 +730,24 @@ void venv::enter(symbol name, varEntry *v) { CHECKNAME(name); - key k(name, v); + // Store the new variable. If it shadows an older variable, that varEntry + // will be returned. + varEntry *shadowed = core.store(name, v); - value &slot=all[k]; - if (slot.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(v->getType(), slot.v->getType()); - - // Replace the old value, but store its now-shadowed varEntry. - if (!scopesizes.empty()) - additions.push(addition(k, slot.v)); - - slot.v = v; - - } else { + names[name].replaceType(t, shadowed->getType()); + else // Add to the names hash table. - names[name].addType(v->getType()); - - if (!scopesizes.empty()) - additions.push(addition(k, 0)); - - slot.v=v; - } + names[name].addType(t); CHECKNAME(name); } @@ -502,58 +756,41 @@ void venv::enter(symbol name, varEntry *v) varEntry *venv::lookBySignature(symbol name, signature *sig) { #ifdef CALLEE_SEARCH // Rest arguments are complicated and rare. Don't handle them here. - if (sig->hasRest()) { -#if 0 - if (lookByType(key(name, sig))) - cout << "FAIL BY REST ARG" << endl; - else - cout << "FAIL BY REST ARG AND NO-MATCH" << endl; -#endif + if (sig->hasRest()) return 0; - } // Likewise with the special operators. - if (name.special()) { - //cout << "FAIL BY SPECIAL" << endl; + if (name.special()) return 0; - } namevalue& nv = names[name]; // Avoid ambiguities with default parameters. - if (nv.maxFormals != sig->getNumFormals()) { -#if 0 - if (lookByType(key(name, sig))) - cout << "FAIL BY NUMARGS" << endl; - else - cout << "FAIL BY NUMARGS AND NO-MATCH" << endl; -#endif + if (nv.maxFormals != sig->getNumFormals()) return 0; - } // At this point, any function with an equivalent an signature will be equal // to the result of the normal overloaded function resolution. We may // safely return it. - varEntry *result = lookByType(key(name, sig)); -#if 0 - if (!result) { - cout << "FAIL BY NO-MATCH" << endl; - } -#endif - return result; + return core.lookupNonSpecial(name, sig); + #else - // The maxFormals field is necessary for this optimization. + // If the optimization is disabled, always return 0. return 0; #endif } void venv::add(venv& source, varEntry *qualifier, coder &c) { - // Enter each distinct (unshadowed) name,type pair. - for(keymap::iterator p = source.all.begin(); p != source.all.end(); ++p) { - varEntry *v=p->second.v; - if (v->checkPerm(READ, c)) - enter(p->first.name, qualifyVarEntry(qualifier, v)); + 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)); + } } } @@ -561,11 +798,14 @@ bool venv::add(symbol src, symbol dest, venv& source, varEntry *qualifier, coder &c) { ty *t=source.getType(src); + if (!t) return false; - else if (t->isOverloaded()) { + + if (t->isOverloaded()) { bool added=false; - for (ty_iterator i = t->begin(); i != t->end(); ++i) { + 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)); @@ -573,7 +813,8 @@ bool venv::add(symbol src, symbol dest, } } return added; - } else { + } + else { varEntry *v=source.lookByType(src, t); if (v->checkPerm(READ, c)) { enter(dest, qualifyVarEntry(qualifier, v)); @@ -629,6 +870,6 @@ void venv::completions(mem::list& l, string start) l.push_back(N->first); } -#endif +#endif /* not NOHASH */ } // namespace trans -- cgit v1.2.3