A delta encoder for a run of source locations. More...

#include "clang/Serialization/SourceLocationEncoding.h"

Public Member Functions
	Chain (UIntTy AnchorOffset)
RawLocEncoding	deltaEncode (RawLocEncoding V)
RawLocEncoding	deltaDecode (RawLocEncoding V)

Detailed Description

A delta encoder for a run of source locations.

The high level strategy of the chain to encode the run is the following. Locations: SL0 SL1 SL2 map to : (SL0 - anchor) (SL1 - SL0) (SL2 - SL1)

Two wrinkles complicate this strategy's implementation. First, since the delta-encoded values are meant for VBR compression, they are mapped from int to unsigned int with the zigZag method.

Second, two cases are given their own codes instead of being stored as distances.

An invalid SourceLocation encodes to 0 – encodeRaw is a bijection and encodeRaw(0) == 0 – and 0 is kept for it here. This case is common because a macro argument expansion has no end location, so the writer stores an invalid one in that field. Expressing it as a distance would be wasteful: the distance from Prev back to the origin is a number as large as Prev itself, while a dedicated code costs a single VBR chunk.

A distance of zero – the location repeats the Previous one in the run – is stored as 1. That is also common, since an expansion's start and end coincide whenever the invocation spans a single token.

Reserving 0 has a consequence. For a given Prev, zigZag(0 - Prev) is the distance that would arrive back at 0, and it can never occur, because an invalid location took the branch above. So that code is dead, and compacting it out is what makes everything fit:

delta = V - Prev hole = zigZag(0 - Prev) encoded = zigZag(delta) + 1 if zigZag(delta) < hole = zigZag(delta) if zigZag(delta) > hole

Or pictorially: zigZag(delta): 0, 1, ... hole - 1, hole + 1, hole + 2, ... encoded: 1, 2, ... hole, hole + 1, hole + 2, ... the encoded value by 1 to leave 0 to represent V == 0. If zigZag(delta) is larger than hole, we do not need to add 1. Therefore, we will not accidentally add 1 to values that may overflow beyond 2^32 - 1, which may lead to accidental change of the ModuleFileIndex bits. This mapping avoids the issue llvm/llvm-project#145529 attempted to fix by design.

Definition at line 106 of file SourceLocationEncoding.h.

Constructor & Destructor Documentation

◆ Chain()

clang::SourceLocationEncoding::Chain::Chain ( UIntTy AnchorOffset )

inlineexplicit

Definition at line 127 of file SourceLocationEncoding.h.

Member Function Documentation

◆ deltaDecode()

RawLocEncoding clang::SourceLocationEncoding::Chain::deltaDecode ( RawLocEncoding V )

inline

Definition at line 153 of file SourceLocationEncoding.h.

References V.

Referenced by clang::ASTReader::ReadSourceLocation().

◆ deltaEncode()

RawLocEncoding clang::SourceLocationEncoding::Chain::deltaEncode ( RawLocEncoding V )