Implement diff for SurfaceFlinger and WindowManager hierarchy
Test: N/A
Change-Id: I3dea4f29de74a8754cf3164d41c7eb3d76c239a8
diff --git a/tools/winscope/package.json b/tools/winscope/package.json
index 1076abd..57bfd1d 100644
--- a/tools/winscope/package.json
+++ b/tools/winscope/package.json
@@ -11,6 +11,7 @@
},
"dependencies": {
"jszip": "^3.5.0",
+ "lodash.clonedeep": "^4.5.0",
"vue": "^2.3.3",
"vue-material": "^1.0.0-beta-11",
"vuex": "^3.4.0"
@@ -35,4 +36,4 @@
"webpack": "^2.6.1",
"webpack-dev-server": "^2.4.5"
}
-}
+}
\ No newline at end of file
diff --git a/tools/winscope/src/TraceView.vue b/tools/winscope/src/TraceView.vue
index d35c455..13af2ab 100644
--- a/tools/winscope/src/TraceView.vue
+++ b/tools/winscope/src/TraceView.vue
@@ -65,6 +65,7 @@
import Rects from './Rects.vue'
import { ObjectTransformer } from './transform.js'
+import { DiffGenerator, defaultModifiedCheck } from './utils/diff.js'
import { format_transform_type, is_simple_transform } from './matrix_utils.js'
import { DATA_TYPES } from './decode.js'
import { stableIdCompatibilityFixup } from './utils/utils.js'
@@ -173,6 +174,28 @@
},
setData(item) {
this.tree = item;
+
+ // TODO: Add flag to toggle diffs or not
+ // TODO: Disable if proto are not the latest
+ if (true) {
+ // Required pre-processing to match algo
+ // TODO: Clean this up somehow
+ if (this.file.type == DATA_TYPES.SURFACE_FLINGER) {
+ item.obj.id = -1; // TODO: Make sure this ID can never be used by other objects
+ item.children[0].obj.id = 0;
+ }
+
+ this.tree = new DiffGenerator(item)
+ .compareWith(this.getDataWithOffset(-1))
+ .withUniqueNodeId(node => {
+ return node.stableId;
+ })
+ .withModifiedCheck(defaultModifiedCheck)
+ .generateDiffTree();
+ } else {
+ this.tree = item;
+ }
+
this.rects = [...item.rects].reverse();
this.bounds = item.bounds;
diff --git a/tools/winscope/src/TreeView.vue b/tools/winscope/src/TreeView.vue
index 5a0402b..76fb656 100644
--- a/tools/winscope/src/TreeView.vue
+++ b/tools/winscope/src/TreeView.vue
@@ -123,6 +123,7 @@
[DiffType.ADDED]: "+",
[DiffType.DELETED]: "-",
[DiffType.MODIFIED]: ".",
+ [DiffType.MOVED]: ".",
},
};
},
@@ -350,7 +351,7 @@
background: chartreuse;
}
-.tree-view .node:not(.selected).removed {
+.tree-view .node:not(.selected).deleted {
background: coral;
}
@@ -358,6 +359,11 @@
background: cyan;
}
+.tree-view .node:not(.selected).addedMove,
+.tree-view .node:not(.selected).deletedMove {
+ background: slateblue;
+}
+
.children {
/* Aligns border with collapse arrows */
margin-left: 12px;
diff --git a/tools/winscope/src/utils/diff.js b/tools/winscope/src/utils/diff.js
index 4482f03..9208e21 100644
--- a/tools/winscope/src/utils/diff.js
+++ b/tools/winscope/src/utils/diff.js
@@ -1,3 +1,5 @@
+import cloneDeep from 'lodash.clonedeep';
+
const DiffType = Object.freeze({
NONE: 'none',
ADDED: 'added',
@@ -7,4 +9,227 @@
MODIFIED: 'modified',
});
-export { DiffType };
\ No newline at end of file
+function defaultModifiedCheck(newNode, oldNode) {
+ if (!newNode && !oldNode) {
+ return false;
+ }
+
+ if ((newNode && !oldNode) || (!newNode && oldNode)) {
+ return true;
+ }
+
+ return JSON.stringify(newNode.obj) !== JSON.stringify(oldNode.obj);
+}
+
+function isPrimitive(test) {
+ return test !== Object(test);
+};
+
+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) {
+ 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,
+ };
+ } 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;
+ }
+
+ _cloneNodeWithoutChildren(node) {
+ const clone = {};
+
+ for (const key in node) {
+ if (key !== 'children') {
+ const val = node[key];
+ clone[key] = isPrimitive(val) ? val : cloneDeep(val);
+ }
+ }
+
+ 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._cloneNodeWithoutChildren(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._cloneNodeWithoutChildren(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._cloneNodeWithoutChildren(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;
+ }
+}
+
+export { DiffGenerator, DiffType, defaultModifiedCheck }
diff --git a/tools/winscope/yarn.lock b/tools/winscope/yarn.lock
index 9e7e040..924ebac 100644
--- a/tools/winscope/yarn.lock
+++ b/tools/winscope/yarn.lock
@@ -3502,6 +3502,11 @@
dependencies:
lodash._createcompounder "^3.0.0"
+lodash.clonedeep@^4.5.0:
+ version "4.5.0"
+ resolved "https://registry.yarnpkg.com/lodash.clonedeep/-/lodash.clonedeep-4.5.0.tgz#e23f3f9c4f8fbdde872529c1071857a086e5ccef"
+ integrity sha1-4j8/nE+Pvd6HJSnBBxhXoIblzO8=
+
lodash.deburr@^3.0.0:
version "3.2.0"
resolved "https://registry.yarnpkg.com/lodash.deburr/-/lodash.deburr-3.2.0.tgz#6da8f54334a366a7cf4c4c76ef8d80aa1b365ed5"
