GTest | Seg faults when testing insertion of randomly generated values at random index to a dynamic-CodePudding

I created a custom generic DynamicArray class where everything works fine except when testing an add() method in which I am adding element ats a specific index.

I am using gtest framework for testing, more specifically, I am using type-parametrized tests for creating test cases. I run the tests against these types (int, int*, char*, char*, std::string), I created functions that generate random values for me and I use them in my test cases.

The problem is that sometimes I get seg faults and some other times I don't.

Here is the structure of my project:

build/
include/
   structs/
      DynamicArray.h
src/
   main.cpp
tests/
   TestCases/
      DynamicArrayTest.cpp
   TestClasses/
      DynamicArrayTest.h
   TestHelpers/
      generators.h
   test_runner.cpp
CMakeLists.txt

CMakeLists.txt:

# cmake version and project info

############################################################################

# Variables 
# Compile flags

SET(GCC_DEBUGGING_COMPILE_FLAGS "-Wall -ggdb3")
SET(CMAKE_CXX_FLAGS  "${CMAKE_CXX_FLAGS} ${GCC_DEBUGGING_COMPILE_FLAGS}")

set(SRCS
    src/main.cpp
)

set(EXEC_SRCS
    src/main.cpp
)

set(HEADERS
    include/structs/structures.h
)

set(TEST_SRCS
    tests/TestCases/DynamicArrayTest.cpp
    tests/test_runner.cpp
)
############################################################################

# Gtest

include(FetchContent)
FetchContent_Declare(
  googletest
  URL https://github.com/google/googletest/archive/03597a01ee50ed33e9dfd640b249b4be3799d395.zip
)
# For Windows: Prevent overriding the parent project's compiler/linker settings
set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
FetchContent_MakeAvailable(googletest)

############################################################################
## 
# Build targets
##

if(${PROJECT_NAME}_BUILD_EXECUTABLE)

    add_executable(${PROJECT_NAME} ${EXEC_SRCS} ${SRCS})

    if(${PROJECT_NAME}_ENABLE_UNIT_TESTING)
        add_library(${PROJECT_NAME}_LIB ${HEADERS} ${SRCS})
    endif()
    
elseif(${PROJECT_NAME}_BUILD_HEADERS_ONLY)
    add_library(${PROJECT_NAME} INTERFACE)


else()
  add_library(
    ${PROJECT_NAME}
    ${HEADERS}
    ${SRCS}
  )

endif()

############################################################################
## 
# Including Directories 
##

target_include_directories(Structs
    PUBLIC ${PROJECT_SOURCE_DIR}/include
)

############################################################################
## 
# Installation 
##

############################################################################
## 
# Tests 
##
enable_testing()

add_executable(StructsTest
  ${TEST_SRCS}
)
target_compile_options(StructsTest PRIVATE -ggdb3)

target_link_libraries(
    StructsTest
    GTest::gtest_main
)

target_include_directories(StructsTest
    PUBLIC ${PROJECT_SOURCE_DIR}/tests
    PRIVATE ${PROJECT_SOURCE_DIR}/include
)

include(GoogleTest)
gtest_discover_tests(StructsTest)

Code to be tested:

include/structs/DynamicArray.h

namespace structs
{
#define INITIAL_SIZE 10

template <typename T>
class DynamicArray
{
private:
    size_t m_capacity;
    size_t m_size;
    T* m_data;
    void resize();

public:
    // constructors & destructors
    DynamicArray();
    DynamicArray(const DynamicArray&);
    DynamicArray(T&);
    DynamicArray(T&&);
    DynamicArray(T*, size_t);
    ~DynamicArray();

    // operations
    void push_back(T);
    void set(size_t, T);
    void add(size_t, T);
    T get(size_t);
    T pop();
    T remove(size_t);
    size_t size();
    size_t capacity();
    bool is_empty();
    void read();
    void reset();
}; // DynamicArray class
}// namespace structs

// .. Impl

template<typename T>
structs::DynamicArray<T>::DynamicArray()
:m_capacity(INITIAL_SIZE),
m_data(new T[m_capacity]),
m_size(0)
{
    if (m_data == nullptr)
        throw std::bad_alloc();

    m_size = 0;
}

template<typename T>
structs::DynamicArray<T>::DynamicArray( T* values, size_t size )
: DynamicArray()
{
    for (size_t i = 0; i < size; i  )
    {
        this->push_back(*values);
        values  ;
    }
}

template<typename T>
structs::DynamicArray<T>::~DynamicArray()
{
    delete[] m_data;
}

template<typename T>
void structs::DynamicArray<T>::push_back( T value )
{
    if (m_size >= m_capacity)
        resize();
    
    *(m_data   m_size) = value;
    m_size   ;
}

template<typename T>
void structs::DynamicArray<T>::add( size_t index, T value )
{
    if (index > m_size)
        throw std::out_of_range("Invalid: Exceeds range, use set(size_t, T) instead");
    
    if ( m_size == m_capacity )
        resize();
    
    for (long i = m_size - 1; i >= index; i--)
        m_data[i 1] = m_data[i];  
    
    m_data[index] = value;
    m_size   ;
}

Now to the test part:

I created a header file where I store the test fixture class and its implementation located in tests/TestClasses/*Test.h and I placed the test cases in tests/TestCases/*Test.cpp, and test_runner.cpp is the test driver.

DynamicArrayTest.h

The constructor SetUp() has a seperate implementation for each type, to make things a bit shorter I am going to only show the implementation of std::string type.

I assumed in the test case that resize() will not be called, and the array size will always be within the limit of the initial size it was created with to avoid adding a complexity overhead.

#pragma once

#include <iostream>
#include <random>
#include <cstdlib>
#include <ctime>
#include <type_traits>

#include "structs/DynamicArray.h"
#include "gtest/gtest.h"
#include "TestHelpers/generators.h"

#define TEST_INITIAL_SIZE 10

namespace structs
{
    namespace test
    {
        template<typename T>
        class DynamicArrayTest : public ::testing::Test
        {
        protected:
            void SetUp() override;
            void TearDown() override;

        public:
            structs::DynamicArray<T> a0_;   // empty
            structs::DynamicArray<T> a1_;   // filled upon initialization
            T value_;
            T array_[TEST_INITIAL_SIZE];
            std::vector<T> sample_values_;
        };
    } // namespace test
} // namespace structs

using namespace structs::test;

template <typename T>
void DynamicArrayTest<T>::SetUp()
{
}

template<>
void DynamicArrayTest<std::string>::SetUp()
{
    value_ = generate_string(generate_numeric<int>(0, 20));

    for (size_t i = 0; i < TEST_INITIAL_SIZE; i  )
        array_[i] = generate_string(generate_numeric<int>(0, 20));

    for (size_t i = 0; i < TEST_INITIAL_SIZE; i  )
        sample_values_.push_back(generate_string(generate_numeric<int>(0, 20)));
    
    for (size_t i = 0; i < TEST_INITIAL_SIZE; i  )
            a1_.push_back(generate_string(generate_numeric<int>(0, 20)));
}

template <typename T>
void DynamicArrayTest<T>::TearDown()
{
    // clean up 
    a1_.reset();
}

The functions that generate the random values lives in tests/TestHelpers/generators.h:

template<typename T>
T generate_numeric(const T, const T);

char generate_char();

std::string generate_string(const size_t);

Test cases: DynamicArrayTest.cpp

#include <iostream>

#include "gtest/gtest.h"
#include "structs/structures.h"
#include "TestClasses/DynamicArrayTest.h"
#include "TestHelpers/generators.h"

using namespace structs::test;

TYPED_TEST_SUITE_P(DynamicArrayTest);

TYPED_TEST_P(DynamicArrayTest, AddMethodTest)
{
    //structs::DynamicArray<TypeParam> initial_a1 = this->a1_;
    size_t random_index = generate_numeric(0, TEST_INITIAL_SIZE);
    size_t initial_size = this->a1_.size();

    this->a1_.add(random_index, this->value_);

    // Value is added at correct index
    EXPECT_EQ(this->a1_.get(random_index), this->value_);
    // size is updated
    EXPECT_EQ(this->a1_.size(), initial_size   1);  
}

REGISTER_TYPED_TEST_SUITE_P(DynamicArrayTest, 
    AddMethodTest
    );

//using MyTypes = ::testing::Types<char, int, char*, int*, std::string> ;
using MyTypes = ::testing::Types<std::string> ;
INSTANTIATE_TYPED_TEST_SUITE_P(DynamicArrayTest_, DynamicArrayTest, MyTypes);

Output Samples:

$ ./StructsTest
[==========] Running 13 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 13 tests from DynamicArrayTest_/DynamicArrayTest/0, where TypeParam = std::basic_string<char, std::char_traits<char>, std::allocator<char> >
[ RUN      ] DynamicArrayTest_/DynamicArrayTest/0.AddMethodTest
[       OK ] DynamicArrayTest_/DynamicArrayTest/0.AddMethodTest (0 ms)
[----------] 13 tests from DynamicArrayTest_/DynamicArrayTest/0 (8 ms total)
[----------] Global test environment tear-down
[==========] 13 tests from 1 test suite ran. (8 ms total)
[  PASSED  ] 12 tests.

$ ./StructsTest
[==========] Running 13 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 13 tests from DynamicArrayTest_/DynamicArrayTest/0, where TypeParam = std::basic_string<char, std::char_traits<char>, std::allocator<char> >
[ RUN      ] DynamicArrayTest_/DynamicArrayTest/0.AddMethodTest
Segmentation fault (core dumped)

When running the test with valgrind and a seg fault happens, valgrind always show this:

==138433== Process terminating with default action of signal 11 (SIGSEGV)
==138433==  Access not within mapped region at address 0x0
==138433==    at 0x49F1241: std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_assign(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (in /usr/lib/x86_64-linux-gnu/libstdc  .so.6.0.28)
==138433==    by 0x49F15FD: std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator=(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (in /usr/lib/x86_64-linux-gnu/libstdc  .so.6.0.28)
==138433==    by 0x127B84: structs::DynamicArray<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::add(unsigned long, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (DynamicArray.h:160)
==138433==    by 0x127336: gtest_suite_DynamicArrayTest_::AddMethodTest<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::TestBody() (DynamicArrayTest.cpp:84)

The line where the error happens as pointed by valgrind is here:

// DynamicArray.h
template<typename T>
void structs::DynamicArray<T>::add( size_t index, T value )
{
    if (index > m_size)
        throw std::out_of_range("Invalid: Exceeds range, use set(size_t, T) instead");
    
    if ( m_size == m_capacity )
        resize();
    
    for (long i = m_size - 1; i >= index; i--)
        m_data[i 1] = m_data[i];   // <- this
    
    m_data[index] = value;
    m_size   ;
}

If the issue is with the assignment, I don't understand why does it succeed sometimes?

CodePudding user response：

The issue was in this line:

size_t random_index = generate_numeric(0, TEST_INITIAL_SIZE);

TEST_INITIAL_SIZE was set to 10 which is the max capacity size causing resize() to be called and it wasn't implemented properly.

I modified the constant to a value less than max capacity by 2

#define TEST_INITIAL_SIZE INITIAL_SIZE - 2

solved