analysis

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
----

(*go/loader.Program).Load fails if it encounters a single parse error.
Make this more robust.

(*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 pacakge 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:
- Add an "analysis help" page explaining the features and UI in more detail.
- 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 oracle 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.

The pointer analysis constraint solver is way too slow.  We really
need to implement the constraint optimizer.  Also: performance has
been quite unpredictable; I recently optimized it fourfold with
type-based label tracking, but the benefit seems to have evaporated.
TODO(adonovan): take a look at recent CLs for regressions.

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/pkg/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 static (go/types) error, the location is highlighted in red and hover text provides the compiler error message.

Index

• func Run(pta bool, result *Result)
• type Link
• type PCGNodeJSON
• type Result
  • func (res *Result) FileInfo(url string) ([]interface{}, []Link)
  • func (res *Result) PackageInfo(importPath string) ([]*PCGNodeJSON, map[string]int, []*TypeInfoJSON)
• type TypeInfoJSON

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 Link

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 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) ([]interface{}, []Link)

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) ([]*PCGNodeJSON, map[string]int, []*TypeInfoJSON)

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

type TypeInfoJSON

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

JavaScript's onClickIdent() expects a TypeInfoJSON.