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