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