7
\$\begingroup\$

I'm getting user submitted text from a <textarea></textarea>, and I want to edit it a bit before storing it in a database. Here are my 3 regexes, with explanations below them:

  1. /(?:^((\pZ)+|((?!\R)\pC)+)(?1)*)|((?1)$)|(?:((?2)+|(?3)+)(?=(?2)|(?3)))/um
    • For every line...
      1. Match all leading whitespace and unicode control characters ("WS/CC") (EXCEPT LINE BREAKS).
      2. Match all trailing WS/CC (EXCEPT LINE BREAKS).
      3. Match all but one WS/CC between non-whitespace characters.
    • regex101
  2. /(\pZ+)|((?!\R)\pC)/u
    • Match remaining WS/CC (EXCEPT LINE BREAKS).
    • regex101
  3. /(^\R+)|(\R+$)|(\R(?=\R{2}))/u
    • Match all leading line breaks.
    • Match all trailing line breaks.
    • Match all but 2 consecutive line breaks.
    • regex101

This is pretty much how I'm planning on using these regexes in my PHP script

// ...
// [Get user input from $_POST
// check its length, etc.,
// if everything looks O.K., store it in $str]
// ...

// Trim unnecessary whitespace (leave line breaks)
$str = preg_replace("/(?:^((\pZ)+|((?!\R)\pC)+)(?1)*)|((?1)$)|(?:((?2)+|(?3)+)(?=(?2)|(?3)))/um", '', $str);
// Convert remaining whitespace to regular spaces (leave line breaks)
$str = preg_replace("/(\pZ+)|((?!\R)\pC)/u", ' ', $str);
// Trim line breaks
$str = preg_replace("/(^\R+)|(\R+$)|(\R(?=\R{2}))/u", '', $str);

// Sanitize for safe printing between html tags
$str = htmlspecialchars($str, ENT_HTML5, 'UTF-8');

// ...
// [Store $str in DB with prepared statements]
// ...

And here's a test case which I've executed on regex101:

Input
(with some WS/CC in it):



a b  c   
 d    e
𝅷f𝅷g𝅷𝅷h𝅷𝅷​​𝅹𝅹i𝅹 𝅹 j




k l m n   
𝅹o𝅹𝅹p




Output after 1st regex
(still has some WS/CC, but none consecutive, except for line breaks):



a b c
d e
f𝅷g𝅷h𝅹i j




k l m n
o𝅹p




Output after 2nd regex
(all previous WS/CC - except for line breaks - are now regular spaces):



a b c
d e
f g h i j




k l m n
o p




Output after 3rd regex
(max 2 consecutive line breaks, and no whitespace other than non-consecutive regular spaces):
a b c
d e
f g h i j

k l m n
o p

Based on my testing, this process seems to work as intended. I would however be very interested if you can think of any cases in which it would fail to behave as expected.

Also - in addition to possible fail-cases - I'd like to know if there are ways I could make these regexes perform better (faster), while still keeping the functionality as is. This is pretty much the first time I've ever done anything in regex, so I'm assuming there's some room for optimizations.

And if you see something else that is done incorrectly/could be done better, do let me know.

EDIT: Added regex101 links
EDIT2: Also, I've heard there's something called ReDoS, or Regex DoS. If you can tell that these regexes are susceptible to those, and which ones specifically, I'd like to know how to avoid them.

\$\endgroup\$
  • 1
    \$\begingroup\$ Would you mind saving and providing the three inputs with their respective three patterns to individual regex101 links for us? This way we can test some refinements with confidence that your sample input data integrity is in tact. (Because whitespaces and control characters may get damage during copy-paste transfer to a regex101 page of our creation.) 3 links are all we need . \$\endgroup\$ – mickmackusa Nov 12 '17 at 7:30
  • \$\begingroup\$ For the record, preg_replace() can handle arrays for patterns and replacement parameters. \$\endgroup\$ – mickmackusa Nov 12 '17 at 7:33
  • \$\begingroup\$ @mickmackusa Yeah, sure, sorry about the late answer. Added the links now. \$\endgroup\$ – user7003859 Nov 12 '17 at 17:16
  • \$\begingroup\$ No idea how to rewrite it efficiently. Perhaps, use 3 different preg_replace statements. This version might work, too, but it is still quite verbose. \$\endgroup\$ – Wiktor Stribiżew Nov 15 '17 at 11:13
  • \$\begingroup\$ Alternatively, you could use a combination of code and regex. For example, start by splitting the string on line breaks; this will remove all line breaks from the output so you no longer need to account for them in regex. For each item in the list, strip out/normalize the white-space using a regex (alternatively, you could use the XSL function normalize-space() to do exactly what you want here, but I don't know what the overhead would be for invoking an XML parser). Drop consecutive empty elements from your list, finally, join all the elements back together separated by '\n'. \$\endgroup\$ – Zack Nov 15 '17 at 16:54
6
+50
\$\begingroup\$

So I've toiled away at this for a while and although I am feeling a little out of my depth I'll submit my approach which employs what I do understand about preg_replace and regex.

  • preg_replace() allows mixed type pattern and replacement parameters, so one call can execute multiple patterns/replacements.
  • Speeding up regex can be achieved by minimizing capture groups and alternatives (pipes) as well as using character classes and negated characters classes where appropriate.

I've prioritized accuracy and endeavored to provide the most robust patterns considering all possible character sequences that may be submitted from the textarea. Then I've attempted to write each pattern with greater efficiency (without impacting accuracy). Finally, I've tried to reduce the overall length and convolution of the regex patterns.

I want to be clear that I don't have any experience with recursive patterns. I don't know how/when to use them effectively and so none of my patterns employ them.

This is the sample input that I used which has whitespaces, newlines (single and greater than double), and control characters:

$text="\0\n\n\1\n\r\n\13\27a ab\r\n\t\t\r\r\ncà\1ê߀\0\0abcbc   d\n\n\t\r\n\5   e\2\n\3\n\4\n";

This input string was designed to be as difficult as possible to best test my method.

$patt_repl=[
    '/^[\s\pC]+|[\s\pC]+$/u'=>'',  // aka mb_trim() -- remove all leading and trailing whitespace and control characters. DO NOT ADD m FLAG TO PATTERN, THAT WILL DAMAGE THE STRING
    '/[\s\pC]*?(\R)[\s\pC]*?(\R)[\s\pC]*/u'=>"\n\n",  // cleans 2 or more new lines (uninterupted by non-white space characters)
    '/(?!\R)[\h\pC]*\R[\h\pC]*(?!\R)/u'=>"\n",    // cleans single new lines
    '/\n+(*SKIP)(*FAIL)|[\h\pC]+/u'=>' '  // convert 1 or more non-newline white-spaces and control characters to single space
];

$text=htmlspecialchars(preg_replace(array_keys($patt_repl),$patt_repl,$text), ENT_HTML5, 'UTF-8');

echo "This is the post-replace/result string dump:\n";
var_dump($text);

Yes, my method uses 4 separate patterns rather than 3 like the OP. This is for improved accuracy. I believe the OP's method had some gaps in accuracy, so that is the justification for the additional pattern.

The output from the above method is:

This is the post-replace/result string dump:
string(28) "a ab

cà ê߀ abcbc d

e"

...which is what I believe the output should be.

  1. It trims all leading and trailing whitespace and control characters from the input string.
  2. It reduces two or more newline characters (which may have leading, in-between, trailing whitespace or control characters) to \n\n.
  3. It trims all leading and trailing horizontal whitespace or control characters from all single newline characters.
  4. It converts 1 or more consecutive horizontal whitespace or control characters to (a single space). This, during my development, required me to use the (*SKIP)(*FAIL) technique to disqualify newline characters becausse \h wasn't doing what I expected. I have read on SO and elsewhere that there can be some quirky/untrustworthy behaviors when dealing with \h and \v while processing certain characters on certain systems -- but I do not possess the necessary wisdom to explain this.

For my own confidence, I wanted to have a way to confirm the existence/absense of whitespace and control characters in the string before and after the method. I found a very helpful function in the top comment at the php manual's ord() page.

Here is a PHP demo that iterates the string and identifies each and every character to prove effectiveness.

Here are a few relevant regex links that I visited during my research:

https://www.regular-expressions.info/unicode.html https://stackoverflow.com/questions/3230623/filter-all-types-of-whitespace-in-php https://stackoverflow.com/questions/5471644/what-are-the-whitespaces-matched-by-s-in-php

On the matter of ReDoS and Catastrophic Backtracking, the threat is minimal (if not non-existent) because of my use of character classes and the structure of my alternatives. In case you haven't already visited it, here is a good page to read if you want to investigate further.

Finally, I humbly ask that if anyone has a string that breaks my method, please provide it to me so that I can update my answer. And if any of my assertions are incorrect, please correct me.

\$\endgroup\$
  • \$\begingroup\$ I've realized some pattern improvements, I'll edit my answer as soon as I can properly. \$\endgroup\$ – mickmackusa Nov 17 '17 at 6:52
  • \$\begingroup\$ Hmm... I wonder if something like $patt_repl=['/\S\K[\s\pC]*?(\n)[\s\pC]*?(\n?)[\h\pC]*|^[\s\pC]+|[\s\pC]+$/u'=>"$1$2",'/\S\K[\h\pC]+/u'=' ']; would work. I'd better run some tests to see if this 2-pattern method can work as required. \$\endgroup\$ – mickmackusa Nov 17 '17 at 13:11
  • \$\begingroup\$ I think there's one ball in the soup in the third pattern, may be something like: [\h\pC]*?\R(?!\R)[\h\pC]* \$\endgroup\$ – Casimir et Hippolyte Nov 18 '17 at 3:07
  • \$\begingroup\$ @Casimir yes, I am least confident in that pattern (of mine). I want to try a 2-pattern method as I recently commented. Is it true that I should not trust \v and \h in php? Do I need to write out the characters that I intend to match (horizontals)? Thanks for your attention, I appreciate it. \$\endgroup\$ – mickmackusa Nov 18 '17 at 3:15
  • 1
    \$\begingroup\$ @user6003859 You've asked a great question. It really got my gears turning about all of the possible fringe cases. I am still refining my answer too (I'll get back to this answer when I find a spare moment). \$\endgroup\$ – mickmackusa Nov 21 '17 at 12:14
6
\$\begingroup\$

First step, start with a simple solution: divide all in simple tasks, keep the patterns short and easily understandable.

$pats = [
    '~\A[\pZ\pC]+|[\pZ\pC]+\z~u', // trim the string
    '~\R~u', // normalize newlines
    '~\pZ+|[^\n\PC]+~u', // replace Z and C with space
    '~^ +| +$| \K +~m', // trim lines, delete consecutive spaces
    '~\n\n\K\n+~' // removes more than 2 consecutive newlines
];

$reps = [ '', "\n", ' ', '', '' ];

$result = preg_replace($pats, $reps, $text);

Whatever the result, it's better to begin with that before trying anything else, particularly to avoid spending time with a set of complicated patterns that, in fine, might be slower. This is essential for future comparisons and provides quickly a working solution.

A mix with classic functions is also possible:

$parts = preg_split('~^[\pC\pZ]+|[\pC\pZ]+$|\R(?:[\pC\pZ]*?(\R)[\pC\pZ]*)?~u', $text, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
$result = implode("\n", array_map(function($i) { return trim(preg_replace('~[\pC\pZ]+~u', ' ', $i));}, $parts));

About pattern performances:

Remove all that is useless, don't capture when you don't need to capture, try to limit the number of groups, branches in alternations. Be careful with subpatterns references (?1): even if the pattern looks shorter, it has a cost (the creation of a capture group, the call to the subpattern). Also, rewriting the subpattern is better than adding a quantifier to it: (?1)+ (one call per repetition).

One of the main cost in a pattern are the alternations in particular when they are at start the pattern. The reason is easy to understand: in the worst case, each branch is tested for a position in the string that doesn't match.

Obviously the best cure is to avoid them, but unfortunately it isn't always possible. You can also try to reduce the number of branches. However, several tricks exist to reduce this cost:

  • sorting the branches by probability of success.

  • the first character discrimination:
    instead of alpha|[0-9]beta|@gamma,
    you can write (?=[a0-9@])(?:alpha|[0-9]beta|@gamma)
    or [a0-9@](?:(?<=a)lpha|(?<=[0-9])beta|(?<=@)gamma).
    This way, positions in the string without an a, a digit or a commercial at sign fail quickly without to test the three alternatives. Obviously, you can try to extend this to more than one character if the entropy of the string is low or if you have many alternatives, but keep in mind that characters in factor at the beginning are tested twice.

  • Studying the pattern: gives good results when each alternative starts with a literal string. With the S modifier, a fast algorithm searches the string for positions of the literal parts for each branch. Once done, the regex engine only tests the pattern at the selected positions.

  • Building a pattern that always succeeds! With this kind of pattern, you are sure that one of the branch will succeed.

Note also that the escape sequence \R isn't a character nor a character class but an alias for (?>\r\n|\n|\x0b|\f|\r|\x85) or (?>\r\n|\n|\x0b|\f|\r|\x85|\xe2\x80[\xa8\xa9]) (depending on the mode). In other word \R is an hidden alternation.

I build a set of patterns/replacements that fits your requirements to illustrate these techniques:

$pats = [ 
  // normalize newlines: Pattern studying
  '~\r\n?|\x0b|\f|\xe2\x80[\xa8\xa9]|\x85~S',

  // replace C and Z chars with a space and keep 1 or 2 newlines
  // if any: always successful pattern
  '~
    [^\pZ\pC]+ \K # part to keep: all that isn t C or Z chars
    \pZ* (?:[^\PC\n]+\pZ*)*   # C and Z chars except newlines

    (?: # keep newlines if any or trim the end of the string
        (\n)                      # one 
        \pZ*+ (?:[^\PC\n]+\pZ*)*+
        (?: (\n) [\pZ\pC]* )?+    # or two newlines (captured)
        (?!\z) # fails if at the end of the string
      |
        [\pZ\pC]+ # end of the string
    )? # eventually
   | 
    [\pZ\pC]+ # start of the string
   ~ux',

  // trim lines: first character discrimination 
  '~ (?:$|(?<=^ ))~m' ];

$reps = [ "\n", '$1$2 ', '' ];

$result = preg_replace($pats, $reps, $text);

Here you can find a test script for the different pattern sets, (you can also pass a callable to the constructor instead of an associative array of pattern/replacements) and useful functions:

https://3v4l.org/iCeHp

About ReDoS attacks:

Except if you finally choose a pathological pattern and doesn't limit the size of posted data, I don't think it's possible to crash your script with your patterns set. It isn't so expensive to run, no more than any other script that filters and validates form data. Other thing, when a pattern is badly written it reaches quickly the backtracking limit, the script doesn't crash and a warning is emitted. You can even retrieve the error using preg_last_error(). If you want to increase the security against DoS, start at the server level, with the apache settings.

\$\endgroup\$
  • \$\begingroup\$ Great review. +1 I didn't know that\R was effectively a piped atomic sequence of characters. \$\endgroup\$ – mickmackusa Nov 18 '17 at 9:16
1
\$\begingroup\$

$str = preg_replace("/^[\pZ]+|[\pZ]+$|([\pZ](?=[^\pL\pN\pS\pP]))/um", '',$str); $str = preg_replace("/[^\pL\pN\pS\pP\pZ\n\r\t\f]/u", '', $str); $str = preg_replace("/(^\R+)|(\R(?=\R{2}|$))/u", '', $str);

Try it

So here are some improvements:

//Trim unnecessary white space (leave line breaks)


$str = preg_replace("/^[\pZ]+|[\pZ]+$|([\pZ](?=[^\pL\pN\pS\pP]))/um", '', $str);

/^[\pZ]+|[\pZ]+$|([\pZ](?=[^\pL\pN\pS\pP]))/gum

(~2ms)

Try it

/(?:^((\pZ)+|((?!\R)\pC)+)(?1)*)|((?1)$)|(?:((?2)+|(?3)+)(?=(?2)|(?3)))/um

(~6ms)

Try it

// Convert remaining whitespace to regular spaces (leave line breaks)


$str = preg_replace("/[^\pL\pN\pS\pP\pZ\n\r\t\f]/u", '', $str);

/[^\pL\pN\pS\pP\pZ\n\r\t\f]/gum

(~0ms)

Try it

/(\pZ+)|((?!\R)\pC)/u

(~2ms) Also doesn't match all whitespace characters

Try it

// Trim line breaks


I couldn't really come up with a solution to this one so I kinda simplified yours:

$str = preg_replace("/(^\R+)|(\R(?=\R{2}|$))/u", '', $str);

/(^\R+)|(\R(?=\R{2}|$))/u

(like 0.03ms faster)

Try it


Note: you can combine both #1 and #2 together like so:

$str = preg_replace("/^[\pZ]+|[\pZ]+$|[^\pL\pN\pS\pP\pZ\n\r\t\f]|([\pZ](?=[^\pL\pN\pS\pP]))/u", '', $str);

/^[\pZ]+|[\pZ]+$|[^\pL\pN\pS\pP\pZ\n\r\t\f]|([\pZ](?=[^\pL\pN\pS\pP]))/gum

Try it

\$\endgroup\$
  • \$\begingroup\$ This answer doesn't not meet the brief. The OP wants to perform 3 separate processes: 1. Omit all leading and trailing white-space and control characters from the string. 2. Reduce 3 or more line breaks to two. and 3. Convert one or more mid-string white-space and control characters as a single space. Having a single pattern and single empty replacement string will not do what is required. \$\endgroup\$ – mickmackusa Nov 15 '17 at 23:01
  • \$\begingroup\$ But this works and I wanted to face this as a challenge, but maybe I did waste 3 hours (just learned rejex :)) \$\endgroup\$ – Bored Nov 16 '17 at 0:54
  • 4
    \$\begingroup\$ Time spent improving your understanding of regex is never time wasted for a developer. \$\endgroup\$ – mickmackusa Nov 16 '17 at 1:01
  • \$\begingroup\$ All posts are editable. If you update your answer to provide a valuable and correct method, I may remove my downvote. The OP has put up half of his/her rep points to represent the importance of receiving advice that is as water-proof as Jesus' feet. I hope the OP gets this. I have invited a few of the "regex masters" that I have met from StackOverflow because I believe mastery is essential to a professional grade set of patterns. \$\endgroup\$ – mickmackusa Nov 16 '17 at 1:12
  • \$\begingroup\$ I guess I'll watch and learn \$\endgroup\$ – Bored Nov 16 '17 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.