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