use grouping instead of colors to show non-global search hits:

- introduced a new run per file containing all spots belonging
  to the same kind (e.g. var decl, const decl, etc.)
- more comments, better index.go file organization

R=rsc
http://go/go-review/1026028

4 files changed, 143 insertions, 134 deletions

diff --git a/doc/style.css b/doc/style.css
index 629509b2ac..85cdbd247c 100644
--- a/doc/style.css
+++ b/doc/style.css
@@ -181,6 +181,11 @@ a.noline {
   text-decoration: none;
 }
 
+a.info {
+  text-decoration: none;
+  background-color: #D8D8D8;
+}
+
 table.layout {
   border-width: 0px;
   border-spacing: 0px;
@@ -197,50 +202,6 @@ span.highlight {
 
 
 /* ------------------------------------------------------------------------- */
-/* Styles used by infoClassFmt */
-
-a.package {
-  text-decoration: none;
-  background-color: #FFFFFF;
-}
-
-a.import {
-  text-decoration: none;
-  background-color: #D8D8D8;
-}
-
-a.const {
-  text-decoration: none;
-  background-color: #F5A9A9;
-}
-
-a.type {
-  text-decoration: none;
-  background-color: #F2F5A9;
-}
-
-a.var {
-  text-decoration: none;
-  background-color: #A9F5A9;
-}
-
-a.func {
-  text-decoration: none;
-  background-color: #A9D0F5;
-}
-
-a.method {
-  text-decoration: none;
-  background-color: #D0A9F5;
-}
-
-a.use {
-  text-decoration: none;
-  color: #FFFFFF;
-  background-color: #5858FA;
-}
-
-/* ------------------------------------------------------------------------- */
 /* Styles for the frontpage */
 
 #gettingStarted {
diff --git a/lib/godoc/search.html b/lib/godoc/search.html
index 8dc32b8434..927910f656 100644
--- a/lib/godoc/search.html
+++ b/lib/godoc/search.html
@@ -24,37 +24,36 @@
 		{.repeated section @}
 			<h3>package {Pak.Name|html}</h3>
 			{.repeated section Files}
-				{.repeated section Infos}
-					<a href="{File.Path|html}?h={Query|html}#L{@|infoLine}" class="noline">{File.Path|html}:{@|infoLine}</a>
-					<pre>{@|infoSnippet}</pre>
+				{.repeated section Groups}
+					{.repeated section Infos}
+						<a href="{File.Path|html}?h={Query|html}#L{@|infoLine}" class="noline">{File.Path|html}:{@|infoLine}</a>
+						<pre>{@|infoSnippet}</pre>
+					{.end}
 				{.end}
 			{.end}
 		{.end}
 	{.end}
 	{.section Others}
 		<h2>Local declarations and uses</h2>
-		<p>
-		Legend:
-		{.repeated section Legend}
-			<a class="{@|html}">{@|html}</a>
-		{.end}
-		</p>
 		{.repeated section @}
 			<h3>package {Pak.Name|html}</h3>
-			<table border="0" cellspacing="2">
 			{.repeated section Files}
-				<tr>
-				<td valign="top">
-					<a href="{File.Path|html}?h={Query|html}" class="noline">{File.Path|html}:</a>
-				</td>
-				<td>
-				{.repeated section Infos}
-					<a href="{File.Path|html}?h={Query|html}#L{@|infoLine}" class="{@|infoClass}">{@|infoLine}</a>
+				<a href="{File.Path|html}?h={Query|html}" class="noline">{File.Path|html}</a>
+				<table class="layout">
+				{.repeated section Groups}
+					<tr>
+					<td width="25"></td>
+					<th align="left" valign="top">{Kind|infoKind}</th>
+					<td align="left" width="4"></td>
+					<td>
+					{.repeated section Infos}
+						<a href="{File.Path|html}?h={Query|html}#L{@|infoLine}" class="info">{@|infoLine}</a>
+					{.end}
+					</td>
+					</tr>
 				{.end}
-				</td>
-				</tr>
+				</table>
 			{.end}
-			</table>
 		{.end}
 	{.end}
 {.or}
diff --git a/src/cmd/godoc/godoc.go b/src/cmd/godoc/godoc.go
index 30f92b674e..a4bc07f3c4 100644
--- a/src/cmd/godoc/godoc.go
+++ b/src/cmd/godoc/godoc.go
@@ -595,22 +595,22 @@ func linkFmt(w io.Writer, x interface{}, format string) {
 }
 
 
-// The strings in infoClasses must be properly html-escaped.
-var infoClasses = [nKinds]string{
-	"package",	// PackageClause
-	"import",	// ImportDecl
-	"const",	// ConstDecl
-	"type",	// TypeDecl
-	"var",	// VarDecl
-	"func",	// FuncDecl
-	"method",	// MethodDecl
-	"use",	// Use
+// The strings in infoKinds must be properly html-escaped.
+var infoKinds = [nKinds]string{
+	PackageClause: "package&nbsp;clause",
+	ImportDecl: "import&nbsp;decl",
+	ConstDecl: "const&nbsp;decl",
+	TypeDecl: "type&nbsp;decl",
+	VarDecl: "var&nbsp;decl",
+	FuncDecl: "func&nbsp;decl",
+	MethodDecl: "method&nbsp;decl",
+	Use: "use",
 }
 
 
-// Template formatter for "infoClass" format.
-func infoClassFmt(w io.Writer, x interface{}, format string) {
-	fmt.Fprintf(w, infoClasses[x.(SpotInfo).Kind()]);	// no html escaping needed
+// Template formatter for "infoKind" format.
+func infoKindFmt(w io.Writer, x interface{}, format string) {
+	fmt.Fprintf(w, infoKinds[x.(SpotKind)]);	// infoKind entries are html-escaped
 }
 
 
@@ -661,7 +661,7 @@ var fmap = template.FormatterMap{
 	"html-comment": htmlCommentFmt,
 	"path": pathFmt,
 	"link": linkFmt,
-	"infoClass": infoClassFmt,
+	"infoKind": infoKindFmt,
 	"infoLine": infoLineFmt,
 	"infoSnippet": infoSnippetFmt,
 	"padding": paddingFmt,
@@ -1071,7 +1071,6 @@ type SearchResult struct {
 	Hit		*LookupResult;
 	Alt		*AltWords;
 	Accurate	bool;
-	Legend		[]string;
 }
 
 func search(c *http.Conn, r *http.Request) {
@@ -1083,7 +1082,6 @@ func search(c *http.Conn, r *http.Request) {
 		result.Hit, result.Alt = index.(*Index).Lookup(query);
 		_, ts := fsTree.get();
 		result.Accurate = timestamp >= ts;
-		result.Legend = &infoClasses;
 	}
 
 	var buf bytes.Buffer;
diff --git a/src/cmd/godoc/index.go b/src/cmd/godoc/index.go
index 47da833966..00c8cf2c73 100644
--- a/src/cmd/godoc/index.go
+++ b/src/cmd/godoc/index.go
@@ -37,7 +37,7 @@ import (
 
 
 // ----------------------------------------------------------------------------
-// Data structures used during indexing
+// RunList
 
 // A RunList is a vector of entries that can be sorted according to some
 // criteria. A RunList may be compressed by grouping "runs" of entries
@@ -83,6 +83,9 @@ func (h *RunList) reduce(less func(x, y interface{}) bool, newRun func(h *RunLis
 }
 
 
+// ----------------------------------------------------------------------------
+// SpotInfo
+
 // A SpotInfo value describes a particular identifier spot in a given file;
 // It encodes three values: the SpotKind (declaration or use), a line or
 // snippet index "lori", and whether it's a line or index.
@@ -140,25 +143,80 @@ func makeSpotInfo(kind SpotKind, lori int, isIndex bool) SpotInfo {
 }
 
 
-func (x SpotInfo) less(y SpotInfo) bool	{ return x.Lori() < y.Lori() }
+func (x SpotInfo) Kind() SpotKind	{ return SpotKind(x>>1&7) }
+func (x SpotInfo) Lori() int		{ return int(x>>4) }
+func (x SpotInfo) IsIndex() bool	{ return x&1 != 0 }
+
+
+// ----------------------------------------------------------------------------
+// KindRun
 
+// Debugging support. Disable to see multiple entries per line.
+const removeDuplicates = true
 
-func (x SpotInfo) Kind() SpotKind	{ return SpotKind(x>>1&7) }
+// A KindRun is a run of SpotInfos of the same kind in a given file.
+type KindRun struct {
+	Kind	SpotKind;
+	Infos	[]SpotInfo;
+}
 
 
-func (x SpotInfo) Lori() int	{ return int(x>>4) }
+// KindRuns are sorted by line number or index. Since the isIndex bit
+// is always the same for all infos in one list we can compare lori's.
+func (f *KindRun) Len() int		{ return len(f.Infos) }
+func (f *KindRun) Less(i, j int) bool	{ return f.Infos[i].Lori() < f.Infos[j].Lori() }
+func (f *KindRun) Swap(i, j int)	{ f.Infos[i], f.Infos[j] = f.Infos[j], f.Infos[i] }
 
 
-func (x SpotInfo) IsIndex() bool	{ return x&1 != 0 }
+// FileRun contents are sorted by Kind for the reduction into KindRuns.
+func lessKind(x, y interface{}) bool	{ return x.(SpotInfo).Kind() < y.(SpotInfo).Kind() }
 
 
+// newKindRun allocates a new KindRun from the SpotInfo run [i, j) in h.
+func newKindRun(h *RunList, i, j int) interface{} {
+	kind := h.At(i).(SpotInfo).Kind();
+	infos := make([]SpotInfo, j-i);
+	k := 0;
+	for ; i < j; i++ {
+		infos[k] = h.At(i).(SpotInfo);
+		k++;
+	}
+	run := &KindRun{kind, infos};
+
+	// Spots were sorted by file and kind to create this run.
+	// Within this run, sort them by line number or index.
+	sort.Sort(run);
+
+	if removeDuplicates {
+		// Since both the lori and kind field must be
+		// same for duplicates, and since the isIndex
+		// bit is always the same for all infos in one
+		// list we can simply compare the entire info.
+		k := 0;
+		var prev SpotInfo;
+		for i, x := range infos {
+			if x != prev || i == 0 {
+				infos[k] = x;
+				k++;
+				prev = x;
+			}
+		}
+		run.Infos = infos[0:k];
+	}
+
+	return run;
+}
+
+
+// ----------------------------------------------------------------------------
+// FileRun
+
 // A Pak describes a Go package.
 type Pak struct {
-	Path	string;	// directory name containing the package
+	Path	string;	// path of directory containing the package
 	Name	string;	// package name as declared by package clause
 }
 
-
 // Paks are sorted by name (primary key) and by import path (secondary key).
 func (p *Pak) less(q *Pak) bool {
 	return p.Name < q.Name || p.Name == q.Name && p.Path < q.Path;
@@ -172,9 +230,6 @@ type File struct {
 }
 
 
-func (f *File) less(g *File) bool	{ return f.Path < g.Path }
-
-
 // A Spot describes a single occurence of a word.
 type Spot struct {
 	File	*File;
@@ -182,59 +237,42 @@ type Spot struct {
 }
 
 
-// Spots are sorted by filename.
-func lessSpot(x, y interface{}) bool	{ return x.(Spot).File.less(y.(Spot).File) }
-
-
-// A FileRun describes a run of Spots of a word in a single file.
+// A FileRun is a list of KindRuns belonging to the same file.
 type FileRun struct {
 	File	*File;
-	Infos	[]SpotInfo;
+	Groups	[]*KindRun;
 }
 
 
-func (f *FileRun) Len() int		{ return len(f.Infos) }
-func (f *FileRun) Less(i, j int) bool	{ return f.Infos[i].less(f.Infos[j]) }
-func (f *FileRun) Swap(i, j int)	{ f.Infos[i], f.Infos[j] = f.Infos[j], f.Infos[i] }
+// Spots are sorted by path for the reduction into FileRuns.
+func lessSpot(x, y interface{}) bool	{ return x.(Spot).File.Path < y.(Spot).File.Path }
 
 
-// newFileRun allocates a new *FileRun from the Spot run [i, j) in h.
-func newFileRun(h *RunList, i, j int) interface{} {
-	file := h.At(i).(Spot).File;
-	infos := make([]SpotInfo, j-i);
+// newFileRun allocates a new FileRun from the Spot run [i, j) in h.
+func newFileRun(h0 *RunList, i, j int) interface{} {
+	file := h0.At(i).(Spot).File;
+
+	// reduce the list of Spots into a list of KindRuns
+	var h1 RunList;
+	h1.Vector.Init(j-i);
 	k := 0;
 	for ; i < j; i++ {
-		infos[k] = h.At(i).(Spot).Info;
+		h1.Set(k, h0.At(i).(Spot).Info);
 		k++;
 	}
-	run := &FileRun{file, infos};
-	// Spots were sorted by file to create this run.
-	// Within this run, sort them by line number.
-	sort.Sort(run);
-	// Remove duplicates: Both the lori and kind field
-	// must be the same for duplicate, and since the
-	// isIndex field is always the same for all infos
-	// in one list we can simply compare the entire
-	// info.
-	k = 0;
-	var prev SpotInfo;
-	for i, x := range infos {
-		if x != prev || i == 0 {
-			infos[k] = x;
-			k++;
-			prev = x;
-		}
+	h2 := h1.reduce(lessKind, newKindRun);
+
+	// create the FileRun
+	groups := make([]*KindRun, h2.Len());
+	for i := 0; i < h2.Len(); i++ {
+		groups[i] = h2.At(i).(*KindRun);
 	}
-	run.Infos = infos[0:k];
-	return run;
+	return &FileRun{file, groups};
 }
 
 
-// FileRuns are sorted by package.
-func lessFileRun(x, y interface{}) bool {
-	return x.(*FileRun).File.Pak.less(&y.(*FileRun).File.Pak);
-}
-
+// ----------------------------------------------------------------------------
+// PakRun
 
 // A PakRun describes a run of *FileRuns of a package.
 type PakRun struct {
@@ -244,11 +282,17 @@ type PakRun struct {
 
 // Sorting support for files within a PakRun.
 func (p *PakRun) Len() int		{ return len(p.Files) }
-func (p *PakRun) Less(i, j int) bool	{ return p.Files[i].File.less(p.Files[j].File) }
+func (p *PakRun) Less(i, j int) bool	{ return p.Files[i].File.Path < p.Files[j].File.Path }
 func (p *PakRun) Swap(i, j int)		{ p.Files[i], p.Files[j] = p.Files[j], p.Files[i] }
 
 
-// newPakRun allocates a new *PakRun from the *FileRun run [i, j) in h.
+// FileRuns are sorted by package for the reduction into PakRuns.
+func lessFileRun(x, y interface{}) bool {
+	return x.(*FileRun).File.Pak.less(&y.(*FileRun).File.Pak);
+}
+
+
+// newPakRun allocates a new PakRun from the *FileRun run [i, j) in h.
 func newPakRun(h *RunList, i, j int) interface{} {
 	pak := h.At(i).(*FileRun).File.Pak;
 	files := make([]*FileRun, j-i);
@@ -263,14 +307,17 @@ func newPakRun(h *RunList, i, j int) interface{} {
 }
 
 
-// PakRuns are sorted by package.
-func lessPakRun(x, y interface{}) bool	{ return x.(*PakRun).Pak.less(&y.(*PakRun).Pak) }
-
+// ----------------------------------------------------------------------------
+// HitList
 
 // A HitList describes a list of PakRuns.
 type HitList []*PakRun
 
 
+// PakRuns are sorted by package.
+func lessPakRun(x, y interface{}) bool	{ return x.(*PakRun).Pak.less(&y.(*PakRun).Pak) }
+
+
 func reduce(h0 *RunList) HitList {
 	// reduce a list of Spots into a list of FileRuns
 	h1 := h0.reduce(lessSpot, newFileRun);
@@ -308,6 +355,9 @@ func (h HitList) filter(pakname string) HitList {
 }
 
 
+// ----------------------------------------------------------------------------
+// AltWords
+
 type wordPair struct {
 	canon	string;	// canonical word spelling (all lowercase)
 	alt	string;	// alternative spelling
@@ -322,10 +372,11 @@ type AltWords struct {
 }
 
 
+// wordPairs are sorted by their canonical spelling.
 func lessWordPair(x, y interface{}) bool	{ return x.(*wordPair).canon < y.(*wordPair).canon }
 
 
-// newAltWords allocates a new *AltWords from the *wordPair run [i, j) in h.
+// newAltWords allocates a new AltWords from the *wordPair run [i, j) in h.
 func newAltWords(h *RunList, i, j int) interface{} {
 	canon := h.At(i).(*wordPair).canon;
 	alts := make([]string, j-i);