modules/core/difference.js (201 lines of code) (raw):

import deepEqual from 'fast-deep-equal'; import { vecEqual } from '@id-sdk/math'; import { utilArrayDifference, utilArrayUnion, utilArrayUniq } from '@id-sdk/util'; /* iD.coreDifference represents the difference between two graphs. It knows how to calculate the set of entities that were created, modified, or deleted, and also contains the logic for recursively extending a difference to the complete set of entities that will require a redraw, taking into account child and parent relationships. */ export function coreDifference(base, head) { var _changes = {}; var _didChange = {}; // 'addition', 'deletion', 'geometry', 'properties' var _diff = {}; function checkEntityID(id) { var h = head.entities[id]; var b = base.entities[id]; if (h === b) return; if (_changes[id]) return; if (!h && b) { _changes[id] = { base: b, head: h }; _didChange.deletion = true; return; } if (h && !b) { _changes[id] = { base: b, head: h }; _didChange.addition = true; return; } if (h && b) { if (h.members && b.members && !deepEqual(h.members, b.members)) { _changes[id] = { base: b, head: h }; _didChange.geometry = true; _didChange.properties = true; return; } if (h.loc && b.loc && !vecEqual(h.loc, b.loc)) { _changes[id] = { base: b, head: h }; _didChange.geometry = true; } if (h.nodes && b.nodes && !deepEqual(h.nodes, b.nodes)) { _changes[id] = { base: b, head: h }; _didChange.geometry = true; } if (h.tags && b.tags && !deepEqual(h.tags, b.tags)) { _changes[id] = { base: b, head: h }; _didChange.properties = true; } } } function load() { // HOT CODE: there can be many thousands of downloaded entities, so looping // through them all can become a performance bottleneck. Optimize by // resolving duplicates and using a basic `for` loop var ids = utilArrayUniq(Object.keys(head.entities).concat(Object.keys(base.entities))); for (var i = 0; i < ids.length; i++) { checkEntityID(ids[i]); } } load(); _diff.length = function length() { return Object.keys(_changes).length; }; _diff.changes = function changes() { return _changes; }; _diff.didChange = _didChange; // pass true to include affected relation members _diff.extantIDs = function extantIDs(includeRelMembers) { var result = new Set(); Object.keys(_changes).forEach(function(id) { if (_changes[id].head) { result.add(id); } var h = _changes[id].head; var b = _changes[id].base; var entity = h || b; if (includeRelMembers && entity.type === 'relation') { var mh = h ? h.members.map(function(m) { return m.id; }) : []; var mb = b ? b.members.map(function(m) { return m.id; }) : []; utilArrayUnion(mh, mb).forEach(function(memberID) { if (head.hasEntity(memberID)) { result.add(memberID); } }); } }); return Array.from(result); }; _diff.modified = function modified() { var result = []; Object.values(_changes).forEach(function(change) { if (change.base && change.head) { result.push(change.head); } }); return result; }; _diff.created = function created() { var result = []; Object.values(_changes).forEach(function(change) { if (!change.base && change.head) { result.push(change.head); } }); return result; }; _diff.deleted = function deleted() { var result = []; Object.values(_changes).forEach(function(change) { if (change.base && !change.head) { result.push(change.base); } }); return result; }; _diff.summary = function summary() { var relevant = {}; var keys = Object.keys(_changes); for (var i = 0; i < keys.length; i++) { var change = _changes[keys[i]]; if (change.head && change.head.geometry(head) !== 'vertex') { addEntity(change.head, head, change.base ? 'modified' : 'created'); } else if (change.base && change.base.geometry(base) !== 'vertex') { addEntity(change.base, base, 'deleted'); } else if (change.base && change.head) { // modified vertex var moved = !deepEqual(change.base.loc, change.head.loc); var retagged = !deepEqual(change.base.tags, change.head.tags); if (moved) { addParents(change.head); } if (retagged || (moved && change.head.hasInterestingTags())) { addEntity(change.head, head, 'modified'); } } else if (change.head && change.head.hasInterestingTags()) { // created vertex addEntity(change.head, head, 'created'); } else if (change.base && change.base.hasInterestingTags()) { // deleted vertex addEntity(change.base, base, 'deleted'); } } return Object.values(relevant); function addEntity(entity, graph, changeType) { relevant[entity.id] = { entity: entity, graph: graph, changeType: changeType }; } function addParents(entity) { var parents = head.parentWays(entity); for (var j = parents.length - 1; j >= 0; j--) { var parent = parents[j]; if (!(parent.id in relevant)) { addEntity(parent, head, 'modified'); } } } }; // returns complete set of entities that require a redraw // (optionally within given `extent`) _diff.complete = function complete(extent) { var result = {}; var id, change; for (id in _changes) { change = _changes[id]; var h = change.head; var b = change.base; var entity = h || b; var i; if (extent && (!h || !h.intersects(extent, head)) && (!b || !b.intersects(extent, base))) { continue; } result[id] = h; if (entity.type === 'way') { var nh = h ? h.nodes : []; var nb = b ? b.nodes : []; var diff; diff = utilArrayDifference(nh, nb); for (i = 0; i < diff.length; i++) { result[diff[i]] = head.hasEntity(diff[i]); } diff = utilArrayDifference(nb, nh); for (i = 0; i < diff.length; i++) { result[diff[i]] = head.hasEntity(diff[i]); } } if (entity.type === 'relation' && entity.isMultipolygon()) { var mh = h ? h.members.map(function(m) { return m.id; }) : []; var mb = b ? b.members.map(function(m) { return m.id; }) : []; var ids = utilArrayUnion(mh, mb); for (i = 0; i < ids.length; i++) { var member = head.hasEntity(ids[i]); if (!member) continue; // not downloaded if (extent && !member.intersects(extent, head)) continue; // not visible result[ids[i]] = member; } } addParents(head.parentWays(entity), result); addParents(head.parentRelations(entity), result); } return result; function addParents(parents, result) { for (var i = 0; i < parents.length; i++) { var parent = parents[i]; if (parent.id in result) continue; result[parent.id] = parent; addParents(head.parentRelations(parent), result); } } }; return _diff; }