• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/*
2 * Copyright (C) 2022 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 */
16import {FilterType, TreeNode} from 'common/tree_utils';
17import {ObjectFormatter} from 'trace/flickerlib/ObjectFormatter';
18import {TraceTreeNode} from 'trace/trace_tree_node';
19import {
20  GPU_CHIP,
21  HWC_CHIP,
22  MISSING_LAYER,
23  RELATIVE_Z_CHIP,
24  RELATIVE_Z_PARENT_CHIP,
25  VISIBLE_CHIP,
26} from 'viewers/common/chip';
27import {DiffType, HierarchyTreeNode, UiTreeUtils} from './ui_tree_utils';
28
29type GetNodeIdCallbackType = (node: TraceTreeNode | null) => string | null;
30type IsModifiedCallbackType = (
31  newTree: TraceTreeNode | null,
32  oldTree: TraceTreeNode | null
33) => boolean;
34
35const HwcCompositionType = {
36  CLIENT: 1,
37  DEVICE: 2,
38  SOLID_COLOR: 3,
39};
40
41export class TreeGenerator {
42  private isOnlyVisibleView = false;
43  private isSimplifyNames = false;
44  private isFlatView = false;
45  private filter: FilterType;
46  private inputEntry: TraceTreeNode;
47  private previousEntry: TraceTreeNode | null = null;
48  private getNodeId?: GetNodeIdCallbackType;
49  private isModified?: IsModifiedCallbackType;
50  private newMapping: Map<string, TraceTreeNode> | null = null;
51  private oldMapping: Map<string, TraceTreeNode> | null = null;
52  private readonly pinnedIds: string[];
53  private pinnedItems: HierarchyTreeNode[] = [];
54  private relZParentIds: string[] = [];
55  private flattenedChildren: HierarchyTreeNode[] = [];
56
57  constructor(inputEntry: TraceTreeNode, filter: FilterType, pinnedIds?: string[]) {
58    this.inputEntry = inputEntry;
59    this.filter = filter;
60    this.pinnedIds = pinnedIds ?? [];
61  }
62
63  setIsOnlyVisibleView(enabled: boolean): TreeGenerator {
64    this.isOnlyVisibleView = enabled;
65    return this;
66  }
67
68  setIsSimplifyNames(enabled: boolean): TreeGenerator {
69    this.isSimplifyNames = enabled;
70    return this;
71  }
72
73  setIsFlatView(enabled: boolean): TreeGenerator {
74    this.isFlatView = enabled;
75    return this;
76  }
77
78  generateTree(): HierarchyTreeNode | null {
79    return this.getCustomizedTree(this.inputEntry);
80  }
81
82  compareWith(previousEntry: TraceTreeNode | null): TreeGenerator {
83    this.previousEntry = previousEntry;
84    return this;
85  }
86
87  withUniqueNodeId(getNodeId?: GetNodeIdCallbackType): TreeGenerator {
88    this.getNodeId = (node: TraceTreeNode | null) => {
89      const id = getNodeId ? getNodeId(node) : this.defaultNodeIdCallback(node);
90      if (id === null || id === undefined) {
91        console.error('Null node ID for node', node);
92        throw new Error("Node ID can't be null or undefined");
93      }
94      return id;
95    };
96    return this;
97  }
98
99  withModifiedCheck(isModified?: IsModifiedCallbackType): TreeGenerator {
100    this.isModified = isModified ?? this.defaultModifiedCheck;
101    return this;
102  }
103
104  generateFinalTreeWithDiff(): HierarchyTreeNode | null {
105    this.newMapping = this.generateIdToNodeMapping(this.inputEntry);
106    this.oldMapping = this.previousEntry ? this.generateIdToNodeMapping(this.previousEntry) : null;
107
108    const diffTrees = this.generateDiffTree(this.inputEntry, this.previousEntry, [], []);
109
110    let diffTree: TraceTreeNode;
111    if (diffTrees.length > 1) {
112      diffTree = {
113        kind: '',
114        name: 'DiffTree',
115        parent: undefined,
116        children: diffTrees,
117        stableId: 'DiffTree',
118      };
119    } else {
120      diffTree = diffTrees[0];
121    }
122    return this.getCustomizedTree(diffTree);
123  }
124
125  private getCustomizedTree(tree: TraceTreeNode | null): HierarchyTreeNode | null {
126    if (!tree) return null;
127    let newTree = this.generateTreeWithUserOptions(tree, false);
128    if (!newTree) return null;
129    newTree = this.updateTreeWithRelZParentChips(newTree);
130
131    if (this.isFlatView && newTree.children) {
132      this.flattenChildren(newTree.children);
133      newTree.children = this.flattenedChildren;
134    }
135    return Object.freeze(newTree);
136  }
137
138  getPinnedItems(): HierarchyTreeNode[] {
139    return this.pinnedItems;
140  }
141
142  private flattenChildren(children: HierarchyTreeNode[]) {
143    for (let i = 0; i < children.length; i++) {
144      const child = children[i];
145      const childIsVisibleNode =
146        child.isVisible && UiTreeUtils.isVisibleNode(child.kind, child.type);
147      const showInOnlyVisibleView = this.isOnlyVisibleView && childIsVisibleNode;
148      const passVisibleCheck = !this.isOnlyVisibleView || showInOnlyVisibleView;
149      if (this.filterMatches(child) && passVisibleCheck) {
150        this.flattenedChildren.push(child);
151      }
152      if (child.children) {
153        this.flattenChildren(child.children);
154      }
155    }
156  }
157
158  private filterMatches(item?: TreeNode | null): boolean {
159    return this.filter(item) ?? false;
160  }
161
162  private generateTreeWithUserOptions(
163    tree: TraceTreeNode,
164    parentFilterMatch: boolean
165  ): HierarchyTreeNode | null {
166    return this.applyChecks(tree, parentFilterMatch);
167  }
168
169  private updateTreeWithRelZParentChips(tree: HierarchyTreeNode): HierarchyTreeNode {
170    return this.applyRelZParentCheck(tree);
171  }
172
173  private applyRelZParentCheck(tree: HierarchyTreeNode) {
174    if (tree.id && this.relZParentIds.includes(`${tree.id}`)) {
175      tree.chips.push(RELATIVE_Z_PARENT_CHIP);
176    }
177
178    const numOfChildren = tree.children?.length ?? 0;
179    for (let i = 0; i < numOfChildren; i++) {
180      tree.children[i] = this.updateTreeWithRelZParentChips(tree.children[i]);
181    }
182
183    return tree;
184  }
185
186  private addChips(tree: HierarchyTreeNode): HierarchyTreeNode {
187    if (tree.hwcCompositionType === HwcCompositionType.CLIENT) {
188      tree.chips.push(GPU_CHIP);
189    } else if (
190      tree.hwcCompositionType === HwcCompositionType.DEVICE ||
191      tree.hwcCompositionType === HwcCompositionType.SOLID_COLOR
192    ) {
193      tree.chips.push(HWC_CHIP);
194    }
195    if (tree.isVisible && UiTreeUtils.isVisibleNode(tree.kind, tree.type)) {
196      tree.chips.push(VISIBLE_CHIP);
197    }
198    if (
199      tree.zOrderRelativeOfId !== undefined &&
200      tree.zOrderRelativeOfId !== -1 &&
201      !UiTreeUtils.isParentNode(tree.kind) &&
202      !tree.isRootLayer
203    ) {
204      tree.chips.push(RELATIVE_Z_CHIP);
205      this.relZParentIds.push(`${tree.zOrderRelativeOfId}`);
206    }
207    if (tree.isMissing) {
208      tree.chips.push(MISSING_LAYER);
209    }
210    return tree;
211  }
212
213  private applyChecks(tree: TraceTreeNode, parentFilterMatch: boolean): HierarchyTreeNode | null {
214    let newTree = this.makeTreeNode(tree);
215
216    // add id field to tree if id does not exist (e.g. for WM traces)
217    if (!newTree?.id && newTree?.layerId) {
218      newTree.id = newTree.layerId;
219    }
220
221    // simplify names check
222    newTree.simplifyNames = this.isSimplifyNames;
223
224    // check item either matches filter, or has parents/children matching filter
225    if (UiTreeUtils.isParentNode(tree.kind) || parentFilterMatch) {
226      newTree.showInFilteredView = true;
227    } else {
228      newTree.showInFilteredView = this.filterMatches(tree);
229      parentFilterMatch = newTree.showInFilteredView;
230    }
231
232    if (this.isOnlyVisibleView) {
233      newTree.showInOnlyVisibleView = UiTreeUtils.isParentNode(tree.kind)
234        ? true
235        : newTree.isVisible;
236    }
237
238    newTree.children = [];
239    const numOfChildren = tree.children?.length ?? 0;
240    for (let i = 0; i < numOfChildren; i++) {
241      const child = tree.children[i];
242      const newTreeChild = this.generateTreeWithUserOptions(child, parentFilterMatch);
243
244      if (newTreeChild) {
245        if (newTreeChild.showInFilteredView) {
246          newTree.showInFilteredView = true;
247        }
248
249        if (this.isOnlyVisibleView && newTreeChild.showInOnlyVisibleView) {
250          newTree.showInOnlyVisibleView = true;
251        }
252
253        newTree.children.push(newTreeChild);
254      }
255    }
256
257    const doNotShowInOnlyVisibleView = this.isOnlyVisibleView && !newTree.showInOnlyVisibleView;
258    if (!newTree.showInFilteredView || doNotShowInOnlyVisibleView) {
259      return null;
260    }
261
262    newTree = this.addChips(newTree);
263
264    if (this.pinnedIds.includes(`${newTree.id}`)) {
265      this.pinnedItems.push(newTree);
266    }
267
268    return newTree;
269  }
270
271  private generateIdToNodeMapping(
272    node: TraceTreeNode,
273    acc?: Map<string, TraceTreeNode>
274  ): Map<string, TraceTreeNode> {
275    acc = acc || new Map<string, TraceTreeNode>();
276
277    const nodeId: string = this.getNodeId!(node)!;
278
279    if (acc.get(nodeId)) {
280      throw new Error(`Duplicate node id '${nodeId}' detected...`);
281    }
282    acc.set(nodeId, node);
283
284    if (node.children) {
285      for (const child of node.children) {
286        this.generateIdToNodeMapping(child, acc);
287      }
288    }
289    return acc;
290  }
291
292  private cloneDiffTreeNode(node: TraceTreeNode | null): TraceTreeNode | null {
293    const clone = ObjectFormatter.cloneObject(node);
294    if (node) {
295      clone.children = node.children;
296      clone.name = node.name;
297      clone.kind = node.kind;
298      clone.stableId = node.stableId;
299      clone.shortName = node.shortName;
300    }
301    return clone;
302  }
303
304  private makeTreeNode(node: TraceTreeNode): HierarchyTreeNode {
305    const clone = new HierarchyTreeNode(node.name, node.kind, node.stableId);
306    if (node.shortName) clone.shortName = node.shortName;
307    if (node.type) clone.type = node.type;
308    if (node.id) clone.id = node.id;
309    if (node.layerId) clone.layerId = node.layerId;
310    if (node.isVisible) clone.isVisible = node.isVisible;
311    if (node.isMissing) clone.isMissing = node.isMissing;
312    if (node.hwcCompositionType) clone.hwcCompositionType = node.hwcCompositionType;
313    if (node.zOrderRelativeOfId) clone.zOrderRelativeOfId = node.zOrderRelativeOfId;
314    if (node.isRootLayer) clone.isRootLayer = node.isRootLayer;
315    if (node.diffType) clone.diffType = node.diffType;
316    if (node.skip) clone.skip = node.skip;
317
318    return clone;
319  }
320
321  private generateDiffTree(
322    newTree: TraceTreeNode | null,
323    oldTree: TraceTreeNode | null,
324    newTreeSiblings: Array<TraceTreeNode | null>,
325    oldTreeSiblings: Array<TraceTreeNode | null>
326  ): TraceTreeNode[] {
327    const diffTrees = [];
328    // NOTE: A null ID represents a non existent node.
329    if (!this.getNodeId) {
330      return [];
331    }
332    const newId = newTree ? this.getNodeId(newTree) : null;
333    const oldId = oldTree ? this.getNodeId(oldTree) : null;
334
335    const newTreeSiblingIds = newTreeSiblings.map(this.getNodeId);
336    const oldTreeSiblingIds = oldTreeSiblings.map(this.getNodeId);
337
338    if (newTree) {
339      // Clone is required because trees are frozen objects — we can't modify the original tree object.
340      const diffTree = this.cloneDiffTreeNode(newTree)!;
341
342      // Default to no changes
343      diffTree.diffType = DiffType.NONE;
344
345      if (!UiTreeUtils.isParentNode(newTree.kind) && newId !== oldId) {
346        // A move, addition, or deletion has occurred
347        let nextOldTree: TraceTreeNode | null = null;
348
349        // Check if newTree has been added or moved
350        if (newId && !oldTreeSiblingIds.includes(newId)) {
351          if (this.oldMapping && this.oldMapping.get(newId)) {
352            // Objected existed in old tree, so DELETED_MOVE will be/has been flagged and added to the
353            // diffTree when visiting it in the oldTree.
354            diffTree.diffType = DiffType.ADDED_MOVE;
355
356            // Switch out oldTree for new one to compare against
357            nextOldTree = this.oldMapping.get(newId) ?? null;
358          } else {
359            diffTree.diffType = DiffType.ADDED;
360
361            // Stop comparing against oldTree
362            nextOldTree = null;
363          }
364        }
365
366        // Check if oldTree has been deleted of moved
367        if (oldId && oldTree && !newTreeSiblingIds.includes(oldId)) {
368          const deletedTreeDiff = this.cloneDiffTreeNode(oldTree)!;
369
370          if (this.newMapping && this.newMapping.get(oldId)) {
371            deletedTreeDiff.diffType = DiffType.DELETED_MOVE;
372
373            // Stop comparing against oldTree, will be/has been
374            // visited when object is seen in newTree
375            nextOldTree = null;
376          } else {
377            deletedTreeDiff.diffType = DiffType.DELETED;
378
379            // Visit all children to check if they have been deleted or moved
380            deletedTreeDiff.children = this.visitChildren(null, oldTree);
381          }
382
383          diffTrees.push(deletedTreeDiff);
384        }
385
386        oldTree = nextOldTree;
387      } else {
388        if (this.isModified && this.isModified(newTree, oldTree)) {
389          diffTree.diffType = DiffType.MODIFIED;
390        }
391      }
392
393      diffTree.children = this.visitChildren(newTree, oldTree);
394      diffTrees.push(diffTree);
395    } else if (oldTree) {
396      if (oldId && !newTreeSiblingIds.includes(oldId)) {
397        // Deep clone oldTree omitting children field
398        const diffTree = this.cloneDiffTreeNode(oldTree)!;
399
400        // newTree doesn't exist, oldTree has either been moved or deleted.
401        if (this.newMapping && this.newMapping.get(oldId)) {
402          diffTree.diffType = DiffType.DELETED_MOVE;
403        } else {
404          diffTree.diffType = DiffType.DELETED;
405        }
406
407        diffTree.children = this.visitChildren(null, oldTree);
408        diffTrees.push(diffTree);
409      }
410    } else {
411      throw new Error('Both newTree and oldTree are undefined...');
412    }
413
414    return diffTrees;
415  }
416
417  private visitChildren(
418    newTree: TraceTreeNode | null,
419    oldTree: TraceTreeNode | null
420  ): TraceTreeNode[] {
421    // Recursively traverse all children of new and old tree.
422    const diffChildren = [];
423    const numOfChildren = Math.max(newTree?.children?.length ?? 0, oldTree?.children?.length ?? 0);
424    for (let i = 0; i < numOfChildren; i++) {
425      const newChild = newTree?.children ? newTree.children[i] : null;
426      const oldChild = oldTree?.children ? oldTree.children[i] : null;
427
428      const childDiffTrees = this.generateDiffTree(
429        newChild,
430        oldChild,
431        newTree?.children ?? [],
432        oldTree?.children ?? []
433      ).filter((tree) => tree != null);
434      diffChildren.push(...childDiffTrees);
435    }
436
437    return diffChildren;
438  }
439
440  private defaultNodeIdCallback(node: TraceTreeNode | null): string | null {
441    return node ? node.stableId : null;
442  }
443
444  private defaultModifiedCheck(
445    newNode: TraceTreeNode | null,
446    oldNode: TraceTreeNode | null
447  ): boolean {
448    if (!newNode && !oldNode) {
449      return false;
450    } else if (newNode && UiTreeUtils.isParentNode(newNode.kind)) {
451      return false;
452    } else if ((newNode && !oldNode) || (!newNode && oldNode)) {
453      return true;
454    } else if (newNode?.equals) {
455      return !newNode.equals(oldNode);
456    }
457    return false;
458  }
459}
460