[performance] rewrite timelines to rely on new timeline cache type (#3941)

* start work rewriting timeline cache type

* further work rewriting timeline caching

* more work integration new timeline code

* remove old code

* add local timeline, fix up merge conflicts

* remove old use of go-bytes

* implement new timeline code into more areas of codebase, pull in latest go-mangler, go-mutexes, go-structr

* remove old timeline package, add local timeline cache

* remove references to old timeline types that needed starting up in tests

* start adding page validation

* fix test-identified timeline cache package issues

* fix up more tests, fix missing required changes, etc

* add exclusion for test.out in gitignore

* clarify some things better in code comments

* tweak cache size limits

* fix list timeline cache fetching

* further list timeline fixes

* linter, ssssssssshhhhhhhhhhhh please

* fix linter hints

* reslice the output if it's beyond length of 'lim'

* remove old timeline initialization code, bump go-structr to v0.9.4

* continued from previous commit

* improved code comments

* don't allow multiple entries for BoostOfID values to prevent repeated boosts of same boosts

* finish writing more code comments

* some variable renaming, for ease of following

* change the way we update lo,hi paging values during timeline load

* improved code comments for updated / returned lo , hi paging values

* finish writing code comments for the StatusTimeline{} type itself

* fill in more code comments

* update go-structr version to latest with changed timeline unique indexing logic

* have a local and public timeline *per user*

* rewrite calls to public / local timeline calls

* remove the zero length check, as lo, hi values might still be set

* simplify timeline cache loading, fix lo/hi returns, fix timeline invalidation side-effects missing for some federated actions

* swap the lo, hi values :facepalm:

* add (now) missing slice reverse of tag timeline statuses when paging ASC

* remove local / public caches (is out of scope for this work), share more timeline code

* remove unnecessary change

* again, remove more unused code

* remove unused function to appease the linter

* move boost checking to prepare function

* fix use of timeline.lastOrder, fix incorrect range functions used

* remove comments for repeat code

* remove the boost logic from prepare function

* do a maximum of 5 loads, not 10

* add repeat boost filtering logic, update go-structr, general improvements

* more code comments

* add important note

* fix timeline tests now that timelines are returned in page order

* remove unused field

* add StatusTimeline{} tests

* add more status timeline tests

* start adding preloading support

* ensure repeat boosts are marked in preloaded entries

* share a bunch of the database load code in timeline cache, don't clear timelines on relationship change

* add logic to allow dynamic clear / preloading of timelines

* comment-out unused functions, but leave in place as we might end-up using them

* fix timeline preload state check

* much improved status timeline code comments

* more code comments, don't bother inserting statuses if timeline not preloaded

* shift around some logic to make sure things aren't accidentally left set

* finish writing code comments

* remove trim-after-insert behaviour

* fix-up some comments referring to old logic

* remove unsetting of lo, hi

* fix preload repeatBoost checking logic

* don't return on status filter errors, these are usually transient

* better concurrency safety in Clear() and Done()

* fix test broken due to addition of preloader

* fix repeatBoost logic that doesn't account for already-hidden repeatBoosts

* ensure edit submodels are dropped on cache insertion

* update code-comment to expand CAS accronym

* use a plus1hULID() instead of 24h

* remove unused functions

* add note that public / local timeline requester can be nil

* fix incorrect visibility filtering of tag timeline statuses

* ensure we filter home timeline statuses on local only

* some small re-orderings to confirm query params in correct places

* fix the local only home timeline filter func

1 files changed, 361 insertions, 0 deletions

diff --git a/internal/cache/timeline/status_test.go b/internal/cache/timeline/status_test.go
new file mode 100644
index 000000000..3e53d8256
--- /dev/null
+++ b/internal/cache/timeline/status_test.go
@@ -0,0 +1,361 @@
+// GoToSocial
+// Copyright (C) GoToSocial Authors admin@gotosocial.org
+// SPDX-License-Identifier: AGPL-3.0-or-later
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Affero General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU Affero General Public License for more details.
+//
+// You should have received a copy of the GNU Affero General Public License
+// along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+package timeline
+
+import (
+	"slices"
+	"testing"
+
+	"codeberg.org/gruf/go-structr"
+	"github.com/stretchr/testify/assert"
+	apimodel "github.com/superseriousbusiness/gotosocial/internal/api/model"
+	"github.com/superseriousbusiness/gotosocial/internal/gtsmodel"
+)
+
+var testStatusMeta = []*StatusMeta{
+	{
+		ID:               "06B19VYTHEG01F3YW13RQE0QM8",
+		AccountID:        "06B1A61MZEBBVDSNPRJAA8F2C4",
+		BoostOfID:        "06B1A5KQWGQ1ABM3FA7TDX1PK8",
+		BoostOfAccountID: "06B1A6707818050PCK8SJAEC6G",
+	},
+	{
+		ID:               "06B19VYTJFT0KDWT5C1CPY0XNC",
+		AccountID:        "06B1A61MZN3ZQPZVNGEFBNYBJW",
+		BoostOfID:        "06B1A5KQWSGFN4NNRV34KV5S9R",
+		BoostOfAccountID: "06B1A6707HY8RAXG7JPCWR7XD4",
+	},
+	{
+		ID:               "06B19VYTJ6WZQPRVNJHPEZH04W",
+		AccountID:        "06B1A61MZY7E0YB6G01VJX8ERR",
+		BoostOfID:        "06B1A5KQX5NPGSYGH8NC7HR1GR",
+		BoostOfAccountID: "06B1A6707XCSAF0MVCGGYF9160",
+	},
+	{
+		ID:               "06B19VYTJPKGG8JYCR1ENAV7KC",
+		AccountID:        "06B1A61N07K1GC35PJ3CZ4M020",
+		BoostOfID:        "06B1A5KQXG6ZCWE1R7C7KR7RYW",
+		BoostOfAccountID: "06B1A67084W6SB6P6HJB7K5DSG",
+	},
+	{
+		ID:               "06B19VYTHRR8S35QXC5A6VE2YW",
+		AccountID:        "06B1A61N0P1TGQDVKANNG4AKP4",
+		BoostOfID:        "06B1A5KQY3K839Z6S5HHAJKSWW",
+		BoostOfAccountID: "06B1A6708SPJC3X3ZG3SGG8BN8",
+	},
+}
+
+func TestStatusTimelineUnprepare(t *testing.T) {
+	var tt StatusTimeline
+	tt.Init(1000)
+
+	// Clone the input test status data.
+	data := slices.Clone(testStatusMeta)
+
+	// Bodge some 'prepared'
+	// models on test data.
+	for _, meta := range data {
+		meta.prepared = &apimodel.Status{}
+	}
+
+	// Insert test data into timeline.
+	_ = tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Unprepare this status with ID.
+		tt.UnprepareByStatusIDs(meta.ID)
+
+		// Check the item is unprepared.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value.prepared)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Unprepare this status with boost ID.
+		tt.UnprepareByStatusIDs(meta.BoostOfID)
+
+		// Check the item is unprepared.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value.prepared)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Unprepare this status with account ID.
+		tt.UnprepareByAccountIDs(meta.AccountID)
+
+		// Check the item is unprepared.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value.prepared)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Unprepare this status with boost account ID.
+		tt.UnprepareByAccountIDs(meta.BoostOfAccountID)
+
+		// Check the item is unprepared.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value.prepared)
+	}
+}
+
+func TestStatusTimelineRemove(t *testing.T) {
+	var tt StatusTimeline
+	tt.Init(1000)
+
+	// Clone the input test status data.
+	data := slices.Clone(testStatusMeta)
+
+	// Insert test data into timeline.
+	_ = tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Remove this status with ID.
+		tt.RemoveByStatusIDs(meta.ID)
+
+		// Check the item is now gone.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Remove this status with boost ID.
+		tt.RemoveByStatusIDs(meta.BoostOfID)
+
+		// Check the item is now gone.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Remove this status with account ID.
+		tt.RemoveByAccountIDs(meta.AccountID)
+
+		// Check the item is now gone.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value)
+	}
+
+	// Clear and reinsert.
+	tt.cache.Clear()
+	tt.cache.Insert(data...)
+
+	for _, meta := range data {
+		// Remove this status with boost account ID.
+		tt.RemoveByAccountIDs(meta.BoostOfAccountID)
+
+		// Check the item is now gone.
+		value := getStatusByID(&tt, meta.ID)
+		assert.Nil(t, value)
+	}
+}
+
+func TestStatusTimelineInserts(t *testing.T) {
+	var tt StatusTimeline
+	tt.Init(1000)
+
+	// Clone the input test status data.
+	data := slices.Clone(testStatusMeta)
+
+	// Insert test data into timeline.
+	l := tt.cache.Insert(data...)
+	assert.Equal(t, len(data), l)
+
+	// Ensure 'min' value status
+	// in the timeline is expected.
+	minID := minStatusID(data)
+	assert.Equal(t, minID, minStatus(&tt).ID)
+
+	// Ensure 'max' value status
+	// in the timeline is expected.
+	maxID := maxStatusID(data)
+	assert.Equal(t, maxID, maxStatus(&tt).ID)
+
+	// Manually mark timeline as 'preloaded'.
+	tt.preloader.CheckPreload(tt.preloader.Done)
+
+	// Specifically craft a boost of latest (i.e. max) status in timeline.
+	boost := &gtsmodel.Status{ID: "06B1A00PQWDZZH9WK9P5VND35C", BoostOfID: maxID}
+
+	// Insert boost into the timeline
+	// checking for 'repeatBoost' notifier.
+	repeatBoost := tt.InsertOne(boost, nil)
+	assert.True(t, repeatBoost)
+
+	// This should be the new 'max'
+	// and have 'repeatBoost' set.
+	newMax := maxStatus(&tt)
+	assert.Equal(t, boost.ID, newMax.ID)
+	assert.True(t, newMax.repeatBoost)
+
+	// Specifically craft 2 boosts of some unseen status in the timeline.
+	boost1 := &gtsmodel.Status{ID: "06B1A121YEX02S0AY48X93JMDW", BoostOfID: "unseen"}
+	boost2 := &gtsmodel.Status{ID: "06B1A12TG2NTJC9P270EQXS08M", BoostOfID: "unseen"}
+
+	// Insert boosts into the timeline, ensuring
+	// first is not 'repeat', but second one is.
+	repeatBoost1 := tt.InsertOne(boost1, nil)
+	repeatBoost2 := tt.InsertOne(boost2, nil)
+	assert.False(t, repeatBoost1)
+	assert.True(t, repeatBoost2)
+}
+
+func TestStatusTimelineTrim(t *testing.T) {
+	var tt StatusTimeline
+	tt.Init(1000)
+
+	// Clone the input test status data.
+	data := slices.Clone(testStatusMeta)
+
+	// Insert test data into timeline.
+	_ = tt.cache.Insert(data...)
+
+	// From here it'll be easier to have DESC sorted
+	// test data for reslicing and checking against.
+	slices.SortFunc(data, func(a, b *StatusMeta) int {
+		const k = +1
+		switch {
+		case a.ID < b.ID:
+			return +k
+		case b.ID < a.ID:
+			return -k
+		default:
+			return 0
+		}
+	})
+
+	// Set manual cutoff for trim.
+	tt.cut = len(data) - 1
+
+	// Perform trim.
+	tt.Trim()
+
+	// The post trim length should be tt.cut
+	assert.Equal(t, tt.cut, tt.cache.Len())
+
+	// It specifically should have removed
+	// the oldest (i.e. min) status element.
+	minID := data[len(data)-1].ID
+	assert.NotEqual(t, minID, minStatus(&tt).ID)
+	assert.False(t, containsStatusID(&tt, minID))
+
+	// Drop trimmed status.
+	data = data[:len(data)-1]
+
+	// Set smaller cutoff for trim.
+	tt.cut = len(data) - 2
+
+	// Perform trim.
+	tt.Trim()
+
+	// The post trim length should be tt.cut
+	assert.Equal(t, tt.cut, tt.cache.Len())
+
+	// It specifically should have removed
+	// the oldest 2 (i.e. min) status elements.
+	minID1 := data[len(data)-1].ID
+	minID2 := data[len(data)-2].ID
+	assert.NotEqual(t, minID1, minStatus(&tt).ID)
+	assert.NotEqual(t, minID2, minStatus(&tt).ID)
+	assert.False(t, containsStatusID(&tt, minID1))
+	assert.False(t, containsStatusID(&tt, minID2))
+
+	// Trim at desired length
+	// should cause no change.
+	before := tt.cache.Len()
+	tt.Trim()
+	assert.Equal(t, before, tt.cache.Len())
+}
+
+// containsStatusID returns whether timeline contains a status with ID.
+func containsStatusID(t *StatusTimeline, id string) bool {
+	return getStatusByID(t, id) != nil
+}
+
+// getStatusByID attempts to fetch status with given ID from timeline.
+func getStatusByID(t *StatusTimeline, id string) *StatusMeta {
+	for _, value := range t.cache.Range(structr.Desc) {
+		if value.ID == id {
+			return value
+		}
+	}
+	return nil
+}
+
+// maxStatus returns the newest (i.e. highest value ID) status in timeline.
+func maxStatus(t *StatusTimeline) *StatusMeta {
+	var meta *StatusMeta
+	for _, value := range t.cache.Range(structr.Desc) {
+		meta = value
+		break
+	}
+	return meta
+}
+
+// minStatus returns the oldest (i.e. lowest value ID) status in timeline.
+func minStatus(t *StatusTimeline) *StatusMeta {
+	var meta *StatusMeta
+	for _, value := range t.cache.Range(structr.Asc) {
+		meta = value
+		break
+	}
+	return meta
+}
+
+// minStatusID returns the oldest (i.e. lowest value ID) status in metas.
+func minStatusID(metas []*StatusMeta) string {
+	var min string
+	min = metas[0].ID
+	for i := 1; i < len(metas); i++ {
+		if metas[i].ID < min {
+			min = metas[i].ID
+		}
+	}
+	return min
+}
+
+// maxStatusID returns the newest (i.e. highest value ID) status in metas.
+func maxStatusID(metas []*StatusMeta) string {
+	var max string
+	max = metas[0].ID
+	for i := 1; i < len(metas); i++ {
+		if metas[i].ID > max {
+			max = metas[i].ID
+		}
+	}
+	return max
+}