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
|
// Copyright 2017 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.collect.nestedset;
import static com.google.common.collect.ImmutableSet.toImmutableSet;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableSet;
import java.util.Arrays;
import java.util.Set;
/**
* Class presenting the logical structure of a {@link NestedSet}.
*
* <p>The main use case for this class are situations were a larger number of related nested sets
* needs to be serialized in an efficient way, as is the case when reporting artifacts in the build
* event protocol.
*
* <p>Note that a {@link NestedSet} does not preserve all structure provided to the {@link
* NestedSetBuilder}; in fact, it may decide to inline the contents of small nested sets as direct
* members. This view class provides a view on the structure that is still present in a {@link
* NestedSet}. As there is a fixed limit on the size a transitive member can have to still be
* eligible for inlining, this is enough to allow an efficient deduplicated presentation.
*/
public class NestedSetView<E> {
private final Object set;
private NestedSetView(Object set) {
this.set = set;
}
/** Construct a view of a given NestedSet. */
public NestedSetView(NestedSet<E> set) {
this(set.getChildren());
}
/**
* Splits the current view into multiple views if the number of entries in the current set exceeds
* the given limit, which has to be at least 2. This method guarantees that the resulting view
* contains the same elements (direct and transitive) overall, and that each node's size is less
* than or equal to the given limit. It makes no guarantees about the resulting structure of the
* graph, and this may affect the traversal order if it is converted back to a nested set.
*/
public NestedSetView<E> splitIfExceedsMaximumSize(int maximumSize) {
Preconditions.checkArgument(maximumSize >= 2, "maximumSize must be at least 2");
if (!(set instanceof Object[])) {
return this;
}
Object[] arr = (Object[]) set;
int size = arr.length;
if (size <= maximumSize) {
return this;
}
Object[][] pieces = new Object[((size + maximumSize - 1) / maximumSize)][];
for (int i = 0; i < pieces.length; i++) {
int max = Math.min((i + 1) * maximumSize, arr.length);
pieces[i] = Arrays.copyOfRange(arr, i * maximumSize, max);
}
return new NestedSetView<E>(pieces).splitIfExceedsMaximumSize(maximumSize);
}
/**
* Return an object where the {@link #equals} method provides the correct notion of (intensional)
* equality of the set viewed. Consumers of this method should not assume any properties of the
* returned object apart from its {@link #equals} method.
*
* <p>The identifier is meant as an abstract, but memory efficient way of remembering nested sets
* directly or indirectly seen. Storing the identifier of a nested-set view will not retain more
* memory than storing the underlying nested set; in particular, it will not prevent the view
* object from being garbage collected.
*
* <p>The equality of the view itself is the one inherited from Object, i.e., you can have many
* views of the same set that are not equal as views.
*/
public Object identifier() {
return set;
}
/**
* Return the set of transitive members.
*
* <p>This refers to the transitive members after any inlining that might have happened at
* construction of the nested set.
*/
public Set<NestedSetView<E>> transitives() {
if (!(set instanceof Object[])) {
return ImmutableSet.of();
}
return Arrays.stream((Object[]) set)
.filter(c -> c instanceof Object[])
.map(c -> new NestedSetView<E>(c))
.collect(toImmutableSet());
}
/**
* Return the set of direct members.
*
* <p>This refers to the direct members after any inlining that might have happened at
* construction of the nested set.
*/
@SuppressWarnings("unchecked")
public Set<E> directs() {
if (!(set instanceof Object[])) {
return ImmutableSet.of((E) set);
}
return Arrays.stream((Object[]) set)
.filter(c -> !(c instanceof Object[]))
.map(c -> (E) c)
.collect(toImmutableSet());
}
}
|
