-
Notifications
You must be signed in to change notification settings - Fork 4k
/
AttributeContainer.java
407 lines (362 loc) · 14.1 KB
/
AttributeContainer.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
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
// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.packages;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
import com.google.errorprone.annotations.CheckReturnValue;
import java.util.BitSet;
import java.util.List;
import javax.annotation.Nullable;
/**
* AttributeContainer holds all attribute values of a rule. In addition, for each one, it records
* whether it is 'explicit', that is, provided by the function call that instantiated the rule, as
* opposed to the default value, or a value computed from other attributes.
*
* <p>This class provides the lowest-level access to attribute information. The public interface for
* attribute access is the rule itself. For a higher level abstraction use {@link AttributeMap}
* instead.
*/
abstract class AttributeContainer {
/**
* Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
* addition, this method returns false if the rule has no attribute with the given index.
*/
abstract boolean isAttributeValueExplicitlySpecified(int attrIndex);
/**
* Returns the value of the attribute with index attrIndex. Returns null if the attribute is not
* set in the container.
*/
@Nullable
abstract Object getAttributeValue(int attrIndex);
/**
* Returns attribute values as tracked by this instance. The indices of attribute values in the
* returned list are not guaranteed to be consistent with the other methods of this class. If this
* is important, which is generally the case, avoid this method.
*/
abstract List<Object> getRawAttributeValues();
/**
* Updates the value of the attribute.
*
* @param attrIndex the index of attribute whose value to update. Assumed to be valid index.
* @param value the value to set
* @param explicit was this explicitly set in the BUILD file.
*/
abstract void setAttributeValue(int attrIndex, Object value, boolean explicit);
/** Returns a frozen AttributeContainer with the same attributes, and a compact representation. */
@CheckReturnValue
abstract AttributeContainer freeze();
/** Returns an AttributeContainer for holding attributes of the given rule class. */
static AttributeContainer newMutableInstance(RuleClass ruleClass) {
int attrCount = ruleClass.getAttributeCount();
Preconditions.checkArgument(attrCount < 254);
return new Mutable(attrCount);
}
/** An AttributeContainer to which attributes may be added. */
static final class Mutable extends AttributeContainer {
// Sparsely populated array of values, indexed by Attribute.index.
final Object[] values;
final BitSet explicitAttrs = new BitSet();
@VisibleForTesting
Mutable(int maxAttrCount) {
values = new Object[maxAttrCount];
}
@Override
public boolean isAttributeValueExplicitlySpecified(int attrIndex) {
return (attrIndex >= 0) && explicitAttrs.get(attrIndex);
}
/**
* Returns the value of the attribute with index attrIndex. Returns null if the attribute is not
* yet been set.
*/
@Override
@Nullable
Object getAttributeValue(int attrIndex) {
return values[attrIndex];
}
/**
* Updates the value of the attribute.
*
* @param attrIndex the index of the attribute whose value to update.
* @param value the value to set
* @param explicit was this explicitly set in the BUILD file.
*/
@Override
void setAttributeValue(int attrIndex, Object value, boolean explicit) {
if (attrIndex < 0 || attrIndex >= values.length) {
throw new IllegalArgumentException(
"attribute with index " + attrIndex + " is not valid for rule");
}
if (!explicit && explicitAttrs.get(attrIndex)) {
throw new IllegalArgumentException(
"attribute with index " + attrIndex + " already explicitly set");
}
values[attrIndex] = value;
if (explicit) {
explicitAttrs.set(attrIndex);
}
}
@Override
public AttributeContainer freeze() {
if (values.length < 126) {
return new Small(values, explicitAttrs);
} else {
return new Large(values, explicitAttrs);
}
}
@Override
List<Object> getRawAttributeValues() {
// Mutable copy since ImmutableList doesn't support null.
return Lists.newArrayList(values);
}
}
/** Frozen AttributeContainer based on compact array with indirect indexing. */
private abstract static class Frozen extends AttributeContainer {
@Override
final void setAttributeValue(int attrIndex, Object value, boolean explicit) {
throw new UnsupportedOperationException(
"Readonly implementations do not support setAttributeValue");
}
@Override
final AttributeContainer freeze() {
return this;
}
}
private static final byte[] EMPTY_STATE = {};
private static final Object[] EMPTY_VALUES = {};
/** Returns number of non-null values. */
private static int nonNullCount(Object[] attrValues) {
// Pre-allocate longer array.
int numSet = 0;
for (Object val : attrValues) {
if (val != null) {
numSet++;
}
}
return numSet;
}
/** Returns index into state array for attrIndex, or -1 if not found */
private static int getStateIndex(byte[] state, int start, int attrIndex, int mask) {
// Binary search, treating values as unsigned bytes.
int lo = start;
int hi = state.length - 1;
while (hi >= lo) {
int mid = (lo + hi) / 2;
int midAttrIndex = state[mid] & mask;
if (midAttrIndex == attrIndex) {
return mid;
} else if (midAttrIndex < attrIndex) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
/**
* A frozen implementation of AttributeContainer which supports RuleClasses with up to 126
* attributes.
*/
@VisibleForTesting
static final class Small extends Frozen {
private final int maxAttrCount;
// Conceptually an AttributeContainer is an unordered set of triples
// (attribute, value, explicit).
// - attribute is represented internally as its index attrIndex.
// cheaply convertible to name and Attribute classes via RuleClass.
// - value is an opaque object, stored in the values array
// - explicit is a boolean which tracks if the attribute was
// explicitly set in the BUILD file.
// Attribute values stored in attrIndex order.
private final Object[] values;
// The 'value' and 'explicit' components are encoded in the same byte.
// Since this class only supports ruleClass with < 126 attributes,
// state[i] encodes the the 'value' index in the 7 lower bits and 'explicit' in the top bit.
// This is the common case.
private final byte[] state;
// Useful Terminology for reading the code.
// - attrIndex: an integer associated with a legal attribute of the ruleClass.
// RuleClass owns the mapping between attribute, its name, and attributeIndex.
// - stateIndex: an index into the state[] array.
// - valueIndex: an index into the attributeValues array.
/**
* Creates a container for a rule of the given rule class. Assumes attrIndex < 126 always.
*
* @param attrValues values for all attributes, null values are considered unset.
* @param explicitAttrs holds explicit bit for each attribute index
*/
private Small(Object[] attrValues, BitSet explicitAttrs) {
maxAttrCount = attrValues.length;
int numSet = nonNullCount(attrValues);
if (numSet == 0) {
this.values = EMPTY_VALUES;
this.state = EMPTY_STATE;
return;
}
values = new Object[numSet];
state = new byte[numSet];
int index = 0;
int attrIndex = -1;
for (Object attrValue : attrValues) {
attrIndex++;
if (attrValue == null) {
continue;
}
byte stateValue = (byte) (0x7f & attrIndex);
if (explicitAttrs.get(attrIndex)) {
stateValue = (byte) (stateValue | 0x80);
}
state[index] = stateValue;
values[index] = attrValue;
index += 1;
}
}
/**
* Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
* addition, this method return false if the rule has no attribute with the given name.
*/
@Override
boolean isAttributeValueExplicitlySpecified(int attrIndex) {
if (attrIndex < 0) {
return false;
}
int stateIndex = getStateIndex(state, 0, attrIndex, 0x7f);
return stateIndex >= 0 && (state[stateIndex] & 0x80) != 0;
}
@Override
Object getAttributeValue(int attrIndex) {
Preconditions.checkArgument(attrIndex >= 0);
if (attrIndex >= maxAttrCount) {
throw new IndexOutOfBoundsException(
"Maximum valid attrIndex is " + (maxAttrCount - 1) + ". Given " + attrIndex);
}
int stateIndex = getStateIndex(state, 0, attrIndex, 0x7f);
return stateIndex < 0 ? null : values[stateIndex];
}
@Override
List<Object> getRawAttributeValues() {
// Mutable copy since ImmutableList doesn't support null.
return Lists.newArrayList(values);
}
}
/**
* A frozen implementation of AttributeContainer which supports RuleClasses with up to 254
* attributes.
*/
@VisibleForTesting
static final class Large extends Frozen {
private final int maxAttrCount;
// Conceptually an AttributeContainer is an unordered set of triples
// (attribute, value, explicit).
// - attribute is represented internally as its index attrIndex.
// cheaply convertible to name and Attribute classes via RuleClass.
// - value is an opaque object, stored in the values array
// - explicit is a boolean which tracks if the attribute was
// explicitly set in the BUILD file.
// Attribute values stored in attrIndex order.
private final Object[] values;
// P = ceil(ruleClass.attributeCount()/8)
// The first P bytes store the explicit bits, while the remaining bytes store attrIndex.
//
// NOTE: We could potentially shave off a few bytes by using P=ceil(values.length/8)
// But
// - it leads to higher CPU cost
// - actual memory savings may not be much since memory is allocated in blocks of 8 bytes and
// the savings is at most 8 bytes.
// - this implementation is used only if ruleClass supports > 126 attributes (very rare).
private final byte[] state;
// Useful Terminology for reading the code.
// - attrIndex: an integer associated with a legal attribute of the ruleClass.
// RuleClass owns the mapping between attribute, its name, and attributeIndex.
// - stateIndex: an index into the state[] array.
// - valueIndex: an index into the attributeValues array.
private static int prefixSize(int attrCount) {
// ceil(max attributes / 8)
return (attrCount + 7) >> 3;
}
/** Set the specified bit in the byte array. Assumes bitIndex is a valid index. */
private static void setBit(byte[] bits, int bitIndex) {
int idx = (bitIndex + 1);
int explicitByte = bits[idx >> 3];
byte mask = (byte) (1 << (idx & 0x07));
bits[idx >> 3] = (byte) (explicitByte | mask);
}
/** Get the specified bit in the byte array. Assumes bitIndex is a valid index. */
private static boolean getBit(byte[] bits, int bitIndex) {
int idx = (bitIndex + 1);
int explicitByte = bits[idx >> 3];
int mask = (byte) (1 << (idx & 0x07));
return (explicitByte & mask) != 0;
}
/**
* Creates a container for a rule of the given rule class. Assumes maxAttrCount < 254
*
* @param attrValues values for all attributes, null values are considered unset.
* @param explicitAttrs holds explicit bit for each attribute index
*/
private Large(Object[] attrValues, BitSet explicitAttrs) {
this.maxAttrCount = attrValues.length;
int numSet = nonNullCount(attrValues);
if (numSet == 0) {
this.values = EMPTY_VALUES;
this.state = EMPTY_STATE;
return;
}
int p = prefixSize(maxAttrCount);
values = new Object[numSet];
state = new byte[p + numSet];
int index = 0;
int attrIndex = -1;
for (Object attrValue : attrValues) {
attrIndex++;
if (attrValue == null) {
continue;
}
if (explicitAttrs.get(attrIndex)) {
setBit(state, attrIndex);
}
state[index + p] = (byte) attrIndex;
values[index] = attrValue;
index += 1;
}
}
/**
* Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
* addition, this method return false if the rule has no attribute with the given name.
*/
@Override
boolean isAttributeValueExplicitlySpecified(int attrIndex) {
return (attrIndex >= 0) && getBit(state, attrIndex);
}
@Override
Object getAttributeValue(int attrIndex) {
Preconditions.checkArgument(attrIndex >= 0);
if (state.length == 0) {
return null;
}
if (attrIndex >= maxAttrCount) {
throw new IndexOutOfBoundsException(
"Maximum valid attrIndex is " + (maxAttrCount - 1) + ". Given " + attrIndex);
}
int p = prefixSize(maxAttrCount);
int stateIndex = getStateIndex(state, p, attrIndex, 0xff);
return stateIndex < 0 ? null : values[stateIndex - p];
}
@Override
List<Object> getRawAttributeValues() {
// Mutable copy since ImmutableList doesn't support null.
return Lists.newArrayList(values);
}
}
}