1    :  // Copyright 2012 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  //
  15    :  // Unittests for the random orderer.
  16    :  
  17    :  #include "syzygy/block_graph/orderers/random_orderer.h"
  18    :  
  19    :  #include "gmock/gmock.h"
  20    :  #include "gtest/gtest.h"
  21    :  
  22    :  namespace block_graph {
  23    :  namespace orderers {
  24    :  
  25    :  namespace {
  26    :  
  27    :  using testing::ContainerEq;
  28    :  
  29    :  class RandomOrdererTest : public testing::Test {
  30    :   public:
  31  E :    virtual void SetUp() {
  32  E :      section1_ = block_graph_.AddSection("foo", 0);
  33  E :      section2_ = block_graph_.AddSection("bar", 0);
  34  E :    }
  35    :  
  36    :    BlockGraph block_graph_;
  37    :    BlockGraph::Section* section1_;
  38    :    BlockGraph::Section* section2_;
  39    :  };
  40    :  
  41    :  template<typename Container>
  42    :  void ToVector(const Container& container,
  43  E :                std::vector<typename Container::value_type>* vector) {
  44  E :    DCHECK(vector != NULL);
  45  E :    vector->assign(container.begin(), container.end());
  46  E :  }
  47    :  
  48    :  template<typename Container>
  49  E :  Container Sorted(const Container& container) {
  50  E :    Container copy(container);
  51  E :    std::sort(copy.begin(), copy.end());
  52  E :    return copy;
  53  E :  }
  54    :  
  55    :  }  // namespace
  56    :  
  57  E :  TEST_F(RandomOrdererTest, DefaultShuffleTrue) {
  58  E :    RandomOrderer random(true);
  59  E :    EXPECT_TRUE(random.ShouldShuffleSection(section1_));
  60  E :    EXPECT_TRUE(random.ShouldShuffleSection(section2_));
  61    :  
  62  E :    random.SetShuffleSection(section1_, false);
  63  E :    EXPECT_FALSE(random.ShouldShuffleSection(section1_));
  64  E :    EXPECT_TRUE(random.ShouldShuffleSection(section2_));
  65    :  
  66  E :    random.SetShuffleSection(section1_, true);
  67  E :    EXPECT_TRUE(random.ShouldShuffleSection(section1_));
  68  E :    EXPECT_TRUE(random.ShouldShuffleSection(section2_));
  69  E :  }
  70    :  
  71  E :  TEST_F(RandomOrdererTest, DefaultShuffleFalse) {
  72  E :    RandomOrderer random(false);
  73  E :    EXPECT_FALSE(random.ShouldShuffleSection(section1_));
  74  E :    EXPECT_FALSE(random.ShouldShuffleSection(section2_));
  75    :  
  76  E :    random.SetShuffleSection(section2_, true);
  77  E :    EXPECT_FALSE(random.ShouldShuffleSection(section1_));
  78  E :    EXPECT_TRUE(random.ShouldShuffleSection(section2_));
  79    :  
  80  E :    random.SetShuffleSection(section2_, false);
  81  E :    EXPECT_FALSE(random.ShouldShuffleSection(section1_));
  82  E :    EXPECT_FALSE(random.ShouldShuffleSection(section2_));
  83  E :  }
  84    :  
  85  E :  TEST_F(RandomOrdererTest, Shuffle) {
  86    :    // Put some blocks in each section.
  87  E :    for (size_t i = 0; i < 2; ++i) {
  88  E :      BlockGraph::SectionId section_id = (i == 0 ? section1_ : section2_)->id();
  89    :  
  90  E :      for (size_t j = 0; j < 30; ++j) {
  91    :        BlockGraph::Block* block =
  92  E :            block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 10, "block");
  93  E :        block->set_section(section_id);
  94  E :      }
  95  E :    }
  96    :  
  97    :    // We have 30! possible permutations, which is far greater than the number
  98    :    // of possible seed values. Thus, our chances of hitting a seed that causes
  99    :    // the identity ordering is quite small, and pretty much impossible for 5
 100    :    // consecutive seed values.
 101    :  
 102  E :    size_t shuffled = 0;
 103  E :    for (uint32 i = 0; i < 5; ++i) {
 104  E :      OrderedBlockGraph obg(&block_graph_);
 105    :  
 106    :      // Get the original order.
 107  E :      BlockVector blocks1, blocks2;
 108  E :      ToVector(obg.ordered_section(section1_).ordered_blocks(), &blocks1);
 109  E :      ToVector(obg.ordered_section(section2_).ordered_blocks(), &blocks2);
 110    :  
 111    :      // Shuffle the blocks.
 112  E :      RandomOrderer random(true, i);
 113  E :      EXPECT_TRUE(random.OrderBlockGraph(&obg, NULL));
 114    :  
 115    :      // Get the shuffled order.
 116  E :      BlockVector shuffled1, shuffled2;
 117  E :      ToVector(obg.ordered_section(section1_).ordered_blocks(), &shuffled1);
 118  E :      ToVector(obg.ordered_section(section2_).ordered_blocks(), &shuffled2);
 119    :  
 120  E :      EXPECT_THAT(Sorted(blocks1), ContainerEq(Sorted(shuffled1)));
 121  E :      EXPECT_THAT(Sorted(blocks2), ContainerEq(Sorted(shuffled2)));
 122    :  
 123  E :      if (blocks1 != shuffled1 && blocks2 != shuffled2)
 124  E :        ++shuffled;
 125  E :    }
 126  E :    EXPECT_LT(0u, shuffled);
 127  E :  }
 128    :  
 129    :  }  // namespace orderers
 130    :  }  // namespace block_graph