comfy_table/utils/arrangement/
dynamic.rs

1use unicode_width::UnicodeWidthStr;
2
3use super::constraint;
4use super::helper::*;
5use super::{ColumnDisplayInfo, DisplayInfos};
6use crate::style::*;
7use crate::utils::formatting::content_split::split_line;
8use crate::{Column, Table};
9
10/// Try to find the best fit for a given content and table_width
11///
12/// 1. Determine the amount of available space after applying fixed columns, padding, and borders.
13/// 2. Now that we know how much space we have to work with, we have to check again for
14///    LowerBoundary constraints. If there are any columns that have a higher LowerBoundary,
15///    we have to fix that column to this size.
16/// 3. Check if there are any columns that require less space than the average
17///    remaining space for the remaining columns. (This includes the MaxWidth constraint).
18/// 4. Take those columns, fix their size and add the surplus in space to the remaining space.
19/// 5. Repeat step 2-3 until no columns with smaller size than average remaining space are left.
20/// 6. At this point, the remaining spaces is equally distributed between all columns.
21///    It get's a little tricky now. Check the documentation of [optimize_space_after_split]
22///    for more information.
23/// 7. Divide the remaining space in relatively equal chunks.
24///
25/// This breaks when:
26///
27/// 1. A user assigns fixed sizes to a few columns, which are larger than the terminal when combined.
28/// 2. A user provides more than 100% column width across a few columns.
29pub fn arrange(
30    table: &Table,
31    infos: &mut DisplayInfos,
32    table_width: usize,
33    max_content_widths: &[u16],
34) {
35    let visible_columns = count_visible_columns(&table.columns);
36
37    // Step 1
38    // Find out how much space there is left.
39    let mut remaining_width: usize =
40        available_content_width(table, infos, visible_columns, table_width);
41    let mut remaining_columns = count_remaining_columns(visible_columns, infos);
42
43    #[cfg(feature = "debug")]
44    println!(
45        "dynamic::arrange: Table width: {table_width}, Start remaining width {remaining_width}"
46    );
47    #[cfg(feature = "debug")]
48    println!("dynamic::arrange: Max content widths: {max_content_widths:#?}");
49
50    // Step 2.
51    //
52    // Iterate through all undecided columns and enforce LowerBoundary constraints, if they're
53    // bigger than the current average space.
54    if remaining_columns > 0 {
55        (remaining_width, remaining_columns) = enforce_lower_boundary_constraints(
56            table,
57            infos,
58            remaining_width,
59            remaining_columns,
60            visible_columns,
61        );
62    }
63
64    // Step 3-5.
65    // Find all columns that require less space than the average.
66    // Returns the remaining available width and the amount of remaining columns that need handling
67    let (mut remaining_width, mut remaining_columns) = find_columns_that_fit_into_average(
68        table,
69        infos,
70        remaining_width,
71        remaining_columns,
72        visible_columns,
73        max_content_widths,
74    );
75
76    #[cfg(feature = "debug")]
77    {
78        println!("After less than average: {infos:#?}");
79        println!("Remaining width {remaining_width}, column {remaining_columns}");
80    }
81
82    // Step 6
83    // All remaining columns should get an equal amount of remaining space.
84    // However, we check if we can save some space after the content has been split.
85    //
86    // We only do this if there are remaining columns.
87    if remaining_columns > 0 {
88        // This is where Step 5 happens.
89        (remaining_width, remaining_columns) = optimize_space_after_split(
90            table,
91            &table.columns,
92            infos,
93            remaining_width,
94            remaining_columns,
95        );
96    }
97
98    #[cfg(feature = "debug")]
99    {
100        println!("dynamic::arrange: After optimize: {infos:#?}",);
101        println!("dynamic::arrange: Remaining width {remaining_width}, column {remaining_columns}",);
102    }
103
104    // Early exit and one branch of Part 7.
105    //
106    // All columns have been successfully assigned a width.
107    // However, in case the user specified that the full terminal width should always be fully
108    // utilized, we have to equally distribute the remaining space across all columns.
109    if remaining_columns == 0 {
110        if remaining_width > 0 && matches!(table.arrangement, ContentArrangement::DynamicFullWidth)
111        {
112            use_full_width(infos, remaining_width);
113            #[cfg(feature = "debug")]
114            println!("dynamic::arrange: After full width: {infos:#?}");
115        }
116        return;
117    }
118
119    // Step 7. Equally distribute the remaining_width to all remaining columns
120    // If we have less than one space per remaining column, give at least one space per column
121    if remaining_width < remaining_columns {
122        remaining_width = remaining_columns;
123    }
124
125    distribute_remaining_space(&table.columns, infos, remaining_width, remaining_columns);
126
127    #[cfg(feature = "debug")]
128    println!("dynamic::arrange: After distribute: {infos:#?}");
129}
130
131/// Step 1
132///
133/// This function calculates the amount of remaining space that can be distributed between
134/// all remaining columns.
135///
136/// Take the current terminal width and
137/// - Subtract borders
138/// - Subtract padding
139/// - Subtract columns that already have a fixed width.
140///
141/// This value is converted to a i32 to handle negative values in case we work with a very small
142/// terminal.
143fn available_content_width(
144    table: &Table,
145    infos: &DisplayInfos,
146    visible_columns: usize,
147    mut width: usize,
148) -> usize {
149    let border_count = count_border_columns(table, visible_columns);
150    width = width.saturating_sub(border_count);
151
152    // Subtract all paddings from the remaining width.
153    for column in table.columns.iter() {
154        if infos.contains_key(&column.index) {
155            continue;
156        }
157        // Remove the fixed padding for each column
158        let (left, right) = column.padding;
159        width = width.saturating_sub((left + right).into());
160    }
161
162    // Remove all already fixed sizes from the remaining_width.
163    for info in infos.values() {
164        if info.is_hidden {
165            continue;
166        }
167        width = width.saturating_sub(info.width().into());
168    }
169
170    width
171}
172
173/// Step 2-4
174/// This function is part of the column width calculation process.
175/// It checks if there are columns that take less space than there's currently available in average
176/// for each column.
177///
178/// The algorithm is a while loop with a nested for loop.
179/// 1. We iterate over all columns and check if there are columns that take less space.
180/// 2. If we find one or more such columns, we fix their width and add the surplus space to the
181///     remaining space. Due to this step, the average space per column increased. Now some other
182///     column might be fixed in width as well.
183/// 3. Do step 1 and 2, as long as there are columns left and as long as we find columns
184///     that take up less space than the current remaining average.
185///
186/// Parameters:
187/// - `table_width`: The absolute amount of available space.
188/// - `remaining_width`: This is the amount of space that isn't yet reserved by any other column.
189///                      We need this to determine the average space each column has left.
190///                      Any columns that needs less than this average receives a fixed width.
191///                      The leftover space can then be used for the other columns.
192/// - `visible_columns`: All visible columns that should be displayed.
193///
194/// Returns:
195/// `(remaining_width: usize, remaining_columns: u16)`
196fn find_columns_that_fit_into_average(
197    table: &Table,
198    infos: &mut DisplayInfos,
199    mut remaining_width: usize,
200    mut remaining_columns: usize,
201    visible_columns: usize,
202    max_content_widths: &[u16],
203) -> (usize, usize) {
204    let mut found_smaller = true;
205    while found_smaller {
206        found_smaller = false;
207
208        // There are no columns left to check. Proceed to the next step
209        if remaining_columns == 0 {
210            break;
211        }
212
213        let mut average_space = remaining_width / remaining_columns;
214        // We have no space left, the terminal is either tiny or the other columns are huge.
215        if average_space == 0 {
216            break;
217        }
218
219        for column in table.columns.iter() {
220            // Ignore hidden columns
221            // We already checked this column, skip it
222            if infos.contains_key(&column.index) {
223                continue;
224            }
225
226            let max_column_width = max_content_widths[column.index];
227
228            // The column has a MaxWidth Constraint.
229            // we can fix the column to this max_width and mark it as checked if these
230            // two conditions are met:
231            // - The average remaining space is bigger then the MaxWidth constraint.
232            // - The actual max content of the column is bigger than the MaxWidth constraint.
233            if let Some(max_width) = constraint::max(table, &column.constraint, visible_columns) {
234                // Max/Min constraints always include padding!
235                let average_space_with_padding =
236                    average_space + usize::from(column.padding_width());
237
238                let width_with_padding = max_column_width + column.padding_width();
239                // Check that both conditions mentioned above are met.
240                if usize::from(max_width) <= average_space_with_padding
241                    && width_with_padding >= max_width
242                {
243                    // Save the calculated info, this column has been handled.
244                    let width = absolute_width_with_padding(column, max_width);
245                    let info = ColumnDisplayInfo::new(column, width);
246                    infos.insert(column.index, info);
247
248                    #[cfg(feature = "debug")]
249                    println!(
250                        "dynamic::find_columns_that_fit_into_average: Fixed column {} via MaxWidth constraint with size {}, as it's bigger than average {}",
251                        column.index, width, average_space
252                    );
253
254                    // Continue with new recalculated width
255                    remaining_width = remaining_width.saturating_sub(width.into());
256                    remaining_columns -= 1;
257
258                    if remaining_columns == 0 {
259                        break;
260                    }
261                    average_space = remaining_width / remaining_columns;
262                    found_smaller = true;
263                    continue;
264                }
265            }
266
267            // The column has a smaller or equal max_content_width than the average space.
268            // Fix the width to max_content_width and mark it as checked
269            if usize::from(max_column_width) <= average_space {
270                let info = ColumnDisplayInfo::new(column, max_column_width);
271                infos.insert(column.index, info);
272
273                #[cfg(feature = "debug")]
274                println!(
275                    "dynamic::find_columns_that_fit_into_average: Fixed column {} with size {}, as it's smaller than average {}",
276                    column.index, max_column_width, average_space
277                );
278
279                // Continue with new recalculated width
280                remaining_width = remaining_width.saturating_sub(max_column_width.into());
281                remaining_columns -= 1;
282                if remaining_columns == 0 {
283                    break;
284                }
285                average_space = remaining_width / remaining_columns;
286                found_smaller = true;
287            }
288        }
289    }
290
291    (remaining_width, remaining_columns)
292}
293
294/// Step 5
295///
296/// Determine, whether there are any columns that are allowed to occupy more width than the current
297/// `average_space` via a [LowerBoundary] constraint.
298///
299/// These columns will then get fixed to the width specified in the [LowerBoundary] constraint.
300///
301/// I.e. if a column has to have at least 10 characters, but the average width left for a column is
302/// only 6, we fix the column to this 10 character minimum!
303fn enforce_lower_boundary_constraints(
304    table: &Table,
305    infos: &mut DisplayInfos,
306    mut remaining_width: usize,
307    mut remaining_columns: usize,
308    visible_columns: usize,
309) -> (usize, usize) {
310    let mut average_space = remaining_width / remaining_columns;
311    for column in table.columns.iter() {
312        // Ignore hidden columns
313        // We already checked this column, skip it
314        if infos.contains_key(&column.index) {
315            continue;
316        }
317
318        // Check whether the column has a LowerBoundary constraint.
319        let min_width =
320            if let Some(min_width) = constraint::min(table, &column.constraint, visible_columns) {
321                min_width
322            } else {
323                continue;
324            };
325
326        // Only proceed if the average spaces is smaller than the specified lower boundary.
327        if average_space >= min_width.into() {
328            continue;
329        }
330
331        // This column would get smaller than the specified lower boundary.
332        // Fix its width!!!
333        let width = absolute_width_with_padding(column, min_width);
334        let info = ColumnDisplayInfo::new(column, width);
335        infos.insert(column.index, info);
336
337        #[cfg(feature = "debug")]
338        println!(
339            "dynamic::enforce_lower_boundary_constraints: Fixed column {} to min constraint width {}",
340            column.index, width
341        );
342
343        // Continue with new recalculated width
344        remaining_width = remaining_width.saturating_sub(width.into());
345        remaining_columns -= 1;
346        if remaining_columns == 0 {
347            break;
348        }
349        average_space = remaining_width / remaining_columns;
350        continue;
351    }
352
353    (remaining_width, remaining_columns)
354}
355
356/// Step 5.
357///
358/// Some Column's are too big and need to be split.
359/// We're now going to simulate how this might look like.
360/// The reason for this is the way we're splitting, which is to prefer a split at a delimiter.
361/// This can lead to a column needing less space than it was initially assigned.
362///
363/// Example:
364/// A column is allowed to have a width of 10 characters.
365/// A cell's content looks like this `sometest sometest`, which is 17 chars wide.
366/// After splitting at the default delimiter (space), it looks like this:
367/// ```text
368/// sometest
369/// sometest
370/// ```
371/// Even though the column required 17 spaces beforehand, it can now be shrunk to 8 chars width.
372///
373/// By doing this for each column, we can save a lot of space in some edge-cases.
374fn optimize_space_after_split(
375    table: &Table,
376    columns: &[Column],
377    infos: &mut DisplayInfos,
378    mut remaining_width: usize,
379    mut remaining_columns: usize,
380) -> (usize, usize) {
381    let mut found_smaller = true;
382    // Calculate the average space that remains for each column.
383    let mut average_space = remaining_width / remaining_columns;
384
385    #[cfg(feature = "debug")]
386    println!(
387        "dynamic::optimize_space_after_split: Start with average_space {}",
388        average_space
389    );
390
391    // Do this as long as we find a smaller column
392    while found_smaller {
393        found_smaller = false;
394        for column in columns.iter() {
395            // We already checked this column, skip it
396            if infos.contains_key(&column.index) {
397                continue;
398            }
399
400            let longest_line = longest_line_after_split(average_space, column, table);
401
402            #[cfg(feature = "debug")]
403            println!(
404                "dynamic::optimize_space_after_split: Longest line after split for column {} is {}",
405                column.index, longest_line
406            );
407
408            // If there's a considerable amount space left after splitting, we freeze the column and
409            // set its content width to the calculated post-split width.
410            let remaining_space = average_space.saturating_sub(longest_line);
411            if remaining_space >= 3 {
412                let info =
413                    ColumnDisplayInfo::new(column, longest_line.try_into().unwrap_or(u16::MAX));
414                infos.insert(column.index, info);
415
416                remaining_width = remaining_width.saturating_sub(longest_line);
417                remaining_columns -= 1;
418                if remaining_columns == 0 {
419                    break;
420                }
421                average_space = remaining_width / remaining_columns;
422
423                #[cfg(feature = "debug")]
424                println!(
425                    "dynamic::optimize_space_after_split: average_space is now {}",
426                    average_space
427                );
428                found_smaller = true;
429            }
430        }
431    }
432
433    (remaining_width, remaining_columns)
434}
435
436/// Part of Step 5.
437///
438/// This function simulates the split of a Column's content and returns the longest
439/// existing line after the split.
440///
441/// A lot of this logic is duplicated from the [utils::format::format_row] function.
442fn longest_line_after_split(average_space: usize, column: &Column, table: &Table) -> usize {
443    // Collect all resulting lines of the column in a single vector.
444    // That way we can easily determine the longest line afterwards.
445    let mut column_lines = Vec::new();
446
447    // Iterate
448    for cell in table.column_cells_with_header_iter(column.index) {
449        // Only look at rows that actually contain this cell.
450        let cell = match cell {
451            Some(cell) => cell,
452            None => continue,
453        };
454
455        let delimiter = delimiter(table, column, cell);
456
457        // Create a temporary ColumnDisplayInfo with the average space as width.
458        // That way we can simulate how the split text will look like.
459        let info = ColumnDisplayInfo::new(column, average_space.try_into().unwrap_or(u16::MAX));
460
461        // Iterate over each line and split it into multiple lines, if necessary.
462        // Newlines added by the user will be preserved.
463        for line in cell.content.iter() {
464            if line.width() > average_space {
465                let mut parts = split_line(line, &info, delimiter);
466
467                #[cfg(feature = "debug")]
468                println!(
469                    "dynamic::longest_line_after_split: Splitting line with width {}. Original:\n    {}\nSplitted:\n    {:?}",
470                    line.width(), line, parts
471                );
472
473                column_lines.append(&mut parts);
474            } else {
475                column_lines.push(line.into());
476            }
477        }
478    }
479
480    // Get the longest line, default to length 0 if no lines exist.
481    column_lines
482        .iter()
483        .map(|line| line.width())
484        .max()
485        .unwrap_or(0)
486}
487
488/// Step 6 - First branch
489///
490/// At this point of time, all columns have been assigned some kind of width!
491/// The user wants to utilize the full width of the terminal and there's space left.
492///
493/// Equally distribute the remaining space between all columns.
494fn use_full_width(infos: &mut DisplayInfos, remaining_width: usize) {
495    let visible_columns = infos.iter().filter(|(_, info)| !info.is_hidden).count();
496
497    if visible_columns == 0 {
498        return;
499    }
500
501    // Calculate the amount of average remaining space per column.
502    // Since we do integer division, there is most likely a little bit of non equally-divisible space.
503    // We then try to distribute it as fair as possible (from left to right).
504    let average_space = remaining_width / visible_columns;
505    let mut excess = remaining_width - (average_space * visible_columns);
506
507    for (_, info) in infos.iter_mut() {
508        // Ignore hidden columns
509        if info.is_hidden {
510            continue;
511        }
512
513        // Distribute the non-divisible excess from left-to right until nothing is left.
514        let width = if excess > 0 {
515            excess -= 1;
516            (average_space + 1).try_into().unwrap_or(u16::MAX)
517        } else {
518            average_space.try_into().unwrap_or(u16::MAX)
519        };
520
521        info.content_width += width;
522    }
523}
524
525/// Step 6 - Second branch
526///
527/// Not all columns have a determined width yet -> The content still doesn't fully fit into the
528/// given width.
529///
530/// This function now equally distributes the remaining width between the remaining columns.
531fn distribute_remaining_space(
532    columns: &[Column],
533    infos: &mut DisplayInfos,
534    remaining_width: usize,
535    remaining_columns: usize,
536) {
537    // Calculate the amount of average remaining space per column.
538    // Since we do integer division, there is most likely a little bit of non equally-divisible space.
539    // We then try to distribute it as fair as possible (from left to right).
540    let average_space = remaining_width / remaining_columns;
541    let mut excess = remaining_width - (average_space * remaining_columns);
542
543    for column in columns.iter() {
544        // Ignore hidden columns
545        if infos.contains_key(&column.index) {
546            continue;
547        }
548
549        // Distribute the non-divisible excess from left-to right until nothing is left.
550        let width = if excess > 0 {
551            excess -= 1;
552            (average_space + 1).try_into().unwrap_or(u16::MAX)
553        } else {
554            average_space.try_into().unwrap_or(u16::MAX)
555        };
556
557        let info = ColumnDisplayInfo::new(column, width);
558        infos.insert(column.index, info);
559    }
560}