Repository: numba/numba
Pull request: Fix numba.typed.List extend for singleton and empty iterable
Fixes #5152

<!--

Thanks for wanting to contribute to Numba :)

First, if you need some help or want to chat to the core developers, please
visit https://gitter.im/numba/numba for real time chat or post to the Numba
mailing list https://groups.google.com/a/continuum.io/forum/#!forum/numba-users.

Here's some guidelines to help the review process go smoothly.

0. Please write a description in this text box of the changes that are being
   made.

1. Please ensure that you have written units tests for the changes made/features
   added.

2. If you are closing an issue please use one of the automatic closing words as
   noted here: https://help.github.com/articles/closing-issues-using-keywords/

3. If your pull request is not ready for review but you want to make use of the
   continuous integration testing facilities please label it with `[WIP]` and
   then remove the label when you'd like it to be reviewed.

4. Once review has taken place please do not add features or make changes out of
   the scope of those requested by the reviewer (doing this just add delays as
   already reviewed code ends up having to be re-reviewed/it is hard to tell
   what is new etc!). Further, please do not rebase your branch on master/force
   push/rewrite history, doing any of these causes the context of any comments
   made by reviewers to be lost. If conflicts occur against master they should
   be resolved by merging master into the branch used for making the pull
   request.

Many thanks in advance for your cooperation!

-->

Problem statement:
typed list fails to refine with tuple in interpreter
Reproducer:

```python
from numba import typed

l = typed.List()
l.extend((1,))
```

Traceback:

```pytb
Traceback (most recent call last):
  File "/Users/vhaenel/git/numba/numba/typeinfer.py", line 148, in propagate
    constraint(typeinfer)
  File "/Users/vhaenel/git/numba/numba/typeinfer.py", line 486, in __call__
    self.resolve(typeinfer, typevars, fnty)
  File "/Users/vhaenel/git/numba/numba/typeinfer.py", line 506, in resolve
    sig = typeinfer.resolve_call(fnty, pos_args, kw_args)
  File "/Users/vhaenel/git/numba/numba/typeinfer.py", line 1440, in resolve_call
    return self.context.resolve_function_type(fnty, pos_args, kw_args)
  File "/Users/vhaenel/git/numba/numba/typing/context.py", line 216, in resolve_function_type
    raise last_exception
  File "/Users/vhaenel/git/numba/numba/typing/context.py", line 199, in resolve_function_type
    res = self._resolve_user_function_type(func, args, kws)
  File "/Users/vhaenel/git/numba/numba/typing/context.py", line 251, in _resolve_user_function_type
    return func.get_call_type(self, args, kws)
  File "/Users/vhaenel/git/numba/numba/types/functions.py", line 217, in get_call_type
    out = template.apply(args, kws)
  File "/Users/vhaenel/git/numba/numba/typing/templates.py", line 245, in apply
    sig = generic(args, kws)
  File "/Users/vhaenel/git/numba/numba/typing/templates.py", line 806, in generic
    sig = self._get_signature(self.context, fnty, args, kws)
  File "/Users/vhaenel/git/numba/numba/typing/templates.py", line 757, in _get_signature
    sig = fnty.get_call_type(typingctx, args, kws)
  File "/Users/vhaenel/git/numba/numba/types/functions.py", line 150, in get_call_type
    failures.raise_error()
  File "/Users/vhaenel/git/numba/numba/types/functions.py", line 79, in raise_error
    raise errors.TypingError(self.format())
numba.errors.TypingError: Invalid use of Function(<function impl_extend at 0x1152bddd0>) with argument(s) of type(s): (ListType[int64], Tuple())
 * parameterized
In definition 0:
    TypingError: extend argument must be iterable
    raised from /Users/vhaenel/git/numba/numba/listobject.py:880
In definition 1:
    TypingError: extend argument must be iterable
    raised from /Users/vhaenel/git/numba/numba/listobject.py:880
This error is usually caused by passing an argument of a type that is unsupported by the named function.
[1] During: resolving callee type: BoundFunction((<class 'numba.types.containers.ListType'>, 'extend') for ListType[int64])
[2] During: typing of call at /Users/vhaenel/git/numba/numba/typed/typedlist.py (82)


The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "foo/foo107.py", line 4, in <module>
    l.extend((1,))
  File "/Users/vhaenel/git/numba/numba/typed/typedlist.py", line 301, in extend
    return _extend(self, iterable[1:])
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 401, in _compile_for_args
    error_rewrite(e, 'typing')
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 342, in error_rewrite
    raise e
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 353, in _compile_for_args
    return self.compile(tuple(argtypes))
  File "/Users/vhaenel/git/numba/numba/compiler_lock.py", line 32, in _acquire_compile_lock
    return func(*args, **kwargs)
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 768, in compile
    cres = self._compiler.compile(args, return_type)
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 81, in compile
    raise retval
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 91, in _compile_cached
    retval = self._compile_core(args, return_type)
  File "/Users/vhaenel/git/numba/numba/dispatcher.py", line 109, in _compile_core
    pipeline_class=self.pipeline_class)
  File "/Users/vhaenel/git/numba/numba/compiler.py", line 551, in compile_extra
    return pipeline.compile_extra(func)
  File "/Users/vhaenel/git/numba/numba/compiler.py", line 331, in compile_extra
    return self._compile_bytecode()
  File "/Users/vhaenel/git/numba/numba/compiler.py", line 393, in _compile_bytecode
    return self._compile_core()
  File "/Users/vhaenel/git/numba/numba/compiler.py", line 373, in _compile_core
    raise e
  File "/Users/vhaenel/git/numba/numba/compiler.py", line 364, in _compile_core
    pm.run(self.state)
  File "/Users/vhaenel/git/numba/numba/compiler_machinery.py", line 347, in run
    raise patched_exception
  File "/Users/vhaenel/git/numba/numba/compiler_machinery.py", line 338, in run
    self._runPass(idx, pass_inst, state)
  File "/Users/vhaenel/git/numba/numba/compiler_lock.py", line 32, in _acquire_compile_lock
    return func(*args, **kwargs)
  File "/Users/vhaenel/git/numba/numba/compiler_machinery.py", line 302, in _runPass
    mutated |= check(pss.run_pass, internal_state)
  File "/Users/vhaenel/git/numba/numba/compiler_machinery.py", line 275, in check
    mangled = func(compiler_state)
  File "/Users/vhaenel/git/numba/numba/typed_passes.py", line 95, in run_pass
    raise_errors=self._raise_errors)
  File "/Users/vhaenel/git/numba/numba/typed_passes.py", line 67, in type_inference_stage
    infer.propagate(raise_errors=raise_errors)
  File "/Users/vhaenel/git/numba/numba/typeinfer.py", line 985, in propagate
    raise errors[0]
numba.errors.TypingError: Failed in nopython mode pipeline (step: nopython frontend)
Invalid use of Function(<function impl_extend at 0x1152bddd0>) with argument(s) of type(s): (ListType[int64], Tuple())
 * parameterized
In definition 0:
    TypingError: extend argument must be iterable
    raised from /Users/vhaenel/git/numba/numba/listobject.py:880
In definition 1:
    TypingError: extend argument must be iterable
    raised from /Users/vhaenel/git/numba/numba/listobject.py:880
This error is usually caused by passing an argument of a type that is unsupported by the named function.
[1] During: resolving callee type: BoundFunction((<class 'numba.types.containers.ListType'>, 'extend') for ListType[int64])
[2] During: typing of call at /Users/vhaenel/git/numba/numba/typed/typedlist.py (82)


File "numba/typed/typedlist.py", line 82:
def _extend(l, iterable):
    return l.extend(iterable)
```

Hints from issue discussion:
It get's even worse, even though the error is raised, the `1` is still added to the list. So the operation succeeds, but throws a meaningless error message.
Has to be fixed here, to check if there is anything left in the iterable:

https://github.com/numba/numba/blob/master/numba/typed/typedlist.py#L364
This fails for empty tuples also:

```
In [1]: from numba.typed import List
l
In [2]: l = List()

In [3]: l.extend(tuple())
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-3-30d0fdf78642> in <module>
----> 1 l.extend(tuple())

~/git/numba/numba/typed/typedlist.py in extend(self, iterable)
    360             # type of the list. FIXME: this may be a problem if the iterable
    361             # can not be sliced.
--> 362             self._initialise_list(iterable[0])
    363             self.append(iterable[0])
    364             if len(iterable) > 1:

IndexError: tuple index out of range
```
Extending with an empty iterable doesn't work either.

```
In [6]: l = List()

In [7]: l = List((1,))

In [8]: l.extend(tuple())
```

Commit message: fix extending a refined list

A `numba.typed.List` that is refined failed to extend on an empty
iterable. This fixes that to be a NO-OP and includes tests.

Patch to review:
diff --git a/numba/tests/test_typedlist.py b/numba/tests/test_typedlist.py
index f43dabb1014..b0afeacf9b4 100644
--- a/numba/tests/test_typedlist.py
+++ b/numba/tests/test_typedlist.py
@@ -729,6 +729,33 @@ def impl():
         got = impl()
         self.assertEqual(expected, got)
 
+    def test_extend_singleton(self):
+        @njit
+        def impl():
+            l = List()
+            l.extend((100,))
+            return l
+
+        expected = impl.py_func()
+        got = impl()
+        self.assertEqual(expected, got)
+
+    def test_extend_empty_unrefined(self):
+        # Extending an unrefined list with an empty iterable doesn't work in a
+        # jit compiled function as the list remains untyped.
+        l = List()
+        l.extend(tuple())
+        self.assertEqual(len(l), 0)
+        self.assertFalse(l._typed)
+
+    def test_extend_empty_refiend(self):
+        # Extending a refined list with an empty iterable doesn't work in a
+        # jit compiled function as the (empty) argument can't be typed
+        l = List((1,))
+        l.extend(tuple())
+        self.assertEqual(len(l), 1)
+        self.assertTrue(l._typed)
+
 
 @njit
 def cmp(a, b):
diff --git a/numba/typed/typedlist.py b/numba/typed/typedlist.py
index 4f5b0dec235..31727c477dc 100644
--- a/numba/typed/typedlist.py
+++ b/numba/typed/typedlist.py
@@ -356,13 +356,24 @@ def pop(self, i=-1):
 
     def extend(self, iterable):
         if not self._typed:
+            iterable_length = len(iterable)
+            # Empty iterable, do nothing
+            if iterable_length == 0:
+                return self
             # Need to get the first element of the iterable to initialise the
             # type of the list. FIXME: this may be a problem if the iterable
             # can not be sliced.
             self._initialise_list(iterable[0])
             self.append(iterable[0])
-            return _extend(self, iterable[1:])
-        return _extend(self, iterable)
+            # Iterable has more values to extend from
+            if iterable_length > 1:
+                return _extend(self, iterable[1:])
+            else:
+                return self
+        elif len(iterable) == 0:
+            return self
+        else:
+            return _extend(self, iterable)
 
     def remove(self, item):
         return _remove(self, item)


Code review comments:
diff_hunk: @@ -729,6 +729,33 @@ def impl():
         got = impl()
         self.assertEqual(expected, got)
 
+    def test_extend_singleton(self):
path: numba/tests/test_typedlist.py
text: @user1:
Where's the singleton? Do you mean, "container holding single value"?

@author:
yes, I was under the impression, that the term 'singleton' could be used to describe such a construct, but perhaps I was mistaken. Is there something shorter than "container holding single value"?

@user1:
It seems, overwhelmingly, singleton refers to the singleton pattern, with the exception of tuple, https://docs.python.org/3/library/stdtypes.html#tuple.

@author:
Thanks for looking into this. So it seems that use of the term 'singleton' in this context is perhaps permissible. In any case to avoid any future ambiguities I think it will be best to rename the test, how about 'single_value_container'?

@user1:
Sounds good, thanks.

@author:
done