chiark / gitweb /
More commands.
[disorder] / lib / unicode.c
1 /*
2  * This file is part of DisOrder
3  * Copyright (C) 2007, 2009 Richard Kettlewell
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  * 
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  * 
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 /** @file lib/unicode.c
19  * @brief Unicode support functions
20  *
21  * Here by UTF-8 and UTF-8 we mean the encoding forms of those names (not the
22  * encoding schemes).  The primary encoding form is UTF-32 but convenience
23  * wrappers using UTF-8 are provided for a number of functions.
24  *
25  * The idea is that all the strings that hit the database will be in a
26  * particular normalization form, and for the search and tags database
27  * in case-folded form, so they can be naively compared within the
28  * database code.
29  *
30  * As the code stands this guarantee is not well met!
31  *
32  * Subpages:
33  * - @ref utf32props
34  * - @ref utftransform
35  * - @ref utf32iterator
36  * - @ref utf32
37  * - @ref utf8
38  */
39
40 #include "common.h"
41
42 #include "mem.h"
43 #include "vector.h"
44 #include "unicode.h"
45 #include "unidata.h"
46
47 /** @defgroup utf32props Unicode Code Point Properties */
48 /*@{*/
49
50 static const struct unidata *utf32__unidata_hard(uint32_t c);
51
52 /** @brief Find definition of code point @p c
53  * @param c Code point
54  * @return Pointer to @ref unidata structure for @p c
55  *
56  * @p c can be any 32-bit value, a sensible value will be returned regardless.
57  * The returned pointer is NOT guaranteed to be unique to @p c.
58  */
59 static inline const struct unidata *utf32__unidata(uint32_t c) {
60   /* The bottom half of the table contains almost everything of interest
61    * and we can just return the right thing straight away */
62   if(c < UNICODE_BREAK_START)
63     return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
64   else
65     return utf32__unidata_hard(c);
66 }
67
68 /** @brief Find definition of code point @p c
69  * @param c Code point
70  * @return Pointer to @ref unidata structure for @p c
71  *
72  * @p c can be any 32-bit value, a sensible value will be returned regardless.
73  * The returned pointer is NOT guaranteed to be unique to @p c.
74  *
75  * Don't use this function (although it will work fine) - use utf32__unidata()
76  * instead.
77  */
78 static const struct unidata *utf32__unidata_hard(uint32_t c) {
79   if(c < UNICODE_BREAK_START)
80     return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
81   /* Within the break everything is unassigned */
82   if(c < UNICODE_BREAK_END)
83     return utf32__unidata(0xFFFF);      /* guaranteed to be Cn */
84   /* Planes 15 and 16 are (mostly) private use */
85   if((c >= 0xF0000 && c <= 0xFFFFD)
86      || (c >= 0x100000 && c <= 0x10FFFD))
87     return utf32__unidata(0xE000);      /* first Co code point */
88   /* Everything else above the break top is unassigned */
89   if(c >= UNICODE_BREAK_TOP)
90     return utf32__unidata(0xFFFF);      /* guaranteed to be Cn */
91   /* Currently the rest is language tags and variation selectors */
92   c -= (UNICODE_BREAK_END - UNICODE_BREAK_START);
93   return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
94 }
95
96 /** @brief Return the combining class of @p c
97  * @param c Code point
98  * @return Combining class of @p c
99  *
100  * @p c can be any 32-bit value, a sensible value will be returned regardless.
101  */
102 static inline int utf32__combining_class(uint32_t c) {
103   return utf32__unidata(c)->ccc;
104 }
105
106 /** @brief Return the combining class of @p c
107  * @param c Code point
108  * @return Combining class of @p c
109  *
110  * @p c can be any 32-bit value, a sensible value will be returned regardless.
111  */
112 int utf32_combining_class(uint32_t c) {
113   return utf32__combining_class(c);
114 }
115
116 /** @brief Return the General_Category value for @p c
117  * @param c Code point
118  * @return General_Category property value
119  *
120  * @p c can be any 32-bit value, a sensible value will be returned regardless.
121  */
122 static inline enum unicode_General_Category utf32__general_category(uint32_t c) {
123   return utf32__unidata(c)->general_category;
124 }
125
126 /** @brief Determine Grapheme_Break property
127  * @param c Code point
128  * @return Grapheme_Break property value of @p c
129  *
130  * @p c can be any 32-bit value, a sensible value will be returned regardless.
131  */
132 static inline enum unicode_Grapheme_Break utf32__grapheme_break(uint32_t c) {
133   return utf32__unidata(c)->grapheme_break;
134 }
135
136 /** @brief Determine Word_Break property
137  * @param c Code point
138  * @return Word_Break property value of @p c
139  *
140  * @p c can be any 32-bit value, a sensible value will be returned regardless.
141  */
142 static inline enum unicode_Word_Break utf32__word_break(uint32_t c) {
143   return utf32__unidata(c)->word_break;
144 }
145
146 /** @brief Determine Sentence_Break property
147  * @param c Code point
148  * @return Word_Break property value of @p c
149  *
150  * @p c can be any 32-bit value, a sensible value will be returned regardless.
151  */
152 static inline enum unicode_Sentence_Break utf32__sentence_break(uint32_t c) {
153   return utf32__unidata(c)->sentence_break;
154 }
155
156 /** @brief Return true if @p c is ignorable for boundary specifications
157  * @param wb Word break property value
158  * @return non-0 if @p wb is unicode_Word_Break_Extend or unicode_Word_Break_Format
159  */
160 static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb) {
161   return (wb == unicode_Word_Break_Extend
162           || wb == unicode_Word_Break_Format);
163 }
164
165 /** @brief Return the canonical decomposition of @p c
166  * @param c Code point
167  * @return 0-terminated canonical decomposition, or 0
168  */
169 static inline const uint32_t *utf32__decomposition_canon(uint32_t c) {
170   const struct unidata *const data = utf32__unidata(c);
171   const uint32_t *const decomp = data->decomp;
172
173   if(decomp && !(data->flags & unicode_compatibility_decomposition))
174     return decomp;
175   else
176     return 0;
177 }
178
179 /** @brief Return the compatibility decomposition of @p c
180  * @param c Code point
181  * @return 0-terminated decomposition, or 0
182  */
183 static inline const uint32_t *utf32__decomposition_compat(uint32_t c) {
184   return utf32__unidata(c)->decomp;
185 }
186
187 /*@}*/
188 /** @defgroup utftransform Functions that transform between different Unicode encoding forms */
189 /*@{*/
190
191 /** @brief Convert UTF-32 to UTF-8
192  * @param s Source string
193  * @param ns Length of source string in code points
194  * @param ndp Where to store length of destination string (or NULL)
195  * @return Newly allocated destination string or NULL on error
196  *
197  * If the UTF-32 is not valid then NULL is returned.  A UTF-32 code point is
198  * invalid if:
199  * - it codes for a UTF-16 surrogate
200  * - it codes for a value outside the unicode code space
201  *
202  * The return value is always 0-terminated.  The value returned via @p *ndp
203  * does not include the terminator.
204  */
205 char *utf32_to_utf8(const uint32_t *s, size_t ns, size_t *ndp) {
206   struct dynstr d;
207   uint32_t c;
208
209   dynstr_init(&d);
210   while(ns > 0) {
211     c = *s++;
212     if(c < 0x80)
213       dynstr_append(&d, c);
214     else if(c < 0x0800) {
215       dynstr_append(&d, 0xC0 | (c >> 6));
216       dynstr_append(&d, 0x80 | (c & 0x3F));
217     } else if(c < 0x10000) {
218       if(c >= 0xD800 && c <= 0xDFFF)
219         goto error;
220       dynstr_append(&d, 0xE0 | (c >> 12));
221       dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
222       dynstr_append(&d, 0x80 | (c & 0x3F));
223     } else if(c < 0x110000) {
224       dynstr_append(&d, 0xF0 | (c >> 18));
225       dynstr_append(&d, 0x80 | ((c >> 12) & 0x3F));
226       dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
227       dynstr_append(&d, 0x80 | (c & 0x3F));
228     } else
229       goto error;
230     --ns;
231   }
232   dynstr_terminate(&d);
233   if(ndp)
234     *ndp = d.nvec;
235   return d.vec;
236 error:
237   xfree(d.vec);
238   return 0;
239 }
240
241 /** @brief Convert UTF-8 to UTF-32
242  * @param s Source string
243  * @param ns Length of source string in code points
244  * @param ndp Where to store length of destination string (or NULL)
245  * @return Newly allocated destination string or NULL on error
246  *
247  * The return value is always 0-terminated.  The value returned via @p *ndp
248  * does not include the terminator.
249  *
250  * If the UTF-8 is not valid then NULL is returned.  A UTF-8 sequence
251  * for a code point is invalid if:
252  * - it is not the shortest possible sequence for the code point
253  * - it codes for a UTF-16 surrogate
254  * - it codes for a value outside the unicode code space
255  */
256 uint32_t *utf8_to_utf32(const char *s, size_t ns, size_t *ndp) {
257   struct dynstr_ucs4 d;
258   uint32_t c32;
259   const uint8_t *ss = (const uint8_t *)s;
260   int n;
261
262   dynstr_ucs4_init(&d);
263   while(ns > 0) {
264     const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
265     if(r->count <= ns) {
266       switch(r->count) {
267       case 1:
268         c32 = *ss;
269         break;
270       case 2:
271         if(ss[1] < r->min2 || ss[1] > r->max2)
272           goto error;
273         c32 = *ss & 0x1F;
274         break;
275       case 3:
276         if(ss[1] < r->min2 || ss[1] > r->max2)
277           goto error;
278         c32 = *ss & 0x0F;
279         break;
280       case 4:
281         if(ss[1] < r->min2 || ss[1] > r->max2)
282           goto error;
283         c32 = *ss & 0x07;
284         break;
285       default:
286         goto error;
287       }
288     } else
289       goto error;
290     for(n = 1; n < r->count; ++n) {
291       if(ss[n] < 0x80 || ss[n] > 0xBF)
292         goto error;
293       c32 = (c32 << 6) | (ss[n] & 0x3F);
294     }
295     dynstr_ucs4_append(&d, c32);
296     ss += r->count;
297     ns -= r->count;
298   }
299   dynstr_ucs4_terminate(&d);
300   if(ndp)
301     *ndp = d.nvec;
302   return d.vec;
303 error:
304   xfree(d.vec);
305   return 0;
306 }
307
308 /** @brief Test whether [s,s+ns) is valid UTF-8
309  * @param s Start of string
310  * @param ns Length of string
311  * @return non-0 if @p s is valid UTF-8, 0 if it is not valid
312  *
313  * This function is intended to be much faster than calling utf8_to_utf32() and
314  * throwing away the result.
315  */
316 int utf8_valid(const char *s, size_t ns) {
317   const uint8_t *ss = (const uint8_t *)s;
318   while(ns > 0) {
319     const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
320     if(r->count <= ns) {
321       switch(r->count) {
322       case 1:
323         break;
324       case 2:
325         if(ss[1] < r->min2 || ss[1] > r->max2)
326           return 0;
327         break;
328       case 3:
329         if(ss[1] < r->min2 || ss[1] > r->max2)
330           return 0;
331         if(ss[2] < 0x80 || ss[2] > 0xBF)
332           return 0;
333         break;
334       case 4:
335         if(ss[1] < r->min2 || ss[1] > r->max2)
336           return 0;
337         if(ss[2] < 0x80 || ss[2] > 0xBF)
338           return 0;
339         if(ss[3] < 0x80 || ss[3] > 0xBF)
340           return 0;
341         break;
342       default:
343         return 0;
344       }
345     } else
346       return 0;
347     ss += r->count;
348     ns -= r->count;
349   }
350   return 1;
351 }
352
353 /*@}*/
354 /** @defgroup utf32iterator UTF-32 string iterators */
355 /*@{*/
356
357 struct utf32_iterator_data {
358   /** @brief Start of string */
359   const uint32_t *s;
360
361   /** @brief Length of string */
362   size_t ns;
363
364   /** @brief Current position */
365   size_t n;
366
367   /** @brief Last two non-ignorable characters or (uint32_t)-1
368    *
369    * last[1] is the non-Extend/Format character just before position @p n;
370    * last[0] is the one just before that.
371    *
372    * Exception 1: if there is no such non-Extend/Format character then an
373    * Extend/Format character is accepted instead.
374    *
375    * Exception 2: if there is no such character even taking that into account
376    * the value is (uint32_t)-1.
377    */
378   uint32_t last[2];
379
380   /** @brief Tailoring for Word_Break */
381   unicode_property_tailor *word_break;
382 };
383
384 /** @brief Initialize an internal private iterator
385  * @param it Iterator
386  * @param s Start of string
387  * @param ns Length of string
388  * @param n Absolute position
389  */
390 static void utf32__iterator_init(utf32_iterator it,
391                                  const uint32_t *s, size_t ns, size_t n) {
392   it->s = s;
393   it->ns = ns;
394   it->n = 0;
395   it->last[0] = it->last[1] = -1;
396   it->word_break = 0;
397   utf32_iterator_set(it, n);
398 }
399
400 /** @brief Create a new iterator pointing at the start of a string
401  * @param s Start of string
402  * @param ns Length of string
403  * @return New iterator
404  */
405 utf32_iterator utf32_iterator_new(const uint32_t *s, size_t ns) {
406   utf32_iterator it = xmalloc(sizeof *it);
407   utf32__iterator_init(it, s, ns, 0);
408   return it;
409 }
410
411 /** @brief Tailor this iterator's interpretation of the Word_Break property.
412  * @param it Iterator
413  * @param pt Property tailor function or NULL
414  *
415  * After calling this the iterator will call @p pt to determine the Word_Break
416  * property of each code point.  If it returns -1 the default value will be
417  * used otherwise the returned value will be used.
418  *
419  * @p pt can be NULL to revert to the default value of the property.
420  *
421  * It is safe to call this function at any time; the iterator's internal state
422  * will be reset to suit the new tailoring.
423  */
424 void utf32_iterator_tailor_word_break(utf32_iterator it,
425                                       unicode_property_tailor *pt) {
426   it->word_break = pt;
427   utf32_iterator_set(it, it->n);
428 }
429
430 static inline enum unicode_Word_Break utf32__iterator_word_break(utf32_iterator it,
431                                                                  uint32_t c) {
432   if(!it->word_break)
433     return utf32__word_break(c);
434   else {
435     const int t = it->word_break(c);
436
437     if(t < 0)
438       return utf32__word_break(c);
439     else
440       return t;
441   }
442 }
443
444 /** @brief Destroy an iterator
445  * @param it Iterator
446  */
447 void utf32_iterator_destroy(utf32_iterator it) {
448   xfree(it);
449 }
450
451 /** @brief Find the current position of an interator
452  * @param it Iterator
453  */
454 size_t utf32_iterator_where(utf32_iterator it) {
455   return it->n;
456 }
457
458 /** @brief Set an iterator's absolute position
459  * @param it Iterator
460  * @param n Absolute position
461  * @return 0 on success, non-0 on error
462  *
463  * It is an error to position the iterator outside the string (but acceptable
464  * to point it at the hypothetical post-final character).  If an invalid value
465  * of @p n is specified then the iterator is not changed.
466  *
467  * This function works by backing up and then advancing to reconstruct the
468  * iterator's internal state for position @p n.  The worst case will be O(n)
469  * time complexity (with a worse constant factor that utf32_iterator_advance())
470  * but the typical case is essentially constant-time.
471  */
472 int utf32_iterator_set(utf32_iterator it, size_t n) {
473   /* We can't just jump to position @p n; the @p last[] values will be wrong.
474    * What we need is to jump a bit behind @p n and then advance forward,
475    * updating @p last[] along the way.  How far back?  We need to cross two
476    * non-ignorable code points as we advance forwards, so we'd better pass two
477    * such characters on the way back (if such are available).
478    */
479   size_t m;
480
481   if(n > it->ns)                        /* range check */
482     return -1;
483   /* Walk backwards skipping ignorable code points */
484   m = n;
485   while(m > 0
486         && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
487                                                                  it->s[m-1]))))
488     --m;
489   /* Either m=0 or s[m-1] is not ignorable */
490   if(m > 0) {
491     --m;
492     /* s[m] is our first non-ignorable code; look for a second in the same
493        way **/
494     while(m > 0
495           && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
496                                                                    it->s[m-1]))))
497       --m;
498     /* Either m=0 or s[m-1] is not ignorable */
499     if(m > 0)
500       --m;
501   }
502   it->last[0] = it->last[1] = -1;
503   it->n = m;
504   return utf32_iterator_advance(it, n - m);
505 }
506
507 /** @brief Advance an iterator
508  * @param it Iterator
509  * @param count Number of code points to advance by
510  * @return 0 on success, non-0 on error
511  *
512  * It is an error to advance an iterator beyond the hypothetical post-final
513  * character of the string.  If an invalid value of @p n is specified then the
514  * iterator is not changed.
515  *
516  * This function has O(n) time complexity: it works by advancing naively
517  * forwards through the string.
518  */
519 int utf32_iterator_advance(utf32_iterator it, size_t count) {
520   if(count <= it->ns - it->n) {
521     while(count > 0) {
522       const uint32_t c = it->s[it->n];
523       const enum unicode_Word_Break wb = utf32__iterator_word_break(it, c);
524       if(it->last[1] == (uint32_t)-1
525          || !utf32__boundary_ignorable(wb)) {
526         it->last[0] = it->last[1];
527         it->last[1] = c;
528       }
529       ++it->n;
530       --count;
531     }
532     return 0;
533   } else
534     return -1;
535 }
536
537 /** @brief Find the current code point
538  * @param it Iterator
539  * @return Current code point or 0
540  *
541  * If the iterator points at the hypothetical post-final character of the
542  * string then 0 is returned.  NB that this doesn't mean that there aren't any
543  * 0 code points inside the string!
544  */
545 uint32_t utf32_iterator_code(utf32_iterator it) {
546   if(it->n < it->ns)
547     return it->s[it->n];
548   else
549     return 0;
550 }
551
552 /** @brief Test for a grapheme boundary
553  * @param it Iterator
554  * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
555  *
556  * This function identifies default grapheme cluster boundaries as described in
557  * UAX #29 s3.  It returns non-0 if @p it points at the code point just after a
558  * grapheme cluster boundary (including the hypothetical code point just after
559  * the end of the string).
560  */
561 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
562   uint32_t before, after;
563   enum unicode_Grapheme_Break gbbefore, gbafter;
564   /* GB1 and GB2 */
565   if(it->n == 0 || it->n == it->ns)
566     return 1;
567   /* Now we know that s[n-1] and s[n] are safe to inspect */
568   /* GB3 */
569   before = it->s[it->n-1];
570   after = it->s[it->n];
571   if(before == 0x000D && after == 0x000A)
572     return 0;
573   gbbefore = utf32__grapheme_break(before);
574   gbafter = utf32__grapheme_break(after);
575   /* GB4 */
576   if(gbbefore == unicode_Grapheme_Break_Control
577      || before == 0x000D
578      || before == 0x000A)
579     return 1;
580   /* GB5 */
581   if(gbafter == unicode_Grapheme_Break_Control
582      || after == 0x000D
583      || after == 0x000A)
584     return 1;
585   /* GB6 */
586   if(gbbefore == unicode_Grapheme_Break_L
587      && (gbafter == unicode_Grapheme_Break_L
588          || gbafter == unicode_Grapheme_Break_V
589          || gbafter == unicode_Grapheme_Break_LV
590          || gbafter == unicode_Grapheme_Break_LVT))
591     return 0;
592   /* GB7 */
593   if((gbbefore == unicode_Grapheme_Break_LV
594       || gbbefore == unicode_Grapheme_Break_V)
595      && (gbafter == unicode_Grapheme_Break_V
596          || gbafter == unicode_Grapheme_Break_T))
597     return 0;
598   /* GB8 */
599   if((gbbefore == unicode_Grapheme_Break_LVT
600       || gbbefore == unicode_Grapheme_Break_T)
601      && gbafter == unicode_Grapheme_Break_T)
602     return 0;
603   /* GB9 */
604   if(gbafter == unicode_Grapheme_Break_Extend)
605     return 0;
606   /* GB9a */
607   if(gbafter == unicode_Grapheme_Break_SpacingMark)
608     return 0;
609   /* GB9b */
610   if(gbbefore == unicode_Grapheme_Break_Prepend)
611     return 0;
612   /* GB10 */
613   return 1;
614
615 }
616
617 /** @brief Test for a word boundary
618  * @param it Iterator
619  * @return Non-0 if pointing just after a word boundary, otherwise 0
620  *
621  * This function identifies default word boundaries as described in UAX #29 s4.
622  * It returns non-0 if @p it points at the code point just after a word
623  * boundary (including the hypothetical code point just after the end of the
624  * string) and 0 otherwise.
625  */
626 int utf32_iterator_word_boundary(utf32_iterator it) {
627   uint32_t before, after;
628   enum unicode_Word_Break wbtwobefore, wbbefore, wbafter, wbtwoafter;
629   size_t nn;
630
631   /* WB1 and WB2 */
632   if(it->n == 0 || it->n == it->ns)
633     return 1;
634   before = it->s[it->n-1];
635   after = it->s[it->n];
636   /* WB3 */
637   if(before == 0x000D && after == 0x000A)
638     return 0;
639   /* WB3a */
640   if(utf32__iterator_word_break(it, before) == unicode_Word_Break_Newline
641      || before == 0x000D
642      || before == 0x000A)
643     return 1;
644   /* WB3b */
645   if(utf32__iterator_word_break(it, after) == unicode_Word_Break_Newline
646      || after == 0x000D
647      || after == 0x000A)
648     return 1;
649   /* WB4 */
650   /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
651   if(utf32__sentence_break(before) != unicode_Sentence_Break_Sep
652      && utf32__boundary_ignorable(utf32__iterator_word_break(it, after)))
653     return 0;
654   /* Gather the property values we'll need for the rest of the test taking the
655    * s6.2 changes into account */
656   /* First we look at the code points after the proposed boundary */
657   nn = it->n;                           /* <it->ns */
658   wbafter = utf32__iterator_word_break(it, it->s[nn++]);
659   if(!utf32__boundary_ignorable(wbafter)) {
660     /* X (Extend|Format)* -> X */
661     while(nn < it->ns
662           && utf32__boundary_ignorable(utf32__iterator_word_break(it,
663                                                                   it->s[nn])))
664       ++nn;
665   }
666   /* It's possible now that nn=ns */
667   if(nn < it->ns)
668     wbtwoafter = utf32__iterator_word_break(it, it->s[nn]);
669   else
670     wbtwoafter = unicode_Word_Break_Other;
671
672   /* We've already recorded the non-ignorable code points before the proposed
673    * boundary */
674   wbbefore = utf32__iterator_word_break(it, it->last[1]);
675   wbtwobefore = utf32__iterator_word_break(it, it->last[0]);
676
677   /* WB5 */
678   if(wbbefore == unicode_Word_Break_ALetter
679      && wbafter == unicode_Word_Break_ALetter)
680     return 0;
681   /* WB6 */
682   if(wbbefore == unicode_Word_Break_ALetter
683      && (wbafter == unicode_Word_Break_MidLetter
684          || wbafter == unicode_Word_Break_MidNumLet)
685      && wbtwoafter == unicode_Word_Break_ALetter)
686     return 0;
687   /* WB7 */
688   if(wbtwobefore == unicode_Word_Break_ALetter
689      && (wbbefore == unicode_Word_Break_MidLetter
690          || wbbefore == unicode_Word_Break_MidNumLet)
691      && wbafter == unicode_Word_Break_ALetter)
692     return 0;
693   /* WB8 */
694   if(wbbefore == unicode_Word_Break_Numeric
695      && wbafter == unicode_Word_Break_Numeric)
696     return 0;
697   /* WB9 */
698   if(wbbefore == unicode_Word_Break_ALetter
699      && wbafter == unicode_Word_Break_Numeric)
700     return 0;
701   /* WB10 */
702   if(wbbefore == unicode_Word_Break_Numeric
703      && wbafter == unicode_Word_Break_ALetter)
704     return 0;
705    /* WB11 */
706   if(wbtwobefore == unicode_Word_Break_Numeric
707      && (wbbefore == unicode_Word_Break_MidNum
708          || wbbefore == unicode_Word_Break_MidNumLet)
709      && wbafter == unicode_Word_Break_Numeric)
710     return 0;
711   /* WB12 */
712   if(wbbefore == unicode_Word_Break_Numeric
713      && (wbafter == unicode_Word_Break_MidNum
714          || wbafter == unicode_Word_Break_MidNumLet)
715      && wbtwoafter == unicode_Word_Break_Numeric)
716     return 0;
717   /* WB13 */
718   if(wbbefore == unicode_Word_Break_Katakana
719      && wbafter == unicode_Word_Break_Katakana)
720     return 0;
721   /* WB13a */
722   if((wbbefore == unicode_Word_Break_ALetter
723       || wbbefore == unicode_Word_Break_Numeric
724       || wbbefore == unicode_Word_Break_Katakana
725       || wbbefore == unicode_Word_Break_ExtendNumLet)
726      && wbafter == unicode_Word_Break_ExtendNumLet)
727     return 0;
728   /* WB13b */
729   if(wbbefore == unicode_Word_Break_ExtendNumLet
730      && (wbafter == unicode_Word_Break_ALetter
731          || wbafter == unicode_Word_Break_Numeric
732          || wbafter == unicode_Word_Break_Katakana))
733     return 0;
734   /* WB14 */
735   return 1;
736 }
737
738 /*@}*/
739 /** @defgroup utf32 Functions that operate on UTF-32 strings */
740 /*@{*/
741
742 /** @brief Return the length of a 0-terminated UTF-32 string
743  * @param s Pointer to 0-terminated string
744  * @return Length of string in code points (excluding terminator)
745  *
746  * Unlike the conversion functions no validity checking is done on the string.
747  */
748 size_t utf32_len(const uint32_t *s) {
749   const uint32_t *t = s;
750
751   while(*t)
752     ++t;
753   return (size_t)(t - s);
754 }
755
756 /** @brief Stably sort [s,s+ns) into descending order of combining class
757  * @param s Start of array
758  * @param ns Number of elements, must be at least 1
759  * @param buffer Buffer of at least @p ns elements
760  */
761 static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
762   uint32_t *a, *b, *bp;
763   size_t na, nb;
764
765   switch(ns) {
766   case 1:                       /* 1-element array is always sorted */
767     return;
768   case 2:                       /* 2-element arrays are trivial to sort */
769     if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) {
770       uint32_t tmp = s[0];
771       s[0] = s[1];
772       s[1] = tmp;
773     }
774     return;
775   default:
776     /* Partition the array */
777     na = ns / 2;
778     nb = ns - na;
779     a = s;
780     b = s + na;
781     /* Sort the two halves of the array */
782     utf32__sort_ccc(a, na, buffer);
783     utf32__sort_ccc(b, nb, buffer);
784     /* Merge them back into one, via the buffer */
785     bp = buffer;
786     while(na > 0 && nb > 0) {
787       /* We want ascending order of combining class (hence <)
788        * and we want stability within combining classes (hence <=)
789        */
790       if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
791         *bp++ = *a++;
792         --na;
793       } else {
794         *bp++ = *b++;
795         --nb;
796       }
797     }
798     while(na > 0) {
799       *bp++ = *a++;
800       --na;
801     }
802     while(nb > 0) {
803       *bp++ = *b++;
804       --nb;
805     }
806     memcpy(s, buffer,  ns * sizeof(uint32_t));
807     return;
808   }
809 }
810
811 /** @brief Put combining characters into canonical order
812  * @param s Pointer to UTF-32 string
813  * @param ns Length of @p s
814  * @return 0 on success, non-0 on error
815  *
816  * @p s is modified in-place.  See Unicode 5.0 s3.11 for details of the
817  * ordering.
818  *
819  * Currently we only support a maximum of 1024 combining characters after each
820  * base character.  If this limit is exceeded then a non-0 value is returned.
821  */
822 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
823   size_t nc;
824   uint32_t buffer[1024];
825
826   /* The ordering amounts to a stable sort of each contiguous group of
827    * characters with non-0 combining class. */
828   while(ns > 0) {
829     /* Skip non-combining characters */
830     if(utf32__combining_class(*s) == 0) {
831       ++s;
832       --ns;
833       continue;
834     }
835     /* We must now have at least one combining character; see how many
836      * there are */
837     for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc)
838       ;
839     if(nc > 1024)
840       return -1;
841     /* Sort the array */
842     utf32__sort_ccc(s, nc, buffer);
843     s += nc;
844     ns -= nc;
845   }
846   return 0;
847 }
848
849 /* Magic numbers from UAX #15 s16 */
850 #define SBase 0xAC00
851 #define LBase 0x1100
852 #define VBase 0x1161
853 #define TBase 0x11A7
854 #define LCount 19
855 #define VCount 21
856 #define TCount 28
857 #define NCount (VCount * TCount)
858 #define SCount (LCount * NCount)
859
860 /** @brief Guts of the decomposition lookup functions */
861 #define utf32__decompose_one_generic(WHICH) do {                        \
862   const uint32_t *dc = utf32__decomposition_##WHICH(c);                 \
863   if(dc) {                                                              \
864     /* Found a canonical decomposition in the table */                  \
865     while(*dc)                                                          \
866       utf32__decompose_one_##WHICH(d, *dc++);                           \
867   } else if(c >= SBase && c < SBase + SCount) {                         \
868     /* Mechanically decomposable Hangul syllable (UAX #15 s16) */       \
869     const uint32_t SIndex = c - SBase;                                  \
870     const uint32_t L = LBase + SIndex / NCount;                         \
871     const uint32_t V = VBase + (SIndex % NCount) / TCount;              \
872     const uint32_t T = TBase + SIndex % TCount;                         \
873     dynstr_ucs4_append(d, L);                                           \
874     dynstr_ucs4_append(d, V);                                           \
875     if(T != TBase)                                                      \
876       dynstr_ucs4_append(d, T);                                         \
877   } else                                                                \
878     /* Equal to own canonical decomposition */                          \
879     dynstr_ucs4_append(d, c);                                           \
880 } while(0)
881
882 /** @brief Recursively compute the canonical decomposition of @p c
883  * @param d Dynamic string to store decomposition in
884  * @param c Code point to decompose (must be a valid!)
885  * @return 0 on success, non-0 on error
886  */
887 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
888   utf32__decompose_one_generic(canon);
889 }
890
891 /** @brief Recursively compute the compatibility decomposition of @p c
892  * @param d Dynamic string to store decomposition in
893  * @param c Code point to decompose (must be a valid!)
894  * @return 0 on success, non-0 on error
895  */
896 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
897   utf32__decompose_one_generic(compat);
898 }
899
900 /** @brief Magic utf32__compositions() return value for Hangul Choseong */
901 static const uint32_t utf32__hangul_L[1];
902
903 /** @brief Return the list of compositions that @p c starts
904  * @param c Starter code point
905  * @return Composition list or NULL
906  *
907  * For Hangul leading (Choseong) jamo we return the special value
908  * utf32__hangul_L.  These code points are not listed as the targets of
909  * canonical decompositions (make-unidata checks) so there is no confusion with
910  * real decompositions here.
911  */
912 static const uint32_t *utf32__compositions(uint32_t c) {
913   const uint32_t *compositions = utf32__unidata(c)->composed;
914
915   if(compositions)
916     return compositions;
917   /* Special-casing for Hangul */
918   switch(utf32__grapheme_break(c)) {
919   default:
920     return 0;
921   case unicode_Grapheme_Break_L:
922     return utf32__hangul_L;
923   }
924 }
925
926 /** @brief Composition step
927  * @param s Start of string
928  * @param ns Length of string
929  * @return New length of string
930  *
931  * This is called from utf32__decompose_generic() to compose the result string
932  * in place.
933  */
934 static size_t utf32__compose(uint32_t *s, size_t ns) {
935   const uint32_t *compositions;
936   uint32_t *start = s, *t = s, *tt, cc;
937
938   while(ns > 0) {
939     uint32_t starter = *s++;
940     int block_starters = 0;
941     --ns;
942     /* We don't attempt to compose the following things:
943      * - final characters whatever kind they are
944      * - non-starter characters
945      * - starters that don't take part in a canonical decomposition mapping
946      */
947     if(ns == 0
948        || utf32__combining_class(starter)
949        || !(compositions = utf32__compositions(starter))) {
950       *t++ = starter;
951       continue;
952     }
953     if(compositions != utf32__hangul_L) {
954       /* Where we'll put the eventual starter */
955       tt = t++;
956       do {
957         /* See if we can find composition of starter+*s */
958         const uint32_t cchar = *s, *cp = compositions;
959         while((cc = *cp++)) {
960           const uint32_t *decomp = utf32__decomposition_canon(cc);
961           /* We know decomp[0] == starter */
962           if(decomp[1] == cchar)
963             break;
964         }
965         if(cc) {
966           /* Found a composition: cc decomposes to starter,*s */
967           starter = cc;
968           compositions = utf32__compositions(starter);
969           ++s;
970           --ns;
971         } else {
972           /* No composition found. */
973           const int class = utf32__combining_class(*s);
974           if(class) {
975             /* Transfer the uncomposable combining character to the output */
976             *t++ = *s++;
977             --ns;
978             /* All the combining characters of the same class of the
979              * uncomposable character are blocked by it, but there may be
980              * others of higher class later.  We eat the uncomposable and
981              * blocked characters and go back round the loop for that higher
982              * class. */
983             while(ns > 0 && utf32__combining_class(*s) == class) {
984               *t++ = *s++;
985               --ns;
986             }
987             /* Block any subsequent starters */
988             block_starters = 1;
989           } else {
990             /* The uncombinable character is itself a starter, so we don't
991              * transfer it to the output but instead go back round the main
992              * loop. */
993             break;
994           }
995         }
996         /* Keep going while there are still characters and the starter takes
997          * part in some composition */
998       } while(ns > 0 && compositions
999               && (!block_starters || utf32__combining_class(*s)));
1000       /* Store any remaining combining characters */
1001       while(ns > 0 && utf32__combining_class(*s)) {
1002         *t++ = *s++;
1003         --ns;
1004       }
1005       /* Store the resulting starter */
1006       *tt = starter;
1007     } else {
1008       /* Special-casing for Hangul
1009        *
1010        * If there are combining characters between the L and the V then they
1011        * will block the V and so no composition happens.  Similarly combining
1012        * characters between V and T will block the T and so we only get as far
1013        * as LV.
1014        */
1015       if(utf32__grapheme_break(*s) == unicode_Grapheme_Break_V) {
1016         const uint32_t V = *s++;
1017         const uint32_t LIndex = starter - LBase;
1018         const uint32_t VIndex = V - VBase;
1019         uint32_t TIndex;
1020         --ns;
1021         if(ns > 0
1022            && utf32__grapheme_break(*s) == unicode_Grapheme_Break_T) {
1023           /* We have an L V T sequence */
1024           const uint32_t T = *s++;
1025           TIndex = T - TBase;
1026           --ns;
1027         } else
1028           /* It's just L V */
1029           TIndex = 0;
1030         /* Compose to LVT or LV as appropriate */
1031         starter = (LIndex * VCount + VIndex) * TCount + TIndex + SBase;
1032       } /* else we only have L or LV and no V or T */
1033       *t++ = starter;
1034       /* There could be some combining characters that belong to the V or T.
1035        * These will be treated as non-starter characters at the top of the loop
1036        * and thuss transferred to the output. */
1037     }
1038   }
1039   return t - start;
1040 }
1041
1042 /** @brief Guts of the composition and decomposition functions
1043  * @param WHICH @c canon or @c compat to choose decomposition
1044  * @param COMPOSE @c 0 or @c 1 to compose
1045  */
1046 #define utf32__decompose_generic(WHICH, COMPOSE) do {   \
1047   struct dynstr_ucs4 d;                                 \
1048   uint32_t c;                                           \
1049                                                         \
1050   dynstr_ucs4_init(&d);                                 \
1051   while(ns) {                                           \
1052     c = *s++;                                           \
1053     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)    \
1054       goto error;                                       \
1055     utf32__decompose_one_##WHICH(&d, c);                \
1056     --ns;                                               \
1057   }                                                     \
1058   if(utf32__canonical_ordering(d.vec, d.nvec))          \
1059     goto error;                                         \
1060   if(COMPOSE)                                           \
1061     d.nvec = utf32__compose(d.vec, d.nvec);             \
1062   dynstr_ucs4_terminate(&d);                            \
1063   if(ndp)                                               \
1064     *ndp = d.nvec;                                      \
1065   return d.vec;                                         \
1066 error:                                                  \
1067   xfree(d.vec);                                         \
1068   return 0;                                             \
1069 } while(0)
1070
1071 /** @brief Canonically decompose @p [s,s+ns)
1072  * @param s Pointer to string
1073  * @param ns Length of string
1074  * @param ndp Where to store length of result
1075  * @return Pointer to result string, or NULL on error
1076  *
1077  * Computes NFD (Normalization Form D) of the string at @p s.  This implies
1078  * performing all canonical decompositions and then normalizing the order of
1079  * combining characters.
1080  *
1081  * Returns NULL if the string is not valid for either of the following reasons:
1082  * - it codes for a UTF-16 surrogate
1083  * - it codes for a value outside the unicode code space
1084  *
1085  * See also:
1086  * - utf32_decompose_compat()
1087  * - utf32_compose_canon()
1088  */
1089 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1090   utf32__decompose_generic(canon, 0);
1091 }
1092
1093 /** @brief Compatibility decompose @p [s,s+ns)
1094  * @param s Pointer to string
1095  * @param ns Length of string
1096  * @param ndp Where to store length of result
1097  * @return Pointer to result string, or NULL on error
1098  *
1099  * Computes NFKD (Normalization Form KD) of the string at @p s.  This implies
1100  * performing all canonical and compatibility decompositions and then
1101  * normalizing the order of combining characters.
1102  *
1103  * Returns NULL if the string is not valid for either of the following reasons:
1104  * - it codes for a UTF-16 surrogate
1105  * - it codes for a value outside the unicode code space
1106  *
1107  * See also:
1108  * - utf32_decompose_canon()
1109  * - utf32_compose_compat()
1110  */
1111 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1112   utf32__decompose_generic(compat, 0);
1113 }
1114
1115 /** @brief Canonically compose @p [s,s+ns)
1116  * @param s Pointer to string
1117  * @param ns Length of string
1118  * @param ndp Where to store length of result
1119  * @return Pointer to result string, or NULL on error
1120  *
1121  * Computes NFC (Normalization Form C) of the string at @p s.  This implies
1122  * performing all canonical decompositions, normalizing the order of combining
1123  * characters and then composing all unblocked primary compositables.
1124  *
1125  * Returns NULL if the string is not valid for either of the following reasons:
1126  * - it codes for a UTF-16 surrogate
1127  * - it codes for a value outside the unicode code space
1128  *
1129  * See also:
1130  * - utf32_compose_compat()
1131  * - utf32_decompose_canon()
1132  */
1133 uint32_t *utf32_compose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1134   utf32__decompose_generic(canon, 1);
1135 }
1136
1137 /** @brief Compatibility compose @p [s,s+ns)
1138  * @param s Pointer to string
1139  * @param ns Length of string
1140  * @param ndp Where to store length of result
1141  * @return Pointer to result string, or NULL on error
1142  *
1143  * Computes NFKC (Normalization Form KC) of the string at @p s.  This implies
1144  * performing all canonical and compatibility decompositions, normalizing the
1145  * order of combining characters and then composing all unblocked primary
1146  * compositables.
1147  *
1148  * Returns NULL if the string is not valid for either of the following reasons:
1149  * - it codes for a UTF-16 surrogate
1150  * - it codes for a value outside the unicode code space
1151  *
1152  * See also:
1153  * - utf32_compose_canon()
1154  * - utf32_decompose_compat()
1155  */
1156 uint32_t *utf32_compose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1157   utf32__decompose_generic(compat, 1);
1158 }
1159
1160 /** @brief Single-character case-fold and decompose operation */
1161 #define utf32__casefold_one(WHICH) do {                                 \
1162   const uint32_t *cf = utf32__unidata(c)->casefold;                     \
1163   if(cf) {                                                              \
1164     /* Found a case-fold mapping in the table */                        \
1165     while(*cf)                                                          \
1166       utf32__decompose_one_##WHICH(&d, *cf++);                          \
1167   } else                                                                \
1168     utf32__decompose_one_##WHICH(&d, c);                                \
1169 } while(0)
1170
1171 /** @brief Case-fold @p [s,s+ns)
1172  * @param s Pointer to string
1173  * @param ns Length of string
1174  * @param ndp Where to store length of result
1175  * @return Pointer to result string, or NULL on error
1176  *
1177  * Case-fold the string at @p s according to full default case-folding rules
1178  * (s3.13) for caseless matching.  The result will be in NFD.
1179  *
1180  * Returns NULL if the string is not valid for either of the following reasons:
1181  * - it codes for a UTF-16 surrogate
1182  * - it codes for a value outside the unicode code space
1183  */
1184 uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1185   struct dynstr_ucs4 d;
1186   uint32_t c;
1187   size_t n;
1188   uint32_t *ss = 0;
1189
1190   /* If the canonical decomposition of the string includes any combining
1191    * character that case-folds to a non-combining character then we must
1192    * normalize before we fold.  In Unicode 5.0.0 this means 0345 COMBINING
1193    * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
1194    * canonically decompose to it. */
1195   for(n = 0; n < ns; ++n)
1196     if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1197       break;
1198   if(n < ns) {
1199     /* We need a preliminary decomposition */
1200     if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1201       return 0;
1202     s = ss;
1203   }
1204   dynstr_ucs4_init(&d);
1205   while(ns) {
1206     c = *s++;
1207     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)
1208       goto error;
1209     utf32__casefold_one(canon);
1210     --ns;
1211   }
1212   if(utf32__canonical_ordering(d.vec, d.nvec))
1213     goto error;
1214   dynstr_ucs4_terminate(&d);
1215   if(ndp)
1216     *ndp = d.nvec;
1217   return d.vec;
1218 error:
1219   xfree(d.vec);
1220   xfree(ss);
1221   return 0;
1222 }
1223
1224 /** @brief Compatibility case-fold @p [s,s+ns)
1225  * @param s Pointer to string
1226  * @param ns Length of string
1227  * @param ndp Where to store length of result
1228  * @return Pointer to result string, or NULL on error
1229  *
1230  * Case-fold the string at @p s according to full default case-folding rules
1231  * (s3.13) for compatibility caseless matching.  The result will be in NFKD.
1232  *
1233  * Returns NULL if the string is not valid for either of the following reasons:
1234  * - it codes for a UTF-16 surrogate
1235  * - it codes for a value outside the unicode code space
1236  */
1237 uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1238   struct dynstr_ucs4 d;
1239   uint32_t c;
1240   size_t n;
1241   uint32_t *ss = 0;
1242
1243   for(n = 0; n < ns; ++n)
1244     if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1245       break;
1246   if(n < ns) {
1247     /* We need a preliminary _canonical_ decomposition */
1248     if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1249       return 0;
1250     s = ss;
1251   }
1252   /* This computes NFKD(toCaseFold(s)) */
1253 #define compat_casefold_middle() do {                   \
1254   dynstr_ucs4_init(&d);                                 \
1255   while(ns) {                                           \
1256     c = *s++;                                           \
1257     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)    \
1258       goto error;                                       \
1259     utf32__casefold_one(compat);                        \
1260     --ns;                                               \
1261   }                                                     \
1262   if(utf32__canonical_ordering(d.vec, d.nvec))          \
1263     goto error;                                         \
1264 } while(0)
1265   /* Do the inner (NFKD o toCaseFold) */
1266   compat_casefold_middle();
1267   /* We can do away with the NFD'd copy of the input now */
1268   xfree(ss);
1269   s = ss = d.vec;
1270   ns = d.nvec;
1271   /* Do the outer (NFKD o toCaseFold) */
1272   compat_casefold_middle();
1273   /* That's all */
1274   dynstr_ucs4_terminate(&d);
1275   if(ndp)
1276     *ndp = d.nvec;
1277   return d.vec;
1278 error:
1279   xfree(d.vec);
1280   xfree(ss);
1281   return 0;
1282 }
1283
1284 /** @brief Order a pair of UTF-32 strings
1285  * @param a First 0-terminated string
1286  * @param b Second 0-terminated string
1287  * @return -1, 0 or 1 for a less than, equal to or greater than b
1288  *
1289  * "Comparable to strcmp() at its best."
1290  */
1291 int utf32_cmp(const uint32_t *a, const uint32_t *b) {
1292   while(*a && *b && *a == *b) {
1293     ++a;
1294     ++b;
1295   }
1296   return *a < *b ? -1 : (*a > *b ? 1 : 0);
1297 }
1298
1299 /** @brief Identify a grapheme cluster boundary
1300  * @param s Start of string (must be NFD)
1301  * @param ns Length of string
1302  * @param n Index within string (in [0,ns].)
1303  * @return 1 at a grapheme cluster boundary, 0 otherwise
1304  *
1305  * This function identifies default grapheme cluster boundaries as described in
1306  * UAX #29 s3.  It returns non-0 if @p n points at the code point just after a
1307  * grapheme cluster boundary (including the hypothetical code point just after
1308  * the end of the string).
1309  *
1310  * This function uses utf32_iterator_set() internally; see that function for
1311  * remarks on performance.
1312  */
1313 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
1314   struct utf32_iterator_data it[1];
1315
1316   utf32__iterator_init(it, s, ns, n);
1317   return utf32_iterator_grapheme_boundary(it);
1318 }
1319
1320 /** @brief Identify a word boundary
1321  * @param s Start of string (must be NFD)
1322  * @param ns Length of string
1323  * @param n Index within string (in [0,ns].)
1324  * @return 1 at a word boundary, 0 otherwise
1325  *
1326  * This function identifies default word boundaries as described in UAX #29 s4.
1327  * It returns non-0 if @p n points at the code point just after a word boundary
1328  * (including the hypothetical code point just after the end of the string).
1329  *
1330  * This function uses utf32_iterator_set() internally; see that function for
1331  * remarks on performance.
1332  */
1333 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
1334   struct utf32_iterator_data it[1];
1335
1336   utf32__iterator_init(it, s, ns, n);
1337   return utf32_iterator_word_boundary(it);
1338 }
1339
1340 /** @brief Split [s,ns) into multiple words
1341  * @param s Pointer to start of string
1342  * @param ns Length of string
1343  * @param nwp Where to store word count, or NULL
1344  * @param wbreak Word_Break property tailor, or NULL
1345  * @return Pointer to array of pointers to words
1346  *
1347  * The returned array is terminated by a NULL pointer and individual
1348  * strings are 0-terminated.
1349  */
1350 uint32_t **utf32_word_split(const uint32_t *s, size_t ns, size_t *nwp,
1351                             unicode_property_tailor *wbreak) {
1352   struct utf32_iterator_data it[1];
1353   size_t b1 = 0, b2 = 0 ,i;
1354   int isword;
1355   struct vector32 v32[1];
1356   uint32_t *w;
1357
1358   vector32_init(v32);
1359   utf32__iterator_init(it, s, ns, 0);
1360   it->word_break = wbreak;
1361   /* Work our way through the string stopping at each word break. */
1362   do {
1363     if(utf32_iterator_word_boundary(it)) {
1364       /* We've found a new boundary */
1365       b1 = b2;
1366       b2 = it->n;
1367       /*fprintf(stderr, "[%zu, %zu) is a candidate word\n", b1, b2);*/
1368       /* Inspect the characters between the boundary and form an opinion as to
1369        * whether they are a word or not */
1370       isword = 0;
1371       for(i = b1; i < b2; ++i) {
1372         switch(utf32__iterator_word_break(it, it->s[i])) {
1373         case unicode_Word_Break_ALetter:
1374         case unicode_Word_Break_Numeric:
1375         case unicode_Word_Break_Katakana:
1376           isword = 1;
1377           break;
1378         default:
1379           break;
1380         }
1381       }
1382       /* If it's a word add it to the list of results */
1383       if(isword) {
1384         const size_t len = b2 - b1;
1385         w = xcalloc_noptr(len + 1, sizeof(uint32_t));
1386         memcpy(w, it->s + b1, len * sizeof (uint32_t));
1387         w[len] = 0;
1388         vector32_append(v32, w);
1389       }
1390     }
1391   } while(!utf32_iterator_advance(it, 1));
1392   vector32_terminate(v32);
1393   if(nwp)
1394     *nwp = v32->nvec;
1395   return v32->vec;
1396 }
1397
1398 /*@}*/
1399 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1400 /*@{*/
1401
1402 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1403 #define utf8__transform(FN) do {                                \
1404   uint32_t *to32 = 0, *decomp32 = 0;                            \
1405   size_t nto32, ndecomp32;                                      \
1406   char *decomp8 = 0;                                            \
1407                                                                 \
1408   if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error;        \
1409   if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error;     \
1410   decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp);            \
1411 error:                                                          \
1412   xfree(to32);                                                  \
1413   xfree(decomp32);                                              \
1414   return decomp8;                                               \
1415 } while(0)
1416
1417 /** @brief Canonically decompose @p [s,s+ns)
1418  * @param s Pointer to string
1419  * @param ns Length of string
1420  * @param ndp Where to store length of result
1421  * @return Pointer to result string, or NULL on error
1422  *
1423  * Computes NFD (Normalization Form D) of the string at @p s.  This implies
1424  * performing all canonical decompositions and then normalizing the order of
1425  * combining characters.
1426  *
1427  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1428  * this might be.
1429  *
1430  * See also:
1431  * - utf32_decompose_canon().
1432  * - utf8_decompose_compat()
1433  * - utf8_compose_canon()
1434  */
1435 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
1436   utf8__transform(utf32_decompose_canon);
1437 }
1438
1439 /** @brief Compatibility decompose @p [s,s+ns)
1440  * @param s Pointer to string
1441  * @param ns Length of string
1442  * @param ndp Where to store length of result
1443  * @return Pointer to result string, or NULL on error
1444  *
1445  * Computes NFKD (Normalization Form KD) of the string at @p s.  This implies
1446  * performing all canonical and compatibility decompositions and then
1447  * normalizing the order of combining characters.
1448  *
1449  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1450  * this might be.
1451  *
1452  * See also:
1453  * - utf32_decompose_compat().
1454  * - utf8_decompose_canon()
1455  * - utf8_compose_compat()
1456  */
1457 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
1458   utf8__transform(utf32_decompose_compat);
1459 }
1460
1461 /** @brief Canonically compose @p [s,s+ns)
1462  * @param s Pointer to string
1463  * @param ns Length of string
1464  * @param ndp Where to store length of result
1465  * @return Pointer to result string, or NULL on error
1466  *
1467  * Computes NFC (Normalization Form C) of the string at @p s.  This implies
1468  * performing all canonical decompositions, normalizing the order of combining
1469  * characters and then composing all unblocked primary compositables.
1470  *
1471  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1472  * this might be.
1473  *
1474  * See also:
1475  * - utf32_compose_canon()
1476  * - utf8_compose_compat()
1477  * - utf8_decompose_canon()
1478  */
1479 char *utf8_compose_canon(const char *s, size_t ns, size_t *ndp) {
1480   utf8__transform(utf32_compose_canon);
1481 }
1482
1483 /** @brief Compatibility compose @p [s,s+ns)
1484  * @param s Pointer to string
1485  * @param ns Length of string
1486  * @param ndp Where to store length of result
1487  * @return Pointer to result string, or NULL on error
1488  *
1489  * Computes NFKC (Normalization Form KC) of the string at @p s.  This implies
1490  * performing all canonical and compatibility decompositions, normalizing the
1491  * order of combining characters and then composing all unblocked primary
1492  * compositables.
1493  *
1494  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1495  * this might be.
1496  *
1497  * See also:
1498  * - utf32_compose_compat()
1499  * - utf8_compose_canon()
1500  * - utf8_decompose_compat()
1501  */
1502 char *utf8_compose_compat(const char *s, size_t ns, size_t *ndp) {
1503   utf8__transform(utf32_compose_compat);
1504 }
1505
1506 /** @brief Case-fold @p [s,s+ns)
1507  * @param s Pointer to string
1508  * @param ns Length of string
1509  * @param ndp Where to store length of result
1510  * @return Pointer to result string, or NULL on error
1511  *
1512  * Case-fold the string at @p s according to full default case-folding rules
1513  * (s3.13).  The result will be in NFD.
1514  *
1515  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1516  * this might be.
1517  */
1518 char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
1519   utf8__transform(utf32_casefold_canon);
1520 }
1521
1522 /** @brief Compatibility case-fold @p [s,s+ns)
1523  * @param s Pointer to string
1524  * @param ns Length of string
1525  * @param ndp Where to store length of result
1526  * @return Pointer to result string, or NULL on error
1527  *
1528  * Case-fold the string at @p s according to full default case-folding rules
1529  * (s3.13).  The result will be in NFKD.
1530  *
1531  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1532  * this might be.
1533  */
1534 char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) {
1535   utf8__transform(utf32_casefold_compat);
1536 }
1537
1538 /** @brief Split [s,ns) into multiple words
1539  * @param s Pointer to start of string
1540  * @param ns Length of string
1541  * @param nwp Where to store word count, or NULL
1542  * @param wbreak Word_Break property tailor, or NULL
1543  * @return Pointer to array of pointers to words
1544  *
1545  * The returned array is terminated by a NULL pointer and individual
1546  * strings are 0-terminated.
1547  */
1548 char **utf8_word_split(const char *s, size_t ns, size_t *nwp,
1549                        unicode_property_tailor *wbreak) {
1550   uint32_t *to32 = 0, **v32 = 0;
1551   size_t nto32, nv, n;
1552   char **v8 = 0, **ret = 0;
1553
1554   if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error;
1555   if(!(v32 = utf32_word_split(to32, nto32, &nv, wbreak))) goto error;
1556   v8 = xcalloc(sizeof (char *), nv + 1);
1557   for(n = 0; n < nv; ++n)
1558     if(!(v8[n] = utf32_to_utf8(v32[n], utf32_len(v32[n]), 0)))
1559       goto error;
1560   ret = v8;
1561   *nwp = nv;
1562   v8 = 0;                               /* don't free */
1563 error:
1564   if(v8) {
1565     for(n = 0; n < nv; ++n)
1566       xfree(v8[n]);
1567     xfree(v8);
1568   }
1569   if(v32) {
1570     for(n = 0; n < nv; ++n)
1571       xfree(v32[n]);
1572     xfree(v32);
1573   }
1574   xfree(to32);
1575   return ret;
1576 }
1577
1578
1579 /*@}*/
1580
1581 /*
1582 Local Variables:
1583 c-basic-offset:2
1584 comment-column:40
1585 fill-column:79
1586 indent-tabs-mode:nil
1587 End:
1588 */