/* Handle list of needed message catalogs
   Copyright (C) 1995, 1996, 1997 Free Software Foundation, Inc.
   Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

#ifdef HAVE_CONFIG_H
# include <lynx_cfg.h>
#endif

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <sys/types.h>

#if defined STDC_HEADERS || defined _LIBC
# include <stdlib.h>
#else
# ifdef HAVE_MALLOC_H
#  include <malloc.h>
# else
void free ();
# endif
#endif

#if defined HAVE_STRING_H || defined _LIBC
# include <string.h>
#else
# include <strings.h>
# ifndef memcpy
#  define memcpy(Dst, Src, Num) bcopy (Src, Dst, Num)
# endif
#endif
#if !HAVE_STRCHR && !defined _LIBC
# ifndef strchr
#  define strchr index
# endif
#endif

#if defined HAVE_UNISTD_H || defined _LIBC
# include <unistd.h>
#endif

#include <gettext.h>
#include <gettextP.h>
#ifdef _LIBC
# include <libintl.h>
#else
# include <libgettext.h>
#endif

/* @@ end of prolog @@ */
/* List of already loaded domains.  */
static struct loaded_l10nfile *_nl_loaded_domains;


/* Return a data structure describing the message catalog described by
   the DOMAINNAME and CATEGORY parameters with respect to the currently
   established bindings.  */
struct loaded_l10nfile *
_nl_find_domain (dirname, locale, domainname)
     const char *dirname;
     char *locale;
     const char *domainname;
{
  struct loaded_l10nfile *retval;
  const char *language;
  const char *modifier;
  const char *territory;
  const char *codeset;
  const char *normalized_codeset;
  const char *special;
  const char *sponsor;
  constpre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
#
#
#            Nim's Runtime Library
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## Regular expression support for Nim.
##
## This module is implemented by providing a wrapper around the
## `PCRE (Perl-Compatible Regular Expressions) <http://www.pcre.org>`_
## C library. This means that your application will depend on the PCRE
## library's licence when using this module, which should not be a problem
## though.
## PCRE's licence follows:
##
## .. include:: ../../doc/regexprs.txt
##

import
  pcre, strutils, rtarrays

const
  MaxSubpatterns* = 20
    ## defines the maximum number of subpatterns that can be captured.
    ## This limit still exists for ``replacef`` and ``parallelReplace``.

type
  RegexFlag* = enum     ## options for regular expressions
    reIgnoreCase = 0,    ## do caseless matching
    reMultiLine = 1,     ## ``^`` and ``$`` match newlines within data
    reDotAll = 2,        ## ``.`` matches anything including NL
    reExtended = 3,      ## ignore whitespace and ``#`` comments
    reStudy = 4          ## study the expression (may be omitted if the
                         ## expression will be used only once)

  RegexDesc = object
    h: ptr Pcre
    e: ptr ExtraData

  Regex* = ref RegexDesc ## a compiled regular expression

  RegexError* = object of ValueError
    ## is raised if the pattern is no valid regular expression.

proc raiseInvalidRegex(msg: string) {.noinline, noreturn.} =
  var e: ref RegexError
  new(e)
  e.msg = msg
  raise e

proc rawCompile(pattern: string, flags: cint): ptr Pcre =
  var
    msg: cstring = ""
    offset: cint = 0
  result = pcre.compile(pattern, flags, addr(msg), addr(offset), nil)
  if result == nil:
    raiseInvalidRegex($msg & "\n" & pattern & "\n" & spaces(offset) & "^\n")

proc finalizeRegEx(x: Regex) =
  # XXX This is a hack, but PCRE does not export its "free" function properly.
  # Sigh. The hack relies on PCRE's implementation (see ``pcre_get.c``).
  # Fortunately the implementation is unlikely to change.
  pcre.free_substring(cast[cstring](x.h))
  if not isNil(x.e):
    pcre.free_substring(cast[cstring](x.e))

proc re*(s: string, flags = {reStudy}): Regex =
  ## Constructor of regular expressions.
  ##
  ## Note that Nim's
  ## extended raw string literals support the syntax ``re"[abc]"`` as
  ## a short form for ``re(r"[abc]")``.
  new(result, finalizeRegEx)
  result.h = rawCompile(s, cast[cint](flags - {reStudy}))
  if reStudy in flags:
    var msg: cstring = ""
    var options: cint = 0
    var hasJit: cint = 0
    if pcre.config(pcre.CONFIG_JIT, addr hasJit) == 0:
      if hasJit == 1'i32:
        options = pcre.STUDY_JIT_COMPILE
    result.e = pcre.study(result.h, options, addr msg)
    if not isNil(msg): raiseInvalidRegex($msg)

proc rex*(s: string, flags = {reStudy, reExtended}): Regex =
  ## Constructor for extended regular expressions.
  ##
  ## The extended means that comments starting with `#` and
  ## whitespace are ignored.
  result = re(s, flags)

proc bufSubstr(b: cstring, sPos, ePos: int): string {.inline.} =
  ## Return a Nim string built from a slice of a cstring buffer.
  ## Don't assume cstring is '\0' terminated
  let sz = ePos - sPos
  result = newString(sz+1)
  copyMem(addr(result[0]), unsafeaddr(b[sPos]), sz)
  result.setLen(sz)

proc matchOrFind(buf: cstring, pattern: Regex, matches: var openArray[string],
                 start, bufSize, flags: cint): cint =
  var
    rtarray = initRtArray[cint]((matches.len+1)*3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize, start, flags,
      cast[ptr cint](rawMatches), (matches.len+1).cint*3)
  if res < 0'i32: return res
  for i in 1..int(res)-1:
    var a = rawMatches[i * 2]
    var b = rawMatches[i * 2 + 1]
    if a >= 0'i32:
      matches[i-1] = bufSubstr(buf, int(a), int(b))
    else: matches[i-1] = ""
  return rawMatches[1] - rawMatches[0]

proc findBounds*(buf: cstring, pattern: Regex, matches: var openArray[string],
                 start = 0, bufSize: int): tuple[first, last: int] =
  ## returns the starting position and end position of ``pattern`` in ``buf``
  ## (where ``buf`` has length ``bufSize`` and is not necessarily ``'\0'`` terminated),
  ## and the captured
  ## substrings in the array ``matches``. If it does not match, nothing
  ## is written into ``matches`` and ``(-1,0)`` is returned.
  var
    rtarray = initRtArray[cint]((matches.len+1)*3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, 0'i32,
      cast[ptr cint](rawMatches), (matches.len+1).cint*3)
  if res < 0'i32: return (-1, 0)
  for i in 1..int(res)-1:
    var a = rawMatches[i * 2]
    var b = rawMatches[i * 2 + 1]
    if a >= 0'i32: matches[i-1] = bufSubstr(buf, int(a), int(b))
    else: matches[i-1] = ""
  return (rawMatches[0].int, rawMatches[1].int - 1)

proc findBounds*(s: string, pattern: Regex, matches: var openArray[string],
                 start = 0): tuple[first, last: int] {.inline.} =
  ## returns the starting position and end position of ``pattern`` in ``s``
  ## and the captured substrings in the array ``matches``.
  ## If it does not match, nothing
  ## is written into ``matches`` and ``(-1,0)`` is returned.
  result = findBounds(cstring(s), pattern, matches, start, s.len)

proc findBounds*(buf: cstring, pattern: Regex,
                 matches: var openArray[tuple[first, last: int]],
                 start = 0, bufSize = 0): tuple[first, last: int] =
  ## returns the starting position and end position of ``pattern`` in ``buf``
  ## (where ``buf`` has length ``bufSize`` and is not necessarily ``'\0'`` terminated),
  ## and the captured substrings in the array ``matches``.
  ## If it does not match, nothing is written into ``matches`` and
  ## ``(-1,0)`` is returned.
  var
    rtarray = initRtArray[cint]((matches.len+1)*3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, 0'i32,
      cast[ptr cint](rawMatches), (matches.len+1).cint*3)
  if res < 0'i32: return (-1, 0)
  for i in 1..int(res)-1:
    var a = rawMatches[i * 2]
    var b = rawMatches[i * 2 + 1]
    if a >= 0'i32: matches[i-1] = (int(a), int(b)-1)
    else: matches[i-1] = (-1,0)
  return (rawMatches[0].int, rawMatches[1].int - 1)

proc findBounds*(s: string, pattern: Regex,
                 matches: var openArray[tuple[first, last: int]],
                 start = 0): tuple[first, last: int] {.inline.} =
  ## returns the starting position and end position of ``pattern`` in ``s``
  ## and the captured substrings in the array ``matches``.
  ## If it does not match, nothing is written into ``matches`` and
  ## ``(-1,0)`` is returned.
  result = findBounds(cstring(s), pattern, matches, start, s.len)

proc findBounds*(buf: cstring, pattern: Regex,
                 start = 0, bufSize: int): tuple[first, last: int] =
  ## returns the ``first`` and ``last`` position of ``pattern`` in ``buf``,
  ## where ``buf`` has length ``bufSize`` (not necessarily ``'\0'`` terminated).
  ## If it does not match, ``(-1,0)`` is returned.
  var
    rtarray = initRtArray[cint](3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, 0'i32,
      cast[ptr cint](rawMatches), 3)
  if res < 0'i32: return (int(res), 0)
  return (int(rawMatches[0]), int(rawMatches[1]-1))

proc findBounds*(s: string, pattern: Regex,
                 start = 0): tuple[first, last: int] {.inline.} =
  ## returns the ``first`` and ``last`` position of ``pattern`` in ``s``.
  ## If it does not match, ``(-1,0)`` is returned.
  ##
  ## Note: there is a speed improvement if the matches do not need to be captured.
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   assert findBounds("01234abc89", re"abc") == (5,7)
  result = findBounds(cstring(s), pattern, start, s.len)

proc matchOrFind(buf: cstring, pattern: Regex, start, bufSize: int, flags: cint): cint =
  var
    rtarray = initRtArray[cint](3)
    rawMatches = rtarray.getRawData
  result = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, flags,
                    cast[ptr cint](rawMatches), 3)
  if result >= 0'i32:
    result = rawMatches[1] - rawMatches[0]

proc matchLen*(s: string, pattern: Regex, matches: var openArray[string],
              start = 0): int {.inline.} =
  ## the same as ``match``, but it returns the length of the match,
  ## if there is no match, ``-1`` is returned. Note that a match length
  ## of zero can happen.
  result = matchOrFind(cstring(s), pattern, matches, start.cint, s.len.cint, pcre.ANCHORED)

proc matchLen*(buf: cstring, pattern: Regex, matches: var openArray[string],
              start = 0, bufSize: int): int {.inline.} =
  ## the same as ``match``, but it returns the length of the match,
  ## if there is no match, ``-1`` is returned. Note that a match length
  ## of zero can happen.
  return matchOrFind(buf, pattern, matches, start.cint, bufSize.cint, pcre.ANCHORED)

proc matchLen*(s: string, pattern: Regex, start = 0): int {.inline.} =
  ## the same as ``match``, but it returns the length of the match,
  ## if there is no match, ``-1`` is returned. Note that a match length
  ## of zero can happen.
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   echo matchLen("abcdefg", re"cde", 2)  # =>  3
  ##   echo matchLen("abcdefg", re"abcde")   # =>  5
  ##   echo matchLen("abcdefg", re"cde")     # => -1
  result = matchOrFind(cstring(s), pattern, start.cint, s.len.cint, pcre.ANCHORED)

proc matchLen*(buf: cstring, pattern: Regex, start = 0, bufSize: int): int {.inline.} =
  ## the same as ``match``, but it returns the length of the match,
  ## if there is no match, ``-1`` is returned. Note that a match length
  ## of zero can happen.
  result = matchOrFind(buf, pattern, start.cint, bufSize, pcre.ANCHORED)

proc match*(s: string, pattern: Regex, start = 0): bool {.inline.} =
  ## returns ``true`` if ``s[start..]`` matches the ``pattern``.
  result = matchLen(cstring(s), pattern, start, s.len) != -1

proc match*(s: string, pattern: Regex, matches: var openArray[string],
           start = 0): bool {.inline.} =
  ## returns ``true`` if ``s[start..]`` matches the ``pattern`` and
  ## the captured substrings in the array ``matches``. If it does not
  ## match, nothing is written into ``matches`` and ``false`` is
  ## returned.
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   var matches: array[2, string]
  ##   if match("abcdefg", re"c(d)ef(g)", matches, 2):
  ##     for s in matches:
  ##       echo s       # => d g
  result = matchLen(cstring(s), pattern, matches, start, s.len) != -1

proc match*(buf: cstring, pattern: Regex, matches: var openArray[string],
           start = 0, bufSize: int): bool {.inline.} =
  ## returns ``true`` if ``buf[start..<bufSize]`` matches the ``pattern`` and
  ## the captured substrings in the array ``matches``. If it does not
  ## match, nothing is written into ``matches`` and ``false`` is
  ## returned.
  ## ``buf`` has length ``bufSize`` (not necessarily ``'\0'`` terminated).
  result = matchLen(buf, pattern, matches, start, bufSize) != -1

proc find*(buf: cstring, pattern: Regex, matches: var openArray[string],
           start = 0, bufSize = 0): int =
  ## returns the starting position of ``pattern`` in ``buf`` and the captured
  ## substrings in the array ``matches``. If it does not match, nothing
  ## is written into ``matches`` and ``-1`` is returned.
  ## ``buf`` has length ``bufSize`` (not necessarily ``'\0'`` terminated).
  var
    rtarray = initRtArray[cint]((matches.len+1)*3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, 0'i32,
      cast[ptr cint](rawMatches), (matches.len+1).cint*3)
  if res < 0'i32: return res
  for i in 1..int(res)-1:
    var a = rawMatches[i * 2]
    var b = rawMatches[i * 2 + 1]
    if a >= 0'i32: matches[i-1] = bufSubstr(buf, int(a), int(b))
    else: matches[i-1] = ""
  return rawMatches[0]

proc find*(s: string, pattern: Regex, matches: var openArray[string],
           start = 0): int {.inline.} =
  ## returns the starting position of ``pattern`` in ``s`` and the captured
  ## substrings in the array ``matches``. If it does not match, nothing
  ## is written into ``matches`` and ``-1`` is returned.
  result = find(cstring(s), pattern, matches, start, s.len)

proc find*(buf: cstring, pattern: Regex, start = 0, bufSize: int): int =
  ## returns the starting position of ``pattern`` in ``buf``,
  ## where ``buf`` has length ``bufSize`` (not necessarily ``'\0'`` terminated).
  ## If it does not match, ``-1`` is returned.
  var
    rtarray = initRtArray[cint](3)
    rawMatches = rtarray.getRawData
    res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, start.cint, 0'i32,
      cast[ptr cint](rawMatches), 3)
  if res < 0'i32: return res
  return rawMatches[0]

proc find*(s: string, pattern: Regex, start = 0): int {.inline.} =
  ## returns the starting position of ``pattern`` in ``s``. If it does not
  ## match, ``-1`` is returned.
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##  echo find("abcdefg", re"cde")  # => 2
  ##  echo find("abcdefg", re"abc")  # => 0
  ##  echo find("abcdefg", re"zz")  # => -1
  result = find(cstring(s), pattern, start, s.len)

iterator findAll*(s: string, pattern: Regex, start = 0): string =
  ## Yields all matching *substrings* of `s` that match `pattern`.
  ##
  ## Note that since this is an iterator you should not modify the string you
  ## are iterating over: bad things could happen.
  var
    i = int32(start)
    rtarray = initRtArray[cint](3)
    rawMatches = rtarray.getRawData
  while true:
    let res = pcre.exec(pattern.h, pattern.e, s, len(s).cint, i, 0'i32,
      cast[ptr cint](rawMatches), 3)
    if res < 0'i32: break
    let a = rawMatches[0]
    let b = rawMatches[1]
    if a == b and a == i: break
    yield substr(s, int(a), int(b)-1)
    i = b

iterator findAll*(buf: cstring, pattern: Regex, start = 0, bufSize: int): string =
  ## Yields all matching `substrings` of ``s`` that match ``pattern``.
  ##
  ## Note that since this is an iterator you should not modify the string you
  ## are iterating over: bad things could happen.
  var
    i = int32(start)
    rtarray = initRtArray[cint](3)
    rawMatches = rtarray.getRawData
  while true:
    let res = pcre.exec(pattern.h, pattern.e, buf, bufSize.cint, i, 0'i32,
      cast[ptr cint](rawMatches), 3)
    if res < 0'i32: break
    let a = rawMatches[0]
    let b = rawMatches[1]
    if a == b and a == i: break
    var str = newString(b-a)
    copyMem(str[0].addr, unsafeAddr(buf[a]), b-a)
    yield str
    i = b

proc findAll*(s: string, pattern: Regex, start = 0): seq[string] {.inline.} =
  ## returns all matching `substrings` of ``s`` that match ``pattern``.
  ## If it does not match, @[] is returned.
  accumulateResult(findAll(s, pattern, start))

when not defined(nimhygiene):
  {.pragma: inject.}

template `=~` *(s: string, pattern: Regex): untyped =
  ## This calls ``match`` with an implicit declared ``matches`` array that
  ## can be used in the scope of the ``=~`` call:
  ##
  ## .. code-block:: nim
  ##
  ##   if line =~ re"\s*(\w+)\s*\=\s*(\w+)":
  ##     # matches a key=value pair:
  ##     echo("Key: ", matches[0])
  ##     echo("Value: ", matches[1])
  ##   elif line =~ re"\s*(\#.*)":
  ##     # matches a comment
  ##     # note that the implicit ``matches`` array is different from the
  ##     # ``matches`` array of the first branch
  ##     echo("comment: ", matches[0])
  ##   else:
  ##     echo("syntax error")
  ##
  bind MaxSubpatterns
  when not declaredInScope(matches):
    var matches {.inject.}: array[MaxSubpatterns, string]
  match(s, pattern, matches)

# ------------------------- more string handling ------------------------------

proc contains*(s: string, pattern: Regex, start = 0): bool {.inline.} =
  ## same as ``find(s, pattern, start) >= 0``
  return find(s, pattern, start) >= 0

proc contains*(s: string, pattern: Regex, matches: var openArray[string],
              start = 0): bool {.inline.} =
  ## same as ``find(s, pattern, matches, start) >= 0``
  return find(s, pattern, matches, start) >= 0

proc startsWith*(s: string, prefix: Regex): bool {.inline.} =
  ## returns true if `s` starts with the pattern `prefix`
  result = matchLen(s, prefix) >= 0

proc endsWith*(s: string, suffix: Regex): bool {.inline.} =
  ## returns true if `s` ends with the pattern `prefix`
  for i in 0 .. s.len-1:
    if matchLen(s, suffix, i) == s.len - i: return true

proc replace*(s: string, sub: Regex, by = ""): string =
  ## Replaces ``sub`` in ``s`` by the string ``by``. Captures cannot be
  ## accessed in ``by``.
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   "var1=key; var2=key2".replace(re"(\w+)=(\w+)")
  ##
  ## Results in:
  ##
  ## .. code-block:: nim
  ##
  ##   "; "
  result = ""
  var prev = 0
  while true:
    var match = findBounds(s, sub, prev)
    if match.first < 0: break
    add(result, substr(s, prev, match.first-1))
    add(result, by)
    prev = match.last + 1
  add(result, substr(s, prev))

proc replacef*(s: string, sub: Regex, by: string): string =
  ## Replaces ``sub`` in ``s`` by the string ``by``. Captures can be accessed in ``by``
  ## with the notation ``$i`` and ``$#`` (see strutils.\`%\`).
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   "var1=key; var2=key2".replacef(re"(\w+)=(\w+)", "$1<-$2$2")
  ##
  ## Results in:
  ##
  ## .. code-block:: nim
  ##
  ## "var1<-keykey; val2<-key2key2"
  result = ""
  var caps: array[MaxSubpatterns, string]
  var prev = 0
  while true:
    var match = findBounds(s, sub, caps, prev)
    if match.first < 0: break
    add(result, substr(s, prev, match.first-1))
    addf(result, by, caps)
    prev = match.last + 1
  add(result, substr(s, prev))

proc multiReplace*(s: string, subs: openArray[
                   tuple[pattern: Regex, repl: string]]): string =
  ## Returns a modified copy of ``s`` with the substitutions in ``subs``
  ## applied in parallel.
  result = ""
  var i = 0
  var caps: array[MaxSubpatterns, string]
  while i < s.len:
    block searchSubs:
      for j in 0..high(subs):
        var x = matchLen(s, subs[j][0], caps, i)
        if x > 0:
          addf(result, subs[j][1], caps)
          inc(i, x)
          break searchSubs
      add(result, s[i])
      inc(i)
  # copy the rest:
  add(result, substr(s, i))

proc parallelReplace*(s: string, subs: openArray[
                      tuple[pattern: Regex, repl: string]]): string {.deprecated.} =
  ## Returns a modified copy of ``s`` with the substitutions in ``subs``
  ## applied in parallel.
  ## **Deprecated since version 0.18.0**: Use ``multiReplace`` instead.
  result = multiReplace(s, subs)

proc transformFile*(infile, outfile: string,
                    subs: openArray[tuple[pattern: Regex, repl: string]]) =
  ## reads in the file ``infile``, performs a parallel replacement (calls
  ## ``parallelReplace``) and writes back to ``outfile``. Raises ``IOError`` if an
  ## error occurs. This is supposed to be used for quick scripting.
  var x = readFile(infile).string
  writeFile(outfile, x.multiReplace(subs))

iterator split*(s: string, sep: Regex; maxsplit = -1): string =
  ## Splits the string ``s`` into substrings.
  ##
  ## Substrings are separated by the regular expression ``sep``
  ## (and the portion matched by ``sep`` is not returned).
  ##
  ## Example:
  ##
  ## .. code-block:: nim
  ##   for word in split("00232this02939is39an22example111", re"\d+"):
  ##     writeLine(stdout, word)
  ##
  ## Results in:
  ##
  ## .. code-block:: nim
  ##   ""
  ##   "this"
  ##   "is"
  ##   "an"
  ##   "example"
  ##   ""
  ##
  var last = 0
  var splits = maxsplit
  var x: int
  while last <= len(s):
    var first = last
    var sepLen = 1
    while last < len(s):
      x = matchLen(s, sep, last)
      if x >= 0:
        sepLen = x
        break
      inc(last)
    if x == 0:
      if last >= len(s): break
      inc last
    if splits == 0: last = len(s)
    yield substr(s, first, last-1)
    if splits == 0: break
    dec(splits)
    inc(last, sepLen)

proc split*(s: string, sep: Regex, maxsplit = -1): seq[string] {.inline.} =
  ## Splits the string ``s`` into a seq of substrings.
  ##
  ## The portion matched by ``sep`` is not returned.
  accumulateResult(split(s, sep))

proc escapeRe*(s: string): string =
  ## escapes ``s`` so that it is matched verbatim when used as a regular
  ## expression.
  result = ""
  for c in items(s):
    case c
    of 'a'..'z', 'A'..'Z', '0'..'9', '_':
      result.add(c)
    else:
      result.add("\\x")
      result.add(toHex(ord(c), 2))

const ## common regular expressions
  reIdentifier* {.deprecated.} = r"\b[a-zA-Z_]+[a-zA-Z_0-9]*\b"
    ## describes an identifier
  reNatural* {.deprecated.} = r"\b\d+\b"
    ## describes a natural number
  reInteger* {.deprecated.} = r"\b[-+]?\d+\b"
    ## describes an integer
  reHex* {.deprecated.} = r"\b0[xX][0-9a-fA-F]+\b"
    ## describes a hexadecimal number
  reBinary* {.deprecated.} = r"\b0[bB][01]+\b"
    ## describes a binary number (example: 0b11101)
  reOctal* {.deprecated.} = r"\b0[oO][0-7]+\b"
    ## describes an octal number (example: 0o777)
  reFloat* {.deprecated.} = r"\b[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?\b"
    ## describes a floating point number
  reEmail* {.deprecated.} = r"\b[a-zA-Z0-9!#$%&'*+/=?^_`{|}~\-]+(?:\. &" &
                            r"[a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+)*@" &
                            r"(?:[a-zA-Z0-9](?:[a-zA-Z0-9-]*[a-zA-Z0-9])?\.)+" &
                            r"(?:[a-zA-Z]{2}|com|org|net|gov|mil|biz|" &
                            r"info|mobi|name|aero|jobs|museum)\b"
    ## describes a common email address
  reURL* {.deprecated.} = r"\b(http(s)?|ftp|gopher|telnet|file|notes|ms-help)" &
                          r":((//)|(\\\\))+[\w\d:#@%/;$()~_?\+\-\=\\\.\&]*\b"
    ## describes an URL

when isMainModule:
  doAssert match("(a b c)", rex"\( .* \)")
  doAssert match("WHiLe", re("while", {reIgnoreCase}))

  doAssert "0158787".match(re"\d+")
  doAssert "ABC 0232".match(re"\w+\s+\d+")
  doAssert "ABC".match(rex"\d+ | \w+")

  {.push warnings:off.}
  doAssert matchLen("key", re(reIdentifier)) == 3
  {.pop.}

  var pattern = re"[a-z0-9]+\s*=\s*[a-z0-9]+"
  doAssert matchLen("key1=  cal9", pattern) == 11

  doAssert find("_____abc_______", re"abc") == 5
  doAssert findBounds("_____abc_______", re"abc") == (5,7)

  var matches: array[6, string]
  if match("abcdefg", re"c(d)ef(g)", matches, 2):
    doAssert matches[0] == "d"
    doAssert matches[1] == "g"
  else:
    doAssert false

  if "abc" =~ re"(a)bcxyz|(\w+)":
    doAssert matches[1] == "abc"
  else:
    doAssert false

  if "abc" =~ re"(cba)?.*":
    doAssert matches[0] == ""
  else: doAssert false

  if "abc" =~ re"().*":
    doAssert matches[0] == ""
  else: doAssert false

  doAssert "var1=key; var2=key2".endsWith(re"\w+=\w+")
  doAssert("var1=key; var2=key2".replacef(re"(\w+)=(\w+)", "$1<-$2$2") ==
         "var1<-keykey; var2<-key2key2")
  doAssert("var1=key; var2=key2".replace(re"(\w+)=(\w+)", "$1<-$2$2") ==
         "$1<-$2$2; $1<-$2$2")

  var accum: seq[string] = @[]
  for word in split("00232this02939is39an22example111", re"\d+"):
    accum.add(word)
  doAssert(accum == @["", "this", "is", "an", "example", ""])

  accum = @[]
  for word in split("AAA :   : BBB", re"\s*:\s*"):
    accum.add(word)
  doAssert(accum == @["AAA", "", "BBB"])

  doAssert(split("abc", re"") == @["a", "b", "c"])
  doAssert(split("", re"") == @[])

  doAssert(split("a;b;c", re";") == @["a", "b", "c"])
  doAssert(split(";a;b;c", re";") == @["", "a", "b", "c"])
  doAssert(split(";a;b;c;", re";") == @["", "a", "b", "c", ""])
  doAssert(split("a;b;c;", re";") == @["a", "b", "c", ""])

  for x in findAll("abcdef", re"^{.}", 3):
    doAssert x == "d"
  accum = @[]
  for x in findAll("abcdef", re".", 3):
    accum.add(x)
  doAssert(accum == @["d", "e", "f"])

  doAssert("XYZ".find(re"^\d*") == 0)
  doAssert("XYZ".match(re"^\d*") == true)

  block:
    var matches: array[16, string]
    if match("abcdefghijklmnop", re"(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)", matches):
      for i in 0..matches.high:
        doAssert matches[i] == $chr(i + 'a'.ord)
    else:
      doAssert false

  block:   # Buffer based RE
    var cs: cstring = "_____abc_______"
    doAssert(cs.find(re"abc", bufSize=15) == 5)
    doAssert(cs.matchLen(re"_*abc", bufSize=15) == 8)
    doAssert(cs.matchLen(re"abc", start=5, bufSize=15) == 3)
    doAssert(cs.matchLen(re"abc", start=5, bufSize=7) == -1)
    doAssert(cs.matchLen(re"abc_*", start=5, bufSize=10) == 5)
    var accum: seq[string] = @[]
    for x in cs.findAll(re"[a-z]", start=3, bufSize=15):
      accum.add($x)
    doAssert(accum == @["a","b","c"])