hphp/util/interval-set.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/util/interval-set.h"
  18
  19 #include "hphp/util/assertions.h"
  20 #include "hphp/util/compilation-flags.h"
  21
  22 #include <sstream>
  23
  24 namespace HPHP {
  25
  26 IntervalSet IntervalSet::operator ~() const {
  27   IntervalSet ret;
  28   auto start = NEG_INF;
  29   for (auto const& i : intervals) {
  30     if (i.start > start) {
  31       ret.intervals.push_back({start, i.start - 1});
  32       if (i.end == POS_INF) return ret.checkInvariants();
  33     }
  34     start = i.end + 1;
  35   }
  36   ret.intervals.push_back({start, POS_INF});
  37   return ret.checkInvariants();
  38 }
  39 IntervalSet& IntervalSet::operator |=(const IntervalSet& o) {
  40   *this = *this | o;
  41   return *this;
  42 }
  43 IntervalSet& IntervalSet::operator &=(const IntervalSet& o) {
  44   *this = *this & o;
  45   return *this;
  46 }
  47 IntervalSet& IntervalSet::operator -=(const IntervalSet& o) {
  48   *this = *this - o;
  49   return *this;
  50 }
  51 IntervalSet IntervalSet::operator |(const IntervalSet& o) const {
  52   IntervalSet ret;
  53   size_t j0 = 0, j1 = 0;
  54   while (j0 < intervals.size() || j1 < o.intervals.size()) {
  55     auto const& i = [&] {
  56       if (j0 == intervals.size()) return o.intervals[j1++];
  57       if (j1 == o.intervals.size()) return intervals[j0++];
  58       if (intervals[j0].start < o.intervals[j1].start) return intervals[j0++];
  59       return o.intervals[j1++];
  60     }();
  61     if (!ret.intervals.size()) {
  62       ret.intervals.emplace_back(i);
  63       continue;
  64     }
  65     auto& last = ret.intervals.back();
  66     if (last.end == POS_INF) return ret.checkInvariants();
  67     if (last.end + 1 >= i.start) {
  68       if (i.end > last.end) last.end = i.end;
  69     } else {
  70       ret.intervals.emplace_back(i);
  71     }
  72   }
  73   return ret.checkInvariants();
  74 }
  75 IntervalSet IntervalSet::operator &(const IntervalSet& o) const {
  76   IntervalSet ret;
  77   size_t j0 = 0, j1 = 0;
  78   while (j0 < intervals.size() && j1 < o.intervals.size()) {
  79     auto const& i0 = intervals[j0];
  80     auto const& i1 = o.intervals[j1];
  81     if (i0.end < i1.start) {
  82       j0++;
  83     } else if (i1.end < i0.start) {
  84       j1++;
  85     } else {
  86       ret.intervals.push_back({
  87         std::max(i0.start, i1.start),
  88         std::min(i0.end, i1.end)
  89       });
  90       if (i0.end < i1.end) j0++;
  91       else j1++;
  92     }
  93   }
  94   return ret.checkInvariants();
  95 }
  96 IntervalSet IntervalSet::operator -(const IntervalSet& o) const {
  97   return *this & ~o;
  98 }
  99
 100 bool IntervalSet::operator ==(const IntervalSet& o) const {
 101   return intervals == o.intervals;
 102 }
 103 bool IntervalSet::operator !=(const IntervalSet& o) const {
 104   return !(*this == o);
 105 }
 106
 107 IntervalSet IntervalSet::None() { return IntervalSet{}; }
 108 IntervalSet IntervalSet::All() {
 109   return Inclusive(NEG_INF, POS_INF);
 110 }
 111 IntervalSet IntervalSet::Point(value_type v) {
 112   IntervalSet ret;
 113   ret.intervals.push_back({v, v});
 114   return ret.checkInvariants();
 115 }
 116 IntervalSet IntervalSet::Inclusive(value_type start, value_type end) {
 117   IntervalSet ret;
 118   ret.intervals.push_back({start, end});
 119   return ret.checkInvariants();
 120 }
 121 IntervalSet IntervalSet::Range(value_type start, value_type end) {
 122   assertx(start != NEG_INF);
 123   assert_flog(start <= end, "start: {}, end: {}", start, end);
 124   if (start == end) return None();
 125   IntervalSet ret;
 126   ret.intervals.push_back({start, end - 1});
 127   return ret.checkInvariants();
 128 }
 129 IntervalSet IntervalSet::Below(value_type end) {
 130   assertx(end != NEG_INF);
 131   IntervalSet ret;
 132   ret.intervals.push_back({NEG_INF, end - 1});
 133   return ret.checkInvariants();
 134 }
 135 IntervalSet IntervalSet::Above(value_type start) {
 136   IntervalSet ret;
 137   ret.intervals.push_back({start, POS_INF});
 138   return ret.checkInvariants();
 139 }
 140
 141 std::string IntervalSet::toString() const {
 142   std::string sep("");
 143   std::ostringstream os;
 144   os << "{";
 145   for (auto const& i : intervals) {
 146     os << sep;
 147     if (i.start == NEG_INF) os << "(-INF";
 148     else os << "[" << i.start;
 149     os << ", ";
 150     if (i.end == POS_INF) os << "+INF";
 151     else os << i.end + 1;
 152     os << ")";
 153     sep = ", ";
 154   }
 155   os << "}";
 156   return os.str();
 157 }
 158
 159 IntervalSet& IntervalSet::checkInvariants() {
 160   if constexpr (!debug) return *this;
 161   SCOPE_ASSERT_DETAIL("IntervalSet") {
 162     return toString();
 163   };
 164   for (size_t j = 0; j < intervals.size(); j++) {
 165     always_assert(intervals[j].start <= intervals[j].end);
 166     always_assert(IMPLIES(j, intervals[j - 1].end < POS_INF));
 167     always_assert(IMPLIES(j, intervals[j - 1].end + 1 < intervals[j].start));
 168   }
 169   return *this;
 170 }
 171 const IntervalSet& IntervalSet::checkInvariants() const {
 172   return const_cast<IntervalSet*>(this)->checkInvariants();
 173 }
 174
 175 } // namespace HPHP