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