1//===- SrcEditMerge.cpp ---------------------------------------------------===//
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// clang-ssaf-src-edit-merge: per-LU source-edit YAML merge tool.
10//
11// Reads N per-TU clang::tooling::TranslationUnitReplacements YAML files,
12// deduplicates and merges them into one flat, conflict-resolved list (see
13// "Conflict policy" below), and writes a single merged YAML spanning all N
14// TUs. The tool does NOT write source files — applying the merge result is
15// the caller's responsibility (typically clang-reforge invokes
16// `clang-apply-replacements` after this tool returns).
17//
18// Conflict policy: this tool implements a drop-all policy. For each file, a
19// maximal group of transitively-overlapping input Replacements (a cluster)
20// is computed directly from the input; if a cluster has more than one
21// member, every member is removed from the merged output — not just enough
22// of them to resolve the overlap. A one-line stderr summary is emitted per
23// dropped cluster, and the tool still exits 0. Any input file that does not
24// exist on disk is excluded entirely from the merged output.
25//
26//===----------------------------------------------------------------------===//
27
28#include "clang/Basic/Version.h"
29#include "clang/Tooling/ReplacementsYaml.h" // IWYU pragma: keep
30#include "llvm/ADT/ArrayRef.h"
31#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/SmallString.h"
33#include "llvm/ADT/StringRef.h"
34#include "llvm/Support/CommandLine.h"
35#include "llvm/Support/Error.h"
36#include "llvm/Support/ErrorOr.h"
37#include "llvm/Support/FileSystem.h"
38#include "llvm/Support/FormatVariadic.h"
39#include "llvm/Support/InitLLVM.h"
40#include "llvm/Support/JSON.h"
41#include "llvm/Support/MemoryBuffer.h"
42#include "llvm/Support/Path.h"
43#include "llvm/Support/YAMLTraits.h"
44#include "llvm/Support/raw_ostream.h"
45
46#include <algorithm>
47#include <map>
48#include <set>
49#include <string>
50#include <utility>
51#include <vector>
52
53namespace {
54
55namespace cl = llvm::cl;
56
57//===----------------------------------------------------------------------===//
58// Error Messages
59//===----------------------------------------------------------------------===//
60
61constexpr const char *ToolName = "clang-ssaf-src-edit-merge";
62
63constexpr const char *CannotReadInput = "cannot read {0}: {1}";
64
65constexpr const char *InvalidReplacementsYaml =
66 "{0}: invalid TranslationUnitReplacements YAML";
67
68constexpr const char *ConflictClusterSummary =
69 "conflict: skipped {0} overlapping replacement(s) at {1}:{2}";
70
71constexpr const char *CannotWriteFile = "cannot write {0}";
72
73constexpr const char *WriteErrorOnFile = "write error on {0}";
74
75constexpr const char *CannotWriteOutput = "cannot write {0}: {1}";
76
77constexpr const char *MissingReplacementFile =
78 "{0}: file does not exist; skipping its replacement(s)";
79
80constexpr const char *CandidateEditMessage = "candidate edit: \"{0}\"";
81
82constexpr const char *ConflictSarifMessage =
83 "{0} overlapping replacement(s) at {1} byte {2} were dropped; resolve "
84 "manually.";
85
86cl::OptionCategory MergeCategory("clang-ssaf-src-edit-merge options");
87
88cl::list<std::string> InputFiles(cl::Positional, cl::OneOrMore,
89 cl::desc("<input.yaml>..."),
90 cl::cat(MergeCategory));
91
92cl::opt<std::string> OutputFile("o", cl::Required, cl::value_desc("path"),
93 cl::desc("Output path for the merged YAML."),
94 cl::cat(MergeCategory));
95
96cl::opt<std::string> SarifConflictsOut(
97 "sarif-conflicts-out", cl::value_desc("path"),
98 cl::desc("Optional path. When supplied, write a SARIF document "
99 "listing conflict clusters dropped from the merged output."),
100 cl::cat(MergeCategory));
101
102/// Read one input YAML into a TranslationUnitReplacements.
103///
104/// Returns true on success. On failure, prints a one-line diagnostic to
105/// stderr and returns false; the caller surfaces this as a non-zero exit.
106bool readInput(llvm::StringRef Path,
107 clang::tooling::TranslationUnitReplacements &Out) {
108 llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buffer =
109 llvm::MemoryBuffer::getFile(Filename: Path);
110 if (std::error_code EC = Buffer.getError()) {
111 llvm::errs() << ToolName << ": "
112 << llvm::formatv(Fmt: CannotReadInput, Vals&: Path, Vals: EC.message()) << "\n";
113 return false;
114 }
115 llvm::yaml::Input YAML(Buffer.get()->getBuffer());
116 YAML >> Out;
117 if (YAML.error()) {
118 llvm::errs() << ToolName << ": "
119 << llvm::formatv(Fmt: InvalidReplacementsYaml, Vals&: Path) << "\n";
120 return false;
121 }
122 return true;
123}
124
125/// The merged output: a flat list of Replacements spanning every input file.
126///
127/// Deliberately not clang::tooling::TranslationUnitReplacements: that type
128/// represents one TU's replacements, but this represents the drop-all-policy
129/// result of merging N TUs' worth of edits. `MappingTraits` below serializes
130/// this to the identical YAML shape (the same two required keys,
131/// MainSourceFile and Replacements) so clang-apply-replacements — which only
132/// knows how to read that shape — can still consume the output; only the
133/// C++ type stops making a claim about the data it doesn't hold.
134/// MainSourceFile is populated on a best-effort basis (computeMainSourceFile,
135/// below) purely for wire compatibility: nothing in the merge/apply pipeline
136/// reads it back.
137struct MergedReplacements {
138 std::string MainSourceFile;
139 std::vector<clang::tooling::Replacement> Replacements;
140};
141
142/// Compute the shared MainSourceFile across inputs.
143///
144/// Per spec: if every input declares the same MainSourceFile, use that;
145/// otherwise use the empty string.
146std::string computeMainSourceFile(
147 const std::vector<clang::tooling::TranslationUnitReplacements> &TUs) {
148 if (TUs.empty())
149 return "";
150 const std::string &First = TUs.front().MainSourceFile;
151 for (const auto &TU : TUs)
152 if (TU.MainSourceFile != First)
153 return "";
154 return First;
155}
156
157/// Build the conflict cluster list from the merged input key set.
158///
159/// `InputKeysByFile` is every input Replacement with length > 0, grouped by
160/// file. Zero-length insertions are excluded by the caller because they never
161/// overlap anything and are a no-op to apply, so they can never affect this
162/// function's clustering.
163///
164/// A cluster is a maximal connected component of one file's input
165/// replacements whose [offset, offset+length) byte ranges transitively
166/// overlap.
167///
168/// The walk merges into the current cluster whenever
169/// key.offset < lastEnd, where
170/// lastEnd = max(member.offset + member.length) across cluster members.
171/// Otherwise the current cluster closes and a new one opens.
172///
173/// Only clusters of size > 1 are returned; singletons are not conflicts.
174///
175/// Each returned cluster's member list is sorted by (offset, length, text);
176/// the cluster list itself is sorted by (file, min-offset) ascending. This
177/// pins iteration order for both stderr cluster lines and (in a follow-on
178/// task) the SARIF results array.
179std::vector<std::vector<clang::tooling::Replacement>> buildConflictClusters(
180 const std::map<std::string, std::set<clang::tooling::Replacement>>
181 &InputKeysByFile) {
182 std::vector<std::vector<clang::tooling::Replacement>> Clusters;
183 for (auto &Entry : InputKeysByFile) {
184 // Keys is a std::set<Replacement>, so it's already ordered by
185 // Replacement::operator< — the (offset, length, text) order the cluster
186 // walk below needs, since every entry here shares Entry.first as its
187 // file path.
188 auto &Keys = Entry.second;
189
190 std::vector<clang::tooling::Replacement> Current;
191 unsigned LastEnd = 0;
192 auto Flush = [&]() {
193 if (Current.size() > 1)
194 Clusters.push_back(x: std::move(Current));
195 Current.clear();
196 LastEnd = 0;
197 };
198
199 for (const clang::tooling::Replacement &K : Keys) {
200 if (Current.empty()) {
201 Current.push_back(x: K);
202 LastEnd = K.getOffset() + K.getLength();
203 continue;
204 }
205 if (K.getOffset() < LastEnd) {
206 Current.push_back(x: K);
207 LastEnd = std::max(a: LastEnd, b: K.getOffset() + K.getLength());
208 } else {
209 Flush();
210 Current.push_back(x: K);
211 LastEnd = K.getOffset() + K.getLength();
212 }
213 }
214 Flush();
215 }
216
217 // Pin cluster-list order by (file, min-offset) ascending.
218 llvm::sort(C&: Clusters, Comp: [](const std::vector<clang::tooling::Replacement> &A,
219 const std::vector<clang::tooling::Replacement> &B) {
220 if (A.front().getFilePath() != B.front().getFilePath())
221 return A.front().getFilePath() < B.front().getFilePath();
222 return A.front().getOffset() < B.front().getOffset();
223 });
224
225 return Clusters;
226}
227
228/// Emit one stderr line per conflict cluster.
229///
230/// Precondition: `Clusters` is sorted by (file, min-offset) ascending —
231/// guaranteed by buildConflictClusters, the only place Clusters is built.
232void emitConflictClusterLines(
233 const std::vector<std::vector<clang::tooling::Replacement>> &Clusters) {
234 for (const auto &Cluster : Clusters) {
235 llvm::errs() << llvm::formatv(Fmt: ConflictClusterSummary, Vals: Cluster.size(),
236 Vals: Cluster.front().getFilePath(),
237 Vals: Cluster.front().getOffset())
238 << "\n";
239 }
240}
241
242/// Canonicalize a Replacement's `FilePath` into an absolute `file://` URI.
243///
244/// Fallback chain:
245/// 1. `llvm::sys::fs::real_path` — resolves symlinks and yields an
246/// absolute path. Only succeeds if the file exists on disk.
247/// 2. `llvm::sys::fs::make_absolute` — succeeds for non-existent paths
248/// too; used for synthetic test fixtures whose FilePath may name a
249/// file that the merger never opened.
250/// 3. Raw `FilePath` — last-resort fallback if both of the above fail.
251/// Emits a syntactically valid `file://` URI even if the underlying
252/// path is relative, matching the SARIF requirement's "absolute"
253/// promise loosely (downstream tooling that needs strict absolute
254/// URIs SHOULD canonicalize on its end if the disk state permits).
255std::string canonicalizeToFileUri(llvm::StringRef FilePath) {
256 llvm::SmallString<256> Buf;
257 if (!llvm::sys::fs::real_path(path: FilePath, output&: Buf))
258 return "file://" + llvm::sys::path::convert_to_slash(path: Buf);
259 Buf.assign(in_start: FilePath.begin(), in_end: FilePath.end());
260 if (!llvm::sys::fs::make_absolute(path&: Buf))
261 return "file://" + llvm::sys::path::convert_to_slash(path: Buf);
262 return "file://" + llvm::sys::path::convert_to_slash(path: FilePath);
263}
264
265/// Emit a SARIF document at `Path` listing every conflict cluster.
266///
267/// `Clusters` SHALL be pre-sorted by `(file, min-offset)` ascending by the
268/// caller; this emitter walks them in order to populate
269/// `runs[0].results[]`. Within each cluster, `relatedLocations[]` is
270/// sorted locally by `(byteLength, candidate-text)` ascending per the
271/// "SARIF conflict report" requirement.
272///
273/// Even when `Clusters` is empty, this writes a well-formed SARIF
274/// document with `runs[0].results: []`. The file's presence is the
275/// "merger ran with conflict reporting requested" signal.
276llvm::Error emitConflictSarif(
277 llvm::StringRef Path,
278 llvm::ArrayRef<std::vector<clang::tooling::Replacement>> Clusters) {
279 llvm::json::Array Results;
280 Results.reserve(S: Clusters.size());
281
282 for (const auto &Cluster : Clusters) {
283 const clang::tooling::Replacement &Min = Cluster.front();
284 std::string Uri = canonicalizeToFileUri(FilePath: Min.getFilePath());
285
286 // Re-sort cluster members locally by (byteLength, text) ascending.
287 std::vector<clang::tooling::Replacement> Sorted(Cluster.begin(),
288 Cluster.end());
289 llvm::sort(C&: Sorted, Comp: [](const clang::tooling::Replacement &A,
290 const clang::tooling::Replacement &B) {
291 if (A.getLength() != B.getLength())
292 return A.getLength() < B.getLength();
293 return A.getReplacementText() < B.getReplacementText();
294 });
295
296 llvm::json::Array RelatedLocations;
297 RelatedLocations.reserve(S: Sorted.size());
298 for (size_t I = 0; I < Sorted.size(); ++I) {
299 const clang::tooling::Replacement &K = Sorted[I];
300 RelatedLocations.push_back(E: llvm::json::Object{
301 {.K: "id", .V: static_cast<int64_t>(I + 1)},
302 {.K: "physicalLocation",
303 .V: llvm::json::Object{
304 {.K: "artifactLocation", .V: llvm::json::Object{{.K: "uri", .V: Uri}}},
305 {.K: "region",
306 .V: llvm::json::Object{
307 {.K: "byteOffset", .V: static_cast<int64_t>(K.getOffset())},
308 {.K: "byteLength", .V: static_cast<int64_t>(K.getLength())}}}}},
309 {.K: "message",
310 .V: llvm::json::Object{{.K: "text", .V: llvm::formatv(Fmt: CandidateEditMessage,
311 Vals: K.getReplacementText())
312 .str()}}}});
313 }
314
315 std::string MessageText =
316 llvm::formatv(Fmt: ConflictSarifMessage, Vals: Cluster.size(), Vals&: Uri,
317 Vals: Min.getOffset())
318 .str();
319
320 Results.push_back(E: llvm::json::Object{
321 {.K: "ruleId", .V: "clang-reforge-replacement-conflict"},
322 {.K: "level", .V: "error"},
323 {.K: "message", .V: llvm::json::Object{{.K: "text", .V: MessageText}}},
324 {.K: "locations",
325 .V: llvm::json::Array{llvm::json::Object{
326 {.K: "physicalLocation",
327 .V: llvm::json::Object{
328 {.K: "artifactLocation", .V: llvm::json::Object{{.K: "uri", .V: Uri}}},
329 {.K: "region", .V: llvm::json::Object{{.K: "byteOffset",
330 .V: static_cast<int64_t>(
331 Min.getOffset())}}}}}}}},
332 {.K: "relatedLocations", .V: std::move(RelatedLocations)}});
333 }
334
335 llvm::json::Value Doc = llvm::json::Object{
336 {.K: "version", .V: "2.1.0"},
337 {.K: "$schema", .V: "https://json.schemastore.org/sarif-2.1.0.json"},
338 {.K: "runs",
339 .V: llvm::json::Array{llvm::json::Object{
340 {.K: "tool",
341 .V: llvm::json::Object{
342 {.K: "driver",
343 .V: llvm::json::Object{{.K: "name", .V: ToolName},
344 {.K: "version", CLANG_VERSION_STRING}}}}},
345 {.K: "results", .V: std::move(Results)}}}}};
346
347 std::error_code EC;
348 llvm::raw_fd_ostream OS(Path, EC, llvm::sys::fs::OF_Text);
349 if (EC)
350 return llvm::createStringError(EC,
351 S: llvm::formatv(Fmt: CannotWriteFile, Vals&: Path).str());
352 // Pretty-print with indent 2 via the json::Value format_provider.
353 OS << llvm::formatv(Fmt: "{0:2}", Vals&: Doc) << "\n";
354 OS.flush();
355 if (OS.has_error())
356 return llvm::createStringError(EC: OS.error(),
357 S: llvm::formatv(Fmt: WriteErrorOnFile, Vals&: Path).str());
358 return llvm::Error::success();
359}
360
361/// Returns whether `Path`'s parent directory exists, so a bad `-o` or
362/// `--sarif-conflicts-out` path can be rejected before any merge work runs.
363/// A `Path` with no directory component (e.g. a bare file name) is treated
364/// as valid — it names a file in the current directory. This is a
365/// best-effort check, not a substitute for handling the real open() failure:
366/// it cannot catch permission errors or a race between the check and the
367/// eventual write.
368bool parentDirectoryExists(llvm::StringRef Path) {
369 llvm::StringRef Parent = llvm::sys::path::parent_path(path: Path);
370 return Parent.empty() || llvm::sys::fs::is_directory(Path: Parent);
371}
372
373} // namespace
374
375namespace llvm {
376namespace yaml {
377/// Specialized MappingTraits to describe how a MergedReplacements is
378/// (de)serialized. Mirrors MappingTraits<TranslationUnitReplacements> in
379/// ReplacementsYaml.h exactly, key-for-key, for wire compatibility.
380template <> struct MappingTraits<MergedReplacements> {
381 static void mapping(IO &Io, MergedReplacements &Doc) {
382 Io.mapRequired(Key: "MainSourceFile", Val&: Doc.MainSourceFile);
383 Io.mapRequired(Key: "Replacements", Val&: Doc.Replacements);
384 }
385};
386} // namespace yaml
387} // namespace llvm
388
389int main(int argc, const char **argv) {
390 llvm::InitLLVM X(argc, argv);
391 cl::HideUnrelatedOptions(Category&: MergeCategory);
392 cl::ParseCommandLineOptions(
393 argc, argv,
394 Overview: "clang-ssaf-src-edit-merge: merge per-TU TranslationUnitReplacements "
395 "YAML files for one link unit into a single merged YAML. Does not "
396 "write source files; the apply step is the caller's responsibility.\n");
397
398 // Validate the command-line parameters that can be checked without
399 // reading any input, so a bad -o or --sarif-conflicts-out path is rejected
400 // before the (potentially expensive) merge work below runs.
401 if (!parentDirectoryExists(Path: OutputFile)) {
402 llvm::errs() << ToolName << ": "
403 << llvm::formatv(Fmt: CannotWriteFile, Vals&: OutputFile) << "\n";
404 return 1;
405 }
406 if (!SarifConflictsOut.empty() && !parentDirectoryExists(Path: SarifConflictsOut)) {
407 llvm::errs() << ToolName << ": "
408 << llvm::formatv(Fmt: CannotWriteFile, Vals&: SarifConflictsOut) << "\n";
409 return 1;
410 }
411
412 // Read all inputs.
413 std::vector<clang::tooling::TranslationUnitReplacements> TUs;
414 TUs.reserve(n: InputFiles.size());
415 for (const std::string &Path : InputFiles) {
416 clang::tooling::TranslationUnitReplacements TU;
417 if (!readInput(Path, Out&: TU))
418 return 1;
419 TUs.push_back(x: std::move(TU));
420 }
421
422 // Pre-deduplicate identical replacements across all input TUs.
423 //
424 // This loop keeps a running set of every (file, offset, length, text)
425 // tuple already kept across all TUs and drops
426 // any later Replacement that matches one already kept, so each distinct
427 // Replacement is considered exactly once below. The first occurrence (in
428 // input-file order, then within-file order) wins; later duplicates are
429 // byte-identical to it, so which one is "first" is observationally moot.
430 {
431 std::set<clang::tooling::Replacement> SeenKeys;
432 for (auto &TU : TUs) {
433 std::vector<clang::tooling::Replacement> Unique;
434 Unique.reserve(n: TU.Replacements.size());
435 for (const clang::tooling::Replacement &R : TU.Replacements) {
436 if (SeenKeys.insert(x: R).second)
437 Unique.push_back(x: R);
438 }
439 TU.Replacements = std::move(Unique);
440 }
441 }
442
443 // Determine which input files exist on disk. A Replacement targeting a
444 // file that doesn't exist can never be applied, so every Replacement
445 // targeting that file is excluded from the merged output.
446 std::set<std::string> MissingFiles;
447 {
448 std::set<std::string> AllFiles;
449 for (const auto &TU : TUs)
450 for (const auto &R : TU.Replacements)
451 AllFiles.insert(x: R.getFilePath().str());
452 for (const std::string &F : AllFiles)
453 if (!llvm::sys::fs::exists(Path: F))
454 MissingFiles.insert(x: F);
455 }
456 for (const std::string &F : MissingFiles)
457 llvm::errs() << ToolName << ": " << llvm::formatv(Fmt: MissingReplacementFile, Vals: F)
458 << "\n";
459
460 // Split every surviving-candidate Replacement by file. Zero-length
461 // insertions go straight into SurvivorsByFile — they can never overlap
462 // anything, so they're never at risk of being dropped. Length > 0 entries
463 // go into InputKeysByFile, the input to buildConflictClusters, which is
464 // the sole authority on which of them conflict.
465 std::map<std::string, std::set<clang::tooling::Replacement>> SurvivorsByFile;
466 std::map<std::string, std::set<clang::tooling::Replacement>> InputKeysByFile;
467 for (const auto &TU : TUs) {
468 for (const auto &R : TU.Replacements) {
469 if (MissingFiles.count(x: R.getFilePath().str()))
470 continue;
471 if (R.getLength() == 0)
472 SurvivorsByFile[R.getFilePath().str()].insert(x: R);
473 else
474 InputKeysByFile[R.getFilePath().str()].insert(x: R);
475 }
476 }
477
478 // Build conflict clusters — the sole authority on both what gets dropped
479 // and what gets reported. There is no separate merge step to disagree
480 // with it.
481 std::vector<std::vector<clang::tooling::Replacement>> Clusters =
482 buildConflictClusters(InputKeysByFile);
483
484 // Every Replacement that's a member of a (size > 1) cluster is dropped;
485 // everything else in InputKeysByFile survives into SurvivorsByFile.
486 std::set<clang::tooling::Replacement> ClusterMembers;
487 for (const auto &Cluster : Clusters)
488 for (const clang::tooling::Replacement &K : Cluster)
489 ClusterMembers.insert(x: K);
490 for (auto &Entry : InputKeysByFile)
491 for (const clang::tooling::Replacement &R : Entry.second)
492 if (!ClusterMembers.count(x: R))
493 SurvivorsByFile[Entry.first].insert(x: R);
494
495 // Flatten SurvivorsByFile into the merged output. Iterating a std::map of
496 // std::sets yields (file, then offset/length/text) order deterministically,
497 // regardless of argv or input-file order.
498 MergedReplacements OutDoc;
499 OutDoc.MainSourceFile = computeMainSourceFile(TUs);
500 for (auto &Entry : SurvivorsByFile)
501 for (const clang::tooling::Replacement &R : Entry.second)
502 OutDoc.Replacements.push_back(x: R);
503
504 // Emit stderr cluster lines. Clusters was sorted by (file, min-offset)
505 // ascending inside buildConflictClusters.
506 emitConflictClusterLines(Clusters);
507
508 // When --sarif-conflicts-out=<path> was supplied, write the SARIF
509 // document. An empty Clusters still produces a well-formed SARIF with
510 // results: [] — the file's presence is the signal that conflict
511 // reporting was requested. Flag-omitted skips emission entirely; no file
512 // is created at any path.
513 if (!SarifConflictsOut.empty()) {
514 if (llvm::Error E = emitConflictSarif(Path: SarifConflictsOut, Clusters)) {
515 llvm::errs() << ToolName << ": " << llvm::toString(E: std::move(E)) << "\n";
516 return 1;
517 }
518 }
519
520 // Write merged YAML (truncate-and-overwrite per spec).
521 std::error_code EC;
522 llvm::raw_fd_ostream OutStream(OutputFile, EC, llvm::sys::fs::OF_Text);
523 if (EC) {
524 llvm::errs() << ToolName << ": "
525 << llvm::formatv(Fmt: CannotWriteOutput, Vals&: OutputFile, Vals: EC.message())
526 << "\n";
527 return 1;
528 }
529 llvm::yaml::Output YAML(OutStream);
530 YAML << OutDoc;
531 OutStream.flush();
532 if (OutStream.has_error()) {
533 llvm::errs() << ToolName << ": "
534 << llvm::formatv(Fmt: WriteErrorOnFile, Vals&: OutputFile) << "\n";
535 return 1;
536 }
537
538 return 0;
539}
540