1/*
2 * Copyright 2020, The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// TODO (b/162300507): Get rid of cloning
18import ObjectFormatter from '../flickerlib/ObjectFormatter';
19
20export const DiffType = Object.freeze({
21  NONE: 'none',
22  ADDED: 'added',
23  DELETED: 'deleted',
24  ADDED_MOVE: 'addedMove',
25  DELETED_MOVE: 'deletedMove',
26  MODIFIED: 'modified',
27});
28
29export function defaultModifiedCheck(newNode, oldNode) {
30  if (!newNode && !oldNode) {
31    return false;
32  }
33
34  if ((newNode && !oldNode) || (!newNode && oldNode)) {
35    return true;
36  }
37
38  return !newNode.equals(oldNode);
39}
40
41export class DiffGenerator {
42  constructor(tree) {
43    this.tree = tree;
44  }
45
46  compareWith(tree) {
47    this.diffWithTree = tree;
48    return this;
49  }
50
51  withUniqueNodeId(getNodeId) {
52    this.getNodeId = (node) => {
53      const id = getNodeId(node);
54      if (id === null || id === undefined) {
55        console.error('Null node ID for node', node);
56        throw new Error('Node ID can\'t be null or undefined');
57      }
58      return id;
59    };
60    return this;
61  }
62
63  withModifiedCheck(isModified) {
64    this.isModified = isModified;
65    return this;
66  }
67
68  generateDiffTree() {
69    this.newMapping = this._generateIdToNodeMapping(this.tree);
70    this.oldMapping = this.diffWithTree ?
71      this._generateIdToNodeMapping(this.diffWithTree) : {};
72
73    const diffTrees =
74      this._generateDiffTree(this.tree, this.diffWithTree, [], []);
75
76    let diffTree;
77    if (diffTrees.length > 1) {
78      diffTree = {
79        kind: '',
80        name: 'DiffTree',
81        children: diffTrees,
82        stableId: 'DiffTree',
83      };
84    } else {
85      diffTree = diffTrees[0];
86    }
87
88    return Object.freeze(diffTree);
89  }
90
91  _generateIdToNodeMapping(node, acc) {
92    acc = acc || {};
93
94    const nodeId = this.getNodeId(node);
95
96    if (acc[nodeId]) {
97      throw new Error(`Duplicate node id '${nodeId}' detected...`);
98    }
99
100    acc[this.getNodeId(node)] = node;
101
102    if (node.children) {
103      for (const child of node.children) {
104        this._generateIdToNodeMapping(child, acc);
105      }
106    }
107
108    return acc;
109  }
110
111  _objIsEmpty(obj) {
112    return Object.keys(obj).length === 0 && obj.constructor === Object;
113  }
114
115  _cloneNode(node) {
116    const clone = ObjectFormatter.cloneObject(node);
117    clone.children = node.children;
118    clone.name = node.name;
119    clone.kind = node.kind;
120    clone.stableId = node.stableId;
121    clone.shortName = node.shortName;
122    return clone;
123  }
124
125  _generateDiffTree(newTree, oldTree, newTreeSiblings, oldTreeSiblings) {
126    const diffTrees = [];
127
128    // NOTE: A null ID represents a non existent node.
129    const newId = newTree ? this.getNodeId(newTree) : null;
130    const oldId = oldTree ? this.getNodeId(oldTree) : null;
131
132    const newTreeSiblingIds = newTreeSiblings.map(this.getNodeId);
133    const oldTreeSiblingIds = oldTreeSiblings.map(this.getNodeId);
134
135    if (newTree) {
136      // Deep clone newTree omitting children field
137      // Clone is required because trees are frozen objects — we can't
138      // modify the original tree object. Also means there is no side effect.
139      const diffTree = this._cloneNode(newTree);
140
141      // Default to no changes
142      diffTree.diff = {type: DiffType.NONE};
143
144      if (newId !== oldId) {
145        // A move, addition, or deletion has occurred
146        let nextOldTree;
147
148        // Check if newTree has been added or moved
149        if (!oldTreeSiblingIds.includes(newId)) {
150          if (this.oldMapping[newId]) {
151            // Objected existed in old tree, the counter party
152            // DELETED_MOVE will be/has been flagged and added to the
153            // diffTree when visiting it in the oldTree.
154            diffTree.diff = {type: DiffType.ADDED_MOVE};
155
156            // TODO: Figure out if oldTree is ever visited now...
157
158            // Switch out oldTree for new one to compare against
159            nextOldTree = this.oldMapping[newId];
160          } else {
161            diffTree.diff = {type: DiffType.ADDED};
162
163            // TODO: Figure out if oldTree is ever visited now...
164
165            // Stop comparing against oldTree
166            nextOldTree = null;
167          }
168        }
169
170        // Check if oldTree has been deleted of moved
171        if (oldTree && !newTreeSiblingIds.includes(oldId)) {
172          const deletedTreeDiff = this._cloneNode(oldTree);
173
174          if (this.newMapping[oldId]) {
175            deletedTreeDiff.diff = {type: DiffType.DELETED_MOVE};
176
177            // Stop comparing against oldTree, will be/has been
178            // visited when object is seen in newTree
179            nextOldTree = null;
180          } else {
181            deletedTreeDiff.diff = {type: DiffType.DELETED};
182
183            // Visit all children to check if they have been deleted or moved
184            deletedTreeDiff.children = this._visitChildren(null, oldTree);
185          }
186
187          diffTrees.push(deletedTreeDiff);
188        }
189
190        oldTree = nextOldTree;
191      } else {
192        // TODO: Always have modified check and add modified tags on top of
193        // others
194        // NOTE: Doesn't check for moved and modified at the same time
195        if (this.isModified && this.isModified(newTree, oldTree)) {
196          diffTree.diff = {type: DiffType.MODIFIED};
197        }
198      }
199
200      diffTree.children = this._visitChildren(newTree, oldTree);
201      diffTrees.push(diffTree);
202    } else if (oldTree) {
203      if (!newTreeSiblingIds.includes(oldId)) {
204        // Deep clone oldTree omitting children field
205        const diffTree = this._cloneNode(oldTree);
206
207        // newTree doesn't exists, oldTree has either been moved or deleted.
208        if (this.newMapping[oldId]) {
209          diffTree.diff = {type: DiffType.DELETED_MOVE};
210        } else {
211          diffTree.diff = {type: DiffType.DELETED};
212        }
213
214        diffTree.children = this._visitChildren(null, oldTree);
215        diffTrees.push(diffTree);
216      }
217    } else {
218      throw new Error('Both newTree and oldTree are undefined...');
219    }
220
221    return diffTrees;
222  }
223
224  _visitChildren(newTree, oldTree) {
225    // Recursively traverse all children of new and old tree.
226    const diffChildren = [];
227
228    // TODO: Try replacing this with some sort of zipWith.
229    const numOfChildren = Math.max(
230        newTree?.children?.length ?? 0, oldTree?.children?.length ?? 0);
231    for (let i = 0; i < numOfChildren; i++) {
232      const newChild = i < newTree?.children?.length ?
233        newTree.children[i] : null;
234
235      const oldChild = i < oldTree?.children?.length ?
236        oldTree.children[i] : null;
237
238      const childDiffTrees = this._generateDiffTree(
239          newChild, oldChild,
240          newTree?.children ?? [], oldTree?.children ?? [],
241      );
242      diffChildren.push(...childDiffTrees);
243    }
244
245    return diffChildren;
246  }
247}
248