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

Last change on this file since 3303 was 3303, checked in by stoecker, 14 years ago

catch all errors thrown from search (there are also out of array index and the like)
  • Property svn:eol-style set to native
File size: 25.9 KB
Line 
1// License: GPL. Copyright 2007 by Immanuel Scholz and others
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.util.regex.Matcher;
10import java.util.regex.Pattern;
11import java.util.regex.PatternSyntaxException;
12
13import org.openstreetmap.josm.Main;
14import org.openstreetmap.josm.actions.search.PushbackTokenizer.Range;
15import org.openstreetmap.josm.actions.search.PushbackTokenizer.Token;
16import org.openstreetmap.josm.data.osm.Node;
17import org.openstreetmap.josm.data.osm.OsmPrimitive;
18import org.openstreetmap.josm.data.osm.OsmUtils;
19import org.openstreetmap.josm.data.osm.Relation;
20import org.openstreetmap.josm.data.osm.RelationMember;
21import org.openstreetmap.josm.data.osm.Way;
22import org.openstreetmap.josm.tools.DateUtils;
23
24/**
25 Implements a google-like search.
26 <br>
27 Grammar:
28<pre>
29expression =
30 fact | expression
31 fact expression
32 fact
33
34fact =
35 ( expression )
36 -fact
37 term?
38 term=term
39 term:term
40 term
41 </pre>
42
43 @author Imi
44 */
45public class SearchCompiler {
46
47 private boolean caseSensitive = false;
48 private boolean regexSearch = false;
49 private static String rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}");
50 private PushbackTokenizer tokenizer;
51
52 public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) {
53 this.caseSensitive = caseSensitive;
54 this.regexSearch = regexSearch;
55 this.tokenizer = tokenizer;
56 }
57
58 abstract public static class Match {
59 abstract public boolean match(OsmPrimitive osm);
60 }
61
62 public static class Always extends Match {
63 public static Always INSTANCE = new Always();
64 @Override public boolean match(OsmPrimitive osm) {
65 return true;
66 }
67 }
68
69 public static class Never extends Match {
70 @Override
71 public boolean match(OsmPrimitive osm) {
72 return false;
73 }
74 }
75
76 private static class Not extends Match {
77 private final Match match;
78 public Not(Match match) {this.match = match;}
79 @Override public boolean match(OsmPrimitive osm) {
80 return !match.match(osm);
81 }
82 @Override public String toString() {return "!"+match;}
83 }
84
85 private static class BooleanMatch extends Match {
86 private final String key;
87 private final boolean defaultValue;
88
89 public BooleanMatch(String key, boolean defaultValue) {
90 this.key = key;
91 this.defaultValue = defaultValue;
92 }
93 @Override
94 public boolean match(OsmPrimitive osm) {
95 Boolean ret = OsmUtils.getOsmBoolean(osm.get(key));
96 if (ret == null)
97 return defaultValue;
98 else
99 return ret;
100 }
101 }
102
103 private static class And extends Match {
104 private Match lhs;
105 private Match rhs;
106 public And(Match lhs, Match rhs) {this.lhs = lhs; this.rhs = rhs;}
107 @Override public boolean match(OsmPrimitive osm) {
108 return lhs.match(osm) && rhs.match(osm);
109 }
110 @Override public String toString() {return lhs+" && "+rhs;}
111 }
112
113 private static class Or extends Match {
114 private Match lhs;
115 private Match rhs;
116 public Or(Match lhs, Match rhs) {this.lhs = lhs; this.rhs = rhs;}
117 @Override public boolean match(OsmPrimitive osm) {
118 return lhs.match(osm) || rhs.match(osm);
119 }
120 @Override public String toString() {return lhs+" || "+rhs;}
121 }
122
123 private static class Id extends Match {
124 private long id;
125 public Id(long id) {
126 this.id = id;
127 }
128 @Override public boolean match(OsmPrimitive osm) {
129 return id == 0?osm.isNew():osm.getUniqueId() == id;
130 }
131 @Override public String toString() {return "id="+id;}
132 }
133
134 private static class ChangesetId extends Match {
135 private long changesetid;
136 public ChangesetId(long changesetid) {this.changesetid = changesetid;}
137 @Override public boolean match(OsmPrimitive osm) {
138 return osm.getChangesetId() == changesetid;
139 }
140 @Override public String toString() {return "changeset="+changesetid;}
141 }
142
143 private static class Version extends Match {
144 private long version;
145 public Version(long version) {this.version = version;}
146 @Override public boolean match(OsmPrimitive osm) {
147 return osm.getVersion() == version;
148 }
149 @Override public String toString() {return "version="+version;}
150 }
151
152 private static class KeyValue extends Match {
153 private final String key;
154 private final Pattern keyPattern;
155 private final String value;
156 private final Pattern valuePattern;
157 private final boolean caseSensitive;
158
159 public KeyValue(String key, String value, boolean regexSearch, boolean caseSensitive) throws ParseError {
160 this.caseSensitive = caseSensitive;
161 if (regexSearch) {
162 int searchFlags = regexFlags(caseSensitive);
163
164 try {
165 this.keyPattern = Pattern.compile(key, searchFlags);
166 } catch (PatternSyntaxException e) {
167 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
168 } catch (Exception e) {
169 throw new ParseError(tr(rxErrorMsg, key, tr("<unknown>"), e.getMessage()));
170 }
171 try {
172 this.valuePattern = Pattern.compile(value, searchFlags);
173 } catch (PatternSyntaxException e) {
174 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
175 } catch (Exception e) {
176 throw new ParseError(tr(rxErrorMsg, value, tr("<unknown>"), e.getMessage()));
177 }
178 this.key = key;
179 this.value = value;
180
181 } else if (caseSensitive) {
182 this.key = key;
183 this.value = value;
184 this.keyPattern = null;
185 this.valuePattern = null;
186 } else {
187 this.key = key.toLowerCase();
188 this.value = value;
189 this.keyPattern = null;
190 this.valuePattern = null;
191 }
192 }
193
194 @Override public boolean match(OsmPrimitive osm) {
195
196 if (keyPattern != null) {
197 if (!osm.hasKeys())
198 return false;
199
200 /* The string search will just get a key like
201 * 'highway' and look that up as osm.get(key). But
202 * since we're doing a regex match we'll have to loop
203 * over all the keys to see if they match our regex,
204 * and only then try to match against the value
205 */
206
207 for (String k: osm.keySet()) {
208 String v = osm.get(k);
209
210 Matcher matcherKey = keyPattern.matcher(k);
211 boolean matchedKey = matcherKey.find();
212
213 if (matchedKey) {
214 Matcher matcherValue = valuePattern.matcher(v);
215 boolean matchedValue = matcherValue.find();
216
217 if (matchedValue)
218 return true;
219 }
220 }
221 } else {
222 String mv = null;
223
224 if (key.equals("timestamp")) {
225 mv = DateUtils.fromDate(osm.getTimestamp());
226 } else {
227 mv = osm.get(key);
228 }
229
230 if (mv == null)
231 return false;
232
233 String v1 = caseSensitive ? mv : mv.toLowerCase();
234 String v2 = caseSensitive ? value : value.toLowerCase();
235
236 // is not Java 1.5
237 //v1 = java.text.Normalizer.normalize(v1, java.text.Normalizer.Form.NFC);
238 //v2 = java.text.Normalizer.normalize(v2, java.text.Normalizer.Form.NFC);
239 return v1.indexOf(v2) != -1;
240 }
241
242 return false;
243 }
244 @Override public String toString() {return key+"="+value;}
245 }
246
247 public static class ExactKeyValue extends Match {
248
249 private enum Mode {
250 ANY, ANY_KEY, ANY_VALUE, EXACT, NONE, MISSING_KEY,
251 ANY_KEY_REGEXP, ANY_VALUE_REGEXP, EXACT_REGEXP, MISSING_KEY_REGEXP;
252 }
253
254 private final String key;
255 private final String value;
256 private final Pattern keyPattern;
257 private final Pattern valuePattern;
258 private final Mode mode;
259
260 public ExactKeyValue(boolean regexp, String key, String value) throws ParseError {
261 if (key == "")
262 throw new ParseError(tr("Key cannot be empty when tag operator is used. Sample use: key=value"));
263 this.key = key;
264 this.value = value == null?"":value;
265 if ("".equals(this.value) && "*".equals(key)) {
266 mode = Mode.NONE;
267 } else if ("".equals(this.value)) {
268 if (regexp) {
269 mode = Mode.MISSING_KEY_REGEXP;
270 } else {
271 mode = Mode.MISSING_KEY;
272 }
273 } else if ("*".equals(key) && "*".equals(this.value)) {
274 mode = Mode.ANY;
275 } else if ("*".equals(key)) {
276 if (regexp) {
277 mode = Mode.ANY_KEY_REGEXP;
278 } else {
279 mode = Mode.ANY_KEY;
280 }
281 } else if ("*".equals(this.value)) {
282 if (regexp) {
283 mode = Mode.ANY_VALUE_REGEXP;
284 } else {
285 mode = Mode.ANY_VALUE;
286 }
287 } else {
288 if (regexp) {
289 mode = Mode.EXACT_REGEXP;
290 } else {
291 mode = Mode.EXACT;
292 }
293 }
294
295 if (regexp && key.length() > 0 && !key.equals("*")) {
296 keyPattern = Pattern.compile(key);
297 } else {
298 keyPattern = null;
299 }
300 if (regexp && this.value.length() > 0 && !this.value.equals("*")) {
301 try {
302 valuePattern = Pattern.compile(this.value);
303 } catch (PatternSyntaxException e) {
304 throw new ParseError(tr("Pattern Syntax Error: Pattern {0} in {1} is illegal!", e.getPattern(), value));
305 }
306 } else {
307 valuePattern = null;
308 }
309 }
310
311 @Override
312 public boolean match(OsmPrimitive osm) {
313
314 if (!osm.hasKeys())
315 return mode == Mode.NONE;
316
317 switch (mode) {
318 case NONE:
319 return false;
320 case MISSING_KEY:
321 return osm.get(key) == null;
322 case ANY:
323 return true;
324 case ANY_VALUE:
325 return osm.get(key) != null;
326 case ANY_KEY:
327 for (String v:osm.getKeys().values()) {
328 if (v.equals(value))
329 return true;
330 }
331 return false;
332 case EXACT:
333 return value.equals(osm.get(key));
334 case ANY_KEY_REGEXP:
335 for (String v:osm.getKeys().values()) {
336 if (valuePattern.matcher(v).matches())
337 return true;
338 }
339 return false;
340 case ANY_VALUE_REGEXP:
341 case EXACT_REGEXP:
342 for (String key: osm.keySet()) {
343 if (keyPattern.matcher(key).matches()) {
344 if (mode == Mode.ANY_VALUE_REGEXP
345 || valuePattern.matcher(osm.get(key)).matches())
346 return true;
347 }
348 }
349 return false;
350 case MISSING_KEY_REGEXP:
351 for (String k:osm.keySet()) {
352 if (keyPattern.matcher(k).matches())
353 return false;
354 }
355 return true;
356 }
357 throw new AssertionError("Missed state");
358 }
359
360 @Override
361 public String toString() {
362 return key + '=' + value;
363 }
364
365 }
366
367 private static class Any extends Match {
368 private final String search;
369 private final Pattern searchRegex;
370 private final boolean caseSensitive;
371
372 public Any(String s, boolean regexSearch, boolean caseSensitive) throws ParseError {
373 this.caseSensitive = caseSensitive;
374 if (regexSearch) {
375 try {
376 this.searchRegex = Pattern.compile(s, regexFlags(caseSensitive));
377 } catch (PatternSyntaxException e) {
378 throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
379 } catch (Exception e) {
380 throw new ParseError(tr(rxErrorMsg, s, tr("<unknown>"), e.getMessage()));
381 }
382 this.search = s;
383 } else if (caseSensitive) {
384 this.search = s;
385 this.searchRegex = null;
386 } else {
387 this.search = s.toLowerCase();
388 this.searchRegex = null;
389 }
390 }
391
392 @Override public boolean match(OsmPrimitive osm) {
393 if (!osm.hasKeys())
394 return search.equals("");
395
396 // is not Java 1.5
397 //search = java.text.Normalizer.normalize(search, java.text.Normalizer.Form.NFC);
398 for (String key: osm.keySet()) {
399 String value = osm.get(key);
400 if (searchRegex != null) {
401
402 // is not Java 1.5
403 //value = java.text.Normalizer.normalize(value, java.text.Normalizer.Form.NFC);
404
405 Matcher keyMatcher = searchRegex.matcher(key);
406 Matcher valMatcher = searchRegex.matcher(value);
407
408 boolean keyMatchFound = keyMatcher.find();
409 boolean valMatchFound = valMatcher.find();
410
411 if (keyMatchFound || valMatchFound)
412 return true;
413 } else {
414 if (!caseSensitive) {
415 key = key.toLowerCase();
416 value = value.toLowerCase();
417 }
418
419 // is not Java 1.5
420 //value = java.text.Normalizer.normalize(value, java.text.Normalizer.Form.NFC);
421
422 if (key.indexOf(search) != -1 || value.indexOf(search) != -1)
423 return true;
424 }
425 }
426 if (osm.getUser() != null) {
427 String name = osm.getUser().getName();
428 // is not Java 1.5
429 //String name = java.text.Normalizer.normalize(name, java.text.Normalizer.Form.NFC);
430 if (!caseSensitive) {
431 name = name.toLowerCase();
432 }
433 if (name.indexOf(search) != -1)
434 return true;
435 }
436 return false;
437 }
438 @Override public String toString() {
439 return search;
440 }
441 }
442
443 private static class ExactType extends Match {
444 private final Class<?> type;
445 public ExactType(String type) throws ParseError {
446 if ("node".equals(type)) {
447 this.type = Node.class;
448 } else if ("way".equals(type)) {
449 this.type = Way.class;
450 } else if ("relation".equals(type)) {
451 this.type = Relation.class;
452 } else
453 throw new ParseError(tr("Unknown primitive type: {0}. Allowed values are node, way or relation",
454 type));
455 }
456 @Override public boolean match(OsmPrimitive osm) {
457 return osm.getClass() == type;
458 }
459 @Override public String toString() {return "type="+type;}
460 }
461
462 private static class UserMatch extends Match {
463 private String user;
464 public UserMatch(String user) {
465 if (user.equals("anonymous")) {
466 this.user = null;
467 } else {
468 this.user = user;
469 }
470 }
471
472 @Override public boolean match(OsmPrimitive osm) {
473 if (osm.getUser() == null)
474 return user == null;
475 else
476 return osm.getUser().hasName(user);
477 }
478
479 @Override public String toString() {
480 return "user=" + user == null ? "" : user;
481 }
482 }
483
484 private static class NodeCountRange extends Match {
485 private int minCount;
486 private int maxCount;
487 public NodeCountRange(int minCount, int maxCount) {
488 if(maxCount < minCount) {
489 this.minCount = maxCount;
490 this.maxCount = minCount;
491 } else {
492 this.minCount = minCount;
493 this.maxCount = maxCount;
494 }
495 }
496 @Override public boolean match(OsmPrimitive osm) {
497 if(!(osm instanceof Way)) return false;
498 int size = ((Way)osm).getNodesCount();
499 return (size >= minCount) && (size <= maxCount);
500 }
501 @Override public String toString() {return "nodes="+minCount+"-"+maxCount;}
502 }
503
504 private static class TagCountRange extends Match {
505 private int minCount;
506 private int maxCount;
507 public TagCountRange(int minCount, int maxCount) {
508 if(maxCount < minCount) {
509 this.minCount = maxCount;
510 this.maxCount = minCount;
511 } else {
512 this.minCount = minCount;
513 this.maxCount = maxCount;
514 }
515 }
516 @Override public boolean match(OsmPrimitive osm) {
517 int size = osm.getKeys().size();
518 return (size >= minCount) && (size <= maxCount);
519 }
520 @Override public String toString() {return "tags="+minCount+"-"+maxCount;}
521 }
522
523 private static class Modified extends Match {
524 @Override public boolean match(OsmPrimitive osm) {
525 return osm.isModified() || osm.isNew();
526 }
527 @Override public String toString() {return "modified";}
528 }
529
530 private static class Selected extends Match {
531 @Override public boolean match(OsmPrimitive osm) {
532 return Main.main.getCurrentDataSet().isSelected(osm);
533 }
534 @Override public String toString() {return "selected";}
535 }
536
537 private static class Incomplete extends Match {
538 @Override public boolean match(OsmPrimitive osm) {
539 return osm.isIncomplete();
540 }
541 @Override public String toString() {return "incomplete";}
542 }
543
544 private static class Untagged extends Match {
545 @Override public boolean match(OsmPrimitive osm) {
546 return !osm.isTagged();
547 }
548 @Override public String toString() {return "untagged";}
549 }
550
551 private static class Parent extends Match {
552 private Match child;
553 public Parent(Match m) { child = m; }
554 @Override public boolean match(OsmPrimitive osm) {
555 boolean isParent = false;
556
557 // "parent" (null) should mean the same as "parent()"
558 // (Always). I.e. match everything
559 if (child == null) {
560 child = new Always();
561 }
562
563 if (osm instanceof Way) {
564 for (Node n : ((Way)osm).getNodes()) {
565 isParent |= child.match(n);
566 }
567 } else if (osm instanceof Relation) {
568 for (RelationMember member : ((Relation)osm).getMembers()) {
569 isParent |= child.match(member.getMember());
570 }
571 }
572 return isParent;
573 }
574 @Override public String toString() {return "parent(" + child + ")";}
575 }
576
577 private static class Child extends Match {
578 private final Match parent;
579
580 public Child(Match m) {
581 // "child" (null) should mean the same as "child()"
582 // (Always). I.e. match everything
583 if (m == null) {
584 parent = new Always();
585 } else {
586 parent = m;
587 }
588 }
589
590 @Override public boolean match(OsmPrimitive osm) {
591 boolean isChild = false;
592 for (OsmPrimitive p : osm.getReferrers()) {
593 isChild |= parent.match(p);
594 }
595 return isChild;
596 }
597 @Override public String toString() {return "child(" + parent + ")";}
598 }
599
600 public static class ParseError extends Exception {
601 public ParseError(String msg) {
602 super(msg);
603 }
604 public ParseError(Token expected, Token found) {
605 this(tr("Unexpected token. Expected {0}, found {1}", expected, found));
606 }
607 }
608
609 public static Match compile(String searchStr, boolean caseSensitive, boolean regexSearch)
610 throws ParseError {
611 return new SearchCompiler(caseSensitive, regexSearch,
612 new PushbackTokenizer(
613 new PushbackReader(new StringReader(searchStr))))
614 .parse();
615 }
616
617 public Match parse() throws ParseError {
618 Match m = parseExpression();
619 if (!tokenizer.readIfEqual(Token.EOF))
620 throw new ParseError(tr("Unexpected token: {0}", tokenizer.nextToken()));
621 if (m == null)
622 return new Always();
623 return m;
624 }
625
626 private Match parseExpression() throws ParseError {
627 Match factor = parseFactor();
628 if (factor == null)
629 return null;
630 if (tokenizer.readIfEqual(Token.OR))
631 return new Or(factor, parseExpression(tr("Missing parameter for OR")));
632 else {
633 Match expression = parseExpression();
634 if (expression == null)
635 return factor;
636 else
637 return new And(factor, expression);
638 }
639 }
640
641 private Match parseExpression(String errorMessage) throws ParseError {
642 Match expression = parseExpression();
643 if (expression == null)
644 throw new ParseError(errorMessage);
645 else
646 return expression;
647 }
648
649 private Match parseFactor() throws ParseError {
650 if (tokenizer.readIfEqual(Token.LEFT_PARENT)) {
651 Match expression = parseExpression();
652 if (!tokenizer.readIfEqual(Token.RIGHT_PARENT))
653 throw new ParseError(Token.RIGHT_PARENT, tokenizer.nextToken());
654 return expression;
655 } else if (tokenizer.readIfEqual(Token.NOT))
656 return new Not(parseFactor(tr("Missing operator for NOT")));
657 else if (tokenizer.readIfEqual(Token.KEY)) {
658 String key = tokenizer.getText();
659 if (tokenizer.readIfEqual(Token.EQUALS))
660 return new ExactKeyValue(regexSearch, key, tokenizer.readTextOrNumber());
661 else if (tokenizer.readIfEqual(Token.COLON)) {
662 if ("id".equals(key))
663 return new Id(tokenizer.readNumber(tr("Primitive id expected")));
664 else if ("tags".equals(key)) {
665 Range range = tokenizer.readRange(tr("Range of numbers expected"));
666 return new TagCountRange((int)range.getStart(), (int)range.getEnd());
667 } else if ("nodes".equals(key)) {
668 Range range = tokenizer.readRange(tr("Range of numbers expected"));
669 return new NodeCountRange((int)range.getStart(), (int)range.getEnd());
670 } else if ("changeset".equals(key))
671 return new ChangesetId(tokenizer.readNumber(tr("Changeset id expected")));
672 else if ("version".equals(key))
673 return new Version(tokenizer.readNumber(tr("Version expected")));
674 else
675 return parseKV(key, tokenizer.readTextOrNumber());
676 } else if (tokenizer.readIfEqual(Token.QUESTION_MARK))
677 return new BooleanMatch(key, false);
678 else if ("modified".equals(key))
679 return new Modified();
680 else if ("incomplete".equals(key))
681 return new Incomplete();
682 else if ("untagged".equals(key))
683 return new Untagged();
684 else if ("selected".equals(key))
685 return new Selected();
686 else if ("child".equals(key))
687 return new Child(parseFactor());
688 else if ("parent".equals(key))
689 return new Parent(parseFactor());
690 else
691 return new Any(key, regexSearch, caseSensitive);
692 } else
693 return null;
694 }
695
696 private Match parseFactor(String errorMessage) throws ParseError {
697 Match fact = parseFactor();
698 if (fact == null)
699 throw new ParseError(errorMessage);
700 else
701 return fact;
702 }
703
704 private Match parseKV(String key, String value) throws ParseError {
705 if (value == null) {
706 value = "";
707 }
708 if (key.equals("type"))
709 return new ExactType(value);
710 else if (key.equals("user"))
711 return new UserMatch(value);
712 else
713 return new KeyValue(key, value, regexSearch, caseSensitive);
714 }
715
716 private static int regexFlags(boolean caseSensitive) {
717 int searchFlags = 0;
718
719 // Enables canonical Unicode equivalence so that e.g. the two
720 // forms of "\u00e9gal" and "e\u0301gal" will match.
721 //
722 // It makes sense to match no matter how the character
723 // happened to be constructed.
724 searchFlags |= Pattern.CANON_EQ;
725
726 // Make "." match any character including newline (/s in Perl)
727 searchFlags |= Pattern.DOTALL;
728
729 // CASE_INSENSITIVE by itself only matches US-ASCII case
730 // insensitively, but the OSM data is in Unicode. With
731 // UNICODE_CASE casefolding is made Unicode-aware.
732 if (!caseSensitive) {
733 searchFlags |= (Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE);
734 }
735
736 return searchFlags;
737 }
738}
Note: See TracBrowser for help on using the repository browser.