unified.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package diff
     6  
     7  import (
     8  	"fmt"
     9  	"log"
    10  	"strings"
    11  )
    12  
    13  // DefaultContextLines is the number of unchanged lines of surrounding
    14  // context displayed by Unified. Use ToUnified to specify a different value.
    15  const DefaultContextLines = 3
    16  
    17  // Unified returns a unified diff of the old and new strings.
    18  // The old and new labels are the names of the old and new files.
    19  // If the strings are equal, it returns the empty string.
    20  func Unified(oldLabel, newLabel, old, new string) string {
    21  	edits := Strings(old, new)
    22  	unified, err := ToUnified(oldLabel, newLabel, old, edits, DefaultContextLines)
    23  	if err != nil {
    24  		// Can't happen: edits are consistent.
    25  		log.Fatalf("internal error in diff.Unified: %v", err)
    26  	}
    27  	return unified
    28  }
    29  
    30  // ToUnified applies the edits to content and returns a unified diff,
    31  // with contextLines lines of (unchanged) context around each diff hunk.
    32  // The old and new labels are the names of the content and result files.
    33  // It returns an error if the edits are inconsistent; see ApplyEdits.
    34  func ToUnified(oldLabel, newLabel, content string, edits []Edit, contextLines int) (string, error) {
    35  	u, err := toUnified(oldLabel, newLabel, content, edits, contextLines)
    36  	if err != nil {
    37  		return "", err
    38  	}
    39  	return u.String(), nil
    40  }
    41  
    42  // unified represents a set of edits as a unified diff.
    43  type unified struct {
    44  	// from is the name of the original file.
    45  	from string
    46  	// to is the name of the modified file.
    47  	to string
    48  	// hunks is the set of edit hunks needed to transform the file content.
    49  	hunks []*hunk
    50  }
    51  
    52  // Hunk represents a contiguous set of line edits to apply.
    53  type hunk struct {
    54  	// The line in the original source where the hunk starts.
    55  	fromLine int
    56  	// The line in the original source where the hunk finishes.
    57  	toLine int
    58  	// The set of line based edits to apply.
    59  	lines []line
    60  }
    61  
    62  // Line represents a single line operation to apply as part of a Hunk.
    63  type line struct {
    64  	// kind is the type of line this represents, deletion, insertion or copy.
    65  	kind opKind
    66  	// content is the content of this line.
    67  	// For deletion it is the line being removed, for all others it is the line
    68  	// to put in the output.
    69  	content string
    70  }
    71  
    72  // opKind is used to denote the type of operation a line represents.
    73  type opKind int
    74  
    75  const (
    76  	// opDelete is the operation kind for a line that is present in the input
    77  	// but not in the output.
    78  	opDelete opKind = iota
    79  	// opInsert is the operation kind for a line that is new in the output.
    80  	opInsert
    81  	// opEqual is the operation kind for a line that is the same in the input and
    82  	// output, often used to provide context around edited lines.
    83  	opEqual
    84  )
    85  
    86  // String returns a human readable representation of an OpKind. It is not
    87  // intended for machine processing.
    88  func (k opKind) String() string {
    89  	switch k {
    90  	case opDelete:
    91  		return "delete"
    92  	case opInsert:
    93  		return "insert"
    94  	case opEqual:
    95  		return "equal"
    96  	default:
    97  		panic("unknown operation kind")
    98  	}
    99  }
   100  
   101  // toUnified takes a file contents and a sequence of edits, and calculates
   102  // a unified diff that represents those edits.
   103  func toUnified(fromName, toName string, content string, edits []Edit, contextLines int) (unified, error) {
   104  	gap := contextLines * 2
   105  	u := unified{
   106  		from: fromName,
   107  		to:   toName,
   108  	}
   109  	if len(edits) == 0 {
   110  		return u, nil
   111  	}
   112  	var err error
   113  	edits, err = lineEdits(content, edits) // expand to whole lines
   114  	if err != nil {
   115  		return u, err
   116  	}
   117  	lines := splitLines(content)
   118  	var h *hunk
   119  	last := 0
   120  	toLine := 0
   121  	for _, edit := range edits {
   122  		// Compute the zero-based line numbers of the edit start and end.
   123  		// TODO(adonovan): opt: compute incrementally, avoid O(n^2).
   124  		start := strings.Count(content[:edit.Start], "\n")
   125  		end := strings.Count(content[:edit.End], "\n")
   126  		if edit.End == len(content) && len(content) > 0 && content[len(content)-1] != '\n' {
   127  			end++ // EOF counts as an implicit newline
   128  		}
   129  
   130  		switch {
   131  		case h != nil && start == last:
   132  			//direct extension
   133  		case h != nil && start <= last+gap:
   134  			//within range of previous lines, add the joiners
   135  			addEqualLines(h, lines, last, start)
   136  		default:
   137  			//need to start a new hunk
   138  			if h != nil {
   139  				// add the edge to the previous hunk
   140  				addEqualLines(h, lines, last, last+contextLines)
   141  				u.hunks = append(u.hunks, h)
   142  			}
   143  			toLine += start - last
   144  			h = &hunk{
   145  				fromLine: start + 1,
   146  				toLine:   toLine + 1,
   147  			}
   148  			// add the edge to the new hunk
   149  			delta := addEqualLines(h, lines, start-contextLines, start)
   150  			h.fromLine -= delta
   151  			h.toLine -= delta
   152  		}
   153  		last = start
   154  		for i := start; i < end; i++ {
   155  			h.lines = append(h.lines, line{kind: opDelete, content: lines[i]})
   156  			last++
   157  		}
   158  		if edit.New != "" {
   159  			for _, content := range splitLines(edit.New) {
   160  				h.lines = append(h.lines, line{kind: opInsert, content: content})
   161  				toLine++
   162  			}
   163  		}
   164  	}
   165  	if h != nil {
   166  		// add the edge to the final hunk
   167  		addEqualLines(h, lines, last, last+contextLines)
   168  		u.hunks = append(u.hunks, h)
   169  	}
   170  	return u, nil
   171  }
   172  
   173  func splitLines(text string) []string {
   174  	lines := strings.SplitAfter(text, "\n")
   175  	if lines[len(lines)-1] == "" {
   176  		lines = lines[:len(lines)-1]
   177  	}
   178  	return lines
   179  }
   180  
   181  func addEqualLines(h *hunk, lines []string, start, end int) int {
   182  	delta := 0
   183  	for i := start; i < end; i++ {
   184  		if i < 0 {
   185  			continue
   186  		}
   187  		if i >= len(lines) {
   188  			return delta
   189  		}
   190  		h.lines = append(h.lines, line{kind: opEqual, content: lines[i]})
   191  		delta++
   192  	}
   193  	return delta
   194  }
   195  
   196  // String converts a unified diff to the standard textual form for that diff.
   197  // The output of this function can be passed to tools like patch.
   198  func (u unified) String() string {
   199  	if len(u.hunks) == 0 {
   200  		return ""
   201  	}
   202  	b := new(strings.Builder)
   203  	fmt.Fprintf(b, "--- %s\n", u.from)
   204  	fmt.Fprintf(b, "+++ %s\n", u.to)
   205  	for _, hunk := range u.hunks {
   206  		fromCount, toCount := 0, 0
   207  		for _, l := range hunk.lines {
   208  			switch l.kind {
   209  			case opDelete:
   210  				fromCount++
   211  			case opInsert:
   212  				toCount++
   213  			default:
   214  				fromCount++
   215  				toCount++
   216  			}
   217  		}
   218  		fmt.Fprint(b, "@@")
   219  		if fromCount > 1 {
   220  			fmt.Fprintf(b, " -%d,%d", hunk.fromLine, fromCount)
   221  		} else if hunk.fromLine == 1 && fromCount == 0 {
   222  			// Match odd GNU diff -u behavior adding to empty file.
   223  			fmt.Fprintf(b, " -0,0")
   224  		} else {
   225  			fmt.Fprintf(b, " -%d", hunk.fromLine)
   226  		}
   227  		if toCount > 1 {
   228  			fmt.Fprintf(b, " +%d,%d", hunk.toLine, toCount)
   229  		} else if hunk.toLine == 1 && toCount == 0 {
   230  			// Match odd GNU diff -u behavior adding to empty file.
   231  			fmt.Fprintf(b, " +0,0")
   232  		} else {
   233  			fmt.Fprintf(b, " +%d", hunk.toLine)
   234  		}
   235  		fmt.Fprint(b, " @@\n")
   236  		for _, l := range hunk.lines {
   237  			switch l.kind {
   238  			case opDelete:
   239  				fmt.Fprintf(b, "-%s", l.content)
   240  			case opInsert:
   241  				fmt.Fprintf(b, "+%s", l.content)
   242  			default:
   243  				fmt.Fprintf(b, " %s", l.content)
   244  			}
   245  			if !strings.HasSuffix(l.content, "\n") {
   246  				fmt.Fprintf(b, "\n\\ No newline at end of file\n")
   247  			}
   248  		}
   249  	}
   250  	return b.String()
   251  }
   252
View as plain text