1 /*
2 $Id: dictobj.c 2593 2021-04-18 13:00:11Z soci $
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17
18 */
19 #include "dictobj.h"
20 #include <string.h>
21 #include "eval.h"
22 #include "error.h"
23 #include "variables.h"
24
25 #include "intobj.h"
26 #include "listobj.h"
27 #include "strobj.h"
28 #include "boolobj.h"
29 #include "typeobj.h"
30 #include "noneobj.h"
31 #include "errorobj.h"
32 #include "symbolobj.h"
33
34 static Type obj;
35
36 Type *const DICT_OBJ = &obj;
37
new_dict(size_t ln)38 static Dict *new_dict(size_t ln) {
39 size_t ln1, ln2, ln3;
40 Dict *v;
41 struct pair_s *p;
42 if (ln > lenof(v->u.val)) {
43 if (ln > SIZE_MAX / (sizeof(struct pair_s) + sizeof(size_t) * 2)) return NULL; /* overflow */
44 ln1 = ln * 3 / 2;
45 ln2 = 8; while (ln1 > ln2) ln2 <<= 1;
46 ln3 = ln2 * ((ln2 <= (1 << (sizeof(uint8_t)*8))) ? sizeof(uint8_t) : sizeof(size_t));
47 p = (struct pair_s *)malloc(ln * sizeof(struct pair_s) + ln3);
48 if (p == NULL) return NULL; /* out of memory */
49 memset(&p[ln], 255, ln3);
50 } else {
51 p = NULL;
52 ln2 = 1;
53 }
54 v = Dict(val_alloc(DICT_OBJ));
55 if (p == NULL) {
56 v->data = v->u.val;
57 } else {
58 v->data = p;
59 v->u.s.hash = -1;
60 v->u.s.max = ln;
61 v->u.s.mask = ln2 - 1;
62 }
63 v->len = 0;
64 return v;
65 }
66
destroy(Obj * o1)67 static FAST_CALL void destroy(Obj *o1) {
68 Dict *v1 = Dict(o1);
69 size_t i;
70 for (i = 0; i < v1->len; i++) {
71 struct pair_s *a = &v1->data[i];
72 val_destroy(a->key);
73 if (a->data != NULL) val_destroy(a->data);
74 }
75 if (v1->u.val != v1->data) free(v1->data);
76 if (v1->def != NULL) val_destroy(v1->def);
77 }
78
garbage(Obj * o1,int j)79 static FAST_CALL void garbage(Obj *o1, int j) {
80 Dict *v1 = Dict(o1);
81 Obj *v;
82 size_t i;
83 switch (j) {
84 case -1:
85 for (i = 0; i < v1->len; i++) {
86 struct pair_s *a = &v1->data[i];
87 a->key->refcount--;
88 if (a->data != NULL) a->data->refcount--;
89 }
90 v = v1->def;
91 if (v != NULL) v->refcount--;
92 return;
93 case 0:
94 if (v1->u.val != v1->data) free(v1->data);
95 return;
96 case 1:
97 for (i = 0; i < v1->len; i++) {
98 struct pair_s *a = &v1->data[i];
99 v = a->data;
100 if (v != NULL) {
101 if ((v->refcount & SIZE_MSB) != 0) {
102 v->refcount -= SIZE_MSB - 1;
103 v->obj->garbage(v, 1);
104 } else v->refcount++;
105 }
106 v = a->key;
107 if ((v->refcount & SIZE_MSB) != 0) {
108 v->refcount -= SIZE_MSB - 1;
109 v->obj->garbage(v, 1);
110 } else v->refcount++;
111 }
112 v = v1->def;
113 if (v == NULL) return;
114 if ((v->refcount & SIZE_MSB) != 0) {
115 v->refcount -= SIZE_MSB - 1;
116 v->obj->garbage(v, 1);
117 } else v->refcount++;
118 return;
119 }
120 }
121
pair_same(const struct pair_s * a,const struct pair_s * b)122 static bool pair_same(const struct pair_s *a, const struct pair_s *b)
123 {
124 if (a->hash != b->hash || a->key->obj != b->key->obj) return false;
125 if (a->key->obj->type == T_SYMBOL) return symbol_cfsame(Symbol(a->key), Symbol(b->key));
126 return a->key->obj->same(a->key, b->key);
127 }
128
dict_update(Dict * dict,const struct pair_s * p)129 static void dict_update(Dict *dict, const struct pair_s *p) {
130 struct pair_s *d;
131 if (dict->u.val == dict->data) {
132 /* nothing */
133 } else if (dict->u.s.mask < (1 << (sizeof(uint8_t)*8))) {
134 size_t mask = dict->u.s.mask;
135 size_t hash = (size_t)p->hash;
136 size_t offs = hash & mask;
137 uint8_t *indexes = (uint8_t *)&dict->data[dict->u.s.max];
138 while (indexes[offs] != (uint8_t)~0) {
139 d = &dict->data[indexes[offs]];
140 if (p->key == d->key || pair_same(p, d)) {
141 if (d->data != NULL) val_destroy(d->data);
142 d->data = (p->data == NULL) ? NULL : val_reference(p->data);
143 return;
144 }
145 hash >>= 5;
146 offs = (5 * offs + hash + 1) & mask;
147 }
148 indexes[offs] = (uint8_t)dict->len;
149 } else {
150 size_t mask = dict->u.s.mask;
151 size_t hash = (size_t)p->hash;
152 size_t offs = hash & mask;
153 size_t *indexes = (size_t *)&dict->data[dict->u.s.max];
154 while (indexes[offs] != SIZE_MAX) {
155 d = &dict->data[indexes[offs]];
156 if (p->key == d->key || pair_same(p, d)) {
157 if (d->data != NULL) val_destroy(d->data);
158 d->data = (p->data == NULL) ? NULL : val_reference(p->data);
159 return;
160 }
161 hash >>= 5;
162 offs = (5 * offs + hash + 1) & mask;
163 }
164 indexes[offs] = dict->len;
165 }
166 d = &dict->data[dict->len];
167 d->hash = p->hash;
168 d->key = val_reference(p->key);
169 d->data = (p->data == NULL) ? NULL : val_reference(p->data);
170 dict->len++;
171 }
172
dict_lookup(const Dict * dict,const struct pair_s * p)173 static const struct pair_s *dict_lookup(const Dict *dict, const struct pair_s *p) {
174 struct pair_s *d;
175 if (dict->u.val == dict->data) {
176 d = &dict->data[0];
177 if (p->key == d->key || pair_same(p, d)) return d;
178 } else if (dict->u.s.mask < (1 << (sizeof(uint8_t)*8))) {
179 size_t mask = dict->u.s.mask;
180 size_t hash = (size_t)p->hash;
181 size_t offs = hash & mask;
182 uint8_t *indexes = (uint8_t *)&dict->data[dict->u.s.max];
183 while (indexes[offs] != (uint8_t)~0) {
184 d = &dict->data[indexes[offs]];
185 if (p->key == d->key || pair_same(p, d)) return d;
186 hash >>= 5;
187 offs = (5 * offs + hash + 1) & mask;
188 }
189 } else {
190 size_t mask = dict->u.s.mask;
191 size_t hash = (size_t)p->hash;
192 size_t offs = hash & mask;
193 size_t *indexes = (size_t *)&dict->data[dict->u.s.max];
194 while (indexes[offs] != SIZE_MAX) {
195 d = &dict->data[indexes[offs]];
196 if (p->key == d->key || pair_same(p, d)) return d;
197 hash >>= 5;
198 offs = (5 * offs + hash + 1) & mask;
199 }
200 }
201 return NULL;
202 }
203
reindex(Dict * dict)204 static void reindex(Dict *dict) {
205 if (dict->u.val == dict->data) {
206 return;
207 } else if (dict->u.s.mask < (1 << (sizeof(uint8_t)*8))) {
208 unsigned int i;
209 size_t mask = dict->u.s.mask;
210 uint8_t *indexes = (uint8_t *)&dict->data[dict->u.s.max];
211 for (i = 0; i < dict->len; i++) {
212 size_t hash = (size_t)dict->data[i].hash;
213 size_t offs = hash & mask;
214 while (indexes[offs] != (uint8_t)~0) {
215 hash >>= 5;
216 offs = (5 * offs + hash + 1) & mask;
217 }
218 indexes[offs] = (uint8_t)i;
219 }
220 } else {
221 size_t i;
222 size_t mask = dict->u.s.mask;
223 size_t *indexes = (size_t *)&dict->data[dict->u.s.max];
224 for (i = 0; i < dict->len; i++) {
225 size_t hash = (size_t)dict->data[i].hash;
226 size_t offs = hash & mask;
227 while (indexes[offs] != SIZE_MAX) {
228 hash >>= 5;
229 offs = (5 * offs + hash + 1) & mask;
230 }
231 indexes[offs] = i;
232 }
233 }
234 }
235
resize(Dict * dict,size_t ln)236 static bool resize(Dict *dict, size_t ln) {
237 struct pair_s *p;
238 size_t ln2 = 8, ln3;
239 size_t ln1 = ln * 3 / 2;
240 while (ln1 > ln2) ln2 <<= 1;
241 ln3 = ln2 * ((ln2 <= (1 << (sizeof(uint8_t)*8))) ? sizeof(uint8_t) : sizeof(size_t));
242 if (dict->u.val == dict->data) {
243 p = (struct pair_s *)malloc(ln * sizeof *dict->data + ln3);
244 if (p == NULL) return true;
245 if (dict->len != 0) p[0] = dict->u.val[0];
246 dict->u.s.hash = -1;
247 dict->u.s.mask = 0;
248 } else {
249 bool same = dict->u.s.mask == ln2 - 1;
250 if (same && dict->u.s.max > ln) {
251 memmove(&dict->data[ln], &dict->data[dict->u.s.max], ln3);
252 dict->u.s.max = ln;
253 }
254 p = (struct pair_s *)realloc(dict->data, ln * sizeof *dict->data + ln3);
255 if (p == NULL) return true;
256 if (same) {
257 if (dict->u.s.max < ln) {
258 memmove(&p[ln], &p[dict->u.s.max], ln3);
259 dict->u.s.max = ln;
260 }
261 dict->data = p;
262 return false;
263 }
264 }
265 dict->data = p;
266 dict->u.s.max = ln;
267 dict->u.s.mask = ln2 - 1;
268 memset(&p[ln], 255, ln3);
269 reindex(dict);
270 return false;
271 }
272
normalize(Dict * dict)273 static MUST_CHECK Obj *normalize(Dict *dict) {
274 if (dict->u.val == dict->data || dict->u.s.max - dict->len < 2) return Obj(dict);
275 resize(dict, dict->len);
276 return Obj(dict);
277 }
278
same(const Obj * o1,const Obj * o2)279 static FAST_CALL bool same(const Obj *o1, const Obj *o2) {
280 const Dict *v1 = Dict(o1), *v2 = Dict(o2);
281 size_t n;
282 if (o1->obj != o2->obj || v1->len != v2->len) return false;
283 if (v1->def != v2->def) {
284 if (v1->def == NULL || v2->def == NULL) return false;
285 if (!v1->def->obj->same(v1->def, v2->def)) return false;
286 }
287 for (n = 0; n < v1->len; n++) {
288 const struct pair_s *p = &v1->data[n];
289 const struct pair_s *p2 = &v2->data[n];
290 if (p->key != p2->key && !p->key->obj->same(p->key, p2->key)) return false;
291 if (p->data == p2->data) continue;
292 if (p->data == NULL || p2->data == NULL) return false;
293 if (!p->data->obj->same(p->data, p2->data)) return false;
294 }
295 return true;
296 }
297
hash(Obj * o1,int * hs,linepos_t epoint)298 static MUST_CHECK Obj *hash(Obj *o1, int *hs, linepos_t epoint) {
299 Dict *v1 = Dict(o1);
300 size_t i, l = v1->len;
301 struct pair_s *vals = v1->data;
302 unsigned int h;
303 if (vals != v1->u.val && v1->u.s.hash >= 0) {
304 *hs = v1->u.s.hash;
305 return NULL;
306 }
307 h = 0;
308 for (i = 0; i < l; i++) {
309 Obj *o2 = vals[i].data;
310 if (o2 != NULL) {
311 int h2;
312 Obj *err = o2->obj->hash(o2, &h2, epoint);
313 if (err != NULL) return err;
314 h += (unsigned int)h2;
315 }
316 h += (unsigned int)vals[i].hash;
317 }
318 if (v1->def != NULL) {
319 Obj *o2 = v1->def;
320 int h2;
321 Obj *err = o2->obj->hash(o2, &h2, epoint);
322 if (err != NULL) return err;
323 h += (unsigned int)h2;
324 }
325 h ^= (unsigned int)i;
326 h &= ((~0U) >> 1);
327 if (vals != v1->u.val) v1->u.s.hash = (int)h;
328 *hs = (int)h;
329 return NULL;
330 }
331
len(oper_t op)332 static MUST_CHECK Obj *len(oper_t op) {
333 Dict *v1 = Dict(op->v2);
334 return int_from_size(v1->len);
335 }
336
iter_element(struct iter_s * v1,size_t i)337 static FAST_CALL MUST_CHECK Obj *iter_element(struct iter_s *v1, size_t i) {
338 Colonlist *iter;
339 const struct pair_s *p = &Dict(v1->data)->data[i];
340 if (p->data == NULL) {
341 return p->key;
342 }
343 iter = Colonlist(v1->iter);
344 if (iter->v.refcount != 1) {
345 iter->v.refcount--;
346 iter = new_colonlist();
347 v1->iter = Obj(iter);
348 iter->data = iter->u.val;
349 iter->len = 2;
350 } else {
351 val_destroy(iter->data[0]);
352 val_destroy(iter->data[1]);
353 }
354 iter->data[0] = val_reference(p->key);
355 iter->data[1] = val_reference(p->data);
356 return Obj(iter);
357 }
358
iter_forward(struct iter_s * v1)359 static FAST_CALL MUST_CHECK Obj *iter_forward(struct iter_s *v1) {
360 if (v1->val >= v1->len) return NULL;
361 return iter_element(v1, v1->val++);
362 }
363
getiter(struct iter_s * v)364 static void getiter(struct iter_s *v) {
365 v->iter = val_reference(v->data);
366 v->val = 0;
367 v->data = val_reference(v->data);
368 v->next = iter_forward;
369 v->len = Dict(v->data)->len;
370 }
371
iter_reverse(struct iter_s * v1)372 static FAST_CALL MUST_CHECK Obj *iter_reverse(struct iter_s *v1) {
373 if (v1->val >= v1->len) return NULL;
374 return iter_element(v1, v1->len - ++v1->val);
375 }
376
getriter(struct iter_s * v)377 static void getriter(struct iter_s *v) {
378 v->iter = val_reference(v->data);
379 v->val = 0;
380 v->data = val_reference(v->data);
381 v->next = iter_reverse;
382 v->len = Dict(v->data)->len;
383 }
384
repr(Obj * o1,linepos_t epoint,size_t maxsize)385 static MUST_CHECK Obj *repr(Obj *o1, linepos_t epoint, size_t maxsize) {
386 Dict *v1 = Dict(o1);
387 const struct pair_s *p;
388 size_t i = 0, j, ln = 2, chars = 2;
389 Tuple *list = NULL;
390 Obj **vals;
391 Obj *v;
392 Str *str;
393 uint8_t *s;
394 size_t def = (v1->def != NULL) ? 1 : 0;
395 if (v1->len != 0 || def != 0) {
396 ln = v1->len * 2;
397 if (ln < v1->len) return NULL; /* overflow */
398 ln += def;
399 if (ln < def) return NULL; /* overflow */
400 chars = ln + 1 + def;
401 if (chars < ln) return NULL; /* overflow */
402 if (chars > maxsize) return NULL;
403 list = new_tuple(ln);
404 vals = list->data;
405 ln = chars;
406 if (v1->len != 0) {
407 size_t n;
408 for (n = 0; n < v1->len; n++) {
409 p = &v1->data[n];
410 v = p->key->obj->repr(p->key, epoint, maxsize - chars);
411 if (v == NULL || v->obj != STR_OBJ) goto error;
412 str = Str(v);
413 ln += str->len;
414 if (ln < str->len) goto error2; /* overflow */
415 chars += str->chars;
416 if (chars > maxsize) goto error2;
417 vals[i++] = v;
418 if (p->data != NULL) {
419 v = p->data->obj->repr(p->data, epoint, maxsize - chars);
420 if (v == NULL || v->obj != STR_OBJ) goto error;
421 str = Str(v);
422 ln += str->len;
423 if (ln < str->len) goto error2; /* overflow */
424 chars += str->chars;
425 if (chars > maxsize) goto error2;
426 } else {
427 v = ref_none();
428 ln--;
429 chars--;
430 }
431 vals[i++] = v;
432 }
433 }
434 if (def != 0) {
435 v = v1->def->obj->repr(v1->def, epoint, maxsize - chars);
436 if (v == NULL || v->obj != STR_OBJ) goto error;
437 str = Str(v);
438 ln += str->len;
439 if (ln < str->len) goto error2; /* overflow */
440 chars += str->chars;
441 if (chars > maxsize) {
442 error2:
443 val_destroy(v);
444 v = NULL;
445 error:
446 list->len = i;
447 val_destroy(Obj(list));
448 return v;
449 }
450 vals[i] = v;
451 }
452 list->len = i + def;
453 }
454 str = new_str2(ln);
455 if (str == NULL) {
456 if (list != NULL) val_destroy(Obj(list));
457 return NULL;
458 }
459 str->chars = chars;
460 s = str->data;
461 *s++ = '{';
462 for (j = 0; j < i; j++) {
463 Str *str2 = Str(vals[j]);
464 if (str2->v.obj != STR_OBJ) continue;
465 if (j != 0) *s++ = ((j & 1) != 0) ? ':' : ',';
466 if (str2->len != 0) {
467 memcpy(s, str2->data, str2->len);
468 s += str2->len;
469 }
470 }
471 if (def != 0) {
472 Str *str2 = Str(vals[j]);
473 if (j != 0) *s++ = ',';
474 *s++ = ':';
475 if (str2->len != 0) {
476 memcpy(s, str2->data, str2->len);
477 s += str2->len;
478 }
479 }
480 *s = '}';
481 if (list != NULL) val_destroy(Obj(list));
482 return Obj(str);
483 }
484
findit(const Dict * v1,Obj * o2,linepos_t epoint)485 static MUST_CHECK Obj *findit(const Dict *v1, Obj *o2, linepos_t epoint) {
486 if (v1->len != 0) {
487 Obj *err;
488 const struct pair_s *p;
489 struct pair_s pair;
490 pair.key = o2;
491 err = o2->obj->hash(o2, &pair.hash, epoint);
492 if (err != NULL) return err;
493 p = dict_lookup(v1, &pair);
494 if (p != NULL && p->data != NULL) return val_reference(p->data);
495 }
496 if (v1->def != NULL) {
497 return val_reference(v1->def);
498 }
499 return new_error_obj(ERROR_____KEY_ERROR, o2, epoint);
500 }
501
indexof(const Dict * v1,Obj * o2,ival_t * r,linepos_t epoint)502 static MUST_CHECK Obj *indexof(const Dict *v1, Obj *o2, ival_t *r, linepos_t epoint) {
503 if (v1->len != 0) {
504 Obj *err;
505 const struct pair_s *p;
506 struct pair_s pair;
507 pair.key = o2;
508 err = o2->obj->hash(o2, &pair.hash, epoint);
509 if (err != NULL) return err;
510 p = dict_lookup(v1, &pair);
511 if (p != NULL) {
512 size_t i = (size_t)(p - v1->data);
513 if (i <= ~(uval_t)0 >> 1) {
514 *r = (ival_t)i;
515 return NULL;
516 }
517 }
518 }
519 return new_error_obj(ERROR_____KEY_ERROR, o2, epoint);
520 }
521
dictsliceparams(const Dict * v1,const Colonlist * v2,struct sliceparam_s * s,linepos_t epoint)522 static MUST_CHECK Obj *dictsliceparams(const Dict *v1, const Colonlist *v2, struct sliceparam_s *s, linepos_t epoint) {
523 Obj *err;
524 ival_t len, offs, end, step = 1;
525
526 s->length = 0;
527 if (v1->len >= (1U << (8 * sizeof(ival_t) - 1))) return new_error_mem(epoint); /* overflow */
528 len = (ival_t)v1->len;
529 if (v2->len > 3 || v2->len < 1) {
530 return new_error_argnum(v2->len <= ~(argcount_t)0 ? (argcount_t)v2->len : ~(argcount_t)0, 1, 3, epoint);
531 }
532 end = len;
533 if (v2->len > 2) {
534 if (v2->data[2] != default_value) {
535 err = Obj(v2->data[2]->obj->ival(v2->data[2], &step, 8 * sizeof step, epoint));
536 if (err != NULL) return err;
537 if (step == 0) {
538 return Obj(new_error(ERROR_NO_ZERO_VALUE, epoint));
539 }
540 }
541 }
542 if (v2->len > 1) {
543 if (v2->data[1] == default_value) end = (step > 0) ? len : -1;
544 else {
545 err = indexof(v1, v2->data[1], &end, epoint);
546 if (err != NULL) return err;
547 }
548 } else end = len;
549 if (v2->data[0] == default_value) offs = (step > 0) ? 0 : len - 1;
550 else {
551 err = indexof(v1, v2->data[0], &offs, epoint);
552 if (err != NULL) return err;
553 }
554
555 if (step > 0) {
556 if (offs > end) offs = end;
557 s->length = (uval_t)(end - offs + step - 1) / (uval_t)step;
558 } else {
559 if (end > offs) end = offs;
560 s->length = (uval_t)(offs - end - step - 1) / (uval_t)-step;
561 }
562
563 s->offset = offs;
564 s->end = end;
565 s->step = step;
566 return NULL;
567 }
568
slice(oper_t op,argcount_t indx)569 static MUST_CHECK Obj *slice(oper_t op, argcount_t indx) {
570 Obj *o2 = op->v2, *vv;
571 Dict *v1 = Dict(op->v1);
572 Funcargs *args = Funcargs(o2);
573 bool more;
574 linepos_t epoint2;
575
576 if (args->len < 1) {
577 return new_error_argnum(args->len, 1, 0, op->epoint2);
578 }
579 more = args->len - 1> indx;
580 o2 = args->val[indx].val;
581 epoint2 = &args->val[indx].epoint;
582
583 if (o2 == none_value) return val_reference(o2);
584 if (o2->obj->iterable) {
585 struct iter_s iter;
586 size_t i;
587 List *v;
588 Obj **vals;
589 iter.data = o2; o2->obj->getiter(&iter);
590
591 if (iter.len == 0) {
592 iter_destroy(&iter);
593 return val_reference(null_list);
594 }
595 v = new_list();
596 v->data = vals = list_create_elements(v, iter.len);
597 for (i = 0; i < iter.len && (o2 = iter.next(&iter)) != NULL; i++) {
598 vv = findit(v1, o2, epoint2);
599 if (vv->obj != ERROR_OBJ && more) {
600 Obj *result;
601 op->v1 = vv;
602 result = vv->obj->slice(op, indx + 1);
603 val_destroy(vv);
604 vv = result;
605 }
606 vals[i] = vv;
607 }
608 iter_destroy(&iter);
609 v->len = i;
610 return Obj(v);
611 }
612 if (o2->obj == COLONLIST_OBJ) {
613 struct sliceparam_s s;
614 uval_t i;
615 Dict *v;
616 Obj *err = dictsliceparams(v1, Colonlist(o2), &s, epoint2);
617 if (err != NULL) return err;
618
619 if (s.length == 0) {
620 return val_reference((v1->v.obj == TUPLE_OBJ) ? null_tuple : null_list);
621 }
622
623 if (s.step == 1 && s.length == v1->len && v1->def == NULL && !more) {
624 return val_reference(Obj(v1)); /* original tuple */
625 }
626 v = new_dict(s.length);
627 if (v == NULL) return new_error_mem(epoint2); /* overflow */
628 v->def = NULL;
629 for (i = 0; i < s.length; i++) {
630 struct pair_s *p = &v->data[i];
631 if (v1->data[s.offset].data == NULL) {
632 if (more) {
633 v->len = i;
634 val_destroy(Obj(v));
635 return new_error_obj(ERROR_____KEY_ERROR, v1->data[s.offset].key, epoint2);
636 }
637 p->data = NULL;
638 } else {
639 if (more) {
640 op->v1 = v1->data[s.offset].data;
641 p->data = op->v1->obj->slice(op, indx + 1);
642 } else {
643 p->data = val_reference(v1->data[s.offset].data);
644 }
645 }
646 p->hash = v1->data[s.offset].hash;
647 p->key = val_reference(v1->data[s.offset].key);
648 s.offset += s.step;
649 }
650 v->len = i;
651 reindex(v);
652 return Obj(v);
653 }
654
655 vv = findit(v1, o2, epoint2);
656 if (vv->obj != ERROR_OBJ && more) {
657 Obj *result;
658 op->v1 = vv;
659 result = vv->obj->slice(op, indx + 1);
660 val_destroy(vv);
661 return result;
662 }
663 return vv;
664 }
665
dict_sort(Dict * v1,const size_t * sort_index)666 MUST_CHECK Obj *dict_sort(Dict *v1, const size_t *sort_index) {
667 size_t i;
668 Dict *v = new_dict(v1->len);
669 if (v == NULL) err_msg_out_of_memory(); /* overflow */
670 for (i = 0; i < v1->len; i++) {
671 struct pair_s *d = &v->data[i];
672 const struct pair_s *s = &v1->data[sort_index[i]];
673 d->hash = s->hash;
674 d->key = val_reference(s->key);
675 d->data = s->data == NULL ? NULL : val_reference(s->data);
676 }
677 v->len = i;
678 reindex(v);
679 v->def = (v1->def == NULL) ? NULL : val_reference(v1->def);
680 return Obj(v);
681 }
682
concat(oper_t op)683 static MUST_CHECK Obj *concat(oper_t op) {
684 Dict *v1 = Dict(op->v1);
685 Dict *v2 = Dict(op->v2);
686 size_t j;
687 size_t ln;
688 Dict *dict;
689
690 if (v2->len == 0 && v2->def == NULL) return val_reference(Obj(v1));
691 if (v1->len == 0 && (v1->def == NULL || v2->def != NULL)) return val_reference(Obj(v2));
692
693 ln = v1->len + v2->len;
694 if (ln < v1->len) goto failed; /* overflow */
695 if (op->inplace == Obj(v1)) {
696 if (ln > ((v1->u.val == v1->data) ? lenof(v1->u.val) : v1->u.s.max)) {
697 size_t ln2 = ln + (ln < 1024 ? ln : 1024);
698 if (ln2 > ln) ln = ln2;
699 if (ln > SIZE_MAX / (sizeof(struct pair_s) + sizeof(size_t) * 2)) goto failed; /* overflow */
700 if (resize(v1, ln)) goto failed; /* overflow */
701 }
702 dict = Dict(val_reference(Obj(v1)));
703 if (dict->data != dict->u.val) dict->u.s.hash = -1;
704 } else {
705 dict = new_dict(ln);
706 if (dict == NULL) goto failed; /* overflow */
707
708 for (j = 0; j < v1->len; j++) {
709 struct pair_s *d = &dict->data[j];
710 const struct pair_s *s = &v1->data[j];
711 d->hash = s->hash;
712 d->key = val_reference(s->key);
713 d->data = s->data == NULL ? NULL : val_reference(s->data);
714 }
715 dict->len = j;
716 reindex(dict);
717 }
718 for (j = 0; j < v2->len; j++) {
719 dict_update(dict, &v2->data[j]);
720 }
721 if (op->inplace == Obj(v1)) {
722 if (v2->def != NULL) {
723 if (dict->def != NULL) val_destroy(dict->def);
724 dict->def = val_reference(v2->def);
725 }
726 } else {
727 dict->def = v2->def != NULL ? val_reference(v2->def) : v1->def != NULL ? val_reference(v1->def) : NULL;
728 }
729 if (dict == v1) return Obj(dict);
730 return normalize(dict);
731 failed:
732 return new_error_mem(op->epoint3); /* overflow */
733 }
734
calc2(oper_t op)735 static MUST_CHECK Obj *calc2(oper_t op) {
736 Obj *o2 = op->v2;
737
738 switch (o2->obj->type) {
739 case T_DICT:
740 if (op->op == O_CONCAT) {
741 return concat(op);
742 }
743 break;
744 case T_ANONSYMBOL:
745 case T_SYMBOL:
746 if (op->op == O_MEMBER) {
747 return findit(Dict(op->v1), o2, op->epoint2);
748 }
749 break;
750 case T_NONE:
751 case T_ERROR:
752 return val_reference(o2);
753 default:
754 if (o2->obj->iterable && op->op != O_X) {
755 return o2->obj->rcalc2(op);
756 }
757 break;
758 }
759 return obj_oper_error(op);
760 }
761
rcalc2(oper_t op)762 static MUST_CHECK Obj *rcalc2(oper_t op) {
763 Dict *v2 = Dict(op->v2);
764 Obj *o1 = op->v1;
765 if (op->op == O_IN) {
766 struct pair_s p;
767 Obj *err;
768
769 if (v2->len == 0) return ref_false();
770 p.key = o1;
771 err = o1->obj->hash(o1, &p.hash, op->epoint);
772 if (err != NULL) return err;
773 return truth_reference(dict_lookup(v2, &p) != NULL);
774 }
775 switch (o1->obj->type) {
776 default:
777 if (!o1->obj->iterable) {
778 break;
779 }
780 /* fall through */
781 case T_NONE:
782 case T_ERROR:
783 return o1->obj->calc2(op);
784 case T_DICT:
785 break;
786 }
787 return obj_oper_error(op);
788 }
789
dictobj_parse(struct values_s * values,size_t args)790 Obj *dictobj_parse(struct values_s *values, size_t args) {
791 size_t j;
792 Dict *dict = new_dict(args);
793 if (dict == NULL) return new_error_mem(&values->epoint);
794 dict->def = NULL;
795
796 for (j = 0; j < args; j++) {
797 Obj *err;
798 struct pair_s p;
799 struct values_s *v2 = &values[j];
800
801 p.key = v2->val;
802 if (p.key == none_value || p.key->obj == ERROR_OBJ) {
803 val_destroy(Obj(dict));
804 return val_reference(p.key);
805 }
806 if (p.key->obj != COLONLIST_OBJ) p.data = NULL;
807 else {
808 Colonlist *list = Colonlist(p.key);
809 if (list->len != 2 || (list->data[0] != default_value && list->data[1] == default_value)) {
810 err = new_error_obj(ERROR__NOT_KEYVALUE, p.key, &v2->epoint);
811 val_destroy(Obj(dict));
812 return err;
813 }
814 p.key = list->data[0];
815 p.data = list->data[1];
816 }
817 if (p.key == default_value) {
818 if (dict->def != NULL) val_destroy(dict->def);
819 dict->def = (p.data == NULL || p.data == default_value) ? NULL : val_reference(p.data);
820 continue;
821 }
822 err = p.key->obj->hash(p.key, &p.hash, &v2->epoint);
823 if (err != NULL) {
824 val_destroy(Obj(dict));
825 return err;
826 }
827 dict_update(dict, &p);
828 }
829 return normalize(dict);
830 }
831
dictobj_init(void)832 void dictobj_init(void) {
833 new_type(&obj, T_DICT, "dict", sizeof(Dict));
834 obj.iterable = true;
835 obj.destroy = destroy;
836 obj.garbage = garbage;
837 obj.same = same;
838 obj.hash = hash;
839 obj.len = len;
840 obj.getiter = getiter;
841 obj.getriter = getriter;
842 obj.repr = repr;
843 obj.calc2 = calc2;
844 obj.rcalc2 = rcalc2;
845 obj.slice = slice;
846 }
847
dictobj_names(void)848 void dictobj_names(void) {
849 new_builtin("dict", val_reference(Obj(DICT_OBJ)));
850 }
851
852