patlua/pat.lua

--[========================================================================[--

Lua pattern matching library (minus string.gsub) ported to Lua.

Copyright © 1994–2018 Lua.org, PUC-Rio.
Copyright © 2019 Pedro Gimeno Fortea.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

--]========================================================================]--

local LUA_MAXCAPTURES = 32

local CAP_UNFINISHED = -1
local CAP_POSITION = -2

local L_ESC = 37 -- 37='%'
-- only used for string.find(x, y, z, true)
-- local SPECIALS = '^$*+?.([%-'

local function LUA_QL(x)
    return "'" .. x .. "'"
end

local function check_capture(ms, l)
  l = l - 48 -- 48='0'
  if l < 1 or l > ms.level or ms.capture[l].len == CAP_UNFINISHED then
    return error("invalid capture index")
  end
  return l
end

local function capture_to_close(ms)
  local level = ms.level
  while level > 0 do
    if ms.capture[level].len == CAP_UNFINISHED then
      return level
    end
    level = level - 1
  end
  return error("invalid pattern capture")
end

local function classend(pat, p)
  local cc = pat:byte(p)
  p = p + 1
  if cc == L_ESC then
    if (pat:byte(p) or 0) == 0 then
      return error("malformed pattern (ends with " .. LUA_QL('%') .. ")")
    end
    return p + 1
  end
  if cc == 91 then -- 91='['
    if pat:byte(p) == 94 then -- 94='^'
      p = p + 1
    end
    repeat -- look for a `]'
      cc = pat:byte(p) or 0
      p = p + 1
      if cc == 0 then
        return error("malformed pattern (missing " .. LUA_QL(']') .. ")")
      end
      if cc == L_ESC then
        if (pat:byte(p) or 0) ~= 0 then
          p = p + 1
        end
      end
    until pat:byte(p) == 93 -- 93=']'
    return p + 1
  end
  return p
end

local function match_class(c, cl)
  local u = cl - cl % 64 + cl % 32 -- upper case
  local negate = cl == u -- true if uppercase
  local res
  if u == 65 then -- 65='A'
    res = c >= 65 and c <= 90 or c >= 97 and c <= 122 -- 65='A', 90='Z', 97='a', 122='z'
  elseif u == 67 then -- 67='C'
    res = c < 32 or c == 127
  elseif u == 68 then -- 68='D'
    res = c >= 48 and c <= 57 -- 48='0', 57='9'
  elseif u == 76 then -- 76='L'
    res = c >= 97 and c <= 122 -- 97='a', 122='z'
  elseif u == 80 then -- 80='P'
    res = c >= 33 and c <= 47 or c >= 58 and c <= 64
       or c >= 91 and c <= 96 or c >= 123 and c <= 126
  elseif u == 83 then -- 83='S'
    res = c == 9 or c >= 10 and c <= 13 or c == 32 -- 9=HT, 10=LF, 13=CR, 32=' '
  elseif u == 85 then -- 85='U'
    res = c >= 65 and c <= 90
  elseif u == 87 then -- 87='W'
    res = c >= 65 and c <= 90 or c >= 97 and c <= 122 -- 65='A', 90='Z', 97='a', 122='z'
       or c >= 48 and c <= 57 -- 48='0', 57='9'
  elseif u == 88 then -- 88='X'
    res = c >= 65 and c <= 70 or c >= 97 and c <= 102 -- 65='A', 70='F', 97='a', 102='f'
       or c >= 48 and c <= 57 -- 48='0', 57='9'
  elseif u == 90 then
    res = c == 0
  else
    return c == cl
  end
  return negate ~= res
end

local function matchbracketclass(c, pat, p, ec)
  local sig = true
  p = p + 1
  if pat:byte(p) == 94 then -- 94='^'
    sig = false
    p = p + 1
  end
  while p < ec do
    local cc = pat:byte(p)
    if cc == L_ESC then
      p = p + 1
      if match_class(c, pat:byte(p)) then
        return sig
      end
    elseif pat:byte(p + 1) == 45 and p + 2 < ec then -- 45='-'
      p = p + 2
      if cc <= c and c <= pat:byte(p) then
        return sig
      end
    elseif cc == c then
      return sig
    end
    p = p + 1
  end
  return not sig
end

local function singlematch(c, pat, p, ep)
  local cc = pat:byte(p)
  if cc == 46 then -- 46='.'
    return true
  end
  if cc == L_ESC then
    return match_class(c, pat:byte(p + 1))
  end
  if cc == 91 then -- 91='['
    return matchbracketclass(c, pat, p, ep - 1)
  end
  return cc == c
end

local match

local function matchbalance(ms, str, s, pat, p)
  local b = pat:byte(p)
  local e = pat:byte(p + 1)
  if (b or 0) == 0 or (e or 0) == 0 then
    return error("unbalanced pattern")
  end
  if str:byte(s) ~= b then
    return false
  end
  local cont = 1
  s = s + 1
  while s < ms.src_end do
    local cc = str:byte(s)
    if cc == e then
      cont = cont - 1
      if cont == 0 then
        return s + 1
      end
    elseif cc == b then
      cont = cont + 1
    end
    s = s + 1
  end
  return false
end

local function max_expand(ms, str, s, pat, p, ep)
  local i = 0 -- counts maximum expand for item
  while s + i < ms.src_end and singlematch(str:byte(s + i), pat, p, ep) do
    i = i + 1
  end
  while i >= 0 do
    local res = match(ms, str, s + i, pat, ep + 1)
    if res then return res end
    i = i - 1 -- else it didn't match; reduce 1 repetition to try again
  end
  return false
end

local function min_expand(ms, str, s, pat, p, ep)
  repeat
    local res = match(ms, str, s, pat, ep + 1)
    if res then
      return res
    end
    if s >= ms.src_end or not singlematch(str:byte(s), pat, p, ep) then
      return false
    end
    s = s + 1
  until false
end

local function start_capture(ms, str, s, pat, p, what)
  local level = ms.level + 1
  if level > LUA_MAXCAPTURES then
    return error("too many captures")
  end
  if not ms.capture[level] then
    ms.capture[level] = {}
  end
  ms.capture[level].init = s
  ms.capture[level].len = what
  ms.level = level
  local res = match(ms, str, s, pat, p)
  if not res then
    ms.level = ms.level - 1
  end
  return res
end

local function end_capture(ms, str, s, pat, p)
  local l = capture_to_close(ms)
  ms.capture[l].len = s - ms.capture[l].init
  local res = match(ms, str, s, pat, p)
  if not res then
    ms.capture[l].len = CAP_UNFINISHED
  end
  return res
end

local function substrcomp(str, start1, start2, len)
  for i = start1, start1 + len - 1 do
    if str:byte(i) ~= str:byte(i + (start2 - start1)) then
      return false
    end
  end
  return true
end

local function match_capture(ms, str, s, l)
  l = check_capture(ms, l)
  local len = ms.capture[l].len
  if ms.src_end - s >= len and substrcomp(str, ms.capture[l].init, s, len) then
    return s + len
  end
  return false
end

-- this is local already, don't add 'local' or it will fail
match = function (ms, str, s, pat, p)
  local cc = pat:byte(p) or 0
  if cc == 40 then -- 40='('
    -- start capture
    if pat:byte(p + 1) == 41 then -- 41=')'
      -- position capture
      return start_capture(ms, str, s, pat, p + 2, CAP_POSITION)
    end
    return start_capture(ms, str, s, pat, p + 1, CAP_UNFINISHED)
  end
  if cc == 41 then -- 41=')'
    -- end capture
    return end_capture(ms, str, s, pat, p + 1)
  end
  if cc == L_ESC then
    cc = pat:byte(p + 1)
    if cc == 98 then -- 98='b'
      -- balanced string
      s = matchbalance(ms, str, s, pat, p + 2)
      if not s then
        return false
      end
      return match(ms, str, s, pat, p + 4)
    end
    if cc == 102 then -- 102='f'
      -- frontier
      p = p + 2
      if pat:byte(p) ~= 91 then -- 91='['
        return error("missing " .. LUA_QL('[') .. " after "
                     .. LUA_QL('%f') .. " in pattern")
      end
      local ep = classend(pat, p)
      local previous = str:byte(s - 1) or 0
      if matchbracketclass(previous, pat, p, ep - 1)
        or not matchbracketclass(str:byte(s) or 0, pat, p, ep - 1)
      then
        return false
      end
      return match(ms, str, s, pat, ep)
    end
    if cc >= 48 and cc <= 57 then -- 48='0', 57='9'
      -- capture results (%0-%9)?
      s = match_capture(ms, str, s, cc)
      if not s then
        return false
      end
      return match(ms, str, s, pat, p + 2)
    end
    cc = -1 -- don't match anything else until default
  end
  if cc == 0 then -- end of pattern
    return s
  end
  if cc == 36 then -- 36='$'
    if (pat:byte(p + 1) or 0) == 0 then -- is the `$' the last char in pattern?
      return s == ms.src_end and s -- check end of string
    end
    -- else fall through to default
  end

  -- default
  local ep = classend(pat, p)
  local m = s < ms.src_end and singlematch(str:byte(s), pat, p, ep)
  cc = pat:byte(ep) or 0
  if cc == 63 then
    if m then
      local res = match(ms, str, s + 1, pat, ep + 1)
      if res then
        return res
      end
    end
    return match(ms, str, s, pat, ep + 1)
  end
  if cc == 42 then -- 42='*'
    -- 0 or more repetitions
    return max_expand(ms, str, s, pat, p, ep)
  end
  if cc == 43 then -- 43='+'
    -- 1 or more repetitions
    return m and max_expand(ms, str, s + 1, pat, p, ep)
  end
  if cc == 45 then -- 45='-'
    -- 0 or more repetitions (minimum)
    return min_expand(ms, str, s, pat, p, ep)
  end
  return m and match(ms, str, s + 1, pat, ep)
end

-- lmemfind not implemented - only used for string.find(x, y, z, true)

local function push_onecapture(ms, i, str, s, e)
  if i > ms.level then
    if i ~= 1 then
      return error("invalid capture index")
    end
    ms.captures[#ms.captures + 1] = str:sub(s, e - 1)
  else
    local l = ms.capture[i].len
    if l == CAP_UNFINISHED then
      return error("unfinished capture")
    end
    if l == CAP_POSITION then
      ms.captures[#ms.captures + 1] = ms.capture[i].init
    else
      ms.captures[#ms.captures + 1] = str:sub(ms.capture[i].init, ms.capture[i].init + l - 1)
    end
  end
end

local function push_captures(ms, str, s, e)
  local nlevels = ms.level
  if nlevels == 0 and s then
    nlevels = 1
  end
  for i = 1, nlevels do
    push_onecapture(ms, i, str, s, e)
  end
end

local function posrelat(pos, len)
  if pos < 0 then pos = pos + len + 1 end
  return pos >= 1 and pos or 1
end

local string_find = string.find

local SPECIALS = { [("^"):byte(1)]=true, [("$"):byte(1)]=true,
                   [("*"):byte(1)]=true, [("+"):byte(1)]=true,
                   [("?"):byte(1)]=true, [("."):byte(1)]=true,
                   [("("):byte(1)]=true, [("["):byte(1)]=true,
                   [("%"):byte(1)]=true, [("-"):byte(1)]=true,
                   [0] = true }

local function specials_free(s)
  for i = 1, #s do
    if SPECIALS[s:byte(i)] then
      if s:byte(i) == 0 then
        return true -- stop at first NUL
      end
      return false
    end
  end
  return true
end

local function str_find_aux(find, str, pat, init, explicit)
  local l1 = #str
  init = posrelat(init or 1, l1)
  if init < 1 then
    init = 1
  elseif init > l1 + 1 then
    init = l1 + 1
  end
  if find and (explicit or specials_free(pat)) then -- explicit request?
    -- do a plain search
    return string_find(str, pat, init, true)
  end
  local p = 1
  local anchor = false
  if pat:byte(1) == 94 then -- 94='^'
    p = p + 1
    anchor = true
  end
  local s1 = init
  local ms = {captures = {}, capture = {}, src_end = l1 + 1}
  repeat
    ms.level = 0
    local res = match(ms, str, s1, pat, p)
    if res then
      if find then
        push_captures(ms, str, false, 0)
        return s1, res - 1, unpack(ms.captures)
      end
      push_captures(ms, str, s1, res)
      return unpack(ms.captures)
    end
    s1 = s1 + 1
  until anchor or s1 > ms.src_end
  return nil
end

local function str_find(str, pat, init, explicit)
  return str_find_aux(true, str, pat, init, explicit)
end

local function str_match(str, pat, init)
  return str_find_aux(false, str, pat, init)
end

local function gmatch(str, pat)
  local init = 1
  local ms = {captures = {}, capture = {}, src_init = str, src_end = #str + 1}
  local function gmatch_aux()
    for i = 1, #ms.captures do ms.captures[i] = nil end
    for src = init, ms.src_end do
      ms.level = 0
      local e = match(ms, str, src, pat, 1)
      if e then
        local newstart = e
        if e == src then newstart = newstart + 1 end -- empty match? go at least one position
        init = newstart
        push_captures(ms, str, src, e)
        return unpack(ms.captures)
      end
    end
  end
  return gmatch_aux
end

return { find = str_find, match = str_match, gmatch = gmatch, gfind = gmatch }