Repository: marshmallow-code/marshmallow

Issue:
[RFC] set_class = OrderedSet by default?
I assume the performance impact would be minimal. From a quick look, it would only affect schema instantiation.

The benefit is that when using Python 3.7+, all schemas would be ordered. They still wouldn't return `OrderedDict` instances unless `ordered` Meta is passed, but they would keep fields declaration order in their output and in their schema list, so that order would be respected in API responses and apispec users would get their fields documented in declaration order.

Currently, users can achieve this in a base schema with

```py
class OrderedBaseSchema(Schema):
    set_class = OrderedSet
```

My gut feeling is that this change would have no functional downside and a negligible perf impact at field init (less that we care about when adding a new feature), while using `ordered=True` does have an impact on serialization performance (I didn't measure it) and functionality (equality test depends on order), hence my proposal. There would still be an interest in allowing the use of `OrderedDict`.

If we go this route, we could use `OrderedSet` by default in marshmallow 3.x, and in marshmallow 4 perhaps rework the `ordered` feature because schemas would already be ordered so it would be specifically for users really needing an `OrderedDict` instance. Perhaps drop the `ordered` Meta option and let the user specify a dict class of their choice another way. But that's another story.

See https://github.com/marshmallow-code/flask-smorest/issues/228#issuecomment-777836226.



Discussion:
lafrech: I can't seem to find a way to silence mypy, here. Help welcome.
kkirsche: Mypy error for those curious:

```
src/marshmallow/schema.py:919: error: Incompatible types in assignment (expression has type "OrderedSet", variable has type "Optional[Union[Sequence[str], Set[str]]]")
src/marshmallow/schema.py:924: error: Incompatible types in assignment (expression has type "OrderedSet", variable has type "Set[Union[Any, str]]")
src/marshmallow/schema.py:972: error: Incompatible types in assignment (expression has type "AbstractSet[Any]", variable has type "OrderedSet")
```
The first error is because `self.only` is configured to be `StrSequenceOrSet | set_class | None` so when you assign an instance variable to it, it's no longer valid as that type, as `StrSequenceOrSet` is defined as `StrSequenceOrSet = typing.Union[typing.Sequence[str], typing.Set[str]]` which doesn't match the MutableSet being subclassed (set vs. mutable set being the key error here).

Updating `StrSequenceOrSet` to the following fixes the first issue:

```
StrSequenceOrSet = typing.Union[
    typing.Sequence[str], typing.Set[str], typing.MutableSet[str]
]
```

The second one is similar in nature, `self.exclude` is inferred as `Set[Any]` because of:

```python
        self.exclude = set(self.opts.exclude) | set(exclude)
```

To address this, you need to allow mutable sets because that's what the OrderedSet is subclassing.

```python
        self.exclude: typing.Set[typing.Any] | typing.MutableSet[typing.Any] = set(
            self.opts.exclude
        ) | set(exclude)
```

Finally, to address the last issue you need to tell Python that the `field_names` is ok being less specific (an AbstractSet rather than either a Mutable or immutable set:

```python
            field_names: typing.AbstractSet[typing.Any] = self.set_class(self.only)
```

With that, you'll pass all tests. Though, the OrderedSet is still only partially defined as it's missing the generic parameters and whatnot
kkirsche: https://docs.python.org/3/library/collections.abc.html#collections-abstract-base-classes can help understand the hierarchy of base types
kkirsche: This is a rough re-write of OrderedSet with type information. I didn't make a PR as I'm not confident enough in how map and end are being used to ensure that the types are correct. The use of lists instead of tuples makes typing a little more difficult as well, because we can't type locations in a list while we can with a tuple.

```python
# OrderedSet
# Copyright (c) 2009 Raymond Hettinger
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
#     The above copyright notice and this permission notice shall be
#     included in all copies or substantial portions of the Software.
#
#     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
#     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
#     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
#     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
#     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
#     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
#     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
#     OTHER DEALINGS IN THE SOFTWARE.
from collections.abc import MutableSet
from typing import Optional, Generator, Iterable, TypeVar

_Key = TypeVar("_Key")


class OrderedSet(MutableSet[_Key]):
    def __init__(self, iterable: Optional[Iterable[_Key]] = None) -> None:
        self.end = end = []  # type: ignore
        end += [None, end, end]  # sentinel node for doubly linked list
        self.map = {}  # key --> [key, prev, next] # type: ignore
        if iterable is not None:
            self |= set(iterable)

    def __len__(self) -> int:
        return len(self.map)

    def __contains__(self, key: object) -> bool:
        return key in self.map

    def add(self, key: _Key) -> None:
        if key not in self.map:
            end = self.end
            curr = end[1]
            curr[2] = end[1] = self.map[key] = [key, curr, end]

    def discard(self, key: _Key) -> None:
        if key in self.map:
            key, prev, next = self.map.pop(key)
            prev[2] = next
            next[1] = prev

    def __iter__(self) -> Generator[_Key, None, None]:
        end = self.end
        curr = end[2]
        while curr is not end:
            yield curr[0]
            curr = curr[2]

    def __reversed__(self) -> Generator[_Key, None, None]:
        end = self.end
        curr = end[1]
        while curr is not end:
            yield curr[0]
            curr = curr[1]

    def pop(self, last: bool = True) -> _Key:
        if not self:
            raise KeyError("set is empty")
        key: _Key = self.end[1][0] if last else self.end[2][0]
        self.discard(key)
        return key

    def __repr__(self) -> str:
        if not self:
            return f"{self.__class__.__name__}()"
        return f"{self.__class__.__name__}({list(self)!r})"

    def __eq__(self, other: object) -> bool:
        if isinstance(other, OrderedSet):
            return len(self) == len(other) and list(self) == list(other)
        if isinstance(other, Iterable):
            return set(self) == set(other)
        return False


if __name__ == "__main__":
    s = OrderedSet("abracadaba")
    t = OrderedSet("simsalabim")
    print(s | t)
    print(s & t)
    print(s - t)
```

Hope this helps :) 
lafrech: Thank you so much for looking into this!

Regarding the OrderedSet type hints, feel free to send a PR even as draft, if only for history. Also, you might want to have a look at ordered-set lib, see how they did id: https://github.com/rspeer/ordered-set/blob/master/ordered_set/__init__.py (and perhaps this SO question: https://stackoverflow.com/questions/52569356/provide-orderedsetint-like-types-using-stub-file-without-modifying-ordered-set). 
kkirsche: Thanks, submitted a few PR's to her repo to address some incorrect type usage (specifically, incorrect usage of `Any`). If you're curious, this comment explains the difference between using `Any` and `object` as a parameter:
https://github.com/python/typeshed/pull/8469#issuecomment-1203116838
lafrech: I think this is ready to go.

I removed the section about `ordered` from the quickstart because it is outdated and the option is now only required for a very specific purpose: using an `OrderedDict` for output, which doesn't need to be documented in a quickstart.

Not sure how and where to document `ordered`, now.

Does this change warrants an "upgrading to ..." section?

Patch:
diff --git a/docs/quickstart.rst b/docs/quickstart.rst
index 7d106228..c6bc2426 100644
--- a/docs/quickstart.rst
+++ b/docs/quickstart.rst
@@ -524,37 +524,6 @@ Note that ``name`` will be automatically formatted as a :class:`String <marshmal
                 # No need to include 'uppername'
                 additional = ("name", "email", "created_at")
 
-Ordering Output
----------------
-
-To maintain field ordering, set the ``ordered`` option to `True`. This will instruct marshmallow to serialize data to a `collections.OrderedDict`.
-
-.. code-block:: python
-
-    from collections import OrderedDict
-    from pprint import pprint
-
-    from marshmallow import Schema, fields
-
-
-    class UserSchema(Schema):
-        first_name = fields.String()
-        last_name = fields.String()
-        email = fields.Email()
-
-        class Meta:
-            ordered = True
-
-
-    u = User("Charlie", "Stones", "charlie@stones.com")
-    schema = UserSchema()
-    result = schema.dump(u)
-    assert isinstance(result, OrderedDict)
-    pprint(result, indent=2)
-    #  OrderedDict([('first_name', 'Charlie'),
-    #              ('last_name', 'Stones'),
-    #              ('email', 'charlie@stones.com')])
-
 Next Steps
 ----------
 
diff --git a/src/marshmallow/fields.py b/src/marshmallow/fields.py
index 118662b9..d258b977 100644
--- a/src/marshmallow/fields.py
+++ b/src/marshmallow/fields.py
@@ -137,7 +137,6 @@ class Field(FieldABC):
     #  to exist as attributes on the objects to serialize. Set this to False
     #  for those fields
     _CHECK_ATTRIBUTE = True
-    _creation_index = 0  # Used for sorting
 
     #: Default error messages for various kinds of errors. The keys in this dictionary
     #: are passed to `Field.make_error`. The values are error messages passed to
@@ -227,9 +226,6 @@ class Field(FieldABC):
                 stacklevel=2,
             )
 
-        self._creation_index = Field._creation_index
-        Field._creation_index += 1
-
         # Collect default error message from self and parent classes
         messages = {}  # type: dict[str, str]
         for cls in reversed(self.__class__.__mro__):
diff --git a/src/marshmallow/schema.py b/src/marshmallow/schema.py
index cde8c080..5a3b601e 100644
--- a/src/marshmallow/schema.py
+++ b/src/marshmallow/schema.py
@@ -42,25 +42,21 @@ from marshmallow.warnings import RemovedInMarshmallow4Warning
 _T = typing.TypeVar("_T")
 
 
-def _get_fields(attrs, ordered=False):
-    """Get fields from a class. If ordered=True, fields will sorted by creation index.
+def _get_fields(attrs):
+    """Get fields from a class
 
     :param attrs: Mapping of class attributes
-    :param bool ordered: Sort fields by creation index
     """
-    fields = [
+    return [
         (field_name, field_value)
         for field_name, field_value in attrs.items()
         if is_instance_or_subclass(field_value, base.FieldABC)
     ]
-    if ordered:
-        fields.sort(key=lambda pair: pair[1]._creation_index)
-    return fields
 
 
 # This function allows Schemas to inherit from non-Schema classes and ensures
 #   inheritance according to the MRO
-def _get_fields_by_mro(klass, ordered=False):
+def _get_fields_by_mro(klass):
     """Collect fields from a class, following its method resolution order. The
     class itself is excluded from the search; only its parents are checked. Get
     fields from ``_declared_fields`` if available, else use ``__dict__``.
@@ -73,7 +69,6 @@ def _get_fields_by_mro(klass, ordered=False):
         (
             _get_fields(
                 getattr(base, "_declared_fields", base.__dict__),
-                ordered=ordered,
             )
             for base in mro[:0:-1]
         ),
@@ -102,13 +97,13 @@ class SchemaMeta(ABCMeta):
                     break
             else:
                 ordered = False
-        cls_fields = _get_fields(attrs, ordered=ordered)
+        cls_fields = _get_fields(attrs)
         # Remove fields from list of class attributes to avoid shadowing
         # Schema attributes/methods in case of name conflict
         for field_name, _ in cls_fields:
             del attrs[field_name]
         klass = super().__new__(mcs, name, bases, attrs)
-        inherited_fields = _get_fields_by_mro(klass, ordered=ordered)
+        inherited_fields = _get_fields_by_mro(klass)
 
         meta = klass.Meta
         # Set klass.opts in __new__ rather than __init__ so that it is accessible in
@@ -117,13 +112,11 @@ class SchemaMeta(ABCMeta):
         # Add fields specified in the `include` class Meta option
         cls_fields += list(klass.opts.include.items())
 
-        dict_cls = OrderedDict if ordered else dict
         # Assign _declared_fields on class
         klass._declared_fields = mcs.get_declared_fields(
             klass=klass,
             cls_fields=cls_fields,
             inherited_fields=inherited_fields,
-            dict_cls=dict_cls,
         )
         return klass
 
@@ -133,7 +126,7 @@ class SchemaMeta(ABCMeta):
         klass: type,
         cls_fields: list,
         inherited_fields: list,
-        dict_cls: type,
+        dict_cls: type = dict,
     ):
         """Returns a dictionary of field_name => `Field` pairs declared on the class.
         This is exposed mainly so that plugins can add additional fields, e.g. fields
@@ -143,8 +136,7 @@ class SchemaMeta(ABCMeta):
         :param cls_fields: The fields declared on the class, including those added
             by the ``include`` class Meta option.
         :param inherited_fields: Inherited fields.
-        :param dict_cls: Either `dict` or `OrderedDict`, depending on whether
-            the user specified `ordered=True`.
+        :param dict_cls: dict-like class to use for dict output Default to ``dict``.
         """
         return dict_cls(inherited_fields + cls_fields)
 
@@ -319,6 +311,8 @@ class Schema(base.SchemaABC, metaclass=SchemaMeta):
 
     OPTIONS_CLASS = SchemaOpts  # type: type
 
+    set_class = OrderedSet
+
     # These get set by SchemaMeta
     opts = None  # type: SchemaOpts
     _declared_fields = {}  # type: typing.Dict[str, ma_fields.Field]
@@ -350,9 +344,7 @@ class Schema(base.SchemaABC, metaclass=SchemaMeta):
         - ``timeformat``: Default format for `Time <fields.Time>` fields.
         - ``render_module``: Module to use for `loads <Schema.loads>` and `dumps <Schema.dumps>`.
             Defaults to `json` from the standard library.
-        - ``ordered``: If `True`, order serialization output according to the
-            order in which fields were declared. Output of `Schema.dump` will be a
-            `collections.OrderedDict`.
+        - ``ordered``: If `True`, output of `Schema.dump` will be a `collections.OrderedDict`.
         - ``index_errors``: If `True`, errors dictionaries will include the index
             of invalid items in a collection.
         - ``load_only``: Tuple or list of fields to exclude from serialized results.
@@ -386,7 +378,9 @@ class Schema(base.SchemaABC, metaclass=SchemaMeta):
         self.declared_fields = copy.deepcopy(self._declared_fields)
         self.many = many
         self.only = only
-        self.exclude = set(self.opts.exclude) | set(exclude)
+        self.exclude: set[typing.Any] | typing.MutableSet[typing.Any] = set(
+            self.opts.exclude
+        ) | set(exclude)
         self.ordered = self.opts.ordered
         self.load_only = set(load_only) or set(self.opts.load_only)
         self.dump_only = set(dump_only) or set(self.opts.dump_only)
@@ -419,10 +413,6 @@ class Schema(base.SchemaABC, metaclass=SchemaMeta):
     def dict_class(self) -> type:
         return OrderedDict if self.ordered else dict
 
-    @property
-    def set_class(self) -> type:
-        return OrderedSet if self.ordered else set
-
     @classmethod
     def from_dict(
         cls,
@@ -970,7 +960,7 @@ class Schema(base.SchemaABC, metaclass=SchemaMeta):
 
         if self.only is not None:
             # Return only fields specified in only option
-            field_names = self.set_class(self.only)
+            field_names: typing.AbstractSet[typing.Any] = self.set_class(self.only)
 
             invalid_fields |= field_names - available_field_names
         else:
diff --git a/src/marshmallow/types.py b/src/marshmallow/types.py
index 7626994a..7c7b6b5b 100644
--- a/src/marshmallow/types.py
+++ b/src/marshmallow/types.py
@@ -6,6 +6,6 @@
 """
 import typing
 
-StrSequenceOrSet = typing.Union[typing.Sequence[str], typing.Set[str]]
+StrSequenceOrSet = typing.Union[typing.Sequence[str], typing.AbstractSet[str]]
 Tag = typing.Union[str, typing.Tuple[str, bool]]
 Validator = typing.Callable[[typing.Any], typing.Any]


Test patch:
diff --git a/tests/test_fields.py b/tests/test_fields.py
index 79fd0172..1296cd6d 100644
--- a/tests/test_fields.py
+++ b/tests/test_fields.py
@@ -9,6 +9,7 @@ from marshmallow import (
     RAISE,
     missing,
 )
+from marshmallow.orderedset import OrderedSet
 from marshmallow.exceptions import StringNotCollectionError
 
 from tests.base import ALL_FIELDS
@@ -380,14 +381,14 @@ class TestNestedField:
     @pytest.mark.parametrize(
         ("param", "fields_list"), [("only", ["foo"]), ("exclude", ["bar"])]
     )
-    def test_ordered_instanced_nested_schema_only_and_exclude(self, param, fields_list):
+    def test_nested_schema_only_and_exclude(self, param, fields_list):
         class NestedSchema(Schema):
+            # We mean to test the use of OrderedSet to specify it explicitly
+            # even if it is default
+            set_class = OrderedSet
             foo = fields.String()
             bar = fields.String()
 
-            class Meta:
-                ordered = True
-
         class MySchema(Schema):
             nested = fields.Nested(NestedSchema(), **{param: fields_list})
 
diff --git a/tests/test_options.py b/tests/test_options.py
index 02652d5f..e24d9445 100644
--- a/tests/test_options.py
+++ b/tests/test_options.py
@@ -178,9 +178,6 @@ class TestFieldOrdering:
 
     def test_nested_field_order_with_exclude_arg_is_maintained(self, user):
         class HasNestedExclude(Schema):
-            class Meta:
-                ordered = True
-
             user = fields.Nested(KeepOrder, exclude=("birthdate",))
 
         ser = HasNestedExclude()
@@ -231,7 +228,7 @@ class TestIncludeOption:
         result = s.load({"name": "Steve", "from": "Oskosh"})
         assert result == in_data
 
-    def test_ordered_included(self):
+    def test_included_fields_ordered_after_declared_fields(self):
         class AddFieldsOrdered(Schema):
             name = fields.Str()
             email = fields.Str()
@@ -242,7 +239,6 @@ class TestIncludeOption:
                     "in": fields.Str(),
                     "@at": fields.Str(),
                 }
-                ordered = True
 
         s = AddFieldsOrdered()
         in_data = {
diff --git a/tests/test_schema.py b/tests/test_schema.py
index 4943fbd8..bca3b78d 100644
--- a/tests/test_schema.py
+++ b/tests/test_schema.py
@@ -2933,3 +2933,16 @@ def test_unknown_parameter_value_is_validated(usage_location):
             MySchema(unknown="badval")
         else:
             MySchema().load({"foo": "bar"}, unknown="badval")
+
+
+@pytest.mark.parametrize("dict_cls", (dict, OrderedDict))
+def test_set_dict_class(dict_cls):
+    """Demonstrate how to specify dict_class as class attribute"""
+
+    class MySchema(Schema):
+        dict_class = dict_cls
+        foo = fields.String()
+
+    result = MySchema().dump({"foo": "bar"})
+    assert result == {"foo": "bar"}
+    assert isinstance(result, dict_cls)