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