MAINT: Rewrite numpy.pad without concatenate (gh-11358)

* ENH: Add support for constant, edge, linear_ramp to new numpy.pad

Passes unit tests:
- TestConstant
- TestEdge
- TestZeroPadWidth
- TestLegacyVectorFunction
- TestNdarrayPadWidth
- TestUnicodeInput
- TestLinearRamp

* MAINT: Simplify diff / change order of functions

* MAINT: Revert to old handling of keyword-only arguments

* ENH: Add support for stat modes

* ENH: Add support for "reflect" mode

* MAINT: Remove _slice_column

* ENH: Add support for "symmetric" mode

* MAINT: Simplify mode "linear_ramp"

Creating the linear ramp as an array with 1-sized dimensions except
for the one given by `axis` allows implicit broadcasting to the needed
shape. This seems to be even a little bit faster that doing this by hand
and allows the simplicifaction of the algorithm.

Note: Profiling and optimization will be done again at a later stage.

* MAINT: Reorder arguments of a sum and fix typo

Addresses feedback raised in PR.

* ENH: Add support for "wrap" mode

This completes the first draft of the complete rewrite meaning all unit
tests should pass from this commit onwards.

* MAINT: Merge functions for "reflect" and "symmetric" mode

The set functions were nearly the same, apart from some index offsets.
Merging them reduces code duplication.

* TST: Add regression test for gh-11216

The rewrite in past commits fixed this bug.

* BUG: Fix edge case for _set_wrap_both when pad_amt contains 0.

And include test to protect against regression.

* MAINT: Simplify and optimize pad modes

Major changes & goals:

Don't deal with pad area in the front and back separately. This
modularity isn't needed and makes handling of the right edge more
awkward. All modes now deal with the left and right side at the same
time.

Move the creation of the linear ramps fully to its own function which
behaves like a vectorized version of linspace.

Separate calculation and application of the pad area where possible.
This means that _get_edges can be reused for _get_linear_ramps.

Combine _normalize_shape and _validate_lengths in a single function
which should handles common cases faster.

Add new mode "empty" which leaves the padded areas undefined.

Add documentation where it was missing.

* TST: Don't use np.empty in unit tests

* MAINT: Reorder workflow in numpy.pad and deal with empty dimensions

Only modes "constant" and "empty" can extend dimensions of size 0. Deal
with this edge case gracefully for all other modes either fail or
return empty array with padded non-zero dimensions.

Handle default values closer to their actual usage. And validate
keyword arguments that must be numbers.

* MAINT: Add small tweaks to control flow and documentation

* BUG: Ensure wrap mode works if right_pad is 0

* ENH: Use reduced region of interest for iterative padding

When padding multiple dimensions iteratively corner values are
unnecessarily overwritten multiple times. This function reduces the
working area for the first dimensions so that corners are excluded.

* MAINT: Restore original argument order in _slice_at_axis

* MAINT: Keep original error message of broadcast_to

* MAINT: Restore old behavior for non-number end_values.

* BENCH: Make the pad benchmark pagefault in setup

* ENH/TST: Preserve memory layout (order) of the input array

and add appropriate unit test.

* STY: Revert cosmetical changes to reduce diff

* MAINT: Pin dtype to float64 for np.pad's benchmarks

* MAINT: Remove redundant code path in _view_roi

* MAINT/TST: Provide proper error message for unsupported modes

and add appropriate unit test.

* STY: Keep docstrings consistent and fix typo.

* MAINT: Simplify logical workflow in pad

* MAINT: Remove dtype argument from _linear_ramp

The responsibility of rounding (but without type conversion) is not
really need in _linear_ramp and only makes it a little bit harder to
reason about.

* DOC: Add version tag to new argument "empty"

* MAINT: Default to C-order for padded arrays

unless the input is F-contiguous.

* MAINT: Name slice of original area consistently

for all arguments describing the same thing.

* STY: Reduce vertical space

* MAINT: Remove shape argument from _slice_at_axis

Simplifies calls to this function and the function itself.
Using `(...,)` instead should keep this unambiguous. This change is not
compatible with Python 2.7 which doesn't support this syntax outside
sequence slicing. If that is wanted one could use `(Ellipsis,)` instead.

* TST: Test if end_values of linear_ramp are exact

which was not given in the old implementation `_arange_ndarray`.

* DOC: Improve comments and wrap long line

* MAINT: Refactor index_pair to width_pair

Calling the right value an index is just plain wrong as it can't be used
as such.

* MAINT: Make _linear_ramp compatible with size=0

* MAINT: Don't rely on negative indices for slicing

Calculating the proper positive index of the start of the right pad area
makes it possible to omit the extra code paths for a width of 0. This
should make the code easier to reason about.

* MAINT: Skip calculation of right_stat if identical

If the input area for both sides is the same we don't need to calculate
it twice.

* TST: Adapt tests from gh-12789 to rewrite of pad

* TST: Add tests for mode "empty"

* TST: Test dtype persistence for all modes

* TST: Test exception for unsupported modes

* TST: Test repeated wrapping for each side

individually. Reaches some only partially covered if-statments in
_set_wrap_both.

* TST: Test padding of empty dimension with constant

* TST: Test if end_values of linear_ramp are exact

which was not given in the old implementation `_arange_ndarray`. (Was
accidentally overwritten during the last merge).

* TST: Test persistence of memory layout

Adapted from an older commit 3ac4d2a1b9b258d65f8d2b5f8f25f88e3a0e8f58
which was accidentally overwritten during the last merge.

* MAINT: Simplify branching in _set_reflect_both

Reduce branching and try to make the calculation of the various indices
easier to understand.

* TST: Parametrize TestConditionalShortcuts class

* TST: Test empty dimension padding for all modes

* TST: Keep test parametrization ordered

Keep parametrization ordered, otherwise pytest-xdist might believe that
different tests were collected during parallelization causing test
failures.

* DOC: Describe performance improvement of np.pad

as well as the new mode "empty" in release notes (see gh-11358).

* DOC: Remove outdated / misleading notes

These notes are badly worded or actually misleading. For a better
explanation on how these functions work have a look at the context and
comments just above the lines calling these functions.

1 files changed, 108 insertions, 48 deletions

diff --git a/numpy/lib/tests/test_arraypad.py b/numpy/lib/tests/test_arraypad.py
index b7393294a..d43c0d32e 100644
--- a/numpy/lib/tests/test_arraypad.py
+++ b/numpy/lib/tests/test_arraypad.py
@@ -2,6 +2,7 @@
 
 """
 from __future__ import division, absolute_import, print_function
+from itertools import chain
 
 import pytest
 
@@ -21,6 +22,7 @@ _all_modes = {
     'reflect': {'reflect_type': 'even'},
     'symmetric': {'reflect_type': 'even'},
     'wrap': {},
+    'empty': {}
 }
 
 
@@ -108,46 +110,25 @@ class TestAsPairs(object):
 
 
 class TestConditionalShortcuts(object):
-    def test_zero_padding_shortcuts(self):
+    @pytest.mark.parametrize("mode", _all_modes.keys())
+    def test_zero_padding_shortcuts(self, mode):
         test = np.arange(120).reshape(4, 5, 6)
-        pad_amt = [(0, 0) for axis in test.shape]
-        modes = ['constant',
-                 'edge',
-                 'linear_ramp',
-                 'maximum',
-                 'mean',
-                 'median',
-                 'minimum',
-                 'reflect',
-                 'symmetric',
-                 'wrap',
-                 ]
-        for mode in modes:
-            assert_array_equal(test, np.pad(test, pad_amt, mode=mode))
-
-    def test_shallow_statistic_range(self):
+        pad_amt = [(0, 0) for _ in test.shape]
+        assert_array_equal(test, np.pad(test, pad_amt, mode=mode))
+
+    @pytest.mark.parametrize("mode", ['maximum', 'mean', 'median', 'minimum',])
+    def test_shallow_statistic_range(self, mode):
         test = np.arange(120).reshape(4, 5, 6)
-        pad_amt = [(1, 1) for axis in test.shape]
-        modes = ['maximum',
-                 'mean',
-                 'median',
-                 'minimum',
-                 ]
-        for mode in modes:
-            assert_array_equal(np.pad(test, pad_amt, mode='edge'),
-                               np.pad(test, pad_amt, mode=mode, stat_length=1))
-
-    def test_clip_statistic_range(self):
+        pad_amt = [(1, 1) for _ in test.shape]
+        assert_array_equal(np.pad(test, pad_amt, mode='edge'),
+                           np.pad(test, pad_amt, mode=mode, stat_length=1))
+
+    @pytest.mark.parametrize("mode", ['maximum', 'mean', 'median', 'minimum',])
+    def test_clip_statistic_range(self, mode):
         test = np.arange(30).reshape(5, 6)
-        pad_amt = [(3, 3) for axis in test.shape]
-        modes = ['maximum',
-                 'mean',
-                 'median',
-                 'minimum',
-                 ]
-        for mode in modes:
-            assert_array_equal(np.pad(test, pad_amt, mode=mode),
-                               np.pad(test, pad_amt, mode=mode, stat_length=30))
+        pad_amt = [(3, 3) for _ in test.shape]
+        assert_array_equal(np.pad(test, pad_amt, mode=mode),
+                           np.pad(test, pad_amt, mode=mode, stat_length=30))
 
 
 class TestStatistic(object):
@@ -444,7 +425,7 @@ class TestStatistic(object):
         assert_array_equal(a, b)
 
     @pytest.mark.parametrize("mode", [
-        pytest.param("mean", marks=pytest.mark.xfail(reason="gh-11216")),
+        "mean",
         "median",
         "minimum",
         "maximum"
@@ -662,6 +643,11 @@ class TestConstant(object):
 
         assert_array_equal(arr, expected)
 
+    def test_pad_empty_dimension(self):
+        arr = np.zeros((3, 0, 2))
+        result = np.pad(arr, [(0,), (2,), (1,)], mode="constant")
+        assert result.shape == (3, 4, 4)
+
 
 class TestLinearRamp(object):
     def test_check_simple(self):
@@ -721,6 +707,14 @@ class TestLinearRamp(object):
         ])
         assert_equal(actual, expected)
 
+    def test_end_values(self):
+        """Ensure that end values are exact."""
+        a = np.pad(np.ones(10).reshape(2, 5), (223, 123), mode="linear_ramp")
+        assert_equal(a[:, 0], 0.)
+        assert_equal(a[:, -1], 0.)
+        assert_equal(a[0, :], 0.)
+        assert_equal(a[-1, :], 0.)
+
 
 class TestReflect(object):
     def test_check_simple(self):
@@ -831,19 +825,29 @@ class TestReflect(object):
         b = np.array([1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3])
         assert_array_equal(a, b)
 
-    def test_check_padding_an_empty_array(self):
-        a = np.pad(np.zeros((0, 3)), ((0,), (1,)), mode='reflect')
-        b = np.zeros((0, 5))
-        assert_array_equal(a, b)
 
-    def test_padding_empty_dimension(self):
-        match = "There aren't any elements to reflect in axis 0"
+class TestEmptyArray(object):
+    """Check how padding behaves on arrays with an empty dimension."""
+
+    @pytest.mark.parametrize(
+        # Keep parametrization ordered, otherwise pytest-xdist might believe
+        # that different tests were collected during parallelization
+        "mode", sorted(_all_modes.keys() - {"constant", "empty"})
+    )
+    def test_pad_empty_dimension(self, mode):
+        match = ("can't extend empty axis 0 using modes other than 'constant' "
+                 "or 'empty'")
         with pytest.raises(ValueError, match=match):
-            np.pad([], 4, mode='reflect')
+            np.pad([], 4, mode=mode)
         with pytest.raises(ValueError, match=match):
-            np.pad(np.ndarray(0), 4, mode='reflect')
+            np.pad(np.ndarray(0), 4, mode=mode)
         with pytest.raises(ValueError, match=match):
-            np.pad(np.zeros((0, 3)), ((1,), (0,)), mode='reflect')
+            np.pad(np.zeros((0, 3)), ((1,), (0,)), mode=mode)
+
+    @pytest.mark.parametrize("mode", _all_modes.keys())
+    def test_pad_non_empty_dimension(self, mode):
+        result = np.pad(np.ones((2, 0, 2)), ((3,), (0,), (1,)), mode=mode)
+        assert result.shape == (8, 0, 4)
 
 
 class TestSymmetric(object):
@@ -1080,6 +1084,19 @@ class TestWrap(object):
         b = np.pad(a, (0, 5), mode="wrap")
         assert_array_equal(a, b[:-5, :-5])
 
+    def test_repeated_wrapping(self):
+        """
+        Check wrapping on each side individually if the wrapped area is longer
+        than the original array.
+        """
+        a = np.arange(5)
+        b = np.pad(a, (12, 0), mode="wrap")
+        assert_array_equal(np.r_[a, a, a, a][3:], b)
+
+        a = np.arange(5)
+        b = np.pad(a, (0, 12), mode="wrap")
+        assert_array_equal(np.r_[a, a, a, a][:-3], b)
+
 
 class TestEdge(object):
     def test_check_simple(self):
@@ -1120,6 +1137,19 @@ class TestEdge(object):
         assert_array_equal(padded, expected)
 
 
+class TestEmpty(object):
+    def test_simple(self):
+        arr = np.arange(24).reshape(4, 6)
+        result = np.pad(arr, [(2, 3), (3, 1)], mode="empty")
+        assert result.shape == (9, 10)
+        assert_equal(arr, result[2:-3, 3:-1])
+
+    def test_pad_empty_dimension(self):
+        arr = np.zeros((3, 0, 2))
+        result = np.pad(arr, [(0,), (2,), (1,)], mode="empty")
+        assert result.shape == (3, 4, 4)
+
+
 def test_legacy_vector_functionality():
     def _padwithtens(vector, pad_width, iaxis, kwargs):
         vector[:pad_width[0]] = 10
@@ -1244,7 +1274,7 @@ def test_kwargs(mode):
     np.pad([1, 2, 3], 1, mode, **allowed)
     # Test if prohibited keyword arguments of other modes raise an error
     for key, value in not_allowed.items():
-        match = 'keyword not in allowed keywords'
+        match = "unsupported keyword arguments for mode '{}'".format(mode)
         with pytest.raises(ValueError, match=match):
             np.pad([1, 2, 3], 1, mode, **{key: value})
 
@@ -1254,9 +1284,39 @@ def test_constant_zero_default():
     assert_array_equal(np.pad(arr, 2), [0, 0, 1, 1, 0, 0])
 
 
+@pytest.mark.parametrize("mode", [1, "const", object(), None, True, False])
+def test_unsupported_mode(mode):
+    match= "mode '{}' is not supported".format(mode)
+    with pytest.raises(ValueError, match=match):
+        np.pad([1, 2, 3], 4, mode=mode)
+
+
 @pytest.mark.parametrize("mode", _all_modes.keys())
 def test_non_contiguous_array(mode):
     arr = np.arange(24).reshape(4, 6)[::2, ::2]
     result = np.pad(arr, (2, 3), mode)
     assert result.shape == (7, 8)
     assert_equal(result[2:-3, 2:-3], arr)
+
+
+@pytest.mark.parametrize("mode", _all_modes.keys())
+def test_memory_layout_persistence(mode):
+    """Test if C and F order is preserved for all pad modes."""
+    x = np.ones((5, 10), order='C')
+    assert np.pad(x, 5, mode).flags["C_CONTIGUOUS"]
+    x = np.ones((5, 10), order='F')
+    assert np.pad(x, 5, mode).flags["F_CONTIGUOUS"]
+
+
+@pytest.mark.parametrize("dtype", chain(
+    # Skip "other" dtypes as they are not supported by all modes
+    np.sctypes["int"],
+    np.sctypes["uint"],
+    np.sctypes["float"],
+    np.sctypes["complex"]
+))
+@pytest.mark.parametrize("mode", _all_modes.keys())
+def test_dtype_persistence(dtype, mode):
+    arr = np.zeros((3, 2, 1), dtype=dtype)
+    result = np.pad(arr, 1, mode=mode)
+    assert result.dtype == dtype