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