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
17import { FILE_TYPES, TRACE_TYPES } from '@/decode.js';
18import TraceBase from './TraceBase';
19
20export default class Transactions extends TraceBase {
21  transactionsFile: Object;
22  transactionHistory: TransactionHistory;
23
24  constructor(files: any[]) {
25    const transactionsFile = files[FILE_TYPES.TRANSACTIONS_TRACE];
26
27    super(transactionsFile.data, transactionsFile.timeline, files);
28
29    this.transactionsFile = transactionsFile;
30  }
31
32  get type() {
33    return TRACE_TYPES.TRANSACTION;
34  }
35}
36
37class TransactionHistory {
38  history: Object;
39  applied: Object;
40  mergeTrees: any;
41
42  constructor(transactionsEventsFiles) {
43    this.history = {};
44    this.applied = {};
45
46    if (!transactionsEventsFiles) {
47      return;
48    }
49
50    for (const eventsFile of transactionsEventsFiles) {
51      for (const event of eventsFile.data) {
52        if (event.merge) {
53          const merge = event.merge;
54          const originalId = merge.originalTransaction.id;
55          const mergedId = merge.mergedTransaction.id;
56
57          this.addMerge(originalId, mergedId);
58        } else if (event.apply) {
59          this.addApply(event.apply.tx_id);
60        }
61      }
62    }
63  }
64
65  addMerge(originalId, mergedId) {
66    const merge = new Merge(originalId, mergedId, this.history);
67    this.addToHistoryOf(originalId, merge);
68  }
69
70  addApply(transactionId) {
71    this.applied[transactionId] = true;
72    this.addToHistoryOf(transactionId, new Apply(transactionId));
73  }
74
75  addToHistoryOf(transactionId, event) {
76    if (!this.history[transactionId]) {
77      this.history[transactionId] = [];
78    }
79    this.history[transactionId].push(event);
80  }
81
82  generateHistoryTreesOf(transactionId) {
83    return this._generateHistoryTree(transactionId);
84  }
85
86  _generateHistoryTree(transactionId, upTo = null) {
87    if (!this.history[transactionId]) {
88      return [];
89    }
90
91    const children = [];
92    const events = this.history[transactionId];
93    for (let i = 0; i < (upTo ?? events.length); i++) {
94      const event = events[i];
95
96      if (event instanceof Merge) {
97        const historyTree = this.
98          _generateHistoryTree(event.mergedId, event.mergedAt);
99        const mergeTreeNode = new MergeTreeNode(event.mergedId, historyTree);
100        children.push(mergeTreeNode);
101      } else if (event instanceof Apply) {
102        children.push(new ApplyTreeNode());
103      } else {
104        throw new Error('Unhandled event type');
105      }
106    }
107
108    return children;
109  }
110
111  /**
112   * Generates the list of all the transactions that have ever been merged into
113   * the target transaction directly or indirectly through the merges of
114   * transactions that ended up being merged into the transaction.
115   * This includes both merges that occur before and after the transaction is
116   * applied.
117   * @param {Number} transactionId - The id of the transaction we want the list
118   *                                 of transactions merged in for
119   * @return {Set<Number>} a set of all the transaction ids that are in the
120   *                       history of merges of the transaction
121   */
122  allTransactionsMergedInto(transactionId) {
123    const allTransactionsMergedIn = new Set();
124
125    let event;
126    const toVisit = this.generateHistoryTreesOf(transactionId);
127    while (event = toVisit.pop()) {
128      if (event instanceof MergeTreeNode) {
129        allTransactionsMergedIn.add(event.mergedId);
130        for (const child of event.children) {
131          toVisit.push(child);
132        }
133      }
134    }
135
136    return allTransactionsMergedIn;
137  }
138
139  /**
140   * Generated the list of transactions that have been directly merged into the
141   * target transaction those are transactions that have explicitly been merged
142   * in the code with a call to merge.
143   * @param {Number} transactionId - The id of the target transaction.
144   * @return {Array<Number>} an array of the transaction ids of the transactions
145   *                        directly merged into the target transaction
146   */
147  allDirectMergesInto(transactionId) {
148    return (this.history[transactionId] ?? [])
149      .filter((event) => event instanceof Merge)
150      .map((merge) => merge.mergedId);
151  }
152}
153
154class MergeTreeNode {
155  mergedId: Number;
156  mergedTransactionHistory: TransactionHistory;
157  children: TransactionHistory[];
158
159  constructor(mergedId, mergedTransactionHistory) {
160    this.mergedId = mergedId;
161    this.mergedTransactionHistory = mergedTransactionHistory;
162    this.children = mergedTransactionHistory;
163  }
164
165  get type() {
166    return 'merge';
167  }
168}
169
170class ApplyTreeNode {
171  children: any[];
172
173  constructor() {
174    this.children = [];
175  }
176
177  get type() {
178    return 'apply';
179  }
180}
181
182class Merge {
183  originalId: Number;
184  mergedId: Number;
185  mergedAt: Number;
186
187  constructor(originalId, mergedId, history) {
188    this.originalId = originalId;
189    this.mergedId = mergedId;
190    // Specifies how long the merge chain of the merged transaction was at the
191    // time is was merged.
192    this.mergedAt = history[mergedId]?.length ?? 0;
193  }
194}
195
196class Apply {
197  transactionId: Number;
198
199  constructor(transactionId) {
200    this.transactionId = transactionId;
201  }
202}
203
204/**
205 * Converts the transactionId to the values that compose the identifier.
206 * The top 32 bits is the PID of the process that created the transaction
207 * and the bottom 32 bits is the ID of the transaction unique within that
208 * process.
209 * @param {Number} transactionId
210 * @return {Object} An object containing the id and pid of the transaction.
211 */
212export function expandTransactionId(transactionId) {
213  // Can't use bit shift operation because it isn't a 32 bit integer...
214  // Because js uses floating point numbers for everything, maths isn't 100%
215  // accurate so we need to round...
216  return Object.freeze({
217    id: Math.round(transactionId % Math.pow(2, 32)),
218    pid: Math.round(transactionId / Math.pow(2, 32)),
219  });
220}
221