1from itertools import product
2from textwrap import dedent
3
4import numpy as np
5
6from numba import njit
7from numba import int32, float32, prange
8from numba.core import types
9from numba import typeof
10from numba.typed import List, Dict
11from numba.core.errors import TypingError
12from numba.tests.support import (TestCase, MemoryLeakMixin, override_config,
13                                 forbid_codegen, skip_parfors_unsupported)
14
15from numba.core.unsafe.refcount import get_refcount
16from numba.experimental import jitclass
17
18
19# global typed-list for testing purposes
20global_typed_list = List.empty_list(int32)
21for i in (1, 2, 3):
22    global_typed_list.append(int32(i))
23
24
25def to_tl(l):
26    """ Convert cpython list to typed-list. """
27    tl = List.empty_list(int32)
28    for k in l:
29        tl.append(k)
30    return tl
31
32
33class TestTypedList(MemoryLeakMixin, TestCase):
34    def test_basic(self):
35        l = List.empty_list(int32)
36        # len
37        self.assertEqual(len(l), 0)
38        # append
39        l.append(0)
40        # len
41        self.assertEqual(len(l), 1)
42        # setitem
43        l.append(0)
44        l.append(0)
45        l[0] = 10
46        l[1] = 11
47        l[2] = 12
48        # getitem
49        self.assertEqual(l[0], 10)
50        self.assertEqual(l[1], 11)
51        self.assertEqual(l[2], 12)
52        self.assertEqual(l[-3], 10)
53        self.assertEqual(l[-2], 11)
54        self.assertEqual(l[-1], 12)
55        # __iter__
56        # the default __iter__ from MutableSequence will raise an IndexError
57        # via __getitem__ and thus leak an exception, so this shouldn't
58        for i in l:
59            pass
60        # contains
61        self.assertTrue(10 in l)
62        self.assertFalse(0 in l)
63        # count
64        l.append(12)
65        self.assertEqual(l.count(0), 0)
66        self.assertEqual(l.count(10), 1)
67        self.assertEqual(l.count(12), 2)
68        # pop
69        self.assertEqual(len(l), 4)
70        self.assertEqual(l.pop(), 12)
71        self.assertEqual(len(l), 3)
72        self.assertEqual(l.pop(1), 11)
73        self.assertEqual(len(l), 2)
74        # extend
75        l.extend((100, 200, 300))
76        self.assertEqual(len(l), 5)
77        self.assertEqual(list(l), [10, 12, 100, 200, 300])
78        # insert
79        l.insert(0, 0)
80        self.assertEqual(list(l), [0, 10, 12, 100, 200, 300])
81        l.insert(3, 13)
82        self.assertEqual(list(l), [0, 10, 12, 13, 100, 200, 300])
83        l.insert(100, 400)
84        self.assertEqual(list(l), [0, 10, 12, 13, 100, 200, 300, 400])
85        # remove
86        l.remove(0)
87        l.remove(400)
88        l.remove(13)
89        self.assertEqual(list(l), [10, 12, 100, 200, 300])
90        # clear
91        l.clear()
92        self.assertEqual(len(l), 0)
93        self.assertEqual(list(l), [])
94        # reverse
95        l.extend(tuple(range(10, 20)))
96        l.reverse()
97        self.assertEqual(list(l), list(range(10, 20))[::-1])
98        # copy
99        new = l.copy()
100        self.assertEqual(list(new), list(range(10, 20))[::-1])
101        # equal
102        self.assertEqual(l, new)
103        # not equal
104        new[-1] = 42
105        self.assertNotEqual(l, new)
106        # index
107        self.assertEqual(l.index(15), 4)
108
109    def test_list_extend_refines_on_unicode_type(self):
110        @njit
111        def foo(string):
112            l = List()
113            l.extend(string)
114            return l
115
116        for func in (foo, foo.py_func):
117            for string in ("a", "abc", "\nabc\t"):
118                self.assertEqual(list(func(string)), list(string))
119
120    def test_unsigned_access(self):
121        L = List.empty_list(int32)
122        ui32_0 = types.uint32(0)
123        ui32_1 = types.uint32(1)
124        ui32_2 = types.uint32(2)
125
126        # insert
127        L.append(types.uint32(10))
128        L.append(types.uint32(11))
129        L.append(types.uint32(12))
130        self.assertEqual(len(L), 3)
131
132        # getitem
133        self.assertEqual(L[ui32_0], 10)
134        self.assertEqual(L[ui32_1], 11)
135        self.assertEqual(L[ui32_2], 12)
136
137        # setitem
138        L[ui32_0] = 123
139        L[ui32_1] = 456
140        L[ui32_2] = 789
141        self.assertEqual(L[ui32_0], 123)
142        self.assertEqual(L[ui32_1], 456)
143        self.assertEqual(L[ui32_2], 789)
144
145        # index
146        ui32_123 = types.uint32(123)
147        ui32_456 = types.uint32(456)
148        ui32_789 = types.uint32(789)
149        self.assertEqual(L.index(ui32_123), 0)
150        self.assertEqual(L.index(ui32_456), 1)
151        self.assertEqual(L.index(ui32_789), 2)
152
153        # delitem
154        L.__delitem__(ui32_2)
155        del L[ui32_1]
156        self.assertEqual(len(L), 1)
157        self.assertEqual(L[ui32_0], 123)
158
159        # pop
160        L.append(2)
161        L.append(3)
162        L.append(4)
163        self.assertEqual(len(L), 4)
164        self.assertEqual(L.pop(), 4)
165        self.assertEqual(L.pop(ui32_2), 3)
166        self.assertEqual(L.pop(ui32_1), 2)
167        self.assertEqual(L.pop(ui32_0), 123)
168
169    def test_dtype(self):
170
171        L = List.empty_list(int32)
172        self.assertEqual(L._dtype, int32)
173
174        L = List.empty_list(float32)
175        self.assertEqual(L._dtype, float32)
176
177        @njit
178        def foo():
179            li, lf = List(), List()
180            li.append(int32(1))
181            lf.append(float32(1.0))
182            return li._dtype, lf._dtype
183
184        self.assertEqual(foo(), (np.dtype('int32'), np.dtype('float32')))
185        self.assertEqual(foo.py_func(), (int32, float32))
186
187    def test_dtype_raises_exception_on_untyped_list(self):
188
189        with self.assertRaises(RuntimeError) as raises:
190            L = List()
191            L._dtype
192        self.assertIn(
193            "invalid operation on untyped list",
194            str(raises.exception),
195        )
196
197    @skip_parfors_unsupported
198    def test_unsigned_prange(self):
199        @njit(parallel=True)
200        def foo(a):
201            r = types.uint64(3)
202            s = types.uint64(0)
203            for i in prange(r):
204                s = s + a[i]
205            return s
206
207        a = List.empty_list(types.uint64)
208        a.append(types.uint64(12))
209        a.append(types.uint64(1))
210        a.append(types.uint64(7))
211        self.assertEqual(foo(a), 20)
212
213    def test_compiled(self):
214        @njit
215        def producer():
216            l = List.empty_list(int32)
217            l.append(23)
218            return l
219
220        @njit
221        def consumer(l):
222            return l[0]
223
224        l = producer()
225        val = consumer(l)
226        self.assertEqual(val, 23)
227
228    def test_getitem_slice(self):
229        """ Test getitem using a slice.
230
231        This tests suffers from combinatorial explosion, so we parametrize it
232        and compare results against the regular list in a quasi fuzzing
233        approach.
234
235        """
236        # initialize regular list
237        rl = list(range(10, 20))
238        # initialize typed list
239        tl = List.empty_list(int32)
240        for i in range(10, 20):
241            tl.append(i)
242        # define the ranges
243        start_range = list(range(-20, 30))
244        stop_range = list(range(-20, 30))
245        step_range = [-5, -4, -3, -2, -1, 1, 2, 3, 4, 5]
246
247        # check that they are the same initially
248        self.assertEqual(rl, list(tl))
249        # check that copy by slice works, no start, no stop, no step
250        self.assertEqual(rl[:], list(tl[:]))
251
252        # start only
253        for sa in start_range:
254            self.assertEqual(rl[sa:], list(tl[sa:]))
255        # stop only
256        for so in stop_range:
257            self.assertEqual(rl[:so], list(tl[:so]))
258        # step only
259        for se in step_range:
260            self.assertEqual(rl[::se], list(tl[::se]))
261
262        # start and stop
263        for sa, so in product(start_range, stop_range):
264            self.assertEqual(rl[sa:so], list(tl[sa:so]))
265        # start and step
266        for sa, se in product(start_range, step_range):
267            self.assertEqual(rl[sa::se], list(tl[sa::se]))
268        # stop and step
269        for so, se in product(stop_range, step_range):
270            self.assertEqual(rl[:so:se], list(tl[:so:se]))
271
272        # start, stop and step
273        for sa, so, se in product(start_range, stop_range, step_range):
274            self.assertEqual(rl[sa:so:se], list(tl[sa:so:se]))
275
276    def test_setitem_slice(self):
277        """ Test setitem using a slice.
278
279        This tests suffers from combinatorial explosion, so we parametrize it
280        and compare results against the regular list in a quasi fuzzing
281        approach.
282
283        """
284
285        def setup(start=10, stop=20):
286            # initialize regular list
287            rl_ = list(range(start, stop))
288            # initialize typed list
289            tl_ = List.empty_list(int32)
290            # populate typed list
291            for i in range(start, stop):
292                tl_.append(i)
293            # check they are the same
294            self.assertEqual(rl_, list(tl_))
295            return rl_, tl_
296
297        ### Simple slicing ###
298
299        # assign to itself
300        rl, tl = setup()
301        rl[:], tl[:] = rl, tl
302        self.assertEqual(rl, list(tl))
303
304        # extend self
305        rl, tl = setup()
306        rl[len(rl):], tl[len(tl):] = rl, tl
307        self.assertEqual(rl, list(tl))
308        # prepend self
309        rl, tl = setup()
310        rl[:0], tl[:0] = rl, tl
311        self.assertEqual(rl, list(tl))
312        # partial assign to self, with equal length
313        rl, tl = setup()
314        rl[3:5], tl[3:5] = rl[6:8], tl[6:8]
315        self.assertEqual(rl, list(tl))
316        # partial assign to self, with larger slice
317        rl, tl = setup()
318        rl[3:5], tl[3:5] = rl[6:9], tl[6:9]
319        self.assertEqual(rl, list(tl))
320        # partial assign to self, with smaller slice
321        rl, tl = setup()
322        rl[3:5], tl[3:5] = rl[6:7], tl[6:7]
323        self.assertEqual(rl, list(tl))
324
325        # extend
326        rl, tl = setup()
327        rl[len(rl):] = list(range(110, 120))
328        tl[len(tl):] = to_tl(range(110,120))
329        self.assertEqual(rl, list(tl))
330        # extend empty
331        rl, tl = setup(0, 0)
332        rl[len(rl):] = list(range(110, 120))
333        tl[len(tl):] = to_tl(range(110,120))
334        self.assertEqual(rl, list(tl))
335        # extend singleton
336        rl, tl = setup(0, 1)
337        rl[len(rl):] = list(range(110, 120))
338        tl[len(tl):] = to_tl(range(110,120))
339        self.assertEqual(rl, list(tl))
340
341        # prepend
342        rl, tl = setup()
343        rl[:0], tl[:0] = list(range(110, 120)), to_tl(range(110,120))
344        self.assertEqual(rl, list(tl))
345        # prepend empty
346        rl, tl = setup(0,0)
347        rl[:0], tl[:0] = list(range(110, 120)), to_tl(range(110,120))
348        self.assertEqual(rl, list(tl))
349        # prepend singleton
350        rl, tl = setup(0,1)
351        rl[:0], tl[:0] = list(range(110, 120)), to_tl(range(110,120))
352        self.assertEqual(rl, list(tl))
353
354        # simple equal length assignment, just replace
355        rl, tl = setup()
356        rl[1:3], tl[1:3] = [100, 200], to_tl([100, 200])
357        self.assertEqual(rl, list(tl))
358
359        # slice for assignment is larger, need to replace and insert
360        rl, tl = setup()
361        rl[1:3], tl[1:3] = [100, 200, 300, 400], to_tl([100, 200, 300, 400])
362        self.assertEqual(rl, list(tl))
363
364        # slice for assignment is smaller, need to replace and delete
365        rl, tl = setup()
366        rl[1:3], tl[1:3] = [100], to_tl([100])
367        self.assertEqual(rl, list(tl))
368
369        # slice for assignment is smaller and item is empty, need to delete
370        rl, tl = setup()
371        rl[1:3], tl[1:3] = [], to_tl([])
372        self.assertEqual(rl, list(tl))
373
374        # Synonym for clear
375        rl, tl = setup()
376        rl[:], tl[:] = [], to_tl([])
377        self.assertEqual(rl, list(tl))
378
379        ### Extended slicing ###
380
381        # replace every second element
382        rl, tl = setup()
383        rl[::2], tl[::2] = [100,200,300,400,500], to_tl([100,200,300,400,500])
384        self.assertEqual(rl, list(tl))
385        # replace every second element, backwards
386        rl, tl = setup()
387        rl[::-2], tl[::-2] = [100,200,300,400,500], to_tl([100,200,300,400,500])
388        self.assertEqual(rl, list(tl))
389
390        # reverse assign to itself
391        rl, tl = setup()
392        rl[::-1], tl[::-1] = rl, tl
393        self.assertEqual(rl, list(tl))
394
395    def test_setitem_slice_value_error(self):
396        self.disable_leak_check()
397
398        tl = List.empty_list(int32)
399        for i in range(10,20):
400            tl.append(i)
401
402        assignment = List.empty_list(int32)
403        for i in range(1, 4):
404            assignment.append(i)
405
406        with self.assertRaises(ValueError) as raises:
407            tl[8:3:-1] = assignment
408        self.assertIn(
409            "length mismatch for extended slice and sequence",
410            str(raises.exception),
411        )
412
413    def test_delitem_slice(self):
414        """ Test delitem using a slice.
415
416        This tests suffers from combinatorial explosion, so we parametrize it
417        and compare results against the regular list in a quasi fuzzing
418        approach.
419
420        """
421
422        def setup(start=10, stop=20):
423            # initialize regular list
424            rl_ = list(range(start, stop))
425            # initialize typed list
426            tl_ = List.empty_list(int32)
427            # populate typed list
428            for i in range(start, stop):
429                tl_.append(i)
430            # check they are the same
431            self.assertEqual(rl_, list(tl_))
432            return rl_, tl_
433
434        # define the ranges
435        start_range = list(range(-20, 30))
436        stop_range = list(range(-20, 30))
437        step_range = [-5, -4, -3, -2, -1, 1, 2, 3, 4, 5]
438
439        rl, tl = setup()
440        # check that they are the same initially
441        self.assertEqual(rl, list(tl))
442        # check that deletion of the whole list by slice works
443        del rl[:]
444        del tl[:]
445        self.assertEqual(rl, list(tl))
446
447        # start only
448        for sa in start_range:
449            rl, tl = setup()
450            del rl[sa:]
451            del tl[sa:]
452            self.assertEqual(rl, list(tl))
453        # stop only
454        for so in stop_range:
455            rl, tl = setup()
456            del rl[:so]
457            del tl[:so]
458            self.assertEqual(rl, list(tl))
459        # step only
460        for se in step_range:
461            rl, tl = setup()
462            del rl[::se]
463            del tl[::se]
464            self.assertEqual(rl, list(tl))
465
466        # start and stop
467        for sa, so in product(start_range, stop_range):
468            rl, tl = setup()
469            del rl[sa:so]
470            del tl[sa:so]
471            self.assertEqual(rl, list(tl))
472        # start and step
473        for sa, se in product(start_range, step_range):
474            rl, tl = setup()
475            del rl[sa::se]
476            del tl[sa::se]
477            self.assertEqual(rl, list(tl))
478        # stop and step
479        for so, se in product(stop_range, step_range):
480            rl, tl = setup()
481            del rl[:so:se]
482            del tl[:so:se]
483            self.assertEqual(rl, list(tl))
484
485        # start, stop and step
486        for sa, so, se in product(start_range, stop_range, step_range):
487            rl, tl = setup()
488            del rl[sa:so:se]
489            del tl[sa:so:se]
490            self.assertEqual(rl, list(tl))
491
492    def test_list_create_no_jit_using_empty_list(self):
493        with override_config('DISABLE_JIT', True):
494            with forbid_codegen():
495                l = List.empty_list(types.int32)
496                self.assertEqual(type(l), list)
497
498    def test_list_create_no_jit_using_List(self):
499        with override_config('DISABLE_JIT', True):
500            with forbid_codegen():
501                l = List()
502                self.assertEqual(type(l), list)
503
504    def test_catch_global_typed_list(self):
505        @njit()
506        def foo():
507            x = List()
508            for i in global_typed_list:
509                x.append(i)
510
511        expected_message = ("The use of a ListType[int32] type, assigned to "
512                            "variable 'global_typed_list' in globals, is not "
513                            "supported as globals are considered compile-time "
514                            "constants and there is no known way to compile "
515                            "a ListType[int32] type as a constant.")
516        with self.assertRaises(TypingError) as raises:
517            foo()
518        self.assertIn(
519            expected_message,
520            str(raises.exception),
521        )
522
523    def test_repr(self):
524        l = List()
525        expected = "ListType[Undefined]([])"
526        self.assertEqual(expected, repr(l))
527
528        l = List([int32(i) for i in (1, 2, 3)])
529        expected = "ListType[int32]([1, 2, 3])"
530        self.assertEqual(expected, repr(l))
531
532
533class TestNoneType(MemoryLeakMixin, TestCase):
534
535    def test_append_none(self):
536        @njit
537        def impl():
538            l = List()
539            l.append(None)
540            return l
541
542        self.assertEqual(impl.py_func(), impl())
543
544    def test_len_none(self):
545        @njit
546        def impl():
547            l = List()
548            l.append(None)
549            return len(l)
550
551        self.assertEqual(impl.py_func(), impl())
552
553    def test_getitem_none(self):
554        @njit
555        def impl():
556            l = List()
557            l.append(None)
558            return l[0]
559
560        self.assertEqual(impl.py_func(), impl())
561
562    def test_setitem_none(self):
563        @njit
564        def impl():
565            l = List()
566            l.append(None)
567            l[0] = None
568            return l
569
570        self.assertEqual(impl.py_func(), impl())
571
572    def test_equals_none(self):
573        @njit
574        def impl():
575            l = List()
576            l.append(None)
577            m = List()
578            m.append(None)
579            return l == m, l != m, l < m, l <= m, l > m, l >= m
580
581        self.assertEqual(impl.py_func(), impl())
582
583    def test_not_equals_none(self):
584        @njit
585        def impl():
586            l = List()
587            l.append(None)
588            m = List()
589            m.append(1)
590            return l == m, l != m, l < m, l <= m, l > m, l >= m
591
592        self.assertEqual(impl.py_func(), impl())
593
594    def test_iter_none(self):
595        @njit
596        def impl():
597            l = List()
598            l.append(None)
599            l.append(None)
600            l.append(None)
601            count = 0
602            for i in l:
603                count += 1
604            return count
605
606        self.assertEqual(impl.py_func(), impl())
607
608    def test_none_typed_method_fails(self):
609        """ Test that unsupported operations on List[None] raise. """
610        def generate_function(line1, line2):
611            context = {}
612            exec(dedent("""
613                from numba.typed import List
614                def bar():
615                    lst = List()
616                    {}
617                    {}
618                """.format(line1, line2)), context)
619            return njit(context["bar"])
620        for line1, line2 in (
621                ("lst.append(None)", "lst.pop()"),
622                ("lst.append(None)", "del lst[0]"),
623                ("lst.append(None)", "lst.count(None)"),
624                ("lst.append(None)", "lst.index(None)"),
625                ("lst.append(None)", "lst.insert(0, None)"),
626                (""                , "lst.insert(0, None)"),
627                ("lst.append(None)", "lst.clear()"),
628                ("lst.append(None)", "lst.copy()"),
629                ("lst.append(None)", "lst.extend([None])"),
630                ("",                 "lst.extend([None])"),
631                ("lst.append(None)", "lst.remove(None)"),
632                ("lst.append(None)", "lst.reverse()"),
633                ("lst.append(None)", "None in lst"),
634        ):
635            with self.assertRaises(TypingError) as raises:
636                foo = generate_function(line1, line2)
637                foo()
638            self.assertIn(
639                "method support for List[None] is limited",
640                str(raises.exception),
641            )
642
643
644class TestAllocation(MemoryLeakMixin, TestCase):
645
646    def test_allocation(self):
647        # kwarg version
648        for i in range(16):
649            tl = List.empty_list(types.int32, allocated=i)
650            self.assertEqual(tl._allocated(), i)
651
652        # posarg version
653        for i in range(16):
654            tl = List.empty_list(types.int32, i)
655            self.assertEqual(tl._allocated(), i)
656
657    def test_allocation_njit(self):
658        # kwarg version
659        @njit
660        def foo(i):
661            tl = List.empty_list(types.int32, allocated=i)
662            return tl._allocated()
663
664        for j in range(16):
665            self.assertEqual(foo(j), j)
666
667        # posarg version
668        @njit
669        def foo(i):
670            tl = List.empty_list(types.int32, i)
671            return tl._allocated()
672
673        for j in range(16):
674            self.assertEqual(foo(j), j)
675
676    def test_growth_and_shrinkage(self):
677        tl = List.empty_list(types.int32)
678        growth_before = {0: 0, 4:4, 8:8, 16:16}
679        growth_after = {0: 4, 4:8, 8:16, 16:25}
680        for i in range(17):
681            if i in growth_before:
682                self.assertEqual(growth_before[i], tl._allocated())
683            tl.append(i)
684            if i in growth_after:
685                self.assertEqual(growth_after[i], tl._allocated())
686
687        shrink_before = {17: 25, 12:25, 9:18, 6:12, 4:8, 3:6, 2:5, 1:4}
688        shrink_after = {17: 25, 12:18, 9:12, 6:8, 4:6, 3:5, 2:4, 1:0}
689        for i in range(17, 0, -1):
690            if i in shrink_before:
691                self.assertEqual(shrink_before[i], tl._allocated())
692            tl.pop()
693            if i in shrink_after:
694                self.assertEqual(shrink_after[i], tl._allocated())
695
696
697class TestExtend(MemoryLeakMixin, TestCase):
698
699    def test_extend_other(self):
700        @njit
701        def impl(other):
702            l = List.empty_list(types.int32)
703            for x in range(10):
704                l.append(x)
705            l.extend(other)
706            return l
707
708        other = List.empty_list(types.int32)
709        for x in range(10):
710            other.append(x)
711
712        expected = impl.py_func(other)
713        got = impl(other)
714        self.assertEqual(expected, got)
715
716    def test_extend_self(self):
717        @njit
718        def impl():
719            l = List.empty_list(types.int32)
720            for x in range(10):
721                l.append(x)
722            l.extend(l)
723            return l
724
725        expected = impl.py_func()
726        got = impl()
727        self.assertEqual(expected, got)
728
729    def test_extend_tuple(self):
730        @njit
731        def impl():
732            l = List.empty_list(types.int32)
733            for x in range(10):
734                l.append(x)
735            l.extend((100,200,300))
736            return l
737
738        expected = impl.py_func()
739        got = impl()
740        self.assertEqual(expected, got)
741
742    def test_extend_single_value_container(self):
743        @njit
744        def impl():
745            l = List()
746            l.extend((100,))
747            return l
748
749        expected = impl.py_func()
750        got = impl()
751        self.assertEqual(expected, got)
752
753    def test_extend_empty_unrefined(self):
754        # Extending an unrefined list with an empty iterable doesn't work in a
755        # jit compiled function as the list remains untyped.
756        l = List()
757        l.extend(tuple())
758        self.assertEqual(len(l), 0)
759        self.assertFalse(l._typed)
760
761    def test_extend_empty_refiend(self):
762        # Extending a refined list with an empty iterable doesn't work in a
763        # jit compiled function as the (empty) argument can't be typed
764        l = List((1,))
765        l.extend(tuple())
766        self.assertEqual(len(l), 1)
767        self.assertTrue(l._typed)
768
769
770@njit
771def cmp(a, b):
772    return a < b, a <= b, a == b, a != b, a >= b, a > b
773
774
775class TestComparisons(MemoryLeakMixin, TestCase):
776
777    def _cmp_dance(self, expected, pa, pb, na, nb):
778        # interpreter with regular list
779        self.assertEqual(cmp.py_func(pa, pb), expected)
780
781        # interpreter with typed-list
782        py_got = cmp.py_func(na, nb)
783        self.assertEqual(py_got, expected)
784
785        # compiled with typed-list
786        jit_got = cmp(na, nb)
787        self.assertEqual(jit_got, expected)
788
789    def test_empty_vs_empty(self):
790        pa, pb = [], []
791        na, nb = to_tl(pa), to_tl(pb)
792        expected = False, True, True, False, True, False
793        self._cmp_dance(expected, pa, pb, na, nb)
794
795    def test_empty_vs_singleton(self):
796        pa, pb = [], [0]
797        na, nb = to_tl(pa), to_tl(pb)
798        expected = True, True, False, True, False, False
799        self._cmp_dance(expected, pa, pb, na, nb)
800
801    def test_singleton_vs_empty(self):
802        pa, pb = [0], []
803        na, nb = to_tl(pa), to_tl(pb)
804        expected = False, False, False, True, True, True
805        self._cmp_dance(expected, pa, pb, na, nb)
806
807    def test_singleton_vs_singleton_equal(self):
808        pa, pb = [0], [0]
809        na, nb = to_tl(pa), to_tl(pb)
810        expected = False, True, True, False, True, False
811        self._cmp_dance(expected, pa, pb, na, nb)
812
813    def test_singleton_vs_singleton_less_than(self):
814        pa, pb = [0], [1]
815        na, nb = to_tl(pa), to_tl(pb)
816        expected = True, True, False, True, False, False
817        self._cmp_dance(expected, pa, pb, na, nb)
818
819    def test_singleton_vs_singleton_greater_than(self):
820        pa, pb = [1], [0]
821        na, nb = to_tl(pa), to_tl(pb)
822        expected = False, False, False, True, True, True
823        self._cmp_dance(expected, pa, pb, na, nb)
824
825    def test_equal(self):
826        pa, pb = [1, 2, 3], [1, 2, 3]
827        na, nb = to_tl(pa), to_tl(pb)
828        expected = False, True, True, False, True, False
829        self._cmp_dance(expected, pa, pb, na, nb)
830
831    def test_first_shorter(self):
832        pa, pb = [1, 2], [1, 2, 3]
833        na, nb = to_tl(pa), to_tl(pb)
834        expected = True, True, False, True, False, False
835        self._cmp_dance(expected, pa, pb, na, nb)
836
837    def test_second_shorter(self):
838        pa, pb = [1, 2, 3], [1, 2]
839        na, nb = to_tl(pa), to_tl(pb)
840        expected = False, False, False, True, True, True
841        self._cmp_dance(expected, pa, pb, na, nb)
842
843    def test_first_less_than(self):
844        pa, pb = [1, 2, 2], [1, 2, 3]
845        na, nb = to_tl(pa), to_tl(pb)
846        expected = True, True, False, True, False, False
847        self._cmp_dance(expected, pa, pb, na, nb)
848
849    def test_first_greater_than(self):
850        pa, pb = [1, 2, 3], [1, 2, 2]
851        na, nb = to_tl(pa), to_tl(pb)
852        expected = False, False, False, True, True, True
853        self._cmp_dance(expected, pa, pb, na, nb)
854
855    def test_equals_non_list(self):
856        l = to_tl([1, 2, 3])
857        self.assertFalse(any(cmp.py_func(l, 1)))
858        self.assertFalse(any(cmp(l, 1)))
859
860
861class TestListInferred(TestCase):
862
863    def test_simple_refine_append(self):
864        @njit
865        def foo():
866            l = List()
867            l.append(1)
868            return l
869
870        expected = foo.py_func()
871        got = foo()
872        self.assertEqual(expected, got)
873        self.assertEqual(list(got), [1])
874        self.assertEqual(typeof(got).item_type, typeof(1))
875
876    def test_simple_refine_insert(self):
877        @njit
878        def foo():
879            l = List()
880            l.insert(0, 1)
881            return l
882
883        expected = foo.py_func()
884        got = foo()
885        self.assertEqual(expected, got)
886        self.assertEqual(list(got), [1])
887        self.assertEqual(typeof(got).item_type, typeof(1))
888
889    def test_refine_extend_list(self):
890        @njit
891        def foo():
892            a = List()
893            b = List()
894            for i in range(3):
895                b.append(i)
896            a.extend(b)
897            return a
898
899        expected = foo.py_func()
900        got = foo()
901        self.assertEqual(expected, got)
902        self.assertEqual(list(got), [0, 1, 2])
903        self.assertEqual(typeof(got).item_type, typeof(1))
904
905    def test_refine_extend_set(self):
906        @njit
907        def foo():
908            l = List()
909            l.extend((0, 1, 2))
910            return l
911
912        expected = foo.py_func()
913        got = foo()
914        self.assertEqual(expected, got)
915        self.assertEqual(list(got), [0, 1, 2])
916        self.assertEqual(typeof(got).item_type, typeof(1))
917
918    def test_refine_list_extend_iter(self):
919        @njit
920        def foo():
921            l = List()
922            d = Dict()
923            d[0] = 0
924            # d.keys() provides a DictKeysIterableType
925            l.extend(d.keys())
926            return l
927
928        got = foo()
929        self.assertEqual(0, got[0])
930
931
932class TestListRefctTypes(MemoryLeakMixin, TestCase):
933
934    def test_str_item(self):
935        @njit
936        def foo():
937            l = List.empty_list(types.unicode_type)
938            for s in ("a", "ab", "abc", "abcd"):
939                l.append(s)
940            return l
941
942        l = foo()
943        expected = ["a", "ab", "abc", "abcd"]
944        for i, s in enumerate(expected):
945            self.assertEqual(l[i], s)
946        self.assertEqual(list(l), expected)
947        # Test insert replacement
948        l[3] = 'uxyz'
949        self.assertEqual(l[3], 'uxyz')
950        # Test list growth
951        nelem = 100
952        for i in range(4, nelem):
953            l.append(str(i))
954            self.assertEqual(l[i], str(i))
955
956    def test_str_item_refcount_replace(self):
957        @njit
958        def foo():
959            # use some tricks to make ref-counted unicode
960            i, j = 'ab', 'c'
961            a = i + j
962            m, n = 'zy', 'x'
963            z = m + n
964            l = List.empty_list(types.unicode_type)
965            l.append(a)
966            # This *should* dec' a and inc' z thus tests that items that are
967            # replaced are also dec'ed.
968            l[0] = z
969            ra, rz = get_refcount(a), get_refcount(z)
970            return l, ra, rz
971
972        l, ra, rz = foo()
973        self.assertEqual(l[0], "zyx")
974        self.assertEqual(ra, 1)
975        self.assertEqual(rz, 2)
976
977    def test_dict_as_item_in_list(self):
978        @njit
979        def foo():
980            l = List.empty_list(Dict.empty(int32, int32))
981            d = Dict.empty(int32, int32)
982            d[0] = 1
983            # This increments the refcount for d
984            l.append(d)
985            return get_refcount(d)
986
987        c = foo()
988        self.assertEqual(2, c)
989
990    def test_dict_as_item_in_list_multi_refcount(self):
991        @njit
992        def foo():
993            l = List.empty_list(Dict.empty(int32, int32))
994            d = Dict.empty(int32, int32)
995            d[0] = 1
996            # This increments the refcount for d, twice
997            l.append(d)
998            l.append(d)
999            return get_refcount(d)
1000
1001        c = foo()
1002        self.assertEqual(3, c)
1003
1004    def test_list_as_value_in_dict(self):
1005        @njit
1006        def foo():
1007            d = Dict.empty(int32, List.empty_list(int32))
1008            l = List.empty_list(int32)
1009            l.append(0)
1010            # This increments the refcount for l
1011            d[0] = l
1012            return get_refcount(l)
1013
1014        c = foo()
1015        self.assertEqual(2, c)
1016
1017    def test_list_as_item_in_list(self):
1018        nested_type = types.ListType(types.int32)
1019
1020        @njit
1021        def foo():
1022            la = List.empty_list(nested_type)
1023            lb = List.empty_list(types.int32)
1024            lb.append(1)
1025            la.append(lb)
1026            return la
1027
1028        expected = foo.py_func()
1029        got = foo()
1030        self.assertEqual(expected, got)
1031
1032    def test_array_as_item_in_list(self):
1033        nested_type = types.Array(types.float64, 1, 'C')
1034
1035        @njit
1036        def foo():
1037            l = List.empty_list(nested_type)
1038            a = np.zeros((1,))
1039            l.append(a)
1040            return l
1041
1042        expected = foo.py_func()
1043        got = foo()
1044        # Need to compare the nested arrays
1045        self.assertTrue(np.all(expected[0] == got[0]))
1046
1047    def test_array_pop_from_single_value_list(self):
1048        @njit
1049        def foo():
1050            l = List((np.zeros((1,)),))
1051            l.pop()
1052            return l
1053
1054        expected, got = foo.py_func(), foo()
1055        # Need to compare the nested arrays
1056        self.assertEqual(len(expected), 0)
1057        self.assertEqual(len(got), 0)
1058        # FIXME comparison of empty array-typed lists fails
1059        # self.assertEqual(expected, got)
1060
1061    def test_5264(self):
1062        # Test the reproducer from #5264 and make sure it doesn't segfault
1063        float_array = types.float64[:]
1064        l = List.empty_list(float_array)
1065        l.append(np.ones(3,dtype=np.float64))
1066        l.pop()
1067        self.assertEqual(0, len(l))
1068
1069    def test_jitclass_as_item_in_list(self):
1070
1071        spec = [
1072            ('value', int32),               # a simple scalar field
1073            ('array', float32[:]),          # an array field
1074        ]
1075
1076        @jitclass(spec)
1077        class Bag(object):
1078            def __init__(self, value):
1079                self.value = value
1080                self.array = np.zeros(value, dtype=np.float32)
1081
1082            @property
1083            def size(self):
1084                return self.array.size
1085
1086            def increment(self, val):
1087                for i in range(self.size):
1088                    self.array[i] += val
1089                return self.array
1090
1091        @njit
1092        def foo():
1093            l = List()
1094            l.append(Bag(21))
1095            l.append(Bag(22))
1096            l.append(Bag(23))
1097            return l
1098
1099        expected = foo.py_func()
1100        got = foo()
1101
1102        def bag_equal(one, two):
1103            # jitclasses couldn't override __eq__ at time of writing
1104            self.assertEqual(one.value, two.value)
1105            np.testing.assert_allclose(one.array, two.array)
1106
1107        [bag_equal(a, b) for a, b in zip(expected, got)]
1108
1109    def test_4960(self):
1110        # Test the reproducer from #4960 and make sure it doesn't segfault
1111        @jitclass([('value', int32)])
1112        class Simple(object):
1113            def __init__(self, value):
1114                self.value = value
1115
1116        @njit
1117        def foo():
1118            l = List((Simple(23),Simple(24)))
1119            l.pop()
1120            return l
1121
1122        l = foo()
1123        self.assertEqual(1, len(l))
1124
1125    def test_storage_model_mismatch(self):
1126        # https://github.com/numba/numba/issues/4520
1127        # check for storage model mismatch in refcount ops generation
1128        lst = List()
1129        ref = [
1130            ("a", True, "a"),
1131            ("b", False, "b"),
1132            ("c", False, "c"),
1133        ]
1134        # populate
1135        for x in ref:
1136            lst.append(x)
1137        # test
1138        for i, x in enumerate(ref):
1139            self.assertEqual(lst[i], ref[i])
1140
1141    def test_equals_on_list_with_dict_for_equal_lists(self):
1142        # https://github.com/numba/numba/issues/4879
1143        a, b = List(), Dict()
1144        b["a"] = 1
1145        a.append(b)
1146
1147        c, d = List(), Dict()
1148        d["a"] = 1
1149        c.append(d)
1150
1151        self.assertEqual(a, c)
1152
1153    def test_equals_on_list_with_dict_for_unequal_dicts(self):
1154        # https://github.com/numba/numba/issues/4879
1155        a, b = List(), Dict()
1156        b["a"] = 1
1157        a.append(b)
1158
1159        c, d = List(), Dict()
1160        d["a"] = 2
1161        c.append(d)
1162
1163        self.assertNotEqual(a, c)
1164
1165    def test_equals_on_list_with_dict_for_unequal_lists(self):
1166        # https://github.com/numba/numba/issues/4879
1167        a, b = List(), Dict()
1168        b["a"] = 1
1169        a.append(b)
1170
1171        c, d, e = List(), Dict(), Dict()
1172        d["a"] = 1
1173        e["b"] = 2
1174        c.append(d)
1175        c.append(e)
1176
1177        self.assertNotEqual(a, c)
1178
1179
1180class TestListSort(MemoryLeakMixin, TestCase):
1181    def setUp(self):
1182        super(TestListSort, self).setUp()
1183        np.random.seed(0)
1184
1185    def make(self, ctor, data):
1186        lst = ctor()
1187        lst.extend(data)
1188        return lst
1189
1190    def make_both(self, data):
1191        return {
1192            'py': self.make(list, data),
1193            'nb': self.make(List, data),
1194        }
1195
1196    def test_sort_no_args(self):
1197        def udt(lst):
1198            lst.sort()
1199            return lst
1200
1201        for nelem in [13, 29, 127]:
1202            my_lists = self.make_both(np.random.randint(0, nelem, nelem))
1203            self.assertEqual(list(udt(my_lists['nb'])), udt(my_lists['py']))
1204
1205    def test_sort_all_args(self):
1206        def udt(lst, key, reverse):
1207            lst.sort(key=key, reverse=reverse)
1208            return lst
1209
1210        possible_keys = [
1211            lambda x: -x,           # negative
1212            lambda x: 1 / (1 + x),  # make float
1213            lambda x: (x, -x),      # tuple
1214            lambda x: x,            # identity
1215        ]
1216        possible_reverse = [True, False]
1217        for key, reverse in product(possible_keys, possible_reverse):
1218            my_lists = self.make_both(np.random.randint(0, 100, 23))
1219            msg = "case for key={} reverse={}".format(key, reverse)
1220            self.assertEqual(
1221                list(udt(my_lists['nb'], key=key, reverse=reverse)),
1222                udt(my_lists['py'], key=key, reverse=reverse),
1223                msg=msg,
1224            )
1225
1226    def test_sort_dispatcher_key(self):
1227        def udt(lst, key):
1228            lst.sort(key=key)
1229            return lst
1230
1231        my_lists = self.make_both(np.random.randint(0, 100, 31))
1232        py_key = lambda x: x + 1
1233        nb_key = njit(lambda x: x + 1)
1234        # test typedlist with jitted function
1235        self.assertEqual(
1236            list(udt(my_lists['nb'], key=nb_key)),
1237            udt(my_lists['py'], key=py_key),
1238        )
1239        # test typedlist with and without jitted function
1240        self.assertEqual(
1241            list(udt(my_lists['nb'], key=nb_key)),
1242            list(udt(my_lists['nb'], key=py_key)),
1243        )
1244
1245    def test_sort_in_jit_w_lambda_key(self):
1246        @njit
1247        def udt(lst):
1248            lst.sort(key=lambda x: -x)
1249            return lst
1250
1251        lst = self.make(List, np.random.randint(0, 100, 31))
1252        self.assertEqual(udt(lst), udt.py_func(lst))
1253
1254    def test_sort_in_jit_w_global_key(self):
1255        @njit
1256        def keyfn(x):
1257            return -x
1258
1259        @njit
1260        def udt(lst):
1261            lst.sort(key=keyfn)
1262            return lst
1263
1264        lst = self.make(List, np.random.randint(0, 100, 31))
1265        self.assertEqual(udt(lst), udt.py_func(lst))
1266
1267    def test_sort_on_arrays(self):
1268        @njit
1269        def foo(lst):
1270            lst.sort(key=lambda arr: np.sum(arr))
1271            return lst
1272
1273        arrays = [np.random.random(3) for _ in range(10)]
1274        my_lists = self.make_both(arrays)
1275        self.assertEqual(
1276            list(foo(my_lists['nb'])),
1277            foo.py_func(my_lists['py']),
1278        )
1279
1280
1281class TestImmutable(MemoryLeakMixin, TestCase):
1282
1283    def test_is_immutable(self):
1284        @njit
1285        def foo():
1286            l = List()
1287            l.append(1)
1288            return l._is_mutable()
1289        self.assertTrue(foo())
1290        self.assertTrue(foo.py_func())
1291
1292    def test_make_immutable_is_immutable(self):
1293        @njit
1294        def foo():
1295            l = List()
1296            l.append(1)
1297            l._make_immutable()
1298            return l._is_mutable()
1299        self.assertFalse(foo())
1300        self.assertFalse(foo.py_func())
1301
1302    def test_length_still_works_when_immutable(self):
1303        @njit
1304        def foo():
1305            l = List()
1306            l.append(1)
1307            l._make_immutable()
1308            return len(l),l._is_mutable()
1309        length, mutable = foo()
1310        self.assertEqual(length, 1)
1311        self.assertFalse(mutable)
1312
1313    def test_getitem_still_works_when_immutable(self):
1314        @njit
1315        def foo():
1316            l = List()
1317            l.append(1)
1318            l._make_immutable()
1319            return l[0], l._is_mutable()
1320        test_item, mutable = foo()
1321        self.assertEqual(test_item, 1)
1322        self.assertFalse(mutable)
1323
1324    def test_append_fails(self):
1325        self.disable_leak_check()
1326
1327        @njit
1328        def foo():
1329            l = List()
1330            l.append(1)
1331            l._make_immutable()
1332            l.append(1)
1333
1334        for func in (foo, foo.py_func):
1335            with self.assertRaises(ValueError) as raises:
1336                func()
1337            self.assertIn(
1338                'list is immutable',
1339                str(raises.exception),
1340            )
1341
1342    def test_mutation_fails(self):
1343        """ Test that any attempt to mutate an immutable typed list fails. """
1344        self.disable_leak_check()
1345
1346        def generate_function(line):
1347            context = {}
1348            exec(dedent("""
1349                from numba.typed import List
1350                def bar():
1351                    lst = List()
1352                    lst.append(1)
1353                    lst._make_immutable()
1354                    {}
1355                """.format(line)), context)
1356            return njit(context["bar"])
1357        for line in ("lst.append(0)",
1358                     "lst[0] = 0",
1359                     "lst.pop()",
1360                     "del lst[0]",
1361                     "lst.extend((0,))",
1362                     "lst.insert(0, 0)",
1363                     "lst.clear()",
1364                     "lst.reverse()",
1365                     "lst.sort()",
1366                     ):
1367            foo = generate_function(line)
1368            for func in (foo, foo.py_func):
1369                with self.assertRaises(ValueError) as raises:
1370                    func()
1371                self.assertIn(
1372                    "list is immutable",
1373                    str(raises.exception),
1374                )
1375
1376
1377class TestListFromIter(MemoryLeakMixin, TestCase):
1378
1379    def test_simple_iterable_types(self):
1380        """Test all simple iterables that a List can be constructed from."""
1381
1382        def generate_function(line):
1383            context = {}
1384            code = dedent("""
1385                from numba.typed import List
1386                def bar():
1387                    {}
1388                    return l
1389                """).format(line)
1390            exec(code, context)
1391            return njit(context["bar"])
1392        for line in ("l = List([0, 1, 2])",
1393                     "l = List(range(3))",
1394                     "l = List(List([0, 1, 2]))",
1395                     "l = List((0, 1, 2))",
1396                     "l = List(set([0, 1, 2]))",
1397                     ):
1398            foo = generate_function(line)
1399            cf_received, py_received = foo(), foo.py_func()
1400            for result in (cf_received, py_received):
1401                for i in range(3):
1402                    self.assertEqual(i, result[i])
1403
1404    def test_unicode(self):
1405        """Test that a List can be created from a unicode string."""
1406        @njit
1407        def foo():
1408            l = List("abc")
1409            return l
1410        expected = List()
1411        for i in ("a", "b", "c"):
1412            expected.append(i)
1413        self.assertEqual(foo.py_func(), expected)
1414        self.assertEqual(foo(), expected)
1415
1416    def test_dict_iters(self):
1417        """Test that a List can be created from Dict iterators."""
1418
1419        def generate_function(line):
1420            context = {}
1421            code = dedent("""
1422                from numba.typed import List, Dict
1423                def bar():
1424                    d = Dict()
1425                    d[0], d[1], d[2] = "a", "b", "c"
1426                    {}
1427                    return l
1428                """).format(line)
1429            exec(code, context)
1430            return njit(context["bar"])
1431
1432        def generate_expected(values):
1433            expected = List()
1434            for i in values:
1435                expected.append(i)
1436            return expected
1437
1438        for line, values in (
1439                ("l = List(d)", (0, 1, 2)),
1440                ("l = List(d.keys())", (0, 1, 2)),
1441                ("l = List(d.values())", ("a", "b", "c")),
1442                ("l = List(d.items())", ((0, "a"), (1, "b"), (2, "c"))),
1443        ):
1444            foo, expected = generate_function(line), generate_expected(values)
1445            for func in (foo, foo.py_func):
1446                self.assertEqual(func(), expected)
1447
1448    def test_ndarray_scalar(self):
1449
1450        @njit
1451        def foo():
1452            return List(np.ones(3))
1453
1454        expected = List()
1455        for i in range(3):
1456            expected.append(1)
1457
1458        self.assertEqual(expected, foo())
1459        self.assertEqual(expected, foo.py_func())
1460
1461    def test_ndarray_oned(self):
1462
1463        @njit
1464        def foo():
1465            return List(np.array(1))
1466
1467        expected = List()
1468        expected.append(1)
1469
1470        self.assertEqual(expected, foo())
1471        self.assertEqual(expected, foo.py_func())
1472
1473    def test_ndarray_twod(self):
1474
1475        @njit
1476        def foo(x):
1477            return List(x)
1478
1479        carr = np.array([[1, 2], [3, 4]])
1480        farr = np.asfortranarray(carr)
1481        aarr = np.arange(8).reshape((2, 4))[:, ::2]
1482
1483        for layout, arr in zip('CFA', (carr, farr, aarr)):
1484            self.assertEqual(typeof(arr).layout, layout)
1485            expected = List()
1486            expected.append(arr[0, :])
1487            expected.append(arr[1, :])
1488            received = foo(arr)
1489
1490            np.testing.assert_equal(expected[0], received[0])
1491            np.testing.assert_equal(expected[1], received[1])
1492
1493            pyreceived = foo.py_func(arr)
1494
1495            np.testing.assert_equal(expected[0], pyreceived[0])
1496            np.testing.assert_equal(expected[1], pyreceived[1])
1497
1498    def test_exception_on_plain_int(self):
1499        @njit
1500        def foo():
1501            l = List(23)
1502            return l
1503
1504        with self.assertRaises(TypingError) as raises:
1505            foo()
1506        self.assertIn(
1507            "List() argument must be iterable",
1508            str(raises.exception),
1509        )
1510
1511        with self.assertRaises(TypeError) as raises:
1512            List(23)
1513        self.assertIn(
1514            "List() argument must be iterable",
1515            str(raises.exception),
1516        )
1517
1518    def test_exception_on_inhomogeneous_tuple(self):
1519        @njit
1520        def foo():
1521            l = List((1, 1.0))
1522            return l
1523
1524        with self.assertRaises(TypingError) as raises:
1525            foo()
1526        self.assertIn(
1527            "List() argument must be iterable",
1528            str(raises.exception),
1529        )
1530
1531        with self.assertRaises(TypingError) as raises:
1532            List((1, 1.0))
1533        # FIXME this bails with a length casting error when we attempt to
1534        # append 1.0 to an int typed list.
1535
1536    def test_exception_on_too_many_args(self):
1537        @njit
1538        def foo():
1539            l = List((0, 1, 2), (3, 4, 5))
1540            return l
1541
1542        with self.assertRaises(TypingError) as raises:
1543            foo()
1544        self.assertIn(
1545            "List() expected at most 1 argument, got 2",
1546            str(raises.exception),
1547        )
1548
1549        with self.assertRaises(TypeError) as raises:
1550            List((0, 1, 2), (3, 4, 5))
1551        self.assertIn(
1552            "List() expected at most 1 argument, got 2",
1553            str(raises.exception),
1554        )
1555
1556        @njit
1557        def foo():
1558            l = List((0, 1, 2), (3, 4, 5), (6, 7, 8))
1559            return l
1560
1561        with self.assertRaises(TypingError) as raises:
1562            foo()
1563        self.assertIn(
1564            "List() expected at most 1 argument, got 3",
1565            str(raises.exception),
1566        )
1567
1568        with self.assertRaises(TypeError) as raises:
1569            List((0, 1, 2), (3, 4, 5), (6, 7, 8))
1570        self.assertIn(
1571            "List() expected at most 1 argument, got 3",
1572            str(raises.exception),
1573        )
1574
1575    def test_exception_on_kwargs(self):
1576        @njit
1577        def foo():
1578            l = List(iterable=(0, 1, 2))
1579            return l
1580
1581        with self.assertRaises(TypingError) as raises:
1582            foo()
1583        self.assertIn(
1584            "List() takes no keyword arguments",
1585            str(raises.exception),
1586        )
1587
1588        with self.assertRaises(TypeError) as raises:
1589            List(iterable=(0, 1, 2))
1590        self.assertIn(
1591            "List() takes no keyword arguments",
1592            str(raises.exception),
1593        )
1594