cmd/compile: replace calls to typecheck with transform functions

For additions, compares, and slices, create transform functions that do
just the transformations for those nodes by the typecheck package (given
that the code has been fully typechecked by types2). For nodes that have
no args with typeparams, we call these transform functions directly in
noder2. But for nodes that have args with typeparams, we have to delay
and call the tranform functions during stenciling, since we don't know
the specific types involved.

We indicate that a node still needs transformation by setting Typecheck
to a new value 3. This value means the current type of the node has been
set (via types2), but the node may still need transformation.

Had to export typcheck.IsCmp and typecheck.Assignop from the typecheck
package.

Added new tests list2.go (required delaying compare typecheck/transform
because of != compare in checkList) and adder.go (requires delaying add
typecheck/transform, since it can do addition for numbers or strings).

There are several more transformation functions needed for expressions
(indexing, calls, etc.) and several more complicated ones needed for
statements (mainly various kinds of assignments).

Change-Id: I7d89d13a4108308ea0304a4b815ab60b40c59b0a
Reviewed-on: https://go-review.googlesource.com/c/go/+/303091
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Dan Scales <danscales@google.com>
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

10 files changed, 785 insertions, 24 deletions

diff --git a/src/cmd/compile/internal/ir/node.go b/src/cmd/compile/internal/ir/node.go
index 38f9123582..7bce0e985c 100644
--- a/src/cmd/compile/internal/ir/node.go
+++ b/src/cmd/compile/internal/ir/node.go
@@ -48,6 +48,12 @@ type Node interface {
 	SetEsc(x uint16)
 	Diag() bool
 	SetDiag(x bool)
+
+	// Typecheck values:
+	//  0 means the node is not typechecked
+	//  1 means the node is completely typechecked
+	//  2 means typechecking of the node is in progress
+	//  3 means the node has its type from types2, but may need transformation
 	Typecheck() uint8
 	SetTypecheck(x uint8)
 	NonNil() bool
diff --git a/src/cmd/compile/internal/noder/expr.go b/src/cmd/compile/internal/noder/expr.go
index 957295bdf0..effc63c09a 100644
--- a/src/cmd/compile/internal/noder/expr.go
+++ b/src/cmd/compile/internal/noder/expr.go
@@ -64,7 +64,7 @@ func (g *irgen) expr(expr syntax.Expr) ir.Node {
 	}
 
 	n := g.expr0(typ, expr)
-	if n.Typecheck() != 1 {
+	if n.Typecheck() != 1 && n.Typecheck() != 3 {
 		base.FatalfAt(g.pos(expr), "missed typecheck: %+v", n)
 	}
 	if !g.match(n.Type(), typ, tv.HasOk()) {
@@ -161,7 +161,7 @@ func (g *irgen) expr0(typ types2.Type, expr syntax.Expr) ir.Node {
 		return g.selectorExpr(pos, typ, expr)
 
 	case *syntax.SliceExpr:
-		return Slice(pos, g.expr(expr.X), g.expr(expr.Index[0]), g.expr(expr.Index[1]), g.expr(expr.Index[2]))
+		return Slice(pos, g.typ(typ), g.expr(expr.X), g.expr(expr.Index[0]), g.expr(expr.Index[1]), g.expr(expr.Index[2]))
 
 	case *syntax.Operation:
 		if expr.Y == nil {
@@ -171,7 +171,7 @@ func (g *irgen) expr0(typ types2.Type, expr syntax.Expr) ir.Node {
 		case ir.OEQ, ir.ONE, ir.OLT, ir.OLE, ir.OGT, ir.OGE:
 			return Compare(pos, g.typ(typ), op, g.expr(expr.X), g.expr(expr.Y))
 		default:
-			return Binary(pos, op, g.expr(expr.X), g.expr(expr.Y))
+			return Binary(pos, op, g.typ(typ), g.expr(expr.X), g.expr(expr.Y))
 		}
 
 	default:
diff --git a/src/cmd/compile/internal/noder/helpers.go b/src/cmd/compile/internal/noder/helpers.go
index 1210d4b58c..e4a1a54fe8 100644
--- a/src/cmd/compile/internal/noder/helpers.go
+++ b/src/cmd/compile/internal/noder/helpers.go
@@ -67,16 +67,47 @@ func Assert(pos src.XPos, x ir.Node, typ *types.Type) ir.Node {
 	return typed(typ, ir.NewTypeAssertExpr(pos, x, nil))
 }
 
-func Binary(pos src.XPos, op ir.Op, x, y ir.Node) ir.Node {
+// transformAdd transforms an addition operation (currently just addition of
+// strings). Equivalent to the "binary operators" case in typecheck.typecheck1.
+func transformAdd(n *ir.BinaryExpr) ir.Node {
+	l := n.X
+	if l.Type().IsString() {
+		var add *ir.AddStringExpr
+		if l.Op() == ir.OADDSTR {
+			add = l.(*ir.AddStringExpr)
+			add.SetPos(n.Pos())
+		} else {
+			add = ir.NewAddStringExpr(n.Pos(), []ir.Node{l})
+		}
+		r := n.Y
+		if r.Op() == ir.OADDSTR {
+			r := r.(*ir.AddStringExpr)
+			add.List.Append(r.List.Take()...)
+		} else {
+			add.List.Append(r)
+		}
+		add.SetType(l.Type())
+		return add
+	}
+	return n
+}
+
+func Binary(pos src.XPos, op ir.Op, typ *types.Type, x, y ir.Node) ir.Node {
 	switch op {
 	case ir.OANDAND, ir.OOROR:
 		return typed(x.Type(), ir.NewLogicalExpr(pos, op, x, y))
 	case ir.OADD:
-		if x.Type().IsString() {
-			// TODO(mdempsky): Construct OADDSTR directly.
-			return typecheck.Expr(ir.NewBinaryExpr(pos, op, x, y))
+		n := ir.NewBinaryExpr(pos, op, x, y)
+		if x.Type().HasTParam() || y.Type().HasTParam() {
+			// Delay transformAdd() if either arg has a type param,
+			// since it needs to know the exact types to decide whether
+			// to transform OADD to OADDSTR.
+			n.SetType(typ)
+			n.SetTypecheck(3)
+			return n
 		}
-		fallthrough
+		n1 := transformAdd(n)
+		return typed(typ, n1)
 	default:
 		return typed(x.Type(), ir.NewBinaryExpr(pos, op, x, y))
 	}
@@ -178,12 +209,56 @@ func Call(pos src.XPos, typ *types.Type, fun ir.Node, args []ir.Node, dots bool)
 	return n
 }
 
+// transformCompare transforms a compare operation (currently just equals/not
+// equals). Equivalent to the "comparison operators" case in
+// typecheck.typecheck1, including tcArith.
+func transformCompare(n *ir.BinaryExpr) {
+	if (n.Op() == ir.OEQ || n.Op() == ir.ONE) && !types.Identical(n.X.Type(), n.Y.Type()) {
+		// Comparison is okay as long as one side is assignable to the
+		// other. The only allowed case where the conversion is not CONVNOP is
+		// "concrete == interface". In that case, check comparability of
+		// the concrete type. The conversion allocates, so only do it if
+		// the concrete type is huge.
+		l, r := n.X, n.Y
+		lt, rt := l.Type(), r.Type()
+		converted := false
+		if rt.Kind() != types.TBLANK {
+			aop, _ := typecheck.Assignop(lt, rt)
+			if aop != ir.OXXX {
+				types.CalcSize(lt)
+				if rt.IsInterface() == lt.IsInterface() || lt.Width >= 1<<16 {
+					l = ir.NewConvExpr(base.Pos, aop, rt, l)
+					l.SetTypecheck(1)
+				}
+
+				converted = true
+			}
+		}
+
+		if !converted && lt.Kind() != types.TBLANK {
+			aop, _ := typecheck.Assignop(rt, lt)
+			if aop != ir.OXXX {
+				types.CalcSize(rt)
+				if rt.IsInterface() == lt.IsInterface() || rt.Width >= 1<<16 {
+					r = ir.NewConvExpr(base.Pos, aop, lt, r)
+					r.SetTypecheck(1)
+				}
+			}
+		}
+		n.X, n.Y = l, r
+	}
+}
+
 func Compare(pos src.XPos, typ *types.Type, op ir.Op, x, y ir.Node) ir.Node {
 	n := ir.NewBinaryExpr(pos, op, x, y)
-	if !types.Identical(x.Type(), y.Type()) {
-		// TODO(mdempsky): Handle subtleties of constructing mixed-typed comparisons.
-		n = typecheck.Expr(n).(*ir.BinaryExpr)
+	if x.Type().HasTParam() || y.Type().HasTParam() {
+		// Delay transformCompare() if either arg has a type param, since
+		// it needs to know the exact types to decide on any needed conversions.
+		n.SetType(typ)
+		n.SetTypecheck(3)
+		return n
 	}
+	transformCompare(n)
 	return typed(typ, n)
 }
 
@@ -267,13 +342,42 @@ func Index(pos src.XPos, typ *types.Type, x, index ir.Node) ir.Node {
 	return typecheck.Expr(n)
 }
 
-func Slice(pos src.XPos, x, low, high, max ir.Node) ir.Node {
+// transformSlice transforms a slice operation.  Equivalent to typecheck.tcSlice.
+func transformSlice(n *ir.SliceExpr) {
+	l := n.X
+	if l.Type().IsArray() {
+		addr := typecheck.NodAddr(n.X)
+		addr.SetImplicit(true)
+		typed(types.NewPtr(n.X.Type()), addr)
+		n.X = addr
+		l = addr
+	}
+	t := l.Type()
+	if t.IsString() {
+		n.SetOp(ir.OSLICESTR)
+	} else if t.IsPtr() && t.Elem().IsArray() {
+		if n.Op().IsSlice3() {
+			n.SetOp(ir.OSLICE3ARR)
+		} else {
+			n.SetOp(ir.OSLICEARR)
+		}
+	}
+}
+
+func Slice(pos src.XPos, typ *types.Type, x, low, high, max ir.Node) ir.Node {
 	op := ir.OSLICE
 	if max != nil {
 		op = ir.OSLICE3
 	}
-	// TODO(mdempsky): Avoid typecheck.Expr.
-	return typecheck.Expr(ir.NewSliceExpr(pos, op, x, low, high, max))
+	n := ir.NewSliceExpr(pos, op, x, low, high, max)
+	if x.Type().HasTParam() {
+		// transformSlice needs to know if x.Type() is a string or an array or a slice.
+		n.SetType(typ)
+		n.SetTypecheck(3)
+		return n
+	}
+	transformSlice(n)
+	return typed(typ, n)
 }
 
 func Unary(pos src.XPos, op ir.Op, x ir.Node) ir.Node {
diff --git a/src/cmd/compile/internal/noder/stencil.go b/src/cmd/compile/internal/noder/stencil.go
index 51ef46c7e7..1b76bb27c5 100644
--- a/src/cmd/compile/internal/noder/stencil.go
+++ b/src/cmd/compile/internal/noder/stencil.go
@@ -367,6 +367,23 @@ func (subst *subster) node(n ir.Node) ir.Node {
 		}
 		ir.EditChildren(m, edit)
 
+		if x.Typecheck() == 3 {
+			// These are nodes whose transforms were delayed until
+			// their instantiated type was known.
+			if typecheck.IsCmp(x.Op()) {
+				transformCompare(m.(*ir.BinaryExpr))
+				m.SetTypecheck(1)
+			} else if x.Op() == ir.OSLICE || x.Op() == ir.OSLICE3 {
+				transformSlice(m.(*ir.SliceExpr))
+				m.SetTypecheck(1)
+			} else if x.Op() == ir.OADD {
+				m = transformAdd(m.(*ir.BinaryExpr))
+				m.SetTypecheck(1)
+			} else {
+				base.Fatalf("Unexpected node with Typecheck() == 3")
+			}
+		}
+
 		switch x.Op() {
 		case ir.OLITERAL:
 			t := m.Type()
diff --git a/src/cmd/compile/internal/typecheck/expr.go b/src/cmd/compile/internal/typecheck/expr.go
index 10a4c1b1dc..fb39709686 100644
--- a/src/cmd/compile/internal/typecheck/expr.go
+++ b/src/cmd/compile/internal/typecheck/expr.go
@@ -77,6 +77,10 @@ func tcShift(n, l, r ir.Node) (ir.Node, ir.Node, *types.Type) {
 	return l, r, t
 }
 
+func IsCmp(op ir.Op) bool {
+	return iscmp[op]
+}
+
 // tcArith typechecks operands of a binary arithmetic expression.
 // The result of tcArith MUST be assigned back to original operands,
 // t is the type of the expression, and should be set by the caller. e.g:
@@ -102,7 +106,7 @@ func tcArith(n ir.Node, op ir.Op, l, r ir.Node) (ir.Node, ir.Node, *types.Type)
 		// The conversion allocates, so only do it if the concrete type is huge.
 		converted := false
 		if r.Type().Kind() != types.TBLANK {
-			aop, _ = assignop(l.Type(), r.Type())
+			aop, _ = Assignop(l.Type(), r.Type())
 			if aop != ir.OXXX {
 				if r.Type().IsInterface() && !l.Type().IsInterface() && !types.IsComparable(l.Type()) {
 					base.Errorf("invalid operation: %v (operator %v not defined on %s)", n, op, typekind(l.Type()))
@@ -121,7 +125,7 @@ func tcArith(n ir.Node, op ir.Op, l, r ir.Node) (ir.Node, ir.Node, *types.Type)
 		}
 
 		if !converted && l.Type().Kind() != types.TBLANK {
-			aop, _ = assignop(r.Type(), l.Type())
+			aop, _ = Assignop(r.Type(), l.Type())
 			if aop != ir.OXXX {
 				if l.Type().IsInterface() && !r.Type().IsInterface() && !types.IsComparable(r.Type()) {
 					base.Errorf("invalid operation: %v (operator %v not defined on %s)", n, op, typekind(r.Type()))
diff --git a/src/cmd/compile/internal/typecheck/stmt.go b/src/cmd/compile/internal/typecheck/stmt.go
index 14ed175be9..175216f279 100644
--- a/src/cmd/compile/internal/typecheck/stmt.go
+++ b/src/cmd/compile/internal/typecheck/stmt.go
@@ -74,7 +74,7 @@ func typecheckrangeExpr(n *ir.RangeStmt) {
 			if ir.DeclaredBy(nn, n) {
 				nn.SetType(t)
 			} else if nn.Type() != nil {
-				if op, why := assignop(t, nn.Type()); op == ir.OXXX {
+				if op, why := Assignop(t, nn.Type()); op == ir.OXXX {
 					base.ErrorfAt(n.Pos(), "cannot assign type %v to %L in range%s", t, nn, why)
 				}
 			}
@@ -519,8 +519,8 @@ func tcSwitchExpr(n *ir.SwitchStmt) {
 			} else if t.IsInterface() && !n1.Type().IsInterface() && !types.IsComparable(n1.Type()) {
 				base.ErrorfAt(ncase.Pos(), "invalid case %L in switch (incomparable type)", n1)
 			} else {
-				op1, _ := assignop(n1.Type(), t)
-				op2, _ := assignop(t, n1.Type())
+				op1, _ := Assignop(n1.Type(), t)
+				op2, _ := Assignop(t, n1.Type())
 				if op1 == ir.OXXX && op2 == ir.OXXX {
 					if n.Tag != nil {
 						base.ErrorfAt(ncase.Pos(), "invalid case %v in switch on %v (mismatched types %v and %v)", n1, n.Tag, n1.Type(), t)
diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go
index c40cfa2288..e58ef9fb05 100644
--- a/src/cmd/compile/internal/typecheck/subr.go
+++ b/src/cmd/compile/internal/typecheck/subr.go
@@ -317,7 +317,7 @@ func assignconvfn(n ir.Node, t *types.Type, context func() string) ir.Node {
 		return n
 	}
 
-	op, why := assignop(n.Type(), t)
+	op, why := Assignop(n.Type(), t)
 	if op == ir.OXXX {
 		base.Errorf("cannot use %L as type %v in %s%s", n, t, context(), why)
 		op = ir.OCONV
@@ -333,7 +333,7 @@ func assignconvfn(n ir.Node, t *types.Type, context func() string) ir.Node {
 // If so, return op code to use in conversion.
 // If not, return OXXX. In this case, the string return parameter may
 // hold a reason why. In all other cases, it'll be the empty string.
-func assignop(src, dst *types.Type) (ir.Op, string) {
+func Assignop(src, dst *types.Type) (ir.Op, string) {
 	if src == dst {
 		return ir.OCONVNOP, ""
 	}
@@ -483,7 +483,7 @@ func convertop(srcConstant bool, src, dst *types.Type) (ir.Op, string) {
 	}
 
 	// 1. src can be assigned to dst.
-	op, why := assignop(src, dst)
+	op, why := Assignop(src, dst)
 	if op != ir.OXXX {
 		return op, why
 	}
diff --git a/src/cmd/compile/internal/typecheck/typecheck.go b/src/cmd/compile/internal/typecheck/typecheck.go
index 30632ac18b..f06a8623d0 100644
--- a/src/cmd/compile/internal/typecheck/typecheck.go
+++ b/src/cmd/compile/internal/typecheck/typecheck.go
@@ -297,7 +297,7 @@ func typecheck(n ir.Node, top int) (res ir.Node) {
 
 	// Skip typecheck if already done.
 	// But re-typecheck ONAME/OTYPE/OLITERAL/OPACK node in case context has changed.
-	if n.Typecheck() == 1 {
+	if n.Typecheck() == 1 || n.Typecheck() == 3 {
 		switch n.Op() {
 		case ir.ONAME, ir.OTYPE, ir.OLITERAL, ir.OPACK:
 			break
@@ -1640,7 +1640,7 @@ func checkassignto(src *types.Type, dst ir.Node) {
 		return
 	}
 
-	if op, why := assignop(src, dst.Type()); op == ir.OXXX {
+	if op, why := Assignop(src, dst.Type()); op == ir.OXXX {
 		base.Errorf("cannot assign %v to %L in multiple assignment%s", src, dst, why)
 		return
 	}
diff --git a/test/typeparam/adder.go b/test/typeparam/adder.go
new file mode 100644
index 0000000000..0c25ad4ef2
--- /dev/null
+++ b/test/typeparam/adder.go
@@ -0,0 +1,29 @@
+// run -gcflags=-G=3
+
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"fmt"
+)
+
+type AddType interface {
+	type int, int64, string
+}
+
+// _Add can add numbers or strings
+func _Add[T AddType](a, b T) T {
+	return a + b
+}
+
+func main() {
+	if got, want := _Add(5, 3), 8; got != want {
+		panic(fmt.Sprintf("got %d, want %d", got, want))
+	}
+	if got, want := _Add("ab", "cd"), "abcd"; got != want {
+		panic(fmt.Sprintf("got %d, want %d", got, want))
+	}
+}
diff --git a/test/typeparam/list2.go b/test/typeparam/list2.go
new file mode 100644
index 0000000000..385193d876
--- /dev/null
+++ b/test/typeparam/list2.go
@@ -0,0 +1,601 @@
+// run -gcflags=-G=3
+
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package list provides a doubly linked list of some element type
+// (generic form of the "container/list" package).
+
+package main
+
+import (
+	"fmt"
+	"strconv"
+)
+
+// Element is an element of a linked list.
+type _Element[T any] struct {
+	// Next and previous pointers in the doubly-linked list of elements.
+	// To simplify the implementation, internally a list l is implemented
+	// as a ring, such that &l.root is both the next element of the last
+	// list element (l.Back()) and the previous element of the first list
+	// element (l.Front()).
+	next, prev *_Element[T]
+
+	// The list to which this element belongs.
+	list *_List[T]
+
+	// The value stored with this element.
+	Value T
+}
+
+// Next returns the next list element or nil.
+func (e *_Element[T]) Next() *_Element[T] {
+	if p := e.next; e.list != nil && p != &e.list.root {
+		return p
+	}
+	return nil
+}
+
+// Prev returns the previous list element or nil.
+func (e *_Element[T]) Prev() *_Element[T] {
+	if p := e.prev; e.list != nil && p != &e.list.root {
+		return p
+	}
+	return nil
+}
+
+// _List represents a doubly linked list.
+// The zero value for _List is an empty list ready to use.
+type _List[T any] struct {
+	root _Element[T] // sentinel list element, only &root, root.prev, and root.next are used
+	len  int     // current list length excluding (this) sentinel element
+}
+
+// Init initializes or clears list l.
+func (l *_List[T]) Init() *_List[T] {
+	l.root.next = &l.root
+	l.root.prev = &l.root
+	l.len = 0
+	return l
+}
+
+// New returns an initialized list.
+func _New[T any]() *_List[T] { return new(_List[T]).Init() }
+
+// Len returns the number of elements of list l.
+// The complexity is O(1).
+func (l *_List[_]) Len() int { return l.len }
+
+// Front returns the first element of list l or nil if the list is empty.
+func (l *_List[T]) Front() *_Element[T] {
+	if l.len == 0 {
+		return nil
+	}
+	return l.root.next
+}
+
+// Back returns the last element of list l or nil if the list is empty.
+func (l *_List[T]) Back() *_Element[T] {
+	if l.len == 0 {
+		return nil
+	}
+	return l.root.prev
+}
+
+// lazyInit lazily initializes a zero _List value.
+func (l *_List[_]) lazyInit() {
+	if l.root.next == nil {
+		l.Init()
+	}
+}
+
+// insert inserts e after at, increments l.len, and returns e.
+func (l *_List[T]) insert(e, at *_Element[T]) *_Element[T] {
+	e.prev = at
+	e.next = at.next
+	e.prev.next = e
+	e.next.prev = e
+	e.list = l
+	l.len++
+	return e
+}
+
+// insertValue is a convenience wrapper for insert(&_Element[T]{Value: v}, at).
+func (l *_List[T]) insertValue(v T, at *_Element[T]) *_Element[T] {
+	return l.insert(&_Element[T]{Value: v}, at)
+}
+
+// remove removes e from its list, decrements l.len, and returns e.
+func (l *_List[T]) remove(e *_Element[T]) *_Element[T] {
+	e.prev.next = e.next
+	e.next.prev = e.prev
+	e.next = nil // avoid memory leaks
+	e.prev = nil // avoid memory leaks
+	e.list = nil
+	l.len--
+	return e
+}
+
+// move moves e to next to at and returns e.
+func (l *_List[T]) move(e, at *_Element[T]) *_Element[T] {
+	if e == at {
+		return e
+	}
+	e.prev.next = e.next
+	e.next.prev = e.prev
+
+	e.prev = at
+	e.next = at.next
+	e.prev.next = e
+	e.next.prev = e
+
+	return e
+}
+
+// Remove removes e from l if e is an element of list l.
+// It returns the element value e.Value.
+// The element must not be nil.
+func (l *_List[T]) Remove(e *_Element[T]) T {
+	if e.list == l {
+		// if e.list == l, l must have been initialized when e was inserted
+		// in l or l == nil (e is a zero _Element) and l.remove will crash
+		l.remove(e)
+	}
+	return e.Value
+}
+
+// PushFront inserts a new element e with value v at the front of list l and returns e.
+func (l *_List[T]) PushFront(v T) *_Element[T] {
+	l.lazyInit()
+	return l.insertValue(v, &l.root)
+}
+
+// PushBack inserts a new element e with value v at the back of list l and returns e.
+func (l *_List[T]) PushBack(v T) *_Element[T] {
+	l.lazyInit()
+	return l.insertValue(v, l.root.prev)
+}
+
+// InsertBefore inserts a new element e with value v immediately before mark and returns e.
+// If mark is not an element of l, the list is not modified.
+// The mark must not be nil.
+func (l *_List[T]) InsertBefore(v T, mark *_Element[T]) *_Element[T] {
+	if mark.list != l {
+		return nil
+	}
+	// see comment in _List.Remove about initialization of l
+	return l.insertValue(v, mark.prev)
+}
+
+// InsertAfter inserts a new element e with value v immediately after mark and returns e.
+// If mark is not an element of l, the list is not modified.
+// The mark must not be nil.
+func (l *_List[T]) InsertAfter(v T, mark *_Element[T]) *_Element[T] {
+	if mark.list != l {
+		return nil
+	}
+	// see comment in _List.Remove about initialization of l
+	return l.insertValue(v, mark)
+}
+
+// MoveToFront moves element e to the front of list l.
+// If e is not an element of l, the list is not modified.
+// The element must not be nil.
+func (l *_List[T]) MoveToFront(e *_Element[T]) {
+	if e.list != l || l.root.next == e {
+		return
+	}
+	// see comment in _List.Remove about initialization of l
+	l.move(e, &l.root)
+}
+
+// MoveToBack moves element e to the back of list l.
+// If e is not an element of l, the list is not modified.
+// The element must not be nil.
+func (l *_List[T]) MoveToBack(e *_Element[T]) {
+	if e.list != l || l.root.prev == e {
+		return
+	}
+	// see comment in _List.Remove about initialization of l
+	l.move(e, l.root.prev)
+}
+
+// MoveBefore moves element e to its new position before mark.
+// If e or mark is not an element of l, or e == mark, the list is not modified.
+// The element and mark must not be nil.
+func (l *_List[T]) MoveBefore(e, mark *_Element[T]) {
+	if e.list != l || e == mark || mark.list != l {
+		return
+	}
+	l.move(e, mark.prev)
+}
+
+// MoveAfter moves element e to its new position after mark.
+// If e or mark is not an element of l, or e == mark, the list is not modified.
+// The element and mark must not be nil.
+func (l *_List[T]) MoveAfter(e, mark *_Element[T]) {
+	if e.list != l || e == mark || mark.list != l {
+		return
+	}
+	l.move(e, mark)
+}
+
+// PushBackList inserts a copy of an other list at the back of list l.
+// The lists l and other may be the same. They must not be nil.
+func (l *_List[T]) PushBackList(other *_List[T]) {
+	l.lazyInit()
+	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
+		l.insertValue(e.Value, l.root.prev)
+	}
+}
+
+// PushFrontList inserts a copy of an other list at the front of list l.
+// The lists l and other may be the same. They must not be nil.
+func (l *_List[T]) PushFrontList(other *_List[T]) {
+	l.lazyInit()
+	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
+		l.insertValue(e.Value, &l.root)
+	}
+}
+
+// Transform runs a transform function on a list returning a new list.
+func _Transform[TElem1, TElem2 any](lst *_List[TElem1], f func(TElem1) TElem2) *_List[TElem2] {
+	ret := _New[TElem2]()
+	for p := lst.Front(); p != nil; p = p.Next() {
+		ret.PushBack(f(p.Value))
+	}
+	return ret
+}
+
+func checkListLen[T any](l *_List[T], len int) bool {
+	if n := l.Len(); n != len {
+		panic(fmt.Sprintf("l.Len() = %d, want %d", n, len))
+		return false
+	}
+	return true
+}
+
+func checkListPointers[T any](l *_List[T], es []*_Element[T]) {
+	root := &l.root
+
+	if !checkListLen(l, len(es)) {
+		return
+	}
+
+	// zero length lists must be the zero value or properly initialized (sentinel circle)
+	if len(es) == 0 {
+		if l.root.next != nil && l.root.next != root || l.root.prev != nil && l.root.prev != root {
+			panic(fmt.Sprintf("l.root.next = %p, l.root.prev = %p; both should both be nil or %p", l.root.next, l.root.prev, root))
+		}
+		return
+	}
+	// len(es) > 0
+
+	// check internal and external prev/next connections
+	for i, e := range es {
+		prev := root
+		Prev := (*_Element[T])(nil)
+		if i > 0 {
+			prev = es[i-1]
+			Prev = prev
+		}
+		if p := e.prev; p != prev {
+			panic(fmt.Sprintf("elt[%d](%p).prev = %p, want %p", i, e, p, prev))
+		}
+		if p := e.Prev(); p != Prev {
+			panic(fmt.Sprintf("elt[%d](%p).Prev() = %p, want %p", i, e, p, Prev))
+		}
+
+		next := root
+		Next := (*_Element[T])(nil)
+		if i < len(es)-1 {
+			next = es[i+1]
+			Next = next
+		}
+		if n := e.next; n != next {
+			panic(fmt.Sprintf("elt[%d](%p).next = %p, want %p", i, e, n, next))
+		}
+		if n := e.Next(); n != Next {
+			panic(fmt.Sprintf("elt[%d](%p).Next() = %p, want %p", i, e, n, Next))
+		}
+	}
+}
+
+func TestList() {
+	l := _New[string]()
+	checkListPointers(l, []*(_Element[string]){})
+
+	// Single element list
+	e := l.PushFront("a")
+	checkListPointers(l, []*(_Element[string]){e})
+	l.MoveToFront(e)
+	checkListPointers(l, []*(_Element[string]){e})
+	l.MoveToBack(e)
+	checkListPointers(l, []*(_Element[string]){e})
+	l.Remove(e)
+	checkListPointers(l, []*(_Element[string]){})
+
+	// Bigger list
+	l2 := _New[int]()
+	e2 := l2.PushFront(2)
+	e1 := l2.PushFront(1)
+	e3 := l2.PushBack(3)
+	e4 := l2.PushBack(600)
+	checkListPointers(l2, []*(_Element[int]){e1, e2, e3, e4})
+
+	l2.Remove(e2)
+	checkListPointers(l2, []*(_Element[int]){e1, e3, e4})
+
+	l2.MoveToFront(e3) // move from middle
+	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
+
+	l2.MoveToFront(e1)
+	l2.MoveToBack(e3) // move from middle
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
+
+	l2.MoveToFront(e3) // move from back
+	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
+	l2.MoveToFront(e3) // should be no-op
+	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
+
+	l2.MoveToBack(e3) // move from front
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
+	l2.MoveToBack(e3) // should be no-op
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
+
+	e2 = l2.InsertBefore(2, e1) // insert before front
+	checkListPointers(l2, []*(_Element[int]){e2, e1, e4, e3})
+	l2.Remove(e2)
+	e2 = l2.InsertBefore(2, e4) // insert before middle
+	checkListPointers(l2, []*(_Element[int]){e1, e2, e4, e3})
+	l2.Remove(e2)
+	e2 = l2.InsertBefore(2, e3) // insert before back
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e2, e3})
+	l2.Remove(e2)
+
+	e2 = l2.InsertAfter(2, e1) // insert after front
+	checkListPointers(l2, []*(_Element[int]){e1, e2, e4, e3})
+	l2.Remove(e2)
+	e2 = l2.InsertAfter(2, e4) // insert after middle
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e2, e3})
+	l2.Remove(e2)
+	e2 = l2.InsertAfter(2, e3) // insert after back
+	checkListPointers(l2, []*(_Element[int]){e1, e4, e3, e2})
+	l2.Remove(e2)
+
+	// Check standard iteration.
+	sum := 0
+	for e := l2.Front(); e != nil; e = e.Next() {
+		sum += e.Value
+	}
+	if sum != 604 {
+		panic(fmt.Sprintf("sum over l = %d, want 604", sum))
+	}
+
+	// Clear all elements by iterating
+	var next *_Element[int]
+	for e := l2.Front(); e != nil; e = next {
+		next = e.Next()
+		l2.Remove(e)
+	}
+	checkListPointers(l2, []*(_Element[int]){})
+}
+
+func checkList[T comparable](l *_List[T], es []interface{}) {
+	if !checkListLen(l, len(es)) {
+		return
+	}
+
+	i := 0
+	for e := l.Front(); e != nil; e = e.Next() {
+		le := e.Value
+		// Comparison between a generically-typed variable le and an interface.
+		if le != es[i] {
+			panic(fmt.Sprintf("elt[%d].Value = %v, want %v", i, le, es[i]))
+		}
+		i++
+	}
+}
+
+func TestExtending() {
+	l1 := _New[int]()
+	l2 := _New[int]()
+
+	l1.PushBack(1)
+	l1.PushBack(2)
+	l1.PushBack(3)
+
+	l2.PushBack(4)
+	l2.PushBack(5)
+
+	l3 := _New[int]()
+	l3.PushBackList(l1)
+	checkList(l3, []interface{}{1, 2, 3})
+	l3.PushBackList(l2)
+	checkList(l3, []interface{}{1, 2, 3, 4, 5})
+
+	l3 = _New[int]()
+	l3.PushFrontList(l2)
+	checkList(l3, []interface{}{4, 5})
+	l3.PushFrontList(l1)
+	checkList(l3, []interface{}{1, 2, 3, 4, 5})
+
+	checkList(l1, []interface{}{1, 2, 3})
+	checkList(l2, []interface{}{4, 5})
+
+	l3 = _New[int]()
+	l3.PushBackList(l1)
+	checkList(l3, []interface{}{1, 2, 3})
+	l3.PushBackList(l3)
+	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
+
+	l3 = _New[int]()
+	l3.PushFrontList(l1)
+	checkList(l3, []interface{}{1, 2, 3})
+	l3.PushFrontList(l3)
+	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
+
+	l3 = _New[int]()
+	l1.PushBackList(l3)
+	checkList(l1, []interface{}{1, 2, 3})
+	l1.PushFrontList(l3)
+	checkList(l1, []interface{}{1, 2, 3})
+}
+
+func TestRemove() {
+	l := _New[int]()
+	e1 := l.PushBack(1)
+	e2 := l.PushBack(2)
+	checkListPointers(l, []*(_Element[int]){e1, e2})
+	e := l.Front()
+	l.Remove(e)
+	checkListPointers(l, []*(_Element[int]){e2})
+	l.Remove(e)
+	checkListPointers(l, []*(_Element[int]){e2})
+}
+
+func TestIssue4103() {
+	l1 := _New[int]()
+	l1.PushBack(1)
+	l1.PushBack(2)
+
+	l2 := _New[int]()
+	l2.PushBack(3)
+	l2.PushBack(4)
+
+	e := l1.Front()
+	l2.Remove(e) // l2 should not change because e is not an element of l2
+	if n := l2.Len(); n != 2 {
+		panic(fmt.Sprintf("l2.Len() = %d, want 2", n))
+	}
+
+	l1.InsertBefore(8, e)
+	if n := l1.Len(); n != 3 {
+		panic(fmt.Sprintf("l1.Len() = %d, want 3", n))
+	}
+}
+
+func TestIssue6349() {
+	l := _New[int]()
+	l.PushBack(1)
+	l.PushBack(2)
+
+	e := l.Front()
+	l.Remove(e)
+	if e.Value != 1 {
+		panic(fmt.Sprintf("e.value = %d, want 1", e.Value))
+	}
+	if e.Next() != nil {
+		panic(fmt.Sprintf("e.Next() != nil"))
+	}
+	if e.Prev() != nil {
+		panic(fmt.Sprintf("e.Prev() != nil"))
+	}
+}
+
+func TestMove() {
+	l := _New[int]()
+	e1 := l.PushBack(1)
+	e2 := l.PushBack(2)
+	e3 := l.PushBack(3)
+	e4 := l.PushBack(4)
+
+	l.MoveAfter(e3, e3)
+	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
+	l.MoveBefore(e2, e2)
+	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
+
+	l.MoveAfter(e3, e2)
+	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
+	l.MoveBefore(e2, e3)
+	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
+
+	l.MoveBefore(e2, e4)
+	checkListPointers(l, []*(_Element[int]){e1, e3, e2, e4})
+	e2, e3 = e3, e2
+
+	l.MoveBefore(e4, e1)
+	checkListPointers(l, []*(_Element[int]){e4, e1, e2, e3})
+	e1, e2, e3, e4 = e4, e1, e2, e3
+
+	l.MoveAfter(e4, e1)
+	checkListPointers(l, []*(_Element[int]){e1, e4, e2, e3})
+	e2, e3, e4 = e4, e2, e3
+
+	l.MoveAfter(e2, e3)
+	checkListPointers(l, []*(_Element[int]){e1, e3, e2, e4})
+	e2, e3 = e3, e2
+}
+
+// Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized _List
+func TestZeroList() {
+	var l1 = new(_List[int])
+	l1.PushFront(1)
+	checkList(l1, []interface{}{1})
+
+	var l2 = new(_List[int])
+	l2.PushBack(1)
+	checkList(l2, []interface{}{1})
+
+	var l3 = new(_List[int])
+	l3.PushFrontList(l1)
+	checkList(l3, []interface{}{1})
+
+	var l4 = new(_List[int])
+	l4.PushBackList(l2)
+	checkList(l4, []interface{}{1})
+}
+
+// Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
+func TestInsertBeforeUnknownMark() {
+	var l _List[int]
+	l.PushBack(1)
+	l.PushBack(2)
+	l.PushBack(3)
+	l.InsertBefore(1, new(_Element[int]))
+	checkList(&l, []interface{}{1, 2, 3})
+}
+
+// Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
+func TestInsertAfterUnknownMark() {
+	var l _List[int]
+	l.PushBack(1)
+	l.PushBack(2)
+	l.PushBack(3)
+	l.InsertAfter(1, new(_Element[int]))
+	checkList(&l, []interface{}{1, 2, 3})
+}
+
+// Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
+func TestMoveUnknownMark() {
+	var l1 _List[int]
+	e1 := l1.PushBack(1)
+
+	var l2 _List[int]
+	e2 := l2.PushBack(2)
+
+	l1.MoveAfter(e1, e2)
+	checkList(&l1, []interface{}{1})
+	checkList(&l2, []interface{}{2})
+
+	l1.MoveBefore(e1, e2)
+	checkList(&l1, []interface{}{1})
+	checkList(&l2, []interface{}{2})
+}
+
+// Test the Transform function.
+func TestTransform() {
+	l1 := _New[int]()
+	l1.PushBack(1)
+	l1.PushBack(2)
+	l2 := _Transform(l1, strconv.Itoa)
+	checkList(l2, []interface{}{"1", "2"})
+}
+
+
+func main() {
+	TestList()
+}
+