1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import {assertNumber} from '../asserts';import type {Hash} from '../hash';
export type HeadChange = {  new: Hash | undefined;  old: Hash | undefined;};
export type RefCountUpdates = Map<Hash, number>;type LoadedRefCountPromises = Map<Hash, Promise<number>>;
export interface GarbageCollectionDelegate {  getRefCount: (hash: Hash) => Promise<number | undefined>;  getRefs: (hash: Hash) => Promise<readonly Hash[] | undefined>;}
/** * Computes how ref counts should be updated when a dag write is commited. * Does not modify the dag store. * @param headChanges Heads that were changed by the dag write. * @param putChunks Chunks that were put by the dag write. * @param delegate Delegate used for loading ref information from the dag store. * @returns Map from chunk Hash to new ref count.  Chunks with a new ref count of 0 should * be deleted.  All hashes in `putChunks` will have an entry (which will be zero if the * newly put chunk is not reachable from any head). */export async function computeRefCountUpdates(  headChanges: Iterable<HeadChange>,  putChunks: ReadonlySet<Hash>,  delegate: GarbageCollectionDelegate,): Promise<RefCountUpdates> {  const newHeads: Hash[] = [];  const oldHeads: Hash[] = [];  for (const changedHead of headChanges) {    changedHead.old && oldHeads.push(changedHead.old);    changedHead.new && newHeads.push(changedHead.new);  }
  const refCountUpdates: RefCountUpdates = new Map();  // This map is used to ensure we do not load the ref count key more than once.  // Once it is loaded we only operate on a cache of the ref counts.  const loadedRefCountPromises: LoadedRefCountPromises = new Map();
  for (const n of newHeads) {    await changeRefCount(      n,      1,      refCountUpdates,      loadedRefCountPromises,      delegate,    );  }
  for (const o of oldHeads) {    await changeRefCount(      o,      -1,      refCountUpdates,      loadedRefCountPromises,      delegate,    );  }
  // Now go through the put chunks to ensure each has an entry in refCountUpdates  // (zero for new chunks which are not reachable from newHeads).  await Promise.all(    Array.from(putChunks.values(), hash =>      ensureRefCountLoaded(        hash,        refCountUpdates,        loadedRefCountPromises,        delegate,      ),    ),  );
  return refCountUpdates;}
async function changeRefCount(  hash: Hash,  delta: number,  refCountUpdates: RefCountUpdates,  loadedRefCountPromises: LoadedRefCountPromises,  delegate: GarbageCollectionDelegate,): Promise<void> {  // First make sure that we have the ref count in the cache. This is async  // because it might need to load the ref count from the store (via the delegate).  //  // Once we have loaded the ref count all the updates to it are sync to  // prevent race conditions.  await ensureRefCountLoaded(    hash,    refCountUpdates,    loadedRefCountPromises,    delegate,  );
  if (updateRefCount(hash, delta, refCountUpdates)) {    const refs = await delegate.getRefs(hash);    if (refs !== undefined) {      const ps = refs.map(ref =>        changeRefCount(          ref,          delta,          refCountUpdates,          loadedRefCountPromises,          delegate,        ),      );      await Promise.all(ps);    }  }}
function ensureRefCountLoaded(  hash: Hash,  refCountUpdates: RefCountUpdates,  loadedRefCountPromises: LoadedRefCountPromises,  delegate: GarbageCollectionDelegate,): Promise<number> {  // Only get the ref count once.  let p = loadedRefCountPromises.get(hash);  if (p === undefined) {    p = (async () => {      const value = (await delegate.getRefCount(hash)) || 0;      refCountUpdates.set(hash, value);      return value;    })();    loadedRefCountPromises.set(hash, p);  }  return p;}
function updateRefCount(  hash: Hash,  delta: number,  refCountUpdates: RefCountUpdates,): boolean {  const oldCount = refCountUpdates.get(hash);  assertNumber(oldCount);  refCountUpdates.set(hash, oldCount + delta);  return (oldCount === 0 && delta === 1) || (oldCount === 1 && delta === -1);}