import { Pointer } from './pointer' ; import { hasOwnProperty , objectType } from './util' ; /**
All diff* functions should return a list of operations, often empty.

Each operation should be an object with two to four fields:
* `op`: the name of the operation; one of "add", "remove", "replace", "move",
  "copy", or "test".
* `path`: a JSON pointer string
* `from`: a JSON pointer string
* `value`: a JSON value

The different operations have different arguments.
* "add": [`path`, `value`]
* "remove": [`path`]
* "replace": [`path`, `value`]
* "move": [`from`, `path`]
* "copy": [`from`, `path`]
* "test": [`path`, `value`]

Currently this only really differentiates between Arrays, Objects, and
Everything Else, which is pretty much just what JSON substantially
differentiates between.
*/ export interface AddOperation { op : 'add' ; path : string ; value : any ; } export interface RemoveOperation { op : 'remove' ; path : string ; } export interface ReplaceOperation { op : 'replace' ; path : string ; value : any ; } export interface MoveOperation { op : 'move' ; from : string ; path : string ; } export interface CopyOperation { op : 'copy' ; from : string ; path : string ; } export interface TestOperation { op : 'test' ; path : string ; value : any ; } export type Operation = AddOperation | RemoveOperation | ReplaceOperation | MoveOperation | CopyOperation | TestOperation ; export function isDestructive ( { op } ) { return op === 'remove' || op === 'replace' || op === 'copy' || op === 'move' ; } export type Diff = ( input : any , output : any , ptr : Pointer ) => Operation [ ] ; /**
VoidableDiff exists to allow the user to provide a partial diff(...) function,
falling back to the built-in diffAny(...) function if the user-provided function
returns void.
*/ export type VoidableDiff = ( input : any , output : any , ptr : Pointer ) => Operation [ ] | void ; param minuend param subtrahend returns export function subtract ( minuend , subtrahend ) { const obj = { } ; for ( const add_key in minuend ) { if ( hasOwnProperty . call ( minuend , add_key ) && minuend [ add_key ] !== undefined ) { obj [ add_key ] = 1 ; } } for ( const del_key in subtrahend ) { if ( hasOwnProperty . call ( subtrahend , del_key ) && subtrahend [ del_key ] !== undefined ) { delete obj [ del_key ] ; } } return Object . keys ( obj ) ; } /**
List the keys that shared by all `objects`.

The semantics of what constitutes a "key" is described in  subtract .

 param objects returns export function intersection ( objects ) { const length = objects . length ; const counter = { } ; for ( let i = 0 ; i < length ; i ++ ) { const object = objects [ i ] ; for ( const key in object ) { if ( hasOwnProperty . call ( object , key ) && object [ key ] !== undefined ) { counter [ key ] = ( counter [ key ] || 0 ) + 1 ; } } } for ( const key in counter ) { if ( counter [ key ] < length ) { delete counter [ key ] ; } } return Object . keys ( counter ) ; } interface ArrayAdd { op : 'add' ; index : number ; value : any ; } interface ArrayRemove { op : 'remove' ; index : number ; } interface ArrayReplace { op : 'replace' ; index : number ; original : any ; value : any ; } /** These are not proper Operation objects, but will be converted into
Operation objects eventually. {index} indicates the actual target position,
never 'end-of-array' */ type ArrayOperation = ArrayAdd | ArrayRemove | ArrayReplace ; function isArrayAdd ( array_operation ) { return array_operation . op === 'add' ; } function isArrayRemove ( array_operation ) { return array_operation . op === 'remove' ; } interface DynamicAlternative { operations : ArrayOperation [ ] ; /**
    cost indicates the total cost of getting to this position.
    */ cost : number ; } function appendArrayOperation ( base , operation ) { return { operations : base . operations . concat ( operation ) , cost : base . cost + 1 , } ; } returns export function diffArrays < T > ( input , output , ptr , diff = diffAny ) { const memo = { '0,0' : { operations : [ ] , cost : 0 } , } ; param i param j returns function dist ( i , j ) { const memo_key = `${ i },${ j }` ; let memoized = memo [ memo_key ] ; if ( memoized === undefined ) { if ( i > 0 && j > 0 && ! diff ( input [ i - 1 ] , output [ j - 1 ] , new Pointer ( ) ) . length ) { memoized = dist ( i - 1 , j - 1 ) ; } else { const alternatives = [ ] ; if ( i > 0 ) { const remove_base = dist ( i - 1 , j ) ; const remove_operation = { op : 'remove' , index : i - 1 , } ; alternatives . push ( appendArrayOperation ( remove_base , remove_operation ) ) ; } if ( j > 0 ) { const add_base = dist ( i , j - 1 ) ; const add_operation = { op : 'add' , index : i - 1 , value : output [ j - 1 ] , } ; alternatives . push ( appendArrayOperation ( add_base , add_operation ) ) ; } if ( i > 0 && j > 0 ) { const replace_base = dist ( i - 1 , j - 1 ) ; const replace_operation = { op : 'replace' , index : i - 1 , original : input [ i - 1 ] , value : output [ j - 1 ] , } ; alternatives . push ( appendArrayOperation ( replace_base , replace_operation ) ) ; } const best = alternatives . sort ( ( a , b ) => a . cost - b . cost ) [ 0 ] ; memoized = best ; } memo [ memo_key ] = memoized ; } return memoized ; } const input_length = ( isNaN ( input . length ) || input . length <= 0 ) ? 0 : input . length ; const output_length = ( isNaN ( output . length ) || output . length <= 0 ) ? 0 : output . length ; const array_operations = dist ( input_length , output_length ) . operations ; const [ padded_operations ] = array_operations . reduce < [ Operation [ ] , number ] > ( ( [ operations , padding ] , array_operation ) => { if ( isArrayAdd ( array_operation ) ) { const padded_index = array_operation . index + 1 + padding ; const index_token = padded_index < ( input_length + padding ) ? String ( padded_index ) : '-' ; const operation = { op : array_operation . op , path : ptr . add ( index_token ) . toString ( ) , value : array_operation . value , } ; return [ operations . concat ( operation ) , padding + 1 ] ; } else if ( isArrayRemove ( array_operation ) ) { const operation = { op : array_operation . op , path : ptr . add ( String ( array_operation . index + padding ) ) . toString ( ) , } ; return [ operations . concat ( operation ) , padding - 1 ] ; } else { const replace_ptr = ptr . add ( String ( array_operation . index + padding ) ) ; const replace_operations = diff ( array_operation . original , array_operation . value , replace_ptr ) ; return [ operations . concat ( ... replace_operations ) , padding ] ; } } , [ [ ] , 0 ] ) ; return padded_operations ; } export function diffObjects ( input , output , ptr , diff = diffAny ) { const operations = [ ] ; subtract ( input , output ) . forEach ( key => { operations . push ( { op : 'remove' , path : ptr . add ( key ) . toString ( ) } ) ; } ) ; subtract ( output , input ) . forEach ( key => { operations . push ( { op : 'add' , path : ptr . add ( key ) . toString ( ) , value : output [ key ] } ) ; } ) ; intersection ( [ input , output ] ) . forEach ( key => { operations . push ( ... diff ( input [ key ] , output [ key ] , ptr . add ( key ) ) ) ; } ) ; return operations ; } /**
`diffAny()` returns an empty array if `input` and `output` are materially equal
(i.e., would produce equivalent JSON); otherwise it produces an array of patches
that would transform `input` into `output`.

> Here, "equal" means that the value at the target location and the
> value conveyed by "value" are of the same JSON type, and that they
> are considered equal by the following rules for that type:
> o  strings: are considered equal if they contain the same number of
>    Unicode characters and their code points are byte-by-byte equal.
> o  numbers: are considered equal if their values are numerically
>    equal.
> o  arrays: are considered equal if they contain the same number of
>    values, and if each value can be considered equal to the value at
>    the corresponding position in the other array, using this list of
>    type-specific rules.
> o  objects: are considered equal if they contain the same number of
>    members, and if each member can be considered equal to a member in
>    the other object, by comparing their keys (as strings) and their
>    values (using this list of type-specific rules).
> o  literals (false, true, and null): are considered equal if they are
>    the same.
*/ export function diffAny ( input , output , ptr , diff = diffAny ) { if ( input === output ) { return [ ] ; } const input_type = objectType ( input ) ; const output_type = objectType ( output ) ; if ( input_type == 'array' && output_type == 'array' ) { return diffArrays ( input , output , ptr , diff ) ; } if ( input_type == 'object' && output_type == 'object' ) { return diffObjects ( input , output , ptr , diff ) ; } return [ { op : 'replace' , path : ptr . toString ( ) , value : output } ] ; }