001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.io;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005import static org.openstreetmap.josm.tools.I18n.trn;
006
007import java.io.IOException;
008import java.io.InputStream;
009import java.net.HttpURLConnection;
010import java.util.ArrayList;
011import java.util.Collection;
012import java.util.Collections;
013import java.util.HashSet;
014import java.util.Iterator;
015import java.util.LinkedHashSet;
016import java.util.List;
017import java.util.Set;
018import java.util.concurrent.Callable;
019import java.util.concurrent.CompletionService;
020import java.util.concurrent.ExecutionException;
021import java.util.concurrent.ExecutorCompletionService;
022import java.util.concurrent.ExecutorService;
023import java.util.concurrent.Executors;
024import java.util.concurrent.Future;
025
026import org.openstreetmap.josm.Main;
027import org.openstreetmap.josm.data.osm.DataSet;
028import org.openstreetmap.josm.data.osm.DataSetMerger;
029import org.openstreetmap.josm.data.osm.Node;
030import org.openstreetmap.josm.data.osm.OsmPrimitive;
031import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
032import org.openstreetmap.josm.data.osm.PrimitiveId;
033import org.openstreetmap.josm.data.osm.Relation;
034import org.openstreetmap.josm.data.osm.RelationMember;
035import org.openstreetmap.josm.data.osm.SimplePrimitiveId;
036import org.openstreetmap.josm.data.osm.Way;
037import org.openstreetmap.josm.gui.preferences.server.OverpassServerPreference;
038import org.openstreetmap.josm.gui.progress.NullProgressMonitor;
039import org.openstreetmap.josm.gui.progress.ProgressMonitor;
040import org.openstreetmap.josm.tools.Utils;
041
042/**
043 * Retrieves a set of {@link OsmPrimitive}s from an OSM server using the so called
044 * Multi Fetch API.
045 *
046 * Usage:
047 * <pre>
048 *    MultiFetchServerObjectReader reader = MultiFetchServerObjectReader()
049 *         .append(2345,2334,4444)
050 *         .append(new Node(72343));
051 *    reader.parseOsm();
052 *    if (!reader.getMissingPrimitives().isEmpty()) {
053 *        Main.info("There are missing primitives: " + reader.getMissingPrimitives());
054 *    }
055 *    if (!reader.getSkippedWays().isEmpty()) {
056 *       Main.info("There are skipped ways: " + reader.getMissingPrimitives());
057 *    }
058 * </pre>
059 */
060public class MultiFetchServerObjectReader extends OsmServerReader {
061    /**
062     * the max. number of primitives retrieved in one step. Assuming IDs with 7 digits,
063     * this leads to a max. request URL of ~ 1600 Bytes ((7 digits +  1 Separator) * 200),
064     * which should be safe according to the
065     * <a href="http://www.boutell.com/newfaq/misc/urllength.html">WWW FAQ</a>.
066     */
067    private static final int MAX_IDS_PER_REQUEST = 200;
068
069    private final Set<Long> nodes;
070    private final Set<Long> ways;
071    private final Set<Long> relations;
072    private Set<PrimitiveId> missingPrimitives;
073    private final DataSet outputDataSet;
074
075    /**
076     * Constructs a {@code MultiFetchServerObjectReader}.
077     */
078    protected MultiFetchServerObjectReader() {
079        nodes = new LinkedHashSet<>();
080        ways = new LinkedHashSet<>();
081        relations = new LinkedHashSet<>();
082        this.outputDataSet = new DataSet();
083        this.missingPrimitives = new LinkedHashSet<>();
084    }
085
086    /**
087     * Creates a new instance of {@link MultiFetchServerObjectReader} or {@link MultiFetchOverpassObjectReader}
088     * depending on the {@link OverpassServerPreference#useForMultiFetch preference}.
089     *
090     * @return a new instance
091     * @since 9241
092     */
093    public static MultiFetchServerObjectReader create() {
094        return create(OverpassServerPreference.useForMultiFetch());
095    }
096
097    /**
098     * Creates a new instance of {@link MultiFetchServerObjectReader} or {@link MultiFetchOverpassObjectReader}
099     * depending on the {@code fromMirror} parameter.
100     *
101     * @param fromMirror {@code false} for {@link MultiFetchServerObjectReader}, {@code true} for {@link MultiFetchOverpassObjectReader}
102     * @return a new instance
103     * @since 9241
104     */
105    static MultiFetchServerObjectReader create(final boolean fromMirror) {
106        if (fromMirror) {
107            return new MultiFetchOverpassObjectReader();
108        } else {
109            return new MultiFetchServerObjectReader();
110        }
111    }
112
113    /**
114     * Remembers an {@link OsmPrimitive}'s id. The id will
115     * later be fetched as part of a Multi Get request.
116     *
117     * Ignore the id if it represents a new primitives.
118     *
119     * @param id  the id
120     */
121    protected void remember(PrimitiveId id) {
122        if (id.isNew()) return;
123        switch(id.getType()) {
124        case NODE: nodes.add(id.getUniqueId()); break;
125        case WAY: ways.add(id.getUniqueId()); break;
126        case RELATION: relations.add(id.getUniqueId()); break;
127        default: throw new AssertionError();
128        }
129    }
130
131    /**
132     * appends a {@link OsmPrimitive} id to the list of ids which will be fetched from the server.
133     *
134     * @param ds the {@link DataSet} to which the primitive belongs
135     * @param id the primitive id
136     * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
137     * {@link OsmPrimitiveType#RELATION RELATION}
138     * @return this
139     */
140    public MultiFetchServerObjectReader append(DataSet ds, long id, OsmPrimitiveType type) {
141        OsmPrimitive p = ds.getPrimitiveById(id, type);
142        switch(type) {
143        case NODE:
144            return appendNode((Node) p);
145        case WAY:
146            return appendWay((Way) p);
147        case RELATION:
148            return appendRelation((Relation) p);
149        }
150        return this;
151    }
152
153    /**
154     * appends a {@link Node} id to the list of ids which will be fetched from the server.
155     *
156     * @param node  the node (ignored, if null)
157     * @return this
158     */
159    public MultiFetchServerObjectReader appendNode(Node node) {
160        if (node == null) return this;
161        remember(node.getPrimitiveId());
162        return this;
163    }
164
165    /**
166     * appends a {@link Way} id and the list of ids of nodes the way refers to the list of ids which will be fetched from the server.
167     *
168     * @param way the way (ignored, if null)
169     * @return this
170     */
171    public MultiFetchServerObjectReader appendWay(Way way) {
172        if (way == null) return this;
173        if (way.isNew()) return this;
174        for (Node node: !recursesDown() ? way.getNodes() : Collections.<Node>emptyList()) {
175            if (!node.isNew()) {
176                remember(node.getPrimitiveId());
177            }
178        }
179        remember(way.getPrimitiveId());
180        return this;
181    }
182
183    /**
184     * appends a {@link Relation} id to the list of ids which will be fetched from the server.
185     *
186     * @param relation  the relation (ignored, if null)
187     * @return this
188     */
189    protected MultiFetchServerObjectReader appendRelation(Relation relation) {
190        if (relation == null) return this;
191        if (relation.isNew()) return this;
192        remember(relation.getPrimitiveId());
193        for (RelationMember member : !recursesDown() ? relation.getMembers() : Collections.<RelationMember>emptyList()) {
194            if (OsmPrimitiveType.from(member.getMember()).equals(OsmPrimitiveType.RELATION)) {
195                // avoid infinite recursion in case of cyclic dependencies in relations
196                //
197                if (relations.contains(member.getMember().getId())) {
198                    continue;
199                }
200            }
201            if (!member.getMember().isIncomplete()) {
202                append(member.getMember());
203            }
204        }
205        return this;
206    }
207
208    /**
209     * appends an {@link OsmPrimitive} to the list of ids which will be fetched from the server.
210     * @param primitive the primitive
211     * @return this
212     */
213    public MultiFetchServerObjectReader append(OsmPrimitive primitive) {
214        if (primitive != null) {
215            switch (OsmPrimitiveType.from(primitive)) {
216                case NODE: return appendNode((Node) primitive);
217                case WAY: return appendWay((Way) primitive);
218                case RELATION: return appendRelation((Relation) primitive);
219            }
220        }
221        return this;
222    }
223
224    /**
225     * appends a list of {@link OsmPrimitive} to the list of ids which will be fetched from the server.
226     *
227     * @param primitives  the list of primitives (ignored, if null)
228     * @return this
229     *
230     * @see #append(OsmPrimitive)
231     */
232    public MultiFetchServerObjectReader append(Collection<? extends OsmPrimitive> primitives) {
233        if (primitives == null) return this;
234        for (OsmPrimitive primitive : primitives) {
235            append(primitive);
236        }
237        return this;
238    }
239
240    /**
241     * extracts a subset of max {@link #MAX_IDS_PER_REQUEST} ids from <code>ids</code> and
242     * replies the subset. The extracted subset is removed from <code>ids</code>.
243     *
244     * @param ids a set of ids
245     * @return the subset of ids
246     */
247    protected Set<Long> extractIdPackage(Set<Long> ids) {
248        Set<Long> pkg = new HashSet<>();
249        if (ids.isEmpty())
250            return pkg;
251        if (ids.size() > MAX_IDS_PER_REQUEST) {
252            Iterator<Long> it = ids.iterator();
253            for (int i = 0; i < MAX_IDS_PER_REQUEST; i++) {
254                pkg.add(it.next());
255            }
256            ids.removeAll(pkg);
257        } else {
258            pkg.addAll(ids);
259            ids.clear();
260        }
261        return pkg;
262    }
263
264    /**
265     * builds the Multi Get request string for a set of ids and a given {@link OsmPrimitiveType}.
266     *
267     * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
268     * {@link OsmPrimitiveType#RELATION RELATION}
269     * @param idPackage  the package of ids
270     * @return the request string
271     */
272    protected String buildRequestString(final OsmPrimitiveType type, Set<Long> idPackage) {
273        return type.getAPIName() + "s?" + type.getAPIName() + "s=" + Utils.join(",", idPackage);
274    }
275
276    @Override
277    protected String getBaseUrl() {
278        return super.getBaseUrl();
279    }
280
281    protected void rememberNodesOfIncompleteWaysToLoad(DataSet from) {
282        for (Way w: from.getWays()) {
283            if (w.hasIncompleteNodes()) {
284                for (Node n: w.getNodes()) {
285                    if (n.isIncomplete()) {
286                        nodes.add(n.getId());
287                    }
288                }
289            }
290        }
291    }
292
293    /**
294     * merges the dataset <code>from</code> to {@link #outputDataSet}.
295     *
296     * @param from the other dataset
297     */
298    protected void merge(DataSet from) {
299        final DataSetMerger visitor = new DataSetMerger(outputDataSet, from);
300        visitor.merge();
301    }
302
303    /**
304     * fetches a set of ids of a given {@link OsmPrimitiveType} from the server
305     *
306     * @param ids the set of ids
307     * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
308     * {@link OsmPrimitiveType#RELATION RELATION}
309     * @param progressMonitor progress monitor
310     * @throws OsmTransferException if an error occurs while communicating with the API server
311     */
312    protected void fetchPrimitives(Set<Long> ids, OsmPrimitiveType type, ProgressMonitor progressMonitor) throws OsmTransferException {
313        String msg;
314        final String baseUrl = getBaseUrl();
315        switch (type) {
316            // CHECKSTYLE.OFF: SingleSpaceSeparator
317            case NODE:     msg = tr("Fetching a package of nodes from ''{0}''",     baseUrl); break;
318            case WAY:      msg = tr("Fetching a package of ways from ''{0}''",      baseUrl); break;
319            case RELATION: msg = tr("Fetching a package of relations from ''{0}''", baseUrl); break;
320            // CHECKSTYLE.ON: SingleSpaceSeparator
321            default: throw new AssertionError();
322        }
323        progressMonitor.setTicksCount(ids.size());
324        progressMonitor.setTicks(0);
325        // The complete set containing all primitives to fetch
326        Set<Long> toFetch = new HashSet<>(ids);
327        // Build a list of fetchers that will  download smaller sets containing only MAX_IDS_PER_REQUEST (200) primitives each.
328        // we will run up to MAX_DOWNLOAD_THREADS concurrent fetchers.
329        int threadsNumber = Main.pref.getInteger("osm.download.threads", OsmApi.MAX_DOWNLOAD_THREADS);
330        threadsNumber = Math.min(Math.max(threadsNumber, 1), OsmApi.MAX_DOWNLOAD_THREADS);
331        final ExecutorService exec = Executors.newFixedThreadPool(
332                threadsNumber, Utils.newThreadFactory(getClass() + "-%d", Thread.NORM_PRIORITY));
333        CompletionService<FetchResult> ecs = new ExecutorCompletionService<>(exec);
334        List<Future<FetchResult>> jobs = new ArrayList<>();
335        while (!toFetch.isEmpty()) {
336            jobs.add(ecs.submit(new Fetcher(type, extractIdPackage(toFetch), progressMonitor)));
337        }
338        // Run the fetchers
339        for (int i = 0; i < jobs.size() && !isCanceled(); i++) {
340            progressMonitor.subTask(msg + "... " + progressMonitor.getTicks() + '/' + progressMonitor.getTicksCount());
341            try {
342                FetchResult result = ecs.take().get();
343                if (result.missingPrimitives != null) {
344                    missingPrimitives.addAll(result.missingPrimitives);
345                }
346                if (result.dataSet != null && !isCanceled()) {
347                    rememberNodesOfIncompleteWaysToLoad(result.dataSet);
348                    merge(result.dataSet);
349                }
350            } catch (InterruptedException | ExecutionException e) {
351                Main.error(e);
352            }
353        }
354        exec.shutdown();
355        // Cancel requests if the user chose to
356        if (isCanceled()) {
357            for (Future<FetchResult> job : jobs) {
358                job.cancel(true);
359            }
360        }
361    }
362
363    /**
364     * invokes one or more Multi Gets to fetch the {@link OsmPrimitive}s and replies
365     * the dataset of retrieved primitives. Note that the dataset includes non visible primitives too!
366     * In contrast to a simple Get for a node, a way, or a relation, a Multi Get always replies
367     * the latest version of the primitive (if any), even if the primitive is not visible (i.e. if
368     * visible==false).
369     *
370     * Invoke {@link #getMissingPrimitives()} to get a list of primitives which have not been
371     * found on  the server (the server response code was 404)
372     *
373     * @return the parsed data
374     * @throws OsmTransferException if an error occurs while communicating with the API server
375     * @see #getMissingPrimitives()
376     *
377     */
378    @Override
379    public DataSet parseOsm(ProgressMonitor progressMonitor) throws OsmTransferException {
380        int n = nodes.size() + ways.size() + relations.size();
381        progressMonitor.beginTask(trn("Downloading {0} object from ''{1}''",
382                "Downloading {0} objects from ''{1}''", n, n, OsmApi.getOsmApi().getBaseUrl()));
383        try {
384            missingPrimitives = new HashSet<>();
385            if (isCanceled()) return null;
386            fetchPrimitives(ways, OsmPrimitiveType.WAY, progressMonitor);
387            if (isCanceled()) return null;
388            fetchPrimitives(nodes, OsmPrimitiveType.NODE, progressMonitor);
389            if (isCanceled()) return null;
390            fetchPrimitives(relations, OsmPrimitiveType.RELATION, progressMonitor);
391            if (outputDataSet != null) {
392                outputDataSet.deleteInvisible();
393            }
394            return outputDataSet;
395        } finally {
396            progressMonitor.finishTask();
397        }
398    }
399
400    /**
401     * replies the set of ids of all primitives for which a fetch request to the
402     * server was submitted but which are not available from the server (the server
403     * replied a return code of 404)
404     *
405     * @return the set of ids of missing primitives
406     */
407    public Set<PrimitiveId> getMissingPrimitives() {
408        return missingPrimitives;
409    }
410
411    /**
412     * Whether this reader fetches nodes when loading ways, or members when loading relations.
413     *
414     * @return {@code true} if the reader recurses down
415     */
416    protected boolean recursesDown() {
417        return false;
418    }
419
420    /**
421     * The class holding the results given by {@link Fetcher}.
422     * It is only a wrapper of the resulting {@link DataSet} and the collection of {@link PrimitiveId} that could not have been loaded.
423     */
424    protected static class FetchResult {
425
426        /**
427         * The resulting data set
428         */
429        public final DataSet dataSet;
430
431        /**
432         * The collection of primitive ids that could not have been loaded
433         */
434        public final Set<PrimitiveId> missingPrimitives;
435
436        /**
437         * Constructs a {@code FetchResult}
438         * @param dataSet The resulting data set
439         * @param missingPrimitives The collection of primitive ids that could not have been loaded
440         */
441        public FetchResult(DataSet dataSet, Set<PrimitiveId> missingPrimitives) {
442            this.dataSet = dataSet;
443            this.missingPrimitives = missingPrimitives;
444        }
445    }
446
447    /**
448     * The class that actually download data from OSM API.
449     * Several instances of this class are used by {@link MultiFetchServerObjectReader} (one per set of primitives to fetch).
450     * The inheritance of {@link OsmServerReader} is only explained by the need to have a distinct OSM connection by {@code Fetcher} instance.
451     * @see FetchResult
452     */
453    protected class Fetcher extends OsmServerReader implements Callable<FetchResult> {
454
455        private final Set<Long> pkg;
456        private final OsmPrimitiveType type;
457        private final ProgressMonitor progressMonitor;
458
459        /**
460         * Constructs a {@code Fetcher}
461         * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
462         * {@link OsmPrimitiveType#RELATION RELATION}
463         * @param idsPackage The set of primitives ids to fetch
464         * @param progressMonitor The progress monitor
465         */
466        public Fetcher(OsmPrimitiveType type, Set<Long> idsPackage, ProgressMonitor progressMonitor) {
467            this.pkg = idsPackage;
468            this.type = type;
469            this.progressMonitor = progressMonitor;
470        }
471
472        @Override
473        public DataSet parseOsm(ProgressMonitor progressMonitor) throws OsmTransferException {
474            // This method is implemented because of the OsmServerReader inheritance, but not used,
475            // as the main target of this class is the call() method.
476            return fetch(progressMonitor).dataSet;
477        }
478
479        @Override
480        public FetchResult call() throws Exception {
481            return fetch(progressMonitor);
482        }
483
484        /**
485         * fetches the requested primitives and updates the specified progress monitor.
486         * @param progressMonitor the progress monitor
487         * @return the {@link FetchResult} of this operation
488         * @throws OsmTransferException if an error occurs while communicating with the API server
489         */
490        protected FetchResult fetch(ProgressMonitor progressMonitor) throws OsmTransferException {
491            try {
492                return multiGetIdPackage(type, pkg, progressMonitor);
493            } catch (OsmApiException e) {
494                if (e.getResponseCode() == HttpURLConnection.HTTP_NOT_FOUND) {
495                    Main.info(tr("Server replied with response code 404, retrying with an individual request for each object."));
496                    return singleGetIdPackage(type, pkg, progressMonitor);
497                } else {
498                    throw e;
499                }
500            }
501        }
502
503        @Override
504        protected String getBaseUrl() {
505            return MultiFetchServerObjectReader.this.getBaseUrl();
506        }
507
508        /**
509         * invokes a Multi Get for a set of ids and a given {@link OsmPrimitiveType}.
510         * The retrieved primitives are merged to {@link #outputDataSet}.
511         *
512         * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
513         * {@link OsmPrimitiveType#RELATION RELATION}
514         * @param pkg the package of ids
515         * @param progressMonitor progress monitor
516         * @return the {@link FetchResult} of this operation
517         * @throws OsmTransferException if an error occurs while communicating with the API server
518         */
519        protected FetchResult multiGetIdPackage(OsmPrimitiveType type, Set<Long> pkg, ProgressMonitor progressMonitor)
520                throws OsmTransferException {
521            String request = buildRequestString(type, pkg);
522            FetchResult result = null;
523            try (InputStream in = getInputStream(request, NullProgressMonitor.INSTANCE)) {
524                if (in == null) return null;
525                progressMonitor.subTask(tr("Downloading OSM data..."));
526                try {
527                    result = new FetchResult(OsmReader.parseDataSet(in, progressMonitor.createSubTaskMonitor(pkg.size(), false)), null);
528                } catch (IllegalDataException e) {
529                    throw new OsmTransferException(e);
530                }
531            } catch (IOException ex) {
532                Main.warn(ex);
533            }
534            return result;
535        }
536
537        /**
538         * invokes a Multi Get for a single id and a given {@link OsmPrimitiveType}.
539         * The retrieved primitive is merged to {@link #outputDataSet}.
540         *
541         * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
542         * {@link OsmPrimitiveType#RELATION RELATION}
543         * @param id the id
544         * @param progressMonitor progress monitor
545         * @return the {@link DataSet} resulting of this operation
546         * @throws OsmTransferException if an error occurs while communicating with the API server
547         */
548        protected DataSet singleGetId(OsmPrimitiveType type, long id, ProgressMonitor progressMonitor) throws OsmTransferException {
549            String request = buildRequestString(type, Collections.singleton(id));
550            DataSet result = null;
551            try (InputStream in = getInputStream(request, NullProgressMonitor.INSTANCE)) {
552                if (in == null) return null;
553                progressMonitor.subTask(tr("Downloading OSM data..."));
554                try {
555                    result = OsmReader.parseDataSet(in, progressMonitor.createSubTaskMonitor(1, false));
556                } catch (IllegalDataException e) {
557                    throw new OsmTransferException(e);
558                }
559            } catch (IOException ex) {
560                Main.warn(ex);
561            }
562            return result;
563        }
564
565        /**
566         * invokes a sequence of Multi Gets for individual ids in a set of ids and a given {@link OsmPrimitiveType}.
567         * The retrieved primitives are merged to {@link #outputDataSet}.
568         *
569         * This method is used if one of the ids in pkg doesn't exist (the server replies with return code 404).
570         * If the set is fetched with this method it is possible to find out which of the ids doesn't exist.
571         * Unfortunately, the server does not provide an error header or an error body for a 404 reply.
572         *
573         * @param type The primitive type. Must be one of {@link OsmPrimitiveType#NODE NODE}, {@link OsmPrimitiveType#WAY WAY},
574         * {@link OsmPrimitiveType#RELATION RELATION}
575         * @param pkg the set of ids
576         * @param progressMonitor progress monitor
577         * @return the {@link FetchResult} of this operation
578         * @throws OsmTransferException if an error occurs while communicating with the API server
579         */
580        protected FetchResult singleGetIdPackage(OsmPrimitiveType type, Set<Long> pkg, ProgressMonitor progressMonitor)
581                throws OsmTransferException {
582            FetchResult result = new FetchResult(new DataSet(), new HashSet<PrimitiveId>());
583            String baseUrl = OsmApi.getOsmApi().getBaseUrl();
584            for (long id : pkg) {
585                try {
586                    String msg;
587                    switch (type) {
588                        // CHECKSTYLE.OFF: SingleSpaceSeparator
589                        case NODE:     msg = tr("Fetching node with id {0} from ''{1}''",     id, baseUrl); break;
590                        case WAY:      msg = tr("Fetching way with id {0} from ''{1}''",      id, baseUrl); break;
591                        case RELATION: msg = tr("Fetching relation with id {0} from ''{1}''", id, baseUrl); break;
592                        // CHECKSTYLE.ON: SingleSpaceSeparator
593                        default: throw new AssertionError();
594                    }
595                    progressMonitor.setCustomText(msg);
596                    result.dataSet.mergeFrom(singleGetId(type, id, progressMonitor));
597                } catch (OsmApiException e) {
598                    if (e.getResponseCode() == HttpURLConnection.HTTP_NOT_FOUND) {
599                        Main.info(tr("Server replied with response code 404 for id {0}. Skipping.", Long.toString(id)));
600                        result.missingPrimitives.add(new SimplePrimitiveId(id, type));
601                    } else {
602                        throw e;
603                    }
604                }
605            }
606            return result;
607        }
608    }
609}