Grcov report - block

1

#![forbid(unsafe_code)]

2

3

use std::fmt;

4

5

use itertools::Itertools;

6

7

use merc_collections::BlockIndex;

8

use merc_lts::IncomingTransitions;

9

use merc_lts::StateIndex;

10

11

use super::Partition;

12

13

/// A partition that explicitly stores a list of blocks and their indexing into

14

/// the list of elements.

15

#[derive(Debug)]

16

pub struct BlockPartition {

17

    elements: Vec<StateIndex>,

18

    blocks: Vec<Block>,

19

20

    // These are only used to provide O(1) marking of elements.

21

    /// Stores the block index for each element.

22

    element_to_block: Vec<BlockIndex>,

23

24

    /// Stores the offset within the block for every element.

25

    element_offset: Vec<usize>,

26

27

28

impl BlockPartition {

29

    /// Create an initial partition where all the states are in a single block

30

    /// 0. And all the elements in the block are marked.

31

5620

    pub fn new(num_of_elements: usize) -> BlockPartition {

32

5620

        debug_assert!(num_of_elements > 0, "Cannot partition the empty set");

33

34

5620

        let blocks = vec![Block::new(0, num_of_elements)];

35

5620

        let elements = (0..num_of_elements).map(StateIndex::new).collect();

36

5620

        let element_to_block = vec![BlockIndex::new(0); num_of_elements];

37

5620

        let element_to_block_offset = (0..num_of_elements).collect();

38

39

5620

        BlockPartition {

40

5620

            elements,

41

5620

            element_to_block,

42

5620

            element_offset: element_to_block_offset,

43

5620

            blocks,

44

5620

45

5620

46

47

    /// Partition the elements of the given block into multiple new blocks based

48

    /// on the given partitioner; which returns a number for each marked

49

    /// element. Elements with the same number belong to the same block, and the

50

    /// returned numbers should be dense.

51

///

52

    /// Returns an iterator over the new block indices, where the first element

53

    /// is the index of the block that was partitioned. And that block is the

54

    /// largest block.

55

168989

    pub fn partition_marked_with<F>(

56

168989

        &mut self,

57

168989

        block_index: BlockIndex,

58

168989

        builder: &mut BlockPartitionBuilder,

59

168989

        mut partitioner: F,

60

168989

    ) -> impl Iterator<Item = BlockIndex> + use<F>

61

168989

    where

62

168989

        F: FnMut(StateIndex, &BlockPartition) -> BlockIndex,

63

64

168989

        let block = self.blocks[block_index];

65

168989

        debug_assert!(

66

168989

            block.has_marked(),

67

            "Cannot partition marked elements of a block without marked elements"

68

);

69

70

168989

        if block.len() == 1 {

71

            // Block only has one element, so trivially partitioned.

72

68098

            self.blocks[block_index].unmark_all();

73

            // Note that all the returned iterators MUST have the same type, but we cannot chain typed_index since Step is an unstable trait.

74

68098

            return (block_index.value()..=block_index.value())

75

68098

                .chain(0..0)

76

68098

                .map(BlockIndex::new);

77

100891

78

79

        // Keeps track of the block index for every element in this block by index.

80

100891

        builder.index_to_block.clear();

81

100891

        builder.block_sizes.clear();

82

100891

        builder.old_elements.clear();

83

84

100891

        builder.index_to_block.resize(block.len_marked(), BlockIndex::new(0));

85

86

        // O(n log n) Loop through the marked elements in order (to maintain topological sorting)

87

100891

        builder.old_elements.extend(block.iter_marked(&self.elements));

88

100891

        builder.old_elements.sort_unstable();

89

90

        // O(n) Loop over marked elements to determine the number of the new block each element is in.

91

1519959

        for (element_index, &element) in builder.old_elements.iter().enumerate() {

92

1519959

            let number = partitioner(element, self);

93

94

1519959

            builder.index_to_block[element_index] = number;

95

1519959

            if number.value() + 1 > builder.block_sizes.len() {

96

341350

                builder.block_sizes.resize(number.value() + 1, 0);

97

1178628

98

99

1519959

            builder.block_sizes[number] += 1;

100

101

102

        // Convert block sizes into block offsets.

103

100891

        let end_of_blocks = self.blocks.len();

104

100891

        let new_block_index = if block.has_unmarked() {

105

27300

            self.blocks.len()

106

        } else {

107

73591

            self.blocks.len() - 1

108

};

109

110

341350

        let _ = builder.block_sizes.iter_mut().fold(0usize, |current, size| {

111

341350

            debug_assert!(*size > 0, "Partition is not dense, there are empty blocks");

112

113

341350

            let current = if current == 0 {

114

100891

                if block.has_unmarked() {

115

                    // Adapt the offsets of the current block to only include the unmarked elements.

116

27300

                    self.blocks[block_index] = Block::new_unmarked(block.begin, block.marked_split);

117

118

                    // Introduce a new block for the zero block.

119

27300

                    self.blocks

120

27300

                        .push(Block::new_unmarked(block.marked_split, block.marked_split + *size));

121

27300

                    block.marked_split

122

                } else {

123

                    // Use this as the zero block.

124

73591

                    self.blocks[block_index] = Block::new_unmarked(block.begin, block.begin + *size);

125

73591

                    block.begin

126

127

            } else {

128

                // Introduce a new block for every other non-empty block.

129

240459

                self.blocks.push(Block::new_unmarked(current, current + *size));

130

240459

                current

131

};

132

133

341350

            let offset = current + *size;

134

341350

            *size = current;

135

341350

            offset

136

341350

});

137

100891

        let block_offsets = &mut builder.block_sizes;

138

139

1519959

        for (index, offset_block_index) in builder.index_to_block.iter().enumerate() {

140

            // Swap the element to the correct position.

141

1519959

            let element = builder.old_elements[index];

142

1519959

            self.elements[block_offsets[*offset_block_index]] = builder.old_elements[index];

143

1519959

            self.element_offset[element] = block_offsets[*offset_block_index];

144

1519959

            self.element_to_block[element] = if *offset_block_index == 0 && !block.has_unmarked() {

145

397490

                block_index

146

            } else {

147

1122469

                BlockIndex::new(new_block_index + offset_block_index.value())

148

};

149

150

            // Update the offset for this block.

151

1519959

            block_offsets[*offset_block_index] += 1;

152

153

154

        // Swap the first block and the maximum sized block.

155

100891

        let max_block_index = (block_index.value()..=block_index.value())

156

100891

            .chain(end_of_blocks..self.blocks.len())

157

100891

            .map(BlockIndex::new)

158

368650

            .max_by_key(|block_index| self.block(*block_index).len())

159

100891

            .unwrap();

160

100891

        self.swap_blocks(block_index, max_block_index);

161

162

100891

        self.assert_consistent();

163

164

100891

        (block_index.value()..=block_index.value())

165

100891

            .chain(end_of_blocks..self.blocks.len())

166

100891

            .map(BlockIndex::new)

167

168989

168

169

    /// Split the given block into two separate block based on the splitter

170

    /// predicate.

171

3

    pub fn split_marked(&mut self, block_index: usize, mut splitter: impl FnMut(StateIndex) -> bool) {

172

3

        let mut updated_block = self.blocks[block_index];

173

3

        let mut new_block: Option<Block> = None;

174

175

        // Loop over all elements, we use a while loop since the index stays the

176

        // same when a swap takes place.

177

3

        let mut element_index = updated_block.marked_split;

178

23

        while element_index < updated_block.end {

179

20

            let element = self.elements[element_index];

180

20

            if splitter(element) {

181

10

                match &mut new_block {

182

3

                    None => {

183

3

                        new_block = Some(Block::new_unmarked(updated_block.end - 1, updated_block.end));

184

3

185

3

                        // Swap the current element to the last place

186

3

                        self.swap_elements(element_index, updated_block.end - 1);

187

3

                        updated_block.end -= 1;

188

3

189

7

                    Some(new_block_index) => {

190

7

                        // Swap the current element to the beginning of the new block.

191

7

                        new_block_index.begin -= 1;

192

7

                        updated_block.end -= 1;

193

7

194

7

                        self.swap_elements(element_index, new_block_index.begin);

195

7

196

197

10

            } else {

198

10

                // If no swap takes place consider the next index.

199

10

                element_index += 1;

200

10

201

202

203

3

        if let Some(new_block) = new_block

204

3

            && (updated_block.end - updated_block.begin) != 0

205

206

            // A new block was introduced, so we need to update the current

207

            // block. Unless the current block is empty in which case

208

            // nothing changes.

209

2

            updated_block.unmark_all();

210

2

            self.blocks[block_index] = updated_block;

211

212

            // Introduce a new block for the split, containing only the new element.

213

2

            self.blocks.push(new_block);

214

215

            // Update the elements for the new block

216

7

            for element in new_block.iter(&self.elements) {

217

7

                self.element_to_block[element] = BlockIndex::new(self.blocks.len() - 1);

218

7

219

1

220

221

3

        self.assert_consistent();

222

3

223

224

    /// Makes the marked elements closed under the silent closure of incoming

225

    /// tau-transitions within the current block.

226

193208

    pub fn mark_backward_closure(&mut self, block_index: BlockIndex, incoming_transitions: &IncomingTransitions) {

227

193208

        let block = self.blocks[block_index];

228

193208

        let mut it = block.end - 1;

229

230

        // First compute backwards silent transitive closure.

231

528775

        while it >= self.blocks[block_index].marked_split && self.blocks[block_index].has_unmarked() {

232

335567

            for transition in incoming_transitions.incoming_silent_transitions(self.elements[it]) {

233

147991

                if self.block_number(transition.from) == block_index {

234

91337

                    self.mark_element(transition.from);

235

91337

236

237

238

335567

            if it == 0 {

239

                break;

240

335567

241

242

335567

            it -= 1;

243

244

245

1127602

        for element in block.iter_marked(&self.elements) {

246

1127602

            debug_assert!(

247

1127602

                incoming_transitions

248

1127602

                    .incoming_silent_transitions(element)

249

1127602

                    .all(|transition| self.block_number(transition.from) != block_index

250

317546

                        || self.is_element_marked(transition.from)),

251

                "All silent transitions from marked elements should be marked"

252

);

253

254

193208

255

256

    /// Swaps the given blocks given by the indices.

257

171376

    pub fn swap_blocks(&mut self, left_index: BlockIndex, right_index: BlockIndex) {

258

171376

        if left_index == right_index {

259

            // Nothing to do.

260

105471

            return;

261

65905

262

263

65905

        self.blocks.swap(left_index.value(), right_index.value());

264

265

517466

        for element in self.block(left_index).iter(&self.elements) {

266

517466

            self.element_to_block[element] = left_index;

267

517466

268

269

276930

        for element in self.block(right_index).iter(&self.elements) {

270

276930

            self.element_to_block[element] = right_index;

271

276930

272

273

65905

        self.assert_consistent();

274

171376

275

276

    /// Marks the given element, such that it is returned by iter_marked.

277

4288744

    pub fn mark_element(&mut self, element: StateIndex) {

278

4288744

        let block_index = self.element_to_block[element];

279

4288744

        let offset = self.element_offset[element];

280

4288744

        let marked_split = self.blocks[block_index].marked_split;

281

282

4288744

        if offset < marked_split {

283

1807146

            // Element was not already marked.

284

1807146

            self.swap_elements(offset, marked_split - 1);

285

1807146

            self.blocks[block_index].marked_split -= 1;

286

2829678

287

288

4288744

        self.blocks[block_index].assert_consistent();

289

4288744

290

291

    /// Returns true iff the given element has already been marked.

292

654289

    pub fn is_element_marked(&self, element: StateIndex) -> bool {

293

654289

        let block_index = self.element_to_block[element];

294

654289

        let offset = self.element_offset[element];

295

654289

        let marked_split = self.blocks[block_index].marked_split;

296

297

654289

        offset >= marked_split

298

654289

299

300

    /// Return a reference to the given block.

301

5342312

    pub fn block(&self, block_index: BlockIndex) -> &Block {

302

5342312

        &self.blocks[block_index]

303

5342312

304

305

    /// Returns the number of blocks in the partition.

306

700868

    pub fn num_of_blocks(&self) -> usize {

307

700868

        self.blocks.len()

308

700868

309

310

    /// Returns an iterator over the elements of a given block.

311

720298

    pub fn iter_block(&self, block_index: BlockIndex) -> BlockIter<'_> {

312

720298

        BlockIter {

313

720298

            elements: &self.elements,

314

720298

            index: self.blocks[block_index].begin,

315

720298

            end: self.blocks[block_index].end,

316

720298

317

720298

318

319

    /// Swaps the elements at the given indices and updates the element_to_block

320

1807156

    fn swap_elements(&mut self, left_index: usize, right_index: usize) {

321

1807156

        self.elements.swap(left_index, right_index);

322

1807156

        self.element_offset[self.elements[left_index]] = left_index;

323

1807156

        self.element_offset[self.elements[right_index]] = right_index;

324

1807156

325

326

    /// Returns true iff the invariants of a partition hold

327

237284

    fn assert_consistent(&self) -> bool {

328

237284

        if cfg!(debug_assertions) {

329

237284

            let mut marked = vec![false; self.elements.len()];

330

331

31575958

            for block in &self.blocks {

332

209085162

                for element in block.iter(&self.elements) {

333

209085162

                    debug_assert!(

334

209085162

                        !marked[element],

335

                        "Partition {self}, element {element} belongs to multiple blocks"

336

);

337

209085162

                    marked[element] = true;

338

339

340

31575958

                block.assert_consistent();

341

342

343

            // Check that every element belongs to a block.

344

237284

            debug_assert!(

345

237284

                !marked.contains(&false),

346

                "Partition {self} contains elements that do not belong to a block"

347

);

348

349

            // Check that it belongs to the block indicated by element_to_block

350

209085162

            for (current_element, block_index) in self.element_to_block.iter().enumerate() {

351

209085162

                debug_assert!(

352

209085162

                    self.blocks[block_index.value()]

353

209085162

                        .iter(&self.elements)

354

28901035878

                        .any(|element| element == current_element),

355

                    "Partition {self:?}, element {current_element} does not belong to block {block_index} as indicated by element_to_block"

356

);

357

358

209085162

                let index = self.element_offset[current_element];

359

209085162

                debug_assert_eq!(

360

209085162

                    self.elements[index], current_element,

361

                    "Partition {self:?}, element {current_element} does not have the correct offset in the block"

362

);

363

364

365

366

237284

        true

367

237284

368

369

370

#[derive(Default)]

371

pub struct BlockPartitionBuilder {

372

    // Keeps track of the block index for every element in this block by index.

373

    index_to_block: Vec<BlockIndex>,

374

375

    /// Keeps track of the size of each block.

376

    block_sizes: Vec<usize>,

377

378

    /// Stores the old elements to perform the swaps safely.

379

    old_elements: Vec<StateIndex>,

380

381

382

impl Partition for BlockPartition {

383

108124181

    fn block_number(&self, element: StateIndex) -> BlockIndex {

384

108124181

        self.element_to_block[element.value()]

385

108124181

386

387

200

    fn num_of_blocks(&self) -> usize {

388

200

        self.blocks.len()

389

200

390

391

164654

    fn len(&self) -> usize {

392

164654

        self.elements.len()

393

164654

394

395

396

impl fmt::Display for BlockPartition {

397

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

398

        let blocks_str = self.blocks.iter().format_with(", ", |block, f| {

399

            let elements = block

400

                .iter_unmarked(&self.elements)

401

                .map(|e| (e, false))

402

                .chain(block.iter_marked(&self.elements).map(|e| (e, true)))

403

                .format_with(", ", |(e, marked), f| {

404

                    if marked {

405

                        f(&format_args!("{}*", e))

406

                    } else {

407

                        f(&format_args!("{}", e))

408

409

});

410

411

            f(&format_args!("{{{}}}", elements))

412

});

413

414

        write!(f, "{{{}}}", blocks_str)

415

416

417

418

/// A block stores a subset of the elements in a partition.

419

///

420

/// # Details

421

///

422

/// A block uses `start`, `middle` and `end` indices to indicate a range

423

/// `start`..`end` of elements in the partition. The middle is used such that

424

/// `marked_split`..`end` are the marked elements. This is useful to be able to

425

/// split off new blocks cheaply.

426

///

427

/// Invariant: `start` <= `middle` <= `end` && `start` < `end`.

428

#[derive(Clone, Copy, Debug)]

429

pub struct Block {

430

    begin: usize,

431

    marked_split: usize,

432

    end: usize,

433

434

435

impl Block {

436

    /// Creates a new block where every element is marked.

437

5620

    pub fn new(begin: usize, end: usize) -> Block {

438

5620

        debug_assert!(begin < end, "The range of this block is incorrect");

439

440

5620

        Block {

441

5620

            begin,

442

5620

            marked_split: begin,

443

5620

            end,

444

5620

445

5620

446

447

665298

    pub fn new_unmarked(begin: usize, end: usize) -> Block {

448

665298

        debug_assert!(begin < end, "The range {begin} to {end} of this block is incorrect");

449

450

665298

        Block {

451

665298

            begin,

452

665298

            marked_split: end,

453

665298

            end,

454

665298

455

665298

456

457

    /// Returns an iterator over the elements in this block.

458

240792932

    pub fn iter<'a>(&self, elements: &'a Vec<StateIndex>) -> BlockIter<'a> {

459

240792932

        BlockIter {

460

240792932

            elements,

461

240792932

            index: self.begin,

462

240792932

            end: self.end,

463

240792932

464

240792932

465

466

    /// Returns an iterator over the marked elements in this block.

467

364584

    pub fn iter_marked<'a>(&self, elements: &'a Vec<StateIndex>) -> BlockIter<'a> {

468

364584

        BlockIter {

469

364584

            elements,

470

364584

            index: self.marked_split,

471

364584

            end: self.end,

472

364584

473

364584

474

475

    /// Returns an iterator over the unmarked elements in this block.

476

    pub fn iter_unmarked<'a>(&self, elements: &'a Vec<StateIndex>) -> BlockIter<'a> {

477

        BlockIter {

478

            elements,

479

            index: self.begin,

480

            end: self.marked_split,

481

482

483

484

    /// Returns true iff the block has marked elements.

485

4893021

    pub fn has_marked(&self) -> bool {

486

4893021

        self.assert_consistent();

487

488

4893021

        self.marked_split < self.end

489

4893021

490

491

    /// Returns true iff the block has unmarked elements.

492

2131939

    pub fn has_unmarked(&self) -> bool {

493

2131939

        self.assert_consistent();

494

495

2131939

        self.begin < self.marked_split

496

2131939

497

498

    /// Returns the number of elements in the block.

499

1013109

    pub fn len(&self) -> usize {

500

1013109

        self.assert_consistent();

501

502

1013109

        self.end - self.begin

503

1013109

504

505

    /// Returns true iff the block is empty.

506

    pub fn is_empty(&self) -> bool {

507

        self.assert_consistent();

508

509

        self.begin == self.end

510

511

512

    /// Returns the number of marked elements in the block.

513

171376

    pub fn len_marked(&self) -> usize {

514

171376

        self.assert_consistent();

515

516

171376

        self.end - self.marked_split

517

171376

518

519

    /// Unmark all elements in the block.

520

176440

    fn unmark_all(&mut self) {

521

176440

        self.marked_split = self.end;

522

176440

523

524

    /// Returns true iff the block is consistent.

525

44074147

    fn assert_consistent(self) {

526

44074147

        debug_assert!(self.begin < self.end, "The range of block {self:?} is incorrect",);

527

528

44074147

        debug_assert!(

529

44074147

            self.begin <= self.marked_split,

530

            "The marked_split lies before the beginning of the block {self:?}"

531

);

532

533

44074147

        debug_assert!(

534

44074147

            self.marked_split <= self.end,

535

            "The marked_split lies after the beginning of the block {self:?}"

536

);

537

44074147

538

539

540

pub struct BlockIter<'a> {

541

    elements: &'a Vec<StateIndex>,

542

    index: usize,

543

    end: usize,

544

545

546

impl Iterator for BlockIter<'_> {

547

    type Item = StateIndex;

548

549

29149785734

    fn next(&mut self) -> Option<Self::Item> {

550

29149785734

        if self.index < self.end {

551

29117219461

            let element = self.elements[self.index];

552

29117219461

            self.index += 1;

553

29117219461

            Some(element)

554

        } else {

555

32566273

            None

556

557

29149785734

558

559

560

#[cfg(test)]

561

mod tests {

562

    use merc_lts::StateIndex;

563

    use test_log::test;

564

565

    use merc_collections::BlockIndex;

566

567

    use crate::BlockPartition;

568

    use crate::BlockPartitionBuilder;

569

570

    #[test]

571

    fn test_block_partition_split() {

572

        let mut partition = BlockPartition::new(10);

573

574

10

        partition.split_marked(0, |element| element < 3);

575

576

        // The new block only has elements that satisfy the predicate.

577

        for element in partition.iter_block(BlockIndex::new(1)) {

578

            assert!(element < 3);

579

580

581

        for element in partition.iter_block(BlockIndex::new(0)) {

582

            assert!(element >= 3);

583

584

585

        for i in (0..10).map(StateIndex::new) {

586

            partition.mark_element(i);

587

588

589

7

        partition.split_marked(0, |element| element < 7);

590

        for element in partition.iter_block(BlockIndex::new(2)) {

591

            assert!((3..7).contains(&element.value()));

592

593

594

        for element in partition.iter_block(BlockIndex::new(0)) {

595

            assert!(element >= 7);

596

597

598

        // Test the case where all elements belong to the split block.

599

3

        partition.split_marked(1, |element| element < 7);

600

601

602

    #[test]

603

    fn test_block_partition_partitioning() {

604

        // Test the partitioning function for a random assignment of elements

605

        let mut partition = BlockPartition::new(10);

606

        let mut builder = BlockPartitionBuilder::default();

607

608

10

        let _ = partition.partition_marked_with(BlockIndex::new(0), &mut builder, |element, _| match element.value() {

609

10

            0..=1 => BlockIndex::new(0),

610

8

            2..=6 => BlockIndex::new(1),

611

3

            _ => BlockIndex::new(2),

612

10

});

613

614

        partition.mark_element(StateIndex::new(7));

615

        partition.mark_element(StateIndex::new(8));

616

2

        let _ = partition.partition_marked_with(BlockIndex::new(2), &mut builder, |element, _| match element.value() {

617

1

            7 => BlockIndex::new(0),

618

1

            8 => BlockIndex::new(1),

619

            _ => BlockIndex::new(2),

620

2

});

621

622