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