1/*
2 * Copyright (C) 2024 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
17import {assertDefined} from 'common/assert_utils';
18import {TreeNode} from 'trace/tree_node/tree_node';
19import {DiffNode} from 'viewers/common/diff_node';
20import {DiffType} from 'viewers/common/diff_type';
21
22export abstract class AddDiffs<T extends DiffNode> {
23  private newIdNodeMap = new Map<string, T>();
24  private oldIdNodeMap = new Map<string, T>();
25  protected abstract addDiffsToNewRoot: boolean;
26  protected abstract processModifiedNodes(newNode: T, oldNode: T): void;
27  protected abstract processOldNode(oldNode: T): void;
28
29  constructor(
30    private isModified: IsModifiedCallbackType,
31    private denylistProperties: string[],
32  ) {}
33
34  async executeInPlace(newRoot: T, oldRoot?: T): Promise<void> {
35    this.newIdNodeMap = this.updateIdNodeMap(newRoot);
36    this.oldIdNodeMap = this.updateIdNodeMap(oldRoot);
37    await this.generateDiffNodes(newRoot, oldRoot, [], []);
38  }
39
40  private updateIdNodeMap(root: T | undefined): Map<string, T> {
41    const idNodeMap = new Map<string, T>();
42
43    root?.forEachNodeDfs((node) => {
44      idNodeMap.set(node.id, node);
45    });
46
47    return idNodeMap;
48  }
49
50  private async generateDiffNodes(
51    newNode: T | undefined,
52    oldNode: T | undefined,
53    newNodeSiblingIds: string[],
54    oldNodeSiblingIds: string[],
55  ): Promise<T[]> {
56    const diffNodes: T[] = [];
57
58    if (!oldNode && !newNode) {
59      console.error('both new and old trees undefined');
60      return diffNodes;
61    }
62
63    if (!newNode && oldNode) {
64      if (!newNodeSiblingIds.includes(oldNode.id)) {
65        //oldNode deleted or moved
66        if (this.newIdNodeMap.get(oldNode.id)) {
67          oldNode.setDiff(DiffType.DELETED_MOVE);
68        } else {
69          oldNode.setDiff(DiffType.DELETED);
70        }
71        const newChildren = await this.visitChildren(undefined, oldNode);
72        oldNode.removeAllChildren();
73        newChildren.forEach((child) => {
74          assertDefined(oldNode).addOrReplaceChild(child);
75        });
76        this.processOldNode(oldNode);
77        diffNodes.push(oldNode);
78      }
79      return diffNodes;
80    }
81
82    newNode = assertDefined(newNode);
83
84    if (!newNode.isRoot() && newNode.id !== oldNode?.id) {
85      let nextOldNode: T | undefined;
86
87      if (!oldNodeSiblingIds.includes(newNode.id)) {
88        if (this.oldIdNodeMap.get(newNode.id)) {
89          if (this.addDiffsToNewRoot) {
90            newNode.setDiff(DiffType.ADDED_MOVE);
91            nextOldNode = this.oldIdNodeMap.get(newNode.id);
92          }
93        } else {
94          newNode.setDiff(DiffType.ADDED);
95          nextOldNode = undefined; //newNode has no equiv in old tree
96        }
97      }
98
99      if (oldNode && !newNodeSiblingIds.includes(oldNode.id)) {
100        if (this.newIdNodeMap.get(oldNode.id)) {
101          //oldNode still exists
102          oldNode.setDiff(DiffType.DELETED_MOVE);
103          nextOldNode = undefined;
104        } else {
105          oldNode.setDiff(DiffType.DELETED);
106
107          const newChildren = await this.visitChildren(undefined, oldNode);
108          oldNode.removeAllChildren();
109
110          newChildren.forEach((child) => {
111            assertDefined(oldNode).addOrReplaceChild(child);
112          });
113        }
114        this.processOldNode(oldNode);
115        diffNodes.push(oldNode);
116      }
117
118      oldNode = nextOldNode;
119    } else if (!newNode.isRoot()) {
120      if (
121        oldNode &&
122        oldNode.id === newNode.id &&
123        (await this.isModified(newNode, oldNode, this.denylistProperties))
124      ) {
125        this.processModifiedNodes(newNode, oldNode);
126      }
127    }
128
129    const newChildren = await this.visitChildren(newNode, oldNode);
130    newNode.removeAllChildren();
131    newChildren.forEach((child) =>
132      assertDefined(newNode).addOrReplaceChild(child),
133    );
134
135    diffNodes.push(newNode);
136    return diffNodes;
137  }
138
139  async visitChildren(
140    newNode: T | undefined,
141    oldNode: T | undefined,
142  ): Promise<T[]> {
143    const diffChildren: T[] = [];
144    const numOfChildren = Math.max(
145      newNode?.getAllChildren().length ?? 0,
146      oldNode?.getAllChildren().length ?? 0,
147    );
148    for (let i = 0; i < numOfChildren; i++) {
149      const newChild = newNode?.getAllChildren()[i];
150      let oldChild = oldNode?.getAllChildren()[i];
151
152      if (!oldChild && newChild) {
153        oldChild = oldNode
154          ?.getAllChildren()
155          .find((node) => node.name === newChild.name);
156      }
157
158      const childDiffTrees = await this.generateDiffNodes(
159        newChild,
160        oldChild,
161        newNode?.getAllChildren().map((child) => child.id) ?? [],
162        oldNode?.getAllChildren().map((child) => child.id) ?? [],
163      );
164      childDiffTrees.forEach((child) => diffChildren.push(child));
165    }
166
167    return diffChildren;
168  }
169}
170
171export type IsModifiedCallbackType = (
172  newTree: TreeNode | undefined,
173  oldTree: TreeNode | undefined,
174  denylistProperties: string[],
175) => Promise<boolean>;
176