Tk Source Code

Check-in [be0be1ae]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix in comparison of homegeneous equal sequences, a real problem with old implementation, see new test case bind-33.15.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | bug6e8afe516d
Files: files | file ages | folders
SHA3-256:be0be1ae8b1241700507c557897aab5afd0065d341d5866c9e066a8faba0d65a
User & Date: gcramer 2019-01-14 17:15:35
Context
2019-01-15
14:44
(1) Computation of most specialized event (PREFER_MOST_SPECIALIZED_EVENT) changed to make it more user-friendly (2) Minor modifications in bind.test (only textual changes) Leaf check-in: 149760d9 user: gcramer tags: bug6e8afe516d
2019-01-14
17:15
Fix in comparison of homegeneous equal sequences, a real problem with old implementation, see new test case bind-33.15. check-in: be0be1ae user: gcramer tags: bug6e8afe516d
2019-01-13
15:48
Superfluous comment removed. check-in: 408bdfa7 user: gcramer tags: bug6e8afe516d
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to generic/tkBind.c.

749
750
751
752
753
754
755




756
757
758
759
760
761
762
...
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831






















832
833
834
835
836
837
838
....
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103


2104
2105

2106
2107

2108
2109





2110


2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
....
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
....
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
....
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710

2711
2712
2713
2714
2715
2716
2717
2718
....
2744
2745
2746
2747
2748
2749
2750


2751
2752
2753
2754
2755
2756
2757
....
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
 
/*
 * Some useful helper functions.
 */
#ifdef SUPPORT_DEBUGGING
static int BindCount = 0;
#endif





static unsigned Max(unsigned a, unsigned b) { return a < b ? b : a; }
static int Abs(int n) { return n < 0 ? -n : n; }
static bool IsOdd(int n) { return n & 1; }

static bool TestNearbyTime(int lhs, int rhs) { return Abs(lhs - rhs) <= NEARBY_MS; }
static bool TestNearbyCoords(int lhs, int rhs) { return Abs(lhs - rhs) <= NEARBY_PIXELS; }
................................................................................
{
    assert(psPtr);
    assert(index < psPtr->numPats);

    return psPtr->pats[index].info;
}

#if PREFER_MOST_SPECIALIZED_EVENT
static unsigned
GetCount(
    const PatSeq *psPtr,
    unsigned index)
{
    assert(psPtr);
    assert(index < psPtr->numPats);

    return psPtr->pats[index].count;
}
#endif























static bool
MatchEventNearby(
    const XEvent *lhs,	/* previous button event */
    const XEvent *rhs)	/* current button event */
{
    assert(lhs);
................................................................................
    }
}

/* helper function */
static bool
IsBetterMatch(
    const PatSeq *fstMatchPtr,
    const PatSeq *sndMatchPtr,	/* this is a better match? */
    unsigned patIndex)
{
    int i;

    if (!sndMatchPtr) { return false; }
    if (!fstMatchPtr) { return true; }

    for (i = patIndex; i >= 0; --i) {
	Info fstInfo = GetInfo(fstMatchPtr, i);
	Info sndInfo = GetInfo(sndMatchPtr, i);

	if (sndInfo && !fstInfo) { return true; }
	if (!sndInfo && fstInfo) { return false; }
    }



#if PREFER_MOST_SPECIALIZED_EVENT

    if (fstMatchPtr->numPats > sndMatchPtr->numPats) { return true; }
    if (fstMatchPtr->numPats < sndMatchPtr->numPats) { return false; }


    for (i = patIndex; i >= 0; --i) {





	unsigned fstCount = GetCount(fstMatchPtr, i);


	unsigned sndCount = GetCount(sndMatchPtr, i);

	if (sndCount > fstCount) { return true; }
	if (sndCount < fstCount) { return false; }
    }
#endif

    if (sndMatchPtr->count > fstMatchPtr->count) { return true; }
    if (sndMatchPtr->count < fstMatchPtr->count) { return false; }

    return sndMatchPtr->number > fstMatchPtr->number;
}

void
Tk_BindEvent(
    Tk_BindingTable bindPtr,	/* Table in which to look for bindings. */
    XEvent *eventPtr,		/* What actually happened. */
................................................................................
	     * have to be promoted. Normally at most one list will be processed, and
	     * usually this list only contains one or two patterns.
	     */

	    for (i = PromArr_Size(bindPtr->promArr); i > 0; --i, --psl[0], --psl[1]) {
		psPtr[0] = MatchPatterns(dispPtr, bindPtr, psl[0], psl[1], i, curEvent, objArr[k], NULL);

		if (IsBetterMatch(matchPtrArr[k], psPtr[0], i)) {
		    /* we will process it later, because we still may find a pattern with better match */
		    matchPtrArr[k] = psPtr[0];
		}
		if (!PSList_IsEmpty(psl[1])) {
		    /* we have promoted sequences, adjust array size */
		    arraySize = Max(i + 1, arraySize);
		}
................................................................................
	    /* we have promoted sequences, adjust array size */
	    arraySize = Max(1u, arraySize);
	}

	bestPtr = psPtr[0] ? psPtr[0] : psPtr[1];

	if (matchPtrArr[k]) {
	    if (IsBetterMatch(matchPtrArr[k], bestPtr, 0)) {
		matchPtrArr[k] = bestPtr;
	    } else {
		/*
		 * We've already found a higher level match, nevertheless it was required to
		 * process the level zero patterns because of possible promotions.
		 */
	    }
................................................................................
    return false;
}

/* helper function */
static int
Compare(
    const PatSeq *fstMatchPtr,
    const PatSeq *sndMatchPtr, /* most recent match */
    unsigned patIndex)
{
    int i;

    assert(sndMatchPtr);

    if (!fstMatchPtr) { return +1; }

    assert(patIndex == fstMatchPtr->numPats - 1);
    assert(patIndex == sndMatchPtr->numPats - 1);

    for (i = patIndex; i >= 0; --i) {
	Info fstInfo = GetInfo(fstMatchPtr, i);
	Info sndInfo = GetInfo(sndMatchPtr, i);

	if (sndInfo && !fstInfo) { return +1; }
	if (!sndInfo && fstInfo) { return -1; }
    }


    return (int) sndMatchPtr->count - (int) fstMatchPtr->count;
}

/* helper function */
static bool
CompareModMasks(
    const PSModMaskArr *fstModMaskArr,
    const PSModMaskArr *sndModMaskArr,
................................................................................
	    ModMask fstModMask = *PSModMaskArr_Get(fstModMaskArr, i);
	    ModMask sndModMask = *PSModMaskArr_Get(sndModMaskArr, i);

	    if (IsSubsetOf(fstModMask, sndModMask)) { ++sndCount; }
	    if (IsSubsetOf(sndModMask, fstModMask)) { ++fstCount; }
	}
    }



    if (IsSubsetOf(fstModMask, sndModMask)) { ++sndCount; }
    if (IsSubsetOf(sndModMask, fstModMask)) { ++fstCount; }

    return fstCount - sndCount;
}

................................................................................
			 */

			if (psPtr->numPats == patIndex + 1) {
			    if (patPtr->count <= count) {
				/*
				 * This is also a final pattern.
				 * We always prefer the pattern with better match.
				 *
				 */

				int cmp = Compare(bestPtr, psPtr, patIndex);

				if (cmp == 0) {
				    cmp = CompareModMasks(psEntry->lastModMaskArr, bestModMaskArr,
					    modMask, bestModMask);
				}

				if (cmp > 0 || (cmp == 0 && bestPtr->number < psPtr->number)) {







>
>
>
>







 







<










<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
<

|



|
|
<
<
<
|
|
|
>
>


>
|
|
>

<
>
>
>
>
>
|
>
>
|
|





<
<
<







 







|







 







|







 







|
<

|

<
<

<
<
<
<
<
<
|
<
<
<
<
<
>
|







 







>
>







 







|


|







749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
...
817
818
819
820
821
822
823

824
825
826
827
828
829
830
831
832
833

834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
....
2106
2107
2108
2109
2110
2111
2112
2113

2114
2115
2116
2117
2118
2119
2120



2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132

2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147



2148
2149
2150
2151
2152
2153
2154
....
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
....
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
....
2711
2712
2713
2714
2715
2716
2717
2718

2719
2720
2721


2722






2723





2724
2725
2726
2727
2728
2729
2730
2731
2732
....
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
....
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
 
/*
 * Some useful helper functions.
 */
#ifdef SUPPORT_DEBUGGING
static int BindCount = 0;
#endif

#if PREFER_MOST_SPECIALIZED_EVENT
static unsigned Sqr(unsigned x) { return x*x; }
#endif

static unsigned Max(unsigned a, unsigned b) { return a < b ? b : a; }
static int Abs(int n) { return n < 0 ? -n : n; }
static bool IsOdd(int n) { return n & 1; }

static bool TestNearbyTime(int lhs, int rhs) { return Abs(lhs - rhs) <= NEARBY_MS; }
static bool TestNearbyCoords(int lhs, int rhs) { return Abs(lhs - rhs) <= NEARBY_PIXELS; }
................................................................................
{
    assert(psPtr);
    assert(index < psPtr->numPats);

    return psPtr->pats[index].info;
}


static unsigned
GetCount(
    const PatSeq *psPtr,
    unsigned index)
{
    assert(psPtr);
    assert(index < psPtr->numPats);

    return psPtr->pats[index].count;
}


static int
CountSpecialized(
    const PatSeq *fstMatchPtr,
    const PatSeq *sndMatchPtr)
{
    int fstCount = 0;
    int sndCount = 0;
    unsigned i;

    assert(fstMatchPtr);
    assert(sndMatchPtr);

    for (i = 0; i < fstMatchPtr->numPats; ++i) {
	if (GetInfo(fstMatchPtr, i)) { fstCount += GetCount(fstMatchPtr, i); }
    }
    for (i = 0; i < sndMatchPtr->numPats; ++i) {
	if (GetInfo(sndMatchPtr, i)) { sndCount += GetCount(sndMatchPtr, i); }
    }

    return sndCount - fstCount;
}

static bool
MatchEventNearby(
    const XEvent *lhs,	/* previous button event */
    const XEvent *rhs)	/* current button event */
{
    assert(lhs);
................................................................................
    }
}

/* helper function */
static bool
IsBetterMatch(
    const PatSeq *fstMatchPtr,
    const PatSeq *sndMatchPtr)	/* this is a better match? */

{
    int diff;

    if (!sndMatchPtr) { return false; }
    if (!fstMatchPtr) { return true; }
    
    diff = CountSpecialized(fstMatchPtr, sndMatchPtr);



    if (diff > 0) { return true; }
    if (diff < 0) { return false; }

    if (sndMatchPtr->count > fstMatchPtr->count) { return true; }
    if (sndMatchPtr->count < fstMatchPtr->count) { return false; }

#if PREFER_MOST_SPECIALIZED_EVENT
    {	/* local scope */
	unsigned fstCount = 0;
	unsigned sndCount = 0;
	unsigned i;


	/*
	 * Count the most high-ordered patterns.
	 */

	for (i = 0; i < fstMatchPtr->numPats; ++i) {
	    fstCount += Sqr(GetCount(fstMatchPtr, i));
	}
	for (i = 0; i < sndMatchPtr->numPats; ++i) {
	    sndCount += Sqr(GetCount(sndMatchPtr, i));
	}
	if (sndCount > fstCount) { return true; }
	if (sndCount < fstCount) { return false; }
    }
#endif




    return sndMatchPtr->number > fstMatchPtr->number;
}

void
Tk_BindEvent(
    Tk_BindingTable bindPtr,	/* Table in which to look for bindings. */
    XEvent *eventPtr,		/* What actually happened. */
................................................................................
	     * have to be promoted. Normally at most one list will be processed, and
	     * usually this list only contains one or two patterns.
	     */

	    for (i = PromArr_Size(bindPtr->promArr); i > 0; --i, --psl[0], --psl[1]) {
		psPtr[0] = MatchPatterns(dispPtr, bindPtr, psl[0], psl[1], i, curEvent, objArr[k], NULL);

		if (IsBetterMatch(matchPtrArr[k], psPtr[0])) {
		    /* we will process it later, because we still may find a pattern with better match */
		    matchPtrArr[k] = psPtr[0];
		}
		if (!PSList_IsEmpty(psl[1])) {
		    /* we have promoted sequences, adjust array size */
		    arraySize = Max(i + 1, arraySize);
		}
................................................................................
	    /* we have promoted sequences, adjust array size */
	    arraySize = Max(1u, arraySize);
	}

	bestPtr = psPtr[0] ? psPtr[0] : psPtr[1];

	if (matchPtrArr[k]) {
	    if (IsBetterMatch(matchPtrArr[k], bestPtr)) {
		matchPtrArr[k] = bestPtr;
	    } else {
		/*
		 * We've already found a higher level match, nevertheless it was required to
		 * process the level zero patterns because of possible promotions.
		 */
	    }
................................................................................
    return false;
}

/* helper function */
static int
Compare(
    const PatSeq *fstMatchPtr,
    const PatSeq *sndMatchPtr) /* most recent match */

{
    int diff;



    if (!fstMatchPtr) { return +1; }






    assert(sndMatchPtr);





    diff = CountSpecialized(fstMatchPtr, sndMatchPtr);
    return diff ? diff : (int) sndMatchPtr->count - (int) fstMatchPtr->count;
}

/* helper function */
static bool
CompareModMasks(
    const PSModMaskArr *fstModMaskArr,
    const PSModMaskArr *sndModMaskArr,
................................................................................
	    ModMask fstModMask = *PSModMaskArr_Get(fstModMaskArr, i);
	    ModMask sndModMask = *PSModMaskArr_Get(sndModMaskArr, i);

	    if (IsSubsetOf(fstModMask, sndModMask)) { ++sndCount; }
	    if (IsSubsetOf(sndModMask, fstModMask)) { ++fstCount; }
	}
    }

    /* Finally compare modifier masks of last pattern. */

    if (IsSubsetOf(fstModMask, sndModMask)) { ++sndCount; }
    if (IsSubsetOf(sndModMask, fstModMask)) { ++fstCount; }

    return fstCount - sndCount;
}

................................................................................
			 */

			if (psPtr->numPats == patIndex + 1) {
			    if (patPtr->count <= count) {
				/*
				 * This is also a final pattern.
				 * We always prefer the pattern with better match.
				 * If completely equal than prefer most recently defined pattern.
				 */

				int cmp = Compare(bestPtr, psPtr);

				if (cmp == 0) {
				    cmp = CompareModMasks(psEntry->lastModMaskArr, bestModMaskArr,
					    modMask, bestModMask);
				}

				if (cmp > 0 || (cmp == 0 && bestPtr->number < psPtr->number)) {

Changes to tests/bind.test.

6354
6355
6356
6357
6358
6359
6360
6361
6362
6363
6364
6365
6366
6367
6368
....
6372
6373
6374
6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
....
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
....
6554
6555
6556
6557
6558
6559
6560



































6561
6562
6563
6564
6565
6566
6567
    event generate .t.f <a>
    event generate .t.f <1>
    event generate .t.f <1>
    set x
} -cleanup {
    destroy .t.f
} -result {a11}
test bind-33.2 {should prefer more specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <Double-1> { lappend x "Double" }
    bind .t.f <1><1> { lappend x "11" }
................................................................................
} -cleanup {
    destroy .t.f
    # This test case shows that old implementation has an issue, because
    # in my opinion it is expected that <Double-1> is matching, this binding
    # is more specialized. But new implementation will be conform to old,
    # and so "11" is the expected result.
} -result {11}
test bind-33.3 {should prefer more specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <a><Double-1><a> { lappend x "Double" }
    bind .t.f <a><1><1><a> { lappend x "11" }
................................................................................
} -cleanup {
    destroy .t.f
    # Also this test case shows that old implementation has an issue, it is
    # expected that <a><Double-1><a> is matching, because <Double-1> is more
    # specialized than <1><1>. But new implementation will be conform to old,
    # and so "11" is the expected result.
} -result {11}
test bind-33.4 {should prefer more specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <1><1> { lappend x "11" }
    bind .t.f <Double-1> { lappend x "Double" }
................................................................................
    set x {}
} -body {
    bind .t.f <1><Control-1> { lappend x "first" }
    bind .t.f <Control-1><1> { lappend x "last" }
    event generate .t.f <Control-1>
    event generate .t.f <Control-1>
    set x



































} -cleanup {
    destroy .t.f
    # Old implementation fails, and returns "first", but this is wrong,
    # because both bindings are homogeneous equal, so the latter must
    # be preferred.
} -result {last}








|







 







|







 







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







6354
6355
6356
6357
6358
6359
6360
6361
6362
6363
6364
6365
6366
6367
6368
....
6372
6373
6374
6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
....
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
....
6554
6555
6556
6557
6558
6559
6560
6561
6562
6563
6564
6565
6566
6567
6568
6569
6570
6571
6572
6573
6574
6575
6576
6577
6578
6579
6580
6581
6582
6583
6584
6585
6586
6587
6588
6589
6590
6591
6592
6593
6594
6595
6596
6597
6598
6599
6600
6601
6602
    event generate .t.f <a>
    event generate .t.f <1>
    event generate .t.f <1>
    set x
} -cleanup {
    destroy .t.f
} -result {a11}
test bind-33.2 {should prefer most specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <Double-1> { lappend x "Double" }
    bind .t.f <1><1> { lappend x "11" }
................................................................................
} -cleanup {
    destroy .t.f
    # This test case shows that old implementation has an issue, because
    # in my opinion it is expected that <Double-1> is matching, this binding
    # is more specialized. But new implementation will be conform to old,
    # and so "11" is the expected result.
} -result {11}
test bind-33.3 {should prefer most specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <a><Double-1><a> { lappend x "Double" }
    bind .t.f <a><1><1><a> { lappend x "11" }
................................................................................
} -cleanup {
    destroy .t.f
    # Also this test case shows that old implementation has an issue, it is
    # expected that <a><Double-1><a> is matching, because <Double-1> is more
    # specialized than <1><1>. But new implementation will be conform to old,
    # and so "11" is the expected result.
} -result {11}
test bind-33.4 {prefer most specialized event} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <1><1> { lappend x "11" }
    bind .t.f <Double-1> { lappend x "Double" }
................................................................................
    set x {}
} -body {
    bind .t.f <1><Control-1> { lappend x "first" }
    bind .t.f <Control-1><1> { lappend x "last" }
    event generate .t.f <Control-1>
    event generate .t.f <Control-1>
    set x
} -cleanup {
    destroy .t.f
    # Old implementation fails, and returns "first", but this is wrong,
    # because both bindings are homogeneous equal, so the latter must
    # be preferred.
} -result {last}
test bind-33.14 {prefer last in case of homogeneous patterns} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <1><ButtonPress><1><ButtonPress> { lappend x "first" }
    bind .t.f <ButtonPress><1><ButtonPress><1> { lappend x "last" }
    event generate .t.f <1>
    event generate .t.f <1>
    event generate .t.f <1>
    event generate .t.f <1>
    set x
} -cleanup {
    destroy .t.f
} -result {last}
test bind-33.15 {prefer last in case of homogeneous patterns} -setup {
    pack [frame .t.f]
    focus -force .t.f
    update
    set x {}
} -body {
    bind .t.f <ButtonPress><1><ButtonPress><1> { lappend x "first" }
    bind .t.f <1><ButtonPress><1><ButtonPress> { lappend x "last" }
    event generate .t.f <1>
    event generate .t.f <1>
    event generate .t.f <1>
    event generate .t.f <1>
    set x
} -cleanup {
    destroy .t.f
    # Old implementation fails, and returns "first", but this is wrong,
    # because both bindings are homogeneous equal, so the latter must
    # be preferred.
} -result {last}