nu_command/
sort_utils.rs

1use nu_engine::ClosureEval;
2use nu_protocol::{PipelineData, Record, ShellError, Span, Value, ast::CellPath};
3use nu_utils::IgnoreCaseExt;
4use std::cmp::Ordering;
5
6/// A specification of sort order for `sort_by`.
7///
8/// A closure comparator allows the user to return custom ordering to sort by.
9/// A cell path comparator uses the value referred to by the cell path as the sorting key.
10pub enum Comparator {
11    KeyClosure(ClosureEval),
12    CustomClosure(ClosureEval),
13    CellPath(CellPath),
14}
15
16/// Sort a slice of `Value`s.
17///
18/// Sort has the following invariants, in order of precedence:
19/// - Null values (Nothing type) are always sorted to the end.
20/// - For natural sort, numeric values (numeric strings, ints, and floats) appear first, sorted by numeric value
21/// - Values appear by order of `Value`'s `PartialOrd`.
22/// - Sorting for values with equal ordering is stable.
23///
24/// Generally, values of different types are ordered by order of appearance in the `Value` enum.
25/// However, this is not always the case. For example, ints and floats will be grouped together since
26/// `Value`'s `PartialOrd` defines a non-decreasing ordering between non-decreasing integers and floats.
27pub fn sort(vec: &mut [Value], insensitive: bool, natural: bool) -> Result<(), ShellError> {
28    // allow the comparator function to indicate error
29    // by mutating this option captured by the closure,
30    // since sort_by closure must be infallible
31    let mut compare_err: Option<ShellError> = None;
32
33    vec.sort_by(|a, b| {
34        // we've already hit an error, bail out now
35        if compare_err.is_some() {
36            return Ordering::Equal;
37        }
38
39        compare_values(a, b, insensitive, natural).unwrap_or_else(|err| {
40            compare_err.get_or_insert(err);
41            Ordering::Equal
42        })
43    });
44
45    if let Some(err) = compare_err {
46        Err(err)
47    } else {
48        Ok(())
49    }
50}
51
52/// Sort a slice of `Value`s by criteria specified by one or multiple `Comparator`s.
53pub fn sort_by(
54    vec: &mut [Value],
55    mut comparators: Vec<Comparator>,
56    head_span: Span,
57    insensitive: bool,
58    natural: bool,
59) -> Result<(), ShellError> {
60    if comparators.is_empty() {
61        return Err(ShellError::GenericError {
62            error: "expected name".into(),
63            msg: "requires a cell path or closure to sort data".into(),
64            span: Some(head_span),
65            help: None,
66            inner: vec![],
67        });
68    }
69
70    // allow the comparator function to indicate error
71    // by mutating this option captured by the closure,
72    // since sort_by closure must be infallible
73    let mut compare_err: Option<ShellError> = None;
74
75    vec.sort_by(|a, b| {
76        compare_by(
77            a,
78            b,
79            &mut comparators,
80            head_span,
81            insensitive,
82            natural,
83            &mut compare_err,
84        )
85    });
86
87    if let Some(err) = compare_err {
88        Err(err)
89    } else {
90        Ok(())
91    }
92}
93
94/// Sort a record's key-value pairs.
95///
96/// Can sort by key or by value.
97pub fn sort_record(
98    record: Record,
99    sort_by_value: bool,
100    reverse: bool,
101    insensitive: bool,
102    natural: bool,
103) -> Result<Record, ShellError> {
104    let mut input_pairs: Vec<(String, Value)> = record.into_iter().collect();
105
106    // allow the comparator function to indicate error
107    // by mutating this option captured by the closure,
108    // since sort_by closure must be infallible
109    let mut compare_err: Option<ShellError> = None;
110
111    if sort_by_value {
112        input_pairs.sort_by(|a, b| {
113            // we've already hit an error, bail out now
114            if compare_err.is_some() {
115                return Ordering::Equal;
116            }
117
118            compare_values(&a.1, &b.1, insensitive, natural).unwrap_or_else(|err| {
119                compare_err.get_or_insert(err);
120                Ordering::Equal
121            })
122        });
123    } else {
124        input_pairs.sort_by(|a, b| compare_strings(&a.0, &b.0, insensitive, natural));
125    };
126
127    if let Some(err) = compare_err {
128        return Err(err);
129    }
130
131    if reverse {
132        input_pairs.reverse()
133    }
134
135    Ok(input_pairs.into_iter().collect())
136}
137
138pub fn compare_by(
139    left: &Value,
140    right: &Value,
141    comparators: &mut [Comparator],
142    span: Span,
143    insensitive: bool,
144    natural: bool,
145    error: &mut Option<ShellError>,
146) -> Ordering {
147    // we've already hit an error, bail out now
148    if error.is_some() {
149        return Ordering::Equal;
150    }
151    for cmp in comparators.iter_mut() {
152        let result = match cmp {
153            Comparator::CellPath(cell_path) => {
154                compare_cell_path(left, right, cell_path, insensitive, natural)
155            }
156            Comparator::KeyClosure(closure) => {
157                compare_key_closure(left, right, closure, span, insensitive, natural)
158            }
159            Comparator::CustomClosure(closure) => {
160                compare_custom_closure(left, right, closure, span)
161            }
162        };
163        match result {
164            Ok(Ordering::Equal) => {}
165            Ok(ordering) => return ordering,
166            Err(err) => {
167                // don't bother continuing through the remaining comparators as we've hit an error
168                // don't overwrite if there's an existing error
169                error.get_or_insert(err);
170                return Ordering::Equal;
171            }
172        }
173    }
174    Ordering::Equal
175}
176
177/// Determines whether a value should be sorted as a string
178///
179/// If we're natural sorting, we want to sort strings, integers, and floats alphanumerically, so we should string sort.
180/// Otherwise, we only want to string sort if both values are strings or globs (to enable case insensitive comparison)
181fn should_sort_as_string(val: &Value, natural: bool) -> bool {
182    matches!(
183        (val, natural),
184        (&Value::String { .. }, _)
185            | (&Value::Glob { .. }, _)
186            | (&Value::Int { .. }, true)
187            | (&Value::Float { .. }, true)
188    )
189}
190
191/// Simple wrapper around `should_sort_as_string` to determine if two values
192/// should be compared as strings.
193fn should_string_compare(left: &Value, right: &Value, natural: bool) -> bool {
194    should_sort_as_string(left, natural) && should_sort_as_string(right, natural)
195}
196
197pub fn compare_values(
198    left: &Value,
199    right: &Value,
200    insensitive: bool,
201    natural: bool,
202) -> Result<Ordering, ShellError> {
203    if should_string_compare(left, right, natural) {
204        Ok(compare_strings(
205            &left.coerce_str()?,
206            &right.coerce_str()?,
207            insensitive,
208            natural,
209        ))
210    } else {
211        Ok(left.partial_cmp(right).unwrap_or(Ordering::Equal))
212    }
213}
214
215pub fn compare_strings(left: &str, right: &str, insensitive: bool, natural: bool) -> Ordering {
216    fn compare_inner<T>(left: T, right: T, natural: bool) -> Ordering
217    where
218        T: AsRef<str> + Ord,
219    {
220        if natural {
221            alphanumeric_sort::compare_str(left, right)
222        } else {
223            left.cmp(&right)
224        }
225    }
226
227    // only allocate a String if necessary for case folding
228    if insensitive {
229        compare_inner(left.to_folded_case(), right.to_folded_case(), natural)
230    } else {
231        compare_inner(left, right, natural)
232    }
233}
234
235pub fn compare_cell_path(
236    left: &Value,
237    right: &Value,
238    cell_path: &CellPath,
239    insensitive: bool,
240    natural: bool,
241) -> Result<Ordering, ShellError> {
242    let left = left.follow_cell_path(&cell_path.members)?;
243    let right = right.follow_cell_path(&cell_path.members)?;
244    compare_values(&left, &right, insensitive, natural)
245}
246
247pub fn compare_key_closure(
248    left: &Value,
249    right: &Value,
250    closure_eval: &mut ClosureEval,
251    span: Span,
252    insensitive: bool,
253    natural: bool,
254) -> Result<Ordering, ShellError> {
255    let left_key = closure_eval
256        .run_with_value(left.clone())?
257        .into_value(span)?;
258    let right_key = closure_eval
259        .run_with_value(right.clone())?
260        .into_value(span)?;
261    compare_values(&left_key, &right_key, insensitive, natural)
262}
263
264pub fn compare_custom_closure(
265    left: &Value,
266    right: &Value,
267    closure_eval: &mut ClosureEval,
268    span: Span,
269) -> Result<Ordering, ShellError> {
270    closure_eval
271        .add_arg(left.clone())
272        .add_arg(right.clone())
273        .run_with_input(PipelineData::Value(
274            Value::list(vec![left.clone(), right.clone()], span),
275            None,
276        ))
277        .and_then(|data| data.into_value(span))
278        .map(|val| {
279            if val.is_true() {
280                Ordering::Less
281            } else {
282                Ordering::Greater
283            }
284        })
285}
nu_command/sort_utils.rs

nu_command/
sort_utils.rs
