001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.actions.search; 003 004import static org.openstreetmap.josm.tools.I18n.marktr; 005import static org.openstreetmap.josm.tools.I18n.tr; 006 007import java.io.PushbackReader; 008import java.io.StringReader; 009import java.text.Normalizer; 010import java.util.Arrays; 011import java.util.Collection; 012import java.util.HashMap; 013import java.util.Map; 014import java.util.regex.Matcher; 015import java.util.regex.Pattern; 016import java.util.regex.PatternSyntaxException; 017 018import org.openstreetmap.josm.Main; 019import org.openstreetmap.josm.actions.search.PushbackTokenizer.Range; 020import org.openstreetmap.josm.actions.search.PushbackTokenizer.Token; 021import org.openstreetmap.josm.data.Bounds; 022import org.openstreetmap.josm.data.osm.Node; 023import org.openstreetmap.josm.data.osm.OsmPrimitive; 024import org.openstreetmap.josm.data.osm.OsmUtils; 025import org.openstreetmap.josm.data.osm.Relation; 026import org.openstreetmap.josm.data.osm.RelationMember; 027import org.openstreetmap.josm.data.osm.Way; 028import org.openstreetmap.josm.tools.DateUtils; 029import org.openstreetmap.josm.tools.Geometry; 030import org.openstreetmap.josm.tools.Predicate; 031 032/** 033 Implements a google-like search. 034 <br> 035 Grammar: 036<pre> 037expression = 038 fact | expression 039 fact expression 040 fact 041 042fact = 043 ( expression ) 044 -fact 045 term? 046 term=term 047 term:term 048 term 049 </pre> 050 051 @author Imi 052 */ 053public class SearchCompiler { 054 055 private boolean caseSensitive = false; 056 private boolean regexSearch = false; 057 private static String rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}"); 058 private static String rxErrorMsgNoPos = marktr("The regex \"{0}\" had a parse error, full error:\n\n{1}"); 059 private PushbackTokenizer tokenizer; 060 private static Map<String, SimpleMatchFactory> simpleMatchFactoryMap = new HashMap<String, SimpleMatchFactory>(); 061 private static Map<String, UnaryMatchFactory> unaryMatchFactoryMap = new HashMap<String, UnaryMatchFactory>(); 062 private static Map<String, BinaryMatchFactory> binaryMatchFactoryMap = new HashMap<String, BinaryMatchFactory>(); 063 064 public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) { 065 this.caseSensitive = caseSensitive; 066 this.regexSearch = regexSearch; 067 this.tokenizer = tokenizer; 068 069 /* register core match factories at first instance, so plugins should 070 * never be able to generate a NPE 071 */ 072 if (simpleMatchFactoryMap.isEmpty()) { 073 addMatchFactory(new CoreSimpleMatchFactory()); 074 } 075 if (unaryMatchFactoryMap.isEmpty()) { 076 addMatchFactory(new CoreUnaryMatchFactory()); 077 } 078 079 } 080 081 /** 082 * Add (register) MatchFactory with SearchCompiler 083 * @param factory 084 */ 085 public static void addMatchFactory(MatchFactory factory) { 086 for (String keyword : factory.getKeywords()) { 087 // TODO: check for keyword collisions 088 if (factory instanceof SimpleMatchFactory) { 089 simpleMatchFactoryMap.put(keyword, (SimpleMatchFactory)factory); 090 } else if (factory instanceof UnaryMatchFactory) { 091 unaryMatchFactoryMap.put(keyword, (UnaryMatchFactory)factory); 092 } else if (factory instanceof BinaryMatchFactory) { 093 binaryMatchFactoryMap.put(keyword, (BinaryMatchFactory)factory); 094 } else 095 throw new AssertionError("Unknown match factory"); 096 } 097 } 098 099 public class CoreSimpleMatchFactory implements SimpleMatchFactory { 100 private Collection<String> keywords = Arrays.asList("id", "version", 101 "changeset", "nodes", "tags", "areasize", "modified", "selected", 102 "incomplete", "untagged", "closed", "new", "indownloadedarea", 103 "allindownloadedarea", "inview", "allinview", "timestamp", "nth", "nth%"); 104 105 @Override 106 public Match get(String keyword, PushbackTokenizer tokenizer) throws ParseError { 107 if ("modified".equals(keyword)) 108 return new Modified(); 109 else if ("selected".equals(keyword)) 110 return new Selected(); 111 else if ("incomplete".equals(keyword)) 112 return new Incomplete(); 113 else if ("untagged".equals(keyword)) 114 return new Untagged(); 115 else if ("closed".equals(keyword)) 116 return new Closed(); 117 else if ("new".equals(keyword)) 118 return new New(); 119 else if ("indownloadedarea".equals(keyword)) 120 return new InDataSourceArea(false); 121 else if ("allindownloadedarea".equals(keyword)) 122 return new InDataSourceArea(true); 123 else if ("inview".equals(keyword)) 124 return new InView(false); 125 else if ("allinview".equals(keyword)) 126 return new InView(true); 127 else if (tokenizer != null) { 128 if ("id".equals(keyword)) 129 return new Id(tokenizer); 130 else if ("version".equals(keyword)) 131 return new Version(tokenizer); 132 else if ("changeset".equals(keyword)) 133 return new ChangesetId(tokenizer); 134 else if ("nodes".equals(keyword)) 135 return new NodeCountRange(tokenizer); 136 else if ("tags".equals(keyword)) 137 return new TagCountRange(tokenizer); 138 else if ("areasize".equals(keyword)) 139 return new AreaSize(tokenizer); 140 else if ("nth".equals(keyword)) 141 return new Nth(tokenizer, false); 142 else if ("nth%".equals(keyword)) 143 return new Nth(tokenizer, true); 144 else if ("timestamp".equals(keyword)) { 145 String rangeS = " " + tokenizer.readTextOrNumber() + " "; // add leading/trailing space in order to get expected split (e.g. "a--" => {"a", ""}) 146 String[] rangeA = rangeS.split("/"); 147 if (rangeA.length == 1) 148 return new KeyValue(keyword, rangeS.trim(), regexSearch, caseSensitive); 149 else if (rangeA.length == 2) { 150 String rangeA1 = rangeA[0].trim(); 151 String rangeA2 = rangeA[1].trim(); 152 long minDate = DateUtils.fromString(rangeA1.isEmpty() ? "1980" : rangeA1).getTime(); // if min timestap is empty: use lowest possible date 153 long maxDate = rangeA2.isEmpty() ? System.currentTimeMillis() : DateUtils.fromString(rangeA2).getTime(); // if max timestamp is empty: use "now" 154 return new TimestampRange(minDate, maxDate); 155 } else 156 /* 157 * I18n: Don't translate timestamp keyword 158 */ throw new ParseError(tr("Expecting <i>min</i>/<i>max</i> after ''timestamp''")); 159 } 160 } 161 return null; 162 } 163 164 @Override 165 public Collection<String> getKeywords() { 166 return keywords; 167 } 168 } 169 170 public static class CoreUnaryMatchFactory implements UnaryMatchFactory { 171 private static Collection<String> keywords = Arrays.asList("parent", "child"); 172 173 @Override 174 public UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) { 175 if ("parent".equals(keyword)) 176 return new Parent(matchOperand); 177 else if ("child".equals(keyword)) 178 return new Child(matchOperand); 179 return null; 180 } 181 182 @Override 183 public Collection<String> getKeywords() { 184 return keywords; 185 } 186 } 187 188 /** 189 * Classes implementing this interface can provide Match operators. 190 */ 191 private interface MatchFactory { 192 public Collection<String> getKeywords(); 193 } 194 195 public interface SimpleMatchFactory extends MatchFactory { 196 public Match get(String keyword, PushbackTokenizer tokenizer) throws ParseError; 197 } 198 199 public interface UnaryMatchFactory extends MatchFactory { 200 public UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) throws ParseError; 201 } 202 203 public interface BinaryMatchFactory extends MatchFactory { 204 public BinaryMatch get(String keyword, Match lhs, Match rhs, PushbackTokenizer tokenizer) throws ParseError; 205 } 206 207 /** 208 * Base class for all search operators. 209 */ 210 abstract public static class Match implements Predicate<OsmPrimitive> { 211 212 abstract public boolean match(OsmPrimitive osm); 213 214 /** 215 * Tests whether one of the primitives matches. 216 */ 217 protected boolean existsMatch(Collection<? extends OsmPrimitive> primitives) { 218 for (OsmPrimitive p : primitives) { 219 if (match(p)) 220 return true; 221 } 222 return false; 223 } 224 225 /** 226 * Tests whether all primitives match. 227 */ 228 protected boolean forallMatch(Collection<? extends OsmPrimitive> primitives) { 229 for (OsmPrimitive p : primitives) { 230 if (!match(p)) 231 return false; 232 } 233 return true; 234 } 235 236 @Override 237 public final boolean evaluate(OsmPrimitive object) { 238 return match(object); 239 } 240 } 241 242 /** 243 * A unary search operator which may take data parameters. 244 */ 245 abstract public static class UnaryMatch extends Match { 246 247 protected final Match match; 248 249 public UnaryMatch(Match match) { 250 if (match == null) { 251 // "operator" (null) should mean the same as "operator()" 252 // (Always). I.e. match everything 253 this.match = new Always(); 254 } else { 255 this.match = match; 256 } 257 } 258 259 public Match getOperand() { 260 return match; 261 } 262 } 263 264 /** 265 * A binary search operator which may take data parameters. 266 */ 267 abstract public static class BinaryMatch extends Match { 268 269 protected final Match lhs; 270 protected final Match rhs; 271 272 public BinaryMatch(Match lhs, Match rhs) { 273 this.lhs = lhs; 274 this.rhs = rhs; 275 } 276 277 public Match getLhs() { 278 return lhs; 279 } 280 281 public Match getRhs() { 282 return rhs; 283 } 284 } 285 286 /** 287 * Matches every OsmPrimitive. 288 */ 289 public static class Always extends Match { 290 public static Always INSTANCE = new Always(); 291 @Override public boolean match(OsmPrimitive osm) { 292 return true; 293 } 294 } 295 296 /** 297 * Never matches any OsmPrimitive. 298 */ 299 public static class Never extends Match { 300 @Override 301 public boolean match(OsmPrimitive osm) { 302 return false; 303 } 304 } 305 306 /** 307 * Inverts the match. 308 */ 309 public static class Not extends UnaryMatch { 310 public Not(Match match) {super(match);} 311 @Override public boolean match(OsmPrimitive osm) { 312 return !match.match(osm); 313 } 314 @Override public String toString() {return "!"+match;} 315 public Match getMatch() { 316 return match; 317 } 318 } 319 320 /** 321 * Matches if the value of the corresponding key is ''yes'', ''true'', ''1'' or ''on''. 322 */ 323 private static class BooleanMatch extends Match { 324 private final String key; 325 private final boolean defaultValue; 326 327 public BooleanMatch(String key, boolean defaultValue) { 328 this.key = key; 329 this.defaultValue = defaultValue; 330 } 331 @Override 332 public boolean match(OsmPrimitive osm) { 333 Boolean ret = OsmUtils.getOsmBoolean(osm.get(key)); 334 if (ret == null) 335 return defaultValue; 336 else 337 return ret; 338 } 339 } 340 341 /** 342 * Matches if both left and right expressions match. 343 */ 344 public static class And extends BinaryMatch { 345 public And(Match lhs, Match rhs) {super(lhs, rhs);} 346 @Override public boolean match(OsmPrimitive osm) { 347 return lhs.match(osm) && rhs.match(osm); 348 } 349 @Override public String toString() { 350 return lhs + " && " + rhs; 351 } 352 } 353 354 /** 355 * Matches if the left OR the right expression match. 356 */ 357 public static class Or extends BinaryMatch { 358 public Or(Match lhs, Match rhs) {super(lhs, rhs);} 359 @Override public boolean match(OsmPrimitive osm) { 360 return lhs.match(osm) || rhs.match(osm); 361 } 362 @Override public String toString() { 363 return lhs + " || " + rhs; 364 } 365 } 366 367 /** 368 * Matches if the left OR the right expression match, but not both. 369 */ 370 public static class Xor extends BinaryMatch { 371 public Xor(Match lhs, Match rhs) {super(lhs, rhs);} 372 @Override public boolean match(OsmPrimitive osm) { 373 return lhs.match(osm) ^ rhs.match(osm); 374 } 375 @Override public String toString() { 376 return lhs + " ^ " + rhs; 377 } 378 } 379 380 /** 381 * Matches objects with ID in the given range. 382 */ 383 private static class Id extends RangeMatch { 384 public Id(Range range) {super(range);} 385 public Id(PushbackTokenizer tokenizer) throws ParseError { 386 this(tokenizer.readRange(tr("Range of primitive ids expected"))); 387 } 388 @Override protected Long getNumber(OsmPrimitive osm) { 389 return osm.isNew() ? 0 : osm.getUniqueId(); 390 } 391 @Override protected String getString() { 392 return "id"; 393 } 394 } 395 396 /** 397 * Matches objects with a changeset ID in the given range. 398 */ 399 private static class ChangesetId extends RangeMatch { 400 public ChangesetId(Range range) {super(range);} 401 public ChangesetId(PushbackTokenizer tokenizer) throws ParseError { 402 this(tokenizer.readRange(tr("Range of changeset ids expected"))); 403 } 404 @Override protected Long getNumber(OsmPrimitive osm) { 405 return (long) osm.getChangesetId(); 406 } 407 @Override protected String getString() { 408 return "changeset"; 409 } 410 } 411 412 /** 413 * Matches objects with a version number in the given range. 414 */ 415 private static class Version extends RangeMatch { 416 public Version(Range range) {super(range);} 417 public Version(PushbackTokenizer tokenizer) throws ParseError { 418 this(tokenizer.readRange(tr("Range of versions expected"))); 419 } 420 @Override protected Long getNumber(OsmPrimitive osm) { 421 return (long) osm.getVersion(); 422 } 423 @Override protected String getString() { 424 return "version"; 425 } 426 } 427 428 /** 429 * Matches objects with the given key-value pair. 430 */ 431 private static class KeyValue extends Match { 432 private final String key; 433 private final Pattern keyPattern; 434 private final String value; 435 private final Pattern valuePattern; 436 private final boolean caseSensitive; 437 438 public KeyValue(String key, String value, boolean regexSearch, boolean caseSensitive) throws ParseError { 439 this.caseSensitive = caseSensitive; 440 if (regexSearch) { 441 int searchFlags = regexFlags(caseSensitive); 442 443 try { 444 this.keyPattern = Pattern.compile(key, searchFlags); 445 } catch (PatternSyntaxException e) { 446 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage())); 447 } catch (Exception e) { 448 throw new ParseError(tr(rxErrorMsgNoPos, key, e.getMessage())); 449 } 450 try { 451 this.valuePattern = Pattern.compile(value, searchFlags); 452 } catch (PatternSyntaxException e) { 453 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage())); 454 } catch (Exception e) { 455 throw new ParseError(tr(rxErrorMsgNoPos, value, e.getMessage())); 456 } 457 this.key = key; 458 this.value = value; 459 460 } else if (caseSensitive) { 461 this.key = key; 462 this.value = value; 463 this.keyPattern = null; 464 this.valuePattern = null; 465 } else { 466 this.key = key.toLowerCase(); 467 this.value = value; 468 this.keyPattern = null; 469 this.valuePattern = null; 470 } 471 } 472 473 @Override public boolean match(OsmPrimitive osm) { 474 475 if (keyPattern != null) { 476 if (!osm.hasKeys()) 477 return false; 478 479 /* The string search will just get a key like 480 * 'highway' and look that up as osm.get(key). But 481 * since we're doing a regex match we'll have to loop 482 * over all the keys to see if they match our regex, 483 * and only then try to match against the value 484 */ 485 486 for (String k: osm.keySet()) { 487 String v = osm.get(k); 488 489 Matcher matcherKey = keyPattern.matcher(k); 490 boolean matchedKey = matcherKey.find(); 491 492 if (matchedKey) { 493 Matcher matcherValue = valuePattern.matcher(v); 494 boolean matchedValue = matcherValue.find(); 495 496 if (matchedValue) 497 return true; 498 } 499 } 500 } else { 501 String mv = null; 502 503 if (key.equals("timestamp")) { 504 mv = DateUtils.fromDate(osm.getTimestamp()); 505 } else { 506 mv = osm.get(key); 507 } 508 509 if (mv == null) 510 return false; 511 512 String v1 = caseSensitive ? mv : mv.toLowerCase(); 513 String v2 = caseSensitive ? value : value.toLowerCase(); 514 515 v1 = Normalizer.normalize(v1, Normalizer.Form.NFC); 516 v2 = Normalizer.normalize(v2, Normalizer.Form.NFC); 517 return v1.indexOf(v2) != -1; 518 } 519 520 return false; 521 } 522 @Override public String toString() {return key+"="+value;} 523 } 524 525 public static class ValueComparison extends Match { 526 private final String key; 527 private final String referenceValue; 528 private final int compareMode; 529 530 public ValueComparison(String key, String referenceValue, int compareMode) { 531 this.key = key; 532 this.referenceValue = referenceValue; 533 this.compareMode = compareMode; 534 } 535 536 @Override 537 public boolean match(OsmPrimitive osm) { 538 int compareResult; 539 try { 540 compareResult = Double.compare( 541 Double.parseDouble(osm.get(key)), 542 Double.parseDouble(referenceValue) 543 ); 544 } catch (Exception ignore) { 545 compareResult = osm.get(key).compareTo(referenceValue); 546 } 547 return compareMode < 0 ? compareResult < 0 : compareMode > 0 ? compareResult > 0 : compareResult == 0; 548 } 549 } 550 551 /** 552 * Matches objects with the exact given key-value pair. 553 */ 554 public static class ExactKeyValue extends Match { 555 556 private enum Mode { 557 ANY, ANY_KEY, ANY_VALUE, EXACT, NONE, MISSING_KEY, 558 ANY_KEY_REGEXP, ANY_VALUE_REGEXP, EXACT_REGEXP, MISSING_KEY_REGEXP; 559 } 560 561 private final String key; 562 private final String value; 563 private final Pattern keyPattern; 564 private final Pattern valuePattern; 565 private final Mode mode; 566 567 public ExactKeyValue(boolean regexp, String key, String value) throws ParseError { 568 if ("".equals(key)) 569 throw new ParseError(tr("Key cannot be empty when tag operator is used. Sample use: key=value")); 570 this.key = key; 571 this.value = value == null?"":value; 572 if ("".equals(this.value) && "*".equals(key)) { 573 mode = Mode.NONE; 574 } else if ("".equals(this.value)) { 575 if (regexp) { 576 mode = Mode.MISSING_KEY_REGEXP; 577 } else { 578 mode = Mode.MISSING_KEY; 579 } 580 } else if ("*".equals(key) && "*".equals(this.value)) { 581 mode = Mode.ANY; 582 } else if ("*".equals(key)) { 583 if (regexp) { 584 mode = Mode.ANY_KEY_REGEXP; 585 } else { 586 mode = Mode.ANY_KEY; 587 } 588 } else if ("*".equals(this.value)) { 589 if (regexp) { 590 mode = Mode.ANY_VALUE_REGEXP; 591 } else { 592 mode = Mode.ANY_VALUE; 593 } 594 } else { 595 if (regexp) { 596 mode = Mode.EXACT_REGEXP; 597 } else { 598 mode = Mode.EXACT; 599 } 600 } 601 602 if (regexp && key.length() > 0 && !key.equals("*")) { 603 try { 604 keyPattern = Pattern.compile(key, regexFlags(false)); 605 } catch (PatternSyntaxException e) { 606 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage())); 607 } catch (Exception e) { 608 throw new ParseError(tr(rxErrorMsgNoPos, key, e.getMessage())); 609 } 610 } else { 611 keyPattern = null; 612 } 613 if (regexp && this.value.length() > 0 && !this.value.equals("*")) { 614 try { 615 valuePattern = Pattern.compile(this.value, regexFlags(false)); 616 } catch (PatternSyntaxException e) { 617 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage())); 618 } catch (Exception e) { 619 throw new ParseError(tr(rxErrorMsgNoPos, value, e.getMessage())); 620 } 621 } else { 622 valuePattern = null; 623 } 624 } 625 626 @Override 627 public boolean match(OsmPrimitive osm) { 628 629 if (!osm.hasKeys()) 630 return mode == Mode.NONE; 631 632 switch (mode) { 633 case NONE: 634 return false; 635 case MISSING_KEY: 636 return osm.get(key) == null; 637 case ANY: 638 return true; 639 case ANY_VALUE: 640 return osm.get(key) != null; 641 case ANY_KEY: 642 for (String v:osm.getKeys().values()) { 643 if (v.equals(value)) 644 return true; 645 } 646 return false; 647 case EXACT: 648 return value.equals(osm.get(key)); 649 case ANY_KEY_REGEXP: 650 for (String v:osm.getKeys().values()) { 651 if (valuePattern.matcher(v).matches()) 652 return true; 653 } 654 return false; 655 case ANY_VALUE_REGEXP: 656 case EXACT_REGEXP: 657 for (String key: osm.keySet()) { 658 if (keyPattern.matcher(key).matches()) { 659 if (mode == Mode.ANY_VALUE_REGEXP 660 || valuePattern.matcher(osm.get(key)).matches()) 661 return true; 662 } 663 } 664 return false; 665 case MISSING_KEY_REGEXP: 666 for (String k:osm.keySet()) { 667 if (keyPattern.matcher(k).matches()) 668 return false; 669 } 670 return true; 671 } 672 throw new AssertionError("Missed state"); 673 } 674 675 @Override 676 public String toString() { 677 return key + '=' + value; 678 } 679 680 } 681 682 /** 683 * Match a string in any tags (key or value), with optional regex and case insensitivity. 684 */ 685 private static class Any extends Match { 686 private final String search; 687 private final Pattern searchRegex; 688 private final boolean caseSensitive; 689 690 public Any(String s, boolean regexSearch, boolean caseSensitive) throws ParseError { 691 s = Normalizer.normalize(s, Normalizer.Form.NFC); 692 this.caseSensitive = caseSensitive; 693 if (regexSearch) { 694 try { 695 this.searchRegex = Pattern.compile(s, regexFlags(caseSensitive)); 696 } catch (PatternSyntaxException e) { 697 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage())); 698 } catch (Exception e) { 699 throw new ParseError(tr(rxErrorMsgNoPos, s, e.getMessage())); 700 } 701 this.search = s; 702 } else if (caseSensitive) { 703 this.search = s; 704 this.searchRegex = null; 705 } else { 706 this.search = s.toLowerCase(); 707 this.searchRegex = null; 708 } 709 } 710 711 @Override public boolean match(OsmPrimitive osm) { 712 if (!osm.hasKeys() && osm.getUser() == null) 713 return search.isEmpty(); 714 715 for (String key: osm.keySet()) { 716 String value = osm.get(key); 717 if (searchRegex != null) { 718 719 value = Normalizer.normalize(value, Normalizer.Form.NFC); 720 721 Matcher keyMatcher = searchRegex.matcher(key); 722 Matcher valMatcher = searchRegex.matcher(value); 723 724 boolean keyMatchFound = keyMatcher.find(); 725 boolean valMatchFound = valMatcher.find(); 726 727 if (keyMatchFound || valMatchFound) 728 return true; 729 } else { 730 if (!caseSensitive) { 731 key = key.toLowerCase(); 732 value = value.toLowerCase(); 733 } 734 735 value = Normalizer.normalize(value, Normalizer.Form.NFC); 736 737 if (key.indexOf(search) != -1 || value.indexOf(search) != -1) 738 return true; 739 } 740 } 741 return false; 742 } 743 @Override public String toString() { 744 return search; 745 } 746 } 747 748 // TODO: change how we handle this 749 private static class ExactType extends Match { 750 private final Class<?> type; 751 public ExactType(String type) throws ParseError { 752 if ("node".equals(type)) { 753 this.type = Node.class; 754 } else if ("way".equals(type)) { 755 this.type = Way.class; 756 } else if ("relation".equals(type)) { 757 this.type = Relation.class; 758 } else 759 throw new ParseError(tr("Unknown primitive type: {0}. Allowed values are node, way or relation", 760 type)); 761 } 762 @Override public boolean match(OsmPrimitive osm) { 763 return osm.getClass() == type; 764 } 765 @Override public String toString() {return "type="+type;} 766 } 767 768 /** 769 * Matches objects last changed by the given username. 770 */ 771 private static class UserMatch extends Match { 772 private String user; 773 public UserMatch(String user) { 774 if (user.equals("anonymous")) { 775 this.user = null; 776 } else { 777 this.user = user; 778 } 779 } 780 781 @Override public boolean match(OsmPrimitive osm) { 782 if (osm.getUser() == null) 783 return user == null; 784 else 785 return osm.getUser().hasName(user); 786 } 787 788 @Override public String toString() { 789 return "user=" + (user == null ? "" : user); 790 } 791 } 792 793 /** 794 * Matches objects with the given relation role (i.e. "outer"). 795 */ 796 private static class RoleMatch extends Match { 797 private String role; 798 public RoleMatch(String role) { 799 if (role == null) { 800 this.role = ""; 801 } else { 802 this.role = role; 803 } 804 } 805 806 @Override public boolean match(OsmPrimitive osm) { 807 for (OsmPrimitive ref: osm.getReferrers()) { 808 if (ref instanceof Relation && !ref.isIncomplete() && !ref.isDeleted()) { 809 for (RelationMember m : ((Relation) ref).getMembers()) { 810 if (m.getMember() == osm) { 811 String testRole = m.getRole(); 812 if(role.equals(testRole == null ? "" : testRole)) 813 return true; 814 } 815 } 816 } 817 } 818 return false; 819 } 820 821 @Override public String toString() { 822 return "role=" + role; 823 } 824 } 825 826 /** 827 * Matches the n-th object of a relation and/or the n-th node of a way. 828 */ 829 private static class Nth extends Match { 830 831 private final int nth; 832 private final boolean modulo; 833 834 public Nth(PushbackTokenizer tokenizer, boolean modulo) throws ParseError { 835 this((int) tokenizer.readNumber(tr("Primitive id expected")), modulo); 836 } 837 838 private Nth(int nth, boolean modulo) { 839 this.nth = nth; 840 this.modulo = modulo; 841 } 842 843 @Override 844 public boolean match(OsmPrimitive osm) { 845 for (OsmPrimitive p : osm.getReferrers()) { 846 Integer idx = null; 847 if (p instanceof Way) { 848 Way w = (Way) p; 849 idx = w.getNodes().indexOf(osm); 850 } else if (p instanceof Relation) { 851 Relation r = (Relation) p; 852 idx = r.getMemberPrimitivesList().indexOf(osm); 853 } 854 if (idx != null) { 855 if (idx.intValue() == nth || (modulo && idx.intValue() % nth == 0)) { 856 return true; 857 } 858 } 859 } 860 return false; 861 } 862 } 863 864 /** 865 * Matches objects with properties in a certain range. 866 */ 867 private abstract static class RangeMatch extends Match { 868 869 private final long min; 870 private final long max; 871 872 public RangeMatch(long min, long max) { 873 this.min = Math.min(min, max); 874 this.max = Math.max(min, max); 875 } 876 877 public RangeMatch(Range range) { 878 this(range.getStart(), range.getEnd()); 879 } 880 881 protected abstract Long getNumber(OsmPrimitive osm); 882 883 protected abstract String getString(); 884 885 @Override 886 public boolean match(OsmPrimitive osm) { 887 Long num = getNumber(osm); 888 if (num == null) 889 return false; 890 else 891 return (num >= min) && (num <= max); 892 } 893 894 @Override 895 public String toString() { 896 return getString() + "=" + min + "-" + max; 897 } 898 } 899 900 901 /** 902 * Matches ways with a number of nodes in given range 903 */ 904 private static class NodeCountRange extends RangeMatch { 905 public NodeCountRange(Range range) { 906 super(range); 907 } 908 909 public NodeCountRange(PushbackTokenizer tokenizer) throws ParseError { 910 this(tokenizer.readRange(tr("Range of numbers expected"))); 911 } 912 913 @Override 914 protected Long getNumber(OsmPrimitive osm) { 915 if (!(osm instanceof Way)) 916 return null; 917 else 918 return (long) ((Way) osm).getRealNodesCount(); 919 } 920 921 @Override 922 protected String getString() { 923 return "nodes"; 924 } 925 } 926 927 /** 928 * Matches objects with a number of tags in given range 929 */ 930 private static class TagCountRange extends RangeMatch { 931 public TagCountRange(Range range) { 932 super(range); 933 } 934 935 public TagCountRange(PushbackTokenizer tokenizer) throws ParseError { 936 this(tokenizer.readRange(tr("Range of numbers expected"))); 937 } 938 939 @Override 940 protected Long getNumber(OsmPrimitive osm) { 941 return (long) osm.getKeys().size(); 942 } 943 944 @Override 945 protected String getString() { 946 return "tags"; 947 } 948 } 949 950 /** 951 * Matches objects with a timestamp in given range 952 */ 953 private static class TimestampRange extends RangeMatch { 954 955 public TimestampRange(long minCount, long maxCount) { 956 super(minCount, maxCount); 957 } 958 959 @Override 960 protected Long getNumber(OsmPrimitive osm) { 961 return osm.getTimestamp().getTime(); 962 } 963 964 @Override 965 protected String getString() { 966 return "timestamp"; 967 } 968 969 } 970 971 /** 972 * Matches objects that are new (i.e. have not been uploaded to the server) 973 */ 974 private static class New extends Match { 975 @Override public boolean match(OsmPrimitive osm) { 976 return osm.isNew(); 977 } 978 @Override public String toString() { 979 return "new"; 980 } 981 } 982 983 /** 984 * Matches all objects that have been modified, created, or undeleted 985 */ 986 private static class Modified extends Match { 987 @Override public boolean match(OsmPrimitive osm) { 988 return osm.isModified() || osm.isNewOrUndeleted(); 989 } 990 @Override public String toString() {return "modified";} 991 } 992 993 /** 994 * Matches all objects currently selected 995 */ 996 private static class Selected extends Match { 997 @Override public boolean match(OsmPrimitive osm) { 998 return Main.main.getCurrentDataSet().isSelected(osm); 999 } 1000 @Override public String toString() {return "selected";} 1001 } 1002 1003 /** 1004 * Match objects that are incomplete, where only id and type are known. 1005 * Typically some members of a relation are incomplete until they are 1006 * fetched from the server. 1007 */ 1008 private static class Incomplete extends Match { 1009 @Override public boolean match(OsmPrimitive osm) { 1010 return osm.isIncomplete(); 1011 } 1012 @Override public String toString() {return "incomplete";} 1013 } 1014 1015 /** 1016 * Matches objects that don't have any interesting tags (i.e. only has source, 1017 * FIXME, etc.). The complete list of uninteresting tags can be found here: 1018 * org.openstreetmap.josm.data.osm.OsmPrimitive.getUninterestingKeys() 1019 */ 1020 private static class Untagged extends Match { 1021 @Override public boolean match(OsmPrimitive osm) { 1022 return !osm.isTagged() && !osm.isIncomplete(); 1023 } 1024 @Override public String toString() {return "untagged";} 1025 } 1026 1027 /** 1028 * Matches ways which are closed (i.e. first and last node are the same) 1029 */ 1030 private static class Closed extends Match { 1031 @Override public boolean match(OsmPrimitive osm) { 1032 return osm instanceof Way && ((Way) osm).isClosed(); 1033 } 1034 @Override public String toString() {return "closed";} 1035 } 1036 1037 /** 1038 * Matches objects if they are parents of the expression 1039 */ 1040 public static class Parent extends UnaryMatch { 1041 public Parent(Match m) { 1042 super(m); 1043 } 1044 @Override public boolean match(OsmPrimitive osm) { 1045 boolean isParent = false; 1046 1047 if (osm instanceof Way) { 1048 for (Node n : ((Way)osm).getNodes()) { 1049 isParent |= match.match(n); 1050 } 1051 } else if (osm instanceof Relation) { 1052 for (RelationMember member : ((Relation)osm).getMembers()) { 1053 isParent |= match.match(member.getMember()); 1054 } 1055 } 1056 return isParent; 1057 } 1058 @Override public String toString() {return "parent(" + match + ")";} 1059 } 1060 1061 /** 1062 * Matches objects if they are children of the expression 1063 */ 1064 public static class Child extends UnaryMatch { 1065 1066 public Child(Match m) { 1067 super(m); 1068 } 1069 1070 @Override public boolean match(OsmPrimitive osm) { 1071 boolean isChild = false; 1072 for (OsmPrimitive p : osm.getReferrers()) { 1073 isChild |= match.match(p); 1074 } 1075 return isChild; 1076 } 1077 @Override public String toString() {return "child(" + match + ")";} 1078 } 1079 1080 /** 1081 * Matches if the size of the area is within the given range 1082 * 1083 * @author Ole Jørgen Brønner 1084 */ 1085 private static class AreaSize extends RangeMatch { 1086 1087 public AreaSize(Range range) { 1088 super(range); 1089 } 1090 1091 public AreaSize(PushbackTokenizer tokenizer) throws ParseError { 1092 this(tokenizer.readRange(tr("Range of numbers expected"))); 1093 } 1094 1095 @Override 1096 protected Long getNumber(OsmPrimitive osm) { 1097 if (!(osm instanceof Way && ((Way) osm).isClosed())) 1098 return null; 1099 Way way = (Way) osm; 1100 return (long) Geometry.closedWayArea(way); 1101 } 1102 1103 @Override 1104 protected String getString() { 1105 return "areasize"; 1106 } 1107 } 1108 1109 /** 1110 * Matches objects within the given bounds. 1111 */ 1112 private abstract static class InArea extends Match { 1113 1114 protected abstract Bounds getBounds(); 1115 protected final boolean all; 1116 1117 /** 1118 * @param all if true, all way nodes or relation members have to be within source area;if false, one suffices. 1119 */ 1120 public InArea(boolean all) { 1121 this.all = all; 1122 } 1123 1124 @Override 1125 public boolean match(OsmPrimitive osm) { 1126 if (!osm.isUsable()) 1127 return false; 1128 else if (osm instanceof Node) { 1129 Bounds bounds = getBounds(); 1130 return bounds != null && bounds.contains(((Node) osm).getCoor()); 1131 } else if (osm instanceof Way) { 1132 Collection<Node> nodes = ((Way) osm).getNodes(); 1133 return all ? forallMatch(nodes) : existsMatch(nodes); 1134 } else if (osm instanceof Relation) { 1135 Collection<OsmPrimitive> primitives = ((Relation) osm).getMemberPrimitives(); 1136 return all ? forallMatch(primitives) : existsMatch(primitives); 1137 } else 1138 return false; 1139 } 1140 } 1141 1142 /** 1143 * Matches objects within source area ("downloaded area"). 1144 */ 1145 private static class InDataSourceArea extends InArea { 1146 1147 public InDataSourceArea(boolean all) { 1148 super(all); 1149 } 1150 1151 @Override 1152 protected Bounds getBounds() { 1153 return new Bounds(Main.main.getCurrentDataSet().getDataSourceArea().getBounds2D()); 1154 } 1155 } 1156 1157 /** 1158 * Matches objects within current map view. 1159 */ 1160 private static class InView extends InArea { 1161 1162 public InView(boolean all) { 1163 super(all); 1164 } 1165 1166 @Override 1167 protected Bounds getBounds() { 1168 if (!Main.isDisplayingMapView()) { 1169 return null; 1170 } 1171 return Main.map.mapView.getRealBounds(); 1172 } 1173 } 1174 1175 public static class ParseError extends Exception { 1176 public ParseError(String msg) { 1177 super(msg); 1178 } 1179 public ParseError(Token expected, Token found) { 1180 this(tr("Unexpected token. Expected {0}, found {1}", expected, found)); 1181 } 1182 } 1183 1184 public static Match compile(String searchStr, boolean caseSensitive, boolean regexSearch) throws ParseError { 1185 return new SearchCompiler(caseSensitive, regexSearch, 1186 new PushbackTokenizer( 1187 new PushbackReader(new StringReader(searchStr)))) 1188 .parse(); 1189 } 1190 1191 /** 1192 * Parse search string. 1193 * 1194 * @return match determined by search string 1195 * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError 1196 */ 1197 public Match parse() throws ParseError { 1198 Match m = parseExpression(); 1199 if (!tokenizer.readIfEqual(Token.EOF)) 1200 throw new ParseError(tr("Unexpected token: {0}", tokenizer.nextToken())); 1201 if (m == null) 1202 return new Always(); 1203 return m; 1204 } 1205 1206 /** 1207 * Parse expression. This is a recursive method. 1208 * 1209 * @return match determined by parsing expression 1210 * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError 1211 */ 1212 private Match parseExpression() throws ParseError { 1213 Match factor = parseFactor(); 1214 if (factor == null) 1215 // empty search string 1216 return null; 1217 if (tokenizer.readIfEqual(Token.OR)) 1218 return new Or(factor, parseExpression(tr("Missing parameter for OR"))); 1219 else if (tokenizer.readIfEqual(Token.XOR)) 1220 return new Xor(factor, parseExpression(tr("Missing parameter for XOR"))); 1221 else { 1222 Match expression = parseExpression(); 1223 if (expression == null) 1224 // reached end of search string, no more recursive calls 1225 return factor; 1226 else 1227 // the default operator is AND 1228 return new And(factor, expression); 1229 } 1230 } 1231 1232 /** 1233 * Parse expression, showing the specified error message if parsing fails. 1234 * 1235 * @param errorMessage to display if parsing error occurs 1236 * @return match determined by parsing expression 1237 * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError 1238 * @see #parseExpression() 1239 */ 1240 private Match parseExpression(String errorMessage) throws ParseError { 1241 Match expression = parseExpression(); 1242 if (expression == null) 1243 throw new ParseError(errorMessage); 1244 else 1245 return expression; 1246 } 1247 1248 /** 1249 * Parse next factor (a search operator or search term). 1250 * 1251 * @return match determined by parsing factor string 1252 * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError 1253 */ 1254 private Match parseFactor() throws ParseError { 1255 if (tokenizer.readIfEqual(Token.LEFT_PARENT)) { 1256 Match expression = parseExpression(); 1257 if (!tokenizer.readIfEqual(Token.RIGHT_PARENT)) 1258 throw new ParseError(Token.RIGHT_PARENT, tokenizer.nextToken()); 1259 return expression; 1260 } else if (tokenizer.readIfEqual(Token.NOT)) { 1261 return new Not(parseFactor(tr("Missing operator for NOT"))); 1262 } else if (tokenizer.readIfEqual(Token.KEY)) { 1263 // factor consists of key:value or key=value 1264 String key = tokenizer.getText(); 1265 if (tokenizer.readIfEqual(Token.EQUALS)) { 1266 return new ExactKeyValue(regexSearch, key, tokenizer.readTextOrNumber()); 1267 } else if (tokenizer.readIfEqual(Token.LESS_THAN)) { 1268 return new ValueComparison(key, tokenizer.readTextOrNumber(), -1); 1269 } else if (tokenizer.readIfEqual(Token.GREATER_THAN)) { 1270 return new ValueComparison(key, tokenizer.readTextOrNumber(), +1); 1271 } else if (tokenizer.readIfEqual(Token.COLON)) { 1272 // see if we have a Match that takes a data parameter 1273 SimpleMatchFactory factory = simpleMatchFactoryMap.get(key); 1274 if (factory != null) 1275 return factory.get(key, tokenizer); 1276 1277 UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key); 1278 if (unaryFactory != null) 1279 return unaryFactory.get(key, parseFactor(), tokenizer); 1280 1281 // key:value form where value is a string (may be OSM key search) 1282 return parseKV(key, tokenizer.readTextOrNumber()); 1283 } else if (tokenizer.readIfEqual(Token.QUESTION_MARK)) 1284 return new BooleanMatch(key, false); 1285 else { 1286 SimpleMatchFactory factory = simpleMatchFactoryMap.get(key); 1287 if (factory != null) 1288 return factory.get(key, null); 1289 1290 UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key); 1291 if (unaryFactory != null) 1292 return unaryFactory.get(key, parseFactor(), null); 1293 1294 // match string in any key or value 1295 return new Any(key, regexSearch, caseSensitive); 1296 } 1297 } else 1298 return null; 1299 } 1300 1301 private Match parseFactor(String errorMessage) throws ParseError { 1302 Match fact = parseFactor(); 1303 if (fact == null) 1304 throw new ParseError(errorMessage); 1305 else 1306 return fact; 1307 } 1308 1309 private Match parseKV(String key, String value) throws ParseError { 1310 if (value == null) { 1311 value = ""; 1312 } 1313 if (key.equals("type")) 1314 return new ExactType(value); 1315 else if (key.equals("user")) 1316 return new UserMatch(value); 1317 else if (key.equals("role")) 1318 return new RoleMatch(value); 1319 else 1320 return new KeyValue(key, value, regexSearch, caseSensitive); 1321 } 1322 1323 private static int regexFlags(boolean caseSensitive) { 1324 int searchFlags = 0; 1325 1326 // Enables canonical Unicode equivalence so that e.g. the two 1327 // forms of "\u00e9gal" and "e\u0301gal" will match. 1328 // 1329 // It makes sense to match no matter how the character 1330 // happened to be constructed. 1331 searchFlags |= Pattern.CANON_EQ; 1332 1333 // Make "." match any character including newline (/s in Perl) 1334 searchFlags |= Pattern.DOTALL; 1335 1336 // CASE_INSENSITIVE by itself only matches US-ASCII case 1337 // insensitively, but the OSM data is in Unicode. With 1338 // UNICODE_CASE casefolding is made Unicode-aware. 1339 if (!caseSensitive) { 1340 searchFlags |= (Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE); 1341 } 1342 1343 return searchFlags; 1344 } 1345}