fcmatch.c revision b2a52337 
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(FONTFORMAT),
251    PRI1(SCALABLE),
252    PRI1(FOUNDRY),
253    PRI1(CHARSET),
254    PRI_FAMILY_STRONG,
255    PRI_POSTSCRIPT_NAME_STRONG,
256    PRI1(LANG),
257    PRI_FAMILY_WEAK,
258    PRI_POSTSCRIPT_NAME_WEAK,
259    PRI1(SPACING),
260    PRI1(PIXEL_SIZE),
261    PRI1(STYLE),
262    PRI1(SLANT),
263    PRI1(WEIGHT),
264    PRI1(WIDTH),
265    PRI1(DECORATIVE),
266    PRI1(ANTIALIAS),
267    PRI1(RASTERIZER),
268    PRI1(OUTLINE),
269    PRI1(FONTVERSION),
270    PRI_END
271} FcMatcherPriority;
272
273#undef PRI1
274
275typedef struct _FcMatcher {
276    FcObject object;
277    double   (*compare) (FcValue *value1, FcValue *value2);
278    int      strong, weak;
279} FcMatcher;
280
281/*
282 * Order is significant, it defines the precedence of
283 * each value, earlier values are more significant than
284 * later values
285 */
286#define FC_OBJECT(NAME, Type, Cmp)	{ FC_##NAME##_OBJECT,	Cmp,	PRI_##NAME##_STRONG,	PRI_##NAME##_WEAK },
287static const FcMatcher _FcMatchers [] = {
288    { FC_INVALID_OBJECT, NULL, -1, -1 },
289#include "fcobjs.h"
290};
291#undef FC_OBJECT
292
293static const FcMatcher*
294FcObjectToMatcher (FcObject object,
295		   FcBool   include_lang)
296{
297    if (include_lang)
298    {
299	switch (object) {
300	case FC_FAMILYLANG_OBJECT:
301	case FC_STYLELANG_OBJECT:
302	case FC_FULLNAMELANG_OBJECT:
303	    object = FC_LANG_OBJECT;
304	    break;
305	}
306    }
307    if (object > FC_MAX_BASE_OBJECT ||
308	!_FcMatchers[object].compare ||
309	_FcMatchers[object].strong == -1 ||
310	_FcMatchers[object].weak == -1)
311	return NULL;
312
313    return _FcMatchers + object;
314}
315
316static FcBool
317FcCompareValueList (FcObject	     object,
318		    const FcMatcher *match,
319		    FcValueListPtr   v1orig,	/* pattern */
320		    FcValueListPtr   v2orig,	/* target */
321		    FcValue         *bestValue,
322		    double          *value,
323		    int             *n,
324		    FcResult        *result)
325{
326    FcValueListPtr  v1, v2;
327    double    	    v, best, bestStrong, bestWeak;
328    int		    j, k, pos = 0;
329
330    if (!match)
331    {
332	if (bestValue)
333	    *bestValue = FcValueCanonicalize(&v2orig->value);
334	if (n)
335	    *n = 0;
336	return FcTrue;
337    }
338
339    best = DBL_MAX;
340    bestStrong = DBL_MAX;
341    bestWeak = DBL_MAX;
342    j = 1;
343    for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
344    {
345	for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
346	{
347	    v = (match->compare) (&v1->value, &v2->value);
348	    if (v < 0)
349	    {
350		*result = FcResultTypeMismatch;
351		return FcFalse;
352	    }
353	    v = v * 1000 + j;
354	    if (v < best)
355	    {
356		if (bestValue)
357		    *bestValue = FcValueCanonicalize(&v2->value);
358		best = v;
359		pos = k;
360	    }
361	    if (v1->binding == FcValueBindingStrong)
362	    {
363		if (v < bestStrong)
364		    bestStrong = v;
365	    }
366	    else
367	    {
368		if (v < bestWeak)
369		    bestWeak = v;
370	    }
371	}
372	j++;
373    }
374    if (FcDebug () & FC_DBG_MATCHV)
375    {
376	printf (" %s: %g ", FcObjectName (object), best);
377	FcValueListPrint (v1orig);
378	printf (", ");
379	FcValueListPrint (v2orig);
380	printf ("\n");
381    }
382    if (value)
383    {
384	int weak    = match->weak;
385	int strong  = match->strong;
386	if (weak == strong)
387	    value[strong] += best;
388	else
389	{
390	    value[weak] += bestWeak;
391	    value[strong] += bestStrong;
392	}
393    }
394    if (n)
395	*n = pos;
396
397    return FcTrue;
398}
399
400/*
401 * Return a value indicating the distance between the two lists of
402 * values
403 */
404
405static FcBool
406FcCompare (FcPattern	*pat,
407	   FcPattern	*fnt,
408	   double	*value,
409	   FcResult	*result)
410{
411    int		    i, i1, i2;
412
413    for (i = 0; i < PRI_END; i++)
414	value[i] = 0.0;
415
416    i1 = 0;
417    i2 = 0;
418    while (i1 < pat->num && i2 < fnt->num)
419    {
420	FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
421	FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
422
423	i = FcObjectCompare(elt_i1->object, elt_i2->object);
424	if (i > 0)
425	    i2++;
426	else if (i < 0)
427	    i1++;
428	else
429	{
430	    const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
431	    if (!FcCompareValueList (elt_i1->object, match,
432				     FcPatternEltValues(elt_i1),
433				     FcPatternEltValues(elt_i2),
434				     NULL, value, NULL, result))
435		return FcFalse;
436	    i1++;
437	    i2++;
438	}
439    }
440    return FcTrue;
441}
442
443FcPattern *
444FcFontRenderPrepare (FcConfig	    *config,
445		     FcPattern	    *pat,
446		     FcPattern	    *font)
447{
448    FcPattern	    *new;
449    int		    i;
450    FcPatternElt    *fe, *pe, *fel, *pel;
451    FcValue	    v;
452    FcResult	    result;
453
454    assert (pat != NULL);
455    assert (font != NULL);
456
457    new = FcPatternCreate ();
458    if (!new)
459	return NULL;
460    for (i = 0; i < font->num; i++)
461    {
462	fe = &FcPatternElts(font)[i];
463	if (fe->object == FC_FAMILYLANG_OBJECT ||
464	    fe->object == FC_STYLELANG_OBJECT ||
465	    fe->object == FC_FULLNAMELANG_OBJECT)
466	{
467	    /* ignore those objects. we need to deal with them
468	     * another way */
469	    continue;
470	}
471	if (fe->object == FC_FAMILY_OBJECT ||
472	    fe->object == FC_STYLE_OBJECT ||
473	    fe->object == FC_FULLNAME_OBJECT)
474	{
475	    FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
476	    FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
477	    FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);
478
479	    fel = FcPatternObjectFindElt (font, fe->object + 1);
480	    pel = FcPatternObjectFindElt (pat, fe->object + 1);
481	}
482	else
483	{
484	    fel = NULL;
485	    pel = NULL;
486	}
487	pe = FcPatternObjectFindElt (pat, fe->object);
488	if (pe)
489	{
490	    const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
491
492	    if (!FcCompareValueList (pe->object, match,
493				     FcPatternEltValues(pe),
494				     FcPatternEltValues(fe), &v, NULL, NULL, &result))
495	    {
496		FcPatternDestroy (new);
497		return NULL;
498	    }
499	    if (fel && pel)
500	    {
501		int n = 1, j;
502		FcValueListPtr l1, l2, ln = NULL, ll = NULL;
503
504		match = FcObjectToMatcher (pel->object, FcTrue);
505		if (!FcCompareValueList (pel->object, match,
506					 FcPatternEltValues (pel),
507					 FcPatternEltValues (fel), NULL, NULL, &n, &result))
508		{
509		    FcPatternDestroy (new);
510		    return NULL;
511		}
512
513		for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
514		     l1 != NULL || l2 != NULL;
515		     j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
516		{
517		    if (j == n)
518		    {
519			if (l1)
520			    ln = FcValueListPrepend (ln,
521						     FcValueCanonicalize (&l1->value),
522						     FcValueBindingStrong);
523			if (l2)
524			    ll = FcValueListPrepend (ll,
525						     FcValueCanonicalize (&l2->value),
526						     FcValueBindingStrong);
527		    }
528		    else
529		    {
530			if (l1)
531			    ln = FcValueListAppend (ln,
532						    FcValueCanonicalize (&l1->value),
533						    FcValueBindingStrong);
534			if (l2)
535			    ll = FcValueListAppend (ll,
536						    FcValueCanonicalize (&l2->value),
537						    FcValueBindingStrong);
538		    }
539		}
540		FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
541		FcPatternObjectListAdd (new, fel->object, ll, FcFalse);
542
543		continue;
544	    }
545	    else if (fel)
546	    {
547		FcValueListPtr l1, l2;
548
549	    copy_lang:
550		l1 = FcValueListDuplicate (FcPatternEltValues (fe));
551		l2 = FcValueListDuplicate (FcPatternEltValues (fel));
552		FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
553		FcPatternObjectListAdd (new, fel->object, l2, FcFalse);
554
555		continue;
556	    }
557	    FcPatternObjectAdd (new, fe->object, v, FcFalse);
558	}
559	else
560	{
561	    if (fel)
562		goto copy_lang;
563	    FcPatternObjectListAdd (new, fe->object,
564				    FcValueListDuplicate (FcPatternEltValues (fe)),
565				    FcTrue);
566	}
567    }
568    for (i = 0; i < pat->num; i++)
569    {
570	pe = &FcPatternElts(pat)[i];
571	fe = FcPatternObjectFindElt (font, pe->object);
572	if (!fe &&
573	    pe->object != FC_FAMILYLANG_OBJECT &&
574	    pe->object != FC_STYLELANG_OBJECT &&
575	    pe->object != FC_FULLNAMELANG_OBJECT)
576	{
577	    FcPatternObjectListAdd (new, pe->object,
578				    FcValueListDuplicate (FcPatternEltValues(pe)),
579				    FcFalse);
580	}
581    }
582
583    FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
584    return new;
585}
586
587static FcPattern *
588FcFontSetMatchInternal (FcFontSet   **sets,
589			int	    nsets,
590			FcPattern   *p,
591			FcResult    *result)
592{
593    double    	    score[PRI_END], bestscore[PRI_END];
594    int		    f;
595    FcFontSet	    *s;
596    FcPattern	    *best;
597    int		    i;
598    int		    set;
599
600    for (i = 0; i < PRI_END; i++)
601	bestscore[i] = 0;
602    best = 0;
603    if (FcDebug () & FC_DBG_MATCH)
604    {
605	printf ("Match ");
606	FcPatternPrint (p);
607    }
608    for (set = 0; set < nsets; set++)
609    {
610	s = sets[set];
611	if (!s)
612	    continue;
613	for (f = 0; f < s->nfont; f++)
614	{
615	    if (FcDebug () & FC_DBG_MATCHV)
616	    {
617		printf ("Font %d ", f);
618		FcPatternPrint (s->fonts[f]);
619	    }
620	    if (!FcCompare (p, s->fonts[f], score, result))
621		return 0;
622	    if (FcDebug () & FC_DBG_MATCHV)
623	    {
624		printf ("Score");
625		for (i = 0; i < PRI_END; i++)
626		{
627		    printf (" %g", score[i]);
628		}
629		printf ("\n");
630	    }
631	    for (i = 0; i < PRI_END; i++)
632	    {
633		if (best && bestscore[i] < score[i])
634		    break;
635		if (!best || score[i] < bestscore[i])
636		{
637		    for (i = 0; i < PRI_END; i++)
638			bestscore[i] = score[i];
639		    best = s->fonts[f];
640		    break;
641		}
642	    }
643	}
644    }
645    if (FcDebug () & FC_DBG_MATCH)
646    {
647	printf ("Best score");
648	for (i = 0; i < PRI_END; i++)
649	    printf (" %g", bestscore[i]);
650	printf ("\n");
651	FcPatternPrint (best);
652    }
653    /* assuming that 'result' is initialized with FcResultNoMatch
654     * outside this function */
655    if (best)
656	*result = FcResultMatch;
657
658    return best;
659}
660
661FcPattern *
662FcFontSetMatch (FcConfig    *config,
663		FcFontSet   **sets,
664		int	    nsets,
665		FcPattern   *p,
666		FcResult    *result)
667{
668    FcPattern	    *best;
669
670    assert (sets != NULL);
671    assert (p != NULL);
672    assert (result != NULL);
673
674    *result = FcResultNoMatch;
675
676    if (!config)
677    {
678	config = FcConfigGetCurrent ();
679	if (!config)
680	    return 0;
681    }
682    best = FcFontSetMatchInternal (sets, nsets, p, result);
683    if (best)
684	return FcFontRenderPrepare (config, p, best);
685    else
686	return NULL;
687}
688
689FcPattern *
690FcFontMatch (FcConfig	*config,
691	     FcPattern	*p,
692	     FcResult	*result)
693{
694    FcFontSet	*sets[2];
695    int		nsets;
696    FcPattern   *best;
697
698    assert (p != NULL);
699    assert (result != NULL);
700
701    *result = FcResultNoMatch;
702
703    if (!config)
704    {
705	config = FcConfigGetCurrent ();
706	if (!config)
707	    return 0;
708    }
709    nsets = 0;
710    if (config->fonts[FcSetSystem])
711	sets[nsets++] = config->fonts[FcSetSystem];
712    if (config->fonts[FcSetApplication])
713	sets[nsets++] = config->fonts[FcSetApplication];
714
715    best = FcFontSetMatchInternal (sets, nsets, p, result);
716    if (best)
717	return FcFontRenderPrepare (config, p, best);
718    else
719	return NULL;
720}
721
722typedef struct _FcSortNode {
723    FcPattern	*pattern;
724    double	score[PRI_END];
725} FcSortNode;
726
727static int
728FcSortCompare (const void *aa, const void *ab)
729{
730    FcSortNode  *a = *(FcSortNode **) aa;
731    FcSortNode  *b = *(FcSortNode **) ab;
732    double	*as = &a->score[0];
733    double	*bs = &b->score[0];
734    double	ad = 0, bd = 0;
735    int         i;
736
737    i = PRI_END;
738    while (i-- && (ad = *as++) == (bd = *bs++))
739	;
740    return ad < bd ? -1 : ad > bd ? 1 : 0;
741}
742
743static FcBool
744FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
745{
746    FcBool ret = FcFalse;
747    FcCharSet *cs;
748    int i;
749
750    cs = 0;
751    if (trim || csp)
752    {
753	cs = FcCharSetCreate ();
754	if (cs == NULL)
755	    goto bail;
756    }
757
758    for (i = 0; i < nnode; i++)
759    {
760	FcSortNode	*node = *n++;
761	FcBool		adds_chars = FcFalse;
762
763	/*
764	 * Only fetch node charset if we'd need it
765	 */
766	if (cs)
767	{
768	    FcCharSet	*ncs;
769
770	    if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
771		FcResultMatch)
772	        continue;
773
774	    if (!FcCharSetMerge (cs, ncs, &adds_chars))
775		goto bail;
776	}
777
778	/*
779	 * If this font isn't a subset of the previous fonts,
780	 * add it to the list
781	 */
782	if (!i || !trim || adds_chars)
783	{
784	    FcPatternReference (node->pattern);
785	    if (FcDebug () & FC_DBG_MATCHV)
786	    {
787		printf ("Add ");
788		FcPatternPrint (node->pattern);
789	    }
790	    if (!FcFontSetAdd (fs, node->pattern))
791	    {
792		FcPatternDestroy (node->pattern);
793		goto bail;
794	    }
795	}
796    }
797    if (csp)
798    {
799	*csp = cs;
800	cs = 0;
801    }
802
803    ret = FcTrue;
804
805bail:
806    if (cs)
807	FcCharSetDestroy (cs);
808
809    return ret;
810}
811
812void
813FcFontSetSortDestroy (FcFontSet *fs)
814{
815    FcFontSetDestroy (fs);
816}
817
818FcFontSet *
819FcFontSetSort (FcConfig	    *config FC_UNUSED,
820	       FcFontSet    **sets,
821	       int	    nsets,
822	       FcPattern    *p,
823	       FcBool	    trim,
824	       FcCharSet    **csp,
825	       FcResult	    *result)
826{
827    FcFontSet	    *ret;
828    FcFontSet	    *s;
829    FcSortNode	    *nodes;
830    FcSortNode	    **nodeps, **nodep;
831    int		    nnodes;
832    FcSortNode	    *new;
833    int		    set;
834    int		    f;
835    int		    i;
836    int		    nPatternLang;
837    FcBool    	    *patternLangSat;
838    FcValue	    patternLang;
839
840    assert (sets != NULL);
841    assert (p != NULL);
842    assert (result != NULL);
843
844    /* There are some implementation that relying on the result of
845     * "result" to check if the return value of FcFontSetSort
846     * is valid or not.
847     * So we should initialize it to the conservative way since
848     * this function doesn't return NULL anymore.
849     */
850    if (result)
851	*result = FcResultNoMatch;
852
853    if (FcDebug () & FC_DBG_MATCH)
854    {
855	printf ("Sort ");
856	FcPatternPrint (p);
857    }
858    nnodes = 0;
859    for (set = 0; set < nsets; set++)
860    {
861	s = sets[set];
862	if (!s)
863	    continue;
864	nnodes += s->nfont;
865    }
866    if (!nnodes)
867	return FcFontSetCreate ();
868
869    for (nPatternLang = 0;
870	 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
871	 nPatternLang++)
872	;
873
874    /* freed below */
875    nodes = malloc (nnodes * sizeof (FcSortNode) +
876		    nnodes * sizeof (FcSortNode *) +
877		    nPatternLang * sizeof (FcBool));
878    if (!nodes)
879	goto bail0;
880    nodeps = (FcSortNode **) (nodes + nnodes);
881    patternLangSat = (FcBool *) (nodeps + nnodes);
882
883    new = nodes;
884    nodep = nodeps;
885    for (set = 0; set < nsets; set++)
886    {
887	s = sets[set];
888	if (!s)
889	    continue;
890	for (f = 0; f < s->nfont; f++)
891	{
892	    if (FcDebug () & FC_DBG_MATCHV)
893	    {
894		printf ("Font %d ", f);
895		FcPatternPrint (s->fonts[f]);
896	    }
897	    new->pattern = s->fonts[f];
898	    if (!FcCompare (p, new->pattern, new->score, result))
899		goto bail1;
900	    if (FcDebug () & FC_DBG_MATCHV)
901	    {
902		printf ("Score");
903		for (i = 0; i < PRI_END; i++)
904		{
905		    printf (" %g", new->score[i]);
906		}
907		printf ("\n");
908	    }
909	    *nodep = new;
910	    new++;
911	    nodep++;
912	}
913    }
914
915    nnodes = new - nodes;
916
917    qsort (nodeps, nnodes, sizeof (FcSortNode *),
918	   FcSortCompare);
919
920    for (i = 0; i < nPatternLang; i++)
921	patternLangSat[i] = FcFalse;
922
923    for (f = 0; f < nnodes; f++)
924    {
925	FcBool	satisfies = FcFalse;
926	/*
927	 * If this node matches any language, go check
928	 * which ones and satisfy those entries
929	 */
930	if (nodeps[f]->score[PRI_LANG] < 2000)
931	{
932	    for (i = 0; i < nPatternLang; i++)
933	    {
934		FcValue	    nodeLang;
935
936		if (!patternLangSat[i] &&
937		    FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
938		    FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
939		{
940		    double  compare = FcCompareLang (&patternLang, &nodeLang);
941		    if (compare >= 0 && compare < 2)
942		    {
943			if (FcDebug () & FC_DBG_MATCHV)
944			{
945			    FcChar8 *family;
946			    FcChar8 *style;
947
948			    if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
949				FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
950				printf ("Font %s:%s matches language %d\n", family, style, i);
951			}
952			patternLangSat[i] = FcTrue;
953			satisfies = FcTrue;
954			break;
955		    }
956		}
957	    }
958	}
959	if (!satisfies)
960	{
961	    nodeps[f]->score[PRI_LANG] = 10000.0;
962	}
963    }
964
965    /*
966     * Re-sort once the language issues have been settled
967     */
968    qsort (nodeps, nnodes, sizeof (FcSortNode *),
969	   FcSortCompare);
970
971    ret = FcFontSetCreate ();
972    if (!ret)
973	goto bail1;
974
975    if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
976	goto bail2;
977
978    free (nodes);
979
980    if (FcDebug() & FC_DBG_MATCH)
981    {
982	printf ("First font ");
983	FcPatternPrint (ret->fonts[0]);
984    }
985    if (ret->nfont > 0)
986	*result = FcResultMatch;
987
988    return ret;
989
990bail2:
991    FcFontSetDestroy (ret);
992bail1:
993    free (nodes);
994bail0:
995    return 0;
996}
997
998FcFontSet *
999FcFontSort (FcConfig	*config,
1000	    FcPattern	*p,
1001	    FcBool	trim,
1002	    FcCharSet	**csp,
1003	    FcResult	*result)
1004{
1005    FcFontSet	*sets[2];
1006    int		nsets;
1007
1008    assert (p != NULL);
1009    assert (result != NULL);
1010
1011    *result = FcResultNoMatch;
1012
1013    if (!config)
1014    {
1015	config = FcConfigGetCurrent ();
1016	if (!config)
1017	    return 0;
1018    }
1019    nsets = 0;
1020    if (config->fonts[FcSetSystem])
1021	sets[nsets++] = config->fonts[FcSetSystem];
1022    if (config->fonts[FcSetApplication])
1023	sets[nsets++] = config->fonts[FcSetApplication];
1024    return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1025}
1026#define __fcmatch__
1027#include "fcaliastail.h"
1028#undef __fcmatch__
1029