Clover coverage report -
Coverage timestamp: Sun Mar 5 2006 06:05:21 CST
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 1,042   Methods: 18
NCLOC: 611   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: ltorunski $
 18    * @version $Revision: 1.2 $
 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  20 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  316 public FastCronParser(String cronExpression) throws ParseException {
 89  316 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  8040332 public void setCronExpression(String cronExpression) throws ParseException {
 100  8040332 if (cronExpression == null) {
 101  4 throw new IllegalArgumentException("Cron time expression cannot be null");
 102    }
 103   
 104  8040328 this.cronExpression = cronExpression;
 105  8040328 parseExpression(cronExpression);
 106    }
 107   
 108    /**
 109    * Retrieves the current cron expression.
 110    *
 111    * @return the current cron expression.
 112    */
 113  12 public String getCronExpression() {
 114  12 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  16040168 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  16040168 Calendar cal = new GregorianCalendar();
 142  16040168 cal.setTimeInMillis(time);
 143   
 144  16040168 int minute = cal.get(Calendar.MINUTE);
 145  16040168 int hour = cal.get(Calendar.HOUR_OF_DAY);
 146  16040168 int dayOfMonth = cal.get(Calendar.DAY_OF_MONTH);
 147  16040168 int month = cal.get(Calendar.MONTH) + 1; // Calendar is 0-based for this field, and we are 1-based
 148  16040168 int year = cal.get(Calendar.YEAR);
 149   
 150  16040168 long validMinutes = lookup[MINUTE];
 151  16040168 long validHours = lookup[HOUR];
 152  16040168 long validDaysOfMonth = lookup[DAY_OF_MONTH];
 153  16040168 long validMonths = lookup[MONTH];
 154  16040168 long validDaysOfWeek = lookup[DAY_OF_WEEK];
 155   
 156    // Find out if we have a Day of Week or Day of Month field
 157  16040168 boolean haveDOM = validDaysOfMonth != Long.MAX_VALUE;
 158  16040168 boolean haveDOW = validDaysOfWeek != Long.MAX_VALUE;
 159   
 160  16040168 boolean skippedNonLeapYear = false;
 161   
 162  16040168 while (true) {
 163  16040316 boolean retry = false;
 164   
 165    // Clean up the month if it was wrapped in a previous iteration
 166  16040316 if (month < 1) {
 167  28 month += 12;
 168  28 year--;
 169    }
 170   
 171    // get month...................................................
 172  16040316 boolean found = false;
 173   
 174  16040316 if (validMonths != Long.MAX_VALUE) {
 175  8040108 for (int i = month + 11; i > (month - 1); i--) {
 176  88480756 int testMonth = (i % 12) + 1;
 177   
 178    // Check if the month is valid
 179  88480756 if (((1L << (testMonth - 1)) & validMonths) != 0) {
 180  8040108 if ((testMonth > month) || skippedNonLeapYear) {
 181  8040060 year--;
 182    }
 183   
 184    // Check there are enough days in this month (catches non leap-years trying to match the 29th Feb)
 185  8040108 int numDays = numberOfDaysInMonth(testMonth, year);
 186   
 187  8040108 if (!haveDOM || (numDays >= lookupMin[DAY_OF_MONTH])) {
 188  8040072 if ((month != testMonth) || skippedNonLeapYear) {
 189    // New DOM = min(maxDOM, prevDays); ie, the highest valid value
 190  8040056 dayOfMonth = (numDays <= lookupMax[DAY_OF_MONTH]) ? numDays : lookupMax[DAY_OF_MONTH];
 191  8040056 hour = lookupMax[HOUR];
 192  8040056 minute = lookupMax[MINUTE];
 193  8040056 month = testMonth;
 194    }
 195   
 196  8040072 found = true;
 197  8040072 break;
 198    }
 199    }
 200    }
 201   
 202  8040108 skippedNonLeapYear = false;
 203   
 204  8040108 if (!found) {
 205    // The only time we drop out here is when we're searching for the 29th of February and no other date!
 206  36 skippedNonLeapYear = true;
 207  36 continue;
 208    }
 209    }
 210   
 211    // Clean up if the dayOfMonth was wrapped. This takes leap years into account.
 212  16040280 if (dayOfMonth < 1) {
 213  20 month--;
 214  20 dayOfMonth += numberOfDaysInMonth(month, year);
 215  20 hour = lookupMax[HOUR];
 216  20 continue;
 217    }
 218   
 219    // get day...................................................
 220  16040260 if (haveDOM && !haveDOW) { // get day using just the DAY_OF_MONTH token
 221   
 222  8040072 int daysInThisMonth = numberOfDaysInMonth(month, year);
 223  8040072 int daysInPreviousMonth = numberOfDaysInMonth(month - 1, year);
 224   
 225    // Find the highest valid day that is below the current day
 226  8040332 for (int i = dayOfMonth + 30; i > (dayOfMonth - 1); i--) {
 227  8040332 int testDayOfMonth = (i % 31) + 1;
 228   
 229    // Skip over any days that don't actually exist (eg 31st April)
 230  8040332 if ((testDayOfMonth <= dayOfMonth) && (testDayOfMonth > daysInThisMonth)) {
 231  0 continue;
 232    }
 233   
 234  8040332 if ((testDayOfMonth > dayOfMonth) && (testDayOfMonth > daysInPreviousMonth)) {
 235  4 continue;
 236    }
 237   
 238  8040328 if (((1L << (testDayOfMonth - 1)) & validDaysOfMonth) != 0) {
 239  8040072 if (testDayOfMonth > dayOfMonth) {
 240    // We've found a valid day, but we had to move back a month
 241  24 month--;
 242  24 retry = true;
 243    }
 244   
 245  8040072 if (dayOfMonth != testDayOfMonth) {
 246  28 hour = lookupMax[HOUR];
 247  28 minute = lookupMax[MINUTE];
 248    }
 249   
 250  8040072 dayOfMonth = testDayOfMonth;
 251  8040072 break;
 252    }
 253    }
 254   
 255  8040072 if (retry) {
 256  24 continue;
 257    }
 258  8000188 } else if (haveDOW && !haveDOM) { // get day using just the DAY_OF_WEEK token
 259   
 260  60 int daysLost = 0;
 261  60 int currentDOW = dayOfWeek(dayOfMonth, month, year);
 262   
 263  208 for (int i = currentDOW + 7; i > currentDOW; i--) {
 264  208 int testDOW = i % 7;
 265   
 266  208 if (((1L << testDOW) & validDaysOfWeek) != 0) {
 267  60 dayOfMonth -= daysLost;
 268   
 269  60 if (dayOfMonth < 1) {
 270    // We've wrapped back a month
 271  16 month--;
 272  16 dayOfMonth += numberOfDaysInMonth(month, year);
 273  16 retry = true;
 274    }
 275   
 276  60 if (currentDOW != testDOW) {
 277  40 hour = lookupMax[HOUR];
 278  40 minute = lookupMax[MINUTE];
 279    }
 280   
 281  60 break;
 282    }
 283   
 284  148 daysLost++;
 285    }
 286   
 287  60 if (retry) {
 288  16 continue;
 289    }
 290    }
 291   
 292    // Clean up if the hour has been wrapped
 293  16040220 if (hour < 0) {
 294  12 hour += 24;
 295  12 dayOfMonth--;
 296  12 continue;
 297    }
 298   
 299    // get hour...................................................
 300  16040208 if (validHours != Long.MAX_VALUE) {
 301    // Find the highest valid hour that is below the current hour
 302  8040496 for (int i = hour + 24; i > hour; i--) {
 303  8040496 int testHour = i % 24;
 304   
 305  8040496 if (((1L << testHour) & validHours) != 0) {
 306  8040120 if (testHour > hour) {
 307    // We've found an hour, but we had to move back a day
 308  16 dayOfMonth--;
 309  16 retry = true;
 310    }
 311   
 312  8040120 if (hour != testHour) {
 313  32 minute = lookupMax[MINUTE];
 314    }
 315   
 316  8040120 hour = testHour;
 317  8040120 break;
 318    }
 319    }
 320   
 321  8040120 if (retry) {
 322  16 continue;
 323    }
 324    }
 325   
 326    // get minute.................................................
 327  16040192 if (validMinutes != Long.MAX_VALUE) {
 328    // Find the highest valid minute that is below the current minute
 329  8040844 for (int i = minute + 60; i > minute; i--) {
 330  8040844 int testMinute = i % 60;
 331   
 332  8040844 if (((1L << testMinute) & validMinutes) != 0) {
 333  8040120 if (testMinute > minute) {
 334    // We've found a minute, but we had to move back an hour
 335  24 hour--;
 336  24 retry = true;
 337    }
 338   
 339  8040120 minute = testMinute;
 340  8040120 break;
 341    }
 342    }
 343   
 344  8040120 if (retry) {
 345  24 continue;
 346    }
 347    }
 348   
 349  16040168 break;
 350    }
 351   
 352    // OK, all done. Return the adjusted time value (adjusting this is faster than creating a new Calendar object)
 353  16040168 cal.set(Calendar.YEAR, year);
 354  16040168 cal.set(Calendar.MONTH, month - 1); // Calendar is 0-based for this field, and we are 1-based
 355  16040168 cal.set(Calendar.DAY_OF_MONTH, dayOfMonth);
 356  16040168 cal.set(Calendar.HOUR_OF_DAY, hour);
 357  16040168 cal.set(Calendar.MINUTE, minute);
 358  16040168 cal.set(Calendar.SECOND, 0);
 359  16040168 cal.set(Calendar.MILLISECOND, 0);
 360   
 361  16040168 return cal.getTime().getTime();
 362    }
 363   
 364    /**
 365    * Takes a cron expression as an input parameter, and extracts from it the
 366    * relevant minutes/hours/days/months that the expression matches.
 367    *
 368    * @param expression A valid cron expression.
 369    * @throws ParseException If the supplied expression could not be parsed.
 370    */
 371  8040328 private void parseExpression(String expression) throws ParseException {
 372  8040328 try {
 373    // Reset all the lookup data
 374  8040328 for (int i = 0; i < lookup.length; lookup[i++] = 0) {
 375  40201640 lookupMin[i] = Integer.MAX_VALUE;
 376  40201640 lookupMax[i] = -1;
 377    }
 378   
 379    // Create some character arrays to hold the extracted field values
 380  8040328 char[][] token = new char[NUMBER_OF_CRON_FIELDS][];
 381   
 382    // Extract the supplied expression into another character array
 383    // for speed
 384  8040328 int length = expression.length();
 385  8040328 char[] expr = new char[length];
 386  8040328 expression.getChars(0, length, expr, 0);
 387   
 388  8040328 int field = 0;
 389  8040328 int startIndex = 0;
 390  8040328 boolean inWhitespace = true;
 391   
 392    // Extract the various cron fields from the expression
 393  8040328 for (int i = 0; (i < length) && (field < NUMBER_OF_CRON_FIELDS);
 394    i++) {
 395  200524544 boolean haveChar = (expr[i] != ' ') && (expr[i] != '\t');
 396   
 397  200524544 if (haveChar) {
 398    // We have a text character of some sort
 399  168363220 if (inWhitespace) {
 400  40201616 startIndex = i; // Remember the start of this token
 401  40201616 inWhitespace = false;
 402    }
 403    }
 404   
 405  200524544 if (i == (length - 1)) { // Adjustment for when we reach the end of the expression
 406  8040324 i++;
 407    }
 408   
 409  200524544 if (!(haveChar || inWhitespace) || (i == length)) {
 410    // We've reached the end of a token. Copy it into a new char array
 411  40201616 token[field] = new char[i - startIndex];
 412  40201616 System.arraycopy(expr, startIndex, token[field], 0, i - startIndex);
 413  40201616 inWhitespace = true;
 414  40201616 field++;
 415    }
 416    }
 417   
 418  8040328 if (field < NUMBER_OF_CRON_FIELDS) {
 419  8 throw new ParseException("Unexpected end of expression while parsing \"" + expression + "\". Cron expressions require 5 separate fields.", length);
 420    }
 421   
 422    // OK, we've broken the string up into the 5 cron fields, now lets add
 423    // each field to their lookup table.
 424  8040320 for (field = 0; field < NUMBER_OF_CRON_FIELDS; field++) {
 425  40201456 startIndex = 0;
 426   
 427  40201456 boolean inDelimiter = true;
 428   
 429    // We add each comma-delimited element seperately.
 430  40201456 int elementLength = token[field].length;
 431   
 432  40201456 for (int i = 0; i < elementLength; i++) {
 433  168363052 boolean haveElement = token[field][i] != ',';
 434   
 435  168363052 if (haveElement) {
 436    // We have a character from an element in the token
 437  136362896 if (inDelimiter) {
 438  72201612 startIndex = i;
 439  72201612 inDelimiter = false;
 440    }
 441    }
 442   
 443  168363052