[PATCH 2/7] Add column layout

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

This mainly add display_columns() that will display a table of items,
filling columns before rows.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 .gitignore        |    1 +
 Makefile          |    3 +
 column.c          |  177 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 column.h          |   20 ++++++
 t/t9002-column.sh |  108 ++++++++++++++++++++++++++++++++
 test-column.c     |   59 ++++++++++++++++++
 6 files changed, 368 insertions(+), 0 deletions(-)
 create mode 100644 column.c
 create mode 100644 column.h
 create mode 100755 t/t9002-column.sh
 create mode 100644 test-column.c

diff --git a/.gitignore b/.gitignore
index 3dd6ef7..a1a1202 100644
--- a/.gitignore
+++ b/.gitignore
@@ -162,6 +162,7 @@
 /gitweb/gitweb.cgi
 /gitweb/static/gitweb.min.*
 /test-chmtime
+/test-column
 /test-ctype
 /test-date
 /test-delta
diff --git a/Makefile b/Makefile
index 775ee83..6d74956 100644
--- a/Makefile
+++ b/Makefile
@@ -417,6 +417,7 @@ PROGRAM_OBJS += http-backend.o
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
 TEST_PROGRAMS_NEED_X += test-chmtime
+TEST_PROGRAMS_NEED_X += test-column
 TEST_PROGRAMS_NEED_X += test-ctype
 TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
@@ -498,6 +499,7 @@ LIB_H += builtin.h
 LIB_H += cache.h
 LIB_H += cache-tree.h
 LIB_H += color.h
+LIB_H += column.h
 LIB_H += commit.h
 LIB_H += compat/bswap.h
 LIB_H += compat/cygwin.h
@@ -575,6 +577,7 @@ LIB_OBJS += branch.o
 LIB_OBJS += bundle.o
 LIB_OBJS += cache-tree.o
 LIB_OBJS += color.o
+LIB_OBJS += column.o
 LIB_OBJS += combine-diff.o
 LIB_OBJS += commit.o
 LIB_OBJS += config.o
diff --git a/column.c b/column.c
new file mode 100644
index 0000000..4b92fa5
--- /dev/null
+++ b/column.c
@@ -0,0 +1,177 @@
+#include "cache.h"
+#include "column.h"
+#include "parse-options.h"
+
+static int item_length(const struct column_layout *c, const char *s)
+{
+	int a_len = 0;
+
+	if (!(c->mode & COL_ANSI))
+		return strlen(s);
+
+	while ((s = strstr(s, "\033[")) != NULL) {
+		int len = strspn(s+2, "0123456789;");
+		s += len+3; /* \033[<len><func char> */
+		a_len += len+3;
+	}
+	return a_len;
+}
+
+static void layout(const struct column_layout *c,
+		   int total_width, int padding,
+		   int *width,
+		   int *rows, int *cols)
+{
+	int i;
+
+	*width = 0;
+	/* Find maximum column width */
+	for (i = 0; i < c->items.nr; i++) {
+		const char *s = c->items.items[i].string;
+		int len = item_length(c, s);
+		if (*width < len)
+			*width = len;
+	}
+	*width += padding;
+
+	*cols = total_width / *width;
+	if (*cols == 0)
+		*cols = 1;
+	/* items.nr <= rows*cols -> rows >= items.nr/cols */
+	*rows = c->items.nr / *cols;
+	if (c->items.nr > *rows * *cols)
+		(*rows)++;
+}
+
+static int squeeze_columns(const struct column_layout *c,
+			   int *width, int padding,
+			   int rows, int cols)
+{
+	int x, y, i, len, item_len, spare = 0;
+	const char *s;
+
+	for (x = 0; x < cols; x++) {
+		for (y = len = 0; y < rows; y++) {
+			i = x * rows + y;
+			if (i >= c->items.nr)
+				break;
+			s = c->items.items[i].string;
+			item_len = item_length(c, s);
+			if (len < item_len)
+				len = item_len;
+		}
+		len += padding;
+		if (len < width[x]) {
+			spare += width[x] - len;
+			width[x] = len;
+		}
+	}
+	return spare;
+}
+
+static void relayout(const struct column_layout *c,
+		     int padding, int spare,
+		     int *initial_width, int **width,
+		     int *rows, int *cols)
+{
+	int new_rows, new_cols, new_initial_width;
+	int i, *new_width, new_spare, total_width;
+
+	/*
+	 * Assume all columns have same width, we would need
+	 * initial_width*cols. But then after squeezing, we have
+	 * "spare" more chars. Assume a new total_width with
+	 * additional chars, then re-squeeze to see if it fits
+	 * c->width.
+	 */
+	total_width = (*initial_width)*(*cols) + spare;
+	layout(c, total_width, padding,
+	       &new_initial_width, &new_rows, &new_cols);
+	new_width = xmalloc(sizeof(*new_width) * new_cols);
+	for (i = 0; i < new_cols; i++)
+		new_width[i] = new_initial_width;
+	new_spare = squeeze_columns(c, new_width, padding, new_rows, new_cols);
+
+	/* Does it fit? */
+	if (total_width - new_spare < c->width) {
+		free(*width);
+		*width = new_width;
+		*initial_width = new_initial_width;
+		*rows = new_rows;
+		*cols = new_cols;
+	}
+}
+
+static void display_columns_first(const struct column_layout *c,
+				  int padding, const char *indent)
+{
+	int x, y, i, cols, rows, initial_width, *width;
+	char *empty_cell;
+
+	layout(c, c->width, padding, &initial_width, &rows, &cols);
+	width = xmalloc(sizeof(*width) * cols);
+	for (i = 0; i < cols; i++)
+		width[i] = initial_width;
+
+	if (c->mode & COL_DENSE) {
+		int spare = squeeze_columns(c, width, padding, rows, cols);
+		/* is it worth relayout? */
+		if (spare >= initial_width/2)
+			relayout(c, padding, spare,
+				 &initial_width, &width, &rows, &cols);
+	}
+
+	empty_cell = xmalloc(initial_width + 1);
+	memset(empty_cell, ' ', initial_width);
+	empty_cell[initial_width] = '\0';
+	for (y = 0; y < rows; y++) {
+		for (x = 0; x < cols; x++) {
+			const char *s;
+			int len;
+
+			i = x * rows + y;
+			if (i >= c->items.nr)
+				break;
+			s = c->items.items[i].string;
+			len = item_length(c, s);
+			if (width[x] < initial_width)
+				len += initial_width - width[x];
+
+			printf("%s%s%s",
+			       x == 0 ? indent : "",
+			       c->items.items[i].string,
+			       /* If the next column at same row is
+				  out of range, end the line. Else pad
+				  some space.  */
+			       i + rows >= c->items.nr ? "\n" : empty_cell + len);
+		}
+	}
+}
+
+static void display_plain(const struct column_layout *c, const char *indent)
+{
+	int i;
+
+	for (i = 0; i < c->items.nr; i++)
+		printf("%s%s\n", indent, c->items.items[i].string);
+}
+
+void display_columns(const struct column_layout *c, int padding, const char *indent)
+{
+	int mode = c->mode & COL_MODE;
+	if (!indent)
+		indent = "";
+	if (c->width <= 1)
+		mode = COL_PLAIN;
+	switch (mode) {
+	case COL_PLAIN:
+		display_plain(c, indent);
+		break;
+
+	case COL_COLUMN_FIRST:
+		display_columns_first(c, padding, indent);
+		break;
+	default:
+		die("BUG: invalid mode %d", c->mode & COL_MODE);
+	}
+}
diff --git a/column.h b/column.h
new file mode 100644
index 0000000..34435b0
--- /dev/null
+++ b/column.h
@@ -0,0 +1,20 @@
+#ifndef COLUMN_H
+#define COLUMN_H
+
+#include "string-list.h"
+
+#define COL_MODE          0x000F
+#define COL_PLAIN         0 /* Single column */
+#define COL_COLUMN_FIRST  1 /* Fill columns before rows */
+#define COL_ANSI          (1 << 4) /* Remove ANSI from string length */
+#define COL_DENSE         (1 << 5) /* "Ragged-right" mode, relayout if enough space */
+
+struct column_layout {
+	int mode;
+	int width;
+	struct string_list items;
+};
+
+extern void display_columns(const struct column_layout *c, int padding, const char *indent);
+
+#endif
diff --git a/t/t9002-column.sh b/t/t9002-column.sh
new file mode 100755
index 0000000..1d030b0
--- /dev/null
+++ b/t/t9002-column.sh
@@ -0,0 +1,108 @@
+#!/bin/sh
+
+test_description='git column'
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	cat >lista <<\EOF
+one
+two
+three
+four
+five
+six
+seven
+eight
+nine
+ten
+eleven
+EOF
+'
+
+test_expect_success '80 columns' '
+	cat >expected <<\EOF &&
+one    two    three  four   five   six    seven  eight  nine   ten    eleven
+EOF
+	COLUMNS=80 test-column < lista > actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'COLUMNS = 1' '
+	cat >expected <<\EOF &&
+one
+two
+three
+four
+five
+six
+seven
+eight
+nine
+ten
+eleven
+EOF
+	COLUMNS=1 test-column < lista > actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'width = 1' '
+	test-column --width=1 < lista > actual &&
+	test_cmp expected actual
+'
+
+COLUMNS=20
+export COLUMNS
+
+test_expect_success '20 columns' '
+	cat >expected <<\EOF &&
+one    seven
+two    eight
+three  nine
+four   ten
+five   eleven
+six
+EOF
+	test-column < lista > actual &&
+	test_cmp expected actual
+'
+
+test_expect_success '20 columns, densed' '
+	cat >expected <<\EOF &&
+one   seven
+two   eight
+three nine
+four  ten
+five  eleven
+six
+EOF
+	test-column --mode=column,dense < lista > actual &&
+	test_cmp expected actual
+'
+
+test_expect_success '20 columns, padding 2' '
+	cat >expected <<\EOF &&
+one     seven
+two     eight
+three   nine
+four    ten
+five    eleven
+six
+EOF
+	test-column --padding 2 < lista > actual &&
+	test_cmp expected actual
+'
+
+test_expect_success '20 columns, left indented' '
+	cat >expected <<\EOF &&
+  one    seven
+  two    eight
+  three  nine
+  four   ten
+  five   eleven
+  six
+EOF
+	test-column --left=2 < lista > actual &&
+	test_cmp expected actual
+'
+
+test_done
diff --git a/test-column.c b/test-column.c
new file mode 100644
index 0000000..4f56cd8
--- /dev/null
+++ b/test-column.c
@@ -0,0 +1,59 @@
+#include "cache.h"
+#include "strbuf.h"
+#include "parse-options.h"
+#include "column.h"
+
+static const char * const builtin_column_usage[] = {
+	"git column [--mode=<mode>] [--width=<width>] [--left-space=<N>] [--right-space=<N>]",
+	NULL
+};
+
+int main(int argc, const char **argv)
+{
+	struct column_layout c;
+	const char *mode = NULL;
+	struct strbuf sb = STRBUF_INIT;
+	int left_space = 0, right_space = 0, padding = 1;
+	int term_width = term_columns();
+	struct option options[] = {
+		OPT_INTEGER(0, "width", &term_width, "Maximum width"),
+		OPT_INTEGER(0, "left", &left_space, "Padding space on left border"),
+		OPT_INTEGER(0, "right", &right_space, "Padding space on right border"),
+		OPT_INTEGER(0, "padding", &padding, "Padding space between columns"),
+		OPT_STRING(0, "mode", &mode, "mode", "Which layout mode to use"),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, "", options, builtin_column_usage, 0);
+
+	memset(&c, 0, sizeof(c));
+	c.width = term_width - right_space - left_space;
+	c.items.strdup_strings = 1;
+
+	while (mode && *mode) {
+		int len = strcspn(mode, ",");
+		if (len == 6 && !strncmp(mode, "column", len))
+			c.mode |= COL_COLUMN_FIRST;
+		else if (len == 5 && !strncmp(mode, "dense", len))
+			c.mode |= COL_DENSE;
+		else if (len == 4 && !strncmp(mode, "ansi", len))
+			c.mode |= COL_ANSI;
+		else
+			die("Unknown mode %s", mode);
+		mode += len;
+		while (*mode == ',')
+			mode++;
+	}
+	if (!c.mode)
+		c.mode = COL_COLUMN_FIRST;
+	if ((c.mode & COL_MODE) == 0)
+		die("Invalid mode '%s'", mode);
+
+	while (!strbuf_getline(&sb, stdin, '\n'))
+		string_list_append(&c.items, sb.buf);
+
+	strbuf_setlen(&sb, left_space);
+	memset(sb.buf, ' ', left_space);
+	display_columns(&c, padding, sb.buf);
+	return 0;
+}
-- 
1.7.2.2