libgo/go/exp/html/node_test.go

   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
   5 package html
   6
   7 import (
   8         "fmt"
   9 )
  10
  11 // checkTreeConsistency checks that a node and its descendants are all
  12 // consistent in their parent/child/sibling relationships.
  13 func checkTreeConsistency(n *Node) error {
  14         return checkTreeConsistency1(n, 0)
  15 }
  16
  17 func 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.
  34 func 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 }