C++ version of polyline_decode decodes incorrectly in some cases

[michal1459]

We've found a scenario in which the C++ flexpolyline.h decodes incorrectly. In comparison, the Javascript version works fine.

1. Steps to reproduce:
   • Encode a line consisting of 3 points: (-37.8312911, 144.9978678), (-37.831321700000004, 144.9978624), (-37.8313573, 144.9978559)

     auto enc = encoder::Encoder(7, hf::ThirdDim::LEVEL, 0);
     enc.add(-37.8312911, 144.9978678, 0);
     enc.add(-37.831321700000004, 144.9978624, 0);
     enc.add(-37.8313573, 144.9978559, 0);
     auto encoded_polyline = enc.get_encoded();

   • Decode the result ("BX9ssyxWsz1zt2CAjTrDAnWhEA")

     std::vector<GeoCoordinates> polyline;
     hf::polyline_decode(
         encoded_polyline, [&polyline](double latitude, double longitude, double altitude) {
             polyline.emplace_back(latitude, longitude, altitude);
         });

     note: GeoCoordinates is a simple struct that holds only latitude, longitude and altitude (all of type double)

2. Expected result: a vector of GeoCoordinates, each element having longitude around 144.998
3. Actual result: a vector of GeoCoordinates, each element having longitude exactly "-69.7505"

[VeaaC]

I can properly decode BX9ssyxWsz1zt2CAjTrDAnWhEA on my local setup. This makes me suspect that their is some UB behaviour. I am going to look a bit into that. Would you mind providing some details about your setup (OS, compiler, compiler flags, etc)?

For testing I simply added:

void test_decode4() {
  std::vector<std::tuple<double, double, double>> polyline;
  auto res = hf::polyline_decode("BX9ssyxWsz1zt2CAjTrDAnWhEA",
                                 [&polyline](double lat, double lng, double z) {
                                   polyline.push_back({lat, lng, z});
                                 });
  assert_true(res);
  std::vector<std::tuple<double, double, double>> expected{{
      {-37.8312911, 144.9978678, 0}, //
      {-37.8313217, 144.9978624, 0}, //
      {-37.8313573, 144.9978559, 0}  //
  }};

  assert_eq(polyline.size(), expected.size());
  for (size_t i = 0; i < polyline.size(); ++i) {
    double delta_lat =
        std::abs(std::get<0>(polyline[i]) - std::get<0>(expected[i]));
    double delta_lng =
        std::abs(std::get<1>(polyline[i]) - std::get<1>(expected[i]));
    double delta_z =
        std::abs(std::get<2>(polyline[i]) - std::get<2>(expected[i]));
    assert_true(delta_lat <= 0.000001);
    assert_true(delta_lng <= 0.000001);
    assert_true(delta_z <= 0.000001);
  }
}

[michal1459]

After slightly modifying your test I was able to create a minimal working example: polyline-decode.cpp:

#include <iostream>
#include <tuple>
#include <vector>
#include <assert.h>
#include <sstream>
#include "flexpolyline.h"

void test_decode4() {
  std::vector<std::tuple<double, double, double>> polyline;
  auto res = hf::polyline_decode("BX9ssyxWsz1zt2CAjTrDAnWhEA",
                                 [&polyline](double lat, double lng, double z) {
                                   polyline.push_back({lat, lng, z});
                                 });
  assert(res);
  std::vector<std::tuple<double, double, double>> expected{{
      {-37.8312911, 144.9978678, 0}, //
      {-37.8313217, 144.9978624, 0}, //
      {-37.8313573, 144.9978559, 0}  //
  }};

  assert(polyline.size() == expected.size());

  for (size_t i = 0; i < polyline.size(); ++i) {
    double delta_lat =
        std::abs(std::get<0>(polyline[i]) - std::get<0>(expected[i]));
    double delta_lng =
        std::abs(std::get<1>(polyline[i]) - std::get<1>(expected[i]));
    double delta_z =
        std::abs(std::get<2>(polyline[i]) - std::get<2>(expected[i]));

    std::stringstream coordinates;
    coordinates << std::get<0>(polyline[i]) << ", " << std::get<1>(polyline[i]) << ", " << std::get<2>(polyline[i]);
    std::cout << coordinates.str() << '\n';
    // assert(delta_lat <= 0.000001);
    // assert(delta_lng <= 0.000001);
    // assert(delta_z <= 0.000001);
  }
}

int main ()
{
  test_decode4();
}

after compiling and running:

g++ --std=c++17 polyline-decode.cpp
./a.out

output is:

-37.8313, -69.7505, 0
-37.8313, -69.7505, 0
-37.8314, -69.7505, 0

OS: MacOS Catalina 10.15.6 (19G73)

g++ --version
Configured with: --prefix=/Users/michal/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Users/michal/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.0 (clang-1200.0.32.21)
Target: x86_64-apple-darwin19.6.0
Thread model: posix