/*****
* 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);

 // Copies the original varEntry and adds a new permission constraint.
 varEntry(varEntry &base, permission perm, record *r)
   : entry(base, perm, r), t(base.t), location(base.location) {}

 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 *> {
 tyEntry *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.
 tyEntry *add(symbol src, symbol dest,
              tenv& source, varEntry *qualifier, coder &c);
};


// For speed reasons, many asserts are only tested when DEBUG_CACHE is set.
#ifndef DEBUG_CACHE_ASSERT
#  ifdef DEBUG_CACHE
#    define DEBUG_CACHE_ASSERT(x) assert(x)
#  else
#    define DEBUG_CACHE_ASSERT(x) (void)(x)
#  endif
#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);
 }
};

struct SigHash {
 size_t operator()(const mem::pair<symbol, ty *>& p) const;
};

struct SigEquiv {
 bool operator()(const mem::pair<symbol, ty *>& p1,
                 const mem::pair<symbol, ty *>& p2) const;
};

enum class AutounravelPriority {
 OFFER,
 FORCE,
};

// 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 list of variables that need to be unraveled whenever the containing
 // record (if any) becomes available.
 mem::list<mem::pair<symbol, varEntry *>> autoUnravels;
 mem::unordered_map<mem::pair<symbol, ty*>,
                    std::nullptr_t,
                    SigHash,
                    SigEquiv> nonShadowableAutoUnravels;

 // 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(astType *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.
 typedef mem::unordered_map<symbol, namevalue, namehash, nameeq> namemap;
 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),
     names(fileNamesSize),
     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,
          mem::vector<varEntry *> *addedVec=nullptr);

 // 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);

 void registerAutoUnravel(
   symbol name,
   varEntry *v,
   AutounravelPriority priority=AutounravelPriority::FORCE
 );

 const mem::list<mem::pair<symbol, varEntry *>>& getAutoUnravels() {
   return autoUnravels;
 }
};

} // namespace trans

#endif //ENTRY_H

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.