yohhoyの日記

技術的メモをしていきたい日記

atoi関数のかしこい実装

C標準ライブラリ Muslのatoi関数実装 では、符号付き整数オーバーフロー回避のため負数範囲で10進数値を減算してゆき最後に符号反転を行っている。

int atoi(const char *s)
{
  int n=0, neg=0;
  while (isspace(*s)) s++;
  switch (*s) {
  case '-': neg=1;
  case '+': s++;
  }
  /* Compute n as a negative number to avoid overflow on INT_MIN */
  while (isdigit(*s))
    n = 10 * n - (*s++ - '0');
  return neg ? n : -n;
}

C言語の符号付き整数型(int)では “2の補数” 表現が用いられるため*1、最大値INT_MAXより最小値INT_MINの絶対値が 1 だけ大きくなり(例:16bit幅ならINT_MAX = 32767, INT_MIN = -32768)、正数範囲の累積計算では値-INT_MINを表現できず未定義動作(undefined behavior)を引き起こしてしまう。*2

その他のC標準ライブラリ実装(glibc, BSD libc, Newlib)では、単純にstrtol関数へ実装移譲している。

int atoi (const char *s)
{
  return (int) strtol (s, NULL, 10);
}

ノート:int型よりlong型の値域が広い場合strtol関数戻り値キャストで未定義動作(undefined behavior)となるが、そもそもC標準ライブラリatoi関数仕様では「戻り値がint型の値域外となる場合の動作は未定義(the behavior is undefined)」とされるため何ら問題はない。いいね?

  • 2022-01-08追記:longint型変換において変換先の符号付き整数型で表現きない値の場合、処理系定義(implementation-defined)の値が得られるか処理系定義のシグナルが発生する(thanks to emkさんコメント)。

C99 3.4.3/p3, 7.20.1/p1, 7.20.1.4/p8より引用(下線部は強調)。

EXAMPLE An example of undefined behavior is the behavior on integer overflow.

The functions atof, atoi, atol, and atoll need not affect the value of the integer expression errno on an error. If the value of the result cannot be represented, the behavior is undefined.

The strtol, strtoll, strtoul, and strtoull functions return the converted value, if any. If no conversion could be performed, zero is returned. If the correct value is outside the range of representable values, LONG_MIN, LONG_MAX, LLONG_MIN, LLONG_MAX, ULONG_MAX, or ULLONG_MAX is returned (according to the return type and sign of the value, if any), and the value of the macro ERANGE is stored in errno.

関連URL

*1:C17現在は “1の補数(ones' complement)” または “符号と絶対値(sign and magnitude)” 表現も許容されるが、次期規格C2xでは “2の補数(two's complement)” のみ許容と改定される。提案文書(PDF)N2412参照。

*2:符号付き整数オーバーフローは、標準規格での明示的な定義が無いことをもって未定義動作とされる(C99 4/p2)

関数型への参照型にまつわる特例ルール

プログラミング言語C++の関数型(function type)には左辺値(lvalue)しか存在しないが(→id:yohhoy:20200530)、左辺値参照型(R (&)(Args...))/右辺値参照型(R (&&)(Args...))いずれにも束縛できる。そう、よかったね。

#include <utility>
using std::move;  // 右辺値参照型(T&&)を返す関数

void f() {}
// 関数型void()
void ( &lref1)() = f;        // OK
void (&&rref1)() = f;        // OK: 右辺値参照型だがlvalue束縛可能
void ( &lref2)() = move(f);  // OK: 関数型の式move(f)はlvalue
void (&&rref2)() = move(f);  // OK: 右辺値参照型だがlvalue束縛可能
// (関数型のprvalueは存在しない)

int n = 42;
// 通常の型(int)
int&  lref3 = i;        // OK
int&& rref3 = i;        // NG: 右辺値参照型はlvalue束縛不可
int&  lref4 = move(i);  // NG: 左辺値参照型はxvalue束縛不可
int&& rref4 = move(i);  // OK
int&  lref5 = 42;       // NG: 左辺値参照型はprvalue束縛不可
int&& rref5 = 42;       // OK

関数オーバーロード解決では関数型への左辺値参照型が優先されるため、あいまいさは存在しない。(C++17 16.3.3.2/p3)

C++17 11.6.3/p5より一部引用(下線部は強調)。

A reference to type "cv1 T1" is initialized by an expression of type "cv2 T2" as follows:

  • If the reference is an lvalue reference and the initializer expression
    • is an lvalue (but is not a bit-field), and "cv1 T1" is reference-compatible with "cv2 T2", or
    • (snip)
  • Otherwise, the reference shall be an lvalue reference to a non-volatile const type (i.e., cv1 shall be const), or the reference shall be an rvalue reference. (snip)
    • If the initializer expression
      • is an rvalue (but not a bit-field) or function lvalue and "cv1 T1" is reference-compatible with "cv2 T2", or
      • (snip)

関数型の右辺値は存在しない

プログラミング言語C++に「関数型(function type)の右辺値(rvalue)」は存在しない。関数型をもつ式の value category は常に左辺値(lvalue)となる。だから何?

int v;
struct S s;
void f();

std::move(v);  // xvalue
std::move(s);  // xvalue
std::move(f);  // lvalue

static_cast<void(&)()>(f);   // lvalue
static_cast<void(&&)()>(f);  // lvalue
static_cast<void(*)()>(f);   // prvalue(関数ポインタ型)
void g(void(&)());   // #1
void g(void(&&)());  // #2

g(f);  // #1を呼び出す
g(std::move(f)); // #1を呼び出す

別途 Function-to-pointer 変換によって、関数型の lvalue は関数ポインタ型の prvalue へと変換されうる。*1

C++17 7/p6, 8.2.2/p11 より引用(下線部は強調)。*2

The effect of any implicit conversion is the same as performing the corresponding declaration and initialization and then using the temporary variable as the result of the conversion. The result is an lvalue if T is an lvalue reference type or an rvalue reference to function type (11.3.2), an xvalue if T is an rvalue reference to object type, and a prvalue otherwise. The expression e is used as a glvalue if and only if the initialization uses it as a glvalue.

A function call is an lvalue if the result type is an lvalue reference type or an rvalue reference to function type, an xvalue if the result type is an rvalue reference to object type, and a prvalue otherwise.

C++11に右辺値参照が追加されたとき、新しい概念の導入による複雑化を避けるため特別扱いされた。(PDF)N3055 Background より一部引用。

In addition, rvalue references (like traditional lvalue references) can be bound to functions. Treating an rvalue reference return value as an rvalue, however, introduces the novel concept of a function rvalue into the language. There was previously no such idea -- a function lvalue used in an rvalue context becomes a pointer-to-function rvalue, not a function rvalue -- so the current draft Standard does not describe how such rvalues are to be treated. In particular, function calls and conversions to function pointers are specified in terms of function lvalues, so most plausible uses of rvalue references to functions are undefined in the current wording.

関連URL

*1:C++17 7.3/p1: "An lvalue of function type T can be converted to a prvalue of type "pointer to T". The result is a pointer to the function."

*2:static_cast式, reinterpret_cast式, キャスト式でも rvalue reference to function type へのキャスト結果は lvalue と定義されている(8.2.9/p1, 8.2.10/p1, 8.4/p1)

C2x標準の属性(attribute)

プログラミング言語Cの次期仕様C2x(C23)では 属性(attribute) 構文が標準化される。属性構文を先行導入したC++言語とほぼ等価であり、連続するブラケット[[]]を用いる。*1

// C2x
[[nodiscard]] int f();

void g([[maybe_unsed]] int a) {
  [[maybe_unused] int x;
  /* ... */
}

struct [[deprecated("old ver.")]] S {
  /*...*/
};

int n = f();
switch (n) {
case 0:
case 1:
  f();
  [[fallthrough]];
default;
  g(n);
  break;
}

属性指定を行える箇所:

  • 構造体(struct)/共用体(union)の型宣言
  • 列挙型(enum)の型宣言
  • 列挙子(enumerator)の定義
  • 変数/関数仮引数の宣言
  • 関数の宣言/定義
  • 任意の文(statement)

2020年2月時点のC2xドラフト*2で追加される属性は下記4種類
2022-08-07追記:Feature Freeze版とされる2022年8月時点のC2xドラフト*3で追加される属性は下記7種類*4

  • nodiscard(→(PDF) N2267
    • 2021-02-28追記:(PDF) N2448 nodiscard("should have a reason") も採択済み。
  • maybe_unused(→(PDF) N2270
  • deprecated, deprecated("string-literal")(→(PDF) N2334
  • fallthrough(→(PDF) N2408
  • 2022-07-26追記:noreturn, _Noreturn(→(PDF) N2764
    • C11で導入された<stdnoreturn.h>標準ヘッダ、_Noreturn関数指定子(function specifier)、およびC2xの_Noreturn属性ともに廃止予定(obsolescent feature)とされる。
  • 2022-08-07追記:reproducible, unsequenced(→N2956)(→id:yohhoy:20220909

C++属性構文との共通点/差分:

  • C++同様に、処理系定義(implementation-defined)の属性を許容する。未知の属性は無視される。
  • C++同様に、処理系定義の属性用に名前空間(相当)を指定できる。*5
  • C2xの属性attrは前後にアンダースコア2つを追加した__attr__と同義。例:[[nodiscard]][[__nodiscard__]]は同じ属性を表す。
  • 2021-07-17追記:属性の重複指定を許容する(→(PDF) N2557)。C++2b(C++23)側もWG21 N2156R1を採択予定。
  • 2022-08-07追記:__has_c_attribute機能テストマクロ(→(PDF) N2553
    • C++20__has_cpp_attribute機能テストマクロのC言語版。*6

関連URL

*1:C2x/C++いずれの言語仕様でも新規トークン [[ や ]] は導入せず、“ブラケット [ または ] が2トークン連続(空白を挟んでもよい)” を属性の開始/終了として扱う。

*2:http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2478.pdf

*3:https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3047.pdf

*4:いずれもプログラム意味論には影響を与えず、標準属性を無視してもプログラム動作は変化しない。それぞれC2x標準属性のサポートは処理系定義のオプションとされるが、各処理系は標準属性を実装することが推奨(recommended)される。

*5:C言語には名前空間(namespace)が存在しないため、属性構文でのみ利用する専用の構文要素 attribute-prefix とコロン2つからなる新しいトークンを導入している。┐(´-`)┌

*6:https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0941r2.html

コンストラクタ/デストラクタ×仮想関数呼び出し

C++においてコンストラクタ/デストラクタからの仮想関数呼び出しそれ自体はwell-definedだが、おそらくC++プログラマの期待する振る舞いではない。

バグの温床になりえるため、大抵のコーディング規約で禁止している(はず)。かつてClangに本件を検知する警告オプションが提案*1されたが放棄された模様。

struct Base {
  Base() {
    // コンストラクタ中での仮想関数呼び出しは
    // B::vfを呼び出す(D::vfではない!)
    vf();  
  }
  void g() {
    // 通常(非static)メンバ関数中からであれば
    // オーバーライドされたD::vfを呼び出す
    vf();
  }
  virtual void vf() { /*...*/ }
};

struct Derived : Base {
  virtual void vf() override { /*...*/ }
};

Derived obj;
obj.g();

純粋仮想関数(pure virtual function)が呼び出される場合は未定義動作(undefined behavior)を引き起こす。*2

struct Interface {
  Interface() {
    vf();  // NG: 純粋仮想関数の呼び出し!
  }
  virtual void vf() = 0;
};

struct Concrete : Interface {
  virtual void vf() override { /*...*/ }
};

Concrete obj;

プログラムのバグであることが自明なため、GCCやClangはコンパイル時に警告として報告する。MSVCの場合はプログラム実行時エラー。

  • GCC:pure virtual 'virtual void Interface::vf()' called from constructor
  • Clang:warning: call to pure virtual member function 'vf' has undefined behavior; overrides of 'vf' in subclasses are not available in the constructor of 'Interface'

C++17 15.7/p3より引用(下線部は強調)。C++11/14では12.7/p4。

Member functions, including virtual functions (13.3), can be called during construction or destruction (15.6.2). When a virtual function is called directly or indirectly from a constructor or from a destructor, including during the construction or destruction of the class's non-static data members, and the object to which the call applies is the object (call it x) under construction or destruction, the function called is the final overrider in the constructor's or destructor's class and not one overriding it in a more-derived class. If the virtual function call uses an explicit class member access (8.2.5) and the object expression refers to the complete object of x or one of that object's base class subobjects but not x or one of its base class subobjects, the behavior is undefined. [Example:

struct V {
  virtual void f();
  virtual void g();
};

struct A : virtual V {
  virtual void f();
};

struct B : virtual V {
  virtual void g();
  B(V*, A*);
};

struct D : A, B {
  virtual void f();
  virtual void g();
  D() : B((A*)this, this) { }
};

B::B(V* v, A* a) {
  f();     // calls V::f, not A::f
  g();     // calls B::g, not D::g
  v->g();  // v is base of B, the call is well-defined, calls B::g
  a->f();  // undefined behavior, a's type not a base of B
}

-- end example]

関連URL

*1:https://reviews.llvm.org/D56366 New warning call-to-virtual-from-ctor-dtor when calling a virtual function from a constructor or a destructor

*2:C++17 13.4/p6: "Member functions can be called from a constructor (or destructor) of an abstract class; the effect of making a virtual call to a pure virtual function directly or indirectly for the object being created (or destroyed) from such a constructor (or destructor) is undefined."

macOSはPOSIX無名セマフォをサポートしない

macOS(旧Mac OS X)では POSIX無名(unnamed)セマフォ を意図的にサポートしない。
無名セマフォ生成sem_initや破壊sem_destroy関数呼び出しはerrno=ENOSYS(function not supported)/戻り値-1で常に失敗する。(おまけ:sem_getvalue関数も非サポート)

名前無しセマフォDispatchSemaphore で代替可能。一般的にはObjective-CやSwiftから呼び出す GCD(Grand Central Dispatch)ランタイム の一部だが、C言語APIとして提供されるためネイティブC/C++コードからも利用できる。
実装例:https://github.com/yohhoy/yamc/blob/master/include/gcd_semaphore.hpp

2009年4月頃のTerry Lambert氏*1メールより一部引用。

They aren't required for UNIX conformance because they are not mandatory interfaces per Appendix 9 of the Single UNIX Specification, and there are lots of alternatives, most of them with better overall semantics, which this tread has amply demonstrated. Most portable and historical software uses System V semaphores, since POSIX semaphores are relatively new, so there's little software portability incentive. The software which does like to use them is typically based on GNU autoconf/automake which typically uses linkage tests to find interfaces and blows it by doing that and ignoring <unistd.h> contents, since historical conformance with older versions of the specification permitted stub functions which errored out, and the linkage tests only check linkability rather than functionality. So basically the software that wants them usually fails to conform to the standards which would have allowed them to be used safely and reliably in the first place.

Then there is the little problem of binary backward compatibility for POSIX named semaphores, if the error or success returns don't happen to match the standard once testing of a full implementation became possible.

As a Mac OS X implementation detail, sem_t is the required data type for both POSIX named semaphores and POSIX unnamed semaphores according to the standard. The sem_t definition has historically been a 32 bit value containing an fd cast to a pointer, which is problematic for maintaining binary and source backward compatibility (hint: think symbol decoration) for named semaphores while at the same time permitting typical usage of unnamed semaphores. Specifically, typical usage of unnamed semaphores is to use them as an IPC synchronization mechanism between otherwise unrelated programs by allocating a shared memory region shared between them of sizeof(sem_t) *number_of_semaphores_desired, and the casting the base address of that memory region to a (sem_t *) and indexing off that to get a semaphore index in the range 0..(number_of_semaphores_desired - 1).

The implementation problems should now be obvious. They are not insurmountable; I sometimes pose how to resolve the conflicting goals involved as an interview question. 8-). But there isn't really a very obvious fix I'd call elegant, either.

https://lists.apple.com/archives/darwin-kernel/2009/Apr/msg00010.html

関連URL

*1:同氏はMac OS Xカーネルの6%を書いたとのこと。https://www.quora.com/profile/Terry-Lambert

Objective-C的 null(nil)安全

Objective-Cにおいてメッセージ送信先のレシーバがnilの場合、Objective-Cランタイムはなにもしない(エラーは発生せずメソッドも呼び出されない)。メソッドが戻り値型を持つ場合、値 0 相当が返却されたかのように振る舞う。

Sending Messages to nil
In Objective-C, it is valid to send a message to nil -- it simply has no effect at runtime. There are several patterns in Cocoa that take advantage of this fact. The value returned from a message to nil may also be valid:

  • If the method returns an object, then a message sent to nil returns 0 (nil). For example:
Person *motherInLaw = [[aPerson spouse] mother];

If the spouse object here is nil, then mother is sent to nil and the method returns nil.

  • If the method returns any pointer type, any integer scalar of size less than or equal to sizeof(void*), a float, a double, a long double, or a long long, then a message sent to nil returns 0.
  • If the method returns a struct, as defined by the OS X ABI Function Call Guide to be returned in registers, then a message sent to nil returns 0.0 for every field in the struct. Other struct data types will not be filled with zeros.
  • If the method returns anything other than the aforementioned value types, the return value of a message sent to nil is undefined.
The Objective-C Programming Language, Objects, Classes, and Messaging

ノート:利便性という観点では他プログラミング言語でいうOptional型に似ており、メソッドチェインを簡潔に記述できるようになっている。一方でコンパイラやランタイムによる検査機構がないことで、本質的なバグを潜在化させて問題を先送りするという危険性もある。

関連URL