001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.gui.mappaint.mapcss; 003 004import java.util.ArrayList; 005import java.util.BitSet; 006import java.util.Collections; 007import java.util.HashMap; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Map; 011import java.util.NoSuchElementException; 012import java.util.Optional; 013 014import org.openstreetmap.josm.data.osm.IPrimitive; 015import org.openstreetmap.josm.data.osm.KeyValueVisitor; 016import org.openstreetmap.josm.data.osm.Tagged; 017import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.KeyCondition; 018import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.KeyValueCondition; 019import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.SimpleKeyValueCondition; 020import org.openstreetmap.josm.tools.Utils; 021 022/** 023 * A collection of {@link MapCSSRule}s, that are indexed by tag key and value. 024 * 025 * Speeds up the process of finding all rules that match a certain primitive. 026 * 027 * Rules with a {@link SimpleKeyValueCondition} [key=value] or rules that require a specific key to be set are 028 * indexed. Now you only need to loop the tags of a primitive to retrieve the possibly matching rules. 029 * 030 * To use this index, you need to {@link #add(MapCSSRule)} all rules to it. You then need to call 031 * {@link #initIndex()}. Afterwards, you can use {@link #getRuleCandidates(IPrimitive)} to get an iterator over 032 * all rules that might be applied to that primitive. 033 */ 034public class MapCSSRuleIndex { 035 /** 036 * This is an iterator over all rules that are marked as possible in the bitset. 037 * 038 * @author Michael Zangl 039 */ 040 private final class RuleCandidatesIterator implements Iterator<MapCSSRule>, KeyValueVisitor { 041 private final BitSet ruleCandidates; 042 private int next; 043 044 private RuleCandidatesIterator(BitSet ruleCandidates) { 045 this.ruleCandidates = ruleCandidates; 046 } 047 048 @Override 049 public boolean hasNext() { 050 return next >= 0 && next < rules.size(); 051 } 052 053 @Override 054 public MapCSSRule next() { 055 if (!hasNext()) 056 throw new NoSuchElementException(); 057 MapCSSRule rule = rules.get(next); 058 next = ruleCandidates.nextSetBit(next + 1); 059 return rule; 060 } 061 062 @Override 063 public void remove() { 064 throw new UnsupportedOperationException(); 065 } 066 067 @Override 068 public void visitKeyValue(Tagged p, String key, String value) { 069 MapCSSKeyRules v = index.get(key); 070 if (v != null) { 071 BitSet rs = v.get(value); 072 ruleCandidates.or(rs); 073 } 074 } 075 076 /** 077 * Call this before using the iterator. 078 */ 079 public void prepare() { 080 next = ruleCandidates.nextSetBit(0); 081 } 082 } 083 084 /** 085 * This is a map of all rules that are only applied if the primitive has a given key (and possibly value) 086 * 087 * @author Michael Zangl 088 */ 089 private static final class MapCSSKeyRules { 090 /** 091 * The indexes of rules that might be applied if this tag is present and the value has no special handling. 092 */ 093 BitSet generalRules = new BitSet(); 094 095 /** 096 * A map that stores the indexes of rules that might be applied if the key=value pair is present on this 097 * primitive. This includes all key=* rules. 098 */ 099 Map<String, BitSet> specialRules = new HashMap<>(); 100 101 public void addForKey(int ruleIndex) { 102 generalRules.set(ruleIndex); 103 for (BitSet r : specialRules.values()) { 104 r.set(ruleIndex); 105 } 106 } 107 108 public void addForKeyAndValue(String value, int ruleIndex) { 109 BitSet forValue = specialRules.get(value); 110 if (forValue == null) { 111 forValue = new BitSet(); 112 forValue.or(generalRules); 113 specialRules.put(value.intern(), forValue); 114 } 115 forValue.set(ruleIndex); 116 } 117 118 public BitSet get(String value) { 119 return specialRules.getOrDefault(value, generalRules); 120 } 121 } 122 123 /** 124 * All rules this index is for. Once this index is built, this list is sorted. 125 */ 126 private final List<MapCSSRule> rules = new ArrayList<>(); 127 /** 128 * All rules that only apply when the given key is present. 129 */ 130 private final Map<String, MapCSSKeyRules> index = new HashMap<>(); 131 /** 132 * Rules that do not require any key to be present. Only the index in the {@link #rules} array is stored. 133 */ 134 private final BitSet remaining = new BitSet(); 135 136 /** 137 * Add a rule to this index. This needs to be called before {@link #initIndex()} is called. 138 * @param rule The rule to add. 139 */ 140 public void add(MapCSSRule rule) { 141 rules.add(rule); 142 } 143 144 /** 145 * Initialize the index. 146 * <p> 147 * You must own the write lock of STYLE_SOURCE_LOCK when calling this method. 148 */ 149 public void initIndex() { 150 Collections.sort(rules); 151 for (int ruleIndex = 0; ruleIndex < rules.size(); ruleIndex++) { 152 MapCSSRule r = rules.get(ruleIndex); 153 for (Selector selector : r.selectors) { 154 Selector selRightmost = selector; 155 while (selRightmost instanceof Selector.ChildOrParentSelector) { 156 selRightmost = ((Selector.ChildOrParentSelector) selRightmost).right; 157 } 158 final List<Condition> conditions = selRightmost.getConditions(); 159 if (Utils.isEmpty(conditions)) { 160 remaining.set(ruleIndex); 161 continue; 162 } 163 Optional<SimpleKeyValueCondition> lastCondition = Utils.filteredCollection(conditions, SimpleKeyValueCondition.class) 164 .stream() 165 .reduce((first, last) -> last); 166 if (lastCondition.isPresent()) { 167 getEntryInIndex(lastCondition.get().k).addForKeyAndValue(lastCondition.get().v, ruleIndex); 168 } else { 169 String key = findAnyRequiredKey(conditions); 170 if (key != null) { 171 getEntryInIndex(key).addForKey(ruleIndex); 172 } else { 173 remaining.set(ruleIndex); 174 } 175 } 176 } 177 } 178 } 179 180 /** 181 * Search for any key that condition might depend on. 182 * 183 * @param conds The conditions to search through. 184 * @return An arbitrary key this rule depends on or <code>null</code> if there is no such key. 185 */ 186 private static String findAnyRequiredKey(List<Condition> conds) { 187 String key = null; 188 for (Condition c : conds) { 189 if (c instanceof KeyCondition) { 190 KeyCondition keyCondition = (KeyCondition) c; 191 if (!keyCondition.negateResult) { 192 key = keyCondition.label; 193 } 194 } else if (c instanceof KeyValueCondition) { 195 KeyValueCondition keyValueCondition = (KeyValueCondition) c; 196 if (keyValueCondition.requiresExactKeyMatch()) { 197 key = keyValueCondition.k; 198 } 199 } 200 } 201 return key; 202 } 203 204 private MapCSSKeyRules getEntryInIndex(String key) { 205 MapCSSKeyRules rulesWithMatchingKey = index.get(key); 206 if (rulesWithMatchingKey == null) { 207 rulesWithMatchingKey = new MapCSSKeyRules(); 208 index.put(key.intern(), rulesWithMatchingKey); 209 } 210 return rulesWithMatchingKey; 211 } 212 213 /** 214 * Get a subset of all rules that might match the primitive. Rules not included in the result are guaranteed to 215 * not match this primitive. 216 * <p> 217 * You must have a read lock of STYLE_SOURCE_LOCK when calling this method. 218 * 219 * @param osm the primitive to match 220 * @return An iterator over possible rules in the right order. 221 * @since 13810 (signature) 222 */ 223 public Iterator<MapCSSRule> getRuleCandidates(IPrimitive osm) { 224 final BitSet ruleCandidates = new BitSet(rules.size()); 225 ruleCandidates.or(remaining); 226 227 final RuleCandidatesIterator candidatesIterator = new RuleCandidatesIterator(ruleCandidates); 228 osm.visitKeys(candidatesIterator); 229 candidatesIterator.prepare(); 230 return candidatesIterator; 231 } 232 233 /** 234 * Clear the index. 235 * <p> 236 * You must own the write lock STYLE_SOURCE_LOCK when calling this method. 237 */ 238 public void clear() { 239 rules.clear(); 240 index.clear(); 241 remaining.clear(); 242 } 243 244 /** 245 * Check if this index is empty. 246 * @return true if this index is empty. 247 * @since 16784 248 */ 249 public boolean isEmpty() { 250 return rules.isEmpty(); 251 } 252}