internal/godoc/internal/doc: sort playable example imports
When constructing a playable example, sort the import
declarations in the usual way, with standard library
imports first.
For golang/go#43658
Change-Id: I47008caf6c2dfa0d66351e7ffb887b0880065fcd
Reviewed-on: https://go-review.googlesource.com/c/pkgsite/+/285812
Trust: Jonathan Amsterdam <jba@google.com>
Run-TryBot: Jonathan Amsterdam <jba@google.com>
TryBot-Result: kokoro <noreply+kokoro@google.com>
Reviewed-by: Julie Qiu <julie@golang.org>
diff --git a/internal/godoc/internal/doc/doc.go b/internal/godoc/internal/doc/doc.go
index 4e8b808..787984a 100644
--- a/internal/godoc/internal/doc/doc.go
+++ b/internal/godoc/internal/doc/doc.go
@@ -209,7 +209,7 @@
// Compute package documentation.
pkg, _ := ast.NewPackage(fset, goFiles, simpleImporter, nil) // Ignore errors that can happen due to unresolved identifiers.
p := New(pkg, importPath, mode)
- classifyExamples(p, Examples(testGoFiles...))
+ classifyExamples(p, Examples(fset, testGoFiles...))
return p, nil
}
diff --git a/internal/godoc/internal/doc/example.go b/internal/godoc/internal/doc/example.go
index 13938a5..3ef4e70 100644
--- a/internal/godoc/internal/doc/example.go
+++ b/internal/godoc/internal/doc/example.go
@@ -47,7 +47,7 @@
// example function, zero test or benchmark functions, and at least one
// top-level function, type, variable, or constant declaration other
// than the example function.
-func Examples(testFiles ...*ast.File) []*Example {
+func Examples(fset *token.FileSet, testFiles ...*ast.File) []*Example {
var list []*Example
for _, file := range testFiles {
hasTests := false // file contains tests or benchmarks
@@ -86,7 +86,7 @@
Name: name[len("Example"):],
Doc: doc,
Code: f.Body,
- Play: playExample(file, f),
+ Play: playExample(fset, file, f),
Comments: file.Comments,
Output: output,
Unordered: unordered,
@@ -149,9 +149,9 @@
// playExample synthesizes a new *ast.File based on the provided
// file with the provided function body as the body of main.
-func playExample(file *ast.File, f *ast.FuncDecl) *ast.File {
+func playExample(fset *token.FileSet, file *ast.File, f *ast.FuncDecl) *ast.File {
body := f.Body
-
+ tokenFile := fset.File(file.Package)
if !strings.HasSuffix(file.Name.Name, "_test") {
// We don't support examples that are part of the
// greater package (yet).
@@ -243,7 +243,6 @@
switch s := spec.(type) {
case *ast.TypeSpec:
ast.Inspect(s.Type, inspectFunc)
-
depDecls = append(depDecls, typMethods[s.Name.Name]...)
case *ast.ValueSpec:
if s.Type != nil {
@@ -336,20 +335,7 @@
}
}
- // Synthesize import declaration.
- importDecl := &ast.GenDecl{
- Tok: token.IMPORT,
- Lparen: 1, // Need non-zero Lparen and Rparen so that printer
- Rparen: 1, // treats this as a factored import.
- }
- for n, p := range namedImports {
- s := &ast.ImportSpec{Path: &ast.BasicLit{Value: strconv.Quote(p)}}
- if path.Base(p) != n {
- s.Name = ast.NewIdent(n)
- }
- importDecl.Specs = append(importDecl.Specs, s)
- }
- importDecl.Specs = append(importDecl.Specs, blankImports...)
+ importDecl := synthesizeImportDecl(namedImports, blankImports, tokenFile)
// Synthesize main function.
funcDecl := &ast.FuncDecl{
@@ -379,6 +365,53 @@
}
}
+// synthesizeImportDecl creates the imports for the example. We want the imports
+// divided into two groups, one for the standard library and one for all others.
+// To get ast.SortImports (called by the formatter) to do that, we must assign
+// file positions to the import specs so that there is a blank line between the
+// two groups. The exact positions don't matter, and they don't have to be
+// distinct within a group; ast.SortImports just looks for a gap of more than
+// one line between specs.
+func synthesizeImportDecl(namedImports map[string]string, blankImports []ast.Spec, tfile *token.File) *ast.GenDecl {
+ importDecl := &ast.GenDecl{
+ Tok: token.IMPORT,
+ Lparen: 1, // Need non-zero Lparen and Rparen so that printer
+ Rparen: 1, // treats this as a factored import.
+ }
+ var stds, others []ast.Spec
+ var stdPos, otherPos token.Pos
+ if tfile.LineCount() >= 3 {
+ stdPos = tfile.LineStart(1)
+ otherPos = tfile.LineStart(3)
+ }
+ for n, p := range namedImports {
+ var (
+ pos token.Pos
+ specs *[]ast.Spec
+ )
+ if !strings.ContainsRune(p, '.') {
+ pos = stdPos
+ specs = &stds
+ } else {
+ pos = otherPos
+ specs = &others
+ }
+ s := &ast.ImportSpec{
+ Path: &ast.BasicLit{Value: strconv.Quote(p), ValuePos: pos},
+ EndPos: pos,
+ }
+ if path.Base(p) != n {
+ s.Name = ast.NewIdent(n)
+ s.Name.NamePos = pos
+ }
+ *specs = append(*specs, s)
+ }
+ importDecl.Specs = append(stds, others...)
+ importDecl.Specs = append(importDecl.Specs, blankImports...)
+
+ return importDecl
+}
+
// playExampleFile takes a whole file example and synthesizes a new *ast.File
// such that the example is function main in package main.
func playExampleFile(file *ast.File) *ast.File {
diff --git a/internal/godoc/internal/doc/example_test.go b/internal/godoc/internal/doc/example_test.go
index 8c1c35e..baccfcd 100644
--- a/internal/godoc/internal/doc/example_test.go
+++ b/internal/godoc/internal/doc/example_test.go
@@ -19,6 +19,7 @@
"strings"
"testing"
+ "github.com/google/go-cmp/cmp"
"golang.org/x/pkgsite/internal/godoc/internal/doc"
)
@@ -42,7 +43,7 @@
}
examples := map[string]*doc.Example{}
unseen := map[string]bool{} // examples we haven't seen yet
- for _, e := range doc.Examples(astFile) {
+ for _, e := range doc.Examples(fset, astFile) {
examples[e.Name] = e
unseen[e.Name] = true
}
@@ -59,8 +60,8 @@
switch kind {
case "Play":
got := strings.TrimSpace(formatFile(t, fset, ex.Play))
- if got != want {
- t.Errorf("%s Play: got\n%s\n---- want ----\n%s", ex.Name, got, want)
+ if diff := cmp.Diff(want, got); diff != "" {
+ t.Errorf("mismatch (-want, +got):\n%s", diff)
}
delete(unseen, name)
case "Output":
diff --git a/internal/godoc/internal/doc/testdata/examples/issue43658.go b/internal/godoc/internal/doc/testdata/examples/issue43658.go
new file mode 100644
index 0000000..ccc1638
--- /dev/null
+++ b/internal/godoc/internal/doc/testdata/examples/issue43658.go
@@ -0,0 +1,221 @@
+// Copyright ©2016 The Gonum Authors. All rights reserved.
+// Copyright 2021 The Go Authors. All rights reserved.
+// (above line required for our license-header checker)
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package community_test
+
+import (
+ "fmt"
+ "log"
+ "sort"
+
+ "golang.org/x/exp/rand"
+
+ "gonum.org/v1/gonum/graph/community"
+ "gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/simple"
+)
+
+func ExampleProfile_simple() {
+ // Profile calls Modularize which implements the Louvain modularization algorithm.
+ // Since this is a randomized algorithm we use a defined random source to ensure
+ // consistency between test runs. In practice, results will not differ greatly
+ // between runs with different PRNG seeds.
+ src := rand.NewSource(1)
+
+ // Create dumbell graph:
+ //
+ // 0 4
+ // |\ /|
+ // | 2 - 3 |
+ // |/ \|
+ // 1 5
+ //
+ g := simple.NewUndirectedGraph()
+ for u, e := range smallDumbell {
+ for v := range e {
+ g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ }
+ }
+
+ // Get the profile of internal node weight for resolutions
+ // between 0.1 and 10 using logarithmic bisection.
+ p, err := community.Profile(
+ community.ModularScore(g, community.Weight, 10, src),
+ true, 1e-3, 0.1, 10,
+ )
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ // Print out each step with communities ordered.
+ for _, d := range p {
+ comm := d.Communities()
+ for _, c := range comm {
+ sort.Sort(ordered.ByID(c))
+ }
+ sort.Sort(ordered.BySliceIDs(comm))
+ fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
+ d.Low, d.High, d.Score, comm, community.Q(g, comm, d.Low))
+ }
+
+ // Output:
+ // Low:0.1 High:0.29 Score:14 Communities:[[0 1 2 3 4 5]] Q=0.9
+ // Low:0.29 High:2.3 Score:12 Communities:[[0 1 2] [3 4 5]] Q=0.714
+ // Low:2.3 High:3.5 Score:4 Communities:[[0 1] [2] [3] [4 5]] Q=-0.31
+ // Low:3.5 High:10 Score:0 Communities:[[0] [1] [2] [3] [4] [5]] Q=-0.607
+}
+
+// intset is an integer set.
+type intset map[int]struct{}
+
+func linksTo(i ...int) intset {
+ if len(i) == 0 {
+ return nil
+ }
+ s := make(intset)
+ for _, v := range i {
+ s[v] = struct{}{}
+ }
+ return s
+}
+
+var smallDumbell = []intset{
+ 0: linksTo(1, 2),
+ 1: linksTo(2),
+ 2: linksTo(3),
+ 3: linksTo(4, 5),
+ 4: linksTo(5),
+ 5: nil,
+}
+
+// http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
+var middleEast = struct{ friends, complicated, enemies []intset }{
+ // green cells
+ friends: []intset{
+ 0: nil,
+ 1: linksTo(5, 7, 9, 12),
+ 2: linksTo(11),
+ 3: linksTo(4, 5, 10),
+ 4: linksTo(3, 5, 10),
+ 5: linksTo(1, 3, 4, 8, 10, 12),
+ 6: nil,
+ 7: linksTo(1, 12),
+ 8: linksTo(5, 9, 11),
+ 9: linksTo(1, 8, 12),
+ 10: linksTo(3, 4, 5),
+ 11: linksTo(2, 8),
+ 12: linksTo(1, 5, 7, 9),
+ },
+
+ // yellow cells
+ complicated: []intset{
+ 0: linksTo(2, 4),
+ 1: linksTo(4, 8),
+ 2: linksTo(0, 3, 4, 5, 8, 9),
+ 3: linksTo(2, 8, 11),
+ 4: linksTo(0, 1, 2, 8),
+ 5: linksTo(2),
+ 6: nil,
+ 7: linksTo(9, 11),
+ 8: linksTo(1, 2, 3, 4, 10, 12),
+ 9: linksTo(2, 7, 11),
+ 10: linksTo(8),
+ 11: linksTo(3, 7, 9, 12),
+ 12: linksTo(8, 11),
+ },
+
+ // red cells
+ enemies: []intset{
+ 0: linksTo(1, 3, 5, 6, 7, 8, 9, 10, 11, 12),
+ 1: linksTo(0, 2, 3, 6, 10, 11),
+ 2: linksTo(1, 6, 7, 10, 12),
+ 3: linksTo(0, 1, 6, 7, 9, 12),
+ 4: linksTo(6, 7, 9, 11, 12),
+ 5: linksTo(0, 6, 7, 9, 11),
+ 6: linksTo(0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12),
+ 7: linksTo(0, 2, 3, 4, 5, 6, 8, 10),
+ 8: linksTo(0, 6, 7),
+ 9: linksTo(0, 3, 4, 5, 6, 10),
+ 10: linksTo(0, 1, 2, 6, 7, 9, 11, 12),
+ 11: linksTo(0, 1, 4, 5, 6, 10),
+ 12: linksTo(0, 2, 3, 4, 6, 10),
+ },
+}
+
+var friends, enemies *simple.WeightedUndirectedGraph
+
+func init() {
+ friends = simple.NewWeightedUndirectedGraph(0, 0)
+ for u, e := range middleEast.friends {
+ // Ensure unconnected nodes are included.
+ if friends.Node(int64(u)) == nil {
+ friends.AddNode(simple.Node(u))
+ }
+ for v := range e {
+ friends.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(u), T: simple.Node(v), W: 1})
+ }
+ }
+ enemies = simple.NewWeightedUndirectedGraph(0, 0)
+ for u, e := range middleEast.enemies {
+ // Ensure unconnected nodes are included.
+ if enemies.Node(int64(u)) == nil {
+ enemies.AddNode(simple.Node(u))
+ }
+ for v := range e {
+ enemies.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(u), T: simple.Node(v), W: -1})
+ }
+ }
+}
+
+func ExampleProfile_multiplex() {
+ // Profile calls ModularizeMultiplex which implements the Louvain modularization
+ // algorithm. Since this is a randomized algorithm we use a defined random source
+ // to ensure consistency between test runs. In practice, results will not differ
+ // greatly between runs with different PRNG seeds.
+ src := rand.NewSource(1)
+
+ // The undirected graphs, friends and enemies, are the political relationships
+ // in the Middle East as described in the Slate article:
+ // http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
+ g, err := community.NewUndirectedLayers(friends, enemies)
+ if err != nil {
+ log.Fatal(err)
+ }
+ weights := []float64{1, -1}
+
+ // Get the profile of internal node weight for resolutions
+ // between 0.1 and 10 using logarithmic bisection.
+ p, err := community.Profile(
+ community.ModularMultiplexScore(g, weights, true, community.WeightMultiplex, 10, src),
+ true, 1e-3, 0.1, 10,
+ )
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ // Print out each step with communities ordered.
+ for _, d := range p {
+ comm := d.Communities()
+ for _, c := range comm {
+ sort.Sort(ordered.ByID(c))
+ }
+ sort.Sort(ordered.BySliceIDs(comm))
+ fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
+ d.Low, d.High, d.Score, comm, community.QMultiplex(g, comm, weights, []float64{d.Low}))
+ }
+
+ // Output:
+ // Low:0.1 High:0.72 Score:26 Communities:[[0] [1 7 9 12] [2 8 11] [3 4 5 10] [6]] Q=[24.7 1.97]
+ // Low:0.72 High:1.1 Score:24 Communities:[[0 6] [1 7 9 12] [2 8 11] [3 4 5 10]] Q=[16.9 14.1]
+ // Low:1.1 High:1.2 Score:18 Communities:[[0 2 6 11] [1 7 9 12] [3 4 5 8 10]] Q=[9.16 25.1]
+ // Low:1.2 High:1.6 Score:10 Communities:[[0 3 4 5 6 10] [1 7 9 12] [2 8 11]] Q=[10.5 26.7]
+ // Low:1.6 High:1.6 Score:8 Communities:[[0 1 6 7 9 12] [2 8 11] [3 4 5 10]] Q=[5.56 39.8]
+ // Low:1.6 High:1.8 Score:2 Communities:[[0 2 3 4 5 6 10] [1 7 8 9 11 12]] Q=[-1.82 48.6]
+ // Low:1.8 High:2.3 Score:-6 Communities:[[0 2 3 4 5 6 8 10 11] [1 7 9 12]] Q=[-5 57.5]
+ // Low:2.3 High:2.4 Score:-10 Communities:[[0 1 2 6 7 8 9 11 12] [3 4 5 10]] Q=[-11.2 79]
+ // Low:2.4 High:4.3 Score:-52 Communities:[[0 1 2 3 4 5 6 7 8 9 10 11 12]] Q=[-46.1 117]
+ // Low:4.3 High:10 Score:-54 Communities:[[0 1 2 3 4 6 7 8 9 10 11 12] [5]] Q=[-82 254]
+}
diff --git a/internal/godoc/internal/doc/testdata/examples/issue43658.golden b/internal/godoc/internal/doc/testdata/examples/issue43658.golden
new file mode 100644
index 0000000..992d025
--- /dev/null
+++ b/internal/godoc/internal/doc/testdata/examples/issue43658.golden
@@ -0,0 +1,135 @@
+---------------- Profile_simple.Play
+package main
+
+import (
+ "fmt"
+ "log"
+ "sort"
+
+ "golang.org/x/exp/rand"
+ "gonum.org/v1/gonum/graph/community"
+ "gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/simple"
+)
+
+func main() {
+ // Profile calls Modularize which implements the Louvain modularization algorithm.
+ // Since this is a randomized algorithm we use a defined random source to ensure
+ // consistency between test runs. In practice, results will not differ greatly
+ // between runs with different PRNG seeds.
+ src := rand.NewSource(1)
+
+ // Create dumbell graph:
+ //
+ // 0 4
+ // |\ /|
+ // | 2 - 3 |
+ // |/ \|
+ // 1 5
+ //
+ g := simple.NewUndirectedGraph()
+ for u, e := range smallDumbell {
+ for v := range e {
+ g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ }
+ }
+
+ // Get the profile of internal node weight for resolutions
+ // between 0.1 and 10 using logarithmic bisection.
+ p, err := community.Profile(
+ community.ModularScore(g, community.Weight, 10, src),
+ true, 1e-3, 0.1, 10,
+ )
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ // Print out each step with communities ordered.
+ for _, d := range p {
+ comm := d.Communities()
+ for _, c := range comm {
+ sort.Sort(ordered.ByID(c))
+ }
+ sort.Sort(ordered.BySliceIDs(comm))
+ fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
+ d.Low, d.High, d.Score, comm, community.Q(g, comm, d.Low))
+ }
+
+}
+
+// intset is an integer set.
+type intset map[int]struct{}
+
+func linksTo(i ...int) intset {
+ if len(i) == 0 {
+ return nil
+ }
+ s := make(intset)
+ for _, v := range i {
+ s[v] = struct{}{}
+ }
+ return s
+}
+
+var smallDumbell = []intset{
+ 0: linksTo(1, 2),
+ 1: linksTo(2),
+ 2: linksTo(3),
+ 3: linksTo(4, 5),
+ 4: linksTo(5),
+ 5: nil,
+}
+---------------- Profile_multiplex.Play
+package main
+
+import (
+ "fmt"
+ "log"
+ "sort"
+
+ "golang.org/x/exp/rand"
+ "gonum.org/v1/gonum/graph/community"
+ "gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/simple"
+)
+
+var friends, enemies *simple.WeightedUndirectedGraph
+
+func main() {
+ // Profile calls ModularizeMultiplex which implements the Louvain modularization
+ // algorithm. Since this is a randomized algorithm we use a defined random source
+ // to ensure consistency between test runs. In practice, results will not differ
+ // greatly between runs with different PRNG seeds.
+ src := rand.NewSource(1)
+
+ // The undirected graphs, friends and enemies, are the political relationships
+ // in the Middle East as described in the Slate article:
+ // http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
+ g, err := community.NewUndirectedLayers(friends, enemies)
+ if err != nil {
+ log.Fatal(err)
+ }
+ weights := []float64{1, -1}
+
+ // Get the profile of internal node weight for resolutions
+ // between 0.1 and 10 using logarithmic bisection.
+ p, err := community.Profile(
+ community.ModularMultiplexScore(g, weights, true, community.WeightMultiplex, 10, src),
+ true, 1e-3, 0.1, 10,
+ )
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ // Print out each step with communities ordered.
+ for _, d := range p {
+ comm := d.Communities()
+ for _, c := range comm {
+ sort.Sort(ordered.ByID(c))
+ }
+ sort.Sort(ordered.BySliceIDs(comm))
+ fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
+ d.Low, d.High, d.Score, comm, community.QMultiplex(g, comm, weights, []float64{d.Low}))
+ }
+
+}