Class: RuboCop::UnifiedDiff Private

Relationships & Source Files
Inherits:	Object
Defined in:	lib/rubocop/unified_diff.rb

Overview

Renders a unified diff between two versions of a file’s source.

RuboCop has no diffing dependency and this output is meant to be read by people (and occasionally piped into git apply), so the goal is a diff that is correct and readable, not one that matches diff -u byte for byte.

Constant Summary

CONTEXT_LINES =
# File 'lib/rubocop/unified_diff.rb', line 12
```
3
```
MAX_EDIT_DISTANCE =

Finding a minimal diff costs time and memory proportional to the square of the number of edits. Past this many edits the file was rewritten rather than corrected, so the changed region is reported as a single replacement instead.

# File 'lib/rubocop/unified_diff.rb', line 19
```
400
```
NO_NEWLINE_MARKER =
# File 'lib/rubocop/unified_diff.rb', line 13
```
"\\ No newline at end of file\n"
```

Class Method Summary

.new(path, old_source, new_source) ⇒ UnifiedDiff constructor Internal use only

Instance Method Summary

#to_s ⇒ String Internal use only
#advance(furthest, diagonal, distance) private Internal use only

Picks the better of the two paths reaching this diagonal, then follows the diagonal as far as the lines match.
#backtrack(trace) private Internal use only
#common_prefix_length private Internal use only
#common_suffix_length(prefix) private Internal use only
#edit_script private Internal use only
#follow_diagonal(old_index, new_index) private Internal use only

Matching lines cost nothing, so the path slides along them for free.
#formatted_line(kind, line) private Internal use only
#hunk(script, range) private Internal use only
#hunks_for(script) private Internal use only
#middle_script(old_lines, new_lines) private Internal use only
#myers_script private Internal use only

Myers' diff algorithm.
#position(start, count) private Internal use only

An empty side is anchored to the line it follows, which is how diff reports a pure insertion or deletion, and a single line drops the count.
#previous_diagonal(furthest, diagonal, distance) private Internal use only

A path arrives at this diagonal either from the one above it (having inserted a line) or the one below it (having deleted one); whichever reached further wins.
#previous_position(furthest, distance, old_index, new_index) private Internal use only
#ranges_for(changed, script_length) private Internal use only

Every change is shown with a few lines of context around it, and changes whose context would overlap are shown as a single hunk.
#reached_end?(old_index, diagonal) ⇒ Boolean private Internal use only
#record_edit(script, position, previous) private Internal use only
#start_of_path(furthest, diagonal, distance) private Internal use only
#start_positions(script, index) private Internal use only
#walk_diagonal(script, position, previous) private Internal use only

Both sides step back together for as long as their lines match.

Constructor Details

.new(path, old_source, new_source) ⇒ `UnifiedDiff`

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 21


def initialize(path, old_source, new_source)
  @path = path
  @old_lines = old_source.lines
  @new_lines = new_source.lines
end

Instance Method Details

#advance(furthest, diagonal, distance) (private)

Picks the better of the two paths reaching this diagonal, then follows the diagonal as far as the lines match.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 106


def advance(furthest, diagonal, distance)
  old_index = start_of_path(furthest, diagonal, distance)

  follow_diagonal(old_index, old_index - diagonal)
end

#backtrack(trace) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 141


def backtrack(trace)
  script = []
  position = [@from_lines.length, @to_lines.length]

  trace.each_with_index.reverse_each do |furthest, distance|
    previous = previous_position(furthest, distance, *position)
    position = walk_diagonal(script, position, previous)
    next if distance.zero?

    position = record_edit(script, position, previous)
  end

  script
end

#common_prefix_length (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 52


def common_prefix_length
  length = 0
  length += 1 while length < @old_lines.length && @old_lines[length] == @new_lines[length]
  length
end

#common_suffix_length(prefix) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 58


def common_suffix_length(prefix)
  length = 0
  max = [@old_lines.length, @new_lines.length].min - prefix
  while length < max &&
        @old_lines[@old_lines.length - 1 - length] == @new_lines[@new_lines.length - 1 - length]
    length += 1
  end
  length
end

#edit_script (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 39


def edit_script
  prefix = common_prefix_length
  suffix = common_suffix_length(prefix)
  old_last = @old_lines.length - suffix
  new_last = @new_lines.length - suffix

  [
    *@old_lines[0...prefix].map { |line| [:equal, line] },
    *middle_script(@old_lines[prefix...old_last], @new_lines[prefix...new_last]),
    *@old_lines[old_last..].map { |line| [:equal, line] }
  ]
end

#follow_diagonal(old_index, new_index) (private)

Matching lines cost nothing, so the path slides along them for free.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 131


def follow_diagonal(old_index, new_index)
  while old_index < @from_lines.length && new_index < @to_lines.length &&
        @from_lines[old_index] == @to_lines[new_index]
    old_index += 1
    new_index += 1
  end

  old_index
end

#formatted_line(kind, line) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 250


def formatted_line(kind, line)
  marker = { equal: ' ', delete: '-', insert: '+' }.fetch(kind)
  return "#{marker}#{line}" if line.end_with?("\n")

  "#{marker}#{line}\n#{NO_NEWLINE_MARKER}"
end

#hunk(script, range) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 216


def hunk(script, range)
  old_start, new_start = start_positions(script, range.first)
  old_count = script[range].count { |kind, _| kind != :insert }
  new_count = script[range].count { |kind, _| kind != :delete }
  body = script[range].map { |kind, line| formatted_line(kind, line) }

  [
    "@@ -#{position(old_start, old_count)} +#{position(new_start, new_count)} @@\n",
    *body
  ].join
end

#hunks_for(script) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 190


def hunks_for(script)
  changed = script.each_index.reject { |index| script[index].first == :equal }
  return [] if changed.empty?

  ranges_for(changed, script.length).map { |range| hunk(script, range) }
end

#middle_script(old_lines, new_lines) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 68


def middle_script(old_lines, new_lines)
  # The region that actually differs is diffed on its own, so the rest of
  # the algorithm works on these two slices rather than the whole file.
  @from_lines = old_lines
  @to_lines = new_lines

  myers_script ||
    [*old_lines.map { |line| [:delete, line] }, *new_lines.map { |line| [:insert, line] }]
end

#myers_script (private)

Myers' diff algorithm. Each round d extends the furthest reaching path for every diagonal k; the first path to reach the end of both sources is a shortest edit script, which is then reconstructed from the saved rounds. Returns nil when the sources are too different to bother.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 82


def myers_script
  trace = []
  furthest = Hash.new(0)
  max_distance = [@from_lines.length + @to_lines.length, MAX_EDIT_DISTANCE].min

  0.upto(max_distance) do |distance|
    trace << furthest.dup

    (-distance).step(distance, 2) do |diagonal|
      furthest[diagonal] = advance(furthest, diagonal, distance)

      return backtrack(trace) if reached_end?(furthest[diagonal], diagonal)
    end
  end

  nil
end

#position(start, count) (private)

An empty side is anchored to the line it follows, which is how diff reports a pure insertion or deletion, and a single line drops the count.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 242


def position(start, count)
  case count
  when 0 then "#{start - 1},0"
  when 1 then start.to_s
  else "#{start},#{count}"
  end
end

#previous_diagonal(furthest, diagonal, distance) (private)

A path arrives at this diagonal either from the one above it (having inserted a line) or the one below it (having deleted one); whichever reached further wins.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 115


def previous_diagonal(furthest, diagonal, distance)
  if diagonal == -distance ||
     (diagonal != distance && furthest[diagonal - 1] < furthest[diagonal + 1])
    diagonal + 1
  else
    diagonal - 1
  end
end

#previous_position(furthest, distance, old_index, new_index) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 183


def previous_position(furthest, distance, old_index, new_index)
  previous = previous_diagonal(furthest, old_index - new_index, distance)
  previous_old = furthest[previous]

  [previous_old, previous_old - previous]
end

#ranges_for(changed, script_length) (private)

Every change is shown with a few lines of context around it, and changes whose context would overlap are shown as a single hunk.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 199


def ranges_for(changed, script_length)
  ranges = []

  changed.each do |index|
    first = [index - CONTEXT_LINES, 0].max
    last = [index + CONTEXT_LINES, script_length - 1].min

    if ranges.last && first <= ranges.last.last + 1
      ranges[-1] = (ranges.last.first..last)
    else
      ranges << (first..last)
    end
  end

  ranges
end

#reached_end?(old_index, diagonal) ⇒ `Boolean` (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 100


def reached_end?(old_index, diagonal)
  old_index >= @from_lines.length && old_index - diagonal >= @to_lines.length
end

#record_edit(script, position, previous) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 169


def record_edit(script, position, previous)
  old_index, new_index = position

  if old_index == previous[0]
    new_index -= 1
    script.unshift([:insert, @to_lines[new_index]])
  else
    old_index -= 1
    script.unshift([:delete, @from_lines[old_index]])
  end

  [old_index, new_index]
end

#start_of_path(furthest, diagonal, distance) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 124


def start_of_path(furthest, diagonal, distance)
  previous = previous_diagonal(furthest, diagonal, distance)

  previous > diagonal ? furthest[previous] : furthest[previous] + 1
end

#start_positions(script, index) (private)

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 228


def start_positions(script, index)
  old_line = 1
  new_line = 1

  script[0...index].each do |entry|
    old_line += 1 unless entry.first == :insert
    new_line += 1 unless entry.first == :delete
  end

  [old_line, new_line]
end

#to_s ⇒ String

Returns:

(String) —

the diff, or an empty string when the sources are identical

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 28


def to_s
  return '' if @old_lines == @new_lines

  hunks = hunks_for(edit_script)
  return '' if hunks.empty?

  ["--- a/#{@path}\n", "+++ b/#{@path}\n", *hunks].join
end

#walk_diagonal(script, position, previous) (private)

Both sides step back together for as long as their lines match.

[ GitHub ]

# File 'lib/rubocop/unified_diff.rb', line 157


def walk_diagonal(script, position, previous)
  old_index, new_index = position

  while old_index > previous[0] && new_index > previous[1]
    old_index -= 1
    new_index -= 1
    script.unshift([:equal, @from_lines[old_index]])
  end

  [old_index, new_index]
end

Class: RuboCop::UnifiedDiff Private

Overview

Constant Summary

Class Method Summary

Instance Method Summary

Constructor Details

.new(path, old_source, new_source) ⇒ UnifiedDiff

Instance Method Details

#advance(furthest, diagonal, distance) (private)

#backtrack(trace) (private)

#common_prefix_length (private)

#common_suffix_length(prefix) (private)

#edit_script (private)

#follow_diagonal(old_index, new_index) (private)

#formatted_line(kind, line) (private)

#hunk(script, range) (private)

#hunks_for(script) (private)

#middle_script(old_lines, new_lines) (private)

#myers_script (private)

#position(start, count) (private)

#previous_diagonal(furthest, diagonal, distance) (private)

#previous_position(furthest, distance, old_index, new_index) (private)

#ranges_for(changed, script_length) (private)

#reached_end?(old_index, diagonal) ⇒ Boolean (private)

#record_edit(script, position, previous) (private)

#start_of_path(furthest, diagonal, distance) (private)

#start_positions(script, index) (private)

#to_s ⇒ String

#walk_diagonal(script, position, previous) (private)

.new(path, old_source, new_source) ⇒ `UnifiedDiff`

#reached_end?(old_index, diagonal) ⇒ `Boolean` (private)