Open-source AI browser agent for Chrome and Firefox (monorepo) ðŸ§
JavaScript ai-agentai-agentsai-toolsbrowser-aibrowser-automationbrowser-extensionchrome-aichrome-devtoolschrome-extensionchrome-extensionsfirefox-addonfirefox-addonsfirefox-extensionfirefox-extensionsgemmagemma4minimaxoffline-aioffline-llmqwen
package d1
// Byte-level BPE matching Hugging Face tokenizers / Transformers.js for the
// d1 (LFM2.5) tokenizer.json: added-token splitting, the Llama-3 style split
// regex, GPT-2 byte mapping and rank-ordered merges.
import (
"container/heap"
"encoding/json"
"errors"
"fmt"
"os"
"sort"
"strings"
"sync"
"github.com/dlclark/regexp2"
)
type addedToken struct {
ID int `json:"id"`
Content string `json:"content"`
Special bool `json:"special"`
}
type Tokenizer struct {
vocab map[string]int
ranks map[string]int
added []addedToken // longest first
addedBy map[string]int
split *regexp2.Regexp
byteEnc [256]string
cacheMu sync.Mutex
cache map[string][]int
BosID int
PadID int
}
// JavaScript's \s (what Transformers.js' RegExp uses), spelled out so the
// .NET-flavoured engine matches the browser exactly.
var jsSpace = jsSpaceClass()
// jsSpaceClass spells JavaScript's \s as regexp escapes (built at run time so
// the source stays ASCII).
func jsSpaceClass() string {
var b strings.Builder
b.WriteString(`\t\n\v\f\r `)
esc := func(cp int) { fmt.Fprintf(&b, "\\%s%04x", "u", cp) }
for _, cp := range []int{0x00a0, 0x1680} {
esc(cp)
}
esc(0x2000)
b.WriteByte('-')
esc(0x200a)
for _, cp := range []int{0x2028, 0x2029, 0x202f, 0x205f, 0x3000, 0xfeff} {
esc(cp)
}
return b.String()
}
func bytesToUnicode() [256]string {
var bs []int
for b := '!'; b <= '~'; b++ {
bs = append(bs, int(b))
}
for b := 0xA1; b <= 0xAC; b++ {
bs = append(bs, b)
}
for b := 0xAE; b <= 0xFF; b++ {
bs = append(bs, b)
}
cs := append([]int(nil), bs...)
n := 0
in := map[int]bool{}
for _, b := range bs {
in[b] = true
}
for b := 0; b < 256; b++ {
if !in[b] {
bs = append(bs, b)
cs = append(cs, 256+n)
n++
}
}
var out [256]string
for i, b := range bs {
out[b] = string(rune(cs[i]))
}
return out
}
// LoadTokenizer reads a tokenizer.json of the d1 family.
func LoadTokenizer(path string) (*Tokenizer, error) {
data, err := os.ReadFile(path)
if err != nil {
return nil, err
}
var raw struct {
AddedTokens []addedToken `json:"added_tokens"`
PreTok struct {
Type string `json:"type"`
Pretokenizers []struct {
Type string `json:"type"`
Pattern struct {
Regex string `json:"Regex"`
} `json:"pattern"`
} `json:"pretokenizers"`
} `json:"pre_tokenizer"`
Model struct {
Type string `json:"type"`
Vocab map[string]int `json:"vocab"`
Merges []json.RawMessage `json:"merges"`
} `json:"model"`
}
if err := json.Unmarshal(data, &raw); err != nil {
return nil, fmt.Errorf("tokenizer.json: %w", err)
}
if raw.Model.Type != "BPE" {
return nil, fmt.Errorf("unsupported tokenizer model %q", raw.Model.Type)
}
t := &Tokenizer{vocab: raw.Model.Vocab, ranks: make(map[string]int, len(raw.Model.Merges)),
addedBy: map[string]int{}, cache: map[string][]int{}, byteEnc: bytesToUnicode()}
for i, m := range raw.Model.Merges {
var pair []string
if err := json.Unmarshal(m, &pair); err != nil {
var s string
if err := json.Unmarshal(m, &s); err != nil {
return nil, errors.New("bad merge entry")
}
pair = strings.SplitN(s, " ", 2)
}
if len(pair) != 2 {
return nil, errors.New("bad merge entry")
}
key := pair[0] + "\x00" + pair[1]
if _, ok := t.ranks[key]; !ok {
t.ranks[key] = i
}
}
for _, a := range raw.AddedTokens {
t.added = append(t.added, a)
t.addedBy[a.Content] = a.ID
}
sort.SliceStable(t.added, func(i, j int) bool { return len(t.added[i].Content) > len(t.added[j].Content) })
pattern := `(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\r\n\p{L}\p{N}]?\p{L}+|\p{N}{1,3}| ?[^\p{L}\p{N}` + jsSpace + `]+[\r\n]*|[` + jsSpace + `]*[\r\n]+|[` + jsSpace + `]+(?![^` + jsSpace + `])|[` + jsSpace + `]+`
for _, p := range raw.PreTok.Pretokenizers {
if p.Type == "Split" && p.Pattern.Regex != "" && !strings.Contains(p.Pattern.Regex, `(?i:'s|'t|'re|'ve|'m|'ll|'d)`) {
return nil, errors.New("unexpected pre-tokenizer pattern")
}
}
t.split, err = regexp2.Compile(pattern, regexp2.Unicode)
if err != nil {
return nil, err
}
t.split.MatchTimeout = 0
t.BosID = t.ID("<|startoftext|>")
t.PadID = t.ID("<|pad|>")
return t, nil
}
// ID returns a token's id (added tokens first), or -1.
func (t *Tokenizer) ID(token string) int {
if id, ok := t.addedBy[token]; ok {
return id
}
if id, ok := t.vocab[token]; ok {
return id
}
return -1
}
// Encode tokenizes text without adding special tokens.
func (t *Tokenizer) Encode(text string) []int {
var out []int
for len(text) > 0 {
pos, tok := t.nextAdded(text)
if pos < 0 {
out = append(out, t.encodePlain(text)...)
break
}
if pos > 0 {
out = append(out, t.encodePlain(text[:pos])...)
}
out = append(out, tok.ID)
text = text[pos+len(tok.Content):]
}
return out
}
// nextAdded finds the leftmost added token (longest at that position).
func (t *Tokenizer) nextAdded(text string) (int, addedToken) {
best := -1
var bestTok addedToken
for _, a := range t.added {
i := strings.Index(text, a.Content)
if i < 0 {
continue
}
if best < 0 || i < best || (i == best && len(a.Content) > len(bestTok.Content)) {
best, bestTok = i, a
}
}
return best, bestTok
}
func (t *Tokenizer) encodePlain(text string) []int {
runes := []rune(text)
var out []int
last := 0
m, _ := t.split.FindRunesMatch(runes)
for m != nil {
if m.Index > last {
out = append(out, t.bpeWord(string(runes[last:m.Index]))...)
}
out = append(out, t.bpeWord(string(runes[m.Index:m.Index+m.Length]))...)
last = m.Index + m.Length
m, _ = t.split.FindNextMatch(m)
}
if last < len(runes) {
out = append(out, t.bpeWord(string(runes[last:]))...)
}
return out
}
type mergeCand struct {
rank, pos int
left string
right string
}
type mergeHeap []mergeCand
func (h mergeHeap) Len() int { return len(h) }
func (h mergeHeap) Less(i, j int) bool {
if h[i].rank != h[j].rank {
return h[i].rank < h[j].rank
}
return h[i].pos < h[j].pos
}
func (h mergeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *mergeHeap) Push(x any) { *h = append(*h, x.(mergeCand)) }
func (h *mergeHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func (t *Tokenizer) bpeWord(piece string) []int {
if piece == "" {
return nil
}
t.cacheMu.Lock()
if ids, ok := t.cache[piece]; ok {
t.cacheMu.Unlock()
return ids
}
t.cacheMu.Unlock()
syms := make([]string, 0, len(piece))
for i := 0; i < len(piece); i++ {
syms = append(syms, t.byteEnc[piece[i]])
}
// Linked list over symbol slots.
n := len(syms)
prev := make([]int, n)
next := make([]int, n)
alive := make([]bool, n)
for i := range syms {
prev[i], next[i], alive[i] = i-1, i+1, true
}
next[n-1] = -1
h := &mergeHeap{}
push := func(i int) {
if i < 0 || !alive[i] || next[i] < 0 {
return
}
j := next[i]
if r, ok := t.ranks[syms[i]+"\x00"+syms[j]]; ok {
heap.Push(h, mergeCand{rank: r, pos: i, left: syms[i], right: syms[j]})
}
}
for i := 0; i < n-1; i++ {
push(i)
}
for h.Len() > 0 {
c := heap.Pop(h).(mergeCand)
i := c.pos
if !alive[i] || next[i] < 0 || syms[i] != c.left || syms[next[i]] != c.right {
continue
}
j := next[i]
syms[i] = c.left + c.right
alive[j] = false
next[i] = next[j]
if next[j] >= 0 {
prev[next[j]] = i
}
push(prev[i])
push(i)
}
var ids []int
for i := 0; i >= 0; i = next[i] {
if !alive[i] {
continue
}
if id, ok := t.vocab[syms[i]]; ok {
ids = append(ids, id)
}
}
if len(piece) < 256 {
t.cacheMu.Lock()
if len(t.cache) > 50000 {
t.cache = map[string][]int{}
}
t.cache[piece] = ids
t.cacheMu.Unlock()
}
return ids
}