hocking.tex

\newcommand{\sectiontidyr}{Comparing \code{namedCapture::df\_match\_variable} with \code{tidyr::extract}}
\newcommand{\sectiontrackDb}{Extract all matches from a multi-line text file via \code{str\_match\_all\_variable}}
\newcommand{\sectiontimings}{Comparing computation times of R regex packages}
\newcommand{\sectiondf}{\code{df\_match\_variable} extracts new columns from character columns in a data.frame}
\newcommand{\sectionrex}{Comparing \CRANpkg{namedCapture} variable argument syntax with \CRANpkg{rex}}

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

\author{by Toby Dylan Hocking}

\maketitle

\abstract{Regular expressions are powerful tools for manipulating
  non-tabular textual 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
  \CRANpkg{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
  (\CRANpkg{rex}, \CRANpkg{stringr}, \CRANpkg{stringi}, \CRANpkg{tidyr},
  \CRANpkg{rematch2}, \CRANpkg{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).

We begin by providing a brief history of regular
expressions and their usage in \R. We then provide an overview of
current R packages for regular expressions.

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

Regular expressions were first proposed on 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|(?P<labelname>...)| and \verb|(?'labelname'...)| syntax, to be
consistent with Perl and .NET \citep{pcre1-changelog.txt}.



The first regular expression support in R was provided by the TRE C
library \citep{TRE}. Although TRE supports capture groups, it does not
allow capture groups to be named. PCRE was first included in R version
1.6.0 in 2002 \citep{R.NEWS.1.txt}. 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}).
%% Although TRE and PCRE offer similar features and
%% performance for the vast majority of real-world subjects and patterns,
%% some malicious patterns can make PCRE run quite a bit slower than TRE
%% (see Section~``\sectiontimings''). 


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). I
wrote the C code that uses PCRE to extract the text matched by each
named capture group \citep{HockingBug2011}, which was accepted into R
starting with version 2.14. I presented a lightning talk at useR 2011
that showcased the new functionality \citep{HockingUseR2011}.

\begin{table}
  \centering
  \begin{tabular}{r|cccc}
    C library & RE2 & PCRE & ICU & TRE \\
    Named capture groups  & yes & yes & no & no\\
    Worst case linear time & yes & no & no & no \\
    Backreferences & no & yes & yes & yes 
  \end{tabular}
  \caption{\label{tab:regex-libraries}
    Features of C libraries for regular expressions usable 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}). 

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 the \code{re\_match\_all} function
which extracts all matches using the base \code{gregexpr} function. In
both cases the output is a tibble (a data.frame subclass) 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 \CRANpkg{stringi} package provides the \code{stri\_match} and
\code{stri\_match\_all} functions, which use the 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 \CRANpkg{stringi}. Capture groups are supported but named groups
are not, so groups must be extracted by number. 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 \CRANpkg{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
\CRANpkg{stringi}/\CRANpkg{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). Like TRE, 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 \CRANpkg{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 \CRANpkg{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}
Package      & First match              & All matches             & C library  \\
\hline
 \pkg{base}         & \code{regexpr}                  & \code{gregexpr}                & PCRE/TRE \\
  \pkg{utils}        & \code{strcapture}               & NA                      & PCRE/TRE \\
  \CRANpkg{rematch2}     & \code{re\_match}                 & \code{re\_match\_all}            & PCRE/TRE\\
  \CRANpkg{namedCapture} & \code{str\_match\_*}, \code{df\_match\_variable}          & \code{str\_match\_all\_*}     & PCRE/RE2\\
  \CRANpkg{rex}          & \code{re\_matches(global=FALSE)} & \code{re\_matches(global=TRUE)} & PCRE\\
  \CRANpkg{stringr}      & \code{str\_match}                & \code{str\_match\_all}           & ICU\\
  \CRANpkg{stringi}      & \code{stri\_match}               & \code{stri\_match\_all}          & ICU\\
  \CRANpkg{tidyr}        & \code{extract}                  & NA                      & ICU\\
  \CRANpkg{re2r}         & \code{re2\_match}                & \code{re2\_match\_all}           & RE2
\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}
Package/function & subject & pattern      & outputs     & named & types \\
\hline
\pkg{base} & chr     & chr          & mat/list    & yes   & no    \\
\code{utils::strcapture} & chr     & chr          & df          & no    & some  \\
\CRANpkg{rematch2} & chr     & chr          & tibble      & yes   & no    \\
\CRANpkg{namedCapture} & chr/df   & verbose      & mat/list/df       & yes   & any   \\
\CRANpkg{rex} & chr     & verbose      & df/list          & yes   & no    \\
\CRANpkg{stringr} & chr     & chr          & mat/list    & no    & no    \\
\CRANpkg{stringi} & chr     & chr          & mat/list    & no    & no    \\
\code{tidyr::extract} & df   & chr          & df       & no    & some  \\
\CRANpkg{re2r} & chr     & chr/compiled & df/list     & yes   & no    
\end{tabular}
\caption{R packages provide different options for subject/pattern input, extracted text outputs, named capture groups, and type conversion. Abbreviations: chr=character vector, df=data.frame, mat=character matrix. }
  \label{tab:features}
\end{table}


\section{The \CRANpkg{namedCapture} package}

The \CRANpkg{namedCapture} package provides functions for extracting
numeric data tables from non-tabular text data using named capture
regular expressions. By default, \CRANpkg{namedCapture} uses the RE2 C
library if the \CRANpkg{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
\CRANpkg{namedCapture} to use PCRE rather than RE2,
\code{options(namedCapture.engine="PCRE")} can be specified. For
patterns that are supported by both engines, \CRANpkg{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 \CRANpkg{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}
  First match & All matches &  Arguments \\
  \hline
  \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, ...
  \end{tabular}
  \caption{Functions of the
  \CRANpkg{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, whereas the \texttt{*\_variable} functions
  take a variable number of arguments.}  \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 \CRANpkg{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}

For an example, we consider subjects containing genomic positions:

\begin{Schunk}
\begin{Sinput}
> 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") 
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> chr.pos.pattern <- paste0(
+   "(?P<chrom>chr.*?)",
+   ":",
+   "(?P<chromStart>[0-9,]+)",
+   "(?:",
+     "-",
+     "(?P<chromEnd>[0-9,]+)",
+   ")?")
> 
\end{Sinput}
\end{Schunk}

The pattern above is defined using \code{paste0}, writing each named capture
group on a separate line, which increases readability of the pattern.
By default
the \code{str\_match\_named} function returns 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:

\begin{Schunk}
\begin{Sinput}
> (match.mat <- namedCapture::str_match_named(
+   chr.pos.subject, chr.pos.pattern))
\end{Sinput}
\begin{Soutput}
     chrom   chromStart    chromEnd     
[1,] "chr10" "213,054,000" "213,055,000"
[2,] "chrM"  "111,000"     ""           
[3,] NA      NA            NA           
[4,] NA      NA            NA           
[5,] "chr1"  "110"         "111"        
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}


Note that the third argument (list of conversion functions) is omitted
in the code above. In that case, the return value is a character
matrix, in which 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).

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:

\begin{Schunk}
\begin{Sinput}
> 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)
\end{Sinput}
\begin{Soutput}
'data.frame':	5 obs. of  3 variables:
 $ chrom     : chr  "chr10" "chrM" NA NA ...
 $ chromStart: int  213054000 111000 NA NA 110
 $ chromEnd  : int  213055000 NA NA NA 111
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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).

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_all_named(
+   chr.pos.subject, chr.pos.pattern, conversion.list)
\end{Sinput}
\begin{Soutput}
[[1]]
  chrom chromStart  chromEnd
1 chr10  213054000 213055000

[[2]]
  chrom chromStart chromEnd
1  chrM     111000       NA

[[3]]
data frame with 0 columns and 0 rows

[[4]]
data frame with 0 columns and 0 rows

[[5]]
  chrom chromStart chromEnd
1  chr1        110      111
2  chr2        220      222
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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).

\begin{Schunk}
\begin{Sinput}
> 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)
\end{Sinput}
\begin{Soutput}
    chrom chromStart  chromEnd
ten chr10  213054000 213055000
M    chrM     111000        NA
two  chr1        110       111
\end{Soutput}
\begin{Sinput}
> namedCapture::str_match_all_named(
+   named.subject, chr.pos.pattern, conversion.list)
\end{Sinput}
\begin{Soutput}
$ten
  chrom chromStart  chromEnd
1 chr10  213054000 213055000

$M
  chrom chromStart chromEnd
1  chrM     111000       NA

$two
  chrom chromStart chromEnd
1  chr1        110      111
2  chr2        220      222
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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).

\begin{Schunk}
\begin{Sinput}
> name.pattern <- paste0(
+   "(?P<name>chr.*?)",
+   ":",
+   "(?P<chromStart>[0-9,]+)",
+   "(?:",
+     "-",
+     "(?P<chromEnd>[0-9,]+)",
+   ")?")
> namedCapture::str_match_named(
+   named.subject, name.pattern, conversion.list)
\end{Sinput}
\begin{Soutput}
     name chromStart  chromEnd
ten chr10  213054000 213055000
M    chrM     111000        NA
two  chr1        110       111
\end{Soutput}
\begin{Sinput}
> namedCapture::str_match_all_named(
+   named.subject, name.pattern, conversion.list)
\end{Sinput}
\begin{Soutput}
$ten
      chromStart  chromEnd
chr10  213054000 213055000

$M
     chromStart chromEnd
chrM     111000       NA

$two
     chromStart chromEnd
chr1        110      111
chr2        220      222
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

\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. 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,

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_variable(
+   named.subject, 
+   "(?P<chrom>chr.*?)",
+   ":",
+   "(?P<chromStart>[0-9,]+)",
+   "(?:",
+     "-",
+     "(?P<chromEnd>[0-9,]+)",
+   ")?")
\end{Sinput}
\begin{Soutput}
    chrom   chromStart    chromEnd     
ten "chr10" "213,054,000" "213,055,000"
M   "chrM"  "111,000"     ""           
two "chr1"  "110"         "111"        
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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)}.

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_variable(
+   named.subject, 
+   chrom="chr.*?",
+   ":",
+   chromStart="[0-9,]+",
+   "(?:",
+     "-",
+     chromEnd="[0-9,]+",
+   ")?")
\end{Sinput}
\begin{Soutput}
    chrom   chromStart    chromEnd     
ten "chr10" "213,054,000" "213,055,000"
M   "chrM"  "111,000"     ""           
two "chr1"  "110"         "111"        
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_variable(
+   named.subject, 
+   chrom="chr.*?",
+   ":",
+   chromStart="[0-9,]+", int.from.digits,
+   "(?:",
+     "-",
+     chromEnd="[0-9,]+", int.from.digits,
+   ")?")
\end{Sinput}
\begin{Soutput}
    chrom chromStart  chromEnd
ten chr10  213054000 213055000
M    chrM     111000        NA
two  chr1        110       111
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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,

\begin{Schunk}
\begin{Sinput}
> int.pattern <- list("[0-9,]+", int.from.digits)
> namedCapture::str_match_variable(
+   named.subject, 
+   chrom="chr.*?",
+   ":",
+   chromStart=int.pattern,
+   "(?:",
+     "-",
+     chromEnd=int.pattern,
+   ")?")
\end{Sinput}
\begin{Soutput}
    chrom chromStart  chromEnd
ten chr10  213054000 213055000
M    chrM     111000        NA
two  chr1        110       111
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_variable(
+   named.subject, 
+   chrom="chr.*?",
+   ":",
+   chromStart=int.pattern,
+   list(
+     "-",
+     chromEnd=int.pattern
+   ), "?")
\end{Sinput}
\begin{Soutput}
    chrom chromStart  chromEnd
ten chr10  213054000 213055000
M    chrM     111000        NA
two  chr1        110       111
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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.

\begin{Schunk}
\begin{Sinput}
> trackDb.txt.gz <- system.file(
+   "extdata", "trackDb.txt.gz", package="namedCapture")
> trackDb.lines <- readLines(trackDb.txt.gz)
> 
\end{Sinput}
\end{Schunk}

Some representative lines from that file are shown below.

\begin{Schunk}
\begin{Sinput}
> cat(trackDb.lines[78:107], sep="\n")
\end{Sinput}
\begin{Soutput}
track peaks_summary
type bigBed 5
shortLabel _model_peaks_summary
longLabel Regions with a peak in at least one sample
visibility pack
itemRgb off
spectrum on
bigDataUrl http://hubs.hpc.mcgill.ca/~thocking/PeakSegFPOP-/peaks_summary.bigBed


 track bcell_McGill0091
 parent bcell
 container multiWig
 type bigWig
 shortLabel bcell_McGill0091
 longLabel bcell | McGill0091
 graphType points
 aggregate transparentOverlay
 showSubtrackColorOnUi on
 maxHeightPixels 25:12:8
 visibility full
 autoScale on

  track bcell_McGill0091Coverage
  bigDataUrl http://hubs.hpc.mcgill.ca/~thocking/PeakSegFPOP-/samples/bcell/McGill0091/coverage.bigWig
  shortLabel bcell_McGill0091Coverage
  longLabel bcell | McGill0091 | Coverage
  parent bcell_McGill0091
  type bigWig
  color 141,211,199
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> fields.mat <- namedCapture::str_match_all_variable(
+   trackDb.lines,
+   "track ",
+   name="\\S+",
+   fields="(?:\n[^\n]+)*",
+   "\n")
> head(substr(fields.mat, 1, 50))
\end{Sinput}
\begin{Soutput}
                       fields                                                 
bcell                  "\nsuperTrack on show\nshortLabel bcell\nlongLabel bce"
kidneyCancer           "\nsuperTrack on show\nshortLabel kidneyCancer\nlongLa"
kidney                 "\nsuperTrack on show\nshortLabel kidney\nlongLabel ki"
leukemiaCD19CD10BCells "\nsuperTrack on show\nshortLabel leukemiaCD19CD10BCe" 
monocyte               "\nsuperTrack on show\nshortLabel monocyte\nlongLabel "
skeletalMuscleCtrl     "\nsuperTrack on show\nshortLabel skeletalMuscleCtrl\n"
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

% 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:

\begin{Schunk}
\begin{Sinput}
> fields.list <- namedCapture::str_match_all_named(
+   fields.mat[, "fields"], paste0(
+     "\\s+",
+     "(?P<name>.*?)",
+     " ",
+     "(?P<value>[^\n]+)"))
> fields.list$bcell_McGill0091Coverage
\end{Sinput}
\begin{Soutput}
           value                                                                                      
bigDataUrl "http://hubs.hpc.mcgill.ca/~thocking/PeakSegFPOP-/samples/bcell/McGill0091/coverage.bigWig"
shortLabel "bcell_McGill0091Coverage"                                                                 
longLabel  "bcell | McGill0091 | Coverage"                                                            
parent     "bcell_McGill0091"                                                                         
type       "bigWig"                                                                                   
color      "141,211,199"                                                                              
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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.

\begin{Schunk}
\begin{Sinput}
> 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", ] 
\end{Sinput}
\begin{Soutput}
                         cellType sampleName sampleID dataType
bcell_McGill0091Coverage    bcell McGill0091       91 Coverage
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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.

\begin{Schunk}
\begin{Sinput}
> (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))
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID
1 07:04:42        13937810_25
2 07:04:42  13937810_25.batch
3 07:04:49 13937810_25.extern
4 00:00:00     14022192_[1-3]
5 00:00:00       14022204_[4]
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> range.pattern <- list(
+   "[[]",
+   task1=int.pattern,
+   list(
+     "-",
+     taskN=int.pattern
+   ), "?",
+   "[]]")
> namedCapture::df_match_variable(sacct.df, JobID=range.pattern)
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID JobID.task1 JobID.taskN
1 07:04:42        13937810_25          NA          NA
2 07:04:42  13937810_25.batch          NA          NA
3 07:04:49 13937810_25.extern          NA          NA
4 00:00:00     14022192_[1-3]           1           3
5 00:00:00       14022204_[4]           4          NA
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> 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)
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID JobID.task JobID.task1 JobID.taskN
1 07:04:42        13937810_25         25          NA          NA
2 07:04:42  13937810_25.batch         25          NA          NA
3 07:04:49 13937810_25.extern         25          NA          NA
4 00:00:00     14022192_[1-3]         NA           1           3
5 00:00:00       14022204_[4]         NA           4          NA
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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

\begin{Schunk}
\begin{Sinput}
> 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))
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID JobID.job JobID.task JobID.task1 JobID.taskN
1 07:04:42        13937810_25  13937810         25          NA          NA
2 07:04:42  13937810_25.batch  13937810         25          NA          NA
3 07:04:49 13937810_25.extern  13937810         25          NA          NA
4 00:00:00     14022192_[1-3]  14022192         NA           1           3
5 00:00:00       14022204_[4]  14022204         NA           4          NA
  JobID.type Elapsed.hours Elapsed.minutes Elapsed.seconds
1                        7               4              42
2      batch             7               4              42
3     extern             7               4              49
4                        0               0               0
5                        0               0               0
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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{Comparisons with other R packages}
\label{sec:comparisons}

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

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

\begin{Schunk}
\begin{Sinput}
> log.subject <- 'gate3.fmr.com - - [05/Jul/1995:13:51:39 -0400] "GET /shuttle/countdown/ 
+ curly02.slip.yorku.ca - - [10/Jul/1995:23:11:49 -0400] "GET /sts-70/sts-70-patch-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]]
> 
\end{Sinput}
\end{Schunk}

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: 

\begin{Schunk}
\begin{Sinput}
> library(rex)
> library(dplyr)
> (rex.filetype.pattern <- rex(
+   non_spaces, ".",
+   capture(name = 'filetype',
+           none_of(space, ".", "?", double_quote) %>% one_or_more())))
\end{Sinput}
\begin{Soutput}
[^[:space:]]+\.(?<filetype>(?:[^[:space:].?"])+)
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> rex.pattern <- rex(
+   "[",
+   capture(name = "time", none_of("]") %>% zero_or_more()),
+   "]",
+   space, double_quote, "GET", space,
+   maybe(rex.filetype.pattern))
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> re_matches(log.lines, rex.pattern) %>% mutate(
+   filetype = tolower(filetype),
+   time = as.POSIXct(time, format="%d/%b/%Y:%H:%M:%S %z"))
\end{Sinput}
\begin{Soutput}
                 time filetype
1 1995-07-05 10:51:39         
2 1995-07-10 20:11:49      gif
3 1995-07-15 08:27:49      mpg
4 1995-07-13 08:02:50      xbm
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}


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

\begin{Schunk}
\begin{Sinput}
> namedCapture.filetype.pattern <- list(
+   "[^[:space:]]+[.]", 
+   filetype='[^[:space:].?"]+', tolower)
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> namedCapture::str_match_variable(
+   log.lines,
+   "\\[",
+   time="[^]]*", function(x)as.POSIXct(x, format="%d/%b/%Y:%H:%M:%S %z"),
+   "\\]",
+   ' "GET ',
+   namedCapture.filetype.pattern, "?")
\end{Sinput}
\begin{Soutput}
                 time filetype
1 1995-07-05 10:51:39         
2 1995-07-10 20:11:49      gif
3 1995-07-15 08:27:49      mpg
4 1995-07-13 08:02:50      xbm
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

Overall both \CRANpkg{rex} and \CRANpkg{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 \CRANpkg{namedCapture} assumes the user knows regular
  expressions and can write them as R string literals; \CRANpkg{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 \CRANpkg{rex} code is a bit more verbose than
  \CRANpkg{namedCapture}.
\item In \CRANpkg{namedCapture} type conversion functions can be specified on the
  same line as the capture group name/pattern, whereas in \CRANpkg{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 \CRANpkg{tidyr} package provides 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:

\begin{Schunk}
\begin{Sinput}
> tidyr.range.pattern <- "\\[([0-9]+)(?:-([0-9]+))?\\]"
> tidyr::extract(
+   sacct.df, "JobID", c("task1", "taskN"), 
+   tidyr.range.pattern, remove=FALSE)
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID task1 taskN
1 07:04:42        13937810_25  <NA>  <NA>
2 07:04:42  13937810_25.batch  <NA>  <NA>
3 07:04:49 13937810_25.extern  <NA>  <NA>
4 00:00:00     14022192_[1-3]     1     3
5 00:00:00       14022204_[4]     4  <NA>
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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:

\begin{Schunk}
\begin{Sinput}
> tidyr.task.pattern <- paste0("_(?:([0-9]+)|", tidyr.range.pattern, ")")
> tidyr::extract(sacct.df, "JobID", c("task", "task1", "taskN"), 
+   tidyr.task.pattern, remove=FALSE)
\end{Sinput}
\begin{Soutput}
   Elapsed              JobID task task1 taskN
1 07:04:42        13937810_25   25  <NA>  <NA>
2 07:04:42  13937810_25.batch   25  <NA>  <NA>
3 07:04:49 13937810_25.extern   25  <NA>  <NA>
4 00:00:00     14022192_[1-3] <NA>     1     3
5 00:00:00       14022204_[4] <NA>     4  <NA>
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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

\begin{Schunk}
\begin{Sinput}
> 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))
\end{Sinput}
\begin{Soutput}
   Elapsed      job task task1 taskN   type
1 07:04:42 13937810   25  <NA>  <NA>   <NA>
2 07:04:42 13937810   25  <NA>  <NA>  batch
3 07:04:49 13937810   25  <NA>  <NA> extern
4 00:00:00 14022192 <NA>     1     3   <NA>
5 00:00:00 14022204 <NA>     4  <NA>   <NA>
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

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.

\begin{Schunk}
\begin{Sinput}
> tidyr::extract(job.df, "Elapsed", c("hours", "minutes", "seconds"),
+   "([0-9]+):([0-9]+):([0-9]+)", convert=TRUE)
\end{Sinput}
\begin{Soutput}
  hours minutes seconds      job task task1 taskN   type
1     7       4      42 13937810   25  <NA>  <NA>   <NA>
2     7       4      42 13937810   25  <NA>  <NA>  batch
3     7       4      49 13937810   25  <NA>  <NA> extern
4     0       0       0 14022192 <NA>     1     3   <NA>
5     0       0       0 14022204 <NA>     4  <NA>   <NA>
\end{Soutput}
\begin{Sinput}
> 
\end{Sinput}
\end{Schunk}

Overall \code{tidyr::extract} functions
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, the
  \CRANpkg{namedCapture} variable argument syntax supports specifying
  capture group names via R argument names on the same line as the
  corresponding sub-pattern.
\item Whereas \code{tidyr::extract(convert=TRUE)} always uses
  \code{utils::type.convert} for type conversion,
  \code{namedCapture::df\_match\_variable} supports arbitrary
  group-specific type conversion functions, which are specified on the
  same line as the corresponding name/pattern.
\item Because one call to \code{tidyr::extract} extracts data from one
  column in the subject data frame, it 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
\CRANpkg{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
\CRANpkg{re2r}, \CRANpkg{stringr}, \CRANpkg{stringi},
\CRANpkg{rematch2}, \CRANpkg{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
\CRANpkg{rex} and \CRANpkg{rematch2} packages have significantly larger slopes than
the other packages
(\CRANpkg{namedCapture}, \CRANpkg{stringr}, \CRANpkg{stringi}, and \CRANpkg{re2r}). This can be explained because \CRANpkg{rex} and \CRANpkg{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}
  \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 \CRANpkg{tidyr}. Again we expected small
differences between the packages, and we observed linear time
complexity for both \CRANpkg{namedCapture} and \CRANpkg{tidyr}.

The fourth example involves using a pathological regular expression of
increasing size (with backreferences) on a subject of increasing size.
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}
  \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
limit PCRE imposes on backtracking. Overall this comparison suggests
that for guaranteed fast matching, RE2 must be used, via the \CRANpkg{re2r} or
\CRANpkg{namedCapture} packages. 

\section{Discussion and conclusions}

Our comparisons showed how similar operations can be performed by
\CRANpkg{namedCapture} and other R packages (e.g. \CRANpkg{tidyr} and
\CRANpkg{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 \CRANpkg{namedCapture} package, along with
detailed comparisons with other R packages for regular expressions.  A
unique feature of the \CRANpkg{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 \CRANpkg{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.
Overall we hope that the unique features of the \CRANpkg{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}

\bibliography{hocking}

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

\begin{figure}
  \includegraphics[width=\textwidth]{figure-timings-pathological}
  \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}