summaryrefslogtreecommitdiff
path: root/graphics/asymptote/entry.h
blob: e11ad59940ebb1419b537332538673b0a1b2836d (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
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
/*****
 * 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);
};


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

} // namespace trans

#endif //ENTRY_H