 /*
 Copyright 2007-2010 Xmarks Inc.

 foxmarks-core.js: implements core sync & merge algorithms. 

 */

function EnumerateDeletedNodes(cs, baseline, current) {
    // Given a delete command, determine which of its desecendant nodes
    // were actually deleted, and attach that list of nids.
    // Some children may have been moved prior to the delete, so they
    // would survive in the curernt nodeset. Those survivors are not
    // included in the attached list.

    
    var deleted = null;

    function EnumerateInternal(nid) {
        if (!current.Node(nid, false, true)) {
            deleted.push(nid);
        }
        var node = baseline.Node(nid);
        if (node.children) {
            node.children.forEach(function(nid) { EnumerateInternal(nid) } );
        }
    }

    cs.set.forEach(function(command) {
        if (command.action == 'delete') {
            command.deleted = [];
            deleted = command.deleted;
            EnumerateInternal(command.nid);
        }
    } );
}

function CleanDeletedNodes(cs) {
    cs.set.forEach(function(cmd) { 
        if (cmd.action == 'delete') {
            delete cmd.deleted;
        }
        delete cmd.fixed;
    } );
}


// Syncd is a bit protective of its semantics. If we generated a move that
// doesn't actually change the node's parent, downgrade it to a reorder.

function CleanServerMoves(cs, ns) {
    cs.set.forEach(function(cmd) {
        if (cmd.action == 'move' && cmd.args.pnid == ns.Node(cmd.nid).pnid) {
            cmd.action = 'reorder';
            delete cmd.args.pnid;
        }
    })
}

function CombinePrePost(cs) {
    cs.set = cs.pre.concat(cs.set).concat(cs.post);
    delete cs.pre;
    delete cs.post;
}

function OpenConflictDialog(url, input) {
    // find a browser window to use as a parent for openDialog
    var wm = Cc['@mozilla.org/appshell/window-mediator;1'].getService();
    var wmi = wm.QueryInterface(Ci.nsIWindowMediator);
    var top = wmi.getMostRecentWindow("foxmarks:progress");

    // If we can't find one of our own windows, try any window.
    if (!top) {
        top = wmi.getMostRecentWindow(null);
        if (!top) {
            // We couldn't find a window, so pretend user canceled.
            return null;
        }
    }

    var output = {};
    Xmarks.ModalDialog(function() top.openDialog(
            url, "_blank", "chrome,dialog,modal,centerscreen", output, input));
    return output.selection;
}



var DETECTORS = {

    // Format for naming of these detectors is localaction_serveraction.

    insert_insert: function(local, server, localNS, serverNS) {
        if (local.nid == server.nid) {  // items created with same nid. Scary!
            var conflict = [];

            forEach(local.args, function(value, attr) {
                if (server.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
                        value != server.args[attr] && (attr != 'tags' ||
                        !tagEquals(server.args[attr], value))) {
                    conflict.push(attr + ":" + value);
                }
            } );

            forEach(server.args, function(value, attr) {
                if (local.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
                        value != local.args[attr] && (attr != 'tags' ||
                        !tagEquals(local.args[attr], value))) {
                    conflict.push(attr + ":" + value);
                }
            } );

            if (conflict.length) {
                var lnode = localNS.Node(local.nid);
                var snode = serverNS.Node(server.nid);
                var rv = localNS.handleNidConflict(lnode, snode, conflict);

                showedUI = true;

                if (rv == "local") {
                    return ["overwrite", "local"];
                } else if (rv == "server") {
                    return ["overwrite", "server"];
                } else if (rv == "same") {
                    return ["drop", "both"];
                } else {
                    throw 2;
                }
            } else {
                return ["drop", "both"];
            }
        }
        if (local.args.pnid == server.args.pnid &&
                local.args.bnid == server.args.bnid) {
            return ["transit", "server"];
        }
        return null;
    },

    insert_move: function(local, server) {
        if (local.args.pnid != server.args.pnid &&
            local.args.bnid == server.nid) {
            return ["nextsib", "left"];
        }
        if (local.nid != server.nid &&
                local.args.pnid == server.args.pnid &&
                local.args.bnid == server.args.bnid) {
                return ["transit", "server"];
        }
        return null;
    },

    insert_reorder: function(local, server, lns, sns) {
        if (local.args.pnid == sns.Node(server.nid).pnid &&
                local.args.bnid == server.args.bnid && !server.fixed) {
            return ["transit", "server"]; 
        }
        if (local.args.pnid == sns.Node(server.nid).pnid &&
                local.args.bnid == server.nid && !server.fixed) {
            return ["nextsib", "left"];
        }
        return null;
    },

    insert_update: function(local, server) {
        return null;
    },

    delete_insert: function(local, server) {
        if (local.deleted.indexOf(server.args.bnid) >= 0) {
            return ["nextsib", "right"];
        }
        if (local.deleted.indexOf(server.args.pnid) >= 0) {
            return ["delinsert", "left"];
        }
        return null;
    },
            
    delete_delete: function(local, server) {
        if (local.nid == server.nid) {
            return ["drop", "both"];
        }
        if (local.deleted.indexOf(server.nid) >= 0) {
            return ["drop", "right"];
        }

        if (server.deleted.indexOf(local.nid) >= 0) {
            return ["drop", "left"];
        }

        return null;
    },

    delete_move: function(local, server) {
        if (local.deleted.indexOf(server.args.bnid) >= 0) {
            return ["nextsib", "right"];
        }
        if (local.deleted.indexOf(server.nid) >= 0) {
            return ["delmoveout", "left"];
        }
        if (local.deleted.indexOf(server.args.pnid) >= 0) {
            return ["delmovein", "left"];
        }
        return null;
    },

    delete_reorder: function(local, server) {
        if (local.deleted.indexOf(server.nid) >= 0) {
            return ["drop", "right"];
        }
        if (local.nid == server.args.bnid) {
            return ["nextsib", "right"];
        }
        return null;
    },

    delete_update: function(local, server) {
        if (local.deleted.indexOf(server.nid) >= 0) {
            // A modified node was deleted. If the modifications
            // were significant, we've got a real conflict. Otherwise,
            // drop the modification and proceed with the delete.
            for (var a in server.args) {
                if (server.args.hasOwnProperty(a) &&
                        !DETECTORS.HARMLESS_ATTRS[a]) {
                    return ["delupdate", "left"];
                }
            }
            // The update was insignificant; drop it.
            return ["drop", "right"];
        }
        return null;
    },

    move_move: function(local, server, localNS, serverNS) {
        if (local.args.pnid == server.args.pnid) {
            if (local.nid == server.nid) {
                if (local.args.bnid == server.args.bnid) {
                    return ["drop", "both"];
                } else {
                    return ["drop", "server"];
                }
            } else {
                if (local.args.bnid == server.args.bnid) {
                    return ["transit", "server"];
                }
            }
        } else {
            if (local.nid == server.nid) {
                var input = { item: localNS.Node(local.nid),
                    local: localNS.Node(local.args.pnid),
                    server: serverNS.Node(server.args.pnid) };
                var rv = OpenConflictDialog(
                    "chrome://foxmarks/content/foxmarks-parentconflict.xul",
                    input);
                showedUI = true;

                if (rv == "local") {
                    return ["drop", "server"];
                } else if (rv == "server") {
                    return ["drop", "local"];
                } else {
                    throw 2;
                }
            } else {
                if (local.nid == server.args.bnid) {
                    return ["nextsib", "right"];
                } else if (local.args.bnid == server.nid) {
                    return ["nextsib", "left"];
                }
            }
        }

        return null;
    },

    move_reorder: function(local, server, lns, sns) {
        if (local.nid == server.nid) {
            return ["drop", "right"];
        }
        if (local.nid == server.args.bnid &&
                local.args.pnid != sns.Node(server.nid).pnid &&
                !server.fixed) {
            return ["nextsib", "right"];
        }
        if (local.args.pnid == sns.Node(server.nid).pnid &&
                local.args.bnid == server.args.bnid &&
                !server.fixed) {
            return ["transit", "server"];
        }
        return null;
    },

    move_update: function() {
        return null;
    },

    reorder_reorder: function(local, server, lns, sns) {
        if (lns.Node(local.nid).pnid != sns.Node(server.nid).pnid) {
            return null;
        }
        if (local.nid == server.nid) {
            if (local.args.bnid == server.args.bnid) {
                if (!local.fixed) {
                    return ["drop", "both"];
                } else {
                    return null;
                }
            } else {
                // XXX: Must retarget in this case
                return ["drop", "server"];
            }
        } else { // local.nid != server.nid
            if (local.nid == server.args.bnid && !server.fixed) {
                return ["commutereorder", "left"];
            } else if (local.args.bnid == server.nid && !local.fixed) {
                return ["commutereorder", "right"];
            } else if (local.args.bnid == server.args.bnid) {
                return ["transit", "local"];
            } else {
                return null;
            }
        }
    },

    reorder_update: function() {
        return null;
    },

    HARMLESS_ATTRS: { created: true, visited: true, modified: true, private: true, 
        icon: true },

    update_update: function(local, server, localNS, serverNS) {
        if (local.nid != server.nid)
            return;

        var conflicts = [];

        forEach(local.args, function(value, attr) {
            if (server.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
                    value != server.args[attr] && (attr != 'tags' ||
                    !tagEquals(value, server.args[attr]))) {
                conflicts.push(attr);
            }
        } );

        // Special case: tag-only conflict
        if (conflicts.length == 1 && conflicts[0] == 'tags') {
            return ["drop", "server"];
        }

        // Special case: conflict on (hidden attributes of) ROOT
        if (local.nid == NODE_ROOT) {
            return ["drop", "server"];
        }

        if (conflicts.length) {
            var lnode = localNS.Node(local.nid);
            var snode = serverNS.Node(server.nid);
            var rv = localNS.handleNidConflict(lnode, snode, conflicts);

            showedUI = true;
            if (rv == "local") {
                return ["drop", "server"];
            } else if (rv == "server") {
                return ["drop", "local"];
            } else if (rv == "same") {
                return ["drop", "both"];
            } else {
                throw 2;
            }
        } 
        return null;
    }
}



// Given a baseline nodeset, a local nodeset, and a server nodeset,
// generate two commandsets, one to be applied to the local nodeset,
// another to be applied to the server nodeset. Applying each commandset
// to the respective nodeset will result in the two nodsets becoming
// synchronized.
//
// Note that the routine operates asynchronously; the client-provided
// callback will be called with two parameters: localCS (the commandset
// to be applied to the server, and serverCS (the commandset to be applied
// to the local nodeset).

function Synchronize(baseline, localCS, serverCS, local, server, callback) {

    EnumerateDeletedNodes(localCS, baseline, local);
    EnumerateDeletedNodes(serverCS, baseline, server);

    localCS.pre = [];
    localCS.post = [];
    serverCS.pre = [];
    serverCS.post = [];

    // Iterate over each local commmand, comparing it with each
    // server command. Detect and resolve conflicts.

    var iterations = 0;
    var conflicts = {};
    var showedUI = false;

    for (var l = 0; l < localCS.set.length; ++l) {
        var lc = localCS.set[l];
        var result = null;
        var breakOut = false;

        for (var s = 0; s < serverCS.set.length; ++s) {

            sc = serverCS.set[s];

            var method = DETECTORS[lc.action + "_" + sc.action];
            if (method) {
                try {
                    result = method(lc, sc, local, server, false);
                } catch (e) {
                    Xmarks.LogWrite("Synchronize: failed processing " +
                        lc.toSource() + ", " + sc.toSource());
                    Xmarks.LogWrite("Error is " + e.toSource());
                    throw e;
                }
                if (!result)
                    continue;
                if (result[1] == 'left') result[1] = 'local';
                else if (result[1] == 'right') result[1] = 'server';
            } else {
                method = DETECTORS[sc.action + "_" + lc.action];
                if (!method) {
                    throw Error("Couldn't find conflict detector for " +
                            lc.action + " : " + sc.action);
                }
                try {
                    result = method(sc, lc, server, local, true);
                } catch (e) {
                    Xmarks.LogWrite("Synchronize: failed processing (reversed) " +
                        sc.toSource() + ", " + lc.toSource());
                    Xmarks.LogWrite("Error is " + e.toSource());
                    throw e;
                }
                if (!result)
                    continue;
                if (result[1] == 'left') result[1] = 'server';
                else if (result[1] == 'right') result[1] = 'local';
            }
           
            conflicts[result[0]] = (conflicts[result[0]] || 0) + 1;

            Xmarks.LogWrite(">>> Sync: Executing " + result[0] + "(" + result[1] + 
                    ") on " + lc.toSource() + " vs. " + sc.toSource());

            switch (result[0]) {
            case 'drop': do_drop(result[1]); break;
            case 'overwrite': do_overwrite(result[1]); break;
            case 'transit': do_transit(result[1]); break;
            case 'nextsib': do_nextsib(result[1]); break;
            case 'delinsert': do_delinsert(result[1]); break;
            case 'delmovein': do_delmovein(result[1]); break;
            case 'delmoveout': do_delmoveout(result[1]); break;
            case 'delupdate': do_delupdate(result[1]); break;
            case 'commutereorder': do_commutereorder(result[1]); break;
            default: throw Error("Unknown sync operator " + result[0]);
            }

            if (breakOut) {
                iterations += 1;
                if (iterations >= 1000) {
                    throw 1013;
                }
                break;
            }
        }
    }

    // We have resolved all conflicts in commands
    CleanDeletedNodes(localCS);
    CleanDeletedNodes(serverCS);
    CombinePrePost(localCS);
    CombinePrePost(serverCS);
    CleanServerMoves(localCS, server);

    callback(localCS, serverCS, conflicts, showedUI);
    return;

    function do_overwrite(arg) {
        switch (arg) {
        case 'local': 
            serverCS.drop(s); 
            s = s - 1;
            localCS.set[l].action = "update";
            localCS.set[l].args.bnid = undefined;
            localCS.set[l].args.pnid = undefined;
            break;
        case 'server': 
            localCS.drop(l); 
            l = l - 1;
            serverCS.set[s].action = "update";
            serverCS.set[s].args.bnid = undefined;
            serverCS.set[s].args.pnid = undefined;
            break;
        default: 
            throw Error("Unknown sync parameter " + result[1]);
        }
        return;
    }
    function do_drop(arg) {
        switch (arg) {
        case 'both': 
            localCS.drop(l);
            serverCS.drop(s);
            l = l - 1;
            breakOut = true;
            // bust out of inner loop; decrement l and start there
            break;
        case 'local': 
            localCS.drop(l); 
            l = l - 1;
            breakOut = true;
            // bust out of inner loop; decrement l and start there
            break;
        case 'server': 
            serverCS.drop(s); 
            s = s - 1;
            // decrement s and continue inner loop
            break;
        default: 
            throw Error("Unknown sync parameter " + result[1]);
        }
        return;
    }

    function do_transit(arg) {
        // A command specifies a bnid that is the target of another command.
        // So we take the bnid specified by the local or server command 
        // (depending on arg) and replace it with the nid of the other command.
        switch (arg) {
        case 'local': 
            lc.args.bnid = sc.nid; 
            lc.fixed = true;
            l = l - 1;
            breakOut = true;
            // restart inner loop
            break;
        case 'server': 
            sc.args.bnid = lc.nid; 
            sc.fixed = true;
            l = -1;
            breakOut = true;
            // restart outer loop
            break;
        default: 
            throw Error("Uknown sync parameter " + result[1]);
        }
        return;
    }

    function do_nextsib(arg) {
        switch (result[1]) {
        case 'local': 
            lc.args.bnid = local.NextSibling(lc.args.bnid, baseline); 
            l = l - 1;
            breakOut = true;
            // restart inner loop
            break;
        case 'server': 
            sc.args.bnid = server.NextSibling(sc.args.bnid, baseline);
            l = -1;
            breakOut = true;
            // restart outer loop
            break;
        default:
            throw Error("Unknown sync parameter " + result[1]);
        }
        return;
    }

    function do_delinsert(arg) {
        // arg is local or server, determining which side
        // originated the delete. The other side originated a
        // conflicting insert. The desired end result is for the inserted
        // node to be inserted into the nearest remaining ancestor of the
        // original pnid. This is accomplished by modifying the existing
        // insert command, changing its parent, and inserting a move command
        // to the side that originated the delete which moves the already
        // inserted node into the correct parent before performing the delete.
        // Finally, we add reorders to the post-sequence to make sure that
        // the inserted item ends up at the bottom of the folder.

        var del = null;
        var ins = null;
        var delCS = null;

        if (arg == "server") {
            del = sc;
            ins = lc;
            delCS = serverCS;
        } else {
            del = lc;
            ins = sc;
            delCS = localCS;
        }

        // What's the ultimate destination for the insert?
        var pnid = NearestAncestor(ins.args.pnid, baseline, local, server);

        // Alter the insert command so that it winds up in a safe home.
        ins.args.pnid = pnid;
        ins.args.bnid = null;

        // Move the inserted node aside before the delete
        delCS.pre.push(new Command("move", ins.nid, { pnid: pnid } ));

        // And now make sure it's add the end of the folder on both sides.
        var cmd = new Command("reorder", ins.nid, { bnid: null } );
        localCS.post.push(cmd);
        serverCS.post.push(cmd);

        // We've modified both commandsets; restart processing from the top.
        l = -1;
        breakOut = true;
        return;
    }

    function do_delmovein(arg) {
        // arg is local or server, determining which side
        // originated the delete. The other side originated a
        // conflicting move into the deleted subtree.
        // The desired end result is for the moved
        // node to be inserted into the nearest remaining ancestor of the
        // original pnid. This is accomplished by modifying the existing
        // move command, changing its parent, and inserting a move command
        // to the side that originated the delete which moves the already
        // inserted node into the correct parent before performing the delete.

        var del = null;
        var ins = null;
        var delCS = null;

        if (arg == "server") {
            del = sc;
            ins = lc;
            delCS = serverCS;
        } else {
            del = lc;
            ins = sc;
            delCS = localCS;
        }

        // What's the ultimate destination for the move?
        var pnid = NearestAncestor(ins.args.pnid, baseline, local, server);

        // Alter the move command so that it winds up in a safe home.
        ins.args.pnid = pnid;
        ins.args.bnid = null;

        // Move the inserted node aside before the delete
        delCS.pre.push(new Command("move", ins.nid, { pnid: pnid } ));

        // And now make sure it's add the end of the folder on both sides.
        var cmd = new Command("reorder", ins.nid, { bnid: null } );
        localCS.post.push(cmd);
        serverCS.post.push(cmd);

        // We've modified both commandsets; restart processing from the top.
        l = -1;
        breakOut = true;
        return;
    }

    function do_delupdate(arg) {
        // arg is local or server, determining which side
        // originated the delete. The other side originated a
        // conflicting update within the deleted subtree.
        // The desired end result is for the updated node and its
        // descendants to survive at the nearest remaining ancestor of the
        // original destination. This is accomplished by resurrecting the
        // modified node and its descendants and adding a move to the side
        // from which the delete originated which moves the item to its new
        // location.

        var update = null;
        var updateCS = null;
        var moveNS = null;
        var del = null;
        var delNS = null
        var delIndex = 0;
        var updateIndex = 0;

        if (arg == "server") {
            update = lc;
            updateCS = localCS;
            updateNS = local;
            del = sc;
            delNS = server;
            delCS = serverCS;
            delIndex = s;
            updateIndex = l;
        } else {
            update = sc;
            updateCS = serverCS;
            updateNS = server;
            del = lc;
            delNS = local;
            delCS = localCS;
            delIndex = l;
            updateIndex = s;
        }
        // Resurrect the deleted nodes
        ResurrectNodes(update, updateNS, updateCS, delNS, delCS);

        // We've modified both commandsets; restart processing from the top.
        l = -1;
        breakOut = true;
        return;
    }

    function do_delmoveout(arg) {
        // arg is local or server, determining which side
        // originated the delete. The other side originated a
        // conflicting move out of the deleted subtree.
        // The desired end result is for the moved
        // node to survive at the nearest remaining ancestor of the
        // original destination. This is accomplished by replacing the existing
        // move command with a (series of) insert(s) that resurrect the deleted
        // nodes(s) in their correct position. We let delinsert deal with the
        // case where the destination folder has also been deleted.

        var move = null;
        var moveCS = null;
        var moveIndex = null;
        var moveNS = null;
        var del = null;
        var delNS = null
        var delCS = null;
        var delIndex = 0;

        if (arg == "server") {
            move = lc;
            moveCS = localCS;
            moveIndex = l;
            moveNS = local;
            del = sc;
            delNS = server;
            delCS = serverCS;
            delIndex = s;
        } else {
            move = sc;
            moveCS = serverCS;
            moveIndex = s;
            moveNS = server;
            del = lc;
            delNS = local;
            delCS = localCS;
            delIndex = l;
        }

        // Resurrect the deleted nodes
        ResurrectNodes(move, moveNS, moveCS, delNS, delCS);

        // We've modified both commandsets; restart processing from the top.
        l = -1;
        breakOut = true;
        return;
    }

    function do_commutereorder(arg) {
        // We've encountered R(x,y) vs. R(y,z).
        // arg determines the side receiving the additional command R(x,y).
        // The resolution is to add R(x,y) as a simulated command
        // after R(y,z). We also mark the original R(x,y) as fixed
        // so we don't trigger again and so we don't drop it believing
        // that it's redundant. It would be nice to handle this in
        // the post-sequence, but, unfortunately, we need to get the
        // order straightened out before further moves and inserts happen.

        var c = arg == "local" ? sc : lc;
        var set = arg == "local" ? localCS.set : serverCS.set;
        var i = arg == "local" ? l : s;
        c.fixed = true;

        // Before we duplicate the command, we must ensure
        // that x (as above) still exists on the side which is to
        // receive the duplicate command.  If it's been deleted, 
        // we can drop the R(x,y), as x's position is irrelevant.
        // See #7379.
        var nodeset = arg == "local" ? local : server;
        if (nodeset.Node(c.nid, false, true) ==  null) {
            return do_drop(arg == "local" ? "server" : "local");
        }

        Xmarks.LogWrite("Duplicating command from " + arg + ": " + c.toSource());

        // This bit is tricky. Insert our copy of the command c in
        // the appropriate place in set. The appropriate place is the first
        // non-fixed spot after the current command.

        for ( i++; i < set.length; ++i) {
            if (!set[i].fixed)
                break;
        }

        set.splice(i, 0, c);
        l = -1;
        breakOut = true;
        return;
    }
}


function NearestAncestor(nid, baseline, ns1, ns2) {
    while (nid) {
        var node = baseline.Node(nid, false, true);
        if (!node) {
            throw Error("NearestAncestor failed accessing " + nid);
        }

        if (ns1.Node(nid, false, true) && ns2.Node(nid, false, true)) {
            return nid;
        }

        nid = node.pnid;
    }
    throw "Couldn't find a common ancestor!";
}

function NextSibling(nid, ns) {
    // Return the next sibling of nid within ns. Returns null if
    // the node in question can't be found, or if it has no next sibling.
    var node = ns.Node(nid, false, true);
    if (!node) return null;

    var parent = ns.Node(node.pnid, false, true);
    if (!parent) return null;

    var siblings = parent.children;
    if (!siblings) return null;

    var index = siblings.indexOf(nid);
    if (index < 0) return null;
    
    if (++index >= siblings.length) return null;

    return siblings[index];
}

function ResurrectNodes(sourceCommand, source, sourceCS, target, targetCS) {

    // Parameters we need:
    //  The source command, source, soureCS.
    //  The target command (the delete), the target nodeset, and the targetCS.


    // We're going to reanimate the dead, as it were. Our intention here
    // is to recreate the subtree from source rooted at nid. We accomplish
    // this by adding one or more inserts/moves into source's command set.
    //
    // We traverse the subtree, trying to find each node in the target nodeset.
    // If we find the node, we generate a move; if we don't find the node,
    // we generate an insert.
    //
    // If we generated an insert, we try to find an already-existing insert
    // in the source CS and drop it; failing that, we try to find a delete
    // within the targetCS that deleted the node and remove it from the list
    // of nids deleted by that node. In this last case, we also look for
    // and drop an update or reorder of this node, as these are now redundant.
    //
    // If we generated a move, then presumably the node still exists,
    // though within some other parent. The move that we generate here may
    // cause its own conflict, but that's okay -- the standard mechanisms
    // will resolve it.
    //
    // Finally, we want to build the commands that we insert locally,
    // inserting them all at the end to avoid the list moving around on us.

    Xmarks.LogWrite("Bring out 'cha dead: resurrecting " + 
            source.NodeName(sourceCommand.nid));
    
    var nids = [sourceCommand.nid];
    var commands = [];
    var sourceDrop = [];
    var targetDrop = [];
    var bnid = NextSibling(sourceCommand.nid, source);
    var first = bnid; // Starts as bnid or null, 
                      // gets set to null after first use.

    while (nids.length) {
        var nid = nids.shift();
        var sourceNode = source.Node(nid);

        // Does the node in question exist in the target?
        if (target.Node(nid, false, true)) {
            // Node still exists; move it into position.
            var attrs = { pnid: sourceNode.pnid };
            if (first) attrs.bnid = first;
            first = null;
            commands.push(new Command("move", nid, attrs));
        } else {
            // Node doesn't exist.
            var c = sourceCS.find("insert", nid);
            // Was node inserted by source?
            if (c) {
                // Yes: drop the insert (we'll recreate it later).
                sourceDrop.push(c);
            } else {
                // No: node must have been deleted in target.
                var c = targetCS.findDelete(nid);
                if (c) {
                    if (c.nid == nid) {
                        targetDrop.push(c);
                    } else {
                        var i = c.deleted.indexOf(nid);
                        if (i >= 0) {
                            c.deleted.splice(i, 1);
                        }
                    }
                }

                // We're going to get rid of updates, reorders, and moves
                // that might have happened on this node, as our insert
                // obviates the need for these changes: we insert into
                // the right parent, in the right position, with the correct
                // attributes.
                sourceDrop.push(sourceCS.find("update", nid));
                sourceDrop.push(sourceCS.find("reoder", nid));
                sourceDrop.push(sourceCS.find("move", nid));
            }

            var attrs = sourceNode.GetSafeAttrs();
            if (first) attrs.bnid = first;
            first = null;
            commands.push(new Command("insert", nid, attrs));
        }
    }

    // Now remove commands from each side that are superfluous.
    sourceDrop.forEach(function(c) {
            if (c) sourceCS.drop(c);
        });
    targetDrop.forEach(function(c) {
            if (c) targetCS.drop(c);
        });
    
    // Append our new commands at the end (but not the post-sequence,
    // as we may need to handle additional conflict resolution).
    commands.forEach(function(c) {
            sourceCS.append(c);
            Xmarks.LogWrite("Resurrect: Appending " + c.toSource());
        });

    // As a final cleanup, since our resurrection happens in the "right" folder
    // but not necessarily in the right position (we may not have found a bnid),
    // tack on a reorder of the root node to the target's post sequence.
    if (!bnid) {
        targetCS.post.push(
            new Command("reorder", sourceCommand.nid, { bnid: null }));
        Xmarks.LogWrite("Resurrect: Appended reorder of " + sourceCommand.nid);
    }
}
