1// Copyright (c) Jupyter Development Team. 2// Distributed under the terms of the Modified BSD License. 3'use strict'; 4 5import * as nbformat from '@jupyterlab/nbformat'; 6 7import { 8 Signal 9} from '@lumino/signaling'; 10 11import { 12 IDiffAddRange, IDiffEntry, IDiffArrayEntry, 13 IDiffPatchObject, IDiffImmutableObjectEntry 14} from '../../diff/diffentries'; 15 16import { 17 getDiffEntryByKey 18} from '../../diff/util'; 19 20import { 21 CellDiffModel, 22 createAddedCellDiffModel, createDeletedCellDiffModel, 23 createPatchedCellDiffModel, createUnchangedCellDiffModel, 24 OutputDiffModel, makeOutputModels, ImmutableDiffModel, 25 setMimetypeFromCellType, createImmutableModel 26} from '../../diff/model'; 27 28import { 29 MergeDecision, resolveCommonPaths, buildDiffs, decisionSortKey, 30 filterDecisions, pushPatchDecision, popPath, applyDecisions, 31 Action 32} from '../../merge/decisions'; 33 34import { 35 patch 36} from '../../patch'; 37 38import { 39 arraysEqual, valueIn, hasEntries, splitLines, unique, stableSort 40} from '../../common/util'; 41 42import { 43 splitMergeDecisionsOnChunks 44} from '../../chunking'; 45 46import { 47 ObjectMergeModel, DecisionStringDiffModel 48} from './common'; 49 50 51import { 52 NotifyUserError 53} from '../../common/exceptions'; 54 55 56/** 57 * Create a cell diff model based on a set of merge 58 * decisions that patch the cell. 59 */ 60function createPatchedCellDecisionDiffModel( 61 base: nbformat.ICell, decisions: MergeDecision[], 62 local: CellDiffModel | null, remote: CellDiffModel | null, 63 mimetype: string): 64 CellDiffModel { 65 66 for (let md of decisions) { 67 if (md.localPath.length === 0) { 68 let val = popPath(md.diffs, true); 69 if (val !== null) { 70 md.diffs = val.diffs; 71 md.pushPath(val.key); 72 } 73 } 74 } 75 76 let source = new DecisionStringDiffModel( 77 base.source, filterDecisions(decisions, ['source'], 2), 78 [local ? local.source : null, 79 remote ? remote.source : null]); 80 setMimetypeFromCellType(source, base, mimetype); 81 82 let metadata = new DecisionStringDiffModel( 83 base.metadata, filterDecisions(decisions, ['metadata'], 2), 84 [local ? local.metadata : null, 85 remote ? remote.metadata : null]); 86 87 let outputs: OutputDiffModel[] | null = null; 88 let executionCount: ImmutableDiffModel | null = null; 89 if (nbformat.isCode(base)) { 90 if (base.outputs) { 91 let outputBase = base.outputs; 92 let outputDec = filterDecisions(decisions, ['outputs'], 2); 93 let mergedDiff = buildDiffs(outputBase, outputDec, 'merged') as IDiffArrayEntry[]; 94 let merged: nbformat.IOutput[]; 95 if (mergedDiff && mergedDiff.length > 0) { 96 merged = patch(outputBase, mergedDiff); 97 } else { 98 merged = outputBase; 99 } 100 outputs = makeOutputModels(outputBase, merged, mergedDiff); 101 } 102 let execBase = base.execution_count; 103 let cellDecs = filterDecisions(decisions, ['cells'], 0, 2); 104 for (let dec of cellDecs) { 105 if (getDiffEntryByKey(dec.localDiff, 'execution_count') !== null || 106 getDiffEntryByKey(dec.remoteDiff, 'execution_count') !== null || 107 getDiffEntryByKey(dec.customDiff, 'execution_count') !== null) { 108 dec.level = 2; 109 let mergeExecDiff = buildDiffs(base, [dec], 'merged') as IDiffImmutableObjectEntry[] | null; 110 let execDiff = hasEntries(mergeExecDiff) ? mergeExecDiff[0] : null; 111 // Pass base as remote, which means fall back to unchanged if no diff: 112 executionCount = createImmutableModel(execBase, execBase, execDiff); 113 } 114 } 115 116 } 117 118 return new CellDiffModel(source, metadata, outputs, executionCount, base.cell_type); 119} 120 121 122/** 123 * CellMergeModel 124 */ 125export 126class CellMergeModel extends ObjectMergeModel<nbformat.ICell, CellDiffModel> { 127 constructor(base: nbformat.ICell | null, decisions: MergeDecision[], mimetype: string) { 128 // TODO: Remove/extend whitelist once we support more 129 super(base, [], mimetype, ['source', 'metadata', 'outputs', 'execution_count']); 130 this.onesided = false; 131 this._deleteCell = false; 132 this.processDecisions(decisions); 133 } 134 135 /** 136 * Whether the cell is present in only one of the two side (local/remote) 137 */ 138 onesided: boolean; 139 140 /** 141 * Run time flag whether the user wants to delete the cell 142 * 143 * @type {boolean} 144 */ 145 get deleteCell(): boolean { 146 return this._deleteCell; 147 } 148 set deleteCell(value: boolean) { 149 if (this._deleteCell !== value) { 150 this._deleteCell = value; 151 this.deleteCellChanged.emit(value); 152 } 153 } 154 private _deleteCell: boolean; 155 156 readonly deleteCellChanged = new Signal<CellMergeModel, boolean>(this); 157 158 159 /** 160 * Run time flag whether the user wants to clear the outputs of the cell 161 * 162 * @type {boolean} 163 */ 164 get clearOutputs(): boolean { 165 return this._clearOutputs; 166 } 167 set clearOutputs(value: boolean) { 168 if (this._clearOutputs !== value) { 169 this._clearOutputs = value; 170 this.clearOutputsChanged.emit(value); 171 } 172 } 173 private _clearOutputs = false; 174 175 readonly clearOutputsChanged = new Signal<CellMergeModel, boolean>(this); 176 177 /** 178 * Whether source is the same in local and remote 179 */ 180 get agreedSource(): boolean { 181 return !!this.local && !!this.remote && 182 this.local.source.remote === this.remote.source.remote; 183 } 184 185 /** 186 * Whether metadata is the same in local and remote 187 */ 188 get agreedMetadata(): boolean { 189 if (!this.local || !this.remote) { 190 return false; 191 } 192 return this.local.metadata.remote === this.remote.metadata.remote; 193 } 194 195 /** 196 * Whether outputs are the same in local and remote 197 */ 198 get agreedOutputs(): boolean { 199 if (!this.local || !this.remote) { 200 return false; 201 } 202 let lo = this.local.outputs; 203 let ro = this.remote.outputs; 204 if (!hasEntries(lo) || !hasEntries(ro)) { 205 return !hasEntries(lo) && !hasEntries(ro); 206 } 207 if (lo.length !== ro.length) { 208 return false; 209 } 210 for (let i=0; i < lo.length; ++i) { 211 if (JSON.stringify(lo[i].remote) !== JSON.stringify(ro[i].remote)) { 212 return false; 213 } 214 } 215 return true; 216 } 217 218 /** 219 * Whether cell is the same in local and remote 220 */ 221 get agreedCell(): boolean { 222 // TODO: Also check other fields? 223 return this.agreedSource && this.agreedMetadata && this.agreedOutputs; 224 } 225 226 /** 227 * Whether the cell has any conflicted decisions. 228 */ 229 get conflicted(): boolean { 230 for (let dec of this.decisions) { 231 if (dec.conflict) { 232 return true; 233 } 234 } 235 return false; 236 } 237 238 /** 239 * Whether the cell has any conflicted decisions on a specific key. 240 */ 241 hasConflictsOn(key: string) { 242 let decs = filterDecisions(this.decisions, [key], 2); 243 for (let dec of decs) { 244 if (dec.conflict) { 245 return true; 246 } 247 } 248 return false; 249 } 250 251 /** 252 * Whether the cell has any conflicted decisions on source. 253 */ 254 get sourceConflicted(): boolean { 255 return this.hasConflictsOn('source'); 256 } 257 258 /** 259 * Whether the cell has any conflicted decisions on metadata. 260 */ 261 get metadataConflicted(): boolean { 262 return this.hasConflictsOn('metadata'); 263 } 264 265 /** 266 * Whether the cell has any conflicted decisions. 267 */ 268 get outputsConflicted(): boolean { 269 return this.hasConflictsOn('outputs'); 270 } 271 272 /** 273 * Clear any conflicts on decisions on outputs 274 */ 275 clearOutputConflicts() { 276 let decs = filterDecisions(this.decisions, ['outputs'], 2); 277 for (let dec of decs) { 278 dec.conflict = false; 279 } 280 } 281 282 /** 283 * Get the decision on `execution_count` field (should only be one). 284 * 285 * Returns null if no decision on `execution_count` was found. 286 */ 287 getExecutionCountDecision(): MergeDecision | null { 288 let cellDecs = filterDecisions(this.decisions, ['cells'], 0, 2); 289 for (let dec of cellDecs) { 290 if (getDiffEntryByKey(dec.localDiff, 'execution_count') !== null || 291 getDiffEntryByKey(dec.remoteDiff, 'execution_count') !== null || 292 getDiffEntryByKey(dec.customDiff, 'execution_count') !== null) { 293 return dec; 294 } 295 } 296 return null; 297 } 298 299 /** 300 * Apply merge decisions to create the merged cell 301 */ 302 serialize(): nbformat.ICell | null { 303 if (this.deleteCell) { 304 return null; 305 } 306 if (this.base === null) { 307 // Only possibility is that cell is added 308 if (this.decisions.length > 1 || !this.merged.added) { 309 throw new NotifyUserError('Invalid cell decision'); 310 } 311 let dec = this.decisions[0]; 312 // Either onesided or identical inserts, but possibly with 313 // a custom diff on top! 314 let d: IDiffEntry; 315 if (dec.action === 'local' || dec.action === 'either') { 316 if (!dec.localDiff ) { 317 throw new NotifyUserError('Invalid cell decision'); 318 } 319 d = dec.localDiff[0]; 320 } else if (dec.action === 'remote') { 321 if (!dec.remoteDiff ) { 322 throw new NotifyUserError('Invalid cell decision'); 323 } 324 d = dec.remoteDiff[0]; 325 } else if (dec.action === 'custom') { 326 if (!dec.customDiff ) { 327 throw new NotifyUserError('Invalid cell decision'); 328 } 329 d = dec.customDiff[0]; 330 } else { 331 throw new NotifyUserError('Invalid cell decision'); 332 } 333 if (d.op !== 'addrange') { 334 throw new NotifyUserError('Invalid cell decision'); 335 } 336 return d.valuelist[0]; 337 } 338 let decisions: MergeDecision[] = []; 339 for (let md of this.decisions) { 340 let nmd = new MergeDecision(md); 341 nmd.level = 2; 342 decisions.push(nmd); 343 } 344 let output = applyDecisions(this.base, decisions); 345 let src = output.source; 346 if (Array.isArray(src)) { 347 src = src.join(''); 348 } 349 if (src !== this._merged!.source.remote) { 350 console.warn('Serialized outputs doesn\'t match model value! ' + 351 'Keeping the model value.'); 352 output.source = splitLines(this._merged!.source.remote!); 353 } 354 if (this.clearOutputs && nbformat.isCode(output)) { 355 output.outputs = []; 356 } 357 return output; 358 } 359 360 protected processDecisions(decisions: MergeDecision[]): void { 361 // First check for cell-level decisions: 362 if (decisions.length === 1) { 363 if (arraysEqual(decisions[0].absolutePath, ['cells'])) { 364 // We have a cell level decision 365 let md = decisions[0]; 366 decisions = this.applyCellLevelDecision(md); 367 if (decisions.length === 0) { 368 this.decisions.push(md); 369 } 370 } 371 } 372 373 for (let md of decisions) { 374 md.level = 2; 375 if (md.absolutePath.length < 2 || 376 md.absolutePath[0] !== 'cells') { 377 throw new Error('Not a valid path for a cell decision'); 378 } else if (md.absolutePath.length === 2 && ( 379 hasEntries(md.localDiff) || hasEntries(md.remoteDiff))) { 380 // Have decision on /cells/X/. 381 // Split the decision on subkey: 382 383 // Nest diff as a patch on cell, which can be split by `splitPatch`: 384 let splitDec = pushPatchDecision(md, md.absolutePath.slice(1, 2)); 385 let localDiff = hasEntries(splitDec.localDiff) ? 386 splitDec.localDiff[0] as IDiffPatchObject : null; 387 let remoteDiff = hasEntries(splitDec.remoteDiff) ? 388 splitDec.remoteDiff[0] as IDiffPatchObject : null; 389 390 let subDecisions = this.splitPatch(splitDec, localDiff, remoteDiff); 391 // Add all split decisions: 392 for (let subdec of subDecisions) { 393 subdec.level = 2; 394 this.decisions.push(subdec); 395 } 396 } else { // Decision has path on subkey 397 // Make local path relative to cell 398 this.decisions.push(md); 399 } 400 } 401 } 402 403 /** 404 * Apply a cell level decision to the model 405 * 406 * This creates the revelant kinds of models 407 */ 408 protected applyCellLevelDecision(md: MergeDecision): MergeDecision[] { 409 let newDecisions: MergeDecision[] = []; 410 /* Possibilities: 411 1. Insertion: base is null! Null diff of missing side (unchanged). 412 2. Deletion: Null diff of present side (unchanged). Set deleteCell 413 depending on action. 414 3. Deletion vs patch: Same as 2., but split patch decision onto 415 source/metadata/outputs. 416 4. Identical ops (insertion or deletion) 417 Cases that shouldn't happen: 418 5. Insertion vs insertion: Shouldn't happen! Should have been split 419 into two decisions with an insertion each before creating model. 420 6. Patch vs patch: Shouldn't occur, as those should have been recursed 421 */ 422 console.assert(!this.onesided, 423 'Cannot have multiple cell decisions on one cell!'); 424 this.onesided = true; // We set this to distinguish case 3 from normal 425 if (!hasEntries(md.localDiff)) { 426 // 1. or 2.: 427 this._local = null; 428 if (!md.remoteDiff || md.remoteDiff.length !== 1) { 429 throw new Error('Merge decision does not conform to expectation: ' + md); 430 } 431 if (this.base === null) { 432 // 1. 433 let first = md.remoteDiff[0]; 434 if (first.op !== 'addrange') { 435 throw new Error('Merge decision does not conform to expectation: ' + md); 436 } 437 let v = first.valuelist[0] as nbformat.ICell; 438 this._remote = createAddedCellDiffModel(v, this.mimetype); 439 this._merged = createAddedCellDiffModel(v, this.mimetype); 440 } else { 441 // 2. 442 this._remote = createDeletedCellDiffModel(this.base, this.mimetype); 443 this._merged = createDeletedCellDiffModel(this.base, this.mimetype); 444 this.deleteCell = valueIn(md.action, ['remote', 'either']); 445 } 446 } else if (!hasEntries(md.remoteDiff)) { 447 // 1. or 2.: 448 this._remote = null; 449 if (!md.localDiff || md.localDiff.length !== 1) { 450 throw new Error('Merge decision does not conform to expectation: ' + md); 451 } 452 if (this.base === null) { 453 // 1. 454 let first = md.localDiff[0]; 455 if (first.op !== 'addrange') { 456 throw new Error('Merge decision does not conform to expectation: ' + md); 457 } 458 let v = first.valuelist[0] as nbformat.ICell; 459 this._local = createAddedCellDiffModel(v, this.mimetype); 460 this._merged = createAddedCellDiffModel(v, this.mimetype); 461 } else { 462 // 2. 463 this._local = createDeletedCellDiffModel(this.base, this.mimetype); 464 this._merged = createDeletedCellDiffModel(this.base, this.mimetype); 465 this.deleteCell = valueIn(md.action, ['local', 'either']); 466 } 467 } else { 468 console.assert(hasEntries(md.localDiff) && hasEntries(md.remoteDiff)); 469 console.assert(md.localDiff.length === 1 && md.remoteDiff.length === 1); 470 // 3. or 4. 471 if (md.localDiff[0].op === md.remoteDiff[0].op) { 472 // 4. 473 if (this.base === null) { 474 // Identical insertions (this relies on preprocessing to ensure only 475 // one value in valuelist) 476 let v = (md.localDiff[0] as IDiffAddRange).valuelist[0]; 477 this._local = createAddedCellDiffModel(v, this.mimetype); 478 this._remote = createAddedCellDiffModel(v, this.mimetype); 479 this._merged = createAddedCellDiffModel(v, this.mimetype); 480 } else { 481 // Identical delections 482 this._local = createDeletedCellDiffModel(this.base, this.mimetype); 483 this._remote = createDeletedCellDiffModel(this.base, this.mimetype); 484 this._merged = createDeletedCellDiffModel(this.base, this.mimetype); 485 this.deleteCell = valueIn(md.action, ['local', 'remote', 'either']); 486 } 487 } else { 488 // 3., by method of elimination 489 let ops = [md.localDiff[0].op, md.remoteDiff[0].op]; 490 console.assert( 491 valueIn('removerange', ops) && valueIn('patch', ops)); 492 if (this.base === null) { 493 throw new Error('Invalid merge decision, ' + 494 'cannot have null base for deleted cell: ' + md); 495 } 496 if (ops[0] === 'removerange') { 497 this._local = createDeletedCellDiffModel(this.base, this.mimetype); 498 this.deleteCell = md.action === 'local'; 499 // The patch op will be on cell level. Split it on sub keys! 500 newDecisions = newDecisions.concat(this.splitPatch( 501 md, null, md.remoteDiff[0] as IDiffPatchObject)); 502 } else { 503 this._remote = createDeletedCellDiffModel(this.base, this.mimetype); 504 this.deleteCell = md.action === 'remote'; 505 // The patch op will be on cell level. Split it on sub keys! 506 newDecisions = newDecisions.concat(this.splitPatch( 507 md, md.localDiff[0] as IDiffPatchObject, null)); 508 } 509 resolveCommonPaths(newDecisions); 510 } 511 } 512 return newDecisions; 513 } 514 515 516 /** 517 * Split a decision with a patch on one side into one decision 518 * for each sub entry in the patch. 519 */ 520 protected splitPatch(md: MergeDecision, localPatch: IDiffPatchObject | null, remotePatch: IDiffPatchObject | null): MergeDecision[] { 521 let local = !!localPatch && hasEntries(localPatch.diff); 522 let remote = !!remotePatch && hasEntries(remotePatch.diff); 523 if (!local && !remote) { 524 return []; 525 } 526 let localDiff = local ? localPatch!.diff : null; 527 let remoteDiff = remote ? remotePatch!.diff : null; 528 let split: MergeDecision[] = []; 529 let keys: (string | number)[] = []; 530 if (local) { 531 for (let d of localDiff!) { 532 keys.push(d.key); 533 } 534 } 535 if (remote) { 536 for (let d of remoteDiff!) { 537 keys.push(d.key); 538 } 539 } 540 keys = keys.filter(unique); 541 if (local && remote) { 542 // Sanity check 543 if (localPatch!.key !== remotePatch!.key) { 544 throw new Error('Different keys of patch ops given to `splitPatch`.'); 545 } 546 } 547 let patchKey = local ? localPatch!.key : remotePatch!.key; 548 for (let key of keys) { 549 if (this._whitelist && !valueIn(key, this._whitelist)) { 550 throw new NotifyUserError('Currently not able to handle decisions on variable \"' + 551 key + '\"'); 552 } 553 let el = getDiffEntryByKey(localDiff, key); 554 let er = getDiffEntryByKey(remoteDiff, key); 555 let onsesided = !(el && er); 556 let action: Action = md.action; 557 // If one-sided, change 'base' actions to present side 558 if (action === 'base' && onsesided) { 559 action = el ? 'local' : 'remote'; 560 } 561 // Create new action: 562 split.push(new MergeDecision( 563 md.absolutePath.concat([patchKey]), 564 el ? [el] : null, 565 er ? [er] : null, 566 action, 567 md.conflict)); 568 } 569 let ret = this.splitOnSourceChunks(split); 570 resolveCommonPaths(ret); 571 return stableSort(ret, decisionSortKey); 572 } 573 574 /** 575 * Split decisions on 'source' by chunks. 576 * 577 * This prevents one decision from contributing to more than one chunk. 578 */ 579 protected splitOnSourceChunks(decisions: MergeDecision[]): MergeDecision[] { 580 let out: MergeDecision[] = []; 581 for (let i=0; i < decisions.length; ++i) { 582 let dec = decisions[i]; 583 if (dec.absolutePath[2] === 'source') { 584 let base = this.base!.source; 585 if (!Array.isArray(base)) { 586 base = splitLines(base); 587 } 588 dec.level = 3; 589 let sub = splitMergeDecisionsOnChunks(base, [dec]); 590 resolveCommonPaths(sub); 591 out = out.concat(stableSort(sub, decisionSortKey)); 592 } else { 593 out.push(dec); 594 } 595 } 596 return out; 597 } 598 599 protected createDiffModel(diff: IDiffEntry[]): CellDiffModel { 600 if (this.base === null) { 601 throw new Error('Cannot create a patched or unchanged diff model with null base!'); 602 } 603 if (diff && diff.length > 0) { 604 return createPatchedCellDiffModel(this.base, diff, this.mimetype); 605 } else { 606 return createUnchangedCellDiffModel(this.base, this.mimetype); 607 } 608 } 609 610 protected createMergedDiffModel(): CellDiffModel { 611 if (this.base === null) { 612 throw new Error('Cannot create a patched or unchanged merged diff model with null base!'); 613 } 614 return createPatchedCellDecisionDiffModel( 615 this.base, this.decisions, this.local, this.remote, this.mimetype); 616 } 617} 618