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