1 | // License: GPL. For details, see LICENSE file.
|
---|
2 | package org.openstreetmap.josm.gui.mappaint.mapcss;
|
---|
3 |
|
---|
4 | import java.util.ArrayList;
|
---|
5 | import java.util.BitSet;
|
---|
6 | import java.util.Collections;
|
---|
7 | import java.util.HashMap;
|
---|
8 | import java.util.Iterator;
|
---|
9 | import java.util.List;
|
---|
10 | import java.util.Map;
|
---|
11 | import java.util.NoSuchElementException;
|
---|
12 | import java.util.Optional;
|
---|
13 |
|
---|
14 | import org.openstreetmap.josm.data.osm.IPrimitive;
|
---|
15 | import org.openstreetmap.josm.data.osm.KeyValueVisitor;
|
---|
16 | import org.openstreetmap.josm.data.osm.Tagged;
|
---|
17 | import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.KeyCondition;
|
---|
18 | import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.KeyValueCondition;
|
---|
19 | import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.SimpleKeyValueCondition;
|
---|
20 | import org.openstreetmap.josm.tools.Utils;
|
---|
21 |
|
---|
22 | /**
|
---|
23 | * A collection of {@link MapCSSRule}s, that are indexed by tag key and value.
|
---|
24 | *
|
---|
25 | * Speeds up the process of finding all rules that match a certain primitive.
|
---|
26 | *
|
---|
27 | * Rules with a {@link SimpleKeyValueCondition} [key=value] or rules that require a specific key to be set are
|
---|
28 | * indexed. Now you only need to loop the tags of a primitive to retrieve the possibly matching rules.
|
---|
29 | *
|
---|
30 | * To use this index, you need to {@link #add(MapCSSRule)} all rules to it. You then need to call
|
---|
31 | * {@link #initIndex()}. Afterwards, you can use {@link #getRuleCandidates(IPrimitive)} to get an iterator over
|
---|
32 | * all rules that might be applied to that primitive.
|
---|
33 | */
|
---|
34 | public class MapCSSRuleIndex {
|
---|
35 | /**
|
---|
36 | * This is an iterator over all rules that are marked as possible in the bitset.
|
---|
37 | *
|
---|
38 | * @author Michael Zangl
|
---|
39 | */
|
---|
40 | private final class RuleCandidatesIterator implements Iterator<MapCSSRule>, KeyValueVisitor {
|
---|
41 | private final BitSet ruleCandidates;
|
---|
42 | private int next;
|
---|
43 |
|
---|
44 | private RuleCandidatesIterator(BitSet ruleCandidates) {
|
---|
45 | this.ruleCandidates = ruleCandidates;
|
---|
46 | }
|
---|
47 |
|
---|
48 | @Override
|
---|
49 | public boolean hasNext() {
|
---|
50 | return next >= 0 && next < rules.size();
|
---|
51 | }
|
---|
52 |
|
---|
53 | @Override
|
---|
54 | public MapCSSRule next() {
|
---|
55 | if (!hasNext())
|
---|
56 | throw new NoSuchElementException();
|
---|
57 | MapCSSRule rule = rules.get(next);
|
---|
58 | next = ruleCandidates.nextSetBit(next + 1);
|
---|
59 | return rule;
|
---|
60 | }
|
---|
61 |
|
---|
62 | @Override
|
---|
63 | public void remove() {
|
---|
64 | throw new UnsupportedOperationException();
|
---|
65 | }
|
---|
66 |
|
---|
67 | @Override
|
---|
68 | public void visitKeyValue(Tagged p, String key, String value) {
|
---|
69 | MapCSSKeyRules v = index.get(key);
|
---|
70 | if (v != null) {
|
---|
71 | BitSet rs = v.get(value);
|
---|
72 | ruleCandidates.or(rs);
|
---|
73 | }
|
---|
74 | }
|
---|
75 |
|
---|
76 | /**
|
---|
77 | * Call this before using the iterator.
|
---|
78 | */
|
---|
79 | public void prepare() {
|
---|
80 | next = ruleCandidates.nextSetBit(0);
|
---|
81 | }
|
---|
82 | }
|
---|
83 |
|
---|
84 | /**
|
---|
85 | * This is a map of all rules that are only applied if the primitive has a given key (and possibly value)
|
---|
86 | *
|
---|
87 | * @author Michael Zangl
|
---|
88 | */
|
---|
89 | private static final class MapCSSKeyRules {
|
---|
90 | /**
|
---|
91 | * The indexes of rules that might be applied if this tag is present and the value has no special handling.
|
---|
92 | */
|
---|
93 | BitSet generalRules = new BitSet();
|
---|
94 |
|
---|
95 | /**
|
---|
96 | * A map that stores the indexes of rules that might be applied if the key=value pair is present on this
|
---|
97 | * primitive. This includes all key=* rules.
|
---|
98 | */
|
---|
99 | 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 | }
|
---|