path: root/alck.c

/* ckaliases - verify syntax of sendmail-style alias files
   Copyright (C) 2005, 2007 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/>. */

#include "alck.h"

#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);
	}
}

struct alias {
	struct alias *prev, *next;
	char *name;
	int num;
	SLIST *exp;
};

struct ali_list {
	struct alias *head, *tail;
	size_t count;
};

struct ali_list aliases;

static int
ali_cmp(struct alias *a, struct alias *b)
{
	return strcmp(a->name, b->name);
}

static int
ali_cmp2(struct alias *a, struct alias *b)
{
	char *aname = a->name;
	char *bname = 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
ali_insert(struct ali_list *lp,
	   struct alias *anchor,
	   struct alias *ent, int before)
{
	struct alias *p;

	if (!anchor) {
		ent->prev = NULL;
		ent->next = lp->head;
		if (lp->head)
			lp->head->prev = ent;
		else
			lp->tail = ent;
		lp->head = ent;
		lp->count++;
		return;
	}

	if (before) {
		ali_insert(lp, anchor->prev, ent, 0);
		return;
	}

	ent->prev = anchor;
	if (p = anchor->next)
		p->prev = ent;
	else
		lp->tail = ent;
	ent->next = p;
	anchor->next = ent;
	lp->count++;
}

void
ali_join(struct ali_list *a, struct ali_list *b)
{
	if (!b->head)
		return;
	b->head->prev = a->tail;
	if (a->tail)
		a->tail->next = b->head;
	else
		a->head = b->head;
	a->tail = b->tail;
}

void
ali_sort(struct ali_list *list, int (*cmp)(struct alias *, struct alias *))
{
	struct alias *cur, *middle;
	struct ali_list high_list, low_list;
	int rc;

	if (!list->head)
		return;
	cur = list->head;
	do {
		cur = cur->next;
		if (!cur)
			return;
	} while ((rc = cmp(list->head, cur)) == 0);

	/* Select the lower of the two as the middle value */
	middle = (rc > 0) ? cur : list->head;

	/* Split into two sublists */
	low_list.head = low_list.tail = NULL;
	high_list.head = high_list.tail = NULL;

	for (cur = list->head; cur; ) {
		struct alias *next = cur->next;
		cur->next = NULL;
		if (cmp(middle, cur) < 0)
			ali_insert(&high_list, high_list.tail, cur, 0);
		else
			ali_insert(&low_list, low_list.tail, cur, 0);
		cur = next;
	}

	/* Sort both sublists recursively */
	ali_sort(&low_list, cmp);
	ali_sort(&high_list, cmp);

	/* Join both lists in order */
	ali_join(&low_list, &high_list);

	/* Return the resulting list */
	list->head = low_list.head;
	list->tail = low_list.tail;
}

struct alias *
ali_locate(struct ali_list *lp, int (*cmp)(struct alias *, struct alias *),
	   struct alias *data)
{
	struct alias *ep;

	for (ep = lp->head; ep; ep = ep->next) {
		if (cmp(ep, data) == 0)
			return ep;
	}
	return NULL;
}

void
end_aliases()
{
	int i;
	struct alias *ali;
	
	ali_sort(&aliases, ali_cmp);
	if (!aliases.head)
		return;
	for (i = 0, ali = aliases.head; ali->next; ali = ali->next, i++) {
		if (ali_cmp(ali, ali->next) == 0) {
			error("alias `%s' multiply defined", ali->name);
			error_count++;
		}
		ali->num = i;
	}
}

void
regalias(char *name, SLIST *exp)
{
	struct alias *a = emalloc(sizeof(*a));
	a->name = name;
	a->exp = exp;
	a->next = NULL;
	ali_insert(&aliases, NULL, a, 0);
}

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

	if (!name)
		return -1;
	a.name = name;
	p = ali_locate(&aliases, ali_cmp2, &a);
	return p ? p->num : -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)
{
	struct alias *ali;

	for (ali = aliases.head; ali; ali = ali->next) {
		if (ali->exp) {
			struct string_list *p;
			for (p = ali->exp->head; p; p = p->next) {
				int n = find_alias(p->str);
				if (n >= 0)
					alias_setbit(r, size, ali->num, n);
			}
		}
	}
}

void
check_circular_deps(unsigned *r, unsigned size)
{
	struct alias *ali;

	for (ali = aliases.head; ali; ali = ali->next) {
		if (alias_bitisset(r, size, ali->num, ali->num)) {
			error("%s: circular dependency", ali->name);
			error_count++;
		}
	}
}

void
check_aliases()
{
	size_t size;
	unsigned *r;

	/* Allocate matrix */
	size = (aliases.count + BITS_PER_WORD - 1) / BITS_PER_WORD;
	r = emalloc(aliases.count * size * sizeof(*r));
	memset(r, 0, aliases.count * size * sizeof(*r));

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

	/* Compute transitive closure of the matrix r */
	TC(r, aliases.count);

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

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