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