From 3b7fc272c199a66b9d2bbecad18a3997c03825f9 Mon Sep 17 00:00:00 2001 From: Johannes Sixt Date: Wed, 20 May 2009 22:13:17 +0200 Subject: [PATCH] Fix template type matching algorithm in the presence of wildcards. The algorithm that chooses a type table among template arguments if the type table entries have wildcards had two grave bugs: - The intention is that entries that have wildcards in later positions are better matches than those with wildcards in earlier positions. But the method that penalized the candidates got this backwards. - After the penalty of a candidate was found, it was tried to compare it to the minimal penalty so far. But if a new minimum was found, it was forgotten to update that minimum. As a consequence, the last candidate was always chosen. These bugs are now fixed. The vector<*> and vector templates were used to test this algorithm, but that the correct candidate was always chosen was just coincidence. --- kdbg/typetable.cpp | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/kdbg/typetable.cpp b/kdbg/typetable.cpp index 3730f63..3136a61 100644 --- a/kdbg/typetable.cpp +++ b/kdbg/typetable.cpp @@ -362,21 +362,25 @@ TypeInfo* ProgramTypeTable::lookup(QString type) QStringList::const_iterator t = parts.begin(); QStringList::const_iterator p = pat.begin(); - unsigned penalty = 0; + unsigned accumPenalty = 0; bool equal = true; - for (int j = 0; equal && p != pat.end(); ++p, ++t, ++j) + unsigned penalty = ~(~0U>>1); // 1 in the leading bit + while (equal && p != pat.end()) { if (*p == "*") - penalty += 1U << j; // penalize wildcards + accumPenalty |= penalty; // penalize wildcards else equal = *p == *t; + ++p, ++t, penalty >>= 1; } if (equal) { - if (penalty == 0) + if (accumPenalty == 0) return i->second.type; - if (penalty < minPenalty) + if (accumPenalty < minPenalty) { result = i->second.type; + minPenalty = accumPenalty; + } } } return result; -- 2.11.4.GIT