001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm.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.ArrayList;
011import java.util.Arrays;
012import java.util.Collection;
013import java.util.Collections;
014import java.util.HashMap;
015import java.util.List;
016import java.util.Locale;
017import java.util.Map;
018import java.util.Optional;
019import java.util.function.Predicate;
020import java.util.regex.Matcher;
021import java.util.regex.Pattern;
022import java.util.regex.PatternSyntaxException;
023import java.util.stream.Collectors;
024
025import org.openstreetmap.josm.data.Bounds;
026import org.openstreetmap.josm.data.coor.LatLon;
027import org.openstreetmap.josm.data.osm.Node;
028import org.openstreetmap.josm.data.osm.OsmPrimitive;
029import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
030import org.openstreetmap.josm.data.osm.OsmUtils;
031import org.openstreetmap.josm.data.osm.Relation;
032import org.openstreetmap.josm.data.osm.RelationMember;
033import org.openstreetmap.josm.data.osm.Tagged;
034import org.openstreetmap.josm.data.osm.Way;
035import org.openstreetmap.josm.data.osm.search.PushbackTokenizer.Range;
036import org.openstreetmap.josm.data.osm.search.PushbackTokenizer.Token;
037import org.openstreetmap.josm.data.projection.ProjectionRegistry;
038import org.openstreetmap.josm.gui.mappaint.Environment;
039import org.openstreetmap.josm.gui.mappaint.mapcss.Selector;
040import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.MapCSSParser;
041import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.ParseException;
042import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset;
043import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetMenu;
044import org.openstreetmap.josm.gui.tagging.presets.TaggingPresetSeparator;
045import org.openstreetmap.josm.gui.tagging.presets.TaggingPresets;
046import org.openstreetmap.josm.tools.AlphanumComparator;
047import org.openstreetmap.josm.tools.Geometry;
048import org.openstreetmap.josm.tools.Logging;
049import org.openstreetmap.josm.tools.UncheckedParseException;
050import org.openstreetmap.josm.tools.date.DateUtils;
051
052/**
053 * Implements a google-like search.
054 * <br>
055 * Grammar:
056 * <pre>
057 * expression =
058 *   fact | expression
059 *   fact expression
060 *   fact
061 *
062 * fact =
063 *  ( expression )
064 *  -fact
065 *  term?
066 *  term=term
067 *  term:term
068 *  term
069 *  </pre>
070 *
071 * @author Imi
072 * @since 12656 (moved from actions.search package)
073 */
074public class SearchCompiler {
075
076    private final boolean caseSensitive;
077    private final boolean regexSearch;
078    private static String rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}");
079    private static String rxErrorMsgNoPos = marktr("The regex \"{0}\" had a parse error, full error:\n\n{1}");
080    private final PushbackTokenizer tokenizer;
081    private static Map<String, SimpleMatchFactory> simpleMatchFactoryMap = new HashMap<>();
082    private static Map<String, UnaryMatchFactory> unaryMatchFactoryMap = new HashMap<>();
083    private static Map<String, BinaryMatchFactory> binaryMatchFactoryMap = new HashMap<>();
084
085    static {
086        addMatchFactory(new CoreSimpleMatchFactory());
087        addMatchFactory(new CoreUnaryMatchFactory());
088    }
089
090    /**
091     * Constructs a new {@code SearchCompiler}.
092     * @param caseSensitive {@code true} to perform a case-sensitive search
093     * @param regexSearch {@code true} to perform a regex-based search
094     * @param tokenizer to split the search string into tokens
095     */
096    public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) {
097        this.caseSensitive = caseSensitive;
098        this.regexSearch = regexSearch;
099        this.tokenizer = tokenizer;
100    }
101
102    /**
103     * Add (register) MatchFactory with SearchCompiler
104     * @param factory match factory
105     */
106    public static void addMatchFactory(MatchFactory factory) {
107        for (String keyword : factory.getKeywords()) {
108            final MatchFactory existing;
109            if (factory instanceof SimpleMatchFactory) {
110                existing = simpleMatchFactoryMap.put(keyword, (SimpleMatchFactory) factory);
111            } else if (factory instanceof UnaryMatchFactory) {
112                existing = unaryMatchFactoryMap.put(keyword, (UnaryMatchFactory) factory);
113            } else if (factory instanceof BinaryMatchFactory) {
114                existing = binaryMatchFactoryMap.put(keyword, (BinaryMatchFactory) factory);
115            } else
116                throw new AssertionError("Unknown match factory");
117            if (existing != null) {
118                Logging.warn("SearchCompiler: for key ''{0}'', overriding match factory ''{1}'' with ''{2}''", keyword, existing, factory);
119            }
120        }
121    }
122
123    public static class CoreSimpleMatchFactory implements SimpleMatchFactory {
124        private final Collection<String> keywords = Arrays.asList("id", "version", "type", "user", "role",
125                "changeset", "nodes", "ways", "tags", "areasize", "waylength", "modified", "deleted", "selected",
126                "incomplete", "untagged", "closed", "new", "indownloadedarea",
127                "allindownloadedarea", "timestamp", "nth", "nth%", "hasRole", "preset");
128
129        @Override
130        public Match get(String keyword, boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) throws SearchParseError {
131            switch(keyword) {
132            case "modified":
133                return new Modified();
134            case "deleted":
135                return new Deleted();
136            case "selected":
137                return new Selected();
138            case "incomplete":
139                return new Incomplete();
140            case "untagged":
141                return new Untagged();
142            case "closed":
143                return new Closed();
144            case "new":
145                return new New();
146            case "indownloadedarea":
147                return new InDataSourceArea(false);
148            case "allindownloadedarea":
149                return new InDataSourceArea(true);
150            default:
151                if (tokenizer != null) {
152                    switch (keyword) {
153                    case "id":
154                        return new Id(tokenizer);
155                    case "version":
156                        return new Version(tokenizer);
157                    case "type":
158                        return new ExactType(tokenizer.readTextOrNumber());
159                    case "preset":
160                        return new Preset(tokenizer.readTextOrNumber());
161                    case "user":
162                        return new UserMatch(tokenizer.readTextOrNumber());
163                    case "role":
164                        return new RoleMatch(tokenizer.readTextOrNumber());
165                    case "changeset":
166                        return new ChangesetId(tokenizer);
167                    case "nodes":
168                        return new NodeCountRange(tokenizer);
169                    case "ways":
170                        return new WayCountRange(tokenizer);
171                    case "tags":
172                        return new TagCountRange(tokenizer);
173                    case "areasize":
174                        return new AreaSize(tokenizer);
175                    case "waylength":
176                        return new WayLength(tokenizer);
177                    case "nth":
178                        return new Nth(tokenizer, false);
179                    case "nth%":
180                        return new Nth(tokenizer, true);
181                    case "hasRole":
182                        return new HasRole(tokenizer);
183                    case "timestamp":
184                        // add leading/trailing space in order to get expected split (e.g. "a--" => {"a", ""})
185                        String rangeS = ' ' + tokenizer.readTextOrNumber() + ' ';
186                        String[] rangeA = rangeS.split("/");
187                        if (rangeA.length == 1) {
188                            return new KeyValue(keyword, rangeS.trim(), regexSearch, caseSensitive);
189                        } else if (rangeA.length == 2) {
190                            String rangeA1 = rangeA[0].trim();
191                            String rangeA2 = rangeA[1].trim();
192                            final long minDate;
193                            final long maxDate;
194                            try {
195                                // if min timestap is empty: use lowest possible date
196                                minDate = DateUtils.fromString(rangeA1.isEmpty() ? "1980" : rangeA1).getTime();
197                            } catch (UncheckedParseException ex) {
198                                throw new SearchParseError(tr("Cannot parse timestamp ''{0}''", rangeA1), ex);
199                            }
200                            try {
201                                // if max timestamp is empty: use "now"
202                                maxDate = rangeA2.isEmpty() ? System.currentTimeMillis() : DateUtils.fromString(rangeA2).getTime();
203                            } catch (UncheckedParseException ex) {
204                                throw new SearchParseError(tr("Cannot parse timestamp ''{0}''", rangeA2), ex);
205                            }
206                            return new TimestampRange(minDate, maxDate);
207                        } else {
208                            throw new SearchParseError("<html>" + tr("Expecting {0} after {1}", "<i>min</i>/<i>max</i>", "<i>timestamp</i>")
209                                + "</html>");
210                        }
211                    }
212                } else {
213                    throw new SearchParseError("<html>" + tr("Expecting {0} after {1}", "<code>:</code>", "<i>" + keyword + "</i>") + "</html>");
214                }
215            }
216            throw new IllegalStateException("Not expecting keyword " + keyword);
217        }
218
219        @Override
220        public Collection<String> getKeywords() {
221            return keywords;
222        }
223    }
224
225    public static class CoreUnaryMatchFactory implements UnaryMatchFactory {
226        private static Collection<String> keywords = Arrays.asList("parent", "child");
227
228        @Override
229        public UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) {
230            if ("parent".equals(keyword))
231                return new Parent(matchOperand);
232            else if ("child".equals(keyword))
233                return new Child(matchOperand);
234            return null;
235        }
236
237        @Override
238        public Collection<String> getKeywords() {
239            return keywords;
240        }
241    }
242
243    /**
244     * Classes implementing this interface can provide Match operators.
245     * @since 10600 (functional interface)
246     */
247    @FunctionalInterface
248    private interface MatchFactory {
249        Collection<String> getKeywords();
250    }
251
252    public interface SimpleMatchFactory extends MatchFactory {
253        Match get(String keyword, boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) throws SearchParseError;
254    }
255
256    public interface UnaryMatchFactory extends MatchFactory {
257        UnaryMatch get(String keyword, Match matchOperand, PushbackTokenizer tokenizer) throws SearchParseError;
258    }
259
260    public interface BinaryMatchFactory extends MatchFactory {
261        AbstractBinaryMatch get(String keyword, Match lhs, Match rhs, PushbackTokenizer tokenizer) throws SearchParseError;
262    }
263
264    /**
265     * Base class for all search criteria. If the criterion only depends on an object's tags,
266     * inherit from {@link org.openstreetmap.josm.data.osm.search.SearchCompiler.TaggedMatch}.
267     */
268    public abstract static class Match implements Predicate<OsmPrimitive> {
269
270        /**
271         * Tests whether the primitive matches this criterion.
272         * @param osm the primitive to test
273         * @return true if the primitive matches this criterion
274         */
275        public abstract boolean match(OsmPrimitive osm);
276
277        /**
278         * Tests whether the tagged object matches this criterion.
279         * @param tagged the tagged object to test
280         * @return true if the tagged object matches this criterion
281         */
282        public boolean match(Tagged tagged) {
283            return tagged instanceof OsmPrimitive && match((OsmPrimitive) tagged);
284        }
285
286        @Override
287        public final boolean test(OsmPrimitive object) {
288            return match(object);
289        }
290    }
291
292    public abstract static class TaggedMatch extends Match {
293
294        @Override
295        public abstract boolean match(Tagged tags);
296
297        @Override
298        public final boolean match(OsmPrimitive osm) {
299            return match((Tagged) osm);
300        }
301
302        protected static Pattern compilePattern(String regex, int flags) throws SearchParseError {
303            try {
304                return Pattern.compile(regex, flags);
305            } catch (PatternSyntaxException e) {
306                throw new SearchParseError(tr(rxErrorMsg, e.getPattern(), e.getIndex(), e.getMessage()), e);
307            } catch (IllegalArgumentException | StringIndexOutOfBoundsException e) {
308                // StringIndexOutOfBoundsException catched because of https://bugs.openjdk.java.net/browse/JI-9044959
309                // See #13870: To remove after we switch to a version of Java which resolves this bug
310                throw new SearchParseError(tr(rxErrorMsgNoPos, regex, e.getMessage()), e);
311            }
312        }
313    }
314
315    /**
316     * A unary search operator which may take data parameters.
317     */
318    public abstract static class UnaryMatch extends Match {
319
320        protected final Match match;
321
322        public UnaryMatch(Match match) {
323            if (match == null) {
324                // "operator" (null) should mean the same as "operator()"
325                // (Always). I.e. match everything
326                this.match = Always.INSTANCE;
327            } else {
328                this.match = match;
329            }
330        }
331
332        public Match getOperand() {
333            return match;
334        }
335
336        @Override
337        public int hashCode() {
338            return 31 + ((match == null) ? 0 : match.hashCode());
339        }
340
341        @Override
342        public boolean equals(Object obj) {
343            if (this == obj)
344                return true;
345            if (obj == null || getClass() != obj.getClass())
346                return false;
347            UnaryMatch other = (UnaryMatch) obj;
348            if (match == null) {
349                if (other.match != null)
350                    return false;
351            } else if (!match.equals(other.match))
352                return false;
353            return true;
354        }
355    }
356
357    /**
358     * A binary search operator which may take data parameters.
359     */
360    public abstract static class AbstractBinaryMatch extends Match {
361
362        protected final Match lhs;
363        protected final Match rhs;
364
365        /**
366         * Constructs a new {@code BinaryMatch}.
367         * @param lhs Left hand side
368         * @param rhs Right hand side
369         */
370        public AbstractBinaryMatch(Match lhs, Match rhs) {
371            this.lhs = lhs;
372            this.rhs = rhs;
373        }
374
375        /**
376         * Returns left hand side.
377         * @return left hand side
378         */
379        public final Match getLhs() {
380            return lhs;
381        }
382
383        /**
384         * Returns right hand side.
385         * @return right hand side
386         */
387        public final Match getRhs() {
388            return rhs;
389        }
390
391        protected static String parenthesis(Match m) {
392            return '(' + m.toString() + ')';
393        }
394
395        @Override
396        public int hashCode() {
397            final int prime = 31;
398            int result = 1;
399            result = prime * result + ((lhs == null) ? 0 : lhs.hashCode());
400            result = prime * result + ((rhs == null) ? 0 : rhs.hashCode());
401            return result;
402        }
403
404        @Override
405        public boolean equals(Object obj) {
406            if (this == obj)
407                return true;
408            if (obj == null || getClass() != obj.getClass())
409                return false;
410            AbstractBinaryMatch other = (AbstractBinaryMatch) obj;
411            if (lhs == null) {
412                if (other.lhs != null)
413                    return false;
414            } else if (!lhs.equals(other.lhs))
415                return false;
416            if (rhs == null) {
417                if (other.rhs != null)
418                    return false;
419            } else if (!rhs.equals(other.rhs))
420                return false;
421            return true;
422        }
423    }
424
425    /**
426     * Matches every OsmPrimitive.
427     */
428    public static class Always extends TaggedMatch {
429        /** The unique instance/ */
430        public static final Always INSTANCE = new Always();
431        @Override
432        public boolean match(Tagged osm) {
433            return true;
434        }
435    }
436
437    /**
438     * Never matches any OsmPrimitive.
439     */
440    public static class Never extends TaggedMatch {
441        /** The unique instance/ */
442        public static final Never INSTANCE = new Never();
443        @Override
444        public boolean match(Tagged osm) {
445            return false;
446        }
447    }
448
449    /**
450     * Inverts the match.
451     */
452    public static class Not extends UnaryMatch {
453        public Not(Match match) {
454            super(match);
455        }
456
457        @Override
458        public boolean match(OsmPrimitive osm) {
459            return !match.match(osm);
460        }
461
462        @Override
463        public boolean match(Tagged osm) {
464            return !match.match(osm);
465        }
466
467        @Override
468        public String toString() {
469            return '!' + match.toString();
470        }
471
472        public Match getMatch() {
473            return match;
474        }
475    }
476
477    /**
478     * Matches if the value of the corresponding key is ''yes'', ''true'', ''1'' or ''on''.
479     */
480    private static class BooleanMatch extends TaggedMatch {
481        private final String key;
482        private final boolean defaultValue;
483
484        BooleanMatch(String key, boolean defaultValue) {
485            this.key = key;
486            this.defaultValue = defaultValue;
487        }
488
489        @Override
490        public boolean match(Tagged osm) {
491            return Optional.ofNullable(OsmUtils.getOsmBoolean(osm.get(key))).orElse(defaultValue);
492        }
493
494        @Override
495        public String toString() {
496            return key + '?';
497        }
498
499        @Override
500        public int hashCode() {
501            final int prime = 31;
502            int result = 1;
503            result = prime * result + (defaultValue ? 1231 : 1237);
504            result = prime * result + ((key == null) ? 0 : key.hashCode());
505            return result;
506        }
507
508        @Override
509        public boolean equals(Object obj) {
510            if (this == obj)
511                return true;
512            if (obj == null || getClass() != obj.getClass())
513                return false;
514            BooleanMatch other = (BooleanMatch) obj;
515            if (defaultValue != other.defaultValue)
516                return false;
517            if (key == null) {
518                if (other.key != null)
519                    return false;
520            } else if (!key.equals(other.key))
521                return false;
522            return true;
523        }
524    }
525
526    /**
527     * Matches if both left and right expressions match.
528     */
529    public static class And extends AbstractBinaryMatch {
530        /**
531         * Constructs a new {@code And} match.
532         * @param lhs left hand side
533         * @param rhs right hand side
534         */
535        public And(Match lhs, Match rhs) {
536            super(lhs, rhs);
537        }
538
539        @Override
540        public boolean match(OsmPrimitive osm) {
541            return lhs.match(osm) && rhs.match(osm);
542        }
543
544        @Override
545        public boolean match(Tagged osm) {
546            return lhs.match(osm) && rhs.match(osm);
547        }
548
549        @Override
550        public String toString() {
551            return (lhs instanceof AbstractBinaryMatch && !(lhs instanceof And) ? parenthesis(lhs) : lhs) + " && "
552                 + (rhs instanceof AbstractBinaryMatch && !(rhs instanceof And) ? parenthesis(rhs) : rhs);
553        }
554    }
555
556    /**
557     * Matches if the left OR the right expression match.
558     */
559    public static class Or extends AbstractBinaryMatch {
560        /**
561         * Constructs a new {@code Or} match.
562         * @param lhs left hand side
563         * @param rhs right hand side
564         */
565        public Or(Match lhs, Match rhs) {
566            super(lhs, rhs);
567        }
568
569        @Override
570        public boolean match(OsmPrimitive osm) {
571            return lhs.match(osm) || rhs.match(osm);
572        }
573
574        @Override
575        public boolean match(Tagged osm) {
576            return lhs.match(osm) || rhs.match(osm);
577        }
578
579        @Override
580        public String toString() {
581            return (lhs instanceof AbstractBinaryMatch && !(lhs instanceof Or) ? parenthesis(lhs) : lhs) + " || "
582                 + (rhs instanceof AbstractBinaryMatch && !(rhs instanceof Or) ? parenthesis(rhs) : rhs);
583        }
584    }
585
586    /**
587     * Matches if the left OR the right expression match, but not both.
588     */
589    public static class Xor extends AbstractBinaryMatch {
590        /**
591         * Constructs a new {@code Xor} match.
592         * @param lhs left hand side
593         * @param rhs right hand side
594         */
595        public Xor(Match lhs, Match rhs) {
596            super(lhs, rhs);
597        }
598
599        @Override
600        public boolean match(OsmPrimitive osm) {
601            return lhs.match(osm) ^ rhs.match(osm);
602        }
603
604        @Override
605        public boolean match(Tagged osm) {
606            return lhs.match(osm) ^ rhs.match(osm);
607        }
608
609        @Override
610        public String toString() {
611            return (lhs instanceof AbstractBinaryMatch && !(lhs instanceof Xor) ? parenthesis(lhs) : lhs) + " ^ "
612                 + (rhs instanceof AbstractBinaryMatch && !(rhs instanceof Xor) ? parenthesis(rhs) : rhs);
613        }
614    }
615
616    /**
617     * Matches objects with ID in the given range.
618     */
619    private static class Id extends RangeMatch {
620        Id(Range range) {
621            super(range);
622        }
623
624        Id(PushbackTokenizer tokenizer) throws SearchParseError {
625            this(tokenizer.readRange(tr("Range of primitive ids expected")));
626        }
627
628        @Override
629        protected Long getNumber(OsmPrimitive osm) {
630            return osm.isNew() ? 0 : osm.getUniqueId();
631        }
632
633        @Override
634        protected String getString() {
635            return "id";
636        }
637    }
638
639    /**
640     * Matches objects with a changeset ID in the given range.
641     */
642    private static class ChangesetId extends RangeMatch {
643        ChangesetId(Range range) {
644            super(range);
645        }
646
647        ChangesetId(PushbackTokenizer tokenizer) throws SearchParseError {
648            this(tokenizer.readRange(tr("Range of changeset ids expected")));
649        }
650
651        @Override
652        protected Long getNumber(OsmPrimitive osm) {
653            return (long) osm.getChangesetId();
654        }
655
656        @Override
657        protected String getString() {
658            return "changeset";
659        }
660    }
661
662    /**
663     * Matches objects with a version number in the given range.
664     */
665    private static class Version extends RangeMatch {
666        Version(Range range) {
667            super(range);
668        }
669
670        Version(PushbackTokenizer tokenizer) throws SearchParseError {
671            this(tokenizer.readRange(tr("Range of versions expected")));
672        }
673
674        @Override
675        protected Long getNumber(OsmPrimitive osm) {
676            return (long) osm.getVersion();
677        }
678
679        @Override
680        protected String getString() {
681            return "version";
682        }
683    }
684
685    /**
686     * Matches objects with the given key-value pair.
687     */
688    private static class KeyValue extends TaggedMatch {
689        private final String key;
690        private final Pattern keyPattern;
691        private final String value;
692        private final Pattern valuePattern;
693        private final boolean caseSensitive;
694
695        KeyValue(String key, String value, boolean regexSearch, boolean caseSensitive) throws SearchParseError {
696            this.caseSensitive = caseSensitive;
697            if (regexSearch) {
698                int searchFlags = regexFlags(caseSensitive);
699                this.keyPattern = compilePattern(key, searchFlags);
700                this.valuePattern = compilePattern(value, searchFlags);
701                this.key = key;
702                this.value = value;
703            } else {
704                this.key = key;
705                this.value = value;
706                this.keyPattern = null;
707                this.valuePattern = null;
708            }
709        }
710
711        @Override
712        public boolean match(Tagged osm) {
713
714            if (keyPattern != null) {
715                if (!osm.hasKeys())
716                    return false;
717
718                /* The string search will just get a key like
719                 * 'highway' and look that up as osm.get(key). But
720                 * since we're doing a regex match we'll have to loop
721                 * over all the keys to see if they match our regex,
722                 * and only then try to match against the value
723                 */
724
725                for (String k: osm.keySet()) {
726                    String v = osm.get(k);
727
728                    Matcher matcherKey = keyPattern.matcher(k);
729                    boolean matchedKey = matcherKey.find();
730
731                    if (matchedKey) {
732                        Matcher matcherValue = valuePattern.matcher(v);
733                        boolean matchedValue = matcherValue.find();
734
735                        if (matchedValue)
736                            return true;
737                    }
738                }
739            } else {
740                String mv;
741
742                if ("timestamp".equals(key) && osm instanceof OsmPrimitive) {
743                    mv = DateUtils.fromTimestamp(((OsmPrimitive) osm).getRawTimestamp());
744                } else {
745                    mv = osm.get(key);
746                    if (!caseSensitive && mv == null) {
747                        for (String k: osm.keySet()) {
748                            if (key.equalsIgnoreCase(k)) {
749                                mv = osm.get(k);
750                                break;
751                            }
752                        }
753                    }
754                }
755
756                if (mv == null)
757                    return false;
758
759                String v1 = caseSensitive ? mv : mv.toLowerCase(Locale.ENGLISH);
760                String v2 = caseSensitive ? value : value.toLowerCase(Locale.ENGLISH);
761
762                v1 = Normalizer.normalize(v1, Normalizer.Form.NFC);
763                v2 = Normalizer.normalize(v2, Normalizer.Form.NFC);
764                return v1.indexOf(v2) != -1;
765            }
766
767            return false;
768        }
769
770        @Override
771        public String toString() {
772            return key + '=' + value;
773        }
774
775        @Override
776        public int hashCode() {
777            final int prime = 31;
778            int result = 1;
779            result = prime * result + (caseSensitive ? 1231 : 1237);
780            result = prime * result + ((key == null) ? 0 : key.hashCode());
781            result = prime * result + ((keyPattern == null) ? 0 : keyPattern.hashCode());
782            result = prime * result + ((value == null) ? 0 : value.hashCode());
783            result = prime * result + ((valuePattern == null) ? 0 : valuePattern.hashCode());
784            return result;
785        }
786
787        @Override
788        public boolean equals(Object obj) {
789            if (this == obj)
790                return true;
791            if (obj == null || getClass() != obj.getClass())
792                return false;
793            KeyValue other = (KeyValue) obj;
794            if (caseSensitive != other.caseSensitive)
795                return false;
796            if (key == null) {
797                if (other.key != null)
798                    return false;
799            } else if (!key.equals(other.key))
800                return false;
801            if (keyPattern == null) {
802                if (other.keyPattern != null)
803                    return false;
804            } else if (!keyPattern.equals(other.keyPattern))
805                return false;
806            if (value == null) {
807                if (other.value != null)
808                    return false;
809            } else if (!value.equals(other.value))
810                return false;
811            if (valuePattern == null) {
812                if (other.valuePattern != null)
813                    return false;
814            } else if (!valuePattern.equals(other.valuePattern))
815                return false;
816            return true;
817        }
818    }
819
820    public static class ValueComparison extends TaggedMatch {
821        private final String key;
822        private final String referenceValue;
823        private final Double referenceNumber;
824        private final int compareMode;
825        private static final Pattern ISO8601 = Pattern.compile("\\d+-\\d+-\\d+");
826
827        public ValueComparison(String key, String referenceValue, int compareMode) {
828            this.key = key;
829            this.referenceValue = referenceValue;
830            Double v = null;
831            try {
832                if (referenceValue != null) {
833                    v = Double.valueOf(referenceValue);
834                }
835            } catch (NumberFormatException ignore) {
836                Logging.trace(ignore);
837            }
838            this.referenceNumber = v;
839            this.compareMode = compareMode;
840        }
841
842        @Override
843        public boolean match(Tagged osm) {
844            final String currentValue = osm.get(key);
845            final int compareResult;
846            if (currentValue == null) {
847                return false;
848            } else if (ISO8601.matcher(currentValue).matches() || ISO8601.matcher(referenceValue).matches()) {
849                compareResult = currentValue.compareTo(referenceValue);
850            } else if (referenceNumber != null) {
851                try {
852                    compareResult = Double.compare(Double.parseDouble(currentValue), referenceNumber);
853                } catch (NumberFormatException ignore) {
854                    return false;
855                }
856            } else {
857                compareResult = AlphanumComparator.getInstance().compare(currentValue, referenceValue);
858            }
859            return compareMode < 0 ? compareResult < 0 : compareMode > 0 ? compareResult > 0 : compareResult == 0;
860        }
861
862        @Override
863        public String toString() {
864            return key + (compareMode == -1 ? "<" : compareMode == +1 ? ">" : "") + referenceValue;
865        }
866
867        @Override
868        public int hashCode() {
869            final int prime = 31;
870            int result = 1;
871            result = prime * result + compareMode;
872            result = prime * result + ((key == null) ? 0 : key.hashCode());
873            result = prime * result + ((referenceNumber == null) ? 0 : referenceNumber.hashCode());
874            result = prime * result + ((referenceValue == null) ? 0 : referenceValue.hashCode());
875            return result;
876        }
877
878        @Override
879        public boolean equals(Object obj) {
880            if (this == obj)
881                return true;
882            if (obj == null || getClass() != obj.getClass())
883                return false;
884            ValueComparison other = (ValueComparison) obj;
885            if (compareMode != other.compareMode)
886                return false;
887            if (key == null) {
888                if (other.key != null)
889                    return false;
890            } else if (!key.equals(other.key))
891                return false;
892            if (referenceNumber == null) {
893                if (other.referenceNumber != null)
894                    return false;
895            } else if (!referenceNumber.equals(other.referenceNumber))
896                return false;
897            if (referenceValue == null) {
898                if (other.referenceValue != null)
899                    return false;
900            } else if (!referenceValue.equals(other.referenceValue))
901                return false;
902            return true;
903        }
904    }
905
906    /**
907     * Matches objects with the exact given key-value pair.
908     */
909    public static class ExactKeyValue extends TaggedMatch {
910
911        enum Mode {
912            ANY, ANY_KEY, ANY_VALUE, EXACT, NONE, MISSING_KEY,
913            ANY_KEY_REGEXP, ANY_VALUE_REGEXP, EXACT_REGEXP, MISSING_KEY_REGEXP;
914        }
915
916        private final String key;
917        private final String value;
918        private final Pattern keyPattern;
919        private final Pattern valuePattern;
920        private final Mode mode;
921
922        /**
923         * Constructs a new {@code ExactKeyValue}.
924         * @param regexp regular expression
925         * @param key key
926         * @param value value
927         * @throws SearchParseError if a parse error occurs
928         */
929        public ExactKeyValue(boolean regexp, String key, String value) throws SearchParseError {
930            if ("".equals(key))
931                throw new SearchParseError(tr("Key cannot be empty when tag operator is used. Sample use: key=value"));
932            this.key = key;
933            this.value = value == null ? "" : value;
934            if ("".equals(this.value) && "*".equals(key)) {
935                mode = Mode.NONE;
936            } else if ("".equals(this.value)) {
937                if (regexp) {
938                    mode = Mode.MISSING_KEY_REGEXP;
939                } else {
940                    mode = Mode.MISSING_KEY;
941                }
942            } else if ("*".equals(key) && "*".equals(this.value)) {
943                mode = Mode.ANY;
944            } else if ("*".equals(key)) {
945                if (regexp) {
946                    mode = Mode.ANY_KEY_REGEXP;
947                } else {
948                    mode = Mode.ANY_KEY;
949                }
950            } else if ("*".equals(this.value)) {
951                if (regexp) {
952                    mode = Mode.ANY_VALUE_REGEXP;
953                } else {
954                    mode = Mode.ANY_VALUE;
955                }
956            } else {
957                if (regexp) {
958                    mode = Mode.EXACT_REGEXP;
959                } else {
960                    mode = Mode.EXACT;
961                }
962            }
963
964            if (regexp && !key.isEmpty() && !"*".equals(key)) {
965                keyPattern = compilePattern(key, regexFlags(false));
966            } else {
967                keyPattern = null;
968            }
969            if (regexp && !this.value.isEmpty() && !"*".equals(this.value)) {
970                valuePattern = compilePattern(this.value, regexFlags(false));
971            } else {
972                valuePattern = null;
973            }
974        }
975
976        @Override
977        public boolean match(Tagged osm) {
978
979            if (!osm.hasKeys())
980                return mode == Mode.NONE;
981
982            switch (mode) {
983            case NONE:
984                return false;
985            case MISSING_KEY:
986                return !osm.hasTag(key);
987            case ANY:
988                return true;
989            case ANY_VALUE:
990                return osm.hasTag(key);
991            case ANY_KEY:
992                for (String v:osm.getKeys().values()) {
993                    if (v.equals(value))
994                        return true;
995                }
996                return false;
997            case EXACT:
998                return value.equals(osm.get(key));
999            case ANY_KEY_REGEXP:
1000                for (String v:osm.getKeys().values()) {
1001                    if (valuePattern.matcher(v).matches())
1002                        return true;
1003                }
1004                return false;
1005            case ANY_VALUE_REGEXP:
1006            case EXACT_REGEXP:
1007                for (String k : osm.keySet()) {
1008                    if (keyPattern.matcher(k).matches()
1009                            && (mode == Mode.ANY_VALUE_REGEXP || valuePattern.matcher(osm.get(k)).matches()))
1010                        return true;
1011                }
1012                return false;
1013            case MISSING_KEY_REGEXP:
1014                for (String k:osm.keySet()) {
1015                    if (keyPattern.matcher(k).matches())
1016                        return false;
1017                }
1018                return true;
1019            }
1020            throw new AssertionError("Missed state");
1021        }
1022
1023        @Override
1024        public String toString() {
1025            return key + '=' + value;
1026        }
1027
1028        @Override
1029        public int hashCode() {
1030            final int prime = 31;
1031            int result = 1;
1032            result = prime * result + ((key == null) ? 0 : key.hashCode());
1033            result = prime * result + ((keyPattern == null) ? 0 : keyPattern.hashCode());
1034            result = prime * result + ((mode == null) ? 0 : mode.hashCode());
1035            result = prime * result + ((value == null) ? 0 : value.hashCode());
1036            result = prime * result + ((valuePattern == null) ? 0 : valuePattern.hashCode());
1037            return result;
1038        }
1039
1040        @Override
1041        public boolean equals(Object obj) {
1042            if (this == obj)
1043                return true;
1044            if (obj == null || getClass() != obj.getClass())
1045                return false;
1046            ExactKeyValue other = (ExactKeyValue) obj;
1047            if (key == null) {
1048                if (other.key != null)
1049                    return false;
1050            } else if (!key.equals(other.key))
1051                return false;
1052            if (keyPattern == null) {
1053                if (other.keyPattern != null)
1054                    return false;
1055            } else if (!keyPattern.equals(other.keyPattern))
1056                return false;
1057            if (mode != other.mode)
1058                return false;
1059            if (value == null) {
1060                if (other.value != null)
1061                    return false;
1062            } else if (!value.equals(other.value))
1063                return false;
1064            if (valuePattern == null) {
1065                if (other.valuePattern != null)
1066                    return false;
1067            } else if (!valuePattern.equals(other.valuePattern))
1068                return false;
1069            return true;
1070        }
1071    }
1072
1073    /**
1074     * Match a string in any tags (key or value), with optional regex and case insensitivity.
1075     */
1076    private static class Any extends TaggedMatch {
1077        private final String search;
1078        private final Pattern searchRegex;
1079        private final boolean caseSensitive;
1080
1081        Any(String s, boolean regexSearch, boolean caseSensitive) throws SearchParseError {
1082            s = Normalizer.normalize(s, Normalizer.Form.NFC);
1083            this.caseSensitive = caseSensitive;
1084            if (regexSearch) {
1085                this.searchRegex = compilePattern(s, regexFlags(caseSensitive));
1086                this.search = s;
1087            } else if (caseSensitive) {
1088                this.search = s;
1089                this.searchRegex = null;
1090            } else {
1091                this.search = s.toLowerCase(Locale.ENGLISH);
1092                this.searchRegex = null;
1093            }
1094        }
1095
1096        @Override
1097        public boolean match(Tagged osm) {
1098            if (!osm.hasKeys())
1099                return search.isEmpty();
1100
1101            for (String key: osm.keySet()) {
1102                String value = osm.get(key);
1103                if (searchRegex != null) {
1104
1105                    value = Normalizer.normalize(value, Normalizer.Form.NFC);
1106
1107                    Matcher keyMatcher = searchRegex.matcher(key);
1108                    Matcher valMatcher = searchRegex.matcher(value);
1109
1110                    boolean keyMatchFound = keyMatcher.find();
1111                    boolean valMatchFound = valMatcher.find();
1112
1113                    if (keyMatchFound || valMatchFound)
1114                        return true;
1115                } else {
1116                    if (!caseSensitive) {
1117                        key = key.toLowerCase(Locale.ENGLISH);
1118                        value = value.toLowerCase(Locale.ENGLISH);
1119                    }
1120
1121                    value = Normalizer.normalize(value, Normalizer.Form.NFC);
1122
1123                    if (key.indexOf(search) != -1 || value.indexOf(search) != -1)
1124                        return true;
1125                }
1126            }
1127            return false;
1128        }
1129
1130        @Override
1131        public String toString() {
1132            return search;
1133        }
1134
1135        @Override
1136        public int hashCode() {
1137            final int prime = 31;
1138            int result = 1;
1139            result = prime * result + (caseSensitive ? 1231 : 1237);
1140            result = prime * result + ((search == null) ? 0 : search.hashCode());
1141            result = prime * result + ((searchRegex == null) ? 0 : searchRegex.hashCode());
1142            return result;
1143        }
1144
1145        @Override
1146        public boolean equals(Object obj) {
1147            if (this == obj)
1148                return true;
1149            if (obj == null || getClass() != obj.getClass())
1150                return false;
1151            Any other = (Any) obj;
1152            if (caseSensitive != other.caseSensitive)
1153                return false;
1154            if (search == null) {
1155                if (other.search != null)
1156                    return false;
1157            } else if (!search.equals(other.search))
1158                return false;
1159            if (searchRegex == null) {
1160                if (other.searchRegex != null)
1161                    return false;
1162            } else if (!searchRegex.equals(other.searchRegex))
1163                return false;
1164            return true;
1165        }
1166    }
1167
1168    private static class ExactType extends Match {
1169        private final OsmPrimitiveType type;
1170
1171        ExactType(String type) throws SearchParseError {
1172            this.type = OsmPrimitiveType.from(type);
1173            if (this.type == null)
1174                throw new SearchParseError(tr("Unknown primitive type: {0}. Allowed values are node, way or relation", type));
1175        }
1176
1177        @Override
1178        public boolean match(OsmPrimitive osm) {
1179            return type == osm.getType();
1180        }
1181
1182        @Override
1183        public String toString() {
1184            return "type=" + type;
1185        }
1186
1187        @Override
1188        public int hashCode() {
1189            return 31 + ((type == null) ? 0 : type.hashCode());
1190        }
1191
1192        @Override
1193        public boolean equals(Object obj) {
1194            if (this == obj)
1195                return true;
1196            if (obj == null || getClass() != obj.getClass())
1197                return false;
1198            ExactType other = (ExactType) obj;
1199            return type == other.type;
1200        }
1201    }
1202
1203    /**
1204     * Matches objects last changed by the given username.
1205     */
1206    private static class UserMatch extends Match {
1207        private String user;
1208
1209        UserMatch(String user) {
1210            if ("anonymous".equals(user)) {
1211                this.user = null;
1212            } else {
1213                this.user = user;
1214            }
1215        }
1216
1217        @Override
1218        public boolean match(OsmPrimitive osm) {
1219            if (osm.getUser() == null)
1220                return user == null;
1221            else
1222                return osm.getUser().hasName(user);
1223        }
1224
1225        @Override
1226        public String toString() {
1227            return "user=" + (user == null ? "" : user);
1228        }
1229
1230        @Override
1231        public int hashCode() {
1232            return 31 + ((user == null) ? 0 : user.hashCode());
1233        }
1234
1235        @Override
1236        public boolean equals(Object obj) {
1237            if (this == obj)
1238                return true;
1239            if (obj == null || getClass() != obj.getClass())
1240                return false;
1241            UserMatch other = (UserMatch) obj;
1242            if (user == null) {
1243                if (other.user != null)
1244                    return false;
1245            } else if (!user.equals(other.user))
1246                return false;
1247            return true;
1248        }
1249    }
1250
1251    /**
1252     * Matches objects with the given relation role (i.e. "outer").
1253     */
1254    private static class RoleMatch extends Match {
1255        private String role;
1256
1257        RoleMatch(String role) {
1258            if (role == null) {
1259                this.role = "";
1260            } else {
1261                this.role = role;
1262            }
1263        }
1264
1265        @Override
1266        public boolean match(OsmPrimitive osm) {
1267            for (OsmPrimitive ref: osm.getReferrers()) {
1268                if (ref instanceof Relation && !ref.isIncomplete() && !ref.isDeleted()) {
1269                    for (RelationMember m : ((Relation) ref).getMembers()) {
1270                        if (m.getMember() == osm) {
1271                            String testRole = m.getRole();
1272                            if (role.equals(testRole == null ? "" : testRole))
1273                                return true;
1274                        }
1275                    }
1276                }
1277            }
1278            return false;
1279        }
1280
1281        @Override
1282        public String toString() {
1283            return "role=" + role;
1284        }
1285
1286        @Override
1287        public int hashCode() {
1288            return 31 + ((role == null) ? 0 : role.hashCode());
1289        }
1290
1291        @Override
1292        public boolean equals(Object obj) {
1293            if (this == obj)
1294                return true;
1295            if (obj == null || getClass() != obj.getClass())
1296                return false;
1297            RoleMatch other = (RoleMatch) obj;
1298            if (role == null) {
1299                if (other.role != null)
1300                    return false;
1301            } else if (!role.equals(other.role))
1302                return false;
1303            return true;
1304        }
1305    }
1306
1307    /**
1308     * Matches the n-th object of a relation and/or the n-th node of a way.
1309     */
1310    private static class Nth extends Match {
1311
1312        private final int nth;
1313        private final boolean modulo;
1314
1315        Nth(PushbackTokenizer tokenizer, boolean modulo) throws SearchParseError {
1316            this((int) tokenizer.readNumber(tr("Positive integer expected")), modulo);
1317        }
1318
1319        private Nth(int nth, boolean modulo) {
1320            this.nth = nth;
1321            this.modulo = modulo;
1322        }
1323
1324        @Override
1325        public boolean match(OsmPrimitive osm) {
1326            for (OsmPrimitive p : osm.getReferrers()) {
1327                final int idx;
1328                final int maxIndex;
1329                if (p instanceof Way) {
1330                    Way w = (Way) p;
1331                    idx = w.getNodes().indexOf(osm);
1332                    maxIndex = w.getNodesCount();
1333                } else if (p instanceof Relation) {
1334                    Relation r = (Relation) p;
1335                    idx = r.getMemberPrimitivesList().indexOf(osm);
1336                    maxIndex = r.getMembersCount();
1337                } else {
1338                    continue;
1339                }
1340                if (nth < 0 && idx - maxIndex == nth) {
1341                    return true;
1342                } else if (idx == nth || (modulo && idx % nth == 0))
1343                    return true;
1344            }
1345            return false;
1346        }
1347
1348        @Override
1349        public String toString() {
1350            return "Nth{nth=" + nth + ", modulo=" + modulo + '}';
1351        }
1352
1353        @Override
1354        public int hashCode() {
1355            final int prime = 31;
1356            int result = 1;
1357            result = prime * result + (modulo ? 1231 : 1237);
1358            result = prime * result + nth;
1359            return result;
1360        }
1361
1362        @Override
1363        public boolean equals(Object obj) {
1364            if (this == obj)
1365                return true;
1366            if (obj == null || getClass() != obj.getClass())
1367                return false;
1368            Nth other = (Nth) obj;
1369            return modulo == other.modulo
1370                   && nth == other.nth;
1371        }
1372    }
1373
1374    /**
1375     * Matches objects with properties in a certain range.
1376     */
1377    private abstract static class RangeMatch extends Match {
1378
1379        private final long min;
1380        private final long max;
1381
1382        RangeMatch(long min, long max) {
1383            this.min = Math.min(min, max);
1384            this.max = Math.max(min, max);
1385        }
1386
1387        RangeMatch(Range range) {
1388            this(range.getStart(), range.getEnd());
1389        }
1390
1391        protected abstract Long getNumber(OsmPrimitive osm);
1392
1393        protected abstract String getString();
1394
1395        @Override
1396        public boolean match(OsmPrimitive osm) {
1397            Long num = getNumber(osm);
1398            if (num == null)
1399                return false;
1400            else
1401                return (num >= min) && (num <= max);
1402        }
1403
1404        @Override
1405        public String toString() {
1406            return getString() + '=' + min + '-' + max;
1407        }
1408
1409        @Override
1410        public int hashCode() {
1411            final int prime = 31;
1412            int result = 1;
1413            result = prime * result + (int) (max ^ (max >>> 32));
1414            result = prime * result + (int) (min ^ (min >>> 32));
1415            return result;
1416        }
1417
1418        @Override
1419        public boolean equals(Object obj) {
1420            if (this == obj)
1421                return true;
1422            if (obj == null || getClass() != obj.getClass())
1423                return false;
1424            RangeMatch other = (RangeMatch) obj;
1425            return max == other.max
1426                && min == other.min;
1427        }
1428    }
1429
1430    /**
1431     * Matches ways with a number of nodes in given range
1432     */
1433    private static class NodeCountRange extends RangeMatch {
1434        NodeCountRange(Range range) {
1435            super(range);
1436        }
1437
1438        NodeCountRange(PushbackTokenizer tokenizer) throws SearchParseError {
1439            this(tokenizer.readRange(tr("Range of numbers expected")));
1440        }
1441
1442        @Override
1443        protected Long getNumber(OsmPrimitive osm) {
1444            if (osm instanceof Way) {
1445                return (long) ((Way) osm).getRealNodesCount();
1446            } else if (osm instanceof Relation) {
1447                return (long) ((Relation) osm).getMemberPrimitives(Node.class).size();
1448            } else {
1449                return null;
1450            }
1451        }
1452
1453        @Override
1454        protected String getString() {
1455            return "nodes";
1456        }
1457    }
1458
1459    /**
1460     * Matches objects with the number of referring/contained ways in the given range
1461     */
1462    private static class WayCountRange extends RangeMatch {
1463        WayCountRange(Range range) {
1464            super(range);
1465        }
1466
1467        WayCountRange(PushbackTokenizer tokenizer) throws SearchParseError {
1468            this(tokenizer.readRange(tr("Range of numbers expected")));
1469        }
1470
1471        @Override
1472        protected Long getNumber(OsmPrimitive osm) {
1473            if (osm instanceof Node) {
1474                return osm.referrers(Way.class).count();
1475            } else if (osm instanceof Relation) {
1476                return (long) ((Relation) osm).getMemberPrimitives(Way.class).size();
1477            } else {
1478                return null;
1479            }
1480        }
1481
1482        @Override
1483        protected String getString() {
1484            return "ways";
1485        }
1486    }
1487
1488    /**
1489     * Matches objects with a number of tags in given range
1490     */
1491    private static class TagCountRange extends RangeMatch {
1492        TagCountRange(Range range) {
1493            super(range);
1494        }
1495
1496        TagCountRange(PushbackTokenizer tokenizer) throws SearchParseError {
1497            this(tokenizer.readRange(tr("Range of numbers expected")));
1498        }
1499
1500        @Override
1501        protected Long getNumber(OsmPrimitive osm) {
1502            return (long) osm.getKeys().size();
1503        }
1504
1505        @Override
1506        protected String getString() {
1507            return "tags";
1508        }
1509    }
1510
1511    /**
1512     * Matches objects with a timestamp in given range
1513     */
1514    private static class TimestampRange extends RangeMatch {
1515
1516        TimestampRange(long minCount, long maxCount) {
1517            super(minCount, maxCount);
1518        }
1519
1520        @Override
1521        protected Long getNumber(OsmPrimitive osm) {
1522            return osm.getTimestamp().getTime();
1523        }
1524
1525        @Override
1526        protected String getString() {
1527            return "timestamp";
1528        }
1529    }
1530
1531    /**
1532     * Matches relations with a member of the given role
1533     */
1534    private static class HasRole extends Match {
1535        private final String role;
1536
1537        HasRole(PushbackTokenizer tokenizer) {
1538            role = tokenizer.readTextOrNumber();
1539        }
1540
1541        @Override
1542        public boolean match(OsmPrimitive osm) {
1543            return osm instanceof Relation && ((Relation) osm).getMemberRoles().contains(role);
1544        }
1545
1546        @Override
1547        public int hashCode() {
1548            return 31 + ((role == null) ? 0 : role.hashCode());
1549        }
1550
1551        @Override
1552        public boolean equals(Object obj) {
1553            if (this == obj)
1554                return true;
1555            if (obj == null || getClass() != obj.getClass())
1556                return false;
1557            HasRole other = (HasRole) obj;
1558            if (role == null) {
1559                if (other.role != null)
1560                    return false;
1561            } else if (!role.equals(other.role))
1562                return false;
1563            return true;
1564        }
1565    }
1566
1567    /**
1568     * Matches objects that are new (i.e. have not been uploaded to the server)
1569     */
1570    private static class New extends Match {
1571        @Override
1572        public boolean match(OsmPrimitive osm) {
1573            return osm.isNew();
1574        }
1575
1576        @Override
1577        public String toString() {
1578            return "new";
1579        }
1580    }
1581
1582    /**
1583     * Matches all objects that have been modified, created, or undeleted
1584     */
1585    private static class Modified extends Match {
1586        @Override
1587        public boolean match(OsmPrimitive osm) {
1588            return osm.isModified() || osm.isNewOrUndeleted();
1589        }
1590
1591        @Override
1592        public String toString() {
1593            return "modified";
1594        }
1595    }
1596
1597    /**
1598     * Matches all objects that have been deleted
1599     */
1600    private static class Deleted extends Match {
1601        @Override
1602        public boolean match(OsmPrimitive osm) {
1603            return osm.isDeleted();
1604        }
1605
1606        @Override
1607        public String toString() {
1608            return "deleted";
1609        }
1610    }
1611
1612    /**
1613     * Matches all objects currently selected
1614     */
1615    private static class Selected extends Match {
1616        @Override
1617        public boolean match(OsmPrimitive osm) {
1618            return osm.getDataSet().isSelected(osm);
1619        }
1620
1621        @Override
1622        public String toString() {
1623            return "selected";
1624        }
1625    }
1626
1627    /**
1628     * Match objects that are incomplete, where only id and type are known.
1629     * Typically some members of a relation are incomplete until they are
1630     * fetched from the server.
1631     */
1632    private static class Incomplete extends Match {
1633        @Override
1634        public boolean match(OsmPrimitive osm) {
1635            return osm.isIncomplete() || (osm instanceof Relation && ((Relation) osm).hasIncompleteMembers());
1636        }
1637
1638        @Override
1639        public String toString() {
1640            return "incomplete";
1641        }
1642    }
1643
1644    /**
1645     * Matches objects that don't have any interesting tags (i.e. only has source,
1646     * FIXME, etc.). The complete list of uninteresting tags can be found here:
1647     * org.openstreetmap.josm.data.osm.OsmPrimitive.getUninterestingKeys()
1648     */
1649    private static class Untagged extends Match {
1650        @Override
1651        public boolean match(OsmPrimitive osm) {
1652            return !osm.isTagged() && !osm.isIncomplete();
1653        }
1654
1655        @Override
1656        public String toString() {
1657            return "untagged";
1658        }
1659    }
1660
1661    /**
1662     * Matches ways which are closed (i.e. first and last node are the same)
1663     */
1664    private static class Closed extends Match {
1665        @Override
1666        public boolean match(OsmPrimitive osm) {
1667            return osm instanceof Way && ((Way) osm).isClosed();
1668        }
1669
1670        @Override
1671        public String toString() {
1672            return "closed";
1673        }
1674    }
1675
1676    /**
1677     * Matches objects if they are parents of the expression
1678     */
1679    public static class Parent extends UnaryMatch {
1680        public Parent(Match m) {
1681            super(m);
1682        }
1683
1684        @Override
1685        public boolean match(OsmPrimitive osm) {
1686            boolean isParent = false;
1687
1688            if (osm instanceof Way) {
1689                for (Node n : ((Way) osm).getNodes()) {
1690                    isParent |= match.match(n);
1691                }
1692            } else if (osm instanceof Relation) {
1693                for (RelationMember member : ((Relation) osm).getMembers()) {
1694                    isParent |= match.match(member.getMember());
1695                }
1696            }
1697            return isParent;
1698        }
1699
1700        @Override
1701        public String toString() {
1702            return "parent(" + match + ')';
1703        }
1704    }
1705
1706    /**
1707     * Matches objects if they are children of the expression
1708     */
1709    public static class Child extends UnaryMatch {
1710
1711        public Child(Match m) {
1712            super(m);
1713        }
1714
1715        @Override
1716        public boolean match(OsmPrimitive osm) {
1717            boolean isChild = false;
1718            for (OsmPrimitive p : osm.getReferrers()) {
1719                isChild |= match.match(p);
1720            }
1721            return isChild;
1722        }
1723
1724        @Override
1725        public String toString() {
1726            return "child(" + match + ')';
1727        }
1728    }
1729
1730    /**
1731     * Matches if the size of the area is within the given range
1732     *
1733     * @author Ole Jørgen Brønner
1734     */
1735    private static class AreaSize extends RangeMatch {
1736
1737        AreaSize(Range range) {
1738            super(range);
1739        }
1740
1741        AreaSize(PushbackTokenizer tokenizer) throws SearchParseError {
1742            this(tokenizer.readRange(tr("Range of numbers expected")));
1743        }
1744
1745        @Override
1746        protected Long getNumber(OsmPrimitive osm) {
1747            final Double area = Geometry.computeArea(osm);
1748            return area == null ? null : area.longValue();
1749        }
1750
1751        @Override
1752        protected String getString() {
1753            return "areasize";
1754        }
1755    }
1756
1757    /**
1758     * Matches if the length of a way is within the given range
1759     */
1760    private static class WayLength extends RangeMatch {
1761
1762        WayLength(Range range) {
1763            super(range);
1764        }
1765
1766        WayLength(PushbackTokenizer tokenizer) throws SearchParseError {
1767            this(tokenizer.readRange(tr("Range of numbers expected")));
1768        }
1769
1770        @Override
1771        protected Long getNumber(OsmPrimitive osm) {
1772            if (!(osm instanceof Way))
1773                return null;
1774            Way way = (Way) osm;
1775            return (long) way.getLength();
1776        }
1777
1778        @Override
1779        protected String getString() {
1780            return "waylength";
1781        }
1782    }
1783
1784    /**
1785     * Matches objects within the given bounds.
1786     */
1787    public abstract static class InArea extends Match {
1788
1789        protected final boolean all;
1790
1791        /**
1792         * @param all if true, all way nodes or relation members have to be within source area;if false, one suffices.
1793         */
1794        protected InArea(boolean all) {
1795            this.all = all;
1796        }
1797
1798        protected abstract Collection<Bounds> getBounds(OsmPrimitive primitive);
1799
1800        @Override
1801        public boolean match(OsmPrimitive osm) {
1802            if (!osm.isUsable())
1803                return false;
1804            else if (osm instanceof Node) {
1805                LatLon coordinate = ((Node) osm).getCoor();
1806                Collection<Bounds> allBounds = getBounds(osm);
1807                return coordinate != null && allBounds != null && allBounds.stream().anyMatch(bounds -> bounds.contains(coordinate));
1808            } else if (osm instanceof Way) {
1809                Collection<Node> nodes = ((Way) osm).getNodes();
1810                return all ? nodes.stream().allMatch(this) : nodes.stream().anyMatch(this);
1811            } else if (osm instanceof Relation) {
1812                Collection<OsmPrimitive> primitives = ((Relation) osm).getMemberPrimitivesList();
1813                return all ? primitives.stream().allMatch(this) : primitives.stream().anyMatch(this);
1814            } else
1815                return false;
1816        }
1817
1818        @Override
1819        public int hashCode() {
1820            return 31 + (all ? 1231 : 1237);
1821        }
1822
1823        @Override
1824        public boolean equals(Object obj) {
1825            if (this == obj)
1826                return true;
1827            if (obj == null || getClass() != obj.getClass())
1828                return false;
1829            InArea other = (InArea) obj;
1830            return all == other.all;
1831        }
1832    }
1833
1834    /**
1835     * Matches objects within source area ("downloaded area").
1836     */
1837    public static class InDataSourceArea extends InArea {
1838
1839        /**
1840         * Constructs a new {@code InDataSourceArea}.
1841         * @param all if true, all way nodes or relation members have to be within source area; if false, one suffices.
1842         */
1843        public InDataSourceArea(boolean all) {
1844            super(all);
1845        }
1846
1847        @Override
1848        protected Collection<Bounds> getBounds(OsmPrimitive primitive) {
1849            return primitive.getDataSet() != null ? primitive.getDataSet().getDataSourceBounds() : null;
1850        }
1851
1852        @Override
1853        public String toString() {
1854            return all ? "allindownloadedarea" : "indownloadedarea";
1855        }
1856    }
1857
1858    /**
1859     * Matches objects which are not outside the source area ("downloaded area").
1860     * Unlike {@link InDataSourceArea} this matches also if no source area is set (e.g., for new layers).
1861     */
1862    public static class NotOutsideDataSourceArea extends InDataSourceArea {
1863
1864        /**
1865         * Constructs a new {@code NotOutsideDataSourceArea}.
1866         */
1867        public NotOutsideDataSourceArea() {
1868            super(false);
1869        }
1870
1871        @Override
1872        protected Collection<Bounds> getBounds(OsmPrimitive primitive) {
1873            final Collection<Bounds> bounds = super.getBounds(primitive);
1874            return bounds == null || bounds.isEmpty() ?
1875                    Collections.singleton(ProjectionRegistry.getProjection().getWorldBoundsLatLon()) : bounds;
1876        }
1877
1878        @Override
1879        public String toString() {
1880            return "NotOutsideDataSourceArea";
1881        }
1882    }
1883
1884    /**
1885     * Matches presets.
1886     * @since 12464
1887     */
1888    private static class Preset extends Match {
1889        private final List<TaggingPreset> presets;
1890
1891        Preset(String presetName) throws SearchParseError {
1892
1893            if (presetName == null || presetName.isEmpty()) {
1894                throw new SearchParseError("The name of the preset is required");
1895            }
1896
1897            int wildCardIdx = presetName.lastIndexOf('*');
1898            int length = presetName.length() - 1;
1899
1900            /*
1901             * Match strictly (simply comparing the names) if there is no '*' symbol
1902             * at the end of the name or '*' is a part of the preset name.
1903             */
1904            boolean matchStrictly = wildCardIdx == -1 || wildCardIdx != length;
1905
1906            this.presets = TaggingPresets.getTaggingPresets()
1907                    .stream()
1908                    .filter(preset -> !(preset instanceof TaggingPresetMenu || preset instanceof TaggingPresetSeparator))
1909                    .filter(preset -> presetNameMatch(presetName, preset, matchStrictly))
1910                    .collect(Collectors.toList());
1911
1912            if (this.presets.isEmpty()) {
1913                throw new SearchParseError(tr("Unknown preset name: ") + presetName);
1914            }
1915        }
1916
1917        @Override
1918        public boolean match(OsmPrimitive osm) {
1919            for (TaggingPreset preset : this.presets) {
1920                if (preset.test(osm)) {
1921                    return true;
1922                }
1923            }
1924
1925            return false;
1926        }
1927
1928        private static boolean presetNameMatch(String name, TaggingPreset preset, boolean matchStrictly) {
1929            if (matchStrictly) {
1930                return name.equalsIgnoreCase(preset.getRawName());
1931            }
1932
1933            try {
1934                String groupSuffix = name.substring(0, name.length() - 2); // try to remove '/*'
1935                TaggingPresetMenu group = preset.group;
1936
1937                return group != null && groupSuffix.equalsIgnoreCase(group.getRawName());
1938            } catch (StringIndexOutOfBoundsException ex) {
1939                Logging.trace(ex);
1940                return false;
1941            }
1942        }
1943
1944        @Override
1945        public int hashCode() {
1946            return 31 + ((presets == null) ? 0 : presets.hashCode());
1947        }
1948
1949        @Override
1950        public boolean equals(Object obj) {
1951            if (this == obj)
1952                return true;
1953            if (obj == null || getClass() != obj.getClass())
1954                return false;
1955            Preset other = (Preset) obj;
1956            if (presets == null) {
1957                if (other.presets != null)
1958                    return false;
1959            } else if (!presets.equals(other.presets))
1960                return false;
1961            return true;
1962        }
1963    }
1964
1965    /**
1966     * Compiles the search expression.
1967     * @param searchStr the search expression
1968     * @return a {@link Match} object for the expression
1969     * @throws SearchParseError if an error has been encountered while compiling
1970     * @see #compile(SearchSetting)
1971     */
1972    public static Match compile(String searchStr) throws SearchParseError {
1973        return new SearchCompiler(false, false,
1974                new PushbackTokenizer(
1975                        new PushbackReader(new StringReader(searchStr))))
1976                .parse();
1977    }
1978
1979    /**
1980     * Compiles the search expression.
1981     * @param setting the settings to use
1982     * @return a {@link Match} object for the expression
1983     * @throws SearchParseError if an error has been encountered while compiling
1984     * @see #compile(String)
1985     */
1986    public static Match compile(SearchSetting setting) throws SearchParseError {
1987        if (setting.mapCSSSearch) {
1988            return compileMapCSS(setting.text);
1989        }
1990        return new SearchCompiler(setting.caseSensitive, setting.regexSearch,
1991                new PushbackTokenizer(
1992                        new PushbackReader(new StringReader(setting.text))))
1993                .parse();
1994    }
1995
1996    static Match compileMapCSS(String mapCSS) throws SearchParseError {
1997        try {
1998            final List<Selector> selectors = new MapCSSParser(new StringReader(mapCSS)).selectors();
1999            return new Match() {
2000                @Override
2001                public boolean match(OsmPrimitive osm) {
2002                    for (Selector selector : selectors) {
2003                        if (selector.matches(new Environment(osm))) {
2004                            return true;
2005                        }
2006                    }
2007                    return false;
2008                }
2009            };
2010        } catch (ParseException | IllegalArgumentException e) {
2011            throw new SearchParseError(tr("Failed to parse MapCSS selector"), e);
2012        }
2013    }
2014
2015    /**
2016     * Parse search string.
2017     *
2018     * @return match determined by search string
2019     * @throws org.openstreetmap.josm.data.osm.search.SearchParseError if search expression cannot be parsed
2020     */
2021    public Match parse() throws SearchParseError {
2022        Match m = Optional.ofNullable(parseExpression()).orElse(Always.INSTANCE);
2023        if (!tokenizer.readIfEqual(Token.EOF))
2024            throw new SearchParseError(tr("Unexpected token: {0}", tokenizer.nextToken()));
2025        Logging.debug("Parsed search expression is {0}", m);
2026        return m;
2027    }
2028
2029    /**
2030     * Parse expression.
2031     *
2032     * @return match determined by parsing expression
2033     * @throws SearchParseError if search expression cannot be parsed
2034     */
2035    private Match parseExpression() throws SearchParseError {
2036        // Step 1: parse the whole expression and build a list of factors and logical tokens
2037        List<Object> list = parseExpressionStep1();
2038        // Step 2: iterate the list in reverse order to build the logical expression
2039        // This iterative approach avoids StackOverflowError for long expressions (see #14217)
2040        return parseExpressionStep2(list);
2041    }
2042
2043    private List<Object> parseExpressionStep1() throws SearchParseError {
2044        Match factor;
2045        String token = null;
2046        String errorMessage = null;
2047        List<Object> list = new ArrayList<>();
2048        do {
2049            factor = parseFactor();
2050            if (factor != null) {
2051                if (token != null) {
2052                    list.add(token);
2053                }
2054                list.add(factor);
2055                if (tokenizer.readIfEqual(Token.OR)) {
2056                    token = "OR";
2057                    errorMessage = tr("Missing parameter for OR");
2058                } else if (tokenizer.readIfEqual(Token.XOR)) {
2059                    token = "XOR";
2060                    errorMessage = tr("Missing parameter for XOR");
2061                } else {
2062                    token = "AND";
2063                    errorMessage = null;
2064                }
2065            } else if (errorMessage != null) {
2066                throw new SearchParseError(errorMessage);
2067            }
2068        } while (factor != null);
2069        return list;
2070    }
2071
2072    private static Match parseExpressionStep2(List<Object> list) {
2073        Match result = null;
2074        for (int i = list.size() - 1; i >= 0; i--) {
2075            Object o = list.get(i);
2076            if (o instanceof Match && result == null) {
2077                result = (Match) o;
2078            } else if (o instanceof String && i > 0) {
2079                Match factor = (Match) list.get(i-1);
2080                switch ((String) o) {
2081                case "OR":
2082                    result = new Or(factor, result);
2083                    break;
2084                case "XOR":
2085                    result = new Xor(factor, result);
2086                    break;
2087                case "AND":
2088                    result = new And(factor, result);
2089                    break;
2090                default: throw new IllegalStateException(tr("Unexpected token: {0}", o));
2091                }
2092                i--;
2093            } else {
2094                throw new IllegalStateException("i=" + i + "; o=" + o);
2095            }
2096        }
2097        return result;
2098    }
2099
2100    /**
2101     * Parse next factor (a search operator or search term).
2102     *
2103     * @return match determined by parsing factor string
2104     * @throws SearchParseError if search expression cannot be parsed
2105     */
2106    private Match parseFactor() throws SearchParseError {
2107        if (tokenizer.readIfEqual(Token.LEFT_PARENT)) {
2108            Match expression = parseExpression();
2109            if (!tokenizer.readIfEqual(Token.RIGHT_PARENT))
2110                throw new SearchParseError(Token.RIGHT_PARENT, tokenizer.nextToken());
2111            return expression;
2112        } else if (tokenizer.readIfEqual(Token.NOT)) {
2113            return new Not(parseFactor(tr("Missing operator for NOT")));
2114        } else if (tokenizer.readIfEqual(Token.KEY)) {
2115            // factor consists of key:value or key=value
2116            String key = tokenizer.getText();
2117            if (tokenizer.readIfEqual(Token.EQUALS)) {
2118                return new ExactKeyValue(regexSearch, key, tokenizer.readTextOrNumber());
2119            } else if (tokenizer.readIfEqual(Token.LESS_THAN)) {
2120                return new ValueComparison(key, tokenizer.readTextOrNumber(), -1);
2121            } else if (tokenizer.readIfEqual(Token.GREATER_THAN)) {
2122                return new ValueComparison(key, tokenizer.readTextOrNumber(), +1);
2123            } else if (tokenizer.readIfEqual(Token.COLON)) {
2124                // see if we have a Match that takes a data parameter
2125                SimpleMatchFactory factory = simpleMatchFactoryMap.get(key);
2126                if (factory != null)
2127                    return factory.get(key, caseSensitive, regexSearch, tokenizer);
2128
2129                UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key);
2130                if (unaryFactory != null)
2131                    return unaryFactory.get(key, parseFactor(), tokenizer);
2132
2133                // key:value form where value is a string (may be OSM key search)
2134                final String value = tokenizer.readTextOrNumber();
2135                return new KeyValue(key, value != null ? value : "", regexSearch, caseSensitive);
2136            } else if (tokenizer.readIfEqual(Token.QUESTION_MARK))
2137                return new BooleanMatch(key, false);
2138            else {
2139                SimpleMatchFactory factory = simpleMatchFactoryMap.get(key);
2140                if (factory != null)
2141                    return factory.get(key, caseSensitive, regexSearch, null);
2142
2143                UnaryMatchFactory unaryFactory = unaryMatchFactoryMap.get(key);
2144                if (unaryFactory != null)
2145                    return unaryFactory.get(key, parseFactor(), null);
2146
2147                // match string in any key or value
2148                return new Any(key, regexSearch, caseSensitive);
2149            }
2150        } else
2151            return null;
2152    }
2153
2154    private Match parseFactor(String errorMessage) throws SearchParseError {
2155        return Optional.ofNullable(parseFactor()).orElseThrow(() -> new SearchParseError(errorMessage));
2156    }
2157
2158    private static int regexFlags(boolean caseSensitive) {
2159        int searchFlags = 0;
2160
2161        // Enables canonical Unicode equivalence so that e.g. the two
2162        // forms of "\u00e9gal" and "e\u0301gal" will match.
2163        //
2164        // It makes sense to match no matter how the character
2165        // happened to be constructed.
2166        searchFlags |= Pattern.CANON_EQ;
2167
2168        // Make "." match any character including newline (/s in Perl)
2169        searchFlags |= Pattern.DOTALL;
2170
2171        // CASE_INSENSITIVE by itself only matches US-ASCII case
2172        // insensitively, but the OSM data is in Unicode. With
2173        // UNICODE_CASE casefolding is made Unicode-aware.
2174        if (!caseSensitive) {
2175            searchFlags |= (Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE);
2176        }
2177
2178        return searchFlags;
2179    }
2180
2181    static String escapeStringForSearch(String s) {
2182        return s.replace("\\", "\\\\").replace("\"", "\\\"");
2183    }
2184
2185    /**
2186     * Builds a search string for the given tag. If value is empty, the existence of the key is checked.
2187     *
2188     * @param key   the tag key
2189     * @param value the tag value
2190     * @return a search string for the given tag
2191     */
2192    public static String buildSearchStringForTag(String key, String value) {
2193        final String forKey = '"' + escapeStringForSearch(key) + '"' + '=';
2194        if (value == null || value.isEmpty()) {
2195            return forKey + '*';
2196        } else {
2197            return forKey + '"' + escapeStringForSearch(value) + '"';
2198        }
2199    }
2200}