1use fxhash::{FxBuildHasher, FxHashSet};
4
5use rquickjs::function::This;
6
7use rquickjs::{
8 atom::PredefinedAtom,
9 function::{Constructor, Opt},
10 Array, Ctx, Function, IntoJs, Null, Object, Result, Type, Value,
11};
12
13use super::object::ObjectExt;
14
15#[derive(Debug)]
16enum StackItem<'js> {
17 Value(usize, Value<'js>, Option<String>, Option<usize>),
18 ObjectEnd,
19}
20
21#[derive(Debug)]
22enum ObjectType {
23 Set,
24 Map,
25}
26
27#[derive(Debug)]
28enum TapeValue<'js> {
29 Array(Array<'js>),
30 Object(Object<'js>),
31 Value(Value<'js>),
32 Collection(Option<Value<'js>>, ObjectType),
33}
34
35#[derive(Debug)]
36struct TapeItem<'js> {
37 parent: usize,
38 object_key: Option<String>,
39 array_index: Option<usize>,
40 value: TapeValue<'js>,
41}
42
43pub fn structured_clone<'js>(
44 ctx: &Ctx<'js>,
45 value: Value<'js>,
46 options: Opt<Object<'js>>,
47) -> Result<Value<'js>> {
48 let globals = ctx.globals();
49 let date_ctor: Constructor = globals.get(PredefinedAtom::Date)?;
50 let map_ctor: Constructor = globals.get(PredefinedAtom::Map)?;
51 let set_ctor: Constructor = globals.get(PredefinedAtom::Set)?;
52 let reg_exp_ctor: Constructor = globals.get(PredefinedAtom::RegExp)?;
53 let error_ctor: Constructor = globals.get(PredefinedAtom::Error)?;
54 let array_ctor: Constructor = globals.get(PredefinedAtom::Array)?;
55 let array_from: Function = array_ctor.get(PredefinedAtom::From)?;
56 let array_buffer: Constructor = globals.get(PredefinedAtom::ArrayBuffer)?;
57 let is_view_fn: Function = array_buffer.get("isView")?;
58
59 let mut transfer_set = None;
60
61 if let Some(options) = options.0 {
62 if let Some(transfer_array) = options.get_optional::<_, Array>("transfer")? {
63 let mut set =
64 FxHashSet::with_capacity_and_hasher(transfer_array.len(), FxBuildHasher::default());
65
66 for item in transfer_array.iter::<Value>() {
67 set.insert(item?);
68 }
69 transfer_set = Some(set);
70 }
71 }
72
73 let mut tape = Vec::<TapeItem>::with_capacity(10);
74 let mut stack = Vec::with_capacity(10);
75 let mut visited = Vec::<(usize, usize)>::with_capacity(10);
76 let mut index = 0usize;
77
78 stack.push(StackItem::Value(0, value, None, None));
79
80 while let Some(item) = stack.pop() {
81 match item {
82 StackItem::Value(parent, value, mut object_key, array_index) => {
83 if let Some(set) = &transfer_set {
84 if let Some(value) = set.get(&value) {
85 append_transfer_value(&mut tape, value, parent, object_key, array_index)?;
86 index += 1;
87 continue;
88 }
89 }
90 match value.type_of() {
91 Type::Object => {
92 if check_circular(
93 &mut tape,
94 &mut visited,
95 &value,
96 parent,
97 &mut object_key,
98 array_index,
99 index,
100 ) {
101 index += 1;
102 continue;
103 }
104
105 let object = value.as_object().unwrap();
106
107 if object.is_instance_of(&date_ctor) {
108 append_ctor_value(
109 &mut tape,
110 object,
111 &date_ctor,
112 parent,
113 object_key,
114 array_index,
115 )?;
116 index += 1;
117 continue;
118 }
119
120 if object.is_instance_of(®_exp_ctor) {
121 append_ctor_value(
122 &mut tape,
123 object,
124 ®_exp_ctor,
125 parent,
126 object_key,
127 array_index,
128 )?;
129 index += 1;
130 continue;
131 }
132
133 let is_collection = if object.is_instance_of(&set_ctor) {
134 Some(ObjectType::Set)
135 } else if object.is_instance_of(&map_ctor) {
136 Some(ObjectType::Map)
137 } else {
138 None
139 };
140
141 if let Some(collection_type) = is_collection {
142 append_collection(
143 &mut tape,
144 &array_from,
145 object,
146 parent,
147 object_key,
148 array_index,
149 collection_type,
150 &mut stack,
151 index,
152 )?;
153
154 index += 1;
155 continue;
156 }
157
158 if is_view_fn.call::<_, bool>((value.clone(),))? {
159 append_buffer(&mut tape, object, parent, object_key, array_index)?;
160 index += 1;
161 continue;
162 }
163
164 let new: Object<'_> = if object.is_instance_of(&error_ctor) {
165 error_ctor.construct(("",))
166 } else {
167 Object::new(ctx.clone())
168 }?;
169
170 tape.push(TapeItem {
171 parent,
172 object_key,
173 array_index,
174 value: TapeValue::Object(new),
175 });
176 stack.push(StackItem::ObjectEnd);
177
178 for key in object.keys::<String>() {
179 let key = key?;
180 let value = object.get(&key)?;
181 stack.push(StackItem::Value(index, value, Some(key), None));
182 }
183 }
184 Type::Array => {
185 if check_circular(
186 &mut tape,
187 &mut visited,
188 &value,
189 parent,
190 &mut object_key,
191 array_index,
192 index,
193 ) {
194 index += 1;
195 continue;
196 }
197 let new = Array::new(ctx.clone())?;
198 tape.push(TapeItem {
199 parent,
200 object_key,
201 array_index,
202 value: TapeValue::Array(new),
203 });
204 stack.push(StackItem::ObjectEnd);
205 let array = value.as_array().unwrap();
206
207 for array_index in (0usize..array.len()).rev() {
209 stack.push(StackItem::Value(
210 index,
211 array.get(array_index)?,
212 None,
213 Some(array_index),
214 ));
215 }
216 }
217 _ => {
218 tape.push(TapeItem {
219 parent,
220 object_key,
221 array_index,
222 value: TapeValue::Value(value),
223 });
224 }
225 }
226 index += 1;
227 }
228 StackItem::ObjectEnd => {
229 visited.pop();
230 }
231 }
232 }
233
234 while let Some(item) = tape.pop() {
235 let value = match item.value {
236 TapeValue::Array(array) => array.into_value(),
237 TapeValue::Object(object) => object.into_value(),
238 TapeValue::Value(value) => value,
239 TapeValue::Collection(mut value, _) => value.take().unwrap(),
240 };
241 if tape.is_empty() {
242 return Ok(value);
243 }
244 let parent = &mut tape[item.parent];
245 let array_index = item.array_index;
246 let object_key = item.object_key;
247 match &mut parent.value {
248 TapeValue::Array(array) => {
249 array.set(array_index.unwrap(), value)?;
250 }
251 TapeValue::Object(object) => {
252 let string = object_key.unwrap();
253 object.set(string, value)?;
254 }
255 TapeValue::Collection(collection_value, collection_type) => {
256 match collection_type {
257 ObjectType::Set => {
258 collection_value.replace(set_ctor.construct((value,))?);
259 }
260 ObjectType::Map => {
261 collection_value.replace(map_ctor.construct((value,))?);
262 }
263 };
264 }
265 _ => {}
266 };
267 }
268
269 Null.into_js(ctx)
270}
271
272#[inline(always)]
273#[cold]
274fn append_buffer<'js>(
275 tape: &mut Vec<TapeItem<'js>>,
276 object: &Object<'js>,
277 parent: usize,
278 object_key: Option<String>,
279 array_index: Option<usize>,
280) -> Result<()> {
281 let ctor: Constructor = object.get(PredefinedAtom::Constructor)?;
282 let slice: Function = object.get("slice")?;
283 let clone: Value = slice.call((This(object.clone()),))?;
284 let new = ctor.construct((clone,))?;
285 tape.push(TapeItem {
286 parent,
287 object_key,
288 array_index,
289 value: TapeValue::Value(new),
290 });
291 Ok(())
292}
293
294#[inline(always)]
295#[cold]
296#[allow(clippy::too_many_arguments)]
297fn append_collection<'js>(
298 tape: &mut Vec<TapeItem<'js>>,
299 array_from: &Function<'js>,
300 object: &Object<'js>,
301 parent: usize,
302 object_key: Option<String>,
303 array_index: Option<usize>,
304 collection_type: ObjectType,
305 stack: &mut Vec<StackItem<'js>>,
306 index: usize,
307) -> Result<()> {
308 let array: Array = array_from.call((object.clone(),))?;
309 tape.push(TapeItem {
310 parent,
311 object_key,
312 array_index,
313 value: TapeValue::Collection(None, collection_type),
314 });
315 stack.push(StackItem::ObjectEnd);
316 stack.push(StackItem::Value(index, array.into(), None, None));
317 Ok(())
318}
319
320#[inline(always)]
321fn check_circular(
322 tape: &mut Vec<TapeItem>,
323 visited: &mut Vec<(usize, usize)>,
324 value: &Value<'_>,
325 parent: usize,
326 object_key: &mut Option<String>,
327 array_index: Option<usize>,
328 index: usize,
329) -> bool {
330 let hash = fxhash::hash(value);
331 if let Some(visited) = visited.iter().find(|v| v.0 == hash) {
332 append_circular(tape, visited, object_key, parent, array_index);
333 return true;
334 }
335 visited.push((hash, index));
336 false
337}
338
339#[inline(always)]
340#[cold]
341fn append_transfer_value<'js>(
342 tape: &mut Vec<TapeItem<'js>>,
343 value: &Value<'js>,
344 parent: usize,
345 object_key: Option<String>,
346 array_index: Option<usize>,
347) -> Result<()> {
348 tape.push(TapeItem {
349 parent,
350 object_key,
351 array_index,
352 value: TapeValue::Value(value.clone()),
353 });
354 Ok(())
355}
356
357#[inline(always)]
358#[cold]
359fn append_circular(
360 tape: &mut Vec<TapeItem<'_>>,
361 visited: &(usize, usize),
362 object_key: &mut Option<String>,
363 parent: usize,
364 array_index: Option<usize>,
365) {
366 let value = match &tape[visited.1].value {
367 TapeValue::Array(array) => array.clone().into_value(),
368 TapeValue::Object(object) => object.clone().into_value(),
369 TapeValue::Value(value) => value.clone(),
370 TapeValue::Collection(value, _) => value.clone().unwrap(),
371 };
372
373 let object_key = object_key.take();
374
375 tape.push(TapeItem {
376 parent,
377 object_key,
378 array_index,
379 value: TapeValue::Value(value),
380 });
381}
382
383#[inline(always)]
384#[cold]
385fn append_ctor_value<'js>(
386 tape: &mut Vec<TapeItem<'js>>,
387 object: &Object<'js>,
388 ctor: &Constructor<'js>,
389 parent: usize,
390 object_key: Option<String>,
391 array_index: Option<usize>,
392) -> Result<()> {
393 let clone: Value = ctor.construct((object.clone(),))?;
394 tape.push(TapeItem {
395 parent,
396 object_key,
397 array_index,
398 value: TapeValue::Value(clone),
399 });
400 Ok(())
401}
402
403