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   free (ts);
  77 }
  78
  79 static struct test_state *
  80 test_state_clone (const struct test_params *params,
  81                   const struct test_state *ots)
  82 {
  83   struct test_state *ts;
  84   int i;
  85
  86   ts = xmalloc (sizeof *ts);
  87   for (i = 0; i < params->n_xarrays; i++)
  88     {
  89       ts->xarrays[i] = sparse_xarray_clone (ots->xarrays[i]);
  90       if (ts->xarrays[i] == NULL)
  91         NOT_REACHED ();
  92     }
  93   return ts;
  94 }
  95
  96 struct xarray_model
  97   {
  98     uint8_t data[MAX_ROWS][MAX_COLS];
  99     bool contains_row[MAX_ROWS];
 100   };
 101
 102 struct test_model
 103   {
 104     struct xarray_model models[2];
 105   };
 106
 107 /* Extracts the contents of TS into TM. */
 108 static void
 109 test_model_extract (const struct test_params *params,
 110                     const struct test_state *ts, struct test_model *tm)
 111 {
 112   int i;
 113
 114   for (i = 0; i < params->n_xarrays; i++)
 115     {
 116       const struct sparse_xarray *sx = ts->xarrays[i];
 117       struct xarray_model *model = &tm->models[i];
 118       size_t n_columns = sparse_xarray_get_n_columns (sx);
 119       size_t n_rows = sparse_xarray_get_n_rows (sx);
 120       size_t row;
 121
 122       assert (n_rows < MAX_ROWS);
 123       assert (n_columns < MAX_COLS);
 124       for (row = 0; row < params->max_rows; row++)
 125         {
 126           model->contains_row[row] = sparse_xarray_contains_row (sx, row);
 127           if (!sparse_xarray_read (sx, row, 0, n_columns, model->data[row]))
 128             NOT_REACHED ();
 129         }
 130     }
 131 }
 132
 133 /* Checks that test state TS matches the test model TM and
 134    reports any mismatches via mc_error.  Then, adds SX to MC as a
 135    new state. */
 136 static void
 137 check_state (struct mc *mc, struct test_state *ts, const struct test_model *tm)
 138 {
 139   const struct test_params *params = mc_get_aux (mc);
 140   int n_columns = params->n_columns;
 141   unsigned int hash;
 142   int i;
 143
 144   for (i = 0; i < params->n_xarrays; i++)
 145     {
 146       const struct xarray_model *model = &tm->models[i];
 147       const struct sparse_xarray *sx = ts->xarrays[i];
 148       bool difference;
 149       int row, col;
 150       int n_rows;
 151
 152       assert (n_columns < MAX_COLS);
 153
 154       /* Check row count. */
 155       n_rows = 0;
 156       for (row = 0; row < params->max_rows; row++)
 157         if (model->contains_row[row])
 158           n_rows = row + 1;
 159       if (n_rows != sparse_xarray_get_n_rows (sx))
 160         mc_error (mc, "xarray %d: row count (%zu) does not match expected "
 161                   "(%d)", i, sparse_xarray_get_n_rows (sx), n_rows);
 162
 163       /* Check row containment. */
 164       for (row = 0; row < params->max_rows; row++)
 165         {
 166           bool contains = sparse_xarray_contains_row (sx, row);
 167           if (contains && !model->contains_row[row])
 168             mc_error (mc, "xarray %d: row %d is contained by sparse_xarray "
 169                       "but should not be", i, row);
 170           else if (!contains && model->contains_row[row])
 171             mc_error (mc, "xarray %d: row %d is not contained by "
 172                       "sparse_xarray but should be", i, row);
 173         }
 174
 175       /* Check contents. */
 176       difference = false;
 177       for (row = 0; row < params->max_rows; row++)
 178         {
 179           unsigned char data[MAX_COLS];
 180
 181           if (!sparse_xarray_read (sx, row, 0, n_columns, data))
 182             NOT_REACHED ();
 183           for (col = 0; col < params->n_columns; col++)
 184             if (data[col] != model->data[row][col])
 185               {
 186                 mc_error (mc, "xarray %d: element %d,%d (of %d,%d) "
 187                           "differs: %d should be %d",
 188                           i, row, col, n_rows, n_columns, data[col],
 189                           model->data[row][col]);
 190                 difference = true;
 191               }
 192         }
 193
 194       if (difference)
 195         {
 196           struct string ds;
 197
 198           mc_error (mc, "xarray %d: expected:", i);
 199           ds_init_empty (&ds);
 200           for (row = 0; row < params->max_rows; row++)
 201             {
 202               ds_clear (&ds);
 203               for (col = 0; col < n_columns; col++)
 204                 ds_put_format (&ds, " %d", model->data[row][col]);
 205               mc_error (mc, "xarray %d: row %d:%s", i, row, ds_cstr (&ds));
 206             }
 207
 208           mc_error (mc, "xarray %d: actual:", i);
 209           ds_init_empty (&ds);
 210           for (row = 0; row < params->max_rows; row++)
 211             {
 212               unsigned char data[MAX_COLS];
 213
 214               if (!sparse_xarray_read (sx, row, 0, n_columns, data))
 215                 NOT_REACHED ();
 216
 217               ds_clear (&ds);
 218               for (col = 0; col < n_columns; col++)
 219                 ds_put_format (&ds, " %d", data[col]);
 220               mc_error (mc, "xarray %d: row %d:%s", i, row, ds_cstr (&ds));
 221             }
 222
 223           ds_destroy (&ds);
 224         }
 225     }
 226
 227   hash = 0;
 228   for (i = 0; i < params->n_xarrays; i++)
 229     hash = sparse_xarray_model_checker_hash (ts->xarrays[i], hash);
 230   if (mc_discard_dup_state (mc, hash))
 231     test_state_destroy (params, ts);
 232   else
 233     mc_add_state (mc, ts);
 234 }
 235
 236 static bool
 237 next_data (unsigned char *data, int n, int n_values)
 238 {
 239   int i;
 240   for (i = n - 1; i >= 0; i--)
 241     {
 242       data[i]++;
 243       if (data[i] < n_values)
 244         return true;
 245       data[i] = 0;
 246     }
 247   return false;
 248 }
 249
 250 struct copy_columns_params
 251   {
 252     int n;                      /* Number of columns to copy. */
 253     int src;                    /* Offset of first source column. */
 254     int dst;                    /* Offset of first destination column. */
 255   };
 256
 257 static bool
 258 copy_columns (const void *src_, void *dst_, void *copy_)
 259 {
 260   const struct copy_columns_params *copy = copy_;
 261   const uint8_t *src = src_;
 262   uint8_t *dst = dst_;
 263
 264   memmove (dst + copy->dst, src + copy->src, copy->n);
 265   return true;
 266 }
 267
 268 /* "init" function for struct mc_class. */
 269 static void
 270 sparse_xarray_mc_init (struct mc *mc)
 271 {
 272   struct test_params *params = mc_get_aux (mc);
 273   struct test_state *ts;
 274   struct test_model tm;
 275   int i;
 276
 277   mc_name_operation (mc, "empty sparse_xarray with n_columns=%d, "
 278                      "max_memory_rows=%d",
 279                      params->n_columns, params->max_memory_rows);
 280   ts = xmalloc (sizeof *ts);
 281   for (i = 0; i < params->n_xarrays; i++)
 282     ts->xarrays[i] = sparse_xarray_create (params->n_columns,
 283                                            params->max_memory_rows);
 284   memset (&tm, 0, sizeof tm);
 285   check_state (mc, ts, &tm);
 286 }
 287
 288 /* "mutate" function for struct mc_class. */
 289 static void
 290 sparse_xarray_mc_mutate (struct mc *mc, const void *ots_)
 291 {
 292   struct test_params *params = mc_get_aux (mc);
 293   size_t n_columns = params->n_columns;
 294   const struct test_state *ots = ots_;
 295   struct test_model otm;
 296   int i;
 297
 298   test_model_extract (params, ots, &otm);
 299   for (i = 0; i < params->n_xarrays; i++)
 300     {
 301       unsigned char value;
 302       int row, col, n, src, dst;
 303
 304       /* Write all possible values to each possible single cell. */
 305       if (params->write_cells)
 306         for (row = 0; row < params->max_rows; row++)
 307           for (col = 0; col < n_columns; col++)
 308             for (value = 0; value < params->n_values; value++)
 309               if (mc_include_state (mc))
 310                 {
 311                   struct test_state *ts = test_state_clone (params, ots);
 312                   struct sparse_xarray *sx = ts->xarrays[i];
 313                   struct test_model tm = otm;
 314                   struct xarray_model *model = &tm.models[i];
 315
 316                   mc_name_operation (mc, "xarray %d: set (%d,%d) to %d",
 317                                      i, row, col, value);
 318                   if (!sparse_xarray_write (sx, row, col, 1, &value))
 319                     NOT_REACHED ();
 320                   model->data[row][col] = value;
 321                   model->contains_row[row] = true;
 322                   check_state (mc, ts, &tm);
 323                 }
 324
 325       /* Write all possible row contents to each row. */
 326       if (params->write_rows)
 327         for (row = 0; row < params->max_rows; row++)
 328           {
 329             struct test_model tm = otm;
 330             struct xarray_model *model = &tm.models[i];
 331
 332             memset (model->data[row], 0, n_columns);
 333             model->contains_row[row] = true;
 334             do
 335               {
 336                 if (mc_include_state (mc))
 337                   {
 338                     struct test_state *ts = test_state_clone (params, ots);
 339                     struct sparse_xarray *sx = ts->xarrays[i];
 340                     char row_string[MAX_COLS + 1];
 341
 342                     mc_name_operation (mc, "xarray %d: set row %d to %s",
 343                                        i, row, row_string);
 344                     for (col = 0; col < n_columns; col++)
 345                       {
 346                         value = model->data[row][col];
 347                         row_string[col] = value < 10 ? '0' + value : '*';
 348                       }
 349                     row_string[n_columns] = '\0';
 350                     if (!sparse_xarray_write (sx, row, 0, n_columns,
 351                                               model->data[row]))
 352                       NOT_REACHED ();
 353                     check_state (mc, ts, &tm);
 354                   }
 355               }
 356             while (next_data (model->data[row], n_columns, params->n_values));
 357           }
 358
 359       /* Write all possible values to each possible column. */
 360       if (params->write_columns)
 361         for (col = 0; col < n_columns; col++)
 362           for (value = 0; value < params->n_values; value++)
 363             if (mc_include_state (mc))
 364               {
 365                 struct test_state *ts = test_state_clone (params, ots);
 366                 struct sparse_xarray *sx = ts->xarrays[i];
 367                 struct test_model tm = otm;
 368                 struct xarray_model *model = &tm.models[i];
 369
 370                 mc_name_operation (mc, "xarray %d: write value %d to "
 371                                    "column %d", i, value, col);
 372                 if (!sparse_xarray_write_columns (sx, col, 1, &value))
 373                   NOT_REACHED ();
 374                 for (row = 0; row < params->max_rows; row++)
 375                   model->data[row][col] = value;
 376                 check_state (mc, ts, &tm);
 377               }
 378
 379       /* Copy all possible column ranges within a single sparse_xarray. */
 380       if (params->copy_within_xarray)
 381         for (n = 1; n <= n_columns; n++)
 382           for (src = 0; src <= n_columns - n; src++)
 383             for (dst = 0; dst <= n_columns - n; dst++)
 384               if (mc_include_state (mc))
 385                 {
 386                   struct copy_columns_params copy_aux;
 387                   struct test_state *ts = test_state_clone (params, ots);
 388                   struct sparse_xarray *sx = ts->xarrays[i];
 389                   struct test_model tm = otm;
 390                   struct xarray_model *model = &tm.models[i];
 391
 392                   mc_name_operation (mc, "xarray %d: copy %d columns from "
 393                                      "offset %d to offset %d", i, n, src, dst);
 394
 395                   copy_aux.n = n;
 396                   copy_aux.src = src;
 397                   copy_aux.dst = dst;
 398                   if (!sparse_xarray_copy (sx, sx, copy_columns, &copy_aux))
 399                     NOT_REACHED ();
 400
 401                   for (row = 0; row < params->max_rows; row++)
 402                     memmove (&model->data[row][dst],
 403                              &model->data[row][src], n);
 404
 405                   check_state (mc, ts, &tm);
 406                 }
 407     }
 408
 409   if (params->n_xarrays == 2)
 410     {
 411       int row, n, src, dst;
 412
 413       /* Copy all possible column ranges from xarrays[0] to xarrays[1]. */
 414       for (n = 1; n <= n_columns; n++)
 415         for (src = 0; src <= n_columns - n; src++)
 416           for (dst = 0; dst <= n_columns - n; dst++)
 417             if (mc_include_state (mc))
 418               {
 419                 struct copy_columns_params copy_aux;
 420                 struct test_state *ts = test_state_clone (params, ots);
 421                 struct test_model tm = otm;
 422
 423                 mc_name_operation (mc, "copy %d columns from offset %d in "
 424                                    "xarray 0 to offset %d in xarray 1",
 425                                    n, src, dst);
 426
 427                 copy_aux.n = n;
 428                 copy_aux.src = src;
 429                 copy_aux.dst = dst;
 430                 if (!sparse_xarray_copy (ts->xarrays[0], ts->xarrays[1],
 431                                          copy_columns, &copy_aux))
 432                   NOT_REACHED ();
 433
 434                 for (row = 0; row < params->max_rows; row++)
 435                   {
 436                     if (tm.models[0].contains_row[row])
 437                       tm.models[1].contains_row[row] = true;
 438                     memmove (&tm.models[1].data[row][dst],
 439                              &tm.models[0].data[row][src], n);
 440                   }
 441
 442                 check_state (mc, ts, &tm);
 443               }
 444     }
 445 }
 446
 447 /* "destroy" function for struct mc_class. */
 448 static void
 449 sparse_xarray_mc_destroy (const struct mc *mc UNUSED, void *ts_)
 450 {
 451   struct test_params *params = mc_get_aux (mc);
 452   struct test_state *ts = ts_;
 453
 454   test_state_destroy (params, ts);
 455 }
 456
 457 static void
 458 usage (void)
 459 {
 460   printf ("%s, for testing the sparse_xarray implementation.\n"
 461           "Usage: %s [OPTION]...\n"
 462           "\nTest state space parameters (min...max, default):\n"
 463           "  --columns=N          Number of columns per row (0...5, 3)\n"
 464           "  --max-rows=N         Maximum number of rows (0...5, 3)\n"
 465           "  --max-memory-rows=N  Max rows before paging to disk (0...5, 3)\n"
 466           "  --values=N           Number of unique cell values (1...254, 3)\n"
 467           "  --xarrays=N          Number of xarrays at a time (1...2, 1)\n"
 468           "\nTest operation parameters:\n"
 469           "  --no-write-cells     Do not write individual cells\n"
 470           "  --no-write-rows      Do not write whole rows\n"
 471           "  --no-write-columns   Do not write whole columns\n"
 472           "  --no-copy-columns    Do not copy column ranges in an xarray\n",
 473           program_name, program_name);
 474   mc_options_usage ();
 475   printf ("\nOther options:\n"
 476          "  --help               Display this help message\n"
 477           "\nReport bugs to <%s>\n", PACKAGE_BUGREPORT);
 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 }