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