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