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