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