Revert "Base re off of nre"

This reverts commit dc60a51e1545d8c73bc9415d1045864b72cfda0b.

1 files changed, 235 insertions, 142 deletions

diff --git a/lib/impure/re.nim b/lib/impure/re.nim
index 0ff6e9555..5f9371f28 100644
--- a/lib/impure/re.nim
+++ b/lib/impure/re.nim
@@ -2,13 +2,13 @@
 #
 #            Nim's Runtime Library
 #        (c) Copyright 2012 Andreas Rumpf
-#        (c) Copyright 2015 Oleh Prypin
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.
 #
 
-## Regular expression support for Nim. Deprecated in favor of nre.
+## Regular expression support for Nim. Deprecated. Consider using the ``nre``
+## or ``pegs`` modules instead.
 ##
 ## **Note:** The 're' proc defaults to the **extended regular expression
 ## syntax** which lets you use whitespace freely to make your regexes readable.
@@ -25,15 +25,13 @@
 ## .. include:: ../doc/regexprs.txt
 ##
 
-
-import strutils
-import nre, options
-
-type Regex* = nre.Regex
+import
+  pcre, strutils, rtarrays
 
 const
-  MaxSubpatterns* {.deprecated.} = 1000
-    ## This is obsolete. There is no limit on the number of subpatterns.
+  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
@@ -43,61 +41,66 @@ type
     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* {.deprecated.} = ref RegexDesc ## a compiled regular expression
 
   RegexError* = object of ValueError
     ## is raised if the pattern is no valid regular expression.
 
+{.deprecated: [TRegexFlag: RegexFlag, TRegexDesc: RegexDesc, TRegex: Regex,
+    EInvalidRegEx: RegexError].}
+
+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
+  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 = {reExtended, reStudy}): Regex {.deprecated.} =
   ## Constructor of regular expressions. Note that Nim's
   ## extended raw string literals support this syntax ``re"[abc]"`` as
   ## a short form for ``re(r"[abc]")``.
-  var options = ""
-  if reStudy notin flags:
-    options.add "(*NO_STUDY)"
-  for t in [
-    (reIgnoreCase, "(?i)"),
-    (reMultiLine, "(?m)"),
-    (reDotAll, "(?s)"),
-    (reExtended, "(?x)")
-  ]:
-    if t[0] in flags:
-      options.add t[1]
-  try:
-    return nre.re(options & s)
-  except nre.SyntaxError:
-    let e = nre.SyntaxError(getCurrentException())
-    raise newException(RegexError, e.msg & "\n" & e.pattern & "\n" &
-                                   repeat(' ', e.pos) & "^\n")
-  except nre.StudyError:
-    let e = nre.StudyError(getCurrentException())
-    raise newException(RegexError, "Study error: " & e.msg)
-
-
-template execute(f: expr, notFound: stmt): stmt {.immediate, dirty.} =
-  let mm = f(s, pattern, start)
-  var m: RegexMatch
-  if mm.isSome:
-    m = mm.unsafeGet()
-  else:
-    notFound
-
-template stringCaptures(): stmt {.immediate, dirty.} =
-  for i in 0 .. <pattern.captureCount:
-    matches[i] = m.captures[i]
-
-template boundCaptures(): stmt {.immediate, dirty.} =
-  for i in 0 .. <pattern.captureCount:
-    let b = m.captureBounds[i]
-    matches[i] =
-      if b.isSome: (b.unsafeGet().a, <b.unsafeGet().b)
-      else: (-1, 0)
-
-template returnBounds(): stmt {.immediate, dirty.} =
-  return (m.matchBounds.a, <m.matchBounds.b)
-
-template returnLength(): stmt {.immediate, dirty.} =
-  return m.matchBounds.b - m.matchBounds.a + 1
+  new(result, finalizeRegEx)
+  result.h = rawCompile(s, cast[cint](flags - {reStudy}))
+  if reStudy in flags:
+    var msg: cstring
+    result.e = pcre.study(result.h, 0, addr msg)
+    if not isNil(msg): raiseInvalidRegex($msg)
+
+proc matchOrFind(s: string, pattern: Regex, matches: var openArray[string],
+                 start, flags: cint): cint =
+  var
+    rtarray = initRtArray[cint]((matches.len+1)*3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, pattern.e, s, len(s).cint, 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] = substr(s, int(a), int(b)-1)
+    else: matches[i-1] = nil
+  return rawMatches[1] - rawMatches[0]
 
 proc findBounds*(s: string, pattern: Regex, matches: var openArray[string],
                  start = 0): tuple[first, last: int] =
@@ -105,10 +108,18 @@ proc findBounds*(s: string, pattern: Regex, matches: var openArray[string],
   ## and the captured
   ## substrings in the array `matches`. If it does not match, nothing
   ## is written into `matches` and ``(-1,0)`` is returned.
-  execute nre.find:
-    return (-1, 0)
-  stringCaptures()
-  returnBounds()
+  var
+    rtarray = initRtArray[cint]((matches.len+1)*3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, pattern.e, s, len(s).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] = substr(s, int(a), int(b)-1)
+    else: matches[i-1] = nil
+  return (rawMatches[0].int, rawMatches[1].int - 1)
 
 proc findBounds*(s: string, pattern: Regex,
                  matches: var openArray[tuple[first, last: int]],
@@ -117,42 +128,56 @@ proc findBounds*(s: string, pattern: Regex,
   ## and the captured substrings in the array `matches`.
   ## If it does not match, nothing is written into `matches` and
   ## ``(-1,0)`` is returned.
-  execute nre.find:
-    return (-1, 0)
-  boundCaptures()
-  returnBounds()
+  var
+    rtarray = initRtArray[cint]((matches.len+1)*3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, pattern.e, s, len(s).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,
                  start = 0): tuple[first, last: int] =
-  ## returns the starting position of `pattern` in `s`. If it does not
-  ## match, ``(-1,0)`` is returned.
-  execute nre.find:
-    return (-1, 0)
-  returnBounds()
+  ## returns the starting position and end position of ``pattern`` in ``s``.
+  ## If it does not match, ``(-1,0)`` is returned.
+  var
+    rtarray = initRtArray[cint](3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, nil, s, len(s).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 matchOrFind(s: string, pattern: Regex, start, flags: cint): cint =
+  var
+    rtarray = initRtArray[cint](3)
+    rawMatches = rtarray.getRawData
+  result = pcre.exec(pattern.h, pattern.e, s, len(s).cint, start, 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 =
+              start = 0): int =
   ## 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.
-  execute nre.match:
-    return -1
-  stringCaptures()
-  returnLength()
+  return matchOrFind(s, pattern, matches, start.cint, pcre.ANCHORED)
 
 proc matchLen*(s: string, pattern: Regex, start = 0): int =
   ## 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.
-  execute nre.match:
-    return -1
-  returnLength()
+  return matchOrFind(s, pattern, start.cint, pcre.ANCHORED)
 
 proc match*(s: string, pattern: Regex, start = 0): bool =
   ## returns ``true`` if ``s[start..]`` matches the ``pattern``.
-  execute nre.match:
-    return false
-  return true
+  result = matchLen(s, pattern, start) != -1
 
 proc match*(s: string, pattern: Regex, matches: var openArray[string],
            start = 0): bool =
@@ -160,45 +185,65 @@ proc match*(s: string, pattern: Regex, matches: var openArray[string],
   ## the captured substrings in the array ``matches``. If it does not
   ## match, nothing is written into ``matches`` and ``false`` is
   ## returned.
-  execute nre.match:
-    return false
-  stringCaptures()
-  return true
+  result = matchLen(s, pattern, matches, start) != -1
 
 proc find*(s: string, pattern: Regex, matches: var openArray[string],
            start = 0): int =
   ## 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.
-  execute nre.find:
-    return -1
-  stringCaptures()
-  return m.matchBounds.a
+  var
+    rtarray = initRtArray[cint]((matches.len+1)*3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, pattern.e, s, len(s).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] = substr(s, int(a), int(b)-1)
+    else: matches[i-1] = nil
+  return rawMatches[0]
 
 proc find*(s: string, pattern: Regex, start = 0): int =
   ## returns the starting position of ``pattern`` in ``s``. If it does not
   ## match, -1 is returned.
-  execute nre.find:
-    return -1
-  return m.matchBounds.a
+  var
+    rtarray = initRtArray[cint](3)
+    rawMatches = rtarray.getRawData
+    res = pcre.exec(pattern.h, nil, s, len(s).cint, start.cint, 0'i32,
+      cast[ptr cint](rawMatches), 3)
+  if res < 0'i32: return res
+  return rawMatches[0]
 
 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.
-  for m in nre.findIter(s, pattern, start):
-    yield $m
+  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
 
 proc findAll*(s: string, pattern: Regex, start = 0): seq[string] =
   ## returns all matching *substrings* of `s` that match `pattern`.
   ## If it does not match, @[] is returned.
-  accumulateResult findAll(s, pattern, start)
+  accumulateResult(findAll(s, pattern, start))
 
 when not defined(nimhygiene):
   {.pragma: inject.}
 
-template `=~`*(s: string, pattern: Regex, start = 0): expr =
+template `=~` *(s: string, pattern: Regex): expr =
   ## This calls ``match`` with an implicit declared ``matches`` array that
   ## can be used in the scope of the ``=~`` call:
   ##
@@ -216,11 +261,10 @@ template `=~`*(s: string, pattern: Regex, start = 0): expr =
   ##   else:
   ##     echo("syntax error")
   ##
-  let mm = nre.match(s, pattern, start)
-  var matches {.inject.}: seq[string]
-  if mm.isSome:
-    matches = mm.unsafeGet().captures.toSeq()
-  mm.isSome
+  bind MaxSubpatterns
+  when not declaredInScope(matches):
+    var matches {.inject.}: array[MaxSubpatterns, string]
+  match(s, pattern, matches)
 
 # ------------------------- more string handling ------------------------------
 
@@ -239,9 +283,8 @@ proc startsWith*(s: string, prefix: Regex): bool =
 
 proc endsWith*(s: string, suffix: Regex): bool =
   ## returns true if `s` ends with the pattern `prefix`
-  for i in 0 .. s.high:
-    if matchLen(s, suffix, i) == s.len - i:
-      return true
+  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
@@ -255,7 +298,15 @@ proc replace*(s: string, sub: Regex, by = ""): string =
   ## .. code-block:: nim
   ##
   ##   "; "
-  return nre.replace(s, sub, by.replace("$", "$$"))
+  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`
@@ -269,7 +320,18 @@ proc replacef*(s: string, sub: Regex, by: string): string =
   ## .. code-block:: nim
   ##
   ## "var1<-keykey; val2<-key2key2"
-  return nre.replace(s, sub, by)
+  result = ""
+  var caps: array[MaxSubpatterns, string]
+  var prev = 0
+  while true:
+    var match = findBounds(s, sub, caps, prev)
+    if match.first < 0: break
+    assert result != nil
+    assert s != nil
+    add(result, substr(s, prev, match.first-1))
+    addf(result, by, caps)
+    prev = match.last + 1
+  add(result, substr(s, prev))
 
 proc parallelReplace*(s: string, subs: openArray[
                       tuple[pattern: Regex, repl: string]]): string =
@@ -277,20 +339,19 @@ proc parallelReplace*(s: string, subs: openArray[
   ## applied in parallel.
   result = ""
   var i = 0
+  var caps: array[MaxSubpatterns, string]
   while i < s.len:
     block searchSubs:
-      for sub in subs:
-        let pattern = sub.pattern
-        let start = i
-        execute nre.match:
-          continue
-        result.addf sub.repl, m.captures.toSeq()
-        i += m.matchBounds.b - m.matchBounds.a
-        break searchSubs
-      result.add s[i]
-      inc i
+      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:
-  result.add s.substr(i)
+  add(result, substr(s, i))
 
 proc transformFile*(infile, outfile: string,
                     subs: openArray[tuple[pattern: Regex, repl: string]]) =
@@ -313,42 +374,67 @@ iterator split*(s: string, sep: Regex): string =
   ## Results in:
   ##
   ## .. code-block:: nim
+  ##   ""
   ##   "this"
   ##   "is"
   ##   "an"
   ##   "example"
+  ##   ""
   ##
-  for m in nre.split(s, sep):
-    yield m
+  var
+    first = -1
+    last = -1
+  while last < len(s):
+    var x = matchLen(s, sep, last)
+    if x > 0: inc(last, x)
+    first = last
+    if x == 0: inc(last)
+    while last < len(s):
+      x = matchLen(s, sep, last)
+      if x >= 0: break
+      inc(last)
+    if first <= last:
+      yield substr(s, first, last-1)
 
 proc split*(s: string, sep: Regex): seq[string] =
   ## Splits the string `s` into substrings.
-  return nre.split(s, sep)
+  accumulateResult(split(s, sep))
 
 proc escapeRe*(s: string): string =
   ## escapes `s` so that it is matched verbatim when used as a regular
   ## expression.
-  return nre.escapeRe(s)
+  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* = r"\b[a-zA-Z_]+[a-zA-Z_0-9]*\b"  ## describes an identifier
-  reNatural* = r"\b\d+\b" ## describes a natural number
-  reInteger* = r"\b[-+]?\d+\b" ## describes an integer
-  reHex* = r"\b0[xX][0-9a-fA-F]+\b" ## describes a hexadecimal number
-  reBinary* = r"\b0[bB][01]+\b" ## describes a binary number (example: 0b11101)
-  reOctal* = r"\b0[oO][0-7]+\b" ## describes an octal number (example: 0o777)
-  reFloat* = r"\b[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?\b"
+  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|" &
-    r"net|gov|mil|biz|info|mobi|name|aero|jobs|museum)\b"
+  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"
+  reURL* {.deprecated.} = r"\b(http(s)?|ftp|gopher|telnet|file|notes|ms-help)" &
+                          r":((//)|(\\\\))+[\w\d:#@%/;$()~_?\+\-\=\\\.\&]*\b"
     ## describes an URL
 
 when isMainModule:
@@ -366,7 +452,7 @@ when isMainModule:
 
   assert find("_____abc_______", re"abc") == 5
 
-  var matches: array[0..5, string]
+  var matches: array[6, string]
   if match("abcdefg", re"c(d)ef(g)", matches, 2):
     assert matches[0] == "d"
     assert matches[1] == "g"
@@ -375,7 +461,8 @@ when isMainModule:
 
   if "abc" =~ re"(a)bcxyz|(\w+)":
     assert matches[1] == "abc"
-  else: assert false
+  else:
+    assert false
 
   if "abc" =~ re"(cba)?.*":
     assert matches[0] == nil
@@ -391,9 +478,16 @@ when isMainModule:
   assert("var1=key; var2=key2".replace(re"(\w+)=(\w+)", "$1<-$2$2") ==
          "$1<-$2$2; $1<-$2$2")
 
-  var accum: seq[string] = split("00232this02939is39an22example111", re"\d+")
+  var accum: seq[string] = @[]
+  for word in split("00232this02939is39an22example111", re"\d+"):
+    accum.add(word)
   assert(accum == @["", "this", "is", "an", "example", ""])
 
+  accum = @[]
+  for word in split("AAA :   : BBB", re"\s*:\s*"):
+    accum.add(word)
+  assert(accum == @["AAA", "", "BBB"])
+
   for x in findAll("abcdef", re"^{.}", 3):
     assert x == "d"
   accum = @[]
@@ -405,10 +499,9 @@ when isMainModule:
   assert("XYZ".match(re"^\d*") == true)
 
   block:
-    var matches: array[0..15, 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:
+    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:
         assert matches[i] == $chr(i + 'a'.ord)
     else:
       assert false