Erreur [Allocation overflow] avec RegExp

Version imprimable

13/07/2018, 16h07
Abdou_moujar

Erreur [Allocation overflow] avec RegExp

Bonjour
Je débute en expressions régulières, j'écris une de la forme /a?|ab/g pour analyser le texte "aaab" j'obtiens alors un message d'erreur
"Allocation overflow" de dépassement de mémoire.Pourquoi?
Merci pour toute réponse.
16/07/2018, 14h57
NoSmoking

Bonjour,
ce que tu nous montres comme code (en fait rien) est insuffisant pour que l'on puisse t'aider !
16/07/2018, 22h30
01001111

Bonjour, ça doit venir d'ailleurs...
si je fais /a?|ab/g.test("aaab") ça me renvoie true sur tout navigateur

voici le code d'essai qui m'a renvoyé l'erreur Allocation overflow

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
function test() {
try {
var regEx = /a|ab/g;
var str = "aaab";
if(!regEx.test(str)) return null;
var a = new Array();
regEx.lastIndex = 0;
while((var result = regEx.exec(str)) != null) {
a.push(result.index);
}
return a;
}
catch(exp) {
alert(exp.message);
}
}
//après j'essaie de récupérer le tableau des indexes s'il est non  nulle et là j'obtiens l'erreur.

Merci

17/07/2018, 08h48
ProgElecT

Salut

Code:

if(!regEx.test(str)) {return null;}

c'est normal tu lances une boucle while sur une condition qui ne change pas,
en effet si str ne change pas reg.test(str) ne sera jamais nul, ton tableau va se remplir sans fin ce qui déclenche le débordement de pile.
il faudrait faire un substr sur la chaine str quand le résultat est trouvé, pour sortir de la boucle.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function test() {
     try {
          var regEx = /a|ab/g;
          var str = "aaab";
          if(!regEx.test(str)) return null;
          var a = new Array();
          var result;
          var o=0;
          while((result = regEx.exec(str)) != null) {
                  a.push(result.index+o);
                  str=str.substr(result.index+result[0].length);
                  o+=result.index+result[0].length;
          }
          return a;
} catch(exp) {
          alert(exp.message);
}

17/07/2018, 19h01
Abdou_moujar

Bonjour: En guise de réponse à 01001111
Je crois savoir que pour chaque appel à la méthode exect(str) sur regEx la position du curseur ou débute la recherche avance au caractère qui suit immédiatement le dernier caractère du dernier match et qui est indiquée par la propriété lastIndex et quand il n'y a plus de match la méthode retourne null et le curseur est réinitialisé à 0.La boucle while() devrait donc s'arrêter là. S'il n'y a pas de match du tout la methode retourne null dès le départ et la boucle n'est jamais déclenchée.

NB: Dans le code que j'ais donné j'ai oublié un ? dans le motif de la regEx en fait le motif qui declenche l'erreur est : /?a|ab/g et non /a|ab/g. Le motif est appliqué au texte "aaab" .C'est tout de même insignifiant mais c'est juste pour comprendre pourquoi cette erreur de dépassement de mémoire est declenchée.
Merci.

Ok, je ne savais pas pour la récursivité de la fonction dans une boucle while...
Alors je crois avoir compris, ça vient du fait que tu rajoutes var au sein de la boucle, c'est aussi pour ce genre de raison que j'avais externalisé le "var".
"var" réinitialise ta recherche à chaque itération, je pense, donc l'allocation overflow serait bien due au remplissage du tableau.
Sinon je crois que le point d'interrogation ne sert à rien si tu le mets au début, puisqu'il signifie oui ou non pour le dernier caractère ou la dernière classe, mais je peux me tromper sur ce point aussi.
Donc le code corrigé serait :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 function test() { try { var regEx = /a|ab/g; var str = "aaab"; if(!regEx.test(str)) return null; var a = new Array(); var result; while((result = regEx.exec(str)) != null) { a.push(result.index); } return a; } catch(exp) { alert(exp.message); } }

:salut:

Je vois que la discussion a bien évolué pendant que j'étais occupé à diverses choses.

Je vous donne tout de même la solution que j'avais retenue hier soir :

Code:

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
function test() {
    let
        regEx = /a|ab/g,
        str = "aaab",
        nb = str.length - 1, // -1 indispensable
        a = [];
 
    while (regEx.lastIndex < nb){
        if (regEx.test(str)){
            regEx.lastIndex--; // indispensable
            a.push(regEx.exec(str));
        }
    }
 
    return a;
}
 
console.log(test());
 
/*
(3) [Array(1), Array(1), Array(1)]
0: ["a", index: 0, input: "aaab", groups: undefined]
1: ["a", index: 1, input: "aaab", groups: undefined]
2: ["a", index: 2, input: "aaab", groups: undefined]
length: 3
*/

18/07/2018, 19h48
NoSmoking

Citation:

Envoyé par Abdou_moujar

NB: Dans le code que j'ais donné j'ai oublié un ? dans le motif de la regEx en fait le motif qui declenche l'erreur est : /?a|ab/g et non /a|ab/g.

il te faut échapper le caractère « ? » pour que cela soit correct.

Code:

var regEx = /\?a|ab/g;
20/07/2018, 11h39
Watilin
Le motif ?a|ab n’est pas valide :

Citation:

SyntaxError: nothing to repeat

Par contre, si on regarde le motif donné dans le premier post, a?|ab, on peut le décomposer. a? signifie « a ou rien », c’est donc une sorte d’alternative : a|{rien}. (Bien sûr, la syntaxe {rien} n’existe pas, c’est juste pour être clair.)

On peut donc réécrire le motif en pseudo-regex : a|{rien}|ab.
Si on réordonne les alternatives : a|ab|{rien} 
 
Et ça, ça peut se réécrire en vrai code valide : (a|ab)? 
Et on peut même « factoriser le a : (ab?)? 

Toutes les versions de cette regexp reconnaissent trois choses :
- "a"
- "ab"
- la chaîne vide ""
Important, il n’y a pas d’ancres (^ ou $) donc le motif peut correspondre à n’importe quel endroit d’une chaîne donnée. En particulier, la chaîne vide est reconnue partout, par exemple dans "xy" il y a une chaîne vide entre x et y. Par conséquent, cette regexp reconnaît toutes les chaînes.

Quand on utilise une regexp dans une boucle, il faut absolument vérifier qu’elle ne reconnaît pas la chaîne vide. En effet, la correspondance chaîne vide a une longueur 0, ce qui fait que lastIndex n’augmente pas, et exec fait du surplace.

Du coup, le script boucle, et selon le contexte, ça fait une popup qui dit « un script de la page ne répond plus », ou un dépassement de mémoire. En l’occurence, je pense que c’est l’allocation d’un nombre infini de variables result qui est la cause du message Allocation Overflow.

Même si c’est étrange, parce que chez moi (sous Firefox), je ne peux pas mettre un var dans un while, ça fait une SyntaxError. Du coup je ne peux faire que des hypothèses.

Certains outils, comme le site https://regexper.com/, te permettent de visualiser tes regexp sous la forme d’un graphe. Essaye a+b ;)
20/07/2018, 15h22
CosmoKnacki

Citation:

Envoyé par Watilin

On peut donc réécrire le motif en pseudo-regex : a|{rien}|ab.
Si on réordonne les alternatives : a|ab|{rien} 
 
Et ça, ça peut se réécrire en vrai code valide : (a|ab)? 
Et on peut même « factoriser le a : (ab?)? 

Si on part de la pattern d'origine a?|ab, une pseudo-regex correspondante est a|{rien}|ab soit a|{rien} car toute alternative située après {rien} ne sera jamais testée, puisque {rien} réussit toujours. Donc pour simplifier la pattern de départ, on écrirait plutôt: a?.

Réordonner les alternatives en a|ab|{rien} sans changer le sens de la pattern de départ n'est ici possible que parce que a réussira toujours avant ab, on ne pourrait pas faire de même avec par exemple a|{rien}|bc. C'est pour la même raison qu'il n'y a pas de correspondance entre (a|ab)?  et (ab?)? car la première pattern ne trouvera jamais la chaîne "ab" alors que la deuxième a la possibilité de le faire. (ab??)? (ou encore a?b??) serait plus fidèle mais peut se ramener quoi qu'il en soit à a?.
22/07/2018, 02h34
Abdou_moujar

Salut
Pour la variable result en réalité je l'ai définie avant la boucle et non à l'intérieur comme je l'ai écrit dans le code. Donc aucun problème de ce coté là.
Mais revenons sur le motif /a?|ab/g appliqué à la chaine "aaab". Si j'utilise le motif /a+|ab/g ou le motif a|ab?/g ça marche à tous les coups. La boucle renvoie 3 matchs qui sont les 3 premières lettres 'a'. Mais analysons de près le motif qui pose problème.
Au départ lastIndex = 0 ce qui correspond à la première lettre 'a', il doit donc y avoir un premier match qui renvoie cette lettre et le curseur se place sur la deuxième lettre 'a' qui devrait à son tour être renvoyée et ainsi jusqu'à ce que le curseur se place sur la lettre 'b'. C'est là ou le comportement du motif n'est pas clair pour moi : est ce que a? veut dire a|{rien} ou bien veut dire a|{tout sauf a} c'est à dire en termes de motif a|[^a] A mon avis le curseur ne fait jamais du surplace car soit il avance lorsque un match est trouvé et dans ce cas result != null et la boucle continue, soit il est remis à 0 si aucun match n'est trouvé et dan ce cas result = null et la boucle s'achève. Tout ça demande peut être un peu plus d'éclaircissement. Le débat est donc toujours ouvert.
Merci pour toute participation.
22/07/2018, 12h36
Watilin
@CosmoKnacki : merci pour ces éclaircissements :)
J’ai tendance à oublier l’aspect séquentiel des regexps, et à me dire que l’ordre n’est pas important.

Citation:

Envoyé par Abdou_moujar

Salut
Pour la variable result en réalité je l'ai définie avant la boucle et non à l'intérieur comme je l'ai écrit dans le code. Donc aucun problème de ce coté là.

Voilà qui me rassure :D
Et ce que je n’avais pas vu jusqu’à maintenant, c’est le a.push dans ta boucle. L’erreur Allocation overflow, c’est tout simplement le tableau qui déborde.

Citation:

est ce que a? veut dire a|{rien} ou bien veut dire a|{tout sauf a} c'est à dire en termes de motif a|[^a]

a? signifie bien a|{rien}.

Le motif a|[^a], quant à lui, revient à dire « accepte tout ce qui est un truc ou tout ce qui n’est pas un truc », autrement dit : absolument tout ce qui existe. C’est comme l’astuce parfois utilisée [/s/S] (tout ce qui est un espacement ou tout ce qui n’est pas un espacement) quand le . ne suffit pas⁽¹⁾, car . ne reconnaît pas les retours chariot "\r" ni les sauts de lignes "\n".

Citation:

A mon avis le curseur ne fait jamais du surplace car soit il avance lorsque un match est trouvé et dans ce cas result != null et la boucle continue, soit il est remis à 0 si aucun match n'est trouvé et dan ce cas result = null et la boucle s'achève. Tout ça demande peut être un peu plus d'éclaircissement. Le débat est donc toujours ouvert.
Merci pour toute participation.

Le problème c’est cette fichue chaîne vide "" qui se trouve n’importe où dans toute chaîne. Dans mon précédent post, j’ai dit que dans "xy" il y avait une chaîne vide entre "x" et "y". En fait, c’est encore pire que ça : il y en a une infinité. Et il y en a aussi en début et en fin de chaîne.

Le curseur peut bel et bien faire du surplace, il existe même plusieurs éléments de regexp prévus pour ça :
- les ancres ^ et $ ;
- la limite de mot (word boundary) \b, qui correspond exactement à une position entre \w et \W, et réciproquement⁽²⁾ ;
- le contraire du précédent, \B, la « non limite de mot » ;
- les, euh… « groupes de longueur 0 », par exemple (?=abc) : ça reconnaît la séquence "abc", mais ça ne fait pas avancer le curseur.
Ce sont donc des correspondances de longueur nulle. En langage savant, on appelle ça des assertions. L’exemple le plus parlant est sans doute celui-ci :
Code:

1 2 3 4 5 6 let str = ""; let reg = /^/g; for (let i = 0; i < 7; i++) { console.log(reg.lastIndex); // toujours 0 console.log(reg.exec(str)); // toujours "" }
Dans le cas qui nous intéresse, l’alternative {rien} qui est cachée dans le motif a? est une correspondance de longueur nulle. Pour vérifier, essaye simplement /a?/.test("b").

Et sinon, tu as essayé a+b ?

(1) Ça marche aussi avec [\w\W] et [\d\D].
(2) \b est un peu erronée car elle ne comprend pas les caractères accentués, entre autres. Par exemple dans "réponse", pour elle, il y a une transition entre "r" et "é".

2 pièce(s) jointe(s)

J'ai fait un test qui confirme que le curseur fait du surplace avec la regexp /a?|ab/g;
voici le test et la capture de la sortie de console :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function test() { try { var regEx = /a?|ab/g; var str = "aaab"; if(!regEx.test(str)) return null; var a = new Array(); var result; while((result = regEx.exec(str)) != null) { console.log(result.index); a.push(result.index); } return a; } catch(exp) { alert(exp.message); } } test();
Pièce jointe 398430
même avec la regexp /ab|a?/g ça bloque en position 4
Pièce jointe 398424

pour moi l'allocation overflow vient bien d'un remplissage de tableau sans fin, lui même du au pointeur de l'expression qui reste le même, d'où le risque d'utiliser des expressions de longueur potentielle 0 sans rien de plus.

22/07/2018, 15h50
CosmoKnacki
Citation:

Envoyé par abdou_moujar

À mon avis le curseur ne fait jamais du surplace...

C'est pourtant bien ce qui se passe, mais ce comportement est propre aux méthodes RegExp.prototype.test et RegExp.prototype.exec qui déterminent la position suivante à partir de la dernière position et de la longueur de la correspondance.
En résumé: position suivante = dernière position + 0 = dernière position. Donc ça ne bouge plus.
Code:

1 2 3 4 5 6 7 8 > re = /./g /./g > re.test('ab') true > re.test('ab') true > re.test('ab') false
Code:

1 2 3 4 5 6 7 8 9 10 11 > re = /z?/g /z?/g > re.test('ab') true > re.test('ab') true > re.test('ab') true > re.test('ab') true ...
Par contre, les méthodes String.prototype.match, String.prototype.replace et String.prototype.split elles, avancent automatiquement d'une position lorsque la correspondance est vide. Formuler autrement, ces méthodes ne testent jamais deux fois la même position.
Code:

1 2 > 'abc'.replace(/z?/g, '#') '#a#b#c#'
(Il n'y a pas eu création d'une chaîne infinie de # allant jusqu'à l'overflow. Le pointeur avance.)

Citation:

Envoyé par Watilin

J’ai tendance à oublier l’aspect séquentiel des regexps, et à me dire que l’ordre n’est pas important.

C'est loin d'être une ineptie car à la base, les moteurs de regex suivant le standard POSIX renvoient non pas la première alternative qui réussit mais celle dont la correspondance est la plus longue, et ce n'est que lorsqu'il y a "égalité" que l'ordre est pris en compte. C'est le comportement auquel il faut s'attendre avec des outils comme grep, sed, awk, avec MySQL ou les fonctions dépréciées ereg* de PHP. Par contre, en Javascript, PHP (preg_*), Ruby, Perl, Python, Java, .net... , la première alternative qui réussit est retenue quelque soit la longueur de la correspondance.

Merci pour toutes vos collaborations
C'est vrai l'indexe renvoyé par la méthode regEx.exec(str) peut faire du surplace. Je l'ai vérifié sur le fameux motif /a?/g appliqué à la chaine "aaab" en utilisant une nested function exécutée de manière répétitive au lieu d''une boucle while, voici le code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 function test() { var str = "aaab", re = /a?/g; var ti = new Date(), tmax = 5000, dt = 1000; var i = 1; start(); function start() { var r = re.exec(str); if(r != null) console.log("N° " + i + " : Index = " + r.index + " Match = " + RegExp.lastMatch); i++; var t = new Date(); if((t - ti) <= tmax) setTimeout(start, dt); } }
En exécutant la fonction test() j'obtient la sortie suivante :
N° 1 : Index = 0 Match = a
N° 2 : Index = 1 Match = a
N° 3 : Index = 2 Match = a
N° 3 : Index = 3 Match =
N° 4 : Index = 3 Match =
N° 5 : Index = 3 Match =
N° 6 : Index = 3 Match =

On voit bien que le curseur bloque sur l'indexe 3 (la lettre b) et le match renvoie toujours la même chaine vide(le fameux a|{rien}) et la variable r n'est jamais nulle.
C'est ce qui explique l'exception Allocation overflow à cause du tableau qui n'en finit jamais de se remplir.
Tout autre éclaircissement serait le bien venu. Merci

27/07/2018, 14h47
Watilin
Une info complémentaire : la taille maximale d’un tableau, fixée par la spécification ECMAScript, est de 2³² - 1. Si on essaye de dépasser cette limite…
Code:

1 2 arr = new Array(2**32 - 1) arr.push("oups")
… On obtient le message d’erreur suivant :

Code:

RangeError: invalid array length

C’est un message différent de Allocation overflow. Ça signifie que la limite de mémoire du navigateur (limite physique) est atteinte avant la limite de taille du tableau (limite virtuelle).
27/07/2018, 19h10
01001111

Enfin ce qui m'étonne la dedans, c'est qu'un tableau rempli x fois avec de petits entiers fasse déborder la mémoire du navigateur, mais je peux me tromper ! C'est sans doute oublier que javascript n'a qu'un type "number"...
C'est pourquoi je pensais à la limite du tableau proprement dit, sous chrome...
Sinon sur un appel récurrent de fonction infini, la limite atteinte lance le message "Maximum call stack size exceeded" sous Chrome

Après depuis Quantum, j'ai une préférence nette pour Firefox qui est redevenu le navigateur optimisé que j'aimais...:P
28/07/2018, 13h26
Watilin

En effet, le type Number est représenté par les flottants double précision de la norme IEEE-754. Ils tiennent sur 64 bits, soit 4 octets.

Mais même en supposant que les nombres n’occupent qu’un seul octet, remplir un tableau de 2³² entrées demanderait un total de 4 Go de mémoire vive. Je ne crois pas qu’il existe un navigateur aujourd’hui qui peut allouer autant à son moteur JavaScript.

Quant à la limite de récursion, on ne la voit pas dans le cas présent car on utilise une boucle while, donc il n’y a pas d’empilement d’appels de fonction.