ironwork_rt/sort/
keys.rs

1//! The order of records under their keys, as SORT and MERGE give it: plain records and keys
2//! described as data, with no program behind them, so a sort utility can use it alone. A record's
3//! keys are read once into [`KeyValue`]s, which compare exactly, so the order is total and a stable
4//! sort keeps records with equal keys in the order they came.
5
6use crate::codec;
7use crate::fixed::{compare_fixed, fixed};
8use crate::lir;
9use crate::storage::{Kind, Val};
10use crate::store::compare_national;
11use crate::vocab::{SignClause, SignPosition};
12use numeric::Numproc;
13use numeric::precision::Places;
14use std::cmp::Ordering;
15use std::fmt;
16use std::rc::Rc;
17use zarch::check::ProgramCheck;
18use zarch::ebcdic::{self, CodePage, Collation};
19use zarch::hfp::Hfp;
20use zarch::wide::U256;
21
22/// A key's format, as DFSORT's SORT FIELDS names it.
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub enum Format {
25    /// Characters, in the order of the sort's collating sequence.
26    Ch,
27    /// Characters, in ASCII's order.
28    Ac,
29    /// Zoned decimal, signed in the last byte's zone.
30    Zd,
31    /// Zoned decimal, signed in the first byte's zone.
32    Clo,
33    /// Zoned decimal with a separate leading sign character.
34    Csl,
35    /// Zoned decimal with a separate trailing sign character.
36    Cst,
37    Pd,
38    /// Unsigned binary.
39    Bi,
40    /// Signed binary, in two's complement.
41    Fi,
42}
43
44impl Format {
45    /// The decimal format DFSORT reads a zoned or packed item's storage as; None for other items.
46    pub fn of_decimal(kind: Kind) -> Option<Format> {
47        Some(match kind {
48            Kind::Packed { .. } => Format::Pd,
49            Kind::Zoned { sign: Some(SignClause { separate: true, position: SignPosition::Leading }), .. } => Format::Csl,
50            Kind::Zoned { sign: Some(SignClause { separate: true, position: SignPosition::Trailing }), .. } => Format::Cst,
51            Kind::Zoned { sign: Some(SignClause { separate: false, position: SignPosition::Leading }), .. } => Format::Clo,
52            Kind::Zoned { .. } => Format::Zd,
53            _ => return None,
54        })
55    }
56
57    fn sign(self) -> Option<SignClause> {
58        match self {
59            Format::Clo => Some(SignClause { position: SignPosition::Leading, separate: false }),
60            Format::Csl => Some(SignClause { position: SignPosition::Leading, separate: true }),
61            Format::Cst => Some(SignClause { position: SignPosition::Trailing, separate: true }),
62            _ => None,
63        }
64    }
65}
66
67/// One key of a record: `length` bytes from byte `position`, counted from 0.
68#[derive(Clone, Copy, Debug, PartialEq, Eq)]
69pub struct Key {
70    pub position: usize,
71    pub length: usize,
72    pub format: Format,
73    pub ascending: bool,
74}
75
76/// The order characters collate in: EBCDIC's, or each byte's position in a sequence, where bytes
77/// that collate equal share a position.
78#[derive(Clone, Debug, Default, PartialEq, Eq)]
79pub enum Collating {
80    #[default]
81    Ebcdic,
82    Positions(Rc<[u8; 256]>),
83}
84
85impl Collating {
86    /// 7-bit ASCII's order, as ALPHABET IS STANDARD-1 gives it: the code page's character for each
87    /// ASCII code in turn, then every other byte in EBCDIC order.
88    pub fn ascii(page: &CodePage) -> Self {
89        let given: Vec<u8> = (0..0x80u8).filter_map(|c| page.encode_char(c as char)).collect();
90        let mut taken = [false; 256];
91        given.iter().for_each(|&b| taken[usize::from(b)] = true);
92        let order = given.into_iter().chain((0..=255u8).filter(|&b| !taken[usize::from(b)]));
93        let mut positions = [0u8; 256];
94        for (at, b) in order.enumerate() {
95            positions[usize::from(b)] = at as u8;
96        }
97        Collating::Positions(Rc::new(positions))
98    }
99
100    /// A program's collating sequence.
101    pub fn of(collating: &lir::Collating) -> Self {
102        match collating {
103            lir::Collating::Native => Collating::Ebcdic,
104            lir::Collating::Sequence(s) => Collating::Positions(Rc::new(*s.positions)),
105        }
106    }
107
108    pub fn is_ebcdic(&self) -> bool {
109        matches!(self, Collating::Ebcdic)
110    }
111
112    /// Each character's position.
113    pub fn collate(&self, bytes: &[u8]) -> Vec<u8> {
114        match self {
115            Collating::Ebcdic => bytes.to_vec(),
116            Collating::Positions(p) => bytes.iter().map(|&b| p[usize::from(b)]).collect(),
117        }
118    }
119}
120
121/// A key's value as the comparison sees it.
122#[derive(Clone, Debug)]
123pub enum KeyValue {
124    /// The value as a program reads its item.
125    Read(Val),
126    /// A zoned or packed key as DFSORT reads a ZD, PD, CLO, CSL or CST field: its sign, and its
127    /// digit nibbles as they stand.
128    Decimal { negative: bool, digits: Vec<u8> },
129    /// Bytes compared unsigned: characters as their positions in the collating sequence, binary
130    /// as it stands.
131    Collated(Vec<u8>),
132}
133
134/// The order of two records by their key values, most significant key first, with each key's
135/// direction in `ascending`. Every comparison is exact, so the order is total.
136pub fn order(a: &[KeyValue], b: &[KeyValue], ascending: &[bool]) -> Ordering {
137    for ((x, y), &up) in a.iter().zip(b).zip(ascending) {
138        let o = match (x, y) {
139            (KeyValue::Read(Val::Num(x)), KeyValue::Read(Val::Num(y))) => compare_fixed(x, y),
140            (KeyValue::Read(Val::Float(x)), KeyValue::Read(Val::Float(y))) => float_order(*x, *y),
141            (KeyValue::Read(Val::National(x)), KeyValue::Read(Val::National(y))) => compare_national(x, y),
142            (KeyValue::Read(Val::Bytes(x)), KeyValue::Read(Val::Bytes(y))) => ebcdic::compare_alphanumeric(x, y, &Collation::Native),
143            (KeyValue::Collated(x), KeyValue::Collated(y)) => x.cmp(y),
144            (KeyValue::Decimal { negative: false, digits: x }, KeyValue::Decimal { negative: false, digits: y }) => x.cmp(y),
145            (KeyValue::Decimal { negative: true, digits: x }, KeyValue::Decimal { negative: true, digits: y }) => y.cmp(x),
146            (KeyValue::Decimal { negative, .. }, KeyValue::Decimal { .. }) => if *negative { Ordering::Less } else { Ordering::Greater },
147            _ => Ordering::Equal,
148        };
149        let o = if up { o } else { o.reverse() };
150        if o != Ordering::Equal {
151            return o;
152        }
153    }
154    Ordering::Equal
155}
156
157/// Floating-point keys in numeric order, by exact value: normalized, the characteristic then the
158/// fraction.
159pub fn float_order(a: Hfp, b: Hfp) -> Ordering {
160    let exact = |h: Hfp| {
161        if h.fraction == 0 {
162            return (0, 0, 0);
163        }
164        let top = 4 * h.precision.digits() - 4;
165        let (mut exponent, mut fraction) = (h.characteristic as i32, h.fraction);
166        while fraction >> top == 0 {
167            fraction <<= 4;
168            exponent -= 1;
169        }
170        (if h.negative { -1 } else { 1 }, exponent, fraction)
171    };
172    let ((sa, ea, fa), (sb, eb, fb)) = (exact(a), exact(b));
173    match sa.cmp(&sb) {
174        Ordering::Equal if sa < 0 => (eb, fb).cmp(&(ea, fa)),
175        Ordering::Equal => (ea, fa).cmp(&(eb, fb)),
176        other => other,
177    }
178}
179
180/// A decimal field's sign and digit nibbles as DFSORT reads them, or None for a format that is not
181/// decimal or a field too short to hold one. See SORT_DECIMAL_KEYS, SORT_KEY_INVALID_DIGITS and
182/// SORT_NEGATIVE_ZERO in numeric::assumptions.
183pub fn decimal(bytes: &[u8], format: Format) -> Option<(bool, Vec<u8>)> {
184    let negative = |sign: u8| sign % 2 == 1 && sign != 0xF;
185    let low = |b: &[u8]| b.iter().map(|b| b & 0x0F).collect();
186    match format {
187        Format::Pd => {
188            let (last, body) = bytes.split_last()?;
189            let mut digits: Vec<u8> = body.iter().flat_map(|b| [b >> 4, b & 0x0F]).collect();
190            digits.push(last >> 4);
191            Some((negative(last & 0x0F), digits))
192        }
193        Format::Csl | Format::Cst => {
194            let (sign, body) = if format == Format::Csl { bytes.split_first()? } else { bytes.split_last()? };
195            Some((*sign == 0x60, low(body)))
196        }
197        Format::Clo => Some((negative(bytes.first()? >> 4), low(bytes))),
198        Format::Zd => Some((negative(bytes.last()? >> 4), low(bytes))),
199        _ => None,
200    }
201}
202
203/// Why a record's keys could not be read.
204#[derive(Clone, Copy, Debug, PartialEq, Eq)]
205pub enum KeyError {
206    /// Record `record` ends inside a key.
207    Short { record: usize, length: usize },
208    /// Under strict reading, key `key` of record `record` is not valid data for its format.
209    Data { record: usize, key: usize, check: ProgramCheck },
210}
211
212impl fmt::Display for KeyError {
213    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214        match self {
215            KeyError::Short { length, .. } => write!(f, "a record of {length} bytes ends inside a key"),
216            KeyError::Data { key, check, .. } => write!(f, "key {} is not valid data for its format: {check}", key + 1),
217        }
218    }
219}
220
221/// A sort's keys, most significant first, and how their bytes are read.
222#[derive(Clone, Debug, PartialEq, Eq)]
223pub struct Keys {
224    pub keys: Vec<Key>,
225    /// The order of CH keys.
226    pub collating: Collating,
227    /// The order of AC keys.
228    pub ascii: Collating,
229    /// None reads decimal keys as DFSORT does; Some reads them as a COBOL program under this
230    /// NUMPROC reads a signed item, refusing invalid data (ironwork's sort-keys strict).
231    pub strict: Option<Numproc>,
232}
233
234impl Keys {
235    /// CH keys in EBCDIC's order, AC keys in ASCII's by `page`, decimal keys as DFSORT reads them.
236    pub fn new(keys: Vec<Key>, page: &CodePage) -> Self {
237        Keys { keys, collating: Collating::Ebcdic, ascii: Collating::ascii(page), strict: None }
238    }
239
240    /// Each key's direction, as [`order`] takes them.
241    pub fn ascending(&self) -> Vec<bool> {
242        self.keys.iter().map(|k| k.ascending).collect()
243    }
244
245    /// The values of `record`'s keys; `index` is the record's place, which an error names.
246    pub fn values(&self, record: &[u8], index: usize) -> Result<Vec<KeyValue>, KeyError> {
247        let mut out = Vec::with_capacity(self.keys.len());
248        for (n, k) in self.keys.iter().enumerate() {
249            let bytes = record.get(k.position..k.position + k.length).ok_or(KeyError::Short { record: index, length: record.len() })?;
250            out.push(match k.format {
251                Format::Ch => KeyValue::Collated(self.collating.collate(bytes)),
252                Format::Ac => KeyValue::Collated(self.ascii.collate(bytes)),
253                Format::Bi => KeyValue::Collated(bytes.to_vec()),
254                Format::Fi => KeyValue::Collated(bytes.iter().enumerate().map(|(i, &b)| if i == 0 { b ^ 0x80 } else { b }).collect()),
255                decimal_format => match self.strict {
256                    Some(numproc) => {
257                        let read = strict(bytes, decimal_format, numproc).map_err(|check| KeyError::Data { record: index, key: n, check })?;
258                        KeyValue::Read(Val::Num(read))
259                    }
260                    None => match decimal(bytes, decimal_format) {
261                        Some((negative, digits)) => KeyValue::Decimal { negative, digits },
262                        None => KeyValue::Collated(Vec::new()),
263                    },
264                },
265            });
266        }
267        Ok(out)
268    }
269
270    pub fn compare(&self, a: &[u8], b: &[u8]) -> Result<Ordering, KeyError> {
271        Ok(order(&self.values(a, 0)?, &self.values(b, 1)?, &self.ascending()))
272    }
273
274    /// The records in key order; records with equal keys keep the order they came in, as DFSORT's
275    /// EQUALS keeps them. With no keys, the records as they came (SORT FIELDS=COPY).
276    pub fn sort(&self, records: Vec<Vec<u8>>) -> Result<Vec<Vec<u8>>, KeyError> {
277        let mut entries = Vec::with_capacity(records.len());
278        for (i, record) in records.into_iter().enumerate() {
279            let values = self.values(&record, i)?;
280            entries.push((record, values));
281        }
282        let ascending = self.ascending();
283        entries.sort_by(|a, b| order(&a.1, &b.1, &ascending));
284        Ok(entries.into_iter().map(|(record, _)| record).collect())
285    }
286
287    /// The first record that sorts before the one ahead of it, which a MERGE's input may not hold.
288    pub fn out_of_order(&self, records: &[Vec<u8>]) -> Result<Option<usize>, KeyError> {
289        let ascending = self.ascending();
290        let mut last: Option<Vec<KeyValue>> = None;
291        for (i, record) in records.iter().enumerate() {
292            let values = self.values(record, i)?;
293            if last.as_ref().is_some_and(|l| order(l, &values, &ascending) == Ordering::Greater) {
294                return Ok(Some(i));
295            }
296            last = Some(values);
297        }
298        Ok(None)
299    }
300}
301
302/// A decimal key read as a signed item of its format is, as a COBOL program reads it.
303fn strict(bytes: &[u8], format: Format, numproc: Numproc) -> Result<numeric::precision::Fixed, ProgramCheck> {
304    let shortest = if matches!(format, Format::Csl | Format::Cst) { 2 } else { 1 };
305    if bytes.len() < shortest {
306        return Err(ProgramCheck::Data);
307    }
308    let d = match format {
309        Format::Pd => codec::packed(bytes, true, numproc)?,
310        _ => codec::zoned(bytes, true, format.sign(), numproc)?,
311    };
312    Ok(fixed(d.negative, U256::from_u128(d.magnitude), Places::new(31, 0)))
313}
ironwork_rt/sort/keys.rs

ironwork_rt/sort/
keys.rs
