src/render.rs · j · git.iko.soy

git.iko.soy/j

on master help sign in

j/src/render.rs

3566 lines 134 kB history raw

1//! Display (§5.1) and tree rendering (§7.11).

3use crate::domain::ROOT_ID;

4use crate::eval::Interp;

5use crate::value::{Crash, ListVal, RecordMap, ShapeKind, Value};

6use std::cmp::Reverse;

7use std::collections::{BTreeMap, BTreeSet, BinaryHeap};

8use std::ops::Bound;

9use std::rc::Rc;

10use unicode_width::UnicodeWidthChar;

12// ----------------------------------------------------------------------

13// colour

14// ----------------------------------------------------------------------

16#[derive(Clone, Copy, PartialEq)]

17pub struct Palette {

18 pub on: bool,

19}

21impl Palette {

22 fn wrap(&self, code: &str, s: &str) -> String {

23 if self.on {

24 format!("\x1b[{}m{}\x1b[0m", code, s)

25 } else {

26 s.to_string()

27 }

28 }

29 pub fn bold(&self, s: &str) -> String {

30 self.wrap("1", s)

31 }

32 pub fn dim(&self, s: &str) -> String {

33 self.wrap("2", s)

34 }

35 pub fn bold_bg(&self, s: &str) -> String {

36 self.wrap("1;97;48;5;17", s)

37 }

38 pub fn dim_italic(&self, s: &str) -> String {

39 self.wrap("2;3", s)

40 }

41 pub fn cyan(&self, s: &str) -> String {

42 self.wrap("96", s)

43 }

44 pub fn red(&self, s: &str) -> String {

45 self.wrap("91", s)

46 }

47 pub fn blue(&self, s: &str) -> String {

48 self.wrap("94", s)

49 }

50 pub fn green(&self, s: &str) -> String {

51 self.wrap("92", s)

52 }

53 pub fn yellow(&self, s: &str) -> String {

54 self.wrap("93", s)

55 }

56 fn id(&self, s: &str) -> String {

57 self.wrap("1;95", s)

58 }

59 fn label(&self, s: &str) -> String {

60 self.wrap("1;92", s)

61 }

62 fn field(&self, s: &str) -> String {

63 self.wrap("2;96", s)

64 }

65 fn rail(&self, lane: usize, s: &str) -> String {

66 let codes = ["95", "96", "93", "92"];

67 self.wrap(codes[lane.saturating_sub(1) % codes.len()], s)

68 }

69 pub fn grey(&self, bright: u8, s: &str) -> String {

70 // grey scale: brighter when more recent

71 self.wrap(&format!("38;5;{}", 245 + bright.min(10)), s)

72 }

73 pub fn accent(&self, level: u8, s: &str) -> String {

74 // Size remains encoded by the bar's height, with a vivid cool-to-warm ramp.

75 let codes = ["96", "94", "95", "93", "1;93"];

76 self.wrap(codes[level.min(4) as usize], s)

77 }

78 pub fn author(&self, name: &str, s: &str) -> String {

79 // stable hue per author

80 let mut h: u32 = 5381;

81 for b in name.bytes() {

82 h = h.wrapping_mul(33).wrapping_add(b as u32);

83 }

84 let hue = (h % 6) as u8;

85 let code = ["91", "92", "93", "94", "95", "96"][hue as usize];

86 self.wrap(code, s)

87 }

88 /// colour with a raw ANSI code (used for meaning-coloured glyphs)

89 pub fn code(&self, code: &str, s: &str) -> String {

90 self.wrap(code, s)

91 }

92 /// Apply a background band across a whole line. The line already contains

93 /// colour codes whose `\x1b[0m` resets would clear the background mid-line,

94 /// so the background is re-applied after every reset. No-op when colour is

95 /// off, so the focus stays marked only by the `▶` gutter (§Colour).

96 pub fn bg_line(&self, bg: &str, s: &str) -> String {

97 if !self.on {

98 return s.to_string();

99 }

100 let onset = format!("\x1b[{}m", bg);

101 let reapply = format!("\x1b[0m{}", onset);

102 let body = s.replace("\x1b[0m", &reapply);

103 format!("{}{}\x1b[0m", onset, body)

104 }

105}

106

107pub fn color_enabled(mode: &str) -> bool {

108 if std::env::var_os("NO_COLOR")

109 .map(|v| !v.is_empty())

110 .unwrap_or(false)

111 {

112 return false;

113 }

114 match mode {

115 "always" => true,

116 "never" => false,

117 _ => std::env::var_os("TERM").map(|t| t != "dumb").unwrap_or(true)

118 && crate::show::stdout_is_tty(),

119 }

120}

121

122// display width with East Asian wide = 2, combining = 0

123pub fn width(s: &str) -> usize {

124 let mut w = 0;

125 let mut esc = false;

126 for c in s.chars() {

127 if esc {

128 if c == 'm' {

129 esc = false;

130 }

131 continue;

132 }

133 if c == '\x1b' {

134 esc = true;

135 continue;

136 }

137 w += UnicodeWidthChar::width(c).unwrap_or(0);

138 }

139 w

140}

141

142fn pad_right(s: &str, w: usize) -> String {

143 let d = width(s);

144 if d >= w {

145 s.to_string()

146 } else {

147 format!("{}{}", s, " ".repeat(w - d))

148 }

149}

150

151fn human_size(n: usize) -> String {

152 if n < 1024 {

153 format!("{} B", n)

154 } else if n < 1024 * 1024 {

155 format!("{:.1} KB", n as f64 / 1024.0)

156 } else {

157 format!("{:.1} MB", n as f64 / 1024.0 / 1024.0)

158 }

159}

160

161// ----------------------------------------------------------------------

162// shape recognition (§4.12/§5.1)

163// ----------------------------------------------------------------------

164

165fn field_set(v: &Value) -> Option<BTreeSet<String>> {

166 match v {

167 Value::Record(m) => Some(m.keys().cloned().collect()),

168 _ => None,

169 }

170}

171

172fn shape_of_record(interp: &Interp, v: &Value) -> Option<String> {

173 let fs = field_set(v)?;

174 // Only these named shapes have special display forms (§5.1). Searching

175 // every declaration let a custom alias win in HashMap iteration order,

176 // randomly turning Commit, Entry, etc. values into generic records.

177 // Resolve each configured shape so aliases and custom field sets still

178 // determine which records match.

179 for name in ["Commit", "Entry", "Subtree", "Repo", "Frame", "Change"] {

180 if let Some(s) = interp.shapes.shape_of(name) {

181 if let ShapeKind::Record(want) = &s.kind {

182 if want == &fs {

183 return Some(name.to_string());

184 }

185 }

186 }

187 }

188 None

189}

190

191pub fn is_commit(interp: &Interp, v: &Value) -> bool {

192 shape_of_record(interp, v).as_deref() == Some("Commit")

193}

194

195// ----------------------------------------------------------------------

196// display

197// ----------------------------------------------------------------------

198

199pub fn display(interp: &mut Interp, v: &Value, color: bool) -> Result<String, Crash> {

200 display_with_width(interp, v, color, tty_width())

201}

202

203/// Display column tables as if stdout had this width; `None` preserves full cells.

204pub fn display_with_width(

205 interp: &mut Interp,

206 v: &Value,

207 color: bool,

208 term_w: Option<usize>,

209) -> Result<String, Crash> {

210 let pal = Palette { on: color };

211 let mut out = String::new();

212 let mut loaded = None;

213 let mut todo = vec![Block::Of(v.clone(), 0)];

214 while let Some(block) = todo.pop() {

215 match block {

216 Block::Of(v, indent) => {

217 display_block(interp, &v, &pal, indent, &mut out, &mut loaded, &mut todo, term_w)?

218 }

219 Block::Items { xs, next, indent } => {

220 if let Some(x) = xs.get(next).cloned() {

221 // separated by a blank line

222 if next > 0 {

223 out.push('\n');

224 }

225 let next = next + 1;

226 todo.push(Block::Items { xs, next, indent });

227 todo.push(Block::Of(x, indent));

228 }

229 }

230 Block::Fields { m, after, name_w, indent } => display_fields(

231 interp,

232 &m,

233 after.as_deref(),

234 name_w,

235 &pal,

236 indent,

237 &mut out,

238 &mut loaded,

239 &mut todo,

240 )?,

241 }

242 }

243 if !out.ends_with('\n') {

244 out.push('\n');

245 }

246 Ok(out)

247}

248

249/// A block still to be displayed, or the rest of one that holds blocks

250/// (§5.1): a list shown one block per item, and a generic record, whose list

251/// fields print in block form under their key. Blocks nest as deep as the

252/// value's lists do, so `display` keeps them on a stack of its own instead of

253/// recursing: at about 14 KB of native stack a level in a debug build, a list

254/// nested as deep as the parser allows (§3.4) overflowed the worker's 512 MB,

255/// and one built at run time is not bounded at all.

256enum Block {

257 /// a value in block form, at an indent

258 Of(Value, usize),

259 /// a list's items from the `next`th on, one block each

260 Items { xs: ListVal, next: usize, indent: usize },

261 /// a generic record's fields after the field `after`, or all of them

262 Fields { m: Rc<RecordMap>, after: Option<String>, name_w: usize, indent: usize },

263}

264

265fn display_id(interp: &Interp, id: &str, pal: &Palette) -> String {

266 let p = interp.unique_prefix(id);

267 let n = p.len();

268 format!("{}{}", pal.id(p.as_str()), pal.dim(&id[n..]))

269}

270

271fn display_line(

272 interp: &mut Interp,

273 v: &Value,

274 pal: &Palette,

275 loaded: &mut Option<Loaded>,

276) -> Result<String, Crash> {

277 let v = &v.forced()?;

278 match v {

279 Value::Thunk(_) => unreachable!("forced never returns a thunk"),

280 Value::Int(n) => Ok(pal.yellow(&n.to_string())),

281 Value::Bool(b) => Ok(if *b { pal.green("true") } else { pal.red("false") }),

282 Value::Text(t) => Ok(first_line(t)),

283 Value::Id(id) => Ok(display_id(interp, id, pal)),

284 Value::Blob(b) => {

285 let size = human_size(b.size());

286 if b.is_unresolved() {

287 Ok(format!("‹✖ {}›", size))

288 } else {

289 Ok(format!("‹{}›", size))

290 }

291 }

292 // a lambda renders as its source (§5.2), which may run over several

293 // lines and hold comments; the line form keeps only the first

294 Value::Fun(_) => Ok(first_line(&crate::show::show(interp, v)?)),

295 Value::Shape(s) => Ok(pal.cyan(&s.name)),

296 Value::Record(_) => {

297 if let Some(shape) = shape_of_record(interp, v) {

298 match shape.as_str() {

299 "Commit" => return line_in(interp, v, pal, loaded, false),

300 "Entry" => return entry_line(interp, v, pal),

301 "Subtree" => return line_in(interp, &v.field("root")?, pal, loaded, false),

302 // its focus's line, drawn as the focus

303 "Repo" => return line_in(interp, &v.field("root")?, pal, loaded, true),

304 "Frame" => return line_in(interp, &v.field("parent")?, pal, loaded, false),

305 "Change" => {

306 let n = touched_paths(v)?.len();

307 return Ok(format!("{} paths", n));

308 }

309 _ => {}

310 }

311 }

312 let names: Vec<String> = field_set(v).unwrap().into_iter().collect();

313 Ok(format!("{{ {} }}", names.join(", ")))

314 }

315 Value::List(xs) => list_line(interp, xs, pal),

316 }

317}

318

319/// The line form of text that may run over several lines (§5.1): its first

320/// line, `…` if there are more.

321fn first_line(s: &str) -> String {

322 let mut lines = s.lines();

323 let first = lines.next().unwrap_or("");

324 if lines.next().is_some() {

325 format!("{}…", first)

326 } else {

327 first.to_string()

328 }

329}

330

331fn list_line(_interp: &Interp, xs: &[Value], pal: &Palette) -> Result<String, Crash> {

332 if xs.is_empty() {

333 return Ok("0 items".into());

334 }

335 let all_id = xs.iter().all(|x| matches!(x, Value::Id(_)));

336 if all_id {

337 return Ok(format!("{} commits", xs.len()));

338 }

339 let all_path = xs.iter().all(|x| match x {

340 Value::List(p) => p.iter().all(|c| matches!(c, Value::Text(_))),

341 _ => false,

342 });

343 if all_path {

344 return Ok(format!("{} paths", xs.len()));

345 }

346 let all_text = xs.iter().all(|x| matches!(x, Value::Text(_)));

347 if all_text {

348 return Ok(format!("{} items", xs.len()));

349 }

350 let all_record = xs.iter().all(|x| matches!(x, Value::Record(_)));

351 if all_record {

352 let first = field_set(&xs[0]).unwrap();

353 let same = xs

354 .iter()

355 .all(|x| field_set(x).map(|s| s == first).unwrap_or(false));

356 if same {

357 return Ok(format!("{} rows", xs.len()));

358 }

359 }

360 let all_scalar = xs.iter().all(|x| {

361 matches!(x, Value::Int(_) | Value::Bool(_))

362 });

363 if all_scalar {

364 let parts: Vec<String> = xs

365 .iter()

366 .map(|x| match x {

367 Value::Int(n) => pal.yellow(&n.to_string()),

368 Value::Bool(b) => if *b { pal.green("true") } else { pal.red("false") },

369 _ => unreachable!(),

370 })

371 .collect();

372 return Ok(parts.join(", "));

373 }

374 Ok(format!("{} items", xs.len()))

375}

376

377fn entry_line(interp: &Interp, v: &Value, pal: &Palette) -> Result<String, Crash> {

378 let path = path_string(&v.field("path")?)?;

379 let content = v.field("content")?;

380 let (size, unresolved) = match &content {

381 Value::Blob(b) => (human_size(b.size()), b.is_unresolved()),

382 _ => (String::new(), false),

383 };

384 let _ = interp;

385 if unresolved {

386 Ok(format!("{} {} {}", pal.red("✖"), pal.cyan(&path), pal.red(&size)))

387 } else {

388 Ok(format!(" {} {}", pal.cyan(&path), pal.yellow(&size)))

389 }

390}

391

392fn path_string(p: &Value) -> Result<String, Crash> {

393 let comps = p.as_list()?;

394 let parts: Vec<String> = comps

395 .iter()

396 .map(|c| c.as_text().map(|s| s.to_string()))

397 .collect::<Result<_, _>>()?;

398 Ok(parts.join("/"))

399}

400

401/// entries of one snapshot, keyed by path components

402type SnapMap = BTreeMap<Vec<String>, Value>;

403

404fn touched_paths(change: &Value) -> Result<Vec<(String, char, bool)>, Crash> {

405 let from = snapshot_map_of(&change.field("from")?)?;

406 let to = snapshot_map_of(&change.field("to")?)?;

407 Ok(touched_in_maps(&from, &to)?

408 .into_iter()

409 .map(|(p, mark, unresolved)| (p.join("/"), mark, unresolved))

410 .collect())

411}

412

413/// The changed paths between two snapshots that have already been keyed, as

414/// (path components, mark, unresolved). Both maps are sorted, so the union is

415/// a merge — the previous version collected every key of both sides into a

416/// `BTreeSet`, cloning each one.

417fn touched_in_maps(from: &SnapMap, to: &SnapMap) -> Result<Vec<(Vec<String>, char, bool)>, Crash> {

418 let mut out = Vec::new();

419 let mut fi = from.iter().peekable();

420 let mut ti = to.iter().peekable();

421 loop {

422 let ord = match (fi.peek(), ti.peek()) {

423 (None, None) => break,

424 (Some(_), None) => std::cmp::Ordering::Less,

425 (None, Some(_)) => std::cmp::Ordering::Greater,

426 (Some((fp, _)), Some((tp, _))) => fp.cmp(tp),

427 };

428 let (path, mark, t) = match ord {

429 std::cmp::Ordering::Less => {

430 let (p, _) = fi.next().unwrap();

431 (p, '−', None)

432 }

433 std::cmp::Ordering::Greater => {

434 let (p, v) = ti.next().unwrap();

435 (p, '+', Some(v))

436 }

437 std::cmp::Ordering::Equal => {

438 let (p, a) = fi.next().unwrap();

439 let (_, b) = ti.next().unwrap();

440 if crate::value::value_eq(a, b)? {

441 continue;

442 }

443 (p, '~', Some(b))

444 }

445 };

446 let unresolved = t

447 .map(|b| matches!(b, Value::Blob(bl) if bl.is_unresolved()))

448 .unwrap_or(false);

449 out.push((

450 path.clone(),

451 if unresolved { '✖' } else { mark },

452 unresolved,

453 ));

454 }

455 Ok(out)

456}

457

458/// The line count from which the size bar draws its last glyph, `▇` (§7.11

459/// column 5): no count past it changes the bar, so none is computed.

460const SIZE_BAR_TOP: usize = 1000;

461

462/// Lines added plus removed between two versions of one path (§7.11 size

463/// bar), either possibly absent, counted up to `cap`: the length of a

464/// shortest line diff, or `cap` if that is at least `cap`. Lines are split

465/// after each `\n` as `line_count` counts them. A conflict counts as its

466/// materialized text, as it is checked out.

467///

468/// A line diff costs the product of the file's length and the size of the

469/// change, so a plain one of a rewritten or reordered long file takes

470/// seconds. The search here stops at the cap rather than at a clock, so the

471/// same two versions always give the same count. Every step before it keeps

472/// the count exact: the common prefix and suffix are equal lines of some

473/// shortest diff, and the difference in length is a lower bound. A small

474/// change is then settled by a short search over the lines as they are.

475/// Otherwise a line that does not occur on the other side at all cannot be

476/// part of any common subsequence, so, as git's xdiff does, it counts as

477/// changed up front, and the rest is searched unless `reorder_bound` already

478/// puts it past the cap. That search (`line_distance`) costs at most about

479/// twice what a bit-parallel search of `cap / 64 + 2` machine words per line

480/// does, whatever the lines are: Myers' search soon stops on most content,

481/// but on a long file of a few lines repeating it can make a pass over the

482/// lines for each of the `2 × cap + 1` diagonals it reaches, so once it has

483/// cost half that the bit-parallel search counts instead. A million lines of

484/// two alternating, with 480 pairs of neighbours swapped, took Myers' search

485/// alone some 5 × 10⁸ comparisons.

486fn changed_lines(from: Option<&Value>, to: Option<&Value>, cap: usize) -> Result<usize, Crash> {

487 use std::collections::HashMap;

488 // the rounds of the first, short search

489 const QUICK: usize = 64;

490 let text = |v: Option<&Value>| -> Result<Vec<u8>, Crash> {

491 match v {

492 Some(Value::Blob(b)) => b.bytes(),

493 _ => Ok(Vec::new()),

494 }

495 };

496 let (a, b) = (text(from)?, text(to)?);

497 let a: Vec<&[u8]> = a.split_inclusive(|c| *c == b'\n').collect();

498 let b: Vec<&[u8]> = b.split_inclusive(|c| *c == b'\n').collect();

499 let (a, b) = trim_common(&a, &b);

500 if a.len().abs_diff(b.len()) >= cap {

501 return Ok(cap);

502 }

503 // the short search's few rounds bound what it costs, so no step limit

504 let quick = cap.min(QUICK);

505 match edit_distance(a, b, quick, usize::MAX, &mut 0) {

506 Some(d) if d < quick || quick == cap => return Ok(d),

507 _ => {}

508 }

509 // number each distinct line, so the rest compares numbers; the lines

510 // numbered while reading `a` are those that occur in it

511 fn number<'l>(ids: &mut HashMap<&'l [u8], usize>, lines: &[&'l [u8]]) -> Vec<usize> {

512 lines

513 .iter()

514 .map(|l| {

515 let next = ids.len();

516 *ids.entry(*l).or_insert(next)

517 })

518 .collect()

519 }

520 let mut ids = HashMap::new();

521 let a = number(&mut ids, a);

522 let in_a = ids.len();

523 let b = number(&mut ids, b);

524 let mut in_b = vec![false; ids.len()];

525 for l in &b {

526 in_b[*l] = true;

527 }

528 let a_common: Vec<usize> = a.iter().copied().filter(|l| in_b[*l]).collect();

529 let b_common: Vec<usize> = b.iter().copied().filter(|l| *l < in_a).collect();

530 let unmatched = (a.len() - a_common.len()) + (b.len() - b_common.len());

531 if unmatched >= cap {

532 return Ok(cap);

533 }

534 let (a, b) = trim_common(&a_common, &b_common);

535 let max = cap - unmatched;

536 if reorder_bound(a, b, ids.len()) >= max {

537 return Ok(cap);

538 }

539 Ok(unmatched + line_distance(a, b, ids.len(), max, &mut 0))

540}

541

542/// `a` and `b` without the lines they start and end with in common.

543fn trim_common<'s, T: PartialEq>(a: &'s [T], b: &'s [T]) -> (&'s [T], &'s [T]) {

544 let pre = a.iter().zip(b).take_while(|(x, y)| x == y).count();

545 let (a, b) = (&a[pre..], &b[pre..]);

546 let suf = a.iter().rev().zip(b.iter().rev()).take_while(|(x, y)| x == y).count();

547 (&a[..a.len() - suf], &b[..b.len() - suf])

548}

549

550/// The number of lines deleted plus inserted by a shortest diff of `a` to

551/// `b`, or `max` if that is at least `max`: Myers' greedy search, which

552/// reaches the end on round `d` exactly when the shortest diff has `d` steps,

553/// run for `max` rounds at most. A round extends each of its diagonals along

554/// equal lines from where the round before left off, so the work is at most

555/// `max` squared diagonals plus one pass over the lines per diagonal. Each

556/// pair of lines compared along a diagonal adds a step to `steps`, and each

557/// diagonal reached `DIAGONAL` steps; `None` once they pass `limit`.

558fn edit_distance<T: PartialEq>(

559 a: &[T],

560 b: &[T],

561 max: usize,

562 limit: usize,

563 steps: &mut usize,

564) -> Option<usize> {

565 let (n, m) = (a.len() as isize, b.len() as isize);

566 // the furthest `x` reached on diagonal `k = x - y`, at `v[k + max]`;

567 // round `d` writes diagonals `-d..=d` from those round `d - 1` wrote, and

568 // round 0 starts from the zero on diagonal 1

569 let mut v = vec![0isize; 2 * max + 1];

570 let at = |k: isize| (k + max as isize) as usize;

571 for d in 0..max as isize {

572 for k in (-d..=d).step_by(2) {

573 // from diagonal `k + 1` by inserting a line of `b`, or from

574 // `k - 1` by deleting one of `a`, whichever gets further

575 let from = if k == -d || (k != d && v[at(k - 1)] < v[at(k + 1)]) {

576 v[at(k + 1)]

577 } else {

578 v[at(k - 1)] + 1

579 };

580 let (mut x, mut y) = (from, from - k);

581 while x < n && y < m && a[x as usize] == b[y as usize] {

582 x += 1;

583 y += 1;

584 }

585 *steps += DIAGONAL + (x - from) as usize;

586 if *steps > limit {

587 return None;

588 }

589 v[at(k)] = x;

590 if x >= n && y >= m {

591 return Some(d as usize);

592 }

593 }

594 }

595 Some(max)

596}

597

598/// What reaching a diagonal costs `edit_distance`, in comparisons of two

599/// lines along one, the unit both searches count their steps in: measured at

600/// about twelve in a debug build and seven in release.

601const DIAGONAL: usize = 8;

602

603/// What a word costs `banded_distance`, in the same comparisons: measured at

604/// about six in a debug build and three to four in release. Weighted so,

605/// `line_distance` gives up Myers' search once it has cost about what the

606/// other search will; counted alike, it gave it up on a long file of a few

607/// lines repeating where finishing would have taken half the time or less.

608const WORD: usize = 4;

609

610/// `edit_distance` of lines numbered below `ids`, in at most twice the steps

611/// `banded_distance` takes and one diagonal with its run, whatever the lines

612/// are. Myers' search soon stops on most content, but on a long file of a

613/// few lines repeating it runs along equal lines on many diagonals, a pass

614/// over the file for each, so it may take only as many steps as

615/// `banded_distance` takes at most, and that counts instead if it has not

616/// finished by then. Steps are weighted by what they cost (`DIAGONAL`,

617/// `WORD`), so that is when it has cost about as much as the other search

618/// will. Both find the same count; `steps` adds up the steps of both.

619fn line_distance(a: &[usize], b: &[usize], ids: usize, max: usize, steps: &mut usize) -> usize {

620 let limit = *steps + banded_steps(a.len(), b.len(), max);

621 match edit_distance(a, b, max, limit, steps) {

622 Some(d) => d,

623 None => banded_distance(a, b, ids, max, steps),

624 }

625}

626

627/// The diagonals `x - y` from `-ins` to `del` that a diff of `n` lines to

628/// `m` stays on, keeping line `x` of the one with line `y` of the other, when

629/// it deletes plus inserts fewer than `max` lines, or `None` if none does:

630/// it deletes `n - m` more lines than it inserts, so at most `del` and

631/// inserts at most `ins`.

632fn band(n: usize, m: usize, max: usize) -> Option<(usize, usize)> {

633 (n.abs_diff(m) < max).then(|| ((max - 1 + n - m) / 2, (max - 1 + m - n) / 2))

634}

635

636/// The most steps `banded_distance` takes on `n` lines and `m` under `max`:

637/// `WORD` per line of the first, to find where its lines are, and per word

638/// of it the band crosses, at most `(del + ins) / 64 + 2`, per line of the

639/// second.

640fn banded_steps(n: usize, m: usize, max: usize) -> usize {

641 match band(n, m, max) {

642 Some((del, ins)) if n > 0 && m > 0 => WORD * (n + m * ((del + ins) / 64 + 2)),

643 _ => 0,

644 }

645}

646

647/// `edit_distance` of lines numbered below `ids`, found a machine word of `a`

648/// at a time for each line of `b` (Hyyrö's bit-parallel longest common

649/// subsequence), over only the band of diagonals a diff counting less than

650/// `max` stays on, as Ukkonen bounds the search. Its steps, which it adds to

651/// `steps`, are `WORD` per line of `a` and per word of `a` the band crosses

652/// per line of `b`, whatever the lines are.

653///

654/// After each line of `b`, the zero bits of `a`'s words up to a place in

655/// `a` count a longest common subsequence of `a` up to there and `b` so far.

656/// Only the words the band crosses change: one above the band keeps what it

657/// last had, and one below it still has the ones it started with, as if the

658/// length grew no further down. Neither counts more than a common

659/// subsequence has, and inside the band the counts are exact whenever a diff

660/// of fewer than `max` lines exists, since such a diff keeps inside the band;

661/// otherwise the count is `max` whatever they are.

662fn banded_distance(a: &[usize], b: &[usize], ids: usize, max: usize, steps: &mut usize) -> usize {

663 let (n, m) = (a.len(), b.len());

664 let Some((del, ins)) = band(n, m, max) else {

665 return max;

666 };

667 if n == 0 || m == 0 {

668 return n + m;

669 }

670 *steps += WORD * n;

671 // per line, from `start[l]` to `start[l + 1]`: the words of `a` it occurs

672 // in, in order, with a bit where it occurs in each

673 let mut start = vec![0usize; ids + 1];

674 let mut last = vec![usize::MAX; ids];

675 for (i, l) in a.iter().enumerate() {

676 if last[*l] != i / 64 {

677 last[*l] = i / 64;

678 start[*l + 1] += 1;

679 }

680 }

681 drop(last);

682 for l in 0..ids {

683 start[l + 1] += start[l];

684 }

685 let (mut word, mut bits) = (vec![0usize; start[ids]], vec![0u64; start[ids]]);

686 let mut next = start[..ids].to_vec();

687 for (i, l) in a.iter().enumerate() {

688 let e = next[*l];

689 if e == start[*l] || word[e - 1] != i / 64 {

690 word[e] = i / 64;

691 next[*l] += 1;

692 }

693 bits[next[*l] - 1] |= 1 << (i % 64);

694 }

695 // before any line of `b` nothing is common; from here on `next[l]` is the

696 // first word line `l` occurs in that is not above the band

697 let mut v = vec![u64::MAX; n.div_ceil(64)];

698 next.copy_from_slice(&start[..ids]);

699 // as slices, which a debug build indexes without a call

700 let (v, next) = (&mut v[..], &mut next[..]);

701 let (start, word, bits) = (&start[..], &word[..], &bits[..]);

702 for (j, l) in b.iter().enumerate() {

703 // line `j` of `b` can only be kept with lines `j - ins` to `j + del`

704 // of `a`

705 let (lo, hi) = (j.saturating_sub(ins) / 64, (j + del).min(n - 1) / 64);

706 *steps += WORD * (hi + 1 - lo);

707 let end = start[*l + 1];

708 let mut e = next[*l];

709 while e < end && word[e] < lo {

710 e += 1;

711 }

712 next[*l] = e;

713 // the words above the band do not change, so nothing carries in

714 let mut carry = false;

715 for (w, v) in v[lo..=hi].iter_mut().enumerate() {

716 let here = if e < end && word[e] == lo + w {

717 e += 1;

718 bits[e - 1]

719 } else {

720 0

721 };

722 let x = *v;

723 let (sum, c1) = x.overflowing_add(x & here);

724 let (sum, c2) = sum.overflowing_add(carry as u64);

725 carry = c1 || c2;

726 *v = sum | (x & !here);

727 }

728 }

729 let common: usize = v.iter().map(|w| w.count_zeros() as usize).sum();

730 (n + m - 2 * common).min(max)

731}

732

733/// A lower bound on the lines deleted plus inserted by any diff of `a` to

734/// `b` (lines numbered below `ids`), cheap where the search is dearest: a

735/// long file whose lines were reordered, or one of a few lines repeating

736/// that now occur a different number of times. A line that occurs once on

737/// each side can only be kept by pairing those two, and the pairs kept keep

738/// their order on both sides, so at most the longest sequence of them in the

739/// same order on both sides is kept (patience sorting finds its length); any

740/// other line is kept at most as many times as it occurs on the side where

741/// it occurs fewer times.

742fn reorder_bound(a: &[usize], b: &[usize], ids: usize) -> usize {

743 // per line: its occurrences in `a` and in `b`, and where it is in `a`

744 let mut seen = vec![(0usize, 0usize, 0usize); ids];

745 for (i, l) in a.iter().enumerate() {

746 seen[*l].0 += 1;

747 seen[*l].2 = i;

748 }

749 for l in b {

750 seen[*l].1 += 1;

751 }

752 // over the lines once on each side, in `b`'s order, by where they are in

753 // `a`: `ends[i]` is the least last place of an increasing sequence of

754 // `i + 1` of them

755 let mut ends: Vec<usize> = Vec::new();

756 for l in b {

757 if let (1, 1, i) = seen[*l] {

758 let at = ends.partition_point(|e| *e < i);

759 if at == ends.len() {

760 ends.push(i);

761 } else {

762 ends[at] = i;

763 }

764 }

765 }

766 let others: usize = seen

767 .iter()

768 .filter(|(in_a, in_b, _)| (*in_a, *in_b) != (1, 1))

769 .map(|(in_a, in_b, _)| in_a.min(in_b))

770 .sum();

771 let kept = ends.len() + others;

772 a.len() + b.len() - 2 * kept

773}

774

775fn snapshot_map_of(snap: &Value) -> Result<SnapMap, Crash> {

776 let mut m = BTreeMap::new();

777 for e in snap.as_list()?.iter() {

778 let path = e

779 .field("path")?

780 .as_list()?

781 .iter()

782 .map(|c| c.as_text().map(|s| s.to_string()))

783 .collect::<Result<Vec<String>, Crash>>()?;

784 m.insert(path, e.field("content")?);

785 }

786 Ok(m)

787}

788

789/// What a commit's glyph says about where it stands in a history

790/// (specs/tree.md §Glyphs), beyond what its own files say. A `Commit` value

791/// records none of it, so both its forms read it from the repository the

792/// expression was given (`Loaded`).

793struct Standing {

794 focus: bool,

795 /// an ancestor of the focus

796 ancestor: bool,

797 immutable: bool,

798 /// no change against its parent

799 empty: bool,

800}

801

802fn commit_line(

803 interp: &Interp,

804 c: &Value,

805 pal: &Palette,

806 standing: &Standing,

807) -> Result<String, Crash> {

808 let id = match c.field("id")? {

809 Value::Id(i) => i.to_string(),

810 _ => return Err(Crash::new("commit without id")),

811 };

812 let msg = c.field("message")?.as_text()?.to_string();

813 let msg_first = msg.lines().next().unwrap_or("").to_string();

814 let labels: Vec<String> = c

815 .field("labels")?

816 .as_list()?

817 .iter()

818 .map(|l| l.as_text().map(|s| s.to_string()))

819 .collect::<Result<_, _>>()?;

820 let glyph = node_glyph(c, &id, standing)?;

821 let id_s = if glyph == "⊗" {

822 pal.red(&display_id(interp, &id, &Palette { on: false }))

823 } else if standing.immutable {

824 pal.blue(&display_id(interp, &id, &Palette { on: false }))

825 } else {

826 display_id(interp, &id, pal)

827 };

828 let glyph = pal.code(node_ansi(&glyph), &glyph);

829 let labels_s = if labels.is_empty() {

830 String::new()

831 } else {

832 pal.label(&labels.join(" "))

833 };

834 Ok(if labels_s.is_empty() {

835 format!("{} {} {}", glyph, id_s, msg_first)

836 } else {

837 format!("{} {} {} {}", glyph, id_s, msg_first, labels_s)

838 })

839}

840

841/// The glyph of a commit line, by `tree`'s precedence (`glyph_for`).

842fn node_glyph(c: &Value, id: &str, standing: &Standing) -> Result<String, Crash> {

843 let g = if id == ROOT_ID {

844 "⌂"

845 } else if has_conflict(c)? {

846 "⊗"

847 } else if standing.empty {

848 "◌"

849 } else if standing.immutable {

850 "◆"

851 } else if standing.focus {

852 "◉"

853 } else if standing.ancestor {

854 "●"

855 } else {

856 "○"

857 };

858 Ok(g.to_string())

859}

860

861fn has_conflict(c: &Value) -> Result<bool, Crash> {

862 let files = c.field("files")?;

863 for e in files.as_list()?.iter() {

864 if let Value::Blob(b) = e.field("content")? {

865 if b.is_unresolved() {

866 return Ok(true);

867 }

868 }

869 }

870 Ok(false)

871}

872

873/// `v` in block form, the blocks it holds left on `todo` (see `Block`)

874#[allow(clippy::too_many_arguments)]

875fn display_block(

876 interp: &mut Interp,

877 v: &Value,

878 pal: &Palette,

879 indent: usize,

880 out: &mut String,

881 loaded: &mut Option<Loaded>,

882 todo: &mut Vec<Block>,

883 term_w: Option<usize>,

884) -> Result<(), Crash> {

885 let pad = " ".repeat(indent);

886 let v = &v.forced()?;

887 match v {

888 Value::Thunk(_) => unreachable!("forced never returns a thunk"),

889 Value::Text(t) => {

890 out.push_str(t);

891 return Ok(());

892 }

893 Value::Blob(b) => {

894 let content = String::from_utf8_lossy(&b.bytes()?).to_string();

895 out.push_str(&indent_multiline(&content, indent));

896 return Ok(());

897 }

898 Value::Int(_) | Value::Bool(_) | Value::Id(_) | Value::Shape(_) => {

899 out.push_str(&pad);

900 out.push_str(&display_line(interp, v, pal, loaded)?);

901 out.push('\n');

902 return Ok(());

903 }

904 // all of a lambda's source, of which the line form keeps the first

905 // line (§5.1), each line under the block's indent

906 Value::Fun(_) => {

907 for l in crate::show::show(interp, v)?.lines() {

908 out.push_str(&pad);

909 out.push_str(l);

910 out.push('\n');

911 }

912 return Ok(());

913 }

914 Value::List(xs) => return display_list_block(interp, xs, pal, indent, out, loaded, todo, term_w),

915 Value::Record(_) => {}

916 }

917 if let Some(shape) = shape_of_record(interp, v) {

918 match shape.as_str() {

919 "Commit" => {

920 let loaded = Loaded::cached(interp, loaded)?;

921 return display_commit_block(interp, v, pal, indent, out, loaded);

922 }

923 "Entry" => {

924 out.push_str(&pad);

925 out.push_str(&entry_line(interp, v, pal)?);

926 out.push('\n');

927 return Ok(());

928 }

929 "Subtree" => {

930 let opts = default_tree_options(interp)?;

931 let repo = Value::record(&[

932 ("root", v.field("root")?),

933 ("children", v.field("children")?),

934 ("context", Value::list(vec![])),

935 ]);

936 let text = tree_render(interp, &opts, &repo, pal, false, term_w)?;

937 out.push_str(&indent_multiline(&text, indent));

938 return Ok(());

939 }

940 "Repo" => {

941 let tree_fn = interp

942 .globals

943 .lookup("tree")

944 .ok_or_else(|| Crash::new("`tree` is not defined"))?;

945 let text = interp.apply(tree_fn, v.clone())?;

946 let text = text.as_text()?;

947 out.push_str(&indent_multiline(text, indent));

948 return Ok(());

949 }

950 "Frame" => {

951 out.push_str(&pad);

952 out.push_str(&line_in(interp, &v.field("parent")?, pal, loaded, false)?);

953 out.push('\n');

954 return Ok(());

955 }

956 "Change" => {

957 for (p, mark, _) in touched_paths(v)? {

958 out.push_str(&pad);

959 out.push_str(&format!("{} {}\n", colored_mark(mark, pal), p));

960 }

961 return Ok(());

962 }

963 _ => {}

964 }

965 }

966 // generic record: one field per line

967 let m = match v {

968 Value::Record(m) => m,

969 _ => unreachable!(),

970 };

971 let name_w = m.keys().map(|k| width(k)).max().unwrap_or(0);

972 display_fields(interp, m, None, name_w, pal, indent, out, loaded, todo)

973}

974

975/// A generic record's fields after the field `after`, or all of them, one

976/// per line under names `name_w` wide, up to the first that is a non-empty

977/// list: its block is left on `todo` to be displayed next, and the fields

978/// after it to follow.

979#[allow(clippy::too_many_arguments)]

980fn display_fields(

981 interp: &mut Interp,

982 m: &Rc<RecordMap>,

983 after: Option<&str>,

984 name_w: usize,

985 pal: &Palette,

986 indent: usize,

987 out: &mut String,

988 loaded: &mut Option<Loaded>,

989 todo: &mut Vec<Block>,

990) -> Result<(), Crash> {

991 let pad = " ".repeat(indent);

992 let status = (m.len() == 5

993 || (m.len() == 6 && matches!(m.get("unrecorded"), Some(Value::List(_)))))

994 && matches!(m.get("id"), Some(Value::Id(_)))

995 && matches!(m.get("message"), Some(Value::Text(_)))

996 && ["changed", "conflicts", "labels"].iter()

997 .all(|key| matches!(m.get(*key), Some(Value::List(_))));

998 let from = after.map_or(Bound::Unbounded, Bound::Excluded);

999 for (k, x) in m.range::<str, _>((from, Bound::Unbounded)) {

1000 out.push_str(&pad);

1001 let label = if status && m.contains_key("unrecorded") && k == "changed" {

1002 "in commit"

1003 } else {

1004 k.as_str()

1005 };

1006 out.push_str(&pal.field(&pad_right(label, name_w)));

1007 out.push_str(" ");

1008 if status {

1009 let empty = match (k.as_str(), x) {

1010 ("changed", Value::List(xs)) if xs.is_empty() => Some("No changes"),

1011 ("unrecorded", Value::List(xs)) if xs.is_empty() => Some("All edits recorded"),

1012 ("conflicts", Value::List(xs)) if xs.is_empty() => Some("No conflicts"),

1013 ("labels", Value::List(xs)) if xs.is_empty() => Some("No labels"),

1014 ("message", Value::Text(s)) if s.is_empty() => Some("No description"),

1015 _ => None,

1016 };

1017 if let Some(text) = empty {

1018 out.push_str(&pal.dim(text));

1019 out.push('\n');

1020 continue;

1021 }

1022 }

1023 // lists print in block form under their key (§5.1)

1024 if matches!(x, Value::List(xs) if !xs.is_empty()) {

1025 out.push('\n');

1026 let after = Some(k.clone());

1027 todo.push(Block::Fields { m: m.clone(), after, name_w, indent });

1028 todo.push(Block::Of(x.clone(), indent + name_w + 2));

1029 return Ok(());

1030 }

1031 let line = display_line(interp, x, pal, loaded)?;

1032 out.push_str(&line);

1033 out.push('\n');

1034 }

1035 Ok(())

1036}

1037

1038fn indent_multiline(s: &str, indent: usize) -> String {

1039 if indent == 0 {

1040 return s.to_string();

1041 }

1042 let pad = " ".repeat(indent);

1043 s.lines()

1044 .map(|l| format!("{}{}", pad, l))

1045 .collect::<Vec<_>>()

1046 .join("\n")

1047 + "\n"

1048}

1049

1050/// A change mark (`+ ~ − ✖`), coloured by what it means.

1051fn colored_mark(mark: char, pal: &Palette) -> String {

1052 let ms = mark.to_string();

1053 match mark {

1054 '+' => pal.green(&ms),

1055 '−' | '✖' => pal.red(&ms),

1056 '~' => pal.yellow(&ms),

1057 _ => ms,

1058 }

1059}

1060

1061/// The repository the expression was given (§1.2 step 4, after the

1062/// snapshot), or, where only the loaded one is set (the interpreter tests),

1063/// that one.

1064fn given_repo(interp: &Interp) -> Option<Value> {

1065 let given = interp.given_repo.borrow().clone();

1066 given.or_else(|| interp.old_repo.borrow().clone())

1067}

1068

1069/// The repository the expression was given (`given_repo`), indexed for

1070/// displaying `Commit` values. A commit value records neither its parent nor

1071/// where it stands, so both its forms read them from the commit with the

1072/// same id there, as its block reads author and age (§5.1). Not the

1073/// repository as loaded: the snapshot has rebased every descendant of the

1074/// focus since, and the values displayed come from after it. Indexed once

1075/// per displayed value, not once per commit: a table of commits would

1076/// otherwise walk the history once for each row.

1077struct Loaded {

1078 /// the parent of every commit that has one

1079 parents: BTreeMap<String, Value>,

1080 focus: String,

1081 /// the focus's ancestors, the focus excluded

1082 ancestors: BTreeSet<String>,

1083 immutable: BTreeSet<String>,

1084}

1085

1086impl Loaded {

1087 /// `cache`, indexed when a display first draws a commit

1088 fn cached<'a>(interp: &mut Interp, cache: &'a mut Option<Loaded>) -> Result<&'a Loaded, Crash> {

1089 if cache.is_none() {

1090 *cache = Some(Loaded::of(interp)?);

1091 }

1092 Ok(cache.as_ref().expect("just set"))

1093 }

1094

1095 fn of(interp: &mut Interp) -> Result<Loaded, Crash> {

1096 let mut loaded = Loaded {

1097 parents: BTreeMap::new(),

1098 focus: String::new(),

1099 ancestors: BTreeSet::new(),

1100 immutable: BTreeSet::new(),

1101 };

1102 let Some(repo) = given_repo(interp) else {

1103 return Ok(loaded);

1104 };

1105 if let Value::Id(i) = repo.field("root")?.field("id")? {

1106 loaded.focus = i.to_string();

1107 }

1108 for frame in repo.field("context")?.as_list()?.iter() {

1109 loaded.ancestors.insert(id_of_frame_parent(frame)?);

1110 }

1111 // as `tree_render` does: a config whose `immutable` crashes draws no `◆`

1112 loaded.immutable = crate::repo::compute_immutable(interp, &repo).unwrap_or_default();

1113 // every commit's parent, walking down from the top of the history

1114 let top = crate::repo::by_id(&repo, &top_id(&repo)?)?.unwrap_or_else(|| repo.clone());

1115 let mut todo = vec![(top.field("root")?, top.field("children")?)];

1116 while let Some((parent, children)) = todo.pop() {

1117 for c in children.as_list()?.iter() {

1118 let root = c.field("root")?;

1119 if let Value::Id(i) = root.field("id")? {

1120 loaded.parents.insert(i.to_string(), parent.clone());

1121 }

1122 todo.push((root, c.field("children")?));

1123 }

1124 }

1125 Ok(loaded)

1126 }

1127

1128 /// Where the commit with id `id` stands here, given whether it changes

1129 /// nothing against its parent here.

1130 fn standing(&self, id: &str, empty: bool) -> Standing {

1131 Standing {

1132 focus: id == self.focus,

1133 ancestor: self.ancestors.contains(id),

1134 immutable: self.immutable.contains(id),

1135 empty,

1136 }

1137 }

1138

1139 /// Where the commit value `c` stands here, for its line form: `◌` judged

1140 /// as the block judges it, by its files against its parent's here. While

1141 /// both still hold their stored trees the backend answers from tree ids,

1142 /// as for `tree` (`build_info`), so a table of commits reads no parent's

1143 /// files. A commit with no parent here claims no `◌`.

1144 fn line_standing(&self, interp: &Interp, c: &Value) -> Result<Standing, Crash> {

1145 let id = match c.field("id")? {

1146 Value::Id(i) => i.to_string(),

1147 _ => String::new(),

1148 };

1149 let empty = match self.parents.get(&id) {

1150 None => false,

1151 Some(parent) => {

1152 let parent_id = match parent.field("id")? {

1153 Value::Id(i) => i.to_string(),

1154 _ => String::new(),

1155 };

1156 let me = stored_origin(c).filter(|o| *o == id);

1157 let stored_parent = stored_origin(parent).filter(|o| *o == parent_id);

1158 let answer = match (me, stored_parent) {

1159 (Some(me), Some(parent)) => interp.backend.is_empty(me, parent),

1160 _ => None,

1161 };

1162 match answer {

1163 Some(e) => e,

1164 // in any order: a snapshot stands for a tree (§7.3)

1165 None => crate::repo::snapshot_eq(&c.field("files")?, &parent.field("files")?)?,

1166 }

1167 }

1168 };

1169 Ok(self.standing(&id, empty))

1170 }

1171}

1172

1173/// A commit's line form, drawn where it stands in the repository the

1174/// expression was given (§5.1); `as_focus` draws it as a `Repo`'s focus.

1175fn line_in(

1176 interp: &mut Interp,

1177 c: &Value,

1178 pal: &Palette,

1179 loaded: &mut Option<Loaded>,

1180 as_focus: bool,

1181) -> Result<String, Crash> {

1182 let loaded = Loaded::cached(interp, loaded)?;

1183 let mut standing = loaded.line_standing(interp, c)?;

1184 standing.focus |= as_focus;

1185 commit_line(interp, c, pal, &standing)

1186}

1187

1188fn display_commit_block(

1189 interp: &mut Interp,

1190 c: &Value,

1191 pal: &Palette,

1192 indent: usize,

1193 out: &mut String,

1194 loaded: &Loaded,

1195) -> Result<(), Crash> {

1196 let pad = " ".repeat(indent);

1197 let id = match c.field("id")? {

1198 Value::Id(i) => i.to_string(),

1199 _ => String::new(),

1200 };

1201 let own = snapshot_map_of(&c.field("files")?)?;

1202 // the paths it changes against its parent in the given repository; with

1203 // no parent there — the root, or a commit the expression made, whose

1204 // parent the value does not record — what it changes is not known

1205 let touched = match loaded.parents.get(&id) {

1206 Some(parent) => Some(touched_in_maps(

1207 &snapshot_map_of(&parent.field("files")?)?,

1208 &own,

1209 )?),

1210 None => None,

1211 };

1212 // the line `tree` draws for it (§5.1: "a `tree` line without rails")

1213 let empty = touched.as_ref().is_some_and(|t| t.is_empty());

1214 out.push_str(&pad);

1215 out.push_str(&commit_line(interp, c, pal, &loaded.standing(&id, empty))?);

1216 out.push('\n');

1217 // author · age · n files — from metadata by id (§5.1)

1218 let n = touched.as_ref().map_or(own.len(), |t| t.len());

1219 if let Ok(meta) = interp.backend.meta(&id) {

1220 let age = render_age(meta.time);

1221 out.push_str(&pad);

1222 out.push_str(&format!(" {} · {} · {} files\n", meta.author, age, n));

1223 }

1224 if n > 0 {

1225 out.push('\n');

1226 }

1227 match &touched {

1228 Some(touched) => {

1229 for (path, mark, _) in touched {

1230 out.push_str(&pad);

1231 out.push_str(&format!(

1232 " {} {}\n",

1233 colored_mark(*mark, pal),

1234 path.join("/")

1235 ));

1236 }

1237 }

1238 // its files, unmarked but for `✖`

1239 None => {

1240 for (path, content) in &own {

1241 out.push_str(&pad);

1242 if matches!(content, Value::Blob(b) if b.is_unresolved()) {

1243 out.push_str(&format!(" {} {}\n", pal.red("✖"), path.join("/")));

1244 } else {

1245 out.push_str(&format!(" {}\n", path.join("/")));

1246 }

1247 }

1248 }

1249 }

1250 Ok(())

1251}

1252

1253pub fn render_age(time: i64) -> String {

1254 let now = std::time::SystemTime::now()

1255 .duration_since(std::time::UNIX_EPOCH)

1256 .map(|d| d.as_secs() as i64)

1257 .unwrap_or(0);

1258 let d = (now - time).max(0);

1259 if d < 60 {

1260 format!("{}s", d)

1261 } else if d < 3600 {

1262 format!("{}m", d / 60)

1263 } else if d < 86400 {

1264 format!("{}h", d / 3600)

1265 } else if d < 86400 * 7 {

1266 format!("{}d", d / 86400)

1267 } else if d < 86400 * 365 {

1268 format!("{}w", d / (86400 * 7))

1269 } else {

1270 format!("{}y", d / (86400 * 365))

1271 }

1272}

1273

1274/// Format unix-seconds `time` as an absolute date `YYYY-MM-DD` (UTC), using

1275/// the civil-from-days algorithm (no external date crate).

1276pub fn render_date(time: i64) -> String {

1277 let days = time.div_euclid(86_400);

1278 // Howard Hinnant's civil_from_days

1279 let z = days + 719_468;

1280 let era = z.div_euclid(146_097);

1281 let doe = z.rem_euclid(146_097);

1282 let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;

1283 let y = yoe + era * 400;

1284 let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);

1285 let mp = (5 * doy + 2) / 153;

1286 let d = doy - (153 * mp + 2) / 5 + 1;

1287 let m = if mp < 10 { mp + 3 } else { mp - 9 };

1288 let y = if m <= 2 { y + 1 } else { y };

1289 format!("{:04}-{:02}-{:02}", y, m, d)

1290}

1291

1292/// the repo value in context (the one the expression was given), for

1293/// resolving ids to commits

1294fn top_of(interp: &Interp, _x: &Value) -> Result<Value, Crash> {

1295 given_repo(interp).ok_or_else(|| Crash::new("display: no repository in context"))

1296}

1297

1298/// `list` in block form, the blocks it holds left on `todo` (see `Block`)

1299#[allow(clippy::too_many_arguments)]

1300fn display_list_block(

1301 interp: &mut Interp,

1302 list: &ListVal,

1303 pal: &Palette,

1304 indent: usize,

1305 out: &mut String,

1306 loaded: &mut Option<Loaded>,

1307 todo: &mut Vec<Block>,

1308 term_w: Option<usize>,

1309) -> Result<(), Crash> {

1310 let xs: &[Value] = list;

1311 let pad = " ".repeat(indent);

1312 if xs.is_empty() {

1313 out.push_str(&pad);

1314 out.push_str(&pal.dim("none"));

1315 out.push('\n');

1316 return Ok(());

1317 }

1318 // list of Id: commit table (one commit line per id, in list order)

1319 if xs.iter().all(|x| matches!(x, Value::Id(_))) {

1320 // index the history once: a `by_id` walk per id made printing a

1321 // revset quadratic in the size of the history

1322 let repo = top_of(interp, &xs[0])?;

1323 let mut commits: BTreeMap<String, Value> = BTreeMap::new();

1324 for c in crate::repo::all_commits(&repo)? {

1325 if let Ok(Value::Id(i)) = c.field("id") {

1326 commits.insert(i.to_string(), c);

1327 }

1328 }

1329 let loaded = Loaded::cached(interp, loaded)?;

1330 for x in xs {

1331 let id = match x {

1332 Value::Id(i) => i.to_string(),

1333 _ => unreachable!(),

1334 };

1335 out.push_str(&pad);

1336 match commits.get(&id) {

1337 Some(c) => {

1338 let c = c.clone();

1339 // the glyph of its line form (§5.1)

1340 let glyph = node_glyph(&c, &id, &loaded.line_standing(interp, &c)?)?;

1341 let conflict = glyph == "⊗";

1342 let glyph = pal.code(node_ansi(&glyph), &glyph);

1343 let msg = c.field("message")?.as_text()?.to_string();

1344 let msg_first = msg.lines().next().unwrap_or("");

1345 let labels: Vec<String> = c

1346 .field("labels")?

1347 .as_list()?

1348 .iter()

1349 .map(|l| l.as_text().map(|s| s.to_string()))

1350 .collect::<Result<_, _>>()?;

1351 let id_s = if conflict {

1352 pal.red(&interp.unique_prefix(&id))

1353 } else {

1354 display_id(interp, &id, pal)

1355 };

1356 if labels.is_empty() {

1357 out.push_str(&format!("{} {} {}\n", glyph, id_s, msg_first));

1358 } else {

1359 out.push_str(&format!(

1360 "{} {} {} {}\n",

1361 glyph,

1362 id_s,

1363 msg_first,

1364 pal.label(&labels.join(" "))

1365 ));

1366 }

1367 }

1368 None => {

1369 out.push_str(&display_id(interp, &id, pal));

1370 out.push('\n');

1371 }

1372 }

1373 }

1374 return Ok(());

1375 }

1376 // list of Text

1377 if xs.iter().all(|x| matches!(x, Value::Text(_))) {

1378 for x in xs {

1379 out.push_str(&pad);

1380 out.push_str(x.as_text()?);

1381 out.push('\n');

1382 }

1383 return Ok(());

1384 }

1385 // list of [Text]: paths

1386 let all_path = xs.iter().all(|x| match x {

1387 Value::List(p) => p.iter().all(|c| matches!(c, Value::Text(_))),

1388 _ => false,

1389 });

1390 if all_path {

1391 for x in xs {

1392 out.push_str(&pad);

1393 out.push_str(&path_string(x)?);

1394 out.push('\n');

1395 }

1396 return Ok(());

1397 }

1398 // list of records with identical field sets: Entry list gets entry lines,

1399 // other identical sets get a column table

1400 let all_record = xs.iter().all(|x| matches!(x, Value::Record(_)));

1401 if all_record {

1402 let first = field_set(&xs[0]).unwrap();

1403 let same = xs

1404 .iter()

1405 .all(|x| field_set(x).map(|s| s == first).unwrap_or(false));

1406 if same {

1407 if shape_of_record(interp, &xs[0]).as_deref() == Some("Entry") {

1408 let width_max = xs

1409 .iter()

1410 .map(|x| path_string(&x.field("path").unwrap()).map(|p| width(&p)))

1411 .collect::<Result<Vec<_>, _>>()?

1412 .into_iter()

1413 .max()

1414 .unwrap_or(0);

1415 for x in xs {

1416 let path = path_string(&x.field("path")?)?;

1417 let content = x.field("content")?;

1418 let (size, unresolved) = match &content {

1419 Value::Blob(b) => (human_size(b.size()), b.is_unresolved()),

1420 _ => (String::new(), false),

1421 };

1422 out.push_str(&pad);

1423 let mark = if unresolved { pal.red("✖") } else { " ".into() };

1424 let size_s = if unresolved {

1425 pal.red(&size)

1426 } else {

1427 pal.yellow(&size)

1428 };

1429 // pad by display width, not by character count: `{:n$}`

1430 // pads to n *chars*, so a wide (East Asian) path pushes

1431 // the size column out of line

1432 out.push_str(&format!(

1433 "{} {} {}\n", mark, pal.cyan(&pad_right(&path, width_max)), size_s

1434 ));

1435 }

1436 return Ok(());

1437 }

1438 return display_table(interp, xs, pal, indent, out, loaded, term_w);

1439 }

1440 }

1441 // list of other scalars

1442 let all_scalar = xs

1443 .iter()

1444 .all(|x| matches!(x, Value::Int(_) | Value::Bool(_)));

1445 if all_scalar {

1446 out.push_str(&pad);

1447 out.push_str(&list_line(interp, xs, pal)?);

1448 out.push('\n');

1449 return Ok(());

1450 }

1451 // one block per item, separated by a blank line (see `Block`)

1452 todo.push(Block::Items { xs: list.clone(), next: 0, indent });

1453 Ok(())

1454}

1455

1456fn display_table(

1457 interp: &mut Interp,

1458 xs: &[Value],

1459 pal: &Palette,

1460 indent: usize,

1461 out: &mut String,

1462 loaded: &mut Option<Loaded>,

1463 term_w: Option<usize>,

1464) -> Result<(), Crash> {

1465 let pad = " ".repeat(indent);

1466 let fields: Vec<String> = field_set(&xs[0]).unwrap().into_iter().collect();

1467 // IDs must distinguish both stored commits and IDs created by this expression.

1468 let mut ids: Vec<String> = xs.iter().flat_map(|x| fields.iter().filter_map(|f| {

1469 match x.field(f) { Ok(Value::Id(id)) => Some(id.to_string()), _ => None }

1470 })).collect();

1471 ids.sort();

1472 ids.dedup();

1473 let mut fixed = vec![false; fields.len()];

1474 // cells

1475 let mut rows: Vec<Vec<String>> = Vec::new();

1476 for x in xs {

1477 let mut row = Vec::new();

1478 for (column, f) in fields.iter().enumerate() {

1479 let cell = match x.field(f)? {

1480 Value::Bool(true) => pal.green("✓"),

1481 Value::Bool(false) => String::new(),

1482 Value::Id(id) => {

1483 fixed[column] = true;

1484 let stored = interp.unique_prefix(&id);

1485 let shown = crate::eval::unique_prefix_in(&ids, &id);

1486 let prefix = if stored.len() > shown.len() { stored } else { shown };

1487 pal.id(&format!("@{}", prefix))

1488 }

1489 Value::List(values) if values.iter().all(|v| matches!(v, Value::Text(_))) => {

1490 values.iter().map(|v| v.as_text().map(first_line))

1491 .collect::<Result<Vec<_>, _>>()?.join(", ")

1492 }

1493 other => display_line(interp, &other, pal, loaded)?,

1494 };

1495 row.push(cell);

1496 }

1497 rows.push(row);

1498 }

1499 // drop columns empty in every row

1500 let keep: Vec<usize> = (0..fields.len())

1501 .filter(|&i| rows.iter().any(|r| !r[i].is_empty()))

1502 .collect();

1503 let mut widths: Vec<usize> = keep

1504 .iter()

1505 .map(|&i| {

1506 rows.iter()

1507 .map(|r| width(&r[i]))

1508 .max()

1509 .unwrap_or(0)

1510 .max(width(&fields[i]))

1511 })

1512 .collect();

1513 if let Some(terminal) = term_w {

1514 let available = terminal.saturating_sub(indent);

1515 let gaps = keep.len().saturating_sub(1) * 3;

1516 let minimum: Vec<usize> = keep.iter().zip(&widths).map(|(&i, &w)| {

1517 if fixed[i] { w } else { w.min(width(&fields[i]).max(6)) }

1518 }).collect();

1519 if minimum.iter().sum::<usize>() + gaps > available {

1520 // A narrow terminal cannot hold the headers and identifiers side by

1521 // side. Keep a small nesting inset below the parent key, instead of

1522 // letting a long parent field name consume the entire line width.

1523 let inset = indent.min(2).min(terminal / 4);

1524 let pad = " ".repeat(inset);

1525 let available = terminal.saturating_sub(inset);

1526 for (n, row) in rows.iter().enumerate() {

1527 if n > 0 { out.push('\n'); }

1528 for &i in &keep {

1529 let text = format!("{}: {}", pal.field(&fields[i]), row[i]);

1530 for line in wrap_display_text(&text, available.max(1)) {

1531 out.push_str(&pad);

1532 out.push_str(&line);

1533 out.push('\n');

1534 }

1535 }

1536 }

1537 return Ok(());

1538 }

1539 let mut excess = (widths.iter().sum::<usize>() + gaps).saturating_sub(available);

1540 while excess > 0 {

1541 let column = (0..widths.len()).filter(|&i| widths[i] > minimum[i])

1542 .max_by_key(|&i| widths[i]).expect("minimum widths fit");

1543 widths[column] -= 1;

1544 excess -= 1;

1545 }

1546 }

1547 // header

1548 out.push_str(&pad);

1549 let header: Vec<String> = keep

1550 .iter()

1551 .zip(&widths)

1552 .map(|(&i, w)| pad_right(&fields[i], *w))

1553 .collect();

1554 out.push_str(&pal.field(&header.join(" ")));

1555 out.push('\n');

1556 for r in &rows {

1557 out.push_str(&pad);

1558 let cells: Vec<String> = keep

1559 .iter()

1560 .zip(&widths)

1561 .map(|(&i, w)| pad_right(&cut_to_width(&r[i], *w), *w))

1562 .collect();

1563 out.push_str(&cells.join(" "));

1564 out.push('\n');

1565 }

1566 Ok(())

1567}

1568

1569// ----------------------------------------------------------------------

1570// treeWith (§7.11)

1571// ----------------------------------------------------------------------

1572

1573pub struct TreeOptions {

1574 pub detail: i64,

1575 pub margin: bool,

1576 pub elide: bool,

1577 pub icons: bool,

1578 pub color: String,

1579 pub lanes: i64,

1580 /// show the full author name column

1581 pub author: bool,

1582 /// show the absolute commit date column (YYYY-MM-DD)

1583 pub date: bool,

1584 /// show the number of files changed column

1585 pub files: bool,

1586}

1587

1588fn default_tree_options(_interp: &Interp) -> Result<TreeOptions, Crash> {

1589 Ok(TreeOptions {

1590 detail: 1,

1591 margin: false,

1592 elide: true,

1593 icons: false,

1594 color: "auto".into(),

1595 lanes: 4,

1596 author: false,

1597 date: false,

1598 files: false,

1599 })

1600}

1601

1602/// The terminal's width when stdout is one — what rows are cut to and the

1603/// legend is placed by (specs/tree.md Step 4, §Legend) — else `None`.

1604fn tty_width() -> Option<usize> {

1605 if crate::show::stdout_is_tty() {

1606 crate::show::terminal_width()

1607 } else {

1608 None

1609 }

1610}

1611

1612pub fn tree_with(interp: &mut Interp, opts: &Value, repo: &Value) -> Result<Value, Crash> {

1613 tree_with_width(interp, opts, repo, tty_width())

1614}

1615

1616/// `treeWith` as if stdout were a terminal `term_w` columns wide (`None`: not

1617/// a terminal). Public so the tests can drive truncation without a pty.

1618pub fn tree_with_width(

1619 interp: &mut Interp,

1620 opts: &Value,

1621 repo: &Value,

1622 term_w: Option<usize>,

1623) -> Result<Value, Crash> {

1624 let defaults = default_tree_options(interp)?;

1625 // a missing option falls back to its default, so an older config that

1626 // predates a newer option keeps working; a present option is type-checked

1627 let bool_opt = |name: &str, default: bool| -> Result<bool, Crash> {

1628 match opts.field(name) {

1629 Ok(Value::Bool(b)) => Ok(b),

1630 Ok(_) => Err(Crash::new(format!("treeWith: {} must be a Bool", name))),

1631 Err(_) => Ok(default),

1632 }

1633 };

1634 let int_opt = |name: &str, default: i64| -> Result<i64, Crash> {

1635 match opts.field(name) {

1636 Ok(Value::Int(n)) => Ok(n.to_string().parse::<i64>().unwrap_or(default)),

1637 Ok(_) => Err(Crash::new(format!("treeWith: {} must be an Int", name))),

1638 Err(_) => Ok(default),

1639 }

1640 };

1641 let detail = int_opt("detail", defaults.detail)?;

1642 let margin = bool_opt("margin", defaults.margin)?;

1643 let elide = bool_opt("elide", defaults.elide)?;

1644 let icons = bool_opt("icons", defaults.icons)?;

1645 let color = match opts.field("color") {

1646 Ok(v) => v.as_text()?.to_string(),

1647 Err(_) => defaults.color.clone(),

1648 };

1649 let lanes = int_opt("lanes", defaults.lanes)?;

1650 if lanes < 1 {

1651 return Err(Crash::new("treeWith: lanes must be at least 1"));

1652 }

1653 let author = bool_opt("author", defaults.author)?;

1654 let date = bool_opt("date", defaults.date)?;

1655 let files = bool_opt("files", defaults.files)?;

1656 let pal = Palette {

1657 on: color_enabled(&color),

1658 };

1659 let o = TreeOptions {

1660 detail,

1661 margin,

1662 elide,

1663 icons,

1664 color,

1665 lanes,

1666 author,

1667 date,

1668 files,

1669 };

1670 let text = tree_render(interp, &o, repo, &pal, true, term_w)?;

1671 Ok(Value::text(text))

1672}

1673

1674struct CommitInfo {

1675 id: String,

1676 message: String,

1677 labels: Vec<String>,

1678 conflict: bool,

1679 empty: bool,

1680 immutable: bool,

1681 is_focus: bool,

1682 is_ancestor_of_focus: bool,

1683 is_child_of_ancestor: bool,

1684 meta: Option<crate::domain::MetaInfo>,

1685 size: Option<usize>, // lines added+removed against parent, up to SIZE_BAR_TOP

1686 nfiles: usize, // number of files changed against parent (`files` column)

1687 detail_marks: Vec<(String, char)>,

1688 children: Vec<CommitInfo>,

1689}

1690

1691impl CommitInfo {

1692 /// §Elision: a commit is *interesting* — never folded into a run — if it is

1693 /// the focus, labelled, conflicted, a leaf, or has more than one child; or

1694 /// if it is an ancestor of the focus (or a child of one) **off the trunk**.

1695 /// Trunk ancestors of the focus below the branch point are not interesting

1696 /// on that ground alone, so an uninteresting run of them folds (as in the

1697 /// worked example's `╎ 14`). The root is interesting only when it is not

1698 /// buried in a longer uninteresting run — a distant root folds into the run

1699 /// rather than being pinned at the top (§Option: far root). A run never

1700 /// straddles the trunk boundary.

1701 fn interesting(&self, trunk: &BTreeSet<String>) -> bool {

1702 self.is_focus

1703 || !self.labels.is_empty()

1704 || self.conflict

1705 || self.children.is_empty()

1706 || self.children.len() > 1

1707 || ((self.is_ancestor_of_focus || self.is_child_of_ancestor)

1708 && !trunk.contains(&self.id))

1709 }

1710}

1711

1712/// A parent commit's snapshot as seen by its children: the files value,

1713/// loaded on first use — by the parent itself or by whichever child needs to

1714/// compare against it, since only the child knows that it does — plus its

1715/// path-keyed map built at most once and shared by every child's diff.

1716/// Keying a snapshot allocates a `Vec<String>` per entry, so rebuilding it for

1717/// each child dominated `treeFull`/`treeData` on a large history.

1718struct ParentSnap<'a> {

1719 commit: &'a Value,

1720 files: &'a std::cell::OnceCell<Value>,

1721 map: &'a std::cell::OnceCell<SnapMap>,

1722 /// the commit's id when its files are still the stored tree

1723 stored: Option<&'a str>,

1724}

1725

1726impl ParentSnap<'_> {

1727 fn files(&self) -> Result<&Value, Crash> {

1728 if self.files.get().is_none() {

1729 let _ = self.files.set(self.commit.field("files")?);

1730 }

1731 Ok(self.files.get().expect("just set"))

1732 }

1733

1734 fn map(&self) -> Result<&SnapMap, Crash> {

1735 if self.map.get().is_none() {

1736 let _ = self.map.set(snapshot_map_of(self.files()?)?);

1737 }

1738 Ok(self.map.get().expect("just set"))

1739 }

1740}

1741

1742/// The id of the stored commit whose tree `commit`'s files are, read without

1743/// loading them: the tag on the backend's lazy list (`ThunkVal::origin`). An

1744/// edit that changes the files replaces that list, so this is `None` for them.

1745fn stored_origin(commit: &Value) -> Option<&str> {

1746 match commit {

1747 Value::Record(m) => match m.get("files") {

1748 Some(Value::Thunk(t)) => t.origin(),

1749 _ => None,

1750 },

1751 _ => None,

1752 }

1753}

1754

1755#[allow(clippy::too_many_arguments)]

1756fn build_info(

1757 interp: &mut Interp,

1758 opts: &TreeOptions,

1759 commit: &Value,

1760 children: &[Value],

1761 immutable: &BTreeSet<String>,

1762 focus_id: &str,

1763 anc: &BTreeSet<String>,

1764 parent_files: Option<&ParentSnap<'_>>,

1765 with_focus: bool,

1766 parent_is_ancestor: bool,

1767 parent_is_focus: bool,

1768) -> Result<CommitInfo, Crash> {

1769 let id = match commit.field("id")? {

1770 Value::Id(i) => i.to_string(),

1771 _ => String::new(),

1772 };

1773 let message = commit.field("message")?.as_text()?.to_string();

1774 let labels: Vec<String> = commit

1775 .field("labels")?

1776 .as_list()?

1777 .iter()

1778 .map(|l| l.as_text().map(|s| s.to_string()))

1779 .collect::<Result<_, _>>()?;

1780 // conflict and empty are O(1) backend queries when the backend can answer

1781 // them from tree ids (jj), without touching the file list at all. Those

1782 // answers are about the stored commits, so they are asked only while this

1783 // commit — and, for empty, its parent here — still holds its stored files:

1784 // a dry run (§1.2) renders edits that keep their ids but not their files.

1785 // Otherwise, as on the in-memory backend, fall back to walking the files.

1786 let stored = stored_origin(commit).filter(|o| *o == id);

1787 let conflict = match stored.and_then(|s| interp.backend.has_conflict(s)) {

1788 Some(c) => c,

1789 None => has_conflict(commit)?,

1790 };

1791 // `size` (a line count) and `detail_marks` are only rendered for detail ≥

1792 // 2 and for the focus and its neighbours, so skip the per-commit line

1793 // counting elsewhere — it dominates render time on large histories.

1794 let is_focus_pre = with_focus && id == focus_id;

1795 let child_is_focus = with_focus

1796 && children.iter().any(|c| {

1797 matches!(c.field("root").and_then(|r| r.field("id")), Ok(Value::Id(i)) if *i == focus_id)

1798 });

1799 let want_diff = opts.detail >= 2 || is_focus_pre || child_is_focus || parent_is_focus;

1800 let backend_empty = match (stored, parent_files.and_then(|p| p.stored)) {

1801 (Some(me), Some(parent)) => interp.backend.is_empty(me, parent),

1802 _ => None,

1803 };

1804 // this commit's own snapshot and its map, each built on first use — here

1805 // or by a child that compares against it — and shared with every child

1806 let my_files: std::cell::OnceCell<Value> = std::cell::OnceCell::new();

1807 let my_map: std::cell::OnceCell<SnapMap> = std::cell::OnceCell::new();

1808 let my_snap = ParentSnap {

1809 commit,

1810 files: &my_files,

1811 map: &my_map,

1812 stored,

1813 };

1814 // the files list is only materialized when something needs it: the diff

1815 // (detail/focus), the files data column, or the emptiness fallback

1816 let (empty, size, detail_marks, nfiles) = match parent_files {

1817 Some(parent) => {

1818 let empty = match backend_empty {

1819 Some(e) => e,

1820 // in any order: a snapshot stands for a tree (§7.3)

1821 None => crate::repo::snapshot_eq(my_snap.files()?, parent.files()?)?,

1822 };

1823 if want_diff {

1824 // both maps are built at most once per commit and reused by

1825 // this commit's children, so a diff costs one keying, not four

1826 let from_map = parent.map()?;

1827 let to_map = my_snap.map()?;

1828 let marks = touched_in_maps(from_map, to_map)?;

1829 // size: lines added plus removed against the parent (§7.11

1830 // column 5); a path changed without a changed line (an empty

1831 // file, a new file type) counts one, so only an empty commit

1832 // has no bar. The count stops where the bar does.

1833 let mut lines = 0usize;

1834 for (key, _, _) in &marks {

1835 if lines >= SIZE_BAR_TOP {

1836 break;

1837 }

1838 let cap = SIZE_BAR_TOP - lines;

1839 lines += changed_lines(from_map.get(key), to_map.get(key), cap)?.max(1);

1840 }

1841 let marks2: Vec<(String, char)> =

1842 marks.iter().map(|(p, m, _)| (p.join("/"), *m)).collect();

1843 (marks.is_empty(), Some(lines), marks2, marks.len())

1844 } else {

1845 // the files column is the number of paths changed against the

1846 // parent (specs/tree.md Step 4), so it diffs even without a bar

1847 let nfiles = if opts.files && !empty {

1848 touched_in_maps(parent.map()?, my_snap.map()?)?.len()

1849 } else {

1850 0

1851 };

1852 (empty, None, Vec::new(), nfiles)

1853 }

1854 }

1855 None => {

1856 // the top of the history: no parent to compare against, and so no

1857 // backend answer either — it is empty iff it has no files (the

1858 // root never counts as empty), and every file it has is added

1859 let nfiles = my_snap.files()?.as_list()?.len();

1860 (nfiles == 0 && id != ROOT_ID, None, Vec::new(), nfiles)

1861 }

1862 };

1863 let meta = interp.backend.meta(&id).ok();

1864 let is_focus = with_focus && id == focus_id;

1865 let is_ancestor_of_focus = anc.contains(&id);

1866 let mut infos = Vec::new();

1867 for c in children.iter() {

1868 infos.push(build_info(

1869 interp,

1870 opts,

1871 &c.field("root")?,

1872 c.field("children")?.as_list()?,

1873 immutable,

1874 focus_id,

1875 anc,

1876 Some(&my_snap),

1877 with_focus,

1878 is_ancestor_of_focus,

1879 is_focus_pre,

1880 )?);

1881 } let immutable_flag = immutable.contains(&id);

1882 Ok(CommitInfo {

1883 id,

1884 message,

1885 labels,

1886 conflict,

1887 empty,

1888 immutable: immutable_flag,

1889 is_focus,

1890 is_ancestor_of_focus,

1891 is_child_of_ancestor: parent_is_ancestor,

1892 meta,

1893 size,

1894 nfiles,

1895 detail_marks,

1896 children: infos,

1897 })

1898}

1899

1900fn tree_render(

1901 interp: &mut Interp,

1902 opts: &TreeOptions,

1903 repo: &Value,

1904 pal: &Palette,

1905 with_focus: bool,

1906 term_w: Option<usize>,

1907) -> Result<String, Crash> {

1908 // immutable set

1909 let immutable = crate::repo::compute_immutable(interp, repo).unwrap_or_default();

1910 let focus_id = match repo.field("root")?.field("id")? {

1911 Value::Id(i) => i.to_string(),

1912 _ => String::new(),

1913 };

1914 // ancestors of focus: the focus id plus every parent recorded in the

1915 // zipper's context frames — read directly rather than refocusing each

1916 // frame (an O(n) by_id per level would make this O(n²))

1917 let mut anc: BTreeSet<String> = BTreeSet::new();

1918 if let Ok(Value::Id(i)) = repo.field("root").and_then(|r| r.field("id")) {

1919 anc.insert(i.to_string());

1920 }

1921 if let Ok(ctx) = repo.field("context").and_then(|v| v.as_list().map(|x| x.to_vec())) {

1922 for frame in &ctx {

1923 if let Ok(pid) = id_of_frame_parent(frame) {

1924 anc.insert(pid);

1925 }

1926 }

1927 }

1928 // the whole history, from the top

1929 let top = crate::repo::by_id(repo, &top_id(repo)?)?.unwrap_or_else(|| repo.clone());

1930 let root_commit = top.field("root")?;

1931 let top_children = top.field("children")?;

1932 let root_info = build_info(

1933 interp,

1934 opts,

1935 &root_commit,

1936 top_children.as_list()?,

1937 &immutable,

1938 &focus_id,

1939 &anc,

1940 None,

1941 with_focus,

1942 false,

1943 false,

1944 )?;

1945 // trunk T (§Trunk)

1946 let trunk = compute_trunk(interp, repo)?;

1947 let lanes_n = opts.lanes.max(1) as usize;

1948 // Step 1 — display tree. The synthetic root is dropped when it is a pure

1949 // anchor (exactly one child): the first real commit then starts the tree

1950 // at the top, rather than pinning `⌂` above it. A root with several

1951 // children is a genuine branch point and is kept (§Option: drop root).

1952 let droot = if root_info.id == ROOT_ID && root_info.children.len() == 1 {

1953 make_display(&root_info.children[0], opts.elide, &trunk)

1954 } else {

1955 make_display(&root_info, opts.elide, &trunk)

1956 };

1957 // Step 2 — row order (topological, oldest first)

1958 let mut flat: Vec<&Display> = Vec::new();

1959 flatten_display(&droot, &mut flat);

1960 // Display uids are dense. Keep the preorder position as the heap's

1961 // second key, so a newly ready descendant wins a time tie with a later

1962 // sibling just as it does in the specification's ready set.

1963 let mut preorder = vec![0; flat.len()];

1964 for (i, n) in flat.iter().enumerate() {

1965 preorder[n.uid()] = i;

1966 }

1967 let mut ready = BinaryHeap::from([Reverse((droot.time(), 0usize))]);

1968 let mut rows: Vec<&Display> = Vec::new();

1969 while let Some(Reverse((_, i))) = ready.pop() {

1970 let n = flat[i];

1971 rows.push(n);

1972 for c in n.children() {

1973 ready.push(Reverse((c.time(), preorder[c.uid()])));

1974 }

1975 }

1976 // Step 3 — lanes

1977 let index = RowIndex::new(&rows);

1978 let placements = assign_lanes(&rows, &index, &trunk, lanes_n);

1979 // id column: shortest unique prefix among the display tree's commits, min 4

1980 // (sorted once, so each row costs a lookup rather than a scan of them all)

1981 let mut ids: Vec<String> = rows

1982 .iter()

1983 .filter_map(|n| n.commit().map(|c| c.id.clone()))

1984 .collect();

1985 ids.sort();

1986 let prefix_len = |id: &str| -> usize {

1987 crate::eval::unique_prefix_in(&ids, id).len()

1988 };

1989 // Step 4 — draw

1990 draw_rows(&rows, &index, &placements, opts, pal, lanes_n, with_focus, &prefix_len, term_w)

1991}

1992

1993fn id_of_frame_parent(frame: &Value) -> Result<String, Crash> {

1994 match frame.field("parent")?.field("id")? {

1995 Value::Id(i) => Ok(i.to_string()),

1996 v => Err(Crash::new(format!("expected an Id, got a {}", v.kind_name()))),

1997 }

1998}

1999

2000fn top_id(repo: &Value) -> Result<String, Crash> {

2001 // the topmost ancestor's id: the focus's own id when the context is empty,

2002 // otherwise the parent recorded in the *last* (outermost) zipper frame —

2003 // read directly, since refocusing each frame with by_id is O(n²) overall

2004 let ctx = repo.field("context").and_then(|v| v.as_list().map(|x| x.to_vec()))?;

2005 match ctx.last() {

2006 None => match repo.field("root")?.field("id")? {

2007 Value::Id(i) => Ok(i.to_string()),

2008 v => Err(Crash::new(format!("expected an Id, got a {}", v.kind_name()))),

2009 },

2010 Some(frame) => id_of_frame_parent(frame),

2011 }

2012}

2013

2014/// The trunk (§Trunk): the config's `trunk` revset against the whole history.

2015/// Empty → the root alone; one commit → it and its ancestors; more → crash.

2016fn compute_trunk(interp: &mut Interp, repo: &Value) -> Result<BTreeSet<String>, Crash> {

2017 let mut set = BTreeSet::new();

2018 set.insert(top_id(repo)?);

2019 let v = interp.apply_cached_revset("trunk", repo)?;

2020 let mut named: Vec<String> = Vec::new();

2021 for idv in v.as_list()?.iter() {

2022 match idv {

2023 Value::Id(id) => named.push(id.to_string()),

2024 _ => return Err(Crash::new("treeWith: trunk returned a non-Id")),

2025 }

2026 }

2027 named.sort();

2028 named.dedup();

2029 match named.len() {

2030 0 => Ok(set),

2031 1 => {

2032 let pmap: BTreeMap<String, String> =

2033 crate::repo::parent_map(repo)?.into_iter().collect();

2034 let mut cur = named[0].clone();

2035 loop {

2036 set.insert(cur.clone());

2037 match pmap.get(&cur) {

2038 Some(p) => cur = p.clone(),

2039 None => break,

2040 }

2041 }

2042 Ok(set)

2043 }

2044 n => Err(Crash::new(format!("treeWith: trunk names {} revisions", n))),

2045 }

2046}

2047

2048// ----------------------------------------------------------------------

2049// Step 1 — the display tree (§Elision)

2050// ----------------------------------------------------------------------

2051

2052enum Display {

2053 Commit {

2054 uid: usize,

2055 info: CommitInfo,

2056 children: Vec<Display>,

2057 },

2058 Run {

2059 uid: usize,

2060 count: usize,

2061 time: Option<i64>,

2062 in_trunk: bool,

2063 child: Box<Display>,

2064 },

2065 Collapsed {

2066 uid: usize,

2067 info: CommitInfo,

2068 hidden: usize,

2069 },

2070}

2071

2072impl Display {

2073 fn uid(&self) -> usize {

2074 match self {

2075 Display::Commit { uid, .. } => *uid,

2076 Display::Run { uid, .. } => *uid,

2077 Display::Collapsed { uid, .. } => *uid,

2078 }

2079 }

2080

2081 /// The node's time for the row order (Step 1). A node with no stored

2082 /// counterpart (minted in this program) has time ∞: it sorts after every

2083 /// stored one, not first as a `None` would.

2084 fn time(&self) -> i64 {

2085 let t = match self {

2086 Display::Commit { info, .. } => info.meta.as_ref().map(|m| m.time),

2087 Display::Run { time, .. } => *time,

2088 Display::Collapsed { info, .. } => info.meta.as_ref().map(|m| m.time),

2089 };

2090 t.unwrap_or(i64::MAX)

2091 }

2092

2093 fn children(&self) -> &[Display] {

2094 match self {

2095 Display::Commit { children, .. } => children,

2096 Display::Run { child, .. } => std::slice::from_ref(&**child),

2097 Display::Collapsed { .. } => &[],

2098 }

2099 }

2100

2101 fn commit(&self) -> Option<&CommitInfo> {

2102 match self {

2103 Display::Commit { info, .. } => Some(info),

2104 Display::Collapsed { info, .. } => Some(info),

2105 Display::Run { .. } => None,

2106 }

2107 }

2108

2109 fn in_trunk(&self, trunk: &BTreeSet<String>) -> bool {

2110 match self {

2111 Display::Run { in_trunk, .. } => *in_trunk,

2112 _ => self.commit().map(|c| trunk.contains(&c.id)).unwrap_or(false),

2113 }

2114 }

2115}

2116

2117fn make_display(info: &CommitInfo, elide: bool, trunk: &BTreeSet<String>) -> Display {

2118 let mut uid = 0usize;

2119 make_display_rec(info, elide, trunk, true, &mut uid)

2120}

2121

2122fn make_display_rec(

2123 info: &CommitInfo,

2124 elide: bool,

2125 trunk: &BTreeSet<String>,

2126 near: bool,

2127 uid: &mut usize,

2128) -> Display {

2129 if !elide {

2130 let my = *uid;

2131 *uid += 1;

2132 let children = info

2133 .children

2134 .iter()

2135 .map(|c| make_display_rec(c, elide, trunk, true, uid))

2136 .collect();

2137 return Display::Commit {

2138 uid: my,

2139 info: clone_info(info, Vec::new()),

2140 children,

2141 };

2142 }

2143 if !near && !info.is_ancestor_of_focus && !info.is_focus {

2144 let my = *uid;

2145 *uid += 1;

2146 return Display::Collapsed {

2147 uid: my,

2148 info: clone_info(info, Vec::new()),

2149 hidden: count_descendants(info),

2150 };

2151 }

2152 if info.interesting(trunk) {

2153 let my = *uid;

2154 *uid += 1;

2155 let children = info

2156 .children

2157 .iter()

2158 .map(|c| make_display_rec(c, elide, trunk, false, uid))

2159 .collect();

2160 return Display::Commit {

2161 uid: my,

2162 info: clone_info(info, Vec::new()),

2163 children,

2164 };

2165 }

2166 // uninteresting: gather the run down the single line of descent until the

2167 // next interesting commit (which always exists: leaves are interesting).

2168 // A run never straddles the trunk boundary: it stops before a commit whose

2169 // trunk membership differs from the run's first commit.

2170 let first_in_trunk = trunk.contains(&info.id);

2171 let mut chain: Vec<&CommitInfo> = Vec::new();

2172 let mut cur = info;

2173 while !cur.interesting(trunk) && trunk.contains(&cur.id) == first_in_trunk {

2174 chain.push(cur);

2175 cur = &cur.children[0];

2176 }

2177 // A distant root folds into the run, but a root that would form a run of

2178 // one — it is right next to an interesting commit, so it is not far — stays

2179 // visible as a normal commit at the top of the tree.

2180 if chain.len() == 1 && chain[0].id == ROOT_ID {

2181 let my = *uid;

2182 *uid += 1;

2183 let children = info

2184 .children

2185 .iter()

2186 .map(|c| make_display_rec(c, elide, trunk, near, uid))

2187 .collect();

2188 return Display::Commit {

2189 uid: my,

2190 info: clone_info(info, Vec::new()),

2191 children,

2192 };

2193 }

2194 let count = chain.len();

2195 let in_trunk = chain.iter().all(|c| trunk.contains(&c.id));

2196 let my = *uid;

2197 *uid += 1;

2198 Display::Run {

2199 uid: my,

2200 count,

2201 time: chain[0].meta.as_ref().map(|m| m.time),

2202 in_trunk,

2203 child: Box::new(make_display_rec(cur, elide, trunk, near, uid)),

2204 }

2205}

2206

2207fn count_descendants(info: &CommitInfo) -> usize {

2208 info.children.iter().map(|c| 1 + count_descendants(c)).sum()

2209}

2210

2211fn clone_info(info: &CommitInfo, children: Vec<CommitInfo>) -> CommitInfo {

2212 CommitInfo {

2213 id: info.id.clone(),

2214 message: info.message.clone(),

2215 labels: info.labels.clone(),

2216 conflict: info.conflict,

2217 empty: info.empty,

2218 immutable: info.immutable,

2219 is_focus: info.is_focus,

2220 is_ancestor_of_focus: info.is_ancestor_of_focus,

2221 is_child_of_ancestor: info.is_child_of_ancestor,

2222 meta: info.meta.clone(),

2223 size: info.size,

2224 nfiles: info.nfiles,

2225 detail_marks: info.detail_marks.clone(),

2226 children,

2227 }

2228}

2229

2230fn flatten_display<'a>(n: &'a Display, out: &mut Vec<&'a Display>) {

2231 out.push(n);

2232 for c in n.children() {

2233 flatten_display(c, out);

2234 }

2235}

2236

2237// ----------------------------------------------------------------------

2238// Step 3 — lanes

2239// ----------------------------------------------------------------------

2240

2241#[derive(Clone, Debug)]

2242enum Rail {

2243 Live,

2244 Reserved(usize),

2245}

2246

2247#[derive(Clone, Debug)]

2248struct Placement {

2249 lane: Option<usize>,

2250 fork: Option<(usize, bool)>, // (source lane, source empties below)

2251 // on a flattened last child of the trunk head (or of the root of an empty

2252 // trunk): its parent's lane, which empties below this row though no fork

2253 // is drawn (Step 3, §Overflow)

2254 ends: Option<usize>,

2255 reservations: Vec<(usize, usize)>, // (lane, child uid)

2256 flattened: bool,

2257}

2258

2259fn mark_subtree(n: &Display, set: &mut BTreeSet<usize>) {

2260 set.insert(n.uid());

2261 for c in n.children() {

2262 mark_subtree(c, set);

2263 }

2264}

2265

2266/// Relations in display-row order, indexed once for lane assignment and

2267/// size bars. Finding a parent or the focus afresh on every row made even a

2268/// single line of history take quadratic time.

2269struct RowIndex {

2270 row_of: Vec<usize>,

2271 parent: Vec<Option<usize>>,

2272 last_child: Vec<Option<usize>>,

2273 focus_adjacent: Vec<bool>,

2274}

2275

2276impl RowIndex {

2277 fn new(rows: &[&Display]) -> Self {

2278 let mut index = RowIndex {

2279 row_of: vec![0; rows.len()],

2280 parent: vec![None; rows.len()],

2281 last_child: vec![None; rows.len()],

2282 focus_adjacent: vec![false; rows.len()],

2283 };

2284 for (i, n) in rows.iter().enumerate() {

2285 index.row_of[n.uid()] = i;

2286 }

2287 for (i, n) in rows.iter().enumerate() {

2288 for c in n.children() {

2289 let child = index.row_of[c.uid()];

2290 index.parent[child] = Some(i);

2291 index.last_child[i] = Some(index.last_child[i].map_or(child, |last| last.max(child)));

2292 }

2293 }

2294 if let Some(focus) = rows.iter().position(|n| n.commit().is_some_and(|c| c.is_focus)) {

2295 if let Some(parent) = index.parent[focus] {

2296 index.focus_adjacent[parent] = true;

2297 }

2298 for c in rows[focus].children() {

2299 index.focus_adjacent[index.row_of[c.uid()]] = true;

2300 }

2301 }

2302 index

2303 }

2304}

2305

2306fn assign_lanes(

2307 rows: &[&Display],

2308 index: &RowIndex,

2309 trunk: &BTreeSet<String>,

2310 lanes_n: usize,

2311) -> Vec<Placement> {

2312 let mut rails: Vec<Option<Rail>> = vec![None; lanes_n];

2313 let mut out: Vec<Placement> = Vec::new();

2314 let mut flattened: BTreeSet<usize> = BTreeSet::new();

2315 // each node's row: "last child" and "after t" are in row order, which is

2316 // not sibling order once an edit appends a child (`new`, `rebase`)

2317 let row_of = &index.row_of;

2318 for (idx, n) in rows.iter().enumerate() {

2319 let in_trunk = n.in_trunk(trunk);

2320 let parent_idx = index.parent[idx];

2321 let parent = parent_idx.map(|i| rows[i]);

2322 let parent_lane = parent_idx.and_then(|i| out[i].lane);

2323 let is_last_child = parent_idx

2324 .map(|i| index.last_child[i] == Some(idx))

2325 .unwrap_or(false);

2326 let was_flat = flattened.contains(&n.uid());

2327 let mut lane: Option<usize> = None;

2328 let mut fork: Option<(usize, bool)> = None;

2329 let mut ends: Option<usize> = None;

2330 if !was_flat {

2331 if idx == 0 {

2332 lane = Some(0);

2333 } else if in_trunk {

2334 lane = Some(0);

2335 } else if let Some(l) =

2336 rails.iter().position(|r| matches!(r, Some(Rail::Reserved(u)) if *u == n.uid()))

2337 {

2338 lane = Some(l);

2339 } else if let (Some(p), Some(pl)) = (parent, parent_lane) {

2340 if !p.in_trunk(trunk) && is_last_child {

2341 // rule 4: inherit p's live rail

2342 lane = Some(pl);

2343 } else {

2344 // rule 5: fork to the leftmost empty lane right of p's lane

2345 match (pl + 1..lanes_n).find(|&l| rails[l].is_none()) {

2346 Some(l) => {

2347 lane = Some(l);

2348 if is_last_child {

2349 fork = Some((pl, true));

2350 rails[pl] = None;

2351 } else {

2352 fork = Some((pl, false));

2353 }

2354 }

2355 None => {

2356 // overflow is rule 5 too: when n is p's last

2357 // child (p is then the trunk head or the root of

2358 // an empty trunk, as any other trunk commit

2359 // reserves lanes for its later side children),

2360 // p's lane empties below this row (Step 3)

2361 mark_subtree(n, &mut flattened);

2362 if is_last_child {

2363 rails[pl] = None;

2364 ends = Some(pl);

2365 }

2366 }

2367 }

2368 }

2369 } else {

2370 mark_subtree(n, &mut flattened);

2371 }

2372 }

2373 let now_flat = flattened.contains(&n.uid());

2374 if !now_flat {

2375 if let Some(l) = lane {

2376 rails[l] = if n.children().is_empty() {

2377 None

2378 } else {

2379 Some(Rail::Live)

2380 };

2381 }

2382 }

2383 // reservations: a trunk node with a trunk child reserves lanes for its

2384 // side children that come after the trunk child in row order

2385 let mut reservations: Vec<(usize, usize)> = Vec::new();

2386 if !now_flat && in_trunk {

2387 let cs = n.children();

2388 if let Some(t) = cs.iter().find(|c| c.in_trunk(trunk)) {

2389 let mut after: Vec<&Display> = cs

2390 .iter()

2391 .filter(|c| row_of[c.uid()] > row_of[t.uid()])

2392 .collect();

2393 after.sort_by_key(|c| row_of[c.uid()]);

2394 for c in after {

2395 if flattened.contains(&c.uid()) {

2396 continue;

2397 }

2398 match (1..lanes_n).find(|&l| rails[l].is_none()) {

2399 Some(l) => {

2400 rails[l] = Some(Rail::Reserved(c.uid()));

2401 reservations.push((l, c.uid()));

2402 }

2403 None => mark_subtree(c, &mut flattened),

2404 }

2405 }

2406 }

2407 }

2408 out.push(Placement {

2409 lane: if now_flat { None } else { lane },

2410 fork: if now_flat { None } else { fork },

2411 ends,

2412 reservations,

2413 flattened: now_flat,

2414 });

2415 }

2416 out

2417}

2418

2419// ----------------------------------------------------------------------

2420// Step 4 — drawing

2421// ----------------------------------------------------------------------

2422

2423struct RowText {

2424 gutter: String,

2425 id: String,

2426 bar: String,

2427 msg: String,

2428 labels: String,

2429 age: String,

2430 initials: String,

2431 initials_author: String,

2432 // extra right-side columns, already joined in display order (§Step 4):

2433 // date, files changed, full author name — only the enabled ones, plain

2434 meta_extra: Vec<String>,

2435}

2436

2437fn build_row_text(

2438 n: &Display,

2439 focus_adjacent: bool,

2440 opts: &TreeOptions,

2441 pal: &Palette,

2442 with_focus: bool,

2443 prefix_len: &dyn Fn(&str) -> usize,

2444 id_w: usize,

2445) -> RowText {

2446 let c = n.commit();

2447 let is_focus = c.map(|x| x.is_focus).unwrap_or(false);

2448 let gutter = if is_focus && with_focus { pal.code("1;96", "▶ ") } else { " ".into() };

2449 // id (blank on a run row, whose count `rail_row` draws: the part that

2450 // overflows the rails area runs on into the id column)

2451 let id = match n {

2452 Display::Run { .. } => " ".repeat(id_w),

2453 _ => match c {

2454 Some(info) => {

2455 let k = prefix_len(&info.id);

2456 let p = &info.id[..k.min(info.id.len())];

2457 // prefix with `@` so the id matches the id-literal syntax (@wqzt)

2458 let colored = if info.conflict {

2459 pal.red(&format!("@{}", p))

2460 } else if info.immutable {

2461 pal.blue(&format!("@{}", p))

2462 } else if info.is_focus {

2463 pal.code("1;96", &format!("@{}", p))

2464 } else {

2465 pal.id(&format!("@{}", p))

2466 };

2467 let plain = k + 1; // +1 for the @

2468 let padded = if plain < id_w {

2469 format!("{}{}", colored, " ".repeat(id_w - plain))

2470 } else {

2471 colored

2472 };

2473 padded

2474 }

2475 None => " ".repeat(id_w),

2476 },

2477 };

2478 // size bar

2479 let show_bar = opts.detail >= 1

2480 && c.map(|x| opts.detail >= 2 || x.is_focus || focus_adjacent)

2481 .unwrap_or(false);

2482 let bar = if show_bar {

2483 c.map(|x| size_bar(x.size, pal)).unwrap_or_default()

2484 } else {

2485 String::new()

2486 };

2487 // message, coloured by state (§Colour): focus bold, conflict red, empty

2488 // dim-italic; the collapsed marker is dim

2489 let msg_first = c.map(|x| x.message.lines().next().unwrap_or("")).unwrap_or("");

2490 let mut msg = match c {

2491 Some(info) if info.empty => pal.dim_italic(msg_first),

2492 Some(info) if info.is_focus => pal.bold(msg_first),

2493 Some(info) if info.conflict => pal.red(msg_first),

2494 _ => msg_first.to_string(),

2495 };

2496 if let Display::Collapsed { hidden, .. } = n {

2497 if *hidden > 0 {

2498 if !msg.is_empty() {

2499 msg.push_str(" ");

2500 }

2501 msg.push_str(&pal.dim(&format!("⋯ {}", hidden)));

2502 }

2503 }

2504 let labels = c.map(|x| x.labels.join(" ")).unwrap_or_default();

2505 let (age, init, author) = match c.and_then(|x| x.meta.as_ref()) {

2506 // the root's margin is not shown (§worked example)

2507 Some(m) if opts.margin && c.map(|x| x.id != ROOT_ID).unwrap_or(false) => {

2508 (render_age(m.time), initials(&m.author), m.author.clone())

2509 }

2510 _ => (String::new(), String::new(), String::new()),

2511 };

2512 // extra columns (§Step 4): date, files changed, full author name — one

2513 // entry per enabled column, blank without metadata (a minted commit), so

2514 // entry k is the same column on every row

2515 let mut meta_extra: Vec<String> = Vec::new();

2516 if let Some(info) = c {

2517 if info.id != ROOT_ID {

2518 if opts.date {

2519 meta_extra.push(info.meta.as_ref().map(|m| render_date(m.time)).unwrap_or_default());

2520 }

2521 if opts.files {

2522 meta_extra.push(format!("{} files", info.nfiles));

2523 }

2524 if opts.author {

2525 meta_extra.push(info.meta.as_ref().map(|m| m.author.clone()).unwrap_or_default());

2526 }

2527 }

2528 }

2529 RowText {

2530 gutter,

2531 id,

2532 bar,

2533 msg,

2534 labels,

2535 age,

2536 initials: init,

2537 initials_author: author,

2538 meta_extra,

2539 }

2540}

2541

2542#[allow(clippy::too_many_arguments)]

2543fn draw_rows(

2544 rows: &[&Display],

2545 index: &RowIndex,

2546 placements: &[Placement],

2547 opts: &TreeOptions,

2548 pal: &Palette,

2549 lanes_n: usize,

2550 with_focus: bool,

2551 prefix_len: &dyn Fn(&str) -> usize,

2552 term_w: Option<usize>,

2553) -> Result<String, Crash> {

2554 let rail_chars = 2 * lanes_n;

2555 let overflow = placements.iter().any(|p| p.flattened);

2556 // each row's rails, drawn once; a run row's go on past the rails area

2557 // when its count does not fit

2558 let mut rail_state = vec![None; lanes_n];

2559 let rails: Vec<(Vec<char>, Vec<bool>)> = rows

2560 .iter()

2561 .zip(placements)

2562 .map(|(n, p)| {

2563 let row = rail_row(n, p, &rail_state, lanes_n, opts);

2564 advance_rail_state(&mut rail_state, n, p);

2565 row

2566 })

2567 .collect();

2568 // id column width: 4-char min prefix plus the `@` literal prefix, and

2569 // what a run count writes into it past the rails area and the space

2570 // after it

2571 let mut id_w = 5usize;

2572 for (chars, _) in &rails {

2573 id_w = id_w.max(chars.len().saturating_sub(rail_chars + 1));

2574 }

2575 for n in rows {

2576 if let Some(c) = n.commit() {

2577 id_w = id_w.max(prefix_len(&c.id) + 1); // +1 for the `@`

2578 }

2579 }

2580 let label_col = rows

2581 .iter()

2582 .any(|n| n.commit().map(|c| !c.labels.is_empty()).unwrap_or(false));

2583 // build row texts

2584 let mut texts: Vec<RowText> = Vec::new();

2585 for (i, n) in rows.iter().enumerate() {

2586 texts.push(build_row_text(n, index.focus_adjacent[i], opts, pal, with_focus, prefix_len, id_w));

2587 }

2588 // Columns 5–9 start at the same offset on every row (§Step 4). The size

2589 // bar's column is there when any row draws a bar — ` ▅`, two columns —

2590 // and blank on the rows that draw none, so a bar never shifts a message.

2591 let bar_col = texts.iter().any(|t| !t.bar.is_empty());

2592 // each row up to its message: gutter, rails, id and bar

2593 let mut heads: Vec<String> = Vec::new();

2594 for (idx, n) in rows.iter().enumerate() {

2595 let pl = &placements[idx];

2596 let t = &texts[idx];

2597 let (chars, lane0) = &rails[idx];

2598 let mut line = String::new();

2599 line.push_str(&t.gutter);

2600 // the node glyph (on a commit row) is meaning-coloured; rails lane-coloured

2601 let glyph = match (n, pl.lane) {

2602 (Display::Commit { info, .. }, Some(l)) => Some((2 * l, glyph_ansi(info))),

2603 _ => None,

2604 };

2605 line.push_str(&color_rails(chars, lane0, pal, glyph));

2606 if overflow {

2607 let status = if pl.flattened {

2608 let glyph = n.commit().map(|c| {

2609 pal.code(glyph_ansi(c), glyph_for(c, opts.icons))

2610 }).unwrap_or_default();

2611 format!("» {}", glyph)

2612 } else {

2613 String::new()

2614 };

2615 line.push_str(&pad_right(&status, 4));

2616 }

2617 line.push(' ');

2618 line.push_str(&t.id);

2619 if bar_col {

2620 line.push(' ');

2621 line.push_str(if t.bar.is_empty() { " " } else { &t.bar });

2622 }

2623 line.push_str(" ");

2624 heads.push(line);

2625 }

2626 // the columns are placed by display width as drawn (an `icons` glyph is

2627 // two columns wide), from the message column on

2628 let msg_col = rows

2629 .iter()

2630 .zip(&heads)

2631 .filter(|(n, _)| n.commit().is_some())

2632 .map(|(_, h)| width(h))

2633 .max()

2634 .unwrap_or(0);

2635 let lab_w = texts.iter().map(|t| width(&t.labels)).max().unwrap_or(0);

2636 // the data columns, each as wide as its widest entry, so that the margin

2637 // after them starts at one offset too

2638 let mut extra_w: Vec<usize> = Vec::new();

2639 for t in &texts {

2640 for (k, e) in t.meta_extra.iter().enumerate() {

2641 if k == extra_w.len() {

2642 extra_w.push(0);

2643 }

2644 extra_w[k] = extra_w[k].max(width(e));

2645 }

2646 }

2647 // the margin's age and initials, each as wide as its widest entry, so

2648 // that a `13m` among `9m`s or a single initial moves nothing

2649 let margin_w = (

2650 texts.iter().map(|t| width(&t.age)).max().unwrap_or(0),

2651 texts.iter().map(|t| width(&t.initials)).max().unwrap_or(0),

2652 );

2653 let metas: Vec<String> = texts

2654 .iter()

2655 .map(|t| meta_block(t, &extra_w, margin_w, opts, pal))

2656 .collect();

2657 // message truncation to the terminal width (§Step 4): the widest part

2658 // right of the message column (labels, data, margin) sets the room left

2659 // for every message, and only messages are cut to it, so the label and

2660 // margin columns hold

2661 if let Some(w) = term_w {

2662 let right = texts

2663 .iter()

2664 .zip(&metas)

2665 .map(|(t, m)| {

2666 if !m.is_empty() {

2667 (if label_col { 2 + lab_w } else { 0 }) + 2 + width(m)

2668 } else if !t.labels.is_empty() {

2669 2 + width(&t.labels)

2670 } else {

2671 0

2672 }

2673 })

2674 .max()

2675 .unwrap_or(0);

2676 let room = w.saturating_sub(msg_col + right);

2677 for t in texts.iter_mut() {

2678 t.msg = cut_to_width(&t.msg, room);

2679 }

2680 }

2681 let msg_w = texts.iter().map(|t| width(&t.msg)).max().unwrap_or(0);

2682 let lab_off = msg_col + msg_w + 2;

2683 let meta_off = if label_col { lab_off + lab_w + 2 } else { lab_off };

2684 let mut lines: Vec<String> = Vec::new();

2685 // Detail lines use the state below their row. Advance it once per row,

2686 // as above, rather than replaying the preceding history.

2687 rail_state.fill(None);

2688 for (idx, n) in rows.iter().enumerate() {

2689 advance_rail_state(&mut rail_state, n, &placements[idx]);

2690 let t = &texts[idx];

2691 let mut line = std::mem::take(&mut heads[idx]);

2692 if n.commit().is_some() {

2693 pad_to(&mut line, msg_col);

2694 }

2695 line.push_str(&t.msg);

2696 if label_col && !t.labels.is_empty() {

2697 pad_to(&mut line, lab_off);

2698 line.push_str(&pal.label(&t.labels));

2699 }

2700 if !metas[idx].is_empty() {

2701 pad_to(&mut line, meta_off);

2702 line.push_str(&metas[idx]);

2703 }

2704 // Remove layout padding, while preserving spaces in detail paths below.

2705 while line.ends_with(' ') { line.pop(); }

2706 // the whole focus row is highlighted with a background band across the

2707 // full terminal width (§Colour; colour only — the ▶ gutter still marks

2708 // the focus when colour is off)

2709 let is_focus_row = n.commit().map(|c| c.is_focus).unwrap_or(false);

2710 if is_focus_row && pal.on {

2711 let padded = match term_w {

2712 Some(w) if width(&line) < w => {

2713 format!("{}{}", line, " ".repeat(w - width(&line)))

2714 }

2715 _ => line.clone(),

2716 };

2717 lines.push(pal.bg_line("97;48;5;17", &padded));

2718 } else {

2719 lines.push(line);

2720 }

2721 // detail line (detail = 2, focus only)

2722 if opts.detail >= 2

2723 && with_focus

2724 && n.commit().map(|c| c.is_focus && !c.detail_marks.is_empty()).unwrap_or(false)

2725 {

2726 let c = n.commit().unwrap();

2727 let (dchars, dlane0) = detail_rail_row(&rail_state);

2728 let mut dline = String::new();

2729 dline.push_str(" ");

2730 dline.push_str(&color_rails(&dchars, &dlane0, pal, None));

2731 if overflow { dline.push_str(" "); }

2732 dline.push(' ');

2733 // the marks start two columns into the id column (§Step 4)

2734 dline.push_str(" ");

2735 let marks: Vec<String> = c

2736 .detail_marks

2737 .iter()

2738 .map(|(p, m)| {

2739 let ms = m.to_string();

2740 let colored = match m {

2741 '+' => pal.green(&ms),

2742 '−' => pal.red(&ms),

2743 '~' => pal.yellow(&ms),

2744 '✖' => pal.red(&ms),

2745 _ => ms,

2746 };

2747 format!("{} {}", colored, p)

2748 })

2749 .collect();

2750 let detail_lines = match term_w {

2751 Some(w) => wrap_detail_items(&marks, w.saturating_sub(width(&dline)).max(1)),

2752 None => vec![marks.join(" ")],

2753 };

2754 for text in detail_lines {

2755 lines.push(format!("{}{}", dline, text));

2756 }

2757 }

2758 }

2759 // Legend (§Legend): explain the symbols that actually appear, faintly, on

2760 // the right of the tree if it fits the terminal width, else at the bottom.

2761 append_legend(&mut lines, rows, opts, pal, term_w, overflow);

2762 let mut out = lines.join("\n");

2763 out.push('\n');

2764 Ok(out)

2765}

2766

2767/// Which symbols appear in the rendered tree, used to build the legend. Only

2768/// symbols that are actually shown are explained (§Legend option: only-used).

2769struct UsedSymbols {

2770 glyphs: Vec<&'static str>, // present node glyphs, in legend order

2771 run: bool, // a ╎ n run row

2772 collapsed: bool, // a ⋯ n collapsed node

2773 focus_gutter: bool, // ▶ present (a focus row exists)

2774 overflow: bool, // separate » status column

2775 detail_marks: Vec<char>, // + ~ − ✖ present in the focus's detail line

2776}

2777

2778fn collect_used(rows: &[&Display], opts: &TreeOptions, icons: bool, overflow: bool) -> UsedSymbols {

2779 let mut present: BTreeSet<&'static str> = BTreeSet::new();

2780 let mut run = false;

2781 let mut collapsed = false;

2782 let mut focus_gutter = false;

2783 let mut marks: BTreeSet<char> = BTreeSet::new();

2784 for n in rows {

2785 match n {

2786 Display::Run { .. } => run = true,

2787 Display::Commit { info, .. } | Display::Collapsed { info, .. } => {

2788 // a collapsed node only shows the ⋯ n marker when it hides

2789 // descendants; only then is the collapsed symbol used

2790 if let Display::Collapsed { hidden, .. } = n {

2791 if *hidden > 0 {

2792 collapsed = true;

2793 }

2794 }

2795 present.insert(glyph_for(info, icons));

2796 if info.is_focus {

2797 focus_gutter = true;

2798 if opts.detail >= 2 {

2799 for (_, m) in &info.detail_marks {

2800 marks.insert(*m);

2801 }

2802 }

2803 }

2804 }

2805 }

2806 }

2807 // legend glyph order: focus, ancestor, other, immutable, empty, conflict, root

2808 const ORDER: [&str; 14] =

2809 ["◉", "🌸", "●", "🌿", "○", "🍃", "◆", "🪨", "◌", "🫙", "⊗", "🔥", "⌂", "🌱"];

2810 let glyphs = ORDER.iter().filter(|g| present.contains(**g)).copied().collect();

2811 UsedSymbols {

2812 glyphs,

2813 run,

2814 collapsed,

2815 focus_gutter,

2816 detail_marks: marks.into_iter().collect(),

2817 overflow,

2818 }

2819}

2820

2821fn glyph_meaning(g: &str) -> &'static str {

2822 match g {

2823 "◉" | "🌸" => "focus",

2824 "●" | "🌿" => "ancestor of focus",

2825 "○" | "🍃" => "other commit",

2826 "◆" | "🪨" => "immutable",

2827 "◌" | "🫙" => "empty",

2828 "⊗" | "🔥" => "conflict",

2829 "⌂" | "🌱" => "root",

2830 _ => "",

2831 }

2832}

2833

2834fn mark_meaning(m: char) -> &'static str {

2835 match m {

2836 '+' => "added",

2837 '~' => "modified",

2838 '−' => "deleted",

2839 '✖' => "unresolved",

2840 _ => "",

2841 }

2842}

2843

2844/// Build the legend lines (plain, uncoloured text) for the used symbols.

2845fn legend_lines(used: &UsedSymbols) -> Vec<String> {

2846 let mut out: Vec<String> = Vec::new();

2847 for g in &used.glyphs {

2848 out.push(format!("{} {}", g, glyph_meaning(g)));

2849 }

2850 if used.focus_gutter {

2851 out.push("▶ current commit".to_string());

2852 }

2853 if used.overflow {

2854 out.push("» branch exceeds lane limit; increase lanes".to_string());

2855 }

2856 if used.run {

2857 out.push("╎ n run of n commits".to_string());

2858 }

2859 if used.collapsed {

2860 out.push("⋯ n collapsed, n hidden".to_string());

2861 }

2862 for m in &used.detail_marks {

2863 out.push(format!("{} {}", m, mark_meaning(*m)));

2864 }

2865 out

2866}

2867

2868/// Place the legend. Try the right of the tree: each legend entry is appended,

2869/// faint, to the right of a tree row starting one row from the top, past the

2870/// widest tree line. If that would exceed the terminal width (or there is no

2871/// terminal), put the legend at the bottom instead.

2872fn append_legend(

2873 lines: &mut Vec<String>,

2874 rows: &[&Display],

2875 opts: &TreeOptions,

2876 pal: &Palette,

2877 tty_width: Option<usize>,

2878 overflow: bool,

2879) {

2880 let used = collect_used(rows, opts, opts.icons, overflow);

2881 let entries = legend_lines(&used);

2882 if entries.is_empty() {

2883 return;

2884 }

2885 let tree_w = lines.iter().map(|l| width(l)).max().unwrap_or(0);

2886 let legend_w = entries.iter().map(|e| width(e)).max().unwrap_or(0);

2887 let gap = 4;

2888 let right_total = tree_w + gap + legend_w;

2889 let fits_right = tty_width.map_or(false, |w| right_total <= w);

2890 if fits_right {

2891 // pad every tree line to tree_w, then append the legend entries dim

2892 for l in lines.iter_mut() {

2893 let d = width(l);

2894 if d < tree_w {

2895 l.push_str(&" ".repeat(tree_w - d));

2896 }

2897 }

2898 for (k, e) in entries.iter().enumerate() {

2899 if k < lines.len() {

2900 lines[k].push_str(&" ".repeat(gap));

2901 lines[k].push_str(&pal.dim(e));

2902 } else {

2903 let mut l = " ".repeat(tree_w + gap);

2904 l.push_str(&pal.dim(e));

2905 lines.push(l);

2906 }

2907 }

2908 } else {

2909 lines.push(String::new());

2910 for e in &entries {

2911 lines.push(pal.dim(e));

2912 }

2913 }

2914}

2915

2916/// Update the rails above a row to the rails below it. Each occupied lane

2917/// records whether it belongs to lane 0.

2918fn advance_rail_state(state: &mut [Option<bool>], n: &Display, p: &Placement) {

2919 if let Some((src, clears)) = p.fork {

2920 if clears {

2921 state[src] = None;

2922 }

2923 }

2924 if let Some(l) = p.ends {

2925 state[l] = None;

2926 }

2927 if let Some(l) = p.lane {

2928 state[l] = if n.children().is_empty() { None } else { Some(l == 0) };

2929 }

2930 for &(l, _) in &p.reservations {

2931 state[l] = Some(false);

2932 }

2933}

2934

2935/// Rails characters for one node's row (§Step 4, the character table).

2936/// Returns the characters and, per character, whether it belongs to lane 0.

2937/// On a run row they go on past the rails area when its count does not fit.

2938fn rail_row(

2939 n: &Display,

2940 pl: &Placement,

2941 state: &[Option<bool>],

2942 lanes_n: usize,

2943 opts: &TreeOptions,

2944) -> (Vec<char>, Vec<bool>) {

2945 let mut chars = vec![' '; 2 * lanes_n];

2946 let mut lane0 = vec![false; 2 * lanes_n];

2947 // horizontal segments: (start, end) in lane coordinates

2948 let mut segments: Vec<(usize, usize)> = Vec::new();

2949 if let Some((src, _)) = pl.fork {

2950 if let Some(tgt) = pl.lane {

2951 segments.push((src, tgt));

2952 }

2953 }

2954 if let Some(l) = pl.lane {

2955 if let Some(max_r) = pl.reservations.iter().map(|&(l, _)| l).max() {

2956 segments.push((l, max_r));

2957 }

2958 }

2959 let in_segment = |i: usize| segments.iter().any(|&(a, b)| a < i && i < b);

2960 for i in 0..lanes_n {

2961 let c = if Some(i) == pl.lane {

2962 match n {

2963 Display::Run { .. } => '╎',

2964 _ => glyph_for(n.commit().unwrap(), opts.icons)

2965 .chars()

2966 .next()

2967 .unwrap(),

2968 }

2969 } else if pl.reservations.iter().any(|&(l, _)| l == i) {

2970 let right = pl.reservations.iter().any(|&(l, _)| l > i);

2971 if right {

2972 '┬'

2973 } else {

2974 '╮'

2975 }

2976 } else if pl.fork.map(|(src, _)| src == i).unwrap_or(false) {

2977 if pl.fork.unwrap().1 {

2978 '╰'

2979 } else {

2980 '├'

2981 }

2982 } else if in_segment(i) {

2983 if state[i].is_some() {

2984 '┼'

2985 } else {

2986 '─'

2987 }

2988 } else if state[i].is_some() {

2989 '│'

2990 } else {

2991 ' '

2992 };

2993 chars[2 * i] = c;

2994 lane0[2 * i] = i == 0;

2995 }

2996 // on a run row the count follows ╎, or the rightmost rail drawn right of

2997 // it, so that it covers none; it is written into the rails area and, if

2998 // needed, on through the space after it into the blank id column. A run

2999 // reserves no lane and any fork on its row comes from its left, so the

3000 // rightmost character drawn so far is ╎ or such a rail.

3001 if let (Display::Run { count, .. }, Some(l)) = (n, pl.lane) {

3002 let from = chars.iter().rposition(|&c| c != ' ').unwrap_or(2 * l) + 1;

3003 for (k, d) in format!(" {}", count).chars().enumerate() {

3004 let pos = from + k;

3005 if pos == chars.len() {

3006 chars.push(d);

3007 lane0.push(l == 0);

3008 } else {

3009 chars[pos] = d;

3010 lane0[pos] = l == 0;

3011 }

3012 }

3013 }

3014 for i in 0..lanes_n {

3015 let inside = segments.iter().any(|&(a, b)| 2 * i + 1 > 2 * a && 2 * i + 1 < 2 * b);

3016 if inside {

3017 chars[2 * i + 1] = '─';

3018 lane0[2 * i + 1] = i == 0;

3019 }

3020 }

3021 (chars, lane0)

3022}

3023

3024/// detail line (§Step 4): `│` in every lane that holds a rail below the focus

3025/// row, including the focus's own lane if it has children

3026fn detail_rail_row(state: &[Option<bool>]) -> (Vec<char>, Vec<bool>) {

3027 let lanes_n = state.len();

3028 let mut chars = vec![' '; 2 * lanes_n];

3029 let mut lane0 = vec![false; 2 * lanes_n];

3030 for i in 0..lanes_n {

3031 if let Some(is0) = state[i] {

3032 chars[2 * i] = '│';

3033 lane0[2 * i] = is0;

3034 }

3035 }

3036 (chars, lane0)

3037}

3038

3039/// Colour the rails. Rail connectors are lane-coloured (lane 0 = immutable

3040/// bright blue, others rotating accent hues); the node glyph at `glyph`

3041/// (its lane position and ANSI code) is meaning-coloured. A glyph two

3042/// columns wide (`icons`) fills both

3043/// characters of its lane, so the one after it is not drawn (§Glyphs).

3044fn color_rails(

3045 chars: &[char],

3046 lane0: &[bool],

3047 pal: &Palette,

3048 glyph: Option<(usize, &str)>,

3049) -> String {

3050 let mut s = String::new();

3051 let mut covered = false;

3052 for (i, c) in chars.iter().enumerate() {

3053 if std::mem::take(&mut covered) {

3054 continue;

3055 }

3056 covered = UnicodeWidthChar::width(*c) == Some(2);

3057 let t = c.to_string();

3058 if *c == ' ' {

3059 s.push(*c);

3060 } else if let Some((pos, code)) = glyph {

3061 if i == pos {

3062 s.push_str(&pal.code(code, &t));

3063 } else if lane0[i] {

3064 s.push_str(&pal.blue(&t));

3065 } else {

3066 s.push_str(&pal.rail(i / 2, &t));

3067 }

3068 } else if lane0[i] {

3069 s.push_str(&pal.blue(&t));

3070 } else {

3071 s.push_str(&pal.rail(i / 2, &t));

3072 }

3073 }

3074 s

3075}

3076

3077/// Wrap without dropping text or splitting ANSI sequences. Close and reopen

3078/// active styles at row boundaries so continuation prefixes stay unstyled.

3079fn wrap_display_text(text: &str, limit: usize) -> Vec<String> {

3080 let limit = limit.max(1);

3081 let mut lines = Vec::new();

3082 let mut line = String::new();

3083 let mut used = 0;

3084 let mut active = String::new();

3085 let mut chars = text.chars();

3086 while let Some(c) = chars.next() {

3087 if c == '\x1b' {

3088 let mut escape = String::from(c);

3089 for e in chars.by_ref() {

3090 escape.push(e);

3091 if e == 'm' { break; }

3092 }

3093 if escape == "\x1b[0m" { active.clear(); } else { active.push_str(&escape); }

3094 line.push_str(&escape);

3095 continue;

3096 }

3097 let cells = UnicodeWidthChar::width(c).unwrap_or(0);

3098 if used > 0 && used + cells > limit {

3099 if !active.is_empty() { line.push_str("\x1b[0m"); }

3100 lines.push(line);

3101 line = active.clone();

3102 used = 0;

3103 }

3104 line.push(c);

3105 used += cells;

3106 }

3107 if !active.is_empty() { line.push_str("\x1b[0m"); }

3108 lines.push(line);

3109 lines

3110}

3111

3112/// Keep whole detail items together when possible; split only an item that

3113/// cannot fit on an otherwise empty continuation row.

3114fn wrap_detail_items(items: &[String], limit: usize) -> Vec<String> {

3115 let mut lines = Vec::new();

3116 let mut line = String::new();

3117 for item in items {

3118 if !line.is_empty() && width(&line) + 3 + width(item) <= limit {

3119 line.push_str(" ");

3120 line.push_str(item);

3121 continue;

3122 }

3123 if !line.is_empty() { lines.push(std::mem::take(&mut line)); }

3124 let mut parts = wrap_display_text(item, limit);

3125 line = parts.pop().unwrap_or_default();

3126 lines.extend(parts);

3127 }

3128 if !line.is_empty() { lines.push(line); }

3129 lines

3130}

3131

3132/// `s` cut to display width `w`, ending with `…` when anything is cut (and

3133/// there is a column for it): the message on a terminal (§Step 4). Colour

3134/// escapes are kept whole and not counted, and those past the cut still

3135/// follow it, so every style `s` opens is closed.

3136fn cut_to_width(s: &str, w: usize) -> String {

3137 if width(s) <= w {

3138 return s.to_string();

3139 }

3140 let mut kept = String::new();

3141 // escapes not yet followed by a kept character

3142 let mut pending = String::new();

3143 let mut used = 0usize;

3144 let mut in_esc = false;

3145 let mut full = false;

3146 for c in s.chars() {

3147 if c == '\x1b' {

3148 in_esc = true;

3149 }

3150 if in_esc {

3151 in_esc = c != 'm';

3152 pending.push(c);

3153 continue;

3154 }

3155 if full {

3156 continue;

3157 }

3158 // one column is left for the `…`

3159 let cw = UnicodeWidthChar::width(c).unwrap_or(0);

3160 if used + cw >= w {

3161 full = true;

3162 continue;

3163 }

3164 kept.push_str(&pending);

3165 pending.clear();

3166 kept.push(c);

3167 used += cw;

3168 }

3169 let ellipsis = if w == 0 { "" } else { "…" };

3170 format!("{}{}{}", kept.trim_end_matches(' '), ellipsis, pending)

3171}

3172

3173/// Pad `line` with spaces to display column `col`.

3174fn pad_to(line: &mut String, col: usize) {

3175 let w = width(line);

3176 if w < col {

3177 line.push_str(&" ".repeat(col - w));

3178 }

3179}

3180

3181/// A row's metadata block (§Step 4): the data columns (date / files /

3182/// author), each padded to its column's width in `extra_w`, then the margin

3183/// (age and initials), each right-aligned in its width in `margin_w`. Empty

3184/// when the row shows none of them.

3185fn meta_block(

3186 t: &RowText,

3187 extra_w: &[usize],

3188 margin_w: (usize, usize),

3189 opts: &TreeOptions,

3190 pal: &Palette,

3191) -> String {

3192 let mut meta: Vec<String> = Vec::new();

3193 for (e, w) in t.meta_extra.iter().zip(extra_w) {

3194 let mut s = if e.is_empty() { String::new() } else { pal.grey(4, e) };

3195 s.push_str(&" ".repeat(w - width(e)));

3196 meta.push(s);

3197 }

3198 if opts.margin && !t.age.is_empty() {

3199 let (age_w, init_w) = margin_w;

3200 let mut age = " ".repeat(age_w - width(&t.age));

3201 age.push_str(&pal.grey(4, &t.age));

3202 meta.push(age);

3203 let mut init = " ".repeat(init_w - width(&t.initials));

3204 init.push_str(&pal.author(&t.initials_author, &t.initials));

3205 meta.push(init);

3206 }

3207 meta.join(" ").trim_end().to_string()

3208}

3209

3210fn glyph_for(info: &CommitInfo, icons: bool) -> &'static str {

3211 if !icons {

3212 if info.id == ROOT_ID {

3213 "⌂"

3214 } else if info.conflict {

3215 "⊗"

3216 } else if info.empty {

3217 "◌"

3218 } else if info.immutable {

3219 "◆"

3220 } else if info.is_focus {

3221 "◉"

3222 } else if info.is_ancestor_of_focus {

3223 "●"

3224 } else {

3225 "○"

3226 }

3227 } else if info.id == ROOT_ID {

3228 "🌱"

3229 } else if info.conflict {

3230 "🔥"

3231 } else if info.empty {

3232 "🫙"

3233 } else if info.immutable {

3234 "🪨"

3235 } else if info.is_focus {

3236 "🌸"

3237 } else if info.is_ancestor_of_focus {

3238 "🌿"

3239 } else {

3240 "🍃"

3241 }

3242}

3243

3244/// The ANSI colour code for a node glyph, by meaning (§Colour: glyphs carry

3245/// meaning; colour only adds emphasis). Mirrors the precedence of `glyph_for`.

3246fn glyph_ansi(info: &CommitInfo) -> &'static str {

3247 node_ansi(glyph_for(info, false))

3248}

3249

3250fn node_ansi(glyph: &str) -> &'static str {

3251 match glyph {

3252 "⌂" => "1;95", // root: bold magenta

3253 "⊗" => "91", // conflict: bright red

3254 "◌" => "2", // empty: dim

3255 "◆" => "94", // immutable: bright blue

3256 "◉" => "1;96", // focus: bold cyan

3257 "●" => "92", // ancestor of focus: bright green

3258 _ => "97", // other commit: bright white

3259 }

3260}

3261

3262fn size_bar(size: Option<usize>, pal: &Palette) -> String {

3263 match size {

3264 None | Some(0) => String::new(),

3265 Some(n) => {

3266 // one glyph per threshold 1, 10, 50, 200, 1000 (§7.11 column 5)

3267 let (bar, level) = if n >= SIZE_BAR_TOP {

3268 ("▇", 4)

3269 } else if n >= 200 {

3270 ("▅", 3)

3271 } else if n >= 50 {

3272 ("▃", 2)

3273 } else if n >= 10 {

3274 ("▂", 1)

3275 } else {

3276 ("▁", 0)

3277 };

3278 pal.accent(level, bar)

3279 }

3280 }

3281}

3282

3283fn initials(name: &str) -> String {

3284 name.split_whitespace()

3285 .filter_map(|w| w.chars().next())

3286 .take(2)

3287 .collect::<String>()

3288 .to_lowercase()

3289}

3290

3291#[cfg(test)]

3292mod tests {

3293 use super::*;

3294 use crate::value::BlobVal;

3295 use std::collections::HashMap;

3296

3297 /// Lines deleted plus inserted by a shortest diff of `a` to `b`, uncapped

3298 /// and found without anything `changed_lines` uses: both lengths less

3299 /// twice a longest common subsequence, which Hyyrö's bit-parallel LCS

3300 /// finds a machine word of `a` at a time.

3301 fn exact(a: &[String], b: &[String]) -> usize {

3302 let words = a.len().div_ceil(64);

3303 // per line of `a`, a bit at each place it occurs in `a`

3304 let mut masks: HashMap<&str, Vec<u64>> = HashMap::new();

3305 for (i, l) in a.iter().enumerate() {

3306 masks.entry(l.as_str()).or_insert_with(|| vec![0; words])[i / 64] |= 1 << (i % 64);

3307 }

3308 let absent = vec![0; words];

3309 // after each line of `b`, the zero bits of `v` up to a place in `a`

3310 // count a longest common subsequence of `a` up to there and `b` so

3311 // far; the bits past the end of `a` stay ones

3312 let mut v = vec![u64::MAX; words];

3313 for l in b {

3314 let m = masks.get(l.as_str()).unwrap_or(&absent);

3315 let mut carry = false;

3316 for (v, m) in v.iter_mut().zip(m) {

3317 let (sum, c1) = v.overflowing_add(*v & m);

3318 let (sum, c2) = sum.overflowing_add(carry as u64);

3319 carry = c1 || c2;

3320 *v = sum | (*v & !m);

3321 }

3322 }

3323 let common: usize = v.iter().map(|w| w.count_zeros() as usize).sum();

3324 a.len() + b.len() - 2 * common

3325 }

3326

3327 /// `changed_lines` from `a` to `b` and back is the exact count, or the

3328 /// cap if that is less: under the size bar's cap, caps on either side of

3329 /// the first search's 64 rounds, `cap` if given, and the exact count plus

3330 /// one, which leaves no room: a bound or a search stopped short that

3331 /// overcounts at all returns the cap there.

3332 fn check(a: &[String], b: &[String], cap: Option<usize>) {

3333 let (va, vb) = (BlobVal::text_blob(&a.concat()), BlobVal::text_blob(&b.concat()));

3334 let want = exact(a, b);

3335 assert_eq!(want, exact(b, a));

3336 let mut caps = vec![1, 64, 65, want + 1, SIZE_BAR_TOP];

3337 caps.extend(cap);

3338 caps.retain(|c| *c <= SIZE_BAR_TOP);

3339 for cap in caps {

3340 for (from, to) in [(&va, &vb), (&vb, &va)] {

3341 let got = changed_lines(Some(from), Some(to), cap).unwrap();

3342 assert_eq!(got, want.min(cap), "cap {}, {} and {} lines", cap, a.len(), b.len());

3343 }

3344 }

3345 }

3346

3347 /// xorshift64*: the same numbers on every run

3348 struct Rng(u64);

3349

3350 impl Rng {

3351 fn below(&mut self, n: usize) -> usize {

3352 self.0 ^= self.0 >> 12;

3353 self.0 ^= self.0 << 25;

3354 self.0 ^= self.0 >> 27;

3355 (self.0.wrapping_mul(0x2545_f491_4f6c_dd1d) >> 32) as usize % n

3356 }

3357 }

3358

3359 #[test]

3360 fn changed_lines_is_exact_up_to_its_cap() {

3361 // the size bar is drawn from this count (§7.11 column 5), and no

3362 // shortcut may change it, whatever the machine or the content.

3363 // A few lines repeating, disjoint adjacent pairs of them swapped, or

3364 // lines a whole number of periods apart each replaced by the line

3365 // after it (two lines each): no line occurs once on either side, and

3366 // every diagonal the period divides runs along equal lines from one

3367 // change to the next. Swapping leaves how many times each line

3368 // occurs as it was; replacing always turns the same line into the

3369 // same other one, so the counts alone bound it by its size

3370 for period in [2, 3] {

3371 let lines: Vec<String> = (0..3000).map(|i| format!("l{}\n", i % period)).collect();

3372 for changes in [1, 33, 499, 501] {

3373 let (mut swapped, mut replaced) = (lines.clone(), lines.clone());

3374 let step = 2990 / changes;

3375 let periods = step / period * period;

3376 for k in 0..changes {

3377 let at = 3 + step * k;

3378 swapped.swap(at, at + 1);

3379 let at = 3 + periods * k;

3380 replaced[at] = lines[at + 1].clone();

3381 }

3382 check(&lines, &swapped, None);

3383 check(&lines, &replaced, None);

3384 }

3385 }

3386 // runs of one line swapped: a shortest diff keeps the longer run

3387 let runs = |x: &str, n: usize, y: &str, m: usize| -> Vec<String> {

3388 let run = |l: &str, n| std::iter::repeat_n(format!("{}\n", l), n);

3389 run(x, n).chain(run(y, m)).collect()

3390 };

3391 check(&runs("a", 499, "b", 501), &runs("b", 501, "a", 500), None);

3392 check(&runs("a", 500, "b", 501), &runs("b", 501, "a", 500), None);

3393 // distinct lines, blocks moved past as many others: two lines per line

3394 // moved, where only the lines that occur once on each side bound it

3395 let lines: Vec<String> = (0..4000).map(|i| format!("line {}\n", i)).collect();

3396 for lens in [&[90; 5][..], &[100, 100, 100, 100, 99], &[100; 5], &[250, 251], &[600]] {

3397 let mut moved = lines.clone();

3398 for (j, len) in lens.iter().enumerate() {

3399 let at = 100 + 700 * j;

3400 let block: Vec<String> = moved.drain(at..at + len).collect();

3401 moved.splice(at + len..at + len, block);

3402 }

3403 check(&lines, &moved, None);

3404 }

3405 // random edits of random files, of two lines up to mostly distinct

3406 // ones: lines inserted, removed, replaced, and blocks moved

3407 let mut rng = Rng(0x9e37_79b9_7f4a_7c15);

3408 for _ in 0..40 {

3409 let distinct = [2, 5, 50, 1 << 20][rng.below(4)];

3410 let line = |rng: &mut Rng| format!("{}\n", rng.below(distinct));

3411 let a: Vec<String> = (0..rng.below(800)).map(|_| line(&mut rng)).collect();

3412 let mut b = a.clone();

3413 for _ in 0..rng.below(300) {

3414 let at = rng.below(b.len() + 1);

3415 match rng.below(4) {

3416 0 => b.insert(at, line(&mut rng)),

3417 1 if at < b.len() => {

3418 b.remove(at);

3419 }

3420 2 if at < b.len() => b[at] = line(&mut rng),

3421 _ => {

3422 let end = (at + rng.below(40)).min(b.len());

3423 let block: Vec<String> = b.drain(at..end).collect();

3424 let to = rng.below(b.len() + 1);

3425 b.splice(to..to, block);

3426 }

3427 }

3428 }

3429 check(&a, &b, Some(1 + rng.below(SIZE_BAR_TOP)));

3430 }

3431 }

3432

3433 #[test]

3434 fn banded_distance_is_exact_under_its_max() {

3435 // the search `line_distance` falls back on, checked on its own,

3436 // since `changed_lines` only reaches it where Myers' search would

3437 // take long. Under the exact count plus one the band has no room to

3438 // spare, so a word wrongly updated or left alone at its edges

3439 // overcounts there. Files of a few words, random or repeating a few

3440 // lines, with a band narrower than them under most caps

3441 let text = |ls: &[usize]| -> Vec<String> {

3442 ls.iter().map(|l| format!("{}\n", l)).collect()

3443 };

3444 let mut rng = Rng(0x2545_f491_4f6c_dd1d);

3445 for _ in 0..200 {

3446 let distinct = [1, 2, 3, 50][rng.below(4)];

3447 let most = [70, 300, 700][rng.below(3)];

3448 let len = rng.below(most);

3449 let periodic = rng.below(2) == 0;

3450 let a: Vec<usize> = (0..len)

3451 .map(|i| if periodic { i % distinct } else { rng.below(distinct) })

3452 .collect();

3453 let mut b = a.clone();

3454 for _ in 0..rng.below(60) {

3455 let at = rng.below(b.len() + 1);

3456 match rng.below(5) {

3457 0 => b.insert(at, rng.below(distinct)),

3458 1 if at < b.len() => {

3459 b.remove(at);

3460 }

3461 2 if at < b.len() => b[at] = rng.below(distinct),

3462 3 if at + 1 < b.len() => b.swap(at, at + 1),

3463 _ => {

3464 let end = (at + rng.below(40)).min(b.len());

3465 let block: Vec<usize> = b.drain(at..end).collect();

3466 let to = rng.below(b.len() + 1);

3467 b.splice(to..to, block);

3468 }

3469 }

3470 }

3471 let want = exact(&text(&a), &text(&b));

3472 for max in [1, 2, want + 1, want + 2, 64, 65, SIZE_BAR_TOP, 1 + rng.below(want + 2)] {

3473 for (x, y) in [(&a, &b), (&b, &a)] {

3474 let mut steps = 0;

3475 let got = banded_distance(x, y, distinct, max, &mut steps);

3476 assert_eq!(got, want.min(max), "max {}, {:?} and {:?}", max, x, y);

3477 assert!(steps <= banded_steps(x.len(), y.len(), max));

3478 }

3479 }

3480 }

3481 }

3482

3483 #[test]

3484 fn line_distance_takes_steps_by_the_band_not_by_the_file() {

3485 // two lines alternating, 480 pairs of neighbours swapped: 960 lines.

3486 // Myers' search runs along equal lines on every other diagonal from

3487 // one swap to the next, a pass over the file for each of about 500

3488 // diagonals, and on such a file of a million lines drawing the size

3489 // bar took seconds. `line_distance` gives it up once it has taken as

3490 // many steps as the bit-parallel search takes at most, 18 words per

3491 // line under the size bar's cap, so it takes at most twice that and

3492 // one diagonal with its run, whatever the lines are

3493 let a: Vec<usize> = (0..100_000).map(|i| i % 2).collect();

3494 let mut b = a.clone();

3495 for k in 0..480 {

3496 b.swap(1000 + 200 * k, 1001 + 200 * k);

3497 }

3498 let (mut plain, mut steps) = (0, 0);

3499 assert_eq!(edit_distance(&a, &b, SIZE_BAR_TOP, usize::MAX, &mut plain), Some(960));

3500 assert_eq!(line_distance(&a, &b, 2, SIZE_BAR_TOP, &mut steps), 960);

3501 let most = banded_steps(a.len(), b.len(), SIZE_BAR_TOP);

3502 assert!(most <= 18 * WORD * a.len(), "{} steps at most", most);

3503 assert!(steps <= 2 * most + DIAGONAL + a.len(), "{} steps", steps);

3504 assert!(plain > 400 * a.len(), "{} steps", plain);

3505 }

3506

3507 #[test]

3508 fn line_distance_gives_up_where_the_bit_parallel_search_costs_less() {

3509 // the hand-over is where it saves time, not where the two searches

3510 // have taken as many steps. Two lines alternating, 32 pairs of

3511 // neighbours swapped far apart: Myers' search compares about twice

3512 // as many pairs of lines as `banded_distance` takes word steps, but

3513 // a word step costs several comparisons, so it is the cheaper search

3514 // and finishes. Giving it up there made the search over a million

3515 // such lines take three times as long in a debug build

3516 let a: Vec<usize> = (0..100_000).map(|i| i % 2).collect();

3517 let mut b = a.clone();

3518 for k in 0..32 {

3519 b.swap(1001 + 3000 * k, 1002 + 3000 * k);

3520 }

3521 let (mut plain, mut steps) = (0, 0);

3522 assert_eq!(edit_distance(&a, &b, SIZE_BAR_TOP, usize::MAX, &mut plain), Some(64));

3523 assert_eq!(line_distance(&a, &b, 2, SIZE_BAR_TOP, &mut steps), 64);

3524 assert_eq!(steps, plain);

3525 // distinct lines, a block of 400 moved past 10000 others: Myers'

3526 // search reaches some 320000 diagonals, on most of which no line is

3527 // equal, and reaching one costs about twice a word step, so it gives

3528 // up and the two searches together take fewer steps than it alone

3529 let a: Vec<usize> = (0..10_400).collect();

3530 let b: Vec<usize> = (400..10_400).chain(0..400).collect();

3531 let (mut plain, mut steps) = (0, 0);

3532 assert_eq!(edit_distance(&a, &b, SIZE_BAR_TOP, usize::MAX, &mut plain), Some(800));

3533 assert_eq!(line_distance(&a, &b, a.len(), SIZE_BAR_TOP, &mut steps), 800);

3534 assert!(steps < plain, "{} steps, {} alone", steps, plain);

3535 }

3536

3537 #[test]

3538 fn reorder_bound_keeps_no_line_more_often_than_either_side_has_it() {

3539 // the bound only spares `changed_lines` a search: the exact counts

3540 // above hold with any lower bound, however loose, so only this pins

3541 // how tight it is. Lines that occur once on each side keep at most a

3542 // longest sequence of them in the same order on both: ten reversed

3543 // keep one

3544 let distinct: Vec<usize> = (0..10).collect();

3545 let reversed: Vec<usize> = (0..10).rev().collect();

3546 assert_eq!(reorder_bound(&distinct, &reversed, 10), 18);

3547 // any other line is kept at most as many times as the side with

3548 // fewer of it has it: two lines alternating with 501 of the 1500

3549 // `0`s turned into `1`s keep 999 `0`s and 1500 `1`s. Counting them

3550 // only up to the shorter side kept all 3000, a bound of 0, and the

3551 // search ran over the whole file

3552 let alternating: Vec<usize> = (0..3000).map(|i| i % 2).collect();

3553 let mut replaced = alternating.clone();

3554 for k in 0..501 {

3555 replaced[2 * k] = 1;

3556 }

3557 assert_eq!(reorder_bound(&alternating, &replaced, 2), 1002);

3558 assert_eq!(reorder_bound(&replaced, &alternating, 2), 1002);

3559 // the two kinds side by side add up

3560 let then = |once: &[usize], others: &[usize]| -> Vec<usize> {

3561 once.iter().copied().chain(others.iter().map(|l| l + 10)).collect()

3562 };

3563 let (a, b) = (then(&distinct, &alternating), then(&reversed, &replaced));

3564 assert_eq!(reorder_bound(&a, &b, 12), 1020);

3565 }

3566}