/* ckaliases - verify syntax of sendmail-style alias files
   Copyright (C) 2005 Sergey Poznyakoff

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 3 of the License, or (at your
   option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License along
   with this program. If not, see <http://www.gnu.org/licenses/>. */

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free	
#include <obstack.h>
#include "ckaliases.h"

void *
xmalloc(size_t size)
{
	void *p = malloc(size);
	if (!p) {
		fprintf(stderr, "not enough memory\n");
		exit(1);
	}
	return p;
}


#ifndef CHAR_BIT
# define CHAR_BIT 8
#endif
#define BITS_PER_WORD   (sizeof(unsigned)*CHAR_BIT)
#define MAXTABLE        32767

#define WORDSIZE(n)     (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)
#define SETBIT(x, i)    ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD)))
#define RESETBIT(x, i)  ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD)))
#define BITISSET(x, i)  (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0)

/* given n by n matrix of bits R, modify its contents
   to be the transitive closure of what was given.  */

void
TC(unsigned *R, int n)
{
        register int rowsize;
        register unsigned mask;
        register unsigned *rowj;
        register unsigned *rp;
        register unsigned *rend;
        register unsigned *ccol;

        unsigned *relend;
        unsigned *cword;
        unsigned *rowi;

        rowsize = WORDSIZE(n) * sizeof(unsigned);
        relend = (unsigned *) ((char *) R + (n * rowsize));

        cword = R;
        mask = 1;
        rowi = R;
        while (rowi < relend) {
                ccol = cword;
                rowj = R;
                
                while (rowj < relend) {
                        if (*ccol & mask) {
                                rp = rowi;
                                rend = (unsigned *) ((char *) rowj + rowsize);
                                
                                while (rowj < rend)
                                        *rowj++ |= *rp++;
                        } else {
                                rowj = (unsigned *) ((char *) rowj + rowsize);
                        }
                        
                        ccol = (unsigned *) ((char *) ccol + rowsize);
                }
                
                mask <<= 1;
                if (mask == 0) {
                        mask = 1;
                        cword++;
                }
                rowi = (unsigned *) ((char *) rowi + rowsize);
        }
}



void
slist_add(SLIST **plist, char *str)
{
	struct string_list *p = xmalloc(sizeof(*p));
	p->str = str;
	p->next = NULL;
	
	if (!*plist) {
		*plist = xmalloc(sizeof(**plist));
		(*plist)->head = NULL;
	}

	if ((*plist)->head == NULL) {
		(*plist)->head = p;
		(*plist)->count = 0;
	} else {
		(*plist)->tail->next = p;
		(*plist)->count++;
	}
	(*plist)->tail = p;
}

void
slist_append(SLIST **pdst, SLIST *src)
{
	struct string_list *tail;
	
	if (!*pdst) {
		*pdst = xmalloc(sizeof(**pdst));
		(*pdst)->head = NULL;
		(*pdst)->count = 0;
	}

	if ((*pdst)->head = NULL) 
		(*pdst)->head = src->head;
	
	for (tail = src->tail; tail->next; tail = tail->next)
		;
	
	(*pdst)->tail = tail;
	(*pdst)->count += src->count;
}

char *
slist_member(SLIST *plist, char *name)
{
	struct string_list *p;
	
	if (plist)
		for (p = plist->head; p; p = p->next)
			if (p->str && strcmp(p->str, name) == 0)
				return p->str;
	return NULL; 
}

void
slist_destroy(SLIST **plist)
{
	struct string_list *p;
	if (!plist || !*plist)
		return;
	p = (*plist)->head;
	while (p) {
		struct string_list *next = p->next;
		free(p);
		p = next;
	}
	free(*plist);
	*plist = NULL;
}
		



typedef struct {
	char *name;
	SLIST *exp;
} ALIAS;

struct obstack alias_stk;
unsigned alias_count;
ALIAS *aliases;

void
regalias(char *name, SLIST *exp)
{
	ALIAS a;
	a.name = name;
	a.exp = exp;
	obstack_grow(&alias_stk, &a, sizeof a);
	alias_count++;
}

void
begin_aliases()
{
	obstack_init(&alias_stk);
}

static int
alias_cmp(const void *a, const void *b)
{
	return strcmp(((ALIAS*)a)->name, ((ALIAS*)b)->name);
}

static int
alias_cmp2(const void *a, const void *b)
{
	char *aname = ((ALIAS*)a)->name;
	char *bname = ((ALIAS*)b)->name;
	int rc;
	int alen;
	int blen;
	char *p;

	if ((p = strchr(aname, '@')) && slist_member(cw_list, p+1))
		alen = p - aname;
	else
		alen = strlen(aname);

	if ((p = strchr(bname, '@')) && slist_member(cw_list, p+1)) 
		blen = p - bname;
	else
		blen = strlen(bname);

	if (alen == blen)
		return memcmp(aname, bname, alen);
	
	return strcmp(aname, bname);
}

void
end_aliases()
{
	int i;
	aliases = obstack_finish(&alias_stk);
	qsort(aliases, alias_count, sizeof aliases[0], alias_cmp);
	for (i = 1; i < alias_count; i++)
		if (alias_cmp(aliases + i - 1, aliases + i) == 0)
			error("alias `%s' multiply defined", aliases[i].name);
}


int
find_alias(char *name)
{
	ALIAS a, *p;

	if (!name)
		return -1;
	a.name = name;
	p = bsearch(&a, aliases, alias_count, sizeof aliases[0], alias_cmp2);
	return p ? p - aliases : -1;
}


static void
alias_setbit(unsigned *r, unsigned rowsize, unsigned row, unsigned col)
{
        SETBIT(r + rowsize * row, col);
}

static int
alias_bitisset(unsigned *r, unsigned rowsize, unsigned row, unsigned col)
{
        return BITISSET(r + rowsize * row, col);
}


void
mark_connected(unsigned *r, unsigned size)
{
	int i;
	
	for (i = 0; i < alias_count; i++) {
		if (aliases[i].exp) {
			struct string_list *p;
			for (p = aliases[i].exp->head; p; p = p->next) {
				int n = find_alias(p->str);
				if (n >= 0)
					alias_setbit(r, size, i, n);
			}
		}
	}
}

void
check_circular_deps(unsigned *r, unsigned size)
{
	int i;
	
	for (i = 0; i < alias_count; i++) {
		if (alias_bitisset(r, size, i, i))
			error("%s: circular dependency", aliases[i].name);
	}
}

void
check_aliases()
{
	size_t size;
	unsigned *r;
	
	/* Allocate matrix */
	size = (alias_count + BITS_PER_WORD - 1) / BITS_PER_WORD;
	r = xmalloc(alias_count*size*sizeof(*r));
	memset(r, 0, alias_count*size*sizeof(*r));

	/* First pass: mark directly connected entries */
	mark_connected(r, size);

	/* Compute transitive closure of the matrix r */
	TC(r, alias_count);

	/* Third pass: check for circular deps */
	check_circular_deps(r, size);

	if (verbose)
		printf("%lu aliases\n", alias_count);
}