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}