tools/winscope/src/utils/diff.js

/*
 * Copyright 2020, The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// TODO (b/162300507): Get rid of cloning
import ObjectFormatter from '../flickerlib/ObjectFormatter';

export const DiffType = Object.freeze({
  NONE: 'none',
  ADDED: 'added',
  DELETED: 'deleted',
  ADDED_MOVE: 'addedMove',
  DELETED_MOVE: 'deletedMove',
  MODIFIED: 'modified',
});

export function defaultModifiedCheck(newNode, oldNode) {
  if (!newNode && !oldNode) {
    return false;
  }

  if ((newNode && !oldNode) || (!newNode && oldNode)) {
    return true;
  }

  return !newNode.equals(oldNode);
}

export class DiffGenerator {
  constructor(tree) {
    this.tree = tree;
  }

  compareWith(tree) {
    this.diffWithTree = tree;
    return this;
  }

  withUniqueNodeId(getNodeId) {
    this.getNodeId = (node) => {
      const id = getNodeId(node);
      if (id === null || id === undefined) {
        console.error('Null node ID for node', node);
        throw new Error('Node ID can\'t be null or undefined');
      }
      return id;
    };
    return this;
  }

  withModifiedCheck(isModified) {
    this.isModified = isModified;
    return this;
  }

  generateDiffTree() {
    this.newMapping = this._generateIdToNodeMapping(this.tree);
    this.oldMapping = this.diffWithTree ?
      this._generateIdToNodeMapping(this.diffWithTree) : {};

    const diffTrees =
      this._generateDiffTree(this.tree, this.diffWithTree, [], []);

    let diffTree;
    if (diffTrees.length > 1) {
      diffTree = {
        kind: '',
        name: 'DiffTree',
        children: diffTrees,
        stableId: 'DiffTree',
      };
    } else {
      diffTree = diffTrees[0];
    }

    return Object.freeze(diffTree);
  }

  _generateIdToNodeMapping(node, acc) {
    acc = acc || {};

    const nodeId = this.getNodeId(node);

    if (acc[nodeId]) {
      throw new Error(`Duplicate node id '${nodeId}' detected...`);
    }

    acc[this.getNodeId(node)] = node;

    if (node.children) {
      for (const child of node.children) {
        this._generateIdToNodeMapping(child, acc);
      }
    }

    return acc;
  }

  _objIsEmpty(obj) {
    return Object.keys(obj).length === 0 && obj.constructor === Object;
  }

  _cloneNode(node) {
    const clone = ObjectFormatter.cloneObject(node);
    clone.children = node.children;
    clone.name = node.name;
    clone.kind = node.kind;
    clone.stableId = node.stableId;
    clone.shortName = node.shortName;
    if ('chips' in node) {
      clone.chips = node.chips.slice();
    }
    return clone;
  }

  _generateDiffTree(newTree, oldTree, newTreeSiblings, oldTreeSiblings) {
    const diffTrees = [];

    // NOTE: A null ID represents a non existent node.
    const newId = newTree ? this.getNodeId(newTree) : null;
    const oldId = oldTree ? this.getNodeId(oldTree) : null;

    const newTreeSiblingIds = newTreeSiblings.map(this.getNodeId);
    const oldTreeSiblingIds = oldTreeSiblings.map(this.getNodeId);

    if (newTree) {
      // Deep clone newTree omitting children field
      // Clone is required because trees are frozen objects — we can't
      // modify the original tree object. Also means there is no side effect.
      const diffTree = this._cloneNode(newTree);

      // Default to no changes
      diffTree.diff = {type: DiffType.NONE};

      if (newId !== oldId) {
        // A move, addition, or deletion has occurred
        let nextOldTree;

        // Check if newTree has been added or moved
        if (!oldTreeSiblingIds.includes(newId)) {
          if (this.oldMapping[newId]) {
            // Objected existed in old tree, the counter party
            // DELETED_MOVE will be/has been flagged and added to the
            // diffTree when visiting it in the oldTree.
            diffTree.diff = {type: DiffType.ADDED_MOVE};

            // TODO: Figure out if oldTree is ever visited now...

            // Switch out oldTree for new one to compare against
            nextOldTree = this.oldMapping[newId];
          } else {
            diffTree.diff = {type: DiffType.ADDED};

            // TODO: Figure out if oldTree is ever visited now...

            // Stop comparing against oldTree
            nextOldTree = null;
          }
        }

        // Check if oldTree has been deleted of moved
        if (oldTree && !newTreeSiblingIds.includes(oldId)) {
          const deletedTreeDiff = this._cloneNode(oldTree);

          if (this.newMapping[oldId]) {
            deletedTreeDiff.diff = {type: DiffType.DELETED_MOVE};

            // Stop comparing against oldTree, will be/has been
            // visited when object is seen in newTree
            nextOldTree = null;
          } else {
            deletedTreeDiff.diff = {type: DiffType.DELETED};

            // Visit all children to check if they have been deleted or moved
            deletedTreeDiff.children = this._visitChildren(null, oldTree);
          }

          diffTrees.push(deletedTreeDiff);
        }

        oldTree = nextOldTree;
      } else {
        // TODO: Always have modified check and add modified tags on top of
        // others
        // NOTE: Doesn't check for moved and modified at the same time
        if (this.isModified && this.isModified(newTree, oldTree)) {
          diffTree.diff = {type: DiffType.MODIFIED};
        }
      }

      diffTree.children = this._visitChildren(newTree, oldTree);
      diffTrees.push(diffTree);
    } else if (oldTree) {
      if (!newTreeSiblingIds.includes(oldId)) {
        // Deep clone oldTree omitting children field
        const diffTree = this._cloneNode(oldTree);

        // newTree doesn't exists, oldTree has either been moved or deleted.
        if (this.newMapping[oldId]) {
          diffTree.diff = {type: DiffType.DELETED_MOVE};
        } else {
          diffTree.diff = {type: DiffType.DELETED};
        }

        diffTree.children = this._visitChildren(null, oldTree);
        diffTrees.push(diffTree);
      }
    } else {
      throw new Error('Both newTree and oldTree are undefined...');
    }

    return diffTrees;
  }

  _visitChildren(newTree, oldTree) {
    // Recursively traverse all children of new and old tree.
    const diffChildren = [];

    // TODO: Try replacing this with some sort of zipWith.
    const numOfChildren = Math.max(
        newTree?.children?.length ?? 0, oldTree?.children?.length ?? 0);
    for (let i = 0; i < numOfChildren; i++) {
      const newChild = i < newTree?.children?.length ?
        newTree.children[i] : null;

      const oldChild = i < oldTree?.children?.length ?
        oldTree.children[i] : null;

      const childDiffTrees = this._generateDiffTree(
          newChild, oldChild,
          newTree?.children ?? [], oldTree?.children ?? [],
      );
      diffChildren.push(...childDiffTrees);
    }

    return diffChildren;
  }
}