simplepath

Documentation

Overview

Package simplepath provides an implementation of paths. Finder that performs a breadth first search for paths against a stellar-core's database.

The core algorithm works as follows:

1. `search` object contains a queue of currently extended paths. Queue is initialized with a single-asset path containing destination asset. Paths are linked lists, head of the path is a newly extended source asset, tail of the path is always the destination asset.
2. Every iteration of search does the following: - pops a path from the queue, - checks if the path starts with a source asset, if it does, it appends the path to results, - finds all assets connected to the head of the current path and prepends the path, calculating the current cost.

Algorithm ends when there is no more paths to extend (len(queue) = 0) or `maxResults` has been reached.

The actual calculation of the cost is happening in `pathNode.Cost()` method. There are a couple of important things to note: 1. We are given `DestinationAmount` and the destination asset is the tail of the list. So we need to start from the end of the path and continue to the front. 2. Because we are going from the tail to the head of the path, given the path A -> B -> C. we are interested in finding:

• amount of B needed to buy `DestinationAmount` of C,
• amount of A needed to by above amount of B.

3. Finally, the actual path payment will sell A, buy B, sell B, buy C. So we need to check the following orderbooks:

• sell C, buy B (the user will sell B, buy C),
• sell B, buy A (the user will sell A, buy B).

The algorithm works as follows:

1. Because the head of the path is source account, we build a stack of assets to reverse that order.
2. We start with the last asset (pop the stack), calculate it's cost (if not cached) and continue towards the source asset (bottom of the stack).
3. We return the final cost.

Index

• Constants
• Variables
• type Finder
  • func (f *Finder) Find(q paths.Query, maxLength uint) (result []paths.Path, lastLedger uint32, err error)
  • func (f *Finder) FindFixedPaths(sourceAsset xdr.Asset, amountToSpend xdr.Int64, destinationAssets []xdr.Asset, ...) ([]paths.Path, uint32, error)
• type InMemoryFinder
  • func NewInMemoryFinder(graph *orderbook.OrderBookGraph) InMemoryFinder
  • func (finder InMemoryFinder) Find(q paths.Query, maxLength uint) ([]paths.Path, uint32, error)
  • func (finder InMemoryFinder) FindFixedPaths(sourceAsset xdr.Asset, amountToSpend xdr.Int64, destinationAssets []xdr.Asset, ...) ([]paths.Path, uint32, error)

Constants

const (

	// MaxInMemoryPathLength is the maximum path length which can be queried by the InMemoryFinder
	MaxInMemoryPathLength = 5
)

const MaxPathLength uint = 7

MaxPathLength is a maximum path length as defined in XDR file (includes source and destination assets).

Variables

var (
	// ErrEmptyInMemoryOrderBook indicates that the in memory order book is not yet populated
	ErrEmptyInMemoryOrderBook = errors.New("Empty orderbook")
)

var ErrNotEnough = errors.New("not enough depth")

ErrNotEnough represents an error that occurs when pricing a trade on an orderbook. This error occurs when the orderbook cannot fulfill the requested amount.

Types

type Finder

type Finder struct {
	Q *core.Q
}

Finder implements the paths.Finder interface and searchs for payment paths using a simple breadth first search of the offers table of a stellar-core.

This implementation is not meant to be fast or to provide the lowest costs paths, but rather is meant to be a simple implementation that gives usable paths.

func (*Finder) Find

func (f *Finder) Find(q paths.Query, maxLength uint) (result []paths.Path, lastLedger uint32, err error)

Find performs a path find with the provided query.

func (*Finder) FindFixedPaths

func (f *Finder) FindFixedPaths(
	sourceAsset xdr.Asset,
	amountToSpend xdr.Int64,
	destinationAssets []xdr.Asset,
	maxLength uint,
) ([]paths.Path, uint32, error)

FindFixedPaths will return an error because this implementation does not support this operation

type InMemoryFinder

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

InMemoryFinder is an implementation of the path finding interface using the in memory orderbook

func NewInMemoryFinder

func NewInMemoryFinder(graph *orderbook.OrderBookGraph) InMemoryFinder

NewInMemoryFinder constructs a new InMemoryFinder instance

func (InMemoryFinder) Find

func (finder InMemoryFinder) Find(q paths.Query, maxLength uint) ([]paths.Path, uint32, error)

Find implements the path payments finder interface

func (InMemoryFinder) FindFixedPaths

func (finder InMemoryFinder) FindFixedPaths(
	sourceAsset xdr.Asset,
	amountToSpend xdr.Int64,
	destinationAssets []xdr.Asset,
	maxLength uint,
) ([]paths.Path, uint32, error)

FindFixedPaths returns a list of payment paths where the source and destination assets are fixed. All returned payment paths will start by spending `amountToSpend` of `sourceAsset` and will end with some positive balance of `destinationAsset`. `sourceAccountID` is optional. if `sourceAccountID` is provided then no offers created by `sourceAccountID` will be considered when evaluating payment paths