<commit_before>#include "../../testing/testing.hpp"
#include "../trie.hpp"
#include "../trie_builder.hpp"
#include "../trie_reader.hpp"
#include "../byte_stream.hpp"
#include "../write_to_sink.hpp"
#include "../../base/logging.hpp"
#include "../../std/algorithm.hpp"
#include "../../std/scoped_ptr.hpp"
#include "../../std/string.hpp"
#include "../../std/vector.hpp"
#include <boost/utility/binary.hpp>

namespace
{

struct ChildNodeInfo
{
  bool m_isLeaf;
  uint32_t m_size;
  vector<uint32_t> m_edge;
  string m_edgeValue;
  ChildNodeInfo(bool isLeaf, uint32_t size, char const * edge, char const * edgeValue)
    : m_isLeaf(isLeaf), m_size(size), m_edgeValue(edgeValue)
  {
    while (*edge)
      m_edge.push_back(*edge++);
  }

  uint32_t Size() const { return m_size; }
  bool IsLeaf() const { return m_isLeaf; }
  uint32_t const * GetEdge() const { return &m_edge[0]; }
  uint32_t GetEdgeSize() const { return m_edge.size(); }
  void const * GetEdgeValue() const { return m_edgeValue.data(); }
  uint32_t GetEdgeValueSize() const { return m_edgeValue.size(); }
};

struct KeyValuePair
{
  buffer_vector<trie::TrieChar, 8> m_key;
  uint32_t m_value;

  KeyValuePair() {}

  template <class StringT>
  KeyValuePair(StringT const & key, int value)
    : m_key(key.begin(), key.end()), m_value(value)
  {}

  uint32_t GetKeySize() const { return m_key.size(); }
  trie::TrieChar const * GetKeyData() const { return m_key.data(); }

  template <class TCont> void SerializeValue(TCont & cont) const
  {
    cont.resize(4);
    memcpy(cont.data(), &m_value, 4);
  }

  bool operator == (KeyValuePair const & p) const
  {
    return (m_key == p.m_key && m_value == p.m_value);
  }

  bool operator < (KeyValuePair const & p) const
  {
    return ((m_key != p.m_key) ? m_key < p.m_key : m_value < p.m_value);
  }

  void Swap(KeyValuePair & r)
  {
    m_key.swap(r.m_key);
    swap(m_value, r.m_value);
  }
};

string DebugPrint(KeyValuePair const & p)
{
  string keyS = ::DebugPrint(p.m_key);
  ostringstream out;
  out << "KVP(" << keyS << ", " << p.m_value << ")";
  return out.str();
}

struct KeyValuePairBackInserter
{
  vector<KeyValuePair> m_v;
  template <class StringT>
  void operator() (StringT const & s,
                   trie::reader::FixedSizeValueReader<4>::ValueType const & rawValue)
  {
    uint32_t value;
    memcpy(&value, &rawValue, 4);
    m_v.push_back(KeyValuePair(s, value));
  }
};

struct MaxValueCalc
{
  typedef uint8_t ValueType;

  ValueType operator() (void const * p, uint32_t size) const
  {
    ASSERT_EQUAL(size, 4, ());
    uint32_t value;
    memcpy(&value, p, 4);
    ASSERT_LESS(value, 256, ());
    return static_cast<uint8_t>(value);
  }
};

}  // unnamed namespace

#define ZENC bits::ZigZagEncode

UNIT_TEST(TrieBuilder_WriteNode_Smoke)
{
  vector<uint8_t> serial;
  PushBackByteSink<vector<uint8_t> > sink(serial);
  ChildNodeInfo children[] =
  {
    ChildNodeInfo(true, 1, "1A", "i1"),
    ChildNodeInfo(false, 2, "B", "ii2"),
    ChildNodeInfo(false, 3, "zz", ""),
    ChildNodeInfo(true, 4,
                  "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij", "i4"),
    ChildNodeInfo(true, 5, "a", "5z")
  };
  trie::builder::WriteNode(sink, 0, 3, "123", 3,
                           &children[0], &children[0] + ARRAY_SIZE(children));
  uint8_t const expected [] =
  {
    BOOST_BINARY(11000101),                                                 // Header: [0b11] [0b000101]
    3,                                                                      // Number of values
    '1', '2', '3',                                                          // Values
    BOOST_BINARY(10000001),                                                 // Child 1: header: [+leaf] [-supershort]  [2 symbols]
    static_cast<uint8_t>(ZENC('1')), static_cast<uint8_t>(ZENC('A' - '1')), // Child 1: edge
    'i', '1',                                                               // Child 1: intermediate data
    1,                                                                      // Child 1: size
    static_cast<uint8_t>(64 | ZENC('B' - '1')),                             // Child 2: header: [-leaf] [+supershort]
    'i', 'i', '2',                                                          // Child 2: intermediate data
    2,                                                                      // Child 2: size
    BOOST_BINARY(00000001),                                                 // Child 3: header: [-leaf] [-supershort]  [2 symbols]
    static_cast<uint8_t>(ZENC('z' - 'B')), 0,                               // Child 3: edge
    3,                                                                      // Child 3: size
    BOOST_BINARY(10111111),                                                 // Child 4: header: [+leaf] [-supershort]  [>= 63 symbols]
    69,                                                                     // Child 4: edgeSize - 1
    static_cast<uint8_t>(ZENC('a' - 'z')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    static_cast<uint8_t>(ZENC('a' - 'j')), 2,2,2,2,2,2,2,2,2,               // Child 4: edge
    'i', '4',                                                               // Child 4: intermediate data
    4,                                                                      // Child 4: size
    static_cast<uint8_t>(BOOST_BINARY(11000000) | ZENC(0)),                 // Child 5: header: [+leaf] [+supershort]
    '5', 'z'                                                                // Child 5: intermediate data
  };

  TEST_EQUAL(serial, vector<uint8_t>(&expected[0], &expected[0] + ARRAY_SIZE(expected)), ());
}

UNIT_TEST(TrieBuilder_Build)
{
  int const base = 3;
  int const maxLen = 3;

  vector<string> possibleStrings(1, string());
  for (int len = 1; len <= maxLen; ++len)
  {
    for (int i = 0, p = static_cast<int>(pow((double) base, len)); i < p; ++i)
    {
      string s(len, 'A');<commit_msg>[tests] updated tests not to fail on arm builds<commit_after>#include "../../testing/testing.hpp"
#include "../trie.hpp"
#include "../trie_builder.hpp"
#include "../trie_reader.hpp"
#include "../byte_stream.hpp"
#include "../write_to_sink.hpp"
#include "../../base/logging.hpp"
#include "../../std/algorithm.hpp"
#include "../../std/scoped_ptr.hpp"
#include "../../std/string.hpp"
#include "../../std/vector.hpp"
#include <boost/utility/binary.hpp>

namespace
{

struct ChildNodeInfo
{
  bool m_isLeaf;
  uint32_t m_size;
  vector<uint32_t> m_edge;
  string m_edgeValue;
  ChildNodeInfo(bool isLeaf, uint32_t size, char const * edge, char const * edgeValue)
    : m_isLeaf(isLeaf), m_size(size), m_edgeValue(edgeValue)
  {
    while (*edge)
      m_edge.push_back(*edge++);
  }

  uint32_t Size() const { return m_size; }
  bool IsLeaf() const { return m_isLeaf; }
  uint32_t const * GetEdge() const { return &m_edge[0]; }
  uint32_t GetEdgeSize() const { return m_edge.size(); }
  void const * GetEdgeValue() const { return m_edgeValue.data(); }
  uint32_t GetEdgeValueSize() const { return m_edgeValue.size(); }
};

struct KeyValuePair
{
  buffer_vector<trie::TrieChar, 8> m_key;
  uint32_t m_value;

  KeyValuePair() {}

  template <class StringT>
  KeyValuePair(StringT const & key, int value)
    : m_key(key.begin(), key.end()), m_value(value)
  {}

  uint32_t GetKeySize() const { return m_key.size(); }
  trie::TrieChar const * GetKeyData() const { return m_key.data(); }

  template <class TCont> void SerializeValue(TCont & cont) const
  {
    cont.resize(4);
    memcpy(cont.data(), &m_value, 4);
  }

  bool operator == (KeyValuePair const & p) const
  {
    return (m_key == p.m_key && m_value == p.m_value);
  }

  bool operator < (KeyValuePair const & p) const
  {
    return ((m_key != p.m_key) ? m_key < p.m_key : m_value < p.m_value);
  }

  void Swap(KeyValuePair & r)
  {
    m_key.swap(r.m_key);
    swap(m_value, r.m_value);
  }
};

string DebugPrint(KeyValuePair const & p)
{
  string keyS = ::DebugPrint(p.m_key);
  ostringstream out;
  out << "KVP(" << keyS << ", " << p.m_value << ")";
  return out.str();
}

struct KeyValuePairBackInserter
{
  vector<KeyValuePair> m_v;
  template <class StringT>
  void operator() (StringT const & s,
                   trie::reader::FixedSizeValueReader<4>::ValueType const & rawValue)
  {
    uint32_t value;
    memcpy(&value, &rawValue, 4);
    m_v.push_back(KeyValuePair(s, value));
  }
};

struct MaxValueCalc
{
  typedef uint8_t ValueType;

  ValueType operator() (void const * p, uint32_t size) const
  {
    ASSERT_EQUAL(size, 4, ());
    uint32_t value;
    memcpy(&value, p, 4);
    ASSERT_LESS(value, 256, ());
    return static_cast<uint8_t>(value);
  }
};

}  // unnamed namespace

#define ZENC bits::ZigZagEncode
#define MKSC(x) static_cast<signed char>(x)

UNIT_TEST(TrieBuilder_WriteNode_Smoke)
{
  vector<uint8_t> serial;
  PushBackByteSink<vector<uint8_t> > sink(serial);
  ChildNodeInfo children[] =
  {
    ChildNodeInfo(true, 1, "1A", "i1"),
    ChildNodeInfo(false, 2, "B", "ii2"),
    ChildNodeInfo(false, 3, "zz", ""),
    ChildNodeInfo(true, 4,
                  "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij", "i4"),
    ChildNodeInfo(true, 5, "a", "5z")
  };
  trie::builder::WriteNode(sink, 0, 3, "123", 3,
                           &children[0], &children[0] + ARRAY_SIZE(children));
  uint8_t const expected [] =
  {
    BOOST_BINARY(11000101),                                                 // Header: [0b11] [0b000101]
    3,                                                                      // Number of values
    '1', '2', '3',                                                          // Values
    BOOST_BINARY(10000001),                                                 // Child 1: header: [+leaf] [-supershort]  [2 symbols]
    static_cast<uint8_t>(ZENC(MKSC('1'))), static_cast<uint8_t>(ZENC(MKSC('A') - MKSC('1'))), // Child 1: edge
    'i', '1',                                                               // Child 1: intermediate data
    1,                                                                      // Child 1: size
    static_cast<uint8_t>(64 | ZENC(MKSC('B') - MKSC('1'))),                 // Child 2: header: [-leaf] [+supershort]
    'i', 'i', '2',                                                          // Child 2: intermediate data
    2,                                                                      // Child 2: size
    BOOST_BINARY(00000001),                                                 // Child 3: header: [-leaf] [-supershort]  [2 symbols]
    static_cast<uint8_t>(ZENC(MKSC('z') - MKSC('B'))), 0,                   // Child 3: edge
    3,                                                                      // Child 3: size
    BOOST_BINARY(10111111),                                                 // Child 4: header: [+leaf] [-supershort]  [>= 63 symbols]
    69,                                                                     // Child 4: edgeSize - 1
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('z'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    static_cast<uint8_t>(ZENC(MKSC('a') - MKSC('j'))), 2,2,2,2,2,2,2,2,2,   // Child 4: edge
    'i', '4',                                                               // Child 4: intermediate data
    4,                                                                      // Child 4: size
    static_cast<uint8_t>(BOOST_BINARY(11000000) | ZENC(0)),                 // Child 5: header: [+leaf] [+supershort]
    '5', 'z'                                                                // Child 5: intermediate data
  };

  TEST_EQUAL(serial, vector<uint8_t>(&expected[0], &expected[0] + ARRAY_SIZE(expected)), ());
}

UNIT_TEST(TrieBuilder_Build)
{
  int const base = 3;
  int const maxLen = 3;

  vector<string> possibleStrings(1, string());
  for (int len = 1; len <= maxLen; ++len)
  {
    for (int i = 0, p = static_cast<int>(pow((double) base, len)); i < p; ++i)
    {
      string s(len, 'A');
{'fraction_non_alphanumeric': 0.1580540037243948, 'fraction_numerical': 0.037243947858473, 'mean_word_length': 1.9206888737820078, 'pattern_counts': {'":': 0, '<': 88, '<?xml version=': 0, '>': 60, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 75, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7199951', 'n_tokens_mistral': 4590, 'n_tokens_neox': 4329, 'n_words': 901}