| 1 | /** |
| 2 | * Copyright (c) Meta Platforms, Inc. and affiliates. |
| 3 | * |
| 4 | * This source code is licensed under the MIT license found in the |
| 5 | * LICENSE file in the root directory of this source tree. |
| 6 | */ |
| 7 | |
| 8 | import type {Hash} from '../types'; |
| 9 | import type {HashWithParents} from './base_dag'; |
| 10 | |
| 11 | import {BaseDag} from './base_dag'; |
| 12 | import {Ancestor, AncestorType} from './render'; |
| 13 | import {TextRenderer} from './renderText'; |
| 14 | |
| 15 | /** |
| 16 | * Dag that tracks predecessor -> successor relationships. |
| 17 | * |
| 18 | * Predecessors are "ancestors". Successors are "descendants". |
| 19 | * |
| 20 | * This graph can contain hashes that were deleted in the main graph. |
| 21 | * For example, amend A1 to A2 to A3 to A4. This graph will keep all |
| 22 | * 4 hashes so it can answer questions like "I had A1, what is it now?" |
| 23 | * (A4) when the main graph only contains A4. |
| 24 | * |
| 25 | * In the above example, the user can also hide A4 and review A3 |
| 26 | * (ex. undo, or hide when A3 has visible descendants). In this case, |
| 27 | * "what A1 becomes?" should be A3. So the followSuccessor() |
| 28 | * implementation should consider the mainDag, like: |
| 29 | * |
| 30 | * // Consider what is present in the mainDag. |
| 31 | * mutationDag.heads(mutationDag.range(start, mainDag)) |
| 32 | * |
| 33 | * not: |
| 34 | * |
| 35 | * // BAD: Only consider mutationDag, might return hashes |
| 36 | * // missing in the mainDag. |
| 37 | * mutationDag.heads(mutationDag.descendants(start)) |
| 38 | * |
| 39 | * Note: "dag" is a lossy view for actual mutation data. For example, |
| 40 | * it does not distinguish between: |
| 41 | * - amending A to A1, amending A to A2 (considered "divergence") |
| 42 | * - splitting A into A1 and A2 (not considered as a "divergence") |
| 43 | * Be careful when it is necessary to distinguish between them. |
| 44 | */ |
| 45 | export class MutationDag extends BaseDag<HashWithParents> { |
| 46 | constructor(baseDag?: BaseDag<HashWithParents>) { |
| 47 | const record = baseDag?.inner; |
| 48 | super(record); |
| 49 | } |
| 50 | |
| 51 | /** |
| 52 | * Insert old->new mappings to the mutation dag. |
| 53 | * |
| 54 | * Note about `oldNewPairs`: |
| 55 | * - a same 'new' can have multiple 'old's (ex. fold) |
| 56 | * - a same 'old' can have multiple 'new's (ex. split) |
| 57 | * So the `oldNewPairs` should not be `Map`s with unique keys. |
| 58 | */ |
| 59 | addMutations(oldNewPairs: Iterable<[Hash, Hash]>): MutationDag { |
| 60 | const infoMap: Map<Hash, HashWithParents> = new Map(); |
| 61 | const insert = (hash: Hash, parents: Hash[]) => { |
| 62 | // Insert `hash` to the infoMap on demand. |
| 63 | let info = infoMap.get(hash); |
| 64 | if (info == null) { |
| 65 | info = { |
| 66 | hash, |
| 67 | parents: this.get(hash)?.parents ?? [], |
| 68 | grandparents: this.get(hash)?.grandparents ?? [], |
| 69 | }; |
| 70 | infoMap.set(hash, info); |
| 71 | } |
| 72 | // Append parents. |
| 73 | if (parents.length > 0) { |
| 74 | info.parents = Array.from(new Set(info.parents.concat(parents))); |
| 75 | } |
| 76 | }; |
| 77 | for (const [oldHash, newHash] of oldNewPairs) { |
| 78 | insert(newHash, [oldHash]); |
| 79 | insert(oldHash, []); |
| 80 | } |
| 81 | const baseDag = this.add(infoMap.values()); |
| 82 | return new MutationDag(baseDag); |
| 83 | } |
| 84 | |
| 85 | /** Provided extra fields for debugging use-case. For now, this includes an ASCII graph. */ |
| 86 | getDebugState(): {rendered: Array<string>} { |
| 87 | const renderer = new TextRenderer(); |
| 88 | const rendered = []; |
| 89 | |
| 90 | // Render row by row. The main complexity is to figure out the "ancestors", |
| 91 | // especially when the provided `set` is a subset of the dag. |
| 92 | for (const hash of this.sortDesc(this, {gap: false})) { |
| 93 | const parents = this.parentHashes(hash); |
| 94 | const typedParents: Ancestor[] = parents.map( |
| 95 | hash => new Ancestor({type: AncestorType.Parent, hash}), |
| 96 | ); |
| 97 | const renderedRow = renderer.nextRow(hash, typedParents, hash); |
| 98 | for (const line of renderedRow.trimEnd().split('\n')) { |
| 99 | rendered.push(line); |
| 100 | } |
| 101 | } |
| 102 | return {rendered}; |
| 103 | } |
| 104 | } |
| 105 | |