winget-cli

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README | LICENSE

ARPCorrelation.cpp (13329B)

      1 // Copyright (c) Microsoft Corporation.
      2 // Licensed under the MIT License.
      3 #include "pch.h"
      4 #include "winget/ARPCorrelation.h"
      5 #include "winget/ARPCorrelationAlgorithms.h"
      6 #include "winget/Manifest.h"
      7 #include "winget/NameNormalization.h"
      8 #include "winget/RepositorySearch.h"
      9 #include "winget/RepositorySource.h"
     10 
     11 using namespace AppInstaller::Manifest;
     12 using namespace AppInstaller::Repository;
     13 using namespace AppInstaller::Utility;
     14 
     15 namespace AppInstaller::Repository::Correlation
     16 {
     17     namespace
     18     {
     19         constexpr double MatchingThreshold = 0.5;
     20         constexpr double MinimumDifferentiationThreshold = 0.05;
     21 
     22         IARPMatchConfidenceAlgorithm& InstanceInternal(std::optional<IARPMatchConfidenceAlgorithm*> algorithmOverride = {})
     23         {
     24             static WordsEditDistanceMatchConfidenceAlgorithm s_algorithm;
     25             static IARPMatchConfidenceAlgorithm* s_override = nullptr;
     26 
     27             if (algorithmOverride.has_value())
     28             {
     29                 s_override = algorithmOverride.value();
     30             }
     31 
     32             if (s_override)
     33             {
     34                 return *s_override;
     35             }
     36             else
     37             {
     38                 return s_algorithm;
     39             }
     40         }
     41     }
     42 
     43     IARPMatchConfidenceAlgorithm& IARPMatchConfidenceAlgorithm::Instance()
     44     {
     45         return InstanceInternal();
     46     }
     47 
     48 #ifndef AICLI_DISABLE_TEST_HOOKS
     49     void IARPMatchConfidenceAlgorithm::OverrideInstance(IARPMatchConfidenceAlgorithm* algorithmOverride)
     50     {
     51         InstanceInternal(algorithmOverride);
     52     }
     53 
     54     void IARPMatchConfidenceAlgorithm::ResetInstance()
     55     {
     56         InstanceInternal(nullptr);
     57     }
     58 #endif
     59 
     60     // Find the best match using heuristics
     61     ARPHeuristicsCorrelationResult FindARPEntryForNewlyInstalledPackageWithHeuristics(
     62         const Manifest::Manifest& manifest,
     63         const std::vector<ARPEntry>& arpEntries)
     64     {
     65         // TODO: In the future we can make different passes with different algorithms until we find a match
     66         return FindARPEntryForNewlyInstalledPackageWithHeuristics(manifest, arpEntries, IARPMatchConfidenceAlgorithm::Instance());
     67     }
     68 
     69     ARPHeuristicsCorrelationResult FindARPEntryForNewlyInstalledPackageWithHeuristics(
     70         const AppInstaller::Manifest::Manifest& manifest,
     71         const std::vector<ARPEntry>& arpEntries,
     72         IARPMatchConfidenceAlgorithm& algorithm)
     73     {
     74         if (arpEntries.empty())
     75         {
     76             AICLI_LOG(Repo, Warning, << "Empty ARP entries given");
     77             return {};
     78         }
     79 
     80         AICLI_LOG(Repo, Verbose, << "Looking for best match in ARP for manifest " << manifest.Id);
     81 
     82         algorithm.Init(manifest);
     83 
     84         ARPHeuristicsCorrelationResult result;
     85         result.Measures.reserve(arpEntries.size());
     86 
     87         for (const auto& arpEntry : arpEntries)
     88         {
     89             auto score = algorithm.ComputeConfidence(arpEntry);
     90             AICLI_LOG(Repo, Verbose, << "Match confidence for " << arpEntry.Entry->GetProperty(PackageProperty::Id) << ": " << score);
     91 
     92             result.Measures.emplace_back(CorrelationMeasure{ score, arpEntry.Entry->GetLatestVersion() });
     93         }
     94 
     95         std::sort(result.Measures.begin(), result.Measures.end(), [](const CorrelationMeasure& a, const CorrelationMeasure& b) { return a.Measure > b.Measure; });
     96 
     97         if (result.Measures[0].Measure < MatchingThreshold)
     98         {
     99             AICLI_LOG(Repo, Verbose, << "Maximum score [" << result.Measures[0].Measure << "] is lower than threshold [" << MatchingThreshold << "]");
    100             result.Reason = "maximum score below threshold";
    101         }
    102         else if (result.Measures.size() >= 2 && (result.Measures[0].Measure - result.Measures[1].Measure) < MinimumDifferentiationThreshold)
    103         {
    104             AICLI_LOG(Repo, Verbose, << "Top two scores, [" << result.Measures[0].Measure << "] and [" << result.Measures[1].Measure << "] are not significantly different [" << MinimumDifferentiationThreshold << "]");
    105             result.Reason = "top two scores are not significantly different";
    106         }
    107         else
    108         {
    109             AICLI_LOG(Repo, Verbose, << "Best match is " << result.Measures[0].Package->GetProperty(PackageVersionProperty::Id));
    110             result.Package = result.Measures[0].Package;
    111             result.Reason = "heuristics match";
    112         }
    113 
    114         return result;
    115     }
    116 
    117     void ARPCorrelationData::CapturePreInstallSnapshot()
    118     {
    119         ProgressCallback empty;
    120         Repository::Source preInstallARP = Repository::Source(PredefinedSource::ARP);
    121         preInstallARP.Open(empty);
    122 
    123         for (const auto& entry : preInstallARP.Search({}).Matches)
    124         {
    125             auto installed = entry.Package->GetInstalled()->GetLatestVersion();
    126             if (installed)
    127             {
    128                 m_preInstallSnapshot.emplace_back(std::make_tuple(
    129                     installed->GetProperty(PackageVersionProperty::Id),
    130                     installed->GetProperty(PackageVersionProperty::Version),
    131                     installed->GetProperty(PackageVersionProperty::Channel)));
    132             }
    133         }
    134 
    135         std::sort(m_preInstallSnapshot.begin(), m_preInstallSnapshot.end());
    136     }
    137 
    138     void ARPCorrelationData::CapturePostInstallSnapshot()
    139     {
    140         ProgressCallback empty;
    141         m_postInstallSnapshotSource = Repository::Source(PredefinedSource::ARP);
    142         m_postInstallSnapshotSource.Open(empty);
    143 
    144         for (auto& entry : m_postInstallSnapshotSource.Search({}).Matches)
    145         {
    146             auto installed = entry.Package->GetInstalled()->GetLatestVersion();
    147 
    148             if (installed)
    149             {
    150                 auto entryKey = std::make_tuple(
    151                     installed->GetProperty(PackageVersionProperty::Id),
    152                     installed->GetProperty(PackageVersionProperty::Version),
    153                     installed->GetProperty(PackageVersionProperty::Channel));
    154 
    155                 auto itr = std::lower_bound(m_preInstallSnapshot.begin(), m_preInstallSnapshot.end(), entryKey);
    156                 m_postInstallSnapshot.emplace_back(entry.Package->GetInstalled(), itr == m_preInstallSnapshot.end() || *itr != entryKey);
    157             }
    158         }
    159     }
    160 
    161     ARPCorrelationResult ARPCorrelationData::CorrelateForNewlyInstalled(const Manifest::Manifest& manifest, const ARPCorrelationSettings& settings)
    162     {
    163         AICLI_LOG(Repo, Verbose, << "Finding ARP entry matching newly installed package");
    164 
    165         // Also attempt to find the entry based on the manifest data
    166 
    167         SearchRequest manifestSearchRequest;
    168         AppInstaller::Manifest::Manifest::string_t defaultPublisher;
    169         if (manifest.DefaultLocalization.Contains(Localization::Publisher))
    170         {
    171             defaultPublisher = manifest.DefaultLocalization.Get<Localization::Publisher>();
    172         }
    173 
    174         // The default localization must contain the name or we cannot do this lookup
    175         if (manifest.DefaultLocalization.Contains(Localization::PackageName))
    176         {
    177             AppInstaller::Manifest::Manifest::string_t defaultName = manifest.DefaultLocalization.Get<Localization::PackageName>();
    178             manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::NormalizedNameAndPublisher, MatchType::Exact, defaultName, defaultPublisher));
    179 
    180             for (const auto& loc : manifest.Localizations)
    181             {
    182                 if (loc.Contains(Localization::PackageName) || loc.Contains(Localization::Publisher))
    183                 {
    184                     manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::NormalizedNameAndPublisher, MatchType::Exact,
    185                         loc.Contains(Localization::PackageName) ? loc.Get<Localization::PackageName>() : defaultName,
    186                         loc.Contains(Localization::Publisher) ? loc.Get<Localization::Publisher>() : defaultPublisher));
    187                 }
    188             }
    189         }
    190 
    191         std::set<std::string> productCodes;
    192         std::set<std::string> upgradeCodes;
    193         for (const auto& installer : manifest.Installers)
    194         {
    195             if (!installer.ProductCode.empty())
    196             {
    197                 // Add each ProductCode only once
    198                 if (productCodes.insert(installer.ProductCode).second)
    199                 {
    200                     manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::ProductCode, MatchType::Exact, installer.ProductCode));
    201                 }
    202             }
    203 
    204             for (const auto& appsAndFeaturesEntry : installer.AppsAndFeaturesEntries)
    205             {
    206                 if (!appsAndFeaturesEntry.DisplayName.empty())
    207                 {
    208                     manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::NormalizedNameAndPublisher, MatchType::Exact,
    209                         appsAndFeaturesEntry.DisplayName,
    210                         appsAndFeaturesEntry.Publisher.empty() ? defaultPublisher : appsAndFeaturesEntry.Publisher));
    211                 }
    212 
    213                 // Add each ProductCode and UpgradeCode only once;
    214                 if (!appsAndFeaturesEntry.ProductCode.empty() && productCodes.insert(appsAndFeaturesEntry.ProductCode).second)
    215                 {
    216                     manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::ProductCode, MatchType::Exact, appsAndFeaturesEntry.ProductCode));
    217                 }
    218                 if (!appsAndFeaturesEntry.UpgradeCode.empty() && upgradeCodes.insert(appsAndFeaturesEntry.UpgradeCode).second)
    219                 {
    220                     manifestSearchRequest.Inclusions.emplace_back(PackageMatchFilter(PackageMatchField::UpgradeCode, MatchType::Exact, appsAndFeaturesEntry.UpgradeCode));
    221                 }
    222             }
    223         }
    224 
    225         SearchResult findByManifest;
    226 
    227         // Don't execute this search if it would just find everything
    228         if (!manifestSearchRequest.IsForEverything())
    229         {
    230             findByManifest = m_postInstallSnapshotSource.Search(manifestSearchRequest);
    231         }
    232 
    233         // Cross reference the changes with the search results
    234         std::vector<std::shared_ptr<IPackage>> packagesInBoth;
    235 
    236         for (const auto& change : m_postInstallSnapshot)
    237         {
    238             if (change.IsNewOrUpdated)
    239             {
    240                 for (const auto& byManifest : findByManifest.Matches)
    241                 {
    242                     if (change.Entry->IsSame(byManifest.Package->GetInstalled().get()))
    243                     {
    244                         packagesInBoth.emplace_back(change.Entry);
    245                         break;
    246                     }
    247                 }
    248             }
    249         }
    250 
    251         // We now have all of the package changes; time to report them.
    252         //
    253         // The set of cases we could have for finding packages based on the manifest:
    254         //  0 packages  ::  The manifest data does not match the ARP information.
    255         //  1 package   ::  Golden path; this should be what we installed.
    256         //  2+ packages ::  The data in the manifest is either too broad or we have
    257         //                  a problem with our name normalization.
    258 
    259         // Find the package that we are going to log
    260         ARPCorrelationResult result;
    261         // TODO: Find a good way to consider the other heuristics in these stats.
    262         result.ChangesToARP = std::count_if(m_postInstallSnapshot.begin(), m_postInstallSnapshot.end(), [](const ARPEntry& e) { return e.IsNewOrUpdated; });
    263         result.MatchesInARP = findByManifest.Matches.size();
    264         result.CountOfIntersectionOfChangesAndMatches = packagesInBoth.size();
    265 
    266         // If there is only a single common package (changed and matches), it is almost certainly the correct one.
    267         if (settings.AllowNormalization && packagesInBoth.size() == 1)
    268         {
    269             result.Package = packagesInBoth[0]->GetLatestVersion();
    270             result.Reason = "normalization match and new/changed";
    271         }
    272         // If it wasn't changed but we still find a match, that is the best thing to report.
    273         else if (settings.AllowNormalization && findByManifest.Matches.size() == 1)
    274         {
    275             result.Package = findByManifest.Matches[0].Package->GetInstalled()->GetLatestVersion();
    276             result.Reason = "normalization match (not new/changed)";
    277         }
    278         else if (settings.AllowSingleChange && result.ChangesToARP == 1)
    279         {
    280             result.Package = std::find_if(m_postInstallSnapshot.begin(), m_postInstallSnapshot.end(), [](const ARPEntry& e) { return e.IsNewOrUpdated; })->Entry->GetLatestVersion();
    281             result.Reason = "only new/changed value";
    282         }
    283         else
    284         {
    285             // We were not able to find an exact match, so we now run some heuristics
    286             // to try and match the package with some ARP entry by assigning them scores.
    287             AICLI_LOG(Repo, Verbose, << "No exact ARP match found. Trying to find one with heuristics");
    288 
    289             result = FindARPEntryForNewlyInstalledPackageWithHeuristics(manifest, m_postInstallSnapshot);
    290         }
    291 
    292         return result;
    293     }
    294 }