Class: DeadEnd::CodeFrontier

Inherits:
Object
  • Object
show all
Defined in:
lib/dead_end/code_frontier.rb

Overview

There are three main phases in the algorithm:

  1. Sanitize/format input source

  2. Search for invalid blocks

  3. Format invalid blocks into something meaninful

The Code frontier is a critical part of the second step

## Knowing where we’ve been

Once a code block is generated it is added onto the frontier. Then it will be sorted by indentation and frontier can be filtered. Large blocks that fully enclose a smaller block will cause the smaller block to be evicted.

CodeFrontier#<<(block) # Adds block to frontier
CodeFrontier#pop # Removes block from frontier

## Knowing where we can go

Internally the frontier keeps track of “unvisited” lines which are exposed via ‘next_indent_line` when called, this method returns, a line of code with the highest indentation.

The returned line of code can be used to build a CodeBlock and then that code block is added back to the frontier. Then, the lines are removed from the “unvisited” so we don’t double-create the same block.

CodeFrontier#next_indent_line # Shows next line
CodeFrontier#register_indent_block(block) # Removes lines from unvisited

## Knowing when to stop

The frontier knows how to check the entire document for a syntax error. When blocks are added onto the frontier, they’re removed from the document. When all code containing syntax errors has been added to the frontier, the document will be parsable without a syntax error and the search can stop.

CodeFrontier#holds_all_syntax_errors? # Returns true when frontier holds all syntax errors

## Filtering false positives

Once the search is completed, the frontier may have multiple blocks that do not contain the syntax error. To limit the result to the smallest subset of “invalid blocks” call:

CodeFrontier#detect_invalid_blocks

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(code_lines:, unvisited: UnvisitedLines.new(code_lines: code_lines)) ⇒ CodeFrontier

Returns a new instance of CodeFrontier.



53
54
55
56
57
58
59
 
# File 'lib/dead_end/code_frontier.rb', line 53

def initialize(code_lines:, unvisited: UnvisitedLines.new(code_lines: code_lines))
  @code_lines = code_lines
  @unvisited = unvisited
  @queue = PriorityEngulfQueue.new

  @check_next = true
end

Class Method Details

.combination(array) ⇒ Object

Example:

combination([:a, :b, :c, :d])
# => [[:a], [:b], [:c], [:d], [:a, :b], [:a, :c], [:a, :d], [:b, :c], [:b, :d], [:c, :d], [:a, :b, :c], [:a, :b, :d], [:a, :c, :d], [:b, :c, :d], [:a, :b, :c, :d]]



162
163
164
165
166
167
168
 
# File 'lib/dead_end/code_frontier.rb', line 162

def self.combination(array)
  guesses = []
  1.upto(array.length).each do |size|
    guesses.concat(array.combination(size).to_a)
  end
  guesses
end

Instance Method Details

#<<(block) ⇒ Object

Add a block to the frontier

This method ensures the frontier always remains sorted (in indentation order) and that each code block’s lines are removed from the indentation hash so we don’t re-evaluate the same line multiple times.



148
149
150
151
152
153
154
155
156
 
# File 'lib/dead_end/code_frontier.rb', line 148

def <<(block)
  @unvisited.visit_block(block)

  @queue.push(block)

  @check_next = true if block.invalid?

  self
end

#count ⇒ Object 



61
62
63
 
# File 'lib/dead_end/code_frontier.rb', line 61

def count
  @queue.length
end

#detect_invalid_blocks ⇒ Object

Given that we know our syntax error exists somewhere in our frontier, we want to find the smallest possible set of blocks that contain all the syntax errors



172
173
174
175
176
 
# File 'lib/dead_end/code_frontier.rb', line 172

def detect_invalid_blocks
  self.class.combination(@queue.to_a.select(&:invalid?)).detect do |block_array|
    holds_all_syntax_errors?(block_array, can_cache: false)
  end || []
end

#expand? ⇒ Boolean

Returns:

  • (Boolean) 


111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/dead_end/code_frontier.rb', line 111

def expand?
  return false if @queue.empty?
  return true if @unvisited.empty?

  frontier_indent = @queue.peek.current_indent
  unvisited_indent = next_indent_line.indent

  if ENV["DEBUG"]
    puts "```"
    puts @queue.peek.to_s
    puts "```"
    puts "  @frontier indent:  #{frontier_indent}"
    puts "  @unvisited indent: #{unvisited_indent}"
  end

  # Expand all blocks before moving to unvisited lines
  frontier_indent >= unvisited_indent
end

#holds_all_syntax_errors?(block_array = @queue, can_cache: true) ⇒ Boolean

Returns true if the document is valid with all lines removed. By default it checks all blocks in present in the frontier array, but can be used for arbitrary arrays of codeblocks as well

Returns:

  • (Boolean) 


89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/dead_end/code_frontier.rb', line 89

def holds_all_syntax_errors?(block_array = @queue, can_cache: true)
  return false if can_cache && can_skip_check?

  without_lines = block_array.to_a.flat_map do |block|
    block.lines
  end

  DeadEnd.valid_without?(
    without_lines: without_lines,
    code_lines: @code_lines
  )
end

#next_indent_line ⇒ Object 



107
108
109
 
# File 'lib/dead_end/code_frontier.rb', line 107

def next_indent_line
  @unvisited.peek
end

#pop ⇒ Object

Returns a code block with the largest indentation possible



103
104
105
 
# File 'lib/dead_end/code_frontier.rb', line 103

def pop
  @queue.pop
end

#register_engulf_block(block) ⇒ Object

When one element fully encapsulates another we remove the smaller block from the frontier. This prevents double expansions and all-around weird behavior. However this guarantee is quite expensive to maintain



140
141
 
# File 'lib/dead_end/code_frontier.rb', line 140

def register_engulf_block(block)
end

#register_indent_block(block) ⇒ Object

Keeps track of what lines have been added to blocks and which are not yet visited.



132
133
134
135
 
# File 'lib/dead_end/code_frontier.rb', line 132

def register_indent_block(block)
  @unvisited.visit_block(block)
  self
end