word-processor

How it is built

Architecture overview

A word processor edits a document: paragraphs of styled text mixed with tables, images, footnotes and fields, laid out on pages of a chosen size. It must do four things at once. It keeps a structured document model that every edit changes in small, reversible steps. It lays out that model into lines and pages exactly as it will print, in every script the user types, and redraws as they type. It reads and writes file formats that other programs also produce, above all Word's DOCX. And, in the cloud editors, it lets several people edit the same document at the same time and converges to one result.

The central idea is a pipeline with two representations. The model is a tree of blocks (paragraphs, tables, lists) containing text with marks (bold, link, font) and positions that refer into it. The layout is derived: runs of text are split by script, direction and font, shaped into glyphs, broken into lines, and stacked into pages. An edit changes the model; layout recomputes only the affected paragraph and the pages after it. Anything that displays (screen, PDF, print) reads the layout, not the model.

Parts:

• Document model and editing — the tree, positions, transactions, undo — rich-text-document-model (no page yet), undo-redo (no page yet), Rope, Text position encoding
• File formats and templates — import and export, images, merge fields — docx-ooxml-format (no page yet), image-codecs (no page yet), template-engines (no page yet)
• Fonts and shaping — maps characters to positioned glyphs and draws them — opentype-font-parsing (no page yet), font-fallback-itemization (no page yet), unicode-bidi-algorithm (no page yet), text-shaping (no page yet), font-rasterization (no page yet)
• Paragraph layout — breaks text into lines — unicode-line-breaking (no page yet), knuth-plass-line-breaking (no page yet), hyphenation-patterns (no page yet), block-inline-layout (no page yet)
• Pagination — flows blocks onto pages — page-layout-pagination (no page yet)
• Proofing — spelling and suggestions — spell-checking (no page yet), levenshtein-automata (no page yet), Unicode text tokenization for search
• Collaboration and history — concurrent edits, saved versions — operational-transformation (no page yet), CRDTs, binary-delta-diff (no page yet)

 keystroke / paste / import
        │
        ▼
 edit command ──► transaction (steps) ──► document model (blocks, marks)  ◄── undo / redo history
        │                                        │                 │
        │                                        │                 └──► sync: OT or CRDT ◄──► other editors
        │                                        ▼
        │                       itemize: script, direction (bidi), font fallback
        │                                        ▼
        │                       shape (glyphs + positions) ─► line breaking (+ hyphenation) ─► paragraph boxes
        │                                                                                         │
        │                                                                           pagination (floats, footnotes, keeps)
        ▼                                                                                         ▼
 proofing (spelling, suggestions)                                         screen raster / PDF / print
                                         save: DOCX package ◄── model;  open: DOCX ──► model

Two clocks run: the typing clock (a keystroke must show within one display frame, so only the touched paragraph is re-laid out) and the document clock (page numbers, tables of contents and the page count settle after, in the background).

How the parts fit together

Document model and editing

A document is a schema-constrained tree. rich-text-document-model (no page yet) defines which nodes may contain which (a list contains list items, a paragraph contains inline text and images, never a table), and represents formatting as marks on text ranges rather than as nested tags, so "bold from here to there" survives edits that split and merge runs. Positions are integers counted over the flattened document; changes are steps (replace a range with a slice) grouped into transactions, as in ProseMirror. A step has an inverse and can be mapped through other steps, which is what both undo and collaboration need.

Plain text inside a paragraph lives in a Rope: a balanced tree of small string chunks with cached lengths and newline counts, so insert, delete and seek by offset are O(log n) even in a book-length document, without moving the megabytes after the cursor.

Text positions have several coordinate systems that must agree: a byte offset in UTF-8 storage, a UTF-16 code unit index in a browser or platform text API, a character index, and a user-perceived character (grapheme cluster: a letter plus combining marks, or a flag made of two code points). Text position encoding stores one canonical offset and converts on demand, so the cursor moves over a whole grapheme and a selection never splits a surrogate pair.

undo-redo (no page yet) keeps a history of transactions. Typing a word is many steps but one undo; the history groups steps by time and by kind and coalesces adjacent insertions. Each entry stores the inverse steps, which are mapped over later changes if they must still apply (essential for collaboration, where undo must revert only your own edits and not a collaborator's text that landed in between).

File formats and templates

DOCX is the interchange format. docx-ooxml-format (no page yet): a ZIP package (Open Packaging Conventions) whose parts are XML: document.xml with paragraphs, runs and text elements, styles.xml with named styles and their inheritance, numbering, headers and footers, relationship files that link parts, and media files. It is specified as ECMA-376. A good importer maps this to the model without losing what it does not understand: unknown elements are kept in an opaque node so a round trip leaves them unchanged. Style resolution (document defaults, style chain, direct formatting) is where most fidelity bugs live; export writes the minimum direct formatting so the file stays editable by Word.

Images in the package are PNG, JPEG, and others; image-codecs (no page yet) decode them for display and re-encode on export. The editor keeps the original bytes and re-embeds them unchanged, because re-encoding a JPEG loses quality.

template-engines (no page yet) turn a document with merge fields into many documents: placeholders for names and addresses, loops over rows, conditional paragraphs. The template is compiled once into a render function, values are inserted as text nodes (never parsed as markup, which closes the injection hole), and the result goes through the same layout path as any other document.

Fonts and shaping

Before a line can be measured, text must become glyphs. opentype-font-parsing (no page yet) reads the font's tables (cmap for character to glyph, hmtx and the outline tables for advance widths and shapes, GSUB and GPOS for substitutions and positioning, variation axes for variable fonts). Fonts can arrive inside documents, so every offset is treated as untrusted.

The string is first itemized into runs that can be shaped as a unit: a single script, a single direction, a single font and size. font-fallback-itemization (no page yet) picks, per character, the first font in the style's list that covers it, falling back for symbols, emoji or CJK, and splits at script changes. unicode-bidi-algorithm (no page yet) (UAX 9) resolves the direction of every run in mixed text: Arabic or Hebrew words inside English text and the reverse, with numbers and punctuation handled by neutral rules. It produces embedding levels, and runs are reordered to visual order per line only after the line is broken; layout and cursor movement must work in logical order with a separate mapping to visual order.

text-shaping (no page yet) turns each run into positioned glyphs by applying GSUB lookups (ligatures such as fi, contextual forms in Arabic, reordering in Indic scripts) and GPOS lookups (kerning, mark attachment). The output is glyph ids, advances and offsets, plus a cluster map back to characters so selection, hit-testing and cursor placement work. HarfBuzz is the open implementation almost every editor uses. Shaped results are cached by (font, text, features), because re-shaping an unchanged paragraph on every key is the easiest way to make typing slow.

font-rasterization (no page yet) turns outlines into pixels: scan conversion with anti-aliasing, optional hinting, sub-pixel positioning so letters do not snap to whole pixels and uneven spacing does not appear at small sizes. Glyph bitmaps are cached in an atlas keyed by (font, size, glyph, sub-pixel offset).

Paragraph layout

unicode-line-breaking (no page yet) (UAX 14) says where a line may break: after spaces and hyphens, between CJK characters, never before a closing punctuation mark, with non-breaking space respected. It gives candidate break points, not breaks. hyphenation-patterns (no page yet) adds more candidates inside words: Liang's pattern method (the one in TeX) holds a few thousand patterns per language and finds the legal hyphen points of a word by looking at the pattern weights of its letter sequences, with an exception list for words the patterns get wrong.

Choosing among the candidates is the real problem. The simple method is greedy: fill each line as far as it goes. It makes bad spaces when a long word does not fit. knuth-plass-line-breaking (no page yet) treats the whole paragraph as a shortest-path problem: text is boxes (words), glue (stretchable spaces) and penalties (breaks, hyphens), each candidate line gets a badness from how far its glue is stretched or shrunk, and dynamic programming over feasible break points finds the set of breaks with the least total demerits (Knuth and Plass 1981). That is how TeX produces even spacing; word processors use it for justified text, usually with a greedy first pass for speed during typing and the optimal pass on idle.

block-inline-layout (no page yet) places the results: block elements stack vertically, text flows in line boxes whose height comes from the tallest inline item, with indents, spacing before and after, borders, tab stops, floating images that text wraps around, and table cells that run the same algorithm in a narrower width. Edits re-lay only the changed paragraph; a table cell can change the row height and everything below.

Pagination

page-layout-pagination (no page yet) takes the sequence of laid-out block boxes and cuts it into pages. A box that fits goes onto the page; one that does not is split at an allowed point. The rules interact: widow and orphan control keeps at least two lines of a paragraph at the top or bottom of a page, keep with next ties a heading to the paragraph after it, keep lines together forbids splitting, a footnote must appear on the page of its reference, a floating figure may move to the next page, and table rows can break across pages with repeated header rows. Satisfying one rule can violate another, so implementations resolve it greedily with limited backtracking.

Page breaks are global: an edit on page 3 may change every later page. The editor therefore lays out the visible pages first, then the rest in the background, and shows the final page count when it is done. Fields such as page numbers and tables of contents depend on the result and trigger a second pass; they are repeated until they stop changing (the table of contents itself can change the page count).

Proofing

spell-checking (no page yet) marks words that are not in the dictionary as the user types. Unicode text tokenization for search segments the text into words (UAX 29 word boundaries, which handle apostrophes, hyphens and numbers, and need a dictionary for languages without spaces). Each word is normalised and looked up in a dictionary of stems and affix rules (Hunspell's format expands "walk" into "walked", "walking" by rules, so a language is a few hundred thousand entries rather than millions of forms). Checks run on the changed paragraph when idle, with results cached by word.

Suggestions need a similarity search: all dictionary words within edit distance one or two of the misspelling. levenshtein-automata (no page yet) builds a small automaton that accepts exactly the strings within distance k of the given word; intersecting it with the dictionary stored as a trie or finite-state transducer walks only the branches that can still match, which is much faster than computing the edit distance against every entry. Candidates are ranked by distance and frequency.

Collaboration and history

Two writers insert at the same offset at the same time. operational-transformation (no page yet) (OT) keeps one server order of operations and transforms each incoming operation against those it did not see, so that "insert at 5" after somebody else's "insert at 2" becomes "insert at 6". Etherpad uses OT. It needs a central server to order operations, and its transform functions are subtle for rich text. CRDTs assign every character a stable identity, so inserts commute and replicas converge by merging in any order, without a central order; Yjs and Automerge implement this. Order of list items is kept with identifiers that sort between neighbours (Fractional indexing), and concurrency is tracked with Vector clocks or Lamport clocks. The price is metadata per character, which is trimmed with garbage collection. Formatting is the hard part: if one person bolds a word while another types at its end, should the new text be bold? Peritext (Ink & Switch) defines a rich-text CRDT with explicit rules for span boundaries.

Each saved version of a large file would repeat almost all its bytes. binary-delta-diff (no page yet) stores a new version as a patch against the previous one: the differences are found by matching long common substrings (a Suffix array or rolling-hash index over the old file), and the patch is a list of "copy from old" and "insert new" instructions, then compressed. Version history, autosave and upload of large files use it. It works best on the XML inside the DOCX when the package is stored uncompressed, because a ZIP's compression makes a small edit change most bytes.

Data and control flow

One keystroke:

1. The key becomes an edit command; a transaction replaces the selection with the character.
2. The model updates; the rope and positions adjust; the history groups the step.
3. The affected paragraph is re-itemized; cached shaped runs are reused where text is unchanged.
4. Lines are re-broken with the fast breaker; the new height shifts the blocks below.
5. Visible pages are repainted; glyphs come from the atlas.
6. The spell checker runs on the changed word; in a shared document, the step is sent to peers or the server.

Open and save:

1. Opening unzips the package, parses XML parts, resolves styles and builds the model; layout starts at the first page and continues in the background.
2. Saving serialises the model to XML parts, re-uses unchanged parts and media, zips them, and writes atomically (temporary file, then rename) so a crash cannot truncate the user's document.

Scaling

1. Document length: a thousand-page document with many tables. Levers: rope for text, layout cache per paragraph, lazy layout of pages outside the view, virtualised rendering.
2. Typing latency: one frame is about 16 ms at 60 Hz. Levers: re-lay only the changed paragraph, cache shaping, move spell checking and the optimal line breaking off the typing path.
3. Script and font diversity: CJK fonts are large, complex scripts shape slowly. Levers: font subsetting, lazily loaded fonts.
4. Concurrent editors: every operation is broadcast. Levers: batch operations per tick, compress presence updates, snapshot plus tail replay for late joiners, garbage collection of CRDT metadata.
5. History size: many versions of a big file. Levers: deltas against a recent base, periodic full snapshots to bound replay.

Failure modes

Real implementations

Sources

• D. Knuth and M. Plass, Breaking Paragraphs into Lines, Software: Practice and Experience 11(11), 1981.
• F. Liang, Word Hy-phen-a-tion by Com-put-er, Stanford PhD thesis, 1983. thesis
• Unicode Standard Annexes: UAX 9 bidirectional algorithm, UAX 14 line breaking, UAX 29 text segmentation
• ECMA-376, Office Open XML file formats. standard
• M. Shapiro et al., A comprehensive study of Convergent and Commutative Replicated Data Types, INRIA, 2011. report
• Ink & Switch, Peritext: a CRDT for rich-text collaboration. essay