Typeahead autocomplete

<?php

declare(strict_types=1);

final readonly class AutocompleteRequest
{
    public function __construct(
        public string $query,
        public string $context = 'web',
        public string $lang = 'en',
        public int $limit = 10,
        public ?string $userId = null,
    ) {}
}

final readonly class Suggestion
{
    public function __construct(
        public string $text,
        public float $score,
        public ?string $highlight = null,
        public ?string $type = null, // query|entity|shortcut
    ) {}
}

final readonly class AutocompleteResponse
{
    /**
     * @param list<Suggestion> $suggestions
     */
    public function __construct(
        public array $suggestions,
        public int $tookMicros,
        public string $version,
    ) {}
}

package api

type AutocompleteRequest struct {
    Query   string `json:"q"`
    Context string `json:"ctx,omitempty"`
    Lang    string `json:"lang,omitempty"`
    Limit   int    `json:"limit,omitempty"`
    UserID  string `json:"user_id,omitempty"`
}

type Suggestion struct {
    Text      string  `json:"text"`
    Score     float64 `json:"score"`
    Highlight string  `json:"highlight,omitempty"`
    Type      string  `json:"type,omitempty"`
}

type AutocompleteResponse struct {
    Suggestions []Suggestion `json:"suggestions"`
    TookMicros  int64        `json:"took_us"`
    Version     string       `json:"version"`
}

using System.Text.Json.Serialization;

namespace Autocomplete.Api;

public sealed record AutocompleteRequest(
    [property: JsonPropertyName("q")] string Query,
    [property: JsonPropertyName("ctx")] string Context = "web",
    [property: JsonPropertyName("lang")] string Lang = "en",
    [property: JsonPropertyName("limit")] int Limit = 10,
    [property: JsonPropertyName("user_id")] string? UserId = null);

public sealed record Suggestion(
    [property: JsonPropertyName("text")] string Text,
    [property: JsonPropertyName("score")] double Score,
    [property: JsonPropertyName("highlight")] string? Highlight = null,
    [property: JsonPropertyName("type")] string? Type = null); // query|entity|shortcut

public sealed record AutocompleteResponse(
    [property: JsonPropertyName("suggestions")] IReadOnlyList<Suggestion> Suggestions,
    [property: JsonPropertyName("took_us")] long TookMicros,
    [property: JsonPropertyName("version")] string Version);

from dataclasses import dataclass, field

@dataclass(frozen=True, slots=True)
class AutocompleteRequest:
    query: str
    context: str = "web"
    lang: str = "en"
    limit: int = 10
    user_id: str | None = None

@dataclass(frozen=True, slots=True)
class Suggestion:
    text: str
    score: float
    highlight: str | None = None
    type: str | None = None  # query|entity|shortcut

@dataclass(frozen=True, slots=True)
class AutocompleteResponse:
    suggestions: list[Suggestion] = field(default_factory=list)
    took_micros: int = 0
    version: str = "v1"

package trie

import (
    "sort"
    "sync/atomic"
)

// TopK is a precomputed slice of top suggestions under a node.
type Suggestion struct {
    Text  string
    Score float64
}

type node struct {
    children map[byte]*node
    topK     []Suggestion // size == K, sorted DESC by score
}

// Trie is an immutable snapshot. Writers build a new tree and atomically
// swap the pointer (RCU pattern), readers never block.
type Trie struct {
    root    *node
    topK    int
}

// Snapshot is an atomic pointer to the current Trie.
type Snapshot struct {
    current atomic.Pointer[Trie]
}

// Load returns the current trie; always non-nil after init.
func (s *Snapshot) Load() *Trie { return s.current.Load() }

// Swap replaces the active trie atomically. Old trie can be GC-ed once
// all in-flight readers are done.
func (s *Snapshot) Swap(t *Trie) { s.current.Store(t) }

// Search returns precomputed top-K under the given prefix.
func (t *Trie) Search(prefix string, k int) []Suggestion {
    n := t.root
    for i := 0; i < len(prefix); i++ {
        c, ok := n.children[prefix[i]]
        if !ok {
            return nil
        }
        n = c
    }
    if k >= len(n.topK) {
        return n.topK
    }
    return n.topK[:k]
}

// Build constructs a trie from a dictionary of (text -> score) pairs and
// precomputes top-K at every node. Done offline, then hot-swapped.
func Build(dict map[string]float64, topK int) *Trie {
    t := &Trie{root: &node{children: map[byte]*node{}}, topK: topK}
    type entry struct {
        text  string
        score float64
    }
    items := make([]entry, 0, len(dict))
    for k, v := range dict {
        items = append(items, entry{k, v})
    }
    // Sort DESC so we propagate top scores first.
    sort.Slice(items, func(i, j int) bool { return items[i].score > items[j].score })

    for _, e := range items {
        n := t.root
        for i := 0; i < len(e.text); i++ {
            c := e.text[i]
            child, ok := n.children[c]
            if !ok {
                child = &node{children: map[byte]*node{}}
                n.children[c] = child
            }
            n = child
            // Only append if topK not full (items are sorted DESC, so we
            // never need to re-sort at this node).
            if len(n.topK) < topK {
                n.topK = append(n.topK, Suggestion{Text: e.text, Score: e.score})
            }
        }
    }
    return t
}

using System.Threading;

namespace Autocomplete.Trie;

// TopK is a precomputed list of top suggestions under a node.
public readonly record struct Suggestion(string Text, double Score);

// Children are keyed by char (UTF-16 code unit), not by byte as in Go:
// that keeps the walk correct for non-ASCII prefixes without extra decoding.
internal sealed class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = [];
    public List<Suggestion> TopK { get; } = []; // size <= K, sorted DESC by score
}

// Trie is an immutable snapshot. Writers build a new tree and atomically
// swap the reference (RCU pattern), readers never block.
public sealed class Trie
{
    private readonly TrieNode _root;
    private readonly int _topK;

    private Trie(TrieNode root, int topK) => (_root, _topK) = (root, topK);

    // Search returns precomputed top-K under the given prefix.
    public IReadOnlyList<Suggestion> Search(string prefix, int k)
    {
        var node = _root;
        foreach (var c in prefix)
        {
            if (!node.Children.TryGetValue(c, out var child))
            {
                return [];
            }
            node = child;
        }
        return k >= node.TopK.Count ? node.TopK : node.TopK.GetRange(0, k);
    }

    // Build constructs a trie from a dictionary of (text -> score) pairs and
    // precomputes top-K at every node. Done offline, then hot-swapped.
    public static Trie Build(IReadOnlyDictionary<string, double> dict, int topK)
    {
        var trie = new Trie(new TrieNode(), topK);

        // Negated score turns the min-heap into a max-heap, so entries come
        // out DESC and we never need to re-sort at a node.
        var queue = new PriorityQueue<string, double>(dict.Count);
        foreach (var (text, score) in dict)
        {
            queue.Enqueue(text, -score);
        }

        while (queue.TryDequeue(out var text, out var negScore))
        {
            var node = trie._root;
            foreach (var c in text)
            {
                if (!node.Children.TryGetValue(c, out var child))
                {
                    child = new TrieNode();
                    node.Children[c] = child;
                }
                node = child;
                // Only append while topK is not full (entries arrive DESC).
                if (node.TopK.Count < topK)
                {
                    node.TopK.Add(new Suggestion(text, -negScore));
                }
            }
        }
        return trie;
    }
}

// Snapshot holds the currently served trie. Volatile read/write gives the
// same publish/acquire guarantees as Go's atomic.Pointer.
public sealed class Snapshot
{
    private Trie? _current;

    // Load returns the current trie; always non-null after init.
    public Trie Load() => Volatile.Read(ref _current)
        ?? throw new InvalidOperationException("trie snapshot is not initialized");

    // Swap replaces the active trie atomically. The old trie is collected
    // once all in-flight readers have released it.
    public void Swap(Trie trie) => Volatile.Write(ref _current, trie);
}

from dataclasses import dataclass, field

# TopK is a precomputed list of top suggestions under a node.
@dataclass(frozen=True, slots=True)
class Suggestion:
    text: str
    score: float

@dataclass(slots=True)
class _Node:
    children: dict[str, "_Node"] = field(default_factory=dict)
    top_k: list[Suggestion] = field(default_factory=list)  # size <= K, sorted DESC

class Trie:
    """Immutable snapshot. Writers build a new tree and swap the reference
    (RCU pattern), readers never block."""

    __slots__ = ("_root", "_top_k")

    def __init__(self, root: _Node, top_k: int) -> None:
        self._root = root
        self._top_k = top_k

    def search(self, prefix: str, k: int) -> list[Suggestion]:
        """Return precomputed top-K under the given prefix."""
        node = self._root
        for ch in prefix:
            child = node.children.get(ch)
            if child is None:
                return []
            node = child
        return node.top_k if k >= len(node.top_k) else node.top_k[:k]

    @classmethod
    def build(cls, dictionary: dict[str, float], top_k: int) -> "Trie":
        """Build a trie from (text -> score) pairs, precomputing top-K at every
        node. Done offline, then hot-swapped."""
        root = _Node()
        # Sort DESC so we propagate top scores first.
        for text, score in sorted(dictionary.items(), key=lambda kv: kv[1], reverse=True):
            node = root
            for ch in text:
                child = node.children.get(ch)
                if child is None:
                    child = _Node()
                    node.children[ch] = child
                node = child
                # Only append while top_k is not full (entries are sorted DESC,
                # so we never need to re-sort at this node).
                if len(node.top_k) < top_k:
                    node.top_k.append(Suggestion(text, score))
        return cls(root, top_k)

class Snapshot:
    """Holds the currently served trie. A plain attribute rebind is atomic
    under the GIL, which is enough for the RCU publish here; on free-threaded
    builds the same guarantee comes from the assignment being a single store."""

    __slots__ = ("_current",)

    def __init__(self, trie: Trie) -> None:
        self._current = trie

    def load(self) -> Trie:
        return self._current

    def swap(self, trie: Trie) -> None:
        self._current = trie

<?php

declare(strict_types=1);

final class AutocompleteClient
{
    public function __construct(
        private readonly \GuzzleHttp\Client $http,
        private readonly string $endpoint,
        private readonly \Redis $cache,
        private readonly LoggerInterface $logger,
    ) {}

    public function suggest(string $q, string $ctx, string $lang): AutocompleteResponse
    {
        $q = mb_strtolower(trim($q));
        if ($q === '') {
            return new AutocompleteResponse([], 0, 'v1');
        }

        $cacheKey = "ac:{$lang}:{$ctx}:" . substr($q, 0, 8); // хеш по первым 8 символам
        $cached = $this->cache->get($cacheKey);
        if (is_string($cached)) {
            return $this->decode($cached);
        }

        try {
            $resp = $this->http->get($this->endpoint, [
                'query' => ['q' => $q, 'ctx' => $ctx, 'lang' => $lang, 'limit' => 10],
                'timeout' => 0.05, // 50ms hard timeout
            ]);
            $body = (string) $resp->getBody();
            $this->cache->setex($cacheKey, 60, $body);
            return $this->decode($body);
        } catch (\Throwable $e) {
            $this->logger->warning('autocomplete failed', ['error' => $e->getMessage()]);
            return new AutocompleteResponse([], 0, 'fallback');
        }
    }

    private function decode(string $body): AutocompleteResponse
    {
        $data = json_decode($body, true, flags: JSON_THROW_ON_ERROR);
        $suggestions = array_map(
            fn(array $s) => new Suggestion($s['text'], (float) $s['score']),
            $data['suggestions'] ?? [],
        );
        return new AutocompleteResponse($suggestions, (int) ($data['took_us'] ?? 0), (string) ($data['version'] ?? ''));
    }
}

using System.Text.Json;
using Autocomplete.Api;
using Microsoft.Extensions.Caching.Distributed;
using Microsoft.Extensions.Logging;

namespace Autocomplete.Client;

// HttpClient is injected by IHttpClientFactory with BaseAddress set to the
// autocomplete endpoint, so no URL is hardcoded here.
public sealed class AutocompleteClient(
    HttpClient http,
    IDistributedCache cache,
    ILogger<AutocompleteClient> logger)
{
    private static readonly TimeSpan RequestTimeout = TimeSpan.FromMilliseconds(50);

    private static readonly DistributedCacheEntryOptions CacheOptions = new()
    {
        AbsoluteExpirationRelativeToNow = TimeSpan.FromSeconds(60),
    };

    public async Task<AutocompleteResponse> SuggestAsync(
        string q, string ctx, string lang, CancellationToken ct = default)
    {
        q = q.Trim().ToLowerInvariant();
        if (q.Length == 0)
        {
            return new AutocompleteResponse([], 0, "v1");
        }

        var cacheKey = $"ac:{lang}:{ctx}:{q[..Math.Min(8, q.Length)]}"; // key by first 8 chars
        var cached = await cache.GetStringAsync(cacheKey, ct);
        if (cached is not null)
        {
            return Decode(cached);
        }

        try
        {
            using var cts = CancellationTokenSource.CreateLinkedTokenSource(ct);
            cts.CancelAfter(RequestTimeout); // 50ms hard timeout

            var query = $"?q={Uri.EscapeDataString(q)}&ctx={Uri.EscapeDataString(ctx)}"
                      + $"&lang={Uri.EscapeDataString(lang)}&limit=10";
            var body = await http.GetStringAsync(query, cts.Token);

            await cache.SetStringAsync(cacheKey, body, CacheOptions, ct);
            return Decode(body);
        }
        catch (Exception e) when (e is HttpRequestException or OperationCanceledException or JsonException)
        {
            logger.LogWarning(e, "autocomplete failed");
            return new AutocompleteResponse([], 0, "fallback");
        }
    }

    private static AutocompleteResponse Decode(string body)
        => JsonSerializer.Deserialize<AutocompleteResponse>(body)
           ?? new AutocompleteResponse([], 0, string.Empty);
}

import json
import logging

import httpx
import redis.asyncio as redis

logger = logging.getLogger(__name__)

CACHE_TTL_SECONDS = 60
REQUEST_TIMEOUT_SECONDS = 0.05  # 50ms hard timeout

class AutocompleteClient:
    def __init__(self, http: httpx.AsyncClient, endpoint: str, cache: redis.Redis) -> None:
        self._http = http
        self._endpoint = endpoint
        self._cache = cache

    async def suggest(self, q: str, ctx: str, lang: str) -> AutocompleteResponse:
        q = q.strip().lower()
        if not q:
            return AutocompleteResponse([], 0, "v1")

        cache_key = f"ac:{lang}:{ctx}:{q[:8]}"  # key by first 8 chars
        cached = await self._cache.get(cache_key)
        if cached is not None:
            return self._decode(cached)

        try:
            resp = await self._http.get(
                self._endpoint,
                params={"q": q, "ctx": ctx, "lang": lang, "limit": 10},
                timeout=REQUEST_TIMEOUT_SECONDS,
            )
            resp.raise_for_status()
            body = resp.text
            await self._cache.setex(cache_key, CACHE_TTL_SECONDS, body)
            return self._decode(body)
        except (httpx.HTTPError, json.JSONDecodeError) as exc:
            logger.warning("autocomplete failed", extra={"error": str(exc)})
            return AutocompleteResponse([], 0, "fallback")

    @staticmethod
    def _decode(body: str | bytes) -> AutocompleteResponse:
        data = json.loads(body)
        suggestions = [
            Suggestion(item["text"], float(item["score"]))
            for item in data.get("suggestions", [])
        ]
        return AutocompleteResponse(
            suggestions,
            int(data.get("took_us", 0)),
            str(data.get("version", "")),
        )