Clover coverage report -
Coverage timestamp: Sat Feb 28 2004 21:40:56 EST
file stats: LOC: 1,040   Methods: 18
NCLOC: 609   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
FastCronParser.java 94.8% 97.6% 94.4% 96.5%
coverage coverage
 1   
 /*
 2   
  * Copyright (c) 2002-2003 by OpenSymphony
 3   
  * All rights reserved.
 4   
  */
 5   
 package com.opensymphony.oscache.util;
 6   
 
 7   
 import java.text.ParseException;
 8   
 
 9   
 import java.util.*;
 10   
 import java.util.Calendar;
 11   
 
 12   
 /**
 13   
  * Parses cron expressions and determines at what time in the past is the
 14   
  * most recent match for the supplied expression.
 15   
  *
 16   
  * @author <a href="&#109;a&#105;&#108;&#116;&#111;:chris&#64;swebtec.&#99;&#111;&#109;">Chris Miller</a>
 17   
  * @author $Author: chris_miller $
 18   
  * @version $Revision: 1.3 $
 19   
  */
 20   
 public class FastCronParser {
 21   
     private static final int NUMBER_OF_CRON_FIELDS = 5;
 22   
     private static final int MINUTE = 0;
 23   
     private static final int HOUR = 1;
 24   
     private static final int DAY_OF_MONTH = 2;
 25   
     private static final int MONTH = 3;
 26   
     private static final int DAY_OF_WEEK = 4;
 27   
 
 28   
     // Lookup tables that hold the min/max/size of each of the above field types.
 29   
     // These tables are precalculated for performance.
 30   
     private static final int[] MIN_VALUE = {0, 0, 1, 1, 0};
 31   
     private static final int[] MAX_VALUE = {59, 23, 31, 12, 6};
 32   
 
 33   
     /**
 34   
      * A lookup table holding the number of days in each month (with the obvious exception
 35   
      * that February requires special handling).
 36   
      */
 37   
     private static final int[] DAYS_IN_MONTH = {
 38   
         31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
 39   
     };
 40   
 
 41   
     /**
 42   
      * Holds the raw cron expression that this parser is handling.
 43   
      */
 44   
     private String cronExpression = null;
 45   
 
 46   
     /**
 47   
     * This is the main lookup table that holds a parsed cron expression. each long
 48   
     * represents one of the above field types. Bits in each long value correspond
 49   
     * to one of the possbile field values - eg, for the minute field, bits 0 -> 59 in
 50   
     * <code>lookup[MINUTE]</code> map to minutes 0 -> 59 respectively. Bits are set if
 51   
     * the corresponding value is enabled. So if the minute field in the cron expression
 52   
     * was <code>"0,2-8,50"</code>, bits 0, 2, 3, 4, 5, 6, 7, 8 and 50 will be set.
 53   
     * If the cron expression is <code>"*"</code>, the long value is set to
 54   
     * <code>Long.MAX_VALUE</code>.
 55   
     */
 56   
     private long[] lookup = {
 57   
         Long.MAX_VALUE, Long.MAX_VALUE, Long.MAX_VALUE, Long.MAX_VALUE,
 58   
         Long.MAX_VALUE
 59   
     };
 60   
 
 61   
     /**
 62   
     * This is based on the contents of the <code>lookup</code> table. It holds the
 63   
     * <em>highest</em> valid field value for each field type.
 64   
     */
 65   
     private int[] lookupMax = {-1, -1, -1, -1, -1};
 66   
 
 67   
     /**
 68   
     * This is based on the contents of the <code>lookup</code> table. It holds the
 69   
     * <em>lowest</em> valid field value for each field type.
 70   
     */
 71   
     private int[] lookupMin = {
 72   
         Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE,
 73   
         Integer.MAX_VALUE, Integer.MAX_VALUE
 74   
     };
 75   
 
 76   
     /**
 77   
     * Creates a FastCronParser that uses a default cron expression of <code>"* * * * *"</cron>.
 78   
     * This will match any time that is supplied.
 79   
     */
 80  6
     public FastCronParser() {
 81   
     }
 82   
 
 83   
     /**
 84   
     * Constructs a new FastCronParser based on the supplied expression.
 85   
     *
 86   
     * @throws ParseException if the supplied expression is not a valid cron expression.
 87   
     */
 88  225
     public FastCronParser(String cronExpression) throws ParseException {
 89  225
         setCronExpression(cronExpression);
 90   
     }
 91   
 
 92   
     /**
 93   
     * Resets the cron expression to the value supplied.
 94   
     *
 95   
     * @param cronExpression the new cron expression.
 96   
     *
 97   
     * @throws ParseException if the supplied expression is not a valid cron expression.
 98   
     */
 99  237
     public void setCronExpression(String cronExpression) throws ParseException {
 100  237
         if (cronExpression == null) {
 101  3
             throw new IllegalArgumentException("Cron time expression cannot be null");
 102   
         }
 103   
 
 104  234
         this.cronExpression = cronExpression;
 105  234
         parseExpression(cronExpression);
 106   
     }
 107   
 
 108   
     /**
 109   
     * Retrieves the current cron expression.
 110   
     *
 111   
     * @return the current cron expression.
 112   
     */
 113  9
     public String getCronExpression() {
 114  9
         return this.cronExpression;
 115   
     }
 116   
 
 117   
     /**
 118   
     * Determines whether this cron expression matches a date/time that is more recent
 119   
     * than the one supplied.
 120   
     *
 121   
     * @param time The time to compare the cron expression against.
 122   
     *
 123   
     * @return <code>true</code> if the cron expression matches a time that is closer
 124   
     * to the current time than the supplied time is, <code>false</code> otherwise.
 125   
     */
 126  0
     public boolean hasMoreRecentMatch(long time) {
 127  0
         return time < getTimeBefore(System.currentTimeMillis());
 128   
     }
 129   
 
 130   
     /**
 131   
     * Find the most recent time that matches this cron expression. This time will
 132   
     * always be in the past, ie a lower value than the supplied time.
 133   
     *
 134   
     * @param time The time (in milliseconds) that we're using as our upper bound.
 135   
     *
 136   
     * @return The time (in milliseconds) when this cron event last occurred.
 137   
     */
 138  120
     public long getTimeBefore(long time) {
 139   
         // It would be nice to get rid of the Calendar class for speed, but it's a lot of work...
 140   
         // We create this
 141  120
         Calendar cal = new GregorianCalendar();
 142  120
         cal.setTime(new Date(time));
 143   
 
 144  120
         int minute = cal.get(Calendar.MINUTE);
 145  120
         int hour = cal.get(Calendar.HOUR_OF_DAY);
 146  120
         int dayOfMonth = cal.get(Calendar.DAY_OF_MONTH);
 147  120
         int month = cal.get(Calendar.MONTH) + 1; // Calendar is 0-based for this field, and we are 1-based
 148  120
         int year = cal.get(Calendar.YEAR);
 149   
 
 150  120
         long validMinutes = lookup[MINUTE];
 151  120
         long validHours = lookup[HOUR];
 152  120
         long validDaysOfMonth = lookup[DAY_OF_MONTH];
 153  120
         long validMonths = lookup[MONTH];
 154  120
         long validDaysOfWeek = lookup[DAY_OF_WEEK];
 155   
 
 156   
         // Find out if we have a Day of Week or Day of Month field
 157  120
         boolean haveDOM = validDaysOfMonth != Long.MAX_VALUE;
 158  120
         boolean haveDOW = validDaysOfWeek != Long.MAX_VALUE;
 159   
 
 160  120
         while (true) {
 161  210
             boolean retry = false;
 162   
 
 163   
             // Clean up the month if it was wrapped in a previous iteration
 164  210
             if (month < 1) {
 165  21
                 month += 12;
 166  21
                 year--;
 167   
             }
 168   
 
 169   
             // get month...................................................
 170  210
             boolean found = false;
 171   
 
 172  210
             if (validMonths != Long.MAX_VALUE) {
 173  54
                 for (int i = month + 11; i > (month - 1); i--) {
 174  309
                     int testMonth = (i % 12) + 1;
 175   
 
 176  309
                     int numDays = numberOfDaysInMonth(testMonth, year);
 177   
 
 178   
                     // Check if the month is valid
 179  309
                     if (((1L << (testMonth - 1)) & validMonths) != 0) {
 180  54
                         if (testMonth > month) {
 181  15
                             year--;
 182   
                         }
 183   
 
 184   
                         // Check there are enough days in this month (catches non leap-years trying to match the 29th Feb)
 185  54
                         if (!haveDOM || (numDays >= lookupMin[DAY_OF_MONTH])) {
 186  45
                             if (month != testMonth) {
 187   
                                 // New DOM = min(maxDOM, prevDays);  ie, the highest valid value
 188  36
                                 dayOfMonth = (numDays <= lookupMax[DAY_OF_MONTH]) ? numDays : lookupMax[DAY_OF_MONTH];
 189   
 
 190  36
                                 hour = lookupMax[HOUR];
 191  36
                                 minute = lookupMax[MINUTE];
 192   
                             }
 193   
 
 194  45
                             month = testMonth;
 195  45
                             found = true;
 196  45
                             break;
 197   
                         }
 198   
                     }
 199   
                 }
 200   
 
 201  54
                 if (!found) {
 202   
                     // The only time we drop out here is when we're searching for the 29th of February and no other date!
 203  9
                     year--;
 204  9
                     continue;
 205   
                 }
 206   
             }
 207   
 
 208   
             // Clean up if the dayOfMonth was wrapped. This takes leap years into account.
 209  201
             if (dayOfMonth < 1) {
 210  15
                 month--;
 211  15
                 dayOfMonth += numberOfDaysInMonth(month, year);
 212  15
                 hour = lookupMax[HOUR];
 213  15
                 continue;
 214   
             }
 215   
 
 216   
             // get day...................................................
 217  186
             if (haveDOM && !haveDOW) { // get day using just the DAY_OF_MONTH token
 218   
 
 219  45
                 int daysInThisMonth = numberOfDaysInMonth(month, year);
 220  45
                 int daysInPreviousMonth = numberOfDaysInMonth(month - 1, year);
 221   
 
 222   
                 // Find the highest valid day that is below the current day
 223  231
                 for (int i = dayOfMonth + 30; i > (dayOfMonth - 1); i--) {
 224  231
                     int testDayOfMonth = (i % 31) + 1;
 225   
 
 226   
                     // Skip over any days that don't actually exist (eg 31st April)
 227  231
                     if ((testDayOfMonth <= dayOfMonth) && (testDayOfMonth > daysInThisMonth)) {
 228  0
                         continue;
 229   
                     }
 230   
 
 231  231
                     if ((testDayOfMonth > dayOfMonth) && (testDayOfMonth > daysInPreviousMonth)) {
 232  3
                         continue;
 233   
                     }
 234   
 
 235  228
                     if (((1L << (testDayOfMonth - 1)) & validDaysOfMonth) != 0) {
 236  45
                         if (testDayOfMonth > dayOfMonth) {
 237   
                             // We've found a valid day, but we had to move back a month
 238  15
                             month--;
 239  15
                             retry = true;
 240   
                         }
 241   
 
 242  45
                         if (dayOfMonth != testDayOfMonth) {
 243  18
                             hour = lookupMax[HOUR];
 244  18
                             minute = lookupMax[MINUTE];
 245   
                         }
 246   
 
 247  45
                         dayOfMonth = testDayOfMonth;
 248  45
                         break;
 249   
                     }
 250   
                 }
 251   
 
 252  45
                 if (retry) {
 253  15
                     continue;
 254   
                 }
 255  141
             } else if (haveDOW && !haveDOM) { // get day using just the DAY_OF_WEEK token
 256   
 
 257  45
                 int daysLost = 0;
 258  45
                 int currentDOW = dayOfWeek(dayOfMonth, month, year);
 259   
 
 260  156
                 for (int i = currentDOW + 7; i > currentDOW; i--) {
 261  156
                     int testDOW = i % 7;
 262   
 
 263  156
                     if (((1L << testDOW) & validDaysOfWeek) != 0) {
 264  45
                         dayOfMonth -= daysLost;
 265   
 
 266  45
                         if (dayOfMonth < 1) {
 267   
                             // We've wrapped back a month
 268  12
                             month--;
 269  12
                             dayOfMonth += numberOfDaysInMonth(month, year);
 270  12
                             retry = true;
 271   
                         }
 272   
 
 273  45
                         if (currentDOW != testDOW) {
 274  30
                             hour = lookupMax[HOUR];
 275  30
                             minute = lookupMax[MINUTE];
 276   
                         }
 277   
 
 278  45
                         break;
 279   
                     }
 280   
 
 281  111
                     daysLost++;
 282   
                 }
 283   
 
 284  45
                 if (retry) {
 285  12
                     continue;
 286   
                 }
 287   
             }
 288   
 
 289   
             // Clean up if the hour has been wrapped
 290  159
             if (hour < 0) {
 291  9
                 hour += 24;
 292  9
                 dayOfMonth--;
 293  9
                 continue;
 294   
             }
 295   
 
 296   
             // get hour...................................................
 297  150
             if (validHours != Long.MAX_VALUE) {
 298   
                 // Find the highest valid hour that is below the current hour
 299  372
                 for (int i = hour + 24; i > hour; i--) {
 300  372
                     int testHour = i % 24;
 301   
 
 302  372
                     if (((1L << testHour) & validHours) != 0) {
 303  90
                         if (testHour > hour) {
 304   
                             // We've found an hour, but we had to move back a day
 305  12
                             dayOfMonth--;
 306  12
                             retry = true;
 307   
                         }
 308   
 
 309  90
                         if (hour != testHour) {
 310  24
                             minute = lookupMax[MINUTE];
 311   
                         }
 312   
 
 313  90
                         hour = testHour;
 314  90
                         break;
 315   
                     }
 316   
                 }
 317   
 
 318  90
                 if (retry) {
 319  12
                     continue;
 320   
                 }
 321   
             }
 322   
 
 323   
             // get minute.................................................
 324  138
             if (validMinutes != Long.MAX_VALUE) {
 325   
                 // Find the highest valid minute that is below the current minute
 326  633
                 for (int i = minute + 60; i > minute; i--) {
 327  633
                     int testMinute = i % 60;
 328   
 
 329  633
                     if (((1L << testMinute) & validMinutes) != 0) {
 330  90
                         if (testMinute > minute) {
 331   
                             // We've found a minute, but we had to move back an hour
 332  18
                             hour--;
 333  18
                             retry = true;
 334   
                         }
 335   
 
 336  90
                         minute = testMinute;
 337  90
                         break;
 338   
                     }
 339   
                 }
 340   
 
 341  90
                 if (retry) {
 342  18
                     continue;
 343   
                 }
 344   
             }
 345   
 
 346  120
             break;
 347   
         }
 348   
 
 349   
         // OK, all done. Return the adjusted time value (adjusting this is faster than creating a new Calendar object)
 350  120
         cal.set(Calendar.YEAR, year);
 351  120
         cal.set(Calendar.MONTH, month - 1); // Calendar is 0-based for this field, and we are 1-based
 352  120
         cal.set(Calendar.DAY_OF_MONTH, dayOfMonth);
 353  120
         cal.set(Calendar.HOUR_OF_DAY, hour);
 354  120
         cal.set(Calendar.MINUTE, minute);
 355  120
         cal.set(Calendar.SECOND, 0);
 356  120
         cal.set(Calendar.MILLISECOND, 0);
 357   
 
 358  120
         return cal.getTime().getTime();
 359   
     }
 360   
 
 361   
     /**
 362   
     * Takes a cron expression as an input parameter, and extracts from it the
 363   
     * relevant minutes/hours/days/months that the expression matches.
 364   
     *
 365   
     * @param expression  A valid cron expression.
 366   
     * @throws ParseException If the supplied expression could not be parsed.
 367   
     */
 368  234
     private void parseExpression(String expression) throws ParseException {
 369  234
         try {
 370   
             // Reset all the lookup data
 371  234
             for (int i = 0; i < lookup.length; lookup[i++] = 0) {
 372  1170
                 lookupMin[i] = Integer.MAX_VALUE;
 373  1170
                 lookupMax[i] = -1;
 374   
             }
 375   
 
 376   
             // Create some character arrays to hold the extracted field values
 377  234
             char[][] token = new char[NUMBER_OF_CRON_FIELDS][];
 378   
 
 379   
             // Extract the supplied expression into another character array
 380   
             // for speed
 381  234
             int length = expression.length();
 382  234
             char[] expr = new char[length];
 383  234
             expression.getChars(0, length, expr, 0);
 384   
 
 385  234
             int field = 0;
 386  234
             int startIndex = 0;
 387  234
             boolean inWhitespace = true;
 388   
 
 389   
             // Extract the various cron fields from the expression
 390  234
             for (int i = 0; (i < length) && (field < NUMBER_OF_CRON_FIELDS);
 391   
                     i++) {
 392  3198
                 boolean haveChar = (expr[i] != ' ') && (expr[i] != '\t');
 393   
 
 394  3198
                 if (haveChar) {
 395   
                     // We have a text character of some sort
 396  2253
                     if (inWhitespace) {
 397  1152
                         startIndex = i; // Remember the start of this token
 398  1152
                         inWhitespace = false;
 399   
                     }
 400   
                 }
 401   
 
 402  3198
                 if (i == (length - 1)) { // Adjustment for when we reach the end of the expression
 403  231
                     i++;
 404   
                 }
 405   
 
 406  3198
                 if (!(haveChar || inWhitespace) || (i == length)) {
 407   
                     // We've reached the end of a token. Copy it into a new char array
 408  1152
                     token[field] = new char[i - startIndex];
 409  1152
                     System.arraycopy(expr, startIndex, token[field], 0, i - startIndex);
 410  1152
                     inWhitespace = true;
 411  1152
                     field++;
 412   
                 }
 413   
             }
 414   
 
 415  234
             if (field < NUMBER_OF_CRON_FIELDS) {
 416  6
                 throw new ParseException("Unexpected end of expression while parsing \"" + expression + "\". Cron expressions require 5 separate fields.", length);
 417   
             }
 418   
 
 419   
             // OK, we've broken the string up into the 5 cron fields, now lets add
 420   
             // each field to their lookup table.
 421  228
             for (field = 0; field < NUMBER_OF_CRON_FIELDS; field++) {
 422  1032
                 startIndex = 0;
 423   
 
 424  1032
                 boolean inDelimiter = true;
 425   
 
 426   
                 // We add each comma-delimited element seperately.
 427  1032
                 int elementLength = token[field].length;
 428   
 
 429  1032
                 for (int i = 0; i < elementLength; i++) {
 430  2127
                     boolean haveElement = token[field][i] != ',';
 431   
 
 432  2127
                     if (haveElement) {
 433   
                         // We have a character from an element in the token
 434  2034
                         if (inDelimiter) {
 435  1125
                             startIndex = i;
 436  1125
                             inDelimiter = false;
 437   
                         }
 438   
                     }
 439   
 
 440  2127
                     if (i == (elementLength - 1)) { // Adjustment for when we reach the end of the token
 441  1032
                         i++;
 442   
                     }
 443   
 
 444  2127
                     if (!(haveElement || inDelimiter) || (i == elementLength)) {
 445   
                         // We've reached the end of an element. Copy it into a new char array
 446  1125
                         char[] element = new char[i - startIndex];
 447  1125
                         System.arraycopy(token[field], startIndex, element, 0, i - startIndex);
 448   
 
 449   
                         // Add the element to our datastructure.
 450  1125
                         storeExpressionValues(element, field);
 451   
 
 452  1038
                         inDelimiter = true;
 453   
                     }
 454   
                 }
 455   
 
 456  945
                 if (lookup[field] == 0) {
 457  0
                     throw new ParseException("Token " + new String(token[field]) + " contains no valid entries for this field.", 0);
 458   
                 }
 459   
             }
 460   
 
 461   
             // Remove any months that will never be valid
 462  141
             switch (lookupMin[DAY_OF_MONTH]) {
 463  3
                 case 31:
 464  3
                     lookup[MONTH] &= (0xFFF - 0x528); // Binary 010100101000 - the months that have 30 days
 465  6
                 case 30:
 466  9
                     lookup[MONTH] &= (0xFFF - 0x2); // Binary 000000000010 - February
 467   
 
 468  9
                     if (lookup[MONTH] == 0) {
 469  6
                         throw new ParseException("The cron expression \"" + expression + "\" will never match any months - the day of month field is out of range.", 0);
 470   
                     }
 471   
             }
 472   
 
 473   
             // Check that we don't have both a day of month and a day of week field.
 474  135
             if ((lookup[DAY_OF_MONTH] != Long.MAX_VALUE) && (lookup[DAY_OF_WEEK] != Long.MAX_VALUE)) {
 475  3
                 throw new ParseException("The cron expression \"" + expression + "\" is invalid. Having both a day-of-month and day-of-week field is not supported.", 0);
 476   
             }
 477   
         } catch (Exception e) {
 478  102
             if (e instanceof ParseException) {
 479  102
                 throw (ParseException) e;
 480   
             } else {
 481  0
                 throw new ParseException("Illegal cron expression format (" + e.toString() + ")", 0);
 482   
             }
 483   
         }
 484   
     }
 485   
 
 486   
     /**
 487   
     * Stores the values for the supplied cron element into the specified field.
 488   
     *
 489   
     * @param element  The cron element to store. A cron element is a single component
 490   
     * of a cron expression. For example, the complete set of elements for the cron expression
 491   
     * <code>30 0,6,12,18 * * *</code> would be <code>{"30", "0", "6", "12", "18", "*", "*", "*"}</code>.
 492   
     * @param field  The field that this expression belongs to. Valid values are {@link #MINUTE},
 493   
     * {@link #HOUR}, {@link #DAY_OF_MONTH}, {@link #MONTH} and {@link #DAY_OF_WEEK}.
 494   
     *
 495   
     * @throws ParseException if there was a problem parsing the supplied element.
 496   
     */
 497  1125
     private void storeExpressionValues(char[] element, int field) throws ParseException {
 498  1125
         int i = 0;
 499   
 
 500  1125
         int start = -99;
 501  1125
         int end = -99;
 502  1125
         int interval = -1;
 503  1125
         boolean wantValue = true;
 504  1125
         boolean haveInterval = false;
 505   
 
 506  1125
         while ((interval < 0) && (i < element.length)) {
 507  1341
             char ch = element[i++];
 508   
 
 509   
             // Handle the wildcard character - it can only ever occur at the start of an element
 510  1341
             if ((i == 1) && (ch == '*')) {
 511   
                 // Handle the special case where we have '*' and nothing else
 512  663
                 if (i >= element.length) {
 513  660
                     addToLookup(-1, -1, field, 1);
 514  660
                     return;
 515   
                 }
 516   
 
 517  3
                 start = -1;
 518  3
                 end = -1;
 519  3
                 wantValue = false;
 520  3
                 continue;
 521   
             }
 522   
 
 523  678
             if (wantValue) {
 524   
                 // Handle any numbers
 525  567
                 if ((ch >= '0') && (ch <= '9')) {
 526  423
                     ValueSet vs = getValue(ch - '0', element, i);
 527   
 
 528  423
                     if (start == -99) {
 529  342
                         start = vs.value;
 530  81
                     } else if (!haveInterval) {
 531  48
                         end = vs.value;
 532   
                     } else {
 533  33
                         if (end == -99) {
 534  18
                             end = MAX_VALUE[field];
 535   
                         }
 536   
 
 537  33
                         interval = vs.value;
 538   
                     }
 539   
 
 540  423
                     i = vs.pos;
 541  423
                     wantValue = false;
 542  423
                     continue;
 543   
                 }
 544   
 
 545  144
                 if (!haveInterval && (end == -99)) {
 546   
                     // Handle any months that have been suplied as words
 547  144
                     if (field == MONTH) {
 548  81
                         if (start == -99) {
 549  72
                             start = getMonthVal(ch, element, i++);
 550   
                         } else {
 551  9
                             end = getMonthVal(ch, element, i++);
 552   
                         }
 553   
 
 554  51
                         wantValue = false;
 555   
 
 556   
                         // Skip past the rest of the month name
 557  51
                         while (++i < element.length) {
 558  81
                             int c = element[i] | 0x20;
 559   
 
 560  81
                             if ((c < 'a') || (c > 'z')) {
 561  12
                                 break;
 562   
                             }
 563   
                         }
 564   
 
 565  51
                         continue;
 566  63
                     } else if (field == DAY_OF_WEEK) {
 567  54
                         if (start == -99) {
 568  42
                             start = getDayOfWeekVal(ch, element, i++);
 569   
                         } else {
 570  12
                             end = getDayOfWeekVal(ch, element, i++);
 571   
                         }
 572   
 
 573  36
                         wantValue = false;
 574   
 
 575   
                         // Skip past the rest of the day name
 576  36
                         while (++i < element.length) {
 577  72
                             int c = element[i] | 0x20;
 578   
 
 579  72
                             if ((c < 'a') || (c > 'z')) {
 580  12
                                 break;
 581   
                             }
 582   
                         }
 583   
 
 584  36
                         continue;
 585   
                     }
 586   
                 }
 587   
             } else {
 588   
                 // Handle the range character. A range character is only valid if we have a start but no end value
 589  111
                 if ((ch == '-') && (start != -99) && (end == -99)) {
 590  72
                     wantValue = true;
 591  72
                     continue;
 592   
                 }
 593   
 
 594   
                 // Handle an interval. An interval is valid as long as we have a start value
 595  39
                 if ((ch == '/') && (start != -99)) {
 596  33
                     wantValue = true;
 597  33
                     haveInterval = true;
 598  33
                     continue;
 599   
                 }
 600   
             }
 601   
 
 602  15
             throw makeParseException("Invalid character encountered while parsing element", element, i);
 603   
         }
 604   
 
 605  402
         if (element.length > i) {
 606  3
             throw makeParseException("Extraneous characters found while parsing element", element, i);
 607   
         }
 608   
 
 609  399
         if (end == -99) {
 610  318
             end = start;
 611   
         }
 612   
 
 613  399
         if (interval < 0) {
 614  369
             interval = 1;
 615   
         }
 616   
 
 617  399
         addToLookup(start, end, field, interval);
 618   
     }
 619   
 
 620   
     /**
 621   
     * Extracts a numerical value from inside a character array.
 622   
     *
 623   
     * @param value    The value of the first character
 624   
     * @param element  The character array we're extracting the value from
 625   
     * @param i        The index into the array of the next character to process
 626   
     *
 627   
     * @return the new index and the extracted value
 628   
     */
 629  423
     private ValueSet getValue(int value, char[] element, int i) {
 630  423
         ValueSet result = new ValueSet();
 631  423
         result.value = value;
 632   
 
 633  423
         if (i >= element.length) {
 634  195
             result.pos = i;
 635  195
             return result;
 636   
         }
 637   
 
 638  228
         char ch = element[i];
 639   
 
 640  228
         while ((ch >= '0') && (ch <= '9')) {
 641  168
             result.value = (result.value * 10) + (ch - '0');
 642   
 
 643  168
             if (++i >= element.length) {
 644  141
                 break;
 645   
             }
 646   
 
 647  27
             ch = element[i];
 648   
         }
 649   
 
 650  228
         result.pos = i;
 651   
 
 652  228
         return result;
 653   
     }
 654   
 
 655   
     /**
 656   
     * Adds a group of valid values to the lookup table for the specified field. This method
 657   
     * handles ranges that increase in arbitrary step sizes. It is also possible to add a single
 658   
     * value by specifying a range with the same start and end values.
 659   
     *
 660   
     * @param start The starting value for the range. Supplying a value that is less than zero
 661   
     * will cause the minimum allowable value for the specified field to be used as the start value.
 662   
     * @param end   The maximum value that can be added (ie the upper bound). If the step size is
 663   
     * greater than one, this maximum value may not necessarily end up being added. Supplying a
 664   
     * value that is less than zero will cause the maximum allowable value for the specified field
 665   
     * to be used as the upper bound.
 666   
     * @param field The field that the values should be added to.
 667   
     * @param interval Specifies the step size for the range. Any values less than one will be
 668   
     * treated as a single step interval.
 669   
     */
 670  1059
     private void addToLookup(int start, int end, int field, int interval) throws ParseException {
 671   
         // deal with the supplied range
 672  1059
         if (start == end) {
 673  981
             if (start < 0) {
 674   
                 // We're setting the entire range of values
 675  663
                 start = lookupMin[field] = MIN_VALUE[field];
 676  663
                 end = lookupMax[field] = MAX_VALUE[field];
 677   
 
 678  663
                 if (interval <= 1) {
 679  660
                     lookup[field] = Long.MAX_VALUE;
 680  660
                     return;
 681   
                 }
 682   
             } else {
 683   
                 // We're only setting a single value - check that it is in range
 684  318
                 if (start < MIN_VALUE[field]) {
 685  3
                     throw new ParseException("Value " + start + " in field " + field + " is lower than the minimum allowable value for this field (min=" + MIN_VALUE[field] + ")", 0);
 686  315
                 } else if (start > MAX_VALUE[field]) {
 687  6
                     throw new ParseException("Value " + start + " in field " + field + " is higher than the maximum allowable value for this field (max=" + MAX_VALUE[field] + ")", 0);
 688   
                 }
 689   
             }
 690   
         } else {
 691   
             // For ranges, if the start is bigger than the end value then swap them over
 692  78
             if (start > end) {
 693  6
                 end ^= start;
 694  6
                 start ^= end;
 695  6
                 end ^= start;
 696   
             }
 697   
 
 698  78
             if (start < 0) {
 699  0
                 start = MIN_VALUE[field];
 700  78
             } else if (start < MIN_VALUE[field]) {
 701  6
                 throw new ParseException("Value " + start + " in field " + field + " is lower than the minimum allowable value for this field (min=" + MIN_VALUE[field] + ")", 0);
 702   
             }
 703   
 
 704  72
             if (end < 0) {
 705  0
                 end = MAX_VALUE[field];
 706  72
             } else if (end > MAX_VALUE[field]) {
 707  6
                 throw new ParseException("Value " + end + " in field " + field + " is higher than the maximum allowable value for this field (max=" + MAX_VALUE[field] + ")", 0);
 708   
             }
 709   
         }
 710   
 
 711  378
         if (interval < 1) {
 712  0
             interval = 1;
 713   
         }
 714   
 
 715  378
         int i = start - MIN_VALUE[field];
 716   
 
 717   
         // Populate the lookup table by setting all the bits corresponding to the valid field values
 718  378
         for (i = start - MIN_VALUE[field]; i <= (end - MIN_VALUE[field]);
 719   
                 i += interval) {
 720  684
             lookup[field] |= (1L << i);
 721   
         }
 722   
 
 723   
         // Make sure we remember the minimum value set so far
 724   
         // Keep track of the highest and lowest values that have been added to this field so far
 725  378
         if (lookupMin[field] > start) {
 726  288
             lookupMin[field] = start;
 727   
         }
 728   
 
 729  378
         i += (MIN_VALUE[field] - interval);
 730   
 
 731  378
         if (lookupMax[field] < i) {
 732  366
             lookupMax[field] = i;
 733   
         }
 734   
     }
 735   
 
 736   
     /**
 737   
     * Indicates if a year is a leap year or not.
 738   
     *
 739   
     * @param year The year to check
 740   
     *
 741   
     * @return <code>true</code> if the year is a leap year, <code>false</code> otherwise.
 742   
     */
 743  39
     private boolean isLeapYear(int year) {
 744  39
         return (((year % 4) == 0) && ((year % 100) != 0)) || ((year % 400) == 0);
 745   
     }
 746   
 
 747   
     /**
 748   
     * Calculate the day of the week. Sunday = 0, Monday = 1, ... , Saturday = 6. The formula
 749   
     * used is an optimized version of Zeller's Congruence.
 750   
     *
 751   
     * @param day        The day of the month (1-31)
 752   
     * @param month      The month (1 - 12)
 753   
     * @param year       The year
 754   
     * @return
 755   
     */
 756  45
     private int dayOfWeek(int day, int month, int year) {
 757  45
         day += ((month < 3) ? year-- : (year - 2));
 758  45
         return ((((23 * month) / 9) + day + 4 + (year / 4)) - (year / 100) + (year / 400)) % 7;
 759   
     }
 760   
 
 761   
     /**
 762   
     * Retrieves the number of days in the supplied month, taking into account leap years.
 763   
     * If the month value is outside the range <code>MIN_VALUE[MONTH] - MAX_VALUE[MONTH]</code>
 764   
     * then the year will be adjusted accordingly and the correct number of days will still
 765   
     * be returned.
 766   
     *
 767   
     * @param month The month of interest.
 768   
     * @param year  The year we are checking.
 769   
     *
 770   
     * @return The number of days in the month.
 771   
     */
 772  426
     private int numberOfDaysInMonth(int month, int year) {
 773  426
         while (month < 1) {
 774  24
             month += 12;
 775  24
             year--;
 776   
         }
 777   
 
 778  426
         while (month > 12) {
 779  0
             month -= 12;
 780  0
             year++;
 781   
         }
 782   
 
 783  426
         if (month == 2) {
 784  39
             return isLeapYear(year) ? 29 : 28;
 785   
         } else {
 786  387
             return DAYS_IN_MONTH[month - 1];
 787   
         }
 788   
     }
 789   
 
 790   
     /**
 791   
     * Quickly retrieves the day of week value (Sun = 0, ... Sat = 6) that corresponds to the
 792   
     * day name that is specified in the character array. Only the first 3 characters are taken
 793   
     * into account; the rest are ignored.
 794   
     *
 795   
     * @param element The character array
 796   
     * @param i       The index to start looking at
 797   
     * @return        The day of week value
 798   
     */
 799  54
     private int getDayOfWeekVal(char ch1, char[] element, int i) throws ParseException {
 800  54
         if ((i + 1) >= element.length) {
 801  3
             throw makeParseException("Unexpected end of element encountered while parsing a day name", element, i);
 802   
         }
 803   
 
 804  51
         int ch2 = element[i] | 0x20;
 805  51
         int ch3 = element[i + 1] | 0x20;
 806   
 
 807  51
         switch (ch1 | 0x20) {
 808  18
             case 's': // Sunday, Saturday
 809   
 
 810  18
                 if ((ch2 == 'u') && (ch3 == 'n')) {
 811  9
                     return 0;
 812   
                 }
 813   
 
 814  9
                 if ((ch2 == 'a') && (ch3 == 't')) {
 815  6
                     return 6;
 816   
                 }
 817   
 
 818  3
                 break;
 819  6
             case 'm': // Monday
 820   
 
 821  6
                 if ((ch2 == 'o') && (ch3 == 'n')) {
 822  3
                     return 1;
 823   
                 }
 824   
 
 825  3
                 break;
 826  15
             case 't': // Tuesday, Thursday
 827   
 
 828  15
                 if ((ch2 == 'u') && (ch3 == 'e')) {
 829  6
                     return 2;
 830   
                 }
 831   
 
 832  9
                 if ((ch2 == 'h') && (ch3 == 'u')) {
 833  6
                     return 4;
 834   
                 }
 835   
 
 836  3
                 break;
 837  6
             case 'w': // Wednesday
 838   
 
 839  6
                 if ((ch2 == 'e') && (ch3 == 'd')) {
 840  3
                     return 3;
 841   
                 }
 842   
 
 843  3
                 break;
 844  6
             case 'f': // Friday
 845   
 
 846  6
                 if ((ch2 == 'r') && (ch3 == 'i')) {
 847  3
                     return 5;
 848   
                 }
 849   
 
 850  3
                 break;
 851   
         }
 852   
 
 853  15
         throw makeParseException("Unexpected character while parsing a day name", element, i - 1);
 854   
     }
 855   
 
 856   
     /**
 857   
     * Quickly retrieves the month value (Jan = 1, ..., Dec = 12) that corresponds to the month
 858   
     * name that is specified in the character array. Only the first 3 characters are taken
 859   
     * into account; the rest are ignored.
 860   
     *
 861   
     * @param element The character array
 862   
     * @param i       The index to start looking at
 863   
     * @return        The month value
 864   
     */
 865  81
     private int getMonthVal(char ch1, char[] element, int i) throws ParseException {
 866  81
         if ((i + 1) >= element.length) {
 867  0
             throw makeParseException("Unexpected end of element encountered while parsing a month name", element, i);
 868   
         }
 869   
 
 870  81
         int ch2 = element[i] | 0x20;
 871  81
         int ch3 = element[i + 1] | 0x20;
 872   
 
 873  81
         switch (ch1 | 0x20) {
 874  21
             case 'j': // January, June, July
 875   
 
 876  21
                 if ((ch2 == 'a') && (ch3 == 'n')) {
 877  6
                     return 1;
 878   
                 }
 879   
 
 880  15
                 if (ch2 == 'u') {
 881  12
                     if (ch3 == 'n') {
 882  6
                         return 6;
 883   
                     }
 884   
 
 885  6
                     if (ch3 == 'l') {
 886  3
                         return 7;
 887   
                     }
 888   
                 }
 889   
 
 890  6
                 break;
 891  9
             case 'f': // February
 892   
 
 893  9
                 if ((ch2 == 'e') && (ch3 == 'b')) {
 894  6
                     return 2;
 895   
                 }
 896   
 
 897  3
                 break;
 898  12
             case 'm': // March, May
 899   
 
 900  12
                 if (ch2 == 'a') {
 901  9
                     if (ch3 == 'r') {
 902  3
                         return 3;
 903   
                     }
 904   
 
 905  6
                     if (ch3 == 'y') {
 906  3
                         return 5;
 907   
                     }
 908   
                 }
 909   
 
 910  6
                 break;
 911  15
             case 'a': // April, August
 912   
 
 913  15
                 if ((ch2 == 'p') && (ch3 == 'r')) {
 914  6
                     return 4;
 915   
                 }
 916   
 
 917  9
                 if ((ch2 == 'u') && (ch3 == 'g')) {
 918  6
                     return 8;
 919   
                 }
 920   
 
 921  3
                 break;
 922  6
             case 's': // September
 923   
 
 924  6
                 if ((ch2 == 'e') && (ch3 == 'p')) {
 925  3
                     return 9;
 926   
                 }
 927   
 
 928  3
                 break;
 929  6
             case 'o': // October
 930   
 
 931  6
                 if ((ch2 == 'c') && (ch3 == 't')) {
 932  3
                     return 10;
 933   
                 }
 934   
 
 935  3
                 break;
 936  6
             case 'n': // November
 937   
 
 938  6
                 if ((ch2 == 'o') && (ch3 == 'v')) {
 939  3
                     return 11;
 940   
                 }
 941   
 
 942  3
                 break;
 943  6
             case 'd': // December
 944   
 
 945  6
                 if ((ch2 == 'e') && (ch3 == 'c')) {
 946  3
                     return 12;
 947   
                 }
 948   
 
 949  3
                 break;
 950   
         }
 951   
 
 952  30
         throw makeParseException("Unexpected character while parsing a month name", element, i - 1);
 953   
     }
 954   
 
 955   
     /**
 956   
     * Recreates the original human-readable cron expression based on the internal
 957   
     * datastructure values.
 958   
     *
 959   
     * @return A cron expression that corresponds to the current state of the
 960   
     * internal data structure.
 961   
     */
 962  12
     public String getExpressionSummary() {
 963  12
         StringBuffer buf = new StringBuffer();
 964   
 
 965  12
         buf.append(getExpressionSetSummary(MINUTE)).append(' ');
 966  12
         buf.append(getExpressionSetSummary(HOUR)).append(' ');
 967  12
         buf.append(getExpressionSetSummary(DAY_OF_MONTH)).append(' ');
 968  12
         buf.append(getExpressionSetSummary(MONTH)).append(' ');
 969  12
         buf.append(getExpressionSetSummary(DAY_OF_WEEK));
 970   
 
 971  12
         return buf.toString();
 972   
     }
 973   
 
 974   
     /**
 975   
     * <p>Converts the internal datastructure that holds a particular cron field into
 976   
     * a human-readable list of values of the field's contents. For example, if the
 977   
     * <code>DAY_OF_WEEK</code> field was submitted that had Sunday and Monday specified,
 978   
     * the string <code>0,1</code> would be returned.</p>
 979   
     *
 980   
     * <p>If the field contains all possible values, <code>*</code> will be returned.
 981   
     *
 982   
     * @param field The field.
 983   
     *
 984   
     * @return A human-readable string representation of the field's contents.
 985   
     */
 986  60
     private String getExpressionSetSummary(int field) {
 987  60
         if (lookup[field] == Long.MAX_VALUE) {
 988  39
             return "*";
 989   
         }
 990   
 
 991  21
         StringBuffer buf = new StringBuffer();
 992   
 
 993  21
         boolean first = true;
 994   
 
 995  21
         for (int i = MIN_VALUE[field]; i <= MAX_VALUE[field]; i++) {
 996  741
             if ((lookup[field] & (1L << (i - MIN_VALUE[field]))) != 0) {
 997  102
                 if (!first) {
 998  81
                     buf.append(",");
 999   
                 } else {
 1000  21
                     first = false;
 1001   
                 }
 1002   
 
 1003  102
                 buf.append(String.valueOf(i));
 1004   
             }
 1005   
         }
 1006   
 
 1007  21
         return buf.toString();
 1008   
     }
 1009   
 
 1010   
     /**
 1011   
     * Makes a <code>ParseException</code>. The exception message is constructed by
 1012   
     * taking the given message parameter and appending the supplied character data
 1013   
     * to the end of it. for example, if <code>msg == "Invalid character
 1014   
     * encountered"</code> and <code>data == {'A','g','u','s','t'}</code>, the resultant
 1015   
     * error message would be <code>"Invalid character encountered [Agust]"</code>.
 1016   
     *
 1017   
     * @param msg       The error message
 1018   
     * @param data      The data that the message
 1019   
     * @param offset    The offset into the data where the error was encountered.
 1020   
     *
 1021   
     * @return a newly created <code>ParseException</code> object.
 1022   
     */
 1023  66
     private ParseException makeParseException(String msg, char[] data, int offset) {
 1024  66
         char[] buf = new char[msg.length() + data.length + 3];
 1025  66
         int msgLen = msg.length();
 1026  66
         System.arraycopy(msg.toCharArray(), 0, buf, 0, msgLen);
 1027  66
         buf[msgLen] = ' ';
 1028  66
         buf[msgLen + 1] = '[';
 1029  66
         System.arraycopy(data, 0, buf, msgLen + 2, data.length);
 1030  66
         buf[buf.length - 1] = ']';
 1031  66
         return new ParseException(new String(buf), offset);
 1032   
     }
 1033   
 }
 1034   
 
 1035   
 
 1036   
 class ValueSet {
 1037   
     public int pos;
 1038   
     public int value;
 1039   
 }
 1040