graph

Documentation

Overview

Package graph contains methods to explore reachable invocations.

Package graph contains methods to explore reachable invocations.

Package graph contains methods to explore reachable invocations.

Index

• Constants
• Variables
• func FindInheritSourcesDescendants(ctx context.Context, invID invocations.ID) (invocations.IDSet, error)
• func FindRoots(ctx context.Context, invID invocations.ID) (invocations.IDSet, error)
• type ReachableInvocation
• type ReachableInvocations
  • func NewReachableInvocations() ReachableInvocations
  • func Reachable(ctx context.Context, roots invocations.IDSet) (ReachableInvocations, error)
  • func ReachableSkipRootCache(ctx context.Context, roots invocations.IDSet) (ReachableInvocations, error)
  • func (r ReachableInvocations) Batches() []ReachableInvocations
  • func (r ReachableInvocations) IDSet() (invocations.IDSet, error)
  • func (r ReachableInvocations) InstructionMap() (map[invocations.ID]*pb.VerdictInstruction, error)
  • func (r *ReachableInvocations) Union(other ReachableInvocations)
  • func (r ReachableInvocations) WithExonerationsIDSet() (invocations.IDSet, error)
  • func (r ReachableInvocations) WithTestResultsIDSet() (invocations.IDSet, error)
• type SourceHash
  • func HashSources(s *pb.Sources) SourceHash
  • func (h SourceHash) String() string

Constants

const MaxNodes = 20000

MaxNodes is the maximum number of invocation nodes that ResultDB can operate on at a time.

Variables

var ErrUnknownReach = fmt.Errorf("the reachable set is unknown")

ErrUnknownReach is returned by ReachCache.Read if the cached value is absent.

var TooManyTag = errors.BoolTag{
	Key: errors.NewTagKey("too many matching invocations matched the condition"),
}

TooManyTag set in an error indicates that too many invocations matched a condition.

Functions

func FindInheritSourcesDescendants

func FindInheritSourcesDescendants(ctx context.Context, invID invocations.ID) (invocations.IDSet, error)

FindInheritSourcesDescendants finds and return all invocations (including the root) which inherit commit source information from the root.

func FindRoots

func FindRoots(ctx context.Context, invID invocations.ID) (invocations.IDSet, error)

FindRoots returns ALL root invocations for a given invocation. A root either

• has is_export_root = true, or
• has no parent invocation.

If the given invocation is already a root, it will return a ID set that only contains the given invocation. If the given invocation has no root (eg. a <-> b), it will return an empty ID set.

It will stop traverse the current path further once a root is encountered. For example, with graph a(is_export_root) -> b (is_export_root) -> c <- d, FindRoots(c) will return [b,d]. -> means includes.

Types

type ReachableInvocation

type ReachableInvocation struct {
	// HasTestResults stores whether the invocation has any test results.
	HasTestResults bool
	// HasTestResults stores whether the invocation has any test exonerations.
	HasTestExonerations bool
	// The realm of the invocation.
	Realm string
	// The source associated with the invocation, which can be looked up in
	// ReachableInvocations.Sources.
	// If no sources could be resolved, this is EmptySourceHash.
	SourceHash SourceHash
	// The instructions associated with this invocation.
	// Note that all contents will be set to empty string "", to reduce
	// the memory footprint when we load the invocation tree.
	Instructions *pb.Instructions
	// Contains the invocation IDs that this invocation includes.
	IncludedInvocationIDs []invocations.ID
}

ReachableInvocation contains summary information about a reachable invocation.

type ReachableInvocations

type ReachableInvocations struct {
	// The set of reachable invocations, including the root
	// invocation from which reachability was explored.
	Invocations map[invocations.ID]ReachableInvocation
	// The distinct code sources in the reachable invocation graph.
	// Stored here rather than on the invocations themselves to
	// simplify deduplicating sources objects as many will be the
	// same between invocations.
	Sources map[SourceHash]*pb.Sources
}

ReachableInvocations is a set of reachable invocations, including summary information about each invocation. The set includes the root invocation(s) from which reachables were explored.

func NewReachableInvocations

func NewReachableInvocations() ReachableInvocations

func Reachable

func Reachable(ctx context.Context, roots invocations.IDSet) (ReachableInvocations, error)

Reachable returns all invocations reachable from roots along the inclusion edges. May return an appstatus-annotated error.

func ReachableSkipRootCache

func ReachableSkipRootCache(ctx context.Context, roots invocations.IDSet) (ReachableInvocations, error)

ReachableSkipRootCache is similar to Reachable, but it ignores cache for the roots.

Useful to keep cache-hit stats high in cases where the roots are known not to have cache.

func (ReachableInvocations) Batches

func (r ReachableInvocations) Batches() []ReachableInvocations

Batches splits s into batches. The batches are sorted by RowID(), such that interval (minRowID, maxRowID) of each batch does not overlap with any other batch.

The size of batch is hardcoded 50, because that's the maximum parallelism we get from Cloud Spanner.

func (ReachableInvocations) IDSet

func (r ReachableInvocations) IDSet() (invocations.IDSet, error)

IDSet returns the set of invocation IDs included in the list of reachable invocations.

func (ReachableInvocations) InstructionMap

func (r ReachableInvocations) InstructionMap() (map[invocations.ID]*pb.VerdictInstruction, error)

InstructionMap returns a mapping invocation_id => VerdictInstruction. It tells where the instructions for each invocation locates. If an invocation does not have instruction, it will not have an entry in the map.

func (*ReachableInvocations) Union

func (r *ReachableInvocations) Union(other ReachableInvocations)

Union adds other reachable invocations.

func (ReachableInvocations) WithExonerationsIDSet

func (r ReachableInvocations) WithExonerationsIDSet() (invocations.IDSet, error)

WithExonerationsIDSet returns the set of invocation IDs that contain test exonerations.

func (ReachableInvocations) WithTestResultsIDSet

func (r ReachableInvocations) WithTestResultsIDSet() (invocations.IDSet, error)

WithTestResultsIDSet returns the set of invocation IDs that contain test results.

type SourceHash

type SourceHash string

SourceHash stores a 12 byte hash of sources, as raw bytes. To display, use the String() method.

const (
	EmptySourceHash SourceHash = ""
)

func HashSources

func HashSources(s *pb.Sources) SourceHash

HashSources returns a hash of the given code sources proto, which can be used as a key in maps.

func (SourceHash) String

func (h SourceHash) String() string