001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.tagging.ac;
003
004import java.util.ArrayList;
005import java.util.Arrays;
006import java.util.Collection;
007import java.util.Collections;
008import java.util.Comparator;
009import java.util.HashMap;
010import java.util.HashSet;
011import java.util.LinkedHashSet;
012import java.util.List;
013import java.util.Map;
014import java.util.Map.Entry;
015import java.util.Objects;
016import java.util.Set;
017import java.util.function.Function;
018import java.util.stream.Collectors;
019
020import org.openstreetmap.josm.data.osm.DataSet;
021import org.openstreetmap.josm.data.osm.OsmPrimitive;
022import org.openstreetmap.josm.data.osm.Relation;
023import org.openstreetmap.josm.data.osm.RelationMember;
024import org.openstreetmap.josm.data.osm.event.AbstractDatasetChangedEvent;
025import org.openstreetmap.josm.data.osm.event.DataChangedEvent;
026import org.openstreetmap.josm.data.osm.event.DataSetListener;
027import org.openstreetmap.josm.data.osm.event.NodeMovedEvent;
028import org.openstreetmap.josm.data.osm.event.PrimitivesAddedEvent;
029import org.openstreetmap.josm.data.osm.event.PrimitivesRemovedEvent;
030import org.openstreetmap.josm.data.osm.event.RelationMembersChangedEvent;
031import org.openstreetmap.josm.data.osm.event.TagsChangedEvent;
032import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
033import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
034import org.openstreetmap.josm.data.tagging.ac.AutoCompletionPriority;
035import org.openstreetmap.josm.data.tagging.ac.AutoCompletionSet;
036import org.openstreetmap.josm.gui.MainApplication;
037import org.openstreetmap.josm.gui.layer.LayerManager.LayerAddEvent;
038import org.openstreetmap.josm.gui.layer.LayerManager.LayerChangeListener;
039import org.openstreetmap.josm.gui.layer.LayerManager.LayerOrderChangeEvent;
040import org.openstreetmap.josm.gui.layer.LayerManager.LayerRemoveEvent;
041import org.openstreetmap.josm.gui.layer.OsmDataLayer;
042import org.openstreetmap.josm.gui.tagging.presets.TaggingPreset;
043import org.openstreetmap.josm.gui.tagging.presets.TaggingPresets;
044import org.openstreetmap.josm.gui.tagging.presets.items.Roles.Role;
045import org.openstreetmap.josm.tools.CheckParameterUtil;
046import org.openstreetmap.josm.tools.MultiMap;
047import org.openstreetmap.josm.tools.Utils;
048
049/**
050 * AutoCompletionManager holds a cache of keys with a list of
051 * possible auto completion values for each key.
052 *
053 * Each DataSet can be assigned one AutoCompletionManager instance such that
054 * <ol>
055 *   <li>any key used in a tag in the data set is part of the key list in the cache</li>
056 *   <li>any value used in a tag for a specific key is part of the autocompletion list of this key</li>
057 * </ol>
058 *
059 * Building up auto completion lists should not
060 * slow down tabbing from input field to input field. Looping through the complete
061 * data set in order to build up the auto completion list for a specific input
062 * field is not efficient enough, hence this cache.
063 *
064 * TODO: respect the relation type for member role autocompletion
065 */
066public class AutoCompletionManager implements DataSetListener {
067
068    /**
069     * Data class to remember tags that the user has entered.
070     */
071    public static class UserInputTag {
072        private final String key;
073        private final String value;
074        private final boolean defaultKey;
075
076        /**
077         * Constructor.
078         *
079         * @param key the tag key
080         * @param value the tag value
081         * @param defaultKey true, if the key was not really entered by the
082         * user, e.g. for preset text fields.
083         * In this case, the key will not get any higher priority, just the value.
084         */
085        public UserInputTag(String key, String value, boolean defaultKey) {
086            this.key = key;
087            this.value = value;
088            this.defaultKey = defaultKey;
089        }
090
091        @Override
092        public int hashCode() {
093            return Objects.hash(key, value, defaultKey);
094        }
095
096        @Override
097        public boolean equals(Object obj) {
098            if (obj == null || getClass() != obj.getClass()) {
099                return false;
100            }
101            final UserInputTag other = (UserInputTag) obj;
102            return this.defaultKey == other.defaultKey
103                && Objects.equals(this.key, other.key)
104                && Objects.equals(this.value, other.value);
105        }
106    }
107
108    /** If the dirty flag is set true, a rebuild is necessary. */
109    protected boolean dirty;
110    /** The data set that is managed */
111    protected DataSet ds;
112
113    /**
114     * the cached tags given by a tag key and a list of values for this tag
115     * only accessed by getTagCache(), rebuild() and cachePrimitiveTags()
116     * use getTagCache() accessor
117     */
118    protected MultiMap<String, String> tagCache;
119
120    /**
121     * the same as tagCache but for the preset keys and values can be accessed directly
122     */
123    static final MultiMap<String, String> PRESET_TAG_CACHE = new MultiMap<>();
124
125    /**
126     * Cache for tags that have been entered by the user.
127     */
128    static final Set<UserInputTag> USER_INPUT_TAG_CACHE = new LinkedHashSet<>();
129
130    /**
131     * the cached list of member roles
132     * only accessed by getRoleCache(), rebuild() and cacheRelationMemberRoles()
133     * use getRoleCache() accessor
134     */
135    protected Set<String> roleCache;
136
137    /**
138     * the same as roleCache but for the preset roles can be accessed directly
139     */
140    static final Set<String> PRESET_ROLE_CACHE = new HashSet<>();
141
142    private static final Map<DataSet, AutoCompletionManager> INSTANCES = new HashMap<>();
143
144    /**
145     * Constructs a new {@code AutoCompletionManager}.
146     * @param ds data set
147     * @throws NullPointerException if ds is null
148     */
149    public AutoCompletionManager(DataSet ds) {
150        this.ds = Objects.requireNonNull(ds);
151        this.dirty = true;
152    }
153
154    protected MultiMap<String, String> getTagCache() {
155        if (dirty) {
156            rebuild();
157            dirty = false;
158        }
159        return tagCache;
160    }
161
162    protected Set<String> getRoleCache() {
163        if (dirty) {
164            rebuild();
165            dirty = false;
166        }
167        return roleCache;
168    }
169
170    /**
171     * initializes the cache from the primitives in the dataset
172     */
173    protected void rebuild() {
174        tagCache = new MultiMap<>();
175        roleCache = new HashSet<>();
176        cachePrimitives(ds.allNonDeletedCompletePrimitives());
177    }
178
179    protected void cachePrimitives(Collection<? extends OsmPrimitive> primitives) {
180        for (OsmPrimitive primitive : primitives) {
181            cachePrimitiveTags(primitive);
182            if (primitive instanceof Relation) {
183                cacheRelationMemberRoles((Relation) primitive);
184            }
185        }
186    }
187
188    /**
189     * make sure, the keys and values of all tags held by primitive are
190     * in the auto completion cache
191     *
192     * @param primitive an OSM primitive
193     */
194    protected void cachePrimitiveTags(OsmPrimitive primitive) {
195        primitive.visitKeys((p, key, value) -> tagCache.put(key, value));
196    }
197
198    /**
199     * Caches all member roles of the relation <code>relation</code>
200     *
201     * @param relation the relation
202     */
203    protected void cacheRelationMemberRoles(Relation relation) {
204        for (RelationMember m: relation.getMembers()) {
205            if (m.hasRole()) {
206                roleCache.add(m.getRole());
207            }
208        }
209    }
210
211    /**
212     * Remembers user input for the given key/value.
213     * @param key Tag key
214     * @param value Tag value
215     * @param defaultKey true, if the key was not really entered by the user, e.g. for preset text fields
216     */
217    public static void rememberUserInput(String key, String value, boolean defaultKey) {
218        UserInputTag tag = new UserInputTag(key, value, defaultKey);
219        USER_INPUT_TAG_CACHE.remove(tag); // re-add, so it gets to the last position of the LinkedHashSet
220        USER_INPUT_TAG_CACHE.add(tag);
221    }
222
223    /**
224     * replies the keys held by the cache
225     *
226     * @return the list of keys held by the cache
227     */
228    protected List<String> getDataKeys() {
229        return new ArrayList<>(getTagCache().keySet());
230    }
231
232    protected Collection<String> getUserInputKeys() {
233        List<String> keys = USER_INPUT_TAG_CACHE.stream()
234                .filter(tag -> !tag.defaultKey)
235                .map(tag -> tag.key)
236                .collect(Collectors.toList());
237        Collections.reverse(keys);
238        return new LinkedHashSet<>(keys);
239    }
240
241    /**
242     * replies the auto completion values allowed for a specific key. Replies
243     * an empty list if key is null or if key is not in {@link #getTagKeys()}.
244     *
245     * @param key OSM key
246     * @return the list of auto completion values
247     */
248    protected List<String> getDataValues(String key) {
249        return new ArrayList<>(getTagCache().getValues(key));
250    }
251
252    protected static Collection<String> getUserInputValues(String key) {
253        List<String> values = USER_INPUT_TAG_CACHE.stream()
254                .filter(tag -> Objects.equals(key, tag.key))
255                .map(tag -> tag.value)
256                .collect(Collectors.toList());
257        Collections.reverse(values);
258        return new LinkedHashSet<>(values);
259    }
260
261    /**
262     * Replies the list of member roles
263     *
264     * @return the list of member roles
265     */
266    public List<String> getMemberRoles() {
267        return new ArrayList<>(getRoleCache());
268    }
269
270    /**
271     * Populates the {@link AutoCompletionList} with the currently cached member roles.
272     *
273     * @param list the list to populate
274     */
275    public void populateWithMemberRoles(AutoCompletionList list) {
276        list.add(TaggingPresets.getPresetRoles(), AutoCompletionPriority.IS_IN_STANDARD);
277        list.add(getRoleCache(), AutoCompletionPriority.IS_IN_DATASET);
278    }
279
280    /**
281     * Populates the {@link AutoCompletionList} with the roles used in this relation
282     * plus the ones defined in its applicable presets, if any. If the relation type is unknown,
283     * then all the roles known globally will be added, as in {@link #populateWithMemberRoles(AutoCompletionList)}.
284     *
285     * @param list the list to populate
286     * @param r the relation to get roles from
287     * @throws IllegalArgumentException if list is null
288     * @since 7556
289     */
290    public void populateWithMemberRoles(AutoCompletionList list, Relation r) {
291        CheckParameterUtil.ensureParameterNotNull(list, "list");
292        Collection<TaggingPreset> presets = r != null ? TaggingPresets.getMatchingPresets(null, r.getKeys(), false) : Collections.emptyList();
293        if (r != null && !Utils.isEmpty(presets)) {
294            for (TaggingPreset tp : presets) {
295                if (tp.roles != null) {
296                    list.add(Utils.transform(tp.roles.roles, (Function<Role, String>) x -> x.key), AutoCompletionPriority.IS_IN_STANDARD);
297                }
298            }
299            list.add(r.getMemberRoles(), AutoCompletionPriority.IS_IN_DATASET);
300        } else {
301            populateWithMemberRoles(list);
302        }
303    }
304
305    /**
306     * Populates the an {@link AutoCompletionList} with the currently cached tag keys
307     *
308     * @param list the list to populate
309     */
310    public void populateWithKeys(AutoCompletionList list) {
311        list.add(TaggingPresets.getPresetKeys(), AutoCompletionPriority.IS_IN_STANDARD);
312        list.add(new AutoCompletionItem("source", AutoCompletionPriority.IS_IN_STANDARD));
313        list.add(getDataKeys(), AutoCompletionPriority.IS_IN_DATASET);
314        list.addUserInput(getUserInputKeys());
315    }
316
317    /**
318     * Populates the an {@link AutoCompletionList} with the currently cached values for a tag
319     *
320     * @param list the list to populate
321     * @param key the tag key
322     */
323    public void populateWithTagValues(AutoCompletionList list, String key) {
324        populateWithTagValues(list, Arrays.asList(key));
325    }
326
327    /**
328     * Populates the {@link AutoCompletionList} with the currently cached values for some given tags
329     *
330     * @param list the list to populate
331     * @param keys the tag keys
332     */
333    public void populateWithTagValues(AutoCompletionList list, List<String> keys) {
334        for (String key : keys) {
335            list.add(TaggingPresets.getPresetValues(key), AutoCompletionPriority.IS_IN_STANDARD);
336            list.add(getDataValues(key), AutoCompletionPriority.IS_IN_DATASET);
337            list.addUserInput(getUserInputValues(key));
338        }
339    }
340
341    private static List<AutoCompletionItem> setToList(AutoCompletionSet set, Comparator<AutoCompletionItem> comparator) {
342        List<AutoCompletionItem> list = new ArrayList<>(set);
343        list.sort(comparator);
344        return list;
345    }
346
347    /**
348     * Returns all cached {@link AutoCompletionItem}s for given keys.
349     *
350     * @param keys retrieve the items for these keys
351     * @return the currently cached items, sorted by priority and alphabet
352     * @since 18221
353     */
354    public List<AutoCompletionItem> getAllForKeys(List<String> keys) {
355        Map<String, AutoCompletionPriority> map = new HashMap<>();
356
357        for (String key : keys) {
358            for (String value : TaggingPresets.getPresetValues(key)) {
359                map.merge(value, AutoCompletionPriority.IS_IN_STANDARD, AutoCompletionPriority::mergeWith);
360            }
361            for (String value : getDataValues(key)) {
362                map.merge(value, AutoCompletionPriority.IS_IN_DATASET, AutoCompletionPriority::mergeWith);
363            }
364            for (String value : getUserInputValues(key)) {
365                map.merge(value, AutoCompletionPriority.UNKNOWN, AutoCompletionPriority::mergeWith);
366            }
367        }
368        return map.entrySet().stream().map(e -> new AutoCompletionItem(e.getKey(), e.getValue())).sorted().collect(Collectors.toList());
369    }
370
371    /**
372     * Returns the currently cached tag keys.
373     * @return a set of tag keys
374     * @since 12859
375     */
376    public AutoCompletionSet getTagKeys() {
377        AutoCompletionList list = new AutoCompletionList();
378        populateWithKeys(list);
379        return list.getSet();
380    }
381
382    /**
383     * Returns the currently cached tag keys.
384     * @param comparator the custom comparator used to sort the list
385     * @return a list of tag keys
386     * @since 12859
387     */
388    public List<AutoCompletionItem> getTagKeys(Comparator<AutoCompletionItem> comparator) {
389        return setToList(getTagKeys(), comparator);
390    }
391
392    /**
393     * Returns the currently cached tag values for a given tag key.
394     * @param key the tag key
395     * @return a set of tag values
396     * @since 12859
397     */
398    public AutoCompletionSet getTagValues(String key) {
399        return getTagValues(Arrays.asList(key));
400    }
401
402    /**
403     * Returns the currently cached tag values for a given tag key.
404     * @param key the tag key
405     * @param comparator the custom comparator used to sort the list
406     * @return a list of tag values
407     * @since 12859
408     */
409    public List<AutoCompletionItem> getTagValues(String key, Comparator<AutoCompletionItem> comparator) {
410        return setToList(getTagValues(key), comparator);
411    }
412
413    /**
414     * Returns the currently cached tag values for a given list of tag keys.
415     * @param keys the tag keys
416     * @return a set of tag values
417     * @since 12859
418     */
419    public AutoCompletionSet getTagValues(List<String> keys) {
420        AutoCompletionList list = new AutoCompletionList();
421        populateWithTagValues(list, keys);
422        return list.getSet();
423    }
424
425    /**
426     * Returns the currently cached tag values for a given list of tag keys.
427     * @param keys the tag keys
428     * @param comparator the custom comparator used to sort the list
429     * @return a set of tag values
430     * @since 12859
431     */
432    public List<AutoCompletionItem> getTagValues(List<String> keys, Comparator<AutoCompletionItem> comparator) {
433        return setToList(getTagValues(keys), comparator);
434    }
435
436    /*
437     * Implementation of the DataSetListener interface
438     *
439     */
440
441    @Override
442    public void primitivesAdded(PrimitivesAddedEvent event) {
443        if (dirty)
444            return;
445        cachePrimitives(event.getPrimitives());
446    }
447
448    @Override
449    public void primitivesRemoved(PrimitivesRemovedEvent event) {
450        dirty = true;
451    }
452
453    @Override
454    public void tagsChanged(TagsChangedEvent event) {
455        if (dirty)
456            return;
457        Map<String, String> newKeys = event.getPrimitive().getKeys();
458        Map<String, String> oldKeys = event.getOriginalKeys();
459
460        if (!newKeys.keySet().containsAll(oldKeys.keySet())) {
461            // Some keys removed, might be the last instance of key, rebuild necessary
462            dirty = true;
463        } else {
464            for (Entry<String, String> oldEntry: oldKeys.entrySet()) {
465                if (!oldEntry.getValue().equals(newKeys.get(oldEntry.getKey()))) {
466                    // Value changed, might be last instance of value, rebuild necessary
467                    dirty = true;
468                    return;
469                }
470            }
471            cachePrimitives(Collections.singleton(event.getPrimitive()));
472        }
473    }
474
475    @Override
476    public void nodeMoved(NodeMovedEvent event) {/* ignored */}
477
478    @Override
479    public void wayNodesChanged(WayNodesChangedEvent event) {/* ignored */}
480
481    @Override
482    public void relationMembersChanged(RelationMembersChangedEvent event) {
483        dirty = true; // TODO: not necessary to rebuild if a member is added
484    }
485
486    @Override
487    public void otherDatasetChange(AbstractDatasetChangedEvent event) {/* ignored */}
488
489    @Override
490    public void dataChanged(DataChangedEvent event) {
491        dirty = true;
492    }
493
494    private AutoCompletionManager registerListeners() {
495        ds.addDataSetListener(this);
496        MainApplication.getLayerManager().addLayerChangeListener(new LayerChangeListener() {
497            @Override
498            public void layerRemoving(LayerRemoveEvent e) {
499                if (e.getRemovedLayer() instanceof OsmDataLayer
500                        && ((OsmDataLayer) e.getRemovedLayer()).data == ds) {
501                    INSTANCES.remove(ds);
502                    ds.removeDataSetListener(AutoCompletionManager.this);
503                    MainApplication.getLayerManager().removeLayerChangeListener(this);
504                    dirty = true;
505                    tagCache = null;
506                    roleCache = null;
507                    ds = null;
508                }
509            }
510
511            @Override
512            public void layerOrderChanged(LayerOrderChangeEvent e) {
513                // Do nothing
514            }
515
516            @Override
517            public void layerAdded(LayerAddEvent e) {
518                // Do nothing
519            }
520        });
521        return this;
522    }
523
524    /**
525     * Returns the {@code AutoCompletionManager} for the given data set.
526     * @param dataSet the data set
527     * @return the {@code AutoCompletionManager} for the given data set
528     * @since 12758
529     */
530    public static AutoCompletionManager of(DataSet dataSet) {
531        return INSTANCES.computeIfAbsent(dataSet, ds -> new AutoCompletionManager(ds).registerListeners());
532    }
533}