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