summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/entry.h
blob: bffec3aa6aa10d538ac72292c4de9f188f53289a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
/*****
 * 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);
};

#ifdef NOHASH //{{{
 /* 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

// venv implemented with a hash table.
class venv {
  struct key : public gc {
    symbol name;
    bool special;
    union {
      ty *t;
      signature *sig;
    } u;

    //key(key& k) : name(k.name), special(k.special), u(k.u) {}

    key(symbol name, ty *t)
      : name(name), special(name.special())
    {
      if (special)
        u.t = t;
      else
        u.sig = t->getSignature();
    }

    /* A fake key used for searching just based on a signature. */
    key(symbol name, signature *sig)
      : name(name), special(false)
    {
      assert(!name.special());
      u.sig = sig;
    }

    key(symbol name, varEntry *v)
      : name(name), special(name.special())
    {
      ty *t = v->getType();
      if (special)
        u.t = t;
      else
        u.sig = t->getSignature();
    }
  };
  friend ostream& operator<< (ostream& out, const venv::key &k);

  struct value : public gc {
    varEntry *v;
    value(varEntry *v)
      : v(v) {}
    value() : v(0) {}
  };

  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 keyhash {
    size_t hashSig(signature *sig) const {
      return sig ? sig->hash() : 0;
    }
    size_t operator()(const key k) const {
      return k.name.hash() * 107 +
        (k.special ? k.u.t->hash() : hashSig(k.u.sig));
    }
  };
  struct keyeq {
#define TEST_COLLISION 0
#if TEST_COLLISION
    bool base(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));
    }
    bool operator()(const key k, const key l) const;
#else
    bool operator()(const key k, const key l) const; 
#endif
  };


  // A hash table used to quickly look up a variable once its name and type are
  // known.  Includes all scopes.
  typedef mem::unordered_map<key, value, keyhash, keyeq> keymap;
  keymap all;

  // Record of added variables in the order they were added.
  struct addition {
    key k;
    varEntry *shadowed;

    addition(key k, varEntry *shadowed) : k(k), 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 namevalue {
#ifdef CALLEE_SEARCH
    size_t maxFormals;
#endif
    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 hash table indexed solely on the name, storing for each name the
  // current (possibly overloaded) type of the name.
  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, /*values &vals,*/ 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 fileAllSize=2000;
  static const size_t namesAllSize=1000;

  // The number of scopes begun (but not yet ended) when the venv was empty.
  size_t empty_scopes;
public:
  venv() : empty_scopes(0) {
    beginScope();
  }

  // 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)
    : all(fileAllSize), names(namesAllSize), empty_scopes(0)
  {
    beginScope();
  }

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

  varEntry *lookByType(key k) {
    keymap::const_iterator p=all.find(k);
    return p!=all.end() ? p->second.v : 0;
  }
  
  // Look for a function that exactly matches the type given.
  varEntry *lookByType(symbol name, ty *t) {
    return lookByType(key(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);

  ty *getType(symbol name);

  void beginScope();
  void endScope();
  
  // Adds the definitions of the top-level scope to the level underneath,
  // and then removes the top scope.
  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