001    // License: GPL. Copyright 2007 by Immanuel Scholz and others
002    package org.openstreetmap.josm.actions.search;
003    
004    import static org.openstreetmap.josm.tools.I18n.marktr;
005    import static org.openstreetmap.josm.tools.I18n.tr;
006    
007    import java.io.PushbackReader;
008    import java.io.StringReader;
009    import java.text.Normalizer;
010    import java.util.Arrays;
011    import java.util.Collection;
012    import java.util.Date;
013    import java.util.HashMap;
014    import java.util.Map;
015    import java.util.regex.Matcher;
016    import java.util.regex.Pattern;
017    import java.util.regex.PatternSyntaxException;
018    
019    import org.openstreetmap.josm.Main;
020    import org.openstreetmap.josm.actions.search.PushbackTokenizer.Range;
021    import org.openstreetmap.josm.actions.search.PushbackTokenizer.Token;
022    import org.openstreetmap.josm.data.Bounds;
023    import org.openstreetmap.josm.data.osm.Node;
024    import org.openstreetmap.josm.data.osm.OsmPrimitive;
025    import org.openstreetmap.josm.data.osm.OsmUtils;
026    import org.openstreetmap.josm.data.osm.Relation;
027    import org.openstreetmap.josm.data.osm.RelationMember;
028    import org.openstreetmap.josm.data.osm.Way;
029    import org.openstreetmap.josm.tools.DateUtils;
030    import org.openstreetmap.josm.tools.Geometry;
031    
032    /**
033     Implements a google-like search.
034     <br>
035     Grammar:
036    <pre>
037    expression =
038      fact | expression
039      fact expression
040      fact
041    
042    fact =
043     ( expression )
044     -fact
045     term?
046     term=term
047     term:term
048     term
049     </pre>
050    
051     @author Imi
052     */
053    public class SearchCompiler {
054    
055        private boolean caseSensitive = false;
056        private boolean regexSearch = false;
057        private static String  rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}");
058        private static String  rxErrorMsgNoPos = marktr("The regex \"{0}\" had a parse error, full error:\n\n{1}");
059        private PushbackTokenizer tokenizer;
060        private static Map<String, SimpleMatchFactory> simpleMatchFactoryMap = new HashMap<String, SimpleMatchFactory>();
061        private static Map<String, UnaryMatchFactory> unaryMatchFactoryMap = new HashMap<String, UnaryMatchFactory>();
062        private static Map<String, BinaryMatchFactory> binaryMatchFactoryMap = new HashMap<String, BinaryMatchFactory>();
063    
064        public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) {
065            this.caseSensitive = caseSensitive;
066            this.regexSearch = regexSearch;
067            this.tokenizer = tokenizer;
068    
069            /* register core match factories at first instance, so plugins should
070             * never be able to generate a NPE
071             */
072            if (simpleMatchFactoryMap.isEmpty()) {
073                addMatchFactory(new CoreSimpleMatchFactory());
074            }
075            if (unaryMatchFactoryMap.isEmpty()) {
076                addMatchFactory(new CoreUnaryMatchFactory());
077            }
078    
079        }
080    
081        /**
082         * Add (register) MatchFactory with SearchCompiler
083         * @param factory
084         */
085        public static void addMatchFactory(MatchFactory factory) {
086            for (String keyword : factory.getKeywords()) {
087                // TODO: check for keyword collisions
088                if (factory instanceof SimpleMatchFactory) {
089                    simpleMatchFactoryMap.put(keyword, (SimpleMatchFactory)factory);
090                } else if (factory instanceof UnaryMatchFactory) {
091                    unaryMatchFactoryMap.put(keyword, (UnaryMatchFactory)factory);
092                } else if (factory instanceof BinaryMatchFactory) {
093                    binaryMatchFactoryMap.put(keyword, (BinaryMatchFactory)factory);
094                } else
095                    throw new AssertionError("Unknown match factory");
096            }
097        }
098    
099        public class CoreSimpleMatchFactory implements SimpleMatchFactory {
100            private Collection<String> keywords = Arrays.asList("id", "version",
101                    "changeset", "nodes", "tags", "areasize", "modified", "selected",
102                    "incomplete", "untagged", "closed", "new", "indownloadarea",
103                    "allindownloadarea", "inview", "allinview", "timestamp");
104    
105            @Override
106            public Match get(String keyword, PushbackTokenizer tokenizer) throws ParseError {
107                if ("modified".equals(keyword))
108                    return new Modified();
109                else if ("selected".equals(keyword))
110                    return new Selected();
111                else if ("incomplete".equals(keyword))
112                    return new Incomplete();
113                else if ("untagged".equals(keyword))
114                    return new Untagged();
115                else if ("closed".equals(keyword))
116                    return new Closed();
117                else if ("new".equals(keyword))
118                    return new New();
119                else if ("indownloadedarea".equals(keyword))
120                    return new InDataSourceArea(false);
121                else if ("allindownloadedarea".equals(keyword))
122                    return new InDataSourceArea(true);
123                else if ("inview".equals(keyword))
124                    return new InView(false);
125                else if ("allinview".equals(keyword))
126                    return new InView(true);
127                else if (tokenizer != null) {
128                    if ("id".equals(keyword))
129                        return new Id(tokenizer);
130                    else if ("version".equals(keyword))
131                        return new Version(tokenizer);
132                    else if ("changeset".equals(keyword))
133                        return new ChangesetId(tokenizer);
134                    else if ("nodes".equals(keyword))
135                        return new NodeCountRange(tokenizer);
136                    else if ("tags".equals(keyword))
137                        return new TagCountRange(tokenizer);
138                    else if ("areasize".equals(keyword))
139                        return new AreaSize(tokenizer);
140                    else if ("timestamp".equals(keyword)) {
141                        String rangeS = " " + tokenizer.readTextOrNumber() + " "; // add leading/trailing space in order to get expected split (e.g. "a--" => {"a", ""})
142                        String[] rangeA = rangeS.split("/");
143                        if (rangeA.length == 1)
144                            return new KeyValue(keyword, rangeS.trim(), regexSearch, caseSensitive);
145                        else if (rangeA.length == 2) {
146                            String rangeA1 = rangeA[0].trim();
147                            String rangeA2 = rangeA[1].trim();
148                            long minDate = DateUtils.fromString(rangeA1.isEmpty() ? "1980" : rangeA1).getTime(); // if min timestap is empty: use lowest possible date
149                            long maxDate = rangeA2.isEmpty() ? new Date().getTime() : DateUtils.fromString(rangeA2).getTime(); // if max timestamp is empty: use "now"
150                            return new TimestampRange(minDate, maxDate);
151                        } else
152                            /*
153                             * I18n: Don't translate timestamp keyword
154                             */ throw new ParseError(tr("Expecting <i>min</i>/<i>max</i> after ''timestamp''"));
155                    }
156                }
157                return null;
158            }
159    
160            @Override
161            public Collection<String> getKeywords() {
162                return keywords;
163            }
164        }
165    
166        public static class CoreUnaryMatchFactory implements UnaryMatchFactory {
167            private static Collection<String> keywords = Arrays.asList("parent", "child");
168    
169            @Override
170            public UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) {
171                if ("parent".equals(keyword))
172                    return new Parent(matchOperand);
173                else if ("child".equals(keyword))
174                    return new Child(matchOperand);
175                return null;
176            }
177    
178            @Override
179            public Collection<String> getKeywords() {
180                return keywords;
181            }
182        }
183    
184        /**
185         * Classes implementing this interface can provide Match operators.
186         */
187        private interface MatchFactory {
188            public Collection<String> getKeywords();
189        }
190    
191        public interface SimpleMatchFactory extends MatchFactory {
192            public Match get(String keyword, PushbackTokenizer tokenizer) throws ParseError;
193        }
194    
195        public interface UnaryMatchFactory extends MatchFactory {
196            public UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) throws ParseError;
197        }
198    
199        public interface BinaryMatchFactory extends MatchFactory {
200            public BinaryMatch get(String keyword, Match lhs, Match rhs, PushbackTokenizer tokenizer) throws ParseError;
201        }
202    
203        /**
204         * Base class for all search operators.
205         */
206        abstract public static class Match {
207    
208            abstract public boolean match(OsmPrimitive osm);
209    
210            /**
211             * Tests whether one of the primitives matches.
212             */
213            protected boolean existsMatch(Collection<? extends OsmPrimitive> primitives) {
214                for (OsmPrimitive p : primitives) {
215                    if (match(p))
216                        return true;
217                }
218                return false;
219            }
220    
221            /**
222             * Tests whether all primitives match.
223             */
224            protected boolean forallMatch(Collection<? extends OsmPrimitive> primitives) {
225                for (OsmPrimitive p : primitives) {
226                    if (!match(p))
227                        return false;
228                }
229                return true;
230            }
231        }
232    
233        /**
234         * A unary search operator which may take data parameters.
235         */
236        abstract public static class UnaryMatch extends Match {
237    
238            protected final Match match;
239    
240            public UnaryMatch(Match match) {
241                if (match == null) {
242                    // "operator" (null) should mean the same as "operator()"
243                    // (Always). I.e. match everything
244                    this.match = new Always();
245                } else {
246                    this.match = match;
247                }
248            }
249    
250            public Match getOperand() {
251                return match;
252            }
253        }
254    
255        /**
256         * A binary search operator which may take data parameters.
257         */
258        abstract public static class BinaryMatch extends Match {
259    
260            protected final Match lhs;
261            protected final Match rhs;
262    
263            public BinaryMatch(Match lhs, Match rhs) {
264                this.lhs = lhs;
265                this.rhs = rhs;
266            }
267    
268            public Match getLhs() {
269                return lhs;
270            }
271    
272            public Match getRhs() {
273                return rhs;
274            }
275        }
276    
277        /**
278         * Matches every OsmPrimitive.
279         */
280        public static class Always extends Match {
281            public static Always INSTANCE = new Always();
282            @Override public boolean match(OsmPrimitive osm) {
283                return true;
284            }
285        }
286    
287        /**
288         * Never matches any OsmPrimitive.
289         */
290        public static class Never extends Match {
291            @Override
292            public boolean match(OsmPrimitive osm) {
293                return false;
294            }
295        }
296    
297        /**
298         * Inverts the match.
299         */
300        public static class Not extends UnaryMatch {
301            public Not(Match match) {super(match);}
302            @Override public boolean match(OsmPrimitive osm) {
303                return !match.match(osm);
304            }
305            @Override public String toString() {return "!"+match;}
306            public Match getMatch() {
307                return match;
308            }
309        }
310    
311        /**
312         * Matches if the value of the corresponding key is ''yes'', ''true'', ''1'' or ''on''.
313         */
314        private static class BooleanMatch extends Match {
315            private final String key;
316            private final boolean defaultValue;
317    
318            public BooleanMatch(String key, boolean defaultValue) {
319                this.key = key;
320                this.defaultValue = defaultValue;
321            }
322            @Override
323            public boolean match(OsmPrimitive osm) {
324                Boolean ret = OsmUtils.getOsmBoolean(osm.get(key));
325                if (ret == null)
326                    return defaultValue;
327                else
328                    return ret;
329            }
330        }
331    
332        /**
333         * Matches if both left and right expressions match.
334         */
335        public static class And extends BinaryMatch {
336        public And(Match lhs, Match rhs) {super(lhs, rhs);}
337            @Override public boolean match(OsmPrimitive osm) {
338                return lhs.match(osm) && rhs.match(osm);
339            }
340            @Override public String toString() {
341                return lhs + " && " + rhs;
342            }
343        }
344    
345        /**
346         * Matches if the left OR the right expression match.
347         */
348        public static class Or extends BinaryMatch {
349        public Or(Match lhs, Match rhs) {super(lhs, rhs);}
350            @Override public boolean match(OsmPrimitive osm) {
351                return lhs.match(osm) || rhs.match(osm);
352            }
353            @Override public String toString() {
354                return lhs + " || " + rhs;
355            }
356        }
357    
358        /**
359         * Matches if the left OR the right expression match, but not both.
360         */
361        public static class Xor extends BinaryMatch {
362        public Xor(Match lhs, Match rhs) {super(lhs, rhs);}
363            @Override public boolean match(OsmPrimitive osm) {
364                return lhs.match(osm) ^ rhs.match(osm);
365            }
366            @Override public String toString() {
367                return lhs + " ^ " + rhs;
368            }
369        }
370    
371        /**
372         * Matches objects with the given object ID.
373         */
374        private static class Id extends Match {
375            private long id;
376            public Id(long id) {
377                this.id = id;
378            }
379            public Id(PushbackTokenizer tokenizer) throws ParseError {
380                this(tokenizer.readNumber(tr("Primitive id expected")));
381            }
382            @Override public boolean match(OsmPrimitive osm) {
383                return id == 0?osm.isNew():osm.getUniqueId() == id;
384            }
385            @Override public String toString() {return "id="+id;}
386        }
387    
388        /**
389         * Matches objects with the given changeset ID.
390         */
391        private static class ChangesetId extends Match {
392            private long changesetid;
393            public ChangesetId(long changesetid) {this.changesetid = changesetid;}
394            public ChangesetId(PushbackTokenizer tokenizer) throws ParseError {
395                this(tokenizer.readNumber(tr("Changeset id expected")));
396            }
397            @Override public boolean match(OsmPrimitive osm) {
398                return osm.getChangesetId() == changesetid;
399            }
400            @Override public String toString() {return "changeset="+changesetid;}
401        }
402    
403        /**
404         * Matches objects with the given version number.
405         */
406        private static class Version extends Match {
407            private long version;
408            public Version(long version) {this.version = version;}
409            public Version(PushbackTokenizer tokenizer) throws ParseError {
410                this(tokenizer.readNumber(tr("Version expected")));
411            }
412            @Override public boolean match(OsmPrimitive osm) {
413                return osm.getVersion() == version;
414            }
415            @Override public String toString() {return "version="+version;}
416        }
417    
418        /**
419         * Matches objects with the given key-value pair.
420         */
421        private static class KeyValue extends Match {
422            private final String key;
423            private final Pattern keyPattern;
424            private final String value;
425            private final Pattern valuePattern;
426            private final boolean caseSensitive;
427    
428            public KeyValue(String key, String value, boolean regexSearch, boolean caseSensitive) throws ParseError {
429                this.caseSensitive = caseSensitive;
430                if (regexSearch) {
431                    int searchFlags = regexFlags(caseSensitive);
432    
433                    try {
434                        this.keyPattern = Pattern.compile(key, searchFlags);
435                    } catch (PatternSyntaxException e) {
436                        throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
437                    } catch (Exception e) {
438                        throw new ParseError(tr(rxErrorMsgNoPos, key, e.getMessage()));
439                    }
440                    try {
441                        this.valuePattern = Pattern.compile(value, searchFlags);
442                    } catch (PatternSyntaxException e) {
443                        throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
444                    } catch (Exception e) {
445                        throw new ParseError(tr(rxErrorMsgNoPos, value, e.getMessage()));
446                    }
447                    this.key = key;
448                    this.value = value;
449    
450                } else if (caseSensitive) {
451                    this.key = key;
452                    this.value = value;
453                    this.keyPattern = null;
454                    this.valuePattern = null;
455                } else {
456                    this.key = key.toLowerCase();
457                    this.value = value;
458                    this.keyPattern = null;
459                    this.valuePattern = null;
460                }
461            }
462    
463            @Override public boolean match(OsmPrimitive osm) {
464    
465                if (keyPattern != null) {
466                    if (!osm.hasKeys())
467                        return false;
468    
469                    /* The string search will just get a key like
470                     * 'highway' and look that up as osm.get(key). But
471                     * since we're doing a regex match we'll have to loop
472                     * over all the keys to see if they match our regex,
473                     * and only then try to match against the value
474                     */
475    
476                    for (String k: osm.keySet()) {
477                        String v = osm.get(k);
478    
479                        Matcher matcherKey = keyPattern.matcher(k);
480                        boolean matchedKey = matcherKey.find();
481    
482                        if (matchedKey) {
483                            Matcher matcherValue = valuePattern.matcher(v);
484                            boolean matchedValue = matcherValue.find();
485    
486                            if (matchedValue)
487                                return true;
488                        }
489                    }
490                } else {
491                    String mv = null;
492    
493                    if (key.equals("timestamp")) {
494                        mv = DateUtils.fromDate(osm.getTimestamp());
495                    } else {
496                        mv = osm.get(key);
497                    }
498    
499                    if (mv == null)
500                        return false;
501    
502                    String v1 = caseSensitive ? mv : mv.toLowerCase();
503                    String v2 = caseSensitive ? value : value.toLowerCase();
504    
505                    v1 = Normalizer.normalize(v1, Normalizer.Form.NFC);
506                    v2 = Normalizer.normalize(v2, Normalizer.Form.NFC);
507                    return v1.indexOf(v2) != -1;
508                }
509    
510                return false;
511            }
512            @Override public String toString() {return key+"="+value;}
513        }
514    
515        /**
516         * Matches objects with the exact given key-value pair.
517         */
518        public static class ExactKeyValue extends Match {
519    
520            private enum Mode {
521                ANY, ANY_KEY, ANY_VALUE, EXACT, NONE, MISSING_KEY,
522                ANY_KEY_REGEXP, ANY_VALUE_REGEXP, EXACT_REGEXP, MISSING_KEY_REGEXP;
523            }
524    
525            private final String key;
526            private final String value;
527            private final Pattern keyPattern;
528            private final Pattern valuePattern;
529            private final Mode mode;
530    
531            public ExactKeyValue(boolean regexp, String key, String value) throws ParseError {
532                if ("".equals(key))
533                    throw new ParseError(tr("Key cannot be empty when tag operator is used. Sample use: key=value"));
534                this.key = key;
535                this.value = value == null?"":value;
536                if ("".equals(this.value) && "*".equals(key)) {
537                    mode = Mode.NONE;
538                } else if ("".equals(this.value)) {
539                    if (regexp) {
540                        mode = Mode.MISSING_KEY_REGEXP;
541                    } else {
542                        mode = Mode.MISSING_KEY;
543                    }
544                } else if ("*".equals(key) && "*".equals(this.value)) {
545                    mode = Mode.ANY;
546                } else if ("*".equals(key)) {
547                    if (regexp) {
548                        mode = Mode.ANY_KEY_REGEXP;
549                    } else {
550                        mode = Mode.ANY_KEY;
551                    }
552                } else if ("*".equals(this.value)) {
553                    if (regexp) {
554                        mode = Mode.ANY_VALUE_REGEXP;
555                    } else {
556                        mode = Mode.ANY_VALUE;
557                    }
558                } else {
559                    if (regexp) {
560                        mode = Mode.EXACT_REGEXP;
561                    } else {
562                        mode = Mode.EXACT;
563                    }
564                }
565    
566                if (regexp && key.length() > 0 && !key.equals("*")) {
567                    try {
568                        keyPattern = Pattern.compile(key, regexFlags(false));
569                    } catch (PatternSyntaxException e) {
570                        throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
571                    } catch (Exception e) {
572                        throw new ParseError(tr(rxErrorMsgNoPos, key, e.getMessage()));
573                    }
574                } else {
575                    keyPattern = null;
576                }
577                if (regexp && this.value.length() > 0 && !this.value.equals("*")) {
578                    try {
579                        valuePattern = Pattern.compile(this.value, regexFlags(false));
580                    } catch (PatternSyntaxException e) {
581                        throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
582                    } catch (Exception e) {
583                        throw new ParseError(tr(rxErrorMsgNoPos, value, e.getMessage()));
584                    }
585                } else {
586                    valuePattern = null;
587                }
588            }
589    
590            @Override
591            public boolean match(OsmPrimitive osm) {
592    
593                if (!osm.hasKeys())
594                    return mode == Mode.NONE;
595    
596                switch (mode) {
597                case NONE:
598                    return false;
599                case MISSING_KEY:
600                    return osm.get(key) == null;
601                case ANY:
602                    return true;
603                case ANY_VALUE:
604                    return osm.get(key) != null;
605                case ANY_KEY:
606                    for (String v:osm.getKeys().values()) {
607                        if (v.equals(value))
608                            return true;
609                    }
610                    return false;
611                case EXACT:
612                    return value.equals(osm.get(key));
613                case ANY_KEY_REGEXP:
614                    for (String v:osm.getKeys().values()) {
615                        if (valuePattern.matcher(v).matches())
616                            return true;
617                    }
618                    return false;
619                case ANY_VALUE_REGEXP:
620                case EXACT_REGEXP:
621                    for (String key: osm.keySet()) {
622                        if (keyPattern.matcher(key).matches()) {
623                            if (mode == Mode.ANY_VALUE_REGEXP
624                                    || valuePattern.matcher(osm.get(key)).matches())
625                                return true;
626                        }
627                    }
628                    return false;
629                case MISSING_KEY_REGEXP:
630                    for (String k:osm.keySet()) {
631                        if (keyPattern.matcher(k).matches())
632                            return false;
633                    }
634                    return true;
635                }
636                throw new AssertionError("Missed state");
637            }
638    
639            @Override
640            public String toString() {
641                return key + '=' + value;
642            }
643    
644        }
645    
646        /**
647         * Match a string in any tags (key or value), with optional regex and case insensitivity.
648         */
649        private static class Any extends Match {
650            private final String search;
651            private final Pattern searchRegex;
652            private final boolean caseSensitive;
653    
654            public Any(String s, boolean regexSearch, boolean caseSensitive) throws ParseError {
655                s = Normalizer.normalize(s, Normalizer.Form.NFC);
656                this.caseSensitive = caseSensitive;
657                if (regexSearch) {
658                    try {
659                        this.searchRegex = Pattern.compile(s, regexFlags(caseSensitive));
660                    } catch (PatternSyntaxException e) {
661                        throw new ParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()));
662                    } catch (Exception e) {
663                        throw new ParseError(tr(rxErrorMsgNoPos, s, e.getMessage()));
664                    }
665                    this.search = s;
666                } else if (caseSensitive) {
667                    this.search = s;
668                    this.searchRegex = null;
669                } else {
670                    this.search = s.toLowerCase();
671                    this.searchRegex = null;
672                }
673            }
674    
675            @Override public boolean match(OsmPrimitive osm) {
676                if (!osm.hasKeys() && osm.getUser() == null)
677                    return search.equals("");
678    
679                for (String key: osm.keySet()) {
680                    String value = osm.get(key);
681                    if (searchRegex != null) {
682    
683                        value = Normalizer.normalize(value, Normalizer.Form.NFC);
684    
685                        Matcher keyMatcher = searchRegex.matcher(key);
686                        Matcher valMatcher = searchRegex.matcher(value);
687    
688                        boolean keyMatchFound = keyMatcher.find();
689                        boolean valMatchFound = valMatcher.find();
690    
691                        if (keyMatchFound || valMatchFound)
692                            return true;
693                    } else {
694                        if (!caseSensitive) {
695                            key = key.toLowerCase();
696                            value = value.toLowerCase();
697                        }
698    
699                        value = Normalizer.normalize(value, Normalizer.Form.NFC);
700    
701                        if (key.indexOf(search) != -1 || value.indexOf(search) != -1)
702                            return true;
703                    }
704                }
705                return false;
706            }
707            @Override public String toString() {
708                return search;
709            }
710        }
711    
712        // TODO: change how we handle this
713        private static class ExactType extends Match {
714            private final Class<?> type;
715            public ExactType(String type) throws ParseError {
716                if ("node".equals(type)) {
717                    this.type = Node.class;
718                } else if ("way".equals(type)) {
719                    this.type = Way.class;
720                } else if ("relation".equals(type)) {
721                    this.type = Relation.class;
722                } else
723                    throw new ParseError(tr("Unknown primitive type: {0}. Allowed values are node, way or relation",
724                            type));
725            }
726            @Override public boolean match(OsmPrimitive osm) {
727                return osm.getClass() == type;
728            }
729            @Override public String toString() {return "type="+type;}
730        }
731    
732        /**
733         * Matches objects last changed by the given username.
734         */
735        private static class UserMatch extends Match {
736            private String user;
737            public UserMatch(String user) {
738                if (user.equals("anonymous")) {
739                    this.user = null;
740                } else {
741                    this.user = user;
742                }
743            }
744    
745            @Override public boolean match(OsmPrimitive osm) {
746                if (osm.getUser() == null)
747                    return user == null;
748                else
749                    return osm.getUser().hasName(user);
750            }
751    
752            @Override public String toString() {
753                return "user=" + user == null ? "" : user;
754            }
755        }
756    
757        /**
758         * Matches objects with the given relation role (i.e. "outer").
759         */
760        private static class RoleMatch extends Match {
761            private String role;
762            public RoleMatch(String role) {
763                if (role == null) {
764                    this.role = "";
765                } else {
766                    this.role = role;
767                }
768            }
769    
770            @Override public boolean match(OsmPrimitive osm) {
771                for (OsmPrimitive ref: osm.getReferrers()) {
772                    if (ref instanceof Relation && !ref.isIncomplete() && !ref.isDeleted()) {
773                        for (RelationMember m : ((Relation) ref).getMembers()) {
774                            if (m.getMember() == osm) {
775                                String testRole = m.getRole();
776                                if(role.equals(testRole == null ? "" : testRole))
777                                    return true;
778                            }
779                        }
780                    }
781                }
782                return false;
783            }
784    
785            @Override public String toString() {
786                return "role=" + role;
787            }
788        }
789    
790        /**
791         * Matches objects with properties in a certain range.
792         */
793        private abstract static class CountRange extends Match {
794    
795            private long minCount;
796            private long maxCount;
797    
798            public CountRange(long minCount, long maxCount) {
799                this.minCount = Math.min(minCount, maxCount);
800                this.maxCount = Math.max(minCount, maxCount);
801            }
802    
803            public CountRange(Range range) {
804                this(range.getStart(), range.getEnd());
805            }
806    
807            protected abstract Long getCount(OsmPrimitive osm);
808    
809            protected abstract String getCountString();
810    
811            @Override
812            public boolean match(OsmPrimitive osm) {
813                Long count = getCount(osm);
814                if (count == null)
815                    return false;
816                else
817                    return (count >= minCount) && (count <= maxCount);
818            }
819    
820            @Override
821            public String toString() {
822                return getCountString() + "=" + minCount + "-" + maxCount;
823            }
824        }
825    
826    
827        /**
828         * Matches ways with a number of nodes in given range
829         */
830        private static class NodeCountRange extends CountRange {
831            public NodeCountRange(Range range) {
832                super(range);
833            }
834    
835            public NodeCountRange(PushbackTokenizer tokenizer) throws ParseError {
836                this(tokenizer.readRange(tr("Range of numbers expected")));
837            }
838    
839            @Override
840            protected Long getCount(OsmPrimitive osm) {
841                if (!(osm instanceof Way))
842                    return null;
843                else
844                    return (long) ((Way) osm).getNodesCount();
845            }
846    
847            @Override
848            protected String getCountString() {
849                return "nodes";
850            }
851        }
852    
853        /**
854         * Matches objects with a number of tags in given range
855         */
856        private static class TagCountRange extends CountRange {
857            public TagCountRange(Range range) {
858                super(range);
859            }
860    
861            public TagCountRange(PushbackTokenizer tokenizer) throws ParseError {
862                this(tokenizer.readRange(tr("Range of numbers expected")));
863            }
864    
865            @Override
866            protected Long getCount(OsmPrimitive osm) {
867                return (long) osm.getKeys().size();
868            }
869    
870            @Override
871            protected String getCountString() {
872                return "tags";
873            }
874        }
875    
876        /**
877         * Matches objects with a timestamp in given range
878         */
879        private static class TimestampRange extends CountRange {
880    
881            public TimestampRange(long minCount, long maxCount) {
882                super(minCount, maxCount);
883            }
884    
885            @Override
886            protected Long getCount(OsmPrimitive osm) {
887                return osm.getTimestamp().getTime();
888            }
889    
890            @Override
891            protected String getCountString() {
892                return "timestamp";
893            }
894    
895        }
896    
897        /**
898         * Matches objects that are new (i.e. have not been uploaded to the server)
899         */
900        private static class New extends Match {
901            @Override public boolean match(OsmPrimitive osm) {
902                return osm.isNew();
903            }
904            @Override public String toString() {
905                return "new";
906            }
907        }
908    
909        /**
910         * Matches all objects that have been modified, created, or undeleted
911         */
912        private static class Modified extends Match {
913            @Override public boolean match(OsmPrimitive osm) {
914                return osm.isModified() || osm.isNewOrUndeleted();
915            }
916            @Override public String toString() {return "modified";}
917        }
918    
919        /**
920         * Matches all objects currently selected
921         */
922        private static class Selected extends Match {
923            @Override public boolean match(OsmPrimitive osm) {
924                return Main.main.getCurrentDataSet().isSelected(osm);
925            }
926            @Override public String toString() {return "selected";}
927        }
928    
929        /**
930         * Match objects that are incomplete, where only id and type are known.
931         * Typically some members of a relation are incomplete until they are
932         * fetched from the server.
933         */
934        private static class Incomplete extends Match {
935            @Override public boolean match(OsmPrimitive osm) {
936                return osm.isIncomplete();
937            }
938            @Override public String toString() {return "incomplete";}
939        }
940    
941        /**
942         * Matches objects that don't have any interesting tags (i.e. only has source,
943         * FIXME, etc.). The complete list of uninteresting tags can be found here:
944         * org.openstreetmap.josm.data.osm.OsmPrimitive.getUninterestingKeys()
945         */
946        private static class Untagged extends Match {
947            @Override public boolean match(OsmPrimitive osm) {
948                return !osm.isTagged() && !osm.isIncomplete();
949            }
950            @Override public String toString() {return "untagged";}
951        }
952    
953        /**
954         * Matches ways which are closed (i.e. first and last node are the same)
955         */
956        private static class Closed extends Match {
957            @Override public boolean match(OsmPrimitive osm) {
958                return osm instanceof Way && ((Way) osm).isClosed();
959            }
960            @Override public String toString() {return "closed";}
961        }
962    
963        /**
964         * Matches objects if they are parents of the expression
965         */
966        public static class Parent extends UnaryMatch {
967            public Parent(Match m) {
968                super(m);
969            }
970            @Override public boolean match(OsmPrimitive osm) {
971                boolean isParent = false;
972    
973                if (osm instanceof Way) {
974                    for (Node n : ((Way)osm).getNodes()) {
975                        isParent |= match.match(n);
976                    }
977                } else if (osm instanceof Relation) {
978                    for (RelationMember member : ((Relation)osm).getMembers()) {
979                        isParent |= match.match(member.getMember());
980                    }
981                }
982                return isParent;
983            }
984            @Override public String toString() {return "parent(" + match + ")";}
985        }
986    
987        /**
988         * Matches objects if they are children of the expression
989         */
990        public static class Child extends UnaryMatch {
991    
992            public Child(Match m) {
993                super(m);
994            }
995    
996            @Override public boolean match(OsmPrimitive osm) {
997                boolean isChild = false;
998                for (OsmPrimitive p : osm.getReferrers()) {
999                    isChild |= match.match(p);
1000                }
1001                return isChild;
1002            }
1003            @Override public String toString() {return "child(" + match + ")";}
1004        }
1005    
1006        /**
1007         * Matches if the size of the area is within the given range
1008         *
1009         * @author Ole J??rgen Br??nner
1010         */
1011        private static class AreaSize extends CountRange {
1012    
1013            public AreaSize(Range range) {
1014                super(range);
1015            }
1016    
1017            public AreaSize(PushbackTokenizer tokenizer) throws ParseError {
1018                this(tokenizer.readRange(tr("Range of numbers expected")));
1019            }
1020    
1021            @Override
1022            protected Long getCount(OsmPrimitive osm) {
1023                if (!(osm instanceof Way && ((Way) osm).isClosed()))
1024                    return null;
1025                Way way = (Way) osm;
1026                return (long) Geometry.closedWayArea(way);
1027            }
1028    
1029            @Override
1030            protected String getCountString() {
1031                return "areasize";
1032            }
1033        }
1034    
1035        /**
1036         * Matches objects within the given bounds.
1037         */
1038        private abstract static class InArea extends Match {
1039    
1040            protected abstract Bounds getBounds();
1041            protected final boolean all;
1042            protected final Bounds bounds;
1043    
1044            /**
1045             * @param all if true, all way nodes or relation members have to be within source area;if false, one suffices.
1046             */
1047            public InArea(boolean all) {
1048                this.all = all;
1049                this.bounds = getBounds();
1050            }
1051    
1052            @Override
1053            public boolean match(OsmPrimitive osm) {
1054                if (!osm.isUsable())
1055                    return false;
1056                else if (osm instanceof Node)
1057                    return bounds.contains(((Node) osm).getCoor());
1058                else if (osm instanceof Way) {
1059                    Collection<Node> nodes = ((Way) osm).getNodes();
1060                    return all ? forallMatch(nodes) : existsMatch(nodes);
1061                } else if (osm instanceof Relation) {
1062                    Collection<OsmPrimitive> primitives = ((Relation) osm).getMemberPrimitives();
1063                    return all ? forallMatch(primitives) : existsMatch(primitives);
1064                } else
1065                    return false;
1066            }
1067        }
1068    
1069        /**
1070         * Matches objects within source area ("downloaded area").
1071         */
1072        private static class InDataSourceArea extends InArea {
1073    
1074            public InDataSourceArea(boolean all) {
1075                super(all);
1076            }
1077    
1078            @Override
1079            protected Bounds getBounds() {
1080                return new Bounds(Main.main.getCurrentDataSet().getDataSourceArea().getBounds2D());
1081            }
1082        }
1083    
1084        /**
1085         * Matches objects within current map view.
1086         */
1087        private static class InView extends InArea {
1088    
1089            public InView(boolean all) {
1090                super(all);
1091            }
1092    
1093            @Override
1094            protected Bounds getBounds() {
1095                return Main.map.mapView.getRealBounds();
1096            }
1097        }
1098    
1099        public static class ParseError extends Exception {
1100            public ParseError(String msg) {
1101                super(msg);
1102            }
1103            public ParseError(Token expected, Token found) {
1104                this(tr("Unexpected token. Expected {0}, found {1}", expected, found));
1105            }
1106        }
1107    
1108        public static Match compile(String searchStr, boolean caseSensitive, boolean regexSearch)
1109                throws ParseError {
1110            return new SearchCompiler(caseSensitive, regexSearch,
1111                    new PushbackTokenizer(
1112                            new PushbackReader(new StringReader(searchStr))))
1113            .parse();
1114        }
1115    
1116        /**
1117         * Parse search string.
1118         *
1119         * @return match determined by search string
1120         * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError
1121         */
1122        public Match parse() throws ParseError {
1123            Match m = parseExpression();
1124            if (!tokenizer.readIfEqual(Token.EOF))
1125                throw new ParseError(tr("Unexpected token: {0}", tokenizer.nextToken()));
1126            if (m == null)
1127                return new Always();
1128            return m;
1129        }
1130    
1131        /**
1132         * Parse expression. This is a recursive method.
1133         *
1134         * @return match determined by parsing expression
1135         * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError
1136         */
1137        private Match parseExpression() throws ParseError {
1138            Match factor = parseFactor();
1139            if (factor == null)
1140                // empty search string
1141                return null;
1142            if (tokenizer.readIfEqual(Token.OR))
1143                return new Or(factor, parseExpression(tr("Missing parameter for OR")));
1144            else if (tokenizer.readIfEqual(Token.XOR))
1145                return new Xor(factor, parseExpression(tr("Missing parameter for XOR")));
1146            else {
1147                Match expression = parseExpression();
1148                if (expression == null)
1149                    // reached end of search string, no more recursive calls
1150                    return factor;
1151                else
1152                    // the default operator is AND
1153                    return new And(factor, expression);
1154            }
1155        }
1156    
1157        /**
1158         * Parse expression, showing the specified error message if parsing fails.
1159         *
1160         * @param errorMessage to display if parsing error occurs
1161         * @return
1162         * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError
1163         */
1164        private Match parseExpression(String errorMessage) throws ParseError {
1165            Match expression = parseExpression();
1166            if (expression == null)
1167                throw new ParseError(errorMessage);
1168            else
1169                return expression;
1170        }
1171    
1172        /**
1173         * Parse next factor (a search operator or search term).
1174         *
1175         * @return match determined by parsing factor string
1176         * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError
1177         */
1178        private Match parseFactor() throws ParseError {
1179            if (tokenizer.readIfEqual(Token.LEFT_PARENT)) {
1180                Match expression = parseExpression();
1181                if (!tokenizer.readIfEqual(Token.RIGHT_PARENT))
1182                    throw new ParseError(Token.RIGHT_PARENT, tokenizer.nextToken());
1183                return expression;
1184            } else if (tokenizer.readIfEqual(Token.NOT)) {
1185                return new Not(parseFactor(tr("Missing operator for NOT")));
1186            } else if (tokenizer.readIfEqual(Token.KEY)) {
1187                // factor consists of key:value or key=value
1188                String key = tokenizer.getText();
1189                if (tokenizer.readIfEqual(Token.EQUALS))
1190                    return new ExactKeyValue(regexSearch, key, tokenizer.readTextOrNumber());
1191                else if (tokenizer.readIfEqual(Token.COLON)) {
1192                    // see if we have a Match that takes a data parameter
1193                    SimpleMatchFactory factory = simpleMatchFactoryMap.get(key);
1194                    if (factory != null)
1195                        return factory.get(key, tokenizer);
1196    
1197                    UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key);
1198                    if (unaryFactory != null)
1199                        return unaryFactory.get(key, parseFactor(), tokenizer);
1200    
1201                    // key:value form where value is a string (may be OSM key search)
1202                    return parseKV(key, tokenizer.readTextOrNumber());
1203                } else if (tokenizer.readIfEqual(Token.QUESTION_MARK))
1204                    return new BooleanMatch(key, false);
1205                else {
1206                    SimpleMatchFactory factory = simpleMatchFactoryMap.get(key);
1207                    if (factory != null)
1208                        return factory.get(key, null);
1209    
1210                    UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key);
1211                    if (unaryFactory != null)
1212                        return unaryFactory.get(key, parseFactor(), null);
1213    
1214                    // match string in any key or value
1215                    return new Any(key, regexSearch, caseSensitive);
1216                }
1217            } else
1218                return null;
1219        }
1220    
1221        private Match parseFactor(String errorMessage) throws ParseError {
1222            Match fact = parseFactor();
1223            if (fact == null)
1224                throw new ParseError(errorMessage);
1225            else
1226                return fact;
1227        }
1228    
1229        private Match parseKV(String key, String value) throws ParseError {
1230            if (value == null) {
1231                value = "";
1232            }
1233            if (key.equals("type"))
1234                return new ExactType(value);
1235            else if (key.equals("user"))
1236                return new UserMatch(value);
1237            else if (key.equals("role"))
1238                return new RoleMatch(value);
1239            else
1240                return new KeyValue(key, value, regexSearch, caseSensitive);
1241        }
1242    
1243        private static int regexFlags(boolean caseSensitive) {
1244            int searchFlags = 0;
1245    
1246            // Enables canonical Unicode equivalence so that e.g. the two
1247            // forms of "\u00e9gal" and "e\u0301gal" will match.
1248            //
1249            // It makes sense to match no matter how the character
1250            // happened to be constructed.
1251            searchFlags |= Pattern.CANON_EQ;
1252    
1253            // Make "." match any character including newline (/s in Perl)
1254            searchFlags |= Pattern.DOTALL;
1255    
1256            // CASE_INSENSITIVE by itself only matches US-ASCII case
1257            // insensitively, but the OSM data is in Unicode. With
1258            // UNICODE_CASE casefolding is made Unicode-aware.
1259            if (!caseSensitive) {
1260                searchFlags |= (Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE);
1261            }
1262    
1263            return searchFlags;
1264        }
1265    }