1 /*
2     $Id: listobj.c 2601 2021-04-25 10:43:31Z 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 "listobj.h"
20 #include <string.h>
21 #include "eval.h"
22 #include "variables.h"
23 #include "error.h"
24 #include "arguments.h"
25 
26 #include "boolobj.h"
27 #include "codeobj.h"
28 #include "strobj.h"
29 #include "intobj.h"
30 #include "typeobj.h"
31 #include "noneobj.h"
32 #include "errorobj.h"
33 #include "foldobj.h"
34 
35 static Type list_obj;
36 static Type tuple_obj;
37 static Type addrlist_obj;
38 static Type colonlist_obj;
39 
40 Type *const LIST_OBJ = &list_obj;
41 Type *const TUPLE_OBJ = &tuple_obj;
42 Type *const ADDRLIST_OBJ = &addrlist_obj;
43 Type *const COLONLIST_OBJ = &colonlist_obj;
44 
45 static Tuple null_tupleval = { { &tuple_obj, 1 }, 0, null_tupleval.u.val, { { 0 } } };
46 static List null_listval = { { &list_obj, 1 }, 0, null_listval.u.val, { { 0 } } };
47 static Addrlist null_addrlistval = { { &addrlist_obj, 1 }, 0, null_addrlistval.u.val, { { 0 } } };
48 
49 Obj *const null_tuple = &null_tupleval.v;
50 Obj *const null_list = &null_listval.v;
51 Obj *const null_addrlist = &null_addrlistval.v;
52 
ref_list(List * v1)53 static inline List *ref_list(List *v1) {
54     v1->v.refcount++; return v1;
55 }
56 
list_destroy(List * v1)57 static FAST_CALL NO_INLINE void list_destroy(List *v1) {
58     free(v1->data);
59 }
60 
destroy(Obj * o1)61 static FAST_CALL void destroy(Obj *o1) {
62     List *v1 = List(o1);
63     size_t i;
64     for (i = 0; i < v1->len; i++) {
65         val_destroy(v1->data[i]);
66     }
67     if (v1->u.val != v1->data) list_destroy(v1);
68 }
69 
garbage(Obj * o1,int j)70 static FAST_CALL void garbage(Obj *o1, int j) {
71     List *v1 = List(o1);
72     size_t i;
73     Obj *v;
74     switch (j) {
75     case -1:
76         for (i = 0; i < v1->len; i++) {
77             v1->data[i]->refcount--;
78         }
79         return;
80     case 0:
81         if (v1->u.val != v1->data) free(v1->data);
82         return;
83     case 1:
84         for (i = 0; i < v1->len; i++) {
85             v = v1->data[i];
86             if ((v->refcount & SIZE_MSB) != 0) {
87                 v->refcount -= SIZE_MSB - 1;
88                 v->obj->garbage(v, 1);
89             } else v->refcount++;
90         }
91         return;
92     }
93 }
94 
lnew(List * v,size_t len)95 static Obj **lnew(List *v, size_t len) {
96     v->len = len;
97     if (len <= lenof(v->u.val)) {
98         v->data = v->u.val;
99         return v->u.val;
100     }
101     if (len <= SIZE_MAX / sizeof *v->data) { /* overflow */
102         Obj **n = (Obj **)malloc(len * sizeof *v->data);
103         if (n != NULL) {
104             v->data = n;
105             v->u.s.max = len;
106             v->u.s.hash = -1;
107             return n;
108         }
109     }
110     v->len = 0;
111     v->data = v->u.val;
112     val_destroy(Obj(v));
113     return NULL;
114 }
115 
lextend(List * v,size_t len)116 static Obj **lextend(List *v, size_t len) {
117     Obj **tmp;
118     if (len <= lenof(v->u.val)) {
119         return v->u.val;
120     }
121     if (len > SIZE_MAX / sizeof *v->data) return NULL; /* overflow */
122     if (v->u.val != v->data) {
123         size_t len2;
124         if (len <= v->u.s.max) return v->data;
125         len2 = len + (len < 1024 ? len : 1024);
126         if (len2 > len) len = len2;
127         tmp = (Obj **)realloc(v->data, len * sizeof *v->data);
128         if (tmp != NULL) {
129             v->data = tmp;
130             v->u.s.max = len;
131             v->u.s.hash = -1;
132         }
133         return tmp;
134     }
135     tmp = (Obj **)malloc(len * sizeof *v->data);
136     if (tmp != NULL) {
137         memcpy(tmp, v->u.val, v->len * sizeof *v->data);
138         v->data = tmp;
139         v->u.s.max = len;
140         v->u.s.hash = -1;
141     }
142     return tmp;
143 }
144 
tuple_from_iterable(Obj * v1,Type * typ,linepos_t epoint)145 static MUST_CHECK Obj *tuple_from_iterable(Obj *v1, Type *typ, linepos_t epoint) {
146     Obj *v;
147     struct iter_s iter;
148     iter.data = v1; v1->obj->getiter(&iter);
149 
150     if (iter.len == 0) {
151         v = val_reference((typ == TUPLE_OBJ) ? null_tuple : null_list);
152     } else {
153         Obj **vals, *o2;
154         v = val_alloc(typ);
155         vals = lnew(List(v), iter.len);
156         if (vals == NULL) {
157             v = new_error_mem(epoint);
158         } else {
159             size_t i;
160             for (i = 0; i < iter.len && (o2 = iter.next(&iter)) != NULL; i++) {
161                 vals[i] = val_reference(o2);
162             }
163             List(v)->len = i;
164         }
165     }
166     iter_destroy(&iter);
167     return v;
168 }
169 
tuple_from_list(List * v1,Type * typ,linepos_t epoint)170 static MUST_CHECK Obj *tuple_from_list(List *v1, Type *typ, linepos_t epoint) {
171     size_t i, ln;
172     Obj **vals, **data = v1->data;
173     Tuple *v = Tuple(val_alloc(typ));
174 
175     ln = v1->len;
176     vals = lnew(v, ln);
177     if (vals == NULL) return new_error_mem(epoint);
178 
179     for (i = 0; i < ln; i++) {
180         vals[i] = val_reference(data[i]);
181     }
182     return Obj(v);
183 }
184 
list_from_obj(Obj * o1,Type * typ,linepos_t epoint)185 static MUST_CHECK Obj *list_from_obj(Obj *o1, Type *typ, linepos_t epoint) {
186     if (o1->obj == typ) {
187         return val_reference(o1);
188     }
189     switch (o1->obj->type) {
190     case T_NONE:
191     case T_ERROR:
192         return val_reference(o1);
193     case T_LIST:
194     case T_TUPLE:
195         return tuple_from_list(List(o1), typ, epoint);
196     case T_CODE:
197         return tuple_from_code(Code(o1), typ);
198     default:
199         if (o1->obj->iterable) {
200             return tuple_from_iterable(o1, typ, epoint);
201         }
202         break;
203     }
204     return new_error_conv(o1, typ, epoint);
205 }
206 
list_convert(oper_t op)207 static MUST_CHECK Obj *list_convert(oper_t op) {
208     return list_from_obj(op->v2, LIST_OBJ, op->epoint2);
209 }
210 
tuple_convert(oper_t op)211 static MUST_CHECK Obj *tuple_convert(oper_t op) {
212     return list_from_obj(op->v2, TUPLE_OBJ, op->epoint2);
213 }
214 
same(const Obj * o1,const Obj * o2)215 static FAST_CALL bool same(const Obj *o1, const Obj *o2) {
216     const List *v1 = List(o1), *v2 = List(o2);
217     size_t i;
218     if (o1->obj != o2->obj || v1->len != v2->len) return false;
219     for (i = 0; i < v2->len; i++) {
220         Obj *val = v1->data[i];
221         if (!val->obj->same(val, v2->data[i])) return false;
222     }
223     return true;
224 }
225 
hash(Obj * o1,int * hs,linepos_t epoint)226 static MUST_CHECK Obj *hash(Obj *o1, int *hs, linepos_t epoint) {
227     List *v1 = List(o1);
228     size_t i, l = v1->len;
229     Obj **vals = v1->data;
230     unsigned int h;
231     if (vals != v1->u.val && v1->u.s.hash >= 0) {
232         *hs = v1->u.s.hash;
233         return NULL;
234     }
235     h = 0;
236     for (i = 0; i < l; i++) {
237         int h2;
238         Obj *o2 = vals[i];
239         Obj *err = o2->obj->hash(o2, &h2, epoint);
240         if (err != NULL) return err;
241         h += (unsigned int)h2;
242     }
243     h ^= (unsigned int)i;
244     h &= ((~0U) >> 1);
245     if (vals != v1->u.val) v1->u.s.hash = (int)h;
246     *hs = (int)h;
247     return NULL;
248 }
249 
repr_listtuple(Obj * o1,linepos_t epoint,size_t maxsize)250 static MUST_CHECK Obj *repr_listtuple(Obj *o1, linepos_t epoint, size_t maxsize) {
251     Tuple *v1 = List(o1);
252     bool tupleorlist = (o1->obj != ADDRLIST_OBJ && o1->obj != COLONLIST_OBJ);
253     size_t i, len = tupleorlist ? 2 : 0, chars = len;
254     Tuple *list = NULL;
255     Obj **vals = NULL, *val;
256     Str *v;
257     uint8_t *s;
258     size_t llen = v1->len;
259     if (llen != 0) {
260         i = (llen != 1 || o1->obj != TUPLE_OBJ) ? (llen - 1) : llen;
261         len += i;
262         if (len < i) return NULL; /* overflow */
263         chars = len;
264         if (chars > maxsize) return NULL;
265         list = Tuple(val_alloc(TUPLE_OBJ));
266         vals = lnew(list, llen);
267         if (vals == NULL) return (epoint != NULL) ? new_error_mem(epoint) : NULL;
268         for (i = 0;i < llen; i++) {
269             Obj *o2 = v1->data[i];
270             if (o2 == default_value && o1->obj == COLONLIST_OBJ) {
271                 val = val_reference(null_str);
272             } else {
273                 val = o2->obj->repr(o2, epoint, maxsize - chars);
274                 if (val == NULL || val->obj != STR_OBJ) goto error;
275             }
276             v = Str(val);
277             len += v->len;
278             if (len < v->len) goto error2; /* overflow */
279             chars += v->chars;
280             if (chars > maxsize) {
281             error2:
282                 val_destroy(val);
283                 val = NULL;
284             error:
285                 list->len = i;
286                 val_destroy(Obj(list));
287                 return val;
288             }
289             vals[i] = val;
290         }
291         list->len = i;
292     } else if (chars > maxsize) return NULL;
293     v = new_str2(len);
294     if (v == NULL) {
295         if (list != NULL) val_destroy(Obj(list));
296         return NULL;
297     }
298     v->chars = chars;
299     s = v->data;
300     if (tupleorlist) *s++ = (o1->obj == LIST_OBJ) ? '[' : '(';
301     for (i = 0; i < llen; i++) {
302         Str *str = Str(vals[i]);
303         if (i != 0) *s++ = (o1->obj == COLONLIST_OBJ) ? ':' : ',';
304         if (str->len != 0) {
305             memcpy(s, str->data, str->len);
306             s += str->len;
307         }
308     }
309     if (i == 1 && o1->obj == TUPLE_OBJ) *s++ = ',';
310     if (tupleorlist) *s = (o1->obj == LIST_OBJ) ? ']' : ')';
311     if (list != NULL) val_destroy(Obj(list));
312     return Obj(v);
313 }
314 
len(oper_t op)315 static MUST_CHECK Obj *len(oper_t op) {
316     List *v1 = List(op->v2);
317     return int_from_size(v1->len);
318 }
319 
iter_forward(struct iter_s * v1)320 static FAST_CALL MUST_CHECK Obj *iter_forward(struct iter_s *v1) {
321     if (v1->val >= v1->len) return NULL;
322     return List(v1->data)->data[v1->val++];
323 }
324 
getiter(struct iter_s * v)325 static void getiter(struct iter_s *v) {
326     v->iter = NULL;
327     v->val = 0;
328     v->data = val_reference(v->data);
329     v->next = iter_forward;
330     v->len = List(v->data)->len;
331 }
332 
iter_reverse(struct iter_s * v1)333 static FAST_CALL MUST_CHECK Obj *iter_reverse(struct iter_s *v1) {
334     if (v1->val >= v1->len) return NULL;
335     return List(v1->data)->data[v1->len - ++v1->val];
336 }
337 
getriter(struct iter_s * v)338 static void getriter(struct iter_s *v) {
339     v->iter = NULL;
340     v->val = 0;
341     v->data = val_reference(v->data);
342     v->next = iter_reverse;
343     v->len = List(v->data)->len;
344 }
345 
list_create_elements(List * v,size_t n)346 Obj **list_create_elements(List *v, size_t n) {
347     if (n <= lenof(v->u.val)) return v->u.val;
348     if (n > SIZE_MAX / sizeof *v->data) err_msg_out_of_memory(); /* overflow */
349     v->u.s.max = n;
350     v->u.s.hash = -1;
351     return (Obj **)mallocx(n * sizeof *v->data);
352 }
353 
list_extend(List * lst)354 MUST_CHECK bool list_extend(List *lst) {
355     Obj **vals;
356     size_t o = lst->len, n;
357     if (lst->data == lst->u.val) {
358         n = 16;
359         vals = (Obj **)malloc(n * sizeof *lst->data);
360         if (vals == NULL) return true;
361         memcpy(vals, lst->u.val, o * sizeof *lst->data);
362     } else {
363         if (o < 256) n = o * 2;
364         else {
365             n = o + 256;
366             if (/*n < 256 ||*/ n > SIZE_MAX / sizeof *lst->data) return true; /* overflow */
367         }
368         vals = (Obj **)realloc(lst->data, n * sizeof *lst->data);
369         if (vals == NULL) return true;
370     }
371     lst->data = vals;
372     lst->u.s.max = n;
373     lst->u.s.hash = -1;
374     return false;
375 }
376 
list_shrink(List * lst,size_t i)377 void list_shrink(List *lst, size_t i) {
378     size_t j = i;
379     while (j < lst->len) val_destroy(lst->data[j++]);
380     lst->len = i;
381     if (lst->data != lst->u.val) {
382         if (lst->len <= lenof(lst->u.val)) {
383             memcpy(lst->u.val, lst->data, lst->len * sizeof *lst->data);
384             free(lst->data);
385             lst->data = lst->u.val;
386         } else {
387             Obj **v = (Obj **)realloc(lst->data, lst->len * sizeof *lst->data);
388             if (v != NULL) {
389                 lst->data = v;
390                 lst->u.s.max = lst->len;
391                 lst->u.s.hash = -1;
392             }
393         }
394     }
395 }
396 
new_tuple(size_t n)397 MUST_CHECK Tuple *new_tuple(size_t n) {
398      Tuple *v = Tuple(val_alloc(TUPLE_OBJ));
399      v->len = n;
400      if (n <= lenof(v->u.val)) {
401          v->data = v->u.val;
402          return v;
403      }
404      if (n > SIZE_MAX / sizeof *v->data) err_msg_out_of_memory(); /* overflow */
405      v->u.s.max = n;
406      v->u.s.hash = -1;
407      v->data = (Obj **)mallocx(n * sizeof *v->data);
408      return v;
409 }
410 
calc1(oper_t op)411 static MUST_CHECK Obj *calc1(oper_t op) {
412     Obj *o1 = op->v1;
413     List *v1 = List(o1), *v;
414     if (v1->len != 0) {
415         Obj **vals;
416         bool inplace = (op->inplace == o1);
417         size_t i;
418         if (inplace) {
419             v = ref_list(v1);
420             vals = v1->data;
421             if (vals != v->u.val) v->u.s.hash = -1;
422         } else {
423             v = List(val_alloc(o1->obj));
424             vals = lnew(v, v1->len);
425             if (vals == NULL) return new_error_mem(op->epoint3);
426         }
427         for (i = 0; i < v1->len; i++) {
428             Obj *val = v1->data[i];
429             op->v1 = val;
430             op->inplace = (inplace && val->refcount == 1) ? val : NULL;
431             val = op->v1->obj->calc1(op);
432             if (inplace) val_destroy(vals[i]);
433             vals[i] = val;
434         }
435         return Obj(v);
436     }
437     return val_reference(o1);
438 }
439 
calc2_list(oper_t op)440 static MUST_CHECK Obj *calc2_list(oper_t op) {
441     Obj *o1 = op->v1, *o2 = op->v2;
442     List *v1 = List(o1), *v2 = List(o2);
443     size_t i;
444     Error *err;
445 
446     switch (op->op) {
447     case O_CMP:
448     case O_EQ:
449     case O_NE:
450     case O_MIN:
451     case O_LT:
452     case O_LE:
453     case O_MAX:
454     case O_GT:
455     case O_GE:
456     case O_MUL:
457     case O_DIV:
458     case O_MOD:
459     case O_ADD:
460     case O_SUB:
461     case O_AND:
462     case O_OR:
463     case O_XOR:
464     case O_LSHIFT:
465     case O_RSHIFT:
466     case O_EXP:
467     case O_MEMBER:
468     case O_LAND:
469     case O_LOR:
470         {
471             if (v1->len == v2->len) {
472                 if (v1->len != 0) {
473                     Obj **vals;
474                     bool minmax = (op->op == O_MIN) || (op->op == O_MAX);
475                     List *v, *inplace;
476                     if (op->inplace == Obj(v1)) {
477                         v = ref_list(v1);
478                         vals = v1->data;
479                         inplace = v1;
480                         if (vals != v->u.val) v->u.s.hash = -1;
481                     } else if (o1->obj == o2->obj && op->inplace == Obj(v2)) {
482                         v = ref_list(v2);
483                         vals = v2->data;
484                         inplace = v2;
485                         if (vals != v->u.val) v->u.s.hash = -1;
486                     } else {
487                         v = List(val_alloc(o1->obj));
488                         vals = lnew(v, v1->len);
489                         if (vals == NULL) goto failed;
490                         inplace = NULL;
491                     }
492                     for (i = 0; i < v1->len; i++) {
493                         Obj *oo1 = op->v1 = v1->data[i];
494                         Obj *oo2 = op->v2 = v2->data[i];
495                         Obj *val;
496                         op->inplace = (inplace == v1 && oo1->refcount == 1 && !minmax) ? oo1 : NULL;
497                         val = op->v1->obj->calc2(op);
498                         if (minmax) {
499                             if (val == true_value) val_replace(&val, oo1);
500                             else if (val == false_value) val_replace(&val, oo2);
501                         }
502                         if (inplace != NULL) val_destroy(vals[i]);
503                         vals[i] = val;
504                     }
505                     return Obj(v);
506                 }
507                 return val_reference(Obj(v1));
508             }
509             if (v1->len == 1) {
510                 if (op->inplace == o1) op->inplace = NULL;
511                 op->v1 = v1->data[0];
512                 return op->v2->obj->rcalc2(op);
513             }
514             if (v2->len == 1) {
515                 if (op->inplace == o2) op->inplace = NULL;
516                 op->v2 = v2->data[0];
517                 return op->v1->obj->calc2(op);
518             }
519             err = new_error(ERROR_CANT_BROADCAS, op->epoint3);
520             err->u.broadcast.v1 = v1->len;
521             err->u.broadcast.v2 = v2->len;
522             return Obj(err);
523         }
524     case O_CONCAT:
525         {
526             Obj **vals;
527             size_t ln, j;
528             List *v;
529 
530             if (v1->len == 0) {
531                 return val_reference(o2);
532             }
533             if (v2->len == 0) {
534                 return val_reference(o1);
535             }
536             ln = v1->len + v2->len;
537             if (ln < v2->len) goto failed; /* overflow */
538             if (op->inplace == Obj(v1)) {
539                 vals = lextend(v1, ln);
540                 if (vals == NULL) goto failed;
541                 i = v1->len;
542                 v1->len = ln;
543                 v = ref_list(List(o1));
544             } else if (o1->obj == o2->obj && op->inplace == Obj(v2)) {
545                 vals = lextend(v2, ln);
546                 if (vals == NULL) goto failed;
547                 memmove(vals + v1->len, v2->data, v2->len * sizeof *v2->data);
548                 v2->len = ln;
549                 for (i = 0; i < v1->len; i++) {
550                     vals[i] = val_reference(v1->data[i]);
551                 }
552                 return val_reference(o2);
553             } else {
554                 v = List(val_alloc(o1->obj));
555                 vals = lnew(v, ln);
556                 if (vals == NULL) goto failed;
557                 for (i = 0; i < v1->len; i++) {
558                     vals[i] = val_reference(v1->data[i]);
559                 }
560             }
561             for (j = 0; i < ln; i++) {
562                 vals[i] = val_reference(v2->data[j++]);
563             }
564             return Obj(v);
565         }
566     default: break;
567     }
568     return obj_oper_error(op);
569 failed:
570     return new_error_mem(op->epoint3);
571 }
572 
repeat(oper_t op)573 static inline MUST_CHECK Obj *repeat(oper_t op) {
574     Obj **vals, *o1 = op->v1;
575     List *v1 = List(o1), *v;
576     uval_t rep;
577     Error *err;
578 
579     err = op->v2->obj->uval(op->v2, &rep, 8 * sizeof rep, op->epoint2);
580     if (err != NULL) return Obj(err);
581 
582     if (v1->len == 0 || rep == 0) return val_reference((o1->obj == TUPLE_OBJ) ? null_tuple : null_list);
583     do {
584         size_t i = 0, j, ln;
585         if (rep == 1) {
586             return val_reference(o1);
587         }
588         if (v1->len > SIZE_MAX / rep) break; /* overflow */
589         v = List(val_alloc(o1->obj));
590         ln = v1->len * rep;
591         vals = lnew(v, ln);
592         if (vals == NULL) break;
593         while ((rep--) != 0) {
594             for (j = 0;j < v1->len; j++, i++) {
595                 vals[i] = val_reference(v1->data[j]);
596             }
597         }
598         return Obj(v);
599     } while (false);
600     return new_error_mem(op->epoint3);
601 }
602 
indexoffs(struct indexoffs_s * io)603 MUST_CHECK Obj *indexoffs(struct indexoffs_s *io) {
604     ival_t ival;
605     Obj *err = Obj(io->val->obj->ival(io->val, &ival, 8 * sizeof ival, io->epoint));
606     if (err != NULL) return err;
607 
608     if (ival >= 0) {
609         if ((uval_t)ival < io->len) {
610             io->offs = (uval_t)ival;
611             return NULL;
612         }
613     } else {
614         ival = -ival;
615         if ((uval_t)ival <= io->len) {
616             io->offs = io->len - (uval_t)ival;
617             return NULL;
618         }
619     }
620     return new_error_obj(ERROR___INDEX_RANGE, io->val, io->epoint);
621 }
622 
sliceparams(struct sliceparam_s * s,const struct indexoffs_s * io)623 MUST_CHECK Obj *sliceparams(struct sliceparam_s *s, const struct indexoffs_s *io) {
624     const Colonlist *v2 = Colonlist(io->val);
625     Obj *err;
626     ival_t len, offs, end, step = 1;
627 
628     if (io->len >= (1U << (8 * sizeof(ival_t) - 1))) return new_error_mem(io->epoint); /* overflow */
629     len = (ival_t)io->len;
630     if (v2->len > 3 || v2->len < 1) {
631         return new_error_argnum(v2->len <= ~(argcount_t)0 ? (argcount_t)v2->len : ~(argcount_t)0, 1, 3, io->epoint);
632     }
633     end = len;
634     if (v2->len > 2) {
635         if (v2->data[2] != default_value) {
636             err = Obj(v2->data[2]->obj->ival(v2->data[2], &step, 8 * sizeof step, io->epoint));
637             if (err != NULL) return err;
638             if (step == 0) {
639                 return Obj(new_error(ERROR_NO_ZERO_VALUE, io->epoint));
640             }
641         }
642     }
643     if (v2->len > 1) {
644         if (v2->data[1] == default_value) end = (step > 0) ? len : -1;
645         else {
646             err = Obj(v2->data[1]->obj->ival(v2->data[1], &end, 8 * sizeof end, io->epoint));
647             if (err != NULL) return err;
648             if (end >= 0) {
649                 if (end > len) end = len;
650             } else {
651                 end += len;
652                 if (end < -1) end = -1;
653             }
654         }
655     } else end = len;
656     if (v2->data[0] == default_value) offs = (step > 0) ? 0 : len - 1;
657     else {
658         ival_t minus;
659         err = Obj(v2->data[0]->obj->ival(v2->data[0], &offs, 8 * sizeof offs, io->epoint));
660         if (err != NULL) return err;
661         minus = (step < 0) ? -1 : 0;
662         if (offs >= 0) {
663             if (offs > len + minus) offs = len + minus;
664         } else {
665             offs += len;
666         }
667         if (offs < minus) offs = minus;
668     }
669 
670     if (step > 0) {
671         if (offs > end) offs = end;
672         s->length = (uval_t)(end - offs + step - 1) / (uval_t)step;
673     } else {
674         if (end > offs) end = offs;
675         s->length = (uval_t)(offs - end - step - 1) / (uval_t)-step;
676     }
677 
678     s->offset = offs;
679     s->end = end;
680     s->step = step;
681     return NULL;
682 }
683 
slice(oper_t op,argcount_t indx)684 static MUST_CHECK Obj *slice(oper_t op, argcount_t indx) {
685     Obj **vals;
686     List *v, *v1 = List(op->v1);
687     Funcargs *args = Funcargs(op->v2);
688     size_t i;
689     Obj *err;
690     bool more;
691     struct indexoffs_s io;
692 
693     if (args->len < 1) {
694         return new_error_argnum(args->len, 1, 0, op->epoint2);
695     }
696     more = args->len - 1 > indx;
697     io.len = v1->len;
698     io.epoint = &args->val[indx].epoint;
699     io.val = args->val[indx].val;
700 
701     if (io.val->obj->iterable) {
702         struct iter_s iter;
703         iter.data = io.val; io.val->obj->getiter(&iter);
704 
705         if (iter.len == 0) {
706             iter_destroy(&iter);
707             return val_reference((v1->v.obj == TUPLE_OBJ) ? null_tuple : null_list);
708         }
709         v = List(val_alloc(v1->v.obj));
710         vals = lnew(v, iter.len);
711         if (vals == NULL) {
712             iter_destroy(&iter);
713             goto failed;
714         }
715         for (i = 0; i < iter.len && (io.val = iter.next(&iter)) != NULL; i++) {
716             err = indexoffs(&io);
717             if (err != NULL) {
718                 vals[i] = err;
719                 continue;
720             }
721             if (more) {
722                 op->v1 = v1->data[io.offs];
723                 vals[i] = op->v1->obj->slice(op, indx + 1);
724             } else {
725                 vals[i] = val_reference(v1->data[io.offs]);
726             }
727         }
728         v->len = i;
729         iter_destroy(&iter);
730         return Obj(v);
731     }
732     if (io.val->obj == COLONLIST_OBJ) {
733         struct sliceparam_s s;
734 
735         err = sliceparams(&s, &io);
736         if (err != NULL) return err;
737 
738         if (s.length == 0) {
739             return val_reference((v1->v.obj == TUPLE_OBJ) ? null_tuple : null_list);
740         }
741 
742         if (s.step == 1 && s.length == v1->len && !more) {
743             return val_reference(Obj(v1)); /* original tuple */
744         }
745         v = List(val_alloc(v1->v.obj));
746         vals = lnew(v, s.length);
747         if (vals == NULL) goto failed;
748         for (i = 0; i < s.length; i++) {
749             if (more) {
750                 op->v1 = v1->data[s.offset];
751                 vals[i] = op->v1->obj->slice(op, indx + 1);
752             } else {
753                 vals[i] = val_reference(v1->data[s.offset]);
754             }
755             s.offset += s.step;
756         }
757         return Obj(v);
758     }
759     err = indexoffs(&io);
760     if (err != NULL) return err;
761     if (more) {
762         op->v1 = v1->data[io.offs];
763         return op->v1->obj->slice(op, indx + 1);
764     }
765     return val_reference(v1->data[io.offs]);
766 failed:
767     return new_error_mem(op->epoint3);
768 }
769 
calc2(oper_t op)770 static MUST_CHECK Obj *calc2(oper_t op) {
771     Obj *o1 = op->v1, *o2 = op->v2;
772     List *v1 = List(o1);
773     size_t i;
774     Obj **vals;
775 
776     if (op->op == O_X) {
777         if (o2 == none_value || o2->obj == ERROR_OBJ) return val_reference(o2);
778         return repeat(op);
779     }
780     if (op->op == O_IN || o2 == fold_value) {
781         return o2->obj->rcalc2(op);
782     }
783     if (o2->obj == TUPLE_OBJ || o2->obj == LIST_OBJ) {
784         return calc2_list(op);
785     }
786     if (o2 == none_value || o2->obj == ERROR_OBJ) {
787         return val_reference(o2);
788     }
789     if (v1->len != 0) {
790         bool minmax = (op->op == O_MIN) || (op->op == O_MAX), inplace = (op->inplace == o1);
791         List *list;
792         if (inplace) {
793             list = ref_list(List(o1));
794             vals = list->data;
795             if (vals != list->u.val) list->u.s.hash = -1;
796         } else {
797             list = List(val_alloc(o1->obj));
798             vals = lnew(list, v1->len);
799             if (vals == NULL) return new_error_mem(op->epoint3);
800         }
801         for (i = 0; i < v1->len; i++) {
802             Obj *val;
803             Obj *oo1 = v1->data[i];
804             op->v1 = oo1;
805             op->v2 = o2;
806             op->inplace = (inplace && oo1->refcount == 1 && !minmax) ? oo1 : NULL;
807             val = op->v1->obj->calc2(op);
808             if (minmax) {
809                 if (val == true_value) val_replace(&val, oo1);
810                 else if (val == false_value) val_replace(&val, o2);
811             }
812             if (inplace) val_destroy(vals[i]);
813             vals[i] = val;
814         }
815         return Obj(list);
816     }
817     return val_reference(o1);
818 }
819 
rcalc2(oper_t op)820 static MUST_CHECK Obj *rcalc2(oper_t op) {
821     Obj *o1 = op->v1, *o2 = op->v2;
822     List *v2 = List(o2);
823     size_t i;
824     Obj **vals;
825 
826     if (op->op == O_IN) {
827         op->op = O_EQ;
828         for (i = 0; i < v2->len; i++) {
829             Obj *result;
830             op->v1 = o1;
831             op->v2 = v2->data[i];
832             op->inplace = NULL;
833             result = o1->obj->calc2(op);
834             if (result == true_value) {
835                 op->op = O_IN;
836                 return result;
837             }
838             val_destroy(result);
839         }
840         op->op = O_IN;
841         return ref_false();
842     }
843     if (o1->obj == TUPLE_OBJ || o1->obj == LIST_OBJ) {
844         return calc2_list(op);
845     }
846     if (o1 == none_value || o1->obj == ERROR_OBJ || o1 == fold_value) {
847         return o1->obj->calc2(op);
848     }
849     if (v2->len != 0) {
850         bool minmax = (op->op == O_MIN) || (op->op == O_MAX), inplace = (op->inplace == o2);
851         List *v;
852         if (inplace) {
853             v = ref_list(List(o2));
854             vals = v->data;
855             if (vals != v->u.val) v->u.s.hash = -1;
856         } else {
857             v = List(val_alloc(o2->obj));
858             vals = lnew(v, v2->len);
859             if (vals == NULL) return new_error_mem(op->epoint3);
860         }
861         for (i = 0; i < v2->len; i++) {
862             Obj *val;
863             Obj *oo2 = v2->data[i];
864             op->v2 = oo2;
865             op->v1 = o1;
866             op->inplace = (inplace && oo2->refcount == 1 && !minmax) ? oo2 : NULL;
867             val = o1->obj->calc2(op);
868             if (minmax) {
869                 if (val == true_value) val_replace(&val, o1);
870                 else if (val == false_value) val_replace(&val, oo2);
871             }
872             if (inplace) val_destroy(vals[i]);
873             vals[i] = val;
874         }
875         return Obj(v);
876     }
877     return val_reference(o2);
878 }
879 
init(Type * obj)880 static void init(Type *obj) {
881     obj->iterable = true;
882     obj->destroy = destroy;
883     obj->garbage = garbage;
884     obj->same = same;
885     obj->hash = hash;
886     obj->len = len;
887     obj->getiter = getiter;
888     obj->getriter = getriter;
889     obj->calc1 = calc1;
890     obj->calc2 = calc2;
891     obj->rcalc2 = rcalc2;
892     obj->slice = slice;
893     obj->repr = repr_listtuple;
894 }
895 
listobj_init(void)896 void listobj_init(void) {
897     new_type(&list_obj, T_LIST, "list", sizeof(List));
898     init(&list_obj);
899     list_obj.convert = list_convert;
900     new_type(&tuple_obj, T_TUPLE, "tuple", sizeof(Tuple));
901     init(&tuple_obj);
902     tuple_obj.convert = tuple_convert;
903     new_type(&addrlist_obj, T_ADDRLIST, "addresslist", sizeof(Addrlist));
904     addrlist_obj.destroy = destroy;
905     addrlist_obj.garbage = garbage;
906     addrlist_obj.same = same;
907     addrlist_obj.repr = repr_listtuple;
908     new_type(&colonlist_obj, T_COLONLIST, "colonlist", sizeof(Colonlist));
909     colonlist_obj.destroy = destroy;
910     colonlist_obj.garbage = garbage;
911     colonlist_obj.same = same;
912     colonlist_obj.repr = repr_listtuple;
913 }
914 
listobj_names(void)915 void listobj_names(void) {
916     new_builtin("list", val_reference(Obj(LIST_OBJ)));
917     new_builtin("tuple", val_reference(Obj(TUPLE_OBJ)));
918 }
919 
listobj_destroy(void)920 void listobj_destroy(void) {
921 #ifdef DEBUG
922     if (null_tuple->refcount != 1) fprintf(stderr, "tuple %" PRIuSIZE "\n", null_tuple->refcount - 1);
923     if (null_list->refcount != 1) fprintf(stderr, "list %" PRIuSIZE "\n", null_list->refcount - 1);
924     if (null_addrlist->refcount != 1) fprintf(stderr, "addrlist %" PRIuSIZE "\n", null_addrlist->refcount - 1);
925 #endif
926 }
927