src/language/tests/datasheet-check.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007 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 #include <config.h>
  18
  19 #include <data/datasheet.h>
  20 #include "datasheet-check.h"
  21 #include "model-checker.h"
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include <data/casereader-provider.h>
  27 #include <data/casereader.h>
  28 #include <data/casewriter.h>
  29 #include <data/lazy-casereader.h>
  30 #include <data/sparse-cases.h>
  31 #include <libpspp/array.h>
  32 #include <libpspp/assertion.h>
  33 #include <libpspp/range-map.h>
  34 #include <libpspp/range-set.h>
  35 #include <libpspp/taint.h>
  36 #include <libpspp/tower.h>
  37
  38 #include "minmax.h"
  39 #include "md4.h"
  40 #include "xalloc.h"
  41
  42
  43 /* lazy_casereader callback function to instantiate a casereader
  44    from the datasheet. */
  45 static struct casereader *
  46 lazy_callback (void *ds_)
  47 {
  48   struct datasheet *ds = ds_;
  49   return datasheet_make_reader (ds);
  50 }
  51
  52
  53 /* Maximum size of datasheet supported for model checking
  54    purposes. */
  55 #define MAX_ROWS 5
  56 #define MAX_COLS 5
  57
  58
  59 /* Checks that READER contains the ROW_CNT rows and COLUMN_CNT
  60    columns of data in ARRAY, reporting any errors via MC. */
  61 static void
  62 check_datasheet_casereader (struct mc *mc, struct casereader *reader,
  63                             double array[MAX_ROWS][MAX_COLS],
  64                             size_t row_cnt, size_t column_cnt)
  65 {
  66   if (casereader_get_case_cnt (reader) != row_cnt)
  67     {
  68       if (casereader_get_case_cnt (reader) == CASENUMBER_MAX
  69           && casereader_count_cases (reader) == row_cnt)
  70         mc_error (mc, "datasheet casereader has unknown case count");
  71       else
  72         mc_error (mc, "casereader row count (%lu) does not match "
  73                   "expected (%zu)",
  74                   (unsigned long int) casereader_get_case_cnt (reader),
  75                   row_cnt);
  76     }
  77   else if (casereader_get_value_cnt (reader) != column_cnt)
  78     mc_error (mc, "casereader column count (%zu) does not match "
  79               "expected (%zu)",
  80               casereader_get_value_cnt (reader), column_cnt);
  81   else
  82     {
  83       struct ccase c;
  84       size_t row;
  85
  86       for (row = 0; row < row_cnt; row++)
  87         {
  88           size_t col;
  89
  90           if (!casereader_read (reader, &c))
  91             {
  92               mc_error (mc, "casereader_read failed reading row %zu of %zu "
  93                         "(%zu columns)", row, row_cnt, column_cnt);
  94               return;
  95             }
  96
  97           for (col = 0; col < column_cnt; col++)
  98             if (case_num_idx (&c, col) != array[row][col])
  99               mc_error (mc, "element %zu,%zu (of %zu,%zu) differs: "
 100                         "%g != %g",
 101                         row, col, row_cnt, column_cnt,
 102                         case_num_idx (&c, col), array[row][col]);
 103
 104           case_destroy (&c);
 105         }
 106
 107       if (casereader_read (reader, &c))
 108         mc_error (mc, "casereader has extra cases (expected %zu)", row_cnt);
 109     }
 110 }
 111
 112 /* Checks that datasheet DS contains has ROW_CNT rows, COLUMN_CNT
 113    columns, and the same contents as ARRAY, reporting any
 114    mismatches via mc_error.  Then, adds DS to MC as a new state. */
 115 static void
 116 check_datasheet (struct mc *mc, struct datasheet *ds,
 117                  double array[MAX_ROWS][MAX_COLS],
 118                  size_t row_cnt, size_t column_cnt)
 119 {
 120   struct datasheet *ds2;
 121   struct casereader *reader;
 122   unsigned long int serial = 0;
 123
 124   assert (row_cnt < MAX_ROWS);
 125   assert (column_cnt < MAX_COLS);
 126
 127   /* If it is a duplicate hash, discard the state before checking
 128      its consistency, to save time. */
 129   if (mc_discard_dup_state (mc, hash_datasheet (ds)))
 130     {
 131       datasheet_destroy (ds);
 132       return;
 133     }
 134
 135   /* Check contents of datasheet via datasheet functions. */
 136   if (row_cnt != datasheet_get_row_cnt (ds))
 137     mc_error (mc, "row count (%lu) does not match expected (%zu)",
 138               (unsigned long int) datasheet_get_row_cnt (ds), row_cnt);
 139   else if (column_cnt != datasheet_get_column_cnt (ds))
 140     mc_error (mc, "column count (%zu) does not match expected (%zu)",
 141               datasheet_get_column_cnt (ds), column_cnt);
 142   else
 143     {
 144       size_t row, col;
 145
 146       for (row = 0; row < row_cnt; row++)
 147         for (col = 0; col < column_cnt; col++)
 148           {
 149             union value v;
 150             if (!datasheet_get_value (ds, row, col, &v, 1))
 151               NOT_REACHED ();
 152             if (v.f != array[row][col])
 153               mc_error (mc, "element %zu,%zu (of %zu,%zu) differs: %g != %g",
 154                         row, col, row_cnt, column_cnt, v.f, array[row][col]);
 155           }
 156     }
 157
 158   /* Check that datasheet contents are correct when read through
 159      casereader. */
 160   ds2 = clone_datasheet (ds);
 161   reader = datasheet_make_reader (ds2);
 162   check_datasheet_casereader (mc, reader, array, row_cnt, column_cnt);
 163   casereader_destroy (reader);
 164
 165   /* Check that datasheet contents are correct when read through
 166      casereader with lazy_casereader wrapped around it.  This is
 167      valuable because otherwise there is no non-GUI code that
 168      uses the lazy_casereader. */
 169   ds2 = clone_datasheet (ds);
 170   reader = lazy_casereader_create (column_cnt, row_cnt,
 171                                    lazy_callback, ds2, &serial);
 172   check_datasheet_casereader (mc, reader, array, row_cnt, column_cnt);
 173   if (lazy_casereader_destroy (reader, serial))
 174     {
 175       /* Lazy casereader was never instantiated.  This will
 176          only happen if there are no rows (because in that case
 177          casereader_read never gets called). */
 178       datasheet_destroy (ds2);
 179       if (row_cnt != 0)
 180         mc_error (mc, "lazy casereader not instantiated, but should "
 181                   "have been (size %zu,%zu)", row_cnt, column_cnt);
 182     }
 183   else
 184     {
 185       /* Lazy casereader was instantiated.  This is the common
 186          case, in which some casereader operation
 187          (casereader_read in this case) was performed on the
 188          lazy casereader. */
 189       casereader_destroy (reader);
 190       if (row_cnt == 0)
 191         mc_error (mc, "lazy casereader instantiated, but should not "
 192                   "have been (size %zu,%zu)", row_cnt, column_cnt);
 193     }
 194
 195   mc_add_state (mc, ds);
 196 }
 197
 198 /* Extracts the contents of DS into DATA. */
 199 static void
 200 extract_data (const struct datasheet *ds, double data[MAX_ROWS][MAX_COLS])
 201 {
 202   size_t column_cnt = datasheet_get_column_cnt (ds);
 203   size_t row_cnt = datasheet_get_row_cnt (ds);
 204   size_t row, col;
 205
 206   assert (row_cnt < MAX_ROWS);
 207   assert (column_cnt < MAX_COLS);
 208   for (row = 0; row < row_cnt; row++)
 209     for (col = 0; col < column_cnt; col++)
 210       {
 211         union value v;
 212         if (!datasheet_get_value (ds, row, col, &v, 1))
 213           NOT_REACHED ();
 214         data[row][col] = v.f;
 215       }
 216 }
 217
 218 /* Clones the structure and contents of ODS into *DS,
 219    and the contents of ODATA into DATA. */
 220 static void
 221 clone_model (const struct datasheet *ods, double odata[MAX_ROWS][MAX_COLS],
 222              struct datasheet **ds, double data[MAX_ROWS][MAX_COLS])
 223 {
 224   *ds = clone_datasheet (ods);
 225   memcpy (data, odata, MAX_ROWS * MAX_COLS * sizeof **data);
 226 }
 227
 228 /* "init" function for struct mc_class. */
 229 static void
 230 datasheet_mc_init (struct mc *mc)
 231 {
 232   struct datasheet_test_params *params = mc_get_aux (mc);
 233   struct datasheet *ds;
 234
 235   if (params->backing_rows == 0 && params->backing_cols == 0)
 236     {
 237       /* Create unbacked datasheet. */
 238       ds = datasheet_create (NULL);
 239       mc_name_operation (mc, "empty datasheet");
 240       check_datasheet (mc, ds, NULL, 0, 0);
 241     }
 242   else
 243     {
 244       /* Create datasheet with backing. */
 245       struct casewriter *writer;
 246       struct casereader *reader;
 247       double data[MAX_ROWS][MAX_COLS];
 248       int row;
 249
 250       assert (params->backing_rows > 0 && params->backing_rows <= MAX_ROWS);
 251       assert (params->backing_cols > 0 && params->backing_cols <= MAX_COLS);
 252
 253       writer = mem_writer_create (params->backing_cols);
 254       for (row = 0; row < params->backing_rows; row++)
 255         {
 256           struct ccase c;
 257           int col;
 258
 259           case_create (&c, params->backing_cols);
 260           for (col = 0; col < params->backing_cols; col++)
 261             {
 262               double value = params->next_value++;
 263               data[row][col] = value;
 264               case_data_rw_idx (&c, col)->f = value;
 265             }
 266           casewriter_write (writer, &c);
 267         }
 268       reader = casewriter_make_reader (writer);
 269       assert (reader != NULL);
 270
 271       ds = datasheet_create (reader);
 272       mc_name_operation (mc, "datasheet with (%d,%d) backing",
 273                          params->backing_rows, params->backing_cols);
 274       check_datasheet (mc, ds, data,
 275                        params->backing_rows, params->backing_cols);
 276     }
 277 }
 278
 279 /* "mutate" function for struct mc_class. */
 280 static void
 281 datasheet_mc_mutate (struct mc *mc, const void *ods_)
 282 {
 283   struct datasheet_test_params *params = mc_get_aux (mc);
 284
 285   const struct datasheet *ods = ods_;
 286   double odata[MAX_ROWS][MAX_COLS];
 287   double data[MAX_ROWS][MAX_COLS];
 288   size_t column_cnt = datasheet_get_column_cnt (ods);
 289   size_t row_cnt = datasheet_get_row_cnt (ods);
 290   size_t pos, new_pos, cnt;
 291
 292   extract_data (ods, odata);
 293
 294   /* Insert all possible numbers of columns in all possible
 295      positions. */
 296   for (pos = 0; pos <= column_cnt; pos++)
 297     for (cnt = 0; cnt <= params->max_cols - column_cnt; cnt++)
 298       if (mc_include_state (mc))
 299         {
 300           struct datasheet *ds;
 301           union value new[MAX_COLS];
 302           size_t i, j;
 303
 304           mc_name_operation (mc, "insert %zu columns at %zu", cnt, pos);
 305           clone_model (ods, odata, &ds, data);
 306
 307           for (i = 0; i < cnt; i++)
 308             new[i].f = params->next_value++;
 309
 310           if (!datasheet_insert_columns (ds, new, cnt, pos))
 311             mc_error (mc, "datasheet_insert_columns failed");
 312
 313           for (i = 0; i < row_cnt; i++)
 314             {
 315               insert_range (&data[i][0], column_cnt, sizeof data[i][0],
 316                             pos, cnt);
 317               for (j = 0; j < cnt; j++)
 318                 data[i][pos + j] = new[j].f;
 319             }
 320
 321           check_datasheet (mc, ds, data, row_cnt, column_cnt + cnt);
 322         }
 323
 324   /* Delete all possible numbers of columns from all possible
 325      positions. */
 326   for (pos = 0; pos < column_cnt; pos++)
 327     for (cnt = 0; cnt < column_cnt - pos; cnt++)
 328       if (mc_include_state (mc))
 329         {
 330           struct datasheet *ds;
 331           size_t i;
 332
 333           mc_name_operation (mc, "delete %zu columns at %zu", cnt, pos);
 334           clone_model (ods, odata, &ds, data);
 335
 336           datasheet_delete_columns (ds, pos, cnt);
 337
 338           for (i = 0; i < row_cnt; i++)
 339             remove_range (&data[i], column_cnt, sizeof *data[i], pos, cnt);
 340
 341           check_datasheet (mc, ds, data, row_cnt, column_cnt - cnt);
 342         }
 343
 344   /* Move all possible numbers of columns from all possible
 345      existing positions to all possible new positions. */
 346   for (pos = 0; pos < column_cnt; pos++)
 347     for (cnt = 0; cnt < column_cnt - pos; cnt++)
 348       for (new_pos = 0; new_pos < column_cnt - cnt; new_pos++)
 349         if (mc_include_state (mc))
 350           {
 351             struct datasheet *ds;
 352             size_t i;
 353
 354             clone_model (ods, odata, &ds, data);
 355             mc_name_operation (mc, "move %zu columns from %zu to %zu",
 356                                cnt, pos, new_pos);
 357
 358             datasheet_move_columns (ds, pos, new_pos, cnt);
 359
 360             for (i = 0; i < row_cnt; i++)
 361               move_range (&data[i], column_cnt, sizeof data[i][0],
 362                           pos, new_pos, cnt);
 363
 364             check_datasheet (mc, ds, data, row_cnt, column_cnt);
 365           }
 366
 367   /* Insert all possible numbers of rows in all possible
 368      positions. */
 369   for (pos = 0; pos <= row_cnt; pos++)
 370     for (cnt = 0; cnt <= params->max_rows - row_cnt; cnt++)
 371       if (mc_include_state (mc))
 372         {
 373           struct datasheet *ds;
 374           struct ccase c[MAX_ROWS];
 375           size_t i, j;
 376
 377           clone_model (ods, odata, &ds, data);
 378           mc_name_operation (mc, "insert %zu rows at %zu", cnt, pos);
 379
 380           for (i = 0; i < cnt; i++)
 381             {
 382               case_create (&c[i], column_cnt);
 383               for (j = 0; j < column_cnt; j++)
 384                 case_data_rw_idx (&c[i], j)->f = params->next_value++;
 385             }
 386
 387           insert_range (data, row_cnt, sizeof data[pos], pos, cnt);
 388           for (i = 0; i < cnt; i++)
 389             for (j = 0; j < column_cnt; j++)
 390               data[i + pos][j] = case_num_idx (&c[i], j);
 391
 392           if (!datasheet_insert_rows (ds, pos, c, cnt))
 393             mc_error (mc, "datasheet_insert_rows failed");
 394
 395           check_datasheet (mc, ds, data, row_cnt + cnt, column_cnt);
 396         }
 397
 398   /* Delete all possible numbers of rows from all possible
 399      positions. */
 400   for (pos = 0; pos < row_cnt; pos++)
 401     for (cnt = 0; cnt < row_cnt - pos; cnt++)
 402       if (mc_include_state (mc))
 403         {
 404           struct datasheet *ds;
 405
 406           clone_model (ods, odata, &ds, data);
 407           mc_name_operation (mc, "delete %zu rows at %zu", cnt, pos);
 408
 409           datasheet_delete_rows (ds, pos, cnt);
 410
 411           remove_range (&data[0], row_cnt, sizeof data[0], pos, cnt);
 412
 413           check_datasheet (mc, ds, data, row_cnt - cnt, column_cnt);
 414         }
 415
 416   /* Move all possible numbers of rows from all possible existing
 417      positions to all possible new positions. */
 418   for (pos = 0; pos < row_cnt; pos++)
 419     for (cnt = 0; cnt < row_cnt - pos; cnt++)
 420       for (new_pos = 0; new_pos < row_cnt - cnt; new_pos++)
 421         if (mc_include_state (mc))
 422           {
 423             struct datasheet *ds;
 424
 425             clone_model (ods, odata, &ds, data);
 426             mc_name_operation (mc, "move %zu rows from %zu to %zu",
 427                                cnt, pos, new_pos);
 428
 429             datasheet_move_rows (ds, pos, new_pos, cnt);
 430
 431             move_range (&data[0], row_cnt, sizeof data[0],
 432                         pos, new_pos, cnt);
 433
 434             check_datasheet (mc, ds, data, row_cnt, column_cnt);
 435           }
 436 }
 437
 438 /* "destroy" function for struct mc_class. */
 439 static void
 440 datasheet_mc_destroy (const struct mc *mc UNUSED, void *ds_)
 441 {
 442   struct datasheet *ds = ds_;
 443   datasheet_destroy (ds);
 444 }
 445
 446 /* Executes the model checker on the datasheet test driver with
 447    the given OPTIONS and passing in the given PARAMS, which must
 448    point to a modifiable "struct datasheet_test_params".  If any
 449    value in PARAMS is out of range, it will be adjusted into the
 450    valid range before running the test.
 451
 452    Returns the results of the model checking run. */
 453 struct mc_results *
 454 datasheet_test (struct mc_options *options, void *params_)
 455 {
 456   struct datasheet_test_params *params = params_;
 457   static const struct mc_class datasheet_mc_class =
 458     {
 459       datasheet_mc_init,
 460       datasheet_mc_mutate,
 461       datasheet_mc_destroy,
 462     };
 463
 464   params->next_value = 1;
 465   params->max_rows = MIN (params->max_rows, MAX_ROWS);
 466   params->max_cols = MIN (params->max_cols, MAX_COLS);
 467   params->backing_rows = MIN (params->backing_rows, params->max_rows);
 468   params->backing_cols = MIN (params->backing_cols, params->max_cols);
 469
 470   mc_options_set_aux (options, params);
 471   return mc_run (&datasheet_mc_class, options);
 472 }