common/
lib.rs

1//! Core types and abstractions used in Texcraft.
2//!
3//!
4
5use std::fmt::Write;
6
7/// Trait satisfied by font formats (like .tfm files).
8pub trait FontFormat: Sized {
9    const DEFAULT_FILE_EXTENSION: &'static str;
10    type Error: std::error::Error + 'static;
11
12    /// Parse binary data into a font.
13    fn parse(b: &[u8]) -> Result<Self, Self::Error>;
14}
15
16/// Scaled numbers.
17///
18/// This is a fixed-width numeric type used in throughout TeX.
19/// This type is defined and described in part 7 "arithmetic with scaled
20/// dimensions" starting at TeX.2021.99.
21///
22/// This numeric type has 15 bits for the integer part,
23/// 16 bits for the fractional part, and a single signed bit.
24/// The inner value is the number multiplied by 2^16.
25#[derive(Default, PartialEq, Eq, Debug, Copy, Clone, PartialOrd, Ord, Hash)]
26#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
27pub struct Scaled(pub i32);
28
29impl Scaled {
30    /// Representation of the number 0 as a [Scaled].
31    pub const ZERO: Scaled = Scaled(0);
32
33    /// Representation of the number 1 as a [Scaled].
34    pub const ONE: Scaled = Scaled(1 << 16);
35
36    /// Representation of the number 2 as a [Scaled].
37    pub const TWO: Scaled = Scaled(1 << 17);
38
39    /// Maximum possible dimension in TeX, which is (2^30-1)/2^16.
40    ///
41    /// This is _not_ the maximum size of the Rust scaled number type, which is (2^31-1)/2^16.
42    ///
43    /// Defined in TeX.2021.421.
44    pub const MAX_DIMEN: Scaled = Scaled((1 << 30) - 1);
45
46    /// Create a scaled number corresponding the provided positive integer.
47    ///
48    /// Scaled numbers are in the range `(-2^14, 2^14)`.
49    /// If _i_ is outside this range an overflow error is returned.
50    pub fn from_integer(i: i32) -> Result<Scaled, OverflowError> {
51        if i >= (1 << 14) || i <= -(1 << 14) {
52            Err(OverflowError {})
53        } else {
54            Ok(Scaled(Scaled::ONE.0 * i))
55        }
56    }
57
58    /// Creates a scaled number from a decimal fraction.
59    ///
60    /// TeX.2021.102.
61    pub fn from_decimal_digits(digits: &[u8]) -> Scaled {
62        let mut a = 0;
63        for d in digits.iter().rev() {
64            a = (a + (*d as i32) * Scaled::TWO.0) / 10
65        }
66        Scaled((a + 1) / 2)
67    }
68
69    /// Creates a scaled number from the provided components.
70    ///
71    /// TeX.2021.458
72    pub fn new(
73        integer_part: i32,
74        fractional_part: Scaled,
75        scaled_unit: ScaledUnit,
76    ) -> Result<Scaled, OverflowError> {
77        if scaled_unit == ScaledUnit::ScaledPoint {
78            return if integer_part > Scaled::MAX_DIMEN.0 {
79                Err(OverflowError)
80            } else {
81                // For sp units, the fractional part is silently dropped.
82                Ok(Scaled(integer_part))
83            };
84        }
85        let (n, d) = scaled_unit.conversion_fraction();
86        // xn_over_d, but with integer arguments
87        let (Scaled(i), Scaled(remainder)) = Scaled(integer_part).xn_over_d(n, d)?;
88        let f =
89            fractional_part.nx_plus_y(n, Scaled::from_integer(remainder).expect("remainder<d<=7200<2^13, so a valid scaled number"))
90            .expect("fractional_part<2^16, remainder<2^16*d, so nx_plus_y<2^16(n+d). Each (n,d) makes this <2^30")
91            / d;
92        let integer_part = Scaled::from_integer(i + f.integer_part())?;
93        Ok(integer_part + f.fractional_part())
94    }
95
96    /// Calculates the integer division _xn_/_d_ and remainder, where _x_ is this scaled number
97    /// and _n_ and _d_ are integers in the range `[0,2^16]`.
98    ///
99    /// This function appears in TeX.2021.107. Knuth is working with 32-bit integers
100    /// and so calculating this number is tricky without overflowing. E.g. _xn_ may
101    /// be larger than `2^32-1` even if the final result is in range.
102    /// TeX has an algorithm that calculates the exact value without overflowing,
103    /// in the case when the final result is in range.
104    ///
105    /// Our implementation simply uses 64-bit integers.
106    pub fn xn_over_d(&self, n: i32, d: i32) -> Result<(Scaled, Scaled), OverflowError> {
107        debug_assert!(n <= 0o200000);
108        debug_assert!(d <= 0o200000);
109        let mut b: i64 = self.0.into();
110        b *= n as i64; // can't overflow because |b|<=2^31 and |n|<=2^16
111        let remainder: i32 = (b % (d as i64)).try_into().expect("d<=2^16 so b%d<2^16");
112        b /= d as i64;
113        if b < -(Scaled::MAX_DIMEN.0 as i64) || b > Scaled::MAX_DIMEN.0 as i64 {
114            return Err(OverflowError {});
115        }
116        let b: i32 = b.try_into().expect("b in (-2^30, +2^30)");
117        Ok((Scaled(b), Scaled(remainder)))
118    }
119
120    /// TeX.2021.105
121    pub fn nx_plus_y(self, mut n: i32, y: Scaled) -> Result<Scaled, OverflowError> {
122        let max_answer = Scaled::MAX_DIMEN;
123        if n == 0 {
124            return Ok(y);
125        }
126        let mut x = self;
127        if n < 0 {
128            n = -n;
129            x = -x;
130        }
131        if x <= (max_answer - y) / n && -x <= (max_answer + y) / n {
132            Ok(x * n + y)
133        } else {
134            Err(OverflowError {})
135        }
136    }
137
138    /// Parses a scaled number from a string of the form `<integer>[.<fraction>]<unit>`.
139    ///
140    /// The unit must be one of the two-character abbreviations recognized by [`ScaledUnit::parse`]
141    /// (e.g. `"pt"`, `"in"`, `"cm"`). The fractional part is optional.
142    pub fn parse_from_string(s: &str) -> Result<Scaled, String> {
143        if s.len() < 3 {
144            return Err(format!(
145                "invalid dimension {s:?}: expected <number><unit> (e.g. 100pt)"
146            ));
147        }
148        let (value_str, unit_str) = s.split_at(s.len() - 2);
149        let unit = ScaledUnit::parse(unit_str)
150            .ok_or_else(|| format!("invalid unit {unit_str:?} in dimension {s:?}"))?;
151        let (int_str, frac_str) = match value_str.find('.') {
152            Some(pos) => (&value_str[..pos], &value_str[pos + 1..]),
153            None => (value_str, ""),
154        };
155        let integer_part: i32 = int_str
156            .parse()
157            .map_err(|_| format!("invalid number {int_str:?} in dimension {s:?}"))?;
158        let frac_digits: Vec<u8> = frac_str.chars().map(|c| c as u8 - b'0').collect();
159        if frac_digits.iter().any(|&d| d > 9) {
160            return Err(format!(
161                "invalid fractional part {frac_str:?} in dimension {s:?}"
162            ));
163        }
164        let fractional_part = Scaled::from_decimal_digits(&frac_digits);
165        Scaled::new(integer_part, fractional_part, unit)
166            .map_err(|_| format!("dimension {s:?} is out of range"))
167    }
168
169    pub fn integer_part(self) -> i32 {
170        self.0 / Scaled::ONE.0
171    }
172
173    pub fn fractional_part(self) -> Scaled {
174        self % Scaled::ONE.0
175    }
176
177    pub fn abs(self) -> Scaled {
178        Scaled(self.0.abs())
179    }
180
181    pub fn wrapping_add(self, rhs: Scaled) -> Self {
182        Scaled(self.0.wrapping_add(rhs.0))
183    }
184    pub fn checked_add(self, rhs: Scaled) -> Option<Self> {
185        Some(Scaled(self.0.checked_add(rhs.0)?))
186    }
187    pub fn wrapping_mul(self, rhs: i32) -> Self {
188        Scaled(self.0.wrapping_mul(rhs))
189    }
190    pub fn checked_mul(self, rhs: i32) -> Option<Self> {
191        // TODO: need to really probe the overflow behavior here!
192        // I actually think it's correct, but we should add tests.
193        self.nx_plus_y(rhs, Scaled::ZERO).ok()
194    }
195    pub fn checked_div(self, rhs: i32) -> Option<Self> {
196        Some(Scaled(self.0.checked_div(rhs)?))
197    }
198    // TeX.2021.103 print_scaled
199    pub fn display_no_units(self) -> impl std::fmt::Display {
200        struct D {
201            s: Scaled,
202        }
203        impl std::fmt::Display for D {
204            fn fmt(&self, fm: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
205                if self.s.0 < 0 {
206                    write!(fm, "-")?;
207                }
208                write!(fm, "{}.", self.s.integer_part().abs())?;
209                // Fractional part
210                let mut f = self.s.fractional_part().abs() * 10 + Scaled(5);
211                let mut delta = Scaled(10);
212                loop {
213                    if delta > Scaled::ONE {
214                        // round the last digit
215                        f += Scaled(0o100000 - 50000);
216                    }
217                    fm.write_char(
218                        char::from_digit(f.integer_part().try_into().unwrap(), 10).unwrap(),
219                    )?;
220                    f = f.fractional_part() * 10;
221                    delta = delta * 10;
222                    if f <= delta {
223                        break;
224                    }
225                }
226                Ok(())
227            }
228        }
229        D { s: self }
230    }
231}
232
233#[derive(Debug)]
234pub struct OverflowError;
235
236impl std::fmt::Display for Scaled {
237    fn fmt(&self, fm: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
238        // Integer part
239        write!(fm, "{}", self.display_no_units())?;
240        // Units
241        write!(fm, "pt")?;
242        Ok(())
243    }
244}
245
246impl std::iter::Sum for Scaled {
247    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
248        Self(iter.map(|s| s.0).sum())
249    }
250}
251
252impl std::ops::Add<Scaled> for Scaled {
253    type Output = Scaled;
254    fn add(self, rhs: Scaled) -> Self::Output {
255        Scaled(self.0 + rhs.0)
256    }
257}
258
259impl std::ops::AddAssign<Scaled> for Scaled {
260    fn add_assign(&mut self, rhs: Scaled) {
261        self.0 += rhs.0;
262    }
263}
264
265impl std::ops::Sub<Scaled> for Scaled {
266    type Output = Scaled;
267    fn sub(self, rhs: Scaled) -> Self::Output {
268        Scaled(self.0 - rhs.0)
269    }
270}
271
272impl std::ops::SubAssign<Scaled> for Scaled {
273    fn sub_assign(&mut self, rhs: Scaled) {
274        self.0 -= rhs.0;
275    }
276}
277
278impl std::ops::Mul<i32> for Scaled {
279    type Output = Scaled;
280    fn mul(self, rhs: i32) -> Self::Output {
281        Scaled(self.0 * rhs)
282    }
283}
284
285impl std::ops::Div<i32> for Scaled {
286    type Output = Scaled;
287    fn div(self, rhs: i32) -> Self::Output {
288        Scaled(self.0 / rhs)
289    }
290}
291
292impl std::ops::DivAssign<i32> for Scaled {
293    fn div_assign(&mut self, rhs: i32) {
294        self.0 = self.0 / rhs
295    }
296}
297
298impl std::ops::Rem<i32> for Scaled {
299    type Output = Scaled;
300    fn rem(self, rhs: i32) -> Self::Output {
301        Scaled(self.0 % rhs)
302    }
303}
304
305impl std::ops::Neg for Scaled {
306    type Output = Scaled;
307    fn neg(self) -> Self::Output {
308        Scaled(-self.0)
309    }
310}
311
312/// Unit used to define a scaled integer
313///
314/// Defined in TeX.2021.458 and chapter 10 of the TeX book.
315#[derive(Debug, Clone, Copy, PartialEq, Eq)]
316pub enum ScaledUnit {
317    Point,
318    Pica,
319    Inch,
320    BigPoint,
321    Centimeter,
322    Millimeter,
323    DidotPoint,
324    Cicero,
325    ScaledPoint,
326}
327
328impl ScaledUnit {
329    /// Parses a unit from a two character abbreviation.
330    ///
331    /// E.g., `"pc"` is parsed to [`ScaledUnit::Pica`].
332    /// These are abreviations are defined in TeX.2021.458 and chapter 10 of the TeX book.
333    pub fn parse(s: &str) -> Option<Self> {
334        use ScaledUnit::*;
335        Some(match s {
336            "pt" => Point,
337            "pc" => Pica,
338            "in" => Inch,
339            "bp" => BigPoint,
340            "cm" => Centimeter,
341            "mm" => Millimeter,
342            "dd" => DidotPoint,
343            "cc" => Cicero,
344            "sp" => ScaledPoint,
345            _ => return None,
346        })
347    }
348
349    /// Returns the fraction needed to convert to/from this unit to points.
350    ///
351    /// The return value is of the form (_n_, _d_).
352    /// If a scaled number represents _x_in these units (e.g. y [`ScaledUnit::Pica`]),
353    ///     then it is _y_=_nx_/_d_ points.
354    ///
355    /// Defined in TeX.2021.458.
356    pub fn conversion_fraction(&self) -> (i32, i32) {
357        use ScaledUnit::*;
358        match self {
359            Point => (1, 1),
360            Pica => (12, 1),
361            Inch => (7227, 100),
362            BigPoint => (7227, 7200),
363            Centimeter => (7227, 254),
364            Millimeter => (7227, 2540),
365            DidotPoint => (1238, 1157),
366            Cicero => (14856, 1157),
367            ScaledPoint => (1, 1 << 16),
368        }
369    }
370}
371
372/// Glue.
373///
374/// In Knuth's TeX this struct is not passed around directly; instead
375/// Knuth essentially uses `std::rc::Rc<Glue>`.
376/// This optimization is based on the fact that very few distinct glue
377/// values appear in a document, and that the pointer takes up less
378/// space than the struct.
379/// We might consider performing such an optimization.
380///
381/// Described in TeX.2021.150.
382#[derive(Copy, Clone, Debug, PartialEq, Eq, Default)]
383#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
384pub struct Glue {
385    pub width: Scaled,
386    pub stretch: Scaled,
387    pub stretch_order: GlueOrder,
388    pub shrink: Scaled,
389    pub shrink_order: GlueOrder,
390}
391
392impl Glue {
393    pub const ZERO: Glue = Glue {
394        width: Scaled::ZERO,
395        stretch: Scaled::ZERO,
396        stretch_order: GlueOrder::Normal,
397        shrink: Scaled::ZERO,
398        shrink_order: GlueOrder::Normal,
399    };
400    pub fn is_zero(&self) -> bool {
401        self.width == Scaled::ZERO && self.stretch == Scaled::ZERO && self.shrink == Scaled::ZERO
402    }
403}
404
405impl std::ops::Mul<i32> for Glue {
406    type Output = Glue;
407    fn mul(self, rhs: i32) -> Self::Output {
408        Glue {
409            width: self.width * rhs,
410            stretch: self.stretch * rhs,
411            stretch_order: self.stretch_order,
412            shrink: self.shrink * rhs,
413            shrink_order: self.shrink_order,
414        }
415    }
416}
417
418impl Glue {
419    /// TeX.2021.1239
420    pub fn wrapping_add(self, rhs: Glue) -> Self {
421        use std::cmp::Ordering::*;
422        Glue {
423            width: self.width.wrapping_add(rhs.width),
424            stretch: match self.stretch_order.cmp(&rhs.stretch_order) {
425                Less => rhs.stretch,
426                Equal => self.stretch.wrapping_add(rhs.stretch),
427                Greater => self.stretch,
428            },
429            stretch_order: self.stretch_order.max(rhs.stretch_order),
430            shrink: match self.shrink_order.cmp(&rhs.shrink_order) {
431                Less => rhs.shrink,
432                Equal => self.shrink.wrapping_add(rhs.shrink),
433                Greater => self.shrink,
434            },
435            shrink_order: self.shrink_order.max(rhs.shrink_order),
436        }
437    }
438    pub fn checked_add(self, rhs: Glue) -> Option<Self> {
439        use std::cmp::Ordering::*;
440        Some(Glue {
441            width: self.width.checked_add(rhs.width)?,
442            stretch: match self.stretch_order.cmp(&rhs.stretch_order) {
443                Less => rhs.stretch,
444                Equal => self.stretch.checked_add(rhs.stretch)?,
445                Greater => self.stretch,
446            },
447            stretch_order: self.stretch_order.max(rhs.stretch_order),
448            shrink: match self.shrink_order.cmp(&rhs.shrink_order) {
449                Less => rhs.shrink,
450                Equal => self.shrink.checked_add(rhs.shrink)?,
451                Greater => self.shrink,
452            },
453            shrink_order: self.shrink_order.max(rhs.shrink_order),
454        })
455    }
456    pub fn checked_mul(self, rhs: i32) -> Option<Self> {
457        Some(Glue {
458            width: self.width.checked_mul(rhs)?,
459            stretch: self.stretch.checked_mul(rhs)?,
460            stretch_order: self.stretch_order,
461            shrink: self.shrink.checked_mul(rhs)?,
462            shrink_order: self.shrink_order,
463        })
464    }
465    pub fn wrapping_mul(self, rhs: i32) -> Self {
466        Glue {
467            width: self.width.wrapping_mul(rhs),
468            stretch: self.stretch.wrapping_mul(rhs),
469            stretch_order: self.stretch_order,
470            shrink: self.shrink.wrapping_mul(rhs),
471            shrink_order: self.shrink_order,
472        }
473    }
474    pub fn checked_div(self, rhs: i32) -> Option<Self> {
475        Some(Glue {
476            width: self.width.checked_div(rhs)?,
477            stretch: self.stretch.checked_div(rhs)?,
478            stretch_order: self.stretch_order,
479            shrink: self.shrink.checked_div(rhs)?,
480            shrink_order: self.shrink_order,
481        })
482    }
483}
484
485impl std::fmt::Display for Glue {
486    // TeX.2021.177 print_spec with s="pt"
487    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
488        write!(f, "{}", self.width)?;
489        if self.stretch != Scaled::ZERO {
490            write!(f, " plus ")?;
491            write!(f, "{}", self.stretch.display_no_units())?;
492            write!(f, "{}", self.stretch_order)?;
493        }
494        if self.shrink != Scaled::ZERO {
495            write!(f, " minus ")?;
496            write!(f, "{}", self.shrink.display_no_units())?;
497            write!(f, "{}", self.shrink_order)?;
498        }
499        Ok(())
500    }
501}
502
503/// Order of infinity of a glue stretch or shrink.
504///
505/// When setting a list of boxes, TeX stretches or shrinks glue boxes.
506/// In some cases it is desirable that TeX only stretches some subset of the
507/// glue boxes.
508/// For example, when setting centered text, TeX only stretches the two glue
509/// boxes at each end of the list and leaves all other glue intact.
510///
511/// To achieve this, each glue stretch or shrink has an order of infinity.
512/// If a list contains glue of some order (e.g. [GlueOrder::Fil]),
513/// then glues of a lower order (e.g. [GlueOrder::Normal]) are not stretched
514/// or shrunk.
515#[derive(Clone, Copy, Debug, PartialEq, Eq, Default, PartialOrd, Ord)]
516#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
517pub enum GlueOrder {
518    #[default]
519    Normal,
520    Fil,
521    Fill,
522    Filll,
523}
524
525impl GlueOrder {
526    /// Parses an infinite glue order from a keyword.
527    pub fn parse(s: &str) -> Option<Self> {
528        use GlueOrder::*;
529        Some(match s {
530            "fil" => Fil,
531            "fill" => Fill,
532            "filll" => Filll,
533            _ => return None,
534        })
535    }
536    pub fn inf_str(&self) -> Option<&'static str> {
537        use GlueOrder::*;
538        match self {
539            Normal => None,
540            Fil => Some("fil"),
541            Fill => Some("fill"),
542            Filll => Some("filll"),
543        }
544    }
545    /// Returns the next highest glue order.
546    pub fn next(&self) -> Option<Self> {
547        use GlueOrder::*;
548        match self {
549            Normal => Some(Fil),
550            Fil => Some(Fill),
551            Fill => Some(Filll),
552            Filll => None,
553        }
554    }
555}
556
557impl std::fmt::Display for GlueOrder {
558    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
559        write!(f, "{}", self.inf_str().unwrap_or("pt"))
560    }
561}
562
563#[cfg(test)]
564mod tests {
565    use super::*;
566
567    #[test]
568    fn type_sizes() {
569        assert_eq!(16, std::mem::size_of::<Glue>());
570    }
571
572    macro_rules! parse_from_string_tests {
573        ( $( $name:ident : $input:expr => $expected:expr, )* ) => {
574            $(
575                #[test]
576                fn $name() {
577                    assert_eq!(Scaled::parse_from_string($input), $expected);
578                }
579            )*
580        };
581    }
582
583    parse_from_string_tests! {
584        // Basic unit types
585        integer_pt:    "100pt"  => Ok(Scaled::new(100, Scaled::ZERO, ScaledUnit::Point).unwrap()),
586        integer_pc:    "6pc"    => Ok(Scaled::new(6,   Scaled::ZERO, ScaledUnit::Pica).unwrap()),
587        integer_in:    "2in"    => Ok(Scaled::new(2,   Scaled::ZERO, ScaledUnit::Inch).unwrap()),
588        integer_bp:    "72bp"   => Ok(Scaled::new(72,  Scaled::ZERO, ScaledUnit::BigPoint).unwrap()),
589        integer_cm:    "10cm"   => Ok(Scaled::new(10,  Scaled::ZERO, ScaledUnit::Centimeter).unwrap()),
590        integer_mm:    "25mm"   => Ok(Scaled::new(25,  Scaled::ZERO, ScaledUnit::Millimeter).unwrap()),
591        integer_dd:    "10dd"   => Ok(Scaled::new(10,  Scaled::ZERO, ScaledUnit::DidotPoint).unwrap()),
592        integer_cc:    "3cc"    => Ok(Scaled::new(3,   Scaled::ZERO, ScaledUnit::Cicero).unwrap()),
593        integer_sp:    "65536sp" => Ok(Scaled(65536)),
594        // Fractional part
595        fractional_pt: "72.27pt" => Ok(Scaled::new(72, Scaled::from_decimal_digits(&[2, 7]), ScaledUnit::Point).unwrap()),
596        fractional_in: "6.5in"  => Ok(Scaled::new(6,  Scaled::from_decimal_digits(&[5]),    ScaledUnit::Inch).unwrap()),
597        // Zero
598        zero_pt:       "0pt"    => Ok(Scaled::ZERO),
599        // Error cases
600        empty:         ""       => Err("invalid dimension \"\": expected <number><unit> (e.g. 100pt)".to_string()),
601        bad_unit:      "10xx"   => Err("invalid unit \"xx\" in dimension \"10xx\"".to_string()),
602        bad_number:    "abpt"   => Err("invalid number \"ab\" in dimension \"abpt\"".to_string()),
603        bad_fraction:  "1.xpt"  => Err("invalid fractional part \"x\" in dimension \"1.xpt\"".to_string()),
604    }
605
606    #[test]
607    fn print_smallest_scaled() {
608        assert_eq!("-32768.0pt", format!("{}", Scaled(i32::MIN)));
609    }
610
611    #[test]
612    fn glue_order_ordering() {
613        assert!(GlueOrder::Normal < GlueOrder::Fil);
614        assert!(GlueOrder::Fil < GlueOrder::Fill);
615        assert!(GlueOrder::Fill < GlueOrder::Filll);
616    }
617}
common/lib.rs

common/
lib.rs
