Ken og Al's største bommert.

Regular expresions, love them or hate them, vi slipper ikke uden om dem.

Men vi slipper desværre heller ikke udenom om den gamle selskabsleg der hedder "hvor mange back-slash mon der bliver brug for ?"

Lige nu sidder jeg med en situation, hvor en regular expression kommer ind via en HTTP header ("slet de cachede objekt der matcher $regexp").

Det indlejrede sprog "VCL" hiver en tekststreng ud af HTTP headeren og sender til Varnish cache-engine og bare for at gøre det underholdende kan der være flere udtryk i samme purge request:

purge req.http.host ~ www.foo.com && req.http.url ~ .png

Hvis nu Ken Thompson og Al Aho fra starten havde smidt regexps ind i en passende indpakning, f.eks <...>, eller en anden passende form for "bracketing", så kunne denne process foregå uden større problemer.

Og frem for alt, uden de evendelige \\\ sekvenser der skal beskytte de magiske tegn i en regular expression imod at blive fortolket af shells, scriptsprog og andre tekstbehandlinger undervejs.

Overvej f.eks hvorledes nogle af de modemstøjsekvenser folk nåede frem til i forbindelse med dato/CPR matching ville se ud med forskellige niveauer af \ quoting.

Man kunne selvfølgelige forsøge at ophæve regular expressions til førsteklasses syntaktiske elementer, men hvis de ikke får første prioritet, (dvs. over både "..." i shell syntax) slipper vi ikke for \\-roderiet.

Til gengæld, hvis de gør, bliver det umuligt at konstruere regular expressions ud af variabler.

Uanset hvilken vej man har næsen vender enden bagud.

Der er mere end en grund til at regular expressions figurerer højt på listen over potientielle sikkerhedshuller.

phk

Kommentarer (17)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#2 Poul-Henning Kamp Blogger

Mna, men overvej nu lige den regexp der match req.http.url.

Hvor mange lovlige URL'er har du set uden mindst en '/' ? [1]

Det har altid været hamrende upraktisk at '/' var regexp delimiter når man havde path-names at slås med.

Visse programmer og her må jeg retfærdigvis tippe med hatten til Ken Thompson, tillader et vilkårligt tegn som "wrapper", hvis de ved at der kommer en regexp.

Men det virker kun hvis du 100% sikkert ved at det er en regexp der kommer.

Det er og bliver noget rod.

Poul-Henning

[1] Dette er et trick-spørgsmål, se RFC2616 :-)

  • 0
  • 0
#3 Lars Balker

...hvor et regexp kan pakkes ind i // eller hvad man nu har lyst til at lave efter et m: m,, m!! m{} m[]

$foo =~ m,/hej/der,;

Jeg kan slet ikke forstå hvorfor du bringer \'er ind i billedet - de er kun et problem, hvis man prøver at repræsentere et regexp i et sprog/datatype hvor \ i forvejen har en betydning. Når du selv definerer sproget, så...

  • 0
  • 0
#5 Poul-Henning Kamp Blogger

Jeg kan slet ikke forstå hvorfor du bringer \'er ind i billedet[...]

Det må så være fordi jeg ikke har tegnet billedet ordentligt :-)

Du har helt ret i, at der ikke er problemer så længe du holder dine regexp's indefor en enkelt veldefineret sandkasse.

Imidlertid indeholder verden situationer der ikke kan håndteres af slige simplificerede tilfælde, f.eks er det i mit tilfælde meget sandsynligt at det samlede forløb er:

Database transaktion der opdaterer webside -> genererer en request der skal invalidere den forrige version, i form af en regular expression. -> regexp'en sendes som kommando parameter til et externt program -> typisk skrevet i PERL el.lign -> Dette program åbner en TCP forbindelse, ==> enten med en forud defineret CLI protokol med typisk "..." quoting, og det er nogenlunde til at håndtere ==> eller også med HTTP protokollen, hvorefter HTTP headers behandles in det kompilerede VCL program, som skal uddrage eller generere regexps og sende disse videre i systemet.

... og så er det lige pludselig ikke nemt mere.

Og jeg kan selvfølgelig sagtens opfinde det varme vand, og sige at alle regexps i denne sammenhæng skal være pakket ind i HALL{...}ELUJA.

Men det gør ikke livet nemmere at jeg tilføjer den 37. metode at pakker regexps ind på, skaden er sket og det bedste jeg kan gøre er at undgå at forvirre mine brugere mere end højest nødvendigt.

Poul-Henning

  • 0
  • 0
#6 Poul-Henning Kamp Blogger

Til den slags fortolkningsproblemer kan du med stor fordel følge kurserne "oversætter" og/eller "videregående oversætter" på DIKU. Der gives bl.a. indsigt i problemstillinger så som entydighed af udtryk.

Din tyrkertro på DIKU er sikkert vel ment, men jeg har svært ved at se hvorledes et DIKU kursus kan rette op på fejltagelse der skete for næsten 40 år siden, og som i mellemtiden er standardiseret ind i alle mulige sprog og APIer.

Poul-Henning

  • 0
  • 0
#8 Jesper Louis Andersen

Nu skal det retfærdigvis siges at videregående oversætterteknik ikke snakker om regulære sprog og grammatikker. Oversætterteknik gør derimod i høj grad, men det er næppe tvetydighed som er et problem her.

RE'er er allerede godt slået i stykker som standard. Emacs, Perl, (F)lex, sed etc har alle deres små "vidunderlige" quirks der gør at man skal tage højde for dette og hint.

Men jeg forstår egentlig ikke hvor der er et issue her. Jeg er ikke umiddelbart nok inde i Varnish og VCL til at se hvor eksempeltvist en shell kan finde på at glob-expandere '*' så det skaber problemer. Du modtager en passende tekststreng i en HTTP header, som du kaster efter varnish. Derefter kaster varnish en parser efter dette, og den har naturligvis derefter en passende opfattelse af hvad headeren sagde. Hvis det skal gå bare nogenlunde stærkt skal der godt nok ikke forkes en shell eller værre i den proces.

Hvis man prøver at redde producenten af RE'en, så taber man jvf de små quirks fra før.

  • 0
  • 0
#9 Poul-Henning Kamp Blogger

se hvor eksempeltvist en shell kan finde på at glob-expandere '*'

Det er ikke '*' der er det største problem, det er '\'.

Hvis du skal skal matche et punktum i en regexp, skal du skrive .mumle eller [.]mumle for '.' er en af de magiske tegn.

Af årsager jeg ikke personligt forstår, foretrækker folk den første form: .

Nu indkapsler du din regexp i "...." for at undgå at shell'en gør underlige ting ved tegn som [*+?

Nu sker der imidlertid det, at shell'en bruger '\' som escape for at du kan få '"' ind i din streng og fordi den bruger '\' er den naturligvis også nødt til at bruge '\' som escape for '\'

Hvis f.eks, din string skal indeholde en backslash skal du altså skrive "\".

Derfor er vores regexp nu blevet til "\.mumle"

Hvis du er uheldig at komme to gange igennem en "..." fortolkning har du brug for "\\.mumle".

Og så fremdeles.

Hvis du er så uheldig, at du slet ikke ved hvor mange gange din regexp streng kan risikere at blive expanderet er du på herrens mark.

Vi kan diskutere hvor, hvem og hvad fejlen skyldes, men et faktum er at det er noget rod.

Problemet er, at vi har standardiseret rodet.

Poul-Henning

  • 0
  • 0
#13 Michael Rasmussen

Du har selvfølgeligt ret mht. optimering, men helt sikker kan man jo ikke være:-)

En anden ting ved [] er så, at de også er specialtegn i diverse shells, hvorfor problematikken ikke ændrer sig.

Hvordan har du egentligt løst problematikken med den teoretiske mulighed for uendelig rekursion ved ekspansion?

  • 0
  • 0
#14 Poul-Henning Kamp Blogger

Hvordan har du egentligt løst problematikken med den teoretiske mulighed for uendelig rekursion ved ekspansion?

Jeg er ikke klar over præcis hvilken "uendelig rekursion" du hentyder til ?

Hvis du mener noget internt i fortolkningen af regexps, så gør jeg naturligvis hvad ethvert tænkende menneske vil gøre:

Jeg kalder operativsystemets regexp bibliotek i henhold til det standardiserede API, der er ingen grund til at skrive sin egen regexp-fortolker[1].

Poul-Henning

[1] OK, disclaimer: Men hvis vi taler om at skrive en regexp-compiler er det en anden historie. Men det kunne jeg ikke drømme om at kigge på, før der er et reelt performance problem med fortolkede regexps og det er vi ikke i nærheden af.

  • 0
  • 0
#15 Deleted User

Det skulle da være en elendig regexp implementering der ikke optimerer [...] med kun et enkelt tegn til en literal...

Programming Perl, 3rd edition, p. 205: ... but the regex optimizer is not smart enough (as of this writing) to figure out that /[b]/ is equivalent to /b/.

Man må næsten tro at der er en eller anden grund til at denne optimering ikke er implementeret i perl.

  • 0
  • 0
#16 Lars Balker

Hvorfor skulle man? Prøv at benchmarke de to løsninger - resultatet drukner i støj.

Den eneste måde man kan optimere den slags er med mere kode, og perls regex er jo netop hurtig(!) fordi kernen ikke er ret stor og derfor oftest passer i cpuens cache.

Premature optimization is the root of all evil. Fy phk.

  • 0
  • 0
#17 Peter Makholm Blogger

Jeg tror ikke at påstanden fra Programming Perl, 3rd edition, gælder for Perl 5.10. Kører jeg et par reguløre udtryk gennem debuggeren får jeg i hvert fald det samme for /a/ og /[a]/.

$ perl -Mre=debug -e '/a/; /[b]/; /[cC]/;'

  • 0
  • 0
Log ind eller Opret konto for at kommentere