PrefixMapTest.cpp

//===--- PrefixMapTest.cpp ------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "swift/Basic/PrefixMap.h"
#include "gtest/gtest.h"

#include "llvm/ADT/SmallString.h"

#include <string>
#include <map>

using namespace swift;

static ArrayRef<char> asArray(StringRef str) {
  return ArrayRef<char>(str.begin(), str.end());
}
static StringRef asString(ArrayRef<char> str) {
  return StringRef(str.begin(), str.size());
}

namespace {

struct Tester {
  std::map<std::string, int> StdMap;
  PrefixMap<char, int> PreMap;

  Tester() {
    assert(PreMap.empty());
  }

  // Performs an insert operation and tests that the result matches what
  // we get from the std::map.
  void insert(StringRef key, int value) {
    auto stdmapResult = StdMap.insert({key.str(), value});
    auto premapResult = PreMap.insert(asArray(key), value);

    // Whether or not we modified the map should be the same in both
    // implementations.
    EXPECT_EQ(stdmapResult.second, premapResult.second);

    // If we did insert a new entry, the value at the handle should
    // reflect the value we inserted.
    if (premapResult.second) {
      EXPECT_EQ(value, *premapResult.first);
    }
  }

  // Tests that the result of a findPrefix matches what we expect from
  // the std::map.
  void find(StringRef key) {
    auto stdmapResult = StdMap.lower_bound(key.str());
    while (stdmapResult == StdMap.end() ||
           !key.startswith(stdmapResult->first)) {
      if (stdmapResult == StdMap.begin()) {
        stdmapResult = StdMap.end();
        break;
      }
      --stdmapResult;
    }
    bool hasStdmapEntry = (stdmapResult != StdMap.end());

    auto premapResult = PreMap.findPrefix(asArray(key));

    EXPECT_EQ(hasStdmapEntry, bool(premapResult.first));
    if (!hasStdmapEntry) return;

    assert(key.startswith(stdmapResult->first));
    auto stdmapValue = stdmapResult->second;
    EXPECT_EQ(stdmapValue, *premapResult.first);
    EXPECT_EQ(key.begin() + stdmapResult->first.size(), premapResult.second);
  }

  // Perform a clear operation.  Tests that that actually clears out the map.
  void clear() {
    StdMap.clear();
    PreMap.clear();
    EXPECT_TRUE(PreMap.empty());
    EXPECT_EQ(0U, PreMap.size());
  }

  // Validate the map.  Primarily tests iteration.
  void validate() {
    EXPECT_EQ(StdMap.empty(), PreMap.empty());
    EXPECT_EQ(StdMap.size(), PreMap.size());

    auto si = StdMap.begin(), se = StdMap.end();
    auto pi = PreMap.begin(), pe = PreMap.end();
    while (true) {
      if (si == se) {
        EXPECT_TRUE(pi == pe);
        return;
      }
      EXPECT_TRUE(pi != pe);

      EXPECT_EQ(si->second, (*pi).getValue());

      llvm::SmallString<128> buffer;
      EXPECT_EQ(StringRef(si->first), asString((*pi).getKey(buffer)));

      ++si;
      ++pi;
    }
  }
};

} // end anonymous namespace

TEST(PrefixMapTest, Insert) {
  PrefixMap<char, int> map;
  map.insert(asArray("abcdefghi"), 5);
  EXPECT_FALSE(bool(map.findPrefix(asArray("abcdefg")).first));

  ArrayRef<char> abcdefghij = asArray("abcdefghij");
  auto abcdefghijHandle = map.findPrefix(abcdefghij);
  EXPECT_TRUE(bool(abcdefghijHandle.first));
  EXPECT_EQ(5, *abcdefghijHandle.first);
  EXPECT_EQ(abcdefghij.data() + 9, abcdefghijHandle.second);
}

TEST(PrefixMapTest, Test1) {
  Tester tester;
  tester.find("");
  tester.validate();
  tester.insert("", 22096);
  tester.validate();
  tester.insert("", 20154);
  tester.validate();
  tester.insert("aezvs", 21441);
  tester.validate();
  tester.insert("aezvs", 838);
  tester.validate();
  tester.insert("aezvs", 16768);
  tester.validate();
  tester.validate();
  tester.find("aezvsrmoll");
  tester.validate();
  tester.insert("aezvsrmoll", 5842);
  tester.validate();
  tester.find("aezvsrmoll");
  tester.validate();
}

TEST(PrefixMapTest, Test2) {
  Tester tester;
  tester.find("");
  tester.validate();
  tester.insert("", 22096);
  tester.validate();
  tester.insert("", 20154);
  tester.validate();
  tester.insert("aezvs", 21441);
  tester.validate();
  tester.insert("aezvs", 838);
  tester.validate();
  tester.insert("aezvs", 16768);
  tester.validate();
  tester.clear();
  tester.validate();
  tester.find("aezvsrmoll");
  tester.validate();
  tester.insert("aezvsrmoll", 5842);
  tester.validate();
  tester.find("aezvsrmoll");
  tester.validate();
}

TEST(PrefixMapTest, Test3) {
  Tester tester;
  tester.insert("wbuqbtaprrpooqteftzdhjd", 11861);
  tester.insert("wbuqbtaprrpooqteftzdhjd", 18531);
  tester.find("wbuqbtaprrpooqteftzdhjdqkemtcl");
}

TEST(PrefixMapTest, Test4) {
  Tester tester;
  tester.find("");
  tester.validate();
  tester.find("l");
  tester.validate();
  tester.insert("l", 5943);
  tester.validate();
  tester.find("l");
  tester.validate();
  tester.insert("l", 8632);
  tester.validate();
  tester.find("zguowwnctgmkg");
}