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

Last change on this file since 2567 was 2567, checked in by Gubaer, 14 years ago

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