include/llvm/FuzzMutate/Random.h

   1 //===--- Random.h - Utilities for random sampling -------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Utilities for random sampling.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_FUZZMUTATE_RANDOM_H
  14 #define LLVM_FUZZMUTATE_RANDOM_H
  15
  16 #include <random>
  17 #include "llvm/Support/raw_ostream.h"
  18 namespace llvm {
  19
  20 /// Return a uniformly distributed random value between \c Min and \c Max
  21 template <typename T, typename GenT> T uniform(GenT &Gen, T Min, T Max) {
  22   return std::uniform_int_distribution<T>(Min, Max)(Gen);
  23 }
  24
  25 /// Return a uniformly distributed random value of type \c T
  26 template <typename T, typename GenT> T uniform(GenT &Gen) {
  27   return uniform<T>(Gen, std::numeric_limits<T>::min(),
  28                     std::numeric_limits<T>::max());
  29 }
  30
  31 /// Randomly selects an item by sampling into a set with an unknown number of
  32 /// elements, which may each be weighted to be more likely choices.
  33 template <typename T, typename GenT> class ReservoirSampler {
  34   GenT &RandGen;
  35   typename std::remove_const<T>::type Selection = {};
  36   uint64_t TotalWeight = 0;
  37
  38 public:
  39   ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
  40
  41   uint64_t totalWeight() const { return TotalWeight; }
  42   bool isEmpty() const { return TotalWeight == 0; }
  43
  44   const T &getSelection() const {
  45     assert(!isEmpty() && "Nothing selected");
  46     return Selection;
  47   }
  48
  49   explicit operator bool() const { return !isEmpty();}
  50   const T &operator*() const { return getSelection(); }
  51
  52   /// Sample each item in \c Items with unit weight
  53   template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
  54     for (auto &I : Items)
  55       sample(I, 1);
  56     return *this;
  57   }
  58
  59   /// Sample a single item with the given weight.
  60   ReservoirSampler &sample(const T &Item, uint64_t Weight) {
  61     if (!Weight)
  62       // If the weight is zero, do nothing.
  63       return *this;
  64     TotalWeight += Weight;
  65     // Consider switching from the current element to this one.
  66     if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
  67       Selection = Item;
  68     return *this;
  69   }
  70 };
  71
  72 template <typename GenT, typename RangeT,
  73           typename ElT = typename std::remove_reference<
  74               decltype(*std::begin(std::declval<RangeT>()))>::type>
  75 ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) {
  76   ReservoirSampler<ElT, GenT> RS(RandGen);
  77   RS.sample(Items);
  78   return RS;
  79 }
  80
  81 template <typename GenT, typename T>
  82 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen, const T &Item,
  83                                       uint64_t Weight) {
  84   ReservoirSampler<T, GenT> RS(RandGen);
  85   RS.sample(Item, Weight);
  86   return RS;
  87 }
  88
  89 template <typename T, typename GenT>
  90 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) {
  91   return ReservoirSampler<T, GenT>(RandGen);
  92 }
  93
  94 } // End llvm namespace
  95
  96 #endif // LLVM_FUZZMUTATE_RANDOM_H