libsmartcols: add lines grouping support

For some use-case we need to describe M:N relation between output
lines. The nice examples are RAIDs or multi-path devices in lsblk
output.

    NAME                 MAJ:MIN RM   SIZE RO TYPE  MOUNTPOINT
    loop0                  7:0    0 955.7M  0 loop
┌┈▶ ├─test-thin-metadata 253:0    0     2M  0 dm
└┬▶ └─test-thin-data     253:1    0 953.7M  0 dm
 └┈┈test-thin-pool       253:2    0 953.7M  0 dm

In this example two line (test-thin-metadata and test-thin-data) are
parents for another line (test-thin-pool). The new API uses term "group"
for parental line -- the number of group members is unlimited and every
group has at least one child.

It's possible that group's child is member of another group:

       NAME                 MAJ:MIN RM   SIZE RO TYPE  MOUNTPOINT
       loop0                  7:0    0 955.7M  0 loop
   ┌┈▶ ├─test-thin-metadata 253:0    0     2M  0 dm
   └┬▶ └─test-thin-data     253:1    0 953.7M  0 dm
┌┈▶ └┈┈test-thin-pool       253:2    0 953.7M  0 dm
┆      └─test-thin          253:3    0 190.8M  0 dm
└┬▶    loop1                  7:1    0 190.8M  0 loop
 └┈┈┈┈┈test-thin-extsnap    253:4    0 190.8M  0 dm

For now multi-group relation is unsupported and one line can be member
of one group only. The library API and printing code is ready to
support this feature, but not sure if we really need it. All what is
necessary is to create array of groups in the line struct.

Note that grouping is independent on standard parent->child relations
between lines and grouping can connect arbitrary lines. The
restriction is only that group child cannot be child of another line
or child of another group. These cross reference are (and probably
will be) impossible.

The patch is relative large, but easy to review. Changes:

* add new UTF symbols
* add scols_symbols_set_group_* public API to modify new symbols
* add struct libscols_group, used only internally

* add "grpset" array to table struct -- the array is used to keep
position of the group in the output. Every active group uses three
items in the grpset. If there is more overlapping groups than bigger
grpset is allocated.

Signed-off-by: Karel Zak <kzak@redhat.com>

1 files changed, 587 insertions, 0 deletions

diff --git a/libsmartcols/src/grouping.c b/libsmartcols/src/grouping.c
new file mode 100644
index 000000000..63ed6c4b2
--- /dev/null
+++ b/libsmartcols/src/grouping.c
@@ -0,0 +1,587 @@
+/*
+ * Copyright (C) 2018 Karel Zak <kzak@redhat.com>
+ */
+#include "smartcolsP.h"
+
+/**
+ * SECTION: grouping
+ * @title: Grouping
+ * @short_description: lines grouing
+ *
+ * Lines groups manipulation API. The grouping API allows to create M:N
+ * relations between lines and on tree-like output it prints extra chart to
+ * visualize these relations. The group has unlimited number of members and
+ * group childs. See libsmartcols/sample/grouping* for more details.
+ */
+
+/* Private API */
+void scols_ref_group(struct libscols_group *gr)
+{
+	if (gr)
+		gr->refcount++;
+}
+
+void scols_group_remove_children(struct libscols_group *gr)
+{
+	if (!gr)
+		return;
+
+	while (!list_empty(&gr->gr_children)) {
+		struct libscols_line *ln = list_entry(gr->gr_children.next,
+						struct libscols_line, ln_children);
+
+		DBG(GROUP, ul_debugobj(gr, "remove child"));
+		list_del_init(&ln->ln_children);
+		scols_ref_group(ln->parent_group);
+		ln->parent_group = NULL;
+		scols_unref_line(ln);
+	}
+}
+
+void scols_group_remove_members(struct libscols_group *gr)
+{
+	if (!gr)
+		return;
+
+	while (!list_empty(&gr->gr_members)) {
+		struct libscols_line *ln = list_entry(gr->gr_members.next,
+						struct libscols_line, ln_groups);
+
+		DBG(GROUP, ul_debugobj(gr, "remove member [%p]", ln));
+		list_del_init(&ln->ln_groups);
+
+		scols_unref_group(ln->group);
+		ln->group->nmembers++;
+		ln->group = NULL;
+
+		scols_unref_line(ln);
+	}
+}
+
+/* note group has to be already without members to deallocate */
+void scols_unref_group(struct libscols_group *gr)
+{
+	if (gr && --gr->refcount <= 0) {
+		DBG(GROUP, ul_debugobj(gr, "dealloc"));
+		scols_group_remove_children(gr);
+		list_del(&gr->gr_groups);
+		free(gr);
+		return;
+	}
+}
+
+
+static void groups_fix_members_order(struct libscols_line *ln)
+{
+	struct libscols_iter itr;
+	struct libscols_line *child;
+
+	if (ln->group) {
+		list_add_tail(&ln->ln_groups, &ln->group->gr_members);
+		DBG(GROUP, ul_debugobj(ln->group, "fixing member line=%p [%zu/%zu]",
+					ln, ln->group->nmembers,
+					list_count_entries(&ln->group->gr_members)));
+	}
+
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_line_next_child(ln, &itr, &child) == 0)
+		groups_fix_members_order(child);
+
+	/*
+	 * We modify gr_members list, so is_last_group_member() does not have
+	 * to provide reliable answer, we need to verify by list_count_entries().
+	 */
+	if (ln->group
+	    && is_last_group_member(ln)
+	    && ln->group->nmembers == list_count_entries(&ln->group->gr_members)) {
+
+		DBG(GROUP, ul_debugobj(ln->group, "fixing childs"));
+		scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+		while (scols_line_next_group_child(ln, &itr, &child) == 0)
+			groups_fix_members_order(child);
+	}
+}
+
+void scols_groups_fix_members_order(struct libscols_table *tb)
+{
+	struct libscols_iter itr;
+	struct libscols_line *ln;
+	struct libscols_group *gr;
+
+	/* remove all from groups lists */
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_table_next_group(tb, &itr, &gr) == 0) {
+		while (!list_empty(&gr->gr_members)) {
+			struct libscols_line *ln = list_entry(gr->gr_members.next,
+						struct libscols_line, ln_groups);
+			list_del_init(&ln->ln_groups);
+		}
+	}
+
+	/* add again to the groups list in order we walk in tree */
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_table_next_line(tb, &itr, &ln) == 0) {
+		if (ln->parent || ln->parent_group)
+			continue;
+		groups_fix_members_order(ln);
+	}
+
+	/* If group child is memeber of another group *
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_table_next_group(tb, &itr, &gr) == 0) {
+		struct libscols_iter xitr;
+		struct libscols_line *child;
+
+		scols_reset_iter(&xitr, SCOLS_ITER_FORWARD);
+		while (scols_line_next_group_child(ln, &xitr, &child) == 0)
+			groups_fix_members_order(child);
+	}
+	*/
+}
+
+static inline const char *group_state_to_string(int state)
+{
+	static const char *grpstates[] = {
+		[SCOLS_GSTATE_NONE]		= "none",
+		[SCOLS_GSTATE_FIRST_MEMBER]	= "1st-member",
+		[SCOLS_GSTATE_MIDDLE_MEMBER]	= "middle-member",
+		[SCOLS_GSTATE_LAST_MEMBER]	= "last-member",
+		[SCOLS_GSTATE_MIDDLE_CHILD]	= "middle-child",
+		[SCOLS_GSTATE_LAST_CHILD]	= "last-child",
+		[SCOLS_GSTATE_CONT_MEMBERS]	= "continue-members",
+		[SCOLS_GSTATE_CONT_CHILDREN]	= "continue-children"
+	};
+
+	assert(state >= 0);
+	assert((size_t) state < ARRAY_SIZE(grpstates));
+
+	return grpstates[state];
+};
+
+static void grpset_debug(struct libscols_table *tb, struct libscols_line *ln)
+{
+	size_t i;
+
+	for (i = 0; i < tb->grpset_size; i++) {
+		if (tb->grpset[i]) {
+			struct libscols_group *gr = tb->grpset[i];
+
+			if (ln)
+				DBG(LINE, ul_debugobj(ln, "grpset[%zu]: %p %s", i,
+					gr, group_state_to_string(gr->state)));
+			else
+				DBG(LINE, ul_debug("grpset[%zu]: %p %s", i,
+					gr, group_state_to_string(gr->state)));
+		} else if (ln) {
+			DBG(LINE, ul_debugobj(ln, "grpset[%zu]: free", i));
+		} else
+			DBG(LINE, ul_debug("grpset[%zu]: free", i));
+	}
+}
+static int group_state_for_line(struct libscols_group *gr, struct libscols_line *ln)
+{
+	if (gr->state == SCOLS_GSTATE_NONE &&
+	    (ln->group != gr || !is_first_group_member(ln)))
+		/*
+		 * NONE is possible to translate to FIRST_MEMBER only, and only if
+		 * line group matches with the current group.
+		 */
+		return SCOLS_GSTATE_NONE;
+
+	if (ln->group != gr && ln->parent_group != gr) {
+		/* Not our line, continue */
+		if (gr->state == SCOLS_GSTATE_FIRST_MEMBER ||
+		    gr->state == SCOLS_GSTATE_MIDDLE_MEMBER ||
+		    gr->state == SCOLS_GSTATE_CONT_MEMBERS)
+			return SCOLS_GSTATE_CONT_MEMBERS;
+
+		if (gr->state == SCOLS_GSTATE_LAST_MEMBER ||
+		    gr->state == SCOLS_GSTATE_MIDDLE_CHILD ||
+		    gr->state == SCOLS_GSTATE_CONT_CHILDREN)
+			return SCOLS_GSTATE_CONT_CHILDREN;
+
+	} else if (ln->group == gr && is_first_group_member(ln)) {
+		return SCOLS_GSTATE_FIRST_MEMBER;
+
+	} else if (ln->group == gr && is_last_group_member(ln)) {
+		return SCOLS_GSTATE_LAST_MEMBER;
+
+	} else if (ln->group == gr && is_group_member(ln)) {
+		return SCOLS_GSTATE_MIDDLE_MEMBER;
+
+	} else if (ln->parent_group == gr && is_last_group_child(ln)) {
+		return SCOLS_GSTATE_LAST_CHILD;
+
+	} else if (ln->parent_group == gr && is_group_child(ln)) {
+		return SCOLS_GSTATE_MIDDLE_CHILD;
+	}
+
+	return SCOLS_GSTATE_NONE;
+}
+
+/* For now we assume that each active group is just 3 columns width. Later we can make it dynamic... 
+ */
+static void grpset_apply_group_state(struct libscols_group **xx, int state, struct libscols_group *gr)
+{
+	DBG(GROUP, ul_debugobj(gr, "   appling state to grpset"));
+
+	/* gr->state holds the old state, @state is the new state
+	 */
+	if (state == SCOLS_GSTATE_NONE)
+		xx[0] = xx[1] = xx[2] = NULL;
+	else
+		xx[0] = xx[1] = xx[2] = gr;
+	gr->state = state;
+}
+
+static struct libscols_group **grpset_locate_freespace(struct libscols_table *tb, size_t wanted, int prepend)
+{
+	size_t i, avail = 0;
+	struct libscols_group **tmp, **first = NULL;
+
+	if (!tb->grpset_size)
+		prepend = 0;
+
+	if (prepend) {
+		for (i = tb->grpset_size - 1; ; i--) {
+			if (tb->grpset[i] == NULL) {
+				first = &tb->grpset[i];
+				avail++;
+			} else
+				avail = 0;
+			if (avail == wanted)
+				goto done;
+			if (i == 0)
+				break;
+		}
+	} else {
+		for (i = 0; i < tb->grpset_size; i++) {
+			if (tb->grpset[i] == NULL) {
+				if (avail == 0)
+					first = &tb->grpset[i];
+				avail++;
+			} else
+				avail = 0;
+			if (avail == wanted)
+				goto done;
+		}
+	}
+
+	DBG(TAB, ul_debugobj(tb, "   realocate grpset [sz: old=%zu, new=%zu]",
+				tb->grpset_size, tb->grpset_size + wanted));
+
+	tmp = realloc(tb->grpset, (tb->grpset_size + wanted) * sizeof(struct libscols_group *));
+	if (!tmp)
+		return NULL;
+
+	tb->grpset = tmp;
+
+	if (prepend) {
+		DBG(TAB, ul_debugobj(tb, "   prepending free space"));
+		char *dest = (char *) tb->grpset;
+
+		memmove(	dest + (wanted * sizeof(struct libscols_group *)),
+				tb->grpset,
+				tb->grpset_size * sizeof(struct libscols_group *));
+		first = tb->grpset;
+	} else {
+		first = tb->grpset + tb->grpset_size;
+	}
+
+	memset(first, 0, wanted * sizeof(struct libscols_group *));
+	tb->grpset_size += wanted;
+
+	grpset_debug(tb, NULL);
+done:
+	return first;
+}
+
+static struct libscols_group **grpset_locate_group(struct libscols_table *tb, struct libscols_group *gr)
+{
+	size_t i;
+
+	for (i = 0; i < tb->grpset_size; i++) {
+		if (gr == tb->grpset[i])
+			return &tb->grpset[i];
+	}
+
+	return NULL;
+}
+
+
+
+#define SCOLS_GRPSET_MINSZ	3
+
+static int grpset_update(struct libscols_table *tb, struct libscols_line *ln, struct libscols_group *gr)
+{
+	struct libscols_group **xx;
+	int state;
+
+	DBG(LINE, ul_debugobj(ln, "   group [%p] grpset update", gr));
+
+	/* new state, note that gr->state still holds the original state */
+	state = group_state_for_line(gr, ln);
+	DBG(LINE, ul_debugobj(ln, "    state old='%s', new='%s'",
+			group_state_to_string(gr->state),
+			group_state_to_string(state)));
+
+	if (state == SCOLS_GSTATE_FIRST_MEMBER && gr->state != SCOLS_GSTATE_NONE) {
+		DBG(LINE, ul_debugobj(ln, "wrong group initialization"));
+		abort();
+	}
+	if (state != SCOLS_GSTATE_NONE && gr->state == SCOLS_GSTATE_LAST_CHILD) {
+		DBG(LINE, ul_debugobj(ln, "wrong group termination"));
+		abort();
+	}
+	if (gr->state == SCOLS_GSTATE_LAST_MEMBER &&
+	    !(state == SCOLS_GSTATE_LAST_CHILD ||
+	      state == SCOLS_GSTATE_CONT_CHILDREN ||
+	      state == SCOLS_GSTATE_MIDDLE_CHILD ||
+	      state == SCOLS_GSTATE_NONE)) {
+		DBG(LINE, ul_debugobj(ln, "wrong group member->child order"));
+		abort();
+	}
+
+	/* should not happen; probably wrong line... */
+	if (gr->state == SCOLS_GSTATE_NONE && state == SCOLS_GSTATE_NONE)
+		return 0;
+
+	/* locate place in grpset where we draw the group */
+	if (!tb->grpset || gr->state == SCOLS_GSTATE_NONE)
+		xx = grpset_locate_freespace(tb, SCOLS_GRPSET_MINSZ, 1);
+	else
+		xx = grpset_locate_group(tb, gr);
+	if (!xx) {
+		DBG(LINE, ul_debugobj(ln, "failed to locate group or reallocate grpset"));
+		return -ENOMEM;
+	}
+
+	grpset_apply_group_state(xx, state, gr);
+	ON_DBG(LINE, grpset_debug(tb, ln));
+	return 0;
+}
+
+static int grpset_update_active_groups(struct libscols_table *tb, struct libscols_line *ln)
+{
+	int rc = 0;
+	size_t i;
+	struct libscols_group *last = NULL;
+
+	DBG(LINE, ul_debugobj(ln, "   update for active groups"));
+
+	for (i = 0; i < tb->grpset_size; i++) {
+		struct libscols_group *gr = tb->grpset[i];
+
+		if (!gr || last == gr)
+			continue;
+		last = gr;
+		rc = grpset_update(tb, ln, gr);
+		if (rc)
+			break;
+	}
+
+	DBG(LINE, ul_debugobj(ln, "   <- active groups updated [rc=%d]", rc));
+	return rc;
+}
+
+int scols_groups_update_grpset(struct libscols_table *tb, struct libscols_line *ln)
+{
+	int rc = 0;
+
+	DBG(LINE, ul_debugobj(ln, "  grpset update [line: group=%p, parent_group=%p",
+				ln->group, ln->parent_group));
+
+	rc = grpset_update_active_groups(tb, ln);
+	if (!rc && ln->group && ln->group->state == SCOLS_GSTATE_NONE) {
+		DBG(LINE, ul_debugobj(ln, " introduce a new group"));
+		rc = grpset_update(tb, ln, ln->group);
+	}
+	return rc;
+}
+
+static int groups_calculate_grpset(struct libscols_table *tb, struct libscols_line *ln)
+{
+	struct libscols_iter itr;
+	struct libscols_line *child;
+	int rc = 0;
+
+	DBG(LINE, ul_debugobj(ln, " grpset calculate"));
+
+	/* current line */
+	rc = scols_groups_update_grpset(tb, ln);
+	if (rc)
+		goto done;
+
+	/* line's children */
+	if (has_children(ln)) {
+		scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+		while (scols_line_next_child(ln, &itr, &child) == 0) {
+			rc = groups_calculate_grpset(tb, child);
+			if (rc)
+				goto done;
+		}
+	}
+
+	/* group's children */
+	if (is_last_group_member(ln) && has_group_children(ln)) {
+		scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+		while (scols_line_next_group_child(ln, &itr, &child) == 0) {
+			rc = groups_calculate_grpset(tb, child);
+			if (rc)
+				goto done;
+		}
+	}
+done:
+	return rc;
+}
+
+
+int scols_groups_calculate_grpset(struct libscols_table *tb)
+{
+	struct libscols_iter itr;
+	struct libscols_line *ln;
+	int rc = 0;
+
+	DBG(TAB, ul_debugobj(tb, "grpset calculate [top-level]"));
+
+	scols_groups_reset_state(tb);
+
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_table_next_line(tb, &itr, &ln) == 0) {
+		if (ln->parent || ln->parent_group)
+			continue;
+		rc = groups_calculate_grpset(tb, ln);
+		if (rc)
+			break;
+	}
+
+	scols_groups_reset_state(tb);
+	return rc;
+}
+
+void scols_groups_reset_state(struct libscols_table *tb)
+{
+	struct libscols_iter itr;
+	struct libscols_group *gr;
+
+	DBG(TAB, ul_debugobj(tb, "reset groups states"));
+
+	scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+	while (scols_table_next_group(tb, &itr, &gr) == 0)
+		gr->state = SCOLS_GSTATE_NONE;
+
+	if (tb->grpset)
+		memset(tb->grpset, 0, tb->grpset_size);
+}
+
+static void add_member(struct libscols_group *gr, struct libscols_line *ln)
+{
+	DBG(GROUP, ul_debugobj(gr, "add member"));
+	ln->group = gr;
+	gr->nmembers++;
+	scols_ref_group(gr);
+
+	list_add_tail(&ln->ln_groups, &gr->gr_members);
+	scols_ref_line(ln);
+}
+
+/**
+ * scols_table_group_lines:
+ * @tb: a pointer to a struct libscols_table instance
+ * @ln: new group member
+ * @member: group member
+ * @id: group identifier (unused, not implemented yet), use zero.
+ *
+ * This function add line @ln to group of lines represented by @member.  If the
+ * group is not yet defined (@member is not member of any group) than a new one
+ * is allocated.
+ *
+ * The @ln maybe a NULL -- in this case only a new group is allocated if not
+ * defined yet.
+ *
+ * Note that the same line cannot be member of more groups (not implemented
+ * yet). The child of any group can be member of another group.
+ *
+ * The @id is not used for now, use 0. The plan is to use it to support
+ * multi-group membership in future.
+ *
+ * Returns: 0, a negative value in case of an error.
+ *
+ * Since: 2.34
+ */
+int scols_table_group_lines(	struct libscols_table *tb,
+				struct libscols_line *ln,
+				struct libscols_line *member,
+				__attribute__((__unused__)) int id)
+{
+	struct libscols_group *gr = NULL;
+
+	if (!tb || (!ln && !member))
+		return -EINVAL;
+	if (ln && member)  {
+		if (ln->group && !member->group)
+			return -EINVAL;
+		if (ln->group && member->group && ln->group != member->group)
+			return -EINVAL;
+	}
+
+	gr = member->group;
+
+	/* create a new group */
+	if (!gr) {
+		gr = calloc(1, sizeof(*gr));
+		if (!gr)
+			return -ENOMEM;
+		DBG(GROUP, ul_debugobj(gr, "alloc"));
+		gr->refcount = 1;
+		INIT_LIST_HEAD(&gr->gr_members);
+		INIT_LIST_HEAD(&gr->gr_children);
+		INIT_LIST_HEAD(&gr->gr_groups);
+
+		/* add group to the table */
+		list_add_tail(&gr->gr_groups, &tb->tb_groups);
+
+		/* add the first member */
+		add_member(gr, member);
+	}
+
+	/* add to group */
+	if (ln && !ln->group)
+		add_member(gr, ln);
+
+	return 0;
+}
+
+/**
+ * scols_line_link_groups:
+ * @ln: line instance
+ * @member: group member
+ * @id: group identifier (unused, not implemented yet))
+ *
+ * Define @ln as child of group represented by group @member. The line @ln
+ * cannot be child of any other line. It's possible to create group->child or
+ * parent->child relationship, but no both for the same line (child).
+ *
+ * The @id is not used for now, use 0. The plan is to use it to support
+ * multi-group membership in future.
+ *
+ * Returns: 0, a negative value in case of an error.
+ *
+ * Since: 2.34
+ */
+int scols_line_link_group(struct libscols_line *ln, struct libscols_line *member,
+		 __attribute__((__unused__)) int id)
+{
+	if (!ln || !member || !member->group || ln->parent)
+		return -EINVAL;
+
+	DBG(GROUP, ul_debugobj(member->group, "add child"));
+
+	list_add_tail(&ln->ln_children, &member->group->gr_children);
+	scols_ref_line(ln);
+
+	ln->parent_group = member->group;
+	scols_ref_group(member->group);
+
+	return 0;
+}