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