1
// Copyright 2011 The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4

5
package html
6

7
import (
8
	"golang.org/x/net/html/atom"
9
)
10

11
// A NodeType is the type of a Node.
12
type NodeType uint32
13

14
const (
15
	ErrorNode NodeType = iota
16
	TextNode
17
	DocumentNode
18
	ElementNode
19
	CommentNode
20
	DoctypeNode
21
	// RawNode nodes are not returned by the parser, but can be part of the
22
	// Node tree passed to func Render to insert raw HTML (without escaping).
23
	// If so, this package makes no guarantee that the rendered HTML is secure
24
	// (from e.g. Cross Site Scripting attacks) or well-formed.
25
	RawNode
26
	scopeMarkerNode
27
)
28

29
// Section 12.2.4.3 says "The markers are inserted when entering applet,
30
// object, marquee, template, td, th, and caption elements, and are used
31
// to prevent formatting from "leaking" into applet, object, marquee,
32
// template, td, th, and caption elements".
33
var scopeMarker = Node{Type: scopeMarkerNode}
34

35
// A Node consists of a NodeType and some Data (tag name for element nodes,
36
// content for text) and are part of a tree of Nodes. Element nodes may also
37
// have a Namespace and contain a slice of Attributes. Data is unescaped, so
38
// that it looks like "a<b" rather than "a&lt;b". For element nodes, DataAtom
39
// is the atom for Data, or zero if Data is not a known tag name.
40
//
41
// Node trees may be navigated using the link fields (Parent,
42
// FirstChild, and so on) or a range loop over iterators such as
43
// [Node.Descendants].
44
//
45
// An empty Namespace implies a "http://www.w3.org/1999/xhtml" namespace.
46
// Similarly, "math" is short for "http://www.w3.org/1998/Math/MathML", and
47
// "svg" is short for "http://www.w3.org/2000/svg".
48
type Node struct {
49
	Parent, FirstChild, LastChild, PrevSibling, NextSibling *Node
50

51
	Type      NodeType
52
	DataAtom  atom.Atom
53
	Data      string
54
	Namespace string
55
	Attr      []Attribute
56
}
57

58
// InsertBefore inserts newChild as a child of n, immediately before oldChild
59
// in the sequence of n's children. oldChild may be nil, in which case newChild
60
// is appended to the end of n's children.
61
//
62
// It will panic if newChild already has a parent or siblings.
63
func (n *Node) InsertBefore(newChild, oldChild *Node) {
64
	if newChild.Parent != nil || newChild.PrevSibling != nil || newChild.NextSibling != nil {
65
		panic("html: InsertBefore called for an attached child Node")
66
	}
67
	var prev, next *Node
68
	if oldChild != nil {
69
		prev, next = oldChild.PrevSibling, oldChild
70
	} else {
71
		prev = n.LastChild
72
	}
73
	if prev != nil {
74
		prev.NextSibling = newChild
75
	} else {
76
		n.FirstChild = newChild
77
	}
78
	if next != nil {
79
		next.PrevSibling = newChild
80
	} else {
81
		n.LastChild = newChild
82
	}
83
	newChild.Parent = n
84
	newChild.PrevSibling = prev
85
	newChild.NextSibling = next
86
}
87

88
// AppendChild adds a node c as a child of n.
89
//
90
// It will panic if c already has a parent or siblings.
91
func (n *Node) AppendChild(c *Node) {
92
	if c.Parent != nil || c.PrevSibling != nil || c.NextSibling != nil {
93
		panic("html: AppendChild called for an attached child Node")
94
	}
95
	last := n.LastChild
96
	if last != nil {
97
		last.NextSibling = c
98
	} else {
99
		n.FirstChild = c
100
	}
101
	n.LastChild = c
102
	c.Parent = n
103
	c.PrevSibling = last
104
}
105

106
// RemoveChild removes a node c that is a child of n. Afterwards, c will have
107
// no parent and no siblings.
108
//
109
// It will panic if c's parent is not n.
110
func (n *Node) RemoveChild(c *Node) {
111
	if c.Parent != n {
112
		panic("html: RemoveChild called for a non-child Node")
113
	}
114
	if n.FirstChild == c {
115
		n.FirstChild = c.NextSibling
116
	}
117
	if c.NextSibling != nil {
118
		c.NextSibling.PrevSibling = c.PrevSibling
119
	}
120
	if n.LastChild == c {
121
		n.LastChild = c.PrevSibling
122
	}
123
	if c.PrevSibling != nil {
124
		c.PrevSibling.NextSibling = c.NextSibling
125
	}
126
	c.Parent = nil
127
	c.PrevSibling = nil
128
	c.NextSibling = nil
129
}
130

131
// reparentChildren reparents all of src's child nodes to dst.
132
func reparentChildren(dst, src *Node) {
133
	for {
134
		child := src.FirstChild
135
		if child == nil {
136
			break
137
		}
138
		src.RemoveChild(child)
139
		dst.AppendChild(child)
140
	}
141
}
142

143
// clone returns a new node with the same type, data and attributes.
144
// The clone has no parent, no siblings and no children.
145
func (n *Node) clone() *Node {
146
	m := &Node{
147
		Type:     n.Type,
148
		DataAtom: n.DataAtom,
149
		Data:     n.Data,
150
		Attr:     make([]Attribute, len(n.Attr)),
151
	}
152
	copy(m.Attr, n.Attr)
153
	return m
154
}
155

156
// nodeStack is a stack of nodes.
157
type nodeStack []*Node
158

159
// pop pops the stack. It will panic if s is empty.
160
func (s *nodeStack) pop() *Node {
161
	i := len(*s)
162
	n := (*s)[i-1]
163
	*s = (*s)[:i-1]
164
	return n
165
}
166

167
// top returns the most recently pushed node, or nil if s is empty.
168
func (s *nodeStack) top() *Node {
169
	if i := len(*s); i > 0 {
170
		return (*s)[i-1]
171
	}
172
	return nil
173
}
174

175
// index returns the index of the top-most occurrence of n in the stack, or -1
176
// if n is not present.
177
func (s *nodeStack) index(n *Node) int {
178
	for i := len(*s) - 1; i >= 0; i-- {
179
		if (*s)[i] == n {
180
			return i
181
		}
182
	}
183
	return -1
184
}
185

186
// contains returns whether a is within s.
187
func (s *nodeStack) contains(a atom.Atom) bool {
188
	for _, n := range *s {
189
		if n.DataAtom == a && n.Namespace == "" {
190
			return true
191
		}
192
	}
193
	return false
194
}
195

196
// insert inserts a node at the given index.
197
func (s *nodeStack) insert(i int, n *Node) {
198
	(*s) = append(*s, nil)
199
	copy((*s)[i+1:], (*s)[i:])
200
	(*s)[i] = n
201
}
202

203
// remove removes a node from the stack. It is a no-op if n is not present.
204
func (s *nodeStack) remove(n *Node) {
205
	i := s.index(n)
206
	if i == -1 {
207
		return
208
	}
209
	copy((*s)[i:], (*s)[i+1:])
210
	j := len(*s) - 1
211
	(*s)[j] = nil
212
	*s = (*s)[:j]
213
}
214

215
type insertionModeStack []insertionMode
216

217
func (s *insertionModeStack) pop() (im insertionMode) {
218
	i := len(*s)
219
	im = (*s)[i-1]
220
	*s = (*s)[:i-1]
221
	return im
222
}
223

224
func (s *insertionModeStack) top() insertionMode {
225
	if i := len(*s); i > 0 {
226
		return (*s)[i-1]
227
	}
228
	return nil
229
}
230

231