TSP server crash on ubuntu 20.04

[cvvergara]

Describe the bug
TSP is crashing the server

To Reproduce

CREATE TABLE tsp_issue AS
SELECT start_vid, end_vid, agg_cost
FROM (VALUES  
     (-2,      -1, 0.005665599374822598),
     (-1,      -2, 0.005665599374822598))
AS t (start_vid, end_vid, agg_cost);

PREPARE test1 AS
SELECT *
FROM pgr_TSP($$  SELECT * FROM tsp_issue$$, -1)

EXECUTE test1;

The first time works fine

 seq | node |         cost         |       agg_cost       
-----+------+----------------------+----------------------
   1 |   -1 | 0.005665599374822598 |                    0
   2 |   -2 | 0.005665599374822598 | 0.005665599374822598
   3 |   -1 |                    0 | 0.011331198749645196
(3 rows)

But eventually after some times it crashes the server

EXECUTE test1; -- ok
EXECUTE test1; -- ok
EXECUTE test1; -- server crash
server closed the connection unexpectedly
        This probably means the server terminated abnormally
        before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.
!> 

Expected behavior
Not to crash the server.

Specifications (please complete the following information):
Use the commands:

SELECT version();
                                                               version                                                               
-------------------------------------------------------------------------------------------------------------------------------------
 PostgreSQL 12.5 (Ubuntu 12.5-0ubuntu0.20.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, 64-bit
(1 row)

sampledata=# SELECT postgis_full_version();
                                                                        postgis_full_version                                                                        
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 POSTGIS="3.0.0 r17983" [EXTENSION] PGSQL="120" GEOS="3.8.0-CAPI-1.13.1 " PROJ="6.3.1" LIBXML="2.9.4" LIBJSON="0.13.1" LIBPROTOBUF="1.3.3" WAGYU="0.4.3 (Internal)"
(1 row)

sampledata=# SELECT pgr_version();
 pgr_version 
-------------
 3.1.1
(1 row)

Additional context

lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 20.04.1 LTS
Release:        20.04
Codename:       focal

and:

cmake ..
-- Setting build type to 'Debug' as none was specified.
-- CMAKE_BUILD_TYPE Debug
-- The C compiler identification is GNU 8.4.0
-- The CXX compiler identification is GNU 8.4.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- DOXYGEN_MINIMUM_VERSION=1.7
-- SPHINX_MINIMUM_VERSION=1.8
-- POSTGRESQL_MINIMUM_VERSION=9.2.0
-- POSTGIS_MINIMUM_VERSION=2.0.0
-- GNU_CXX_MINIMUM_VERSION=4.6
-- CLANG_CXX_MINIMUM_VERSION=
-- MSVC_CXX_MINIMUM_VERSION=18.0
-- dir='/home/vicky/pgrouting/pgrouting/cvvergara/cmake'
-- Performing Test COMPILER_SUPPORTS_CXX0X
-- Performing Test COMPILER_SUPPORTS_CXX0X - Success
-- Performing Test COMPILER_SUPPORTS_CXX11
-- Performing Test COMPILER_SUPPORTS_CXX11 - Success
-- Using  -std=c++11.
-- Found Perl: /usr/bin/perl (found version "5.30.0") 
-- POSTGRESQL_PG_CONFIG is /usr/bin/pg_config
-- POSTGRESQL_EXECUTABLE is /usr/lib/postgresql/12/bin/postgres
-- POSTGRESQL_VERSION_STRING in FindPostgreSQL.cmake is PostgreSQL 12.5 (Ubuntu 12.5-0ubuntu0.20.04.1)
-- POSTGRESQL_INCLUDE_DIR: /usr/include/postgresql/12/server
-- POSTGRESQL_LIBRARIES: /usr/lib/x86_64-linux-gnu
-- PGSQL_VERSION=125
-- Found Boost: /usr/lib/x86_64-linux-gnu/cmake/Boost-1.71.0/BoostConfig.cmake (found suitable version "1.71.0", minimum required is "1.53")  
-- Boost headers were found here: /usr/include
-- Boost VERSION 1.71.0
-- BOOST_VERSION_OK 1
-- BOOST_Geometry_VERSION_OK 1
-- Performing Test C_COMPILER_SUPPORTS_FPIC
-- Performing Test C_COMPILER_SUPPORTS_FPIC - Success
-- Performing Test CXX_COMPILER_SUPPORTS_FPIC
-- Performing Test CXX_COMPILER_SUPPORTS_FPIC - Success
-- Performing Test C_COMPILER_SUPPORTS_ROUNDING_MATH
-- Performing Test C_COMPILER_SUPPORTS_ROUNDING_MATH - Success
-- Performing Test CXX_COMPILER_SUPPORTS_ROUNDING_MATH
-- Performing Test CXX_COMPILER_SUPPORTS_ROUNDING_MATH - Success
-- Configuring done
-- Generating done
-- Build files have been written to: /home/vicky/pgrouting/pgrouting/cvvergara/build

[cvvergara]

The fix that I could find is the following:

bool
Dmatrix::has_id(int64_t id) const {
    auto pos = std::lower_bound(ids.begin(), ids.end(), id);
    return *pos == id;
}

to

bool
Dmatrix::has_id(int64_t id) const {
    for (const auto &i : ids) {
        if (i == id) return true;
    }
    return false;
}

which means that std::lower_bound from G++ is not working like it should.
This issue does not show on 18.04 for example.
So the Compiler version of GNU G++ might have a bug.
Will investigate that.

On the meantime this branch has that proposed fix which is not crashing the server:
https://github.com/cvvergara/pgrouting/tree/issue-1760-3.1

Please try it