pintos-os.org Git - pspp/blob - src/data/format-guesser.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2008 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 "format-guesser.h"
  20
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include "c-ctype.h"
  25 #include "minmax.h"
  26 #include "xalloc.h"
  27
  28 #include <data/format.h>
  29 #include <data/settings.h>
  30 #include <libpspp/assertion.h>
  31 #include <libpspp/str.h>
  32
  33 /* A token in which potential date or time fields are broken.
  34
  35    The token type is actually a bit-map.  This allows a single
  36    token to represent multiple roles, as often happens in parsing
  37    adate or a time.  For example, the number "1" can be a quarter
  38    of the year, month, hour, day of the month, week of the year,
  39    or a count of days.  Such ambiguities are resolved on the
  40    higher-level bases of multiple tokens and multiple full
  41    dates. */
  42 enum date_token
  43   {
  44     DT_DAY = 1 << 0,            /* dd: Day of the month. */
  45     DT_MONTH = 1 << 1,          /* mm: Month. */
  46     DT_ENGLISH_MONTH = 1 << 2,  /* mmm: Spelled-out month, e.g. "jan". */
  47     DT_YEAR = 1 << 3,           /* yy: Year. */
  48
  49     DT_HOUR = 1 << 4,           /* HH: Hour. */
  50     DT_MINUTE = 1 << 5,         /* MM: Minute. */
  51     DT_SECOND = 1 << 6,         /* SS: Second. */
  52
  53     DT_WEEKDAY = 1 << 7,        /* www: Day of the week. */
  54
  55     DT_DAY_COUNT = 1 << 8,      /* D: Number of days. */
  56     DT_WEEK = 1 << 9,           /* ww: Week of the year. */
  57     DT_QUARTER = 1 << 10,       /* q: Quarter of the year. */
  58
  59     DT_Q = 1 << 11,             /* Literal "Q". */
  60     DT_WK = 1 << 12,            /* Literal "WK". */
  61
  62     DT_DELIM = 1 << 13,         /* One of -/., or white space. */
  63     DT_SPACE = 1 << 14,         /* Any white space. */
  64     DT_COLON = 1 << 15,         /* : */
  65   };
  66
  67 /* Syntax of a date format, in terms of the date tokens that
  68    compose it.*/
  69 struct date_syntax
  70   {
  71     enum fmt_type format;       /* Format type. */
  72 #define MAX_TOKENS 11
  73     size_t token_cnt;           /* Number of tokens. */
  74     enum date_token tokens[MAX_TOKENS]; /* Tokens. */
  75   };
  76
  77 /* Syntax of all the data formats that we can parse.
  78
  79    The order in the array can make a difference in the final
  80    choice of formats: in the case of a tie between the number of
  81    times each format is seen, the syntax earlier in the array
  82    takes precedence.  The most important cases are the ordering
  83    of DATE before EDATE, so that spelled-out months in input
  84    yield DATE format (that produces spelled-out months in output,
  85    and the ordering of EDATE before ADATE, so that ambiguous
  86    dates such as "1/1/99" yield the more sensible European date
  87    format instead of American format.
  88
  89    When a given date format has more than one syntax, they must
  90    be in adjacent array elements. */
  91 static struct date_syntax syntax[] =
  92   {
  93     /* dd-mmm-yy */
  94     { FMT_DATE, 5, {DT_DAY, DT_DELIM, DT_ENGLISH_MONTH, DT_DELIM, DT_YEAR} },
  95
  96     /* dd.mm.yy */
  97     { FMT_EDATE, 5, {DT_DAY, DT_DELIM, DT_MONTH, DT_DELIM, DT_YEAR} },
  98
  99     /* mm/dd/yy */
 100     { FMT_ADATE, 5, {DT_MONTH, DT_DELIM, DT_DAY, DT_DELIM, DT_YEAR} },
 101
 102     /* yy/mm/dd */
 103     { FMT_SDATE, 5, {DT_YEAR, DT_DELIM, DT_MONTH, DT_DELIM, DT_DAY} },
 104
 105     /* mmm yy */
 106     { FMT_MOYR, 3, {DT_MONTH, DT_DELIM, DT_YEAR} },
 107
 108     /* q Q yy */
 109     { FMT_QYR, 3, {DT_QUARTER, DT_Q, DT_YEAR} },
 110
 111     /* ww WK yy */
 112     { FMT_WKYR, 3, {DT_WEEK, DT_WK, DT_YEAR} },
 113
 114     /* dd-mmm-yyyy HH:MM */
 115     { FMT_DATETIME,
 116       9, {DT_DAY, DT_DELIM, DT_MONTH, DT_DELIM, DT_YEAR, DT_SPACE, DT_HOUR,
 117           DT_COLON, DT_MINUTE} },
 118     /* dd-mmm-yyyy HH:MM:SS */
 119     { FMT_DATETIME,
 120       11, {DT_DAY, DT_DELIM, DT_MONTH, DT_DELIM, DT_YEAR, DT_SPACE, DT_HOUR,
 121            DT_COLON, DT_MINUTE, DT_COLON, DT_SECOND} },
 122
 123     /* HH:MM */
 124     { FMT_TIME, 3, {DT_HOUR, DT_COLON, DT_MINUTE} },
 125     /* HH:MM:SS */
 126     { FMT_TIME, 5, {DT_HOUR, DT_COLON, DT_MINUTE, DT_COLON, DT_SECOND} },
 127
 128     /* D HH:MM */
 129     { FMT_DTIME, 5, {DT_DAY_COUNT, DT_SPACE, DT_HOUR, DT_COLON, DT_MINUTE} },
 130     /* D HH:MM:SS */
 131     { FMT_DTIME,
 132       7, {DT_DAY_COUNT, DT_SPACE, DT_HOUR, DT_COLON, DT_MINUTE, DT_COLON,
 133           DT_SECOND} },
 134
 135     /* www */
 136     { FMT_WKDAY, 1, {DT_WEEKDAY} },
 137
 138     /* mmm
 139
 140        We require a spelled-out English month so that
 141        single-character Roman numerals like "i" and "x" don't get
 142        detected as months.  The latter is particularly common in
 143        the password field of /etc/passwd-like files. */
 144     { FMT_MONTH, 1, {DT_ENGLISH_MONTH} },
 145   };
 146
 147 /* Number of recognized date syntax formats. */
 148 #define DATE_SYNTAX_CNT (sizeof syntax / sizeof *syntax)
 149
 150 /* A format guesser. */
 151 struct fmt_guesser
 152   {
 153     /* Maximum observed input width. */
 154     unsigned int width;
 155
 156     /* Sum of the digits after the decimal point in each input
 157        (divide by count to obtain average decimal positions). */
 158     unsigned int decimals;
 159
 160     /* Number of non-empty, non-missing input values.
 161
 162        count is the sum of any_numeric, any_date, and the number
 163        of inputs that were not in any recognized format (hence,
 164        treated as A format). */
 165     unsigned int count;
 166
 167     /* Numeric input formats. */
 168     unsigned int any_numeric;   /* Sum of following counts. */
 169     unsigned int f;             /* Number of inputs in F format. */
 170     unsigned int comma;         /* Number of inputs in COMMA format. */
 171     unsigned int dot;           /* Number of inputs in DOT format. */
 172     unsigned int dollar;        /* Number of inputs in DOLLAR format. */
 173     unsigned int pct;           /* Number of inputs in PCT format. */
 174     unsigned int e;             /* Number of inputs in E format. */
 175
 176     /* Date or time input formats.
 177
 178        The sum of the values in the date array is at least
 179        any_date, often higher because many example dates match
 180        more than one date format. */
 181     unsigned int any_date;      /* Number of inputs in any date format. */
 182     unsigned int date[DATE_SYNTAX_CNT]; /* Number of inputs in each date
 183                                            format. */
 184   };
 185
 186 static bool add_numeric (struct fmt_guesser *, struct substring);
 187 static void guess_numeric (struct fmt_guesser *, struct fmt_spec *);
 188 static void add_date_time (struct fmt_guesser *, struct substring);
 189 static bool match_date_syntax (const enum date_token a[], size_t a_len,
 190                                const enum date_token b[], size_t b_len);
 191 static void guess_date_time (struct fmt_guesser *, struct fmt_spec *);
 192 static enum date_token parse_date_token (struct substring *,
 193                                          enum date_token tokens_seen,
 194                                          int *decimals);
 195 static enum date_token parse_date_number (struct substring *,
 196                                           enum date_token tokens_seen,
 197                                           int *decimals);
 198 static enum date_token recognize_identifier_token (struct substring *);
 199 static enum date_token recognize_id2 (int s0, int s1, bool more);
 200 static enum date_token recognize_id3 (int s0, int s1, int s2, bool more);
 201
 202 /* Creates and returns a new format guesser. */
 203 struct fmt_guesser *
 204 fmt_guesser_create (void)
 205 {
 206   struct fmt_guesser *g = xmalloc (sizeof *g);
 207   fmt_guesser_clear (g);
 208   return g;
 209 }
 210
 211 /* Destroys format guesser G. */
 212 void
 213 fmt_guesser_destroy (struct fmt_guesser *g)
 214 {
 215   free (g);
 216 }
 217
 218 /* Clears the state of format guesser G, making it available for
 219    guessing the format of a new input stream.  */
 220 void
 221 fmt_guesser_clear (struct fmt_guesser *g)
 222 {
 223   memset (g, 0, sizeof *g);
 224 }
 225
 226 /* Appends S to the stream of data items whose format G is
 227    guessing. */
 228 void
 229 fmt_guesser_add (struct fmt_guesser *g, struct substring s)
 230 {
 231   if (ss_length (s) > g->width)
 232     g->width = ss_length (s);
 233   ss_trim (&s, ss_cstr (CC_SPACES));
 234   if (ss_is_empty (s) || ss_equals (s, ss_cstr (".")))
 235     {
 236       /* Can't guess anything from an empty string or a missing value. */
 237       return;
 238     }
 239
 240   g->count++;
 241   if (!add_numeric (g, s))
 242     add_date_time (g, s);
 243 }
 244
 245 /* Guesses the format of the input previously added to G using
 246    fmt_guesser_add, storing the guess into *F.  The guessed
 247    format may not actually a valid input or output format, in
 248    that its width and number of decimal places may be outside the
 249    valid range for the guessed format type.  The caller must
 250    therefore adjust the format to make it valid, e.g. by calling
 251    fmt_fix. */
 252 void
 253 fmt_guesser_guess (struct fmt_guesser *g, struct fmt_spec *f)
 254 {
 255   if (g->count > 0)
 256     {
 257       /* Set defaults.  The guesser functions typically override
 258          the width and type. */
 259       f->type = FMT_A;
 260       f->w = g->width;
 261       f->d = 0;
 262
 263       if (g->any_numeric > g->count / 2)
 264         guess_numeric (g, f);
 265       else if (g->any_date > g->count / 2)
 266         guess_date_time (g, f);
 267     }
 268   else
 269     {
 270       /* No data at all.  Use fallback default. */
 271       *f = fmt_default_for_width (0);
 272     }
 273 }
 274 \f
 275 /* Numeric formats. */
 276
 277 /* Tries to parse S as a numeric (F, COMMA, DOT, DOLLAR, PCT, or
 278    E) format.  If successful, increments G's any_numeric counter
 279    and the counter for the specific format S that S matches and
 280    returns true.  On failure, returns false without modifying G.
 281
 282    This function is intended to match exactly the same set of
 283    strings that the actual numeric value parsers used by the
 284    data_in function would match. */
 285 static bool
 286 add_numeric (struct fmt_guesser *g, struct substring s)
 287 {
 288   bool has_dollar;              /* '$' appeared at start of S? */
 289   bool has_percent;             /* '%' appeared at end of S? */
 290   int digits;                   /* Number of digits in S (before exponent). */
 291   int dots;                     /* Number of '.' in S. */
 292   int commas;                   /* Number of ',' in S. */
 293   bool has_exp;                 /* [eEdD] appeared introducing exponent? */
 294   bool has_exp_sign;            /* '+' or '-' appeared in exponent? */
 295   int exp_digits;               /* Number of digits in exponent. */
 296
 297   int prev_delim;       /* Initially 0, then ',' or '.' as delimiters seen. */
 298   int delim_digits;             /* Number of digits since last delimiter. */
 299
 300   int decimal;                  /* Decimal point character: '.', ',',
 301                                    or 0 if unknown or no decimal point in S. */
 302   int precision;                /* Digits of precision after decimal point. */
 303
 304   int c;
 305
 306   /* Skip leading "$" and optional following white space. */
 307   has_dollar = ss_match_char (&s, '$');
 308   if (has_dollar)
 309     ss_ltrim (&s, ss_cstr (CC_SPACES));
 310
 311   /* Skip optional sign. */
 312   ss_match_char_in (&s, ss_cstr ("+-"));
 313
 314   /* Skip digits punctuated by commas and dots.  We don't know
 315      whether the decimal point is a comma or a dot, so for now we
 316      just count them.  */
 317   digits = dots = commas = 0;
 318   delim_digits = 0;
 319   prev_delim = 0;
 320   for (; (c = ss_first (s)) != -1; ss_advance (&s, 1))
 321     {
 322       if (c >= '0' && c <= '9')
 323         {
 324           digits++;
 325           if (dots || commas)
 326             delim_digits++;
 327         }
 328       else if (c == '.' )
 329         {
 330           dots++;
 331           prev_delim = c;
 332           delim_digits = 0;
 333         }
 334       else if (c == ',')
 335         {
 336           commas++;
 337           prev_delim = c;
 338           delim_digits = 0;
 339         }
 340       else
 341         break;
 342     }
 343   if (digits == 0 || (dots > 1 && commas > 1))
 344     {
 345       /* A valid number has at least one digit and can't have
 346          more than one decimal point. */
 347       return false;
 348     }
 349
 350   /* Skip the optional exponent. */
 351   has_exp = ss_match_char_in (&s, ss_cstr ("eEdD")) != EOF;
 352   has_exp_sign = ss_match_char_in (&s, ss_cstr ("-+")) != EOF;
 353   if (has_exp_sign)
 354     ss_match_char (&s, ' ');
 355   exp_digits = ss_ltrim (&s, ss_cstr (CC_DIGITS));
 356   if ((has_exp || has_exp_sign) && !exp_digits)
 357     {
 358       /* Can't have the E or sign that leads in the exponent
 359          without actually having an exponent. */
 360       return false;
 361     }
 362
 363   /* Skip optional '%'. */
 364   has_percent = ss_match_char (&s, '%');
 365   if (has_dollar && has_percent)
 366     {
 367       /* A valid number cannot have both '$' and '%'. */
 368       return false;
 369     }
 370
 371   /* Make sure there's no trailing garbage. */
 372   if (!ss_is_empty (s))
 373     return false;
 374
 375   /* Figure out the decimal point (and therefore grouping)
 376      character and the number of digits following the decimal
 377      point.  Sometimes the answer is ambiguous. */
 378   if (dots > 1 && prev_delim == '.')
 379     {
 380       /* Can't have multiple decimal points, so '.' must really
 381          be the grouping character, with a precision of 0. */
 382       decimal = ',';
 383       precision = 0;
 384     }
 385   else if (commas > 1 && prev_delim == ',')
 386     {
 387       /* Can't have multiple decimal points, so ',' must really
 388          be the grouping character, with a precision of 0. */
 389       decimal = '.';
 390       precision = 0;
 391     }
 392   else if (delim_digits == 3 && (!dots || !commas))
 393     {
 394       /* The input is something like "1.234" or "1,234" where we
 395          can't tell whether the ',' or '.' is a grouping or
 396          decimal character.  Assume that the decimal character
 397          from the settings is in use. */
 398       if (prev_delim == settings_get_decimal_char (FMT_F))
 399         {
 400           decimal = prev_delim;
 401           precision = delim_digits;
 402         }
 403       else
 404         {
 405           decimal = prev_delim == '.' ? ',' : '.';
 406           precision = 0;
 407         }
 408     }
 409   else
 410     {
 411       /* The final delimiter is a decimal point, and the digits
 412          following it are decimals. */
 413       decimal = prev_delim;
 414       precision = delim_digits;
 415     }
 416
 417   /* Decide the most likely format. */
 418   g->any_numeric++;
 419   g->decimals += precision;
 420   if (has_dollar)
 421     g->dollar++;
 422   else if (has_percent)
 423     g->pct++;
 424   else if (commas && decimal == '.')
 425     g->comma++;
 426   else if (dots && decimal == ',')
 427     g->dot++;
 428   else if (has_exp || has_exp_sign)
 429     g->e++;
 430   else
 431     g->f++;
 432
 433   return true;
 434 }
 435
 436 /* Guess which numeric format is most likely represented by G,
 437    and store it in F's type and d members.  (f->w is already
 438    initialized.) */
 439 static void
 440 guess_numeric (struct fmt_guesser *g, struct fmt_spec *f)
 441 {
 442   int decimal_char = settings_get_decimal_char (FMT_COMMA);
 443
 444   f->d = g->decimals / g->count;
 445   if (g->pct)
 446     f->type = FMT_PCT;
 447   else if (g->dollar)
 448     f->type = FMT_DOLLAR;
 449   else if (g->comma > g->dot)
 450     f->type = decimal_char == '.' ? FMT_COMMA : FMT_DOT;
 451   else if (g->dot > g->comma)
 452     f->type = decimal_char == '.' ? FMT_DOT : FMT_COMMA;
 453   else if (g->e > g->any_numeric / 2)
 454     f->type = FMT_E;
 455   else
 456     f->type = FMT_F;
 457 }
 458 \f
 459 /* Tries to parse S as a date (DATE, ADATE, EDATE, SDATE, QYR,
 460    MOYR, WKYR, or DATETIME), time (TIME or DTIME), or date
 461    component (WKDAY or MONTH) format.  If successful, increments
 462    G's any_date counter and the counter or counters for the
 463    specific format(s) that S matches.  On failure, does not
 464    modify G.
 465
 466    Does not attempt to recognize JDATE format: it looks just like
 467    F format and will thus be caught by the numeric parser.
 468
 469    This function is intended to match a set of strings close to
 470    those that actual date and time parsers used by the data_in
 471    function would match, but somewhat pickier.  In particular,
 472    minutes and seconds are only recognized when they have exactly
 473    two digits: "1:02:03" is a valid time, but "1:2:3" is
 474    rejected.  */
 475 static void
 476 add_date_time (struct fmt_guesser *g, struct substring s)
 477 {
 478   enum date_token token;
 479   enum date_token tokens[MAX_TOKENS];
 480   enum date_token tokens_seen;
 481   size_t token_cnt;
 482   int decimals;
 483   bool is_date;
 484   int i;
 485
 486   /* Break S into tokens. */
 487   token_cnt = 0;
 488   tokens_seen = 0;
 489   decimals = 0;
 490   while (!ss_is_empty (s))
 491     {
 492       if (token_cnt >= MAX_TOKENS)
 493         return;
 494
 495       token = parse_date_token (&s, tokens_seen, &decimals);
 496       if (token == 0)
 497         return;
 498       tokens[token_cnt++] = token;
 499       tokens_seen |= token;
 500     }
 501   if (token_cnt == 0)
 502     return;
 503
 504   /* Find matching date formats, if any, and increment the
 505      counter for each one of them. */
 506   is_date = false;
 507   for (i = 0; i < DATE_SYNTAX_CNT; i++)
 508     {
 509       struct date_syntax *s = &syntax[i];
 510       if (match_date_syntax (tokens, token_cnt, s->tokens, s->token_cnt))
 511         {
 512           is_date = true;
 513           g->date[i]++;
 514         }
 515     }
 516   if (is_date)
 517     {
 518       g->any_date++;
 519       g->decimals += decimals;
 520     }
 521 }
 522
 523 /* Returns true if the A_LEN tokens in A[] match the B_LEN tokens
 524    in B[], false otherwise. */
 525 static bool
 526 match_date_syntax (const enum date_token a[], size_t a_len,
 527                    const enum date_token b[], size_t b_len)
 528 {
 529   size_t i;
 530
 531   if (a_len != b_len)
 532     return false;
 533
 534   for (i = 0; i < a_len; i++)
 535     if (!(a[i] & b[i]))
 536       return false;
 537
 538   return true;
 539 }
 540
 541 /* Guess which date or time format is most likely represented by
 542    G, and store it in F's type and d members.  (f->w is already
 543    initialized.) */
 544 static void
 545 guess_date_time (struct fmt_guesser *g, struct fmt_spec *f)
 546 {
 547   unsigned int max = 0;
 548   int i, j;
 549
 550   /* Choose the date format matched by the most inputs.  Break
 551      ties by choosing the earliest in the array. */
 552   for (i = 0; i < DATE_SYNTAX_CNT; i = j)
 553     {
 554       unsigned int sum = g->date[i];
 555       for (j = i + 1; j < DATE_SYNTAX_CNT; j++)
 556         {
 557           if (syntax[i].format != syntax[j].format)
 558             break;
 559           sum += g->date[j];
 560         }
 561       if (sum > max)
 562         {
 563           f->type = syntax[i].format;
 564           max = sum;
 565         }
 566     }
 567
 568   /* Formats that include a time have an optional seconds field.
 569      If we saw a seconds field in any of the inputs, make sure
 570      that the field width is large enough to include for them.
 571      (We use the minimum input width, but an output width would
 572      be equally appropriate, since all the time formats have the
 573      same minimum widths for input and output.)  */
 574   if (f->type == FMT_DATETIME || f->type == FMT_TIME
 575       || f->type == FMT_DTIME)
 576     {
 577       for (i = 0; i < DATE_SYNTAX_CNT; i++)
 578         if (g->date[i]
 579             && syntax[i].tokens[syntax[i].token_cnt - 1] == DT_SECOND)
 580           {
 581             f->d = g->decimals / g->count;
 582             f->w = MAX (f->w, fmt_min_input_width (f->type) + 3);
 583           }
 584     }
 585 }
 586
 587 /* Extracts the next date token from the string represented by S,
 588    which must not be an empty string, and advances *S past the
 589    end of the token.  Returns the parsed token, or 0 if no valid
 590    token was found.
 591
 592    TOKENS_SEEN should be a bitmap representing all the tokens
 593    already seen in this input; this is used to resolve some
 594    otherwise ambiguous parsing situation.  If a count of seconds
 595    is parsed, *DECIMALS is set to the number of digits after the
 596    decimal point.  */
 597 static enum date_token
 598 parse_date_token (struct substring *s, enum date_token tokens_seen,
 599                   int *decimals)
 600 {
 601   int c = ss_first (*s);
 602
 603   switch (c)
 604     {
 605     case '0': case '1': case '2': case '3': case '4':
 606     case '5': case '6': case '7': case '8': case '9':
 607       return parse_date_number (s, tokens_seen, decimals);
 608
 609     case '+':
 610     case '-':
 611       /* '+' or '-' at the start of a string, or following a
 612          space, could be the sign that optionally introduces a
 613          time, e.g. "-1:00" in TIME format, "-1 1:00" in DTIME
 614          format, or "1/1/1978 +1:00" in DATETIME format. */
 615       if ((!tokens_seen || s->string[-1] == ' ') && c_isdigit (ss_at (*s, 1)))
 616         {
 617           ss_advance (s, 1);
 618           ss_ltrim (s, ss_cstr (CC_DIGITS));
 619           return DT_DAY_COUNT | DT_HOUR;
 620         }
 621       else if (c == '+')
 622         return 0;
 623       /* Fall through. */
 624     case '/': case '.': case ',':
 625       ss_advance (s, 1);
 626       return DT_DELIM;
 627
 628     case ':':
 629       ss_advance (s, 1);
 630       return DT_COLON;
 631
 632     case ' ': case '\t': case '\v': case '\r': case '\n':
 633       {
 634         enum date_token token;
 635         ss_advance (s, 1);
 636         token = recognize_identifier_token (s);
 637         if (token)
 638           ss_match_char_in (s, ss_cstr (CC_SPACES));
 639         else
 640           token = DT_DELIM | DT_SPACE;
 641         return token;
 642       }
 643
 644     default:
 645       return recognize_identifier_token (s);
 646
 647     case EOF:
 648       NOT_REACHED ();
 649     }
 650 }
 651
 652 /* Parses a digit sequence found in a date token.  Advances *S
 653    past the end of the token.  Returns the parsed token, or 0 if
 654    no valid token was found.
 655
 656    TOKENS_SEEN should be a bitmap representing all the tokens
 657    already seen in this input; this is used to resolve some
 658    otherwise ambiguous parsing situation.  If a count of seconds
 659    is parsed, *DECIMALS is set to the number of digits after the
 660    decimal point.*/
 661 static enum date_token
 662 parse_date_number (struct substring *s, enum date_token tokens_seen,
 663                    int *decimals)
 664 {
 665   long int value;
 666   size_t digit_cnt = ss_get_long (s, &value);
 667   enum date_token token = 0;
 668
 669   if (ss_match_char (s, settings_get_decimal_char (FMT_F))
 670       && tokens_seen & DT_COLON
 671       && value <= 59)
 672     {
 673       /* Parse digits after the decimal point. */
 674       token = DT_SECOND;
 675       *decimals = ss_ltrim (s, ss_cstr (CC_DIGITS));
 676     }
 677   else
 678     {
 679       if (value <= 4)
 680         token = (DT_QUARTER | DT_MONTH | DT_HOUR | DT_DAY | DT_WEEK
 681                  | DT_DAY_COUNT);
 682       else if (value <= 12)
 683         token = DT_MONTH | DT_HOUR | DT_DAY | DT_WEEK | DT_DAY_COUNT;
 684       else if (value <= 23)
 685         token = DT_HOUR | DT_DAY | DT_WEEK | DT_DAY_COUNT;
 686       else if (value <= 31)
 687         token = DT_DAY | DT_WEEK | DT_DAY_COUNT;
 688       else if (value <= 52)
 689         token = DT_WEEK | DT_DAY_COUNT;
 690       else
 691         token = DT_DAY_COUNT;
 692
 693       if (digit_cnt == 2)
 694         {
 695           token |= DT_YEAR;
 696           if (value <= 59)
 697             token |= DT_MINUTE | DT_SECOND;
 698         }
 699       else if (digit_cnt == 4)
 700         token |= DT_YEAR;
 701     }
 702
 703   return token;
 704 }
 705
 706 /* Attempts to parse an identifier found in a date at the
 707    beginning of S.  Advances *S past the end of the token.
 708    Returns the parsed token, or 0 if no valid token was
 709    found.  */
 710 static enum date_token
 711 recognize_identifier_token (struct substring *s)
 712 {
 713   size_t length = ss_span (*s, ss_cstr (CC_LETTERS));
 714   enum date_token token = 0;
 715   switch (length)
 716     {
 717     case 0:
 718       break;
 719
 720     case 1:
 721       switch (c_tolower (s->string[0]))
 722         {
 723         case 'i':
 724         case 'v':
 725         case 'x':
 726           token = DT_MONTH;
 727           break;
 728
 729         case 'q':
 730           token = DT_Q;
 731           break;
 732         }
 733       break;
 734
 735     case 2:
 736       {
 737         int s0 = c_tolower ((unsigned char) s->string[0]);
 738         int s1 = c_tolower ((unsigned char) s->string[1]);
 739         token = recognize_id2 (s0, s1, false);
 740         if (!token && s0 == 'w' && s1 == 'k')
 741           token = DT_WK;
 742       }
 743       break;
 744
 745     default:
 746       {
 747         int s0 = c_tolower ((unsigned char) s->string[0]);
 748         int s1 = c_tolower ((unsigned char) s->string[1]);
 749         int s2 = c_tolower ((unsigned char) s->string[2]);
 750         token = recognize_id2 (s0, s1, true);
 751         if (!token)
 752           token = recognize_id3 (s0, s1, s2, length > 3);
 753         if (!token && length == 4)
 754           {
 755             int s3 = c_tolower ((unsigned char) s->string[3]);
 756             if (s0 == 'v' && s1 == 'i' && s2 == 'i' && s3 == 'i')
 757               token = DT_MONTH;
 758           }
 759       }
 760       break;
 761     }
 762   if (token)
 763     ss_advance (s, length);
 764   return token;
 765 }
 766
 767 static enum date_token
 768 recognize_id2 (int s0, int s1, bool more)
 769 {
 770   bool weekday;
 771   switch (s0)
 772     {
 773     case 's': weekday = s1 == 'a' || s1 == 'u'; break;
 774     case 'm': weekday = s1 == 'o'; break;
 775     case 't': weekday = s1 == 'u' || s1 == 'h'; break;
 776     case 'w': weekday = s1 == 'e'; break;
 777     case 'f': weekday = s1 == 'r'; break;
 778     default: weekday = false; break;
 779     }
 780   if (weekday)
 781     return DT_WEEKDAY;
 782
 783   if (!more)
 784     {
 785       bool month;
 786       switch (s0)
 787         {
 788         case 'i': month = s1 == 'i' || s1 == 'v' || s1 == 'x'; break;
 789         case 'v': month = s1 == 'i'; break;
 790         case 'x': month = s1 == 'i'; break;
 791         default: month = false; break;
 792         }
 793       if (month)
 794         return DT_MONTH;
 795     }
 796
 797   return 0;
 798 }
 799
 800 static enum date_token
 801 recognize_id3 (int s0, int s1, int s2, bool more)
 802 {
 803   bool month;
 804   switch (s0)
 805     {
 806     case 'j':
 807       month = ((s1 == 'a' && s2 == 'n')
 808                || (s1 == 'u' && (s2 == 'n' || s2 == 'l')));
 809       break;
 810     case 'f':
 811       month = s1 == 'e' && s2 == 'b';
 812       break;
 813     case 'm':
 814       month = (s1 == 'a' && (s2 == 'r' || s2 == 'y'));
 815       break;
 816     case 'a':
 817       month = (s1 == 'p' && s2 == 'r') || (s1 == 'u' && s2 == 'g');
 818       break;
 819     case 's':
 820       month = s1 == 'e' && s2 == 'p';
 821       break;
 822     case 'o':
 823       month = s1 == 'c' && s2 == 't';
 824       break;
 825     case 'n':
 826       month = s1 == 'o' && s2 == 'v';
 827       break;
 828     case 'd':
 829       month = s1 == 'e' && s2 == 'c';
 830       break;
 831     default:
 832       month = false;
 833     }
 834   if (month)
 835     return DT_MONTH | DT_ENGLISH_MONTH;
 836
 837   if (!more)
 838     {
 839       bool roman_month = false;
 840       switch (s0)
 841         {
 842         case 'i':
 843         case 'x':
 844           roman_month = s1 == 'i' && s2 == 'i';
 845           break;
 846         case 'v':
 847           roman_month = s1 == 'i' && s2 == 'i';
 848           break;
 849         }
 850       if (roman_month)
 851         return DT_MONTH;
 852     }
 853
 854   return 0;
 855 }
 856
 857
 858
 859