1// Copyright 2018 Keybase Inc. All rights reserved.
2// Use of this source code is governed by a BSD
3// license that can be found in the LICENSE file.
4
5package kbfsedits
6
7import (
8	"context"
9	"fmt"
10	"sort"
11	"strings"
12	"sync"
13
14	"github.com/keybase/client/go/kbfs/tlf"
15	"github.com/keybase/client/go/libkb"
16	"github.com/keybase/client/go/logger"
17	"github.com/keybase/client/go/protocol/keybase1"
18)
19
20const (
21	// MaxClusters is the max number of TLF writer clusters to return
22	// in a user history.
23	MaxClusters = 10
24
25	// The minimum number of self-clusters that should appear in the
26	// history for the logged-in user.
27	minNumSelfClusters = 3
28)
29
30type tlfKey struct {
31	tlfName tlf.CanonicalName
32	tlfType tlf.Type
33}
34
35// UserHistory keeps a sorted list of the top known TLF edit
36// histories, and can convert those histories into keybase1 protocol
37// structs.  TLF histories must be updated by an external caller
38// whenever they change.
39type UserHistory struct {
40	lock      sync.RWMutex
41	histories map[tlfKey]writersByRevision
42	log       logger.Logger
43	vlog      *libkb.VDebugLog
44}
45
46// NewUserHistory constructs a UserHistory instance.
47func NewUserHistory(log logger.Logger, vlog *libkb.VDebugLog) *UserHistory {
48	return &UserHistory{
49		histories: make(map[tlfKey]writersByRevision),
50		log:       log,
51		vlog:      vlog,
52	}
53}
54
55// UpdateHistory should be called whenever the edit history for a
56// given TLF gets new information.
57func (uh *UserHistory) UpdateHistory(
58	tlfName tlf.CanonicalName, tlfType tlf.Type, tlfHistory *TlfHistory,
59	loggedInUser string) {
60	uh.vlog.CLogf(
61		context.TODO(), libkb.VLog1, "Updating user history for TLF %s, "+
62			"user %s", tlfName, loggedInUser)
63	history := tlfHistory.getHistory(loggedInUser)
64	key := tlfKey{tlfName, tlfType}
65
66	uh.lock.Lock()
67	defer uh.lock.Unlock()
68	uh.histories[key] = history
69}
70
71func (uh *UserHistory) getTlfHistoryLocked(
72	tlfName tlf.CanonicalName, tlfType tlf.Type) (
73	history keybase1.FSFolderEditHistory) {
74	key := tlfKey{tlfName, tlfType}
75	tlfHistory, ok := uh.histories[key]
76	if !ok {
77		return keybase1.FSFolderEditHistory{}
78	}
79
80	folder := keybase1.Folder{
81		Name:       string(tlfName),
82		FolderType: tlfType.FolderType(),
83		Private:    tlfType == tlf.Private,
84	}
85	history.Folder = folder
86	if len(tlfHistory) == 0 {
87		return history
88	}
89	if len(tlfHistory[0].notifications) > 0 {
90		history.ServerTime = keybase1.ToTime(
91			tlfHistory[0].notifications[0].Time)
92		// If there are no notifications (only deletes), leave
93		// `ServerTime` unset.
94	}
95	history.History = make(
96		[]keybase1.FSFolderWriterEditHistory, len(tlfHistory))
97	for i, wn := range tlfHistory {
98		history.History[i].WriterName = wn.writerName
99		history.History[i].Edits = make(
100			[]keybase1.FSFolderWriterEdit, len(wn.notifications))
101		for j, n := range wn.notifications {
102			history.History[i].Edits[j].Filename = n.Filename
103			history.History[i].Edits[j].ServerTime = keybase1.ToTime(n.Time)
104			switch n.Type {
105			case NotificationCreate:
106				history.History[i].Edits[j].NotificationType =
107					keybase1.FSNotificationType_FILE_CREATED
108			case NotificationModify:
109				history.History[i].Edits[j].NotificationType =
110					keybase1.FSNotificationType_FILE_MODIFIED
111			default:
112				panic(fmt.Sprintf("Unknown notification type %s", n.Type))
113			}
114		}
115
116		history.History[i].Deletes = make(
117			[]keybase1.FSFolderWriterEdit, len(wn.deletes))
118		for j, n := range wn.deletes {
119			history.History[i].Deletes[j].Filename = n.Filename
120			history.History[i].Deletes[j].ServerTime = keybase1.ToTime(n.Time)
121			history.History[i].Deletes[j].NotificationType =
122				keybase1.FSNotificationType_FILE_DELETED
123		}
124	}
125	return history
126}
127
128// GetTlfHistory returns the edit history of a given TLF, converted to
129// keybase1 protocol structs.
130func (uh *UserHistory) GetTlfHistory(
131	tlfName tlf.CanonicalName, tlfType tlf.Type) (
132	history keybase1.FSFolderEditHistory) {
133	uh.lock.RLock()
134	defer uh.lock.RUnlock()
135	return uh.getTlfHistoryLocked(tlfName, tlfType)
136}
137
138type historyClusters []keybase1.FSFolderEditHistory
139
140func (hc historyClusters) Len() int {
141	return len(hc)
142}
143
144func (hc historyClusters) Less(i, j int) bool {
145	iTime := hc[i].ServerTime
146	jTime := hc[j].ServerTime
147
148	if iTime == 0 && jTime == 0 {
149		// If both are zero, use the times of the first delete instead.
150		if len(hc[i].History[0].Deletes) > 0 {
151			iTime = hc[i].History[0].Deletes[0].ServerTime
152		}
153		if len(hc[j].History[0].Deletes) > 0 {
154			jTime = hc[j].History[0].Deletes[0].ServerTime
155		}
156	}
157
158	return iTime > jTime
159}
160
161func (hc historyClusters) Swap(i, j int) {
162	hc[i], hc[j] = hc[j], hc[i]
163}
164
165// Get returns the full edit history for the user, converted to
166// keybase1 protocol structs.
167func (uh *UserHistory) Get(loggedInUser string) (
168	history []keybase1.FSFolderEditHistory) {
169	uh.lock.RLock()
170	defer uh.lock.RUnlock()
171	uh.vlog.CLogf(
172		context.TODO(), libkb.VLog1, "User history requested: %s", loggedInUser)
173	var clusters historyClusters
174	for key := range uh.histories {
175		history := uh.getTlfHistoryLocked(key.tlfName, key.tlfType)
176
177		// Only include public TLFs if they match the logged-in user.
178		if history.Folder.FolderType == keybase1.FolderType_PUBLIC {
179			names := strings.Split(history.Folder.Name, ",")
180			match := false
181			for _, name := range names {
182				if name == loggedInUser {
183					match = true
184					break
185				}
186			}
187			if !match {
188				continue
189			}
190		}
191
192		// Break it up into individual clusters
193		for _, wh := range history.History {
194			if len(wh.Edits) > 0 || len(wh.Deletes) > 0 {
195				var serverTime keybase1.Time
196				if len(wh.Edits) > 0 {
197					serverTime = wh.Edits[0].ServerTime
198				}
199				clusters = append(clusters, keybase1.FSFolderEditHistory{
200					Folder:     history.Folder,
201					ServerTime: serverTime,
202					History:    []keybase1.FSFolderWriterEditHistory{wh},
203				})
204			}
205		}
206	}
207
208	// We need to sort these by the ServerTime of these particular edits,
209	// not by the full TLF time.
210	sort.Sort(clusters)
211
212	// TODO: consolidate neighboring clusters that share the same folder?
213	if len(clusters) > MaxClusters {
214		// Find the top self-clusters.
215		loggedInIndices := make([]int, 0, minNumSelfClusters)
216		for i, c := range clusters {
217			if c.History[0].WriterName == loggedInUser {
218				loggedInIndices = append(loggedInIndices, i)
219			}
220			if len(loggedInIndices) == minNumSelfClusters {
221				break
222			}
223		}
224
225		// Move each self-cluster into its rightful spot at the end of
226		// the slice, unless it's already at a lower index.
227		for i, loggedInIndex := range loggedInIndices {
228			newLoggedInIndex := MaxClusters - (len(loggedInIndices) - i)
229			if loggedInIndex < newLoggedInIndex {
230				continue
231			}
232			clusters[newLoggedInIndex] = clusters[loggedInIndex]
233		}
234
235		return clusters[:MaxClusters]
236	}
237	return clusters
238}
239
240// Clear erases all saved histories; TLFs must be re-added.
241func (uh *UserHistory) Clear() {
242	uh.lock.Lock()
243	defer uh.lock.Unlock()
244	uh.histories = make(map[tlfKey]writersByRevision)
245}
246
247// ClearTLF removes a TLF from this UserHistory.
248func (uh *UserHistory) ClearTLF(tlfName tlf.CanonicalName, tlfType tlf.Type) {
249	key := tlfKey{tlfName, tlfType}
250	uh.lock.Lock()
251	defer uh.lock.Unlock()
252	delete(uh.histories, key)
253}
254