Bakåtspårning i reguljära uttryck
Bakåtspårning sker när ett mönster för reguljära uttryck innehåller valfria kvantifierare eller växlingskonstruktioner, och motorn för reguljära uttryck återgår till ett tidigare sparat tillstånd för att fortsätta sökningen efter en matchning. Backtracking är centralt för kraften i reguljära uttryck. det gör det möjligt för uttryck att vara kraftfulla och flexibla, och att matcha mycket komplexa mönster. Samtidigt kommer den här kraften till en kostnad. Backtracking är ofta den enskilt viktigaste faktorn som påverkar prestanda för den reguljära uttrycksmotorn. Lyckligtvis har utvecklaren kontroll över beteendet för motorn för reguljära uttryck och hur den använder backtracking. Det här avsnittet förklarar hur backtracking fungerar och hur det kan styras.
Varning
När du använder System.Text.RegularExpressions för att bearbeta ej betrodda indata skickar du en timeout. En obehörig användare kan ange indata till RegularExpressions, vilket orsakar en Denial-of-Service-attack. ASP.NET Core Framework-API:er som använder RegularExpressions passera en timeout.
Linjär jämförelse utan backtracking
Om ett reguljärt uttrycksmönster inte har några valfria kvantifierare eller alternationskonstruktioner körs motorn för reguljära uttryck linjärt. Efter att motorn för reguljära uttryck matchar det första språkelementet i mönstret med text i indatasträngen försöker den matcha nästa språkelement i mönstret med nästa tecken eller grupp med tecken i indatasträngen. Detta fortsätter tills matchningen lyckas eller misslyckas. I båda fallen avancerar motorn för reguljära uttryck med ett tecken i taget i indatasträngen.
I följande exempel visas en bild. Det reguljära uttrycket e{2}\w\b söker efter två förekomster av bokstaven "e" följt av ordtecken följt av en ordgräns.
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
Även om det här reguljära uttrycket innehåller kvantifieraren {2}utvärderas det linjärt. Motorn för reguljära uttryck backar inte eftersom {2} den inte är en valfri kvantifierare. Den anger ett exakt tal och inte ett variabelt antal gånger som föregående underuttryck måste matcha. Det innebär att motorn för reguljära uttryck försöker matcha mönstret för reguljära uttryck med indatasträngen enligt följande tabell.
| Åtgärd | Position i mönster | Placera i sträng | Resultat |
|---|---|---|---|
| 1 | e | "behöver en vass" (index 0) | Ingen matchning. |
| 2 | e | "eeding a reed" (index 1) | Möjlig matchning. |
| 3 | E{2} | "eding a reed" (index 2) | Möjlig matchning. |
| 4 | \W | "ding a reed" (index 3) | Möjlig matchning. |
| 5 | \B | "ing a reed" (index 4) | Möjliga matchning misslyckas. |
| 6 | e | "eding a reed" (index 2) | Möjlig matchning. |
| 7 | E{2} | "ding a reed" (index 3) | Möjliga matchning misslyckas. |
| 8 | e | "ding a reed" (index 3) | Matchning misslyckas. |
| 9 | e | "ing a reed" (index 4) | Ingen matchning. |
| 10 | e | "ng a reed" (index 5) | Ingen matchning. |
| 11 | e | "g a reed" (index 6) | Ingen matchning. |
| 12 | e | "a reed" (index 7) | Ingen matchning. |
| 13 | e | "a reed" (index 8) | Ingen matchning. |
| 14 | e | "reed" (index 9) | Ingen matchning. |
| 15 | e | "reed" (index 10) | Ingen matchning |
| 16 | e | "eed" (index 11) | Möjlig matchning. |
| 17 | E{2} | "ed" (index 12) | Möjlig matchning. |
| 18 | \W | "d" (index 13) | Möjlig matchning. |
| 19 | \B | "" (index 14) | Matcha. |
Om ett mönster för reguljära uttryck inte innehåller några valfria kvantifierare eller växlingskonstruktioner motsvarar det maximala antalet jämförelser som krävs för att matcha mönstret för reguljära uttryck med indatasträngen ungefär lika med antalet tecken i indatasträngen. I det här fallet använder motorn för reguljära uttryck 19 jämförelser för att identifiera möjliga matchningar i den här strängen med 13 tecken. Med andra ord körs motorn för reguljära uttryck nästan linjärt om den inte innehåller några valfria kvantifierare eller alternationskonstruktioner.
Bakåtspårning med valfria kvantifierare eller växlingskonstruktioner
När ett reguljärt uttryck innehåller valfria kvantifierare eller alternationskonstruktioner är utvärderingen av indatasträngen inte längre linjär. Mönstermatchning med en nondeterministisk Finite Automaton-motor (NFA) drivs av språkelementen i det reguljära uttrycket och inte av de tecken som ska matchas i indatasträngen. Därför försöker motorn för reguljära uttryck att helt matcha valfria eller alternativa underuttryck. När den går vidare till nästa språkelement i underuttrycket och matchningen misslyckas kan motorn för reguljära uttryck överge en del av sin lyckade matchning och återgå till ett tidigare sparat tillstånd för att matcha det reguljära uttrycket som helhet med indatasträngen. Den här processen för att återgå till ett tidigare sparat tillstånd för att hitta en matchning kallas backtracking.
Tänk till exempel på det reguljära uttrycksmönstret .*(es), som matchar tecknen "es" och alla tecken som föregår det. Som i följande exempel visas, om indatasträngen är "Essential services are provided by regular expressions.", matchar mönstret hela strängen upp till och inklusive "es" i "expressions".
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
För att göra detta använder motorn för reguljära uttryck backtracking på följande sätt:
Den matchar
.*(som matchar noll, en eller flera förekomster av något tecken) med hela indatasträngen.Den försöker matcha "e" i mönstret för reguljära uttryck. Indatasträngen har dock inga återstående tecken att matcha.
Den backar till sin senaste lyckade matchning, "Viktiga tjänster tillhandahålls av reguljära uttryck" och försöker matcha "e" med perioden i slutet av meningen. Matchningen misslyckas.
Det fortsätter att backa till en tidigare lyckad matchning ett tecken i taget tills den preliminärt matchade delsträngen är "Essential services are provided by regular expr". Den jämför sedan "e" i mönstret med det andra "e" i "uttryck" och hittar en matchning.
Den jämför "s" i mönstret med "s" som följer det matchade "e"-tecknet (de första "s" i "uttryck"). Matchningen lyckas.
När du använder backtracking krävs 67 jämförelseåtgärder för att matcha det reguljära uttrycksmönstret med indatasträngen, som är 55 tecken lång. Om ett reguljärt uttrycksmönster har en enda alternationskonstruktion eller en enda valfri kvantifierare är antalet jämförelseåtgärder som krävs för att matcha mönstret mer än dubbelt så många tecken i indatasträngen.
Backtracking med kapslade valfria kvantifierare
Antalet jämförelseåtgärder som krävs för att matcha ett mönster för reguljära uttryck kan öka exponentiellt om mönstret innehåller ett stort antal alternationskonstruktioner, om det innehåller kapslade alternationskonstruktioner, eller oftast om det innehåller kapslade valfria kvantifierare. Mönstret ^(a+)+$ för reguljära uttryck är till exempel utformat för att matcha en fullständig sträng som innehåller ett eller flera "a"-tecken. Exemplet innehåller två indatasträngar med identisk längd, men endast den första strängen matchar mönstret. Klassen System.Diagnostics.Stopwatch används för att avgöra hur lång tid matchningsåtgärden tar.
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
Som utdata från exemplet visar tog det betydligt längre tid för motorn för reguljära uttryck att upptäcka att en indatasträng inte matchade mönstret som den gjorde för att identifiera en matchande sträng. Det beror på att en misslyckad matchning alltid representerar ett värsta scenario. Motorn för reguljära uttryck måste använda reguljära uttryck för att följa alla möjliga sökvägar genom data innan den kan dra slutsatsen att matchningen misslyckas och de kapslade parenteserna skapar många ytterligare sökvägar genom data. Motorn för reguljära uttryck drar slutsatsen att den andra strängen inte matchade mönstret genom att göra följande:
Den kontrollerar att den var i början av strängen och matchar sedan de första fem tecknen i strängen med mönstret
a+. Den avgör sedan att det inte finns några ytterligare grupper med "a"-tecken i strängen. Slutligen testas för slutet av strängen. Eftersom ytterligare ett tecken finns kvar i strängen misslyckas matchningen. Den här misslyckade matchning kräver 9 jämförelser. Motorn för reguljära uttryck sparar även tillståndsinformation från dess matchningar av "a" (som vi kallar matchning 1), "aa" (match 2), "aaa" (match 3) och "aaaa" (match 4).Den återgår till den tidigare sparade matchningen 4. Det avgör att det finns ytterligare ett "a"-tecken att tilldela till ytterligare en grupperad grupp. Slutligen testas för slutet av strängen. Eftersom ytterligare ett tecken finns kvar i strängen misslyckas matchningen. Den här misslyckade matchning kräver 4 jämförelser. Hittills har totalt 13 jämförelser utförts.
Den återgår till den tidigare sparade matchningen 3. Det avgör att det finns ytterligare två "a"-tecken att tilldela till ytterligare en grupperad grupp. Det går dock inte att slutföra strängtestet. Den returnerar sedan för att matcha 3 och försöker matcha de två ytterligare "a"-tecknen i ytterligare två insamlade grupper. Testet i slutet av strängen misslyckas fortfarande. Dessa misslyckade matchningar kräver 12 jämförelser. Hittills har totalt 25 jämförelser utförts.
Jämförelsen av indatasträngen med det reguljära uttrycket fortsätter på det här sättet tills motorn för reguljära uttryck har provat alla möjliga kombinationer av matchningar och sedan drar slutsatsen att det inte finns någon matchning. På grund av de kapslade kvantifierarna är den här jämförelsen en O(2n) eller en exponentiell åtgärd, där n är antalet tecken i indatasträngen. Det innebär att i värsta fall kräver en indatasträng på 30 tecken cirka 1 073 741 824 jämförelser och en indatasträng på 40 tecken kräver cirka 1 099 511 627 776 jämförelser. Om du använder strängar av dessa eller ännu större längder kan reguljära uttrycksmetoder ta mycket lång tid att slutföra när de bearbetar indata som inte matchar det reguljära uttrycksmönstret.
Kontrollera backtracking
Med bakåtspårning kan du skapa kraftfulla, flexibla reguljära uttryck. Men som föregående avsnitt visade kan dessa fördelar kombineras med oacceptabelt dåliga prestanda. För att förhindra överdriven backtracking bör du definiera ett tidsgränsintervall när du instansierar ett Regex objekt eller anropar en matchningsmetod för statiska reguljära uttryck. Detta beskrivs i nästa avsnitt. Dessutom har .NET stöd för tre reguljära uttrycksspråkelement som begränsar eller undertrycker backtracking och som stöder komplexa reguljära uttryck med liten eller ingen prestandaförsämring: atomiska grupper, lookbehind-försäkran och lookahead-försäkran. Mer information om varje språkelement finns i Grupperingskonstruktioner.
Motor för icke-bakåtspårande reguljära uttryck
Om du inte behöver använda några konstruktioner som kräver backtracking (till exempel lösningar, backreferences eller atomiska grupper) bör du överväga att använda RegexOptions.NonBacktracking läget. Det här läget är utformat för att köras i tid som är proportionellt mot längden på indata. Mer information finns i NonBacktracking-läge. Du kan också ange ett timeout-värde.
Begränsa storleken på indata
Vissa reguljära uttryck har godtagbara prestanda om inte indata är exceptionellt stora. Om alla rimliga textindata i ditt scenario är kända för att vara under en viss längd bör du överväga att avvisa längre indata innan du tillämpar det reguljära uttrycket på dem.
Ange ett tidsgränsintervall
Du kan ange ett timeout-värde som representerar det längsta intervallet som motorn för reguljära uttryck söker efter en enda matchning innan den överger försöket och genererar ett RegexMatchTimeoutException undantag. Du anger tidsgränsintervallet genom att ange ett TimeSpan värde till Regex(String, RegexOptions, TimeSpan) konstruktorn för reguljära instansuttryck. Dessutom har varje statisk mönstermatchningsmetod en överlagring med en TimeSpan parameter som gör att du kan ange ett timeout-värde.
Om du inte uttryckligen anger ett timeout-värde bestäms standardvärdet för timeout enligt följande:
- Med hjälp av tidsgränsvärdet för hela programmet, om det finns ett sådant. Detta kan vara ett timeout-värde som gäller för programdomänen Regex där objektet instansieras eller det statiska metodanropet görs. Du kan ange tidsgränsvärdet för hela programmet genom att anropa AppDomain.SetData metoden för att tilldela strängrepresentationen av ett TimeSpan värde till egenskapen "REGEX_DEFAULT_MATCH_TIMEOUT".
- Genom att använda värdet InfiniteMatchTimeout, om inget timeout-värde för hela programmet har angetts.
Som standard är tidsgränsintervallet inställt på Regex.InfiniteMatchTimeout och motorn för reguljära uttryck överskrider inte tidsgränsen.
Viktigt!
När du inte använder RegexOptions.NonBacktrackingrekommenderar vi att du alltid anger ett tidsgränsintervall om ditt reguljära uttryck förlitar sig på backtracking eller använder ej betrodda indata.
Ett RegexMatchTimeoutException undantag anger att motorn för reguljära uttryck inte kunde hitta en matchning inom det angivna tidsgränsintervallet, men anger inte varför undantaget utlöstes. Orsaken kan vara överdriven backtracking, men det är också möjligt att tidsgränsintervallet angavs för lågt med tanke på systembelastningen när undantaget utlöstes. När du hanterar undantaget kan du välja att avbryta ytterligare matchningar med indatasträngen eller öka tidsgränsintervallet och försöka matcha åtgärden igen.
Följande kod anropar Regex(String, RegexOptions, TimeSpan) till exempel konstruktorn för att instansiera ett Regex objekt med ett timeout-värde på 1 sekund. Det reguljära uttrycksmönstret (a+)+$, som matchar en eller flera sekvenser med ett eller flera "a"-tecken i slutet av en rad, är föremål för överdriven bakåtspårning. Om en RegexMatchTimeoutException genereras ökar exemplet timeout-värdet upp till ett maximalt intervall på 3 sekunder. Därefter avbryts försöket att matcha mönstret.
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.
Atomiska grupper
Underuttrycksspråkelementet (?>)är en atomisk gruppering. Det förhindrar backtracking till underuttrycket. När det här språkelementet har matchats ger det inte upp någon del av sin matchning till efterföljande backtracking. Om det till exempel inte går att matcha \d* i mönstret (?>\w*\d*)11 ger inte matchningen upp någon av matchningen, även om det innebär att den tillåter 1 matchningen. Atomgrupper kan hjälpa till att förhindra prestandaproblem som är associerade med misslyckade matchningar.
I följande exempel visas hur om du undertrycker backtracking förbättras prestandan när du använder kapslade kvantifierare. Den mäter den tid som krävs för motorn för reguljära uttryck för att fastställa att en indatasträng inte matchar två reguljära uttryck. Det första reguljära uttrycket använder backtracking för att försöka matcha en sträng som innehåller en eller flera förekomster av en eller flera hexadecimala siffror, följt av ett kolon följt av en eller flera hexadecimala siffror, följt av två kolon. Det andra reguljära uttrycket är identiskt med det första, förutom att det inaktiverar bakåtspårning. Som utdata från exemplet visar är prestandaförbättringen från att inaktivera backtracking betydande.
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-försäkran
.NET innehåller två språkelement, (?<=underuttryck) och(?<! underuttryck), som matchar föregående tecken eller tecken i indatasträngen. Båda språkelementen är nollbreddskontroller. De avgör alltså om tecknet eller tecknen som omedelbart föregår det aktuella tecknet kan matchas av underuttryck, utan att avancera eller bakåtspåra.
(?<=subexpression) är en positiv lookbehind försäkran, det vill säga tecknet eller tecknen innan den aktuella positionen måste matcha underuttryck. (?<!subexpression) är en negativ lookbehind försäkran, det vill säga tecknet eller tecknen före den aktuella positionen får inte matcha underuttryck. Både positiva och negativa lookbehind försäkran är mest användbara när underuttryck är en delmängd av föregående underuttryck.
I följande exempel används två motsvarande mönster för reguljära uttryck som validerar användarnamnet i en e-postadress. Det första mönstret är föremål för dåliga prestanda på grund av överdriven backtracking. Det andra mönstret ändrar det första reguljära uttrycket genom att ersätta en kapslad kvantifierare med en positiv lookbehind-försäkran. Utdata från exemplet visar körningstiden för Regex.IsMatch metoden.
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
Det första reguljära uttrycksmönstret, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, definieras enligt följande tabell.
| Mönster | beskrivning |
|---|---|
^ |
Starta matchningen i början av strängen. |
[0-9A-Z] |
Matcha ett alfanumeriskt tecken. Den här jämförelsen är skiftlägeskänslig eftersom Regex.IsMatch metoden anropas med alternativet RegexOptions.IgnoreCase . |
[-.\w]* |
Matcha noll, en eller flera förekomster av ett bindestreck, punkt- eller ordtecken. |
[0-9A-Z] |
Matcha ett alfanumeriskt tecken. |
([-.\w]*[0-9A-Z])* |
Matcha noll eller fler förekomster av kombinationen av noll eller fler bindestreck, punkter eller ordtecken följt av ett alfanumeriskt tecken. Det här är den första insamlingsgruppen. |
@ |
Matcha ett vid tecken ("@"). |
Det andra reguljära uttrycksmönstret, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, använder en positiv lookbehind-försäkran. Den definieras enligt följande tabell.
| Mönster | beskrivning |
|---|---|
^ |
Starta matchningen i början av strängen. |
[0-9A-Z] |
Matcha ett alfanumeriskt tecken. Den här jämförelsen är skiftlägeskänslig eftersom Regex.IsMatch metoden anropas med alternativet RegexOptions.IgnoreCase . |
[-.\w]* |
Matcha noll eller fler förekomster av ett bindestreck, punkt- eller ordtecken. |
(?<=[0-9A-Z]) |
Titta tillbaka på det senast matchade tecknet och fortsätt matchningen om det är alfanumeriskt. Observera att alfanumeriska tecken är en delmängd av uppsättningen som består av punkter, bindestreck och alla ordtecken. |
@ |
Matcha ett vid tecken ("@"). |
Lookahead-försäkran
.NET innehåller två språkelement, (?=underuttryck) och(?! underuttryck), som matchar nästa tecken eller tecken i indatasträngen. Båda språkelementen är nollbreddskontroller. De avgör alltså om tecknet eller tecknen som omedelbart följer det aktuella tecknet kan matchas av underuttryck, utan att avancera eller backa.
(?=subexpression) är en positiv lookahead-försäkran, det vill: tecknet eller tecknen efter den aktuella positionen måste matcha underuttryck. (?!subexpression) är en negativ lookahead-försäkran, det vill: tecknet eller tecknen efter den aktuella positionen får inte matcha underuttryck. Både positiva och negativa lookahead-försäkran är mest användbara när underuttryck är en delmängd av nästa underuttryck.
I följande exempel används två motsvarande mönster för reguljära uttryck som verifierar ett fullständigt kvalificerat typnamn. Det första mönstret är föremål för dåliga prestanda på grund av överdriven backtracking. Det andra ändrar det första reguljära uttrycket genom att ersätta en kapslad kvantifierare med en positiv lookahead-försäkran. Utdata från exemplet visar körningstiden för Regex.IsMatch metoden.
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
Det första reguljära uttrycksmönstret, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, definieras enligt följande tabell.
| Mönster | beskrivning |
|---|---|
^ |
Starta matchningen i början av strängen. |
([A-Z]\w*)+\. |
Matcha ett alfabetiskt tecken (A-Z) följt av noll eller fler ordtecken en eller flera gånger följt av en punkt. Den här jämförelsen är skiftlägeskänslig eftersom Regex.IsMatch metoden anropas med alternativet RegexOptions.IgnoreCase . |
(([A-Z]\w*)+\.)* |
Matcha föregående mönster noll eller fler gånger. |
[A-Z]\w* |
Matcha ett alfabetiskt tecken följt av noll eller fler ordtecken. |
$ |
Avsluta matchningen i slutet av indatasträngen. |
Det andra reguljära uttrycksmönstret, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, använder en positiv lookahead-försäkran. Den definieras enligt följande tabell.
| Mönster | beskrivning |
|---|---|
^ |
Starta matchningen i början av strängen. |
(?=[A-Z]) |
Titta framåt till det första tecknet och fortsätt matchningen om det är alfabetiskt (A-Z). Den här jämförelsen är skiftlägeskänslig eftersom Regex.IsMatch metoden anropas med alternativet RegexOptions.IgnoreCase . |
\w+\. |
Matcha ett eller flera ordtecken följt av en punkt. |
((?=[A-Z])\w+\.)* |
Matcha mönstret för ett eller flera ordtecken följt av en period noll eller flera gånger. Det inledande ordtecknet måste vara alfabetiskt. |
[A-Z]\w* |
Matcha ett alfabetiskt tecken följt av noll eller fler ordtecken. |
$ |
Avsluta matchningen i slutet av indatasträngen. |
Allmänna prestandaöverväganden
Följande förslag är inte specifikt för att förhindra överdriven backtracking, men kan hjälpa till att öka prestandan för ditt reguljära uttryck:
Förkompilera starkt använda mönster. Det bästa sättet att göra detta är att använda källgeneratorn för reguljära uttryck för att förkompilera den. Om källgeneratorn inte är tillgänglig för din app, till exempel om du inte riktar in dig på .NET 7 eller senare, eller om du inte känner till mönstret vid kompileringstillfället, använder du RegexOptions.Compiled alternativet .
Cachelagrade regex-objekt som används mycket. Detta inträffar implicit när du använder källgeneratorn. Annars skapar du ett Regex-objekt och lagrar det för återanvändning i stället för att använda statiska Regex-metoder eller skapa och kasta bort ett Regex-objekt.
Börja matcha från en förskjutning. Om du vet att matchningar alltid börjar bortom en viss förskjutning i mönstret skickar du in förskjutningen med hjälp av en överlagring som Regex.Match(String, Int32). Detta minskar mängden text som motorn behöver tänka på.
Samla bara in den information du behöver. Om du bara behöver veta om en matchning inträffar men inte var matchningen sker, föredrar du Regex.IsMatch. Om du bara behöver veta hur många gånger något matchar föredrar du att använda Regex.Count. Om du bara behöver känna till gränserna för en matchning, men inte något om en matchnings avbildningar, föredrar du att använda Regex.EnumerateMatches. Desto mindre information behöver motorn ge, desto bättre.
Undvik onödiga avbildningar. Parenteser i ditt mönster utgör en insamlingsgrupp som standard. Om du inte behöver avbildningar anger RegexOptions.ExplicitCapture eller använder du grupper som inte samlar in i stället. Detta sparar motorn som håller reda på dessa avbildningar.
Se även
Feedback
Kommer snart: Under hela 2024 kommer vi att fasa ut GitHub-problem som feedbackmekanism för innehåll och ersätta det med ett nytt feedbacksystem. Mer information finns i: https://aka.ms/ContentUserFeedback.
Skicka och visa feedback för