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
|
/*******************************************************************************
* Copyright (c) 2006, 2008 IBM Corporation and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* IBM Corporation - initial API and implementation
*******************************************************************************/
package org.eclipse.cdt.core.dom.lrparser.action.c99;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import org.eclipse.cdt.internal.core.dom.lrparser.c99.bindings.IC99Binding;
import org.eclipse.cdt.internal.core.dom.lrparser.c99.bindings.IC99Scope;
/**
* Used to compute binding resolution during the parse.
*
* Imperative style symbol table with destructive update.
*
* Consists of two data structures, a hash table for fast lookup
* of bindings given their names, and a stack used to keep track
* of scopes.
*
* @deprecated Use FunctionalSymbolTable now that undo actions are needed
*
* @author Mike Kucera
*/
@Deprecated public class ImperativeSymbolTable {
private static final int TABLE_SIZE = 256;
private Bucket[] table = new Bucket[TABLE_SIZE];
private LinkedList<SymbolScope> scopeStack = new LinkedList<SymbolScope>();
/**
* Represents a scope in the C language.
*/
private static class SymbolScope {
/**
* List of buckets that have been modified in the current scope.
* When the scope is closed these buckets are popped, returning the
* symbol table to the state it was in before the scope was opened.
*/
List<Integer> modifiedBuckets = new ArrayList<Integer>();
/**
* List of inner scopes that have been closed.
*/
List<IC99Scope> innerScopes = new ArrayList<IC99Scope>();
}
/**
* A bucket object used to hold elements in the hash table.
*/
private static class Bucket {
String key;
CNamespace namespace;
IC99Binding binding;
Bucket next;
Bucket(Bucket next, CNamespace namespace, String key, IC99Binding binding) {
this.key = key;
this.namespace = namespace;
this.binding = binding;
this.next = next;
}
}
public ImperativeSymbolTable() {
openScope(); // open the global scope
// TODO populate the global scope with built-ins
}
/**
* Hashes a key into an index in the hash table.
*/
private int index(String key) {
return Math.abs(key.hashCode() % TABLE_SIZE);
}
/**
* Adds a binding to the symbol table in the current scope.
*
* @param mask A bit mask used to identify the namespace of the identifier.
*/
public void put(CNamespace namespace, String ident, IC99Binding b) {
int index = index(ident);
table[index] = new Bucket(table[index], namespace, ident, b);
SymbolScope scope = scopeStack.getLast();
scope.modifiedBuckets.add(index);
}
/**
* Special version of put that adds the binding to the scope that contains
* the current scope.
*
* This is here because the scope for a function body is opened before
* the function binding is created.
*/
public void putInOuterScope(CNamespace namespace, String ident, IC99Binding b) {
LinkedList<Bucket> poppedBindings = new LinkedList<Bucket>();
SymbolScope scope = scopeStack.removeLast();
for(int index : scope.modifiedBuckets) {
Bucket bucket = table[index];
poppedBindings.add(bucket);
table[index] = bucket.next;
}
put(namespace, ident, b);
for(int index : scope.modifiedBuckets) {
Bucket bucket = poppedBindings.removeFirst();
bucket.next = table[index];
table[index] = bucket;
}
scopeStack.add(scope);
}
/**
* Returns the binding associated with the given identifier, or
* null if there is none.
*
* @param mask A bit mask used to identify the namespace of the identifier.
*/
public IC99Binding get(CNamespace namespace, String ident) {
Bucket b = table[index(ident)];
while(b != null) {
if(namespace == b.namespace && ident.equals(b.key))
return b.binding;
b = b.next;
}
return null;
}
List<IC99Scope> getInnerScopes() {
return scopeStack.getLast().innerScopes;
}
/**
* Opens a new inner scope for identifiers.
*
* If an identifier is added that already exists in an outer scope
* then it will be shadowed.
*/
public void openScope() {
scopeStack.add(new SymbolScope());
}
/**
* Remove all the symbols defined in the scope that is being closed.
*
* @param scope An IScope object that will be used to represent this scope.
* @throws SymbolTableException If the global scope has already been closed or if bindingScope is null.
*/
public void closeScope(IC99Scope bindingScope) {
SymbolScope poppedScope = scopeStack.removeLast(); // pop the scopeStack
for(IC99Scope innerScope : poppedScope.innerScopes) {
innerScope.setParent(bindingScope);
}
if(!scopeStack.isEmpty()) { // would be empty if the global scope was popped
SymbolScope outerScope = scopeStack.getLast();
outerScope.innerScopes.add(bindingScope);
}
// pop each bucket that was modified in the scope
for(int index : poppedScope.modifiedBuckets) {
Bucket bucket = table[index];
bucket.binding.setScope(bindingScope);
table[index] = bucket.next;
}
}
public String toString() {
StringBuilder buff = new StringBuilder("[");
for(Bucket b : table) {
while(b != null) {
buff.append("<").append(b.key).append(": ").append(b.binding).append(">, ");
b = b.next;
}
}
return buff.append("]").toString();
}
}
|
