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