Logically dead code in Collinear_3.h - static analysis

[GilesBathgate]

Issue Details

In the following code the value of of int_tmp_result is either set to 1, or -1 or the function is exited early via the returns. Then sign_of_determinant_return_value (which is assigned from int_tmp_result) is checked to see if it is not equal to 0, which by the above code will always be true, so the function exits with return false;

cgal/Filtered_kernel/include/CGAL/internal/Static_filters/Collinear_3.h

Lines 74 to 104 in 16fc8d1

	if (max1 < lower_bound_1)
	lower_bound_1 = max1;
	else if (max1 > upper_bound_1)
	upper_bound_1 = max1;
	int int_tmp_result;
	if (lower_bound_1 < 5.00368081960964635413e-147)
	return Base::operator()(p, q, r);
	else
	{
	if (upper_bound_1 > 1.67597599124282407923e+153)
	return Base::operator()(p, q, r);
	double eps = (8.88720573725927976811e-16 * (max1 * max2));
	if (double_tmp_result > eps)
	int_tmp_result = 1;
	else
	{
	if (double_tmp_result < -eps)
	int_tmp_result = -1;
	else
	return Base::operator()(p, q, r);
	}
	}
	int sign_of_determinant_return_value = int_tmp_result;
	if (sign_of_determinant_return_value != 0)
	return false;
	double dpz = (pz - rz);
	double dqz = (qz - rz);

The remaining code in the function is therefore never executed. Either this is an indication of a different bug, or the dead code should be removed.

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux
• Compiler: gcc
• Release or debug mode: Release
• Specific flags used (if any): None
• CGAL version: 5.0.2
• Boost version: 1.71.0
• Other libraries versions if used (Eigen, TBB, etc.): Qt 5.12.8

[mglisse]

I confirm that this looks suspicious. IIUC, the code is trying to find a reason to return false, by projecting along each of the axes in turn, before calling the base function. This seems to indicate that all the return Base::operator()(p, q, r); except the very last one are premature and should instead jump to the next projection (i.e. set int_tmp_result=0). That would explain why the code is formatted the way it is (there is no point using an else block if the then block returns).
Well, at least, calling the base function is always safe, just possibly a missed optimization.
(by the way, since we don't use the sign, std::abs(double_tmp_result)>eps seems simpler than 2 tests)

[lrineau]

The code was added @sgiraudot by commit 4665299 of PR #2136. It seems the code was actually genereated (probably by FPG). The corresponding FT code is:

cgal/Cartesian_kernel/include/CGAL/predicates/kernel_ftC3.h

Lines 92 to 109 in 8698331

	template < class FT >
	CGAL_KERNEL_MEDIUM_INLINE
	typename Equal_to<FT>::result_type
	collinearC3(const FT &px, const FT &py, const FT &pz,
	const FT &qx, const FT &qy, const FT &qz,
	const FT &rx, const FT &ry, const FT &rz)
	{
	FT dpx = px-rx;
	FT dqx = qx-rx;
	FT dpy = py-ry;
	FT dqy = qy-ry;
	if (sign_of_determinant(dpx, dqx, dpy, dqy) != ZERO)
	return false;
	FT dpz = pz-rz;
	FT dqz = qz-rz;
	return CGAL_AND( sign_of_determinant(dpx, dqx, dpz, dqz) == ZERO ,
	sign_of_determinant(dpy, dqy, dpz, dqz) == ZERO );
	}

Probably FPG was not smart enough.

[mglisse]

Ah, yes, generated code would explain the strange variable names 😄
Side remark: the code in kernel_ftC3.h uses CGAL_AND to avoid forcing a conversion to bool too early, but it converts the first sign!=ZERO to bool eagerly, that seems inconsistent. I think it could mimic CGAL_AND, store the first result as s, early out if certainly(s), and combine s with the final result. And the code could probably be shared with parallelC3, which currently doesn't bother trying to save the last 2 subtractions.

[afabri]

Would that be the right improvement:

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
collinearC3(const FT &px, const FT &py, const FT &pz,
            const FT &qx, const FT &qy, const FT &qz,
            const FT &rx, const FT &ry, const FT &rz)
{
  FT dpx = px-rx;
  FT dqx = qx-rx;
  FT dpy = py-ry;
  FT dqy = qy-ry;

  Uncertain<bool> not_zero = sign_of_determinant(dpx, dqx, dpy, dqy) != ZERO;
  if (certainly(not_zero))
      return false;
  FT dpz = pz-rz;
  FT dqz = qz-rz;
      return CGAL_AND( ! not_zero,
                       sign_of_determinant(dpx, dqx, dpz, dqz) == ZERO ,
                       sign_of_determinant(dpy, dqy, dpz, dqz) == ZERO );
}

[afabri]

I am also wondering if we should not use CGAL::is_zero()

[afabri]

The above code adresses @mglisse remark "I think it could mimic CGAL_AND, store the first result as s, early out if certainly(s), and combine s with the final result.".

[mglisse]

not_zero could be of type auto, and you can directly use !not_zero & CGAL_AND(...) instead of CGAL_AND_3 since not_zero has already been tested. But yes, I think I probably had something like that in mind.

[afabri]

As not_zero might be uncertain, would it then not throw an Uncertain_exception before the logical & ? Don't we first have to give the expressions inside the CGAL_AND a chance for a decisions with interval arithmetic ? So either by putting !not_zero in the CGAL_AND or by writing CGAL_AND(...) & !not_zero.

[mglisse]

CGAL_AND is implemented as certainly_not(a) ? make_uncertain(false) : a & make_uncertain(f_b()). Since we have already done the certainly_not(a) ? make_uncertain(false) part 2 lines above, I meant go straight to a & make_uncertain(f_b()) (operator& is overloaded for Uncertain<bool>). operator& should be symmetric, the order of its arguments should not matter. It is true that if the xz test is certainly false, we will uselessly compute maybe&false or true&false, but that seems negligible.
Am I misunderstanding something?