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