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