001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.mappaint.mapcss;
003
004import static org.openstreetmap.josm.data.projection.Ellipsoid.WGS84;
005
006import java.util.Collection;
007import java.util.Collections;
008import java.util.List;
009import java.util.NoSuchElementException;
010import java.util.Objects;
011import java.util.Set;
012import java.util.function.IntFunction;
013import java.util.function.IntSupplier;
014import java.util.regex.PatternSyntaxException;
015
016import org.openstreetmap.josm.data.osm.Node;
017import org.openstreetmap.josm.data.osm.OsmPrimitive;
018import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
019import org.openstreetmap.josm.data.osm.OsmUtils;
020import org.openstreetmap.josm.data.osm.Relation;
021import org.openstreetmap.josm.data.osm.RelationMember;
022import org.openstreetmap.josm.data.osm.Way;
023import org.openstreetmap.josm.data.osm.visitor.OsmPrimitiveVisitor;
024import org.openstreetmap.josm.data.osm.visitor.paint.relations.MultipolygonCache;
025import org.openstreetmap.josm.gui.mappaint.Environment;
026import org.openstreetmap.josm.gui.mappaint.Range;
027import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.OpenEndPseudoClassCondition;
028import org.openstreetmap.josm.tools.CheckParameterUtil;
029import org.openstreetmap.josm.tools.Geometry;
030import org.openstreetmap.josm.tools.Logging;
031import org.openstreetmap.josm.tools.Pair;
032import org.openstreetmap.josm.tools.SubclassFilteredCollection;
033import org.openstreetmap.josm.tools.Utils;
034
035/**
036 * MapCSS selector.
037 *
038 * A rule has two parts, a selector and a declaration block
039 * e.g.
040 * <pre>
041 * way[highway=residential]
042 * { width: 10; color: blue; }
043 * </pre>
044 *
045 * The selector decides, if the declaration block gets applied or not.
046 *
047 * All implementing classes of Selector are immutable.
048 */
049public interface Selector {
050
051    /**
052     * Apply the selector to the primitive and check if it matches.
053     *
054     * @param env the Environment. env.mc and env.layer are read-only when matching a selector.
055     * env.source is not needed. This method will set the matchingReferrers field of env as
056     * a side effect! Make sure to clear it before invoking this method.
057     * @return true, if the selector applies
058     */
059    boolean matches(Environment env);
060
061    /**
062     * Returns the subpart, if supported. A subpart identifies different rendering layers (<code>::subpart</code> syntax).
063     * @return the subpart, if supported
064     * @throws UnsupportedOperationException if not supported
065     */
066    Subpart getSubpart();
067
068    /**
069     * Returns the scale range, an interval of the form "lower &lt; x &lt;= upper" where 0 &lt;= lower &lt; upper.
070     * @return the scale range, if supported
071     * @throws UnsupportedOperationException if not supported
072     */
073    Range getRange();
074
075    /**
076     * Create an "optimized" copy of this selector that omits the base check.
077     *
078     * For the style source, the list of rules is preprocessed, such that
079     * there is a separate list of rules for nodes, ways, ...
080     *
081     * This means that the base check does not have to be performed
082     * for each rule, but only once for each primitive.
083     *
084     * @return a selector that is identical to this object, except the base of the
085     * "rightmost" selector is not checked
086     */
087    Selector optimizedBaseCheck();
088
089    /**
090     * The type of child of parent selector.
091     * @see ChildOrParentSelector
092     */
093    enum ChildOrParentSelectorType {
094        CHILD, PARENT, ELEMENT_OF, CROSSING, SIBLING
095    }
096
097    /**
098     * <p>Represents a child selector or a parent selector.</p>
099     *
100     * <p>In addition to the standard CSS notation for child selectors, JOSM also supports
101     * an "inverse" notation:</p>
102     * <pre>
103     *    selector_a &gt; selector_b { ... }       // the standard notation (child selector)
104     *    relation[type=route] &gt; way { ... }    // example (all ways of a route)
105     *
106     *    selector_a &lt; selector_b { ... }       // the inverse notation (parent selector)
107     *    node[traffic_calming] &lt; way { ... }   // example (way that has a traffic calming node)
108     * </pre>
109     * <p>Child: see <a href="https://josm.openstreetmap.de/wiki/Help/Styles/MapCSSImplementation#Childselector">wiki</a>
110     * <br>Parent: see <a href="https://josm.openstreetmap.de/wiki/Help/Styles/MapCSSImplementation#Parentselector">wiki</a></p>
111     */
112    class ChildOrParentSelector implements Selector {
113        public final Selector left;
114        public final LinkSelector link;
115        public final Selector right;
116        public final ChildOrParentSelectorType type;
117
118        /**
119         * Constructs a new {@code ChildOrParentSelector}.
120         * @param a the first selector
121         * @param link link
122         * @param b the second selector
123         * @param type the selector type
124         */
125        public ChildOrParentSelector(Selector a, LinkSelector link, Selector b, ChildOrParentSelectorType type) {
126            CheckParameterUtil.ensureParameterNotNull(a, "a");
127            CheckParameterUtil.ensureParameterNotNull(b, "b");
128            CheckParameterUtil.ensureParameterNotNull(link, "link");
129            CheckParameterUtil.ensureParameterNotNull(type, "type");
130            this.left = a;
131            this.link = link;
132            this.right = b;
133            this.type = type;
134        }
135
136        /**
137         * <p>Finds the first referrer matching {@link #left}</p>
138         *
139         * <p>The visitor works on an environment and it saves the matching
140         * referrer in {@code e.parent} and its relative position in the
141         * list referrers "child list" in {@code e.index}.</p>
142         *
143         * <p>If after execution {@code e.parent} is null, no matching
144         * referrer was found.</p>
145         *
146         */
147        private class MatchingReferrerFinder implements OsmPrimitiveVisitor {
148            private final Environment e;
149
150            /**
151             * Constructor
152             * @param e the environment against which we match
153             */
154            MatchingReferrerFinder(Environment e) {
155                this.e = e;
156            }
157
158            @Override
159            public void visit(Node n) {
160                // node should never be a referrer
161                throw new AssertionError();
162            }
163
164            private <T extends OsmPrimitive> void doVisit(T parent, IntSupplier counter, IntFunction<OsmPrimitive> getter) {
165                // If e.parent is already set to the first matching referrer.
166                // We skip any following referrer injected into the visitor.
167                if (e.parent != null) return;
168
169                if (!left.matches(e.withPrimitive(parent)))
170                    return;
171                int count = counter.getAsInt();
172                if (link.conds == null) {
173                    // index is not needed, we can avoid the sequential search below
174                    e.parent = parent;
175                    e.count = count;
176                    return;
177                }
178                for (int i = 0; i < count; i++) {
179                    if (getter.apply(i).equals(e.osm) && link.matches(e.withParentAndIndexAndLinkContext(parent, i, count))) {
180                        e.parent = parent;
181                        e.index = i;
182                        e.count = count;
183                        return;
184                    }
185                }
186            }
187
188            @Override
189            public void visit(Way w) {
190                doVisit(w, w::getNodesCount, w::getNode);
191            }
192
193            @Override
194            public void visit(Relation r) {
195                doVisit(r, r::getMembersCount, i -> r.getMember(i).getMember());
196            }
197        }
198
199        private abstract static class AbstractFinder implements OsmPrimitiveVisitor {
200            protected final Environment e;
201
202            protected AbstractFinder(Environment e) {
203                this.e = e;
204            }
205
206            @Override
207            public void visit(Node n) {
208            }
209
210            @Override
211            public void visit(Way w) {
212            }
213
214            @Override
215            public void visit(Relation r) {
216            }
217
218            public void visit(Collection<? extends OsmPrimitive> primitives) {
219                for (OsmPrimitive p : primitives) {
220                    if (e.child != null) {
221                        // abort if first match has been found
222                        break;
223                    } else if (isPrimitiveUsable(p)) {
224                        p.accept(this);
225                    }
226                }
227            }
228
229            public boolean isPrimitiveUsable(OsmPrimitive p) {
230                return !e.osm.equals(p) && p.isUsable();
231            }
232        }
233
234        private class MultipolygonOpenEndFinder extends AbstractFinder {
235
236            @Override
237            public void visit(Way w) {
238                w.visitReferrers(innerVisitor);
239            }
240
241            MultipolygonOpenEndFinder(Environment e) {
242                super(e);
243            }
244
245            private final OsmPrimitiveVisitor innerVisitor = new AbstractFinder(e) {
246                @Override
247                public void visit(Relation r) {
248                    if (left.matches(e.withPrimitive(r))) {
249                        final List<Node> openEnds = MultipolygonCache.getInstance().get(r).getOpenEnds();
250                        final int openEndIndex = openEnds.indexOf(e.osm);
251                        if (openEndIndex >= 0) {
252                            e.parent = r;
253                            e.index = openEndIndex;
254                            e.count = openEnds.size();
255                        }
256                    }
257                }
258            };
259        }
260
261        private final class CrossingFinder extends AbstractFinder {
262
263            private final String layer;
264
265            private CrossingFinder(Environment e) {
266                super(e);
267                CheckParameterUtil.ensureThat(e.osm instanceof Way, "Only ways are supported");
268                layer = OsmUtils.getLayer(e.osm);
269            }
270
271            @Override
272            public void visit(Way w) {
273                if (e.child == null && Objects.equals(layer, OsmUtils.getLayer(w))
274                    && left.matches(new Environment(w).withParent(e.osm))
275                    && e.osm instanceof Way && Geometry.PolygonIntersection.CROSSING.equals(
276                            Geometry.polygonIntersection(w.getNodes(), ((Way) e.osm).getNodes()))) {
277                    e.child = w;
278                }
279            }
280        }
281
282        private class ContainsFinder extends AbstractFinder {
283            protected ContainsFinder(Environment e) {
284                super(e);
285                CheckParameterUtil.ensureThat(!(e.osm instanceof Node), "Nodes not supported");
286            }
287
288            @Override
289            public void visit(Node n) {
290                if (e.child == null && left.matches(new Environment(n).withParent(e.osm))
291                    && ((e.osm instanceof Way && Geometry.nodeInsidePolygon(n, ((Way) e.osm).getNodes()))
292                            || (e.osm instanceof Relation && (
293                                    (Relation) e.osm).isMultipolygon() && Geometry.isNodeInsideMultiPolygon(n, (Relation) e.osm, null)))) {
294                    e.child = n;
295                }
296            }
297
298            @Override
299            public void visit(Way w) {
300                if (e.child == null && left.matches(new Environment(w).withParent(e.osm))
301                    && ((e.osm instanceof Way && Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(
302                            Geometry.polygonIntersection(w.getNodes(), ((Way) e.osm).getNodes())))
303                            || (e.osm instanceof Relation && (
304                                    (Relation) e.osm).isMultipolygon()
305                                    && Geometry.isPolygonInsideMultiPolygon(w.getNodes(), (Relation) e.osm, null)))) {
306                    e.child = w;
307                }
308            }
309        }
310
311        @Override
312        public boolean matches(Environment e) {
313
314            if (!right.matches(e))
315                return false;
316
317            if (ChildOrParentSelectorType.ELEMENT_OF.equals(type)) {
318
319                if (e.osm instanceof Node || e.osm.getDataSet() == null) {
320                    // nodes cannot contain elements
321                    return false;
322                }
323
324                ContainsFinder containsFinder;
325                try {
326                    // if right selector also matches relations and if matched primitive is a way which is part of a multipolygon,
327                    // use the multipolygon for further analysis
328                    if (!(e.osm instanceof Way)
329                            || (right instanceof OptimizedGeneralSelector
330                            && !((OptimizedGeneralSelector) right).matchesBase(OsmPrimitiveType.RELATION))) {
331                        throw new NoSuchElementException();
332                    }
333                    final Collection<Relation> multipolygons = Utils.filteredCollection(SubclassFilteredCollection.filter(
334                            e.osm.getReferrers(), p -> p.hasTag("type", "multipolygon")), Relation.class);
335                    final Relation multipolygon = multipolygons.iterator().next();
336                    if (multipolygon == null) throw new NoSuchElementException();
337                    final Set<OsmPrimitive> members = multipolygon.getMemberPrimitives();
338                    containsFinder = new ContainsFinder(new Environment(multipolygon)) {
339                        @Override
340                        public boolean isPrimitiveUsable(OsmPrimitive p) {
341                            return super.isPrimitiveUsable(p) && !members.contains(p);
342                        }
343                    };
344                } catch (NoSuchElementException ignore) {
345                    Logging.trace(ignore);
346                    containsFinder = new ContainsFinder(e);
347                }
348                e.parent = e.osm;
349
350                if (left instanceof OptimizedGeneralSelector) {
351                    if (((OptimizedGeneralSelector) left).matchesBase(OsmPrimitiveType.NODE)) {
352                        containsFinder.visit(e.osm.getDataSet().searchNodes(e.osm.getBBox()));
353                    }
354                    if (((OptimizedGeneralSelector) left).matchesBase(OsmPrimitiveType.WAY)) {
355                        containsFinder.visit(e.osm.getDataSet().searchWays(e.osm.getBBox()));
356                    }
357                } else {
358                    // use slow test
359                    containsFinder.visit(e.osm.getDataSet().allPrimitives());
360                }
361
362                return e.child != null;
363
364            } else if (ChildOrParentSelectorType.CROSSING.equals(type) && e.osm instanceof Way) {
365                e.parent = e.osm;
366                final CrossingFinder crossingFinder = new CrossingFinder(e);
367                if (right instanceof OptimizedGeneralSelector
368                        && ((OptimizedGeneralSelector) right).matchesBase(OsmPrimitiveType.WAY)) {
369                    crossingFinder.visit(e.osm.getDataSet().searchWays(e.osm.getBBox()));
370                }
371                return e.child != null;
372            } else if (ChildOrParentSelectorType.SIBLING.equals(type)) {
373                if (e.osm instanceof Node) {
374                    for (Way w : Utils.filteredCollection(e.osm.getReferrers(true), Way.class)) {
375                        final int i = w.getNodes().indexOf(e.osm);
376                        if (i - 1 >= 0) {
377                            final Node n = w.getNode(i - 1);
378                            final Environment e2 = e.withPrimitive(n).withParent(w).withChild(e.osm);
379                            if (left.matches(e2) && link.matches(e2.withLinkContext())) {
380                                e.child = n;
381                                e.index = i;
382                                e.count = w.getNodesCount();
383                                e.parent = w;
384                                return true;
385                            }
386                        }
387                    }
388                }
389            } else if (ChildOrParentSelectorType.CHILD.equals(type)
390                    && link.conds != null && !link.conds.isEmpty()
391                    && link.conds.get(0) instanceof OpenEndPseudoClassCondition) {
392                if (e.osm instanceof Node) {
393                    e.osm.visitReferrers(new MultipolygonOpenEndFinder(e));
394                    return e.parent != null;
395                }
396            } else if (ChildOrParentSelectorType.CHILD.equals(type)) {
397                MatchingReferrerFinder collector = new MatchingReferrerFinder(e);
398                e.osm.visitReferrers(collector);
399                if (e.parent != null)
400                    return true;
401            } else if (ChildOrParentSelectorType.PARENT.equals(type)) {
402                if (e.osm instanceof Way) {
403                    List<Node> wayNodes = ((Way) e.osm).getNodes();
404                    for (int i = 0; i < wayNodes.size(); i++) {
405                        Node n = wayNodes.get(i);
406                        if (left.matches(e.withPrimitive(n))
407                            && link.matches(e.withChildAndIndexAndLinkContext(n, i, wayNodes.size()))) {
408                            e.child = n;
409                            e.index = i;
410                            e.count = wayNodes.size();
411                            return true;
412                        }
413                    }
414                } else if (e.osm instanceof Relation) {
415                    List<RelationMember> members = ((Relation) e.osm).getMembers();
416                    for (int i = 0; i < members.size(); i++) {
417                        OsmPrimitive member = members.get(i).getMember();
418                        if (left.matches(e.withPrimitive(member))
419                            && link.matches(e.withChildAndIndexAndLinkContext(member, i, members.size()))) {
420                            e.child = member;
421                            e.index = i;
422                            e.count = members.size();
423                            return true;
424                        }
425                    }
426                }
427            }
428            return false;
429        }
430
431        @Override
432        public Subpart getSubpart() {
433            return right.getSubpart();
434        }
435
436        @Override
437        public Range getRange() {
438            return right.getRange();
439        }
440
441        @Override
442        public Selector optimizedBaseCheck() {
443            return new ChildOrParentSelector(left, link, right.optimizedBaseCheck(), type);
444        }
445
446        @Override
447        public String toString() {
448            return left.toString() + ' ' + (ChildOrParentSelectorType.PARENT.equals(type) ? '<' : '>') + link + ' ' + right;
449        }
450    }
451
452    /**
453     * Super class of {@link org.openstreetmap.josm.gui.mappaint.mapcss.Selector.GeneralSelector} and
454     * {@link org.openstreetmap.josm.gui.mappaint.mapcss.Selector.LinkSelector}.
455     * @since 5841
456     */
457    abstract class AbstractSelector implements Selector {
458
459        protected final List<Condition> conds;
460
461        protected AbstractSelector(List<Condition> conditions) {
462            if (conditions == null || conditions.isEmpty()) {
463                this.conds = null;
464            } else {
465                this.conds = conditions;
466            }
467        }
468
469        /**
470         * Determines if all conditions match the given environment.
471         * @param env The environment to check
472         * @return {@code true} if all conditions apply, false otherwise.
473         */
474        @Override
475        public boolean matches(Environment env) {
476            CheckParameterUtil.ensureParameterNotNull(env, "env");
477            if (conds == null) return true;
478            for (Condition c : conds) {
479                try {
480                    if (!c.applies(env)) return false;
481                } catch (PatternSyntaxException e) {
482                    Logging.log(Logging.LEVEL_ERROR, "PatternSyntaxException while applying condition" + c + ':', e);
483                    return false;
484                }
485            }
486            return true;
487        }
488
489        /**
490         * Returns the list of conditions.
491         * @return the list of conditions
492         */
493        public List<Condition> getConditions() {
494            if (conds == null) {
495                return Collections.emptyList();
496            }
497            return Collections.unmodifiableList(conds);
498        }
499    }
500
501    /**
502     * In a child selector, conditions on the link between a parent and a child object.
503     * See <a href="https://josm.openstreetmap.de/wiki/Help/Styles/MapCSSImplementation#Linkselector">wiki</a>
504     */
505    class LinkSelector extends AbstractSelector {
506
507        public LinkSelector(List<Condition> conditions) {
508            super(conditions);
509        }
510
511        @Override
512        public boolean matches(Environment env) {
513            Utils.ensure(env.isLinkContext(), "Requires LINK context in environment, got ''{0}''", env.getContext());
514            return super.matches(env);
515        }
516
517        @Override
518        public Subpart getSubpart() {
519            throw new UnsupportedOperationException("Not supported yet.");
520        }
521
522        @Override
523        public Range getRange() {
524            throw new UnsupportedOperationException("Not supported yet.");
525        }
526
527        @Override
528        public Selector optimizedBaseCheck() {
529            throw new UnsupportedOperationException();
530        }
531
532        @Override
533        public String toString() {
534            return "LinkSelector{conditions=" + conds + '}';
535        }
536    }
537
538    /**
539     * General selector. See <a href="https://josm.openstreetmap.de/wiki/Help/Styles/MapCSSImplementation#Selectors">wiki</a>
540     */
541    class GeneralSelector extends OptimizedGeneralSelector {
542
543        public GeneralSelector(String base, Pair<Integer, Integer> zoom, List<Condition> conds, Subpart subpart) {
544            super(base, zoom, conds, subpart);
545        }
546
547        public boolean matchesConditions(Environment e) {
548            return super.matches(e);
549        }
550
551        @Override
552        public Selector optimizedBaseCheck() {
553            return new OptimizedGeneralSelector(this);
554        }
555
556        @Override
557        public boolean matches(Environment e) {
558            return matchesBase(e) && super.matches(e);
559        }
560    }
561
562    /**
563     * Superclass of {@link GeneralSelector}. Used to create an "optimized" copy of this selector that omits the base check.
564     * @see Selector#optimizedBaseCheck
565     */
566    class OptimizedGeneralSelector extends AbstractSelector {
567        public final String base;
568        public final Range range;
569        public final Subpart subpart;
570
571        public OptimizedGeneralSelector(String base, Pair<Integer, Integer> zoom, List<Condition> conds, Subpart subpart) {
572            super(conds);
573            this.base = base;
574            if (zoom != null) {
575                int a = zoom.a == null ? 0 : zoom.a;
576                int b = zoom.b == null ? Integer.MAX_VALUE : zoom.b;
577                if (a <= b) {
578                    range = fromLevel(a, b);
579                } else {
580                    range = Range.ZERO_TO_INFINITY;
581                }
582            } else {
583                range = Range.ZERO_TO_INFINITY;
584            }
585            this.subpart = subpart != null ? subpart : Subpart.DEFAULT_SUBPART;
586        }
587
588        public OptimizedGeneralSelector(String base, Range range, List<Condition> conds, Subpart subpart) {
589            super(conds);
590            this.base = base;
591            this.range = range;
592            this.subpart = subpart != null ? subpart : Subpart.DEFAULT_SUBPART;
593        }
594
595        public OptimizedGeneralSelector(GeneralSelector s) {
596            this(s.base, s.range, s.conds, s.subpart);
597        }
598
599        @Override
600        public Subpart getSubpart() {
601            return subpart;
602        }
603
604        @Override
605        public Range getRange() {
606            return range;
607        }
608
609        public String getBase() {
610            return base;
611        }
612
613        public boolean matchesBase(OsmPrimitiveType type) {
614            if ("*".equals(base)) {
615                return true;
616            } else if (OsmPrimitiveType.NODE.equals(type)) {
617                return "node".equals(base);
618            } else if (OsmPrimitiveType.WAY.equals(type)) {
619                return "way".equals(base) || "area".equals(base);
620            } else if (OsmPrimitiveType.RELATION.equals(type)) {
621                return "area".equals(base) || "relation".equals(base) || "canvas".equals(base);
622            }
623            return false;
624        }
625
626        public boolean matchesBase(OsmPrimitive p) {
627            if (!matchesBase(p.getType())) {
628                return false;
629            } else {
630                if (p instanceof Relation) {
631                    if ("area".equals(base)) {
632                        return ((Relation) p).isMultipolygon();
633                    } else if ("canvas".equals(base)) {
634                        return p.get("#canvas") != null;
635                    }
636                }
637                return true;
638            }
639        }
640
641        public boolean matchesBase(Environment e) {
642            return matchesBase(e.osm);
643        }
644
645        @Override
646        public Selector optimizedBaseCheck() {
647            throw new UnsupportedOperationException();
648        }
649
650        public static Range fromLevel(int a, int b) {
651            if (a > b)
652                throw new AssertionError();
653            double lower = 0;
654            double upper = Double.POSITIVE_INFINITY;
655            if (b != Integer.MAX_VALUE) {
656                lower = level2scale(b + 1);
657            }
658            if (a != 0) {
659                upper = level2scale(a);
660            }
661            return new Range(lower, upper);
662        }
663
664        public static double level2scale(int lvl) {
665            if (lvl < 0)
666                throw new IllegalArgumentException("lvl must be >= 0 but is "+lvl);
667            // preliminary formula - map such that mapnik imagery tiles of the same
668            // or similar level are displayed at the given scale
669            return 2.0 * Math.PI * WGS84.a / Math.pow(2.0, lvl) / 2.56;
670        }
671
672        public static int scale2level(double scale) {
673            if (scale < 0)
674                throw new IllegalArgumentException("scale must be >= 0 but is "+scale);
675            return (int) Math.floor(Math.log(2 * Math.PI * WGS84.a / 2.56 / scale) / Math.log(2));
676        }
677
678        @Override
679        public String toString() {
680            return base + (Range.ZERO_TO_INFINITY.equals(range) ? "" : range) + Utils.join("", conds)
681                    + (subpart != null && subpart != Subpart.DEFAULT_SUBPART ? ("::" + subpart) : "");
682        }
683    }
684}