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

9442

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

32

9442

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

33

34

9442

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

35

9442

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

36

9442

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

37

9442

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

38

39

9442

        BlockPartition {

40

9442

            elements,

41

9442

            element_to_block,

42

9442

            element_offset: element_to_block_offset,

43

9442

            blocks,

44

9442

45

9442

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

170808

    pub fn partition_marked_with<F>(

56

170808

        &mut self,

57

170808

        block_index: BlockIndex,

58

170808

        builder: &mut BlockPartitionBuilder,

59

170808

        mut partitioner: F,

60

170808

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

61

170808

    where

62

170808

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

63

64

170808

        let block = self.blocks[block_index];

65

170808

        debug_assert!(

66

170808

            block.has_marked(),

67

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

68

);

69

70

170808

        if block.len() == 1 {

71

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

72

69059

            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

69059

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

75

69059

                .chain(0..0)

76

69059

                .map(BlockIndex::new);

77

101749

78

79

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

80

101749

        builder.index_to_block.clear();

81

101749

        builder.block_sizes.clear();

82

101749

        builder.old_elements.clear();

83

84

101749

        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

101749

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

88

101749

        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

1426025

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

92

1426025

            let number = partitioner(element, self);

93

94

1426025

            builder.index_to_block[element_index] = number;

95

1426025

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

96

343939

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

97

1082105

98

99

1426025

            builder.block_sizes[number] += 1;

100

101

102

        // Convert block sizes into block offsets.

103

101749

        let end_of_blocks = self.blocks.len();

104

101749

        let new_block_index = if block.has_unmarked() {

105

27350

            self.blocks.len()

106

        } else {

107

74399

            self.blocks.len() - 1

108

};

109

110

343939

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

111

343939

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

112

113

343939

            let current = if current == 0 {

114

101749

                if block.has_unmarked() {

115

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

116

27350

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

117

118

                    // Introduce a new block for the zero block.

119

27350

                    self.blocks

120

27350

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

121

27350

                    block.marked_split

122

                } else {

123

                    // Use this as the zero block.

124

74399

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

125

74399

                    block.begin

126

127

            } else {

128

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

129

242190

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

130

242190

                current

131

};

132

133

343939

            let offset = current + *size;

134

343939

            *size = current;

135

343939

            offset

136

343939

});

137

101749

        let block_offsets = &mut builder.block_sizes;

138

139

1426025

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

140

            // Swap the element to the correct position.

141

1426025

            let element = builder.old_elements[index];

142

1426025

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

143

1426025

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

144

1426025

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

145

343016

                block_index

146

            } else {

147

1083009

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

148

};

149

150

            // Update the offset for this block.

151

1426025

            block_offsets[*offset_block_index] += 1;

152

153

154

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

155

101749

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

156

101749

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

157

101749

            .map(BlockIndex::new)

158

371289

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

159

101749

            .unwrap();

160

101749

        self.swap_blocks(block_index, max_block_index);

161

162

101749

        self.assert_consistent();

163

164

101749

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

165

101749

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

166

101749

            .map(BlockIndex::new)

167

170808

168

169

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

170

    /// predicate.

171

3

    pub fn split_marked<F>(&mut self, block_index: usize, mut splitter: F)

172

3

    where

173

3

        F: FnMut(StateIndex) -> bool,

174

175

3

        let mut updated_block = self.blocks[block_index];

176

3

        let mut new_block: Option<Block> = None;

177

178

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

179

        // same when a swap takes place.

180

3

        let mut element_index = updated_block.marked_split;

181

23

        while element_index < updated_block.end {

182

20

            let element = self.elements[element_index];

183

20

            if splitter(element) {

184

10

                match &mut new_block {

185

3

                    None => {

186

3

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

187

3

188

3

                        // Swap the current element to the last place

189

3

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

190

3

                        updated_block.end -= 1;

191

3

192

7

                    Some(new_block_index) => {

193

7

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

194

7

                        new_block_index.begin -= 1;

195

7

                        updated_block.end -= 1;

196

7

197

7

                        self.swap_elements(element_index, new_block_index.begin);

198

7

199

200

10

            } else {

201

10

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

202

10

                element_index += 1;

203

10

204

205

206

3

        if let Some(new_block) = new_block

207

3

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

208

209

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

210

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

211

            // nothing changes.

212

2

            updated_block.unmark_all();

213

2

            self.blocks[block_index] = updated_block;

214

215

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

216

2

            self.blocks.push(new_block);

217

218

            // Update the elements for the new block

219

7

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

220

7

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

221

7

222

1

223

224

3

        self.assert_consistent();

225

3

226

227

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

228

    /// tau-transitions within the current block.

229

290790

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

230

290790

        let block = self.blocks[block_index];

231

290790

        let mut it = block.end - 1;

232

233

        // First compute backwards silent transitive closure.

234

783321

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

235

492531

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

236

220947

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

237

135792

                    self.mark_element(transition.from);

238

135792

239

240

241

492531

            if it == 0 {

242

                break;

243

492531

244

245

492531

            it -= 1;

246

247

248

1667139

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

249

1667139

            debug_assert!(

250

1667139

                incoming_transitions

251

1667139

                    .incoming_silent_transitions(element)

252

1667139

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

253

463793

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

254

                "All silent transitions from marked elements should be marked"

255

);

256

257

290790

258

259

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

260

231547

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

261

231547

        if left_index == right_index {

262

            // Nothing to do.

263

138991

            return;

264

92556

265

266

92556

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

267

268

544925

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

269

544925

            self.element_to_block[element] = left_index;

270

544925

271

272

309706

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

273

309706

            self.element_to_block[element] = right_index;

274

309706

275

276

92556

        self.assert_consistent();

277

231547

278

279

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

280

3341413

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

281

3341413

        let block_index = self.element_to_block[element];

282

3341413

        let offset = self.element_offset[element];

283

3341413

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

284

285

3341413

        if offset < marked_split {

286

1800144

            // Element was not already marked.

287

1800144

            self.swap_elements(offset, marked_split - 1);

288

1800144

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

289

1890284

290

291

3341413

        self.blocks[block_index].assert_consistent();

292

3341413

293

294

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

295

955250

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

296

955250

        let block_index = self.element_to_block[element];

297

955250

        let offset = self.element_offset[element];

298

955250

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

299

300

955250

        offset >= marked_split

301

955250

302

303

    /// Return a reference to the given block.

304

4797833

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

305

4797833

        &self.blocks[block_index]

306

4797833

307

308

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

309

1001769

    pub fn num_of_blocks(&self) -> usize {

310

1001769

        self.blocks.len()

311

1001769

312

313

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

314

1033861

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

315

1033861

        BlockIter {

316

1033861

            elements: &self.elements,

317

1033861

            index: self.blocks[block_index].begin,

318

1033861

            end: self.blocks[block_index].end,

319

1033861

320

1033861

321

322

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

323

1800154

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

324

1800154

        self.elements.swap(left_index, right_index);

325

1800154

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

326

1800154

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

327

1800154

328

329

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

330

324106

    fn assert_consistent(&self) -> bool {

331

324106

        if cfg!(debug_assertions) {

332

324106

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

333

334

34373572

            for block in &self.blocks {

335

168334246

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

336

168334246

                    debug_assert!(

337

168334246

                        !marked[element],

338

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

339

);

340

168334246

                    marked[element] = true;

341

342

343

34373572

                block.assert_consistent();

344

345

346

            // Check that every element belongs to a block.

347

324106

            debug_assert!(

348

324106

                !marked.contains(&false),

349

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

350

);

351

352

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

353

168334246

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

354

168334246

                debug_assert!(

355

168334246

                    self.blocks[block_index.value()]

356

168334246

                        .iter(&self.elements)

357

14459531162

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

358

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

359

);

360

361

168334246

                let index = self.element_offset[current_element];

362

168334246

                debug_assert_eq!(

363

168334246

                    self.elements[index], current_element,

364

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

365

);

366

367

368

369

324106

        true

370

324106

371

372

373

#[derive(Default)]

374

pub struct BlockPartitionBuilder {

375

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

376

    index_to_block: Vec<BlockIndex>,

377

378

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

379

    block_sizes: Vec<usize>,

380

381

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

382

    old_elements: Vec<StateIndex>,

383

384

385

impl Partition for BlockPartition {

386

109211534

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

387

109211534

        self.element_to_block[element.value()]

388

109211534

389

390

200

    fn num_of_blocks(&self) -> usize {

391

200

        self.blocks.len()

392

200

393

394

165260

    fn len(&self) -> usize {

395

165260

        self.elements.len()

396

165260

397

398

399

impl fmt::Display for BlockPartition {

400

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

401

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

402

            let elements = block

403

                .iter_unmarked(&self.elements)

404

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

405

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

406

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

407

                    if marked {

408

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

409

                    } else {

410

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

411

412

});

413

414

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

415

});

416

417

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

418

419

420

421

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

422

///

423

/// # Details

424

///

425

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

426

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

427

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

428

/// split off new blocks cheaply.

429

///

430

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

431

#[derive(Clone, Copy, Debug)]

432

pub struct Block {

433

    begin: usize,

434

    marked_split: usize,

435

    end: usize,

436

437

438

impl Block {

439

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

440

9442

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

441

9442

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

442

443

9442

        Block {

444

9442

            begin,

445

9442

            marked_split: begin,

446

9442

            end,

447

9442

448

9442

449

450

911121

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

451

911121

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

452

453

911121

        Block {

454

911121

            begin,

455

911121

            marked_split: end,

456

911121

            end,

457

911121

458

911121

459

460

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

461

202892932

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

462

202892932

        BlockIter {

463

202892932

            elements,

464

202892932

            index: self.begin,

465

202892932

            end: self.end,

466

202892932

467

202892932

468

469

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

470

522337

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

471

522337

        BlockIter {

472

522337

            elements,

473

522337

            index: self.marked_split,

474

522337

            end: self.end,

475

522337

476

522337

477

478

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

479

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

480

        BlockIter {

481

            elements,

482

            index: self.begin,

483

            end: self.marked_split,

484

485

486

487

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

488

4197599

    pub fn has_marked(&self) -> bool {

489

4197599

        self.assert_consistent();

490

491

4197599

        self.marked_split < self.end

492

4197599

493

494

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

495

2547485

    pub fn has_unmarked(&self) -> bool {

496

2547485

        self.assert_consistent();

497

498

2547485

        self.begin < self.marked_split

499

2547485

500

501

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

502

///

503

    /// A block always satisfies `begin < end`, so it is never empty; there is

504

    /// deliberately no `is_empty`.

505

    #[allow(clippy::len_without_is_empty)]

506

1407114

    pub fn len(&self) -> usize {

507

1407114

        self.assert_consistent();

508

509

1407114

        self.end - self.begin

510

1407114

511

512

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

513

231547

    pub fn len_marked(&self) -> usize {

514

231547

        self.assert_consistent();

515

516

231547

        self.end - self.marked_split

517

231547

518

519

    /// Unmark all elements in the block.

520

264451

    fn unmark_all(&mut self) {

521

264451

        self.marked_split = self.end;

522

264451

523

524

    /// Returns true iff the block is consistent.

525

46098730

    fn assert_consistent(&self) {

526

46098730

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

527

528

46098730

        debug_assert!(

529

46098730

            self.begin <= self.marked_split,

530

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

531

);

532

533

46098730

        debug_assert!(

534

46098730

            self.marked_split <= self.end,

535

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

536

);

537

46098730

538

539

540

pub struct BlockIter<'a> {

541

    elements: &'a [StateIndex],

542

    index: usize,

543

    end: usize,

544

545

546

impl Iterator for BlockIter<'_> {

547

    type Item = StateIndex;

548

549

14672150822

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

550

14672150822

        if self.index < self.end {

551

14636390228

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

552

14636390228

            self.index += 1;

553

14636390228

            Some(element)

554

        } else {

555

35760594

            None

556

557

14672150822

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

1

    fn test_block_partition_split() {

572

1

        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

3

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

578

3

            assert!(element < 3);

579

580

581

7

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

582

7

            assert!(element >= 3);

583

584

585

10

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

586

10

            partition.mark_element(i);

587

10

588

589

7

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

590

4

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

591

4

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

592

593

594

3

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

595

3

            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

1

601

602

    #[test]

603

1

    fn test_block_partition_partitioning() {

604

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

605

1

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

606

1

        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

1

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

615

1

        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

1

622