-
Notifications
You must be signed in to change notification settings - Fork 1.1k
/
TemplateTypeMap.java
375 lines (335 loc) · 12.6 KB
/
TemplateTypeMap.java
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
/*
*
* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is Rhino code, released
* May 6, 1999.
*
* The Initial Developer of the Original Code is
* Netscape Communications Corporation.
* Portions created by the Initial Developer are Copyright (C) 1997-1999
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
* Bob Jervis
* Google Inc.
*
* Alternatively, the contents of this file may be used under the terms of
* the GNU General Public License Version 2 or later (the "GPL"), in which
* case the provisions of the GPL are applicable instead of those above. If
* you wish to allow use of your version of this file only under the terms of
* the GPL and not to allow others to use your version of this file under the
* MPL, indicate your decision by deleting the provisions above and replacing
* them with the notice and other provisions required by the GPL. If you do
* not delete the provisions above, a recipient may use your version of this
* file under either the MPL or the GPL.
*
* ***** END LICENSE BLOCK ***** */
package com.google.javascript.rhino.jstype;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.javascript.rhino.jstype.JSType.EqCache;
import com.google.javascript.rhino.jstype.JSType.SubtypingMode;
import java.io.Serializable;
/**
* Manages a mapping from TemplateType to its resolved JSType. Provides utility
* methods for cloning/extending the map.
*
* @author izaakr@google.com (Izaak Rubin)
*/
public class TemplateTypeMap implements Serializable {
// The TemplateType keys of the map.
private final ImmutableList<TemplateType> templateKeys;
// The JSType values, which are index-aligned with their corresponding keys.
// These values are left as specified in the TemplateTypeMap constructor; they
// may refer to TemplateTypes that are keys in this TemplateTypeMap, requiring
// iterative type resolution to find their true, resolved type.
private final ImmutableList<JSType> templateValues;
// The JSType values, which are index-aligned with their corresponding keys.
// These values have been iteratively type-resolved using this TemplateTypeMap
// instance. These fully-resolved values are necessary for determining the
// equivalence of two TemplateTypeMap instances.
private final JSType[] resolvedTemplateValues;
private boolean inRecursiveEquivalenceCheck = false;
final JSTypeRegistry registry;
TemplateTypeMap(JSTypeRegistry registry,
ImmutableList<TemplateType> templateKeys,
ImmutableList<JSType> templateValues) {
Preconditions.checkNotNull(templateKeys);
Preconditions.checkNotNull(templateValues);
Preconditions.checkArgument(templateValues.size() <= templateKeys.size());
this.registry = registry;
this.templateKeys = templateKeys;
this.templateValues = templateValues;
// Iteratively resolve any JSType values that refer to the TemplateType keys
// of this TemplateTypeMap.
TemplateTypeMapReplacer replacer = new TemplateTypeMapReplacer(registry, this);
int nValues = this.templateValues.size();
JSType[] resolvedValues = null;
if (nValues > 0) {
resolvedValues = new JSType[nValues];
for (int i = 0; i < nValues; i++) {
TemplateType templateKey = this.templateKeys.get(i);
replacer.setKeyType(templateKey);
JSType templateValue = this.templateValues.get(i);
resolvedValues[i] = templateValue.visit(replacer);
}
}
this.resolvedTemplateValues = resolvedValues;
}
/**
* Returns true if the map is empty; false otherwise.
*/
public boolean isEmpty() {
return templateKeys.isEmpty();
}
/**
* Returns a list of all template keys.
*/
public ImmutableList<TemplateType> getTemplateKeys() {
return templateKeys;
}
/**
* Returns true if this map contains the specified template key, false
* otherwise.
*/
public boolean hasTemplateKey(TemplateType templateKey) {
// Note: match by identity, not equality
for (TemplateType entry : templateKeys) {
if (entry == templateKey) {
return true;
}
}
return false;
}
/**
* Returns the number of template keys in this map that do not have a
* corresponding JSType value.
*/
int numUnfilledTemplateKeys() {
return templateKeys.size() - templateValues.size();
}
/**
* Returns a list of template keys in this map that do not have corresponding
* JSType values.
*/
ImmutableList<TemplateType> getUnfilledTemplateKeys() {
return templateKeys.subList(templateValues.size(), templateKeys.size());
}
/**
* Returns true if there is a JSType value associated with the specified
* template key; false otherwise.
*/
public boolean hasTemplateType(TemplateType key) {
return getTemplateTypeIndex(key) != -1;
}
JSType getUnresolvedOriginalTemplateType(TemplateType key) {
int index = getTemplateTypeIndex(key);
return (index == -1) ? registry.getNativeType(JSTypeNative.UNKNOWN_TYPE) :
templateValues.get(index);
}
public TemplateType getTemplateTypeKeyByName(String keyName) {
for (TemplateType key : templateKeys) {
if (key.getReferenceName().equals(keyName)) {
return key;
}
}
return null;
}
/**
* Returns the index of the JSType value associated with the specified
* template key. If no JSType value is associated, returns -1.
*/
private int getTemplateTypeIndex(TemplateType key) {
int maxIndex = Math.min(templateKeys.size(), templateValues.size());
for (int i = maxIndex - 1; i >= 0; i--) {
if (templateKeys.get(i) == key) {
return i;
}
}
return -1;
}
/**
* Returns the JSType value associated with the specified template key. If no
* JSType value is associated, returns UNKNOWN_TYPE.
*/
public JSType getResolvedTemplateType(TemplateType key) {
TemplateTypeMap resolvedMap = this.addUnknownValues();
int index = resolvedMap.getTemplateTypeIndex(key);
return (index == -1) ? registry.getNativeType(JSTypeNative.UNKNOWN_TYPE) :
resolvedMap.resolvedTemplateValues[index];
}
/**
* An enum tracking the three different equivalence match states for a
* template key-value pair.
*/
private enum EquivalenceMatch {
NO_KEY_MATCH, VALUE_MISMATCH, VALUE_MATCH
}
/**
* Determines if this map and the specified map have equivalent template
* types.
*/
public boolean checkEquivalenceHelper(
TemplateTypeMap that, EquivalenceMethod eqMethod, SubtypingMode subtypingMode) {
return checkEquivalenceHelper(that, eqMethod, EqCache.create(), subtypingMode);
}
public boolean checkEquivalenceHelper(TemplateTypeMap that,
EquivalenceMethod eqMethod, EqCache eqCache, SubtypingMode subtypingMode) {
boolean result = false;
if (!this.inRecursiveEquivalenceCheck &&
!that.inRecursiveEquivalenceCheck) {
this.inRecursiveEquivalenceCheck = true;
that.inRecursiveEquivalenceCheck = true;
result = checkEquivalenceHelper(eqMethod, this, that, eqCache, subtypingMode)
&& checkEquivalenceHelper(eqMethod, that, this, eqCache, subtypingMode);
this.inRecursiveEquivalenceCheck = false;
that.inRecursiveEquivalenceCheck = false;
}
return result;
}
private static boolean checkEquivalenceHelper(EquivalenceMethod eqMethod,
TemplateTypeMap thisMap, TemplateTypeMap thatMap,
EqCache eqCache, SubtypingMode subtypingMode) {
ImmutableList<TemplateType> thisKeys = thisMap.getTemplateKeys();
ImmutableList<TemplateType> thatKeys = thatMap.getTemplateKeys();
for (int i = 0; i < thisKeys.size(); i++) {
TemplateType thisKey = thisKeys.get(i);
JSType thisType = thisMap.getResolvedTemplateType(thisKey);
EquivalenceMatch thisMatch = EquivalenceMatch.NO_KEY_MATCH;
for (int j = 0; j < thatKeys.size(); j++) {
TemplateType thatKey = thatKeys.get(j);
JSType thatType = thatMap.getResolvedTemplateType(thatKey);
// Cross-compare every key-value pair in this TemplateTypeMap with
// those in that TemplateTypeMap. Update the Equivalence match for both
// key-value pairs involved.
if (thisKey == thatKey) {
EquivalenceMatch newMatchType = EquivalenceMatch.VALUE_MISMATCH;
if (thisType.checkEquivalenceHelper(thatType, eqMethod, eqCache)) {
newMatchType = EquivalenceMatch.VALUE_MATCH;
} else if (subtypingMode == SubtypingMode.IGNORE_NULL_UNDEFINED
&& thisType.isSubtypeModuloNullUndefined(thatType)
&& thatType.isSubtypeModuloNullUndefined(thatType)) {
newMatchType = EquivalenceMatch.VALUE_MATCH;
}
if (thisMatch != EquivalenceMatch.VALUE_MATCH) {
thisMatch = newMatchType;
}
}
}
if (failedEquivalenceCheck(thisMatch, eqMethod)) {
return false;
}
}
return true;
}
/**
* Determines if the specified EquivalenceMatch is considered a failing
* condition for an equivalence check, given the EquivalenceMethod used for
* the check.
*/
private static boolean failedEquivalenceCheck(
EquivalenceMatch eqMatch, EquivalenceMethod eqMethod) {
return eqMatch == EquivalenceMatch.VALUE_MISMATCH ||
(eqMatch == EquivalenceMatch.NO_KEY_MATCH &&
eqMethod != EquivalenceMethod.INVARIANT);
}
/**
* Extends this TemplateTypeMap with the contents of the specified map.
* UNKNOWN_TYPE will be used as the value for any missing values in the
* specified map.
*/
TemplateTypeMap extend(TemplateTypeMap thatMap) {
thatMap = thatMap.addUnknownValues();
return registry.createTemplateTypeMap(
concatImmutableLists(thatMap.templateKeys, templateKeys),
concatImmutableLists(thatMap.templateValues, templateValues));
}
/**
* Returns a new TemplateTypeMap whose values have been extended with the
* specified list.
*/
TemplateTypeMap addValues(ImmutableList<JSType> newValues) {
// Ignore any new template values that will not align with an existing
// template key.
int numUnfilledKeys = numUnfilledTemplateKeys();
if (numUnfilledKeys < newValues.size()) {
newValues = newValues.subList(0, numUnfilledKeys);
}
return registry.createTemplateTypeMap(
templateKeys, concatImmutableLists(templateValues, newValues));
}
/**
* Returns a new TemplateTypeMap, where all unfilled values have been filled
* with UNKNOWN_TYPE.
*/
private TemplateTypeMap addUnknownValues() {
int numUnfilledTemplateKeys = numUnfilledTemplateKeys();
if (numUnfilledTemplateKeys == 0) {
return this;
}
ImmutableList.Builder<JSType> builder = ImmutableList.builder();
for (int i = 0; i < numUnfilledTemplateKeys; i++) {
builder.add(registry.getNativeType(JSTypeNative.UNKNOWN_TYPE));
}
return addValues(builder.build());
}
/**
* Concatenates two ImmutableList instances. If either input is empty, the
* other is returned; otherwise, a new ImmutableList instance is created that
* contains the contents of both arguments.
*/
private <T> ImmutableList<T> concatImmutableLists(
ImmutableList<T> first, ImmutableList<T> second) {
if (first.isEmpty()) {
return second;
}
if (second.isEmpty()) {
return first;
}
ImmutableList.Builder<T> builder = ImmutableList.builder();
builder.addAll(first);
builder.addAll(second);
return builder.build();
}
boolean hasAnyTemplateTypesInternal() {
if (resolvedTemplateValues != null) {
for (JSType templateValue : addUnknownValues().resolvedTemplateValues) {
if (templateValue.hasAnyTemplateTypes()) {
return true;
}
}
}
return false;
}
@Override
public String toString() {
String s = "";
int len = templateKeys.size();
s += "{ ";
for (int i = 0; i < len; i++) {
s += "(";
s += templateKeys.get(i);
s += ",";
s += (i < templateValues.size()) ? templateValues.get(i) : "";
s += ",";
s += (resolvedTemplateValues != null && i < resolvedTemplateValues.length)
? resolvedTemplateValues[i]
: "";
s += ") ";
}
s += "}";
return s;
}
}