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