fcmatch.c 26.8 KB
Newer Older
Keith Packard's avatar
Keith Packard committed
1
/*
2
 * fontconfig/src/fcmatch.c
Keith Packard's avatar
Keith Packard committed
3
 *
4
 * Copyright © 2000 Keith Packard
Keith Packard's avatar
Keith Packard committed
5 6 7 8 9
 *
 * 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
10
 * documentation, and that the name of the author(s) not be used in
Keith Packard's avatar
Keith Packard committed
11
 * advertising or publicity pertaining to distribution of the software without
12
 * specific, written prior permission.  The authors make no
Keith Packard's avatar
Keith Packard committed
13 14 15
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
16
 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
Keith Packard's avatar
Keith Packard committed
17
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18
 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
Keith Packard's avatar
Keith Packard committed
19 20 21 22 23 24
 * 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.
 */

25
#include "fcint.h"
Keith Packard's avatar
Keith Packard committed
26 27

static double
28
FcCompareNumber (const FcValue *value1, const FcValue *value2, FcValue *bestValue)
Keith Packard's avatar
Keith Packard committed
29
{
30
    double  v1, v2, v;
31

Behdad Esfahbod's avatar
Behdad Esfahbod committed
32
    switch ((int) value1->type) {
33
    case FcTypeInteger:
34
	v1 = (double) value1->u.i;
35 36
	break;
    case FcTypeDouble:
37
	v1 = value1->u.d;
38 39
	break;
    default:
Keith Packard's avatar
Keith Packard committed
40
	return -1.0;
41
    }
Behdad Esfahbod's avatar
Behdad Esfahbod committed
42
    switch ((int) value2->type) {
43
    case FcTypeInteger:
44
	v2 = (double) value2->u.i;
45 46
	break;
    case FcTypeDouble:
47
	v2 = value2->u.d;
48 49 50 51 52
	break;
    default:
	return -1.0;
    }
    v = v2 - v1;
Keith Packard's avatar
Keith Packard committed
53 54
    if (v < 0)
	v = -v;
55
    *bestValue = FcValueCanonicalize (value2);
56
    return v;
Keith Packard's avatar
Keith Packard committed
57 58 59
}

static double
60
FcCompareString (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
Keith Packard's avatar
Keith Packard committed
61
{
62
    *bestValue = FcValueCanonicalize (v2);
63
    return (double) FcStrCmpIgnoreCase (FcValueString(v1), FcValueString(v2)) != 0;
Keith Packard's avatar
Keith Packard committed
64 65
}

66
static double
67
FcCompareFamily (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
68
{
Behdad Esfahbod's avatar
Behdad Esfahbod committed
69
    /* rely on the guarantee in FcPatternObjectAddWithBinding that
70
     * families are always FcTypeString. */
71 72
    const FcChar8* v1_string = FcValueString(v1);
    const FcChar8* v2_string = FcValueString(v2);
73

74 75
    *bestValue = FcValueCanonicalize (v2);

76 77
    if (FcToLower(*v1_string) != FcToLower(*v2_string) &&
	*v1_string != ' ' && *v2_string != ' ')
78 79 80
       return 1.0;

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

83
static double
84
FcComparePostScript (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
85 86 87 88 89 90
{
    const FcChar8 *v1_string = FcValueString (v1);
    const FcChar8 *v2_string = FcValueString (v2);
    int n;
    size_t len;

91 92
    *bestValue = FcValueCanonicalize (v2);

93 94 95 96 97 98 99 100 101 102
    if (FcToLower (*v1_string) != FcToLower (*v2_string) &&
	*v1_string != ' ' && *v2_string != ' ')
	return 1.0;

    n = FcStrMatchIgnoreCaseAndDelims (v1_string, v2_string, (const FcChar8 *)" -");
    len = strlen ((const char *)v1_string);

    return (double)(len - n) / (double)len;
}

103
static double
104
FcCompareLang (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
105 106
{
    FcLangResult    result;
107
    FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
108

Behdad Esfahbod's avatar
Behdad Esfahbod committed
109
    switch ((int) value1.type) {
110
    case FcTypeLangSet:
Behdad Esfahbod's avatar
Behdad Esfahbod committed
111
	switch ((int) value2.type) {
112
	case FcTypeLangSet:
113
	    result = FcLangSetCompare (value1.u.l, value2.u.l);
114 115
	    break;
	case FcTypeString:
116
	    result = FcLangSetHasLang (value1.u.l,
117
				       value2.u.s);
118 119 120 121 122 123
	    break;
	default:
	    return -1.0;
	}
	break;
    case FcTypeString:
Behdad Esfahbod's avatar
Behdad Esfahbod committed
124
	switch ((int) value2.type) {
125
	case FcTypeLangSet:
126
	    result = FcLangSetHasLang (value2.u.l, value1.u.s);
127 128
	    break;
	case FcTypeString:
129
	    result = FcLangCompare (value1.u.s,
130
				    value2.u.s);
131 132 133 134 135 136
	    break;
	default:
	    return -1.0;
	}
	break;
    default:
137
	return -1.0;
138
    }
139
    *bestValue = FcValueCanonicalize (v2);
140 141 142 143 144 145 146 147 148 149 150
    switch (result) {
    case FcLangEqual:
	return 0;
    case FcLangDifferentCountry:
	return 1;
    case FcLangDifferentLang:
    default:
	return 2;
    }
}

Keith Packard's avatar
Keith Packard committed
151
static double
152
FcCompareBool (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
Keith Packard's avatar
Keith Packard committed
153
{
154
    if (v2->type != FcTypeBool || v1->type != FcTypeBool)
Keith Packard's avatar
Keith Packard committed
155
	return -1.0;
156

157 158 159 160 161 162
    if (v2->u.b != FcDontCare)
	*bestValue = FcValueCanonicalize (v2);
    else
	*bestValue = FcValueCanonicalize (v1);

    return (double) ((v2->u.b ^ v1->u.b) == 1);
Keith Packard's avatar
Keith Packard committed
163 164 165
}

static double
166
FcCompareCharSet (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
Keith Packard's avatar
Keith Packard committed
167
{
168
    *bestValue = FcValueCanonicalize (v2); /* TODO Improve. */
169
    return (double) FcCharSetSubtractCount (FcValueCharSet(v1), FcValueCharSet(v2));
Keith Packard's avatar
Keith Packard committed
170 171
}

172
static double
173
FcCompareRange (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
174 175 176
{
    FcValue value1 = FcValueCanonicalize (v1);
    FcValue value2 = FcValueCanonicalize (v2);
177
    double b1, e1, b2, e2, d;
178 179

    switch ((int) value1.type) {
180 181 182
    case FcTypeInteger:
        b1 = e1 = value1.u.i;
	break;
183
    case FcTypeDouble:
184
        b1 = e1 = value1.u.d;
185 186
	break;
    case FcTypeRange:
187 188
	b1 = value1.u.r->begin;
	e1 = value1.u.r->end;
189 190
	break;
    default:
191
	return -1;
192 193
    }
    switch ((int) value2.type) {
194 195 196
    case FcTypeInteger:
        b2 = e2 = value2.u.i;
	break;
197
    case FcTypeDouble:
198
        b2 = e2 = value2.u.d;
199 200
	break;
    case FcTypeRange:
201 202
	b2 = value2.u.r->begin;
	e2 = value2.u.r->end;
203 204
	break;
    default:
205
	return -1;
206 207
    }

208 209 210 211 212 213 214 215 216 217
    if (e1 < b2)
      d = b2;
    else if (e2 < b1)
      d = e2;
    else
      d = (FC_MAX (b1, b2) + FC_MIN (e1, e2)) * .5;

    bestValue->type = FcTypeDouble;
    bestValue->u.d = d;

218 219 220
    /* If the ranges overlap, it's a match, otherwise return closest distance. */
    if (e1 < b2 || e2 < b1)
	return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
221
    else
222
	return 0.0;
223 224
}

225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273
static double
FcCompareSize (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
{
    FcValue value1 = FcValueCanonicalize (v1);
    FcValue value2 = FcValueCanonicalize (v2);
    double b1, e1, b2, e2;

    switch ((int) value1.type) {
    case FcTypeInteger:
        b1 = e1 = value1.u.i;
	break;
    case FcTypeDouble:
        b1 = e1 = value1.u.d;
	break;
    case FcTypeRange:
	abort();
	b1 = value1.u.r->begin;
	e1 = value1.u.r->end;
	break;
    default:
	return -1;
    }
    switch ((int) value2.type) {
    case FcTypeInteger:
        b2 = e2 = value2.u.i;
	break;
    case FcTypeDouble:
        b2 = e2 = value2.u.d;
	break;
    case FcTypeRange:
	b2 = value2.u.r->begin;
	e2 = value2.u.r->end;
	break;
    default:
	return -1;
    }

    bestValue->type = FcTypeDouble;
    bestValue->u.d = (b1 + e1) * .5;

    /* If the ranges overlap, it's a match, otherwise return closest distance. */
    if (e1 < b2 || e2 < b1)
	return FC_MIN (fabs (b2 - e1), fabs (b1 - e2));
    if (b2 != e2 && b1 == e2) /* Semi-closed interval. */
        return 1e-15;
    else
	return 0.0;
}

274
static double
275
FcCompareFilename (const FcValue *v1, const FcValue *v2, FcValue *bestValue)
276
{
277
    const FcChar8 *s1 = FcValueString (v1), *s2 = FcValueString (v2);
278
    *bestValue = FcValueCanonicalize (v2);
279 280 281 282 283 284 285 286 287 288
    if (FcStrCmp (s1, s2) == 0)
	return 0.0;
    else if (FcStrCmpIgnoreCase (s1, s2) == 0)
	return 1.0;
    else if (FcStrGlobMatch (s1, s2))
	return 2.0;
    else
	return 3.0;
}

Behdad Esfahbod's avatar
Behdad Esfahbod committed
289 290 291

/* Define priorities to -1 for objects that don't have a compare function. */

292 293 294 295 296 297 298 299 300 301 302
#define PRI_NULL(n)				\
    PRI_ ## n ## _STRONG = -1,			\
    PRI_ ## n ## _WEAK = -1,
#define PRI1(n)
#define PRI_FcCompareFamily(n)		PRI1(n)
#define PRI_FcCompareString(n)		PRI1(n)
#define PRI_FcCompareNumber(n)		PRI1(n)
#define PRI_FcCompareBool(n)		PRI1(n)
#define PRI_FcCompareFilename(n)	PRI1(n)
#define PRI_FcCompareCharSet(n)		PRI1(n)
#define PRI_FcCompareLang(n)		PRI1(n)
303
#define PRI_FcComparePostScript(n)	PRI1(n)
304
#define PRI_FcCompareRange(n)		PRI1(n)
305
#define PRI_FcCompareSize(n)		PRI1(n)
306 307 308 309 310 311 312 313 314

#define FC_OBJECT(NAME, Type, Cmp)	PRI_##Cmp(NAME)

typedef enum _FcMatcherPriorityDummy {
#include "fcobjs.h"
} FcMatcherPriorityDummy;

#undef FC_OBJECT

Behdad Esfahbod's avatar
Behdad Esfahbod committed
315 316 317

/* Canonical match priority order. */

318
#undef PRI1
319 320 321 322
#define PRI1(n)					\
    PRI_ ## n,					\
    PRI_ ## n ## _STRONG = PRI_ ## n,		\
    PRI_ ## n ## _WEAK = PRI_ ## n
323 324 325

typedef enum _FcMatcherPriority {
    PRI1(FILE),
326
    PRI1(FONTFORMAT),
327
    PRI1(VARIABLE),
328
    PRI1(SCALABLE),
Behdad Esfahbod's avatar
Behdad Esfahbod committed
329
    PRI1(COLOR),
330 331 332
    PRI1(FOUNDRY),
    PRI1(CHARSET),
    PRI_FAMILY_STRONG,
333
    PRI_POSTSCRIPT_NAME_STRONG,
334
    PRI1(LANG),
335
    PRI_FAMILY_WEAK,
336
    PRI_POSTSCRIPT_NAME_WEAK,
337
    PRI1(SYMBOL),
338
    PRI1(SPACING),
339
    PRI1(SIZE),
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
    PRI1(PIXEL_SIZE),
    PRI1(STYLE),
    PRI1(SLANT),
    PRI1(WEIGHT),
    PRI1(WIDTH),
    PRI1(DECORATIVE),
    PRI1(ANTIALIAS),
    PRI1(RASTERIZER),
    PRI1(OUTLINE),
    PRI1(FONTVERSION),
    PRI_END
} FcMatcherPriority;

#undef PRI1

355
typedef struct _FcMatcher {
356
    FcObject object;
357
    double   (*compare) (const FcValue *v1, const FcValue *v2, FcValue *bestValue);
358
    int      strong, weak;
359 360
} FcMatcher;

Keith Packard's avatar
Keith Packard committed
361 362 363 364 365
/*
 * Order is significant, it defines the precedence of
 * each value, earlier values are more significant than
 * later values
 */
366
#define FC_OBJECT(NAME, Type, Cmp)	{ FC_##NAME##_OBJECT,	Cmp,	PRI_##NAME##_STRONG,	PRI_##NAME##_WEAK },
367
static const FcMatcher _FcMatchers [] = {
368 369
    { FC_INVALID_OBJECT, NULL, -1, -1 },
#include "fcobjs.h"
Keith Packard's avatar
Keith Packard committed
370
};
371
#undef FC_OBJECT
Keith Packard's avatar
Keith Packard committed
372

Behdad Esfahbod's avatar
Behdad Esfahbod committed
373
static const FcMatcher*
374 375
FcObjectToMatcher (FcObject object,
		   FcBool   include_lang)
Keith Packard's avatar
Keith Packard committed
376
{
377 378 379 380 381 382 383 384
    if (include_lang)
    {
	switch (object) {
	case FC_FAMILYLANG_OBJECT:
	case FC_STYLELANG_OBJECT:
	case FC_FULLNAMELANG_OBJECT:
	    object = FC_LANG_OBJECT;
	    break;
385
	}
386
    }
387 388
    if (object > FC_MAX_BASE_OBJECT ||
	!_FcMatchers[object].compare ||
389 390
	_FcMatchers[object].strong == -1 ||
	_FcMatchers[object].weak == -1)
391
	return NULL;
392

393
    return _FcMatchers + object;
394 395 396
}

static FcBool
397 398 399 400 401 402 403 404
FcCompareValueList (FcObject	     object,
		    const FcMatcher *match,
		    FcValueListPtr   v1orig,	/* pattern */
		    FcValueListPtr   v2orig,	/* target */
		    FcValue         *bestValue,
		    double          *value,
		    int             *n,
		    FcResult        *result)
405 406 407
{
    FcValueListPtr  v1, v2;
    double    	    v, best, bestStrong, bestWeak;
408
    int		    j, k, pos = 0;
409 410

    if (!match)
411 412
    {
	if (bestValue)
413
	    *bestValue = FcValueCanonicalize(&v2orig->value);
414 415
	if (n)
	    *n = 0;
416 417
	return FcTrue;
    }
418

Keith Packard's avatar
Keith Packard committed
419
    best = 1e99;
420 421
    bestStrong = 1e99;
    bestWeak = 1e99;
422
    j = 0;
423
    for (v1 = v1orig; v1; v1 = FcValueListNext(v1))
Keith Packard's avatar
Keith Packard committed
424
    {
425
	for (v2 = v2orig, k = 0; v2; v2 = FcValueListNext(v2), k++)
Keith Packard's avatar
Keith Packard committed
426
	{
427 428
	    FcValue matchValue;
	    v = (match->compare) (&v1->value, &v2->value, &matchValue);
Keith Packard's avatar
Keith Packard committed
429 430 431 432 433
	    if (v < 0)
	    {
		*result = FcResultTypeMismatch;
		return FcFalse;
	    }
434
	    v = v * 1000 + j;
Keith Packard's avatar
Keith Packard committed
435 436 437
	    if (v < best)
	    {
		if (bestValue)
438
		    *bestValue = matchValue;
Keith Packard's avatar
Keith Packard committed
439
		best = v;
440
		pos = k;
Keith Packard's avatar
Keith Packard committed
441
	    }
442
	    if (v1->binding == FcValueBindingStrong)
443 444 445 446 447 448 449 450 451
	    {
		if (v < bestStrong)
		    bestStrong = v;
	    }
	    else
	    {
		if (v < bestWeak)
		    bestWeak = v;
	    }
Keith Packard's avatar
Keith Packard committed
452 453 454 455 456
	}
	j++;
    }
    if (FcDebug () & FC_DBG_MATCHV)
    {
457
	printf (" %s: %g ", FcObjectName (object), best);
Keith Packard's avatar
Keith Packard committed
458 459 460 461 462
	FcValueListPrint (v1orig);
	printf (", ");
	FcValueListPrint (v2orig);
	printf ("\n");
    }
463
    if (value)
464
    {
465 466
	int weak    = match->weak;
	int strong  = match->strong;
467 468 469 470 471 472 473 474
	if (weak == strong)
	    value[strong] += best;
	else
	{
	    value[weak] += bestWeak;
	    value[strong] += bestStrong;
	}
    }
475 476 477
    if (n)
	*n = pos;

Keith Packard's avatar
Keith Packard committed
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492
    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;
493

494
    for (i = 0; i < PRI_END; i++)
Keith Packard's avatar
Keith Packard committed
495
	value[i] = 0.0;
496

497 498 499
    i1 = 0;
    i2 = 0;
    while (i1 < pat->num && i2 < fnt->num)
Keith Packard's avatar
Keith Packard committed
500
    {
501 502
	FcPatternElt *elt_i1 = &FcPatternElts(pat)[i1];
	FcPatternElt *elt_i2 = &FcPatternElts(fnt)[i2];
503

504
	i = FcObjectCompare(elt_i1->object, elt_i2->object);
505 506 507 508 509
	if (i > 0)
	    i2++;
	else if (i < 0)
	    i1++;
	else
Keith Packard's avatar
Keith Packard committed
510
	{
511 512
	    const FcMatcher *match = FcObjectToMatcher (elt_i1->object, FcFalse);
	    if (!FcCompareValueList (elt_i1->object, match,
513 514
				     FcPatternEltValues(elt_i1),
				     FcPatternEltValues(elt_i2),
515
				     NULL, value, NULL, result))
516 517 518
		return FcFalse;
	    i1++;
	    i2++;
Keith Packard's avatar
Keith Packard committed
519
	}
520 521
    }
    return FcTrue;
Keith Packard's avatar
Keith Packard committed
522 523
}

524 525 526 527 528 529 530
FcPattern *
FcFontRenderPrepare (FcConfig	    *config,
		     FcPattern	    *pat,
		     FcPattern	    *font)
{
    FcPattern	    *new;
    int		    i;
531
    FcPatternElt    *fe, *pe;
532
    FcValue	    v;
533
    FcResult	    result;
534 535
    FcBool	    variable = FcFalse;
    FcStrBuf        variations;
536

537 538 539
    assert (pat != NULL);
    assert (font != NULL);

540 541 542 543 544
    FcPatternObjectGetBool (font, FC_VARIABLE_OBJECT, 0, &variable);
    assert (variable != FcDontCare);
    if (variable)
	FcStrBufInit (&variations, NULL, 0);

545 546
    new = FcPatternCreate ();
    if (!new)
547
	return NULL;
548 549
    for (i = 0; i < font->num; i++)
    {
550
	fe = &FcPatternElts(font)[i];
551 552 553 554 555 556 557 558 559 560 561 562
	if (fe->object == FC_FAMILYLANG_OBJECT ||
	    fe->object == FC_STYLELANG_OBJECT ||
	    fe->object == FC_FULLNAMELANG_OBJECT)
	{
	    /* ignore those objects. we need to deal with them
	     * another way */
	    continue;
	}
	if (fe->object == FC_FAMILY_OBJECT ||
	    fe->object == FC_STYLE_OBJECT ||
	    fe->object == FC_FULLNAME_OBJECT)
	{
563 564
	    FcPatternElt    *fel, *pel;

565 566 567 568 569 570 571 572 573
	    FC_ASSERT_STATIC ((FC_FAMILY_OBJECT + 1) == FC_FAMILYLANG_OBJECT);
	    FC_ASSERT_STATIC ((FC_STYLE_OBJECT + 1) == FC_STYLELANG_OBJECT);
	    FC_ASSERT_STATIC ((FC_FULLNAME_OBJECT + 1) == FC_FULLNAMELANG_OBJECT);

	    fel = FcPatternObjectFindElt (font, fe->object + 1);
	    pel = FcPatternObjectFindElt (pat, fe->object + 1);

	    if (fel && pel)
	    {
574 575 576 577
		/* The font has name languages, and pattern asks for specific language(s).
		 * Match on language and and prefer that result.
		 * Note:  Currently the code only give priority to first matching language.
		 */
578
		int n = 1, j;
579
		FcValueListPtr l1, l2, ln = NULL, ll = NULL;
580
		const FcMatcher *match = FcObjectToMatcher (pel->object, FcTrue);
581 582 583

		if (!FcCompareValueList (pel->object, match,
					 FcPatternEltValues (pel),
584
					 FcPatternEltValues (fel), NULL, NULL, &n, &result))
585 586 587 588 589
		{
		    FcPatternDestroy (new);
		    return NULL;
		}

590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
		for (j = 0, l1 = FcPatternEltValues (fe), l2 = FcPatternEltValues (fel);
		     l1 != NULL || l2 != NULL;
		     j++, l1 = l1 ? FcValueListNext (l1) : NULL, l2 = l2 ? FcValueListNext (l2) : NULL)
		{
		    if (j == n)
		    {
			if (l1)
			    ln = FcValueListPrepend (ln,
						     FcValueCanonicalize (&l1->value),
						     FcValueBindingStrong);
			if (l2)
			    ll = FcValueListPrepend (ll,
						     FcValueCanonicalize (&l2->value),
						     FcValueBindingStrong);
		    }
605
		    else
606 607 608 609 610 611 612 613 614 615
		    {
			if (l1)
			    ln = FcValueListAppend (ln,
						    FcValueCanonicalize (&l1->value),
						    FcValueBindingStrong);
			if (l2)
			    ll = FcValueListAppend (ll,
						    FcValueCanonicalize (&l2->value),
						    FcValueBindingStrong);
		    }
616
		}
617 618 619 620
		FcPatternObjectListAdd (new, fe->object, ln, FcFalse);
		FcPatternObjectListAdd (new, fel->object, ll, FcFalse);

		continue;
621 622 623
	    }
	    else if (fel)
	    {
624 625
		/* Pattern doesn't ask for specific language.  Copy all for name and
		 * lang. */
626 627 628 629 630 631 632 633
		FcValueListPtr l1, l2;

		l1 = FcValueListDuplicate (FcPatternEltValues (fe));
		l2 = FcValueListDuplicate (FcPatternEltValues (fel));
		FcPatternObjectListAdd (new, fe->object, l1, FcFalse);
		FcPatternObjectListAdd (new, fel->object, l2, FcFalse);

		continue;
634
	    }
635 636 637 638 639 640 641 642 643 644 645 646 647
	}

	pe = FcPatternObjectFindElt (pat, fe->object);
	if (pe)
	{
	    const FcMatcher *match = FcObjectToMatcher (pe->object, FcFalse);
	    if (!FcCompareValueList (pe->object, match,
				     FcPatternEltValues(pe),
				     FcPatternEltValues(fe), &v, NULL, NULL, &result))
	    {
		FcPatternDestroy (new);
		return NULL;
	    }
648
	    FcPatternObjectAdd (new, fe->object, v, FcFalse);
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681

	    /* Set font-variations settings for standard axes in variable fonts. */
	    if (variable &&
		FcPatternEltValues(fe)->value.type == FcTypeRange &&
		(fe->object == FC_WEIGHT_OBJECT ||
		 fe->object == FC_WIDTH_OBJECT ||
		 fe->object == FC_SIZE_OBJECT))
	    {
		double num;
		FcChar8 temp[128];
		const char *tag = "    ";
		assert (v.type == FcTypeDouble);
		num = v.u.d;
		if (variations.len)
		    FcStrBufChar (&variations, ',');
		switch (fe->object)
		{
		    case FC_WEIGHT_OBJECT:
			tag = "wght";
			num = FcWeightToOpenType (num);
			break;

		    case FC_WIDTH_OBJECT:
			tag = "wdth";
			break;

		    case FC_SIZE_OBJECT:
			tag = "opsz";
			break;
		}
		sprintf ((char *) temp, "%4s=%g", tag, num);
		FcStrBufString (&variations, temp);
	    }
682 683
	}
	else
684
	{
685 686 687
	    FcPatternObjectListAdd (new, fe->object,
				    FcValueListDuplicate (FcPatternEltValues (fe)),
				    FcTrue);
688
	}
689 690 691
    }
    for (i = 0; i < pat->num; i++)
    {
692 693
	pe = &FcPatternElts(pat)[i];
	fe = FcPatternObjectFindElt (font, pe->object);
694 695 696 697
	if (!fe &&
	    pe->object != FC_FAMILYLANG_OBJECT &&
	    pe->object != FC_STYLELANG_OBJECT &&
	    pe->object != FC_FULLNAMELANG_OBJECT)
698
	{
699 700
	    FcPatternObjectListAdd (new, pe->object,
				    FcValueListDuplicate (FcPatternEltValues(pe)),
Behdad Esfahbod's avatar
Behdad Esfahbod committed
701
				    FcFalse);
702
	}
703
    }
704

705
    if (variable && variations.len)
706
    {
707 708 709 710 711 712 713 714 715 716
	FcChar8 *vars = NULL;
	if (FcPatternObjectGetString (new, FC_FONT_VARIATIONS_OBJECT, 0, &vars) == FcResultMatch)
	{
	    FcStrBufChar (&variations, ',');
	    FcStrBufString (&variations, vars);
	    FcPatternObjectDel (new, FC_FONT_VARIATIONS_OBJECT);
	}

	FcPatternObjectAddString (new, FC_FONT_VARIATIONS_OBJECT, FcStrBufDoneStatic (&variations));
	FcStrBufDestroy (&variations);
717 718
    }

719
    FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
720 721 722
    return new;
}

723
static FcPattern *
724
FcFontSetMatchInternal (FcFontSet   **sets,
725 726 727
			int	    nsets,
			FcPattern   *p,
			FcResult    *result)
Keith Packard's avatar
Keith Packard committed
728
{
729
    double    	    score[PRI_END], bestscore[PRI_END];
Keith Packard's avatar
Keith Packard committed
730 731 732
    int		    f;
    FcFontSet	    *s;
    FcPattern	    *best;
733
    int		    i;
734
    int		    set;
Keith Packard's avatar
Keith Packard committed
735

736
    for (i = 0; i < PRI_END; i++)
737 738
	bestscore[i] = 0;
    best = 0;
Keith Packard's avatar
Keith Packard committed
739 740 741 742 743
    if (FcDebug () & FC_DBG_MATCH)
    {
	printf ("Match ");
	FcPatternPrint (p);
    }
744
    for (set = 0; set < nsets; set++)
Keith Packard's avatar
Keith Packard committed
745
    {
746 747
	s = sets[set];
	if (!s)
Keith Packard's avatar
Keith Packard committed
748
	    continue;
749
	for (f = 0; f < s->nfont; f++)
750 751 752
	{
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
753 754
		printf ("Font %d ", f);
		FcPatternPrint (s->fonts[f]);
Keith Packard's avatar
Keith Packard committed
755
	    }
756 757 758
	    if (!FcCompare (p, s->fonts[f], score, result))
		return 0;
	    if (FcDebug () & FC_DBG_MATCHV)
759
	    {
760
		printf ("Score");
761
		for (i = 0; i < PRI_END; i++)
762
		{
763
		    printf (" %g", score[i]);
Keith Packard's avatar
Keith Packard committed
764
		}
765
		printf ("\n");
766
	    }
767
	    for (i = 0; i < PRI_END; i++)
768
	    {
769 770 771 772
		if (best && bestscore[i] < score[i])
		    break;
		if (!best || score[i] < bestscore[i])
		{
773
		    for (i = 0; i < PRI_END; i++)
774 775 776 777
			bestscore[i] = score[i];
		    best = s->fonts[f];
		    break;
		}
778 779
	    }
	}
Keith Packard's avatar
Keith Packard committed
780
    }
781
    if (FcDebug () & FC_DBG_MATCH)
782
    {
783
	printf ("Best score");
784
	for (i = 0; i < PRI_END; i++)
785
	    printf (" %g", bestscore[i]);
786
	printf ("\n");
787 788
	FcPatternPrint (best);
    }
789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809
    if (FcDebug () & FC_DBG_MATCH2)
    {
	char *env = getenv ("FC_DBG_MATCH_FILTER");
	FcObjectSet *os = NULL;

	if (env)
	{
	    char *ss, *s;
	    char *p;
	    FcBool f = FcTrue;

	    ss = s = strdup (env);
	    os = FcObjectSetCreate ();
	    while (f)
	    {
		size_t len;
		char *x;

		if (!(p = strchr (s, ',')))
		{
		    f = FcFalse;
810
		    len = strlen (s);
811 812 813
		}
		else
		{
814
		    len = (p - s);
815
		}
816
		x = malloc (sizeof (char) * (len + 1));
817 818 819 820 821 822 823 824
		if (x)
		{
		    strcpy (x, s);
		    if (FcObjectFromName (x) > 0)
			FcObjectSetAdd (os, x);
		    s = p + 1;
		    free (x);
		}
825 826 827 828 829 830 831
	    }
	    free (ss);
	}
	FcPatternPrint2 (p, best, os);
	if (os)
	    FcObjectSetDestroy (os);
    }
832 833 834 835 836
    /* assuming that 'result' is initialized with FcResultNoMatch
     * outside this function */
    if (best)
	*result = FcResultMatch;

837 838 839 840 841 842 843 844 845 846 847 848
    return best;
}

FcPattern *
FcFontSetMatch (FcConfig    *config,
		FcFontSet   **sets,
		int	    nsets,
		FcPattern   *p,
		FcResult    *result)
{
    FcPattern	    *best;

849 850 851 852
    assert (sets != NULL);
    assert (p != NULL);
    assert (result != NULL);

853 854
    *result = FcResultNoMatch;

855 856 857 858 859 860
    if (!config)
    {
	config = FcConfigGetCurrent ();
	if (!config)
	    return 0;
    }
861
    best = FcFontSetMatchInternal (sets, nsets, p, result);
862 863 864 865
    if (best)
	return FcFontRenderPrepare (config, p, best);
    else
	return NULL;
Keith Packard's avatar
Keith Packard committed
866
}
867 868 869

FcPattern *
FcFontMatch (FcConfig	*config,
870
	     FcPattern	*p,
871 872 873 874
	     FcResult	*result)
{
    FcFontSet	*sets[2];
    int		nsets;
875
    FcPattern   *best;
876

877 878 879
    assert (p != NULL);
    assert (result != NULL);

880 881
    *result = FcResultNoMatch;

882 883 884 885 886 887 888 889 890 891 892
    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];
893

894
    best = FcFontSetMatchInternal (sets, nsets, p, result);
895 896 897 898
    if (best)
	return FcFontRenderPrepare (config, p, best);
    else
	return NULL;
899
}
900 901 902

typedef struct _FcSortNode {
    FcPattern	*pattern;
903
    double	score[PRI_END];
904 905
} FcSortNode;

906 907
static int
FcSortCompare (const void *aa, const void *ab)
908
{
909 910
    FcSortNode  *a = *(FcSortNode **) aa;
    FcSortNode  *b = *(FcSortNode **) ab;
911 912
    double	*as = &a->score[0];
    double	*bs = &b->score[0];
913
    double	ad = 0, bd = 0;
914
    int         i;
915

916
    i = PRI_END;
917 918 919
    while (i-- && (ad = *as++) == (bd = *bs++))
	;
    return ad < bd ? -1 : ad > bd ? 1 : 0;
920 921 922
}

static FcBool
923
FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **csp, FcBool trim)
924
{
925 926
    FcBool ret = FcFalse;
    FcCharSet *cs;
927
    int i;
928 929 930 931 932 933 934 935

    cs = 0;
    if (trim || csp)
    {
	cs = FcCharSetCreate ();
	if (cs == NULL)
	    goto bail;
    }
936

937
    for (i = 0; i < nnode; i++)
938
    {
939 940
	FcSortNode	*node = *n++;
	FcBool		adds_chars = FcFalse;
941 942 943 944

	/*
	 * Only fetch node charset if we'd need it
	 */
945
	if (cs)
946
	{
947 948
	    FcCharSet	*ncs;

949 950 951
	    if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) !=
		FcResultMatch)
	        continue;
952 953 954

	    if (!FcCharSetMerge (cs, ncs, &adds_chars))
		goto bail;
955 956 957 958 959 960
	}

	/*
	 * If this font isn't a subset of the previous fonts,
	 * add it to the list
	 */
961
	if (!i || !trim || adds_chars)
962
	{
963 964 965 966 967 968 969 970 971
	    FcPatternReference (node->pattern);
	    if (FcDebug () & FC_DBG_MATCHV)
	    {
		printf ("Add ");
		FcPatternPrint (node->pattern);
	    }
	    if (!FcFontSetAdd (fs, node->pattern))
	    {
		FcPatternDestroy (node->pattern);
972
		goto bail;
973 974 975
	    }
	}
    }
976 977 978 979 980 981 982 983 984 985 986 987 988
    if (csp)
    {
	*csp = cs;
	cs = 0;
    }

    ret = FcTrue;

bail:
    if (cs)
	FcCharSetDestroy (cs);

    return ret;
989 990
}

991 992 993 994 995 996
void
FcFontSetSortDestroy (FcFontSet *fs)
{
    FcFontSetDestroy (fs);
}

997
FcFontSet *
998
FcFontSetSort (FcConfig	    *config FC_UNUSED,
999 1000 1001 1002 1003 1004 1005 1006 1007 1008
	       FcFontSet    **sets,
	       int	    nsets,
	       FcPattern    *p,
	       FcBool	    trim,
	       FcCharSet    **csp,
	       FcResult	    *result)
{
    FcFontSet	    *ret;
    FcFontSet	    *s;
    FcSortNode	    *nodes;
1009
    FcSortNode	    **nodeps, **nodep;
1010 1011 1012 1013 1014
    int		    nnodes;
    FcSortNode	    *new;
    int		    set;
    int		    f;
    int		    i;
1015 1016 1017
    int		    nPatternLang;
    FcBool    	    *patternLangSat;
    FcValue	    patternLang;
1018

1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031
    assert (sets != NULL);
    assert (p != NULL);
    assert (result != NULL);

    /* There are some implementation that relying on the result of
     * "result" to check if the return value of FcFontSetSort
     * is valid or not.
     * So we should initialize it to the conservative way since
     * this function doesn't return NULL anymore.
     */
    if (result)
	*result = FcResultNoMatch;

1032 1033 1034 1035 1036
    if (FcDebug () & FC_DBG_MATCH)
    {
	printf ("Sort ");
	FcPatternPrint (p);
    }
1037 1038 1039 1040 1041 1042 1043 1044 1045
    nnodes = 0;
    for (set = 0; set < nsets; set++)
    {
	s = sets[set];
	if (!s)
	    continue;
	nnodes += s->nfont;
    }
    if (!nnodes)
1046
	return FcFontSetCreate ();
1047

1048 1049 1050 1051 1052
    for (nPatternLang = 0;
	 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
	 nPatternLang++)
	;
	
1053
    /* freed below */
1054
    nodes = malloc (nnodes * sizeof (FcSortNode) +
1055 1056
		    nnodes * sizeof (FcSortNode *) +
		    nPatternLang * sizeof (FcBool));
1057 1058
    if (!nodes)
	goto bail0;
1059
    nodeps = (FcSortNode **) (nodes + nnodes);
1060
    patternLangSat = (FcBool *) (nodeps + nnodes);
1061

1062
    new = nodes;
1063
    nodep = nodeps;
1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081
    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");
1082
		for (i = 0; i < PRI_END; i++)
1083 1084 1085 1086 1087
		{
		    printf (" %g", new->score[i]);
		}
		printf ("\n");
	    }
1088
	    *nodep = new;
1089
	    new++;
1090
	    nodep++;
1091 1092 1093
	}
    }

1094
    nnodes = new - nodes;
1095

1096
    qsort (nodeps, nnodes, sizeof (FcSortNode *),
1097
	   FcSortCompare);
1098

1099 1100
    for (i = 0; i < nPatternLang; i++)
	patternLangSat[i] = FcFalse;
1101

1102 1103 1104 1105 1106 1107 1108
    for (f = 0; f < nnodes; f++)
    {
	FcBool	satisfies = FcFalse;
	/*
	 * If this node matches any language, go check
	 * which ones and satisfy those entries
	 */
1109
	if (nodeps[f]->score[PRI_LANG] < 2000)
1110 1111 1112 1113 1114 1115 1116 1117 1118
	{
	    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)
		{
1119 1120
		    FcValue matchValue;
		    double  compare = FcCompareLang (&patternLang, &nodeLang, &matchValue);
1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139
		    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)
1140
	{
1141
	    nodeps[f]->score[PRI_LANG] = 10000.0;
1142
	}
1143 1144 1145 1146 1147 1148 1149
    }

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

1151 1152 1153 1154
    ret = FcFontSetCreate ();
    if (!ret)
	goto bail1;

1155
    if (!FcSortWalk (nodeps, nnodes, ret, csp, trim))
1156 1157
	goto bail2;

1158 1159
    free (nodes);

1160 1161 1162 1163 1164
    if (FcDebug() & FC_DBG_MATCH)
    {
	printf ("First font ");
	FcPatternPrint (ret->fonts[0]);
    }
1165 1166 1167
    if (ret->nfont > 0)
	*result = FcResultMatch;

1168 1169 1170 1171 1172 1173 1174 1175 1176
    return ret;

bail2:
    FcFontSetDestroy (ret);
bail1:
    free (nodes);
bail0:
    return 0;
}
1177 1178 1179

FcFontSet *
FcFontSort (FcConfig	*config,
1180
	    FcPattern	*p,
1181 1182 1183 1184 1185 1186 1187
	    FcBool	trim,
	    FcCharSet	**csp,
	    FcResult	*result)
{
    FcFontSet	*sets[2];
    int		nsets;

1188 1189 1190
    assert (p != NULL);
    assert (result != NULL);

1191 1192
    *result = FcResultNoMatch;

1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205
    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);
}
1206 1207 1208
#define __fcmatch__
#include "fcaliastail.h"
#undef __fcmatch__