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