Repository: pallets/werkzeug (python)

Issue:
deprecate `OrderedMultiDict`
`OrderedMultiDict` is not used by Werkzeug. It has a complex implementation, and is documented to be slow. `dict` maintains key insertion order in all supported versions of Python. `MultiDict` already maintains the insertion order of values within a key. `OrderedMultiDict` maintains the insertion order of each item, so `[(a, 1), (b, 2), (a, 3)]` comes out the same instead of `[(a, 1), (a, 3), (b, 2)]`. It's not clear there's a use case for this, searching sourcegraph shows some use of `OrderedMultiDict` but it's not clear if the use is actually required vs using `MultiDict`. Other libraries such as boltons also provide implementations. Mark this as deprecated and see if anything comes up.

Pull request description:
deprecate OrderedMultiDict
closes #2968 

Patch:
diff --git a/CHANGES.rst b/CHANGES.rst
index 2976f889..c73bcaa8 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -10,6 +10,8 @@ Unreleased
 -   ``Request.max_form_memory_size`` defaults to 500kB instead of unlimited.
     Non-file form fields over this size will cause a ``RequestEntityTooLarge``
     error. :issue:`2964`
+-   ``OrderedMultiDict`` and ``ImmutableOrderedMultiDict`` are deprecated.
+    Use ``MultiDict`` and ``ImmutableMultiDict`` instead. :issue:`2968`
 -  Support Cookie CHIPS (Partitioned Cookies). :issue:`2797`
 -   ``CacheControl.no_transform`` is a boolean when present. ``min_fresh`` is
     ``None`` when not present. Added the ``must_understand`` attribute. Fixed
diff --git a/docs/datastructures.rst b/docs/datastructures.rst
index 92c96993..bd2c0d22 100644
--- a/docs/datastructures.rst
+++ b/docs/datastructures.rst
@@ -27,10 +27,33 @@ General Purpose
    :members:
    :inherited-members:
 
-.. autoclass:: OrderedMultiDict
+.. class:: OrderedMultiDict
 
-.. autoclass:: ImmutableMultiDict
-   :members: copy
+    Works like a regular :class:`MultiDict` but preserves the
+    order of the fields.  To convert the ordered multi dict into a
+    list you can use the :meth:`items` method and pass it ``multi=True``.
+
+    In general an :class:`OrderedMultiDict` is an order of magnitude
+    slower than a :class:`MultiDict`.
+
+    .. admonition:: note
+
+       Due to a limitation in Python you cannot convert an ordered
+       multi dict into a regular dict by using ``dict(multidict)``.
+       Instead you have to use the :meth:`to_dict` method, otherwise
+       the internal bucket objects are exposed.
+
+    .. deprecated:: 3.1
+        Will be removed in Werkzeug 3.2. Use ``MultiDict`` instead.
+
+.. class:: ImmutableMultiDict
+
+    An immutable :class:`OrderedMultiDict`.
+
+    .. deprecated:: 3.1
+        Will be removed in Werkzeug 3.2. Use ``ImmutableMultiDict`` instead.
+
+    .. versionadded:: 0.6
 
 .. autoclass:: ImmutableOrderedMultiDict
    :members: copy
diff --git a/src/werkzeug/datastructures/__init__.py b/src/werkzeug/datastructures/__init__.py
index 846ffce6..6582de02 100644
--- a/src/werkzeug/datastructures/__init__.py
+++ b/src/werkzeug/datastructures/__init__.py
@@ -1,3 +1,7 @@
+from __future__ import annotations
+
+import typing as t
+
 from .accept import Accept as Accept
 from .accept import CharsetAccept as CharsetAccept
 from .accept import LanguageAccept as LanguageAccept
@@ -26,9 +30,35 @@ from .structures import HeaderSet as HeaderSet
 from .structures import ImmutableDict as ImmutableDict
 from .structures import ImmutableList as ImmutableList
 from .structures import ImmutableMultiDict as ImmutableMultiDict
-from .structures import ImmutableOrderedMultiDict as ImmutableOrderedMultiDict
 from .structures import ImmutableTypeConversionDict as ImmutableTypeConversionDict
 from .structures import iter_multi_items as iter_multi_items
 from .structures import MultiDict as MultiDict
-from .structures import OrderedMultiDict as OrderedMultiDict
 from .structures import TypeConversionDict as TypeConversionDict
+
+
+def __getattr__(name: str) -> t.Any:
+    import warnings
+
+    if name == "OrderedMultiDict":
+        from .structures import _OrderedMultiDict
+
+        warnings.warn(
+            "'OrderedMultiDict' is deprecated and will be removed in Werkzeug"
+            " 3.2. Use 'MultiDict' instead.",
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        return _OrderedMultiDict
+
+    if name == "ImmutableOrderedMultiDict":
+        from .structures import _ImmutableOrderedMultiDict
+
+        warnings.warn(
+            "'OrderedMultiDict' is deprecated and will be removed in Werkzeug"
+            " 3.2. Use 'ImmutableMultiDict' instead.",
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        return _ImmutableOrderedMultiDict
+
+    raise AttributeError(name)
diff --git a/src/werkzeug/datastructures/structures.py b/src/werkzeug/datastructures/structures.py
index eb54599d..34863ccc 100644
--- a/src/werkzeug/datastructures/structures.py
+++ b/src/werkzeug/datastructures/structures.py
@@ -522,7 +522,7 @@ class _omd_bucket(t.Generic[K, V]):
 
     __slots__ = ("prev", "key", "value", "next")
 
-    def __init__(self, omd: OrderedMultiDict[K, V], key: K, value: V) -> None:
+    def __init__(self, omd: _OrderedMultiDict[K, V], key: K, value: V) -> None:
         self.prev: _omd_bucket[K, V] | None = omd._last_bucket
         self.key: K = key
         self.value: V = value
@@ -534,7 +534,7 @@ class _omd_bucket(t.Generic[K, V]):
             omd._last_bucket.next = self
         omd._last_bucket = self
 
-    def unlink(self, omd: OrderedMultiDict[K, V]) -> None:
+    def unlink(self, omd: _OrderedMultiDict[K, V]) -> None:
         if self.prev:
             self.prev.next = self.next
         if self.next:
@@ -545,7 +545,7 @@ class _omd_bucket(t.Generic[K, V]):
             omd._last_bucket = self.prev
 
 
-class OrderedMultiDict(MultiDict[K, V]):
+class _OrderedMultiDict(MultiDict[K, V]):
     """Works like a regular :class:`MultiDict` but preserves the
     order of the fields.  To convert the ordered multi dict into a
     list you can use the :meth:`items` method and pass it ``multi=True``.
@@ -559,6 +559,9 @@ class OrderedMultiDict(MultiDict[K, V]):
        multi dict into a regular dict by using ``dict(multidict)``.
        Instead you have to use the :meth:`to_dict` method, otherwise
        the internal bucket objects are exposed.
+
+    .. deprecated:: 3.1
+        Will be removed in Werkzeug 3.2. Use ``MultiDict`` instead.
     """
 
     def __init__(
@@ -570,6 +573,14 @@ class OrderedMultiDict(MultiDict[K, V]):
             | None
         ) = None,
     ) -> None:
+        import warnings
+
+        warnings.warn(
+            "'OrderedMultiDict' is deprecated and will be removed in Werkzeug"
+            " 3.2. Use 'MultiDict' instead.",
+            DeprecationWarning,
+            stacklevel=2,
+        )
         super().__init__()
         self._first_bucket: _omd_bucket[K, V] | None = None
         self._last_bucket: _omd_bucket[K, V] | None = None
@@ -579,7 +590,7 @@ class OrderedMultiDict(MultiDict[K, V]):
     def __eq__(self, other: object) -> bool:
         if not isinstance(other, MultiDict):
             return NotImplemented
-        if isinstance(other, OrderedMultiDict):
+        if isinstance(other, _OrderedMultiDict):
             iter1 = iter(self.items(multi=True))
             iter2 = iter(other.items(multi=True))
             try:
@@ -944,9 +955,14 @@ class ImmutableMultiDict(ImmutableMultiDictMixin[K, V], MultiDict[K, V]):  # typ
         return self
 
 
-class ImmutableOrderedMultiDict(ImmutableMultiDictMixin[K, V], OrderedMultiDict[K, V]):  # type: ignore[misc]
+class _ImmutableOrderedMultiDict(  # type: ignore[misc]
+    ImmutableMultiDictMixin[K, V], _OrderedMultiDict[K, V]
+):
     """An immutable :class:`OrderedMultiDict`.
 
+    .. deprecated:: 3.1
+        Will be removed in Werkzeug 3.2. Use ``ImmutableMultiDict`` instead.
+
     .. versionadded:: 0.6
     """
 
@@ -963,17 +979,17 @@ class ImmutableOrderedMultiDict(ImmutableMultiDictMixin[K, V], OrderedMultiDict[
 
         if mapping is not None:
             for k, v in iter_multi_items(mapping):
-                OrderedMultiDict.add(self, k, v)
+                _OrderedMultiDict.add(self, k, v)
 
     def _iter_hashitems(self) -> cabc.Iterable[t.Any]:
         return enumerate(self.items(multi=True))
 
-    def copy(self) -> OrderedMultiDict[K, V]:  # type: ignore[override]
+    def copy(self) -> _OrderedMultiDict[K, V]:  # type: ignore[override]
         """Return a shallow mutable copy of this object.  Keep in mind that
         the standard library's :func:`copy` function is a no-op for this class
         like for any other python immutable type (eg: :class:`tuple`).
         """
-        return OrderedMultiDict(self)
+        return _OrderedMultiDict(self)
 
     def __copy__(self) -> te.Self:
         return self
@@ -1157,3 +1173,27 @@ class HeaderSet(cabc.MutableSet[str]):
 
 # circular dependencies
 from .. import http
+
+
+def __getattr__(name: str) -> t.Any:
+    import warnings
+
+    if name == "OrderedMultiDict":
+        warnings.warn(
+            "'OrderedMultiDict' is deprecated and will be removed in Werkzeug"
+            " 3.2. Use 'MultiDict' instead.",
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        return _OrderedMultiDict
+
+    if name == "ImmutableOrderedMultiDict":
+        warnings.warn(
+            "'ImmutableOrderedMultiDict' is deprecated and will be removed in"
+            " Werkzeug 3.2. Use 'ImmutableMultiDict' instead.",
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        return _ImmutableOrderedMultiDict
+
+    raise AttributeError(name)
diff --git a/src/werkzeug/sansio/request.py b/src/werkzeug/sansio/request.py
index dd0805d7..8d5fbd8f 100644
--- a/src/werkzeug/sansio/request.py
+++ b/src/werkzeug/sansio/request.py
@@ -67,10 +67,8 @@ class Request:
 
     #: the class to use for `args` and `form`.  The default is an
     #: :class:`~werkzeug.datastructures.ImmutableMultiDict` which supports
-    #: multiple values per key.  alternatively it makes sense to use an
-    #: :class:`~werkzeug.datastructures.ImmutableOrderedMultiDict` which
-    #: preserves order or a :class:`~werkzeug.datastructures.ImmutableDict`
-    #: which is the fastest but only remembers the last key.  It is also
+    #: multiple values per key. A :class:`~werkzeug.datastructures.ImmutableDict`
+    #: is faster but only remembers the last key. It is also
     #: possible to use mutable structures, but this is not recommended.
     #:
     #: .. versionadded:: 0.6


Test patch:
diff --git a/tests/test_datastructures.py b/tests/test_datastructures.py
index 76de1d84..9d11d2aa 100644
--- a/tests/test_datastructures.py
+++ b/tests/test_datastructures.py
@@ -9,6 +9,8 @@ import pytest
 
 from werkzeug import datastructures as ds
 from werkzeug import http
+from werkzeug.datastructures.structures import _ImmutableOrderedMultiDict
+from werkzeug.datastructures.structures import _OrderedMultiDict
 from werkzeug.exceptions import BadRequestKeyError
 
 
@@ -333,8 +335,9 @@ class TestImmutableDict(_ImmutableDictTests):
     storage_class = ds.ImmutableDict
 
 
+@pytest.mark.filterwarnings("ignore:'OrderedMultiDict':DeprecationWarning")
 class TestImmutableOrderedMultiDict(_ImmutableDictTests):
-    storage_class = ds.ImmutableOrderedMultiDict
+    storage_class = _ImmutableOrderedMultiDict
 
     def test_ordered_multidict_is_hashable(self):
         a = self.storage_class([("a", 1), ("b", 1), ("a", 2)])
@@ -412,8 +415,9 @@ class TestMultiDict(_MutableMultiDictTests):
             md["empty"]
 
 
+@pytest.mark.filterwarnings("ignore:'OrderedMultiDict':DeprecationWarning")
 class TestOrderedMultiDict(_MutableMultiDictTests):
-    storage_class = ds.OrderedMultiDict
+    storage_class = _OrderedMultiDict
 
     def test_ordered_interface(self):
         cls = self.storage_class
diff --git a/tests/test_wrappers.py b/tests/test_wrappers.py
index f7569445..8bc063c7 100644
--- a/tests/test_wrappers.py
+++ b/tests/test_wrappers.py
@@ -16,11 +16,11 @@ from werkzeug.datastructures import CombinedMultiDict
 from werkzeug.datastructures import Headers
 from werkzeug.datastructures import ImmutableList
 from werkzeug.datastructures import ImmutableMultiDict
-from werkzeug.datastructures import ImmutableOrderedMultiDict
 from werkzeug.datastructures import LanguageAccept
 from werkzeug.datastructures import MIMEAccept
 from werkzeug.datastructures import MultiDict
 from werkzeug.datastructures import WWWAuthenticate
+from werkzeug.datastructures.structures import _ImmutableOrderedMultiDict
 from werkzeug.exceptions import BadRequest
 from werkzeug.exceptions import RequestedRangeNotSatisfiable
 from werkzeug.exceptions import SecurityError
@@ -998,9 +998,10 @@ def test_new_response_iterator_behavior():
         assert resp.response == ["foo", "bar", "baz"]
 
 
+@pytest.mark.filterwarnings("ignore:'OrderedMultiDict':DeprecationWarning")
 def test_form_data_ordering():
     class MyRequest(wrappers.Request):
-        parameter_storage_class = ImmutableOrderedMultiDict
+        parameter_storage_class = _ImmutableOrderedMultiDict
 
     req = MyRequest.from_values("/?foo=1&bar=0&foo=3")
     assert list(req.args) == ["foo", "bar"]
@@ -1009,7 +1010,7 @@ def test_form_data_ordering():
         ("bar", "0"),
         ("foo", "3"),
     ]
-    assert isinstance(req.args, ImmutableOrderedMultiDict)
+    assert isinstance(req.args, _ImmutableOrderedMultiDict)
     assert isinstance(req.values, CombinedMultiDict)
     assert req.values["foo"] == "1"
     assert req.values.getlist("foo") == ["1", "3"]