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

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

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