First attempt at data generator support

The support is to be considered experimental, that is, the interfaces,
the first party generators and helper functions can change or be removed
at any point in time.

Related to #850

9 files changed, 424 insertions, 16 deletions

diff --git a/include/catch.hpp b/include/catch.hpp
index 017619ce..02a727cc 100644
--- a/include/catch.hpp
+++ b/include/catch.hpp
@@ -62,6 +62,7 @@
 #ifndef CATCH_CONFIG_DISABLE_MATCHERS
 #include "internal/catch_capture_matchers.h"
 #endif
+#include "internal/catch_generators.hpp"
 
 // These files are included here so the single_include script doesn't put them
 // in the conditionally compiled sections
diff --git a/include/internal/catch_generators.cpp b/include/internal/catch_generators.cpp
new file mode 100644
index 00000000..caf5a0df
--- /dev/null
+++ b/include/internal/catch_generators.cpp
@@ -0,0 +1,45 @@
+/*
+ *  Created by Phil Nash on 15/6/2018.
+ *
+ *  Distributed under the Boost Software License, Version 1.0. (See accompanying
+ *  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#include "catch_generators.hpp"
+#include "catch_random_number_generator.h"
+#include "catch_interfaces_capture.h"
+
+#include <set>
+
+namespace Catch {
+
+IGeneratorTracker::~IGeneratorTracker() {}
+
+namespace Generators {
+
+    GeneratorBase::~GeneratorBase() {}
+
+    std::vector<size_t> randomiseIndices( size_t selectionSize, size_t sourceSize ) {
+
+        assert( selectionSize <= sourceSize );
+        std::vector<size_t> indices;
+        indices.reserve( selectionSize );
+        std::uniform_int_distribution<size_t> uid( 0, sourceSize-1 );
+
+        std::set<size_t> seen;
+        // !TBD: improve this algorithm
+        while( indices.size() < selectionSize ) {
+            auto index = uid( rng() );
+            if( seen.insert( index ).second )
+                indices.push_back( index );
+        }
+        return indices;
+    }
+
+    auto acquireGeneratorTracker( SourceLineInfo const& lineInfo ) -> IGeneratorTracker& {
+        return getResultCapture().acquireGeneratorTracker( lineInfo );
+    }
+
+
+} // namespace Generators
+} // namespace Catch
diff --git a/include/internal/catch_generators.hpp b/include/internal/catch_generators.hpp
new file mode 100644
index 00000000..26a310c2
--- /dev/null
+++ b/include/internal/catch_generators.hpp
@@ -0,0 +1,255 @@
+/*
+ *  Created by Phil Nash on 15/6/2018.
+ *
+ *  Distributed under the Boost Software License, Version 1.0. (See accompanying
+ *  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+#ifndef TWOBLUECUBES_CATCH_GENERATORS_HPP_INCLUDED
+#define TWOBLUECUBES_CATCH_GENERATORS_HPP_INCLUDED
+
+#include "catch_interfaces_generatortracker.h"
+#include "catch_common.h"
+
+#include <memory>
+#include <vector>
+#include <cassert>
+#include <limits>
+
+#include <utility>
+
+namespace Catch {
+namespace Generators {
+
+    // !TBD move this into its own location?
+    namespace pf{
+        template<typename T, typename... Args>
+        std::unique_ptr<T> make_unique( Args&&... args ) {
+            return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
+        }
+    }
+
+    template<typename T>
+    struct IGenerator {
+        virtual ~IGenerator() {}
+        virtual auto get( size_t index ) const -> T = 0;
+    };
+
+    template<typename T>
+    class SingleValueGenerator : public IGenerator<T> {
+        T m_value;
+    public:
+        SingleValueGenerator( T const& value ) : m_value( value ) {}
+
+        auto get( size_t ) const -> T override {
+            return m_value;
+        }
+    };
+
+    template<typename T>
+    class FixedValuesGenerator : public IGenerator<T> {
+        std::vector<T> m_values;
+
+    public:
+        FixedValuesGenerator( std::initializer_list<T> values ) : m_values( values ) {}
+
+        auto get( size_t index ) const -> T override {
+            return m_values[index];
+        }
+    };
+
+    template<typename T>
+    class RangeGenerator : public IGenerator<T> {
+        T const m_first;
+        T const m_last;
+
+    public:
+        RangeGenerator( T const& first, T const& last ) : m_first( first ), m_last( last ) {
+            assert( m_last > m_first );
+        }
+
+        auto get( size_t index ) const -> T override {
+            // ToDo:: introduce a safe cast to catch potential overflows
+            return static_cast<T>(m_first+index);
+        }
+    };
+
+
+    template<typename T>
+    struct NullGenerator : IGenerator<T> {
+        auto get( size_t ) const -> T override {
+            throw std::logic_error("A Null Generator should always be empty" );
+        }
+    };
+
+    template<typename T>
+    class Generator {
+        std::unique_ptr<IGenerator<T>> m_generator;
+        size_t m_size;
+
+    public:
+        Generator( size_t size, std::unique_ptr<IGenerator<T>> generator )
+        :   m_generator( std::move( generator ) ),
+            m_size( size )
+        {}
+
+        auto size() const -> size_t { return m_size; }
+        auto operator[]( size_t index ) const -> T {
+            assert( index < m_size );
+            return m_generator->get( index );
+        }
+    };
+
+    std::vector<size_t> randomiseIndices( size_t selectionSize, size_t sourceSize );
+
+    template<typename T>
+    class GeneratorRandomiser : public IGenerator<T> {
+        Generator<T> m_baseGenerator;
+
+        std::vector<size_t> m_indices;
+    public:
+        GeneratorRandomiser( Generator<T>&& baseGenerator, size_t numberOfItems )
+        :   m_baseGenerator( std::move( baseGenerator ) ),
+            m_indices( randomiseIndices( numberOfItems, m_baseGenerator.size() ) )
+        {}
+
+        auto get( size_t index ) const -> T override {
+            return m_baseGenerator[m_indices[index]];
+        }
+    };
+
+    template<typename T>
+    struct RequiresASpecialisationFor;
+
+    template<typename T>
+    auto all() -> Generator<T> { return RequiresASpecialisationFor<T>(); }
+
+
+    template<typename T>
+    auto range( T const& first, T const& last ) -> Generator<T> {
+        return Generator<T>( (last-first), pf::make_unique<RangeGenerator<T>>( first, last ) );
+    }
+    template<>
+    inline auto all<int>() -> Generator<int> {
+        return range( std::numeric_limits<int>::min(), std::numeric_limits<int>::max()-1 );
+    }
+
+
+    template<typename T>
+    auto random( T const& first, T const& last ) -> Generator<T> {
+        auto gen = range( first, last );
+        auto size = gen.size();
+
+        return Generator<T>( size, pf::make_unique<GeneratorRandomiser<T>>( std::move( gen ), size ) );
+    }
+    template<typename T>
+    auto random( size_t size ) -> Generator<T> {
+        return Generator<T>( size, pf::make_unique<GeneratorRandomiser<T>>( all<T>(), size ) );
+    }
+
+    template<typename T>
+    auto values( std::initializer_list<T> values ) -> Generator<T> {
+        return Generator<T>( values.size(), pf::make_unique<FixedValuesGenerator<T>>( values ) );
+    }
+    template<typename T>
+    auto value( T const& val ) -> Generator<T> {
+        return Generator<T>( 1, pf::make_unique<SingleValueGenerator<T>>( val ) );
+    }
+
+    template<typename T>
+    auto as() -> Generator<T> {
+        return Generator<T>( 0, pf::make_unique<NullGenerator<T>>() );
+    }
+
+    template<typename... Ts>
+    auto table( std::initializer_list<std::tuple<Ts...>>&& tuples ) -> Generator<std::tuple<Ts...>> {
+        return values<std::tuple<Ts...>>( std::forward<std::initializer_list<std::tuple<Ts...>>>( tuples ) );
+    }
+
+
+    template<typename T>
+    struct Generators : GeneratorBase {
+        std::vector<Generator<T>> m_generators;
+
+        using type = T;
+
+        Generators() : GeneratorBase( 0 ) {}
+
+        void populate( T&& val ) {
+            m_size += 1;
+            m_generators.emplace_back( value( std::move( val ) ) );
+        }
+        template<typename U>
+        void populate( U&& val ) {
+            populate( T( std::move( val ) ) );
+        }
+        void populate( Generator<T>&& generator ) {
+            m_size += generator.size();
+            m_generators.emplace_back( std::move( generator ) );
+        }
+
+        template<typename U, typename... Gs>
+        void populate( U&& valueOrGenerator, Gs... moreGenerators ) {
+            populate( std::forward<U>( valueOrGenerator ) );
+            populate( std::forward<Gs>( moreGenerators )... );
+        }
+
+        auto operator[]( size_t index ) const -> T {
+            size_t sizes = 0;
+            for( auto const& gen : m_generators ) {
+                auto localIndex = index-sizes;
+                sizes += gen.size();
+                if( index < sizes )
+                    return gen[localIndex];
+            }
+            throw std::out_of_range("index out of range");
+        }
+    };
+
+    template<typename T, typename... Gs>
+    auto makeGenerators( Generator<T>&& generator, Gs... moreGenerators ) -> Generators<T> {
+        Generators<T> generators;
+        generators.m_generators.reserve( 1+sizeof...(Gs) );
+        generators.populate( std::move( generator ), std::forward<Gs>( moreGenerators )... );
+        return generators;
+    }
+    template<typename T>
+    auto makeGenerators( Generator<T>&& generator ) -> Generators<T> {
+        Generators<T> generators;
+        generators.populate( std::move( generator ) );
+        return generators;
+    }
+    template<typename T, typename... Gs>
+    auto makeGenerators( T&& val, Gs... moreGenerators ) -> Generators<T> {
+        return makeGenerators( value( std::forward<T>( val ) ), std::forward<Gs>( moreGenerators )... );
+    }
+    template<typename T, typename U, typename... Gs>
+    auto makeGenerators( U&& val, Gs... moreGenerators ) -> Generators<T> {
+        return makeGenerators( value( T( std::forward<U>( val ) ) ), std::forward<Gs>( moreGenerators )... );
+    }
+
+
+    auto acquireGeneratorTracker( SourceLineInfo const& lineInfo ) -> IGeneratorTracker&;
+
+    template<typename L>
+    // Note: The type after -> is weird, because VS2015 cannot parse
+    //       the expression used in the typedef inside, when it is in
+    //       return type. Yeah, ¯\_(ツ)_/¯
+    auto generate( SourceLineInfo const& lineInfo, L const& generatorExpression ) -> decltype(std::declval<decltype(generatorExpression())>()[0]) {
+        using UnderlyingType = typename decltype(generatorExpression())::type;
+
+        IGeneratorTracker& tracker = acquireGeneratorTracker( lineInfo );
+        if( !tracker.hasGenerator() )
+            tracker.setGenerator( pf::make_unique<Generators<UnderlyingType>>( generatorExpression() ) );
+
+        auto const& generator = static_cast<Generators<UnderlyingType> const&>( *tracker.getGenerator() );
+        return generator[tracker.getIndex()];
+    }
+
+} // namespace Generators
+} // namespace Catch
+
+#define GENERATE( ... ) \
+    Catch::Generators::generate( CATCH_INTERNAL_LINEINFO, []{ using namespace Catch::Generators; return makeGenerators( __VA_ARGS__ ); } )
+
+
+#endif // TWOBLUECUBES_CATCH_GENERATORS_HPP_INCLUDED
diff --git a/include/internal/catch_interfaces_capture.h b/include/internal/catch_interfaces_capture.h
index 4d091f89..950d498d 100644
--- a/include/internal/catch_interfaces_capture.h
+++ b/include/internal/catch_interfaces_capture.h
@@ -24,8 +24,10 @@ namespace Catch {
     struct BenchmarkInfo;
     struct BenchmarkStats;
     struct AssertionReaction;
+    struct SourceLineInfo;
 
     struct ITransientExpression;
+    struct IGeneratorTracker;
 
     struct IResultCapture {
 
@@ -36,6 +38,8 @@ namespace Catch {
         virtual void sectionEnded( SectionEndInfo const& endInfo ) = 0;
         virtual void sectionEndedEarly( SectionEndInfo const& endInfo ) = 0;
 
+        virtual auto acquireGeneratorTracker( SourceLineInfo const& lineInfo ) -> IGeneratorTracker& = 0;
+
         virtual void benchmarkStarting( BenchmarkInfo const& info ) = 0;
         virtual void benchmarkEnded( BenchmarkStats const& stats ) = 0;
 
diff --git a/include/internal/catch_interfaces_generatortracker.h b/include/internal/catch_interfaces_generatortracker.h
new file mode 100644
index 00000000..2cf6269e
--- /dev/null
+++ b/include/internal/catch_interfaces_generatortracker.h
@@ -0,0 +1,39 @@
+/*
+ *  Created by Phil Nash on 26/6/2018.
+ *
+ *  Distributed under the Boost Software License, Version 1.0. (See accompanying
+ *  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#ifndef TWOBLUECUBES_CATCH_INTERFACES_GENERATORTRACKER_INCLUDED
+#define TWOBLUECUBES_CATCH_INTERFACES_GENERATORTRACKER_INCLUDED
+
+#include <memory>
+
+namespace Catch {
+
+    namespace Generators {
+        class GeneratorBase {
+        protected:
+            size_t m_size = 0;
+
+        public:
+            GeneratorBase( size_t size ) : m_size( size ) {}
+            virtual ~GeneratorBase();
+            auto size() const -> size_t { return m_size; }
+        };
+        using GeneratorBasePtr = std::unique_ptr<GeneratorBase>;
+
+    } // namespace Generators
+
+    struct IGeneratorTracker {
+        virtual ~IGeneratorTracker();
+        virtual auto hasGenerator() const -> bool = 0;
+        virtual auto getGenerator() const -> Generators::GeneratorBasePtr const& = 0;
+        virtual void setGenerator( Generators::GeneratorBasePtr&& generator ) = 0;
+        virtual auto getIndex() const -> std::size_t = 0;
+    };
+
+} // namespace Catch
+
+#endif //TWOBLUECUBES_CATCH_INTERFACES_GENERATORTRACKER_INCLUDED
diff --git a/include/internal/catch_run_context.cpp b/include/internal/catch_run_context.cpp
index ecaa34db..2739284c 100644
--- a/include/internal/catch_run_context.cpp
+++ b/include/internal/catch_run_context.cpp
@@ -11,6 +11,70 @@
 
 namespace Catch {
 
+    namespace Generators {
+        struct GeneratorTracker : TestCaseTracking::TrackerBase, IGeneratorTracker {
+            size_t m_index = static_cast<size_t>( -1 );
+            GeneratorBasePtr m_generator;
+
+            GeneratorTracker( TestCaseTracking::NameAndLocation const& nameAndLocation, TrackerContext& ctx, ITracker* parent )
+            :   TrackerBase( nameAndLocation, ctx, parent )
+            {}
+            ~GeneratorTracker();
+
+            static GeneratorTracker& acquire( TrackerContext& ctx, TestCaseTracking::NameAndLocation const& nameAndLocation ) {
+                std::shared_ptr<GeneratorTracker> tracker;
+
+                ITracker& currentTracker = ctx.currentTracker();
+                if( TestCaseTracking::ITrackerPtr childTracker = currentTracker.findChild( nameAndLocation ) ) {
+                    assert( childTracker );
+                    assert( childTracker->isIndexTracker() );
+                    tracker = std::static_pointer_cast<GeneratorTracker>( childTracker );
+                }
+                else {
+                    tracker = std::make_shared<GeneratorTracker>( nameAndLocation, ctx, &currentTracker );
+                    currentTracker.addChild( tracker );
+                }
+
+                if( !ctx.completedCycle() && !tracker->isComplete() ) {
+                    if( tracker->m_runState != ExecutingChildren && tracker->m_runState != NeedsAnotherRun )
+                        tracker->moveNext();
+                    tracker->open();
+                }
+
+                return *tracker;
+            }
+
+            void moveNext() {
+                m_index++;
+                m_children.clear();
+            }
+
+            // TrackerBase interface
+            bool isIndexTracker() const override { return true; }
+            auto hasGenerator() const -> bool override {
+                return !!m_generator;
+            }
+            void close() override {
+                TrackerBase::close();
+                if( m_runState == CompletedSuccessfully && m_index < m_generator->size()-1 )
+                    m_runState = Executing;
+            }
+
+            // IGeneratorTracker interface
+            auto getGenerator() const -> GeneratorBasePtr const& override {
+                return m_generator;
+            }
+            void setGenerator( GeneratorBasePtr&& generator ) override {
+                m_generator = std::move( generator );
+            }
+            auto getIndex() const -> size_t override {
+                return m_index;
+            }
+        };
+        GeneratorTracker::~GeneratorTracker() {}
+    }
+
+
     RunContext::RunContext(IConfigPtr const& _config, IStreamingReporterPtr&& reporter)
     :   m_runInfo(_config->name()),
         m_context(getCurrentMutableContext()),
@@ -128,6 +192,13 @@ namespace Catch {
 
         return true;
     }
+    auto RunContext::acquireGeneratorTracker( SourceLineInfo const& lineInfo ) -> IGeneratorTracker& {
+        using namespace Generators;
+        GeneratorTracker& tracker = GeneratorTracker::acquire( m_trackerContext, TestCaseTracking::NameAndLocation( "generator", lineInfo ) );
+        assert( tracker.isOpen() );
+        m_lastAssertionInfo.lineInfo = lineInfo;
+        return tracker;
+    }
 
     bool RunContext::testForMissingAssertions(Counts& assertions) {
         if (assertions.total() != 0)
diff --git a/include/internal/catch_run_context.h b/include/internal/catch_run_context.h
index 6b894173..952ef147 100644
--- a/include/internal/catch_run_context.h
+++ b/include/internal/catch_run_context.h
@@ -8,6 +8,7 @@
 #ifndef TWOBLUECUBES_CATCH_RUNNER_IMPL_HPP_INCLUDED
 #define TWOBLUECUBES_CATCH_RUNNER_IMPL_HPP_INCLUDED
 
+#include "catch_interfaces_generatortracker.h"
 #include "catch_interfaces_runner.h"
 #include "catch_interfaces_reporter.h"
 #include "catch_interfaces_exception.h"
@@ -79,6 +80,8 @@ namespace Catch {
         void sectionEnded( SectionEndInfo const& endInfo ) override;
         void sectionEndedEarly( SectionEndInfo const& endInfo ) override;
 
+        auto acquireGeneratorTracker( SourceLineInfo const& lineInfo ) -> IGeneratorTracker& override;
+
         void benchmarkStarting( BenchmarkInfo const& info ) override;
         void benchmarkEnded( BenchmarkStats const& stats ) override;
 
diff --git a/include/internal/catch_test_case_tracker.cpp b/include/internal/catch_test_case_tracker.cpp
index c6759438..7839a71b 100644
--- a/include/internal/catch_test_case_tracker.cpp
+++ b/include/internal/catch_test_case_tracker.cpp
@@ -69,14 +69,6 @@ namespace TestCaseTracking {
     }
 
 
-
-    TrackerBase::TrackerHasName::TrackerHasName( NameAndLocation const& nameAndLocation ) : m_nameAndLocation( nameAndLocation ) {}
-    bool TrackerBase::TrackerHasName::operator ()( ITrackerPtr const& tracker ) const {
-        return
-            tracker->nameAndLocation().location == m_nameAndLocation.location &&
-            tracker->nameAndLocation().name == m_nameAndLocation.name;
-    }
-
     TrackerBase::TrackerBase( NameAndLocation const& nameAndLocation, TrackerContext& ctx, ITracker* parent )
     :   m_nameAndLocation( nameAndLocation ),
         m_ctx( ctx ),
@@ -105,7 +97,12 @@ namespace TestCaseTracking {
     }
 
     ITrackerPtr TrackerBase::findChild( NameAndLocation const& nameAndLocation ) {
-        auto it = std::find_if( m_children.begin(), m_children.end(), TrackerHasName( nameAndLocation ) );
+        auto it = std::find_if( m_children.begin(), m_children.end(),
+            [&nameAndLocation]( ITrackerPtr const& tracker ){
+                return
+                    tracker->nameAndLocation().location == nameAndLocation.location &&
+                    tracker->nameAndLocation().name == nameAndLocation.name;
+            } );
         return( it != m_children.end() )
             ? *it
             : nullptr;
diff --git a/include/internal/catch_test_case_tracker.h b/include/internal/catch_test_case_tracker.h
index a4b0440a..72b506a9 100644
--- a/include/internal/catch_test_case_tracker.h
+++ b/include/internal/catch_test_case_tracker.h
@@ -95,13 +95,6 @@ namespace TestCaseTracking {
             Failed
         };
 
-        class TrackerHasName {
-            NameAndLocation m_nameAndLocation;
-        public:
-            TrackerHasName( NameAndLocation const& nameAndLocation );
-            bool operator ()( ITrackerPtr const& tracker ) const;
-        };
-
         using Children = std::vector<ITrackerPtr>;
         NameAndLocation m_nameAndLocation;
         TrackerContext& m_ctx;