]> git.wh0rd.org - fontconfig.git/blobdiff - src/fcmatch.c
Stephan Kulow <coolo@suse.de> Michael Matz <matz@suse.de> reviewed by: plam
[fontconfig.git] / src / fcmatch.c
index 20c0861a890d84eb80b35328c4efab62e10f6b24..0af0c8367d68dd50f56a560d8f486e0940ea50cc 100644 (file)
@@ -1,7 +1,7 @@
 /*
- * $XFree86: xc/lib/fontconfig/src/fcmatch.c,v 1.18 2002/08/19 19:32:05 keithp Exp $
+ * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
  *
- * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
+ * 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
 #include <stdio.h>
 
 static double
-FcCompareInteger (char *object, FcValue value1, FcValue value2)
+FcCompareNumber (FcValue *value1, FcValue *value2)
 {
-    int        v;
+    double  v1, v2, v;
     
-    if (value2.type != FcTypeInteger || value1.type != FcTypeInteger)
+    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 = value2.u.i - value1.u.i;
+    }
+    v = v2 - v1;
     if (v < 0)
        v = -v;
-    return (double) v;
+    return v;
 }
 
 static double
-FcCompareString (char *object, FcValue value1, FcValue value2)
+FcCompareString (FcValue *v1, FcValue *v2)
 {
-    if (value2.type != FcTypeString || value1.type != FcTypeString)
-       return -1.0;
-    return (double) FcStrCmpIgnoreCase (value1.u.s, value2.u.s) != 0;
+    return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
 }
 
 static double
-FcCompareFamily (char *object, FcValue value1, FcValue value2)
+FcCompareFamily (FcValue *v1, FcValue *v2)
 {
-    if (value2.type != FcTypeString || value1.type != FcTypeString)
-       return -1.0;
-    return (double) FcStrCmpIgnoreBlanksAndCase (value1.u.s, value2.u.s) != 0;
+    /* 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 (char *object, FcValue value1, FcValue value2)
+FcCompareLang (FcValue *v1, FcValue *v2)
 {
     FcLangResult    result;
+    FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
     
     switch (value1.type) {
     case FcTypeLangSet:
@@ -68,7 +91,8 @@ FcCompareLang (char *object, FcValue value1, FcValue value2)
            result = FcLangSetCompare (value1.u.l, value2.u.l);
            break;
        case FcTypeString:
-           result = FcLangSetHasLang (value1.u.l, value2.u.s);
+           result = FcLangSetHasLang (value1.u.l, 
+                                      value2.u.s);
            break;
        default:
            return -1.0;
@@ -80,7 +104,8 @@ FcCompareLang (char *object, FcValue value1, FcValue value2)
            result = FcLangSetHasLang (value2.u.l, value1.u.s);
            break;
        case FcTypeString:
-           result = FcLangCompare (value1.u.s, value2.u.s);
+           result = FcLangCompare (value1.u.s, 
+                                   value2.u.s);
            break;
        default:
            return -1.0;
@@ -101,42 +126,40 @@ FcCompareLang (char *object, FcValue value1, FcValue value2)
 }
 
 static double
-FcCompareBool (char *object, FcValue value1, FcValue value2)
+FcCompareBool (FcValue *v1, FcValue *v2)
 {
-    if (value2.type != FcTypeBool || value1.type != FcTypeBool)
+    if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
        return -1.0;
-    return (double) value2.u.b != value1.u.b;
+    return (double) v2->u.b != v1->u.b;
 }
 
 static double
-FcCompareCharSet (char *object, FcValue value1, FcValue value2)
+FcCompareCharSet (FcValue *v1, FcValue *v2)
 {
-    if (value2.type != FcTypeCharSet || value1.type != FcTypeCharSet)
-       return -1.0;
-    return (double) FcCharSetSubtractCount (value1.u.c, value2.u.c);
+    return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
 }
 
 static double
-FcCompareSize (char *object, FcValue value1, FcValue value2)
+FcCompareSize (FcValue *value1, FcValue *value2)
 {
     double  v1, v2, v;
 
-    switch (value1.type) {
+    switch (value1->type) {
     case FcTypeInteger:
-       v1 = value1.u.i;
+       v1 = value1->u.i;
        break;
     case FcTypeDouble:
-       v1 = value1.u.d;
+       v1 = value1->u.d;
        break;
     default:
        return -1;
     }
-    switch (value2.type) {
+    switch (value2->type) {
     case FcTypeInteger:
-       v2 = value2.u.i;
+       v2 = value2->u.i;
        break;
     case FcTypeDouble:
-       v2 = value2.u.d;
+       v2 = value2->u.d;
        break;
     default:
        return -1;
@@ -150,8 +173,9 @@ FcCompareSize (char *object, FcValue value1, FcValue value2)
 }
 
 typedef struct _FcMatcher {
-    char           *object;
-    double         (*compare) (char *object, FcValue value1, FcValue value2);
+    const char     *object;
+    FcObjectPtr            objectPtr;
+    double         (*compare) (FcValue *value1, FcValue *value2);
     int                    strong, weak;
 } FcMatcher;
 
@@ -161,68 +185,106 @@ typedef struct _FcMatcher {
  * later values
  */
 static FcMatcher _FcMatchers [] = {
-    { FC_FOUNDRY,      FcCompareString,        0, 0 },
+    { FC_FOUNDRY,      0, FcCompareString,     0, 0 },
 #define MATCH_FOUNDRY      0
+#define MATCH_FOUNDRY_INDEX 0
     
-    { FC_CHARSET,      FcCompareCharSet,       1, 1 },
+    { FC_CHARSET,      0, FcCompareCharSet,    1, 1 },
 #define MATCH_CHARSET      1
+#define MATCH_CHARSET_INDEX 1
     
-    { FC_FAMILY,       FcCompareFamily,        2, 4 },
+    { FC_FAMILY,       0, FcCompareFamily,     2, 4 },
 #define MATCH_FAMILY       2
+#define MATCH_FAMILY_STRONG_INDEX   2
+#define MATCH_FAMILY_WEAK_INDEX            4
     
-    { FC_LANG,         FcCompareLang,          3, 3 },
+    { FC_LANG,         0, FcCompareLang,       3, 3 },
 #define MATCH_LANG         3
+#define MATCH_LANG_INDEX    3
     
-    { FC_SPACING,      FcCompareInteger,       5, 5 },
+    { FC_SPACING,      0, FcCompareNumber,     5, 5 },
 #define MATCH_SPACING      4
+#define MATCH_SPACING_INDEX 5
     
-    { FC_PIXEL_SIZE,   FcCompareSize,          6, 6 },
+    { FC_PIXEL_SIZE,   0, FcCompareSize,       6, 6 },
 #define MATCH_PIXEL_SIZE    5
+#define MATCH_PIXEL_SIZE_INDEX 6
     
-    { FC_STYLE,                FcCompareString,        7, 7 },
+    { FC_STYLE,                0, FcCompareString,     7, 7 },
 #define MATCH_STYLE        6
+#define MATCH_STYLE_INDEX   7
     
-    { FC_SLANT,                FcCompareInteger,       8, 8 },
+    { FC_SLANT,                0, FcCompareNumber,     8, 8 },
 #define MATCH_SLANT        7
+#define MATCH_SLANT_INDEX   8
     
-    { FC_WEIGHT,       FcCompareInteger,       9, 9 },
+    { FC_WEIGHT,       0, FcCompareNumber,     9, 9 },
 #define MATCH_WEIGHT       8
+#define MATCH_WEIGHT_INDEX  9
     
-    { FC_ANTIALIAS,    FcCompareBool,          10, 10 },
-#define MATCH_ANTIALIAS            9
+    { FC_WIDTH,                0, FcCompareNumber,     10, 10 },
+#define MATCH_WIDTH        9
+#define MATCH_WIDTH_INDEX   10
     
-    { FC_RASTERIZER,   FcCompareString,        11, 11 },
-#define MATCH_RASTERIZER    10
+    { FC_ANTIALIAS,    0, FcCompareBool,       11, 11 },
+#define MATCH_ANTIALIAS            10
+#define MATCH_ANTIALIAS_INDEX      11
     
-    { FC_OUTLINE,      FcCompareBool,          12, 12 },
-#define MATCH_OUTLINE      11
+    { FC_RASTERIZER,   0, FcCompareString,     12, 12 },
+#define MATCH_RASTERIZER    11
+#define MATCH_RASTERIZER_INDEX    12
+
+    { FC_OUTLINE,      0, FcCompareBool,       13, 13 },
+#define MATCH_OUTLINE      12
+#define MATCH_OUTLINE_INDEX        13
+
+    { FC_FONTVERSION,  0, FcCompareNumber,     14, 14 },
+#define MATCH_FONTVERSION   13
+#define MATCH_FONTVERSION_INDEX   14
 };
 
-#define NUM_MATCH_VALUES    13
+#define NUM_MATCH_VALUES    15
 
-static FcBool
-FcCompareValueList (const char  *object,
-                   FcValueList *v1orig,        /* pattern */
-                   FcValueList *v2orig,        /* target */
-                   FcValue     *bestValue,
-                   double      *value,
-                   FcResult    *result)
+static FcBool matchObjectPtrsInit = FcFalse;
+
+static void
+FcMatchObjectPtrsInit (void)
 {
-    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
-     */
+    _FcMatchers[MATCH_FOUNDRY].objectPtr = FcObjectToPtr(FC_FOUNDRY);
+    _FcMatchers[MATCH_CHARSET].objectPtr = FcObjectToPtr(FC_CHARSET);
+    _FcMatchers[MATCH_FAMILY].objectPtr = FcObjectToPtr(FC_FAMILY);
+    _FcMatchers[MATCH_LANG].objectPtr = FcObjectToPtr(FC_LANG);
+    _FcMatchers[MATCH_SPACING].objectPtr = FcObjectToPtr(FC_SPACING);
+    _FcMatchers[MATCH_PIXEL_SIZE].objectPtr = FcObjectToPtr(FC_PIXEL_SIZE);
+    _FcMatchers[MATCH_STYLE].objectPtr = FcObjectToPtr(FC_STYLE);
+    _FcMatchers[MATCH_SLANT].objectPtr = FcObjectToPtr(FC_SLANT);
+    _FcMatchers[MATCH_WEIGHT].objectPtr = FcObjectToPtr(FC_WEIGHT);
+    _FcMatchers[MATCH_WIDTH].objectPtr = FcObjectToPtr(FC_WIDTH);
+    _FcMatchers[MATCH_ANTIALIAS].objectPtr = FcObjectToPtr(FC_ANTIALIAS);
+    _FcMatchers[MATCH_RASTERIZER].objectPtr = FcObjectToPtr(FC_RASTERIZER);
+    _FcMatchers[MATCH_OUTLINE].objectPtr = FcObjectToPtr(FC_OUTLINE);
+    _FcMatchers[MATCH_FONTVERSION].objectPtr = FcObjectToPtr(FC_FONTVERSION);
+    matchObjectPtrsInit = FcTrue;
+}
+
+static FcMatcher*
+FcObjectPtrToMatcher (FcObjectPtr o)
+{
+    int        i;
+    const char  *object = FcObjectPtrU(o);
+
     i = -1;
-    switch (FcToLower (object[0])) {
+    switch (object[0]) {
     case 'f':
-       switch (FcToLower (object[1])) {
+       switch (object[1]) {
        case 'o':
-           i = MATCH_FOUNDRY; break;
+           switch (object[2]) {
+           case 'u':
+               i = MATCH_FOUNDRY; break;
+           case 'n':
+               i = MATCH_FONTVERSION; break;
+           }
+           break;
        case 'a':
            i = MATCH_FAMILY; break;
        }
@@ -234,7 +296,7 @@ FcCompareValueList (const char  *object,
     case 'l':
        i = MATCH_LANG; break;
     case 's':
-       switch (FcToLower (object[1])) {
+       switch (object[1]) {
        case 'p':
            i = MATCH_SPACING; break;
        case 't':
@@ -246,60 +308,77 @@ FcCompareValueList (const char  *object,
     case 'p':
        i = MATCH_PIXEL_SIZE; break;
     case 'w':
-       i = MATCH_WEIGHT; break;
+       switch (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 (i < 0)
+       return 0;
+
+    if (!matchObjectPtrsInit)
+        FcMatchObjectPtrsInit();
+
+    if (o != _FcMatchers[i].objectPtr)
+       return 0;
+
+    return _FcMatchers+i;
+}
+
+static FcBool
+FcCompareValueList (FcObjectPtr o,
+                   FcValueListPtr v1orig,      /* pattern */
+                   FcValueListPtr v2orig,      /* target */
+                   FcValue     *bestValue,
+                   double      *value,
+                   FcResult    *result)
+{
+    FcValueListPtr  v1, v2;
+    FcValueList     *v1_ptrU, *v2_ptrU;
+    double         v, best, bestStrong, bestWeak;
+    int                    j;
+    const char     *object = FcObjectPtrU(o);
+    FcMatcher       *match = FcObjectPtrToMatcher(o);
+
+    if (!match)
     {
        if (bestValue)
-           *bestValue = v2orig->value;
+           *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
        return FcTrue;
     }
-#endif
+
     best = 1e99;
     bestStrong = 1e99;
     bestWeak = 1e99;
     j = 0;
-    for (v1 = v1orig; v1; v1 = v1->next)
+    for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
+        v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1))
     {
-       for (v2 = v2orig; v2; v2 = v2->next)
+       for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); v2_ptrU;
+            v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
        {
-           v = (*_FcMatchers[i].compare) (_FcMatchers[i].object,
-                                           v1->value,
-                                           v2->value);
+           v = (match->compare) (&v1_ptrU->value, &v2_ptrU->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;
+                   *bestValue = FcValueCanonicalize(&v2_ptrU->value);
                best = v;
            }
-           if (v1->binding == FcValueBindingStrong)
+           if (v1_ptrU->binding == FcValueBindingStrong)
            {
                if (v < bestStrong)
                    bestStrong = v;
@@ -322,8 +401,8 @@ FcCompareValueList (const char  *object,
     }
     if (value)
     {
-       int weak    = _FcMatchers[i].weak;
-       int strong  = _FcMatchers[i].strong;
+       int weak    = match->weak;
+       int strong  = match->strong;
        if (weak == strong)
            value[strong] += best;
        else
@@ -355,38 +434,25 @@ FcCompare (FcPattern      *pat,
     i2 = 0;
     while (i1 < pat->num && i2 < fnt->num)
     {
-       i = strcmp (pat->elts[i1].object, fnt->elts[i2].object);
+       FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
+       FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
+
+       i = FcObjectPtrCompare(elt_i1->object, elt_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))
+           if (!FcCompareValueList (elt_i1->object,
+                                    elt_i1->values, elt_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 *
@@ -405,8 +471,8 @@ FcFontRenderPrepare (FcConfig           *config,
        return 0;
     for (i = 0; i < font->num; i++)
     {
-       fe = &font->elts[i];
-       pe = FcPatternFindElt (pat, fe->object);
+       fe = FcPatternEltU(font->elts)+i;
+       pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
        if (pe)
        {
            if (!FcCompareValueList (pe->object, pe->values, 
@@ -417,16 +483,21 @@ FcFontRenderPrepare (FcConfig         *config,
            }
        }
        else
-           v = fe->values->value;
-       FcPatternAdd (new, fe->object, v, FcFalse);
+           v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
+       FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
     }
     for (i = 0; i < pat->num; i++)
     {
-       pe = &pat->elts[i];
-       fe = FcPatternFindElt (font, pe->object);
+       pe = FcPatternEltU(pat->elts)+i;
+       fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
        if (!fe)
-           FcPatternAdd (new, pe->object, pe->values->value, FcTrue);
+           FcPatternAdd (new, FcObjectPtrU(pe->object), 
+                          FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
     }
+
+    if (FcPatternFindElt (font, FC_FILE))
+       FcPatternTransferFullFname (new, font);
+
     FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
     return new;
 }
@@ -438,15 +509,14 @@ FcFontSetMatch (FcConfig    *config,
                FcPattern   *p,
                FcResult    *result)
 {
-    double         score[NUM_MATCH_VALUES], bestscore[NUM_MATCH_VALUES];
+    double         score;
+    double         bestscore;
     int                    f;
     FcFontSet      *s;
     FcPattern      *best;
-    int                    i;
+    int                    scoring_index;
     int                    set;
 
-    for (i = 0; i < NUM_MATCH_VALUES; i++)
-       bestscore[i] = 0;
     best = 0;
     if (FcDebug () & FC_DBG_MATCH)
     {
@@ -457,51 +527,141 @@ FcFontSetMatch (FcConfig    *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");
+
+        char* matchBlocked = (char*)calloc(s->nfont, sizeof(FcBool));
+
+       /* The old algorithm checked if each font beat 'best', 
+        * scanning all of the value lists for all of the pattern elts. */
+       /* This algorithm checks each font on a element-by-element basis
+        * and blocks fonts that have already lost on some element from
+        * further consideration from being best.  Basically, we've
+        * swapped the order of loops and short-circuited fonts that
+        * are out of contention right away.
+        * This saves a lot of time! */
+        for (scoring_index = 0; scoring_index < NUM_MATCH_VALUES; 
+            scoring_index++)
+        {
+            int            pat_elt;
+            FcPatternElt    *pat_elts = FcPatternEltU(p->elts);
+           FcMatcher       *match = 0;
+           FcValueListPtr  v1;
+            FcValueList     *v1_ptrU;
+            int            v1_offset = 0;
+
+
+            for (pat_elt = 0; pat_elt < p->num; pat_elt++) 
+            {
+                match = FcObjectPtrToMatcher
+                   ((FcPatternEltU(p->elts)+pat_elt)->object);
+
+               if (match && 
+                    (match->strong == scoring_index ||
+                    match->weak == scoring_index))
+                   break;
+               else
+                   match = 0;
            }
-           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 (!match)
+               continue;
+
+            bestscore = 1e99;
+
+            
+            for (v1 = pat_elts[pat_elt].values, v1_ptrU = FcValueListPtrU(v1); 
+                v1_ptrU;
+                 v1 = FcValueListPtrU(v1)->next, 
+                    v1_ptrU = FcValueListPtrU(v1), v1_offset++)
+            {
+
+               if (v1_ptrU->binding == FcValueBindingWeak
+                    && scoring_index != match->weak)
+                   continue;
+
+               for (f = 0; f < s->nfont; f++)
+               {
+                   int                 cand_elt;
+                   FcPatternElt        *cand_elts;
+
+                   if (matchBlocked[f])
+                       continue;
+
+                   score = 0.0;
+                   cand_elts = FcPatternEltU(s->fonts[f]->elts);
+                   
+                   /* Look for the appropriate element in this candidate
+                    * pattern 'f' and evaluate its score wrt 'p'. */
+                   for (cand_elt = 0; cand_elt < s->fonts[f]->num; cand_elt++)
+                   {
+                       if (cand_elts[cand_elt].object == 
+                               pat_elts[pat_elt].object)
+                        {
+                           FcValueListPtr  v2;
+                           FcValueList     *v2_ptrU;
+                           double          v2_best_score = 1e99;
+
+                           for (v2 = cand_elts[cand_elt].values, 
+                                    v2_ptrU = FcValueListPtrU(v2);
+                                FcValueListPtrU(v2);
+                                v2 = FcValueListPtrU(v2)->next)
+                           {
+                               double v = (match->compare) 
+                                   (&v1_ptrU->value, &v2_ptrU->value);
+
+                               if (v < 0)
+                               {
+                                   *result = FcResultTypeMismatch;
+                                   return 0;
+                               }
+                               /* I'm actually kind of surprised that
+                                * this isn't v + 100 * v1_offset. -PL */
+                               v = v * 100 + v1_offset;
+                               if (v < v2_best_score)
+                                   v2_best_score = v;
+                           }
+                           score += v2_best_score;
+                       }
+                   }
+
+                   /* If there's a previous champion, and current score
+                    * beats previous best score, on this element, then
+                    * knock out the previous champion and anything
+                    * else that we would have visited previous to f;
+                    * clearly anything previous to f would have been
+                    * less than f on this score. */
+                   if (!best || score < bestscore)
+                   {
+                       if (best) 
+                       {
+                           int b;
+                           for (b = 0; b < f; ++b)
+                               matchBlocked[b] = FcTrue;
+                       }
+
+                       bestscore = score;
+                       best = s->fonts[f];
+                   }
+
+                   /* If f loses, then it's out too. */
+                   if (best && score > bestscore)
+                       matchBlocked[f] = FcTrue;
+
+                   /* Otherwise, f is equal to best on this element.
+                    * Carry on to next pattern element. */
                }
-           }
-       }
-    }
-    if (FcDebug () & FC_DBG_MATCH)
-    {
-       printf ("Best score");
-       for (i = 0; i < NUM_MATCH_VALUES; i++)
-           printf (" %g", bestscore[i]);
-       FcPatternPrint (best);
+           }
+        }
+       free (matchBlocked);
     }
     if (!best)
     {
@@ -624,6 +784,9 @@ FcFontSetSort (FcConfig         *config,
     int                    set;
     int                    f;
     int                    i;
+    int                    nPatternLang;
+    FcBool         *patternLangSat;
+    FcValue        patternLang;
 
     if (FcDebug () & FC_DBG_MATCH)
     {
@@ -640,10 +803,20 @@ FcFontSetSort (FcConfig       *config,
     }
     if (!nnodes)
        goto bail0;
-    nodes = malloc (nnodes * sizeof (FcSortNode) + nnodes * sizeof (FcSortNode *));
+    
+    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;
@@ -681,6 +854,55 @@ FcFontSetSort (FcConfig        *config,
     
     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 (&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)