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    /// Each character's position.
109    pub fn collate(&self, bytes: &[u8]) -> Vec<u8> {
110        match self {
111            Collating::Ebcdic => bytes.to_vec(),
112            Collating::Positions(p) => bytes.iter().map(|&b| p[usize::from(b)]).collect(),
113        }
114    }
115}
116
117/// A key's value as the comparison sees it.
118#[derive(Clone, Debug)]
119pub enum KeyValue {
120    /// The value as a program reads its item.
121    Read(Val),
122    /// A zoned or packed key as DFSORT reads a ZD, PD, CLO, CSL or CST field: its sign, and its
123    /// digit nibbles as they stand.
124    Decimal { negative: bool, digits: Vec<u8> },
125    /// Bytes compared unsigned: characters as their positions in the collating sequence, binary
126    /// as it stands.
127    Collated(Vec<u8>),
128}
129
130/// The order of two records by their key values, most significant key first, with each key's
131/// direction in `ascending`. Every comparison is exact, so the order is total.
132pub fn order(a: &[KeyValue], b: &[KeyValue], ascending: &[bool]) -> Ordering {
133    for ((x, y), &up) in a.iter().zip(b).zip(ascending) {
134        let o = match (x, y) {
135            (KeyValue::Read(Val::Num(x)), KeyValue::Read(Val::Num(y))) => compare_fixed(x, y),
136            (KeyValue::Read(Val::Float(x)), KeyValue::Read(Val::Float(y))) => float_order(*x, *y),
137            (KeyValue::Read(Val::National(x)), KeyValue::Read(Val::National(y))) => compare_national(x, y),
138            (KeyValue::Read(Val::Bytes(x)), KeyValue::Read(Val::Bytes(y))) => ebcdic::compare_alphanumeric(x, y, &Collation::Native),
139            (KeyValue::Collated(x), KeyValue::Collated(y)) => x.cmp(y),
140            (KeyValue::Decimal { negative: false, digits: x }, KeyValue::Decimal { negative: false, digits: y }) => x.cmp(y),
141            (KeyValue::Decimal { negative: true, digits: x }, KeyValue::Decimal { negative: true, digits: y }) => y.cmp(x),
142            (KeyValue::Decimal { negative, .. }, KeyValue::Decimal { .. }) => if *negative { Ordering::Less } else { Ordering::Greater },
143            _ => Ordering::Equal,
144        };
145        let o = if up { o } else { o.reverse() };
146        if o != Ordering::Equal {
147            return o;
148        }
149    }
150    Ordering::Equal
151}
152
153/// Floating-point keys in numeric order, by exact value: normalized, the characteristic then the
154/// fraction.
155pub fn float_order(a: Hfp, b: Hfp) -> Ordering {
156    let exact = |h: Hfp| {
157        if h.fraction == 0 {
158            return (0, 0, 0);
159        }
160        let top = 4 * h.precision.digits() - 4;
161        let (mut exponent, mut fraction) = (h.characteristic as i32, h.fraction);
162        while fraction >> top == 0 {
163            fraction <<= 4;
164            exponent -= 1;
165        }
166        (if h.negative { -1 } else { 1 }, exponent, fraction)
167    };
168    let ((sa, ea, fa), (sb, eb, fb)) = (exact(a), exact(b));
169    match sa.cmp(&sb) {
170        Ordering::Equal if sa < 0 => (eb, fb).cmp(&(ea, fa)),
171        Ordering::Equal => (ea, fa).cmp(&(eb, fb)),
172        other => other,
173    }
174}
175
176/// A decimal field's sign and digit nibbles as DFSORT reads them, or None for a format that is not
177/// decimal or a field too short to hold one. See SORT_DECIMAL_KEYS, SORT_KEY_INVALID_DIGITS and
178/// SORT_NEGATIVE_ZERO in numeric::assumptions.
179pub fn decimal(bytes: &[u8], format: Format) -> Option<(bool, Vec<u8>)> {
180    let negative = |sign: u8| sign % 2 == 1 && sign != 0xF;
181    let low = |b: &[u8]| b.iter().map(|b| b & 0x0F).collect();
182    match format {
183        Format::Pd => {
184            let (last, body) = bytes.split_last()?;
185            let mut digits: Vec<u8> = body.iter().flat_map(|b| [b >> 4, b & 0x0F]).collect();
186            digits.push(last >> 4);
187            Some((negative(last & 0x0F), digits))
188        }
189        Format::Csl | Format::Cst => {
190            let (sign, body) = if format == Format::Csl { bytes.split_first()? } else { bytes.split_last()? };
191            Some((*sign == 0x60, low(body)))
192        }
193        Format::Clo => Some((negative(bytes.first()? >> 4), low(bytes))),
194        Format::Zd => Some((negative(bytes.last()? >> 4), low(bytes))),
195        _ => None,
196    }
197}
198
199/// Why a record's keys could not be read.
200#[derive(Clone, Copy, Debug, PartialEq, Eq)]
201pub enum KeyError {
202    /// Record `record` ends inside a key.
203    Short { record: usize, length: usize },
204    /// Under strict reading, key `key` of record `record` is not valid data for its format.
205    Data { record: usize, key: usize, check: ProgramCheck },
206}
207
208impl fmt::Display for KeyError {
209    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210        match self {
211            KeyError::Short { length, .. } => write!(f, "a record of {length} bytes ends inside a key"),
212            KeyError::Data { key, check, .. } => write!(f, "key {} is not valid data for its format: {check}", key + 1),
213        }
214    }
215}
216
217/// A sort's keys, most significant first, and how their bytes are read.
218#[derive(Clone, Debug, PartialEq, Eq)]
219pub struct Keys {
220    pub keys: Vec<Key>,
221    /// The order of CH keys.
222    pub collating: Collating,
223    /// The order of AC keys.
224    pub ascii: Collating,
225    /// None reads decimal keys as DFSORT does; Some reads them as a COBOL program under this
226    /// NUMPROC reads a signed item, refusing invalid data (ironwork's sort-keys strict).
227    pub strict: Option<Numproc>,
228}
229
230impl Keys {
231    /// CH keys in EBCDIC's order, AC keys in ASCII's by `page`, decimal keys as DFSORT reads them.
232    pub fn new(keys: Vec<Key>, page: &CodePage) -> Self {
233        Keys { keys, collating: Collating::Ebcdic, ascii: Collating::ascii(page), strict: None }
234    }
235
236    /// Each key's direction, as [`order`] takes them.
237    pub fn ascending(&self) -> Vec<bool> {
238        self.keys.iter().map(|k| k.ascending).collect()
239    }
240
241    /// The values of `record`'s keys; `index` is the record's place, which an error names.
242    pub fn values(&self, record: &[u8], index: usize) -> Result<Vec<KeyValue>, KeyError> {
243        let mut out = Vec::with_capacity(self.keys.len());
244        for (n, k) in self.keys.iter().enumerate() {
245            let bytes = record.get(k.position..k.position + k.length).ok_or(KeyError::Short { record: index, length: record.len() })?;
246            out.push(match k.format {
247                Format::Ch => KeyValue::Collated(self.collating.collate(bytes)),
248                Format::Ac => KeyValue::Collated(self.ascii.collate(bytes)),
249                Format::Bi => KeyValue::Collated(bytes.to_vec()),
250                Format::Fi => KeyValue::Collated(bytes.iter().enumerate().map(|(i, &b)| if i == 0 { b ^ 0x80 } else { b }).collect()),
251                decimal_format => match self.strict {
252                    Some(numproc) => {
253                        let read = strict(bytes, decimal_format, numproc).map_err(|check| KeyError::Data { record: index, key: n, check })?;
254                        KeyValue::Read(Val::Num(read))
255                    }
256                    None => match decimal(bytes, decimal_format) {
257                        Some((negative, digits)) => KeyValue::Decimal { negative, digits },
258                        None => KeyValue::Collated(Vec::new()),
259                    },
260                },
261            });
262        }
263        Ok(out)
264    }
265
266    pub fn compare(&self, a: &[u8], b: &[u8]) -> Result<Ordering, KeyError> {
267        Ok(order(&self.values(a, 0)?, &self.values(b, 1)?, &self.ascending()))
268    }
269
270    /// The records in key order; records with equal keys keep the order they came in, as DFSORT's
271    /// EQUALS keeps them. With no keys, the records as they came (SORT FIELDS=COPY).
272    pub fn sort(&self, records: Vec<Vec<u8>>) -> Result<Vec<Vec<u8>>, KeyError> {
273        let mut entries = Vec::with_capacity(records.len());
274        for (i, record) in records.into_iter().enumerate() {
275            let values = self.values(&record, i)?;
276            entries.push((record, values));
277        }
278        let ascending = self.ascending();
279        entries.sort_by(|a, b| order(&a.1, &b.1, &ascending));
280        Ok(entries.into_iter().map(|(record, _)| record).collect())
281    }
282
283    /// The first record that sorts before the one ahead of it, which a MERGE's input may not hold.
284    pub fn out_of_order(&self, records: &[Vec<u8>]) -> Result<Option<usize>, KeyError> {
285        let ascending = self.ascending();
286        let mut last: Option<Vec<KeyValue>> = None;
287        for (i, record) in records.iter().enumerate() {
288            let values = self.values(record, i)?;
289            if last.as_ref().is_some_and(|l| order(l, &values, &ascending) == Ordering::Greater) {
290                return Ok(Some(i));
291            }
292            last = Some(values);
293        }
294        Ok(None)
295    }
296}
297
298/// A decimal key read as a signed item of its format is, as a COBOL program reads it.
299fn strict(bytes: &[u8], format: Format, numproc: Numproc) -> Result<numeric::precision::Fixed, ProgramCheck> {
300    let shortest = if matches!(format, Format::Csl | Format::Cst) { 2 } else { 1 };
301    if bytes.len() < shortest {
302        return Err(ProgramCheck::Data);
303    }
304    let d = match format {
305        Format::Pd => codec::packed(bytes, true, numproc)?,
306        _ => codec::zoned(bytes, true, format.sign(), numproc)?,
307    };
308    Ok(fixed(d.negative, U256::from_u128(d.magnitude), Places::new(31, 0)))
309}
ironwork_rt/sort/keys.rs

ironwork_rt/sort/
keys.rs
