Class: Datadog::CI::Git::ChangedLines

Inherits:
Object
  • Object
show all
Defined in:
lib/datadog/ci/git/changed_lines.rb

Overview

Helper class to efficiently store and query changed line intervals for a single file Uses merged sorted intervals with binary search for O(log n) query performance

Instance Method Summary collapse

Constructor Details

#initialize ⇒ ChangedLines

Returns a new instance of ChangedLines.



9
10
11
12
13
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 9

def initialize
  @intervals = [] # Array of [start, end] pairs
  @built = false
  @mutex = Mutex.new
end

Instance Method Details

#add_interval(start_line, end_line) ⇒ Object

Add an interval (defers merging until build! is called)



16
17
18
19
20
21
22
23
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 16

def add_interval(start_line, end_line)
  return if start_line > end_line

  @mutex.synchronize do
    @intervals << [start_line, end_line]
    @built = false
  end
end

#build! ⇒ Object

Sort and merge all intervals Call this after all intervals have been added



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 27

def build!
  @mutex.synchronize do
    return false if @built

    @built = true
    return false if @intervals.empty?

    # Sort intervals by start line
    @intervals.sort_by!(&:first)

    # Merge overlapping intervals
    merged = []

    # @type var current_start: Integer
    # @type var current_end: Integer
    current_start, current_end = @intervals.first

    @intervals.each_with_index do |interval, index|
      next if index == 0
      # @type var start_line: Integer
      # @type var end_line: Integer
      start_line, end_line = interval

      if start_line <= current_end + 1
        # Overlapping or adjacent intervals, merge them
        current_end = [current_end, end_line].max
      else
        # Non-overlapping interval, save current and start new
        merged << [current_start, current_end]
        current_start = start_line
        current_end = end_line
      end
    end

    merged << [current_start, current_end]

    @intervals = merged
    true
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


98
99
100
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 98

def empty?
  @intervals.empty?
end

#intervals ⇒ Object 



102
103
104
105
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 102

def intervals
  build! unless @built
  @intervals.dup
end

#overlaps?(query_start, query_end) ⇒ Boolean

Check if any line in the query interval overlaps with changed lines Uses binary search for O(log n) performance

Returns:

  • (Boolean) 


70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/datadog/ci/git/changed_lines.rb', line 70

def overlaps?(query_start, query_end)
  build! unless @built

  return false if @intervals.empty? || query_start > query_end

  # Binary search for the first interval that might overlap
  left = 0
  right = @intervals.length - 1

  while left <= right
    mid = (left + right) / 2
    # @type var interval_start: Integer
    # @type var interval_end: Integer
    interval_start, interval_end = @intervals[mid]

    if interval_end < query_start
      left = mid + 1
    elsif interval_start > query_end
      right = mid - 1
    else
      # Found overlap
      return true
    end
  end

  false
end