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