220 33220 <4a572c09-5142-4834-a907-93c3cc87e79c@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: federico.kircheis@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: safe integrals comparison Date: Sun, 16 Jul 2017 01:00:17 -0700 (PDT) Lines: 420 Approved: news@gmane.org Message-ID: <4a572c09-5142-4834-a907-93c3cc87e79c@isocpp.org> References: <66f9bab2-7220-4bf1-afb7-77c5efa1bac3@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_538_349762377.1500192018086" X-Trace: blaine.gmane.org 1500192028 19087 195.159.176.226 (16 Jul 2017 08:00:28 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 16 Jul 2017 08:00:28 +0000 (UTC) Cc: federico.kircheis@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCZ3PBGHYEBBBE52VTFQKGQEXHD674Y@isocpp.org Sun Jul 16 10:00:21 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f198.google.com ([209.85.161.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dWeTP-0004Ng-55 for gclcip-std-proposals@m.gmane.org; Sun, 16 Jul 2017 10:00:15 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id c13sf82996774ywa.13 for ; Sun, 16 Jul 2017 01:00:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=yIdJNqMwrWbUVSDHYwtmaymZwi6eOFihz5RGQipibzk=; b=lTg7w8v2Qn3y14IQqnPPNiJsD7RBbYg1QjjFwJ1ugSc5q8jHMFO51WpQ/mdoAQm8Vm aYZ2y44FqZTVM3+53w+y0PohcIcsIbFlnJezuLmnJoLGTKqY49+j5RGMCY8PWgiuE7a+ akWCqbPAO6c5j+FYVLdp+sJbS85YIJobHZnYlegr9m1kaa7lW752auYD9ZhgDggTc6qi 8iwxDjIljwclNaG1LWFBE9XH92v4gqfEt2kYNlaZK2G2J9+8GRut30bRcILMIQpeObjJ GzgxOJymwRj70td1kFkwdzEk2m6VSN9TdkMgmMccLd4NdXt4+6B6az4Qh+Tt7zI5h77E mXBA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=yIdJNqMwrWbUVSDHYwtmaymZwi6eOFihz5RGQipibzk=; b=q7Hcf7R/jctYHI8PNjGERkfpqI3LQRMfE12qinRJvFLblW93eU9L4iDj8NECnGFJc5 7VlV68QMdJoaR9pxkTxBz1xL8CCviYCf1LfjXiUEI+lvOQutbbjGLu0IkjJrzAJ9hwDJ EBbfRwYTS1ZQybeM4pBBkhVn+PqfKySwmpdhqNQujAJhihh7chxcwb5PJ45yzhUJ9aSS MtqwBt0T1l7TSlHPa1/JUvY+t0UwZeg45sdWjlK7kTtt0ALtHonX1W+t7ReVlZijh4B0 3OFjkUUsM8ILga7A9wcTDVe5xdyhHoQ8Ot0/YQatzFki3EoxKPMzfN0/5LjwSDPdrNdc 0QIA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:x-original-sender:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=yIdJNqMwrWbUVSDHYwtmaymZwi6eOFihz5RGQipibzk=; b=L8ubeHtMT3o/pRlC8r/bBAEUM3c/EHBOrZCvLfuFU8+O0wuZXY2wHFSMMJzOGG96OM eqvjo2/vrdhAieV+sjIx13ju3dqr5zeuItgyBrVXSlFW1wNMUheqqrGQLuCvcQu/bQkk iAKXx64hpV8fLxLdU6DmUw2EFCawAI9x24FYoys5GkkUz0WipMLMlwQi4L4exqV4F5Ty Zcg/yJakPrCQ2TYTXZjFXVzjBYvVu8o/Y9fd+Oz7iBVlKiKNp18z8R/mCGLAkUxJMhFO pYjWaOySpXv4a4LBNuJDtQ1KAFDqeGSz9YF5Nb1GaCoq0RDSqgp059zCZZE9lStvip+a ZADQ== X-Gm-Message-State: AIVw11396LJs98FLEyNWrXeRt+J8BZxXWHTbKAhffhzeH2/ydKKohvEG 0r5cioaitQ+yo8kG X-Received: by 10.129.172.104 with SMTP id z40mr10554898ywj.29.1500192020331; Sun, 16 Jul 2017 01:00:20 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.36.91.20 with SMTP id g20ls3646391itb.6.gmail; Sun, 16 Jul 2017 01:00:18 -0700 (PDT) X-Received: by 10.31.99.134 with SMTP id x128mr58587vkb.3.1500192018800; Sun, 16 Jul 2017 01:00:18 -0700 (PDT) In-Reply-To: <66f9bab2-7220-4bf1-afb7-77c5efa1bac3@isocpp.org> X-Original-Sender: federico.kircheis@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:33220 Archived-At: ------=_Part_538_349762377.1500192018086 Content-Type: multipart/alternative; boundary="----=_Part_539_1765635022.1500192018087" ------=_Part_539_1765635022.1500192018087 Content-Type: text/plain; charset="UTF-8" Another update to the proposal, I've added the references to Robert Ramey's proposal (and a link to an alternative implementation of the comparison functions in his github repository) and Herb Sutter's proposal for operator<=>. -- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/4a572c09-5142-4834-a907-93c3cc87e79c%40isocpp.org. ------=_Part_539_1765635022.1500192018087 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Another update to the proposal,

I've added the = references to Robert Ramey's proposal (and a link to an alternative imp= lementation of the comparison functions in his github repository) and Herb = Sutter's proposal for operator<=3D>.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/4a572c09-5142-4834-a907-93c3cc87e79c= %40isocpp.org.
------=_Part_539_1765635022.1500192018087-- ------=_Part_538_349762377.1500192018086 Content-Type: text/html; charset=US-ASCII; name=proposal.html Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=proposal.html X-Attachment-Id: 1746a96f-c239-4a45-b6af-058adc3784f5 Content-ID: <1746a96f-c239-4a45-b6af-058adc3784f5> Safe integral comparisons
Document number: P0586R0
Date: 2017-02-04
Project: Programming Language C++
Reply-to: Federico Kircheis

Safe integral comparisons

I. Table of Contents

II. Motivation

Comparing integrals of different types may be a more complex task than expected. Most of the time we expect that a simple 

	if(a < b){
		// ...
	} else {
		// ...
	}

should work in all cases, but if a and b are of different types, things are more complicated.
If a is a signed type, and b unsigned, then a is converted to the unsigned type. If a held a number less than zero, then the result may be unexpected, since the expression a < b could evaluate to false, even if a strictly negative number is always lower than a positive one.

Also converting integrals between different types can be challenging, for simplicity, most of the time we assume that values are in range, and write 

	a = static_cast<decltype(a)>(b);

If we want to write a safe conversion, we need to check if b has a value between std::numeric_limits<decltype(a)>::min() and std::numeric_limits<decltype(a)>::max(). We also need to pay attention that no implicit conversion (for example between unsigned and signed types) invalidates our comparison.

Comparing and converting numbers, even of different numeric types, should be a trivial task. Unfortunately it is not, and because of implicit conversions we may write, without noticing it, unsafe code.

III. Proposal

This paper proposes to add a set of constexpr and noexcept functions for converting and comparing integrals of different signeddes and precision (except for bool):

  • Two functions to compare if two variables represent the same value or not 
    	template <typename T, typename U>
	constexpr bool std::cmp_equal(T t, U u) noexcept;

	template <typename T, typename U>
	constexpr bool std::cmp_unequal(T t, U u) noexcept;
  • A set of functions that can be used to determine the relative order of two values 
    	template <typename T, typename U>
	constexpr bool std::cmp_less(T t, U u) noexcept;

	template <typename T, typename U>
	constexpr bool std::cmp_greater(T t, U u) noexcept;

	template <typename T, typename U>
	constexpr bool std::cmp_less_or_equal(T t, U u) noexcept;

	template <typename T, typename U>
	constexpr bool std::cmp_greater_or_equal(T t, U u) noexcept;
  • One function to determine if a specific value is inside the range of possible values of another type (i.e. if we can convert the value to the other type safely) 
    	template <typename R, typename T>
	constexpr bool in_range(T t) noexcept;
  • One function for retrieving the precision of a given numeric type 
    
	template <typename T>
	constexpr std::size_t std::precision() noexcept;

The function precision is part of the proposal because we cannot use the operator sizeof to determine between two types which one has a wider range (quote from SecureCoding):

Integer types in C have both a size and a precision. The size indicates the number of bytes used by an object and can be retrieved for any object or type using the sizeof operator. The precision of an integer type is the number of bits it uses to represent values, excluding any sign and padding bits. Padding bits contribute to the integer's size, but not to its precision. Consequently, inferring the precision of an integer type from its size may result in too large a value, which can then lead to incorrect assumptions about the numeric range of these types. Programmers should use correct integer precisions in their code, and in particular, should not use the sizeof operator to compute the precision of an integer type on architectures that use padding bits or in strictly conforming (that is, portable) programs.

The precision function does not have to be part of the proposal, but it seems an useful addition.

IV. Examples

Examples without current proposal

Comparing an unsigned int with an int:

	int a = ...
	unsigned int b = ...
	// added static_cast to avoid compiler warnings since we are doing a "safe" comparison
	if(a < 0 || static_cast<unsigned int>(a) < b){
		// do X
	} else {
		// do Y
	}

Comparing an uint32_t with an int16_t:

	int32_t a = ...
	uint16_t b = ...
	// added static_cast to avoid compiler warnings since we are doing a "safe" comparison
	if(a < static_cast<int32_t>(b)){
		// do X
	} else {
		// do Y
	}

Comparing an int with an intptr_t:

	int a = ...
	intptr_t b = ...
	if(???){ // no idea how to do it in one readable line without some assumption about int and intptr_t
		// do X
	} else {
		// do Y
	}

Example with current proposal

Comparing one integral type A with another integral type B (both non bool): 

	A a = ...
	B b = ...
	// no need for any cast since std::cmp_less is taking care of everything
	if( std::cmp_less(a,b)){
		// do X
	} else {
		// do Y
	}

V. Example implementation

This section shows an example of how precision, cmp_equal, cmp_less and in_range can be implemented with any standard conforming C++11 compiler. The only dependencies are the std::numeric_limits function from the limits header and some traits from the type_traits header. 


	#include <limits>
	#include <type_traits>

	template <typename T>
	constexpr std::size_t precision() noexcept;

	namespace details{
	#if defined(ERR_MSG_xxx_NEEDS_INTEGRAL_NOT_BOOL) || defined(ASSERT_INTEGRAL_NOT_BOOL_TYPE)
	#error "ERR_MSG_xxx_NEEDS_INTEGRAL_NOT_BOOL or ASSERT_INTEGRAL_NOT_BOOL_TYPE already defined"
	#endif
	#define ERR_MSG_xxx_NEEDS_INTEGRAL_NOT_BOOL " needs to be an integral (not bool) value type"
	#define ASSERT_INTEGRAL_NOT_BOOL_TYPE(T) static_assert(is_integral_not_bool<T>(), #T ERR_MSG_xxx_NEEDS_INTEGRAL_NOT_BOOL);

	template <typename T>
	constexpr bool is_integral_not_bool(){
		using value_type = typename std::remove_cv<T>::type;
		return !std::is_same<value_type,bool>::value && std::is_integral<T>::value;
	}

	template <class T>
	constexpr std::size_t pop(const std::size_t precision, const T num) {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		return (num == T{0}) ? precision : pop(((num % 2 != 0) ? precision+1 : precision), num >> 1);
	}


	// could use the same implementation of in_range_signed_signed, but compiler may generate warning that t is always bigger than 0
	template <typename R, typename T>
	constexpr bool in_range_unsigned_unsigned(const T t) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(R);
		return (precision<T>() > precision<R>()) ?
		    (t < static_cast<T>(std::numeric_limits<R>::max())) :
		    (static_cast<R>(t) <std::numeric_limits<R>::max());
	}

	template <typename R, typename T>
	constexpr bool in_range_signed_signed(const T t) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(R);
		return (precision<T>() > precision<R>()) ?
		    (t <= static_cast<T>(std::numeric_limits<R>::max()) && t >= static_cast<T>(std::numeric_limits<R>::min())) :
		    (static_cast<R>(t) <= std::numeric_limits<R>::max() && static_cast<R>(t) >= std::numeric_limits<R>::max());
	}

	template <typename R, typename T>
	constexpr bool in_range_signed_unsigned(const T t) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(R);
		return (t < T{ 0 }) ? false :
		    (precision<T>() / 2 <= precision<R>()) ? true :
		    (t <= static_cast<T>(std::numeric_limits<R>::max()));
	}

	template <typename R, typename T>
	constexpr bool in_range_unsigned_signed(const T t) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(R);
		return (precision<T>() >= precision<R>() / 2) ? (t <= static_cast<T>(std::numeric_limits<R>::max())) : true;
	}

	template <typename R, typename T>
	constexpr bool in_range_unsigned(const T t) noexcept {
		return std::is_unsigned<R>::value ? in_range_unsigned_unsigned<R>(t) : in_range_unsigned_signed<R>(t);
	}

	template <typename R, typename T>
	constexpr bool in_range_signed(const T t) noexcept {
		return std::is_signed<R>::value ? in_range_signed_signed<R>(t) : in_range_signed_unsigned<R>(t);
	}

	template <typename T, typename U>
	constexpr bool cmp_equal_same_sign(const T t, const U u) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(U);
		return (precision<T>()>precision<U>()) ? (t == static_cast<T>(u)) : (static_cast<U>(t) == u);
	}

	template <typename T, typename U>
	constexpr bool cmp_equal_signed_unsigned(const T t, const U u) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(U);
		return (t<T{ 0 }) ? false : (precision<T>() / 2>precision<U>()) ? (t == static_cast<T>(u)) : (static_cast<U>(t) == u);
	}

	template <typename T, typename U>
	constexpr bool cmp_less_same_sign(const T t, const U u) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(U);
		return (precision<T>()>precision<U>()) ? (t < static_cast<T>(u)) : (static_cast<U>(t) < u);
	}

	template <typename T, typename U>
	constexpr bool cmp_less_signed_unsigned(const T t, const U u) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(U);
		return (t<T{ 0 }) ? true : (precision<T>() / 2>precision<U>()) ? (t < static_cast<T>(u)) : (static_cast<U>(t) < u);
	}

	template <typename T, typename U>
	constexpr bool cmp_less_unsigned_signed(const T t, const U u) noexcept {
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(T);
		ASSERT_INTEGRAL_NOT_BOOL_TYPE(U);
		return (u<U{ 0 }) ? false : (precision<U>() / 2>precision<T>()) ? (static_cast<U>(t) < u) : (t < static_cast<T>(u));
	}

	#undef ERR_MSG_xxx_NEEDS_INTEGRAL_NOT_BOOL
	#undef ASSERT_INTEGRAL_NOT_BOOL_TYPE
	} // end details

	template <typename T>
	constexpr std::size_t precision() noexcept {
		return details::pop(0, std::numeric_limits<T>::max());
	}

	/// Usage:
	/// size_t i = ...
	/// if(in_range<DWORD>(i)){
	///  // safe to use i as a DWORD value, parameter...
	/// } else {
	///  // not possible to rappresent i as a DWORD
	/// }
	template <typename R, typename T>
	constexpr bool in_range(const T t) noexcept {
		return std::is_unsigned<T>::value ? details::in_range_unsigned<R>(t) : details::in_range_signed<R>(t);
	}

	// equivalent of operator== for different types
	/// Usage:
	/// size_t i = ...
	/// DWORD j = ...
	/// if(cmp_equal(i,j)){
	///  // i and j rappresent the same quantity
	/// } else {
	///  // i and j rappresents different quantities
	/// }
	template <typename T, typename U>
	constexpr bool cmp_equal(const T t, const U u) noexcept {
		return
		    (std::is_signed<T>::value == std::is_signed<U>::value) ? details::cmp_equal_same_sign(t, u) :
		    (std::is_signed<T>::value) ? details::cmp_equal_signed_unsigned(t, u) : details::cmp_equal_signed_unsigned(u,t);
	}

	// equivalent of operator< for different integral types
	/// Usage:
	/// size_t i = ...
	/// DWORD j = ...
	/// if(cmp_less(i,j)){
	///  // i < j
	/// } else {
	///  // i >= j
	/// }
	template <typename T, typename U>
	constexpr bool cmp_less(const T t, const U u) noexcept {
		return
		    (std::is_signed<T>::value == std::is_signed<U>::value) ? details::cmp_less_same_sign(t,u) :
		    (std::is_signed<T>::value) ? details::cmp_less_signed_unsigned(t, u) : details::cmp_less_unsigned_signed(t, u);
	}

VI. Effects on Existing Code

Since the proposed functions are not defined in any standard header, no currently existing code behavior will be changed.

VII. Design Decisions

Since there is no reason to compare true and false with other integral types, there isn't one to provide an overload for the bool integral type either.
The name of the functions (cmp_equal, cmp_less and others) are open to discussion, but the function names std::less and std::greater should not be used, since these do already exist, and have a different meaning.

In 2016, Robert Ramey did a much bigger proposal (see p0228r0) regaridng safe integer types. He also used similar functions proposed in this paper for implementing his classes and operators, therefore an alternative implementation can be found on his github repository. This proposal addresses a smaller problem, namely comparing integral values, and is therefore much smaller.
The functions provided can be also used for creating safe integer types.

Another work, by Herb Sutter (see p0515r0), is about a new comparison operator (<=>). As far as I've understood the proposal the operator<=> should compare correctly different integral types, making part of this proposal obsolete if the operator is added to the language. While it would be a nice thing to have, having a new comparison operator that operates differently from the old operators may be counterintuitive and cause confusion, even if the new behaviour is more correct.

------=_Part_538_349762377.1500192018086-- .