[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 <string.h>
#include <ctype.h>
#include "fcint.h"
#include <stdio.h>

static double
FcCompareNumber (char *object, 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 (double) v;
}

static double
FcCompareString (char *object, FcValue value1, FcValue value2)
{
    if (value2.type != FcTypeString || value1.type != FcTypeString)
	return -1.0;
    return (double) FcStrCmpIgnoreCase (value1.u.s, value2.u.s) != 0;
}

static double
FcCompareFamily (char *object, FcValue value1, FcValue value2)
{
    if (value2.type != FcTypeString || value1.type != FcTypeString)
	return -1.0;
    return (double) FcStrCmpIgnoreBlanksAndCase (value1.u.s, value2.u.s) != 0;
}

static double
FcCompareLang (char *object, FcValue value1, FcValue value2)
{
    FcLangResult    result;
    
    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 (char *object, FcValue value1, FcValue value2)
{
    if (value2.type != FcTypeBool || value1.type != FcTypeBool)
	return -1.0;
    return (double) value2.u.b != value1.u.b;
}

static double
FcCompareCharSet (char *object, FcValue value1, FcValue value2)
{
    if (value2.type != FcTypeCharSet || value1.type != FcTypeCharSet)
	return -1.0;
    return (double) FcCharSetSubtractCount (value1.u.c, value2.u.c);
}

static double
FcCompareSize (char *object, 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 {
    char	    *object;
    double	    (*compare) (char *object, 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,	FcCompareString,	0, 0 },
#define MATCH_FOUNDRY	    0
#define MATCH_FOUNDRY_INDEX 0
    
    { FC_CHARSET,	FcCompareCharSet,	1, 1 },
#define MATCH_CHARSET	    1
#define MATCH_CHARSET_INDEX 1
    
    { FC_FAMILY,    	FcCompareFamily,	2, 4 },
#define MATCH_FAMILY	    2
#define MATCH_FAMILY_STRONG_INDEX   2
#define MATCH_FAMILY_WEAK_INDEX	    4
    
    { FC_LANG,		FcCompareLang,		3, 3 },
#define MATCH_LANG	    3
#define MATCH_LANG_INDEX    3
    
    { FC_SPACING,	FcCompareNumber,	5, 5 },
#define MATCH_SPACING	    4
#define MATCH_SPACING_INDEX 5
    
    { FC_PIXEL_SIZE,	FcCompareSize,		6, 6 },
#define MATCH_PIXEL_SIZE    5
#define MATCH_PIXEL_SIZE_INDEX	6
    
    { FC_STYLE,		FcCompareString,	7, 7 },
#define MATCH_STYLE	    6
#define MATCH_STYLE_INDEX   7
    
    { FC_SLANT,		FcCompareNumber,	8, 8 },
#define MATCH_SLANT	    7
#define MATCH_SLANT_INDEX   8
    
    { FC_WEIGHT,	FcCompareNumber,	9, 9 },
#define MATCH_WEIGHT	    8
#define MATCH_WEIGHT_INDEX  9
    
    { FC_WIDTH,		FcCompareNumber,	10, 10 },
#define MATCH_WIDTH	    9
#define MATCH_WIDTH_INDEX   10
    
    { FC_ANTIALIAS,	FcCompareBool,		11, 11 },
#define MATCH_ANTIALIAS	    10
#define MATCH_ANTIALIAS_INDEX	    11
    
    { FC_RASTERIZER,	FcCompareString,	12, 12 },
#define MATCH_RASTERIZER    11
#define MATCH_RASTERIZER_INDEX    12

    { FC_OUTLINE,	FcCompareBool,		13, 13 },
#define MATCH_OUTLINE	    12
#define MATCH_OUTLINE_INDEX	    13

    { FC_FONTVERSION,	FcCompareNumber,	14, 14 },
#define MATCH_FONTVERSION   13
#define MATCH_FONTVERSION_INDEX   14
};

#define NUM_MATCH_VALUES    15

static FcBool
FcCompareValueList (const char  *object,
		    FcValueList	*v1orig,	/* pattern */
		    FcValueList *v2orig,	/* target */
		    FcValue	*bestValue,
		    double	*value,
		    FcResult	*result)
{
    FcValueList    *v1, *v2;
    double    	    v, best, bestStrong, bestWeak;
    int		    i;
    int		    j;
    
    /*
     * Locate the possible matching entry by examining the
     * first few characters in object
     */
    i = -1;
    switch (FcToLower (object[0])) {
    case 'f':
	switch (FcToLower (object[1])) {
	case 'o':
	    switch (FcToLower (object[2])) {
	    case 'u':
		i = MATCH_FOUNDRY; break;
	    case 'n':
		i = MATCH_FONTVERSION; break;
	    }
	    break;
	case 'a':
	    i = MATCH_FAMILY; break;
	}
	break;
    case 'c':
	i = MATCH_CHARSET; break;
    case 'a':
	i = MATCH_ANTIALIAS; break;
    case 'l':
	i = MATCH_LANG; break;
    case 's':
	switch (FcToLower (object[1])) {
	case 'p':
	    i = MATCH_SPACING; break;
	case 't':
	    i = MATCH_STYLE; break;
	case 'l':
	    i = MATCH_SLANT; break;
	}
	break;
    case 'p':
	i = MATCH_PIXEL_SIZE; break;
    case 'w':
	switch (FcToLower (object[1])) {
	case 'i':
	    i = MATCH_WIDTH; break;
	case 'e':
	    i = MATCH_WEIGHT; break;
	}
	break;
    case 'r':
	i = MATCH_RASTERIZER; break;
    case 'o':
	i = MATCH_OUTLINE; break;
    }
    if (i == -1 || 
	FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
			    (FcChar8 *) object) != 0)
    {
	if (bestValue)
	    *bestValue = v2orig->value;
	return FcTrue;
    }
#if 0
    for (i = 0; i < NUM_MATCHER; i++)
    {
	if (!FcStrCmpIgnoreCase ((FcChar8 *) _FcMatchers[i].object,
				 (FcChar8 *) object))
	    break;
    }
    if (i == NUM_MATCHER)
    {
	if (bestValue)
	    *bestValue = v2orig->value;
	return FcTrue;
    }
#endif
    best = 1e99;
    bestStrong = 1e99;
    bestWeak = 1e99;
    j = 0;
    for (v1 = v1orig; v1; v1 = v1->next)
    {
	for (v2 = v2orig; v2; v2 = v2->next)
	{
	    v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
					    v1->value,
					    v2->value);
	    if (v < 0)
	    {
		*result = FcResultTypeMismatch;
		return FcFalse;
	    }
	    if (FcDebug () & FC_DBG_MATCHV)
		printf (" v %g j %d ", v, j);
	    v = v * 100 + j;
	    if (v < best)
	    {
		if (bestValue)
		    *bestValue = 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 ", object, best);
	FcValueListPrint (v1orig);
	printf (", ");
	FcValueListPrint (v2orig);
	printf ("\n");
    }
    if (value)
    {
	int weak    = _FcMatchers[i].weak;
	int strong  = _FcMatchers[i].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)
    {
	i = strcmp (pat->elts[i1].object, fnt->elts[i2].object);
	if (i > 0)
	    i2++;
	else if (i < 0)
	    i1++;
	else
	{
	    if (!FcCompareValueList (pat->elts[i1].object,
				     pat->elts[i1].values,
				     fnt->elts[i2].values,
				     0,
				     value,
				     result))
		return FcFalse;
	    i1++;
	    i2++;
	}
    }
    return FcTrue;
#if 0
    for (i1 = 0; i1 < pat->num; i1++)
    {
	for (i2 = 0; i2 < fnt->num; i2++)
	{
	    if (!strcmp (pat->elts[i1].object, fnt->elts[i2].object))
	    {
		break;
	    }
	}
    }
    return FcTrue;
#endif
}

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 = &font->elts[i];
	pe = FcPatternFindElt (pat, fe->object);
	if (pe)
	{
	    if (!FcCompareValueList (pe->object, pe->values, 
				     fe->values, &v, 0, &result))
	    {
		FcPatternDestroy (new);
		return 0;
	    }
	}
	else
	    v = fe->values->value;
	FcPatternAdd (new, fe->object, v, FcFalse);
    }
    for (i = 0; i < pat->num; i++)
    {
	pe = &pat->elts[i];
	fe = FcPatternFindElt (font, pe->object);
	if (!fe)
	    FcPatternAdd (new, pe->object, pe->values->value, 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)
	{
	    *result = FcResultOutOfMemory;
	    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)
{
    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 (*cs)
		{
		    ncs = FcCharSetUnion (ncs, *cs);
		    if (!ncs)
			return FcFalse;
		    FcCharSetDestroy (*cs);
		}
		else
		    ncs = FcCharSetCopy (ncs);
		*cs = ncs;
		FcPatternReference (node->pattern);
		if (FcDebug () & FC_DBG_MATCH)
		{
		    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] < nPatternLang)
	{
	    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 (FC_LANG, 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))
	goto bail2;

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

    free (nodes);

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