+++ /dev/null
-// Copyright 2012 Google, Inc. All rights reserved.
-//
-// Use of this source code is governed by a BSD-style license
-// that can be found in the LICENSE file in the root of the source
-// tree.
-
-// Package bytediff provides a simple diff utility for looking at differences in byte
-// slices. It's slow, clunky, and not particularly good by any measure, but
-// it does provide very useful visualizations for diffs between small byte
-// slices.
-//
-// Our diff algorithm uses a dynamic programming implementation of longest common
-// substring to find matching parts of slices, then recursively calls itself on
-// the prefix/suffix of that matching part for each packet. This is a Bad Idea
-// (tm) for normal (especially large) input, but for packets where large portions
-// repeat frequently and we expect minor changes between results, it's actually
-// quite useful.
-package bytediff
-
-import (
- "bytes"
- "fmt"
-)
-
-// OutputFormat tells a Differences.String call how to format the set of
-// differences into a human-readable string. Its internals are currently
-// unexported because we may want to change them drastically in the future. For
-// the moment, please just use one of the provided OutputFormats that comes with
-// this library.
-type OutputFormat struct {
- start, finish, add, remove, change, reset string
-}
-
-var (
- // BashOutput uses bash escape sequences to color output.
- BashOutput = &OutputFormat{
- reset: "\033[0m",
- remove: "\033[32m",
- add: "\033[31m",
- change: "\033[33m",
- }
- // HTMLOutput uses a <pre> to wrap output, and <span>s to color it.
- // HTMLOutput is pretty experimental, so use at your own risk ;)
- HTMLOutput = &OutputFormat{
- start: "<pre>",
- finish: "</pre>",
- reset: "</span>",
- remove: "<span style='color:red'>",
- add: "<span style='color:green'>",
- change: "<span style='color:yellow'>",
- }
-)
-
-// longestCommonSubstring uses a O(MN) dynamic programming approach to find the
-// longest common substring in a set of slices. It returns the index in each
-// slice at which the substring begins, plus the length of the commonality.
-func longestCommonSubstring(strA, strB []byte) (indexA, indexB, length int) {
- lenA, lenB := len(strA), len(strB)
- if lenA == 0 || lenB == 0 {
- return 0, 0, 0
- }
- arr := make([][]int, lenA)
- for i := 0; i < lenA; i++ {
- arr[i] = make([]int, lenB)
- }
- var maxLength int
- var maxA, maxB int
- for a := 0; a < lenA; a++ {
- for b := 0; b < lenB; b++ {
- if strA[a] == strB[b] {
- length := 1
- if a > 0 && b > 0 {
- length = arr[a-1][b-1] + 1
- }
- arr[a][b] = length
- if length > maxLength {
- maxLength = length
- maxA = a
- maxB = b
- }
- }
- }
- }
- a, b := maxA, maxB
- for a >= 0 && b >= 0 && strA[a] == strB[b] {
- indexA = a
- indexB = b
- a--
- b--
- length++
- }
- return
-}
-
-func intMax(a, b int) int {
- if a > b {
- return a
- }
- return b
-}
-
-// Difference represents a single part of the data being diffed, containing
-// information about both the original and new values.
-// From and To are the sets of bytes in the original and the new byte slice.
-// !Replace implies From == To (no change)
-// len(To) == 0 implies From is being deleted
-// len(From) == 0 implies To is being inserted
-// else implies From is being replaced by To
-type Difference struct {
- Replace bool
- From, To []byte
-}
-
-// color returns the bash color for a given difference.
-func (c *OutputFormat) color(d Difference) string {
- switch {
- case !d.Replace:
- return ""
- case len(d.From) == 0:
- return c.remove
- case len(d.To) == 0:
- return c.add
- default:
- return c.change
- }
-}
-
-// Diff diffs strA and strB, returning a list of differences which
-// can be used to construct either the original or new string.
-//
-// Diff is optimized for comparing VERY SHORT slices. It's meant for comparing
-// things like packets off the wire, not large files or the like.
-// As such, its runtime can be catastrophic if large inputs are passed in.
-// You've been warned.
-func Diff(strA, strB []byte) Differences {
- if len(strA) == 0 && len(strB) == 0 {
- return nil
- }
- ia, ib, l := longestCommonSubstring(strA, strB)
- if l == 0 {
- return Differences{
- Difference{true, strA, strB},
- }
- }
- beforeA, match, afterA := strA[:ia], strA[ia:ia+l], strA[ia+l:]
- beforeB, afterB := strB[:ib], strB[ib+l:]
- var diffs Differences
- diffs = append(diffs, Diff(beforeA, beforeB)...)
- diffs = append(diffs, Difference{false, match, match})
- diffs = append(diffs, Diff(afterA, afterB)...)
- return diffs
-}
-
-// Differences is a set of differences for a given diff'd pair of byte slices.
-type Differences []Difference
-
-// String outputs a previously diff'd set of strings, showing differences
-// between them, highlighted by colors.
-//
-// The output format of this function is NOT guaranteed consistent, and may be
-// changed at any time by the library authors. It's meant solely for human
-// consumption.
-func (c *OutputFormat) String(diffs Differences) string {
- var buf bytes.Buffer
- count := 0
- fmt.Fprintf(&buf, "%s", c.start)
- fmt.Fprintf(&buf, "00000000 ")
- for i := 0; i < len(diffs); i++ {
- diff := diffs[i]
- color := c.color(diff)
- reset := ""
- if color != "" {
- reset = c.reset
- }
- fmt.Fprint(&buf, color)
- for _, b := range diff.From {
- fmt.Fprintf(&buf, " %02x", b)
- count++
- switch count % 16 {
- case 0:
- fmt.Fprintf(&buf, "%v\n%08x%v ", reset, count, color)
- case 8:
- fmt.Fprintf(&buf, " ")
- }
- }
- fmt.Fprint(&buf, reset)
- }
- fmt.Fprintf(&buf, "\n\n00000000 ")
- count = 0
- for i := 0; i < len(diffs); i++ {
- diff := diffs[i]
- str := diff.From
- if diff.Replace {
- str = diff.To
- }
- color := c.color(diff)
- reset := ""
- if color != "" {
- reset = c.reset
- }
- fmt.Fprint(&buf, color)
- for _, b := range str {
- fmt.Fprintf(&buf, " %02x", b)
- count++
- switch count % 16 {
- case 0:
- fmt.Fprintf(&buf, "%v\n%08x%v ", reset, count, color)
- case 8:
- fmt.Fprintf(&buf, " ")
- }
- }
- fmt.Fprint(&buf, reset)
- }
- fmt.Fprint(&buf, "\n")
- fmt.Fprintf(&buf, "%s", c.finish)
- return string(buf.Bytes())
-}
Code Review / govpp.git / blobdiff