winget-cli

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

Correlation.cpp (10828B)

      1 // Copyright (c) Microsoft Corporation.
      2 // Licensed under the MIT License.
      3 #include "pch.h"
      4 #include "TestCommon.h"
      5 #include "TestSource.h"
      6 
      7 #include <winget/ARPCorrelation.h>
      8 #include <winget/ARPCorrelationAlgorithms.h>
      9 #include <winget/Manifest.h>
     10 #include <winget/RepositorySearch.h>
     11 
     12 using namespace AppInstaller::Manifest;
     13 using namespace AppInstaller::Repository;
     14 using namespace AppInstaller::Repository::Correlation;
     15 using namespace AppInstaller::Utility;
     16 
     17 using namespace TestCommon;
     18 
     19 // Data for defining a test case
     20 struct TestCase
     21 {
     22     // Actual app data
     23     std::string AppName;
     24     std::string AppPublisher;
     25 
     26     // Data in ARP
     27     std::string ARPName;
     28     std::string ARPPublisher;
     29 
     30     bool IsMatch;
     31 };
     32 
     33 // Definition of a collection of test cases that we evaluate
     34 // together to get a single aggregate result
     35 struct DataSet
     36 {
     37     // Details about the apps we are trying to correlate
     38     std::vector<TestCase> TestCases;
     39 
     40     // Additional ARP entries to use as "noise" for the correlation
     41     std::vector<ARPEntry> ARPNoise;
     42 
     43     // Thresholds for considering a run of an heuristic against
     44     // this data set "good".
     45     // Values are ratios to the total number of test cases
     46     double RequiredTrueMatchRatio;
     47     double RequiredTrueMismatchRatio;
     48     double RequiredFalseMatchRatio;
     49     double RequiredFalseMismatchRatio;
     50 };
     51 
     52 // Aggregate result of running an heuristic against a data set.
     53 struct ResultSummary
     54 {
     55     size_t TrueMatches;
     56     size_t TrueMismatches;
     57     size_t FalseMatches;
     58     size_t FalseMismatches;
     59     std::chrono::milliseconds TotalTime;
     60 
     61     size_t TotalCases() const
     62     {
     63         return TrueMatches + TrueMismatches + FalseMatches + FalseMismatches;
     64     }
     65 
     66     auto AverageMatchingTime() const
     67     {
     68         return TotalTime / TotalCases();
     69     }
     70 };
     71 
     72 Manifest GetManifestFromTestCase(const TestCase& testCase)
     73 {
     74     Manifest manifest;
     75     manifest.DefaultLocalization.Add<Localization::PackageName>(testCase.AppName);
     76     manifest.DefaultLocalization.Add<Localization::Publisher>(testCase.AppPublisher);
     77     manifest.Localizations.push_back(manifest.DefaultLocalization);
     78     return manifest;
     79 }
     80 
     81 ARPEntry GetARPEntryFromTestCase(const TestCase& testCase, bool isNew)
     82 {
     83     Manifest arpManifest;
     84     arpManifest.DefaultLocalization.Add<Localization::PackageName>(testCase.ARPName);
     85     arpManifest.DefaultLocalization.Add<Localization::Publisher>(testCase.ARPPublisher);
     86     arpManifest.Localizations.push_back(arpManifest.DefaultLocalization);
     87     return ARPEntry{ TestPackage::Make(arpManifest, TestPackage::MetadataMap{}), isNew };
     88 }
     89 
     90 ARPEntry GetExistingARPEntryFromTestCase(const TestCase& testCase)
     91 {
     92     return GetARPEntryFromTestCase(testCase, /* isNew */ false);
     93 }
     94 
     95 void ReportMatch(std::string_view label, std::string_view appName, std::string_view appPublisher, std::string_view arpName, std::string_view arpPublisher)
     96 {
     97     WARN(label << '\n' <<
     98         "\tApp name      = " << appName << '\n' <<
     99         "\tApp publisher = " << appPublisher << '\n' <<
    100         "\tARP name      = " << arpName << '\n' <<
    101         "\tARP publisher = " << arpPublisher);
    102 }
    103 
    104 ResultSummary EvaluateDataSetWithHeuristic(const DataSet& dataSet, IARPMatchConfidenceAlgorithm& correlationAlgorithm, bool reportErrors = false)
    105 {
    106     ResultSummary result{};
    107     auto startTime = std::chrono::steady_clock::now();
    108 
    109     // Each entry under test will be pushed at the end of this
    110     // and removed at the end.
    111     auto arpEntries = dataSet.ARPNoise;
    112 
    113     for (const auto& testCase : dataSet.TestCases)
    114     {
    115         arpEntries.push_back(GetARPEntryFromTestCase(testCase, /* isNew */ true));
    116         ARPHeuristicsCorrelationResult correlationResult = FindARPEntryForNewlyInstalledPackageWithHeuristics(GetManifestFromTestCase(testCase), arpEntries, correlationAlgorithm);
    117         auto match = correlationResult.Package;
    118         arpEntries.pop_back();
    119 
    120         if (match)
    121         {
    122             auto matchName = match->GetProperty(PackageVersionProperty::Name);
    123             auto matchPublisher = match->GetProperty(PackageVersionProperty::Publisher);
    124 
    125             // The strings get normalized when added to the manifest, so we have
    126             // to normalize for the comparison.
    127             if (matchName == NormalizedString(testCase.ARPName) && matchPublisher == NormalizedString(testCase.ARPPublisher))
    128             {
    129                 ++result.TrueMatches;
    130             }
    131             else
    132             {
    133                 ++result.FalseMatches;
    134 
    135                 if (reportErrors)
    136                 {
    137                     ReportMatch("False match", testCase.AppName, testCase.AppPublisher, matchName, matchPublisher);
    138                 }
    139             }
    140         }
    141         else
    142         {
    143             if (testCase.IsMatch)
    144             {
    145                 ++result.FalseMismatches;
    146 
    147                 if (reportErrors)
    148                 {
    149                     ReportMatch("False mismatch", testCase.AppName, testCase.AppPublisher, testCase.ARPName, testCase.ARPPublisher);
    150                 }
    151             }
    152             else
    153             {
    154                 ++result.TrueMismatches;
    155             }
    156         }
    157     }
    158 
    159     auto endTime = std::chrono::steady_clock::now();
    160     result.TotalTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime);
    161 
    162     return result;
    163 }
    164 
    165 void ReportResults(ResultSummary results)
    166 {
    167     // This uses WARN to report as that is always shown regardless of the test result.
    168     // We may want to re-consider reporting in some other way
    169     WARN("Total cases:       " << results.TotalCases() << '\n' <<
    170          "True matches:      " << results.TrueMatches << '\n' <<
    171          "False matches:     " << results.FalseMatches << '\n' <<
    172          "True mismatches:   " << results.TrueMismatches << '\n' <<
    173          "False mismatches:  " << results.FalseMismatches << '\n' <<
    174          "Total matching time:   " << results.TotalTime.count() << "ms\n" <<
    175          "Average matching time: " << results.AverageMatchingTime().count() << "ms");
    176 }
    177 
    178 void ReportAndEvaluateResults(ResultSummary results, const DataSet& dataSet)
    179 {
    180     ReportResults(results);
    181 
    182     // Required True ratio is a lower limit. The more results we get right, the better.
    183     // Required False ratio is an upper limit. The fewer results we get wrong, the better.
    184     REQUIRE(results.TrueMatches >= results.TotalCases() * dataSet.RequiredTrueMatchRatio);
    185     REQUIRE(results.TrueMismatches >= results.TotalCases() * dataSet.RequiredTrueMismatchRatio);
    186     REQUIRE(results.FalseMatches <= results.TotalCases() * dataSet.RequiredFalseMatchRatio);
    187     REQUIRE(results.FalseMismatches <= results.TotalCases()* dataSet.RequiredFalseMismatchRatio);
    188 }
    189 
    190 // TODO: Define multiple data sets
    191 //   - Data set with many apps.
    192 //   - Data set with popular apps. The match requirements should be higher
    193 //   - Data set(s) in other languages.
    194 //   - Data set where not everything has a match
    195 
    196 std::vector<TestCase> LoadTestData()
    197 {
    198     // Creates test cases from the test data file.
    199     // The format of the file is one case per line, each with pipe (|) separated values.
    200     // Each row contains: AppId, AppName, AppPublisher, ARPDisplayName, ARPDisplayVersion, ARPPublisherName, ARPProductCode
    201     // TODO: Add more test cases; particularly for non-matches
    202     std::ifstream testDataStream(TestCommon::TestDataFile("InputARPData.txt").GetPath());
    203     REQUIRE(testDataStream);
    204 
    205     std::vector<TestCase> testCases;
    206 
    207     std::string line;
    208     while (std::getline(testDataStream, line))
    209     {
    210         std::stringstream ss{ line };
    211 
    212         TestCase testCase;
    213         std::string appId;
    214         std::string arpDisplayVersion;
    215         std::string arpProductCode;
    216         std::getline(ss, appId, '|');
    217         std::getline(ss, testCase.AppName, '|');
    218         std::getline(ss, testCase.AppPublisher, '|');
    219         std::getline(ss, testCase.ARPName, '|');
    220         std::getline(ss, arpDisplayVersion, '|');
    221         std::getline(ss, testCase.ARPPublisher, '|');
    222         std::getline(ss, arpProductCode, '|');
    223 
    224         testCase.IsMatch = true;
    225 
    226         testCases.push_back(std::move(testCase));
    227     }
    228 
    229     return testCases;
    230 }
    231 
    232 DataSet GetDataSet_NoNoise()
    233 {
    234     DataSet dataSet;
    235     dataSet.TestCases = LoadTestData();
    236 
    237     // Arbitrary values. We should refine them as the algorithm gets better.
    238     dataSet.RequiredTrueMatchRatio = 0.81;
    239     dataSet.RequiredFalseMatchRatio = 0;
    240     dataSet.RequiredTrueMismatchRatio = 0; // There are no expected mismatches in this data set
    241     dataSet.RequiredFalseMismatchRatio = 0.25;
    242 
    243     return dataSet;
    244 }
    245 
    246 DataSet GetDataSet_WithNoise()
    247 {
    248     DataSet dataSet;
    249     auto baseTestCases = LoadTestData();
    250 
    251     std::transform(baseTestCases.begin(), baseTestCases.end(), std::back_inserter(dataSet.ARPNoise), GetExistingARPEntryFromTestCase);
    252     dataSet.TestCases = std::move(baseTestCases);
    253 
    254     // Arbitrary values. We should refine them as the algorithm gets better.
    255     dataSet.RequiredTrueMatchRatio = 0.81;
    256     dataSet.RequiredFalseMatchRatio = 0; // This should always stay at 0
    257     dataSet.RequiredTrueMismatchRatio = 0; // There are no expected mismatches in this data set
    258     dataSet.RequiredFalseMismatchRatio = 0.25;
    259 
    260     return dataSet;
    261 }
    262 
    263 // Hide this test as it takes too long to run.
    264 // It is useful for comparing multiple algorithms, but for
    265 // regular testing we need only check that the chosen algorithm
    266 // performs well.
    267 TEMPLATE_TEST_CASE("Correlation_MeasureAlgorithmPerformance", "[correlation][.]",
    268     EmptyMatchConfidenceAlgorithm,
    269     WordsEditDistanceMatchConfidenceAlgorithm)
    270 {
    271     // Each section loads a different data set,
    272     // and then they are all handled the same
    273     DataSet dataSet;
    274     SECTION("No ARP noise")
    275     {
    276         dataSet = GetDataSet_NoNoise();
    277     }
    278     SECTION("With ARP noise")
    279     {
    280         dataSet = GetDataSet_WithNoise();
    281     }
    282 
    283     TestType measure;
    284     auto results = EvaluateDataSetWithHeuristic(dataSet, measure);
    285     ReportResults(results);
    286 }
    287 
    288 TEST_CASE("Correlation_ChosenHeuristicIsGood", "[correlation]")
    289 {
    290     // Each section loads a different data set,
    291     // and then they are all handled the same
    292     DataSet dataSet;
    293     SECTION("No ARP noise")
    294     {
    295         dataSet = GetDataSet_NoNoise();
    296     }
    297     SECTION("With ARP noise")
    298     {
    299         dataSet = GetDataSet_WithNoise();
    300     }
    301 
    302     // Use only the measure we ultimately pick
    303     auto& algorithm = IARPMatchConfidenceAlgorithm::Instance();
    304     auto results = EvaluateDataSetWithHeuristic(dataSet, algorithm, /* reportErrors */ true);
    305     ReportAndEvaluateResults(results, dataSet);
    306 }