Emacs-KP: Knuth-Plass Line Breaking for Emacs

中文文档 | Developer Guide | Repository Audit

Emacs-kp implements the Knuth-Plass optimal line breaking algorithm with full support for CJK (Chinese, Japanese, Korean) and Latin mixed text typesetting, entirely inside Emacs.

Features

• Optimal line breaking — the Knuth-Plass dynamic program finds the globally optimal set of breaks for a paragraph, not greedy first-fit.
• CJK support — every CJK character is a breakable box; kinsoku rules keep punctuation attached (，。 never start a line, 「《 never end one); dedicated inter-CJK and CJK↔Latin spacing.
• Hyphenation — Frank Liang's algorithm (the TeX algorithm) with 49 checksum-pinned Hunspell pattern dictionaries bundled.
• Pixel-accurate justification — one semantic layout plan drives both renderers. The string API uses pixel spaces; buffer layout combines space-width with absolute-pixel min-width, so it works with variable-width fonts without inserting layout characters.
• Clean editable buffers — buffer commands create no overlays and add no glue spaces, soft newlines, or discretionary hyphens to the character stream. buffer-string, char-after, search, syntax, save, and ordinary Elisp text consumers see the source characters.
• Text properties preserved — faces, colors and other properties survive justification; inserted hyphens inherit the face of the word they break.
• Robust on hard input — unprotected overlong tokens (URLs, long words at narrow widths) degrade to emergency breaks instead of losing text; every input produces output.
• Optional C module — a dynamic module runs the DP in C with a thread pool that processes paragraphs in parallel (see benchmarks).

Requirements

• Emacs 29.1+ (uses string-pixel-width and object-intervals)
• Optional, for the C module: a C11 compiler and pthreads

Installation

Clone the repository and add it to your load-path (the dictionaries/ directory must sit next to the .el files):

(add-to-list 'load-path "/path/to/emacs-kp")
(require 'ekp)
(require 'ekp-buffer)   ; buffer/region commands

Byte-compiling is strongly recommended — the Elisp engine is about 10× faster compiled.

Quick Start

(require 'ekp)

;; Justify a paragraph to 600 pixels
(insert (ekp-pixel-justify "Your paragraph text here..." 600))

;; Find the best width in a range; returns (justified-text . width)
(ekp-pixel-range-justify "Your text" 400 800)

Multiline strings are treated as one paragraph per line; blank lines are preserved.

C module (recommended for long texts)

cd ekp_c && make PROFILE=portable # default; produces ekp.dylib/.so/.dll

(ekp-c-module-load)     ; prints "ekp-c module loaded (version 1.6, N threads)"
(ekp-c-module-build)    ; prompts for portable/native/debug/sanitize

Once loaded (and since ekp-use-c-module defaults to t), all justification calls automatically use the C engine. The Elisp and C engines produce identical output; Elisp is the always-available path when no module is enabled or C returns no result. An enabled module signal is surfaced as a backend contract failure. If the module on disk is older than the Elisp code expects, loading refuses with a message asking you to rebuild.

Interactive Use (buffer & region)

ekp-buffer.el turns the string API into buffer-level commands:

(require 'ekp-buffer)

• M-x ekp-justify-region — justify the region to the window text width (with a numeric prefix argument, to that many pixels). With no active region, it justifies the paragraph at point.
• M-x ekp-justify-buffer — justify the whole buffer.
• M-x ekp-unjustify-region / ekp-unjustify-buffer — remove EKP's display projection. The source text does not need restoration because buffer layout never replaced it.
• M-x ekp-auto-justify-mode — keep completed hard paragraphs justified while ordinary typing remains stable. The active hard line has a committed projection plus one local edit transaction. Typing within the same native visual row does no whole-line planning and leaves unaffected projected rows untouched. Editing a projected middle row naturalizes only that row's dirty island, so later break anchors stay in place and native wrapping handles local word migration. When input naturally crosses into the next visual row, EKP runs or reuses one complete ekp-layout-plan and atomically publishes all completed rows; the new row remains natural. Deleting and reinserting the same source restores the saved projection exactly, including text properties. Point motion never plans or writes layout properties, even when point leaves the paragraph. Global commits happen only at a visual-row crossing, hard newline/paragraph completion, the next real edit elsewhere, explicit refill, or a width/font/layout-context change. There is no edit-idle whole-paragraph snap. Window resize re-flow is debounced by ekp-auto-justify-resize-delay. The mode temporarily disables both explicit line truncation and Emacs's narrow partial-window truncation, so a side-by-side editing window still soft-wraps normally. Disabling the mode restores the prior buffer-local or global ownership of both settings. A leading or trailing space/tab on the active line is visible in the same input turn; deleting a following glyph does not hide that source whitespace. Reprojection also preserves an inactive mark as inactive, so width changes do not create an accidental selection. While active, the standard EKP menu exposes formatting, protection, and window-fit diagnostic commands; C-h m describes the same workflow.

The projection uses text properties on existing source graphemes only:

• Existing ASCII spaces receive ((space-width FACTOR) (min-width ((TARGET-PIXELS)))).
• A CJK or mixed gap with no source space adds min-width to the preceding complete grapheme; the target is its natural advance plus the glue.
• line-prefix supplies indentation. A break or discretionary hyphen is a replacing display string on an existing complete grapheme.
• EKP never creates an overlay. It also never steals a foreign replacing display, line-prefix, wrap-prefix, composition, or invisible owner; that hard paragraph stays natural and M-x ekp-diagnose reports the conflict.

Consequently:

• Elisp APIs and saving see the original character sequence. Visual spaces, newlines, and hyphens cannot reach disk or syntax/search logic. buffer-substring can still carry the EKP display properties because it preserves text properties; buffer-substring-no-properties is the plain source string.
• Searching (including isearch) operates directly on source text, so a word remains one word across a visual discretionary break.
• Copying and killing strip EKP-owned projection properties while composing with any existing substring filter. Pasted text contains only the logical content and its non-EKP properties.
• Projection updates run inside with-silent-modifications: enabling, editing, resizing, and disabling layout do not create layout-only undo entries, modified-state changes, or character-modified ticks.

ekp-buffer-margin-pixel (default 2) is subtracted from the window width as a rounding safety margin.

Large buffers (over ekp-auto-justify-lazy-threshold characters, default 20 000) re-flow visible-first: the portion on screen updates synchronously and the rest follows in idle background chunks, with a per-tick time budget (ekp-auto-justify-tick-budget) and priority for whatever you scroll to.

Automatic planning is also bounded per hard paragraph. ekp-auto-justify-paragraph-limit defaults to 2 048 characters. A longer single paragraph stays naturally wrapped and fully editable instead of blocking input in an unbounded Knuth-Plass pass; M-x ekp-diagnose reports the reason. Run M-x ekp-refill-paragraph when you explicitly want the unbounded full-quality pass for that paragraph.

Mode presets for explicit local protection — one call each:

(add-hook 'org-mode-hook      #'ekp-org-setup)
(add-hook 'markdown-mode-hook #'ekp-markdown-setup)

ekp-auto-justify-mode consults ekp-buffer-mode-policy-alist automatically in Org and Markdown buffers. It does not copy profile values into buffer-local variables unless you explicitly call the setup functions above.

Protecting code and other verbatim text

• Block level: paragraphs carrying the ekp-verbatim text property (M-x ekp-verbatim-region), wearing a face listed in ekp-buffer-skip-faces (e.g. org-block, markdown-code-face), or matched by the buffer-local function ekp-buffer-skip-predicate pass through completely untouched.
• Automatic inline level: faces listed in ekp-buffer-inline-faces (Org org-code/org-verbatim, Markdown inline code by default through mode profiles) use ekp-inline-code-policy. The default no-hyphen keeps source spaces literal and suppresses dictionary hyphenation, but it may still wrap at legal source boundaries. Automatic no-break spans downgrade to no-hyphen when wider than the effective measure.
• Explicit hard atom level: spans carrying ekp-no-break (M-x ekp-no-break-region) become rigid atoms — never broken, never hyphenated, spacing kept literal — ideal for inline code, product names, or numbers with units. An atom wider than the measure stays intact but is not guaranteed a line of its own: the final pass may place it on one overflow line with preceding ordinary content. Ordinary underfull candidates use fixed emergency stretch and normal K-P costs. If an overfull candidate would otherwise extinguish every active final-pass path, the core preserves the last path with TeX-style artificial demerits. There is no CJK-orphan, unit, or screenshot-specific rule.

Manual properties are deliberately current-buffer-session only: plain-text saving and reopening do not persist them. Use M-x ekp-allow-break-region / ekp-clear-verbatim-region to remove them. For protection derived from persistent document syntax, use mode faces or the buffer-local ekp-buffer-skip-predicate (the Org/Markdown presets do this automatically).

Typography

• Alignment — ekp-alignment: justify (default), ragged-right, ragged-left, or center. Non-justify modes keep word spacing natural while Knuth-Plass still minimizes raggedness within ekp-ragged-stretch-pixel (≈2 em) per line.
• Hanging punctuation — set ekp-protrusion to t and line-final punctuation (。、」 as well as periods, commas and break hyphens) hangs past the flush edge by ekp-protrusion-ratios. The 0.5 default for fullwidth closers is visually equivalent to CLREQ line-end punctuation compression. ekp-auto-justify-mode reserves the protrusion width automatically.
• Paragraph shapes — ekp-first-line-indent (t = 2 em) for the CJK paragraph convention, or full TeX-style ekp-parshape with per-line (INDENT . WIDTH). First-line indent runs on the fast 1D path and the C engine; only full ekp-parshape and ekp-looseness fall back to the Elisp-only 2D dynamic program.
• Unbreakables — NO-BREAK SPACE, NARROW NBSP, FIGURE SPACE and WORD JOINER characters keep their neighbors together out of the box.
• Kinsoku covers full- and halfwidth punctuation: a line never starts with 。、」!? or a lone .,;:!?, never ends with 「( etc. Japanese line-start prohibition also covers small kana, the prolonged sound mark and iteration marks (っ ょ ー 々), configurable via ekp-cjk-no-line-start-extra.

Limitations worth knowing: mid-line CLREQ punctuation compression (e.g. 「字。下」 squeezed inside a line) cannot be rendered — Emacs cannot shrink a glyph's advance — which is why line-edge compression is delivered via protrusion instead; left-edge protrusion is likewise not renderable (text cannot start before the line origin).

Configuration

Break policy and measure

The break-policy defaults are intended to make code readable without making every code-looking span a hard atom:

Option	Default	Scope	Effect
ekp-inline-code-policy	no-hyphen	global, profile, local	normal, no-hyphen, or automatic fitting no-break for inline-face spans
ekp-hyphenation	auto	global, profile, local, region via command	auto/on use dictionaries when available; off suppresses discretionary hyphens
ekp-token-break-policies	URL/path/identifier no-hyphen, number-unit no-break	global, profile, local	per-token automatic policies; local/profile values merge by token category
ekp-number-unit-suffixes	common CSS, time, data, frequency, and metric units	global, profile, local	suffixes recognized by the compact number-unit classifier
ekp-kinsoku-profile	common	global, profile, local	common, zh, ja, off, or custom CJK line-start/end prohibitions
ekp-cjk-no-line-start-extra / ekp-cjk-no-line-end-extra	""	global, profile, local	additions used by the custom profile
ekp-overlong-token-policy	emergency	global, profile, local	emergency, overflow, or natural for ordinary overlong Latin-like tokens
ekp-buffer-measure	narrowest-window	global, profile, local	narrowest-window, fixed pixel integer, or (max . PIXELS)
ekp-buffer-skip-faces	profile-dependent	global, profile, local	paragraph-level verbatim faces
ekp-buffer-inline-faces	profile-dependent	global, profile, local	exact inline spans using ekp-inline-code-policy
ekp-buffer-mode-policy-alist	Org and Markdown profiles	global/local safe value	mode profiles consulted by automatic and manual buffer layout

Effective precedence is deterministic: explicit region text properties first, then explicit buffer/file/dir-local values, then the first matching major-mode profile, then global defaults. ekp-break-policy region values are normal, hyphenate, and no-hyphen; they override automatic token or inline policies for the exact region but never create a hard atom. ekp-no-break remains the only explicit hard-atom property and wins over every automatic policy.

All listed variables have closed safe-local predicates where file/dir local configuration is supported. ekp-diagnose reports the requested measure, the narrowest live window, the effective measure, overflow risk, conflict count, and the active inline/hyphenation/kinsoku/overlong policy summary. The EKP menu exposes diagnose plus region commands for normal break, hyphenation on, hyphenation off, clear break policy, no-break, and verbatim.

Hyphenation language

(setq ekp-latin-lang "de_DE")   ; default "en_US"

Short codes like "de" resolve to the first matching dictionary. Each supported dictionary's own LEFTHYPHENMIN / RIGHTHYPHENMIN are honored (English keeps ≥2 letters before and ≥3 after a break); pass explicit margins to ekp-hyphen-create to override.

EKP supports ordinary Liang patterns. It fails closed with ekp-hyphen-unsupported-pattern for eo, ca, hu_HU, and sq_AL because those files contain slash/replacement rules that conditionally rewrite glyphs at a chosen break. Treating them as ordinary positions would produce linguistically wrong text and incorrect DP widths. The exact inventory, SHA-256 checksums, pinned source paths, and license evidence live in dictionaries/MANIFEST.tsv and dictionaries/LICENSES.md.

Spacing parameters

Three glue classes control spacing (all values in pixels):

Group	Between
lws-*	two Latin words
mws-*	a Latin word and a CJK char
cws-*	two CJK characters

Each class has an ideal width, a maximum stretch and a maximum shrink:

(ekp-param-set lws-ideal lws-stretch lws-shrink
               mws-ideal mws-stretch mws-shrink
               cws-ideal cws-stretch cws-shrink)
;; e.g. (ekp-param-set 7 3 2  5 2 1  0 2 0)

• If you never call ekp-param-set, defaults are derived automatically from the font of each string.
• Explicit parameters persist until you call ekp-param-reset, which returns to automatic per-string defaults.

Algorithm parameters

Variable	Default	Meaning
ekp-line-penalty	10	Base cost per line; higher prefers fewer lines
ekp-hyphen-penalty	50	Cost of a hyphenated break (added as penalty²)
ekp-adjacent-fitness-penalty	100	Cost when adjacent lines differ in tightness by >1 class
ekp-consecutive-hyphen-penalty	100	Multiplier for runs of hyphenated lines (× count²)
ekp-last-line-min-ratio	0.5	Minimum fill ratio for the last line
ekp-last-line-short-penalty	50	Cost multiplier for a too-short last line
ekp-looseness	0	Target line count offset: +1 = one line more than optimal, −1 = one fewer

Both engines implement these parameters: before an actual C computation, the Elisp side synchronizes their current values. The DP cache signature includes every parameter in the table, so changes take effect on the next call without manually clearing caches. ekp-looseness is part of the cache key and uses a dedicated Elisp path (the C module is bypassed automatically while it is non-zero).

Caching

Tokenization, measurement, and DP results are cached per paragraph; box widths are additionally cached session-wide, so a glyph shared across paragraphs is measured only once. Both explicit spacing values and the automatic ekp-default-cws-stretch-pixel input participate in paragraph cache identity. The same complete structural key also governs the same-string fast path, so adding or removing layout properties such as ekp-no-break takes effect immediately on an already cached string object.

• ekp-para-cache-limit (default 256): max cached paragraphs; the cache is flushed when the limit is reached.
• M-x ekp-clear-caches clears everything (use after changing fonts or themes that affect glyph widths).

Performance

Measured on the bundled sample texts (tests/ekp-bench.el), batch Emacs 30.2, Apple Silicon; see DEVELOPER.md for methodology:

Case (text-zh.txt ≈ 3.6 KB)	Elisp (byte-compiled)	C module
justify, width 200px	150 ms	41 ms
optimal-width search 340–380	529 ms	106 ms
DP only, width 400px	30 ms	2.5 ms

Byte-compile the package — the Elisp engine is ~10× faster compiled. Both engines produce identical output; the C module pays off most for optimal-width search and long multi-paragraph texts. (Absolute numbers vary with machine and power state; the ratios are the point.)

Known Limitations

• Text properties are buffer-wide, so one buffer cannot carry independent plans for windows of different widths. EKP uses the narrowest live window as the authoritative width; wider windows can show unused space but never overflow.
• EKP-owned layout properties are visible to APIs that explicitly inspect text properties. The character stream is clean; copy/kill removes the owned projection metadata.
• Tabs and non-ASCII whitespace cannot be shrunk with space-width. If an exact plan would require that operation, EKP leaves the affected hard paragraph natural and reports the conflict.
• Measurement follows the current buffer's face remappings (text-scale-mode, themes, ekp-org-setup-style tweaks) and reserves the truncation-indicator column in windows without fringes, so justified lines fit the real display. If lines ever look truncated or short in an exotic setup, run M-x ekp-diagnose in that buffer — it reports whether measurement matches rendering. The full fit matrix is a developer tool in tests/ekp-gui-verify.el; load that file before invoking M-x ekp-gui-verify.
• One font is assumed per Latin/CJK script per paragraph when computing spacing defaults; mixed-font paragraphs work but spacing defaults come from the first font found.
• ekp-pixel-range-justify minimizes average demerits with a ternary search plus a local scan; cost is not perfectly unimodal in width, so the result is a very good, but not guaranteed global, optimum.
• In batch/tty Emacs, pixel widths degrade to character columns (the full pipeline still works; useful for testing).

Interactive Demo

emacs -Q -L /path/to/emacs-kp -l tests/ekp-showcase.el -f ekp-showcase

One buffer, live keys: -/+ change the pixel width (per-reflow time in the header line), d runs an animated width sweep with an fps report, a cycles alignment, p toggles hanging punctuation, i first-line indent, s a wedge parshape, c compares the C engine with pure Elisp, w follows the window width via ekp-auto-justify-mode. The sample text includes a protected code block, an inline no-break atom and NBSP-joined numbers.

Testing

tests/run-tests.sh /path/to/emacs     # batch-safe ERT suite

# Full interactive GUI fit matrix
emacs -Q -L /path/to/emacs-kp -L /path/to/emacs-kp/tests \
  -l /path/to/emacs-kp/tests/ekp-gui-verify.el \
  -f ekp-gui-verify-matrix

The matrix prints every row and exits with status 1 if any fit check fails, so the same command can gate local release automation. The verifier is a developer tool under tests/; it is not loaded by (require 'ekp-buffer).

Credits

• Core algorithm: "Breaking Paragraphs into Lines" by Donald E. Knuth and Michael F. Plass (1981)
• Hyphenation: Frank Liang's algorithm, adapted from Pyphen
• Dictionaries: hyphenation patterns from the LibreOffice dictionaries; see dictionaries/MANIFEST.tsv, dictionaries/LICENSES.md, and the bundled per-dictionary notices for exact source, checksum, and license evidence.