README

Type and Pointer Analysis to-do list
====================================

Alan Donovan <adonovan@google.com>


Overall design
--------------

We should re-run the type and pointer analyses periodically,
as we do with the indexer.

Version skew: how to mitigate the bad effects of stale URLs in old pages?
We could record the file's length/CRC32/mtime in the go/loader, and
refuse to decorate it with links unless they match at serving time.

Use the VFS mechanism when (a) enumerating packages and (b) loading
them.  (Requires planned changes to go/loader.)

Future work: shard this using map/reduce for larger corpora.

Testing: how does one test that a web page "looks right"?


Bugs
----

(*ssa.Program).Create requires transitively error-free packages.  We
can make this more robust by making the requirement transitively free
of "hard" errors; soft errors are fine.

Markup of compiler errors is slightly buggy because they overlap with
other selections (e.g. Idents).  Fix.


User Interface
--------------

CALLGRAPH:
- Add a search box: given a search node, expand path from each entry
  point to it.
- Cause hovering over a given node to highlight that node, and all
  nodes that are logically identical to it.
- Initially expand the callgraph trees (but not their toggle divs).

CALLEES:
- The '(' links are not very discoverable.  Highlight them?

Type info:
- In the source viewer's lower pane, use a toggle div around the
  IMPLEMENTS and METHODSETS lists, like we do in the package view.
  Only expand them initially if short.
- Include IMPLEMENTS and METHOD SETS information in search index.
- URLs in IMPLEMENTS/METHOD SETS always link to source, even from the
  package docs view.  This makes sense for links to non-exported
  types, but links to exported types and funcs should probably go to
  other package docs.
- Suppress toggle divs for empty method sets.

Misc:
- The [X] button in the lower pane is subject to scrolling.
- Should the lower pane be floating?  An iframe?
  When we change document.location by clicking on a link, it will go away.
  How do we prevent that (a la Gmail's chat windows)?
- Progress/status: for each file, display its analysis status, one of:
   - not in analysis scope
   - type analysis running...
   - type analysis complete
     (+ optionally: there were type errors in this file)
   And if PTA requested:
   - type analysis complete; PTA not attempted due to type errors
   - PTA running...
   - PTA complete
- Scroll the selection into view, e.g. the vertical center, or better
  still, under the pointer (assuming we have a mouse).


More features
-------------

Display the REFERRERS relation?  (Useful but potentially large.)

Display the INSTANTIATIONS relation? i.e. given a type T, show the set of
syntactic constructs that can instantiate it:
    var x T
    x := T{...}
    x = new(T)
    x = make([]T, n)
    etc
    + all INSTANTIATIONS of all S defined as struct{t T} or [n]T
(Potentially a lot of information.)
(Add this to guru too.)


Optimisations
-------------

Each call to addLink takes a (per-file) lock.  The locking is
fine-grained so server latency isn't terrible, but overall it makes
the link computation quite slow.  Batch update might be better.

Memory usage is now about 1.5GB for GOROOT + go.tools.  It used to be 700MB.

Optimize for time and space.  The main slowdown is the network I/O
time caused by an increase in page size of about 3x: about 2x from
HTML, and 0.7--2.1x from JSON (unindented vs indented).  The JSON
contains a lot of filenames (e.g. 820 copies of 16 distinct
filenames).  20% of the HTML is L%d spans (now disabled).  The HTML
also contains lots of tooltips for long struct/interface types.
De-dup or just abbreviate?  The actual formatting is very fast.

Documentation

Overview

Package analysis performs type and pointer analysis and generates mark-up for the Go source view.

The Run method populates a Result object by running type and (optionally) pointer analysis. The Result object is thread-safe and at all times may be accessed by a serving thread, even as it is progressively populated as analysis facts are derived.

The Result is a mapping from each godoc file URL (e.g. /src/fmt/print.go) to information about that file. The information is a list of HTML markup links and a JSON array of structured data values. Some of the links call client-side JavaScript functions that index this array.

The analysis computes mark-up for the following relations:

IMPORTS: for each ast.ImportSpec, the package that it denotes.

RESOLUTION: for each ast.Ident, its kind and type, and the location of its definition.

METHOD SETS, IMPLEMENTS: for each ast.Ident defining a named type, its method-set, the set of interfaces it implements or is implemented by, and its size/align values.

CALLERS, CALLEES: for each function declaration ('func' token), its callers, and for each call-site ('(' token), its callees.

CALLGRAPH: the package docs include an interactive viewer for the intra-package call graph of "fmt".

CHANNEL PEERS: for each channel operation make/<-/close, the set of other channel ops that alias the same channel(s).

ERRORS: for each locus of a frontend (scanner/parser/type) error, the location is highlighted in red and hover text provides the compiler error message.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Run

func Run(pta bool, result *Result)

Run runs program analysis and computes the resulting markup, populating *result in a thread-safe manner, first with type information then later with pointer analysis information if enabled by the pta flag.

Types

type FileInfo

type FileInfo struct {
	Data  []interface{} // JSON serializable values
	Links []Link        // HTML link markup
}

FileInfo holds analysis information for the source file view. Clients must not mutate it.

type Link interface {
	Start() int
	End() int
	Write(w io.Writer, _ int, start bool) // the godoc.LinkWriter signature
}

A Link is an HTML decoration of the bytes [Start, End) of a file. Write is called before/after those bytes to emit the mark-up.

type PCGNodeJSON

type PCGNodeJSON struct {
	Func    anchorJSON
	Callees []int // indices within CALLGRAPH of nodes called by this one
}

JavaScript's cgAddChild requires a global array of PCGNodeJSON called CALLGRAPH, representing the intra-package call graph. The first element is special and represents "all external callers".

type PackageInfo

type PackageInfo struct {
	CallGraph      []*PCGNodeJSON
	CallGraphIndex map[string]int
	Types          []*TypeInfoJSON
}

PackageInfo holds analysis information for the package view. Clients must not mutate it.

type Result

type Result struct {
	// contains filtered or unexported fields
}

Result contains the results of analysis. The result contains a mapping from filenames to a set of HTML links and JavaScript data referenced by the links.

func (*Result) FileInfo

func (res *Result) FileInfo(url string) (fi FileInfo)

FileInfo returns new slices containing opaque JSON values and the HTML link markup for the specified godoc file URL. Thread-safe. Callers must not mutate the elements. It returns "zero" if no data is available.

func (*Result) PackageInfo

func (res *Result) PackageInfo(importPath string) PackageInfo

PackageInfo returns new slices of JSON values for the callgraph and type info for the specified package. Thread-safe. Callers must not mutate its fields. PackageInfo returns "zero" if no data is available.

func (*Result) Status

func (res *Result) Status() string

Status returns a human-readable description of the current analysis status.

type TypeInfoJSON

type TypeInfoJSON struct {
	Name        string // type name
	Size, Align int64
	Methods     []anchorJSON
	ImplGroups  []implGroupJSON
}

JavaScript's onClickIdent() expects a TypeInfoJSON.