onionmessage: add BFS pathfinding for onion messages

diff --git a/onionmessage/errors.go b/onionmessage/errors.go
index ac79808..32898b4 100644
--- a/onionmessage/errors.go
+++ b/onionmessage/errors.go
@@ -19,4 +19,15 @@ var (
 	// would be sent back to the same peer it was received from.
 	ErrSamePeerCycle = errors.New("onion message cycle: next " +
 		"hop is the sending peer")
+	// ErrNoPathFound is returned when no path exists between the source
+	// and destination nodes that supports onion messaging.
+	ErrNoPathFound = errors.New("no path found to destination")
+
+	// ErrDestinationNoOnionSupport is returned when the destination node
+	// does not advertise support for onion messages.
+	ErrDestinationNoOnionSupport = errors.New("destination does not " +
+		"support onion messages")
+
+	// ErrNodeNotFound is returned when the node is not found in the graph.
+	ErrNodeNotFound = errors.New("node not found in graph")
 )
diff --git a/onionmessage/pathfind.go b/onionmessage/pathfind.go
new file mode 100644
index 0000000..a9e4ff6
--- /dev/null
+++ b/onionmessage/pathfind.go
@@ -0,0 +1,161 @@
+package onionmessage
+
+import (
+	"context"
+	"errors"
+
+	graphdb "github.com/lightningnetwork/lnd/graph/db"
+	"github.com/lightningnetwork/lnd/lnwire"
+	"github.com/lightningnetwork/lnd/routing/route"
+)
+
+// OnionMessagePath represents a route found for an onion message. It is a slice
+// of vertices ordered from the first-hop peer to the destination.
+type OnionMessagePath []route.Vertex
+
+// FindPath finds the shortest path (by hop count) from source to destination
+// through nodes that support onion messaging (feature bit 38/39). It uses a
+// standard BFS on the channel graph filtered by the OnionMessagesOptional
+// feature bit.
+func FindPath(ctx context.Context, graph graphdb.NodeTraverser, source,
+	destination route.Vertex, maxHops int) (OnionMessagePath, error) {
+
+	// Check that the destination supports onion messaging.
+	destFeatures, err := graph.FetchNodeFeatures(ctx, destination)
+	if err != nil {
+		return nil, err
+	}
+
+	// An empty feature vector means the node is absent from our graph.
+	// In that case, we send back a NotFound error.
+	if len(destFeatures.Features()) == 0 {
+		return nil, ErrNodeNotFound
+	}
+
+	if !destFeatures.HasFeature(lnwire.OnionMessagesOptional) {
+		return nil, ErrDestinationNoOnionSupport
+	}
+
+	// If source == destination, return empty path.
+	if source == destination {
+		return OnionMessagePath{}, nil
+	}
+
+	parent := make(map[route.Vertex]route.Vertex)
+	visited := make(map[route.Vertex]bool)
+
+	visited[source] = true
+
+	queue := []route.Vertex{source}
+	depth := 0
+
+	for len(queue) > 0 {
+		depth++
+		if depth > maxHops {
+			break
+		}
+
+		nextQueue := make([]route.Vertex, 0)
+
+		for _, current := range queue {
+			err := graph.ForEachNodeDirectedChannel(ctx, current,
+				func(channel *graphdb.DirectedChannel) error {
+					neighbor := channel.OtherNode
+
+					if visited[neighbor] {
+						return nil
+					}
+
+					// Mark visited before the feature check
+					// so we never fetch features for the
+					// same node twice.
+					visited[neighbor] = true
+
+					// Skip nodes that don't support onion
+					// messaging.
+					feats, err := graph.FetchNodeFeatures(
+						ctx, neighbor,
+					)
+					if err != nil {
+						// If the context is canceled or
+						// deadline exceeded, propagate
+						// the error.
+
+						if ctx.Err() != nil {
+							return err
+						}
+
+						log.Tracef("Unable to fetch "+
+							"features for node "+
+							"%v: %v",
+							neighbor.String(), err)
+
+						return nil
+					}
+
+					if !feats.HasFeature(
+						lnwire.OnionMessagesOptional,
+					) {
+
+						return nil
+					}
+
+					parent[neighbor] = current
+
+					if neighbor == destination {
+						return errBFSDone
+					}
+
+					nextQueue = append(
+						nextQueue, neighbor,
+					)
+
+					return nil
+				},
+				func() {},
+			)
+
+			// Check if we found the destination.
+			if errors.Is(err, errBFSDone) {
+				return reconstructPath(
+					parent, source, destination,
+				), nil
+			}
+
+			if err != nil {
+				return nil, err
+			}
+		}
+
+		queue = nextQueue
+	}
+
+	return nil, ErrNoPathFound
+}
+
+// errBFSDone is a sentinel error used internally to break out of the
+// ForEachNodeDirectedChannel callback when the destination is found.
+var errBFSDone = errors.New("bfs done")
+
+// reconstructPath rebuilds the path from destination back to source using the
+// parent map, returning the hops in forward order (excluding source).
+func reconstructPath(parent map[route.Vertex]route.Vertex,
+	source, destination route.Vertex) OnionMessagePath {
+
+	// Calculate path length to pre-allocate the slice.
+	pathLen := 0
+	for curr := destination; curr != source; curr = parent[curr] {
+		pathLen++
+	}
+
+	// Populate the path in correct order, avoiding a separate reversal
+	// step.
+	path := make(OnionMessagePath, pathLen)
+	curr := destination
+	for i := pathLen - 1; i >= 0; i-- {
+		path[i] = curr
+		curr = parent[curr]
+	}
+
+	return path
+}
diff --git a/onionmessage/pathfind_test.go b/onionmessage/pathfind_test.go
new file mode 100644
index 0000000..1b7e6ff
--- /dev/null
+++ b/onionmessage/pathfind_test.go
@@ -0,0 +1,361 @@
+package onionmessage
+
+import (
+	"context"
+	"testing"
+
+	graphdb "github.com/lightningnetwork/lnd/graph/db"
+	"github.com/lightningnetwork/lnd/lnwire"
+	"github.com/lightningnetwork/lnd/routing/route"
+	"github.com/stretchr/testify/require"
+)
+
+// mockNodeTraverser implements graphdb.NodeTraverser for testing the BFS
+// pathfinding algorithm.
+type mockNodeTraverser struct {
+	// edges maps each node to its list of channel neighbors.
+	edges map[route.Vertex][]route.Vertex
+
+	// features maps each node to its advertised feature vector.
+	features map[route.Vertex]*lnwire.FeatureVector
+}
+
+// newMockNodeTraverser creates a new mockNodeTraverser with initialized maps.
+func newMockNodeTraverser() *mockNodeTraverser {
+	return &mockNodeTraverser{
+		edges:    make(map[route.Vertex][]route.Vertex),
+		features: make(map[route.Vertex]*lnwire.FeatureVector),
+	}
+}
+
+// addNode adds a node with the given features to the mock graph.
+func (m *mockNodeTraverser) addNode(v route.Vertex,
+	features *lnwire.FeatureVector) {
+
+	m.features[v] = features
+}
+
+// addEdge adds a bidirectional edge between two nodes.
+func (m *mockNodeTraverser) addEdge(a, b route.Vertex) {
+	m.edges[a] = append(m.edges[a], b)
+	m.edges[b] = append(m.edges[b], a)
+}
+
+// ForEachNodeDirectedChannel calls the callback for every channel neighbor of
+// the given node.
+func (m *mockNodeTraverser) ForEachNodeDirectedChannel(
+	_ context.Context, nodePub route.Vertex,
+	cb func(channel *graphdb.DirectedChannel) error,
+	reset func()) error {
+
+	neighbors, ok := m.edges[nodePub]
+	if !ok {
+		return nil
+	}
+
+	for _, neighbor := range neighbors {
+		err := cb(&graphdb.DirectedChannel{
+			OtherNode: neighbor,
+		})
+		if err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+// FetchNodeFeatures returns the features of the given node. Returns an
+// EmptyFeatureVector (nil error) when the node is absent, matching the
+// production DB behaviour of graphdb.nodeTraverserSession.
+func (m *mockNodeTraverser) FetchNodeFeatures(
+	_ context.Context,
+	nodePub route.Vertex) (*lnwire.FeatureVector, error) {
+
+	features, ok := m.features[nodePub]
+	if !ok {
+		return lnwire.EmptyFeatureVector(), nil
+	}
+
+	return features, nil
+}
+
+// vertexFromByte creates a test Vertex from a single byte for readability.
+func vertexFromByte(b byte) route.Vertex {
+	var v route.Vertex
+	v[0] = b
+
+	return v
+}
+
+// onionFeatures returns a feature vector with the OnionMessagesOptional bit
+// set.
+func onionFeatures() *lnwire.FeatureVector {
+	return lnwire.NewFeatureVector(
+		lnwire.NewRawFeatureVector(lnwire.OnionMessagesOptional),
+		nil,
+	)
+}
+
+// noOnionFeatures returns a feature vector that has some bits set (e.g.
+// data-loss-protect) but NOT onion message support. This simulates a node
+// that is present in the graph but does not advertise onion messages,
+// as distinct from a node that is absent from the graph entirely (which
+// returns a zero-bit EmptyFeatureVector).
+func noOnionFeatures() *lnwire.FeatureVector {
+	return lnwire.NewFeatureVector(
+		lnwire.NewRawFeatureVector(lnwire.DataLossProtectOptional),
+		nil,
+	)
+}
+
+// TestFindPathDirectNeighbor tests pathfinding when destination is a direct
+// neighbor.
+func TestFindPathDirectNeighbor(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	dest := vertexFromByte(2)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+	graph.addEdge(source, dest)
+
+	path, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 1)
+	require.Equal(t, dest, path[0])
+}
+
+// TestFindPathMultiHop tests pathfinding across multiple hops.
+func TestFindPathMultiHop(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	hop1 := vertexFromByte(2)
+	hop2 := vertexFromByte(3)
+	dest := vertexFromByte(4)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(hop1, onionFeatures())
+	graph.addNode(hop2, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	graph.addEdge(source, hop1)
+	graph.addEdge(hop1, hop2)
+	graph.addEdge(hop2, dest)
+
+	path, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 3)
+	require.Equal(t, hop1, path[0])
+	require.Equal(t, hop2, path[1])
+	require.Equal(t, dest, path[2])
+}
+
+// TestFindPathFeatureFiltering tests that nodes without onion message support
+// are skipped, finding a longer path through supporting nodes.
+func TestFindPathFeatureFiltering(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	noOnion := vertexFromByte(2)
+	withOnion := vertexFromByte(3)
+	withOnion2 := vertexFromByte(4)
+	dest := vertexFromByte(5)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(noOnion, noOnionFeatures())
+	graph.addNode(withOnion, onionFeatures())
+	graph.addNode(withOnion2, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	// Direct path through noOnion (shorter).
+	graph.addEdge(source, noOnion)
+	graph.addEdge(noOnion, dest)
+
+	// Alternate path through withOnion (longer).
+	graph.addEdge(source, withOnion)
+	graph.addEdge(withOnion, withOnion2)
+	graph.addEdge(withOnion2, dest)
+
+	path, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 3)
+	require.Equal(t, withOnion, path[0])
+	require.Equal(t, withOnion2, path[1])
+	require.Equal(t, dest, path[2])
+}
+
+// TestFindPathNoPathExists tests that ErrNoPathFound is returned when the
+// graph is disconnected.
+func TestFindPathNoPathExists(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	dest := vertexFromByte(2)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	// No edges between source and dest.
+	_, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.ErrorIs(t, err, ErrNoPathFound)
+}
+
+// TestFindPathDestinationNotInGraph tests that ErrNodeNotFound is returned when
+// the destination has no entry in the graph (empty feature vector).
+func TestFindPathDestinationNotInGraph(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	dest := vertexFromByte(2)
+
+	// dest not added to graph; FetchNodeFeatures returns
+	// EmptyFeatureVector.
+	graph.addNode(source, onionFeatures())
+
+	_, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.ErrorIs(t, err, ErrNodeNotFound)
+}
+
+// TestFindPathDestinationNoOnionSupport tests that
+// ErrDestinationNoOnionSupport is returned when the destination doesn't
+// support onion messages.
+func TestFindPathDestinationNoOnionSupport(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	dest := vertexFromByte(2)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(dest, noOnionFeatures())
+	graph.addEdge(source, dest)
+
+	_, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.ErrorIs(t, err, ErrDestinationNoOnionSupport)
+}
+
+// TestFindPathMaxHopsExceeded tests that ErrNoPathFound is returned when the
+// path exceeds the maximum number of hops.
+func TestFindPathMaxHopsExceeded(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	hop1 := vertexFromByte(2)
+	hop2 := vertexFromByte(3)
+	dest := vertexFromByte(4)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(hop1, onionFeatures())
+	graph.addNode(hop2, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	graph.addEdge(source, hop1)
+	graph.addEdge(hop1, hop2)
+	graph.addEdge(hop2, dest)
+
+	// Path requires 3 hops, but maxHops is 2.
+	_, err := FindPath(t.Context(), graph, source, dest, 2)
+	require.ErrorIs(t, err, ErrNoPathFound)
+}
+
+// TestFindPathWithCycles tests that BFS correctly handles cycles in the graph.
+func TestFindPathWithCycles(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	a := vertexFromByte(2)
+	b := vertexFromByte(3)
+	c := vertexFromByte(4)
+	dest := vertexFromByte(5)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(a, onionFeatures())
+	graph.addNode(b, onionFeatures())
+	graph.addNode(c, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	// Create a cycle: source -> a -> b -> c -> a
+	graph.addEdge(source, a)
+	graph.addEdge(a, b)
+	graph.addEdge(b, c)
+	graph.addEdge(c, a)
+
+	// Path to dest through b.
+	graph.addEdge(b, dest)
+
+	path, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 3)
+	require.Equal(t, a, path[0])
+	require.Equal(t, b, path[1])
+	require.Equal(t, dest, path[2])
+}
+
+// TestFindPathShortestPath tests that BFS finds the shortest path when
+// multiple paths of different lengths exist.
+func TestFindPathShortestPath(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	source := vertexFromByte(1)
+	a := vertexFromByte(2)
+	b := vertexFromByte(3)
+	c := vertexFromByte(4)
+	dest := vertexFromByte(5)
+
+	graph.addNode(source, onionFeatures())
+	graph.addNode(a, onionFeatures())
+	graph.addNode(b, onionFeatures())
+	graph.addNode(c, onionFeatures())
+	graph.addNode(dest, onionFeatures())
+
+	// Long path: source -> a -> b -> c -> dest (4 hops).
+	graph.addEdge(source, a)
+	graph.addEdge(a, b)
+	graph.addEdge(b, c)
+	graph.addEdge(c, dest)
+
+	// Short path: source -> b -> dest (2 hops).
+	graph.addEdge(source, b)
+	graph.addEdge(b, dest)
+
+	path, err := FindPath(t.Context(), graph, source, dest, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 2)
+	require.Equal(t, b, path[0])
+	require.Equal(t, dest, path[1])
+}
+
+// TestFindPathSameSourceAndDest tests that finding a path from a node to
+// itself returns an empty path.
+func TestFindPathSameSourceAndDest(t *testing.T) {
+	t.Parallel()
+
+	graph := newMockNodeTraverser()
+
+	node := vertexFromByte(1)
+	graph.addNode(node, onionFeatures())
+
+	path, err := FindPath(t.Context(), graph, node, node, 20)
+	require.NoError(t, err)
+	require.Len(t, path, 0)
+}