Round language stats percentage using largest remainder (#22026)

Fix #22023 

I've changed how the percentages for the language statistics are rounded
because they did not always add up to 100%
Now it's done with the largest remainder method, which makes sure that
total is 100%

Co-authored-by: Lauris BH <lauris@nix.lv>

1 files changed, 36 insertions, 4 deletions

diff --git a/models/repo/language_stats.go b/models/repo/language_stats.go
index f8f5dd041f..2da16814bd 100644
--- a/models/repo/language_stats.go
+++ b/models/repo/language_stats.go
@@ -6,6 +6,7 @@ package repo
 import (
 	"context"
 	"math"
+	"sort"
 	"strings"
 
 	"code.gitea.io/gitea/models/db"
@@ -43,7 +44,7 @@ func (stats LanguageStatList) LoadAttributes() {
 
 func (stats LanguageStatList) getLanguagePercentages() map[string]float32 {
 	langPerc := make(map[string]float32)
-	var otherPerc float32 = 100
+	var otherPerc float32
 	var total int64
 
 	for _, stat := range stats {
@@ -51,21 +52,52 @@ func (stats LanguageStatList) getLanguagePercentages() map[string]float32 {
 	}
 	if total > 0 {
 		for _, stat := range stats {
-			perc := float32(math.Round(float64(stat.Size)/float64(total)*1000) / 10)
+			perc := float32(float64(stat.Size) / float64(total) * 100)
 			if perc <= 0.1 {
+				otherPerc += perc
 				continue
 			}
-			otherPerc -= perc
 			langPerc[stat.Language] = perc
 		}
-		otherPerc = float32(math.Round(float64(otherPerc)*10) / 10)
 	}
 	if otherPerc > 0 {
 		langPerc["other"] = otherPerc
 	}
+	roundByLargestRemainder(langPerc, 100)
 	return langPerc
 }
 
+// Rounds to 1 decimal point, target should be the expected sum of percs
+func roundByLargestRemainder(percs map[string]float32, target float32) {
+	leftToDistribute := int(target * 10)
+
+	keys := make([]string, 0, len(percs))
+
+	for k, v := range percs {
+		percs[k] = v * 10
+		floored := math.Floor(float64(percs[k]))
+		leftToDistribute -= int(floored)
+		keys = append(keys, k)
+	}
+
+	// Sort the keys by the largest remainder
+	sort.SliceStable(keys, func(i, j int) bool {
+		_, remainderI := math.Modf(float64(percs[keys[i]]))
+		_, remainderJ := math.Modf(float64(percs[keys[j]]))
+		return remainderI > remainderJ
+	})
+
+	// Increment the values in order of largest remainder
+	for _, k := range keys {
+		percs[k] = float32(math.Floor(float64(percs[k])))
+		if leftToDistribute > 0 {
+			percs[k]++
+			leftToDistribute--
+		}
+		percs[k] /= 10
+	}
+}
+
 // GetLanguageStats returns the language statistics for a repository
 func GetLanguageStats(ctx context.Context, repo *Repository) (LanguageStatList, error) {
 	stats := make(LanguageStatList, 0, 6)