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