]> git.wh0rd.org - fontconfig.git/blame - src/fcmatch.c
Fix matching bug when multiple elements match; don't use the sum of all
[fontconfig.git] / src / fcmatch.c
CommitLineData
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
30static double
9ab79bdf 31FcCompareNumber (FcValue *value1, FcValue *value2)
24330d27 32{
2d39321f 33 double v1, v2, v;
24330d27 34
4262e0b3 35 switch (value1->type) {
2d39321f 36 case FcTypeInteger:
4262e0b3 37 v1 = (double) value1->u.i;
2d39321f
KP
38 break;
39 case FcTypeDouble:
4262e0b3 40 v1 = value1->u.d;
2d39321f
KP
41 break;
42 default:
24330d27 43 return -1.0;
2d39321f 44 }
4262e0b3 45 switch (value2->type) {
2d39321f 46 case FcTypeInteger:
4262e0b3 47 v2 = (double) value2->u.i;
2d39321f
KP
48 break;
49 case FcTypeDouble:
4262e0b3 50 v2 = value2->u.d;
2d39321f
KP
51 break;
52 default:
53 return -1.0;
54 }
55 v = v2 - v1;
24330d27
KP
56 if (v < 0)
57 v = -v;
4f8b266f 58 return v;
24330d27
KP
59}
60
61static double
9ab79bdf 62FcCompareString (FcValue *v1, FcValue *v2)
24330d27 63{
1c9fdcca 64 return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
24330d27
KP
65}
66
82f4243f 67static double
9ab79bdf 68FcCompareFamily (FcValue *v1, FcValue *v2)
82f4243f 69{
4f8b266f
PL
70 /* rely on the guarantee in FcPatternAddWithBinding that
71 * families are always FcTypeString. */
4f8b266f
PL
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;
82f4243f
KP
79}
80
81static double
9ab79bdf 82FcCompareLang (FcValue *v1, FcValue *v2)
82f4243f
KP
83{
84 FcLangResult result;
4262e0b3 85 FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
82f4243f 86
d8d73958
KP
87 switch (value1.type) {
88 case FcTypeLangSet:
89 switch (value2.type) {
90 case FcTypeLangSet:
4262e0b3 91 result = FcLangSetCompare (value1.u.l, value2.u.l);
d8d73958
KP
92 break;
93 case FcTypeString:
4262e0b3
PL
94 result = FcLangSetHasLang (value1.u.l,
95 value2.u.s);
d8d73958
KP
96 break;
97 default:
98 return -1.0;
99 }
100 break;
101 case FcTypeString:
102 switch (value2.type) {
103 case FcTypeLangSet:
4262e0b3 104 result = FcLangSetHasLang (value2.u.l, value1.u.s);
d8d73958
KP
105 break;
106 case FcTypeString:
4262e0b3
PL
107 result = FcLangCompare (value1.u.s,
108 value2.u.s);
d8d73958
KP
109 break;
110 default:
111 return -1.0;
112 }
113 break;
114 default:
82f4243f 115 return -1.0;
d8d73958 116 }
82f4243f
KP
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
24330d27 128static double
9ab79bdf 129FcCompareBool (FcValue *v1, FcValue *v2)
24330d27 130{
1c9fdcca 131 if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
24330d27 132 return -1.0;
1c9fdcca 133 return (double) v2->u.b != v1->u.b;
24330d27
KP
134}
135
136static double
9ab79bdf 137FcCompareCharSet (FcValue *v1, FcValue *v2)
24330d27 138{
1c9fdcca 139 return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
24330d27
KP
140}
141
142static double
9ab79bdf 143FcCompareSize (FcValue *value1, FcValue *value2)
24330d27
KP
144{
145 double v1, v2, v;
146
4262e0b3 147 switch (value1->type) {
24330d27 148 case FcTypeInteger:
4262e0b3 149 v1 = value1->u.i;
24330d27
KP
150 break;
151 case FcTypeDouble:
4262e0b3 152 v1 = value1->u.d;
24330d27
KP
153 break;
154 default:
155 return -1;
156 }
4262e0b3 157 switch (value2->type) {
24330d27 158 case FcTypeInteger:
4262e0b3 159 v2 = value2->u.i;
24330d27
KP
160 break;
161 case FcTypeDouble:
4262e0b3 162 v2 = value2->u.d;
24330d27
KP
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
4c003605 175typedef struct _FcMatcher {
67accef4 176 const char *object;
cbe1df81 177 FcObjectPtr objectPtr;
9ab79bdf 178 double (*compare) (FcValue *value1, FcValue *value2);
4c003605
KP
179 int strong, weak;
180} FcMatcher;
181
24330d27
KP
182/*
183 * Order is significant, it defines the precedence of
184 * each value, earlier values are more significant than
185 * later values
186 */
187static FcMatcher _FcMatchers [] = {
cbe1df81 188 { FC_FOUNDRY, 0, FcCompareString, 0, 0 },
4c003605 189#define MATCH_FOUNDRY 0
5cf8c536 190#define MATCH_FOUNDRY_INDEX 0
bc9469ba 191
cbe1df81 192 { FC_CHARSET, 0, FcCompareCharSet, 1, 1 },
4c003605 193#define MATCH_CHARSET 1
5cf8c536 194#define MATCH_CHARSET_INDEX 1
bc9469ba 195
cbe1df81 196 { FC_FAMILY, 0, FcCompareFamily, 2, 4 },
4c003605 197#define MATCH_FAMILY 2
5cf8c536
KP
198#define MATCH_FAMILY_STRONG_INDEX 2
199#define MATCH_FAMILY_WEAK_INDEX 4
bc9469ba 200
cbe1df81 201 { FC_LANG, 0, FcCompareLang, 3, 3 },
4c003605 202#define MATCH_LANG 3
5cf8c536 203#define MATCH_LANG_INDEX 3
bc9469ba 204
cbe1df81 205 { FC_SPACING, 0, FcCompareNumber, 5, 5 },
4c003605 206#define MATCH_SPACING 4
5cf8c536 207#define MATCH_SPACING_INDEX 5
bc9469ba 208
cbe1df81 209 { FC_PIXEL_SIZE, 0, FcCompareSize, 6, 6 },
4c003605 210#define MATCH_PIXEL_SIZE 5
5cf8c536 211#define MATCH_PIXEL_SIZE_INDEX 6
bc9469ba 212
cbe1df81 213 { FC_STYLE, 0, FcCompareString, 7, 7 },
4c003605 214#define MATCH_STYLE 6
5cf8c536 215#define MATCH_STYLE_INDEX 7
bc9469ba 216
cbe1df81 217 { FC_SLANT, 0, FcCompareNumber, 8, 8 },
4c003605 218#define MATCH_SLANT 7
5cf8c536 219#define MATCH_SLANT_INDEX 8
bc9469ba 220
cbe1df81 221 { FC_WEIGHT, 0, FcCompareNumber, 9, 9 },
4c003605 222#define MATCH_WEIGHT 8
5cf8c536 223#define MATCH_WEIGHT_INDEX 9
f534109f 224
cbe1df81 225 { FC_WIDTH, 0, FcCompareNumber, 10, 10 },
81fa16c3 226#define MATCH_WIDTH 9
5cf8c536 227#define MATCH_WIDTH_INDEX 10
bc9469ba 228
cbe1df81 229 { FC_ANTIALIAS, 0, FcCompareBool, 11, 11 },
81fa16c3 230#define MATCH_ANTIALIAS 10
5cf8c536 231#define MATCH_ANTIALIAS_INDEX 11
bc9469ba 232
cbe1df81 233 { FC_RASTERIZER, 0, FcCompareString, 12, 12 },
81fa16c3 234#define MATCH_RASTERIZER 11
5cf8c536
KP
235#define MATCH_RASTERIZER_INDEX 12
236
cbe1df81 237 { FC_OUTLINE, 0, FcCompareBool, 13, 13 },
81fa16c3 238#define MATCH_OUTLINE 12
5cf8c536 239#define MATCH_OUTLINE_INDEX 13
a342e87d 240
cbe1df81 241 { FC_FONTVERSION, 0, FcCompareNumber, 14, 14 },
81fa16c3 242#define MATCH_FONTVERSION 13
5cf8c536 243#define MATCH_FONTVERSION_INDEX 14
24330d27
KP
244};
245
81fa16c3 246#define NUM_MATCH_VALUES 15
24330d27 247
cbe1df81
PL
248static FcBool matchObjectPtrsInit = FcFalse;
249
250static void
251FcMatchObjectPtrsInit (void)
252{
253 _FcMatchers[MATCH_FOUNDRY].objectPtr = FcObjectToPtr(FC_FOUNDRY);
254 _FcMatchers[MATCH_CHARSET].objectPtr = FcObjectToPtr(FC_CHARSET);
255 _FcMatchers[MATCH_FAMILY].objectPtr = FcObjectToPtr(FC_FAMILY);
256 _FcMatchers[MATCH_LANG].objectPtr = FcObjectToPtr(FC_LANG);
257 _FcMatchers[MATCH_SPACING].objectPtr = FcObjectToPtr(FC_SPACING);
258 _FcMatchers[MATCH_PIXEL_SIZE].objectPtr = FcObjectToPtr(FC_PIXEL_SIZE);
259 _FcMatchers[MATCH_STYLE].objectPtr = FcObjectToPtr(FC_STYLE);
260 _FcMatchers[MATCH_SLANT].objectPtr = FcObjectToPtr(FC_SLANT);
261 _FcMatchers[MATCH_WEIGHT].objectPtr = FcObjectToPtr(FC_WEIGHT);
262 _FcMatchers[MATCH_WIDTH].objectPtr = FcObjectToPtr(FC_WIDTH);
263 _FcMatchers[MATCH_ANTIALIAS].objectPtr = FcObjectToPtr(FC_ANTIALIAS);
264 _FcMatchers[MATCH_RASTERIZER].objectPtr = FcObjectToPtr(FC_RASTERIZER);
265 _FcMatchers[MATCH_OUTLINE].objectPtr = FcObjectToPtr(FC_OUTLINE);
266 _FcMatchers[MATCH_FONTVERSION].objectPtr = FcObjectToPtr(FC_FONTVERSION);
267 matchObjectPtrsInit = FcTrue;
268}
269
aa472e5f
PL
270static FcMatcher*
271FcObjectPtrToMatcher (FcObjectPtr o)
24330d27 272{
aa472e5f
PL
273 int i;
274 const char *object = FcObjectPtrU(o);
d854eaf8 275
bc9469ba 276 i = -1;
d854eaf8 277 switch (object[0]) {
bc9469ba 278 case 'f':
d854eaf8 279 switch (object[1]) {
bc9469ba 280 case 'o':
d854eaf8 281 switch (object[2]) {
a342e87d
KP
282 case 'u':
283 i = MATCH_FOUNDRY; break;
284 case 'n':
285 i = MATCH_FONTVERSION; break;
286 }
287 break;
bc9469ba
KP
288 case 'a':
289 i = MATCH_FAMILY; break;
290 }
291 break;
292 case 'c':
293 i = MATCH_CHARSET; break;
294 case 'a':
295 i = MATCH_ANTIALIAS; break;
296 case 'l':
297 i = MATCH_LANG; break;
298 case 's':
d854eaf8 299 switch (object[1]) {
bc9469ba
KP
300 case 'p':
301 i = MATCH_SPACING; break;
302 case 't':
303 i = MATCH_STYLE; break;
304 case 'l':
305 i = MATCH_SLANT; break;
306 }
307 break;
308 case 'p':
309 i = MATCH_PIXEL_SIZE; break;
310 case 'w':
d854eaf8 311 switch (object[1]) {
81fa16c3
KP
312 case 'i':
313 i = MATCH_WIDTH; break;
314 case 'e':
315 i = MATCH_WEIGHT; break;
316 }
317 break;
bc9469ba
KP
318 case 'r':
319 i = MATCH_RASTERIZER; break;
320 case 'o':
321 i = MATCH_OUTLINE; break;
322 }
cbe1df81 323
aa472e5f
PL
324 if (i < 0)
325 return 0;
326
cbe1df81
PL
327 if (!matchObjectPtrsInit)
328 FcMatchObjectPtrsInit();
cbe1df81 329
aa472e5f
PL
330 if (o != _FcMatchers[i].objectPtr)
331 return 0;
332
333 return _FcMatchers+i;
334}
335
336static FcBool
337FcCompareValueList (FcObjectPtr o,
338 FcValueListPtr v1orig, /* pattern */
339 FcValueListPtr v2orig, /* target */
340 FcValue *bestValue,
341 double *value,
342 FcResult *result)
343{
344 FcValueListPtr v1, v2;
345 FcValueList *v1_ptrU, *v2_ptrU;
346 double v, best, bestStrong, bestWeak;
347 int j;
348 const char *object = FcObjectPtrU(o);
349 FcMatcher *match = FcObjectPtrToMatcher(o);
350
351 if (!match)
bc9469ba
KP
352 {
353 if (bestValue)
4262e0b3 354 *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
bc9469ba
KP
355 return FcTrue;
356 }
aa472e5f 357
24330d27 358 best = 1e99;
4c003605
KP
359 bestStrong = 1e99;
360 bestWeak = 1e99;
24330d27 361 j = 0;
adac22f2 362 for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
200a44fe 363 v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1))
24330d27 364 {
200a44fe
PL
365 for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); v2_ptrU;
366 v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
24330d27 367 {
aa472e5f 368 v = (match->compare) (&v1_ptrU->value, &v2_ptrU->value);
24330d27
KP
369 if (v < 0)
370 {
371 *result = FcResultTypeMismatch;
372 return FcFalse;
373 }
24330d27
KP
374 v = v * 100 + j;
375 if (v < best)
376 {
377 if (bestValue)
adac22f2 378 *bestValue = FcValueCanonicalize(&v2_ptrU->value);
24330d27
KP
379 best = v;
380 }
adac22f2 381 if (v1_ptrU->binding == FcValueBindingStrong)
4c003605
KP
382 {
383 if (v < bestStrong)
384 bestStrong = v;
385 }
386 else
387 {
388 if (v < bestWeak)
389 bestWeak = v;
390 }
24330d27
KP
391 }
392 j++;
393 }
394 if (FcDebug () & FC_DBG_MATCHV)
395 {
396 printf (" %s: %g ", object, best);
397 FcValueListPrint (v1orig);
398 printf (", ");
399 FcValueListPrint (v2orig);
400 printf ("\n");
401 }
d0f07b8d 402 if (value)
4c003605 403 {
aa472e5f
PL
404 int weak = match->weak;
405 int strong = match->strong;
4c003605
KP
406 if (weak == strong)
407 value[strong] += best;
408 else
409 {
410 value[weak] += bestWeak;
411 value[strong] += bestStrong;
412 }
413 }
24330d27
KP
414 return FcTrue;
415}
416
417/*
418 * Return a value indicating the distance between the two lists of
419 * values
420 */
421
422static FcBool
423FcCompare (FcPattern *pat,
424 FcPattern *fnt,
425 double *value,
426 FcResult *result)
427{
428 int i, i1, i2;
429
4c003605 430 for (i = 0; i < NUM_MATCH_VALUES; i++)
24330d27
KP
431 value[i] = 0.0;
432
bc9469ba
KP
433 i1 = 0;
434 i2 = 0;
435 while (i1 < pat->num && i2 < fnt->num)
24330d27 436 {
9ab79bdf
PL
437 FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
438 FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
439
440 i = FcObjectPtrCompare(elt_i1->object, elt_i2->object);
bc9469ba
KP
441 if (i > 0)
442 i2++;
443 else if (i < 0)
444 i1++;
445 else
24330d27 446 {
d854eaf8 447 if (!FcCompareValueList (elt_i1->object,
9ab79bdf
PL
448 elt_i1->values, elt_i2->values,
449 0, value, result))
bc9469ba
KP
450 return FcFalse;
451 i1++;
452 i2++;
24330d27 453 }
bc9469ba
KP
454 }
455 return FcTrue;
24330d27
KP
456}
457
216fac98
KP
458FcPattern *
459FcFontRenderPrepare (FcConfig *config,
460 FcPattern *pat,
461 FcPattern *font)
462{
463 FcPattern *new;
464 int i;
465 FcPatternElt *fe, *pe;
466 FcValue v;
216fac98
KP
467 FcResult result;
468
469 new = FcPatternCreate ();
470 if (!new)
471 return 0;
472 for (i = 0; i < font->num; i++)
473 {
cd2ec1a9
PL
474 fe = FcPatternEltU(font->elts)+i;
475 pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
216fac98
KP
476 if (pe)
477 {
d854eaf8 478 if (!FcCompareValueList (pe->object, pe->values,
938bc633 479 fe->values, &v, 0, &result))
216fac98
KP
480 {
481 FcPatternDestroy (new);
482 return 0;
483 }
484 }
485 else
4262e0b3 486 v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
cd2ec1a9 487 FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
216fac98
KP
488 }
489 for (i = 0; i < pat->num; i++)
490 {
cd2ec1a9
PL
491 pe = FcPatternEltU(pat->elts)+i;
492 fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
216fac98 493 if (!fe)
cd2ec1a9 494 FcPatternAdd (new, FcObjectPtrU(pe->object),
4262e0b3 495 FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
216fac98 496 }
793154ed
PL
497
498 if (FcPatternFindElt (font, FC_FILE))
499 FcPatternTransferFullFname (new, font);
500
fa244f3d 501 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
216fac98
KP
502 return new;
503}
504
24330d27 505FcPattern *
80c053b7
KP
506FcFontSetMatch (FcConfig *config,
507 FcFontSet **sets,
508 int nsets,
509 FcPattern *p,
510 FcResult *result)
24330d27 511{
aa472e5f
PL
512 double score;
513 double bestscore;
24330d27
KP
514 int f;
515 FcFontSet *s;
516 FcPattern *best;
aa472e5f 517 int scoring_index;
216fac98 518 int set;
24330d27 519
24330d27
KP
520 best = 0;
521 if (FcDebug () & FC_DBG_MATCH)
522 {
523 printf ("Match ");
524 FcPatternPrint (p);
525 }
526 if (!config)
527 {
528 config = FcConfigGetCurrent ();
529 if (!config)
ec0c740e
KP
530 {
531 *result = FcResultOutOfMemory;
24330d27 532 return 0;
ec0c740e 533 }
24330d27 534 }
80c053b7 535 for (set = 0; set < nsets; set++)
24330d27 536 {
1ed98a0c
PL
537 FcBool *matchBlocked;
538 int blockStart;
539
80c053b7 540 s = sets[set];
24330d27
KP
541 if (!s)
542 continue;
aa472e5f 543
1ed98a0c
PL
544 matchBlocked = (FcBool*)calloc(s->nfont, sizeof(FcBool));
545 blockStart = 0;
aa472e5f
PL
546
547 /* The old algorithm checked if each font beat 'best',
548 * scanning all of the value lists for all of the pattern elts. */
549 /* This algorithm checks each font on a element-by-element basis
550 * and blocks fonts that have already lost on some element from
551 * further consideration from being best. Basically, we've
552 * swapped the order of loops and short-circuited fonts that
553 * are out of contention right away.
554 * This saves a lot of time! */
555 for (scoring_index = 0; scoring_index < NUM_MATCH_VALUES;
556 scoring_index++)
557 {
558 int pat_elt;
559 FcPatternElt *pat_elts = FcPatternEltU(p->elts);
560 FcMatcher *match = 0;
561 FcValueListPtr v1;
562 FcValueList *v1_ptrU;
563 int v1_offset = 0;
564
565
566 for (pat_elt = 0; pat_elt < p->num; pat_elt++)
567 {
568 match = FcObjectPtrToMatcher
569 ((FcPatternEltU(p->elts)+pat_elt)->object);
570
571 if (match &&
572 (match->strong == scoring_index ||
573 match->weak == scoring_index))
574 break;
575 else
576 match = 0;
24330d27 577 }
aa472e5f
PL
578
579 if (!match)
580 continue;
581
aa472e5f
PL
582 for (v1 = pat_elts[pat_elt].values, v1_ptrU = FcValueListPtrU(v1);
583 v1_ptrU;
584 v1 = FcValueListPtrU(v1)->next,
585 v1_ptrU = FcValueListPtrU(v1), v1_offset++)
586 {
1ed98a0c 587 if ((v1_ptrU->binding == FcValueBindingWeak
aa472e5f 588 && scoring_index != match->weak)
1ed98a0c
PL
589 || (v1_ptrU->binding == FcValueBindingStrong
590 && scoring_index != match->strong)
591 )
aa472e5f
PL
592 continue;
593
1ed98a0c
PL
594 bestscore = 1e99;
595
596 if (FcDebug () & FC_DBG_MATCHV)
597 {
598 int blocked_fonts = 0;
599 for (f = 0; f < s->nfont; f++)
600 blocked_fonts += matchBlocked[f] ? 1 : 0;
601 printf("Scoring Index %d, Value %d: %d(%d) fonts left\n",
602 scoring_index, v1_offset, s->nfont - blocked_fonts, s->nfont);
603 }
604
aa472e5f
PL
605 for (f = 0; f < s->nfont; f++)
606 {
607 int cand_elt;
608 FcPatternElt *cand_elts;
609
610 if (matchBlocked[f])
611 continue;
612
613 score = 0.0;
614 cand_elts = FcPatternEltU(s->fonts[f]->elts);
615
616 /* Look for the appropriate element in this candidate
617 * pattern 'f' and evaluate its score wrt 'p'. */
618 for (cand_elt = 0; cand_elt < s->fonts[f]->num; cand_elt++)
619 {
620 if (cand_elts[cand_elt].object ==
621 pat_elts[pat_elt].object)
622 {
623 FcValueListPtr v2;
624 FcValueList *v2_ptrU;
625 double v2_best_score = 1e99;
626
627 for (v2 = cand_elts[cand_elt].values,
628 v2_ptrU = FcValueListPtrU(v2);
629 FcValueListPtrU(v2);
630 v2 = FcValueListPtrU(v2)->next)
631 {
632 double v = (match->compare)
633 (&v1_ptrU->value, &v2_ptrU->value);
634
635 if (v < 0)
636 {
637 *result = FcResultTypeMismatch;
638 return 0;
639 }
640 /* I'm actually kind of surprised that
641 * this isn't v + 100 * v1_offset. -PL */
642 v = v * 100 + v1_offset;
643 if (v < v2_best_score)
644 v2_best_score = v;
645 }
646 score += v2_best_score;
647 }
648 }
649
650 /* If there's a previous champion, and current score
651 * beats previous best score, on this element, then
652 * knock out the previous champion and anything
653 * else that we would have visited previous to f;
654 * clearly anything previous to f would have been
655 * less than f on this score. */
656 if (!best || score < bestscore)
657 {
658 if (best)
659 {
660 int b;
1ed98a0c 661 for (b = blockStart; b < f; ++b)
aa472e5f
PL
662 matchBlocked[b] = FcTrue;
663 }
664
665 bestscore = score;
666 best = s->fonts[f];
1ed98a0c 667 blockStart = f;
aa472e5f
PL
668 }
669
670 /* If f loses, then it's out too. */
671 if (best && score > bestscore)
672 matchBlocked[f] = FcTrue;
673
674 /* Otherwise, f is equal to best on this element.
675 * Carry on to next pattern element. */
24330d27 676 }
1ed98a0c
PL
677 if ((FcDebug () & FC_DBG_MATCHV) && best)
678 {
679 printf ("Best match (scoring index %d) candidate ", scoring_index);
680 FcPatternPrint (best);
681 }
aa472e5f
PL
682 }
683 }
684 free (matchBlocked);
24330d27 685 }
1ed98a0c
PL
686 if ((FcDebug () & FC_DBG_MATCH) && best)
687 {
688 printf ("Best match ");
689 FcPatternPrint (best);
690 }
24330d27
KP
691 if (!best)
692 {
693 *result = FcResultNoMatch;
694 return 0;
695 }
216fac98 696 return FcFontRenderPrepare (config, p, best);
24330d27 697}
80c053b7
KP
698
699FcPattern *
700FcFontMatch (FcConfig *config,
701 FcPattern *p,
702 FcResult *result)
703{
704 FcFontSet *sets[2];
705 int nsets;
706
707 if (!config)
708 {
709 config = FcConfigGetCurrent ();
710 if (!config)
711 return 0;
712 }
713 nsets = 0;
714 if (config->fonts[FcSetSystem])
715 sets[nsets++] = config->fonts[FcSetSystem];
716 if (config->fonts[FcSetApplication])
717 sets[nsets++] = config->fonts[FcSetApplication];
718 return FcFontSetMatch (config, sets, nsets, p, result);
719}
216fac98 720
216fac98 721typedef struct _FcSortNode {
216fac98 722 FcPattern *pattern;
4c003605 723 double score[NUM_MATCH_VALUES];
216fac98
KP
724} FcSortNode;
725
0ab36ca8
KP
726static int
727FcSortCompare (const void *aa, const void *ab)
216fac98 728{
0ab36ca8
KP
729 FcSortNode *a = *(FcSortNode **) aa;
730 FcSortNode *b = *(FcSortNode **) ab;
bc9469ba
KP
731 double *as = &a->score[0];
732 double *bs = &b->score[0];
88c747e2 733 double ad = 0, bd = 0;
0ab36ca8 734 int i;
216fac98 735
4c003605 736 i = NUM_MATCH_VALUES;
bc9469ba
KP
737 while (i-- && (ad = *as++) == (bd = *bs++))
738 ;
739 return ad < bd ? -1 : ad > bd ? 1 : 0;
216fac98
KP
740}
741
742static FcBool
0ab36ca8 743FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim)
216fac98
KP
744{
745 FcCharSet *ncs;
0ab36ca8
KP
746 FcSortNode *node;
747
748 while (nnode--)
216fac98 749 {
0ab36ca8
KP
750 node = *n++;
751 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
752 FcResultMatch)
216fac98 753 {
1412a699
KP
754 /*
755 * If this font isn't a subset of the previous fonts,
756 * add it to the list
757 */
758 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
216fac98 759 {
0ab36ca8
KP
760 if (*cs)
761 {
762 ncs = FcCharSetUnion (ncs, *cs);
763 if (!ncs)
764 return FcFalse;
765 FcCharSetDestroy (*cs);
766 }
767 else
768 ncs = FcCharSetCopy (ncs);
769 *cs = ncs;
6f6563ed 770 FcPatternReference (node->pattern);
82f4243f
KP
771 if (FcDebug () & FC_DBG_MATCH)
772 {
773 printf ("Add ");
774 FcPatternPrint (node->pattern);
775 }
0ab36ca8 776 if (!FcFontSetAdd (fs, node->pattern))
6f6563ed
KP
777 {
778 FcPatternDestroy (node->pattern);
216fac98 779 return FcFalse;
6f6563ed 780 }
216fac98 781 }
216fac98
KP
782 }
783 }
216fac98
KP
784 return FcTrue;
785}
786
1412a699
KP
787void
788FcFontSetSortDestroy (FcFontSet *fs)
789{
1412a699
KP
790 FcFontSetDestroy (fs);
791}
792
216fac98
KP
793FcFontSet *
794FcFontSetSort (FcConfig *config,
795 FcFontSet **sets,
796 int nsets,
797 FcPattern *p,
798 FcBool trim,
799 FcCharSet **csp,
800 FcResult *result)
801{
802 FcFontSet *ret;
803 FcFontSet *s;
804 FcSortNode *nodes;
0ab36ca8 805 FcSortNode **nodeps, **nodep;
216fac98 806 int nnodes;
216fac98
KP
807 FcSortNode *new;
808 FcCharSet *cs;
809 int set;
810 int f;
811 int i;
5cf8c536
KP
812 int nPatternLang;
813 FcBool *patternLangSat;
814 FcValue patternLang;
216fac98 815
82f4243f
KP
816 if (FcDebug () & FC_DBG_MATCH)
817 {
818 printf ("Sort ");
819 FcPatternPrint (p);
820 }
216fac98
KP
821 nnodes = 0;
822 for (set = 0; set < nsets; set++)
823 {
824 s = sets[set];
825 if (!s)
826 continue;
827 nnodes += s->nfont;
828 }
829 if (!nnodes)
830 goto bail0;
5cf8c536
KP
831
832 for (nPatternLang = 0;
833 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
834 nPatternLang++)
835 ;
836
9dac3c59 837 /* freed below */
5cf8c536
KP
838 nodes = malloc (nnodes * sizeof (FcSortNode) +
839 nnodes * sizeof (FcSortNode *) +
840 nPatternLang * sizeof (FcBool));
216fac98
KP
841 if (!nodes)
842 goto bail0;
1412a699 843 nodeps = (FcSortNode **) (nodes + nnodes);
5cf8c536 844 patternLangSat = (FcBool *) (nodeps + nnodes);
216fac98 845
216fac98 846 new = nodes;
0ab36ca8 847 nodep = nodeps;
216fac98
KP
848 for (set = 0; set < nsets; set++)
849 {
850 s = sets[set];
851 if (!s)
852 continue;
853 for (f = 0; f < s->nfont; f++)
854 {
855 if (FcDebug () & FC_DBG_MATCHV)
856 {
857 printf ("Font %d ", f);
858 FcPatternPrint (s->fonts[f]);
859 }
860 new->pattern = s->fonts[f];
861 if (!FcCompare (p, new->pattern, new->score, result))
862 goto bail1;
863 if (FcDebug () & FC_DBG_MATCHV)
864 {
865 printf ("Score");
4c003605 866 for (i = 0; i < NUM_MATCH_VALUES; i++)
216fac98
KP
867 {
868 printf (" %g", new->score[i]);
869 }
870 printf ("\n");
871 }
0ab36ca8 872 *nodep = new;
216fac98 873 new++;
0ab36ca8 874 nodep++;
216fac98
KP
875 }
876 }
877
0ab36ca8
KP
878 nnodes = new - nodes;
879
1412a699 880 qsort (nodeps, nnodes, sizeof (FcSortNode *),
0ab36ca8 881 FcSortCompare);
5cf8c536
KP
882
883 for (i = 0; i < nPatternLang; i++)
884 patternLangSat[i] = FcFalse;
885
886 for (f = 0; f < nnodes; f++)
887 {
888 FcBool satisfies = FcFalse;
889 /*
890 * If this node matches any language, go check
891 * which ones and satisfy those entries
892 */
893 if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
894 {
895 for (i = 0; i < nPatternLang; i++)
896 {
897 FcValue nodeLang;
898
899 if (!patternLangSat[i] &&
900 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
901 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
902 {
9ab79bdf 903 double compare = FcCompareLang (&patternLang, &nodeLang);
5cf8c536
KP
904 if (compare >= 0 && compare < 2)
905 {
906 if (FcDebug () & FC_DBG_MATCHV)
907 {
908 FcChar8 *family;
909 FcChar8 *style;
910
911 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
912 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
913 printf ("Font %s:%s matches language %d\n", family, style, i);
914 }
915 patternLangSat[i] = FcTrue;
916 satisfies = FcTrue;
917 break;
918 }
919 }
920 }
921 }
922 if (!satisfies)
923 nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
924 }
925
926 /*
927 * Re-sort once the language issues have been settled
928 */
929 qsort (nodeps, nnodes, sizeof (FcSortNode *),
930 FcSortCompare);
0ab36ca8 931
216fac98
KP
932 ret = FcFontSetCreate ();
933 if (!ret)
934 goto bail1;
935
936 cs = 0;
937
0ab36ca8 938 if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim))
216fac98
KP
939 goto bail2;
940
d0f07b8d
KP
941 if (csp)
942 *csp = cs;
943 else
944 FcCharSetDestroy (cs);
216fac98 945
1412a699
KP
946 free (nodes);
947
216fac98
KP
948 return ret;
949
950bail2:
951 if (cs)
952 FcCharSetDestroy (cs);
953 FcFontSetDestroy (ret);
954bail1:
955 free (nodes);
956bail0:
957 return 0;
958}
20ac65ab
KP
959
960FcFontSet *
961FcFontSort (FcConfig *config,
962 FcPattern *p,
963 FcBool trim,
964 FcCharSet **csp,
965 FcResult *result)
966{
967 FcFontSet *sets[2];
968 int nsets;
969
970 if (!config)
971 {
972 config = FcConfigGetCurrent ();
973 if (!config)
974 return 0;
975 }
976 nsets = 0;
977 if (config->fonts[FcSetSystem])
978 sets[nsets++] = config->fonts[FcSetSystem];
979 if (config->fonts[FcSetApplication])
980 sets[nsets++] = config->fonts[FcSetApplication];
981 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
982}