Discussion :

[stendhal666]

J'ai écrit sur mon blog un billet décrivant l'analyse syntaxique monadique. Je voudrais écrire une suite pour comparer avec l'analyse syntaxique d'un document .csv dans un langage impératif (j'ai choisi le C++).

Il me faut donc un analyseur de .csv en C++. Je me débrouille pas mal mais je voudrais avoir des conseils et avis pour aboutir à un code idiomatique, esthétique et performant (dans cet ordre) pour que la comparaison soit le plus équitable possible (il ne s'agira pas au bout de déclarer un vainqueur, mais de montrer les différences d'approche et les éventuels points forts/points faibles).

Un petit rappel sur le format csv:il nous faut
- un séparateur de ligne
- un séparateur de colonne
- ignorer ces séparateurs lorsqu'ils apparaissent dans un champ placé entre guillemets
- permettre, au sein des champs entre guillemets, l'utilisation du caractère "guillemet", qui doit être doublé (ex: "name;"John\"\"the Snake\"\" Smith" => name / John "the Snake" Smith)

l'input est représenté sous forme de std::istream. Je vois un certain nombre de stratégies possibles. La première qui me vient à l'esprit est d'utiliser une forme modifiée de getline, puis d'appliquer une fonction splitIntoCells aux strings obtenues:

- la fonction getCsvLine est simple (mais dangereuse à élaborer: il faut s'appuyer sur std::getline et non sur istream::get car ils ont des sémantiques différentes: en particulier, quand elle rencontre eof, std::getline n'allume pas le flag failbit, tandis que istream::get le fait ):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
std::istream& getCsvLine(std::istream& is, std::string& res) {
  std::string tmp; // il faut un stockage temporaire car getline réinitialise la std::string passée en argument avant de la remplir
  for (;;) {
    std::getline(is, res);
    tmp += res;
    if ((std::count(tmp.begin(), tmp.end(), '"') % 2) == 0) break;
  }
  res = tmp;
  return is;
}

- la fonction splitIntoCells serait:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::vector<std::string> splitIntoCells(const std::string& line) {
  std::vector<std::string> res;
  bool quoted = false;
  std::string::const_iterator a = line.begin();
  for (std::string::const_iterator b = a; b < line.end(); ++b) {
    if (*b == '"') quoted = !quoted;
    if (*b == ';' && !quoted) {
      res.push_back(suppressExtraQuotes(std::string(a,b))); // il faut supprimer les guillemets qui font partie du format mais pas du contenu
      a = b+1;
    }
  }
  res.push_back(suppressExtraQuotes(std::string(a,line.end())));
  return res;
}

Elle n'est pas très élégantes et plutôt "bas niveau" mais une formulation de plus haut niveau implique des allers-retours dans la std::string:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<std::string> splitIntoCellsB(const std::string& line) {
  std::vector<std::string> res;
  for (std::string::const_iterator b = line.begin();;) {
    std::string::const_iterator f = std::find(b, line.end(), ';');
    while (std::count(b, f, '"') % 2 == 1) { // tant que les guillemets ne sont pas fermés
      f = std::find(f+1, line.end(), ';');    // on continue à chercher
    }
    res.push_back(suppressExtraQuotes(std::string(b,f)));
    if (f == line.end()) break;
    b = ++f;
  }
  return res;
}

Je mets également la fonction spécial-guillemets:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
std::string suppressExtraQuotes(const std::string& s) {
  std::string tmp = s, res;
  if (*tmp.begin() == '"') tmp = std::string(tmp.begin()+1, tmp.end()-1); // on enlève les guillemets de début et de fin
  for (std::string::iterator it = tmp.begin(); it < tmp.end(); ++it) {
    res.push_back(*it);
    if (*it == '"') ++it; // si c'est un guillemet on saute le prochaine caractère (aussi un guillemet)
  }
  return res;
}

Il ne reste plus qu'à écrire une fonction qui prenne un fichier en argument:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
std::vector<std::vector<std::string> > parseCSV(std::istream& is) {
  std::vector<std::vector<std::string> > res;
  std::string line;
  while (getCsvLine(is, line)) {
    res.push_back(splitIntoCells(line);
  }
  return res;
}

Donc ma question: est-ce que cela vous paraît un code acceptable (hors bibliothèques spécialisées et autres regexp, évidemment)? Avez-vous des propositions d'amélioration?
Merci d'avance!

[white_tentacle]

J’ai un article en cours qui doit sortir sur justement ce sujet (en gros, il est en relecture technique pour l’instant, j’espère pouvoir le publier d’ici la fin du mois).

Du coup je ne vais pas répéter ici son contenu. Néanmoins, deux trois remarques rapides :
- splitter d’abord en ligne, puis en champ, c’est un peu idiot. Il vaut mieux parser des champs tant que tu en rencontres, et construire le résultat au fur et à mesure. Là tu fais le travail deux fois.
- pareil pour ta suppression de guillemets. Si tu regardes bien, tu parcours la chaîne plusieurs fois : une fois pour voir s’il y a des guillemets, une fois pour construire la sous-chaîne, une fois (au moins, je n’ai pas regarder comment tu as implémenté suppressExtraQuotes) pour lui enlever ses guillemets. C’est deux de trop.
- std vector de std vector de string est une mauvaise structure de résultat. Un csv est globalement un tableau à deux dimensions, et très souvent on va avoir une ligne d’en-têtes qui donne le nom des colonnes. On va vouloir accéder aux éléments de chaque ligne par le nom de leur colonne.
- et un dernier point qui casse toute ton analyse :

toto;ti"ti;tata

est un cas qu’on peut rencontrer (la RFC 4180 le déconseille, mais j’ai vu des programmes le produire).

[stendhal666]

J’ai un article en cours qui doit sortir sur justement ce sujet (en gros, il est en relecture technique pour l’instant, j’espère pouvoir le publier d’ici la fin du mois).

Too bad. C'est vraiment dommage pcq tes remarques me paraissent très justes mais vont me demander bcp de travail si je veux les incorporer... Ce ne serait pas possible d'avoir au moins le nom de quelques techniques à considérer?

- et un dernier point qui casse toute ton analyse :
toto;ti"ti;tata
est un cas qu’on peut rencontrer (la RFC 4180 le déconseille, mais j’ai vu des programmes le produire).

Là en revanche, je ne sais pas si je dois m'en préoccuper. La norme ne déconseille pas mais interdit:

Each field may or may not be enclosed in double quotes (however
some programs, such as Microsoft Excel, do not use double quotes
at all). If fields are not enclosed with double quotes, then
double quotes may not appear inside the fields.

[white_tentacle]

Too bad. C'est vraiment dommage pcq tes remarques me paraissent très justes mais vont me demander bcp de travail si je veux les incorporer... Ce ne serait pas possible d'avoir au moins le nom de quelques techniques à considérer?

Alors en gros, machine à état pour l’analyse, et analyseur traversant avec callbacks pour la production du résultat. Ça sera effectivement compliqué d’intégrer tout ça, car pour moi tu es parti sur mauvaise piste au départ (getline). Il y a beaucoup de choses à dire sur le sujet, c’est ça qui m’a motivé à en faire un article .

Là en revanche, je ne sais pas si je dois m'en préoccuper. La norme ne déconseille pas mais interdit:

double quotes may not appear inside the fields.

Attention lors de la lecture d’une norme / RFC. may not != must not, should != must. may not = fortement déconseillé, must not = interdit. En gros, tu ne devrais pas produire des fichiers ayant des double quote au milieu d’un champ non lui-même entre double quote, mais il n’est pas impossible que tu en rencontres.

[ternel]

Ca dépend des normes, il y en a qui définissent ces mots en préambule.
Et en règle générale, pour des formats textes, il faut s'attendre à des violations.

[stendhal666]

Alors en gros, machine à état pour l’analyse, et analyseur traversant avec callbacks pour la production du résultat. Ça sera effectivement compliqué d’intégrer tout ça, car pour moi tu es parti sur mauvaise piste au départ (getline). Il y a beaucoup de choses à dire sur le sujet, c’est ça qui m’a motivé à en faire un article .

J'ai changé de piste comme tu le suggérais mais de toute façon, machine à état et analyseur traversant dépasseront assez largement le cadre de ma comparaison... J'attends ton article avec impatience en tout cas!

Attention lors de la lecture d’une norme / RFC. may not != must not, should != must. may not = fortement déconseillé, must not = interdit. En gros, tu ne devrais pas produire des fichiers ayant des double quote au milieu d’un champ non lui-même entre double quote, mais il n’est pas impossible que tu en rencontres.

Ah eh bien! non seulement il faut apprendre un anglais spécial pour comprendre les normes mais en plus on peut trouver un guillemet tout seul au milieu d'un champ qui n'en est pas encadré! Moi qui croyais choisir un exemple simple avec ce format csv...

[ternel]

L'exemple simple, c'est un sous-ensemble maitrisé et défini.
Parce que le CSV peut aussi être délimité par des deux-points (colon) ou des virgules (comma) c'est d'ailleurs cette dernière qui donne son nom au format.

Il me semble même qu'on peut faire d'autres siouxeries

au passage, en C++ (et en C), le caractère " se note '"' car il n'a pas besoin d'être échappé dans un caractère litéral.

[white_tentacle]

Il me semble même qu'on peut faire d'autres siouxeries

L’encodage est la première source d’emmerdes dans la vraie vie. D’autant que les logiciels ont des valeurs par défaut qui diffèrent, et que les utilisateurs finaux ne comprennent généralement pas cette notion (contrairement au séparateur pour lequel ils voient bien ce que c’est).

[stendhal666]

Bon, quelques essais plus tard, j'ai l'impression de tenir quelque chose de pas trop mal:

- une fonction parseField, qui branche verse parseQuotedField si le champ commence par des guillemets:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::istream& parseField(std::istream& is, std::string& res, bool& eol) {
  if (is.rdstate() & std::ios::eofbit) { // cette machinerie est nécessaire à cause du comportement de istream::get (eof => fail)
    is.clear(std::ios::failbit);
    return is;
  }
  if (is.peek() == '"') return parseQuotedField(is, res, eol);
  res = "";
  eol = false;
  char c;
  while (is.get(c)) {
    if (c == ';') return is;
    if (c == '\n') { eol = true; return is; }
    res.push_back(c);
  }
  if (is.rdstate() & std::ios::eofbit) {
    is.clear(std::ios::eofbit);
  }
  return is;
}

- l'équivalent donc pour un champ entre guillemets:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
std::istream& parseQuotedField(std::istream& is, std::string& res, bool& eol) {
  res = "";
  eol = false;
  char c;
  is.ignore(); // on passe le guillemet en première position
  while (is.get(c)) {
    if (c == '"') {
      if (is.peek() == '"') {
        res.push_back(c);
        is.ignore();
      }
      else if (c == ';') {
        is.ignore();
        return is;
      }
      else if (c == '\n') {
        is.ignore();
        eol = true;
        return is;
      }
    }
    else res.push_back(c);
  }
  if (is.rdstate() & std::ios::eofbit) {
    is.clear(std::ios::eofbit);
  }
  return is;
}

- et une fonction d'entrée

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<std::vector<std::string> > parseCSV(std::istream& is) {
 
  std::vector<std::vector<std::string> > vvs;
  std::vector<std::string> vs;
  std::string s;
  bool b;
 
  while (parseField(is, s, b)) {
    vs.push_back(s);
    if (b) {
      vvs.push_back(std::move(vs));
    }
  }
  vvs.push_back(std::move(vs));
  return vvs;
}

A priori ça passe même pour des guillemets perdus dans un champ qui n'est pas prévu à cet effet! j'ai testé avec un stringstream initialisé avec: "123;12\"4;125\n126;127;\"128\n129\";\"130\"\"131\"\";132"

Je ne marque pas tout de suite la discussion comme résolue au cas où d'autres conseils viendraient!

PS: @whitetentacle je retiens les remarques sur les headers et le fait qu'il vaudrait mieux pouvoir accéder au colonnes par nom, mais cela dépasse un peu le cadre de ce dont j'ai besoin pour mon billet.

[white_tentacle]

Rapidement :

je n’aime pas « peek ». Soit on lit et on consomme, soit on lit pas. peek veut généralement dire qu’on lit deux fois.

Du coup je réécrirai plutôt ça comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
char c;
if(!is.get(c))
   return is;
if(c == '"')
   return parseQuotedField(is, res, eol);
do {
  if (c == ';') return is;
  if (c == '\n') { eol = true; return is; }
  res.push_back(c);
} while(is.get(c))

et modifier parseQuotedField (pour ne plus enlever le guillemet qui est déjà enlevé, et de la même manière, pour ne pas faire de peek() ).

Dernière remarque, mais je pense que là aussi c’est au-delà de ce que tu veux pour ton billet : il n’y a aucune gestion d’erreur / de validité du fichier.

[stendhal666]

Rapidement :

je n’aime pas « peek ». Soit on lit et on consomme, soit on lit pas. peek veut généralement dire qu’on lit deux fois.

Du coup je réécrirai plutôt ça comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
char c;
if(!is.get(c))
   return is;
if(c == '"')
   return parseQuotedField(is, res, eol);
do {
  if (c == ';') return is;
  if (c == '\n') { eol = true; return is; }
  res.push_back(c);
} while(is.get(c))

Je vais tester ça, mais à cause de la sémantique de get, qui met automatiquement le flag failbit en même temps que le flag eofbit (ce qui fait sortir une fois trop tôt de la boucle: while {parseField(...) }) ça peut être moins coûteux pour moi de faire un peek.

Dernière remarque, mais je pense que là aussi c’est au-delà de ce que tu veux pour ton billet : il n’y a aucune gestion d’erreur / de validité du fichier.

Ce serait bien pour mon billet. Comme ça, ça me fout plutôt la pétoche mais en y réfléchissant, je me dis qu'il n'y a qu'un signe d'erreur, qui est que les records aient un nombre de fields variable, non? pour le reste il y a une certain ambiguïté j'ai l'impression.

[white_tentacle]

Ce serait bien pour mon billet. Comme ça, ça me fout plutôt la pétoche mais en y réfléchissant, je me dis qu'il n'y a qu'un signe d'erreur, qui est que les records aient un nombre de fields variable, non? pour le reste il y a une certain ambiguïté j'ai l'impression.

Rapidement et de mémoire, il y a en plus du cas du nombre de colonnes inconsistant :
* l’enregistrement entre guillemets pas terminé (en fin de fichier uniquement, du coup)
* la chaîne entre quote avec une simple quote au milieu (par exemple titi;"to"to";tutu )

[foetus]

Le fichier .csv ce n'est que de l'ANSI, pas d'unicode.
Il faut passer par un fichier .slk (SYLK) (<- qui lui est méchant )

Ce gros couillon d'Excel au lieu de mettre des virgules ou des points virgules, il met des ... tabulations


Je ne comprends pas vos craintes sur la double quote

État: "entre 2 double quotes"
Si '\' -> je dois tester le caractère après
Si ';' -> Erreur, double quote non fermée
Si '"' -> je rentre dans l'état "entre une double quote fermante et le ';'"
Si '\n' ou '\r' -> Erreur, double quote non fermée
Sinon -> je mange (c'est un algo glouton)

État "entre une double quote fermante et le ';'"
Si '\n' ou '\r' -> Test sur le nombre de colonnes de la ligne
Si '"' -> Erreur ou je rentre dans l'état "entre 2 double quotes"
Si ';' -> Test sur le nombre de colonnes et/ ou je passe à la colonne suivante
Si ' ' -> je ne fais rien
Sinon -> erreur, ou alors on peut avoir des caractères après une double quotes (<- je ne le sais pas )

[stendhal666]

@foetus: quand tu le dis ça paraît simple mais tu t'en donnes les moyens avec une machine à états pour commencer...

Une question complémentaire d'ordre conceptuel sur la gestion des erreurs: si on met de côté l'idée de validation du fichier, c'est-à-dire que l'objectif est prioritairement l'utilisation du fichier et pas la vérification de son respect de la norme, est-ce qu'il ne vaut pas mieux reporter la gestion de certaines erreurs après l'analyse du fichier?

Par exemple, pour la question du nombre égal de colonnes, on pourrait imaginer de proposer à l'utilisateur une "mise aux normes" en ajoutant le nombre adéquat de colonnes vides dans les lignes qui n'en ont pas assez, ou de façon plus conservatrice au moins lister les lignes qui ont un nombre inférieur de colonnes? Dans ces cas-là on admet que le but n'est pas de reporter l'erreur au moment où elle se produit mais après avoir parcouru l'ensemble du fichier.

[white_tentacle]

Il ne faut pas faire la validation de « structure » dans l’analyseur lui-même, en effet. Après tu as deux choix :
* tu construis dans tous les cas toute la structure, et tu valides à la fin
* tu valides au fur et à mesure, afin de pouvoir t’arrêter si jamais il y a une erreur (inutile d’analyser > 100Mo de données s’il y a une erreur au début)

C’est un des points que j’aborde dans mon article : cette gestion doit être choisie par l’utilisateur final, et certainement pas imposée par l’analyseur.

[ternel]

En fait, ca dépend de l'usage que tu veux faire du csv.
Dans mon projet actuel, on utilise des csv, et on ajoute de temps en temps des colonnes supplémentaires pour "documenter les cas de tests".
Par exemple:

cle1;cle2;cle3;valeur1;valeur2;valeur3
cle1;cle2;;valeur1;valeur2;valeur3; cle3 manquante

Le fichier utile ne fait que six colonnes, mais notre parseur ne s'inquiète pas des colonnes en trop. Volontairement.

Tu peux aussi savoir à l'avance le format métier du fichier, et parser directement chaque ligne dedans, avec un stream concu pour.

[stendhal666]

Je conclus de vos deux réponses que l'idéal est de pouvoir paramétrer la gestion des exceptions. C'est vrai qu'il s'agit de deux emplois différents de la norme:
- cas1 : le format csv est utilisé pour communiquer des données entre deux applications, la norme doit être respectée pour éviter de coupler le comportement des deux -> analyse rigoriste, on quitte dès la première erreur pour éviter de perdre du temps
- cas2 : le format csv est utilisé pour sa simplicité et on accepte des dérogations pour accentuer sa souplesse -> analyse souple, on récupère le max en supposant que celui qui a dérogé à la norme sait ce qu'il fait.

Ca pourrait fournir une ouverture intéressante à mon billet. Comment s'y prendre pour le côté C++ néanmoins?
- Rajouter un argument aux fonctions (ou une variable de classe pour une classe CsvParser) et faire des branches: if (strict) throw BadCsvField; else etc. // c'est un peu bourrin mais je soupçonne qu'une machine à état gérerait ces embranchements élégamment
- Avec les classes d'exceptions en argument template? Mais j'ai l'impression que revenir dans le flux normal du programme après avoir lancé une exception n'est pas aisé
- what else?

[ternel]

On ne lit pas "du csv", mais "des données au format csv".
Je vais comparer au xml pour donner une idée plus générale.

Pour charger des données dans un fichier on a deux étapes.

1. sortir du fichier
2. entrer dans les données métier

En xml, par exemple, sortir du fichier, c'est passer d'un flot de caractères à un arbre de noeuds.
En csv, c'est arriver à un ensemble de lignes.
Cette étape peut avoir des erreurs en xml (balise mal fermée, par exemple), mais assez peu en csv. éventuellement, les fameux guillemets

Puis vient l'interprétation.
En xml, on a un seul élément, le document racine, dont on peut extraire des parties selon le besoin.
En csv, par contre, on en a plusieurs: autant que de lignes.

Une économie serait d'interpréter chaque ligne quand elle est extraite, et décider quoi faire en cas d'erreur.
En faisant une fonction analysant la ligne, il s'agit juste d'attraper son erreur et au choix: passer à la ligne suivante ou rejeter le fichier complet.

La représentation en sortie du fichier est normalement générique, et peut se coder aveuglément.
C'est ce que contiennent les bibliothèques.

Pour le csv, on a (a priori) deux formes possibles:

1. la séquence de lignes
2. la séquence de séquences de champs

Entrer dans les données métier est spécifique, et ne doit pas être codée génériquement.
Par contre, il est très important que la bibliothèque fournisse les bons outils.

Pour du csv, a priori, j'imaginerai bien une conversion en tuple<>, des accesseurs par champ brut (std::string field()) et typés (T as<T>())

Pour de l'xml, par comparaison, on veut pouvoir accéder aux noeuds via xpath, mais aussi aux fils, parent, ou voisins d'un noeud.


De là, tu as deux approches, le parseur sauvage, qui va lire tout le fichier immédiatement, et le parseur à la demande, qui avance d'une unité logique.
Idéalement, le mode sauvage demandera un itérateur d'insertion (input iterator) pour lire stocker les données lues, un peu comme le fait std::copy.

Le mode "à la demande" ou "en flux" permet de ne pas mettre tout le fichier en mémoire.
C'est comme cela que fonctionne sed. (d'ailleurs, c'est amusant d'utiliser sed sur du csv. laborieux, mais puissant)

[white_tentacle]

Puis vient l'interprétation.
En xml, on a un seul élément, le document racine, dont on peut extraire des parties selon le besoin.
En csv, par contre, on en a plusieurs: autant que de lignes.

Oui et non. Il y a plusieurs manières de travailler sur du XML, la plus courante est l’arbre DOM. Pour csv, il est effectivement possible de définir une représentation « agnostique » sous forme de tableau de lignes, chaque ligne étant elle-même un tableau de chaînes.

MAIS, et c’est un point important, ce n’est pas le boulot de l’analyseur de déterminer dans quelle structure les résultats de l’analyse doivent être stockés. C’est le boulot de l’utilisateur final, qui peut éventuellement utiliser une structure générique fournie par la lib, mais en aucun cas ne doit y être obligé. Pour poursuivre l’analogie avec XML : la bonne manière de lire du xml (celle qu’on devrait presque toujours utiliser, les cas où on a réellement besoin de travailler sur l’arbre dom sont rares) est SAX. Pour csv, ce sera de la même manière une lecture « évènementielle ».

Pour la gestion des erreurs, le mot-clé est « politique ». Les classes de politiques sont justement là pour permettre de modifier le comportement. ET il est important de pouvoir arrêter l’analyse CSV avant la fin si on sait que les données sont moisies (par exemple, on veut lire des entiers, et on a une chaîne bidon à la place).

[stendhal666]

Pour la gestion des erreurs, le mot-clé est « politique ».

- On parle bien des classes "Policy" du modern C++? C'est ce que je voulais évoquer (maladroitement) en parlant de "classes d'exceptions en argument template". Donc le principe de base serait d'avoir un parseur paramétré (entre autres) dans le genre de:

template <ErrorPolicy>
std::istream& parseField(std::istream& is, std::string& field, ErrorPolicy& checker) {
// analyser le prochain champ
checker.check(champ); // selon le ErrorPolicy choisi, enverra une exception en cas d'erreur, ou loggera l'erreur, ou ne fera rien du tout
return is;
}

?

- et sur DOM/SAX, il est clair que SAX a des capacités supplémentaires mais j'ai une vision un peu nébuleuse de la façon de le mettre en oeuvre... Il va falloir que j'attende ton article, je pense...