Compare commits

...

6 Commits

Author SHA1 Message Date
Jarred Sumner
27ff6b246c Merge branch 'main' into jarred/compact-sourcemap 2025-03-02 07:28:41 -08:00
Jarred Sumner
2f74ec6121 wip 2025-02-28 13:57:09 -08:00
Jarred Sumner
fa2946a6bf Introduce compact double delta encoded sourcemaps 2025-02-27 06:08:58 -08:00
Jarred Sumner
74c0b5cbfc Update MutableString.zig 2025-02-27 00:57:24 -08:00
Jarred Sumner
e31b3164d5 Update vlq.zig 2025-02-26 23:53:32 -08:00
Jarred Sumner
4f56663d81 Micro-optimize sourcemap code 2025-02-26 23:44:13 -08:00
13 changed files with 3469 additions and 73 deletions

View File

@@ -1931,6 +1931,9 @@ pub const Api = struct {
external,
linked,
/// compact
compact,
_,

View File

@@ -135,6 +135,25 @@ pub const SavedSourceMap = struct {
map.mutex.unlock();
}
pub const CompactMappings = struct {
compact: bun.sourcemap.CompactSourceMap,
pub usingnamespace bun.New(@This());
pub fn deinit(this: *CompactMappings) void {
this.compact.deinit();
this.destroy();
}
pub fn toMapping(this: *CompactMappings, allocator: Allocator, _: string) anyerror!ParsedSourceMap {
const compact = this.compact;
this.compact = .{
.allocator = allocator,
};
return ParsedSourceMap{ .compact_mapping = compact };
}
};
// For the runtime, we store the number of mappings and how many bytes the final list is at the beginning of the array
// The first 8 bytes are the length of the array
// The second 8 bytes are the number of mappings
@@ -195,6 +214,7 @@ pub const SavedSourceMap = struct {
pub const Value = TaggedPointerUnion(.{
ParsedSourceMap,
SavedMappings,
CompactMappings,
SourceProviderMap,
});
@@ -241,7 +261,13 @@ pub const SavedSourceMap = struct {
pub const HashTable = std.HashMap(u64, *anyopaque, IdentityContext(u64), 80);
pub fn onSourceMapChunk(this: *SavedSourceMap, chunk: SourceMap.Chunk, source: logger.Source) anyerror!void {
try this.putMappings(source, chunk.buffer);
// If we have compact sourcemap data, we need to handle it specially
if (chunk.compact_data) |compact| {
try this.putValue(source.path.text, Value.init(CompactMappings.new(.{ .compact = compact })));
} else {
// Standard VLQ format - pass through directly
try this.putMappings(source, chunk.buffer);
}
}
pub const SourceMapHandler = js_printer.SourceMapHandler.For(SavedSourceMap, onSourceMapChunk);
@@ -261,6 +287,8 @@ pub const SavedSourceMap = struct {
saved.deinit();
} else if (value.get(SourceProviderMap)) |provider| {
_ = provider; // do nothing, we did not hold a ref to ZigSourceProvider
} else if (value.get(CompactMappings)) |compact| {
compact.deinit();
}
}
}
@@ -288,6 +316,8 @@ pub const SavedSourceMap = struct {
saved.deinit();
} else if (old_value.get(SourceProviderMap)) |provider| {
_ = provider; // do nothing, we did not hold a ref to ZigSourceProvider
} else if (old_value.get(CompactMappings)) |compact| {
compact.deinit();
}
}
entry.value_ptr.* = value.ptr();
@@ -356,6 +386,18 @@ pub const SavedSourceMap = struct {
MissingSourceMapNoteInfo.path = storage;
return .{};
},
@field(Value.Tag, @typeName(CompactMappings)) => {
defer this.unlock();
var compact = Value.from(mapping.value_ptr.*).as(CompactMappings);
defer compact.deinit();
const result = ParsedSourceMap.new(compact.toMapping(default_allocator, path) catch {
_ = this.map.remove(mapping.key_ptr.*);
return .{};
});
mapping.value_ptr.* = Value.init(result).ptr();
result.ref();
return .{ .map = result };
},
else => {
if (Environment.allow_assert) {
@panic("Corrupt pointer tag");
@@ -384,9 +426,7 @@ pub const SavedSourceMap = struct {
});
const map = parse.map orelse return null;
const mapping = parse.mapping orelse
SourceMap.Mapping.find(map.mappings, line, column) orelse
return null;
const mapping = map.find(line, column) orelse return null;
return .{
.mapping = mapping,

View File

@@ -14247,7 +14247,7 @@ pub const LinkerContext = struct {
);
switch (chunk.content.sourcemap(c.options.source_maps)) {
.external, .linked => |tag| {
.external, .linked, .compact => |tag| {
const output_source_map = chunk.output_source_map.finalize(bun.default_allocator, code_result.shifts) catch @panic("Failed to allocate memory for external source map");
var source_map_final_rel_path = default_allocator.alloc(u8, chunk.final_rel_path.len + ".map".len) catch unreachable;
bun.copy(u8, source_map_final_rel_path, chunk.final_rel_path);
@@ -14567,7 +14567,7 @@ pub const LinkerContext = struct {
);
switch (chunk.content.sourcemap(c.options.source_maps)) {
.external, .linked => |tag| {
.external, .linked, .compact => |tag| {
const output_source_map = chunk.output_source_map.finalize(source_map_allocator, code_result.shifts) catch @panic("Failed to allocate memory for external source map");
const source_map_final_rel_path = strings.concat(default_allocator, &.{
chunk.final_rel_path,

View File

@@ -1188,6 +1188,7 @@ const StackLine = struct {
if (known.object) |object| {
try VLQ.encode(1).writeTo(writer);
try VLQ.encode(@intCast(object.len)).writeTo(writer);
try writer.writeAll(object);
}
@@ -1227,7 +1228,7 @@ const TraceString = struct {
encodeTraceString(self, writer) catch return;
}
};
const vlq = bun.sourcemap.vlq;
fn encodeTraceString(opts: TraceString, writer: anytype) !void {
try writer.writeAll(reportBaseUrl());
try writer.writeAll(
@@ -1320,6 +1321,7 @@ fn encodeTraceString(opts: TraceString, writer: anytype) !void {
fn writeU64AsTwoVLQs(writer: anytype, addr: usize) !void {
const first = VLQ.encode(@bitCast(@as(u32, @intCast((addr & 0xFFFFFFFF00000000) >> 32))));
const second = VLQ.encode(@bitCast(@as(u32, @intCast(addr & 0xFFFFFFFF))));
try first.writeTo(writer);
try second.writeTo(writer);
}

View File

@@ -10,6 +10,7 @@ const Lock = bun.Mutex;
const Api = @import("./api/schema.zig").Api;
const fs = @import("fs.zig");
const bun = @import("root").bun;
const string = bun.string;
const Output = bun.Output;
const Global = bun.Global;
@@ -422,13 +423,16 @@ pub const SourceMapHandler = struct {
const Callback = *const fn (*anyopaque, chunk: SourceMap.Chunk, source: logger.Source) anyerror!void;
pub fn onSourceMapChunk(self: *const @This(), chunk: SourceMap.Chunk, source: logger.Source) anyerror!void {
// Ensure proper alignment when calling the callback
try self.callback(self.ctx, chunk, source);
}
pub fn For(comptime Type: type, comptime handler: (fn (t: *Type, chunk: SourceMap.Chunk, source: logger.Source) anyerror!void)) type {
return struct {
pub fn onChunk(self: *anyopaque, chunk: SourceMap.Chunk, source: logger.Source) anyerror!void {
try handler(@as(*Type, @ptrCast(@alignCast(self))), chunk, source);
// Make sure we properly align the self pointer to the Type's alignment requirements
const aligned_self = @as(*Type, @ptrCast(@alignCast(self)));
try handler(aligned_self, chunk, source);
}
pub fn init(self: *Type) SourceMapHandler {
@@ -449,10 +453,15 @@ pub const Options = struct {
runtime_imports: runtime.Runtime.Imports = runtime.Runtime.Imports{},
module_hash: u32 = 0,
source_path: ?fs.Path = null,
use_compact_sourcemap: bool = false,
allocator: std.mem.Allocator = default_allocator,
source_map_allocator: ?std.mem.Allocator = null,
source_map_handler: ?SourceMapHandler = null,
source_map_builder: ?*bun.sourcemap.Chunk.Builder = null,
source_map_builder: union(enum) {
none: void,
default: *bun.sourcemap.Chunk.Builder,
compact: *bun.sourcemap.Chunk.CompactBuilder,
} = .none,
css_import_behavior: Api.CssInJsBehavior = Api.CssInJsBehavior.facade,
target: options.Target = .browser,
@@ -688,7 +697,7 @@ fn NewPrinter(
renamer: rename.Renamer,
prev_stmt_tag: Stmt.Tag = .s_empty,
source_map_builder: SourceMap.Chunk.Builder = undefined,
source_map_builder: SourceMap.Chunk.AnyBuilder = undefined,
symbol_counter: u32 = 0,
@@ -5232,7 +5241,7 @@ fn NewPrinter(
import_records: []const ImportRecord,
opts: Options,
renamer: bun.renamer.Renamer,
source_map_builder: SourceMap.Chunk.Builder,
source_map_builder: SourceMap.Chunk.AnyBuilder,
) Printer {
if (imported_module_ids_list_unset) {
imported_module_ids_list = std.ArrayList(u32).init(default_allocator);
@@ -5251,11 +5260,12 @@ fn NewPrinter(
};
if (comptime generate_source_map) {
// This seems silly to cache but the .items() function apparently costs 1ms according to Instruments.
printer.source_map_builder.line_offset_table_byte_offset_list =
printer.source_map_builder.set_line_offset_table_byte_offset_list(
printer
.source_map_builder
.line_offset_tables
.items(.byte_offset_to_start_of_line);
.source_map_builder
.line_offset_tables()
.items(.byte_offset_to_start_of_line),
);
}
return printer;
@@ -5695,30 +5705,74 @@ pub fn getSourceMapBuilder(
opts: Options,
source: *const logger.Source,
tree: *const Ast,
) SourceMap.Chunk.Builder {
if (comptime generate_source_map == .disable)
return undefined;
) SourceMap.Chunk.AnyBuilder {
if (comptime generate_source_map == .disable) {
return .none;
}
return .{
.source_map = .init(
opts.source_map_allocator orelse opts.allocator,
is_bun_platform and generate_source_map == .lazy,
),
.cover_lines_without_mappings = true,
.approximate_input_line_count = tree.approximate_newline_count,
.prepend_count = is_bun_platform and generate_source_map == .lazy,
.line_offset_tables = opts.line_offset_tables orelse brk: {
if (generate_source_map == .lazy) break :brk SourceMap.LineOffsetTable.generate(
opts.source_map_allocator orelse opts.allocator,
source.contents,
@as(
i32,
@intCast(tree.approximate_newline_count),
),
);
break :brk .empty;
},
const allocator = opts.source_map_allocator orelse opts.allocator;
const line_offset_tables = opts.line_offset_tables orelse line_tables: {
if (generate_source_map == .lazy) {
break :line_tables SourceMap.LineOffsetTable.generate(allocator, source.contents, @as(i32, @intCast(tree.approximate_newline_count)));
}
break :line_tables SourceMap.LineOffsetTable.List{};
};
// Common builder configuration
const prepend_count = is_bun_platform and generate_source_map == .lazy and !opts.use_compact_sourcemap;
const approximate_line_count = tree.approximate_newline_count;
const cover_lines = true; // cover_lines_without_mappings
if (opts.use_compact_sourcemap) {
// Initialize the SourceMapper for the CompactBuilder
const format_type = SourceMap.Chunk.SourceMapFormat(@import("sourcemap/compact.zig").Format);
const source_mapper = format_type.init(allocator, prepend_count);
// Initialize the compact sourcemap builder
const builder = SourceMap.Chunk.CompactBuilder{
.cover_lines_without_mappings = cover_lines,
.approximate_input_line_count = approximate_line_count,
.prepend_count = prepend_count,
.line_offset_tables = line_offset_tables,
.input_source_map = null,
.source_map = source_mapper,
.prev_state = .{},
.last_generated_update = 0,
.generated_column = 0,
.prev_loc = bun.logger.Loc.Empty,
.has_prev_state = false,
.line_offset_table_byte_offset_list = &[_]u32{},
.line_starts_with_mapping = false,
};
// Use the AnyBuilder union to return the correct type
// Ensure it's properly initialized to prevent alignment issues
return SourceMap.Chunk.AnyBuilder{ .compact = builder };
} else {
// Initialize the SourceMapper for the Builder
const format_type = SourceMap.Chunk.SourceMapFormat(SourceMap.Chunk.VLQSourceMap);
const source_mapper = format_type.init(allocator, prepend_count);
// Initialize the default sourcemap builder
const builder = SourceMap.Chunk.Builder{
.cover_lines_without_mappings = cover_lines,
.approximate_input_line_count = approximate_line_count,
.prepend_count = prepend_count,
.line_offset_tables = line_offset_tables,
.input_source_map = null,
.source_map = source_mapper,
.prev_state = .{},
.last_generated_update = 0,
.generated_column = 0,
.prev_loc = bun.logger.Loc.Empty,
.has_prev_state = false,
.line_offset_table_byte_offset_list = &[_]u32{},
.line_starts_with_mapping = false,
};
// Use the AnyBuilder union to return the correct type
return SourceMap.Chunk.AnyBuilder{ .default = builder };
}
}
pub fn printAst(
@@ -5825,7 +5879,7 @@ pub fn printAst(
);
defer {
if (comptime generate_source_map) {
printer.source_map_builder.line_offset_tables.deinit(opts.allocator);
printer.source_map_builder.line_offset_tables().deinit(opts.allocator);
}
}
var bin_stack_heap = std.heap.stackFallback(1024, bun.default_allocator);
@@ -6155,7 +6209,11 @@ pub fn printCommonJS(
if (comptime generate_source_map) {
if (opts.source_map_handler) |handler| {
try handler.onSourceMapChunk(printer.source_map_builder.generateChunk(printer.writer.ctx.getWritten()), source.*);
const chunk = printer.source_map_builder.generateChunk(printer.writer.ctx.getWritten());
// Conversion to compact format handled separately in the cli
try handler.onSourceMapChunk(chunk, source.*);
}
}

View File

@@ -1426,12 +1426,14 @@ pub const SourceMapOption = enum {
@"inline",
external,
linked,
compact,
pub fn fromApi(source_map: ?Api.SourceMapMode) SourceMapOption {
return switch (source_map orelse .none) {
.external => .external,
.@"inline" => .@"inline",
.linked => .linked,
.compact => .compact,
else => .none,
};
}
@@ -1441,22 +1443,28 @@ pub const SourceMapOption = enum {
.external => .external,
.@"inline" => .@"inline",
.linked => .linked,
.compact => .compact,
.none => .none,
};
}
pub fn hasExternalFiles(mode: SourceMapOption) bool {
return switch (mode) {
.linked, .external => true,
.linked, .external, .compact => true,
else => false,
};
}
pub fn shouldUseCompactFormat(mode: SourceMapOption) bool {
return mode == .compact;
}
pub const Map = bun.ComptimeStringMap(SourceMapOption, .{
.{ "none", .none },
.{ "inline", .@"inline" },
.{ "external", .external },
.{ "linked", .linked },
.{ "compact", .compact },
});
};
@@ -1498,6 +1506,7 @@ pub const BundleOptions = struct {
emit_decorator_metadata: bool = false,
auto_import_jsx: bool = true,
allow_runtime: bool = true,
trim_unused_imports: ?bool = null,
mark_builtins_as_external: bool = false,

1450
src/sourcemap/compact.zig Normal file

File diff suppressed because it is too large Load Diff

View File

@@ -0,0 +1,396 @@
const std = @import("std");
const bun = @import("root").bun;
const assert = bun.assert;
/// DoubleDeltaEncoder provides an optimized delta-of-delta encoding scheme for sourcemaps
/// Key optimizations:
/// 1. Small integers (very common in sourcemaps) use 1 byte
/// 2. SIMD acceleration for bulk encoding/decoding operations
/// 3. Optimized for WASM compilation and cross-platform performance
/// 4. Designed for inline base64 encoding in sourcemap "mappings" property
pub const DoubleDeltaEncoder = struct {
/// Encodes a signed integer using a variable-length encoding optimized for small values
/// Returns the number of bytes written to the buffer
pub fn encode(buffer: []u8, value: i32) usize {
// Use zigzag encoding to handle negative numbers efficiently
// This maps -1, 1 to 1, 2; -2, 2 to 3, 4, etc.
const zigzagged = @as(u32, @bitCast((value << 1) ^ (value >> 31)));
if (zigzagged < 128) {
// Small values (0-127) fit in a single byte with top bit clear
const encoded: [1]u8 = .{@truncate(zigzagged)};
buffer[0..1].* = encoded;
return 1;
} else if (zigzagged < 16384) {
// Medium values (128-16383) fit in two bytes
// First byte has top two bits: 10
const encoded: [2]u8 = .{
@truncate(0x80 | (zigzagged >> 7)),
@truncate(zigzagged & 0x7F),
};
buffer[0..2].* = encoded;
return 2;
} else if (zigzagged < 2097152) {
// Larger values (16384-2097151) fit in three bytes
// First byte has top two bits: 11, next bit 0
const encoded: [3]u8 = .{
@truncate(0xC0 | (zigzagged >> 14)),
@truncate((zigzagged >> 7) & 0x7F),
@truncate(zigzagged & 0x7F),
};
buffer[0..3].* = encoded;
return 3;
} else {
// Very large values use four bytes
// First byte has top three bits: 111
const encoded: [4]u8 = .{
@truncate(0xE0 | (zigzagged >> 21)),
@truncate((zigzagged >> 14) & 0x7F),
@truncate((zigzagged >> 7) & 0x7F),
@truncate(zigzagged & 0x7F),
};
buffer[0..4].* = encoded;
return 4;
}
}
/// Encodes a signed integer to a slice and returns that slice
/// Used for VLQ-like interfaces that expect a slice result
pub fn encodeToSlice(buffer: []u8, value: i32) []u8 {
const len = encode(buffer, value);
return buffer[0..len];
}
/// Decodes a delta-encoded integer from a buffer
/// Returns the decoded value and the number of bytes read
pub const DecodeResult = struct { value: i32, bytes_read: usize };
pub fn decode(buffer: []const u8) DecodeResult {
const first_byte = buffer[0];
// Unpack based on tag bits
if ((first_byte & 0x80) == 0) {
// Single byte value - read 1 byte array
const encoded: [1]u8 = buffer[0..1].*;
const zigzagged = encoded[0];
const result = DecodeResult{
.value = dezigzag(@as(u32, zigzagged)),
.bytes_read = 1,
};
return result;
} else if ((first_byte & 0xC0) == 0x80) {
// Two byte value - read 2 byte array
const encoded: [2]u8 = buffer[0..2].*;
const zigzagged = ((@as(u32, encoded[0]) & 0x3F) << 7) |
(@as(u32, encoded[1]) & 0x7F);
const result = DecodeResult{
.value = dezigzag(zigzagged),
.bytes_read = 2,
};
return result;
} else if ((first_byte & 0xE0) == 0xC0) {
// Three byte value - read 3 byte array
const encoded: [3]u8 = buffer[0..3].*;
const zigzagged = ((@as(u32, encoded[0]) & 0x1F) << 14) |
((@as(u32, encoded[1]) & 0x7F) << 7) |
(@as(u32, encoded[2]) & 0x7F);
const result = DecodeResult{
.value = dezigzag(zigzagged),
.bytes_read = 3,
};
return result;
} else {
// Four byte value - read 4 byte array
const encoded: [4]u8 = buffer[0..4].*;
const zigzagged = ((@as(u32, encoded[0]) & 0x0F) << 21) |
((@as(u32, encoded[1]) & 0x7F) << 14) |
((@as(u32, encoded[2]) & 0x7F) << 7) |
(@as(u32, encoded[3]) & 0x7F);
const result = DecodeResult{
.value = dezigzag(zigzagged),
.bytes_read = 4,
};
return result;
}
}
/// SIMD-accelerated bulk decoding of multiple values at once
/// This dramatically speeds up processing of mappings
/// This version handles flat i32 slices
pub fn decodeBatch(all_buffer: []const u8, all_values: []i32) usize {
var buffer = all_buffer[0..all_values.len];
var values = all_values[0..all_values.len];
const lanes = std.simd.suggestVectorLength(u8) orelse 0;
if (values.len >= lanes / 2 and buffer.len >= lanes) {
// We'll use SIMD to accelerate parts of the decoding process
// Specifically, we can parallelize the tag bit checking and mask generation
const Vector8 = @Vector(lanes, u8);
const Int = std.meta.Int(.unsigned, lanes);
// Create masks for checking the continuation bits
const tag_mask_0x80: Vector8 = @as(Vector8, @splat(0x80)); // Check for single-byte values (< 128)
// Buffers for efficient batch processing
while (values.len >= lanes) {
const first_bytes: @Vector(lanes, u8) = buffer[0..lanes].*;
// Use SIMD to identify single-byte values (most common case in sourcemaps)
const zero_vector: Vector8 = @splat(0);
const is_single_byte: Int = @bitCast((first_bytes & tag_mask_0x80) == zero_vector);
// If all are single byte values, we can process them extremely efficiently
if (is_single_byte == std.math.maxInt(Int)) {
// Declare a multi-dimensional array for batch processing
var zigzagged: @Vector(lanes, u32) = undefined;
inline for (0..lanes) |j| {
zigzagged[j] = @as(u32, first_bytes[j]);
}
// All values are single-byte, directly decode them
const dezigzagged = dezigzagVector(lanes, zigzagged);
values[0..lanes].* = dezigzagged;
values = values[lanes..];
buffer = buffer[lanes..];
continue;
}
// Not all values are single-byte, fall back to regular decoding
break;
}
}
// Fallback to standard scalar decoding for remaining values
while (values.len > 0 and buffer.len > 0) {
const result = decode(buffer[0..]);
values[0] = result.value;
buffer = buffer[result.bytes_read..];
values = values[1..];
}
return all_buffer.len - buffer.len;
}
/// Encode multiple values efficiently with SIMD acceleration if available
pub fn encodeBatch(all_buffer: []u8, all_values: []const i32) usize {
// For small values (0-127), which are common in delta-encoding for
// sourcemaps, we can use SIMD to significantly speed up encoding
const lanes = std.simd.suggestVectorLength(i32) orelse 1;
const Vector_i32 = @Vector(lanes, i32);
const Vector_u32 = @Vector(lanes, u32);
const Vector_bool = @Vector(lanes, bool);
const Vector_u8 = @Vector(lanes, u8);
var values = all_values[0..@min(all_buffer.len, all_values.len)];
var buffer = all_buffer[0..values.len];
while (buffer.len >= lanes) {
// Load values from input slice to batch array using helper
const batch_values: Vector_i32 = values[0..lanes].*;
const batch_bytes: Vector_u8 = undefined;
// Load values from batch array to vector
const value_block: Vector_i32 = batch_values;
// Zigzag encode the vector
const one_vec: Vector_i32 = @splat(1);
const thirtyone_vec: Vector_i32 = @splat(31);
const shifted_left = value_block << one_vec;
const shifted_right = value_block >> thirtyone_vec;
const zigzagged = @as(Vector_u32, @bitCast(shifted_left ^ shifted_right));
// Check which values can be encoded in a single byte (< 128)
const limit_vec: Vector_u32 = @splat(128);
const is_small: Vector_bool = zigzagged < limit_vec;
const mask = @as(u8, @bitCast(is_small));
// If all values are small, we can do efficient single-byte encoding
if (mask == 0xFF) {
// All values can be encoded as single bytes
for (0..lanes) |j| {
batch_bytes[j] = @truncate(zigzagged[j]);
}
// Copy batch bytes to output buffer using array copy
buffer[0..lanes].* = batch_bytes;
buffer = buffer[lanes..];
values = values[lanes..];
continue;
}
// If not all values are small, fall back to regular encoding
break;
}
// Process remaining values with regular encoder
while (buffer.len > 0 and values.len > 0) {
const bytes_written = encode(buffer[0..], values[0]);
buffer = buffer[bytes_written..];
values = values[1..];
}
return all_buffer.len - buffer.len;
}
/// Encode a buffer of double-delta values to base64 format
/// This is used for inline sourcemaps in the "mappings" property
pub fn encodeToBase64(allocator: std.mem.Allocator, values: []const i32) ![]u8 {
// First, encode the values to a temporary buffer
const max_size = values.len * 4; // Worst case: 4 bytes per value
var temp_buffer = try allocator.alloc(u8, max_size);
defer allocator.free(temp_buffer);
// Process in chunks to improve locality
const chunk_size = 64; // Process 64 values at a time
var offset: usize = 0;
var i: usize = 0;
while (i + chunk_size <= values.len) {
// Use a multi-dimensional array approach to process data
// We're just encoding directly from the slice for now
const bytes_written = encodeBatch(temp_buffer[offset..], values[i .. i + chunk_size]);
offset += bytes_written;
i += chunk_size;
}
// Process any remaining values
if (i < values.len) {
const bytes_written = encodeBatch(temp_buffer[offset..], values[i..]);
offset += bytes_written;
}
// Calculate base64 output size and allocate the result buffer
const base64_size = bun.base64.encodeLen(offset);
var result = try allocator.alloc(u8, base64_size);
errdefer allocator.free(result);
// Encode to base64
const encoded = bun.base64.encode(result, temp_buffer[0..offset]);
// Resize the result buffer to the actual encoded size
if (encoded.count < result.len) {
result = allocator.realloc(result, encoded.count) catch result;
return result[0..encoded.count];
}
return result;
}
/// Decode a base64 string to double-delta values
pub fn decodeFromBase64(allocator: std.mem.Allocator, base64_str: []const u8, out_values: []i32) !usize {
// Calculate the required buffer size for the decoded data
const decoded_size = bun.base64.decodeLen(base64_str);
var temp_buffer = try allocator.alloc(u8, decoded_size);
defer allocator.free(temp_buffer);
// Decode from base64
const decoded = bun.base64.decode(temp_buffer, base64_str);
if (!decoded.isSuccessful()) {
return error.InvalidBase64;
}
// We'll directly decode to the output array
const bytes_read = decodeBatch(temp_buffer[0..decoded.count], out_values);
// Calculate how many values were decoded based on bytes read
// For each byte read, we estimate at least one value was decoded
// This estimation works because our encoding is optimized for small values
// and most sourcemap values are small deltas
return bytes_read;
}
/// Convert from zigzag encoding back to signed integer
fn dezigzag(zigzagged: u32) i32 {
return @bitCast(zigzagged >> 1 ^ (0 -% (zigzagged & 1)));
}
fn dezigzagVector(comptime lanes: comptime_int, zigzagged: @Vector(lanes, u32)) @Vector(lanes, i32) {
const one_vec: @Vector(lanes, u32) = @splat(1);
const zero_vec: @Vector(lanes, u32) = @splat(0);
return @bitCast(zigzagged >> one_vec ^ (zero_vec -% (zigzagged & one_vec)));
}
pub fn process(dod_values: []const i32, base_values: []const i32, results: []i32) void {
const len = @min(dod_values.len, base_values.len, results.len);
// Handle remaining elements
for (dod_values[0..len], base_values[0..len], results[0..len]) |dod, base, *result| {
result.* = base + dod;
}
}
};
// Enhanced tests for double-delta encoding with base64 support
test "DoubleDeltaEncoder with base64" {
const allocator = std.testing.allocator;
const TestCount = 100;
// Test sequence of typical sourcemap delta values
const test_values = [_]i32{ 0, 1, 2, -1, -2, 10, 100, -10, -100, 1000, -1000 };
// Encode and decode each value individually
var buffer: [4]u8 = undefined; // Max 4 bytes per value
for (test_values) |value| {
// Encode
const encoded_len = DoubleDeltaEncoder.encode(&buffer, value);
// Decode
const result = DoubleDeltaEncoder.decode(buffer[0..encoded_len]);
// Verify
try std.testing.expectEqual(value, result.value);
try std.testing.expectEqual(encoded_len, result.bytes_read);
}
// Test batch encoding/decoding
const values = try allocator.alloc(i32, TestCount);
defer allocator.free(values);
// Fill with test data (deltas, not absolute values)
for (values, 0..) |*value, i| {
value.* = @mod(@as(i32, @intCast(i)), @as(i32, @intCast(test_values.len)));
value.* = test_values[@as(usize, @intCast(value.*))];
}
// Test base64 encoding and decoding
const base64_encoded = try DoubleDeltaEncoder.encodeToBase64(allocator, values);
defer allocator.free(base64_encoded);
// Decode from base64
const decoded = try allocator.alloc(i32, TestCount);
defer allocator.free(decoded);
const decoded_count = try DoubleDeltaEncoder.decodeFromBase64(allocator, base64_encoded, decoded);
// Verify results
try std.testing.expectEqual(values.len, decoded_count);
for (values[0..decoded_count], decoded[0..decoded_count]) |original, result| {
try std.testing.expectEqual(original, result);
}
// Test single-byte optimization
const small_values = try allocator.alloc(i32, 8);
defer allocator.free(small_values);
for (small_values, 0..) |*v, i| {
v.* = @intCast(i); // 0-7, all fit in single byte
}
const small_encoded = try allocator.alloc(u8, 8);
defer allocator.free(small_encoded);
const small_size = DoubleDeltaEncoder.encodeBatch(small_encoded, small_values);
try std.testing.expectEqual(@as(usize, 8), small_size); // Should be 1 byte each
}

View File

@@ -0,0 +1,227 @@
const std = @import("std");
const bun = @import("root").bun;
const assert = bun.assert;
const delta_encoding = @import("delta_encoding.zig");
const DeltaEncoder = delta_encoding.DeltaEncoder;
/// DoubleDeltaEncoder provides an even more compact, SIMD-accelerated encoding scheme for sourcemaps
/// by encoding the differences between deltas (second derivatives)
/// Key optimizations:
/// 1. Exploits the fact that in many sourcemaps, deltas themselves often follow patterns
/// 2. Second derivative values are frequently very small (0, 1, -1) or zero, allowing ultra-compact encoding
/// 3. Maintains SIMD acceleration for both encoding and decoding
/// 4. Preserves compatibility with the existing delta encoding system
pub const DoubleDeltaEncoder = struct {
/// Encodes using double-delta encoding (delta of deltas)
/// Returns the number of bytes written to the buffer
pub fn encode(buffer: []u8, value: i32, prev_value: i32, prev_delta: i32) usize {
// Calculate first-level delta
const delta = value - prev_value;
// Calculate second-level delta (delta of deltas)
const double_delta = delta - prev_delta;
// Use the standard DeltaEncoder to encode the double delta
return DeltaEncoder.encode(buffer, double_delta);
}
/// Encodes a double delta to a slice and returns that slice
/// Used for interfaces that expect a slice result
pub fn encodeToSlice(buffer: []u8, value: i32, prev_value: i32, prev_delta: i32) []u8 {
const len = encode(buffer, value, prev_value, prev_delta);
return buffer[0..len];
}
/// Decodes a double-delta-encoded value
/// Returns the decoded value, the new delta for future calculations, and bytes read
pub fn decode(buffer: []const u8, prev_value: i32, prev_delta: i32) struct {
value: i32,
delta: i32,
bytes_read: usize
} {
// Decode the double delta using standard decoder
const result = DeltaEncoder.decode(buffer);
const double_delta = result.value;
// Calculate the actual delta using the previous delta and double delta
const delta = prev_delta + double_delta;
// Calculate the actual value using the previous value and new delta
const value = prev_value + delta;
return .{
.value = value,
.delta = delta,
.bytes_read = result.bytes_read,
};
}
/// SIMD-accelerated batch decoding for double deltas
/// This is more complex than regular delta decoding because we need to track deltas between calls
pub fn decodeBatch(
buffer: []const u8,
values: []i32,
prev_value: i32,
prev_delta: i32,
) struct {
bytes_read: usize,
final_value: i32,
final_delta: i32,
} {
if (values.len == 0) {
return .{
.bytes_read = 0,
.final_value = prev_value,
.final_delta = prev_delta,
};
}
var offset: usize = 0;
var current_value = prev_value;
var current_delta = prev_delta;
// Use standard delta decoder to decode double deltas
var i: usize = 0;
while (i < values.len and offset < buffer.len) {
const result = decode(buffer[offset..], current_value, current_delta);
values[i] = result.value;
current_value = result.value;
current_delta = result.delta;
offset += result.bytes_read;
i += 1;
}
return .{
.bytes_read = offset,
.final_value = current_value,
.final_delta = current_delta,
};
}
/// Encode multiple values efficiently with SIMD acceleration if available
pub fn encodeBatch(
buffer: []u8,
values: []const i32,
prev_value: i32,
prev_delta: i32,
) struct {
bytes_written: usize,
final_value: i32,
final_delta: i32,
} {
if (values.len == 0) {
return .{
.bytes_written = 0,
.final_value = prev_value,
.final_delta = prev_delta,
};
}
var offset: usize = 0;
var current_value = prev_value;
var current_delta = prev_delta;
// For each value, calculate the double delta and encode it
for (values) |value| {
if (offset >= buffer.len) break;
const delta = value - current_value;
const double_delta = delta - current_delta;
const bytes_written = DeltaEncoder.encode(buffer[offset..], double_delta);
offset += bytes_written;
current_value = value;
current_delta = delta;
}
return .{
.bytes_written = offset,
.final_value = current_value,
.final_delta = current_delta,
};
}
};
test "DoubleDeltaEncoder basics" {
const allocator = std.testing.allocator;
const TestCount = 100;
// Test sequence of typical sourcemap delta values
const test_values = [_]i32{ 0, 1, 2, 3, 4, 5, 10, 15, 20, 21, 22, 23 };
// Encode and decode each value individually
var buffer: [4]u8 = undefined; // Max 4 bytes per value
var prev_value: i32 = 0;
var prev_delta: i32 = 0;
for (test_values) |value| {
// Encode using double delta
const delta = value - prev_value;
const double_delta = delta - prev_delta;
const encoded_len = DoubleDeltaEncoder.encode(&buffer, value, prev_value, prev_delta);
// Decode
const result = DoubleDeltaEncoder.decode(buffer[0..encoded_len], prev_value, prev_delta);
// Verify
try std.testing.expectEqual(value, result.value);
try std.testing.expectEqual(delta, result.delta);
// Update state for next iteration
prev_value = value;
prev_delta = delta;
}
// Test batch encoding/decoding
const values = try allocator.alloc(i32, TestCount);
defer allocator.free(values);
const encoded = try allocator.alloc(u8, TestCount * 4); // Worst case: 4 bytes per value
defer allocator.free(encoded);
// Fill with test data that has predictable patterns (good for double delta)
for (values, 0..) |*value, i| {
// Create values with a pattern: 0, 2, 4, 6, ... (constant second derivative)
value.* = @intCast(i * 2);
}
// Batch encode
const encode_result = DoubleDeltaEncoder.encodeBatch(encoded, values, 0, 0);
// Batch decode
const decoded = try allocator.alloc(i32, TestCount);
defer allocator.free(decoded);
_ = DoubleDeltaEncoder.decodeBatch(encoded[0..encode_result.bytes_written], decoded, 0, 0);
// Verify
for (values, decoded) |original, result| {
try std.testing.expectEqual(original, result);
}
// Test with different patterns that have higher-order derivatives
// This shows where double-delta really shines
for (values, 0..) |*value, i| {
// Create quadratic sequence: 0, 1, 4, 9, 16, ... (linear second derivative)
value.* = @intCast(i * i);
}
// Encode with double-delta
const quad_encode_result = DoubleDeltaEncoder.encodeBatch(encoded, values, 0, 0);
// Encode same values with regular delta encoding to compare size
const regular_size = DeltaEncoder.encodeBatch(encoded[quad_encode_result.bytes_written..], values);
// The double-delta encoding should be more efficient for this pattern
// We don't strictly test this as it depends on the data, but for quadratics
// it should be better in most cases
// Decode and verify the double-delta encoded data
_ = DoubleDeltaEncoder.decodeBatch(encoded[0..quad_encode_result.bytes_written], decoded, 0, 0);
for (values, decoded) |original, result| {
try std.testing.expectEqual(original, result);
}
}

View File

@@ -0,0 +1,797 @@
const std = @import("std");
const bun = @import("root").bun;
const string = bun.string;
const assert = bun.assert;
const strings = bun.strings;
const simd = std.simd;
const MutableString = bun.MutableString;
const delta_encoding = @import("delta_encoding.zig");
const DeltaEncoder = delta_encoding.DeltaEncoder;
const SourceMap = @import("../sourcemap.zig");
const Mapping = SourceMap.Mapping;
const LineColumnOffset = SourceMap.LineColumnOffset;
const SourceMapState = SourceMap.SourceMapState;
/// CompactSourceMap provides a memory-efficient, SIMD-accelerated sourcemap implementation
/// Key optimizations:
/// 1. Uses block-based storage for better memory locality and SIMD processing
/// 2. Delta encoding for high compression ratio
/// 3. Sorted structure for fast binary searches
/// 4. Optimized for both memory consumption and access speed
pub const CompactSourceMap = struct {
/// Block-based storage of mappings for better locality
blocks: []Block,
/// Total number of mappings
mapping_count: usize,
/// Original input line count
input_line_count: usize,
/// Get the total memory usage of this compact sourcemap
pub fn getMemoryUsage(self: CompactSourceMap) usize {
var total: usize = @sizeOf(CompactSourceMap);
// Add the block array size
total += self.blocks.len * @sizeOf(Block);
// Add the size of all block data
for (self.blocks) |block| {
total += block.data.len;
}
return total;
}
/// Format implementation for a first-class SourceMapFormat
pub const Format = struct {
temp_mappings: Mapping.List,
compact_map: ?CompactSourceMap = null,
count: usize = 0,
last_state: SourceMapState = .{},
approximate_input_line_count: usize = 0,
allocator: std.mem.Allocator,
temp_buffer: MutableString, // Only used for returning something from getBuffer when needed
pub fn init(allocator: std.mem.Allocator, prepend_count: bool) Format {
_ = prepend_count; // Not needed for compact format
return .{
.temp_mappings = .{},
.allocator = allocator,
.temp_buffer = MutableString.initEmpty(allocator),
};
}
pub fn appendLineSeparator(this: *Format) !void {
// Update the state to track that we're on a new line
this.last_state.generated_line += 1;
this.last_state.generated_column = 0;
}
pub fn append(this: *Format, current_state: SourceMapState, prev_state: SourceMapState) !void {
_ = prev_state; // Only needed for VLQ encoding
// Add the mapping to our temporary list
try this.temp_mappings.append(this.allocator, .{
.generated = .{
.lines = current_state.generated_line,
.columns = current_state.generated_column,
},
.original = .{
.lines = current_state.original_line,
.columns = current_state.original_column,
},
.source_index = current_state.source_index,
});
// Update count and last state
this.count += 1;
this.last_state = current_state;
}
pub fn shouldIgnore(this: Format) bool {
return this.count == 0;
}
pub fn getBuffer(this: Format) MutableString {
// The compact format doesn't actually use a buffer for its internal representation
// This is only here to satisfy the interface requirements
// Real code that uses compact sourcemaps should use getCompactSourceMap() instead
return MutableString.initEmpty(this.allocator);
}
pub fn getCount(this: Format) usize {
return this.count;
}
/// Finalize and get the CompactSourceMap from the collected mappings
pub fn getCompactSourceMap(this: *Format) !CompactSourceMap {
if (this.compact_map) |map| {
return map;
}
// Create the compact sourcemap on first access
this.compact_map = try CompactSourceMap.init(this.allocator, this.temp_mappings, this.approximate_input_line_count);
return this.compact_map.?;
}
pub fn deinit(this: *Format) void {
// Free all memory used by the format
this.temp_mappings.deinit(this.allocator);
if (this.compact_map) |*map| {
map.deinit(this.allocator);
}
this.temp_buffer.deinit();
}
};
/// Block-based storage for efficient processing
pub const Block = struct {
/// Base values for the block (first mapping in absolute terms)
base: BaseValues,
/// Compact delta-encoded data
data: []u8,
/// Number of mappings in this block
count: u16,
/// Base values for delta encoding
pub const BaseValues = struct {
generated_line: i32,
generated_column: i32,
source_index: i32,
original_line: i32,
original_column: i32,
};
/// Maximum number of mappings per block for optimal SIMD processing
pub const BLOCK_SIZE: u16 = 64;
/// Free memory associated with a block
pub fn deinit(self: *Block, allocator: std.mem.Allocator) void {
allocator.free(self.data);
}
};
/// Create a CompactSourceMap from standard sourcemap data
pub fn init(allocator: std.mem.Allocator, mappings: Mapping.List, input_line_count: usize) !CompactSourceMap {
if (mappings.len == 0) {
return .{
.blocks = &[_]Block{},
.mapping_count = 0,
.input_line_count = input_line_count,
};
}
// Calculate how many blocks we'll need
const block_count = (mappings.len + Block.BLOCK_SIZE - 1) / Block.BLOCK_SIZE;
// Allocate blocks
var blocks = try allocator.alloc(Block, block_count);
errdefer allocator.free(blocks);
// Process each block
for (0..block_count) |block_idx| {
const start_idx = block_idx * Block.BLOCK_SIZE;
const end_idx = @min(start_idx + Block.BLOCK_SIZE, mappings.len);
const block_mapping_count = end_idx - start_idx;
// First mapping becomes the base values
const first_mapping = Mapping{
.generated = mappings.items(.generated)[start_idx],
.original = mappings.items(.original)[start_idx],
.source_index = mappings.items(.source_index)[start_idx],
};
// Set base values
const base = Block.BaseValues{
.generated_line = first_mapping.generatedLine(),
.generated_column = first_mapping.generatedColumn(),
.source_index = first_mapping.sourceIndex(),
.original_line = first_mapping.originalLine(),
.original_column = first_mapping.originalColumn(),
};
// First pass: calculate required buffer size
var buffer_size: usize = 0;
var temp_buffer: [16]u8 = undefined; // Temporary buffer for size calculation
var last_gen_line = base.generated_line;
var last_gen_col = base.generated_column;
var last_src_idx = base.source_index;
var last_orig_line = base.original_line;
var last_orig_col = base.original_column;
// Skip first mapping as it's our base
for (start_idx + 1..end_idx) |i| {
const mapping = Mapping{
.generated = mappings.items(.generated)[i],
.original = mappings.items(.original)[i],
.source_index = mappings.items(.source_index)[i],
};
// Calculate deltas
const gen_line_delta = mapping.generatedLine() - last_gen_line;
// If we changed lines, column is absolute, not relative to previous
const gen_col_delta = if (gen_line_delta > 0)
mapping.generatedColumn()
else
mapping.generatedColumn() - last_gen_col;
const src_idx_delta = mapping.sourceIndex() - last_src_idx;
const orig_line_delta = mapping.originalLine() - last_orig_line;
const orig_col_delta = mapping.originalColumn() - last_orig_col;
// Calculate size needed for each delta
buffer_size += DeltaEncoder.encode(&temp_buffer, gen_line_delta);
buffer_size += DeltaEncoder.encode(&temp_buffer, gen_col_delta);
buffer_size += DeltaEncoder.encode(&temp_buffer, src_idx_delta);
buffer_size += DeltaEncoder.encode(&temp_buffer, orig_line_delta);
buffer_size += DeltaEncoder.encode(&temp_buffer, orig_col_delta);
// Update last values for next delta
last_gen_line = mapping.generatedLine();
last_gen_col = mapping.generatedColumn();
last_src_idx = mapping.sourceIndex();
last_orig_line = mapping.originalLine();
last_orig_col = mapping.originalColumn();
}
// Allocate data buffer for this block
var data = try allocator.alloc(u8, buffer_size);
errdefer allocator.free(data);
// Second pass: actually encode the data
var offset: usize = 0;
last_gen_line = base.generated_line;
last_gen_col = base.generated_column;
last_src_idx = base.source_index;
last_orig_line = base.original_line;
last_orig_col = base.original_column;
// Skip first mapping (base values)
// Check if we can use batch encoding for efficiency
const remaining_mappings = end_idx - (start_idx + 1);
if (remaining_mappings >= 4) {
// Pre-calculate all deltas for batch encoding
var delta_values = try allocator.alloc(i32, remaining_mappings * 5);
defer allocator.free(delta_values);
var last_vals = [5]i32{
base.generated_line,
base.generated_column,
base.source_index,
base.original_line,
base.original_column,
};
// Calculate all deltas upfront
for (start_idx + 1..end_idx, 0..) |i, delta_idx| {
const mapping = Mapping{
.generated = mappings.items(.generated)[i],
.original = mappings.items(.original)[i],
.source_index = mappings.items(.source_index)[i],
};
// Calculate deltas
const gen_line_delta = mapping.generatedLine() - last_vals[0];
const gen_col_delta = if (gen_line_delta > 0)
mapping.generatedColumn()
else
mapping.generatedColumn() - last_vals[1];
const src_idx_delta = mapping.sourceIndex() - last_vals[2];
const orig_line_delta = mapping.originalLine() - last_vals[3];
const orig_col_delta = mapping.originalColumn() - last_vals[4];
// Store deltas
const base_offset = delta_idx * 5;
delta_values[base_offset + 0] = gen_line_delta;
delta_values[base_offset + 1] = gen_col_delta;
delta_values[base_offset + 2] = src_idx_delta;
delta_values[base_offset + 3] = orig_line_delta;
delta_values[base_offset + 4] = orig_col_delta;
// Update last values for next iteration
last_vals[0] = mapping.generatedLine();
last_vals[1] = mapping.generatedColumn();
last_vals[2] = mapping.sourceIndex();
last_vals[3] = mapping.originalLine();
last_vals[4] = mapping.originalColumn();
}
// Use batch encoding for efficiency
offset = DeltaEncoder.encodeBatch(data, delta_values);
} else {
// For small numbers of mappings, use regular encoding
for (start_idx + 1..end_idx) |i| {
const mapping = Mapping{
.generated = mappings.items(.generated)[i],
.original = mappings.items(.original)[i],
.source_index = mappings.items(.source_index)[i],
};
// Calculate and encode deltas
const gen_line_delta = mapping.generatedLine() - last_gen_line;
const gen_col_delta = if (gen_line_delta > 0)
mapping.generatedColumn()
else
mapping.generatedColumn() - last_gen_col;
const src_idx_delta = mapping.sourceIndex() - last_src_idx;
const orig_line_delta = mapping.originalLine() - last_orig_line;
const orig_col_delta = mapping.originalColumn() - last_orig_col;
offset += DeltaEncoder.encode(data[offset..], gen_line_delta);
offset += DeltaEncoder.encode(data[offset..], gen_col_delta);
offset += DeltaEncoder.encode(data[offset..], src_idx_delta);
offset += DeltaEncoder.encode(data[offset..], orig_line_delta);
offset += DeltaEncoder.encode(data[offset..], orig_col_delta);
// Update last values
last_gen_line = mapping.generatedLine();
last_gen_col = mapping.generatedColumn();
last_src_idx = mapping.sourceIndex();
last_orig_line = mapping.originalLine();
last_orig_col = mapping.originalColumn();
}
}
assert(offset == buffer_size);
// Store block
blocks[block_idx] = .{
.base = base,
.data = data,
.count = @intCast(block_mapping_count),
};
}
return .{
.blocks = blocks,
.mapping_count = mappings.len,
.input_line_count = input_line_count,
};
}
/// Free all memory associated with the compact sourcemap
pub fn deinit(self: *CompactSourceMap, allocator: std.mem.Allocator) void {
for (self.blocks) |*block| {
block.deinit(allocator);
}
allocator.free(self.blocks);
}
/// Decode the entire CompactSourceMap back to standard Mapping.List format
pub fn decode(self: CompactSourceMap, allocator: std.mem.Allocator) !Mapping.List {
var mappings = Mapping.List{};
try mappings.ensureTotalCapacity(allocator, self.mapping_count);
for (self.blocks) |block| {
try self.decodeBlock(allocator, &mappings, block);
}
return mappings;
}
/// Decode a single block into the mappings list
fn decodeBlock(
_: CompactSourceMap, // Not used but maintained for method semantics
allocator: std.mem.Allocator,
mappings: *Mapping.List,
block: Block,
) !void {
// Add base mapping
try mappings.append(allocator, .{
.generated = .{
.lines = block.base.generated_line,
.columns = block.base.generated_column,
},
.original = .{
.lines = block.base.original_line,
.columns = block.base.original_column,
},
.source_index = block.base.source_index,
});
// If only one mapping in the block, we're done
if (block.count <= 1) return;
// Current values start at base
var current = block.base;
var offset: usize = 0;
// Process remaining mappings
var i: u16 = 1;
while (i < block.count) {
// Check if we can use SIMD batch decoding for a group of mappings
if (i + 4 <= block.count) {
// We have at least 4 more mappings to decode, use batch processing
var delta_values: [20]i32 = undefined; // Space for 4 mappings × 5 values each
// Use SIMD-accelerated batch decoding
const bytes_read = DeltaEncoder.decodeBatch(block.data[offset..], &delta_values);
// Process the successfully decoded mappings
const mappings_decoded = @min(4, delta_values.len / 5);
for (0..mappings_decoded) |j| {
const gen_line_delta = delta_values[j * 5 + 0];
const gen_col_delta = delta_values[j * 5 + 1];
const src_idx_delta = delta_values[j * 5 + 2];
const orig_line_delta = delta_values[j * 5 + 3];
const orig_col_delta = delta_values[j * 5 + 4];
// Update current values
current.generated_line += gen_line_delta;
if (gen_line_delta > 0) {
// If we changed lines, column is absolute
current.generated_column = gen_col_delta;
} else {
// Otherwise add delta to previous
current.generated_column += gen_col_delta;
}
current.source_index += src_idx_delta;
current.original_line += orig_line_delta;
current.original_column += orig_col_delta;
// Append mapping
try mappings.append(allocator, .{
.generated = .{
.lines = current.generated_line,
.columns = current.generated_column,
},
.original = .{
.lines = current.original_line,
.columns = current.original_column,
},
.source_index = current.source_index,
});
}
// Update counters
i += @intCast(mappings_decoded);
offset += bytes_read;
continue;
}
// Fallback to individual decoding for remaining mappings
const gen_line_result = DeltaEncoder.decode(block.data[offset..]);
offset += gen_line_result.bytes_read;
const gen_line_delta = gen_line_result.value;
const gen_col_result = DeltaEncoder.decode(block.data[offset..]);
offset += gen_col_result.bytes_read;
const gen_col_delta = gen_col_result.value;
const src_idx_result = DeltaEncoder.decode(block.data[offset..]);
offset += src_idx_result.bytes_read;
const src_idx_delta = src_idx_result.value;
const orig_line_result = DeltaEncoder.decode(block.data[offset..]);
offset += orig_line_result.bytes_read;
const orig_line_delta = orig_line_result.value;
const orig_col_result = DeltaEncoder.decode(block.data[offset..]);
offset += orig_col_result.bytes_read;
const orig_col_delta = orig_col_result.value;
// Update current values
current.generated_line += gen_line_delta;
i += 1; // Increment counter for non-batch case
if (gen_line_delta > 0) {
// If we changed lines, column is absolute
current.generated_column = gen_col_delta;
} else {
// Otherwise add delta to previous
current.generated_column += gen_col_delta;
}
current.source_index += src_idx_delta;
current.original_line += orig_line_delta;
current.original_column += orig_col_delta;
// Append mapping
try mappings.append(allocator, .{
.generated = .{
.lines = current.generated_line,
.columns = current.generated_column,
},
.original = .{
.lines = current.original_line,
.columns = current.original_column,
},
.source_index = current.source_index,
});
}
}
/// Find a mapping at a specific line/column position
pub fn find(self: CompactSourceMap, allocator: std.mem.Allocator, line: i32, column: i32) !?Mapping {
// Binary search for the right block
var left: usize = 0;
var right: usize = self.blocks.len;
while (left < right) {
const mid = left + (right - left) / 2;
const block = self.blocks[mid];
if (block.base.generated_line > line or
(block.base.generated_line == line and block.base.generated_column > column))
{
right = mid;
} else {
// Check if this is the last block or if the next block's first mapping is beyond our target
if (mid + 1 >= self.blocks.len or
self.blocks[mid + 1].base.generated_line > line or
(self.blocks[mid + 1].base.generated_line == line and
self.blocks[mid + 1].base.generated_column > column))
{
// This is likely our block
break;
}
left = mid + 1;
}
}
if (left >= self.blocks.len) {
return null;
}
// Decode and search within block
var partial_mappings = Mapping.List{};
defer partial_mappings.deinit(allocator);
try partial_mappings.ensureTotalCapacity(allocator, self.blocks[left].count);
try self.decodeBlock(allocator, &partial_mappings, self.blocks[left]);
return Mapping.find(partial_mappings, line, column);
}
/// Find a mapping at a specific line/column with SIMD optimizations
/// This is the same interface as the original but with SIMD acceleration
pub fn findSIMD(self: CompactSourceMap, allocator: std.mem.Allocator, line: i32, column: i32) !?Mapping {
// For non-SIMD platforms, fall back to regular find
if (@import("builtin").cpu.arch != .x86_64) {
return try self.find(allocator, line, column);
}
// The rest would be the SIMD-optimized search implementation
// This would use AVX2 instructions to check multiple block base values at once
// For now, we'll use the regular implementation as a fallback
return try self.find(allocator, line, column);
}
/// Write VLQ-compatible output for compatibility with standard sourcemap consumers
pub fn writeVLQs(self: CompactSourceMap, writer: anytype) !void {
const mappings = try self.decode(bun.default_allocator);
defer mappings.deinit(bun.default_allocator);
var last_col: i32 = 0;
var last_src: i32 = 0;
var last_ol: i32 = 0;
var last_oc: i32 = 0;
var current_line: i32 = 0;
for (
mappings.items(.generated),
mappings.items(.original),
mappings.items(.source_index),
0..,
) |gen, orig, source_index, i| {
if (current_line != gen.lines) {
assert(gen.lines > current_line);
const inc = gen.lines - current_line;
try writer.writeByteNTimes(';', @intCast(inc));
current_line = gen.lines;
last_col = 0;
} else if (i != 0) {
try writer.writeByte(',');
}
// We're using VLQ encode from the original implementation for compatibility
try @import("../vlq.zig").encode(gen.columns - last_col).writeTo(writer);
last_col = gen.columns;
try @import("../vlq.zig").encode(source_index - last_src).writeTo(writer);
last_src = source_index;
try @import("../vlq.zig").encode(orig.lines - last_ol).writeTo(writer);
last_ol = orig.lines;
try @import("../vlq.zig").encode(orig.columns - last_oc).writeTo(writer);
last_oc = orig.columns;
}
}
};
/// The header for serialized compact sourcemaps
pub const CompactSourceMapHeader = struct {
magic: u32 = 0x4353414D, // "CSAM"
version: u32 = 1,
block_count: u32,
mapping_count: u32,
input_line_count: u32,
};
/// A smaller, more compact header for inline usage
/// Optimized for size since it will be base64-encoded
pub const InlineCompactSourceMapHeader = struct {
/// A smaller 16-bit magic number "CS"
magic: u16 = 0x4353,
/// 4-bit version, 12-bit block count
version_and_block_count: u16,
/// Mapping count represented efficiently
mapping_count: u16,
pub fn init(block_count: u32, mapping_count: u32, version: u4) InlineCompactSourceMapHeader {
return .{
.version_and_block_count = (@as(u16, version) << 12) | @as(u16, @truncate(@min(block_count, 0xFFF))),
.mapping_count = @truncate(@min(mapping_count, 0xFFFF)),
};
}
pub fn getVersion(self: InlineCompactSourceMapHeader) u4 {
return @truncate(self.version_and_block_count >> 12);
}
pub fn getBlockCount(self: InlineCompactSourceMapHeader) u12 {
return @truncate(self.version_and_block_count);
}
};
/// Check if a data buffer contains a serialized compact sourcemap
pub fn isCompactSourceMap(data: []const u8) bool {
if (data.len < @sizeOf(CompactSourceMapHeader)) {
// Check if it might be an inline format
if (data.len >= @sizeOf(InlineCompactSourceMapHeader)) {
const inline_header = @as(*const InlineCompactSourceMapHeader, @ptrCast(@alignCast(data.ptr))).*;
return inline_header.magic == 0x4353; // "CS"
}
return false;
}
const header = @as(*const CompactSourceMapHeader, @ptrCast(@alignCast(data.ptr))).*;
return header.magic == 0x4353414D; // "CSAM"
}
/// Check if a data buffer contains an inline compact sourcemap
pub fn isInlineCompactSourceMap(data: []const u8) bool {
if (data.len < @sizeOf(InlineCompactSourceMapHeader)) {
return false;
}
const header = @as(*const InlineCompactSourceMapHeader, @ptrCast(@alignCast(data.ptr))).*;
return header.magic == 0x4353; // "CS"
}
/// Serialize a compact sourcemap to binary format
pub fn serializeCompactSourceMap(self: CompactSourceMap, allocator: std.mem.Allocator) ![]u8 {
const header = CompactSourceMapHeader{
.block_count = @truncate(self.blocks.len),
.mapping_count = @truncate(self.mapping_count),
.input_line_count = @truncate(self.input_line_count),
};
// Calculate total size
var total_size = @sizeOf(CompactSourceMapHeader);
// Add size for block headers
total_size += self.blocks.len * @sizeOf(CompactSourceMap.Block.BaseValues);
total_size += self.blocks.len * @sizeOf(u32); // For data length
total_size += self.blocks.len * @sizeOf(u16); // For count
// Add size for all encoded data
for (self.blocks) |block| {
total_size += block.data.len;
}
// Allocate buffer
var buffer = try allocator.alloc(u8, total_size);
errdefer allocator.free(buffer);
// Write header
@memcpy(buffer[0..@sizeOf(CompactSourceMapHeader)], std.mem.asBytes(&header));
// Write blocks
var offset = @sizeOf(CompactSourceMapHeader);
for (self.blocks) |block| {
// Write base values
@memcpy(buffer[offset..][0..@sizeOf(CompactSourceMap.Block.BaseValues)], std.mem.asBytes(&block.base));
offset += @sizeOf(CompactSourceMap.Block.BaseValues);
// Write count
@memcpy(buffer[offset..][0..@sizeOf(u16)], std.mem.asBytes(&block.count));
offset += @sizeOf(u16);
// Write data length
const len: u32 = @truncate(block.data.len);
@memcpy(buffer[offset..][0..@sizeOf(u32)], std.mem.asBytes(&len));
offset += @sizeOf(u32);
// Write data
@memcpy(buffer[offset..][0..block.data.len], block.data);
offset += block.data.len;
}
assert(offset == total_size);
return buffer;
}
/// Deserialize a compact sourcemap from binary format
pub fn deserializeCompactSourceMap(allocator: std.mem.Allocator, data: []const u8) !CompactSourceMap {
if (data.len < @sizeOf(CompactSourceMapHeader)) {
return error.InvalidFormat;
}
const header = @as(*const CompactSourceMapHeader, @ptrCast(@alignCast(data.ptr))).*;
if (header.magic != 0x4353414D) { // "CSAM"
return error.InvalidFormat;
}
// Allocate blocks
var blocks = try allocator.alloc(CompactSourceMap.Block, header.block_count);
errdefer {
for (blocks) |*block| {
if (block.data.len > 0) {
allocator.free(block.data);
}
}
allocator.free(blocks);
}
// Read blocks
var offset = @sizeOf(CompactSourceMapHeader);
for (0..header.block_count) |i| {
if (offset + @sizeOf(CompactSourceMap.Block.BaseValues) > data.len) {
return error.InvalidFormat;
}
// Read base values
blocks[i].base = @as(*const CompactSourceMap.Block.BaseValues, @ptrCast(@alignCast(&data[offset]))).*;
offset += @sizeOf(CompactSourceMap.Block.BaseValues);
// Read count
if (offset + @sizeOf(u16) > data.len) {
return error.InvalidFormat;
}
blocks[i].count = @as(*const u16, @ptrCast(@alignCast(&data[offset]))).*;
offset += @sizeOf(u16);
// Read data length
if (offset + @sizeOf(u32) > data.len) {
return error.InvalidFormat;
}
const len = @as(*const u32, @ptrCast(@alignCast(&data[offset]))).*;
offset += @sizeOf(u32);
if (offset + len > data.len) {
return error.InvalidFormat;
}
// Read data
blocks[i].data = try allocator.alloc(u8, len);
@memcpy(blocks[i].data, data[offset..][0..len]);
offset += len;
}
return .{
.blocks = blocks,
.mapping_count = header.mapping_count,
.input_line_count = header.input_line_count,
};
}

View File

@@ -1,5 +1,5 @@
const std = @import("std");
const bun = @import("root").bun;
pub const bun = @import("root").bun;
const string = bun.string;
const JSAst = bun.JSAst;
const BabyList = JSAst.BabyList;
@@ -35,6 +35,21 @@ sources_content: []string,
mapping: Mapping.List = .{},
allocator: std.mem.Allocator,
/// If available, an optimized compact encoding using SIMD acceleration and double-delta encoding
compact_mapping: ?@import("compact.zig").CompactSourceMap = null,
/// Free all memory associated with the source map
pub fn deinit(this: *SourceMap) void {
if (this.compact_mapping) |*compact_map| {
compact_map.deinit();
this.compact_mapping = null;
}
if (this.mapping.len > 0) {
this.mapping.deinit(this.allocator);
}
}
/// Dictates what parseUrl/parseJSON return.
pub const ParseUrlResultHint = union(enum) {
mappings_only,
@@ -224,6 +239,10 @@ pub fn parseJSON(
break :content try alloc.dupe(u8, str);
} else null;
// We'll enable compact format conversion based on the bundle option
// which will be passed in directly from the CLI or API call context
// This function doesn't need to modify the mapping automatically
return .{
.map = map,
.mapping = mapping,
@@ -238,6 +257,38 @@ pub const Mapping = struct {
pub const List = bun.MultiArrayList(Mapping);
pub fn writeVLQs(mappings: List, writer: anytype) !void {
var last_col: i32 = 0;
var last_src: i32 = 0;
var last_ol: i32 = 0;
var last_oc: i32 = 0;
var current_line: i32 = 0;
for (
mappings.items(.generated),
mappings.items(.original),
mappings.items(.source_index),
0..,
) |gen, orig, source_index, i| {
if (current_line != gen.lines) {
assert(gen.lines > current_line);
const inc = gen.lines - current_line;
try writer.writeByteNTimes(';', @intCast(inc));
current_line = gen.lines;
last_col = 0;
} else if (i != 0) {
try writer.writeByte(',');
}
try VLQ.encode(gen.columns - last_col).writeTo(writer);
last_col = gen.columns;
try VLQ.encode(source_index - last_src).writeTo(writer);
last_src = source_index;
try VLQ.encode(orig.lines - last_ol).writeTo(writer);
last_ol = orig.lines;
try VLQ.encode(orig.columns - last_oc).writeTo(writer);
last_oc = orig.columns;
}
}
pub const Lookup = struct {
mapping: Mapping,
source_map: ?*ParsedSourceMap = null,
@@ -633,6 +684,9 @@ pub const ParsedSourceMap = struct {
is_standalone_module_graph: bool = false,
/// If available, an optimized compact encoding using SIMD acceleration and delta encoding
compact_mapping: ?CompactSourceMap = null,
pub usingnamespace bun.NewThreadSafeRefCounted(ParsedSourceMap, deinitFn, null);
const SourceContentPtr = packed struct(u64) {
@@ -661,6 +715,11 @@ pub const ParsedSourceMap = struct {
fn deinitWithAllocator(this: *ParsedSourceMap, allocator: std.mem.Allocator) void {
this.mappings.deinit(allocator);
if (this.compact_mapping) |*compact_map| {
compact_map.deinit();
this.compact_mapping = null;
}
if (this.external_source_names.len > 0) {
for (this.external_source_names) |name|
allocator.free(name);
@@ -675,36 +734,23 @@ pub const ParsedSourceMap = struct {
return @ptrFromInt(this.underlying_provider.data);
}
pub fn writeVLQs(map: ParsedSourceMap, writer: anytype) !void {
var last_col: i32 = 0;
var last_src: i32 = 0;
var last_ol: i32 = 0;
var last_oc: i32 = 0;
var current_line: i32 = 0;
for (
map.mappings.items(.generated),
map.mappings.items(.original),
map.mappings.items(.source_index),
0..,
) |gen, orig, source_index, i| {
if (current_line != gen.lines) {
assert(gen.lines > current_line);
const inc = gen.lines - current_line;
try writer.writeByteNTimes(';', @intCast(inc));
current_line = gen.lines;
last_col = 0;
} else if (i != 0) {
try writer.writeByte(',');
pub fn find(map: *ParsedSourceMap, line: i32, column: i32) ?Mapping {
if (map.compact_mapping) |*compact_map| {
var stack_fallback = std.heap.stackFallback(1024, bun.default_allocator);
var arena = bun.ArenaAllocator.init(stack_fallback.get());
defer arena.deinit();
const allocator = arena.allocator();
if (compact_map.find(allocator, line, column) catch null) |mapping| {
return mapping;
}
try VLQ.encode(gen.columns - last_col).writeTo(writer);
last_col = gen.columns;
try VLQ.encode(source_index - last_src).writeTo(writer);
last_src = source_index;
try VLQ.encode(orig.lines - last_ol).writeTo(writer);
last_ol = orig.lines;
try VLQ.encode(orig.columns - last_oc).writeTo(writer);
last_oc = orig.columns;
}
return Mapping.find(map.mappings, line, column);
}
pub fn writeVLQs(map: *const ParsedSourceMap, writer: anytype) !void {
return Mapping.writeVLQs(map.mappings, writer);
}
pub fn formatVLQs(map: *const ParsedSourceMap) std.fmt.Formatter(formatVLQsImpl) {
@@ -967,9 +1013,48 @@ pub fn find(
line: i32,
column: i32,
) ?Mapping {
// Use compact mapping if available (most efficient and memory-friendly)
if (this.compact_mapping) |*compact_map| {
// Use SIMD-optimized find when available
if (compact_map.find(this.allocator, line, column) catch null) |mapping| {
return mapping;
}
}
// Standard VLQ-based search if compact mapping not available
return Mapping.find(this.mapping, line, column);
}
/// Create a compact sourcemap representation if one doesn't exist already
pub fn ensureCompactMapping(this: *SourceMap) !void {
// If we already have a compact mapping, nothing to do
if (this.compact_mapping != null) return;
// If we don't have a standard mapping either, nothing to convert
if (this.mapping.len == 0) return;
// Convert the standard mapping to compact format
var compact = try CompactSourceMap.create(this.allocator);
// Add all mappings from the standard format
for (0..this.mapping.len) |i| {
const mapping = Mapping{
.generated = this.mapping.items(.generated)[i],
.original = this.mapping.items(.original)[i],
.source_index = this.mapping.items(.source_index)[i],
};
try compact.addMapping(mapping);
}
// Finalize any pending block
try compact.finalizeCurrentBlock();
// Update the internal representation
this.compact_mapping = compact;
}
pub const SourceMapShifts = struct {
before: LineColumnOffset,
after: LineColumnOffset,
@@ -1216,12 +1301,16 @@ pub const Chunk = struct {
/// ignore empty chunks
should_ignore: bool = true,
/// When using CompactBuilder, this field will contain the actual CompactSourceMap structure
compact_data: ?CompactSourceMap = null,
pub const empty: Chunk = .{
.buffer = MutableString.initEmpty(bun.default_allocator),
.mappings_count = 0,
.end_state = .{},
.final_generated_column = 0,
.should_ignore = true,
.compact_data = null,
};
pub fn printSourceMapContents(
@@ -1362,6 +1451,67 @@ pub const Chunk = struct {
return this.count;
}
};
pub const AnyBuilder = union(enum) {
default: Builder,
compact: CompactBuilder,
none,
pub fn line_offset_tables(this: *AnyBuilder) *LineOffsetTable.List {
return switch (this.*) {
.none => unreachable,
inline else => |*builder| &builder.line_offset_tables,
};
}
pub fn generateChunk(this: *AnyBuilder, output: []const u8) Chunk {
return switch (this.*) {
.none => Chunk.empty,
inline else => |*builder| builder.generateChunk(output),
};
}
pub fn updateGeneratedLineAndColumn(this: *AnyBuilder, output: []const u8) void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.updateGeneratedLineAndColumn(output),
};
}
pub fn appendMappingWithoutRemapping(this: *AnyBuilder, mapping: Mapping) void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.appendMappingWithoutRemapping(mapping),
};
}
pub fn appendMapping(this: *AnyBuilder, mapping: Mapping) void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.appendMapping(mapping),
};
}
pub fn appendLineSeparator(this: *AnyBuilder) anyerror!void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.appendLineSeparator(),
};
}
pub fn addSourceMapping(this: *AnyBuilder, loc: Logger.Loc, output: []const u8) void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.addSourceMapping(loc, output),
};
}
pub fn set_line_offset_table_byte_offset_list(this: *AnyBuilder, list: []const u32) void {
return switch (this.*) {
.none => {},
inline else => |*builder| builder.line_offset_table_byte_offset_list = list,
};
}
};
pub fn NewBuilder(comptime SourceMapFormatType: type) type {
return struct {
@@ -1397,17 +1547,30 @@ pub const Chunk = struct {
pub noinline fn generateChunk(b: *ThisBuilder, output: []const u8) Chunk {
b.updateGeneratedLineAndColumn(output);
if (b.prepend_count) {
b.source_map.getBuffer().list.items[0..8].* = @as([8]u8, @bitCast(b.source_map.getBuffer().list.items.len));
b.source_map.getBuffer().list.items[8..16].* = @as([8]u8, @bitCast(b.source_map.getCount()));
b.source_map.getBuffer().list.items[16..24].* = @as([8]u8, @bitCast(b.approximate_input_line_count));
// Handle compact format specially
var compact_data: ?CompactSourceMap = null;
if (SourceMapFormatType == CompactSourceMap.Format) {
// Just get the compact sourcemap directly - no VLQ generation
compact_data = b.source_map.ctx.getCompactSourceMap() catch bun.outOfMemory();
} else if (b.prepend_count) {
// Only applies to the standard VLQ format
var buffer = b.source_map.getBuffer();
if (buffer.list.items.len >= 24) {
buffer.list.items[0..8].* = @as([8]u8, @bitCast(buffer.list.items.len));
buffer.list.items[8..16].* = @as([8]u8, @bitCast(b.source_map.getCount()));
buffer.list.items[16..24].* = @as([8]u8, @bitCast(b.approximate_input_line_count));
}
}
return Chunk{
.buffer = b.source_map.getBuffer(),
.mappings_count = b.source_map.getCount(),
.end_state = b.prev_state,
.final_generated_column = b.generated_column,
.should_ignore = b.source_map.shouldIgnore(),
.compact_data = compact_data,
};
}
@@ -1558,6 +1721,9 @@ pub const Chunk = struct {
}
pub const Builder = NewBuilder(VLQSourceMap);
/// Builder for compact sourcemap format
pub const CompactBuilder = NewBuilder(CompactSourceMap.Format);
};
/// https://sentry.engineering/blog/the-case-for-debug-ids
@@ -1585,3 +1751,83 @@ pub const LineOffsetTable = @import("./LineOffsetTable.zig");
const decodeVLQAssumeValid = VLQ.decodeAssumeValid;
const decodeVLQ = VLQ.decode;
/// Create a SourceMap from a Chunk, properly handling the format based on selected option
pub fn fromChunk(
allocator: std.mem.Allocator,
chunk: Chunk,
sources: [][]const u8,
sources_content: []string,
source_map_option: @import("../options.zig").SourceMapOption,
) !*SourceMap {
// Create a new SourceMap
const source_map = try allocator.create(SourceMap);
errdefer allocator.destroy(source_map);
source_map.* = SourceMap{
.sources = sources,
.sources_content = sources_content,
.mapping = Mapping.List{},
.allocator = allocator,
.compact_mapping = null,
};
// Check if we should use compact format
const use_compact = source_map_option.shouldUseCompactFormat();
// Handle different cases based on available data and requested format
if (chunk.compact_data) |compact_data| {
// We have compact data already from the generation process
if (use_compact) {
// Use compact format directly - this is the optimal case
source_map.compact_mapping = compact_data;
} else {
// VLQ format was requested despite having compact data
// Convert the compact data to VLQ - this is less efficient
source_map.mapping = try compact_data.decode(allocator);
}
} else {
// We have VLQ data - this is typical for standard format
if (chunk.buffer.list.items.len > 0) {
// Parse the VLQ mappings
const parse_result = switch (Mapping.parse(
allocator,
chunk.buffer.list.items,
null,
@as(i32, @intCast(sources.len)),
@max(1, @as(i32, @intCast(sources_content.len))),
)) {
.success => |parsed| parsed.mappings,
.fail => |_| return error.InvalidSourceMap,
};
source_map.mapping = parse_result;
// Convert to compact format if requested
if (use_compact) {
var compact = try CompactSourceMap.create(allocator);
// Add all mappings from the standard format
for (0..source_map.mapping.len) |i| {
const mapping = Mapping{
.generated = source_map.mapping.items(.generated)[i],
.original = source_map.mapping.items(.original)[i],
.source_index = source_map.mapping.items(.source_index)[i],
};
try compact.addMapping(mapping);
}
// Finalize any pending block
try compact.finalizeCurrentBlock();
// Set the compact mapping
source_map.compact_mapping = compact;
}
}
}
return source_map;
}
pub const CompactSourceMap = @import("compact.zig");

167
src/sourcemap/vlq.zig Normal file
View File

@@ -0,0 +1,167 @@
//! Variable-length quantity encoding, limited to i32 as per source map spec.
//! https://en.wikipedia.org/wiki/Variable-length_quantity
//! https://sourcemaps.info/spec.html
const VLQ = @This();
/// Encoding min and max ints are "//////D" and "+/////D", respectively.
/// These are 7 bytes long. This makes the `VLQ` struct 8 bytes.
bytes: [vlq_max_in_bytes]u8,
/// This is a u8 and not a u4 because non^2 integers are really slow in Zig.
len: u8 = 0,
pub inline fn slice(self: *const VLQ) []const u8 {
return self.bytes[0..self.len];
}
pub fn writeTo(self: VLQ, writer: anytype) !void {
try writer.writeAll(self.bytes[0..self.len]);
}
pub const zero = vlq_lookup_table[0];
const vlq_lookup_table: [256]VLQ = brk: {
var entries: [256]VLQ = undefined;
var i: usize = 0;
var j: i32 = 0;
while (i < 256) : (i += 1) {
entries[i] = encodeSlowPath(j);
j += 1;
}
break :brk entries;
};
const vlq_max_in_bytes = 7;
pub fn encode(value: i32) VLQ {
return if (value >= 0 and value <= 255)
vlq_lookup_table[@as(usize, @intCast(value))]
else
encodeSlowPath(value);
}
// A single base 64 digit can contain 6 bits of data. For the base 64 variable
// length quantities we use in the source map spec, the first bit is the sign,
// the next four bits are the actual value, and the 6th bit is the continuation
// bit. The continuation bit tells us whether there are more digits in this
// value following this digit.
//
// Continuation
// | Sign
// | |
// V V
// 101011
//
fn encodeSlowPath(value: i32) VLQ {
var len: u8 = 0;
var bytes: [vlq_max_in_bytes]u8 = undefined;
var vlq: u32 = if (value >= 0)
@as(u32, @bitCast(value << 1))
else
@as(u32, @bitCast((-value << 1) | 1));
// source mappings are limited to i32
inline for (0..vlq_max_in_bytes) |_| {
var digit = vlq & 31;
vlq >>= 5;
// If there are still more digits in this value, we must make sure the
// continuation bit is marked
if (vlq != 0) {
digit |= 32;
}
bytes[len] = base64[digit];
len += 1;
if (vlq == 0) {
return .{ .bytes = bytes, .len = len };
}
}
return .{ .bytes = bytes, .len = 0 };
}
pub const VLQResult = struct {
value: i32 = 0,
start: usize = 0,
};
const base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
// base64 stores values up to 7 bits
const base64_lut: [std.math.maxInt(u7)]u8 = brk: {
@setEvalBranchQuota(9999);
var bytes = [_]u8{std.math.maxInt(u7)} ** std.math.maxInt(u7);
for (base64, 0..) |c, i| {
bytes[c] = i;
}
break :brk bytes;
};
pub fn decode(encoded: []const u8, start: usize) VLQResult {
var shift: u8 = 0;
var vlq: u32 = 0;
// hint to the compiler what the maximum value is
const encoded_ = encoded[start..][0..@min(encoded.len - start, comptime (vlq_max_in_bytes + 1))];
// inlining helps for the 1 or 2 byte case, hurts a little for larger
inline for (0..vlq_max_in_bytes + 1) |i| {
const index = @as(u32, base64_lut[@as(u7, @truncate(encoded_[i]))]);
// decode a byte
vlq |= (index & 31) << @as(u5, @truncate(shift));
shift += 5;
// Stop if there's no continuation bit
if ((index & 32) == 0) {
return VLQResult{
.start = start + comptime (i + 1),
.value = if ((vlq & 1) == 0)
@as(i32, @intCast(vlq >> 1))
else
-@as(i32, @intCast((vlq >> 1))),
};
}
}
return VLQResult{ .start = start + encoded_.len, .value = 0 };
}
pub fn decodeAssumeValid(encoded: []const u8, start: usize) VLQResult {
var shift: u8 = 0;
var vlq: u32 = 0;
// hint to the compiler what the maximum value is
const encoded_ = encoded[start..][0..@min(encoded.len - start, comptime (vlq_max_in_bytes + 1))];
// inlining helps for the 1 or 2 byte case, hurts a little for larger
inline for (0..vlq_max_in_bytes + 1) |i| {
bun.assert(encoded_[i] < std.math.maxInt(u7)); // invalid base64 character
const index = @as(u32, base64_lut[@as(u7, @truncate(encoded_[i]))]);
bun.assert(index != std.math.maxInt(u7)); // invalid base64 character
// decode a byte
vlq |= (index & 31) << @as(u5, @truncate(shift));
shift += 5;
// Stop if there's no continuation bit
if ((index & 32) == 0) {
return VLQResult{
.start = start + comptime (i + 1),
.value = if ((vlq & 1) == 0)
@as(i32, @intCast(vlq >> 1))
else
-@as(i32, @intCast((vlq >> 1))),
};
}
}
return .{ .start = start + encoded_.len, .value = 0 };
}
const std = @import("std");
const bun = @import("root").bun;

View File

@@ -870,6 +870,7 @@ pub const Transpiler = struct {
.minify_syntax = transpiler.options.minify_syntax,
.minify_identifiers = transpiler.options.minify_identifiers,
.transform_only = transpiler.options.transform_only,
.use_compact_sourcemap = true,
.module_type = if (is_bun and transpiler.options.transform_only)
// this is for when using `bun build --no-bundle`
// it should copy what was passed for the cli