commit 6e964f71ff7a0e7e942c8819973e63b4f5193cec
parent 4b7444f33871d1f4869f63a2691f2cc58ec1ef7b
Author: Terry Yiu <git@tyiu.xyz>
Date: Sat, 1 Jul 2023 14:42:36 -0400
Add trie-based user search cache to replace non-performant linear scans
Changelog-Added: Speed up user search
Tested-by: William Casarin <jb55@jb55.com>
Fixes: #1219
Closes: #1342
Diffstat:
13 files changed, 518 insertions(+), 94 deletions(-)
diff --git a/damus.xcodeproj/project.pbxproj b/damus.xcodeproj/project.pbxproj
@@ -20,7 +20,11 @@
3A4325A82961E11400BFCD9D /* Localizable.stringsdict in Resources */ = {isa = PBXBuildFile; fileRef = 3A4325AA2961E11400BFCD9D /* Localizable.stringsdict */; };
3A4647CF2A413ADC00386AD8 /* CondensedProfilePicturesView.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A4647CE2A413ADC00386AD8 /* CondensedProfilePicturesView.swift */; };
3A48E7B029DFBE9D006E787E /* MutedThreadsManager.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A48E7AF29DFBE9D006E787E /* MutedThreadsManager.swift */; };
+ 3A5E47C52A4A6CF400C0D090 /* Trie.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A5E47C42A4A6CF400C0D090 /* Trie.swift */; };
+ 3A5E47C72A4A76C800C0D090 /* TrieTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A5E47C62A4A76C800C0D090 /* TrieTests.swift */; };
3A8CC6CC2A2CFEF900940F5F /* StringUtil.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A8CC6CB2A2CFEF900940F5F /* StringUtil.swift */; };
+ 3A90B1812A4EA3AF00000D94 /* UserSearchCache.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A90B1802A4EA3AF00000D94 /* UserSearchCache.swift */; };
+ 3A90B1832A4EA3C600000D94 /* UserSearchCacheTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3A90B1822A4EA3C600000D94 /* UserSearchCacheTests.swift */; };
3AA247FD297E3CFF0090C62D /* RepostsModel.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3AA247FC297E3CFF0090C62D /* RepostsModel.swift */; };
3AA247FF297E3D900090C62D /* RepostsView.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3AA247FE297E3D900090C62D /* RepostsView.swift */; };
3AA24802297E3DC20090C62D /* RepostView.swift in Sources */ = {isa = PBXBuildFile; fileRef = 3AA24801297E3DC20090C62D /* RepostView.swift */; };
@@ -377,6 +381,8 @@
3A5CAE1D298DC0DB00B5334F /* zh-CN */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = "zh-CN"; path = "zh-CN.lproj/InfoPlist.strings"; sourceTree = "<group>"; };
3A5CAE1E298DC0DB00B5334F /* zh-CN */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = "zh-CN"; path = "zh-CN.lproj/Localizable.strings"; sourceTree = "<group>"; };
3A5CAE1F298DC0DB00B5334F /* zh-CN */ = {isa = PBXFileReference; lastKnownFileType = text.plist.stringsdict; name = "zh-CN"; path = "zh-CN.lproj/Localizable.stringsdict"; sourceTree = "<group>"; };
+ 3A5E47C42A4A6CF400C0D090 /* Trie.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = Trie.swift; sourceTree = "<group>"; };
+ 3A5E47C62A4A76C800C0D090 /* TrieTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = TrieTests.swift; sourceTree = "<group>"; };
3A66D927299472FA008B44F4 /* ja */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = ja; path = ja.lproj/InfoPlist.strings; sourceTree = "<group>"; };
3A66D928299472FA008B44F4 /* ja */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = ja; path = ja.lproj/Localizable.strings; sourceTree = "<group>"; };
3A66D929299472FA008B44F4 /* ja */ = {isa = PBXFileReference; lastKnownFileType = text.plist.stringsdict; name = ja; path = ja.lproj/Localizable.stringsdict; sourceTree = "<group>"; };
@@ -390,6 +396,8 @@
3A8624DA299E82BE00BD8BE9 /* cs */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = cs; path = cs.lproj/Localizable.strings; sourceTree = "<group>"; };
3A8624DB299E82BE00BD8BE9 /* cs */ = {isa = PBXFileReference; lastKnownFileType = text.plist.stringsdict; name = cs; path = cs.lproj/Localizable.stringsdict; sourceTree = "<group>"; };
3A8CC6CB2A2CFEF900940F5F /* StringUtil.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = StringUtil.swift; sourceTree = "<group>"; };
+ 3A90B1802A4EA3AF00000D94 /* UserSearchCache.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = UserSearchCache.swift; sourceTree = "<group>"; };
+ 3A90B1822A4EA3C600000D94 /* UserSearchCacheTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = UserSearchCacheTests.swift; sourceTree = "<group>"; };
3A929C20297F2CF80090925E /* it-IT */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = "it-IT"; path = "it-IT.lproj/InfoPlist.strings"; sourceTree = "<group>"; };
3A929C21297F2CF80090925E /* it-IT */ = {isa = PBXFileReference; lastKnownFileType = text.plist.strings; name = "it-IT"; path = "it-IT.lproj/Localizable.strings"; sourceTree = "<group>"; };
3A929C22297F2CF80090925E /* it-IT */ = {isa = PBXFileReference; lastKnownFileType = text.plist.stringsdict; name = "it-IT"; path = "it-IT.lproj/Localizable.stringsdict"; sourceTree = "<group>"; };
@@ -921,6 +929,8 @@
3A48E7AF29DFBE9D006E787E /* MutedThreadsManager.swift */,
4C7D09772A0B0CC900943473 /* WalletModel.swift */,
3A23838D2A297DD200E5AA2E /* ZapButtonModel.swift */,
+ 3A5E47C42A4A6CF400C0D090 /* Trie.swift */,
+ 3A90B1802A4EA3AF00000D94 /* UserSearchCache.swift */,
);
path = Models;
sourceTree = "<group>";
@@ -1379,6 +1389,8 @@
4C8D00D329E3C5D40036AF10 /* NIP19Tests.swift */,
501F8C812A0224EB001AFC1D /* KeychainStorageTests.swift */,
3AFBF3FC29FDA7CC00E79C7C /* CustomZapViewTests.swift */,
+ 3A5E47C62A4A76C800C0D090 /* TrieTests.swift */,
+ 3A90B1822A4EA3C600000D94 /* UserSearchCacheTests.swift */,
);
path = damusTests;
sourceTree = "<group>";
@@ -1731,6 +1743,7 @@
4C3D52B8298DB5C6001C5831 /* TextEvent.swift in Sources */,
4C216F362870A9A700040376 /* InputDismissKeyboard.swift in Sources */,
4C8D1A6F29F31E5000ACDF75 /* FriendsButton.swift in Sources */,
+ 3A5E47C52A4A6CF400C0D090 /* Trie.swift in Sources */,
4C216F382871EDE300040376 /* DirectMessageModel.swift in Sources */,
4C75EFA627FF87A20006080F /* Nostr.swift in Sources */,
4CB883A62975F83C00DC99E7 /* LNUrlPayRequest.swift in Sources */,
@@ -1867,6 +1880,7 @@
4C8EC52529D1FA6C0085D9A8 /* DamusColors.swift in Sources */,
3A4647CF2A413ADC00386AD8 /* CondensedProfilePicturesView.swift in Sources */,
D2277EEA2A089BD5006C3807 /* Router.swift in Sources */,
+ 3A90B1812A4EA3AF00000D94 /* UserSearchCache.swift in Sources */,
4C5C7E6A284EDE2E00A22DF5 /* SearchResultsView.swift in Sources */,
4CE1399429F0669900AC6A0B /* BigButton.swift in Sources */,
7C60CAEF298471A1009C80D6 /* CoreSVG.swift in Sources */,
@@ -1958,6 +1972,7 @@
buildActionMask = 2147483647;
files = (
5019CADD2A0FB0A9000069E1 /* ProfileDatabaseTests.swift in Sources */,
+ 3A90B1832A4EA3C600000D94 /* UserSearchCacheTests.swift in Sources */,
3A3040ED29A5CB86008A0F29 /* ReplyDescriptionTests.swift in Sources */,
4C8D00D429E3C5D40036AF10 /* NIP19Tests.swift in Sources */,
3A30410129AB12AA008A0F29 /* EventGroupViewTests.swift in Sources */,
@@ -1972,6 +1987,7 @@
4CB883AA297612FF00DC99E7 /* ZapTests.swift in Sources */,
4CB8839A297322D200DC99E7 /* DMTests.swift in Sources */,
F944F56E29EA9CCC0067B3BF /* DamusParseContentTests.swift in Sources */,
+ 3A5E47C72A4A76C800C0D090 /* TrieTests.swift in Sources */,
4CB883AE2976FA9300DC99E7 /* FormatTests.swift in Sources */,
4C363AA02828A8DD006E126D /* LikeTests.swift in Sources */,
4C90BD1C283AC38E008EE7EF /* Bech32Tests.swift in Sources */,
diff --git a/damus/ContentView.swift b/damus/ContentView.swift
@@ -624,13 +624,14 @@ struct ContentView: View {
let nwc = WalletConnectURL(str: nwc_str) {
try? pool.add_relay(.nwc(url: nwc.relay))
}
-
+
+ let user_search_cache = UserSearchCache()
self.damus_state = DamusState(pool: pool,
keypair: keypair,
likes: EventCounter(our_pubkey: pubkey),
boosts: EventCounter(our_pubkey: pubkey),
contacts: Contacts(our_pubkey: pubkey),
- profiles: Profiles(),
+ profiles: Profiles(user_search_cache: user_search_cache),
dms: home.dms,
previews: PreviewCache(),
zaps: Zaps(our_pubkey: pubkey),
@@ -646,7 +647,8 @@ struct ContentView: View {
replies: ReplyCounter(our_pubkey: pubkey),
muted_threads: MutedThreadsManager(keypair: keypair),
wallet: WalletModel(settings: settings),
- nav: self.navigationCoordinator
+ nav: self.navigationCoordinator,
+ user_search_cache: user_search_cache
)
home.damus_state = self.damus_state!
@@ -876,17 +878,18 @@ func handle_unfollow(state: DamusState, notif: Notification) {
let target = notif.object as! FollowTarget
let pk = target.pubkey
+ let old_contacts = state.contacts.event
if let ev = unfollow_user(postbox: state.postbox,
- our_contacts: state.contacts.event,
+ our_contacts: old_contacts,
pubkey: state.pubkey,
privkey: privkey,
unfollow: pk) {
notify(.unfollowed, pk)
-
+
state.contacts.event = ev
state.contacts.remove_friend(pk)
- //friend_events = friend_events.filter { $0.pubkey != pk }
+ state.user_search_cache.updateOwnContactsPetnames(id: state.pubkey, oldEvent: old_contacts, newEvent: ev)
}
}
diff --git a/damus/Models/DamusState.swift b/damus/Models/DamusState.swift
@@ -31,6 +31,7 @@ struct DamusState {
let muted_threads: MutedThreadsManager
let wallet: WalletModel
let nav: NavigationCoordinator
+ let user_search_cache: UserSearchCache
@discardableResult
func add_zap(zap: Zapping) -> Bool {
@@ -58,5 +59,6 @@ struct DamusState {
}
static var empty: DamusState {
- return DamusState.init(pool: RelayPool(), keypair: Keypair(pubkey: "", privkey: ""), likes: EventCounter(our_pubkey: ""), boosts: EventCounter(our_pubkey: ""), contacts: Contacts(our_pubkey: ""), profiles: Profiles(), dms: DirectMessagesModel(our_pubkey: ""), previews: PreviewCache(), zaps: Zaps(our_pubkey: ""), lnurls: LNUrls(), settings: UserSettingsStore(), relay_filters: RelayFilters(our_pubkey: ""), relay_metadata: RelayMetadatas(), drafts: Drafts(), events: EventCache(), bookmarks: BookmarksManager(pubkey: ""), postbox: PostBox(pool: RelayPool()), bootstrap_relays: [], replies: ReplyCounter(our_pubkey: ""), muted_threads: MutedThreadsManager(keypair: Keypair(pubkey: "", privkey: nil)), wallet: WalletModel(settings: UserSettingsStore()), nav: NavigationCoordinator()) }
+ let user_search_cache = UserSearchCache()
+ return DamusState.init(pool: RelayPool(), keypair: Keypair(pubkey: "", privkey: ""), likes: EventCounter(our_pubkey: ""), boosts: EventCounter(our_pubkey: ""), contacts: Contacts(our_pubkey: ""), profiles: Profiles(user_search_cache: user_search_cache), dms: DirectMessagesModel(our_pubkey: ""), previews: PreviewCache(), zaps: Zaps(our_pubkey: ""), lnurls: LNUrls(), settings: UserSettingsStore(), relay_filters: RelayFilters(our_pubkey: ""), relay_metadata: RelayMetadatas(), drafts: Drafts(), events: EventCache(), bookmarks: BookmarksManager(pubkey: ""), postbox: PostBox(pool: RelayPool()), bootstrap_relays: [], replies: ReplyCounter(our_pubkey: ""), muted_threads: MutedThreadsManager(keypair: Keypair(pubkey: "", privkey: nil)), wallet: WalletModel(settings: UserSettingsStore()), nav: NavigationCoordinator(), user_search_cache: user_search_cache) }
}
diff --git a/damus/Models/HomeModel.swift b/damus/Models/HomeModel.swift
@@ -612,7 +612,8 @@ func add_contact_if_friend(contacts: Contacts, ev: NostrEvent) {
contacts.add_friend_contact(ev)
}
-func load_our_contacts(contacts: Contacts, m_old_ev: NostrEvent?, ev: NostrEvent) {
+func load_our_contacts(state: DamusState, m_old_ev: NostrEvent?, ev: NostrEvent) {
+ let contacts = state.contacts
var new_pks = Set<String>()
// our contacts
for tag in ev.tags {
@@ -641,6 +642,8 @@ func load_our_contacts(contacts: Contacts, m_old_ev: NostrEvent?, ev: NostrEvent
contacts.remove_friend(pk)
}
}
+
+ state.user_search_cache.updateOwnContactsPetnames(id: contacts.our_pubkey, oldEvent: m_old_ev, newEvent: ev)
}
@@ -701,7 +704,9 @@ func process_metadata_profile(our_pubkey: String, profiles: Profiles, profile: P
}
var old_nip05: String? = nil
- if let mprof = profiles.lookup_with_timestamp(id: ev.pubkey) {
+ let mprof = profiles.lookup_with_timestamp(id: ev.pubkey)
+
+ if let mprof {
old_nip05 = mprof.profile.nip05
if mprof.event.created_at > ev.created_at {
// skip if we already have an newer profile
@@ -810,7 +815,7 @@ func load_our_stuff(state: DamusState, ev: NostrEvent) {
let m_old_ev = state.contacts.event
state.contacts.event = ev
- load_our_contacts(contacts: state.contacts, m_old_ev: m_old_ev, ev: ev)
+ load_our_contacts(state: state, m_old_ev: m_old_ev, ev: ev)
load_our_relays(state: state, m_old_ev: m_old_ev, ev: ev)
}
diff --git a/damus/Models/Trie.swift b/damus/Models/Trie.swift
@@ -0,0 +1,129 @@
+//
+// Trie.swift
+// damus
+//
+// Created by Terry Yiu on 6/26/23.
+//
+
+import Foundation
+
+/// Tree data structure of all the substring permutations of a collection of strings optimized for searching for values of type V.
+///
+/// Each node in the tree can have child nodes.
+/// Each node represents a single character in substrings, and each of its child nodes represent the subsequent character in those substrings.
+///
+/// A node that has no children mean that there are no substrings with any additional characters beyond the branch of letters leading up to that node.
+///
+/// A node that has values mean that there are strings that end in the character represented by the node and contain the substring represented by the branch of letters leading up to that node.
+///
+/// https://en.wikipedia.org/wiki/Trie
+class Trie<V: Hashable> {
+ private var children: [Character : Trie] = [:]
+
+ /// Separate exact matches from strict substrings so that exact matches appear first in returned results.
+ private var exactMatchValues = Set<V>()
+ private var substringMatchValues = Set<V>()
+
+ private var parent: Trie? = nil
+}
+
+extension Trie {
+ var hasChildren: Bool {
+ return !self.children.isEmpty
+ }
+
+ var hasValues: Bool {
+ return !self.exactMatchValues.isEmpty || !self.substringMatchValues.isEmpty
+ }
+
+ /// Finds the branch that matches the specified key and returns the values from all of its descendant nodes.
+ func find(key: String) -> [V] {
+ var currentNode = self
+
+ // Find branch with matching prefix.
+ for char in key {
+ if let child = currentNode.children[char] {
+ currentNode = child
+ } else {
+ return []
+ }
+ }
+
+ // Perform breadth-first search from matching branch and collect values from all descendants.
+ var exactMatches = Set<V>()
+ var substringMatches = Set<V>()
+ var queue = [currentNode]
+
+ while !queue.isEmpty {
+ let node = queue.removeFirst()
+ exactMatches.formUnion(node.exactMatchValues)
+ substringMatches.formUnion(node.substringMatchValues)
+ queue.append(contentsOf: node.children.values)
+ }
+
+ return Array(exactMatches) + substringMatches
+ }
+
+ /// Inserts value of type V into this trie for the specified key. This function stores all substring endings of the key, not only the key itself.
+ /// Runtime performance is O(n^2) and storage cost is O(n), where n is the number of characters in the key.
+ func insert(key: String, value: V) {
+ // Create root branches for each character of the key to enable substring searches instead of only just prefix searches.
+ // Hence the nested loop.
+ for i in 0..<key.count {
+ var currentNode = self
+
+ // Find branch with matching prefix.
+ for char in key[key.index(key.startIndex, offsetBy: i)...] {
+ if let child = currentNode.children[char] {
+ currentNode = child
+ } else {
+ let child = Trie()
+ child.parent = currentNode
+ currentNode.children[char] = child
+ currentNode = child
+ }
+ }
+
+ if i == 0 {
+ currentNode.exactMatchValues.insert(value)
+ } else {
+ currentNode.substringMatchValues.insert(value)
+ }
+ }
+ }
+
+ /// Removes value of type V from this trie for the specified key.
+ func remove(key: String, value: V) {
+ for i in 0..<key.count {
+ var currentNode = self
+
+ var foundLeafNode = true
+
+ // Find branch with matching prefix.
+ for j in i..<key.count {
+ let char = key[key.index(key.startIndex, offsetBy: j)]
+
+ if let child = currentNode.children[char] {
+ currentNode = child
+ } else {
+ foundLeafNode = false
+ break
+ }
+ }
+
+ if foundLeafNode {
+ currentNode.exactMatchValues.remove(value)
+ currentNode.substringMatchValues.remove(value)
+
+ // Clean up the tree if this leaf node no longer holds values or children.
+ for j in (i..<key.count).reversed() {
+ if let parent = currentNode.parent, !currentNode.hasValues && !currentNode.hasChildren {
+ currentNode = parent
+ let char = key[key.index(key.startIndex, offsetBy: j)]
+ currentNode.children.removeValue(forKey: char)
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/damus/Models/UserSearchCache.swift b/damus/Models/UserSearchCache.swift
@@ -0,0 +1,107 @@
+//
+// UserSearchCache.swift
+// damus
+//
+// Created by Terry Yiu on 6/27/23.
+//
+
+import Foundation
+
+/// Cache of searchable users by name, display_name, NIP-05 identifier, or own contact list petname.
+/// Optimized for fast searches of substrings by using a Trie.
+/// Optimal for performing user searches that could be initiated by typing quickly on a keyboard into a text input field.
+class UserSearchCache {
+ private let trie = Trie<String>()
+
+ func search(key: String) -> [String] {
+ let results = trie.find(key: key)
+ return results
+ }
+
+ /// Computes the differences between an old profile, if it exists, and a new profile, and updates the user search cache accordingly.
+ func updateProfile(id: String, profiles: Profiles, oldProfile: Profile?, newProfile: Profile) {
+ // Remove searchable keys tied to the old profile if they differ from the new profile
+ // to keep the trie clean without empty nodes while avoiding excessive graph searching.
+ if let oldProfile {
+ if let oldName = oldProfile.name, newProfile.name?.caseInsensitiveCompare(oldName) != .orderedSame {
+ trie.remove(key: oldName.lowercased(), value: id)
+ }
+ if let oldDisplayName = oldProfile.display_name, newProfile.display_name?.caseInsensitiveCompare(oldDisplayName) != .orderedSame {
+ trie.remove(key: oldDisplayName.lowercased(), value: id)
+ }
+ if let oldNip05 = oldProfile.nip05, newProfile.nip05?.caseInsensitiveCompare(oldNip05) != .orderedSame {
+ trie.remove(key: oldNip05.lowercased(), value: id)
+ }
+ }
+
+ addProfile(id: id, profiles: profiles, profile: newProfile)
+ }
+
+ /// Adds a profile to the user search cache.
+ private func addProfile(id: String, profiles: Profiles, profile: Profile) {
+ // Searchable by name.
+ if let name = profile.name {
+ trie.insert(key: name.lowercased(), value: id)
+ }
+
+ // Searchable by display name.
+ if let displayName = profile.display_name {
+ trie.insert(key: displayName.lowercased(), value: id)
+ }
+
+ // Searchable by NIP-05 identifier.
+ if let nip05 = profiles.is_validated(id) {
+ trie.insert(key: "\(nip05.username.lowercased())@\(nip05.host.lowercased())", value: id)
+ }
+ }
+
+ /// Computes the diffences between an old contacts event and a new contacts event for our own user, and updates the search cache accordingly.
+ func updateOwnContactsPetnames(id: String, oldEvent: NostrEvent?, newEvent: NostrEvent) {
+ guard newEvent.known_kind == .contacts && newEvent.pubkey == id else {
+ return
+ }
+
+ var petnames: [String: String] = [:]
+
+ // Gets all petnames from our new contacts list.
+ newEvent.tags.forEach { tag in
+ guard tag.count >= 4 && tag[0] == "p" else {
+ return
+ }
+
+ let pubkey = tag[1]
+ let petname = tag[3]
+
+ petnames[pubkey] = petname
+ }
+
+ // Compute the diff with the old contacts list, if it exists,
+ // mark the ones that are the same to not be removed from the user search cache,
+ // and remove the old ones that are different from the user search cache.
+ if let oldEvent, oldEvent.known_kind == .contacts && oldEvent.pubkey == id {
+ oldEvent.tags.forEach { tag in
+ guard tag.count >= 4 && tag[0] == "p" else {
+ return
+ }
+
+ let pubkey = tag[1]
+ let oldPetname = tag[3]
+
+ if let newPetname = petnames[pubkey] {
+ if newPetname.caseInsensitiveCompare(oldPetname) == .orderedSame {
+ petnames.removeValue(forKey: pubkey)
+ } else {
+ trie.remove(key: oldPetname, value: pubkey)
+ }
+ } else {
+ trie.remove(key: oldPetname, value: pubkey)
+ }
+ }
+ }
+
+ // Add the new petnames to the user search cache.
+ for (pubkey, petname) in petnames {
+ trie.insert(key: petname, value: pubkey)
+ }
+ }
+}
diff --git a/damus/Nostr/Profiles.swift b/damus/Nostr/Profiles.swift
@@ -23,6 +23,12 @@ class Profiles {
var zappers: [String: String] = [:]
private let database = ProfileDatabase()
+
+ let user_search_cache: UserSearchCache
+
+ init(user_search_cache: UserSearchCache) {
+ self.user_search_cache = user_search_cache
+ }
func is_validated(_ pk: String) -> NIP05? {
validated[pk]
@@ -40,7 +46,9 @@ class Profiles {
func add(id: String, profile: TimestampedProfile) {
queue.async(flags: .barrier) {
+ let old_timestamped_profile = self.profiles[id]
self.profiles[id] = profile
+ self.user_search_cache.updateProfile(id: id, profiles: self, oldProfile: old_timestamped_profile?.profile, newProfile: profile.profile)
}
Task {
diff --git a/damus/Views/Posting/UserSearch.swift b/damus/Views/Posting/UserSearch.swift
@@ -8,7 +8,6 @@
import SwiftUI
struct SearchedUser: Identifiable {
- let petname: String?
let profile: Profile?
let pubkey: String
@@ -28,11 +27,7 @@ struct UserSearch: View {
@EnvironmentObject var tagModel: TagModel
var users: [SearchedUser] {
- guard let contacts = damus_state.contacts.event else {
- return search_profiles(profiles: damus_state.profiles, search: search)
- }
-
- return search_users_for_autocomplete(profiles: damus_state.profiles, tags: contacts.tags, search: search)
+ return search_profiles(profiles: damus_state.profiles, search: search)
}
func on_user_tapped(user: SearchedUser) {
@@ -99,56 +94,6 @@ struct UserSearch_Previews: PreviewProvider {
}
}
-
-func search_users_for_autocomplete(profiles: Profiles, tags: [[String]], search _search: String) -> [SearchedUser] {
- var seen_user = Set<String>()
- let search = _search.lowercased()
-
- var matches = tags.reduce(into: Array<SearchedUser>()) { arr, tag in
- guard tag.count >= 2 && tag[0] == "p" else {
- return
- }
-
- let pubkey = tag[1]
- guard !seen_user.contains(pubkey) else {
- return
- }
- seen_user.insert(pubkey)
-
- var petname: String? = nil
- if tag.count >= 4 {
- petname = tag[3]
- }
-
- let profile = profiles.lookup(id: pubkey)
-
- guard ((petname?.lowercased().hasPrefix(search) ?? false) ||
- (profile?.name?.lowercased().hasPrefix(search) ?? false) ||
- (profile?.display_name?.lowercased().hasPrefix(search) ?? false)) else {
- return
- }
-
- let searched_user = SearchedUser(petname: petname, profile: profile, pubkey: pubkey)
- arr.append(searched_user)
- }
-
- // search profile cache as well
- for tup in profiles.enumerated() {
- let pk = tup.element.key
- let prof = tup.element.value.profile
-
- guard !seen_user.contains(pk) else {
- continue
- }
-
- if let match = profile_search_matches(profiles: profiles, profile: prof, pubkey: pk, search: search) {
- matches.append(match)
- }
- }
-
- return matches
-}
-
func user_tag_attr_string(profile: Profile?, pubkey: String) -> NSMutableAttributedString {
let display_name = Profile.displayName(profile: profile, pubkey: pubkey)
let name = display_name.username.truncate(maxLength: 50)
diff --git a/damus/Views/Profile/ProfilePicView.swift b/damus/Views/Profile/ProfilePicView.swift
@@ -162,7 +162,8 @@ func get_profile_url(picture: String?, pubkey: String, profiles: Profiles) -> UR
}
func make_preview_profiles(_ pubkey: String) -> Profiles {
- let profiles = Profiles()
+ let user_search_cache = UserSearchCache()
+ let profiles = Profiles(user_search_cache: user_search_cache)
let picture = "http://cdn.jb55.com/img/red-me.jpg"
let profile = Profile(name: "jb55", display_name: "William Casarin", about: "It's me", picture: picture, banner: "", website: "https://jb55.com", lud06: nil, lud16: nil, nip05: "jb55.com", damus_donation: nil)
let ts_profile = TimestampedProfile(profile: profile, timestamp: 0, event: test_event)
diff --git a/damus/Views/SearchResultsView.swift b/damus/Views/SearchResultsView.swift
@@ -180,33 +180,21 @@ func make_hashtagable(_ str: String) -> String {
}
func search_profiles(profiles: Profiles, search: String) -> [SearchedUser] {
- let new = search.lowercased()
- return profiles.enumerated().reduce(into: []) { acc, els in
- let pk = els.element.key
- let prof = els.element.value.profile
-
- if let searched = profile_search_matches(profiles: profiles, profile: prof, pubkey: pk, search: new) {
- acc.append(searched)
- }
+ // Search by hex pubkey.
+ if search.count == 64 && hex_decode(search) != nil, let profile = profiles.lookup(id: search) {
+ return [SearchedUser(profile: profile, pubkey: search)]
}
-}
-
-func profile_search_matches(profiles: Profiles, profile prof: Profile, pubkey pk: String, search new: String) -> SearchedUser? {
- let lowname = prof.name.map { $0.lowercased() }
- let lownip05 = profiles.is_validated(pk).map { $0.host.lowercased() }
- let lowdisp = prof.display_name.map { $0.lowercased() }
- let ok = new.count == 1 ?
- ((lowname?.starts(with: new) ?? false) ||
- (lownip05?.starts(with: new) ?? false) ||
- (lowdisp?.starts(with: new) ?? false)) : (pk.starts(with: new) || String(new.dropFirst()) == pk
- || lowname?.contains(new) ?? false
- || lownip05?.contains(new) ?? false
- || lowdisp?.contains(new) ?? false)
-
- if ok {
- return SearchedUser(petname: nil, profile: prof, pubkey: pk)
+ // Search by npub pubkey.
+ if search.starts(with: "npub"), let bech32_key = decode_bech32_key(search), case Bech32Key.pub(let hex) = bech32_key, let profile = profiles.lookup(id: hex) {
+ return [SearchedUser(profile: profile, pubkey: hex)]
}
-
- return nil
+
+ let new = search.lowercased()
+ let matched_pubkeys = profiles.user_search_cache.search(key: new)
+
+ return matched_pubkeys
+ .map { ($0, profiles.lookup(id: $0)) }
+ .filter { $1 != nil }
+ .map { SearchedUser(profile: $1, pubkey: $0) }
}
diff --git a/damusTests/TrieTests.swift b/damusTests/TrieTests.swift
@@ -0,0 +1,79 @@
+//
+// TrieTests.swift
+// damusTests
+//
+// Created by Terry Yiu on 6/26/23.
+//
+
+import XCTest
+@testable import damus
+
+final class TrieTests: XCTestCase {
+
+ func testFind() throws {
+ let trie = Trie<String>()
+
+ let keys = ["foobar", "food", "foo", "somethingelse", "duplicate", "duplicate"]
+ keys.forEach {
+ trie.insert(key: $0, value: $0)
+ }
+
+ let allResults = trie.find(key: "")
+ XCTAssertEqual(Set(allResults), Set(["foobar", "food", "foo", "somethingelse", "duplicate"]))
+
+ let fooResults = trie.find(key: "foo")
+ XCTAssertEqual(fooResults.first, "foo")
+ XCTAssertEqual(Set(fooResults), Set(["foobar", "food", "foo"]))
+
+ let foodResults = trie.find(key: "food")
+ XCTAssertEqual(foodResults, ["food"])
+
+ let ooResults = trie.find(key: "oo")
+ XCTAssertEqual(Set(ooResults), Set(["foobar", "food", "foo"]))
+
+ let aResults = trie.find(key: "a")
+ XCTAssertEqual(Set(aResults), Set(["foobar", "duplicate"]))
+
+ let notFoundResults = trie.find(key: "notfound")
+ XCTAssertEqual(notFoundResults, [])
+
+ // Sanity check that the root node has children.
+ XCTAssertTrue(trie.hasChildren)
+
+ // Sanity check that the root node has no values.
+ XCTAssertFalse(trie.hasValues)
+ }
+
+ func testRemove() {
+ let trie = Trie<String>()
+
+ let keys = ["foobar", "food", "foo", "somethingelse", "duplicate", "duplicate"]
+ keys.forEach {
+ trie.insert(key: $0, value: $0)
+ }
+
+ keys.forEach {
+ trie.remove(key: $0, value: $0)
+ }
+
+ let allResults = trie.find(key: "")
+ XCTAssertTrue(allResults.isEmpty)
+
+ let fooResults = trie.find(key: "foo")
+ XCTAssertTrue(fooResults.isEmpty)
+
+ let foodResults = trie.find(key: "food")
+ XCTAssertTrue(foodResults.isEmpty)
+
+ let ooResults = trie.find(key: "oo")
+ XCTAssertTrue(ooResults.isEmpty)
+
+ let aResults = trie.find(key: "a")
+ XCTAssertTrue(aResults.isEmpty)
+
+ // Verify that removal of values from all the keys that were inserted in the trie previously also resulted in the cleanup of the trie.
+ XCTAssertFalse(trie.hasChildren)
+ XCTAssertFalse(trie.hasValues)
+ }
+
+}
diff --git a/damusTests/UserSearchCacheTests.swift b/damusTests/UserSearchCacheTests.swift
@@ -0,0 +1,141 @@
+//
+// UserSearchCacheTests.swift
+// damusTests
+//
+// Created by Terry Yiu on 6/30/23.
+//
+
+import XCTest
+@testable import damus
+
+final class UserSearchCacheTests: XCTestCase {
+
+ var keypair: Keypair? = nil
+ let damusState = DamusState.empty
+ let nip05 = "_@somedomain.com"
+
+ override func setUpWithError() throws {
+ keypair = try XCTUnwrap(generate_new_keypair())
+
+ if let keypair {
+ let pubkey = keypair.pubkey
+
+ damusState.profiles.validated[pubkey] = NIP05.parse(nip05)
+
+ let profile = Profile(name: "tyiu", display_name: "Terry Yiu", about: nil, picture: nil, banner: nil, website: nil, lud06: nil, lud16: nil, nip05: nip05, damus_donation: nil)
+ let timestampedProfile = TimestampedProfile(profile: profile, timestamp: 0, event: test_event)
+ damusState.profiles.add(id: pubkey, profile: timestampedProfile)
+
+ // Lookup to synchronize access on profiles dictionary to avoid race conditions.
+ let _ = damusState.profiles.lookup(id: pubkey)
+ }
+ }
+
+ override func tearDown() {
+ keypair = nil
+ }
+
+ func testSearch() throws {
+ let keypair = try XCTUnwrap(keypair)
+ XCTAssertEqual(damusState.user_search_cache.search(key: "tyiu"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "ty"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "terry yiu"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "rry"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "somedomain"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "dom"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "i"), [keypair.pubkey])
+ }
+
+ func testUpdateProfile() throws {
+ let keypair = try XCTUnwrap(keypair)
+
+ let newNip05 = "_@other.xyz"
+ damusState.profiles.validated[keypair.pubkey] = NIP05.parse(newNip05)
+
+ let newProfile = Profile(name: "whoami", display_name: "T-DAWG", about: nil, picture: nil, banner: nil, website: nil, lud06: nil, lud16: nil, nip05: newNip05, damus_donation: nil)
+ let newTimestampedProfile = TimestampedProfile(profile: newProfile, timestamp: 1000, event: test_event)
+ damusState.profiles.add(id: keypair.pubkey, profile: newTimestampedProfile)
+
+ // Lookup to synchronize access on profiles dictionary to avoid race conditions.
+ let _ = damusState.profiles.lookup(id: keypair.pubkey)
+
+ // Old profile attributes are removed from cache.
+ XCTAssertEqual(damusState.user_search_cache.search(key: "tyiu"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "ty"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "Terry Yiu"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "rry"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "somedomain"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "dom"), [])
+
+ // New profile attributes are added to cache.
+ XCTAssertEqual(damusState.user_search_cache.search(key: "whoami"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "hoa"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "t-dawg"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "daw"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "other"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "xyz"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "the"), [keypair.pubkey])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "y"), [keypair.pubkey])
+ }
+
+ func testUpdateOwnContactsPetnames() throws {
+ let keypair = try XCTUnwrap(keypair)
+ let damus = "3efdaebb1d8923ebd99c9e7ace3b4194ab45512e2be79c1b7d68d9243e0d2681"
+ let jb55 = "32e1827635450ebb3c5a7d12c1f8e7b2b514439ac10a67eef3d9fd9c5c68e245"
+
+ var pubkeysToPetnames = [String: String]()
+ pubkeysToPetnames[damus] = "damus"
+ pubkeysToPetnames[jb55] = "jb55"
+
+ let contactsEvent = try createContactsEventWithPetnames(pubkeysToPetnames: pubkeysToPetnames)
+
+ // Initial own contacts event caching on searchable petnames.
+ damusState.user_search_cache.updateOwnContactsPetnames(id: keypair.pubkey, oldEvent: nil, newEvent: contactsEvent)
+
+ XCTAssertEqual(damusState.user_search_cache.search(key: "damus"), [damus])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "jb55"), [jb55])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "5"), [jb55])
+
+ // Replace one of the petnames and verify if the cache updates accordingly.
+
+ pubkeysToPetnames.removeValue(forKey: jb55)
+ pubkeysToPetnames[jb55] = "bill"
+ let newContactsEvent = try createContactsEventWithPetnames(pubkeysToPetnames: pubkeysToPetnames)
+
+ damusState.user_search_cache.updateOwnContactsPetnames(id: keypair.pubkey, oldEvent: contactsEvent, newEvent: newContactsEvent)
+
+ XCTAssertEqual(damusState.user_search_cache.search(key: "damus"), [damus])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "jb55"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "5"), [])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "bill"), [jb55])
+ XCTAssertEqual(damusState.user_search_cache.search(key: "l"), [jb55])
+ }
+
+ private func createContactsEventWithPetnames(pubkeysToPetnames: [String: String]) throws -> NostrEvent {
+ let keypair = try XCTUnwrap(keypair)
+ let privkey = try XCTUnwrap(keypair.privkey)
+
+ let bootstrapRelays = load_bootstrap_relays(pubkey: keypair.pubkey)
+ let relayInfo = RelayInfo(read: true, write: true)
+ var relays: [String: RelayInfo] = [:]
+
+ for relay in bootstrapRelays {
+ relays[relay] = relayInfo
+ }
+
+ let relayJson = encode_json(relays)!
+
+ let tags = pubkeysToPetnames.enumerated().map {
+ ["p", $0.element.key, "", $0.element.value]
+ }
+
+ let ev = NostrEvent(content: relayJson,
+ pubkey: keypair.pubkey,
+ kind: NostrKind.contacts.rawValue,
+ tags: tags)
+ ev.calculate_id()
+ ev.sign(privkey: privkey)
+ return ev
+ }
+
+}
diff --git a/damusTests/ZapTests.swift b/damusTests/ZapTests.swift
@@ -69,7 +69,7 @@ final class ZapTests: XCTestCase {
XCTAssertEqual(zap.target, ZapTarget.profile("32e1827635450ebb3c5a7d12c1f8e7b2b514439ac10a67eef3d9fd9c5c68e245"))
XCTAssertEqual(zap_notification_title(zap), "Zap")
- XCTAssertEqual(zap_notification_body(profiles: Profiles(), zap: zap), "You received 1k sats from 107jk7ht:2qlu3nfm")
+ XCTAssertEqual(zap_notification_body(profiles: Profiles(user_search_cache: UserSearchCache()), zap: zap), "You received 1k sats from 107jk7ht:2qlu3nfm")
}
}
