pyWinAuto: c:\.projects\py_pywinauto\pywinauto\findbestmatch.py

0001# GUI Application automation and testing library

0002# Copyright (C) 2006 Mark Mc Mahon

0003#

0004# This library is free software; you can redistribute it and/or

0005# modify it under the terms of the GNU Lesser General Public License

0006# as published by the Free Software Foundation; either version 2.1

0007# of the License, or (at your option) any later version.

0008#

0009# This library is distributed in the hope that it will be useful,

0010# but WITHOUT ANY WARRANTY; without even the implied warranty of

0011# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

0012# See the GNU Lesser General Public License for more details.

0013#

0014# You should have received a copy of the GNU Lesser General Public

0015# License along with this library; if not, write to the

0016#    Free Software Foundation, Inc.,

0017#    59 Temple Place,

0018#    Suite 330,

0019#    Boston, MA 02111-1307 USA

0020

0021"Module to find the closest match of a string in a list"

0022

0023__revision__ = "$Revision: 607 $"

0024

0025import re

0026import difflib

0027

0028import fuzzydict

0029#import ctypes

0030#import ldistance

0031#levenshtein_distance = ctypes.cdll.levenshtein.levenshtein_distance

0032#levenshtein_distance = ldistance.distance

0033

0034

0035# need to use sets.Set for python 2.3 compatability

0036import sets

0037

0038find_best_control_match_cutoff = .6

0039

0040#====================================================================

0041class MatchError(IndexError):

0042    "A suitable match could not be found"

0043    def __init__(self, items = None, tofind = ''):

0044        "Init the parent with the message"

0045        self.tofind = tofind

0046        self.items = items

0047        if self.items is None:

0048            self.items = []

0049

0050        IndexError.__init__(self,

0051            "Could not find '%s' in '%s'"% (tofind, self.items))

0052

0053

0054_cache = {}

0055

0056# given a list of texts return the match score for each

0057# and the best score and text with best score

0058#====================================================================

0059def _get_match_ratios(texts, match_against):

0060    "Get the match ratio of how each item in texts compared to match_against"

0061

0062    # now time to figre out the matching

0063    ratio_calc = difflib.SequenceMatcher()

0064    ratio_calc.set_seq1(match_against)

0065

0066    ratios = {}

0067    best_ratio = 0

0068    best_text = ''

0069

0070    global cache

0071

0072    for text in texts:

0073

0074        if 0:

0075            pass

0076

0077        if (text, match_against) in _cache:

0078            ratios[text] = _cache[(text, match_against)]

0079

0080        elif(match_against, text) in _cache:

0081            ratios[text] = _cache[(match_against, text)]

0082

0083        else:

0084            # set up the SequenceMatcher with other text

0085            ratio_calc.set_seq2(text)

0086

0087            # try using the levenshtein distance instead

0088            #lev_dist = levenshtein_distance(unicode(match_against), unicode(text))

0089            #ratio = 1 - lev_dist / 10.0

0090            #ratios[text] = ratio

0091

0092            # calculate ratio and store it

0093            ratios[text] = ratio_calc.ratio()

0094

0095            _cache[(match_against, text)] = ratios[text]

0096

0097        # if this is the best so far then update best stats

0098        if ratios[text] > best_ratio:

0099            best_ratio = ratios[text]

0100            best_text = text

0101

0102    return ratios, best_ratio, best_text

0103

0104

0105

0106

0107#====================================================================

0108def find_best_match(search_text, item_texts, items, limit_ratio = .5):

0109    """Return the item that best matches the search_text

0110    

0111    * **search_text** The text to search for

0112    * **item_texts** The list of texts to search through

0113    * **items** The list of items corresponding (1 to 1) 

0114      to the list of texts to search through.

0115    * **limit_ratio** How well the text has to match the best match.

0116      If the best match matches lower then this then it is not 

0117      considered a match and a MatchError is raised, (default = .5)

0118    """

0119    search_text = _cut_at_tab(search_text)

0120

0121

0122    text_item_map = UniqueDict()

0123    # Clean each item, make it unique and map to

0124    # to the item index

0125    for text, item in zip(item_texts, items):

0126        text_item_map[_cut_at_tab(text)] = item

0127

0128    ratios, best_ratio, best_text =           _get_match_ratios(text_item_map.keys(), search_text)

0130

0131    if best_ratio < limit_ratio:

0132        raise MatchError(items = text_item_map.keys(), tofind = search_text)

0133

0134    return text_item_map[best_text]

0135

0136

0137

0138

0139

0140#====================================================================

0141_after_tab = re.compile(ur"\t.*", re.UNICODE)

0142_non_word_chars = re.compile(ur"\W", re.UNICODE)

0143

0144def _cut_at_tab(text):

0145    "Clean out non characters from the string and return it"

0146

0147    # remove anything after the first tab

0148    return  _after_tab.sub("", text)

0149

0150def _clean_non_chars(text):

0151    "Remove non word characters"

0152    # should this also remove everything after the first tab?

0153

0154    # remove non alphanumeric characters

0155    return _non_word_chars.sub("", text)

0156

0157

0158def IsAboveOrToLeft(ref_control, other_ctrl):

0159    "Return true if the other_ctrl is above or to the left of ref_control"

0160    text_r = other_ctrl.Rectangle()

0161    ctrl_r = ref_control.Rectangle()

0162

0163    # skip controls where text win is to the right of ctrl

0164    if text_r.left >= ctrl_r.right:

0165        return False

0166

0167    # skip controls where text win is below ctrl

0168    if text_r.top >= ctrl_r.bottom:

0169        return False

0170

0171    return True

0172

0173

0174#====================================================================

0175distance_cuttoff = 999

0176def GetNonTextControlName(ctrl, controls):

0177    """return the name for this control by finding the closest

0178    text control above and to its left"""

0179

0180

0181    names = []

0182

0183    ctrl_index = controls.index(ctrl)

0184

0185    if ctrl_index != 0:

0186        prev_ctrl = controls[ctrl_index-1]

0187

0188        if prev_ctrl.FriendlyClassName() == "Static" and               prev_ctrl.IsVisible() and prev_ctrl.WindowText() and               IsAboveOrToLeft(ctrl, prev_ctrl):

0191

0192            names.append(

0193                prev_ctrl.WindowText() +

0194                    ctrl.FriendlyClassName())

0195

0196

0197    # get the visible text controls so that we can get

0198    # the closest text if the control has no text

0199    text_ctrls = [ctrl_ for ctrl_ in controls

0200        if ctrl_.IsVisible() and ctrl_.WindowText()]

0201

0202

0203    best_name = ''

0204    closest = distance_cuttoff

0205    # now for each of the visible text controls

0206    for text_ctrl in text_ctrls:

0207

0208        # get aliases to the control rectangles

0209        text_r = text_ctrl.Rectangle()

0210        ctrl_r = ctrl.Rectangle()

0211

0212        # skip controls where text win is to the right of ctrl

0213        if text_r.left >= ctrl_r.right:

0214            continue

0215

0216        # skip controls where text win is below ctrl

0217        if text_r.top >= ctrl_r.bottom:

0218            continue

0219

0220        # calculate the distance between the controls

0221        # at first I just calculated the distance from the top let

0222        # corner of one control to the top left corner of the other control

0223        # but this was not best, so as a text control should either be above

0224        # or to the left of the control I get the distance between

0225        # the top left of the non text control against the

0226        #    Top-Right of the text control (text control to the left)

0227        #    Bottom-Left of the text control (text control above)

0228        # then I get the min of these two

0229

0230

0231        # We do not actually need to calculate the difference here as we

0232        # only need a comparative number. As long as we find the closest one

0233        # the actual distance is not all that important to us.

0234        # this reduced the unit tests run on my by about 1 second

0235        # (from 61 ->60 s)

0236

0237        # (x^2 + y^2)^.5

0238        #distance = (

0239        #    (text_r.left - ctrl_r.left) ** 2 +  #  (x^2 + y^2)

0240        #    (text_r.bottom - ctrl_r.top) ** 2) \

0241        #    ** .5  # ^.5

0242

0243        #distance2 = (

0244        #    (text_r.right - ctrl_r.left) ** 2 +  #  (x^2 + y^2)

0245        #    (text_r.top - ctrl_r.top) ** 2) \

0246        #    ** .5  # ^.5

0247

0248        distance = abs(text_r.left - ctrl_r.left) + abs(text_r.bottom - ctrl_r.top)

0249        distance2 = abs(text_r.right - ctrl_r.left) + abs(text_r.top - ctrl_r.top)

0250

0251        distance = min(distance, distance2)

0252

0253        # if this distance was closer then the last one

0254        if distance < closest:

0255            closest = distance

0256            best_name = text_ctrl.WindowText() + ctrl.FriendlyClassName()

0257

0258    names.append(best_name)

0259

0260    return names

0261

0262

0263#====================================================================

0264def get_control_names(control, allcontrols):

0265    "Returns a list of names for this control"

0266    names = []

0267

0268    # if it has a reference control - then use that

0269    #if hasattr(control, 'ref') and control.ref:

0270    #    control = control.ref

0271

0272    # Add the control based on it's friendly class name

0273    names.append(control.FriendlyClassName())

0274

0275    # if it has some character text then add it base on that

0276    # and based on that with friendly class name appended

0277    cleaned = control.WindowText()

0278    if cleaned:

0279        names.append(cleaned)

0280        names.append(cleaned + control.FriendlyClassName())

0281

0282    # it didn't have visible text

0283    else:

0284        # so find the text of the nearest text visible control

0285        non_text_names = GetNonTextControlName(control, allcontrols)

0286        # and if one was found - add it

0287        if non_text_names:

0288            names.extend(non_text_names)

0289

0290    # return the names - and make sure there are no duplicates

0291    return sets.Set(names)

0292

0293

0294

0295

0296

0297#====================================================================

0298class UniqueDict(dict):

0299    "A dictionary subclass that handles making it's keys unique"

0300    def __setitem__(self, text, item):

0301        "Set an item of the dictionary"

0302

0303        # this text is already in the map

0304        # so we need to make it unique

0305        if text in self:

0306            # find next unique text after text1

0307            unique_text = text

0308            counter = 2

0309            while unique_text in self:

0310                unique_text = text + str(counter)

0311                counter += 1

0312

0313            # now we also need to make sure the original item

0314            # is under text0 and text1 also!

0315            if text + '0' not in self:

0316                dict.__setitem__(self, text+'0', self[text])

0317                dict.__setitem__(self, text+'1', self[text])

0318

0319            # now that we don't need original 'text' anymore

0320            # replace it with the uniq text

0321            text = unique_text

0322

0323        # add our current item

0324        dict.__setitem__(self, text, item)

0325

0326

0327    def FindBestMatches(

0328        self,

0329        search_text,

0330        clean = False,

0331        ignore_case = False):

0332

0333        """Return the best matches for search_text in the items

0334

0335        * **search_text** the text to look for

0336        * **clean** whether to clean non text characters out of the strings

0337        * **ignore_case** compare strings case insensitively

0338        """

0339

0340        # now time to figure out the matching

0341        ratio_calc = difflib.SequenceMatcher()

0342

0343        if ignore_case:

0344            search_text = search_text.lower()

0345

0346        ratio_calc.set_seq1(search_text)

0347

0348        ratios = {}

0349        best_ratio = 0

0350        best_texts = []

0351

0352        ratio_offset = 1

0353        if clean:

0354            ratio_offset *= .9

0355

0356        if ignore_case:

0357            ratio_offset *= .9

0358

0359        for text_ in self:

0360

0361            # make a copy of the text as we need the original later

0362            text = text_

0363

0364            if clean:

0365                text = _clean_non_chars(text)

0366

0367            if ignore_case:

0368                text = text.lower()

0369

0370            # check if this item is in the cache - if yes, then retrieve it

0371            if (text, search_text) in _cache:

0372                ratios[text_] = _cache[(text, search_text)]

0373

0374            elif(search_text, text) in _cache:

0375                ratios[text_] = _cache[(search_text, text)]

0376

0377            # not in the cache - calculate it and add it to the cache

0378            else:

0379                # set up the SequenceMatcher with other text

0380                ratio_calc.set_seq2(text)

0381

0382                # if a very quick check reveals that this is not going

0383                # to match then

0384                ratio = ratio_calc.real_quick_ratio() * ratio_offset

0385

0386                if ratio  >=  find_best_control_match_cutoff:

0387                    ratio = ratio_calc.quick_ratio() * ratio_offset

0388

0389                    if ratio >= find_best_control_match_cutoff:

0390                        ratio = ratio_calc.ratio() * ratio_offset

0391

0392                # save the match we got and store it in the cache

0393                ratios[text_] = ratio

0394                _cache[(text, search_text)] = ratio

0395

0396            # try using the levenshtein distance instead

0397            #lev_dist = levenshtein_distance(unicode(search_text), unicode(text))

0398            #ratio = 1 - lev_dist / 10.0

0399            #ratios[text_] = ratio

0400            #print "%5s" %("%0.2f"% ratio), search_text, `text`

0401

0402            # if this is the best so far then update best stats

0403            if ratios[text_] > best_ratio and                   ratios[text_] >= find_best_control_match_cutoff:

0405

0406                best_ratio = ratios[text_]

0407                best_texts = [text_]

0408

0409            elif ratios[text_] == best_ratio:

0410                best_texts.append(text_)

0411

0412        #best_ratio *= ratio_offset

0413

0414        return best_ratio, best_texts

0415

0416

0417#====================================================================

0418def build_unique_dict(controls):

0419    """Build the disambiguated list of controls

0420

0421    Separated out to a different function so that we can get

0422    the control identifiers for printing.

0423    """

0424    name_control_map = UniqueDict()

0425

0426

0427    # collect all the possible names for all controls

0428    # and build a list of them

0429    for ctrl in controls:

0430        ctrl_names = get_control_names(ctrl, controls)

0431

0432        # for each of the names

0433        for name in ctrl_names:

0434            name_control_map[name] = ctrl

0435    return name_control_map

0436

0437

0438#====================================================================

0439def find_best_control_matches(search_text, controls):

0440    """Returns the control that is the the best match to search_text

0441

0442    This is slightly differnt from find_best_match in that it builds

0443    up the list of text items to search through using information

0444    from each control. So for example for there is an OK, Button

0445    then the following are all added to the search list:

0446    "OK", "Button", "OKButton"

0447

0448    But if there is a ListView (which do not have visible 'text')

0449    then it will just add "ListView".

0450    """

0451

0452    name_control_map = build_unique_dict(controls)

0453

0454

0455#    # collect all the possible names for all controls

0456#    # and build a list of them

0457#    for ctrl in controls:

0458#        ctrl_names = get_control_names(ctrl, controls)

0459#

0460#        # for each of the names

0461#        for name in ctrl_names:

0462#            name_control_map[name] = ctrl

0463

0464    search_text = unicode(search_text)

0465

0466    best_ratio, best_texts = name_control_map.FindBestMatches(search_text)

0467

0468    best_ratio_ci, best_texts_ci =           name_control_map.FindBestMatches(search_text, ignore_case = True)

0470

0471    best_ratio_clean, best_texts_clean =           name_control_map.FindBestMatches(search_text, clean = True)

0473

0474    best_ratio_clean_ci, best_texts_clean_ci =           name_control_map.FindBestMatches(

0476            search_text, clean = True, ignore_case = True)

0477

0478

0479    if best_ratio_ci > best_ratio:

0480        best_ratio = best_ratio_ci

0481        best_texts = best_texts_ci

0482

0483    if best_ratio_clean > best_ratio:

0484        best_ratio = best_ratio_clean

0485        best_texts = best_texts_clean

0486

0487    if best_ratio_clean_ci > best_ratio:

0488        best_ratio = best_ratio_clean_ci

0489        best_texts = best_texts_clean_ci

0490

0491    if best_ratio < find_best_control_match_cutoff:

0492        raise MatchError(items = name_control_map.keys(), tofind = search_text)

0493

0494    return [name_control_map[best_text] for best_text in best_texts]

0495

0496

0497

0498

0499

0500

0501#

0502#def GetControlMatchRatio(text, ctrl):

0503#    # get the texts for the control

0504#    ctrl_names = get_control_names(ctrl)

0505#

0506#    #get the best match for these

0507#    matcher = UniqueDict()

0508#    for name in ctrl_names:

0509#        matcher[name] = ctrl

0510#

0511#    best_ratio, unused = matcher.FindBestMatches(text)

0512#

0513#    return best_ratio

0514#

0515#

0516#

0517#def get_controls_ratios(search_text, controls):

0518#    name_control_map = UniqueDict()

0519#

0520#    # collect all the possible names for all controls

0521#    # and build a list of them

0522#    for ctrl in controls:

0523#        ctrl_names = get_control_names(ctrl)

0524#

0525#        # for each of the names

0526#        for name in ctrl_names:

0527#            name_control_map[name] = ctrl

0528#

0529#    match_ratios, best_ratio, best_text = \

0530#        _get_match_ratios(name_control_map.keys(), search_text)

0531#

0532#    return match_ratios, best_ratio, best_text,