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.