| b69ab31 | | | 1 | /** |
| b69ab31 | | | 2 | * Copyright (c) Meta Platforms, Inc. and affiliates. |
| b69ab31 | | | 3 | * |
| b69ab31 | | | 4 | * This source code is licensed under the MIT license found in the |
| b69ab31 | | | 5 | * LICENSE file in the root directory of this source tree. |
| b69ab31 | | | 6 | */ |
| b69ab31 | | | 7 | |
| b69ab31 | | | 8 | // @lint-ignore-every SPELL |
| b69ab31 | | | 9 | |
| b69ab31 | | | 10 | import type {CommitInfo, CommitPhaseType, Hash, SuccessorInfo} from '../../types'; |
| b69ab31 | | | 11 | import type {SetLike} from '../set'; |
| b69ab31 | | | 12 | |
| b69ab31 | | | 13 | import {BaseDag} from '../base_dag'; |
| b69ab31 | | | 14 | import {Dag, DagCommitInfo, REBASE_SUCC_PREFIX} from '../dag'; |
| b69ab31 | | | 15 | import {HashSet} from '../set'; |
| b69ab31 | | | 16 | |
| b69ab31 | | | 17 | const toInfo = (info: Partial<CommitInfo>): DagCommitInfo => DagCommitInfo.fromCommitInfo(info); |
| b69ab31 | | | 18 | const DRAFT: CommitPhaseType = 'draft'; |
| b69ab31 | | | 19 | const PUBLIC: CommitPhaseType = 'public'; |
| b69ab31 | | | 20 | |
| b69ab31 | | | 21 | describe('Dag', () => { |
| b69ab31 | | | 22 | // Dummy info. |
| b69ab31 | | | 23 | const date = new Date(42); |
| b69ab31 | | | 24 | const info: CommitInfo = { |
| b69ab31 | | | 25 | title: '', |
| b69ab31 | | | 26 | hash: '', |
| b69ab31 | | | 27 | parents: [], |
| b69ab31 | | | 28 | grandparents: [], |
| b69ab31 | | | 29 | phase: DRAFT, |
| b69ab31 | | | 30 | isDot: false, |
| b69ab31 | | | 31 | author: '', |
| b69ab31 | | | 32 | date, |
| b69ab31 | | | 33 | description: '', |
| b69ab31 | | | 34 | bookmarks: [], |
| b69ab31 | | | 35 | remoteBookmarks: [], |
| b69ab31 | | | 36 | totalFileCount: 0, |
| b69ab31 | | | 37 | filePathsSample: [], |
| b69ab31 | | | 38 | maxCommonPathPrefix: '', |
| b69ab31 | | | 39 | }; |
| b69ab31 | | | 40 | |
| b69ab31 | | | 41 | describe('basic queries', () => { |
| b69ab31 | | | 42 | const dagAbc = new BaseDag().add([ |
| b69ab31 | | | 43 | {hash: 'a', parents: ['z'], grandparents: []}, |
| b69ab31 | | | 44 | {hash: 'b', parents: ['a'], grandparents: []}, |
| b69ab31 | | | 45 | {hash: 'c', parents: ['b', 'a'], grandparents: []}, |
| b69ab31 | | | 46 | ]); |
| b69ab31 | | | 47 | |
| b69ab31 | | | 48 | it('maintains parent<->child mappings', () => { |
| b69ab31 | | | 49 | const dag = dagAbc; |
| b69ab31 | | | 50 | expect(dag.parentHashes('a')).toEqual([]); |
| b69ab31 | | | 51 | expect(dag.parentHashes('b')).toEqual(['a']); |
| b69ab31 | | | 52 | expect(dag.parentHashes('c')).toEqual(['b', 'a']); |
| b69ab31 | | | 53 | expect(dag.parentHashes('d')).toEqual([]); |
| b69ab31 | | | 54 | expect(dag.parentHashes('z')).toEqual([]); |
| b69ab31 | | | 55 | expect(dag.childHashes('a').toArray()).toEqual(['b', 'c']); |
| b69ab31 | | | 56 | expect(dag.childHashes('b').toArray()).toEqual(['c']); |
| b69ab31 | | | 57 | expect(dag.childHashes('c').toArray()).toEqual([]); |
| b69ab31 | | | 58 | expect(dag.childHashes('d').toArray()).toEqual([]); |
| b69ab31 | | | 59 | expect(dag.childHashes('z').toArray()).toEqual([]); |
| b69ab31 | | | 60 | }); |
| b69ab31 | | | 61 | |
| b69ab31 | | | 62 | it('maintains parent<->child mappings after remove()', () => { |
| b69ab31 | | | 63 | const dag = dagAbc.remove(['b']); |
| b69ab31 | | | 64 | expect(dag.parentHashes('c')).toEqual(['a']); |
| b69ab31 | | | 65 | expect(dag.childHashes('a').toArray()).toEqual(['c']); |
| b69ab31 | | | 66 | expect(dag.parentHashes('b')).toEqual([]); |
| b69ab31 | | | 67 | expect(dag.childHashes('b').toArray()).toEqual([]); |
| b69ab31 | | | 68 | }); |
| b69ab31 | | | 69 | |
| b69ab31 | | | 70 | it('removes conflicted commits', () => { |
| b69ab31 | | | 71 | const dag = dagAbc.add([{hash: 'c', parents: [], grandparents: []}]); |
| b69ab31 | | | 72 | expect(dag.parentHashes('c')).toEqual([]); |
| b69ab31 | | | 73 | expect(dag.childHashes('b').toArray()).toEqual([]); |
| b69ab31 | | | 74 | }); |
| b69ab31 | | | 75 | |
| b69ab31 | | | 76 | it('supports replaceWith()', () => { |
| b69ab31 | | | 77 | const dag = new Dag() |
| b69ab31 | | | 78 | .add( |
| b69ab31 | | | 79 | [ |
| b69ab31 | | | 80 | {...info, hash: 'a', parents: ['z']}, |
| b69ab31 | | | 81 | {...info, hash: 'b', parents: ['a']}, |
| b69ab31 | | | 82 | {...info, hash: 'c', parents: ['b', 'a']}, |
| b69ab31 | | | 83 | ].map(toInfo), |
| b69ab31 | | | 84 | ) |
| b69ab31 | | | 85 | .replaceWith(['c', 'd'], (h, _c) => |
| b69ab31 | | | 86 | toInfo({ |
| b69ab31 | | | 87 | ...info, |
| b69ab31 | | | 88 | hash: h, |
| b69ab31 | | | 89 | parents: ['b'], |
| b69ab31 | | | 90 | }), |
| b69ab31 | | | 91 | ).commitDag; |
| b69ab31 | | | 92 | expect(dag.parentHashes('c')).toEqual(['b']); |
| b69ab31 | | | 93 | expect(dag.parentHashes('d')).toEqual(['b']); |
| b69ab31 | | | 94 | expect(dag.childHashes('a').toArray()).toEqual(['b']); |
| b69ab31 | | | 95 | expect(dag.childHashes('b').toArray()).toEqual(['c', 'd']); |
| b69ab31 | | | 96 | }); |
| b69ab31 | | | 97 | }); |
| b69ab31 | | | 98 | |
| b69ab31 | | | 99 | describe('high-level queries', () => { |
| b69ab31 | | | 100 | /** |
| b69ab31 | | | 101 | * A--B--C--F |
| b69ab31 | | | 102 | * \ / |
| b69ab31 | | | 103 | * D-E--G |
| b69ab31 | | | 104 | */ |
| b69ab31 | | | 105 | const dag = new Dag().add( |
| b69ab31 | | | 106 | [ |
| b69ab31 | | | 107 | {...info, hash: 'a', parents: []}, |
| b69ab31 | | | 108 | {...info, hash: 'b', parents: ['a']}, |
| b69ab31 | | | 109 | {...info, hash: 'c', parents: ['b']}, |
| b69ab31 | | | 110 | {...info, hash: 'd', parents: ['b']}, |
| b69ab31 | | | 111 | {...info, hash: 'e', parents: ['d']}, |
| b69ab31 | | | 112 | {...info, hash: 'f', parents: ['c', 'e']}, |
| b69ab31 | | | 113 | {...info, hash: 'g', parents: ['e']}, |
| b69ab31 | | | 114 | ].map(toInfo), |
| b69ab31 | | | 115 | ); |
| b69ab31 | | | 116 | |
| b69ab31 | | | 117 | it('parents()', () => { |
| b69ab31 | | | 118 | expect(dag.parents('f').toSortedArray()).toEqual(['c', 'e']); |
| b69ab31 | | | 119 | expect(dag.parents(['b', 'c', 'f']).toSortedArray()).toEqual(['a', 'b', 'c', 'e']); |
| b69ab31 | | | 120 | }); |
| b69ab31 | | | 121 | |
| b69ab31 | | | 122 | it('children()', () => { |
| b69ab31 | | | 123 | expect(dag.children('b').toSortedArray()).toEqual(['c', 'd']); |
| b69ab31 | | | 124 | expect(dag.children(['a', 'b', 'd']).toSortedArray()).toEqual(['b', 'c', 'd', 'e']); |
| b69ab31 | | | 125 | }); |
| b69ab31 | | | 126 | |
| b69ab31 | | | 127 | it('ancestors()', () => { |
| b69ab31 | | | 128 | expect(dag.ancestors('c').toSortedArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 129 | expect(dag.ancestors('f').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f']); |
| b69ab31 | | | 130 | expect(dag.ancestors('g').toSortedArray()).toEqual(['a', 'b', 'd', 'e', 'g']); |
| b69ab31 | | | 131 | expect(dag.ancestors('f', {within: ['a', 'c', 'd', 'e']}).toSortedArray()).toEqual([ |
| b69ab31 | | | 132 | 'c', |
| b69ab31 | | | 133 | 'd', |
| b69ab31 | | | 134 | 'e', |
| b69ab31 | | | 135 | 'f', |
| b69ab31 | | | 136 | ]); |
| b69ab31 | | | 137 | }); |
| b69ab31 | | | 138 | |
| b69ab31 | | | 139 | it('descendants()', () => { |
| b69ab31 | | | 140 | expect(dag.descendants('a').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f', 'g']); |
| b69ab31 | | | 141 | expect(dag.descendants('c').toSortedArray()).toEqual(['c', 'f']); |
| b69ab31 | | | 142 | expect(dag.descendants('d').toSortedArray()).toEqual(['d', 'e', 'f', 'g']); |
| b69ab31 | | | 143 | expect(dag.descendants('b', {within: ['c', 'd', 'g']}).toSortedArray()).toEqual([ |
| b69ab31 | | | 144 | 'b', |
| b69ab31 | | | 145 | 'c', |
| b69ab31 | | | 146 | 'd', |
| b69ab31 | | | 147 | ]); |
| b69ab31 | | | 148 | }); |
| b69ab31 | | | 149 | |
| b69ab31 | | | 150 | it('heads()', () => { |
| b69ab31 | | | 151 | expect(dag.heads(['a', 'b', 'c']).toSortedArray()).toEqual(['c']); |
| b69ab31 | | | 152 | expect(dag.heads(['d', 'e', 'g']).toSortedArray()).toEqual(['g']); |
| b69ab31 | | | 153 | expect(dag.heads(['e', 'f', 'g']).toSortedArray()).toEqual(['f', 'g']); |
| b69ab31 | | | 154 | expect(dag.heads(['c', 'e', 'f']).toSortedArray()).toEqual(['f']); |
| b69ab31 | | | 155 | }); |
| b69ab31 | | | 156 | |
| b69ab31 | | | 157 | it('roots()', () => { |
| b69ab31 | | | 158 | expect(dag.roots(['a', 'b', 'c']).toSortedArray()).toEqual(['a']); |
| b69ab31 | | | 159 | expect(dag.roots(['d', 'e', 'g']).toSortedArray()).toEqual(['d']); |
| b69ab31 | | | 160 | expect(dag.roots(['e', 'f', 'g']).toSortedArray()).toEqual(['e']); |
| b69ab31 | | | 161 | expect(dag.roots(['c', 'e', 'f']).toSortedArray()).toEqual(['c', 'e']); |
| b69ab31 | | | 162 | }); |
| b69ab31 | | | 163 | |
| b69ab31 | | | 164 | it('range()', () => { |
| b69ab31 | | | 165 | expect(dag.range('a', 'c').toSortedArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 166 | expect(dag.range('a', 'f').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f']); |
| b69ab31 | | | 167 | expect(dag.range('b', 'g').toSortedArray()).toEqual(['b', 'd', 'e', 'g']); |
| b69ab31 | | | 168 | expect(dag.range(['a', 'b'], ['a', 'b']).toSortedArray()).toEqual(['a', 'b']); |
| b69ab31 | | | 169 | }); |
| b69ab31 | | | 170 | |
| b69ab31 | | | 171 | it('gca()', () => { |
| b69ab31 | | | 172 | expect(dag.gca('f', 'g').toSortedArray()).toEqual(['e']); |
| b69ab31 | | | 173 | expect(dag.gca('f', 'e').toSortedArray()).toEqual(['e']); |
| b69ab31 | | | 174 | expect(dag.gca('c', 'e').toSortedArray()).toEqual(['b']); |
| b69ab31 | | | 175 | }); |
| b69ab31 | | | 176 | |
| b69ab31 | | | 177 | it('isAncestor()', () => { |
| b69ab31 | | | 178 | expect(dag.isAncestor('a', 'a')).toBe(true); |
| b69ab31 | | | 179 | expect(dag.isAncestor('b', 'g')).toBe(true); |
| b69ab31 | | | 180 | expect(dag.isAncestor('d', 'f')).toBe(true); |
| b69ab31 | | | 181 | expect(dag.isAncestor('c', 'g')).toBe(false); |
| b69ab31 | | | 182 | expect(dag.isAncestor('g', 'a')).toBe(false); |
| b69ab31 | | | 183 | }); |
| b69ab31 | | | 184 | |
| b69ab31 | | | 185 | it('supports present()', () => { |
| b69ab31 | | | 186 | expect(dag.present(['a', 'x']).toSortedArray()).toEqual(['a']); |
| b69ab31 | | | 187 | }); |
| b69ab31 | | | 188 | |
| b69ab31 | | | 189 | it('does not infinite loop on cyclic graphs', () => { |
| b69ab31 | | | 190 | const dag = new BaseDag().add([ |
| b69ab31 | | | 191 | {hash: 'a', parents: ['b'], grandparents: []}, |
| b69ab31 | | | 192 | {hash: 'b', parents: ['c'], grandparents: []}, |
| b69ab31 | | | 193 | {hash: 'c', parents: ['a'], grandparents: []}, |
| b69ab31 | | | 194 | ]); |
| b69ab31 | | | 195 | expect(dag.ancestors('b').toSortedArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 196 | expect(dag.descendants('b').toSortedArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 197 | expect(dag.isAncestor('a', 'c')).toBe(true); |
| b69ab31 | | | 198 | expect(dag.isAncestor('c', 'a')).toBe(true); |
| b69ab31 | | | 199 | }); |
| b69ab31 | | | 200 | |
| b69ab31 | | | 201 | it('preserves order for ancestors() or descendants()', () => { |
| b69ab31 | | | 202 | // a--b--c |
| b69ab31 | | | 203 | const dag = new BaseDag().add([ |
| b69ab31 | | | 204 | {...info, hash: 'a', parents: []}, |
| b69ab31 | | | 205 | {...info, hash: 'b', parents: ['a']}, |
| b69ab31 | | | 206 | {...info, hash: 'c', parents: ['b']}, |
| b69ab31 | | | 207 | ]); |
| b69ab31 | | | 208 | expect(dag.ancestors('c').toArray()).toEqual(['c', 'b', 'a']); |
| b69ab31 | | | 209 | expect(dag.ancestors('c').reverse().toArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 210 | expect(dag.descendants('a').toArray()).toEqual(['a', 'b', 'c']); |
| b69ab31 | | | 211 | }); |
| b69ab31 | | | 212 | }); |
| b69ab31 | | | 213 | |
| b69ab31 | | | 214 | describe('sort', () => { |
| b69ab31 | | | 215 | // a--b--c--d---e--f |
| b69ab31 | | | 216 | // \ / |
| b69ab31 | | | 217 | // y--x--w--v--u |
| b69ab31 | | | 218 | const dag = new BaseDag().add( |
| b69ab31 | | | 219 | Object.entries({ |
| b69ab31 | | | 220 | a: '', |
| b69ab31 | | | 221 | b: 'a', |
| b69ab31 | | | 222 | c: 'b', |
| b69ab31 | | | 223 | d: 'c', |
| b69ab31 | | | 224 | e: 'd v', |
| b69ab31 | | | 225 | f: 'e', |
| b69ab31 | | | 226 | y: '', |
| b69ab31 | | | 227 | x: 'y b', |
| b69ab31 | | | 228 | w: 'x', |
| b69ab31 | | | 229 | v: 'w', |
| b69ab31 | | | 230 | u: 'v', |
| b69ab31 | | | 231 | }).map(([hash, v]) => { |
| b69ab31 | | | 232 | return {hash, parents: v.split(' '), grandparents: []}; |
| b69ab31 | | | 233 | }), |
| b69ab31 | | | 234 | ); |
| b69ab31 | | | 235 | |
| b69ab31 | | | 236 | it('asc', () => { |
| b69ab31 | | | 237 | const sort = (s: SetLike) => dag.sortAsc(s).join(' '); |
| b69ab31 | | | 238 | // sort all |
| b69ab31 | | | 239 | expect(sort(dag)).toBe('a b c d y x w v e f u'); |
| b69ab31 | | | 240 | // sort subset |
| b69ab31 | | | 241 | expect(sort(['a', 'f', 'b', 'c', 'e', 'd'])).toBe('a b c d e f'); |
| b69ab31 | | | 242 | expect(sort(['y', 'u', 'w', 'v', 'x'])).toBe('y x w v u'); |
| b69ab31 | | | 243 | expect(sort(['a', 'f', 'd'])).toBe('a d f'); |
| b69ab31 | | | 244 | expect(sort(['u', 'y', 'w'])).toBe('y w u'); |
| b69ab31 | | | 245 | expect(sort(['w', 'f', 'y'])).toBe('y w f'); |
| b69ab31 | | | 246 | expect(sort(['x', 'y', 'f', 'e'])).toBe('y x e f'); |
| b69ab31 | | | 247 | // custom sort function |
| b69ab31 | | | 248 | expect(dag.sortAsc(['d', 'v'], {compare: a => (a.hash === 'v' ? -1 : 1)})).toEqual([ |
| b69ab31 | | | 249 | 'v', |
| b69ab31 | | | 250 | 'd', |
| b69ab31 | | | 251 | ]); |
| b69ab31 | | | 252 | }); |
| b69ab31 | | | 253 | |
| b69ab31 | | | 254 | it('desc', () => { |
| b69ab31 | | | 255 | const sort = (s: SetLike) => [...dag.sortDesc(s)].join(' '); |
| b69ab31 | | | 256 | // sort all |
| b69ab31 | | | 257 | expect(sort(dag)).toBe('u f e v w x y d c b a'); |
| b69ab31 | | | 258 | // sort subset |
| b69ab31 | | | 259 | expect(sort(['a', 'f', 'b', 'c', 'e', 'd'])).toBe('f e d c b a'); |
| b69ab31 | | | 260 | expect(sort(['y', 'u', 'w', 'v', 'x'])).toBe('u v w x y'); |
| b69ab31 | | | 261 | expect(sort(['w', 'f', 'y'])).toBe('f w y'); |
| b69ab31 | | | 262 | expect(sort(['x', 'y', 'f', 'e'])).toBe('f e x y'); |
| b69ab31 | | | 263 | // custom sort function |
| b69ab31 | | | 264 | expect(dag.sortDesc(['c', 'x'], {compare: a => (a.hash === 'x' ? -1 : 1)})).toEqual([ |
| b69ab31 | | | 265 | 'x', |
| b69ab31 | | | 266 | 'c', |
| b69ab31 | | | 267 | ]); |
| b69ab31 | | | 268 | }); |
| b69ab31 | | | 269 | }); |
| b69ab31 | | | 270 | |
| b69ab31 | | | 271 | describe('resolve', () => { |
| b69ab31 | | | 272 | const dag = new Dag().add( |
| b69ab31 | | | 273 | [ |
| b69ab31 | | | 274 | {...info, hash: 'abc'}, |
| b69ab31 | | | 275 | {...info, hash: 'abd', bookmarks: ['foo', 'bar']}, |
| b69ab31 | | | 276 | {...info, hash: 'acc', remoteBookmarks: ['remote/foo', 'remote/main']}, |
| b69ab31 | | | 277 | {...info, hash: 'add', isDot: true}, |
| b69ab31 | | | 278 | {...info, hash: 'aee', remoteBookmarks: ['remote/bar'], bookmarks: ['baz']}, |
| b69ab31 | | | 279 | {...info, hash: 'aff'}, |
| b69ab31 | | | 280 | ].map(toInfo), |
| b69ab31 | | | 281 | ); |
| b69ab31 | | | 282 | |
| b69ab31 | | | 283 | it('supports "."', () => { |
| b69ab31 | | | 284 | expect(dag.resolve('.')?.hash).toBe('add'); |
| b69ab31 | | | 285 | }); |
| b69ab31 | | | 286 | |
| b69ab31 | | | 287 | it('supports hashes', () => { |
| b69ab31 | | | 288 | for (const h of ['abc', 'abd', 'aff']) { |
| b69ab31 | | | 289 | expect(dag.resolve(h)?.hash).toBe(h); |
| b69ab31 | | | 290 | } |
| b69ab31 | | | 291 | }); |
| b69ab31 | | | 292 | |
| b69ab31 | | | 293 | it('supports bookmarks', () => { |
| b69ab31 | | | 294 | expect(dag.resolve('foo')?.hash).toBe('abd'); |
| b69ab31 | | | 295 | expect(dag.resolve('bar')?.hash).toBe('abd'); |
| b69ab31 | | | 296 | expect(dag.resolve('baz')?.hash).toBe('aee'); |
| b69ab31 | | | 297 | }); |
| b69ab31 | | | 298 | |
| b69ab31 | | | 299 | it('supports remotenames', () => { |
| b69ab31 | | | 300 | expect(dag.resolve('remote/foo')?.hash).toBe('acc'); |
| b69ab31 | | | 301 | expect(dag.resolve('remote/main')?.hash).toBe('acc'); |
| b69ab31 | | | 302 | expect(dag.resolve('remote/bar')?.hash).toBe('aee'); |
| b69ab31 | | | 303 | }); |
| b69ab31 | | | 304 | |
| b69ab31 | | | 305 | it('supports hoisted remotenames', () => { |
| b69ab31 | | | 306 | expect(dag.resolve('main')?.hash).toBe('acc'); |
| b69ab31 | | | 307 | }); |
| b69ab31 | | | 308 | |
| b69ab31 | | | 309 | it('supports hash prefix', () => { |
| b69ab31 | | | 310 | expect(dag.resolve('af')?.hash).toBe('aff'); |
| b69ab31 | | | 311 | expect(dag.resolve('ac')?.hash).toBe('acc'); |
| b69ab31 | | | 312 | expect(dag.resolve('ab')?.hash).toBe(undefined); // ambiguous |
| b69ab31 | | | 313 | }); |
| b69ab31 | | | 314 | |
| b69ab31 | | | 315 | it('considers priorities between bookmarks and hashes', () => { |
| b69ab31 | | | 316 | const dag = new Dag().add( |
| b69ab31 | | | 317 | [ |
| b69ab31 | | | 318 | {...info, hash: 'foo'}, |
| b69ab31 | | | 319 | {...info, hash: 'bar', bookmarks: ['foo']}, |
| b69ab31 | | | 320 | {...info, hash: 'baz', bookmarks: ['fo']}, |
| b69ab31 | | | 321 | ].map(toInfo), |
| b69ab31 | | | 322 | ); |
| b69ab31 | | | 323 | // full hash > bookmark |
| b69ab31 | | | 324 | expect(dag.resolve('foo')?.hash).toBe('foo'); |
| b69ab31 | | | 325 | // bookmark > prefix |
| b69ab31 | | | 326 | expect(dag.resolve('fo')?.hash).toBe('baz'); |
| b69ab31 | | | 327 | }); |
| b69ab31 | | | 328 | |
| b69ab31 | | | 329 | it('moves "." with edits', () => { |
| b69ab31 | | | 330 | const dag1 = dag.replaceWith(['add', 'abc'], (h, c) => { |
| b69ab31 | | | 331 | return c?.set('isDot', h === 'abc'); |
| b69ab31 | | | 332 | }); |
| b69ab31 | | | 333 | expect(dag1.remove('abc').resolve('.')?.hash).toBe(undefined); |
| b69ab31 | | | 334 | }); |
| b69ab31 | | | 335 | |
| b69ab31 | | | 336 | it('resolves hoisted name when conflicted bookmark is removed', () => { |
| b69ab31 | | | 337 | // foo: abd (bookmark); acc (hoisted remote bookmark) |
| b69ab31 | | | 338 | // removing 'abc' will make foo resolve to acc. |
| b69ab31 | | | 339 | expect(dag.remove('abd').resolve('foo')?.hash).toBe('acc'); |
| b69ab31 | | | 340 | }); |
| b69ab31 | | | 341 | |
| b69ab31 | | | 342 | it('hash prefix works when ambiguous hashes are removed', () => { |
| b69ab31 | | | 343 | // 'ab' prefix: abc abd |
| b69ab31 | | | 344 | // removing 'abc' will make 'ab' resolve to 'abd'. |
| b69ab31 | | | 345 | expect(dag.remove('abc').resolve('ab')?.hash).toBe('abd'); |
| b69ab31 | | | 346 | }); |
| b69ab31 | | | 347 | }); |
| b69ab31 | | | 348 | |
| b69ab31 | | | 349 | describe('mutation', () => { |
| b69ab31 | | | 350 | // mutation: a-->a1-->a2-->a3 |
| b69ab31 | | | 351 | // dag: a1 a2 b. |
| b69ab31 | | | 352 | const dag = new Dag() |
| b69ab31 | | | 353 | .add( |
| b69ab31 | | | 354 | [ |
| b69ab31 | | | 355 | {...info, hash: 'a', successorInfo: {hash: 'a1', type: ''}}, |
| b69ab31 | | | 356 | {...info, hash: 'a1'}, |
| b69ab31 | | | 357 | {...info, hash: 'a2', closestPredecessors: ['a1']}, |
| b69ab31 | | | 358 | {...info, hash: 'a3', closestPredecessors: ['a2']}, |
| b69ab31 | | | 359 | {...info, hash: 'b', closestPredecessors: ['b0']}, |
| b69ab31 | | | 360 | ].map(toInfo), |
| b69ab31 | | | 361 | ) |
| b69ab31 | | | 362 | .remove(['a', 'a3']); |
| b69ab31 | | | 363 | |
| b69ab31 | | | 364 | it('followSuccessors()', () => { |
| b69ab31 | | | 365 | expect(dag.followSuccessors(['a', 'b']).toSortedArray()).toEqual(['a2', 'b']); |
| b69ab31 | | | 366 | expect(dag.followSuccessors(['a3']).toSortedArray()).toEqual(['a3']); |
| b69ab31 | | | 367 | expect(dag.followSuccessors(['a1', 'a2']).toSortedArray()).toEqual(['a2']); |
| b69ab31 | | | 368 | }); |
| b69ab31 | | | 369 | |
| b69ab31 | | | 370 | it('successors()', () => { |
| b69ab31 | | | 371 | expect(dag.successors(['a', 'b']).toSortedArray()).toEqual(['a', 'a1', 'a2', 'b']); |
| b69ab31 | | | 372 | expect(dag.successors(['a1', 'a2']).toSortedArray()).toEqual(['a1', 'a2']); |
| b69ab31 | | | 373 | }); |
| b69ab31 | | | 374 | |
| b69ab31 | | | 375 | it('predecessors()', () => { |
| b69ab31 | | | 376 | expect(dag.predecessors(['a', 'b']).toSortedArray()).toEqual(['b']); |
| b69ab31 | | | 377 | expect(dag.predecessors(['a2']).toSortedArray()).toEqual(['a1', 'a2']); |
| b69ab31 | | | 378 | expect(dag.predecessors(['a3']).toSortedArray()).toEqual(['a1', 'a2']); |
| b69ab31 | | | 379 | }); |
| b69ab31 | | | 380 | |
| b69ab31 | | | 381 | it('picks stack top when following a split', () => { |
| b69ab31 | | | 382 | // mutation: a->b a->c a->d |
| b69ab31 | | | 383 | // dag: a b--d--c. |
| b69ab31 | | | 384 | const dag = new Dag() |
| b69ab31 | | | 385 | .add( |
| b69ab31 | | | 386 | [ |
| b69ab31 | | | 387 | {...info, hash: 'a'}, |
| b69ab31 | | | 388 | {...info, hash: 'b', closestPredecessors: ['a']}, |
| b69ab31 | | | 389 | {...info, hash: 'c', closestPredecessors: ['a'], parents: ['d']}, |
| b69ab31 | | | 390 | {...info, hash: 'd', closestPredecessors: ['a'], parents: ['b']}, |
| b69ab31 | | | 391 | ].map(toInfo), |
| b69ab31 | | | 392 | ) |
| b69ab31 | | | 393 | .remove(['a']); |
| b69ab31 | | | 394 | // not ['d'] or ['b', 'c', 'd'] |
| b69ab31 | | | 395 | expect(dag.followSuccessors('a').toSortedArray()).toEqual(['c']); |
| b69ab31 | | | 396 | }); |
| b69ab31 | | | 397 | }); |
| b69ab31 | | | 398 | |
| b69ab31 | | | 399 | describe('rebase', () => { |
| b69ab31 | | | 400 | const succ = (h: Hash): Hash => `${REBASE_SUCC_PREFIX}${h}`; |
| b69ab31 | | | 401 | |
| b69ab31 | | | 402 | it('can break linear stack', () => { |
| b69ab31 | | | 403 | // a--b--c rebase -r c -d a |
| b69ab31 | | | 404 | let dag = new Dag().add( |
| b69ab31 | | | 405 | [ |
| b69ab31 | | | 406 | {...info, hash: 'a', parents: []}, |
| b69ab31 | | | 407 | {...info, hash: 'b', parents: ['a']}, |
| b69ab31 | | | 408 | {...info, hash: 'c', parents: ['b']}, |
| b69ab31 | | | 409 | ].map(toInfo), |
| b69ab31 | | | 410 | ); |
| b69ab31 | | | 411 | dag = dag.rebase(['c'], 'a'); |
| b69ab31 | | | 412 | expect(dag.parentHashes('c')).toEqual(['a']); |
| b69ab31 | | | 413 | }); |
| b69ab31 | | | 414 | |
| b69ab31 | | | 415 | it('skips already rebased branches', () => { |
| b69ab31 | | | 416 | // a--------b rebase -r c+d+e+f -d b |
| b69ab31 | | | 417 | // \ \ e f should not be touched. |
| b69ab31 | | | 418 | // c--d e--f |
| b69ab31 | | | 419 | let dag = new Dag().add( |
| b69ab31 | | | 420 | [ |
| b69ab31 | | | 421 | {...info, hash: 'a', parents: [], phase: PUBLIC}, |
| b69ab31 | | | 422 | {...info, hash: 'b', parents: ['a'], phase: PUBLIC}, |
| b69ab31 | | | 423 | {...info, hash: 'c', parents: ['a'], phase: DRAFT}, |
| b69ab31 | | | 424 | {...info, hash: 'd', parents: ['c'], phase: DRAFT}, |
| b69ab31 | | | 425 | {...info, hash: 'e', parents: ['b'], phase: DRAFT}, |
| b69ab31 | | | 426 | {...info, hash: 'f', parents: ['e'], phase: DRAFT}, |
| b69ab31 | | | 427 | ].map(toInfo), |
| b69ab31 | | | 428 | ); |
| b69ab31 | | | 429 | dag = dag.rebase(['c', 'd', 'e', 'f'], 'b'); |
| b69ab31 | | | 430 | |
| b69ab31 | | | 431 | // e and f should not be touched |
| b69ab31 | | | 432 | expect(dag.get('e')?.date).toEqual(date); |
| b69ab31 | | | 433 | expect(dag.get('f')?.date).toEqual(date); |
| b69ab31 | | | 434 | |
| b69ab31 | | | 435 | // c and d are touched |
| b69ab31 | | | 436 | expect(dag.get('c')?.date).not.toEqual(date); |
| b69ab31 | | | 437 | expect(dag.get('d')?.date).not.toEqual(date); |
| b69ab31 | | | 438 | |
| b69ab31 | | | 439 | // check b--e--f and b--c--d |
| b69ab31 | | | 440 | expect(dag.parentHashes('f')).toEqual(['e']); |
| b69ab31 | | | 441 | expect(dag.parentHashes('e')).toEqual(['b']); |
| b69ab31 | | | 442 | expect(dag.parentHashes('d')).toEqual(['c']); |
| b69ab31 | | | 443 | expect(dag.parentHashes('c')).toEqual(['b']); |
| b69ab31 | | | 444 | }); |
| b69ab31 | | | 445 | |
| b69ab31 | | | 446 | it('handles orphaned commits', () => { |
| b69ab31 | | | 447 | // a--b z; rebase -r a -d z; result: |
| b69ab31 | | | 448 | // a(pred)--b z--a(succ). |
| b69ab31 | | | 449 | let dag = new Dag().add( |
| b69ab31 | | | 450 | [ |
| b69ab31 | | | 451 | {...info, hash: 'z', parents: [], phase: PUBLIC}, |
| b69ab31 | | | 452 | {...info, hash: 'a', parents: [], phase: DRAFT}, |
| b69ab31 | | | 453 | {...info, hash: 'b', parents: ['a'], phase: DRAFT}, |
| b69ab31 | | | 454 | ].map(toInfo), |
| b69ab31 | | | 455 | ); |
| b69ab31 | | | 456 | dag = dag.rebase(['a'], 'z'); |
| b69ab31 | | | 457 | |
| b69ab31 | | | 458 | // check z--a(succ) |
| b69ab31 | | | 459 | expect(dag.parentHashes(succ('a'))).toEqual(['z']); |
| b69ab31 | | | 460 | expect(dag.get(succ('a'))?.date).not.toEqual(date); |
| b69ab31 | | | 461 | |
| b69ab31 | | | 462 | // check a(pred)--b |
| b69ab31 | | | 463 | expect(dag.parentHashes('b')).toEqual(['a']); |
| b69ab31 | | | 464 | expect(dag.parentHashes('a')).toEqual([]); |
| b69ab31 | | | 465 | expect(dag.get('a')?.date).toEqual(date); |
| b69ab31 | | | 466 | expect(dag.get('b')?.date).toEqual(date); |
| b69ab31 | | | 467 | }); |
| b69ab31 | | | 468 | |
| b69ab31 | | | 469 | it('handles non-continuous selection', () => { |
| b69ab31 | | | 470 | // a--b--c--d--e--f z; rebase b+c+e+f to z; result: |
| b69ab31 | | | 471 | // a--b(pred)--c(pred)--d; z--b(succ)--c(succ)--e--f |
| b69ab31 | | | 472 | let dag = new Dag().add( |
| b69ab31 | | | 473 | [ |
| b69ab31 | | | 474 | {...info, hash: 'a', parents: []}, |
| b69ab31 | | | 475 | {...info, hash: 'b', parents: ['a']}, |
| b69ab31 | | | 476 | {...info, hash: 'c', parents: ['b']}, |
| b69ab31 | | | 477 | {...info, hash: 'd', parents: ['c']}, // not rebasing |
| b69ab31 | | | 478 | {...info, hash: 'e', parents: ['d']}, |
| b69ab31 | | | 479 | {...info, hash: 'f', parents: ['e']}, |
| b69ab31 | | | 480 | {...info, hash: 'z', parents: []}, |
| b69ab31 | | | 481 | ].map(toInfo), |
| b69ab31 | | | 482 | ); |
| b69ab31 | | | 483 | dag = dag.rebase(['b', 'c', 'e', 'f'], 'z'); |
| b69ab31 | | | 484 | |
| b69ab31 | | | 485 | // check z--b(succ)--c(succ)--e--f |
| b69ab31 | | | 486 | expect(dag.parentHashes('f')).toEqual(['e']); |
| b69ab31 | | | 487 | expect(dag.parentHashes('e')).toEqual([succ('c')]); |
| b69ab31 | | | 488 | expect(dag.parentHashes(succ('c'))).toEqual([succ('b')]); |
| b69ab31 | | | 489 | expect(dag.parentHashes(succ('b'))).toEqual(['z']); |
| b69ab31 | | | 490 | |
| b69ab31 | | | 491 | // check a--b(pred)--c(pred)--c--d |
| b69ab31 | | | 492 | expect(dag.parentHashes('c')).toEqual(['b']); |
| b69ab31 | | | 493 | expect(dag.parentHashes('b')).toEqual(['a']); |
| b69ab31 | | | 494 | expect(dag.childHashes('d').toArray()).toEqual([]); |
| b69ab31 | | | 495 | |
| b69ab31 | | | 496 | // succ and pred info |
| b69ab31 | | | 497 | expect(dag.get('b')?.successorInfo?.hash).toEqual(succ('b')); |
| b69ab31 | | | 498 | expect(dag.get('c')?.successorInfo?.hash).toEqual(succ('c')); |
| b69ab31 | | | 499 | expect(dag.get(succ('b'))?.closestPredecessors).toEqual(['b']); |
| b69ab31 | | | 500 | expect(dag.get(succ('c'))?.closestPredecessors).toEqual(['c']); |
| b69ab31 | | | 501 | |
| b69ab31 | | | 502 | // orphaned and obsoleted b--c--d are not touched |
| b69ab31 | | | 503 | expect(dag.get('b')?.date).toEqual(date); |
| b69ab31 | | | 504 | expect(dag.get('c')?.date).toEqual(date); |
| b69ab31 | | | 505 | expect(dag.get('d')?.date).toEqual(date); |
| b69ab31 | | | 506 | }); |
| b69ab31 | | | 507 | |
| b69ab31 | | | 508 | it('cleans up obsoleted commits', () => { |
| b69ab31 | | | 509 | // a--b--c--f rebase -r f -d z |
| b69ab31 | | | 510 | // \ / b, c, d, e are obsoleted |
| b69ab31 | | | 511 | // -d--e- b is head |
| b69ab31 | | | 512 | // z check: c, d, e are removed |
| b69ab31 | | | 513 | const successorInfo: SuccessorInfo = {hash: 'z', type: 'rewrite'}; |
| b69ab31 | | | 514 | let dag = new Dag().add( |
| b69ab31 | | | 515 | [ |
| b69ab31 | | | 516 | {...info, hash: 'z', parents: [], phase: PUBLIC}, |
| b69ab31 | | | 517 | {...info, hash: 'a', parents: [], phase: DRAFT}, |
| b69ab31 | | | 518 | {...info, hash: 'b', parents: ['a'], phase: DRAFT, date, successorInfo, isDot: true}, |
| b69ab31 | | | 519 | {...info, hash: 'c', parents: ['b'], phase: DRAFT, date, successorInfo}, |
| b69ab31 | | | 520 | {...info, hash: 'd', parents: ['a'], phase: DRAFT, date, successorInfo}, |
| b69ab31 | | | 521 | {...info, hash: 'e', parents: ['d'], phase: DRAFT, date, successorInfo}, |
| b69ab31 | | | 522 | {...info, hash: 'f', parents: ['c', 'e'], phase: DRAFT, date}, |
| b69ab31 | | | 523 | ].map(toInfo), |
| b69ab31 | | | 524 | ); |
| b69ab31 | | | 525 | dag = dag.rebase(['f'], 'z'); |
| b69ab31 | | | 526 | expect(['b', 'c', 'd', 'e'].filter(h => dag.has(h))).toEqual(['b']); |
| b69ab31 | | | 527 | }); |
| b69ab31 | | | 528 | }); |
| b69ab31 | | | 529 | |
| b69ab31 | | | 530 | describe('connect public commits', () => { |
| b69ab31 | | | 531 | it('connect with grandparents info', () => { |
| b69ab31 | | | 532 | // z-w x y => z-x-y |
| b69ab31 | | | 533 | // \ |
| b69ab31 | | | 534 | // w |
| b69ab31 | | | 535 | const dag = new Dag().add( |
| b69ab31 | | | 536 | [ |
| b69ab31 | | | 537 | {...info, hash: 'z', phase: PUBLIC}, |
| b69ab31 | | | 538 | {...info, hash: 'x', phase: PUBLIC, parents: ['a'], grandparents: ['z']}, |
| b69ab31 | | | 539 | {...info, hash: 'y', phase: PUBLIC, parents: ['b'], grandparents: ['x']}, |
| b69ab31 | | | 540 | {...info, hash: 'w', phase: PUBLIC, parents: ['z']}, |
| b69ab31 | | | 541 | ].map(toInfo), |
| b69ab31 | | | 542 | ); |
| b69ab31 | | | 543 | expect(dag.children('z').toSortedArray()).toEqual(['w', 'x']); |
| b69ab31 | | | 544 | expect(dag.children('x').toSortedArray()).toEqual(['y']); |
| b69ab31 | | | 545 | expect(dag.children('y').toSortedArray()).toEqual([]); |
| b69ab31 | | | 546 | expect(dag.children('w').toSortedArray()).toEqual([]); |
| b69ab31 | | | 547 | }); |
| b69ab31 | | | 548 | |
| b69ab31 | | | 549 | it('forceConnectPublic() without grandparents info', () => { |
| b69ab31 | | | 550 | // z-w x y => z-x-y |
| b69ab31 | | | 551 | // \ |
| b69ab31 | | | 552 | // w |
| b69ab31 | | | 553 | const dag = new Dag() |
| b69ab31 | | | 554 | .add( |
| b69ab31 | | | 555 | [ |
| b69ab31 | | | 556 | {...info, hash: 'z', phase: PUBLIC, date: new Date(1)}, |
| b69ab31 | | | 557 | {...info, hash: 'x', phase: PUBLIC, date: new Date(2)}, |
| b69ab31 | | | 558 | {...info, hash: 'y', phase: PUBLIC, date: new Date(3)}, |
| b69ab31 | | | 559 | {...info, hash: 'w', phase: PUBLIC, date: new Date(3), parents: ['z']}, |
| b69ab31 | | | 560 | ].map(toInfo), |
| b69ab31 | | | 561 | ) |
| b69ab31 | | | 562 | .maybeForceConnectPublic(); |
| b69ab31 | | | 563 | // Without grandparents info, fallback to chronological connections. |
| b69ab31 | | | 564 | expect(dag.children('z').toSortedArray()).toEqual(['w', 'x']); |
| b69ab31 | | | 565 | expect(dag.children('x').toSortedArray()).toEqual(['y']); |
| b69ab31 | | | 566 | expect(dag.children('y').toSortedArray()).toEqual([]); |
| b69ab31 | | | 567 | // w is not a root so it does not need fix. |
| b69ab31 | | | 568 | expect(dag.children('w').toSortedArray()).toEqual([]); |
| b69ab31 | | | 569 | }); |
| b69ab31 | | | 570 | }); |
| b69ab31 | | | 571 | |
| b69ab31 | | | 572 | it('renders to ASCII text', () => { |
| b69ab31 | | | 573 | // a--b--c |
| b69ab31 | | | 574 | // / \ |
| b69ab31 | | | 575 | // z d |
| b69ab31 | | | 576 | const dag = new Dag().add( |
| b69ab31 | | | 577 | [ |
| b69ab31 | | | 578 | {...info, phase: PUBLIC, hash: 'a', parents: []}, |
| b69ab31 | | | 579 | {...info, phase: PUBLIC, hash: 'z', parents: []}, |
| b69ab31 | | | 580 | {...info, phase: PUBLIC, hash: 'b', parents: ['a', 'z']}, |
| b69ab31 | | | 581 | {...info, phase: PUBLIC, hash: 'c', parents: ['b']}, |
| b69ab31 | | | 582 | {...info, phase: DRAFT, hash: 'd', parents: ['c']}, |
| b69ab31 | | | 583 | ].map(toInfo), |
| b69ab31 | | | 584 | ); |
| b69ab31 | | | 585 | |
| b69ab31 | | | 586 | expect(dag.renderAscii()).toMatchInlineSnapshot(` |
| b69ab31 | | | 587 | " |
| b69ab31 | | | 588 | o d |
| b69ab31 | | | 589 | │ |
| b69ab31 | | | 590 | ╭─╯ |
| b69ab31 | | | 591 | o c |
| b69ab31 | | | 592 | │ |
| b69ab31 | | | 593 | o b |
| b69ab31 | | | 594 | │ |
| b69ab31 | | | 595 | ├─╮ |
| b69ab31 | | | 596 | o │ a |
| b69ab31 | | | 597 | │ |
| b69ab31 | | | 598 | o z" |
| b69ab31 | | | 599 | `); |
| b69ab31 | | | 600 | |
| b69ab31 | | | 601 | // Render a subset. |
| b69ab31 | | | 602 | // [a, c] subset: edge is dashed. |
| b69ab31 | | | 603 | expect(dag.renderAscii(['a', 'c'])).toMatchInlineSnapshot(` |
| b69ab31 | | | 604 | " |
| b69ab31 | | | 605 | o c |
| b69ab31 | | | 606 | │ |
| b69ab31 | | | 607 | : |
| b69ab31 | | | 608 | o a" |
| b69ab31 | | | 609 | `); |
| b69ab31 | | | 610 | // [b, d] subset: indents "d" (draft), and "b" has an "~". |
| b69ab31 | | | 611 | expect(dag.renderAscii(['b', 'd'])).toMatchInlineSnapshot(` |
| b69ab31 | | | 612 | " |
| b69ab31 | | | 613 | o d |
| b69ab31 | | | 614 | │ |
| b69ab31 | | | 615 | ╭─╯ |
| b69ab31 | | | 616 | : |
| b69ab31 | | | 617 | o b |
| b69ab31 | | | 618 | │ |
| b69ab31 | | | 619 | │ |
| b69ab31 | | | 620 | ~" |
| b69ab31 | | | 621 | `); |
| b69ab31 | | | 622 | }); |
| b69ab31 | | | 623 | }); |
| b69ab31 | | | 624 | |
| b69ab31 | | | 625 | describe('HashSet', () => { |
| b69ab31 | | | 626 | it('preserves order on intersect', () => { |
| b69ab31 | | | 627 | const a = HashSet.fromHashes(['c', 'b', 'e', 'd', 'a', 'f']); |
| b69ab31 | | | 628 | expect(a.intersect(['d', 'b']).toArray()).toEqual(['b', 'd']); |
| b69ab31 | | | 629 | expect(a.intersect(['b', 'd']).toArray()).toEqual(['b', 'd']); |
| b69ab31 | | | 630 | }); |
| b69ab31 | | | 631 | |
| b69ab31 | | | 632 | it('preserves order on substract', () => { |
| b69ab31 | | | 633 | const a = HashSet.fromHashes(['c', 'b', 'e', 'd', 'a', 'f']); |
| b69ab31 | | | 634 | expect(a.subtract(['d', 'b']).toArray()).toEqual(['c', 'e', 'a', 'f']); |
| b69ab31 | | | 635 | expect(a.subtract(['b', 'd']).toArray()).toEqual(['c', 'e', 'a', 'f']); |
| b69ab31 | | | 636 | expect(a.subtract(['f', 'c', 'e']).toArray()).toEqual(['b', 'd', 'a']); |
| b69ab31 | | | 637 | }); |
| b69ab31 | | | 638 | |
| b69ab31 | | | 639 | it('preserves order on union', () => { |
| b69ab31 | | | 640 | const a = HashSet.fromHashes(['d', 'a', 'c']); |
| b69ab31 | | | 641 | expect(a.union(['x', 'z', 'y']).toArray()).toEqual(['d', 'a', 'c', 'x', 'z', 'y']); |
| b69ab31 | | | 642 | expect(a.union(['y', 'z', 'x']).toArray()).toEqual(['d', 'a', 'c', 'y', 'z', 'x']); |
| b69ab31 | | | 643 | |
| b69ab31 | | | 644 | expect(a.union(['a', 'd']).toArray()).toEqual(['d', 'a', 'c']); |
| b69ab31 | | | 645 | expect(a.union(['d', 'a']).toArray()).toEqual(['d', 'a', 'c']); |
| b69ab31 | | | 646 | |
| b69ab31 | | | 647 | expect(a.union(['a', 'b']).toArray()).toEqual(['d', 'a', 'c', 'b']); |
| b69ab31 | | | 648 | expect(a.union(['f', 'c', 'a', 'd', 'e']).toArray()).toEqual(['d', 'a', 'c', 'f', 'e']); |
| b69ab31 | | | 649 | }); |
| b69ab31 | | | 650 | }); |