rotation works and is tested
[pspp] / src / language / dictionary / modify-variables.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 1997-9, 2000, 2010, 2011, 2012 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 <stdlib.h>
20
21 #include "data/dataset.h"
22 #include "data/dictionary.h"
23 #include "data/variable.h"
24 #include "language/command.h"
25 #include "language/lexer/lexer.h"
26 #include "language/lexer/variable-parser.h"
27 #include "libpspp/array.h"
28 #include "libpspp/assertion.h"
29 #include "libpspp/compiler.h"
30 #include "libpspp/i18n.h"
31 #include "libpspp/message.h"
32 #include "libpspp/misc.h"
33 #include "libpspp/str.h"
34
35 #include "gl/xalloc.h"
36
37 #include "gettext.h"
38 #define _(msgid) gettext (msgid)
39
40 /* These control the ordering produced by
41    compare_variables_given_ordering(). */
42 struct ordering
43   {
44     bool forward;               /* true=FORWARD, false=BACKWARD. */
45     bool positional;            /* true=POSITIONAL, false=ALPHA. */
46   };
47
48 /* Increasing order of variable index. */
49 static struct ordering forward_positional_ordering = {1, 1};
50
51 static int compare_variables_given_ordering (const void *, const void *,
52                                              const void *ordering);
53
54 /* Explains how to modify the variables in a dictionary. */
55 struct var_modification
56   {
57     /* New variable ordering. */
58     struct variable **reorder_vars;
59     size_t n_reorder;
60
61     /* DROP/KEEP information. */
62     struct variable **drop_vars;
63     size_t n_drop;
64
65     /* New variable names. */
66     struct variable **rename_vars;
67     char **new_names;
68     size_t n_rename;
69   };
70
71 static bool rearrange_dict (struct dictionary *d,
72                            const struct var_modification *vm);
73
74 /* Performs MODIFY VARS command. */
75 int
76 cmd_modify_vars (struct lexer *lexer, struct dataset *ds)
77 {
78   if (proc_make_temporary_transformations_permanent (ds))
79     msg (SE, _("%s may not be used after %s.  "
80                "Temporary transformations will be made permanent."),
81          "MODIFY VARS", "TEMPORARY");
82
83   /* Bits indicated whether we've already encountered a subcommand of this
84      type. */
85   unsigned int already_encountered = 0;
86
87   /* Return code. */
88   int ret_code = CMD_CASCADING_FAILURE;
89
90   /* What we are going to do to the active dataset. */
91   struct var_modification vm =
92     {
93       .reorder_vars = NULL,
94       .n_reorder = 0,
95       .rename_vars = NULL,
96       .new_names = NULL,
97       .n_rename = 0,
98       .drop_vars = NULL,
99       .n_drop = 0,
100     };
101
102   /* Parse each subcommand. */
103   lex_match (lexer, T_SLASH);
104   for (;;)
105     {
106       if (lex_match_id (lexer, "REORDER"))
107         {
108           if (already_encountered & 1)
109             {
110               lex_sbc_only_once ("REORDER");
111               goto done;
112             }
113           already_encountered |= 1;
114
115           struct variable **v = NULL;
116           size_t nv = 0;
117
118           lex_match (lexer, T_EQUALS);
119           do
120             {
121               struct ordering ordering;
122               size_t prev_nv = nv;
123
124               ordering.forward = ordering.positional = true;
125               for (;;)
126                 {
127                   if (lex_match_id (lexer, "FORWARD"))
128                     ordering.forward = true;
129                   else if (lex_match_id (lexer, "BACKWARD"))
130                     ordering.forward = false;
131                   else if (lex_match_id (lexer, "POSITIONAL"))
132                     ordering.positional = true;
133                   else if (lex_match_id (lexer, "ALPHA"))
134                     ordering.positional = false;
135                   else
136                     break;
137                 }
138
139               if (lex_match (lexer, T_ALL)
140                   || lex_token (lexer) == T_SLASH
141                   || lex_token (lexer) == T_ENDCMD)
142                 {
143                   if (prev_nv != 0)
144                     {
145                       msg (SE, _("Cannot specify ALL after specifying a set "
146                            "of variables."));
147                       goto done;
148                     }
149                   dict_get_vars_mutable (dataset_dict (ds), &v, &nv,
150                                          DC_SYSTEM);
151                 }
152               else
153                 {
154                   if (!lex_match (lexer, T_LPAREN))
155                     {
156                       lex_error_expecting (lexer, "`('");
157                       free (v);
158                       goto done;
159                     }
160                   if (!parse_variables (lexer, dataset_dict (ds), &v, &nv,
161                                         PV_APPEND | PV_NO_DUPLICATE))
162                     {
163                       free (v);
164                       goto done;
165                     }
166                   if (!lex_match (lexer, T_RPAREN))
167                     {
168                       lex_error_expecting (lexer, "`)'");
169                       free (v);
170                       goto done;
171                     }
172                 }
173
174               if (!ordering.positional)
175                 sort (&v[prev_nv], nv - prev_nv, sizeof *v,
176                       compare_variables_given_ordering, &ordering);
177               else if (!ordering.forward)
178                 reverse_array(&v[prev_nv], nv - prev_nv, sizeof *v);
179             }
180           while (lex_token (lexer) != T_SLASH
181                  && lex_token (lexer) != T_ENDCMD);
182
183           vm.reorder_vars = v;
184           vm.n_reorder = nv;
185         }
186       else if (lex_match_id (lexer, "RENAME"))
187         {
188           if (already_encountered & 2)
189             {
190               lex_sbc_only_once ("RENAME");
191               goto done;
192             }
193           already_encountered |= 2;
194
195           lex_match (lexer, T_EQUALS);
196           do
197             {
198               size_t prev_nv_1 = vm.n_rename;
199               size_t prev_nv_2 = vm.n_rename;
200
201               if (!lex_match (lexer, T_LPAREN))
202                 {
203                   lex_error_expecting (lexer, "`('");
204                   goto done;
205                 }
206               if (!parse_variables (lexer, dataset_dict (ds),
207                                     &vm.rename_vars, &vm.n_rename,
208                                     PV_APPEND | PV_NO_DUPLICATE))
209                 goto done;
210               if (!lex_match (lexer, T_EQUALS))
211                 {
212                   lex_error_expecting (lexer, "`='");
213                   goto done;
214                 }
215
216               if (!parse_DATA_LIST_vars (lexer, dataset_dict (ds),
217                                          &vm.new_names, &prev_nv_1, PV_APPEND))
218                 goto done;
219               if (prev_nv_1 != vm.n_rename)
220                 {
221                   msg (SE, _("Differing number of variables in old name list "
222                              "(%zu) and in new name list (%zu)."),
223                        vm.n_rename - prev_nv_2, prev_nv_1 - prev_nv_2);
224                   for (size_t i = 0; i < prev_nv_1; i++)
225                     free (vm.new_names[i]);
226                   free (vm.new_names);
227                   vm.new_names = NULL;
228                   goto done;
229                 }
230               if (!lex_match (lexer, T_RPAREN))
231                 {
232                   lex_error_expecting (lexer, "`)'");
233                   goto done;
234                 }
235             }
236           while (lex_token (lexer) != T_ENDCMD
237                  && lex_token (lexer) != T_SLASH);
238         }
239       else if (lex_match_id (lexer, "KEEP"))
240         {
241           if (already_encountered & 4)
242             {
243               msg (SE,
244                    _("%s subcommand may be given at most once.  It may "
245                      "not be given in conjunction with the %s subcommand."),
246                    "KEEP", "DROP");
247               goto done;
248             }
249           already_encountered |= 4;
250
251           struct variable **keep_vars, **drop_vars;
252           size_t n_keep, n_drop;
253           lex_match (lexer, T_EQUALS);
254           if (!parse_variables (lexer, dataset_dict (ds),
255                                 &keep_vars, &n_keep, PV_NONE))
256             goto done;
257
258           /* Transform the list of variables to keep into a list of
259              variables to drop.  First sort the keep list, then figure
260              out which variables are missing. */
261           sort (keep_vars, n_keep, sizeof *keep_vars,
262                 compare_variables_given_ordering,
263                 &forward_positional_ordering);
264
265           struct variable **all_vars;
266           size_t n_all;
267           dict_get_vars_mutable (dataset_dict (ds), &all_vars, &n_all, 0);
268           assert (n_all >= n_keep);
269
270           n_drop = n_all - n_keep;
271           drop_vars = xnmalloc (n_drop, sizeof *keep_vars);
272           if (set_difference (all_vars, n_all,
273                               keep_vars, n_keep,
274                               sizeof *all_vars,
275                               drop_vars,
276                               compare_variables_given_ordering,
277                               &forward_positional_ordering)
278               != n_drop)
279             NOT_REACHED ();
280
281           free (keep_vars);
282           free (all_vars);
283
284           vm.drop_vars = drop_vars;
285           vm.n_drop = n_drop;
286         }
287       else if (lex_match_id (lexer, "DROP"))
288         {
289           struct variable **drop_vars;
290           size_t n_drop;
291
292           if (already_encountered & 4)
293             {
294               msg (SE, _("%s subcommand may be given at most once.  It may "
295                          "not be given in conjunction with the %s "
296                          "subcommand."),
297                    "DROP", "KEEP"
298                 );
299               goto done;
300             }
301           already_encountered |= 4;
302
303           lex_match (lexer, T_EQUALS);
304           if (!parse_variables (lexer, dataset_dict (ds),
305                                 &drop_vars, &n_drop, PV_NONE))
306             goto done;
307           vm.drop_vars = drop_vars;
308           vm.n_drop = n_drop;
309
310           if (n_drop == dict_get_n_vars (dataset_dict (ds)))
311             {
312               msg (SE, _("%s may not be used to delete all variables "
313                          "from the active dataset dictionary.  "
314                          "Use %s instead."), "MODIFY VARS", "NEW FILE");
315               goto done;
316             }
317         }
318       else if (lex_match_id (lexer, "MAP"))
319         {
320           struct dictionary *temp = dict_clone (dataset_dict (ds));
321           int success = rearrange_dict (temp, &vm);
322           if (success)
323             {
324               /* FIXME: display new dictionary. */
325             }
326           dict_unref (temp);
327         }
328       else
329         {
330           if (lex_token (lexer) == T_ID)
331             msg (SE, _("Unrecognized subcommand name `%s'."),
332                  lex_tokcstr (lexer));
333           else
334             msg (SE, _("Subcommand name expected."));
335           goto done;
336         }
337
338       if (lex_token (lexer) == T_ENDCMD)
339         break;
340       if (lex_token (lexer) != T_SLASH)
341         {
342           lex_error_expecting (lexer, "`/'", "`.'");
343           goto done;
344         }
345       lex_get (lexer);
346     }
347
348   if (already_encountered & (1 | 4))
349     {
350       /* Read the data. */
351       if (!proc_execute (ds))
352         goto done;
353     }
354
355   if (!rearrange_dict (dataset_dict (ds), &vm))
356     goto done;
357
358   ret_code = CMD_SUCCESS;
359
360 done:
361   free (vm.reorder_vars);
362   free (vm.rename_vars);
363   if (vm.new_names)
364     for (size_t i = 0; i < vm.n_rename; i++)
365       free (vm.new_names[i]);
366   free (vm.new_names);
367   free (vm.drop_vars);
368   return ret_code;
369 }
370
371 /* Compares A and B according to the settings in ORDERING, returning a
372    strcmp()-type result. */
373 static int
374 compare_variables_given_ordering (const void *a_, const void *b_,
375                                   const void *ordering_)
376 {
377   struct variable *const *pa = a_;
378   struct variable *const *pb = b_;
379   const struct variable *a = *pa;
380   const struct variable *b = *pb;
381   const struct ordering *ordering = ordering_;
382
383   int result;
384   if (ordering->positional)
385     {
386       size_t a_index = var_get_dict_index (a);
387       size_t b_index = var_get_dict_index (b);
388       result = a_index < b_index ? -1 : a_index > b_index;
389     }
390   else
391     result = utf8_strcasecmp (var_get_name (a), var_get_name (b));
392   if (!ordering->forward)
393     result = -result;
394   return result;
395 }
396
397 /* Pairs a variable with a new name. */
398 struct var_renaming
399   {
400     struct variable *var;
401     const char *new_name;
402   };
403
404 /* A algo_compare_func that compares new_name members in struct var_renaming
405    structures A and B. */
406 static int
407 compare_var_renaming_by_new_name (const void *a_, const void *b_,
408                                   const void *aux UNUSED)
409 {
410   const struct var_renaming *a = a_;
411   const struct var_renaming *b = b_;
412
413   return utf8_strcasecmp (a->new_name, b->new_name);
414 }
415
416 /* Returns true if performing VM on dictionary D would not cause problems such
417    as duplicate variable names.  Returns false otherwise, and issues an error
418    message. */
419 static bool
420 validate_var_modification (const struct dictionary *d,
421                            const struct var_modification *vm)
422 {
423   /* Variable reordering can't be a problem, so we don't simulate
424      it.  Variable renaming can cause duplicate names, but
425      dropping variables can eliminate them, so we simulate both
426      of those. */
427
428   /* All variables, in index order. */
429   struct variable **all_vars;
430   size_t n_all;
431   dict_get_vars_mutable (d, &all_vars, &n_all, 0);
432
433   /* Drop variables, in index order. */
434   size_t n_drop = vm->n_drop;
435   struct variable **drop_vars = xnmalloc (n_drop, sizeof *drop_vars);
436   memcpy (drop_vars, vm->drop_vars, n_drop * sizeof *drop_vars);
437   sort (drop_vars, n_drop, sizeof *drop_vars,
438         compare_variables_given_ordering, &forward_positional_ordering);
439
440   /* Keep variables, in index order. */
441   assert (n_all >= n_drop);
442   size_t n_keep = n_all - n_drop;
443   struct variable **keep_vars = xnmalloc (n_keep, sizeof *keep_vars);
444   if (set_difference (all_vars, n_all,
445                       drop_vars, n_drop,
446                       sizeof *all_vars,
447                       keep_vars,
448                       compare_variables_given_ordering,
449                       &forward_positional_ordering) != n_keep)
450     NOT_REACHED ();
451
452   /* Copy variables into var_renaming array. */
453   struct var_renaming *var_renaming = xnmalloc (n_keep, sizeof *var_renaming);
454   for (size_t i = 0; i < n_keep; i++)
455     {
456       var_renaming[i].var = keep_vars[i];
457       var_renaming[i].new_name = var_get_name (keep_vars[i]);
458     }
459
460   /* Rename variables in var_renaming array. */
461   for (size_t i = 0; i < vm->n_rename; i++)
462     {
463       struct variable *const *kv;
464       struct var_renaming *vr;
465
466       /* Get the var_renaming element. */
467       kv = binary_search (keep_vars, n_keep, sizeof *keep_vars,
468                           &vm->rename_vars[i],
469                           compare_variables_given_ordering,
470                           &forward_positional_ordering);
471       if (kv == NULL)
472         continue;
473       vr = var_renaming + (kv - keep_vars);
474
475       vr->new_name = vm->new_names[i];
476     }
477
478   /* Sort var_renaming array by new names and check for duplicates. */
479   sort (var_renaming, n_keep, sizeof *var_renaming,
480         compare_var_renaming_by_new_name, NULL);
481   bool ok = !adjacent_find_equal (var_renaming, n_keep, sizeof *var_renaming,
482                                   compare_var_renaming_by_new_name, NULL);
483
484   /* Clean up. */
485   free (all_vars);
486   free (keep_vars);
487   free (drop_vars);
488   free (var_renaming);
489
490   return ok;
491 }
492
493 /* Reorders, removes, and renames variables in dictionary D according to VM.
494    Returns true if successful, false if there would have been duplicate
495    variable names if the modifications had been carried out.  In the latter
496    case, the dictionary is not modified. */
497 static bool
498 rearrange_dict (struct dictionary *d, const struct var_modification *vm)
499 {
500   /* Check whether the modifications will cause duplicate names. */
501   if (!validate_var_modification (d, vm))
502     return false;
503
504   /* Record the old names of variables to rename.  After variables are deleted,
505      we can't depend on the variables to still exist, but we can still look
506      them up by name. */
507   char **rename_old_names = xnmalloc (vm->n_rename, sizeof *rename_old_names);
508   for (size_t i = 0; i < vm->n_rename; i++)
509     rename_old_names[i] = xstrdup (var_get_name (vm->rename_vars[i]));
510
511   /* Reorder and delete variables. */
512   dict_reorder_vars (d, vm->reorder_vars, vm->n_reorder);
513   dict_delete_vars (d, vm->drop_vars, vm->n_drop);
514
515   /* Compose lists of variables to rename and their new names. */
516   struct variable **rename_vars = xnmalloc (vm->n_rename, sizeof *rename_vars);
517   char **rename_new_names = xnmalloc (vm->n_rename, sizeof *rename_new_names);
518   size_t n_rename = 0;
519   for (size_t i = 0; i < vm->n_rename; i++)
520     {
521       struct variable *var = dict_lookup_var (d, rename_old_names[i]);
522       if (var == NULL)
523         continue;
524
525       rename_vars[n_rename] = var;
526       rename_new_names[n_rename] = vm->new_names[i];
527       n_rename++;
528     }
529
530   /* Do renaming. */
531   if (dict_rename_vars (d, rename_vars, rename_new_names, n_rename,
532                         NULL) == 0)
533     NOT_REACHED ();
534
535   /* Clean up. */
536   for (size_t i = 0; i < vm->n_rename; i++)
537     free (rename_old_names[i]);
538   free (rename_old_names);
539   free (rename_vars);
540   free (rename_new_names);
541
542   return true;
543 }