/
action.rb
242 lines (215 loc) · 9.24 KB
/
action.rb
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
# frozen_string_literal: true
module Parser
module Source
##
# @api private
#
# Actions are arranged in a tree and get combined so that:
# children are strictly contained by their parent
# sibblings all disjoint from one another and ordered
# only actions with replacement==nil may have children
#
class TreeRewriter::Action
attr_reader :range, :replacement, :insert_before, :insert_after
def initialize(range, enforcer,
insert_before: '',
replacement: nil,
insert_after: '',
children: []
)
@range, @enforcer, @children, @insert_before, @replacement, @insert_after =
range, enforcer, children.freeze, insert_before.freeze, replacement, insert_after.freeze
freeze
end
def combine(action)
return self if action.empty? # Ignore empty action
do_combine(action)
end
def empty?
@insert_before.empty? &&
@insert_after.empty? &&
@children.empty? &&
(@replacement == nil || (@replacement.empty? && @range.empty?))
end
def ordered_replacements
reps = []
reps << [@range.begin, @insert_before] unless @insert_before.empty?
reps << [@range, @replacement] if @replacement
reps.concat(@children.flat_map(&:ordered_replacements))
reps << [@range.end, @insert_after] unless @insert_after.empty?
reps
end
def nested_actions
actions = []
actions << [:wrap, @range, @insert_before, @insert_after] if !@insert_before.empty? ||
!@insert_after.empty?
actions << [:replace, @range, @replacement] if @replacement
actions.concat(@children.flat_map(&:nested_actions))
end
def insertion?
!insert_before.empty? || !insert_after.empty? || (replacement && !replacement.empty?)
end
##
# A root action has its range set to the whole source range, even
# though it typically do not act on that range.
# This method returns the action as if it was a child action with
# its range contracted.
# @return [Action]
def contract
raise 'Empty actions can not be contracted' if empty?
return self if insertion?
range = @range.with(
begin_pos: children.first.range.begin_pos,
end_pos: children.last.range.end_pos,
)
with(range: range)
end
##
# @return [Action] that has been moved to the given source_buffer and with the given offset
# No check is done on validity of resulting range.
def moved(source_buffer, offset)
moved_range = ::Parser::Source::Range.new(
source_buffer,
@range.begin_pos + offset,
@range.end_pos + offset
)
with(
range: moved_range,
children: children.map { |child| child.moved(source_buffer, offset) }
)
end
protected
attr_reader :children
def with(range: @range, enforcer: @enforcer, children: @children, insert_before: @insert_before, replacement: @replacement, insert_after: @insert_after)
children = swallow(children) if replacement
self.class.new(range, enforcer, children: children, insert_before: insert_before, replacement: replacement, insert_after: insert_after)
end
# Assumes range.contains?(action.range) && action.children.empty?
def do_combine(action)
if action.range == @range
merge(action)
else
place_in_hierarchy(action)
end
end
def place_in_hierarchy(action)
family = analyse_hierarchy(action)
if family[:fusible]
fuse_deletions(action, family[:fusible], [*family[:sibbling_left], *family[:child], *family[:sibbling_right]])
else
extra_sibbling = if family[:parent] # action should be a descendant of one of the children
family[:parent].do_combine(action)
elsif family[:child] # or it should become the parent of some of the children,
action.with(children: family[:child], enforcer: @enforcer)
.combine_children(action.children)
else # or else it should become an additional child
action
end
with(children: [*family[:sibbling_left], extra_sibbling, *family[:sibbling_right]])
end
end
# Assumes `more_children` all contained within `@range`
def combine_children(more_children)
more_children.inject(self) do |parent, new_child|
parent.place_in_hierarchy(new_child)
end
end
def fuse_deletions(action, fusible, other_sibblings)
without_fusible = with(children: other_sibblings)
fused_range = [action, *fusible].map(&:range).inject(:join)
fused_deletion = action.with(range: fused_range)
without_fusible.do_combine(fused_deletion)
end
# Similar to @children.bsearch_index || size
# except allows for a starting point
# and `bsearch_index` is only Ruby 2.3+
def bsearch_child_index(from = 0)
size = @children.size
(from...size).bsearch { |i| yield @children[i] } || size
end
# Returns the children in a hierarchy with respect to `action`:
# :sibbling_left, sibbling_right (for those that are disjoint from `action`)
# :parent (in case one of our children contains `action`)
# :child (in case `action` strictly contains some of our children)
# :fusible (in case `action` overlaps some children but they can be fused in one deletion)
# or raises a `CloberingError`
# In case a child has equal range to `action`, it is returned as `:parent`
# Reminder: an empty range 1...1 is considered disjoint from 1...10
def analyse_hierarchy(action)
r = action.range
# left_index is the index of the first child that isn't completely to the left of action
left_index = bsearch_child_index { |child| child.range.end_pos > r.begin_pos }
# right_index is the index of the first child that is completely on the right of action
start = left_index == 0 ? 0 : left_index - 1 # See "corner case" below for reason of -1
right_index = bsearch_child_index(start) { |child| child.range.begin_pos >= r.end_pos }
center = right_index - left_index
case center
when 0
# All children are disjoint from action, nothing else to do
when -1
# Corner case: if a child has empty range == action's range
# then it will appear to be both disjoint and to the left of action,
# as well as disjoint and to the right of action.
# Since ranges are equal, we return it as parent
left_index -= 1 # Fix indices, as otherwise this child would be
right_index += 1 # considered as a sibbling (both left and right!)
parent = @children[left_index]
else
overlap_left = @children[left_index].range.begin_pos <=> r.begin_pos
overlap_right = @children[right_index-1].range.end_pos <=> r.end_pos
# For one child to be the parent of action, we must have:
if center == 1 && overlap_left <= 0 && overlap_right >= 0
parent = @children[left_index]
else
# Otherwise consider all non disjoint elements (center) to be contained...
contained = @children[left_index...right_index]
fusible = check_fusible(action,
(contained.shift if overlap_left < 0), # ... but check first and last one
(contained.pop if overlap_right > 0) # ... for overlaps
)
end
end
{
parent: parent,
sibbling_left: @children[0...left_index],
sibbling_right: @children[right_index...@children.size],
fusible: fusible,
child: contained,
}
end
# @param [Array(Action | nil)] fusible
def check_fusible(action, *fusible)
fusible.compact!
return if fusible.empty?
fusible.each do |child|
kind = action.insertion? || child.insertion? ? :crossing_insertions : :crossing_deletions
@enforcer.call(kind) { {range: action.range, conflict: child.range} }
end
fusible
end
# Assumes action.range == range && action.children.empty?
def merge(action)
call_enforcer_for_merge(action)
with(
insert_before: "#{action.insert_before}#{insert_before}",
replacement: action.replacement || @replacement,
insert_after: "#{insert_after}#{action.insert_after}",
).combine_children(action.children)
end
def call_enforcer_for_merge(action)
@enforcer.call(:different_replacements) do
if @replacement && action.replacement && @replacement != action.replacement
{range: @range, replacement: action.replacement, other_replacement: @replacement}
end
end
end
def swallow(children)
@enforcer.call(:swallowed_insertions) do
insertions = children.select(&:insertion?)
{range: @range, conflict: insertions.map(&:range)} unless insertions.empty?
end
[]
end
end
end
end