/* This file is part of Mailfromd.
   Copyright (C) 2007-2008, 2010-2011, 2015-2016 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, 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 <string.h>
#include "mailfromd.h"
#include "spf.h"

typedef struct spf_term spf_term;

#define SPF_MOD_EXP      0
#define SPF_MOD_REDIRECT 1
#define MAX_SPF_MOD      2
typedef struct spf_data {
	/* Internal data */
	mu_opool_t tmpool;       /* Opool for keeping temporary values */
	char *buffer;            /* Expansion and transformation buffer */  
	size_t bufsize;          /* Size of buffer */
	spf_term *mod[MAX_SPF_MOD];
	size_t loopno;
	/* Input data */
	spf_query_t q;
	struct in_addr ipaddr;   /* Originator IP in binary (network order) */
	/* Output data */
	spf_result result;       /* SPF result if a term throws an exception */
	spf_answer_t *answer;
} spf_data;

#define UPDATE_ANSWER_TTL(dat, ttl)		                \
	do {					                \
	        if ((dat)->answer) {				\
			UPDATE_TTL((dat)->answer->ttl, ttl);	\
		}						\
	} while (0)

static char *spf_result_str[] = {
	"None",
	"Neutral",
	"Pass",
	"Fail",
	"SoftFail",
	"TempError",
	"PermError",
};

static spf_result spf_check_host_internal(spf_query_t *q, spf_answer_t *answer,
					  size_t loopno);

int
spf_data_init(struct spf_data *dat, spf_query_t *q, spf_answer_t *answer,
	      size_t loopno)
{
	memset(dat, 0, sizeof dat[0]);
	mu_opool_create(&dat->tmpool, MU_OPOOL_ENOMEMABRT);
	dat->q = *q;
	if (!inet_aton(dat->q.ipstr, &dat->ipaddr)) {
		mu_error(_("spf_data_init: invalid IP address: %s"),
			 dat->q.ipstr);
		return 1;
	}
	dat->ipaddr.s_addr = ntohl(dat->ipaddr.s_addr);
	dat->answer = answer;
	dat->loopno = loopno;
	return 0;
}

void
spf_data_alloc(struct spf_data *dat, size_t s)
{
	if (dat->bufsize < s) {
		dat->bufsize = s;
		dat->buffer = mu_realloc(dat->buffer, dat->bufsize);
	}
}

void
spf_data_free(struct spf_data *dat)
{
	free(dat->buffer);
	mu_opool_destroy(&dat->tmpool);
}

char *
spf_data_ptr(struct spf_data *dat)
{
	return mu_opool_finish(dat->tmpool, NULL);
}

/* Swap LEN bytes between A and B */
void
swapi(char *a, char *b, size_t len)
{
	int t;
	while (len--) {
		t = *b;
		*b++ = *a;
		*a++ = t;
	}
}

/* Swap LEN bytes between A and B in backward direction */
void
swapd(char *a, char *b, size_t len)
{
	int t;
	while (len--) {
		t = *b;
		*b-- = *a;
		*a-- = t;
	}
}

static char *
scanback(char *s, int c, size_t n)
{
	s += n;
	while (n > 0) {
		n--;
		s--;
		if (*s == c)
			return s;
	}
	return NULL;
}

/* Reverse the order of parts of BUF, delimited by DELIM */
void
spf_reverse(char *buf, size_t len, int delim)
{
	char *lp, *rp;
	size_t llen, rlen;
	char *tmp = NULL;
	size_t tmpsize = 0;
	size_t delta;
	size_t bufsize = strlen(buf);
	
	do {
		lp = memchr(buf, delim, bufsize);
		if (!lp)
			break;
		llen = lp - buf;
		rp = scanback(buf, delim, bufsize) + 1;
		rlen = bufsize - (rp - buf);
		
		if (llen == rlen)
			swapi(buf, rp, llen);
		else if (llen < rlen) {
			swapi(buf, rp, llen);
			delta = rlen - llen;
			if (tmpsize < delta) {
				tmpsize = delta;
				tmp = mu_realloc(tmp, tmpsize);
			}
			memcpy(tmp, rp + llen, delta);
			memmove(lp + delta, lp, bufsize - (lp - buf) - delta);
			memcpy(buf + llen, tmp, delta);
			rp += delta;
			lp += delta;
		} else /* if (rlen < llen) */ {
			swapd(buf + llen - 1, rp + rlen - 1, rlen);
			delta = llen - rlen;
			if (tmpsize < delta) {
				tmpsize = delta;
				tmp = mu_realloc(tmp, tmpsize);
			}
			memcpy(tmp, buf, delta);
			memmove(buf, buf + delta, rp - buf - 1);
			rp -= delta;
			memcpy(rp, tmp, delta);
			lp -= delta;
		}
 		buf = lp + 1;
		bufsize = rp - buf - 1;
	} while (rp > lp + 1);
	free(tmp);
}

/* BUFFER contains several DELIM-separated parts. Retain at most
   NPARTS right-hand parts of them. If NPARTS is greater than the
   actual number of parts, then do nothing */
void
spf_truncate(char *buffer, int delim, unsigned nparts)
{
	char *p;
	size_t len;

	len = strlen(buffer);
	while (nparts--) {
		if (len == 0)
			return;
		p = scanback(buffer, delim, len);
		if (!p)
			return;
		if (p == buffer)
			return;
		len = p - buffer;
	}
	p++;
	len = strlen(p);
	memmove(buffer, p, len + 1);
}

/* Replace with dots all occurrences of DELIM in first LEN bytes of BUF */
void
spf_repl(char *buf, size_t len, int delim)
{
	while (len--) {
		if (*buf == delim)
			*buf = '.';
		buf++;
	}
}

/* Perform an RFC 4408 transformation.
   DAT - current spf_data
   X   - the substituted value
   L   - its length
   PPTR points to the current position in the macro string.
   Return 0 if successful and move PPTR past the closing curly brace.
   If there is no brace, return 1 (failure) */
int
spf_transform(struct spf_data *dat, const char *x, size_t l, const char **pptr)
{
	const char *p = *pptr;
	int nparts = 0;
	int reverse = 0;
	int delim = '.';
	
	while (mu_isdigit(*p))
		nparts = nparts * 10 + *p++ - '0';
	
	if (*p == 'r') {
		p++;
		reverse = 1;
	}
	if (*p && strchr(".-+,/_=:", *p))
		delim = *p++;
	if (*p != '}')
		return 1;
	*pptr = p + 1;
		
	if (l == 0)
		l = strlen(x);

	spf_data_alloc(dat, l + 1);
	memcpy(dat->buffer, x, l);
	dat->buffer[l] = 0;

	if (reverse)
		spf_reverse(dat->buffer, l, delim);
	if (nparts) {
		spf_truncate(dat->buffer, delim, nparts);
		l = strlen(dat->buffer);
	}
	if (delim != '.')
		spf_repl(dat->buffer, l, delim);

	mu_opool_append(dat->tmpool, dat->buffer, l);

	return 0;
}

/* Return 1 if NAME ends in DOMAIN */
static int
domain_match(const char *name, const char *domain)
{
	const char *np = name + strlen(name) - 1;
	const char *dp = domain + strlen(domain) - 1;

	while (1) {
		if (tolower(*dp) != tolower(*np))
			return 0;
		if (np == name)
			return dp == domain;
		np--;
		if (dp == domain)
			return *np == '.';
		dp--;
	}
}

/* Expand a single macro as per RFC 4408, chapter 8.
   PPTR points to the macro symbol, right past the opening curly brace.
   ALLOW_EXP is 1 if the expansion of macros c, r and t is allowed (see
   RFC 4408, page 27).
   Return 0 on success, 1 on failure.
   Before returning advance PPTR past the last character parsed (a closing
   '}' in case of success). */
int
spf_expand_do(struct spf_data *dat, int allow_exp, const char **pptr)
{
	char *q;
	
	switch (*(*pptr)++) {
	case 'd':
	case 'D':
		return spf_transform(dat, dat->q.domain, 0, pptr);
		
	case 'h':
	case 'H':
		return spf_transform(dat, dat->q.helo_domain, 0, pptr);
		
	case 'i':
	case 'I':
		return spf_transform(dat, dat->q.ipstr, 0, pptr);
		
	case 'l':
	case 'L':
		q = strchr(dat->q.sender, '@');
		if (!q)
			return 1;
		return spf_transform(dat, dat->q.sender, q - dat->q.sender,
				     pptr);
		
	case 'o':
	case 'O':
		q = strchr(dat->q.sender, '@');
		if (!q)
			return 1;
		return spf_transform(dat, q + 1, 0, pptr);
		
	case 'p':
	case 'P':
	{
		int rc;
		size_t i;
		char *name = NULL;
		char **vnames;
		size_t vcount;
		unsigned long ttl;
		dns_status status = ptr_validate(dat->q.ipstr,
						 &vnames, &vcount,
						 &ttl);
		if (status != dns_success)
			return spf_transform(dat, "unknown", 0, pptr);

		UPDATE_ANSWER_TTL(dat, ttl);
		
		for (i = 0; i < vcount; i++)
			if (strcasecmp(vnames[i], dat->q.domain) == 0) {
				name = vnames[i];
				break;
			}

		if (!name) {
			for (i = 0; i < vcount; i++)
				if (domain_match(vnames[i], dat->q.domain)) {
					name = vnames[i]; 
					break;
				}

			if (!name)
				name = vnames[0];
		}

		rc = spf_transform(dat, name, 0, pptr);
		mu_argcv_free(vcount, vnames);
		return rc;
	}
		
	case 's':
	case 'S':
		return spf_transform(dat, dat->q.sender, 0, pptr);

	case 'v':
	case 'V':
		/* FIXME: add IPv6 support */
		return spf_transform(dat, "in-addr", 0, pptr);
		
	case 'c':
	case 'C':
		if (!allow_exp)
			return 1;
		else
			return spf_transform(dat, dat->q.ipstr, 0, pptr);
		
	case 'r':
	case 'R':
		if (!allow_exp)
			return 1;
		else
			return spf_transform(dat, dat->q.my_domain, 0, pptr);
		
	case 't':
	case 'T':
		if (!allow_exp)
			return 1;
		else {
			char buf[NUMERIC_BUFSIZE_BOUND];
			snprintf(buf, sizeof buf, "%lu",
				 (unsigned long) time(NULL));
			mu_opool_appendz(dat->tmpool, buf);
		}
		break;

	default:
		return 1;
	}
	return 0;
}

/* Expand the macro string INPUT as per RFC 4408, chapter 8.
   ALLOW_EXP is 1 if the expansion of macros c, r and t is allowed (see
   RFC 4408, page 27).
   Return 0 on success, 1 on failure.
   To obtain the expanded string, run spf_data_ptr(dat); */
int
_spf_macro_expand(const char *input, struct spf_data *dat, int allow_exp)
{
	const char *p;
	
	while (p = strchr(input, '%')) {
		size_t len = p - input;
		if (len > 0)
			mu_opool_append(dat->tmpool, input, len);
		switch (p[1]) {
		case '{':
			p += 2;
			if (spf_expand_do(dat, allow_exp, &p))
				return 1;
			break;
			
		case '%':
			mu_opool_append_char(dat->tmpool, '%');
			p += 2;
			break;
			
		case '_':
			mu_opool_append_char(dat->tmpool, ' ');
			p += 2;
			break;
			
		case '-':
			mu_opool_appendz(dat->tmpool, "%20");
			p += 2;
			break;

		default:
			return 1;
		}
		input = p;
	}
	if (input) 
		mu_opool_appendz(dat->tmpool, input);
	mu_opool_append_char(dat->tmpool, 0);
	return 0;
}

/* The interface function for _spf_macro_expand above.
   Takes care about unfinished opool memory in case of failure. */
int
spf_macro_expand(const char *input, struct spf_data *dat, int allow_exp)
{
	int rc = _spf_macro_expand(input, dat, allow_exp);
	if (rc)
		mu_opool_free(dat->tmpool, NULL);
	return rc;
}


/* ******************* */
/*  SPF term evaluator */

typedef enum {
	spf_term_mechanism,
	spf_term_modifier
} spf_term_type;

typedef enum {
	spf_arg_none,
	spf_arg_domain_spec,
	spf_arg_ipv4,
	spf_arg_ipv6
} spf_arg_type;

typedef struct {
	spf_arg_type type;
	union {
		char *domain_spec;
		struct in_addr ip;
		/* FIXME: ipv6 */
	} v;
} spf_term_arg;

typedef enum {
	spf_term_match,
	spf_term_nomatch,
	spf_term_exception,
} spf_term_result;

typedef spf_term_result (*spf_term_handler)(struct spf_data *dat,
					    spf_term_arg *arg,
					    unsigned long masklen);

struct spf_term {
	spf_term_type type;           /* Term type */
	const char *expr;             /* Original expression (for debugging)*/ 
	spf_term_handler handler;     /* Term handler */
	int has_arg;                  /* Is an explicite argument given */
	spf_term_arg arg;             /* Argument if has_arg==1 */
	spf_result qualifier;         /* only for type == spf_term_directive */
	unsigned long masklen;        /* Netmask length */
};

struct spf_term_syntax {
	char *tag;
	spf_term_type type;
	spf_arg_type argtype;
	unsigned long default_masklen; /* 0 if not allowed */
	spf_term_handler handler;
	int mod_index; /* Modifier index */
};

#define DNS_CATCH(expr) \
	switch (expr) {                                           \
	case dns_success:                                         \
		break;                                            \
	case dns_not_found:                                       \
	case dns_failure:                                         \
		return spf_term_nomatch;                          \
	case dns_temp_failure:                                    \
		dat->result = spf_temp_error;                     \
		return spf_term_exception;                        \
	}		


/* Hanlders for particular terms */

/* RFC 4408, 5.1.
     all              = "all"
*/
static spf_term_result 
mech_all(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	dat->mod[SPF_MOD_REDIRECT] = NULL;
	return spf_term_match;
}

/* 5.2.
         include          = "include"  ":" domain-spec
*/
static spf_term_result 
mech_include(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	spf_result res;
	spf_term_result tres;
	spf_query_t query;
	size_t mechn;
	
	if (!arg) {
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
			 ("include used without argument"));
		dat->result = spf_perm_error;
		return spf_term_exception;
	}
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
		 ("include %s", arg->v.domain_spec));

	query = dat->q;
	query.domain = arg->v.domain_spec;
	mechn = dat->answer->mechn;
	res = spf_check_host_internal(&query, dat->answer, dat->loopno);
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1, 
		 ("check_host returned %s", spf_result_str[res]));
	switch (res) {
	case spf_pass:
		tres = spf_term_match;
		break;
		
	case spf_fail:
	case spf_soft_fail:
	case spf_neutral:
		/* Remove any mechanisms that may have been saved during
		   interior check_host */
		while (dat->answer->mechn > mechn)
			free(dat->answer->mechv[--dat->answer->mechn]);
		tres = spf_term_nomatch;
		break;

	case spf_temp_error:
		dat->result = spf_temp_error;                     
		tres = spf_term_exception;
		break;
		
	case spf_perm_error:
	case spf_none:
		dat->result = spf_perm_error;
		tres = spf_term_exception;
		break;
	}		

	return tres;
}

/* Compute IPv4 netmask for the given length */
static unsigned long
make_netmask(unsigned long masklen)
{
	unsigned long netmask;
	masklen = 32 - masklen;
	if (masklen == 32)
		netmask = 0;
	else
		netmask = (0xfffffffful >> masklen) << masklen;
	return netmask;
}

/* 5.3.
      A                = "a"      [ ":" domain-spec ] [ dual-cidr-length ]
*/
static spf_term_result 
mech_a(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	const char *domain_spec;
	unsigned long netmask;
	struct in_addr addr;
	GACOPYZ_UINT32_T ipbuf[64]; /* FIXME: arbitrary limit */
	size_t i, ipcount;
	unsigned long ttl;
	
	if (arg) 
		domain_spec = arg->v.domain_spec;
	else 
		domain_spec = dat->q.domain;

	netmask = make_netmask(masklen);
	
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1, 
		 ("A domain_spec=%s, netmask=%lx", domain_spec, netmask));
	
	DNS_CATCH(a_lookup(domain_spec, ipbuf, NELEMS(ipbuf), &ipcount,
			   &ttl, NULL, 0));
	UPDATE_ANSWER_TTL(dat, ttl);
	
	addr.s_addr = dat->ipaddr.s_addr & netmask;
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE6,
		 ("A: s_addr=%x", addr.s_addr));
	
	for (i = 0; i < ipcount; i++) {
		if ((ntohl(ipbuf[i]) & netmask) == addr.s_addr) {
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
				 ("A matches"));
			return spf_term_match;
		}
	}
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1, ("A does not match"));
	return spf_term_nomatch;
}

/* 5.4.
      MX               = "mx"     [ ":" domain-spec ] [ dual-cidr-length ]
*/
static spf_term_result  
mech_mx(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	unsigned long netmask = make_netmask(masklen);
	struct mxbuf mxbuf;
	size_t i;
	spf_term_result result = spf_term_nomatch;
	const char *domain_spec;
	unsigned long ttl;
	
	if (arg)
		domain_spec = arg->v.domain_spec;
	else
		domain_spec = dat->q.domain;

	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
		 ("MX domain_spec=%s, netmask=%lx",
		  domain_spec, netmask));

	mxbuf.mx_flags = MXF_MAX;
	mxbuf.mx_max = 10;
	DNS_CATCH(dns_get_mx_records(domain_spec, 1, &mxbuf, &ttl));
	UPDATE_ANSWER_TTL(dat, ttl);
	
	for (i = 0; i < mxbuf.mx_cnt; i++) {
		spf_term_arg targ;
		spf_term_result res;
		
		targ.type = spf_arg_domain_spec;
		targ.v.domain_spec = mxbuf.mx_buf[i];
		res = mech_a(dat, &targ, masklen);
		if (res == spf_term_match) {
			result = res;
			break;
		}
	}

	mxbuf_free(&mxbuf);
	return result;
}

/* 5.5.
      PTR              = "ptr"    [ ":" domain-spec ]
*/
static spf_term_result  
mech_ptr(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	char **vnames;
	size_t vcount;
	size_t i;
	const char *domain_spec;
	spf_term_result result = spf_term_nomatch;
	unsigned long ttl;
	
	if (arg)
		domain_spec = arg->v.domain_spec;
	else
		domain_spec = dat->q.domain;
	
	DNS_CATCH(ptr_validate(dat->q.ipstr, &vnames, &vcount, &ttl));
	UPDATE_ANSWER_TTL(dat, ttl);
	
	for (i = 0; i < vcount; i++)
		if (domain_match(vnames[i], domain_spec)) {
			result = spf_term_match;
			break;
		}
	mu_argcv_free(vcount, vnames);
	return result;
}

/* 5.6.
      IP4              = "ip4"      ":" ip4-network   [ ip4-cidr-length ]
*/
static spf_term_result  
mech_ip4(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	unsigned long netmask = make_netmask(masklen);

	if (!arg) {
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
			 ("ip4 used without argument"));
		dat->result = spf_perm_error;
		return spf_term_exception;
	}
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1, 
		 ("IP4 addr=%lx, netmask=%lx",
		  (unsigned long) arg->v.ip.s_addr, netmask));

	if ((dat->ipaddr.s_addr & netmask) == (arg->v.ip.s_addr & netmask)) 
		return spf_term_match;
	return spf_term_nomatch;
}

/* Not yet implemented: 
     IP6              = "ip6"      ":" ip6-network   [ ip6-cidr-length ]
*/
static spf_term_result  
mech_ip6(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
		 ("ip6 mechanism is not yet supported"));
	dat->result = spf_perm_error;
	return spf_term_exception;
}

/* 5.7.
      exists           = "exists"   ":" domain-spec
*/
static spf_term_result  
mech_exists(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	unsigned long ttl;
	if (!arg) {
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
			 ("exists used without argument"));
		dat->result = spf_perm_error;
		return spf_term_exception;
	}
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
		 ("EXISTS domain_spec=%s", arg->v.domain_spec));
	
	DNS_CATCH(a_lookup(arg->v.domain_spec, NULL, 0, NULL, &ttl, NULL, 0));
	UPDATE_ANSWER_TTL(dat, ttl);
	
	return spf_term_match;
}

/* 6.1.
      redirect         = "redirect" "=" domain-spec
*/
static spf_term_result  
mod_redirect(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	spf_query_t query;

	query = dat->q;
	query.domain = arg->v.domain_spec;
	dat->result = spf_check_host_internal(&query, dat->answer, dat->loopno);
	if (dat->result == spf_none) 
		dat->result = spf_perm_error;
	return spf_term_exception;
}

/* 6.2.
      explanation      = "exp" "=" domain-spec
*/
static spf_term_result  
mod_exp(spf_data *dat, spf_term_arg *arg, unsigned long masklen)
{
	char *names[128]; /* FIXME: arbitrary limit */
	if (arg->v.domain_spec
	    && txt_lookup(arg->v.domain_spec,
			  names, NELEMS(names), NULL,
			  NULL, 0) == dns_success) {
		int i;
		char *text;
		
		for (i = 0; names[i]; i++) {
			mu_opool_appendz(dat->tmpool, names[i]);
			free(names[i]);
		}
		mu_opool_append_char(dat->tmpool, 0);
		text = spf_data_ptr(dat);

		if (dat->q.exp_prefix)
			mu_opool_appendz(dat->tmpool, dat->q.exp_prefix);
		if (spf_macro_expand(text, dat, 1)) {
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
				 ("error expanding explanation text %s",
				  text));
//FIXME			mu_opool_append_char(dat->tmpool, 0);
		} else 
			dat->answer->exp_text = mu_strdup(spf_data_ptr(dat));
	}
	return spf_term_nomatch;
}


/* Syntax driver table */
static struct spf_term_syntax term_syntax[] = {
	{ "all", spf_term_mechanism, spf_arg_none, 0, mech_all },
	{ "include", spf_term_mechanism, spf_arg_domain_spec, 0,
	  mech_include },
	{ "a", spf_term_mechanism, spf_arg_domain_spec, 32, mech_a },
	{ "mx", spf_term_mechanism, spf_arg_domain_spec, 32, mech_mx },
	{ "ptr", spf_term_mechanism, spf_arg_domain_spec, 0, mech_ptr },
	{ "ip4", spf_term_mechanism, spf_arg_ipv4, 32, mech_ip4 },
	{ "ip6", spf_term_mechanism, spf_arg_ipv6, 128, mech_ip6 },
	{ "exists", spf_term_mechanism, spf_arg_domain_spec, 0, mech_exists },
	{ "redirect", spf_term_modifier, spf_arg_domain_spec, 0,
	  mod_redirect, SPF_MOD_REDIRECT },
	{ "exp", spf_term_modifier, spf_arg_domain_spec, 0, mod_exp,
	  SPF_MOD_EXP },
	{ NULL }
};

/* Return a syntax driver for the given TAG */
static const struct spf_term_syntax *
find_syntax(const char *tag)
{
	const struct spf_term_syntax *p;
	for (p = term_syntax; p->tag; p++)
		if (strcasecmp(p->tag, tag) == 0)
			return p;
	return NULL;
}

#define ISSPACE(c) ((c) == ' ' || (c) == '\t')
#define skip_word(p) while (*(p) && !ISSPACE(*(p))) ++(p)
#define skip_space(p) while (*(p) && ISSPACE(*(p))) ++(p)

/* Parse the SPFv1 record REC.
   On success, return 0 and store the compiled array of terms in PTERMV,
   the number of terms in PTERMC, and the number of modifiers in PMODC.
   Make sure the compiled modifiers follow the mechanisms.
*/
static int
parse_record(char *rec, struct spf_data *dat, int *ptermc, spf_term **ptermv)
{
	int termc = 0;
	char *p;
	int i;
	spf_term term;
	char *expr_space;
	spf_term modv[MAX_SPF_MOD];

	memset(modv, 0, sizeof modv);
	
	/* Skip the initial version declaration */
	skip_word(rec);

	/* Allocate enough memory for debugging strings */
	mu_opool_alloc(dat->tmpool, strlen(rec) + 1);
	expr_space = mu_opool_finish(dat->tmpool, NULL);
		
	while (*rec) {
		char *arg;
		char *maskp = NULL;
		spf_term_type type = spf_term_mechanism;
		const struct spf_term_syntax *synt;
		
		skip_space(rec);
		p = rec;
		skip_word(rec);
		if (*rec)
			*rec++ = 0;

		term.expr = expr_space;
		strcpy(expr_space, p);
		expr_space += rec - p;
		
		switch (*p) {
		case '+':
			term.qualifier = spf_pass;
			p++;
			break;
			
		case '-':
			term.qualifier = spf_fail;
			p++;
			break;
			
		case '~':
			term.qualifier = spf_soft_fail;
			p++;
			break;
			
		case '?':
			term.qualifier = spf_neutral;
			p++;
			break;

		default:
			term.qualifier = spf_pass;
		}

		
		for (arg = p; *arg; arg++)
			if (*arg == ':') {
				*arg++ = 0;
				type = spf_term_mechanism;
				break;
			} else if (*arg == '/') {
				maskp = arg + 1;
				*arg = 0;
				type = spf_term_mechanism;
				break;
			} else if (*arg == '=') {
				*arg++ = 0;
				type = spf_term_modifier;
				break;
			}

		synt = find_syntax(p);
		if (!synt) {
			if (type == spf_term_modifier) {
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
					 ("ignoring unknown modifier %s", p));
				continue;
			} else {
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
					 ("unknown mechanism %s", p));
				return 1;
			}
		}
		
		if (synt->type != type) {
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
				 ("invalid use of %s", p));
			return 1;
		}
		
		term.type = synt->type;
		term.handler = synt->handler;
		term.masklen = synt->default_masklen;

		if (!maskp) {
			if (arg) {
				maskp = strchr(arg, '/');
				if (maskp)
					*maskp++ = 0;
			}
		}

		if (maskp) {
			if (synt->default_masklen) {
				char *endp;
				term.masklen = strtoul(maskp, &endp, 0);
				if (*endp == '/') {
					mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
					      ("ignoring unsupported IPv6 mask %s",
					       endp));
				} else if (*endp) {
					mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
					      ("invalid netmask %s "
					       "(stopped near %s)",
					       maskp, endp));
					return 1;
				}
			} else {
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
                                      ("error: netmask used with %s", p));
				return 1;
			}
		}
		
		if (!*arg)
			term.has_arg = 0;
		else if (synt->argtype == spf_arg_none) {
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
                              ("%s used with an argument", p));
			return 1;
		} else {
			term.has_arg = 1;
			term.arg.type = synt->argtype;
			switch (synt->argtype) {
			default:
				abort(); 

			case spf_arg_domain_spec:
				term.arg.v.domain_spec = arg;
				break;
				
			case spf_arg_ipv4:
				if (!inet_aton(arg, &term.arg.v.ip)) {
					mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
						 ("invalid IPv4: %s", arg));
					return 1;
				}
				term.arg.v.ip.s_addr = ntohl(term.arg.v.ip.s_addr);
				break;
					  
			case spf_arg_ipv6:
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
					 ("ignoring unsupported IPv6: %s",
					  arg));
				continue;
			}
		}
		
		if (term.type == spf_term_modifier) {
			if (modv[synt->mod_index].handler) {
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
					 ("duplicate %s modifier", p));
				return 1;
			}
			modv[synt->mod_index] = term;
		} else {
			mu_opool_append(dat->tmpool, &term, sizeof term);
			termc++;
		}
	}

	*ptermc = termc;
	*ptermv = (spf_term*) spf_data_ptr(dat);
	
	for (i = 0; i < NELEMS(modv); i++)
		dat->mod[i] = mu_opool_dup(dat->tmpool, &modv[i],
					   sizeof modv[0]);
	return 0;
}

static int
expand_term_arg(struct spf_data *dat, spf_term *term, spf_term_arg **parg)
{
	if (term->has_arg) {
		spf_term_arg *arg = &term->arg;
		if (arg->type == spf_arg_domain_spec) {
			if (spf_macro_expand(arg->v.domain_spec, dat, 0)) {
				mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR, 
					 ("error expanding %s",
					  arg->v.domain_spec));
				return 1;
			}
			arg->v.domain_spec = spf_data_ptr(dat);
		}
		*parg = arg;
	} else
		*parg = NULL;
	return 0;
}

/* Parse and evaluate SPFv1 record REC. */
spf_result
spf_eval_record(char *rec, struct spf_data *dat)
{
	int i;
	int termc;
	spf_term *termv, *tp;
	spf_result result = spf_neutral;
	const char *match = NULL;
	spf_term_arg *parg;
		
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,
		 ("Parsing SPF record: %s", rec));
	if (parse_record(rec, dat, &termc, &termv))
	    return spf_perm_error;

	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
		 ("Evaluating SPF record"));
	for (i = 0; i < termc; i++) {
		tp = &termv[i];
		
		if (expand_term_arg(dat, tp, &parg)) {
			result = spf_perm_error;
			break;
		}
		    
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
			 ("SPF TERM: %s", tp->expr));
		switch (tp->handler(dat, parg, tp->masklen)) {
		case spf_term_match:
			match = tp->expr;
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
				 ("term matched"));
			result = tp->qualifier;
			break;

		case spf_term_nomatch:
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
				 ("term did not match"));
			continue;

		case spf_term_exception:
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE1,
				 ("term threw exception: %s",
			       spf_result_str[dat->result]));
			result = dat->result;
			break;
		}
		break;
	}

	if (match)
		spf_answer_add_mech(dat->answer, match);
	
	if (!match && (tp = dat->mod[SPF_MOD_REDIRECT])->handler) {
		if (expand_term_arg(dat, tp, &parg)) 
			result = spf_perm_error;
		else {
			spf_answer_add_mech(dat->answer, tp->expr);
			if (tp->handler(dat, parg, tp->masklen)
			    == spf_term_exception) 
				result = dat->result;
			else if (dat->answer)
				free(dat->answer->mechv[--dat->answer->mechn]);
		}
	} else if (result == spf_fail
		   && (tp = dat->mod[SPF_MOD_EXP])->handler) {
		if (expand_term_arg(dat, tp, &parg))
			result = spf_perm_error;
		else
			tp->handler(dat, parg, tp->masklen);
	}

	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,
		 ("result = %s", spf_result_str[result]));
	return result;
}

#define POSTMASTER_PFX "postmaster@"

static spf_result
spf_exec_query(char *rec, struct spf_data *dat)
{
	if (!strchr(dat->q.sender, '@')) {
		mu_opool_append(dat->tmpool, POSTMASTER_PFX,
				sizeof(POSTMASTER_PFX) - 1);
		dat->q.sender = mu_opool_dup(dat->tmpool, dat->q.sender,
					     strlen(dat->q.sender) + 1);
	}

	return spf_eval_record(rec, dat);
}

spf_result
spf_test_record(const char *rec, spf_query_t *q, spf_answer_t *a)
{
	struct spf_data dat;
	spf_result result;
	
	mu_debug(MF_SOURCE_SPF,
		 MU_DEBUG_TRACE0,
		 ("SPF record: %s, ip=%s, domain=%s, sender=%s",
		  rec, q->ipstr, q->domain, q->sender));

	if (a)
		memset(a, 0, sizeof *a);
	if (spf_data_init(&dat, q, a, 0))
		return spf_perm_error;

	result = spf_exec_query(mu_opool_dup(dat.tmpool, rec, strlen(rec) + 1),
				&dat);

	spf_data_free(&dat);

	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,
		 ("result = %s", spf_result_str[result]));

	return result;
}	

/* Implementation of check_host() function. RFC 4408, 4. */
spf_result
spf_check_host_internal(spf_query_t *q, spf_answer_t *a, size_t loopno)
{
	char *txt_rec[SPF_MAX_TXT_REC+1];
	int ntxt, i;
	struct spf_data dat;
	spf_result result;
#define SPF_RETURN(res, text) {						\
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,		\
		      ("check_host(%s, %s, %s) = %s; %s",		\
		       q->ipstr, q->domain, q->sender,			\
		       spf_result_str[res],				\
		       text));						\
		return res; }
	unsigned long ttl;

	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,
		 ("check_host(%s, %s, %s)",
		  q->ipstr, q->domain, q->sender));

	if (loopno > SPF_MAX_RECURSION) {
		mu_debug(MF_SOURCE_SPF, MU_DEBUG_ERROR,
			 ("SPF recursion limit reached"));
		return spf_perm_error;
	}
	
	if (a)
		memset(a, 0, sizeof *a);
	if (strlen(q->domain) > 63) 
		SPF_RETURN(spf_none, "domain too long");
	
	switch (spf_lookup(q->domain, txt_rec, NELEMS(txt_rec),
			   &ttl, NULL, 0)) {
	case dns_success:
		break;

	case dns_not_found:
	case dns_failure:
		SPF_RETURN(spf_none,
			   "invalid domain or no SPF records published");

	case dns_temp_failure:
		SPF_RETURN(spf_temp_error, "DNS temporary failure");
	}

	/* Select SPF1 records */
	ntxt = 0;
	for (i = 0; txt_rec[i]; i++) {
		if (memcmp(txt_rec[i], "v=spf1", 6) == 0
		    && (txt_rec[i][6] == 0 || mu_isspace(txt_rec[i][6]))) {
			mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE6,
				 ("record: %s", txt_rec[i]));
			if (ntxt != i) {
				txt_rec[ntxt++] = txt_rec[i];
				txt_rec[i] = NULL;
			} else
				ntxt = i + 1;
		} else {
			free(txt_rec[i]);
			txt_rec[i] = NULL;
		}
	}

	if (ntxt == 0) 
		SPF_RETURN(spf_none, "no SPF records published");
	if (ntxt > 1)
		SPF_RETURN(spf_perm_error, "too many SPF records published");
	
	mu_debug(MF_SOURCE_SPF, MU_DEBUG_TRACE0,
		 ("SPF record: %s", txt_rec[0]));

	if (a)
		UPDATE_TTL(a->ttl, ttl);
	if (spf_data_init(&dat, q, a, loopno + 1))
		SPF_RETURN(spf_perm_error, "spf_data_init failed");
	
	result = spf_exec_query(txt_rec[0], &dat);
	
	spf_data_free(&dat);
	free(txt_rec[0]);

	SPF_RETURN(result, "");
}

spf_result
spf_check_host(spf_query_t *q, spf_answer_t *a)
{
	return spf_check_host_internal(q, a, 0);
}

void
spf_answer_free(spf_answer_t *ans)
{
	size_t i;
	
	free(ans->exp_text);
	for (i = 0; i < ans->mechn; i++)
		free(ans->mechv[i]);
	free(ans->mechv);
}

void
spf_answer_add_mech(spf_answer_t *ans, char const *mech)
{
	if (!ans)
		return;
	if (ans->mechn == ans->mechmax) {
		if (ans->mechmax == 0)
			ans->mechmax = SPF_MAX_RECURSION;
		ans->mechv = mu_2nrealloc(ans->mechv,
					  &ans->mechmax,
					  sizeof(ans->mechv[0]));
	}
	ans->mechv[ans->mechn++] = mu_strdup(mech);
}