1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
67
68
69
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
# frozen_string_literal: true
module SyntaxSuggest
# The main function of the frontier is to hold the edges of our search and to
# evaluate when we can stop searching.
# 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 CodeFrontier
def initialize(code_lines:, unvisited: UnvisitedLines.new(code_lines: code_lines))
@code_lines = code_lines
@unvisited = unvisited
@queue = PriorityEngulfQueue.new
@check_next = true
end
def count
@queue.length
end
# Performance optimization
#
# Parsing with ripper is expensive
# If we know we don't have any blocks with invalid
# syntax, then we know we cannot have found
# the incorrect syntax yet.
#
# When an invalid block is added onto the frontier
# check document state
private def can_skip_check?
check_next = @check_next
@check_next = false
if check_next
false
else
true
end
end
# 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
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
SyntaxSuggest.valid_without?(
without_lines: without_lines,
code_lines: @code_lines
)
end
# Returns a code block with the largest indentation possible
def pop
@queue.pop
end
def next_indent_line
@unvisited.peek
end
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["SYNTAX_SUGGEST_DEBUG"]
puts "```"
puts @queue.peek
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
# Keeps track of what lines have been added to blocks and which are not yet
# visited.
def register_indent_block(block)
@unvisited.visit_block(block)
self
end
# 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
def register_engulf_block(block)
end
# 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.
def <<(block)
@unvisited.visit_block(block)
@queue.push(block)
@check_next = true if block.invalid?
self
end
# 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]]
def self.combination(array)
guesses = []
1.upto(array.length).each do |size|
guesses.concat(array.combination(size).to_a)
end
guesses
end
# 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
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
end
end
|
