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