1 /*
2 * Copyright (c) 2010, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.javafx.css;
27
28
29 import java.util.ArrayList;
30 import java.util.Collections;
31 import java.util.Comparator;
32 import java.util.HashMap;
33 import java.util.List;
34 import java.util.Map;
35 import java.util.Set;
36
37 /**
38 * Code to partition selectors into a tree-like structure for faster matching.
39 */
40 public final class SelectorPartitioning {
41
42 /** package accessible */
43 SelectorPartitioning() {}
44
45 /*
46 * Wrapper so that we can have Map<ParitionKey, Partition> even though
47 * the innards of the key might be a String or long[]
48 */
49 private final static class PartitionKey<K> {
50
51 private final K key;
52
53 private PartitionKey(K key) {
54 this.key = key;
55 }
56
57 @Override
58 public boolean equals(Object obj) {
59 if (obj == null) {
60 return false;
61 }
62 if (getClass() != obj.getClass()) {
63 return false;
64 }
65 final PartitionKey<K> other = (PartitionKey<K>) obj;
66 if (this.key != other.key && (this.key == null || !this.key.equals(other.key))) {
67 return false;
68 }
69 return true;
70 }
71
72 @Override
73 public int hashCode() {
74 int hash = 7;
75 hash = 71 * hash + (this.key != null ? this.key.hashCode() : 0);
76 return hash;
77 }
78
79 }
80
81 /**
82 * A Partition corresponds to a selector type, id or styleclass. For any
83 * given id (for example) there will be one Partition held in the
84 * corresponding map (idMap, for example). Each Partition has Slots which
85 * define a path from one Partition to the next. For example, if we have
86 * A.b#c, there will be a Partition for each of A, .b and #c. The partition
87 * for #c will have a Slot pointing to A. Likewise, A will have a Slot
88 * corresponding to .b. Each Slot is capable of pointing to more than one
89 * Partition. If another selector A.#c.z were partitioned, then the Slot
90 * for A in Partition #c would now have Slots for both .b and .z.
91 * <p>
92 * Rules are added to the last Slot or to the Partition. If there is a
93 * selector #c { -fx-fill: red; }, then the selector will be added to the
94 * Partition for #c. If the selector were for A.b#c, then selector would be added
95 * to the slot for '.b' which is in the slot for A in partion #c.
96 * <p>
97 * When Node is matched, it picks up the Selectors from the Partition and Slot
98 * as the graph is traversed.
99 */
100 private static final class Partition {
101
102 private final PartitionKey key;
103 private final Map<PartitionKey, Slot> slots;
104 private List<Selector> selectors;
105
106 private Partition(PartitionKey key) {
107 this.key = key;
108 slots = new HashMap<PartitionKey,Slot>();
109 }
110
111 private void addSelector(Selector pair) {
112 if (selectors == null) {
113 selectors = new ArrayList<Selector>();
114 }
115 selectors.add(pair);
116 }
117
118 /**
119 * This routine finds the slot corresponding to the PartitionKey,
120 * creating a Partition and Slot if necessary.
121 */
122 private Slot partition(PartitionKey id, Map<PartitionKey, Partition> map) {
123
124 Slot slot = slots.get(id);
125 if (slot == null) {
126 Partition partition = getPartition(id,map);
127 slot = new Slot(partition);
128 slots.put(id, slot);
129 }
130 return slot;
131 }
132
133 }
134
135 /**
136 * A Slot is pointer to the next piece of the selector.
137 */
138 private static final class Slot {
139
140
141 // The Partition to which this Slot belongs
142 private final Partition partition;
143
144 // The other Slots to which this Slot refers
145 private final Map<PartitionKey, Slot> referents;
146
147 // Selectors that match the path to this slot
148 private List<Selector> selectors;
149
150 private Slot(Partition partition) {
151 this.partition = partition;
152 this.referents = new HashMap<PartitionKey, Slot>();
153 }
154
155 private void addSelector(Selector pair) {
156 if (selectors == null) {
157 selectors = new ArrayList<Selector>();
158 }
159 selectors.add(pair);
160 }
161
162 /**
163 * This routine finds the slot corresponding to the PartitionKey,
164 * creating a Partition and Slot if necessary.
165 */
166 private Slot partition(PartitionKey id, Map<PartitionKey, Partition> map) {
167 Slot slot = referents.get(id);
168 if (slot == null) {
169
170 Partition p = getPartition(id, map);
171 slot = new Slot(p);
172 referents.put(id, slot);
173
174 }
175 return slot;
176 }
177
178 }
179
180 /* A Map for selectors that have an id */
181 private final Map<PartitionKey, Partition> idMap = new HashMap<PartitionKey,Partition>();
182
183 /* A Map for selectors that have an element type */
184 private final Map<PartitionKey, Partition> typeMap = new HashMap<PartitionKey,Partition>();
185
186 /* A Map for selectors that have style classes */
187 private final Map<PartitionKey, Partition> styleClassMap = new HashMap<PartitionKey,Partition>();
188
189 /**
190 * Keep track of the order in which a selector is added to the mapping so
191 * the original order can be restored for the cascade.
192 */
193 private int ordinal;
194
195 /** clear current partitioning */
196 void reset() {
197 idMap.clear();
198 typeMap.clear();
199 styleClassMap.clear();
200 ordinal = 0;
201 }
202
203
204 /**
205 * Helper to lookup an id in the given map, creating and adding a Partition
206 *
207 */
208 private static Partition getPartition(PartitionKey id, Map<PartitionKey,Partition> map) {
209
210 Partition treeNode = map.get(id);
211 if (treeNode == null) {
212 treeNode = new Partition(id);
213 map.put(id, treeNode);
214 }
215 return treeNode;
216 }
217
218 /* Mask that indicates the selector has an id part, e.g. #title */
219 private static final int ID_BIT = 4;
220 /* Mask that indicates the selector has a type part, e.g. Label */
221 private static final int TYPE_BIT = 2;
222 /* Mask that indicates the selector has a styleclass part, e.g. .label */
223 private static final int STYLECLASS_BIT = 1;
224 /* If there is no type part, then * is the default. */
225 private static final PartitionKey WILDCARD = new PartitionKey<String>("*");
226
227 /* Place this selector into the partitioning map. Package accessible */
228 void partition(Selector selector) {
229
230 SimpleSelector simpleSelector = null;
231 if (selector instanceof CompoundSelector) {
232 final List<SimpleSelector> selectors = ((CompoundSelector)selector).getSelectors();
233 final int last = selectors.size()-1;
234 simpleSelector = selectors.get(last);
235 } else {
236 simpleSelector = (SimpleSelector)selector;
237 }
238
239 final String selectorId = simpleSelector.getId();
240 final boolean hasId =
241 (selectorId != null && selectorId.isEmpty() == false);
242 final PartitionKey idKey = hasId
243 ? new PartitionKey(selectorId)
244 : null;
245
246 final String selectorType = simpleSelector.getName();
247 final boolean hasType =
248 (selectorType != null && selectorType.isEmpty() == false);
249 final PartitionKey typeKey = hasType
250 ? new PartitionKey(selectorType)
251 : null;
252
253 final Set<StyleClass> selectorStyleClass = simpleSelector.getStyleClassSet();
254 final boolean hasStyleClass =
255 (selectorStyleClass != null && selectorStyleClass.size() > 0);
256 final PartitionKey styleClassKey = hasStyleClass
257 ? new PartitionKey<Set<StyleClass>>(selectorStyleClass)
258 : null;
259
260 final int c =
261 (hasId ? ID_BIT : 0) | (hasType ? TYPE_BIT : 0) | (hasStyleClass ? STYLECLASS_BIT : 0);
262
263 Partition partition = null;
264 Slot slot = null;
265
266 selector.setOrdinal(ordinal++);
267
268 switch(c) {
269 case ID_BIT | TYPE_BIT | STYLECLASS_BIT:
270 case ID_BIT | TYPE_BIT:
271
272 partition = getPartition(idKey, idMap);
273 slot = partition.partition(typeKey, typeMap);
274 if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) {
275 slot = slot.partition(styleClassKey, styleClassMap);
276 }
277 slot.addSelector(selector);
278 break;
279
280 case TYPE_BIT | STYLECLASS_BIT:
281 case TYPE_BIT:
282
283 partition = getPartition(typeKey, typeMap);
284 if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) {
285 slot = partition.partition(styleClassKey, styleClassMap);
286 slot.addSelector(selector);
287 } else {
288 partition.addSelector(selector);
289 }
290 break;
291
292 // SimpleSelector always has a type which defaults to '*'
293 case ID_BIT | STYLECLASS_BIT:
294 case ID_BIT:
295 case STYLECLASS_BIT:
296 default:
297 assert(false);
298 }
299
300 }
301
302 /** Get the list of selectors that match this selector. Package accessible */
303 List<Selector> match(String selectorId, String selectorType, Set<StyleClass> selectorStyleClass) {
304
305 final boolean hasId =
306 (selectorId != null && selectorId.isEmpty() == false);
307 final PartitionKey idKey = hasId
308 ? new PartitionKey(selectorId)
309 : null;
310
311 final boolean hasType =
312 (selectorType != null && selectorType.isEmpty() == false);
313 final PartitionKey typeKey = hasType
314 ? new PartitionKey(selectorType)
315 : null;
316
317 final boolean hasStyleClass =
318 (selectorStyleClass != null && selectorStyleClass.size() > 0);
319 final PartitionKey styleClassKey = hasStyleClass
320 ? new PartitionKey<Set<StyleClass>>(selectorStyleClass)
321 : null;
322
323 int c =
324 (hasId ? ID_BIT : 0) | (hasType ? TYPE_BIT : 0) | (hasStyleClass ? STYLECLASS_BIT : 0);
325
326 Partition partition = null;
327 Slot slot = null;
328 List<Selector> selectors = new ArrayList<Selector>();
329
330 while (c != 0) {
331
332 switch(c) {
333 case ID_BIT | TYPE_BIT | STYLECLASS_BIT:
334 case ID_BIT | TYPE_BIT:
335 {
336
337 partition = idMap.get(idKey);
338 if (partition != null) {
339 if (partition.selectors != null) {
340 selectors.addAll(partition.selectors);
341 }
342 // do-while handles A.b#c also matches A#c by first
343 // doing A.b#c then doing *.b#c
344 PartitionKey typePK = typeKey;
345 do {
346 slot = partition.slots.get(typePK);
347 if (slot != null) {
348
349 if (slot.selectors != null) {
350 selectors.addAll(slot.selectors);
351 }
352 if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) {
353 Set<StyleClass> key = (Set<StyleClass>)styleClassKey.key;
354 for (Slot s : slot.referents.values()) {
355 if (s.selectors == null || s.selectors.isEmpty()) continue;
356 Set<StyleClass> other = (Set<StyleClass>)s.partition.key.key;
357 if (key.containsAll(other)) {
358 selectors.addAll(s.selectors);
359 }
360 }
361 }
362
363 }
364 // if typePK is 'A', make it '*', if it is '*' make it null
365 typePK=WILDCARD.equals(typePK) == false ? WILDCARD : null;
366
367 } while(typePK != null);
368 }
369
370 c -= ID_BIT;
371 continue;
372 }
373
374
375 // SimpleSelector always has a type which defaults to '*'
376 case ID_BIT | STYLECLASS_BIT:
377 case ID_BIT:
378 c -= ID_BIT;
379 break;
380
381 case TYPE_BIT | STYLECLASS_BIT:
382 case TYPE_BIT:
383 {
384
385 // do-while handles A.b also matches .b by first
386 // doing A.b then doing *.b
387 PartitionKey typePK = typeKey;
388 do {
389 partition = typeMap.get(typePK);
390 if (partition != null) {
391 if (partition.selectors != null) {
392 selectors.addAll(partition.selectors);
393 }
394 if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) {
395 Set<StyleClass> key = (Set<StyleClass>)styleClassKey.key;
396 for (Slot s : partition.slots.values()) {
397 if (s.selectors == null || s.selectors.isEmpty()) continue;
398 Set<StyleClass> other = (Set<StyleClass>)s.partition.key.key;
399 if (key.containsAll(other)) {
400 selectors.addAll(s.selectors);
401 }
402 }
403 }
404 }
405 // if typePK is 'A', make it '*', if it is '*' make it null
406 typePK=WILDCARD.equals(typePK) == false ? WILDCARD : null;
407
408 } while(typePK != null);
409
410 c -= TYPE_BIT;
411 continue;
412 }
413
414 // SimpleSelector always has a type which defaults to '*'
415 case STYLECLASS_BIT:
416 c -= STYLECLASS_BIT;
417 break;
418
419 default:
420 assert(false);
421 }
422 }
423
424 Collections.sort(selectors, COMPARATOR);
425 return selectors;
426 }
427
428 private static final Comparator<Selector> COMPARATOR =
429 (o1, o2) -> o1.getOrdinal() - o2.getOrdinal();
430
431
432 }