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
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
test_state_destroy(const struct test_params * params,struct test_state * ts)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 *
test_state_clone(const struct test_params * params,const struct test_state * ots)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
test_model_extract(const struct test_params * params,const struct test_state * ts,struct test_model * tm)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
check_state(struct mc * mc,struct test_state * ts,const struct test_model * tm)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
next_data(unsigned char * data,int n,int n_values)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
copy_columns(const void * src_,void * dst_,void * copy_)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
sparse_xarray_mc_init(struct mc * mc)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
sparse_xarray_mc_mutate(struct mc * mc,const void * ots_)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, ©_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, ©_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
sparse_xarray_mc_destroy(const struct mc * mc UNUSED,void * ts_)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
usage(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 fputs ("\nOther options:\n"
476 " --help Display this help message\n"
477 "\nReport bugs to <bug-gnu-pspp@gnu.org>\n",
478 stdout);
479 exit (0);
480 }
481
482 enum
483 {
484 OPT_COLUMNS,
485 OPT_MAX_ROWS,
486 OPT_MAX_MEMORY_ROWS,
487 OPT_VALUES,
488 OPT_XARRAYS,
489 OPT_NO_WRITE_CELLS,
490 OPT_NO_WRITE_ROWS,
491 OPT_NO_WRITE_COLUMNS,
492 OPT_NO_COPY_COLUMNS,
493 OPT_HELP,
494 N_SPARSE_XARRAY_OPTIONS
495 };
496
497 static struct argv_option sparse_xarray_argv_options[N_SPARSE_XARRAY_OPTIONS] =
498 {
499 {"columns", 0, required_argument, OPT_COLUMNS},
500 {"max-rows", 0, required_argument, OPT_MAX_ROWS},
501 {"max-memory-rows", 0, required_argument, OPT_MAX_MEMORY_ROWS},
502 {"values", 0, required_argument, OPT_VALUES},
503 {"xarrays", 0, required_argument, OPT_XARRAYS},
504 {"no-write-cells", 0, no_argument, OPT_NO_WRITE_CELLS},
505 {"no-write-rows", 0, no_argument, OPT_NO_WRITE_ROWS},
506 {"no-write-columns", 0, no_argument, OPT_NO_WRITE_COLUMNS},
507 {"no-copy-columns", 0, no_argument, OPT_NO_COPY_COLUMNS},
508 {"help", 'h', no_argument, OPT_HELP},
509 };
510
511 static void
sparse_xarray_option_callback(int id,void * params_)512 sparse_xarray_option_callback (int id, void *params_)
513 {
514 struct test_params *params = params_;
515 switch (id)
516 {
517 case OPT_COLUMNS:
518 params->n_columns = atoi (optarg);
519 break;
520
521 case OPT_MAX_ROWS:
522 params->max_rows = atoi (optarg);
523 break;
524
525 case OPT_MAX_MEMORY_ROWS:
526 params->max_memory_rows = atoi (optarg);
527 break;
528
529 case OPT_VALUES:
530 params->n_values = atoi (optarg);
531 break;
532
533 case OPT_XARRAYS:
534 params->n_xarrays = atoi (optarg);
535 break;
536
537 case OPT_NO_WRITE_CELLS:
538 params->write_cells = false;
539 break;
540
541 case OPT_NO_WRITE_ROWS:
542 params->write_rows = false;
543 break;
544
545 case OPT_NO_WRITE_COLUMNS:
546 params->write_columns = false;
547 break;
548
549 case OPT_NO_COPY_COLUMNS:
550 params->copy_within_xarray = false;
551 break;
552
553 case OPT_HELP:
554 usage ();
555 break;
556
557 default:
558 NOT_REACHED ();
559 }
560 }
561
562 int
main(int argc,char * argv[])563 main (int argc, char *argv[])
564 {
565 static const struct mc_class sparse_xarray_mc_class =
566 {
567 sparse_xarray_mc_init,
568 sparse_xarray_mc_mutate,
569 sparse_xarray_mc_destroy,
570 };
571
572 struct test_params params;
573 struct mc_options *options;
574 struct mc_results *results;
575 struct argv_parser *parser;
576 int verbosity;
577 bool success;
578
579 set_program_name (argv[0]);
580
581 /* Default parameters. */
582 params.n_columns = 3;
583 params.max_rows = 3;
584 params.max_memory_rows = 3;
585 params.n_values = 3;
586 params.n_xarrays = 1;
587 params.write_cells = true;
588 params.write_rows = true;
589 params.write_columns = true;
590 params.copy_within_xarray = true;
591
592 /* Parse command line. */
593 parser = argv_parser_create ();
594 options = mc_options_create ();
595 mc_options_register_argv_parser (options, parser);
596 argv_parser_add_options (parser, sparse_xarray_argv_options,
597 N_SPARSE_XARRAY_OPTIONS,
598 sparse_xarray_option_callback, ¶ms);
599 if (!argv_parser_run (parser, argc, argv))
600 exit (EXIT_FAILURE);
601 argv_parser_destroy (parser);
602 verbosity = mc_options_get_verbosity (options);
603
604 /* Force parameters into allowed ranges. */
605 params.n_columns = MAX (0, MIN (params.n_columns, MAX_COLS));
606 params.max_rows = MAX (0, MIN (params.max_rows, MAX_ROWS));
607 params.max_memory_rows = MAX (0, MIN (params.max_memory_rows,
608 params.max_rows));
609 params.n_values = MIN (254, MAX (1, params.n_values));
610 params.n_xarrays = MAX (1, MIN (2, params.n_xarrays));
611 mc_options_set_aux (options, ¶ms);
612 results = mc_run (&sparse_xarray_mc_class, options);
613
614 /* Output results. */
615 success = (mc_results_get_stop_reason (results) != MC_MAX_ERROR_COUNT
616 && mc_results_get_stop_reason (results) != MC_INTERRUPTED);
617 if (verbosity > 0 || !success)
618 {
619 printf ("Parameters: "
620 "--columns=%d --max-rows=%d --max-memory-rows=%d --values=%d "
621 "--xarrays=%d",
622 params.n_columns, params.max_rows, params.max_memory_rows,
623 params.n_values, params.n_xarrays);
624 if (!params.write_cells)
625 printf (" --no-write-cells");
626 if (!params.write_rows)
627 printf (" --no-write-rows");
628 if (!params.write_columns)
629 printf (" --no-write-columns");
630 if (!params.copy_within_xarray)
631 printf (" --no-copy-columns");
632 printf ("\n\n");
633 mc_results_print (results, stdout);
634 }
635 mc_results_destroy (results);
636
637 return success ? 0 : EXIT_FAILURE;
638 }
639