From ae4fa388c3a2fac5f1908f0696e22b05b76359cc Mon Sep 17 00:00:00 2001 From: Mike Curtiss Date: Tue, 5 Mar 2013 23:22:54 -0800 Subject: [PATCH] HACK: Static detection of infinite sequences Summary: Certain operations should not be performed on infinite sequences (e.g. sorting, left-folds, summation). In some cases, we can detect that a sequence is infinite at compile-time and provide a static_assert to prevent such dangerous operations. Test Plan: Manually created cases where the operation should be disallowed. Compiler correctly raised an error. Reviewed By: tjackson@fb.com FB internal diff: D740011 --- folly/experimental/FileGen-inl.h | 5 +++++ folly/experimental/Gen-inl.h | 33 +++++++++++++++++++++++++++-- folly/experimental/StringGen-inl.h | 2 ++ folly/experimental/test/GenTest.cpp | 4 ++-- 4 files changed, 40 insertions(+), 4 deletions(-) diff --git a/folly/experimental/FileGen-inl.h b/folly/experimental/FileGen-inl.h index d45cc618..21b0589c 100644 --- a/folly/experimental/FileGen-inl.h +++ b/folly/experimental/FileGen-inl.h @@ -52,6 +52,11 @@ class FileReader : public GenImpl { } } } + + // Technically, there could be infinite files (e.g. /dev/random), but people + // who open those can do so at their own risk. + static constexpr bool infinite = false; + private: File file_; std::unique_ptr buffer_; diff --git a/folly/experimental/Gen-inl.h b/folly/experimental/Gen-inl.h index 6f68da1a..b0e989c1 100644 --- a/folly/experimental/Gen-inl.h +++ b/folly/experimental/Gen-inl.h @@ -168,10 +168,16 @@ class GenImpl : public FBounded { template void foreach(Body&& body) const { this->self().apply([&](Value value) -> bool { + static_assert(!infinite, "Cannot call foreach on infinite GenImpl"); body(std::forward(value)); return true; }); } + + // Child classes should override if the sequence generated is *definitely* + // infinite. 'infinite' may be false_type for some infinite sequences + // (due the the Halting Problem). + static constexpr bool infinite = false; }; template::value>::type operator|(const GenImpl& gen, Handler&& handler) { + static_assert(!Gen::infinite, + "Cannot pull all values from an infinite sequence."); gen.self().foreach(std::forward(handler)); } @@ -439,6 +447,8 @@ public: body(arg); } } + + static constexpr bool infinite = endless; }; /** @@ -470,6 +480,8 @@ public: first_.foreach(std::forward(body)); second_.foreach(std::forward(body)); } + + static constexpr bool infinite = First::infinite || Second::infinite; }; /** @@ -567,6 +579,8 @@ class Map : public Operator> { return handler(pred_(std::forward(value))); }); } + + static constexpr bool infinite = Source::infinite; }; template> { return true; }); } + + static constexpr bool infinite = Source::infinite; }; template> { Gen compose(const GenImpl& source) const { return Gen(source.self(), pred_); } + + // Theoretically an 'until' might stop an infinite + static constexpr bool infinite = false; }; /** @@ -809,6 +828,8 @@ class Skip : public Operator { return handler(std::forward(value)); }); } + + static constexpr bool infinite = Source::infinite; }; template> { class Generator : public GenImpl> { + static_assert(!Source::infinite, "Cannot sort infinite source!"); Source source_; Selector selector_; Comparer comparer_; @@ -1010,6 +1032,7 @@ class FoldLeft : public Operator> { template Seed compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot foldl infinite source"); Seed accum = seed_; source | [&](Value v) { accum = fold_(std::move(accum), std::forward(v)); @@ -1107,6 +1130,7 @@ class All : public Operator> { template bool compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot call 'all' on infinite source"); bool all = true; source | [&](Value v) -> bool { if (!pred_(std::forward(v))) { @@ -1173,6 +1197,7 @@ class Count : public Operator { template size_t compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot count infinite source"); return foldl(size_t(0), [](size_t accum, Value v) { return accum + 1; @@ -1189,12 +1214,11 @@ class Count : public Operator { */ class Sum : public Operator { public: - Sum() { } - template::type> StorageType compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot sum infinite source"); return foldl(StorageType(0), [](StorageType&& accum, Value v) { return std::move(accum) + std::forward(v); @@ -1222,6 +1246,9 @@ class Contains : public Operator> { class Value, class StorageType = typename std::decay::type> bool compose(const GenImpl& source) const { + static_assert(!Source::infinite, + "Calling contains on an infinite source might cause " + "an infinite loop."); return !(source | [this](Value value) { return !(needle_ == std::forward(value)); }); @@ -1414,6 +1441,8 @@ class Concat : public Operator { inner.foreach(std::forward(body)); }); } + + static constexpr bool infinite = Source::infinite; }; template { } return true; } + + static constexpr bool infinite = Source::infinite; }; template(); // std::string gen, const char* needle - EXPECT_TRUE(gen | contains("49")); + EXPECT_TRUE(gen | take(9999) | contains("49")); } } @@ -427,7 +427,7 @@ TEST(Gen, Any) { TEST(Gen, All) { EXPECT_TRUE(seq(0, 10) | all([](int i) { return i < 11; })); EXPECT_FALSE(seq(0, 10) | all([](int i) { return i < 5; })); - EXPECT_FALSE(seq(0) | all([](int i) { return i < 10; })); + EXPECT_FALSE(seq(0) | take(9999) | all([](int i) { return i < 10; })); // empty lists satisfies all EXPECT_TRUE(seq(0) | take(0) | all([](int i) { return i < 50; })); -- 2.34.1