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