1package goja
2
3import (
4	"math"
5	"math/bits"
6	"reflect"
7	"sort"
8	"strconv"
9
10	"github.com/dop251/goja/unistring"
11)
12
13type sparseArrayItem struct {
14	idx   uint32
15	value Value
16}
17
18type sparseArrayObject struct {
19	baseObject
20	items          []sparseArrayItem
21	length         uint32
22	propValueCount int
23	lengthProp     valueProperty
24}
25
26func (a *sparseArrayObject) findIdx(idx uint32) int {
27	return sort.Search(len(a.items), func(i int) bool {
28		return a.items[i].idx >= idx
29	})
30}
31
32func (a *sparseArrayObject) _setLengthInt(l int64, throw bool) bool {
33	if l >= 0 && l <= math.MaxUint32 {
34		ret := true
35		l := uint32(l)
36		if l <= a.length {
37			if a.propValueCount > 0 {
38				// Slow path
39				for i := len(a.items) - 1; i >= 0; i-- {
40					item := a.items[i]
41					if item.idx <= l {
42						break
43					}
44					if prop, ok := item.value.(*valueProperty); ok {
45						if !prop.configurable {
46							l = item.idx + 1
47							ret = false
48							break
49						}
50						a.propValueCount--
51					}
52				}
53			}
54		}
55
56		idx := a.findIdx(l)
57
58		aa := a.items[idx:]
59		for i := range aa {
60			aa[i].value = nil
61		}
62		a.items = a.items[:idx]
63		a.length = l
64		if !ret {
65			a.val.runtime.typeErrorResult(throw, "Cannot redefine property: length")
66		}
67		return ret
68	}
69	panic(a.val.runtime.newError(a.val.runtime.global.RangeError, "Invalid array length"))
70}
71
72func (a *sparseArrayObject) setLengthInt(l int64, throw bool) bool {
73	if l == int64(a.length) {
74		return true
75	}
76	if !a.lengthProp.writable {
77		a.val.runtime.typeErrorResult(throw, "length is not writable")
78		return false
79	}
80	return a._setLengthInt(l, throw)
81}
82
83func (a *sparseArrayObject) setLength(v Value, throw bool) bool {
84	l, ok := toIntIgnoreNegZero(v)
85	if ok && l == int64(a.length) {
86		return true
87	}
88	if !a.lengthProp.writable {
89		a.val.runtime.typeErrorResult(throw, "length is not writable")
90		return false
91	}
92	if ok {
93		return a._setLengthInt(l, throw)
94	}
95	panic(a.val.runtime.newError(a.val.runtime.global.RangeError, "Invalid array length"))
96}
97
98func (a *sparseArrayObject) _getIdx(idx uint32) Value {
99	i := a.findIdx(idx)
100	if i < len(a.items) && a.items[i].idx == idx {
101		return a.items[i].value
102	}
103
104	return nil
105}
106
107func (a *sparseArrayObject) getStr(name unistring.String, receiver Value) Value {
108	return a.getStrWithOwnProp(a.getOwnPropStr(name), name, receiver)
109}
110
111func (a *sparseArrayObject) getIdx(idx valueInt, receiver Value) Value {
112	prop := a.getOwnPropIdx(idx)
113	if prop == nil {
114		if a.prototype != nil {
115			if receiver == nil {
116				return a.prototype.self.getIdx(idx, a.val)
117			}
118			return a.prototype.self.getIdx(idx, receiver)
119		}
120	}
121	if prop, ok := prop.(*valueProperty); ok {
122		if receiver == nil {
123			return prop.get(a.val)
124		}
125		return prop.get(receiver)
126	}
127	return prop
128}
129
130func (a *sparseArrayObject) getLengthProp() Value {
131	a.lengthProp.value = intToValue(int64(a.length))
132	return &a.lengthProp
133}
134
135func (a *sparseArrayObject) getOwnPropStr(name unistring.String) Value {
136	if idx := strToArrayIdx(name); idx != math.MaxUint32 {
137		return a._getIdx(idx)
138	}
139	if name == "length" {
140		return a.getLengthProp()
141	}
142	return a.baseObject.getOwnPropStr(name)
143}
144
145func (a *sparseArrayObject) getOwnPropIdx(idx valueInt) Value {
146	if idx := toIdx(idx); idx != math.MaxUint32 {
147		return a._getIdx(idx)
148	}
149	return a.baseObject.getOwnPropStr(idx.string())
150}
151
152func (a *sparseArrayObject) add(idx uint32, val Value) {
153	i := a.findIdx(idx)
154	a.items = append(a.items, sparseArrayItem{})
155	copy(a.items[i+1:], a.items[i:])
156	a.items[i] = sparseArrayItem{
157		idx:   idx,
158		value: val,
159	}
160}
161
162func (a *sparseArrayObject) _setOwnIdx(idx uint32, val Value, throw bool) bool {
163	var prop Value
164	i := a.findIdx(idx)
165	if i < len(a.items) && a.items[i].idx == idx {
166		prop = a.items[i].value
167	}
168
169	if prop == nil {
170		if proto := a.prototype; proto != nil {
171			// we know it's foreign because prototype loops are not allowed
172			if res, ok := proto.self.setForeignIdx(valueInt(idx), val, a.val, throw); ok {
173				return res
174			}
175		}
176
177		// new property
178		if !a.extensible {
179			a.val.runtime.typeErrorResult(throw, "Cannot add property %d, object is not extensible", idx)
180			return false
181		}
182
183		if idx >= a.length {
184			if !a.setLengthInt(int64(idx)+1, throw) {
185				return false
186			}
187		}
188
189		if a.expand(idx) {
190			a.items = append(a.items, sparseArrayItem{})
191			copy(a.items[i+1:], a.items[i:])
192			a.items[i] = sparseArrayItem{
193				idx:   idx,
194				value: val,
195			}
196		} else {
197			ar := a.val.self.(*arrayObject)
198			ar.values[idx] = val
199			ar.objCount++
200			return true
201		}
202	} else {
203		if prop, ok := prop.(*valueProperty); ok {
204			if !prop.isWritable() {
205				a.val.runtime.typeErrorResult(throw)
206				return false
207			}
208			prop.set(a.val, val)
209		} else {
210			a.items[i].value = val
211		}
212	}
213	return true
214}
215
216func (a *sparseArrayObject) setOwnStr(name unistring.String, val Value, throw bool) bool {
217	if idx := strToArrayIdx(name); idx != math.MaxUint32 {
218		return a._setOwnIdx(idx, val, throw)
219	} else {
220		if name == "length" {
221			return a.setLength(val, throw)
222		} else {
223			return a.baseObject.setOwnStr(name, val, throw)
224		}
225	}
226}
227
228func (a *sparseArrayObject) setOwnIdx(idx valueInt, val Value, throw bool) bool {
229	if idx := toIdx(idx); idx != math.MaxUint32 {
230		return a._setOwnIdx(idx, val, throw)
231	}
232
233	return a.baseObject.setOwnStr(idx.string(), val, throw)
234}
235
236func (a *sparseArrayObject) setForeignStr(name unistring.String, val, receiver Value, throw bool) (bool, bool) {
237	return a._setForeignStr(name, a.getOwnPropStr(name), val, receiver, throw)
238}
239
240func (a *sparseArrayObject) setForeignIdx(name valueInt, val, receiver Value, throw bool) (bool, bool) {
241	return a._setForeignIdx(name, a.getOwnPropIdx(name), val, receiver, throw)
242}
243
244type sparseArrayPropIter struct {
245	a   *sparseArrayObject
246	idx int
247}
248
249func (i *sparseArrayPropIter) next() (propIterItem, iterNextFunc) {
250	for i.idx < len(i.a.items) {
251		name := unistring.String(strconv.Itoa(int(i.a.items[i.idx].idx)))
252		prop := i.a.items[i.idx].value
253		i.idx++
254		if prop != nil {
255			return propIterItem{name: name, value: prop}, i.next
256		}
257	}
258
259	return i.a.baseObject.enumerateOwnKeys()()
260}
261
262func (a *sparseArrayObject) enumerateOwnKeys() iterNextFunc {
263	return (&sparseArrayPropIter{
264		a: a,
265	}).next
266}
267
268func (a *sparseArrayObject) ownKeys(all bool, accum []Value) []Value {
269	if all {
270		for _, item := range a.items {
271			accum = append(accum, asciiString(strconv.FormatUint(uint64(item.idx), 10)))
272		}
273	} else {
274		for _, item := range a.items {
275			if prop, ok := item.value.(*valueProperty); ok && !prop.enumerable {
276				continue
277			}
278			accum = append(accum, asciiString(strconv.FormatUint(uint64(item.idx), 10)))
279		}
280	}
281
282	return a.baseObject.ownKeys(all, accum)
283}
284
285func (a *sparseArrayObject) setValues(values []Value, objCount int) {
286	a.items = make([]sparseArrayItem, 0, objCount)
287	for i, val := range values {
288		if val != nil {
289			a.items = append(a.items, sparseArrayItem{
290				idx:   uint32(i),
291				value: val,
292			})
293		}
294	}
295}
296
297func (a *sparseArrayObject) hasOwnPropertyStr(name unistring.String) bool {
298	if idx := strToArrayIdx(name); idx != math.MaxUint32 {
299		i := a.findIdx(idx)
300		return i < len(a.items) && a.items[i].idx == idx
301	} else {
302		return a.baseObject.hasOwnPropertyStr(name)
303	}
304}
305
306func (a *sparseArrayObject) hasOwnPropertyIdx(idx valueInt) bool {
307	if idx := toIdx(idx); idx != math.MaxUint32 {
308		i := a.findIdx(idx)
309		return i < len(a.items) && a.items[i].idx == idx
310	}
311
312	return a.baseObject.hasOwnPropertyStr(idx.string())
313}
314
315func (a *sparseArrayObject) expand(idx uint32) bool {
316	if l := len(a.items); l >= 1024 {
317		if ii := a.items[l-1].idx; ii > idx {
318			idx = ii
319		}
320		if (bits.UintSize == 64 || idx < math.MaxInt32) && int(idx)>>3 < l {
321			//log.Println("Switching sparse->standard")
322			ar := &arrayObject{
323				baseObject:     a.baseObject,
324				length:         a.length,
325				propValueCount: a.propValueCount,
326			}
327			ar.setValuesFromSparse(a.items, int(idx))
328			ar.val.self = ar
329			ar.lengthProp.writable = a.lengthProp.writable
330			a._put("length", &ar.lengthProp)
331			return false
332		}
333	}
334	return true
335}
336
337func (a *sparseArrayObject) _defineIdxProperty(idx uint32, desc PropertyDescriptor, throw bool) bool {
338	var existing Value
339	i := a.findIdx(idx)
340	if i < len(a.items) && a.items[i].idx == idx {
341		existing = a.items[i].value
342	}
343	prop, ok := a.baseObject._defineOwnProperty(unistring.String(strconv.FormatUint(uint64(idx), 10)), existing, desc, throw)
344	if ok {
345		if idx >= a.length {
346			if !a.setLengthInt(int64(idx)+1, throw) {
347				return false
348			}
349		}
350		if i >= len(a.items) || a.items[i].idx != idx {
351			if a.expand(idx) {
352				a.items = append(a.items, sparseArrayItem{})
353				copy(a.items[i+1:], a.items[i:])
354				a.items[i] = sparseArrayItem{
355					idx:   idx,
356					value: prop,
357				}
358				if idx >= a.length {
359					a.length = idx + 1
360				}
361			} else {
362				a.val.self.(*arrayObject).values[idx] = prop
363			}
364		} else {
365			a.items[i].value = prop
366		}
367		if _, ok := prop.(*valueProperty); ok {
368			a.propValueCount++
369		}
370	}
371	return ok
372}
373
374func (a *sparseArrayObject) defineOwnPropertyStr(name unistring.String, descr PropertyDescriptor, throw bool) bool {
375	if idx := strToArrayIdx(name); idx != math.MaxUint32 {
376		return a._defineIdxProperty(idx, descr, throw)
377	}
378	if name == "length" {
379		return a.val.runtime.defineArrayLength(&a.lengthProp, descr, a.setLength, throw)
380	}
381	return a.baseObject.defineOwnPropertyStr(name, descr, throw)
382}
383
384func (a *sparseArrayObject) defineOwnPropertyIdx(idx valueInt, descr PropertyDescriptor, throw bool) bool {
385	if idx := toIdx(idx); idx != math.MaxUint32 {
386		return a._defineIdxProperty(idx, descr, throw)
387	}
388	return a.baseObject.defineOwnPropertyStr(idx.string(), descr, throw)
389}
390
391func (a *sparseArrayObject) _deleteIdxProp(idx uint32, throw bool) bool {
392	i := a.findIdx(idx)
393	if i < len(a.items) && a.items[i].idx == idx {
394		if p, ok := a.items[i].value.(*valueProperty); ok {
395			if !p.configurable {
396				a.val.runtime.typeErrorResult(throw, "Cannot delete property '%d' of %s", idx, a.val.toString())
397				return false
398			}
399			a.propValueCount--
400		}
401		copy(a.items[i:], a.items[i+1:])
402		a.items[len(a.items)-1].value = nil
403		a.items = a.items[:len(a.items)-1]
404	}
405	return true
406}
407
408func (a *sparseArrayObject) deleteStr(name unistring.String, throw bool) bool {
409	if idx := strToArrayIdx(name); idx != math.MaxUint32 {
410		return a._deleteIdxProp(idx, throw)
411	}
412	return a.baseObject.deleteStr(name, throw)
413}
414
415func (a *sparseArrayObject) deleteIdx(idx valueInt, throw bool) bool {
416	if idx := toIdx(idx); idx != math.MaxUint32 {
417		return a._deleteIdxProp(idx, throw)
418	}
419	return a.baseObject.deleteStr(idx.string(), throw)
420}
421
422func (a *sparseArrayObject) sortLen() int64 {
423	if len(a.items) > 0 {
424		return int64(a.items[len(a.items)-1].idx) + 1
425	}
426
427	return 0
428}
429
430func (a *sparseArrayObject) export(ctx *objectExportCtx) interface{} {
431	if v, exists := ctx.get(a); exists {
432		return v
433	}
434	arr := make([]interface{}, a.length)
435	ctx.put(a, arr)
436	var prevIdx uint32
437	for _, item := range a.items {
438		idx := item.idx
439		for i := prevIdx; i < idx; i++ {
440			if a.prototype != nil {
441				if v := a.prototype.self.getIdx(valueInt(i), nil); v != nil {
442					arr[i] = exportValue(v, ctx)
443				}
444			}
445		}
446		v := item.value
447		if v != nil {
448			if prop, ok := v.(*valueProperty); ok {
449				v = prop.get(a.val)
450			}
451			arr[idx] = exportValue(v, ctx)
452		}
453		prevIdx = idx + 1
454	}
455	for i := prevIdx; i < a.length; i++ {
456		if a.prototype != nil {
457			if v := a.prototype.self.getIdx(valueInt(i), nil); v != nil {
458				arr[i] = exportValue(v, ctx)
459			}
460		}
461	}
462	return arr
463}
464
465func (a *sparseArrayObject) exportType() reflect.Type {
466	return reflectTypeArray
467}
468