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