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

Last change on this file since 1925 was 1925, checked in by jttt, 15 years ago

Replaced Relation.members with Relation.getMembers()

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