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        public boolean matches(Environment env) {
417            if (conds == null) return true;
418            for (Condition c : conds) {
419                try {
420                    if (!c.applies(env)) return false;
421                } catch (PatternSyntaxException e) {
422                    Main.error("PatternSyntaxException while applying condition" + c +": "+e.getMessage());
423                    return false;
424                }
425            }
426            return true;
427        }
428
429        public List<Condition> getConditions() {
430            if (conds == null) {
431                return Collections.emptyList();
432            }
433            return Collections.unmodifiableList(conds);
434        }
435    }
436
437    public static class LinkSelector extends AbstractSelector {
438
439        public LinkSelector(List<Condition> conditions) {
440            super(conditions);
441        }
442
443        @Override
444        public boolean matches(Environment env) {
445            Utils.ensure(env.isLinkContext(), "Requires LINK context in environment, got ''{0}''", env.getContext());
446            return super.matches(env);
447        }
448
449        @Override
450        public String getSubpart() {
451            throw new UnsupportedOperationException("Not supported yet.");
452        }
453
454        @Override
455        public Range getRange() {
456            throw new UnsupportedOperationException("Not supported yet.");
457        }
458
459        @Override
460        public Selector optimizedBaseCheck() {
461            throw new UnsupportedOperationException();
462        }
463
464        @Override
465        public String toString() {
466            return "LinkSelector{" + "conditions=" + conds + '}';
467        }
468    }
469
470    public static class GeneralSelector extends OptimizedGeneralSelector {
471
472        public GeneralSelector(String base, Pair<Integer, Integer> zoom, List<Condition> conds, String subpart) {
473            super(base, zoom, conds, subpart);
474        }
475        
476        public boolean matchesConditions(Environment e) {
477            return super.matches(e);
478        }
479
480        @Override
481        public Selector optimizedBaseCheck() {
482            return new OptimizedGeneralSelector(this);
483        }
484
485        @Override
486        public boolean matches(Environment e) {
487            return matchesBase(e) && super.matches(e);
488        }
489    }
490    
491    public static class OptimizedGeneralSelector extends AbstractSelector {
492        public final String base;
493        public final Range range;
494        public final String subpart;
495
496        public OptimizedGeneralSelector(String base, Pair<Integer, Integer> zoom, List<Condition> conds, String subpart) {
497            super(conds);
498            this.base = base;
499            if (zoom != null) {
500                int a = zoom.a == null ? 0 : zoom.a;
501                int b = zoom.b == null ? Integer.MAX_VALUE : zoom.b;
502                if (a <= b) {
503                    range = fromLevel(a, b);
504                } else {
505                    range = Range.ZERO_TO_INFINITY;
506                }
507            } else {
508                range = Range.ZERO_TO_INFINITY;
509            }
510            this.subpart = subpart;
511        }
512        
513        public OptimizedGeneralSelector(String base, Range range, List<Condition> conds, String subpart) {
514            super(conds);
515            this.base = base;
516            this.range = range;
517            this.subpart = subpart;
518        }
519        
520        public OptimizedGeneralSelector(GeneralSelector s) {
521            this(s.base, s.range, s.conds, s.subpart);
522        }
523
524        @Override
525        public String getSubpart() {
526            return subpart;
527        }
528
529        @Override
530        public Range getRange() {
531            return range;
532        }
533
534        public String getBase() {
535            return base;
536        }
537
538        public boolean matchesBase(OsmPrimitiveType type) {
539            if ("*".equals(base)) {
540                return true;
541            } else if (OsmPrimitiveType.NODE.equals(type)) {
542                return "node".equals(base);
543            } else if (OsmPrimitiveType.WAY.equals(type)) {
544                return "way".equals(base) || "area".equals(base);
545            } else if (OsmPrimitiveType.RELATION.equals(type)) {
546                return "area".equals(base) || "relation".equals(base) || "canvas".equals(base);
547            }
548            return false;
549        }
550
551        public boolean matchesBase(OsmPrimitive p) {
552            if (!matchesBase(p.getType())) {
553                return false;
554            } else {
555                if (p instanceof Relation) {
556                    if ("area".equals(base)) {
557                        return ((Relation) p).isMultipolygon();
558                    } else if ("canvas".equals(base)) {
559                        return p.get("#canvas") != null;
560                    }
561                }
562                return true;
563            }
564        }
565
566        public boolean matchesBase(Environment e) {
567            return matchesBase(e.osm);
568        }
569
570        @Override
571        public Selector optimizedBaseCheck() {
572            throw new UnsupportedOperationException();
573        }
574        
575        public static Range fromLevel(int a, int b) {
576            if (a > b)
577                throw new AssertionError();
578            double lower = 0;
579            double upper = Double.POSITIVE_INFINITY;
580            if (b != Integer.MAX_VALUE) {
581                lower = level2scale(b + 1);
582            }
583            if (a != 0) {
584                upper = level2scale(a);
585            }
586            return new Range(lower, upper);
587        }
588
589        static final double R = 6378135;
590
591        public static double level2scale(int lvl) {
592            if (lvl < 0)
593                throw new IllegalArgumentException();
594            // preliminary formula - map such that mapnik imagery tiles of the same
595            // or similar level are displayed at the given scale
596            return 2.0 * Math.PI * R / Math.pow(2.0, lvl) / 2.56;
597        }
598
599        @Override
600        public String toString() {
601            return base + (Range.ZERO_TO_INFINITY.equals(range) ? "" : range) + Utils.join("", conds) + (subpart != null ? ("::" + subpart) : "");
602        }
603    }
604}