fcmatch.c revision d91dd368 
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
749    cs = 0;
750    if (trim || csp)
751    {
752	cs = FcCharSetCreate ();
753	if (cs == NULL)
754	    goto bail;
755    }
756
757    while (nnode--)
758    {
759	FcSortNode	*node = *n++;
760	FcBool		adds_chars = FcFalse;
761
762	/*
763	 * Only fetch node charset if we'd need it
764	 */
765	if (cs)
766	{
767	    FcCharSet	*ncs;
768
769	    if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
770		FcResultMatch)
771	        continue;
772
773	    if (!FcCharSetMerge (cs, ncs, &adds_chars))
774		goto bail;
775	}
776
777	/*
778	 * If this font isn't a subset of the previous fonts,
779	 * add it to the list
780	 */
781	if (!trim || adds_chars)
782	{
783	    FcPatternReference (node->pattern);
784	    if (FcDebug () & FC_DBG_MATCHV)
785	    {
786		printf ("Add ");
787		FcPatternPrint (node->pattern);
788	    }
789	    if (!FcFontSetAdd (fs, node->pattern))
790	    {
791		FcPatternDestroy (node->pattern);
792		goto bail;
793	    }
794	}
795    }
796    if (csp)
797    {
798	*csp = cs;
799	cs = 0;
800    }
801
802    ret = FcTrue;
803
804bail:
805    if (cs)
806	FcCharSetDestroy (cs);
807
808    return ret;
809}
810
811void
812FcFontSetSortDestroy (FcFontSet *fs)
813{
814    FcFontSetDestroy (fs);
815}
816
817FcFontSet *
818FcFontSetSort (FcConfig	    *config FC_UNUSED,
819	       FcFontSet    **sets,
820	       int	    nsets,
821	       FcPattern    *p,
822	       FcBool	    trim,
823	       FcCharSet    **csp,
824	       FcResult	    *result)
825{
826    FcFontSet	    *ret;
827    FcFontSet	    *s;
828    FcSortNode	    *nodes;
829    FcSortNode	    **nodeps, **nodep;
830    int		    nnodes;
831    FcSortNode	    *new;
832    int		    set;
833    int		    f;
834    int		    i;
835    int		    nPatternLang;
836    FcBool    	    *patternLangSat;
837    FcValue	    patternLang;
838
839    assert (sets != NULL);
840    assert (p != NULL);
841    assert (result != NULL);
842
843    /* There are some implementation that relying on the result of
844     * "result" to check if the return value of FcFontSetSort
845     * is valid or not.
846     * So we should initialize it to the conservative way since
847     * this function doesn't return NULL anymore.
848     */
849    if (result)
850	*result = FcResultNoMatch;
851
852    if (FcDebug () & FC_DBG_MATCH)
853    {
854	printf ("Sort ");
855	FcPatternPrint (p);
856    }
857    nnodes = 0;
858    for (set = 0; set < nsets; set++)
859    {
860	s = sets[set];
861	if (!s)
862	    continue;
863	nnodes += s->nfont;
864    }
865    if (!nnodes)
866	return FcFontSetCreate ();
867
868    for (nPatternLang = 0;
869	 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
870	 nPatternLang++)
871	;
872
873    /* freed below */
874    nodes = malloc (nnodes * sizeof (FcSortNode) +
875		    nnodes * sizeof (FcSortNode *) +
876		    nPatternLang * sizeof (FcBool));
877    if (!nodes)
878	goto bail0;
879    nodeps = (FcSortNode **) (nodes + nnodes);
880    patternLangSat = (FcBool *) (nodeps + nnodes);
881
882    new = nodes;
883    nodep = nodeps;
884    for (set = 0; set < nsets; set++)
885    {
886	s = sets[set];
887	if (!s)
888	    continue;
889	for (f = 0; f < s->nfont; f++)
890	{
891	    if (FcDebug () & FC_DBG_MATCHV)
892	    {
893		printf ("Font %d ", f);
894		FcPatternPrint (s->fonts[f]);
895	    }
896	    new->pattern = s->fonts[f];
897	    if (!FcCompare (p, new->pattern, new->score, result))
898		goto bail1;
899	    if (FcDebug () & FC_DBG_MATCHV)
900	    {
901		printf ("Score");
902		for (i = 0; i < PRI_END; i++)
903		{
904		    printf (" %g", new->score[i]);
905		}
906		printf ("\n");
907	    }
908	    *nodep = new;
909	    new++;
910	    nodep++;
911	}
912    }
913
914    nnodes = new - nodes;
915
916    qsort (nodeps, nnodes, sizeof (FcSortNode *),
917	   FcSortCompare);
918
919    for (i = 0; i < nPatternLang; i++)
920	patternLangSat[i] = FcFalse;
921
922    for (f = 0; f < nnodes; f++)
923    {
924	FcBool	satisfies = FcFalse;
925	/*
926	 * If this node matches any language, go check
927	 * which ones and satisfy those entries
928	 */
929	if (nodeps[f]->score[PRI_LANG] < 2000)
930	{
931	    for (i = 0; i < nPatternLang; i++)
932	    {
933		FcValue	    nodeLang;
934
935		if (!patternLangSat[i] &&
936		    FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
937		    FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
938		{
939		    double  compare = FcCompareLang (&patternLang, &nodeLang);
940		    if (compare >= 0 && compare < 2)
941		    {
942			if (FcDebug () & FC_DBG_MATCHV)
943			{
944			    FcChar8 *family;
945			    FcChar8 *style;
946
947			    if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
948				FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
949				printf ("Font %s:%s matches language %d\n", family, style, i);
950			}
951			patternLangSat[i] = FcTrue;
952			satisfies = FcTrue;
953			break;
954		    }
955		}
956	    }
957	}
958	if (!satisfies)
959	{
960	    nodeps[f]->score[PRI_LANG] = 10000.0;
961	}
962    }
963
964    /*
965     * Re-sort once the language issues have been settled
966     */
967    qsort (nodeps, nnodes, sizeof (FcSortNode *),
968	   FcSortCompare);
969
970    ret = FcFontSetCreate ();
971    if (!ret)
972	goto bail1;
973
974    if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
975	goto bail2;
976
977    free (nodes);
978
979    if (FcDebug() & FC_DBG_MATCH)
980    {
981	printf ("First font ");
982	FcPatternPrint (ret->fonts[0]);
983    }
984    if (ret->nfont > 0)
985	*result = FcResultMatch;
986
987    return ret;
988
989bail2:
990    FcFontSetDestroy (ret);
991bail1:
992    free (nodes);
993bail0:
994    return 0;
995}
996
997FcFontSet *
998FcFontSort (FcConfig	*config,
999	    FcPattern	*p,
1000	    FcBool	trim,
1001	    FcCharSet	**csp,
1002	    FcResult	*result)
1003{
1004    FcFontSet	*sets[2];
1005    int		nsets;
1006
1007    assert (p != NULL);
1008    assert (result != NULL);
1009
1010    *result = FcResultNoMatch;
1011
1012    if (!config)
1013    {
1014	config = FcConfigGetCurrent ();
1015	if (!config)
1016	    return 0;
1017    }
1018    nsets = 0;
1019    if (config->fonts[FcSetSystem])
1020	sets[nsets++] = config->fonts[FcSetSystem];
1021    if (config->fonts[FcSetApplication])
1022	sets[nsets++] = config->fonts[FcSetApplication];
1023    return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1024}
1025#define __fcmatch__
1026#include "fcaliastail.h"
1027#undef __fcmatch__
1028