1 //===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //===----------------------------------------------------------------------===//
7 
8 #include "llvm/ADT/DeltaAlgorithm.h"
9 #include <algorithm>
10 #include <iterator>
11 #include <set>
12 using namespace llvm;
13 
14 DeltaAlgorithm::~DeltaAlgorithm() {
15 }
16 
17 bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
18   if (FailedTestsCache.count(Changes))
19     return false;
20 
21   bool Result = ExecuteOneTest(Changes);
22   if (!Result)
23     FailedTestsCache.insert(Changes);
24 
25   return Result;
26 }
27 
28 void DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
29   // FIXME: Allow clients to provide heuristics for improved splitting.
30 
31   // FIXME: This is really slow.
32   changeset_ty LHS, RHS;
33   unsigned idx = 0, N = S.size() / 2;
34   for (changeset_ty::const_iterator it = S.begin(),
35          ie = S.end(); it != ie; ++it, ++idx)
36     ((idx < N) ? LHS : RHS).insert(*it);
37   if (!LHS.empty())
38     Res.push_back(LHS);
39   if (!RHS.empty())
40     Res.push_back(RHS);
41 }
42 
43 DeltaAlgorithm::changeset_ty
44 DeltaAlgorithm::Delta(const changeset_ty &Changes,
45                       const changesetlist_ty &Sets) {
46   // Invariant: union(Res) == Changes
47   UpdatedSearchState(Changes, Sets);
48 
49   // If there is nothing left we can remove, we are done.
50   if (Sets.size() <= 1)
51     return Changes;
52 
53   // Look for a passing subset.
54   changeset_ty Res;
55   if (Search(Changes, Sets, Res))
56     return Res;
57 
58   // Otherwise, partition the sets if possible; if not we are done.
59   changesetlist_ty SplitSets;
60   for (const changeset_ty &Set : Sets)
61     Split(Set, SplitSets);
62   if (SplitSets.size() == Sets.size())
63     return Changes;
64 
65   return Delta(Changes, SplitSets);
66 }
67 
68 bool DeltaAlgorithm::Search(const changeset_ty &Changes,
69                             const changesetlist_ty &Sets,
70                             changeset_ty &Res) {
71   // FIXME: Parallelize.
72   for (changesetlist_ty::const_iterator it = Sets.begin(),
73          ie = Sets.end(); it != ie; ++it) {
74     // If the test passes on this subset alone, recurse.
75     if (GetTestResult(*it)) {
76       changesetlist_ty Sets;
77       Split(*it, Sets);
78       Res = Delta(*it, Sets);
79       return true;
80     }
81 
82     // Otherwise, if we have more than two sets, see if test passes on the
83     // complement.
84     if (Sets.size() > 2) {
85       // FIXME: This is really slow.
86       changeset_ty Complement;
87       std::set_difference(
88         Changes.begin(), Changes.end(), it->begin(), it->end(),
89         std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
90       if (GetTestResult(Complement)) {
91         changesetlist_ty ComplementSets;
92         ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
93         ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
94         Res = Delta(Complement, ComplementSets);
95         return true;
96       }
97     }
98   }
99 
100   return false;
101 }
102 
103 DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
104   // Check empty set first to quickly find poor test functions.
105   if (GetTestResult(changeset_ty()))
106     return changeset_ty();
107 
108   // Otherwise run the real delta algorithm.
109   changesetlist_ty Sets;
110   Split(Changes, Sets);
111 
112   return Delta(Changes, Sets);
113 }
114