local f={}local A=assert local Z={["\040"]="\041";["\123"]="\125";["\091"]="\093"}local C={}for f,A in pairs(Z)do C[A]=f end local function O(f,Z)Z=Z or 1 local C=Z local O=f:sub(Z,Z)if O=="\""or O=="\'"then Z=Z+1 while 1 do Z=A(f:find("\091"..(O.."\092\093"),Z),"\115\121\110\116\097\120 \101\114\114\111\114")if f:sub(Z,Z)==O then local A=f:sub(C,Z)return A,Z+1 else Z=Z+2 end end else local O=f:match("\094\037\091\040\061\042\041\037\091",Z)if O then local b b,Z=f:find("\037\093"..(O.."\037\093"),Z)A(Z)local I=f:sub(C,Z)return I,Z+1 else return nil,Z end end end f.match_string=O local function b(f,b)b=b or 1 local I=b local h=f:sub(b,b)if not Z[h]then return nil,b end local L={}while 1 do b=f:find("\091\037\040\037\123\037\091\037\041\037\125\037\093\"\'\093",b)A(b,"\115\121\110\116\097\120 \101\114\114\111\114\058 \117\110\098\097\108\097\110\099\101\100")local h=f:sub(b,b)if h=="\""or h=="\'"then local Z Z,b=O(f,b)A(Z)elseif Z[h]then local Z,C if h=="\091"then Z,C=f:match("\094\037\091\040\061\042\041\037\091\040\041",b)end if Z then b=f:match("\037\093"..(Z.."\037\093\040\041"),C)A(b,"\115\121\110\116\097\120 \101\114\114\111\114\058 \108\111\110\103 \115\116\114\105\110\103 \110\111\116 \116\101\114\109\105\110\097\116\101\100")if#L==0 then local A=f:sub(I,b-1)return A,b end else L[#L+1]=h b=b+1 end else A(L[#L]==A(C[h]),"\115\121\110\116\097\120 \101\114\114\111\114\058 \117\110\098\097\108\097\110\099\101\100")L[#L]=nil if#L==0 then local A=f:sub(I,b)return A,b+1 end b=b+1 end end end f.match_bracketed=b local function I(f,A)A=A or 1 if f:sub(A,A+1)~="--"then return nil,A end A=A+2 local Z,C=O(f,A)if Z then return"--"..Z,C end local b b,A=f:match("\094\040\091\094\n\093\042\n\063\041\040\041",A)return"--"..b,A end local h={["\097\110\100"]=true,["\111\114"]=true;["\110\111\116"]=true}local L={["\062"]=true,["\060"]=true;["~"]=true}local function W(f,Z)Z=Z or 1 local C local W=Z local G local o,R while Z do local m=f:sub(Z,Z)if m=="\""or m=="\'"or m=="\091"and f:find("\094\091\061\037\091\093",Z+1)then local C C,Z=O(f,Z)A(C,"\115\121\110\116\097\120 \101\114\114\111\114")elseif m=="-"and f:sub(Z+1,Z+1)=="-"then o=Z while f:sub(Z,Z+1)=="--"do local C C,Z=I(f,Z)A(C)Z=f:match("\094\037\115\042\040\041",Z)R=Z end elseif m=="\040"or m=="\123"or m=="\091"then C,Z=b(f,Z)elseif m=="\061"and f:sub(Z+1,Z+1)=="\061"then Z=Z+2 elseif m=="\061"and L[f:sub(Z-1,Z-1)]then Z=Z+1 elseif m:match("\094\091\037\041\037\125\037\093\059\044\061\093")then local A=f:sub(W,Z-1)return A,Z elseif m:match("\094\091\037\119\095\093")then local A,C=f:match("\094\040\091\037\119\095\093\043\041\040\041",Z)if Z~=W and not h[A]then local A=(R==Z and o or Z)-1 while f:match("\094\037\115",A)do A=A-1 end local C=f:sub(A,A)if C:match("\091\037\041\037\125\'\"\037\093\093")or C:match("\091\037\119\095\093")and not h[G]then local A=f:sub(W,Z-1)return A,Z end end G,Z=A,C else Z=Z+1 end Z=f:find("\091\037\040\037\123\037\091\037\041\037\125\037\093\"\'\059\044\061\037\119\095\037-\093",Z)end local m=f:sub(W,#f)return m,#f+1 end f.match_expression=W local function G(f,A)A=A or 1 local Z={}while 1 do local C=#Z==0 and"\094"or"\094\037\115\042\044\037\115\042"local O,b=f:match(C.."\040\091\037\097\095\093\091\037\119\095\093\042\041\037\115\042\040\041",A)if O then A=b else break end Z[#Z+1]=O end return Z,A end f.match_namelist=G local function o(f,Z)Z=Z or 1 local C={}while 1 do if#C~=0 then local A=f:match("\094\037\115\042\044\037\115\042\040\041",Z)if A then Z=A else break end end local O O,Z=W(f,Z)A(O,"\115\121\110\116\097\120 \101\114\114\111\114")C[#C+1]=O end return C,Z end f.match_explist=o local function R(f,Z)local C=1 local b=1 local h=""while 1 do C=f:find("\091\037-\'\"\037\091\093",C)if not C then break end if f:match("\094\037-\037-",C)then local O=f:sub(b,C-1)if#O>0 then h=h..(Z("\101",O)or O)end local L L,C=I(f,C)h=h..(Z("\099",A(L))or L)b=C else local A=f:find("\094\091\'\"\037\091\093",C)local I if A then I,C=O(f,A)end if I then local O=f:sub(b,A-1)if#O>0 then h=h..(Z("\101",O)or O)end h=h..(Z("\115",I)or I)b=C else C=C+1 end end end local L=f:sub(b)if#L>0 then h=h..(Z("\101",L)or L)end return h end f.gsub=R return f
--- Extract delimited Lua sequences from strings.
-- Inspired by Damian Conway's Text::Balanced in Perl. <br/>
-- <ul>
--   <li>[1] <a href="http://lua-users.org/wiki/LuaBalanced">Lua Wiki Page</a></li>
--   <li>[2] http://search.cpan.org/dist/Text-Balanced/lib/Text/Balanced.pm</li>
-- </ul> <br/>
-- <pre class=example>
-- local lb = require "pl.luabalanced"
-- --Extract Lua expression starting at position 4.
--  print(lb.match_expression("if x^2 + x > 5 then print(x) end", 4))
--  --> x^2 + x > 5     16
-- --Extract Lua string starting at (default) position 1.
-- print(lb.match_string([["test\"123" .. "more"]]))
-- --> "test\"123"     12
-- </pre>
-- (c) 2008, David Manura, Licensed under the same terms as Lua (MIT license).
-- @class module
-- @name pl.luabalanced

local M = {}

local assert = assert

-- map opening brace <-> closing brace.
local ends = { ['('] = ')', ['{'] = '}', ['['] = ']' }
local begins = {}; for k,v in pairs(ends) do begins[v] = k end


-- Match Lua string in string <s> starting at position <pos>.
-- Returns <string>, <posnew>, where <string> is the matched
-- string (or nil on no match) and <posnew> is the character
-- following the match (or <pos> on no match).
-- Supports all Lua string syntax: "...", '...', [[...]], [=[...]=], etc.
local function match_string(s, pos)
  pos = pos or 1
  local posa = pos
  local c = s:sub(pos,pos)
  if c == '"' or c == "'" then
    pos = pos + 1
    while 1 do
      pos = assert(s:find("[" .. c .. "\\]", pos), 'syntax error')
      if s:sub(pos,pos) == c then
        local part = s:sub(posa, pos)
        return part, pos + 1
      else
        pos = pos + 2
      end
    end
  else
    local sc = s:match("^%[(=*)%[", pos)
    if sc then
      local _; _, pos = s:find("%]" .. sc .. "%]", pos)
      assert(pos)
      local part = s:sub(posa, pos)
      return part, pos + 1
    else
      return nil, pos
    end
  end
end
M.match_string = match_string


-- Match bracketed Lua expression, e.g. "(...)", "{...}", "[...]", "[[...]]",
-- [=[...]=], etc.
-- Function interface is similar to match_string.
local function match_bracketed(s, pos)
  pos = pos or 1
  local posa = pos
  local ca = s:sub(pos,pos)
  if not ends[ca] then
    return nil, pos
  end
  local stack = {}
  while 1 do
    pos = s:find('[%(%{%[%)%}%]\"\']', pos)
    assert(pos, 'syntax error: unbalanced')
    local c = s:sub(pos,pos)
    if c == '"' or c == "'" then
      local part; part, pos = match_string(s, pos)
      assert(part)
    elseif ends[c] then -- open
      local mid, posb
      if c == '[' then mid, posb = s:match('^%[(=*)%[()', pos) end
      if mid then
        pos = s:match('%]' .. mid .. '%]()', posb)
        assert(pos, 'syntax error: long string not terminated')
        if #stack == 0 then
          local part = s:sub(posa, pos-1)
          return part, pos
        end
      else
        stack[#stack+1] = c
        pos = pos + 1
      end
    else -- close
      assert(stack[#stack] == assert(begins[c]), 'syntax error: unbalanced')
      stack[#stack] = nil
      if #stack == 0 then
        local part = s:sub(posa, pos)
        return part, pos+1
      end
      pos = pos + 1
    end
  end
end
M.match_bracketed = match_bracketed


-- Match Lua comment, e.g. "--...\n", "--[[...]]", "--[=[...]=]", etc.
-- Function interface is similar to match_string.
local function match_comment(s, pos)
  pos = pos or 1
  if s:sub(pos, pos+1) ~= '--' then
    return nil, pos
  end
  pos = pos + 2
  local partt, post = match_string(s, pos)
  if partt then
    return '--' .. partt, post
  end
  local part; part, pos = s:match('^([^\n]*\n?)()', pos)
  return '--' .. part, pos
end


-- Match Lua expression, e.g. "a + b * c[e]".
-- Function interface is similar to match_string.
local wordop = {['and']=true, ['or']=true, ['not']=true}
local is_compare = {['>']=true, ['<']=true, ['~']=true}
local function match_expression(s, pos)
  pos = pos or 1
  local _
  local posa = pos
  local lastident
  local poscs, posce
  while pos do
    local c = s:sub(pos,pos)
    if c == '"' or c == "'" or c == '[' and s:find('^[=%[]', pos+1) then
      local part; part, pos = match_string(s, pos)
      assert(part, 'syntax error')
    elseif c == '-' and s:sub(pos+1,pos+1) == '-' then
      -- note: handle adjacent comments in loop to properly support
      -- backtracing (poscs/posce).
      poscs = pos
      while s:sub(pos,pos+1) == '--' do
        local part; part, pos = match_comment(s, pos)
        assert(part)
        pos = s:match('^%s*()', pos)
        posce = pos
      end
    elseif c == '(' or c == '{' or c == '[' then
      _, pos = match_bracketed(s, pos)
    elseif c == '=' and s:sub(pos+1,pos+1) == '=' then
      pos = pos + 2  -- skip over two-char op containing '='
    elseif c == '=' and is_compare[s:sub(pos-1,pos-1)] then
      pos = pos + 1  -- skip over two-char op containing '='
    elseif c:match'^[%)%}%];,=]' then
      local part = s:sub(posa, pos-1)
      return part, pos
    elseif c:match'^[%w_]' then
      local newident,newpos = s:match('^([%w_]+)()', pos)
      if pos ~= posa and not wordop[newident] then -- non-first ident
        local pose = ((posce == pos) and poscs or pos) - 1
        while s:match('^%s', pose) do pose = pose - 1 end
        local ce = s:sub(pose,pose)
        if ce:match'[%)%}\'\"%]]' or
           ce:match'[%w_]' and not wordop[lastident]
        then
          local part = s:sub(posa, pos-1)
          return part, pos
        end
      end
      lastident, pos = newident, newpos
    else
      pos = pos + 1
    end
    pos = s:find('[%(%{%[%)%}%]\"\';,=%w_%-]', pos)
  end
  local part = s:sub(posa, #s)
  return part, #s+1
end
M.match_expression = match_expression


-- Match name list (zero or more names).  E.g. "a,b,c"
-- Function interface is similar to match_string,
-- but returns array as match.
local function match_namelist(s, pos)
  pos = pos or 1
  local list = {}
  while 1 do
    local c = #list == 0 and '^' or '^%s*,%s*'
    local item, post = s:match(c .. '([%a_][%w_]*)%s*()', pos)
    if item then pos = post else break end
    list[#list+1] = item
  end
  return list, pos
end
M.match_namelist = match_namelist


-- Match expression list (zero or more expressions).  E.g. "a+b,b*c".
-- Function interface is similar to match_string,
-- but returns array as match.
local function match_explist(s, pos)
  pos = pos or 1
  local list = {}
  while 1 do
    if #list ~= 0 then
      local post = s:match('^%s*,%s*()', pos)
      if post then pos = post else break end
    end
    local item; item, pos = match_expression(s, pos)
    assert(item, 'syntax error')
    list[#list+1] = item
  end
  return list, pos
end
M.match_explist = match_explist


-- Replace snippets of code in Lua code string <s>
-- using replacement function f(u,sin) --> sout.
-- <u> is the type of snippet ('c' = comment, 's' = string,
-- 'e' = any other code).
-- Snippet is replaced with <sout> (unless <sout> is nil or false, in
-- which case the original snippet is kept)
-- This is somewhat analogous to string.gsub .
local function gsub(s, f)
  local pos = 1
  local posa = 1
  local sret = ''
  while 1 do
    pos = s:find('[%-\'\"%[]', pos)
    if not pos then break end
    if s:match('^%-%-', pos) then
      local exp = s:sub(posa, pos-1)
      if #exp > 0 then sret = sret .. (f('e', exp) or exp) end
      local comment; comment, pos = match_comment(s, pos)
      sret = sret .. (f('c', assert(comment)) or comment)
      posa = pos
    else
      local posb = s:find('^[\'\"%[]', pos)
      local str
      if posb then str, pos = match_string(s, posb) end
      if str then
        local exp = s:sub(posa, posb-1)
        if #exp > 0 then sret = sret .. (f('e', exp) or exp) end
        sret = sret .. (f('s', str) or str)
        posa = pos
      else
        pos = pos + 1
      end
    end
  end
  local exp = s:sub(posa)
  if #exp > 0 then sret = sret .. (f('e', exp) or exp) end
  return sret
end
M.gsub = gsub


return M
