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