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

#define MAX(a,b) (((a) > (b)) ? (a) : (b))

typedef struct { 
	const char *name; 
	int idx; 
} node_t; 

node_t *nodes;
int n_nodes;

typedef struct { 
	const char *from; 
	const char *to; 
} edge_t;

edge_t *edges;
int n_edges;

int 
nodecmp (const void *n1, const void* n2)
{
	const node_t *d1 = n1;
	const node_t *d2 = n2;

	return strcmp (d1->name, d2->name);
}

int 
find_index (const char *name)
{
	node_t *res;
	node_t key;
	
	key.name = name;
	res = bsearch (&key, nodes, n_nodes, sizeof (node_t), nodecmp);

	if (res)
		return res->idx;

	return -1;
}

char **
allocate_matrix (int rows, int cols)
{
	char **matrix;
	int i;

	matrix = malloc (rows * sizeof (char *));
	for (i = 0; i < rows; i++)
		matrix[i] = calloc (cols, 1);

	return matrix;
}

void
transitive_closure (char **adj, char **path)
{
	int i, j, k;

	for (i = 0; i < n_nodes; i++) 
  		for (j = 0; j < n_nodes; j++)
      			path[i][j] = adj[i][j];

	for (i = 0; i < n_nodes; i++)
		path[i][i] = 1;

    	for (k = 0; k < n_nodes; k++)
		for (i = 0; i < n_nodes; i++)
			for (j = 0; j < n_nodes; j++)
   				path[i][j] = path[i][j] || (path[i][k] && path[k][j]);
}

void
strong_components (char **path, int *comp)
{
	int i, j;

	for (i = 0; i < n_nodes; i++) 
		comp[i] = i;

	for (i = 0; i < n_nodes; i++) 
		for (j = i; j < n_nodes; j++)
			if (path[i][j] && path[j][i] && comp[j] == j)
				comp[j] = i;
}

void 
dump_components (int *comp)
{
	int i, j, started;
	
	for (i = 0; i < n_nodes; i++)
		if (comp[i] == i) {
			started = 0;
			for (j = i + 1; j < n_nodes; j++) 
				if (comp[j] == i) {
					if (!started) {
						started = 1;
						printf ("%s", nodes[i].name);
					}	
					printf (" <-> %s", nodes[j].name);
				}
			if (started)
				printf ("\n");
		}
}

int
find_roots (char **path, int *comp, int target, int **roots)
{
	int i, j;
	int n_roots;
	
	n_roots = 0;
	*roots = NULL;

	for (i = 0; i < n_nodes; i++) {
		if (path[i][target]) {
			for (j = 0; j < n_nodes; j++) {
				if (path[j][i] && comp[i] != comp[j])
					break;
			}
			if (j == n_nodes) {
				n_roots++;
				*roots = realloc (*roots, n_roots * sizeof (int));
				(*roots)[n_roots - 1] = i; 
				/*printf ("%s --> %s\n", nodes[i].name, name);*/
			}
		}
	}

	return n_roots;
}

int *
find_paths (char **path, int *comp, int target, int *roots, int n_roots)
{
	int i, j, k;
	int *sub;

	sub = malloc (sizeof (int) * n_nodes);
	for (i = 0; i < n_nodes; i++) {
		sub[i] = 0;
		for (k = 0; k < n_roots; k++) {
			if (i == target || i == roots[k] ||
		 	    (path[roots[k]][i] && path[i][target])) {
				sub[i] = 1;
				break;
			}
		}
	}

	return sub;
}

void
print_subgraph (char **adj, int *sub, int target, int *roots, int n_roots)
{
	int i, j, k;
	
	printf ("digraph packages {\n"
	        "node [color=lightblue2, style=filled];\n"
	        "\"%s\" [color=green];\n", nodes[target].name);
	for (k = 0; k < n_roots; k++)
		printf ("\"%s\" [color=red];\n", nodes[roots[k]].name);

	for (i = 0; i < n_nodes; i++) {
		if (sub[i]) {
			for (j = 0; j < n_nodes; j++) {
				if (sub[j] && adj[i][j]) 
					printf ("\"%s\" -> \"%s\";\n", nodes[i].name, nodes[j].name);
			}
		}
	}
	printf ("}\n");
}

void
read_edges (const char *filename)
{
	FILE *f;
	int n, i, j, k;
	char *from, *to;
	const char *name;
	int total_edges;
	int total_nodes;

	n_edges = total_edges = 0;
	edges = NULL;

	f = fopen (filename, "r");
	if (f == NULL) {
		fprintf (stderr, "file %s not found\n", filename);
		exit (1);
	}
	while (1) {
		n = fscanf (f, "%as -> %as\n", &from, &to);
		if (n == EOF)
			break;
		if (n != 2) {
			fprintf (stderr, "error while reading file %s: %d\n", filename, n);
			exit (1);
		}
		if (n_edges == total_edges) {
			total_edges = MAX (1, total_edges * 2);
			edges = realloc (edges, sizeof (edge_t) * total_edges);
		}
		edges[n_edges].from = from;
		edges[n_edges].to = to;		
		n_edges++;
	}
	fclose (f);

	total_nodes = n_edges;
	n_nodes = 0;
	nodes = malloc (sizeof (node_t) * total_nodes);
	
	for (i = 0; i < n_edges; i++) {
		for (j = 0; j < 2; j++) {
			name = j ? edges[i].from : edges[i].to;
			for (k = 0; k < n_nodes; k++) {
				if (strcmp (name, nodes[k].name) == 0)
					break;
			}
			if (k == n_nodes) {
				if (n_nodes == total_nodes) {
					total_nodes = MAX (1, total_nodes * 2);
					nodes = realloc (nodes, sizeof (node_t) * total_nodes);
				}
				nodes[n_nodes].name = name;
				n_nodes++;
			} 
		}
	}

	/*printf ("read %d edges, %d nodes\n", n_edges, n_nodes);*/
	qsort (nodes, n_nodes, sizeof (node_t), nodecmp);	
	for (i = 0; i < n_nodes; i++)
		nodes[i].idx = i;	

}

void
usage (void)
{
	printf (
"Usage: why [<root package>] <package>\n"
"\n"
"Finds out why a package is installed. If <root package> is specified,\n"
"produces a graph representation of all dependencies from <root package>\n"
"to <package>. If <root package> is not specified, all \"leaf\" packages\n"
"above <package> are included.\n"
"\n"
"Reads package dependencies from a file named \"alldeps\" containing\n"
"lines of the form: <package a> -> <package b>\n"
"\n"
"The output is in the form of a dot file, which can be converted into\n"
"multiple formats using the Graphviz tools.\n");
	exit (1);
}

int 
main (int argc, char *argv[])
{
	char **adj, **path;
	int *comp;
	int i, from, to;
	int target;
	int *roots;
	int n_roots;
	int *sub;

	if (argc < 2 || argc > 3)
		usage ();

	read_edges ("alldeps");

	adj = allocate_matrix (n_nodes, n_nodes);

	/* set up adjacency matrix */
	for (i = 0; i < n_edges; i++) {
		from = find_index (edges[i].from);
		to = find_index (edges[i].to);

		if (from < 0) {
			fprintf (stderr, "edge %d: from node %s not found\n", i, edges[i].from);
			exit (1);
		}
		if (to < 0) {
			fprintf (stderr, "edge %d: to node %s not found\n", i, edges[i].to);
			exit (1);
		}
		
		adj[from][to] = 1;
	}

	/* make irreflexive */
	for (i = 0; i < n_nodes; i++)
		adj[i][i] = 0;

	/* compute transitive closure */
	path = allocate_matrix (n_nodes, n_nodes);
        transitive_closure (adj, path);

	/* compute strong components */
	comp = malloc (sizeof (int) * n_nodes);
	strong_components (path, comp);
	/*dump_components (comp);*/

	if (argc == 2) {
		target = find_index (argv[1]);
		n_roots = find_roots (path, comp, target, &roots);
	}
	else {
		n_roots = 1;
		roots = malloc (sizeof (int));
		roots[0] = find_index (argv[1]);
		target = find_index (argv[2]);
	}

	sub = find_paths (path, comp, target, roots, n_roots);
	print_subgraph (adj, sub, target, roots, n_roots);
	
	free (roots);
	free (sub);

	return 0;
}