namespace pxt . diff { type UArray = Uint32Array | Uint16Array ; export function toLines ( file ) { return file ? file . split ( /\r?\n/ ) : [ ] ; } export interface DiffOptions { context ? : number ; ignoreWhitespace ? : boolean ; maxDiffSize ? : number ; full ? : boolean ; } export function compute ( fileA , fileB , options = { } ) { if ( options . ignoreWhitespace ) { fileA = fileA . replace ( /[\r\n]+$/ , "" ) ; fileB = fileB . replace ( /[\r\n]+$/ , "" ) ; } const a = toLines ( fileA ) ; const b = toLines ( fileB ) ; const MAX = Math . min ( options . maxDiffSize || 1024 , a . length + b . length ) ; if ( MAX == 0 ) return [ ] ; const ctor = a . length > 0xfff0 ? Uint32Array : Uint16Array ; const idxmap = { } ; let curridx = 0 ; const aidx = mkidx ( a ) , bidx = mkidx ( b ) ; function mkidx ( strings ) { const idxarr = new ctor ( strings . length ) ; let i = 0 ; for ( let e of strings ) { if ( options . ignoreWhitespace ) e = e . replace ( /\s+$/g , "" ) . replace ( /^\s+/g , '' ) ; if ( idxmap . hasOwnProperty ( e ) ) idxarr [ i ] = idxmap [ e ] ; else { ++ curridx ; idxarr [ i ] = curridx ; idxmap [ e ] = curridx ; } i ++ ; } return idxarr ; } const V = new ctor ( 2 * MAX + 1 ) ; let diffLen = - 1 ; for ( let D = 0 ; D <= MAX ; D ++ ) { if ( computeFor ( D , V ) != null ) { diffLen = D ; } } if ( diffLen == - 1 ) return null ; const trace = [ ] ; let endpoint = null ; for ( let D = 0 ; D <= diffLen ; D ++ ) { const V = trace . length ? trace [ trace . length - 1 ] . slice ( 0 ) : new ctor ( 2 * diffLen + 1 ) ; trace . push ( V ) ; endpoint = computeFor ( D , V ) ; if ( endpoint != null ) break ; } const diff = [ ] ; let k = endpoint ; for ( let D = trace . length - 1 ; D >= 0 ; D -- ) { const V = trace [ D ] ; let x = 0 ; let nextK = 0 ; if ( k == - D || ( k != D && V [ MAX + k - 1 ] < V [ MAX + k + 1 ] ) ) { nextK = k + 1 ; x = V [ MAX + nextK ] ; } else { nextK = k - 1 ; x = V [ MAX + nextK ] + 1 ; } let y = x - k ; const snakeLen = V [ MAX + k ] - x ; for ( let i = snakeLen - 1 ; i >= 0 ; -- i ) diff . push ( "  " + b [ y + i ] ) ; if ( nextK == k - 1 ) { diff . push ( "- " + a [ x - 1 ] ) ; } else { if ( y > 0 ) diff . push ( "+ " + b [ y - 1 ] ) ; } k = nextK ; } diff . reverse ( ) ; if ( options . context == Infinity || options . full ) return diff ; let aline = 1 , bline = 1 , idx = 0 ; const shortDiff = [ ] ; const context = options . context || 3 ; while ( idx < diff . length ) { let nextIdx = idx ; while ( nextIdx < diff . length && diff [ nextIdx ] [ 0 ] == " " ) nextIdx ++ ; if ( nextIdx == diff . length ) break ; const startIdx = nextIdx - context ; const skip = startIdx - idx ; if ( skip > 0 ) { aline += skip ; bline += skip ; idx = startIdx ; } const hdPos = shortDiff . length ; const aline0 = aline , bline0 = bline ; shortDiff . push ( "@@" ) ; let endIdx = idx ; let numCtx = 0 ; while ( endIdx < diff . length ) { if ( diff [ endIdx ] [ 0 ] == " " ) { numCtx ++ ; if ( numCtx > context * 2 + 2 ) { endIdx -= context + 2 ; break ; } } else { numCtx = 0 ; } endIdx ++ ; } while ( idx < endIdx ) { shortDiff . push ( diff [ idx ] ) ; const c = diff [ idx ] [ 0 ] ; switch ( c ) { case "-" : aline ++ ; break ; case "+" : bline ++ ; break ; case " " : aline ++ ; bline ++ ; break ; } idx ++ ; } shortDiff [ hdPos ] = `@@ -${ aline0 },${ aline - aline0 } +${ bline0 },${ bline - bline0 } @@` ; } return shortDiff ; function computeFor ( D , V ) { for ( let k = - D ; k <= D ; k += 2 ) { let x = 0 ; if ( k == - D || ( k != D && V [ MAX + k - 1 ] < V [ MAX + k + 1 ] ) ) x = V [ MAX + k + 1 ] ; else x = V [ MAX + k - 1 ] + 1 ; let y = x - k ; while ( x < aidx . length && y < bidx . length && aidx [ x ] == bidx [ y ] ) { x ++ ; y ++ ; } V [ MAX + k ] = x ; if ( x >= aidx . length && y >= bidx . length ) { return k ; } } return null ; } } export function diff3 ( fileA , fileO , fileB , lblA , lblB ) { const ma = computeMatch ( fileA ) ; const mb = computeMatch ( fileB ) ; if ( ! ma || ! mb ) return undefined ; const fa = toLines ( fileA ) ; const fb = toLines ( fileB ) ; let numConflicts = 0 ; let r = [ ] ; let la = 0 , lb = 0 ; for ( let i = 0 ; i < ma . length - 1 ; ) { if ( ma [ i ] == la && mb [ i ] == lb ) { r . push ( fa [ la ] ) ; la ++ ; lb ++ ; i ++ ; } else { let aSame = true ; let bSame = true ; let j = i ; while ( j < ma . length ) { if ( ma [ j ] != la + j - i ) aSame = false ; if ( mb [ j ] != lb + j - i ) bSame = false ; if ( ma [ j ] != null && mb [ j ] != null ) break ; j ++ ; } U . assert ( j < ma . length ) ; if ( aSame ) { while ( lb < mb [ j ] ) r . push ( fb [ lb ++ ] ) ; } else if ( bSame ) { while ( la < ma [ j ] ) r . push ( fa [ la ++ ] ) ; } else if ( fa . slice ( la , ma [ j ] ) . join ( "\n" ) == fb . slice ( lb , mb [ j ] ) . join ( "\n" ) ) { while ( la < ma [ j ] ) r . push ( fa [ la ++ ] ) ; } else { numConflicts ++ ; r . push ( "<<<<<<< " + lblA ) ; while ( la < ma [ j ] ) r . push ( fa [ la ++ ] ) ; r . push ( "=======" ) ; while ( lb < mb [ j ] ) r . push ( fb [ lb ++ ] ) ; r . push ( ">>>>>>> " + lblB ) ; } i = j ; la = ma [ j ] ; lb = mb [ j ] ; } } return { merged : r . join ( "\n" ) , numConflicts } ; function computeMatch ( fileA ) { const da = compute ( fileO , fileA , { context : Infinity } ) ; if ( ! da ) return undefined ; const ma = [ ] ; let aidx = 0 ; let oidx = 0 ; for ( let l of da ) { if ( l [ 0 ] == "+" ) { aidx ++ ; } else if ( l [ 0 ] == "-" ) { ma [ oidx ] = null ; oidx ++ ; } else if ( l [ 0 ] == " " ) { ma [ oidx ] = aidx ; aidx ++ ; oidx ++ ; } else { U . oops ( ) ; } } ma . push ( aidx + 1 ) ; return ma ; } } export function removeTrailingSemiColumns ( src ) { return toLines ( src ) . map ( line => line . replace ( /;\s*$/ , '' ) ) . join ( '\n' ) ; } export function split ( dualSrc , options ? ) { const src = dualSrc . split ( /-{10,}/ , 2 ) ; if ( src . length < 2 ) return { fileA : dualSrc , fileB : undefined } ; let fileA = src [ 0 ] . replace ( /\n$/ , '' ) ; let fileB = src [ 1 ] . replace ( /^\n/ , '' ) ; if ( options && options . removeTrailingSemiColumns ) { fileA = removeTrailingSemiColumns ( fileA ) ; fileB = removeTrailingSemiColumns ( fileB ) ; } return { fileA , fileB } ; } export interface DiffMarker { oldStart : number ; oldLength : number ; newStart : number ; newLength : number ; } export function parseDiffMarker ( ln ) { const m = /^@@ -(\d+),(\d+) \+(\d+),(\d+)/ . exec ( ln ) ; return m && { oldStart : parseInt ( m [ 1 ] ) - 1 , oldLength : parseInt ( m [ 2 ] ) , newStart : parseInt ( m [ 3 ] ) - 1 , newLength : parseInt ( m [ 4 ] ) } ; } export interface RenderOptions extends DiffOptions { hideMarkerLine ? : boolean ; hideLineNumbers ? : boolean ; hideMarker ? : boolean ; hideRemoved ? : boolean ; update ? : boolean ; } export function render ( fileA , fileB , options = { } ) { const diffLines = compute ( fileA , fileB , options ) ; if ( ! diffLines ) { return pxt . dom . el ( "div" , null , pxtc . Util . lf ( "Too many differences to render diff." ) ) ; } const diffClasses = { "@" : "diff-marker" , " " : "diff-unchanged" , "+" : "diff-added" , "-" : "diff-removed" , } ; let lnA = 0 , lnB = 0 ; let lastMark = "" ; const tbody = pxt . dom . el ( "tbody" ) ; const diffEl = pxt . dom . el ( "table" , { "class" : `diffview ${ options . update ? 'update' : '' }` } , tbody ) ; let savedDiffEl = null ; diffLines . forEach ( ( ln , idx ) => { const m = parseDiffMarker ( ln ) ; if ( m ) { lnA = m . oldStart ; lnB = m . newStart ; } else { if ( ln [ 0 ] != "+" ) lnA ++ ; if ( ln [ 0 ] != "-" ) lnB ++ ; } const nextMark = diffLines [ idx + 1 ] ? diffLines [ idx + 1 ] [ 0 ] : "" ; const next2Mark = diffLines [ idx + 2 ] ? diffLines [ idx + 2 ] [ 0 ] : "" ; const lnSrc = ln . slice ( 2 ) ; let currDiff = pxt . dom . el ( "code" , null , lnSrc ) ; if ( savedDiffEl ) { currDiff = savedDiffEl ; savedDiffEl = null ; } else if ( ln [ 0 ] == "-" && ( lastMark == " " || lastMark == "@" ) && nextMark == "+" && ( next2Mark == " " || next2Mark == "@" || next2Mark == "" ) ) { const r = lineDiff ( ln . slice ( 2 ) , diffLines [ idx + 1 ] . slice ( 2 ) ) ; currDiff = r . a ; savedDiffEl = r . b ; } lastMark = ln [ 0 ] ; if ( ( options . hideMarkerLine && lastMark == "@" ) || ( options . hideRemoved && lastMark == "-" ) ) return ; const isMarkerLine = lastMark == "@" ; const className = `${ diffClasses [ lastMark ] }` ; tbody . appendChild ( pxt . dom . el ( "tr" , { "class" : className } , [ ! options . hideLineNumbers && pxt . dom . el ( "td" , { class : "line-a" , "data-content" : lnA } ) , ! options . hideLineNumbers && pxt . dom . el ( "td" , { class : "line-b" , "data-content" : lnB } ) , isMarkerLine && pxt . dom . el ( "td" , { "colspan" : 2 , class : "change" } , pxt . dom . el ( "code" , null , ln ) ) , ! options . hideMarker && ! isMarkerLine && pxt . dom . el ( "td" , { class : "marker" , "data-content" : lastMark } ) , ! isMarkerLine && pxt . dom . el ( "td" , { class : "change" } , currDiff ) ] ) ) ; } ) ; return diffEl ; } function lineDiff ( lineA , lineB ) { const df = compute ( lineA . split ( "" ) . join ( "\n" ) , lineB . split ( "" ) . join ( "\n" ) , { context : Infinity } ) ; if ( ! df ) return { a : pxt . dom . el ( "div" , { "class" : "inline-diff" } , pxt . dom . el ( "code" , null , lineA ) ) , b : pxt . dom . el ( "div" , { "class" : "inline-diff" } , pxt . dom . el ( "code" , null , lineB ) ) } ; const ja = [ ] ; const jb = [ ] ; for ( let i = 0 ; i < df . length ; ) { let j = i ; const mark = df [ i ] [ 0 ] ; while ( df [ j ] && df [ j ] [ 0 ] == mark ) j ++ ; const chunk = df . slice ( i , j ) . map ( s => s . slice ( 2 ) ) . join ( "" ) ; if ( mark == " " ) { ja . push ( pxt . dom . el ( "code" , { "class" : "ch-common" } , chunk ) ) ; jb . push ( pxt . dom . el ( "code" , { "class" : "ch-common" } , chunk ) ) ; } else if ( mark == "-" ) { ja . push ( pxt . dom . el ( "code" , { "class" : "ch-removed" } , chunk ) ) ; } else if ( mark == "+" ) { jb . push ( pxt . dom . el ( "code" , { "class" : "ch-added" } , chunk ) ) ; } else { pxt . Util . oops ( ) ; } i = j ; } return { a : pxt . dom . el ( "div" , { "class" : "inline-diff" } , ja ) , b : pxt . dom . el ( "div" , { "class" : "inline-diff" } , jb ) } ; } export function resolveMergeConflictMarker ( content , startMarkerLine , local , remote ) { let lines = pxt . diff . toLines ( content ) ; let startLine = startMarkerLine ; while ( startLine < lines . length ) { if ( /^<<<<<<<[^<]/ . test ( lines [ startLine ] ) ) { break ; } startLine ++ ; } let middleLine = startLine + 1 ; while ( middleLine < lines . length ) { if ( /^=======$/ . test ( lines [ middleLine ] ) ) break ; middleLine ++ ; } let endLine = middleLine + 1 ; while ( endLine < lines . length ) { if ( /^>>>>>>>[^>]/ . test ( lines [ endLine ] ) ) { break ; } endLine ++ ; } if ( endLine >= lines . length ) { pxt . debug ( `diff marker mistmatch: ${ lines . length } -> ${ startLine } ${ middleLine } ${ endLine }` ) ; return content ; } lines [ startLine ] = undefined ; lines [ middleLine ] = undefined ; lines [ endLine ] = undefined ; if ( ! local ) for ( let i = startLine ; i <= middleLine ; ++ i ) lines [ i ] = undefined ; if ( ! remote ) for ( let i = middleLine ; i <= endLine ; ++ i ) lines [ i ] = undefined ; return lines . filter ( line => line !== undefined ) . join ( "\n" ) ; } param configA param configO param configB export function mergeDiff3Config ( configA , configO , configB ) { let jsonA = pxt . Util . jsonTryParse ( configA ) ; let jsonO = pxt . Util . jsonTryParse ( configO ) ; let jsonB = pxt . Util . jsonTryParse ( configB ) ; if ( jsonA && ! jsonB ) return configA ; if ( ! jsonA ) return configB || configO ; if ( ! jsonO && jsonB ) jsonO = jsonB ; if ( ! jsonA || ! jsonO || ! jsonB ) return undefined ; delete jsonA . installedVersion ; delete jsonO . installedVersion ; delete jsonB . installedVersion ; const r = { } as pxt . PackageConfig ; const keys = pxt . U . unique ( Object . keys ( jsonO ) . concat ( Object . keys ( jsonA ) ) . concat ( Object . keys ( jsonB ) ) , l => l ) ; for ( const key of keys ) { const vA = jsonA [ key ] ; const vO = jsonO [ key ] ; const vB = jsonB [ key ] ; const svA = JSON . stringify ( vA ) ; const svB = JSON . stringify ( vB ) ; if ( svA == svB ) { if ( vA !== undefined ) r [ key ] = vA ; } else { switch ( key ) { case "name" : r [ key ] = mergeName ( vA , vO , vB ) ; break ; case "version" : r [ key ] = pxt . semver . strcmp ( vA , vB ) > 0 ? vA : vB ; break ; case "languageRestriction" : case "preferredEditor" : case "targetVersion" : r [ key ] = vA ; break ; case "public" : r [ key ] = vA && vB ; break ; case "files" : case "testFiles" : { const m = mergeFiles ( vA || [ ] , vO || [ ] , vB || [ ] ) ; if ( ! m ) return undefined ; r [ key ] = m . length ? m : undefined ; break ; } case "dependencies" : case "testDependencies" : { const m = mergeDependencies ( vA || { } , vO || { } , vB || { } ) ; if ( Object . keys ( m ) . length ) return undefined ; r [ key ] = m ; break ; } case "description" : if ( vA && ! vB ) r [ key ] = vA ; else if ( ! vA && vB ) r [ key ] = vB ; else return undefined ; break ; default : return undefined ; } } } return pxt . Package . stringifyConfig ( r ) ; function mergeName ( fA , fO , fB ) { if ( fA == fO ) return fB ; if ( fB == fO ) return fA ; if ( fA == lf ( "Untitled" ) ) return fB ; return fA ; } function mergeFiles ( fA , fO , fB ) { const r = [ ] ; const fkeys = pxt . U . unique ( fO . concat ( fA ) . concat ( fB ) , l => l ) ; for ( const fkey of fkeys ) { const mA = fA . indexOf ( fkey ) > - 1 ; const mB = fB . indexOf ( fkey ) > - 1 ; const mO = fO . indexOf ( fkey ) > - 1 ; if ( mA == mB ) { if ( mA ) r . push ( fkey ) ; } else { if ( mB == mO ) { if ( mA ) r . push ( fkey ) ; } else { if ( mB ) r . push ( fkey ) ; } } } return r ; } function mergeDependencies ( fA , fO , fB ) { const r = { } ; const fkeys = pxt . U . unique ( Object . keys ( fO ) . concat ( Object . keys ( fA ) ) . concat ( Object . keys ( fB ) ) , l => l ) ; for ( const fkey of fkeys ) { const mA = fA [ fkey ] ; const mB = fB [ fkey ] ; const mO = fO [ fkey ] ; if ( mA == mB ) { if ( mA ) r [ fkey ] = mA ; } else { const ghA = pxt . github . parseRepoId ( mA ) ; const ghB = pxt . github . parseRepoId ( mB ) ; if ( ghA && ghB && pxt . semver . tryParse ( ghA . tag ) && pxt . semver . tryParse ( ghB . tag ) && ghA . owner && ghA . project && ghA . owner == ghB . owner && ghA . project == ghB . project ) { const newtag = pxt . semver . strcmp ( ghA . tag , ghB . tag ) > 0 ? ghA . tag : ghB . tag ; r [ fkey ] = `github:${ ghA . owner }/${ ghA . project }#${ newtag }` ; } else if ( mB == mO ) { if ( mA ) r [ fkey ] = mA ; } else { if ( mB ) r [ fkey ] = mB ; } } } return r ; } } export function hasMergeConflictMarker ( content ) { return content && /^(<<<<<<<[^<]|>>>>>>>[^>])/m . test ( content ) ; } export function reconstructConfig ( parsed , files , commit , tp ) { let dependencies = { } ; let commitFiles = commit . tree . tree . map ( f => f . path ) . filter ( f => /\.(ts|blocks|md|jres|asm|json)$/ . test ( f ) ) . filter ( f => f != pxt . CONFIG_NAME ) ; if ( parsed . fileName ) commitFiles = commitFiles . filter ( f => f . indexOf ( parsed . fileName ) === 0 ) . map ( f => f . slice ( parsed . fileName . length + 1 ) ) ; if ( ! commitFiles . find ( f => /\.ts$/ . test ( f ) ) ) { tp . config . files . filter ( f => commitFiles . indexOf ( f ) < 0 ) . forEach ( f => { commitFiles . push ( f ) ; files [ f ] = tp . files [ f ] ; } ) ; pxt . Util . jsonCopyFrom ( dependencies , tp . config . dependencies ) ; } if ( ! Object . keys ( dependencies ) . length ) dependencies [ pxt . appTarget . corepkg ] = "*" ; const cfg = { name : "" , files : commitFiles , dependencies , preferredEditor : commitFiles . find ( f => /.blocks$/ . test ( f ) ) ? pxt . BLOCKS_PROJECT_NAME : pxt . JAVASCRIPT_PROJECT_NAME } ; return cfg ; } }