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

Last change on this file since 2264 was 2264, checked in by stoecker, 15 years ago

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