1 //===-- lib/Parser/provenance.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 #include "flang/Parser/provenance.h"
10 #include "flang/Common/idioms.h"
11 #include "llvm/Support/raw_ostream.h"
12 #include <algorithm>
13 #include <utility>
14 
15 namespace Fortran::parser {
16 
17 ProvenanceRangeToOffsetMappings::ProvenanceRangeToOffsetMappings() {}
18 ProvenanceRangeToOffsetMappings::~ProvenanceRangeToOffsetMappings() {}
19 
20 void ProvenanceRangeToOffsetMappings::Put(
21     ProvenanceRange range, std::size_t offset) {
22   auto fromTo{map_.equal_range(range)};
23   for (auto iter{fromTo.first}; iter != fromTo.second; ++iter) {
24     if (range == iter->first) {
25       iter->second = std::min(offset, iter->second);
26       return;
27     }
28   }
29   if (fromTo.second != map_.end()) {
30     map_.emplace_hint(fromTo.second, range, offset);
31   } else {
32     map_.emplace(range, offset);
33   }
34 }
35 
36 std::optional<std::size_t> ProvenanceRangeToOffsetMappings::Map(
37     ProvenanceRange range) const {
38   auto fromTo{map_.equal_range(range)};
39   std::optional<std::size_t> result;
40   for (auto iter{fromTo.first}; iter != fromTo.second; ++iter) {
41     ProvenanceRange that{iter->first};
42     if (that.Contains(range)) {
43       std::size_t offset{iter->second + that.MemberOffset(range.start())};
44       if (!result || offset < *result) {
45         result = offset;
46       }
47     }
48   }
49   return result;
50 }
51 
52 bool ProvenanceRangeToOffsetMappings::WhollyPrecedes::operator()(
53     ProvenanceRange before, ProvenanceRange after) const {
54   return before.start() + before.size() <= after.start();
55 }
56 
57 void OffsetToProvenanceMappings::clear() { provenanceMap_.clear(); }
58 
59 void OffsetToProvenanceMappings::swap(OffsetToProvenanceMappings &that) {
60   provenanceMap_.swap(that.provenanceMap_);
61 }
62 
63 void OffsetToProvenanceMappings::shrink_to_fit() {
64   provenanceMap_.shrink_to_fit();
65 }
66 
67 std::size_t OffsetToProvenanceMappings::SizeInBytes() const {
68   if (provenanceMap_.empty()) {
69     return 0;
70   } else {
71     const ContiguousProvenanceMapping &last{provenanceMap_.back()};
72     return last.start + last.range.size();
73   }
74 }
75 
76 void OffsetToProvenanceMappings::Put(ProvenanceRange range) {
77   if (provenanceMap_.empty()) {
78     provenanceMap_.push_back({0, range});
79   } else {
80     ContiguousProvenanceMapping &last{provenanceMap_.back()};
81     if (!last.range.AnnexIfPredecessor(range)) {
82       provenanceMap_.push_back({last.start + last.range.size(), range});
83     }
84   }
85 }
86 
87 void OffsetToProvenanceMappings::Put(const OffsetToProvenanceMappings &that) {
88   for (const auto &map : that.provenanceMap_) {
89     Put(map.range);
90   }
91 }
92 
93 ProvenanceRange OffsetToProvenanceMappings::Map(std::size_t at) const {
94   if (provenanceMap_.empty()) {
95     CHECK(at == 0);
96     return {};
97   }
98   std::size_t low{0}, count{provenanceMap_.size()};
99   while (count > 1) {
100     std::size_t mid{low + (count >> 1)};
101     if (provenanceMap_[mid].start > at) {
102       count = mid - low;
103     } else {
104       count -= mid - low;
105       low = mid;
106     }
107   }
108   std::size_t offset{at - provenanceMap_[low].start};
109   return provenanceMap_[low].range.Suffix(offset);
110 }
111 
112 void OffsetToProvenanceMappings::RemoveLastBytes(std::size_t bytes) {
113   for (; bytes > 0; provenanceMap_.pop_back()) {
114     CHECK(!provenanceMap_.empty());
115     ContiguousProvenanceMapping &last{provenanceMap_.back()};
116     std::size_t chunk{last.range.size()};
117     if (bytes < chunk) {
118       last.range = last.range.Prefix(chunk - bytes);
119       break;
120     }
121     bytes -= chunk;
122   }
123 }
124 
125 ProvenanceRangeToOffsetMappings OffsetToProvenanceMappings::Invert(
126     const AllSources &allSources) const {
127   ProvenanceRangeToOffsetMappings result;
128   for (const auto &contig : provenanceMap_) {
129     ProvenanceRange range{contig.range};
130     while (!range.empty()) {
131       ProvenanceRange source{allSources.IntersectionWithSourceFiles(range)};
132       if (source.empty()) {
133         break;
134       }
135       result.Put(
136           source, contig.start + contig.range.MemberOffset(source.start()));
137       Provenance after{source.NextAfter()};
138       if (range.Contains(after)) {
139         range = range.Suffix(range.MemberOffset(after));
140       } else {
141         break;
142       }
143     }
144   }
145   return result;
146 }
147 
148 AllSources::AllSources() : range_{1, 1} {
149   // Start the origin_ array with a dummy entry that has a forced provenance,
150   // so that provenance offset 0 remains reserved as an uninitialized
151   // value.
152   origin_.emplace_back(range_, std::string{'?'});
153 }
154 
155 AllSources::~AllSources() {}
156 
157 const char &AllSources::operator[](Provenance at) const {
158   const Origin &origin{MapToOrigin(at)};
159   return origin[origin.covers.MemberOffset(at)];
160 }
161 
162 void AllSources::AppendSearchPathDirectory(std::string directory) {
163   // gfortran and ifort append to current path, PGI prepends
164   searchPath_.push_back(directory);
165 }
166 
167 const SourceFile *AllSources::Open(std::string path, llvm::raw_ostream &error,
168     std::optional<std::string> &&prependPath) {
169   std::unique_ptr<SourceFile> source{std::make_unique<SourceFile>(encoding_)};
170   if (prependPath) {
171     // Set to "." for the initial source file; set to the directory name
172     // of the including file for #include "quoted-file" directives &
173     // INCLUDE statements.
174     searchPath_.emplace_front(std::move(*prependPath));
175   }
176   std::optional<std::string> found{LocateSourceFile(path, searchPath_)};
177   if (prependPath) {
178     searchPath_.pop_front();
179   }
180   if (!found) {
181     error << "Source file '" << path << "' was not found";
182     return nullptr;
183   } else if (source->Open(*found, error)) {
184     return ownedSourceFiles_.emplace_back(std::move(source)).get();
185   } else {
186     return nullptr;
187   }
188 }
189 
190 const SourceFile *AllSources::ReadStandardInput(llvm::raw_ostream &error) {
191   std::unique_ptr<SourceFile> source{std::make_unique<SourceFile>(encoding_)};
192   if (source->ReadStandardInput(error)) {
193     return ownedSourceFiles_.emplace_back(std::move(source)).get();
194   }
195   return nullptr;
196 }
197 
198 ProvenanceRange AllSources::AddIncludedFile(
199     const SourceFile &source, ProvenanceRange from, bool isModule) {
200   ProvenanceRange covers{range_.NextAfter(), source.bytes()};
201   CHECK(range_.AnnexIfPredecessor(covers));
202   CHECK(origin_.back().covers.ImmediatelyPrecedes(covers));
203   origin_.emplace_back(covers, source, from, isModule);
204   return covers;
205 }
206 
207 ProvenanceRange AllSources::AddMacroCall(
208     ProvenanceRange def, ProvenanceRange use, const std::string &expansion) {
209   ProvenanceRange covers{range_.NextAfter(), expansion.size()};
210   CHECK(range_.AnnexIfPredecessor(covers));
211   CHECK(origin_.back().covers.ImmediatelyPrecedes(covers));
212   origin_.emplace_back(covers, def, use, expansion);
213   return covers;
214 }
215 
216 ProvenanceRange AllSources::AddCompilerInsertion(std::string text) {
217   ProvenanceRange covers{range_.NextAfter(), text.size()};
218   CHECK(range_.AnnexIfPredecessor(covers));
219   CHECK(origin_.back().covers.ImmediatelyPrecedes(covers));
220   origin_.emplace_back(covers, text);
221   return covers;
222 }
223 
224 void AllSources::EmitMessage(llvm::raw_ostream &o,
225     const std::optional<ProvenanceRange> &range, const std::string &message,
226     bool echoSourceLine) const {
227   if (!range) {
228     o << message << '\n';
229     return;
230   }
231   CHECK(IsValid(*range));
232   const Origin &origin{MapToOrigin(range->start())};
233   std::visit(
234       common::visitors{
235           [&](const Inclusion &inc) {
236             o << inc.source.path();
237             std::size_t offset{origin.covers.MemberOffset(range->start())};
238             SourcePosition pos{inc.source.FindOffsetLineAndColumn(offset)};
239             o << ':' << pos.line << ':' << pos.column;
240             o << ": " << message << '\n';
241             if (echoSourceLine) {
242               const char *text{inc.source.content().data() +
243                   inc.source.GetLineStartOffset(pos.line)};
244               o << "  ";
245               for (const char *p{text}; *p != '\n'; ++p) {
246                 o << *p;
247               }
248               o << "\n  ";
249               for (int j{1}; j < pos.column; ++j) {
250                 char ch{text[j - 1]};
251                 o << (ch == '\t' ? '\t' : ' ');
252               }
253               o << '^';
254               if (range->size() > 1) {
255                 auto last{range->start() + range->size() - 1};
256                 if (&MapToOrigin(last) == &origin) {
257                   auto endOffset{origin.covers.MemberOffset(last)};
258                   auto endPos{inc.source.FindOffsetLineAndColumn(endOffset)};
259                   if (pos.line == endPos.line) {
260                     for (int j{pos.column}; j < endPos.column; ++j) {
261                       o << '^';
262                     }
263                   }
264                 }
265               }
266               o << '\n';
267             }
268             if (IsValid(origin.replaces)) {
269               EmitMessage(o, origin.replaces,
270                   inc.isModule ? "used here"s : "included here"s,
271                   echoSourceLine);
272             }
273           },
274           [&](const Macro &mac) {
275             EmitMessage(o, origin.replaces, message, echoSourceLine);
276             EmitMessage(
277                 o, mac.definition, "in a macro defined here", echoSourceLine);
278             if (echoSourceLine) {
279               o << "that expanded to:\n  " << mac.expansion << "\n  ";
280               for (std::size_t j{0};
281                    origin.covers.OffsetMember(j) < range->start(); ++j) {
282                 o << (mac.expansion[j] == '\t' ? '\t' : ' ');
283               }
284               o << "^\n";
285             }
286           },
287           [&](const CompilerInsertion &) { o << message << '\n'; },
288       },
289       origin.u);
290 }
291 
292 const SourceFile *AllSources::GetSourceFile(
293     Provenance at, std::size_t *offset) const {
294   const Origin &origin{MapToOrigin(at)};
295   return std::visit(common::visitors{
296                         [&](const Inclusion &inc) {
297                           if (offset) {
298                             *offset = origin.covers.MemberOffset(at);
299                           }
300                           return &inc.source;
301                         },
302                         [&](const Macro &) {
303                           return GetSourceFile(origin.replaces.start(), offset);
304                         },
305                         [offset](const CompilerInsertion &) {
306                           if (offset) {
307                             *offset = 0;
308                           }
309                           return static_cast<const SourceFile *>(nullptr);
310                         },
311                     },
312       origin.u);
313 }
314 
315 const char *AllSources::GetSource(ProvenanceRange range) const {
316   Provenance start{range.start()};
317   const Origin &origin{MapToOrigin(start)};
318   return origin.covers.Contains(range)
319       ? &origin[origin.covers.MemberOffset(start)]
320       : nullptr;
321 }
322 
323 std::optional<SourcePosition> AllSources::GetSourcePosition(
324     Provenance prov) const {
325   const Origin &origin{MapToOrigin(prov)};
326   return std::visit(
327       common::visitors{
328           [&](const Inclusion &inc) -> std::optional<SourcePosition> {
329             std::size_t offset{origin.covers.MemberOffset(prov)};
330             return inc.source.FindOffsetLineAndColumn(offset);
331           },
332           [&](const Macro &) {
333             return GetSourcePosition(origin.replaces.start());
334           },
335           [](const CompilerInsertion &) -> std::optional<SourcePosition> {
336             return std::nullopt;
337           },
338       },
339       origin.u);
340 }
341 
342 std::optional<ProvenanceRange> AllSources::GetFirstFileProvenance() const {
343   for (const auto &origin : origin_) {
344     if (std::holds_alternative<Inclusion>(origin.u)) {
345       return origin.covers;
346     }
347   }
348   return std::nullopt;
349 }
350 
351 std::string AllSources::GetPath(Provenance at) const {
352   const SourceFile *source{GetSourceFile(at)};
353   return source ? source->path() : ""s;
354 }
355 
356 int AllSources::GetLineNumber(Provenance at) const {
357   std::size_t offset{0};
358   const SourceFile *source{GetSourceFile(at, &offset)};
359   return source ? source->FindOffsetLineAndColumn(offset).line : 0;
360 }
361 
362 Provenance AllSources::CompilerInsertionProvenance(char ch) {
363   auto iter{compilerInsertionProvenance_.find(ch)};
364   if (iter != compilerInsertionProvenance_.end()) {
365     return iter->second;
366   }
367   ProvenanceRange newCharRange{AddCompilerInsertion(std::string{ch})};
368   Provenance newCharProvenance{newCharRange.start()};
369   compilerInsertionProvenance_.insert(std::make_pair(ch, newCharProvenance));
370   return newCharProvenance;
371 }
372 
373 ProvenanceRange AllSources::IntersectionWithSourceFiles(
374     ProvenanceRange range) const {
375   if (range.empty()) {
376     return {};
377   } else {
378     const Origin &origin{MapToOrigin(range.start())};
379     if (std::holds_alternative<Inclusion>(origin.u)) {
380       return range.Intersection(origin.covers);
381     } else {
382       auto skip{
383           origin.covers.size() - origin.covers.MemberOffset(range.start())};
384       return IntersectionWithSourceFiles(range.Suffix(skip));
385     }
386   }
387 }
388 
389 AllSources::Origin::Origin(ProvenanceRange r, const SourceFile &source)
390     : u{Inclusion{source}}, covers{r} {}
391 AllSources::Origin::Origin(ProvenanceRange r, const SourceFile &included,
392     ProvenanceRange from, bool isModule)
393     : u{Inclusion{included, isModule}}, covers{r}, replaces{from} {}
394 AllSources::Origin::Origin(ProvenanceRange r, ProvenanceRange def,
395     ProvenanceRange use, const std::string &expansion)
396     : u{Macro{def, expansion}}, covers{r}, replaces{use} {}
397 AllSources::Origin::Origin(ProvenanceRange r, const std::string &text)
398     : u{CompilerInsertion{text}}, covers{r} {}
399 
400 const char &AllSources::Origin::operator[](std::size_t n) const {
401   return std::visit(
402       common::visitors{
403           [n](const Inclusion &inc) -> const char & {
404             return inc.source.content()[n];
405           },
406           [n](const Macro &mac) -> const char & { return mac.expansion[n]; },
407           [n](const CompilerInsertion &ins) -> const char & {
408             return ins.text[n];
409           },
410       },
411       u);
412 }
413 
414 const AllSources::Origin &AllSources::MapToOrigin(Provenance at) const {
415   CHECK(range_.Contains(at));
416   std::size_t low{0}, count{origin_.size()};
417   while (count > 1) {
418     std::size_t mid{low + (count >> 1)};
419     if (at < origin_[mid].covers.start()) {
420       count = mid - low;
421     } else {
422       count -= mid - low;
423       low = mid;
424     }
425   }
426   CHECK(origin_[low].covers.Contains(at));
427   return origin_[low];
428 }
429 
430 std::optional<ProvenanceRange> CookedSource::GetProvenanceRange(
431     CharBlock cookedRange) const {
432   if (!AsCharBlock().Contains(cookedRange)) {
433     return std::nullopt;
434   }
435   ProvenanceRange first{provenanceMap_.Map(cookedRange.begin() - &data_[0])};
436   if (cookedRange.size() <= first.size()) {
437     return first.Prefix(cookedRange.size());
438   }
439   ProvenanceRange last{provenanceMap_.Map(cookedRange.end() - &data_[0])};
440   return {ProvenanceRange{first.start(), last.start() - first.start()}};
441 }
442 
443 std::optional<CharBlock> CookedSource::GetCharBlock(
444     ProvenanceRange range) const {
445   CHECK(!invertedMap_.empty() &&
446       "CompileProvenanceRangeToOffsetMappings not called");
447   if (auto to{invertedMap_.Map(range)}) {
448     return CharBlock{data_.c_str() + *to, range.size()};
449   } else {
450     return std::nullopt;
451   }
452 }
453 
454 std::size_t CookedSource::BufferedBytes() const { return buffer_.bytes(); }
455 
456 void CookedSource::Marshal(AllCookedSources &allCookedSources) {
457   CHECK(provenanceMap_.SizeInBytes() == buffer_.bytes());
458   provenanceMap_.Put(allCookedSources.allSources().AddCompilerInsertion(
459       "(after end of source)"));
460   data_ = buffer_.Marshal();
461   buffer_.clear();
462   allCookedSources.Register(*this);
463 }
464 
465 void CookedSource::CompileProvenanceRangeToOffsetMappings(
466     AllSources &allSources) {
467   if (invertedMap_.empty()) {
468     invertedMap_ = provenanceMap_.Invert(allSources);
469   }
470 }
471 
472 static void DumpRange(llvm::raw_ostream &o, const ProvenanceRange &r) {
473   o << "[" << r.start().offset() << ".." << r.Last().offset() << "] ("
474     << r.size() << " bytes)";
475 }
476 
477 llvm::raw_ostream &ProvenanceRangeToOffsetMappings::Dump(
478     llvm::raw_ostream &o) const {
479   for (const auto &m : map_) {
480     o << "provenances ";
481     DumpRange(o, m.first);
482     o << " -> offsets [" << m.second << ".." << (m.second + m.first.size() - 1)
483       << "]\n";
484   }
485   return o;
486 }
487 
488 llvm::raw_ostream &OffsetToProvenanceMappings::Dump(
489     llvm::raw_ostream &o) const {
490   for (const ContiguousProvenanceMapping &m : provenanceMap_) {
491     std::size_t n{m.range.size()};
492     o << "offsets [" << m.start << ".." << (m.start + n - 1)
493       << "] -> provenances ";
494     DumpRange(o, m.range);
495     o << '\n';
496   }
497   return o;
498 }
499 
500 llvm::raw_ostream &AllSources::Dump(llvm::raw_ostream &o) const {
501   o << "AllSources range_ ";
502   DumpRange(o, range_);
503   o << '\n';
504   for (const Origin &m : origin_) {
505     o << "   ";
506     DumpRange(o, m.covers);
507     o << " -> ";
508     std::visit(common::visitors{
509                    [&](const Inclusion &inc) {
510                      if (inc.isModule) {
511                        o << "module ";
512                      }
513                      o << "file " << inc.source.path();
514                    },
515                    [&](const Macro &mac) { o << "macro " << mac.expansion; },
516                    [&](const CompilerInsertion &ins) {
517                      o << "compiler '" << ins.text << '\'';
518                      if (ins.text.length() == 1) {
519                        int ch = ins.text[0];
520                        o << "(0x";
521                        o.write_hex(ch & 0xff) << ")";
522                      }
523                    },
524                },
525         m.u);
526     if (IsValid(m.replaces)) {
527       o << " replaces ";
528       DumpRange(o, m.replaces);
529     }
530     o << '\n';
531   }
532   return o;
533 }
534 
535 llvm::raw_ostream &CookedSource::Dump(llvm::raw_ostream &o) const {
536   o << "CookedSource::provenanceMap_:\n";
537   provenanceMap_.Dump(o);
538   o << "CookedSource::invertedMap_:\n";
539   invertedMap_.Dump(o);
540   return o;
541 }
542 
543 AllCookedSources::AllCookedSources(AllSources &s) : allSources_{s} {}
544 AllCookedSources::~AllCookedSources() {}
545 
546 CookedSource &AllCookedSources::NewCookedSource() {
547   return cooked_.emplace_back();
548 }
549 
550 const CookedSource *AllCookedSources::Find(CharBlock x) const {
551   auto pair{index_.equal_range(x)};
552   for (auto iter{pair.first}; iter != pair.second; ++iter) {
553     if (iter->second.AsCharBlock().Contains(x)) {
554       return &iter->second;
555     }
556   }
557   return nullptr;
558 }
559 
560 std::optional<ProvenanceRange> AllCookedSources::GetProvenanceRange(
561     CharBlock cb) const {
562   if (const CookedSource * c{Find(cb)}) {
563     return c->GetProvenanceRange(cb);
564   } else {
565     return std::nullopt;
566   }
567 }
568 
569 std::optional<CharBlock> AllCookedSources::GetCharBlockFromLineAndColumns(
570     int line, int startColumn, int endColumn) const {
571   // 2nd column is exclusive, meaning it is target column + 1.
572   CHECK(line > 0 && startColumn > 0 && endColumn > 0);
573   CHECK(startColumn < endColumn);
574   auto provenanceStart{allSources_.GetFirstFileProvenance().value().start()};
575   if (auto sourceFile{allSources_.GetSourceFile(provenanceStart)}) {
576     CHECK(line <= static_cast<int>(sourceFile->lines()));
577     return GetCharBlock(ProvenanceRange(sourceFile->GetLineStartOffset(line) +
578             provenanceStart.offset() + startColumn - 1,
579         endColumn - startColumn));
580   }
581   return std::nullopt;
582 }
583 
584 std::optional<std::pair<SourcePosition, SourcePosition>>
585 AllCookedSources::GetSourcePositionRange(CharBlock cookedRange) const {
586   if (auto range{GetProvenanceRange(cookedRange)}) {
587     if (auto firstOffset{allSources_.GetSourcePosition(range->start())}) {
588       if (auto secondOffset{
589               allSources_.GetSourcePosition(range->start() + range->size())}) {
590         return std::pair{*firstOffset, *secondOffset};
591       }
592     }
593   }
594   return std::nullopt;
595 }
596 
597 std::optional<CharBlock> AllCookedSources::GetCharBlock(
598     ProvenanceRange range) const {
599   for (const auto &c : cooked_) {
600     if (auto result{c.GetCharBlock(range)}) {
601       return result;
602     }
603   }
604   return std::nullopt;
605 }
606 
607 void AllCookedSources::Dump(llvm::raw_ostream &o) const {
608   o << "AllSources:\n";
609   allSources_.Dump(o);
610   for (const auto &c : cooked_) {
611     c.Dump(o);
612   }
613 }
614 
615 bool AllCookedSources::Precedes(CharBlock x, CharBlock y) const {
616   if (const CookedSource * xSource{Find(x)}) {
617     if (xSource->AsCharBlock().Contains(y)) {
618       return x.begin() < y.begin();
619     } else if (const CookedSource * ySource{Find(y)}) {
620       return xSource->number() < ySource->number();
621     } else {
622       return true; // by fiat, all cooked source < anything outside
623     }
624   } else if (Find(y)) {
625     return false;
626   } else {
627     // Both names are compiler-created (SaveTempName).
628     return x < y;
629   }
630 }
631 
632 void AllCookedSources::Register(CookedSource &cooked) {
633   index_.emplace(cooked.AsCharBlock(), cooked);
634   cooked.set_number(static_cast<int>(index_.size()));
635 }
636 
637 } // namespace Fortran::parser
638