Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / vars-prs.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
5    This program is free software; you can redistribute it and/or
6    modify it under the terms of the GNU General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful, but
11    WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
18    02111-1307, USA. */
19
20 #include <config.h>
21 #include "var.h"
22 #include <ctype.h>
23 #include <stdlib.h>
24 #include "alloc.h"
25 #include "bitvector.h"
26 #include "dictionary.h"
27 #include "error.h"
28 #include "hash.h"
29 #include "lexer.h"
30 #include "misc.h"
31 #include "str.h"
32
33 /* Parses a name as a variable within VS and returns the variable
34    if successful.  On failure emits an error message and returns
35    a null pointer. */
36 static struct variable *
37 parse_vs_variable (const struct var_set *vs)
38 {
39   struct variable *vp;
40
41   if (token != T_ID)
42     {
43       lex_error ("expecting variable name");
44       return NULL;
45     }
46
47   vp = var_set_lookup_var (vs, tokid);
48   if (vp == NULL)
49     msg (SE, _("%s is not a variable name."), tokid);
50   lex_get ();
51
52   return vp;
53 }
54
55 /* Parses a variable name in dictionary D and returns the
56    variable if successful.  On failure emits an error message and
57    returns a null pointer. */
58 struct variable *
59 parse_dict_variable (const struct dictionary *d) 
60 {
61   struct var_set *vs = var_set_create_from_dict (d);
62   struct variable *var = parse_vs_variable (vs);
63   var_set_destroy (vs);
64   return var;
65 }
66
67 /* Parses a variable name in default_dict and returns the
68    variable if successful.  On failure emits an error message and
69    returns a null pointer. */
70 struct variable *
71 parse_variable (void)
72 {
73   return parse_dict_variable (default_dict);
74 }
75
76 /* Returns the dictionary class corresponding to a variable named
77    NAME. */
78 enum dict_class
79 dict_class_from_id (const char *name) 
80 {
81   assert (name != NULL);
82
83   switch (name[0]) 
84     {
85     default:
86       return DC_ORDINARY;
87     case '$':
88       return DC_SYSTEM;
89     case '#':
90       return DC_SCRATCH;
91     }
92 }
93
94 /* Returns the name of dictionary class DICT_CLASS. */
95 const char *
96 dict_class_to_name (enum dict_class dict_class) 
97 {
98   switch (dict_class) 
99     {
100     case DC_ORDINARY:
101       return _("ordinary");
102     case DC_SYSTEM:
103       return _("system");
104     case DC_SCRATCH:
105       return _("scratch");
106     default:
107       assert (0);
108       abort ();
109     }
110 }
111
112 /* Parses a set of variables from dictionary D given options
113    OPTS.  Resulting list of variables stored in *VAR and the
114    number of variables into *CNT.  Returns nonzero only if
115    successful. */
116 int
117 parse_variables (const struct dictionary *d, struct variable ***var,
118                  int *cnt, int opts) 
119 {
120   struct var_set *vs;
121   int success;
122
123   assert (d != NULL);
124   assert (var != NULL);
125   assert (cnt != NULL);
126
127   vs = var_set_create_from_dict (d);
128   success = parse_var_set_vars (vs, var, cnt, opts);
129   var_set_destroy (vs);
130   return success;
131 }
132
133 /* Note that if parse_variables() returns 0, *v is free()'d.
134    Conversely, if parse_variables() returns non-zero, then *nv is
135    nonzero and *v is non-NULL. */
136 int
137 parse_var_set_vars (const struct var_set *vs, 
138                     struct variable ***v, int *nv,
139                     int pv_opts)
140 {
141   size_t vs_var_cnt;
142   int i;
143   char *included = NULL;
144
145   struct variable *v1, *v2;
146   int count, mv;
147   enum dict_class dict_class;
148
149   assert (vs != NULL);
150   assert (v != NULL);
151   assert (nv != NULL);
152
153   /* At most one of PV_NUMERIC, PV_STRING, PV_SAME_TYPE may be
154      specified. */
155   assert ((((pv_opts & PV_NUMERIC) != 0)
156            + ((pv_opts & PV_STRING) != 0)
157            + ((pv_opts & PV_SAME_TYPE) != 0)) <= 1);
158
159   /* PV_DUPLICATE and PV_NO_DUPLICATE are incompatible. */
160   assert (!(pv_opts & PV_DUPLICATE) || !(pv_opts & PV_NO_DUPLICATE));
161
162   vs_var_cnt = var_set_get_cnt (vs);
163
164   if (!(pv_opts & PV_APPEND))
165     {
166       *v = NULL;
167       *nv = 0;
168       mv = 0;
169     }
170   else
171     mv = *nv;
172
173   if (!(pv_opts & PV_DUPLICATE))
174     {
175       included = xmalloc (vs_var_cnt);
176       memset (included, 0, vs_var_cnt);
177       for (i = 0; i < *nv; i++)
178         included[(*v)[i]->index] = 1;
179     }
180
181   do
182     {
183       if (lex_match (T_ALL))
184         {
185           v1 = var_set_get_var (vs, 0);
186           v2 = var_set_get_var (vs, vs_var_cnt - 1);
187           count = vs_var_cnt;
188           dict_class = DC_ORDINARY;
189         }
190       else
191         {
192           v1 = parse_vs_variable (vs);
193           if (!v1)
194             goto fail;
195
196           if (lex_match (T_TO))
197             {
198               enum dict_class dict_class_2;
199
200               v2 = parse_vs_variable (vs);
201               if (!v2)
202                 {
203                   lex_error ("expecting variable name");
204                   goto fail;
205                 }
206
207               count = v2->index - v1->index + 1;
208               if (count < 1)
209                 {
210                   msg (SE, _("%s TO %s is not valid syntax since %s "
211                        "precedes %s in the dictionary."),
212                        v1->name, v2->name, v2->name, v1->name);
213                   goto fail;
214                 }
215
216               dict_class = dict_class_from_id (v1->name);
217               dict_class_2 = dict_class_from_id (v2->name);
218               if (dict_class != dict_class_2)
219                 {
220                   msg (SE, _("When using the TO keyword to specify several "
221                              "variables, both variables must be from "
222                              "the same variable dictionaries, of either "
223                              "ordinary, scratch, or system variables.  "
224                              "%s is a %s variable, whereas %s is %s."),
225                        v1->name, dict_class_to_name (dict_class),
226                        v2->name, dict_class_to_name (dict_class_2));
227                   goto fail;
228                 }
229             }
230           else
231             {
232               v2 = v1;
233               count = 1;
234               dict_class = dict_class_from_id (v1->name);
235             }
236           if (dict_class == DC_SCRATCH && (pv_opts & PV_NO_SCRATCH))
237             {
238               msg (SE, _("Scratch variables (such as %s) are not allowed "
239                          "here."), v1->name);
240               goto fail;
241             }
242         }
243
244       if (*nv + count > mv)
245         {
246           mv += ROUND_UP (count, 16);
247           *v = xrealloc (*v, mv * sizeof **v);
248         }
249
250       /* Add v1...v2 to the list. */
251       for (i = v1->index; i <= v2->index; i++)
252         {
253           struct variable *add = var_set_get_var (vs, i);
254
255           /* Skip over other dictionaries. */
256           if (dict_class != dict_class_from_id (add->name))
257             continue;
258
259           /* Different kinds of errors. */
260           if ((pv_opts & PV_NUMERIC) && add->type != NUMERIC)
261             msg (SW, _("%s is not a numeric variable.  It will not be "
262                        "included in the variable list."), add->name);
263           else if ((pv_opts & PV_STRING) && add->type != ALPHA)
264             msg (SE, _("%s is not a string variable.  It will not be "
265                        "included in the variable list."), add->name);
266           else if ((pv_opts & PV_SAME_TYPE) && *nv
267                    && add->type != (*v)[0]->type)
268             msg (SE, _("%s and %s are not the same type.  All variables in "
269                        "this variable list must be of the same type.  %s "
270                        "will be omitted from list."),
271                  (*v)[0]->name, add->name, add->name);
272           else if ((pv_opts & PV_NO_DUPLICATE) && included[add->index])
273             msg (SE, _("Variable %s appears twice in variable list."),
274                  add->name);
275           else {
276             /* Success--add the variable to the list. */
277             if ((pv_opts & PV_DUPLICATE) || !included[add->index])
278               {
279                 (*v)[(*nv)++] = var_set_get_var (vs, i);
280                 if (!(pv_opts & PV_DUPLICATE))
281                   included[add->index] = 1;
282               }
283
284             /* Next. */
285             continue;
286           }
287
288           /* Arrive here only on failure. */
289           if (pv_opts & PV_SINGLE)
290             goto fail;
291         }
292
293       /* We finished adding v1...v2 to the list. */
294       if (pv_opts & PV_SINGLE)
295         return 1;
296       lex_match (',');
297     }
298   while ((token == T_ID && var_set_lookup_var (vs, tokid) != NULL)
299          || token == T_ALL);
300
301   if (!(pv_opts & PV_DUPLICATE))
302     free (included);
303   if (!*nv)
304     goto fail;
305   return 1;
306
307 fail:
308   free (*v);
309   *v = NULL;
310   *nv = 0;
311   if (!(pv_opts & PV_DUPLICATE))
312     free (included);
313   return 0;
314 }
315
316 /* Extracts a numeric suffix from variable name S, copying it
317    into string R.  Sets *D to the length of R and *N to its
318    value. */
319 static int
320 extract_num (char *s, char *r, int *n, int *d)
321 {
322   char *cp;
323
324   /* Find first digit. */
325   cp = s + strlen (s) - 1;
326   while (isdigit ((unsigned char) *cp) && cp > s)
327     cp--;
328   cp++;
329
330   /* Extract root. */
331   strncpy (r, s, cp - s);
332   r[cp - s] = 0;
333
334   /* Count initial zeros. */
335   *n = *d = 0;
336   while (*cp == '0')
337     {
338       (*d)++;
339       cp++;
340     }
341
342   /* Extract value. */
343   while (isdigit ((unsigned char) *cp))
344     {
345       (*d)++;
346       *n = (*n * 10) + (*cp - '0');
347       cp++;
348     }
349
350   /* Sanity check. */
351   if (*n == 0 && *d == 0)
352     {
353       msg (SE, _("incorrect use of TO convention"));
354       return 0;
355     }
356   return 1;
357 }
358
359 /* Parses a list of variable names according to the DATA LIST version
360    of the TO convention.  */
361 int
362 parse_DATA_LIST_vars (char ***names, int *nnames, int pv_opts)
363 {
364   int n1, n2;
365   int d1, d2;
366   int n;
367   int nvar, mvar;
368   char *name1, *name2;
369   char *root1, *root2;
370   int success = 0;
371
372   assert (names != NULL);
373   assert (nnames != NULL);
374   assert ((pv_opts & ~(PV_APPEND | PV_SINGLE
375                        | PV_NO_SCRATCH | PV_NO_DUPLICATE)) == 0);
376   /* FIXME: PV_NO_DUPLICATE is not implemented. */
377
378   if (pv_opts & PV_APPEND)
379     nvar = mvar = *nnames;
380   else
381     {
382       nvar = mvar = 0;
383       *names = NULL;
384     }
385
386   name1 = xmalloc (36);
387   name2 = &name1[1 * 9];
388   root1 = &name1[2 * 9];
389   root2 = &name1[3 * 9];
390   do
391     {
392       if (token != T_ID)
393         {
394           lex_error ("expecting variable name");
395           goto fail;
396         }
397       if (dict_class_from_id (tokid) == DC_SCRATCH
398           && (pv_opts & PV_NO_SCRATCH))
399         {
400           msg (SE, _("Scratch variables not allowed here."));
401           goto fail;
402         }
403       strcpy (name1, tokid);
404       lex_get ();
405       if (token == T_TO)
406         {
407           lex_get ();
408           if (token != T_ID)
409             {
410               lex_error ("expecting variable name");
411               goto fail;
412             }
413           strcpy (name2, tokid);
414           lex_get ();
415
416           if (!extract_num (name1, root1, &n1, &d1)
417               || !extract_num (name2, root2, &n2, &d2))
418             goto fail;
419
420           if (strcmp (root1, root2))
421             {
422               msg (SE, _("Prefixes don't match in use of TO convention."));
423               goto fail;
424             }
425           if (n1 > n2)
426             {
427               msg (SE, _("Bad bounds in use of TO convention."));
428               goto fail;
429             }
430           if (d2 > d1)
431             d2 = d1;
432
433           if (mvar < nvar + (n2 - n1 + 1))
434             {
435               mvar += ROUND_UP (n2 - n1 + 1, 16);
436               *names = xrealloc (*names, mvar * sizeof **names);
437             }
438
439           for (n = n1; n <= n2; n++)
440             {
441               (*names)[nvar] = xmalloc (9);
442               sprintf ((*names)[nvar], "%s%0*d", root1, d1, n);
443               nvar++;
444             }
445         }
446       else
447         {
448           if (nvar >= mvar)
449             {
450               mvar += 16;
451               *names = xrealloc (*names, mvar * sizeof **names);
452             }
453           (*names)[nvar++] = xstrdup (name1);
454         }
455
456       lex_match (',');
457
458       if (pv_opts & PV_SINGLE)
459         break;
460     }
461   while (token == T_ID);
462   success = 1;
463
464 fail:
465   *nnames = nvar;
466   free (name1);
467   if (!success)
468     {
469       int i;
470       for (i = 0; i < nvar; i++)
471         free ((*names)[i]);
472       free (*names);
473       *names = NULL;
474       *nnames = 0;
475     }
476   return success;
477 }
478
479 /* Parses a list of variables where some of the variables may be
480    existing and the rest are to be created.  Same args as
481    parse_DATA_LIST_vars(). */
482 int
483 parse_mixed_vars (char ***names, int *nnames, int pv_opts)
484 {
485   int i;
486
487   assert (names != NULL);
488   assert (nnames != NULL);
489   assert ((pv_opts & ~PV_APPEND) == 0);
490
491   if (!(pv_opts & PV_APPEND))
492     {
493       *names = NULL;
494       *nnames = 0;
495     }
496   while (token == T_ID || token == T_ALL)
497     {
498       if (token == T_ALL || dict_lookup_var (default_dict, tokid) != NULL)
499         {
500           struct variable **v;
501           int nv;
502
503           if (!parse_variables (default_dict, &v, &nv, PV_NONE))
504             goto fail;
505           *names = xrealloc (*names, (*nnames + nv) * sizeof **names);
506           for (i = 0; i < nv; i++)
507             (*names)[*nnames + i] = xstrdup (v[i]->name);
508           free (v);
509           *nnames += nv;
510         }
511       else if (!parse_DATA_LIST_vars (names, nnames, PV_APPEND))
512         goto fail;
513     }
514   return 1;
515
516 fail:
517   for (i = 0; i < *nnames; i++)
518     free ((*names)[*nnames]);
519   free (names);
520   *names = NULL;
521   *nnames = 0;
522   return 0;
523 }
524 \f
525 /* A set of variables. */
526 struct var_set 
527   {
528     size_t (*get_cnt) (const struct var_set *);
529     struct variable *(*get_var) (const struct var_set *, size_t idx);
530     struct variable *(*lookup_var) (const struct var_set *, const char *);
531     void (*destroy) (struct var_set *);
532     void *aux;
533   };
534
535 /* Returns the number of variables in VS. */
536 size_t
537 var_set_get_cnt (const struct var_set *vs) 
538 {
539   assert (vs != NULL);
540
541   return vs->get_cnt (vs);
542 }
543
544 /* Return variable with index IDX in VS.
545    IDX must be less than the number of variables in VS. */
546 struct variable *
547 var_set_get_var (const struct var_set *vs, size_t idx) 
548 {
549   assert (vs != NULL);
550   assert (idx < var_set_get_cnt (vs));
551
552   return vs->get_var (vs, idx);
553 }
554
555 /* Returns the variable in VS named NAME, or a null pointer if VS
556    contains no variable with that name. */
557 struct variable *
558 var_set_lookup_var (const struct var_set *vs, const char *name) 
559 {
560   assert (vs != NULL);
561   assert (name != NULL);
562   assert (strlen (name) < 9);
563
564   return vs->lookup_var (vs, name);
565 }
566
567 /* Destroys VS. */
568 void
569 var_set_destroy (struct var_set *vs) 
570 {
571   if (vs != NULL)
572     vs->destroy (vs);
573 }
574 \f
575 /* Returns the number of variables in VS. */
576 static size_t
577 dict_var_set_get_cnt (const struct var_set *vs) 
578 {
579   struct dictionary *d = vs->aux;
580
581   return dict_get_var_cnt (d);
582 }
583
584 /* Return variable with index IDX in VS.
585    IDX must be less than the number of variables in VS. */
586 static struct variable *
587 dict_var_set_get_var (const struct var_set *vs, size_t idx) 
588 {
589   struct dictionary *d = vs->aux;
590
591   return dict_get_var (d, idx);
592 }
593
594 /* Returns the variable in VS named NAME, or a null pointer if VS
595    contains no variable with that name. */
596 static struct variable *
597 dict_var_set_lookup_var (const struct var_set *vs, const char *name) 
598 {
599   struct dictionary *d = vs->aux;
600
601   return dict_lookup_var (d, name);
602 }
603
604 /* Destroys VS. */
605 static void
606 dict_var_set_destroy (struct var_set *vs) 
607 {
608   free (vs);
609 }
610
611 /* Returns a variable set based on D. */
612 struct var_set *
613 var_set_create_from_dict (const struct dictionary *d) 
614 {
615   struct var_set *vs = xmalloc (sizeof *vs);
616   vs->get_cnt = dict_var_set_get_cnt;
617   vs->get_var = dict_var_set_get_var;
618   vs->lookup_var = dict_var_set_lookup_var;
619   vs->destroy = dict_var_set_destroy;
620   vs->aux = (void *) d;
621   return vs;
622 }
623 \f
624 /* A variable set based on an array. */
625 struct array_var_set 
626   {
627     struct variable *const *var;/* Array of variables. */
628     size_t var_cnt;             /* Number of elements in var. */
629     struct hsh_table *name_tab; /* Hash from variable names to variables. */
630   };
631
632 /* Returns the number of variables in VS. */
633 static size_t
634 array_var_set_get_cnt (const struct var_set *vs) 
635 {
636   struct array_var_set *avs = vs->aux;
637
638   return avs->var_cnt;
639 }
640
641 /* Return variable with index IDX in VS.
642    IDX must be less than the number of variables in VS. */
643 static struct variable *
644 array_var_set_get_var (const struct var_set *vs, size_t idx) 
645 {
646   struct array_var_set *avs = vs->aux;
647
648   return (struct variable *) avs->var[idx];
649 }
650
651 /* Returns the variable in VS named NAME, or a null pointer if VS
652    contains no variable with that name. */
653 static struct variable *
654 array_var_set_lookup_var (const struct var_set *vs, const char *name) 
655 {
656   struct array_var_set *avs = vs->aux;
657   struct variable v;
658
659   strcpy (v.name, name);
660
661   return hsh_find (avs->name_tab, &v);
662 }
663
664 /* Destroys VS. */
665 static void
666 array_var_set_destroy (struct var_set *vs) 
667 {
668   struct array_var_set *avs = vs->aux;
669
670   hsh_destroy (avs->name_tab);
671   free (avs);
672   free (vs);
673 }
674
675 /* Returns a variable set based on the VAR_CNT variables in
676    VAR. */
677 struct var_set *
678 var_set_create_from_array (struct variable *const *var, size_t var_cnt) 
679 {
680   struct var_set *vs;
681   struct array_var_set *avs;
682   size_t i;
683
684   vs = xmalloc (sizeof *vs);
685   vs->get_cnt = array_var_set_get_cnt;
686   vs->get_var = array_var_set_get_var;
687   vs->lookup_var = array_var_set_lookup_var;
688   vs->destroy = array_var_set_destroy;
689   vs->aux = avs = xmalloc (sizeof *avs);
690   avs->var = var;
691   avs->var_cnt = var_cnt;
692   avs->name_tab = hsh_create (2 * var_cnt,
693                               compare_variables, hash_variable, NULL,
694                               NULL);
695   for (i = 0; i < var_cnt; i++)
696     if (hsh_insert (avs->name_tab, (void *) var[i]) != NULL) 
697       {
698         var_set_destroy (vs);
699         return NULL;
700       }
701   
702   return vs;
703 }