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