001/**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.activemq.broker.scheduler;
018
019import java.util.ArrayList;
020import java.util.Calendar;
021import java.util.Collections;
022import java.util.List;
023import java.util.StringTokenizer;
024import javax.jms.MessageFormatException;
025
026public class CronParser {
027
028    private static final int NUMBER_TOKENS = 5;
029    private static final int MINUTES = 0;
030    private static final int HOURS = 1;
031    private static final int DAY_OF_MONTH = 2;
032    private static final int MONTH = 3;
033    private static final int DAY_OF_WEEK = 4;
034
035    public static long getNextScheduledTime(final String cronEntry, long currentTime) throws MessageFormatException {
036
037        long result = 0;
038
039        if (cronEntry == null || cronEntry.length() == 0) {
040            return result;
041        }
042
043        // Handle the once per minute case "* * * * *"
044        // starting the next event at the top of the minute.
045        if (cronEntry.startsWith("* * * * *")) {
046            result = currentTime + 60 * 1000;
047            result = result / 1000 * 1000;
048            return result;
049        }
050
051        List<String> list = tokenize(cronEntry);
052        List<CronEntry> entries = buildCronEntries(list);
053        Calendar working = Calendar.getInstance();
054        working.setTimeInMillis(currentTime);
055        working.set(Calendar.SECOND, 0);
056
057        CronEntry minutes = entries.get(MINUTES);
058        CronEntry hours = entries.get(HOURS);
059        CronEntry dayOfMonth = entries.get(DAY_OF_MONTH);
060        CronEntry month = entries.get(MONTH);
061        CronEntry dayOfWeek = entries.get(DAY_OF_WEEK);
062
063        // Start at the top of the next minute, cron is only guaranteed to be
064        // run on the minute.
065        int timeToNextMinute = 60 - working.get(Calendar.SECOND);
066        working.add(Calendar.SECOND, timeToNextMinute);
067
068        // If its already to late in the day this will roll us over to tomorrow
069        // so we'll need to check again when done updating month and day.
070        int currentMinutes = working.get(Calendar.MINUTE);
071        if (!isCurrent(minutes, currentMinutes)) {
072            int nextMinutes = getNext(minutes, currentMinutes);
073            working.add(Calendar.MINUTE, nextMinutes);
074        }
075
076        int currentHours = working.get(Calendar.HOUR_OF_DAY);
077        if (!isCurrent(hours, currentHours)) {
078            int nextHour = getNext(hours, currentHours);
079            working.add(Calendar.HOUR_OF_DAY, nextHour);
080        }
081
082        // We can roll into the next month here which might violate the cron setting
083        // rules so we check once then recheck again after applying the month settings.
084        doUpdateCurrentDay(working, dayOfMonth, dayOfWeek);
085
086        // Start by checking if we are in the right month, if not then calculations
087        // need to start from the beginning of the month to ensure that we don't end
088        // up on the wrong day.  (Can happen when DAY_OF_WEEK is set and current time
089        // is ahead of the day of the week to execute on).
090        doUpdateCurrentMonth(working, month);
091
092        // Now Check day of week and day of month together since they can be specified
093        // together in one entry, if both "day of month" and "day of week" are restricted
094        // (not "*"), then either the "day of month" field (3) or the "day of week" field
095        // (5) must match the current day or the Calenday must be advanced.
096        doUpdateCurrentDay(working, dayOfMonth, dayOfWeek);
097
098        // Now we can chose the correct hour and minute of the day in question.
099
100        currentHours = working.get(Calendar.HOUR_OF_DAY);
101        if (!isCurrent(hours, currentHours)) {
102            int nextHour = getNext(hours, currentHours);
103            working.add(Calendar.HOUR_OF_DAY, nextHour);
104        }
105
106        currentMinutes = working.get(Calendar.MINUTE);
107        if (!isCurrent(minutes, currentMinutes)) {
108            int nextMinutes = getNext(minutes, currentMinutes);
109            working.add(Calendar.MINUTE, nextMinutes);
110        }
111
112        result = working.getTimeInMillis();
113
114        if (result <= currentTime) {
115            throw new ArithmeticException("Unable to compute next scheduled exection time.");
116        }
117
118        return result;
119    }
120
121    protected static long doUpdateCurrentMonth(Calendar working, CronEntry month) throws MessageFormatException {
122
123        int currentMonth = working.get(Calendar.MONTH) + 1;
124        if (!isCurrent(month, currentMonth)) {
125            int nextMonth = getNext(month, currentMonth);
126            working.add(Calendar.MONTH, nextMonth);
127
128            // Reset to start of month.
129            resetToStartOfDay(working, 1);
130
131            return working.getTimeInMillis();
132        }
133
134        return 0L;
135    }
136
137    protected static long doUpdateCurrentDay(Calendar working, CronEntry dayOfMonth, CronEntry dayOfWeek) throws MessageFormatException {
138
139        int currentDayOfWeek = working.get(Calendar.DAY_OF_WEEK) - 1;
140        int currentDayOfMonth = working.get(Calendar.DAY_OF_MONTH);
141
142        // Simplest case, both are unrestricted or both match today otherwise
143        // result must be the closer of the two if both are set, or the next
144        // match to the one that is.
145        if (!isCurrent(dayOfWeek, currentDayOfWeek) ||
146            !isCurrent(dayOfMonth, currentDayOfMonth) ) {
147
148            int nextWeekDay = Integer.MAX_VALUE;
149            int nextCalendarDay = Integer.MAX_VALUE;
150
151            if (!isCurrent(dayOfWeek, currentDayOfWeek)) {
152                nextWeekDay = getNext(dayOfWeek, currentDayOfWeek);
153            }
154
155            if (!isCurrent(dayOfMonth, currentDayOfMonth)) {
156                nextCalendarDay = getNext(dayOfMonth, currentDayOfMonth);
157            }
158
159            if( nextWeekDay < nextCalendarDay ) {
160                working.add(Calendar.DAY_OF_WEEK, nextWeekDay);
161            } else {
162                working.add(Calendar.DAY_OF_MONTH, nextCalendarDay);
163            }
164
165            // Since the day changed, we restart the clock at the start of the day
166            // so that the next time will either be at 12am + value of hours and
167            // minutes pattern.
168            resetToStartOfDay(working, working.get(Calendar.DAY_OF_MONTH));
169
170            return working.getTimeInMillis();
171        }
172
173        return 0L;
174    }
175
176    public static void validate(final String cronEntry) throws MessageFormatException {
177        List<String> list = tokenize(cronEntry);
178        List<CronEntry> entries = buildCronEntries(list);
179        for (CronEntry e : entries) {
180            validate(e);
181        }
182    }
183
184    static void validate(final CronEntry entry) throws MessageFormatException {
185
186        List<Integer> list = entry.currentWhen;
187        if (list.isEmpty() || list.get(0).intValue() < entry.start || list.get(list.size() - 1).intValue() > entry.end) {
188            throw new MessageFormatException("Invalid token: " + entry);
189        }
190    }
191
192    static int getNext(final CronEntry entry, final int current) throws MessageFormatException {
193        int result = 0;
194
195        if (entry.currentWhen == null) {
196            entry.currentWhen = calculateValues(entry);
197        }
198
199        List<Integer> list = entry.currentWhen;
200        int next = -1;
201        for (Integer i : list) {
202            if (i.intValue() > current) {
203                next = i.intValue();
204                break;
205            }
206        }
207        if (next != -1) {
208            result = next - current;
209        } else {
210            int first = list.get(0).intValue();
211            result = entry.end + first - entry.start - current;
212
213            // Account for difference of one vs zero based indices.
214            if (entry.name.equals("DayOfWeek") || entry.name.equals("Month")) {
215                result++;
216            }
217        }
218
219        return result;
220    }
221
222    static boolean isCurrent(final CronEntry entry, final int current) throws MessageFormatException {
223        boolean result = entry.currentWhen.contains(new Integer(current));
224        return result;
225    }
226
227    protected static void resetToStartOfDay(Calendar target, int day) {
228        target.set(Calendar.DAY_OF_MONTH, day);
229        target.set(Calendar.HOUR_OF_DAY, 0);
230        target.set(Calendar.MINUTE, 0);
231        target.set(Calendar.SECOND, 0);
232    }
233
234    static List<String> tokenize(String cron) throws IllegalArgumentException {
235        StringTokenizer tokenize = new StringTokenizer(cron);
236        List<String> result = new ArrayList<String>();
237        while (tokenize.hasMoreTokens()) {
238            result.add(tokenize.nextToken());
239        }
240        if (result.size() != NUMBER_TOKENS) {
241            throw new IllegalArgumentException("Not a valid cron entry - wrong number of tokens(" + result.size()
242                    + "): " + cron);
243        }
244        return result;
245    }
246
247    protected static List<Integer> calculateValues(final CronEntry entry) {
248        List<Integer> result = new ArrayList<Integer>();
249        if (isAll(entry.token)) {
250            for (int i = entry.start; i <= entry.end; i++) {
251                result.add(i);
252            }
253        } else if (isAStep(entry.token)) {
254            int denominator = getDenominator(entry.token);
255            String numerator = getNumerator(entry.token);
256            CronEntry ce = new CronEntry(entry.name, numerator, entry.start, entry.end);
257            List<Integer> list = calculateValues(ce);
258            for (Integer i : list) {
259                if (i.intValue() % denominator == 0) {
260                    result.add(i);
261                }
262            }
263        } else if (isAList(entry.token)) {
264            StringTokenizer tokenizer = new StringTokenizer(entry.token, ",");
265            while (tokenizer.hasMoreTokens()) {
266                String str = tokenizer.nextToken();
267                CronEntry ce = new CronEntry(entry.name, str, entry.start, entry.end);
268                List<Integer> list = calculateValues(ce);
269                result.addAll(list);
270            }
271        } else if (isARange(entry.token)) {
272            int index = entry.token.indexOf('-');
273            int first = Integer.parseInt(entry.token.substring(0, index));
274            int last = Integer.parseInt(entry.token.substring(index + 1));
275            for (int i = first; i <= last; i++) {
276                result.add(i);
277            }
278        } else {
279            int value = Integer.parseInt(entry.token);
280            result.add(value);
281        }
282        Collections.sort(result);
283        return result;
284    }
285
286    protected static boolean isARange(String token) {
287        return token != null && token.indexOf('-') >= 0;
288    }
289
290    protected static boolean isAStep(String token) {
291        return token != null && token.indexOf('/') >= 0;
292    }
293
294    protected static boolean isAList(String token) {
295        return token != null && token.indexOf(',') >= 0;
296    }
297
298    protected static boolean isAll(String token) {
299        return token != null && token.length() == 1 && (token.charAt(0) == '*' || token.charAt(0) == '?');
300    }
301
302    protected static int getDenominator(final String token) {
303        int result = 0;
304        int index = token.indexOf('/');
305        String str = token.substring(index + 1);
306        result = Integer.parseInt(str);
307        return result;
308    }
309
310    protected static String getNumerator(final String token) {
311        int index = token.indexOf('/');
312        String str = token.substring(0, index);
313        return str;
314    }
315
316    static List<CronEntry> buildCronEntries(List<String> tokens) {
317
318        List<CronEntry> result = new ArrayList<CronEntry>();
319
320        CronEntry minutes = new CronEntry("Minutes", tokens.get(MINUTES), 0, 60);
321        minutes.currentWhen = calculateValues(minutes);
322        result.add(minutes);
323        CronEntry hours = new CronEntry("Hours", tokens.get(HOURS), 0, 24);
324        hours.currentWhen = calculateValues(hours);
325        result.add(hours);
326        CronEntry dayOfMonth = new CronEntry("DayOfMonth", tokens.get(DAY_OF_MONTH), 1, 31);
327        dayOfMonth.currentWhen = calculateValues(dayOfMonth);
328        result.add(dayOfMonth);
329        CronEntry month = new CronEntry("Month", tokens.get(MONTH), 1, 12);
330        month.currentWhen = calculateValues(month);
331        result.add(month);
332        CronEntry dayOfWeek = new CronEntry("DayOfWeek", tokens.get(DAY_OF_WEEK), 0, 6);
333        dayOfWeek.currentWhen = calculateValues(dayOfWeek);
334        result.add(dayOfWeek);
335
336        return result;
337    }
338
339    static class CronEntry {
340
341        final String name;
342        final String token;
343        final int start;
344        final int end;
345
346        List<Integer> currentWhen;
347
348        CronEntry(String name, String token, int start, int end) {
349            this.name = name;
350            this.token = token;
351            this.start = start;
352            this.end = end;
353        }
354
355        @Override
356        public String toString() {
357            return this.name + ":" + token;
358        }
359    }
360
361}