source: josm/trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java@ 8377

Last change on this file since 8377 was 8250, checked in by simon04, 9 years ago

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