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