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