// Canonical Quoted Text 3.17 -- Java port of the reference implementation in cqt.py.
//
// Run the conformance vectors with the single-file source launcher (no build tool,
// no javac, no dependencies):
//
// java Cqt.java [path/to/../../goldens/cqt3.17.json]
//
// Unicode: the spec requires Unicode 17.0.0 for every Character Database lookup.
// The JDK bundles its own version (Java 25 = Unicode 16.0.0), so the NFKC
// differences between 16 and 17 are corrected explicitly. See UNICODE_DELTA_FROM
// and CCC_DELTA below.
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Cqt {
public static final String UNICODE_VERSION = "17.0.0";
// ---------------------------------------------------------------- Unicode delta
// The JDK's java.text.Normalizer uses the Unicode version bundled with the
// runtime, which for Java 25 is 16.0.0 (measured: every Unicode 16 addition is
// assigned, no Unicode 17 addition is). Sweeps over all 1,114,112 code points
// found exactly two kinds of difference between Unicode 16 and Unicode 17 that
// CQT can observe, and no General_Category difference at all in the classes CQT
// reads (Cc, Ps, Pi, Pe, Pf).
//
// First: one decomposition mapping.
//
// U+A7F1 MODIFIER LETTER CAPITAL S -> "S" (assigned in Unicode 17)
//
// U+A7F1 has ccc=0 and its compatibility decomposition is the single scalar "S",
// which also has ccc=0, so substituting before normalization is exactly
// equivalent to a Unicode 17 NFKC: NFKD would have performed the same
// replacement in the same position, and the canonical composition that follows
// then sees identical input.
private static final String UNICODE_DELTA_FROM = "๊ฑ";
private static final String UNICODE_DELTA_TO = "S";
// Second: five combining marks whose Canonical_Combining_Class changed from 0
// (a starter) to a non-zero value. Under Unicode 16 a JDK normalizer treats them
// as starters, so they act as barriers to canonical ordering and to composition;
// under Unicode 17 they are marks that sort by class and let a following mark
// compose with the base before them. "a" + U+1ADD + U+0301 is "a U+1ADD U+0301"
// under 16 and "รก U+1ADD" under 17.
//
// None of the five has a decomposition and none is the second element of a
// primary composite, so their only effect on NFKC is through their class. That
// makes them interchangeable, for normalization purposes, with any other mark of
// the same class that also never composes -- which is what the correction below
// exploits: swap each one for such a proxy, let the JDK's own Unicode 16 tables
// do the ordering and composition, and swap back.
//
// {affected code point, the proxy that carries its Unicode 17 class}
private static final int[][] CCC_DELTA = {
{0x1ADD, 0x101FD}, // COMBINING DOT-AND-RING BELOW, ccc 0 -> 220
{0x1AE6, 0x101FD}, // COMBINING DOUBLE ARCH BELOW, ccc 0 -> 220
{0x10EFA, 0x101FD}, // ARABIC DOUBLE VERTICAL BAR BELOW, ccc 0 -> 220
{0x10EFB, 0x101FD}, // ARABIC SMALL LOW NOON, ccc 0 -> 220
{0x1AEB, 0x1DCD}, // COMBINING DOUBLE RIGHTWARDS ARROW ABOVE, ccc 0 -> 234
};
// The two proxies. U+101FD PHAISTOS DISC SIGN COMBINING OBLIQUE STROKE has ccc
// 220 and U+1DCD COMBINING DOUBLE CIRCUMFLEX ABOVE has ccc 234, in Unicode 16 and
// 17 alike. Neither has a decomposition, neither is the second element of a
// primary composite, and neither appears in the compatibility decomposition of
// any other scalar -- so normalization can neither manufacture one nor consume
// one. Several occurrences of a proxy therefore come out of the normalizer in the
// same relative order they went in: canonical ordering is a stable sort on class,
// marks never cross a starter, and composition removes only marks that compose.
// That is what lets one proxy stand in for four different characters at once, and
// stand in for itself where the text already contained it -- restoration walks the
// occurrences in order and puts each one back as what it was.
private static final int CCC_PROXY_220 = 0x101FD;
private static final int CCC_PROXY_234 = 0x1DCD;
// ---------------------------------------------------------------- character sets
private static boolean isWhiteSpace(int cp) {
return (cp >= 0x0009 && cp <= 0x000D)
|| cp == 0x0020 || cp == 0x0085 || cp == 0x00A0 || cp == 0x1680
|| (cp >= 0x2000 && cp <= 0x200A)
|| cp == 0x2028 || cp == 0x2029 || cp == 0x202F || cp == 0x205F
|| cp == 0x3000;
}
private static boolean isDashPunctuation(int cp) {
switch (cp) {
case 0x002D: case 0x058A: case 0x05BE: case 0x1400: case 0x1806:
case 0x2010: case 0x2011: case 0x2012: case 0x2013: case 0x2014:
case 0x2015: case 0x2E17: case 0x2E1A: case 0x2E3A: case 0x2E3B:
case 0x2E40: case 0x2E5D: case 0x301C: case 0x3030: case 0x30A0:
case 0xFE31: case 0xFE32: case 0xFE58: case 0xFE63: case 0xFF0D:
case 0x10D6E: case 0x10EAD:
return true;
default:
return false;
}
}
private static boolean isQuoteCharacter(int cp) {
switch (cp) {
case 0x0022: case 0x2018: case 0x2019: case 0x201C: case 0x201D:
case 0x00AB: case 0x00BB: case 0x2039: case 0x203A:
case 0x3008: case 0x3009: case 0x300A: case 0x300B:
case 0x300C: case 0x300D:
return true;
default:
return false;
}
}
/** U+FEFF is a serialization artifact, removed by step 2.4 before recognition,
* which is why it also comes out of a protected span. */
private static boolean isRemovedArtifact(int cp) {
return cp == 0xFEFF;
}
/** Step 2.5 folds all of these onto LF. */
private static boolean isLineTerminator(int cp) {
return (cp >= 0x0A && cp <= 0x0D) || cp == 0x85 || cp == 0x2028 || cp == 0x2029;
}
private static boolean isHorizontalWhiteSpace(int cp) {
return isWhiteSpace(cp) && cp != '\n';
}
/** An RFC 2045 token character: printable ASCII other than space, controls and
* the tspecials ()<>@,;:\\"/[]?= */
private static boolean isTokenChar(int cp) {
if (cp <= ' ' || cp >= 0x7F) {
return false;
}
return "()<>@,;:\\\"/[]?=".indexOf(cp) < 0;
}
private static boolean isRemovedInvisible(int cp) {
return cp == 0x00AD || cp == 0x200B || cp == 0x2060 || cp == 0xFEFF;
}
// Unicode 17.0.0 Terminal_Punctuation, from PropList.txt. Punctuation that ends
// a sentence, clause or word, and so attaches to the text on its LEFT. The ASCII
// members are exactly ! , . : ; ? -- deliberately NOT the whole Po category,
// which would drag in the solidus and turn "A & B / C" into "A & B/ C", nor the
// apostrophe, which the quote fold has already made ambiguous.
private static final String[] TERMINAL_PUNCTUATION_RANGES = {
"0021", "002C", "002E", "003A-003B", "003F", "037E", "0387", "0589", "05C3",
"060C", "061B", "061D-061F", "06D4", "0700-070A", "070C", "07F8-07F9",
"0830-0835", "0837-083E", "085E", "0964-0965", "0E5A-0E5B", "0F08",
"0F0D-0F12", "104A-104B", "1361-1368", "166E", "16EB-16ED", "1735-1736",
"17D4-17D6", "17DA", "1802-1805", "1808-1809", "1944-1945", "1AA8-1AAB",
"1B4E-1B4F", "1B5A-1B5B", "1B5D-1B5F", "1B7D-1B7F", "1C3B-1C3F", "1C7E-1C7F",
"2024", "203C-203D", "2047-2049", "2CF9-2CFB", "2E2E", "2E3C", "2E41", "2E4C",
"2E4E-2E4F", "2E53-2E54", "3001-3002", "A4FE-A4FF", "A60D-A60F", "A6F3-A6F7",
"A876-A877", "A8CE-A8CF", "A92F", "A9C7-A9C9", "AA5D-AA5F", "AADF",
"AAF0-AAF1", "ABEB", "FE12", "FE15-FE16", "FE50-FE52", "FE54-FE57", "FF01",
"FF0C", "FF0E", "FF1A-FF1B", "FF1F", "FF61", "FF64", "1039F", "103D0", "10857",
"1091F", "10A56-10A57", "10AF0-10AF5", "10B3A-10B3F", "10B99-10B9C",
"10F55-10F59", "10F86-10F89", "11047-1104D", "110BE-110C1", "11141-11143",
"111C5-111C6", "111CD", "111DE-111DF", "11238-1123C", "112A9", "113D4-113D5",
"1144B-1144D", "1145A-1145B", "115C2-115C5", "115C9-115D7", "11641-11642",
"1173C-1173E", "11944", "11946", "11A42-11A43", "11A9B-11A9C", "11AA1-11AA2",
"11C41-11C43", "11C71", "11EF7-11EF8", "11F43-11F44", "12470-12474",
"16A6E-16A6F", "16AF5", "16B37-16B39", "16B44", "16D6E-16D6F", "16E97-16E98",
"1BC9F", "1DA87-1DA8A",
};
// Unicode 17.0.0 Line_Break=SA, from LineBreak.txt: the scripts that do not
// separate words with spaces and therefore need explicit break opportunities --
// Thai, Lao, Khmer, Myanmar, Tai Tham, New Tai Lue, Ahom. In these scripts
// U+200B is a real word separator rather than a layout artifact.
private static final String[] SPACELESS_SCRIPT_RANGES = {
"0E01-0E3A", "0E40-0E4E", "0E81-0E82", "0E84", "0E86-0E8A", "0E8C-0EA3",
"0EA5", "0EA7-0EBD", "0EC0-0EC4", "0EC6", "0EC8-0ECE", "0EDC-0EDF",
"1000-103F", "1050-108F", "109A-109F", "1780-17D3", "17D7", "17DC-17DD",
"1950-196D", "1970-1974", "1980-19AB", "19B0-19C9", "19DE-19DF", "1A20-1A5E",
"1A60-1A7C", "1AA0-1AAD", "A9E0-A9EF", "A9FA-A9FE", "AA60-AAC2", "AADB-AADF",
"11700-1171A", "1171D-1172B", "1173A-1173B", "1173F-11746",
};
private static final int[][] TERMINAL_PUNCTUATION = parseRanges(TERMINAL_PUNCTUATION_RANGES);
private static final int[][] SPACELESS_SCRIPTS = parseRanges(SPACELESS_SCRIPT_RANGES);
private static int[][] parseRanges(String[] items) {
int[][] out = new int[items.length][2];
for (int i = 0; i < items.length; i++) {
int dash = items[i].indexOf('-');
if (dash < 0) {
out[i][0] = Integer.parseInt(items[i], 16);
out[i][1] = out[i][0];
} else {
out[i][0] = Integer.parseInt(items[i].substring(0, dash), 16);
out[i][1] = Integer.parseInt(items[i].substring(dash + 1), 16);
}
}
java.util.Arrays.sort(out, (a, b) -> Integer.compare(a[0], b[0]));
return out;
}
private static boolean inRanges(int[][] ranges, int cp) {
int lo = 0;
int hi = ranges.length - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (cp < ranges[mid][0]) {
hi = mid - 1;
} else if (cp > ranges[mid][1]) {
lo = mid + 1;
} else {
return true;
}
}
return false;
}
private static boolean isTerminalPunctuation(int cp) {
return inRanges(TERMINAL_PUNCTUATION, cp);
}
private static boolean isSpacelessScript(int cp) {
return inRanges(SPACELESS_SCRIPTS, cp);
}
private static boolean isPeOrPf(int cp) {
int type = Character.getType(cp);
return type == Character.END_PUNCTUATION || type == Character.FINAL_QUOTE_PUNCTUATION;
}
private static boolean isPsOrPi(int cp) {
int type = Character.getType(cp);
return type == Character.START_PUNCTUATION || type == Character.INITIAL_QUOTE_PUNCTUATION;
}
// ---------------------------------------------------------------- autocorrect
// Spelled numerically because the characters themselves are invisible in source.
/** U+FE0F VARIATION SELECTOR-16, which asks for the emoji rendering. */
private static final String VARIATION_SELECTOR_16 = Character.toString(0xFE0F);
/** U+FE0E VARIATION SELECTOR-15, which asks for the text rendering. */
private static final String VARIATION_SELECTOR_15 = Character.toString(0xFE0E);
private static final String[][] AUTOCORRECT_BASE = {
{"๐", ":-)"}, // U+1F60A
{"๐", ":-|"}, // U+1F610
{"โน", ":-("}, // U+2639
{"๐", ":-D"}, // U+1F603
{"๐", ":-p"}, // U+1F61D
{"๐ฒ", ":-o"}, // U+1F632
{"๐", ";-)"}, // U+1F609
{"โค", "<3"}, // U+2764
{"๐", " protectedSpans = new LinkedHashMap<>();
String text = protect(stripped, protectedSpans);
text = canonicalizeProse(text);
text = restore(text, protectedSpans);
return text.getBytes(StandardCharsets.UTF_8);
}
/** Convenience wrapper returning the canonical text rather than its bytes. */
public static String canonicalize(String plaintext) {
return new String(algorithm317(plaintext), StandardCharsets.UTF_8);
}
// ---------------------------------------------------------------- step 2
/**
* Remove what cannot belong to plain text.
*
*
Three groups, all artifacts rather than writing. Control characters outside
* the White_Space set -- NUL and its neighbours -- are not plain text. Unpaired
* surrogates are not Unicode scalar values at all and have no UTF-8 encoding; a
* well-formed pair is one character and is left alone. And the two directional
* overrides, LRO (U+202D) and RLO (U+202E), force every character in their scope
* to render in a chosen direction regardless of what the character is, which is
* an instruction to a rendering engine rather than a statement about the text.
*
*
The other bidi controls stay. Marks (ALM, LRM, RLM) only affect how
* neighbouring neutral characters resolve, and isolates (LRI, RLI, FSI, PDI)
* scope a direction without overriding anything.
*/
private static String stripDisallowed(String text) {
StringBuilder out = new StringBuilder(text.length());
int i = 0;
int n = text.length();
while (i < n) {
char c = text.charAt(i);
if (c >= 0xD800 && c <= 0xDBFF) {
if (i + 1 < n) {
char low = text.charAt(i + 1);
if (low >= 0xDC00 && low <= 0xDFFF) {
// A well-formed pair is one astral character, not two errors.
out.append(c).append(low);
i += 2;
continue;
}
}
i++;
continue;
}
if (c >= 0xDC00 && c <= 0xDFFF) {
i++;
continue;
}
if (Character.getType(c) == Character.CONTROL && !isWhiteSpace(c)) {
i++;
continue;
}
if (c == 0x202D || c == 0x202E) {
// The only two scalars whose Bidi_Class is LRO or RLO.
i++;
continue;
}
out.append(c);
i++;
}
return out.toString();
}
// ---------------------------------------------------------------- step 3: spans
private enum SpanKind { FENCE, INLINE, URL }
private static final class Span {
final int start;
final int end;
final SpanKind kind;
Span(int start, int end, SpanKind kind) {
this.start = start;
this.end = end;
this.kind = kind;
}
}
private static String lineBody(String line) {
return line.endsWith("\n") ? line.substring(0, line.length() - 1) : line;
}
/** Split on LF, which step 2.5 has made the only line terminator. */
private static List linesWithEndings(String text) {
List lines = new ArrayList<>();
int start = 0;
int i = 0;
int n = text.length();
while (i < n) {
char c = text.charAt(i);
if (c == '\n') {
i += 1;
lines.add(text.substring(start, i));
start = i;
} else {
i++;
}
}
if (start < n) {
lines.add(text.substring(start));
}
return lines;
}
private static List fencedSpans(String text) {
List lines = linesWithEndings(text);
List spans = new ArrayList<>();
int[] offsets = new int[lines.size()];
int offset = 0;
for (int k = 0; k < lines.size(); k++) {
offsets[k] = offset;
offset += lines.get(k).length();
}
int i = 0;
while (i < lines.size()) {
Matcher opening = FENCE_OPEN.matcher(lineBody(lines.get(i)));
if (!opening.matches()) {
i++;
continue;
}
int fenceLength = opening.group(1).length();
Pattern closing = Pattern.compile("^" + HWS + "*`{" + fenceLength + ",}" + HWS + "*$");
int j = i + 1;
while (j < lines.size() && !closing.matcher(lineBody(lines.get(j))).matches()) {
j++;
}
int start = offsets[i];
if (start > 0 && text.charAt(start - 1) == '\n') {
start -= 1;
}
if (!spans.isEmpty()) {
start = Math.max(start, spans.get(spans.size() - 1).end);
}
if (j == lines.size()) {
// An opener with no closer runs to the end of the input rather than
// decaying into prose. Truncation is ordinary, and under the old rule
// losing one line reinterpreted a whole block.
spans.add(new Span(start, text.length(), SpanKind.FENCE));
break;
}
int end = offsets[j] + lines.get(j).length();
spans.add(new Span(start, end, SpanKind.FENCE));
i = j + 1;
}
return spans;
}
private static int indexOfWithin(String text, String needle, int from, int limit) {
int last = limit - needle.length();
for (int i = Math.max(from, 0); i <= last; i++) {
if (text.startsWith(needle, i)) {
return i;
}
}
return -1;
}
private static int matchingBacktickRun(String text, int start, int limit, int length) {
String needle = "`".repeat(length);
int candidate = indexOfWithin(text, needle, start, limit);
while (candidate != -1) {
boolean beforeIsTick = candidate > start && text.charAt(candidate - 1) == '`';
int after = candidate + length;
boolean afterIsTick = after < limit && text.charAt(after) == '`';
if (!beforeIsTick && !afterIsTick) {
return candidate;
}
candidate = indexOfWithin(text, needle, candidate + length, limit);
}
return -1;
}
private static int urlEnd(String text, int start, int limit) {
int i = start;
int parenDepth = 0;
while (i < limit) {
char c = text.charAt(i);
// The Cc test is unreachable defence in depth: stripDisallowed has already
// removed every Cc scalar that is not White_Space, and the White_Space ones
// terminate on the first test. Kept so a reordering of the passes cannot
// silently swallow a control character into a URL.
if (isWhiteSpace(c) || c == '<' || c == '>' || c == '"' || c == '`'
|| Character.getType(c) == Character.CONTROL) {
break;
}
if (c == '(') {
parenDepth++;
} else if (c == ')') {
if (parenDepth == 0) {
break;
}
parenDepth--;
}
i++;
}
return i;
}
/**
* Match {@code https?://} at {@code i}, ASCII-case-insensitively, and return the
* offset just past the scheme, or -1.
*
*
The ASCII restriction is load-bearing. A Unicode case fold makes U+017F
* LATIN SMALL LETTER LONG S match the "s" of "https", so "http{U+017F}://..."
* would be protected as a URL. RFC 3986 section 3.1 restricts a scheme to ASCII
* ALPHA, so that match is simply wrong. In Java, Pattern.CASE_INSENSITIVE without
* Pattern.UNICODE_CASE is already ASCII-only; this hand-rolled comparison makes
* the property explicit and independent of flag choices.
*/
private static int runOfTokens(String text, int at, int limit) {
int i = at;
while (i < limit && isTokenChar(text.charAt(i))) {
i++;
}
return i > at ? i : -1;
}
/** An RFC 2397 header: an optional type/subtype, zero or more ";attribute=value"
* parameters, an optional ";base64", and the mandatory comma. Returns the offset
* just past the comma. */
private static int dataHeader(String text, int at, int limit) {
int i = at;
int j = runOfTokens(text, i, limit);
if (j > 0 && j < limit && text.charAt(j) == '/') {
int k = runOfTokens(text, j + 1, limit);
if (k > 0) {
i = k;
}
}
while (i < limit && text.charAt(i) == ';') {
if (asciiEqualsIgnoreCase(text, i, limit, ";base64")
&& i + 7 < limit && text.charAt(i + 7) == ',') {
return i + 8;
}
int name = runOfTokens(text, i + 1, limit);
if (name < 0 || name >= limit || text.charAt(name) != '=') {
return -1;
}
int value = runOfTokens(text, name + 1, limit);
if (value < 0) {
return -1;
}
i = value;
}
return (i < limit && text.charAt(i) == ',') ? i + 1 : -1;
}
/** The three forms of URI span, returning the offset just past the recognized
* prefix. Any scheme followed by "://" is safe because "://" does not occur in
* prose; a bare scheme is not, because "note:" and "here is the data:" are
* ordinary English. The two bare schemes admitted here carry structure a
* sentence does not: mailto: must reach an "@" before any whitespace, and data:
* must present a well-formed RFC 2397 header.
*
* Comparison is ASCII-only. A Unicode case fold would make U+017F LATIN SMALL
* LETTER LONG S match the "s" of "https", and RFC 3986 section 3.1 allows only
* ASCII letters in a scheme, so that match is simply wrong. */
private static int matchUrlScheme(String text, int i, int limit) {
char first = text.charAt(i);
if (!((first >= 'A' && first <= 'Z') || (first >= 'a' && first <= 'z'))) {
return -1;
}
int j = i + 1;
while (j < limit) {
char c = text.charAt(j);
boolean ok = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')
|| (c >= '0' && c <= '9') || c == '+' || c == '-' || c == '.';
if (!ok) {
break;
}
j++;
}
if (asciiEqualsIgnoreCase(text, j, limit, "://")) {
return j + 3;
}
if (asciiEqualsIgnoreCase(text, i, limit, "mailto:")) {
for (int n = i + 7; n < limit && !isWhiteSpace(text.charAt(n)); n++) {
if (text.charAt(n) == '@') {
return i + 7;
}
}
return -1;
}
if (asciiEqualsIgnoreCase(text, i, limit, "data:")) {
return dataHeader(text, i + 5, limit);
}
return -1;
}
private static boolean asciiEqualsIgnoreCase(String text, int at, int limit, String lowerNeedle) {
if (at + lowerNeedle.length() > limit) {
return false;
}
for (int k = 0; k < lowerNeedle.length(); k++) {
char c = text.charAt(at + k);
if (c >= 'A' && c <= 'Z') {
c = (char) (c + 32);
}
if (c != lowerNeedle.charAt(k)) {
return false;
}
}
return true;
}
private static void inlineAndUrlSpans(String text, int start, int end, List spans) {
int i = start;
while (i < end) {
if (text.charAt(i) == '`') {
int runEnd = i + 1;
while (runEnd < end && text.charAt(runEnd) == '`') {
runEnd++;
}
int runLength = runEnd - i;
int closing = matchingBacktickRun(text, runEnd, end, runLength);
if (closing != -1) {
int spanEnd = closing + runLength;
spans.add(new Span(i, spanEnd, SpanKind.INLINE));
i = spanEnd;
continue;
}
// An unmatched run is ordinary prose in its entirety, so resume AFTER
// it. Advancing one character would re-examine a proper suffix of the
// run as a shorter run, which can pair with a later run and protect
// text the prose rules should have normalized.
i = runEnd;
continue;
}
int schemeEnd = matchUrlScheme(text, i, end);
if (schemeEnd != -1) {
int spanEnd = urlEnd(text, schemeEnd, end);
spans.add(new Span(i, spanEnd, SpanKind.URL));
i = spanEnd;
continue;
}
i++;
}
}
/** Fenced code blocks first, then inline code spans and URLs in what remains. */
private static List opaqueSpans(String text) {
List fences = fencedSpans(text);
List spans = new ArrayList<>();
int cursor = 0;
for (Span fence : fences) {
inlineAndUrlSpans(text, cursor, fence.start, spans);
spans.add(fence);
cursor = fence.end;
}
inlineAndUrlSpans(text, cursor, text.length(), spans);
return spans;
}
// -------------------------------------------------- step 2, continued
/** Step 2.4: drop the byte order mark. U+FEFF is a serialization signature
* rather than writing, so it is not text and does not belong to the author.
* Removing it here, before recognition, is why it also comes out of a fence. */
private static String removeArtifacts(String text) {
StringBuilder out = new StringBuilder(text.length());
for (int i = 0; i < text.length(); ) {
int cp = text.codePointAt(i);
if (!isRemovedArtifact(cp)) {
out.appendCodePoint(cp);
}
i += Character.charCount(cp);
}
return out.toString();
}
/** Step 2.5: every line terminator becomes LF. Prose is unaffected, because
* step 6.2 collapses any of them to one space either way; what changes is the
* interior of a protected span, where CRLF and LF used to give different bytes
* for the same block. MIME text/plain is CRLF-canonical. */
private static String normalizeLineTerminators(String text) {
StringBuilder out = new StringBuilder(text.length());
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
if (c == '\r' && i + 1 < text.length() && text.charAt(i + 1) == '\n') {
out.append('\n');
i++;
continue;
}
out.append(isLineTerminator(c) ? '\n' : c);
}
return out.toString();
}
/** Step 2.6: remove the whole run of horizontal whitespace before a line ending
* or the end of the input. A pending run is emitted verbatim otherwise --
* emitting spaces instead would turn a tab inside an inline code span into a
* space, which is not this step's business. */
private static String rightTrimLines(String text) {
StringBuilder out = new StringBuilder(text.length());
StringBuilder pending = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
if (isHorizontalWhiteSpace(c)) {
pending.append(c);
continue;
}
if (c != '\n') {
out.append(pending);
}
pending.setLength(0);
out.append(c);
}
return out.toString();
}
// ------------------------------------------------------------- step 6.1
/** Step 6.1: normalize quotation.
*
* The marker first: a leading run of horizontal whitespace, a ">", and every
* following character that is horizontal whitespace or another ">" all become
* a single ">". A line that is nothing but the prefix is dropped, as is a
* blank line, because mailers disagree about whether a blank quoted line keeps
* its marker and nothing downstream would have preserved it.
*
* Then the structure. Consecutive lines of the same kind are joined, so the
* number of markers stops tracking how a client wrapped the text; and the line
* ending is kept wherever the kind changes, so a quoted question cannot absorb
* the reply beneath it. */
private static String normalizeQuotation(String text) {
List parts = new ArrayList<>();
List current = new ArrayList<>();
Boolean kind = null;
for (String line : text.split("\n", -1)) {
int i = 0;
while (i < line.length() && isHorizontalWhiteSpace(line.charAt(i))) {
i++;
}
boolean quoted = i < line.length() && line.charAt(i) == '>';
if (quoted) {
i++;
while (i < line.length()
&& (line.charAt(i) == '>' || isHorizontalWhiteSpace(line.charAt(i)))) {
i++;
}
} else {
i = 0;
}
String body = line.substring(i);
if (body.trim().isEmpty()) {
continue;
}
if (kind != null && kind != quoted) {
parts.add((kind ? ">" : "") + String.join(" ", current));
current.clear();
}
kind = quoted;
current.add(body);
}
if (kind != null) {
parts.add((kind ? ">" : "") + String.join(" ", current));
}
return String.join("\n", parts);
}
// ---------------------------------------------------- span normalization
/** Strip leading horizontal whitespace from a fence's delimiter lines. Only the
* two lines that are pure syntax; indentation inside the block is content. */
private static String normalizeFenceIndent(String body) {
List lines = linesWithEndings(body);
int fenceLength = -1;
StringBuilder out = new StringBuilder(body.length());
for (int index = 0; index < lines.size(); index++) {
String line = lines.get(index);
String core = lineBody(line);
if (fenceLength < 0) {
Matcher opening = FENCE_OPEN.matcher(core);
if (opening.matches()) {
fenceLength = opening.group(1).length();
line = LEAD_HWS.matcher(line).replaceFirst("");
}
out.append(line);
continue;
}
if (index == lines.size() - 1) {
Pattern closing = Pattern.compile("^" + HWS + "*`{" + fenceLength + ",}" + HWS + "*$");
if (closing.matcher(core).matches()) {
line = LEAD_HWS.matcher(line).replaceFirst("");
}
}
out.append(line);
}
return out.toString();
}
/** Each run of line endings inside an inline span, with any horizontal whitespace
* after it, becomes one space. That is what makes an inline span rewrap-safe. */
private static String foldInlineNewlines(String body) {
StringBuilder out = new StringBuilder(body.length());
int i = 0;
while (i < body.length()) {
char c = body.charAt(i);
if (c != '\n') {
out.append(c);
i++;
continue;
}
while (i < body.length()
&& (body.charAt(i) == '\n' || isHorizontalWhiteSpace(body.charAt(i)))) {
i++;
}
out.append(' ');
}
return out.toString();
}
private static String asciiLower(String text) {
StringBuilder out = new StringBuilder(text.length());
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
out.append(c >= 'A' && c <= 'Z' ? (char) (c + 32) : c);
}
return out.toString();
}
/** Lowercase what RFC 2045 section 5.1 defines as case-insensitive and nothing
* else: the type, the subtype and each parameter's attribute NAME. A value is
* not case-insensitive in general, so it is reproduced exactly. ";base64" is an
* attribute name with no value and folds with them. */
private static String lowerDataHeader(String header) {
String[] parts = header.split(";", -1);
for (int i = 0; i < parts.length; i++) {
if (i == 0) {
parts[i] = asciiLower(parts[i]);
continue;
}
int eq = parts[i].indexOf('=');
parts[i] = eq < 0 ? asciiLower(parts[i])
: asciiLower(parts[i].substring(0, eq)) + parts[i].substring(eq);
}
return String.join(";", parts);
}
/** Lowercase the scheme, and the host of a URI that has an authority; RFC 3986
* defines both as case-insensitive. A data: URI carries its own case-insensitive
* fields, defined by RFC 2045. Nothing else folds. */
private static String normalizeUri(String body) {
int slashes = body.indexOf("://");
if (slashes > 0) {
String scheme = body.substring(0, slashes);
String rest = body.substring(slashes + 3);
int end = rest.length();
for (int i = 0; i < rest.length(); i++) {
char c = rest.charAt(i);
if (c == '/' || c == '?' || c == '#') {
end = i;
break;
}
}
String authority = rest.substring(0, end);
String tail = rest.substring(end);
String userinfo = "";
int at = authority.lastIndexOf('@');
if (at >= 0) {
userinfo = authority.substring(0, at + 1);
authority = authority.substring(at + 1);
}
return asciiLower(scheme) + "://" + userinfo + asciiLower(authority) + tail;
}
int colon = body.indexOf(':');
if (colon < 0) {
return body;
}
String scheme = asciiLower(body.substring(0, colon));
if (!scheme.equals("data")) {
return scheme + body.substring(colon);
}
int comma = body.indexOf(',', colon + 1);
if (comma < 0) {
return scheme + body.substring(colon);
}
return scheme + ":" + lowerDataHeader(body.substring(colon + 1, comma)) + body.substring(comma);
}
/** A protected span is not untouched bytes. It is text canonicalized under a
* reduced rule set: line structure belongs to the channel, everything else
* belongs to the author. */
private static String normalizeSpan(SpanKind kind, String body) {
switch (kind) {
case FENCE:
return normalizeFenceIndent(body);
case INLINE:
return foldInlineNewlines(body);
case URL:
return normalizeUri(body);
default:
return body;
}
}
private static String applyGuardedEmoticons(String text) {
StringBuilder out = new StringBuilder(text.length());
int i = 0;
outer:
while (i < text.length()) {
for (String[] pair : GUARDED_EMOTICONS) {
String from = pair[0];
if (!text.startsWith(from, i)) {
continue;
}
int next = i + from.length();
if (next < text.length()) {
char c = text.charAt(next);
if (Character.isLetterOrDigit(c) && c < 0x80 || c == '-' || c == '_') {
continue;
}
}
out.append(pair[1]);
i = next;
continue outer;
}
out.append(text.charAt(i));
i++;
}
return out.toString();
}
private static String protect(String text, Map protectedSpans) {
List spans = opaqueSpans(text);
if (spans.isEmpty()) {
return text;
}
StringBuilder out = new StringBuilder(text.length());
int cursor = 0;
int markerNumber = 0;
for (Span span : spans) {
String marker = MARKER_OPEN + "CQT" + markerNumber + MARKER_CLOSE;
markerNumber++;
out.append(text, cursor, span.start);
out.append(marker);
protectedSpans.put(marker, normalizeSpan(span.kind, text.substring(span.start, span.end)));
cursor = span.end;
}
out.append(text, cursor, text.length());
return out.toString();
}
private static String restore(String text, Map protectedSpans) {
if (protectedSpans.isEmpty()) {
return text;
}
Matcher matcher = PROTECTED_MARKER.matcher(text);
StringBuilder out = new StringBuilder(text.length());
int cursor = 0;
while (matcher.find()) {
out.append(text, cursor, matcher.start());
String replacement = protectedSpans.get(matcher.group());
// Unreachable now that the marker is made of NUL, since no marker-shaped
// run can survive step 2. Kept because CQT 3.17 never rejects text, so a
// marker without an entry has to come out as the text it is.
out.append(replacement != null ? replacement : matcher.group());
cursor = matcher.end();
}
out.append(text, cursor, text.length());
return out.toString();
}
// ---------------------------------------------------------------- steps 4-7
/**
* One pass, in order. Nothing here runs twice.
*
*
The autocorrect tables run before space removal. A client that swaps an emoji
* for its emoticon spelling, or the reverse, is exactly the kind of tooling
* transformation CQT exists to survive, so "hello ", "hello :)" and
* "hello :-)" must all reach the same bytes. Mapping to the canonical spelling
* first puts a colon where the space rule can see it.
*
*
The cost of a single pass is that ": )" ends at ":)" rather than ":-)", since
* nothing revisits the tables after the space closes the gap.
*/
private static String canonicalizeProse(String text) {
text = normalizeNfkc17(text);
text = removeInvisibles(text);
text = normalizeQuotation(text);
text = collapseUnicodeWhitespace(text);
text = mapCodePoints(text, cp -> isDashPunctuation(cp) ? "-" : null);
text = MULTI_HYPHEN.matcher(text).replaceAll("-");
text = text.replace("ใ", ",").replace("ใ", ".");
text = text.replace("โฆ", "...");
text = LONG_DOTS.matcher(text).replaceAll("...");
text = text.replace("โ", "/");
text = mapCodePoints(text, cp -> isQuoteCharacter(cp) ? "'" : null);
for (String[] pair : AUTOCORRECT_PAIRS) {
text = text.replace(pair[0], pair[1]);
}
for (String[] pair : ASCII_AUTOCORRECT_PAIRS) {
text = text.replace(pair[0], pair[1]);
}
text = applyGuardedEmoticons(text);
text = removeSpacesAdjacentToPunctuation(text);
text = text.replace("&", " & ");
return collapseUnicodeWhitespace(text);
}
/**
* Step 4: NFKC as Unicode 17.0.0 defines it, on a runtime whose tables are older.
*
*
See UNICODE_DELTA_FROM and CCC_DELTA above for what is being corrected and
* why each correction is exact. When the text contains none of the six affected
* scalars -- which is the case for essentially all text -- this is the JDK's own
* NFKC and nothing else.
*/
private static String normalizeNfkc17(String text) {
text = text.replace(UNICODE_DELTA_FROM, UNICODE_DELTA_TO);
boolean affected = false;
for (int[] delta : CCC_DELTA) {
if (text.indexOf(delta[0]) >= 0) {
affected = true;
break;
}
}
if (!affected) {
return java.text.Normalizer.normalize(text, java.text.Normalizer.Form.NFKC);
}
// Rewrite every affected mark, and every pre-existing occurrence of a proxy,
// as that proxy, remembering in order what each occurrence really was.
List tags220 = new ArrayList<>();
List tags234 = new ArrayList<>();
StringBuilder substituted = new StringBuilder(text.length());
int i = 0;
while (i < text.length()) {
int cp = text.codePointAt(i);
i += Character.charCount(cp);
int proxy = proxyFor(cp);
if (proxy == CCC_PROXY_220) {
tags220.add(cp);
} else if (proxy == CCC_PROXY_234) {
tags234.add(cp);
}
substituted.appendCodePoint(proxy >= 0 ? proxy : cp);
}
String normalized = java.text.Normalizer.normalize(
substituted.toString(), java.text.Normalizer.Form.NFKC);
StringBuilder out = new StringBuilder(normalized.length());
int next220 = 0;
int next234 = 0;
int j = 0;
while (j < normalized.length()) {
int cp = normalized.codePointAt(j);
j += Character.charCount(cp);
if (cp == CCC_PROXY_220 && next220 < tags220.size()) {
out.appendCodePoint(tags220.get(next220++));
} else if (cp == CCC_PROXY_234 && next234 < tags234.size()) {
out.appendCodePoint(tags234.get(next234++));
} else {
out.appendCodePoint(cp);
}
}
return out.toString();
}
/** The proxy standing in for {@code cp} during normalization, or -1 for none. */
private static int proxyFor(int cp) {
if (cp == CCC_PROXY_220 || cp == CCC_PROXY_234) {
return cp;
}
for (int[] delta : CCC_DELTA) {
if (delta[0] == cp) {
return delta[1];
}
}
return -1;
}
private interface CodePointMapper {
/** Return the replacement for {@code cp}, or null to keep it as it is. */
String map(int cp);
}
private static String mapCodePoints(String text, CodePointMapper mapper) {
StringBuilder out = new StringBuilder(text.length());
int i = 0;
int n = text.length();
while (i < n) {
int cp = text.codePointAt(i);
String replacement = mapper.map(cp);
if (replacement != null) {
out.append(replacement);
} else {
out.appendCodePoint(cp);
}
i += Character.charCount(cp);
}
return out.toString();
}
/**
* Step 5: drop the four layout-only characters.
*
*
U+200B survives between two scalars from a script that does not separate
* words with spaces, where it is the word separator rather than an artifact. Both
* neighbours must qualify, so a stray U+200B injected at a script boundary by a
* mailer or sanitizer is still removed. Neighbours are scalars, not UTF-16 code
* units: two of the qualifying scripts (Ahom, U+11700..U+11746) are astral.
*/
private static String removeInvisibles(String text) {
StringBuilder out = new StringBuilder(text.length());
int i = 0;
int n = text.length();
while (i < n) {
int cp = text.codePointAt(i);
int width = Character.charCount(cp);
if (!isRemovedInvisible(cp)) {
out.appendCodePoint(cp);
i += width;
continue;
}
if (cp == 0x200B) {
int before = i > 0 ? text.codePointBefore(i) : -1;
int after = (i + width) < n ? text.codePointAt(i + width) : -1;
if (before >= 0 && after >= 0 && isSpacelessScript(before) && isSpacelessScript(after)) {
out.appendCodePoint(cp);
}
}
i += width;
}
return out.toString();
}
/** Step 6: each run of White_Space becomes one U+0020, then leading/trailing spaces go. */
private static String collapseUnicodeWhitespace(String text) {
StringBuilder out = new StringBuilder(text.length());
boolean inWhitespace = false;
boolean runHasNewline = false;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
if (isWhiteSpace(c)) {
runHasNewline |= c == '\n';
if (!inWhitespace) {
out.append(' ');
}
inWhitespace = true;
} else {
if (inWhitespace && runHasNewline) {
out.setCharAt(out.length() - 1, '\n');
}
runHasNewline = false;
out.append(c);
inWhitespace = false;
}
}
// Python's str.strip(" ") trims ASCII spaces only; String.strip() would trim
// Unicode whitespace, which is a different operation.
int begin = 0;
int end = out.length();
while (begin < end && (out.charAt(begin) == ' ' || out.charAt(begin) == '\n')) {
begin++;
}
while (end > begin && (out.charAt(end - 1) == ' ' || out.charAt(end - 1) == '\n')) {
end--;
}
return out.substring(begin, end);
}
/**
* Step 7.9: attach punctuation to the side it belongs to.
*
*
Punctuation is not symmetric. Opening punctuation binds to what follows it and
* closing, final and terminal punctuation bind to what precedes, so a space is
* removed on the side the punctuation attaches to and left alone on the other.
* That keeps "ignorance, up" and "name: value" intact while still converging
* "hello :)" and "hello {U+1F60A}" on "hello:-)".
*/
private static String removeSpacesAdjacentToPunctuation(String text) {
StringBuilder out = new StringBuilder(text.length());
int n = text.length();
int cursor = 0;
int i = 0;
while (i < n) {
if (text.charAt(i) != ' ') {
i++;
continue;
}
int runStart = i;
while (i < n && text.charAt(i) == ' ') {
i++;
}
int runEnd = i;
out.append(text, cursor, runStart);
int before = runStart > 0 ? text.codePointBefore(runStart) : -1;
int after = runEnd < n ? text.codePointAt(runEnd) : -1;
boolean attachesLeft = after >= 0 && (isTerminalPunctuation(after) || isPeOrPf(after));
boolean attachesRight = before >= 0 && isPsOrPi(before);
if (!(attachesLeft || attachesRight)) {
out.append(' ');
}
cursor = runEnd;
}
out.append(text, cursor, n);
return out.toString();
}
// ---------------------------------------------------------------- conformance
public static void main(String[] args) throws IOException {
System.exit(Conformance.run(args));
}
}
/**
* The conformance runner. It lives in this file because the single-file source
* launcher ({@code java Cqt.java}) compiles exactly one source file, and this repo
* has no build tool.
*/
final class Conformance {
private Conformance() {
}
static int run(String[] args) throws IOException {
Path goldens = locate(args.length > 0 ? args[0] : null);
if (goldens == null) {
System.err.println("cannot find ../../goldens/cqt3.17.json; pass its path as the first argument");
return 2;
}
String source = Files.readString(goldens, StandardCharsets.UTF_8);
Object root = MiniJson.parse(source);
Map doc = MiniJson.asObject(root);
System.out.println("vectors: " + goldens.toAbsolutePath());
System.out.println("algorithm: " + doc.get("algorithm") + " unicode: " + doc.get("unicode_version"));
System.out.println("runtime: Java " + System.getProperty("java.version")
+ " (JDK Unicode 16 tables, corrected to " + Cqt.UNICODE_VERSION + ")");
List