src/cmd/compile/internal/gc/syntax.go

   1 // Copyright 2009 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 // “Abstract” syntax representation.
   6
   7 package gc
   8
   9 import (
  10         "cmd/compile/internal/syntax"
  11         "cmd/internal/src"
  12 )
  13
  14 // A Node is a single node in the syntax tree.
  15 // Actually the syntax tree is a syntax DAG, because there is only one
  16 // node with Op=ONAME for a given instance of a variable x.
  17 // The same is true for Op=OTYPE and Op=OLITERAL.
  18 type Node struct {
  19         // Tree structure.
  20         // Generic recursive walks should follow these fields.
  21         Left  *Node
  22         Right *Node
  23         Ninit Nodes
  24         Nbody Nodes
  25         List  Nodes
  26         Rlist Nodes
  27
  28         // most nodes
  29         Type *Type
  30         Orig *Node // original form, for printing, and tracking copies of ONAMEs
  31
  32         // func
  33         Func *Func
  34
  35         // ONAME
  36         Name *Name
  37
  38         Sym *Sym        // various
  39         E   interface{} // Opt or Val, see methods below
  40
  41         // Various. Usually an offset into a struct. For example:
  42         // - ONAME nodes that refer to local variables use it to identify their stack frame position.
  43         // - ODOT, ODOTPTR, and OINDREGSP use it to indicate offset relative to their base address.
  44         // - OSTRUCTKEY uses it to store the named field's offset.
  45         // - OXCASE and OXFALL use it to validate the use of fallthrough.
  46         // - ONONAME uses it to store the current value of iota, see Node.Iota
  47         // Possibly still more uses. If you find any, document them.
  48         Xoffset int64
  49
  50         Pos src.XPos
  51
  52         Esc uint16 // EscXXX
  53
  54         Op        Op
  55         Ullman    uint8 // sethi/ullman number
  56         Addable   bool  // addressable
  57         Etype     EType // op for OASOP, etype for OTYPE, exclam for export, 6g saved reg, ChanDir for OTCHAN, for OINDEXMAP 1=LHS,0=RHS
  58         Bounded   bool  // bounds check unnecessary
  59         NonNil    bool  // guaranteed to be non-nil
  60         Class     Class // PPARAM, PAUTO, PEXTERN, etc
  61         Embedded  uint8 // ODCLFIELD embedded type
  62         Colas     bool  // OAS resulting from :=
  63         Diag      bool  // already printed error about this
  64         Noescape  bool  // func arguments do not escape; TODO(rsc): move Noescape to Func struct (see CL 7360)
  65         Walkdef   uint8 // tracks state during typecheckdef; 2 == loop detected
  66         Typecheck uint8 // tracks state during typechecking; 2 == loop detected
  67         Local     bool
  68         IsStatic  bool // whether this Node will be converted to purely static data
  69         Initorder uint8
  70         Used      bool // for variable/label declared and not used error
  71         Isddd     bool // is the argument variadic
  72         Implicit  bool
  73         Addrtaken bool  // address taken, even if not moved to heap
  74         Assigned  bool  // is the variable ever assigned to
  75         Likely    int8  // likeliness of if statement
  76         hasVal    int8  // +1 for Val, -1 for Opt, 0 for not yet set
  77         flags     uint8 // TODO: store more bool fields in this flag field
  78 }
  79
  80 // IsAutoTmp indicates if n was created by the compiler as a temporary,
  81 // based on the setting of the .AutoTemp flag in n's Name.
  82 func (n *Node) IsAutoTmp() bool {
  83         if n == nil || n.Op != ONAME {
  84                 return false
  85         }
  86         return n.Name.AutoTemp
  87 }
  88
  89 const (
  90         hasBreak = 1 << iota
  91         isClosureVar
  92         isOutputParamHeapAddr
  93         noInline // used internally by inliner to indicate that a function call should not be inlined; set for OCALLFUNC and OCALLMETH only
  94 )
  95
  96 func (n *Node) HasBreak() bool {
  97         return n.flags&hasBreak != 0
  98 }
  99 func (n *Node) SetHasBreak(b bool) {
 100         if b {
 101                 n.flags |= hasBreak
 102         } else {
 103                 n.flags &^= hasBreak
 104         }
 105 }
 106 func (n *Node) isClosureVar() bool {
 107         return n.flags&isClosureVar != 0
 108 }
 109 func (n *Node) setIsClosureVar(b bool) {
 110         if b {
 111                 n.flags |= isClosureVar
 112         } else {
 113                 n.flags &^= isClosureVar
 114         }
 115 }
 116 func (n *Node) noInline() bool {
 117         return n.flags&noInline != 0
 118 }
 119 func (n *Node) setNoInline(b bool) {
 120         if b {
 121                 n.flags |= noInline
 122         } else {
 123                 n.flags &^= noInline
 124         }
 125 }
 126
 127 func (n *Node) IsOutputParamHeapAddr() bool {
 128         return n.flags&isOutputParamHeapAddr != 0
 129 }
 130 func (n *Node) setIsOutputParamHeapAddr(b bool) {
 131         if b {
 132                 n.flags |= isOutputParamHeapAddr
 133         } else {
 134                 n.flags &^= isOutputParamHeapAddr
 135         }
 136 }
 137
 138 // Val returns the Val for the node.
 139 func (n *Node) Val() Val {
 140         if n.hasVal != +1 {
 141                 return Val{}
 142         }
 143         return Val{n.E}
 144 }
 145
 146 // SetVal sets the Val for the node, which must not have been used with SetOpt.
 147 func (n *Node) SetVal(v Val) {
 148         if n.hasVal == -1 {
 149                 Debug['h'] = 1
 150                 Dump("have Opt", n)
 151                 Fatalf("have Opt")
 152         }
 153         n.hasVal = +1
 154         n.E = v.U
 155 }
 156
 157 // Opt returns the optimizer data for the node.
 158 func (n *Node) Opt() interface{} {
 159         if n.hasVal != -1 {
 160                 return nil
 161         }
 162         return n.E
 163 }
 164
 165 // SetOpt sets the optimizer data for the node, which must not have been used with SetVal.
 166 // SetOpt(nil) is ignored for Vals to simplify call sites that are clearing Opts.
 167 func (n *Node) SetOpt(x interface{}) {
 168         if x == nil && n.hasVal >= 0 {
 169                 return
 170         }
 171         if n.hasVal == +1 {
 172                 Debug['h'] = 1
 173                 Dump("have Val", n)
 174                 Fatalf("have Val")
 175         }
 176         n.hasVal = -1
 177         n.E = x
 178 }
 179
 180 func (n *Node) Iota() int64 {
 181         return n.Xoffset
 182 }
 183
 184 func (n *Node) SetIota(x int64) {
 185         n.Xoffset = x
 186 }
 187
 188 // Name holds Node fields used only by named nodes (ONAME, OPACK, OLABEL, some OLITERAL).
 189 type Name struct {
 190         Pack      *Node  // real package for import . names
 191         Pkg       *Pkg   // pkg for OPACK nodes
 192         Heapaddr  *Node  // temp holding heap address of param (could move to Param?)
 193         Defn      *Node  // initializing assignment
 194         Curfn     *Node  // function for local variables
 195         Param     *Param // additional fields for ONAME
 196         Decldepth int32  // declaration loop depth, increased for every loop or label
 197         Vargen    int32  // unique name for ONAME within a function.  Function outputs are numbered starting at one.
 198         Funcdepth int32
 199         Readonly  bool
 200         Captured  bool // is the variable captured by a closure
 201         Byval     bool // is the variable captured by value or by reference
 202         Needzero  bool // if it contains pointers, needs to be zeroed on function entry
 203         Keepalive bool // mark value live across unknown assembly call
 204         AutoTemp  bool // is the variable a temporary (implies no dwarf info. reset if escapes to heap)
 205 }
 206
 207 type Param struct {
 208         Ntype *Node
 209
 210         // ONAME PAUTOHEAP
 211         Stackcopy *Node // the PPARAM/PPARAMOUT on-stack slot (moved func params only)
 212
 213         // ONAME PPARAM
 214         Field *Field // TFIELD in arg struct
 215
 216         // ONAME closure linkage
 217         // Consider:
 218         //
 219         //      func f() {
 220         //              x := 1 // x1
 221         //              func() {
 222         //                      use(x) // x2
 223         //                      func() {
 224         //                              use(x) // x3
 225         //                              --- parser is here ---
 226         //                      }()
 227         //              }()
 228         //      }
 229         //
 230         // There is an original declaration of x and then a chain of mentions of x
 231         // leading into the current function. Each time x is mentioned in a new closure,
 232         // we create a variable representing x for use in that specific closure,
 233         // since the way you get to x is different in each closure.
 234         //
 235         // Let's number the specific variables as shown in the code:
 236         // x1 is the original x, x2 is when mentioned in the closure,
 237         // and x3 is when mentioned in the closure in the closure.
 238         //
 239         // We keep these linked (assume N > 1):
 240         //
 241         //   - x1.Defn = original declaration statement for x (like most variables)
 242         //   - x1.Innermost = current innermost closure x (in this case x3), or nil for none
 243         //   - x1.isClosureVar() = false
 244         //
 245         //   - xN.Defn = x1, N > 1
 246         //   - xN.isClosureVar() = true, N > 1
 247         //   - x2.Outer = nil
 248         //   - xN.Outer = x(N-1), N > 2
 249         //
 250         //
 251         // When we look up x in the symbol table, we always get x1.
 252         // Then we can use x1.Innermost (if not nil) to get the x
 253         // for the innermost known closure function,
 254         // but the first reference in a closure will find either no x1.Innermost
 255         // or an x1.Innermost with .Funcdepth < Funcdepth.
 256         // In that case, a new xN must be created, linked in with:
 257         //
 258         //     xN.Defn = x1
 259         //     xN.Outer = x1.Innermost
 260         //     x1.Innermost = xN
 261         //
 262         // When we finish the function, we'll process its closure variables
 263         // and find xN and pop it off the list using:
 264         //
 265         //     x1 := xN.Defn
 266         //     x1.Innermost = xN.Outer
 267         //
 268         // We leave xN.Innermost set so that we can still get to the original
 269         // variable quickly. Not shown here, but once we're
 270         // done parsing a function and no longer need xN.Outer for the
 271         // lexical x reference links as described above, closurebody
 272         // recomputes xN.Outer as the semantic x reference link tree,
 273         // even filling in x in intermediate closures that might not
 274         // have mentioned it along the way to inner closures that did.
 275         // See closurebody for details.
 276         //
 277         // During the eventual compilation, then, for closure variables we have:
 278         //
 279         //     xN.Defn = original variable
 280         //     xN.Outer = variable captured in next outward scope
 281         //                to make closure where xN appears
 282         //
 283         // Because of the sharding of pieces of the node, x.Defn means x.Name.Defn
 284         // and x.Innermost/Outer means x.Name.Param.Innermost/Outer.
 285         Innermost *Node
 286         Outer     *Node
 287
 288         // OTYPE pragmas
 289         //
 290         // TODO: Should Func pragmas also be stored on the Name?
 291         Pragma syntax.Pragma
 292 }
 293
 294 // Func holds Node fields used only with function-like nodes.
 295 type Func struct {
 296         Shortname  *Node
 297         Enter      Nodes // for example, allocate and initialize memory for escaping parameters
 298         Exit       Nodes
 299         Cvars      Nodes   // closure params
 300         Dcl        []*Node // autodcl for this func/closure
 301         Inldcl     Nodes   // copy of dcl for use in inlining
 302         Closgen    int
 303         Outerfunc  *Node // outer function (for closure)
 304         FieldTrack map[*Sym]struct{}
 305         Ntype      *Node // signature
 306         Top        int   // top context (Ecall, Eproc, etc)
 307         Closure    *Node // OCLOSURE <-> ODCLFUNC
 308         Nname      *Node
 309
 310         Inl     Nodes // copy of the body for use in inlining
 311         InlCost int32
 312         Depth   int32
 313
 314         Label int32 // largest auto-generated label in this function
 315
 316         Endlineno src.XPos
 317         WBPos     src.XPos // position of first write barrier
 318
 319         Pragma          syntax.Pragma // go:xxx function annotations
 320         Dupok           bool          // duplicate definitions ok
 321         Wrapper         bool          // is method wrapper
 322         Needctxt        bool          // function uses context register (has closure variables)
 323         ReflectMethod   bool          // function calls reflect.Type.Method or MethodByName
 324         IsHiddenClosure bool
 325         NoFramePointer  bool // Must not use a frame pointer for this function
 326 }
 327
 328 type Op uint8
 329
 330 // Node ops.
 331 const (
 332         OXXX = Op(iota)
 333
 334         // names
 335         ONAME    // var, const or func name
 336         ONONAME  // unnamed arg or return value: f(int, string) (int, error) { etc }
 337         OTYPE    // type name
 338         OPACK    // import
 339         OLITERAL // literal
 340
 341         // expressions
 342         OADD             // Left + Right
 343         OSUB             // Left - Right
 344         OOR              // Left | Right
 345         OXOR             // Left ^ Right
 346         OADDSTR          // +{List} (string addition, list elements are strings)
 347         OADDR            // &Left
 348         OANDAND          // Left && Right
 349         OAPPEND          // append(List)
 350         OARRAYBYTESTR    // Type(Left) (Type is string, Left is a []byte)
 351         OARRAYBYTESTRTMP // Type(Left) (Type is string, Left is a []byte, ephemeral)
 352         OARRAYRUNESTR    // Type(Left) (Type is string, Left is a []rune)
 353         OSTRARRAYBYTE    // Type(Left) (Type is []byte, Left is a string)
 354         OSTRARRAYBYTETMP // Type(Left) (Type is []byte, Left is a string, ephemeral)
 355         OSTRARRAYRUNE    // Type(Left) (Type is []rune, Left is a string)
 356         OAS              // Left = Right or (if Colas=true) Left := Right
 357         OAS2             // List = Rlist (x, y, z = a, b, c)
 358         OAS2FUNC         // List = Rlist (x, y = f())
 359         OAS2RECV         // List = Rlist (x, ok = <-c)
 360         OAS2MAPR         // List = Rlist (x, ok = m["foo"])
 361         OAS2DOTTYPE      // List = Rlist (x, ok = I.(int))
 362         OASOP            // Left Etype= Right (x += y)
 363         OASWB            // Left = Right (with write barrier)
 364         OCALL            // Left(List) (function call, method call or type conversion)
 365         OCALLFUNC        // Left(List) (function call f(args))
 366         OCALLMETH        // Left(List) (direct method call x.Method(args))
 367         OCALLINTER       // Left(List) (interface method call x.Method(args))
 368         OCALLPART        // Left.Right (method expression x.Method, not called)
 369         OCAP             // cap(Left)
 370         OCLOSE           // close(Left)
 371         OCLOSURE         // func Type { Body } (func literal)
 372         OCMPIFACE        // Left Etype Right (interface comparison, x == y or x != y)
 373         OCMPSTR          // Left Etype Right (string comparison, x == y, x < y, etc)
 374         OCOMPLIT         // Right{List} (composite literal, not yet lowered to specific form)
 375         OMAPLIT          // Type{List} (composite literal, Type is map)
 376         OSTRUCTLIT       // Type{List} (composite literal, Type is struct)
 377         OARRAYLIT        // Type{List} (composite literal, Type is array)
 378         OSLICELIT        // Type{List} (composite literal, Type is slice)
 379         OPTRLIT          // &Left (left is composite literal)
 380         OCONV            // Type(Left) (type conversion)
 381         OCONVIFACE       // Type(Left) (type conversion, to interface)
 382         OCONVNOP         // Type(Left) (type conversion, no effect)
 383         OCOPY            // copy(Left, Right)
 384         ODCL             // var Left (declares Left of type Left.Type)
 385
 386         // Used during parsing but don't last.
 387         ODCLFUNC  // func f() or func (r) f()
 388         ODCLFIELD // struct field, interface field, or func/method argument/return value.
 389         ODCLCONST // const pi = 3.14
 390         ODCLTYPE  // type Int int
 391
 392         ODELETE    // delete(Left, Right)
 393         ODOT       // Left.Sym (Left is of struct type)
 394         ODOTPTR    // Left.Sym (Left is of pointer to struct type)
 395         ODOTMETH   // Left.Sym (Left is non-interface, Right is method name)
 396         ODOTINTER  // Left.Sym (Left is interface, Right is method name)
 397         OXDOT      // Left.Sym (before rewrite to one of the preceding)
 398         ODOTTYPE   // Left.Right or Left.Type (.Right during parsing, .Type once resolved)
 399         ODOTTYPE2  // Left.Right or Left.Type (.Right during parsing, .Type once resolved; on rhs of OAS2DOTTYPE)
 400         OEQ        // Left == Right
 401         ONE        // Left != Right
 402         OLT        // Left < Right
 403         OLE        // Left <= Right
 404         OGE        // Left >= Right
 405         OGT        // Left > Right
 406         OIND       // *Left
 407         OINDEX     // Left[Right] (index of array or slice)
 408         OINDEXMAP  // Left[Right] (index of map)
 409         OKEY       // Left:Right (key:value in struct/array/map literal)
 410         OSTRUCTKEY // Sym:Left (key:value in struct literal, after type checking)
 411         OLEN       // len(Left)
 412         OMAKE      // make(List) (before type checking converts to one of the following)
 413         OMAKECHAN  // make(Type, Left) (type is chan)
 414         OMAKEMAP   // make(Type, Left) (type is map)
 415         OMAKESLICE // make(Type, Left, Right) (type is slice)
 416         OMUL       // Left * Right
 417         ODIV       // Left / Right
 418         OMOD       // Left % Right
 419         OLSH       // Left << Right
 420         ORSH       // Left >> Right
 421         OAND       // Left & Right
 422         OANDNOT    // Left &^ Right
 423         ONEW       // new(Left)
 424         ONOT       // !Left
 425         OCOM       // ^Left
 426         OPLUS      // +Left
 427         OMINUS     // -Left
 428         OOROR      // Left || Right
 429         OPANIC     // panic(Left)
 430         OPRINT     // print(List)
 431         OPRINTN    // println(List)
 432         OPAREN     // (Left)
 433         OSEND      // Left <- Right
 434         OSLICE     // Left[List[0] : List[1]] (Left is untypechecked or slice)
 435         OSLICEARR  // Left[List[0] : List[1]] (Left is array)
 436         OSLICESTR  // Left[List[0] : List[1]] (Left is string)
 437         OSLICE3    // Left[List[0] : List[1] : List[2]] (Left is untypedchecked or slice)
 438         OSLICE3ARR // Left[List[0] : List[1] : List[2]] (Left is array)
 439         ORECOVER   // recover()
 440         ORECV      // <-Left
 441         ORUNESTR   // Type(Left) (Type is string, Left is rune)
 442         OSELRECV   // Left = <-Right.Left: (appears as .Left of OCASE; Right.Op == ORECV)
 443         OSELRECV2  // List = <-Right.Left: (apperas as .Left of OCASE; count(List) == 2, Right.Op == ORECV)
 444         OIOTA      // iota
 445         OREAL      // real(Left)
 446         OIMAG      // imag(Left)
 447         OCOMPLEX   // complex(Left, Right)
 448         OALIGNOF   // unsafe.Alignof(Left)
 449         OOFFSETOF  // unsafe.Offsetof(Left)
 450         OSIZEOF    // unsafe.Sizeof(Left)
 451
 452         // statements
 453         OBLOCK    // { List } (block of code)
 454         OBREAK    // break
 455         OCASE     // case Left or List[0]..List[1]: Nbody (select case after processing; Left==nil and List==nil means default)
 456         OXCASE    // case List: Nbody (select case before processing; List==nil means default)
 457         OCONTINUE // continue
 458         ODEFER    // defer Left (Left must be call)
 459         OEMPTY    // no-op (empty statement)
 460         OFALL     // fallthrough (after processing)
 461         OXFALL    // fallthrough (before processing)
 462         OFOR      // for Ninit; Left; Right { Nbody }
 463         OGOTO     // goto Left
 464         OIF       // if Ninit; Left { Nbody } else { Rlist }
 465         OLABEL    // Left:
 466         OPROC     // go Left (Left must be call)
 467         ORANGE    // for List = range Right { Nbody }
 468         ORETURN   // return List
 469         OSELECT   // select { List } (List is list of OXCASE or OCASE)
 470         OSWITCH   // switch Ninit; Left { List } (List is a list of OXCASE or OCASE)
 471         OTYPESW   // List = Left.(type) (appears as .Left of OSWITCH)
 472
 473         // types
 474         OTCHAN   // chan int
 475         OTMAP    // map[string]int
 476         OTSTRUCT // struct{}
 477         OTINTER  // interface{}
 478         OTFUNC   // func()
 479         OTARRAY  // []int, [8]int, [N]int or [...]int
 480
 481         // misc
 482         ODDD        // func f(args ...int) or f(l...) or var a = [...]int{0, 1, 2}.
 483         ODDDARG     // func f(args ...int), introduced by escape analysis.
 484         OINLCALL    // intermediary representation of an inlined call.
 485         OEFACE      // itable and data words of an empty-interface value.
 486         OITAB       // itable word of an interface value.
 487         OIDATA      // data word of an interface value in Left
 488         OSPTR       // base pointer of a slice or string.
 489         OCLOSUREVAR // variable reference at beginning of closure function
 490         OCFUNC      // reference to c function pointer (not go func value)
 491         OCHECKNIL   // emit code to ensure pointer/interface not nil
 492         OVARKILL    // variable is dead
 493         OVARLIVE    // variable is alive
 494         OINDREGSP   // offset plus indirect of REGSP, such as 8(SP).
 495
 496         // arch-specific opcodes
 497         OCMP    // compare: ACMP.
 498         ODEC    // decrement: ADEC.
 499         OINC    // increment: AINC.
 500         OEXTEND // extend: ACWD/ACDQ/ACQO.
 501         OHMUL   // high mul: AMUL/AIMUL for unsigned/signed (OMUL uses AIMUL for both).
 502         OLROT   // left rotate: AROL.
 503         ORROTC  // right rotate-carry: ARCR.
 504         ORETJMP // return to other function
 505         OPS     // compare parity set (for x86 NaN check)
 506         OPC     // compare parity clear (for x86 NaN check)
 507         OSQRT   // sqrt(float64), on systems that have hw support
 508         OGETG   // runtime.getg() (read g pointer)
 509
 510         OEND
 511 )
 512
 513 // Nodes is a pointer to a slice of *Node.
 514 // For fields that are not used in most nodes, this is used instead of
 515 // a slice to save space.
 516 type Nodes struct{ slice *[]*Node }
 517
 518 // Slice returns the entries in Nodes as a slice.
 519 // Changes to the slice entries (as in s[i] = n) will be reflected in
 520 // the Nodes.
 521 func (n Nodes) Slice() []*Node {
 522         if n.slice == nil {
 523                 return nil
 524         }
 525         return *n.slice
 526 }
 527
 528 // Len returns the number of entries in Nodes.
 529 func (n Nodes) Len() int {
 530         if n.slice == nil {
 531                 return 0
 532         }
 533         return len(*n.slice)
 534 }
 535
 536 // Index returns the i'th element of Nodes.
 537 // It panics if n does not have at least i+1 elements.
 538 func (n Nodes) Index(i int) *Node {
 539         return (*n.slice)[i]
 540 }
 541
 542 // First returns the first element of Nodes (same as n.Index(0)).
 543 // It panics if n has no elements.
 544 func (n Nodes) First() *Node {
 545         return (*n.slice)[0]
 546 }
 547
 548 // Second returns the second element of Nodes (same as n.Index(1)).
 549 // It panics if n has fewer than two elements.
 550 func (n Nodes) Second() *Node {
 551         return (*n.slice)[1]
 552 }
 553
 554 // Set sets n to a slice.
 555 // This takes ownership of the slice.
 556 func (n *Nodes) Set(s []*Node) {
 557         if len(s) == 0 {
 558                 n.slice = nil
 559         } else {
 560                 // Copy s and take address of t rather than s to avoid
 561                 // allocation in the case where len(s) == 0 (which is
 562                 // over 3x more common, dynamically, for make.bash).
 563                 t := s
 564                 n.slice = &t
 565         }
 566 }
 567
 568 // Set1 sets n to a slice containing a single node.
 569 func (n *Nodes) Set1(node *Node) {
 570         n.slice = &[]*Node{node}
 571 }
 572
 573 // Set2 sets n to a slice containing two nodes.
 574 func (n *Nodes) Set2(n1, n2 *Node) {
 575         n.slice = &[]*Node{n1, n2}
 576 }
 577
 578 // MoveNodes sets n to the contents of n2, then clears n2.
 579 func (n *Nodes) MoveNodes(n2 *Nodes) {
 580         n.slice = n2.slice
 581         n2.slice = nil
 582 }
 583
 584 // SetIndex sets the i'th element of Nodes to node.
 585 // It panics if n does not have at least i+1 elements.
 586 func (n Nodes) SetIndex(i int, node *Node) {
 587         (*n.slice)[i] = node
 588 }
 589
 590 // Addr returns the address of the i'th element of Nodes.
 591 // It panics if n does not have at least i+1 elements.
 592 func (n Nodes) Addr(i int) **Node {
 593         return &(*n.slice)[i]
 594 }
 595
 596 // Append appends entries to Nodes.
 597 // If a slice is passed in, this will take ownership of it.
 598 func (n *Nodes) Append(a ...*Node) {
 599         if len(a) == 0 {
 600                 return
 601         }
 602         if n.slice == nil {
 603                 n.slice = &a
 604         } else {
 605                 *n.slice = append(*n.slice, a...)
 606         }
 607 }
 608
 609 // Prepend prepends entries to Nodes.
 610 // If a slice is passed in, this will take ownership of it.
 611 func (n *Nodes) Prepend(a ...*Node) {
 612         if len(a) == 0 {
 613                 return
 614         }
 615         if n.slice == nil {
 616                 n.slice = &a
 617         } else {
 618                 *n.slice = append(a, *n.slice...)
 619         }
 620 }
 621
 622 // AppendNodes appends the contents of *n2 to n, then clears n2.
 623 func (n *Nodes) AppendNodes(n2 *Nodes) {
 624         switch {
 625         case n2.slice == nil:
 626         case n.slice == nil:
 627                 n.slice = n2.slice
 628         default:
 629                 *n.slice = append(*n.slice, *n2.slice...)
 630         }
 631         n2.slice = nil
 632 }