hocking.Rnw

\newcommand{\sectiontidyr}{Comparisons with other functions for data frames}
\newcommand{\sectiontrackDb}{Capturing all matches from a multi-line text file}
\newcommand{\sectiontimings}{Comparing computation times of R regex packages}
\newcommand{\sectiondf}{Creating new columns from character columns in a data frame}
\newcommand{\sectionrex}{Comparing \pkg{namedCapture} variable argument syntax with \pkg{rex}}
\newcommand{\sectioncomparisons}{Comparisons with other R packages}

\title{Comparing \pkg{namedCapture} with other R packages for 
  regular expressions}

\author{by Toby Dylan Hocking}

\maketitle

\abstract{Regular expressions are powerful tools for manipulating
  non-tabular text data. For many tasks (visualization, machine
  learning, etc), tables of numbers must be extracted from such data
  before processing by other R functions. We present the R package
  \pkg{namedCapture}, which facilitates such tasks by providing a new
  user-friendly syntax for defining regular expressions in R code. We
  begin by describing the history of regular expressions and their
  usage in R. We then describe the new features of the namedCapture
  package, and provide detailed comparisons with related R packages
  (\pkg{rex}, \pkg{stringr}, \pkg{stringi}, \pkg{tidyr},
  \pkg{rematch2}, \pkg{re2r}).}

\section{Introduction}

Today regular expression libraries are powerful and widespread tools
for text processing. A regular expression \dfn{pattern} is
typically a character string that defines a set of possible
\dfn{matches} in some other \dfn{subject} strings. For example
the pattern \code{o+} matches one or more lower-case o characters; it
would match the last two characters in the subject \code{foo}, and it
would not match in the subject \code{bar}. 

The focus of this article is regular expressions with capture groups,
which are used to extract subject substrings. Capture groups are
typically defined using parentheses. For example, the pattern
\code{[0-9]+} matches one or more digits (e.g.\ \code{123} but not
\code{abc}), and the pattern \code{[0-9]+-[0-9]+} matches a range of
integers (e.g.\ \code{9-5}). The pattern \code{([0-9]+)-([0-9]+)} will
perform matching identically, but provides access by number/index to
the strings matched by the capturing sub-patterns enclosed in
parentheses (group 1 matches \code{9}, group 2 matches \code{5}). The
pattern \code{(?P<start>[0-9]+)-(?P<end>[0-9]+)} further provides access
by name to the captured sub-strings (\code{start} group matches
\code{9}, \code{end} group matches \code{5}). In R named capture
groups are useful in order to create more readable regular expressions
(names document the purpose of each sub-pattern), and to create more
readable \R\ code (it is easier to understand the intent of named references than
numbered references).

In this article our original contribution is the \R\ package
\CRANpkg{namedCapture} which provides several new features for named capture
regular expressions. The main new ideas are (1) group-specific type
conversion functions, (2) a user-friendly syntax for defining group
names with \R\ argument names, and (3) named output based on subject names and the
\code{name} capture group. 

The organization of this article is as follows. The rest of this
introduction provides a brief history of regular expressions and their
usage in \R, then gives an overview of current \R\ packages for
regular expressions. The second section describes the proposed
functions of the \pkg{namedCapture} package. The third section
provides detailed comparisons with other \R\ packages, in terms of
syntax and computation times. The article concludes with a summary and
discussion.

\subsection{Origin of regular expressions and named capture groups}

Regular expressions were first proposed in a theoretical paper
by \citet{Kleene56}. Among the first uses of a regular expression in
computers was for searching in a text editor \citep{Thompson68} and
lexical processing of source code \citep{Johnson68}. 

A capture group in a regular expression is used to extract text that
matches a sub-pattern. In 1974, Thompson wrote the \texttt{grep}
command line program, which was among the first to support capture
groups \citep{Friedl2002}. In that program, backslash-escaped
parentheses \verb|\(\)| were used to open and close each capture
group, which could then be referenced by number (\verb|\1| for the
first capture group, etc).

The idea for named capture groups seems to have originated in 1994
with the contributions of Tracy Tims to Python 1.0.0, which used the
\verb|\(<labelname>...\)| syntax
\citep{Python-1.5.2-Misc-HISTORY}. Python 1.5 introduced the
\verb|(?P<labelname>...)| syntax for name capture groups
\citep{python-1.5-Doc-libre.tex}; the P was used to indicate that the
syntax was a Python extension to the standard.

Perl-Compatible Regular Expressions (PCRE) is a C library that is now
widely used in free/open-source software tools such as Python and R.
PCRE introduced support for named capture in 2003, based on the Python
syntax \citep{pcre1-changelog.txt}. Starting in 2006, it supported the
\verb|(?<labelname>...)| syntax without a P, and the
\verb|(?'labelname'...)| syntax with single quotes, to be consistent
with Perl and .NET \citep{pcre1-changelog.txt}.

In the R NEWS files, the first mention of regular expression support
was in 1997 with R-0.60, ``Regular expression matching is now done
with system versions of the regexp library''
\citep{R.NEWS.0}. Starting with R-0.99.0, ``R now compiles in the GNU
version of regex'' \citep{R.NEWS.0}. PCRE was first included in R
version 1.6.0 in 2002 \citep{R.NEWS.1.txt}. R-2.10 in 2009 was the
first version to deprecate basic regular expressions,
\code{extended=FALSE}, which are no longer supported
\citep{R.NEWS.2}. TRE is another C library for regular expressions
that was included in R starting in R-2.10 
\citep{TRE}. Although TRE supports capture groups, it does
not allow capture groups to be named. The base R functions
\code{regexpr} and \code{gregexpr} can be given the \code{perl=TRUE}
argument in order to use the PCRE library, or \code{perl=FALSE} to use
the TRE C library. Recently created packages (\CRANpkg{stringi},
\CRANpkg{re2r}) have provided R interfaces to the ICU and RE2
libraries. 

Each library has different characteristics in terms of supported regex
features and time complexity (Table~\ref{tab:regex-libraries}). The
most important feature for the purposes of this paper is ``Output
group names'' which means the C library supports specifying capture
group names in the regular expression pattern via \verb|(?<group>pattern)| or \verb|(?P<group>pattern)|, and then extracting
those names for use in R (typically as column names in the resulting
match matrix). ``Worst case linear time'' means that the match time is
linear in the length of the input string, which is only guaranteed by
the RE2 library. ``Backreferences'' can be used in patterns such as
\verb|(.)\1|, which means to match any character that appears twice in
a row. ``Atomic grouping'' or ``possessive quantifiers'' means that
only the greediest option of all possible alternatives will be
considered; an example is the pattern \verb/(?>.+)bar/ which does not
match the subject \verb|foobar| (whereas the analog without the atomic
group does). 
``Unicode properties'' means support for regular expressions such as
\verb|\p{EMOJI_Presentation}|, which only work with ICU.
``Lookaround'' means support for zero-length assertions
such as \verb|foo(?=bar)| which matches \verb|foo| only when it is
followed by \verb|bar| (but \verb|bar| is not included in the match).
``Recursion'' is useful for matching balanced parentheses, and is only
supported in PCRE; a simple recursive pattern is \verb|a(?R)?z| which
matches one or more \verb|a| followed by exactly the same number of
\verb|z| (e.g.\ \verb|aaazzz|).

The original versions of \code{regexpr} and \code{gregexpr} only
returned the position/length of the text matched by an entire regex,
not the capture groups (even though this is supported in
TRE/PCRE). The C code that uses PCRE to extract each named capture
group was accepted into R starting with version 2.14
\citep{HockingBug2011}. A lightning talk at useR 2011 showcased the
new functionality \citep{HockingUseR2011}.

\begin{table}
  \centering
  \begin{tabular}{r|cccc}
    \toprule
    C library & RE2 & PCRE & ICU & TRE \\
    \midrule
    Specify un-named group via \verb|(pattern)| & yes & yes & yes & yes \\
    Specify group names via \verb|(?<group>pattern)| & no & yes & yes & no \\
    Specify group names via \verb|(?P<group>pattern)| & yes & yes & no & no \\
    Output group names  & yes & yes & no & no\\
    Worst case linear time & yes & no & no & no \\
    Backreferences & no & yes & yes & yes \\
    Atomic groups / possessive quantifiers & no & yes & yes & no \\
    Unicode properties & no & no & yes & no \\ 
    Lookaround & no & yes & yes & no \\
    Recursion & no & yes & no & no \\
    \bottomrule
  \end{tabular}
  \caption{\label{tab:regex-libraries}
    Features of C libraries for regular expressions which can be used in R.
    }
\end{table}

\subsection{Related R packages for capturing regular expressions}

Since the introduction of named capture support in base R version
2.14, several packages have been developed which use this
functionality, and other packages have been developed which use other
C libraries (Table~\ref{tab:Clib}). Each package supports different
options for subject/pattern input, extracted text outputs, named
capture groups, and type conversion
(Table~\ref{tab:features}). In this section we give an overview of the
features of each package; in the section ``\sectioncomparisons'' we show detailed
comparisons including sample R code and outputs.

The \pkg{utils} package now includes the \code{strcapture} function, which uses the
base \code{regexec} function (also introduced in R-2.14) to extract the first
match as a data.frame with one row per subject, and one column per
capture group. It allows capture group names/types to be specified in
a prototype data.frame argument, but does not allow capture group
names in the regex pattern. PCRE is used with \code{perl=TRUE}
and TRE is used with \code{perl=FALSE}.
 
The \CRANpkg{rematch2} package provides the \code{re\_match} function which
extracts the first match using the base \code{regexpr} function
\citep{rematch2}. It also provides \code{bind\_re\_match} 
for matching data.frame columns, and \code{re\_match\_all} 
which extracts all matches using the base \code{gregexpr} function. 
All functions output a data.frame with one row
for each subject (for all matches a list column is used). PCRE is used
with \code{perl=TRUE} and TRE is used with \code{perl=FALSE}. Although
TRE supports capture groups (and can be used via the base R \code{regexec}
function), capture groups are not supported in rematch2 with
\code{perl=FALSE} (because it uses the base \code{regexpr}/\code{gregexpr} functions
which do not return group info for TRE). Named capture groups are
supported in rematch2 with \code{perl=TRUE}.

The \pkg{stringi} package provides the \code{stri\_match} and
\code{stri\_match\_all} functions, 
which have strong unicode support due to the underlying ICU C library
\citep{stringi}. The \CRANpkg{stringr} package provides the \code{str\_match} and
\code{str\_match\_all} functions, which simply call the analogous
functions from \pkg{stringi}. 
In ICU regular expressions, named groups are supported for use 
in backreferences since version 55
\citep{ICU-release-notes-55, ICU-ticket-named-capture}. 
However, the ICU library does not report group
names to R, so groups must be extracted by number in R. 
The \code{stri\_match}
function returns a character matrix with one row for each subject and
one column for each capture group. The \code{stri\_match\_all} function
returns a list with one element for each subject; each element is a
data frame with one row for each match, and one column for each
capture group.

The \pkg{re2r} package provides the \code{re2\_match} and
\code{re2\_match\_all} functions, which use the RE2 C++ library
\citep{re2r}. The outputs of these functions are consistent with the
\pkg{stringi}/\pkg{stringr} packages. The input regex pattern may be
specified as a character string or as a pre-compiled regex object
(which results in faster matching if the regex is used with several
calls to matching functions). Unlike the other regex libraries, the RE2
library guarantees linear time complexity, which is useful to avoid
denial-of-service attacks from malicious patterns (see
Section~``\sectiontimings'').

The \CRANpkg{rex} package provides the \code{re\_matches} function which supports
named capture groups, and always uses PCRE \citep{rex}. By default it
returns the first match (using the base \code{regexpr} function), as a
data.frame with one row for each subject, and one column for each
capture group. If the \code{global=TRUE} argument is given,
\code{gregexpr} is used to return all matches as a list of
data.frames. A unique feature of the \pkg{rex} package is a set of functions
for defining a regular expression in R code, which is then converted
to a standard PCRE regex pattern string (for a detailed comparison
with the proposed syntax of the \pkg{namedCapture} package, see
Section~``\sectionrex'').

The \CRANpkg{tidyr} package provides the \code{extract} function which uses the
ICU library, so does not support regex patterns with named capture
groups \citep{tidyr}. The subject is specified via the first two
arguments: (1) a data.frame, and (2) a column name. The pattern is
specified via the second two arguments: (3) a character vector for the
capture group names, and (4) the regex pattern string (it is an error
if the number of capture group names does not match the number of un-named
capture groups in the regex pattern). The pattern is used to find the
first match in each subject. The return value is a data.frame with the
same number of rows as the input, but without the subject column, and
with an additional column for each capture group.

\begin{table}
  \centering
\begin{tabular}{llll}
  \toprule
Package      & First match              & All matches             & C library  \\
\midrule
  \pkg{namedCapture} & \code{*\_match\_variable}          & \code{str\_match\_all\_variable}     & PCRE/RE2\\
 \pkg{base}         & \code{regexpr}                  & \code{gregexpr}                & PCRE/TRE \\
  \pkg{utils}        & \code{strcapture}               & NA                      & PCRE/TRE \\
  \pkg{rematch2}     & \code{re\_match}, \code{bind\_re\_match}   & \code{re\_match\_all}            & PCRE/TRE\\
  \pkg{rex}          & \code{re\_matches(global=FALSE)} & \code{re\_matches(global=TRUE)} & PCRE\\
  \pkg{stringr}      & \code{str\_match}                & \code{str\_match\_all}           & ICU\\
  \pkg{stringi}      & \code{stri\_match}               & \code{stri\_match\_all}          & ICU\\
  \pkg{tidyr}        & \code{extract}                  & NA                      & ICU\\
  \pkg{re2r}         & \code{re2\_match}                & \code{re2\_match\_all}           & RE2\\
  \bottomrule
\end{tabular}
  \caption{R packages that provide functions for extracting first/all regex matches, and C library used.}
  \label{tab:Clib}
\end{table}


\begin{table}
  \centering
\begin{tabular}{llllll}
  \toprule
Package/function & subject & pattern      & outputs     & named & types \\
\midrule
\pkg{namedCapture} & chr/df   & chr/verbose      & mat/list/df       & yes   & any   \\
\pkg{base} & chr     & chr          & mat/list    & yes   & no    \\
\code{utils::strcapture} & chr     & chr          & df          & no    & some  \\
\pkg{rematch2} & chr/df     & chr          & df      & yes   & no    \\
\pkg{rex} & chr     & chr/verbose      & df/list          & yes   & no    \\
\pkg{stringr} & chr     & chr          & mat/list    & no    & no    \\
\pkg{stringi} & chr     & chr          & mat/list    & no    & no    \\
\code{tidyr::extract} & df   & chr          & df       & no    & some  \\
\pkg{re2r} & chr     & chr/compiled & df/list     & yes   & no    \\
  \bottomrule
\end{tabular}
\caption{R packages provide different options for subject/pattern input, extracted text outputs, named capture groups output to R, and type conversion. Abbreviations: chr=character vector, df=data.frame, mat=character matrix, verbose=regex defined in R code which is translated to a character string, compiled=regex string may be compiled and saved to an R object for later use.}
  \label{tab:features}
\end{table}


\section{The \pkg{namedCapture} package}

The \pkg{namedCapture} package provides functions for extracting
numeric data tables from non-tabular text data using named capture
regular expressions. By default, \pkg{namedCapture} uses the RE2 C
library if the \pkg{re2r} package is available, and PCRE otherwise
(via the base \code{regexpr} and \code{gregexpr} functions). RE2 is
preferred because it is guaranteed to find a match in linear time (see
Section~``\sectiontimings''). However, PCRE supports some regex features
(e.g.\ backreferences) that RE2 does not. To tell
\pkg{namedCapture} to use PCRE rather than RE2,
\code{options(namedCapture.engine="PCRE")} can be specified. For
patterns that are supported by both engines, \pkg{namedCapture}
functions return the resulting match in the standard output format
described below.

The main design features of the namedCapture package are
inspired by the base R system, which provides good support for
naming objects, and referring to objects by name. In particular, the namedCapture package supports 
\begin{itemize}
\item Standard syntax for specifying capture groups with names in a
  regular expression string, and stopping with an informative error if
  there are un-named capture groups.
\item A new/alternative syntax for specifying capture group names via
  named arguments in R code.
\item Output with rownames or list names taken from subject names.
\item Output with rownames taken from the \code{name} capture group.
\item Specifying a type conversion function for each named capture
  group.
\item Saving sub-patterns to R variables, and re-using them multiple
  times in one or several patterns in order to avoid repetition.
\end{itemize}

The main functions provided by the \pkg{namedCapture} package are summarized
in Table~\ref{tab:functions}. We begin by introducing the \code{*\_named} functions, which take three arguments.

\begin{table}
  \centering \begin{tabular}{llll}
               \toprule
  First match & All matches &  Arguments \\
               \midrule
  \code{str\_match\_named} & \code{str\_match\_all\_named} & chr subject, chr pattern, functions \\
  \code{str\_match\_variable}  & \code{str\_match\_all\_variable} & chr subject, chr/list/function,  ... \\
  \code{df\_match\_variable} & NA & df subject,  chr/list/function, ...\\
\bottomrule
  \end{tabular}
  \caption{Functions of the
  \pkg{namedCapture} package. The first argument of each function specifies
  the subject, as either a character vector (for \texttt{str\_*})
  functions, or a data.frame
  (for \texttt{df\_match\_variable}). The \texttt{*\_named} functions
  require three arguments, and are mostly for internal use; the \texttt{*\_variable} functions
  take a variable number of arguments and are the recommended functions to use.}  \label{tab:functions}
\end{table}

\subsection{Three argument syntax: \code{str\_match\_named} and \code{str\_match\_all\_named}}

The most basic functions of the \pkg{namedCapture} package
are \code{str\_match\_named} and \code{str\_match\_all\_named}, which accept exactly three arguments:
\begin{itemize}
\item subject: a character vector from which we want to extract
  tabular data.
\item pattern: the (character scalar) regular expression with named
  capture groups used for extraction.
\item fun.list: a list with names that correspond to capture groups,
  and values are functions used to convert the extracted character
  data to other (typically numeric) types.
\end{itemize}
Since introduction of the variable argument syntax (explained later in this section), 
these functions are mostly for internal use. 
Here we give an example of their usage, 
because it is similar to other R regex packages 
which some readers are probably already familiar with.
Consider subjects containing genomic positions:

<<subject>>=

chr.pos.subject <- c("chr10:213,054,000-213,055,000", "chrM:111,000", 
  "this will not match", NA, "chr1:110-111 chr2:220-222") 

@

These subjects consist of a chromosome name string, a colon, a start
position, and optionally a dash and and end position. The following
pattern is used to extract those data:

<<chrPosPattern>>=

chr.pos.pattern <- paste0(
  "(?P<chrom>chr.*?)",
  ":",
  "(?P<chromStart>[0-9,]+)",
  "(?:",
    "-",
    "(?P<chromEnd>[0-9,]+)",
  ")?")

@

The pattern above is defined using \code{paste0}, writing each named capture
group on a separate line, which increases readability of the
pattern. Note that an optional non-capturing group begins with
\verb|(?:| and ends with \verb|)?|.
In the code below, we use the \code{str\_match\_named} function on the
previously defined subject and pattern:

<<chrPosNoTypes>>=

(match.mat <- namedCapture::str_match_named(
  chr.pos.subject, chr.pos.pattern))

@

When the third argument is omitted, the return value a character
matrix with one row for each subject and one column for each capture
group. Column names are taken from the group names that were specified
in the regular expression pattern. Missing values indicate missing subjects or
no match. The empty string is used for optional groups which are not
used in the match (e.g.\ chromEnd group/column for second
subject). This output format is similar to the output of
\code{stringi::stri\_match} and \code{stringr::str\_match}; these
other functions also report a column for the entire match, whereas
\code{namedCapture::str\_match\_named} only reports a column for each
named capture group.

However we often want to extract numeric data; in this case we want to
convert chromStart/End to integers. You can do that by supplying a
named list of conversion functions as the third argument. Each
function should take exactly one argument, a character vector (data in
the matched column/group), and return a vector of the same size. The
code below specifies the \code{int.from.digits} function for both chromStart
and chromEnd:

<<intFromDigits>>=

int.from.digits <- function(captured.text)as.integer(gsub("[^0-9]", "", captured.text))
conversion.list <- list(chromStart = int.from.digits, chromEnd = int.from.digits)
match.df <- namedCapture::str_match_named(
  chr.pos.subject, chr.pos.pattern, conversion.list)
str(match.df)

@

Note that a data.frame is returned when the third argument is
specified, in order to handle non-character data types returned by the
conversion functions.

In the examples above the last subject has two possible
matches, but only the first is returned by \code{str\_match\_named}. Use
\code{str\_match\_all\_named} to get all matches in each subject (not just the
first match).

<<allChrPos>>=

namedCapture::str_match_all_named(
  chr.pos.subject, chr.pos.pattern, conversion.list)

@

As shown above, the result is a list with one element for
each subject. Each list element is a data.frame with one row for each
match.

\subsection{Named output for named subjects}

If the subject is named, its names will be used to name the output
(rownames or list names).

<<namedSubject>>=

named.subject <- c(ten = "chr10:213,054,000-213,055,000", 
  M = "chrM:111,000", two = "chr1:110-111 chr2:220-222")
namedCapture::str_match_named(
  named.subject, chr.pos.pattern, conversion.list)
namedCapture::str_match_all_named(
  named.subject, chr.pos.pattern, conversion.list)

@

This feature makes it easy to select particular subjects/matches by
name. 

\subsection{The \code{name} group specifies row names of output}

If the pattern specifies the \code{name} group, then it will be used
for the rownames of the output, and it will not be included as a
column. However if the subject has names, and the \code{name} group is
specified, then to avoid losing information the subject names are used
to name the output (and the \code{name} column is included in the
output).

<<namedSubjectPattern>>=

name.pattern <- paste0(
  "(?P<name>chr.*?)",
  ":",
  "(?P<chromStart>[0-9,]+)",
  "(?:",
    "-",
    "(?P<chromEnd>[0-9,]+)",
  ")?")
namedCapture::str_match_named(
  named.subject, name.pattern, conversion.list)
namedCapture::str_match_all_named(
  named.subject, name.pattern, conversion.list)

@

\subsection{Readable and efficient variable argument syntax used in \code{str\_match\_variable}}

In this section we introduce the variable argument syntax used in the
\code{*\_variable} functions, which is the recommended way to to use \pkg{namedCapture}. 
This new syntax is both readable and
efficient, because it is motivated by the desire to avoid
repetitive/boilerplate code. In the previous sections we defined the
pattern using the \code{paste0} boilerplate, which is used to break the
pattern over several lines for clarity. We begin by introducing
\code{str\_match\_variable}, which extracts the first match from each
subject. Using the variable argument syntax, we can omit \code{paste0}, and
simply supply the pattern strings to \code{str\_match\_variable}
directly,

<<strMatchNamed>>=

namedCapture::str_match_variable(
  named.subject, 
  "(?P<chrom>chr.*?)",
  ":",
  "(?P<chromStart>[0-9,]+)",
  "(?:",
    "-",
    "(?P<chromEnd>[0-9,]+)",
  ")?")

@

The variable argument syntax allows further simplification by removing the named capture groups from the
strings, and adding names to the corresponding arguments. For
\code{name1 = "pattern1"}, namedCapture internally generates/uses the regex
\code{(?P<name1>pattern1)}.

<<namedArgs>>=

namedCapture::str_match_variable(
  named.subject, 
  chrom = "chr.*?",
  ":",
  chromStart = "[0-9,]+",
  "(?:",
    "-",
    chromEnd = "[0-9,]+",
  ")?")

@

We can also provide a type conversion function on the same line as a named group:

<<inlineconversion>>=

namedCapture::str_match_variable(
  named.subject, 
  chrom = "chr.*?",
  ":",
  chromStart = "[0-9,]+", int.from.digits,
  "(?:",
    "-",
    chromEnd = "[0-9,]+", int.from.digits,
  ")?")

@

Note the repetition in the chromStart/End lines --- the same pattern
and type conversion function is used for each group. This repetition
can be avoided by creating and using a sub-pattern list variable,

<<subPatternList>>=

int.pattern <- list("[0-9,]+", int.from.digits)
namedCapture::str_match_variable(
  named.subject, 
  chrom = "chr.*?",
  ":",
  chromStart = int.pattern,
  "(?:",
    "-",
    chromEnd = int.pattern,
  ")?")

@

Finally, the non-capturing group can be replaced by an un-named list:

<<nonCapturingList>>=

namedCapture::str_match_variable(
  named.subject, 
  chrom = "chr.*?",
  ":",
  chromStart = int.pattern,
  list(
    "-",
    chromEnd = int.pattern
  ), "?")

@

In summary, the \code{str\_match\_variable} function takes a variable number of arguments, and allows for a shorter, less repetitive, and thus more user-friendly syntax:
\begin{itemize}
\item The first argument is the subject character vector.
\item The other arguments specify the pattern, via character strings,
  functions, and/or lists.
\item If a pattern (character/list) is named, we use the argument name in R for the capture
  group name in the regex.
\item Each function is used to convert the text extracted by the previous
  named pattern argument. (type conversion can only be used with named R arguments, NOT with explicitly specified named groups in regex strings)
\item R sub-pattern variables
  may be used to avoid repetition in the definition of the pattern and type conversion functions.
\item Each list generates a group in the regex (named list = named capture group, un-named list = non-capturing group).
\item All patterns are pasted together in the order that they appear in
  the argument list.
\end{itemize}

\subsection{\sectiontrackDb}

\label{sec:trackDb}

The variable argument syntax can also be used with
\code{str\_match\_all\_variable}, which is for the common case of extracting
each match from a multi-line text file. In this section we demonstrate
how to use \code{str\_match\_all\_variable} to extract data.frames from a
non-tabular text file.

<<trackDb>>=

trackDb.txt.gz <- system.file(
  "extdata", "trackDb.txt.gz", package = "namedCapture")
trackDb.lines <- readLines(trackDb.txt.gz)

@

Some representative lines from that file are shown below.

<<catTrackDB>>=

show.width <- 55
substr(trackDb.lines[78:107], 1, show.width)

@

Each block of text begins with \code{track} and includes several lines of
data before the block ends with two consecutive newlines. That pattern
is coded below:

<<fieldsDF>>=

fields.mat <- namedCapture::str_match_all_variable(
  trackDb.lines,
  "track ",
  name = "\\S+",
  fields = "(?:\n[^\n]+)*",
  "\n")
head(substr(fields.mat, 1, show.width))

@

% TODO maybe delete this part, and only include the last part which
% creates trackName sampleID etc columns?

Note that this function assumes that its subject is a character vector
with one element for each line in a file. The elements are pasted
together using newline as a separator, and the regex is used to find
all matches in the resulting multi-line string. The code above creates
a data frame with one row for each track block, with rownames given by
the track line (because of the \code{name} capture group), and one
\code{fields} column which is a string with the rest of the data in that
block.

Each block has a variable number of lines/fields. Each line starts
with a field name, followed by a space, followed by the field
value. That regex is coded below:

<<fieldsList>>=

fields.list <- namedCapture::str_match_all_named(
  fields.mat[, "fields"], paste0(
    "\\s+",
    "(?P<name>.*?)",
    " ",
    "(?P<value>[^\n]+)"))
substr(fields.list$bcell_McGill0091Coverage, 1, show.width)

@

The result is a list of data frames. 
There is a list element for each block, named by track. Each list
element is a data frame with one row per field defined in that
block (rownames are field names). The names/rownames make it easy
to write R code that selects individual elements by name.

In the example above we extracted all fields from all tracks (using
two regexes, one for the track, one for the field). In the example
below we use a single regex to extract the name of each track, and split
components into separate columns. It also demonstrates how to use nested named
capture groups, via a named list which contains other named patterns.

<<trackDbMatchAll>>=

match.df <- namedCapture::str_match_all_variable(
  trackDb.lines,
  "track ",
  name = list(
    cellType = ".*?",
    "_",
    sampleName = list(
      "McGill",
      sampleID = int.pattern),
    dataType = "Coverage|Peaks",
    "|",
    "[^\n]+")) 
match.df["bcell_McGill0091Coverage", ] 

@

Exercise for the reader: modify the above in order to capture the
bigDataUrl field, and three additional columns (red, green, blue) from
the color field.

\subsection{\sectiondf}

\label{sec:df_match_variable}

We also provide \code{namedCapture::df\_match\_variable} which extracts text
from several columns of a data.frame, using a different named capture
regular expression for each column.

\begin{itemize}
\item It requires a data.frame as the first argument.
\item It takes a variable number of other arguments, all of which must be
  named. For each other argument we call \code{str\_match\_variable} on one
  column of the input data.frame.
\item Each argument name specifies a column of the data.frame which will
  be used as the subject in \code{str\_match\_variable}.
\item Each argument value specifies a pattern, in
  list/character/function variable argument syntax.
\item The return value is a data.frame with the same number of rows as the
  input, but with an additional column for each named capture
  group. New columns are named using the convention
  \code{subjectColumnName.groupName}.
\end{itemize}
This function can greatly simplify the code required to create numeric
data columns from character data columns. For example consider the
following data which was output from the SLURM sacct command line program.

<<sacctdf>>=

(sacct.df <- data.frame(
  Elapsed = c("07:04:42", "07:04:42", "07:04:49", "00:00:00", "00:00:00"),
  JobID = c("13937810_25", "13937810_25.batch", "13937810_25.extern",
    "14022192_[1-3]", "14022204_[4]"), stringsAsFactors = FALSE))

@

Say we want to filter by the total Elapsed time (which is reported as
hours:minutes:seconds), and base job id (which is the number before
the underscore in the JobID column). We begin by defining a pattern
that matches a range of integer task IDs in square brackets, and applying that
pattern to the JobID column:

<<rangePat>>=

range.pattern <- list(
  "[[]",
  task1 = int.pattern,
  list(
    "-",
    taskN = int.pattern
  ), "?",
  "[]]")
namedCapture::df_match_variable(sacct.df, JobID = range.pattern)

@ 

The result shown above is another data frame with an additional column for each
named capture group. 
Next, we define another pattern that matches either one task ID
or the previously defined range pattern:

<<taskPat>>=

task.pattern <- list(
  "_", list(
    task = int.pattern,
    "|",#either one task(above) or range(below)
    range.pattern))
namedCapture::df_match_variable(sacct.df, JobID = task.pattern)

@ 

Below, we use the previously defined patterns to match the complete
JobID column, along with the Elapsed column:

<<dfMatchVar>>=

future::plan("multiprocess")
namedCapture::df_match_variable(
  sacct.df,
  JobID = list(
    job = int.pattern,
    task.pattern,
    list(
      "[.]",
      type = ".*"
    ), "?"),
  Elapsed = list(
    hours = int.pattern,
    ":",
    minutes = int.pattern,
    ":",
    seconds = int.pattern))

@

The code above specifies two named arguments to
\code{df\_match\_variable}. Each named argument specifies a column from
which tabular data are extracted using the corresponding pattern. The
final result is a data frame with an additional column for each named
capture group. 

\section{\sectioncomparisons}
\label{sec:comparisons}

In this section we compare the proposed functions in the \pkg{namedCapture}
package with similar functions in other R packages for regular expressions.

\subsection{\sectionrex}
\label{sec:rex}
In this section we compare \pkg{namedCapture} verbose variable argument
syntax with the similar \pkg{rex} package. We have adapted the log
parsing example from the \pkg{rex} package:

<<logsubject>>=

log.subject <- 'gate3.fmr.com - - [05/Jul/1995:13:51:39 -0400] "GET /shuttle/ 
curly02.slip.yorku.ca - - [10/Jul/1995:23:11:49 -0400] "GET /sts-70/sts-small.gif
boson.epita.fr - - [15/Jul/1995:11:27:49 -0400] "GET /movies/sts-71-mir-dock.MPG
134.153.50.9 - - [13/Jul/1995:11:02:50 -0400] "GET /icons/text.xbm'
log.lines <- strsplit(log.subject, split = "\n")[[1]]

@ 

The goal is to extract the time and filetype for
each log line. The code below uses the \code{rex} function to define a
pattern for matching the filetype: 

<<rex>>=

library(rex)
library(dplyr)
(rex.filetype.pattern <- rex(
  non_spaces, ".",
  capture(name = 'filetype',
          none_of(space, ".", "?", double_quote) %>% one_or_more())))

@ 

Note that rex defines R functions (e.g.\ \code{capture},
\code{one\_or\_more}) and constants (\code{non\_spaces},
\code{double\_quote}) which are translated to standard regular expression
syntax via the \code{rex} function. These regex objects can be used as
sub-patterns in other calls to \code{rex}, as in the code below:

<<rexFull>>=

rex.pattern <- rex(
  "[",
  capture(name = "time", none_of("]") %>% zero_or_more()),
  "]",
  space, double_quote, "GET", space,
  maybe(rex.filetype.pattern))

@ 

Finally, the pattern is used with \code{re\_matches} in order to
extract a data table, and the \code{mutate} function is used for type
conversion:

<<reMatches>>=

re_matches(log.lines, rex.pattern) %>% mutate(
  filetype = tolower(filetype),
  time = as.POSIXct(time, format = "%d/%b/%Y:%H:%M:%S %z"))

@


Using the \pkg{namedCapture} package we begin by defining an analogous
filetype pattern as a list containing literal regex strings and a type
conversion function:

<<lognamedcapture>>=

namedCapture.filetype.pattern <- list(
  "[^[:space:]]+[.]", 
  filetype = '[^[:space:].?"]+', tolower)

@ 

We can then use that as a sub-pattern in a call to
\code{str\_match\_variable}, which results in a data table with columns
generated via the specified type conversion functions:

<<s>>=

namedCapture::str_match_variable(
  log.lines,
  "\\[",
  time = "[^]]*", function(x)as.POSIXct(x, format = "%d/%b/%Y:%H:%M:%S %z"),
  "\\]",
  ' "GET ',
  namedCapture.filetype.pattern, "?")

@ 

Overall both \pkg{rex} and \pkg{namedCapture} provide good
support for defining regular expresions using a verbose, readable, and
thus user-friendly syntax. However there are two major differences:
\begin{itemize}
\item \pkg{namedCapture} assumes the user knows regular
  expressions and can write them as R string literals; \pkg{rex}
  assumes the user knows its functions, which generate regex
  strings. For example the capture group time,
  \verb|none_of("]") %>% zero_or_more()| in rex gets translated to the
  regex string \verb|[^]]*|. Thus \pkg{rex} code is a bit more verbose than
  \pkg{namedCapture}.
\item In \pkg{namedCapture} type conversion functions can be specified on the
  same line as the capture group name/pattern, whereas in \pkg{rex} type conversions are
  specified as a post-processing step on the result of \code{re\_matches}. 
\end{itemize}

\subsection{\sectiontidyr}
\label{sec:tidyr}

The \pkg{tidyr} and \pkg{rematch2} packages provide functionality similar to
\code{namedCapture::df\_match\_variable}, which was introduced in
Section~``\sectiondf.'' Below we show how
\code{tidyr::extract} can be used to compute a similar result as in
that previous section, using the same data from the SLURM sacct
command line program. We begin by defining a pattern which matches a
range of integers in square brackets:

<<tidyr.range>>=

tidyr.range.pattern <- "\\[([0-9]+)(?:-([0-9]+))?\\]"
tidyr::extract(
  sacct.df, "JobID", c("task1", "taskN"), 
  tidyr.range.pattern, remove = FALSE)

@ 

Note the pattern string includes un-named capture groups, because
named capture is not supported. Names must therefore be specified in
the third argument of \code{extract}. Next, we define a pattern which
matches either a single task ID, or a range in square brackets:

<<tidyr.task>>=

tidyr.task.pattern <- paste0("_(?:([0-9]+)|", tidyr.range.pattern, ")")
tidyr::extract(sacct.df, "JobID", c("task", "task1", "taskN"), 
  tidyr.task.pattern, remove = FALSE)

@ 

In the code below we define a pattern that matches the entire job string:

<<tidyr.job>>=

tidyr.job.pattern <- paste0("([0-9]+)", tidyr.task.pattern, "(?:[.](.*))?")
(job.df <- tidyr::extract(sacct.df, "JobID", 
  c("job", "task", "task1", "taskN", "type"), tidyr.job.pattern))

@ 

Finally, we use another pattern to extract the components of the
elapsed time. Note that \code{convert = TRUE} means to use
\code{utils::type.convert} on the result of each extracted group.

<<tidyr2>>=

tidyr::extract(job.df, "Elapsed", c("hours", "minutes", "seconds"),
  "([0-9]+):([0-9]+):([0-9]+)", convert = TRUE)

@

Below we show the same computation using
\code{rematch2::bind\_re\_match}, which supports named capture. Note
that we use \code{paste0} to define a regular expression with each
named capture group on a separate line:

<<bind>>=

rematch2.range.pattern <- paste0(
  "\\[",
  "(?P<task1>[0-9]+)",
  "(?:-",
  "(?P<taskN>[0-9]+)",
  ")?\\]")
rematch2::bind_re_match(sacct.df, JobID, rematch2.range.pattern)

@ 

Above we extract a range of task IDs in square brackets, and below we
optionally match a single task ID:

<<bindtask>>=

rematch2.task.pattern <- paste0(
  "_(?:",
  "(?P<task>[0-9]+)",
  "|", rematch2.range.pattern, ")")
rematch2::bind_re_match(sacct.df, JobID, rematch2.task.pattern)

@ 

Below we additionally match the job ID and job type:

<<bindjob>>=

rematch2.job.pattern <- paste0(
  "(?P<job>[0-9]+)", 
  rematch2.task.pattern, 
  "(?:[.]",
  "(?P<type>.*)",
  ")?")
(rematch2.job.df <- rematch2::bind_re_match(
  sacct.df, JobID, rematch2.job.pattern))

@ 

Finally we call the function on the result from above with a new
pattern for another column:

<<bindall>>=

transform(rematch2::bind_re_match(
  rematch2.job.df, Elapsed, 
  "(?P<hours>[0-9]+):(?P<minutes>[0-9]+):(?P<seconds>[0-9]+)"),
  hours.int = as.integer(hours),
  minutes.int = as.integer(minutes),
  seconds.int = as.integer(seconds))

@ 

Overall our comparison demonstrates that \code{tidyr::extract} and
\code{rematch2::bind\_re\_match} function similarly to
\code{namedCapture::df\_match\_variable}, with the following
differences:
\begin{itemize}
\item Because \code{tidyr::extract} uses the ICU C library, which does
  not support named capture regular expressions, it requires
  specifying the group names in a separate argument. In contrast,
  \pkg{rematch2} supports specifying capture group names in regex
  string literals; \pkg{namedCapture} variable argument syntax
  supports specifying capture group names as R argument names on the
  same line as the corresponding sub-pattern.
\item Since \code{rematch2::bind\_re\_match} returns character
  columns, conversion to numeric types must be accomplished in a
  post-processing step using a function such as \code{transform}.
  In contrast \code{tidyr::extract(convert = TRUE)} always uses
  \code{utils::type.convert} for type conversion, and
  \code{namedCapture::df\_match\_variable} supports arbitrary
  group-specific type conversion functions, which may be specified on the
  same line as the corresponding name/pattern.
\item Because \code{tidyr::extract} and
  \code{rematch2::bind\_re\_match} operate on one column in the
  subject data frame, they must be called twice (once for the Elapsed
  column, once for the JobID column). In contrast, one call to
  \code{namedCapture::df\_match\_variable} can be used to extract data
  from multiple columns in the subject data frame.
\end{itemize}

\subsection{\sectiontimings}
\label{sec:timings}

In this section we compare the computation time of the proposed
\pkg{namedCapture} package with other R packages. For all of the
comparisons, we used the \CRANpkg{microbenchmark} package to compute
the computation times of each R package/function. We study how the
empirical computation time scales as a function of subject/pattern size. The
first three comparisons come from the real-world examples discussed
earlier in this article; the last two comparisons are pathological examples
used to show worst case time complexity.

The first example involves extracting all matches from a multi-line
text file, as discussed in Section~``\sectiontrackDb.''
Figure~\ref{fig:timings-all} shows comparisons with packages
\pkg{re2r}, \pkg{stringr}, \pkg{stringi},
\pkg{rematch2}, \pkg{rex}. We expected small differences
between the packages, on the order of constant factors. Using R-3.5.2
(left panel of Figure~\ref{fig:timings-all}), the lines for the
\pkg{rex} and \pkg{rematch2} packages have significantly larger slopes than
the other packages
(\pkg{namedCapture}, \pkg{stringr}, \pkg{stringi}, and \pkg{re2r}). This can be explained because \pkg{rex} and \pkg{rematch2} use the base \code{gregexpr} and \code{substring} functions,
which are implemented using inefficient quadratic time algorithms in
R-3.5.2. As a result of this research, this issue was reported on
the R-devel email list, and R-core member Tomas Kalibera has fixed the problem. In R-3.6.0 (right panel of Figure~\ref{fig:timings-all}), linear time algorithms are used. 

\begin{figure}
  \includegraphics[width=\textwidth]{figure-timings-all-linetype}
  \vskip -0.5cm
  \caption{\label{fig:timings-all} Computation time for finding
    all matches in a text file is plotted as a function of number of lines (median lines and quartile bands over 5 timings). Such timings
    are typical of real-world subjects/patterns. R-3.5.2 used
    quadratic time algorithms for \code{gregexpr}/\code{substring}
    (left), which were changed to linear time algorithms in R-3.6.0
    due to this research (right).}
\end{figure}

The second example involves extracting the first match from each line
of a log file, as discussed in Section~``\sectionrex.''
Figure~\ref{fig:timings-first} (left) shows comparisons with the
previously discussed packages and \code{utils:strcapture}. We expected
small differences between the packages, on the order of constant
factors. In this comparison we observed only small constant factor
differences, and linear time complexity for all packages.

The third example involves using a different regular expression to
extract data for each of two columns of a data frame, as discussed in
Section~``\sectiontidyr.'' Figure~\ref{fig:timings-first} (right)
shows a comparison with \pkg{tidyr} and \pkg{rematch2}. Again we expected small
differences between the packages, and we observed linear time
complexity for \pkg{tidyr}, \pkg{rematch2}, and \pkg{namedCapture} (using
either PCRE or RE2).

The fourth example shows the worst case time complexity, 
using a pathological regular expression of
increasing size (with backreferences) on a subject of increasing
size. 
For example with size $N=2$ we use the regex \verb|(a)?(a)?\1\1| on the
pattern \code{aa}; the match time complexity is $O(2^N)$.
Note that possessive quantifiers, \code{(a)?+},
could be used to avoid the exponential time complexity
(but possessive quantifers are only supported in PCRE and ICU, not TRE nor RE2).
Figure~\ref{fig:timings-pathological} (left) shows a comparison
between ICU, PCRE, and TRE (RE2 is not included because it does not
support backreferences). It is clear that all three libraries suffer
from exponential time complexity.
Although these timings are not typical, they illustrate
the worst case time complexity that can be achieved. Such information
should be considered along with other features
(Table~\ref{tab:regex-libraries}) when choosing a regex library. For
example, guaranteed linear time complexity is essential for avoiding
denial-of-service attacks in situations where potentially malicious
users are permitted to define the regular expression pattern.

\begin{figure}
  \includegraphics[width=\textwidth]{figure-timings-first-linetype}
  \vskip -0.5cm
  \caption{\label{fig:timings-first} Computation time for finding the first match is plotted as
    a function of subject size (median lines and quartile bands over 5
    timings). Such timings are typical for real-world subjects and patterns such as the two examples shown. }
\end{figure}

The final example involves using a pathological regular expression of
increasing size (without backreferences) on a subject of increasing
size. Figure~\ref{fig:timings-pathological} (right) shows a comparison
between the previous libraries and additionally RE2. Is is clear that
the fastest libraries are TRE and RE2, which exhibit linear time
complexity. The slowest algorithm is clearly ICU, which exhibits
exponential time complexity. 
The PCRE library is exponential up to a
certain pattern/subject size, after which it is constant, because of a
default limit PCRE imposes on backtracking. 
If other libraries allow configuring a limit on backtracking, 
such an option could be used to avoid this exponential time complexity.
Again these timings are on
synthetic data which achieve the worst case time complexity, and are
not typical of real data. Overall this comparison suggests that for
guaranteed fast matching, RE2 must be used, via the \pkg{re2r} or
\pkg{namedCapture} packages.

\section{Discussion and conclusions}

Our comparisons showed how similar operations can be performed by
\pkg{namedCapture} and other R packages (e.g.\ \pkg{tidyr} and
\pkg{rex}). Our empirical timings revealed an inefficient
implementation of the \code{substring}/\code{gregexpr} functions in
R-3.5.2, which was fixed in R-3.6.0 as a result of this
research. After applying that fix, all packages were asymptotically
linear in our empirical comparisons of time to compute matches using
typical/real-world patterns and subjects. Finally, we studied the
worst-case time complexity of matching on pathological
patterns/subjects, and showed that RE2 must be used for guaranteed
linear time complexity.

The article presented the \pkg{namedCapture} package, along with
detailed comparisons with other R packages for regular expressions.  A
unique feature of the \pkg{namedCapture} package is its compact and
readable syntax for defining regular expressions in R code. We showed
how this syntax can be used to extract data tables from a variety of
non-tabular text data. We also highlighted several other features of
the \pkg{namedCapture} package, which include support for 
arbitrary type conversion functions, named output based on subject names and the
\code{name} capture group, and two regex engines (PCRE and RE2). PCRE
can be used for backreferences (e.g.\ for matching HTML tags), but
otherwise RE2 should be preferred for guaranteed linear time
complexity. 

The ICU library may be preferred for its strong unicode support
(Table~\ref{tab:regex-libraries}), so one may wonder if it is possible
to support ICU as an engine in \pkg{namedCapture}. It is not possible,
because \pkg{namedCapture} requires the engine to support output of
capture group names,
which is not supported by ICU (Table~\ref{tab:regex-libraries}).
However ICU does support un-named capture groups,
so we have implemented support for the ICU engine
in a new package, \CRANpkg{nc}, which provides functions
that allow the user to specify output column names as R arguments
(as in the proposed variable argument syntax). Internally \pkg{nc}
generates an un-named capture group for each named R argument,
and uses the specified argument name for the corresponding output column name.
Therefore \pkg{nc} is able to provide a standard interface to three C regex libraries:
PCRE, RE2, and ICU.

We thank a reviewer for a suggestion about other choices for the
variable argument syntax for specifying type conversion functions. The
current syntax uses a named R argument to specify the capture group
name, then a character string literal to specify the capture group
pattern, then a function to specify the type conversion. Other
choices could use formulas or the \verb|:=| operator to define type
conversions.  Overall we hope that the unique features of the
\pkg{namedCapture} package will be useful and inspiring for other
package developers.

\paragraph{Reproducible research statement.} The source code for this
article can be freely downloaded from
\url{https://github.com/tdhock/namedCapture-article}


\begin{figure}
  \includegraphics[width=\textwidth]{figure-timings-pathological-linetype}
  \vskip -0.5cm
  \caption{\label{fig:timings-pathological} Computation time is
    plotted as a function of subject/pattern size (median lines and
    quartile bands over 10 timings). For $N=2$ the subject is \code{aa}
    and the pattern is shown in the facet title. Such slow timings
    only result from pathological subject/pattern combinations.}
\end{figure}

\bibliography{hocking}

\address{Toby Dylan Hocking\\
  School of Informatics, Computing, and Cyber Systems\\
  Northern Arizona University\\
  Flagstaff, Arizona\\
  USA\\
  \email{toby.hocking@nau.edu}}