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