SourceLocationIndex.h

Go to the documentation of this file.

/*$!{
* Aurora Clang AST Viewer (ACAV)
* 
* Copyright (c) 2026 Min Liu
* Copyright (c) 2026 Michael David Adams
* 
* SPDX-License-Identifier: GPL-2.0-or-later
* 
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
* 
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License along
* with this program; if not, see <https://www.gnu.org/licenses/>.
}$!*/

#pragma once
 
#include "common/FileManager.h"
#include <map>
#include <memory>
#include <vector>
 
namespace acav {
 
// Forward declarations
class AstViewNode;

struct Interval {
  unsigned beginLine;
  unsigned beginColumn;
  unsigned endLine;
  unsigned endColumn;
  AstViewNode *node; // Not owned - AstContext owns all nodes

  bool contains(unsigned line, unsigned column) const;

  bool operator<(const Interval &other) const;
};

class IntervalTree {
public:
  IntervalTree() = default;
  ~IntervalTree() = default;
 
  // Non-copyable
  IntervalTree(const IntervalTree &) = delete;
  IntervalTree &operator=(const IntervalTree &) = delete;

  void insert(Interval interval);

  void finalize();

  std::vector<AstViewNode *> query(unsigned line, unsigned column) const;

  AstViewNode *queryFirstContained(unsigned beginLine, unsigned beginColumn,
                                   unsigned endLine, unsigned endColumn) const;

  std::size_t size() const { return intervals_.size(); }
 
private:
  struct SourcePoint {
    unsigned line;
    unsigned column;
  };
 
  struct QueryNode {
    SourcePoint center;
    std::vector<Interval> byBegin;
    std::vector<Interval> byEndDescending;
    std::unique_ptr<QueryNode> left;
    std::unique_ptr<QueryNode> right;
  };
 
  std::vector<Interval> intervals_;
  std::unique_ptr<QueryNode> queryRoot_;
  bool finalized_ = false;
 
  static std::unique_ptr<QueryNode>
  buildQueryTree(std::vector<Interval> intervals);
  static void queryPoint(const QueryNode *node, SourcePoint point,
                         std::vector<AstViewNode *> &results);
  static SourcePoint beginPoint(const Interval &interval);
  static SourcePoint endPoint(const Interval &interval);
  static bool pointLess(SourcePoint lhs, SourcePoint rhs);
  static bool startsAfter(const Interval &interval, SourcePoint point);
  static bool endsBefore(const Interval &interval, SourcePoint point);
  static bool intervalEndGreater(const Interval &lhs, const Interval &rhs);
 
  unsigned getDepth(AstViewNode *node) const;
};

class SourceLocationIndex {
public:
  SourceLocationIndex() = default;
  ~SourceLocationIndex() = default;
 
  // Non-copyable (manages interval trees)
  SourceLocationIndex(const SourceLocationIndex &) = delete;
  SourceLocationIndex &operator=(const SourceLocationIndex &) = delete;

  void addNode(AstViewNode *node);

  void finalize();

  std::vector<AstViewNode *> getNodesAt(FileID fileId, unsigned line,
                                         unsigned column) const;

  AstViewNode *getFirstNodeContainedInRange(FileID fileId, unsigned beginLine,
                                            unsigned beginColumn,
                                            unsigned endLine,
                                            unsigned endColumn) const;

  std::size_t getFileCount() const { return trees_.size(); }

  std::size_t getTotalIntervals() const;

  bool hasFile(FileID fileId) const;
 
private:
  std::map<FileID, IntervalTree> trees_; // One tree per file
};
 
} // namespace acav