1 #include "smartcolsP.h"
2 #include "mbsalign.h"
3
4 static void dbg_column(struct libscols_table *tb, struct libscols_column *cl)
5 {
6 struct libscols_wstat *st;
7
8 if (scols_column_is_hidden(cl)) {
9 DBG(COL, ul_debugobj(cl, "%s (hidden) ignored", cl->header.data));
10 return;
11 }
12
13 st = &cl->wstat;
14
15 DBG(COL, ul_debugobj(cl, "%15s seq=%zu, width=%zd, "
16 "hint=%d, max=%zu, min=%zu, "
17 "0x04%x [%s%s%s]",
18
19 cl->header.data, cl->seqnum, cl->width,
20 cl->width_hint >= 1.0 ? (int) cl->width_hint :
21 (int) (cl->width_hint * tb->termwidth),
22 st->width_max,
23 st->width_min,
24 cl->flags,
25 cl->flags & SCOLS_FL_TRUNC ? "trunc" : "",
26 scols_column_is_right(cl) ? " right" : "",
27 scols_column_is_noextremes(cl) ? " noextrem" : ""));
28 }
29
30 static void dbg_columns(struct libscols_table *tb)
31 {
32 struct libscols_iter itr;
33 struct libscols_column *cl;
34
35 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
36 while (scols_table_next_column(tb, &itr, &cl) == 0)
37 dbg_column(tb, cl);
38 }
39
40 static int count_cell_width(struct libscols_table *tb,
41 struct libscols_line *ln,
42 struct libscols_column *cl,
43 struct ul_buffer *buf)
44 {
45 size_t len;
46 char *data;
47 int rc;
48 struct libscols_cell *ce;
49 struct libscols_wstat *st;
50
51 rc = __cell_to_buffer(tb, ln, cl, buf);
52 if (rc)
53 return rc;
54
55 data = ul_buffer_get_data(buf, NULL, NULL);
56 if (!data)
57 len = 0;
58 else if (scols_column_is_customwrap(cl))
59 len = cl->wrap_chunksize(cl, data, cl->wrapfunc_data);
60 else if (scols_table_is_noencoding(tb))
61 len = mbs_width(data);
62 else
63 len = mbs_safe_width(data);
64
65 if (len == (size_t) -1) /* ignore broken multibyte strings */
66 len = 0;
67
68 ce = scols_line_get_cell(ln, cl->seqnum);
69 ce->width = len;
70
71 st = &cl->wstat;
72 st->width_max = max(len, st->width_max);
73
74 if (scols_column_is_tree(cl)) {
75 size_t treewidth = ul_buffer_get_safe_pointer_width(buf, SCOLS_BUFPTR_TREEEND);
76 cl->width_treeart = max(cl->width_treeart, treewidth);
77 }
78
79 return 0;
80 }
81
82 static int walk_count_cell_width(struct libscols_table *tb,
83 struct libscols_line *ln,
84 struct libscols_column *cl,
85 void *data)
86 {
87 return count_cell_width(tb, ln, cl, (struct ul_buffer *) data);
88 }
89
90 static double sqrtroot(double num)
91 {
92 double tmp = 0, sq = num / 2;
93
94 while (sq != tmp){
95 tmp = sq;
96 sq = (num / tmp + tmp) / 2;
97 }
98 return sq;
99 }
100
101 static void count_column_deviation(struct libscols_table *tb, struct libscols_column *cl)
102 {
103 struct libscols_wstat *st;
104 struct libscols_iter itr;
105 struct libscols_line *ln;
106 struct libscols_cell *ce;
107 size_t sum = 0, n = 0, extra = 0;
108
109 st = &cl->wstat;
110
111 if (scols_column_is_tree(cl) && has_groups(tb))
112 extra = tb->grpset_size + 1;
113
114 /* count average */
115 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
116 while (scols_table_next_line(tb, &itr, &ln) == 0) {
117 ce = scols_line_get_cell(ln, cl->seqnum);
118
119 n++;
120 sum += ce->width + extra;
121 }
122
123 if (n)
124 st->width_avg = sum / n;
125
126 /* count deviation */
127 if (n > 1) {
128 double variance;
129
130 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
131 while (scols_table_next_line(tb, &itr, &ln) == 0) {
132 double diff;
133 ce = scols_line_get_cell(ln, cl->seqnum);
134
135 diff = (double) ce->width - st->width_avg;
136 st->width_sqr_sum += diff * diff; /* aka pow(x, 2) */
137 }
138
139 variance = st->width_sqr_sum / (n - 1);
140 st->width_deviation = sqrtroot(variance);
141 }
142
143 DBG(COL, ul_debugobj(cl, "%15s avg=%g, deviation=%g",
144 cl->header.data,
145 st->width_avg,
146 st->width_deviation));
147 }
148
149 /*
150 * This function counts column width.
151 */
152 static int count_column_width(struct libscols_table *tb,
153 struct libscols_column *cl,
154 struct ul_buffer *buf)
155 {
156 int rc = 0, no_header = 0;
157 const char *data;
158 struct libscols_wstat *st;
159 struct libscols_iter itr;
160 struct libscols_line *ln;
161
162 assert(tb);
163 assert(cl);
164
165 st = &cl->wstat;
166
167 cl->width = 0;
168 memset(st, 0, sizeof(struct libscols_wstat));
169
170 /* set minimal width according to width_hint */
171 if (cl->width_hint < 1 && scols_table_is_maxout(tb) && tb->is_term) {
172 st->width_min = (size_t) (cl->width_hint * tb->termwidth);
173 if (st->width_min && !is_last_column(cl))
174 st->width_min--;
175 }
176
177 /* set minimal width according to header width */
178 data = scols_cell_get_data(&cl->header);
179 if (data) {
180 size_t len = scols_table_is_noencoding(tb) ?
181 mbs_width(data) : mbs_safe_width(data);
182
183 st->width_min = max(st->width_min, len);
184 } else
185 no_header = 1;
186
187 if (!st->width_min)
188 st->width_min = 1;
189
190 /* count width according to cells data */
191 if (scols_table_is_tree(tb)) {
192 /* Count width for tree */
193 rc = scols_walk_tree(tb, cl, walk_count_cell_width, (void *) buf);
194 if (rc)
195 goto done;
196 } else {
197 /* Count width for list */
198 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
199 while (scols_table_next_line(tb, &itr, &ln) == 0) {
200 rc = count_cell_width(tb, ln, cl, buf);
201 if (rc)
202 goto done;
203 }
204 }
205
206 if (scols_column_is_tree(cl) && has_groups(tb)) {
207 /* We don't fill buffer with groups tree ascii art during width
208 * calculation. The print function only enlarge grpset[] and we
209 * calculate final width from grpset_size.
210 */
211 size_t gprwidth = tb->grpset_size + 1;
212 st->width_treeart += gprwidth;
213 st->width_max += gprwidth;
214 }
215
216 /* this is default, may be later reduced */
217 cl->width = st->width_max;
218
219 /* enlarge to minimal width */
220 if (cl->width < st->width_min && !scols_column_is_strict_width(cl))
221 cl->width = st->width_min;
222
223 /* use absolute size for large columns */
224 else if (cl->width_hint >= 1 && cl->width < (size_t) cl->width_hint
225 && st->width_min < (size_t) cl->width_hint)
226
227 cl->width = (size_t) cl->width_hint;
228
229
230 /* Column without header and data, set minimal size to zero (default is 1) */
231 if (st->width_max == 0 && no_header && st->width_min == 1 && cl->width <= 1)
232 cl->width = st->width_min = 0;
233
234 done:
235 ON_DBG(COL, dbg_column(tb, cl));
236 return rc;
237 }
238
239 static int cmp_deviation(struct list_head *a, struct list_head *b,
240 void *data __attribute__((__unused__)))
241 {
242 struct libscols_column *ca = list_entry(a, struct libscols_column, cl_columns);
243 struct libscols_column *cb = list_entry(b, struct libscols_column, cl_columns);
244
245 double xa = ca->wstat.width_avg + (3*ca->wstat.width_deviation);
246 double xb = cb->wstat.width_avg + (3*cb->wstat.width_deviation);
247
248 return cmp_numbers(xa, xb);
249 }
250
251 static int cmp_seqnum(struct list_head *a, struct list_head *b,
252 void *data __attribute__((__unused__)))
253 {
254 struct libscols_column *ca = list_entry(a, struct libscols_column, cl_columns);
255 struct libscols_column *cb = list_entry(b, struct libscols_column, cl_columns);
256
257 return cmp_numbers(ca->seqnum, cb->seqnum);
258 }
259
260 static inline void sort_columns(struct libscols_table *tb,
261 int (*cmp)(struct list_head *, struct list_head *, void *))
262 {
263 list_sort(&tb->tb_columns, cmp, NULL);
264 }
265
266
267 /* 68%–95%–99% rule (aka empirical rule) defines relation ship between
268 * mean (avg) and and standard deviation.
269 *
270 * avg + (n * deviation)
271 *
272 * n=1 : covers 68% of data
273 * n=2 : covers 95% of data
274 * n=3 : covers 99.7% of data
275 *
276 */
277 static void reduce_to_68(struct libscols_column *cl, size_t wanted)
278 {
279 struct libscols_wstat *st = &cl->wstat;
280 size_t new;
281
282 if (st->width_deviation < 1.0)
283 return;
284
285 new = st->width_avg + st->width_deviation;
286 if (new < st->width_min)
287 new = st->width_min;
288
289 if (cl->width - new > wanted)
290 cl->width -= wanted;
291 else
292 cl->width = new;
293 }
294
295 static int reduce_column(struct libscols_table *tb,
296 struct libscols_column *cl,
297 size_t *width,
298 int stage,
299 int nth)
300 {
301 struct libscols_wstat *st = &cl->wstat;
302 size_t wanted, org_width, reduce = 1;
303 int is_trunc = 0;
304
305 if (tb->termwidth >= *width)
306 return 1;
307 /* ignore hidden columns */
308 if (scols_column_is_hidden(cl))
309 return 0;
310 /* never truncate if already minimal width */
311 if (cl->width == cl->wstat.width_min)
312 return 0;
313 /* nothing to truncate */
314 if (cl->width == 0)
315 return 0;
316 /* never truncate the tree */
317 if (scols_column_is_tree(cl) && *width <= cl->width_treeart)
318 return 0;
319
320 org_width = cl->width;
321 wanted = *width - tb->termwidth;
322
323 is_trunc = scols_column_is_trunc(cl)
324 || (scols_column_is_wrap(cl) && !scols_column_is_customwrap(cl));
325
326 switch (stage) {
327 case 0:
328 /* reduce 1st column if with trunc or extreme flag (the
329 * columns are sorted by deviation, so 1st is the worst) */
330 if (!is_trunc && !scols_column_is_noextremes(cl))
331 break;
332 if (nth != 0)
333 break;
334 reduce_to_68(cl, wanted);
335 break;
336
337 case 1:
338 /* reduce extreme columns with large width deviation */
339 if (st->width_deviation < st->width_avg / 2.0)
340 break;
341 /* fallthrough */
342 case 2:
343 /* reduce extreme columns */
344 if (!scols_column_is_noextremes(cl))
345 break;
346 reduce_to_68(cl, wanted);
347 break;
348
349 case 3:
350 /* reduce columns with trunc flag and relative whint and large width deviation */
351 if (st->width_deviation < st->width_avg / 2.0)
352 break;
353 /* fallthrough */
354 case 4:
355 /* reduce columns with trunc flag and relative whint */
356 if (!is_trunc)
357 break;
358 if (cl->width_hint <= 0 || cl->width_hint >= 1)
359 break;
360 if (cl->width < (size_t) (cl->width_hint * tb->termwidth))
361 break;
362 reduce_to_68(cl, wanted);
363 break;
364
365 case 5:
366 /* reduce all columns with trunc flag large width deviation */
367 if (st->width_deviation < st->width_avg / 2.2)
368 break;
369 /* fallthrough */
370 case 6:
371 /* reduce all columns with trunc flag */
372 if (!is_trunc && !scols_column_is_noextremes(cl))
373 break;
374 if (nth == 0)
375 /* columns are reduced in "bad first" way, be more
376 * agresive for the the worst column */
377 reduce = 3;
378 if (cl->width - reduce < st->width_min)
379 reduce = cl->width - st->width_min;
380 cl->width -= reduce;
381 break;
382 default:
383 return -1; /* no more stages */
384 }
385
386 /* hide zero width columns */
387 if (cl->width == 0)
388 cl->flags |= SCOLS_FL_HIDDEN;
389
390 if (cl->width != org_width)
391 DBG(COL, ul_debugobj(cl, " [%02zd] %s reduced %zu-->%zu",
392 cl->seqnum,
393 cl->header.data, org_width, cl->width));
394
395 *width -= org_width - cl->width;
396 return 0;
397 }
398
399 /*
400 * This is core of the scols_* voodoo...
401 */
402 int __scols_calculate(struct libscols_table *tb, struct ul_buffer *buf)
403 {
404 struct libscols_column *cl, *last_cl;
405 struct libscols_iter itr;
406 size_t width = 0, width_min = 0; /* output width */
407 int stage = 0, rc = 0;
408 int ignore_extremes = 0, group_ncolumns = 0;
409 size_t colsepsz;
410 int sorted = 0;
411
412
413 DBG(TAB, ul_debugobj(tb, "-----calculate-(termwidth=%zu)-----", tb->termwidth));
414 tb->is_dummy_print = 1;
415
416 colsepsz = scols_table_is_noencoding(tb) ?
417 mbs_width(colsep(tb)) :
418 mbs_safe_width(colsep(tb));
419
420 if (has_groups(tb))
421 group_ncolumns = 1;
422
423 /* set basic columns width
424 */
425 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
426 while (scols_table_next_column(tb, &itr, &cl) == 0) {
427 int is_last;
428
429 if (scols_column_is_hidden(cl))
430 continue;
431
432 /* we print groups chart only for the for the first tree column */
433 if (scols_column_is_tree(cl) && group_ncolumns == 1) {
434 cl->is_groups = 1;
435 group_ncolumns++;
436 }
437
438 rc = count_column_width(tb, cl, buf);
439 if (rc)
440 goto done;
441
442 is_last = is_last_column(cl);
443
444 width += cl->width + (is_last ? 0 : colsepsz); /* separator for non-last column */
445 width_min += cl->wstat.width_min + (is_last ? 0 : colsepsz);
446 }
447
448 if (!tb->is_term) {
449 DBG(TAB, ul_debugobj(tb, " non-terminal output"));
450 goto done;
451 }
452
453 /* be paranoid */
454 if (width_min > tb->termwidth && scols_table_is_maxout(tb)) {
455 DBG(TAB, ul_debugobj(tb, " min width larger than terminal! [width=%zu, term=%zu]", width_min, tb->termwidth));
456 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
457 while (width_min > tb->termwidth
458 && scols_table_next_column(tb, &itr, &cl) == 0) {
459
460 if (scols_column_is_hidden(cl))
461 continue;
462 width_min--;
463 cl->wstat.width_min--;
464 }
465 DBG(TAB, ul_debugobj(tb, " min width reduced to %zu", width_min));
466 }
467
468 /* calculate statistics */
469 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
470 while (scols_table_next_column(tb, &itr, &cl) == 0) {
471
472 count_column_deviation(tb, cl);
473
474 if (scols_column_is_noextremes(cl))
475 ignore_extremes++;
476 }
477
478 /* remember last column before we sort columns */
479 last_cl = list_entry(tb->tb_columns.prev, struct libscols_column, cl_columns);
480
481 /* reduce columns width */
482 while (width > tb->termwidth) {
483 size_t org_width = width;
484 int rc = 0, n = 0;
485
486 if (!sorted) {
487 DBG(TAB, ul_debugobj(tb, "sorting by deviation"));
488 sort_columns(tb, cmp_deviation);
489 ON_DBG(TAB, dbg_columns(tb));
490 sorted = 1;
491 }
492
493 DBG(TAB, ul_debugobj(tb, "#%d reduce stage (width=%zu, term=%zu)",
494 stage, width, tb->termwidth));
495
496 scols_reset_iter(&itr, SCOLS_ITER_BACKWARD);
497
498 while (width > tb->termwidth
499 && rc == 0
500 && scols_table_next_column(tb, &itr, &cl) == 0) {
501 rc = reduce_column(tb, cl, &width, stage, n++);
502 }
503
504 if (rc != 0)
505 break;
506 if (org_width == width)
507 stage++;
508 }
509
510 /* enlarge */
511 if (width < tb->termwidth) {
512 if (ignore_extremes) {
513 if (!sorted) {
514 sort_columns(tb, cmp_deviation);
515 sorted = 1;
516 }
517
518 scols_reset_iter(&itr, SCOLS_ITER_BACKWARD);
519 while (scols_table_next_column(tb, &itr, &cl) == 0) {
520 size_t add;
521
522 if (!scols_column_is_noextremes(cl) || scols_column_is_hidden(cl))
523 continue;
524 if (cl->wstat.width_min == 0 && cl->width == 0)
525 continue;
526
527 add = tb->termwidth - width;
528 if (add && cl->wstat.width_max &&
529 cl->width + add > cl->wstat.width_max)
530 add = cl->wstat.width_max - cl->width;
531 if (!add)
532 continue;
533 DBG(TAB, ul_debugobj(tb, " add +%zd (extreme %s)",
534 add, cl->header.data));
535 cl->width += add;
536 width += add;
537
538 if (width == tb->termwidth)
539 break;
540 }
541 }
542
543 if (width < tb->termwidth && scols_table_is_maxout(tb)) {
544 DBG(TAB, ul_debugobj(tb, " enlarge width (max-out)"));
545
546 /* try enlarging all columns */
547 while (width < tb->termwidth) {
548 scols_reset_iter(&itr, SCOLS_ITER_BACKWARD);
549 while (scols_table_next_column(tb, &itr, &cl) == 0) {
550 if (scols_column_is_hidden(cl))
551 continue;
552 DBG(TAB, ul_debugobj(tb, " enlarge (max-out %s)",
553 cl->header.data));
554 cl->width++;
555 width++;
556 if (width == tb->termwidth)
557 break;
558 }
559 }
560 } else if (width < tb->termwidth) {
561 /* enlarge the last column */
562 DBG(TAB, ul_debugobj(tb, " enlarge width (last column)"));
563
564 if (!scols_column_is_right(last_cl)) {
565 last_cl->width += tb->termwidth - width;
566 width = tb->termwidth;
567 }
568 }
569 }
570
571
572 if (sorted) {
573 sort_columns(tb, cmp_seqnum);
574 sorted = 0;
575 }
576
577 /* ignore last column(s) or force last column to be truncated if
578 * nowrap mode enabled */
579 if (tb->no_wrap && width > tb->termwidth) {
580 scols_reset_iter(&itr, SCOLS_ITER_BACKWARD);
581 while (scols_table_next_column(tb, &itr, &cl) == 0) {
582
583 if (scols_column_is_hidden(cl))
584 continue;
585 if (width <= tb->termwidth)
586 break;
587 if (width - cl->width < tb->termwidth) {
588 size_t r = width - tb->termwidth;
589
590 cl->flags |= SCOLS_FL_TRUNC;
591 cl->width -= r;
592 width -= r;
593 } else {
594 cl->flags |= SCOLS_FL_HIDDEN;
595 width -= cl->width + colsepsz;
596 }
597 }
598 }
599 done:
600 if (sorted)
601 sort_columns(tb, cmp_seqnum);
602
603 tb->is_dummy_print = 0;
604 DBG(TAB, ul_debugobj(tb, "-----final width: %zu (rc=%d)-----", width, rc));
605 ON_DBG(TAB, dbg_columns(tb));
606
607 return rc;
608 }