lcs.c

/*
 * License: GPLv2+
 * Author: Colomban Wendling <[email protected]>
 */

/*
 * FIXME: improve function names (e.g. strvstrv doesn't simply do strstr anymore)
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <glib.h>

#define MIN_ELLIPSISING 5
#define ELLIPSIS "…"

#define SETPTR(p, v) \
	do { \
		gpointer old_ptr = (p); \
		(p) = (v); \
		g_free(old_ptr); \
	} while(0)

/* like strstr() but on GStrv: searches for @p needle in @p haystack and returns
 * the pointer in @p haystack where @p needle starts, or NULL if not found.
 * Compares only @p needle_len elements from @p needle */
static gchar **strvstrv(gchar **haystack, gchar **needle, gsize needle_len)
{
	for (; haystack && *haystack; haystack++)
	{
		gsize i = 0;
		while (haystack[i] && i < needle_len &&
#ifdef G_OS_WIN32
			   g_ascii_strcasecmp(haystack[i], needle[i]) == 0
#else
			   strcmp(haystack[i], needle[i]) == 0
#endif
			   )
			i++;
		if (i == needle_len)
			return haystack;
	}

	return NULL;
}

static void strv_remove_range(gchar **strv, gsize start, gsize len)
{
	gsize strv_len = 0;

	/* compute the length and free the elements to remove */
	for (strv_len = start; strv[strv_len]; strv_len++)
	{
		if (strv_len < start + len)
			g_free(strv[strv_len]);
	}
	/* move the remainder, including the NULL sentinel */
	memmove(&strv[start], &strv[start + len], sizeof *strv * (strv_len - len + 1));
}

/* Strips common prefix and common longest substring from paths in @path_list.
 *
 * @param path_list A list of paths, usually absolute.
 * @param path_list_len the length of @path_list.
 *
 * It is implemented splitting the paths on separators, searching for common
 * elements, stripping them and rebuilding the altered path.
 *
 * @returns a GStrv of shortened paths.
 */
static gchar **shorten_path_list(gchar **path_list, const gsize path_list_len)
{
	gchar ***split_paths;
	gsize split_paths_0_len;

	/* split the paths on separators */
	split_paths = g_malloc(sizeof *split_paths * (path_list_len + 1));
	for (gsize i = 0; i < path_list_len; i++)
		split_paths[i] = g_strsplit_set(path_list[i],
										"/"
#ifdef G_OS_WIN32 /* on Windows we need to also include \ as a separator */
										"\\"
#endif
										, -1);
	split_paths[path_list_len] = NULL;

	split_paths_0_len = g_strv_length(split_paths[0]); 

	/* find the longest common prefix, not counting the basename, and strip it if it's longer
	 * than just the leading G_DIR_SEPARATOR or, for Windows paths, the drive letter. */
	if (split_paths_0_len > 1)
	{
		gsize longest_prefix = split_paths_0_len - 1;
		for (gsize i = 1; longest_prefix > 0 && split_paths[i]; i++)
		{
			gsize prefix = 0;

			while (prefix < longest_prefix && strcmp(split_paths[0][prefix], split_paths[i][prefix]) == 0)
				prefix++;
			longest_prefix = prefix;
		}
		if (longest_prefix > 1)
		{
			for (gsize i = 0; split_paths[i]; i++)
				strv_remove_range(split_paths[i], 0, longest_prefix);
			split_paths_0_len -= longest_prefix;
		}
	}

	/* find the longest common substring (not counting the basename), if any, and
	 * replace it with a placeholder if it's long enough to be worth it */
	if (split_paths_0_len > 1)
	{
		gchar **sub = split_paths[0];
		gchar **found = NULL;
		gsize found_len = 0;
		gsize found_str_len = 0;

		for (gsize sub_len = split_paths_0_len - 1; *sub; sub++, sub_len--)
		{
			for (gsize candidate_len = sub_len; candidate_len > 0; candidate_len--)
			{
				gchar **candidate = sub;

				for (gsize j = 1; candidate && split_paths[j]; j++)
				{
					if (! strvstrv(split_paths[j], candidate, candidate_len))
						candidate = NULL;
				}
				if (candidate)
				{
					gsize candidate_str_len = candidate_len - 1; /* account for the dir separators */
					for (gsize i = 0; i < candidate_len; i++)
						candidate_str_len += strlen(candidate[i]);
					if (candidate_str_len > found_str_len)
					{
						found_str_len = candidate_str_len;
						found_len = candidate_len;
						found = candidate;
					}
				}
			}
		}
		/* if we found a common substring long enough, strip it */
		if (found && found_str_len >= MIN_ELLIPSISING)
		{
			for (gsize i = path_list_len; i > 0; i--)
			{
				gchar **p = strvstrv(split_paths[i - 1], found, found_len);

				if (! p)
				{
					/* should never happen if the code is not buggy */
					g_warn_if_reached();
					continue;
				}

				SETPTR(p[0], g_strdup(ELLIPSIS));
				if (found_len > 1)
					strv_remove_range(p, 1, found_len - 1);
			}
			split_paths_0_len -= found_len;
		}
	}

	/* build the shortened list, and free the split one */
	gchar **short_paths = g_malloc((path_list_len + 1) * sizeof *short_paths);
	for (gsize i = 0; split_paths[i]; i++)
	{
		short_paths[i] = g_strjoinv(G_DIR_SEPARATOR_S, split_paths[i]);
		g_strfreev(split_paths[i]);
	}
	short_paths[path_list_len] = NULL;

	g_free(split_paths);

	return short_paths;
}


/*---------------------------------------------------------------------------*/

int main(int argc, char **argv)
{
	gchar **paths = shorten_path_list(&argv[1], (gsize) argc - 1);
	for (gchar **el = paths; *el; el++)
		fprintf(stderr, "path = %s\n", *el);
	g_strfreev(paths);
	
	return 0;
}