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}