Multiple overlap regions can cause an unbuildable builder

[danlehmann]

It is possible construct bitfields that have Builder without ever having a build() function.

See main...daniel/bugrepro for an example.

The build method at the end won't compile. It does compile however, if enable_bits: u5 is removed. So I'm assuming there is an issue with multiple overlap ranges (both u5 alias the 5 u1).

[estebank]

Just to clarify, in that case we should allow it. (The first sentence sounds like we also have an issue of ::builder() being available even when .build() won't ever be.)

[estebank]

This is caused due to set_params being built without accounting for multiple cases of fields being enabled or not. This will require combinational exhaustive search. PR shortly.

[danlehmann]

combinational exhaustive search

How slow could that get if there are multiple overlaps?

[estebank]

As I got it working now, it's not a factor of the number of overlaps but rather the number of fields. Compile times start taking a hit after 20 fields. After 23 it finishes in a few seconds but beyond that it starts to become prohibitively slow. I can make it so that the exhaustive eval is only done if we've already determined that there's any overlap, but that's not great.

I'll try to come up with a more opportunistic approach (keep track of overlaps suitable for linear scan). I made a worst case scenario test (128 bools + 64 u2 + 32 u4 + 16 u8 + 8 u16 + 4 u32 + 2 u64 fields) that we can use to evaluate the alternatives.

Details

#[bitfield(u128, default = 0)] #[derive(PartialEq, Eq, Debug)] struct Foo
{
    #[bit(0, rw)] bool_field_0 : bool, #[bit(1, rw)] bool_field_1 : bool,
    #[bit(2, rw)] bool_field_2 : bool, #[bit(3, rw)] bool_field_3 : bool,
    #[bit(4, rw)] bool_field_4 : bool, #[bit(5, rw)] bool_field_5 : bool,
    #[bit(6, rw)] bool_field_6 : bool, #[bit(7, rw)] bool_field_7 : bool,
    #[bit(8, rw)] bool_field_8 : bool, #[bit(9, rw)] bool_field_9 : bool,
    #[bit(10, rw)] bool_field_10 : bool, #[bit(11, rw)] bool_field_11 : bool,
    #[bit(12, rw)] bool_field_12 : bool, #[bit(13, rw)] bool_field_13 : bool,
    #[bit(14, rw)] bool_field_14 : bool, #[bit(15, rw)] bool_field_15 : bool,
    #[bit(16, rw)] bool_field_16 : bool, #[bit(17, rw)] bool_field_17 : bool,
    #[bit(18, rw)] bool_field_18 : bool, #[bit(19, rw)] bool_field_19 : bool,
    #[bit(20, rw)] bool_field_20 : bool, #[bit(21, rw)] bool_field_21 : bool,
    #[bit(22, rw)] bool_field_22 : bool, #[bit(23, rw)] bool_field_23 : bool,
    #[bit(24, rw)] bool_field_24 : bool, #[bit(25, rw)] bool_field_25 : bool,
    #[bit(26, rw)] bool_field_26 : bool, #[bit(27, rw)] bool_field_27 : bool,
    #[bit(28, rw)] bool_field_28 : bool, #[bit(29, rw)] bool_field_29 : bool,
    #[bit(30, rw)] bool_field_30 : bool, #[bit(31, rw)] bool_field_31 : bool,
    #[bit(32, rw)] bool_field_32 : bool, #[bit(33, rw)] bool_field_33 : bool,
    #[bit(34, rw)] bool_field_34 : bool, #[bit(35, rw)] bool_field_35 : bool,
    #[bit(36, rw)] bool_field_36 : bool, #[bit(37, rw)] bool_field_37 : bool,
    #[bit(38, rw)] bool_field_38 : bool, #[bit(39, rw)] bool_field_39 : bool,
    #[bit(40, rw)] bool_field_40 : bool, #[bit(41, rw)] bool_field_41 : bool,
    #[bit(42, rw)] bool_field_42 : bool, #[bit(43, rw)] bool_field_43 : bool,
    #[bit(44, rw)] bool_field_44 : bool, #[bit(45, rw)] bool_field_45 : bool,
    #[bit(46, rw)] bool_field_46 : bool, #[bit(47, rw)] bool_field_47 : bool,
    #[bit(48, rw)] bool_field_48 : bool, #[bit(49, rw)] bool_field_49 : bool,
    #[bit(50, rw)] bool_field_50 : bool, #[bit(51, rw)] bool_field_51 : bool,
    #[bit(52, rw)] bool_field_52 : bool, #[bit(53, rw)] bool_field_53 : bool,
    #[bit(54, rw)] bool_field_54 : bool, #[bit(55, rw)] bool_field_55 : bool,
    #[bit(56, rw)] bool_field_56 : bool, #[bit(57, rw)] bool_field_57 : bool,
    #[bit(58, rw)] bool_field_58 : bool, #[bit(59, rw)] bool_field_59 : bool,
    #[bit(60, rw)] bool_field_60 : bool, #[bit(61, rw)] bool_field_61 : bool,
    #[bit(62, rw)] bool_field_62 : bool, #[bit(63, rw)] bool_field_63 : bool,
    #[bit(64, rw)] bool_field_64 : bool, #[bit(65, rw)] bool_field_65 : bool,
    #[bit(66, rw)] bool_field_66 : bool, #[bit(67, rw)] bool_field_67 : bool,
    #[bit(68, rw)] bool_field_68 : bool, #[bit(69, rw)] bool_field_69 : bool,
    #[bit(70, rw)] bool_field_70 : bool, #[bit(71, rw)] bool_field_71 : bool,
    #[bit(72, rw)] bool_field_72 : bool, #[bit(73, rw)] bool_field_73 : bool,
    #[bit(74, rw)] bool_field_74 : bool, #[bit(75, rw)] bool_field_75 : bool,
    #[bit(76, rw)] bool_field_76 : bool, #[bit(77, rw)] bool_field_77 : bool,
    #[bit(78, rw)] bool_field_78 : bool, #[bit(79, rw)] bool_field_79 : bool,
    #[bit(80, rw)] bool_field_80 : bool, #[bit(81, rw)] bool_field_81 : bool,
    #[bit(82, rw)] bool_field_82 : bool, #[bit(83, rw)] bool_field_83 : bool,
    #[bit(84, rw)] bool_field_84 : bool, #[bit(85, rw)] bool_field_85 : bool,
    #[bit(86, rw)] bool_field_86 : bool, #[bit(87, rw)] bool_field_87 : bool,
    #[bit(88, rw)] bool_field_88 : bool, #[bit(89, rw)] bool_field_89 : bool,
    #[bit(90, rw)] bool_field_90 : bool, #[bit(91, rw)] bool_field_91 : bool,
    #[bit(92, rw)] bool_field_92 : bool, #[bit(93, rw)] bool_field_93 : bool,
    #[bit(94, rw)] bool_field_94 : bool, #[bit(95, rw)] bool_field_95 : bool,
    #[bit(96, rw)] bool_field_96 : bool, #[bit(97, rw)] bool_field_97 : bool,
    #[bit(98, rw)] bool_field_98 : bool, #[bit(99, rw)] bool_field_99 : bool,
    #[bit(100, rw)] bool_field_100 : bool, #[bit(101, rw)] bool_field_101 :
    bool, #[bit(102, rw)] bool_field_102 : bool, #[bit(103, rw)]
    bool_field_103 : bool, #[bit(104, rw)] bool_field_104 : bool,
    #[bit(105, rw)] bool_field_105 : bool, #[bit(106, rw)] bool_field_106 :
    bool, #[bit(107, rw)] bool_field_107 : bool, #[bit(108, rw)]
    bool_field_108 : bool, #[bit(109, rw)] bool_field_109 : bool,
    #[bit(110, rw)] bool_field_110 : bool, #[bit(111, rw)] bool_field_111 :
    bool, #[bit(112, rw)] bool_field_112 : bool, #[bit(113, rw)]
    bool_field_113 : bool, #[bit(114, rw)] bool_field_114 : bool,
    #[bit(115, rw)] bool_field_115 : bool, #[bit(116, rw)] bool_field_116 :
    bool, #[bit(117, rw)] bool_field_117 : bool, #[bit(118, rw)]
    bool_field_118 : bool, #[bit(119, rw)] bool_field_119 : bool,
    #[bit(120, rw)] bool_field_120 : bool, #[bit(121, rw)] bool_field_121 :
    bool, #[bit(122, rw)] bool_field_122 : bool, #[bit(123, rw)]
    bool_field_123 : bool, #[bit(124, rw)] bool_field_124 : bool,
    #[bit(125, rw)] bool_field_125 : bool, #[bit(126, rw)] bool_field_126 :
    bool, #[bit(127, rw)] bool_field_127 : bool, #[bits(0 ..= 1, rw)]
    u2_field_0 : u2, #[bits(2 ..= 3, rw)] u2_field_1 : u2,
    #[bits(4 ..= 5, rw)] u2_field_2 : u2, #[bits(6 ..= 7, rw)] u2_field_3 :
    u2, #[bits(8 ..= 9, rw)] u2_field_4 : u2, #[bits(10 ..= 11, rw)]
    u2_field_5 : u2, #[bits(12 ..= 13, rw)] u2_field_6 : u2,
    #[bits(14 ..= 15, rw)] u2_field_7 : u2, #[bits(16 ..= 17, rw)] u2_field_8
    : u2, #[bits(18 ..= 19, rw)] u2_field_9 : u2, #[bits(20 ..= 21, rw)]
    u2_field_10 : u2, #[bits(22 ..= 23, rw)] u2_field_11 : u2,
    #[bits(24 ..= 25, rw)] u2_field_12 : u2, #[bits(26 ..= 27, rw)]
    u2_field_13 : u2, #[bits(28 ..= 29, rw)] u2_field_14 : u2,
    #[bits(30 ..= 31, rw)] u2_field_15 : u2, #[bits(32 ..= 33, rw)]
    u2_field_16 : u2, #[bits(34 ..= 35, rw)] u2_field_17 : u2,
    #[bits(36 ..= 37, rw)] u2_field_18 : u2, #[bits(38 ..= 39, rw)]
    u2_field_19 : u2, #[bits(40 ..= 41, rw)] u2_field_20 : u2,
    #[bits(42 ..= 43, rw)] u2_field_21 : u2, #[bits(44 ..= 45, rw)]
    u2_field_22 : u2, #[bits(46 ..= 47, rw)] u2_field_23 : u2,
    #[bits(48 ..= 49, rw)] u2_field_24 : u2, #[bits(50 ..= 51, rw)]
    u2_field_25 : u2, #[bits(52 ..= 53, rw)] u2_field_26 : u2,
    #[bits(54 ..= 55, rw)] u2_field_27 : u2, #[bits(56 ..= 57, rw)]
    u2_field_28 : u2, #[bits(58 ..= 59, rw)] u2_field_29 : u2,
    #[bits(60 ..= 61, rw)] u2_field_30 : u2, #[bits(62 ..= 63, rw)]
    u2_field_31 : u2, #[bits(64 ..= 65, rw)] u2_field_32 : u2,
    #[bits(66 ..= 67, rw)] u2_field_33 : u2, #[bits(68 ..= 69, rw)]
    u2_field_34 : u2, #[bits(70 ..= 71, rw)] u2_field_35 : u2,
    #[bits(72 ..= 73, rw)] u2_field_36 : u2, #[bits(74 ..= 75, rw)]
    u2_field_37 : u2, #[bits(76 ..= 77, rw)] u2_field_38 : u2,
    #[bits(78 ..= 79, rw)] u2_field_39 : u2, #[bits(80 ..= 81, rw)]
    u2_field_40 : u2, #[bits(82 ..= 83, rw)] u2_field_41 : u2,
    #[bits(84 ..= 85, rw)] u2_field_42 : u2, #[bits(86 ..= 87, rw)]
    u2_field_43 : u2, #[bits(88 ..= 89, rw)] u2_field_44 : u2,
    #[bits(90 ..= 91, rw)] u2_field_45 : u2, #[bits(92 ..= 93, rw)]
    u2_field_46 : u2, #[bits(94 ..= 95, rw)] u2_field_47 : u2,
    #[bits(96 ..= 97, rw)] u2_field_48 : u2, #[bits(98 ..= 99, rw)]
    u2_field_49 : u2, #[bits(100 ..= 101, rw)] u2_field_50 : u2,
    #[bits(102 ..= 103, rw)] u2_field_51 : u2, #[bits(104 ..= 105, rw)]
    u2_field_52 : u2, #[bits(106 ..= 107, rw)] u2_field_53 : u2,
    #[bits(108 ..= 109, rw)] u2_field_54 : u2, #[bits(110 ..= 111, rw)]
    u2_field_55 : u2, #[bits(112 ..= 113, rw)] u2_field_56 : u2,
    #[bits(114 ..= 115, rw)] u2_field_57 : u2, #[bits(116 ..= 117, rw)]
    u2_field_58 : u2, #[bits(118 ..= 119, rw)] u2_field_59 : u2,
    #[bits(120 ..= 121, rw)] u2_field_60 : u2, #[bits(122 ..= 123, rw)]
    u2_field_61 : u2, #[bits(124 ..= 125, rw)] u2_field_62 : u2,
    #[bits(126 ..= 127, rw)] u2_field_63 : u2, #[bits(0 ..= 3, rw)] u4_field_0
    : u4, #[bits(4 ..= 7, rw)] u4_field_1 : u4, #[bits(8 ..= 11, rw)]
    u4_field_2 : u4, #[bits(12 ..= 15, rw)] u4_field_3 : u4,
    #[bits(16 ..= 19, rw)] u4_field_4 : u4, #[bits(20 ..= 23, rw)] u4_field_5
    : u4, #[bits(24 ..= 27, rw)] u4_field_6 : u4, #[bits(28 ..= 31, rw)]
    u4_field_7 : u4, #[bits(32 ..= 35, rw)] u4_field_8 : u4,
    #[bits(36 ..= 39, rw)] u4_field_9 : u4, #[bits(40 ..= 43, rw)] u4_field_10
    : u4, #[bits(44 ..= 47, rw)] u4_field_11 : u4, #[bits(48 ..= 51, rw)]
    u4_field_12 : u4, #[bits(52 ..= 55, rw)] u4_field_13 : u4,
    #[bits(56 ..= 59, rw)] u4_field_14 : u4, #[bits(60 ..= 63, rw)]
    u4_field_15 : u4, #[bits(64 ..= 67, rw)] u4_field_16 : u4,
    #[bits(68 ..= 71, rw)] u4_field_17 : u4, #[bits(72 ..= 75, rw)]
    u4_field_18 : u4, #[bits(76 ..= 79, rw)] u4_field_19 : u4,
    #[bits(80 ..= 83, rw)] u4_field_20 : u4, #[bits(84 ..= 87, rw)]
    u4_field_21 : u4, #[bits(88 ..= 91, rw)] u4_field_22 : u4,
    #[bits(92 ..= 95, rw)] u4_field_23 : u4, #[bits(96 ..= 99, rw)]
    u4_field_24 : u4, #[bits(100 ..= 103, rw)] u4_field_25 : u4,
    #[bits(104 ..= 107, rw)] u4_field_26 : u4, #[bits(108 ..= 111, rw)]
    u4_field_27 : u4, #[bits(112 ..= 115, rw)] u4_field_28 : u4,
    #[bits(116 ..= 119, rw)] u4_field_29 : u4, #[bits(120 ..= 123, rw)]
    u4_field_30 : u4, #[bits(124 ..= 127, rw)] u4_field_31 : u4,
    #[bits(0 ..= 7, rw)] u8_field_0 : u8, #[bits(8 ..= 15, rw)] u8_field_1 :
    u8, #[bits(16 ..= 23, rw)] u8_field_2 : u8, #[bits(24 ..= 31, rw)]
    u8_field_3 : u8, #[bits(32 ..= 39, rw)] u8_field_4 : u8,
    #[bits(40 ..= 47, rw)] u8_field_5 : u8, #[bits(48 ..= 55, rw)] u8_field_6
    : u8, #[bits(56 ..= 63, rw)] u8_field_7 : u8, #[bits(64 ..= 71, rw)]
    u8_field_8 : u8, #[bits(72 ..= 79, rw)] u8_field_9 : u8,
    #[bits(80 ..= 87, rw)] u8_field_10 : u8, #[bits(88 ..= 95, rw)]
    u8_field_11 : u8, #[bits(96 ..= 103, rw)] u8_field_12 : u8,
    #[bits(104 ..= 111, rw)] u8_field_13 : u8, #[bits(112 ..= 119, rw)]
    u8_field_14 : u8, #[bits(120 ..= 127, rw)] u8_field_15 : u8,
    #[bits(0 ..= 15, rw)] u16_field_0 : u16, #[bits(16 ..= 31, rw)]
    u16_field_1 : u16, #[bits(32 ..= 47, rw)] u16_field_2 : u16,
    #[bits(48 ..= 63, rw)] u16_field_3 : u16, #[bits(64 ..= 79, rw)]
    u16_field_4 : u16, #[bits(80 ..= 95, rw)] u16_field_5 : u16,
    #[bits(96 ..= 111, rw)] u16_field_6 : u16, #[bits(112 ..= 127, rw)]
    u16_field_7 : u16, #[bits(0 ..= 31, rw)] u32_field_0 : u32,
    #[bits(32 ..= 63, rw)] u32_field_1 : u32, #[bits(64 ..= 95, rw)]
    u32_field_2 : u32, #[bits(96 ..= 127, rw)] u32_field_3 : u32,
    #[bits(0 ..= 63, rw)] u64_field_0 : u64, #[bits(64 ..= 127, rw)]
    u64_field_1 : u64,
}

[danlehmann]

Would the old u128 mask approach solve this? Basically we'd collect all writable bits and how many bits have been written for a given combination. If not equal, no build() is offered. If there is no way to even get there in theory, no Builder() is offered

[estebank]

Yes. That approach would work (and could still be made to work with builders) but we would be losing in the output of calling .build() incorrectly: there's no way of actually seeing which subsets are allowed (you can turn the mask to binary output and manually figure things out, but suspect most won't be doing that). I can try out that change in approach, but would that be a breaking change in your eyes? (It'd be if anyone is referencing the Partial* types).

Edit: actually we won't be able to do that until #![feature(generic_const_exprs)] stabilizes, because we need to compute the mask after calling the setter from the prior mask state, and that isn't possible in stable today :-/

We can make it work only by generating impl blocks for every combination, which will significantly explode the generated code size.