local D={}
D.SPACE={text=" "}

local VOID={area=1,base=1,br=1,col=1,embed=1,hr=1,img=1,input=1,link=1,meta=1,
param=1,source=1,track=1,wbr=1}
local RAW={script=1,style=1,textarea=1,title=1,noscript=1,template=1,svg=1}

local CLOSES={
p={p=1},li={li=1},dt={dt=1,dd=1},dd={dt=1,dd=1},tr={tr=1,td=1,th=1},
td={td=1,th=1},th={td=1,th=1},option={option=1},thead={tbody=1,tfoot=1},
tbody={thead=1,tbody=1,tfoot=1},tfoot={thead=1,tbody=1},
}
local BLOCK_CLOSES_P={div=1,ul=1,ol=1,table=1,h1=1,h2=1,h3=1,h4=1,h5=1,h6=1,section=1,
article=1,header=1,footer=1,nav=1,form=1,pre=1,blockquote=1,hr=1,main=1,aside=1,figure=1}

local function parseAttrs(s,decode)
local a={}
local pos=1
while true do
local n1,n2,name=s:find("^%s*([^%s=/>\"']+)",pos)
if not n1 then break end
pos=n2+1
local v
local e1,e2=s:find("^%s*=%s*",pos)
if e1 then
pos=e2+1
local q=s:sub(pos,pos)
if q=='"'or q=="'"then
local close=s:find(q,pos+1,true)or#s+1
v=s:sub(pos+1,close-1)
pos=close+1
else
local _,ve=s:find("^[^%s>]*",pos)
v=s:sub(pos,ve)
pos=ve+1
end
end
a[name:lower()]=v and decode(v)or""
end
return a
end

function D.parse(html,decode,maxNodes,yield)
maxNodes=maxNodes or 12000
local root={tag="#document",attrs={},children={}}
local stack={root}
local count=0
local pos,len=1,#html
local lower=html:lower()
local function top()return stack[#stack]end
local function add(node)
local p=top()
node.parent=p
p.children[#p.children+1]=node
count=count+1
end
local function closeTo(name)
for i=#stack,2,-1 do
if stack[i].tag==name then
for j=#stack,i,-1 do stack[j]=nil end
return true
end
end
end
while pos<=len and count<maxNodes do
if yield and count%300==0 then yield()end
local lt=html:find("<",pos,true)
local tEnd=(lt or len+1)-1
if tEnd>=pos then
local t=html:sub(pos,tEnd)
if t:find("%S")then add({text=decode(t)})
elseif#top().children>0 then

local p=top()
p.children[#p.children+1]=D.SPACE
end
end
if not lt then break end
local c2=html:sub(lt+1,lt+1)
if html:sub(lt,lt+3)=="<!--"then
local e=html:find("-->",lt+4,true)
pos=e and e+3 or len+1
elseif c2=="!"or c2=="?"then
local e=html:find(">",lt,true)
pos=e and e+1 or len+1
else
local gt=html:find(">",lt,true)
if not gt then break end
local raw=html:sub(lt+1,gt-1)
pos=gt+1
local close=raw:sub(1,1)=="/"
local name=(raw:match("^/?%s*([%w%-]+)")or""):lower()
if name~=""then
if close then
if name=="p"and not closeTo("p")then add({tag="p",attrs={},children={}})
else closeTo(name)end
else
local attrs=parseAttrs(raw:sub(#name+1):gsub("/%s*$",""),decode)
local t=top()
if CLOSES[name]and CLOSES[name][t.tag]then stack[#stack]=nil end
if BLOCK_CLOSES_P[name]and top().tag=="p"then stack[#stack]=nil end
local node={tag=name,attrs=attrs,children={}}
add(node)
if RAW[name]then
local e=lower:find("</"..name,pos,true)or len+1
local body=html:sub(pos,e-1)
if name=="textarea"or name=="title"then node.children[1]={text=decode(body),parent=node}
elseif name=="style"then node.css=body end
local gt2=html:find(">",e,true)
pos=gt2 and gt2+1 or len+1
elseif not VOID[name]and not raw:find("/%s*$")then
stack[#stack+1]=node
end
end
end
end
end
root.truncated=count>=maxNodes
return root
end


function D.walk(node,fn,depth)
depth=depth or 0
if fn(node,depth)==false then return end
for _,c in ipairs(node.children or{})do D.walk(c,fn,depth+1)end
end
function D.find(node,tag)
local r
D.walk(node,function(n)if not r and n.tag==tag then r=n return false end end)
return r
end
function D.text(node)
local t={}
D.walk(node,function(n)if n.text then t[#t+1]=n.text end end)
return table.concat(t)
end

return D