llvm/FuzzMutate/Random.h

0001 //===--- Random.h - Utilities for random sampling -------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Utilities for random sampling.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_FUZZMUTATE_RANDOM_H
0014 #define LLVM_FUZZMUTATE_RANDOM_H
0015
0016 #include "llvm/Support/raw_ostream.h"
0017 #include <random>
0018 namespace llvm {
0019
0020 /// Return a uniformly distributed random value between \c Min and \c Max
0021 template <typename T, typename GenT> T uniform(GenT &Gen, T Min, T Max) {
0022   return std::uniform_int_distribution<T>(Min, Max)(Gen);
0023 }
0024
0025 /// Return a uniformly distributed random value of type \c T
0026 template <typename T, typename GenT> T uniform(GenT &Gen) {
0027   return uniform<T>(Gen, std::numeric_limits<T>::min(),
0028                     std::numeric_limits<T>::max());
0029 }
0030
0031 /// Randomly selects an item by sampling into a set with an unknown number of
0032 /// elements, which may each be weighted to be more likely choices.
0033 template <typename T, typename GenT> class ReservoirSampler {
0034   GenT &RandGen;
0035   std::remove_const_t<T> Selection = {};
0036   uint64_t TotalWeight = 0;
0037
0038 public:
0039   ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
0040
0041   uint64_t totalWeight() const { return TotalWeight; }
0042   bool isEmpty() const { return TotalWeight == 0; }
0043
0044   const T &getSelection() const {
0045     assert(!isEmpty() && "Nothing selected");
0046     return Selection;
0047   }
0048
0049   explicit operator bool() const { return !isEmpty(); }
0050   const T &operator*() const { return getSelection(); }
0051
0052   /// Sample each item in \c Items with unit weight
0053   template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
0054     for (auto &I : Items)
0055       sample(I, 1);
0056     return *this;
0057   }
0058
0059   /// Sample a single item with the given weight.
0060   ReservoirSampler &sample(const T &Item, uint64_t Weight) {
0061     if (!Weight)
0062       // If the weight is zero, do nothing.
0063       return *this;
0064     TotalWeight += Weight;
0065     // Consider switching from the current element to this one.
0066     if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
0067       Selection = Item;
0068     return *this;
0069   }
0070 };
0071
0072 template <typename GenT, typename RangeT,
0073           typename ElT = std::remove_reference_t<
0074               decltype(*std::begin(std::declval<RangeT>()))>>
0075 ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) {
0076   ReservoirSampler<ElT, GenT> RS(RandGen);
0077   RS.sample(Items);
0078   return RS;
0079 }
0080
0081 template <typename GenT, typename T>
0082 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen, const T &Item,
0083                                       uint64_t Weight) {
0084   ReservoirSampler<T, GenT> RS(RandGen);
0085   RS.sample(Item, Weight);
0086   return RS;
0087 }
0088
0089 template <typename T, typename GenT>
0090 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) {
0091   return ReservoirSampler<T, GenT>(RandGen);
0092 }
0093
0094 } // namespace llvm
0095
0096 #endif // LLVM_FUZZMUTATE_RANDOM_H