2 * Copyright 2014 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
23 #include <unordered_map>
25 #include "folly/Conv.h"
26 #include "folly/dynamic.h"
27 #include "folly/Format.h"
28 #include "folly/json.h"
30 // Add stateful Cron support for more robustness, see README for a design.
32 namespace folly { namespace cron {
35 * A CrontabSelector is a wildcard for matching some periodic value (e.g.
36 * days of week, years, minutes, ...). This is a base class, so Cron itself
37 * uses a bunch of specialized descendants.
39 * The periodic values being matched are integers of varying signedness and
42 * CrontabSelector is a union type, representing either:
43 * - A list of one or more values to match. E.g. January & March.
44 * - A start, an end, and an interval. This range type does not wrap:
45 * starting from Tuesday with an interval of 6 is equivalent to only
48 * A selector knows its minimum and maximum permissible value. For example,
49 * a day-of-month is between 1 and 31, but real months may have fewer days,
50 * which is handled at a higher level -- the selector is meant to apply
51 * uniformly to all months.
53 * A selector also supports 3-character string-prefix aliases for the
54 * integer value. For example, "sun", "Sund", and "Sunday" would all map to
55 * 1, while "sAt" is 7. In the month type, "july" maps to 7, etc. Note
56 * that these strings are not localized -- specs are English-only, but this
57 * is a feature, since otherwise a Cron configuration might be ambiguous
58 * depending on the system locale. Also note that the day-of-week numbering
59 * is similarly unlocalized English, so the Russians who think Sunday == 7
62 * Selectors are specified using JSON. Here are some month selectors:
64 * 5 // The value 5, or May
65 * "Apr" // The value 4, or April
66 * ["Jun", "Jul", 12] // June, July, or December
67 * {"interval": 1} // Match any of the 12 months
68 * {"start": "Aug", "end": 11} // August through November, inclusive
69 * {"interval": 2, "end": "Jul"} // January, March, May, or July
71 * We do not implement the traditional Cron syntax because it's hard to read
72 * and verify, and implies the presence of some Cron misfeatures that we do
73 * not support. A reasonable patch adding such parser would be accepted,
76 template<typename Num>
77 class CrontabSelector {
80 CrontabSelector(const CrontabSelector&) = delete; // can neither copy
81 CrontabSelector& operator=(const CrontabSelector&) = delete; // nor assign
82 virtual ~CrontabSelector() {}
85 * Initialize the selector from a JSON object (see the class docblock).
87 void loadDynamic(const folly::dynamic &d) {
88 if (initialized_) { // This restriction could be lifted if necessary.
89 throw std::runtime_error("loadDynamic cannot be called twice");
92 case folly::dynamic::Type::INT64:
93 case folly::dynamic::Type::STRING:
94 sorted_values_.emplace_back(parseValue(d));
96 case folly::dynamic::Type::ARRAY:
97 for (const auto& val : d) {
98 sorted_values_.emplace_back(parseValue(val));
100 // If somebody specifies [] for a selector, we have to silently
101 // accept it, since PHP's JSON library can morph {} into [], and {}
102 // must mean "default selector accepting all values."
104 case folly::dynamic::Type::OBJECT:
105 for (const auto& pair : d.items()) {
106 // Interval is first so that it doesn't accept strings like "jan"
107 if (pair.first == "interval") {
108 interval_ = pair.second.asInt();
109 if (interval_ < 1 || interval_ >= max_val_ - min_val_) {
110 throw std::runtime_error(folly::format(
111 "interval not in [1, {}]: {}", max_val_ - min_val_, interval_
116 // For start & end, we are happy to accept string names
117 auto val = parseValue(pair.second);
118 if (pair.first == "start") {
120 } else if (pair.first == "end") {
123 throw std::runtime_error(folly::format(
124 "Unknown key: {}", pair.first
128 // If we got an empty object, no problem -- this selector will
129 // follow the default of "match everything".
132 throw std::runtime_error(folly::format(
133 "Bad type for crontab selector: {}", d.typeName()
136 std::sort(sorted_values_.begin(), sorted_values_.end());
141 * Returns the first t_match >= t such that t_match matches this selector.
142 * If no match is found, wraps around to the selector's first element, and
143 * sets the "carry" bool to true. Otherwise, that value is false.
145 * Note: no modular arithmetic happens here -- as soon as we exceed end_,
146 * we simply reset to start_. This is not the full story for
147 * day-of-month, so StandardCrontabItem has to do some extra work there.
148 * The simple "wrap to start" behavior is correct because with modular
149 * arithmetic a "week" selector starting on Tuesday with a stride of 6
150 * would accept any day of the week, which is far more surprising than
151 * only accepting Tuesday.
153 std::pair<Num, bool> findFirstMatch(Num t) const {
155 throw std::runtime_error("Selector not initialized");
158 if (!sorted_values_.empty()) {
159 // If this were stateful, we could remember where the previous item was,
160 // but as is, we incur the log(n) search time every time.
162 std::lower_bound(sorted_values_.begin(), sorted_values_.end(), t);
163 if (i == sorted_values_.end()) { // Wrap to the start
164 return std::make_pair(*sorted_values_.begin(), true);
166 return std::make_pair(*i, false);
170 return std::make_pair(start_, false);
172 int64_t next = t + (interval_ - (t - start_) % interval_) % interval_;
174 return std::make_pair(start_, true);
176 return std::make_pair(next, false);
179 bool isInitialized() const { return initialized_; }
182 * A compact string representation for unit tests or debugging, which sort
183 * of emulates standard cron syntax. This function is subject to change
184 * without notice -- send a patch with toDynamic() if you need to inspect
185 * the contents of a selector in production code. We will NOT fix your
186 * code if you are using this function. You have been warned.
188 std::string getPrintable() const {
190 for (const auto &v : sorted_values_) {
191 folly::toAppend(v, ',', &s);
193 if (start_ != min_val_ || end_ != max_val_ || interval_ != 1) {
194 if (!sorted_values_.empty()) {
195 s[s.size() - 1] = '/';
197 folly::toAppend(start_, '-', end_, ':', interval_, &s);
198 } else if (sorted_values_.empty()) {
199 folly::toAppend('*', &s);
206 Num getMin() const { return min_val_; }
207 Num getMax() const { return max_val_; }
210 typedef std::unordered_map<std::string, Num> PrefixMap;
212 CrontabSelector(Num min_val, Num max_val)
213 : initialized_(false),
221 * Converts 3-letter string prefixes to numeric values, e.g. Jan=>1, Wed=>3
223 virtual const PrefixMap& getPrefixMap() const { return emptyPrefixMap_; }
226 Num parseValue(const folly::dynamic& d) {
230 } else if (d.isString()) {
231 // TODO: This prefix-matching could be more robust... we don't even
232 // check if the prefix map is populated with 3-character strings.
233 auto s = d.asString().substr(0, 3).toStdString();
234 std::transform(s.begin(), s.end(), s.begin(), ::tolower);
235 auto prefix_map = getPrefixMap();
236 auto i = prefix_map.find(s);
237 if (i == prefix_map.end()) {
238 throw std::runtime_error(folly::format(
239 "Cannot convert prefix to int: {}", s
244 throw std::runtime_error(folly::format(
245 "Cannot parse {}", folly::toJson(d)
248 if (res < min_val_ || res > max_val_) {
249 throw std::runtime_error(folly::format(
250 "Value {} out of range [{}, {}]", res, min_val_, max_val_
258 std::vector<Num> sorted_values_;
259 // These three are unused when sorted_values_ is set
264 // Default values for start & end, also used for range-checking.
268 // Should be static but it's too hard to do that with templates.
269 // TODO(agoder): Make this better.
270 const std::unordered_map<std::string, Num> emptyPrefixMap_;