/*
-------------------------------------------------------------------------------
By Bob Jenkins, March 2003.  Public domain.

jenny.c -- jennyrate tests from m dimensions of features that cover all
  n-tuples of features, n<m, with each feature chosen from a different 
  dimension.  For example, given 10 dimensions (m=10) with 2 to 8 features
  apiece, cover all feature triplets (n=3).  A lower bound on the number
  of tests required is the product of the sizes of the largest n dimensions.
  Already-written tests can be piped in to be reused.

Arguments
  Arguments without a leading '-' : an integer in 2..52.  Represents a
  dimension.  Dimensions are implicitly numbered 1..65535, in the order
  they appear.  Features in dimensions are always implicitly given
  1-character names, which are in order a..z, A..Z .  It's a good idea
  to pass the output of jenny through a postprocessor that expands these names
  into something intelligible.

  -o : old.  -ofoo.txt reads existing tests from the file foo.txt, includes
       those tests in the output, and adds whatever other tests are needed to
       complete coverage.  An error is reported if the input tests are of the
       wrong shape or contain disallowed feature interactions.

  -h : help.  Print out instructions for using jenny.

  -n : an integer.  Cover all n-tuples of features, one from each dimension.
       Default is 2 (pairs).  3 (triplets) may be reasonable.  4 (quadruplets)
       is definitely overkill.  n > 4 is highly discouraged.

  -s : seed.  An integer.  Seed the random number generator.

  -w : without this combination of features.  A feature is given by a dimension
       number followed by a one-character feature name.  A single -w can
       disallow multiple features in a dimension.  For example, -w1a2cd4ac
       disallows the combinations (1a,2c,4a),(1a,2c,4c),(1a,2d,4a),(1a,2d,4c)
       where 1a represents the first dimension's first feature, 2c is the 
       second dimension's third feature, and 4a is the fourth dimension's
       first feature.

Example: 10 dimensions of 2, 3, 8, 3, 2, 2, 5, 3, 2, 2 features apiece,
with some restrictions, asking for all triplets of features to be covered.
This will produce at least 8*5*3=120 tests.  Splitting the 8 features in the
third dimension into three dimensions each of length 2 would reduce the
number of testcases required to at least 5*3*3=45.

  jenny -n3 2 3 8 -w1a2bc3b -w1b3a 3 -w1a4b 2 2 5 3 2 2 -w9a10b -w3a4b -s3
-------------------------------------------------------------------------------
*/

#include <stdio.h>
#include <stddef.h>

char *bob_malloc( size_t len)
{
  return (char *)malloc(len);
}

void bob_free( char *x)
{
  free(x);
}

/*
-------------------------------------------------------------------------------
Implementation:

Internally, there can be 64K dimensions with 64K features apiece.  Externally,
the number of features per dimensions is limited to just 52, and are implicitly
named a..z, A..Z.  Other printable characters, like |, caused trouble in the
shell when I tried to give them during a without.

The program first finds tests for all features, then adds tests to cover
all pairs of features, then all triples of features, and so forth up to
the tuples size the user asked for.
-------------------------------------------------------------------------------
*/

/*
-------------------------------------------------------------------------------
Structures
-------------------------------------------------------------------------------
*/

typedef  unsigned char      ub1;
typedef  unsigned short     ub2;
typedef  signed   short     sb2;
typedef  unsigned long      ub4;
typedef  signed   long      sb4;
typedef  unsigned long long ub8;
typedef  signed   long long sb8;
#define TRUE  1
#define FALSE 0
#define UB4MAXVAL 0xffffffff
#define UB2MAXVAL 0xffff

/*
-------------------------------------------------------------------------------
Random number stuff
-------------------------------------------------------------------------------
*/

#define RAND_SIZE 256
typedef  struct randctx {
  ub4 b,c,d,z;                                             /* special memory */
  ub4 m[RAND_SIZE];                             /* big random pool of memory */
  ub4 r[RAND_SIZE];                                               /* results */
  ub4 q;                     /* counter, which result of r was last reported */
} randctx;

/* Pseudorandom numbers, courtesy of FLEA */
void rand_batch( randctx *x) {
  ub4 a, b=x->b, c=x->c+(++x->z), d=x->d, i, *m=x->m, *r=x->r;
  for (i=0; i<RAND_SIZE; ++i) {
    a = m[b % RAND_SIZE];
    m[b % RAND_SIZE] = d;
    d = (c<<19) + (c>>13) + b;
    c = b ^ m[i];
    b = a + d;
    r[i] = c;
  }
  x->b=b; x->c=c; x->d=d;
}

ub4 rand( randctx *x) {
  if (!x->q--) {
    x->q = RAND_SIZE-1;
    rand_batch(x);
  }
  return x->r[x->q];
}

void rand_init( randctx *x, ub4 seed) {
  ub4    i;

  x->b = x->c = x->d = x->z = seed;
  for (i = 0; i<RAND_SIZE; ++i) {
    x->m[i] = seed;
  }
  for (i=0; i<10; ++i) {
    rand_batch(x);
  }
  x->q = 0;
}




/*
------------------------------------------------------------------------------
Other helper routines
------------------------------------------------------------------------------
*/

#define TUPLE_ARRAY  5040       /* tuple array size, multiple of 1,2,3,4,5,6 */

/* An arbitrary feature, prefix fe */
typedef  struct feature {
  ub2    d;                                                /* Dimension name */
  ub2    f;                                                  /* Feature name */
} feature;

/* a tuple array, prefix tu */
typedef  struct tu_arr {
  struct tu_arr  *next;                                  /* next tuple array */
  ub2             len;                               /* length of this array */
  feature         fe[TUPLE_ARRAY];                        /* array of tuples */
} tu_arr;

/* an iterator over a tuple array, prefix tu */
typedef  struct tu_iter {
  struct tu_arr **tu;                                 /* current tuple array */
  ub2             offset;                         /* offset of current tuple */
  ub2             n;                         /* number of features per tuple */
  ub4            *count;                         /* number of tuples in list */
  feature        *fe;                                       /* current tuple */
} tu_iter;

/* names of features, for output */
static const char feature_name[] =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

/* insert a tuple into a tuple array */
int insert_tuple( tu_iter *ctx, feature *tuple)
{
  ub4      i;
  feature *fe;
  ub1      n = ctx->n;
  ub4      lim = TUPLE_ARRAY / n;

  while (*ctx->tu && (*ctx->tu)->len == lim) {
    ctx->tu = &((*ctx->tu)->next);
  }
  if (!*ctx->tu) {
    if (!((*ctx->tu) = (tu_arr *)bob_malloc(sizeof(tu_arr)))) {
      return FALSE;
    }
    (*ctx->tu)->len = 0;
    (*ctx->tu)->next = (tu_arr *)0;
  }
  fe = &(*ctx->tu)->fe[(*ctx->tu)->len*n];
  for (i=0; i<n; ++i) {
    fe[i].d = tuple[i].d;
    fe[i].f = tuple[i].f;
  }
  ++(*ctx->tu)->len;
  ++*ctx->count;
  return TRUE;
}

/* print out a single tuple */
void show_tuple( feature *fe, ub2 len)
{
  ub4 i;
  for (i=0; i<len; ++i) {
    printf(" %d%c", fe[i].d+1, feature_name[fe[i].f]);
  }
  printf(" \n");
}

/* delete a tuple from a tuple array */
feature *delete_tuple( tu_iter *ctx)
{
  feature *fe;
  ub4      i;
  feature *tuple = ctx->fe;
  ub1      n = ctx->n;

  --(*ctx->tu)->len;
  --*ctx->count;
  fe = &(*ctx->tu)->fe[(*ctx->tu)->len * n];
  for (i=0; i<n; ++i) {
    tuple[i].d = fe[i].d;
    tuple[i].f = fe[i].f;
  }
  if (!(*ctx->tu)->len) {
    tu_arr *tu2 = *ctx->tu;
    *ctx->tu = ((*ctx->tu)->next);
    bob_free((char *)tu2);
  }

  if (!*ctx->tu) {                                   /* freed the last block */
    ctx->offset = 0;
    ctx->fe = (feature *)0;
    return ctx->fe;
  } else if (tuple == fe) {
    ctx->offset = 0;
    ctx->fe = &(*ctx->tu)->fe[0];          /* freed this block, move to next */
    return ctx->fe;
  } else {
    return tuple;                 /* moved a new tuple into the old location */
  }
}

/* start a tuple iterator */
feature *start_tuple( tu_iter *ctx, tu_arr **tu, ub4 n, ub4 *count)
{
  ctx->tu = tu;
  ctx->offset = 0;
  ctx->n = n;
  ctx->count = count;

  if (*tu) {
    ctx->fe = (*tu)->fe;
  } else {
    ctx->fe = (feature *)0;
  }
  return ctx->fe;
}

/* get the next tuple from a tuple iterator (0 if no more tuples) */
static feature *next_tuple( tu_iter *ctx)
{
  if (++ctx->offset < (*ctx->tu)->len) {
    ctx->fe += ctx->n;
  } else {
    ctx->tu = &(*ctx->tu)->next;
    ctx->offset = 0;
    if (*ctx->tu && (*ctx->tu)->len) {
      ctx->fe = (*ctx->tu)->fe;
    } else {
      ctx->fe = (feature *)0;
    }
  }
  return ctx->fe;
}


/* test if this test covers this tuple */
static int test_tuple( ub2 *test, feature *tuple, ub2 n)
{
  sb4 i;
  for (i=0; i<n; ++i) {
    if (tuple[i].f != test[tuple[i].d]) {
      return FALSE;
    }
  }
  return TRUE;
}

/* test if first tuple (t1, n1) is a subset of second tuple (t2, n2) */
int subset_tuple( feature *t1, ub1 n1, feature *t2, ub1 n2)
{
  sb4 i, j;
  if (n2 < n1)
    return FALSE;
  for (i=0, j=0; i<n1; ++i) {
    while (t1[i].d > t2[j].d) {
      if (++j == n2)
	return FALSE;
    }
    if (t1[i].d != t2[j].d || t1[i].f != t2[j].f) {
      return FALSE;
    }
  }
  return TRUE;
}



/*
------------------------------------------------------------------------------
Stuff specific to jenny
------------------------------------------------------------------------------
*/

#define MAX_FEATURES 52                  /* can't name more than 52 features */
#define MAX_N        32       /* never can do complete coverage of 33-tuples */
#define MAX_WITHOUT  (MAX_FEATURES*MAX_N)       /* max features in a without */
#define MAX_DIMENSIONS (((ub2)~0)-1) /* More than 64K dimensions needs a ub4 */

/* A "test", which is a combination of features.  Prefix t. */
typedef  struct test {
  struct test *next;                                            /* next test */
  ub2         *f;                                   /* features in this test */
} test;

/* representation of a restriction, prefix w */
typedef  struct without {
  ub2             len;                            /* length of feature array */
  struct feature *fe;                                       /* feature array */
} without;

/* without chain */
typedef  struct wchain {
  without       *w;
  struct wchain *next;
} wchain;


/* Return a count of how many withouts are disobeyed. */
/* Also set a pointer to a randomly chosen violated without */
int count_withouts(
test     *t,                                                /* test to check */
wchain   *wc)                                                /* restrictions */
{
  ub4      count;                             /* count of disobeyed withouts */

  for (count = 0; wc; wc = wc->next) {
    without *w = wc->w;
    ub4      i = 0;
    int      match = TRUE;                   /* match the entire restriction */
    while (i<w->len) {
      int dimension_match = FALSE;                /* match in this dimension */
      do {
	if (t->f[w->fe[i].d] == w->fe[i].f) {
	  dimension_match = TRUE;
	}
	++i;
      } while (i<w->len && (w->fe[i].d == w->fe[i-1].d));
      if (!dimension_match) {
	match = FALSE;
	break;
      }
    }
    if (match) {
      ++count;
    }
  }
  return count;
}


/* token definitions */
typedef enum token_type {
  TOKEN_ERROR = 0,                                /* TOKEN_ERROR has to be 0 */
  TOKEN_END,
  TOKEN_NUMBER,
  TOKEN_FEATURE,
  TOKEN_SPACE
} token_type;


/* whole current state, prefix s */
typedef  struct state {
  ub1       n_final;           /* The n in the user's n-tuples, default is 2 */
  ub1     **n;  /* n[d][f] is current n-tuple size for dimension d feature f */
  ub2       ndim;                                    /* number of dimensions */
  ub2       ntests;                                  /* number of tests in t */
  ub2      *dim;                     /* number of features in each dimension */
  wchain  **wc;                   /* s->wc[d] lists withouts for dimension d */
  wchain   *wc2;                      /* a list of all the original withouts */
  wchain   *wc3;                             /* additional, deduced withouts */
  tu_arr ***tu;  /* tu[d][f] lists untested tuples for dimension d feature f */
  ub4     **tc;   /* tc[d][f] is # untested tulpes for dimension d feature f */
  test     *t;                             /* all the tests generated so far */
  test     *tuple_tester;   /* an all -1 test used to test individual tuples */
  ub2      *dimord;                   /* order in which to choose dimensions */
  ub2      *featord;                    /* order in which to choose features */
  randctx   r;                                      /* random number context */
} state;

void initialize( state *s)
{
  /* make all freeable pointers start out zero */
  s->dim          = (ub2 *)0;
  s->wc           = (wchain **)0;
  s->wc2          = (wchain *)0;
  s->wc3          = (wchain *)0;
  s->tu           = (tu_arr ***)0;
  s->n            = (ub1 **)0;
  s->tc           = (ub4 **)0;
  s->t            = (test *)0;
  s->tuple_tester = (test *)0;
  s->dimord       = (ub2 *)0;
  s->featord      = (ub2 *)0;

  /* fill in default values */
  s->ndim = (ub2)0;
  s->n_final = 2;     /* guarantees that all pairs of dimensions are covered */
  s->ntests = 0;
  rand_init(&s->r, 0);                 /* initialize random number generator */
}


void cleanup(state *s)
{
  if (s->tu) {
    ub2 d,f;
    for (d=0; d<s->ndim; ++d) {
      if (s->tu[d]) {
	for (f=0; f<s->dim[d]; ++f) {
	  while (s->tu[d][f]) {
	    tu_arr *tu2 = s->tu[d][f];
	    s->tu[d][f] = tu2->next;
	    bob_free((char *)tu2);
	  }
	}
	bob_free((char *)s->tu[d]);
      }
    }
    bob_free((char *)s->tu);
  }

  /* free n, the tuple lengths */
  if (s->n) {
    ub2 d;
    for (d=0; d<s->ndim; ++d) {
      if (s->n[d]) {
	bob_free((char *)s->n[d]);
      }
    }
    bob_free((char *)s->n);
  }

  /* free tc, count of uncovered tuples */
  if (s->tc) {
    ub2 d;
    for (d=0; d<s->ndim; ++d) {
      if (s->tc[d]) {
	bob_free((char *)s->tc[d]);
      }
    }
    bob_free((char *)s->tc);
  }

  /* free the secondary chains of restrictions */
  if (s->wc) {
    ub2 i;
    for (i=0; i<s->ndim; ++i) {
      while (s->wc[i]) {
	wchain  *wc = s->wc[i];
	s->wc[i] = s->wc[i]->next;
	bob_free((char *)wc);
      }
    }
    bob_free((char *)s->wc);
  }

  /* free all the actual restrictions */
  while (s->wc2) {
    wchain  *wc = s->wc2;
    without *w = wc->w;
    s->wc2 = s->wc2->next;
    if (w->fe) bob_free((char *)w->fe);
    bob_free((char *)w);
    bob_free((char *)wc);
  }

  while (s->wc3) {
    wchain  *wc = s->wc3;
    without *w = wc->w;
    s->wc3 = s->wc3->next;
    if (w->fe) bob_free((char *)w->fe);
    bob_free((char *)w);
    bob_free((char *)wc);
  }

  while (s->t) {
    test *t = s->t;
    s->t = s->t->next;
    if (t->f) {
      bob_free((char *)t->f);
    }
    bob_free((char *)t);
  }

  if (s->tuple_tester) {
    if (s->tuple_tester->f) {
      bob_free((char *)s->tuple_tester->f);
    }
    bob_free((char *)s->tuple_tester);
  }

  if (s->dimord) {
    bob_free((char *)s->dimord);
  }

  if (s->featord) {
    bob_free((char *)s->featord);
  }

  /* free the array of dimension lengths */
  if (s->dim) bob_free((char *)s->dim);
}


char *my_alloc( state *s, size_t len)
{
  char *rsl;
  if (!(rsl = (char *)bob_malloc(len))) {
    printf("jenny: could not allocate space\n");
    cleanup(s);
    exit(0);  
  }
  return rsl;
}

/* add one test to the list of tests */
void add_test( state *s, test *t)
{
  test **tp;
  for (tp = &s->t; *tp; tp = &(*tp)->next)
    ;
  t->next = (test *)0;
  *tp = t;
  ++s->ntests;
}

/*
 * parse a token
 * Start at *curr in string *inp of length inl
 * Adjust *curr to be after the just-parsed token
 * Place the token value in *rsl
 * Return the token type
 */
token_type parse_token(char *inp, ub4 inl, ub4 *curr, ub4 *rsl)
{
  char mychar;
  ub4  i;

  if (*curr == inl)
    return TOKEN_END;
  mychar = inp[*curr];

  if (mychar == '\0') {
    return TOKEN_END;
  } else if (mychar == ' ' || mychar == '\t' || mychar == '\n') {
    /*--------------------------------------------------------- parse spaces */
    for (i=*curr+1; i < inl; ++i) {
      mychar = inp[i];
      if (!(mychar == ' ' || mychar == '\t' || mychar == '\n'))
	break;
    }
    *curr = i;
    return TOKEN_SPACE;
  } else if (mychar >= '0' && mychar <= '9') {
    /*------------------------------------------------------- parse a number */
    ub4 i, number = 0;
    for (i=*curr; i < inl && inp[i] >= '0' && inp[i] <= '9';  ++i) {
      number = number*10 + (inp[i] - '0');
    }
    *curr = i;
    *rsl = number;
    return TOKEN_NUMBER;
  } else if ((mychar >= 'a' && mychar <= 'z') ||
	     (mychar >= 'A' && mychar <= 'Z')) {
    /*------------------------------------------------- parse a feature name */
    ub4 i;
    for (i=0; i<MAX_FEATURES; ++i)
      if (feature_name[i] == mychar)
	break;
    if (i == MAX_FEATURES) {
      printf("jenny: the name '%c' is not used for any feature\n",
	     mychar);
	return TOKEN_ERROR;
    }
    *rsl = i;
    ++*curr;
    return TOKEN_FEATURE;
  } else {
    return TOKEN_ERROR;
  }
}

#define BUFSIZE (MAX_DIMENSIONS*7+2)
/* load old tests before generating new ones */
int load( state *s, char *testfile)
{
  char  buf[BUFSIZE];            /* buffer holding a line read from the file */
  FILE *f;
  
  if (testfile[0] == '\0') {
    f = stdin;
  } else {
    f = fopen(testfile, "r");
  }

  if (!f) {
    printf("jenny: file %s could not be opened\n", testfile);
    return FALSE;
  }

  while (fgets(buf, BUFSIZE, f) && (buf[0] != '.')) {
    ub4   curr = 0;                               /* current offset into buf */
    ub4   value;                                              /* token value */
    token_type token;                                          /* token type */
    ub4   i;
    test *t;

    t = (test *)my_alloc( s, sizeof(test));
    t->f = (ub2 *)my_alloc( s, sizeof(ub2)*s->ndim);
    add_test(s, t);

    for (i=0; i<s->ndim; ++i) {
      if (parse_token(buf, UB4MAXVAL, &curr, &value) != TOKEN_SPACE) {
	printf("jenny: -o, non-space found where space expected\n");
	goto failure;
      }
      if (parse_token(buf, UB4MAXVAL, &curr, &value) != TOKEN_NUMBER) {
	printf("jenny: -o, non-number found where number expected\n");
	goto failure;
      }
      if (value-1 != i) {
	printf("jenny: -o, number %d found out-of-place\n", value);
	goto failure;
      }
      if (parse_token(buf, UB4MAXVAL, &curr, &value) != TOKEN_FEATURE) {
	printf("jenny: -o, non-feature found where feature expected\n");
	goto failure;
      }
      if (value >= s->dim[i]) {
	printf("jenny: -o, feature %c does not exist in dimension %d\n", 
	       feature_name[value], i+1);
	goto failure;
      }
      t->f[i] = value;
    }
    if (parse_token(buf, UB4MAXVAL, &curr, &value) != TOKEN_SPACE) {
      printf("jenny: -o, non-space found where trailing space expected\n");
      goto failure;
    }
    if (parse_token(buf, UB4MAXVAL, &curr, &value) != TOKEN_END) {
      printf("jenny: -o, testcase not properly terminated\n");
      goto failure;
    }

    /* make sure the testcase obeys all the withouts */
    if (count_withouts(t, s->wc2)) {
      printf("jenny: -o, old testcase contains some without\n");
      goto failure;
    }
  }

  (void)fclose(f);
  return TRUE;

 failure:
  while (fgets(buf, BUFSIZE, f) && (buf[0] != '.'))
    ;                                            /* finish reading the input */
  (void)fclose(f);                                         /* close the file */
  return FALSE;
}

static const ub1 *jenny_doc[] = {
  "jenny:\n",
  "  Given a set of feature dimensions and withouts, produce tests\n",
  "  covering all n-tuples of features where all features come from\n",
  "  different dimensions.  For example (=, <, >, <=, >=, !=) is a\n",
  "  dimension with 6 features.  The type of the left-hand argument is\n",
  "  another dimension.  Dimensions are numbered 1..65535, in the order\n",
  "  they are listed.  Features are implicitly named a..z, A..Z.\n",
  "   3 Dimensions are given by the number of features in that dimension.\n",
  "  -h prints out these instructions.\n",
  "  -n specifies the n in n-tuple.  The default is 2 (meaning pairs).\n",
  "  -w gives withouts.  -w1b4ab says that combining the second feature\n",
  "     of the first dimension with the first or second feature of the\n",
  "     fourth dimension is disallowed.\n",
  "  The output is a test per line, one feature per dimension per test,\n",
  "  followed by the list of all allowed tuples that jenny could not\n",
  "  reach.\n",
  "\n",
  "  Example: jenny -n3 3 2 2 -w2b3b 5 3 -w1c3b4ace5ac 8 2 2 3 2\n",
  "  This gives ten dimensions, asks that for any three dimensions all\n",
  "  combinations of features (one feature per dimension) be covered,\n",
  "  plus it asks that certain combinations of features\n",
  "  (like (1c,3b,4c,5c)) not be covered.\n",
  "\n"
};


/* parse -n, the tuple size */
int parse_n( state *s, char *myarg)
{
  ub4 curr = 0;
  ub4 temp = UB4MAXVAL;
  token_type token;
  ub4 dummy;

  if ((token=parse_token(myarg, UB4MAXVAL, &curr, &temp)) != TOKEN_NUMBER) {
    printf("jenny: -n should give an integer in 1..32, for example, -n2.\n");
    return FALSE;
  }
  if ((token=parse_token(myarg, UB4MAXVAL, &curr, &dummy)) != TOKEN_END) {
    printf("jenny: -n should be followed by just an integer\n");
    return FALSE;
  }
  
  if ((temp < 1) || (temp > 32)) {
    printf("jenny: -n says all n-tuples should be covered.\n");
    return FALSE;
  }
  if (temp > s->ndim) {
    printf("jenny: -n, %ld-tuples are impossible with only %d dimensions\n",
	   temp, s->ndim);
    return FALSE;
  }
  s->n_final = (ub2)temp;
  return TRUE;
}



/* parse -w, a without */
int parse_w( state *s, ub1 *myarg)
{
  without   *w;
  wchain    *wc;
  feature    fe[MAX_WITHOUT];
  ub1        used[MAX_DIMENSIONS];
  ub4        dimension_number;
  ub4        curr = 0;
  ub4        fe_len, value;
  ub4        i, j, k;
  size_t     len = strlen(myarg);
  token_type t = parse_token(myarg, len, &curr, &value);
  
 start:
  for (i=0; i<s->ndim; ++i)
    used[i] = FALSE;
  if (t != TOKEN_NUMBER) {
    printf("jenny: -w is <number><features><number><features>...\n");
    printf("jenny: -w must start with an integer (1 to #dimensions)\n");
    return FALSE;
  }
  fe_len=0;
  
 number:
  dimension_number = --value;
  if (dimension_number >= s->ndim) {
    printf("jenny: -w, dimension %ld does not exist, ", dimension_number+1);
    printf("you gave only %d dimensions\n", s->ndim);
    return FALSE;
  }
  if (used[dimension_number]) {
    printf("jenny: -w, dimension %d was given twice in a single without\n",
	   dimension_number+1);
    return FALSE;
  }
  used[dimension_number] = TRUE;
  
  
  switch (parse_token(myarg, len, &curr, &value)) {
  case TOKEN_FEATURE: goto feature;
  case TOKEN_END:
    printf("jenny: -w, withouts must follow numbers with features\n");
    return FALSE;
  default:
    printf("jenny: -w, unexpected without syntax\n");
    printf("jenny: proper withouts look like -w2a1bc99a\n");
    return FALSE;
  }
  
 feature:
  if (value >= s->dim[dimension_number]) {
    printf("jenny: -w, there is no feature '%c' in dimension %d\n",
	   feature_name[value], dimension_number+1);
    return FALSE;
  }
  fe[fe_len].d = dimension_number;
  fe[fe_len].f = value;
  if (++fe_len >= MAX_WITHOUT) {
    printf("jenny: -w, at most %d features in a single without\n",
	   MAX_WITHOUT);
    return FALSE;
  }

  
  switch (parse_token(myarg, len, &curr, &value)) {
  case TOKEN_FEATURE: goto feature;
  case TOKEN_NUMBER: goto number;
  case TOKEN_END: goto end;
  default:
    printf("jenny: -w, unexpected without syntax\n");
    printf("jenny: proper withouts look like -w2a1bc99a\n");
    return FALSE;
  }
  
 end:

  /* sort the dimensions and features in this restriction */
  for (i=0; i<fe_len; ++i) {
    for (j=i+1; j<fe_len; ++j) {
      if ((fe[i].d > fe[j].d) ||
	  ((fe[i].d == fe[j].d) && (fe[i].f > fe[j].f))) {
	ub2 fe_temp;
	fe_temp = fe[i].d;
	fe[i].d = fe[j].d;
	fe[j].d = fe_temp;
	fe_temp = fe[i].f;
	fe[i].f = fe[j].f;
	fe[j].f = fe_temp;
      }
    }
  }

  /* allocate a without */
  w = (without *)my_alloc( s, sizeof(without));
  wc = (wchain *)my_alloc( s, sizeof(wchain));
  wc->next = s->wc2;
  wc->w = w;
  w->len = fe_len;
  w->fe = (feature *)my_alloc( s, sizeof(feature)*fe_len);
  for (i=0; i<fe_len; ++i) {
    w->fe[i].d = fe[i].d;
    w->fe[i].f = fe[i].f;
  }
  s->wc2 = wc;

  return TRUE;
}

/* parse -s, a seed for the random number generator */
int parse_s( state *s, ub1 *myarg)
{
  ub4 seed = 0;
  ub4 dummy = 0;
  ub4 curr = 0;
  if (parse_token( myarg, UB4MAXVAL, &curr, &seed) != TOKEN_NUMBER) {
    printf("jenny: -s must be followed by a positive integer\n");
    return FALSE;
  }
  if (parse_token( myarg, UB4MAXVAL, &curr, &dummy) != TOKEN_END) {
    printf("jenny: -s should give just an integer, example -s123\n");
    return FALSE;
  }
  rand_init(&s->r, seed);          /* initialize random number generator */
  return TRUE;
}

/* parse the inputs */
int parse( int argc, char *argv[], state *s)
{
  int   i, j;
  ub4   temp;
  char *testfile = (char *)0;

  /* internal check: we have MAX_FEATURES names for features */
  if (strlen(feature_name) != MAX_FEATURES) {
    printf("feature_name length is wrong, %d\n", strlen(feature_name));
    return FALSE;
  }

  /* How many dimensions are there?  Set ndim, allocate space for dim.  */
  for (temp=0, i=1; i<argc; ++i) {
    if (argv[i][0] >= '0' && argv[i][0] <= '9') {
      ++temp;
    }
  }
  if (temp > MAX_DIMENSIONS) {
    printf("jenny: maximum number of dimensions is %ld.  %ld is too many.\n",
	   MAX_DIMENSIONS, temp);
    return FALSE;
  }
  s->ndim = (ub2)temp;
  s->dim = (ub2 *)my_alloc( s, sizeof(ub2)*(s->ndim));

  /* Read the lengths of all the dimensions */
  for (i=1, j=0; i<argc; ++i) {
    if (argv[i][0] >= '0' && argv[i][0] <= '9') {        /* dimension length */
      ub1 *myarg = argv[i];
      ub4  dummy;
      ub4  curr = 0;

      (void)parse_token(myarg, UB4MAXVAL, &curr, &temp);
      if (parse_token(myarg, UB4MAXVAL, &curr, &dummy) != TOKEN_END) {
	printf("jenny: something was trailing a dimension number\n");
	return FALSE;
      }
      if (temp > MAX_FEATURES) {
	printf("jenny: dimensions must be smaller than %d.  %ld is too big.\n",
	       MAX_FEATURES, temp);
	return FALSE;
      }
      if (temp < 2) {
	printf("jenny: a dimension must have at least 2 features, not %d\n",
	       temp);
	return FALSE;
      }
      s->dim[j++] = (ub2)temp;
    } else if (argv[i][1] == 'h') {
      int i;
      for (i=0; i<(sizeof(jenny_doc)/sizeof(ub1 *)); ++i) {
	printf(jenny_doc[i]);
      }
      return FALSE;
    }
  }

  /* Read the rest of the arguments */
  for (i=1; i<argc; ++i) if (argv[i][0] == '-') {        /* dimension length */
    switch(argv[i][1]) {
    case '\0':
      printf("jenny: '-' by itself isn't a proper argument.\n");
      return FALSE;
    case 'o':                               /* -o, file containing old tests */
      testfile = &argv[i][2];
      break;
    case 'n':                       /* -n, get the n of "cover all n-tuples" */
      if (!parse_n( s, &argv[i][2])) return FALSE;
      break;
    case 'w':                                /* -w, "without", a restriction */
      if (!parse_w( s, &argv[i][2])) return FALSE;
      break;
    case 's':                           /* -s, "random", change the behavior */
      if (!parse_s( s, &argv[i][2])) return FALSE;
      break;
    default:
      printf("jenny: legal arguments are numbers, -n, -s, -w, -h, not -%c\n",
	     argv[i][1]);
      return FALSE;
    }
  }                                            /* for (each argument) if '-' */

  if (s->n_final > s->ndim) {
    printf("jenny: %ld-tuples are impossible with only %d dimensions\n",
	   s->n_final, s->ndim);
    return FALSE;
  }

  /* read in any old tests so we can build from that base */
  if (testfile) {
    if (!load( s, testfile)) {
      return FALSE;
    }
  }

  return TRUE;
}

void preliminary( state *s)
{
  wchain  *wc;
  ub4      d;

  s->tuple_tester = (test *)my_alloc( s, sizeof(test));
  s->tuple_tester->f = (ub2 *)my_alloc( s, sizeof(ub2)*s->ndim);
  s->tuple_tester->next = (test *)0;
  s->dimord  = (ub2 *)my_alloc( s, sizeof(ub2)*s->ndim);
  s->wc = (wchain **)my_alloc( s, sizeof(wchain *)*s->ndim);
  s->tu = (tu_arr ***)my_alloc( s, sizeof(tu_arr **)*s->ndim);
  s->n  = (ub1 **)my_alloc( s, sizeof(ub1 *)*s->ndim);
  s->tc = (ub4 **)my_alloc( s, sizeof(ub4 *)*s->ndim);

  /* initialize to safe values before doing further allocations */
  for (d=0; d<s->ndim; ++d) {
    s->tuple_tester->f[d] = (ub2)~0;
    s->dimord[d] = (ub2)d;
    s->wc[d] = (wchain *)0;
    s->tu[d] = (tu_arr **)0;
    s->n[d] = (ub1 *)0;
    s->tc[d] = (ub4 *)0;
  }

  s->featord = (ub2 *)my_alloc( s, sizeof(ub2)*MAX_FEATURES);

  /* allocate roots for feature-specific lists of uncovered tuples */
  for (d=0; d<s->ndim; ++d) {
    ub2 f;
    s->tu[d] = (tu_arr **)my_alloc( s, sizeof(tu_arr *)*s->dim[d]);
    s->n[d]  = (ub1 *)my_alloc(s, sizeof(ub1)*s->dim[d]);
    s->tc[d] = (ub4 *)my_alloc(s, sizeof(ub4)*s->dim[d]);
    for (f=0; f<s->dim[d]; ++f) {
      s->tu[d][f] = (tu_arr *)0;
      s->n[d][f]  = 0;
      s->tc[d][f] = 0;
    }
  }

  /* make dimension-specific lists of withouts */
  for (wc=s->wc2; wc; wc=wc->next) {
    without *w = wc->w;
    int      old = -1;
    int      i;
    for (i=0; i<w->len; ++i) {
      if (w->fe[i].d != old) {
	wchain *wc = (wchain *)my_alloc( s, sizeof(wchain));
	wc->w = w;
	wc->next = s->wc[w->fe[i].d];
	s->wc[w->fe[i].d] = wc;
	old = w->fe[i].d;
      }
    }
  }
}

/* print out a single test */
void report( test *t, ub2 len)
{
  ub4 i;
  for (i=0; i<len; ++i) {
    printf(" %d%c", i+1, feature_name[t->f[i]]);
  }
  printf(" \n");
}

/* print out all the tests */
void report_all( state *s)
{
  test *tp;
  for (tp = s->t; tp; tp = tp->next) {
    report(tp, s->ndim);
  }
}


void build_tuples( state *s, ub2 d, ub2 f)
{
  feature  offset[MAX_N];
  sb4      i, j, n = s->n[d][f];
  ub8      count = 0;
  test    *t;
  tu_iter  ctx;

  if (s->tc[d][f] > 0 || s->n[d][f] == s->n_final) {
    return;                               /* no need to generate more tuples */
  }

  n = ++s->n[d][f];                        /* move up to a bigger tuple size */

  /* Make a list of allowed but uncovered tuples */
  for (i=0; i<n; ++i) {
    offset[i].d = i;
    offset[i].f = 0;
    start_tuple(&ctx, &s->tu[d][f], n, &s->tc[d][f]);
  }

  for (;;) {
    /* only accept tuples that contain dimension d with feature f */
    /* Slow.  I ought to generate (n-1)-tuples and insert d.f into them */
    for (i=0; i<n; ++i) {
      if (offset[i].d == d && offset[i].f == f)
	break;
    }
    if (i==n)
      goto make_next_tuple;

    for (i=0; i<n; ++i) {
      s->tuple_tester->f[offset[i].d] = offset[i].f;
    }
    if (count_withouts(s->tuple_tester, s->wc2) ||
	count_withouts(s->tuple_tester, s->wc3))
      goto make_next_tuple;

    /* is this tuple covered by the existing tests? */
    for (t=s->t; t; t = t->next) {
      for (i=0; i<n; ++i) {
	if (t->f[offset[i].d] != offset[i].f) {
	  break;
	}
      }
      if (i == n) {
	goto make_next_tuple;
      }
    }

    /* add it to the list of uncovered tuples */
    if (!insert_tuple(&ctx, offset)) {
      printf("jenny: could not insert tuple\n");
      return;
    }
    ++count;

#ifdef NEVER
    printf("missed %d:", n);
    for (i=0; i<n; ++i)
      printf("%d%c ",
	     offset[i].d+1, feature_name[offset[i].f]);
    printf("\n");
#endif

    /* next tuple */
  make_next_tuple:
    for (i=0; i<n; ++i) {
      s->tuple_tester->f[offset[i].d] = (ub2)~0;
    }
    i=s->n[d][f];
    while (i-- &&
	   offset[i].d == s->ndim-n+i &&
	   offset[i].f == s->dim[offset[i].d]-1)
      ;
    if (i == -1)
      break;                                                         /* done */
    else if (offset[i].f < s->dim[offset[i].d]-1) {
      ++offset[i].f;                                    /* increment feature */
      for (i; i<n-1; ++i) {          /* reset all less significant positions */
	offset[i+1].d = offset[i].d+1;
	offset[i+1].f = 0;
      }
    }
    else {
      ++offset[i].d;   /* increment least significant non-maxed-out position */
      offset[i].f = (ub2)0;                             /* reset its feature */
      for (i; i<n-1; ++i) {          /* reset all less significant positions */
	offset[i+1].d = offset[i].d+1;
	offset[i+1].f = 0;
      }
    }
  }
}

/*
 * Tweak the test, other than entries in tuple, so that all withouts are
 * obeyed.
 *
 * Algorithm: loop through all the dimensions touched by any without, changing
 * features in those dimensions so that the total number of withouts disobeyed
 * decreases or stays the same.  Succeed if all withouts are obeyed.  Give up
 * after MAX_NO_PROGRESS consecutive loops that fail to decrease the number of
 * withouts disobeyed.
 *
 * Would it be better to find some disobeyed without, and change one of its
 * dimensions at random?  No.  Consider
 *   jenny 2 2 2 -w1a2a -w1b3a -w1b3a -w2b3a -w2b3a
 * and tentative testcase
 *   1a 2a 3a
 * Progress is impossible unless you change a dimension that is not currently
 * in any disobeyed without.
 */
#define MAX_NO_PROGRESS 2
int obey_withouts(
state *s,                                                    /* global state */
test  *t,                                                /* test being built */
ub1   *mut)              /* mut[i] = 1 if I am allowed to adjust dimension i */
{
  ub4      i;
  without *w;                               /* one of the disobeyed withouts */
  ub4      count;                        /* number of withouts currently hit */
  ub2      ndim;                                         /* size of dimord[] */
  ub2      temp;

  /* how many withouts are currently disobeyed? */
  if (!count_withouts(t, s->wc2))
    return TRUE;

  /* fill dimord[] with all dimensions that can and should be tweaked */
  for (ndim=0, i=0; i<s->ndim; ++i) {
    if (mut[i] && s->wc[i]) {
      s->dimord[ndim++] = i;
    }
  }

  /* hillclimbing, with sidestepping, minimize number of withouts hit */
  for (i=0; i<MAX_NO_PROGRESS; ++i) {
    ub4     j;
    ub2     best[MAX_FEATURES];                      /* best features so far */
    ub1     ok = TRUE;
    
    for (j=ndim; j>0; --j) {
      ub2 fcount = 0;                    /* count of filled elements of best */
      ub2 mydim;                                    /* the current dimension */
      ub2 k;

      /* walk the dimensions in a random order, no replacement */
      mydim = rand(&s->r) % j;
      temp = s->dimord[mydim];
      s->dimord[mydim] = s->dimord[j-1];
      s->dimord[j-1] = temp;
      mydim = s->dimord[j-1];

      /* see how many withouts this dimension is disobeying */
      count = count_withouts(t, s->wc[mydim]);

      /* test every feature of this dimension, trying to make progress */
      for (k=0; k<s->dim[mydim]; ++k) {
	ub2 newcount;
	t->f[mydim] = k;
	newcount = count_withouts(t, s->wc[mydim]);
	if (newcount <= count) {
	  if (newcount < count) {
	    i = 0;                                      /* partial progress! */
	    fcount = 0;
	    count = newcount;
	  }
	  best[fcount++] = k;
	}
      }

      /* choose one of the best features for this dimension at random */
      if (fcount == 0) {
	printf("jenny: internal error a\n");
      } else if (fcount == 1) {
	t->f[mydim] = best[0];
      } else {
	temp = (rand(&s->r) % fcount);
	t->f[mydim] = best[temp];
      }

      if (count > 0)
	ok = FALSE;
    }
    if (ok) {                                       /* no withouts disobeyed */
      return TRUE;
    }
  }
  return FALSE;               /* failure, could not satisfy all the withouts */
}

ub4 count_tuples( state *s, test *t, int d, int f)
{
  ub4      count = 0;
  ub1      n = s->n[d][f];
  tu_iter  ctx;
  feature *this = start_tuple(&ctx, &s->tu[d][f], n, &s->tc[d][f]);
  while (this) {
    count += test_tuple(t->f, this, n);
    this = next_tuple(&ctx);
  }
  return count;
}

ub4 maximize_coverage( 
state *s,                                                    /* global state */
test  *t,            /* testcase being built, already obeys all restrictions */
ub1   *mut,                        /* mut[i] = 1 if I can adjust dimension i */
ub1    n)                            /* size of smallest tuple left to cover */
{
  ub1 progress;
  ub2 ndim;
  ub2 i;
  ub4 total;

  /* build a list of all the dimensions that we can modify */
  for (ndim=0, i=0; i<s->ndim; ++i) {
    if (mut[i]) {
      s->dimord[ndim++] = i;
    }
  }

  /* repeatedly loop through all dimensions, maximizing tuple coverage */
  do {
    progress = FALSE;             /* assume no improvement in tuple coverage */
    total    = 1; /* one, for the one fixed tuple we are guaranteed to cover */

    /* scramble the array of dimensions; */
    for (i=ndim; i>1; --i) {
      ub2 j = rand(&s->r) % i;
      ub2 temp = s->dimord[i-1];
      s->dimord[i-1] = s->dimord[j];
      s->dimord[j] = temp;
    }

    /* for every dimension that we can adjust */
    for (i=0; i<ndim; ++i) {
      ub2 best[MAX_FEATURES];     /* list of features with the best coverage */
      ub2 count = 0;                                       /* size of best[] */
      ub2 d = s->dimord[i];
      ub1 best_n = s->n[d][t->f[d]];
      ub4 coverage = count_tuples(s, t, d, t->f[d]);
      ub4 f;

      /* for every feature in mydim, see if using it would improve coverage */
      for (f=0; f<s->dim[d]; ++f) {
	t->f[d] = f;                            /* switch to the new feature */
	if (!count_withouts(t, s->wc[d])) {         /* need to obey withouts */
	  ub4 new_coverage = count_tuples(s, t, d, f);
	  if (s->n[d][f] < best_n) {
	    best_n = s->n[d][f];
	    progress = TRUE;
	    coverage = new_coverage;
	    count = 0;
	    best[count++] = f;
	  } else if (s->n[d][f] == best_n && new_coverage >= coverage) {
	    if (new_coverage > coverage) {
	      progress = TRUE;
	      coverage = new_coverage;
	      count = 0;
	    }
	    best[count++] = f;
	  }
	}
      }

      /* 
       * Change this dimension to the best features seen.
       * Worst case, everyone was worse than the old value, so best[0] will
       * be the old value.  Coverage will be the same and still no withouts
       * will be hit.
       */
      if (count == 0) {
	printf("jenny: internal error b\n");
      } else if (count == 1) {
	t->f[d] = best[0];
      } else {
	t->f[d] = best[rand(&s->r) % count];
      }
      if (s->n[d][t->f[d]] == n)
	total += coverage;
    }

  } while (progress);
  return total;
}


/*
 * Generate one test that obeys all the restrictions and covers at 
 * least one tuple.  Do not add it to the list of tests yet.  Return FALSE
 * if we couldn't satisfy the withouts while covering this tuple.
 */
#define MAX_ITERS 10
ub4 generate_test( state *s, test *t, feature *tuple, ub1 n)
{
  int  iter, i;
  ub1  mut[MAX_DIMENSIONS];        /* mut[i] = 1 if I can adjust dimension i */
  ub4  coverage = 0;

  /* mut[i] = 1 if I can modify dimension i */
  for (i=0; i<s->ndim; ++i) mut[i] = 1;
  for (i=0; i<n; ++i) mut[tuple[i].d] = 0;
  
  for (iter=0; iter<MAX_ITERS; ++iter) {
    /* Produce a totally random testcase */
    for (i=0; i<s->ndim; ++i) {
      t->f[i] = rand(&s->r) % (s->dim[i]);
    }
    
    /* Plug in the chosen new tuple */
    for (i=0; i<n; ++i){
      t->f[tuple[i].d] = tuple[i].f;
    }

    /* If we can get all the withouts obeyed, break, success */
    if (!s->wc2 || obey_withouts(s, t, mut)) {
      if (count_withouts(t, s->wc2)) {
	printf("internal error without %d\n", s->wc2);
      }
      break;
    }
  }

  /* quit if we were unable to satisfy the withouts */
  if (iter == MAX_ITERS) {
    goto done;
  }

  /*
   * We now have a test that covers the new tuple and satisfies withouts.
   * Do hillclimbing to cover as many new tuples as possible.
   */
  coverage = maximize_coverage(s, t, mut, n);

 done:
  return coverage;
}

#define GROUP_SIZE 5
void cover_tuples( state *s)
{
  test *curr_test;
  curr_test = (test *)my_alloc( s, sizeof(test));
  curr_test->f = (ub2 *)my_alloc( s, sizeof(ub2)*s->ndim);

  while (TRUE) {
    ub4         i;
    ub2         d;
    test       *best_test;
    sb4         best_count = -1;
    ub1         tuple_n = MAX_N;
    ub4         tuple_count = 0;
    ub1         covered = FALSE;
    feature    *tuple = (feature *)0;

    /* extend lists of tuples and choose one tuple to cover */
    for (d=0; d<s->ndim; ++d) {
      ub2 f;
      for (f=0; f<s->dim[d]; ++f) {
	build_tuples(s, d, f);
	if (s->n[d][f] < tuple_n && s->tc[d][f] > 0) {
	  tuple_n = s->n[d][f];
	  tuple_count = s->tc[d][f];
	  tuple = s->tu[d][f]->fe;
	} else if (s->n[d][f] == tuple_n && s->tc[d][f] > tuple_count) {
	  tuple_count = s->tc[d][f];
	  tuple = s->tu[d][f]->fe;
	}
      }
    }

    if (tuple_count == 0) {
      break;                               /* no more tuples to cover, done! */
    }

    best_test = (test *)my_alloc( s, sizeof(test));
    best_test->f = (ub2 *)my_alloc( s, sizeof(ub2)*s->ndim);

    /* find a good test */
    for (i=0; i<GROUP_SIZE; ++i) {
      tu_iter  ctx;
      sb4      this_count;

      /* generate a test that covers the first tuple */
      if (!(this_count = generate_test(s, curr_test, tuple, tuple_n))) {
	continue;
      }
      covered = TRUE;

      /* see how many tuples are covered altogether */
      if (this_count > best_count) {
	test *temp = best_test;
	best_test = curr_test;
	curr_test = temp;

	best_count = this_count;
      }
    }

    if (!covered) {
      wchain  *wc = (wchain *)my_alloc( s, sizeof(wchain));
      without *w = (without *)my_alloc( s, sizeof(without));
      feature  extra[MAX_N];

      /* make a copy of tuple, because we'll be deleting it */
      for (i=0; i<tuple_n; ++i) {
	extra[i].d = tuple[i].d;
	extra[i].f = tuple[i].f;
      }

      printf("Could not cover tuple ");
      show_tuple(tuple, tuple_n);

      /* add this tuple to the list of restrictions */
      wc->w = w;
      wc->next = s->wc3;
      s->wc3 = wc;
      w->fe = (feature *)0;
      w->len = tuple_n;
      w->fe = (feature *)my_alloc( s, sizeof(feature)*tuple_n);
      for (i=0; i<tuple_n; ++i) {
	w->fe[i].d = extra[i].d;
	w->fe[i].f = extra[i].f;
      }
      
      for (d=0; d<s->ndim; ++d) {
	ub2      f;
	tu_iter  ctx;
	for (f=0; f<s->dim[d]; ++f) {
	  ub1      n = s->n[d][f];
	  feature *this = start_tuple(&ctx, &s->tu[d][f], n, &s->tc[d][f]);
	
	  /* remove all the tuples covered by it */
	  while (this) {
	    if (subset_tuple(extra, tuple_n, this, n)) {
	      this = delete_tuple(&ctx);
	    } else {
	      this = next_tuple(&ctx);
	    }
	  }
	}
      }
      bob_free((char *)best_test->f);
      bob_free((char *)best_test);
    } else {
      ub2      d;
      for (d=0; d<s->ndim; ++d) {
	tu_iter  ctx;
	ub2      f = best_test->f[d];
	ub1      n = s->n[d][f];
	feature *this = start_tuple(&ctx, &s->tu[d][f], n, &s->tc[d][f]);
	
	/* remove all the tuples covered by it */
	while (this) {
	  if (test_tuple(best_test->f, this, n)) {
	    this = delete_tuple(&ctx);
	  } else {
	    this = next_tuple(&ctx);
	  }
	}
      }

      /* add it to the list of tests */
      add_test(s, best_test);
    }
  }

  bob_free((char *)curr_test->f);
  bob_free((char *)curr_test);
}

void driver( int argc, char *argv[])
{
  state s;                                                 /* internal state */

  initialize(&s);

  if (parse(argc, argv, &s)) {               /* read the user's instructions */
    preliminary(&s);                          /* do any preliminary analysis */

    cover_tuples(&s);

    report_all(&s);                                    /* report the results */
  }
  cleanup(&s);                                      /* deallocate everything */
}

int main( int argc, char *argv[])
{
  driver(argc, argv);
  return 0;
}