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