Add support for sub-indexes (#120)

<details>
<summary>Background</summary>

Sally renders two kinds of pages:

- packages: These are for packages defined in sally.yaml
  and any route under the package path.
- indexes: These list available packages.

The latter--indexes was previously only supported at '/', the root page.

This leads to a slight UX issue:
if you have a package with a / in its name (e.g. net/metrics):

- example.com/net/metrics gives you the package page
- example.com/ lists net/metrics
- However, example.com/net fails with a 404

</details>

This adds support for index pages on all parents of package pages.
Therefore, if example.com/net/metrics exists,
example.com/net will list all packages defined under that path.

Resolves #31

9 files changed, 288 insertions, 84 deletions

diff --git a/.github/workflows/go.yml b/.github/workflows/go.yml
index a04b4ab..9c644e1 100644
--- a/.github/workflows/go.yml
+++ b/.github/workflows/go.yml
@@ -20,7 +20,7 @@ jobs:
     - name: Setup Go
       uses: actions/setup-go@v4
       with:
-        go-version: 1.20.x
+        go-version: 1.21.x
         cache: true
 
     - name: Lint
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1f67c60..eb44942 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4,6 +4,11 @@ All notable changes to this project will be documented in this file.
 The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
 and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
 
+## Unreleased
+### Added
+- Generate a package listing for sub-paths
+  that match a subset of the known packages.
+
 ## [1.4.0]
 ### Added
 - Publish a Docker image to GitHub Container Registry.
diff --git a/Dockerfile b/Dockerfile
index d6033ac..9fb023c 100644
--- a/Dockerfile
+++ b/Dockerfile
@@ -2,7 +2,7 @@
 # It does not include a sally configuration.
 # A /sally.yaml file is required for this to run.
 
-FROM golang:1.19-alpine
+FROM golang:1.21-alpine
 
 COPY . /build
 WORKDIR /build
diff --git a/go.mod b/go.mod
index ee31bf0..91027f4 100644
--- a/go.mod
+++ b/go.mod
@@ -1,6 +1,8 @@
 module go.uber.org/sally
 
-go 1.18
+go 1.21
+
+toolchain go1.21.3
 
 require (
 	github.com/stretchr/testify v1.8.4
diff --git a/handler.go b/handler.go
index 18dd1f4..f636359 100644
--- a/handler.go
+++ b/handler.go
@@ -1,10 +1,12 @@
 package main
 
 import (
+	"cmp"
 	"fmt"
 	"html/template"
 	"net/http"
-	"sort"
+	"path"
+	"slices"
 	"strings"
 
 	"go.uber.org/sally/templates"
@@ -17,112 +19,168 @@ var (
 		template.New("package.html").Parse(templates.Package))
 )
 
-// CreateHandler creates a Sally http.Handler
+// CreateHandler builds a new handler
+// with the provided package configuration.
+// The returned handler provides the following endpoints:
+//
+//	GET /
+//		Index page listing all packages.
+//	GET /<name>
+//	       Package page for the given package.
+//	GET /<dir>
+//		Page listing packages under the given directory,
+//		assuming that there's no package with the given name.
+//	GET /<name>/<subpkg>
+//		Package page for the given subpackage.
 func CreateHandler(config *Config) http.Handler {
 	mux := http.NewServeMux()
-
-	pkgs := make([]packageInfo, 0, len(config.Packages))
+	pkgs := make([]*sallyPackage, 0, len(config.Packages))
 	for name, pkg := range config.Packages {
-		handler := newPackageHandler(config, name, pkg)
+		baseURL := config.URL
+		if pkg.URL != "" {
+			// Package-specific override for the base URL.
+			baseURL = pkg.URL
+		}
+		modulePath := path.Join(baseURL, name)
+		docURL := "https://" + path.Join(config.Godoc.Host, modulePath)
+
+		pkg := &sallyPackage{
+			Name:       name,
+			Desc:       pkg.Desc,
+			ModulePath: modulePath,
+			DocURL:     docURL,
+			GitURL:     pkg.Repo,
+		}
+		pkgs = append(pkgs, pkg)
+
 		// Double-register so that "/foo"
 		// does not redirect to "/foo/" with a 300.
+		handler := &packageHandler{Pkg: pkg}
 		mux.Handle("/"+name, handler)
 		mux.Handle("/"+name+"/", handler)
-
-		pkgs = append(pkgs, packageInfo{
-			Desc:       pkg.Desc,
-			ImportPath: handler.canonicalURL,
-			GitURL:     handler.gitURL,
-			GodocHome:  handler.godocHost + "/" + handler.canonicalURL,
-		})
 	}
-	sort.Slice(pkgs, func(i, j int) bool {
-		return pkgs[i].ImportPath < pkgs[j].ImportPath
+
+	mux.Handle("/", newIndexHandler(pkgs))
+	return requireMethod(http.MethodGet, mux)
+}
+
+func requireMethod(method string, handler http.Handler) http.Handler {
+	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
+		if r.Method != method {
+			http.NotFound(w, r)
+			return
+		}
+
+		handler.ServeHTTP(w, r)
 	})
-	mux.Handle("/", &indexHandler{pkgs: pkgs})
+}
 
-	return mux
+type sallyPackage struct {
+	// Name of the package.
+	//
+	// This is the part after the base URL.
+	Name string
+
+	// Canonical import path for the package.
+	ModulePath string
+
+	// Description of the package, if any.
+	Desc string
+
+	// URL at which documentation for the package can be found.
+	DocURL string
+
+	// URL at which the Git repository is hosted.
+	GitURL string
 }
 
 type indexHandler struct {
-	pkgs []packageInfo
+	pkgs []*sallyPackage // sorted by name
 }
 
-type packageInfo struct {
-	Desc       string // package description
-	ImportPath string // canonical import path
-	GitURL     string // URL of the Git repository
-	GodocHome  string // documentation home URL
-}
+var _ http.Handler = (*indexHandler)(nil)
 
-func (h *indexHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
-	// Index handler only supports '/'.
-	// ServeMux will call us for any '/foo' that is not a known package.
-	if r.Method != http.MethodGet || r.URL.Path != "/" {
-		http.NotFound(w, r)
-		return
-	}
+func newIndexHandler(pkgs []*sallyPackage) *indexHandler {
+	slices.SortFunc(pkgs, func(a, b *sallyPackage) int {
+		return cmp.Compare(a.Name, b.Name)
+	})
 
-	data := struct{ Packages []packageInfo }{
-		Packages: h.pkgs,
-	}
-	if err := indexTemplate.Execute(w, data); err != nil {
-		http.Error(w, err.Error(), 500)
+	return &indexHandler{
+		pkgs: pkgs,
 	}
 }
 
-type packageHandler struct {
-	// Hostname of the godoc server, e.g. "godoc.org".
-	godocHost string
+func (h *indexHandler) rangeOf(path string) (start, end int) {
+	if len(path) == 0 {
+		return 0, len(h.pkgs)
+	}
 
-	// Name of the package relative to the vanity base URL.
-	// For example, "zap" for "go.uber.org/zap".
-	name string
+	// If the packages are sorted by name,
+	// we can scan adjacent packages to find the range of packages
+	// whose name descends from path.
+	start, _ = slices.BinarySearchFunc(h.pkgs, path, func(pkg *sallyPackage, path string) int {
+		return cmp.Compare(pkg.Name, path)
+	})
 
-	// Path at which the Git repository is hosted.
-	// For example, "github.com/uber-go/zap".
-	gitURL string
+	for idx := start; idx < len(h.pkgs); idx++ {
+		if !descends(path, h.pkgs[idx].Name) {
+			// End of matching sequences.
+			// The next path is not a descendant of path.
+			return start, idx
+		}
+	}
 
-	// Canonical import path for the package.
-	canonicalURL string
+	// All packages following start are descendants of path.
+	// Return the rest of the packages.
+	return start, len(h.pkgs)
 }
 
-func newPackageHandler(cfg *Config, name string, pkg PackageConfig) *packageHandler {
-	baseURL := cfg.URL
-	if pkg.URL != "" {
-		baseURL = pkg.URL
+func (h *indexHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
+	path := strings.TrimPrefix(strings.TrimSuffix(r.URL.Path, "/"), "/")
+	start, end := h.rangeOf(path)
+
+	// If start == end, then there are no packages
+	if start == end {
+		w.WriteHeader(http.StatusNotFound)
+		fmt.Fprintf(w, "no packages found under path: %v\n", path)
+		return
 	}
-	canonicalURL := fmt.Sprintf("%s/%s", baseURL, name)
 
-	return &packageHandler{
-		godocHost:    cfg.Godoc.Host,
-		name:         name,
-		canonicalURL: canonicalURL,
-		gitURL:       pkg.Repo,
+	err := indexTemplate.Execute(w,
+		struct{ Packages []*sallyPackage }{
+			Packages: h.pkgs[start:end],
+		})
+	if err != nil {
+		http.Error(w, err.Error(), 500)
 	}
 }
 
-func (h *packageHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
-	if r.Method != http.MethodGet {
-		http.NotFound(w, r)
-		return
-	}
+type packageHandler struct {
+	Pkg *sallyPackage
+}
+
+var _ http.Handler = (*packageHandler)(nil)
 
+func (h *packageHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
 	// Extract the relative path to subpackages, if any.
-	//	"/foo/bar" => "/bar"
-	//	"/foo" => ""
-	relPath := strings.TrimPrefix(r.URL.Path, "/"+h.name)
-
-	data := struct {
-		Repo         string
-		CanonicalURL string
-		GodocURL     string
+	//      "/foo/bar" => "/bar"
+	//      "/foo" => ""
+	relPath := strings.TrimPrefix(r.URL.Path, "/"+h.Pkg.Name)
+
+	err := packageTemplate.Execute(w, struct {
+		ModulePath string
+		GitURL     string
+		DocURL     string
 	}{
-		Repo:         h.gitURL,
-		CanonicalURL: h.canonicalURL,
-		GodocURL:     fmt.Sprintf("https://%s/%s%s", h.godocHost, h.canonicalURL, relPath),
-	}
-	if err := packageTemplate.Execute(w, data); err != nil {
+		ModulePath: h.Pkg.ModulePath,
+		GitURL:     h.Pkg.GitURL,
+		DocURL:     h.Pkg.DocURL + relPath,
+	})
+	if err != nil {
 		http.Error(w, err.Error(), 500)
 	}
 }
+
+func descends(from, to string) bool {
+	return to == from || (strings.HasPrefix(to, from) && to[len(from)] == '/')
+}
diff --git a/handler_test.go b/handler_test.go
index 370eb45..e910897 100644
--- a/handler_test.go
+++ b/handler_test.go
@@ -23,6 +23,10 @@ packages:
     url: go.uberalt.org
     repo: github.com/uber-go/zap
     description: A fast, structured logging library.
+  net/metrics:
+    repo: github.com/yarpc/metrics
+  net/something:
+    repo: github.com/yarpc/something
 
 `
 
@@ -34,6 +38,19 @@ func TestIndex(t *testing.T) {
 	assert.Contains(t, body, "github.com/thriftrw/thriftrw-go")
 	assert.Contains(t, body, "github.com/yarpc/yarpc-go")
 	assert.Contains(t, body, "A fast, structured logging library.")
+	assert.Contains(t, body, "github.com/yarpc/metrics")
+	assert.Contains(t, body, "github.com/yarpc/something")
+}
+
+func TestSubindex(t *testing.T) {
+	rr := CallAndRecord(t, config, "/net")
+	assert.Equal(t, 200, rr.Code)
+
+	body := rr.Body.String()
+	assert.NotContains(t, body, "github.com/thriftrw/thriftrw-go")
+	assert.NotContains(t, body, "github.com/yarpc/yarpc-go")
+	assert.Contains(t, body, "github.com/yarpc/metrics")
+	assert.Contains(t, body, "github.com/yarpc/something")
 }
 
 func TestPackageShouldExist(t *testing.T) {
@@ -55,7 +72,7 @@ func TestPackageShouldExist(t *testing.T) {
 func TestNonExistentPackageShould404(t *testing.T) {
 	rr := CallAndRecord(t, config, "/nonexistent")
 	AssertResponse(t, rr, 404, `
-404 page not found
+no packages found under path: nonexistent
 `)
 }
 
@@ -161,3 +178,123 @@ func TestPostRejected(t *testing.T) {
 		})
 	}
 }
+
+func TestIndexHandler_rangeOf(t *testing.T) {
+	tests := []struct {
+		desc string
+		pkgs []*sallyPackage
+		path string
+		want []string // names
+	}{
+		{
+			desc: "empty",
+			pkgs: []*sallyPackage{
+				{Name: "foo"},
+				{Name: "bar"},
+			},
+			want: []string{"foo", "bar"},
+		},
+		{
+			desc: "single child",
+			pkgs: []*sallyPackage{
+				{Name: "foo/bar"},
+				{Name: "baz"},
+			},
+			path: "foo",
+			want: []string{"foo/bar"},
+		},
+		{
+			desc: "multiple children",
+			pkgs: []*sallyPackage{
+				{Name: "foo/bar"},
+				{Name: "foo/baz"},
+				{Name: "qux"},
+				{Name: "quux/quuz"},
+			},
+			path: "foo",
+			want: []string{"foo/bar", "foo/baz"},
+		},
+		{
+			desc: "to end of list",
+			pkgs: []*sallyPackage{
+				{Name: "a"},
+				{Name: "b"},
+				{Name: "c/d"},
+				{Name: "c/e"},
+			},
+			path: "c",
+			want: []string{"c/d", "c/e"},
+		},
+		{
+			desc: "similar name",
+			pkgs: []*sallyPackage{
+				{Name: "foobar"},
+				{Name: "foo/bar"},
+			},
+			path: "foo",
+			want: []string{"foo/bar"},
+		},
+		{
+			desc: "no match",
+			pkgs: []*sallyPackage{
+				{Name: "foo"},
+				{Name: "bar"},
+			},
+			path: "baz",
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.desc, func(t *testing.T) {
+			h := newIndexHandler(tt.pkgs)
+			start, end := h.rangeOf(tt.path)
+
+			var got []string
+			for _, pkg := range tt.pkgs[start:end] {
+				got = append(got, pkg.Name)
+			}
+			assert.ElementsMatch(t, tt.want, got)
+		})
+	}
+}
+
+func BenchmarkHandlerDispatch(b *testing.B) {
+	handler := CreateHandler(&Config{
+		URL: "go.uberalt.org",
+		Packages: map[string]PackageConfig{
+			"zap": {
+				Repo: "github.com/uber-go/zap",
+			},
+			"net/metrics": {
+				Repo: "github.com/yarpc/metrics",
+			},
+		},
+	})
+	resw := new(nopResponseWriter)
+
+	tests := []struct {
+		name string
+		path string
+	}{
+		{name: "index", path: "/"},
+		{name: "subindex", path: "/net"},
+		{name: "package", path: "/zap"},
+		{name: "subpackage", path: "/zap/zapcore"},
+	}
+
+	for _, tt := range tests {
+		b.Run(tt.name, func(b *testing.B) {
+			req := httptest.NewRequest("GET", tt.path, nil)
+			b.ResetTimer()
+			for i := 0; i < b.N; i++ {
+				handler.ServeHTTP(resw, req)
+			}
+		})
+	}
+}
+
+type nopResponseWriter struct{}
+
+func (nopResponseWriter) Header() http.Header       { return nil }
+func (nopResponseWriter) Write([]byte) (int, error) { return 0, nil }
+func (nopResponseWriter) WriteHeader(int)           {}
diff --git a/sally.yaml b/sally.yaml
index c9a3af8..3055d87 100644
--- a/sally.yaml
+++ b/sally.yaml
@@ -6,3 +6,5 @@ packages:
     description: A customizable implementation of Thrift.
   yarpc:
     repo: github.com/yarpc/yarpc-go
+  net/metrics:
+    repo: github.com/yarpc/metrics
diff --git a/templates/index.html b/templates/index.html
index fa061f1..7ffc1a6 100644
--- a/templates/index.html
+++ b/templates/index.html
@@ -29,15 +29,15 @@
                 <div class="row">
                     <div class="five columns">
                         <span class="inline-header">Package:</span>
-                        {{ .ImportPath }}
+                        {{ .ModulePath }}
                     </div>
                     <div class="five columns">
                         <span class="inline-header">Source:</span>
                         <a href="//{{ .GitURL }}">{{ .GitURL }}</a>
                     </div>
                     <div class="two columns">
-                        <a href="//{{ .GodocHome }}">
-                            <img src="//pkg.go.dev/badge/{{ .ImportPath }}.svg" alt="Go Reference" />
+                        <a href="//{{ .DocURL }}">
+                            <img src="//pkg.go.dev/badge/{{ .ModulePath }}.svg" alt="Go Reference" />
                         </a>
                     </div>
                 </div>
diff --git a/templates/package.html b/templates/package.html
index a85ff77..bd56c38 100644
--- a/templates/package.html
+++ b/templates/package.html
@@ -1,10 +1,10 @@
 <!DOCTYPE html>
 <html>
     <head>
-        <meta name="go-import" content="{{ .CanonicalURL }} git https://{{ .Repo }}">
-        <meta http-equiv="refresh" content="0; url={{ .GodocURL }}">
+        <meta name="go-import" content="{{ .ModulePath }} git https://{{ .GitURL }}">
+        <meta http-equiv="refresh" content="0; url={{ .DocURL }}">
     </head>
     <body>
-        Nothing to see here. Please <a href="{{ .GodocURL }}">move along</a>.
+        Nothing to see here. Please <a href="{{ .DocURL }}">move along</a>.
     </body>
 </html>