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