folly/experimental/cron/CrontabSelector.h

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #pragma once
  18
  19 #include <algorithm>
  20 #include <vector>
  21 #include <stdexcept>
  22 #include <string>
  23 #include <unordered_map>
  24
  25 #include "folly/Conv.h"
  26 #include "folly/dynamic.h"
  27 #include "folly/Format.h"
  28 #include "folly/json.h"
  29
  30 // Add stateful Cron support for more robustness, see README for a design.
  31
  32 namespace folly { namespace cron {
  33
  34 /**
  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.
  38  *
  39  * The periodic values being matched are integers of varying signedness and
  40  * bit-widths.
  41  *
  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
  46  *     Tuesday.
  47  *
  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.
  52  *
  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
  60  * will have to cope.
  61  *
  62  * Selectors are specified using JSON. Here are some month selectors:
  63  *
  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
  70  *
  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,
  74  * however.
  75  */
  76 template<typename Num>
  77 class CrontabSelector {
  78 public:
  79
  80   CrontabSelector(const CrontabSelector&) = delete;  // can neither copy
  81   CrontabSelector& operator=(const CrontabSelector&) = delete;  // nor assign
  82   virtual ~CrontabSelector() {}
  83
  84   /**
  85    * Initialize the selector from a JSON object (see the class docblock).
  86    */
  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");
  90     }
  91     switch (d.type()) {
  92       case folly::dynamic::Type::INT64:
  93       case folly::dynamic::Type::STRING:
  94         sorted_values_.emplace_back(parseValue(d));
  95         break;
  96       case folly::dynamic::Type::ARRAY:
  97         for (const auto& val : d) {
  98           sorted_values_.emplace_back(parseValue(val));
  99         }
 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."
 103         break;
 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_
 112               ).str());
 113             }
 114             continue;
 115           }
 116           // For start & end, we are happy to accept string names
 117           auto val = parseValue(pair.second);
 118           if (pair.first == "start") {
 119             start_ = val;
 120           } else if (pair.first == "end") {
 121             end_ = val;
 122           } else {
 123             throw std::runtime_error(folly::format(
 124               "Unknown key: {}", pair.first
 125             ).str());
 126           }
 127         }
 128         // If we got an empty object, no problem -- this selector will
 129         // follow the default of "match everything".
 130         break;
 131       default:
 132         throw std::runtime_error(folly::format(
 133           "Bad type for crontab selector: {}", d.typeName()
 134         ).str());
 135     }
 136     std::sort(sorted_values_.begin(), sorted_values_.end());
 137     initialized_ = true;
 138   }
 139
 140   /**
 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.
 144    *
 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.
 152    */
 153   std::pair<Num, bool> findFirstMatch(Num t) const {
 154     if (!initialized_) {
 155       throw std::runtime_error("Selector not initialized");
 156     }
 157
 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.
 161       auto i =
 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);
 165       }
 166       return std::make_pair(*i, false);
 167     }
 168
 169     if (t < start_) {
 170       return std::make_pair(start_, false);
 171     }
 172     int64_t next = t + (interval_ - (t - start_) % interval_) % interval_;
 173     if (next > end_) {
 174       return std::make_pair(start_, true);
 175     }
 176     return std::make_pair(next, false);
 177   }
 178
 179   bool isInitialized() const { return initialized_; }
 180
 181   /**
 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.
 187    */
 188   std::string getPrintable() const {
 189     std::string s;
 190     for (const auto &v : sorted_values_) {
 191       folly::toAppend(v, ',', &s);
 192     }
 193     if (start_ != min_val_ || end_ != max_val_ || interval_ != 1) {
 194       if (!sorted_values_.empty()) {
 195         s[s.size() - 1] = '/';
 196       }
 197       folly::toAppend(start_, '-', end_, ':', interval_, &s);
 198     } else if (sorted_values_.empty()) {
 199       folly::toAppend('*', &s);
 200     } else {
 201       s.pop_back();
 202     }
 203     return s;
 204   }
 205
 206   Num getMin() const { return min_val_; }
 207   Num getMax() const { return max_val_; }
 208
 209 protected:
 210   typedef std::unordered_map<std::string, Num> PrefixMap;
 211
 212   CrontabSelector(Num min_val, Num max_val)
 213     : initialized_(false),
 214       start_(min_val),
 215       end_(max_val),
 216       interval_(1),
 217       min_val_(min_val),
 218       max_val_(max_val) {}
 219
 220   /**
 221    * Converts 3-letter string prefixes to numeric values, e.g. Jan=>1, Wed=>3
 222    */
 223   virtual const PrefixMap& getPrefixMap() const { return emptyPrefixMap_; }
 224
 225 private:
 226   Num parseValue(const folly::dynamic& d) {
 227     Num res;
 228     if (d.isInt()) {
 229       res = d.asInt();
 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
 240         ).str());
 241       }
 242       res = i->second;
 243     } else {
 244       throw std::runtime_error(folly::format(
 245         "Cannot parse {}", folly::toJson(d)
 246       ).str());
 247     }
 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_
 251       ).str());
 252     }
 253     return res;
 254   }
 255
 256   bool initialized_;
 257
 258   std::vector<Num> sorted_values_;
 259   // These three are unused when sorted_values_ is set
 260   Num start_;
 261   Num end_;
 262   Num interval_;
 263
 264   // Default values for start & end, also used for range-checking.
 265   const Num min_val_;
 266   const Num max_val_;
 267
 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_;
 271 };
 272
 273 }}