[fontconfig.git] / src / fcmatch.c

/*
 * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
 *
 * Copyright © 2000 Keith Packard
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Keith Packard not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  Keith Packard makes no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

#include "fcint.h"
#include <string.h>
#include <ctype.h>
#include <stdio.h>

static double
FcCompareNumber (FcValue *value1, FcValue *value2)
{
    double  v1, v2, v;
    
    switch (value1->type) {
    case FcTypeInteger:
	v1 = (double) value1->u.i;
	break;
    case FcTypeDouble:
	v1 = value1->u.d;
	break;
    default:
	return -1.0;
    }
    switch (value2->type) {
    case FcTypeInteger:
	v2 = (double) value2->u.i;
	break;
    case FcTypeDouble:
	v2 = value2->u.d;
	break;
    default:
	return -1.0;
    }
    v = v2 - v1;
    if (v < 0)
	v = -v;
    return v;
}

static double
FcCompareString (FcValue *v1, FcValue *v2)
{
    return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
}

static double
FcCompareFamily (FcValue *v1, FcValue *v2)
{
    /* rely on the guarantee in FcPatternAddWithBinding that
     * families are always FcTypeString. */
    const FcChar8* v1_string = fc_value_string(v1);
    const FcChar8* v2_string = fc_value_string(v2);

    if (FcToLower(*v1_string) != FcToLower(*v2_string))
       return 1.0;

    return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
}

static double
FcCompareLang (FcValue *v1, FcValue *v2)
{
    FcLangResult    result;
    FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
    
    switch (value1.type) {
    case FcTypeLangSet:
	switch (value2.type) {
	case FcTypeLangSet:
	    result = FcLangSetCompare (value1.u.l, value2.u.l);
	    break;
	case FcTypeString:
	    result = FcLangSetHasLang (value1.u.l, 
				       value2.u.s);
	    break;
	default:
	    return -1.0;
	}
	break;
    case FcTypeString:
	switch (value2.type) {
	case FcTypeLangSet:
	    result = FcLangSetHasLang (value2.u.l, value1.u.s);
	    break;
	case FcTypeString:
	    result = FcLangCompare (value1.u.s, 
				    value2.u.s);
	    break;
	default:
	    return -1.0;
	}
	break;
    default:
	return -1.0;
    }
    switch (result) {
    case FcLangEqual:
	return 0;
    case FcLangDifferentCountry:
	return 1;
    case FcLangDifferentLang:
    default:
	return 2;
    }
}

static double
FcCompareBool (FcValue *v1, FcValue *v2)
{
    if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
	return -1.0;
    return (double) v2->u.b != v1->u.b;
}

static double
FcCompareCharSet (FcValue *v1, FcValue *v2)
{
    return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
}

static double
FcCompareSize (FcValue *value1, FcValue *value2)
{
    double  v1, v2, v;

    switch (value1->type) {
    case FcTypeInteger:
	v1 = value1->u.i;
	break;
    case FcTypeDouble:
	v1 = value1->u.d;
	break;
    default:
	return -1;
    }
    switch (value2->type) {
    case FcTypeInteger:
	v2 = value2->u.i;
	break;
    case FcTypeDouble:
	v2 = value2->u.d;
	break;
    default:
	return -1;
    }
    if (v2 == 0)
	return 0;
    v = v2 - v1;
    if (v < 0)
	v = -v;
    return v;
}

typedef struct _FcMatcher {
    FcObject	    object;
    double	    (*compare) (FcValue *value1, FcValue *value2);
    int		    strong, weak;
} FcMatcher;

/*
 * Order is significant, it defines the precedence of
 * each value, earlier values are more significant than
 * later values
 */
static FcMatcher _FcMatchers [] = {
    { FC_FOUNDRY_OBJECT,	FcCompareString,	0, 0 },
#define MATCH_FOUNDRY	    0
#define MATCH_FOUNDRY_INDEX 0
    
    { FC_CHARSET_OBJECT,	FcCompareCharSet,	1, 1 },
#define MATCH_CHARSET	    1
#define MATCH_CHARSET_INDEX 1
    
    { FC_FAMILY_OBJECT,    	FcCompareFamily,	2, 4 },
#define MATCH_FAMILY	    2
#define MATCH_FAMILY_STRONG_INDEX   2
#define MATCH_FAMILY_WEAK_INDEX	    4
    
    { FC_LANG_OBJECT,		FcCompareLang,	3, 3 },
#define MATCH_LANG	    3
#define MATCH_LANG_INDEX    3
    
    { FC_SPACING_OBJECT,	FcCompareNumber,	5, 5 },
#define MATCH_SPACING	    4
#define MATCH_SPACING_INDEX 5
    
    { FC_PIXEL_SIZE_OBJECT,	FcCompareSize,	6, 6 },
#define MATCH_PIXEL_SIZE    5
#define MATCH_PIXEL_SIZE_INDEX	6
    
    { FC_STYLE_OBJECT,		FcCompareString,	7, 7 },
#define MATCH_STYLE	    6
#define MATCH_STYLE_INDEX   7
    
    { FC_SLANT_OBJECT,		FcCompareNumber,	8, 8 },
#define MATCH_SLANT	    7
#define MATCH_SLANT_INDEX   8
    
    { FC_WEIGHT_OBJECT,		FcCompareNumber,	9, 9 },
#define MATCH_WEIGHT	    8
#define MATCH_WEIGHT_INDEX  9
    
    { FC_WIDTH_OBJECT,		FcCompareNumber,	10, 10 },
#define MATCH_WIDTH	    9
#define MATCH_WIDTH_INDEX   10
    
    { FC_DECORATIVE_OBJECT,	FcCompareBool,		11, 11 },
#define MATCH_DECORATIVE	11
#define MATCH_DECORATIVE_INDEX	12

    { FC_ANTIALIAS_OBJECT,	FcCompareBool,		12, 12 },
    
#define MATCH_ANTIALIAS		    11
#define MATCH_ANTIALIAS_INDEX	    12
    
    { FC_RASTERIZER_OBJECT,	FcCompareString,	13, 13 },
#define MATCH_RASTERIZER	    12
#define MATCH_RASTERIZER_INDEX	    12

    { FC_OUTLINE_OBJECT,	FcCompareBool,		14, 14 },
#define MATCH_OUTLINE		    13
#define MATCH_OUTLINE_INDEX	    14

    { FC_FONTVERSION_OBJECT,	FcCompareNumber,	15, 15 },
#define MATCH_FONTVERSION	    14
#define MATCH_FONTVERSION_INDEX	    15
};

#define NUM_MATCH_VALUES    16

static FcMatcher*
FcObjectToMatcher (FcObject object)
{
    int 	i;

    i = -1;
    switch (object) {
    case FC_FOUNDRY_OBJECT:
	i = MATCH_FOUNDRY; break;
    case FC_FONTVERSION_OBJECT:
	i = MATCH_FONTVERSION; break;
    case FC_FAMILY_OBJECT:
	i = MATCH_FAMILY; break;
    case FC_CHARSET_OBJECT:
	i = MATCH_CHARSET; break;
    case FC_ANTIALIAS_OBJECT:
	i = MATCH_ANTIALIAS; break;
    case FC_LANG_OBJECT:
	i = MATCH_LANG; break;
    case FC_SPACING_OBJECT:
        i = MATCH_SPACING; break;
    case FC_STYLE_OBJECT:
        i = MATCH_STYLE; break;
    case FC_SLANT_OBJECT:
        i = MATCH_SLANT; break;
    case FC_PIXEL_SIZE_OBJECT:
	i = MATCH_PIXEL_SIZE; break;
    case FC_WIDTH_OBJECT:
        i = MATCH_WIDTH; break;
    case FC_WEIGHT_OBJECT:
        i = MATCH_WEIGHT; break;
    case FC_RASTERIZER_OBJECT:
	i = MATCH_RASTERIZER; break;
    case FC_OUTLINE_OBJECT:
	i = MATCH_OUTLINE; break;
    case FC_DECORATIVE_OBJECT:
	i = MATCH_DECORATIVE; break;
    }

    if (i < 0)
	return NULL;

    return _FcMatchers+i;
}

static FcBool
FcCompareValueList (FcObject	 object,
		    FcValueListPtr v1orig,	/* pattern */
		    FcValueListPtr v2orig,	/* target */
		    FcValue	*bestValue,
		    double	*value,
		    FcResult	*result)
{
    FcValueListPtr  v1, v2;
    double    	    v, best, bestStrong, bestWeak;
    int		    j;
    FcMatcher       *match = FcObjectToMatcher(object);

    if (!match)
    {
	if (bestValue)
	    *bestValue = FcValueCanonicalize(&v2orig->value);
	return FcTrue;
    }

    best = 1e99;
    bestStrong = 1e99;
    bestWeak = 1e99;
    j = 0;
    for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
    {
	for (v2 = v2orig; v2; v2 = FcValueListNext(v2))
	{
	    v = (match->compare) (&v1->value, &v2->value);
	    if (v < 0)
	    {
		*result = FcResultTypeMismatch;
		return FcFalse;
	    }
	    v = v * 100 + j;
	    if (v < best)
	    {
		if (bestValue)
		    *bestValue = FcValueCanonicalize(&v2->value);
		best = v;
	    }
	    if (v1->binding == FcValueBindingStrong)
	    {
		if (v < bestStrong)
		    bestStrong = v;
	    }
	    else
	    {
		if (v < bestWeak)
		    bestWeak = v;
	    }
	}
	j++;
    }
    if (FcDebug () & FC_DBG_MATCHV)
    {
	printf (" %s: %g ", FcObjectName (object), best);
	FcValueListPrint (v1orig);
	printf (", ");
	FcValueListPrint (v2orig);
	printf ("\n");
    }
    if (value)
    {
	int weak    = match->weak;
	int strong  = match->strong;
	if (weak == strong)
	    value[strong] += best;
	else
	{
	    value[weak] += bestWeak;
	    value[strong] += bestStrong;
	}
    }
    return FcTrue;
}

/*
 * Return a value indicating the distance between the two lists of
 * values
 */

static FcBool
FcCompare (FcPattern	*pat,
	   FcPattern	*fnt,
	   double	*value,
	   FcResult	*result)
{
    int		    i, i1, i2;
    
    for (i = 0; i < NUM_MATCH_VALUES; i++)
	value[i] = 0.0;
    
    i1 = 0;
    i2 = 0;
    while (i1 < pat->num && i2 < fnt->num)
    {
	FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
	FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];

	i = FcObjectCompare(elt_i1->object, elt_i2->object);
	if (i > 0)
	    i2++;
	else if (i < 0)
	    i1++;
	else
	{
	    if (!FcCompareValueList (elt_i1->object,
				     FcPatternEltValues(elt_i1),
				     FcPatternEltValues(elt_i2),
				     0, value, result))
		return FcFalse;
	    i1++;
	    i2++;
	}
    }
    return FcTrue;
}

FcPattern *
FcFontRenderPrepare (FcConfig	    *config,
		     FcPattern	    *pat,
		     FcPattern	    *font)
{
    FcPattern	    *new;
    int		    i;
    FcPatternElt    *fe, *pe;
    FcValue	    v;
    FcResult	    result;
    
    new = FcPatternCreate ();
    if (!new)
	return 0;
    for (i = 0; i < font->num; i++)
    {
	fe = &FcPatternElts(font)[i];
	pe = FcPatternObjectFindElt (pat, fe->object);
	if (pe)
	{
	    if (!FcCompareValueList (pe->object, FcPatternEltValues(pe), 
				     FcPatternEltValues(fe), &v, 0, &result))
	    {
		FcPatternDestroy (new);
		return 0;
	    }
	}
	else
	    v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
	FcPatternObjectAdd (new, fe->object, v, FcFalse);
    }
    for (i = 0; i < pat->num; i++)
    {
	pe = &FcPatternElts(pat)[i];
	fe = FcPatternObjectFindElt (font, pe->object);
	if (!fe)
	{
	    v = FcValueCanonicalize(&FcPatternEltValues(pe)->value);
	    FcPatternObjectAdd (new, pe->object, v, FcTrue);
	}
    }

    FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
    return new;
}

FcPattern *
FcFontSetMatch (FcConfig    *config,
		FcFontSet   **sets,
		int	    nsets,
		FcPattern   *p,
		FcResult    *result)
{
    double    	    score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
    int		    f;
    FcFontSet	    *s;
    FcPattern	    *best;
    int		    i;
    int		    set;

    for (i = 0; i < NUM_MATCH_VALUES; i++)
	bestscore[i] = 0;
    best = 0;
    if (FcDebug () & FC_DBG_MATCH)
    {
	printf ("Match ");
	FcPatternPrint (p);
    }
    if (!config)
    {
	config = FcConfigGetCurrent ();
	if (!config)
	    return 0;
    }
    for (set = 0; set < nsets; set++)
    {
	s = sets[set];
	if (!s)
	    continue;
	for (f = 0; f < s->nfont; f++)
	{
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
		printf ("Font %d ", f);
		FcPatternPrint (s->fonts[f]);
	    }
	    if (!FcCompare (p, s->fonts[f], score, result))
		return 0;
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
		printf ("Score");
		for (i = 0; i < NUM_MATCH_VALUES; i++)
		{
		    printf (" %g", score[i]);
		}
		printf ("\n");
	    }
	    for (i = 0; i < NUM_MATCH_VALUES; i++)
	    {
		if (best && bestscore[i] < score[i])
		    break;
		if (!best || score[i] < bestscore[i])
		{
		    for (i = 0; i < NUM_MATCH_VALUES; i++)
			bestscore[i] = score[i];
		    best = s->fonts[f];
		    break;
		}
	    }
	}
    }
    if (FcDebug () & FC_DBG_MATCH)
    {
	printf ("Best score");
	for (i = 0; i < NUM_MATCH_VALUES; i++)
	    printf (" %g", bestscore[i]);
	FcPatternPrint (best);
    }
    if (!best)
    {
	*result = FcResultNoMatch;
	return 0;
    }
    return FcFontRenderPrepare (config, p, best);
}

FcPattern *
FcFontMatch (FcConfig	*config,
	     FcPattern	*p, 
	     FcResult	*result)
{
    FcFontSet	*sets[2];
    int		nsets;

    if (!config)
    {
	config = FcConfigGetCurrent ();
	if (!config)
	    return 0;
    }
    nsets = 0;
    if (config->fonts[FcSetSystem])
	sets[nsets++] = config->fonts[FcSetSystem];
    if (config->fonts[FcSetApplication])
	sets[nsets++] = config->fonts[FcSetApplication];
    return FcFontSetMatch (config, sets, nsets, p, result);
}

typedef struct _FcSortNode {
    FcPattern	*pattern;
    double	score[NUM_MATCH_VALUES];
} FcSortNode;

static int
FcSortCompare (const void *aa, const void *ab)
{
    FcSortNode  *a = *(FcSortNode **) aa;
    FcSortNode  *b = *(FcSortNode **) ab;
    double	*as = &a->score[0];
    double	*bs = &b->score[0];
    double	ad = 0, bd = 0;
    int         i;

    i = NUM_MATCH_VALUES;
    while (i-- && (ad = *as++) == (bd = *bs++))
	;
    return ad < bd ? -1 : ad > bd ? 1 : 0;
}

static FcBool
FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
{
    FcCharSet	*ncs;
    FcSortNode	*node;

    while (nnode--)
    {
	node = *n++;
	if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) == 
	    FcResultMatch)
	{
	    /*
	     * If this font isn't a subset of the previous fonts,
	     * add it to the list
	     */
	    if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
	    {
                if (trim || build_cs)
                {
                    if (*cs)
                    {
                        ncs = FcCharSetUnion (ncs, *cs);
                        if (!ncs)
                            return FcFalse;
                        FcCharSetDestroy (*cs);
                    }
                    else
                        ncs = FcCharSetCopy (ncs);
                    *cs = ncs;
                }

		FcPatternReference (node->pattern);
		if (FcDebug () & FC_DBG_MATCHV)
		{
		    printf ("Add ");
		    FcPatternPrint (node->pattern);
		}
		if (!FcFontSetAdd (fs, node->pattern))
		{
		    FcPatternDestroy (node->pattern);
		    return FcFalse;
		}
	    }
	}
    }
    return FcTrue;
}

void
FcFontSetSortDestroy (FcFontSet *fs)
{
    FcFontSetDestroy (fs);
}

FcFontSet *
FcFontSetSort (FcConfig	    *config,
	       FcFontSet    **sets,
	       int	    nsets,
	       FcPattern    *p,
	       FcBool	    trim,
	       FcCharSet    **csp,
	       FcResult	    *result)
{
    FcFontSet	    *ret;
    FcFontSet	    *s;
    FcSortNode	    *nodes;
    FcSortNode	    **nodeps, **nodep;
    int		    nnodes;
    FcSortNode	    *new;
    FcCharSet	    *cs;
    int		    set;
    int		    f;
    int		    i;
    int		    nPatternLang;
    FcBool    	    *patternLangSat;
    FcValue	    patternLang;

    if (FcDebug () & FC_DBG_MATCH)
    {
	printf ("Sort ");
	FcPatternPrint (p);
    }
    nnodes = 0;
    for (set = 0; set < nsets; set++)
    {
	s = sets[set];
	if (!s)
	    continue;
	nnodes += s->nfont;
    }
    if (!nnodes)
	goto bail0;
    
    for (nPatternLang = 0;
	 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
	 nPatternLang++)
	;
	
    /* freed below */
    nodes = malloc (nnodes * sizeof (FcSortNode) + 
		    nnodes * sizeof (FcSortNode *) +
		    nPatternLang * sizeof (FcBool));
    if (!nodes)
	goto bail0;
    nodeps = (FcSortNode **) (nodes + nnodes);
    patternLangSat = (FcBool *) (nodeps + nnodes);
    
    new = nodes;
    nodep = nodeps;
    for (set = 0; set < nsets; set++)
    {
	s = sets[set];
	if (!s)
	    continue;
	for (f = 0; f < s->nfont; f++)
	{
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
		printf ("Font %d ", f);
		FcPatternPrint (s->fonts[f]);
	    }
	    new->pattern = s->fonts[f];
	    if (!FcCompare (p, new->pattern, new->score, result))
		goto bail1;
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
		printf ("Score");
		for (i = 0; i < NUM_MATCH_VALUES; i++)
		{
		    printf (" %g", new->score[i]);
		}
		printf ("\n");
	    }
	    *nodep = new;
	    new++;
	    nodep++;
	}
    }

    nnodes = new - nodes;
    
    qsort (nodeps, nnodes, sizeof (FcSortNode *),
	   FcSortCompare);
    
    for (i = 0; i < nPatternLang; i++)
	patternLangSat[i] = FcFalse;
    
    for (f = 0; f < nnodes; f++)
    {
	FcBool	satisfies = FcFalse;
	/*
	 * If this node matches any language, go check
	 * which ones and satisfy those entries
	 */
	if (nodeps[f]->score[MATCH_LANG_INDEX] < 200)
	{
	    for (i = 0; i < nPatternLang; i++)
	    {
		FcValue	    nodeLang;
		
		if (!patternLangSat[i] &&
		    FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
		    FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
		{
		    double  compare = FcCompareLang (&patternLang, &nodeLang);
		    if (compare >= 0 && compare < 2)
		    {
			if (FcDebug () & FC_DBG_MATCHV)
			{
			    FcChar8 *family;
			    FcChar8 *style;

			    if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
				FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
				printf ("Font %s:%s matches language %d\n", family, style, i);
			}
			patternLangSat[i] = FcTrue;
			satisfies = FcTrue;
			break;
		    }
		}
	    }
	}
	if (!satisfies)
	    nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
    }

    /*
     * Re-sort once the language issues have been settled
     */
    qsort (nodeps, nnodes, sizeof (FcSortNode *),
	   FcSortCompare);

    ret = FcFontSetCreate ();
    if (!ret)
	goto bail1;

    cs = 0;

    if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
	goto bail2;

    if (csp)
	*csp = cs;
    else
    {
        if (cs)
            FcCharSetDestroy (cs);
    }

    free (nodes);

    if (FcDebug() & FC_DBG_MATCH)
    {
	printf ("First font ");
	FcPatternPrint (ret->fonts[0]);
    }
    return ret;

bail2:
    if (cs)
	FcCharSetDestroy (cs);
    FcFontSetDestroy (ret);
bail1:
    free (nodes);
bail0:
    return 0;
}

FcFontSet *
FcFontSort (FcConfig	*config,
	    FcPattern	*p, 
	    FcBool	trim,
	    FcCharSet	**csp,
	    FcResult	*result)
{
    FcFontSet	*sets[2];
    int		nsets;

    if (!config)
    {
	config = FcConfigGetCurrent ();
	if (!config)
	    return 0;
    }
    nsets = 0;
    if (config->fonts[FcSetSystem])
	sets[nsets++] = config->fonts[FcSetSystem];
    if (config->fonts[FcSetApplication])
	sets[nsets++] = config->fonts[FcSetApplication];
    return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
}
#define __fcmatch__
#include "fcaliastail.h"
#undef __fcmatch__
Commit	Line	Data
	1	/*
	2	* $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
	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 Keith Packard not be used in
	11	* advertising or publicity pertaining to distribution of the software without
	12	* specific, written prior permission. Keith Packard makes 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	* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
	17	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
	18	* EVENT SHALL KEITH PACKARD 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 <string.h>
	27	#include <ctype.h>
	28	#include <stdio.h>
	29
	30	static double
	31	FcCompareNumber (FcValue value1, FcValue value2)
	32	{
	33	double v1, v2, v;
	34
	35	switch (value1->type) {
	36	case FcTypeInteger:
	37	v1 = (double) value1->u.i;
	38	break;
	39	case FcTypeDouble:
	40	v1 = value1->u.d;
	41	break;
	42	default:
	43	return -1.0;
	44	}
	45	switch (value2->type) {
	46	case FcTypeInteger:
	47	v2 = (double) value2->u.i;
	48	break;
	49	case FcTypeDouble:
	50	v2 = value2->u.d;
	51	break;
	52	default:
	53	return -1.0;
	54	}
	55	v = v2 - v1;
	56	if (v < 0)
	57	v = -v;
	58	return v;
	59	}
	60
	61	static double
	62	FcCompareString (FcValue v1, FcValue v2)
	63	{
	64	return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
	65	}
	66
	67	static double
	68	FcCompareFamily (FcValue v1, FcValue v2)
	69	{
	70	/* rely on the guarantee in FcPatternAddWithBinding that
	71	* families are always FcTypeString. */
	72	const FcChar8* v1_string = fc_value_string(v1);
	73	const FcChar8* v2_string = fc_value_string(v2);
	74
	75	if (FcToLower(v1_string) != FcToLower(v2_string))
	76	return 1.0;
	77
	78	return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
	79	}
	80
	81	static double
	82	FcCompareLang (FcValue v1, FcValue v2)
	83	{
	84	FcLangResult result;
	85	FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
	86
	87	switch (value1.type) {
	88	case FcTypeLangSet:
	89	switch (value2.type) {
	90	case FcTypeLangSet:
	91	result = FcLangSetCompare (value1.u.l, value2.u.l);
	92	break;
	93	case FcTypeString:
	94	result = FcLangSetHasLang (value1.u.l,
	95	value2.u.s);
	96	break;
	97	default:
	98	return -1.0;
	99	}
	100	break;
	101	case FcTypeString:
	102	switch (value2.type) {
	103	case FcTypeLangSet:
	104	result = FcLangSetHasLang (value2.u.l, value1.u.s);
	105	break;
	106	case FcTypeString:
	107	result = FcLangCompare (value1.u.s,
	108	value2.u.s);
	109	break;
	110	default:
	111	return -1.0;
	112	}
	113	break;
	114	default:
	115	return -1.0;
	116	}
	117	switch (result) {
	118	case FcLangEqual:
	119	return 0;
	120	case FcLangDifferentCountry:
	121	return 1;
	122	case FcLangDifferentLang:
	123	default:
	124	return 2;
	125	}
	126	}
	127
	128	static double
	129	FcCompareBool (FcValue v1, FcValue v2)
	130	{
	131	if (fc_storage_type(v2) != FcTypeBool \|\| fc_storage_type(v1) != FcTypeBool)
	132	return -1.0;
	133	return (double) v2->u.b != v1->u.b;
	134	}
	135
	136	static double
	137	FcCompareCharSet (FcValue v1, FcValue v2)
	138	{
	139	return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
	140	}
	141
	142	static double
	143	FcCompareSize (FcValue value1, FcValue value2)
	144	{
	145	double v1, v2, v;
	146
	147	switch (value1->type) {
	148	case FcTypeInteger:
	149	v1 = value1->u.i;
	150	break;
	151	case FcTypeDouble:
	152	v1 = value1->u.d;
	153	break;
	154	default:
	155	return -1;
	156	}
	157	switch (value2->type) {
	158	case FcTypeInteger:
	159	v2 = value2->u.i;
	160	break;
	161	case FcTypeDouble:
	162	v2 = value2->u.d;
	163	break;
	164	default:
	165	return -1;
	166	}
	167	if (v2 == 0)
	168	return 0;
	169	v = v2 - v1;
	170	if (v < 0)
	171	v = -v;
	172	return v;
	173	}
	174
	175	typedef struct _FcMatcher {
	176	FcObject object;
	177	double (compare) (FcValue value1, FcValue *value2);
	178	int strong, weak;
	179	} FcMatcher;
	180
	181	/*
	182	* Order is significant, it defines the precedence of
	183	* each value, earlier values are more significant than
	184	* later values
	185	*/
	186	static FcMatcher _FcMatchers [] = {
	187	{ FC_FOUNDRY_OBJECT, FcCompareString, 0, 0 },
	188	#define MATCH_FOUNDRY 0
	189	#define MATCH_FOUNDRY_INDEX 0
	190
	191	{ FC_CHARSET_OBJECT, FcCompareCharSet, 1, 1 },
	192	#define MATCH_CHARSET 1
	193	#define MATCH_CHARSET_INDEX 1
	194
	195	{ FC_FAMILY_OBJECT, FcCompareFamily, 2, 4 },
	196	#define MATCH_FAMILY 2
	197	#define MATCH_FAMILY_STRONG_INDEX 2
	198	#define MATCH_FAMILY_WEAK_INDEX 4
	199
	200	{ FC_LANG_OBJECT, FcCompareLang, 3, 3 },
	201	#define MATCH_LANG 3
	202	#define MATCH_LANG_INDEX 3
	203
	204	{ FC_SPACING_OBJECT, FcCompareNumber, 5, 5 },
	205	#define MATCH_SPACING 4
	206	#define MATCH_SPACING_INDEX 5
	207
	208	{ FC_PIXEL_SIZE_OBJECT, FcCompareSize, 6, 6 },
	209	#define MATCH_PIXEL_SIZE 5
	210	#define MATCH_PIXEL_SIZE_INDEX 6
	211
	212	{ FC_STYLE_OBJECT, FcCompareString, 7, 7 },
	213	#define MATCH_STYLE 6
	214	#define MATCH_STYLE_INDEX 7
	215
	216	{ FC_SLANT_OBJECT, FcCompareNumber, 8, 8 },
	217	#define MATCH_SLANT 7
	218	#define MATCH_SLANT_INDEX 8
	219
	220	{ FC_WEIGHT_OBJECT, FcCompareNumber, 9, 9 },
	221	#define MATCH_WEIGHT 8
	222	#define MATCH_WEIGHT_INDEX 9
	223
	224	{ FC_WIDTH_OBJECT, FcCompareNumber, 10, 10 },
	225	#define MATCH_WIDTH 9
	226	#define MATCH_WIDTH_INDEX 10
	227
	228	{ FC_DECORATIVE_OBJECT, FcCompareBool, 11, 11 },
	229	#define MATCH_DECORATIVE 11
	230	#define MATCH_DECORATIVE_INDEX 12
	231
	232	{ FC_ANTIALIAS_OBJECT, FcCompareBool, 12, 12 },
	233
	234	#define MATCH_ANTIALIAS 11
	235	#define MATCH_ANTIALIAS_INDEX 12
	236
	237	{ FC_RASTERIZER_OBJECT, FcCompareString, 13, 13 },
	238	#define MATCH_RASTERIZER 12
	239	#define MATCH_RASTERIZER_INDEX 12
	240
	241	{ FC_OUTLINE_OBJECT, FcCompareBool, 14, 14 },
	242	#define MATCH_OUTLINE 13
	243	#define MATCH_OUTLINE_INDEX 14
	244
	245	{ FC_FONTVERSION_OBJECT, FcCompareNumber, 15, 15 },
	246	#define MATCH_FONTVERSION 14
	247	#define MATCH_FONTVERSION_INDEX 15
	248	};
	249
	250	#define NUM_MATCH_VALUES 16
	251
	252	static FcMatcher*
	253	FcObjectToMatcher (FcObject object)
	254	{
	255	int i;
	256
	257	i = -1;
	258	switch (object) {
	259	case FC_FOUNDRY_OBJECT:
	260	i = MATCH_FOUNDRY; break;
	261	case FC_FONTVERSION_OBJECT:
	262	i = MATCH_FONTVERSION; break;
	263	case FC_FAMILY_OBJECT:
	264	i = MATCH_FAMILY; break;
	265	case FC_CHARSET_OBJECT:
	266	i = MATCH_CHARSET; break;
	267	case FC_ANTIALIAS_OBJECT:
	268	i = MATCH_ANTIALIAS; break;
	269	case FC_LANG_OBJECT:
	270	i = MATCH_LANG; break;
	271	case FC_SPACING_OBJECT:
	272	i = MATCH_SPACING; break;
	273	case FC_STYLE_OBJECT:
	274	i = MATCH_STYLE; break;
	275	case FC_SLANT_OBJECT:
	276	i = MATCH_SLANT; break;
	277	case FC_PIXEL_SIZE_OBJECT:
	278	i = MATCH_PIXEL_SIZE; break;
	279	case FC_WIDTH_OBJECT:
	280	i = MATCH_WIDTH; break;
	281	case FC_WEIGHT_OBJECT:
	282	i = MATCH_WEIGHT; break;
	283	case FC_RASTERIZER_OBJECT:
	284	i = MATCH_RASTERIZER; break;
	285	case FC_OUTLINE_OBJECT:
	286	i = MATCH_OUTLINE; break;
	287	case FC_DECORATIVE_OBJECT:
	288	i = MATCH_DECORATIVE; break;
	289	}
	290
	291	if (i < 0)
	292	return NULL;
	293
	294	return _FcMatchers+i;
	295	}
	296
	297	static FcBool
	298	FcCompareValueList (FcObject object,
	299	FcValueListPtr v1orig, /* pattern */
	300	FcValueListPtr v2orig, /* target */
	301	FcValue *bestValue,
	302	double *value,
	303	FcResult *result)
	304	{
	305	FcValueListPtr v1, v2;
	306	double v, best, bestStrong, bestWeak;
	307	int j;
	308	FcMatcher *match = FcObjectToMatcher(object);
	309
	310	if (!match)
	311	{
	312	if (bestValue)
	313	*bestValue = FcValueCanonicalize(&v2orig->value);
	314	return FcTrue;
	315	}
	316
	317	best = 1e99;
	318	bestStrong = 1e99;
	319	bestWeak = 1e99;
	320	j = 0;
	321	for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
	322	{
	323	for (v2 = v2orig; v2; v2 = FcValueListNext(v2))
	324	{
	325	v = (match->compare) (&v1->value, &v2->value);
	326	if (v < 0)
	327	{
	328	*result = FcResultTypeMismatch;
	329	return FcFalse;
	330	}
	331	v = v * 100 + j;
	332	if (v < best)
	333	{
	334	if (bestValue)
	335	*bestValue = FcValueCanonicalize(&v2->value);
	336	best = v;
	337	}
	338	if (v1->binding == FcValueBindingStrong)
	339	{
	340	if (v < bestStrong)
	341	bestStrong = v;
	342	}
	343	else
	344	{
	345	if (v < bestWeak)
	346	bestWeak = v;
	347	}
	348	}
	349	j++;
	350	}
	351	if (FcDebug () & FC_DBG_MATCHV)
	352	{
	353	printf (" %s: %g ", FcObjectName (object), best);
	354	FcValueListPrint (v1orig);
	355	printf (", ");
	356	FcValueListPrint (v2orig);
	357	printf ("\n");
	358	}
	359	if (value)
	360	{
	361	int weak = match->weak;
	362	int strong = match->strong;
	363	if (weak == strong)
	364	value[strong] += best;
	365	else
	366	{
	367	value[weak] += bestWeak;
	368	value[strong] += bestStrong;
	369	}
	370	}
	371	return FcTrue;
	372	}
	373
	374	/*
	375	* Return a value indicating the distance between the two lists of
	376	* values
	377	*/
	378
	379	static FcBool
	380	FcCompare (FcPattern *pat,
	381	FcPattern *fnt,
	382	double *value,
	383	FcResult *result)
	384	{
	385	int i, i1, i2;
	386
	387	for (i = 0; i < NUM_MATCH_VALUES; i++)
	388	value[i] = 0.0;
	389
	390	i1 = 0;
	391	i2 = 0;
	392	while (i1 < pat->num && i2 < fnt->num)
	393	{
	394	FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
	395	FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
	396
	397	i = FcObjectCompare(elt_i1->object, elt_i2->object);
	398	if (i > 0)
	399	i2++;
	400	else if (i < 0)
	401	i1++;
	402	else
	403	{
	404	if (!FcCompareValueList (elt_i1->object,
	405	FcPatternEltValues(elt_i1),
	406	FcPatternEltValues(elt_i2),
	407	0, value, result))
	408	return FcFalse;
	409	i1++;
	410	i2++;
	411	}
	412	}
	413	return FcTrue;
	414	}
	415
	416	FcPattern *
	417	FcFontRenderPrepare (FcConfig *config,
	418	FcPattern *pat,
	419	FcPattern *font)
	420	{
	421	FcPattern *new;
	422	int i;
	423	FcPatternElt fe, pe;
	424	FcValue v;
	425	FcResult result;
	426
	427	new = FcPatternCreate ();
	428	if (!new)
	429	return 0;
	430	for (i = 0; i < font->num; i++)
	431	{
	432	fe = &FcPatternElts(font)[i];
	433	pe = FcPatternObjectFindElt (pat, fe->object);
	434	if (pe)
	435	{
	436	if (!FcCompareValueList (pe->object, FcPatternEltValues(pe),
	437	FcPatternEltValues(fe), &v, 0, &result))
	438	{
	439	FcPatternDestroy (new);
	440	return 0;
	441	}
	442	}
	443	else
	444	v = FcValueCanonicalize(&FcPatternEltValues (fe)->value);
	445	FcPatternObjectAdd (new, fe->object, v, FcFalse);
	446	}
	447	for (i = 0; i < pat->num; i++)
	448	{
	449	pe = &FcPatternElts(pat)[i];
	450	fe = FcPatternObjectFindElt (font, pe->object);
	451	if (!fe)
	452	{
	453	v = FcValueCanonicalize(&FcPatternEltValues(pe)->value);
	454	FcPatternObjectAdd (new, pe->object, v, FcTrue);
	455	}
	456	}
	457
	458	FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
	459	return new;
	460	}
	461
	462	FcPattern *
	463	FcFontSetMatch (FcConfig *config,
	464	FcFontSet **sets,
	465	int nsets,
	466	FcPattern *p,
	467	FcResult *result)
	468	{
	469	double score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
	470	int f;
	471	FcFontSet *s;
	472	FcPattern *best;
	473	int i;
	474	int set;
	475
	476	for (i = 0; i < NUM_MATCH_VALUES; i++)
	477	bestscore[i] = 0;
	478	best = 0;
	479	if (FcDebug () & FC_DBG_MATCH)
	480	{
	481	printf ("Match ");
	482	FcPatternPrint (p);
	483	}
	484	if (!config)
	485	{
	486	config = FcConfigGetCurrent ();
	487	if (!config)
	488	return 0;
	489	}
	490	for (set = 0; set < nsets; set++)
	491	{
	492	s = sets[set];
	493	if (!s)
	494	continue;
	495	for (f = 0; f < s->nfont; f++)
	496	{
	497	if (FcDebug () & FC_DBG_MATCHV)
	498	{
	499	printf ("Font %d ", f);
	500	FcPatternPrint (s->fonts[f]);
	501	}
	502	if (!FcCompare (p, s->fonts[f], score, result))
	503	return 0;
	504	if (FcDebug () & FC_DBG_MATCHV)
	505	{
	506	printf ("Score");
	507	for (i = 0; i < NUM_MATCH_VALUES; i++)
	508	{
	509	printf (" %g", score[i]);
	510	}
	511	printf ("\n");
	512	}
	513	for (i = 0; i < NUM_MATCH_VALUES; i++)
	514	{
	515	if (best && bestscore[i] < score[i])
	516	break;
	517	if (!best \|\| score[i] < bestscore[i])
	518	{
	519	for (i = 0; i < NUM_MATCH_VALUES; i++)
	520	bestscore[i] = score[i];
	521	best = s->fonts[f];
	522	break;
	523	}
	524	}
	525	}
	526	}
	527	if (FcDebug () & FC_DBG_MATCH)
	528	{
	529	printf ("Best score");
	530	for (i = 0; i < NUM_MATCH_VALUES; i++)
	531	printf (" %g", bestscore[i]);
	532	FcPatternPrint (best);
	533	}
	534	if (!best)
	535	{
	536	*result = FcResultNoMatch;
	537	return 0;
	538	}
	539	return FcFontRenderPrepare (config, p, best);
	540	}
	541
	542	FcPattern *
	543	FcFontMatch (FcConfig *config,
	544	FcPattern *p,
	545	FcResult *result)
	546	{
	547	FcFontSet *sets[2];
	548	int nsets;
	549
	550	if (!config)
	551	{
	552	config = FcConfigGetCurrent ();
	553	if (!config)
	554	return 0;
	555	}
	556	nsets = 0;
	557	if (config->fonts[FcSetSystem])
	558	sets[nsets++] = config->fonts[FcSetSystem];
	559	if (config->fonts[FcSetApplication])
	560	sets[nsets++] = config->fonts[FcSetApplication];
	561	return FcFontSetMatch (config, sets, nsets, p, result);
	562	}
	563
	564	typedef struct _FcSortNode {
	565	FcPattern *pattern;
	566	double score[NUM_MATCH_VALUES];
	567	} FcSortNode;
	568
	569	static int
	570	FcSortCompare (const void aa, const void ab)
	571	{
	572	FcSortNode a = (FcSortNode **) aa;
	573	FcSortNode b = (FcSortNode **) ab;
	574	double *as = &a->score[0];
	575	double *bs = &b->score[0];
	576	double ad = 0, bd = 0;
	577	int i;
	578
	579	i = NUM_MATCH_VALUES;
	580	while (i-- && (ad = as++) == (bd = bs++))
	581	;
	582	return ad < bd ? -1 : ad > bd ? 1 : 0;
	583	}
	584
	585	static FcBool
	586	FcSortWalk (FcSortNode *n, int nnode, FcFontSet fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
	587	{
	588	FcCharSet *ncs;
	589	FcSortNode *node;
	590
	591	while (nnode--)
	592	{
	593	node = *n++;
	594	if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
	595	FcResultMatch)
	596	{
	597	/*
	598	* If this font isn't a subset of the previous fonts,
	599	* add it to the list
	600	*/
	601	if (!trim \|\| !cs \|\| !FcCharSetIsSubset (ncs, cs))
	602	{
	603	if (trim \|\| build_cs)
	604	{
	605	if (*cs)
	606	{
	607	ncs = FcCharSetUnion (ncs, *cs);
	608	if (!ncs)
	609	return FcFalse;
	610	FcCharSetDestroy (*cs);
	611	}
	612	else
	613	ncs = FcCharSetCopy (ncs);
	614	*cs = ncs;
	615	}
	616
	617	FcPatternReference (node->pattern);
	618	if (FcDebug () & FC_DBG_MATCHV)
	619	{
	620	printf ("Add ");
	621	FcPatternPrint (node->pattern);
	622	}
	623	if (!FcFontSetAdd (fs, node->pattern))
	624	{
	625	FcPatternDestroy (node->pattern);
	626	return FcFalse;
	627	}
	628	}
	629	}
	630	}
	631	return FcTrue;
	632	}
	633
	634	void
	635	FcFontSetSortDestroy (FcFontSet *fs)
	636	{
	637	FcFontSetDestroy (fs);
	638	}
	639
	640	FcFontSet *
	641	FcFontSetSort (FcConfig *config,
	642	FcFontSet **sets,
	643	int nsets,
	644	FcPattern *p,
	645	FcBool trim,
	646	FcCharSet **csp,
	647	FcResult *result)
	648	{
	649	FcFontSet *ret;
	650	FcFontSet *s;
	651	FcSortNode *nodes;
	652	FcSortNode nodeps, nodep;
	653	int nnodes;
	654	FcSortNode *new;
	655	FcCharSet *cs;
	656	int set;
	657	int f;
	658	int i;
	659	int nPatternLang;
	660	FcBool *patternLangSat;
	661	FcValue patternLang;
	662
	663	if (FcDebug () & FC_DBG_MATCH)
	664	{
	665	printf ("Sort ");
	666	FcPatternPrint (p);
	667	}
	668	nnodes = 0;
	669	for (set = 0; set < nsets; set++)
	670	{
	671	s = sets[set];
	672	if (!s)
	673	continue;
	674	nnodes += s->nfont;
	675	}
	676	if (!nnodes)
	677	goto bail0;
	678
	679	for (nPatternLang = 0;
	680	FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
	681	nPatternLang++)
	682	;
	683
	684	/* freed below */
	685	nodes = malloc (nnodes * sizeof (FcSortNode) +
	686	nnodes * sizeof (FcSortNode *) +
	687	nPatternLang * sizeof (FcBool));
	688	if (!nodes)
	689	goto bail0;
	690	nodeps = (FcSortNode **) (nodes + nnodes);
	691	patternLangSat = (FcBool *) (nodeps + nnodes);
	692
	693	new = nodes;
	694	nodep = nodeps;
	695	for (set = 0; set < nsets; set++)
	696	{
	697	s = sets[set];
	698	if (!s)
	699	continue;
	700	for (f = 0; f < s->nfont; f++)
	701	{
	702	if (FcDebug () & FC_DBG_MATCHV)
	703	{
	704	printf ("Font %d ", f);
	705	FcPatternPrint (s->fonts[f]);
	706	}
	707	new->pattern = s->fonts[f];
	708	if (!FcCompare (p, new->pattern, new->score, result))
	709	goto bail1;
	710	if (FcDebug () & FC_DBG_MATCHV)
	711	{
	712	printf ("Score");
	713	for (i = 0; i < NUM_MATCH_VALUES; i++)
	714	{
	715	printf (" %g", new->score[i]);
	716	}
	717	printf ("\n");
	718	}
	719	*nodep = new;
	720	new++;
	721	nodep++;
	722	}
	723	}
	724
	725	nnodes = new - nodes;
	726
	727	qsort (nodeps, nnodes, sizeof (FcSortNode *),
	728	FcSortCompare);
	729
	730	for (i = 0; i < nPatternLang; i++)
	731	patternLangSat[i] = FcFalse;
	732
	733	for (f = 0; f < nnodes; f++)
	734	{
	735	FcBool satisfies = FcFalse;
	736	/*
	737	* If this node matches any language, go check
	738	* which ones and satisfy those entries
	739	*/
	740	if (nodeps[f]->score[MATCH_LANG_INDEX] < 200)
	741	{
	742	for (i = 0; i < nPatternLang; i++)
	743	{
	744	FcValue nodeLang;
	745
	746	if (!patternLangSat[i] &&
	747	FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
	748	FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
	749	{
	750	double compare = FcCompareLang (&patternLang, &nodeLang);
	751	if (compare >= 0 && compare < 2)
	752	{
	753	if (FcDebug () & FC_DBG_MATCHV)
	754	{
	755	FcChar8 *family;
	756	FcChar8 *style;
	757
	758	if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
	759	FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
	760	printf ("Font %s:%s matches language %d\n", family, style, i);
	761	}
	762	patternLangSat[i] = FcTrue;
	763	satisfies = FcTrue;
	764	break;
	765	}
	766	}
	767	}
	768	}
	769	if (!satisfies)
	770	nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
	771	}
	772
	773	/*
	774	* Re-sort once the language issues have been settled
	775	*/
	776	qsort (nodeps, nnodes, sizeof (FcSortNode *),
	777	FcSortCompare);
	778
	779	ret = FcFontSetCreate ();
	780	if (!ret)
	781	goto bail1;
	782
	783	cs = 0;
	784
	785	if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
	786	goto bail2;
	787
	788	if (csp)
	789	*csp = cs;
	790	else
	791	{
	792	if (cs)
	793	FcCharSetDestroy (cs);
	794	}
	795
	796	free (nodes);
	797
	798	if (FcDebug() & FC_DBG_MATCH)
	799	{
	800	printf ("First font ");
	801	FcPatternPrint (ret->fonts[0]);
	802	}
	803	return ret;
	804
	805	bail2:
	806	if (cs)
	807	FcCharSetDestroy (cs);
	808	FcFontSetDestroy (ret);
	809	bail1:
	810	free (nodes);
	811	bail0:
	812	return 0;
	813	}
	814
	815	FcFontSet *
	816	FcFontSort (FcConfig *config,
	817	FcPattern *p,
	818	FcBool trim,
	819	FcCharSet **csp,
	820	FcResult *result)
	821	{
	822	FcFontSet *sets[2];
	823	int nsets;
	824
	825	if (!config)
	826	{
	827	config = FcConfigGetCurrent ();
	828	if (!config)
	829	return 0;
	830	}
	831	nsets = 0;
	832	if (config->fonts[FcSetSystem])
	833	sets[nsets++] = config->fonts[FcSetSystem];
	834	if (config->fonts[FcSetApplication])
	835	sets[nsets++] = config->fonts[FcSetApplication];
	836	return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
	837	}
	838	#define __fcmatch__
	839	#include "fcaliastail.h"
	840	#undef __fcmatch__