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