fcmatch.c revision d81fd2f8 
1/*
2 * fontconfig/src/fcmatch.c
3 *
4 * Copyright © 2000 Keith Packard
5 *
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of the author(s) not be used in
11 * advertising or publicity pertaining to distribution of the software without
12 * specific, written prior permission.  The authors make no
13 * representations about the suitability of this software for any purpose.  It
14 * is provided "as is" without express or implied warranty.
15 *
16 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22 * PERFORMANCE OF THIS SOFTWARE.
23 */
24
25#include "fcint.h"
26#include <float.h>
27
28
29static double
30FcCompareNumber (FcValue *value1, FcValue *value2)
31{
32    double  v1, v2, v;
33
34    switch ((int) value1->type) {
35    case FcTypeInteger:
36	v1 = (double) value1->u.i;
37	break;
38    case FcTypeDouble:
39	v1 = value1->u.d;
40	break;
41    default:
42	return -1.0;
43    }
44    switch ((int) value2->type) {
45    case FcTypeInteger:
46	v2 = (double) value2->u.i;
47	break;
48    case FcTypeDouble:
49	v2 = value2->u.d;
50	break;
51    default:
52	return -1.0;
53    }
54    v = v2 - v1;
55    if (v < 0)
56	v = -v;
57    return v;
58}
59
60static double
61FcCompareString (FcValue *v1, FcValue *v2)
62{
63    return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
64}
65
66static double
67FcCompareFamily (FcValue *v1, FcValue *v2)
68{
69    /* rely on the guarantee in FcPatternObjectAddWithBinding that
70     * families are always FcTypeString. */
71    const FcChar8* v1_string = FcValueString(v1);
72    const FcChar8* v2_string = FcValueString(v2);
73
74    if (FcToLower(*v1_string) != FcToLower(*v2_string) &&
75	*v1_string != ' ' && *v2_string != ' ')
76       return 1.0;
77
78    return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
79}
80
81static double
82FcComparePostScript (FcValue *v1, FcValue *v2)
83{
84    const FcChar8 *v1_string = FcValueString (v1);
85    const FcChar8 *v2_string = FcValueString (v2);
86    int n;
87    size_t len;
88
89    if (FcToLower (*v1_string) != FcToLower (*v2_string) &&
90	*v1_string != ' ' && *v2_string != ' ')
91	return 1.0;
92
93    n = FcStrMatchIgnoreCaseAndDelims (v1_string, v2_string, (const FcChar8 *)" -");
94    len = strlen ((const char *)v1_string);
95
96    return (double)(len - n) / (double)len;
97}
98
99static double
100FcCompareLang (FcValue *v1, FcValue *v2)
101{
102    FcLangResult    result;
103    FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
104
105    switch ((int) value1.type) {
106    case FcTypeLangSet:
107	switch ((int) value2.type) {
108	case FcTypeLangSet:
109	    result = FcLangSetCompare (value1.u.l, value2.u.l);
110	    break;
111	case FcTypeString:
112	    result = FcLangSetHasLang (value1.u.l,
113				       value2.u.s);
114	    break;
115	default:
116	    return -1.0;
117	}
118	break;
119    case FcTypeString:
120	switch ((int) value2.type) {
121	case FcTypeLangSet:
122	    result = FcLangSetHasLang (value2.u.l, value1.u.s);
123	    break;
124	case FcTypeString:
125	    result = FcLangCompare (value1.u.s,
126				    value2.u.s);
127	    break;
128	default:
129	    return -1.0;
130	}
131	break;
132    default:
133	return -1.0;
134    }
135    switch (result) {
136    case FcLangEqual:
137	return 0;
138    case FcLangDifferentCountry:
139	return 1;
140    case FcLangDifferentLang:
141    default:
142	return 2;
143    }
144}
145
146static double
147FcCompareBool (FcValue *v1, FcValue *v2)
148{
149    if (v2->type != FcTypeBool || v1->type != FcTypeBool)
150	return -1.0;
151    return (double) v2->u.b != v1->u.b;
152}
153
154static double
155FcCompareCharSet (FcValue *v1, FcValue *v2)
156{
157    return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
158}
159
160static double
161FcCompareSize (FcValue *value1, FcValue *value2)
162{
163    double  v1, v2, v;
164
165    switch ((int) value1->type) {
166    case FcTypeInteger:
167	v1 = value1->u.i;
168	break;
169    case FcTypeDouble:
170	v1 = value1->u.d;
171	break;
172    default:
173	return -1;
174    }
175    switch ((int) value2->type) {
176    case FcTypeInteger:
177	v2 = value2->u.i;
178	break;
179    case FcTypeDouble:
180	v2 = value2->u.d;
181	break;
182    default:
183	return -1;
184    }
185    if (v2 == 0)
186	return 0;
187    v = v2 - v1;
188    if (v < 0)
189	v = -v;
190    return v;
191}
192
193static double
194FcCompareFilename (FcValue *v1, FcValue *v2)
195{
196    const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
197    if (FcStrCmp (s1, s2) == 0)
198	return 0.0;
199    else if (FcStrCmpIgnoreCase (s1, s2) == 0)
200	return 1.0;
201    else if (FcStrGlobMatch (s1, s2))
202	return 2.0;
203    else
204	return 3.0;
205}
206
207static double
208FcCompareHash (FcValue *v1, FcValue *v2)
209{
210    const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
211
212    /* Do not match an empty string */
213    if (!s1 || !s2 || !s1[0] || !s2[0])
214	return 1.0;
215    return FcCompareString (v1, v2);
216}
217
218#define PRI_NULL(n)				\
219    PRI_ ## n ## _STRONG = -1,			\
220    PRI_ ## n ## _WEAK = -1,
221#define PRI1(n)
222#define PRI_FcCompareFamily(n)		PRI1(n)
223#define PRI_FcCompareString(n)		PRI1(n)
224#define PRI_FcCompareNumber(n)		PRI1(n)
225#define PRI_FcCompareSize(n)		PRI1(n)
226#define PRI_FcCompareBool(n)		PRI1(n)
227#define PRI_FcCompareFilename(n)	PRI1(n)
228#define PRI_FcCompareCharSet(n)		PRI1(n)
229#define PRI_FcCompareLang(n)		PRI1(n)
230#define PRI_FcComparePostScript(n)	PRI1(n)
231#define PRI_FcCompareHash(n)		PRI1(n)
232
233#define FC_OBJECT(NAME, Type, Cmp)	PRI_##Cmp(NAME)
234
235typedef enum _FcMatcherPriorityDummy {
236#include "fcobjs.h"
237} FcMatcherPriorityDummy;
238
239#undef FC_OBJECT
240
241#undef PRI1
242#define PRI1(n)					\
243    PRI_ ## n,					\
244    PRI_ ## n ## _STRONG = PRI_ ## n,		\
245    PRI_ ## n ## _WEAK = PRI_ ## n
246
247typedef enum _FcMatcherPriority {
248    PRI1(HASH),
249    PRI1(FILE),
250    PRI1(FOUNDRY),
251    PRI1(CHARSET),
252    PRI_FAMILY_STRONG,
253    PRI_POSTSCRIPT_NAME_STRONG,
254    PRI1(LANG),
255    PRI_FAMILY_WEAK,
256    PRI_POSTSCRIPT_NAME_WEAK,
257    PRI1(SPACING),
258    PRI1(PIXEL_SIZE),
259    PRI1(STYLE),
260    PRI1(SLANT),
261    PRI1(WEIGHT),
262    PRI1(WIDTH),
263    PRI1(DECORATIVE),
264    PRI1(ANTIALIAS),
265    PRI1(RASTERIZER),
266    PRI1(OUTLINE),
267    PRI1(FONTVERSION),
268    PRI_END
269} FcMatcherPriority;
270
271#undef PRI1
272
273typedef struct _FcMatcher {
274    FcObject object;
275    double   (*compare) (FcValue *value1, FcValue *value2);
276    int      strong, weak;
277} FcMatcher;
278
279/*
280 * Order is significant, it defines the precedence of
281 * each value, earlier values are more significant than
282 * later values
283 */
284#define FC_OBJECT(NAME, Type, Cmp)	{ FC_##NAME##_OBJECT,	Cmp,	PRI_##NAME##_STRONG,	PRI_##NAME##_WEAK },
285static const FcMatcher _FcMatchers [] = {
286    { FC_INVALID_OBJECT, NULL, -1, -1 },
287#include "fcobjs.h"
288};
289#undef FC_OBJECT
290
291static const FcMatcher*
292FcObjectToMatcher (FcObject object,
293		   FcBool   include_lang)
294{
295    if (include_lang)
296    {
297	switch (object) {
298	case FC_FAMILYLANG_OBJECT:
299	case FC_STYLELANG_OBJECT:
300	case FC_FULLNAMELANG_OBJECT:
301	    object = FC_LANG_OBJECT;
302	    break;
303	}
304    }
305    if (object > FC_MAX_BASE_OBJECT ||
306	!_FcMatchers[object].compare ||
307	_FcMatchers[object].strong == -1 ||
308	_FcMatchers[object].weak == -1)
309	return NULL;
310
311    return _FcMatchers + object;
312}
313
314static FcBool
315FcCompareValueList (FcObject	     object,
316		    const FcMatcher *match,
317		    FcValueListPtr   v1orig,	/* pattern */
318		    FcValueListPtr   v2orig,	/* target */
319		    FcValue         *bestValue,
320		    double          *value,
321		    int             *n,
322		    FcResult        *result)
323{
324    FcValueListPtr  v1, v2;
325    double    	    v, best, bestStrong, bestWeak;
326    int		    j, k, pos = 0;
327
328    if (!match)
329    {
330	if (bestValue)
331	    *bestValue = FcValueCanonicalize(&v2orig->value);
332	if (n)
333	    *n = 0;
334	return FcTrue;
335    }
336
337    best = DBL_MAX;
338    bestStrong = DBL_MAX;
339    bestWeak = DBL_MAX;
340    j = 1;
341    for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
342    {
343	for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
344	{
345	    v = (match->compare) (&v1->value, &v2->value);
346	    if (v < 0)
347	    {
348		*result = FcResultTypeMismatch;
349		return FcFalse;
350	    }
351	    v = v * 1000 + j;
352	    if (v < best)
353	    {
354		if (bestValue)
355		    *bestValue = FcValueCanonicalize(&v2->value);
356		best = v;
357		pos = k;
358	    }
359	    if (v1->binding == FcValueBindingStrong)
360	    {
361		if (v < bestStrong)
362		    bestStrong = v;
363	    }
364	    else
365	    {
366		if (v < bestWeak)
367		    bestWeak = v;
368	    }
369	}
370	j++;
371    }
372    if (FcDebug () & FC_DBG_MATCHV)
373    {
374	printf (" %s: %g ", FcObjectName (object), best);
375	FcValueListPrint (v1orig);
376	printf (", ");
377	FcValueListPrint (v2orig);
378	printf ("\n");
379    }
380    if (value)
381    {
382	int weak    = match->weak;
383	int strong  = match->strong;
384	if (weak == strong)
385	    value[strong] += best;
386	else
387	{
388	    value[weak] += bestWeak;
389	    value[strong] += bestStrong;
390	}
391    }
392    if (n)
393	*n = pos;
394
395    return FcTrue;
396}
397
398/*
399 * Return a value indicating the distance between the two lists of
400 * values
401 */
402
403static FcBool
404FcCompare (FcPattern	*pat,
405	   FcPattern	*fnt,
406	   double	*value,
407	   FcResult	*result)
408{
409    int		    i, i1, i2;
410
411    for (i = 0; i < PRI_END; i++)
412	value[i] = 0.0;
413
414    i1 = 0;
415    i2 = 0;
416    while (i1 < pat->num && i2 < fnt->num)
417    {
418	FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
419	FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
420
421	i = FcObjectCompare(elt_i1->object, elt_i2->object);
422	if (i > 0)
423	    i2++;
424	else if (i < 0)
425	    i1++;
426	else
427	{
428	    const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
429	    if (!FcCompareValueList (elt_i1->object, match,
430				     FcPatternEltValues(elt_i1),
431				     FcPatternEltValues(elt_i2),
432				     NULL, value, NULL, result))
433		return FcFalse;
434	    i1++;
435	    i2++;
436	}
437    }
438    return FcTrue;
439}
440
441FcPattern *
442FcFontRenderPrepare (FcConfig	    *config,
443		     FcPattern	    *pat,
444		     FcPattern	    *font)
445{
446    FcPattern	    *new;
447    int		    i;
448    FcPatternElt    *fe, *pe, *fel, *pel;
449    FcValue	    v;
450    FcResult	    result;
451
452    assert (pat != NULL);
453    assert (font != NULL);
454
455    new = FcPatternCreate ();
456    if (!new)
457	return NULL;
458    for (i = 0; i < font->num; i++)
459    {
460	fe = &FcPatternElts(font)[i];
461	if (fe->object == FC_FAMILYLANG_OBJECT ||
462	    fe->object == FC_STYLELANG_OBJECT ||
463	    fe->object == FC_FULLNAMELANG_OBJECT)
464	{
465	    /* ignore those objects. we need to deal with them
466	     * another way */
467	    continue;
468	}
469	if (fe->object == FC_FAMILY_OBJECT ||
470	    fe->object == FC_STYLE_OBJECT ||
471	    fe->object == FC_FULLNAME_OBJECT)
472	{
473	    FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
474	    FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
475	    FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
476
477	    fel = FcPatternObjectFindElt (font, fe->object + 1);
478	    pel = FcPatternObjectFindElt (pat, fe->object + 1);
479	}
480	else
481	{
482	    fel = NULL;
483	    pel = NULL;
484	}
485	pe = FcPatternObjectFindElt (pat, fe->object);
486	if (pe)
487	{
488	    const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
489
490	    if (!FcCompareValueList (pe->object, match,
491				     FcPatternEltValues(pe),
492				     FcPatternEltValues(fe), &v, NULL, NULL, &result))
493	    {
494		FcPatternDestroy (new);
495		return NULL;
496	    }
497	    if (fel && pel)
498	    {
499		int n = 1, j;
500		FcValueListPtr l1, l2, ln = NULL, ll = NULL;
501
502		match = FcObjectToMatcher (pel->object, FcTrue);
503		if (!FcCompareValueList (pel->object, match,
504					 FcPatternEltValues (pel),
505					 FcPatternEltValues (fel), NULL, NULL, &n, &result))
506		{
507		    FcPatternDestroy (new);
508		    return NULL;
509		}
510
511		for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
512		     l1 != NULL || l2 != NULL;
513		     j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
514		{
515		    if (j == n)
516		    {
517			if (l1)
518			    ln = FcValueListPrepend (ln,
519						     FcValueCanonicalize (&l1->value),
520						     FcValueBindingStrong);
521			if (l2)
522			    ll = FcValueListPrepend (ll,
523						     FcValueCanonicalize (&l2->value),
524						     FcValueBindingStrong);
525		    }
526		    else
527		    {
528			if (l1)
529			    ln = FcValueListAppend (ln,
530						    FcValueCanonicalize (&l1->value),
531						    FcValueBindingStrong);
532			if (l2)
533			    ll = FcValueListAppend (ll,
534						    FcValueCanonicalize (&l2->value),
535						    FcValueBindingStrong);
536		    }
537		}
538		FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
539		FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
540
541		continue;
542	    }
543	    else if (fel)
544	    {
545		FcValueListPtr l1, l2;
546
547	    copy_lang:
548		l1 = FcValueListDuplicate (FcPatternEltValues (fe));
549		l2 = FcValueListDuplicate (FcPatternEltValues (fel));
550		FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
551		FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
552
553		continue;
554	    }
555	}
556	else
557	{
558	    if (fel)
559		goto copy_lang;
560	    v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
561	}
562	FcPatternObjectAdd (new, fe->object, v, FcFalse);
563    }
564    for (i = 0; i < pat->num; i++)
565    {
566	pe = &FcPatternElts(pat)[i];
567	fe = FcPatternObjectFindElt (font, pe->object);
568	if (!fe &&
569	    pe->object != FC_FAMILYLANG_OBJECT &&
570	    pe->object != FC_STYLELANG_OBJECT &&
571	    pe->object != FC_FULLNAMELANG_OBJECT)
572	{
573	    FcPatternObjectListAdd (new, pe->object,
574				    FcValueListDuplicate (FcPatternEltValues(pe)),
575				    FcFalse);
576	}
577    }
578
579    FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
580    return new;
581}
582
583static FcPattern *
584FcFontSetMatchInternal (FcFontSet   **sets,
585			int	    nsets,
586			FcPattern   *p,
587			FcResult    *result)
588{
589    double    	    score[PRI_END], bestscore[PRI_END];
590    int		    f;
591    FcFontSet	    *s;
592    FcPattern	    *best;
593    int		    i;
594    int		    set;
595
596    for (i = 0; i < PRI_END; i++)
597	bestscore[i] = 0;
598    best = 0;
599    if (FcDebug () & FC_DBG_MATCH)
600    {
601	printf ("Match ");
602	FcPatternPrint (p);
603    }
604    for (set = 0; set < nsets; set++)
605    {
606	s = sets[set];
607	if (!s)
608	    continue;
609	for (f = 0; f < s->nfont; f++)
610	{
611	    if (FcDebug () & FC_DBG_MATCHV)
612	    {
613		printf ("Font %d ", f);
614		FcPatternPrint (s->fonts[f]);
615	    }
616	    if (!FcCompare (p, s->fonts[f], score, result))
617		return 0;
618	    if (FcDebug () & FC_DBG_MATCHV)
619	    {
620		printf ("Score");
621		for (i = 0; i < PRI_END; i++)
622		{
623		    printf (" %g", score[i]);
624		}
625		printf ("\n");
626	    }
627	    for (i = 0; i < PRI_END; i++)
628	    {
629		if (best && bestscore[i] < score[i])
630		    break;
631		if (!best || score[i] < bestscore[i])
632		{
633		    for (i = 0; i < PRI_END; i++)
634			bestscore[i] = score[i];
635		    best = s->fonts[f];
636		    break;
637		}
638	    }
639	}
640    }
641    if (FcDebug () & FC_DBG_MATCH)
642    {
643	printf ("Best score");
644	for (i = 0; i < PRI_END; i++)
645	    printf (" %g", bestscore[i]);
646	printf ("\n");
647	FcPatternPrint (best);
648    }
649    /* assuming that 'result' is initialized with FcResultNoMatch
650     * outside this function */
651    if (best)
652	*result = FcResultMatch;
653
654    return best;
655}
656
657FcPattern *
658FcFontSetMatch (FcConfig    *config,
659		FcFontSet   **sets,
660		int	    nsets,
661		FcPattern   *p,
662		FcResult    *result)
663{
664    FcPattern	    *best;
665
666    assert (sets != NULL);
667    assert (p != NULL);
668    assert (result != NULL);
669
670    *result = FcResultNoMatch;
671
672    if (!config)
673    {
674	config = FcConfigGetCurrent ();
675	if (!config)
676	    return 0;
677    }
678    best = FcFontSetMatchInternal (sets, nsets, p, result);
679    if (best)
680	return FcFontRenderPrepare (config, p, best);
681    else
682	return NULL;
683}
684
685FcPattern *
686FcFontMatch (FcConfig	*config,
687	     FcPattern	*p,
688	     FcResult	*result)
689{
690    FcFontSet	*sets[2];
691    int		nsets;
692    FcPattern   *best;
693
694    assert (p != NULL);
695    assert (result != NULL);
696
697    *result = FcResultNoMatch;
698
699    if (!config)
700    {
701	config = FcConfigGetCurrent ();
702	if (!config)
703	    return 0;
704    }
705    nsets = 0;
706    if (config->fonts[FcSetSystem])
707	sets[nsets++] = config->fonts[FcSetSystem];
708    if (config->fonts[FcSetApplication])
709	sets[nsets++] = config->fonts[FcSetApplication];
710
711    best = FcFontSetMatchInternal (sets, nsets, p, result);
712    if (best)
713	return FcFontRenderPrepare (config, p, best);
714    else
715	return NULL;
716}
717
718typedef struct _FcSortNode {
719    FcPattern	*pattern;
720    double	score[PRI_END];
721} FcSortNode;
722
723static int
724FcSortCompare (const void *aa, const void *ab)
725{
726    FcSortNode  *a = *(FcSortNode **) aa;
727    FcSortNode  *b = *(FcSortNode **) ab;
728    double	*as = &a->score[0];
729    double	*bs = &b->score[0];
730    double	ad = 0, bd = 0;
731    int         i;
732
733    i = PRI_END;
734    while (i-- && (ad = *as++) == (bd = *bs++))
735	;
736    return ad < bd ? -1 : ad > bd ? 1 : 0;
737}
738
739static FcBool
740FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
741{
742    FcBool ret = FcFalse;
743    FcCharSet *cs;
744
745    cs = 0;
746    if (trim || csp)
747    {
748	cs = FcCharSetCreate ();
749	if (cs == NULL)
750	    goto bail;
751    }
752
753    while (nnode--)
754    {
755	FcSortNode	*node = *n++;
756	FcBool		adds_chars = FcFalse;
757
758	/*
759	 * Only fetch node charset if we'd need it
760	 */
761	if (cs)
762	{
763	    FcCharSet	*ncs;
764
765	    if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
766		FcResultMatch)
767	        continue;
768
769	    if (!FcCharSetMerge (cs, ncs, &adds_chars))
770		goto bail;
771	}
772
773	/*
774	 * If this font isn't a subset of the previous fonts,
775	 * add it to the list
776	 */
777	if (!trim || adds_chars)
778	{
779	    FcPatternReference (node->pattern);
780	    if (FcDebug () & FC_DBG_MATCHV)
781	    {
782		printf ("Add ");
783		FcPatternPrint (node->pattern);
784	    }
785	    if (!FcFontSetAdd (fs, node->pattern))
786	    {
787		FcPatternDestroy (node->pattern);
788		goto bail;
789	    }
790	}
791    }
792    if (csp)
793    {
794	*csp = cs;
795	cs = 0;
796    }
797
798    ret = FcTrue;
799
800bail:
801    if (cs)
802	FcCharSetDestroy (cs);
803
804    return ret;
805}
806
807void
808FcFontSetSortDestroy (FcFontSet *fs)
809{
810    FcFontSetDestroy (fs);
811}
812
813FcFontSet *
814FcFontSetSort (FcConfig	    *config FC_UNUSED,
815	       FcFontSet    **sets,
816	       int	    nsets,
817	       FcPattern    *p,
818	       FcBool	    trim,
819	       FcCharSet    **csp,
820	       FcResult	    *result)
821{
822    FcFontSet	    *ret;
823    FcFontSet	    *s;
824    FcSortNode	    *nodes;
825    FcSortNode	    **nodeps, **nodep;
826    int		    nnodes;
827    FcSortNode	    *new;
828    int		    set;
829    int		    f;
830    int		    i;
831    int		    nPatternLang;
832    FcBool    	    *patternLangSat;
833    FcValue	    patternLang;
834
835    assert (sets != NULL);
836    assert (p != NULL);
837    assert (result != NULL);
838
839    /* There are some implementation that relying on the result of
840     * "result" to check if the return value of FcFontSetSort
841     * is valid or not.
842     * So we should initialize it to the conservative way since
843     * this function doesn't return NULL anymore.
844     */
845    if (result)
846	*result = FcResultNoMatch;
847
848    if (FcDebug () & FC_DBG_MATCH)
849    {
850	printf ("Sort ");
851	FcPatternPrint (p);
852    }
853    nnodes = 0;
854    for (set = 0; set < nsets; set++)
855    {
856	s = sets[set];
857	if (!s)
858	    continue;
859	nnodes += s->nfont;
860    }
861    if (!nnodes)
862	return FcFontSetCreate ();
863
864    for (nPatternLang = 0;
865	 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
866	 nPatternLang++)
867	;
868
869    /* freed below */
870    nodes = malloc (nnodes * sizeof (FcSortNode) +
871		    nnodes * sizeof (FcSortNode *) +
872		    nPatternLang * sizeof (FcBool));
873    if (!nodes)
874	goto bail0;
875    nodeps = (FcSortNode **) (nodes + nnodes);
876    patternLangSat = (FcBool *) (nodeps + nnodes);
877
878    new = nodes;
879    nodep = nodeps;
880    for (set = 0; set < nsets; set++)
881    {
882	s = sets[set];
883	if (!s)
884	    continue;
885	for (f = 0; f < s->nfont; f++)
886	{
887	    if (FcDebug () & FC_DBG_MATCHV)
888	    {
889		printf ("Font %d ", f);
890		FcPatternPrint (s->fonts[f]);
891	    }
892	    new->pattern = s->fonts[f];
893	    if (!FcCompare (p, new->pattern, new->score, result))
894		goto bail1;
895	    if (FcDebug () & FC_DBG_MATCHV)
896	    {
897		printf ("Score");
898		for (i = 0; i < PRI_END; i++)
899		{
900		    printf (" %g", new->score[i]);
901		}
902		printf ("\n");
903	    }
904	    *nodep = new;
905	    new++;
906	    nodep++;
907	}
908    }
909
910    nnodes = new - nodes;
911
912    qsort (nodeps, nnodes, sizeof (FcSortNode *),
913	   FcSortCompare);
914
915    for (i = 0; i < nPatternLang; i++)
916	patternLangSat[i] = FcFalse;
917
918    for (f = 0; f < nnodes; f++)
919    {
920	FcBool	satisfies = FcFalse;
921	/*
922	 * If this node matches any language, go check
923	 * which ones and satisfy those entries
924	 */
925	if (nodeps[f]->score[PRI_LANG] < 2000)
926	{
927	    for (i = 0; i < nPatternLang; i++)
928	    {
929		FcValue	    nodeLang;
930
931		if (!patternLangSat[i] &&
932		    FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
933		    FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
934		{
935		    double  compare = FcCompareLang (&patternLang, &nodeLang);
936		    if (compare >= 0 && compare < 2)
937		    {
938			if (FcDebug () & FC_DBG_MATCHV)
939			{
940			    FcChar8 *family;
941			    FcChar8 *style;
942
943			    if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
944				FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
945				printf ("Font %s:%s matches language %d\n", family, style, i);
946			}
947			patternLangSat[i] = FcTrue;
948			satisfies = FcTrue;
949			break;
950		    }
951		}
952	    }
953	}
954	if (!satisfies)
955	{
956	    nodeps[f]->score[PRI_LANG] = 10000.0;
957	}
958    }
959
960    /*
961     * Re-sort once the language issues have been settled
962     */
963    qsort (nodeps, nnodes, sizeof (FcSortNode *),
964	   FcSortCompare);
965
966    ret = FcFontSetCreate ();
967    if (!ret)
968	goto bail1;
969
970    if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
971	goto bail2;
972
973    free (nodes);
974
975    if (FcDebug() & FC_DBG_MATCH)
976    {
977	printf ("First font ");
978	FcPatternPrint (ret->fonts[0]);
979    }
980    if (ret->nfont > 0)
981	*result = FcResultMatch;
982
983    return ret;
984
985bail2:
986    FcFontSetDestroy (ret);
987bail1:
988    free (nodes);
989bail0:
990    return 0;
991}
992
993FcFontSet *
994FcFontSort (FcConfig	*config,
995	    FcPattern	*p,
996	    FcBool	trim,
997	    FcCharSet	**csp,
998	    FcResult	*result)
999{
1000    FcFontSet	*sets[2];
1001    int		nsets;
1002
1003    assert (p != NULL);
1004    assert (result != NULL);
1005
1006    *result = FcResultNoMatch;
1007
1008    if (!config)
1009    {
1010	config = FcConfigGetCurrent ();
1011	if (!config)
1012	    return 0;
1013    }
1014    nsets = 0;
1015    if (config->fonts[FcSetSystem])
1016	sets[nsets++] = config->fonts[FcSetSystem];
1017    if (config->fonts[FcSetApplication])
1018	sets[nsets++] = config->fonts[FcSetApplication];
1019    return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1020}
1021#define __fcmatch__
1022#include "fcaliastail.h"
1023#undef __fcmatch__
1024