tests/libpspp/sparse-xarray-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* This is a test program for the sparse array routines defined
  18    in sparse-xarray.c.  This test program aims to be as
  19    comprehensive as possible.  "gcov -b" should report 100%
  20    coverage of lines and branches in sparse-xarray.c when
  21    compiled with -DNDEBUG.  "valgrind --leak-check=yes
  22    --show-reachable=yes" should give a clean report. */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <getopt.h>
  29 #include <assert.h>
  30 #include <limits.h>
  31 #include <stdint.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include <libpspp/argv-parser.h>
  37 #include <libpspp/assertion.h>
  38 #include <libpspp/hash-functions.h>
  39 #include <libpspp/model-checker.h>
  40 #include <libpspp/sparse-xarray.h>
  41 #include <libpspp/str.h>
  42
  43 #include "error.h"
  44 #include "minmax.h"
  45 #include "progname.h"
  46 #include "xalloc.h"
  47 \f
  48 /* Maximum size of sparse_xarray supported for model checking
  49    purposes. */
  50 #define MAX_ROWS 5
  51 #define MAX_COLS 5
  52
  53 /* Test parameters. */
  54 struct test_params
  55   {
  56     /* Controlling the test state space. */
  57     int n_columns;              /* Number of columns in each row. */
  58     int max_rows;               /* Maximum number of rows. */
  59     int max_memory_rows;        /* Max rows before writing to disk. */
  60     unsigned char n_values;     /* Number of unique cell values. */
  61     int n_xarrays;              /* Number of sparse_xarrays in state. */
  62
  63     /* Types of operations to perform. */
  64     bool write_cells;           /* Write to individual cells. */
  65     bool write_rows;            /* Write whole rows. */
  66     bool write_columns;         /* Write whole columns. */
  67     bool copy_within_xarray;    /* Copy column ranges in a single xarray. */
  68   };
  69
  70 struct test_state
  71   {
  72     struct sparse_xarray *xarrays[2];
  73   };
  74
  75 static void
  76 test_state_destroy (const struct test_params *params, struct test_state *ts)
  77 {
  78   int i;
  79
  80   for (i = 0; i < params->n_xarrays; i++)
  81     sparse_xarray_destroy (ts->xarrays[i]);
  82 }
  83
  84 static struct test_state *
  85 test_state_clone (const struct test_params *params,
  86                   const struct test_state *ots)
  87 {
  88   struct test_state *ts;
  89   int i;
  90
  91   ts = xmalloc (sizeof *ts);
  92   for (i = 0; i < params->n_xarrays; i++)
  93     {
  94       ts->xarrays[i] = sparse_xarray_clone (ots->xarrays[i]);
  95       if (ts->xarrays[i] == NULL)
  96         NOT_REACHED ();
  97     }
  98   return ts;
  99 }
 100
 101 struct xarray_model
 102   {
 103     uint8_t data[MAX_ROWS][MAX_COLS];
 104     bool contains_row[MAX_ROWS];
 105   };
 106
 107 struct test_model
 108   {
 109     struct xarray_model models[2];
 110   };
 111
 112 /* Extracts the contents of TS into TM. */
 113 static void
 114 test_model_extract (const struct test_params *params,
 115                     const struct test_state *ts, struct test_model *tm)
 116 {
 117   int i;
 118
 119   for (i = 0; i < params->n_xarrays; i++)
 120     {
 121       const struct sparse_xarray *sx = ts->xarrays[i];
 122       struct xarray_model *model = &tm->models[i];
 123       size_t n_columns = sparse_xarray_get_n_columns (sx);
 124       size_t n_rows = sparse_xarray_get_n_rows (sx);
 125       size_t row;
 126
 127       assert (n_rows < MAX_ROWS);
 128       assert (n_columns < MAX_COLS);
 129       for (row = 0; row < params->max_rows; row++)
 130         {
 131           model->contains_row[row] = sparse_xarray_contains_row (sx, row);
 132           if (!sparse_xarray_read (sx, row, 0, n_columns, model->data[row]))
 133             NOT_REACHED ();
 134         }
 135     }
 136 }
 137
 138 /* Checks that test state TS matches the test model TM and
 139    reports any mismatches via mc_error.  Then, adds SX to MC as a
 140    new state. */
 141 static void
 142 check_state (struct mc *mc, struct test_state *ts, const struct test_model *tm)
 143 {
 144   const struct test_params *params = mc_get_aux (mc);
 145   int n_columns = params->n_columns;
 146   unsigned int hash;
 147   int i;
 148
 149   for (i = 0; i < params->n_xarrays; i++)
 150     {
 151       const struct xarray_model *model = &tm->models[i];
 152       const struct sparse_xarray *sx = ts->xarrays[i];
 153       bool difference;
 154       int row, col;
 155       int n_rows;
 156
 157       assert (n_columns < MAX_COLS);
 158
 159       /* Check row count. */
 160       n_rows = 0;
 161       for (row = 0; row < params->max_rows; row++)
 162         if (model->contains_row[row])
 163           n_rows = row + 1;
 164       if (n_rows != sparse_xarray_get_n_rows (sx))
 165         mc_error (mc, "xarray %d: row count (%zu) does not match expected "
 166                   "(%d)", i, sparse_xarray_get_n_rows (sx), n_rows);
 167
 168       /* Check row containment. */
 169       for (row = 0; row < params->max_rows; row++)
 170         {
 171           bool contains = sparse_xarray_contains_row (sx, row);
 172           if (contains && !model->contains_row[row])
 173             mc_error (mc, "xarray %d: row %d is contained by sparse_xarray "
 174                       "but should not be", i, row);
 175           else if (!contains && model->contains_row[row])
 176             mc_error (mc, "xarray %d: row %d is not contained by "
 177                       "sparse_xarray but should be", i, row);
 178         }
 179
 180       /* Check contents. */
 181       difference = false;
 182       for (row = 0; row < params->max_rows; row++)
 183         {
 184           unsigned char data[MAX_COLS];
 185
 186           if (!sparse_xarray_read (sx, row, 0, n_columns, data))
 187             NOT_REACHED ();
 188           for (col = 0; col < params->n_columns; col++)
 189             if (data[col] != model->data[row][col])
 190               {
 191                 mc_error (mc, "xarray %d: element %zu,%zu (of %zu,%zu) "
 192                           "differs: %d should be %d",
 193                           i, row, col, n_rows, n_columns, data[col],
 194                           model->data[row][col]);
 195                 difference = true;
 196               }
 197         }
 198
 199       if (difference)
 200         {
 201           struct string ds;
 202
 203           mc_error (mc, "xarray %d: expected:", i);
 204           ds_init_empty (&ds);
 205           for (row = 0; row < params->max_rows; row++)
 206             {
 207               ds_clear (&ds);
 208               for (col = 0; col < n_columns; col++)
 209                 ds_put_format (&ds, " %d", model->data[row][col]);
 210               mc_error (mc, "xarray %d: row %zu:%s", i, row, ds_cstr (&ds));
 211             }
 212
 213           mc_error (mc, "xarray %d: actual:", i);
 214           ds_init_empty (&ds);
 215           for (row = 0; row < params->max_rows; row++)
 216             {
 217               unsigned char data[MAX_COLS];
 218
 219               if (!sparse_xarray_read (sx, row, 0, n_columns, data))
 220                 NOT_REACHED ();
 221
 222               ds_clear (&ds);
 223               for (col = 0; col < n_columns; col++)
 224                 ds_put_format (&ds, " %d", data[col]);
 225               mc_error (mc, "xarray %d: row %zu:%s", i, row, ds_cstr (&ds));
 226             }
 227
 228           ds_destroy (&ds);
 229         }
 230     }
 231
 232   hash = 0;
 233   for (i = 0; i < params->n_xarrays; i++)
 234     hash = sparse_xarray_model_checker_hash (ts->xarrays[i], hash);
 235   if (mc_discard_dup_state (mc, hash))
 236     test_state_destroy (params, ts);
 237   else
 238     mc_add_state (mc, ts);
 239 }
 240
 241 static bool
 242 next_data (unsigned char *data, int n, int n_values)
 243 {
 244   int i;
 245   for (i = n - 1; i >= 0; i--)
 246     {
 247       data[i]++;
 248       if (data[i] < n_values)
 249         return true;
 250       data[i] = 0;
 251     }
 252   return false;
 253 }
 254
 255 struct copy_columns_params
 256   {
 257     int n;                      /* Number of columns to copy. */
 258     int src;                    /* Offset of first source column. */
 259     int dst;                    /* Offset of first destination column. */
 260   };
 261
 262 static bool
 263 copy_columns (const void *src_, void *dst_, void *copy_)
 264 {
 265   const struct copy_columns_params *copy = copy_;
 266   const uint8_t *src = src_;
 267   uint8_t *dst = dst_;
 268
 269   memmove (dst + copy->dst, src + copy->src, copy->n);
 270   return true;
 271 }
 272
 273 /* "init" function for struct mc_class. */
 274 static void
 275 sparse_xarray_mc_init (struct mc *mc)
 276 {
 277   struct test_params *params = mc_get_aux (mc);
 278   struct test_state *ts;
 279   struct test_model tm;
 280   int i;
 281
 282   mc_name_operation (mc, "empty sparse_xarray with n_columns=%zu, "
 283                      "max_memory_rows=%zu",
 284                      params->n_columns, params->max_memory_rows);
 285   ts = xmalloc (sizeof *ts);
 286   for (i = 0; i < params->n_xarrays; i++)
 287     ts->xarrays[i] = sparse_xarray_create (params->n_columns,
 288                                            params->max_memory_rows);
 289   memset (&tm, 0, sizeof tm);
 290   check_state (mc, ts, &tm);
 291 }
 292
 293 /* "mutate" function for struct mc_class. */
 294 static void
 295 sparse_xarray_mc_mutate (struct mc *mc, const void *ots_)
 296 {
 297   struct test_params *params = mc_get_aux (mc);
 298   size_t n_columns = params->n_columns;
 299   const struct test_state *ots = ots_;
 300   struct test_model otm;
 301   int i;
 302
 303   test_model_extract (params, ots, &otm);
 304   for (i = 0; i < params->n_xarrays; i++)
 305     {
 306       unsigned char value;
 307       int row, col, n, src, dst;
 308
 309       /* Write all possible values to each possible single cell. */
 310       if (params->write_cells)
 311         for (row = 0; row < params->max_rows; row++)
 312           for (col = 0; col < n_columns; col++)
 313             for (value = 0; value < params->n_values; value++)
 314               if (mc_include_state (mc))
 315                 {
 316                   struct test_state *ts = test_state_clone (params, ots);
 317                   struct sparse_xarray *sx = ts->xarrays[i];
 318                   struct test_model tm = otm;
 319                   struct xarray_model *model = &tm.models[i];
 320
 321                   mc_name_operation (mc, "xarray %d: set (%d,%d) to %d",
 322                                      i, row, col, value);
 323                   if (!sparse_xarray_write (sx, row, col, 1, &value))
 324                     NOT_REACHED ();
 325                   model->data[row][col] = value;
 326                   model->contains_row[row] = true;
 327                   check_state (mc, ts, &tm);
 328                 }
 329
 330       /* Write all possible row contents to each row. */
 331       if (params->write_rows)
 332         for (row = 0; row < params->max_rows; row++)
 333           {
 334             struct test_model tm = otm;
 335             struct xarray_model *model = &tm.models[i];
 336
 337             memset (model->data[row], 0, n_columns);
 338             model->contains_row[row] = true;
 339             do
 340               {
 341                 if (mc_include_state (mc))
 342                   {
 343                     struct test_state *ts = test_state_clone (params, ots);
 344                     struct sparse_xarray *sx = ts->xarrays[i];
 345                     char row_string[MAX_COLS + 1];
 346
 347                     mc_name_operation (mc, "xarray %d: set row %d to %s",
 348                                        i, row, row_string);
 349                     for (col = 0; col < n_columns; col++)
 350                       {
 351                         value = model->data[row][col];
 352                         row_string[col] = value < 10 ? '0' + value : '*';
 353                       }
 354                     row_string[n_columns] = '\0';
 355                     if (!sparse_xarray_write (sx, row, 0, n_columns,
 356                                               model->data[row]))
 357                       NOT_REACHED ();
 358                     check_state (mc, ts, &tm);
 359                   }
 360               }
 361             while (next_data (model->data[row], n_columns, params->n_values));
 362           }
 363
 364       /* Write all possible values to each possible column. */
 365       if (params->write_columns)
 366         for (col = 0; col < n_columns; col++)
 367           for (value = 0; value < params->n_values; value++)
 368             if (mc_include_state (mc))
 369               {
 370                 struct test_state *ts = test_state_clone (params, ots);
 371                 struct sparse_xarray *sx = ts->xarrays[i];
 372                 struct test_model tm = otm;
 373                 struct xarray_model *model = &tm.models[i];
 374
 375                 mc_name_operation (mc, "xarray %d: write value %d to "
 376                                    "column %d", i, value, col);
 377                 if (!sparse_xarray_write_columns (sx, col, 1, &value))
 378                   NOT_REACHED ();
 379                 for (row = 0; row < params->max_rows; row++)
 380                   model->data[row][col] = value;
 381                 check_state (mc, ts, &tm);
 382               }
 383
 384       /* Copy all possible column ranges within a single sparse_xarray. */
 385       if (params->copy_within_xarray)
 386         for (n = 1; n <= n_columns; n++)
 387           for (src = 0; src <= n_columns - n; src++)
 388             for (dst = 0; dst <= n_columns - n; dst++)
 389               if (mc_include_state (mc))
 390                 {
 391                   struct copy_columns_params copy_aux;
 392                   struct test_state *ts = test_state_clone (params, ots);
 393                   struct sparse_xarray *sx = ts->xarrays[i];
 394                   struct test_model tm = otm;
 395                   struct xarray_model *model = &tm.models[i];
 396
 397                   mc_name_operation (mc, "xarray %d: copy %d columns from "
 398                                      "offset %d to offset %d", i, n, src, dst);
 399
 400                   copy_aux.n = n;
 401                   copy_aux.src = src;
 402                   copy_aux.dst = dst;
 403                   if (!sparse_xarray_copy (sx, sx, copy_columns, &copy_aux))
 404                     NOT_REACHED ();
 405
 406                   for (row = 0; row < params->max_rows; row++)
 407                     memmove (&model->data[row][dst],
 408                              &model->data[row][src], n);
 409
 410                   check_state (mc, ts, &tm);
 411                 }
 412     }
 413
 414   if (params->n_xarrays == 2)
 415     {
 416       int row, n, src, dst;
 417
 418       /* Copy all possible column ranges from xarrays[0] to xarrays[1]. */
 419       for (n = 1; n <= n_columns; n++)
 420         for (src = 0; src <= n_columns - n; src++)
 421           for (dst = 0; dst <= n_columns - n; dst++)
 422             if (mc_include_state (mc))
 423               {
 424                 struct copy_columns_params copy_aux;
 425                 struct test_state *ts = test_state_clone (params, ots);
 426                 struct test_model tm = otm;
 427
 428                 mc_name_operation (mc, "copy %d columns from offset %d in "
 429                                    "xarray 0 to offset %d in xarray 1",
 430                                    n, src, dst);
 431
 432                 copy_aux.n = n;
 433                 copy_aux.src = src;
 434                 copy_aux.dst = dst;
 435                 if (!sparse_xarray_copy (ts->xarrays[0], ts->xarrays[1],
 436                                          copy_columns, &copy_aux))
 437                   NOT_REACHED ();
 438
 439                 for (row = 0; row < params->max_rows; row++)
 440                   {
 441                     if (tm.models[0].contains_row[row])
 442                       tm.models[1].contains_row[row] = true;
 443                     memmove (&tm.models[1].data[row][dst],
 444                              &tm.models[0].data[row][src], n);
 445                   }
 446
 447                 check_state (mc, ts, &tm);
 448               }
 449     }
 450 }
 451
 452 /* "destroy" function for struct mc_class. */
 453 static void
 454 sparse_xarray_mc_destroy (const struct mc *mc UNUSED, void *ts_)
 455 {
 456   struct test_params *params = mc_get_aux (mc);
 457   struct test_state *ts = ts_;
 458
 459   test_state_destroy (params, ts);
 460 }
 461
 462 static void
 463 usage (void)
 464 {
 465   printf ("%s, for testing the sparse_xarray implementation.\n"
 466           "Usage: %s [OPTION]...\n"
 467           "\nTest state space parameters (min...max, default):\n"
 468           "  --columns=N          Number of columns per row (0...5, 3)\n"
 469           "  --max-rows=N         Maximum number of rows (0...5, 3)\n"
 470           "  --max-memory-rows=N  Max rows before paging to disk (0...5, 3)\n"
 471           "  --values=N           Number of unique cell values (1...254, 3)\n"
 472           "  --xarrays=N          Number of xarrays at a time (1...2, 1)\n"
 473           "\nTest operation parameters:\n"
 474           "  --no-write-cells     Do not write individual cells\n"
 475           "  --no-write-rows      Do not write whole rows\n"
 476           "  --no-write-columns   Do not write whole columns\n"
 477           "  --no-copy-columns    Do not copy column ranges in an xarray\n",
 478           program_name, program_name);
 479   mc_options_usage ();
 480   fputs ("\nOther options:\n"
 481          "  --help               Display this help message\n"
 482          "\nReport bugs to <bug-gnu-pspp@gnu.org>\n",
 483          stdout);
 484   exit (0);
 485 }
 486 \f
 487 enum
 488   {
 489     OPT_COLUMNS,
 490     OPT_MAX_ROWS,
 491     OPT_MAX_MEMORY_ROWS,
 492     OPT_VALUES,
 493     OPT_XARRAYS,
 494     OPT_NO_WRITE_CELLS,
 495     OPT_NO_WRITE_ROWS,
 496     OPT_NO_WRITE_COLUMNS,
 497     OPT_NO_COPY_COLUMNS,
 498     OPT_HELP
 499   };
 500
 501 static struct argv_option sparse_xarray_argv_options[] =
 502   {
 503     {"columns", 0, required_argument, OPT_COLUMNS},
 504     {"max-rows", 0, required_argument, OPT_MAX_ROWS},
 505     {"max-memory-rows", 0, required_argument, OPT_MAX_MEMORY_ROWS},
 506     {"values", 0, required_argument, OPT_VALUES},
 507     {"xarrays", 0, required_argument, OPT_XARRAYS},
 508     {"no-write-cells", 0, no_argument, OPT_NO_WRITE_CELLS},
 509     {"no-write-rows", 0, no_argument, OPT_NO_WRITE_ROWS},
 510     {"no-write-columns", 0, no_argument, OPT_NO_WRITE_COLUMNS},
 511     {"no-copy-columns", 0, no_argument, OPT_NO_COPY_COLUMNS},
 512     {"help", 'h', no_argument, OPT_HELP},
 513   };
 514 enum { N_SPARSE_XARRAY_ARGV_OPTIONS = (sizeof sparse_xarray_argv_options
 515                                        / sizeof *sparse_xarray_argv_options) };
 516
 517 static void
 518 sparse_xarray_option_callback (int id, void *params_)
 519 {
 520   struct test_params *params = params_;
 521   switch (id)
 522     {
 523     case OPT_COLUMNS:
 524       params->n_columns = atoi (optarg);
 525       break;
 526
 527     case OPT_MAX_ROWS:
 528       params->max_rows = atoi (optarg);
 529       break;
 530
 531     case OPT_MAX_MEMORY_ROWS:
 532       params->max_memory_rows = atoi (optarg);
 533       break;
 534
 535     case OPT_VALUES:
 536       params->n_values = atoi (optarg);
 537       break;
 538
 539     case OPT_XARRAYS:
 540       params->n_xarrays = atoi (optarg);
 541       break;
 542
 543     case OPT_NO_WRITE_CELLS:
 544       params->write_cells = false;
 545       break;
 546
 547     case OPT_NO_WRITE_ROWS:
 548       params->write_rows = false;
 549       break;
 550
 551     case OPT_NO_WRITE_COLUMNS:
 552       params->write_columns = false;
 553       break;
 554
 555     case OPT_NO_COPY_COLUMNS:
 556       params->copy_within_xarray = false;
 557       break;
 558
 559     case OPT_HELP:
 560       usage ();
 561       break;
 562
 563     default:
 564       NOT_REACHED ();
 565     }
 566 }
 567
 568 int
 569 main (int argc, char *argv[])
 570 {
 571   static const struct mc_class sparse_xarray_mc_class =
 572     {
 573       sparse_xarray_mc_init,
 574       sparse_xarray_mc_mutate,
 575       sparse_xarray_mc_destroy,
 576     };
 577
 578   struct test_params params;
 579   struct mc_options *options;
 580   struct mc_results *results;
 581   struct argv_parser *parser;
 582   int verbosity;
 583   bool success;
 584
 585   set_program_name (argv[0]);
 586
 587   /* Default parameters. */
 588   params.n_columns = 3;
 589   params.max_rows = 3;
 590   params.max_memory_rows = 3;
 591   params.n_values = 3;
 592   params.n_xarrays = 1;
 593   params.write_cells = true;
 594   params.write_rows = true;
 595   params.write_columns = true;
 596   params.copy_within_xarray = true;
 597
 598   /* Parse command line. */
 599   parser = argv_parser_create ();
 600   options = mc_options_create ();
 601   mc_options_register_argv_parser (options, parser);
 602   argv_parser_add_options (parser, sparse_xarray_argv_options,
 603                            N_SPARSE_XARRAY_ARGV_OPTIONS,
 604                            sparse_xarray_option_callback, &params);
 605   if (!argv_parser_run (parser, argc, argv))
 606     exit (EXIT_FAILURE);
 607   argv_parser_destroy (parser);
 608   verbosity = mc_options_get_verbosity (options);
 609
 610   /* Force parameters into allowed ranges. */
 611   params.n_columns = MAX (0, MIN (params.n_columns, MAX_COLS));
 612   params.max_rows = MAX (0, MIN (params.max_rows, MAX_ROWS));
 613   params.max_memory_rows = MAX (0, MIN (params.max_memory_rows,
 614                                         params.max_rows));
 615   params.n_values = MIN (254, MAX (1, params.n_values));
 616   params.n_xarrays = MAX (1, MIN (2, params.n_xarrays));
 617   mc_options_set_aux (options, &params);
 618   results = mc_run (&sparse_xarray_mc_class, options);
 619
 620   /* Output results. */
 621   success = (mc_results_get_stop_reason (results) != MC_MAX_ERROR_COUNT
 622              && mc_results_get_stop_reason (results) != MC_INTERRUPTED);
 623   if (verbosity > 0 || !success)
 624     {
 625       printf ("Parameters: "
 626               "--columns=%d --max-rows=%d --max-memory-rows=%d --values=%d "
 627               "--xarrays=%d",
 628               params.n_columns, params.max_rows, params.max_memory_rows,
 629               params.n_values, params.n_xarrays);
 630       if (!params.write_cells)
 631         printf (" --no-write-cells");
 632       if (!params.write_rows)
 633         printf (" --no-write-rows");
 634       if (!params.write_columns)
 635         printf (" --no-write-columns");
 636       if (!params.copy_within_xarray)
 637         printf (" --no-copy-columns");
 638       printf ("\n\n");
 639       mc_results_print (results, stdout);
 640     }
 641   mc_results_destroy (results);
 642
 643   return success ? 0 : EXIT_FAILURE;
 644 }