merge.go (3160 bytes)
1 package main 2 3 import ( 4 "regexp" 5 "strings" 6 ) 7 8 var scheme = regexp.MustCompile(`^[A-Za-z][A-Za-z0-9+.-]*://`) 9 10 // norm gives the form of a URL that bm uses to find duplicates: two URLs are 11 // the same bookmark when they differ only in scheme, a leading "www.", 12 // trailing slashes or the case of the host. 13 func norm(u string) string { 14 u = scheme.ReplaceAllString(u, "") 15 host, rest := u, "" 16 if i := strings.IndexByte(u, '/'); i >= 0 { 17 host, rest = u[:i], u[i:] 18 } 19 host = strings.TrimPrefix(strings.ToLower(host), "www.") 20 return host + strings.TrimRight(rest, "/") 21 } 22 23 // key gives the bookmark that a line holds: the normal form of its URL, the 24 // first field. Comments and empty lines hold no bookmark and give "". 25 func key(line string) string { 26 if strings.TrimSpace(line) == "" || strings.HasPrefix(line, "#") { 27 return "" 28 } 29 u, _, _ := strings.Cut(line, "\t") 30 return norm(u) 31 } 32 33 // lines splits a file into lines without their ends. CRLF counts as LF. 34 func lines(text string) []string { 35 text = strings.ReplaceAll(text, "\r\n", "\n") 36 if text == "" { 37 return nil 38 } 39 return strings.Split(strings.TrimSuffix(text, "\n"), "\n") 40 } 41 42 // join is the reverse of lines: each line ends with LF. 43 func join(ls []string) string { 44 if len(ls) == 0 { 45 return "" 46 } 47 return strings.Join(ls, "\n") + "\n" 48 } 49 50 func set(ls []string) map[string]bool { 51 m := make(map[string]bool, len(ls)) 52 for _, l := range ls { 53 m[l] = true 54 } 55 return m 56 } 57 58 // merge combines two versions of a bookmark file that both come from base: 59 // local, which a device sends, and remote, which the server holds. 60 // 61 // The result is remote with the changes that local made since base. A line 62 // that local removed goes. A line that local added comes in: at the end, 63 // where bm adds bookmarks, or in the place of the remote line for the same 64 // bookmark, so that an edit on the device wins. Lines are compared whole. 65 // When base is unknown, pass "": nothing is removed, and the result is the 66 // union of both files. 67 func merge(base, local, remote string) string { 68 b := set(lines(base)) 69 l := lines(local) 70 inLocal := set(l) 71 r := lines(remote) 72 inRemote := set(r) 73 74 var added []string 75 first := map[string]int{} // key of an added line: its index in added 76 for _, x := range l { 77 if b[x] { 78 continue 79 } 80 if k := key(x); k != "" { 81 if _, ok := first[k]; !ok { 82 first[k] = len(added) 83 } 84 } 85 added = append(added, x) 86 } 87 used := make([]bool, len(added)) 88 89 // replacement gives the added line that takes the place of x, if any. 90 replacement := func(x string) (string, bool) { 91 k := key(x) 92 if k == "" { 93 return "", false 94 } 95 i, ok := first[k] 96 if !ok || used[i] || inRemote[added[i]] { 97 return "", false 98 } 99 used[i] = true 100 return added[i], true 101 } 102 103 var out []string 104 for _, x := range r { 105 if inLocal[x] { 106 out = append(out, x) 107 continue 108 } 109 // Local does not have x: local removed or changed it since base, or 110 // x is new on the server. 111 if y, ok := replacement(x); ok { 112 out = append(out, y) 113 } else if !b[x] { 114 out = append(out, x) 115 } 116 } 117 for i, y := range added { 118 if !used[i] && !inRemote[y] { 119 out = append(out, y) 120 } 121 } 122 return join(out) 123 }