githubmirror/brackets

src/language/HTMLDOMDiff.js
633 строки26 KB
Narciso Jaramillo
Start test branch for CodeMirror v4. Load it via require everywhere it's used.
15 ноя 2013, 00:57
15 ноя 2013, 00:579fc28ce
/*
 * Copyright (c) 2013 Adobe Systems Incorporated. All rights reserved.
 *  
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"), 
 * to deal in the Software without restriction, including without limitation 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
 * and/or sell copies of the Software, and to permit persons to whom the 
 * Software is furnished to do so, subject to the following conditions:
 *  
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *  
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 * DEALINGS IN THE SOFTWARE.
 * 
 */


/*jslint vars: true, plusplus: true, devel: true, nomen: true, indent: 4, maxerr: 50 */
/*global define, $ */
/*unittests: HTML Instrumentation*/

define(function (require, exports, module) {
    "use strict";
    
    /**
     * @private
     *
     * Determines the changes made to attributes and generates edits for those changes.
     *
     * @param {SimpleNode} oldNode node from old tree
     * @param {SimpleNode} newNode node from new tree
     * @return {Array.<Object>} list of edits to mutate attributes from the old node to the new
     */
    function generateAttributeEdits(oldNode, newNode) {
        // shallow copy the old attributes object so that we can modify it
        var oldAttributes = $.extend({}, oldNode.attributes),
            newAttributes = newNode.attributes,
            edits = [];
        
        Object.keys(newAttributes).forEach(function (attributeName) {
            if (oldAttributes[attributeName] !== newAttributes[attributeName]) {
                var type = oldAttributes.hasOwnProperty(attributeName) ? "attrChange" : "attrAdd";
                edits.push({
                    type: type,
                    tagID: oldNode.tagID,
                    attribute: attributeName,
                    value: newAttributes[attributeName]
                });
            }
            delete oldAttributes[attributeName];
        });
        
        Object.keys(oldAttributes).forEach(function (attributeName) {
            edits.push({
                type: "attrDelete",
                tagID: oldNode.tagID,
                attribute: attributeName
            });
        });
        
        return edits;
    }
    
    /**
     * @private
     *
     * Retrieve the parent tag ID of a SimpleDOM node.
     *
     * @param {Object} node SimpleDOM node for which to look up parent ID
     * @return {int?} ID or null if there is no parent
     */
    function getParentID(node) {
        return node.parent && node.parent.tagID;
    }
    
    /**
     * @private
     *
     * When the main loop (see below) determines that something has changed with
     * an element's immediate children, it calls this function to create edit
     * operations for those changes.
     *
     * This adds to the edit list in place and does not return anything.
     *
     * @param {?Object} oldParent SimpleDOM node for the previous state of this element, null/undefined if the element is new
     * @param {Object} newParent SimpleDOM node for the current state of the element
     */
    var generateChildEdits = function (oldParent, oldNodeMap, newParent, newNodeMap) {
        /*jslint continue: true */
        
        var newIndex = 0,
            oldIndex = 0,
            newChildren = newParent.children,
            oldChildren = oldParent ? oldParent.children : [],
            newChild,
            oldChild,
            newEdits = [],
            newEdit,
            textAfterID,
            edits = [],
            moves = [],
            newElements = [];
        
        /**
         * We initially put new edit objects into the `newEdits` array so that we
         * can fix them up with proper positioning information. This function is
         * responsible for doing that fixup.
         *
         * The `beforeID` that appears in many edits tells the browser to make the
         * change before the element with the given ID. In other words, an
         * elementInsert with a `beforeID` of 32 would result in something like
         * `parentElement.insertBefore(newChildElement, _queryBracketsID(32))`
         *
         * Many new edits are captured in the `newEdits` array so that a suitable
         * `beforeID` can be added to them before they are added to the main edits
         * list. This function sets the `beforeID` on any pending edits and adds
         * them to the main list.
         *
         * If this item is not being deleted, then it will be used as the `afterID`
         * for text edits that follow.
         *
         * @param {int} beforeID ID to set on the pending edits
         * @param {boolean} isBeingDeleted true if the given item is being deleted. If so,
         *     we can't use it as the `afterID` for future edits--whatever previous item
         *     was set as the `textAfterID` is still okay.
         */
        var finalizeNewEdits = function (beforeID, isBeingDeleted) {
            newEdits.forEach(function (edit) {
                // elementDeletes don't need any positioning information
                if (edit.type !== "elementDelete") {
                    edit.beforeID = beforeID;
                }
            });
            edits.push.apply(edits, newEdits);
            newEdits = [];
            
            // If the item we made this set of edits relative to
            // is being deleted, we can't use it as the afterID for future
            // edits. It's okay to just keep the previous afterID, since
            // this node will no longer be in the tree by the time we get
            // to any future edit that needs an afterID.
            if (!isBeingDeleted) {
                textAfterID = beforeID;
            }
        };
        
        /**
         * If the current element was not in the old DOM, then we will create
         * an elementInsert edit for it.
         *
         * If the element was in the old DOM, this will return false and the
         * main loop will either spot this element later in the child list
         * or the element has been moved.
         *
         * @return {boolean} true if an elementInsert was created
         */
        var addElementInsert = function () {
            if (!oldNodeMap[newChild.tagID]) {
                newEdit = {
                    type: "elementInsert",
                    tag: newChild.tag,
                    tagID: newChild.tagID,
                    parentID: newChild.parent.tagID,
                    attributes: newChild.attributes
                };
                
                newEdits.push(newEdit);
                
                // This newly inserted node needs to have edits generated for its
                // children, so we add it to the queue.
                newElements.push(newChild);
                
                // A textInsert edit that follows this elementInsert should use
                // this element's ID.
                textAfterID = newChild.tagID;
                
                // new element means we need to move on to compare the next
                // of the current tree with the one from the old tree that we
                // just compared
                newIndex++;
                return true;
            }
            return false;
        };
        
        /**
         * If the old element that we're looking at does not appear in the new
         * DOM, that means it was deleted and we'll create an elementDelete edit.
         *
         * If the element is in the new DOM, then this will return false and
         * the main loop with either spot this node later on or the element
         * has been moved.
         *
         * @return {boolean} true if elementDelete was generated
         */
        var addElementDelete = function () {
            if (!newNodeMap[oldChild.tagID]) {
                // We can finalize existing edits relative to this node *before* it's
                // deleted.
                finalizeNewEdits(oldChild.tagID, true);
                
                newEdit = {
                    type: "elementDelete",
                    tagID: oldChild.tagID
                };
                newEdits.push(newEdit);
                
                // deleted element means we need to move on to compare the next
                // of the old tree with the one from the current tree that we
                // just compared
                oldIndex++;
                return true;
            }
            return false;
        };
        
        /**
         * Adds a textInsert edit for a newly created text node.
         */
        var addTextInsert = function () {
            newEdit = {
                type: "textInsert",
                content: newChild.content,
                parentID: newChild.parent.tagID
            };
            
            // text changes will generally have afterID and beforeID, but we make
            // special note if it's the first child.
            if (textAfterID) {
                newEdit.afterID = textAfterID;
            } else {
                newEdit.firstChild = true;
            }
            newEdits.push(newEdit);
            
            // The text node is in the new tree, so we move to the next new tree item
            newIndex++;
        };
        
        /**
         * Finds the previous child of the new tree.
         *
         * @return {?Object} previous child or null if there wasn't one
         */
        var prevNode = function () {
            if (newIndex > 0) {
                return newParent.children[newIndex - 1];
            }
            return null;
        };
        
        /**
         * Adds a textDelete edit for text node that is not in the new tree.
         * Note that we actually create a textReplace rather than a textDelete
         * if the previous node in current tree was a text node. We do this because
         * text nodes are not individually addressable and a delete event would
         * end up clearing out both that previous text node that we want to keep
         * and this text node that we want to eliminate. Instead, we just log
         * a textReplace which will result in the deletion of this node and
         * the maintaining of the old content.
         */
        var addTextDelete = function () {
            var prev = prevNode();
            if (prev && !prev.children) {
                newEdit = {
                    type: "textReplace",
                    content: prev.content
                };
            } else {
                newEdit = {
                    type: "textDelete"
                };
            }
            
            // When elements are deleted or moved from the old set of children, you
            // can end up with multiple text nodes in a row. A single textReplace edit
            // will take care of those (and will contain all of the right content since
            // the text nodes between elements in the new DOM are merged together).
            // The check below looks to see if we're already in the process of adding
            // a textReplace edit following the same element.
            var previousEdit = newEdits.length > 0 && newEdits[newEdits.length - 1];
            if (previousEdit && previousEdit.type === "textReplace" &&
                    previousEdit.afterID === textAfterID) {
                oldIndex++;
                return;
            }
            
            newEdit.parentID = oldChild.parent.tagID;
            
            // If there was only one child previously, we just pass along
            // textDelete/textReplace with the parentID and the browser will
            // clear all of the children
            if (oldChild.parent.children.length === 1) {
                newEdits.push(newEdit);
            } else {
                if (textAfterID) {
                    newEdit.afterID = textAfterID;
                }
                newEdits.push(newEdit);
            }
            
            // This text appeared in the old tree but not the new one, so we
            // increment the old children counter.
            oldIndex++;
        };
        
        /**
         * Adds an elementMove edit if the parent has changed between the old and new trees. 
         * These are fairly infrequent and generally occur if you make a change across 
         * tag boundaries.
         *
         * @return {boolean} true if an elementMove was generated
         */
        var addElementMove = function () {
            
            // This check looks a little strange, but it suits what we're trying
            // to do: as we're walking through the children, a child node that has moved
            // from one parent to another will be found but would look like some kind
            // of insert. The check that we're doing here is looking up the current
            // child's ID in the *old* map and seeing if this child used to have a 
            // different parent.
            var possiblyMovedElement = oldNodeMap[newChild.tagID];
            if (possiblyMovedElement &&
                    newParent.tagID !== getParentID(possiblyMovedElement)) {
                newEdit = {
                    type: "elementMove",
                    tagID: newChild.tagID,
                    parentID: newChild.parent.tagID
                };
                moves.push(newEdit.tagID);
                newEdits.push(newEdit);
                
                // this element in the new tree was a move to this spot, so we can move
                // on to the next child in the new tree.
                newIndex++;
                return true;
            }
            return false;
        };
        
        /**
         * Looks to see if the element in the old tree has moved by checking its
         * current and former parents.
         *
         * @return {boolean} true if the element has moved
         */
        var hasMoved = function (oldChild) {
            var oldChildInNewTree = newNodeMap[oldChild.tagID];
            
            return oldChild.children && oldChildInNewTree && getParentID(oldChild) !== getParentID(oldChildInNewTree);
        };
        
        // Loop through the current and old children, comparing them one by one.
        while (newIndex < newChildren.length && oldIndex < oldChildren.length) {
            newChild = newChildren[newIndex];
            
            // Check to see if the currentChild has been reparented from somewhere 
            // else in the old tree
            if (newChild.children && addElementMove()) {
                continue;
            }
            
            oldChild = oldChildren[oldIndex];
            
            // Check to see if the oldChild has been moved to another parent.
            // If it has, we deal with it on the other side (see above)
            if (hasMoved(oldChild)) {
                oldIndex++;
                continue;
            }
            
            if (newChild.isElement() || oldChild.isElement()) {
                
                if (newChild.isElement() && oldChild.isText()) {
                    addTextDelete();
                    
                    // If this element is new, add it and move to the next child
                    // in the current tree. Otherwise, we'll compare this same
                    // current element with the next old element on the next pass
                    // through the loop.
                    addElementInsert();
                
                } else if (oldChild.isElement() && newChild.isText()) {
                    // If the old child has *not* been deleted, we assume that we've
                    // inserted some text and will still encounter the old node
                    if (!addElementDelete()) {
                        addTextInsert();
                    }
                
                // both children are elements
                } else {
                    if (newChild.tagID !== oldChild.tagID) {
                        
                        // First, check to see if we're deleting an element.
                        // If we are, get rid of that element and restart our comparison
                        // logic with the same element from the new tree and the next one
                        // from the old tree.
                        if (!addElementDelete()) {
                            // Since we're not deleting and these elements don't match up, we
                            // must have a new element. Add an elementInsert (and log a problem
                            // if no insert works.)
                            if (!addElementInsert()) {
                                console.error("HTML Instrumentation: This should not happen. Two elements have different tag IDs and there was no insert/delete. This generally means there was a reordering of elements.");
                                newIndex++;
                                oldIndex++;
                            }
                        }
                    
                    // There has been no change in the tag we're looking at.
                    } else {
                        // Since this element hasn't moved, it is a suitable "beforeID"
                        // for the edits we've logged.
                        finalizeNewEdits(oldChild.tagID, false);
                        newIndex++;
                        oldIndex++;
                    }
                }
            
            // We know we're comparing two texts. Just match up their signatures.
            } else {
                if (newChild.textSignature !== oldChild.textSignature) {
                    newEdit = {
                        type: "textReplace",
                        content: newChild.content,
                        parentID: newChild.parent.tagID
                    };
                    if (textAfterID) {
                        newEdit.afterID = textAfterID;
                    }
                    newEdits.push(newEdit);
                }
                
                // Either we've done a text replace or both sides matched. In either
                // case we're ready to move forward among both the old and new children.
                newIndex++;
                oldIndex++;
            }
        }
        
        // At this point, we've used up all of the children in at least one of the
        // two sets of children.
        
        /**
         * Take care of any remaining children in the old tree.
         */
        while (oldIndex < oldChildren.length) {
            oldChild = oldChildren[oldIndex];
            
            // Check for an element that has moved
            if (hasMoved(oldChild)) {
                // This element has moved, so we skip it on this side (the move
                // is handled on the new tree side).
                oldIndex++;
            
            // is this an element? if so, delete it
            } else if (oldChild.isElement()) {
                if (!addElementDelete()) {
                    console.error("HTML Instrumentation: failed to add elementDelete for remaining element in the original DOM. This should not happen.", oldChild);
                    oldIndex++;
                }
            
            // must be text. delete that.
            } else {
                addTextDelete();
            }
        }
        
        /**
         * Take care of the remaining children in the new tree.
         */
        while (newIndex < newChildren.length) {
            newChild = newChildren[newIndex];
            
            // Is this an element?
            if (newChild.isElement()) {
                
                // Look to see if the element has moved here.
                if (!addElementMove()) {
                    // Not a move, so we insert this element.
                    if (!addElementInsert()) {
                        console.error("HTML Instrumentation: failed to add elementInsert for remaining element in the updated DOM. This should not happen.");
                        newIndex++;
                    }
                }
            
            // not a new element, so it must be new text.
            } else {
                addTextInsert();
            }
        }
        
        /**
         * Finalize remaining edits. For inserts and moves, we can set the `lastChild`
         * flag and the browser can simply use `appendChild` to add these items.
         */
        newEdits.forEach(function (edit) {
            if (edit.type === "textInsert" || edit.type === "elementInsert" || edit.type === "elementMove") {
                edit.lastChild = true;
                delete edit.firstChild;
                delete edit.afterID;
            }
        });
        edits.push.apply(edits, newEdits);
        
        return {
            edits: edits,
            moves: moves,
            newElements: newElements
        };
    };

    /**
     * Generate a list of edits that will mutate oldNode to look like newNode.
     * Currently, there are the following possible edit operations:
     *
     * * elementInsert
     * * elementDelete
     * * elementMove
     * * textInsert
     * * textDelete
     * * textReplace
     * * attrDelete
     * * attrChange
     * * attrAdd
     * * rememberNodes (a special instruction that reflects the need to hang on to moved nodes)
     *
     * @param {Object} oldNode SimpleDOM node with the original content
     * @param {Object} newNode SimpleDOM node with the new content
     * @return {Array.{Object}} list of edit operations
     */
    function domdiff(oldNode, newNode) {
        var queue = [],
            edits = [],
            moves = [],
            newElement,
            oldElement,
            oldNodeMap = oldNode ? oldNode.nodeMap : {},
            newNodeMap = newNode.nodeMap;
        
        /**
         * Adds elements to the queue for generateChildEdits.
         * Only elements (and not text nodes) are added. New nodes (ones that aren't in the
         * old nodeMap), are not added here because they will be added when generateChildEdits
         * creates the elementInsert edit.
         */
        var queuePush = function (node) {
            if (node.children && oldNodeMap[node.tagID]) {
                queue.push(node);
            }
        };
        
        /**
         * Aggregates the child edits in the proper data structures.
         *
         * @param {Object} delta edits, moves and newElements to add
         */
        var addEdits = function (delta) {
            edits.push.apply(edits, delta.edits);
            moves.push.apply(moves, delta.moves);
            queue.push.apply(queue, delta.newElements);
        };
        
        // Start at the root of the current tree.
        queue.push(newNode);
        
        do {
            newElement = queue.pop();
            oldElement = oldNodeMap[newElement.tagID];
            
            // Do we need to compare elements?
            if (oldElement) {
                
                // Are attributes different?
                if (newElement.attributeSignature !== oldElement.attributeSignature) {
                    // generate attribute edits
                    edits.push.apply(edits, generateAttributeEdits(oldElement, newElement));
                }
                
                // Has there been a change to this node's immediate children?
                if (newElement.childSignature !== oldElement.childSignature) {
                    addEdits(generateChildEdits(oldElement, oldNodeMap, newElement, newNodeMap));
                }
                
                // If there's a change farther down in the tree, add the children to the queue.
                // If not, we can skip that whole subtree.
                if (newElement.subtreeSignature !== oldElement.subtreeSignature) {
                    newElement.children.forEach(queuePush);
                }
            
            // This is a new element, so go straight to generating child edits (which will
            // create the appropriate Insert edits).
            } else {
                // If this is the root (html) tag, we need to manufacture an insert for it here,
                // because it isn't the child of any other node. The browser-side code doesn't
                // care about parentage/positioning in this case, and will handle just setting the 
                // ID on the existing implied HTML tag in the browser without actually creating it.
                if (!newElement.parent) {
                    edits.push({
                        type: "elementInsert",
                        tag: newElement.tag,
                        tagID: newElement.tagID,
                        parentID: null,
                        attributes: newElement.attributes
                    });
                }
                
                addEdits(generateChildEdits(null, oldNodeMap, newElement, newNodeMap));
            }
        } while (queue.length);
        
        // Special handling for moves: add edits to the beginning of the list so that
        // moved nodes are set aside to ensure that they remain available at the time of their
        // move.
        if (moves.length > 0) {
            edits.unshift({
                type: "rememberNodes",
                tagIDs: moves
            });
        }
        
        return edits;
    }
    
    // Public API
    exports.domdiff = domdiff;
});