aboutsummaryrefslogtreecommitdiff
path: root/src/install
diff options
context:
space:
mode:
Diffstat (limited to 'src/install')
-rw-r--r--src/install/bit_set.zig1825
-rw-r--r--src/install/install.zig2
-rw-r--r--src/install/lockfile.zig2
-rw-r--r--src/install/semver.zig2
4 files changed, 3 insertions, 1828 deletions
diff --git a/src/install/bit_set.zig b/src/install/bit_set.zig
deleted file mode 100644
index 661a3a4bf..000000000
--- a/src/install/bit_set.zig
+++ /dev/null
@@ -1,1825 +0,0 @@
-//! This file defines several variants of bit sets. A bit set
-//! is a densely stored set of integers with a known maximum,
-//! in which each integer gets a single bit. Bit sets have very
-//! fast presence checks, update operations, and union and intersection
-//! operations. However, if the number of possible items is very
-//! large and the number of actual items in a given set is usually
-//! small, they may be less memory efficient than an array set.
-//!
-//! There are five variants defined here:
-//!
-//! IntegerBitSet:
-//! A bit set with static size, which is backed by a single integer.
-//! This set is good for sets with a small size, but may generate
-//! inefficient code for larger sets, especially in debug mode.
-//!
-//! ArrayBitSet:
-//! A bit set with static size, which is backed by an array of usize.
-//! This set is good for sets with a larger size, but may use
-//! more bytes than necessary if your set is small.
-//!
-//! StaticBitSet:
-//! Picks either IntegerBitSet or ArrayBitSet depending on the requested
-//! size. The interfaces of these two types match exactly, except for fields.
-//!
-//! DynamicBitSet:
-//! A bit set with runtime-known size, backed by an allocated slice
-//! of usize.
-//!
-//! DynamicBitSetUnmanaged:
-//! A variant of DynamicBitSet which does not store a pointer to its
-//! allocator, in order to save space.
-
-const std = @import("std");
-const Allocator = std.mem.Allocator;
-const bun = @import("bun");
-const Environment = bun.Environment;
-
-/// Returns the optimal static bit set type for the specified number
-/// of elements. The returned type will perform no allocations,
-/// can be copied by value, and does not require deinitialization.
-/// Both possible implementations fulfill the same interface.
-pub fn StaticBitSet(comptime size: usize) type {
- if (size <= @bitSizeOf(usize)) {
- return IntegerBitSet(size);
- } else {
- return ArrayBitSet(usize, size);
- }
-}
-
-/// A bit set with static size, which is backed by a single integer.
-/// This set is good for sets with a small size, but may generate
-/// inefficient code for larger sets, especially in debug mode.
-pub fn IntegerBitSet(comptime size: u16) type {
- return packed struct {
- const Self = @This();
-
- // TODO: Make this a comptime field once those are fixed
- /// The number of items in this bit set
- pub const bit_length: usize = size;
-
- /// The integer type used to represent a mask in this bit set
- pub const MaskInt = std.meta.Int(.unsigned, size);
-
- /// The integer type used to shift a mask in this bit set
- pub const ShiftInt = std.math.Log2Int(MaskInt);
-
- /// The bit mask, as a single integer
- mask: MaskInt,
-
- /// Creates a bit set with no elements present.
- pub fn initEmpty() Self {
- return .{ .mask = 0 };
- }
-
- /// Creates a bit set with all elements present.
- pub fn initFull() Self {
- return .{ .mask = ~@as(MaskInt, 0) };
- }
-
- /// Returns the number of bits in this bit set
- pub inline fn capacity(self: Self) usize {
- _ = self;
- return bit_length;
- }
-
- /// Returns true if the bit at the specified index
- /// is present in the set, false otherwise.
- pub fn isSet(self: Self, index: usize) bool {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- return (self.mask & maskBit(index)) != 0;
- }
-
- /// Returns the total number of set bits in this bit set.
- pub fn count(self: Self) usize {
- return @popCount(self.mask);
- }
-
- /// Changes the value of the specified bit of the bit
- /// set to match the passed boolean.
- pub fn setValue(self: *Self, index: usize, value: bool) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (MaskInt == u0) return;
- const bit = maskBit(index);
- const new_bit = bit & std.math.boolMask(MaskInt, value);
- self.mask = (self.mask & ~bit) | new_bit;
- }
-
- /// Adds a specific bit to the bit set
- pub fn set(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- self.mask |= maskBit(index);
- }
-
- /// Changes the value of all bits in the specified range to
- /// match the passed boolean.
- pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
- if (comptime Environment.allow_assert) {
- std.debug.assert(range.end <= bit_length);
- std.debug.assert(range.start <= range.end);
- }
- if (range.start == range.end) return;
- if (MaskInt == u0) return;
-
- const start_bit = @intCast(ShiftInt, range.start);
-
- var mask = std.math.boolMask(MaskInt, true) << start_bit;
- if (range.end != bit_length) {
- const end_bit = @intCast(ShiftInt, range.end);
- mask &= std.math.boolMask(MaskInt, true) >> @truncate(ShiftInt, @as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit));
- }
- self.mask &= ~mask;
-
- mask = std.math.boolMask(MaskInt, value) << start_bit;
- if (range.end != bit_length) {
- const end_bit = @intCast(ShiftInt, range.end);
- mask &= std.math.boolMask(MaskInt, value) >> @truncate(ShiftInt, @as(usize, @bitSizeOf(MaskInt)) - @as(usize, end_bit));
- }
- self.mask |= mask;
- }
-
- /// Removes a specific bit from the bit set
- pub fn unset(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- // Workaround for #7953
- if (MaskInt == u0) return;
- self.mask &= ~maskBit(index);
- }
-
- /// Flips a specific bit in the bit set
- pub fn toggle(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- self.mask ^= maskBit(index);
- }
-
- /// Flips all bits in this bit set which are present
- /// in the toggles bit set.
- pub fn toggleSet(self: *Self, toggles: Self) void {
- self.mask ^= toggles.mask;
- }
-
- /// Flips every bit in the bit set.
- pub fn toggleAll(self: *Self) void {
- self.mask = ~self.mask;
- }
-
- /// Performs a union of two bit sets, and stores the
- /// result in the first one. Bits in the result are
- /// set if the corresponding bits were set in either input.
- pub fn setUnion(self: *Self, other: Self) void {
- self.mask |= other.mask;
- }
-
- /// Performs an intersection of two bit sets, and stores
- /// the result in the first one. Bits in the result are
- /// set if the corresponding bits were set in both inputs.
- pub fn setIntersection(self: *Self, other: Self) void {
- self.mask &= other.mask;
- }
-
- /// Finds the index of the first set bit.
- /// If no bits are set, returns null.
- pub fn findFirstSet(self: Self) ?usize {
- const mask = self.mask;
- if (mask == 0) return null;
- return @ctz(mask);
- }
-
- /// Finds the index of the first set bit, and unsets it.
- /// If no bits are set, returns null.
- pub fn toggleFirstSet(self: *Self) ?usize {
- const mask = self.mask;
- if (mask == 0) return null;
- const index = @ctz(mask);
- self.mask = mask & (mask - 1);
- return index;
- }
-
- /// Returns true iff every corresponding bit in both
- /// bit sets are the same.
- pub fn eql(self: Self, other: Self) bool {
- return bit_length == 0 or self.mask == other.mask;
- }
-
- /// Returns true iff the first bit set is the subset
- /// of the second one.
- pub fn subsetOf(self: Self, other: Self) bool {
- return self.intersectWith(other).eql(self);
- }
-
- /// Returns true iff the first bit set is the superset
- /// of the second one.
- pub fn supersetOf(self: Self, other: Self) bool {
- return other.subsetOf(self);
- }
-
- /// Returns the complement bit sets. Bits in the result
- /// are set if the corresponding bits were not set.
- pub fn complement(self: Self) Self {
- var result = self;
- result.toggleAll();
- return result;
- }
-
- /// Returns the union of two bit sets. Bits in the
- /// result are set if the corresponding bits were set
- /// in either input.
- pub fn unionWith(self: Self, other: Self) Self {
- var result = self;
- result.setUnion(other);
- return result;
- }
-
- /// Returns the intersection of two bit sets. Bits in
- /// the result are set if the corresponding bits were
- /// set in both inputs.
- pub fn intersectWith(self: Self, other: Self) Self {
- var result = self;
- result.setIntersection(other);
- return result;
- }
-
- /// Returns the xor of two bit sets. Bits in the
- /// result are set if the corresponding bits were
- /// not the same in both inputs.
- pub fn xorWith(self: Self, other: Self) Self {
- var result = self;
- result.toggleSet(other);
- return result;
- }
-
- /// Returns the difference of two bit sets. Bits in
- /// the result are set if set in the first but not
- /// set in the second set.
- pub fn differenceWith(self: Self, other: Self) Self {
- var result = self;
- result.setIntersection(other.complement());
- return result;
- }
-
- /// Iterates through the items in the set, according to the options.
- /// The default options (.{}) will iterate indices of set bits in
- /// ascending order. Modifications to the underlying bit set may
- /// or may not be observed by the iterator.
- pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
- return .{
- .bits_remain = switch (options.kind) {
- .set => self.mask,
- .unset => ~self.mask,
- },
- };
- }
-
- pub fn Iterator(comptime options: IteratorOptions) type {
- return SingleWordIterator(options.direction);
- }
-
- fn SingleWordIterator(comptime direction: IteratorOptions.Direction) type {
- return struct {
- const IterSelf = @This();
- // all bits which have not yet been iterated over
- bits_remain: MaskInt,
-
- /// Returns the index of the next unvisited set bit
- /// in the bit set, in ascending order.
- pub fn next(self: *IterSelf) ?usize {
- if (self.bits_remain == 0) return null;
-
- switch (direction) {
- .forward => {
- const next_index = @ctz(self.bits_remain);
- self.bits_remain &= self.bits_remain - 1;
- return next_index;
- },
- .reverse => {
- const leading_zeroes = @clz(self.bits_remain);
- const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
- self.bits_remain &= (@as(MaskInt, 1) << @intCast(ShiftInt, top_bit)) - 1;
- return top_bit;
- },
- }
- }
- };
- }
-
- fn maskBit(index: usize) MaskInt {
- if (MaskInt == u0) return 0;
- return @as(MaskInt, 1) << @intCast(ShiftInt, index);
- }
- fn boolMaskBit(index: usize, value: bool) MaskInt {
- if (MaskInt == u0) return 0;
- return @as(MaskInt, @boolToInt(value)) << @intCast(ShiftInt, index);
- }
- };
-}
-
-/// A bit set with static size, which is backed by an array of usize.
-/// This set is good for sets with a larger size, but may use
-/// more bytes than necessary if your set is small.
-pub fn ArrayBitSet(comptime MaskIntType: type, comptime size: usize) type {
- const mask_info: std.builtin.Type = @typeInfo(MaskIntType);
-
- // Make sure the mask int is indeed an int
- if (mask_info != .Int) @compileError("ArrayBitSet can only operate on integer masks, but was passed " ++ @typeName(MaskIntType));
-
- // It must also be unsigned.
- if (mask_info.Int.signedness != .unsigned) @compileError("ArrayBitSet requires an unsigned integer mask type, but was passed " ++ @typeName(MaskIntType));
-
- // And it must not be empty.
- if (MaskIntType == u0)
- @compileError("ArrayBitSet requires a sized integer for its mask int. u0 does not work.");
-
- const byte_size = std.mem.byte_size_in_bits;
-
- // We use shift and truncate to decompose indices into mask indices and bit indices.
- // This operation requires that the mask has an exact power of two number of bits.
- if (!std.math.isPowerOfTwo(@bitSizeOf(MaskIntType))) {
- var desired_bits = std.math.ceilPowerOfTwoAssert(usize, @bitSizeOf(MaskIntType));
- if (desired_bits < byte_size) desired_bits = byte_size;
- const FixedMaskType = std.meta.Int(.unsigned, desired_bits);
- @compileError("ArrayBitSet was passed integer type " ++ @typeName(MaskIntType) ++
- ", which is not a power of two. Please round this up to a power of two integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
- }
-
- // Make sure the integer has no padding bits.
- // Those would be wasteful here and are probably a mistake by the user.
- // This case may be hit with small powers of two, like u4.
- if (@bitSizeOf(MaskIntType) != @sizeOf(MaskIntType) * byte_size) {
- var desired_bits = @sizeOf(MaskIntType) * byte_size;
- desired_bits = std.math.ceilPowerOfTwoAssert(usize, desired_bits);
- const FixedMaskType = std.meta.Int(.unsigned, desired_bits);
- @compileError("ArrayBitSet was passed integer type " ++ @typeName(MaskIntType) ++
- ", which contains padding bits. Please round this up to an unpadded integer size (i.e. " ++ @typeName(FixedMaskType) ++ ").");
- }
-
- return extern struct {
- const Self = @This();
-
- // TODO: Make this a comptime field once those are fixed
- /// The number of items in this bit set
- pub const bit_length: usize = size;
-
- /// The integer type used to represent a mask in this bit set
- pub const MaskInt = MaskIntType;
-
- /// The integer type used to shift a mask in this bit set
- pub const ShiftInt = std.math.Log2Int(MaskInt);
-
- // bits in one mask
- const mask_len = @bitSizeOf(MaskInt);
- // total number of masks
- const num_masks = (size + mask_len - 1) / mask_len;
- // padding bits in the last mask (may be 0)
- const last_pad_bits = mask_len * num_masks - size;
- // Mask of valid bits in the last mask.
- // All functions will ensure that the invalid
- // bits in the last mask are zero.
- pub const last_item_mask = ~@as(MaskInt, 0) >> last_pad_bits;
-
- /// The bit masks, ordered with lower indices first.
- /// Padding bits at the end are undefined.
- masks: [num_masks]MaskInt,
-
- /// Creates a bit set with no elements present.
- pub fn initEmpty() Self {
- return .{ .masks = [_]MaskInt{0} ** num_masks };
- }
-
- /// Creates a bit set with all elements present.
- pub fn initFull() Self {
- if (num_masks == 0) {
- return .{ .masks = .{} };
- } else {
- return .{ .masks = [_]MaskInt{~@as(MaskInt, 0)} ** (num_masks - 1) ++ [_]MaskInt{last_item_mask} };
- }
- }
-
- /// Returns the number of bits in this bit set
- pub inline fn capacity(self: Self) usize {
- _ = self;
- return bit_length;
- }
-
- /// Returns true if the bit at the specified index
- /// is present in the set, false otherwise.
- pub fn isSet(self: *const Self, index: usize) bool {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (num_masks == 0) return false; // doesn't compile in this case
- return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
- }
-
- /// Returns the total number of set bits in this bit set.
- pub fn count(self: *const Self) usize {
- var total: usize = 0;
- for (self.masks) |mask| {
- total += @popCount(mask);
- }
- return total;
- }
-
- /// Changes the value of the specified bit of the bit
- /// set to match the passed boolean.
- pub fn setValue(self: *Self, index: usize, value: bool) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (num_masks == 0) return; // doesn't compile in this case
- const bit = maskBit(index);
- const mask_index = maskIndex(index);
- const new_bit = bit & std.math.boolMask(MaskInt, value);
- self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
- }
-
- /// Adds a specific bit to the bit set
- pub fn set(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (num_masks == 0) return; // doesn't compile in this case
- self.masks[maskIndex(index)] |= maskBit(index);
- }
-
- /// Changes the value of all bits in the specified range to
- /// match the passed boolean.
- pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
- if (comptime Environment.allow_assert) {
- std.debug.assert(range.end <= bit_length);
- std.debug.assert(range.start <= range.end);
- }
- if (range.start == range.end) return;
- if (num_masks == 0) return;
-
- const start_mask_index = maskIndex(range.start);
- const start_bit = @truncate(ShiftInt, range.start);
-
- const end_mask_index = maskIndex(range.end);
- const end_bit = @truncate(ShiftInt, range.end);
-
- if (start_mask_index == end_mask_index) {
- var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
- var mask2 = std.math.boolMask(MaskInt, true) >> (mask_len - 1) - (end_bit - 1);
- self.masks[start_mask_index] &= ~(mask1 & mask2);
-
- mask1 = std.math.boolMask(MaskInt, value) << start_bit;
- mask2 = std.math.boolMask(MaskInt, value) >> (mask_len - 1) - (end_bit - 1);
- self.masks[start_mask_index] |= mask1 & mask2;
- } else {
- var bulk_mask_index: usize = undefined;
- if (start_bit > 0) {
- self.masks[start_mask_index] =
- (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
- (std.math.boolMask(MaskInt, value) << start_bit);
- bulk_mask_index = start_mask_index + 1;
- } else {
- bulk_mask_index = start_mask_index;
- }
-
- while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
- self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
- }
-
- if (end_bit > 0) {
- self.masks[end_mask_index] =
- (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
- (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
- }
- }
- }
-
- /// Removes a specific bit from the bit set
- pub fn unset(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (num_masks == 0) return; // doesn't compile in this case
- self.masks[maskIndex(index)] &= ~maskBit(index);
- }
-
- /// Flips a specific bit in the bit set
- pub fn toggle(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < bit_length);
- if (num_masks == 0) return; // doesn't compile in this case
- self.masks[maskIndex(index)] ^= maskBit(index);
- }
-
- /// Flips all bits in this bit set which are present
- /// in the toggles bit set.
- pub fn toggleSet(self: *Self, toggles: *const Self) void {
- const other = &toggles.masks;
- for (&self.masks, 0..) |*mask, i| {
- mask.* ^= other[i];
- }
- }
-
- /// Flips every bit in the bit set.
- pub fn toggleAll(self: *Self) void {
- for (&self.masks) |*mask| {
- mask.* = ~mask.*;
- }
-
- // Zero the padding bits
- if (num_masks > 0) {
- self.masks[num_masks - 1] &= last_item_mask;
- }
- }
-
- /// Performs a union of two bit sets, and stores the
- /// result in the first one. Bits in the result are
- /// set if the corresponding bits were set in either input.
- pub fn setUnion(self: *Self, other: *const Self) void {
- for (&self.masks, 0..) |*mask, i| {
- mask.* |= other.masks[i];
- }
- }
-
- /// Performs an intersection of two bit sets, and stores
- /// the result in the first one. Bits in the result are
- /// set if the corresponding bits were set in both inputs.
- pub fn setIntersection(self: *Self, other: *const Self) void {
- for (&self.masks, 0..) |*mask, i| {
- mask.* &= other.masks[i];
- }
- }
-
- /// Finds the index of the first set bit.
- /// If no bits are set, returns null.
- pub fn findFirstSet(self: *const Self) ?usize {
- var offset: usize = 0;
- const mask = for (self.masks) |mask| {
- if (mask != 0) break mask;
- offset += @bitSizeOf(MaskInt);
- } else return null;
- return offset + @ctz(mask);
- }
-
- /// Finds the index of the first set bit, and unsets it.
- /// If no bits are set, returns null.
- pub fn toggleFirstSet(self: *Self) ?usize {
- var offset: usize = 0;
- const mask = for (&self.masks) |*mask| {
- if (mask.* != 0) break mask;
- offset += @bitSizeOf(MaskInt);
- } else return null;
- const index = @ctz(mask.*);
- mask.* &= (mask.* - 1);
- return offset + index;
- }
-
- /// Returns true iff every corresponding bit in both
- /// bit sets are the same.
- pub fn eql(self: *const Self, other: *const Self) bool {
- var i: usize = 0;
- return while (i < num_masks) : (i += 1) {
- if (self.masks[i] != other.masks[i]) {
- break false;
- }
- } else true;
- }
-
- /// Returns true iff the first bit set is the subset
- /// of the second one.
- pub fn subsetOf(self: *const Self, other: *const Self) bool {
- return self.intersectWith(other).eql(self);
- }
-
- /// Returns true iff the first bit set is the superset
- /// of the second one.
- pub fn supersetOf(self: *const Self, other: *const Self) bool {
- return other.subsetOf(self);
- }
-
- /// Returns the complement bit sets. Bits in the result
- /// are set if the corresponding bits were not set.
- pub fn complement(self: *const Self) Self {
- var result = self.*;
- result.toggleAll();
- return result;
- }
-
- /// Returns the union of two bit sets. Bits in the
- /// result are set if the corresponding bits were set
- /// in either input.
- pub fn unionWith(self: *const Self, other: *const Self) Self {
- var result = self.*;
- result.setUnion(other);
- return result;
- }
-
- /// Returns the intersection of two bit sets. Bits in
- /// the result are set if the corresponding bits were
- /// set in both inputs.
- pub fn intersectWith(self: *const Self, other: *const Self) Self {
- var result = self.*;
- result.setIntersection(other);
- return result;
- }
-
- /// Returns the xor of two bit sets. Bits in the
- /// result are set if the corresponding bits were
- /// not the same in both inputs.
- pub fn xorWith(self: *const Self, other: *const Self) Self {
- var result = self.*;
- result.toggleSet(other);
- return result;
- }
-
- /// Returns the difference of two bit sets. Bits in
- /// the result are set if set in the first but not
- /// set in the second set.
- pub fn differenceWith(self: *const Self, other: *const Self) Self {
- var result = self.*;
- result.setIntersection(&other.complement());
- return result;
- }
-
- /// Iterates through the items in the set, according to the options.
- /// The default options (.{}) will iterate indices of set bits in
- /// ascending order. Modifications to the underlying bit set may
- /// or may not be observed by the iterator.
- pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
- return Iterator(options).init(&self.masks, last_item_mask);
- }
-
- pub fn Iterator(comptime options: IteratorOptions) type {
- return BitSetIterator(MaskInt, options);
- }
-
- fn maskBit(index: usize) MaskInt {
- return @as(MaskInt, 1) << @truncate(ShiftInt, index);
- }
- fn maskIndex(index: usize) usize {
- return index >> @bitSizeOf(ShiftInt);
- }
- fn boolMaskBit(index: usize, value: bool) MaskInt {
- return @as(MaskInt, @boolToInt(value)) << @intCast(ShiftInt, index);
- }
- };
-}
-
-/// A bit set with runtime-known size, backed by an allocated slice
-/// of usize. The allocator must be tracked externally by the user.
-pub const DynamicBitSetUnmanaged = struct {
- const Self = @This();
-
- /// The integer type used to represent a mask in this bit set
- pub const MaskInt = usize;
-
- /// The integer type used to shift a mask in this bit set
- pub const ShiftInt = std.math.Log2Int(MaskInt);
-
- /// The number of valid items in this bit set
- bit_length: usize = 0,
-
- /// The bit masks, ordered with lower indices first.
- /// Padding bits at the end must be zeroed.
- masks: [*]MaskInt = empty_masks_ptr,
- // This pointer is one usize after the actual allocation.
- // That slot holds the size of the true allocation, which
- // is needed by Zig's allocator interface in case a shrink
- // fails.
-
- // Don't modify this value. Ideally it would go in const data so
- // modifications would cause a bus error, but the only way
- // to discard a const qualifier is through ptrToInt, which
- // cannot currently round trip at comptime.
- var empty_masks_data = [_]MaskInt{ 0, undefined };
- const empty_masks_ptr = empty_masks_data[1..2];
-
- /// Creates a bit set with no elements present.
- /// If bit_length is not zero, deinit must eventually be called.
- pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
- var self = Self{};
- try self.resize(allocator, bit_length, false);
- return self;
- }
-
- /// Creates a bit set with all elements present.
- /// If bit_length is not zero, deinit must eventually be called.
- pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
- var self = Self{};
- try self.resize(allocator, bit_length, true);
- return self;
- }
-
- /// Resizes to a new bit_length. If the new length is larger
- /// than the old length, fills any added bits with `fill`.
- /// If new_len is not zero, deinit must eventually be called.
- pub fn resize(self: *@This(), allocator: Allocator, new_len: usize, fill: bool) !void {
- const old_len = self.bit_length;
-
- const old_masks = numMasks(old_len);
- const new_masks = numMasks(new_len);
-
- const old_allocation = (self.masks - 1)[0..(self.masks - 1)[0]];
-
- if (new_masks == 0) {
- if (comptime Environment.allow_assert) std.debug.assert(new_len == 0);
- allocator.free(old_allocation);
- self.masks = empty_masks_ptr;
- self.bit_length = 0;
- return;
- }
-
- if (old_allocation.len != new_masks + 1) realloc: {
- // If realloc fails, it may mean one of two things.
- // If we are growing, it means we are out of memory.
- // If we are shrinking, it means the allocator doesn't
- // want to move the allocation. This means we need to
- // hold on to the extra 8 bytes required to be able to free
- // this allocation properly.
- const new_allocation = allocator.realloc(old_allocation, new_masks + 1) catch |err| {
- if (new_masks + 1 > old_allocation.len) return err;
- break :realloc;
- };
-
- new_allocation[0] = new_allocation.len;
- self.masks = new_allocation.ptr + 1;
- }
-
- // If we increased in size, we need to set any new bits
- // to the fill value.
- if (new_len > old_len) {
- // set the padding bits in the old last item to 1
- if (fill and old_masks > 0) {
- const old_padding_bits = old_masks * @bitSizeOf(MaskInt) - old_len;
- const old_mask = (~@as(MaskInt, 0)) >> @intCast(ShiftInt, old_padding_bits);
- self.masks[old_masks - 1] |= ~old_mask;
- }
-
- // fill in any new masks
- if (new_masks > old_masks) {
- const fill_value = std.math.boolMask(MaskInt, fill);
- std.mem.set(MaskInt, self.masks[old_masks..new_masks], fill_value);
- }
- }
-
- // Zero out the padding bits
- if (new_len > 0) {
- const padding_bits = new_masks * @bitSizeOf(MaskInt) - new_len;
- const last_item_mask = (~@as(MaskInt, 0)) >> @intCast(ShiftInt, padding_bits);
- self.masks[new_masks - 1] &= last_item_mask;
- }
-
- // And finally, save the new length.
- self.bit_length = new_len;
- }
-
- /// deinitializes the array and releases its memory.
- /// The passed allocator must be the same one used for
- /// init* or resize in the past.
- pub fn deinit(self: *Self, allocator: Allocator) void {
- self.resize(allocator, 0, false) catch unreachable;
- }
-
- /// Creates a duplicate of this bit set, using the new allocator.
- pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
- const num_masks = numMasks(self.bit_length);
- var copy = Self{};
- try copy.resize(new_allocator, self.bit_length, false);
- bun.copy(MaskInt, copy.masks, self.masks[0..num_masks]);
- return copy;
- }
-
- /// Returns the number of bits in this bit set
- pub inline fn capacity(self: Self) usize {
- return self.bit_length;
- }
-
- /// Returns true if the bit at the specified index
- /// is present in the set, false otherwise.
- pub fn isSet(self: Self, index: usize) bool {
- if (comptime Environment.allow_assert) std.debug.assert(index < self.bit_length);
- return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
- }
-
- /// Returns the total number of set bits in this bit set.
- pub fn count(self: Self) usize {
- const num_masks = (self.bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
- var total: usize = 0;
- for (self.masks[0..num_masks]) |mask| {
- // Note: This is where we depend on padding bits being zero
- total += @popCount(mask);
- }
- return total;
- }
-
- /// Changes the value of the specified bit of the bit
- /// set to match the passed boolean.
- pub fn setValue(self: *Self, index: usize, value: bool) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < self.bit_length);
- const bit = maskBit(index);
- const mask_index = maskIndex(index);
- const new_bit = bit & std.math.boolMask(MaskInt, value);
- self.masks[mask_index] = (self.masks[mask_index] & ~bit) | new_bit;
- }
-
- /// Adds a specific bit to the bit set
- pub fn set(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < self.bit_length);
- self.masks[maskIndex(index)] |= maskBit(index);
- }
-
- /// Changes the value of all bits in the specified range to
- /// match the passed boolean.
- pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
- if (comptime Environment.allow_assert) std.debug.assert(range.end <= self.bit_length);
- if (comptime Environment.allow_assert) std.debug.assert(range.start <= range.end);
- if (range.start == range.end) return;
-
- const start_mask_index = maskIndex(range.start);
- const start_bit = @truncate(ShiftInt, range.start);
-
- const end_mask_index = maskIndex(range.end);
- const end_bit = @truncate(ShiftInt, range.end);
-
- if (start_mask_index == end_mask_index) {
- var mask1 = std.math.boolMask(MaskInt, true) << start_bit;
- var mask2 = std.math.boolMask(MaskInt, true) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
- self.masks[start_mask_index] &= ~(mask1 & mask2);
-
- mask1 = std.math.boolMask(MaskInt, value) << start_bit;
- mask2 = std.math.boolMask(MaskInt, value) >> (@bitSizeOf(MaskInt) - 1) - (end_bit - 1);
- self.masks[start_mask_index] |= mask1 & mask2;
- } else {
- var bulk_mask_index: usize = undefined;
- if (start_bit > 0) {
- self.masks[start_mask_index] =
- (self.masks[start_mask_index] & ~(std.math.boolMask(MaskInt, true) << start_bit)) |
- (std.math.boolMask(MaskInt, value) << start_bit);
- bulk_mask_index = start_mask_index + 1;
- } else {
- bulk_mask_index = start_mask_index;
- }
-
- while (bulk_mask_index < end_mask_index) : (bulk_mask_index += 1) {
- self.masks[bulk_mask_index] = std.math.boolMask(MaskInt, value);
- }
-
- if (end_bit > 0) {
- self.masks[end_mask_index] =
- (self.masks[end_mask_index] & (std.math.boolMask(MaskInt, true) << end_bit)) |
- (std.math.boolMask(MaskInt, value) >> ((@bitSizeOf(MaskInt) - 1) - (end_bit - 1)));
- }
- }
- }
-
- /// Removes a specific bit from the bit set
- pub fn unset(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < self.bit_length);
- self.masks[maskIndex(index)] &= ~maskBit(index);
- }
-
- /// Flips a specific bit in the bit set
- pub fn toggle(self: *Self, index: usize) void {
- if (comptime Environment.allow_assert) std.debug.assert(index < self.bit_length);
- self.masks[maskIndex(index)] ^= maskBit(index);
- }
-
- /// Flips all bits in this bit set which are present
- /// in the toggles bit set. Both sets must have the
- /// same bit_length.
- pub fn toggleSet(self: *Self, toggles: Self) void {
- if (comptime Environment.allow_assert) std.debug.assert(toggles.bit_length == self.bit_length);
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* ^= toggles.masks[i];
- }
- }
-
- /// Flips every bit in the bit set.
- pub fn toggleAll(self: *Self) void {
- const bit_length = self.bit_length;
- // avoid underflow if bit_length is zero
- if (bit_length == 0) return;
-
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks]) |*mask| {
- mask.* = ~mask.*;
- }
-
- const padding_bits = num_masks * @bitSizeOf(MaskInt) - bit_length;
- const last_item_mask = (~@as(MaskInt, 0)) >> @intCast(ShiftInt, padding_bits);
- self.masks[num_masks - 1] &= last_item_mask;
- }
-
- pub fn copyInto(self: *Self, other: Self) void {
- const bit_length = self.bit_length;
- // avoid underflow if bit_length is zero
- if (bit_length == 0) return;
-
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* = other.masks[i];
- }
-
- const padding_bits = num_masks * @bitSizeOf(MaskInt) - bit_length;
- const last_item_mask = (~@as(MaskInt, 0)) >> @intCast(ShiftInt, padding_bits);
- self.masks[num_masks - 1] &= last_item_mask;
- }
-
- /// Performs a union of two bit sets, and stores the
- /// result in the first one. Bits in the result are
- /// set if the corresponding bits were set in either input.
- /// The two sets must both be the same bit_length.
- pub fn setUnion(self: *Self, other: Self) void {
- if (comptime Environment.allow_assert) std.debug.assert(other.bit_length == self.bit_length);
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* |= other.masks[i];
- }
- }
-
- /// Performs an intersection of two bit sets, and stores
- /// the result in the first one. Bits in the result are
- /// set if the corresponding bits were set in both inputs.
- /// The two sets must both be the same bit_length.
- pub fn setIntersection(self: *Self, other: Self) void {
- if (comptime Environment.allow_assert) std.debug.assert(other.bit_length == self.bit_length);
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* &= other.masks[i];
- }
- }
-
- pub fn setExcludeTwo(self: *Self, other: Self, third: Self) void {
- if (comptime Environment.allow_assert) std.debug.assert(other.bit_length == self.bit_length);
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* &= ~other.masks[i];
- mask.* &= ~third.masks[i];
- }
- }
-
- pub fn setExclude(self: *Self, other: Self) void {
- if (comptime Environment.allow_assert) std.debug.assert(other.bit_length == self.bit_length);
- const num_masks = numMasks(self.bit_length);
- for (&self.masks[0..num_masks], 0..) |*mask, i| {
- mask.* &= ~other.masks[i];
- }
- }
-
- /// Finds the index of the first set bit.
- /// If no bits are set, returns null.
- pub fn findFirstSet(self: Self) ?usize {
- var offset: usize = 0;
- var mask = self.masks;
- while (offset < self.bit_length) {
- if (mask[0] != 0) break;
- mask += 1;
- offset += @bitSizeOf(MaskInt);
- } else return null;
- return offset + @ctz(mask[0]);
- }
-
- /// Finds the index of the first set bit, and unsets it.
- /// If no bits are set, returns null.
- pub fn toggleFirstSet(self: *Self) ?usize {
- var offset: usize = 0;
- var mask = self.masks;
- while (offset < self.bit_length) {
- if (mask[0] != 0) break;
- mask += 1;
- offset += @bitSizeOf(MaskInt);
- } else return null;
- const index = @ctz(mask[0]);
- mask[0] &= (mask[0] - 1);
- return offset + index;
- }
-
- /// Returns true iff every corresponding bit in both
- /// bit sets are the same.
- pub fn eql(self: Self, other: Self) bool {
- if (self.bit_length != other.bit_length) {
- return false;
- }
- const num_masks = numMasks(self.bit_length);
- var i: usize = 0;
- return while (i < num_masks) : (i += 1) {
- if (self.masks[i] != other.masks[i]) {
- break false;
- }
- } else true;
- }
-
- /// Returns true iff the first bit set is the subset
- /// of the second one.
- pub fn subsetOf(self: Self, other: Self) bool {
- if (self.bit_length != other.bit_length) {
- return false;
- }
- const num_masks = numMasks(self.bit_length);
- var i: usize = 0;
- return while (i < num_masks) : (i += 1) {
- if (self.masks[i] & other.masks[i] != self.masks[i]) {
- break false;
- }
- } else true;
- }
-
- /// Returns true iff the first bit set is the superset
- /// of the second one.
- pub fn supersetOf(self: Self, other: Self) bool {
- if (self.bit_length != other.bit_length) {
- return false;
- }
- const num_masks = numMasks(self.bit_length);
- var i: usize = 0;
- return while (i < num_masks) : (i += 1) {
- if (self.masks[i] & other.masks[i] != other.masks[i]) {
- break false;
- }
- } else true;
- }
-
- /// Iterates through the items in the set, according to the options.
- /// The default options (.{}) will iterate indices of set bits in
- /// ascending order. Modifications to the underlying bit set may
- /// or may not be observed by the iterator. Resizing the underlying
- /// bit set invalidates the iterator.
- pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
- const num_masks = numMasks(self.bit_length);
- const padding_bits = num_masks * @bitSizeOf(MaskInt) - self.bit_length;
- const last_item_mask = (~@as(MaskInt, 0)) >> @intCast(ShiftInt, padding_bits);
- return Iterator(options).init(self.masks[0..num_masks], last_item_mask);
- }
-
- pub fn Iterator(comptime options: IteratorOptions) type {
- return BitSetIterator(MaskInt, options);
- }
-
- fn maskBit(index: usize) MaskInt {
- return @as(MaskInt, 1) << @truncate(ShiftInt, index);
- }
- fn maskIndex(index: usize) usize {
- return index >> @bitSizeOf(ShiftInt);
- }
- fn boolMaskBit(index: usize, value: bool) MaskInt {
- return @as(MaskInt, @boolToInt(value)) << @intCast(ShiftInt, index);
- }
- fn numMasks(bit_length: usize) usize {
- return (bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
- }
-};
-
-/// A bit set with runtime-known size, backed by an allocated slice
-/// of usize. Thin wrapper around DynamicBitSetUnmanaged which keeps
-/// track of the allocator instance.
-pub const DynamicBitSet = struct {
- const Self = @This();
-
- /// The integer type used to represent a mask in this bit set
- pub const MaskInt = usize;
-
- /// The integer type used to shift a mask in this bit set
- pub const ShiftInt = std.math.Log2Int(MaskInt);
-
- /// The allocator used by this bit set
- allocator: Allocator,
-
- /// The number of valid items in this bit set
- unmanaged: DynamicBitSetUnmanaged = .{},
-
- /// Creates a bit set with no elements present.
- pub fn initEmpty(allocator: Allocator, bit_length: usize) !Self {
- return Self{
- .unmanaged = try DynamicBitSetUnmanaged.initEmpty(allocator, bit_length),
- .allocator = allocator,
- };
- }
-
- /// Creates a bit set with all elements present.
- pub fn initFull(allocator: Allocator, bit_length: usize) !Self {
- return Self{
- .unmanaged = try DynamicBitSetUnmanaged.initFull(allocator, bit_length),
- .allocator = allocator,
- };
- }
-
- /// Resizes to a new length. If the new length is larger
- /// than the old length, fills any added bits with `fill`.
- pub fn resize(self: *@This(), new_len: usize, fill: bool) !void {
- try self.unmanaged.resize(self.allocator, new_len, fill);
- }
-
- /// deinitializes the array and releases its memory.
- /// The passed allocator must be the same one used for
- /// init* or resize in the past.
- pub fn deinit(self: *Self) void {
- self.unmanaged.deinit(self.allocator);
- }
-
- /// Creates a duplicate of this bit set, using the new allocator.
- pub fn clone(self: *const Self, new_allocator: Allocator) !Self {
- return Self{
- .unmanaged = try self.unmanaged.clone(new_allocator),
- .allocator = new_allocator,
- };
- }
-
- /// Returns the number of bits in this bit set
- pub inline fn capacity(self: Self) usize {
- return self.unmanaged.capacity();
- }
-
- /// Returns true if the bit at the specified index
- /// is present in the set, false otherwise.
- pub fn isSet(self: Self, index: usize) bool {
- return self.unmanaged.isSet(index);
- }
-
- /// Returns the total number of set bits in this bit set.
- pub fn count(self: Self) usize {
- return self.unmanaged.count();
- }
-
- /// Changes the value of the specified bit of the bit
- /// set to match the passed boolean.
- pub fn setValue(self: *Self, index: usize, value: bool) void {
- self.unmanaged.setValue(index, value);
- }
-
- /// Adds a specific bit to the bit set
- pub fn set(self: *Self, index: usize) void {
- self.unmanaged.set(index);
- }
-
- /// Changes the value of all bits in the specified range to
- /// match the passed boolean.
- pub fn setRangeValue(self: *Self, range: Range, value: bool) void {
- self.unmanaged.setRangeValue(range, value);
- }
-
- /// Removes a specific bit from the bit set
- pub fn unset(self: *Self, index: usize) void {
- self.unmanaged.unset(index);
- }
-
- /// Flips a specific bit in the bit set
- pub fn toggle(self: *Self, index: usize) void {
- self.unmanaged.toggle(index);
- }
-
- /// Flips all bits in this bit set which are present
- /// in the toggles bit set. Both sets must have the
- /// same bit_length.
- pub fn toggleSet(self: *Self, toggles: Self) void {
- self.unmanaged.toggleSet(toggles.unmanaged);
- }
-
- /// Flips every bit in the bit set.
- pub fn toggleAll(self: *Self) void {
- self.unmanaged.toggleAll();
- }
-
- /// Performs a union of two bit sets, and stores the
- /// result in the first one. Bits in the result are
- /// set if the corresponding bits were set in either input.
- /// The two sets must both be the same bit_length.
- pub fn setUnion(self: *Self, other: Self) void {
- self.unmanaged.setUnion(other.unmanaged);
- }
-
- /// Performs an intersection of two bit sets, and stores
- /// the result in the first one. Bits in the result are
- /// set if the corresponding bits were set in both inputs.
- /// The two sets must both be the same bit_length.
- pub fn setIntersection(self: *Self, other: Self) void {
- self.unmanaged.setIntersection(other.unmanaged);
- }
-
- /// Finds the index of the first set bit.
- /// If no bits are set, returns null.
- pub fn findFirstSet(self: Self) ?usize {
- return self.unmanaged.findFirstSet();
- }
-
- /// Finds the index of the first set bit, and unsets it.
- /// If no bits are set, returns null.
- pub fn toggleFirstSet(self: *Self) ?usize {
- return self.unmanaged.toggleFirstSet();
- }
-
- /// Returns true iff every corresponding bit in both
- /// bit sets are the same.
- pub fn eql(self: Self, other: Self) bool {
- return self.unmanaged.eql(other.unmanaged);
- }
-
- /// Iterates through the items in the set, according to the options.
- /// The default options (.{}) will iterate indices of set bits in
- /// ascending order. Modifications to the underlying bit set may
- /// or may not be observed by the iterator. Resizing the underlying
- /// bit set invalidates the iterator.
- pub fn iterator(self: *const Self, comptime options: IteratorOptions) Iterator(options) {
- return self.unmanaged.iterator(options);
- }
-
- pub const Iterator = DynamicBitSetUnmanaged.Iterator;
-};
-
-/// Options for configuring an iterator over a bit set
-pub const IteratorOptions = struct {
- /// determines which bits should be visited
- kind: Type = .set,
- /// determines the order in which bit indices should be visited
- direction: Direction = .forward,
-
- pub const Type = enum {
- /// visit indexes of set bits
- set,
- /// visit indexes of unset bits
- unset,
- };
-
- pub const Direction = enum {
- /// visit indices in ascending order
- forward,
- /// visit indices in descending order.
- /// Note that this may be slightly more expensive than forward iteration.
- reverse,
- };
-};
-
-// The iterator is reusable between several bit set types
-fn BitSetIterator(comptime MaskInt: type, comptime options: IteratorOptions) type {
- const ShiftInt = std.math.Log2Int(MaskInt);
- const kind = options.kind;
- const direction = options.direction;
- return struct {
- const Self = @This();
-
- // all bits which have not yet been iterated over
- bits_remain: MaskInt,
- // all words which have not yet been iterated over
- words_remain: []const MaskInt,
- // the offset of the current word
- bit_offset: usize,
- // the mask of the last word
- last_word_mask: MaskInt,
-
- fn init(masks: []const MaskInt, last_word_mask: MaskInt) Self {
- if (masks.len == 0) {
- return Self{
- .bits_remain = 0,
- .words_remain = &[_]MaskInt{},
- .last_word_mask = last_word_mask,
- .bit_offset = 0,
- };
- } else {
- var result = Self{
- .bits_remain = 0,
- .words_remain = masks,
- .last_word_mask = last_word_mask,
- .bit_offset = if (direction == .forward) 0 else (masks.len - 1) * @bitSizeOf(MaskInt),
- };
- result.nextWord(true);
- return result;
- }
- }
-
- /// Returns the index of the next unvisited set bit
- /// in the bit set, in ascending order.
- pub fn next(self: *Self) ?usize {
- while (self.bits_remain == 0) {
- if (self.words_remain.len == 0) return null;
- self.nextWord(false);
- switch (direction) {
- .forward => self.bit_offset += @bitSizeOf(MaskInt),
- .reverse => self.bit_offset -= @bitSizeOf(MaskInt),
- }
- }
-
- switch (direction) {
- .forward => {
- const next_index = @ctz(self.bits_remain) + self.bit_offset;
- self.bits_remain &= self.bits_remain - 1;
- return next_index;
- },
- .reverse => {
- const leading_zeroes = @clz(self.bits_remain);
- const top_bit = (@bitSizeOf(MaskInt) - 1) - leading_zeroes;
- const no_top_bit_mask = (@as(MaskInt, 1) << @intCast(ShiftInt, top_bit)) - 1;
- self.bits_remain &= no_top_bit_mask;
- return top_bit + self.bit_offset;
- },
- }
- }
-
- // Load the next word. Don't call this if there
- // isn't a next word. If the next word is the
- // last word, mask off the padding bits so we
- // don't visit them.
- inline fn nextWord(self: *Self, comptime is_first_word: bool) void {
- var word = switch (direction) {
- .forward => self.words_remain[0],
- .reverse => self.words_remain[self.words_remain.len - 1],
- };
- switch (kind) {
- .set => {},
- .unset => {
- word = ~word;
- if ((direction == .reverse and is_first_word) or
- (direction == .forward and self.words_remain.len == 1))
- {
- word &= self.last_word_mask;
- }
- },
- }
- switch (direction) {
- .forward => self.words_remain = self.words_remain[1..],
- .reverse => self.words_remain.len -= 1,
- }
- self.bits_remain = word;
- }
- };
-}
-
-/// A range of indices within a bitset.
-pub const Range = struct {
- /// The index of the first bit of interest.
- start: usize,
- /// The index immediately after the last bit of interest.
- end: usize,
-};
-
-// ---------------- Tests -----------------
-
-const testing = std.testing;
-
-fn testEql(empty: anytype, full: anytype, len: usize) !void {
- try testing.expect(empty.eql(empty));
- try testing.expect(full.eql(full));
- switch (len) {
- 0 => {
- try testing.expect(empty.eql(full));
- try testing.expect(full.eql(empty));
- },
- else => {
- try testing.expect(!empty.eql(full));
- try testing.expect(!full.eql(empty));
- },
- }
-}
-
-fn testSubsetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
- try testing.expect(empty.subsetOf(empty));
- try testing.expect(empty.subsetOf(full));
- try testing.expect(full.subsetOf(full));
- switch (len) {
- 0 => {
- try testing.expect(even.subsetOf(odd));
- try testing.expect(odd.subsetOf(even));
- },
- 1 => {
- try testing.expect(!even.subsetOf(odd));
- try testing.expect(odd.subsetOf(even));
- },
- else => {
- try testing.expect(!even.subsetOf(odd));
- try testing.expect(!odd.subsetOf(even));
- },
- }
-}
-
-fn testSupersetOf(empty: anytype, full: anytype, even: anytype, odd: anytype, len: usize) !void {
- try testing.expect(full.supersetOf(full));
- try testing.expect(full.supersetOf(empty));
- try testing.expect(empty.supersetOf(empty));
- switch (len) {
- 0 => {
- try testing.expect(even.supersetOf(odd));
- try testing.expect(odd.supersetOf(even));
- },
- 1 => {
- try testing.expect(even.supersetOf(odd));
- try testing.expect(!odd.supersetOf(even));
- },
- else => {
- try testing.expect(!even.supersetOf(odd));
- try testing.expect(!odd.supersetOf(even));
- },
- }
-}
-
-fn testBitSet(a: anytype, b: anytype, len: usize) !void {
- try testing.expectEqual(len, a.capacity());
- try testing.expectEqual(len, b.capacity());
- const needs_ptr = @hasField(std.meta.Child(@TypeOf(a)), "masks") and @typeInfo(@TypeOf(@field(a, "masks"))) != .Pointer;
-
- {
- var i: usize = 0;
- while (i < len) : (i += 1) {
- a.setValue(i, i & 1 == 0);
- b.setValue(i, i & 2 == 0);
- }
- }
-
- try testing.expectEqual((len + 1) / 2, a.count());
- try testing.expectEqual((len + 3) / 4 + (len + 2) / 4, b.count());
-
- {
- var iter = a.iterator(.{});
- var i: usize = 0;
- while (i < len) : (i += 2) {
- try testing.expectEqual(@as(?usize, i), iter.next());
- }
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- }
- a.toggleAll();
- {
- var iter = a.iterator(.{});
- var i: usize = 1;
- while (i < len) : (i += 2) {
- try testing.expectEqual(@as(?usize, i), iter.next());
- }
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- }
-
- {
- var iter = b.iterator(.{ .kind = .unset });
- var i: usize = 2;
- while (i < len) : (i += 4) {
- try testing.expectEqual(@as(?usize, i), iter.next());
- if (i + 1 < len) {
- try testing.expectEqual(@as(?usize, i + 1), iter.next());
- }
- }
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- }
-
- {
- var i: usize = 0;
- while (i < len) : (i += 1) {
- try testing.expectEqual(i & 1 != 0, a.isSet(i));
- try testing.expectEqual(i & 2 == 0, b.isSet(i));
- }
- }
-
- if (comptime needs_ptr) {
- a.setUnion(b);
- } else {
- a.setUnion(b.*);
- }
-
- {
- var i: usize = 0;
- while (i < len) : (i += 1) {
- try testing.expectEqual(i & 1 != 0 or i & 2 == 0, a.isSet(i));
- try testing.expectEqual(i & 2 == 0, b.isSet(i));
- }
-
- i = len;
- var set = a.iterator(.{ .direction = .reverse });
- var unset = a.iterator(.{ .kind = .unset, .direction = .reverse });
- while (i > 0) {
- i -= 1;
- if (i & 1 != 0 or i & 2 == 0) {
- try testing.expectEqual(@as(?usize, i), set.next());
- } else {
- try testing.expectEqual(@as(?usize, i), unset.next());
- }
- }
- try testing.expectEqual(@as(?usize, null), set.next());
- try testing.expectEqual(@as(?usize, null), set.next());
- try testing.expectEqual(@as(?usize, null), set.next());
- try testing.expectEqual(@as(?usize, null), unset.next());
- try testing.expectEqual(@as(?usize, null), unset.next());
- try testing.expectEqual(@as(?usize, null), unset.next());
- }
-
- if (comptime needs_ptr) {
- a.toggleSet(b);
- } else {
- a.toggleSet(b.*);
- }
- {
- try testing.expectEqual(len / 4, a.count());
-
- var i: usize = 0;
- while (i < len) : (i += 1) {
- try testing.expectEqual(i & 1 != 0 and i & 2 != 0, a.isSet(i));
- try testing.expectEqual(i & 2 == 0, b.isSet(i));
- if (i & 1 == 0) {
- a.set(i);
- } else {
- a.unset(i);
- }
- }
- }
-
- if (comptime needs_ptr) {
- a.setIntersection(b);
- } else {
- a.setIntersection(b.*);
- }
- {
- try testing.expectEqual((len + 3) / 4, a.count());
-
- var i: usize = 0;
- while (i < len) : (i += 1) {
- try testing.expectEqual(i & 1 == 0 and i & 2 == 0, a.isSet(i));
- try testing.expectEqual(i & 2 == 0, b.isSet(i));
- }
- }
-
- if (comptime needs_ptr) {
- a.toggleSet(a);
- } else {
- a.toggleSet(a.*);
- }
- {
- var iter = a.iterator(.{});
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(usize, 0), a.count());
- }
- {
- var iter = a.iterator(.{ .direction = .reverse });
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(?usize, null), iter.next());
- try testing.expectEqual(@as(usize, 0), a.count());
- }
-
- const test_bits = [_]usize{
- 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 22, 31, 32, 63, 64,
- 66, 95, 127, 160, 192, 1000,
- };
- for (test_bits) |i| {
- if (i < a.capacity()) {
- a.set(i);
- }
- }
-
- for (test_bits) |i| {
- if (i < a.capacity()) {
- try testing.expectEqual(@as(?usize, i), a.findFirstSet());
- try testing.expectEqual(@as(?usize, i), a.toggleFirstSet());
- }
- }
- try testing.expectEqual(@as(?usize, null), a.findFirstSet());
- try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
- try testing.expectEqual(@as(?usize, null), a.findFirstSet());
- try testing.expectEqual(@as(?usize, null), a.toggleFirstSet());
- try testing.expectEqual(@as(usize, 0), a.count());
-
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- try testing.expectEqual(@as(usize, 0), a.count());
-
- a.setRangeValue(.{ .start = 0, .end = len }, true);
- try testing.expectEqual(len, a.count());
-
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = 0, .end = 0 }, true);
- try testing.expectEqual(@as(usize, 0), a.count());
-
- a.setRangeValue(.{ .start = len, .end = len }, true);
- try testing.expectEqual(@as(usize, 0), a.count());
-
- if (len >= 1) {
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = 0, .end = 1 }, true);
- try testing.expectEqual(@as(usize, 1), a.count());
- try testing.expect(a.isSet(0));
-
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = 0, .end = len - 1 }, true);
- try testing.expectEqual(len - 1, a.count());
- try testing.expect(!a.isSet(len - 1));
-
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = 1, .end = len }, true);
- try testing.expectEqual(@as(usize, len - 1), a.count());
- try testing.expect(!a.isSet(0));
-
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = len - 1, .end = len }, true);
- try testing.expectEqual(@as(usize, 1), a.count());
- try testing.expect(a.isSet(len - 1));
-
- if (len >= 4) {
- a.setRangeValue(.{ .start = 0, .end = len }, false);
- a.setRangeValue(.{ .start = 1, .end = len - 2 }, true);
- try testing.expectEqual(@as(usize, len - 3), a.count());
- try testing.expect(!a.isSet(0));
- try testing.expect(a.isSet(1));
- try testing.expect(a.isSet(len - 3));
- try testing.expect(!a.isSet(len - 2));
- try testing.expect(!a.isSet(len - 1));
- }
- }
-}
-
-fn fillEven(set: anytype, len: usize) void {
- var i: usize = 0;
- while (i < len) : (i += 1) {
- set.setValue(i, i & 1 == 0);
- }
-}
-
-fn fillOdd(set: anytype, len: usize) void {
- var i: usize = 0;
- while (i < len) : (i += 1) {
- set.setValue(i, i & 1 == 1);
- }
-}
-
-fn testPureBitSet(comptime Set: type) !void {
- var empty_ = Set.initEmpty();
- var full_ = Set.initFull();
- const needs_ptr = @hasField(Set, "masks") and @typeInfo(@TypeOf(empty_.masks)) != .Pointer;
-
- var even_ = even: {
- var bit_set = Set.initEmpty();
- fillEven(&bit_set, Set.bit_length);
- break :even bit_set;
- };
-
- var odd_ = odd: {
- var bit_set = Set.initEmpty();
- fillOdd(&bit_set, Set.bit_length);
- break :odd bit_set;
- };
-
- var empty = if (needs_ptr) &empty_ else empty_;
- var full = if (needs_ptr) &full_ else full_;
- var even = if (needs_ptr) &even_ else even_;
- var odd = if (needs_ptr) &odd_ else odd_;
-
- try testSubsetOf(empty, full, even, odd, Set.bit_length);
- try testSupersetOf(empty, full, even, odd, Set.bit_length);
-
- try testing.expect(empty.complement().eql(full));
- try testing.expect(full.complement().eql(empty));
- try testing.expect(even.complement().eql(odd));
- try testing.expect(odd.complement().eql(even));
-
- try testing.expect(empty.unionWith(empty).eql(empty));
- try testing.expect(empty.unionWith(full).eql(full));
- try testing.expect(full.unionWith(full).eql(full));
- try testing.expect(full.unionWith(empty).eql(full));
- try testing.expect(even.unionWith(odd).eql(full));
- try testing.expect(odd.unionWith(even).eql(full));
-
- try testing.expect(empty.intersectWith(empty).eql(empty));
- try testing.expect(empty.intersectWith(full).eql(empty));
- try testing.expect(full.intersectWith(full).eql(full));
- try testing.expect(full.intersectWith(empty).eql(empty));
- try testing.expect(even.intersectWith(odd).eql(empty));
- try testing.expect(odd.intersectWith(even).eql(empty));
-
- try testing.expect(empty.xorWith(empty).eql(empty));
- try testing.expect(empty.xorWith(full).eql(full));
- try testing.expect(full.xorWith(full).eql(empty));
- try testing.expect(full.xorWith(empty).eql(full));
- try testing.expect(even.xorWith(odd).eql(full));
- try testing.expect(odd.xorWith(even).eql(full));
-
- try testing.expect(empty.differenceWith(empty).eql(empty));
- try testing.expect(empty.differenceWith(full).eql(empty));
- try testing.expect(full.differenceWith(full).eql(empty));
- try testing.expect(full.differenceWith(empty).eql(full));
- try testing.expect(full.differenceWith(odd).eql(even));
- try testing.expect(full.differenceWith(even).eql(odd));
-}
-
-fn testStaticBitSet(comptime Set: type, comptime Container: @Type(.EnumLiteral)) !void {
- var a = Set.initEmpty();
- var b = Set.initFull();
- try testing.expectEqual(@as(usize, 0), a.count());
- try testing.expectEqual(@as(usize, Set.bit_length), b.count());
-
- if (comptime Container == .ArrayBitSet) {
- try testEql(&a, &b, Set.bit_length);
- } else {
- try testEql(a, b, Set.bit_length);
- }
-
- try testBitSet(&a, &b, Set.bit_length);
-
- try testPureBitSet(Set);
-}
-
-test "IntegerBitSet" {
- try testStaticBitSet(IntegerBitSet(0), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(1), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(2), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(5), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(8), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(32), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(64), .IntegerBitSet);
- try testStaticBitSet(IntegerBitSet(127), .IntegerBitSet);
-}
-
-test "ArrayBitSet" {
- inline for (.{ 0, 1, 2, 31, 32, 33, 63, 64, 65, 254, 500, 3000 }) |size| {
- try testStaticBitSet(ArrayBitSet(u8, size), .ArrayBitSet);
- try testStaticBitSet(ArrayBitSet(u16, size), .ArrayBitSet);
- try testStaticBitSet(ArrayBitSet(u32, size), .ArrayBitSet);
- try testStaticBitSet(ArrayBitSet(u64, size), .ArrayBitSet);
- try testStaticBitSet(ArrayBitSet(u128, size), .ArrayBitSet);
- }
-}
-
-test "DynamicBitSetUnmanaged" {
- const allocator = std.testing.allocator;
- var a = try DynamicBitSetUnmanaged.initEmpty(allocator, 300);
- try testing.expectEqual(@as(usize, 0), a.count());
- a.deinit(allocator);
-
- a = try DynamicBitSetUnmanaged.initEmpty(allocator, 0);
- defer a.deinit(allocator);
- for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
- const old_len = a.capacity();
-
- var empty = try a.clone(allocator);
- defer empty.deinit(allocator);
- try testing.expectEqual(old_len, empty.capacity());
- var i: usize = 0;
- while (i < old_len) : (i += 1) {
- try testing.expectEqual(a.isSet(i), empty.isSet(i));
- }
-
- a.toggleSet(a); // zero a
- empty.toggleSet(empty);
-
- try a.resize(allocator, size, true);
- try empty.resize(allocator, size, false);
-
- if (size > old_len) {
- try testing.expectEqual(size - old_len, a.count());
- } else {
- try testing.expectEqual(@as(usize, 0), a.count());
- }
- try testing.expectEqual(@as(usize, 0), empty.count());
-
- var full = try DynamicBitSetUnmanaged.initFull(allocator, size);
- defer full.deinit(allocator);
- try testing.expectEqual(@as(usize, size), full.count());
-
- try testEql(empty, full, size);
- {
- var even = try DynamicBitSetUnmanaged.initEmpty(allocator, size);
- defer even.deinit(allocator);
- fillEven(&even, size);
-
- var odd = try DynamicBitSetUnmanaged.initEmpty(allocator, size);
- defer odd.deinit(allocator);
- fillOdd(&odd, size);
-
- try testSubsetOf(empty, full, even, odd, size);
- try testSupersetOf(empty, full, even, odd, size);
- }
- try testBitSet(&a, &full, size);
- }
-}
-
-test "DynamicBitSet" {
- const allocator = std.testing.allocator;
- var a = try DynamicBitSet.initEmpty(allocator, 300);
- try testing.expectEqual(@as(usize, 0), a.count());
- a.deinit();
-
- a = try DynamicBitSet.initEmpty(allocator, 0);
- defer a.deinit();
- for ([_]usize{ 1, 2, 31, 32, 33, 0, 65, 64, 63, 500, 254, 3000 }) |size| {
- const old_len = a.capacity();
-
- var tmp = try a.clone(allocator);
- defer tmp.deinit();
- try testing.expectEqual(old_len, tmp.capacity());
- var i: usize = 0;
- while (i < old_len) : (i += 1) {
- try testing.expectEqual(a.isSet(i), tmp.isSet(i));
- }
-
- a.toggleSet(a); // zero a
- tmp.toggleSet(tmp); // zero tmp
-
- try a.resize(size, true);
- try tmp.resize(size, false);
-
- if (size > old_len) {
- try testing.expectEqual(size - old_len, a.count());
- } else {
- try testing.expectEqual(@as(usize, 0), a.count());
- }
- try testing.expectEqual(@as(usize, 0), tmp.count());
-
- var b = try DynamicBitSet.initFull(allocator, size);
- defer b.deinit();
- try testing.expectEqual(@as(usize, size), b.count());
-
- try testEql(tmp, b, size);
- try testBitSet(&a, &b, size);
- }
-}
-
-test "StaticBitSet" {
- try testing.expectEqual(IntegerBitSet(0), StaticBitSet(0));
- try testing.expectEqual(IntegerBitSet(5), StaticBitSet(5));
- try testing.expectEqual(IntegerBitSet(@bitSizeOf(usize)), StaticBitSet(@bitSizeOf(usize)));
- try testing.expectEqual(ArrayBitSet(usize, @bitSizeOf(usize) + 1), StaticBitSet(@bitSizeOf(usize) + 1));
- try testing.expectEqual(ArrayBitSet(usize, 500), StaticBitSet(500));
-}
diff --git a/src/install/install.zig b/src/install/install.zig
index 69a39fd7a..0ae273f79 100644
--- a/src/install/install.zig
+++ b/src/install/install.zig
@@ -44,7 +44,7 @@ const Integrity = @import("./integrity.zig").Integrity;
const clap = bun.clap;
const ExtractTarball = @import("./extract_tarball.zig");
const Npm = @import("./npm.zig");
-const Bitset = @import("./bit_set.zig").DynamicBitSetUnmanaged;
+const Bitset = bun.bit_set.DynamicBitSetUnmanaged;
const z_allocator = @import("../memory_allocator.zig").z_allocator;
const Syscall = bun.JSC.Node.Syscall;
const RunCommand = @import("../cli/run_command.zig").RunCommand;
diff --git a/src/install/lockfile.zig b/src/install/lockfile.zig
index b2997899f..93cd15fb2 100644
--- a/src/install/lockfile.zig
+++ b/src/install/lockfile.zig
@@ -46,7 +46,7 @@ const Integrity = @import("./integrity.zig").Integrity;
const clap = bun.clap;
const ExtractTarball = @import("./extract_tarball.zig");
const Npm = @import("./npm.zig");
-const Bitset = @import("./bit_set.zig").DynamicBitSetUnmanaged;
+const Bitset = bun.bit_set.DynamicBitSetUnmanaged;
const z_allocator = @import("../memory_allocator.zig").z_allocator;
const Lockfile = @This();
diff --git a/src/install/semver.zig b/src/install/semver.zig
index e96b1cddc..928fb9227 100644
--- a/src/install/semver.zig
+++ b/src/install/semver.zig
@@ -96,7 +96,7 @@ pub const String = extern struct {
lhs_buf: []const u8,
rhs_buf: []const u8,
) std.math.Order {
- return std.mem.order(u8, lhs.slice(lhs_buf), rhs.slice(rhs_buf));
+ return strings.order(lhs.slice(lhs_buf), rhs.slice(rhs_buf));
}
pub inline fn canInline(buf: []const u8) bool {
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-28 22:26:51 +0000