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