debugd/src/random_selector_test.cc

// Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <base/strings/string_util.h>
#include <cmath>
#include <gtest/gtest.h>
#include <map>
#include <string>

#include "debugd/src/random_selector.h"

using debugd::RandomSelector;

namespace {

// A large number to do a lot of tests so the probability distribution of the
// results is close to the expected distribution.
const int kLargeNumber = 2000;

// A small floating point number used to verify that the expected odds are equal
// to the odds set.
const double kEpsilon = 0.01;

// A test file that contains some odds.
const char kOddsFilename[] = "../src/testdata/simple_odds_file.txt";

// This function tests whether the results are close enough to the odds (within
// 1%).
void CheckResultsAgainstOdds(
    const std::vector<RandomSelector::OddsAndValue>& odds,
    const std::map<std::string, int>& results) {
  EXPECT_EQ(odds.size(), results.size());

  const double odds_sum = RandomSelector::SumOdds(odds);
  int results_sum = 0;
  for (const auto& item : results) {
    results_sum += item.second;
  }

  for (const auto& odd : odds) {
    const auto result = results.find(JoinString(odd.value, ' '));
    EXPECT_NE(result, results.end());
    const double results_ratio = 1.0*result->second / results_sum;
    const double odds_ratio = odd.weight / odds_sum;
    const double abs_diff = fabs(results_ratio - odds_ratio);
    EXPECT_LT(abs_diff, kEpsilon);
  }
}

// A class that overrides RandDoubleUpTo() to not be random. The number
// generator will emulate a uniform distribution of numbers between 0.0 and
// |max| when called with the same |max| parameter and a whole multiple of
// |random_period| times. This allows better testing of the RandomSelector
// class.
class RandomSelectorWithCustomRNG : public RandomSelector {
 public:
  explicit RandomSelectorWithCustomRNG(unsigned int random_period)
      : random_period_(random_period), current_index_(0) {}

 private:
  // This function returns floats between 0.0 and |max| in an increasing
  // fashion at regular intervals.
  double RandDoubleUpTo(double max) override {
    current_index_ = (current_index_ + 1) % random_period_;
    return max * current_index_ / random_period_;
  }

  // Period (number of calls) over which the fake RNG repeats.
  const unsigned int random_period_;

  // Stores the current position we are at in the interval between 0.0 and
  // |max|. See the function RandDoubleUpTo for details on how this is used.
  int current_index_;
};

// Use the random_selector to generate some values. The number of values to
// generate is |iterations|.
void GenerateResults(size_t iterations,
                     RandomSelector* random_selector,
                     std::map<std::string, int>* results) {
  for (size_t i = 0; i < iterations; ++i) {
    const std::vector<std::string>& next_value = random_selector->GetNext();
    std::string joined = JoinString(next_value, ' ');
    (*results)[joined]++;
  }
}

// Test the RandomSelector class given the odds in the |odds| list.
void TestOdds(const std::vector<RandomSelector::OddsAndValue>& odds) {
  RandomSelectorWithCustomRNG random_selector(kLargeNumber);
  random_selector.SetOdds(odds);
  // Generate a lot of values.
  std::map<std::string, int> results;
  GenerateResults(kLargeNumber, &random_selector, &results);
  // Ensure the values and odds are related.
  CheckResultsAgainstOdds(odds, results);
}

}  // namespace

// Ensure RandomSelector is able to generate results from given odds.
TEST(RandomSelector, GenerateTest) {
  std::vector<RandomSelector::OddsAndValue> odds = {
    {1, {"a", "1"}},
    {2, {"b", "--help"}},
    {3, {"c", "bar"}},
  };
  TestOdds(odds);
}

// Ensure RandomSelector is able to read odds from a file.
TEST(RandomSelector, SetOddsFromFileTest) {
  RandomSelectorWithCustomRNG random_selector(kLargeNumber);
  random_selector.SetOddsFromFile(std::string(kOddsFilename));
  std::map<std::string, int> results;
  std::vector<RandomSelector::OddsAndValue> odds = {
    {3, {"afile"}},
    {2, {"bfile", "-o", "output"}},
    {1, {"cfile", "-e", "cycles"}},
  };
  GenerateResults(kLargeNumber, &random_selector, &results);
  CheckResultsAgainstOdds(odds, results);
}