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     */
017    package org.apache.activemq.broker.scheduler;
018    
019    import java.util.ArrayList;
020    import java.util.Calendar;
021    import java.util.Collections;
022    import java.util.List;
023    import java.util.StringTokenizer;
024    import javax.jms.MessageFormatException;
025    
026    public 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    }