oxedyne/fe2o3/fe2o3_text/src/outline.rs
4.1 KiB, 29 runs
created by r3767465682:77350, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! The outline of indented text: its landmark lines, down to the deepest indentation that fits |
| 2 | //! a byte budget. |
| 3 | //! |
| 4 | //! A landmark is a line holding a letter or a digit, so blank lines and lone closers (`}`, `);`) |
| 5 | //! are not. Its depth is the width of its leading whitespace. Adjacent landmarks that open with |
| 6 | //! the same indentation and word, a block of `use` or `import` lines, make one entry, |
| 7 | //! `12-30\tuse … (19 lines)`; blank lines between them do not part them. The first pass sums the |
| 8 | //! bytes the entries at each depth would take, the outline takes every depth whose running sum |
| 9 | //! fits, and the second pass writes it, so memory is bounded on any file. |
| 10 | //! |
| 11 | //! Lines are read through [`crate::bounded`], keeping the first `KEEP` bytes of each, so a line of any |
| 12 | //! length costs no more; a NUL means the text is binary, and it has no outline. |
| 13 | //! |
| 14 | //! Nothing about a language is known, and nesting is read from indentation alone. Text with no |
| 15 | //! nesting, a log or a table, or prose whose headings share the margin with its paragraphs, has |
| 16 | //! no outline that fits, and neither has text that is one entry. |
| 17 | |
| 18 | use crate::bounded::line; |
| 19 | |
| 20 | use oxedyne_fe2o3_core::prelude::*; |
| 21 | |
| 22 | use std::{ |
| 23 | collections::BTreeMap, |
| 24 | io::{BufRead, Seek}, |
| 25 | }; |
| 26 | |
| 27 | |
| 28 | const CUT: usize = 100; // characters of an entry's text kept, enough to name an item |
| 29 | const KEEP: usize = 4 * (CUT + 1); // fixed: bytes holding CUT characters and the next, at most four bytes each |
| 30 | |
| 31 | #[derive(Clone, Debug, Default, Eq, PartialEq)] |
| 32 | pub struct Outline { |
| 33 | pub text: String, // one `N\ttext\n` row per entry |
| 34 | pub lines: u64, // in the whole text |
| 35 | } |
| 36 | |
| 37 | /// The outline of the text `r` holds from its start, in at most `budget` bytes, or `None` when |
| 38 | /// not even its outermost depth fits, or it holds a NUL. |
| 39 | pub fn outline<R: BufRead + Seek>(r: &mut R, budget: usize) -> Outcome<Option<Outline>> { |
| 40 | let mut cost = BTreeMap::<usize, (usize, usize)>::new(); // depth to bytes and entries |
| 41 | let lines = match res!(walk(r, |e| { |
| 42 | let c = cost.entry(e.depth).or_insert((0, 0)); |
| 43 | c.0 += e.row().len(); |
| 44 | c.1 += 1; |
| 45 | })) { |
| 46 | Some(n) => n, |
| 47 | None => return Ok(None), |
| 48 | }; |
| 49 | let mut sum = (0, 0); |
| 50 | let mut deepest = None; |
| 51 | for (d, (bytes, n)) in &cost { |
| 52 | if sum.0 + bytes > budget { |
| 53 | break; |
| 54 | } |
| 55 | sum = (sum.0 + bytes, sum.1 + n); |
| 56 | deepest = Some(*d); |
| 57 | } |
| 58 | let deepest = match (deepest, sum.1 > 1) { |
| 59 | (Some(d), true) => d, |
| 60 | _ => return Ok(None), |
| 61 | }; |
| 62 | let mut text = String::with_capacity(sum.0); |
| 63 | if res!(walk(r, |e| if e.depth <= deepest { |
| 64 | text.push_str(&e.row()); |
| 65 | })).is_none() { |
| 66 | return Ok(None); |
| 67 | } |
| 68 | Ok(Some(Outline { text, lines })) |
| 69 | } |
| 70 | |
| 71 | // A run of adjacent landmarks with one head. |
| 72 | struct Entry { |
| 73 | depth: usize, |
| 74 | first: u64, |
| 75 | last: u64, |
| 76 | text: String, // the first line's, cut |
| 77 | } |
| 78 | |
| 79 | impl Entry { |
| 80 | fn row(&self) -> String { |
| 81 | match self.first == self.last { |
| 82 | true => fmt!("{}\t{}\n", self.first, self.text), |
| 83 | false => fmt!("{}-{}\t{} … ({} lines)\n", |
| 84 | self.first, self.last, head(&self.text), self.last - self.first + 1), |
| 85 | } |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | // Calls `f` on each entry from the start of the text and returns its line count, or `None` at a NUL. |
| 90 | fn walk<R: BufRead + Seek, F: FnMut(&Entry)>(r: &mut R, mut f: F) -> Outcome<Option<u64>> { |
| 91 | res!(r.rewind(), IO, Read); |
| 92 | let mut buf = Vec::new(); |
| 93 | let mut n = 0u64; |
| 94 | let mut run: Option<Entry> = None; |
| 95 | while let Some(l) = res!(line(r, &mut buf, 0, KEEP)) { |
| 96 | if l.nul { |
| 97 | return Ok(None); |
| 98 | } |
| 99 | n += 1; |
| 100 | let s = String::from_utf8_lossy(&buf); |
| 101 | let s = s.trim_end(); |
| 102 | if s.is_empty() { |
| 103 | continue; |
| 104 | } |
| 105 | let s = cut(s); |
| 106 | let mark = s.chars().any(char::is_alphanumeric); |
| 107 | if let Some(e) = &mut run { |
| 108 | if mark && head(&e.text) == head(&s) { |
| 109 | e.last = n; |
| 110 | continue; |
| 111 | } |
| 112 | f(e); |
| 113 | run = None; |
| 114 | } |
| 115 | if mark { |
| 116 | run = Some(Entry { depth: s.len() - s.trim_start().len(), first: n, last: n, text: s.to_string() }); |
| 117 | } |
| 118 | } |
| 119 | if let Some(e) = &run { |
| 120 | f(e); |
| 121 | } |
| 122 | Ok(Some(n)) |
| 123 | } |
| 124 | |
| 125 | // The line's indentation and first word. |
| 126 | fn head(s: &str) -> &str { |
| 127 | let body = s.trim_start(); |
| 128 | let at = s.len() - body.len(); |
| 129 | &s[..at + body.find(char::is_whitespace).unwrap_or(body.len())] |
| 130 | } |
| 131 | |
| 132 | fn cut(s: &str) -> std::borrow::Cow<'_, str> { |
| 133 | match s.char_indices().nth(CUT) { |
| 134 | Some((i, _)) => fmt!("{}…", &s[..i]).into(), |
| 135 | None => s.into(), |
| 136 | } |
| 137 | } |