8ef64d9f25754bfe9a5ddd846e632dc545fcc5bf
[pspp] / command-name.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2010 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 "language/lexer/command-name.h"
20
21 #include <assert.h>
22 #include <limits.h>
23
24 #include "data/identifier.h"
25
26 #include "gl/c-ctype.h"
27
28 /* Stores the first word in S into WORD and advances S past that word.  Returns
29    true if successful, false if no word remained in S to be extracted.
30
31    A word is a sequence of digits, a letter possibly followed by a sequence of
32    letters or digits, or one character of another type.  Words may be delimited
33    by spaces. */
34 static bool
35 find_word (struct substring *s, struct substring *word)
36 {
37   size_t ofs;
38   ucs4_t c;
39
40   /* Skip whitespace. */
41   for (;;)
42     {
43       c = ss_first_mb (*s);
44       if (c == UINT32_MAX)
45         {
46           *word = ss_empty ();
47           return false;
48         }
49       else if (lex_uc_is_space (c))
50         ss_get_mb (s);
51       else
52         break;
53     }
54
55   ofs = ss_first_mblen (*s);
56   if (lex_uc_is_id1 (c))
57     {
58       while (lex_uc_is_idn (ss_at_mb (*s, ofs)))
59         ofs += ss_at_mblen (*s, ofs);
60     }
61   else if (c_isdigit (c))
62     {
63       while (c_isdigit (s->string[ofs]))
64         ofs++;
65     }
66   ss_get_bytes (s, ofs, word);
67   return true;
68 }
69
70 /* Returns the number of words in S, as extracted by find_word(). */
71 static int
72 count_words (struct substring s)
73 {
74   struct substring word;
75   int n;
76
77   n = 0;
78   while (find_word (&s, &word))
79     n++;
80   return n;
81 }
82
83 /* Compares STRING obtained from the user against the full name of a COMMAND,
84    using this algorithm:
85
86    1. Divide COMMAND into words C[0] through C[n - 1].
87
88    2. Divide STRING into words S[0] through S[m - 1].
89
90    3. Compare word C[i] against S[i] for 0 <= i < min(n, m), using the keyword
91       matching algorithm implemented by lex_id_match().  If any of them fail to
92       match, then STRING does not match COMMAND and the function returns false.
93
94    4. Otherwise, STRING and COMMAND match.  Set *MISSING_WORDS to n - m.  Set
95       *EXACT to false if any of the S[i] were found to be abbreviated in the
96       comparisons done in step 3, or to true if they were all exactly equal
97       (modulo case).  Return true. */
98 bool
99 command_match (struct substring command, struct substring string,
100                bool *exact, int *missing_words)
101 {
102   *exact = true;
103   for (;;)
104     {
105       struct substring cw, sw;
106       int match;
107
108       if (!find_word (&command, &cw))
109         {
110           *missing_words = -count_words (string);
111           return true;
112         }
113       else if (!find_word (&string, &sw))
114         {
115           *missing_words = 1 + count_words (command);
116           return true;
117         }
118
119       match = lex_id_match (cw, sw);
120       if (sw.length < cw.length)
121         *exact = false;
122       if (match == 0)
123         return false;
124     }
125 }
126
127 /* Initializes CM for matching STRING against a table of command names.
128
129    STRING may be ASCII or UTF-8.
130
131    For sample use, see command.c.  Here's a usage outline:
132
133       // Try each possible command.
134       command_matcher_init (&cm, string);
135       for (cmd = commands; cmd < &commands[command_cnt]; cmd++)
136         command_matcher_add (&cm, cmd->name, cmd);
137
138       // Get the result.
139       match = command_matcher_get_match (&cm);
140       missing_words = command_matcher_get_missing_words (&cm);
141
142       if (missing_words > 0)
143         {
144           // Incomplete command name.  Add another word to the string
145           // and start over.  Or if there are no more words to be added,
146           // add " ." to the string as a sentinel and start over.
147         }
148       else if (match == NULL)
149         {
150           // No valid command with this name.
151         }
152       else if (missing_words == 0)
153         {
154           // The full, correct command name is 'match'.
155         }
156       else if (missing_words < 0)
157         {
158           // The abs(missing_words) last words of 'string' are actually
159           // part of the command's body, not part of its name; they
160           // were only needed to resolve ambiguities.  'match' is the
161           // correct command but those extra words should be put back
162           // for later re-parsing.
163         }
164 */
165 void
166 command_matcher_init (struct command_matcher *cm, struct substring string)
167 {
168   cm->string = string;
169   cm->extensible = false;
170   cm->exact_match = NULL;
171   cm->n_matches = 0;
172   cm->match = NULL;
173   cm->match_missing_words = 0;
174 }
175
176 /* Destroys CM's state. */
177 void
178 command_matcher_destroy (struct command_matcher *cm UNUSED)
179 {
180   /* Nothing to do. */
181 }
182
183 /* Considers COMMAND as a candidate for the command name being parsed by CM.
184    If COMMAND is the correct command name, then command_matcher_get_match()
185    will return AUX later.
186
187    COMMAND must be an ASCII string. */
188 void
189 command_matcher_add (struct command_matcher *cm, struct substring command,
190                      void *aux)
191 {
192   int missing_words;
193   bool exact;
194
195   assert (aux != NULL);
196   if (command_match (command, cm->string, &exact, &missing_words))
197     {
198       if (missing_words > 0)
199         cm->extensible = true;
200       else if (exact && missing_words == 0)
201         cm->exact_match = aux;
202       else
203         {
204           if (missing_words > cm->match_missing_words)
205             cm->n_matches = 0;
206
207           if (missing_words >= cm->match_missing_words || cm->n_matches == 0)
208             {
209               cm->n_matches++;
210               cm->match = aux;
211               cm->match_missing_words = missing_words;
212             }
213         }
214     }
215 }
216
217 /* Returns the command name matched by CM. */
218 void *
219 command_matcher_get_match (const struct command_matcher *cm)
220 {
221   return (cm->extensible ? NULL
222           : cm->exact_match != NULL ? cm->exact_match
223           : cm->n_matches == 1 ? cm->match
224           : NULL);
225 }
226
227 /* Returns the difference between the number of words in the matched command
228    name and the string provided to command_matcher_init(). */
229 int
230 command_matcher_get_missing_words (const struct command_matcher *cm)
231 {
232   return (cm->extensible ? 1
233           : cm->exact_match != NULL ? 0
234           : cm->match_missing_words);
235 }