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
|
/*******************************************************************************
* Copyright (c) 2006, 2008 IBM Corporation and others.
*
* This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-2.0/
*
* SPDX-License-Identifier: EPL-2.0
*
* Contributors:
* IBM Corporation - initial API and implementation
*******************************************************************************/
package org.eclipse.cdt.internal.core.dom.lrparser.symboltable;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import org.eclipse.cdt.core.dom.ast.IBinding;
/**
* 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.
*
*
* @author Mike Kucera
*/
public class CImperativeSymbolTable {
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>();
}
/**
* A bucket object used to hold elements in the hash table.
*/
private static class Bucket {
String key;
CNamespace namespace;
IBinding binding;
Bucket next;
Bucket(Bucket next, CNamespace namespace, String key, IBinding binding) {
this.key = key;
this.namespace = namespace;
this.binding = binding;
this.next = next;
}
}
public CImperativeSymbolTable() {
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, IBinding b) {
int index = index(ident);
table[index] = new Bucket(table[index], namespace, ident, b);
SymbolScope scope = scopeStack.getLast();
scope.modifiedBuckets.add(index);
}
/**
* 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 IBinding 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;
}
/**
* 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() {
SymbolScope poppedScope = scopeStack.removeLast(); // pop the scopeStack
// pop each bucket that was modified in the scope
for(int index : poppedScope.modifiedBuckets)
table[index] = table[index].next;
}
@SuppressWarnings("nls")
@Override
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();
}
}
|
