diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /graphics/asymptote/entry.h |
Initial commit
Diffstat (limited to 'graphics/asymptote/entry.h')
-rw-r--r-- | graphics/asymptote/entry.h | 535 |
1 files changed, 535 insertions, 0 deletions
diff --git a/graphics/asymptote/entry.h b/graphics/asymptote/entry.h new file mode 100644 index 0000000000..0c1441c6a0 --- /dev/null +++ b/graphics/asymptote/entry.h @@ -0,0 +1,535 @@ +/***** + * entry.h + * 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, a table of + * "entries" is used. + *****/ + +#ifndef ENTRY_H +#define ENTRY_H + +#include <iostream> + +#include "common.h" +#include "frame.h" +#include "table.h" +#include "types.h" +#include "modifier.h" + +using sym::symbol; +using types::ty; +using types::signature; + +// Forward declaration. +namespace types { +class record; +} +using types::record; + +namespace trans { + +// An entry is associated to a name in the (variable or type) environment, and +// has permission based on the enclosing records where it was defined or +// imported. +class entry : public gc { + struct pr { + permission perm; + record *r; + + pr(permission perm, record *r) + : perm(perm), r(r) {} + + // Returns true if the permission allows access in this context. + bool check(action act, coder &c); + + // Reports an error if permission is not allowed. + void report(action act, position pos, coder &c); + }; + + mem::list<pr> perms; + + void addPerm(permission perm, record *r) { + // Only store restrictive permissions. + if (perm != PUBLIC && r) + perms.push_back(pr(perm,r)); + } + + // The record where the variable or type is defined, or 0 if the entry is + // not a field. + record *where; + + // The location (file and line number) where the entry was defined. + position pos; + +public: + entry(record *where, position pos) : where(where), pos(pos) {} + entry(permission perm, record *r, record *where, position pos) + : where(where), pos(pos) { + addPerm(perm, r); + } + + // (Non-destructively) merges two entries, appending permission lists. + // The 'where' member is taken from the second entry. + entry(entry &e1, entry &e2); + + // Create an entry with one more permission in the list. + entry(entry &base, permission perm, record *r); + + bool checkPerm(action act, coder &c); + void reportPerm(action act, position pos, coder &c); + + record *whereDefined() { + return where; + } + + position getPos() { + return pos; + } +}; + +class varEntry : public entry { + ty *t; + access *location; + +public: + varEntry(ty *t, access *location, record *where, position pos) + : entry(where, pos), t(t), location(location) {} + + varEntry(ty *t, access *location, permission perm, record *r, + record *where, position pos) + : entry(perm, r, where, pos), t(t), location(location) {} + + // (Non-destructively) merges two varEntries, creating a qualified varEntry. + varEntry(varEntry &qv, varEntry &v); + + ty *getType() + { return t; } + + signature *getSignature() + { + return t->getSignature(); + } + + access *getLocation() + { return location; } + + frame *getLevel(); + + // Encodes the access, but also checks permissions. + void encode(action act, position pos, coder &c); + void encode(action act, position pos, coder &c, frame *top); +}; + +varEntry *qualifyVarEntry(varEntry *qv, varEntry *v); + +// As looked-up types can be allocated in a new expression, we need to know +// what frame they should be allocated on. Type entries store this extra +// information along with the type. +class tyEntry : public entry { +public: + ty *t; + varEntry *v; // NOTE: Name isn't very descriptive. + + tyEntry(ty *t, varEntry *v, record *where, position pos) + : entry(where, pos), t(t), v(v) {} + + tyEntry(tyEntry *base, permission perm, record *r) + : entry(*base, perm, r), t(base->t), v(base->v) {} + + // Records need a varEntry that refers back to the qualifier qv; i.e. in + // the last new of the code + // struct A { + // struct B {} + // } + // A a=new A; + // unravel a; + // new B; + // we need to put a's frame on the stack before allocating an instance of B. + // NOTE: A possible optimization could be to only qualify the varEntry if + // the type is a record, as other types don't use the varEntry. +private: + tyEntry(tyEntry *base, varEntry *qv) + : entry(*base, *qv), t(base->t), v(qualifyVarEntry(qv, base->v)) {} + +public: + // Since the constructor can only be used when qv is non-null it is private + // for safety reasons, and we provide this method instead. + friend tyEntry *qualifyTyEntry(varEntry *qv, tyEntry *ent); +}; + +inline tyEntry *qualifyTyEntry(varEntry *qv, tyEntry *ent) { + return qv ? new tyEntry(ent, qv) : ent; +} + +// The type environment. +class tenv : public sym::table<tyEntry *> { + bool add(symbol dest, names_t::value_type &x, varEntry *qualifier, + coder &c); +public: + // Add the entries in one environment to another, if qualifier is + // non-null, it is a record and the source environment is its types. The + // coder is used to see which entries are accessible and should be added. + void add(tenv& source, varEntry *qualifier, coder &c); + + // Adds entries of the name src in source as the name dest, returning true if + // any were added. + bool add(symbol src, symbol dest, + tenv& source, varEntry *qualifier, coder &c); +}; + +#if 0 //{{{ + /* This version of venv is provided for compiling on systems which do not + * have some form of STL hash table. It will eventually be removed. + * See the hash version below for documentation on the functions. + */ +/*NOHASH*/ class venv : public sym::table<varEntry*> { +/*NOHASH*/ public: +/*NOHASH*/ venv() {} +/*NOHASH*/ +/*NOHASH*/ struct file_env_tag {}; +/*NOHASH*/ venv(file_env_tag) {} +/*NOHASH*/ +/*NOHASH*/ void add(venv& source, varEntry *qualifier, coder &c); +/*NOHASH*/ +/*NOHASH*/ bool add(symbol src, symbol dest, +/*NOHASH*/ venv& source, varEntry *qualifier, coder &c); +/*NOHASH*/ +/*NOHASH*/ varEntry *lookByType(symbol name, ty *t); +/*NOHASH*/ +/*NOHASH*/ varEntry *lookBySignature(symbol name, signature *sig) { +/*NOHASH*/ // This optimization is not implemented for the NOHASH version. +/*NOHASH*/ return 0; +/*NOHASH*/ } +/*NOHASH*/ +/*NOHASH*/ ty *getType(symbol name); +/*NOHASH*/ +/*NOHASH*/ friend std::ostream& operator<< (std::ostream& out, +/*NOHASH*/ const venv& ve); +/*NOHASH*/ +/*NOHASH*/ void list(record *module=0); +/*NOHASH*/ }; + +//}}} +#else + +// For speed reasons, many asserts are only tested when DEBUG_CACHE is set. +#ifdef DEBUG_CACHE +#define DEBUG_CACHE_ASSERT(x) assert(x) +#else +#define DEBUG_CACHE_ASSERT(x) (void)(x) +#endif + +// The hash table which is at the core of the variable environment venv. +class core_venv : public gc { + +public: + // The cells of the table + struct cell { + symbol name; + varEntry *ent; + + bool empty() const { + return name == 0; + } + + bool isATomb() const { + DEBUG_CACHE_ASSERT(!empty()); + return ent == 0; + } + + bool filled() const { + return !empty() and !isATomb(); + } + + bool matches(symbol name, const ty *t) { + DEBUG_CACHE_ASSERT(name.special()); + DEBUG_CACHE_ASSERT(t); + + if (this->name != name) + return false; + if (!this->ent) + return false; + return equivalent(this->ent->getType(), t); + } + + bool matches(symbol name, const signature *sig) { + DEBUG_CACHE_ASSERT(!name.special()); + + if (this->name != name) + return false; + if (!this->ent) + return false; + return equivalent(this->ent->getSignature(), sig); + } + + void storeNew(symbol name, varEntry *ent) { + DEBUG_CACHE_ASSERT(empty() || isATomb()); + + this->name = name; + this->ent = ent; + } + + varEntry *replaceWith(symbol name, varEntry *ent) { + this->name = name; + + varEntry *old = this->ent; + this->ent = ent; + return old; + } + + void remove() { + this->ent = 0; + } + }; + +private: + size_t capacity; + size_t size; + size_t mask; + cell *table; + + void initTable(size_t capacity); + + void resize(); + + cell& cellByIndex(size_t i); + + const cell& cellByIndex(size_t i) const; + + varEntry *storeNew(cell& cell, symbol name, varEntry *ent); + + varEntry *storeNonSpecialAfterTomb(size_t tombIndex, + symbol name, varEntry *ent); + varEntry *storeSpecialAfterTomb(size_t tombIndex, + symbol name, varEntry *ent); + +public: + core_venv(size_t capacity) { + initTable(capacity); + } + + bool empty() const { return size == 0; } + void clear(); + + void confirm_size(); + + // Store an entry into the table. If this shadows a previous entry, the old + // entry is returned, otherwise 0 is returned. + varEntry *storeNonSpecial(symbol name, varEntry *ent); + varEntry *storeSpecial(symbol name, varEntry *ent); + varEntry *store(symbol name, varEntry *ent); + + // Lookup an entry in the table. + varEntry *lookupNonSpecial(symbol name, const signature *sig); + varEntry *lookupSpecial(symbol name, const ty *t); + varEntry *lookup(symbol name, const ty *t); + + // Remove an entry from the table. + void removeNonSpecial(symbol name, const signature *sig); + void removeSpecial(symbol name, const ty *t); + void remove(symbol name, const ty *t); + + // Features for iterating over the entire table. + class const_iterator { + const core_venv& core; + size_t index; + + public: + const_iterator(const core_venv& core, size_t index) + : core(core), index(index) {} + + const cell& operator * () const { + return core.cellByIndex(index); + } + const cell* operator -> () const { + return &core.cellByIndex(index); + } + + const_iterator& operator ++ () { + // Advance to the next filled cell, or stop at the end of the array. + do { + ++index; + } while (!(*this)->filled() && index < core.capacity); + + DEBUG_CACHE_ASSERT((*this)->filled() || (*this) == core.end()); + + return *this; + } + + friend bool operator == (const const_iterator& a, const const_iterator& b) + { + // For speed, we don't compare the hashtables. + return a.index == b.index; + } + friend bool operator != (const const_iterator& a, const const_iterator& b) + { + // For speed, we don't compare the hashtables. + return a.index != b.index; + } + }; + + const_iterator begin() const { + size_t index = 0; + while (index < capacity && !cellByIndex(index).filled()) + ++index; + return const_iterator(*this, index); + } + + const_iterator end() const { + return const_iterator(*this, capacity); + } +}; + + +// venv implemented with a hash table. +class venv { + // A hash table used to quickly look up a variable once its name and type are + // known. Includes all scopes. + core_venv core; + + // Record of added variables in the order they were added. + struct addition { + symbol name; + ty *t; + varEntry *shadowed; + + addition(symbol name, ty *t, varEntry *shadowed) + : name(name), t(t), shadowed(shadowed) {} + }; + typedef mem::stack<addition> addstack; + addstack additions; + + // A scope can be recorded by the size of the addition stack at the time the + // scope began. + typedef mem::stack<size_t> scopestack; + scopestack scopesizes; + + + struct namehash { + size_t operator()(const symbol name) const { + return name.hash(); + } + }; + struct nameeq { + bool operator()(const symbol s, const symbol t) const { + return s==t; + } + }; + + struct namevalue { + size_t maxFormals; + ty *t; + + namevalue() : maxFormals(0), t(0) {} + + void addType(ty *s); + + void replaceType(ty *new_t, ty *old_t); + +#if DEBUG_CACHE + void popType(ty *tnew); +#else + void popType(); +#endif + }; + + // A dictionary indexed solely on the name, storing for each name the + // current (possibly overloaded) type of the name. + // The hash table implementation is slightly faster than the std::map binary + // tree implementation, so we use it if we can. +#ifdef NOHASH + typedef mem::map<symbol CONST, namevalue> namemap; +#else + typedef mem::unordered_map<symbol, namevalue, namehash, nameeq> namemap; +#endif + namemap names; + + + // A sanity check. For a given name, it checks that the type stored in the + // names hash table exactly matches with all of the entries of that name + // stored in the full hash table. + void checkName(symbol name); + + void listValues(symbol name, record *module); + + + // Helper function for endScope. + void remove(const addition& a); + + // These are roughly the size the hashtables will be after loading the + // builtin functions and plain module. + static const size_t fileCoreSize=1 << 13; + static const size_t fileNamesSize=1000; + + // The number of scopes begun (but not yet ended) when the venv was empty. + size_t empty_scopes; +public: + venv() : + core(1 << 2), empty_scopes(0) {} + + // Most file level modules automatically import plain, so allocate hashtables + // big enough to hold it in advance. + struct file_env_tag {}; + venv(file_env_tag) + : core(fileCoreSize), +#ifndef NOHASH + names(fileNamesSize), +#endif + empty_scopes(0) {} + + // Add a new variable definition. + void enter(symbol name, varEntry *v); + + // Add the entries in one environment to another, if qualifier is + // non-null, it is a record and entries of the source environment are its + // fields. The coder is necessary to check which variables are accessible and + // should be added. + void add(venv& source, varEntry *qualifier, coder &c); + + // Add all unshadowed variables from source of the name src as variables + // named dest. Returns true if at least one was added. + bool add(symbol src, symbol dest, + venv& source, varEntry *qualifier, coder &c); + + // Look for a function that exactly matches the type given. + varEntry *lookByType(symbol name, ty *t) { + return core.lookup(name, t); + } + + // An optimization heuristic. Try to guess the signature of a variable and + // look it up. This is allowed to return 0 even if the appropriate variable + // exists. If it returns a varEntry from an overloaded number of choices, + // the returned function must be the one which would be called with + // arguments given by sig, and its signature must be equivalent to sig. + // For instance, in + // int f(int a, int b); + // int f(int a, int b, int c = 1); + // f(a,b); + // looking up the signature of 'f' with arguments (int, int) must return 0 + // as there is an ambiguity. The maxFormals field is used to ensure we + // avoid such ambiguities. + varEntry *lookBySignature(symbol name, signature *sig); + + // Get the (possibly overloaded) type of all variables associated to a + // particular name. + ty *getType(symbol name); + + void beginScope(); + void endScope(); + + // Merges the top-level scope with the level immediately underneath it. + void collapseScope(); + + // Prints a list of the variables to the standard output. + void list(record *module=0); + + // Adds to l, all names prefixed by start. + void completions(mem::list<symbol>& l, string start); +}; +#endif + +} // namespace trans + +#endif //ENTRY_H |