Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472//! The people the user writes to and hears from, gathered from the From,//! To, and Cc of the mail parcel reads, for compose to suggest as the//! user types an address. Parcel cannot read Google Contacts: that is//! another scope and another sign-in.//!//! Each person is ranked by the newest few messages they were on, each//! weighed by how the user knows them from it, most for a message the//! user wrote to them, and fading with its age. They are kept between//! runs in the state directory, readable by the user alone.
const std = @import("std");const Settings = @import("Settings.zig");const ascii = std.ascii;const assert = std.debug.assert;const json = std.json;const mem = std.mem;const testing = std.testing;const time = std.time;const Allocator = std.mem.Allocator;const ArenaAllocator = std.heap.ArenaAllocator;const ArrayList = std.ArrayList;const Io = std.Io;const log = std.log.scoped(.contacts);
const Contacts = @This();
pub const file_name = "contacts.json";
/// Changes when the file's shape does; another version is ignored.const version = 1;
/// The most people saved: the best ranked.const max_people = 2000;
/// The messages kept per person to rank them by: the newest.const kept = 8;
const day = time.ms_per_day;
/// A message's weight halves every this many milliseconds.const half_life: f64 = 30 * day;
/// What separates the words of a name or an address, which a query/// matches by their starts.const separators = " \t.,;:@_-+<>\"'()[]/";
/// How the user knows someone from a message.pub const How = enum { /// The user wrote to them: they are in To or Cc of a message the user /// sent. wrote, /// They wrote to the user: From of a message the user got. heard, /// They were in To or Cc of a message the user got. copied,
fn weight(how: How) f64 { return switch (how) { .wrote => 8, .heard => 2, .copied => 1, }; }};
/// A message someone was on, by its date in milliseconds, which tells it/// from their others when it is read again.const Seen = struct { ms: i64, how: How };
const Person = struct { /// Empty when no message named them. name: []const u8, address: []const u8, /// The newest messages they were on, in no order; the first `count` /// hold one. A stdx.buffer.Array once stdx builds on 0.17. seen: [kept]Seen, count: u8,
/// Counts a message once, keeping the newest. Whether it is the /// newest of them. fn add(p: *Person, seen: Seen) bool { var oldest: u8 = 0; var newest = true; for (p.seen[0..p.count], 0..) |*s, i| { if (s.ms == seen.ms) { if (seen.how.weight() > s.how.weight()) s.how = seen.how; return false; } if (s.ms > seen.ms) newest = false; if (s.ms < p.seen[oldest].ms) oldest = @intCast(i); } if (p.count < kept) { p.seen[p.count] = seen; p.count += 1; } else if (seen.ms > p.seen[oldest].ms) { p.seen[oldest] = seen; } else return false; return newest; }
/// The weight of their messages, faded by age as of `now`. Only the /// order of scores matters, which `now` does not change, so it is the /// newest message known, keeping the numbers in range. fn score(p: *const Person, now: i64) f64 { var sum: f64 = 0; for (p.seen[0..p.count]) |s| { const age: f64 = @floatFromInt(now - s.ms); sum += s.how.weight() * @exp2(-age / half_life); } return sum; }
/// Whether every word of `query` starts a word of the name or the /// address, ignoring case; any person matches no words. fn matches(p: *const Person, query: []const u8) bool { var words = mem.tokenizeAny(u8, query, separators); while (words.next()) |word| { if (!startsWord(p.name, word) and !startsWord(p.address, word)) return false; } return true; }};
/// Someone to suggest. Its text lasts as long as the contacts do.pub const Match = struct { name: []const u8, address: []const u8,
/// As an address list holds it: `Ana Lima <ana@example.com>`, the /// name quoted when it holds a comma or another special. pub fn format(m: Match, w: *Io.Writer) Io.Writer.Error!void { if (m.name.len == 0) return w.writeAll(m.address); if (mem.findAny(u8, m.name, "()<>[]:;@\\,.\"") == null) return w.print("{s} <{s}>", .{ m.name, m.address }); try w.writeByte('"'); for (m.name) |c| { if (c == '"' or c == '\\') try w.writeByte('\\'); try w.writeByte(c); } try w.print("\" <{s}>", .{m.address}); }};
gpa: Allocator,/// Holds names and addresses, which are never freed before the contacts/// are, so a Match outlives changes.strings: ArenaAllocator,/// By address, lowercased.people: std.array_hash_map.String(Person),/// Whether they include the mail read before they were kept: they came/// from the file, or Gmail's newest threads were read for them.seeded: bool,/// Whether everyone on the mail kept for search is among them, so the/// corpus need not be read for them again.from_corpus: bool,
pub fn init(gpa: Allocator) Contacts { return .{ .gpa = gpa, .strings = .init(gpa), .people = .empty, .seeded = false, .from_corpus = false };}
pub fn deinit(self: *Contacts) void { self.people.deinit(self.gpa); self.strings.deinit(); self.* = undefined;}
/// Adds the people saved last, if any were.pub fn load(self: *Contacts, settings: Settings) void { const bytes = settings.loadAlloc(file_name, self.gpa, .limited(16 << 20)) orelse return; defer self.gpa.free(bytes); self.parse(bytes) catch |err| return log.warn("{s}: {t}; starting afresh", .{ file_name, err }); self.seeded = true;}
/// Saves the best ranked people, for the user's eyes alone. A failure/// is logged: the next run gathers them again.pub fn save(self: *const Contacts, settings: Settings) void { var arena_state: ArenaAllocator = .init(self.gpa); defer arena_state.deinit(); const bytes = self.serialize(arena_state.allocator()) catch |err| return log.warn("{s}: {t}", .{ file_name, err }); settings.saveSecret(file_name, bytes) catch |err| log.warn("{s}: {t}", .{ file_name, err });}
/// Notes everyone in `header`, an address list such as a From or To/// header's, on a message dated `ms` milliseconds since the epoch.pub fn note(self: *Contacts, how: How, header: []const u8, ms: i64) Allocator.Error!void { var it: Addresses = .{ .rest = header }; while (it.next()) |entry| { const address = mem.trim(u8, bare(entry), " \t"); const lt = mem.findScalar(u8, entry, '<') orelse 0; try self.noteAddress(how, mem.trim(u8, entry[0..lt], " \t\"'"), address, ms); }}
/// Notes `name` at `address` on a message dated `ms` milliseconds since/// the epoch, unless it is no address or a robot's.pub fn noteAddress(self: *Contacts, how: How, name: []const u8, address: []const u8, ms: i64) Allocator.Error!void { if (!isAddress(address) or isRobot(address)) return; try self.notePerson(how, if (ascii.eqlIgnoreCase(name, address)) "" else name, address, ms);}
/// Notes everyone `other` knows, on the messages it knows them from.pub fn absorb(self: *Contacts, other: *const Contacts) Allocator.Error!void { for (other.people.values()) |*p| { for (p.seen[0..p.count]) |s| try self.notePerson(s.how, p.name, p.address, s.ms); }}
/// The best ranked people with a word starting with each word of/// `query`, or any with none, as many as `out` holds, but none an/// address list in `taken` already names.pub fn suggest(self: *const Contacts, out: []Match, query: []const u8, taken: []const []const u8) []Match { var scores: [16]f64 = undefined; assert(out.len <= scores.len); const most: u32 = @intCast(out.len); const now = self.latest(); var n: u32 = 0; next: for (self.people.values()) |*p| { if (!p.matches(query)) continue; for (taken) |list| if (mentions(list, p.address)) continue :next; const s = p.score(now); // Insertion into the few kept, best first. var i = n; while (i > 0 and scores[i - 1] < s) : (i -= 1) { if (i < most) { scores[i] = scores[i - 1]; out[i] = out[i - 1]; } } if (i == most) continue; scores[i] = s; out[i] = .{ .name = p.name, .address = p.address }; n = @min(n + 1, most); } return out[0..n];}
fn notePerson(self: *Contacts, how: How, name: []const u8, address: []const u8, ms: i64) Allocator.Error!void { var key_buf: [254]u8 = undefined; // Longer than an address can be. if (address.len > key_buf.len) return; const key = ascii.lowerString(&key_buf, address); const strings = self.strings.allocator(); const p = self.people.getPtr(key) orelse blk: { const person: Person = .{ .name = "", .address = try strings.dupe(u8, address), .seen = undefined, .count = 0 }; try self.people.put(self.gpa, try strings.dupe(u8, key), person); break :blk self.people.getPtr(key).?; }; const newest_one = p.add(.{ .ms = ms, .how = how }); // The name they went by last. if (name.len > 0 and (newest_one or p.name.len == 0) and !mem.eql(u8, name, p.name)) { p.name = try strings.dupe(u8, name); }}
/// The date of the newest message anyone was on.fn latest(self: *const Contacts) i64 { var ms: i64 = 0; for (self.people.values()) |p| { for (p.seen[0..p.count]) |s| ms = @max(ms, s.ms); } return ms;}
/// The file: everyone kept, with the messages that rank them.const File = struct { version: u32, corpus: bool = false, people: []const Entry,
const Entry = struct { name: []const u8, address: []const u8, seen: []const Seen };};
fn parse(self: *Contacts, bytes: []const u8) !void { var arena_state: ArenaAllocator = .init(self.gpa); defer arena_state.deinit(); const file = try json.parseFromSliceLeaky(File, arena_state.allocator(), bytes, .{ .ignore_unknown_fields = true }); if (file.version != version) return error.OtherVersion; self.from_corpus = file.corpus; for (file.people) |e| { for (e.seen) |s| try self.notePerson(s.how, e.name, e.address, s.ms); }}
fn serialize(self: *const Contacts, arena: Allocator) ![]const u8 { const people = self.people.values(); const order = try arena.alloc(u32, people.len); for (order, 0..) |*o, i| o.* = @intCast(i); const Rank = struct { const Self = @This();
people: []const Person, now: i64,
fn better(r: Self, a: u32, b: u32) bool { return r.people[a].score(r.now) > r.people[b].score(r.now); } }; mem.sort(u32, order, Rank{ .people = people, .now = self.latest() }, Rank.better); const entries = try arena.alloc(File.Entry, @min(order.len, max_people)); for (entries, order[0..entries.len]) |*e, i| { const p = &people[i]; e.* = .{ .name = p.name, .address = p.address, .seen = p.seen[0..p.count] }; } const file: File = .{ .version = version, .corpus = self.from_corpus, .people = entries }; return json.Stringify.valueAlloc(arena, file, .{});}
/// The entries of an address list such as To: "Ana <a@x.org>, b@y.org",/// split at commas outside quotes and angle brackets.pub const Addresses = struct { rest: []const u8,
pub fn next(it: *Addresses) ?[]const u8 { while (it.rest.len > 0) { const end = entryEnd(it.rest); const entry = mem.trim(u8, it.rest[0..end], " \t\r\n"); it.rest = if (end < it.rest.len) it.rest[end + 1 ..] else ""; if (entry.len > 0) return entry; } return null; }};
/// Where the first entry of an address list ends: at its first comma/// outside quotes and angle brackets, or at its end.pub fn entryEnd(list: []const u8) usize { var quoted = false; var angled = false; return for (list, 0..) |c, i| switch (c) { '"' => quoted = !quoted, '<' => angled = true, '>' => angled = false, ',' => if (!quoted and !angled) break i, else => {}, } else list.len;}
/// The address in an entry: what is in angle brackets, or all of it.pub fn bare(entry: []const u8) []const u8 { const lt = mem.findScalar(u8, entry, '<') orelse return entry; const gt = mem.findScalarPos(u8, entry, lt, '>') orelse entry.len; return entry[lt + 1 .. gt];}
/// Whether an address list names `address`.pub fn mentions(list: []const u8, address: []const u8) bool { var it: Addresses = .{ .rest = list }; while (it.next()) |entry| { if (ascii.eqlIgnoreCase(mem.trim(u8, bare(entry), " \t"), address)) return true; } return false;}
fn isAddress(text: []const u8) bool { const at = mem.findScalar(u8, text, '@') orelse return false; return at > 0 and at + 1 < text.len and mem.findAny(u8, text, " \t\"<>,") == null;}
/// Whether an address says not to write to it, as notifications' do.fn isRobot(address: []const u8) bool { const local = address[0 .. mem.findScalar(u8, address, '@') orelse address.len]; const robots = [_][]const u8{ "noreply", "no-reply", "no_reply", "donotreply", "do-not-reply", "notification", "mailer-daemon", }; for (robots) |robot| { if (ascii.findIgnoreCase(local, robot) != null) return true; } return false;}
fn startsWord(text: []const u8, prefix: []const u8) bool { var words = mem.tokenizeAny(u8, text, separators); while (words.next()) |word| { if (ascii.startsWithIgnoreCase(word, prefix)) return true; } return false;}
/// The addresses `query` suggests, best first, as one line in `buf`.fn testAddresses(buf: []u8, out: []Match, contacts: *const Contacts, query: []const u8) ![]const u8 { var w: Io.Writer = .fixed(buf); for (contacts.suggest(out, query, &.{}), 0..) |m, i| { if (i > 0) try w.writeAll(" "); try w.writeAll(m.address); } return w.buffered();}
test "people rank by the messages they were on, those the user wrote to first, newer ahead of older" { var c: Contacts = .init(testing.allocator); defer c.deinit(); const now: i64 = 1_793_836_800_000; // Written to once this week outweighs heard from three times, and // both outweigh copied yesterday, and written to last year. for (0..3) |i| try c.note(.heard, "Mara Lind <mara@example.com>", now - @as(i64, @intCast(i)) * day); try c.note(.wrote, "\"Marc, M.\" <marc@example.com>, nobody", now - 2 * day); try c.note(.wrote, "Matt <matt@example.com>", now - 365 * day); try c.note(.copied, "max@example.com", now - day); var out: [8]Match = undefined; var buf: [256]u8 = undefined; try testing.expectEqualStrings( "marc@example.com mara@example.com max@example.com matt@example.com", try testAddresses(&buf, &out, &c, "ma"), ); // A message read again counts once. for (0..4) |_| try c.note(.copied, "max@example.com", now - day); try testing.expectEqualStrings( "marc@example.com mara@example.com max@example.com matt@example.com", try testAddresses(&buf, &out, &c, "ma"), ); // Only the best fit in a short list. try testing.expectEqualStrings("marc@example.com mara@example.com", try testAddresses(&buf, out[0..2], &c, "ma")); // The name a person went by last stays, quoted as an entry needs it. const marc = c.suggest(out[0..1], "marc", &.{})[0]; try testing.expectEqualStrings("\"Marc, M.\" <marc@example.com>", try mem.print(&buf, "{f}", .{marc}));}
test "a query matches the start of any word of a name or an address, each of its words" { var c: Contacts = .init(testing.allocator); defer c.deinit(); try c.note(.heard, "Lena Fischer <lena.f@example.org>, 'Bo' <bo_smith@work.example>", 0); try c.note(.heard, "GitHub <noreply@github.com>, Alerts <do-not-reply@x.example>", 0); try c.note(.heard, "Lindsay via Todoist <notifications@todoist.com>", 0); try c.note(.copied, "Tim <TIM@example.com>", 0); var out: [8]Match = undefined; var buf: [256]u8 = undefined; try testing.expectEqualStrings("lena.f@example.org", try testAddresses(&buf, &out, &c, "FISCH")); try testing.expectEqualStrings("lena.f@example.org", try testAddresses(&buf, &out, &c, "lena f")); try testing.expectEqualStrings("bo_smith@work.example", try testAddresses(&buf, &out, &c, "smi")); try testing.expectEqualStrings("bo_smith@work.example", try testAddresses(&buf, &out, &c, "work")); // Inside a word is no match, and neither is a word of the query that // starts none. try testing.expectEqualStrings("", try testAddresses(&buf, &out, &c, "ischer")); try testing.expectEqualStrings("", try testAddresses(&buf, &out, &c, "lena x")); // No words is anyone, as search's from: suggests before a letter. try testing.expectEqualStrings( "lena.f@example.org bo_smith@work.example TIM@example.com", try testAddresses(&buf, &out, &c, " "), ); // Notifications are no one to write to. try testing.expectEqualStrings("", try testAddresses(&buf, &out, &c, "git")); try testing.expectEqualStrings("", try testAddresses(&buf, &out, &c, "todoist")); // Nor is the user, nor anyone already on the list. try testing.expectEqual(0, c.suggest(&out, "tim", &.{"tim@example.com"}).len); try testing.expectEqual(0, c.suggest(&out, "lena", &.{ "Bo <x@y.z>, Lena <LENA.F@example.org>", "" }).len);}
test "contacts are saved for the user alone, and read back ranked the same" { var tmp = testing.tmpDir(.{}); defer tmp.cleanup(); const settings: Settings = .{ .io = testing.io, .dir = tmp.dir }; var c: Contacts = .init(testing.allocator); defer c.deinit(); try c.note(.heard, "Ana <ana@example.com>", 5 * day); try c.note(.wrote, "Al \"the\" Pal <al@example.com>", day); c.save(settings); const stat = try tmp.dir.statFile(testing.io, file_name, .{}); try testing.expectEqual(0o600, @backingInt(stat.permissions) & 0o777);
var back: Contacts = .init(testing.allocator); defer back.deinit(); back.load(settings); try testing.expect(back.seeded); var out: [4]Match = undefined; const found = back.suggest(&out, "a", &.{}); try testing.expectEqual(2, found.len); try testing.expectEqualStrings("al@example.com", found[0].address); try testing.expectEqualStrings("Al \"the\" Pal", found[0].name); try testing.expectEqualStrings("Ana", found[1].name);}