15736109134

Committed 18 Jun 2025 02:46PM UTC coverage: 58.197% (-10.1%) from 68.248%

Build # 15736109134

Build Type

Pull #9752

github

Committed by

web-flow

Commit Message

Merge d2634a68c into 31c74f20f

Pull Request Pull Request #9752: routerrpc: reject payment to invoice that don't have payment secret or blinded paths

Run Details

6 of 13 new or added lines in 2 files covered. (46.15%)

28331 existing lines in 455 files now uncovered.

97860 of 168153 relevant lines covered (58.2%)

1.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/autopilot/choice.go

package autopilot

import (
        "errors"
        "fmt"
        "math/rand"
)

// ErrNoPositive is returned from weightedChoice when there are no positive
// weights left to choose from.
var ErrNoPositive = errors.New("no positive weights left")

// weightedChoice draws a random index from the slice of weights, with a
// probability proportional to the weight at the given index.
func weightedChoice(w []float64) (int, error) {
        // Calculate the sum of weights.
        var sum float64
        for _, v := range w {
                sum += v
        }

        if sum <= 0 {
                return 0, ErrNoPositive
        }

        // Pick a random number in the range [0.0, 1.0) and multiply it with
        // the sum of weights. Then we'll iterate the weights until the number
        // goes below 0. This means that each index is picked with a probability
        // equal to their normalized score.
        //
        // Example:
        // Items with scores [1, 5, 2, 2]
        // Normalized scores [0.1, 0.5, 0.2, 0.2]
        // Imagine they each occupy a "range" equal to their normalized score
        // in [0, 1.0]:
        // [|-0.1-||-----0.5-----||--0.2--||--0.2--|]
        // The following loop is now equivalent to "hitting" the intervals.
        r := rand.Float64() * sum
        for i := range w {
                r -= w[i]
                if r <= 0 {
                        return i, nil
                }
        }

        return 0, fmt.Errorf("unable to make choice")
}

// chooseN picks at random min[n, len(s)] nodes if from the NodeScore map, with
// a probability weighted by their score.
func chooseN(n uint32, s map[NodeID]*NodeScore) (
        map[NodeID]*NodeScore, error) {

        // Keep track of the number of nodes not yet chosen, in addition to
        // their scores and NodeIDs.
        rem := len(s)
        scores := make([]float64, len(s))
        nodeIDs := make([]NodeID, len(s))
        i := 0
        for k, v := range s {
                scores[i] = v.Score
                nodeIDs[i] = k
                i++
        }

        // Pick a weighted choice from the remaining nodes as long as there are
        // nodes left, and we haven't already picked n.
        chosen := make(map[NodeID]*NodeScore)
        for len(chosen) < int(n) && rem > 0 {
                choice, err := weightedChoice(scores)
                if err == ErrNoPositive {
                        return chosen, nil
                } else if err != nil {
                        return nil, err
                }

                nID := nodeIDs[choice]

                chosen[nID] = s[nID]

                // We set the score of the chosen node to 0, so it won't be
                // picked the next iteration.
                scores[choice] = 0
        }

        return chosen, nil
}

1	package autopilot
2
3	import (
4	"errors"
5	"fmt"
6	"math/rand"
7	)
8
9	// ErrNoPositive is returned from weightedChoice when there are no positive
10	// weights left to choose from.
11	var ErrNoPositive = errors.New("no positive weights left")
12
13	// weightedChoice draws a random index from the slice of weights, with a
14	// probability proportional to the weight at the given index.
UNCOV 15	func weightedChoice(w []float64) (int, error) {	×
UNCOV 16	// Calculate the sum of weights.	×
UNCOV 17	var sum float64	×
UNCOV 18	for _, v := range w {	×
UNCOV 19	sum += v	×
UNCOV 20	}	×
21
UNCOV 22	if sum <= 0 {	×
UNCOV 23	return 0, ErrNoPositive	×
UNCOV 24	}	×
25
26	// Pick a random number in the range [0.0, 1.0) and multiply it with
27	// the sum of weights. Then we'll iterate the weights until the number
28	// goes below 0. This means that each index is picked with a probability
29	// equal to their normalized score.
30	//
31	// Example:
32	// Items with scores [1, 5, 2, 2]
33	// Normalized scores [0.1, 0.5, 0.2, 0.2]
34	// Imagine they each occupy a "range" equal to their normalized score
35	// in [0, 1.0]:
36	// [\|-0.1-\|\|-----0.5-----\|\|--0.2--\|\|--0.2--\|]
37	// The following loop is now equivalent to "hitting" the intervals.
UNCOV 38	r := rand.Float64() * sum	×
UNCOV 39	for i := range w {	×
UNCOV 40	r -= w[i]	×
UNCOV 41	if r <= 0 {	×
UNCOV 42	return i, nil	×
UNCOV 43	}	×
44	}
45
46	return 0, fmt.Errorf("unable to make choice")	×
47	}
48
49	// chooseN picks at random min[n, len(s)] nodes if from the NodeScore map, with
50	// a probability weighted by their score.
51	func chooseN(n uint32, s map[NodeID]*NodeScore) (
UNCOV 52	map[NodeID]*NodeScore, error) {	×
UNCOV 53		×
UNCOV 54	// Keep track of the number of nodes not yet chosen, in addition to	×
UNCOV 55	// their scores and NodeIDs.	×
UNCOV 56	rem := len(s)	×
UNCOV 57	scores := make([]float64, len(s))	×
UNCOV 58	nodeIDs := make([]NodeID, len(s))	×
UNCOV 59	i := 0	×
UNCOV 60	for k, v := range s {	×
UNCOV 61	scores[i] = v.Score	×
UNCOV 62	nodeIDs[i] = k	×
UNCOV 63	i++	×
UNCOV 64	}	×
65
66	// Pick a weighted choice from the remaining nodes as long as there are
67	// nodes left, and we haven't already picked n.
UNCOV 68	chosen := make(map[NodeID]*NodeScore)	×
UNCOV 69	for len(chosen) < int(n) && rem > 0 {	×
UNCOV 70	choice, err := weightedChoice(scores)	×
UNCOV 71	if err == ErrNoPositive {	×
UNCOV 72	return chosen, nil	×
UNCOV 73	} else if err != nil {	×
74	return nil, err	×
75	}	×
76
UNCOV 77	nID := nodeIDs[choice]	×
UNCOV 78		×
UNCOV 79	chosen[nID] = s[nID]	×
UNCOV 80		×
UNCOV 81	// We set the score of the chosen node to 0, so it won't be	×
UNCOV 82	// picked the next iteration.	×
UNCOV 83	scores[choice] = 0	×
84	}
85
UNCOV 86	return chosen, nil	×
87	}

lightningnetwork / lnd / 15736109134

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous