plg_runtime/builtins/
sortops.rs

1//! List-sorting builtins: `msort/2`, `sort/2`.
2//!
3//! Both sort by the standard order of terms (`compare_terms`):
4//! - `msort/2` is a stable sort that KEEPS duplicates.
5//! - `sort/2` sorts and then removes adjacent `Equal` duplicates.
6//!
7//! The first argument must be a proper list; otherwise a
8//! `type_error(list, Culprit)` is raised. The result is built on the heap.
9
10use crate::builtins::order::compare_terms;
11use crate::cell::*;
12use crate::machine::Machine;
13use crate::unify::unify;
14use plg_shared::atom::ATOM_NIL;
15use std::cmp::Ordering;
16
17#[inline]
18fn mref<'a>(m: *mut Machine) -> &'a mut Machine {
19    unsafe { &mut *m }
20}
21
22/// Collect a proper list's element words; `None` if not nil-terminated.
23fn collect_list(m: &Machine, w: Word) -> Option<Vec<Word>> {
24    let mut out = Vec::new();
25    let mut cur = m.deref(w);
26    loop {
27        match tag_of(cur) {
28            TAG_ATOM if atom_id(cur) == ATOM_NIL => return Some(out),
29            TAG_LST => {
30                let idx = payload(cur) as usize;
31                out.push(m.heap[idx]);
32                cur = m.deref(m.heap[idx + 1]);
33            }
34            _ => return None,
35        }
36    }
37}
38
39/// Build a nil-terminated list from words; return its word.
40fn build_list(m: &mut Machine, elems: &[Word]) -> Word {
41    let mut tail = make_atom(ATOM_NIL);
42    for &e in elems.iter().rev() {
43        let idx = m.heap.len();
44        m.heap.push(e);
45        m.heap.push(tail);
46        tail = make(TAG_LST, idx as u64);
47    }
48    tail
49}
50
51/// `msort/2`: stable sort by standard order, duplicates kept.
52#[unsafe(no_mangle)]
53pub extern "C" fn plg_rt_b_msort_2(m: *mut Machine, list: u64, sorted: u64, site_id: u32) -> i32 {
54    let _site = crate::machine::ErrorSiteGuard::enter(m, site_id);
55    let m = mref(m);
56    let Some(mut elems) = collect_list(m, list) else {
57        let culprit = m.deref(list);
58        crate::errors::type_error(m, "list", culprit, "msort/2: first argument must be a list");
59        return 0;
60    };
61    elems.sort_by(|&a, &b| compare_terms(m, a, b));
62    let lst = build_list(m, &elems);
63    unify(m, sorted, lst) as i32
64}
65
66/// `sort/2`: sort by standard order then drop adjacent `Equal` dups.
67#[unsafe(no_mangle)]
68pub extern "C" fn plg_rt_b_sort_2(m: *mut Machine, list: u64, sorted: u64, site_id: u32) -> i32 {
69    let _site = crate::machine::ErrorSiteGuard::enter(m, site_id);
70    let m = mref(m);
71    let Some(mut elems) = collect_list(m, list) else {
72        let culprit = m.deref(list);
73        crate::errors::type_error(m, "list", culprit, "sort/2: first argument must be a list");
74        return 0;
75    };
76    elems.sort_by(|&a, &b| compare_terms(m, a, b));
77    elems.dedup_by(|&mut a, &mut b| compare_terms(m, a, b) == Ordering::Equal);
78    let lst = build_list(m, &elems);
79    unify(m, sorted, lst) as i32
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use crate::machine::NO_SITE;
86    use plg_shared::StringInterner;
87
88    fn machine() -> Box<Machine> {
89        Machine::new(StringInterner::new(), Vec::new())
90    }
91
92    // Thin wrappers: existing tests exercise behavior, not provenance.
93    fn msort(m: *mut Machine, l: u64, s: u64) -> i32 {
94        plg_rt_b_msort_2(m, l, s, NO_SITE)
95    }
96    fn sort(m: *mut Machine, l: u64, s: u64) -> i32 {
97        plg_rt_b_sort_2(m, l, s, NO_SITE)
98    }
99
100    fn msg(m: &Machine) -> &str {
101        m.error.as_ref().unwrap().message.as_str()
102    }
103
104    fn ints(m: &mut Machine, vals: &[i64]) -> Word {
105        let ws: Vec<Word> = vals.iter().map(|&v| make_int(v)).collect();
106        build_list(m, &ws)
107    }
108
109    #[test]
110    fn msort_keeps_duplicates() {
111        let mut m = machine();
112        let l = ints(&mut m, &[3, 1, 2, 1]);
113        let out = m.new_var();
114        let mp = &mut *m as *mut Machine;
115        assert_eq!(msort(mp, l, out), 1);
116        let got: Vec<i64> = collect_list(&m, out)
117            .unwrap()
118            .iter()
119            .map(|&w| int_value(m.deref(w)))
120            .collect();
121        assert_eq!(got, vec![1, 1, 2, 3]);
122    }
123
124    #[test]
125    fn sort_dedups_adjacent_equal() {
126        let mut m = machine();
127        let l = ints(&mut m, &[3, 1, 2, 1]);
128        let out = m.new_var();
129        let mp = &mut *m as *mut Machine;
130        assert_eq!(sort(mp, l, out), 1);
131        let got: Vec<i64> = collect_list(&m, out)
132            .unwrap()
133            .iter()
134            .map(|&w| int_value(m.deref(w)))
135            .collect();
136        assert_eq!(got, vec![1, 2, 3]);
137    }
138
139    #[test]
140    fn sort_non_list_errors() {
141        let mut m = machine();
142        let foo = make_atom(m.atoms.intern("foo"));
143        let out = m.new_var();
144        let mp = &mut *m as *mut Machine;
145        assert_eq!(sort(mp, foo, out), 0);
146        assert_eq!(
147            msg(&m),
148            "error(type_error(list, foo), sort/2: first argument must be a list)"
149        );
150
151        let mut m = machine();
152        let foo = make_atom(m.atoms.intern("foo"));
153        let out = m.new_var();
154        let mp = &mut *m as *mut Machine;
155        assert_eq!(msort(mp, foo, out), 0);
156        assert_eq!(
157            msg(&m),
158            "error(type_error(list, foo), msort/2: first argument must be a list)"
159        );
160    }
161}
plg_runtime/builtins/sortops.rs

plg_runtime/builtins/
sortops.rs
