local W=require("\112\108\046\117\116\105\108\115")local h=W.split local K=table.insert local Q=table.concat local N=table.remove local y=string.match local X=tostring local A=setmetatable local k=getmetatable local Y=pairs local j=ipairs local F=type local G=next local n=print local I=W.unpack local r=string.gsub local s=string.sub local H=string.find local l=pcall local u=require W.raise_deprecation({source="\080\101\110\108\105\103\104\116 "..W._VERSION;message="\116\104\101 \099\111\110\116\101\110\116\115 \111\102 \109\111\100\117\108\101 \'\112\108\046\120\109\108\' \104\097\115 \098\101\101\110 \100\101\112\114\101\099\097\116\101\100\044 \112\108\101\097\115\101 \117\115\101 \097 \109\111\114\101 \115\112\101\099\105\097\108\105\122\101\100 \108\105\098\114\097\114\121 \105\110\115\116\101\097\100";version_removed="\050\046\048\046\048";deprecated_after="\049\046\049\049\046\048";no_trace=true})local x={}local p={__type="\100\111\099"}p.__index=p local function V(W)return F(W)=="\115\116\114\105\110\103"end local function f(W)return F(W)=="\116\097\098\108\101"and V(W.tag)end function x.new(W,h)if F(W)~="\115\116\114\105\110\103"then error("\101\120\112\101\099\116\101\100 \'\116\097\103\' \116\111 \098\101 \097 \115\116\114\105\110\103 \118\097\108\117\101\044 \103\111\116\058 "..F(W),2)end h=h or{}if F(h)~="\116\097\098\108\101"then error("\101\120\112\101\099\116\101\100 \'\097\116\116\114\' \116\111 \098\101 \097 \116\097\098\108\101 \118\097\108\117\101\044 \103\111\116\058 "..F(h),2)end local K={tag=W;attr=h,last_add={}}return A(K,p)end function x.parse(h,K,Q)local N,y,X if Q then N=x.basic_parse else y,X=l(u,"\108\120\112\046\108\111\109")if not y then N=x.basic_parse else N=X.parse end end if K then local K,Q=W.readfile(h)if not K then return nil,Q end h=K end local k,Y=N(h)if not k then return nil,Y end if X then x.walk(k,false,function(W,h)A(h,p)end)end return k end function x.elem(W,h)local Q=x.new(W)if V(h)then h={h}end if f(h)then K(Q,h)elseif F(h)=="\116\097\098\108\101"then for W,h in Y(h)do if V(W)then Q.attr[W]=h K(Q.attr,W)else Q[W]=h end end end return Q end function x.tags(W)local K={}if V(W)then W=h(W:match("\094\037\115\042\040\046-\041\037\115\042\036"),"\037\115\042\044\037\115\042")end for W,h in j(W)do local function Q(W)return x.elem(h,W)end K[W]=Q end return I(K)end function p.addtag(Q,W,h)local N=x.new(W,h)Q:add_child(N)K(Q.last_add,N)return Q end function p.text(h,W)h:add_child(W)return h end function p.up(W)N(W.last_add)return W end function p.reset(W)local h=W.last_add for W=1,#h,1 do h[W]=nil end return W end function p.add_direct_child(h,W)K(h,W)return h end function p.add_child(h,W)(h.last_add[#h.last_add]or h):add_direct_child(W)return h end function p.set_attribs(h,W)for W,K in Y(W)do h.attr[W]=K end return h end function p.set_attrib(K,W,h)K.attr[W]=h return K end function p.get_attribs(W)return W.attr end local E do local W={}function E(h)if V(h)then if W[h]then return W[h]else local K,Q=x.parse(h,false,true)if not K then return nil,Q end W[h]=K return K end end if f(h)then return h end return nil,"\116\101\109\112\108\097\116\101 \105\115 \110\111\116 \097 \100\111\099\117\109\101\110\116"end end do local function W(W)return#W==0 or F(W[1])~="\116\097\098\108\101"end local function h(W)for h,K in j(W)do W[X(h)]=K end end function p.subst(Q,N)if F(N)~="\116\097\098\108\101"or not G(N)then return nil,"\100\097\116\097 \109\117\115\116 \098\101 \097 \110\111\110-\101\109\112\116\121 \116\097\098\108\101"end if W(N)then h(N)end local y,X=E(Q)if X then return nil,X end local function A(W)return x.clone(y,function(h)return h:gsub("\037\036\040\037\119\043\041",W)end)end if W(N)then return A(N)end local k={}for W,Q in j(N)do h(Q)K(k,A(Q))end if N.tag then k=x.elem(N.tag,k)end return k end end function p.child_with_name(h,W)for h,K in j(h)do if K.tag==W then return K end end end do local function W(h,Q,N,y)for h,X in j(h)do if F(X)=="\116\097\098\108\101"then if X.tag==Q then K(N,X)end if y then W(X,Q,N,y)end end end end function p.get_elements_with_name(Q,h,K)local N={}W(Q,h,N,not K)return N end end function p.children(W)local h=0 return function(W)h=h+1 return W[h]end,W,h end function p.first_childtag(W)if#W==0 then return end for W,h in j(W)do if f(h)then return h end end end function p.matching_tags(K,W,h)h=h or K.attr.xmlns local Q=K local N=1 local y=#Q local X return function()for K=N,y,1 do X=Q[K]if(not W or X.tag==W)and(not h or h==X.attr.xmlns)then N=K+1 return X end end end,Q,N end function p.childtags(W)local h=0 return function(K)local Q repeat h=h+1 Q=W[h]if Q and F(Q)=="\116\097\098\108\101"then return Q end until not Q end,W[1],h end function p.maptags(h,W)local K=1 while K<=#h do if f(h[K])then local Q=W(h[K])if Q==nil then N(h,K)else h[K]=Q K=K+1 end else K=K+1 end end return h end do local W={["\'"]="\038\097\112\111\115\059",["\""]="\038\113\117\111\116\059",["\060"]="\038\108\116\059",["\062"]="\038\103\116\059";["\038"]="\038\097\109\112\059"}function x.xml_escape(h)return r(h,"\091\'\038\060\062\"\093",W)end end local O=x.xml_escape do local W={quot="\"",apos="\'",lt="\060";gt="\062",amp="\038"}function x.xml_unescape(h)return h:gsub("\038\040\037\097\043\041\059",W)end end local g=x.xml_unescape local function D(W,h,Q,N,X,A)local k=0 local F=W.tag local G=""if X then G="\n"..N end local n=" "if A then n="\n"..(N..A)end K(h,G..("\060"..F))local function I(W,N)if H(W,"\001",1,true)then k=k+1 local Q,X=y(W,"\094\040\091\094\001\093\042\041\001\063\040\046\042\041\036")K(h," \120\109\108\110\115\058\110\115"..(k..("\061\'"..(O(Q)..("\' "..("\110\115"..(k..("\058"..(X..("\061\'"..(O(N).."\'")))))))))))elseif not(W=="\120\109\108\110\115"and N==Q)then K(h,n..(W..("\061\'"..(O(N).."\'"))))end end if#W.attr>0 then for h,K in j(W.attr)do I(K,W.attr[K])end else for W,h in Y(W.attr)do I(W,h)end end local r=#W local s if r==0 then K(h,A and"\n"..(N.."\047\062")or"\047\062")else K(h,"\062")for Q=1,r,1 do local y=W[Q]if y.tag then s=true D(y,h,W.attr.xmlns,N and N..X,X,A)else K(h,O(y))end end K(h,(s and G or"")..("\060\047"..(F.."\062")))end end function x.tostring(W,h,K,N,y)local X={}if F(h)=="\110\117\109\098\101\114"then h=(" "):rep(h)end if F(K)=="\110\117\109\098\101\114"then K=(" "):rep(K)end if F(N)=="\110\117\109\098\101\114"then N=(" "):rep(N)end if y then if F(y)=="\115\116\114\105\110\103"then X[1]=y else X[1]="\060\063\120\109\108 \118\101\114\115\105\111\110\061\'\049\046\048\'\063\062"end end D(W,X,nil,h,K,N,y)return Q(X)end p.__tostring=x.tostring function p.tostring(N,W,h,K,Q)return x.tostring(N,W,h,K,Q)end function p.get_text(W)local h={}for W,Q in j(W)do if V(Q)then K(h,Q)end end return Q(h)end do local function W(h,Q,N,y,X)if F(h)~="\116\097\098\108\101"then if y and V(h)then return y(h,Q,N)else return h end end if X[h]then error("\114\101\099\117\114\115\105\111\110 \100\101\116\101\099\116\101\100")end X[h]=true local j={}X[h]=j local G=h.tag j.tag=W(G,"\042\084\065\071",N,y,X)if h.attr then local K={}for Q,N in Y(h.attr)do if F(Q)=="\115\116\114\105\110\103"then K[Q]=W(N,Q,h,y,X)end end j.attr=K end for Q=1,#h,1 do local N=W(h[Q],"\042\084\069\088\084",h,y,X)K(j,N)end return A(j,k(h))end function x.clone(h,K)return W(h,nil,nil,K,{})end end p.filter=x.clone do local function W(h,K,Q)local N=F(h)local y=F(K)if N~=y then return false,"\116\121\112\101 \109\105\115\109\097\116\099\104"end if N=="\115\116\114\105\110\103"then if h==K then return true else return false,"\116\101\120\116 "..(h..(" ~\061 \116\101\120\116 "..K))end end if N~="\116\097\098\108\101"or y~="\116\097\098\108\101"then return false,"\110\111\116 \097 \100\111\099\117\109\101\110\116"end if Q[h]then return false,"\114\101\099\117\114\115\105\118\101 \100\111\099\117\109\101\110\116"end Q[h]=true if h.tag~=K.tag then return false,"\116\097\103  "..(h.tag..(" ~\061 \116\097\103 "..K.tag))end if#h~=#K then return false,"\115\105\122\101 "..(#h..(" ~\061 \115\105\122\101 "..(#K..(" \102\111\114 \116\097\103 "..h.tag))))end for W,h in Y(h.attr)do local Q=K.attr[W]if F(W)=="\115\116\114\105\110\103"then if Q~=h then return false,"\109\105\115\109\097\116\099\104 \097\116\116\114\105\098"end else if Q~=nil and Q~=h then return false,"\109\105\115\109\097\116\099\104 \097\116\116\114\105\098 \111\114\100\101\114"end end end for W,K in Y(K.attr)do local Q=h.attr[W]if F(W)=="\115\116\114\105\110\103"then if Q~=K then return false,"\109\105\115\109\097\116\099\104 \097\116\116\114\105\098"end else if Q~=nil and Q~=K then return false,"\109\105\115\109\097\116\099\104 \097\116\116\114\105\098 \111\114\100\101\114"end end end for N=1,#h,1 do local y,X=W(h[N],K[N],Q)if not y then return y,X end end return true end function x.compare(h,K)return W(h,K,{})end end x.is_tag=f do local function W(h,K,Q,N)if not K then Q(h.tag,h)end for h,y in j(h)do if f(y)then assert(not N[y],"\114\101\099\117\114\115\105\111\110 \100\101\116\101\099\116\101\100")N[y]=true W(y,K,Q,N)end end if K then Q(h.tag,h)end end function x.walk(h,K,Q)return W(h,K,Q,{})end end local q={br=true;img=true;meta=true,frame=true;area=true,hr=true;base=true;col=true,link=true,input=true,option=true,param=true,isindex=true,embed=true}function x.parsehtml(W)return x.basic_parse(W,false,true)end function x.basic_parse(W,h,Q)local y={}local X={}local function k(W)local h={}W:gsub("\040\091\037\119\058\037-\095\093\043\041\037\115\042\061\037\115\042\040\091\"\'\093\041\040\046-\041\037\050",function(W,K,N)if Q then W=W:lower()end h[W]=g(N)end)if Q then W:gsub("\040\091\037\119\058\037-\095\093\043\041\037\115\042\061\037\115\042\040\091\094\"\'\093\043\041\037\115\042",function(W,K)W=W:lower()h[W]=g(K)end)end return h end K(y,X)local Y,j,F,G,n,I,r local l=1 local u I,r=H(W,"\094\037\115\042\060\037\063\091\094\037\063\093\043\037\063\062\037\115\042")if not r then I,r=H(W,"\094\037\115\042\060\033\068\079\067\084\089\080\069\046-\062\037\115\042")end if r then l=r+1 end while true do Y,u,j,F,G,n=H(W,"\060\040\091\037\047\033\093\063\041\040\091\037\119\058\037-\095\093\043\041\040\046-\041\040\037\047\063\041\062",l)if not Y then break end if j=="\033"then if not(F:match("\037-\037-\036")and G=="")then if G:match("\037-\037-\036")then u=u-2 end I,u=H(W,"--\062",u,true)end else local I=s(W,l,Y-1)if Q then F=F:lower()if q[F]then n="\047"end end if h or not H(I,"\094\037\115\042\036")then K(X,g(I))end if n=="\047"then K(X,A({tag=F;attr=k(G),empty=1},p))elseif j==""then X=A({tag=F;attr=k(G)},p)K(y,X)else local W=N(y)X=y[#y]if#y<1 then error("\110\111\116\104\105\110\103 \116\111 \099\108\111\115\101 \119\105\116\104 "..(F..("\058"..I)))end if W.tag~=F then error("\116\114\121\105\110\103 \116\111 \099\108\111\115\101 "..(W.tag..(" \119\105\116\104 "..(F..(" "..I)))))end K(X,W)end end l=u+1 end local x=s(W,l)if h or not H(x,"\094\037\115\042\036")then K(y[#y],g(x))end if#y>1 then error("\117\110\099\108\111\115\101\100 "..y[#y].tag)end local f=y[1]return V(f[1])and f[2]or f[1]end do local W do local function h(W)return not W or not G(W)end local Q do local function W(W)local h,K=G(W)if G(W,h)~=nil then return false end return h,K end function Q(Q,N)if not h(N)then local y if N._ then y=N._ N._=nil if h(N)then return end end local X,A=W(N)if X==0 then N=A end if y then Q[y]=N else K(Q,N)end end end end local function N(W)if W:find("\094\037\100\043\036")then W=tonumber(W)end return W end local function y(W,h,K)h=N(h:sub(2))W[h]=K return true end function W(K,X,A,k)local j=true if K==nil then K=""end if V(K)then if not V(X)then return false end if x.debug then n(K,X)end if X:find("\094\037\036")then return y(A,X,K)else return K==X end else if x.debug then n(K.tag,X.tag)end local y=X.tag:match("\094\040\046-\041\037-\036")if y then y=N(y)A[y]=K.tag end if K.tag==X.tag or y then if not h(X.attr)then if h(K.attr)then j=false else for h,Q in Y(X.attr)do local N=K.attr[h]if not W(N,Q,A)then j=false break end end end end if j and#X>0 then local h,N=1,1 local function y()N=N+1 if V(K[N])then N=N+1 end return N<=#K end repeat local k=X[h]if f(k)and k.repeated then local X repeat local h={}j=W(K[N],k,h,false)if j then X=false Q(A,h)end until not y()or X and not j h=h+1 else j=W(K[N],k,A,false)if j then h=h+1 end end until not y()or h>#X if h>#X then return true end end if j then return true end else j=false end if k then for h in K:childtags()do j=W(h,X,A,k)if j then break end end end end return j end end function p.match(K,h)local Q h,Q=E(h)if not h then return nil,Q end x.walk(h,false,function(W,h)if V(h[1])and(f(h[2])and(V(h[3])and(h[1]:find("\037\115\042\123\123")and h[3]:find("\125\125\037\115\042"))))then N(h,1)N(h,2)h[1].repeated=true end end)local y={}local X=W(K,h,y,true)return y,X end end return x
--- XML LOM Utilities.
--
-- This implements some useful things on [LOM](http://matthewwild.co.uk/projects/luaexpat/lom.html) documents, such as returned by `lxp.lom.parse`.
-- In particular, it can convert LOM back into XML text, with optional pretty-printing control.
-- It is based on stanza.lua from [Prosody](http://hg.prosody.im/trunk/file/4621c92d2368/util/stanza.lua)
--
--     > d = xml.parse "<nodes><node id='1'>alice</node></nodes>"
--     > = d
--     <nodes><node id='1'>alice</node></nodes>
--     > = xml.tostring(d,'','  ')
--     <nodes>
--        <node id='1'>alice</node>
--     </nodes>
--
-- Can be used as a lightweight one-stop-shop for simple XML processing; a simple XML parser is included
-- but the default is to use `lxp.lom` if it can be found.
-- <pre>
-- Prosody IM
-- Copyright (C) 2008-2010 Matthew Wild
-- Copyright (C) 2008-2010 Waqas Hussain--
-- classic Lua XML parser by Roberto Ierusalimschy.
-- modified to output LOM format.
-- http://lua-users.org/wiki/LuaXml
-- </pre>
-- See @{06-data.md.XML|the Guide}
--
-- Dependencies: `pl.utils`
--
-- Soft Dependencies: `lxp.lom` (fallback is to use basic Lua parser)
-- @module pl.xml

local utils = require 'pl.utils'
local split         =   utils.split
local t_insert      =  table.insert
local t_concat      =  table.concat
local t_remove      =  table.remove
local s_match       =  string.match
local tostring      =      tostring
local setmetatable  =  setmetatable
local getmetatable  =  getmetatable
local pairs         =         pairs
local ipairs        =        ipairs
local type          =          type
local next          =          next
local print         =         print
local unpack        =  utils.unpack
local s_gsub        =   string.gsub
local s_sub         =    string.sub
local s_find        =   string.find
local pcall         =         pcall
local require       =       require


utils.raise_deprecation {
  source = "Penlight " .. utils._VERSION,
  message = "the contents of module 'pl.xml' has been deprecated, please use a more specialized library instead",
  version_removed = "2.0.0",
  deprecated_after = "1.11.0",
  no_trace = true,
}



local _M = {}
local Doc = { __type = "doc" };
Doc.__index = Doc;


local function is_text(s) return type(s) == 'string' end
local function is_tag(d) return type(d) == 'table' and is_text(d.tag) end



--- create a new document node.
-- @tparam string tag the tag name
-- @tparam[opt={}] table attr attributes (table of name-value pairs)
-- @return the Node object
-- @see xml.elem
-- @usage
-- local doc = xml.new("main", { hello = "world", answer = "42" })
-- print(doc)  -->  <main hello='world' answer='42'/>
function _M.new(tag, attr)
  if type(tag) ~= "string" then
    error("expected 'tag' to be a string value, got: " .. type(tag), 2)
  end
  attr = attr or {}
  if type(attr) ~= "table" then
    error("expected 'attr' to be a table value, got: " .. type(attr), 2)
  end

  local doc = { tag = tag, attr = attr, last_add = {}};
  return setmetatable(doc, Doc);
end


--- parse an XML document. By default, this uses lxp.lom.parse, but
-- falls back to basic_parse, or if `use_basic` is truthy
-- @param text_or_filename  file or string representation
-- @param is_file whether text_or_file is a file name or not
-- @param use_basic do a basic parse
-- @return a parsed LOM document with the document metatatables set
-- @return nil, error the error can either be a file error or a parse error
function _M.parse(text_or_filename, is_file, use_basic)
  local parser,status,lom
  if use_basic then
    parser = _M.basic_parse
  else
    status,lom = pcall(require,'lxp.lom')
    if not status then
      parser = _M.basic_parse
    else
      parser = lom.parse
    end
  end

  if is_file then
    local text, err = utils.readfile(text_or_filename)
    if not text then
      return nil, err
    end
    text_or_filename = text
  end

  local doc, err = parser(text_or_filename)
  if not doc then
    return nil, err
  end

  if lom then
    _M.walk(doc, false, function(_, d)
      setmetatable(d, Doc)
    end)
  end
  return doc
end


--- Create a Node with a set of children (text or Nodes) and attributes.
-- @tparam string tag a tag name
-- @tparam table|string items either a single child (text or Node), or a table where the hash
-- part is the attributes and the list part is the children (text or Nodes).
-- @return the new Node
-- @see xml.new
-- @see xml.tags
-- @usage
-- local doc = xml.elem("top", "hello world")                -- <top>hello world</top>
-- local doc = xml.elem("main", xml.new("child"))            -- <main><child/></main>
-- local doc = xml.elem("main", { "this ", "is ", "nice" })  -- <main>this is nice</main>
-- local doc = xml.elem("main", { xml.new "this",
--                                xml.new "is",
--                                xml.new "nice" })          -- <main><this/><is/><nice/></main>
-- local doc = xml.elem("main", { hello = "world" })         -- <main hello='world'/>
-- local doc = xml.elem("main", {
--   "prefix",
--   xml.elem("child", { "this ", "is ", "nice"}),
--   "postfix",
--   attrib = "value"
-- })   -- <main attrib='value'>prefix<child>this is nice</child>postfix</main>"
function _M.elem(tag, items)
  local s = _M.new(tag)
  if is_text(items) then items = {items} end
  if is_tag(items) then
    t_insert(s,items)
  elseif type(items) == 'table' then
    for k,v in pairs(items) do
      if is_text(k) then
        s.attr[k] = v
        t_insert(s.attr,k)
      else
        s[k] = v
      end
    end
  end
  return s
end


--- given a list of names, return a number of element constructors.
-- If passing a comma-separated string, then whitespace surrounding the values
-- will be stripped.
--
-- The returned constructor functions are a shortcut to `xml.elem` where you
-- no longer provide the tag-name, but only the `items` table.
-- @tparam string|table list a list of names, or a comma-separated string.
-- @return (multiple) constructor functions; `function(items)`. For the `items`
-- parameter see `xml.elem`.
-- @see xml.elem
-- @usage
-- local new_parent, new_child = xml.tags 'mom, kid'
-- doc = new_parent {new_child 'Bob', new_child 'Annie'}
-- -- <mom><kid>Bob</kid><kid>Annie</kid></mom>
function _M.tags(list)
  local ctors = {}
  if is_text(list) then
    list = split(list:match("^%s*(.-)%s*$"),'%s*,%s*')
  end
  for i,tag in ipairs(list) do
    local function ctor(items)
      return _M.elem(tag,items)
    end
    ctors[i] = ctor
  end
  return unpack(ctors)
end


--- Adds a document Node, at current position.
-- This updates the last inserted position to the new Node.
-- @tparam string tag the tag name
-- @tparam[opt={}] table attrs attributes (table of name-value pairs)
-- @return the current node (`self`)
-- @usage
-- local doc = xml.new("main")
-- doc:addtag("penlight", { hello = "world"})
-- doc:addtag("expat")  -- added to 'penlight' since position moved
-- print(doc)  -->  <main><penlight hello='world'><expat/></penlight></main>
function Doc:addtag(tag, attrs)
  local s = _M.new(tag, attrs)
  self:add_child(s)
  t_insert(self.last_add, s)
  return self
end


--- Adds a text node, at current position.
-- @tparam string text a string
-- @return the current node (`self`)
-- @usage
-- local doc = xml.new("main")
-- doc:text("penlight")
-- doc:text("expat")
-- print(doc)  -->  <main><penlightexpat</main>
function Doc:text(text)
  self:add_child(text)
  return self
end


--- Moves current position up one level.
-- @return the current node (`self`)
function Doc:up()
  t_remove(self.last_add)
  return self
end


--- Resets current position to top level.
-- Resets to the `self` node.
-- @return the current node (`self`)
function Doc:reset()
  local last_add = self.last_add
  for i = 1,#last_add do
    last_add[i] = nil
  end
  return self
end


--- Append a child to the currrent Node (ignoring current position).
-- @param child a child node (either text or a document)
-- @return the current node (`self`)
-- @usage
-- local doc = xml.new("main")
-- doc:add_direct_child("dog")
-- doc:add_direct_child(xml.new("child"))
-- doc:add_direct_child("cat")
-- print(doc)  -->  <main>dog<child/>cat</main>
function Doc:add_direct_child(child)
  t_insert(self, child)
  return self
end


--- Append a child at the current position (without changing position).
-- @param child a child node (either text or a document)
-- @return the current node (`self`)
-- @usage
-- local doc = xml.new("main")
-- doc:addtag("one")
-- doc:add_child(xml.new("item1"))
-- doc:add_child(xml.new("item2"))
-- doc:add_child(xml.new("item3"))
-- print(doc)  -->  <main><one><item1/><item2/><item3/></one></main>
function Doc:add_child(child)
  (self.last_add[#self.last_add] or self):add_direct_child(child)
  return self
end


--accessing attributes: useful not to have to expose implementation (attr)
--but also can allow attr to be nil in any future optimizations


--- Set attributes of a document node.
-- Will add/overwite values, but will not remove existing ones.
-- Operates on the Node itself, will not take position into account.
-- @tparam table t a table containing attribute/value pairs
-- @return the current node (`self`)
function Doc:set_attribs(t)
  -- TODO: keep array part in sync
  for k,v in pairs(t) do
    self.attr[k] = v
  end
  return self
end


--- Set a single attribute of a document node.
-- Operates on the Node itself, will not take position into account.
-- @param a attribute
-- @param v its value, pass in `nil` to delete the attribute
-- @return the current node (`self`)
function Doc:set_attrib(a,v)
  -- TODO: keep array part in sync
  self.attr[a] = v
  return self
end


--- Gets the attributes of a document node.
-- Operates on the Node itself, will not take position into account.
-- @return table with attributes (attribute/value pairs)
function Doc:get_attribs()
  return self.attr
end



local template_cache do
  local templ_cache = {}

  -- @param templ a template, a string being valid xml to be parsed, or a Node object
  function template_cache(templ)
    if is_text(templ) then
      if templ_cache[templ] then
        -- cache hit
        return templ_cache[templ]

      else
        -- parse and cache
        local ptempl, err = _M.parse(templ,false,true)
        if not ptempl then
          return nil, err
        end
        templ_cache[templ] = ptempl
        return ptempl
      end
    end

    if is_tag(templ) then
      return templ
    end

    return nil, "template is not a document"
  end
end


do
  local function is_data(data)
    return #data == 0 or type(data[1]) ~= 'table'
  end


  local function prepare_data(data)
    -- a hack for ensuring that $1 maps to first element of data, etc.
    -- Either this or could change the gsub call just below.
    for i,v in ipairs(data) do
      data[tostring(i)] = v
    end
  end

  --- create a substituted copy of a document,
  -- @param template may be a document or a string representation which will be parsed and cached
  -- @param data a table of name-value pairs or a list of such tables
  -- @return an XML document
  function Doc.subst(template, data)
    if type(data) ~= 'table' or not next(data) then
      return nil, "data must be a non-empty table"
    end

    if is_data(data) then
      prepare_data(data)
    end

    local templ, err = template_cache(template)
    if err then
      return nil, err
    end

    local function _subst(item)
      return _M.clone(templ, function(s)
        return s:gsub('%$(%w+)', item)
      end)
    end

    if is_data(data) then
      return _subst(data)
    end

    local list = {}
    for _, item in ipairs(data) do
      prepare_data(item)
      t_insert(list, _subst(item))
    end

    if data.tag then
      list = _M.elem(data.tag,list)
    end
    return list
  end
end


--- Return the first child with a given tag name (non-recursive).
-- @param tag the tag name
-- @return the child Node found or `nil` if not found
function Doc:child_with_name(tag)
  for _, child in ipairs(self) do
    if child.tag == tag then
      return child
    end
  end
end


do
  -- @param self document node to traverse
  -- @param tag tag-name to look for
  -- @param list array table to add the matching ones to
  -- @param recurse if truthy, recursivly search the node
  local function _children_with_name(self, tag, list, recurse)
    -- TODO: protect against recursion
    for _, child in ipairs(self) do
      if type(child) == 'table' then
        if child.tag == tag then
          t_insert(list, child)
        end
        if recurse then
          _children_with_name(child, tag, list, recurse)
        end
      end
    end
  end

  --- Returns all elements in a document that have a given tag.
  -- @tparam string tag a tag name
  -- @tparam[opt=false] boolean dont_recurse optionally only return the immediate children with this tag name
  -- @return a list of elements found, list will be empty if none was found.
  function Doc:get_elements_with_name(tag, dont_recurse)
    local res = {}
    _children_with_name(self, tag, res, not dont_recurse)
    return res
  end
end



--- Iterator over all children of a document node, including text nodes.
-- This function is not recursive, so returns only direct child nodes.
-- @return iterator that returns a single Node per iteration.
function Doc:children()
  local i = 0;
  return function (a)
    i = i + 1
    return a[i];
  end, self, i;
end


--- Return the first child element of a node, if it exists.
-- This will skip text nodes.
-- @return first child Node or `nil` if there is none.
function Doc:first_childtag()
  if #self == 0 then
    return
  end
  for _, t in ipairs(self) do
    if is_tag(t) then
      return t
    end
  end
end


--- Iterator that matches tag names, and a namespace (non-recursive).
-- @tparam[opt=nil] string tag tag names to return. Returns all tags if not provided.
-- @tparam[opt=nil] string xmlns the namespace value ('xmlns' attribute) to return. If not
-- provided will match all namespaces.
-- @return iterator that returns a single Node per iteration.
function Doc:matching_tags(tag, xmlns)
  -- TODO: this doesn't make sense??? namespaces are not "xmnls", as matched below
  -- but "xmlns:name"... so should be a string-prefix match if anything...
  xmlns = xmlns or self.attr.xmlns;
  local tags = self
  local next_i = 1
  local max_i = #tags
  local node
  return function ()
      for i = next_i, max_i do
        node = tags[i];
        if (not tag or node.tag == tag) and
           (not xmlns or xmlns == node.attr.xmlns) then
          next_i = i + 1
          return node
        end
      end
    end, tags, next_i
end


--- Iterator over all child tags of a document node. This will skip over
-- text nodes.
-- @return iterator that returns a single Node per iteration.
function Doc:childtags()
  local i = 0;
  return function (a)
    local v
      repeat
        i = i + 1
        v = self[i]
        if v and type(v) == 'table' then
          return v
        end
      until not v
    end, self[1], i;
end


--- Visit child Nodes of a node and call a function, possibly modifying the document.
-- Text elements will be skipped.
-- This is not recursive, so only direct children will be passed.
-- @tparam function callback a function with signature `function(node)`, passed the node.
-- The element will be updated with the returned value, or deleted if it returns `nil`.
function Doc:maptags(callback)
  local i = 1;

  while i <= #self do
    if is_tag(self[i]) then
      local ret = callback(self[i]);
      if ret == nil then
        -- remove it
        t_remove(self, i);

      else
        -- update it
        self[i] = ret;
        i = i + 1;
      end
    else
      i = i + 1
    end
  end

  return self;
end


do
  local escape_table = {
    ["'"] = "&apos;",
    ['"'] = "&quot;",
    ["<"] = "&lt;",
    [">"] = "&gt;",
    ["&"] = "&amp;",
  }

  --- Escapes a string for safe use in xml.
  -- Handles quotes(single+double), less-than, greater-than, and ampersand.
  -- @tparam string str string value to escape
  -- @return escaped string
  -- @usage
  -- local esc = xml.xml_escape([["'<>&]])  --> "&quot;&apos;&lt;&gt;&amp;"
  function _M.xml_escape(str)
    return (s_gsub(str, "['&<>\"]", escape_table))
  end
end
local xml_escape = _M.xml_escape

do
  local escape_table = {
    quot = '"',
    apos = "'",
    lt = "<",
    gt = ">",
    amp = "&",
  }

  --- Unescapes a string from xml.
  -- Handles quotes(single+double), less-than, greater-than, and ampersand.
  -- @tparam string str string value to unescape
  -- @return unescaped string
  -- @usage
  -- local unesc = xml.xml_escape("&quot;&apos;&lt;&gt;&amp;")  --> [["'<>&]]
  function _M.xml_unescape(str)
    return (str:gsub( "&(%a+);", escape_table))
  end
end
local xml_unescape = _M.xml_unescape

-- pretty printing
-- if indent, then put each new tag on its own line
-- if attr_indent, put each new attribute on its own line
local function _dostring(t, buf, parentns, block_indent, tag_indent, attr_indent)
  local nsid = 0
  local tag = t.tag

  local lf = ""
  if tag_indent then
    lf = '\n'..block_indent
  end

  local alf = " "
  if attr_indent then
    alf = '\n'..block_indent..attr_indent
  end

  t_insert(buf, lf.."<"..tag)

  local function write_attr(k,v)
    if s_find(k, "\1", 1, true) then
      nsid = nsid + 1
      local ns, attrk = s_match(k, "^([^\1]*)\1?(.*)$")
      t_insert(buf, " xmlns:ns"..nsid.."='"..xml_escape(ns).."' ".."ns"..nsid..":"..attrk.."='"..xml_escape(v).."'")

    elseif not (k == "xmlns" and v == parentns) then
      t_insert(buf, alf..k.."='"..xml_escape(v).."'");
    end
  end

  -- it's useful for testing to have predictable attribute ordering, if available
  if #t.attr > 0 then
    -- TODO: the key-value list is leading, what if they are not in-sync
    for _,k in ipairs(t.attr) do
      write_attr(k,t.attr[k])
    end
  else
    for k, v in pairs(t.attr) do
      write_attr(k,v)
    end
  end

  local len = #t
  local has_children

  if len == 0 then
    t_insert(buf, attr_indent and '\n'..block_indent.."/>" or "/>")

  else
    t_insert(buf, ">");

    for n = 1, len do
      local child = t[n]

      if child.tag then
        has_children = true
        _dostring(child, buf, t.attr.xmlns, block_indent and block_indent..tag_indent, tag_indent, attr_indent)

      else
        -- text element
        t_insert(buf, xml_escape(child))
      end
    end

    t_insert(buf, (has_children and lf or '').."</"..tag..">");
  end
end

--- Function to pretty-print an XML document.
-- @param doc an XML document
-- @tparam[opt] string|int b_ind an initial block-indent (required when `t_ind` is set)
-- @tparam[opt] string|int t_ind an tag-indent for each level (required when `a_ind` is set)
-- @tparam[opt] string|int a_ind if given, indent each attribute pair and put on a separate line
-- @tparam[opt] string|bool xml_preface force prefacing with default or custom <?xml...>, if truthy then `&lt;?xml version='1.0'?&gt;` will be used as default.
-- @return a string representation
-- @see Doc:tostring
function _M.tostring(doc, b_ind, t_ind, a_ind, xml_preface)
  local buf = {}

  if type(b_ind) == "number" then b_ind = (" "):rep(b_ind) end
  if type(t_ind) == "number" then t_ind = (" "):rep(t_ind) end
  if type(a_ind) == "number" then a_ind = (" "):rep(a_ind) end

  if xml_preface then
    if type(xml_preface) == "string" then
      buf[1] = xml_preface
    else
      buf[1] = "<?xml version='1.0'?>"
    end
  end

  _dostring(doc, buf, nil, b_ind, t_ind, a_ind, xml_preface)

  return t_concat(buf)
end


Doc.__tostring = _M.tostring


--- Method to pretty-print an XML document.
-- Invokes `xml.tostring`.
-- @tparam[opt] string|int b_ind an initial indent (required when `t_ind` is set)
-- @tparam[opt] string|int t_ind an indent for each level (required when `a_ind` is set)
-- @tparam[opt] string|int a_ind if given, indent each attribute pair and put on a separate line
-- @tparam[opt="&lt;?xml version='1.0'?&gt;"] string xml_preface force prefacing with default or custom <?xml...>
-- @return a string representation
-- @see xml.tostring
function Doc:tostring(b_ind, t_ind, a_ind, xml_preface)
  return _M.tostring(self, b_ind, t_ind, a_ind, xml_preface)
end


--- get the full text value of an element.
-- @return a single string with all text elements concatenated
-- @usage
-- local doc = xml.new("main")
-- doc:text("one")
-- doc:add_child(xml.elem "two")
-- doc:text("three")
--
-- local t = doc:get_text()    -->  "onethree"
function Doc:get_text()
  local res = {}
  for i,el in ipairs(self) do
    if is_text(el) then t_insert(res,el) end
  end
  return t_concat(res);
end


do
  local function _copy(object, kind, parent, strsubst, lookup_table)
    if type(object) ~= "table" then
      if strsubst and is_text(object) then
        return strsubst(object, kind, parent)
      else
        return object
      end
    end

    if lookup_table[object] then
      error("recursion detected")
    end
    lookup_table[object] = true

    local new_table = {}
    lookup_table[object] = new_table

    local tag = object.tag
    new_table.tag = _copy(tag, '*TAG', parent, strsubst, lookup_table)

    if object.attr then
      local res = {}
      for attr, value in pairs(object.attr) do
        if type(attr) == "string" then
          res[attr] = _copy(value, attr, object, strsubst, lookup_table)
        end
      end
      new_table.attr = res
    end

    for index = 1, #object do
      local v = _copy(object[index], '*TEXT', object, strsubst, lookup_table)
      t_insert(new_table,v)
    end

    return setmetatable(new_table, getmetatable(object))
  end

  --- Returns a copy of a document.
  -- The `strsubst` parameter is a callback with signature `function(object, kind, parent)`.
  --
  -- Param `kind` has the following values, and parameters:
  --
  -- - `"*TAG"`: `object` is the tag-name, `parent` is the Node object. Returns the new tag name.
  --
  -- - `"*TEXT"`: `object` is the text-element, `parent` is the Node object. Returns the new text value.
  --
  -- - other strings not prefixed with `*`: `kind` is the attribute name, `object` is the
  --   attribute value, `parent` is the Node object. Returns the new attribute value.
  --
  -- @tparam Node|string doc a Node object or string (text node)
  -- @tparam[opt] function strsubst an optional function for handling string copying
  -- which could do substitution, etc.
  -- @return copy of the document
  -- @see Doc:filter
  function _M.clone(doc, strsubst)
    return _copy(doc, nil, nil, strsubst, {})
  end
end


--- Returns a copy of a document.
-- This is the method version of `xml.clone`.
-- @see xml.clone
-- @name Doc:filter
-- @tparam[opt] function strsubst an optional function for handling string copying
Doc.filter = _M.clone -- also available as method

do
  local function _compare(t1, t2, recurse_check)

    local ty1 = type(t1)
    local ty2 = type(t2)

    if ty1 ~= ty2 then
      return false, 'type mismatch'
    end

    if ty1 == 'string' then
      if t1 == t2 then
        return true
      else
        return false, 'text '..t1..' ~= text '..t2
      end
    end

    if ty1 ~= 'table' or ty2 ~= 'table' then
      return false, 'not a document'
    end

    if recurse_check[t1] then
      return false, "recursive document"
    end
    recurse_check[t1] = true

    if t1.tag ~= t2.tag then
      return false, 'tag  '..t1.tag..' ~= tag '..t2.tag
    end

    if #t1 ~= #t2 then
      return false, 'size '..#t1..' ~= size '..#t2..' for tag '..t1.tag
    end

    -- compare attributes
    for k,v in pairs(t1.attr) do
      local t2_value = t2.attr[k]
      if type(k) == "string" then
        if t2_value ~= v then return false, 'mismatch attrib' end
      else
        if t2_value ~= nil and t2_value ~= v then return false, "mismatch attrib order" end
      end
    end
    for k,v in pairs(t2.attr) do
      local t1_value = t1.attr[k]
      if type(k) == "string" then
        if t1_value ~= v then return false, 'mismatch attrib' end
      else
        if t1_value ~= nil and t1_value ~= v then return false, "mismatch attrib order" end
      end
    end

    -- compare children
    for i = 1, #t1 do
      local ok, err = _compare(t1[i], t2[i], recurse_check)
      if not ok then
        return ok, err
      end
    end
    return true
  end

  --- Compare two documents or elements.
  -- Equality is based on tag, child nodes (text and tags), attributes and order
  -- of those (order only fails if both are given, and not equal).
  -- @tparam Node|string t1 a Node object or string (text node)
  -- @tparam Node|string t2 a Node object or string (text node)
  -- @treturn boolean `true` when the Nodes are equal.
  function _M.compare(t1,t2)
    return _compare(t1, t2, {})
  end
end


--- is this value a document element?
-- @param d any value
-- @treturn boolean `true` if it is a `table` with property `tag` being a string value.
-- @name is_tag
_M.is_tag = is_tag


do
  local function _walk(doc, depth_first, operation, recurse_check)
    if not depth_first then operation(doc.tag, doc) end
    for _,d in ipairs(doc) do
      if is_tag(d) then
        assert(not recurse_check[d], "recursion detected")
        recurse_check[d] = true
        _walk(d, depth_first, operation, recurse_check)
      end
    end
    if depth_first then operation(doc.tag, doc) end
  end

  --- Calls a function recursively over Nodes in the document.
  -- Will only call on tags, it will skip text nodes.
  -- The function signature for `operation` is `function(tag_name, Node)`.
  -- @tparam Node|string doc a Node object or string (text node)
  -- @tparam boolean depth_first visit child nodes first, then the current node
  -- @tparam function operation a function which will receive the current tag name and current node.
  function _M.walk(doc, depth_first, operation)
    return _walk(doc, depth_first, operation, {})
  end
end


local html_empty_elements = { --lists all HTML empty (void) elements
    br      = true,
    img     = true,
    meta    = true,
    frame   = true,
    area    = true,
    hr      = true,
    base    = true,
    col     = true,
    link    = true,
    input   = true,
    option  = true,
    param   = true,
    isindex = true,
    embed = true,
}

--- Parse a well-formed HTML file as a string.
-- Tags are case-insenstive, DOCTYPE is ignored, and empty elements can be .. empty.
-- @param s the HTML
function _M.parsehtml(s)
    return _M.basic_parse(s,false,true)
end

--- Parse a simple XML document using a pure Lua parser based on Robero Ierusalimschy's original version.
-- @param s the XML document to be parsed.
-- @param all_text  if true, preserves all whitespace. Otherwise only text containing non-whitespace is included.
-- @param html if true, uses relaxed HTML rules for parsing
function _M.basic_parse(s, all_text, html)
    local stack = {}
    local top = {}

    local function parseargs(s)
      local arg = {}
      s:gsub("([%w:%-_]+)%s*=%s*([\"'])(.-)%2", function (w, _, a)
        if html then w = w:lower() end
        arg[w] = xml_unescape(a)
      end)
      if html then
        s:gsub("([%w:%-_]+)%s*=%s*([^\"']+)%s*", function (w, a)
          w = w:lower()
          arg[w] = xml_unescape(a)
        end)
      end
      return arg
    end

    t_insert(stack, top)
    local ni,c,label,xarg, empty, _, istart
    local i = 1
    local j
    -- we're not interested in <?xml version="1.0"?>
    _,istart = s_find(s,'^%s*<%?[^%?]+%?>%s*')
    if not istart then -- or <!DOCTYPE ...>
        _,istart = s_find(s,'^%s*<!DOCTYPE.->%s*')
    end
    if istart then i = istart+1 end
    while true do
        ni,j,c,label,xarg, empty = s_find(s, "<([%/!]?)([%w:%-_]+)(.-)(%/?)>", i)
        if not ni then break end
        if c == "!" then -- comment
            -- case where there's no space inside comment
            if not (label:match '%-%-$' and xarg == '') then
                if xarg:match '%-%-$' then -- we've grabbed it all
                    j = j - 2
                end
                -- match end of comment
                _,j = s_find(s, "-->", j, true)
            end
        else
            local text = s_sub(s, i, ni-1)
            if html then
                label = label:lower()
                if html_empty_elements[label] then empty = "/" end
            end
            if all_text or not s_find(text, "^%s*$") then
                t_insert(top, xml_unescape(text))
            end
            if empty == "/" then  -- empty element tag
                t_insert(top, setmetatable({tag=label, attr=parseargs(xarg), empty=1},Doc))
            elseif c == "" then   -- start tag
                top = setmetatable({tag=label, attr=parseargs(xarg)},Doc)
                t_insert(stack, top)   -- new level
            else  -- end tag
                local toclose = t_remove(stack)  -- remove top
                top = stack[#stack]
                if #stack < 1 then
                    error("nothing to close with "..label..':'..text)
                end
                if toclose.tag ~= label then
                    error("trying to close "..toclose.tag.." with "..label.." "..text)
                end
                t_insert(top, toclose)
            end
        end
        i = j+1
    end
    local text = s_sub(s, i)
    if all_text or  not s_find(text, "^%s*$") then
        t_insert(stack[#stack], xml_unescape(text))
    end
    if #stack > 1 then
        error("unclosed "..stack[#stack].tag)
    end
    local res = stack[1]
    return is_text(res[1]) and res[2] or res[1]
end

do
  local match do

    local function empty(attr) return not attr or not next(attr) end

    local append_capture do
      -- returns the key,value pair from a table if it has exactly one entry
      local function has_one_element(t)
          local key,value = next(t)
          if next(t,key) ~= nil then return false end
          return key,value
      end

      function append_capture(res,tbl)
          if not empty(tbl) then -- no point in capturing empty tables...
              local key
              if tbl._ then  -- if $_ was set then it is meant as the top-level key for the captured table
                  key = tbl._
                  tbl._ = nil
                  if empty(tbl) then return end
              end
              -- a table with only one pair {[0]=value} shall be reduced to that value
              local numkey,val = has_one_element(tbl)
              if numkey == 0 then tbl = val end
              if key then
                  res[key] = tbl
              else -- otherwise, we append the captured table
                  t_insert(res,tbl)
              end
          end
      end
    end

    local function make_number(pat)
        if pat:find '^%d+$' then -- $1 etc means use this as an array location
            pat = tonumber(pat)
        end
        return pat
    end

    local function capture_attrib(res,pat,value)
        pat = make_number(pat:sub(2))
        res[pat] = value
        return true
    end

    function match(d,pat,res,keep_going)
        local ret = true
        if d == nil then d = '' end --return false end
        -- attribute string matching is straight equality, except if the pattern is a $ capture,
        -- which always succeeds.
        if is_text(d) then
            if not is_text(pat) then return false end
            if _M.debug then print(d,pat) end
            if pat:find '^%$' then
                return capture_attrib(res,pat,d)
            else
                return d == pat
            end
        else
        if _M.debug then print(d.tag,pat.tag) end
            -- this is an element node. For a match to succeed, the attributes must
            -- match as well.
            -- a tagname in the pattern ending with '-' is a wildcard and matches like an attribute
            local tagpat = pat.tag:match '^(.-)%-$'
            if tagpat then
                tagpat = make_number(tagpat)
                res[tagpat] = d.tag
            end
            if d.tag == pat.tag or tagpat then

                if not empty(pat.attr) then
                    if empty(d.attr) then ret =  false
                    else
                        for prop,pval in pairs(pat.attr) do
                            local dval = d.attr[prop]
                            if not match(dval,pval,res) then ret = false;  break end
                        end
                    end
                end
                -- the pattern may have child nodes. We match partially, so that {P1,P2} shall match {X,P1,X,X,P2,..}
                if ret and #pat > 0 then
                    local i,j = 1,1
                    local function next_elem()
                        j = j + 1  -- next child element of data
                        if is_text(d[j]) then j = j + 1 end
                        return j <= #d
                    end
                    repeat
                        local p = pat[i]
                        -- repeated {{<...>}} patterns  shall match one or more elements
                        -- so e.g. {P+} will match {X,X,P,P,X,P,X,X,X}
                        if is_tag(p) and p.repeated then
                            local found
                            repeat
                                local tbl = {}
                                ret = match(d[j],p,tbl,false)
                                if ret then
                                    found = false --true
                                    append_capture(res,tbl)
                                end
                            until not next_elem() or (found and not ret)
                            i = i + 1
                        else
                            ret = match(d[j],p,res,false)
                            if ret then i = i + 1 end
                        end
                    until not next_elem() or i > #pat -- run out of elements or patterns to match
                    -- if every element in our pattern matched ok, then it's been a successful match
                    if i > #pat then return true end
                end
                if ret then return true end
            else
                ret = false
            end
            -- keep going anyway - look at the children!
            if keep_going then
                for child in d:childtags() do
                    ret = match(child,pat,res,keep_going)
                    if ret then break end
                end
            end
        end
        return ret
    end
  end

  --- does something...
  function Doc:match(pat)
      local err
      pat,err = template_cache(pat)
      if not pat then return nil, err end
      _M.walk(pat,false,function(_,d)
          if is_text(d[1]) and is_tag(d[2]) and is_text(d[3]) and
            d[1]:find '%s*{{' and d[3]:find '}}%s*' then
            t_remove(d,1)
            t_remove(d,2)
            d[1].repeated = true
          end
      end)

      local res = {}
      local ret = match(self,pat,res,true)
      return res,ret
  end
end


return _M

