Affichage des articles dont le libellé est sémantique. Afficher tous les articles
Affichage des articles dont le libellé est sémantique. Afficher tous les articles

mardi 6 janvier 2015

Arithmétique des pointeurs...et fonctions...

Dans mon éternelle quête de l'inépuisable Graal, je viens de découvrir (naïf que je suis) que l'arithmétique des pointeurs révèle des surprises. Je passe outre le fait que les débordements de tableaux via les pointeurs sont des comportements plus étranges qu'il n'y paraît. Le standard indique à propos de la sémantique de l'arithmétique:
Section 6.5.6/8 Additive operators. When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated. 
Oui j'ai bien lu (pas vous ?): If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. Ce qui signifie en clair que l'on peut pointer à l'adresse qui suit immédiatement le dernier élément d'un tableau et que l'adresse stockée dans le pointeur est quelque chose une véritable adresse correctement calculée quand bien même on ne doit pas déréférencer le pointeur (c'est le end des itérateurs C++); mais pointer plus loin est un comportement non défini. Autrement dit, un programme faisant une telle opération ne peut être considéré comme juste, ce n'est pas un programme C! Attention c'est non-défini pas non-spécifié, par conséquent le compilateur/le runtime sont libres de faire ce qu'il veulent (y compris réinstaller Windows par-dessus votre cher Linux rien que pour vous punir).

Bon mais ma question originelle était le problème de l'arithmétique sur les pointeurs de fonction! Soit l'exemple suivant :
void f() {
  // super code génial
}
...
void (*pf)();
pf = f;
pf();
// Ok je vois bien
pf++;
pf(); // Argh!
...
Dans ce cas, il est évident que le second appel serait bien étrange, mais prenons l'exemple suivant:
void f() {
  // mega code trop bien
}
void g() {
  // hyper code trop cool
}
void magic(int i) {
  (f+(g-f)*i)();
}
L'idée étant que si on appelle magic(0) c'est f qui s'exécute et si on appelle magic(1) c'est g. Une compilation ordinaire ne dit rien et le code fonctionne. Si l'on active le standard c99, rien non plus. Par contre le mode pédant :
$ gcc --std=c99 -pedantic -c t.c
t.c:10:8: warning: arithmetic on pointers to the function type 'void ()' is a
      GNU extension [-Wpointer-arith]
  (f+(g-f)*i)();
      ~^~
t.c:10:5: warning: arithmetic on a pointer to the function type 'void ()' is a
      GNU extension [-Wpointer-arith]
  (f+(g-f)*i)();
Argh, l'arithmétique sur les pointeurs de fonctions est donc encore plus limitée ? Voyons ce qu'en dit le standard alors :
6.5.6/3 Additive operators. For subtraction, one of the following shall hold:
—  both operands have arithmetic type;
—  both operands are pointers to qualified or unqualified versions of compatible complete object types; or
—  the left operand is a pointer to a complete object type and the right operand has integer type.
What is object type ??? Appelons le standard de Cognacq-Jay:
6.2.5/1 Types. The meaning of a value stored in an object or returned by a function is determined by the type of the expression used to access it. (An identifier declared to be an object is the simplest such expression; the type is specified in the declaration of the identifier.) Types are partitioned into object types (types that describe objects) and function types (types that describe functions). At various points within a translation unit an object type may be incomplete (lacking sufficient information to determine the size of objects of that type) or complete (having sufficient information).
Bon ben ok, ben les pointers to functions types n'ont donc pas d'arithmétique! Ben voilà... Je suis déçu, encore une fois j'ai la preuve que je ne possède pas le Craal.

DjiBee

mercredi 29 janvier 2014

Have you ever encountered a compiler bug ?

Bon, c'est pas la première fois que ça m'arrive mais cette fois j'ai mis du temps à réagir... Pour préparer un nouvel article sur le C++11 je testais différentes choses autour des rvalue-references. L'article viendra plus tard donc... Finalement les problèmes rencontrés n'avaient rien à voir avec les rvalue-references, mais je m'entêtais; il a fallu du temps pour extraire la substantifique moelle. Mon exemple sur les rvalue-references essayait de montrer comment ce mécanisme permet d'optimiser le code en évitant de dupliquer trop d'objets en autorisant le contrôle des déplacements de valeur; comme les compilateurs C++ font aussi de l'élimination de copie (voir un billet précédent) je souhaitais donc supprimer la copy-elision afin d'effectuer des mesures sur un code analysable simplement par lecture de son code source. Finalement, le problème a surgit quand bien même les rvalue-references ne sont pas utilisées. Voici le code qui pose problème :
#include <iostream>
#include <string>
#include <utility>
using namespace std;

int main() {
  string s = string("11") + "22" + "33" + "44";
  cout << s << endl;

  string s2 = "11";
  cout << s2 << endl;

  string s3 = s2 + "22";
  cout << s3 << endl;
  return 0;
}
Bien entendu, les deux premières lignes sont bien suffisantes, mais j'ai laissé quelques autres petites tests mineurs.
Premier test avec une compilation ordinaire (donc avec copy-elision) :
% g++ -o rv4 rv4.cpp
% ./rv4
11223344
11
1122
Rien de mystérieux ni d'anormal. Compilons en enlevant la copy-elision :
% g++ -fno-elide-constructors -o rv4 rv4.cpp
% ./rv4

11

Comme on l'observe facilement, il y a un problème; mais l'observation n'est pas complète car cet exemple est trop épuré. Avec des structures plus complexes que les string l'effet est tout à fait surréaliste, les structures de données sont dans des états bizarres et les affichages difficilement interprétables.
Pire, en compilant en conformité avec le standard C++11, le résultat n'est pas le même!
% g++ -std=c++11 -fno-elide-constructors -o rv4 rv4.cpp
% ./rv4                                            
11223344
11

Lorsque ceci est mélangé à l'utilisation de la sémantique de déplacement (move) je vous laisse imaginer ma perplexité lorsque combiné avec un type un poil plus subtil utilisant des pointeurs et de l'allocation dynamique!
Alors quelle version de g++ est impactée ? Il semble que de nombreuses le soient. La mienne est :
% g++ --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin13.0.0
Thread model: posix
%
Le rapport de bug est disponible ici. L'un des commentaires daté du 11 janvier 2014 indique que le bug a été corrigé, ce que je n'ai pu encore tester mais que je m'empresserais de faire à la prochaine mise à jour. Si vous êtes intéressé par la correction, la voici : commit.

Conclusion : doit-il y a voir une conclusion ? Peut-être que la réalité de l'informatique nous oblige à croire que nous faisons naturellement trop d'erreurs et avons donc un défaut de confiance en notre propre code, voire trop de confiance en les compilateurs. Vivement les compilateurs certifiés... Je sais il y en a et des français y travaillent : citons Xavier Leroy (ou sa page Wikipedia) et Cminor, ou quelqu'un de plus proche encore de nous : YuRuG. Ou encore, vivement des spécifications pas trop tordues pour les langages, peut-être C++ est-il arrivé dans un état qui causera sa propre perte ? ou l'enfermera dans une niche d'où il ne sortira plus ?

DjiBee

jeudi 16 janvier 2014

C++, "copy elision" et copy-initialization

What the hell are these ?

Prenons une classe C++ ordinaire définissant un constructeur à un argument, un constructeur par copie et un destructeur, soit :

#include <iostream>
using namespace std;

class MaClasse {
public:
  MaClasse(int i) {
    cout << "ctor " << this << " avec i=" << i << endl;
  }
  MaClasse(const MaClasse &m) {
    cout << "ctor " << this << " avec " << &m << endl;
  }
  ~MaClasse() {
    cout << "dtor " << this << endl;
  }
};

int main() {
  MaClasse c1(1);
  MaClasse c2 = 2;

  cout << "fin" << endl;
  return 0;
}

Compilons ordinairement avec gcc (par exemple), puis exécutons :

% g++ -o test test.cpp
% ./test
ctor 0x7fff52a7f9d8 avec i=1
ctor 0x7fff52a7f9d0 avec i=2
fin
dtor 0x7fff52a7f9d0
dtor 0x7fff52a7f9d8
%

Ceci donne à penser qu'on obtient une construction ordinaire dans les deux cas, en utilisant le fait qu'on a à faire à la syntaxe d'initialisation traditionnelle, e.g. int i=4, et fonctionnelle, e.g. int i(4), sachant que l'existence d'un constructeur à un argument autorise (soit-disant) cette syntaxe d'initialisation par uniformité syntaxique.

En réalité, la sémantique est plus complexe (désormais?) puisque si cette fois on compile de la façon suivante, on obtient :

% g++ -fno-elide-constructors -o test test.cpp
% ./test
ctor 0x7fff4fce09d8 avec i=1
ctor 0x7fff4fce09c8 avec i=2
ctor 0x7fff4fce09d0 avec 0x7fff4fce09c8
dtor 0x7fff4fce09c8
fin
dtor 0x7fff4fce09d0
dtor 0x7fff4fce09d8
%

Où l'on observe qu'un objet temporaire (celui d'adresse 0x7fff4fce09c8) a été créé à l'aide d'un constructeur à un argument (avec la valeur 2), puis que cet objet temporaire a été utilisé dans la construction par copie pour l'objet désiré in-fine. L'objet temporaire étant alors immédiatement détruit.

Le mécanisme est dit de copy elision, puisque, par défaut dans gcc, on élimine cette copie inutile (création d'un objet temporaire, copie, puis suppression) afin d'éviter des constructions/destructions trop nombreuses (la plaie de la programmation objet mal contrôlée).
Bien entendu, ce mécanisme est employé élégamment lors des passages d'arguments de type objet et retour de fonctions afin d'éviter les copies lors de passage par valeur (la plaie du C++).

Néanmoins, il me semble que le mécanisme ne devrait pas être visible pour les initialisations, si effectivement on utilisait une simple uniformité syntaxique de sorte que O o(v) serait syntaxiquement équivalent à O o=v. Ce que l'expérience prouve être faux (pour s'en convaincre encore il suffit de qualifier le constructeur à un argument d'explicit, ce qui a pour effet de provoquer une erreur de compilation dans les deux cas).

Dans l'expérience, il semble donc que l'opérateur d'initalisation = soit traité à la manière de l'opérateur d'affectation =, c'est-à-dire que le compilateur tente d'effectuer une conversion de la valeur vers une valeur du type de l'objet à affecter, puis réaliser l'affectation; ceci dans le cadre d'une initialisation, d'où le refus lorsqu'explicit est employé.
Or initialisation et affectation sont a-priori des opérations bien différentes et pourraient être traitées comme telles. Ici, privilège est donné à la construction par copie, à laquelle une élision est appliquée, d'ailleurs :

La norme C++11 précise l'existence de trois syntaxes d'initialisation :
  1. T x(a)
  2. T x = a
  3. T x{a}
Note: pour le troisième cas, prière de compiler avec -std=c++11.

D'après §8.5 de la norme ISO/IEC JTC1 SC22 WG21 N 3690, les cas 1 et 3 sont appelés direct-initialization, signifiant ainsi qu'aucun objet temporaire n'est requis.
Le cas 2 est appelé copy-initialization, signifiant que l'objet x est normalement créé par copie d'un objet de type compatible; mais que la copy elision permet d'éliminer (voir §12.8).

L'enfer se cache dans les détails…
Il n'existe pas d'équivalence syntaxique ou sucre syntaxique (du moins pour les types objets) entre initialisation avec liste à un argument et initialisation avec opérateur =, pas d'équivalence opérationnelle non plus d'ailleurs (sauf dans le cas de l'optimisation par élision), il n'y a qu'une équivalence sémantique (dénotationnelle) entre initialisation avec liste d'argument à un argument et initialisation avec opérateur =.
Djibee

Wanna play with direct and copy initialization ? See Herb Sutter problem #36.

lundi 13 janvier 2014

Qu'est ce que st_nlink exactement ?

Le problème est de déterminer si l'interprétation HFS+ (le système de fichier natif de MacOSX) est conforme au standard POSIX. En général, on considère l'interprétation conduisant à déduire du nombre de liens associés à un inœud de type répertoire, le nombre de sous-répertoires qu'il possède (en supposant d'ailleurs qu'aucun hard-link n'est autorisé autrement que via mkdir()).

Les gnous en disent :
The number of hard links to the file. This count keeps track of how many directories have entries for this file. If the count is ever decremented to zero, then the file itself is discarded as soon as no process still holds it open. Symbolic links are not counted in the total.

Le standard POSIX 1003.1-1988 affirme :
§5.6.1 The value of the member st_nlink shall be set to the number of links to the file. 
§2.3 link. See directory entry. 
§2.3 directory entry (or link). An object that associates a filename with a file. Several directory entries can associate names with the same file.
Creusons un peu plus loin dans POSIX :
§2.3 file. An object that can be written to, or read from, or both. A file has certain attributes, including access permissions and type. File types include regular file, character special file, block special file, FIFO special file, and directory. Other types of files may be defined by the implementation.
§2.3 filename. A name consisting of 1 to [NAME_MAX] bytes used to name a file. The characters composing the name may be selected from the set of all character values excluding the slash character and the null character. The filenames dot and dot-dot have a special meaning; see pathname resolution §2.4. A filename is sometimes referred to as a pathname component.
Ce qui est remarquable (à mes yeux) est que dans ces définitions aucune référence explicite n'est faite au contenant des directory entries. On suppose habituellement que les directory entries sont nécessairement contenues dans des fichiers de type répertoire, mais ce n'est nullement précisé. Ce qui est précisé c'est le contenu d'un répertoire :
§2.3 directory. A file that contains directory entries. No two directory entries in the same directory shall have the same name.
Par conséquent, il n'est pas (à mes yeux) interdit d'imaginer que st_nlink pour les répertoires se comporte comme dans MacOSX, c'est-à-dire correspond au nombre d'entrées dans le répertoire. À tout fichier HFS+ correspond un lien vers le répertoire qui le contient.

Attention! Je ne prétends pas ici que HFS+ est POSIX-compliant! D'ailleurs qu'est-ce que cela signifierait ? Les filesystems ne sont pas en eux-même conformes à une norme sémantique, fusse t-elle POSIX. Les systèmes de fichiers ne sont que des structures de données, il n'y a qu'une couche logicielle qui puisse imposer une sémantique. J'affirme donc que la sémantique POSIX est respectée par le couple OSX/HFS+, autrement dit que via OSX la sémantique est respectée. D'ailleurs OSX n'est autre que Darwin, une personnalité FreeBSD de Mach. Je l'affirme a contrario de nombreux articles Internet sur le sujet.

Question subsidiaire : existe t-il dans une distribution Unix classique (je n'ai pas de définition autre que le sens commun) un outil standard qui utilise la valeur du champ st_nlink pour faire quelque chose d'intéressant ? J'exclue d'office un outil type fsck dont le rôle est justement d'examiner la structure du filesystem à des fins de réparation par exemple...

DjiBee