1//===- IntegerInclusiveInterval.cpp -----------------------------*- 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//
9// This file implements utilities for handling lists of inclusive integer
10// intervals, such as parsing interval strings like "1-10,20-30,45", which are
11// used in debugging and bisection tools.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Support/IntegerInclusiveInterval.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/Support/Error.h"
18#include "llvm/Support/Regex.h"
19#include "llvm/Support/raw_ostream.h"
20#include <string>
21
22using namespace llvm;
23
24namespace llvm::IntegerInclusiveIntervalUtils {
25
26Expected<IntervalList> parseIntervals(StringRef Str, char Separator) {
27 IntervalList Intervals;
28
29 if (Str.empty())
30 return std::move(Intervals);
31
32 // Regex to match either single number or interval "num1-num2".
33 const Regex IntervalRegex("^([0-9]+)(-([0-9]+))?$");
34
35 for (StringRef Part : llvm::split(Str, Separator)) {
36 Part = Part.trim();
37 if (Part.empty())
38 continue;
39
40 SmallVector<StringRef, 4> Matches;
41 if (!IntervalRegex.match(String: Part, Matches: &Matches))
42 return createStringError(EC: std::errc::invalid_argument,
43 Fmt: "Invalid interval format: '%s'",
44 Vals: Part.str().c_str());
45
46 int64_t Begin, End;
47 if (Matches[1].getAsInteger(Radix: 10, Result&: Begin))
48 return createStringError(EC: std::errc::invalid_argument,
49 Fmt: "Failed to parse number: '%s'",
50 Vals: Matches[1].str().c_str());
51
52 if (!Matches[3].empty()) {
53 // Interval format "begin-end".
54 if (Matches[3].getAsInteger(Radix: 10, Result&: End))
55 return createStringError(EC: std::errc::invalid_argument,
56 Fmt: "Failed to parse number: '%s'",
57 Vals: Matches[3].str().c_str());
58 if (Begin >= End)
59 return createStringError(EC: std::errc::invalid_argument,
60 Fmt: "Invalid interval: %lld >= %lld", Vals: Begin, Vals: End);
61 } else
62 // Single number.
63 End = Begin;
64
65 // Check ordering constraint (intervals must be in increasing order).
66 if (!Intervals.empty() && Begin <= Intervals.back().getEnd())
67 return createStringError(
68 EC: std::errc::invalid_argument,
69 Fmt: "Expected intervals to be in increasing order: %lld <= %lld", Vals: Begin,
70 Vals: Intervals.back().getEnd());
71
72 Intervals.push_back(Elt: IntegerInclusiveInterval(Begin, End));
73 }
74
75 return Intervals;
76}
77
78bool contains(ArrayRef<IntegerInclusiveInterval> Intervals, int64_t Value) {
79 for (const IntegerInclusiveInterval &It : Intervals) {
80 if (It.contains(Value))
81 return true;
82 }
83 return false;
84}
85
86void printIntervals(raw_ostream &OS,
87 ArrayRef<IntegerInclusiveInterval> Intervals,
88 char Separator) {
89 if (Intervals.empty()) {
90 OS << "empty";
91 return;
92 }
93
94 std::string Sep(1, Separator);
95 ListSeparator LS(Sep);
96 for (const IntegerInclusiveInterval &It : Intervals) {
97 OS << LS;
98 It.print(OS);
99 }
100}
101
102IntervalList
103mergeAdjacentIntervals(ArrayRef<IntegerInclusiveInterval> Intervals) {
104 if (Intervals.empty())
105 return {};
106
107 IntervalList Result;
108 Result.push_back(Elt: Intervals[0]);
109
110 for (const IntegerInclusiveInterval &Current : Intervals.drop_front()) {
111 IntegerInclusiveInterval &Last = Result.back();
112 // Check if current interval is adjacent to the last merged interval.
113 if (Current.getBegin() == Last.getEnd() + 1) {
114 // Merge by extending the end of the last interval.
115 Last.setEnd(Current.getEnd());
116 } else {
117 // Not adjacent, add as separate interval.
118 Result.push_back(Elt: Current);
119 }
120 }
121
122 return Result;
123}
124
125} // end namespace llvm::IntegerInclusiveIntervalUtils
126