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:



408
409
410
411
412
413
414
415
416
417
 
# File 'lib/red_quilt/arena.rb', line 408

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.



368
369
370
371
372
373
374
375
376
 
# File 'lib/red_quilt/arena.rb', line 368

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

#code_block_info(id) ⇒ Object

CODE_BLOCK: the fence info string (e.g. ‘ruby’, ‘vtt audio=“x”’).



284
285
286
 
# File 'lib/red_quilt/arena.rb', line 284

def code_block_info(id)
  @str2[id]
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.



356
357
358
359
360
361
362
363
 
# File 'lib/red_quilt/arena.rb', line 356

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

#footnote_label(id) ⇒ Object

FOOTNOTE_REFERENCE / FOOTNOTE_DEFINITION: the author-written label.



310
311
312
 
# File 'lib/red_quilt/arena.rb', line 310

def footnote_label(id)
  @str1[id]
end

#footnote_number(id) ⇒ Object

FOOTNOTE_REFERENCE: the assigned footnote number.



299
300
301
 
# File 'lib/red_quilt/arena.rb', line 299

def footnote_number(id)
  @int1[id]
end

#footnote_occurrence(id) ⇒ Object

FOOTNOTE_REFERENCE: which occurrence of a repeated reference this is (1-based), used to give each backref a unique anchor.



305
306
307
 
# File 'lib/red_quilt/arena.rb', line 305

def footnote_occurrence(id)
  @int2[id]
end

#footnote_total_references(id) ⇒ Object

FOOTNOTE_DEFINITION: total number of references to this footnote, materialized by FootnotePass so renderers can read it off the node instead of consulting the registry. (FOOTNOTE_REFERENCE reuses int2 for its own occurrence index; see #footnote_occurrence.)



318
319
320
 
# File 'lib/red_quilt/arena.rb', line 318

def footnote_total_references(id)
  @int2[id]
end

#heading_level(id) ⇒ Object

HEADING: nesting level (1..6).



249
250
251
 
# File 'lib/red_quilt/arena.rb', line 249

def heading_level(id)
  @int1[id]
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

#link_destination(id) ⇒ Object

LINK / IMAGE: destination URL.



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

def link_destination(id)
  @str1[id]
end

#link_title(id) ⇒ Object

LINK / IMAGE: optional title attribute (nil/empty when absent).



294
295
296
 
# File 'lib/red_quilt/arena.rb', line 294

def link_title(id)
  @str2[id]
end

#list_delimiter(id) ⇒ Object

LIST: the item delimiter as authored (e.g. “-”, “1.”).



269
270
271
 
# File 'lib/red_quilt/arena.rb', line 269

def list_delimiter(id)
  @str1[id]
end

#list_ordered?(id) ⇒ Boolean

LIST: ordered (‘1.`) vs bullet (`-`).

Returns:

  • (Boolean) 


254
255
256
 
# File 'lib/red_quilt/arena.rb', line 254

def list_ordered?(id)
  @int1[id] == 1
end

#list_start(id) ⇒ Object

LIST: the start number of an ordered list (1 unless overridden).



259
260
261
 
# File 'lib/red_quilt/arena.rb', line 259

def list_start(id)
  @int2[id]
end

#list_tight?(id) ⇒ Boolean

LIST: tight (no blank lines between items) vs loose.

Returns:

  • (Boolean) 


264
265
266
 
# File 'lib/red_quilt/arena.rb', line 264

def list_tight?(id)
  @int3[id] == 1
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

#resolve_footnote_definition(id, number, total_references) ⇒ Object

FOOTNOTE_DEFINITION: records the resolved number and total reference count onto the node (read back via #footnote_number / #footnote_total_references).



325
326
327
328
 
# File 'lib/red_quilt/arena.rb', line 325

def resolve_footnote_definition(id, number, total_references)
  @int1[id] = number
  @int2[id] = total_references
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).



332
333
334
335
336
337
 
# File 'lib/red_quilt/arena.rb', line 332

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

#table_cell_header?(id) ⇒ Boolean

TABLE_CELL: header cell (<th>) vs data cell (<td>).

Returns:

  • (Boolean) 


279
280
281
 
# File 'lib/red_quilt/arena.rb', line 279

def table_cell_header?(id)
  @int1[id] == 1
end

#table_row_header?(id) ⇒ Boolean

TABLE_ROW: header row (rendered in <thead>) vs body row.

Returns:

  • (Boolean) 


274
275
276
 
# File 'lib/red_quilt/arena.rb', line 274

def table_row_header?(id)
  @int1[id] == 1
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.



343
344
345
346
347
348
349
350
351
 
# File 'lib/red_quilt/arena.rb', line 343

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 



382
383
384
 
# File 'lib/red_quilt/arena.rb', line 382

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

#update_span(id, start_byte, end_byte) ⇒ Object 



386
387
388
389
 
# File 'lib/red_quilt/arena.rb', line 386

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 



378
379
380
 
# File 'lib/red_quilt/arena.rb', line 378

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