Compare commits

..
7 changed files with 147 additions and 158 deletions
+8 -9
View File
@@ -203,11 +203,12 @@ pub(super) fn pie(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx, inne
// ---------------------------------------------------------------- treemap
/// Worst aspect ratio of a row with the given sum, smallest and largest area.
fn worst(s: f64, mn: f64, mx: f64, side: f64) -> f64 {
fn worst(row: &[f64], side: f64) -> f64 {
let s: f64 = row.iter().sum();
if s <= 0.0 || side <= 0.0 {
return f64::INFINITY;
}
let (mn, mx) = row.iter().fold((f64::INFINITY, 0.0f64), |(a, b), v| (a.min(*v), b.max(*v)));
let s2 = s * s;
let w2 = side * side;
(w2 * mx / s2).max(s2 / (w2 * mn))
@@ -224,8 +225,6 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
let mut out = Vec::with_capacity(items.len());
let mut rem = r;
let mut row: Vec<(usize, f64)> = Vec::new();
// The row's sum, smallest and largest area, kept as items join so each step is O(1).
let (mut sum, mut mn, mut mx) = (0.0f64, f64::INFINITY, 0.0f64);
let mut i = 0;
let layout = |row: &[(usize, f64)], rem: &mut Bx, out: &mut Vec<(usize, Bx)>| {
let s: f64 = row.iter().map(|x| x.1).sum();
@@ -257,14 +256,15 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
while let Some(&(j, v)) = items.get(i) {
let a = v * scale;
let side = rem.w.min(rem.h) as f64;
if row.is_empty() || worst(sum + a, mn.min(a), mx.max(a), side) <= worst(sum, mn, mx, side) {
let cur: Vec<f64> = row.iter().map(|x| x.1).collect();
let mut with = cur.clone();
with.push(a);
if row.is_empty() || worst(&with, side) <= worst(&cur, side) {
row.push((j, a));
(sum, mn, mx) = (sum + a, mn.min(a), mx.max(a));
i += 1;
} else {
layout(&row, &mut rem, &mut out);
row.clear();
(sum, mn, mx) = (0.0, f64::INFINITY, 0.0);
}
}
if !row.is_empty() {
@@ -279,7 +279,6 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
s.values.iter().take(MAX_MARKERS).enumerate().filter_map(|(j, v)| v.filter(|v| *v > 0.0).map(|v| (j, v))).collect();
items.sort_by(|a, b| b.1.total_cmp(&a.1));
let f = Fmt::new(&s.number_format);
let value_of: std::collections::HashMap<usize, f64> = items.iter().copied().collect();
for (j, b) in squarify(&items, area) {
let fill = point_color(data, j);
ctx.rect(b.x, b.y, b.w, b.h, fill, Some((WHITE, 1.5)));
@@ -287,7 +286,7 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
let name = ctx.fit(&cat_label(data, j), LABEL_SIZE, b.w - 8.0);
ctx.text(b.x + 4.0, b.y + 4.0, &name, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
if chart.data_labels && b.h > LABEL_SIZE * 3.2 {
let v = value_of.get(&j).copied().unwrap_or(0.0);
let v = items.iter().find(|x| x.0 == j).map(|x| x.1).unwrap_or(0.0);
let t = ctx.fit(&f.format(v, None), LABEL_SIZE, b.w - 8.0);
ctx.text(b.x + 4.0, b.y + 4.0 + LABEL_SIZE * 1.4, &t, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
}
-73
View File
@@ -695,79 +695,6 @@ fn bands_unit() {
assert!(w.len() > 2);
}
/// The wrapper `wrap_lines` replaced, re-measuring strings, as the reference for its lines.
fn wrap_lines_remeasuring(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
let mut out = Vec::new();
for para in text.split('\n') {
let mut line = String::new();
for word in para.split(' ') {
let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
line = cand;
} else {
out.push(std::mem::take(&mut line));
line = word.to_string();
}
while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
let chars: Vec<char> = line.chars().collect();
let (mut lo, mut hi) = (1usize, chars.len());
while lo < hi {
let mid = lo + (hi - lo).div_ceil(2);
let cut: String = chars[..mid].iter().collect();
if gridcraft_pdf::text_width(font, size, &cut) <= width {
lo = mid;
} else {
hi = mid - 1;
}
}
if lo == chars.len() {
break;
}
out.push(chars[..lo].iter().collect());
line = chars[lo..].iter().collect();
}
if out.len() > 2000 {
return out;
}
}
out.push(line);
}
out
}
#[test]
fn wrap_lines_matches_the_remeasuring_wrapper() {
let texts = [
"the quick brown fox jumps",
"Supercalifragilistic",
"a b c\n\nverylongwordthatneedsbreaking short\nend ",
"Wide WWWWWWWWWW words, iiiiiiii narrow ones; mixed MMMMiiiiMMMM",
"€ ü ß — unicode Ünïcödé text",
"",
" ",
];
for text in texts {
for font in [Font::Helvetica, Font::HelveticaBold, Font::Courier] {
for (size, width) in [(10.0, 50.0), (10.0, 20.0), (11.0, 1.0), (8.0, 300.0), (12.0, 0.0)] {
assert_eq!(wrap_lines(text, font, size, width), wrap_lines_remeasuring(text, font, size, width), "{text:?} {font:?} {size} {width}");
}
}
}
}
#[test]
fn wrapping_a_long_word_in_a_narrow_box_stops_at_the_line_limit() {
// One character per line: the old wrapper re-measured and copied the rest of the word for
// each of the 100,000 lines before checking the limit.
let word = "w".repeat(100_000);
let lines = wrap_lines(&word, Font::Helvetica, 10.0, 1.0);
assert!(lines.len() <= 2002, "{}", lines.len());
assert!(lines.iter().all(|l| l == "w"));
// A long paragraph in a very wide box is one line.
let para = vec!["word"; 50_000].join(" ");
assert_eq!(wrap_lines(&para, Font::Helvetica, 10.0, 1.0e9), vec![para.clone()]);
}
#[test]
fn center_across_spans_following_empty_center_across_cells() {
let mut styles = StyleTable::default();
+24 -39
View File
@@ -3,57 +3,42 @@ use super::{CellRef, Color, Font, HAlign, MAX_COLS, Page, Point, RangeRef, Sheet
const PAD_PX: f32 = 2.0;
/// Most lines [`wrap_lines`] returns (it may return one more, the rest of a paragraph).
const MAX_WRAP_LINES: usize = 2000;
/// Word-wraps `text` to `width` points.
///
/// Widths are kept as running sums of glyph widths (the sum `text_width` makes), so each
/// character is measured once: re-measuring the line for every word, or the rest of an
/// over-long word for every piece cut from it, made a long paragraph or word quadratic.
pub(super) fn wrap_lines(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
let units_of = |s: &str| -> u64 { s.chars().map(|c| u64::from(font.char_width(c))).sum() };
let fits = |units: u64| units as f32 * size / 1000.0 <= width;
let space = units_of(" ");
let mut out = Vec::new();
for para in text.split('\n') {
let mut line = String::new();
let mut line_units: u64 = 0;
for word in para.split(' ') {
let word_units = units_of(word);
if line.is_empty() {
line.push_str(word);
line_units = word_units;
} else if fits(line_units + space + word_units) {
line.push(' ');
line.push_str(word);
line_units += space + word_units;
let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
line = cand;
} else {
out.push(std::mem::take(&mut line));
line.push_str(word);
line_units = word_units;
line = word.to_string();
}
// Break a single over-long word by characters: each piece is the longest that fits
// (at least one character).
if !fits(line_units) && line.chars().nth(1).is_some() {
let mut piece = String::new();
let mut units: u64 = 0;
for c in line.chars() {
let w = u64::from(font.char_width(c));
if !piece.is_empty() && !fits(units + w) {
out.push(std::mem::take(&mut piece));
units = 0;
if out.len() > MAX_WRAP_LINES {
return out;
}
// Break a single over-long word by characters. The cut that fits is found by binary
// search (each try measures one candidate prefix), so an over-long word costs
// O(n log n) measurements instead of re-measuring the whole cut per character for
// every emitted line (`a` × 100k pasted text would be cubic worst case).
while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
let chars: Vec<char> = line.chars().collect();
let (mut lo, mut hi) = (1usize, chars.len());
while lo < hi {
let mid = lo + (hi - lo).div_ceil(2);
let cut: String = chars[..mid].iter().collect();
if gridcraft_pdf::text_width(font, size, &cut) <= width {
lo = mid;
} else {
hi = mid - 1;
}
piece.push(c);
units += w;
}
line = piece;
line_units = units;
if lo == chars.len() {
break;
}
out.push(chars[..lo].iter().collect());
line = chars[lo..].iter().collect();
}
if out.len() > MAX_WRAP_LINES {
if out.len() > 2000 {
return out;
}
}
+24
View File
@@ -57,6 +57,10 @@ fn rows_ref(sheet: &str, origin: CellRef, col: u32, rows: &[u32]) -> Option<Stri
/// Most category rows a PivotChart plots.
const MAX_CHART_ROWS: usize = 10_000;
/// Most series a PivotChart gets: the chart renderer reads at most 255 series, and each one owns
/// reference text as long as its category rows, copied into every linked chart.
const MAX_CHART_SERIES: usize = 255;
/// A PivotChart's series for a report written at `origin`: categories are the innermost row
/// items, one series per item column (column items × value fields); totals are left out.
pub fn chart_series(sheet: &str, origin: CellRef, out: &Output) -> Vec<Series> {
@@ -64,6 +68,7 @@ pub fn chart_series(sheet: &str, origin: CellRef, out: &Output) -> Vec<Series> {
let categories = out.label_col.and_then(|c| rows_ref(sheet, origin, c, &rows));
out.chart_cols
.iter()
.take(MAX_CHART_SERIES)
.filter_map(|(c, name)| {
Some(Series {
name: Some(format!("\"{}\"", name.replace('"', "\"\""))),
@@ -106,3 +111,22 @@ pub fn clear_output(wb: &mut Workbook, sheet: usize, idx: usize) {
p.last_range = None;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_pivot_chart_gets_at_most_the_series_the_renderer_reads() {
let out = Output {
grid: vec![],
row_kinds: vec![],
body_offset: 0,
width: 1000,
chart_rows: vec![1, 2, 3],
chart_cols: (1..1000).map(|c| (c, format!("S{c}"))).collect(),
label_col: Some(0),
};
assert_eq!(chart_series("Sheet1", CellRef::new(0, 0), &out).len(), MAX_CHART_SERIES);
}
}
+62 -29
View File
@@ -1,5 +1,7 @@
use super::items::{Acc, FieldItems, build_tree, collect_siblings, is_collapsed, item_label};
use super::output::{AggMap, CellKind, ColKind, ColSpec, Ctx, Grid, Line, LineKind, Output, RowKind, ValSrc, data_cols_exceed_sheet, flatten_cols};
use super::output::{
AggMap, CellKind, ColKind, ColSpec, Ctx, Grid, Line, LineKind, Output, RowKind, ValSrc, caption, data_cols_exceed_sheet, flatten_cols,
};
use super::{
CalcSet, CellError, CellRef, HashMap, HashSet, MAX_AXIS_FIELDS, MAX_COLS, MAX_VALUE_FIELDS, PivotDateGroup, PivotField, PivotFilter, PivotFunc,
PivotLayout, PivotShowAs, PivotTable, PivotValue, Source, Value, Workbook, read_source,
@@ -92,6 +94,10 @@ struct AggregateData {
col_leaves: HashSet<Vec<u32>>,
}
/// Most accumulators (groups times value columns) one report may hold: twice what the 5 million
/// group limit allowed at one value field.
const MAX_ACCUMULATORS: usize = 16_000_000;
fn aggregate_record(
input: &AggregateInput<'_>,
data: &mut AggregateData,
@@ -150,7 +156,9 @@ fn aggregate_record(
if !input.cols.is_empty() && data_cols_exceed_sheet(data.col_leaves.len(), input.pt.grand_totals_rows, input.vals.len()) {
return Err("The PivotTable report will not fit on the sheet.".into());
}
if data.aggs.len() > 5_000_000 {
// Each entry holds one accumulator per value field and calculated-field source column, so the
// width counts too: a handful of groups over hundreds of fields is large as well.
if data.aggs.len() > 5_000_000 || data.aggs.len().saturating_mul(input.vals.len() + input.extra.len()) > MAX_ACCUMULATORS {
return Err("The PivotTable report is too large.".into());
}
Ok(())
@@ -257,8 +265,8 @@ fn write_headers(g: &mut Grid, input: HeaderInput<'_>) -> Result<(), String> {
let lv = spec.path.len().saturating_sub(1);
let label = spec.path.last().and_then(|it| col_items.get(lv).map(|fi| fi.label(*it))).unwrap_or_default();
let text = match vi {
Some(vi) if k > 1 => format!("{label} {}", val_name(*vi)),
_ => format!("{label} Total"),
Some(vi) if k > 1 => caption(&label, &val_name(*vi)),
_ => caption(&label, "Total"),
};
g.set(first_level + lv, c, Value::text(text), CellKind::ColLabel, 0, None);
}
@@ -316,6 +324,7 @@ struct ShowContext<'a> {
value_index: usize,
level0: &'a [u32],
siblings: &'a HashMap<Vec<u32>, Vec<u32>>,
cache: &'a ShowCache,
}
fn number(value: &Option<Value>) -> Option<f64> {
@@ -332,42 +341,65 @@ fn ratio(a: Value, b: Option<Value>) -> Value {
}
}
/// What Running Total and Rank need from other cells, computed once per sibling set instead of
/// once per displayed value (which rescanned the whole set every time).
type ShowKey = (Vec<u32>, Vec<u32>, usize);
/// Cumulative values by top-level item, and the total of all of them.
type RunningTotals = (HashMap<u32, f64>, f64);
#[derive(Default)]
struct ShowCache {
/// Ranked values' sibling numbers, sorted ascending without repeats, by (parent, column, value).
ranks: std::cell::RefCell<HashMap<ShowKey, Vec<f64>>>,
/// Running totals by top-level item, with the total of all of them, by (rest of path, column, value).
running: std::cell::RefCell<HashMap<ShowKey, RunningTotals>>,
}
fn running_total(raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
let Some((first, _)) = context.row_path.split_first() else { return raw };
let Some((first, rest)) = context.row_path.split_first() else { return raw };
if !matches!(raw, Value::Number(_)) {
return raw;
}
let mut total = 0.0;
for item in context.level0 {
let mut path = context.row_path.to_vec();
if let Some(first_item) = path.first_mut() {
*first_item = *item;
let mut cache = context.cache.running.borrow_mut();
let (by_item, all) = cache.entry((rest.to_vec(), context.col_path.to_vec(), context.value_index)).or_insert_with(|| {
let mut total = 0.0;
let mut by_item = HashMap::new();
for item in context.level0 {
let mut path = Vec::with_capacity(rest.len() + 1);
path.push(*item);
path.extend_from_slice(rest);
total += number(&lookup.get(&path, context.col_path, context.value_index)).unwrap_or(0.0);
by_item.entry(*item).or_insert(total);
}
total += number(&lookup.get(&path, context.col_path, context.value_index)).unwrap_or(0.0);
if item == first {
break;
}
}
Value::number(total)
(by_item, total)
});
Value::number(by_item.get(first).copied().unwrap_or(*all))
}
fn ranked_value(raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
let Some((_, parent)) = context.row_path.split_last() else { return Value::Empty };
let Some(me) = raw.as_f64() else { return raw };
let siblings = context.siblings.get(parent).cloned().unwrap_or_default();
let mut cache = context.cache.ranks.borrow_mut();
let sorted = cache.entry((parent.to_vec(), context.col_path.to_vec(), context.value_index)).or_insert_with(|| {
let mut all: Vec<f64> = context
.siblings
.get(parent)
.into_iter()
.flatten()
.filter_map(|sibling| {
let mut path = parent.to_vec();
path.push(*sibling);
number(&lookup.get(&path, context.col_path, context.value_index))
})
.collect();
all.sort_by(f64::total_cmp);
all.dedup();
all
});
// Excel's ranks are dense: ties share a rank and the next value takes the next one
// (5, 4, 3, 3, 4 rank 1, 2, 3, 3, 2), so count the distinct larger values.
let mut larger: Vec<f64> = siblings
.into_iter()
.filter_map(|sibling| {
let mut path = parent.to_vec();
path.push(sibling);
number(&lookup.get(&path, context.col_path, context.value_index)).filter(|value| *value > me)
})
.collect();
larger.sort_by(f64::total_cmp);
larger.dedup();
Value::number(larger.len() as f64 + 1.0)
let larger = sorted.len() - sorted.partition_point(|value| *value <= me);
Value::number(larger as f64 + 1.0)
}
fn show_value(definition: &PivotValue, raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
@@ -637,6 +669,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
})
.collect();
let lookup = ValueLookup { wb, source: src, calc: &calc, vals: &vals, extra: &extra, aggs: &aggs, value_count: k };
let show_cache = ShowCache::default();
let mut chart_rows: Vec<u32> = Vec::new();
let chart_cols: Vec<(u32, String)> = data_cols
.iter()
@@ -694,7 +727,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
let Some((_, vdef)) = vals.get(*vi) else { continue };
let cp = spec.path.as_slice();
let Some(raw) = lookup.get(rp, cp, *vi) else { continue };
let context = ShowContext { row_path: rp, col_path: cp, value_index: *vi, level0: &level0, siblings: &siblings };
let context = ShowContext { row_path: rp, col_path: cp, value_index: *vi, level0: &level0, siblings: &siblings, cache: &show_cache };
let shown = show_value(vdef, raw, &lookup, &context);
if let Some(pr) = probe.as_deref_mut() {
if pr.at == Some((r, l + j)) {
+29 -3
View File
@@ -121,6 +121,18 @@ pub(super) enum ColKind {
Grand,
}
/// Longest item caption Excel keeps; a subtotal caption repeats its parent's label for every value
/// field at every level, so a long source label is cut rather than multiplied.
const MAX_CAPTION_LABEL_CHARS: usize = 255;
/// `label` (cut to [`MAX_CAPTION_LABEL_CHARS`]) and `suffix`, as in "East Total".
pub(super) fn caption(label: &str, suffix: &str) -> String {
let mut out: String = label.chars().take(MAX_CAPTION_LABEL_CHARS).collect();
out.push(' ');
out.push_str(suffix);
out
}
pub(super) struct ColSpec {
pub(super) kind: ColKind,
pub(super) path: Vec<u32>,
@@ -162,7 +174,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.to_vec(),
values: true,
labels: vec![(col, Value::text(format!("{label} {name}")), indent, None)],
labels: vec![(col, Value::text(caption(label, name)), indent, None)],
vi: Some(vi),
});
}
@@ -249,7 +261,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.clone(),
values: true,
labels: vec![(col, Value::text(format!("{label} Total")), indent, None)],
labels: vec![(col, Value::text(caption(&label, "Total")), indent, None)],
vi,
});
}
@@ -316,7 +328,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.clone(),
values: true,
labels: vec![(col, Value::text(format!("{label} Total")), 0, None)],
labels: vec![(col, Value::text(caption(&label, "Total")), 0, None)],
vi,
});
}
@@ -438,3 +450,17 @@ pub(super) fn cell_style(lk: &Look, rk: RowKind, cell: &OutCell, last_header: bo
}
s
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn captions_cut_a_long_parent_label() {
assert_eq!(caption("East", "Total"), "East Total");
let long = "é".repeat(100_000);
let c = caption(&long, "Sum of Sales");
assert_eq!(c.chars().count(), MAX_CAPTION_LABEL_CHARS + " Sum of Sales".len());
assert!(c.ends_with(" Sum of Sales"));
}
}
-5
View File
@@ -136,9 +136,6 @@ pub(crate) fn fixed(a: f64, decimals: usize) -> (String, String) {
/// General format squeezed into `max_chars` characters. Excel shows fewer decimals, then
/// scientific notation, then "####" when a column is narrow; `None` means the caller paints "####".
pub fn format_general_fit(n: f64, max_chars: usize) -> Option<String> {
// The widest fixed rendering of a double is about 330 characters; a larger request only
// pads zero decimals the trim below throws away.
let max_chars = max_chars.min(1024);
if !n.is_finite() {
return None;
}
@@ -217,8 +214,6 @@ mod tests {
fn general_fit() {
assert_eq!(format_general_fit(1e11, 11).as_deref(), Some("1E+11"));
assert_eq!(format_general_fit(12345678901.0, 11).as_deref(), Some("12345678901"));
// A huge width neither allocates width-sized padding nor changes the text.
assert_eq!(format_general_fit(1.5, usize::MAX).as_deref(), Some("1.5"));
assert_eq!(format_general_fit(123456789012.0, 11).as_deref(), Some("1.23457E+11"));
assert_eq!(format_general_fit(0.1 + 0.2, 11).as_deref(), Some("0.3"));
assert_eq!(format_general_fit(1.0 / 3.0, 11).as_deref(), Some("0.333333333"));