Skip to content
This repository was archived by the owner on Jun 4, 2026. It is now read-only.

rfc-740-accept-scip-in-the-backend.md

Latest commit

 

History

History
378 lines (339 loc) · 19.3 KB

rfc-740-accept-scip-in-the-backend.md

File metadata and controls

378 lines (339 loc) · 19.3 KB
Raw

RFC 740 WIP: Accept SCIP in the backend

Author: Eric Fritz
Date: Sep 27, 2022
Status: WIP

Background

We currently have a database schema to specifically store processed code intelligence data. This is a separate schema as it has very different update properties than the rest of the Sourcegraph database. We do bulk insertion of large payloads as we process user or automated uploads.

We access and update this data via the LSIFStore interface. This interface and the database schema are designed in a way to answer our current code navigation queries effectively and store payloads that are processed from LSIF graphs.

SCIP is a protocol (defined here) that improves on LSIF. Our new indexers output SCIP rather than LSIF, and we have abandoned any plans to extend LSIF further than we already have to adopt new features. Our upload mechanism will convert SCIP to LSIF on the fly prior to uploading it to the Sourcegraph instance. In order to take advantage of data available in SCIP but not LSIF, we need to understand it as a first-class protocol on the backend.

Disk usage required for a non-trivial amount of precise code intelligence is high and reported as an issue by several customers. Storing SCIP payloads instead of LSIF payloads will bring inherent determinism to our correlation process, allowing us to deduplicate data that doesn’t change over time. This wasn’t possible with the structure of LSIF, which required us to determine the graph isomorphism between two indexes. Adopting SCIP will solve coarse-grained data sharing as a by-product of its adoption, and will set the stage for incremental indexing. Both of these are problems that we were unable to solve with the previous technical landscape.

Proposal

This proposal primarily concerns itself with the removal of LSIF knowledge from our backend, to allow us to focus solely on SCIP and its evolution as a first-class and ubiquitous transport mechanism within the Sourcegraph ecosystem. This proposal is informed by future access patterns, but does not suggest a final solution for how we store this data. We fully expect this proposal to be followed by another one radically changing what data is linked/indexed and how we store that in a scalable way.

This section is organized into four sections. The first two sections detail the current interface, and database schema/query patterns used to fulfill that interface. The second two sections detail a proposed interface and database schema to fulfill the modified interface.

The implementation plan laid out in the following section outlines how we will move from the LSIF-centric tables and interfaces to the SCIP-centric ones. Of particular note is that the new interface must have a superset of capability of the current interface (as we do not want to change above the lsifstore layer).

Once this transition has been completed, we can completely wreck and rewrite the entire codenav data vertical, but we cannot make meaningful refactor progress or feature progression until we are no longer dealing with the lowest common denominator of LSIF data.

Current LSIF-centric interface design

The following methods are defined on the interface to a single LSIF dump (a processed upload):

  • GetPathExists
    • Signature: Given an index and a text document path, determine if there is data for the text document.
    • Steps:
      • Load any data from the document
  • GetStencil
    • Signature: Given an index and a text document path, return the set of ranges for which there is data.
    • Steps:
      • Load ranges from the document
      • Return flattened ranges
  • GetRanges
    • Signature: Given an index, a text document path, and a range of line offsets, return index-local data about each occurrence within the visible window. This includes hover text, documentation, reference, and implementation locations within the same index.
    • Steps:
      • Load ranges and hovers from the document
      • Search for ranges falling in the given window
      • Hydrate each range’s definition, reference, and implementation identifier with the set of locations within the same text document, by following the steps for the methods GetXLocations, described below.
      • Return the hydrated ranges
  • GetHover
    • Signature: Given an index, a text document path, and an exact position within the text document, return the hover text data associated with the smallest range enclosing that position.
    • Steps:
      • Load ranges and hovers from the document
      • Search for ranges matching the input position
      • Return the hover text associated with those ranges
  • Get{Definition,Reference,Implementation}Locations
    • Signature: Given an index, a text document path, and an exact position within the text document, return the set of locations that define, reference, or implement the symbol occurring at that position.
    • Steps:
      • Load ranges from the document
      • Search for ranges matching the input position
      • Extract the relevant LSIF ResultSet identifiers from matching ranges
      • Each result set identifier maps to a particular result chunk. Load each of the chunks to get a matching document identifier/range identifier pair.
      • Load each matching document to map the range identifier to a location within the document and return the resulting locations
  • GetDiagnostics
    • Signature: Given an index, a path prefix, and pagination bounds (limit, offset), return the page of diagnostics for text documents matching that prefix described by those bounds.
    • Steps:
      • Load diagnostics from the documents matching the path prefix. We use the field num_diagnostics to ensure we can paginate by diagnostic results, not by the containing document or index.
      • Extract and return the page of matching diagnostics
  • GetMonikersByPosition
    • Signature: Given an index, a text document path, and an exact position within the text document, return the set of monikers attached to the symbol occurring at that position.
    • Steps:
      • Load ranges and monikers from the document
      • Search for ranges matching the input position
      • Return the monikers associated with those ranges
  • GetBulkMonikerLocations
    • Signature: Given a set of indexes, a relationship (definition, reference, implementation), a set of monikers, and pagination bounds (limit, offset), return the page of locations described by those bounds. Each location will conform to the target relationship to one of the supplied monikers (i.e., the {definitions, references, implementations} of these monikers within these indexes).
    • Steps:
      • Search over lsif_data_{relationship} matching both:
        • One of the given index identifiers
        • One of the given monikers (scheme, identifier pairs)
      • Return location results bucketed by moniker
  • GetPackageInformation
    • Signature: Given an index, a text document path, and a package information identifier within that text document, return the package information payload matching that identifier.
    • Steps:
      • Load packages from the document
      • Return the matching package

Current LSIF-centric schema design

The (primary) tables used to store processed LSIF tables are structured as follows. Unlisted tables include ways to efficiently find processed uploads (referred to here as dumps) with a given schema version so that they can be migrated to a newer format in the background via out-of-band migrations.

  • lsif_data_documents
    • Fields:
      • dump_id integer, path text
      • schema_version integer
      • ranges bytea
      • hovers bytea
      • monikers bytea
      • packages bytea
      • diagnostics bytea, num_diagnostics integer
    • Indexes:
      • dump_id, path form the PK
  • lsif_data_result_chunks
    • Fields:
      • dump_id integer, idx integer
      • data bytea
    • Indexes:
      • dump_id, idx form the PK
  • lsif_data_{definitions,references,implementations}
    • Fields:
      • dump_id integer, scheme text, identifier text
      • schema_version integer
    • Indexes:
      • dump_id, scheme, identifier form the PK

The query patterns used in code navigation can be simplified to the following:

  • Get all data (of a particular type) about a text document given an index-root relative path.
    • Table: lsif_data_documents
    • Key: dump_id, path
    • Returns: One or more of the following (each is an id -> payload map). Each of the fields have been split out to reduce network traffic when fetching irrelevant fields. For example, diagnostics are not needed to resolve hover text, and only the map from LSIF identifiers to hovers needed to be transported and deserialized.
      • Ranges (position; result definition, reference, hover result, and moniker IDs)
      • Hovers (string)
      • Monikers (kind, scheme, identifier, package reference)
      • Packages (name, version)
      • Diagnostics (severity, code, message, source, position)
  • Access intra-text document relationships (e.g., reference edges across files). Result chunk data is shared between documents, and a document may have edges into multiple result chunks. As a result, reading all relationships from a single document can open many result chunks.
    • Table: lsif_data_result_chunks
    • Key: dump_id, idx
    • Returns: ResultChunk
  • Get position of occurrences (of a particular type) of a particular symbol within the index by its fully (index-)qualified name. Types of occurrences are grouped together into separate tables.
    • Table: lsif_data_{definitions,references,implementations}
    • Key: dump_id, scheme, identifier
    • Returns: []LocationData

Proposed SCIP-centric schema design

The SCIP-centric schema design must look fairly similar to the LSIF-centric design so that we can seamlessly transition to all-SCIP-everywhere without having to rewrite large portions of the codenav stack (including extension logic that lives currently in multiple places).

Additional technical considerations:

  1. We’d like SCIP data to be cacheable in layers. Specifically, we’d like to be able to combine SCIP results about a single text document, compilation unit, or symbol that come from processors with different precision guarantees/concerns. For example, we should use tree-sitter to fill in the syntax highlighting information for a text document if the SCIP indexer has not provided that data.
  2. We’d like SCIP data to be stored in a naturally normalized format (as much as possible). If we index the full repository on every commit, we’re likely to see many identical text documents in both indexes. These should not be stored duplicately on the backend (which is currently the case when storing LSIF).
  3. We’d like to support the ability (and with additional indexing, efficient ability) to query arbitrary relations related to any particular symbol that exists in any statically uploaded index.

We propose the following canonicalization phases of input SCIP indexes prior to persistence into the database to ensure that we have a deterministic hash used in our content-addressable(-like) store below. These transformations are meant to be done in a streaming fashion that doesn’t require the entire index to be slurped into memory (as LSIF requires today). This should also make it easier to process each text document without the need for a lookup table with relevant external definitions.

  • If an Index message is supplied we break it into a stream of components instead to allow processing with lower memory overhead.
  • Canonicalize fields with documented restrictions (e.g., relative_path).
  • Ensure repeated fields (e.g., occurrences, symbols, relationships) are ordered by a well-defined property.
  • Ensure that each occurrence range is encoded optimally (no repeated line numbers).
  • Pack external symbols into documents that reference them. This is probably the one that is either the hardest, or it’s going to be stupid easy with one weird trick that only one person is going to understand (prolly not me tho).

We propose the initial schema design, described below, which stores SCIP data directly. A processed SCIP index is a collection of rows with the same upload_id in the codeintel_scip_symbols and codeintel_scip_index_documents tables.

The codeintel_scip_documents table stores processed and canonicalied SCIP Document payloads against a digest of its contents. We assume this hash to be deterministic, and analysis of the same source code should produce the same hash. We allow multiple indexes to share the same document data, as many documents will be unchanged across commit boundaries. This allows us to deduplicate document data for free. We will need to ensure that deletion of data related to an upload also cleans up references to unreachable content-addressed data such as this. We can use similar row reference counting techniques as we’ve used in the past.

The codeintel_scip_symbols table is an index from symbol names to the documents that contain occurrences of that symbol within a given processed upload. Each row indicates a set of ranges within a text document that have the same relationship to a particular symbol (e.g., ranges of all references to a particular variable).

  • codeintel_scip_index_documents
    • Fields:
      • id serial
      • upload_id integer, path text
      • hash text
    • Indexes:
      • id forms the PK
      • upload_id, path form a unique index
  • codeintel_scip_documents
    • Fields:
      • hash text
      • raw_scip_payload bytea
    • Indexes:
      • hash alone forms the PK
  • codeintel_scip_symbols
    • Fields:
      • upload_id integer
      • symbol_name text
      • document_id integer (join to index_documents to get path)
      • {def,ref,impl,typedef}_ranges bytea
    • Indexes:
      • upload_id, symbol_name, document_id forms the PK

We can also emulate the query patterns in the LSIF-centric design:

  • Get all data (of a particular type) about a text document given an index-root relative path.
    • We query the joined result set of the tables codeintel_scip_index_documents and codeintel_scip_documents to retrieve relevant portions of the SCIP payload. There are SCIP analogs to each of the LSIF definitions:
      • Ranges -> Occurrence
      • Hovers -> SymbolInformation.documentation
      • Monikers, Packages -> SymbolName
      • Diagnostics -> Occurrence.Diagnostic
  • Access intra-text document relationships (e.g., reference edges across files).
    • We use symbol names in place of opaque identifiers and will be able to access the text documents with relationships to symbols directly. This uses the relationships between the tables codeintel_scip_symbols and codeintel_scip_{index_}documents. Ranges are denormalized onto the row so that the common case of wanting only locations does not require a second scatter+gather query.
  • Get position of occurrences (of a particular symbol role) of a particular symbol within the index by its fully (index-)qualified name.
    • Similar to the query pattern above, we look up the target text document by querying the table codeintel_scip_symbols, which stores the set of ranges in each text document.

Implementation plan

Execution progress will be tracked in the RFC 740 tracking issue. Until we’ve settled on an implementation plan we will sketch rough steps in this document.

Rough steps (order dependent):

  1. Test/validate LSIF -> SCIP conversion tooling
  2. Write new SCIP-centric tables to the database (initially empty)
  3. Add new lookup on SCIP-centric tables on queries to existing table, falling back to the unmigrated LSIF data where no SCIP data exists
  4. Accept SCIP alongside LSIF in the worker (differentiating on a new header from src-cli)
  5. Add out-of-band migration that rewrites LSIF data to SCIP
  6. Stop accepting LSIF payloads; add LSIF -> SCIP conversion in src-cli (requires a deprecation period, otherwise smart src-cli version or capability checks)
  7. Deprecate out-of-band migration and remove LSIF-centric query paths and tables (requires a branch cut after out-of-band migration has been introduced)
  8. Now we only have SCIP data and a single query path - optimize and extend features

Comments

Olaf GeirssonOne use-case that I’d love to solve (if possible) is being able to cheaply load blob views with href links to all referenced definitions. My thinking is that the href links would point to SCIP symbol URLs instead of concrete repo+revision+file+line URLs. Tom Rossmentioned this would complement very nicely with keyboard navigation where you can quickly cycle through tokens and press enter to load definitions.
Eric Fritz This is P.H.A.S.E. O.N.E. of a master plan to bring more SCIP-symbol focused APIs to phase out our current location/position-based one. That was fine when we had to also support LSP calls, but we should naturally be moving towards batch results (all links filled out for a document) and being able to jump to a symbol definition deterministically and concretely by a global name; so I agree with this general approach.

Olaf Geirsson, 1Another use-case I’d badly want to support is resolving the definition of a symbol on-demand. For example, given a symbol like “scip-java com.google.guava guava 31.1-jre com/google/Future#”, we can find the location of this symbol with tree-sitter alone and then queue an auto-indexing job for that package if it’s missing. I don’t think this use-case is relevant for the discussion in this document, but wanted to mention it nevertheless.