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