Steven Levithan – Page 10 – Flagrant Badassery

The terms single-line and multi-line considered harmful

Alright, that title doesn't really work, but one thing I've encountered quite frequently is that the terms "single-line mode" and "multi-line mode" seem to cause no end of confusion for the vast majority of regex users. Many guides try to explain the terms based on some description of lines, or other unrelated issues. I won't, because I think that's highly misleading. In fact, I shunned the terms in RegexPal in favor of the hopefully more descriptive "dot matches all" (instead of single-line) and "^$ match at line breaks" (instead of multi-line). Another sensible name I've seen used for multi-line mode is "enhanced line-anchor mode".

The first important thing to understand is that single-line and multi-line modes have nothing to do with each other. Hence, they can be applied independently — e.g., sometimes it makes sense to use both at the same time. Single-line mode changes the meaning of the dot, while multi-line mode changes the meaning of ^ and $. There are no other side effects. This means that if your regex does not contain one of those three metacharacters (., ^, $), neither modifier has any impact (except possibly confusing other people who read your regexes).

Let's get more specific…

Dot (.) matches all characters except newlines. In single-line mode, it matches all characters.
Caret (^) matches the position at the beginning of the string. In multi-line mode, it additionally matches the position just after newlines.
Dollar ($) matches the position at the end of the string. With most regex flavors, it also matches just before a string-ending newline. In multi-line mode, it additionally matches the position just before newlines (not only string-ending newlines).

As for exactly which characters are considered newline characters, that is regex-flavor and character-encoding specific. See my last post, JavaScript, Regex, and Unicode, for a precise JavaScript definition.

Finally, although single-line and multi-line modifiers are standard in most Perl-derivative regex flavors, there are a couple notable exceptions.

JavaScript does not have a single-line modifier. Use [\S\s] instead of a dot if you want to match any character including newlines. And for the love of god, don't use (.|\r|\n) or similar — it's terribly inefficient (especially when repeated infinitely) and doesn't match a couple lesser-used newline characters.
In JavaScript, $ without /m matches only the position at the end of the string. It does not match before a string-ending newline.
In Ruby, ^ and $ always match at newlines, and there is no mode to change this. Use \A and \Z to match at the beginning and end of the string only. In fact, what Ruby calls multi-line mode (and implements as /m) is what other regex flavors call single-line mode! Talk about confusing!

Edit: On his blog, Jeffrey Friedl pointed out a related post he'd made on the comp.lang.perl Usenet group back in 1994.

Edit 2: Note that I consider Tcl's "Advanced Regular Expressions" flavor to be more inspired by some features of Perl than actually Perl-derivative. Hence, its peculiarities regarding so-called single-line and multi-line handling are not mentioned here.

JavaScript, Regex, and Unicode

Not all shorthand character classes and other JavaScript regex syntax is Unicode-aware. In some cases it can be important to know exactly what certain tokens match, and that's what this post will explore.

According to ECMA-262 3rd Edition, \s, \S, ., ^, and $ use Unicode-based interpretations of whitespace and newline, while \d, \D, \w, \W, \b, and \B use ASCII-only interpretations of digit, word character, and word boundary (e.g. /a\b/.test("naïve") returns true). Actual browser implementations often differ on these points. For example, Firefox 2 considers \d and \D to be Unicode-aware, while Firefox 3 fixes this bug — making \d equivalent to [0-9] as with most other browsers.

Here again are the affected tokens, along with their definitions:

\d — Digits.
\s — Whitespace.
\w — Word characters.
\D — All except digits.
\S — All except whitespace.
\W — All except word characters.
. — All except newlines.
^ (with /m) — The positions at the beginning of the string and just after newlines.
$ (with /m) — The positions at the end of the string and just before newlines.
\b — Word boundary positions.
\B — Not word boundary positions.

All of the above are standard in Perl-derivative regex flavors. However, the meaning of the terms digit, whitespace, word character, word boundary, and newline depend on the regex flavor, character set, and platform you're using, so here are the official JavaScript meanings as they apply to regexes:

Digit — The characters 0-9 only.
Whitespace — Tab, line feed, vertical tab, form feed, carriage return, space, no-break space, line separator, paragraph separator, and "any other Unicode 'space separator'".
Word character — The characters A-Z, a-z, 0-9, and _ only.
Word boundary — The position between a word character and non-word character.
Newline — The line feed, carriage return, line separator, and paragraph separator characters.

Here again are the newline characters, with their character codes:

\u000a — Line feed — \n
\u000d — Carriage return — \r
\u2028 — Line separator
\u2029 — Paragraph separator

Note that ECMAScript 4 proposals indicate that the C1/Unicode NEL "next line" control character (\u0085) will be recognized as an additional newline character in that standard. Also note that although CRLF (a carriage return followed by a line feed) is treated as a single newline sequence in most contexts, /\r^$\n/m.test("\r\n") returns true.

As for whitespace, ECMA-262 3rd Edition uses an interpretation based on Unicode's Basic Multilingual Plane, from version 2.1 or later of the Unicode standard. Following are the characters which should be matched by \s according to ECMA-262 3rd Edition and Unicode 5.1:

\u0009 — Tab — \t
\u000a — Line feed — \n — (newline character)
\u000b — Vertical tab — \v
\u000c — Form feed — \f
\u000d — Carriage return — \r — (newline character)
\u0020 — Space
\u00a0 — No-break space
\u1680 — Ogham space mark
\u180e — Mongolian vowel separator
\u2000 — En quad
\u2001 — Em quad
\u2002 — En space
\u2003 — Em space
\u2004 — Three-per-em space
\u2005 — Four-per-em space
\u2006 — Six-per-em space
\u2007 — Figure space
\u2008 — Punctuation space
\u2009 — Thin space
\u200a — Hair space
\u2028 — Line separator — (newline character)
\u2029 — Paragraph separator — (newline character)
\u202f — Narrow no-break space
\u205f — Medium mathematical space
\u3000 — Ideographic space

To test which characters or positions are matched by all of the tokens mentioned here in your browser, see JavaScript Regex and Unicode Tests. Note that Firefox 2.0.0.11, IE 7, and Safari 3.0.3 beta all get some of the tests wrong.

Update: My new Unicode plugin for XRegExp allows you to easily match Unicode categories, scripts, and blocks in JavaScript regular expressions.

JavaScript Password Validation

Since I've seen tons of password validation help requests on regexadvice.com (where I hang out from time to time), I've written up a more general-purpose JavaScript password validation function. It's reasonably straightforward, and covers the validation requirements I've most frequently encountered. Plus, if it doesn't handle your exact needs, its functionality can be augmented by passing it custom functions and regular expressions.

Here are the validation types supported out of the box. All are optional, which means that all passwords are allowed by default.

Minimum and maximum length.
Minimum n lowercase characters (a–z).
Minimum n uppercase characters (A–Z).
Minimum n combined a–z and A–Z characters.
Minimum n numeric characters (0–9).
Minimum n special characters (characters other than a–z, A–Z, and 0–9).
Ban particular words (tested case-insensitively).
Ban n-length character sequences (e.g. "abc", "XYZ", or "789", with a sequence length of 3; does not apply to special characters).
Ban n-length qwerty character sequences (e.g. "qwerty" or "asdf", with a sequence length of 4; does not apply to special characters).
Ban sequential, identical characters (e.g. "aa" or "!!").
Use custom regular expressions (tested using RegExp.prototype.test) and functions (the password is provided as the first argument, and a Boolean value is expected in return).

Here's an example of how it can be used:

var password = "password";
var passed = validatePassword(password, {
	length:   [8, Infinity],
	lower:    1,
	upper:    1,
	numeric:  1,
	special:  1,
	badWords: ["password", "steven", "levithan"],
	badSequenceLength: 4
});
// passed: false

The above requires that password is at least eight characters long; has at least one lowercase, uppercase, numeric, and special character; doesn't include the words "password", "steven", or "levithan"; and doesn't include an alphanumeric sequence four or more characters in length (e.g. "1234").

Here's the code (there are no external library dependencies):

/*
	Password Validator 0.1
	(c) 2007 Steven Levithan <stevenlevithan.com>
	MIT License
*/

function validatePassword (pw, options) {
	// default options (allows any password)
	var o = {
		lower:    0,
		upper:    0,
		alpha:    0, /* lower + upper */
		numeric:  0,
		special:  0,
		length:   [0, Infinity],
		custom:   [ /* regexes and/or functions */ ],
		badWords: [],
		badSequenceLength: 0,
		noQwertySequences: false,
		noSequential:      false
	};

	for (var property in options)
		o[property] = options[property];

	var	re = {
			lower:   /[a-z]/g,
			upper:   /[A-Z]/g,
			alpha:   /[A-Z]/gi,
			numeric: /[0-9]/g,
			special: /[\W_]/g
		},
		rule, i;

	// enforce min/max length
	if (pw.length < o.length[0] || pw.length > o.length[1])
		return false;

	// enforce lower/upper/alpha/numeric/special rules
	for (rule in re) {
		if ((pw.match(re[rule]) || []).length < o[rule])
			return false;
	}

	// enforce word ban (case insensitive)
	for (i = 0; i < o.badWords.length; i++) {
		if (pw.toLowerCase().indexOf(o.badWords[i].toLowerCase()) > -1)
			return false;
	}

	// enforce the no sequential, identical characters rule
	if (o.noSequential && /([\S\s])\1/.test(pw))
		return false;

	// enforce alphanumeric/qwerty sequence ban rules
	if (o.badSequenceLength) {
		var	lower   = "abcdefghijklmnopqrstuvwxyz",
			upper   = lower.toUpperCase(),
			numbers = "0123456789",
			qwerty  = "qwertyuiopasdfghjklzxcvbnm",
			start   = o.badSequenceLength - 1,
			seq     = "_" + pw.slice(0, start);
		for (i = start; i < pw.length; i++) {
			seq = seq.slice(1) + pw.charAt(i);
			if (
				lower.indexOf(seq)   > -1 ||
				upper.indexOf(seq)   > -1 ||
				numbers.indexOf(seq) > -1 ||
				(o.noQwertySequences && qwerty.indexOf(seq) > -1)
			) {
				return false;
			}
		}
	}

	// enforce custom regex/function rules
	for (i = 0; i < o.custom.length; i++) {
		rule = o.custom[i];
		if (rule instanceof RegExp) {
			if (!rule.test(pw))
				return false;
		} else if (rule instanceof Function) {
			if (!rule(pw))
				return false;
		}
	}

	// great success!
	return true;
}

You can download it here.

Lemme know if you have any feature requests or other suggestions about how to improve it, or if you need help writing custom rules for it.

/(bb|[^b]{2})/

$/(bb|[^b]{2})/$

…That is the question. ThinkGeek is selling that on a t-shirt for the "regular expression junkie + lover of literature." Wearing that around would be a sure way to get me to notice you, especially if you have a nice rack or happen to be Angelina Jolie.

Note that the parentheses are unnecessary except in the case of Perl-folk wishing to avoid using the naughty $& variable for performance reasons. Also, the expression is buggy in that many alternatives to "bb" are not matched, so it would probably be better written as simply /bb|.*/s. For a JavaScript solution you could try var answer = /^bb$/.test(i);.

Alright, I'm done debugging the shirt now.

Performance of Greedy vs. Lazy Regex Quantifiers

A common misconception about regular expression performance is that lazy quantifiers (also called non-greedy, reluctant, minimal, or ungreedy) are faster than their greedy equivalents. That's generally not true, but with an important qualifier: in practice, lazy quantifiers often are faster. This seeming contradiction is due to the fact that many people rely on backtracking to compensate for the impreciseness of their patterns, often without realizing this is what they're doing. Hence, the previously mentioned misconception stems from that fact that lazy quantifiers often result in much less backtracking when combined with long subject strings and the (mis)use of overly flexible regex tokens such as the dot.

Consider the following simple example: When the regexes <.*?> and <[^>]*> are applied to the subject string "<0123456789>", they are functionally equivalent. The only difference is how the regex engine goes about generating the match. However, the latter regex (which uses a greedy quantifier) is more efficient, because it describes what the user really means: match the character "<", followed by any number of characters which are not ">", and finally, match the character ">". Defined this way, it requires no backtracking in the case of any successful match, and only one backtracking step in the case of any unsuccessful match. Hand-optimization of regex patterns largely revolves around the ideas of reducing backtracking and the steps which are potentially required to match or fail at any given character position, and here we've reduced both cases to the absolute minimum.

So what exactly is different about how a backtracking, leftmost-first regex engine (your traditional NFA engine type, which describes most modern, Perl-derivative flavors) goes about matching our subject text when working with these two regexes? Let's first take a look at what happens with <.*?>. I'll use the RegexBuddy debugger style to illustrate each step.

Note: If you're reading this in a feed reader or aggregator which strips out inline styles, see the original post, which should make things much easier to follow.

Beginning match attempt at character 0
<
<ok
<backtrack
<0
<0backtrack
<01
<01backtrack
<012
<012backtrack
<0123
<0123backtrack
<01234
<01234backtrack
<012345
<012345backtrack
<0123456
<0123456backtrack
<01234567
<01234567backtrack
<012345678
<012345678backtrack
<0123456789
<0123456789>
Match found

The text ok means the engine completed a successful, zero-length match, and backtrack shows where the engine backtracks to the last choice point, which it does after trying and failing to match the next token (>). As you can see here, with lazy quantification the engine backtracks forward after each character which is not followed by ">".

Here's what happens with <[^>]*>:

Beginning match attempt at character 0
<
<0123456789
<0123456789>
Match found

As you can see, 20 fewer steps are required, and there is no backtracking. This is faster, and can also increase the potential for internal optimization of the matching process. As a simple example, when greedily quantifying an any-character token, the engine can simply move the read-head to the end of the string, rather than testing every character along the way (this is an oversimplification of the process taken by modern regex engines, but you get the idea). You can see this exact kind of internal optimization occurring in IE with the "trim8" pattern in my Faster JavaScript Trim post from a while back.

You might be wondering what happens if we use the regex <.*>. Take a look:

Beginning match attempt at character 0
<
<0123456789>
<0123456789>backtrack
<0123456789
<0123456789>
Match found

Although the output didn't change much when used with our subject string of "<0123456789>", you can see that the .* caused the engine to trek all the way to the end of the string, then backtrack from the right. If we'd used a 10,000-character string without newlines or other ">" characters, that would've resulted in nearly 10,000 backtracks.

In short:

Make your patterns more explicit where it makes sense, to better guide the regex engine and avoid backtracking.
Be careful about using the more appropriate type of quantification (to your best approximation, since this often depends on the subject string) even when it has no impact on the text matched by your regex.
If possible, avoid greedy quantification of the dot and other needlessly flexible tokens.