tea_dom_search

# The whole io surface of the panel: one call which splits the static search
# index from the small model that crosses the wire on every event.
#
# `serve_with_state` roots that index in the guest after init. On wasm each
# request enters `main` afresh, but the root belongs to the module instance and
# is therefore still present when the next independent `dawn_turn` arrives.
#
#   $ echo '{"op":"init","flags":"{\"root\":\".\",\"index\":{\"v\":1,\
#       \"lang\":\"en\",\"items\":[]}}"}' | dawn run examples/projects/tea_dom_search

use tea_dom/reactor.{serve_with_state}
use search.{init, encode, decode, update, view, supplied, absorb}

pub fn main() -> Unit !io = serve_with_state(init, encode, decode, update, view, Some(supplied), Some(absorb))

# The pure half of the site's search panel: an index, a query, a selection,
# and the tree those three make. No io, no wire format, no page.
#
# What makes it worth writing in Dawn rather than in the page's own script is
# the three shapes it is built out of, each of which the language has and a
# hand-rolled accumulator does not.
#
#   nested collectors   The result list is grouped, so the view is a collector
#                       inside a collector: [sections] installs one for the
#                       sections and [rows_of] installs another for the rows
#                       of one group, and the inner installation shadows the
#                       outer one for the length of its body. What crosses
#                       from inner to outer is the finished `<li>`, never its
#                       rows. Both are conditional -- a group with no hits
#                       emits nothing at all rather than an empty section --
#                       which is the thing a list of slots cannot express.
#
#   two state cells     [scan] carries `hits` and `chosen` in one
#                       `with handle`. They are not the same quantity: the
#                       first is every match in display order, numbered, the
#                       second is the href the selection lands on, and it is
#                       decided by comparing the running ordinal with the
#                       selection at the moment the match is found. Nothing
#                       outside the arm can see the ordinal.
#
#   a reader effect     Every link this view builds needs the page's distance
#                       from the site root, and every label needs its
#                       language. Both are retained fields read at the leaves,
#                       nine calls below the state. `Ctx` is installed once at
#                       the top of `view` and asked at the bottom, which is
#                       two parameters that no function in between has to
#                       carry or forward.
#
# The index arrives as flags -- one string the page has and the guest does not
# -- and is split from the mutable model at init. `serve_with_state` roots that
# read-only value inside the guest, so only query/selection/open/navigation and
# the ids of the current hits cross the wire on a keystroke. A wasm call enters
# main afresh, but the root's lifetime is the module instance rather than that
# one call.
#
# The ranking runs in `update`, once per change of the query, and its answer is
# a field of the model. A turn computes `view` twice (the old tree to route the
# event, the new one to diff against), and a typed character is two turns, its
# `keydown` and its `input`: when the ranking lived in `view` (and `pressed`
# ranked again to find the last row), a character walked the whole index five
# times and an arrow key three. Now a character walks it once and an arrow key
# not at all. The index is lowercased and split into words once, at init, for
# the same reason.
#
# The tree is a WAI-ARIA combobox: the field controls a listbox of groups of
# options, and an option's id is its ordinal, so `aria-activedescendant` is a
# function of the model and needs no lookup in the tree. What a dialog owes
# the rest of the document -- the scrim, focus kept inside and handed back,
# the selected row scrolled into view -- the guest cannot reach, and
# site/assets/search.js does it.
#
# Before anything is typed the list is not empty: it holds the reader's own
# recent queries and three places the site suggests starting from, and the
# arrows, Enter and the pointer move through those exactly as through
# results. The recent queries live in the page's localStorage, which the
# guest cannot reach; they arrive as flags, read-only, and the guest never
# writes them. Its delete and Clear buttons carry the query in a `data-`
# attribute instead of a listener, and the page script does the forgetting
# and starts the panel again from the new list (site/assets/search.js says
# why that and not a message back in). A shared `?q=` link arrives the same
# way: the query is a flag, and init answers its hits in the first turn. The
# link is made the same way too: the foot's Copy link button, there while the
# field holds a query, names itself in a `data-` attribute, and the page
# writes the address and fills the clipboard ([copy_link]).
#
# The documents' text is a second index, fetched the first time the reader
# types (search-body-<lang>.json, docs/site-search-design.md). It reaches the
# guest the way everything else read-only does: the page starts the panel
# again with it in the flags, and init keeps it beside the titles. A section
# whose text answers is one more row in its document's group, under every
# title that answered, with the paragraph that answered best as its excerpt;
# the hit is still one integer in the model ([body_base]).
#
# What reaches the guest is a manifest (format 3, design section 13): the
# sections, and the names of the chunks the words and postings are cut into.
# Everything else is fetched as a query needs it, by the guest asking the host
# (`Fetch`) and keeping what comes back in the retained state ([absorb]) --
# read-only data, so it stays out of the model that crosses the wire. The
# words of a query are in a few chunks, found by binary search on the
# chunks' first words; until they have all arrived the text answers nothing
# (an intersection over a missing chunk would be wrong, not partial), and the
# titles answer alone. What a row shows, and what a Chinese phrase is checked
# against, is a section's text fragment, a file of its own asked for the rows
# the reader can see. A row whose fragment has not arrived is drawn with its
# title and place and no excerpt. In both cases the answer is computed again
# when the file does arrive -- the ranking is a function of the query and of
# what has arrived, so a late chunk or fragment reorders rows rather than
# needing a second code path, and once everything asked for is here the answer
# is the one a panel holding the whole index would give.
#
# A query neither index answers is looked at once more for slips of the
# fingers ([suggest]): the words it lacks are measured against the words the
# indexes have that begin with the same letter, and the first query so made
# that answers is offered, with its count, as one line of the empty state.
# The query typed is still the query searched.
#
# The bilingual strings below are data, not prose: this application draws
# itself on an English page and on a Chinese one, and the site's own generator
# (site/src/gen/pages.dawn) keeps its two languages in one table for the same
# reason -- a missing one is then a compile error rather than a page that
# renders half-translated.

use std/str
use std/list
use std/char
use std/cursor
use json/value.{Json, JNull, JBool, JInt, JStr, JArr, JObj}
use json/parser.{parse}
use json/render.{render}
use std/map
use tea_core/cmd.{Cmd, NoCmd, SendMsg, BatchCmd, Fetch, fold_cmds, fetches}
use tea_dom/node.{Node, On, NoData}
use tea_dom/dsl.{el, div, span, text, on_value, on_key, on_click}

## One thing a reader can go to: which part of the site it belongs to, what it
## is called, the one line under the name, and where it lives.
##
## `detail` is a signature for an API entry and the document's name for a
## section; `note` is the first sentence of a doc comment, or empty. `href` is
## relative to the SITE root, not to the page the panel is open on -- the page
## supplies its own distance and [link] joins the two.
pub type Entry = {
  group: String,
  title: String,
  detail: String,
  note: String,
  href: String,
}

## A match, and its ordinal among all the matches in display order. The
## ordinal is what the arrow keys move and what a row compares itself with to
## know whether it is the selected one.
##
## `text` is whether the row is a section of the documents' text rather than
## a title row, which decides one class and nothing else.
pub type Hit = { entry: Entry, at: Int, text: Bool }

## Everything a scan of the index answers: the matches, and the href the
## current selection resolves to.
pub type Scan = { hits: List[Hit], chosen: String }

## What init derives from one entry so that a keystroke does not have to: the
## position of its group in the panel's order (-1 for a group the panel does
## not draw), its title lowercased, the words of its title, and the words of
## its title, signature and note together.
pub type Key = {
  group: Int,
  title: String,
  heads: List[String],
  words: List[String],
}

## What init retains in the guest. There is deliberately no update that returns
## this type: the index, root and language belong to one successful init and a
## later successful init is the only operation that may replace them.
##
## `mod_key` is what the reader's keyboard calls the modifier that opens a
## result in a new tab (`⌘` or `Ctrl`), a fact about the machine that only
## the page can see. `start` is the index's own list of suggested entries, as
## ids into `entries`: the generator picks them, so their titles and hrefs are
## the language's and gen/links has checked every one. `recent` is the
## reader's recent queries, newest first; the page keeps them and the guest
## only shows them, which is why they are here and not in the model.
##
## `body` is the manifest of the documents' text index, once the page has
## fetched it and started the panel again with it ([body_of]); until then, and
## for an asset in a format this panel does not read, the panel searches titles
## only and says so in its foot. `texts` are the sections' paragraphs and
## `chunks` the words and postings, each fetched when a query needs it
## ([absorb]) and kept for the life of the panel.
pub type State = {
  root: String,
  lang: String,
  mod_key: String,
  entries: List[Entry],
  keys: List[Key],
  start: List[Int],
  recent: List[String],
  body: Option[Body],
  texts: Map[Int, List[String]],
  chunks: Map[Int, Posts],
}

## The mutable model, and therefore the whole model text on the wire. `goto` is
## an instruction rather than durable state: something asks for it, the page
## reads it out of the document, and the next message clears it.
##
## Which "something" is a `Cmd` now. Enter used to write the field from inside
## its own arm, which is what a command is when there is no channel for one:
## an instruction dressed as a state change. Enter answers
## `SendMsg(Chose(href))` instead, and `Chose` is the only arm that writes
## `goto`. The model the turn ends with is the same one, byte for byte.
##
## `hits` is what [search] answered for `query`: ids into the index, in the
## order the panel shows them, at most [cap] of them. Only `Typed` and
## `Scoped` write it. An id from [body_base] up is a paragraph of the body
## index rather than a title row: the row is its section, and the paragraph
## is the excerpt it shows. One list rather than two, because the order of
## the rows is one order, across both kinds.
##
## `scope` is the group the reader has narrowed the list to, by its place in
## [groups], or -1 for all of them; `counts` is how many entries of each group
## the query matched before any narrowing or cap, which is what the scope
## pills show. Both are a view over the same ranking, not a second index: a
## pill filters the matches, and the cap then applies inside the one group.
##
## `fix` is the one query the panel suggests when nothing answered this one
## ([suggest]), and `fix_hits` how many rows that query answers; `""` and 0
## whenever something did answer. Written with `hits`, by the same arms.
##
## `asked` is the sections whose text fragment has been requested and has not
## come back: what keeps a second keystroke from asking for the same file
## again. `chased` is how many sections' text this query has asked for only to
## check a Chinese phrase ([verify_total]). `loading` is the postings chunks
## requested and not yet back, the same thing for the words: it keeps a second
## keystroke from asking for a chunk already on its way, and it is how the
## panel knows an empty answer may only be an unfinished one. All three are on
## the wire only while they are not empty or zero.
##
## `stale` is the query the rows in `hits` answer, while that is not `query`:
## typing a word whose chunks have not arrived leaves the last settled view in
## place (its rows, counts, scope, suggestion and selection exactly as they
## were, drawn dimmed with `aria-busy`) rather than recomputing against words
## that are not here, and the view swaps to the new answer in one turn when
## they arrive. "" whenever the rows answer the query.
pub type Model = {
  query: String,
  sel: Int,
  open: Bool,
  goto: String,
  hits: List[Int],
  scope: Int,
  counts: List[Int],
  fix: String,
  fix_hits: Int,
  asked: List[Int],
  chased: Int,
  loading: List[Int],
  stale: String,
}

## What the listeners mean, plus the one message no listener produces.
##
## `Hovered` is the pointer resting on the row with that ordinal, and
## `Dismissed` the Cancel button a phone shows in place of the Escape key.
## `Scoped` is a scope pill: the group it narrows to, or -1 for All.
##
## `Arrived` is a section's text fragment having come back (or failed to): the
## host's answer to a `Fetch`, read by [supplied]. The text itself is not in the
## message; [absorb] has already put it in the retained state.
##
## `Loaded` is the same for a postings chunk of the text's index: the words
## are in the retained state, and the answer is asked again with them.
##
## `Chose` cannot arrive from the page: a message reaches this application
## only through the `to_msg` of a listener `route.at` found in the tree, and no
## listener names it. It arrives from Enter's command and nowhere else.
pub type Msg =
  | Typed(text: String)
  | Pressed(key: String)
  | Hovered(at: Int)
  | Dismissed
  | Chose(href: String)
  | Scoped(group: Int)
  | Arrived(sec: Int)
  | Loaded(chunk: Int)
derive Show

## Where the page is, what language it is in, and whether the documents'
## text is searched as well as the titles, asked for at the leaves.
##
## None takes a type parameter because an effect operation cannot (spec
## §6.5) and none needs one: a root is a relative path, a language is its
## `lang` attribute, and the third is a yes or a no that two labels read.
pub effect Ctx {
  fn root() -> String
  fn lang() -> String
  fn full_text() -> Bool
}

## One matched entry, in the order the body found it.
pub effect Found {
  fn found(e: Entry, text: Bool) -> Unit
}

## One child, in the order the body wants it. The same shape
## scripts/wasm-dom-contract/collect pins, and the same one the counter's view
## uses; it is spelled here rather than imported because a way of *building* a
## child list is not part of `tea_dom`'s vocabulary yet.
pub effect Emit {
  fn emit(w: Node[Msg]) -> Unit
}

# ---- the five groups ------------------------------------------------------

## A group of results. The id is what an index entry's `group` field carries,
## so this table is also the registration: an entry whose group is not one of
## these five is never shown at all, and the test below is what says the index
## agrees. The order here breaks ties only; a group's place in the panel is
## its best match ([arrange]).
##
## `pill_en` and `pill_zh` are the group's name on its scope pill, where a
## row of six has to fit a phone.
type Group = { id: String, en: String, zh: String, pill_en: String, pill_zh: String }

fn groups() -> List[Group] = [
  Group { id: "stdlib", en: "Standard library", zh: "标准库", pill_en: "Stdlib", pill_zh: "标准库" },
  Group { id: "spec", en: "Spec", zh: "规范", pill_en: "Spec", pill_zh: "规范" },
  Group { id: "tutorial", en: "Tutorial", zh: "教程", pill_en: "Tutorial", pill_zh: "教程" },
  Group { id: "examples", en: "Examples and pages", zh: "示例与页面", pill_en: "Examples", pill_zh: "示例" },
  Group { id: "history", en: "History", zh: "历史", pill_en: "History", pill_zh: "历史" },
]

## Where `id` stands in [groups], or -1 when the panel does not draw it.
fn group_index(id: String) -> Int = {
  var at = -1
  var i = 0
  for g in groups() {
    if at < 0 && g.id == id {
      at = i
    }
    i = i + 1
  }
  at
}

fn group_label(g: Group, code: String) -> String =
  if code == "zh-CN" { g.zh } else { g.en }

## What the panel says it searches. The expectation this manages is the one
## the whole design rests on: until the documents' text has arrived this is
## a title and API-name index, so a reader who types a word out of the middle
## of a paragraph gets nothing and has to be told why rather than left to
## conclude the search is broken. The line changes when the text is in, and
## stays as it is when the page could not give it (a fetch that failed, an
## asset in a format this panel does not read).
fn scope_line(code: String, full: Bool) -> String =
  if full {
    say(code, "Searches titles, API names and the documents' text.", "搜标题、API 名与文档正文。")
  } else {
    say(code, "Searches titles and API names, not body text.", "只搜标题与 API 名，不搜正文。")
  }

## `en` on an English page and `zh` on a Chinese one. Every other string the
## panel shows goes through here, so the two languages of one label are on one
## line and neither can be forgotten without the other.
fn say(code: String, en: String, zh: String) -> String = if code == "zh-CN" { zh } else { en }

fn placeholder(code: String, full: Bool) -> String =
  if full {
    say(code, "Search titles, API names and text", "搜索标题、API 名与正文")
  } else {
    say(code, "Search titles and API names", "搜索标题与 API 名")
  }

fn prompt_line(code: String) -> String =
  if code == "zh-CN" { "输入关键词开始搜索。" } else { "Type to search." }

# ---- words ----------------------------------------------------------------
#
# The tokenizer is written twice, here and in site/src/gen/search.dawn,
# because the two are separate programs that cannot share a line of code. The
# rule is short enough to state in full, and a pair of tests that name each
# other pins both copies to the same samples:
#
#   lowercase; split on every character that is not an ASCII letter or digit,
#   `_`, `!`, `.`, or a letter or digit beyond ASCII; strip the dots off both
#   ends of a run; then a run made of pieces joined by `.`, `_` or `!` yields
#   each piece and then the run itself, so `io.read_file` is `io`, `read`,
#   `file` and `io.read_file`, and `!Fs` is `fs` and `!fs`.
#
# Letters beyond ASCII are kept because the Chinese index is searched in
# Chinese. They are not split any further: Chinese has no spaces to split on,
# and the panel reaches inside such a run with a substring test instead
# ([Fit]).

## What a code point is to the tokenizer: 0 between runs, 1 a dot, 2 one of
## the other two joints, 3 a character of a piece.
fn kind_of(k: Int) -> Int =
  if (k >= 97 && k <= 122) || (k >= 48 && k <= 57) {
    3
  } else if k == 46 {
    1
  } else if k == 95 || k == 33 {
    2
  } else if k > 127 && is_wide_alnum(k) {
    3
  } else {
    0
  }

fn is_wide_alnum(k: Int) -> Bool =
  match char.of(k) {
    Some(c) -> char.is_alnum(c)
    None -> false
  }

## The words of `s`, by the rule at the head of this section.
##
## One walk with a cursor, and one slice per word. Init runs this over every
## title, signature and note in the index and it is most of what init costs,
## which is why it is a state machine rather than the three passes the rule
## reads as: over the live index the passes took 42 ms and this takes 3
## (wasm, Node 26). site/src/gen/search.dawn keeps the three-pass reading; the
## pair of tests is what says the two agree.
##
## Not deduplicated across runs: a word that occurs twice is two entries, and
## matching does not care.
pub fn tokens(s: String) -> List[String] = {
  let t = str.to_lower(s)
  var out: List[String] = []
  var at = cursor.start(t)
  # where the run began, where its current piece began, and just past its last
  # character that is not a dot -- the end of the run once the dots are off
  var run_from = at
  var piece_from = at
  var last_end = at
  var in_run = false
  var in_piece = false
  var pieces = 0
  # whether a joint stands inside the run, and whether a dot has been seen
  # that only counts as inside once another piece follows it
  var joined = false
  var pending = false
  var go = true
  while go {
    let fin = cursor.done(t, at)
    let cls = if fin { 0 } else { cursor.char(t, at).kind_of() }
    let nx = cursor.next(t, at)
    if cls == 3 {
      if not in_run {
        in_run = true
        run_from = at
        pieces = 0
        joined = false
        pending = false
      }
      if not in_piece {
        in_piece = true
        piece_from = at
        if pending {
          joined = true
          pending = false
        }
      }
      last_end = nx
    } else {
      if in_piece {
        out = out ++ [cursor.slice(t, piece_from, at)]
        pieces = pieces + 1
        in_piece = false
      }
      if cls == 2 {
        if not in_run {
          in_run = true
          run_from = at
          pieces = 0
          pending = false
        }
        joined = true
        last_end = nx
      } else if cls == 1 {
        if in_run {
          pending = true
        }
      } else {
        if in_run && pieces > 0 && joined {
          out = out ++ [cursor.slice(t, run_from, last_end)]
        }
        in_run = false
        go = not fin
      }
    }
    at = nx
  }
  out
}

## The runs of `s`, lowercased, dots and all.
fn runs(s: String) -> List[String] = {
  let t = str.to_lower(s)
  var out: List[String] = []
  var at = cursor.start(t)
  var from = at
  var in_run = false
  var go = true
  while go {
    let fin = cursor.done(t, at)
    let cls = if fin { 0 } else { cursor.char(t, at).kind_of() }
    if cls != 0 {
      if not in_run {
        in_run = true
        from = at
      }
    } else {
      if in_run {
        out = out ++ [cursor.slice(t, from, at)]
      }
      in_run = false
      go = not fin
    }
    at = cursor.next(t, at)
  }
  out
}

## `w` without the dots at its start, and at its end too when `both`.
fn trim_dots(w: String, both: Bool) -> String = {
  var s = w
  while str.starts_with(s, ".") {
    s = str.drop(s, 1)
  }
  while both && str.ends_with(s, ".") {
    s = str.take(s, len(s) - 1)
  }
  s
}

## The words of a paragraph of the documents' text, and of a query for it
## (docs/site-search-design.md 2.3): every Han character becomes a blank and
## the rest goes through [tokens]; then each Han character is a word of its
## own, in the order they occur.
##
## site/src/gen/search.dawn writes the body index with its own copy of this,
## and the two are held to the table in 3.2 of that document by a test on
## each side. Single characters because Chinese has no blanks to split on;
## the blanks first because the text joins inline code straight onto the
## Chinese after it, and `Fs效果` has to give `fs`.
pub fn body_terms(s: String) -> List[String] = {
  var rest: List[Char] = []
  var han: List[String] = []
  for c in code_points(s) {
    if is_han(c) {
      rest = rest ++ [' ']
      han = han ++ [str.from_char(c)]
    } else {
      rest = rest ++ [c]
    }
  }
  rest.from_code_points().tokens() ++ han
}

## Whether `c` is a Han character: the CJK unified ideographs, extension A,
## the compatibility block and the supplementary planes' extensions. Kana,
## Hangul and full-width punctuation are not.
pub fn is_han(c: Char) -> Bool = {
  let n = char.code(c)
  (n >= 0x3400 && n <= 0x4DBF) || (n >= 0x4E00 && n <= 0x9FFF) || (n >= 0xF900 && n <= 0xFAFF)
    || (n >= 0x20000 && n <= 0x2FA1F)
}

## How one word of a query has to meet a word of an entry.
##
## `Whole` for every word but the last, which is `Start` because the reader is
## still typing it. `Within` for a word beyond ASCII, wherever it stands: a
## Chinese run is a whole phrase, and a reader looking for `效果` means the one
## inside `命名效果` too.
pub type Fit =
  | Whole
  | Start
  | Within
derive Show

pub type Term = { word: String, fit: Fit }

## A query's words, each with how it has to fit.
##
## The runs of the same rule, but not its pieces: a query word is matched
## against an entry's pieces *and* runs, so `fs` finds `!Fs` and `str.tr`
## finds `str.trim` without the query having to be split. The last word keeps
## its trailing dot, which is the difference between `str.` (a module's
## members) and `str` (everything that starts with it).
pub fn terms(q: String) -> List[Term] = {
  let rs = runs(q)
  var out: List[Term] = []
  var i = 0
  for r in rs {
    let last = i == len(rs) - 1
    let w = trim_dots(r, not last)
    let ks = code_points(w)
    if list.any(ks, c => char.code(c).kind_of() == 3) {
      let fit = if list.any(ks, c => char.code(c) > 127) {
        Within
      } else if last {
        Start
      } else {
        Whole
      }
      out = out ++ [Term { word: w, fit: fit }]
    }
    i = i + 1
  }
  out
}

fn fits(t: Term, word: String) -> Bool =
  match t.fit {
    Whole -> word == t.word
    Start -> str.starts_with(word, t.word)
    Within -> str.contains(word, t.word)
  }

## Whether every term fits some word of `words`.
fn all_fit(ts: List[Term], words: List[String]) -> Bool =
  len(ts) > 0 && list.all(ts, t => list.any(words, w => fits(t, w)))

# ---- the documents' text ---------------------------------------------------
#
# The second index is the documents split into sections and paragraphs, with
# an inverted index from words to paragraph numbers. Its format, and the five
# constraints it puts on this side, are docs/site-search-design.md 2.1-2.5;
# its words are [body_terms], pinned to the generator's copy by the table in
# 3.2 of the same file.
#
# A query is answered with binary search and merges, never with a walk of the
# text: every word but the last is looked up whole, the last as a prefix (the
# union of a range of the sorted words), each Han character whole, and the
# paragraph lists are intersected. Chinese is indexed one character at a time,
# so a phrase of two or more characters is then checked against the few
# candidates' excerpts. The paragraphs fall into sections, and a section is
# one row.

## Where the ids of body rows begin in the model's `hits`: an id `body_base()
## + p` is paragraph `p` of the body index. A decimal offset rather than a
## second list, so that one list keeps the panel's one order, and rather than
## a bit, so that a transcript says `1000412` and a reader sees paragraph 412.
## The title index has a few hundred rows.
pub fn body_base() -> Int = 1000000

## One section of a document, as the body index's section table names it,
## and two things init derives from it so that a keystroke does not have to:
## the group of the panel it is drawn in (-1 for none), and the title row with
## the same href (-1 for none), which is the row that stands for it when both
## answer.
pub type Sec = { doc: String, href: String, title: String, group: Int, entry: Int, frag: String }

## One paragraph: its section, and its place among that section's paragraphs
## that have a number. Its text is in the section's fragment, `nth`-th, and in
## the index nowhere.
pub type Para = { sec: Int, nth: Int }

## One postings chunk as the manifest lists it: the first word it holds and
## the hash in the name of its file. Chunk `i` holds the words from its `first`
## up to the next chunk's `first`, so which chunk has a word is a binary search
## on the manifest and nothing else.
pub type Chunk = { first: String, hash: String }

## The body index, read: the manifest, which is all the page hands over.
## `dir` is where the fragments are and a section's `frag` is the hash in the
## name of its file; `chunk_dir` and a chunk's `hash` do the same for the
## chunks of words and postings, which arrive on demand and are kept in the
## state ([Posts]).
pub type Body = {
  dir: String,
  chunk_dir: String,
  secs: List[Sec],
  chunks: List[Chunk],
  paras: List[Para],
}

## A chunk that has arrived: its words in code-point order, and `posts[i]`, the
## paragraph numbers `terms[i]` occurs in, ascending (the asset writes the gaps
## between them, and the chunk is summed once when it arrives rather than every
## keystroke). A chunk that failed to come, or is not the one the manifest
## describes, is recorded with no words at all: the words in it are then
## words the index lacks, and it is not asked for again.
pub type Posts = { terms: List[String], posts: List[List[Int]] }

fn has_body(state: State) -> Bool =
  match state.body {
    Some(_) -> true
    None -> false
  }

## The body index out of its manifest, or `None` for anything but format 3.
##
## A version this panel does not know is not read at all, rather than read as
## far as it happens to agree: the version is the format's whole promise, and
## a panel without the text is a working panel that says it searches titles.
## Inside format 3 the asset is a file the page fetched, and every lookup
## below is total: a field of the wrong kind reads as empty and a number that
## names nothing is passed over.
pub fn body_of(j: Json, entries: List[Entry]) -> Option[Body] = {
  let fs = jarr(j)
  if len(fs) != 6 || jint_or(fs[0], 0) != 3 {
    None
  } else {
    let by_href = hrefs_of(entries)
    let secs = list.map(jarr(fs[2]), s => s.jarr().sec_of(by_href))
    let counts = list.map(jarr(fs[3]), c => jint_or(c, 0))
    let chunks = list.map(jarr(fs[5]), c => chunk_of(c.jarr()))
    if len(counts) != len(secs) || len(chunks) == 0 {
      None
    } else {
      Some(Body {
        dir: jstr_or(fs[1], ""),
        chunk_dir: jstr_or(fs[4], ""),
        secs: secs,
        chunks: chunks,
        paras: paras_of(counts),
      })
    }
  }
}

fn chunk_of(fs: List[Json]) -> Chunk =
  if len(fs) == 2 { Chunk { first: jstr_or(fs[0], ""), hash: jstr_or(fs[1], "") } } else { Chunk { first: "", hash: "" } }

## The paragraph table out of the per-section counts: section 0's paragraphs
## first, then section 1's, each numbered from 0 within its section.
fn paras_of(counts: List[Int]) -> List[Para] = {
  var out: List[Para] = []
  var sec = 0
  for n in counts {
    for k in range(0, n) {
      out = out ++ [Para { sec: sec, nth: k }]
    }
    sec = sec + 1
  }
  out
}

## Each title row's href, to its id; the first row wins a shared href.
fn hrefs_of(entries: List[Entry]) -> Map[String, Int] = {
  var out: Map[String, Int] = map.empty()
  var id = 0
  for e in entries {
    if not map.has(out, e.href) {
      out = map.insert(out, e.href, id)
    }
    id = id + 1
  }
  out
}

fn sec_of(fs: List[Json], by_href: Map[String, Int]) -> Sec = {
  let ok = len(fs) == 4
  let doc = if ok { jstr_or(fs[0], "") } else { "" }
  let href = if ok { jstr_or(fs[1], "") } else { "" }
  Sec {
    doc: doc,
    href: href,
    title: if ok { jstr_or(fs[2], "") } else { "" },
    group: doc_group(doc),
    entry: map.get(by_href, href).unwrap_or(-1),
    frag: if ok { jstr_or(fs[3], "") } else { "" },
  }
}

## The group a document's sections are drawn in. The early design decisions
## are history, as they are in the title index; the body index keeps the two
## apart only so that a row can say which page it is on.
fn doc_group(doc: String) -> Int =
  if doc == "design" { group_index("history") } else if doc == "stdlib" || doc == "examples" { -1 } else { group_index(doc) }

## Gaps back into the numbers they separate.
fn sums(gaps: List[Json]) -> List[Int] = {
  var out: List[Int] = []
  var at = 0
  for g in gaps {
    at = at + jint_or(g, 0)
    out = out ++ [at]
  }
  out
}

## How `a` and `b` compare by code point: negative, zero or positive. This is
## the order the asset sorts its words in (docs/site-search-design.md 2.3), and
## it is spelled out here rather than left to `<` on strings, whose order is a
## backend's business.
fn order(a: String, b: String) -> Int = {
  var i = cursor.start(a)
  var j = cursor.start(b)
  var out = 0
  var go = true
  while go {
    let ea = cursor.done(a, i)
    let eb = cursor.done(b, j)
    if ea || eb {
      out = if ea && eb { 0 } else if ea { -1 } else { 1 }
      go = false
    } else {
      let d = cursor.char(a, i) - cursor.char(b, j)
      if d != 0 {
        out = d
        go = false
      } else {
        i = cursor.next(a, i)
        j = cursor.next(b, j)
      }
    }
  }
  out
}

## The first word at or after `w`.
fn lower_bound(terms: List[String], w: String) -> Int = {
  var lo = 0
  var hi = len(terms)
  while lo < hi {
    let mid = (lo + hi) / 2
    if order(terms[mid], w) < 0 {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  lo
}

## The first word from `from` on that does not start with `w`. The words that
## do are one run there, because the list is sorted and `from` is where `w`
## itself would stand.
fn past_prefix(terms: List[String], w: String, from: Int) -> Int = {
  var lo = from
  var hi = len(terms)
  while lo < hi {
    let mid = (lo + hi) / 2
    if str.starts_with(terms[mid], w) {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  lo
}

## A word of a query, and whether it may be the start of a word rather than
## all of one.
pub type BodyTerm = { word: String, prefix: Bool }

## A query's words for the body index: [body_terms] of it, once each, and the
## ones the query ends with are prefixes because the reader is still typing
## them -- the last piece of the last run and that run itself, so `io.read_fi`
## looks for `io` and `read` whole and for `fi…` and `io.read_fi…`. A query
## that ends in a Han character or a blank has no prefix: a Han character is
## a whole word by construction.
##
## A prefix of one letter is looked up whole. `s…` is a few hundred words and
## most of the paragraphs, and merging them was the one step of a keystroke
## that cost more than the titles did (8 ms of wasm, measured); a reader who
## has typed one letter is answered by the titles, and by the text a letter
## later.
pub fn body_query(q: String) -> List[BodyTerm] = {
  let low = str.to_lower(str.trim(q))
  let tail = last_run(low)
  list.map(list.unique(body_terms(low)), w =>
      BodyTerm { word: w, prefix: tail != "" && str.ends_with(tail, w) && not han_word(w) && len(w) >= 2 })
}

fn han_word(w: String) -> Bool = list.any(code_points(w), c => is_han(c))

## The query's last run, without its dots, when the query ends with it, and
## empty otherwise.
fn last_run(low: String) -> String = {
  let rs = list.map(code_points(low), c => if is_han(c) { ' ' } else { c })
    .from_code_points()
    .runs()
  if len(rs) == 0 {
    ""
  } else {
    let r = rs[len(rs) - 1]
    if str.ends_with(low, r) { trim_dots(r, true) } else { "" }
  }
}

## The query's phrases of two or more Han characters in a row, which the
## single-character index cannot answer for by itself.
pub fn han_runs(q: String) -> List[String] = {
  var out: List[String] = []
  var run: List[Char] = []
  for c in code_points(q) ++ [' '] {
    if is_han(c) {
      run = run ++ [c]
    } else {
      if len(run) >= 2 {
        out = out ++ [from_code_points(run)]
      }
      run = []
    }
  }
  out
}

## `s` without the blanks that stand between two Han characters. A Chinese
## paragraph's source lines are joined with a blank (the browser does the
## same), so a phrase that crossed a line in the source has one inside it.
fn squash(s: String) -> String = {
  let cs = code_points(s)
  var out: List[Char] = []
  var i = 0
  for c in cs {
    let gap = char.is_space(c) && i > 0 && i + 1 < len(cs) && is_han(cs[i - 1]) && is_han(cs[i + 1])
    if not gap {
      out = out ++ [c]
    }
    i = i + 1
  }
  from_code_points(out)
}

# ---- which chunk has a word --------------------------------------------------

## The chunk that holds the word `w` if the index has it: the last one whose
## first word is not after `w`, or -1 when `w` sorts before every chunk (no
## such word is in the index).
fn chunk_at(b: Body, w: String) -> Int = {
  var lo = 0
  var hi = len(b.chunks)
  while lo < hi {
    let mid = (lo + hi) / 2
    if order(b.chunks[mid].first, w) <= 0 {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  lo - 1
}

## The chunks that can hold a word starting with `w` when `prefix`, or `w`
## itself when not. A prefix's words are one run of the sorted list, so its
## chunks are: the one `w` itself would be in, then each next one whose first
## word still starts with `w` (a chunk that starts past the run ends it). The
## first of them may hold only words before `w`; it is asked for anyway,
## because the manifest cannot say.
fn chunks_for(b: Body, w: String, prefix: Bool) -> List[Int] = {
  let i = chunk_at(b, w)
  if not prefix {
    if i >= 0 { [i] } else { [] }
  } else {
    var out: List[Int] = if i >= 0 { [i] } else { [] }
    var j = i + 1
    while j < len(b.chunks) && str.starts_with(b.chunks[j].first, w) {
      out = out ++ [j]
      j = j + 1
    }
    out
  }
}

## The chunks a query's words are in, ascending, each once.
fn chunks_of_query(b: Body, ts: List[BodyTerm]) -> List[Int] = {
  var out: List[Int] = []
  for t in ts {
    for i in chunks_for(b, t.word, t.prefix) {
      if not list.contains(out, i) {
        out = out ++ [i]
      }
    }
  }
  sort_by(out, (x, y) => x - y)
}

## Those of `ids` whose words have neither arrived nor failed: what is still to
## be asked for before a lookup in them means anything.
fn not_here(state: State, ids: List[Int]) -> List[Int] = list.filter(ids, i => not map.has(state.chunks, i))

## The chunks a query (lowercased and trimmed) would need that are not here
## yet. Empty without the body index: there is nothing to ask for.
pub fn body_need(state: State, q: String) -> List[Int] =
  match state.body {
    None -> []
    Some(b) -> state.not_here(chunks_of_query(b, body_query(q)))
  }

## The words of chunk `i` and their postings, empty when it has not arrived.
fn posts_at(state: State, i: Int) -> Posts =
  map.get(state.chunks, i).unwrap_or(Posts { terms: [], posts: [] })

## The paragraphs one word is in, from the chunks that hold it. A chunk that is
## not here reads as having none of its words, which is why [body_hits] does not
## look until every chunk the query needs is.
fn postings(state: State, b: Body, t: BodyTerm) -> List[Int] = {
  if t.prefix {
    var lists: List[List[Int]] = []
    for i in chunks_for(b, t.word, true) {
      let c = posts_at(state, i)
      let lo = lower_bound(c.terms, t.word)
      lists = lists ++ list.slice(c.posts, lo, past_prefix(c.terms, t.word, lo))
    }
    union(lists)
  } else {
    let i = chunk_at(b, t.word)
    if i < 0 {
      []
    } else {
      let c = posts_at(state, i)
      let lo = lower_bound(c.terms, t.word)
      if lo < len(c.terms) && c.terms[lo] == t.word { c.posts[lo] } else { [] }
    }
  }
}

## Every number in any of the ascending lists, ascending, once. Halves rather
## than one list at a time, so a short prefix that covers hundreds of words
## costs a merge per level and not a merge per word.
fn union(ls: List[List[Int]]) -> List[Int] =
  if len(ls) == 0 {
    []
  } else if len(ls) == 1 {
    ls[0]
  } else {
    let half = len(ls) / 2
    either(union(list.take(ls, half)), union(list.drop(ls, half)))
  }

fn either(a: List[Int], b: List[Int]) -> List[Int] = {
  var out: List[Int] = []
  var i = 0
  var j = 0
  let na = len(a)
  let nb = len(b)
  while i < na || j < nb {
    if j >= nb || (i < na && a[i] < b[j]) {
      out = out ++ [a[i]]
      i = i + 1
    } else if i >= na || b[j] < a[i] {
      out = out ++ [b[j]]
      j = j + 1
    } else {
      out = out ++ [a[i]]
      i = i + 1
      j = j + 1
    }
  }
  out
}

fn both(a: List[Int], b: List[Int]) -> List[Int] = {
  var out: List[Int] = []
  var i = 0
  var j = 0
  while i < len(a) && j < len(b) {
    if a[i] < b[j] {
      i = i + 1
    } else if b[j] < a[i] {
      j = j + 1
    } else {
      out = out ++ [a[i]]
      i = i + 1
      j = j + 1
    }
  }
  out
}

## The numbers in every list, shortest list first so that the running answer
## is never longer than the rarest word's.
fn every(ls: List[List[Int]]) -> List[Int] = {
  let by_size = sort_by(ls, (a, b) => len(a) - len(b))
  var out: List[Int] = if len(by_size) > 0 { by_size[0] } else { [] }
  for l in list.drop(by_size, 1) {
    if len(out) > 0 {
      out = both(out, l)
    }
  }
  out
}

## A section the text answers. `paras` are the paragraphs that answered in it,
## of which its row shows one ([shown_para]); `rank` is its tier in
## [answer]'s table and `weight` orders the sections of one tier.
pub type BodyHit = { sec: Int, paras: List[Int], rank: Int, weight: Int }

## Every section of the body index that answers `q` (lowercased and trimmed),
## in section order. Nothing at all without the body index.
pub fn body_hits(state: State, q: String) -> List[BodyHit] =
  match state.body {
    None -> []
    Some(b) -> {
      let ts = body_query(q)
      if len(ts) == 0 || len(state.not_here(chunks_of_query(b, ts))) > 0 {
        []
      } else {
        let lists = list.map(ts, t => postings(state, b, t))
        let all = every(lists)
        if len(all) > 0 {
          checked(state, b, all, han_runs(q))
        } else if len(ts) >= 3 && not han_word(q) {
          most(b, lists)
        } else {
          []
        }
      }
    }
  }

## The candidates, checked for the query's Chinese phrases and gathered into
## sections. Paragraph numbers ascend with section numbers (design 2.1), so a
## section's paragraphs are one run of the candidates.
##
## A candidate whose text has every phrase is sure, and one whose text does not
## goes. A candidate whose section's text has not arrived cannot be checked, and
## is kept a tier lower (design 2.5, 13.7): all its characters are there, the
## phrase may not be. Once the fragment is in, the same candidate is sure or
## gone, which is how a late fragment reorders rows.
fn checked(state: State, b: Body, ps: List[Int], phrases: List[String]) -> List[BodyHit] = {
  var out: List[BodyHit] = []
  var sec = -1
  var sure: List[Int] = []
  var maybe: List[Int] = []
  for p in ps {
    match get(b.paras, p) {
      Some(para) -> {
        let v = verdict(para_text(state, p), phrases)
        if v > 0 {
          if para.sec != sec {
            out = out ++ section_hit(sec, sure, maybe)
            sec = para.sec
            sure = []
            maybe = []
          }
          if v == 2 {
            sure = sure ++ [p]
          } else {
            maybe = maybe ++ [p]
          }
        }
      }
      None -> ()
    }
  }
  out ++ section_hit(sec, sure, maybe)
}

## 2 when the text has every phrase (or the query has none), 1 when the text
## is not here to say, 0 when it is here and does not.
fn verdict(text: Option[String], phrases: List[String]) -> Int =
  if len(phrases) == 0 {
    2
  } else {
    match text {
      None -> 1
      Some(t) -> {
        let flat = squash(t)
        if list.all(phrases, ph => str.contains(flat, ph)) { 2 } else { 0 }
      }
    }
  }

## Paragraph `p`'s whole text, when its section's fragment has arrived. A
## fragment that failed to come is recorded as empty and reads as absent, so a
## section whose file is missing degrades to rows with no excerpt rather than
## to a request made again on every keystroke.
fn para_text(state: State, p: Int) -> Option[String] =
  match state.body {
    None -> None
    Some(b) ->
      match get(b.paras, p) {
        None -> None
        Some(para) ->
          match map.get(state.texts, para.sec) {
            None -> None
            Some(ts) -> get(ts, para.nth)
          }
      }
  }

fn section_hit(sec: Int, sure: List[Int], maybe: List[Int]) -> List[BodyHit] =
  if sec < 0 {
    []
  } else if len(sure) > 0 {
    [BodyHit { sec: sec, paras: sure, rank: 0, weight: len(sure) }]
  } else if len(maybe) > 0 {
    [BodyHit { sec: sec, paras: maybe, rank: -1, weight: len(maybe) }]
  } else {
    []
  }

## When no paragraph has every word of a longer query: the paragraphs that
## have most of them.
##
## A question typed as a sentence (`where does the spec say handle`) has words
## no paragraph shares all of, and an intersection answers nothing. So for a
## query of three words or more that nothing answers whole, a paragraph is
## kept when it has at least half of the words, and weighed by how rare the
## ones it has are: `say` and `handle` count for more than `the` and `does`.
## These rows are the lowest tier there is. Not for Chinese: one character is
## too common a word for "most of them" to mean anything.
fn most(b: Body, lists: List[List[Int]]) -> List[BodyHit] = {
  let n = len(b.paras)
  var acc = Tally { paras: [], scores: [], counts: [] }
  for ps in lists {
    acc = tally(acc, ps, rarity(n, len(ps)))
  }
  let need = (len(lists) + 1) / 2
  var out: List[BodyHit] = []
  for i in range(0, len(acc.paras)) {
    if acc.counts[i] >= need {
      out = keep_most(b, out, acc.paras[i], acc.scores[i])
    }
  }
  out
}

## Paragraphs, ascending, each with the sum of the rarities of the words it
## has and how many words that is. Three lists rather than a list of records,
## so that a merge appends integers.
type Tally = { paras: List[Int], scores: List[Int], counts: List[Int] }

## `t` with one more word, whose paragraphs are `ps` and whose rarity is `w`:
## one merge of two ascending lists, rather than a sort of every (paragraph,
## word) pair.
fn tally(t: Tally, ps: List[Int], w: Int) -> Tally = {
  var paras: List[Int] = []
  var scores: List[Int] = []
  var counts: List[Int] = []
  var i = 0
  var j = 0
  let na = len(t.paras)
  let nb = len(ps)
  while i < na || j < nb {
    if j >= nb || (i < na && t.paras[i] < ps[j]) {
      paras = paras ++ [t.paras[i]]
      scores = scores ++ [t.scores[i]]
      counts = counts ++ [t.counts[i]]
      i = i + 1
    } else if i >= na || ps[j] < t.paras[i] {
      paras = paras ++ [ps[j]]
      scores = scores ++ [w]
      counts = counts ++ [1]
      j = j + 1
    } else {
      paras = paras ++ [ps[j]]
      scores = scores ++ [t.scores[i] + w]
      counts = counts ++ [t.counts[i] + 1]
      i = i + 1
      j = j + 1
    }
  }
  Tally { paras: paras, scores: scores, counts: counts }
}

## Paragraph `p`, with `score`, added to the sections found so far: to the last
## one when it is in the same section, as a new one otherwise. A section's
## weight is its best paragraph's score, and only the paragraphs with that
## score are kept. Which of those it shows is still [shown_para]'s choice:
## the score may be in words an excerpt has cut. Keeping the rest made that
## choice the dearest step of a sentence-long query (3 ms of wasm, measured).
fn keep_most(b: Body, out: List[BodyHit], p: Int, score: Int) -> List[BodyHit] =
  match get(b.paras, p) {
    None -> out
    Some(para) -> {
      let n = len(out)
      if n > 0 && out[n - 1].sec == para.sec {
        let h = out[n - 1]
        if score > h.weight {
          list.take(out, n - 1) ++ [BodyHit { ..h, paras: [p], weight: score }]
        } else if score == h.weight {
          list.take(out, n - 1) ++ [BodyHit { ..h, paras: h.paras ++ [p] }]
        } else {
          out
        }
      } else {
        out ++ [BodyHit { sec: para.sec, paras: [p], rank: -2, weight: score }]
      }
    }
  }

## How much one word says about a paragraph, by how few paragraphs have it:
## the number of bits in `8n / df`, so a word in every paragraph counts 4 and
## a word in one of a thousand counts 13.
fn rarity(n: Int, df: Int) -> Int = {
  var x = if df > 0 { n * 8 / df } else { 0 }
  var bits = 0
  while x > 0 {
    x = x / 2
    bits = bits + 1
  }
  bits
}

## The paragraph a section's row shows: the one where the query's words are
## densest in the excerpt the reader will see, the first of equals. mdBook's
## teaser picked the section's first paragraph, which is often not where the
## words are (research report §4); a paragraph that answered is not enough
## either, when its words fall outside what the excerpt keeps. Until the
## section's text has arrived every paragraph scores alike, so the first one
## stands in; the choice is made again when it does.
fn shown_para(state: State, h: BodyHit, ts: List[Term]) -> Int = {
  var best = -1
  var best_score = -1
  for p in h.paras {
    let s = match para_text(state, p) {
      Some(t) -> density(excerpt(t), ts)
      None -> 0
    }
    if s > best_score {
      best = p
      best_score = s
    }
  }
  best
}

## How many places the words are found in `text`, per thousand code points.
fn density(text: String, ts: List[Term]) -> Int = {
  let low = str.to_lower(text)
  let found = list.fold(ts, 0, (acc, t) => acc + low.places(t).len())
  found * 1000 / (len(low) + 1)
}

# ---- what a row shows of a paragraph ---------------------------------------

## How many display columns of a paragraph a row shows, before the `…`: about
## two lines of the panel. The same 120 the index's excerpts were cut at before
## format 2 (design 6.5); the cut moved here when the text left the index, and
## it is a width on the panel, which is why the panel makes it.
fn excerpt_len() -> Int = 120

## The columns `c` takes on the panel: 2 for the East Asian Wide and Fullwidth
## characters the documents use (Han, CJK punctuation, kana, Hangul syllables,
## the fullwidth forms), 1 for everything else. A subset of UAX #11 for the
## languages the documents are in; a wide character missing here only lets an
## excerpt run long. The generator keeps the same table
## (site/src/gen/search_body.dawn `columns`) and a test pins them together.
pub fn columns(c: Char) -> Int = {
  let n = char.code(c)
  if is_han(c) || (n >= 0x3000 && n <= 0x30FF) || (n >= 0xAC00 && n <= 0xD7A3)
    || (n >= 0xFF01 && n <= 0xFF60) || (n >= 0xFFE0 && n <= 0xFFE6) {
    2
  } else {
    1
  }
}

## A paragraph as a row shows it: whole when it is at most [excerpt_len]
## columns wide, otherwise cut and marked with `…`. The cut is at the last blank
## that starts at or after half the bound, so that a word is not split; text
## with no blank there (Chinese, mostly) is cut where the bound falls.
pub fn excerpt(s: String) -> String = {
  let cs = code_points(s)
  let n = excerpt_len()
  # at[i]: the columns the first i code points take
  var at: List[Int] = [0]
  var w = 0
  for c in cs {
    w = w + columns(c)
    at = at ++ [w]
  }
  if w <= n {
    s
  } else {
    # fit: how many code points fit in the bound
    var fit = 0
    while at[fit + 1] <= n {
      fit = fit + 1
    }
    var i = fit
    while i >= 0 && at[i] >= n / 2 && not char.is_space(cs[i]) {
      i = i - 1
    }
    let keep = if i < 0 || at[i] < n / 2 { fit } else { i }
    from_code_points(list.take(cs, keep)) ++ "…"
  }
}

## The sorted `ids` hold `x`.
fn has_sorted(ids: List[Int], x: Int) -> Bool = {
  var lo = 0
  var hi = len(ids)
  while lo < hi {
    let mid = (lo + hi) / 2
    if ids[mid] < x {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  lo < len(ids) && ids[lo] == x
}

## The line under a section's title that says where it is: the document, and
## the section's number in the spec or the chapter in the tutorial.
fn crumb(s: Sec, code: String) -> String = {
  let doc = if s.doc == "spec" {
    say(code, "Spec", "规范")
  } else if s.doc == "tutorial" {
    say(code, "Tutorial", "教程")
  } else if s.doc == "design" {
    say(code, "Early decisions", "早期设计决定")
  } else {
    say(code, "History", "历史")
  }
  let (path, anchor) = str.split_once(s.href, "#").unwrap_or((s.href, ""))
  let at = if s.doc == "spec" && str.starts_with(anchor, "s") {
    "§" ++ str.replace(str.drop(anchor, 1), "-", ".")
  } else if s.doc == "tutorial" {
    chapter(path, code)
  } else {
    ""
  }
  if at == "" { doc } else { "${doc} › ${at}" }
}

## "Chapter 9" for `tutorial/09.html`, or nothing for a path that is not one.
fn chapter(path: String, code: String) -> String = {
  let parts = str.split(path, "/")
  let file = parts[len(parts) - 1]
  let num = str.strip_suffix(file, ".html").unwrap_or("")
  let digits = list.all(code_points(num), c => char.is_digit(c))
  if num == "" || not digits {
    ""
  } else {
    var n = num
    while n.code_points().len() > 1 && str.starts_with(n, "0") {
      n = str.drop(n, 1)
    }
    say(code, "Chapter ${n}", "第 ${n} 章")
  }
}

# ---- scoring --------------------------------------------------------------

## How many rows the panel will show. A cap rather than a scroll: the panel is
## a keyboard target, and a list nobody can reach the bottom of by pressing
## down is not a list.
fn cap() -> Int = 40

## How well an entry answers a query, 0 for not at all.
##
## Deterministic and total: the same pair always scores the same, and ties are
## broken by index order, so no two runs can disagree about the order.
##
## `q` arrives lowercased and trimmed and `ts` are its terms, both once per
## keystroke; `k` was lowercased and tokenized once per init.
##
##   5  the title is the query
##   4  the title starts with it
##   3  every word of the query is a word of the title
##   2  the title contains it
##   1  every word of the query is a word of the title, signature or note
pub fn score(k: Key, q: String, ts: List[Term]) -> Int =
  if q == "" {
    0
  } else if k.title == q {
    5
  } else if str.starts_with(k.title, q) {
    4
  } else if all_fit(ts, k.heads) {
    3
  } else if str.contains(k.title, q) {
    2
  } else if all_fit(ts, k.words) {
    1
  } else {
    0
  }

## One match before it has a place in the list.
##
## `rank` is the tier, from [score] for a title row and from the table at
## [answer] for a section of the text; `weight` orders the rows of one tier
## (0 for every title row, whose ties are broken by index order).
type Scored = { id: Int, group: Int, rank: Int, weight: Int }

## The ids of the entries a query answers, in the order the panel shows them.
##
## This is the whole cost of a keystroke, and it is paid once: [update] runs it
## when the query changes and keeps the answer in the model, and neither view
## nor a key that only moves the selection runs it again.
pub fn search(state: State, query: String) -> List[Int] = answer(state, query, -1).hits

## What one walk of the index answers for a query narrowed to `scope`.
##
## `scope` is the scope that was actually applied: a group the query matched
## nothing in is not kept, and the answer falls back to all of them, so a
## reader who narrowed to Spec and then typed a word only the standard
## library has sees its results rather than an empty list beside a pill that
## says why.
##
## `need` is the sections whose text, were it here, would change the answer:
## the candidates of a Chinese phrase query that could not be checked and are
## near enough the top of the order to matter ([verify_cap]). The rows on
## screen are not in it; those are asked for by their place in `hits`
## ([visible_secs]). `words` is the chunks of the text's index the query
## needs and that are not here: while it is not empty the text answers nothing
## (the answer would be a guess), and the titles answer alone.
pub type Answer = { hits: List[Int], counts: List[Int], scope: Int, need: List[Int], words: List[Int] }

##
## The tiers, best first. A title row is above every section of the text,
## because a title that answers is the reader's destination named, and a
## paragraph is somewhere inside one (the field weighting MiniSearch and
## DocSearch use: title over body):
##
##   5..1  a title row, by [score]
##   0     a section with a paragraph that has every word of the query (and,
##         for Chinese, every phrase of it in the paragraph's text)
##   -1    a section whose paragraphs have every character of a Chinese
##         phrase, but whose text has not arrived to say whether the phrase
##         is there
##   -2    a query of three words or more that no paragraph has all of: a
##         section with a paragraph that has at least half of them ([most])
##
## A section whose title row answered too is not a second row: the title row
## stands for it. The text's sections count in the scope pills like any row.
pub fn answer(state: State, query: String, scope: Int) -> Answer = {
  let q = str.to_lower(str.trim(query))
  if q == "" {
    Answer { hits: [], counts: [], scope: -1, need: [], words: [] }
  } else {
    let ts = terms(q)
    let titles = matches(state.keys, q, ts)
    let bodies = text_rows(state, q, titles)
    let found = titles ++ text_scored(state, bodies)
    let counts = list.map(range(0, groups().len()), g => list.filter(found, s => s.group == g).len())
    let kept = if scope >= 0 && scope < len(counts) && counts[scope] > 0 { scope } else { -1 }
    let narrowed = if kept >= 0 { list.filter(found, s => s.group == kept) } else { found }
    Answer {
      hits: list.map(arrange(narrowed), id => shown_id(state, bodies, id, ts)),
      counts: counts,
      scope: kept,
      need: unchecked(state, bodies),
      words: body_need(state, q),
    }
  }
}

## How far down the ordered sections of the text an unchecked one is still
## worth asking the text of. The candidates of a two-character phrase are every
## paragraph that has both characters somewhere, and a common pair has far more
## of them than the panel can show; asking them all would cost as much as the
## whole text. So only the sections in the first [verify_cap] places of the
## order are asked, the order being the one the rows will take (sure before
## unchecked, heavier before lighter). A section that is checked and has the
## phrase moves up and one that has not drops out, so the places fill with
## checked sections or run out of candidates, and the asking stops there
## (design 13.7, measured in 13.9).
pub fn verify_cap() -> Int = 10

## How many sections' text one query may ask for only to check a phrase. The
## places in the order fill with checked sections only if enough candidates
## have the phrase; when it is rare among them (`内存`: most paragraphs with
## both characters are about something else) filling them would mean asking for
## every candidate, which is the whole-text download again by another road. So
## the checking stops after this many, and the candidates left unchecked stay in
## the tier below the sure ones, where an unchecked candidate always was.
pub fn verify_total() -> Int = 12

## The sections of `bodies` in the first [verify_cap] places that are in the
## "may have the phrase" tier because their text is not here. A section whose
## fragment was asked for already or failed is not asked again; that is
## [wanting]'s test and the `texts` test here.
fn unchecked(state: State, bodies: List[BodyHit]) -> List[Int] = {
  let order = sort_by(bodies, (a, b) => if a.rank != b.rank { b.rank - a.rank } else { b.weight - a.weight })
  list.map(list.filter(list.take(order, verify_cap()), h => h.rank == -1 && not map.has(state.texts, h.sec)), h => h.sec)
}

## The sections of the text as matches: the `i`th is id `body_base() + i`
## until [shown_id] knows which of its paragraphs it shows.
fn text_scored(state: State, bodies: List[BodyHit]) -> List[Scored] = {
  var out: List[Scored] = []
  var i = 0
  for h in bodies {
    out = out ++ [Scored { id: body_base() + i, group: sec_group(state, h.sec), rank: h.rank, weight: h.weight }]
    i = i + 1
  }
  out
}

## The sections of the text that answer and are not already a title row that
## answered, in a group the panel draws.
fn text_rows(state: State, q: String, titles: List[Scored]) -> List[BodyHit] = {
  let ids = list.map(titles, s => s.id)
  list.filter(body_hits(state, q), h => {
    let s = sec_at(state, h.sec)
    s.group >= 0 && not (s.entry >= 0 && has_sorted(ids, s.entry))
  })
}

fn sec_at(state: State, sec: Int) -> Sec =
  match state.body {
    Some(b) -> b.secs.get(sec)
      .unwrap_or(Sec { doc: "", href: "", title: "", group: -1, entry: -1, frag: "" })
    None -> Sec { doc: "", href: "", title: "", group: -1, entry: -1, frag: "" }
  }

fn sec_group(state: State, sec: Int) -> Int = sec_at(state, sec).group

## The id the model keeps for a row [arrange] placed: a title row's own, and
## for the `i`th section of the text, the paragraph its row shows. Choosing
## that paragraph waits until here, so it is done for the rows on screen and
## not for every section that answered.
fn shown_id(state: State, bodies: List[BodyHit], id: Int, ts: List[Term]) -> Int =
  if id < body_base() {
    id
  } else {
    body_base() + shown_para(state, bodies[id - body_base()], ts)
  }

## Every entry that answers, in index order.
##
## The conditional is the whole of the filter: an entry that does not match is
## not kept at all, rather than kept with a zero score for somebody further on
## to drop. An entry whose group the panel does not draw is not kept either.
fn matches(keys: List[Key], q: String, ts: List[Term]) -> List[Scored] = {
  var out: List[Scored] = []
  var id = 0
  for k in keys {
    let r = score(k, q, ts)
    if r > 0 && k.group >= 0 {
      out = out ++ [Scored { id: id, group: k.group, rank: r, weight: 0 }]
    }
    id = id + 1
  }
  out
}

## The matches, grouped, best group first and best first within a group.
##
## A group's place is its best rank, with the panel's own order breaking ties,
## so a query whose best answer is a section of the spec shows the spec first
## even though the standard library is listed first. Within a group the order
## is rank, then weight, then index order: `sort_by` is stable.
fn arrange(found: List[Scored]) -> List[Int] = {
  let best_first = sort_by(found, (a, b) => if a.rank != b.rank { b.rank - a.rank } else { b.weight - a.weight })
  var per: List[List[Scored]] = []
  for g in range(0, groups().len()) {
    let mine = list.filter(best_first, s => s.group == g)
    if len(mine) > 0 {
      per = per ++ [mine]
    }
  }
  let order = sort_by(per, (a, b) => b[0].rank - a[0].rank)
  let quota = list.map(order, xs => len(xs)).shares(cap())
  var out: List[Int] = []
  for i in range(0, len(order)) {
    for s in list.take(order[i], quota[i]) {
      out = out ++ [s.id]
    }
  }
  out
}

## How many rows each group shows when `limit` are dealt one per group per
## round, in order, until they run out.
##
## Round-robin rather than first come: with a shared cap, a broad query whose
## best group has forty matches would show that group alone, and the one
## tutorial chapter that answered it as well would never be on screen.
pub fn shares(sizes: List[Int], limit: Int) -> List[Int] = {
  var rounds = 0
  while rounds < limit && one_more(sizes, rounds, limit) {
    rounds = rounds + 1
  }
  var left = limit - dealt(sizes, rounds)
  var out: List[Int] = []
  for n in sizes {
    if n > rounds && left > 0 {
      out = out ++ [rounds + 1]
      left = left - 1
    } else {
      out = out ++ [if n < rounds { n } else { rounds }]
    }
  }
  out
}

## Whether a round after `r` deals anything, and stays within `limit`.
fn one_more(sizes: List[Int], r: Int, limit: Int) -> Bool =
  dealt(sizes, r + 1) <= limit && dealt(sizes, r + 1) > dealt(sizes, r)

## How many rows `r` full rounds deal.
fn dealt(sizes: List[Int], r: Int) -> Int =
  list.fold(sizes, 0, (acc, n) => acc + (if n < r { n } else { r }))

# ---- near misses -----------------------------------------------------------
#
# When nothing answers a query, a word of it may be a slip of the fingers:
# `handel` for `handle`, `efect` for `effect`. The panel then looks for the
# words the index does have that are a small edit away, asks the query again
# with them, and offers the first such query that has answers, with how many
# -- one line in the empty state, never a correction of its own. What the
# reader typed is what was searched; the suggestion is a button.
#
# All of this runs only when the titles and the text both answered nothing
# ([asked]), so a keystroke that finds something pays none of it.

## How many edits a query word of `n` code points may be from a word it is
## taken for: none under three code points, where one edit reaches too many
## words to mean anything, one up to four, two from five on.
pub fn allowed(n: Int) -> Int = if n >= 5 { 2 } else if n >= 3 { 1 } else { 0 }

## The edit distance from `a` to `b`, counting an insertion, a deletion, a
## substitution and a swap of two neighbours as one edit each (the optimal
## string alignment distance), or `limit + 1` as soon as it is known to be
## more than `limit`.
##
## The swap is one edit because it is the commonest slip there is, and plain
## Levenshtein would count it as two: `handel` would then be as far from
## `handle` as from `hand`, and `wiht`, four letters, would not reach `with`
## at all.
pub fn distance(a: String, b: String, limit: Int) -> Int = {
  let xs0 = code_points(a)
  let ys0 = code_points(b)
  if len(xs0) - len(ys0) > limit || len(ys0) - len(xs0) > limit {
    limit + 1
  } else {
    # What the two share at either end costs nothing, and most pairs that
    # are near at all share most of themselves: `sturct` and `struct` leave
    # `ur` and `ru` to the table.
    var lead = 0
    while lead < len(xs0) && lead < len(ys0) && xs0[lead] == ys0[lead] {
      lead = lead + 1
    }
    var tail = 0
    while tail < len(xs0) - lead && tail < len(ys0) - lead && xs0[len(xs0) - 1 - tail] == ys0[len(ys0) - 1 - tail] {
      tail = tail + 1
    }
    let xs = list.slice(xs0, lead, len(xs0) - tail)
    let ys = list.slice(ys0, lead, len(ys0) - tail)
    let d = table(xs, ys, limit)
    if d > limit { limit + 1 } else { d }
  }
}

## The distance table, one row at a time, given up on as soon as a whole row
## is past `limit`. Only the cells within `limit` of the diagonal are worked
## out; the rest cannot lead anywhere within reach and stand at `limit + 1`.
fn table(xs: List[Char], ys: List[Char], limit: Int) -> Int = {
  let n = len(xs)
  let m = len(ys)
  let far = limit + 1
  var before: List[Int] = []
  var prev: List[Int] = list.map(range(0, m + 1), j => if j > limit { far } else { j })
  var over = false
  var i = 1
  while i <= n && not over {
    var cur: List[Int] = [if i > limit { far } else { i }]
    var least = cur[0]
    for j in range(1, m + 1) {
      var d = far
      if j - i <= limit && i - j <= limit {
        let same = xs[i - 1] == ys[j - 1]
        d = prev[j - 1] + (if same { 0 } else { 1 })
        if prev[j] + 1 < d {
          d = prev[j] + 1
        }
        if cur[j - 1] + 1 < d {
          d = cur[j - 1] + 1
        }
        if i > 1 && j > 1 && xs[i - 1] == ys[j - 2] && xs[i - 2] == ys[j - 1] && before[j - 2] + 1 < d {
          d = before[j - 2] + 1
        }
        if d > far {
          d = far
        }
      }
      cur = cur ++ [d]
      if d < least {
        least = d
      }
    }
    over = least > limit
    before = prev
    prev = cur
    i = i + 1
  }
  if over { far } else { prev[m] }
}

## A word of the index a query word may have meant: how many edits away it
## is, and how many entries and paragraphs have it.
pub type Near = { word: String, dist: Int, freq: Int }

## The words of the index a query word `w` may have meant, and whether the
## index has `w` itself, so that it is no slip: whole, or as the start of a
## word when it is the query's last, which the reader may still be typing.
##
## `words` are the words that begin with the letter `w` begins with and are
## within `limit` code points of its length, each with how many title rows
## and paragraphs have it. The bucket is the first letter. Every word of the
## text that begins with it is one run of the sorted word list (two binary
## searches); the titles' words are not sorted anywhere, and rather than sort
## them at every init for a branch most keystrokes never take, they are
## walked here, which is one comparison of a first letter per word. A slip in
## the first letter is not looked for: it would mean a distance against every
## word of the index, which is what the research measured at 12.5 ms of wasm
## (report 1.8), and the first letter is the one a reader is least likely to
## get wrong. Search engines that tolerate typos make the same trade
## (Elasticsearch's fuzzy `prefix_length`).
type Pool = { known: Bool, words: Map[String, Int] }

fn bucket(state: State, w: String, last: Bool, limit: Int) -> Pool = {
  let first = str.take(w, 1)
  let n = len(w)
  var known = false
  var out: Map[String, Int] = map.empty()
  for k in state.keys {
    if k.group >= 0 && not known {
      for x in k.words {
        if str.starts_with(x, first) {
          if x == w || (last && str.starts_with(x, w)) {
            known = true
          }
          let xn = len(x)
          if xn - n <= limit && n - xn <= limit {
            out = map.insert(out, x, map.get(out, x).unwrap_or(0) + 1)
          }
        }
      }
    }
  }
  match state.body {
    None -> ()
    Some(b) -> {
      if body_has(state, b, w, last) {
        known = true
      }
      if not known {
        # the first letter's words, from whichever chunks are here
        for ci in chunks_for(b, first, true) {
          let c = posts_at(state, ci)
          let lo = lower_bound(c.terms, first)
          for i in range(lo, past_prefix(c.terms, first, lo)) {
            let x = c.terms[i]
            let xn = len(x)
            if xn - n <= limit && n - xn <= limit {
              out = map.insert(out, x, map.get(out, x).unwrap_or(0) + len(c.posts[i]))
            }
          }
        }
      }
    }
  }
  Pool { known: known, words: out }
}

## Whether the text's index has the word `w`, or a word starting with it when
## `prefix`, among the chunks that are here.
fn body_has(state: State, b: Body, w: String, prefix: Bool) -> Bool =
  list.any(chunks_for(b, w, prefix), ci => {
    let c = posts_at(state, ci)
    let at = lower_bound(c.terms, w)
    at < len(c.terms) && (c.terms[at] == w || (prefix && str.starts_with(c.terms[at], w)))
  })

## Whether a title of the index has the word `w` (or a word starting with it
## when `last`), which makes it no slip without looking at the text.
fn title_has(state: State, w: String, last: Bool) -> Bool =
  list.any(state.keys, k => k.group >= 0 && list.any(k.words, x => x == w || (last && str.starts_with(x, w))))

## The chunks [reach] would read for the word `w` and that are not here: the
## ones the word itself is in, and when the titles and those do not have it,
## the first letter's. Asked in that order, one step at a time, so that a
## correctly spelled word costs the first step only.
fn reach_need(state: State, w: String, last: Bool) -> List[Int] = {
  let limit = len(w).allowed()
  let ascii = list.all(code_points(w), c => char.code(c) < 128)
  match state.body {
    None -> []
    Some(b) ->
      if limit == 0 || not ascii || title_has(state, w, last) {
        []
      } else {
        let own = state.not_here(chunks_for(b, w, last))
        if len(own) > 0 {
          own
        } else if body_has(state, b, w, last) {
          []
        } else {
          state.not_here(chunks_for(b, str.take(w, 1), true))
        }
      }
  }
}

## What a query word may have meant: nothing when the index has it, and
## otherwise the words of its bucket within [allowed] edits, nearest first,
## then commonest, then in code-point order. Only ASCII words are looked at:
## Chinese is searched one character at a time and a character either is in
## the index or is not, and an edit distance between two letters of another
## alphabet says nothing a reader would recognise.
pub fn near_words(state: State, w: String, last: Bool) -> List[Near] = reach(state, w, last).near

## [near_words], and whether the word is one the index lacks with nothing near
## it either: a word no query made from this one can find.
type Reach = { dead: Bool, near: List[Near] }

fn reach(state: State, w: String, last: Bool) -> Reach = {
  let limit = len(w).allowed()
  let ascii = list.all(code_points(w), c => char.code(c) < 128)
  if limit == 0 || not ascii {
    Reach { dead: false, near: [] }
  } else {
    let pool = bucket(state, w, last, limit)
    if pool.known {
      Reach { dead: false, near: [] }
    } else {
      let seen = letters(w)
      var out: List[Near] = []
      for e in map.entries(pool.words) {
        let (x, freq) = e
        if strangers(x, seen, limit) <= limit {
          let d = distance(w, x, limit)
          if d > 0 && d <= limit {
            out = out ++ [Near { word: x, dist: d, freq: freq }]
          }
        }
      }
      Reach {
        dead: len(out) == 0,
        near: sort_by(out, (a, b) =>
            if a.dist != b.dist { a.dist - b.dist } else if a.freq != b.freq { b.freq - a.freq } else { order(a.word, b.word) }),
      }
    }
  }
}

## Which of the 128 ASCII code points `w` has.
fn letters(w: String) -> List[Bool] = {
  let ks = list.map(code_points(w), c => char.code(c))
  list.map(range(0, 128), k => list.contains(ks, k))
}

## How many characters of `x` are not among `seen`, counted up to one past
## `limit`. Each of them is an edit on its own -- a swap brings no character
## in -- so a word with more of them than the limit is out of reach, and the
## table is not drawn for it. Most of a bucket goes here: `sturct` has no
## `o`, `p` or `e`, and `scope` is three edits away before anything is
## compared.
fn strangers(x: String, seen: List[Bool], limit: Int) -> Int = {
  var at = cursor.start(x)
  var n = 0
  while n <= limit && not cursor.done(x, at) {
    let k = cursor.char(x, at)
    if k >= 128 || not seen[k] {
      n = n + 1
    }
    at = cursor.next(x, at)
  }
  n
}

## How many words each query word may become while the panel looks for a
## query that answers, and how many such queries it asks before it gives up.
## Each one asked is a search of both indexes, about 2 ms of wasm; two is
## what keeps a query of three slips nothing answers under the budget
## (docs/site-search-design.md 10.3).
fn near_cap() -> Int = 3

fn tries_cap() -> Int = 2

## One query the panel may suggest: its words, and how many edits they are
## from the reader's, in all.
type Guess = { words: List[String], dist: Int }

## A query like `q` that answers, and how many rows it answers with: `("",
## 0)` when no word of `q` has a near miss, or none of the queries made from
## them answers.
##
## Every word the index lacks is replaced by one of its nearest words, the
## others kept, and the queries so made are asked fewest edits first -- at
## most [tries_cap] of them. The count is what the suggested query answers
## when asked ([tally_of]), which is the number the reader gets by taking it.
pub fn suggest(state: State, q: String) -> (String, Int) = {
  let (fix, n, _) = suggest_plan(state, q)
  (fix, n)
}

## [suggest], and the chunks of the text's index it still needs before it can
## say: when the list is not empty the first two are not an answer, they are
## "ask again once these are here". It is asked in the order the work goes in:
## the chunks the query's words are in (and the first letters', for a word
## that is no word), then the chunks of each query it would try, one query at
## a time, so that a first guess that answers costs no chunks for the second.
pub fn suggest_plan(state: State, q: String) -> (String, Int, List[Int]) = {
  let ts = str.to_lower(str.trim(q)).terms()
  var reads: List[Int] = []
  var at = 0
  for t in ts {
    for c in reach_need(state, t.word, at == len(ts) - 1) {
      if not list.contains(reads, c) {
        reads = reads ++ [c]
      }
    }
    at = at + 1
  }
  if len(reads) > 0 {
    ("", 0, reads)
  } else {
    suggest_ready(state, ts)
  }
}

fn suggest_ready(state: State, ts: List[Term]) -> (String, Int, List[Int]) = {
  var guesses: List[Guess] = [Guess { words: [], dist: 0 }]
  var changed = false
  var dead = 0
  var i = 0
  for t in ts {
    let r = reach(state, t.word, i == len(ts) - 1)
    let near = r.near
    if r.dead {
      dead = dead + 1
    }
    # past nine queries in hand, a word adds its nearest only, so that a long
    # query of slips does not multiply into hundreds
    let options =
      if len(near) == 0 {
        [Near { word: t.word, dist: 0, freq: 0 }]
      } else {
        list.take(near, if len(guesses) >= 9 { 1 } else { near_cap() })
      }
    if len(near) > 0 {
      changed = true
    }
    var next: List[Guess] = []
    for g in guesses {
      for o in options {
        next = next ++ [Guess { words: g.words ++ [o.word], dist: g.dist + o.dist }]
      }
    }
    guesses = next
    i = i + 1
  }
  # Under three words every word has to be found (the sentence tier of
  # [most] starts at three), so a word nothing is near sinks every query
  # made from this one, and none is asked.
  if not changed || (dead > 0 && len(ts) < 3) {
    ("", 0, [])
  } else {
    var found = ""
    var count = 0
    var tried = 0
    var pending: List[Int] = []
    for g in sort_by(guesses, (a, b) => a.dist - b.dist) {
      if found == "" && tried < tries_cap() && len(pending) == 0 {
        let fix = join(g.words, " ")
        let missing = body_need(state, str.to_lower(str.trim(fix)))
        if len(missing) > 0 {
          pending = missing
        } else {
          let n = tally_of(state, fix)
          if n > 0 {
            found = fix
            count = n
          }
          tried = tried + 1
        }
      }
    }
    if len(pending) > 0 { ("", 0, pending) } else { (found, count, []) }
  }
}

## How many rows `query` answers in all, before any narrowing or cap: the sum
## of its scope pills' counts, without arranging or excerpting anything.
pub fn tally_of(state: State, query: String) -> Int = {
  let q = str.to_lower(str.trim(query))
  if q == "" {
    0
  } else {
    let titles = matches(state.keys, q, terms(q))
    len(titles) + state.text_rows(q, titles).len()
  }
}

# ---- the scan: two cells in one handler ------------------------------------

## The model's hits, numbered, and the href the selection lands on.
##
## The two cells are the reason this is a handler and not a fold. `hits` is
## the accumulation; `chosen` is decided by comparing the running ordinal --
## which is `len(hits)` at the moment the arm runs, and which nothing outside
## the arm can see -- against the selection the model carries. A fold could
## carry both in a pair, at the cost of threading that pair through [probe];
## the point of the cells is that [probe]'s signature says `!Found` and says
## nothing about what is being accumulated.
##
## It walks at most [cap] ids, not the index: the ranking is [search]'s, and
## happened when the query last changed.
pub fn scan(state: State, ids: List[Int], sel: Int) -> Scan = {
  with handle Found {
    var hits: List[Hit] = []
    var chosen: String = ""
    found(e, text) => {
      if len(hits) == sel {
        chosen = e.href
      }
      hits = hits ++ [Hit { entry: e, at: len(hits), text: text }]
    }
  }
  probe(state, ids)
  Scan { hits: hits, chosen: chosen }
}

## Perform `found` once per id, in the model's order. An id that names no
## entry is passed over: a model is text the page hands back, and a page may
## hand back anything.
fn probe(state: State, ids: List[Int]) -> Unit !Found = {
  for id in ids {
    match entry_at(state, id) {
      Some(e) -> found(e, id >= body_base())
      None -> ()
    }
  }
}

## What a row of the model's hits shows: a title row as the index has it, and
## a paragraph of the text as its section, with the paragraph as the note.
## The section's title takes the title's place and where it is takes the
## signature's, so a row of the text is drawn by the same [row] as any other.
fn entry_at(state: State, id: Int) -> Option[Entry] =
  if id < body_base() {
    get(state.entries, id)
  } else {
    match state.body {
      None -> None
      Some(b) ->
        match get(b.paras, id - body_base()) {
          None -> None
          Some(p) ->
            match get(b.secs, p.sec) {
              None -> None
              Some(s) ->
                if s.group < 0 {
                  None
                } else {
                  Some(Entry {
                    group: groups()[s.group].id,
                    title: s.title,
                    detail: crumb(s, state.lang),
                    note: match para_text(state, id - body_base()) {
                      Some(t) -> excerpt(t)
                      None -> ""
                    },
                    href: s.href,
                  })
                }
            }
        }
    }
  }

# ---- the view: a collector inside a collector ------------------------------

## Run `body` and answer everything it emitted, in the order it emitted it.
##
## The row `!Emit !Ctx` is what lets this be nested inside itself while the
## reader effect passes straight through: `Emit` is taken off by the handler
## here, `Ctx` is not, so a body that asks the page where it is stays honest
## all the way up to the one installation in [view].
fn collect(body: fn() -> Unit !Emit !Ctx) -> List[Node[Msg]] !Ctx = {
  with handle Emit {
    var acc: List[Node[Msg]] = []
    emit(w) => { acc = acc ++ [w] }
  }
  body()
  acc
}

## An href on this page, given one relative to the site root.
fn link(href: String) -> String !Ctx = "${root()}/${href}"

## The ids the combobox pattern ties together. There is one panel per page,
## so a fixed prefix is unique, and an option's id is its ordinal: the same
## number the arrow keys move, which is what lets `aria-activedescendant` be
## computed from the model rather than looked up in the tree.
fn list_id() -> String = "dawn-search-list"

fn option_id(at: Int) -> String = "dawn-search-opt-${at}"

fn group_id(g: Group) -> String = "dawn-search-g-${g.id}"

## Which of the three section hues a group's dot takes. By the group's place in
## [groups] rather than on screen, so a group keeps its colour while the
## ranking moves it up and down the panel.
fn hue_of(g: Group) -> Int = group_index(g.id) % 3 + 1

## One result row. `chosen` decides the class and `aria-selected` and nothing
## else, so moving the selection is one `set-self` per row that changed and no
## rebuild.
##
## The anchor is out of the tab order: the field owns the keyboard and the
## rows are reached with the arrows, the combobox pattern's rule. It stays an
## anchor so that a click (or a middle click) is the browser's own navigation.
## The pointer moves the selection too, through `mouseenter`, so the row the
## mouse is on and the row Enter opens are never two different rows.
fn row(h: Hit, chosen: Bool, ts: List[Term]) -> Node[Msg] !Ctx = {
  let e = h.entry
  let at = h.at
  # the name and its signature share a line and shrink together; the note
  # takes the line below
  let head: List[Node[Msg]] = [
    el("span", class: "search-head", kids: [
      el("span", class: "search-title", kids: marked(e.title, ts)),
      span(e.detail, class: "search-detail"),
    ]),
  ]
  let link_kids = head ++ note_kids(e, ts)
  let kind = if h.text { "search-row search-text" } else { "search-row" }
  el("li", option_props(at, chosen), class: if chosen { "${kind} is-selected" } else { kind },
    on: [hover_on(at)], kids: [el("a", [("href", link(e.href)), ("tabindex", "-1")], kids: link_kids)])
}

## What makes an `<li>` the option with ordinal `at`.
fn option_props(at: Int, chosen: Bool) -> List[(String, String)] = [
  ("id", option_id(at)),
  ("role", "option"),
  ("aria-selected", if chosen { "true" } else { "false" }),
]

fn hover_on(at: Int) -> On[Msg] = On { event: "mouseenter", payload: NoData, to_msg: _p => Hovered(at: at) }

## The one-line note, when there is one. A row with no note has no element for
## it rather than an empty one, which is the same rule the sections follow.
fn note_kids(e: Entry, ts: List[Term]) -> List[Node[Msg]] =
  if e.note == "" { [] } else { [el("span", class: "search-note", kids: marked_runs(e.note, ts))] }

## A note's text, with each backticked span as a `<code>`.
##
## Doc comments in this repository write code between backticks, and a note
## is the first sentence of one. A backtick with no partner -- a note cut
## inside a span -- is shown as the character it is.
pub fn note_runs(note: String) -> List[Node[Msg]] = marked_runs(note, [])

## [note_runs], with the query's words marked inside both kinds of run.
fn marked_runs(note: String, ts: List[Term]) -> List[Node[Msg]] = {
  let parts = str.split(note, "`")
  let unpaired = len(parts) % 2 == 0
  var out: List[Node[Msg]] = []
  var i = 0
  for p in parts {
    if unpaired && i == len(parts) - 1 {
      out = out ++ marked("`" ++ p, ts)
    } else if i % 2 == 1 {
      out = out ++ [el("code", kids: marked(p, ts))]
    } else if p != "" {
      out = out ++ marked(p, ts)
    }
    i = i + 1
  }
  out
}

## `s` as text, with every place a word of the query is found wrapped in a
## `<mark>`.
##
## Where a word counts as found follows [fits] loosely: an ASCII word where a
## word of `s` begins (so `read` marks `io.read_file` but not `bread`), and
## where one ends too unless it is the word still being typed (so `the` marks
## `the` and not the start of `then`), a word beyond ASCII anywhere, since a
## Chinese run has no word starts inside it. The mark is for the eye and
## decides nothing; a row that matched through its signature alone simply has
## nothing marked.
##
## Positions are code points of the lowercased text, laid over the original.
## A string whose lowercase has a different number of code points is left
## unmarked rather than marked in the wrong place.
pub fn marked(s: String, ts: List[Term]) -> List[Node[Msg]] = {
  let low = str.to_lower(s)
  let n = len(s)
  if s == "" {
    []
  } else if len(ts) == 0 || len(low) != n {
    [text(s)]
  } else {
    var spans: List[(Int, Int)] = []
    for t in ts {
      spans = spans ++ places(low, t)
    }
    let sorted = sort_by(spans, (a, b) => {
      let (x, _) = a
      let (y, _) = b
      x - y
    })
    var out: List[Node[Msg]] = []
    var pos = 0
    var open_at = -1
    var open_to = -1
    for sp in sorted {
      let (a, b) = sp
      if open_at >= 0 && a <= open_to {
        if b > open_to {
          open_to = b
        }
      } else {
        if open_at >= 0 {
          out = out ++ plain_then_mark(s, pos, open_at, open_to)
          pos = open_to
        }
        open_at = a
        open_to = b
      }
    }
    if open_at >= 0 {
      out = out ++ plain_then_mark(s, pos, open_at, open_to)
      pos = open_to
    }
    if pos < n {
      let tail: Node[Msg] = text(str.slice(s, pos, n))
      out = out ++ [tail]
    }
    out
  }
}

fn plain_then_mark(s: String, pos: Int, a: Int, b: Int) -> List[Node[Msg]] = {
  let lead: List[Node[Msg]] = if a > pos { [text(str.slice(s, pos, a))] } else { [] }
  let hit: Node[Msg] = el("mark", kids: [text(str.slice(s, a, b))])
  lead ++ [hit]
}

## Where `t` is found in `low`, as code-point spans.
fn places(low: String, t: Term) -> List[(Int, Int)] = {
  let w = t.word
  let wl = len(w)
  var out: List[(Int, Int)] = []
  var from = 0
  var go = wl > 0
  while go {
    match str.index_of(str.drop(low, from), w) {
      Some(i) -> {
        let p = from + i
        let starts = p == 0 || char.code(str.at(low, p - 1)).kind_of() != 3
        let ends = t.fit != Whole || p + wl >= len(low) || char.code(str.at(low, p + wl))
          .kind_of() != 3
        if t.fit == Within || (starts && ends) {
          out = out ++ [(p, p + wl)]
        }
        from = p + 1
      }
      None -> {
        go = false
      }
    }
  }
  out
}

## The rows of one group. The inner collector: its installation shadows the
## outer one for the length of the body, so these `emit`s land here and the
## sections collector never sees them.
fn rows_of(hits: List[Hit], g: Group, sel: Int, ts: List[Term]) -> List[Node[Msg]] !Ctx =
  collect(() => {
    for h in hits {
      if h.entry.group == g.id {
        emit(row(h, h.at == sel, ts))
      }
    }
  })

## Every group that has something to show, in the order the hits name them.
##
## The outer collector. A group with no rows emits nothing -- not an empty
## section, not a placeholder -- which is why the answer's length is the
## number of groups that matched rather than five.
fn sections(hits: List[Hit], sel: Int, ts: List[Term]) -> List[Node[Msg]] !Ctx =
  collect(() => {
    for g in panel_order(hits) {
      let rows: List[Node[Msg]] = rows_of(hits, g, sel, ts)
      if len(rows) > 0 {
        emit(section(g, rows))
      }
    }
  })

## The groups in the order their first hit comes in, the rest after them.
## [search] keeps a group's hits together, so this is the order it ranked the
## groups in.
fn panel_order(hits: List[Hit]) -> List[Group] = {
  let gs = groups()
  sort_by(gs, (a, b) => first_at(hits, a.id) - first_at(hits, b.id))
}

## The ordinal of the first hit in group `id`, or one past the last hit.
fn first_at(hits: List[Hit], id: String) -> Int =
  match list.find(hits, h => h.entry.group == id) {
    Some(h) -> h.at
    None -> len(hits)
  }

## A group: its heading, then its rows as an ARIA group named by the heading.
## The `<li>` itself is presentation, so a screen reader walking the listbox
## meets groups and options and nothing else.
fn section(g: Group, rows: List[Node[Msg]]) -> Node[Msg] !Ctx =
  el("li", [("role", "presentation")], class: "search-group hue-${hue_of(g)}", kids: [
    el("div", [("id", group_id(g))], class: "search-group-name", kids: [
      text(group_label(g, lang())),
      span("${len(rows)}", class: "search-group-count"),
    ]),
    el("ul", [("role", "group"), ("aria-labelledby", group_id(g))], class: "search-group-rows",
      kids: rows),
  ])

## The link Enter chose, for the page's script to follow. It carries
## `data-goto` because a page reads markup and not a model: the script looks
## for that attribute after every keystroke and navigates when it appears.
fn goto_kids(m: Model) -> List[Node[Msg]] !Ctx =
  if m.goto == "" {
    []
  } else {
    [el("a", [("href", link(m.goto)), ("data-goto", "1")], class: "search-goto",
      kids: [text(m.goto)])]
  }

## What the list area holds when there is nothing to list: a reason, not a
## blank. The two reasons are different -- an empty query has not been asked
## anything yet (and says so only when there is no recent query and no
## suggestion to show instead), a query with no hits has.
##
## A query whose words are still being fetched ([Model]'s `loading`) has not
## been answered, so it says nothing yet rather than that nothing matches.
##
## The region is there whether or not it says anything, because a live region
## that is inserted along with its text is one a screen reader may never
## announce; one that already exists and changes is announced.
fn status(m: Model, shown: Bool) -> Node[Msg] !Ctx = {
  let q = str.trim(m.query)
  let say_it: List[Node[Msg]] =
    if shown {
      []
    } else if q == "" {
      [el("p", class: "search-status", kids: [text(lang().prompt_line())])]
    } else if len(m.loading) > 0 {
      # words of the text's index are on their way: "nothing" is not yet an answer
      []
    } else {
      [el("div", class: "search-nothing", kids: nothing(lang(), q, m.fix, m.fix_hits))]
    }
  el("div", [("role", "status")], class: "search-none", kids: say_it)
}

## A query nothing answered: what was asked, the query the panel guesses was
## meant when it has one ([fix_line]), and three ways to ask again.
##
## Each tip names its examples in `<code>`, because what a reader types next
## is the example, letter for letter. The tips are about the panel as it is --
## a title and API-name index that splits on words.
##
## The picture is a small sunrise over the horizon line, drawn by the
## stylesheet: the element is empty and hidden from assistive technology, and
## an `<svg>` built here would not render, because tea_dom creates every
## element in the HTML namespace.
fn nothing(code: String, q: String, fix: String, fix_hits: Int) -> List[Node[Msg]] = {
  let head: List[Node[Msg]] = [
    el("div", [("aria-hidden", "true")], class: "search-none-art"),
    el("p", class: "search-none-title",
      kids: [text(say(code, "Nothing matches “${q}”.", "没有匹配「${q}」的结果。"))]),
  ]
  head ++ fix_line(code, fix, fix_hits) ++ tips(code)
}

## The three tips under a query nothing answered.
fn tips(code: String) -> List[Node[Msg]] = [
  el("ul", class: "search-tips", kids: [
    tip(if code == "zh-CN" {
      ["API 请用英文名：", "read_file", "，而不是", "读文件", "。"]
    } else {
      ["Try the English name of an API: ", "read_file", ", not ", "读文件", "."]
    }),
    tip(if code == "zh-CN" {
      ["符号要么去掉，要么整个保留：", "!io", "、", "with handle", "。"]
    } else {
      ["Drop symbols, or keep them whole: ", "!io", ", ", "with handle", "."]
    }),
    tip(if code == "zh-CN" {
      ["搜标题：", "效果系统", "、", "教程 17", "。"]
    } else {
      ["Search a title: ", "Effect system", ", ", "Tutorial 17", "."]
    }),
  ]),
]

## "Did you mean `handle`? 9 results": the suggested query as a button that
## asks it, and how many rows it answers. Nothing when there is no suggestion.
##
## A button and not a link, though it is drawn as one: it goes nowhere, it
## fills the field and asks, with the same `Typed` a recent query sends.
## Enter in the field does the same ([pressed]).
fn fix_line(code: String, fix: String, n: Int) -> List[Node[Msg]] =
  if fix == "" {
    []
  } else {
    let found = if code == "zh-CN" { "${n} 条结果" } else if n == 1 { "1 result" } else { "${n} results" }
    [el("p", class: "search-fix", kids: [
      text(say(code, "Did you mean ", "你是想找 ")),
      el("button", [("type", "button")], class: "search-fix-term", on: [on_click(Typed(text: fix))],
        kids: [text(fix)]),
      text(say(code, "? ", "？")),
      span(found, class: "search-fix-count"),
    ])]
  }

## One tip: prose and examples taking turns, the examples as code.
fn tip(parts: List[String]) -> Node[Msg] = {
  var kids: List[Node[Msg]] = []
  var i = 0
  for p in parts {
    let k: Node[Msg] = if i % 2 == 1 { el("code", kids: [text(p)]) } else { text(p) }
    kids = kids ++ [k]
    i = i + 1
  }
  el("li", kids: kids)
}

# ---- the scope pills --------------------------------------------------------

## The row of scope pills: All, then each group, each with how many entries
## the query matched there. A filter over the matches the model already has,
## so a pill is one walk of the index like a keystroke, and nothing at all
## when the query has no matches or is not a query yet.
##
## The row is there either way, empty when it has nothing to say, so that
## the list after it keeps its place in the tree from one turn to the next.
## A pill with nothing in it is disabled rather than hidden: the row reads
## the same for every query, and a zero is an answer too.
fn pills(m: Model) -> Node[Msg] !Ctx = {
  let code = lang()
  let total = list.fold(m.counts, 0, (a, c) => a + c)
  var kids: List[Node[Msg]] = []
  if total > 0 && not idle(m) {
    kids = kids ++ [pill(say(code, "All", "全部"), total, -1, m.scope == -1)]
    var i = 0
    for g in groups() {
      let n = m.counts.get(i).unwrap_or(0)
      kids = kids ++ [pill(if code == "zh-CN" { g.pill_zh } else { g.pill_en }, n, i, m.scope == i)]
      i = i + 1
    }
  }
  el("div", [("role", "group"), ("aria-label", say(code, "Narrow to", "范围"))], class: "search-pills",
    kids: kids)
}

fn pill(name: String, n: Int, scope: Int, on: Bool) -> Node[Msg] = {
  let off: List[(String, String)] = if n == 0 { [("disabled", "")] } else { [] }
  let state_props: List[(String, String)] =
    [("type", "button"), ("aria-pressed", if on { "true" } else { "false" })] ++ off
  let cls = if on { "search-pill is-on" } else if n == 0 { "search-pill is-zero" } else { "search-pill" }
  el("button", state_props, class: cls, on: [on_click(Scoped(group: scope))],
    kids: [text(name), span("${n}", class: "search-pill-count")])
}

# ---- before anything is asked ----------------------------------------------

## Whether the field asks nothing, so the list shows the idle rows.
fn idle(m: Model) -> Bool = str.trim(m.query) == ""

## The suggested entries the index names, in its order. An id that names no
## entry, or an entry in a group the panel does not draw, is passed over: the
## index is a file the page fetched, and the guest trusts no more of it than
## it can check.
fn starts(state: State) -> List[Entry] = {
  var out: List[Entry] = []
  for id in state.start {
    match get(state.entries, id) {
      Some(e) -> {
        if group_index(e.group) >= 0 {
          out = out ++ [e]
        }
      }
      None -> ()
    }
  }
  out
}

## How many rows the list shows: the hits for a query, or the recent queries
## and the suggestions before one. The arrows, Home, End and the pointer are
## all bounded by this.
fn shown_rows(state: State, m: Model) -> Int =
  if idle(m) { len(state.recent) + state.starts().len() } else { len(m.hits) }

## What Enter does on an idle row: a recent query is asked again, which is the
## field taking that text, and a suggestion is opened like a result.
fn idle_choice(state: State, sel: Int) -> Cmd[Msg] = {
  let n = len(state.recent)
  if sel >= 0 && sel < n {
    SendMsg(msg: Typed(text: state.recent[sel]))
  } else {
    match state.starts().get(sel - n) {
      Some(e) -> SendMsg(msg: Chose(href: e.href))
      None -> NoCmd
    }
  }
}

## The idle list: Recent, then Start here, either one absent when it has no
## rows. The ordinals run across both, recent queries first, so one `sel`
## moves through the two groups as it moves through result groups.
fn idle_sections(state: State, sel: Int) -> List[Node[Msg]] !Ctx = {
  let code = lang()
  var recent_rows: List[Node[Msg]] = []
  var at = 0
  for q in state.recent {
    recent_rows = recent_rows ++ [recent_row(q, at, at == sel)]
    at = at + 1
  }
  var start_rows: List[Node[Msg]] = []
  for e in starts(state) {
    start_rows = start_rows ++ [start_row(e, at, at == sel)]
    at = at + 1
  }
  let clear: Node[Msg] =
    el("button", [("type", "button"), ("data-forget-all", "1")], class: "search-clear",
      kids: [text(say(code, "Clear", "清空"))])
  let recent: List[Node[Msg]] =
    if len(recent_rows) == 0 {
      []
    } else {
      [idle_group("recent", say(code, "Recent", "最近"), [clear], recent_rows)]
    }
  let start: List[Node[Msg]] =
    if len(start_rows) == 0 {
      []
    } else {
      [idle_group("start", say(code, "Start here", "从这里开始"), [], start_rows)]
    }
  recent ++ start
}

## An idle group, built like a result group: a heading, then the rows as an
## ARIA group named by it. `extra` is what the heading carries after its name.
fn idle_group(id: String, name: String, extra: List[Node[Msg]], rows: List[Node[Msg]]) -> Node[Msg] = {
  let head_id = "dawn-search-g-${id}"
  let named: List[Node[Msg]] = [text(name)]
  el("li", [("role", "presentation")], class: "search-group search-group-${id}", kids: [
    el("div", [("id", head_id)], class: "search-group-name", kids: named ++ extra),
    el("ul", [("role", "group"), ("aria-labelledby", head_id)], class: "search-group-rows",
      kids: rows),
  ])
}

## A recent query. Clicking it, or Enter on it, asks it again.
##
## The delete button is a sibling of the clickable part and not inside it, so
## a click on it is not also a click on the query; and it has no listener. It
## names the query in `data-forget`, and the page script, which owns the
## stored list, removes it there and starts the panel again.
fn recent_row(q: String, at: Int, chosen: Bool) -> Node[Msg] !Ctx = {
  let code = lang()
  el("li", option_props(at, chosen),
    class: if chosen { "search-row search-recent is-selected" } else { "search-row search-recent" },
    on: [hover_on(at)], kids: [
      el("span", class: "search-recall", on: [on_click(Typed(text: q))], kids: [
        el("span", [("aria-hidden", "true")], class: "search-icon search-icon-clock"),
        span(q, class: "search-title"),
      ]),
      el("button", [
        ("type", "button"),
        ("data-forget", q),
        ("aria-label", say(code, "Remove “${q}” from recent searches", "从最近搜索中删除「${q}」")),
      ], class: "search-forget"),
    ])
}

## A suggested entry: a link like a result's, with an arrow in its group's hue
## where a result has nothing.
fn start_row(e: Entry, at: Int, chosen: Bool) -> Node[Msg] !Ctx = {
  let hue = group_index(e.group) % 3 + 1
  el("li", option_props(at, chosen),
    class: if chosen { "search-row search-start hue-${hue} is-selected" } else { "search-row search-start hue-${hue}" },
    on: [hover_on(at)], kids: [
      el("a", [("href", link(e.href)), ("tabindex", "-1")], kids: [
        el("span", [("aria-hidden", "true")], class: "search-icon search-icon-go"),
        el("span", class: "search-head", kids: [
          span(e.title, class: "search-title"),
          span(e.detail, class: "search-detail"),
        ]),
      ]),
    ])
}

## The field: a combobox in the WAI-ARIA sense, whose popup is the result list
## and whose active option is the selection. Focus never leaves it while the
## arrows move; `aria-activedescendant` is how the selection is announced.
fn field(m: Model, shown: Int) -> Node[Msg] !Ctx = {
  let code = lang()
  let active: List[(String, String)] =
    if m.sel >= 0 && m.sel < shown {
      [("aria-activedescendant", option_id(m.sel))]
    } else {
      []
    }
  el("input", [
    ("value", m.query),
    ("type", "text"),
    ("role", "combobox"),
    ("aria-label", say(code, "Search the site", "搜索本站")),
    ("aria-expanded", if shown > 0 { "true" } else { "false" }),
    ("aria-controls", list_id()),
    ("aria-autocomplete", "list"),
  ] ++ active ++ [
    ("placeholder", placeholder(code, full_text())),
    ("autocomplete", "off"),
    ("spellcheck", "false"),
    ("enterkeyhint", "go"),
  ], class: "search-input", on: [on_value("input", Typed), on_key("keydown", Pressed)])
}

## The input bar: the field, then the way out. A keyboard reader is shown the
## key; a phone, which has none, gets a button, and the stylesheet decides
## which of the two is on screen.
fn bar(m: Model, shown: Int) -> Node[Msg] !Ctx = {
  let code = lang()
  el("div", class: "search-bar", kids: [
    field(m, shown),
    el("kbd", [("aria-hidden", "true")], class: "search-esc", kids: [text("esc")]),
    el("button", [("type", "button")], class: "search-cancel", on: [on_click(Dismissed)],
      kids: [text(say(code, "Cancel", "取消"))]),
  ])
}

## One key hint: the keys, then what they do.
fn hint(keys: List[String], does: String) -> Node[Msg] = {
  var kids: List[Node[Msg]] = []
  for k in keys {
    let cap: Node[Msg] = el("kbd", kids: [text(k)])
    kids = kids ++ [cap]
  }
  let what: Node[Msg] = text(does)
  el("span", class: "search-hint", kids: kids ++ [what])
}

## The foot of the panel: the keys, for a reader who has them, what the
## panel searches, for every reader, and, while there is a query, a way to
## share it.
fn foot(mod_key: String, m: Model) -> Node[Msg] !Ctx = {
  let code = lang()
  let share: List[Node[Msg]] = if idle(m) { [] } else { copy_link(code) }
  el("div", class: "search-foot", kids: [
    el("span", [("aria-hidden", "true")], class: "search-keys", kids: [
      hint(["↵"], say(code, "open", "打开")),
      hint(["↑", "↓"], say(code, "move", "选择")),
      hint([mod_key, "↵"], say(code, "new tab", "新标签页")),
      hint(["esc"], say(code, "close", "关闭")),
    ]),
    el("p", class: "search-scope", kids: [text(scope_line(code, full_text()))]),
  ] ++ share)
}

## Copy link: the query, as an address a reader can send.
##
## Like the delete and Clear buttons it has no listener. The address is the
## page's (the guest has no URL bar), so is the clipboard, and so is whether
## the copy worked; the button only says what it is with `data-copy-link`, and
## site/assets/search.js writes `?q=` into the address, copies it and says so.
## Both of the button's labels are drawn here, in the page's language, because
## the page script carries no words: it shows "Copied" by putting `is-copied`
## on the host, the stylesheet swaps the two labels, and the status line
## beside the button is what a screen reader hears. The status is drawn with
## the button, so it is in the document before its text is shown, which is
## when a live region is announced. The id is what the page's fallback field
## (a clipboard that refuses) is labelled by.
fn copy_link(code: String) -> List[Node[Msg]] = [
  el("button", [("type", "button"), ("id", "dawn-search-copy"), ("data-copy-link", "1")], class: "search-copy",
    kids: [
      span(say(code, "Copy link", "复制链接"), class: "search-copy-do"),
      span(say(code, "Copied", "已复制"), class: "search-copy-done"),
    ]),
  el("span", [("role", "status")], class: "search-copy-said", kids: [
    span(say(code, "Link copied", "链接已复制"), class: "search-copy-said-text"),
  ]),
]

## `aria-busy` while the rows are the last settled answer and not this query's.
fn busy(m: Model) -> List[(String, String)] = if m.stale == "" { [] } else { [("aria-busy", "true")] }

fn panel(state: State, m: Model) -> Node[Msg] !Ctx = {
  let code = lang()
  let found: List[Node[Msg]] =
    if idle(m) {
      idle_sections(state, m.sel)
    } else {
      sections(scan(state, m.hits, m.sel).hits, m.sel, terms(if m.stale == "" { m.query } else { m.stale }))
    }
  let label =
    if idle(m) { say(code, "Recent searches and suggestions", "最近搜索与推荐") } else { say(code, "Results", "结果") }
  el("div", [
    ("role", "dialog"),
    ("aria-modal", "true"),
    ("aria-label", say(code, "Search", "搜索")),
  ], class: "search-panel", kids: [
    bar(m, if len(found) > 0 { shown_rows(state, m) } else { 0 }),
    el("div", [("aria-hidden", "true")], class: "search-line"),
    pills(m),
    el("ul", [("id", list_id()), ("role", "listbox"), ("aria-label", label)] ++ busy(m),
      class: if m.stale == "" { "search-results" } else { "search-results is-stale" }, kids: found),
    status(m, len(found) > 0),
    foot(state.mod_key, m),
  ] ++ goto_kids(m))
}

# ---- the loop --------------------------------------------------------------

## The retained state and mutable model a fresh panel start from, given what
## the page already knew.
##
## Total, because a page may hand back anything: no flags, flags that are not
## JSON, JSON that is not an object and an object with no index are four
## things a running application meets, and each falls back to the same visible
## default -- a panel with an empty index, which says "no matches" for
## everything and is therefore obvious rather than silent.
pub fn init(flags: Option[String]) -> (State, Model) =
  match flags {
    None -> (blank_state(), blank())
    Some(text) ->
      match parse(text) {
        Ok(j) -> {
          let index = jget(j, "index")
          let entries = index.jget("items").entries_of()
          let state = State {
            root: j.jget("root").jstr_or("."),
            lang: index.jget("lang").jstr_or("en"),
            mod_key: j.jget("mod").jstr_or("⌘"),
            entries: entries,
            keys: list.map(entries, e => key_of(e)),
            start: list.map(index.jget("start").jarr(), s => jint_or(s, -1)),
            recent: j.jget("recent").recent_of(),
            body: j.jget("body").body_of(entries),
            texts: map.empty(),
            chunks: map.empty(),
          }
          # A shared link's query is answered in the first turn, so the
          # panel opens on its results rather than on an empty field.
          let q = j.jget("q").jstr_or("")
          let (first, _) = asked(state, blank(), q, -1)
          (state, if q == "" { blank() } else { first })
        }
        Err(_) -> (blank_state(), blank())
      }
  }

fn blank_state() -> State =
  State { root: ".", lang: "en", mod_key: "⌘", entries: [], keys: [], start: [], recent: [], body: None, texts: map.empty(), chunks: map.empty() }

## How many recent queries the panel shows. The page keeps no more than this
## either; the bound is restated here because flags are text a page may hand
## over with anything in it.
fn recent_cap() -> Int = 5

## The recent queries out of the flags: strings only, blank ones dropped, at
## most [recent_cap], in the order the page keeps them (newest first).
fn recent_of(j: Json) -> List[String] = {
  var out: List[String] = []
  for item in jarr(j) {
    let q = str.trim(jstr_or(item, ""))
    if q != "" && len(out) < recent_cap() {
      out = out ++ [q]
    }
  }
  out
}

## Everything a keystroke would otherwise derive from `e` again.
pub fn key_of(e: Entry) -> Key = {
  let heads = tokens(e.title)
  Key {
    group: group_index(e.group),
    title: str.to_lower(e.title),
    heads: heads,
    words: heads ++ tokens(e.detail) ++ tokens(e.note),
  }
}

## The model of a panel that has been left: closed, and holding nothing a
## reopening could mistake for its own.
fn closed(m: Model) -> Model =
  Model { ..m, open: false, query: "", sel: 0, goto: "", hits: [], scope: -1, counts: [], fix: "", fix_hits: 0, asked: [], chased: 0, loading: [], stale: "" }

fn blank() -> Model =
  Model {
    query: "",
    sel: 0,
    open: true,
    goto: "",
    hits: [],
    scope: -1,
    counts: [],
    fix: "",
    fix_hits: 0,
    asked: [],
    chased: 0,
    loading: [],
    stale: "",
  }

## What an answer still owes the host: the sections whose text would change it
## ([Answer]'s `need`) and the chunks of the text's index it cannot be given
## without (`words`, which also covers the chunks a suggestion is waiting for).
type Owed = { secs: List[Int], words: List[Int] }

## The model after asking `text` within `scope`, selection at the top, and what
## the answer is still owed.
##
## A suggestion is looked for only here and when a chunk arrives ([refreshed]),
## and only when neither index answered anything: that is the whole of the
## trigger, and the reason a keystroke that finds something never pays for it.
## While the text's index is missing chunks the query needs, nothing has been
## answered yet and no suggestion is made: it would be made from a guess.
fn asked(state: State, m: Model, text: String, scope: Int) -> (Model, Owed) = {
  let a = answer(state, text, scope)
  let none: List[Int] = []
  if len(a.words) > 0 && text != "" && has_text_rows(m) {
    # the chunks of this query are not here: keep the last settled view as it
    # was, and only note which query the rows answer
    (
      Model { ..m, query: text, goto: "", chased: 0, stale: if m.stale == "" { m.query } else { m.stale } },
      Owed { secs: none, words: a.words },
    )
  } else {
    let (fix, n, more) =
      if len(a.hits) == 0 && len(a.words) == 0 { suggest_plan(state, text) } else { ("", 0, none) }
    (
      Model { ..m, query: text, sel: 0, goto: "", hits: a.hits, scope: a.scope, counts: a.counts, fix: fix, fix_hits: n, chased: 0, stale: "" },
      Owed { secs: a.need, words: merged(a.words, more) },
    )
  }
}

## Whether the rows of `m` include any from the text's index.
fn has_text_rows(m: Model) -> Bool = list.any(m.hits, h => h >= body_base())

fn merged(a: List[Int], b: List[Int]) -> List[Int] = {
  var out = a
  for x in b {
    if not list.contains(out, x) {
      out = out ++ [x]
    }
  }
  out
}

## The same question asked again of the same query, because what the answer
## depends on has changed: a fragment arrived, or (`words`) a chunk did. The
## selection stays on its row number, held inside the new list. The suggestion
## is left as it was, unless a chunk arrived and the question is still
## unanswered, in which case it is made again, now that it may be made.
fn refreshed(state: State, m: Model, words: Bool) -> (Model, Owed) = {
  let a = answer(state, m.query, m.scope)
  if m.stale != "" && len(a.words) > 0 {
    # still waiting on chunks: the snapshot stays
    (m, Owed { secs: [], words: a.words })
  } else {
    settled(state, m, a, words)
  }
}

fn settled(state: State, m: Model, a: Answer, words: Bool) -> (Model, Owed) = {
  let sel = if m.sel < len(a.hits) { m.sel } else if len(a.hits) > 0 { len(a.hits) - 1 } else { 0 }
  let again = words && len(a.words) == 0
  let none: List[Int] = []
  let (fix, n, more) =
    if again && len(a.hits) == 0 {
      suggest_plan(state, m.query)
    } else if again {
      ("", 0, none)
    } else {
      (m.fix, m.fix_hits, none)
    }
  (
    Model { ..m, sel: if m.stale == "" { sel } else { 0 }, hits: a.hits, scope: a.scope, counts: a.counts, fix: fix, fix_hits: n, stale: "" },
    Owed { secs: a.need, words: merged(a.words, more) },
  )
}

# ---- fetching the text -----------------------------------------------------

## How many rows from the top are fetched for at once, whatever the selection:
## what a panel shows without scrolling. The rows after them are fetched as
## the selection (arrow keys, the pointer resting on a row) comes within
## [lookahead] of them.
pub fn first_rows() -> Int = 10

fn lookahead() -> Int = 5

## The section a body row (`id` from [body_base] up) is a paragraph of, or -1.
fn sec_of_id(state: State, id: Int) -> Int =
  match state.body {
    None -> -1
    Some(b) ->
      match get(b.paras, id - body_base()) {
        Some(p) -> p.sec
        None -> -1
      }
  }

## The sections of the rows the reader can reach without scrolling: the first
## [first_rows] rows, or [lookahead] rows past the selection when that is
## further. Title rows have no section.
fn visible_secs(state: State, m: Model) -> List[Int] = {
  let upto = if m.sel + lookahead() > first_rows() { m.sel + lookahead() } else { first_rows() }
  var out: List[Int] = []
  for id in list.take(m.hits, upto) {
    if id >= body_base() {
      out = out ++ [sec_of_id(state, id)]
    }
  }
  out
}

## The fragment of section `sec` as the file the host should fetch, relative to
## the host's own base (a worker resolves against its script, which lives in
## /assets/ with the directory beside it), or "" for a section with no text.
fn fragment_url(state: State, sec: Int) -> String =
  match state.body {
    None -> ""
    Some(b) ->
      match get(b.secs, sec) {
        Some(s) -> if s.frag == "" { "" } else { "${b.dir}/${sec}.${s.frag}.json" }
        None -> ""
      }
  }

## The chunk `c` of the text's index as the file the host should fetch, in the
## same terms as [fragment_url], or "" for a chunk the manifest does not have.
fn chunk_url(state: State, c: Int) -> String =
  match state.body {
    None -> ""
    Some(b) ->
      match get(b.chunks, c) {
        Some(ch) -> if ch.hash == "" { "" } else { "${b.chunk_dir}/${c}.${ch.hash}.json" }
        None -> ""
      }
  }

## The name a chunk's request goes by: `c` and its position, as a section's is
## `t` and its number.
fn chunk_tag(c: Int) -> String = "c${c}"

## The name a section's request goes by. The host returns it verbatim with the
## outcome, and [sec_of_tag] reads it back.
fn fetch_tag(sec: Int) -> String = "t${sec}"

## The model with the fetches it still owes, and the command that makes them:
## the sections of the rows on screen (and the look-ahead), then `extra` (the
## unchecked candidates), minus what has arrived, what failed, and what is
## already on its way. Every file is asked for once per session of the panel.
fn wanting(state: State, m: Model, owed: Owed) -> (Model, Cmd[Msg]) =
  match state.body {
    None -> (m, NoCmd)
    Some(_) -> {
      let extra = owed.secs
      # the chunks first: the answer waits on them, and the rows to be asked
      # the text of do not exist until they are here
      var words: List[Int] = []
      for c in owed.words {
        if not map.has(state.chunks, c) && not list.contains(m.loading, c) && not list.contains(words, c)
          && chunk_url(state, c) != "" {
          words = words ++ [c]
        }
      }
      var want: List[Int] = []
      for sec in visible_secs(state, m) {
        if not list.contains(extra, sec) && askable(state, m, want, sec) {
          want = want ++ [sec]
        }
      }
      # the unchecked candidates, on screen or not, as many as this query has
      # left to spend: a section on screen whose phrase is still unchecked is
      # in `extra` too, and counts against the same budget, or a rare phrase
      # would walk down its candidates one dropped row at a time
      var left = verify_total() - m.chased
      var spent = 0
      for sec in extra {
        if left > 0 && askable(state, m, want, sec) {
          want = want ++ [sec]
          left = left - 1
          spent = spent + 1
        }
      }
      if len(want) == 0 && len(words) == 0 {
        (m, NoCmd)
      } else {
        (
          Model { ..m, asked: m.asked ++ want, chased: m.chased + spent, loading: m.loading ++ words },
          BatchCmd(cmds: fetches_of(state, words, want)),
        )
      }
    }
  }

## The fetches for `words` (chunks) and `want` (sections), chunks first.
fn fetches_of(state: State, words: List[Int], want: List[Int]) -> List[Cmd[Msg]] = {
  let a: List[Cmd[Msg]] = list.map(words, c => Fetch(url: chunk_url(state, c), tag: chunk_tag(c)))
  let b: List[Cmd[Msg]] = list.map(want, sec => Fetch(url: fragment_url(state, sec), tag: fetch_tag(sec)))
  a ++ b
}

## Whether section `sec` still has to be asked for: it has a text file, and it
## has not arrived, failed, been asked for, or been put in `want` already.
fn askable(state: State, m: Model, want: List[Int], sec: Int) -> Bool =
  sec >= 0 && fragment_url(state, sec) != "" && not map.has(state.texts, sec)
  && not list.contains(m.asked, sec) && not list.contains(want, sec)

## Two commands as one, with `NoCmd` the identity.
fn join_cmds(a: Cmd[Msg], b: Cmd[Msg]) -> Cmd[Msg] =
  match (a, b) {
    (NoCmd, _) -> b
    (_, NoCmd) -> a
    _ -> BatchCmd(cmds: [a, b])
  }

## A fetch's outcome as the message for the turn it arrives in. The text is
## already in the retained state ([absorb]); the message only says which
## section, so that the answer is asked again. A tag that is not one of this
## panel's (a request of a session that has since been restarted, say) is a
## section nobody has, and changes nothing.
pub fn supplied(tag: String, _outcome: Result[String, String]) -> Msg =
  if str.starts_with(tag, "c") { Loaded(chunk: chunk_of_tag(tag)) } else { Arrived(sec: sec_of_tag(tag)) }

fn chunk_of_tag(tag: String) -> Int =
  if str.starts_with(tag, "c") { parse_int(str.drop(tag, 1)).unwrap_or(-1) } else { -1 }

fn sec_of_tag(tag: String) -> Int =
  if str.starts_with(tag, "t") { parse_int(str.drop(tag, 1)).unwrap_or(-1) } else { -1 }

## What a fetched fragment adds to the retained state: the section's paragraphs,
## whole, under the section's number. This is `tea_dom/reactor`'s `absorbed`
## hook, which runs before the turn's message is folded, so the turn that
## answers `Arrived` already sees the text. A fragment that failed to arrive, is
## not JSON, names another section or has another count of paragraphs than the
## index says is recorded as no text at all: the section is not asked for
## again, its rows are drawn without an excerpt, and a Chinese phrase in it
## stays unchecked.
pub fn absorb(state: State, tag: String, outcome: Result[String, String]) -> State = {
  let sec = sec_of_tag(tag)
  let chunk = chunk_of_tag(tag)
  match state.body {
    None -> state
    Some(b) ->
      if chunk >= 0 && chunk < len(b.chunks) {
        State { ..state, chunks: map.insert(state.chunks, chunk, chunk_posts(chunk, outcome)) }
      } else if sec < 0 || sec >= len(b.secs) {
        state
      } else {
        State { ..state, texts: map.insert(state.texts, sec, fragment_texts(b, sec, outcome)) }
      }
  }
}

## The words and postings a chunk file holds, or none if it is not the one the
## manifest named (`[n, [word, ...], [[gap, ...], ...]]` with its own position,
## and as many posting lists as words, the words in ascending code-point
## order). The gaps are added up here, once, so that a keystroke does not.
fn chunk_posts(n: Int, outcome: Result[String, String]) -> Posts = {
  let none = Posts { terms: [], posts: [] }
  match outcome {
    Err(_) -> none
    Ok(body) ->
      match parse(body) {
        Err(_) -> none
        Ok(j) -> {
          let fs = jarr(j)
          if len(fs) != 3 || jint_or(fs[0], -1) != n {
            none
          } else {
            let terms = list.map(jarr(fs[1]), t => jstr_or(t, ""))
            let posts = list.map(jarr(fs[2]), g => g.jarr().sums())
            if len(terms) == len(posts) { Posts { terms: terms, posts: posts } } else { none }
          }
        }
      }
  }
}

## The paragraphs a fragment holds, or none if the file is not the one the index
## describes (`[section, [paragraph, ...]]` with the section's own number and as
## many paragraphs as the index counted for it).
fn fragment_texts(b: Body, sec: Int, outcome: Result[String, String]) -> List[String] =
  match outcome {
    Err(_) -> none_texts()
    Ok(body) ->
      match parse(body) {
        Err(_) -> none_texts()
        Ok(j) -> {
          let fs = jarr(j)
          let none: List[String] = []
          let texts = if len(fs) == 2 { list.map(jarr(fs[1]), t => jstr_or(t, "")) } else { none }
          if len(fs) == 2 && jint_or(fs[0], -1) == sec && len(texts) == paras_in(b, sec) { texts } else { none }
        }
      }
  }

## How many numbered paragraphs the index gives section `sec`.
fn none_texts() -> List[String] = []

fn paras_in(b: Body, sec: Int) -> Int = len(list.filter(b.paras, p => p.sec == sec))

## One turn: the model the message leaves behind, and what the panel asks the
## driver for next.
pub fn update(state: State, m: Model, msg: Msg) -> (Model, Cmd[Msg]) =
  match msg {
    # The arms that search ask for the text of what they answered.
    Typed(text) -> {
      let (m1, owed) = asked(state, m, text, m.scope)
      wanting(state, m1, owed)
    }
    # A pill that is already on changes nothing.
    Scoped(g) ->
      if g == m.scope {
        (m, NoCmd)
      } else {
        let (m1, owed) = asked(state, m, m.query, g)
        wanting(state, m1, owed)
      }
    # A section's text is in: the same question has a better answer now.
    Arrived(sec) -> {
      let m1 = Model { ..m, asked: list.filter(m.asked, a => a != sec) }
      if m1.query == "" {
        (m1, NoCmd)
      } else {
        let (m2, owed) = refreshed(state, m1, false)
        wanting(state, m2, owed)
      }
    }
    # A chunk of words is in: the question may be answerable now.
    Loaded(c) -> {
      let m1 = Model { ..m, loading: list.filter(m.loading, x => x != c) }
      if m1.query == "" {
        (m1, NoCmd)
      } else {
        let (m2, owed) = refreshed(state, m1, true)
        wanting(state, m2, owed)
      }
    }
    # Everything else reads `hits`, and may move the selection toward rows
    # whose text has not been asked for.
    _ -> {
      let (m1, c) = moved(state, m, msg)
      let (m2, f) = wanting(state, m1, Owed { secs: [], words: [] })
      (m2, join_cmds(c, f))
    }
  }

## The messages that read `hits` and move the selection or leave the panel:
## everything but the arms that search and the arrival of a fragment.
fn moved(state: State, m: Model, msg: Msg) -> (Model, Cmd[Msg]) =
  match msg {
    Pressed(key) -> pressed(state, m, key)
    # The pointer selects what it rests on. Resting on the row that is already
    # selected changes nothing, so the turn answers no patches.
    Hovered(at) ->
      if at >= 0 && at < shown_rows(state, m) && at != m.sel {
        (Model { ..m, sel: at, goto: "" }, NoCmd)
      } else {
        (m, NoCmd)
      }
    Dismissed -> (closed(m), NoCmd)
    # The whole of the navigation instruction, in one place. It overwrites
    # `goto` rather than reading it, so the arm that commands it does not have
    # to clear the field first.
    Chose(href) -> (Model { ..m, goto: href }, NoCmd)
    _ -> (m, NoCmd)
  }

## Closed is an empty tree, not a hidden one: the panel is a whole document
## while it is open and nothing at all while it is not, so the page keeps no
## stale rows behind a `hidden` attribute.
pub fn view(state: State, m: Model) -> Node[Msg] = {
  with handle Ctx {
    root() => state.root
    lang() => state.lang
    full_text() => has_body(state)
  }
  if m.open { panel(state, m) } else { div(class: "search-panel is-closed") }
}

## What a key means. Everything not named here means nothing, which is the
## half that keeps typing cheap: an ordinary character is an `input` event and
## a `keydown` this ignores, and ignoring it answers with no patches at all.
fn pressed(state: State, m: Model, key: String) -> (Model, Cmd[Msg]) = {
  let last = shown_rows(state, m) - 1
  if key == "ArrowDown" {
    (Model { ..m, sel: if m.sel < last { m.sel + 1 } else { m.sel }, goto: "" }, NoCmd)
  } else if key == "ArrowUp" {
    (Model { ..m, sel: if m.sel > 0 { m.sel - 1 } else { 0 }, goto: "" }, NoCmd)
  } else if key == "Home" {
    (Model { ..m, sel: 0, goto: "" }, NoCmd)
  } else if key == "End" {
    (Model { ..m, sel: if last > 0 { last } else { 0 }, goto: "" }, NoCmd)
  } else if key == "Enter" && idle(m) {
    (m, idle_choice(state, m.sel))
  } else if key == "Enter" && len(m.hits) == 0 && m.fix != "" {
    # Nothing to open, and a query that has answers on offer: Enter takes it,
    # the way it takes a recent query.
    (m, SendMsg(msg: Typed(text: m.fix)))
  } else if key == "Enter" {
    # Nothing about the model changes here. Where the selection points is a
    # question `scan` answers, and what to do about it is the command.
    (m, SendMsg(msg: Chose(href: scan(state, m.hits, m.sel).chosen)))
  } else if key == "Escape" {
    # Escape takes back one step: a query first, then the panel. A reader who
    # typed the wrong thing gets an empty field and not a closed panel, and
    # the second press is the one that leaves.
    if m.query == "" {
      (closed(m), NoCmd)
    } else {
      (Model { ..m, query: "", sel: 0, goto: "", hits: [], scope: -1, counts: [], fix: "", fix_hits: 0, asked: [], chased: 0, loading: [], stale: "" }, NoCmd)
    }
  } else {
    (m, NoCmd)
  }
}

# ---- the model as text -----------------------------------------------------

fn jget(j: Json, key: String) -> Json =
  match j {
    JObj(entries) -> map.get(entries, key).unwrap_or(JNull)
    _ -> JNull
  }

fn jstr_or(j: Json, fallback: String) -> String =
  match j {
    JStr(s) -> s
    _ -> fallback
  }

fn jint_or(j: Json, fallback: Int) -> Int =
  match j {
    JInt(v) -> v
    _ -> fallback
  }

fn jbool_or(j: Json, fallback: Bool) -> Bool =
  match j {
    JBool(b) -> b
    _ -> fallback
  }

fn jarr(j: Json) -> List[Json] =
  match j {
    JArr(items) -> items
    _ -> []
  }

## The index, read out of the five-string rows both halves of this feature
## agree on. site/src/gen/search.dawn writes exactly this shape and pins the
## same literal in a test of its own; the two are separate programs, so the
## pair of tests is what keeps them level.
pub fn entries_of(j: Json) -> List[Entry] = {
  var out: List[Entry] = []
  for item in jarr(j) {
    let fs = jarr(item)
    if len(fs) == 5 {
      out = out
        ++ [Entry {
          group: jstr_or(fs[0], ""),
          title: jstr_or(fs[1], ""),
          detail: jstr_or(fs[2], ""),
          note: jstr_or(fs[3], ""),
          href: jstr_or(fs[4], ""),
        }]
    }
  }
  out
}

fn quoted(s: String) -> String = render(JStr(value: s))

## The model as one line of JSON, and back.
##
## Written out rather than assembled through `JObj`, because a map's iteration
## order is a fact about a hash and this text is compared byte for byte in
## scripts/example-main-contract/registry.json. Field order here is the field
## order there. The retained state is intentionally absent: encoding root,
## language or index here would put the large static half back on the wire.
## The hits are ids into it, at most [cap] small integers.
pub fn encode(m: Model) -> String =
  "{\"q\":" ++ quoted(m.query)
  ++ ",\"sel\":" ++ to_string(m.sel)
  ++ ",\"open\":" ++ (if m.open { "true" } else { "false" })
  ++ ",\"goto\":" ++ quoted(m.goto)
  ++ ",\"hits\":[" ++ list.map(m.hits, h => to_string(h)).join(",") ++ "]"
  ++ ",\"scope\":" ++ to_string(m.scope)
  ++ ",\"counts\":[" ++ list.map(m.counts, c => to_string(c)).join(",") ++ "]"
  ++ ",\"fix\":" ++ quoted(m.fix)
  ++ ",\"fix_hits\":" ++ to_string(m.fix_hits)
  ++ (if len(m.asked) == 0 { "" } else { ",\"asked\":[" ++ list.map(m.asked, a => to_string(a)).join(",") ++ "]" })
  ++ (if m.chased == 0 { "" } else { ",\"chased\":" ++ to_string(m.chased) })
  ++ (if m.stale == "" { "" } else { ",\"stale\":" ++ quoted(m.stale) })
  ++ (if len(m.loading) == 0 { "" } else { ",\"loading\":[" ++ list.map(m.loading, a => to_string(a)).join(",") ++ "]" })
  ++ "}"

## Total, because a host may hand back anything: an unreadable model reads as
## a fresh one rather than as a panic, which keeps a corrupted page
## recoverable by typing.
pub fn decode(s: String) -> Model =
  match parse(s) {
    Ok(j) ->
      match j {
        JObj(_) ->
          Model {
            query: j.jget("q").jstr_or(""),
            sel: j.jget("sel").jint_or(0),
            open: j.jget("open").jbool_or(true),
            goto: j.jget("goto").jstr_or(""),
            hits: list.map(j.jget("hits").jarr(), h => jint_or(h, -1)),
            scope: j.jget("scope").jint_or(-1),
            counts: list.map(j.jget("counts").jarr(), c => jint_or(c, 0)),
            fix: j.jget("fix").jstr_or(""),
            fix_hits: j.jget("fix_hits").jint_or(0),
            asked: list.map(j.jget("asked").jarr(), a => jint_or(a, -1)),
            chased: j.jget("chased").jint_or(0),
            loading: list.map(j.jget("loading").jarr(), a => jint_or(a, -1)),
            stale: j.jget("stale").jstr_or(""),
          }
        _ -> blank()
      }
    Err(_) -> blank()
  }

# ---- tests -----------------------------------------------------------------

# One turn as the reactor commits it: `update`, then everything its command
# asked for, fetches included ([drive] answers them from the fixtures).
# `tea_dom/reactor.turn_with_state` folds with the same function, so an
# assertion written on this is an assertion about what the page gets.
fn turn(state: State, m: Model, msg: Msg) -> Model = {
  let (_, mo) = drive(state, m, msg)
  mo
}

## The model a reader leaves behind by typing `q` into a fresh panel.
fn typed(state: State, q: String) -> Model = turn(state, blank(), Typed(text: q))

fn probe_entry(group: String, title: String, note: String, href: String) -> Entry =
  Entry { group: group, title: title, detail: "fn ${title}()", note: note, href: href }

fn probe_index() -> List[Entry] = [
  probe_entry("stdlib", "str.trim", "Remove surrounding whitespace.", "stdlib.html#std-str-trim"),
  probe_entry("stdlib", "str.split", "", "stdlib.html#std-str-split"),
  probe_entry("stdlib", "list.map", "", "stdlib.html#std-list-map"),
  probe_entry("spec", "6.5 Named effects", "", "spec.html#s6-5"),
  probe_entry("tutorial", "Effects", "", "tutorial/09.html"),
]

fn state_of(entries: List[Entry]) -> State =
  State { ..blank_state(), entries: entries, keys: list.map(entries, e => key_of(e)) }

fn probe_state() -> State = probe_index().state_of()

fn shown(state: State, q: String) -> List[String] =
  list.map(scan(state, search(state, q), 0).hits, h => h.entry.title)

test "a query answers the entries that match it, best rank first" {
  let state = probe_state()
  # an exact title beats a prefix beats a word prefix beats a substring
  assert shown(state, "str.trim") == ["str.trim"]
  assert shown(state, "str.") == ["str.trim", "str.split"]
  # `map` is a word of `list.map` and a substring of nothing else here
  assert shown(state, "map") == ["list.map"]
  # the note is the last resort, and only when nothing in a title matched
  assert shown(state, "whitespace") == ["str.trim"]
  # case and surrounding blanks are not part of the question
  assert shown(state, "  STR.Trim ") == ["str.trim"]
  # an empty query asks nothing, so nothing answers
  let none: List[String] = []
  assert shown(state, "") == none
  assert shown(state, "nothing here") == none
}

## Every word has to be found, the last one as a prefix and the others whole,
## and a word may be found in any of the three fields.
test "a query of several words answers only the entries that have all of them" {
  let state = state_of([
    Entry {
      group: "stdlib",
      title: "io.read_file",
      detail: "fn read_file(path: String) -> Result[String, IoError] !Fs",
      note: "The file at `path` as UTF-8 text.",
      href: "stdlib.html#std-io-read_file",
    },
    Entry {
      group: "stdlib",
      title: "io.write_file",
      detail: "fn write_file(path: String, text: String) -> Result[Unit, IoError] !Fs",
      note: "",
      href: "stdlib.html#std-io-write_file",
    },
    probe_entry("spec", "6.5 Named effects", "", "spec.html#s6-5"),
  ])
  # `fs` is the `!Fs` of both signatures, `read` begins only one of the names
  assert shown(state, "fs read") == ["io.read_file"]
  assert shown(state, "fs") == ["io.read_file", "io.write_file"]
  assert shown(state, "!fs") == ["io.read_file", "io.write_file"]
  # a word that is not last has to be whole: `rea` is not a word of either
  let none: List[String] = []
  assert shown(state, "rea fs") == none
  # the order of the words does not matter, and the note is searched too
  assert shown(state, "text read") == ["io.read_file"]
  # a dotted query is one word, matched against the dotted name
  assert shown(state, "io.read") == ["io.read_file"]
  assert shown(state, "6.5") == ["6.5 Named effects"]
}

## A Chinese title is one run with no spaces in it, so a Chinese word is looked
## for inside the words rather than at their start.
test "a word beyond ASCII is found inside a run" {
  let state = state_of([
    probe_entry("spec", "6.5 命名效果", "", "zh/spec.html#s6-5"),
    probe_entry("tutorial", "效果与处理器", "", "zh/tutorial/09.html"),
  ])
  assert shown(state, "效果") == ["效果与处理器", "6.5 命名效果"]
  assert shown(state, "命名效果") == ["6.5 命名效果"]
}

## The words of a string, by the rule at the head of the words section. These
## samples are the contract between two programs that cannot share a line of
## code; the same list is pinned in site/src/gen/search.dawn's own test, and
## the two tests name each other so that a change to either is a change to
## both.
test "an index's words and a query's words split the same way" {
  let samples: List[(String, List[String])] = [
    ("io.read_file", ["io", "read", "file", "io.read_file"]),
    ("fn read_file(path: String) -> Unit !Fs", ["fn", "read", "file", "read_file", "path",
      "string", "unit", "fs", "!fs"]),
    ("6.5 Named effects", ["6", "5", "6.5", "named", "effects"]),
    ("Remove surrounding whitespace.", ["remove", "surrounding", "whitespace"]),
    ("str.", ["str"]),
    ("`with handle` 命名效果，处理器", ["with", "handle", "命名效果", "处理器"]),
    ("... ! -> ()", []),
  ]
  for sample in samples {
    let (s, words) = sample
    assert tokens(s) == words
  }
}

test "a query's terms say how each word has to fit" {
  assert terms("fs read") == [Term { word: "fs", fit: Whole }, Term { word: "read", fit: Start }]
  # the last word keeps its trailing dot, an earlier one does not
  assert terms("str. list.") == [Term { word: "str", fit: Whole }, Term { word: "list.", fit: Start }]
  assert terms("效果 x") == [Term { word: "效果", fit: Within }, Term { word: "x", fit: Start }]
  let none: List[Term] = []
  assert terms("  !! ") == none
}

## A group's place is its best match, not its place in the table: `eff` begins
## the whole of the tutorial chapter's title and only a word of the spec
## section's, so the tutorial comes first although [groups] lists the spec
## first -- and the standard library, listed before both, matches nothing.
test "groups come in the order of their best hit and are numbered across" {
  let state = probe_state()
  let s = scan(state, search(state, "eff"), 0)
  assert list.map(s.hits, h => h.entry.group) == ["tutorial", "spec"]
  assert list.map(s.hits, h => h.at) == [0, 1]
}

## Within a group the order is rank and then index order, and every group that
## matched keeps a place when the cap is reached.
test "the cap is dealt out one row per group per round" {
  assert shares([50, 3, 1], 40) == [36, 3, 1]
  assert shares([30, 30], 40) == [20, 20]
  assert shares([30, 30, 30], 40) == [14, 13, 13]
  assert shares([2, 1], 40) == [2, 1]
  let none: List[Int] = []
  assert shares(none, 40) == none
  # on an index, too: sixty stdlib rows and one tutorial row, all rank 1
  var many: List[Entry] = []
  for i in range(0, 60) {
    many = many ++ [probe_entry("stdlib", "f${i}", "tick", "stdlib.html#f${i}")]
  }
  let state = state_of(many ++ [probe_entry("tutorial", "Clocks", "tick", "tutorial/20.html")])
  let hits = scan(state, search(state, "tick"), 0).hits
  assert len(hits) == cap()
  assert list.map(list.filter(hits, h => h.entry.group == "tutorial"), h => h.entry.title)
    == ["Clocks"]
  # and the stdlib rows that made it are the first ones, in index order
  assert hits[0].entry.title == "f0"
  assert hits[38].entry.title == "f38"
}

## The second cell. `chosen` is not a function of `hits` alone -- it is the
## href at the ordinal the model is pointing at, decided inside the arm while
## the ordinal still exists.
test "the selection resolves to one href, and out of range resolves to none" {
  let state = probe_state()
  let ids = search(state, "str.")
  assert scan(state, ids, 0).chosen == "stdlib.html#std-str-trim"
  assert scan(state, ids, 1).chosen == "stdlib.html#std-str-split"
  assert scan(state, ids, 7).chosen == ""
  # and with nothing matched there is nothing to choose
  assert scan(state, search(state, "nothing here"), 0).chosen == ""
  # an id the index does not have is passed over rather than trusted
  assert len(scan(state, [99, 0, -1], 0).hits) == 1
}

## Every group an index entry can name is a group the panel draws. An entry in
## an unregistered group would be scored, matched, and then silently dropped
## by [rows_of].
test "the registered groups are the ones an index may name" {
  let ids = list.map(groups(), g => g.id)
  assert ids == ["stdlib", "spec", "tutorial", "examples", "history"]
  for e in probe_index() {
    assert list.contains(ids, e.group)
  }
  for g in groups() {
    assert group_label(g, "en") != ""
    assert group_label(g, "zh-CN") != ""
    assert group_label(g, "en") != group_label(g, "zh-CN")
  }
  # and an entry in a group nobody registered is never a hit
  let stray = state_of([probe_entry("blog", "str.trim", "", "blog.html")])
  let none: List[Int] = []
  assert search(stray, "str.trim") == none
}

## The nesting rule, on the tree rather than on the collector: what crosses
## from the inner installation to the outer one is one `<li class="search-
## group">` per group, never its rows. A collector that let them leak would
## produce the same rows in the same order under no section at all.
test "each group's rows stay inside that group's section" {
  let state = probe_state()
  let v = view(state, typed(state, "eff"))
  # two groups matched, so the results list has exactly two children
  assert count_class(v, "search-group") == 2
  assert count_class(v, "search-row") == 2
  # and the rows are underneath the sections rather than beside them: the
  # results list holds two sections and no row, and each section holds one row;
  # each section's dot takes its group's hue, not its place on screen
  assert kid_classes(v, "search-results") == ["search-group hue-3", "search-group hue-2"]
  assert list.map(all_with_class(v, "search-group-rows"), n => n.kids_of().len()) == [1, 1]
}

## The conditional half of the same rule: a group with no hits is absent, not
## empty. With one group matched there is one section and no second heading.
test "a group with no hits emits no section at all" {
  let state = probe_state()
  let v = view(state, typed(state, "map"))
  assert count_class(v, "search-group") == 1
  assert count_class(v, "search-row") == 1
  # nothing matched at all: no sections, and a reason in their place
  let no_hits = view(state, typed(state, "nothing here"))
  assert count_class(no_hits, "search-group") == 0
  assert count_class(no_hits, "search-nothing") == 1
}

## The reader effect, end to end: the root and the language reach the leaves.
## A link is the page's own distance plus the site-root href, and a heading is
## in the page's language -- neither of which any function between [view] and
## the leaf mentions.
test "the page's root and language reach the leaves through the handler" {
  let en_state = State { ..probe_state(), root: ".." }
  let m = typed(en_state, "str.trim")
  assert en_state.view(m).hrefs() == ["../stdlib.html#std-str-trim"]
  assert str.contains(en_state.view(m).show_tree(), "Standard library")
  let zh_state = State { ..en_state, lang: "zh-CN", root: "../.." }
  assert zh_state.view(m).hrefs() == ["../../stdlib.html#std-str-trim"]
  assert str.contains(zh_state.view(m).show_tree(), "标准库")
  # the scope line follows it too, which is the expectation this panel manages
  assert str.contains(en_state.view(m).show_tree(), "Searches titles and API names")
  assert str.contains(zh_state.view(m).show_tree(), "只搜标题与 API 名")
}

test "a note's backticks are code, and an unpaired one is a backtick" {
  let plain: List[Node[Msg]] = [text("Remove surrounding whitespace.")]
  assert note_runs("Remove surrounding whitespace.") == plain
  let coded: List[Node[Msg]] = [
    text("The file at "),
    el("code", kids: [text("path")]),
    text(" as text."),
  ]
  assert note_runs("The file at `path` as text.") == coded
  let lead: List[Node[Msg]] = [el("code", kids: [text("n")]), text(" items")]
  assert note_runs("`n` items") == lead
  let cut: List[Node[Msg]] = [
    text("a "),
    el("code", kids: [text("b")]),
    text(" c "),
    text("`d e..."),
  ]
  assert note_runs("a `b` c `d e...") == cut
}

test "arrows move the selection and stop at both ends" {
  let state = probe_state()
  let m = typed(state, "str.")
  assert turn(state, m, Pressed(key: "ArrowUp")).sel == 0
  let down = turn(state, m, Pressed(key: "ArrowDown"))
  assert down.sel == 1
  # moving the selection is not a search: the hits are the ones typing left
  assert down.hits == m.hits
  # two hits, so the second is the last one
  assert turn(state, down, Pressed(key: "ArrowDown")).sel == 1
  assert turn(state, down, Pressed(key: "ArrowUp")).sel == 0
  # the selected row is the one that says so, and it is the only one
  assert state.view(down).selected_titles() == ["str.split"]
  # a key nothing is bound to leaves the model alone, so the turn has no patches
  assert turn(state, down, Pressed(key: "x")) == down
}

test "typing replaces the query and the hits and puts the selection back at the top" {
  let state = probe_state()
  let m = Model { ..typed(state, "str."), sel: 1 }
  let again = turn(state, m, Typed(text: "list"))
  assert again.query == "list"
  assert again.sel == 0
  assert again.goto == ""
  assert again.hits == [2]
}

## Enter is the one message that leaves an instruction in the tree, and Escape
## is the one that empties it: the first press takes the query back, the
## second closes the panel.
test "enter marks a destination and escape renders nothing at all" {
  let state = probe_state()
  let m = Model { ..typed(state, "str."), sel: 1 }
  let go = turn(state, m, Pressed(key: "Enter"))
  assert go.goto == "stdlib.html#std-str-split"
  assert str.contains(state.view(go).show_tree(), "data-goto")
  # the next message clears it, so one Enter is one navigation
  assert turn(state, go, Typed(text: "str.")).goto == ""
  let cleared = turn(state, go, Pressed(key: "Escape"))
  assert cleared.open
  assert cleared.query == ""
  assert cleared.goto == ""
  assert cleared.hits == blank().hits
  let shut = turn(state, cleared, Pressed(key: "Escape"))
  assert not shut.open
  assert shut.query == ""
  assert shut.hits == blank().hits
  let closed: List[Node[Msg]] = []
  assert view(state, shut) == div(class: "search-panel is-closed", kids: closed)
}

test "flags carry the index, and every way of not having them is an empty one" {
  let flags = "{\"root\":\"..\",\"index\":{\"v\":1,\"lang\":\"zh-CN\","
    ++ "\"items\":[[\"stdlib\",\"str.trim\",\"fn trim(s: String) -> String\","
    ++ "\"Remove surrounding whitespace.\",\"zh/stdlib.html#std-str-trim\"]]}}"
  let (state, m) = init(Some(flags))
  assert state.root == ".."
  assert state.lang == "zh-CN"
  assert len(state.entries) == 1
  assert state.entries[0] == Entry {
    group: "stdlib",
    title: "str.trim",
    detail: "fn trim(s: String) -> String",
    note: "Remove surrounding whitespace.",
    href: "zh/stdlib.html#std-str-trim",
  }
  # and the words of it, once, at init
  assert state.keys == [key_of(state.entries[0])]
  assert state.keys[0].title == "str.trim"
  assert state.keys[0].heads == ["str", "trim", "str.trim"]
  assert m == blank()
  let none: Option[String] = None
  assert init(none) == (blank_state(), blank())
  assert init(Some("")) == (blank_state(), blank())
  assert init(Some("not json at all")) == (blank_state(), blank())
  assert init(Some("[1,2]")) == (blank_state(), blank())
  assert init(Some("{\"root\":\"..\"}"))
    == (State { ..blank_state(), root: ".." }, blank())
}

## The shape the site generator writes. This literal is the contract between
## two programs that cannot share a line of code, and the same one is pinned
## in site/src/gen/search.dawn's own test.
test "an index row is five strings, in this order" {
  match parse("[[\"spec\",\"6.5 Named effects\",\"Spec\",\"\",\"spec.html#s6-5\"]]") {
    Ok(j) -> {
      assert entries_of(j) == [Entry {
        group: "spec",
        title: "6.5 Named effects",
        detail: "Spec",
        note: "",
        href: "spec.html#s6-5",
      }]
    }
    Err(e) -> panic("the pinned index row must parse: ${e}")
  }
}

test "only the mutable model round-trips through its text" {
  let state = probe_state()
  let m = typed(state, "str.")
  assert m.encode().decode() == m
  assert encode(m)
    == "{\"q\":\"str.\",\"sel\":0,\"open\":true,\"goto\":\"\",\"hits\":[0,1],"
    ++ "\"scope\":-1,\"counts\":[2,0,0,0,0],\"fix\":\"\",\"fix_hits\":0}"
  assert not str.contains(encode(m), "root")
  assert not str.contains(encode(m), "items")
  let shut = turn(state, turn(state, m, Pressed(key: "Escape")), Pressed(key: "Escape"))
  assert shut.encode().decode().open == false
  assert decode("not json at all") == blank()
  assert decode("[1,2]") == blank()
  # an object missing every field is the blank model, field by field
  assert decode("{}") == blank()
}

# The helpers the assertions above read trees with. `Show` on a `Node` is the
# whole tree as text, which is enough for "does this string appear anywhere in
# the document" and useless for "where"; everything that needs structure walks
# the tree instead. A class is matched as a WORD of the class attribute, not
# as the whole of it -- a selected row's class is `search-row is-selected`,
# and a check that compared the attribute would have stopped counting it.

fn show_tree(w: Node[Msg]) -> String = to_string(w)

fn count_class(w: Node[Msg], cls: String) -> Int = w.all_with_class(cls).len()

## The class attribute of each child of the first element carrying `cls`.
fn kid_classes(w: Node[Msg], cls: String) -> List[String] =
  match w.all_with_class(cls).get(0) {
    None -> []
    Some(found) -> list.map(kids_of(found), k => class_of(k))
  }

fn selected_titles(w: Node[Msg]) -> List[String] = {
  var out: List[String] = []
  for row in all_with_class(w, "is-selected") {
    for title in all_with_class(row, "search-title") {
      out = out ++ [text_of(title)]
    }
  }
  out
}

## Every `href` prop in the tree, in document order.
fn hrefs(w: Node[Msg]) -> List[String] = {
  var out: List[String] = []
  match w {
    Text(_) -> ()
    Elem(_, props, ..) -> {
      for p in props {
        let (k, v) = p
        if k == "href" {
          out = out ++ [v]
        }
      }
    }
  }
  for k in kids_of(w) {
    out = out ++ hrefs(k)
  }
  out
}

fn class_of(w: Node[Msg]) -> String =
  match w {
    Text(_) -> ""
    Elem(_, props, ..) -> {
      var found = ""
      for p in props {
        let (k, v) = p
        if k == "class" {
          found = v
        }
      }
      found
    }
  }

fn kids_of(w: Node[Msg]) -> List[Node[Msg]] =
  match w {
    Text(_) -> []
    Elem(_, _, _, kids, ..) -> kids
  }

fn text_of(w: Node[Msg]) -> String =
  match w {
    Text(s) -> s
    Elem(_, _, _, kids, ..) -> list.map(kids, k => text_of(k)).join("")
  }

fn has_class(w: Node[Msg], cls: String) -> Bool =
  list.contains(str.split(class_of(w), " "), cls)

fn all_with_class(w: Node[Msg], cls: String) -> List[Node[Msg]] = {
  var out: List[Node[Msg]] = []
  if has_class(w, cls) {
    out = out ++ [w]
  }
  for k in kids_of(w) {
    out = out ++ all_with_class(k, cls)
  }
  out
}

## Enter as a command rather than as a field write: the same model comes out,
## and the two halves are now separable.
test "enter commands the navigation instead of writing it" {
  let state = probe_state()
  let m = Model { ..typed(state, "str."), sel: 1 }
  # `update` alone moves nothing. Without the fold the panel would answer with
  # no patches at all and the page would never see a destination.
  let (kept, c) = update(state, m, Pressed(key: "Enter"))
  assert kept == m
  assert c == SendMsg(msg: Chose(href: "stdlib.html#std-str-split"))
  # And the commanded message is the only thing that writes the field.
  let (chosen, after) = update(state, m, Chose(href: "stdlib.html#std-str-split"))
  assert chosen.goto == "stdlib.html#std-str-split"
  let nothing: Cmd[Msg] = NoCmd
  assert after == nothing
  # The whole turn is what a driver commits, and it is what it always was.
  assert turn(state, m, Pressed(key: "Enter")) == Model { ..m, goto: "stdlib.html#std-str-split" }
}

## The pointer and the arrows move one selection: the row the mouse rests on
## is the row Enter opens, and resting on an ordinal the hits do not have
## moves nothing.
test "hovering a row selects it" {
  let state = probe_state()
  let m = typed(state, "str.")
  let on_second = turn(state, m, Hovered(at: 1))
  assert on_second.sel == 1
  assert state.view(on_second).selected_titles() == ["str.split"]
  assert turn(state, on_second, Pressed(key: "Enter")).goto == "stdlib.html#std-str-split"
  # the row that is already selected, and rows that do not exist, change nothing
  assert turn(state, on_second, Hovered(at: 1)) == on_second
  assert turn(state, m, Hovered(at: 2)) == m
  assert turn(state, m, Hovered(at: -1)) == m
}

## A phone has no Escape key; its Cancel button leaves in one press, query or
## no query.
test "cancel closes the panel at once" {
  let state = probe_state()
  let shut = turn(state, typed(state, "str."), Dismissed)
  assert not shut.open
  assert shut.query == ""
  let closed_kids: List[Node[Msg]] = []
  assert view(state, shut) == div(class: "search-panel is-closed", kids: closed_kids)
}

## The combobox pattern, as attributes: the field names the list it controls
## and the option that is active, the list is a listbox of groups of options,
## and the ids are the ordinals.
test "the field, the list and the rows carry the combobox roles" {
  let state = probe_state()
  let m = turn(state, typed(state, "str."), Pressed(key: "ArrowDown"))
  let v = view(state, m)
  let field = all_with_class(v, "search-input")[0]
  assert prop_of(field, "role") == "combobox"
  assert prop_of(field, "aria-expanded") == "true"
  assert prop_of(field, "aria-controls") == "dawn-search-list"
  assert prop_of(field, "aria-activedescendant") == "dawn-search-opt-1"
  assert prop_of(field, "aria-label") == "Search the site"
  let results = all_with_class(v, "search-results")[0]
  assert prop_of(results, "id") == "dawn-search-list"
  assert prop_of(results, "role") == "listbox"
  let rows = all_with_class(v, "search-row")
  assert list.map(rows, r => prop_of(r, "id")) == ["dawn-search-opt-0", "dawn-search-opt-1"]
  assert list.map(rows, r => prop_of(r, "role")) == ["option", "option"]
  assert list.map(rows, r => prop_of(r, "aria-selected")) == ["false", "true"]
  let rows_box = all_with_class(v, "search-group-rows")[0]
  assert prop_of(rows_box, "role") == "group"
  assert prop_of(rows_box, "aria-labelledby") == "dawn-search-g-stdlib"
  # with nothing listed the popup is collapsed and nothing is active
  let empty = state.view(typed(state, "nothing here")).all_with_class("search-input")[0]
  assert prop_of(empty, "aria-expanded") == "false"
  assert prop_of(empty, "aria-activedescendant") == ""
}

## Every label the panel adds is in the page's language.
test "the panel's own words follow the page's language" {
  let en = probe_state()
  let zh = State { ..en, lang: "zh-CN" }
  let m = typed(en, "str.")
  let en_text = en.view(m).show_tree()
  let zh_text = zh.view(m).show_tree()
  assert str.contains(en_text, "Cancel")
  assert str.contains(zh_text, "取消")
  assert not str.contains(zh_text, "Cancel")
  assert str.contains(en_text, "open")
  assert str.contains(zh_text, "打开")
  assert prop_of(zh.view(m).all_with_class("search-input")[0], "aria-label") == "搜索本站"
}

## The mark is where a word of the query begins a word of the text, or
## anywhere for a word beyond ASCII; overlapping places are one mark.
test "the query's words are marked where they begin a word" {
  let m1: List[Node[Msg]] = [
    text("io."),
    el("mark", kids: [text("read")]),
    text("_file"),
  ]
  assert marked("io.read_file", terms("read")) == m1
  # not inside a word
  let m2: List[Node[Msg]] = [text("bread")]
  assert marked("bread", terms("read")) == m2
  # case is the text's own, and two words that overlap are one mark
  let m3: List[Node[Msg]] = [el("mark", kids: [text("Handler")]), text(" state")]
  assert marked("Handler state", terms("hand handler")) == m3
  # a Chinese word is found inside a run
  let m4: List[Node[Msg]] = [text("6.5 命名"), el("mark", kids: [text("效果")])]
  assert marked("6.5 命名效果", terms("效果")) == m4
  # no query, no marks
  let m5: List[Node[Msg]] = [text("str.trim")]
  assert marked("str.trim", terms("")) == m5
  # and inside a note's code
  let m6: List[Node[Msg]] = [
    text("The file at "),
    el("code", kids: [el("mark", kids: [text("path")])]),
  ]
  assert marked_runs("The file at `path`", terms("path")) == m6
  # a word that is not the last is whole: `the` is not the start of `then`
  let m7: List[Node[Msg]] = [text("then "), el("mark", kids: [text("the")])]
  assert marked("then the", terms("the y")) == m7
}

fn prop_of(w: Node[Msg], name: String) -> String =
  match w {
    Text(_) -> ""
    Elem(_, props, ..) -> {
      var found = ""
      for p in props {
        let (k, v) = p
        if k == name {
          found = v
        }
      }
      found
    }
  }

## A shared `?q=` link is a query in the flags, and the first turn is already
## its answer. The recent queries ride in the same flags, and init keeps the
## ones it can use.
test "flags carry a shared query and the recent ones, and init answers both" {
  let flags = "{\"root\":\".\",\"mod\":\"Ctrl\",\"q\":\"str.\","
    ++ "\"recent\":[\"with handle\",\"  \",7,\"!io\",\"a\",\"b\",\"c\",\"d\"],"
    ++ "\"index\":{\"v\":1,\"lang\":\"en\",\"start\":[1,99],\"items\":["
    ++ "[\"stdlib\",\"str.trim\",\"fn trim(s: String) -> String\",\"\",\"stdlib.html#std-str-trim\"],"
    ++ "[\"stdlib\",\"str.split\",\"fn split()\",\"\",\"stdlib.html#std-str-split\"]]}}"
  let (state, m) = init(Some(flags))
  assert m.query == "str."
  assert m.hits == [0, 1]
  assert m.sel == 0
  assert m.open
  # blank and non-string entries are dropped, and no more than five are kept
  assert state.recent == ["with handle", "!io", "a", "b", "c"]
  assert state.mod_key == "Ctrl"
  assert state.start == [1, 99]
  # an id that names no entry is not a suggestion
  assert list.map(starts(state), e => e.title) == ["str.split"]
  # no query in the flags is the blank model, recent queries or not
  let (_, plain) = init(Some("{\"recent\":[\"x\"],\"index\":{\"items\":[]}}"))
  assert plain == blank()
}

fn idle_state() -> State = State { ..probe_state(), recent: ["with handle", "!io"], start: [4, 3, 0] }

## Before anything is typed the list holds the reader's recent queries and
## then the suggested entries, as one listbox with one run of ordinals.
test "an empty query lists the recent queries, then where to start" {
  let state = idle_state()
  let v = view(state, blank())
  assert kid_classes(v, "search-results") == ["search-group search-group-recent", "search-group search-group-start"]
  let rows = all_with_class(v, "search-row")
  assert list.map(rows, r => prop_of(r, "id"))
    == ["dawn-search-opt-0", "dawn-search-opt-1", "dawn-search-opt-2", "dawn-search-opt-3", "dawn-search-opt-4"]
  assert list.map(rows, r => prop_of(r, "role")) == ["option", "option", "option", "option", "option"]
  assert selected_titles(v) == ["with handle"]
  let field = all_with_class(v, "search-input")[0]
  assert prop_of(field, "aria-expanded") == "true"
  assert prop_of(field, "aria-activedescendant") == "dawn-search-opt-0"
  # each recent query names itself for the page to forget, and so does Clear
  let forget = all_with_class(v, "search-forget")
  assert list.map(forget, b => prop_of(b, "data-forget")) == ["with handle", "!io"]
  assert prop_of(forget[0], "aria-label") == "Remove “with handle” from recent searches"
  assert prop_of(all_with_class(v, "search-clear")[0], "data-forget-all") == "1"
  # the suggestions are links, in the index's order, under the page's root
  assert list.map(all_with_class(v, "search-start"), r => text_of(all_with_class(r, "search-title")[0]))
    == ["Effects", "6.5 Named effects", "str.trim"]
  assert list.take(hrefs(v), 3) == ["./tutorial/09.html", "./spec.html#s6-5", "./stdlib.html#std-str-trim"]
  # and with rows to show there is no prompt
  assert count_class(v, "search-status") == 0
  # no recent queries: no Recent group, and the suggestions number from 0
  let fresh = view(State { ..state, recent: [] }, blank())
  assert kid_classes(fresh, "search-results") == ["search-group search-group-start"]
  assert prop_of(all_with_class(fresh, "search-row")[0], "id") == "dawn-search-opt-0"
  # nothing at all to show: the prompt, as before
  let bare = probe_state().view(blank())
  assert count_class(bare, "search-group") == 0
  assert count_class(bare, "search-status") == 1
  assert prop_of(all_with_class(bare, "search-input")[0], "aria-expanded") == "false"
}

## The idle rows answer the same keys as results: Enter on a recent query
## asks it again, Enter on a suggestion opens it.
test "the keys move through the idle rows, and enter asks again or opens" {
  let state = idle_state()
  let m = blank()
  assert turn(state, m, Pressed(key: "End")).sel == 4
  assert turn(state, turn(state, m, Pressed(key: "End")), Pressed(key: "ArrowDown")).sel == 4
  assert turn(state, turn(state, m, Pressed(key: "End")), Pressed(key: "Home")).sel == 0
  let second = turn(state, m, Pressed(key: "ArrowDown"))
  assert second.sel == 1
  # a recent query is typed again, and answered
  let asked = turn(state, second, Pressed(key: "Enter"))
  assert asked.query == "!io"
  assert asked.hits == search(state, "!io")
  assert asked.goto == ""
  # a suggestion is a destination, like a result
  let third = turn(state, second, Pressed(key: "ArrowDown"))
  assert turn(state, third, Pressed(key: "Enter")).goto == "tutorial/09.html"
  # the pointer is bounded by the rows the list shows
  assert turn(state, m, Hovered(at: 4)).sel == 4
  assert turn(state, m, Hovered(at: 5)) == m
  # a click on the query is the same as Enter on it
  let (clicked, _) = update(state, m, Typed(text: "with handle"))
  assert clicked.query == "with handle"
}

## Home and End are the ends of the result list, wherever the selection is.
test "home and end jump to the first and the last result" {
  let state = probe_state()
  let m = typed(state, "str.")
  let last = turn(state, m, Pressed(key: "End"))
  assert last.sel == 1
  assert last.hits == m.hits
  assert turn(state, last, Pressed(key: "Home")).sel == 0
  # with no hits there is nowhere to go
  let none = typed(state, "nothing here")
  assert turn(state, none, Pressed(key: "End")).sel == 0
}

## A query with no hits says what was asked and offers three ways to ask
## again, in the page's language.
test "a query nothing answers says so, with three tips" {
  let en = probe_state()
  let v = view(en, typed(en, "  handel "))
  let block = all_with_class(v, "search-nothing")
  assert len(block) == 1
  assert text_of(all_with_class(v, "search-none-title")[0]) == "Nothing matches “handel”."
  assert count_class(v, "search-none-art") == 1
  let tips = kids_of(all_with_class(v, "search-tips")[0])
  assert len(tips) == 3
  assert text_of(tips[0]) == "Try the English name of an API: read_file, not 读文件."
  # the examples are code, letter for letter what a reader would type
  let io_code: Node[Msg] = el("code", kids: [text("!io")])
  let handle_code: Node[Msg] = el("code", kids: [text("with handle")])
  assert kids_of(tips[1])[1] == io_code
  assert kids_of(tips[1])[3] == handle_code
  # the probe index has no word near `handel`, so there is nothing to offer
  assert not str.contains(show_tree(v), "Did you mean")
  let zh = State { ..en, lang: "zh-CN" }
  let zv = view(zh, typed(zh, "handel"))
  assert text_of(all_with_class(zv, "search-none-title")[0]) == "没有匹配「handel」的结果。"
  assert text_of(kids_of(all_with_class(zv, "search-tips")[0])[2]) == "搜标题：效果系统、教程 17。"
  # the region that says it is the live one
  assert prop_of(all_with_class(v, "search-none")[0], "role") == "status"
}

## The foot names the modifier the reader's own keyboard has.
test "the new-tab hint uses the modifier the page names" {
  let ctrl = State { ..probe_state(), mod_key: "Ctrl" }
  let text_ctrl = ctrl.view(blank()).show_tree()
  assert str.contains(text_ctrl, "Ctrl")
  assert str.contains(text_ctrl, "new tab")
  assert str.contains(probe_state().view(blank()).show_tree(), "⌘")
  assert str.contains(view(State { ..ctrl, lang: "zh-CN" }, blank()).show_tree(), "新标签页")
}

## Copy link is in the foot only while the field holds a query, names itself
## for the page instead of carrying a listener, and draws both of its labels
## and its status line in the page's language.
test "the foot offers copy link only while there is a query" {
  let state = probe_state()
  assert state.view(blank()).count_class("search-copy") == 0
  assert state.view(typed(state, "   ")).count_class("search-copy") == 0
  let v = view(state, typed(state, "str."))
  let copy = all_with_class(v, "search-copy")
  assert len(copy) == 1
  assert all_with_class(all_with_class(v, "search-foot")[0], "search-copy").len() == 1
  assert prop_of(copy[0], "data-copy-link") == "1"
  assert prop_of(copy[0], "id") == "dawn-search-copy"
  let heard = match copy[0] {
    Text(_) -> -1
    Elem(_, _, on, ..) -> len(on)
  }
  assert heard == 0
  assert text_of(all_with_class(v, "search-copy-do")[0]) == "Copy link"
  assert text_of(all_with_class(v, "search-copy-done")[0]) == "Copied"
  assert prop_of(all_with_class(v, "search-copy-said")[0], "role") == "status"
  let zh = State { ..state, lang: "zh-CN" }
  let w = view(zh, typed(zh, "str."))
  assert text_of(all_with_class(w, "search-copy-do")[0]) == "复制链接"
  assert text_of(all_with_class(w, "search-copy-done")[0]) == "已复制"
  assert text_of(all_with_class(w, "search-copy-said")[0]) == "链接已复制"
  # a query with no hits can be shared as well: the link asks it again
  assert state.view(typed(state, "zzzz")).count_class("search-copy") == 1
}

## The pills narrow the matches the query already has: All and each group,
## with how many entries matched there, and the cap applies inside the one
## group a pill picks.
test "a scope pill narrows the list to one group and counts every group" {
  let state = probe_state()
  let m = typed(state, "e")
  # `e` begins a word of `6.5 Named effects` and of `Effects`, and of nothing else
  assert m.counts == [0, 1, 1, 0, 0]
  assert m.scope == -1
  let v = view(state, m)
  let ps = all_with_class(v, "search-pill")
  assert list.map(ps, p => text_of(p)) == ["All2", "Stdlib0", "Spec1", "Tutorial1", "Examples0", "History0"]
  assert list.map(ps, p => prop_of(p, "aria-pressed")) == ["true", "false", "false", "false", "false", "false"]
  # a group with nothing in it cannot be picked
  assert prop_of(ps[1], "disabled") == ""
  assert has_class(ps[1], "is-zero")
  assert not has_class(ps[2], "is-zero")
  # narrowing to Spec keeps the spec row only, and the counts
  let spec = turn(state, Model { ..m, sel: 1 }, Scoped(group: 1))
  assert spec.scope == 1
  assert spec.sel == 0
  assert list.map(scan(state, spec.hits, 0).hits, h => h.entry.title) == ["6.5 Named effects"]
  assert spec.counts == m.counts
  assert prop_of(state.view(spec).all_with_class("search-pill")[2], "aria-pressed") == "true"
  # the pill that is on changes nothing, and All undoes it
  assert turn(state, spec, Scoped(group: 1)) == spec
  assert turn(state, spec, Scoped(group: -1)).hits == m.hits
  # the scope survives typing while the group still has matches ...
  let more = turn(state, spec, Typed(text: "effects"))
  assert more.scope == 1
  assert list.map(scan(state, more.hits, 0).hits, h => h.entry.title) == ["6.5 Named effects"]
  # ... and falls back to All once it has none
  let other = turn(state, spec, Typed(text: "str."))
  assert other.scope == -1
  assert len(other.hits) == 2
  # no query, or nothing matched: the row is there and empty
  assert kids_of(state.view(blank()).all_with_class("search-pills")[0]) == []
  assert kids_of(state.view(typed(state, "nothing here")).all_with_class("search-pills")[0]) == []
  # escape takes the scope back with the query
  let cleared = turn(state, spec, Pressed(key: "Escape"))
  assert cleared.scope == -1
  assert cleared.counts == []
}

## The cap is per list, so narrowing to a group shows up to the cap of that
## group even when All had dealt it only a share.
test "narrowing deals the whole cap to the one group" {
  var es: List[Entry] = []
  for i in range(0, 45) {
    es = es ++ [probe_entry("stdlib", "fn${i} x", "", "stdlib.html#f${i}")]
  }
  es = es ++ [probe_entry("spec", "x spec", "", "spec.html#s1")]
  let state = state_of(es)
  let all = typed(state, "x")
  assert all.counts == [45, 1, 0, 0, 0]
  assert len(all.hits) == cap()
  let lib = turn(state, all, Scoped(group: 0))
  assert len(lib.hits) == cap()
  assert list.all(lib.hits, id => id < 45)
}

# ---- the documents' text ---------------------------------------------------

## The words of a paragraph, by the table in docs/site-search-design.md 3.2.
## That table is the contract with the generator that writes the body index
## (site/src/gen/search.dawn, whose test of the same name copies the same
## rows), so a change to either side is a change to the table.
test "a body's words split by the table in docs/site-search-design.md 3.2" {
  let samples: List[(String, List[String])] = [
    ("io.read_file", ["io", "read", "file", "io.read_file"]),
    ("!io 效果", ["io", "!io", "效", "果"]),
    ("!Fs", ["fs", "!fs"]),
    ("命名效果，处理器", ["命", "名", "效", "果", "处", "理", "器"]),
    ("Fs效果的 handler", ["fs", "handler", "效", "果", "的"]),
    ("str.trim 去掉空白", ["str", "trim", "str.trim", "去", "掉", "空", "白"]),
    ("6.5 具名效果", ["6", "5", "6.5", "具", "名", "效", "果"]),
    ("café λx", ["café", "λx"]),
    ("全角，标点。", ["全", "角", "标", "点"]),
    ("... ! -> ()", []),
  ]
  for sample in samples {
    let (s, words) = sample
    assert body_terms(s) == words
  }
}

## A body manifest in the asset's format (docs/site-search-design.md 13.4),
## built from sections and paragraphs with this file's [body_terms] the way the
## generator builds it with its own: per section how many paragraphs it holds
## (and the hash of its fragment, none for a section that holds none), and the
## words in code-point order cut into chunks of [fixture_chunk_words] words,
## each named by its first word and a fixed hash. The chunk directory is the
## fragment directory's sibling.
fn body_asset(version: Int, dir: String, secs: List[List[String]], paras: List[(Int, String)]) -> String = {
  let counts = list.map(range(0, len(secs)), i => len(list.filter(paras, x => {
    let (sec, _) = x
    sec == i
  })))
  var rows: List[Json] = []
  for i in range(0, len(secs)) {
    rows = rows ++ [JArr(items: list.map(secs[i], f => JStr(value: f)) ++ [JStr(value: if counts[i] > 0 { frag_hash() } else { "" })])]
  }
  let chunks = list.map(fixture_chunks(paras), c => {
    let (first, _) = c
    JArr(items: [JStr(value: first), JStr(value: chunk_hash())])
  })
  render(JArr(items: [
    JInt(value: version),
    JStr(value: dir),
    JArr(items: rows),
    JArr(items: list.map(counts, c => JInt(value: c))),
    JStr(value: str.replace(dir, "search-text", "search-index")),
    JArr(items: chunks),
  ]))
}

fn chunk_hash() -> String = "feed5678"

## How many words a fixture chunk holds: few, so that a handful of paragraphs
## makes several chunks and a prefix has chunks to span.
fn fixture_chunk_words() -> Int = 6

## The fixture's postings in chunks: (first word, the chunk's file text) for
## the words of `paras` in code-point order, [fixture_chunk_words] to a chunk.
fn fixture_chunks(paras: List[(Int, String)]) -> List[(String, String)] = {
  var table: Map[String, List[Int]] = map.empty()
  var p = 0
  for para in paras {
    let (_, text) = para
    for w in list.unique(body_terms(text)) {
      table = map.insert(table, w, map.get(table, w).unwrap_or([]) ++ [p])
    }
    p = p + 1
  }
  let t = table
  let words = map.keys(t).sort_by((a, b) => order(a, b))
  var out: List[(String, String)] = []
  var at = 0
  while at < len(words) {
    let here = list.slice(words, at, at + fixture_chunk_words())
    let gaps = list.map(here, w => "[" ++ join(list.map(map.get(t, w).unwrap_or([]).gaps_of(), g => to_string(g)), ",") ++ "]")
    out = out ++ [(here[0], "[${len(out)},[" ++ join(list.map(here, w => quoted(w)), ",") ++ "],[" ++ join(gaps, ",") ++ "]]")]
    at = at + fixture_chunk_words()
  }
  out
}

## The fixture's chunk files, by url, under `dir` with the `search-index`
## sibling of a fragment directory.
fn chunk_files(dir: String, paras: List[(Int, String)]) -> Map[String, String] = {
  var out: Map[String, String] = map.empty()
  var i = 0
  for c in fixture_chunks(paras) {
    let (_, text) = c
    out = map.insert(out, "${str.replace(dir, "search-text", "search-index")}/${i}.${chunk_hash()}.json", text)
    i = i + 1
  }
  out
}

fn frag_hash() -> String = "abcd1234"

## The fragments of the same sections, as the host would serve them: url to
## body, in the form the generator writes (`[section, [paragraph, ...]]`).
fn fragment_files(dir: String, secs: List[List[String]], paras: List[(Int, String)]) -> Map[String, String] = {
  var out: Map[String, String] = map.empty()
  for i in range(0, len(secs)) {
    let mine = list.filter(paras, x => {
      let (sec, _) = x
      sec == i
    })
    if len(mine) > 0 {
      let texts = list.map(mine, x => {
        let (_, text) = x
        quoted(text)
      })
      out = map.insert(out, "${dir}/${i}.${frag_hash()}.json", "[${i},[" ++ join(texts, ",") ++ "]]")
    }
  }
  out
}

fn gaps_of(ps: List[Int]) -> List[Int] = {
  var out: List[Int] = []
  var last = 0
  for p in ps {
    out = out ++ [p - last]
    last = p
  }
  out
}

fn en_secs() -> List[List[String]] = [
  ["spec", "spec.html", "Dawn Language Specification"],
  ["spec", "spec.html#s6-5", "6.5 Named effects"],
  ["spec", "spec.html#s6-5-4", "with handle"],
  ["tutorial", "tutorial/09.html#s0-2", "Handlers keep state"],
  ["design", "design.html#s2", "2. Non-goals"],
]

fn en_paras() -> List[(Int, String)] = [
  (0, "Status: normative."),
  (1, "Users declare effects and handle them."),
  (2, "with handle E { arms } installs a handler for the rest of the block."),
  (2, "Handler-local state: a handler keeps its cells, and the handler's arms read them."),
  (3, "A handler can keep state between operations."),
  (4, "Full algebraic effects with multiple resumption are out of scope."),
]

fn zh_secs() -> List[List[String]] = [
  ["spec", "zh/spec.html#s6-5", "6.5 命名效果"],
  ["tutorial", "zh/tutorial/09.html", "9. 效果"],
  ["history", "zh/history.html#s1", "历史"],
]

fn zh_paras() -> List[(Int, String)] = [
  (0, "用户声明效果，并在别处处理它们。"),
  (0, "效用与结果，处置与理由，各说各的。"),
  (1, "处在开头的理由，效与果分开出现，这一段被截断…"),
  (1, "`Fs`效 果的处理在这里：源文件里这一行折了。"),
  (2, "处于理想，效率结果都要，这一段同样被截断…"),
]

## Every fragment of both fixture documents, by url: what the host can serve.
fn fixture_files() -> Map[String, String] = {
  var out = fragment_files("search-text/en", en_secs(), en_paras())
  let others = [
    fragment_files("search-text/zh", zh_secs(), zh_paras()),
    chunk_files("search-text/en", en_paras()),
    chunk_files("search-text/zh", zh_paras()),
  ]
  for files in others {
    for k in map.keys(files) {
      out = map.insert(out, k, map.get(files, k).unwrap_or(""))
    }
  }
  out
}

## `state` with every chunk its manifest names read from `files`, as if the
## host had answered them all: for the tests that ask a question of the state
## directly and are not about the words arriving.
fn with_words(state: State, files: Map[String, String]) -> State = {
  var st = state
  match state.body {
    None -> ()
    Some(b) -> {
      for i in range(0, len(b.chunks)) {
        let outcome: Result[String, String] = match map.get(files, chunk_url(state, i)) {
          Some(text) -> Ok(text)
          None -> Err("HTTP 404")
        }
        st = absorb(st, chunk_tag(i), outcome)
      }
    }
  }
  st
}

## The probe index, with the sections of five documents beside it and the
## words of all of them. No section's text has arrived yet: that is what
## [drive] brings.
fn text_state() -> State = with_words(bare_state(), fixture_files())

## The same, with the manifest only: not a chunk of words has arrived.
fn bare_state() -> State = {
  let titles = probe_state()
  let j = body_asset(3, "search-text/en", en_secs(), en_paras()).json_of()
  State { ..titles, body: body_of(j, titles.entries) }
}

## One message, as the host would carry it out: fold it with what it commands,
## answer every fetch from `files` (a url not in it is a 404), put the text in
## the state ([absorb]) and fold the arrival, until nothing is left to ask.
## Returns the state the panel ends with beside the model, because the text a
## row shows is in the state.
fn drive(state: State, m: Model, msg: Msg) -> (State, Model) = {
  let (m1, wanted) = fold_cmds(m, msg, (acc, x) => update(state, acc, x))
  var st = state
  var mo = m1
  var queue = wanted
  while len(queue) > 0 {
    let f = queue[0]
    queue = list.drop(queue, 1)
    let outcome: Result[String, String] = match map.get(fixture_files(), f.url) {
      Some(b) -> Ok(b)
      None -> Err("HTTP 404")
    }
    st = absorb(st, f.tag, outcome)
    let here = st
    let (m2, more) = fold_cmds(mo, supplied(f.tag, outcome), (acc, x) => update(here, acc, x))
    mo = m2
    queue = queue ++ more
  }
  (st, mo)
}

## The panel after `q` is typed into a fresh one and everything it asked for
## has come.
fn world(state: State, q: String) -> (State, Model) = drive(state, blank(), Typed(text: q))

fn sections_of(hs: List[BodyHit]) -> List[(Int, Int)] = list.map(hs, h => (h.sec, h.rank))

test "the manifest is read in format 3 only, and a chunk's gaps are added up when it arrives" {
  let titles = probe_state()
  let asset = body_asset(3, "search-text/en", en_secs(), en_paras())
  match asset.json_of().body_of(titles.entries) {
    Some(b) -> {
      assert b.dir == "search-text/en"
      assert b.chunk_dir == "search-index/en"
      assert len(b.secs) == 5
      assert len(b.paras) == 6
      # the counts [1, 1, 2, 1, 1] number the paragraphs section by section,
      # each from 0 within its own
      assert list.map(b.paras, p => (p.sec, p.nth)) == [(0, 0), (1, 0), (2, 0), (2, 1), (3, 0), (4, 0)]
      assert b.secs[2].frag == "abcd1234"
      # the manifest has the chunks' first words, in code-point order, and
      # nothing else about the words
      assert len(b.chunks) > 3
      assert b.chunks[0].first == "a"
      assert list.all(range(1, len(b.chunks)), k => order(b.chunks[k - 1].first, b.chunks[k].first) < 0)
      # a word is in the last chunk that starts at or before it
      assert chunk_at(b, "a") == 0
      assert chunk_at(b, "") == -1
      assert chunk_at(b, "zzzz") == len(b.chunks) - 1
      let i = chunk_at(b, "handler")
      assert order(b.chunks[i].first, "handler") <= 0
      assert i + 1 == len(b.chunks) || order("handler", b.chunks[i + 1].first) < 0
      # `handler` is in paragraphs 2, 3 and 4, written as the gaps 2, 1, 1
      let st = with_words(State { ..titles, body: Some(b) }, fixture_files())
      let c = posts_at(st, i)
      let at = lower_bound(c.terms, "handler")
      assert c.terms[at] == "handler"
      assert c.posts[at] == [2, 3, 4]
      # the words of a chunk are in code-point order
      assert list.all(range(1, len(c.terms)), k => order(c.terms[k - 1], c.terms[k]) < 0)
      # the section the title index also has knows its row, and the
      # design notes are drawn with history
      assert b.secs[1].entry == 3
      assert b.secs[2].entry == -1
      assert b.secs[4].group == group_index("history")
    }
    None -> panic("a format 3 manifest must be read")
  }
  # another version, or something that is not one, is no body at all
  let other = body_asset(1, "search-text/en", en_secs(), en_paras()).json_of()
  assert not has_body(State { ..titles, body: body_of(other, titles.entries) })
  let two = body_asset(2, "search-text/en", en_secs(), en_paras()).json_of()
  assert not has_body(State { ..titles, body: body_of(two, titles.entries) })
  assert not has_body(State { ..titles, body: body_of(JNull, titles.entries) })
  # a count list that does not match the section table is not a manifest
  # either, nor is one that lists no chunk
  match parse("[3,\"d\",[[\"spec\",\"a\",\"A\",\"\"]],[],\"c\",[[\"a\",\"00000000\"]]]") {
    Ok(j) -> {
      assert not has_body(State { ..titles, body: body_of(j, titles.entries) })
    }
    Err(e) -> panic("the literal must parse: ${e}")
  }
  match parse("[3,\"d\",[[\"spec\",\"a\",\"A\",\"\"]],[0],\"c\",[]]") {
    Ok(j) -> {
      assert not has_body(State { ..titles, body: body_of(j, titles.entries) })
    }
    Err(e) -> panic("the literal must parse: ${e}")
  }
}

## It arrives in the flags, and the foot says what is searched either way.
test "the flags carry the body index, and the foot says whether it is in" {
  let index = "\"index\":{\"v\":1,\"lang\":\"en\",\"items\":[]}"
  let (with_body, _) = init(Some("{${index},\"body\":${body_asset(3, "search-text/en", en_secs(), en_paras())}}"))
  assert has_body(with_body)
  let (old_body, _) = init(Some("{${index},\"body\":${body_asset(1, "search-text/en", en_secs(), en_paras())}}"))
  assert not has_body(old_body)
  let (none, _) = init(Some("{${index}}"))
  assert not has_body(none)
  assert str.contains(with_body.view(blank()).show_tree(), "Searches titles, API names and the documents' text.")
  assert str.contains(old_body.view(blank()).show_tree(), "Searches titles and API names, not body text.")
  let zh = State { ..with_body, lang: "zh-CN" }
  assert str.contains(zh.view(blank()).show_tree(), "搜标题、API 名与文档正文。")
  assert prop_of(with_body.view(blank()).all_with_class("search-input")[0], "placeholder")
    == "Search titles, API names and text"
}

## Every word whole but the ones the query ends with, which are the start of
## a word; a Han character is always whole.
test "a query's words for the text, the ones it ends with as prefixes" {
  assert body_query("io.read_fi") == [
    BodyTerm { word: "io", prefix: false },
    BodyTerm { word: "read", prefix: false },
    BodyTerm { word: "fi", prefix: true },
    BodyTerm { word: "io.read_fi", prefix: true },
  ]
  assert body_query("Keep sta") == [BodyTerm { word: "keep", prefix: false }, BodyTerm { word: "sta", prefix: true }]
  assert body_query("fs 效果") == [
    BodyTerm { word: "fs", prefix: false },
    BodyTerm { word: "效", prefix: false },
    BodyTerm { word: "果", prefix: false },
  ]
  assert han_runs("效果 处理 x 效") == ["效果", "处理"]
  # one letter is not yet a prefix
  assert body_query("handle s") == [BodyTerm { word: "handle", prefix: false }, BodyTerm { word: "s", prefix: false }]
}

## A paragraph has to have every word, and the sections are the rows.
test "the text answers with the sections whose paragraphs have every word" {
  let state = text_state()
  # `keep` is whole: the paragraph with `keeps` does not have it
  assert state.body_hits("keep sta").sections_of() == [(3, 0)]
  # `handl` is the start of `handle`, `handler` and `handler's`
  assert state.body_hits("handl").sections_of() == [(1, 0), (2, 0), (3, 0)]
  let none: List[(Int, Int)] = []
  assert state.body_hits("keep effects").sections_of() == none
  # and no text at all before the page has given it
  assert probe_state().body_hits("handl").sections_of() == none
}

## One row per section, and its excerpt is the paragraph where the words are
## densest, not the section's first: paragraph 3 says `handler` three times.
test "a section's row shows the paragraph where the words are densest" {
  let (state, m) = world(text_state(), "handler")
  assert list.filter(m.hits, id => id >= body_base()) == [body_base() + 3, body_base() + 4]
  let v = view(state, m)
  let rows = all_with_class(v, "search-row")
  assert list.map(rows, r => text_of(all_with_class(r, "search-title")[0])) == ["with handle", "Handlers keep state"]
  assert list.map(rows, r => text_of(all_with_class(r, "search-detail")[0]))
    == ["Spec › §6.5.4", "Tutorial › Chapter 9"]
  # the words are marked in the excerpt, where they begin a word
  let note = all_with_class(rows[0], "search-note")[0]
  assert list.map(all_with_tag(note, "mark"), k => text_of(k)) == ["Handler", "handler", "handler"]
  # the row goes to the section
  assert hrefs(v) == ["./spec.html#s6-5-4", "./tutorial/09.html#s0-2"]
  assert turn(state, m, Pressed(key: "Enter")).goto == "spec.html#s6-5-4"
  # the model carries the paragraph, and reads back the same
  assert m.encode().decode() == m
  assert str.contains(encode(m), "\"hits\":[1000003,1000004]")
}

## A title row is above every section of the text, and a section a title row
## already answered for is that row and not a second one.
test "the text ranks below the titles and never repeats a title row" {
  let (state, m) = world(text_state(), "effects")
  # `Effects` is a title, `6.5 Named effects` has the word in its title and
  # its text, and the design notes have it only in their text
  assert m.hits == [4, 3, body_base() + 5]
  assert m.counts == [0, 1, 1, 0, 1]
  let v = view(state, m)
  assert kid_classes(v, "search-results") == ["search-group hue-3", "search-group hue-2", "search-group hue-2"]
  assert text_of(all_with_class(v, "search-detail")[2]) == "Early decisions"
  # and only the section of the text is marked as one
  assert list.map(all_with_class(v, "search-row"), r => has_class(r, "search-text")) == [false, false, true]
  # the history pill narrows to the text's row
  let hist = turn(state, m, Scoped(group: 4))
  assert hist.hits == [body_base() + 5]
  # without the text the same query has the two title rows only
  assert probe_state().typed("effects").hits == [4, 3]
  assert probe_state().typed("effects").counts == [0, 1, 1, 0, 0]
}

## A question typed as a sentence has words no paragraph has all of. When
## that is so for three words or more, the paragraphs with at least half of
## them answer, weighed by how rare their words are, below every other row.
test "a longer query nothing answers whole is answered by most of its words" {
  let state = text_state()
  assert state.body_hits("where does the block handle").sections_of() == [(2, -2)]
  let none: List[(Int, Int)] = []
  # two words are not a sentence: both, or nothing
  assert state.body_hits("where handle").sections_of() == none
  # and a query that does have an answer whole is not loosened
  assert state.body_hits("the handler arms").sections_of() == [(2, 0)]
}

## Chinese is indexed by character, so a phrase is checked in the text of the
## paragraphs that have its characters. Until a section's text has arrived it
## cannot be, and its candidates are kept a tier lower; once it has, a candidate
## has the phrase and is sure, or has not and is gone.
test "a Chinese phrase is checked in the candidates' text once it has arrived" {
  let j = body_asset(3, "search-text/zh", zh_secs(), zh_paras()).json_of()
  let state = with_words(State { ..blank_state(), lang: "zh-CN", body: body_of(j, []) }, fixture_files())
  # nothing can be checked yet: every paragraph with all the characters is a
  # "may have it", paragraph 1 of section 0 and paragraph 2 of section 1 too
  assert state.body_hits("效果 处理").sections_of() == [(0, -1), (1, -1), (2, -1)]
  let (loaded, m) = world(state, "效果 处理")
  # paragraph 1 has every character and neither phrase; paragraph 3 has
  # `效果` across a folded line; paragraph 4 has the characters but not the
  # phrase, and goes
  assert loaded.body_hits("效果 处理").sections_of() == [(0, 0), (1, 0)]
  let hs = body_hits(loaded, "效果 处理")
  assert hs[0].paras == [0]
  assert hs[1].paras == [3]
  # one character is a word, and there is no phrase to check
  assert loaded.body_hits("效").sections_of() == [(0, 0), (1, 0), (2, 0)]
  let v = view(loaded, m)
  assert list.map(all_with_class(v, "search-detail"), d => text_of(d)) == ["规范 › §6.5", "教程 › 第 9 章"]
  # the phrase is marked in the excerpt
  assert list.map(all_with_tag(all_with_class(v, "search-note")[0], "mark"), k => text_of(k)) == ["效果", "处理"]
}

# ---- fetching the text ----

fn fetch_urls(c: Cmd[Msg]) -> List[String] = list.map(fetches(c), f => f.url)

## The words arrive in chunks, on demand (docs/site-search-design.md 13.11). A
## query asks for the chunks its words are in, before anything else; until they
## are here the text answers nothing and the titles answer alone; once they are
## here the answer is the one a panel holding every chunk gives.
test "a query asks for the chunks of its words and the text answers when they are here" {
  let bare = bare_state()
  let (m, c) = update(bare, blank(), Typed(text: "handler"))
  assert list.all(m.hits, h => h < body_base())
  assert len(m.loading) == 1
  assert fetch_urls(c) == ["search-index/en/${m.loading[0]}.feed5678.json"]
  assert str.contains(encode(m), "\"loading\":[")
  # the same keystroke again does not ask again for a chunk on its way
  let (m2, c2) = update(bare, m, Typed(text: "handler"))
  assert fetch_urls(c2) == []
  assert m2.loading == m.loading
  # the chunk arrives: the words are in the state, the message says which
  let outcome: Result[String, String] = Ok(map.get(fixture_files(), "search-index/en/${m.loading[0]}.feed5678.json").unwrap_or(""))
  let here = absorb(bare, "c${m.loading[0]}", outcome)
  assert supplied("c${m.loading[0]}", outcome) == Loaded(chunk: m.loading[0])
  let (m3, c3) = update(here, m, Loaded(chunk: m.loading[0]))
  assert m3.loading == []
  assert m3.hits == [body_base() + 2, body_base() + 4]
  assert fetch_urls(c3) == ["search-text/en/2.abcd1234.json", "search-text/en/3.abcd1234.json"]
  # a model that is waiting says so on the wire, and only then
  assert decode(encode(m)) == m
  assert not str.contains(encode(m3), "loading")
}

## Chunking changes what is fetched and nothing about the answer: every query
## ends, once the host has answered what it asked, with the rows, counts and
## suggestion a panel holding all the chunks from the start gives.
test "a panel that fetches its chunks as it goes ends where one that has them all begins" {
  for q in ["handler", "handler state", "with handle", "the", "effects", "han", "ha", "handel", "wiht handel",
    "where does the spec say handle", "xyzzyx", "io.read_file", "algebraic effects multiple", "st", "s"] {
    let (_, lazy) = world(bare_state(), q)
    let (_, full) = world(text_state(), q)
    assert lazy.hits == full.hits
    assert lazy.counts == full.counts
    assert lazy.fix == full.fix
    assert lazy.fix_hits == full.fix_hits
    assert lazy.loading == []
  }
  for q in ["效果", "效果 处理", "处理器", "效", "理由"] {
    let j = body_asset(3, "search-text/zh", zh_secs(), zh_paras()).json_of()
    let zh = State { ..blank_state(), lang: "zh-CN", body: body_of(j, []) }
    let (_, lazy) = world(zh, q)
    let (_, full) = world(with_words(zh, fixture_files()), q)
    assert lazy.hits == full.hits
    assert lazy.counts == full.counts
    assert lazy.loading == []
  }
}

## A prefix is a run of the sorted words and a run can cross a chunk boundary:
## its postings are the union over every chunk the run touches, whatever the
## chunk size. Checked against a scan of every word of every chunk, for each
## prefix of two and three letters of every word the fixture has.
test "a prefix spanning chunks finds what a scan of all the words finds" {
  let state = text_state()
  match state.body {
    None -> panic("the text state has a body")
    Some(b) -> {
      var all_terms: List[String] = []
      var all_posts: List[List[Int]] = []
      for i in range(0, len(b.chunks)) {
        all_terms = all_terms ++ posts_at(state, i).terms
        all_posts = all_posts ++ posts_at(state, i).posts
      }
      var prefixes: List[String] = []
      for w in all_terms {
        for n in [2, 3] {
          if len(w) >= n && not list.contains(prefixes, str.take(w, n)) {
            prefixes = prefixes ++ [str.take(w, n)]
          }
        }
      }
      var spanning = 0
      for p in prefixes {
        var scan: List[List[Int]] = []
        for i in range(0, len(all_terms)) {
          if str.starts_with(all_terms[i], p) {
            scan = scan ++ [all_posts[i]]
          }
        }
        assert postings(state, b, BodyTerm { word: p, prefix: true }) == union(scan)
        if len(chunks_for(b, p, true)) > 1 {
          spanning = spanning + 1
        }
      }
      assert len(prefixes) > 20
      assert spanning > 0
    }
  }
}

## A chunk that cannot be had is recorded as having no words and is not asked
## for again, so a missing file costs the words in it and not a request per key.
test "a chunk that failed, or is not the one the manifest describes, has no words and is not asked again" {
  let bare = bare_state()
  let (m, _) = update(bare, blank(), Typed(text: "handler"))
  let c = m.loading[0]
  let good = map.get(fixture_files(), "search-index/en/${c}.feed5678.json").unwrap_or("")
  assert len(posts_at(absorb(bare, "c${c}", Ok(good)), c).terms) > 0
  assert posts_at(absorb(bare, "c${c}", Err("HTTP 404")), c) == Posts { terms: [], posts: [] }
  assert posts_at(absorb(bare, "c${c}", Ok("<html>")), c).terms == []
  assert posts_at(absorb(bare, "c${c}", Ok(str.replace(good, "[${c},", "[${c + 1},"))), c).terms == []
  assert posts_at(absorb(bare, "c${c}", Ok("[${c},[\"a\",\"b\"],[[1]]]")), c).terms == []
  assert absorb(bare, "c999", Ok(good)).chunks == bare.chunks
  let failed = absorb(bare, "c${c}", Err("HTTP 404"))
  let (m2, c2) = update(failed, Model { ..m, loading: [] }, Typed(text: "handler"))
  assert fetch_urls(c2) == []
  assert m2.hits == []
}

## Typing a word whose chunk has not been fetched must not blank the text
## section the previous query showed: while any chunk the query needs is on
## its way the panel keeps the last settled view as it was, and swaps to the
## new settled answer when the chunks are here. Every message of typing
## `handler state` is checked, with the host's replies held back one at a time.
test "while chunks are on their way the panel keeps the last settled view, never an empty text section" {
  let full = text_state()
  var st = bare_state()
  var m = blank()
  var settled = blank()
  let cs = code_points("handler state")
  var kept = 0
  for k in range(1, len(cs) + 1) {
    let text = from_code_points(list.take(cs, k))
    let here0 = st
    let (m1, wanted) = fold_cmds(m, Typed(text: text), (acc, x) => update(here0, acc, x))
    m = m1
    var queue = wanted
    var first = true
    while first || len(queue) > 0 {
      if not first {
        let f = queue[0]
        queue = list.drop(queue, 1)
        let outcome: Result[String, String] = match map.get(fixture_files(), f.url) {
          Some(b) -> Ok(b)
          None -> Err("HTTP 404")
        }
        st = absorb(st, f.tag, outcome)
        let here = st
        let (m2, more) = fold_cmds(m, supplied(f.tag, outcome), (acc, x) => update(here, acc, x))
        m = m2
        queue = queue ++ more
      }
      first = false
      let texty = list.any(settled.hits, h => h >= body_base())
      let wanted_text = list.any(answer(full, text, -1).hits, h => h >= body_base())
      if len(m.loading) > 0 {
        if texty {
          # waiting: exactly the last settled rows, counts and grouping
          assert m.hits == settled.hits
          assert m.counts == settled.counts
          assert m.scope == settled.scope && m.sel == settled.sel && m.fix == settled.fix
          assert m.stale == settled.query
          assert m.query == text
          let tree = st.view(m).show_tree()
          assert str.contains(tree, "search-results is-stale")
          assert str.contains(tree, "aria-busy")
          kept = kept + 1
        }
      } else {
        # settled: the answer a panel holding every chunk gives
        assert list.any(m.hits, h => h >= body_base()) == wanted_text
        assert m.hits == answer(full_with_texts(st), text, -1).hits
        assert m.stale == ""
        assert not str.contains(st.view(m).show_tree(), "aria-busy")
        settled = m
      }
    }
  }
  assert kept > 0
  # clearing the query clears at once, whatever is on its way
  let (cleared, _) = update(st, Model { ..settled, stale: "handler", query: "handler s", loading: [1] }, Typed(text: ""))
  assert cleared.hits == [] && cleared.stale == ""
  # the snapshot is on the wire only while it is one
  assert not str.contains(encode(settled), "stale")
  let stale_m = Model { ..settled, stale: "handler", query: "handler s" }
  assert decode(encode(stale_m)) == stale_m
}

## `full` with the section texts `st` has fetched, so that the paragraph a row
## shows is chosen the way the live panel chose it.
fn full_with_texts(st: State) -> State = State { ..text_state(), texts: st.texts }

## While the words are on their way a query nothing has answered is not "no
## matches": the panel is waiting, and says nothing until it knows.
test "a query waiting for its words does not say that nothing matches" {
  let bare = bare_state()
  let (m, _) = update(bare, blank(), Typed(text: "zzyzx"))
  assert m.hits == []
  assert len(m.loading) > 0
  assert m.fix == ""
  assert not str.contains(bare.view(m).show_tree(), "Nothing matches")
  let (_, done) = world(bare, "zzyzx")
  assert str.contains(bare.view(done).show_tree(), "Nothing matches")
}

## The first answer is from the index alone. The rows on screen ask for their
## sections' files, once each, under names the index gives them.
test "the rows on screen ask for their sections' text, once" {
  let state = text_state()
  let (m, c) = update(state, blank(), Typed(text: "handler"))
  assert m.hits == [body_base() + 2, body_base() + 4]
  assert fetch_urls(c) == ["search-text/en/2.abcd1234.json", "search-text/en/3.abcd1234.json"]
  assert list.map(fetches(c), f => f.tag) == ["t2", "t3"]
  assert m.asked == [2, 3]
  # no text yet: the rows are there, with their title and place and no excerpt
  let rows = all_with_class(view(state, m), "search-row")
  assert len(rows) == 2
  assert list.map(rows, r => text_of(all_with_class(r, "search-title")[0])) == ["with handle", "Handlers keep state"]
  assert list.map(rows, r => len(all_with_class(r, "search-note"))) == [0, 0]
  # the next keystroke asks for nothing that is already on its way
  let (m2, c2) = update(state, m, Typed(text: "handle"))
  assert fetch_urls(c2) == ["search-text/en/1.abcd1234.json"]
  assert m2.asked == [2, 3, 1]
  let (_, c3) = update(state, m2, Typed(text: "handler"))
  assert fetch_urls(c3) == []
}

test "a section's text arriving changes the answer and the row, and is asked for no more" {
  let state = text_state()
  let (m, _) = update(state, blank(), Typed(text: "handler"))
  # section 2 answers with paragraphs 2 and 3; without text the first stands in
  assert m.hits[0] == body_base() + 2
  let outcome: Result[String, String] = Ok(map.get(fixture_files(), "search-text/en/2.abcd1234.json").unwrap_or(""))
  let kept = absorb(state, "t2", outcome)
  let (m2, c2) = update(kept, m, supplied("t2", outcome))
  assert m2.asked == [3]
  assert fetch_urls(c2) == []
  # paragraph 3 says `handler` three times in what the row shows: it is the one
  assert m2.hits == [body_base() + 3, body_base() + 4]
  let note = all_with_class(all_with_class(view(kept, m2), "search-row")[0], "search-note")[0]
  assert list.map(all_with_tag(note, "mark"), k => text_of(k)) == ["Handler", "handler", "handler"]
  # the selection stayed where it was
  let (moved, _) = update(kept, m2, Hovered(at: 1))
  let (after, _) = update(kept, moved, Arrived(sec: 3))
  assert after.sel == 1
}

test "a fragment that failed, or is not the one the index describes, is no text and is not asked again" {
  let state = text_state()
  let files = fixture_files()
  let good = map.get(files, "search-text/en/2.abcd1234.json").unwrap_or("")
  assert map.get(absorb(state, "t2", Ok(good)).texts, 2) == Some(["with handle E { arms } installs a handler for the rest of the block.",
    "Handler-local state: a handler keeps its cells, and the handler's arms read them."])
  # a 404, text that is not JSON, another section's number, a different count
  let none: List[String] = []
  assert map.get(absorb(state, "t2", Err("HTTP 404")).texts, 2) == Some(none)
  assert map.get(absorb(state, "t2", Ok("<html>")).texts, 2) == Some(none)
  assert map.get(absorb(state, "t2", Ok("[3,[\"a\",\"b\"]]")).texts, 2) == Some(none)
  assert map.get(absorb(state, "t2", Ok("[2,[\"a\"]]")).texts, 2) == Some(none)
  # and a tag that is not a section of this index changes nothing
  assert absorb(state, "t99", Ok(good)).texts == state.texts
  assert absorb(state, "other", Ok(good)).texts == state.texts
  assert supplied("other", Ok("")) == Arrived(sec: -1)
  # a failed section stays asked for no more, and its row has no excerpt
  let failed = absorb(state, "t2", Err("HTTP 404"))
  let (m, c) = update(failed, blank(), Typed(text: "handler"))
  assert fetch_urls(c) == ["search-text/en/3.abcd1234.json"]
  let first = all_with_class(view(failed, m), "search-row")[0]
  assert len(all_with_class(first, "search-note")) == 0
  let (m3, c3) = update(failed, m, Arrived(sec: 2))
  assert fetch_urls(c3) == []
  assert m3.hits == m.hits
}

## Text that comes late reorders: a candidate that could not be checked is in
## the tier below, and joins or leaves the first tier when its text is here.
test "a late fragment moves a Chinese candidate between tiers" {
  let j = body_asset(3, "search-text/zh", zh_secs(), zh_paras()).json_of()
  let state = with_words(State { ..blank_state(), lang: "zh-CN", body: body_of(j, []) }, fixture_files())
  let (m, c) = update(state, blank(), Typed(text: "效果 处理"))
  assert len(m.hits) == 3
  # the three rows, and both asked for and unchecked sections are the same three
  assert fetch_urls(c) == ["search-text/zh/0.abcd1234.json", "search-text/zh/1.abcd1234.json", "search-text/zh/2.abcd1234.json"]
  let outcome: Result[String, String] = Ok(map.get(fixture_files(), "search-text/zh/2.abcd1234.json").unwrap_or(""))
  let kept = absorb(state, "t2", outcome)
  let (m2, _) = update(kept, m, supplied("t2", outcome))
  # section 2's only candidate has the characters but not the phrase: gone
  assert len(m2.hits) == 2
}

test "the model says what it is waiting for only while it is waiting" {
  let m = blank()
  assert not str.contains(encode(m), "asked")
  let w = Model { ..m, asked: [4, 9] }
  assert str.ends_with(encode(w), ",\"asked\":[4,9]}")
  assert decode(encode(w)) == w
  assert decode(encode(m)) == m
}

## Rows past the first screen are asked for as the selection nears them, not
## before: the fourteen sections here answer, ten are fetched, and moving to
## the last row asks for the rest.
test "rows further down ask for their text when the selection comes near" {
  var secs: List[List[String]] = []
  var paras: List[(Int, String)] = []
  for i in range(0, 14) {
    secs = secs ++ [["spec", "spec.html#s${i}", "Part ${i}"]]
    paras = paras ++ [(i, "common word${i}")]
  }
  let j = body_asset(3, "search-text/en", secs, paras).json_of()
  let state = with_words(State { ..blank_state(), body: body_of(j, []) }, chunk_files("search-text/en", paras))
  let (m, c) = update(state, blank(), Typed(text: "common"))
  assert len(m.hits) == 14
  assert len(fetches(c)) == 10
  let (m2, c2) = update(state, m, Pressed(key: "End"))
  assert m2.sel == 13
  assert fetch_urls(c2) == ["search-text/en/10.abcd1234.json", "search-text/en/11.abcd1234.json", "search-text/en/12.abcd1234.json", "search-text/en/13.abcd1234.json"]
  # five rows of look-ahead: resting on row 6 asks for the row past ten, and
  # each arrow down after it for one more
  let (m3, c3) = update(state, m, Hovered(at: 6))
  assert fetch_urls(c3) == ["search-text/en/10.abcd1234.json"]
  let (_, c4) = update(state, m3, Pressed(key: "ArrowDown"))
  assert fetch_urls(c4) == ["search-text/en/11.abcd1234.json"]
}

## The panel's cut and the generator's width table are one rule written twice
## (site/src/gen/search_body.dawn `columns`), and this pins the panel's half.
test "an excerpt is cut at a blank and marked, in display columns" {
  assert excerpt("short.") == "short."
  let long = str.repeat("word ", 30) ++ str.repeat("longword ", 30)
  let cut = excerpt(long)
  assert str.ends_with(cut, "…")
  let kept = code_points(cut)
  assert len(kept) <= excerpt_len() + 1
  # the kept text is a prefix of the paragraph that ends at a word boundary
  let body = from_code_points(list.take(kept, len(kept) - 1))
  assert str.starts_with(long, body)
  assert char.is_space(code_points(long)[len(kept) - 1])
  assert not str.ends_with(body, " ")
  # no blank to cut at: the bound, which a Han character fills two columns at a time
  assert len(code_points(excerpt(str.repeat("效", 300)))) == excerpt_len() / 2 + 1
  # exactly at the bound is not cut
  let exact = str.repeat("x", excerpt_len())
  assert excerpt(exact) == exact
  let exact_han = str.repeat("效", excerpt_len() / 2)
  assert excerpt(exact_han) == exact_han
  assert columns('a') == 1
  assert columns('é') == 1
  assert columns('效') == 2
  assert columns('，') == 2
  assert columns('「') == 2
  # mixed: an ASCII word between Han runs, cut at the blank after it
  let mixed = str.repeat("效", 40) ++ " Fs " ++ str.repeat("果", 100)
  assert excerpt(mixed) == str.repeat("效", 40) ++ " Fs" ++ "…"
  # a wide character that would straddle the bound is left out
  let odd = "x" ++ str.repeat("效", 100)
  assert len(code_points(excerpt(odd))) == 1 + (excerpt_len() - 1) / 2 + 1
}

# ---- near misses ----

## The distance, on the samples that decide what it is: a swap of two
## neighbours is one edit, two edits are two, and past the limit the answer
## is the limit plus one however far it really is.
test "the edit distance counts a swap as one edit and stops at its limit" {
  assert distance("handel", "handle", 2) == 1
  assert distance("efect", "effect", 2) == 1
  assert distance("hahsmap", "hashmap", 2) == 1
  assert distance("wiht", "with", 1) == 1
  assert distance("hendl", "handle", 2) == 2
  assert distance("handle", "handle", 2) == 0
  assert distance("kitten", "sitting", 3) == 3
  # the swap is of neighbours that stay swapped: `ca` to `abc` is three, not
  # the two of the unrestricted distance
  assert distance("ca", "abc", 3) == 3
  # beyond the limit, by length or by edits
  assert distance("ab", "abcd", 1) == 2
  assert distance("hadl", "handle", 1) == 2
  assert distance("handle", "zzzzzz", 2) == 3
  # the limit follows the length of the query word: none under three code
  # points, one up to four, two from five on
  assert list.map(range(1, 8), n => allowed(n)) == [0, 0, 1, 1, 2, 2, 2]
}

## The length rule, through the whole suggestion: `hendl` has five letters and
## may be two edits from `handle`; `hadl` has four and may not.
test "a word of five letters may be two edits off, a shorter one only one" {
  let state = text_state()
  let (fix, _) = suggest(state, "hendl")
  assert fix == "handle"
  assert suggest(state, "hadl") == ("", 0)
  # one edit under five letters, and none under three
  assert list.map(near_words(state, "wiht", false), x => x.word) == ["with"]
  assert near_words(state, "ha", false) == []
}

## Every word of the index that begins with the query word's letter and is
## within reach is a candidate: the same answer as measuring every word of
## both indexes and keeping those. The letters chosen sit at both ends of the
## sorted words (`a`, `w`) and in the middle, with words from the titles and
## from the text in one bucket.
test "the first-letter bucket misses no word that a walk of the whole index finds" {
  let state = text_state()
  var vocab: List[String] = []
  for k in state.keys {
    vocab = vocab ++ k.words
  }
  match state.body {
    Some(b) -> {
      for i in range(0, len(b.chunks)) {
        vocab = vocab ++ posts_at(state, i).terms
      }
    }
    None -> panic("the text state has a body")
  }
  let every_word = list.unique(vocab)
  for w in ["arns", "wiht", "thet", "hendl", "handel", "efects", "stae", "remve", "spilt"] {
    let limit = len(w).allowed()
    let walked = list.filter(every_word, x => str.starts_with(x, str.take(w, 1)) && x != w && distance(w, x, limit) <= limit)
      .sort_by((a, b) => order(a, b))
    let bucketed = list.map(near_words(state, w, false), x => x.word).sort_by((a, b) => order(a, b))
    assert bucketed == walked
  }
  # and the bucket holds both indexes: `spilt` reaches a title's word,
  # `stae` the text's
  assert list.map(near_words(state, "spilt", false), x => x.word) == ["split"]
  assert list.map(near_words(state, "stae", false), x => x.word) == ["state"]
}

## A word the index has is not a slip, whole or, when the query ends with it,
## as the start of a word; and a Chinese word is never measured.
test "only a word the index lacks has near misses" {
  let state = text_state()
  assert near_words(state, "handle", false) == []
  assert near_words(state, "handl", true) == []
  assert list.map(near_words(state, "handl", false), x => x.word) == ["handle", "handler"]
  assert near_words(state, "效课", false) == []
  assert suggest(state, "效课") == ("", 0)
}

## Only a query that nothing answers is given a suggestion. This one has a
## slip in it and still answers, through the most of its words (the
## sentence tier), so it is shown what it found and nothing else.
test "a suggestion is looked for only when neither index answers" {
  let state = text_state()
  let m = typed(state, "the block handel installs")
  assert len(m.hits) > 0
  assert m.fix == ""
  assert m.fix_hits == 0
  # the same slip on its own answers nothing, and is offered the word
  let alone = typed(state, "handel")
  assert alone.hits == []
  assert alone.fix == "handle"
  # and the titles alone know no word near it
  assert probe_state().typed("handel").fix == ""
}

## Each word the index lacks is replaced; the ones it has are kept. The
## queries so made are asked nearest first, and the first that answers is the
## one offered, which need not be the one made of each word's nearest:
## `the` is commoner than `them`, but only `them` is in a paragraph with
## `declare`.
test "every slip of a longer query is replaced, and the query offered answers" {
  let state = text_state()
  assert suggest(state, "wiht handel") == ("with handle", 1)
  assert list.map(near_words(state, "thet", false), x => x.word) == ["the", "them"]
  let (fix, n) = suggest(state, "thet declare")
  assert fix == "them declare"
  assert n == 1
  # the count is what the suggested query answers, counted the way the
  # scope pills count it
  let (one, one_n) = suggest(state, "hendl")
  let taken = typed(state, one)
  assert one_n == list.fold(taken.counts, 0, (a, c) => a + c)
  assert one_n == 3
  # a word with nothing near it sinks a two-word query, whatever the other
  # becomes
  assert suggest(state, "wiht zzzzzz") == ("", 0)
}

## The suggestion is a line in the empty state, in the page's language, with
## the count; the button and Enter both ask the suggested query through
## `Typed`, the message a recent query sends.
test "did you mean names the query and asks it on a click or on enter" {
  let state = text_state()
  let m = typed(state, "  Handel ")
  assert m.fix == "handle"
  assert m.fix_hits == 3
  let v = view(state, m)
  let line = all_with_class(v, "search-fix")
  assert len(line) == 1
  assert text_of(line[0]) == "Did you mean handle? 3 results"
  assert text_of(all_with_class(v, "search-none-title")[0]) == "Nothing matches “Handel”."
  # it sits between what was asked and the tips
  assert list.map(kids_of(all_with_class(v, "search-nothing")[0]), k => class_of(k))
    == ["search-none-art", "search-none-title", "search-fix", "search-tips"]
  let button = all_with_class(v, "search-fix-term")[0]
  assert prop_of(button, "type") == "button"
  match button {
    Elem(_, _, on, ..) -> {
      assert len(on) == 1
      assert on[0].event == "click"
      assert to_string(on[0].to_msg("")) == to_string(Typed(text: "handle"))
    }
    Text(_) -> panic("the suggestion is an element")
  }
  # Enter in the field asks it too, and the panel then has its rows
  let (kept, c) = update(state, m, Pressed(key: "Enter"))
  assert kept == m
  assert c == SendMsg(msg: Typed(text: "handle"))
  let taken = turn(state, m, Pressed(key: "Enter"))
  assert taken.query == "handle"
  assert len(taken.hits) == 3
  assert taken.fix == ""
  assert state.view(taken).count_class("search-fix") == 0
  # one result is one
  assert text_of(state.view(typed(state, "wiht handel")).all_with_class("search-fix-count")[0]) == "1 result"
  # the Chinese page says it in Chinese
  let zh = State { ..state, lang: "zh-CN" }
  assert text_of(zh.view(typed(zh, "handel")).all_with_class("search-fix")[0]) == "你是想找 handle？3 条结果"
  # Escape takes the suggestion with the query, and the model carries it
  assert turn(state, m, Pressed(key: "Escape")).fix == ""
  assert m.encode().decode() == m
  assert str.contains(encode(m), "\"fix\":\"handle\",\"fix_hits\":3")
}

fn all_with_tag(w: Node[Msg], tag: String) -> List[Node[Msg]] = {
  var out: List[Node[Msg]] = []
  match w {
    Text(_) -> ()
    Elem(t, ..) -> {
      if t == tag {
        out = out ++ [w]
      }
    }
  }
  for k in kids_of(w) {
    out = out ++ all_with_tag(k, tag)
  }
  out
}

fn json_of(s: String) -> Json =
  match parse(s) {
    Ok(j) -> j
    Err(_) -> JNull
  }