LOOP: Convert tests to Autotest framework.
[pspp] / 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 }