09_regexp.txt

:chap_num: 9
:prev_link: 08_error
:next_link: 10_modules

= Regular Expressions =

[quote,Jamie Zawinski]
____
Some people, when confronted with a problem, think ‘I know, I'll use
regular expressions.’ Now they have two problems.
____

[quote, Master Yuan-Ma, The Book of Programming]
____
Yuan-Ma said, ‘When you cut against the grain of the wood, much
strength is needed. When you program against the grain of a problem,
much code is needed.’
____

The way programming conventions and techniques survive and spread
happens in a chaotic, evolutionary way. It's not usually the pretty or
brilliant ones that win, but rather the ones that combine working
passably well with sitting in the right niche—for example by being
integrated with another successful piece of technology.

In this chapter I will discuss one such technology, _regular
expressions_. Regular expressions are a way to describe patterns in
string data. They form a small, separate language that is part of
JavaScript (as well as various other programming languages and tools).

Regular expressions are both extremely useful and terribly awkward.
Learning them properly will make it much easier to inspect and process
strings. Yes the syntax used for these expressions is cryptic, and the
programming interface JavaScript provides for them is clumsy.

== Notation ==

A regular expression is an object. It can either be constructed with
the `RegExp` constructor or written as a literal value by enclosing
the pattern in slash (‘/’) characters.

[source,javascript]
----
var re1 = new RegExp("abc");
var re2 = /abc/;
----

Such an object represents a pattern. In this case, the pattern is an
“a” character followed by “b” and “c”.

When using the `RegExp` constructor, the pattern is written as a
normal string, so the usual rules apply for backslashes. In the second
notation, we are using slashes to delimit the pattern, so we'd have to
backslash-escape slash characters that are part of the pattern. Some
other characters, such as question marks and plus signs, are used as
special markers in regular expressions, and must to be preceded by a
backslash if they are meant to represent the character itself.

[source,javascript]
----
var onePlusOne = /1 \+ 1/;
----

Knowing precisely what characters to backslash-escape when writing
regular expressions requires you to know about all the special meaning
assigned to characters by this syntax. For the time being, this may
not be realistic. When in doubt, it is safe to just put a backslash
before any character that is not a letter, number, or whitespace.

== Testing for matches ==

(((test method)))Regular expression objects have a number of methods.
The simplest one is `test`, which you pass a string, and which will
return a boolean that tells you whether the pattern contained in the
expression matches the string.

[source,javascript]
----
console.log(/abc/.test("abcde"));
// → true
console.log(/abc/.test("12345"));
// → false
----

A regular expression consisting of only normal characters simply
represents that sequence of characters. If “abc” occurs anywhere (not
just at the start) in the string we are testing against, the result
will be true.

== Matching a set of characters ==

(((indexOf method)))Finding out whether a string contains “abc” could
just as well be done with a call to `indexOf`. Regular expressions are
able to express more complicated patterns.

Say we want to match any number. In a regular expression, putting a
set of characters between square brackets makes that part of the
expression match any of the characters between the brackets.

The expressions below matche all strings that contains a digit.

[source,javascript]
----
console.log(/[0123456789]/.test("in 1992"));
// → true
console.log(/[0-9]/.test("in 1992"));
// → true
----

(((digit (regexp))))Between square brackets, a dash (“-”) between two
characters can be used to indicate a range of characters. Since the
Unicode character codes for “0” to “9” sit right next to each other
(codes 48 to 57), `[0-9]` covers all of them, and matches any digit.

(((whitespace (regexp))))(((alphanumeric character (regexp))))(((dot
(regexp)))) There are a number of commonly use character groups that
have their own built-in shortcuts. Digits are one of them—you can
write backslash-d (`\d`) to mean the same thing as `[0-9]`.

[cols="1,5"]
|====
|`\d`      |Digit characters
|`\w`      |Alphanumeric characters (“word characters”)
|`\s`      |Whitespace characters (space, tab, newline, and similar)
|`\D`      |Characters that are _not_ digits
|`\W`      |Non-alphanumeric characters
|`\S`      |Non-whitespace characters
|`.`       |A period matches all characters except newlines
|====

For each of the backslash-prefixed categories, there is an uppercase
variant that means the exact opposite.

So you could express a date and time format like “30/01/2003 15:20” with
the following expression:

[source,javascript]
----
var dateTime = /\d\d\/\d\d\/\d\d\d\d \d\d:\d\d/;
console.log(dateTime.test("30/01/2003 15:20"));
// → true
console.log(dateTime.test("30/jan/2003 15:20"));
// → false
----

(((backslash)))Looks completely awful, doesn't it? Way too many
backslashes, producing a background noise that makes it hard to spot
the actual pattern expressed. Such is life with regular expressions.

These category markers can also be used inside of square brackets, so
`[\d\.]` means any digit or a dot.

To “invert” a set of characters, to express that you want to match any
character _except_ the ones in the set, a caret (‘^’) character is
written after the opening bracket.

[source,javascript]
----
var notBinary = /[^01]/;
console.log(notBinary.test("01101"));
// → false
console.log(notBinary.test("01201"));
// → true
----

== Repeating parts of a pattern ==

We now know how to match a single digit. What if we want to match a
whole number—a sequence of one or more digits?

(((repetition (regexp))))(((\* operator)))(((+ operator)))When you put
a plus sign (‘+’) after something in a regular expression, that
indicates that it may be repeated more than once. Thus, `/\d+/`
matches one or more digit characters.

[source,javascript]
----
console.log(/'\d+'/.test("'123'"));
// → true
console.log(/'\d+'/.test("''"));
// → false
console.log(/'\d*'/.test("'123'"));
// → true
console.log(/'\d*'/.test("''"));
// → true
----

The star (‘*’) has a similar meaning, but also allows the pattern to
match zero times. So something with a star after it never prevents a
pattern from matching—it'll just match zero instances if it can't find
any suitable text to match.

A question mark makes a part of a pattern “optional”, meaning it may
occur zero or one times. In this example, the “u” character is allowed
to occur, but the pattern also matches when it is missing.

[source,javascript]
----
var neighbor = /neighbou?r/;
console.log(neighbor.test("neighbour"));
// → true
console.log(neighbor.test("neighbor"));
// → true
----

To allow a pattern to occur a precisely defined number of times, curly
braces are used. Putting `{4}` after an element requires it to occur
exactly four times. Similarly, `{2,4}` is used when the element must
occur at least twice, and at most four times.

Here is another version of the date and time pattern. It allows
single-digit day, month, and hour numbers, and is slightly more
readable:

[source,javascript]
----
var dateTime = /\d{1,2}\/\d{1,2}\/\d{4} \d{1,2}:\d{2}/;
console.log(dateTime.test("30/1/2003 8:45"));
// → true
----

It is also possible to leave either the minimum or the maximum amount
of occurrences open-ended, by omitting the number on one side of the
comma. So `{,5}` means zero to five times, and `{5,}` means five or
more times.

== Grouping sub-expressions ==

(((grouping (regexp))))To use an operator like ‘*’ or ‘+’ on more than
one character at a time, need to use parentheses. A piece of a regular
expression that is surrounded in parentheses counts as a single unit
as far as the operators following it are concerned.

[source,javascript]
----
var cartoonCrying = /boo+(hoo+)+/i;
console.log(cartoonCrying.test("Boohoooohoohooo"));
// → true
----

The third ‘+’ applies to the whole group `(hoo+)`, matching one or
more sequences like that.

(((case-sensitivity (regexp))))The “i” at the end of the expression in
the example above makes this regular expression case-insensitive,
allowing it to match the uppercase “B” in the input string, even
though the pattern is itself all lowercase.

== Matches and groups ==

The `test` method is the absolute simplest way to match a regular
expression. It only tells you whether it matched, and nothing else.
Regular expressions also have an `exec` (execute) method, that will
return `null` when no match was found, and an object with information
about the match otherwise.

[source,javascript]
----
var match = /\d+/.exec("one two 100");
console.log(match);
// → ["100"]
console.log(match.index);
// → 8
----

(((match method)))String values have a `match` method that behaves
very similarly.

[source,javascript]
----
console.log("one two 100".match(/\d+/));
// → ["100"]
----

(((index property)))An object returned from `exec` or `match` has an
`index` property that tells us _where_ in the string the successful
match started. Otherwise, the object looks like (and in fact is) an
array of strings, whose first element is the string that was
matched—in the example above, that is the sequence of digits that we
were looking for.

When the regular expression contains expressions grouped with
parentheses, the text that matched those groups will also show up in
the array. The first element is always the whole match, after that
follows the part matched by the first group (the one whose opening
parenthesis comes first in the expression), then the second, and so
on.

[source,javascript]
----
var quotedText = /'([^']*)'/;
console.log(quotedText.exec("she said 'hello'"));
// → ["'hello'", "hello"]
----

When a group does not end up being matched at all (for example when
followed by a question mark), its position in the output array will
hold `undefined`. Similarly, when a group is matched multiple times,
only the last match ends up in the array.

[source,javascript]
----
console.log(/bad(ly)?/.exec("bad"));
// → ["bad", undefined]
console.log(/(\d)+/.exec("123"));
// → ["123", "3"]
----

Groups can be very useful for extracting parts of a string. If we do
not just want to verify whether a string contains a date, but also
extract it and construct an object that represents it, we can wrap
parentheses around the digit patterns, and directly pick them out of
the result of `exec`.

But first, a short detour.

== The date type ==

JavaScript has a standard object type for representing dates—or
rather, points in time. It is called `Date`. If you simply create a
date object using `new`, you get the current date and time.

// test: no

[source,javascript]
----
console.log(new Date());
// → Wed Dec 04 2013 14:24:57 GMT+0100 (CET)
----

You can also create an object for a specific time.

[source,javascript]
----
console.log(new Date(2009, 11, 9));
// → Wed Dec 09 2009 00:00:00 GMT+0100 (CET)
console.log(new Date(2009, 11, 9, 12, 59, 59, 999));
// → Wed Dec 09 2009 12:59:59 GMT+0100 (CET)
----

JavaScript uses a convention where month numbers start at zero (so
December is 11), yet day numbers start at one. This is confusing and
silly. Be careful.

The last four arguments (hours, minutes, seconds, and milliseconds)
are optional, and taken to be zero when not given.

Timestamps are in fact stored as the number of milliseconds since the
start of 1970. The `getTime` method on a date object returns this
number. It is big, as you can imagine.

[source,javascript]
----
console.log(new Date(2013, 11, 19).getTime());
// → 1387407600000
console.log(new Date(1387407600000));
// → Thu Dec 19 2013 00:00:00 GMT+0100 (CET)
----

When giving the `Date` constructor a single argument, that argument is
treated as such a millisecond number.

Date objects provide methods like `getFullYear` (`getYear` gets you
the useless two-digit version), `getMonth`, `getDate`, `getHours`,
`getMinutes`, and `getSeconds` to extract their components.

So now, putting parentheses around the parts of the expression that we
are interested in, we can easily extract a date from a string.

[source,javascript]
----
function findDate(string) {
  var dateTime = /(\d{1,2})\/(\d{1,2})\/(\d{4})/;
  var match = dateTime.exec(string);
  return new Date(Number(match[3]), Number(match[2]),
                  Number(match[1]));
}
console.log(findDate("30/1/2003"));
// → Sun Mar 02 2003 00:00:00 GMT+0100 (CET)
----

== Word and string boundaries ==

The `findDate` function will also happily extract a date from the
string `"100/1/30000"`—a match may happen anywhere in the string, so
in this case it'll just start at the second character and end at the
one-but-last.

(((boundary (regexp))))If we want to enforce that the match must span
the whole string, we can add the markers ‘^’ and ‘$’. The first
matches the start of the input string, and the second the end. So
`/^\d+$/` matches a string consisting entirely of one or more digits,
`/^!/` matches any string that starts with an exclamation sign, and
`/x^/` does not match anything (the start of a string can not be after
a character).

(((word boundary (regexp))))If, on the other hand, we just want to
make sure the date starts and ends on a word boundary, we can use the
marker `\b`. A word boundary is a point that has a word character on
one side, and a non-word character on the other.

[source,javascript]
----
console.log(/cat/.test("concatenate"));
// → true
console.log(/\bcat\b/.test("concatenate"));
// → false
----

Note that these boundary markers don't “cover” any actual characters,
they just enforce that the pattern only matches when a certain
condition holds at the place where they appear.

== Alternatives ==

Next, we want to know whether a piece of text contains not only a
number, but a number followed by one of the words “pig”, “cow”, or
“chicken”, or their plural forms.

We could write three regular expressions, and test them in turn, but
there is a nicer way. The pipe character (`|`) denotes a choice
between the pattern to its left and the pattern to its right. So I can
say this:

[source,javascript]
----
var animalCount = /\b\d+ (pig|cow|chicken)s?\b/;
console.log(animalCount.test("15 pigs"));
// → true
console.log(animalCount.test("15 pigchickens"));
// → false
----

Parentheses can be used to limit the part of the pattern that the pipe
operator applies to, and you can put multiple such operators next to
each other to express a choice between more than two patterns.

== The mechanics of matching ==

Regular expressions can be thought of as flow diagrams. This is the
diagram for the livestock expression in the previous example:

image::img/re_pigchickens.svg[alt="Visualization of /\b\d+ (pig|cow|chicken)s?\b/"]

A string matches the expression if a path from the start (left) to the
end (right) of the diagram can be found, with a corresponding start
and end position in the string, such that every time we go through a
box, we verify that our current position in the string corresponds to
the element described by the box and, for elements that match actual
characters (which the word boundaries do not), move our position
forward.

So if we match `"the 3 pigs"` there is a match between positions 4
(the digit “3”) and 10 (the end of the string).

 - At position 4, there is a word boundary, so we can move past the
   first box.

 - Still at position 4, we find a digit, so we can also move past the
   second box.

 - At position 5, we could go back to before the second (digit) box,
   or move forward through the box that holds a single space
   character. There is a space here, not a digit, so we choose the
   second path.

 - We are now at position 6 (the start of “pigs”) and at the three-way
   branch in the diagram. We don't see “cow” or “chicken” here, but we
   do see “pig”, so we take that branch.

 - At position 9, after the three-way branching, we could either skip
   the “s” box and go straight to the final word boundary, or first
   match an “s”. There is an “s” character here, not a word boundary,
   so we go through the “s” box.

 - We're at position 10 (end of the string) and can only match a word
   boundary. The end of a string counts as a word boundary, so we go
   through the last box and have successfully matched this string.

The way the regular expression engine present in a JavaScript system
will conceptually look for a match in a string is simple. It starts at
the start of the string and tries a match there. In this case, there
_is_ a word boundary there, so it'd get past the first box, but there
is no digit, so it'd fail at the second box. Then it moves on to the
second character in the string, and tries there. And so on, until it
finds a match, or reaches the end of the string and decides that there
really is no match.

== Backtracking ==

(((backtracking)))The regular expression `/\b([01]+b|\d+|[\da-f]h)\b/`
matches either a binary number followed by a “b”, a regular decimal
number without suffix character, or a hexadecimal number (base 16,
with the letters “a” to “f” standing for the digits 10 to 15) followed
by an “h”. This is the corresponding diagram:

image::img/re_number.svg[alt="Visualization of /\b([01]+b|\d+|[\da-f]h)\b/"]

When matching this expression, it will often happen that the top
(binary) branch is entered although the input does not actually
contain a binary number. When matching the string `"103"`, it is only
at the “3” that it becomes clear that we are in the wrong branch. The
string does match the expression, just not the branch we are currently
in.

What happens then is that the matcher _backtracks_. When entering a
branch, it remembers where it was when it entered the current branch
(in this case, at the start of the string, just past the first
boundary box in the diagram), so that it can go back and try another
branch if the current one does not work out. So for the string
`"103"`, after encountering the “3” character, it will start trying
the decimal (second) branch. This one matches, so a match is reported
after all.

When more than one branch matches, the first one (in the order in
which the branches appear in the expression) will be taken.

Backtracking also happens, in slightly different forms, when matching
repeat operators. If you match `/^.*x/` against `"abcxe"`, the `.*`
part will first try to match the whole string. It'll then realize that
it can only match when it is followed by an “x”, and there is no “x”
past the end of the string. So it tries to match one character less.
And then another character less. And _now_ it finds an “x” where it
needs it, and reports a successful match from position 0 to 4.

It is possible to write regular expressions that will do a _lot_ of
backtracking. This problem occurs when a pattern can match a piece of
input in many different ways. For example, if we get confused while
writing our binary-number regexp and accidentally write something like
`/([01]+)+b/`.

image::img/re_slow.svg[alt="Visualization of /([01]+)+b/"]

If that tries to match some long series of zeroes and ones _without_ a
“b” character after them, it will first go through the inner loop
until it runs out of digits. Then it notices there is no “b”, so it
backtracks one position, goes through the _outer_ loop once, and give
up again, backtracking out of the inner loop once more. It will
continue to try every possible route through these two loops, which
means the amount of work it needs to do doubles with each additional
character. For a few dozen characters, the resulting match will
already take practically forever.

== The replace method ==

(((replace method)))(((regular expression!replacing)))String values
have a `replace` method, which can be used to replace parts of the
string with another string.

[source,javascript]
----
console.log("papa".replace("p", "m"));
// → mapa
----

The first argument can also be a regular expression, in which case the
first match of the regular expression is replaced.

[source,javascript]
----
console.log("Borobudur".replace(/[ou]/, "a"));
// → Barobudur
console.log("Borobudur".replace(/[ou]/g, "a"));
// → Barabadar
----

When a “g” option (for “global”) is added to the regular expression,
_all_ matches in the string will be replaced, not just the first.

It would have been sensible if the choice between replacing one match
or all matches was made through an addition argument to `replace`, or
by providing a different method `replaceAll`. But for some reason, the
choice was made to rely on a property of the regular expression
instead.

The real power of using regular expressions with `replace` comes from
the fact that we can refer back to the matched groups in the
replacement string. For example, say we have a big string containing
the names of people, one name per line, in the format `Lastname,
Firstname`. If we want to swap these names and remove the comma to get
a simple `Firstname Lastname` format, we can use the following code:

[source,javascript]
----
console.log(
  "Hopper, Grace\nMcCarthy, John\nRitchie, Dennis"
    .replace(/([\w ]+), ([\w ]+)/g, "$2 $1"));
// → Grace Hopper
//   John McCarthy
//   Dennis Ritchie
----

The `$1` and `$2` in the replacement string refer to the parenthesized
parts in the pattern. `$1` is replaced by the text that matched
against the first pair of parentheses, `$2` by the second, and so on,
up to `$9`.

It is also possible to pass a function, rather than a string, as the
second argument to `replace`. For each replacement, the function will
be called with the matched groups (as well as the whole match) as
arguments, and the value it returns will be inserted into the new
string.

Here's a simple example:

[source,javascript]
----
var s = "the cia and fbi";
console.log(s.replace(/\b(fbi|cia)\b/g, function(str) {
  return str.toUpperCase();
}));
// → the CIA and FBI
----

And here's another one:

[source,javascript]
----
var stock = "1 lemon, 2 cabbages, and 101 eggs";
function minusOne(match, amount, unit) {
  amount = Number(amount) - 1;
  if (amount == 1) // only one left, remove the 's'
    unit = unit.slice(0, unit.length - 1);
  else if (amount == 0)
    amount = "no";
  return amount + " " + unit;
}
console.log(stock.replace(/(\d+) (\w+)/g, minusOne));
// → no lemon, 1 cabbage, and 100 eggs
----

This takes a string, finds all occurrences of a number followed by an
alphanumeric word, and returns a string wherein every such occurrence
is decremented by one.

The `(\d+)` group ends up as the `amount` argument to the function,
and the `(\w+)` group gets bound to `unit`. The function converts the
amount to a number—which always works, since it matched `\d+`—and
makes some adjustments in case there is only one or zero left.

== Greed ==

It isn't hard to use `replace` to write a function that removes all
comments from a piece of JavaScript code. Here is the first attempt:

// test: wrap

[source,javascript]
----
function stripComments(code) {
  return code.replace(/\/\/.*|\/\*[\w\W]*\*\//g, "");
}
console.log(stripComments("1 + /* 2 */3"));
// → 1 + 3
console.log(stripComments("x = 10;// ten!"));
// → x = 10;
console.log(stripComments("1 /* a */+/* b */ 1"));
// → 1  1
----

The part before the “or” operator simply matches two slash characters
followed by any number of non-newline characters. The part for
multi-line comments is more involved. We use `[\w\W]` as a way to
match any character. Block comments can continue on a new line, so we
can't use a dot here. Matching something that is either a word
character or not a word character will match all possible characters.

But the output of the last example appears to have gone wrong. Why?

The `.*` part of the expression, as I described in the section on
backtracking, will first match as much as it can, and then, if that
causes the part of the pattern after it to fail, move back one match
at a time and try from there. In this case, we are first matching the
whole rest of the string, and then moving back from there. It will
find an occurrence of `*/` after going back four characters, and match
that. This is not what we wanted—the intention was to match a single
comment, not to go all the way to the end of the code and find the end
of the last block comment.

There are two variants of the repetition operators in regular
expressions (‘+’, ‘*’, ‘?’, and ‘{}’). By default, they are _greedy_,
meaning they match as much as they can and backtrack back from there.
If you put a question mark after them, they become non-greedy, and
start by matching as little as possible, and only matching more when
the remaining pattern does not fit with the smaller match.

And that is exactly what we want in this case. By having the star
match the smallest stretch of characters that brings us to a “++*/++”
closing marker, we consume one block comment, and nothing more.

// test: wrap

[source,javascript]
----
function stripComments(code) {
  return code.replace(/\/\/.*|\/\*[\w\W]*?\*\//g, "");
}
console.log(stripComments("1 /* a */+/* b */ 1"));
// → 1 + 1
----

== Dynamically creating RegExp objects ==

(((RegExp type)))There are cases where you might not know the exact
pattern you need to match against when you are writing your code. Say
you want to look for the user's name in a piece of text, and enclose
it in underscore characters to make it stand out. The name is only
known when the program is actually running, so we can not use the
slash-based notation.

But we can build up a string and use the `RegExp` constructor on that.
For example:

[source,javascript]
----
var name = "harry";
var text = "Harry is a suspicious character.";
var regexp = new RegExp("\\b(" + name + ")\\b", "gi");
console.log(text.replace(regexp, "_$1_"));
// → _Harry_ is a suspicious character.
----

When creating the `\b` boundary markers, we have to use two
backslashes, because we are writing them in a normal string, not a
slash-enclosed regular expression. The options (global and
case-insensitive) for the regular expression can be given as a second
argument to the `RegExp` constructor.

But what if the name is `"dea+hl[]rd"` because our user is a nerdy
teenager? That would cause us to produce a bogus regular expression,
which will cause unexpected results.

To work around this, we can add backslashes before any character that
we don't trust. Adding backslashes before alphabetic characters is a
bad idea, because things like `\b` and `\n` have a special meaning.
But escaping everything that's not alphanumeric or whitespace is safe.

[source,javascript]
----
var name = "dea+hl[]rd";
var text = "This dea+hl[]rd guy is super annoying.";
var escaped = name.replace(/[^\w\s]/g, "\\$&");
var regexp = new RegExp("\\b(" + escaped + ")\\b", "gi");
console.log(text.replace(regexp, "_$1_"));
// → This _dea+hl[]rd_ guy is super annoying.
----

The `$&` placeholder in the replacement string acts similar to `$1`,
but will be replaced by the whole match, rather than a matched group.

== The search method ==

(((indexOf method)))(((search method)))The `indexOf` method on strings
can not be called with a regular expression. But there is another
method, `search`, which does expect a regular expression. Like
`indexOf`, it returns the first index on which the expression was
found or -1 when it wasn't found.

[source,javascript]
----
console.log("  word".search(/\S/));
// → 2
console.log("    ".search(/\S/));
// → -1
----

Unfortunately, there is no way to indicate that the match should start
at a given offset (as with the second argument to `indexOf`), which
would often be very useful.

== The lastIndex property ==

(((exec method)))The `exec` method similarly does not provide a
convenient way to start searching from a given position in the string.
But it does provide an inconvenient way.

(((source property)))(((lastIndex property)))Regular expression
objects have properties (such as `source`, which contains the string
that expression was created from). One such property, `lastIndex`,
controls, in some limited circumstances, where the next match will
start.

Those circumstances are that the regular expression must have the
“global” (`g`) option enabled, and the match must happen through the
`exec` method. Again, the sane way would have been to just allow an
extra argument to be passed to `exec`, but sanity is not a defining
characteristic of JavaScript's regular expression interface.

[source,javascript]
----
var pattern = /y/g;
pattern.lastIndex = 3;
var match = pattern.exec("xyzzy");
console.log(match.index);
// → 4
console.log(pattern.lastIndex);
// → 5
----

The `lastIndex` property is updated by the call to `exec` to point
after the match, when the match was successful. When no match was
found, `lastIndex` is set back to zero, which is also the value it
has in a newly constructed regular expression object.

When using a global regular expressions value for multiple `exec`
calls, this changing of the `lastIndex` property can cause
problems—your regular expression might be accidentally starting at an
index that was left over from a previous call.

(((match method)))Another interesting effect of the global option is
that changes the way the `match` method on strings works. When called
with a global expression, instead of returning an array similar to
that returned by `exec`, `match` will find _all_ matches of the
pattern in the string, and return an array containing the matched
strings.

[source,javascript]
----
console.log("Banana".match(/an/g));
// → ["an", "an"]
----

So be cautious with global regular expressions. The cases where they
are necessary—calls to `replace` and places where you want to
explicitly use ++lastIndex++—are typically the only places where you
want to use them.

A common pattern is to scan through all occurrences of a pattern in a
string, with full access to matched groups and the `index` property,
by using `lastIndex` and `exec`.

[source,javascript]
----
var input = "A text with 3 numbers in it... 42 and 88.";
var number = /\b(\d+)\b/g;
var match;
while (match = number.exec(input))
  console.log("Found", match[1], "at", match.index);
// → Found 3 at 12
//   Found 42 at 31
//   Found 88 at 38
----

This makes use of the fact that the value of an assignment expression
(‘=’) is the assigned value. So by using `match = re.exec(input)` as
the condition in the `while` statement, we both perform the match at
the start of each iteration, save its result in a variable, and stop
looping when no more matches are found.

== Parsing an INI file ==

(((ini file)))Now let's look at a real problem that calls for regular
expressions. Imagine we are writing a program to automatically harvest
information about our enemies from the Internet. (We will not actually
write that program here, just the part that reads the configuration
file. Sorry to disappoint.) This configuration file looks like this:

[source,text/plain]
----
searchengine=http://www.google.com/search?q=$1
spitefulness=9.7

; comments are preceded by a semicolon...
; these are sections, concerning individual enemies
[larry]
fullname=Larry Doe
type=kindergarten bully
website=http://www.geocities.com/CapeCanaveral/11451

[gargamel]
fullname=Gargamel
type=evil sorcerer
outputdir=/home/marijn/enemies/gargamel
----

(((grammar)))The exact rules for this format (which is actually a
widely used format, usually called an _INI_ file) are as follows:

- Blank lines and lines starting with semicolons are ignored.

- Lines wrapped in `[` and `]` start a new section.

- Lines containing an alphanumeric identifier followed by an `=`
  character add a setting to the current section.

- Anything else is invalid.

Our task is to convert a string like this into an array of objects,
each with a `name` property and an array of `name`/`value` pairs.
We'll need one such object for each section and one for the
section-less settings at the top.

Since the format has to be processed line by line, splitting the file
up into separate lines is a good start. We've used the `split` method
once in Chapter 6, as `string.split("\n")`. Some operating systems,
however, use not just a newline character to separate lines but a
carriage return character followed by a newline (`"\r\n"`).

Given that the `split` method also allows a regular expression as its
argument, we can split on a regular expression like `/\r?\n/` to split
in a way that allows both `"\n"` and `"\r\n"` between lines.

[source,javascript]
----
function parseINI(string) {
  var currentCategory = {name: null, fields: []};
  var categories = [currentCategory];

  string.split(/\r?\n/).forEach(function(line) {
    var match;
    if (/^\s*(;.*)?$/.test(line)) {
      return;
    } else if (match = line.match(/^\[(.*)\]$/)) {
      currentCategory = {name: match[1], fields: []};
      categories.push(currentCategory);
    } else if (match = line.match(/^(\w+)=(.*)$/)) {
      currentCategory.fields.push({name: match[1],
                                   value: match[2]});
    } else {
      throw new Error("Line '" + line + "' is invalid.");
    }
  });

  return categories;
}
----

The code goes over every line in the file. It keeps a “current
category” object, and when it finds a normal directive, it adds it to
this object. When it encounters a line that starts a new category, it
replaces the current category with a new one, to which subsequent
directives will get added. Finally, it returns an array containing all
the categories it came across.

Note the recurring use of `^` and `$` to make sure the expression
matches the whole line, not just part of it. Leaving these out is a
common mistake, which results in code that mostly works but behaves
strangely for some input.

The expression `/^\s*(;.*)?$/` can be used to test for lines that can
be ignored. Do you see how it works? The part between the parentheses
will match comments, and the `?` after that will make sure it also
matches lines with only whitespace.

The pattern `if (match = string.match(...))` is similar to the trick
where I used an assignment as the condition for `while`. You usually
aren't sure that your expression will match. But you only want to do
something with the resulting match array if it not null, so you need
to test for that first. To not break the pleasant chain of `if` forms,
we can assign this result to a variable as the test for `if` and do
the matching and the testing in a single line.

== International characters ==

Due to an initial simplistic implementation and the fact that this
simplistic approach was later set in stone as standard behavior,
JavaScript's regular expressions are rather dumb about characters that
do not appear in the English language. For example “word” characters,
in this context, actually means the 26 characters in the Latin
alphabet, their upper-case variants, and, for some reason, the
underscore character. Things like “é” or “β”, which most definitely
are word characters, will not match `\w` (and _will_ match upper-case
`\W`, the non-word category).

Through strange historical accident, `\s` (whitespace) is different,
and will match all characters that the Unicode standard considers
whitespace, such as a non-breaking space or a Mongolian vowel
separator.

Some regular expression implementations in other programming languages
have syntax to match specific Unicode character categories, such as
all uppercase letters, all punctuation, control characters, or
similar. There are plans to add support to this to JavaScript, but
they unfortunately look like they won't be realized in the near
future.

== Summary ==

Regular expressions are objects that represent patterns in strings.
They use their own syntax for expressing these patterns.

[cols="1,5"]
|====
|`/abc/`     |Sequence of characters
|`/[abc]/`   |Any character from a set of characters
|`/[^abc]/`  |Any character _not_ in a set of characters
|`/[0-9]/`   |Any character in a range of characters
|`/x+/`      |One or more occurrences of a pattern
|`/x+?/`     |One or more occurrences, non-greedy
|`/x*/`      |Zero or more occurrences
|`/x?/`      |Zero or one occurrence
|`/x{2,4}/`  |Between two and four occurrences
|`/(abc)+/`  |Grouping
|++/a{brvbar}b{brvbar}c/++ |Alternative patterns
|`/\d/`      |Digit characters
|`/\w/`      |Alphanumeric characters (“word characters”)
|`/\s/`      |Whitespace characters
|`/./`       |All characters except newlines
|`/\b/`      |Word boundary
|`/^/`       |Start of input
|`/$/`       |End of input
|====

A regular expression has a method `test` to test whether a given
string matches it, and a method `exec` which, when a match is found,
returns an array containing all matched groups and an `index` property
that indicates where the match started.

Strings have a `match` method to match them against a regular
expression, and a `search` method to search for one. Their `replace`
method can replace matches of a pattern with a replacement string.
Alternatively, a function can be passed that builds up a replacement
based on the match text and matched groups.

Regular expressions can have options (flags), which are written after
the closing slash. The “i” option makes the match case-insensitive,
and the “g” flag makes the expression global which, among other
things, causes the `replace` method to replace all instances instead
of just the first.

The `RegExp` constructor can be used to create a regular expression
value from a string.

Regular expressions are a sharp tool with an awkward handle. They'll
simplify some tasks tremendously, but quickly become unmanageable when
applied to complex problems. Part of knowing how to use them is
knowing when to give up on them and switch to a more explicit
approach.

== Exercises ==

It is almost unavoidable that, in the course of working on these
exercises, you will be confused and frustrated by some regular
expression's inexplicable behavior. What sometimes helps is entering
your expression into an online tool like
https://www.debuggex.com/[debuggex.com], to see whether its
visualization corresponds to what you intended, and to experiment with
the way it responds to various input strings.

=== Regex golf ===

“Code golf” is a term used for the game of trying to express a
particular program in as few characters as possible. Similarly, regex
golf is the practice of writing as tiny a regular expression as
possible to match a given pattern (and only that pattern).

Write regular expressions that tests whether any of the sub-strings
given occur in a string. The regular expression should match _only_
strings containing one the sub-strings described. Do not worry about
word boundaries unless explicitly mentioned. When your expression
works, see if you can make it any smaller.

 1. “car” and “cat”
 2. “pop” and “prop”
 3. “ferret”, “ferry”, and “ferrari”
 4. Any word _ending_ in “ious”
 5. A whitespace character followed by a dot, comma, colon, or semicolon
 6. A word longer than 6 letters
 7. A word without the letter “e”

Refer back to the table in the chapter summary to quickly look
something up. Test each solution out with a few test strings.

ifdef::html_target[]
[source,javascript]
----
// Fill in the regular expressions

verify(/.../,
       ["my car", "bad cats"],
       ["camper", "high art"]);

verify(/.../,
       ["pop culture", "mad props"],
       ["plop"]);

verify(/.../,
       ["ferret", "ferry", "ferrari"],
       ["ferrum", "transfer A"]);

verify(/.../,
       ["how delicious", "spacious room"],
       ["ruinous", "consciousness"]);

verify(/.../,
       ["bad punctuation ."],
       ["escape the dot"]);

verify(/.../,
       ["hottentottententen"],
       ["no", "hotten totten tenten"]);

verify(/.../,
       ["red platypus", "wobbling nest"],
       ["earth bed", "learning ape"]);


function verify(regexp, yes, no) {
  // Ignore unfinished exercises
  if (regexp.source == "...") return;
  yes.forEach(function(s) {
    if (!regexp.test(s))
      console.log("Failure to match '" + s + "'");
  });
  no.forEach(function(s) {
    if (regexp.test(s))
      console.log("Unexpected match for '" + s + "'");
  });
}
----
endif::html_target[]

=== Quoting style ===

Imagine you have written a text, and used single quotation marks
throughout. Now you want to replace all those that actually quote a
piece of text with double quotes, but *not* the ones used in
contractions like `"aren't"`.

Think of a pattern that distinguishes these two kind of quote usage
and craft a call to the `replace` method that does the proper
replacement.

ifdef::html_target[]
// test: no

[source,javascript]
----
var text = "'I'm the cook,' he said, 'it's my job.'";
// Change this call.
console.log(text.replace(/A/g, "B"));
// → "I'm the cook," he said, "it's my job."
----
endif::html_target[]

!!solution!!

The most obvious solution is to only replace quotes with a non-word
character on at least one side. Something like `/\W'|'\W/`. But you
also have to take the start and end of the line into account.

In addition you must ensure that the replacement also includes the
characters that were matched by the `\W` pattern, so that those are
not dropped. This can be done by wrapping them in parentheses, and
including their groups in the replacement string (`$1`, `$2`). Groups
that are not matched will be replaced by nothing.

!!solution!!

=== Numbers again ===

Series of digits can be matched by the simple regular expression
`/\d+/`.

Write an expression that matches (only) JavaScript-style numbers. That
means it must support an optional minus _or_ plus sign in front of the
number, the decimal dot, and exponent notation—`5e-3` or `1E10`—with again an
optional sign in front of the exponent.

ifdef::html_target[]
// test: no

[source,javascript]
----
// Fill in this regular expression.
var number = /^...$/;

// Tests:
["1", "-1", "+15", "1.55", ".5", "5.", "1.3e2", "1E-4",
 "1e+12"].forEach(function(s) {
  if (!number.test(s))
    console.log("Failed to match '" + s + "'");
});
["1a", "+-1", "1.2.3", "1+1", "1e4.5", ".5.", "1f5",
 "."].forEach(function(s) {
  if (number.test(s))
    console.log("Incorrectly accepted '" + s + "'");
});
----
endif::html_target[]

!!solution!!

First, do not forget the backslash in front of the dot.

Matching the optional sign in front of the number, as well as in front
of the exponent, can be done with `[+\-]?` or `(+|-|)` (plus, minus,
or nothing).

The more complicated part of the exercise is probably the problem of
matching both `"5."` and `".5"` without also matching `"."`. For this,
a good solution is to use the ‘|’ operator to separate the two cases
out—either one or more digits optionally followed by a dot and zero or
more digits, _or_ a dot followed by one or more digits.

Finally, to make the “e” case-insensitive, either add an “i” option to
the regular expression, or use `[eE]`.

!!solution!!