Index Canonicalization
Relevant source files
The following files were used as context for generating this wiki page:
Index Canonicalization is the process of deterministically sorting, merging, and sanitizing the components of a SCIP index. This ensures that the index has a stable representation, which is critical for deduplication, efficient storage in databases, and predictable behavior across different producers and consumers. The process primarily focuses on Document, Occurrence, and SymbolInformation entities within the SCIP protocol.
The high-level goal is to ensure that each index has exactly one representation of a given document path and that symbols or occurrences with equivalent bounds or names are merged into single, unified entities.
Sources: bindings/go/scip/canonicalize.go:3-11, bindings/go/scip/flatten.go:3-6
Core Canonicalization Logic
The canonicalization of a Document involves three primary phases: occurrences processing, symbols processing, and final sanitization. This logic ensures that illegal data is removed and remaining data is organized according to strict ordering rules.
Document Pipeline
The entry point for this process is CanonicalizeDocument, which orchestrates the transformation of the document structure.
Sorting and Merging Requirements
Canonicalization imposes specific post-conditions on the document data:
- Occurrences: Must have well-formed ranges (length 3 or 4). They are sorted in ascending order based on
Range.CompareStrict. - Symbols: Must be sorted in ascending order by symbol name.
SymbolInformationvalues with the same name are merged. - Relationships: Fields within symbol relationships are deterministically re-ordered and sorted.
Sources: bindings/go/scip/canonicalize.go:5-11, bindings/go/scip/canonicalize.go:66-70
Component Flattening
Flattening is the mechanism used to merge duplicate entries. This allows downstream processes, such as the SQLite converter, to assume that each path or symbol is unique within its context.
| Entity | Merging Logic |
|---|---|
| Document | Merges elements with the same RelativePath. Symbols and Occurrences from duplicates are appended to the first instance. |
| SymbolInformation | Merges elements with the same symbol name. Documentation strings are combined (deduplicated), and relationships are appended. |
| Occurrence | Merges elements with equivalent bounds and symbol names. Bitsets for SymbolRoles are OR-ed, and diagnostics/documentation are appended. |
| Relationship | Merges elements with the same symbol name. Boolean flags (IsReference, IsImplementation, etc.) are combined using logical OR. |
Sources: bindings/go/scip/flatten.go:5-15, bindings/go/scip/flatten.go:30-40, bindings/go/scip/flatten.go:52-65, bindings/go/scip/flatten.go:88-95
Sanitization
Sanitization is the final step in the canonicalization pipeline. It ensures that all string data within the SCIP index is valid UTF-8. This is a critical requirement for successful Protobuf encoding and transmission.
Sanitization Process
The SanitizeDocument function recursively traverses the document structure, coercing invalid strings into valid UTF-8 by converting them through rune slices if necessary.
Integration in Index Conversion
Canonicalization is a prerequisite for converting SCIP indexes into other formats, such as SQLite. In the Converter.Convert implementation, every document is canonicalized before being inserted into the database to ensure data integrity.
for i, doc := range index.Documents {
// ... path deduplication logic ...
doc = scip.CanonicalizeDocument(doc)
index.Documents[i] = doc
docID, err := c.insertDocument(doc)
// ... insertion logic ...
}
Sources: cmd/scip/convert.go:189-195
Conclusion
Index Canonicalization provides the deterministic foundation for the SCIP protocol's transmission goals. By enforcing strict sorting, merging duplicates through flattening, and ensuring UTF-8 compliance via sanitization, the system guarantees that data remains consistent regardless of the producer's implementation details.