Class: RedQuilt::Arena

Inherits:
Object
  • Object
show all
Defined in:
lib/red_quilt/arena.rb

Overview

Parallel-array storage for AST nodes.

Each node has a single integer id (its position in the columns). All structural and payload fields are stored as columns keyed by id:

structural   parent, first_child, last_child, next_sibling, prev_sibling
source span  source_start (byte offset, -1 = no span), source_len
payload      int1..int3, str1, str2  (per-NodeType conventions)

Invariants:

  • id starts at 0 and grows monotonically with #add_node. Ids are never reassigned and never reclaimed; a #detach’ed node keeps its row in the columns and stays addressable (its parent / siblings are reset to NO_NODE) but is no longer reachable from the tree. This means the arena’s memory is monotone non-decreasing for the lifetime of a parse — a deliberate trade for allocation simplicity.

  • NO_NODE (= -1) is the sentinel value used for “no parent”, “no sibling”, and as a source_start to mean “this node has no span; its content is materialized in str1 instead”.

  • @source is the original document string. It is treated as immutable: callers must not mutate it after constructing the arena, since byteslice positions stored in source_start/source_len refer to it directly.

Defined Under Namespace

Classes: IntegrityError

Constant Summary collapse

NO_NODE = 
-1

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(source) ⇒ Arena

Returns a new instance of Arena.



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/red_quilt/arena.rb', line 35

def initialize(source)
  @source = source
  @type = []
  @parent = []
  @first_child = []
  @last_child = []
  @next_sibling = []
  @prev_sibling = []
  @source_start = []
  @source_len = []
  @int1 = []
  @int2 = []
  @int3 = []
  @str1 = []
  @str2 = []
end

Instance Attribute Details

#source ⇒ Object (readonly)

Returns the value of attribute source.



33
34
35
 
# File 'lib/red_quilt/arena.rb', line 33

def source
  @source
end

Instance Method Details

#add_node(type, source_start: NO_NODE, source_len: 0, int1: 0, int2: 0, int3: 0, str1: nil, str2: nil) ⇒ Object

Appends a fresh node to the arena and returns its id. The node starts detached (parent = first_child = … = NO_NODE).



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/red_quilt/arena.rb', line 54

def add_node(type, source_start: NO_NODE, source_len: 0, int1: 0, int2: 0, int3: 0, str1: nil, str2: nil)
  id = @type.length
  @type[id] = type
  @parent[id] = NO_NODE
  @first_child[id] = NO_NODE
  @last_child[id] = NO_NODE
  @next_sibling[id] = NO_NODE
  @prev_sibling[id] = NO_NODE
  @source_start[id] = source_start
  @source_len[id] = source_len
  @int1[id] = int1
  @int2[id] = int2
  @int3[id] = int3
  @str1[id] = str1
  @str2[id] = str2
  id
end

#append_child(parent_id, child_id) ⇒ Object 



72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/red_quilt/arena.rb', line 72

def append_child(parent_id, child_id)
  @parent[child_id] = parent_id
  if @first_child[parent_id] == NO_NODE
    @first_child[parent_id] = child_id
    @last_child[parent_id] = child_id
  else
    last = @last_child[parent_id]
    @next_sibling[last] = child_id
    @prev_sibling[child_id] = last
    @last_child[parent_id] = child_id
  end
  child_id
end

#check_integrity!(root_id) ⇒ Object

Verifies the structural invariants of the tree rooted at root_id. Raises IntegrityError on the first violation, including the offending node id(s) and a description of the broken rule.

Checked invariants:

  • root has parent = NO_NODE

  • for every reachable node ‘n` and its first_child / last_child `fc` / `lc`:

    * fc and lc are both NO_NODE, or both not NO_NODE
* walking next_sibling from fc reaches lc and only lc
* for each child `c`, @parent[c] == n
* for each child `c`, @prev_sibling[c] equals the previously
  visited sibling (or NO_NODE for the first)

  • no node is reached twice (no shared subtrees, no cycles)

Intended for development / debugging. Not called by the production parse / render path.

Raises:



312
313
314
315
316
317
318
319
320
321
 
# File 'lib/red_quilt/arena.rb', line 312

def check_integrity!(root_id)
  raise IntegrityError, "root_id #{root_id} has no row" if root_id >= @type.length
  if @parent[root_id] != NO_NODE
    raise IntegrityError, "root #{root_id} has non-NO_NODE parent #{@parent[root_id]}"
  end

  visited = {}
  walk_for_integrity(root_id, NO_NODE, visited)
  self
end

#child_ids(id) ⇒ Object

Returns an Enumerator yielding each child id. Kept for the external NodeRef API where Enumerator chaining (map, select, …) is convenient.



272
273
274
275
276
277
278
279
280
 
# File 'lib/red_quilt/arena.rb', line 272

def child_ids(id)
  Enumerator.new do |yielder|
    child_id = @first_child[id]
    until child_id == NO_NODE
      yielder << child_id
      child_id = @next_sibling[child_id]
    end
  end
end

#detach(child_id) ⇒ Object

Removes child_id from its current parent. The node’s row stays in the arena (its payload columns are untouched) but parent / siblings are reset to NO_NODE, so the node is no longer reachable through any tree walk. Detached rows are not reused by subsequent #add_node calls.



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/red_quilt/arena.rb', line 106

def detach(child_id)
  parent_id = @parent[child_id]
  prev_id = @prev_sibling[child_id]
  next_id = @next_sibling[child_id]

  if prev_id == NO_NODE
    @first_child[parent_id] = next_id
  else
    @next_sibling[prev_id] = next_id
  end

  if next_id == NO_NODE
    @last_child[parent_id] = prev_id
  else
    @prev_sibling[next_id] = prev_id
  end

  @parent[child_id] = NO_NODE
  @prev_sibling[child_id] = NO_NODE
  @next_sibling[child_id] = NO_NODE
  child_id
end

#each_child(id) ⇒ Object

Yields each child id of ‘id` in order. Block form is preferred over #child_ids on hot paths (renderer, builder) because it avoids the Enumerator allocation.



260
261
262
263
264
265
266
267
 
# File 'lib/red_quilt/arena.rb', line 260

def each_child(id)
  child_id = @first_child[id]
  until child_id == NO_NODE
    yield child_id
    child_id = @next_sibling[child_id]
  end
  self
end

#insert_before(parent_id, ref_id, new_id) ⇒ Object

Inserts new_id immediately before ref_id in parent_id’s child list.



87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/red_quilt/arena.rb', line 87

def insert_before(parent_id, ref_id, new_id)
  @parent[new_id] = parent_id
  prev_ref = @prev_sibling[ref_id]
  @prev_sibling[new_id] = prev_ref
  @next_sibling[new_id] = ref_id
  @prev_sibling[ref_id] = new_id
  if prev_ref == NO_NODE
    @first_child[parent_id] = new_id
  else
    @next_sibling[prev_ref] = new_id
  end
  new_id
end

#int1(id) ⇒ Object 



214
215
216
 
# File 'lib/red_quilt/arena.rb', line 214

def int1(id)
  @int1[id]
end

#int2(id) ⇒ Object 



218
219
220
 
# File 'lib/red_quilt/arena.rb', line 218

def int2(id)
  @int2[id]
end

#int3(id) ⇒ Object 



222
223
224
 
# File 'lib/red_quilt/arena.rb', line 222

def int3(id)
  @int3[id]
end

#raw_first_child_id(id) ⇒ Object 



185
186
187
 
# File 'lib/red_quilt/arena.rb', line 185

def raw_first_child_id(id)
  @first_child[id]
end

#raw_last_child_id(id) ⇒ Object 



189
190
191
 
# File 'lib/red_quilt/arena.rb', line 189

def raw_last_child_id(id)
  @last_child[id]
end

#raw_next_sibling_id(id) ⇒ Object 



193
194
195
 
# File 'lib/red_quilt/arena.rb', line 193

def raw_next_sibling_id(id)
  @next_sibling[id]
end

#raw_parent_id(id) ⇒ Object

Structural id accessors. The ‘raw_` prefix flags that these return raw column values that may be the NO_NODE sentinel, and the `_id` suffix flags that the returned integer is a node id (suitable for feeding back into other Arena methods).



181
182
183
 
# File 'lib/red_quilt/arena.rb', line 181

def raw_parent_id(id)
  @parent[id]
end

#raw_prev_sibling_id(id) ⇒ Object 



197
198
199
 
# File 'lib/red_quilt/arena.rb', line 197

def raw_prev_sibling_id(id)
  @prev_sibling[id]
end

#reparent(new_parent_id, first_id, last_id) ⇒ Object

Moves a contiguous sibling range [first_id .. last_id] (both inclusive, walking #next_sibling from first to last) under new_parent_id, replacing any existing children there. The walk assumes the range is well-formed; passing nodes from different parents or a last_id not reachable from first_id is undefined behavior.



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
 
# File 'lib/red_quilt/arena.rb', line 135

def reparent(new_parent_id, first_id, last_id)
  return if first_id == NO_NODE || last_id == NO_NODE

  original_parent = @parent[first_id]
  prev_of_first = @prev_sibling[first_id]
  next_of_last = @next_sibling[last_id]

  if prev_of_first == NO_NODE
    @first_child[original_parent] = next_of_last
  else
    @next_sibling[prev_of_first] = next_of_last
  end

  if next_of_last == NO_NODE
    @last_child[original_parent] = prev_of_first
  else
    @prev_sibling[next_of_last] = prev_of_first
  end

  @prev_sibling[first_id] = NO_NODE
  @next_sibling[last_id] = NO_NODE

  id = first_id
  loop do
    @parent[id] = new_parent_id
    break if id == last_id

    id = @next_sibling[id]
  end

  @first_child[new_parent_id] = first_id
  @last_child[new_parent_id] = last_id
end

#source_end(id) ⇒ Object

Byte offset one past the node’s source span (start + len).



210
211
212
 
# File 'lib/red_quilt/arena.rb', line 210

def source_end(id)
  @source_start[id] + @source_len[id]
end

#source_len(id) ⇒ Object 



205
206
207
 
# File 'lib/red_quilt/arena.rb', line 205

def source_len(id)
  @source_len[id]
end

#source_span(id) ⇒ Object

Returns a SourceSpan for the node, or nil when the node has no span (source_start < 0, meaning the content is held in str1).



236
237
238
239
240
241
 
# File 'lib/red_quilt/arena.rb', line 236

def source_span(id)
  start_byte = @source_start[id]
  return nil if start_byte.nil? || start_byte.negative?

  SourceSpan.new(start_byte, start_byte + @source_len[id])
end

#source_start(id) ⇒ Object 



201
202
203
 
# File 'lib/red_quilt/arena.rb', line 201

def source_start(id)
  @source_start[id]
end

#str1(id) ⇒ Object 



226
227
228
 
# File 'lib/red_quilt/arena.rb', line 226

def str1(id)
  @str1[id]
end

#str2(id) ⇒ Object 



230
231
232
 
# File 'lib/red_quilt/arena.rb', line 230

def str2(id)
  @str2[id]
end

#text(id) ⇒ Object

Returns the node’s textual content. Prefers str1 (the literal form, e.g. an entity decoded to its character, or a reassembled blockquote line). Falls back to a byteslice of @source when only a span is recorded. Returns nil if neither is available.



247
248
249
250
251
252
253
254
255
 
# File 'lib/red_quilt/arena.rb', line 247

def text(id)
  literal = @str1[id]
  return literal unless literal.nil?

  start_byte = @source_start[id]
  return nil if start_byte.nil? || start_byte.negative?

  @source.byteslice(start_byte, @source_len[id])
end

#type(id) ⇒ Object 



169
170
171
 
# File 'lib/red_quilt/arena.rb', line 169

def type(id)
  @type[id]
end

#type_name(id) ⇒ Object 



173
174
175
 
# File 'lib/red_quilt/arena.rb', line 173

def type_name(id)
  NodeType.name_for(@type[id])
end

#update_int3(id, value) ⇒ Object 



286
287
288
 
# File 'lib/red_quilt/arena.rb', line 286

def update_int3(id, value)
  @int3[id] = value
end

#update_span(id, start_byte, end_byte) ⇒ Object 



290
291
292
293
 
# File 'lib/red_quilt/arena.rb', line 290

def update_span(id, start_byte, end_byte)
  @source_start[id] = start_byte
  @source_len[id] = end_byte - start_byte
end

#update_str1(id, value) ⇒ Object 



282
283
284
 
# File 'lib/red_quilt/arena.rb', line 282

def update_str1(id, value)
  @str1[id] = value
end