Use CRON to set the schedule of queues export

# Description

Currently the interval of queues export can only be set as "Every N units". This sometimes does not work well as it always starts the count from the time `0` (January 1st, 1970). It means that, for instance, if the customer wants to set an export to "Every week", it will happen every Thursday.

This PR fixes the problem by providing a CRON way to set the schedule which is proven to be very flexible and meeting (almost) any requirement the user may have.

* Changelog entry
Type: feature
Component: queue-agent

Support CRON schedules for queue exports.

---

Pull Request resolved: https://github.com/ytsaurus/ytsaurus/pull/1239

Co-authored-by: apachee <apachee@yandex-team.com>
Co-authored-by: apachee <apachee@yandex-team.com>
Co-authored-by: apachee <apachee@yandex-team.com>
Co-authored-by: apachee <apachee@yandex-team.com>
Co-authored-by: apachee <apachee@yandex-team.com>
commit_hash:6a536f5edc17b3ad8d2243d55d876994141d38b0

1 files changed, 1199 insertions, 0 deletions

diff --git a/library/cpp/cron_expression/cron_expression.cpp b/library/cpp/cron_expression/cron_expression.cpp
new file mode 100644
index 00000000000..55b64ee6d24
--- /dev/null
+++ b/library/cpp/cron_expression/cron_expression.cpp
@@ -0,0 +1,1199 @@
+#include "cron_expression.h"
+
+#include <util/generic/bitmap.h>
+#include <util/string/ascii.h>
+#include <util/string/join.h>
+#include <util/string/split.h>
+
+class TCronExpression::TImpl {
+private:
+    static constexpr uint32_t CRON_MAX_SECONDS = 60;
+    static constexpr uint32_t CRON_MAX_MINUTES = 60;
+    static constexpr uint32_t CRON_MAX_HOURS = 24;
+    static constexpr uint32_t CRON_MAX_DAYS_OF_MONTH = 31;
+    static constexpr uint32_t CRON_MAX_DAYS_OF_WEEK = 7;
+    static constexpr uint32_t CRON_MAX_MONTHS = 12;
+    static constexpr uint32_t CRON_MIN_YEARS = 1970;
+    static constexpr uint32_t CRON_MAX_YEARS = 2200;
+    static constexpr uint32_t CRON_MAX_YEARS_DIFF = 4;
+
+    static constexpr uint32_t WEEK_DAYS = 7;
+    static constexpr uint32_t YEARS_GAP_LENGTH = 231;
+
+    enum class ECronField {
+        CF_SECOND,
+        CF_MINUTE,
+        CF_HOUR_OF_DAY,
+        CF_DAY_OF_WEEK,
+        CF_DAY_OF_MONTH,
+        CF_MONTH,
+        CF_YEAR,
+        CF_NEXT
+    };
+
+    enum class ETokenType {
+        TT_ASTERISK,
+        TT_QUESTION,
+        TT_NUMBER,
+        TT_COMMA,
+        TT_SLASH,
+        TT_L,
+        TT_W,
+        TT_HASH,
+        TT_MINUS,
+        TT_WS,
+        TT_EOF,
+        TT_INVALID
+    };
+
+    static constexpr std::array<TStringBuf, 7> DAYS_ARR = {"SUN"sv, "MON"sv, "TUE"sv, "WED"sv, "THU"sv, "FRI"sv, "SAT"sv};
+    static constexpr std::array<TStringBuf, 12> CF_MONTHS_ARR = {"JAN"sv, "FEB"sv, "MAR"sv, "APR"sv, "MAY"sv, "JUN"sv, "JUL"sv, "AUG"sv, "SEP"sv, "OCT"sv, "NOV"sv, "DEC"sv};
+
+    static constexpr TStringBuf ErrorWS = "Fields - expected whitespace separator"sv;
+    static constexpr TStringBuf ErrorOutOfRange = "Idx out of range"sv;
+    static constexpr TStringBuf ErrorUnknownField = "Unknown field"sv;
+    static constexpr TStringBuf ErrorDateNotExists = "Requested date does not exist"sv;
+
+    class TCronExpr {
+    private:
+        TBitMap<60, uint8_t> Seconds;
+        TBitMap<60, uint8_t> Minutes;
+        TBitMap<24, uint8_t> Hours;
+
+        // Sunday can be represented both as 0 and 7
+        TBitMap<8, uint8_t> DaysOfWeek;
+        TBitMap<31, uint8_t> DaysOfMonth;
+        TBitMap<12, uint8_t> Months;
+        int8_t DayInMonth = 0;
+
+        // 0 last day of the month
+        // 1 last weekday of the month
+        // 2 closest weekday to day in month
+        uint8_t Flags = 0;
+        TBitMap<YEARS_GAP_LENGTH, uint8_t> Years;
+
+    private:
+
+        template <size_t N>
+        static TMaybe<uint32_t> NextSetBit(const TBitMap<N, uint8_t>& bits, uint32_t max, uint32_t fromIndex, uint32_t offset) {
+            if (fromIndex < offset || max < offset) {
+                ythrow yexception() << ErrorOutOfRange;
+            }
+            fromIndex -= offset;
+            max -= offset;
+            if (bits.Get(fromIndex)) {
+                return fromIndex + offset;
+            }
+            uint8_t nextBit = bits.NextNonZeroBit(fromIndex);
+            if (nextBit < max) {
+                return nextBit + offset;
+            }
+            return Nothing();
+        }
+
+        template <size_t N>
+        static TMaybe<uint32_t> PrevSetBit(const TBitMap<N, uint8_t>& bits, uint32_t fromIndex, uint32_t toIndex, uint32_t offset) {
+            if (fromIndex < offset || toIndex < offset) {
+                ythrow yexception() << ErrorOutOfRange;
+            }
+            fromIndex -= offset;
+            toIndex -= offset;
+            for (; fromIndex + 1 > toIndex; --fromIndex) {
+                if (bits.Get(fromIndex)) {
+                    return fromIndex + offset;
+                }
+                if (fromIndex == 0) {
+                    return Nothing();
+                }
+            }
+            return Nothing();
+        }
+
+    public:
+        void SetBit(ECronField field, uint32_t idx) {
+            switch(field) {
+                case ECronField::CF_SECOND: {
+                    Seconds.Set(idx);
+                    break;
+                }
+                case ECronField::CF_MINUTE: {
+                    Minutes.Set(idx);
+                    break;
+                }
+                case ECronField::CF_HOUR_OF_DAY: {
+                    Hours.Set(idx);
+                    break;
+                }
+                case ECronField::CF_DAY_OF_WEEK: {
+                    DaysOfWeek.Set(idx);
+                    break;
+                }
+                case ECronField::CF_DAY_OF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    DaysOfMonth.Set(idx - 1);
+                    break;
+                }
+                case ECronField::CF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    Months.Set(idx - 1);
+                    break;
+                }
+                case ECronField::CF_YEAR: {
+                    if (idx < 1970) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    Years.Set(idx - 1970);
+                    break;
+                }
+                default:
+                    ythrow yexception() << ErrorUnknownField;
+            }
+        }
+
+        void DelBit(ECronField field, uint32_t idx) {
+            switch(field) {
+                case ECronField::CF_SECOND: {
+                    Seconds.Reset(idx);
+                    break;
+                }
+                case ECronField::CF_MINUTE: {
+                    Minutes.Reset(idx);
+                    break;
+                }
+                case ECronField::CF_HOUR_OF_DAY: {
+                    Hours.Reset(idx);
+                    break;
+                }
+                case ECronField::CF_DAY_OF_WEEK: {
+                    DaysOfWeek.Reset(idx);
+                    break;
+                }
+                case ECronField::CF_DAY_OF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    DaysOfMonth.Reset(idx - 1);
+                    break;
+                }
+                case ECronField::CF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    Months.Reset(idx - 1);
+                    break;
+                }
+                case ECronField::CF_YEAR: {
+                    if (idx < 1970) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    Years.Reset(idx - 1970);
+                    break;
+                }
+                default:
+                    ythrow yexception() << ErrorUnknownField;
+            }
+        }
+
+        uint8_t GetBit(ECronField field, uint32_t idx) {
+            switch(field) {
+                case ECronField::CF_SECOND: {
+                    return Seconds.Get(idx);
+                }
+                case ECronField::CF_MINUTE: {
+                    return Minutes.Get(idx);
+                }
+                case ECronField::CF_HOUR_OF_DAY: {
+                    return Hours.Get(idx);
+                }
+                case ECronField::CF_DAY_OF_WEEK: {
+                    return DaysOfWeek.Get(idx);
+                }
+                case ECronField::CF_DAY_OF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    return DaysOfMonth.Get(idx - 1);
+                }
+                case ECronField::CF_MONTH: {
+                    if (idx < 1) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    return Months.Get(idx - 1);
+                }
+                case ECronField::CF_YEAR: {
+                    if (idx < 1970) {
+                        ythrow yexception() << ErrorOutOfRange;
+                    }
+                    return Years.Get(idx - 1970);
+                }
+                default: {
+                    ythrow yexception() << ErrorUnknownField;
+                }
+            }
+        }
+
+        TMaybe<uint32_t> FindNextSetBit(ECronField field, uint32_t max, uint32_t fromIndex) {
+            switch(field) {
+                case ECronField::CF_SECOND: {
+                    return NextSetBit(Seconds, max, fromIndex, 0);
+                }
+                case ECronField::CF_MINUTE: {
+                    return NextSetBit(Minutes, max, fromIndex, 0);
+                }
+                case ECronField::CF_HOUR_OF_DAY: {
+                    return NextSetBit(Hours, max, fromIndex, 0);
+                }
+                case ECronField::CF_DAY_OF_WEEK: {
+                    return NextSetBit(DaysOfWeek, max, fromIndex, 0);
+                }
+                case ECronField::CF_DAY_OF_MONTH: {
+                    return NextSetBit(DaysOfMonth, max, fromIndex, 1);
+                }
+                case ECronField::CF_MONTH: {
+                    return NextSetBit(Months, max, fromIndex, 1);
+                }
+                case ECronField::CF_YEAR: {
+                    return NextSetBit(Years, max, fromIndex, 1970);
+                }
+                default:
+                    ythrow yexception() << ErrorUnknownField;
+            }
+        }
+
+        TMaybe<uint32_t> FindPrevSetBit(ECronField field, uint32_t fromIndex, uint32_t toIndex) {
+            switch(field) {
+                case ECronField::CF_SECOND: {
+                    return PrevSetBit(Seconds, fromIndex, toIndex, 0);
+                }
+                case ECronField::CF_MINUTE: {
+                    return PrevSetBit(Minutes, fromIndex, toIndex, 0);
+                }
+                case ECronField::CF_HOUR_OF_DAY: {
+                    return PrevSetBit(Hours, fromIndex, toIndex, 0);
+                }
+                case ECronField::CF_DAY_OF_WEEK: {
+                    return PrevSetBit(DaysOfWeek, fromIndex, toIndex, 0);
+                }
+                case ECronField::CF_DAY_OF_MONTH: {
+                    return PrevSetBit(DaysOfMonth, fromIndex, toIndex, 1);
+                }
+                case ECronField::CF_MONTH: {
+                    return PrevSetBit(Months, fromIndex, toIndex, 1);
+                }
+                case ECronField::CF_YEAR: {
+                    return PrevSetBit(Years, fromIndex, toIndex, 1970);
+                }
+                default:
+                    ythrow yexception() << ErrorUnknownField;
+            }
+        }
+
+        uint8_t GetFlags() {
+            return Flags;
+        }
+
+        void SetFlag(uint32_t idx) {
+            Y_ENSURE(8 > idx, ErrorOutOfRange);
+            Flags |= static_cast<uint8_t>(1 << idx);
+        }
+
+        int8_t GetDayInMonth() {
+            return DayInMonth;
+        }
+
+        void SetDayInMonth(int8_t dim) {
+            DayInMonth = dim;
+        }
+
+        void AddToDayInMonth(int8_t dim) {
+            DayInMonth += dim;
+        }
+    };
+
+    struct TParserContext {
+        TStringBuf input;
+        ETokenType Type = ETokenType::TT_INVALID;
+        ECronField FieldType = ECronField::CF_SECOND;
+        int32_t Value = 0;
+        uint32_t Min = 0;
+        uint32_t Max = 0;
+        bool FixDow = false;
+        bool LDow = false;
+    };
+
+private:
+    TCronExpr Target_;
+
+    static uint32_t GetWeekday(const NDatetime::TCivilSecond& calendar) {
+        return (static_cast<int32_t>(NDatetime::GetWeekday(calendar)) + 1) % 7;
+    }
+
+    static uint32_t GetField(const NDatetime::TCivilSecond& date, ECronField field) {
+        switch (field) {
+            case ECronField::CF_SECOND:
+                return date.second();
+            case ECronField::CF_MINUTE:
+                return date.minute();
+            case ECronField::CF_HOUR_OF_DAY:
+                return date.hour();
+            case ECronField::CF_DAY_OF_WEEK:
+                return GetWeekday(date);
+            case ECronField::CF_DAY_OF_MONTH:
+                return date.day();
+            case ECronField::CF_MONTH:
+                return date.month();
+            case ECronField::CF_YEAR:
+                return date.year();
+            default:
+                ythrow yexception() << ErrorUnknownField;
+        }
+    }
+
+    static uint32_t LastDayOfMonth(uint32_t month, uint32_t year, bool isWeekday) {
+        NDatetime::TCivilSecond calendar(year, month + 1, 0);
+        uint32_t day = calendar.day();
+
+        if (isWeekday) {
+            uint32_t weekday = GetWeekday(calendar);
+            if (weekday == 0) {
+                if (day < 2) {
+                    ythrow yexception() << ErrorOutOfRange;
+                }
+                day -= 2;
+            } else if (weekday == 6) {
+                if (day < 1) {
+                    ythrow yexception() << ErrorOutOfRange;
+                }
+                day -= 1;
+            }
+        }
+        return day;
+    }
+
+    static uint32_t ClosestWeekday(uint32_t dayOfMonth, uint32_t month, uint32_t year) {
+        NDatetime::TCivilSecond calendar;
+
+        if (dayOfMonth > LastDayOfMonth(month, year, false)) {
+            ythrow yexception() << "Day of month out of range";
+        }
+
+        calendar = NDatetime::TCivilSecond(year, month, dayOfMonth);
+
+        uint32_t wday = GetWeekday(calendar);
+
+        if (wday == 0) {
+            if (dayOfMonth == LastDayOfMonth(month, year, 0)) {
+                dayOfMonth -= 2;
+            } else {
+                dayOfMonth += 1;
+            }
+
+        } else if (wday == 6) {
+            if (dayOfMonth == 1) {
+                dayOfMonth += 2;
+            } else {
+                dayOfMonth -= 1;
+            }
+        }
+
+        return dayOfMonth;
+    }
+
+    static void SetField(NDatetime::TCivilSecond& calendar, ECronField field, int32_t value) {
+        switch (field) {
+            case ECronField::CF_SECOND:
+                calendar = NDatetime::TCivilSecond(calendar.year(), calendar.month(), calendar.day(), calendar.hour(), calendar.minute(), value);
+                return;
+            case ECronField::CF_MINUTE:
+                calendar = NDatetime::TCivilSecond(calendar.year(), calendar.month(), calendar.day(), calendar.hour(), value, calendar.second());
+                return;
+            case ECronField::CF_HOUR_OF_DAY:
+                calendar = NDatetime::TCivilSecond(calendar.year(), calendar.month(), calendar.day(), value, calendar.minute(), calendar.second());
+                return;
+            case ECronField::CF_DAY_OF_MONTH:
+                calendar = NDatetime::TCivilSecond(calendar.year(), calendar.month(), value, calendar.hour(), calendar.minute(), calendar.second());
+                return;
+            case ECronField::CF_MONTH: {
+                int32_t maxDays = LastDayOfMonth(value, calendar.year(), false);
+                if (calendar.day() > maxDays) {
+                    calendar = NDatetime::TCivilSecond(calendar.year(), calendar.month(), maxDays, calendar.hour(), calendar.minute(), calendar.second());
+                }
+                calendar = NDatetime::TCivilSecond(calendar.year(), value, calendar.day(), calendar.hour(), calendar.minute(), calendar.second());
+                return;
+            }
+            case ECronField::CF_YEAR:
+                calendar = NDatetime::TCivilSecond(value, calendar.month(), calendar.day(), calendar.hour(), calendar.minute(), calendar.second());
+                return;
+            default:
+                ythrow yexception() << ErrorUnknownField;
+        }
+    }
+
+    static void AddToField(NDatetime::TCivilSecond& calendar, ECronField field, int32_t value) {
+        SetField(calendar, field, static_cast<int32_t>(GetField(calendar, field)) + value);
+    }
+
+    static void ResetMin(NDatetime::TCivilSecond& calendar, ECronField field) {
+        if (field == ECronField::CF_DAY_OF_MONTH || field == ECronField::CF_MONTH) {
+            SetField(calendar, field, 1);
+        } else {
+            SetField(calendar, field, 0);
+        }
+    }
+
+    static void ResetMax(NDatetime::TCivilSecond& calendar, ECronField field) {
+        switch (field) {
+            case ECronField::CF_SECOND:
+                SetField(calendar, field, CRON_MAX_SECONDS - 1);
+                break;
+            case ECronField::CF_MINUTE:
+                SetField(calendar, field, CRON_MAX_MINUTES - 1);
+                break;
+            case ECronField::CF_HOUR_OF_DAY:
+                SetField(calendar, field, CRON_MAX_HOURS  - 1);
+                break;
+            case ECronField::CF_DAY_OF_MONTH:
+                SetField(calendar, field, LastDayOfMonth(calendar.month(), calendar.year(), 0));
+                break;
+            default:
+                break;
+        }
+    }
+
+    static void ResetAllMin(NDatetime::TCivilSecond& calendar, TBitMap<7, uint8_t>& fields) {
+        for (int32_t i = 0; i < 7; ++i) {
+
+            if (fields.Get(i)) {
+                ResetMin(calendar, ECronField(i));
+            }
+        }
+    }
+
+    static void ResetAllMax(NDatetime::TCivilSecond& calendar, TBitMap<7, uint8_t>& fields) {
+        for (int32_t i = 0; i < 7; ++i) {
+            if (fields.Get(i)) {
+                ResetMax(calendar, ECronField(i));
+            }
+        }
+    }
+
+    template <size_t N>
+    static TMaybe<uint32_t> MatchOrdinals(TStringBuf str, std::array<TStringBuf, N> arr) {
+        size_t arrLen = arr.size();
+
+        for (size_t i = 0; i < arrLen; ++i) {
+            if (AsciiHasPrefixIgnoreCase(str, arr[i])) {
+                return i;
+            }
+        }
+        return Nothing();
+    }
+
+    static void TokenNext(TParserContext& context) {
+        auto input = context.input;
+        context.Type = ETokenType::TT_INVALID;
+        context.Value = 0;
+
+        if (context.input.empty() || context.input.front() == '\0') {
+            context.Type = ETokenType::TT_EOF;
+        } else if (IsAsciiSpace(context.input.front())) {
+
+            while (!context.input.empty() && IsAsciiSpace(context.input.front())) {
+                context.input.Skip(1);
+            }
+            context.Type = ETokenType::TT_WS;
+
+        } else if (IsAsciiDigit(context.input.front())) {
+
+            while (!context.input.empty() && IsAsciiDigit(context.input.front())) {
+                context.Value = context.Value * 10 + (context.input.front() - '0');
+                context.input.Skip(1);
+            }
+            context.Type = ETokenType::TT_NUMBER;
+
+        } else {
+            bool isAlpha = IsAsciiAlpha(input.front());
+
+            if (isAlpha) {
+                while (!input.empty() && IsAsciiAlpha(input.front())) {
+                    input.Skip(1);
+                }
+                context.Value = MatchOrdinals(context.input, DAYS_ARR).GetOrElse(-1);
+
+                if (context.Value < 0) {
+                    context.Value = MatchOrdinals(context.input, CF_MONTHS_ARR).GetOrElse(-1) + 1;
+                    if (context.Value == 0) {
+                        context.Value = -1;
+                    }
+                }
+
+                if (context.Value >= 0) {
+                    context.input = input;
+                    context.Type = ETokenType::TT_NUMBER;
+                }
+            }
+
+            if (!isAlpha || context.Value < 0) {
+                switch (context.input.front()) {
+                    case '*':
+                        context.Type = ETokenType::TT_ASTERISK;
+                        break;
+                    case '?':
+                        context.Type = ETokenType::TT_QUESTION;
+                        break;
+                    case ',':
+                        context.Type = ETokenType::TT_COMMA;
+                        break;
+                    case '/':
+                        context.Type = ETokenType::TT_SLASH;
+                        break;
+                    case 'L':
+                        context.Type = ETokenType::TT_L;
+                        break;
+                    case 'W':
+                        context.Type = ETokenType::TT_W;
+                        break;
+                    case '#':
+                        context.Type = ETokenType::TT_HASH;
+                        break;
+                    case '-':
+                        context.Type = ETokenType::TT_MINUS;
+                        break;
+                }
+                context.input.Skip(1);
+            }
+        }
+
+        if (ETokenType::TT_INVALID == context.Type) {
+            ythrow yexception() << ErrorUnknownField;
+        }
+    }
+
+    static int32_t Number(TParserContext& context) {
+        int32_t value = 0;
+
+        switch (context.Type) {
+            case ETokenType::TT_MINUS:
+                TokenNext(context);
+
+                if (ETokenType::TT_NUMBER == context.Type) {
+                    value = -context.Value;
+                    TokenNext(context);
+                } else {
+                    ythrow yexception() << "Number '-' follows with number";
+                }
+                break;
+            case ETokenType::TT_NUMBER:
+                value = context.Value;
+                TokenNext(context);
+                break;
+            default:
+                ythrow yexception() << "Number - error";
+        }
+
+        return value;
+    }
+
+    static uint32_t Frequency(TParserContext& context, uint32_t delta, uint32_t& to, bool range) {
+        switch (context.Type) {
+            case ETokenType::TT_SLASH: {
+                TokenNext(context);
+                if (ETokenType::TT_NUMBER == context.Type) {
+                    delta = context.Value;
+                    if (delta < 1) {
+                        ythrow yexception() << "Frequency - needs to be at least 1";
+                    }
+                    if (!range) {
+                        to = context.Max - 1;
+                    }
+                    TokenNext(context);
+                } else {
+                    ythrow yexception() << "Frequency - '/' follows with number";
+                }
+                break;
+            }
+            case ETokenType::TT_COMMA:
+            case ETokenType::TT_WS:
+            case ETokenType::TT_EOF:
+                break;
+            default:
+                ythrow yexception() << "Frequency - error";
+        }
+        return delta;
+    }
+
+    uint32_t Range(TParserContext& context, uint32_t& from, uint32_t to) {
+        switch (context.Type) {
+            case ETokenType::TT_HASH: {
+
+                if (ECronField::CF_DAY_OF_WEEK == context.FieldType) {
+                    TokenNext(context);
+
+                    if (Target_.GetDayInMonth()) {
+                        ythrow yexception() << "Nth-day - support for specifying multiple '#' segments is not implemented";
+                    }
+
+                    Target_.SetDayInMonth(Number(context));
+
+                    if (Target_.GetDayInMonth() > 5 || Target_.GetDayInMonth() < -5) {
+                        ythrow yexception() << "Nth-day - '#' can follow only with -5..5";
+                    }
+                } else {
+                    ythrow yexception() << "Nth-day - '#' allowed only for day of week";
+                }
+                break;
+            }
+            case ETokenType::TT_MINUS: {
+                TokenNext(context);
+
+                if (ETokenType::TT_NUMBER == context.Type) {
+                    to = context.Value;
+                    TokenNext(context);
+                } else {
+                    ythrow yexception() << "Range '-' follows with number";
+                }
+                break;
+            }
+            case ETokenType::TT_W: {
+                Target_.SetDayInMonth(static_cast<int8_t>(to));
+                from = context.Min;
+
+                for (uint32_t i = 1; i <= 5; ++i) {
+                    Target_.SetBit(ECronField::CF_DAY_OF_WEEK, i);
+                }
+                Target_.SetFlag(2);
+                to = context.Max - 1;
+                TokenNext(context);
+                break;
+            }
+            case ETokenType::TT_L: {
+                if (ECronField::CF_DAY_OF_WEEK == context.FieldType) {
+                    Target_.SetDayInMonth(-1);
+                    TokenNext(context);
+                } else {
+                    ythrow yexception() << "Range - 'L' allowed only for day of week";
+                }
+                break;
+            }
+            case ETokenType::TT_WS:
+            case ETokenType::TT_SLASH:
+            case ETokenType::TT_COMMA:
+            case ETokenType::TT_EOF:
+                break;
+            default:
+                ythrow yexception() << "Range - error";
+        }
+
+        return to;
+    }
+
+    void Segment(TParserContext& context) {
+        uint32_t from = context.Min;
+        Y_ENSURE(context.Max > 0);
+        uint32_t to = context.Max - 1;
+        uint32_t delta = 1;
+        bool isLW = false;
+
+        switch (context.Type) {
+            case ETokenType::TT_ASTERISK: {
+                TokenNext(context);
+                delta = Frequency(context, delta, to, false);
+                break;
+            }
+            case ETokenType::TT_NUMBER: {
+                from = context.Value;
+                TokenNext(context);
+                to = Range(context, from, from);
+                delta = Frequency(context, delta, to, from != to);
+                break;
+            }
+            case ETokenType::TT_L: {
+                TokenNext(context);
+
+                switch (context.FieldType) {
+                    case ECronField::CF_DAY_OF_MONTH: {
+                        Target_.SetDayInMonth(-1);
+
+                        switch (context.Type) {
+                            case ETokenType::TT_MINUS:
+                            case ETokenType::TT_NUMBER: {
+                                Target_.AddToDayInMonth(Number(context));
+                                break;
+                            }
+                            case ETokenType::TT_W: {
+                                if (ECronField::CF_DAY_OF_MONTH == context.FieldType) {
+                                    TokenNext(context);
+
+                                    for (uint32_t i = 1; i <= 5; ++i) {
+                                        Target_.SetBit(ECronField::CF_DAY_OF_WEEK, i);
+                                    }
+
+                                    Target_.SetFlag(1);
+                                    context.FixDow = true;
+                                    isLW = true;
+                                } else {
+                                    ythrow yexception() << "Offset - 'W' allowed only for day of month";
+                                }
+                                break;
+                            }
+                            case ETokenType::TT_COMMA:
+                            case ETokenType::TT_WS:
+                            case ETokenType::TT_EOF:
+                                break;
+                            default:
+                                ythrow yexception() << "Offset - error";
+                        }
+                        /* Note 0..6 and not 1..7*/
+                        if (!isLW) {
+                            Target_.SetFlag(0);
+                            context.FixDow = true;
+                            context.LDow = true;
+                        }
+                        break;
+                    }
+                    case ECronField::CF_DAY_OF_WEEK:
+                        from = to = 0;
+                        break;
+                    default:
+                        ythrow yexception() << "Segment 'L' allowed only for day of month and day of week";
+                }
+                break;
+            }
+            case ETokenType::TT_W: {
+                if (ECronField::CF_DAY_OF_MONTH != context.FieldType) {
+                    ythrow yexception() << "Segment 'W' allowed only for day of month";
+                }
+                for (uint32_t i = 1; i <= 5; ++i) {
+                    Target_.SetBit(ECronField::CF_DAY_OF_WEEK, i);
+                }
+                TokenNext(context);
+                context.FixDow = true;
+                break;
+            }
+            case ETokenType::TT_QUESTION: {
+                TokenNext(context);
+                break;
+            }
+            default:
+                ythrow yexception() << "Segment - error";
+        }
+
+        if (ECronField::CF_DAY_OF_WEEK == context.FieldType && context.FixDow && !context.LDow) {
+            return;
+        }
+
+        if (from < context.Min || to < context.Min) {
+            ythrow yexception() << "Range - specified range is less than minimum";
+        }
+
+        if (from >= context.Max || to >= context.Max) {
+            ythrow yexception() << "Range - specified range exceeds maximum";
+        }
+
+        if (from > to && ECronField::CF_DAY_OF_WEEK != context.FieldType) {
+            ythrow yexception() << "Range - specified range start exceeds range end";
+        }
+
+        if (from > to && ECronField::CF_DAY_OF_WEEK == context.FieldType) {
+            for (; from < 7; from += delta) {
+                Target_.SetBit(context.FieldType, from);
+            }
+            for (from %= 7; from <= to; from += delta) {
+                Target_.SetBit(context.FieldType, from);
+            }
+        }
+
+        for (; from <= to; from += delta) {
+            Target_.SetBit(context.FieldType, from);
+        }
+
+        if (ECronField::CF_DAY_OF_WEEK == context.FieldType && Target_.GetBit(ECronField::CF_DAY_OF_WEEK, 7)) {
+
+            // Sunday can be represented as 0 or 7
+            Target_.SetBit(ECronField::CF_DAY_OF_WEEK, 0);
+            Target_.DelBit(ECronField::CF_DAY_OF_WEEK, 7);
+        }
+        return;
+    }
+
+    void Field(TParserContext& context) {
+        Segment(context);
+        switch (context.Type) {
+            case ETokenType::TT_COMMA:
+                TokenNext(context);
+                Field(context);
+                break;
+            case ETokenType::TT_WS:
+            case ETokenType::TT_EOF:
+                break;
+            default:
+                ythrow yexception() << "FieldRest - error";
+        }
+        return;
+    }
+
+    void FieldWrapper(TParserContext& context, ECronField FieldType, uint32_t min, uint32_t max) {
+        context.FieldType = FieldType;
+        context.Min = min;
+        context.Max = max;
+
+        Field(context);
+    }
+
+    void Fields(TParserContext& context, uint32_t len) {
+        TokenNext(context);
+
+        if (len < 6) {
+            Target_.SetBit(ECronField::CF_SECOND, 0);
+        } else {
+            FieldWrapper(context, ECronField::CF_SECOND, 0, CRON_MAX_SECONDS);
+
+            if (ETokenType::TT_WS == context.Type) {
+                TokenNext(context);
+            } else {
+                ythrow yexception() << ErrorWS;
+            }
+        }
+
+        FieldWrapper(context, ECronField::CF_MINUTE, 0, CRON_MAX_MINUTES);
+        if (ETokenType::TT_WS == context.Type) {
+            TokenNext(context);
+        } else {
+            ythrow yexception() << ErrorWS;
+        }
+
+        FieldWrapper(context, ECronField::CF_HOUR_OF_DAY, 0, CRON_MAX_HOURS);
+        if (ETokenType::TT_WS == context.Type) {
+            TokenNext(context);
+        } else {
+            ythrow yexception() << ErrorWS;
+        }
+
+        FieldWrapper(context, ECronField::CF_DAY_OF_MONTH, 1, CRON_MAX_DAYS_OF_MONTH + 1);
+        if (ETokenType::TT_WS == context.Type) {
+            TokenNext(context);
+        } else {
+            ythrow yexception() << ErrorWS;
+        }
+
+        FieldWrapper(context, ECronField::CF_MONTH, 1, CRON_MAX_MONTHS + 1);
+        if (ETokenType::TT_WS == context.Type) {
+            TokenNext(context);
+        } else {
+            ythrow yexception() << ErrorWS;
+        }
+
+        FieldWrapper(context, ECronField::CF_DAY_OF_WEEK, 0, CRON_MAX_DAYS_OF_WEEK + 1);
+        if (len < 7) {
+            Target_.SetBit(ECronField::CF_YEAR, 1970 + YEARS_GAP_LENGTH - 1);
+        } else {
+            if (ETokenType::TT_WS == context.Type) {
+                TokenNext(context);
+            } else {
+                ythrow yexception() << ErrorWS;
+            }
+
+            FieldWrapper(context, ECronField::CF_YEAR, CRON_MIN_YEARS, CRON_MAX_YEARS);
+        }
+        return;
+    }
+
+    /////////////////////////////////////////////////
+
+    TMaybe<uint32_t> FindNextPrev(uint32_t max, uint32_t value, uint32_t min, NDatetime::TCivilSecond& calendar, ECronField field, ECronField nextField, TBitMap<7, uint8_t>& lowerOrders, int32_t offset) {
+        TMaybe<uint32_t> nextValue = (offset > 0 ? Target_.FindNextSetBit(field, max, value) : Target_.FindPrevSetBit(field, value, min));
+
+        // roll under if needed
+        if (nextValue.Empty()) {
+            if (nextField == ECronField::CF_NEXT) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+            if (offset > 0) {
+                ResetMax(calendar, field);
+            } else {
+                ResetMin(calendar, field);
+            }
+            AddToField(calendar, nextField, offset);
+
+            nextValue = offset > 0 ? Target_.FindNextSetBit(field, max, min) : Target_.FindPrevSetBit(field, max - 1, value);
+        }
+
+        if (nextValue.Empty() || nextValue != value) {
+            if (offset > 0) {
+                ResetAllMin(calendar, lowerOrders);
+            } else {
+                ResetAllMax(calendar, lowerOrders);
+            }
+            if (nextValue.Empty()) {
+                SetField(calendar, field, 0);
+                return 0;
+            } else {
+                SetField(calendar, field, nextValue.GetRef());
+            }
+
+        }
+        return nextValue;
+    }
+
+    bool FindDayCondition(const NDatetime::TCivilSecond& calendar, int8_t dim, uint32_t dom, uint32_t dow, uint8_t flags, TMaybe<uint32_t> day) {
+        if (day.Empty()) {
+            if ((!flags && dim < 0) || flags & 1) {
+                day = LastDayOfMonth(calendar.month(), calendar.year(), 0);
+            } else if (flags & 2) {
+                day = LastDayOfMonth(calendar.month(), calendar.year(), 1);
+            } else if (flags & 4) {
+                Y_ENSURE(dim >= 0);
+                day = ClosestWeekday(dim, calendar.month(), calendar.year());
+            }
+        }
+
+        if (!Target_.GetBit(ECronField::CF_DAY_OF_MONTH, dom) || !Target_.GetBit(ECronField::CF_DAY_OF_WEEK, dow)) {
+            return true;
+        }
+
+        int64_t dayValue = day.Empty() ? 0 : (day.GetRef() + 1);
+        int64_t domValue = static_cast<int64_t>(dom);
+
+        if (flags) {
+            if ((flags & 3) && domValue != dayValue + dim) {
+                return true;
+            }
+
+            if ((flags & 4) && domValue != dayValue - 1) {
+                return true;
+            }
+        } else {
+            if (dim < 0 && (domValue < dayValue + static_cast<int64_t>(WEEK_DAYS) * dim || domValue >= dayValue + static_cast<int64_t>(WEEK_DAYS) * (dim + 1))) {
+                return true;
+            }
+
+            if (dim > 0 && (domValue < static_cast<int64_t>(WEEK_DAYS) * (dim - 1) + 1 || domValue >= static_cast<int64_t>(WEEK_DAYS) * dim + 1)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    TMaybe<int32_t> FindDay(NDatetime::TCivilSecond& calendar, int8_t dim, uint32_t dom, uint32_t dow, uint8_t flags, TBitMap<7, uint8_t>& resets, int32_t offset) {
+        TMaybe<uint32_t> day = Nothing();
+        uint32_t year = calendar.year();
+        uint32_t month = calendar.month();
+        uint32_t count = 0;
+        uint32_t max = 366;
+
+        while (FindDayCondition(calendar, dim, dom, dow, flags, day) && count++ < max) {
+            if (offset > 0) {
+                ResetAllMin(calendar, resets);
+            } else {
+                ResetAllMax(calendar, resets);
+            }
+
+            AddToField(calendar, ECronField::CF_DAY_OF_MONTH, offset);
+
+            dom = calendar.day();
+            dow = GetWeekday(calendar);
+
+            if (year != calendar.year()) {
+                year = calendar.year();
+                day = Nothing(); /* This should not be needed unless there is as single day month in libc. */
+            }
+
+            if (month != static_cast<uint32_t>(calendar.month())) {
+                month = calendar.month();
+                day = Nothing();
+                Y_ENSURE(day.Empty());
+            }
+        }
+        return dom;
+    }
+
+    void DoNextPrev(NDatetime::TCivilSecond& calendar, int32_t offset) {
+        uint32_t baseYear = calendar.year();
+        uint32_t value = 0;
+        TMaybe<uint32_t> updateValue = Nothing();
+        TBitMap<7, uint8_t> resets(0);
+
+        for (;;) {
+            resets.Clear();
+
+            value = GetField(calendar, ECronField::CF_SECOND);
+            updateValue = FindNextPrev(CRON_MAX_SECONDS, value, 0, calendar, ECronField::CF_SECOND, ECronField::CF_MINUTE, resets, offset);
+
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value == updateValue) {
+                resets.Set(static_cast<uint32_t>(ECronField::CF_SECOND));
+            } else {
+                continue;
+            }
+
+            value = GetField(calendar, ECronField::CF_MINUTE);
+            updateValue = FindNextPrev(CRON_MAX_MINUTES, value, 0, calendar, ECronField::CF_MINUTE, ECronField::CF_HOUR_OF_DAY, resets, offset);
+
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value == updateValue) {
+                resets.Set(static_cast<uint32_t>(ECronField::CF_MINUTE));
+            } else {
+                continue;
+            }
+
+            value = GetField(calendar, ECronField::CF_HOUR_OF_DAY);
+            updateValue = FindNextPrev(CRON_MAX_HOURS, value, 0, calendar, ECronField::CF_HOUR_OF_DAY, ECronField::CF_DAY_OF_MONTH, resets, offset);
+
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value == updateValue) {
+                resets.Set(static_cast<uint32_t>(ECronField::CF_HOUR_OF_DAY));
+            } else {
+                continue;
+            }
+
+            value = GetField(calendar, ECronField::CF_DAY_OF_MONTH);
+            updateValue = FindDay(calendar, Target_.GetDayInMonth(), value, GetWeekday(calendar), Target_.GetFlags(), resets, offset);
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value == updateValue) {
+                resets.Set(static_cast<uint32_t>(ECronField::CF_DAY_OF_MONTH));
+            } else {
+                continue;
+            }
+
+            value = GetField(calendar, ECronField::CF_MONTH);
+            updateValue = FindNextPrev(CRON_MAX_MONTHS, value, 1, calendar, ECronField::CF_MONTH, ECronField::CF_YEAR, resets, offset);
+
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value != updateValue) {
+                if (static_cast<uint32_t>(std::abs(calendar.year() - baseYear)) > CRON_MAX_YEARS_DIFF) {
+                    break;
+                }
+                continue;
+            }
+
+            if (Target_.GetBit(ECronField::CF_YEAR, 1970 + YEARS_GAP_LENGTH - 1)) {
+                break;
+            } else {
+                resets.Set(static_cast<uint32_t>(ECronField::CF_MONTH));
+            }
+
+            value = GetField(calendar, ECronField::CF_YEAR);
+            updateValue = FindNextPrev(CRON_MAX_YEARS, value, CRON_MIN_YEARS, calendar, ECronField::CF_YEAR, ECronField::CF_NEXT, resets, offset);
+
+            if (updateValue.Empty()) {
+                ythrow yexception() << ErrorDateNotExists;
+            }
+
+            if (value == updateValue) {
+                break;
+            }
+        }
+    }
+
+    NDatetime::TCivilSecond Cron(NDatetime::TCivilSecond original, int32_t offset) {
+        NDatetime::TCivilSecond calendar;
+        calendar = original;
+
+        DoNextPrev(calendar, offset);
+
+        if (calendar == original) {
+            /* We arrived at the original timestamp - round up to the next whole second and try again... */
+            AddToField(calendar, ECronField::CF_SECOND, offset);
+            DoNextPrev(calendar, offset);
+        }
+
+        if (
+            !Target_.GetBit(ECronField::CF_SECOND, calendar.second()) ||
+            !Target_.GetBit(ECronField::CF_MINUTE, calendar.minute()) ||
+            !Target_.GetBit(ECronField::CF_HOUR_OF_DAY, calendar.hour()) ||
+            !Target_.GetBit(ECronField::CF_DAY_OF_MONTH, calendar.day()) ||
+            !Target_.GetBit(ECronField::CF_MONTH, calendar.month()) ||
+            !(Target_.GetBit(ECronField::CF_YEAR, 1970 + YEARS_GAP_LENGTH - 1) || Target_.GetBit(ECronField::CF_YEAR, calendar.year())) ||
+            !Target_.GetBit(ECronField::CF_DAY_OF_WEEK, GetWeekday(calendar))
+        ) {
+            ythrow yexception() << ErrorDateNotExists;
+        }
+
+        return calendar;
+    }
+
+    void CronParseExpr(TStringBuf expression) {
+        TParserContext context;
+        if (expression.empty()) {
+            ythrow yexception() << "Invalid empty expression";
+        }
+
+        if ('@' == expression.front()) {
+            if (expression == "@annually"sv || expression == "@yearly"sv) {
+                expression = "0 0 0 1 1 *"sv;
+            } else if (expression == "@monthly"sv) {
+                expression = "0 0 0 1 * *"sv;
+            } else if (expression == "@weekly"sv) {
+                expression = "0 0 0 * * 0"sv;
+            } else if (expression == "@daily"sv || expression == "@midnight"sv) {
+                expression = "0 0 0 * * *"sv;
+            } else if (expression == "@hourly"sv) {
+                expression = "0 0 * * * *"sv;
+            } else if (expression == "@minutely"sv) {
+                expression = "0 * * * * *"sv;
+            } else if (expression == "@secondly"sv) {
+                expression = "* * * * * * *"sv;
+            } else if (expression == "@reboot"sv) {
+                ythrow yexception() << "@reboot not implemented";
+            } else {
+                ythrow yexception() << "Unknown typed cron";
+            }
+        }
+        uint32_t len = StringSplitter(expression).Split(' ').SkipEmpty().Count();
+        if (len < 5 || len > 7) {
+            ythrow yexception() << Join(" ", "Invalid number of fields, expression must consist of 5-7 fields but has:"sv, len);
+        }
+
+        context.input = expression;
+        Fields(context, len);
+        return;
+    }
+
+public:
+
+    NDatetime::TCivilSecond FindCronNext(NDatetime::TCivilSecond date) {
+        return Cron(date, +1);
+    }
+
+    NDatetime::TCivilSecond FindCronPrev(NDatetime::TCivilSecond date) {
+        return Cron(date, -1);
+    }
+
+    TImpl(const TStringBuf cronUnparsedExpr) {
+        CronParseExpr(cronUnparsedExpr);
+    }
+};
+
+TCronExpression::TCronExpression(const TStringBuf cronUnparsedExpr)
+    : Impl(MakeHolder<TImpl>(cronUnparsedExpr))
+{
+}
+
+TCronExpression::~TCronExpression() = default;
+
+NDatetime::TCivilSecond TCronExpression::CronNext(NDatetime::TCivilSecond date) {
+    return Impl->FindCronNext(date);
+}
+
+NDatetime::TCivilSecond TCronExpression::CronPrev(NDatetime::TCivilSecond date) {
+    return Impl->FindCronPrev(date);
+}