--- /dev/null
+/*
+ * Copyright 2014 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <vector>
+#include <stdexcept>
+#include <string>
+#include <unordered_map>
+
+#include "folly/Conv.h"
+#include "folly/dynamic.h"
+#include "folly/Format.h"
+#include "folly/json.h"
+
+// Add stateful Cron support for more robustness, see README for a design.
+
+namespace folly { namespace cron {
+
+/**
+ * A CrontabSelector is a wildcard for matching some periodic value (e.g.
+ * days of week, years, minutes, ...). This is a base class, so Cron itself
+ * uses a bunch of specialized descendants.
+ *
+ * The periodic values being matched are integers of varying signedness and
+ * bit-widths.
+ *
+ * CrontabSelector is a union type, representing either:
+ * - A list of one or more values to match. E.g. January & March.
+ * - A start, an end, and an interval. This range type does not wrap:
+ * starting from Tuesday with an interval of 6 is equivalent to only
+ * Tuesday.
+ *
+ * A selector knows its minimum and maximum permissible value. For example,
+ * a day-of-month is between 1 and 31, but real months may have fewer days,
+ * which is handled at a higher level -- the selector is meant to apply
+ * uniformly to all months.
+ *
+ * A selector also supports 3-character string-prefix aliases for the
+ * integer value. For example, "sun", "Sund", and "Sunday" would all map to
+ * 1, while "sAt" is 7. In the month type, "july" maps to 7, etc. Note
+ * that these strings are not localized -- specs are English-only, but this
+ * is a feature, since otherwise a Cron configuration might be ambiguous
+ * depending on the system locale. Also note that the day-of-week numbering
+ * is similarly unlocalized English, so the Russians who think Sunday == 7
+ * will have to cope.
+ *
+ * Selectors are specified using JSON. Here are some month selectors:
+ *
+ * 5 // The value 5, or May
+ * "Apr" // The value 4, or April
+ * ["Jun", "Jul", 12] // June, July, or December
+ * {"interval": 1} // Match any of the 12 months
+ * {"start": "Aug", "end": 11} // August through November, inclusive
+ * {"interval": 2, "end": "Jul"} // January, March, May, or July
+ *
+ * We do not implement the traditional Cron syntax because it's hard to read
+ * and verify, and implies the presence of some Cron misfeatures that we do
+ * not support. A reasonable patch adding such parser would be accepted,
+ * however.
+ */
+template<typename Num>
+class CrontabSelector {
+public:
+
+ CrontabSelector(const CrontabSelector&) = delete; // can neither copy
+ CrontabSelector& operator=(const CrontabSelector&) = delete; // nor assign
+ virtual ~CrontabSelector() {}
+
+ /**
+ * Initialize the selector from a JSON object (see the class docblock).
+ */
+ void loadDynamic(const folly::dynamic &d) {
+ if (initialized_) { // This restriction could be lifted if necessary.
+ throw std::runtime_error("loadDynamic cannot be called twice");
+ }
+ switch (d.type()) {
+ case folly::dynamic::Type::INT64:
+ case folly::dynamic::Type::STRING:
+ sorted_values_.emplace_back(parseValue(d));
+ break;
+ case folly::dynamic::Type::ARRAY:
+ for (const auto& val : d) {
+ sorted_values_.emplace_back(parseValue(val));
+ }
+ // If somebody specifies [] for a selector, we have to silently
+ // accept it, since PHP's JSON library can morph {} into [], and {}
+ // must mean "default selector accepting all values."
+ break;
+ case folly::dynamic::Type::OBJECT:
+ for (const auto& pair : d.items()) {
+ // Interval is first so that it doesn't accept strings like "jan"
+ if (pair.first == "interval") {
+ interval_ = pair.second.asInt();
+ if (interval_ < 1 || interval_ >= max_val_ - min_val_) {
+ throw std::runtime_error(folly::format(
+ "interval not in [1, {}]: {}", max_val_ - min_val_, interval_
+ ).str());
+ }
+ continue;
+ }
+ // For start & end, we are happy to accept string names
+ auto val = parseValue(pair.second);
+ if (pair.first == "start") {
+ start_ = val;
+ } else if (pair.first == "end") {
+ end_ = val;
+ } else {
+ throw std::runtime_error(folly::format(
+ "Unknown key: {}", pair.first
+ ).str());
+ }
+ }
+ // If we got an empty object, no problem -- this selector will
+ // follow the default of "match everything".
+ break;
+ default:
+ throw std::runtime_error(folly::format(
+ "Bad type for crontab selector: {}", d.typeName()
+ ).str());
+ }
+ std::sort(sorted_values_.begin(), sorted_values_.end());
+ initialized_ = true;
+ }
+
+ /**
+ * Returns the first t_match >= t such that t_match matches this selector.
+ * If no match is found, wraps around to the selector's first element, and
+ * sets the "carry" bool to true. Otherwise, that value is false.
+ *
+ * Note: no modular arithmetic happens here -- as soon as we exceed end_,
+ * we simply reset to start_. This is not the full story for
+ * day-of-month, so StandardCrontabItem has to do some extra work there.
+ * The simple "wrap to start" behavior is correct because with modular
+ * arithmetic a "week" selector starting on Tuesday with a stride of 6
+ * would accept any day of the week, which is far more surprising than
+ * only accepting Tuesday.
+ */
+ std::pair<Num, bool> findFirstMatch(Num t) const {
+ if (!initialized_) {
+ throw std::runtime_error("Selector not initialized");
+ }
+
+ if (!sorted_values_.empty()) {
+ // If this were stateful, we could remember where the previous item was,
+ // but as is, we incur the log(n) search time every time.
+ auto i =
+ std::lower_bound(sorted_values_.begin(), sorted_values_.end(), t);
+ if (i == sorted_values_.end()) { // Wrap to the start
+ return std::make_pair(*sorted_values_.begin(), true);
+ }
+ return std::make_pair(*i, false);
+ }
+
+ if (t < start_) {
+ return std::make_pair(start_, false);
+ }
+ int64_t next = t + (interval_ - (t - start_) % interval_) % interval_;
+ if (next > end_) {
+ return std::make_pair(start_, true);
+ }
+ return std::make_pair(next, false);
+ }
+
+ bool isInitialized() const { return initialized_; }
+
+ /**
+ * A compact string representation for unit tests or debugging, which sort
+ * of emulates standard cron syntax. This function is subject to change
+ * without notice -- send a patch with toDynamic() if you need to inspect
+ * the contents of a selector in production code. We will NOT fix your
+ * code if you are using this function. You have been warned.
+ */
+ std::string getPrintable() const {
+ std::string s;
+ for (const auto &v : sorted_values_) {
+ folly::toAppend(v, ',', &s);
+ }
+ if (start_ != min_val_ || end_ != max_val_ || interval_ != 1) {
+ if (!sorted_values_.empty()) {
+ s[s.size() - 1] = '/';
+ }
+ folly::toAppend(start_, '-', end_, ':', interval_, &s);
+ } else if (sorted_values_.empty()) {
+ folly::toAppend('*', &s);
+ } else {
+ s.pop_back();
+ }
+ return s;
+ }
+
+ Num getMin() const { return min_val_; }
+ Num getMax() const { return max_val_; }
+
+protected:
+ typedef std::unordered_map<std::string, Num> PrefixMap;
+
+ CrontabSelector(Num min_val, Num max_val)
+ : initialized_(false),
+ start_(min_val),
+ end_(max_val),
+ interval_(1),
+ min_val_(min_val),
+ max_val_(max_val) {}
+
+ /**
+ * Converts 3-letter string prefixes to numeric values, e.g. Jan=>1, Wed=>3
+ */
+ virtual const PrefixMap& getPrefixMap() const { return emptyPrefixMap_; }
+
+private:
+ Num parseValue(const folly::dynamic& d) {
+ Num res;
+ if (d.isInt()) {
+ res = d.asInt();
+ } else if (d.isString()) {
+ // TODO: This prefix-matching could be more robust... we don't even
+ // check if the prefix map is populated with 3-character strings.
+ auto s = d.asString().substr(0, 3).toStdString();
+ std::transform(s.begin(), s.end(), s.begin(), ::tolower);
+ auto prefix_map = getPrefixMap();
+ auto i = prefix_map.find(s);
+ if (i == prefix_map.end()) {
+ throw std::runtime_error(folly::format(
+ "Cannot convert prefix to int: {}", s
+ ).str());
+ }
+ res = i->second;
+ } else {
+ throw std::runtime_error(folly::format(
+ "Cannot parse {}", folly::toJson(d)
+ ).str());
+ }
+ if (res < min_val_ || res > max_val_) {
+ throw std::runtime_error(folly::format(
+ "Value {} out of range [{}, {}]", res, min_val_, max_val_
+ ).str());
+ }
+ return res;
+ }
+
+ bool initialized_;
+
+ std::vector<Num> sorted_values_;
+ // These three are unused when sorted_values_ is set
+ Num start_;
+ Num end_;
+ Num interval_;
+
+ // Default values for start & end, also used for range-checking.
+ const Num min_val_;
+ const Num max_val_;
+
+ // Should be static but it's too hard to do that with templates.
+ // TODO(agoder): Make this better.
+ const std::unordered_map<std::string, Num> emptyPrefixMap_;
+};
+
+}}
--- /dev/null
+/*
+ * Copyright 2014 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gtest/gtest.h>
+
+#include "folly/experimental/cron/CrontabSelector.h"
+#include "folly/json.h"
+
+using namespace folly::cron;
+using namespace folly;
+using namespace std;
+
+// Templates lead to poor error messages, so the preprocessor rules this land
+
+#define check_parse_impl(Selector, json, expected_printable) { \
+ Selector c; \
+ c.loadDynamic(parseJson(json)); \
+ EXPECT_EQ(expected_printable, c.getPrintable()); \
+}
+
+#define check_first_match_impl(Selector, Num, json, t, match, carry) { \
+ Num match_ = match; /* Make the input the right type */ \
+ Selector c; \
+ c.loadDynamic(parseJson(json)); \
+ EXPECT_EQ(make_pair(match_, carry), c.findFirstMatch(t)); \
+}
+
+#define check_parse(json, expected_printable) \
+ check_parse_impl(ClownCrontabSelector, json, expected_printable)
+
+#define check_first_match(json, t, match, carry) \
+ check_first_match_impl( \
+ ClownCrontabSelector, unsigned short, json, t, match, carry \
+ )
+
+/**
+ * There are 7 clowns in the world, numbered from 1 through 7, with the
+ * names listed below.
+ */
+class ClownCrontabSelector : public CrontabSelector<unsigned short> {
+public:
+ ClownCrontabSelector() : CrontabSelector(1, 7) {}
+protected:
+ virtual const PrefixMap& getPrefixMap() const { return clownToInt_; }
+private:
+ const static PrefixMap clownToInt_;
+};
+const ClownCrontabSelector::PrefixMap ClownCrontabSelector::clownToInt_{
+ {"sun", 1}, // Sunny
+ {"mon", 2}, // Monica
+ {"tue", 3}, // Tuelly
+ {"wed", 4}, // Wedder
+ {"thu", 5}, // Thurmond
+ {"fri", 6}, // Friedrich
+ {"sat", 7}, // Satay
+};
+
+TEST(TestCrontabSelector, CheckParseRanges) {
+ check_parse("{}", "*");
+ check_parse("{\"interval\": 3}", "1-7:3");
+ check_parse("{\"start\": 2}", "2-7:1");
+ check_parse("{\"start\": \"Sunny\"}", "*");
+ check_parse("{\"end\": \"Thu\"}", "1-5:1");
+ check_parse("{\"start\": \"Tuelly\", \"end\": \"Wed\"}", "3-4:1");
+ check_parse("{\"end\": \"Fri\", \"interval\": 2}", "1-6:2");
+}
+
+TEST(TestCrontabSelector, CheckParseValues) {
+ check_parse("5", "5");
+ check_parse("\"Thu\"", "5");
+ check_parse("[\"Sat\", 1, \"Fri\"]", "1,6,7");
+}
+
+TEST(TestCrontabSelector, CheckMatchValues) {
+ for (int64_t i = 0; i < 10; ++i) { // A single value never changes
+ check_first_match("5", i, 5, i > 5);
+ }
+
+ // Now check a list of values
+ check_first_match("[2,4,5]", 0, 2, false);
+ check_first_match("[2,4,5]", 1, 2, false);
+ check_first_match("[2,4,5]", 2, 2, false);
+ check_first_match("[2,4,5]", 3, 4, false);
+ check_first_match("[2,4,5]", 4, 4, false);
+ check_first_match("[2,4,5]", 5, 5, false);
+ check_first_match("[2,4,5]", 6, 2, true);
+ check_first_match("[2,4,5]", 7, 2, true);
+}
+
+TEST(TestCrontabSelector, CheckMatchDefaultRange) {
+ check_first_match("{}", 0, 1, false);
+ check_first_match("[]", 1, 1, false);
+ check_first_match("[]", 6, 6, false);
+ check_first_match("{}", 7, 7, false);
+ check_first_match("{}", 8, 1, true);
+ check_first_match("[]", 10, 1, true);
+}
+
+TEST(TestCrontabSelector, CheckMatchNontrivialRange) {
+ string range = "{\"start\": 3, \"end\": 7, \"interval\": 2}";
+ check_first_match(range, 1, 3, false);
+ check_first_match(range, 2, 3, false);
+ check_first_match(range, 3, 3, false);
+ check_first_match(range, 4, 5, false);
+ check_first_match(range, 5, 5, false);
+ check_first_match(range, 6, 7, false);
+ check_first_match(range, 7, 7, false);
+ check_first_match(range, 8, 3, true);
+}
+
+TEST(TestCrontabSelector, CheckInit) {
+ ClownCrontabSelector s;
+
+ EXPECT_THROW(s.findFirstMatch(5), runtime_error); // Not initialized
+
+ // Initialized and functional
+ s.loadDynamic(dynamic::object());
+ EXPECT_EQ(make_pair((unsigned short)5, false), s.findFirstMatch(5));
+
+ // Cannot double-initialize
+ EXPECT_THROW(s.loadDynamic(dynamic::object()), runtime_error);
+}
+
+TEST(TestCrontabSelector, CheckParseErrors) {
+ // Out-of-range intervals
+ EXPECT_THROW(check_parse("{\"interval\": 0}", ""), runtime_error);
+ EXPECT_THROW(check_parse("{\"interval\": -1}", ""), runtime_error);
+ EXPECT_THROW(check_parse("{\"interval\": 7}", ""), runtime_error);
+
+ // Out-of-range start or end
+ EXPECT_THROW(check_parse("{\"start\": 0}", ""), runtime_error);
+ EXPECT_THROW(check_parse("{\"end\": 8}", ""), runtime_error);
+
+ // Problematic JSON inputs
+ EXPECT_THROW(check_parse("{\"bad_key\": 3}", ""), runtime_error);
+ EXPECT_THROW(check_parse("0.1", ""), runtime_error); // no floats
+
+ // Invalid values
+ EXPECT_THROW(check_parse("\"Chicken\"", ""), runtime_error);
+ EXPECT_THROW(check_parse("\"Th\"", ""), runtime_error); // Need >= 3 chars
+ EXPECT_THROW(check_parse("\"S\"", ""), runtime_error);
+ EXPECT_THROW(check_parse("{\"start\": 0.3}", ""), runtime_error); // float
+}
projects / folly.git / commitdiff