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_value(tail) + 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_value(list) {
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 if self.list_is_empty_value(left) {
54 return if right.is_empty_list_immediate() {
55 self.push_list(Vec::new())
56 } else {
57 right.arena_index()
58 };
59 }
60 if self.list_is_empty_value(right) {
61 return left.arena_index();
62 }
63 let len = self.list_len_value(left) + self.list_len_value(right);
64 self.push(ArenaEntry::List(ArenaList::Concat { left, right, len }))
65 }
66
67 pub fn list_len_value(&self, list: NanValue) -> usize {
68 if list.is_empty_list_immediate() {
69 0
70 } else {
71 self.list_len(list.arena_index())
72 }
73 }
74
75 pub fn list_is_empty_value(&self, list: NanValue) -> bool {
76 self.list_len_value(list) == 0
77 }
78
79 pub fn list_get_value(&self, list: NanValue, position: usize) -> Option<NanValue> {
80 if list.is_empty_list_immediate() {
81 None
82 } else {
83 self.list_get(list.arena_index(), position)
84 }
85 }
86
87 pub fn list_to_vec_value(&self, list: NanValue) -> Vec<NanValue> {
88 if list.is_empty_list_immediate() {
89 Vec::new()
90 } else {
91 self.list_to_vec(list.arena_index())
92 }
93 }
94
95 pub fn list_len(&self, index: u32) -> usize {
96 match self.get_list(index) {
97 ArenaList::Flat { items, start } => items.len().saturating_sub(*start),
98 ArenaList::Prepend { len, .. }
99 | ArenaList::Concat { len, .. }
100 | ArenaList::Segments { len, .. } => *len,
101 }
102 }
103
104 pub fn list_is_empty(&self, index: u32) -> bool {
105 self.list_len(index) == 0
106 }
107
108 pub fn list_get(&self, index: u32, position: usize) -> Option<NanValue> {
109 let mut current = NanValue::new_list(index);
110 let mut remaining = position;
111
112 loop {
113 if current.is_empty_list_immediate() {
114 return None;
115 }
116 match self.get_list(current.arena_index()) {
117 ArenaList::Flat { items, start } => {
118 return items.get(start.saturating_add(remaining)).copied();
119 }
120 ArenaList::Prepend { head, tail, .. } => {
121 if remaining == 0 {
122 return Some(*head);
123 }
124 remaining -= 1;
125 current = *tail;
126 }
127 ArenaList::Concat { left, right, .. } => {
128 let left_len = self.list_len_value(*left);
129 if remaining < left_len {
130 current = *left;
131 } else {
132 remaining -= left_len;
133 current = *right;
134 }
135 }
136 ArenaList::Segments {
137 current: head,
138 rest,
139 start,
140 ..
141 } => {
142 let head_len = self.list_len_value(*head);
143 if remaining < head_len {
144 current = *head;
145 } else {
146 remaining -= head_len;
147 let mut found = None;
148 for part in &rest[*start..] {
149 let part_len = self.list_len_value(*part);
150 if remaining < part_len {
151 found = Some(*part);
152 break;
153 }
154 remaining -= part_len;
155 }
156 current = found?;
157 }
158 }
159 }
160 }
161 }
162
163 pub fn list_to_vec(&self, index: u32) -> Vec<NanValue> {
164 let mut out = Vec::with_capacity(self.list_len(index));
165 let mut stack = vec![NanValue::new_list(index)];
166
167 while let Some(list) = stack.pop() {
168 if list.is_empty_list_immediate() {
169 continue;
170 }
171 match self.get_list(list.arena_index()) {
172 ArenaList::Flat { items, start } => {
173 out.extend(items[*start..].iter().copied());
174 }
175 ArenaList::Prepend { head, tail, .. } => {
176 out.push(*head);
177 stack.push(*tail);
178 }
179 ArenaList::Concat { left, right, .. } => {
180 stack.push(*right);
181 stack.push(*left);
182 }
183 ArenaList::Segments {
184 current,
185 rest,
186 start,
187 ..
188 } => {
189 for part in rest[*start..].iter().rev() {
190 stack.push(*part);
191 }
192 stack.push(*current);
193 }
194 }
195 }
196
197 out
198 }
199
200 pub fn list_uncons(&mut self, list: NanValue) -> Option<(NanValue, NanValue)> {
201 debug_assert!(list.is_list());
202 if list.is_empty_list_immediate() {
203 return None;
204 }
205 let mut rights = Vec::new();
206 let mut current = list;
207
208 loop {
209 if current.is_empty_list_immediate() {
210 return None;
211 }
212 match self.get_list(current.arena_index()).clone() {
213 ArenaList::Flat { items, start } => {
214 let head = *items.get(start)?;
215 let tail = if start + 1 >= items.len() {
216 self.empty_list_value()
217 } else {
218 let tail_idx = self.push(ArenaEntry::List(ArenaList::Flat {
219 items: Rc::clone(&items),
220 start: start + 1,
221 }));
222 NanValue::new_list(tail_idx)
223 };
224 rights.reverse();
225 return Some((head, self.push_list_segments(tail, rights)));
226 }
227 ArenaList::Prepend { head, tail, .. } => {
228 rights.reverse();
229 return Some((head, self.push_list_segments(tail, rights)));
230 }
231 ArenaList::Concat { left, right, .. } => {
232 if self.list_is_empty_value(left) {
233 current = right;
234 } else {
235 rights.push(right);
236 current = left;
237 }
238 }
239 ArenaList::Segments {
240 current: head_segment,
241 rest,
242 start,
243 ..
244 } => {
245 let (head, tail) = self.list_uncons(head_segment)?;
246 return Some((
247 head,
248 self.push_list_segments_rc(tail, Rc::clone(&rest), start),
249 ));
250 }
251 }
252 }
253 }
254
255 fn empty_list_value(&mut self) -> NanValue {
256 NanValue::EMPTY_LIST
257 }
258
259 fn push_list_segments(&mut self, current: NanValue, rest: Vec<NanValue>) -> NanValue {
260 let filtered: Vec<NanValue> = rest
261 .into_iter()
262 .filter(|part| !self.list_is_empty_value(*part))
263 .collect();
264 self.push_list_segments_rc(current, Rc::new(filtered), 0)
265 }
266
267 fn push_list_segments_rc(
268 &mut self,
269 mut current: NanValue,
270 rest: Rc<Vec<NanValue>>,
271 mut start: usize,
272 ) -> NanValue {
273 while self.list_is_empty_value(current) {
274 if let Some(next) = rest.get(start).copied() {
275 current = next;
276 start += 1;
277 } else {
278 return self.empty_list_value();
279 }
280 }
281
282 if start >= rest.len() {
283 return current;
284 }
285
286 let len = self.list_len_value(current)
287 + rest[start..]
288 .iter()
289 .map(|part| self.list_len_value(*part))
290 .sum::<usize>();
291 let idx = self.push(ArenaEntry::List(ArenaList::Segments {
292 current,
293 rest,
294 start,
295 len,
296 }));
297 NanValue::new_list(idx)
298 }
299}