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