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