X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/disorder/blobdiff_plain/b21a155c6389025b456895312d425c2f6c485f33..b6995afb9029aa609747d541d6fb0ea4bb185bae:/lib/unicode.c

diff --git a/lib/unicode.c b/lib/unicode.c
index 26363f2..4f4f2ca 100644
--- a/lib/unicode.c
+++ b/lib/unicode.c
@@ -30,6 +30,13 @@
  * database code.
  *
  * As the code stands this guarantee is not well met!
+ *
+ * Subpages:
+ * - @ref utf32props
+ * - @ref utftransform
+ * - @ref utf32iterator
+ * - @ref utf32
+ * - @ref utf8
  */
 
 #include <config.h>
@@ -103,7 +110,7 @@ static inline int utf32__combining_class(uint32_t c) {
 }
 
 /** @brief Return the General_Category value for @p c
- * @param Code point
+ * @param c Code point
  * @return General_Category property value
  *
  * @p c can be any 32-bit value, a sensible value will be returned regardless.
@@ -151,6 +158,28 @@ static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb) {
           || wb == unicode_Word_Break_Format);
 }
 
+/** @brief Return the canonical decomposition of @p c
+ * @param c Code point
+ * @return 0-terminated canonical decomposition, or 0
+ */
+static inline const uint32_t *utf32__decomposition_canon(uint32_t c) {
+  const struct unidata *const data = utf32__unidata(c);
+  const uint32_t *const decomp = data->decomp;
+
+  if(decomp && !(data->flags & unicode_compatibility_decomposition))
+    return decomp;
+  else
+    return 0;
+}
+
+/** @brief Return the compatibility decomposition of @p c
+ * @param c Code point
+ * @return 0-terminated decomposition, or 0
+ */
+static inline const uint32_t *utf32__decomposition_compat(uint32_t c) {
+  return utf32__unidata(c)->decomp;
+}
+
 /*@}*/
 /** @defgroup utftransform Functions that transform between different Unicode encoding forms */
 /*@{*/
@@ -209,7 +238,7 @@ error:
  * @param s Source string
  * @param ns Length of source string in code points
  * @param ndp Where to store length of destination string (or NULL)
- * @return Newly allocated destination string or NULL
+ * @return Newly allocated destination string or NULL on error
  *
  * The return value is always 0-terminated.  The value returned via @p *ndp
  * does not include the terminator.
@@ -396,6 +425,11 @@ size_t utf32_iterator_where(utf32_iterator it) {
  * It is an error to position the iterator outside the string (but acceptable
  * to point it at the hypothetical post-final character).  If an invalid value
  * of @p n is specified then the iterator is not changed.
+ *
+ * This function works by backing up and then advancing to reconstruct the
+ * iterator's internal state for position @p n.  The worst case will be O(n)
+ * time complexity (with a worse constant factor that utf32_iterator_advance())
+ * but the typical case is essentially constant-time.
  */
 int utf32_iterator_set(utf32_iterator it, size_t n) {
   /* We can't just jump to position @p n; the @p last[] values will be wrong.
@@ -476,6 +510,11 @@ uint32_t utf32_iterator_code(utf32_iterator it) {
 /** @brief Test for a grapheme boundary
  * @param it Iterator
  * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
+ *
+ * This function identifies default grapheme cluster boundaries as described in
+ * UAX #29 s3.  It returns non-0 if @p it points at the code point just after a
+ * grapheme cluster boundary (including the hypothetical code point just after
+ * the end of the string).
  */
 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
   uint32_t before, after;
@@ -530,6 +569,11 @@ int utf32_iterator_grapheme_boundary(utf32_iterator it) {
 /** @brief Test for a word boundary
  * @param it Iterator
  * @return Non-0 if pointing just after a word boundary, otherwise 0
+ *
+ * This function identifies default word boundaries as described in UAX #29 s4.
+ * It returns non-0 if @p it points at the code point just after a word
+ * boundary (including the hypothetical code point just after the end of the
+ * string) and 0 otherwise.
  */
 int utf32_iterator_word_boundary(utf32_iterator it) {
   enum unicode_Word_Break twobefore, before, after, twoafter;
@@ -674,7 +718,7 @@ static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
     /* Merge them back into one, via the buffer */
     bp = buffer;
     while(na > 0 && nb > 0) {
-      /* We want descending order of combining class (hence <)
+      /* We want ascending order of combining class (hence <)
        * and we want stability within combining classes (hence <=)
        */
       if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
@@ -701,13 +745,13 @@ static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
 /** @brief Put combining characters into canonical order
  * @param s Pointer to UTF-32 string
  * @param ns Length of @p s
- * @return 0 on success, -1 on error
+ * @return 0 on success, non-0 on error
  *
  * @p s is modified in-place.  See Unicode 5.0 s3.11 for details of the
  * ordering.
  *
  * Currently we only support a maximum of 1024 combining characters after each
- * base character.  If this limit is exceeded then -1 is returned.
+ * base character.  If this limit is exceeded then a non-0 value is returned.
  */
 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
   size_t nc;
@@ -749,7 +793,7 @@ static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
 
 /** @brief Guts of the decomposition lookup functions */
 #define utf32__decompose_one_generic(WHICH) do {                        \
-  const uint32_t *dc = utf32__unidata(c)->WHICH;                        \
+  const uint32_t *dc = utf32__decomposition_##WHICH(c);	                \
   if(dc) {                                                              \
     /* Found a canonical decomposition in the table */                  \
     while(*dc)                                                          \
@@ -772,7 +816,7 @@ static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
 /** @brief Recursively compute the canonical decomposition of @p c
  * @param d Dynamic string to store decomposition in
  * @param c Code point to decompose (must be a valid!)
- * @return 0 on success, -1 on error
+ * @return 0 on success, non-0 on error
  */
 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
   utf32__decompose_one_generic(canon);
@@ -781,14 +825,159 @@ static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
 /** @brief Recursively compute the compatibility decomposition of @p c
  * @param d Dynamic string to store decomposition in
  * @param c Code point to decompose (must be a valid!)
- * @return 0 on success, -1 on error
+ * @return 0 on success, non-0 on error
  */
 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
   utf32__decompose_one_generic(compat);
 }
 
-/** @brief Guts of the decomposition functions */
-#define utf32__decompose_generic(WHICH) do {            \
+/** @brief Magic utf32__compositions() return value for Hangul Choseong */
+static const uint32_t utf32__hangul_L[1];
+
+/** @brief Return the list of compositions that @p c starts
+ * @param c Starter code point
+ * @return Composition list or NULL
+ *
+ * For Hangul leading (Choseong) jamo we return the special value
+ * utf32__hangul_L.  These code points are not listed as the targets of
+ * canonical decompositions (make-unidata checks) so there is no confusion with
+ * real decompositions here.
+ */
+static const uint32_t *utf32__compositions(uint32_t c) {
+  const uint32_t *compositions = utf32__unidata(c)->composed;
+
+  if(compositions)
+    return compositions;
+  /* Special-casing for Hangul */
+  switch(utf32__grapheme_break(c)) {
+  default:
+    return 0;
+  case unicode_Grapheme_Break_L:
+    return utf32__hangul_L;
+  }
+}
+
+/** @brief Composition step
+ * @param s Start of string
+ * @param ns Length of string
+ * @return New length of string
+ *
+ * This is called from utf32__decompose_generic() to compose the result string
+ * in place.
+ */
+static size_t utf32__compose(uint32_t *s, size_t ns) {
+  const uint32_t *compositions;
+  uint32_t *start = s, *t = s, *tt, cc;
+
+  while(ns > 0) {
+    uint32_t starter = *s++;
+    int block_starters = 0;
+    --ns;
+    /* We don't attempt to compose the following things:
+     * - final characters whatever kind they are
+     * - non-starter characters
+     * - starters that don't take part in a canonical decomposition mapping
+     */
+    if(ns == 0
+       || utf32__combining_class(starter)
+       || !(compositions = utf32__compositions(starter))) {
+      *t++ = starter;
+      continue;
+    }
+    if(compositions != utf32__hangul_L) {
+      /* Where we'll put the eventual starter */
+      tt = t++;
+      do {
+        /* See if we can find composition of starter+*s */
+        const uint32_t cchar = *s, *cp = compositions;
+        while((cc = *cp++)) {
+          const uint32_t *decomp = utf32__decomposition_canon(cc);
+          /* We know decomp[0] == starter */
+          if(decomp[1] == cchar)
+            break;
+        }
+        if(cc) {
+          /* Found a composition: cc decomposes to starter,*s */
+          starter = cc;
+          compositions = utf32__compositions(starter);
+          ++s;
+          --ns;
+        } else {
+          /* No composition found. */
+          const int class = utf32__combining_class(*s);
+          if(class) {
+            /* Transfer the uncomposable combining character to the output */
+            *t++ = *s++;
+            --ns;
+            /* All the combining characters of the same class of the
+             * uncomposable character are blocked by it, but there may be
+             * others of higher class later.  We eat the uncomposable and
+             * blocked characters and go back round the loop for that higher
+             * class. */
+            while(ns > 0 && utf32__combining_class(*s) == class) {
+              *t++ = *s++;
+              --ns;
+            }
+            /* Block any subsequent starters */
+            block_starters = 1;
+          } else {
+            /* The uncombinable character is itself a starter, so we don't
+             * transfer it to the output but instead go back round the main
+             * loop. */
+            break;
+          }
+        }
+        /* Keep going while there are still characters and the starter takes
+         * part in some composition */
+      } while(ns > 0 && compositions
+              && (!block_starters || utf32__combining_class(*s)));
+      /* Store any remaining combining characters */
+      while(ns > 0 && utf32__combining_class(*s)) {
+        *t++ = *s++;
+        --ns;
+      }
+      /* Store the resulting starter */
+      *tt = starter;
+    } else {
+      /* Special-casing for Hangul
+       *
+       * If there are combining characters between the L and the V then they
+       * will block the V and so no composition happens.  Similarly combining
+       * characters between V and T will block the T and so we only get as far
+       * as LV.
+       */
+      if(utf32__grapheme_break(*s) == unicode_Grapheme_Break_V) {
+        const uint32_t V = *s++;
+        const uint32_t LIndex = starter - LBase;
+        const uint32_t VIndex = V - VBase;
+        uint32_t TIndex;
+        --ns;
+        if(ns > 0
+           && utf32__grapheme_break(*s) == unicode_Grapheme_Break_T) {
+          /* We have an L V T sequence */
+          const uint32_t T = *s++;
+          TIndex = T - TBase;
+          --ns;
+        } else
+          /* It's just L V */
+          TIndex = 0;
+        /* Compose to LVT or LV as appropriate */
+        starter = (LIndex * VCount + VIndex) * TCount + TIndex + SBase;
+      } /* else we only have L or LV and no V or T */
+      *t++ = starter;
+      /* There could be some combining characters that belong to the V or T.
+       * These will be treated as non-starter characters at the top of the loop
+       * and thuss transferred to the output. */
+    }
+  }
+  return t - start;
+}
+
+/** @brief Guts of the composition and decomposition functions
+ * @param WHICH @c canon or @c compat to choose decomposition
+ * @param COMPOSE @c 0 or @c 1 to compose
+ */
+#define utf32__decompose_generic(WHICH, COMPOSE) do {   \
   struct dynstr_ucs4 d;                                 \
   uint32_t c;                                           \
                                                         \
@@ -802,6 +991,8 @@ static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
   }                                                     \
   if(utf32__canonical_ordering(d.vec, d.nvec))          \
     goto error;                                         \
+  if(COMPOSE)                                           \
+    d.nvec = utf32__compose(d.vec, d.nvec);             \
   dynstr_ucs4_terminate(&d);                            \
   if(ndp)                                               \
     *ndp = d.nvec;                                      \
@@ -815,38 +1006,89 @@ error:                                                  \
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
- * Computes the canonical decomposition of a string and stably sorts combining
- * characters into canonical order.  The result is in Normalization Form D and
- * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's
- * NormalizationTest.txt.
+ * Computes NFD (Normalization Form D) of the string at @p s.  This implies
+ * performing all canonical decompositions and then normalizing the order of
+ * combining characters.
  *
  * Returns NULL if the string is not valid for either of the following reasons:
  * - it codes for a UTF-16 surrogate
  * - it codes for a value outside the unicode code space
+ *
+ * See also:
+ * - utf32_decompose_compat()
+ * - utf32_compose_canon()
  */
 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
-  utf32__decompose_generic(canon);
+  utf32__decompose_generic(canon, 0);
 }
 
 /** @brief Compatibility decompose @p [s,s+ns)
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
- * Computes the compatibility decomposition of a string and stably sorts
- * combining characters into canonical order.  The result is in Normalization
- * Form KD and (at the time of writing!) passes the NFKD tests defined in
- * Unicode 5.0's NormalizationTest.txt.
+ * Computes NFKD (Normalization Form KD) of the string at @p s.  This implies
+ * performing all canonical and compatibility decompositions and then
+ * normalizing the order of combining characters.
  *
  * Returns NULL if the string is not valid for either of the following reasons:
  * - it codes for a UTF-16 surrogate
  * - it codes for a value outside the unicode code space
+ *
+ * See also:
+ * - utf32_decompose_canon()
+ * - utf32_compose_compat()
  */
 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
-  utf32__decompose_generic(compat);
+  utf32__decompose_generic(compat, 0);
+}
+
+/** @brief Canonically compose @p [s,s+ns)
+ * @param s Pointer to string
+ * @param ns Length of string
+ * @param ndp Where to store length of result
+ * @return Pointer to result string, or NULL on error
+ *
+ * Computes NFC (Normalization Form C) of the string at @p s.  This implies
+ * performing all canonical decompositions, normalizing the order of combining
+ * characters and then composing all unblocked primary compositables.
+ *
+ * Returns NULL if the string is not valid for either of the following reasons:
+ * - it codes for a UTF-16 surrogate
+ * - it codes for a value outside the unicode code space
+ *
+ * See also:
+ * - utf32_compose_compat()
+ * - utf32_decompose_canon()
+ */
+uint32_t *utf32_compose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
+  utf32__decompose_generic(canon, 1);
+}
+
+/** @brief Compatibility compose @p [s,s+ns)
+ * @param s Pointer to string
+ * @param ns Length of string
+ * @param ndp Where to store length of result
+ * @return Pointer to result string, or NULL on error
+ *
+ * Computes NFKC (Normalization Form KC) of the string at @p s.  This implies
+ * performing all canonical and compatibility decompositions, normalizing the
+ * order of combining characters and then composing all unblocked primary
+ * compositables.
+ *
+ * Returns NULL if the string is not valid for either of the following reasons:
+ * - it codes for a UTF-16 surrogate
+ * - it codes for a value outside the unicode code space
+ *
+ * See also:
+ * - utf32_compose_canon()
+ * - utf32_decompose_compat()
+ */
+uint32_t *utf32_compose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
+  utf32__decompose_generic(compat, 1);
 }
 
 /** @brief Single-character case-fold and decompose operation */
@@ -864,7 +1106,7 @@ uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
  * Case-fold the string at @p s according to full default case-folding rules
  * (s3.13) for caseless matching.  The result will be in NFD.
@@ -913,11 +1155,11 @@ error:
   return 0;
 }
 
-/** @brief Compatibilit case-fold @p [s,s+ns)
+/** @brief Compatibility case-fold @p [s,s+ns)
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
  * Case-fold the string at @p s according to full default case-folding rules
  * (s3.13) for compatibility caseless matching.  The result will be in NFKD.
@@ -995,9 +1237,12 @@ int utf32_cmp(const uint32_t *a, const uint32_t *b) {
  * @return 1 at a grapheme cluster boundary, 0 otherwise
  *
  * This function identifies default grapheme cluster boundaries as described in
- * UAX #29 s3.  It returns 1 if @p n points at the code point just after a
+ * UAX #29 s3.  It returns non-0 if @p n points at the code point just after a
  * grapheme cluster boundary (including the hypothetical code point just after
  * the end of the string).
+ *
+ * This function uses utf32_iterator_set() internally; see that function for
+ * remarks on performance.
  */
 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
   struct utf32_iterator_data it[1];
@@ -1013,8 +1258,11 @@ int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
  * @return 1 at a word boundary, 0 otherwise
  *
  * This function identifies default word boundaries as described in UAX #29 s4.
- * It returns 1 if @p n points at the code point just after a word boundary
+ * It returns non-0 if @p n points at the code point just after a word boundary
  * (including the hypothetical code point just after the end of the string).
+ *
+ * This function uses utf32_iterator_set() internally; see that function for
+ * remarks on performance.
  */
 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
   struct utf32_iterator_data it[1];
@@ -1046,17 +1294,19 @@ error:                                                          \
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
- * Computes the canonical decomposition of a string and stably sorts combining
- * characters into canonical order.  The result is in Normalization Form D and
- * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's
- * NormalizationTest.txt.
+ * Computes NFD (Normalization Form D) of the string at @p s.  This implies
+ * performing all canonical decompositions and then normalizing the order of
+ * combining characters.
  *
  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
  * this might be.
  *
- * See also utf32_decompose_canon().
+ * See also:
+ * - utf32_decompose_canon().
+ * - utf8_decompose_compat()
+ * - utf8_compose_canon()
  */
 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
   utf8__transform(utf32_decompose_canon);
@@ -1066,27 +1316,74 @@ char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
- * Computes the compatibility decomposition of a string and stably sorts
- * combining characters into canonical order.  The result is in Normalization
- * Form KD and (at the time of writing!) passes the NFKD tests defined in
- * Unicode 5.0's NormalizationTest.txt.
+ * Computes NFKD (Normalization Form KD) of the string at @p s.  This implies
+ * performing all canonical and compatibility decompositions and then
+ * normalizing the order of combining characters.
  *
  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
  * this might be.
  *
- * See also utf32_decompose_compat().
+ * See also:
+ * - utf32_decompose_compat().
+ * - utf8_decompose_canon()
+ * - utf8_compose_compat()
  */
 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
   utf8__transform(utf32_decompose_compat);
 }
 
+/** @brief Canonically compose @p [s,s+ns)
+ * @param s Pointer to string
+ * @param ns Length of string
+ * @param ndp Where to store length of result
+ * @return Pointer to result string, or NULL on error
+ *
+ * Computes NFC (Normalization Form C) of the string at @p s.  This implies
+ * performing all canonical decompositions, normalizing the order of combining
+ * characters and then composing all unblocked primary compositables.
+ *
+ * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
+ * this might be.
+ *
+ * See also:
+ * - utf32_compose_canon()
+ * - utf8_compose_compat()
+ * - utf8_decompose_canon()
+ */
+char *utf8_compose_canon(const char *s, size_t ns, size_t *ndp) {
+  utf8__transform(utf32_compose_canon);
+}
+
+/** @brief Compatibility compose @p [s,s+ns)
+ * @param s Pointer to string
+ * @param ns Length of string
+ * @param ndp Where to store length of result
+ * @return Pointer to result string, or NULL on error
+ *
+ * Computes NFKC (Normalization Form KC) of the string at @p s.  This implies
+ * performing all canonical and compatibility decompositions, normalizing the
+ * order of combining characters and then composing all unblocked primary
+ * compositables.
+ *
+ * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
+ * this might be.
+ *
+ * See also:
+ * - utf32_compose_compat()
+ * - utf8_compose_canon()
+ * - utf8_decompose_compat()
+ */
+char *utf8_compose_compat(const char *s, size_t ns, size_t *ndp) {
+  utf8__transform(utf32_compose_compat);
+}
+
 /** @brief Case-fold @p [s,s+ns)
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
  * Case-fold the string at @p s according to full default case-folding rules
  * (s3.13).  The result will be in NFD.
@@ -1102,7 +1399,7 @@ char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
  * @param s Pointer to string
  * @param ns Length of string
  * @param ndp Where to store length of result
- * @return Pointer to result string, or NULL
+ * @return Pointer to result string, or NULL on error
  *
  * Case-fold the string at @p s according to full default case-folding rules
  * (s3.13).  The result will be in NFKD.