1use super::*;
2
3impl Arena {
4 pub fn push_list_prepend(&mut self, head: NanValue, tail: NanValue) -> u32 {
5 debug_assert!(tail.is_list());
6 let len = self.list_len(tail.arena_index()) + 1;
7 self.push(ArenaEntry::List(ArenaList::Prepend { head, tail, len }))
8 }
9
10 pub fn push_list_append(&mut self, list: NanValue, value: NanValue) -> u32 {
11 debug_assert!(list.is_list());
12 if self.list_is_empty(list.arena_index()) {
13 return self.push_list(vec![value]);
14 }
15
16 match self.get_list(list.arena_index()).clone() {
17 ArenaList::Flat { items, start } => {
18 let slice = &items[start..];
19 if slice.len() < LIST_APPEND_CHUNK_LIMIT {
20 let mut out = Vec::with_capacity(slice.len() + 1);
21 out.extend(slice.iter().copied());
22 out.push(value);
23 return self.push_list(out);
24 }
25 }
26 ArenaList::Concat { left, right, len } => {
27 if let ArenaList::Flat { items, start } = self.get_list(right.arena_index()).clone()
28 {
29 let slice = &items[start..];
30 if slice.len() < LIST_APPEND_CHUNK_LIMIT {
31 let mut out = Vec::with_capacity(slice.len() + 1);
32 out.extend(slice.iter().copied());
33 out.push(value);
34 let right_idx = self.push_list(out);
35 return self.push(ArenaEntry::List(ArenaList::Concat {
36 left,
37 right: NanValue::new_list(right_idx),
38 len: len + 1,
39 }));
40 }
41 }
42 }
43 ArenaList::Prepend { .. } | ArenaList::Segments { .. } => {}
44 }
45
46 let singleton_idx = self.push_list(vec![value]);
47 self.push_list_concat(list, NanValue::new_list(singleton_idx))
48 }
49
50 pub fn push_list_concat(&mut self, left: NanValue, right: NanValue) -> u32 {
51 debug_assert!(left.is_list());
52 debug_assert!(right.is_list());
53 let len = self.list_len(left.arena_index()) + self.list_len(right.arena_index());
54 self.push(ArenaEntry::List(ArenaList::Concat { left, right, len }))
55 }
56
57 pub fn list_len(&self, index: u32) -> usize {
58 match self.get_list(index) {
59 ArenaList::Flat { items, start } => items.len().saturating_sub(*start),
60 ArenaList::Prepend { len, .. }
61 | ArenaList::Concat { len, .. }
62 | ArenaList::Segments { len, .. } => *len,
63 }
64 }
65
66 pub fn list_is_empty(&self, index: u32) -> bool {
67 self.list_len(index) == 0
68 }
69
70 pub fn list_get(&self, index: u32, position: usize) -> Option<NanValue> {
71 let mut current = NanValue::new_list(index);
72 let mut remaining = position;
73
74 loop {
75 match self.get_list(current.arena_index()) {
76 ArenaList::Flat { items, start } => {
77 return items.get(start.saturating_add(remaining)).copied();
78 }
79 ArenaList::Prepend { head, tail, .. } => {
80 if remaining == 0 {
81 return Some(*head);
82 }
83 remaining -= 1;
84 current = *tail;
85 }
86 ArenaList::Concat { left, right, .. } => {
87 let left_len = self.list_len(left.arena_index());
88 if remaining < left_len {
89 current = *left;
90 } else {
91 remaining -= left_len;
92 current = *right;
93 }
94 }
95 ArenaList::Segments {
96 current: head,
97 rest,
98 start,
99 ..
100 } => {
101 let head_len = self.list_len(head.arena_index());
102 if remaining < head_len {
103 current = *head;
104 } else {
105 remaining -= head_len;
106 let mut found = None;
107 for part in &rest[*start..] {
108 let part_len = self.list_len(part.arena_index());
109 if remaining < part_len {
110 found = Some(*part);
111 break;
112 }
113 remaining -= part_len;
114 }
115 current = found?;
116 }
117 }
118 }
119 }
120 }
121
122 pub fn list_to_vec(&self, index: u32) -> Vec<NanValue> {
123 let mut out = Vec::with_capacity(self.list_len(index));
124 let mut stack = vec![NanValue::new_list(index)];
125
126 while let Some(list) = stack.pop() {
127 match self.get_list(list.arena_index()) {
128 ArenaList::Flat { items, start } => {
129 out.extend(items[*start..].iter().copied());
130 }
131 ArenaList::Prepend { head, tail, .. } => {
132 out.push(*head);
133 stack.push(*tail);
134 }
135 ArenaList::Concat { left, right, .. } => {
136 stack.push(*right);
137 stack.push(*left);
138 }
139 ArenaList::Segments {
140 current,
141 rest,
142 start,
143 ..
144 } => {
145 for part in rest[*start..].iter().rev() {
146 stack.push(*part);
147 }
148 stack.push(*current);
149 }
150 }
151 }
152
153 out
154 }
155
156 pub fn list_uncons(&mut self, list: NanValue) -> Option<(NanValue, NanValue)> {
157 debug_assert!(list.is_list());
158 let mut rights = Vec::new();
159 let mut current = list;
160
161 loop {
162 match self.get_list(current.arena_index()).clone() {
163 ArenaList::Flat { items, start } => {
164 let head = *items.get(start)?;
165 let tail = if start + 1 >= items.len() {
166 self.empty_list_value()
167 } else {
168 let tail_idx = self.push(ArenaEntry::List(ArenaList::Flat {
169 items: Rc::clone(&items),
170 start: start + 1,
171 }));
172 NanValue::new_list(tail_idx)
173 };
174 rights.reverse();
175 return Some((head, self.push_list_segments(tail, rights)));
176 }
177 ArenaList::Prepend { head, tail, .. } => {
178 rights.reverse();
179 return Some((head, self.push_list_segments(tail, rights)));
180 }
181 ArenaList::Concat { left, right, .. } => {
182 if self.list_is_empty(left.arena_index()) {
183 current = right;
184 } else {
185 rights.push(right);
186 current = left;
187 }
188 }
189 ArenaList::Segments {
190 current: head_segment,
191 rest,
192 start,
193 ..
194 } => {
195 let (head, tail) = self.list_uncons(head_segment)?;
196 return Some((
197 head,
198 self.push_list_segments_rc(tail, Rc::clone(&rest), start),
199 ));
200 }
201 }
202 }
203 }
204
205 fn empty_list_value(&mut self) -> NanValue {
206 NanValue::new_list(self.push_list(Vec::new()))
207 }
208
209 fn push_list_segments(&mut self, current: NanValue, rest: Vec<NanValue>) -> NanValue {
210 let filtered: Vec<NanValue> = rest
211 .into_iter()
212 .filter(|part| !self.list_is_empty(part.arena_index()))
213 .collect();
214 self.push_list_segments_rc(current, Rc::new(filtered), 0)
215 }
216
217 fn push_list_segments_rc(
218 &mut self,
219 mut current: NanValue,
220 rest: Rc<Vec<NanValue>>,
221 mut start: usize,
222 ) -> NanValue {
223 while self.list_is_empty(current.arena_index()) {
224 if let Some(next) = rest.get(start).copied() {
225 current = next;
226 start += 1;
227 } else {
228 return self.empty_list_value();
229 }
230 }
231
232 if start >= rest.len() {
233 return current;
234 }
235
236 let len = self.list_len(current.arena_index())
237 + rest[start..]
238 .iter()
239 .map(|part| self.list_len(part.arena_index()))
240 .sum::<usize>();
241 let idx = self.push(ArenaEntry::List(ArenaList::Segments {
242 current,
243 rest,
244 start,
245 len,
246 }));
247 NanValue::new_list(idx)
248 }
249}