Infinite loop when parsing template alias

[Haddayn]

You probably should update the info on your website, since the freenode channel is dead.

Cppcheck (version 2.5) got stuck in an infinite loop when parsing a template alias. Or at least it has been running for an hour. I've managed to condense the code into the following snippet:

namespace mystd {

template <typename T>
using remove_reference_t = typename std::remove_reference<T>::type;

template <typename T>
struct remove_cvref
{
    using type = typename std::remove_cv<remove_reference_t<T>>::type;
};

template <typename T>
using remove_cvref_t = typename remove_cvref<T>::type;

class any;

template <typename T>
T any_cast(any& any)
{
    if (auto* ptr = any_cast<remove_cvref_t<T>>(&any))
        return static_cast<T>(*ptr);
    throw bad_any_cast();
}
} // namespace mystd


int main()
{
    mystd::any a(4);
    *(mystd::any_cast<int>(&a)) = 5;
}

The code above was extracted from a full-fledged std::any implementation.

Cppcheck gets stuck in:

#0  0x000055555580c511 in TemplateSimplifier::addInstantiation(Token*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ()
#1  0x000055555581030a in TemplateSimplifier::getTemplateInstantiations() ()
#2  0x000055555581a9dc in TemplateSimplifier::simplifyTemplates(long, bool&) () <--- here, keeps adding same instantiation over and over again
#3  0x0000555555889fbc in Tokenizer::simplifyTokenList1(char const*) ()
#4  0x000055555588a14b in Tokenizer::simplifyTokens1(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ()
#5  0x000055555573c414 in CppCheck::checkFile(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::istream&) ()
#6  0x000055555573e40b in CppCheck::check(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ()
#7  0x000055555560a82b in CppCheckExecutor::check_internal(CppCheck&, int, char const* const*) ()
#8  0x000055555560acd1 in CppCheckExecutor::check(int, char const* const*) ()
#9  0x00005555555f3bf0 in main ()

[Daniel Marjamäki]

You probably should update the info on your website, since the freenode channel is dead.

We have tried to change.. can you specify where you see the freenode link.

[Haddayn]

On the trac page https://trac.cppcheck.net/

[Haddayn]

I tried to figure out what's gone wrong, but it is hard without diving deeper into the code which I don't have time for. I hope this information is helpful:

I inserted a breakpoint at the line

Token *tok2 = tok->next()->findClosingBracket();

And it seems it keeps adding same token over and over, when printing tok2->mPrevious->mPrevious, tok2->mPrevious->mPrevious->mPrevious->mPrevious etc, all point to the token "remove_cvref_t". All of these have diffrent addresses, so it is not a cyclic reference.

mTemplateInstantiations kept growing and growing, after a while there were 13640 instantiations of mystd :: remove_cvref_t

[Haddayn]

Managed to reduce it even further:

namespace mystd {
template <typename T>
struct remove_cvref
{
    using type = T
};

template <typename T>
using remove_cvref_t = typename remove_cvref<T>::type;

class any;

template <typename T>
T any_cast(any& any)
{
    any_cast<remove_cvref_t<T>>(&any);
}
}

int main()
{
    mystd::any a(4);
    mystd::any_cast<int&>(a) = 5;
}

Changing anything at this point breaks the infinite loop.

[Daniel Marjamäki]

Thank you! I have created ticket https://trac.cppcheck.net/ticket/10506

[david ingamells]

The following also infinite loops, maybe useful as a second test case.

#include <string>
#include <cstdint>

#include <boost/icl/interval_map.hpp>
#include <boost/numeric/interval.hpp>
#include <boost/variant.hpp>


namespace H
{
    namespace Type
    {
        struct SomeItem
        {
            std::string field1;

            bool operator<(
                const SomeItem &rhs) const
            {
                return field1 < rhs.field1;
            }
            bool operator==(
                const SomeItem &rhs) const
            {
                return field1 == rhs.field1;
            }
        };
    }

    using RangeVariant = boost::variant< Type::SomeItem >;

    using DataSet =  std::set<RangeVariant>;
    using interval_map = boost::icl::interval_map<double, DataSet>;
    using icl_interval = boost::icl::interval<double>;
}

namespace
{
    using namespace H;
    using namespace H::Type;

    struct PassOneArg
    {
        const std::string data1;
        const std::string data2;
    };

    auto splitData = [](const auto& ,
                        const std::function<void(const std::vector<std::string>& data)>&)
    {

    };

    void myFunction(
        interval_map& parts,
        const PassOneArg& arg)
    {
        splitData(arg.data2, [&](const auto& )
                  {
                      parts += make_pair(icl_interval::right_open(0, 1),
                                         DataSet(
                                             {
                                                 SomeItem
                                                 {
                                                     ""
                                                 }
                                             })
                                        );
                  });

        splitData(arg.data1, [&](const auto& offsetData)
        {
            for (size_t i = 2; i < offsetData.size(); ++ i)
            {


            }
        });

    }
}

namespace H
{
    void convert(bool)
    {
        interval_map boundaryData;
        PassOneArg arg{
                          "",
                          ""
                      };

        myFunction(boundaryData, arg);
    }
}

int main()
{
    convert(false);
}