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