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