Le très bizarre QRegExp

L'analyse de fichiers texte est un problème commun dans la programmation journalière. En général, l'écriture d'analyseurs prend du temps et est difficile. De nombreux problèmes peuvent être évités en utilisant des expressions régulières : faciles et amusantes à écrire, elles sont aussi faciles à adapter pour respecter les spécifications changeantes. Cependant, il faut faire attention aux nombreux pièges qui peuvent être évités avec un peu d'attention, comme dans le premier exemple.

Une tâche habituelle est de trouver des paires équilibrées, comme des parenthèses ouvrantes et fermantes, ou bien des balises SGML. Par exemple, cette expression régulière permet de trouver le texte mis en évidence dans un document HTML.

QRegExp rx( "<(em|i)>.*</\\1>" );
rx.setCaseSensitive( FALSE );

L'expression régulière <(em|i)>.*</\\1> signifie :

Rechercher <, puis em ou i, puis >, ensuite zéro ou plus de caractères divers, ensuite </, puis em et i, et finalement, >

Cependant, pour le moment, le HTML accepte des espaces dans les balises, une meilleure expression régulière serait :

QRegExp rx( "<\\s*(em|i)\\s*>.*<\\s*/\\s*\\1\\s*>" );

Par défaut, les expressions régulières sont avides, et essayent de faire correspondre autant de texte que possible. Par exemple, dans la chaîne

Un drapeau <i>noir</i>, <i>jaune</i> et <i>rouge</i>

Cette expression régulière ferait correspondre <i>noir</i> <i>jaune</i> <i>rouge</i >, au lieu de simplement <i>noir</i>. La solution est d'appeler

rx.setMinimal( TRUE );

Pour demander à QRegExp de sélectionner le strict minimum, c'est-à-dire <i>noir</i>.

Une alternative qui ne requiert pas setMinimal() et qui donne des résultats équivalents serait de remplacer .* par [^<]*, qui va être mis en relation avec seulement < au lieu de rien du tout. Malheureusement, ces deux solutions sont très fragiles, parce qu'elles ne peuvent réussir sur des paires enchâssées, comme, par exemple :

Un peu de txte <i><i><i>fort</i>ement</i> en <i>i</i>talique</i>.

Ceci est un problème régulier avec les expressions régulières, et une des raisons pour lesquelles des analyseurs complets sont requis dans certaines situations. D'un autre côté, si vous pouvez être garanti que le HTML est libre de telles constructions (sûrement parce que le code est généré par votre application) vous pouvez analyser très simplement du HTML avec des expressions régulières comme celle ci-dessus.

Toute application peut, très facilement, lire et écrire leurs propriétés grâce à QSettings, ce qui, internement, utilise des fichiers de configuration ou le registre Windows. Or, relativement souvent, nous voulons lire et écrire des fichiers de configuration dans un format de fichiers personnel. QRegExp est utile dans ces situations. La majorité des fichiers de configuration, dont les fichiers .pro de qmake, contiennent des entrées de la forme clé = valeur, comme, par exemple :

# calc.pro
SOURCES = appwindow.cpp \
      main.cpp
TARGET  = calc

Analyser ce genre de fichiers n'est pas trivial, car le format autorise des quantités très arbitraires d'espaces, et peut avoir des entrées sur plusieurs lignes, avec la barre oblique inverse (\). Nous allons écrire un analyseur très simple de fichiers .pro, avec QRegExp.

QFile in( "calc.pro" );
if ( !in.open(IO_ReadOnly) )
	return;
QString text = in.readAll();
in.close();

En premier, nous lisons un fichier, ici calc.pro, dans un QString.

text.replace( QRegExp("#[^\n]*"), "" );
text.replace( QRegExp("\\\\\\s*\n"), " " );
text.replace( QRegExp("\\s*\n\\s*"), "<END>" );
text.replace( QRegExp("="), " = " );
text = text.simplifyWhiteSpace();

Nous canonicalisons la forme du fichier. Les commentaires sont enlevés, et les entrées sur plusieurs lignes, ramenées sur une seule, avec un espace qui finit chaque ligne. Ensuite, nous nous assurons qu'il y a un seul et unique espace entre chaque signe d'égalité. Chaque entrée possède un marqueur <END> à la fin. Nous ne pouvons, en effet, pas garder simplement les \n originaux, car QString::simplifyWhiteSpace les remplace par des espaces.

QStringList lines = QStringList::split( "<END>", text );
QStringList::Iterator line = lines.begin();
while ( line != lines.end() )
{
	QStringList toks = QStringList::split( " ", *line );
	QStringList::Iterator it = toks.begin();

	if ( toks.count() >= 3 && toks[1] == "=" )
	{
	    QString key = *it++;
	    it++;
	    while ( it != toks.end() )
		{
			process_value( key, *it++ );
	    }
	}
	++line;
}

Nous séparons tout le texte en quelques lignes, et les séparons en pièces détachées, plus faciles à manier. Nous prenons chacune de ces pièces comme une clé en ignorant le signe d'égalité, et utilisons les pièces restantes comme valeurs. Et c'est tout : un analyseur simple de fichiers .pro en une vingtaine de lignes !

Notre troisième application de QRegExp est un programme qui convertit les commentaires // en commentaires /* ... */ Un tel programme pourrait être utile pour porter du code du C++ vers du C.

Il serait tentant d'écrire ceci :

text.replace( QRegExp("//([^\n]*)(\n|$)"), "/*\\1 */\\2" );

Malheureusement, ceci ne fonctionne pas. L'expression régulière remplacerait, en effet, les occurrences de // dans les commentaires /* ... */, et dans les chaînes de caractères.

Une approche plus sophistiquée utiliserait une expression dans ce genre :

QRegExp rx( "(//([^\n]*)(\n|$)|/\\*.*\\*/|\"([^\\\\]|\\\\.)*\"" );
rx.setMinimal( TRUE );

L'expression consiste en trois parties alternatives :

1. //([^\n]*)(\n|$), qui reconnaît les commentaires à la C++ ;
2. /\\*.*\\*/, qui s'occupe des commentaires à la mode C ;
3. \"([^\\\\]|\\\\.)*\", qui identifie les chaînes de caractères.

L'on désire un strict minimum de correspondances, pour les mêmes raisons que dans l'exemple du HTML. Sans cela, en effet, nous pourrions faire commencer un commentaire à un /* et le faire finir au */ d'un autre.

L'expression régulière contient trois paires de parenthèses. Le texte qu'elles récupèrent est disponible avec QRegExp::cap, cap(2), et cap(3). Ici, nous n'utiliserons que cap(1). Nous aurions pu utiliser des parenthèses non-capturantes (?:...) au lieu de (...), dans les deux autres cas.

Nous pouvons utiliser cette expression dans une boucle.

int pos = 0;
while ( (pos = rx.search(text, pos)) != -1 )
{
	if ( rx.cap(1).startsWith("//") )
	{
	    QString before = rx.cap( 1 );
	    QString after = "/*" + before.mid( 2 ) + " */";
	    text.replace( pos, before.length(), after );
	    pos += after.length();
	}
	else 
	{
	    pos += rx.matchedLength();
	}
}

Ceci marchera dans tous les cas, sauf si un commentaire // contient */. Pour des cas aussi rares, une correction à la main est la solution la plus pratique.

Nous allons maintenant regarder le fonctionnement interne de QRegExp, et revoir quelques techniques pour son utilisation efficace sur de grandes quantités de données. Faites attention : les détails de l'implémentation ici présentés peuvent changer dans une version ultérieure de Qt (NdT : les versions 3.1 et supérieures. Actuellement, seule la 4.5 va apporter quelques changements). De plus, la plupart des programmes n'ont absolument pas besoin de ces optimisations.

QRegExp rx( "de+f" );

Ceci convertit la chaîne de+f dans une structure plus complexe pour des résultats plus prompts. Le processus de conversion d'un texte d'une expression régulière en une structure interne de stockage de données est appelée "compilation d'une expression régulière", et apparaît lors de l'exécution. QRegExp utilise deux optimisations pour réduire le coût de la construction d'un tel objet : le partage implicite et le cache.

Le partage implicite implique que la structure des données de QRegExp est partagée par de multiples objets qui ont la même expression régulière. Ceci est une optimisation très fréquente dans Qt : par exemple, les classes QBrush, QCursor, QFont, QIconSet, QMap, QPalette, QPicture, QPixmap, QRegion, et QString utilisent la même technique.

Concernant le cache, Qt maintient une liste des objets les plus récemment construits pour éviter le coût de leur recompilation. Le cache permet de rendre ce code relativement efficace :

for ( int i = 0; i < 1000; i++ )
{
	QRegExp rx( "de+f" );
}

Il est, cependant, une très bonne habitude de ne pas construire d'objets QRegExp dans une boucle lorsque cela est possible.

Certaines constructions des expressions régulières ralentissent considérablement leur compilation ou leur utilisation, tandis que d'autres les accélèrent. Voici quelques astuces.

V-A-1. Utiliser (?: ... ), au lieu de ( ... ), autant que possible▲

V-A-2. Utiliser ^ ou QRegExp::exactMatch(), dès que possible▲

if ( line.find(QRegExp("^(SRC|SOURCE)=")) == 0 )
{
	...
}

V-A-3. Factoriser les sous-expressions▲

V-A-4. Éviter les références en arrière ( \\1 , \\2 ...), les répétitions ( ({1,500}) )▲

V-A-5. Éviter le non-déterminisme▲

D'autres optimisations sont spécifiques à QRegExp::search, une fonction qui recherche dans une potentiellement très grande quantité de texte.

rx.search( "abcdefghijklmnopqrstuvwxyz" );

search() essaye de faire correspond l'expression régulière de+f aux positions 1, 2, 3 ... de la chaîne "abcdefghijklmnopqrstuvwxyz", comme illustré ci-dessous.

Quatre essais sont nécessaires avant de trouver une correspondance ("def", en troisième position). Essayer de faire correspondre à chaque position dans la chaîne cible est très coûteux, et peut être évité via l'heuristique. Une analyse de l'expression régulière de+f fournit les informations suivantes :

• La longueur minimale de chaque texte testé est de 3 (par exemple, "def") ;
• Chaque occurrence doit commencer avec le texte "de" ;
• La lettre d apparaît au plus tôt à la position 0, e, à la position 1, et f, à la position 2. Aucun autre caractère ne peut apparaître dans la correspondance.

QRegExp::search utilise ces informations, et sélectionnent automatiquement une des heuristiques suivantes pour localiser les correspondances potentielles : une heuristique de bonne sous-série ou une heuristique de mauvais caractère.

V-B-1. Heuristique de bonne série▲

headed deer ddd eee fff

V-B-2. Heuristique de mauvais caractère▲

a "hea"ded deer ddd eee fff

La fonction interne heuristicallyChooseHeuristic() sélectionne l'heuristique la plus appropriée en se basant sur l'expression régulière. Elle calcule des scores pour les deux heuristiques selon une formule mathématique. Le tableau suivant montre les scores avec les deux heuristiques des deux expressions régulières.

Les lecteurs curieux ou enthousiastes peuvent compiler leurs propres statistiques en insérant cette expression vers la fin de heuristicallyChooseHeuristic() dans qregexp.cpp.

qDebug( "gsh %d, bch %d, '%s' at %d..%d",
    	goodStringScore, badCharScore,
  		goodString.isNull() ? "" : goodString.latin1(),
  		goodEarlyStart, goodLateStart );

La fonction interne dump() peut aussi se révéler utile pour de telles investigations.

Les deux heuristiques sont utilisées dans QRegExp::search et QRegExp::find, mais pas dans QRegExp::searchRev ou QRegExp::findRev, ainsi, les recherches inversées peuvent être beaucoup plus lentes.

Le meilleur moyen d'optimiser une expression régulière est de ne pas en utiliser du tout !

Depuis que les expressions régulières sont compilées à l'exécution, elles ne peuvent pas être aussi rapides que du code optimisé à la main qui ne les utilise pas. Par exemple, sur une large entre, cette fonction est ridiculement lente.

text.replace( QRegExp("\r\n"), "\n" );