Changeset 36230 in osm for applications/editors/josm/plugins

Timestamp:

2024-03-19T17:42:16+01:00 (8 months ago)

Author:

taylor.smock

Message:

reverter: Speed up reverting of large changesets where many objects have changed since the changeset was closed

This is done by using the OSM multi-fetch API to avoid doing a request per
version per object. Instead, we now do a bulk request for a series of versions
until we have all the information we need.

Additional performance enhancements include:

• Don't do string concatenation prior to logging call for Reverting {target} to {old version}
• reverter multi-fetch now queries 2k objects or 8k characters, whichever comes first
• Some locations which fire DataSet events are now wrapped in DataSet#update calls

Location:

applications/editors/josm/plugins/reverter/src/reverter

Files:

• ChangesetReverter.java (modified) (4 diffs)
• DataSetCommandMerger.java (modified) (4 diffs)
• OsmServerMultiObjectReader.java (modified) (3 diffs)
• RevertChangesetTask.java (modified) (2 diffs)

applications/editors/josm/plugins/reverter/src/reverter/ChangesetReverter.java

@@ -15 +15 @@
 import java.util.List;
 import java.util.Map;
+import java.util.Optional;
 import java.util.stream.Collectors;
 
@@ -22 +23 @@
 import org.openstreetmap.josm.data.conflict.Conflict;
 import org.openstreetmap.josm.data.coor.LatLon;
+import org.openstreetmap.josm.data.osm.AbstractPrimitive;
 import org.openstreetmap.josm.data.osm.Changeset;
 import org.openstreetmap.josm.data.osm.ChangesetDataSet;
@@ -273 +275 @@
             if (progressMonitor.isCanceled()) return;
             nds = rdr.parseOsm(progressMonitor.createSubTaskMonitor(1, true));
-            for (OsmPrimitive p : nds.allPrimitives()) {
-                if (!p.isIncomplete()) {
-                    addMissingId(p);
-                } else {
-                    if (ds.getPrimitiveById(p.getPrimitiveId()) == null) {
-                        switch (p.getType()) {
-                        case NODE: ds.addPrimitive(new Node(p.getUniqueId())); break;
-                        case CLOSEDWAY:
-                        case WAY: ds.addPrimitive(new Way(p.getUniqueId())); break;
-                        case MULTIPOLYGON:
-                        case RELATION: ds.addPrimitive(new Relation(p.getUniqueId())); break;
-                        default: throw new AssertionError();
+            ds.update(() -> {
+                for (OsmPrimitive p : nds.allPrimitives()) {
+                    if (!p.isIncomplete()) {
+                        addMissingId(p);
+                    } else {
+                        if (ds.getPrimitiveById(p.getPrimitiveId()) == null) {
+                            switch (p.getType()) {
+                            case NODE: ds.addPrimitive(new Node(p.getUniqueId())); break;
+                            case CLOSEDWAY:
+                            case WAY: ds.addPrimitive(new Way(p.getUniqueId())); break;
+                            case MULTIPOLYGON:
+                            case RELATION: ds.addPrimitive(new Relation(p.getUniqueId())); break;
+                            default: throw new AssertionError();
+                            }
                         }
                     }
                 }
-            }
+            });
         } finally {
             progressMonitor.finishTask();
@@ -503 +507 @@
         int num = nodes.size();
         progressMonitor.beginTask(addChangesetIdPrefix(
-                trn("Checking coordinates of {0} node", "Checking coordinates of {0} nodes", num, num)), num);
-
+                trn("Checking coordinates of {0} node", "Checking coordinates of {0} nodes", num, num)),
+                // downloads == num ticks, then we get the downloaded data (1 tick), then we process the nodes (num ticks)
+                2 * num + 1);
+
+        // Do bulk version fetches first
+        // The objects to get next
+        final Map<Long, Integer> versionMap = nodes.stream()
+                .collect(Collectors.toMap(AbstractPrimitive::getUniqueId,
+                        id -> Math.max(1, Optional.ofNullable(ds.getPrimitiveById(id)).orElse(id).getVersion() - 1)));
         try {
-            for (Node n : nodes) {
-                if (!n.isDeleted() && !n.isLatLonKnown()) {
-                    PrimitiveId id = n.getPrimitiveId();
-                    OsmPrimitive p = ds.getPrimitiveById(id);
-                    if (p instanceof Node && !((Node) p).isLatLonKnown()) {
-                        int version = p.getVersion();
-                        while (version > 1) {
-                            // find the version that was in use when the current changeset was closed
-                            --version;
-                            final OsmServerMultiObjectReader rdr = new OsmServerMultiObjectReader();
-                            readObjectVersion(rdr, id, version, progressMonitor);
-                            DataSet history = rdr.parseOsm(progressMonitor.createSubTaskMonitor(1, true));
-                            if (!history.isEmpty()) {
-                                Node historyNode = (Node) history.allPrimitives().iterator().next();
-                                if (historyNode.isLatLonKnown() && changeset.getClosedAt().isAfter(historyNode.getInstant())) {
-                                    n.load(historyNode.save());
-                                    break;
-                                }
+            while (!versionMap.isEmpty()) {
+                final OsmServerMultiObjectReader rds = new OsmServerMultiObjectReader();
+                final ProgressMonitor subMonitor = progressMonitor.createSubTaskMonitor(num, false);
+                subMonitor.beginTask(tr("Fetching multi-objects"), versionMap.size());
+                rds.readMultiObjects(OsmPrimitiveType.NODE, versionMap, subMonitor);
+                subMonitor.finishTask();
+                final DataSet history = rds.parseOsm(progressMonitor.createSubTaskMonitor(0, false));
+                versionMap.replaceAll((key, value) -> value - 1);
+                versionMap.values().removeIf(i -> i <= 0);
+                ds.update(() -> {
+                    for (Node n : nodes) {
+                        if (!n.isDeleted() && !n.isLatLonKnown()) {
+                            final Node historyNode = (Node) history.getPrimitiveById(n);
+                            if (historyNode != null && historyNode.isLatLonKnown()
+                                    && changeset.getClosedAt().isAfter(historyNode.getInstant())) {
+                                n.load(historyNode.save());
+                                versionMap.remove(n.getUniqueId());
+                                progressMonitor.worked(1);
                             }
                         }
+                        if (progressMonitor.isCanceled()) {
+                            break;
+                        }
                     }
+                });
+                if (progressMonitor.isCanceled()) {
+                    break;
                 }
-                if (progressMonitor.isCanceled())
-                    return;
-                progressMonitor.worked(1);
             }
         } finally {

applications/editors/josm/plugins/reverter/src/reverter/DataSetCommandMerger.java

@@ -7 +7 @@
 import java.util.Collection;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 import org.openstreetmap.josm.command.ChangeCommand;
@@ -38 +40 @@
     private final DataSet targetDataSet;
 
-    private final List<Command> cmds = new LinkedList<>();
-    private final List<OsmPrimitive> nominalRevertedPrimitives = new LinkedList<>();
+    private final List<Command> cmds = new ArrayList<>();
+    private final Set<OsmPrimitive> nominalRevertedPrimitives = new HashSet<>();
 
     /**
@@ -60 +62 @@
                 nominalRevertedPrimitives.add(target);
             }
-            Logging.debug("Reverting " + target + " to " + newTarget);
+            Logging.debug("Reverting {0} to {1}", target, newTarget);
         }
     }
@@ -126 +128 @@
             // Target node has been deleted by a more recent changeset -> conflict
             } else if (sourceNode.isIncomplete() && !conflicts.hasConflictForMy(targetNode)) {
-                localConflicts.add(new Conflict<OsmPrimitive>(targetNode, sourceNode, true));
+                localConflicts.add(new Conflict<>(targetNode, sourceNode, true));
             } else {
                Logging.info("Skipping target node "+targetNode+" for source node "+sourceNode+" while reverting way "+source);

applications/editors/josm/plugins/reverter/src/reverter/OsmServerMultiObjectReader.java

@@ -43 +43 @@
         }
     }
+
+    /**
+     * Generate query strings
+     * @param type The type of the object to get
+     * @param list The map of ids to versions
+     * @return The queries to make
+     */
     private static List<String> makeQueryStrings(OsmPrimitiveType type, Map<Long,Integer> list) {
-        List<String> result = new ArrayList<>((list.size()+maxQueryIds-1)/maxQueryIds);
+        // This is a "worst-case" calculation. Keep it fast (and err higher rather than lower), not accurate.
+        final int expectedSize = (int) (list.entrySet().stream().mapToLong(entry ->
+                // Keep in mind that 0-3 is 0, 3-32 is 1, 32-316 is 2, and so on when rounding log10.
+                // First the key.
+                Math.round(Math.log10(entry.getKey())) + 1 +
+                // Then the value
+                Math.round(Math.log10(entry.getValue())) + 1 +
+                // And finally the "static" size (',' + 'v')
+                2
+                ).sum() / MAX_QUERY_LENGTH);
+        List<String> result = new ArrayList<>(expectedSize + 1);
         StringBuilder sb = new StringBuilder();
         int cnt=0;
@@ -60 +77 @@
             sb.append(entry.getValue());
             cnt++;
-            if (cnt >=maxQueryIds) {
+            if (cnt >= MAX_QUERY_IDS || sb.length() > MAX_QUERY_LENGTH) {
                 result.add(sb.toString());
                 sb.setLength(0);
@@ -72 +89 @@
     }
 
-    protected static final int maxQueryIds = 128;
+    /**
+     * The maximum ids we want to query. API docs indicate 725 is "safe" for non-versioned objects with 10-digit ids.
+     * Since we use {@link #MAX_QUERY_LENGTH} to avoid issues where we go over the permitted length, we can have a
+     * bigger number here.
+     * @see <a href="https://wiki.openstreetmap.org/wiki/API_v0.6#Multi_fetch:_GET_/api/0.6/[nodes|ways|relations]?#parameters">
+     *     API_v0.6#Multi_fetch
+     * </a>
+     */
+    protected static final int MAX_QUERY_IDS = 2000;
+    /**
+     * The maximum query length. Docs indicate 8213 characters in the URI is safe. The maximum base length before
+     * query parameters is for relations at 59 characters for 8154 characters in the query parameters. We round down to
+     * 8000 characters.
+     * @see <a href="https://wiki.openstreetmap.org/wiki/API_v0.6#Multi_fetch:_GET_/api/0.6/[nodes|ways|relations]?#parameters">
+     *     API_v0.6#Multi_fetch
+     * </a>
+     */
+    protected static final int MAX_QUERY_LENGTH = 8000;
+
+    /**
+     * Parse many objects
+     * @param type The object type (<i>must</i> be common between all objects)
+     * @param list The map of object id to object version
+     * @param progressMonitor The progress monitor to update
+     * @throws OsmTransferException If there is an issue getting the data
+     */
     public void readMultiObjects(OsmPrimitiveType type, Map<Long,Integer> list, ProgressMonitor progressMonitor) throws OsmTransferException {
         for (String query : makeQueryStrings(type,list)) {

applications/editors/josm/plugins/reverter/src/reverter/RevertChangesetTask.java

@@ -191 +191 @@
             return null;
         }
-        GuiHelper.runInEDT(() -> {
+        GuiHelper.runInEDT(() -> cmds.get(0).getAffectedDataSet().update(() -> {
             for (Command c : cmds) {
                 if (c instanceof ConflictAddCommand) {
@@ -198 +198 @@
                 c.executeCommand();
             }
-        });
+        }));
         final String desc;
         if (revertType == RevertType.FULL) {