django_query/
sorting.rs

1//! # Create sort orders for Rust objects from query URLs
2//!
3//! Django queries can contain an `ordering` expression, which gives the
4//! fields of the object that should be used to determine
5//! the relative position of objects in the result table.
6//! Not all fields are sortable, but each sortable field
7//! provides one natural ordering.
8//!
9//! For fields of structured type, the natural ordering by that field
10//! can be taken from the natural ordering of one of its own fields,
11//! but this relationship is fixed. This is the only form of nesting
12//! present in ordering expressions.
13//!
14//! The expressions themselves are a comma-separated list of fields in
15//! priority order. Each field can be optional prefixed with a `-` to
16//! indicate the reverse ordering. So for example `"ordering=a,-b"`,
17//! means sort by the `a` field, and for ties use the reverse ordering
18//! of the `b` field
19//!
20//! # Overview
21//!
22//! The main trait in this module is [`Sortable`] which has an
23//! associated derive macro [`macro@Sortable`]. Deriving [`Sortable`]
24//! means the type can describe the sort orders it supports. An [`OrderingSet`]
25//! can be constructed for any [`Sortable`] type, and can parse ordering
26//! expressions from django-style queries.
27//!
28//! Example:
29//!
30//! ```rust
31//! use django_query::sorting::{Sortable, OrderingSet};
32//!
33//! #[derive(Sortable)]
34//! struct Bar {
35//!   #[django(sort)]
36//!   a: i32,
37//!   #[django(sort)]
38//!   b: i32,
39//! }
40//!
41//! #[derive(Sortable)]
42//! struct Foo {
43//!   #[django(sort)]
44//!   c: i32,
45//!   #[django(sort("b"))]
46//!   d: Bar,
47//! }
48//!
49//! let mut foos = vec![
50//!     Foo { c: 0, d: Bar { a: 1, b: 1 } },
51//!     Foo { c: 1, d: Bar { a: 0, b: 0 } },
52//!     Foo { c: 2, d: Bar { a: 2, b: 1 } },
53//!     Foo { c: 3, d: Bar { a: 3, b: 0 } },
54//! ];
55//!
56//! let qr = OrderingSet::<Foo>::new();
57//!
58//! let sort = qr.create_sort("-c").unwrap();
59//! sort.sort_vec(&mut foos);
60//! assert_eq!(foos[0].c, 3);
61//! assert_eq!(foos[1].c, 2);
62//! assert_eq!(foos[2].c, 1);
63//! assert_eq!(foos[3].c, 0);
64//!
65//! let sort = qr.create_sort("d,c").unwrap();
66//! sort.sort_vec(&mut foos);
67//! assert_eq!(foos[0].c, 1);
68//! assert_eq!(foos[1].c, 3);
69//! assert_eq!(foos[2].c, 0);
70//! assert_eq!(foos[3].c, 2);
71//! ```
72//!
73//! Because [`Sorter`] objects produced by parsing are boxed, there is
74//! virtual function call overhead when using them. This can be
75//! minimised by using the provided [`sort_vec`](Sorter::sort_vec)
76//! method to sort an entire [`Vec`] at a time, instead of testing
77//! pairs individually with [`compare`](Sorter::compare).
78
79use core::cmp::Ordering;
80use core::ops::Deref;
81
82use std::sync::Arc;
83
84use thiserror::Error;
85
86/// Errors produced by sorting.
87#[derive(Debug, Error)]
88pub enum SorterError {
89    /// The given sort expression is invalid.
90    #[error("cannot sort by expression '{0}'")]
91    NoSort(String),
92}
93
94/// A [`Sorter`] defined for all types that are [`Ord`].
95pub struct Compare;
96
97impl<T: Ord> Sorter<T> for Compare {
98    fn compare(&self, a: &T, b: &T) -> Ordering {
99        a.cmp(b)
100    }
101}
102
103/// A [`Sorter`] defined for all types that are [`Ord`], which reverses
104/// the natural order.
105pub struct ReverseCompare;
106
107impl<T: Ord> Sorter<T> for ReverseCompare {
108    fn compare(&self, a: &T, b: &T) -> Ordering {
109        b.cmp(a)
110    }
111}
112
113/// The [`SorterClass`] for [`Compare`] and [`ReverseCompare`].
114#[derive(Clone)]
115pub struct CompareClass;
116
117impl<'s, T: Ord> SorterClass<'s, T> for CompareClass {
118    fn instantiate(&self, reverse: bool) -> Box<dyn Sorter<T> + 's> {
119        if reverse {
120            Box::new(ReverseCompare)
121        } else {
122            Box::new(Compare)
123        }
124    }
125}
126
127impl<T: Ord> SorterTypedClass<T> for CompareClass {
128    type Sorter = Compare;
129    fn instantiate(&self) -> Compare {
130        Compare
131    }
132}
133
134/// Apply a [`Sorter`] to a member of a type.
135///
136/// By asking the type to apply the operator, we can avoid cloning
137/// potentially large objects in more complex cases of nesting.  If we
138/// used [`Accessor`] directly for everything, which is a much simpler
139/// definition, there are some constructs that we cannot handle
140/// efficiently, because of nested comparisons within members of type
141/// [`Option`], for example (i.e. in the case that a `Foo` is to be
142/// sorted by the `a` member of a contained object of type
143/// `Option<Bar>`.
144pub trait Field<R>: Clone {
145    type Value;
146    /// Extract whichever member this [Field] obtains from `R`, from
147    /// both `a` and `b` and apply `op` to the results.
148    fn apply_sorter<V: Sorter<Self::Value>>(&self, op: &V, a: &R, b: &R) -> Ordering;
149}
150
151/// Return a particular member of an instance by reference.
152///
153/// When [`Accessor`] is combined with the marker trait [`ReferenceField`], then
154/// [`Field`] is automatically derived.
155///
156/// Example:
157/// ```rust
158/// use django_query::sorting::{Accessor, Field, Compare, ReferenceField};
159/// use core::cmp::Ordering;
160///
161/// struct Foo {
162///   a: i32
163/// }
164///
165/// #[derive(Clone)]
166/// struct FooA;
167///
168/// impl Accessor<Foo> for FooA {
169///     type Value = i32;
170///     fn value<'a>(&self, data: &'a Foo) -> &'a i32 {
171///        &data.a
172///     }
173/// }
174///
175/// impl ReferenceField for FooA {}
176///
177/// let f_a = FooA;
178/// let foo1 = Foo { a: 20 };
179/// let foo2 = Foo { a: 10 };
180/// assert_eq!(f_a.value(&foo1), &20i32);
181/// assert_eq!(f_a.apply_sorter(&Compare, &foo1, &foo2), Ordering::Greater);
182/// ```
183pub trait Accessor<R>: Clone {
184    type Value;
185    /// Return a reference to a member of `data`
186    fn value<'a>(&self, data: &'a R) -> &'a Self::Value;
187}
188
189/// A marker for an [`Accessor`] that can act as a field.
190///
191/// Not all types of [`Field`] can be defined as a simple pass
192/// through, based on [`Accessor`].  Some fields need to create
193/// intermediate values, for example fields nested inside [`Option`]
194/// typed members of a containing structure. This marker indicates
195/// that the implementation of [`Accessor`] can be used for this type
196/// to automatically derive [`Field`].
197pub trait ReferenceField {}
198
199impl<R, F> Field<R> for F
200where
201    F: Accessor<R> + ReferenceField,
202{
203    type Value = <F as Accessor<R>>::Value;
204    fn apply_sorter<V: Sorter<Self::Value>>(&self, op: &V, a: &R, b: &R) -> Ordering {
205        op.compare(self.value(a), self.value(b))
206    }
207}
208
209/// Compare two values of another type `R`.
210///
211/// While [`Ord`] is a sensible trait for types that can have only one
212/// ordering, it needs to be generalised when a type can have multiple
213/// orderings according to some parameterisation. [`Sorter`] is just
214/// that generalisation.
215pub trait Sorter<R> {
216    /// Compare two elements, returning an [`Ordering`].
217    ///
218    /// This is essentially the equivalent of implementing
219    /// [`cmp`](core::cmp::Ord::cmp) for another type.
220    fn compare(&self, a: &R, b: &R) -> Ordering;
221
222    /// Sort a [`Vec`] in place.
223    fn sort_vec(&self, vec: &mut Vec<R>) {
224        vec.sort_by(|x, y| self.compare(x, y))
225    }
226
227    /// Sort a [`Vec`] of references in place.
228    fn sort_ref_vec(&self, vec: &mut Vec<&R>) {
229        vec.sort_by(|x, y| self.compare(x, y))
230    }
231}
232
233#[doc(hidden)]
234pub struct SorterImpl<F, S> {
235    field: F,
236    sorter: S,
237}
238
239impl<F, S> SorterImpl<F, S> {
240    pub fn new(field: F, sorter: S) -> Self {
241        Self { field, sorter }
242    }
243}
244
245impl<R, F, T, S> Sorter<R> for SorterImpl<F, S>
246where
247    F: Field<R, Value = T>,
248    S: Sorter<T>,
249{
250    fn compare(&self, a: &R, b: &R) -> Ordering {
251        self.field.apply_sorter(&self.sorter, a, b)
252    }
253}
254
255struct Reverser<S> {
256    inner: S,
257}
258
259impl<S> Reverser<S> {
260    pub fn new(inner: S) -> Self {
261        Self { inner }
262    }
263}
264
265impl<R, S> Sorter<R> for Reverser<S>
266where
267    S: Sorter<R>,
268{
269    fn compare(&self, a: &R, b: &R) -> Ordering {
270        self.inner.compare(a, b).reverse()
271    }
272}
273
274/// Make a type-elided [`Sorter`].
275///
276/// Instances of [`SorterClass`] can be stored in an [`OrderingSet`]
277/// and used to later instantiate [`Sorter`] instances.
278pub trait SorterClass<'s, R> {
279    /// Create a [`Sorter`], optionally reversing the order.
280    fn instantiate(&self, reverse: bool) -> Box<dyn Sorter<R> + 's>;
281}
282
283/// Make a typed [`Sorter`].
284///
285/// This trait is used for any underlying [`Sorter`] that wants to be
286/// used directly on a field, for example as a replacement for
287/// [`Compare`]. It does not incur virtual function overhead or
288/// storage overhead, but it also cannot be stored in collections for
289/// a given type.
290pub trait SorterTypedClass<R>: Clone {
291    type Sorter: Sorter<R>;
292    /// Create a new [`Sorter`].
293    fn instantiate(&self) -> Self::Sorter;
294}
295
296#[derive(Clone)]
297#[doc(hidden)]
298pub struct SorterClassImpl<F, S> {
299    field: F,
300    sorter: S,
301}
302
303impl<F, S> SorterClassImpl<F, S> {
304    pub fn new(field: F, sorter: S) -> Self {
305        Self { field, sorter }
306    }
307}
308
309impl<'s, R, F, T, S> SorterClass<'s, R> for SorterClassImpl<F, S>
310where
311    F: Field<R, Value = T> + 's,
312    S: SorterTypedClass<T>,
313    <S as SorterTypedClass<T>>::Sorter: 's,
314{
315    fn instantiate(&self, reverse: bool) -> Box<dyn Sorter<R> + 's> {
316        if reverse {
317            Box::new(Reverser::new(SorterImpl::new(
318                self.field.clone(),
319                self.sorter.instantiate(),
320            )))
321        } else {
322            Box::new(SorterImpl::new(
323                self.field.clone(),
324                self.sorter.instantiate(),
325            ))
326        }
327    }
328}
329
330impl<'s, R, F, T, S> SorterTypedClass<R> for SorterClassImpl<F, S>
331where
332    F: Field<R, Value = T> + 's,
333    S: SorterTypedClass<T>,
334{
335    type Sorter = SorterImpl<F, <S as SorterTypedClass<T>>::Sorter>;
336    fn instantiate(&self) -> Self::Sorter {
337        SorterImpl::new(self.field.clone(), self.sorter.instantiate())
338    }
339}
340
341/// Receive descriptions of the sort orders a type provides.
342///
343/// Each [`Meta`] instance will accept a [`SortVisitor`] and
344/// describe to it the list of sorts it supports, using the provided
345/// methods.
346pub trait SortVisitor<'s> {
347    type Target;
348    /// Receive a basic sort on a given raw [`Field`], named `name`.
349    /// The comparison operator itself is given as `sort`.
350    fn visit_sort<F, T, S>(&mut self, name: &str, field: &F, sort: &S)
351    where
352        F: Field<Self::Target, Value = T> + 's,
353        S: SorterTypedClass<T> + 's,
354        <S as SorterTypedClass<T>>::Sorter: 's;
355
356    /// Receive a key sort on a member field which is itself [`Sortable`].
357    ///
358    /// Here, `name` is the name of the sort as usual, `field` is the
359    /// accessor for the member, and `sort_key` is the name of the
360    /// sort in the field's own type which should be used.
361    fn visit_key_sort<F, T, M>(&mut self, name: &str, field: &F, sort_key: &str, meta: M)
362    where
363        F: Field<Self::Target, Value = T> + 's,
364        M: Meta<'s, T>;
365}
366
367/// Metadata about sorting for a type.
368pub trait Meta<'s, R> {
369    /// `visitor` will receive a callback for each sort that is
370    /// defined for this type.
371    fn accept_visitor<V: SortVisitor<'s, Target = R>>(&self, visitor: &mut V)
372    where
373        Self: Sized;
374}
375
376/// Something that can describe its sort orders.
377///
378/// This is the central trait of this module. Something that is
379/// [`Sortable`] can produce a [`Meta`] describing its sort orders. It
380/// has a derive macro which will automatically create all necessary
381/// supporting types using the markup on the type.
382pub trait Sortable<'s>: Sized {
383    /// `Meta` is the type which can describe our fields and their operators.
384    type Meta: Meta<'s, Self>;
385    /// `get_meta` produces an instance of our `Meta` type.
386    fn get_meta() -> Self::Meta;
387}
388
389impl<'s, T> Sortable<'s> for Arc<T>
390where
391    T: Sortable<'s>,
392{
393    type Meta = ArcMeta;
394    fn get_meta() -> Self::Meta {
395        ArcMeta
396    }
397}
398
399#[doc(hidden)]
400pub struct ArcMeta;
401
402impl<'s, T> Meta<'s, Arc<T>> for ArcMeta
403where
404    T: Sortable<'s>,
405{
406    fn accept_visitor<V: SortVisitor<'s, Target = Arc<T>>>(&self, visitor: &mut V) {
407        let mut v = VisitorWrapper { parent: visitor };
408        T::get_meta().accept_visitor(&mut v);
409    }
410}
411
412struct VisitorWrapper<'a, P> {
413    parent: &'a mut P,
414}
415
416impl<'a, 's, P, R, U> SortVisitor<'s> for VisitorWrapper<'a, P>
417where
418    P: SortVisitor<'s, Target = U>,
419    U: Deref<Target = R>,
420{
421    type Target = R;
422    fn visit_sort<F, T, S>(&mut self, name: &str, field: &F, sort: &S)
423    where
424        F: Field<R, Value = T> + 's,
425        S: SorterTypedClass<T> + 's,
426        <S as SorterTypedClass<T>>::Sorter: 's,
427    {
428        self.parent.visit_sort(
429            name,
430            &WrappedField {
431                inner: field.clone(),
432            },
433            sort,
434        );
435    }
436
437    fn visit_key_sort<F, T, M>(&mut self, name: &str, field: &F, sort_key: &str, meta: M)
438    where
439        F: Field<R, Value = T> + 's,
440        M: Meta<'s, T>,
441    {
442        self.parent.visit_key_sort(
443            name,
444            &WrappedField {
445                inner: field.clone(),
446            },
447            sort_key,
448            meta,
449        );
450    }
451}
452
453#[derive(Clone)]
454struct WrappedField<F> {
455    inner: F,
456}
457
458impl<R, F, T, U> Field<U> for WrappedField<F>
459where
460    F: Field<R, Value = T>,
461    U: Deref<Target = R>,
462{
463    type Value = T;
464    fn apply_sorter<V: Sorter<Self::Value>>(&self, op: &V, a: &U, b: &U) -> Ordering {
465        self.inner.apply_sorter(op, a, b)
466    }
467}
468
469impl<'s, T> Sortable<'s> for Option<T>
470where
471    T: Sortable<'s>,
472{
473    type Meta = OptionMeta;
474
475    fn get_meta() -> Self::Meta {
476        OptionMeta
477    }
478}
479
480#[doc(hidden)]
481pub struct OptionMeta;
482
483impl<'s, T> Meta<'s, Option<T>> for OptionMeta
484where
485    T: Sortable<'s>,
486{
487    fn accept_visitor<V: SortVisitor<'s, Target = Option<T>>>(&self, visitor: &mut V)
488    where
489        Self: Sized,
490    {
491        let mut v = OptionVisitor { parent: visitor };
492        T::get_meta().accept_visitor(&mut v);
493    }
494}
495
496struct OptionVisitor<'a, P> {
497    parent: &'a mut P,
498}
499
500impl<'a, 's, P, R> SortVisitor<'s> for OptionVisitor<'a, P>
501where
502    P: SortVisitor<'s, Target = Option<R>>,
503{
504    type Target = R;
505    fn visit_sort<F, T, S>(&mut self, name: &str, field: &F, sort: &S)
506    where
507        F: Field<R, Value = T> + 's,
508        S: SorterTypedClass<T> + 's,
509        <S as SorterTypedClass<T>>::Sorter: 's,
510    {
511        self.parent.visit_sort(
512            name,
513            &OptionField {
514                inner: field.clone(),
515            },
516            sort,
517        );
518    }
519
520    fn visit_key_sort<F, T, M>(&mut self, name: &str, field: &F, sort_key: &str, meta: M)
521    where
522        F: Field<R, Value = T> + 's,
523        M: Meta<'s, T>,
524    {
525        self.parent.visit_key_sort(
526            name,
527            &OptionField {
528                inner: field.clone(),
529            },
530            sort_key,
531            meta,
532        );
533    }
534}
535
536#[derive(Clone)]
537struct OptionField<F> {
538    inner: F,
539}
540
541impl<R, F, T> Field<Option<R>> for OptionField<F>
542where
543    F: Field<R, Value = T>,
544{
545    type Value = T;
546    fn apply_sorter<V: Sorter<Self::Value>>(
547        &self,
548        op: &V,
549        a: &Option<R>,
550        b: &Option<R>,
551    ) -> Ordering {
552        match (a.as_ref(), b.as_ref()) {
553            (Some(a), Some(b)) => self.inner.apply_sorter(&OptionOp { parent: op }, a, b),
554            (Some(_), None) => Ordering::Greater,
555            (None, Some(_)) => Ordering::Less,
556            (None, None) => Ordering::Equal,
557        }
558    }
559}
560
561struct OptionOp<'a, V> {
562    parent: &'a V,
563}
564
565impl<'a, V, T> Sorter<T> for OptionOp<'a, V>
566where
567    V: Sorter<T>,
568{
569    fn compare(&self, a: &T, b: &T) -> Ordering {
570        self.parent.compare(a, b)
571    }
572}
573
574/// A collection of sort orders, built from a [`Sortable`] type.
575pub struct OrderingSet<R> {
576    _marker: core::marker::PhantomData<R>,
577}
578
579impl<'s, R: Sortable<'s>> Default for OrderingSet<R> {
580    fn default() -> Self {
581        Self {
582            _marker: Default::default(),
583        }
584    }
585}
586
587impl<'s, R: Sortable<'s>> OrderingSet<R>
588where
589    // This unnecessary and painful bound is a result of
590    // https://github.com/rust-lang/rust/issues/96243 and comes about
591    // because we want StackedSorter to exist, but rust cannot
592    // correctly infer its lifetime
593    R: 's,
594{
595    /// Create a new [`OrderingSet`] for a [`Sortable`] type.
596    pub fn new() -> Self {
597        Default::default()
598    }
599
600    /// Parse a sort expression and return a [`Sorter`].
601    ///
602    /// Valid sort expressions consist of a comma-separated list of sorts, each of
603    /// which may be optionally preceded by a `-` to reverse its sense.
604    pub fn create_sort(&self, expr: &str) -> Result<Box<dyn Sorter<R> + 's>, SorterError> {
605        let parts = expr.split(',').collect::<Vec<&str>>();
606        let mut full_sort: Option<Box<dyn Sorter<R> + 's>> = None;
607        for part in parts.iter().rev() {
608            let part_sort = if let Some(name) = part.strip_prefix('-') {
609                let mut sp = SortProcessor { name, result: None };
610                R::get_meta().accept_visitor(&mut sp);
611
612                sp.result
613                    .ok_or_else(|| SorterError::NoSort(part.to_string()))?
614                    .instantiate(true)
615            } else {
616                let mut sp = SortProcessor {
617                    name: *part,
618                    result: None,
619                };
620                R::get_meta().accept_visitor(&mut sp);
621
622                sp.result
623                    .ok_or_else(|| SorterError::NoSort(part.to_string()))?
624                    .instantiate(false)
625            };
626            full_sort = if let Some(sort) = full_sort {
627                Some(Box::new(StackedSorter::new(part_sort, sort)))
628            } else {
629                Some(part_sort)
630            };
631        }
632        full_sort.ok_or_else(|| SorterError::NoSort(expr.to_string()))
633    }
634}
635
636#[doc(hidden)]
637pub struct SortProcessor<'s, 'q, R> {
638    pub name: &'q str,
639    pub result: Option<Box<dyn SorterClass<'s, R> + 's>>,
640}
641
642impl<'s, 'q, R> SortVisitor<'s> for SortProcessor<'s, 'q, R> {
643    type Target = R;
644    fn visit_sort<F, T, S>(&mut self, name: &str, field: &F, sort: &S)
645    where
646        F: Field<R, Value = T> + 's,
647        S: SorterTypedClass<T> + 's,
648        <S as SorterTypedClass<T>>::Sorter: 's,
649    {
650        if name == self.name {
651            self.result = Some(Box::new(SorterClassImpl::new(field.clone(), sort.clone())))
652        }
653    }
654
655    fn visit_key_sort<F, T, M>(&mut self, name: &str, field: &F, key: &str, meta: M)
656    where
657        F: Field<R, Value = T> + 's,
658        M: Meta<'s, T>,
659    {
660        let mut v = KeyVisitor::new(name, key, field.clone(), self);
661        meta.accept_visitor(&mut v);
662    }
663}
664
665#[doc(hidden)]
666pub struct KeyVisitor<'a, 'b, P, F> {
667    name: &'a str,
668    key: &'a str,
669    field: F,
670    parent: &'b mut P,
671}
672
673impl<'a, 'b, P, F> KeyVisitor<'a, 'b, P, F> {
674    pub fn new(name: &'a str, key: &'a str, field: F, parent: &'b mut P) -> Self {
675        Self {
676            name,
677            key,
678            field,
679            parent,
680        }
681    }
682}
683
684impl<'a, 'b, 's, P, G, R, S> SortVisitor<'s> for KeyVisitor<'a, 'b, P, G>
685where
686    P: SortVisitor<'s, Target = S>,
687    G: Field<S, Value = R> + 's,
688{
689    type Target = R;
690
691    fn visit_sort<F, T, Srt>(&mut self, name: &str, field: &F, sort: &Srt)
692    where
693        F: Field<R, Value = T> + 's,
694        Srt: SorterTypedClass<T> + 's,
695        <Srt as SorterTypedClass<T>>::Sorter: 's,
696    {
697        if name == self.key {
698            self.parent.visit_sort(
699                self.name,
700                &NestedField {
701                    outer: self.field.clone(),
702                    inner: field.clone(),
703                },
704                sort,
705            );
706        }
707    }
708
709    fn visit_key_sort<F, T, M>(&mut self, name: &str, field: &F, key: &str, meta: M)
710    where
711        F: Field<R, Value = T> + 's,
712        M: Meta<'s, T>,
713    {
714        if name == self.key {
715            let mut v = KeyVisitor {
716                name: self.name,
717                key,
718                field: NestedField {
719                    outer: self.field.clone(),
720                    inner: field.clone(),
721                },
722                parent: self.parent,
723            };
724            meta.accept_visitor(&mut v);
725        }
726    }
727}
728
729#[derive(Clone)]
730struct NestedField<F, G> {
731    outer: F,
732    inner: G,
733}
734
735impl<'s, F, G, R, T, U> Field<R> for NestedField<F, G>
736where
737    F: Field<R, Value = T>,
738    G: Field<T, Value = U>,
739{
740    type Value = U;
741    fn apply_sorter<V: Sorter<Self::Value>>(&self, op: &V, a: &R, b: &R) -> Ordering {
742        let n = NestedSorter {
743            inner: &self.inner,
744            op,
745        };
746        self.outer.apply_sorter(&n, a, b)
747    }
748}
749
750struct NestedSorter<'a, 'b, F, P> {
751    inner: &'a F,
752    op: &'b P,
753}
754
755impl<'a, 'b, F, P, T, U> Sorter<T> for NestedSorter<'a, 'b, F, P>
756where
757    F: Field<T, Value = U>,
758    P: Sorter<U>,
759{
760    fn compare(&self, a: &T, b: &T) -> Ordering {
761        self.inner.apply_sorter(self.op, a, b)
762    }
763}
764
765struct StackedSorter<'s, R> {
766    primary: Box<dyn Sorter<R> + 's>,
767    secondary: Box<dyn Sorter<R> + 's>,
768}
769
770impl<'s, R> StackedSorter<'s, R> {
771    pub fn new(primary: Box<dyn Sorter<R> + 's>, secondary: Box<dyn Sorter<R> + 's>) -> Self {
772        Self { primary, secondary }
773    }
774}
775
776impl<'s, R> Sorter<R> for StackedSorter<'s, R> {
777    fn compare(&self, a: &R, b: &R) -> Ordering {
778        match self.primary.compare(a, b) {
779            Ordering::Less => Ordering::Less,
780            Ordering::Greater => Ordering::Greater,
781            Ordering::Equal => self.secondary.compare(a, b),
782        }
783    }
784}
785
786// State support
787
788/// Something that can describe its sort orders, if a context value is
789/// provided.
790///
791/// A type implementing [`SortableWithContext`] can provide a [`Meta`]
792/// which describes its sorting fields, but only when a context object
793/// is provided. Note that the provided context object be stored
794/// within the [`Meta`], which is the origin of the lifetime parameter
795/// on that type.
796///
797#[cfg_attr(
798    feature = "persian-rug",
799    doc = r##"
800This can be derived via the
801[`SortableWithPersianRug`](SortableWithPersianRug)
802derive macro for the case of a [`persian-rug`](::persian_rug)
803type.
804"##
805)]
806pub trait SortableWithContext<'s, A: 's>: Sized {
807    /// `Meta` is the type which can describe our fields and their operators.
808    type Meta: Meta<'s, Self>;
809    /// `get_meta` produces an instance of our `Meta` type.
810    fn get_meta(access: A) -> Self::Meta;
811}
812
813/// A collection of sort orders, built from a [`SortableWithContext`] type.
814///
815/// Note that the context object provided on construction may be
816/// stored within the resulting object, and may also be cloned into
817/// the [`Meta`] for other types.
818pub struct OrderingSetWithContext<R, A> {
819    _marker: core::marker::PhantomData<R>,
820    access: A,
821}
822
823impl<'s, A: Clone + 's, R: SortableWithContext<'s, A>> OrderingSetWithContext<R, A>
824where
825    // This unnecessary and painful bound is a result of
826    // https://github.com/rust-lang/rust/issues/96243 and comes about
827    // because we want StackedSorter to exist, but rust cannot
828    // correctly infer its lifetime
829    R: 's,
830{
831    /// Create a new [OrderingSet] for a [Sortable] type.
832    pub fn new(access: A) -> Self {
833        Self {
834            _marker: Default::default(),
835            access,
836        }
837    }
838
839    /// Parse a sort expression and return a [Sorter].
840    ///
841    /// Valid sort expressions consist of a comma-separated list of sorts, each of
842    /// which may be optionally preceded by a `-` to reverse its sense.
843    pub fn create_sort(&self, expr: &str) -> Result<Box<dyn Sorter<R> + 's>, SorterError> {
844        let parts = expr.split(',').collect::<Vec<&str>>();
845        let mut full_sort: Option<Box<dyn Sorter<R> + 's>> = None;
846        for part in parts.iter().rev() {
847            let part_sort = if let Some(name) = part.strip_prefix('-') {
848                let mut sp = SortProcessor { name, result: None };
849                R::get_meta(self.access.clone()).accept_visitor(&mut sp);
850
851                sp.result
852                    .ok_or_else(|| SorterError::NoSort(part.to_string()))?
853                    .instantiate(true)
854            } else {
855                let mut sp = SortProcessor {
856                    name: *part,
857                    result: None,
858                };
859
860                R::get_meta(self.access.clone()).accept_visitor(&mut sp);
861
862                sp.result
863                    .ok_or_else(|| SorterError::NoSort(part.to_string()))?
864                    .instantiate(false)
865            };
866            full_sort = if let Some(sort) = full_sort {
867                Some(Box::new(StackedSorter::new(part_sort, sort)))
868            } else {
869                Some(part_sort)
870            };
871        }
872        full_sort.ok_or_else(|| SorterError::NoSort(expr.to_string()))
873    }
874}
875
876impl<'s, T, A> SortableWithContext<'s, A> for Option<T>
877where
878    T: SortableWithContext<'s, A>,
879    A: 's + Clone,
880{
881    type Meta = OptionMetaWithContext<A>;
882
883    fn get_meta(access: A) -> Self::Meta {
884        OptionMetaWithContext { access }
885    }
886}
887
888#[doc(hidden)]
889pub struct OptionMetaWithContext<A> {
890    access: A,
891}
892
893impl<'s, T, A> Meta<'s, Option<T>> for OptionMetaWithContext<A>
894where
895    A: 's + Clone,
896    T: SortableWithContext<'s, A>,
897{
898    fn accept_visitor<V: SortVisitor<'s, Target = Option<T>>>(&self, visitor: &mut V)
899    where
900        Self: Sized,
901    {
902        let mut v = OptionVisitor { parent: visitor };
903        T::get_meta(self.access.clone()).accept_visitor(&mut v);
904    }
905}
906
907pub use django_query_derive::Sortable;
908
909#[cfg(feature = "persian-rug")]
910#[cfg_attr(docsrs, doc(cfg(feature = "persian-rug")))]
911pub use crate::persian_rug::SortableWithPersianRug;
django_query/sorting.rs

django_query/
sorting.rs
