src/data/format.c (fmt_affix_free): Fix memory leak
[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   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 }