lineDiff lists the lines removed from a ("- ") and added in b ("+ ").
(a, b string)
| 494 | |
| 495 | // lineDiff lists the lines removed from a ("- ") and added in b ("+ "). |
| 496 | func lineDiff(a, b string) []string { |
| 497 | al, bl := splitLines(a), splitLines(b) |
| 498 | n, m := len(al), len(bl) |
| 499 | if n*m > 4_000_000 { |
| 500 | return []string{"(too long to compare line by line)"} |
| 501 | } |
| 502 | lcs := make([][]int, n+1) |
| 503 | for i := range lcs { |
| 504 | lcs[i] = make([]int, m+1) |
| 505 | } |
| 506 | for i := n - 1; i >= 0; i-- { |
| 507 | for j := m - 1; j >= 0; j-- { |
| 508 | if al[i] == bl[j] { |
| 509 | lcs[i][j] = lcs[i+1][j+1] + 1 |
| 510 | } else { |
| 511 | lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1]) |
| 512 | } |
| 513 | } |
| 514 | } |
| 515 | var out []string |
| 516 | i, j := 0, 0 |
| 517 | for i < n && j < m { |
| 518 | switch { |
| 519 | case al[i] == bl[j]: |
| 520 | i++ |
| 521 | j++ |
| 522 | case lcs[i+1][j] >= lcs[i][j+1]: |
| 523 | out = append(out, "- "+al[i]) |
| 524 | i++ |
| 525 | default: |
| 526 | out = append(out, "+ "+bl[j]) |
| 527 | j++ |
| 528 | } |
| 529 | } |
| 530 | for ; i < n; i++ { |
| 531 | out = append(out, "- "+al[i]) |
| 532 | } |
| 533 | for ; j < m; j++ { |
| 534 | out = append(out, "+ "+bl[j]) |
| 535 | } |
| 536 | return out |
| 537 | } |
| 538 | |
| 539 | func splitLines(s string) []string { |
| 540 | if s == "" { |
no test coverage detected