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