summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/entry.h
blob: c4ad2bef451ede2f537015e5b7b2b9af5e1318d1 (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
/*****
 * 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 //{{{
class venv : public sym::table<varEntry*> {
public:
  venv() {}

  // This is an optimization in the hashtable version that is duplicated here
  // for compatibility.  It is identical to venv().
  struct file_env_tag {};
  venv(file_env_tag) {}

#if 0
  // Look for a function that exactly matches the signature given.
  varEntry *lookExact(symbol *name, signature *key);
#endif

  // Add the entries in one environment to another, if qualifier is
  // non-null, it is a record and 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);

  // Checks if a function was added in the top scope as two identical
  // functions cannot be defined in one scope.
  varEntry *lookInTopScope(symbol *name, ty *t);

  // Return the type of the variable, if name is overloaded, return an
  // overloaded type.
  ty *getType(symbol *name);

  friend std::ostream& operator<< (std::ostream& out, const venv& ve);
  
  // Prints a list of the variables to the standard output.
  void list(record *module=0);
};

//}}}
#else //{{{

// venv implemented with a hash table.
class venv {
  struct key : public gc {
    symbol *name;
    ty *t;

    key(symbol *name, ty *t)
      : name(name), t(t) {}

    key(symbol *name, varEntry *v)
      : name(name), t(v->getType()) {}
  };
  friend ostream& operator<< (ostream& out, const venv::key &k);

  struct value : public gc {
    varEntry *v;
    bool shadowed;
    value *next;  // The entry (of the same key) that this one shadows.

    value(varEntry *v)
      : v(v), shadowed(false), next(0) {}
  };
  struct namehash {
    size_t operator()(const symbol *name) const {
      return (size_t)name;
    }
  };
  struct nameeq {
    bool operator()(const symbol *s, const symbol *t) const {
      return s==t;
    }
  };
  struct keyhash {
    size_t hashSig(ty *t) const {
      signature *sig=t->getSignature();
      return sig ? sig->hash() : 0;
    }
    size_t operator()(const key k) const {
      return (size_t)(k.name) * 107 +
        (k.name->special ? k.t->hash() : hashSig(k.t));
    }
  };
  struct keyeq {
#define TEST_COLLISION 0
#if TEST_COLLISION
    bool base(const key k, const key l) const {
      return k.name==l.name &&
        (k.name->special ? equivalent(k.t, l.t) :
         equivalent(k.t->getSignature(),
                    l.t->getSignature()));
    }
    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;

  // Similar hashes, one for each scope level.
  typedef mem::unordered_multimap<key, value *, keyhash, keyeq> keymultimap;
  typedef mem::stack<keymultimap> mapstack;
  mapstack scopes;

  // A hash table indexed solely on the name, storing for each name the list of
  // all values of that name.  Used to get the (possibly overloaded) type
  // of the name.
  typedef mem::list<value *> values;
  typedef mem::unordered_map<symbol *, values, namehash, nameeq> namemap;
  namemap names;

  void listValues(symbol *name, values &vals, record *module);

  // Helper function for endScope.
  void remove(key k);

  // 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;
public:
  venv() {
    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)
  {
    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);

  bool lookInTopScope(key k) {
    return scopes.top().find(k)!=scopes.top().end();
  }

  // Look for a function that exactly matches the type given.
  bool lookInTopScope(symbol *name, ty *t) {
    return lookInTopScope(key(name, t));
  }

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

  ty *getType(symbol *name);

  void beginScope() {
    scopes.push(keymultimap());
  }
  void endScope() {
    keymultimap &scope=scopes.top();
    for (keymultimap::iterator p=scope.begin(); p!=scope.end(); ++p) {
      remove(p->first);
    }
    scopes.pop();
  }
  
  // Adds the definitions of the top-level scope to the level underneath,
  // and then removes the top scope.
  void collapseScope() {
    // NOTE: May be expensively copying a large hash table.
    keymultimap top=scopes.top();
    scopes.pop();

    keymultimap& underneath=scopes.top();
    underneath.insert(top.begin(), top.end());
  }

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