pintos-os.org Git - pspp/blob - src/language/lexer/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 (ofs < s->length && 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[n_commands]; 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 }