1// Copyright 2010 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
5package html
6
7import (
8	"fmt"
9)
10
11// checkTreeConsistency checks that a node and its descendants are all
12// consistent in their parent/child/sibling relationships.
13func checkTreeConsistency(n *Node) error {
14	return checkTreeConsistency1(n, 0)
15}
16
17func checkTreeConsistency1(n *Node, depth int) error {
18	if depth == 1e4 {
19		return fmt.Errorf("html: tree looks like it contains a cycle")
20	}
21	if err := checkNodeConsistency(n); err != nil {
22		return err
23	}
24	for c := n.FirstChild; c != nil; c = c.NextSibling {
25		if err := checkTreeConsistency1(c, depth+1); err != nil {
26			return err
27		}
28	}
29	return nil
30}
31
32// checkNodeConsistency checks that a node's parent/child/sibling relationships
33// are consistent.
34func checkNodeConsistency(n *Node) error {
35	if n == nil {
36		return nil
37	}
38
39	nParent := 0
40	for p := n.Parent; p != nil; p = p.Parent {
41		nParent++
42		if nParent == 1e4 {
43			return fmt.Errorf("html: parent list looks like an infinite loop")
44		}
45	}
46
47	nForward := 0
48	for c := n.FirstChild; c != nil; c = c.NextSibling {
49		nForward++
50		if nForward == 1e6 {
51			return fmt.Errorf("html: forward list of children looks like an infinite loop")
52		}
53		if c.Parent != n {
54			return fmt.Errorf("html: inconsistent child/parent relationship")
55		}
56	}
57
58	nBackward := 0
59	for c := n.LastChild; c != nil; c = c.PrevSibling {
60		nBackward++
61		if nBackward == 1e6 {
62			return fmt.Errorf("html: backward list of children looks like an infinite loop")
63		}
64		if c.Parent != n {
65			return fmt.Errorf("html: inconsistent child/parent relationship")
66		}
67	}
68
69	if n.Parent != nil {
70		if n.Parent == n {
71			return fmt.Errorf("html: inconsistent parent relationship")
72		}
73		if n.Parent == n.FirstChild {
74			return fmt.Errorf("html: inconsistent parent/first relationship")
75		}
76		if n.Parent == n.LastChild {
77			return fmt.Errorf("html: inconsistent parent/last relationship")
78		}
79		if n.Parent == n.PrevSibling {
80			return fmt.Errorf("html: inconsistent parent/prev relationship")
81		}
82		if n.Parent == n.NextSibling {
83			return fmt.Errorf("html: inconsistent parent/next relationship")
84		}
85
86		parentHasNAsAChild := false
87		for c := n.Parent.FirstChild; c != nil; c = c.NextSibling {
88			if c == n {
89				parentHasNAsAChild = true
90				break
91			}
92		}
93		if !parentHasNAsAChild {
94			return fmt.Errorf("html: inconsistent parent/child relationship")
95		}
96	}
97
98	if n.PrevSibling != nil && n.PrevSibling.NextSibling != n {
99		return fmt.Errorf("html: inconsistent prev/next relationship")
100	}
101	if n.NextSibling != nil && n.NextSibling.PrevSibling != n {
102		return fmt.Errorf("html: inconsistent next/prev relationship")
103	}
104
105	if (n.FirstChild == nil) != (n.LastChild == nil) {
106		return fmt.Errorf("html: inconsistent first/last relationship")
107	}
108	if n.FirstChild != nil && n.FirstChild == n.LastChild {
109		// We have a sole child.
110		if n.FirstChild.PrevSibling != nil || n.FirstChild.NextSibling != nil {
111			return fmt.Errorf("html: inconsistent sole child's sibling relationship")
112		}
113	}
114
115	seen := map[*Node]bool{}
116
117	var last *Node
118	for c := n.FirstChild; c != nil; c = c.NextSibling {
119		if seen[c] {
120			return fmt.Errorf("html: inconsistent repeated child")
121		}
122		seen[c] = true
123		last = c
124	}
125	if last != n.LastChild {
126		return fmt.Errorf("html: inconsistent last relationship")
127	}
128
129	var first *Node
130	for c := n.LastChild; c != nil; c = c.PrevSibling {
131		if !seen[c] {
132			return fmt.Errorf("html: inconsistent missing child")
133		}
134		delete(seen, c)
135		first = c
136	}
137	if first != n.FirstChild {
138		return fmt.Errorf("html: inconsistent first relationship")
139	}
140
141	if len(seen) != 0 {
142		return fmt.Errorf("html: inconsistent forwards/backwards child list")
143	}
144
145	return nil
146}
147