diff options
Diffstat (limited to 'src/qdoc/catch_generators/src')
12 files changed, 1839 insertions, 0 deletions
diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/combinators/cycle_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/combinators/cycle_generator.h new file mode 100644 index 000000000..b60600747 --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/combinators/cycle_generator.h @@ -0,0 +1,80 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" +#include "../../utilities/semantics/generator_handler.h" + +#include <catch/catch.hpp> + +#include <vector> + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + template<typename T> + class CycleGenerator : public Catch::Generators::IGenerator<T> { + public: + CycleGenerator(Catch::Generators::GeneratorWrapper<T>&& generator) + : generator{std::move(generator)}, + cache{}, + cache_index{0} + { + // REMARK: We generally handle extracting the first + // value by using an handler, to avoid code + // duplication and the possibility of an error. + // In this specific case, we turn to a more "manual" + // approach as it better models the cache-based + // implementation, removing the need to not increment + // cache_index the first time that next is called. + cache.emplace_back(this->generator.get()); + } + + T const& get() const override { return cache[cache_index]; } + + bool next() override { + if (generator.next()) { + cache.emplace_back(generator.get()); + ++cache_index; + } else { + cache_index = (cache_index + 1) % cache.size(); + } + + return true; + } + + private: + Catch::Generators::GeneratorWrapper<T> generator; + + std::vector<T> cache; + std::size_t cache_index; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + /*! + * Returns a generator that behaves like \a generator until \a + * generator is exhausted, repeating the same generation that \a + * generator produced, infinitely, afterwards. + * + * This is generally intended to produce infinite generators from + * finite ones. + * + * For example, consider a generator that produces values based on + * another generator that it owns. + * If the owning generator needs to produce more values that the + * owned generator can support, it might fail at some point. + * By cycling over the owned generator, we can extend the sequence + * of produced values so that enough are generated, in a controlled + * way. + * + * The type T should generally be copyable for this generator to + * work. + */ + template<typename T> + inline Catch::Generators::GeneratorWrapper<T> cycle(Catch::Generators::GeneratorWrapper<T>&& generator) { + return Catch::Generators::GeneratorWrapper<T>(std::unique_ptr<Catch::Generators::IGenerator<T>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::CycleGenerator(std::move(generator)))); + } + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/combinators/oneof_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/combinators/oneof_generator.h new file mode 100644 index 000000000..5de9dcb6c --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/combinators/oneof_generator.h @@ -0,0 +1,185 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" +#include "../../utilities/statistics/percentages.h" +#include "../../utilities/semantics/generator_handler.h" + +#include <catch/catch.hpp> + +#include <vector> +#include <random> +#include <algorithm> +#include <numeric> + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + template<typename T> + class OneOfGenerator : public Catch::Generators::IGenerator<T> { + public: + OneOfGenerator( + std::vector<Catch::Generators::GeneratorWrapper<T>>&& generators, + const std::vector<double>& weights + ) : generators{std::move(generators)}, + random_engine{std::random_device{}()}, + choice_distribution{weights.cbegin(), weights.cend()} + { + assert(weights.size() == this->generators.size()); + assert(std::reduce(weights.cbegin(), weights.cend()) == Approx(100.0)); + + std::transform( + this->generators.begin(), this->generators.end(), this->generators.begin(), + [](auto& generator){ return QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(generator)); } + ); + + static_cast<void>(next()); + } + + T const& get() const override { return current_value; } + + bool next() override { + std::size_t generator_index{choice_distribution(random_engine)}; + + if (!generators[generator_index].next()) return false; + current_value = generators[generator_index].get(); + + return true; + } + + private: + std::vector<Catch::Generators::GeneratorWrapper<T>> generators; + + std::mt19937 random_engine; + std::discrete_distribution<std::size_t> choice_distribution; + + T current_value; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + /*! + * Returns a generator whose set of elements is the union of the + * set of elements of the generators in \a generators. + * + * Each time the generator produces a value, a generator from \a + * generators is randomly chosen to produce the value. + * + * The distribution for the choice is given by \a weights. + * The \e {ith} element in \a weights represent the percentage + * probability of the \e {ith} element of \a generators to be + * chosen. + * + * It follows that the size of \a weights must be the same as the + * size of \a generators. + * + * Furthermore, the sum of elements in \a weights should be a + * hundred. + * + * The generator produces values until a generator that is chosen + * to produce a value is unable to do so. + * The first such generator to do so will stop the generation + * independently of the availability of the other generators. + * + * Similarly, values will be produced as long as the chosen + * generator can produce a value, independently of the other + * generators being exhausted already. + */ + template<typename T> + inline Catch::Generators::GeneratorWrapper<T> oneof( + std::vector<Catch::Generators::GeneratorWrapper<T>>&& generators, + const std::vector<double>& weights + ) { + return Catch::Generators::GeneratorWrapper<T>(std::unique_ptr<Catch::Generators::IGenerator<T>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::OneOfGenerator(std::move(generators), weights))); + } + + + /*! + * Returns a generator whose set of elements is the union of the + * set of elements of the generators in \a generators and in which + * the distribution of the generated elements is uniform over \a + * generators. + * + * Each time the generator produces a value, a generator from \a + * generators is randomly chosen to produce the value. + * + * Each generator from \a generators has the same chance of being + * chosen. + * + * Do note that the distribution over the set of values is not + * necessarily uniform. + * + * The generator produces values until a generator that is chosen + * to produce a value is unable to do so. + * The first such generator to do so will stop the generation + * independently of the availability of the other generators. + * + * Similarly, values will be produced as long as the chosen + * generator can produce a value, independently of the other + * generators being exhausted already. + */ + template<typename T> + inline Catch::Generators::GeneratorWrapper<T> uniform_oneof( + std::vector<Catch::Generators::GeneratorWrapper<T>>&& generators + ) { + std::vector<double> weights( + generators.size(), + QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::uniform_probability(generators.size()) + ); + return oneof(std::move(generators), std::move(weights)); + } + + /*! + * Returns a generator whose set of elements is the union of the + * set of elements of the generators in \a generators and in which + * the distribution of the generated elements is uniform over the + * elements of \a generators. + * + * The generators in \a generator should have a uniform + * distribution and be finite. + * If the set of elements that the generators in \a generator is + * not disjoint, the distribution will be skewed towards repeated + * elements. + * + * Each time the generator produces a value, a generator from \a + * generators is randomly chosen to produce the value. + * + * Each generator from \a generators has a probability of being + * chosen based on the proportion of the cardinality of the subset + * it produces. + * + * The \e {ith} element of \a amounts should contain the + * cardinality of the set produced by the \e {ith} generator in \a + * generators. + * + * The generator produces values until a generator that is chosen + * to produce a value is unable to do so. + * The first such generator to do so will stop the generation + * independently of the availability of the other generators. + * + * Similarly, values will be produced as long as the chosen + * generator can produce a value, independently of the other + * generators being exhausted already. + */ + template<typename T> + inline Catch::Generators::GeneratorWrapper<T> uniformly_valued_oneof( + std::vector<Catch::Generators::GeneratorWrapper<T>>&& generators, + const std::vector<std::size_t>& amounts + ) { + std::size_t total_amount{std::accumulate(amounts.cbegin(), amounts.cend(), std::size_t{0})}; + + std::vector<double> weights; + weights.reserve(amounts.size()); + + std::transform( + amounts.cbegin(), amounts.cend(), + std::back_inserter(weights), + [total_amount](auto element){ return QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::percent_of(static_cast<double>(element), static_cast<double>(total_amount)); } + ); + + return oneof(std::move(generators), std::move(weights)); + } + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/k_partition_of_r_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/k_partition_of_r_generator.h new file mode 100644 index 000000000..832ee2838 --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/k_partition_of_r_generator.h @@ -0,0 +1,113 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../namespaces.h" + +#include <catch/catch.hpp> + +#include <random> +#include <numeric> +#include <algorithm> + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + class KPartitionOfRGenerator : public Catch::Generators::IGenerator<std::vector<double>> { + public: + KPartitionOfRGenerator(double r, std::size_t k) + : random_engine{std::random_device{}()}, + interval_distribution{0.0, r}, + k{k}, + r{r}, + current_partition(k) + { + assert(r >= 0.0); + assert(k >= 1); + + static_cast<void>(next()); + } + + std::vector<double> const& get() const override { return current_partition; } + + bool next() override { + if (k == 1) current_partition[0] = r; + else { + // REMARK: The following wasn't formally proved + // but is based on intuition. + // It is probably erroneous but is expected to be + // good enough for our case. + + // REMARK: We aim to provide a non skewed + // distribution for the elements of the partition. + // + // The reasoning for this is to ensure that our + // testing surface has a good chance of hitting + // many of the available elements between the many + // runs. + // + // To approximate this, a specific algorithm was chosen. + // The following code can be intuitively seen as doing the following: + // + // Consider an interval [0.0, r] on the real line, where r > 0.0. + // + // k - 1 > 0 elements of the interval are chosen, + // partitioning the interval into disjoint + // sub-intervals. + // + // --------------------------------------------------------------------------------------------------------------------- + // | | | | | + // 0 k_1 k_2 k_3 r + // | | | | | + // _______--------------------_______________________________________________________----------------------------------- + // k_1 - 0 k_2 - k_1 k_3 - k_2 r - k_3 + // p1 p2 p3 p4 + // + // The length of each sub interval is chosen as one of the elements of the partition. + // + // Trivially, the sum of the chosen elements is r. + // + // Furthermore, as long as the distribution used + // to choose the elements of the original interval + // is uniform, the probability of each partition + // being produced should tend to being uniform + // itself. + std::generate(current_partition.begin(), current_partition.end() - 1, [this](){ return interval_distribution(random_engine); }); + + current_partition.back() = r; + + std::sort(current_partition.begin(), current_partition.end()); + std::adjacent_difference(current_partition.begin(), current_partition.end(), current_partition.begin()); + } + + return true; + } + + private: + std::mt19937 random_engine; + std::uniform_real_distribution<double> interval_distribution; + + std::size_t k; + double r; + + std::vector<double> current_partition; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + /*! + * Returns a generator that generates collections of \a k elements + * whose sum is \a r. + * + * \a r must be a real number greater or euqal to zero and \a k + * must be a natural number greater than zero. + * + * The generated partitions tends to be uniformely distributed + * over the set of partitions of r. + */ + inline Catch::Generators::GeneratorWrapper<std::vector<double>> k_partition_of_r(double r, std::size_t k) { + return Catch::Generators::GeneratorWrapper<std::vector<double>>(std::unique_ptr<Catch::Generators::IGenerator<std::vector<double>>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::KPartitionOfRGenerator(r, k))); + } + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/path_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/path_generator.h new file mode 100644 index 000000000..875502e49 --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/path_generator.h @@ -0,0 +1,853 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +// TODO: Change the include paths to implicitly consider +// `catch_generators` a root directory and change the CMakeLists.txt +// file to make this possible. + +#include "../namespaces.h" +#include "qchar_generator.h" +#include "qstring_generator.h" +#include "../utilities/semantics/move_into_vector.h" +#include "../utilities/semantics/generator_handler.h" + +#if defined(Q_OS_WINDOWS) + + #include "combinators/cycle_generator.h" + +#endif + +#include <catch/catch.hpp> + +#include <random> + +#include <QChar> +#include <QString> +#include <QStringList> +#include <QRegularExpression> + +#if defined(Q_OS_WINDOWS) + + #include <QStorageInfo> + +#endif + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + + + struct PathGeneratorConfiguration { + double multi_device_path_probability{0.5}; + double absolute_path_probability{0.5}; + double directory_path_probability{0.5}; + double has_trailing_separator_probability{0.5}; + std::size_t minimum_components_amount{1}; + std::size_t maximum_components_amount{10}; + + PathGeneratorConfiguration& set_multi_device_path_probability(double amount) { + multi_device_path_probability = amount; + return *this; + } + + PathGeneratorConfiguration& set_absolute_path_probability(double amount) { + absolute_path_probability = amount; + return *this; + } + + PathGeneratorConfiguration& set_directory_path_probability(double amount) { + directory_path_probability = amount; + return *this; + } + + PathGeneratorConfiguration& set_has_trailing_separator_probability(double amount) { + has_trailing_separator_probability = amount; + return *this; + } + + PathGeneratorConfiguration& set_minimum_components_amount(std::size_t amount) { + minimum_components_amount = amount; + return *this; + } + + PathGeneratorConfiguration& set_maximum_components_amount(std::size_t amount) { + maximum_components_amount = amount; + return *this; + } + }; + + /*! + * \class PathGeneratorConfiguration + * \brief Defines some parameters to customize the generation of + * paths by a PathGenerator. + */ + + /*! + * \variable PathGeneratorConfiguration::multi_device_path_probability + * + * Every path produced by a PathGenerator configured with a + * mutli_device_path_probability of n has a probability of n to be + * \e {Multi-Device} and a probability of 1.0 - n to not be \a + * {Multi-Device}. + * + * multi_device_path_probability should be a value in the range [0.0, + * 1.0]. + */ + + /*! + * \variable PathGeneratorConfiguration::absolute_path_probability + * + * Every path produced by a PathGenerator configured with an + * absolute_path_probability of n has a probability of n to be \e + * {Absolute} and a probability of 1.0 - n to be \e {Relative}. + * + * absolute_path_probability should be a value in the range [0.0, + * 1.0]. + */ + + /*! + * \variable PathGeneratorConfiguration::directory_path_probability + * + * Every path produced by a PathGenerator configured with a + * directory_path_probability of n has a probability of n to be \e + * {To a Directory} and a probability of 1.0 - n to be \e {To a + * File}. + * + * directory_path_probability should be a value in the range [0.0, + * 1.0]. + */ + + /*! + * \variable PathGeneratorConfiguration::has_trailing_separator_probability + * + * Every path produced by a PathGenerator configured with an + * has_trailing_separator_probability of n has a probability of n + * to \e {Have a Trailing Separator} and a probability of 1.0 - n + * to not \e {Have a Trailing Separator}, when this is applicable. + * + * has_trailing_separator_probability should be a value in the + * range [0.0, 1.0]. + */ + + /*! + * \variable PathGeneratorConfiguration::minimum_components_amount + * + * Every path produced by a PathGenerator configured with a + * minimum_components_amount of n will be the concatenation of at + * least n non \e {device}, non \e {root}, non \e {separator} + * components. + * + * minimum_components_amount should be greater than zero and less + * than maximum_components_amount. + */ + + /*! + * \variable PathGeneratorConfiguration::maximum_components_amount + * + * Every path produced by a PathGenerator configured with a + * maximum_components_amount of n will be the concatenation of at + * most n non \e {device}, non \e {root}, non \e {separator} components. + * + * maximum_components_amount should be greater than or equal to + * minimum_components_amount. + */ + + + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + class PathGenerator : public Catch::Generators::IGenerator<QString> { + public: + PathGenerator( + Catch::Generators::GeneratorWrapper<QString>&& device_component_generator, + Catch::Generators::GeneratorWrapper<QString>&& root_component_generator, + Catch::Generators::GeneratorWrapper<QString>&& directory_component_generator, + Catch::Generators::GeneratorWrapper<QString>&& filename_component_generator, + Catch::Generators::GeneratorWrapper<QString>&& separator_component_generator, + PathGeneratorConfiguration configuration = PathGeneratorConfiguration{} + ) : device_component_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(device_component_generator))}, + root_component_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(root_component_generator))}, + directory_component_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(directory_component_generator))}, + filename_component_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(filename_component_generator))}, + separator_component_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(separator_component_generator))}, + random_engine{std::random_device{}()}, + components_amount_distribution{configuration.minimum_components_amount, configuration.maximum_components_amount}, + is_multi_device_distribution{configuration.multi_device_path_probability}, + is_absolute_path_distribution{configuration.absolute_path_probability}, + is_directory_path_distribution{configuration.directory_path_probability}, + has_trailing_separator{configuration.has_trailing_separator_probability}, + current_path{} + { + assert(configuration.minimum_components_amount > 0); + assert(configuration.minimum_components_amount <= configuration.maximum_components_amount); + + if (!next()) + Catch::throw_exception("Not enough values to initialize the first string"); + } + + QString const& get() const override { return current_path; } + + bool next() override { + std::size_t components_amount{components_amount_distribution(random_engine)}; + + current_path = ""; + + // REMARK: As per our specification of a path, we + // do not count device components, and separators, + // when considering the amount of components in a + // path. + // This is a tradeoff that is not necessarily + // precise. + // Counting those kinds of components, on one + // hand, would allow a device component to stands + // on its own as a path, for example "C:", which + // might actually be correct in some path format. + // On the other hand, counting those kinds of + // components makes the construction of paths for + // our model much more complex with regards, for + // example, to the amount of component. + // + // Counting device components, since they can + // appear both in relative and absolute paths, + // makes the minimum amount of components + // different for different kinds of paths. + // + // Since absolute paths always require a root + // component, the minimum amount of components for + // a multi-device absolute path is 2. + // + // But an absolute path that is not multi-device + // would only require one minimum component. + // + // Similarly, problems arise with the existence of + // Windows' relative multi-device path, which + // require a leading separator component after a + // device component. + // + // This problem mostly comes from our model + // simplifying the definition of paths quite a bit + // into binary-forms. + // This simplifies the code and its structure, + // sacrificing some precision. + // The lost precision is almost none for POSIX + // based paths, but is graver for DOS paths, since + // they have a more complex specification. + // + // Currently, we expect that the paths that QDoc + // will encounter will mostly be in POSIX-like + // forms, even on Windows, and aim to support + // that, such that the simplification of code is + // considered a better tradeoff compared to the + // loss of precision. + // + // If this changes, the model should be changed to + // pursue a Windows-first modeling, moving the + // categorization of paths from the current binary + // model to the absolute, drive-relative and + // relative triptych that Windows uses. + // This more complex model should be able to + // completely describe posix paths too, making it + // a superior choice as long as the complexity is + // warranted. + // + // Do note that the model similarly can become + // inconsistent when used to generate format of + // paths such as the one used in some resource + // systems. + // Those are considered out-of-scope for our needs + // and were not taken into account when developing + // this generator. + if (is_multi_device_distribution(random_engine)) { + if (!device_component_generator.next()) return false; + current_path += device_component_generator.get(); + } + + // REMARK: Similarly to not counting other form of + // components, we do not count root components + // towards the amounts of components that the path + // has to simplify the code. + // To support the "special" root path on, for + // example, posix systems, we require a more + // complex branching logic that changes based on + // the path being absolute or not. + // + // We don't expect root to be a particularly + // useful path for QDoc purposes and expect to not + // have to consider it for our tests. + // If consideration for it become required, it is + // possible to test it directly in the affected + // systemss as a special case. + // + // If most systems are affected by the handling of + // a root path, then the model should be slightly + // changed to accommodate its generation. + if (is_absolute_path_distribution(random_engine)) { + if (!root_component_generator.next()) return false; + + current_path += root_component_generator.get(); + } + + std::size_t prefix_components_amount{std::max(std::size_t{1}, components_amount) - 1}; + while (prefix_components_amount > 0) { + if (!directory_component_generator.next()) return false; + if (!separator_component_generator.next()) return false; + + current_path += directory_component_generator.get() + separator_component_generator.get(); + --prefix_components_amount; + } + + if (is_directory_path_distribution(random_engine)) { + if (!directory_component_generator.next()) return false; + current_path += directory_component_generator.get(); + + if (has_trailing_separator(random_engine)) { + if (!separator_component_generator.next()) return false; + current_path += separator_component_generator.get(); + } + } else { + if (!filename_component_generator.next()) return false; + current_path += filename_component_generator.get(); + } + + return true; + } + + private: + Catch::Generators::GeneratorWrapper<QString> device_component_generator; + Catch::Generators::GeneratorWrapper<QString> root_component_generator; + Catch::Generators::GeneratorWrapper<QString> directory_component_generator; + Catch::Generators::GeneratorWrapper<QString> filename_component_generator; + Catch::Generators::GeneratorWrapper<QString> separator_component_generator; + + std::mt19937 random_engine; + std::uniform_int_distribution<std::size_t> components_amount_distribution; + std::bernoulli_distribution is_multi_device_distribution; + std::bernoulli_distribution is_absolute_path_distribution; + std::bernoulli_distribution is_directory_path_distribution; + std::bernoulli_distribution has_trailing_separator; + + QString current_path; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + +/*! + * Returns a generator that produces QStrings that represent a + * path in a filesystem. + * + * A path is formed by the following components, loosely based + * on the abstraction that is used by std::filesystem::path: + * + * \list + * \li \b {device}: + * Represents the device on the filesystem that + * the path should be considered in terms of. + * This is an optional components that is sometimes + * present on multi-device systems, such as Windows, to + * distinguish which device the path refers to. + * When present, it always appears before any other + * component. + * \li \b {root}: + * A special sequence that marks the path as absolute. + * This is an optional component that is present, always, + * in absolute paths. + * \li \b {directory}: + * A component that represents a directory on the + * filesystem that the path "passes-trough". + * Zero or more of this components can be present in the + * path. + * A path pointing to a directory on the filesystem that + * is not \e {root} always ends with a component of this + * type. + * \li \b {filename}: + * A component that represents a file on the + * filesystem. + * When this component is present, it is present only once + * and always as the last component of the path. + * A path that has such a component is a path that points + * to a file on the filesystem. + * For some path formats, there is no difference in the + * format of a \e {filename} and a \e {directory}. + * \li \b {separator}: + * A component that is interleaved between other types of + * components to separate them so that they are + * recognizable. + * A path that points to a directory on the filesystem may + * sometimes have a \e {separator} at the end, after the + * ending \e {directory} component. + * \endlist + * + * Each component is representable as a string and a path is a + * concatenation of the string representation of some + * components, with the following rules: + * + * \list + * \li There is at most one \e {device} component. + * \li If a \e {device} component is present it always + * precedes all other components. + * \li There is at most one \e {root} component. + * \li If a \e {root} component is present it: + * \list + * \li Succeeds the \e {device} component if it is present. + * \li Precedes every other components if the \e {device} + * component is not present. + * \endlist + * \li There are zero or more \e {directory} component. + * \li There is at most one \e {filename} component. + * \li If a \e {filename} component is present it always + * succeeds all other components. + * \li Between any two successive \e {directory} components + * there is a \e {separator} component. + * \li Between each successive \e {directory} and \e + * {filename} component there is a \e {separator} component. + * \li If the last component is a \e {directory} component it + * can be optionally followed by a \e {separator} component. + * \li At least one component that is not a \e {device}, a \e + * {root} or \e {separator} component is present. + * \endlist + * + * For example, if "C:" is a \e {device} component, "\\" is a + * \e {root} component, "\\" is a \e {separator} component, + * "directory" is a \e {directory} component and "filename" is + * a \e {filename} component, the following are all paths: + * + * "C:\\directory", "C:\\directory\\directory", "C:filename", + * "directory\\directory\\", "\\directory\\filename", "filename". + * + * While the following aren't: + * + * "C:", "C:\\", "directory\\C:", "foo", "C:filename\\", + * "filename\\directory\\filename", "filename\\filename", + * "directorydirectory"." + * + * The format of different components type can be the same. + * For example, the \e {root} and \e {separator} component in + * the above example. + * For the purpose of generation, we do not care about the + * format itself and consider a component of a certain type + * depending only on how it is generated/where it is generated + * from. + * + * For example, if every component is formatted as the string + * "a", the string "aaa" could be a generated path. + * By the string alone, it is not possible to simply discern + * which components form it, but it would be possible to + * generate it if the first "a" is a \a {device} component, + * the second "a" is a \e {root} component and the third "a" + * is a \e {directory} or \e {filename} component. + * + * A path, is further said to have some properties, pairs of + * which are exclusive to each other. + * + * A path is said to be: + * + * \list + * \li \b {Multi-Device}: + * When it contains a \e {device} component. + * \li \b {Absolute}: + * When it contains a \e {root} component. + * If the path is \e {Absolute} it is not \e {Relative}. + * \li \b {Relative}: + * When it does not contain a \e {root} component. + * If the path is \e {Relative} it is not \e {Absolute}. + * \li \b {To a Directory}: + * When its last component is a \e {directory} component + * or a \e {directory} component followed by a \e + * {separator} component. + * If the path is \e {To a Directory} it is not \e {To a + * File}. + * \li \b {To a File}: + * When its last component is a \e {filename}. + * If the path is \e {To a File} it is not \e {To a + * Directory}. + * \endlist + * + * All path are \e {Relative/Absolute}, \e {To a + * Directory/To a File} and \e {Multi-Device} or not. + * + * Furthermore, a path that is \e {To a Directory} and whose + * last component is a \e {separator} component is said to \e + * {Have a Trailing Separator}. + */ + inline Catch::Generators::GeneratorWrapper<QString> path( + Catch::Generators::GeneratorWrapper<QString>&& device_generator, + Catch::Generators::GeneratorWrapper<QString>&& root_component_generator, + Catch::Generators::GeneratorWrapper<QString>&& directory_generator, + Catch::Generators::GeneratorWrapper<QString>&& filename_generator, + Catch::Generators::GeneratorWrapper<QString>&& separator_generator, + PathGeneratorConfiguration configuration = PathGeneratorConfiguration{} + ) { + return Catch::Generators::GeneratorWrapper<QString>( + std::unique_ptr<Catch::Generators::IGenerator<QString>>( + new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::PathGenerator(std::move(device_generator), std::move(root_component_generator), std::move(directory_generator), std::move(filename_generator), std::move(separator_generator), configuration) + ) + ); + } + + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + // REMARK: We need a bounded length for the generation of path + // components as strings. + // We trivially do not want components to be the empty string, + // such that we have a minimum length of 1, but the maximum + // length is more malleable. + // We don't want components that are too long to avoid + // incurring in a big performance overhead, as we may generate + // many of them. + // At the same time, we want some freedom in having diffent + // length components. + // The value that was chosen is based on the general value for + // POSIX's NAME_MAX, which seems to tend to be 14 on many systems. + // We see this value as a small enough but not too much value + // that further brings with itself a relation to paths, + // increasing our portability even if it is out of scope, as + // almost no modern respects NAME_MAX. + // We don't use POSIX's NAME_MAX directly as it may not be available + // on all systems. + inline static constexpr std::size_t minimum_component_length{1}; + inline static constexpr std::size_t maximum_component_length{14}; + + /*! + * Returns a generator that generates strings that are + * suitable to be used as a root component in POSIX paths. + * + * As per + * \l {https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_02}, + * this is any sequence of slash characters that is not of + * length 2. + */ + inline Catch::Generators::GeneratorWrapper<QString> posix_root() { + return uniformly_valued_oneof( + QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::move_into_vector( + string(character('/', '/'), 1, 1), + string(character('/', '/'), 3, maximum_component_length) + ), + std::vector{1, maximum_component_length - 3} + ); + } + + /*! + * Returns a generator that generates strings that are + * suitable to be used as directory components in POSIX paths + * and that use an alphabet that should generally be supported + * by other systems. + * + * Components of this kind use the \l + * {https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_282}{Portable Filename Character Set}. + */ + inline Catch::Generators::GeneratorWrapper<QString> portable_posix_directory_name() { + return string( + QDOC_CATCH_GENERATORS_QCHAR_ALPHABETS_NAMESPACE::portable_posix_filename(), + minimum_component_length, maximum_component_length + ); + } + + /*! + * Returns a generator that generates strings that are + * suitable to be used as filenames in POSIX paths and that + * use an alphabet that should generally be supported by + * other systems. + * + * Filenames of this kind use the \l + * {https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_282}{Portable Filename Character Set}. + */ + inline Catch::Generators::GeneratorWrapper<QString> portable_posix_filename() { + // REMARK: "." and ".." always represent directories so we + // avoid generating them. Other than this, there is no + // difference between a file name and a directory name. + return filter([](auto& filename) { return filename != "." && filename != ".."; }, portable_posix_directory_name()); + } + + /*! + * Returns a generator that generates strings that can be used + * as POSIX compliant separators. + * + * As per \l + * {https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_271}, + * a separator is a sequence of one or more slashes. + */ + inline Catch::Generators::GeneratorWrapper<QString> posix_separator() { + return string(character('/', '/'), minimum_component_length, maximum_component_length); + } + + /*! + * Returns a generator that generates strings that can be + * suitably used as logical drive names in Windows' paths. + * + * As per \l + * {https://docs.microsoft.com/en-us/dotnet/standard/io/file-path-formats#traditional-dos-paths} + * and \l + * {https://docs.microsoft.com/en-us/windows/win32/api/fileapi/nf-fileapi-getlogicaldrives}, + * they are composed of a single letter. + * Each generated string always follows the lettet with a + * colon, as it is specifically intended for path usages, + * where this is required. + * + * We use only uppercase letters for the drives names albeit, + * depending on case sensitivity, lowercase letter could be + * used. + */ + inline Catch::Generators::GeneratorWrapper<QString> windows_logical_drives() { + // REMARK: If a Windows path is generated on Windows + // itself, we expect that it may be used to interact with + // the filesystem, similar to how we expect a POSIX path + // to be used on Linux. + // For this reason, we only generate a specific drive, the one + // that contains the current working directory, so that we + // know it is an actually available drive and to contain the + // possible modifications to the filesystem to an easily + // foundable place. + +#if defined(Q_OS_WINDOWS) + + auto root_device{QStorageInfo{QDir()}.rootPath().first(1) + ":"}; + + return cycle(Catch::Generators::value(std::move(root_device))); + +#else + + return Catch::Generators::map( + [](QString letter){ return letter + ':';}, + string(QDOC_CATCH_GENERATORS_QCHAR_ALPHABETS_NAMESPACE::ascii_uppercase(), 1, 1) + ); + +#endif + } + + /*! + * Returns a generator that generate strings that can be used + * as separators in Windows based paths. + * + * As per \l + * {https://docs.microsoft.com/en-us/dotnet/api/system.io.path.directoryseparatorchar?view=net-6.0} + * and \l + * {https://docs.microsoft.com/en-us/dotnet/standard/io/file-path-formats#canonicalize-separators}, + * this is a sequence of one or more backward or forward slashes. + */ + inline Catch::Generators::GeneratorWrapper<QString> windows_separator() { + return uniform_oneof( + QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::move_into_vector( + string(character('\\', '\\'), minimum_component_length, maximum_component_length), + string(character('/', '/'), minimum_component_length, maximum_component_length) + ) + ); + } + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + /*! + * Returns a generator that generates strings representing + * POSIX compatible paths. + * + * The generated paths follows the format specified in \l + * {https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_271}. + * + * The optional length-requirements, such as PATH_MAX and + * NAME_MAX, are relaxed away as they are generally not + * respected by modern systems. + * + * It is possible to set the probability of obtaining a + * relative or absolute path through \a + * absolute_path_probability and the one of obtaining a path + * potentially pointing ot a directory or on a file through \a + * directory_path_probability. + */ + inline Catch::Generators::GeneratorWrapper<QString> relaxed_portable_posix_path(double absolute_path_probability = 0.5, double directory_path_probability = 0.5) { + return path( + // POSIX path are never multi-device, so that we have + // provide an empty device component generator and set + // the probability for Multi-Device paths to zero. + string(character(), 0, 0), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::posix_root(), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::portable_posix_directory_name(), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::portable_posix_filename(), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::posix_separator(), + PathGeneratorConfiguration{} + .set_multi_device_path_probability(0.0) + .set_absolute_path_probability(absolute_path_probability) + .set_directory_path_probability(directory_path_probability) + ); + } + + /*! + * Returns a generator that produces strings that represents + * traditional DOS paths as defined in \l + * {https://docs.microsoft.com/en-us/dotnet/standard/io/file-path-formats#traditional-dos-paths}. + * + * The directory and filename components of a path generated + * in this way are, currently, restricted to use a portable + * character set as defined by POSIX. + * + * Do note that most paths themselves, will not be portable, on + * the whole, albeit they may be valid paths on other systems, as + * Windows uses a path system that is generally incompatible with + * other systems. + * + * Some possibly valid special path, such as a "C:" or "\" + * will never be generated. + */ + inline Catch::Generators::GeneratorWrapper<QString> traditional_dos_path( + double absolute_path_probability = 0.5, + double directory_path_probability = 0.5, + double multi_device_path_probability = 0.5 + ) { + return path( + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::windows_logical_drives(), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::windows_separator(), + // REMAKR: Windows treats trailing dots as if they were a + // component of their own, that is, as the special + // relative paths. + // This seems to not be correctly handled by Qt's + // filesystem methods, resulting in inconsistencies when + // one such path is encountered. + // To avoid the issue, considering that an equivalent path + // can be formed by actually having the dots on their own + // as a component, we filter out all those paths that have + // trailing dots but are not only composed of dots. + Catch::Generators::filter( + [](auto& path){ return !(path.endsWith(".") && path.contains(QRegularExpression("[^.]"))) ; }, + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::portable_posix_directory_name() + ), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::portable_posix_filename(), + QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::windows_separator(), + PathGeneratorConfiguration{} + .set_multi_device_path_probability(multi_device_path_probability) + .set_absolute_path_probability(absolute_path_probability) + .set_directory_path_probability(directory_path_probability) + ); + } + + // TODO: Find a good way to test the following functions. + // native_path can probably be tied to the tests for the + // OS-specific functions, with TEMPLATE_TEST_CASE. + // The other ones may follow a similar pattern but require a bit + // more work so that they tie to a specific case instead of the + // general one. + // Nonetheless, this approach is both error prone and difficult to + // parse, because of the required if preprocessor directives, + // and should be avoided if possible. + + /*! + * Returns a generator that generates QStrings that represents + * paths native to the underlying OS. + * + * On Windows, paths that refer to a drive always refer to the + * root drive. + * + * native* functions should always be chosen when using paths for + * testing interfacing with the filesystem itself. + * + * System outside Linux, macOS or Windows are not supported. + */ + inline Catch::Generators::GeneratorWrapper<QString> native_path(double absolute_path_probability = 0.5, double directory_path_probability = 0.5) { +#if defined(Q_OS_LINUX) || defined(Q_OS_MACOS) + + return relaxed_portable_posix_path(absolute_path_probability, directory_path_probability); + +#elif defined(Q_OS_WINDOWS) + + // REMARK: When generating native paths for testing we + // generally want to avoid relative paths that are + // drive-specific, as we want them to be tied to a specific + // working directory that may not be the current directory on + // the drive. + // Hence, we avoid generating paths that may have a drive component. + // For tests where those kind of paths are interesting, a + // specific Windows-only test should be made, using + // traditional_dos_path to generate drive-relative paths only. + return traditional_dos_path(absolute_path_probability, directory_path_probability, 0.0); + +#endif + } + + /*! + * Returns a generator that generates QStrings that represents + * paths native to the underlying OS and that are always \e + * {Relative}. + * + * Avoids generating paths that refer to a directory that is not + * included in the path itself. + * + * System outside Linux, macOS or Windows are not supported. + */ + inline Catch::Generators::GeneratorWrapper<QString> native_relative_path(double directory_path_probability = 0.5) { + // REMARK: When testing, we generally use some specific + // directory as a root for relative paths. + // We want the generated path to be relative to that + // directory because we need a clean state for the test to + // be reliable. + // When generating paths, it is possible, correctly, to + // have a path that refers to that directory or some + // parent of it, removing us from the clean state that we + // need. + // To avoid that, we filter out paths that end up referring to a directory that is not under our "root" directory. + // + // We can think of each generated component moving us + // further down or up, in case of "..", a directory + // hierarchy, or keeping us at the same place in case of + // ".". + // Any path that ends up under our original "root" + // directory will safely keep our clean state for testing. + // + // Each "." keeps us at the same level in the hierarchy. + // Each ".." moves us up one level in the hierarchy. + // Each component that is not "." or ".." moves us down + // one level into the hierarchy. + // + // Then, to avoid referring to the "root" directory or one + // of its parents, we need to balance out each "." and + // ".." with the components that precedes or follow their + // appearance. + // + // Since "." keeps us at the same level, it can appear how + // many times it wants as long as the path referes to the + // "root" directory or a directory or file under it and at + // least one other component referes to a directory or + // file that is under the "root" directory. + // + // Since ".." moves us one level up in the hierarchy, a + // sequence of n ".." components is safe when at least n + + // 1 non "." or ".." components appear before it. + // + // To avoid the above problem, we filter away paths that + // do not respect those rules. + return Catch::Generators::filter( + [](auto& path){ + QStringList components{path.split(QRegularExpression{R"((\\|\/)+)"}, Qt::SkipEmptyParts)}; + int depth{0}; + + for (auto& component : components) { + if (component == "..") + --depth; + else if (component != ".") + ++depth; + + if (depth < 0) return false; + } + + return (depth > 0); + }, + native_path(0.0, directory_path_probability) + ); + } + + /*! + * Returns a generator that generates QStrings that represents + * paths native to the underlying OS and that are always \e + * {Relative} and \e {To a File}. + * + * System outside Linux, macOS or Windows are not supported. + */ + inline Catch::Generators::GeneratorWrapper<QString> native_relative_file_path() { + return native_relative_path(0.0); + } + + /*! + * Returns a generator that generates QStrings that represents + * paths native to the underlying OS and that are always \e + * {Relative} and \e {To a Directory}. + * + * System outside Linux, macOS or Windows are not supported. + */ + inline Catch::Generators::GeneratorWrapper<QString> native_relative_directory_path() { + return native_relative_path(1.0); + } + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/qchar_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/qchar_generator.h new file mode 100644 index 000000000..33efc5ea4 --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/qchar_generator.h @@ -0,0 +1,110 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../namespaces.h" +#include "../utilities/semantics/move_into_vector.h" +#include "combinators/oneof_generator.h" + +#include <catch/catch.hpp> + +#include <random> + +#include <QChar> + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + class QCharGenerator : public Catch::Generators::IGenerator<QChar> { + public: + QCharGenerator( + char16_t lower_bound = std::numeric_limits<char16_t>::min(), + char16_t upper_bound = std::numeric_limits<char16_t>::max() + ) : random_engine{std::random_device{}()}, + distribution{static_cast<unsigned int>(lower_bound), static_cast<unsigned int>(upper_bound)} + { + assert(lower_bound <= upper_bound); + static_cast<void>(next()); + } + + QChar const& get() const override { return current_character; } + + bool next() override { + current_character = QChar(static_cast<char16_t>(distribution(random_engine))); + + return true; + } + + private: + QChar current_character; + + std::mt19937 random_engine; + std::uniform_int_distribution<unsigned int> distribution; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + + /*! + * Returns a generator of that generates elements of QChar whose + * ucs value is in the range [\a lower_bound, \a upper_bound]. + * + * When \a lower_bound = \a upper_bound, the generator infinitely + * generates the same character. + */ + inline Catch::Generators::GeneratorWrapper<QChar> character(char16_t lower_bound = std::numeric_limits<char16_t>::min(), char16_t upper_bound = std::numeric_limits<char16_t>::max()) { + return Catch::Generators::GeneratorWrapper<QChar>(std::unique_ptr<Catch::Generators::IGenerator<QChar>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QCharGenerator(lower_bound, upper_bound))); + } + + + namespace QDOC_CATCH_GENERATORS_QCHAR_ALPHABETS_NAMESPACE { + + namespace QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE { + + enum class Alphabets : std::size_t {digit, ascii_lowercase, ascii_uppercase, ascii_alpha, ascii_alphanumeric, portable_posix_filename}; + + template<Alphabets alphabet> + struct sizeof_alphabet; + + template<Alphabets alphabet> + inline constexpr std::size_t sizeof_alphabet_v = sizeof_alphabet<alphabet>::value; + + template <> struct sizeof_alphabet<Alphabets::digit> { static constexpr std::size_t value{'9' - '0'}; }; + template <> struct sizeof_alphabet<Alphabets::ascii_lowercase> { static constexpr std::size_t value{'z' - 'a'}; }; + template<> struct sizeof_alphabet<Alphabets::ascii_uppercase> { static constexpr std::size_t value{'Z' - 'A'}; }; + template<> struct sizeof_alphabet<Alphabets::ascii_alpha> { static constexpr std::size_t value{sizeof_alphabet_v<Alphabets::ascii_lowercase> + sizeof_alphabet_v<Alphabets::ascii_uppercase>}; }; + template<> struct sizeof_alphabet<Alphabets::ascii_alphanumeric>{ static constexpr std::size_t value{sizeof_alphabet_v<Alphabets::ascii_alpha> + sizeof_alphabet_v<Alphabets::digit>}; }; + + } // end QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE + + + inline Catch::Generators::GeneratorWrapper<QChar> digit() { + return Catch::Generators::GeneratorWrapper<QChar>(std::unique_ptr<Catch::Generators::IGenerator<QChar>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QCharGenerator('0', '9'))); + } + + inline Catch::Generators::GeneratorWrapper<QChar> ascii_lowercase() { + return Catch::Generators::GeneratorWrapper<QChar>(std::unique_ptr<Catch::Generators::IGenerator<QChar>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QCharGenerator('a', 'z'))); + } + + inline Catch::Generators::GeneratorWrapper<QChar> ascii_uppercase() { + return Catch::Generators::GeneratorWrapper<QChar>(std::unique_ptr<Catch::Generators::IGenerator<QChar>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QCharGenerator('A', 'Z'))); + } + + inline Catch::Generators::GeneratorWrapper<QChar> ascii_alpha() { + return uniform_oneof(QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::move_into_vector(ascii_lowercase(), ascii_uppercase())); + } + + inline Catch::Generators::GeneratorWrapper<QChar> ascii_alphanumeric() { + return uniformly_valued_oneof(QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::move_into_vector(ascii_alpha(), digit()), std::vector{traits::sizeof_alphabet_v<traits::Alphabets::ascii_alpha> , traits::sizeof_alphabet_v<traits::Alphabets::digit>}); + } + + inline Catch::Generators::GeneratorWrapper<QChar> portable_posix_filename() { + return uniformly_valued_oneof(QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::move_into_vector(ascii_alphanumeric(), character('.', '.'), character('-', '-'), character('_', '_')), + std::vector{traits::sizeof_alphabet_v<traits::Alphabets::ascii_alphanumeric>, std::size_t{1}, std::size_t{1}, std::size_t{1}}); + } + + } // end QDOC_CATCH_GENERATORS_QCHAR_ALPHABETS_NAMESPACE + + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/generators/qstring_generator.h b/src/qdoc/catch_generators/src/catch_generators/generators/qstring_generator.h new file mode 100644 index 000000000..fe854d22f --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/generators/qstring_generator.h @@ -0,0 +1,92 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../namespaces.h" +#include "qchar_generator.h" +#include "../utilities/semantics/generator_handler.h" + +#include <catch/catch.hpp> + +#include <random> + +#include <QString> + +namespace QDOC_CATCH_GENERATORS_ROOT_NAMESPACE { + namespace QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE { + + class QStringGenerator : public Catch::Generators::IGenerator<QString> { + public: + QStringGenerator(Catch::Generators::GeneratorWrapper<QChar>&& character_generator, qsizetype minimum_length, qsizetype maximum_length) + : character_generator{QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE::handler(std::move(character_generator))}, + random_engine{std::random_device{}()}, + length_distribution{minimum_length, maximum_length}, + current_string{} + { + assert(minimum_length >= 0); + assert(maximum_length >= 0); + assert(minimum_length <= maximum_length); + + if (!next()) + Catch::throw_exception("Not enough values to initialize the first string"); + } + + QString const& get() const override { return current_string; } + + bool next() override { + qsizetype length{length_distribution(random_engine)}; + + current_string = QString(); + for (qsizetype length_index{0}; length_index < length; ++length_index) { + if (!character_generator.next()) return false; + + current_string += character_generator.get(); + } + + return true; + } + + private: + Catch::Generators::GeneratorWrapper<QChar> character_generator; + + std::mt19937 random_engine; + std::uniform_int_distribution<qsizetype> length_distribution; + + QString current_string; + }; + + } // end QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE + + /*! + * Returns a generator that generates elements of QString from + * some amount of elements taken from \a character_generator. + * + * The generated strings will have a length in the range + * [\a minimum_length, \a maximum_length]. + * + * For compatibility with the Qt API, it is possible to provide + * negative bounds for the length. This is, nonetheless, + * considered an error such that the bounds should always be + * greater or equal to zero. + * + * It is similarly considered an error to have minimum_length <= + * maximum_length. + * + * The provided generator will generate elements until \a + * character_generator is exhausted. + */ + inline Catch::Generators::GeneratorWrapper<QString> string(Catch::Generators::GeneratorWrapper<QChar>&& character_generator, qsizetype minimum_length, qsizetype maximum_length) { + return Catch::Generators::GeneratorWrapper<QString>(std::unique_ptr<Catch::Generators::IGenerator<QString>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QStringGenerator(std::move(character_generator), minimum_length, maximum_length))); + } + + /*! + * Returns an infinite generator whose elements are the empty + * QString. + */ + inline Catch::Generators::GeneratorWrapper<QString> empty_string() { + return Catch::Generators::GeneratorWrapper<QString>(std::unique_ptr<Catch::Generators::IGenerator<QString>>(new QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::QStringGenerator(character(), 0, 0))); + } + + +} // end QDOC_CATCH_GENERATORS_ROOT_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/namespaces.h b/src/qdoc/catch_generators/src/catch_generators/namespaces.h new file mode 100644 index 000000000..3c956d44f --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/namespaces.h @@ -0,0 +1,14 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#define QDOC_CATCH_GENERATORS_ROOT_NAMESPACE qdoc::catch_generators + +#define QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE details + +#define QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE traits + +#define QDOC_CATCH_GENERATORS_QCHAR_ALPHABETS_NAMESPACE alphabets + +#define QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE QDOC_CATCH_GENERATORS_ROOT_NAMESPACE::QDOC_CATCH_GENERATORS_PRIVATE_NAMESPACE::utils diff --git a/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/copy_value.h b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/copy_value.h new file mode 100644 index 000000000..57798be1a --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/copy_value.h @@ -0,0 +1,26 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" + +#include <type_traits> + +namespace QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE { + + /*! + * Forces \value to be copied in an expression context. + * + * This is used in contexts where inferences of a type that + * requires generality might identify a reference when ownership + * is required. + * + * Note that the compiler might optmize the copy away. This is a + * non-issue as we are only interested in breaking lifetime + * dependencies. + */ + template<typename T> + std::remove_reference_t<T> copy_value(T value) { return value; } + +} // end QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/generator_handler.h b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/generator_handler.h new file mode 100644 index 000000000..328627512 --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/generator_handler.h @@ -0,0 +1,97 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" + +#include <catch/catch.hpp> + +#include <optional> +#include <cassert> + +namespace QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE { + + template<typename T> + class GeneratorHandler : public Catch::Generators::IGenerator<T> { + public: + + GeneratorHandler(Catch::Generators::GeneratorWrapper<T>&& generator) + : generator{std::move(generator)}, + first_call{true} + {} + + T const& get() const override { + assert(!first_call); + return generator.get(); + } + + bool next() override { + if (first_call) { + first_call = false; + return true; + } + + return generator.next(); + } + + private: + Catch::Generators::GeneratorWrapper<T> generator; + bool first_call; + }; + + + /*! + * Returns a generator wrapping \a generator that ensures that + * changes its semantics so that the first call to get should be + * preceded by a call to next. + * + * Catch generators require that is valid to call get and obtain a + * valid value on a generator that was just created. + * That is, generators should be non-empty and their first value + * should be initialized on construction. + * + * Normally, this is not a problem, and the next implementation of + * the generator can be simply called in the constructor. + * But when a generator depends on other generators, doing so will + * generally skip the first value that the generator + * produces, as the wrapping generator will need to advance the + * underlying generator, losing the value in the process. + * This is in particular, a problem, on generators that are finite + * or infinite and ordered. + * + * To solve the issue, the original value can be saved before + * advancing the generator or some code can be duplicated or + * abstracted so that what a new element can be generated without + * advancing the underlying generator. + * + * While this is acceptable, it can be error prone on more complex + * generators, generators that randomly access a collection of + * generators and so on. + * + * To simplify this process, this generator changes the semantics + * of the wrapped generator such that the first value of the + * generator is produced after the first call to next and the + * generator is considered in an invalid state before the first + * advancement. + * + * In this way, by wrapping all generators that a generator + * depends on, the implementation required for the first value is + * the same as the one required for all following values, with + * regards to the sequencing of next and get operations, + * simplifying the implementation of dependent generators. + * + * Do note that, while the generator returned by this function + * implments the generator interface that Catch2 requires, it + * cannot be normally used as a generator as it fails to comply + * with the first value semantics that a generator requires. + * Indeed, it should only be used as an intermediate wrapper for + * the implementation of generators that depends on other + * generators. + */ + template<typename T> + inline Catch::Generators::GeneratorWrapper<T> handler(Catch::Generators::GeneratorWrapper<T>&& generator) { + return Catch::Generators::GeneratorWrapper<T>(std::unique_ptr<Catch::Generators::IGenerator<T>>(new GeneratorHandler(std::move(generator)))); + } + +} // end QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/move_into_vector.h b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/move_into_vector.h new file mode 100644 index 000000000..5e780085b --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/utilities/semantics/move_into_vector.h @@ -0,0 +1,62 @@ +// Copyright (C) 2021 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" + +#include <vector> +#include <tuple> + +namespace QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE { + + namespace QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE { + + /*! + * Returns the type of the first element of Args. + * + * Args is expected to have at least one + */ + template<typename... Args> + using first_from_pack_t = std::tuple_element_t<0, std::tuple<Args...>>; + + } // end QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE + + + /*! + * Builds an std::vector by moving \a movables into it. + * + * \a movables must be made of homogenous types. + * + * This function is intended to allow the construction of an + * std::vector<T>, where T is a move only type, as an expression, + * to lighten the idiom. + * + * For example, Catch's GeneratorWrapper<T> adapts a + * std::unique_ptr, which is move only, making it impossible to + * build a std::vector from them in place. + * + * Then, everywhere this is needed, a more complex approach of + * generating the collection of objects, generating a vector of a + * suitable size and iterating the objects to move-emplace them in + * the vector is required. + * + * This not only complicates the code but is incompatible with a + * GENERATE expression, making it extremely hard, noisy and error + * prone to use them together. + * + * In those cases, then, a call to move_into_vector can be used as + * an expression to circumvent the problem. + */ + template<typename... MoveOnlyTypes> + inline auto move_into_vector(MoveOnlyTypes... movables) { + std::vector<QDOC_CATCH_GENERATORS_TRAITS_NAMESPACE::first_from_pack_t<MoveOnlyTypes...>> + moved_into_vector; + moved_into_vector.reserve(sizeof...(movables)); + + (moved_into_vector.emplace_back(std::move(movables)), ...); + + return moved_into_vector; + } + +} // end QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/distribution.h b/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/distribution.h new file mode 100644 index 000000000..4374993bf --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/distribution.h @@ -0,0 +1,158 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" + +#include <functional> +#include <optional> +#include <ostream> +#include <unordered_map> + +namespace QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE { + + template<typename T> + using Histogram = std::unordered_map<T, std::size_t>; + + template<typename InputIt, typename GroupBy> + auto make_histogram(InputIt begin, InputIt end, GroupBy&& group_by) { + Histogram<std::invoke_result_t<GroupBy, decltype(*begin)>> histogram{}; + + while (begin != end) { + auto key{std::invoke(std::forward<GroupBy>(group_by), *begin)}; + + histogram.try_emplace(key, 0); + histogram[key] += 1; + ++begin; + } + + return histogram; + } + + template<typename T> + struct DistributionError { + T value; + double probability; + double expected_probability; + }; + + template<typename T> + inline std::ostream& operator<<(std::ostream& os, const DistributionError<T>& error) { + return os << "DistributionError{" << + "The value { " << error.value << + " } appear with a probability of { " << error.probability << + " } while a probability of { " << error.expected_probability << " } was expected." << + "}"; + } + + // REMARK: The following should really return an Either of unit/error + // but std::variant in C++ is both extremely unusable and comes with a + // strong overhead unless certain conditions are met. + // For this reason, we keep to the less intutitive optional error. + + /*! + * Returns true when the given \a sequence approximately respects a + * given distribution. + * + * The \a sequence respects a given distribution when the count of + * each collection of values is a percentage of the total values that + * is near the percentage probability described by distribution. + * + * The values in \a sequence are collected according to \a group_by. + * \a group_by, given an element of \a sequence, should return a value + * of some type that represent the category of the inspected value. + * Values that have the same category share their count. + * + * The distribution that should be respected is given by \a + * probability_of. \a probability_of is a function that takes a + * category that was produced from a call to \a group_by and returns + * the expect probability, in percentage, of apperance for that + * category. + * + * The given probability is then compared to the one found by counting + * the element of \a sequence under \a group_by, to ensure that it + * matches. + * + * The margin of error for the comparison is given, in percentage + * points, by \a margin. + * The approximation uses an absolute comparison and scales the + * margin inversely based on the size of \a sequence, to account for the + * precision of the data set itself. + * + * When the distribution is not respected, a DistributionError is + * returned enclosed in an optional value. + * The error allows reports which the first category for which the + * comparison failed, along with its expected probability and the one + * that was actually inferred from \a sequence. + */ + template<typename T, typename GroupBy, typename ProbabilityOf> + std::optional<DistributionError<T>> respects_distribution(std::vector<T>&& sequence, GroupBy&& group_by, ProbabilityOf&& probability_of, double margin = 33) { + std::size_t data_point_amount{sequence.size()}; + + // REMARK: We scale the margin based on the data set to allow for + // an easier change in downstream tests. + // The precision required for the approximation will vary + // depending on how many values we generate. + // The amount of values we generate depends on how much time we + // want the tests to take. + // This amount may change in the future. For example, as code is + // added and tests are added, we might need some expensive + // computations here and there. + // Sometimes, this will increase the test suite runtime without an + // obvious way of improving the performance of the underlying code + // to reduce it. + // In those cases, the total run time can be decreased by running + // less generations for battle-tested tests. + // If some code has not been changed for a long time, it will have + // had thousands of generations by that point, giving us a good + // degree of certainty of it not being bugged (for whatever bugs + // the tests account for). + // Then, running a certain amount of generation is not required + // anymore such that some of them can be optimized out. + // For tests like the one using this function, where our ability + // to test is always dependent on the amount of generations, + // changing the generated amount will mean that we will need to + // change our conditions too, potentially changing the meaning of + // the test. + // To take this into account, we perform a scaling on the + // condition itself, so that if the amount of data points that are + // generated changes, we do not generally have to change anything + // in the condition. + // + // For this case, we scale logarithmically_10 for the simple + // reason that we tend to generate values in power of tens, + // starting with the 100 values default that Quickcheck used. + // + // The default value for the margin on which the scaling is based, + // was chosen heuristically. + // As we expect generation under 10^3 to be generally meaningless + // for this kind of testing, the value was chosen so that it would + // start to normalize around that amount. + // Deviation of about 5-10% were identified trough various + // generations for an amount of data points near 1000, while a + // deviation of about 1-3% was identified with about 10000 values. + // With the chosen default value, the scaling approaches those + // percentage points with some margin of error. + // + // We expect up to a 10%, or a bit more, deviation to be suitable + // for our purposes, as it would still allow for a varied + // distribution in downstream consumers. + double scaled_margin{margin * (1.0/std::log10(data_point_amount))}; + + auto histogram{make_histogram(sequence.begin(), sequence.end(), std::forward<GroupBy>(group_by))}; + + for (auto& bin : histogram) { + auto [key, count] = bin; + + double actual_percentage{percent_of(static_cast<double>(count), static_cast<double>(data_point_amount))}; + double expected_percentage{std::invoke(std::forward<ProbabilityOf>(probability_of), key)}; + + if (!(actual_percentage == Approx(expected_percentage).margin(scaled_margin))) + return std::make_optional(DistributionError<T>{key, actual_percentage, expected_percentage}); + } + + return std::nullopt; + } + +} // end QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE diff --git a/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/percentages.h b/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/percentages.h new file mode 100644 index 000000000..2d80a459f --- /dev/null +++ b/src/qdoc/catch_generators/src/catch_generators/utilities/statistics/percentages.h @@ -0,0 +1,49 @@ +// Copyright (C) 2022 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 + +#pragma once + +#include "../../namespaces.h" + +#include <cassert> + +namespace QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE { + + /*! + * Returns the percentage of \amount over \a total. + * + * \a amount needs to be greater or equal to zero and \a total + * needs to be greater than zero. + */ + inline double percent_of(double amount, double total) { + assert(amount >= 0.0); + assert(total > 0.0); + + return (amount / total) * 100.0; + } + + /*! + * Given the cardinality of a set, returns the percentage + * probability that applied to every element of the set generates + * a uniform distribution. + */ + inline double uniform_probability(std::size_t cardinality) { + assert(cardinality > 0); + + return (100.0 / static_cast<double>(cardinality)); + } + + /*! + * Returns a percentage probability that is equal to \a + * probability. + * + * \a probability must be in the range [0.0, 1.0] + */ + inline double probability_to_percentage(double probability) { + assert(probability >= 0.0); + assert(probability <= 1.0); + + return probability * 100.0; + } + +} // end QDOC_CATCH_GENERATORS_UTILITIES_ABSOLUTE_NAMESPACE |