From d29e59af9fbd420e34378bcbf7ae543134070217 Mon Sep 17 00:00:00 2001 From: Adin Scannell Date: Mon, 27 Jan 2020 10:04:07 -0800 Subject: Standardize on tools directory. PiperOrigin-RevId: 291745021 --- tools/go_generics/BUILD | 2 +- tools/go_generics/globals/BUILD | 4 ++-- tools/go_generics/go_merge/BUILD | 2 +- tools/go_generics/rules_tests/BUILD | 2 +- 4 files changed, 5 insertions(+), 5 deletions(-) (limited to 'tools/go_generics') diff --git a/tools/go_generics/BUILD b/tools/go_generics/BUILD index 39318b877..069df3856 100644 --- a/tools/go_generics/BUILD +++ b/tools/go_generics/BUILD @@ -1,4 +1,4 @@ -load("@io_bazel_rules_go//go:def.bzl", "go_binary") +load("//tools:defs.bzl", "go_binary") package(licenses = ["notice"]) diff --git a/tools/go_generics/globals/BUILD b/tools/go_generics/globals/BUILD index 74853c7d2..38caa3ce7 100644 --- a/tools/go_generics/globals/BUILD +++ b/tools/go_generics/globals/BUILD @@ -1,4 +1,4 @@ -load("@io_bazel_rules_go//go:def.bzl", "go_library") +load("//tools:defs.bzl", "go_library") package(licenses = ["notice"]) @@ -8,6 +8,6 @@ go_library( "globals_visitor.go", "scope.go", ], - importpath = "gvisor.dev/gvisor/tools/go_generics/globals", + stateify = False, visibility = ["//tools/go_generics:__pkg__"], ) diff --git a/tools/go_generics/go_merge/BUILD b/tools/go_generics/go_merge/BUILD index 02b09120e..b7d35e272 100644 --- a/tools/go_generics/go_merge/BUILD +++ b/tools/go_generics/go_merge/BUILD @@ -1,4 +1,4 @@ -load("@io_bazel_rules_go//go:def.bzl", "go_binary") +load("//tools:defs.bzl", "go_binary") package(licenses = ["notice"]) diff --git a/tools/go_generics/rules_tests/BUILD b/tools/go_generics/rules_tests/BUILD index 9d26a88b7..8a329dfc6 100644 --- a/tools/go_generics/rules_tests/BUILD +++ b/tools/go_generics/rules_tests/BUILD @@ -1,4 +1,4 @@ -load("@io_bazel_rules_go//go:def.bzl", "go_test") +load("//tools:defs.bzl", "go_test") load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance") package(licenses = ["notice"]) -- cgit v1.2.3 From 0efa8168c7c04ec0a4bd62e2d2eb8718b5d72ea7 Mon Sep 17 00:00:00 2001 From: Adin Scannell Date: Mon, 10 Feb 2020 11:28:57 -0800 Subject: Update visibility. PiperOrigin-RevId: 294265019 --- pkg/seccomp/BUILD | 2 +- test/root/testdata/BUILD | 2 +- tools/build/BUILD | 2 +- tools/checkunsafe/BUILD | 2 +- tools/go_generics/BUILD | 2 +- tools/go_generics/go_merge/BUILD | 2 +- tools/go_stateify/BUILD | 2 +- 7 files changed, 7 insertions(+), 7 deletions(-) (limited to 'tools/go_generics') diff --git a/pkg/seccomp/BUILD b/pkg/seccomp/BUILD index 742c8b79b..c5fca2ba3 100644 --- a/pkg/seccomp/BUILD +++ b/pkg/seccomp/BUILD @@ -26,7 +26,7 @@ go_library( "seccomp_rules.go", "seccomp_unsafe.go", ], - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], deps = [ "//pkg/abi/linux", "//pkg/bpf", diff --git a/test/root/testdata/BUILD b/test/root/testdata/BUILD index bca5f9cab..6859541ad 100644 --- a/test/root/testdata/BUILD +++ b/test/root/testdata/BUILD @@ -13,6 +13,6 @@ go_library( "simple.go", ], visibility = [ - "//visibility:public", + "//:sandbox", ], ) diff --git a/tools/build/BUILD b/tools/build/BUILD index 0c0ce3f4d..00a467473 100644 --- a/tools/build/BUILD +++ b/tools/build/BUILD @@ -6,5 +6,5 @@ genrule( name = "loopback", outs = ["loopback.txt"], cmd = "touch $@", - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], ) diff --git a/tools/checkunsafe/BUILD b/tools/checkunsafe/BUILD index 92ba8ab06..4f1a31a6d 100644 --- a/tools/checkunsafe/BUILD +++ b/tools/checkunsafe/BUILD @@ -5,7 +5,7 @@ package(licenses = ["notice"]) go_tool_library( name = "checkunsafe", srcs = ["check_unsafe.go"], - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], deps = [ "@org_golang_x_tools//go/analysis:go_tool_library", ], diff --git a/tools/go_generics/BUILD b/tools/go_generics/BUILD index 069df3856..32a949c93 100644 --- a/tools/go_generics/BUILD +++ b/tools/go_generics/BUILD @@ -9,7 +9,7 @@ go_binary( "imports.go", "remove.go", ], - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], deps = ["//tools/go_generics/globals"], ) diff --git a/tools/go_generics/go_merge/BUILD b/tools/go_generics/go_merge/BUILD index b7d35e272..2fd5a200d 100644 --- a/tools/go_generics/go_merge/BUILD +++ b/tools/go_generics/go_merge/BUILD @@ -5,5 +5,5 @@ package(licenses = ["notice"]) go_binary( name = "go_merge", srcs = ["main.go"], - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], ) diff --git a/tools/go_stateify/BUILD b/tools/go_stateify/BUILD index 6036faf7b..503cdf2e5 100644 --- a/tools/go_stateify/BUILD +++ b/tools/go_stateify/BUILD @@ -5,6 +5,6 @@ package(licenses = ["notice"]) go_binary( name = "stateify", srcs = ["main.go"], - visibility = ["//visibility:public"], + visibility = ["//:sandbox"], deps = ["//tools/tags"], ) -- cgit v1.2.3 From 03cee0656c9fd8cf9509c3a91baf72db4a8f6d28 Mon Sep 17 00:00:00 2001 From: 徐志强 <652732310@qq.com> Date: Tue, 18 Feb 2020 16:03:32 +0800 Subject: scope.add should only record the first position --- tools/go_generics/globals/scope.go | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'tools/go_generics') diff --git a/tools/go_generics/globals/scope.go b/tools/go_generics/globals/scope.go index 96c965ea2..eec93534b 100644 --- a/tools/go_generics/globals/scope.go +++ b/tools/go_generics/globals/scope.go @@ -72,6 +72,10 @@ func (s *scope) deepLookup(n string) *symbol { } func (s *scope) add(name string, kind SymKind, pos token.Pos) { + if s.syms[name] != nil { + return + } + s.syms[name] = &symbol{ kind: kind, pos: pos, -- cgit v1.2.3 From 6dd5a1f3fe55daa8510b1ee5e3a59219aad92af6 Mon Sep 17 00:00:00 2001 From: Fabricio Voznika Date: Wed, 8 Apr 2020 17:56:55 -0700 Subject: Clean up TODOs PiperOrigin-RevId: 305592245 --- pkg/sentry/fs/tmpfs/fs.go | 3 --- pkg/sentry/fsimpl/kernfs/filesystem.go | 2 +- pkg/sentry/kernel/ptrace.go | 1 - pkg/sentry/vfs/filesystem.go | 2 +- pkg/sentry/vfs/mount.go | 12 ++++++------ pkg/sentry/vfs/mount_test.go | 2 +- runsc/cmd/gofer.go | 5 ++--- test/syscalls/linux/epoll.cc | 4 ---- test/syscalls/linux/file_base.h | 1 + test/syscalls/linux/pwrite64.cc | 9 +-------- test/syscalls/linux/tuntap.cc | 7 ++++--- test/syscalls/linux/write.cc | 10 ++-------- tools/go_generics/defs.bzl | 1 - 13 files changed, 19 insertions(+), 40 deletions(-) (limited to 'tools/go_generics') diff --git a/pkg/sentry/fs/tmpfs/fs.go b/pkg/sentry/fs/tmpfs/fs.go index d5be56c3f..bc117ca6a 100644 --- a/pkg/sentry/fs/tmpfs/fs.go +++ b/pkg/sentry/fs/tmpfs/fs.go @@ -44,9 +44,6 @@ const ( // lookup. cacheRevalidate = "revalidate" - // TODO(edahlgren/mpratt): support a tmpfs size limit. - // size = "size" - // Permissions that exceed modeMask will be rejected. modeMask = 01777 diff --git a/pkg/sentry/fsimpl/kernfs/filesystem.go b/pkg/sentry/fsimpl/kernfs/filesystem.go index 16a3c18ae..4433071aa 100644 --- a/pkg/sentry/fsimpl/kernfs/filesystem.go +++ b/pkg/sentry/fsimpl/kernfs/filesystem.go @@ -682,7 +682,7 @@ func (fs *Filesystem) StatFSAt(ctx context.Context, rp *vfs.ResolvingPath) (linu if err != nil { return linux.Statfs{}, err } - // TODO: actually implement statfs + // TODO(gvisor.dev/issue/1193): actually implement statfs. return linux.Statfs{}, syserror.ENOSYS } diff --git a/pkg/sentry/kernel/ptrace.go b/pkg/sentry/kernel/ptrace.go index 35ad97d5d..e23e796ef 100644 --- a/pkg/sentry/kernel/ptrace.go +++ b/pkg/sentry/kernel/ptrace.go @@ -184,7 +184,6 @@ func (t *Task) CanTrace(target *Task, attach bool) bool { if targetCreds.PermittedCaps&^callerCreds.PermittedCaps != 0 { return false } - // TODO: Yama LSM return true } diff --git a/pkg/sentry/vfs/filesystem.go b/pkg/sentry/vfs/filesystem.go index cd34782ff..bef1bd312 100644 --- a/pkg/sentry/vfs/filesystem.go +++ b/pkg/sentry/vfs/filesystem.go @@ -497,7 +497,7 @@ type FilesystemImpl interface { // Preconditions: vd.Mount().Filesystem().Impl() == this FilesystemImpl. PrependPath(ctx context.Context, vfsroot, vd VirtualDentry, b *fspath.Builder) error - // TODO: inotify_add_watch() + // TODO(gvisor.dev/issue/1479): inotify_add_watch() } // PrependPathAtVFSRootError is returned by implementations of diff --git a/pkg/sentry/vfs/mount.go b/pkg/sentry/vfs/mount.go index 1b8ecc415..f06946103 100644 --- a/pkg/sentry/vfs/mount.go +++ b/pkg/sentry/vfs/mount.go @@ -233,9 +233,9 @@ func (vfs *VirtualFilesystem) MountAt(ctx context.Context, creds *auth.Credentia } vd.dentry.mu.Lock() } - // TODO: Linux requires that either both the mount point and the mount root - // are directories, or neither are, and returns ENOTDIR if this is not the - // case. + // TODO(gvisor.dev/issue/1035): Linux requires that either both the mount + // point and the mount root are directories, or neither are, and returns + // ENOTDIR if this is not the case. mntns := vd.mount.ns mnt := newMount(vfs, fs, root, mntns, opts) vfs.mounts.seq.BeginWrite() @@ -274,9 +274,9 @@ func (vfs *VirtualFilesystem) UmountAt(ctx context.Context, creds *auth.Credenti } } - // TODO(jamieliu): Linux special-cases umount of the caller's root, which - // we don't implement yet (we'll just fail it since the caller holds a - // reference on it). + // TODO(gvisor.dev/issue/1035): Linux special-cases umount of the caller's + // root, which we don't implement yet (we'll just fail it since the caller + // holds a reference on it). vfs.mounts.seq.BeginWrite() if opts.Flags&linux.MNT_DETACH == 0 { diff --git a/pkg/sentry/vfs/mount_test.go b/pkg/sentry/vfs/mount_test.go index 3b933468d..3335e4057 100644 --- a/pkg/sentry/vfs/mount_test.go +++ b/pkg/sentry/vfs/mount_test.go @@ -55,7 +55,7 @@ func TestMountTableInsertLookup(t *testing.T) { } } -// TODO: concurrent lookup/insertion/removal +// TODO(gvisor.dev/issue/1035): concurrent lookup/insertion/removal. // must be powers of 2 var benchNumMounts = []int{1 << 2, 1 << 5, 1 << 8} diff --git a/runsc/cmd/gofer.go b/runsc/cmd/gofer.go index 02e5af3d3..28f0d54b9 100644 --- a/runsc/cmd/gofer.go +++ b/runsc/cmd/gofer.go @@ -272,9 +272,8 @@ func setupRootFS(spec *specs.Spec, conf *boot.Config) error { root := spec.Root.Path if !conf.TestOnlyAllowRunAsCurrentUserWithoutChroot { - // FIXME: runsc can't be re-executed without - // /proc, so we create a tmpfs mount, mount ./proc and ./root - // there, then move this mount to the root and after + // runsc can't be re-executed without /proc, so we create a tmpfs mount, + // mount ./proc and ./root there, then move this mount to the root and after // setCapsAndCallSelf, runsc will chroot into /root. // // We need a directory to construct a new root and we know that diff --git a/test/syscalls/linux/epoll.cc b/test/syscalls/linux/epoll.cc index a4f8f3cec..f57d38dc7 100644 --- a/test/syscalls/linux/epoll.cc +++ b/test/syscalls/linux/epoll.cc @@ -56,10 +56,6 @@ TEST(EpollTest, AllWritable) { struct epoll_event result[kFDsPerEpoll]; ASSERT_THAT(RetryEINTR(epoll_wait)(epollfd.get(), result, kFDsPerEpoll, -1), SyscallSucceedsWithValue(kFDsPerEpoll)); - // TODO(edahlgren): Why do some tests check epoll_event::data, and others - // don't? Does Linux actually guarantee that, in any of these test cases, - // epoll_wait will necessarily write out the epoll_events in the order that - // they were registered? for (int i = 0; i < kFDsPerEpoll; i++) { ASSERT_EQ(result[i].events, EPOLLOUT); } diff --git a/test/syscalls/linux/file_base.h b/test/syscalls/linux/file_base.h index 25fdd7106..fb418e052 100644 --- a/test/syscalls/linux/file_base.h +++ b/test/syscalls/linux/file_base.h @@ -87,6 +87,7 @@ class FileTest : public ::testing::Test { ClosePipes(); } + protected: std::string test_file_name_; FileDescriptor test_file_fd_; diff --git a/test/syscalls/linux/pwrite64.cc b/test/syscalls/linux/pwrite64.cc index b48fe540d..c2f72e010 100644 --- a/test/syscalls/linux/pwrite64.cc +++ b/test/syscalls/linux/pwrite64.cc @@ -27,14 +27,7 @@ namespace testing { namespace { -// This test is currently very rudimentary. -// -// TODO(edahlgren): -// * bad buffer states (EFAULT). -// * bad fds (wrong permission, wrong type of file, EBADF). -// * check offset is not incremented. -// * check for EOF. -// * writing to pipes, symlinks, special files. +// TODO(gvisor.dev/issue/2370): This test is currently very rudimentary. class Pwrite64 : public ::testing::Test { void SetUp() override { name_ = NewTempAbsPath(); diff --git a/test/syscalls/linux/tuntap.cc b/test/syscalls/linux/tuntap.cc index 53ad2dda3..3a8ba37eb 100644 --- a/test/syscalls/linux/tuntap.cc +++ b/test/syscalls/linux/tuntap.cc @@ -242,7 +242,7 @@ TEST_F(TuntapTest, InvalidReadWrite) { TEST_F(TuntapTest, WriteToDownDevice) { SKIP_IF(!ASSERT_NO_ERRNO_AND_VALUE(HaveCapability(CAP_NET_ADMIN))); - // FIXME: gVisor always creates enabled/up'd interfaces. + // FIXME(b/110961832): gVisor always creates enabled/up'd interfaces. SKIP_IF(IsRunningOnGvisor()); FileDescriptor fd = ASSERT_NO_ERRNO_AND_VALUE(Open(kDevNetTun, O_RDWR)); @@ -280,10 +280,11 @@ PosixErrorOr OpenAndAttachTap( &addr, sizeof(addr))); if (!IsRunningOnGvisor()) { - // FIXME: gVisor doesn't support setting MAC address on interfaces yet. + // FIXME(b/110961832): gVisor doesn't support setting MAC address on + // interfaces yet. RETURN_IF_ERRNO(LinkSetMacAddr(link->index, kMacA, sizeof(kMacA))); - // FIXME: gVisor always creates enabled/up'd interfaces. + // FIXME(b/110961832): gVisor always creates enabled/up'd interfaces. RETURN_IF_ERRNO(LinkChangeFlags(link->index, IFF_UP, IFF_UP)); } diff --git a/test/syscalls/linux/write.cc b/test/syscalls/linux/write.cc index 9b219cfd6..39b5b2f56 100644 --- a/test/syscalls/linux/write.cc +++ b/test/syscalls/linux/write.cc @@ -31,14 +31,8 @@ namespace gvisor { namespace testing { namespace { -// This test is currently very rudimentary. -// -// TODO(edahlgren): -// * bad buffer states (EFAULT). -// * bad fds (wrong permission, wrong type of file, EBADF). -// * check offset is incremented. -// * check for EOF. -// * writing to pipes, symlinks, special files. + +// TODO(gvisor.dev/issue/2370): This test is currently very rudimentary. class WriteTest : public ::testing::Test { public: ssize_t WriteBytes(int fd, int bytes) { diff --git a/tools/go_generics/defs.bzl b/tools/go_generics/defs.bzl index c5be52ecd..8c9995fd4 100644 --- a/tools/go_generics/defs.bzl +++ b/tools/go_generics/defs.bzl @@ -105,7 +105,6 @@ def _go_template_instance_impl(ctx): executable = ctx.executable._tool, ) - # TODO: How can we get the dependencies out? return struct( files = depset([output]), ) -- cgit v1.2.3 From 059879e14301660c9fce1e5e59bdfaef89fc4aaf Mon Sep 17 00:00:00 2001 From: Reapor-Yurnero Date: Wed, 20 May 2020 22:48:41 -0700 Subject: Implement gap tracking in the segment set. This change was derived from a change by: Reapor-Yurnero And has been modified by: Adin Scannell (The original change author is preserved for the commit.) This change implements gap tracking in the segment set by adding additional information in each node, and using that information to speed up gap finding from a linear scan to a O(log(n)) walk of the tree. This gap tracking is optional, and will default to off except for segment instances that set gapTracking equal to 1 in their const lists. PiperOrigin-RevId: 312621607 --- pkg/segment/BUILD | 2 + pkg/segment/set.go | 400 +++++++++++++++++++++++++++++++++++++- pkg/segment/test/BUILD | 18 ++ pkg/segment/test/segment_test.go | 397 ++++++++++++++++++++++++++++++++----- pkg/segment/test/set_functions.go | 32 ++- pkg/sentry/mm/BUILD | 1 + pkg/sentry/mm/vma.go | 4 +- tools/go_generics/generics.go | 4 +- 8 files changed, 792 insertions(+), 66 deletions(-) (limited to 'tools/go_generics') diff --git a/pkg/segment/BUILD b/pkg/segment/BUILD index 1b487b887..f57ccc170 100644 --- a/pkg/segment/BUILD +++ b/pkg/segment/BUILD @@ -21,6 +21,8 @@ go_template( ], opt_consts = [ "minDegree", + # trackGaps must either be 0 or 1. + "trackGaps", ], types = [ "Key", diff --git a/pkg/segment/set.go b/pkg/segment/set.go index 03e4f258f..1a17ad9cb 100644 --- a/pkg/segment/set.go +++ b/pkg/segment/set.go @@ -36,6 +36,34 @@ type Range interface{} // Value is a required type parameter. type Value interface{} +// trackGaps is an optional parameter. +// +// If trackGaps is 1, the Set will track maximum gap size recursively, +// enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this +// case, Key must be an unsigned integer. +// +// trackGaps must be 0 or 1. +const trackGaps = 0 + +var _ = uint8(trackGaps << 7) // Will fail if not zero or one. + +// dynamicGap is a type that disappears if trackGaps is 0. +type dynamicGap [trackGaps]Key + +// Get returns the value of the gap. +// +// Precondition: trackGaps must be non-zero. +func (d *dynamicGap) Get() Key { + return d[:][0] +} + +// Set sets the value of the gap. +// +// Precondition: trackGaps must be non-zero. +func (d *dynamicGap) Set(v Key) { + d[:][0] = v +} + // Functions is a required type parameter that must be a struct implementing // the methods defined by Functions. type Functions interface { @@ -327,8 +355,12 @@ func (s *Set) Insert(gap GapIterator, r Range, val Value) Iterator { } if prev.Ok() && prev.End() == r.Start { if mval, ok := (Functions{}).Merge(prev.Range(), prev.Value(), r, val); ok { + shrinkMaxGap := trackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get() prev.SetEndUnchecked(r.End) prev.SetValue(mval) + if shrinkMaxGap { + gap.node.updateMaxGapLeaf() + } if next.Ok() && next.Start() == r.End { val = mval if mval, ok := (Functions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok { @@ -342,11 +374,16 @@ func (s *Set) Insert(gap GapIterator, r Range, val Value) Iterator { } if next.Ok() && next.Start() == r.End { if mval, ok := (Functions{}).Merge(r, val, next.Range(), next.Value()); ok { + shrinkMaxGap := trackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get() next.SetStartUnchecked(r.Start) next.SetValue(mval) + if shrinkMaxGap { + gap.node.updateMaxGapLeaf() + } return next } } + // InsertWithoutMergingUnchecked will maintain maxGap if necessary. return s.InsertWithoutMergingUnchecked(gap, r, val) } @@ -373,11 +410,15 @@ func (s *Set) InsertWithoutMerging(gap GapIterator, r Range, val Value) Iterator // Preconditions: r.Start >= gap.Start(); r.End <= gap.End(). func (s *Set) InsertWithoutMergingUnchecked(gap GapIterator, r Range, val Value) Iterator { gap = gap.node.rebalanceBeforeInsert(gap) + splitMaxGap := trackGaps != 0 && (gap.node.nrSegments == 0 || gap.Range().Length() == gap.node.maxGap.Get()) copy(gap.node.keys[gap.index+1:], gap.node.keys[gap.index:gap.node.nrSegments]) copy(gap.node.values[gap.index+1:], gap.node.values[gap.index:gap.node.nrSegments]) gap.node.keys[gap.index] = r gap.node.values[gap.index] = val gap.node.nrSegments++ + if splitMaxGap { + gap.node.updateMaxGapLeaf() + } return Iterator{gap.node, gap.index} } @@ -399,12 +440,23 @@ func (s *Set) Remove(seg Iterator) GapIterator { // overlap. seg.SetRangeUnchecked(victim.Range()) seg.SetValue(victim.Value()) + // Need to update the nextAdjacentNode's maxGap because the gap in between + // must have been modified by updating seg.Range() to victim.Range(). + // seg.NextSegment() must exist since the last segment can't be in a + // non-leaf node. + nextAdjacentNode := seg.NextSegment().node + if trackGaps != 0 { + nextAdjacentNode.updateMaxGapLeaf() + } return s.Remove(victim).NextGap() } copy(seg.node.keys[seg.index:], seg.node.keys[seg.index+1:seg.node.nrSegments]) copy(seg.node.values[seg.index:], seg.node.values[seg.index+1:seg.node.nrSegments]) Functions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1]) seg.node.nrSegments-- + if trackGaps != 0 { + seg.node.updateMaxGapLeaf() + } return seg.node.rebalanceAfterRemove(GapIterator{seg.node, seg.index}) } @@ -455,6 +507,7 @@ func (s *Set) MergeUnchecked(first, second Iterator) Iterator { // overlaps second. first.SetEndUnchecked(second.End()) first.SetValue(mval) + // Remove will handle the maxGap update if necessary. return s.Remove(second).PrevSegment() } } @@ -631,6 +684,12 @@ type node struct { // than "isLeaf" because false must be the correct value for an empty root. hasChildren bool + // The longest gap within this node. If the node is a leaf, it's simply the + // maximum gap among all the (nrSegments+1) gaps formed by its nrSegments keys + // including the 0th and nrSegments-th gap possibly shared with its upper-level + // nodes; if it's a non-leaf node, it's the max of all children's maxGap. + maxGap dynamicGap + // Nodes store keys and values in separate arrays to maximize locality in // the common case (scanning keys for lookup). keys [maxDegree - 1]Range @@ -676,12 +735,12 @@ func (n *node) nextSibling() *node { // required for insertion, and returns an updated iterator to the position // represented by gap. func (n *node) rebalanceBeforeInsert(gap GapIterator) GapIterator { - if n.parent != nil { - gap = n.parent.rebalanceBeforeInsert(gap) - } if n.nrSegments < maxDegree-1 { return gap } + if n.parent != nil { + gap = n.parent.rebalanceBeforeInsert(gap) + } if n.parent == nil { // n is root. Move all segments before and after n's median segment // into new child nodes adjacent to the median segment, which is now @@ -719,6 +778,13 @@ func (n *node) rebalanceBeforeInsert(gap GapIterator) GapIterator { n.hasChildren = true n.children[0] = left n.children[1] = right + // In this case, n's maxGap won't violated as it's still the root, + // but the left and right children should be updated locally as they + // are newly split from n. + if trackGaps != 0 { + left.updateMaxGapLocal() + right.updateMaxGapLocal() + } if gap.node != n { return gap } @@ -758,6 +824,12 @@ func (n *node) rebalanceBeforeInsert(gap GapIterator) GapIterator { } } n.nrSegments = minDegree - 1 + // MaxGap of n's parent is not violated because the segments within is not changed. + // n and its sibling's maxGap need to be updated locally as they are two new nodes split from old n. + if trackGaps != 0 { + n.updateMaxGapLocal() + sibling.updateMaxGapLocal() + } // gap.node can't be n.parent because gaps are always in leaf nodes. if gap.node != n { return gap @@ -821,6 +893,12 @@ func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { } n.nrSegments++ sibling.nrSegments-- + // n's parent's maxGap does not need to be updated as its content is unmodified. + // n and its sibling must be updated with (new) maxGap because of the shift of keys. + if trackGaps != 0 { + n.updateMaxGapLocal() + sibling.updateMaxGapLocal() + } if gap.node == sibling && gap.index == sibling.nrSegments { return GapIterator{n, 0} } @@ -849,6 +927,12 @@ func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { } n.nrSegments++ sibling.nrSegments-- + // n's parent's maxGap does not need to be updated as its content is unmodified. + // n and its sibling must be updated with (new) maxGap because of the shift of keys. + if trackGaps != 0 { + n.updateMaxGapLocal() + sibling.updateMaxGapLocal() + } if gap.node == sibling { if gap.index == 0 { return GapIterator{n, n.nrSegments} @@ -886,6 +970,7 @@ func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { p.children[0] = nil p.children[1] = nil } + // No need to update maxGap of p as its content is not changed. if gap.node == left { return GapIterator{p, gap.index} } @@ -932,11 +1017,152 @@ func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { } p.children[p.nrSegments] = nil p.nrSegments-- + // Update maxGap of left locally, no need to change p and right because + // p's contents is not changed and right is already invalid. + if trackGaps != 0 { + left.updateMaxGapLocal() + } // This process robs p of one segment, so recurse into rebalancing p. n = p } } +// updateMaxGapLeaf updates maxGap bottom-up from the calling leaf until no +// necessary update. +// +// Preconditions: n must be a leaf node, trackGaps must be 1. +func (n *node) updateMaxGapLeaf() { + if n.hasChildren { + panic(fmt.Sprintf("updateMaxGapLeaf should always be called on leaf node: %v", n)) + } + max := n.calculateMaxGapLeaf() + if max == n.maxGap.Get() { + // If new max equals the old maxGap, no update is needed. + return + } + oldMax := n.maxGap.Get() + n.maxGap.Set(max) + if max > oldMax { + // Grow ancestor maxGaps. + for p := n.parent; p != nil; p = p.parent { + if p.maxGap.Get() >= max { + // p and its ancestors already contain an equal or larger gap. + break + } + // Only if new maxGap is larger than parent's + // old maxGap, propagate this update to parent. + p.maxGap.Set(max) + } + return + } + // Shrink ancestor maxGaps. + for p := n.parent; p != nil; p = p.parent { + if p.maxGap.Get() > oldMax { + // p and its ancestors still contain a larger gap. + break + } + // If new max is smaller than the old maxGap, and this gap used + // to be the maxGap of its parent, iterate parent's children + // and calculate parent's new maxGap.(It's probable that parent + // has two children with the old maxGap, but we need to check it anyway.) + parentNewMax := p.calculateMaxGapInternal() + if p.maxGap.Get() == parentNewMax { + // p and its ancestors still contain a gap of at least equal size. + break + } + // If p's new maxGap differs from the old one, propagate this update. + p.maxGap.Set(parentNewMax) + } +} + +// updateMaxGapLocal updates maxGap of the calling node solely with no +// propagation to ancestor nodes. +// +// Precondition: trackGaps must be 1. +func (n *node) updateMaxGapLocal() { + if !n.hasChildren { + // Leaf node iterates its gaps. + n.maxGap.Set(n.calculateMaxGapLeaf()) + } else { + // Non-leaf node iterates its children. + n.maxGap.Set(n.calculateMaxGapInternal()) + } +} + +// calculateMaxGapLeaf iterates the gaps within a leaf node and calculate the +// max. +// +// Preconditions: n must be a leaf node. +func (n *node) calculateMaxGapLeaf() Key { + max := GapIterator{n, 0}.Range().Length() + for i := 1; i <= n.nrSegments; i++ { + if current := (GapIterator{n, i}).Range().Length(); current > max { + max = current + } + } + return max +} + +// calculateMaxGapInternal iterates children's maxGap within an internal node n +// and calculate the max. +// +// Preconditions: n must be a non-leaf node. +func (n *node) calculateMaxGapInternal() Key { + max := n.children[0].maxGap.Get() + for i := 1; i <= n.nrSegments; i++ { + if current := n.children[i].maxGap.Get(); current > max { + max = current + } + } + return max +} + +// searchFirstLargeEnoughGap returns the first gap having at least minSize length +// in the subtree rooted by n. If not found, return a terminal gap iterator. +func (n *node) searchFirstLargeEnoughGap(minSize Key) GapIterator { + if n.maxGap.Get() < minSize { + return GapIterator{} + } + if n.hasChildren { + for i := 0; i <= n.nrSegments; i++ { + if largeEnoughGap := n.children[i].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() { + return largeEnoughGap + } + } + } else { + for i := 0; i <= n.nrSegments; i++ { + currentGap := GapIterator{n, i} + if currentGap.Range().Length() >= minSize { + return currentGap + } + } + } + panic(fmt.Sprintf("invalid maxGap in %v", n)) +} + +// searchLastLargeEnoughGap returns the last gap having at least minSize length +// in the subtree rooted by n. If not found, return a terminal gap iterator. +func (n *node) searchLastLargeEnoughGap(minSize Key) GapIterator { + if n.maxGap.Get() < minSize { + return GapIterator{} + } + if n.hasChildren { + for i := n.nrSegments; i >= 0; i-- { + if largeEnoughGap := n.children[i].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() { + return largeEnoughGap + } + } + } else { + for i := n.nrSegments; i >= 0; i-- { + currentGap := GapIterator{n, i} + if currentGap.Range().Length() >= minSize { + return currentGap + } + } + } + panic(fmt.Sprintf("invalid maxGap in %v", n)) +} + // A Iterator is conceptually one of: // // - A pointer to a segment in a set; or @@ -1243,6 +1469,122 @@ func (gap GapIterator) NextGap() GapIterator { return seg.NextGap() } +// NextLargeEnoughGap returns the iterated gap's first next gap with larger +// length than minSize. If not found, return a terminal gap iterator (does NOT +// include this gap itself). +// +// Precondition: trackGaps must be 1. +func (gap GapIterator) NextLargeEnoughGap(minSize Key) GapIterator { + if trackGaps != 1 { + panic("set is not tracking gaps") + } + if gap.node != nil && gap.node.hasChildren && gap.index == gap.node.nrSegments { + // If gap is the trailing gap of an non-leaf node, + // translate it to the equivalent gap on leaf level. + gap.node = gap.NextSegment().node + gap.index = 0 + return gap.nextLargeEnoughGapHelper(minSize) + } + return gap.nextLargeEnoughGapHelper(minSize) +} + +// nextLargeEnoughGapHelper is the helper function used by NextLargeEnoughGap +// to do the real recursions. +// +// Preconditions: gap is NOT the trailing gap of a non-leaf node. +func (gap GapIterator) nextLargeEnoughGapHelper(minSize Key) GapIterator { + // Crawl up the tree if no large enough gap in current node or the + // current gap is the trailing one on leaf level. + for gap.node != nil && + (gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == gap.node.nrSegments)) { + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + } + // If no large enough gap throughout the whole set, return a terminal + // gap iterator. + if gap.node == nil { + return GapIterator{} + } + // Iterate subsequent gaps. + gap.index++ + for gap.index <= gap.node.nrSegments { + if gap.node.hasChildren { + if largeEnoughGap := gap.node.children[gap.index].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() { + return largeEnoughGap + } + } else { + if gap.Range().Length() >= minSize { + return gap + } + } + gap.index++ + } + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + if gap.node != nil && gap.index == gap.node.nrSegments { + // If gap is the trailing gap of a non-leaf node, crawl up to + // parent again and do recursion. + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + } + return gap.nextLargeEnoughGapHelper(minSize) +} + +// PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or +// equal length than minSize. If not found, return a terminal gap iterator +// (does NOT include this gap itself). +// +// Precondition: trackGaps must be 1. +func (gap GapIterator) PrevLargeEnoughGap(minSize Key) GapIterator { + if trackGaps != 1 { + panic("set is not tracking gaps") + } + if gap.node != nil && gap.node.hasChildren && gap.index == 0 { + // If gap is the first gap of an non-leaf node, + // translate it to the equivalent gap on leaf level. + gap.node = gap.PrevSegment().node + gap.index = gap.node.nrSegments + return gap.prevLargeEnoughGapHelper(minSize) + } + return gap.prevLargeEnoughGapHelper(minSize) +} + +// prevLargeEnoughGapHelper is the helper function used by PrevLargeEnoughGap +// to do the real recursions. +// +// Preconditions: gap is NOT the first gap of a non-leaf node. +func (gap GapIterator) prevLargeEnoughGapHelper(minSize Key) GapIterator { + // Crawl up the tree if no large enough gap in current node or the + // current gap is the first one on leaf level. + for gap.node != nil && + (gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == 0)) { + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + } + // If no large enough gap throughout the whole set, return a terminal + // gap iterator. + if gap.node == nil { + return GapIterator{} + } + // Iterate previous gaps. + gap.index-- + for gap.index >= 0 { + if gap.node.hasChildren { + if largeEnoughGap := gap.node.children[gap.index].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() { + return largeEnoughGap + } + } else { + if gap.Range().Length() >= minSize { + return gap + } + } + gap.index-- + } + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + if gap.node != nil && gap.index == 0 { + // If gap is the first gap of a non-leaf node, crawl up to + // parent again and do recursion. + gap.node, gap.index = gap.node.parent, gap.node.parentIndex + } + return gap.prevLargeEnoughGapHelper(minSize) +} + // segmentBeforePosition returns the predecessor segment of the position given // by n.children[i], which may or may not contain a child. If no such segment // exists, segmentBeforePosition returns a terminal iterator. @@ -1271,7 +1613,7 @@ func segmentAfterPosition(n *node, i int) Iterator { func zeroValueSlice(slice []Value) { // TODO(jamieliu): check if Go is actually smart enough to optimize a - // ClearValue that assigns nil to a memset here + // ClearValue that assigns nil to a memset here. for i := range slice { Functions{}.ClearValue(&slice[i]) } @@ -1310,7 +1652,15 @@ func (n *node) writeDebugString(buf *bytes.Buffer, prefix string) { child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, i)) } buf.WriteString(prefix) - buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i])) + if n.hasChildren { + if trackGaps != 0 { + buf.WriteString(fmt.Sprintf("- % 3d: %v => %v, maxGap: %d\n", i, n.keys[i], n.values[i], n.maxGap.Get())) + } else { + buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i])) + } + } else { + buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i])) + } } if child := n.children[n.nrSegments]; child != nil { child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, n.nrSegments)) @@ -1362,3 +1712,43 @@ func (s *Set) ImportSortedSlices(sds *SegmentDataSlices) error { } return nil } + +// segmentTestCheck returns an error if s is incorrectly sorted, does not +// contain exactly expectedSegments segments, or contains a segment which +// fails the passed check. +// +// This should be used only for testing, and has been added to this package for +// templating convenience. +func (s *Set) segmentTestCheck(expectedSegments int, segFunc func(int, Range, Value) error) error { + havePrev := false + prev := Key(0) + nrSegments := 0 + for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { + next := seg.Start() + if havePrev && prev >= next { + return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments) + } + if segFunc != nil { + if err := segFunc(nrSegments, seg.Range(), seg.Value()); err != nil { + return err + } + } + prev = next + havePrev = true + nrSegments++ + } + if nrSegments != expectedSegments { + return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments) + } + return nil +} + +// countSegments counts the number of segments in the set. +// +// Similar to Check, this should only be used for testing. +func (s *Set) countSegments() (segments int) { + for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { + segments++ + } + return segments +} diff --git a/pkg/segment/test/BUILD b/pkg/segment/test/BUILD index f2d8462d8..131bf09b9 100644 --- a/pkg/segment/test/BUILD +++ b/pkg/segment/test/BUILD @@ -29,10 +29,28 @@ go_template_instance( }, ) +go_template_instance( + name = "gap_set", + out = "gap_set.go", + consts = { + "trackGaps": "1", + }, + package = "segment", + prefix = "gap", + template = "//pkg/segment:generic_set", + types = { + "Key": "int", + "Range": "Range", + "Value": "int", + "Functions": "gapSetFunctions", + }, +) + go_library( name = "segment", testonly = 1, srcs = [ + "gap_set.go", "int_range.go", "int_set.go", "set_functions.go", diff --git a/pkg/segment/test/segment_test.go b/pkg/segment/test/segment_test.go index 97b16c158..85fa19096 100644 --- a/pkg/segment/test/segment_test.go +++ b/pkg/segment/test/segment_test.go @@ -17,6 +17,7 @@ package segment import ( "fmt" "math/rand" + "reflect" "testing" ) @@ -32,61 +33,65 @@ const ( // valueOffset is the difference between the value and start of test // segments. valueOffset = 100000 + + // intervalLength is the interval used by random gap tests. + intervalLength = 10 ) func shuffle(xs []int) { - for i := range xs { - j := rand.Intn(i + 1) - xs[i], xs[j] = xs[j], xs[i] - } + rand.Shuffle(len(xs), func(i, j int) { xs[i], xs[j] = xs[j], xs[i] }) } -func randPermutation(size int) []int { +func randIntervalPermutation(size int) []int { p := make([]int, size) for i := range p { - p[i] = i + p[i] = intervalLength * i } shuffle(p) return p } -// checkSet returns an error if s is incorrectly sorted, does not contain -// exactly expectedSegments segments, or contains a segment for which val != -// key + valueOffset. -func checkSet(s *Set, expectedSegments int) error { - havePrev := false - prev := 0 - nrSegments := 0 - for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { - next := seg.Start() - if havePrev && prev >= next { - return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments) - } - if got, want := seg.Value(), seg.Start()+valueOffset; got != want { - return fmt.Errorf("segment %d has key %d, value %d (expected %d)", nrSegments, seg.Start(), got, want) - } - prev = next - havePrev = true - nrSegments++ - } - if nrSegments != expectedSegments { - return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments) +// validate can be passed to Check. +func validate(nr int, r Range, v int) error { + if got, want := v, r.Start+valueOffset; got != want { + return fmt.Errorf("segment %d has key %d, value %d (expected %d)", nr, r.Start, got, want) } return nil } -// countSegmentsIn returns the number of segments in s. -func countSegmentsIn(s *Set) int { - var count int - for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { - count++ +// checkSetMaxGap returns an error if maxGap inside all nodes of s is not well +// maintained. +func checkSetMaxGap(s *gapSet) error { + n := s.root + return checkNodeMaxGap(&n) +} + +// checkNodeMaxGap returns an error if maxGap inside the subtree rooted by n is +// not well maintained. +func checkNodeMaxGap(n *gapnode) error { + var max int + if !n.hasChildren { + max = n.calculateMaxGapLeaf() + } else { + for i := 0; i <= n.nrSegments; i++ { + child := n.children[i] + if err := checkNodeMaxGap(child); err != nil { + return err + } + if temp := child.maxGap.Get(); i == 0 || temp > max { + max = temp + } + } + } + if max != n.maxGap.Get() { + return fmt.Errorf("maxGap wrong in node\n%vexpected: %d got: %d", n, max, n.maxGap) } - return count + return nil } func TestAddRandom(t *testing.T) { var s Set - order := randPermutation(testSize) + order := rand.Perm(testSize) var nrInsertions int for i, j := range order { if !s.AddWithoutMerging(Range{j, j + 1}, j+valueOffset) { @@ -94,12 +99,12 @@ func TestAddRandom(t *testing.T) { break } nrInsertions++ - if err := checkSet(&s, nrInsertions); err != nil { + if err := s.segmentTestCheck(nrInsertions, validate); err != nil { t.Errorf("Iteration %d: %v", i, err) break } } - if got, want := countSegmentsIn(&s), nrInsertions; got != want { + if got, want := s.countSegments(), nrInsertions; got != want { t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) } if t.Failed() { @@ -115,7 +120,156 @@ func TestRemoveRandom(t *testing.T) { t.Fatalf("Failed to insert segment %d", i) } } - order := randPermutation(testSize) + order := rand.Perm(testSize) + var nrRemovals int + for i, j := range order { + seg := s.FindSegment(j) + if !seg.Ok() { + t.Errorf("Iteration %d: failed to find segment with key %d", i, j) + break + } + s.Remove(seg) + nrRemovals++ + if err := s.segmentTestCheck(testSize-nrRemovals, validate); err != nil { + t.Errorf("Iteration %d: %v", i, err) + break + } + } + if got, want := s.countSegments(), testSize-nrRemovals; got != want { + t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) + } + if t.Failed() { + t.Logf("Removal order: %v", order[:nrRemovals]) + t.Logf("Set contents:\n%v", &s) + t.FailNow() + } +} + +func TestMaxGapAddRandom(t *testing.T) { + var s gapSet + order := rand.Perm(testSize) + var nrInsertions int + for i, j := range order { + if !s.AddWithoutMerging(Range{j, j + 1}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + nrInsertions++ + if err := s.segmentTestCheck(nrInsertions, validate); err != nil { + t.Errorf("Iteration %d: %v", i, err) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + if got, want := s.countSegments(), nrInsertions; got != want { + t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) + } + if t.Failed() { + t.Logf("Insertion order: %v", order[:nrInsertions]) + t.Logf("Set contents:\n%v", &s) + } +} + +func TestMaxGapAddRandomWithRandomInterval(t *testing.T) { + var s gapSet + order := randIntervalPermutation(testSize) + var nrInsertions int + for i, j := range order { + if !s.AddWithoutMerging(Range{j, j + rand.Intn(intervalLength-1) + 1}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + nrInsertions++ + if err := s.segmentTestCheck(nrInsertions, validate); err != nil { + t.Errorf("Iteration %d: %v", i, err) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + if got, want := s.countSegments(), nrInsertions; got != want { + t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) + } + if t.Failed() { + t.Logf("Insertion order: %v", order[:nrInsertions]) + t.Logf("Set contents:\n%v", &s) + } +} + +func TestMaxGapAddRandomWithMerge(t *testing.T) { + var s gapSet + order := randIntervalPermutation(testSize) + nrInsertions := 1 + for i, j := range order { + if !s.Add(Range{j, j + intervalLength}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + if got, want := s.countSegments(), nrInsertions; got != want { + t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) + } + if t.Failed() { + t.Logf("Insertion order: %v", order) + t.Logf("Set contents:\n%v", &s) + } +} + +func TestMaxGapRemoveRandom(t *testing.T) { + var s gapSet + for i := 0; i < testSize; i++ { + if !s.AddWithoutMerging(Range{i, i + 1}, i+valueOffset) { + t.Fatalf("Failed to insert segment %d", i) + } + } + order := rand.Perm(testSize) + var nrRemovals int + for i, j := range order { + seg := s.FindSegment(j) + if !seg.Ok() { + t.Errorf("Iteration %d: failed to find segment with key %d", i, j) + break + } + temprange := seg.Range() + s.Remove(seg) + nrRemovals++ + if err := s.segmentTestCheck(testSize-nrRemovals, validate); err != nil { + t.Errorf("Iteration %d: %v", i, err) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When removing %v: %v", temprange, err) + break + } + } + if got, want := s.countSegments(), testSize-nrRemovals; got != want { + t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) + } + if t.Failed() { + t.Logf("Removal order: %v", order[:nrRemovals]) + t.Logf("Set contents:\n%v", &s) + t.FailNow() + } +} + +func TestMaxGapRemoveHalfRandom(t *testing.T) { + var s gapSet + for i := 0; i < testSize; i++ { + if !s.AddWithoutMerging(Range{intervalLength * i, intervalLength*i + rand.Intn(intervalLength-1) + 1}, intervalLength*i+valueOffset) { + t.Fatalf("Failed to insert segment %d", i) + } + } + order := randIntervalPermutation(testSize) + order = order[:testSize/2] var nrRemovals int for i, j := range order { seg := s.FindSegment(j) @@ -123,14 +277,19 @@ func TestRemoveRandom(t *testing.T) { t.Errorf("Iteration %d: failed to find segment with key %d", i, j) break } + temprange := seg.Range() s.Remove(seg) nrRemovals++ - if err := checkSet(&s, testSize-nrRemovals); err != nil { + if err := s.segmentTestCheck(testSize-nrRemovals, validate); err != nil { t.Errorf("Iteration %d: %v", i, err) break } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When removing %v: %v", temprange, err) + break + } } - if got, want := countSegmentsIn(&s), testSize-nrRemovals; got != want { + if got, want := s.countSegments(), testSize-nrRemovals; got != want { t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) } if t.Failed() { @@ -140,6 +299,148 @@ func TestRemoveRandom(t *testing.T) { } } +func TestMaxGapAddRandomRemoveRandomHalfWithMerge(t *testing.T) { + var s gapSet + order := randIntervalPermutation(testSize * 2) + order = order[:testSize] + for i, j := range order { + if !s.Add(Range{j, j + intervalLength}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + shuffle(order) + var nrRemovals int + for _, j := range order { + seg := s.FindSegment(j) + if !seg.Ok() { + continue + } + temprange := seg.Range() + s.Remove(seg) + nrRemovals++ + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When removing %v: %v", temprange, err) + break + } + } + if t.Failed() { + t.Logf("Removal order: %v", order[:nrRemovals]) + t.Logf("Set contents:\n%v", &s) + t.FailNow() + } +} + +func TestNextLargeEnoughGap(t *testing.T) { + var s gapSet + order := randIntervalPermutation(testSize * 2) + order = order[:testSize] + for i, j := range order { + if !s.Add(Range{j, j + rand.Intn(intervalLength-1) + 1}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + shuffle(order) + order = order[:testSize/2] + for _, j := range order { + seg := s.FindSegment(j) + if !seg.Ok() { + continue + } + temprange := seg.Range() + s.Remove(seg) + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When removing %v: %v", temprange, err) + break + } + } + minSize := 7 + var gapArr1 []int + for gap := s.LowerBoundGap(0).NextLargeEnoughGap(minSize); gap.Ok(); gap = gap.NextLargeEnoughGap(minSize) { + if gap.Range().Length() < minSize { + t.Errorf("NextLargeEnoughGap wrong, gap %v has length %d, wanted %d", gap.Range(), gap.Range().Length(), minSize) + } else { + gapArr1 = append(gapArr1, gap.Range().Start) + } + } + var gapArr2 []int + for gap := s.LowerBoundGap(0).NextGap(); gap.Ok(); gap = gap.NextGap() { + if gap.Range().Length() >= minSize { + gapArr2 = append(gapArr2, gap.Range().Start) + } + } + + if !reflect.DeepEqual(gapArr2, gapArr1) { + t.Errorf("Search result not correct, got: %v, wanted: %v", gapArr1, gapArr2) + } + if t.Failed() { + t.Logf("Set contents:\n%v", &s) + t.FailNow() + } +} + +func TestPrevLargeEnoughGap(t *testing.T) { + var s gapSet + order := randIntervalPermutation(testSize * 2) + order = order[:testSize] + for i, j := range order { + if !s.Add(Range{j, j + rand.Intn(intervalLength-1) + 1}, j+valueOffset) { + t.Errorf("Iteration %d: failed to insert segment with key %d", i, j) + break + } + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When inserting %d: %v", j, err) + break + } + } + end := s.LastSegment().End() + shuffle(order) + order = order[:testSize/2] + for _, j := range order { + seg := s.FindSegment(j) + if !seg.Ok() { + continue + } + temprange := seg.Range() + s.Remove(seg) + if err := checkSetMaxGap(&s); err != nil { + t.Errorf("When removing %v: %v", temprange, err) + break + } + } + minSize := 7 + var gapArr1 []int + for gap := s.UpperBoundGap(end + intervalLength).PrevLargeEnoughGap(minSize); gap.Ok(); gap = gap.PrevLargeEnoughGap(minSize) { + if gap.Range().Length() < minSize { + t.Errorf("PrevLargeEnoughGap wrong, gap length %d, wanted %d", gap.Range().Length(), minSize) + } else { + gapArr1 = append(gapArr1, gap.Range().Start) + } + } + var gapArr2 []int + for gap := s.UpperBoundGap(end + intervalLength).PrevGap(); gap.Ok(); gap = gap.PrevGap() { + if gap.Range().Length() >= minSize { + gapArr2 = append(gapArr2, gap.Range().Start) + } + } + if !reflect.DeepEqual(gapArr2, gapArr1) { + t.Errorf("Search result not correct, got: %v, wanted: %v", gapArr1, gapArr2) + } + if t.Failed() { + t.Logf("Set contents:\n%v", &s) + t.FailNow() + } +} + func TestAddSequentialAdjacent(t *testing.T) { var s Set var nrInsertions int @@ -148,12 +449,12 @@ func TestAddSequentialAdjacent(t *testing.T) { t.Fatalf("Failed to insert segment %d", i) } nrInsertions++ - if err := checkSet(&s, nrInsertions); err != nil { + if err := s.segmentTestCheck(nrInsertions, validate); err != nil { t.Errorf("Iteration %d: %v", i, err) break } } - if got, want := countSegmentsIn(&s), nrInsertions; got != want { + if got, want := s.countSegments(), nrInsertions; got != want { t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) } if t.Failed() { @@ -202,12 +503,12 @@ func TestAddSequentialNonAdjacent(t *testing.T) { t.Fatalf("Failed to insert segment %d", i) } nrInsertions++ - if err := checkSet(&s, nrInsertions); err != nil { + if err := s.segmentTestCheck(nrInsertions, validate); err != nil { t.Errorf("Iteration %d: %v", i, err) break } } - if got, want := countSegmentsIn(&s), nrInsertions; got != want { + if got, want := s.countSegments(), nrInsertions; got != want { t.Errorf("Wrong final number of segments: got %d, wanted %d", got, want) } if t.Failed() { @@ -293,7 +594,7 @@ Tests: var i int for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { if i > len(test.final) { - t.Errorf("%s: Incorrect number of segments: got %d, wanted %d; set contents:\n%v", test.name, countSegmentsIn(&s), len(test.final), &s) + t.Errorf("%s: Incorrect number of segments: got %d, wanted %d; set contents:\n%v", test.name, s.countSegments(), len(test.final), &s) continue Tests } if got, want := seg.Range(), test.final[i]; got != want { @@ -351,7 +652,7 @@ Tests: var i int for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { if i > len(test.final) { - t.Errorf("%s: Incorrect number of segments: got %d, wanted %d; set contents:\n%v", test.name, countSegmentsIn(&s), len(test.final), &s) + t.Errorf("%s: Incorrect number of segments: got %d, wanted %d; set contents:\n%v", test.name, s.countSegments(), len(test.final), &s) continue Tests } if got, want := seg.Range(), test.final[i]; got != want { @@ -378,7 +679,7 @@ func benchmarkAddSequential(b *testing.B, size int) { } func benchmarkAddRandom(b *testing.B, size int) { - order := randPermutation(size) + order := rand.Perm(size) b.ResetTimer() for n := 0; n < b.N; n++ { @@ -416,7 +717,7 @@ func benchmarkFindRandom(b *testing.B, size int) { b.Fatalf("Failed to insert segment %d", i) } } - order := randPermutation(size) + order := rand.Perm(size) b.ResetTimer() for n := 0; n < b.N; n++ { @@ -470,7 +771,7 @@ func benchmarkAddFindRemoveSequential(b *testing.B, size int) { } func benchmarkAddFindRemoveRandom(b *testing.B, size int) { - order := randPermutation(size) + order := rand.Perm(size) b.ResetTimer() for n := 0; n < b.N; n++ { diff --git a/pkg/segment/test/set_functions.go b/pkg/segment/test/set_functions.go index bcddb39bb..7cd895cc7 100644 --- a/pkg/segment/test/set_functions.go +++ b/pkg/segment/test/set_functions.go @@ -14,21 +14,16 @@ package segment -// Basic numeric constants that we define because the math package doesn't. -// TODO(nlacasse): These should be Math.MaxInt64/MinInt64? -const ( - maxInt = int(^uint(0) >> 1) - minInt = -maxInt - 1 -) - type setFunctions struct{} -func (setFunctions) MinKey() int { - return minInt +// MinKey returns the minimum key for the set. +func (s setFunctions) MinKey() int { + return -s.MaxKey() - 1 } +// MaxKey returns the maximum key for the set. func (setFunctions) MaxKey() int { - return maxInt + return int(^uint(0) >> 1) } func (setFunctions) ClearValue(*int) {} @@ -40,3 +35,20 @@ func (setFunctions) Merge(_ Range, val1 int, _ Range, _ int) (int, bool) { func (setFunctions) Split(_ Range, val int, _ int) (int, int) { return val, val } + +type gapSetFunctions struct { + setFunctions +} + +// MinKey is adjusted to make sure no add overflow would happen in test cases. +// e.g. A gap with range {MinInt32, 2} would cause overflow in Range().Length(). +// +// Normally Keys should be unsigned to avoid these issues. +func (s gapSetFunctions) MinKey() int { + return s.setFunctions.MinKey() / 2 +} + +// MaxKey returns the maximum key for the set. +func (s gapSetFunctions) MaxKey() int { + return s.setFunctions.MaxKey() / 2 +} diff --git a/pkg/sentry/mm/BUILD b/pkg/sentry/mm/BUILD index 73591dab7..a036ce53c 100644 --- a/pkg/sentry/mm/BUILD +++ b/pkg/sentry/mm/BUILD @@ -25,6 +25,7 @@ go_template_instance( out = "vma_set.go", consts = { "minDegree": "8", + "trackGaps": "1", }, imports = { "usermem": "gvisor.dev/gvisor/pkg/usermem", diff --git a/pkg/sentry/mm/vma.go b/pkg/sentry/mm/vma.go index 9a14e69e6..16d8207e9 100644 --- a/pkg/sentry/mm/vma.go +++ b/pkg/sentry/mm/vma.go @@ -195,7 +195,7 @@ func (mm *MemoryManager) applicationAddrRange() usermem.AddrRange { // Preconditions: mm.mappingMu must be locked. func (mm *MemoryManager) findLowestAvailableLocked(length, alignment uint64, bounds usermem.AddrRange) (usermem.Addr, error) { - for gap := mm.vmas.LowerBoundGap(bounds.Start); gap.Ok() && gap.Start() < bounds.End; gap = gap.NextGap() { + for gap := mm.vmas.LowerBoundGap(bounds.Start); gap.Ok() && gap.Start() < bounds.End; gap = gap.NextLargeEnoughGap(usermem.Addr(length)) { if gr := gap.availableRange().Intersect(bounds); uint64(gr.Length()) >= length { // Can we shift up to match the alignment? if offset := uint64(gr.Start) % alignment; offset != 0 { @@ -214,7 +214,7 @@ func (mm *MemoryManager) findLowestAvailableLocked(length, alignment uint64, bou // Preconditions: mm.mappingMu must be locked. func (mm *MemoryManager) findHighestAvailableLocked(length, alignment uint64, bounds usermem.AddrRange) (usermem.Addr, error) { - for gap := mm.vmas.UpperBoundGap(bounds.End); gap.Ok() && gap.End() > bounds.Start; gap = gap.PrevGap() { + for gap := mm.vmas.UpperBoundGap(bounds.End); gap.Ok() && gap.End() > bounds.Start; gap = gap.PrevLargeEnoughGap(usermem.Addr(length)) { if gr := gap.availableRange().Intersect(bounds); uint64(gr.Length()) >= length { // Can we shift down to match the alignment? start := gr.End - usermem.Addr(length) diff --git a/tools/go_generics/generics.go b/tools/go_generics/generics.go index e9cc2c753..0860ca9db 100644 --- a/tools/go_generics/generics.go +++ b/tools/go_generics/generics.go @@ -223,7 +223,9 @@ func main() { } else { switch kind { case globals.KindType, globals.KindVar, globals.KindConst, globals.KindFunction: - ident.Name = *prefix + ident.Name + *suffix + if ident.Name != "_" { + ident.Name = *prefix + ident.Name + *suffix + } case globals.KindTag: // Modify the state tag appropriately. if m := stateTagRegexp.FindStringSubmatch(ident.Name); m != nil { -- cgit v1.2.3 From ab0262bd94c25bc91d5e0d831b75729c253dfde6 Mon Sep 17 00:00:00 2001 From: Adin Scannell Date: Thu, 23 Jul 2020 18:00:12 -0700 Subject: Convert go_generics tests to starlark. For some reason these tests were broken when run via the bazel docker container. The mechanism used was a bit crazy (self-extracting bundle), so convert them to use straight-forward starlark rules. This has the added advantaged that they are now independent tests. --- images/default/Dockerfile | 2 +- tools/go_generics/BUILD | 24 -- tools/go_generics/defs.bzl | 5 +- .../go_generics/generics_tests/all_stmts/input.go | 290 --------------------- .../go_generics/generics_tests/all_stmts/opts.txt | 1 - .../generics_tests/all_stmts/output/output.go | 288 -------------------- .../go_generics/generics_tests/all_types/input.go | 43 --- .../generics_tests/all_types/lib/lib.go | 17 -- .../go_generics/generics_tests/all_types/opts.txt | 1 - .../generics_tests/all_types/output/output.go | 41 --- tools/go_generics/generics_tests/anon/input.go | 46 ---- tools/go_generics/generics_tests/anon/opts.txt | 1 - .../generics_tests/anon/output/output.go | 42 --- tools/go_generics/generics_tests/consts/input.go | 26 -- tools/go_generics/generics_tests/consts/opts.txt | 1 - .../generics_tests/consts/output/output.go | 26 -- tools/go_generics/generics_tests/imports/input.go | 24 -- tools/go_generics/generics_tests/imports/opts.txt | 1 - .../generics_tests/imports/output/output.go | 27 -- .../generics_tests/remove_typedef/input.go | 37 --- .../generics_tests/remove_typedef/opts.txt | 1 - .../generics_tests/remove_typedef/output/output.go | 29 --- tools/go_generics/generics_tests/simple/input.go | 45 ---- tools/go_generics/generics_tests/simple/opts.txt | 1 - .../generics_tests/simple/output/output.go | 43 --- tools/go_generics/go_generics_unittest.sh | 70 ----- tools/go_generics/tests/BUILD | 0 tools/go_generics/tests/all_stmts/BUILD | 10 + tools/go_generics/tests/all_stmts/input.go | 290 +++++++++++++++++++++ tools/go_generics/tests/all_stmts/output.go | 288 ++++++++++++++++++++ tools/go_generics/tests/all_types/BUILD | 10 + tools/go_generics/tests/all_types/input.go | 45 ++++ tools/go_generics/tests/all_types/lib/lib.go | 17 ++ tools/go_generics/tests/all_types/output.go | 43 +++ tools/go_generics/tests/anon/BUILD | 12 + tools/go_generics/tests/anon/input.go | 46 ++++ tools/go_generics/tests/anon/output.go | 42 +++ tools/go_generics/tests/consts/BUILD | 17 ++ tools/go_generics/tests/consts/input.go | 26 ++ tools/go_generics/tests/consts/output.go | 26 ++ tools/go_generics/tests/defs.bzl | 67 +++++ tools/go_generics/tests/imports/BUILD | 18 ++ tools/go_generics/tests/imports/input.go | 24 ++ tools/go_generics/tests/imports/output.go | 27 ++ tools/go_generics/tests/remove_typedef/BUILD | 10 + tools/go_generics/tests/remove_typedef/input.go | 37 +++ tools/go_generics/tests/remove_typedef/output.go | 29 +++ tools/go_generics/tests/simple/BUILD | 11 + tools/go_generics/tests/simple/input.go | 45 ++++ tools/go_generics/tests/simple/output.go | 43 +++ 50 files changed, 1187 insertions(+), 1128 deletions(-) delete mode 100644 tools/go_generics/generics_tests/all_stmts/input.go delete mode 100644 tools/go_generics/generics_tests/all_stmts/opts.txt delete mode 100644 tools/go_generics/generics_tests/all_stmts/output/output.go delete mode 100644 tools/go_generics/generics_tests/all_types/input.go delete mode 100644 tools/go_generics/generics_tests/all_types/lib/lib.go delete mode 100644 tools/go_generics/generics_tests/all_types/opts.txt delete mode 100644 tools/go_generics/generics_tests/all_types/output/output.go delete mode 100644 tools/go_generics/generics_tests/anon/input.go delete mode 100644 tools/go_generics/generics_tests/anon/opts.txt delete mode 100644 tools/go_generics/generics_tests/anon/output/output.go delete mode 100644 tools/go_generics/generics_tests/consts/input.go delete mode 100644 tools/go_generics/generics_tests/consts/opts.txt delete mode 100644 tools/go_generics/generics_tests/consts/output/output.go delete mode 100644 tools/go_generics/generics_tests/imports/input.go delete mode 100644 tools/go_generics/generics_tests/imports/opts.txt delete mode 100644 tools/go_generics/generics_tests/imports/output/output.go delete mode 100644 tools/go_generics/generics_tests/remove_typedef/input.go delete mode 100644 tools/go_generics/generics_tests/remove_typedef/opts.txt delete mode 100644 tools/go_generics/generics_tests/remove_typedef/output/output.go delete mode 100644 tools/go_generics/generics_tests/simple/input.go delete mode 100644 tools/go_generics/generics_tests/simple/opts.txt delete mode 100644 tools/go_generics/generics_tests/simple/output/output.go delete mode 100755 tools/go_generics/go_generics_unittest.sh create mode 100644 tools/go_generics/tests/BUILD create mode 100644 tools/go_generics/tests/all_stmts/BUILD create mode 100644 tools/go_generics/tests/all_stmts/input.go create mode 100644 tools/go_generics/tests/all_stmts/output.go create mode 100644 tools/go_generics/tests/all_types/BUILD create mode 100644 tools/go_generics/tests/all_types/input.go create mode 100644 tools/go_generics/tests/all_types/lib/lib.go create mode 100644 tools/go_generics/tests/all_types/output.go create mode 100644 tools/go_generics/tests/anon/BUILD create mode 100644 tools/go_generics/tests/anon/input.go create mode 100644 tools/go_generics/tests/anon/output.go create mode 100644 tools/go_generics/tests/consts/BUILD create mode 100644 tools/go_generics/tests/consts/input.go create mode 100644 tools/go_generics/tests/consts/output.go create mode 100644 tools/go_generics/tests/defs.bzl create mode 100644 tools/go_generics/tests/imports/BUILD create mode 100644 tools/go_generics/tests/imports/input.go create mode 100644 tools/go_generics/tests/imports/output.go create mode 100644 tools/go_generics/tests/remove_typedef/BUILD create mode 100644 tools/go_generics/tests/remove_typedef/input.go create mode 100644 tools/go_generics/tests/remove_typedef/output.go create mode 100644 tools/go_generics/tests/simple/BUILD create mode 100644 tools/go_generics/tests/simple/input.go create mode 100644 tools/go_generics/tests/simple/output.go (limited to 'tools/go_generics') diff --git a/images/default/Dockerfile b/images/default/Dockerfile index 397082b02..2b38e6c58 100644 --- a/images/default/Dockerfile +++ b/images/default/Dockerfile @@ -1,7 +1,7 @@ FROM fedora:31 # Install bazel. RUN dnf install -y dnf-plugins-core && dnf copr enable -y vbatts/bazel -RUN dnf install -y git gcc make golang gcc-c++ glibc-devel python3 which python3-pip python3-devel libffi-devel openssl-devel pkg-config glibc-static libstdc++-static patch +RUN dnf install -y git gcc make golang gcc-c++ glibc-devel python3 which python3-pip python3-devel libffi-devel openssl-devel pkg-config glibc-static libstdc++-static patch diffutils RUN pip install pycparser RUN dnf install -y bazel3 # Install gcloud. diff --git a/tools/go_generics/BUILD b/tools/go_generics/BUILD index 32a949c93..558826bf1 100644 --- a/tools/go_generics/BUILD +++ b/tools/go_generics/BUILD @@ -12,27 +12,3 @@ go_binary( visibility = ["//:sandbox"], deps = ["//tools/go_generics/globals"], ) - -genrule( - name = "go_generics_tests", - srcs = glob(["generics_tests/**"]) + [":go_generics"], - outs = ["go_generics_tests.tgz"], - cmd = "tar -czvhf $@ $(SRCS)", -) - -genrule( - name = "go_generics_test_bundle", - srcs = [ - ":go_generics_tests.tgz", - ":go_generics_unittest.sh", - ], - outs = ["go_generics_test.sh"], - cmd = "cat $(location :go_generics_unittest.sh) $(location :go_generics_tests.tgz) > $@", - executable = True, -) - -sh_test( - name = "go_generics_test", - size = "small", - srcs = ["go_generics_test.sh"], -) diff --git a/tools/go_generics/defs.bzl b/tools/go_generics/defs.bzl index ec047a644..7fe7d7e59 100644 --- a/tools/go_generics/defs.bzl +++ b/tools/go_generics/defs.bzl @@ -100,7 +100,8 @@ def _go_template_instance_impl(ctx): # Build the argument list. args = ["-i=%s" % template.file.path, "-o=%s" % output.path] - args += ["-p=%s" % ctx.attr.package] + if ctx.attr.package: + args += ["-p=%s" % ctx.attr.package] if len(ctx.attr.prefix) > 0: args += ["-prefix=%s" % ctx.attr.prefix] @@ -151,7 +152,7 @@ go_template_instance = rule( "consts": attr.string_dict(), "imports": attr.string_dict(), "anon": attr.bool(mandatory = False, default = False), - "package": attr.string(mandatory = True), + "package": attr.string(mandatory = False), "out": attr.output(mandatory = True), "_tool": attr.label(executable = True, cfg = "host", default = Label("//tools/go_generics")), }, diff --git a/tools/go_generics/generics_tests/all_stmts/input.go b/tools/go_generics/generics_tests/all_stmts/input.go deleted file mode 100644 index 4791d1ff1..000000000 --- a/tools/go_generics/generics_tests/all_stmts/input.go +++ /dev/null @@ -1,290 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -import ( - "sync" -) - -type T int - -func h(T) { -} - -type s struct { - a, b int - c []int -} - -func g(T) *s { - return &s{} -} - -func f() (T, []int) { - // Branch. - goto T - goto R - - // Labeled. -T: - _ = T(0) - - // Empty. -R: - ; - - // Assignment with definition. - a, b, c := T(1), T(2), T(3) - _, _, _ = a, b, c - - // Assignment without definition. - g(T(0)).a, g(T(1)).b, c = int(T(1)), int(T(2)), T(3) - _, _, _ = a, b, c - - // Block. - { - var T T - T = 0 - _ = T - } - - // Declarations. - type Type T - const Const T = 10 - var g1 func(T, int, ...T) (int, T) - var v T - var w = T(0) - { - var T struct { - f []T - } - _ = T - } - - // Defer. - defer g1(T(0), 1) - - // Expression. - h(v + w + T(1)) - - // For statements. - for i := T(0); i < T(10); i++ { - var T func(int) T - v := T(0) - _ = v - } - - for { - var T func(int) T - v := T(0) - _ = v - } - - // Go. - go g1(T(0), 1) - - // If statements. - if a != T(1) { - var T func(int) T - v := T(0) - _ = v - } - - if a := T(0); a != T(1) { - var T func(int) T - v := T(0) - _ = v - } - - if a := T(0); a != T(1) { - var T func(int) T - v := T(0) - _ = v - } else if b := T(0); b != T(1) { - var T func(int) T - v := T(0) - _ = v - } else if T := T(0); T != 1 { - T++ - } else { - T-- - } - - if a := T(0); a != T(1) { - var T func(int) T - v := T(0) - _ = v - } else { - var T func(int) T - v := T(0) - _ = v - } - - // Inc/Dec statements. - (*(*T)(nil))++ - (*(*T)(nil))-- - - // Range statements. - for g(T(0)).a, g(T(1)).b = range g(T(10)).c { - var d T - _ = d - } - - for T, b := range g(T(10)).c { - _ = T - _ = b - } - - // Select statement. - { - var fch func(T) chan int - - select { - case <-fch(T(30)): - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - case T := <-fch(T(30)): - T = 0 - _ = T - case g(T(0)).a = <-fch(T(30)): - var T T - T = 0 - _ = T - case fch(T(30)) <- int(T(0)): - var T T - T = 0 - _ = T - } - } - - // Send statements. - { - var ch chan T - var fch func(T) chan int - - ch <- T(0) - fch(T(1)) <- g(T(10)).a - } - - // Switch statements. - { - var a T - var b int - switch { - case a == T(0): - var T T - T = 0 - _ = T - case a < T(0), b < g(T(10)).a: - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - } - - switch T(g(T(10)).a) { - case T(0): - var T T - T = 0 - _ = T - case T(1), T(g(T(10)).a): - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - - switch b := g(T(10)); T(b.a) + T(10) { - case T(0): - var T T - T = 0 - _ = T - case T(1), T(g(T(10)).a): - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - - // Type switch statements. - { - var interfaceFunc func(T) interface{} - - switch interfaceFunc(T(0)).(type) { - case *T, T, int: - var T T - T = 0 - _ = T - case sync.Mutex, **T: - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - - switch x := interfaceFunc(T(0)).(type) { - case *T, T, int: - var T T - T = 0 - _ = T - _ = x - case sync.Mutex, **T: - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - - switch t := T(0); x := interfaceFunc(T(0) + t).(type) { - case *T, T, int: - var T T - T = 0 - _ = T - _ = x - case sync.Mutex, **T: - var T T - T = 0 - _ = T - default: - var T T - T = 0 - _ = T - } - } - - // Return statement. - return T(10), g(T(11)).c -} diff --git a/tools/go_generics/generics_tests/all_stmts/opts.txt b/tools/go_generics/generics_tests/all_stmts/opts.txt deleted file mode 100644 index c9d0e09bf..000000000 --- a/tools/go_generics/generics_tests/all_stmts/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=Q diff --git a/tools/go_generics/generics_tests/all_stmts/output/output.go b/tools/go_generics/generics_tests/all_stmts/output/output.go deleted file mode 100644 index a53d84535..000000000 --- a/tools/go_generics/generics_tests/all_stmts/output/output.go +++ /dev/null @@ -1,288 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -import ( - "sync" -) - -func h(Q) { -} - -type s struct { - a, b int - c []int -} - -func g(Q) *s { - return &s{} -} - -func f() (Q, []int) { - // Branch. - goto T - goto R - - // Labeled. -T: - _ = Q(0) - - // Empty. -R: - ; - - // Assignment with definition. - a, b, c := Q(1), Q(2), Q(3) - _, _, _ = a, b, c - - // Assignment without definition. - g(Q(0)).a, g(Q(1)).b, c = int(Q(1)), int(Q(2)), Q(3) - _, _, _ = a, b, c - - // Block. - { - var T Q - T = 0 - _ = T - } - - // Declarations. - type Type Q - const Const Q = 10 - var g1 func(Q, int, ...Q) (int, Q) - var v Q - var w = Q(0) - { - var T struct { - f []Q - } - _ = T - } - - // Defer. - defer g1(Q(0), 1) - - // Expression. - h(v + w + Q(1)) - - // For statements. - for i := Q(0); i < Q(10); i++ { - var T func(int) Q - v := T(0) - _ = v - } - - for { - var T func(int) Q - v := T(0) - _ = v - } - - // Go. - go g1(Q(0), 1) - - // If statements. - if a != Q(1) { - var T func(int) Q - v := T(0) - _ = v - } - - if a := Q(0); a != Q(1) { - var T func(int) Q - v := T(0) - _ = v - } - - if a := Q(0); a != Q(1) { - var T func(int) Q - v := T(0) - _ = v - } else if b := Q(0); b != Q(1) { - var T func(int) Q - v := T(0) - _ = v - } else if T := Q(0); T != 1 { - T++ - } else { - T-- - } - - if a := Q(0); a != Q(1) { - var T func(int) Q - v := T(0) - _ = v - } else { - var T func(int) Q - v := T(0) - _ = v - } - - // Inc/Dec statements. - (*(*Q)(nil))++ - (*(*Q)(nil))-- - - // Range statements. - for g(Q(0)).a, g(Q(1)).b = range g(Q(10)).c { - var d Q - _ = d - } - - for T, b := range g(Q(10)).c { - _ = T - _ = b - } - - // Select statement. - { - var fch func(Q) chan int - - select { - case <-fch(Q(30)): - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - case T := <-fch(Q(30)): - T = 0 - _ = T - case g(Q(0)).a = <-fch(Q(30)): - var T Q - T = 0 - _ = T - case fch(Q(30)) <- int(Q(0)): - var T Q - T = 0 - _ = T - } - } - - // Send statements. - { - var ch chan Q - var fch func(Q) chan int - - ch <- Q(0) - fch(Q(1)) <- g(Q(10)).a - } - - // Switch statements. - { - var a Q - var b int - switch { - case a == Q(0): - var T Q - T = 0 - _ = T - case a < Q(0), b < g(Q(10)).a: - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - } - - switch Q(g(Q(10)).a) { - case Q(0): - var T Q - T = 0 - _ = T - case Q(1), Q(g(Q(10)).a): - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - - switch b := g(Q(10)); Q(b.a) + Q(10) { - case Q(0): - var T Q - T = 0 - _ = T - case Q(1), Q(g(Q(10)).a): - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - - // Type switch statements. - { - var interfaceFunc func(Q) interface{} - - switch interfaceFunc(Q(0)).(type) { - case *Q, Q, int: - var T Q - T = 0 - _ = T - case sync.Mutex, **Q: - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - - switch x := interfaceFunc(Q(0)).(type) { - case *Q, Q, int: - var T Q - T = 0 - _ = T - _ = x - case sync.Mutex, **Q: - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - - switch t := Q(0); x := interfaceFunc(Q(0) + t).(type) { - case *Q, Q, int: - var T Q - T = 0 - _ = T - _ = x - case sync.Mutex, **Q: - var T Q - T = 0 - _ = T - default: - var T Q - T = 0 - _ = T - } - } - - // Return statement. - return Q(10), g(Q(11)).c -} diff --git a/tools/go_generics/generics_tests/all_types/input.go b/tools/go_generics/generics_tests/all_types/input.go deleted file mode 100644 index 3575d02ec..000000000 --- a/tools/go_generics/generics_tests/all_types/input.go +++ /dev/null @@ -1,43 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -import "./lib" - -type T int - -type newType struct { - a T - b lib.T - c *T - d (T) - e chan T - f <-chan T - g chan<- T - h []T - i [10]T - j map[T]T - k func(T, T) (T, T) - l interface { - f(T) - } - m struct { - T - a T - } -} - -func f(...T) { -} diff --git a/tools/go_generics/generics_tests/all_types/lib/lib.go b/tools/go_generics/generics_tests/all_types/lib/lib.go deleted file mode 100644 index 988786496..000000000 --- a/tools/go_generics/generics_tests/all_types/lib/lib.go +++ /dev/null @@ -1,17 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package lib - -type T int32 diff --git a/tools/go_generics/generics_tests/all_types/opts.txt b/tools/go_generics/generics_tests/all_types/opts.txt deleted file mode 100644 index c9d0e09bf..000000000 --- a/tools/go_generics/generics_tests/all_types/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=Q diff --git a/tools/go_generics/generics_tests/all_types/output/output.go b/tools/go_generics/generics_tests/all_types/output/output.go deleted file mode 100644 index 41fd147a1..000000000 --- a/tools/go_generics/generics_tests/all_types/output/output.go +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -import "./lib" - -type newType struct { - a Q - b lib.T - c *Q - d (Q) - e chan Q - f <-chan Q - g chan<- Q - h []Q - i [10]Q - j map[Q]Q - k func(Q, Q) (Q, Q) - l interface { - f(Q) - } - m struct { - Q - a Q - } -} - -func f(...Q) { -} diff --git a/tools/go_generics/generics_tests/anon/input.go b/tools/go_generics/generics_tests/anon/input.go deleted file mode 100644 index 44086d522..000000000 --- a/tools/go_generics/generics_tests/anon/input.go +++ /dev/null @@ -1,46 +0,0 @@ -// Copyright 2019 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -type T interface { - Apply(T) T -} - -type Foo struct { - T - Bar map[string]T `json:"bar,omitempty"` -} - -type Baz struct { - T someTypeNotT -} - -func (f Foo) GetBar(name string) T { - b, ok := f.Bar[name] - if ok { - b = f.Apply(b) - } else { - b = f.T - } - return b -} - -func foobar() { - a := Baz{} - a.T = 0 // should not be renamed, this is a limitation - - b := otherpkg.UnrelatedType{} - b.T = 0 // should not be renamed, this is a limitation -} diff --git a/tools/go_generics/generics_tests/anon/opts.txt b/tools/go_generics/generics_tests/anon/opts.txt deleted file mode 100644 index a5e9d26de..000000000 --- a/tools/go_generics/generics_tests/anon/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=Q -suffix=New -anon diff --git a/tools/go_generics/generics_tests/anon/output/output.go b/tools/go_generics/generics_tests/anon/output/output.go deleted file mode 100644 index 160cddf79..000000000 --- a/tools/go_generics/generics_tests/anon/output/output.go +++ /dev/null @@ -1,42 +0,0 @@ -// Copyright 2019 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -type FooNew struct { - Q - Bar map[string]Q `json:"bar,omitempty"` -} - -type BazNew struct { - T someTypeNotT -} - -func (f FooNew) GetBar(name string) Q { - b, ok := f.Bar[name] - if ok { - b = f.Apply(b) - } else { - b = f.Q - } - return b -} - -func foobarNew() { - a := BazNew{} - a.Q = 0 // should not be renamed, this is a limitation - - b := otherpkg.UnrelatedType{} - b.Q = 0 // should not be renamed, this is a limitation -} diff --git a/tools/go_generics/generics_tests/consts/input.go b/tools/go_generics/generics_tests/consts/input.go deleted file mode 100644 index 04b95fcc6..000000000 --- a/tools/go_generics/generics_tests/consts/input.go +++ /dev/null @@ -1,26 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -const c1 = 10 -const x, y, z = 100, 200, 300 -const v float32 = 1.0 + 2.0 -const s = "abc" -const ( - A = 10 - B, C, D = 10, 20, 30 - S = "abc" - T, U, V string = "abc", "def", "ghi" -) diff --git a/tools/go_generics/generics_tests/consts/opts.txt b/tools/go_generics/generics_tests/consts/opts.txt deleted file mode 100644 index 4fb59dce8..000000000 --- a/tools/go_generics/generics_tests/consts/opts.txt +++ /dev/null @@ -1 +0,0 @@ --c=c1=20 -c=z=600 -c=v=3.3 -c=s="def" -c=A=20 -c=C=100 -c=S="def" -c=T="ABC" diff --git a/tools/go_generics/generics_tests/consts/output/output.go b/tools/go_generics/generics_tests/consts/output/output.go deleted file mode 100644 index 18d316cc9..000000000 --- a/tools/go_generics/generics_tests/consts/output/output.go +++ /dev/null @@ -1,26 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -const c1 = 20 -const x, y, z = 100, 200, 600 -const v float32 = 3.3 -const s = "def" -const ( - A = 20 - B, C, D = 10, 100, 30 - S = "def" - T, U, V string = "ABC", "def", "ghi" -) diff --git a/tools/go_generics/generics_tests/imports/input.go b/tools/go_generics/generics_tests/imports/input.go deleted file mode 100644 index 0f032c2a1..000000000 --- a/tools/go_generics/generics_tests/imports/input.go +++ /dev/null @@ -1,24 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -type T int - -var global T - -const ( - m = 0 - n = 0 -) diff --git a/tools/go_generics/generics_tests/imports/opts.txt b/tools/go_generics/generics_tests/imports/opts.txt deleted file mode 100644 index 87324be79..000000000 --- a/tools/go_generics/generics_tests/imports/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=sync.Mutex -c=n=math.Uint32 -c=m=math.Uint64 -import=sync=sync -import=math=mymathpath diff --git a/tools/go_generics/generics_tests/imports/output/output.go b/tools/go_generics/generics_tests/imports/output/output.go deleted file mode 100644 index 2488ca58c..000000000 --- a/tools/go_generics/generics_tests/imports/output/output.go +++ /dev/null @@ -1,27 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -import ( - __generics_imported1 "mymathpath" - __generics_imported0 "sync" -) - -var global __generics_imported0.Mutex - -const ( - m = __generics_imported1.Uint64 - n = __generics_imported1.Uint32 -) diff --git a/tools/go_generics/generics_tests/remove_typedef/input.go b/tools/go_generics/generics_tests/remove_typedef/input.go deleted file mode 100644 index cf632bae7..000000000 --- a/tools/go_generics/generics_tests/remove_typedef/input.go +++ /dev/null @@ -1,37 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -func f(T) Q { - return Q{} -} - -type T struct{} - -type Q struct{} - -func (*T) f() { -} - -func (T) g() { -} - -func (*Q) f(T) T { - return T{} -} - -func (*Q) g(T) *T { - return nil -} diff --git a/tools/go_generics/generics_tests/remove_typedef/opts.txt b/tools/go_generics/generics_tests/remove_typedef/opts.txt deleted file mode 100644 index 9c8ecaada..000000000 --- a/tools/go_generics/generics_tests/remove_typedef/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=U diff --git a/tools/go_generics/generics_tests/remove_typedef/output/output.go b/tools/go_generics/generics_tests/remove_typedef/output/output.go deleted file mode 100644 index d44fd8e1c..000000000 --- a/tools/go_generics/generics_tests/remove_typedef/output/output.go +++ /dev/null @@ -1,29 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -func f(U) Q { - return Q{} -} - -type Q struct{} - -func (*Q) f(U) U { - return U{} -} - -func (*Q) g(U) *U { - return nil -} diff --git a/tools/go_generics/generics_tests/simple/input.go b/tools/go_generics/generics_tests/simple/input.go deleted file mode 100644 index 2a917f16c..000000000 --- a/tools/go_generics/generics_tests/simple/input.go +++ /dev/null @@ -1,45 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package tests - -type T int - -var global T - -func f(_ T, a int) { -} - -func g(a T, b int) { - var c T - _ = c - - d := (*T)(nil) - _ = d -} - -type R struct { - T - a *T -} - -var ( - Z *T = (*T)(nil) -) - -const ( - X T = (T)(0) -) - -type Y T diff --git a/tools/go_generics/generics_tests/simple/opts.txt b/tools/go_generics/generics_tests/simple/opts.txt deleted file mode 100644 index 7832ef66f..000000000 --- a/tools/go_generics/generics_tests/simple/opts.txt +++ /dev/null @@ -1 +0,0 @@ --t=T=Q -suffix=New diff --git a/tools/go_generics/generics_tests/simple/output/output.go b/tools/go_generics/generics_tests/simple/output/output.go deleted file mode 100644 index 6bfa0b25b..000000000 --- a/tools/go_generics/generics_tests/simple/output/output.go +++ /dev/null @@ -1,43 +0,0 @@ -// Copyright 2018 The gVisor Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -package main - -var globalNew Q - -func fNew(_ Q, a int) { -} - -func gNew(a Q, b int) { - var c Q - _ = c - - d := (*Q)(nil) - _ = d -} - -type RNew struct { - Q - a *Q -} - -var ( - ZNew *Q = (*Q)(nil) -) - -const ( - XNew Q = (Q)(0) -) - -type YNew Q diff --git a/tools/go_generics/go_generics_unittest.sh b/tools/go_generics/go_generics_unittest.sh deleted file mode 100755 index 44b22db91..000000000 --- a/tools/go_generics/go_generics_unittest.sh +++ /dev/null @@ -1,70 +0,0 @@ -#!/bin/bash - -# Copyright 2018 The gVisor Authors. -# -# Licensed under the Apache License, Version 2.0 (the "License"); -# you may not use this file except in compliance with the License. -# You may obtain a copy of the License at -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -# Bash "safe-mode": Treat command failures as fatal (even those that occur in -# pipes), and treat unset variables as errors. -set -eu -o pipefail - -# This file will be generated as a self-extracting shell script in order to -# eliminate the need for any runtime dependencies. The tarball at the end will -# include the go_generics binary, as well as a subdirectory named -# generics_tests. See the BUILD file for more information. -declare -r temp=$(mktemp -d) -function cleanup() { - rm -rf "${temp}" -} -# trap cleanup EXIT - -# Print message in "$1" then exit with status 1. -function die () { - echo "$1" 1>&2 - exit 1 -} - -# This prints the line number of __BUNDLE__ below, that should be the last line -# of this script. After that point, the concatenated archive will be the -# contents. -declare -r tgz=`awk '/^__BUNDLE__/ {print NR + 1; exit 0; }' $0` -tail -n+"${tgz}" $0 | tar -xzv -C "${temp}" - -# The target for the test. -declare -r binary="$(find ${temp} -type f -a -name go_generics)" -declare -r input_dirs="$(find ${temp} -type d -a -name generics_tests)/*" - -# Go through all test cases. -for f in ${input_dirs}; do - base=$(basename "${f}") - - # Run go_generics on the input file. - opts=$(head -n 1 ${f}/opts.txt) - out="${f}/output/generated.go" - expected="${f}/output/output.go" - ${binary} ${opts} "-i=${f}/input.go" "-o=${out}" || die "go_generics failed for test case \"${base}\"" - - # Compare the outputs. - diff ${expected} ${out} - if [ $? -ne 0 ]; then - echo "Expected:" - cat ${expected} - echo "Actual:" - cat ${out} - die "Actual output is different from expected for test \"${base}\"" - fi -done - -echo "PASS" -exit 0 -__BUNDLE__ diff --git a/tools/go_generics/tests/BUILD b/tools/go_generics/tests/BUILD new file mode 100644 index 000000000..e69de29bb diff --git a/tools/go_generics/tests/all_stmts/BUILD b/tools/go_generics/tests/all_stmts/BUILD new file mode 100644 index 000000000..fbc07dbff --- /dev/null +++ b/tools/go_generics/tests/all_stmts/BUILD @@ -0,0 +1,10 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "all_stmts", + inputs = ["input.go"], + output = "output.go", + types = { + "T": "Q", + }, +) diff --git a/tools/go_generics/tests/all_stmts/input.go b/tools/go_generics/tests/all_stmts/input.go new file mode 100644 index 000000000..4791d1ff1 --- /dev/null +++ b/tools/go_generics/tests/all_stmts/input.go @@ -0,0 +1,290 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +import ( + "sync" +) + +type T int + +func h(T) { +} + +type s struct { + a, b int + c []int +} + +func g(T) *s { + return &s{} +} + +func f() (T, []int) { + // Branch. + goto T + goto R + + // Labeled. +T: + _ = T(0) + + // Empty. +R: + ; + + // Assignment with definition. + a, b, c := T(1), T(2), T(3) + _, _, _ = a, b, c + + // Assignment without definition. + g(T(0)).a, g(T(1)).b, c = int(T(1)), int(T(2)), T(3) + _, _, _ = a, b, c + + // Block. + { + var T T + T = 0 + _ = T + } + + // Declarations. + type Type T + const Const T = 10 + var g1 func(T, int, ...T) (int, T) + var v T + var w = T(0) + { + var T struct { + f []T + } + _ = T + } + + // Defer. + defer g1(T(0), 1) + + // Expression. + h(v + w + T(1)) + + // For statements. + for i := T(0); i < T(10); i++ { + var T func(int) T + v := T(0) + _ = v + } + + for { + var T func(int) T + v := T(0) + _ = v + } + + // Go. + go g1(T(0), 1) + + // If statements. + if a != T(1) { + var T func(int) T + v := T(0) + _ = v + } + + if a := T(0); a != T(1) { + var T func(int) T + v := T(0) + _ = v + } + + if a := T(0); a != T(1) { + var T func(int) T + v := T(0) + _ = v + } else if b := T(0); b != T(1) { + var T func(int) T + v := T(0) + _ = v + } else if T := T(0); T != 1 { + T++ + } else { + T-- + } + + if a := T(0); a != T(1) { + var T func(int) T + v := T(0) + _ = v + } else { + var T func(int) T + v := T(0) + _ = v + } + + // Inc/Dec statements. + (*(*T)(nil))++ + (*(*T)(nil))-- + + // Range statements. + for g(T(0)).a, g(T(1)).b = range g(T(10)).c { + var d T + _ = d + } + + for T, b := range g(T(10)).c { + _ = T + _ = b + } + + // Select statement. + { + var fch func(T) chan int + + select { + case <-fch(T(30)): + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + case T := <-fch(T(30)): + T = 0 + _ = T + case g(T(0)).a = <-fch(T(30)): + var T T + T = 0 + _ = T + case fch(T(30)) <- int(T(0)): + var T T + T = 0 + _ = T + } + } + + // Send statements. + { + var ch chan T + var fch func(T) chan int + + ch <- T(0) + fch(T(1)) <- g(T(10)).a + } + + // Switch statements. + { + var a T + var b int + switch { + case a == T(0): + var T T + T = 0 + _ = T + case a < T(0), b < g(T(10)).a: + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + } + + switch T(g(T(10)).a) { + case T(0): + var T T + T = 0 + _ = T + case T(1), T(g(T(10)).a): + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + + switch b := g(T(10)); T(b.a) + T(10) { + case T(0): + var T T + T = 0 + _ = T + case T(1), T(g(T(10)).a): + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + + // Type switch statements. + { + var interfaceFunc func(T) interface{} + + switch interfaceFunc(T(0)).(type) { + case *T, T, int: + var T T + T = 0 + _ = T + case sync.Mutex, **T: + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + + switch x := interfaceFunc(T(0)).(type) { + case *T, T, int: + var T T + T = 0 + _ = T + _ = x + case sync.Mutex, **T: + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + + switch t := T(0); x := interfaceFunc(T(0) + t).(type) { + case *T, T, int: + var T T + T = 0 + _ = T + _ = x + case sync.Mutex, **T: + var T T + T = 0 + _ = T + default: + var T T + T = 0 + _ = T + } + } + + // Return statement. + return T(10), g(T(11)).c +} diff --git a/tools/go_generics/tests/all_stmts/output.go b/tools/go_generics/tests/all_stmts/output.go new file mode 100644 index 000000000..a53d84535 --- /dev/null +++ b/tools/go_generics/tests/all_stmts/output.go @@ -0,0 +1,288 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +import ( + "sync" +) + +func h(Q) { +} + +type s struct { + a, b int + c []int +} + +func g(Q) *s { + return &s{} +} + +func f() (Q, []int) { + // Branch. + goto T + goto R + + // Labeled. +T: + _ = Q(0) + + // Empty. +R: + ; + + // Assignment with definition. + a, b, c := Q(1), Q(2), Q(3) + _, _, _ = a, b, c + + // Assignment without definition. + g(Q(0)).a, g(Q(1)).b, c = int(Q(1)), int(Q(2)), Q(3) + _, _, _ = a, b, c + + // Block. + { + var T Q + T = 0 + _ = T + } + + // Declarations. + type Type Q + const Const Q = 10 + var g1 func(Q, int, ...Q) (int, Q) + var v Q + var w = Q(0) + { + var T struct { + f []Q + } + _ = T + } + + // Defer. + defer g1(Q(0), 1) + + // Expression. + h(v + w + Q(1)) + + // For statements. + for i := Q(0); i < Q(10); i++ { + var T func(int) Q + v := T(0) + _ = v + } + + for { + var T func(int) Q + v := T(0) + _ = v + } + + // Go. + go g1(Q(0), 1) + + // If statements. + if a != Q(1) { + var T func(int) Q + v := T(0) + _ = v + } + + if a := Q(0); a != Q(1) { + var T func(int) Q + v := T(0) + _ = v + } + + if a := Q(0); a != Q(1) { + var T func(int) Q + v := T(0) + _ = v + } else if b := Q(0); b != Q(1) { + var T func(int) Q + v := T(0) + _ = v + } else if T := Q(0); T != 1 { + T++ + } else { + T-- + } + + if a := Q(0); a != Q(1) { + var T func(int) Q + v := T(0) + _ = v + } else { + var T func(int) Q + v := T(0) + _ = v + } + + // Inc/Dec statements. + (*(*Q)(nil))++ + (*(*Q)(nil))-- + + // Range statements. + for g(Q(0)).a, g(Q(1)).b = range g(Q(10)).c { + var d Q + _ = d + } + + for T, b := range g(Q(10)).c { + _ = T + _ = b + } + + // Select statement. + { + var fch func(Q) chan int + + select { + case <-fch(Q(30)): + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + case T := <-fch(Q(30)): + T = 0 + _ = T + case g(Q(0)).a = <-fch(Q(30)): + var T Q + T = 0 + _ = T + case fch(Q(30)) <- int(Q(0)): + var T Q + T = 0 + _ = T + } + } + + // Send statements. + { + var ch chan Q + var fch func(Q) chan int + + ch <- Q(0) + fch(Q(1)) <- g(Q(10)).a + } + + // Switch statements. + { + var a Q + var b int + switch { + case a == Q(0): + var T Q + T = 0 + _ = T + case a < Q(0), b < g(Q(10)).a: + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + } + + switch Q(g(Q(10)).a) { + case Q(0): + var T Q + T = 0 + _ = T + case Q(1), Q(g(Q(10)).a): + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + + switch b := g(Q(10)); Q(b.a) + Q(10) { + case Q(0): + var T Q + T = 0 + _ = T + case Q(1), Q(g(Q(10)).a): + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + + // Type switch statements. + { + var interfaceFunc func(Q) interface{} + + switch interfaceFunc(Q(0)).(type) { + case *Q, Q, int: + var T Q + T = 0 + _ = T + case sync.Mutex, **Q: + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + + switch x := interfaceFunc(Q(0)).(type) { + case *Q, Q, int: + var T Q + T = 0 + _ = T + _ = x + case sync.Mutex, **Q: + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + + switch t := Q(0); x := interfaceFunc(Q(0) + t).(type) { + case *Q, Q, int: + var T Q + T = 0 + _ = T + _ = x + case sync.Mutex, **Q: + var T Q + T = 0 + _ = T + default: + var T Q + T = 0 + _ = T + } + } + + // Return statement. + return Q(10), g(Q(11)).c +} diff --git a/tools/go_generics/tests/all_types/BUILD b/tools/go_generics/tests/all_types/BUILD new file mode 100644 index 000000000..9144b0811 --- /dev/null +++ b/tools/go_generics/tests/all_types/BUILD @@ -0,0 +1,10 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "all_types", + inputs = ["input.go"], + output = "output.go", + types = { + "T": "Q", + }, +) diff --git a/tools/go_generics/tests/all_types/input.go b/tools/go_generics/tests/all_types/input.go new file mode 100644 index 000000000..6f85bbb69 --- /dev/null +++ b/tools/go_generics/tests/all_types/input.go @@ -0,0 +1,45 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +import ( + "./lib" +) + +type T int + +type newType struct { + a T + b lib.T + c *T + d (T) + e chan T + f <-chan T + g chan<- T + h []T + i [10]T + j map[T]T + k func(T, T) (T, T) + l interface { + f(T) + } + m struct { + T + a T + } +} + +func f(...T) { +} diff --git a/tools/go_generics/tests/all_types/lib/lib.go b/tools/go_generics/tests/all_types/lib/lib.go new file mode 100644 index 000000000..988786496 --- /dev/null +++ b/tools/go_generics/tests/all_types/lib/lib.go @@ -0,0 +1,17 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package lib + +type T int32 diff --git a/tools/go_generics/tests/all_types/output.go b/tools/go_generics/tests/all_types/output.go new file mode 100644 index 000000000..c0bbebfe7 --- /dev/null +++ b/tools/go_generics/tests/all_types/output.go @@ -0,0 +1,43 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +import ( + "./lib" +) + +type newType struct { + a Q + b lib.T + c *Q + d (Q) + e chan Q + f <-chan Q + g chan<- Q + h []Q + i [10]Q + j map[Q]Q + k func(Q, Q) (Q, Q) + l interface { + f(Q) + } + m struct { + Q + a Q + } +} + +func f(...Q) { +} diff --git a/tools/go_generics/tests/anon/BUILD b/tools/go_generics/tests/anon/BUILD new file mode 100644 index 000000000..1890f2817 --- /dev/null +++ b/tools/go_generics/tests/anon/BUILD @@ -0,0 +1,12 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "anon", + anon = True, + inputs = ["input.go"], + output = "output.go", + suffix = "New", + types = { + "T": "Q", + }, +) diff --git a/tools/go_generics/tests/anon/input.go b/tools/go_generics/tests/anon/input.go new file mode 100644 index 000000000..44086d522 --- /dev/null +++ b/tools/go_generics/tests/anon/input.go @@ -0,0 +1,46 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +type T interface { + Apply(T) T +} + +type Foo struct { + T + Bar map[string]T `json:"bar,omitempty"` +} + +type Baz struct { + T someTypeNotT +} + +func (f Foo) GetBar(name string) T { + b, ok := f.Bar[name] + if ok { + b = f.Apply(b) + } else { + b = f.T + } + return b +} + +func foobar() { + a := Baz{} + a.T = 0 // should not be renamed, this is a limitation + + b := otherpkg.UnrelatedType{} + b.T = 0 // should not be renamed, this is a limitation +} diff --git a/tools/go_generics/tests/anon/output.go b/tools/go_generics/tests/anon/output.go new file mode 100644 index 000000000..7fa791853 --- /dev/null +++ b/tools/go_generics/tests/anon/output.go @@ -0,0 +1,42 @@ +// Copyright 2019 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +type FooNew struct { + Q + Bar map[string]Q `json:"bar,omitempty"` +} + +type BazNew struct { + T someTypeNotT +} + +func (f FooNew) GetBar(name string) Q { + b, ok := f.Bar[name] + if ok { + b = f.Apply(b) + } else { + b = f.Q + } + return b +} + +func foobarNew() { + a := BazNew{} + a.Q = 0 + + b := otherpkg.UnrelatedType{} + b.Q = 0 +} diff --git a/tools/go_generics/tests/consts/BUILD b/tools/go_generics/tests/consts/BUILD new file mode 100644 index 000000000..1e3574593 --- /dev/null +++ b/tools/go_generics/tests/consts/BUILD @@ -0,0 +1,17 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "consts", + consts = { + "c1": "20", + "z": "600", + "v": "3.3", + "s": "\"def\"", + "A": "20", + "C": "100", + "S": "\"def\"", + "T": "\"ABC\"", + }, + inputs = ["input.go"], + output = "output.go", +) diff --git a/tools/go_generics/tests/consts/input.go b/tools/go_generics/tests/consts/input.go new file mode 100644 index 000000000..04b95fcc6 --- /dev/null +++ b/tools/go_generics/tests/consts/input.go @@ -0,0 +1,26 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +const c1 = 10 +const x, y, z = 100, 200, 300 +const v float32 = 1.0 + 2.0 +const s = "abc" +const ( + A = 10 + B, C, D = 10, 20, 30 + S = "abc" + T, U, V string = "abc", "def", "ghi" +) diff --git a/tools/go_generics/tests/consts/output.go b/tools/go_generics/tests/consts/output.go new file mode 100644 index 000000000..18d316cc9 --- /dev/null +++ b/tools/go_generics/tests/consts/output.go @@ -0,0 +1,26 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +const c1 = 20 +const x, y, z = 100, 200, 600 +const v float32 = 3.3 +const s = "def" +const ( + A = 20 + B, C, D = 10, 100, 30 + S = "def" + T, U, V string = "ABC", "def", "ghi" +) diff --git a/tools/go_generics/tests/defs.bzl b/tools/go_generics/tests/defs.bzl new file mode 100644 index 000000000..038629852 --- /dev/null +++ b/tools/go_generics/tests/defs.bzl @@ -0,0 +1,67 @@ +"""Generics tests.""" + +load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance") + +def _go_generics_test_impl(ctx): + runner = ctx.actions.declare_file(ctx.label.name) + runner_content = "\n".join([ + "#!/bin/bash", + "exec diff --ignore-blank-lines --ignore-matching-lines=^[[:space:]]*// %s %s" % ( + ctx.files.template_output[0].short_path, + ctx.files.expected_output[0].short_path, + ), + "", + ]) + ctx.actions.write(runner, runner_content, is_executable = True) + return [DefaultInfo( + executable = runner, + runfiles = ctx.runfiles( + files = ctx.files.template_output + ctx.files.expected_output, + collect_default = True, + collect_data = True, + ), + )] + +_go_generics_test = rule( + implementation = _go_generics_test_impl, + attrs = { + "template_output": attr.label(mandatory = True, allow_single_file = True), + "expected_output": attr.label(mandatory = True, allow_single_file = True), + }, + test = True, +) + +""" +Instantiates a generics test. + +Args: + name: the name of the test. + inputs: all the input files. + output: the output files. + opts: the template options. +""" + +def go_generics_test(name, inputs, output, types = None, consts = None, **kwargs): + if types == None: + types = dict() + if consts == None: + consts = dict() + go_template( + name = name + "_template", + srcs = inputs, + types = types.keys(), + consts = consts.keys(), + ) + go_template_instance( + name = name + "_output", + template = ":" + name + "_template", + out = name + "_output.go", + types = types, + consts = consts, + **kwargs + ) + _go_generics_test( + name = name + "_test", + template_output = name + "_output.go", + expected_output = output, + ) diff --git a/tools/go_generics/tests/imports/BUILD b/tools/go_generics/tests/imports/BUILD new file mode 100644 index 000000000..c4424ee9c --- /dev/null +++ b/tools/go_generics/tests/imports/BUILD @@ -0,0 +1,18 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "imports", + consts = { + "n": "math.Uint32", + "m": "math.Uint64", + }, + imports = { + "sync": "sync", + "math": "mymathpath", + }, + inputs = ["input.go"], + output = "output.go", + types = { + "T": "sync.Mutex", + }, +) diff --git a/tools/go_generics/tests/imports/input.go b/tools/go_generics/tests/imports/input.go new file mode 100644 index 000000000..0f032c2a1 --- /dev/null +++ b/tools/go_generics/tests/imports/input.go @@ -0,0 +1,24 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +type T int + +var global T + +const ( + m = 0 + n = 0 +) diff --git a/tools/go_generics/tests/imports/output.go b/tools/go_generics/tests/imports/output.go new file mode 100644 index 000000000..2488ca58c --- /dev/null +++ b/tools/go_generics/tests/imports/output.go @@ -0,0 +1,27 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +import ( + __generics_imported1 "mymathpath" + __generics_imported0 "sync" +) + +var global __generics_imported0.Mutex + +const ( + m = __generics_imported1.Uint64 + n = __generics_imported1.Uint32 +) diff --git a/tools/go_generics/tests/remove_typedef/BUILD b/tools/go_generics/tests/remove_typedef/BUILD new file mode 100644 index 000000000..84f6ac1ab --- /dev/null +++ b/tools/go_generics/tests/remove_typedef/BUILD @@ -0,0 +1,10 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "remove_typedef", + inputs = ["input.go"], + output = "output.go", + types = { + "T": "U", + }, +) diff --git a/tools/go_generics/tests/remove_typedef/input.go b/tools/go_generics/tests/remove_typedef/input.go new file mode 100644 index 000000000..cf632bae7 --- /dev/null +++ b/tools/go_generics/tests/remove_typedef/input.go @@ -0,0 +1,37 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +func f(T) Q { + return Q{} +} + +type T struct{} + +type Q struct{} + +func (*T) f() { +} + +func (T) g() { +} + +func (*Q) f(T) T { + return T{} +} + +func (*Q) g(T) *T { + return nil +} diff --git a/tools/go_generics/tests/remove_typedef/output.go b/tools/go_generics/tests/remove_typedef/output.go new file mode 100644 index 000000000..d44fd8e1c --- /dev/null +++ b/tools/go_generics/tests/remove_typedef/output.go @@ -0,0 +1,29 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +func f(U) Q { + return Q{} +} + +type Q struct{} + +func (*Q) f(U) U { + return U{} +} + +func (*Q) g(U) *U { + return nil +} diff --git a/tools/go_generics/tests/simple/BUILD b/tools/go_generics/tests/simple/BUILD new file mode 100644 index 000000000..204952b90 --- /dev/null +++ b/tools/go_generics/tests/simple/BUILD @@ -0,0 +1,11 @@ +load("//tools/go_generics/tests:defs.bzl", "go_generics_test") + +go_generics_test( + name = "simple", + inputs = ["input.go"], + output = "output.go", + suffix = "New", + types = { + "T": "Q", + }, +) diff --git a/tools/go_generics/tests/simple/input.go b/tools/go_generics/tests/simple/input.go new file mode 100644 index 000000000..2a917f16c --- /dev/null +++ b/tools/go_generics/tests/simple/input.go @@ -0,0 +1,45 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package tests + +type T int + +var global T + +func f(_ T, a int) { +} + +func g(a T, b int) { + var c T + _ = c + + d := (*T)(nil) + _ = d +} + +type R struct { + T + a *T +} + +var ( + Z *T = (*T)(nil) +) + +const ( + X T = (T)(0) +) + +type Y T diff --git a/tools/go_generics/tests/simple/output.go b/tools/go_generics/tests/simple/output.go new file mode 100644 index 000000000..6bfa0b25b --- /dev/null +++ b/tools/go_generics/tests/simple/output.go @@ -0,0 +1,43 @@ +// Copyright 2018 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package main + +var globalNew Q + +func fNew(_ Q, a int) { +} + +func gNew(a Q, b int) { + var c Q + _ = c + + d := (*Q)(nil) + _ = d +} + +type RNew struct { + Q + a *Q +} + +var ( + ZNew *Q = (*Q)(nil) +) + +const ( + XNew Q = (Q)(0) +) + +type YNew Q -- cgit v1.2.3 From 90021e775a6e8059ea4f4262a16c4f962d3b9732 Mon Sep 17 00:00:00 2001 From: Adin Scannell Date: Thu, 6 Aug 2020 12:08:12 -0700 Subject: Add bzl_library rules for .bzl files without one. PiperOrigin-RevId: 325280924 --- benchmarks/BUILD | 8 ++++++++ test/packetdrill/BUILD | 9 ++++++++- test/packetimpact/runner/BUILD | 8 +++++++- test/runner/BUILD | 8 +++++++- test/runtimes/BUILD | 7 +++++++ test/runtimes/defs.bzl | 4 ++++ tools/BUILD | 8 ++++++++ tools/bazeldefs/BUILD | 20 +++++++++++++++++++- tools/bazeldefs/defs.bzl | 2 ++ tools/defs.bzl | 3 ++- tools/go_generics/BUILD | 8 +++++++- tools/go_generics/tests/BUILD | 7 +++++++ tools/go_marshal/BUILD | 8 +++++++- tools/go_stateify/BUILD | 8 +++++++- tools/nogo/BUILD | 8 +++++++- tools/vm/BUILD | 8 +++++++- website/BUILD | 8 +++++++- 17 files changed, 121 insertions(+), 11 deletions(-) (limited to 'tools/go_generics') diff --git a/benchmarks/BUILD b/benchmarks/BUILD index 389351210..39ca5919c 100644 --- a/benchmarks/BUILD +++ b/benchmarks/BUILD @@ -1,3 +1,5 @@ +load("//tools:defs.bzl", "bzl_library") + package(licenses = ["notice"]) config_setting( @@ -27,3 +29,9 @@ py_binary( ], deps = ["//benchmarks/runner"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/test/packetdrill/BUILD b/test/packetdrill/BUILD index dfcd55f60..49642f282 100644 --- a/test/packetdrill/BUILD +++ b/test/packetdrill/BUILD @@ -1,4 +1,5 @@ -load("defs.bzl", "packetdrill_test") +load("//tools:defs.bzl", "bzl_library") +load("//test/packetdrill:defs.bzl", "packetdrill_test") package(licenses = ["notice"]) @@ -36,3 +37,9 @@ packetdrill_test( name = "tcp_defer_accept_timeout_test", scripts = ["tcp_defer_accept_timeout.pkt"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/test/packetimpact/runner/BUILD b/test/packetimpact/runner/BUILD index bad4f0183..ff2be9b30 100644 --- a/test/packetimpact/runner/BUILD +++ b/test/packetimpact/runner/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_test") +load("//tools:defs.bzl", "bzl_library", "go_test") package( default_visibility = ["//test/packetimpact:__subpackages__"], @@ -19,3 +19,9 @@ go_test( "@com_github_docker_docker//api/types/mount:go_default_library", ], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/test/runner/BUILD b/test/runner/BUILD index 63c7ec83a..582d2946d 100644 --- a/test/runner/BUILD +++ b/test/runner/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_binary") +load("//tools:defs.bzl", "bzl_library", "go_binary") package(licenses = ["notice"]) @@ -21,3 +21,9 @@ go_binary( "@org_golang_x_sys//unix:go_default_library", ], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/test/runtimes/BUILD b/test/runtimes/BUILD index 3d0f10855..066338ee3 100644 --- a/test/runtimes/BUILD +++ b/test/runtimes/BUILD @@ -1,3 +1,4 @@ +load("//tools:defs.bzl", "bzl_library") load("//test/runtimes:defs.bzl", "runtime_test") package(licenses = ["notice"]) @@ -37,3 +38,9 @@ runtime_test( lang = "python", shard_count = 8, ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/test/runtimes/defs.bzl b/test/runtimes/defs.bzl index db22029a8..702522d86 100644 --- a/test/runtimes/defs.bzl +++ b/test/runtimes/defs.bzl @@ -55,9 +55,13 @@ _runtime_test = rule( ), "_runner": attr.label( default = "//test/runtimes/runner:runner", + executable = True, + cfg = "target", ), "_proctor": attr.label( default = "//test/runtimes/proctor:proctor", + executable = True, + cfg = "target", ), }, test = True, diff --git a/tools/BUILD b/tools/BUILD index 34b950644..da83877b1 100644 --- a/tools/BUILD +++ b/tools/BUILD @@ -1 +1,9 @@ +load("//tools:defs.bzl", "bzl_library") + package(licenses = ["notice"]) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/bazeldefs/BUILD b/tools/bazeldefs/BUILD index 3f809065d..8d4356119 100644 --- a/tools/bazeldefs/BUILD +++ b/tools/bazeldefs/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "rbe_platform", "rbe_toolchain") +load("//tools:defs.bzl", "bzl_library", "rbe_platform", "rbe_toolchain") package(licenses = ["notice"]) @@ -86,3 +86,21 @@ rbe_toolchain( toolchain = "@bazel_toolchains_bazel3//configs/ubuntu16_04_clang/11.0.0/bazel_3.1.0/cc:cc-compiler-k8", toolchain_type = "@bazel_tools//tools/cpp:toolchain_type", ) + +bzl_library( + name = "platforms_bzl", + srcs = ["platforms.bzl"], + visibility = ["//visibility:private"], +) + +bzl_library( + name = "tags_bzl", + srcs = ["tags.bzl"], + visibility = ["//visibility:private"], +) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/bazeldefs/defs.bzl b/tools/bazeldefs/defs.bzl index 3db8e13d0..d0096dcec 100644 --- a/tools/bazeldefs/defs.bzl +++ b/tools/bazeldefs/defs.bzl @@ -2,6 +2,7 @@ load("@bazel_gazelle//:def.bzl", _gazelle = "gazelle") load("@bazel_skylib//rules:build_test.bzl", _build_test = "build_test") +load("@bazel_skylib//:bzl_library.bzl", _bzl_library = "bzl_library") load("@bazel_tools//tools/cpp:cc_flags_supplier.bzl", _cc_flags_supplier = "cc_flags_supplier") load("@io_bazel_rules_go//go:def.bzl", "GoLibrary", _go_binary = "go_binary", _go_context = "go_context", _go_embed_data = "go_embed_data", _go_library = "go_library", _go_path = "go_path", _go_test = "go_test") load("@io_bazel_rules_go//proto:def.bzl", _go_grpc_library = "go_grpc_library", _go_proto_library = "go_proto_library") @@ -11,6 +12,7 @@ load("@pydeps//:requirements.bzl", _py_requirement = "requirement") load("@com_github_grpc_grpc//bazel:cc_grpc_library.bzl", _cc_grpc_library = "cc_grpc_library") build_test = _build_test +bzl_library = _bzl_library cc_library = _cc_library cc_flags_supplier = _cc_flags_supplier cc_proto_library = _cc_proto_library diff --git a/tools/defs.bzl b/tools/defs.bzl index e35e29634..b64d735e6 100644 --- a/tools/defs.bzl +++ b/tools/defs.bzl @@ -7,13 +7,14 @@ change for Google-internal and bazel-compatible rules. load("//tools/go_stateify:defs.bzl", "go_stateify") load("//tools/go_marshal:defs.bzl", "go_marshal", "marshal_deps", "marshal_test_deps") -load("//tools/bazeldefs:defs.bzl", _build_test = "build_test", _cc_binary = "cc_binary", _cc_flags_supplier = "cc_flags_supplier", _cc_grpc_library = "cc_grpc_library", _cc_library = "cc_library", _cc_proto_library = "cc_proto_library", _cc_test = "cc_test", _cc_toolchain = "cc_toolchain", _default_installer = "default_installer", _default_net_util = "default_net_util", _gazelle = "gazelle", _gbenchmark = "gbenchmark", _go_binary = "go_binary", _go_embed_data = "go_embed_data", _go_grpc_and_proto_libraries = "go_grpc_and_proto_libraries", _go_library = "go_library", _go_path = "go_path", _go_proto_library = "go_proto_library", _go_test = "go_test", _grpcpp = "grpcpp", _gtest = "gtest", _loopback = "loopback", _pkg_deb = "pkg_deb", _pkg_tar = "pkg_tar", _proto_library = "proto_library", _py_binary = "py_binary", _py_library = "py_library", _py_requirement = "py_requirement", _py_test = "py_test", _rbe_platform = "rbe_platform", _rbe_toolchain = "rbe_toolchain", _select_arch = "select_arch", _select_system = "select_system", _short_path = "short_path", _vdso_linker_option = "vdso_linker_option") +load("//tools/bazeldefs:defs.bzl", _build_test = "build_test", _bzl_library = "bzl_library", _cc_binary = "cc_binary", _cc_flags_supplier = "cc_flags_supplier", _cc_grpc_library = "cc_grpc_library", _cc_library = "cc_library", _cc_proto_library = "cc_proto_library", _cc_test = "cc_test", _cc_toolchain = "cc_toolchain", _default_installer = "default_installer", _default_net_util = "default_net_util", _gazelle = "gazelle", _gbenchmark = "gbenchmark", _go_binary = "go_binary", _go_embed_data = "go_embed_data", _go_grpc_and_proto_libraries = "go_grpc_and_proto_libraries", _go_library = "go_library", _go_path = "go_path", _go_proto_library = "go_proto_library", _go_test = "go_test", _grpcpp = "grpcpp", _gtest = "gtest", _loopback = "loopback", _pkg_deb = "pkg_deb", _pkg_tar = "pkg_tar", _proto_library = "proto_library", _py_binary = "py_binary", _py_library = "py_library", _py_requirement = "py_requirement", _py_test = "py_test", _rbe_platform = "rbe_platform", _rbe_toolchain = "rbe_toolchain", _select_arch = "select_arch", _select_system = "select_system", _short_path = "short_path", _vdso_linker_option = "vdso_linker_option") load("//tools/bazeldefs:platforms.bzl", _default_platform = "default_platform", _platforms = "platforms") load("//tools/bazeldefs:tags.bzl", "go_suffixes") load("//tools/nogo:defs.bzl", "nogo_test") # Delegate directly. build_test = _build_test +bzl_library = _bzl_library cc_binary = _cc_binary cc_flags_supplier = _cc_flags_supplier cc_grpc_library = _cc_grpc_library diff --git a/tools/go_generics/BUILD b/tools/go_generics/BUILD index 558826bf1..807c08ead 100644 --- a/tools/go_generics/BUILD +++ b/tools/go_generics/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_binary") +load("//tools:defs.bzl", "bzl_library", "go_binary") package(licenses = ["notice"]) @@ -12,3 +12,9 @@ go_binary( visibility = ["//:sandbox"], deps = ["//tools/go_generics/globals"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/go_generics/tests/BUILD b/tools/go_generics/tests/BUILD index e69de29bb..7547a6b53 100644 --- a/tools/go_generics/tests/BUILD +++ b/tools/go_generics/tests/BUILD @@ -0,0 +1,7 @@ +load("//tools:defs.bzl", "bzl_library") + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/go_marshal/BUILD b/tools/go_marshal/BUILD index be49cf9c8..f79defea7 100644 --- a/tools/go_marshal/BUILD +++ b/tools/go_marshal/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_binary") +load("//tools:defs.bzl", "bzl_library", "go_binary") licenses(["notice"]) @@ -17,3 +17,9 @@ config_setting( name = "marshal_config_verbose", values = {"define": "gomarshal=verbose"}, ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/go_stateify/BUILD b/tools/go_stateify/BUILD index 503cdf2e5..913558b4e 100644 --- a/tools/go_stateify/BUILD +++ b/tools/go_stateify/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_binary") +load("//tools:defs.bzl", "bzl_library", "go_binary") package(licenses = ["notice"]) @@ -8,3 +8,9 @@ go_binary( visibility = ["//:sandbox"], deps = ["//tools/tags"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/nogo/BUILD b/tools/nogo/BUILD index c21b09511..e1bfb9a2c 100644 --- a/tools/nogo/BUILD +++ b/tools/nogo/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "go_library") +load("//tools:defs.bzl", "bzl_library", "go_library") package(licenses = ["notice"]) @@ -47,3 +47,9 @@ go_library( "@org_golang_x_tools//go/gcexportdata:go_tool_library", ], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/tools/vm/BUILD b/tools/vm/BUILD index f7160c627..d95ca6c63 100644 --- a/tools/vm/BUILD +++ b/tools/vm/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "cc_binary", "gtest") +load("//tools:defs.bzl", "bzl_library", "cc_binary", "gtest") load("//tools/vm:defs.bzl", "vm_image", "vm_test") package( @@ -55,3 +55,9 @@ vm_test( shard_count = 2, targets = [":test"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) diff --git a/website/BUILD b/website/BUILD index d3bcaa09e..7b61d13c8 100644 --- a/website/BUILD +++ b/website/BUILD @@ -1,4 +1,4 @@ -load("//tools:defs.bzl", "pkg_tar") +load("//tools:defs.bzl", "bzl_library", "pkg_tar") load("//website:defs.bzl", "doc", "docs") package(licenses = ["notice"]) @@ -180,3 +180,9 @@ genrule( "rm -rf $$T", tools = ["//website/cmd/syscalldocs"], ) + +bzl_library( + name = "defs_bzl", + srcs = ["defs.bzl"], + visibility = ["//visibility:private"], +) -- cgit v1.2.3