Matthias Andreas Benkard | 832a54e | 2019-01-29 09:27:38 +0100 | [diff] [blame] | 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 | scopeMarkerNode |
| 22 | ) |
| 23 | |
| 24 | // Section 12.2.4.3 says "The markers are inserted when entering applet, |
| 25 | // object, marquee, template, td, th, and caption elements, and are used |
| 26 | // to prevent formatting from "leaking" into applet, object, marquee, |
| 27 | // template, td, th, and caption elements". |
| 28 | var scopeMarker = Node{Type: scopeMarkerNode} |
| 29 | |
| 30 | // A Node consists of a NodeType and some Data (tag name for element nodes, |
| 31 | // content for text) and are part of a tree of Nodes. Element nodes may also |
| 32 | // have a Namespace and contain a slice of Attributes. Data is unescaped, so |
| 33 | // that it looks like "a<b" rather than "a<b". For element nodes, DataAtom |
| 34 | // is the atom for Data, or zero if Data is not a known tag name. |
| 35 | // |
| 36 | // An empty Namespace implies a "http://www.w3.org/1999/xhtml" namespace. |
| 37 | // Similarly, "math" is short for "http://www.w3.org/1998/Math/MathML", and |
| 38 | // "svg" is short for "http://www.w3.org/2000/svg". |
| 39 | type Node struct { |
| 40 | Parent, FirstChild, LastChild, PrevSibling, NextSibling *Node |
| 41 | |
| 42 | Type NodeType |
| 43 | DataAtom atom.Atom |
| 44 | Data string |
| 45 | Namespace string |
| 46 | Attr []Attribute |
| 47 | } |
| 48 | |
| 49 | // InsertBefore inserts newChild as a child of n, immediately before oldChild |
| 50 | // in the sequence of n's children. oldChild may be nil, in which case newChild |
| 51 | // is appended to the end of n's children. |
| 52 | // |
| 53 | // It will panic if newChild already has a parent or siblings. |
| 54 | func (n *Node) InsertBefore(newChild, oldChild *Node) { |
| 55 | if newChild.Parent != nil || newChild.PrevSibling != nil || newChild.NextSibling != nil { |
| 56 | panic("html: InsertBefore called for an attached child Node") |
| 57 | } |
| 58 | var prev, next *Node |
| 59 | if oldChild != nil { |
| 60 | prev, next = oldChild.PrevSibling, oldChild |
| 61 | } else { |
| 62 | prev = n.LastChild |
| 63 | } |
| 64 | if prev != nil { |
| 65 | prev.NextSibling = newChild |
| 66 | } else { |
| 67 | n.FirstChild = newChild |
| 68 | } |
| 69 | if next != nil { |
| 70 | next.PrevSibling = newChild |
| 71 | } else { |
| 72 | n.LastChild = newChild |
| 73 | } |
| 74 | newChild.Parent = n |
| 75 | newChild.PrevSibling = prev |
| 76 | newChild.NextSibling = next |
| 77 | } |
| 78 | |
| 79 | // AppendChild adds a node c as a child of n. |
| 80 | // |
| 81 | // It will panic if c already has a parent or siblings. |
| 82 | func (n *Node) AppendChild(c *Node) { |
| 83 | if c.Parent != nil || c.PrevSibling != nil || c.NextSibling != nil { |
| 84 | panic("html: AppendChild called for an attached child Node") |
| 85 | } |
| 86 | last := n.LastChild |
| 87 | if last != nil { |
| 88 | last.NextSibling = c |
| 89 | } else { |
| 90 | n.FirstChild = c |
| 91 | } |
| 92 | n.LastChild = c |
| 93 | c.Parent = n |
| 94 | c.PrevSibling = last |
| 95 | } |
| 96 | |
| 97 | // RemoveChild removes a node c that is a child of n. Afterwards, c will have |
| 98 | // no parent and no siblings. |
| 99 | // |
| 100 | // It will panic if c's parent is not n. |
| 101 | func (n *Node) RemoveChild(c *Node) { |
| 102 | if c.Parent != n { |
| 103 | panic("html: RemoveChild called for a non-child Node") |
| 104 | } |
| 105 | if n.FirstChild == c { |
| 106 | n.FirstChild = c.NextSibling |
| 107 | } |
| 108 | if c.NextSibling != nil { |
| 109 | c.NextSibling.PrevSibling = c.PrevSibling |
| 110 | } |
| 111 | if n.LastChild == c { |
| 112 | n.LastChild = c.PrevSibling |
| 113 | } |
| 114 | if c.PrevSibling != nil { |
| 115 | c.PrevSibling.NextSibling = c.NextSibling |
| 116 | } |
| 117 | c.Parent = nil |
| 118 | c.PrevSibling = nil |
| 119 | c.NextSibling = nil |
| 120 | } |
| 121 | |
| 122 | // reparentChildren reparents all of src's child nodes to dst. |
| 123 | func reparentChildren(dst, src *Node) { |
| 124 | for { |
| 125 | child := src.FirstChild |
| 126 | if child == nil { |
| 127 | break |
| 128 | } |
| 129 | src.RemoveChild(child) |
| 130 | dst.AppendChild(child) |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | // clone returns a new node with the same type, data and attributes. |
| 135 | // The clone has no parent, no siblings and no children. |
| 136 | func (n *Node) clone() *Node { |
| 137 | m := &Node{ |
| 138 | Type: n.Type, |
| 139 | DataAtom: n.DataAtom, |
| 140 | Data: n.Data, |
| 141 | Attr: make([]Attribute, len(n.Attr)), |
| 142 | } |
| 143 | copy(m.Attr, n.Attr) |
| 144 | return m |
| 145 | } |
| 146 | |
| 147 | // nodeStack is a stack of nodes. |
| 148 | type nodeStack []*Node |
| 149 | |
| 150 | // pop pops the stack. It will panic if s is empty. |
| 151 | func (s *nodeStack) pop() *Node { |
| 152 | i := len(*s) |
| 153 | n := (*s)[i-1] |
| 154 | *s = (*s)[:i-1] |
| 155 | return n |
| 156 | } |
| 157 | |
| 158 | // top returns the most recently pushed node, or nil if s is empty. |
| 159 | func (s *nodeStack) top() *Node { |
| 160 | if i := len(*s); i > 0 { |
| 161 | return (*s)[i-1] |
| 162 | } |
| 163 | return nil |
| 164 | } |
| 165 | |
| 166 | // index returns the index of the top-most occurrence of n in the stack, or -1 |
| 167 | // if n is not present. |
| 168 | func (s *nodeStack) index(n *Node) int { |
| 169 | for i := len(*s) - 1; i >= 0; i-- { |
| 170 | if (*s)[i] == n { |
| 171 | return i |
| 172 | } |
| 173 | } |
| 174 | return -1 |
| 175 | } |
| 176 | |
| 177 | // contains returns whether a is within s. |
| 178 | func (s *nodeStack) contains(a atom.Atom) bool { |
| 179 | for _, n := range *s { |
| 180 | if n.DataAtom == a { |
| 181 | return true |
| 182 | } |
| 183 | } |
| 184 | return false |
| 185 | } |
| 186 | |
| 187 | // insert inserts a node at the given index. |
| 188 | func (s *nodeStack) insert(i int, n *Node) { |
| 189 | (*s) = append(*s, nil) |
| 190 | copy((*s)[i+1:], (*s)[i:]) |
| 191 | (*s)[i] = n |
| 192 | } |
| 193 | |
| 194 | // remove removes a node from the stack. It is a no-op if n is not present. |
| 195 | func (s *nodeStack) remove(n *Node) { |
| 196 | i := s.index(n) |
| 197 | if i == -1 { |
| 198 | return |
| 199 | } |
| 200 | copy((*s)[i:], (*s)[i+1:]) |
| 201 | j := len(*s) - 1 |
| 202 | (*s)[j] = nil |
| 203 | *s = (*s)[:j] |
| 204 | } |
| 205 | |
| 206 | type insertionModeStack []insertionMode |
| 207 | |
| 208 | func (s *insertionModeStack) pop() (im insertionMode) { |
| 209 | i := len(*s) |
| 210 | im = (*s)[i-1] |
| 211 | *s = (*s)[:i-1] |
| 212 | return im |
| 213 | } |
| 214 | |
| 215 | func (s *insertionModeStack) top() insertionMode { |
| 216 | if i := len(*s); i > 0 { |
| 217 | return (*s)[i-1] |
| 218 | } |
| 219 | return nil |
| 220 | } |