/*
 * Copyright (c) 2010, 2015, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package com.sun.javafx.css;

import javafx.css.CompoundSelector;
import javafx.css.Selector;
import javafx.css.SimpleSelector;
import javafx.css.StyleClass;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

Code to partition selectors into a tree-like structure for faster matching.
/** * Code to partition selectors into a tree-like structure for faster matching. */
public final class SelectorPartitioning {
package accessible
/** package accessible */
public SelectorPartitioning() {} /* * Wrapper so that we can have Map<ParitionKey, Partition> even though * the innards of the key might be a String or long[] */ private final static class PartitionKey<K> { private final K key; private PartitionKey(K key) { this.key = key; } @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final PartitionKey<K> other = (PartitionKey<K>) obj; if (this.key != other.key && (this.key == null || !this.key.equals(other.key))) { return false; } return true; } @Override public int hashCode() { int hash = 7; hash = 71 * hash + (this.key != null ? this.key.hashCode() : 0); return hash; } }
A Partition corresponds to a selector type, id or styleclass. For any given id (for example) there will be one Partition held in the corresponding map (idMap, for example). Each Partition has Slots which define a path from one Partition to the next. For example, if we have A.b#c, there will be a Partition for each of A, .b and #c. The partition for #c will have a Slot pointing to A. Likewise, A will have a Slot corresponding to .b. Each Slot is capable of pointing to more than one Partition. If another selector A.#c.z were partitioned, then the Slot for A in Partition #c would now have Slots for both .b and .z.

Rules are added to the last Slot or to the Partition. If there is a selector #c { -fx-fill: red; }, then the selector will be added to the Partition for #c. If the selector were for A.b#c, then selector would be added to the slot for '.b' which is in the slot for A in partion #c.

When Node is matched, it picks up the Selectors from the Partition and Slot as the graph is traversed.

/** * A Partition corresponds to a selector type, id or styleclass. For any * given id (for example) there will be one Partition held in the * corresponding map (idMap, for example). Each Partition has Slots which * define a path from one Partition to the next. For example, if we have * A.b#c, there will be a Partition for each of A, .b and #c. The partition * for #c will have a Slot pointing to A. Likewise, A will have a Slot * corresponding to .b. Each Slot is capable of pointing to more than one * Partition. If another selector A.#c.z were partitioned, then the Slot * for A in Partition #c would now have Slots for both .b and .z. * <p> * Rules are added to the last Slot or to the Partition. If there is a * selector #c { -fx-fill: red; }, then the selector will be added to the * Partition for #c. If the selector were for A.b#c, then selector would be added * to the slot for '.b' which is in the slot for A in partion #c. * <p> * When Node is matched, it picks up the Selectors from the Partition and Slot * as the graph is traversed. */
private static final class Partition { private final PartitionKey key; private final Map<PartitionKey, Slot> slots; private List<Selector> selectors; private Partition(PartitionKey key) { this.key = key; slots = new HashMap<PartitionKey,Slot>(); } private void addSelector(Selector pair) { if (selectors == null) { selectors = new ArrayList<Selector>(); } selectors.add(pair); }
This routine finds the slot corresponding to the PartitionKey, creating a Partition and Slot if necessary.
/** * This routine finds the slot corresponding to the PartitionKey, * creating a Partition and Slot if necessary. */
private Slot partition(PartitionKey id, Map<PartitionKey, Partition> map) { Slot slot = slots.get(id); if (slot == null) { Partition partition = getPartition(id,map); slot = new Slot(partition); slots.put(id, slot); } return slot; } }
A Slot is pointer to the next piece of the selector.
/** * A Slot is pointer to the next piece of the selector. */
private static final class Slot { // The Partition to which this Slot belongs private final Partition partition; // The other Slots to which this Slot refers private final Map<PartitionKey, Slot> referents; // Selectors that match the path to this slot private List<Selector> selectors; private Slot(Partition partition) { this.partition = partition; this.referents = new HashMap<PartitionKey, Slot>(); } private void addSelector(Selector pair) { if (selectors == null) { selectors = new ArrayList<Selector>(); } selectors.add(pair); }
This routine finds the slot corresponding to the PartitionKey, creating a Partition and Slot if necessary.
/** * This routine finds the slot corresponding to the PartitionKey, * creating a Partition and Slot if necessary. */
private Slot partition(PartitionKey id, Map<PartitionKey, Partition> map) { Slot slot = referents.get(id); if (slot == null) { Partition p = getPartition(id, map); slot = new Slot(p); referents.put(id, slot); } return slot; } } /* A Map for selectors that have an id */ private final Map<PartitionKey, Partition> idMap = new HashMap<PartitionKey,Partition>(); /* A Map for selectors that have an element type */ private final Map<PartitionKey, Partition> typeMap = new HashMap<PartitionKey,Partition>(); /* A Map for selectors that have style classes */ private final Map<PartitionKey, Partition> styleClassMap = new HashMap<PartitionKey,Partition>();
Keep track of the order in which a selector is added to the mapping so the original order can be restored for the cascade.
/** * Keep track of the order in which a selector is added to the mapping so * the original order can be restored for the cascade. */
private int ordinal;
clear current partitioning
/** clear current partitioning */
public void reset() { idMap.clear(); typeMap.clear(); styleClassMap.clear(); ordinal = 0; }
Helper to lookup an id in the given map, creating and adding a Partition
/** * Helper to lookup an id in the given map, creating and adding a Partition * */
private static Partition getPartition(PartitionKey id, Map<PartitionKey,Partition> map) { Partition treeNode = map.get(id); if (treeNode == null) { treeNode = new Partition(id); map.put(id, treeNode); } return treeNode; } /* Mask that indicates the selector has an id part, e.g. #title */ private static final int ID_BIT = 4; /* Mask that indicates the selector has a type part, e.g. Label */ private static final int TYPE_BIT = 2; /* Mask that indicates the selector has a styleclass part, e.g. .label */ private static final int STYLECLASS_BIT = 1; /* If there is no type part, then * is the default. */ private static final PartitionKey WILDCARD = new PartitionKey<String>("*"); /* Place this selector into the partitioning map. Package accessible */ public void partition(Selector selector) { SimpleSelector simpleSelector = null; if (selector instanceof CompoundSelector) { final List<SimpleSelector> selectors = ((CompoundSelector)selector).getSelectors(); final int last = selectors.size()-1; simpleSelector = selectors.get(last); } else { simpleSelector = (SimpleSelector)selector; } final String selectorId = simpleSelector.getId(); final boolean hasId = (selectorId != null && selectorId.isEmpty() == false); final PartitionKey idKey = hasId ? new PartitionKey(selectorId) : null; final String selectorType = simpleSelector.getName(); final boolean hasType = (selectorType != null && selectorType.isEmpty() == false); final PartitionKey typeKey = hasType ? new PartitionKey(selectorType) : null; final Set<StyleClass> selectorStyleClass = simpleSelector.getStyleClassSet(); final boolean hasStyleClass = (selectorStyleClass != null && selectorStyleClass.size() > 0); final PartitionKey styleClassKey = hasStyleClass ? new PartitionKey<Set<StyleClass>>(selectorStyleClass) : null; final int c = (hasId ? ID_BIT : 0) | (hasType ? TYPE_BIT : 0) | (hasStyleClass ? STYLECLASS_BIT : 0); Partition partition = null; Slot slot = null; selector.setOrdinal(ordinal++); switch(c) { case ID_BIT | TYPE_BIT | STYLECLASS_BIT: case ID_BIT | TYPE_BIT: partition = getPartition(idKey, idMap); slot = partition.partition(typeKey, typeMap); if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) { slot = slot.partition(styleClassKey, styleClassMap); } slot.addSelector(selector); break; case TYPE_BIT | STYLECLASS_BIT: case TYPE_BIT: partition = getPartition(typeKey, typeMap); if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) { slot = partition.partition(styleClassKey, styleClassMap); slot.addSelector(selector); } else { partition.addSelector(selector); } break; // SimpleSelector always has a type which defaults to '*' case ID_BIT | STYLECLASS_BIT: case ID_BIT: case STYLECLASS_BIT: default: assert(false); } }
Get the list of selectors that match this selector. Package accessible
/** Get the list of selectors that match this selector. Package accessible */
public List<Selector> match(String selectorId, String selectorType, Set<StyleClass> selectorStyleClass) { final boolean hasId = (selectorId != null && selectorId.isEmpty() == false); final PartitionKey idKey = hasId ? new PartitionKey(selectorId) : null; final boolean hasType = (selectorType != null && selectorType.isEmpty() == false); final PartitionKey typeKey = hasType ? new PartitionKey(selectorType) : null; final boolean hasStyleClass = (selectorStyleClass != null && selectorStyleClass.size() > 0); final PartitionKey styleClassKey = hasStyleClass ? new PartitionKey<Set<StyleClass>>(selectorStyleClass) : null; int c = (hasId ? ID_BIT : 0) | (hasType ? TYPE_BIT : 0) | (hasStyleClass ? STYLECLASS_BIT : 0); Partition partition = null; Slot slot = null; List<Selector> selectors = new ArrayList<Selector>(); while (c != 0) { switch(c) { case ID_BIT | TYPE_BIT | STYLECLASS_BIT: case ID_BIT | TYPE_BIT: { partition = idMap.get(idKey); if (partition != null) { if (partition.selectors != null) { selectors.addAll(partition.selectors); } // do-while handles A.b#c also matches A#c by first // doing A.b#c then doing *.b#c PartitionKey typePK = typeKey; do { slot = partition.slots.get(typePK); if (slot != null) { if (slot.selectors != null) { selectors.addAll(slot.selectors); } if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) { Set<StyleClass> key = (Set<StyleClass>)styleClassKey.key; for (Slot s : slot.referents.values()) { if (s.selectors == null || s.selectors.isEmpty()) continue; Set<StyleClass> other = (Set<StyleClass>)s.partition.key.key; if (key.containsAll(other)) { selectors.addAll(s.selectors); } } } } // if typePK is 'A', make it '*', if it is '*' make it null typePK=WILDCARD.equals(typePK) == false ? WILDCARD : null; } while(typePK != null); } c -= ID_BIT; continue; } // SimpleSelector always has a type which defaults to '*' case ID_BIT | STYLECLASS_BIT: case ID_BIT: c -= ID_BIT; break; case TYPE_BIT | STYLECLASS_BIT: case TYPE_BIT: { // do-while handles A.b also matches .b by first // doing A.b then doing *.b PartitionKey typePK = typeKey; do { partition = typeMap.get(typePK); if (partition != null) { if (partition.selectors != null) { selectors.addAll(partition.selectors); } if ((c & STYLECLASS_BIT) == STYLECLASS_BIT) { Set<StyleClass> key = (Set<StyleClass>)styleClassKey.key; for (Slot s : partition.slots.values()) { if (s.selectors == null || s.selectors.isEmpty()) continue; Set<StyleClass> other = (Set<StyleClass>)s.partition.key.key; if (key.containsAll(other)) { selectors.addAll(s.selectors); } } } } // if typePK is 'A', make it '*', if it is '*' make it null typePK=WILDCARD.equals(typePK) == false ? WILDCARD : null; } while(typePK != null); c -= TYPE_BIT; continue; } // SimpleSelector always has a type which defaults to '*' case STYLECLASS_BIT: c -= STYLECLASS_BIT; break; default: assert(false); } } Collections.sort(selectors, COMPARATOR); return selectors; } private static final Comparator<Selector> COMPARATOR = (o1, o2) -> o1.getOrdinal() - o2.getOrdinal(); }