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