Backtracking in reguliere expressies
Backtracking treedt op wanneer een normaal expressiepatroon optionele kwantificatoren of alternation-constructies bevat en de engine voor reguliere expressies terugkeert naar een eerdere opgeslagen status om door te gaan met het zoeken naar een overeenkomst. Backtracking is centraal in de kracht van reguliere expressies; het maakt het mogelijk voor expressies om krachtig en flexibel te zijn en om zeer complexe patronen te vinden. Tegelijkertijd kost dit vermogen een prijs. Backtracking is vaak de belangrijkste factor die van invloed is op de prestaties van de engine voor reguliere expressies. Gelukkig heeft de ontwikkelaar controle over het gedrag van de reguliere expressie-engine en hoe backtracking wordt gebruikt. In dit onderwerp wordt uitgelegd hoe backtracking werkt en hoe deze kan worden beheerd.
Waarschuwing
Wanneer u System.Text.RegularExpressions niet-vertrouwde invoer gebruikt, geeft u een time-out door. Een kwaadwillende gebruiker kan invoer opgeven voor RegularExpressionseen Denial-of-Service-aanval. ASP.NET Core Framework-API's die gebruikmaken van RegularExpressions een time-out.
Lineaire vergelijking zonder backtracking
Als een patroon voor reguliere expressies geen optionele kwantificatoren of alternatieconstructies heeft, wordt de engine voor reguliere expressies in lineaire tijd uitgevoerd. Nadat de engine voor reguliere expressies overeenkomt met het eerste taalelement in het patroon met tekst in de invoertekenreeks, probeert deze het volgende taalelement in het patroon te vinden met het volgende teken of de groep tekens in de invoertekenreeks. Dit gaat door totdat de overeenkomst slaagt of mislukt. In beide gevallen gaat de engine voor de reguliere expressie met één teken tegelijk in de invoertekenreeks verder.
In het volgende voorbeeld ziet u een afbeelding. De reguliere expressie e{2}\w\b zoekt naar twee exemplaren van de letter 'e' gevolgd door een woordteken gevolgd door een woordgrens.
using System;
using System.Text.RegularExpressions;
public class Example1
{
public static void Run()
{
string input = "needing a reed";
string pattern = @"e{2}\w\b";
foreach (Match match in Regex.Matches(input, pattern))
Console.WriteLine("{0} found at position {1}",
match.Value, match.Index);
}
}
// The example displays the following output:
// eed found at position 11
Imports System.Text.RegularExpressions
Module Example1
Public Sub Run()
Dim input As String = "needing a reed"
Dim pattern As String = "e{2}\w\b"
For Each match As Match In Regex.Matches(input, pattern)
Console.WriteLine("{0} found at position {1}",
match.Value, match.Index)
Next
End Sub
End Module
' The example displays the following output:
' eed found at position 11
Hoewel deze reguliere expressie de kwantificeerder {2}bevat, wordt deze op een lineaire manier geëvalueerd. De engine voor reguliere expressies maakt geen backtrack omdat {2} dit geen optionele kwantificator is. Hiermee wordt een exact getal opgegeven en niet een variabel aantal keren dat de vorige subexpressie moet overeenkomen. Als gevolg hiervan probeert de engine voor reguliere expressies overeen te komen met het reguliere expressiepatroon met de invoertekenreeks, zoals wordt weergegeven in de volgende tabel.
| Operation | Positie in patroon | Positie in tekenreeks | Resultaat |
|---|---|---|---|
| 1 | e | "behoefte aan een reed" (index 0) | Geen overeenkomst. |
| 2 | e | "eeding a reed" (index 1) | Mogelijke overeenkomst. |
| 3 | E{2} | "eding a reed" (index 2) | Mogelijke overeenkomst. |
| 4 | \W | "ding a reed" (index 3) | Mogelijke overeenkomst. |
| 5 | \B | "ing a reed" (index 4) | Mogelijke overeenkomst mislukt. |
| 6 | e | "eding a reed" (index 2) | Mogelijke overeenkomst. |
| 7 | E{2} | "ding a reed" (index 3) | Mogelijke overeenkomst mislukt. |
| 8 | e | "ding a reed" (index 3) | Overeenkomst mislukt. |
| 9 | e | "ing a reed" (index 4) | Geen overeenkomst. |
| 10 | e | "ng a reed" (index 5) | Geen overeenkomst. |
| 11 | e | "g a reed" (index 6) | Geen overeenkomst. |
| 12 | e | "a reed" (index 7) | Geen overeenkomst. |
| 13 | e | "a reed" (index 8) | Geen overeenkomst. |
| 14 | e | " reed" (index 9) | Geen overeenkomst. |
| 15 | e | "reed" (index 10) | Geen overeenkomst |
| 16 | e | "eed" (index 11) | Mogelijke overeenkomst. |
| 17 | E{2} | "ed" (index 12) | Mogelijke overeenkomst. |
| 18 | \W | "d" (index 13) | Mogelijke overeenkomst. |
| 19 | \B | "" (index 14) | Overeenkomen met. |
Als een patroon voor reguliere expressies geen optionele kwantificatoren of alternatieconstructies bevat, is het maximum aantal vergelijkingen dat nodig is om het reguliere expressiepatroon te vergelijken met de invoertekenreeks ongeveer gelijk aan het aantal tekens in de invoertekenreeks. In dit geval gebruikt de engine voor reguliere expressies 19 vergelijkingen om mogelijke overeenkomsten in deze tekenreeks van 13 tekens te identificeren. Met andere woorden, de reguliere expressie-engine wordt bijna lineair uitgevoerd als deze geen optionele kwantifiers of alternation constructs bevat.
Backtracking met optionele kwantificatoren of alternation-constructies
Wanneer een reguliere expressie optionele kwantificatoren of alternation-constructies bevat, is de evaluatie van de invoertekenreeks niet langer lineair. Het patroon dat overeenkomt met een NFA-engine (Nondeterministic Finite Automaton) wordt aangestuurd door de taalelementen in de reguliere expressie en niet door de tekens die moeten worden vergeleken in de invoertekenreeks. Daarom probeert de engine voor reguliere expressies volledig overeen te komen met optionele of alternatieve subexpressies. Wanneer het naar het volgende taalelement in de subexpressie gaat en de overeenkomst mislukt, kan de engine voor reguliere expressies een deel van de geslaagde overeenkomst afbreken en terugkeren naar een eerder opgeslagen status om de reguliere expressie als geheel te vergelijken met de invoertekenreeks. Dit proces om terug te keren naar een eerdere opgeslagen status om een overeenkomst te vinden, wordt backtracking genoemd.
Denk bijvoorbeeld aan het reguliere expressiepatroon .*(es), dat overeenkomt met de tekens 'es' en alle tekens die eraan voorafgaan. Zoals in het volgende voorbeeld wordt weergegeven, komt het patroon overeen met de hele tekenreeks tot en met de 'es' in 'expressies' als de invoertekenreeks 'Essentiële services worden geleverd door reguliere expressies'.
using System;
using System.Text.RegularExpressions;
public class Example2
{
public static void Run()
{
string input = "Essential services are provided by regular expressions.";
string pattern = ".*(es)";
Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
if (m.Success)
{
Console.WriteLine("'{0}' found at position {1}",
m.Value, m.Index);
Console.WriteLine("'es' found at position {0}",
m.Groups[1].Index);
}
}
}
// 'Essential services are provided by regular expressions found at position 0
// 'es' found at position 47
Imports System.Text.RegularExpressions
Module Example2
Public Sub Run()
Dim input As String = "Essential services are provided by regular expressions."
Dim pattern As String = ".*(es)"
Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
If m.Success Then
Console.WriteLine("'{0}' found at position {1}",
m.Value, m.Index)
Console.WriteLine("'es' found at position {0}",
m.Groups(1).Index)
End If
End Sub
End Module
' 'Essential services are provided by regular expressions found at position 0
' 'es' found at position 47
Hiervoor gebruikt de engine voor reguliere expressies backtracking als volgt:
Deze komt overeen met de
.*(die overeenkomt met nul, een of meer exemplaren van een willekeurig teken) met de hele invoertekenreeks.Er wordt geprobeerd om 'e' in het reguliere expressiepatroon te vinden. De invoertekenreeks bevat echter geen resterende tekens die overeenkomen.
Het backtrackt naar de laatste geslaagde overeenkomst, 'Essentiële services worden geleverd door reguliere expressies' en probeert 'e' te vergelijken met de punt aan het einde van de zin. De overeenkomst mislukt.
Het blijft teruggaan naar een vorige geslaagde overeenkomst één voor één teken totdat de voorlopig overeenkomende subtekenreeks 'Essentiële services worden geleverd door reguliere expr'. Vervolgens wordt de 'e' in het patroon vergeleken met de tweede 'e' in 'expressies' en wordt een overeenkomst gevonden.
Het vergelijkt 's' in het patroon met de 's' die het overeenkomende 'e'-teken volgt (de eerste 's' in 'expressies'). De overeenkomst is geslaagd.
Wanneer u backtracking gebruikt, moet u 67 vergelijkingsbewerkingen uitvoeren om het reguliere expressiepatroon te vergelijken met de invoertekenreeks, die 55 tekens lang is. Over het algemeen geldt dat als een patroon voor een reguliere expressie één alternationconstructie of één optionele kwantificator heeft, het aantal vergelijkingsbewerkingen dat nodig is om aan het patroon te voldoen, meer dan twee keer het aantal tekens in de invoertekenreeks is.
Backtracking met geneste optionele kwantificatoren
Het aantal vergelijkingsbewerkingen dat nodig is om overeen te komen met een normaal expressiepatroon kan exponentieel toenemen als het patroon een groot aantal alternatieconstructies bevat, als het geneste alternatieconstructies bevat, of, meestal, als het geneste optionele kwantificatoren bevat. Het reguliere expressiepatroon ^(a+)+$ is bijvoorbeeld ontworpen om overeen te komen met een volledige tekenreeks die een of meer a-tekens bevat. Het voorbeeld bevat twee invoertekenreeksen met een identieke lengte, maar alleen de eerste tekenreeks komt overeen met het patroon. De System.Diagnostics.Stopwatch klasse wordt gebruikt om te bepalen hoe lang de overeenkomstbewerking duurt.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example3
{
public static void Run()
{
string pattern = "^(a+)+$";
string[] inputs = { "aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!" };
Regex rgx = new Regex(pattern);
Stopwatch sw;
foreach (string input in inputs)
{
sw = Stopwatch.StartNew();
Match match = rgx.Match(input);
sw.Stop();
if (match.Success)
Console.WriteLine($"Matched {match.Value} in {sw.Elapsed}");
else
Console.WriteLine($"No match found in {sw.Elapsed}");
}
}
}
// Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
// No match found in 00:00:05.1882144
Imports System.Text.RegularExpressions
Module Example3
Public Sub Run()
Dim pattern As String = "^(a+)+$"
Dim inputs() As String = {"aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!"}
Dim rgx As New Regex(pattern)
Dim sw As Stopwatch
For Each input As String In inputs
sw = Stopwatch.StartNew()
Dim match As Match = rgx.Match(input)
sw.Stop()
If match.Success Then
Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
Else
Console.WriteLine("No match found in {0}", sw.Elapsed)
End If
Next
End Sub
End Module
' Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
' No match found in 00:00:05.1882144
Zoals de uitvoer uit het voorbeeld laat zien, duurde het aanzienlijk langer om te ontdekken dat een invoertekenreeks niet overeenkomt met het patroon, net als bij het identificeren van een overeenkomende tekenreeks. Dit komt doordat een mislukte overeenkomst altijd een slechtst scenario vertegenwoordigt. De engine voor reguliere expressies moet de reguliere expressie gebruiken om alle mogelijke paden door de gegevens te volgen voordat wordt geconcludeerd dat de overeenkomst mislukt en dat de geneste haakjes veel extra paden door de gegevens maken. De engine voor reguliere expressies concludeert dat de tweede tekenreeks niet overeenkomt met het patroon door het volgende te doen:
Er wordt gecontroleerd of deze zich aan het begin van de tekenreeks bevond en vervolgens overeenkomt met de eerste vijf tekens in de tekenreeks met het patroon
a+. Vervolgens wordt bepaald dat er geen extra groepen 'a' tekens in de tekenreeks staan. Ten slotte wordt getest op het einde van de tekenreeks. Omdat er nog één extra teken in de tekenreeks blijft, mislukt de overeenkomst. Voor deze mislukte overeenkomst zijn 9 vergelijkingen vereist. De engine voor reguliere expressies slaat ook statusgegevens op uit de overeenkomsten van 'a' (die we match 1 noemen), 'aa' (overeenkomst 2), 'aaa' (overeenkomst 3) en 'aaaa' (overeenkomst 4).Deze keert terug naar de eerder opgeslagen overeenkomst 4. Er wordt bepaald dat er één extra a-teken is dat moet worden toegewezen aan een extra vastgelegde groep. Ten slotte wordt getest op het einde van de tekenreeks. Omdat er nog één extra teken in de tekenreeks blijft, mislukt de overeenkomst. Voor deze mislukte overeenkomst zijn vier vergelijkingen vereist. Tot nu toe zijn er in totaal 13 vergelijkingen uitgevoerd.
Deze keert terug naar de eerder opgeslagen overeenkomst 3. Er wordt bepaald dat er twee extra 'a'-tekens zijn die moeten worden toegewezen aan een extra vastgelegde groep. De end-of-string-test mislukt echter. Vervolgens wordt de waarde 3 geretourneerd en wordt geprobeerd de twee extra 'a'-tekens in twee extra vastgelegde groepen te vinden. De end-of-string-test mislukt nog steeds. Voor deze mislukte overeenkomsten zijn 12 vergelijkingen vereist. Tot nu toe zijn er in totaal 25 vergelijkingen uitgevoerd.
De vergelijking van de invoertekenreeks met de reguliere expressie wordt op deze manier voortgezet totdat de engine voor reguliere expressies alle mogelijke combinaties van overeenkomsten heeft geprobeerd en vervolgens besluit dat er geen overeenkomst is. Vanwege de geneste kwantificatoren is deze vergelijking een O(2n) of een exponentiële bewerking, waarbij n het aantal tekens in de invoertekenreeks is. Dit betekent dat in het ergste geval een invoertekenreeks van 30 tekens ongeveer 1.073.741.824 vergelijkingen vereist en een invoertekenreeks van 40 tekens ongeveer 1.099.511.627.776 vergelijkingen vereist. Als u tekenreeksen van deze of nog grotere lengten gebruikt, kan het zeer lang duren voordat reguliere expressiemethoden zijn voltooid wanneer ze invoer verwerken die niet overeenkomt met het reguliere expressiepatroon.
Backtracking van besturingselementen
Met Backtracking kunt u krachtige, flexibele reguliere expressies maken. Zoals in de vorige sectie is gebleken, kunnen deze voordelen echter worden gekoppeld aan onaanvaardbaar slechte prestaties. Als u overmatige backtracking wilt voorkomen, moet u een time-outinterval definiëren wanneer u een Regex object instantiëren of een statische reguliere expressiekoppelingsmethode aanroept. Dit wordt besproken in de volgende sectie. Daarnaast ondersteunt .NET drie reguliere expressietaalelementen die backtracking beperken of onderdrukken en die complexe reguliere expressies ondersteunen met weinig of geen prestatiestraf: atomische groepen, lookbehind-asserties en lookahead-asserties. Zie Groeperingsconstructies voor meer informatie over elk taalelement.
Engine voor niet-backtracking van reguliere expressies
Als u geen constructies hoeft te gebruiken waarvoor backtracking is vereist (bijvoorbeeld lookarounds, backreferences of atomische groepen), kunt u overwegen de RegexOptions.NonBacktracking modus te gebruiken. Deze modus is ontworpen om in de tijd evenredig te worden uitgevoerd met de lengte van de invoer. Zie de modus NonBacktracking voor meer informatie. U kunt ook een time-outwaarde instellen.
De grootte van invoer beperken
Sommige reguliere expressies hebben acceptabele prestaties, tenzij de invoer uitzonderlijk groot is. Als alle redelijke tekstinvoer in uw scenario onder een bepaalde lengte staat, kunt u overwegen langere invoer te weigeren voordat u de reguliere expressie erop toepast.
Een time-outinterval opgeven
U kunt een time-outwaarde instellen die het langste interval aangeeft dat de engine voor reguliere expressies zoekt naar één overeenkomst voordat de poging wordt afgelaten en een RegexMatchTimeoutException uitzondering genereert. U geeft het time-outinterval op door een TimeSpan waarde op te geven aan de Regex(String, RegexOptions, TimeSpan) constructor voor bijvoorbeeld reguliere expressies. Bovendien heeft elke methode voor het vergelijken van statische patronen een overbelasting met een TimeSpan parameter waarmee u een time-outwaarde kunt opgeven.
Als u geen time-outwaarde expliciet instelt, wordt de standaardtime-outwaarde als volgt bepaald:
- Als deze bestaat, gebruikt u de time-outwaarde voor de hele toepassing. Dit kan elke time-outwaarde zijn die van toepassing is op het toepassingsdomein waarin het Regex object wordt geïnstantieerd of de aanroep van de statische methode wordt uitgevoerd. U kunt de time-outwaarde voor de hele toepassing instellen door de AppDomain.SetData methode aan te roepen om de tekenreeksweergave van een TimeSpan waarde toe te wijzen aan de eigenschap 'REGEX_DEFAULT_MATCH_TIMEOUT'.
- Als er geen time-outwaarde voor de hele toepassing is ingesteld met behulp van de waarde InfiniteMatchTimeout.
Standaard is het time-outinterval ingesteld op Regex.InfiniteMatchTimeout en treedt er geen time-out op voor de engine voor reguliere expressies.
Belangrijk
Wanneer u deze functie niet gebruikt RegexOptions.NonBacktracking, wordt u aangeraden altijd een time-outinterval in te stellen als uw reguliere expressie afhankelijk is van backtracking of werkt op niet-vertrouwde invoer.
Een RegexMatchTimeoutException uitzondering geeft aan dat de engine voor reguliere expressies geen overeenkomst kon vinden binnen het opgegeven time-outinterval, maar niet aangeeft waarom de uitzondering is gegenereerd. De reden kan overmatige backtracking zijn, maar het is ook mogelijk dat het time-outinterval te laag is ingesteld, gezien de systeembelasting op het moment dat de uitzondering werd gegenereerd. Wanneer u de uitzondering afhandelt, kunt u ervoor kiezen om verdere overeenkomsten met de invoertekenreeks te verlaten of het time-outinterval te verhogen en de overeenkomende bewerking opnieuw uit te voeren.
Met de volgende code wordt de Regex(String, RegexOptions, TimeSpan) constructor bijvoorbeeld aangeroepen om een Regex object te instantiëren met een time-outwaarde van 1 seconde. Het reguliere expressiepatroon (a+)+$, dat overeenkomt met een of meer reeksen van een of meer a-tekens aan het einde van een regel, is onderhevig aan overmatige backtracking. Als er een RegexMatchTimeoutException optreedt, verhoogt het voorbeeld de time-outwaarde tot een maximuminterval van 3 seconden. Daarna wordt de poging om het patroon te vinden, afgelaten.
using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading;
public class Example
{
const int MaxTimeoutInSeconds = 3;
public static void Main()
{
string pattern = @"(a+)+$"; // DO NOT REUSE THIS PATTERN.
Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));
Stopwatch? sw = null;
string[] inputs = { "aa", "aaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };
foreach (var inputValue in inputs)
{
Console.WriteLine("Processing {0}", inputValue);
bool timedOut = false;
do
{
try
{
sw = Stopwatch.StartNew();
// Display the result.
if (rgx.IsMatch(inputValue))
{
sw.Stop();
Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)",
inputValue, sw.Elapsed);
}
else
{
sw.Stop();
Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
inputValue, sw.Elapsed);
}
}
catch (RegexMatchTimeoutException e)
{
sw.Stop();
// Display the elapsed time until the exception.
Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}",
inputValue, sw.Elapsed);
Thread.Sleep(1500); // Pause for 1.5 seconds.
// Increase the timeout interval and retry.
TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
if (timeout.TotalSeconds > MaxTimeoutInSeconds)
{
Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
MaxTimeoutInSeconds);
timedOut = false;
}
else
{
Console.WriteLine("Changing the timeout interval to {0}",
timeout);
rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
timedOut = true;
}
}
} while (timedOut);
Console.WriteLine();
}
}
}
// The example displays output like the following :
// Processing aa
// Valid: 'aa' (00.0000779 seconds)
//
// Processing aaaa>
// 'aaaa>' is not a valid string. (00.00005 seconds)
//
// Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
// Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//
// Processing aaaaaaaaaaaaaaaaaaaaaa>
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
// Changing the timeout interval to 00:00:02
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
// Changing the timeout interval to 00:00:03
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
// Maximum timeout interval of 3 seconds exceeded.
//
// Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
// Maximum timeout interval of 3 seconds exceeded.
Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading
Module Example
Const MaxTimeoutInSeconds As Integer = 3
Public Sub Main()
Dim pattern As String = "(a+)+$" ' DO NOT REUSE THIS PATTERN.
Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))
Dim sw As Stopwatch = Nothing
Dim inputs() As String = {"aa", "aaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>"}
For Each inputValue In inputs
Console.WriteLine("Processing {0}", inputValue)
Dim timedOut As Boolean = False
Do
Try
sw = Stopwatch.StartNew()
' Display the result.
If rgx.IsMatch(inputValue) Then
sw.Stop()
Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)",
inputValue, sw.Elapsed)
Else
sw.Stop()
Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
inputValue, sw.Elapsed)
End If
Catch e As RegexMatchTimeoutException
sw.Stop()
' Display the elapsed time until the exception.
Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}",
inputValue, sw.Elapsed)
Thread.Sleep(1500) ' Pause for 1.5 seconds.
' Increase the timeout interval and retry.
Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
If timeout.TotalSeconds > MaxTimeoutInSeconds Then
Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
MaxTimeoutInSeconds)
timedOut = False
Else
Console.WriteLine("Changing the timeout interval to {0}",
timeout)
rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
timedOut = True
End If
End Try
Loop While timedOut
Console.WriteLine()
Next
End Sub
End Module
' The example displays output like the following:
' Processing aa
' Valid: 'aa' (00.0000779 seconds)
'
' Processing aaaa>
' 'aaaa>' is not a valid string. (00.00005 seconds)
'
' Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
' Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'
' Processing aaaaaaaaaaaaaaaaaaaaaa>
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
' Changing the timeout interval to 00:00:02
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
' Changing the timeout interval to 00:00:03
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
' Maximum timeout interval of 3 seconds exceeded.
'
' Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
' Maximum timeout interval of 3 seconds exceeded.
Atomische groepen
Het (?>subexpressietaalelement) is een atomische groepering. Hiermee voorkomt u dat er backtracking wordt uitgevoerd naar de subexpressie. Zodra dit taalelement is gematcht, geeft het geen deel van de overeenkomst op aan volgende backtracking. Als het patroon (?>\w*\d*)11 bijvoorbeeld niet kan worden vergeleken, geeft het \d* geen overeenkomst op, zelfs niet als dat betekent dat de overeenkomst met 1 succes kan worden vergeleken. Atomische groepen kunnen helpen de prestatieproblemen te voorkomen die zijn gekoppeld aan mislukte overeenkomsten.
In het volgende voorbeeld ziet u hoe het onderdrukken van backtracking de prestaties verbetert bij het gebruik van geneste kwantificatoren. Het meet de tijd die nodig is voor de engine voor reguliere expressies om te bepalen dat een invoertekenreeks niet overeenkomt met twee reguliere expressies. De eerste reguliere expressie maakt gebruik van backtracking om te proberen een tekenreeks te vinden die een of meer exemplaren van een of meer hexadecimale cijfers bevat, gevolgd door een dubbele punt, gevolgd door een of meer hexadecimale cijfers, gevolgd door twee dubbele punten. De tweede reguliere expressie is identiek aan de eerste, behalve dat backtracking wordt uitgeschakeld. Zoals de uitvoer uit het voorbeeld laat zien, is de prestatieverbetering van het uitschakelen van backtracking aanzienlijk.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example4
{
public static void Run()
{
string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
bool matched;
Stopwatch sw;
Console.WriteLine("With backtracking:");
string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
sw = Stopwatch.StartNew();
matched = Regex.IsMatch(input, backPattern);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed);
Console.WriteLine();
Console.WriteLine("Without backtracking:");
string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
sw = Stopwatch.StartNew();
matched = Regex.IsMatch(input, noBackPattern);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed);
}
}
// The example displays output like the following:
// With backtracking:
// Match: False in 00:00:27.4282019
//
// Without backtracking:
// Match: False in 00:00:00.0001391
Imports System.Text.RegularExpressions
Module Example4
Public Sub Run()
Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
Dim matched As Boolean
Dim sw As Stopwatch
Console.WriteLine("With backtracking:")
Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
sw = Stopwatch.StartNew()
matched = Regex.IsMatch(input, backPattern)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
Console.WriteLine()
Console.WriteLine("Without backtracking:")
Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
sw = Stopwatch.StartNew()
matched = Regex.IsMatch(input, noBackPattern)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
End Sub
End Module
' The example displays the following output:
' With backtracking:
' Match: False in 00:00:27.4282019
'
' Without backtracking:
' Match: False in 00:00:00.0001391
Lookbehind-asserties
.NET bevat twee taalelementen, (?<=subexpressie en (?<!subexpressie)), die overeenkomen met het vorige teken of de vorige tekens in de invoertekenreeks. Beide taalelementen zijn asserties met nul breedte; dat wil gezegd, ze bepalen of het teken of de tekens die direct voorafgaan aan het huidige teken, kunnen worden vergeleken met subexpressie, zonder vooruit of terug te gaan.
(?<=subexpressie is een positieve lookbehind-assertie) ; dat wil zeggen dat het teken of de tekens vóór de huidige positie moeten overeenkomen met subexpressie. (?<!subexpressie is een negatieve lookbehind-assertie) ; dat wil zeggen dat het teken of de tekens vóór de huidige positie niet overeenkomen met subexpressie. Zowel positieve als negatieve lookbehind-asserties zijn het handigst wanneer subexpressie een subset van de vorige subexpressie is.
In het volgende voorbeeld worden twee equivalente reguliere expressiepatronen gebruikt waarmee de gebruikersnaam in een e-mailadres wordt gevalideerd. Het eerste patroon is onderhevig aan slechte prestaties vanwege overmatige backtracking. Het tweede patroon wijzigt de eerste reguliere expressie door een geneste kwantificator te vervangen door een positieve lookbehind-assertie. In de uitvoer van het voorbeeld wordt de uitvoeringstijd van de Regex.IsMatch methode weergegeven.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example5
{
public static void Run()
{
Stopwatch sw;
string input = "test@contoso.com";
bool result;
string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);
string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
}
}
// The example displays output similar to the following:
// Match: True in 00:00:00.0017549
// Match with Lookbehind: True in 00:00:00.0000659
Module Example5
Public Sub Run()
Dim sw As Stopwatch
Dim input As String = "test@contoso.com"
Dim result As Boolean
Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)
Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays output similar to the following:
' Match: True in 00:00:00.0017549
' Match with Lookbehind: True in 00:00:00.0000659
Het eerste reguliere expressiepatroon, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.
| Patroon | Beschrijving |
|---|---|
^ |
Begin de overeenkomst aan het begin van de tekenreeks. |
[0-9A-Z] |
Komt overeen met een alfanumerieke teken. Deze vergelijking is niet hoofdlettergevoelig, omdat de Regex.IsMatch methode wordt aangeroepen met de RegexOptions.IgnoreCase optie. |
[-.\w]* |
Kom overeen met nul, een of meer exemplaren van een afbreekstreepje, punt of woordteken. |
[0-9A-Z] |
Komt overeen met een alfanumerieke teken. |
([-.\w]*[0-9A-Z])* |
Kom overeen met nul of meer exemplaren van de combinatie van nul of meer afbreekstreepjes, punten of woordtekens, gevolgd door een alfanumerieke teken. Dit is de eerste opnamegroep. |
@ |
Overeenkomst met een bijteken ("@"). |
Het tweede reguliere expressiepatroon, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@gebruikt een positieve lookbehind-assertie. Deze wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.
| Patroon | Beschrijving |
|---|---|
^ |
Begin de overeenkomst aan het begin van de tekenreeks. |
[0-9A-Z] |
Komt overeen met een alfanumerieke teken. Deze vergelijking is niet hoofdlettergevoelig, omdat de Regex.IsMatch methode wordt aangeroepen met de RegexOptions.IgnoreCase optie. |
[-.\w]* |
Kom overeen met nul of meer exemplaren van een afbreekstreepje, punt of woordteken. |
(?<=[0-9A-Z]) |
Kijk terug naar het laatste overeenkomende teken en ga door met de overeenkomst als het alfanumeriek is. Alfanumerieke tekens zijn een subset van de set die bestaat uit punten, afbreekstreepjes en alle woordtekens. |
@ |
Overeenkomst met een bijteken ("@"). |
Lookahead-asserties
.NET bevat twee taalelementen, (?=subexpressie en (?!subexpressie)), die overeenkomen met het volgende teken of de volgende tekens in de invoertekenreeks. Beide taalelementen zijn asserties met nul breedte; dat wil gezegd, bepalen ze of het teken of de tekens die direct volgen op het huidige teken, kunnen worden vergeleken met subexpressie, zonder vooruit of terug te gaan.
(?=subexpressie is een positieve lookahead-assertie) . Dat wil zeggen dat het teken of de tekens na de huidige positie overeenkomen met subexpressie. (?!subexpressie is een negatieve lookahead-assertie) ; dat wil zeggen dat het teken of de tekens na de huidige positie niet overeenkomen met subexpressie. Zowel positieve als negatieve lookahead-asserties zijn het nuttigst wanneer subexpressie een subset van de volgende subexpressie is.
In het volgende voorbeeld worden twee equivalente reguliere expressiepatronen gebruikt waarmee een volledig gekwalificeerde typenaam wordt gevalideerd. Het eerste patroon is onderhevig aan slechte prestaties vanwege overmatige backtracking. De tweede wijzigt de eerste reguliere expressie door een geneste kwantificator te vervangen door een positieve lookahead-assertie. In de uitvoer van het voorbeeld wordt de uitvoeringstijd van de Regex.IsMatch methode weergegeven.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example6
{
public static void Run()
{
string input = "aaaaaaaaaaaaaaaaaaaaaa.";
bool result;
Stopwatch sw;
string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
}
}
// The example displays the following output:
// False in 00:00:03.8003793
// False in 00:00:00.0000866
Imports System.Text.RegularExpressions
Module Example6
Public Sub Run()
Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
Dim result As Boolean
Dim sw As Stopwatch
Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays the following output:
' False in 00:00:03.8003793
' False in 00:00:00.0000866
Het eerste reguliere expressiepatroon, ^(([A-Z]\w*)+\.)*[A-Z]\w*$wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.
| Patroon | Beschrijving |
|---|---|
^ |
Begin de overeenkomst aan het begin van de tekenreeks. |
([A-Z]\w*)+\. |
Een alfabetisch teken (A-Z), gevolgd door nul of meer woordtekens, één of meer keren, gevolgd door een punt. Deze vergelijking is niet hoofdlettergevoelig, omdat de Regex.IsMatch methode wordt aangeroepen met de RegexOptions.IgnoreCase optie. |
(([A-Z]\w*)+\.)* |
Komt overeen met het vorige patroon nul of meer keren. |
[A-Z]\w* |
Komt overeen met een alfabetisch teken, gevolgd door nul of meer woordtekens. |
$ |
Beëindig de overeenkomst aan het einde van de invoertekenreeks. |
Het tweede reguliere expressiepatroon, ^((?=[A-Z])\w+\.)*[A-Z]\w*$maakt gebruik van een positieve lookahead-assertie. Deze wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.
| Patroon | Beschrijving |
|---|---|
^ |
Begin de overeenkomst aan het begin van de tekenreeks. |
(?=[A-Z]) |
Kijk vooruit naar het eerste teken en ga door met de overeenkomst als het alfabetisch is (A-Z). Deze vergelijking is niet hoofdlettergevoelig, omdat de Regex.IsMatch methode wordt aangeroepen met de RegexOptions.IgnoreCase optie. |
\w+\. |
Komt overeen met een of meer woordtekens gevolgd door een punt. |
((?=[A-Z])\w+\.)* |
Komt overeen met het patroon van een of meer woordtekens gevolgd door een punt nul of meer keren. Het eerste woord moet alfabetisch zijn. |
[A-Z]\w* |
Komt overeen met een alfabetisch teken, gevolgd door nul of meer woordtekens. |
$ |
Beëindig de overeenkomst aan het einde van de invoertekenreeks. |
Algemene prestatieoverwegingen
De volgende suggesties zijn niet specifiek bedoeld om overmatige backtracking te voorkomen, maar kunnen de prestaties van uw reguliere expressie verbeteren:
Vooraf gebruikte patronen compileren. De beste manier om dit te doen, is door de brongenerator voor reguliere expressies te gebruiken om deze vooraf te compileren. Als de brongenerator niet beschikbaar is voor uw app, bijvoorbeeld als u zich niet richt op .NET 7 of hoger, of als u het patroon tijdens het compileren niet kent, gebruikt u de RegexOptions.Compiled optie.
Cache intensief gebruikte Regex-objecten. Dit gebeurt impliciet wanneer u de brongenerator gebruikt. Anders maakt u een Regex-object en slaat u het op voor hergebruik, in plaats van de statische Regex-methoden te gebruiken of een Regex-object te maken en weg te gooien.
Begin met vergelijken vanaf een offset. Als u weet dat overeenkomsten altijd buiten een bepaalde verschuiving in het patroon beginnen, geeft u de offset door in het gebruik van een overbelasting zoals Regex.Match(String, Int32). Dit vermindert de hoeveelheid tekst die de engine moet overwegen.
Verzamel alleen de informatie die u nodig hebt. Als u alleen wilt weten of een overeenkomst plaatsvindt, maar niet waar de overeenkomst plaatsvindt, geeft u de voorkeur Regex.IsMatch. Als u alleen hoeft te weten hoe vaak iets overeenkomt, gebruikt u liever Regex.Count. Als u alleen de grenzen van een overeenkomst hoeft te kennen, maar niets over de opnamen van een overeenkomst, gebruikt u liever Regex.EnumerateMatches. Hoe minder informatie de engine moet leveren, hoe beter.
Vermijd onnodige opnamen. Haakjes in uw patroon vormen standaard een vastleggende groep. Als u geen opnamen nodig hebt, kunt u in plaats daarvan groepen opgeven RegexOptions.ExplicitCapture of gebruiken die niet worden vastgelegd. Hierdoor wordt de motor opgeslagen om deze opnamen bij te houden.
Zie ook
Feedback
Binnenkort beschikbaar: In de loop van 2024 zullen we GitHub-problemen geleidelijk uitfaseren als het feedbackmechanisme voor inhoud en deze vervangen door een nieuw feedbacksysteem. Zie voor meer informatie: https://aka.ms/ContentUserFeedback.
Feedback verzenden en weergeven voor