graph

package
v0.47.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 5, 2026 License: Unlicense Imports: 15 Imported by: 0

Documentation

Overview

Package graph implements NIP-XX Graph Query protocol support. This file contains the executor that runs graph traversal queries.

Package graph implements NIP-XX Graph Query protocol support. It provides types and functions for parsing and validating graph traversal queries.

Index

Constants

View Source 
const (
	KindGraphFollows  = 39000 // Response for follows/followers queries
	KindGraphMentions = 39001 // Response for mentions queries
	KindGraphThread   = 39002 // Response for thread traversal queries
)

Response kinds for graph queries (ephemeral range, relay-signed)

Variables

View Source 
var (
	ErrMissingMethod     = errors.New("_graph.method is required")
	ErrInvalidMethod     = errors.New("_graph.method must be one of: follows, followers, mentions, thread")
	ErrMissingSeed       = errors.New("_graph.seed is required")
	ErrInvalidSeed       = errors.New("_graph.seed must be a 64-character hex string")
	ErrDepthTooHigh      = errors.New("_graph.depth cannot exceed 16")
	ErrEmptyRefSpecKinds = errors.New("ref spec kinds array cannot be empty")
)

Validation errors

Functions

func IsGraphQuery 

func IsGraphQuery(f *filter.F) bool

IsGraphQuery returns true if the filter contains a _graph extension. This is a quick check that doesn't parse the full query.

Types

type Executor 

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

Executor handles graph query execution and response generation.

func NewExecutor 

func NewExecutor(db GraphDatabase, secretKey []byte) (*Executor, error)

NewExecutor creates a new graph query executor. The secretKey should be the 32-byte relay identity secret key.

func (*Executor) Execute 

func (e *Executor) Execute(q *Query) (*event.E, error)

Execute runs a graph query and returns a relay-signed event with results.

type GraphDatabase 

type GraphDatabase interface {
	// TraverseFollows performs BFS traversal of follow graph
	TraverseFollows(seedPubkey []byte, maxDepth int) (GraphResultI, error)
	// TraverseFollowers performs BFS traversal to find followers
	TraverseFollowers(seedPubkey []byte, maxDepth int) (GraphResultI, error)
	// FindMentions finds events mentioning a pubkey
	FindMentions(pubkey []byte, kinds []uint16) (GraphResultI, error)
	// TraverseThread performs BFS traversal of thread structure
	TraverseThread(seedEventID []byte, maxDepth int, direction string) (GraphResultI, error)
	// CollectInboundRefs finds events that reference items in the result
	CollectInboundRefs(result GraphResultI, depth int, kinds []uint16) error
	// CollectOutboundRefs finds events referenced by items in the result
	CollectOutboundRefs(result GraphResultI, depth int, kinds []uint16) error
}

GraphDatabase defines the interface for graph traversal operations. This is implemented by the database package.

type GraphResultI 

type GraphResultI interface {
	ToDepthArrays() [][]string
	ToEventDepthArrays() [][]string
	GetAllPubkeys() []string
	GetAllEvents() []string
	GetPubkeysByDepth() map[int][]string
	GetEventsByDepth() map[int][]string
	GetTotalPubkeys() int
	GetTotalEvents() int
	// Ref aggregation methods
	GetInboundRefs() map[uint16]map[string][]string
	GetOutboundRefs() map[uint16]map[string][]string
}

GraphResultI is the interface that database.GraphResult implements. This allows the executor to work with the database result without importing it.

type Query 

type Query struct {
	// Method is the traversal method: "follows", "followers", "mentions", "thread"
	Method string `json:"method"`

	// Seed is the starting point for traversal (pubkey hex or event ID hex)
	Seed string `json:"seed"`

	// Depth is the maximum traversal depth (1-16, default: 1)
	Depth int `json:"depth,omitempty"`

	// InboundRefs specifies which inbound references to collect
	// (events that reference discovered events via e-tags)
	InboundRefs []RefSpec `json:"inbound_refs,omitempty"`

	// OutboundRefs specifies which outbound references to collect
	// (events referenced by discovered events via e-tags)
	OutboundRefs []RefSpec `json:"outbound_refs,omitempty"`
}

Query represents a graph traversal query from a _graph filter extension.

func ExtractFromFilter 

func ExtractFromFilter(f *filter.F) (*Query, error)

ExtractFromFilter checks if a filter has a _graph extension and parses it. Returns nil if no _graph field is present. Returns an error if _graph is present but invalid.

func (*Query) HasInboundRefs 

func (q *Query) HasInboundRefs() bool

HasInboundRefs returns true if the query includes inbound reference collection.

func (*Query) HasOutboundRefs 

func (q *Query) HasOutboundRefs() bool

HasOutboundRefs returns true if the query includes outbound reference collection.

func (*Query) HasRefs 

func (q *Query) HasRefs() bool

HasRefs returns true if the query includes any reference collection.

func (*Query) InboundKindsAtDepth 

func (q *Query) InboundKindsAtDepth(depth int) map[int]bool

InboundKindsAtDepth returns a set of kinds that should be collected at the given depth. It aggregates all RefSpecs where from_depth <= depth.

func (*Query) OutboundKindsAtDepth 

func (q *Query) OutboundKindsAtDepth(depth int) map[int]bool

OutboundKindsAtDepth returns a set of kinds that should be collected at the given depth.

func (*Query) Validate 

func (q *Query) Validate() error

Validate checks the query for correctness and applies defaults.

type RateLimiter 

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

RateLimiter implements a token bucket rate limiter with adaptive throttling based on graph query complexity. It allows cooperative scheduling by inserting pauses between operations to allow other work to proceed.

func NewRateLimiter 

func NewRateLimiter(cfg RateLimiterConfig) *RateLimiter

NewRateLimiter creates a new rate limiter with the given configuration.

func (*RateLimiter) Acquire 

func (rl *RateLimiter) Acquire(ctx context.Context, cost float64) (time.Duration, error)

Acquire tries to acquire tokens for a query. If not enough tokens are available, it waits until they become available or the context is cancelled. Returns the delay that was applied, or an error if context was cancelled.

func (*RateLimiter) AvailableTokens 

func (rl *RateLimiter) AvailableTokens() float64

AvailableTokens returns the current number of available tokens.

func (*RateLimiter) OperationCost 

func (rl *RateLimiter) OperationCost(depth int, nodesAtDepth int) float64

OperationCost calculates the token cost for a single traversal operation. This is used during query execution for per-operation throttling.

func (*RateLimiter) Pause 

func (rl *RateLimiter) Pause(ctx context.Context, depth int, itemsProcessed int) error

Pause inserts a cooperative delay to allow other work to proceed. The delay is proportional to the current depth and load. This should be called periodically during long-running traversals.

func (*RateLimiter) QueryCost 

func (rl *RateLimiter) QueryCost(q *Query) float64

QueryCost calculates the token cost for a graph query based on its complexity. Higher depths and larger limits cost exponentially more tokens.

func (*RateLimiter) TryAcquire 

func (rl *RateLimiter) TryAcquire(cost float64) bool

TryAcquire attempts to acquire tokens without waiting. Returns true if successful, false if insufficient tokens.

type RateLimiterConfig 

type RateLimiterConfig struct {
	// MaxTokens is the maximum number of tokens in the bucket (default: 100)
	MaxTokens float64

	// RefillRate is tokens added per second (default: 10)
	RefillRate float64

	// BaseDelay is the minimum delay between operations (default: 1ms)
	BaseDelay time.Duration

	// MaxDelay is the maximum delay for complex queries (default: 100ms)
	MaxDelay time.Duration

	// DepthFactor is the cost multiplier per depth level (default: 2.0)
	// A depth-3 query costs 2^3 = 8x more tokens than depth-1
	DepthFactor float64

	// LimitFactor is additional cost per 100 results requested (default: 0.1)
	LimitFactor float64
}

RateLimiterConfig configures the rate limiter behavior.

func DefaultRateLimiterConfig 

func DefaultRateLimiterConfig() RateLimiterConfig

DefaultRateLimiterConfig returns sensible defaults for the rate limiter.

type RefSpec 

type RefSpec struct {
	// Kinds is the list of event kinds to match (OR semantics within this spec)
	Kinds []int `json:"kinds"`

	// FromDepth specifies the minimum depth at which to collect refs (default: 0)
	// 0 = include refs from seed itself
	// 1 = start from first-hop connections
	FromDepth int `json:"from_depth,omitempty"`
}

RefSpec specifies which event references to include in results.

type RefSummary added in v0.47.0 

type RefSummary struct {
	// Kind is the kind of the referencing/referenced events
	Kind uint16 `json:"kind"`

	// Target is the event ID being referenced (for inbound) or referencing (for outbound)
	Target string `json:"target"`

	// Count is the number of references
	Count int `json:"count"`

	// Refs is the list of event IDs (optional, may be omitted for large sets)
	Refs []string `json:"refs,omitempty"`
}

RefSummary represents aggregated reference data for a single target/source.

type ResponseContent 

type ResponseContent struct {
	// PubkeysByDepth contains arrays of pubkeys at each depth (1-indexed)
	// Each pubkey appears ONLY at the depth where it was first discovered.
	PubkeysByDepth [][]string `json:"pubkeys_by_depth,omitempty"`

	// EventsByDepth contains arrays of event IDs at each depth (1-indexed)
	EventsByDepth [][]string `json:"events_by_depth,omitempty"`

	// TotalPubkeys is the total count of unique pubkeys discovered
	TotalPubkeys int `json:"total_pubkeys,omitempty"`

	// TotalEvents is the total count of unique events discovered
	TotalEvents int `json:"total_events,omitempty"`

	// InboundRefs contains aggregated inbound references (events referencing discovered items)
	// Structure: array of {kind, target, count, refs[]}
	InboundRefs []RefSummary `json:"inbound_refs,omitempty"`

	// OutboundRefs contains aggregated outbound references (events referenced by discovered items)
	// Structure: array of {kind, source, count, refs[]}
	OutboundRefs []RefSummary `json:"outbound_refs,omitempty"`
}

ResponseContent is the JSON structure for graph query responses.

type Throttler 

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

Throttler provides a simple interface for cooperative scheduling during traversal. It wraps the rate limiter and provides depth-aware throttling.

func NewThrottler 

func NewThrottler(rl *RateLimiter, depth int) *Throttler

NewThrottler creates a throttler for a specific traversal operation.

func (*Throttler) Complete 

func (t *Throttler) Complete() (itemsProcessed int)

Complete marks the throttler as complete and returns stats.

func (*Throttler) Tick 

func (t *Throttler) Tick(ctx context.Context) error

Tick should be called after processing each item. It tracks progress and inserts pauses as needed.

Source Files

  • executor.go
  • query.go
  • ratelimit.go

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.