Grcov report - block

1

#![forbid(unsafe_code)]

2

3

use std::fmt;

4

5

use itertools::Itertools;

6

7

use merc_lts::IncomingTransitions;

8

use merc_lts::StateIndex;

9

10

use super::Partition;

11

use crate::BlockIndex;

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

402

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

32

402

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

33

34

402

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

35

402

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

36

402

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

37

402

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

38

39

402

        BlockPartition {

40

402

            elements,

41

402

            element_to_block,

42

402

            element_offset: element_to_block_offset,

43

402

            blocks,

44

402

45

402

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

20801

    pub fn partition_marked_with<F>(

56

20801

        &mut self,

57

20801

        block_index: BlockIndex,

58

20801

        builder: &mut BlockPartitionBuilder,

59

20801

        mut partitioner: F,

60

20801

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

61

20801

    where

62

20801

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

63

64

20801

        let block = self.blocks[block_index];

65

20801

        debug_assert!(

66

20801

            block.has_marked(),

67

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

68

);

69

70

20801

        if block.len() == 1 {

71

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

72

16198

            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

16198

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

75

16198

                .chain(0..0)

76

16198

                .map(BlockIndex::new);

77

4603

78

79

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

80

4603

        builder.index_to_block.clear();

81

4603

        builder.block_sizes.clear();

82

4603

        builder.old_elements.clear();

83

84

4603

        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

4603

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

88

4603

        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

30970

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

92

30970

            let number = partitioner(element, self);

93

94

30970

            builder.index_to_block[element_index] = number;

95

30970

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

96

18727

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

97

20385

98

99

30970

            builder.block_sizes[number] += 1;

100

101

102

        // Convert block sizes into block offsets.

103

4603

        let end_of_blocks = self.blocks.len();

104

4603

        let new_block_index = if block.has_unmarked() {

105

207

            self.blocks.len()

106

        } else {

107

4396

            self.blocks.len() - 1

108

};

109

110

18727

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

111

18727

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

112

113

18727

            let current = if current == 0 {

114

4603

                if block.has_unmarked() {

115

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

116

207

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

117

118

                    // Introduce a new block for the zero block.

119

207

                    self.blocks

120

207

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

121

207

                    block.marked_split

122

                } else {

123

                    // Use this as the zero block.

124

4396

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

125

4396

                    block.begin

126

127

            } else {

128

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

129

14124

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

130

14124

                current

131

};

132

133

18727

            let offset = current + *size;

134

18727

            *size = current;

135

18727

            offset

136

18727

});

137

4603

        let block_offsets = &mut builder.block_sizes;

138

139

30970

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

140

            // Swap the element to the correct position.

141

30970

            let element = builder.old_elements[index];

142

30970

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

143

30970

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

144

30970

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

145

9056

                block_index

146

            } else {

147

21914

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

148

};

149

150

            // Update the offset for this block.

151

30970

            block_offsets[*offset_block_index] += 1;

152

153

154

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

155

4603

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

156

4603

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

157

4603

            .map(BlockIndex::new)

158

18934

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

159

4603

            .unwrap();

160

4603

        self.swap_blocks(block_index, max_block_index);

161

162

4603

        self.assert_consistent();

163

164

4603

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

165

4603

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

166

4603

            .map(BlockIndex::new)

167

20801

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

            if (updated_block.end - updated_block.begin) != 0 {

205

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

206

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

207

                // nothing changes.

208

2

                updated_block.unmark_all();

209

2

                self.blocks[block_index] = updated_block;

210

211

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

212

2

                self.blocks.push(new_block);

213

214

                // Update the elements for the new block

215

7

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

216

7

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

217

7

218

1

219

220

221

3

        println!("{self:?}");

222

3

        self.assert_consistent();

223

3

224

225

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

226

    /// tau-transitions within the current block.

227

366

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

228

366

        let block = self.blocks[block_index];

229

366

        let mut it = block.end - 1;

230

231

        // First compute backwards silent transitive closure.

232

979

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

233

613

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

234

611

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

235

556

                    self.mark_element(transition.to);

236

556

237

238

239

613

            if it == 0 {

240

                break;

241

613

242

243

613

            it -= 1;

244

245

366

246

247

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

248

4603

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

249

4603

        if left_index == right_index {

250

            // Nothing to do.

251

2345

            return;

252

2258

253

254

2258

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

255

256

3608

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

257

3608

            self.element_to_block[element] = left_index;

258

3608

259

260

2738

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

261

2738

            self.element_to_block[element] = right_index;

262

2738

263

264

2258

        self.assert_consistent();

265

4603

266

267

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

268

107538

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

269

107538

        let block_index = self.element_to_block[element];

270

107538

        let offset = self.element_offset[element];

271

107538

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

272

273

107538

        if offset < marked_split {

274

28213

            // Element was not already marked.

275

28213

            self.swap_elements(offset, marked_split - 1);

276

28213

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

277

80394

278

279

107538

        self.blocks[block_index].assert_consistent();

280

107538

281

282

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

283

2029

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

284

2029

        let block_index = self.element_to_block[element];

285

2029

        let offset = self.element_offset[element];

286

2029

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

287

288

2029

        offset >= marked_split

289

2029

290

291

    /// Return a reference to the given block.

292

151219

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

293

151219

        &self.blocks[block_index]

294

151219

295

296

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

297

41798

    pub fn num_of_blocks(&self) -> usize {

298

41798

        self.blocks.len()

299

41798

300

301

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

302

27541

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

303

27541

        BlockIter {

304

27541

            elements: &self.elements,

305

27541

            index: self.blocks[block_index].begin,

306

27541

            end: self.blocks[block_index].end,

307

27541

308

27541

309

310

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

311

28223

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

312

28223

        self.elements.swap(left_index, right_index);

313

28223

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

314

28223

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

315

28223

316

317

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

318

6864

    fn assert_consistent(&self) -> bool {

319

6864

        if cfg!(debug_assertions) {

320

6864

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

321

322

1927620

            for block in &self.blocks {

323

2709519

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

324

2709519

                    debug_assert!(

325

2709519

                        !marked[element],

326

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

327

);

328

2709519

                    marked[element] = true;

329

330

331

1927620

                block.assert_consistent();

332

333

334

            // Check that every element belongs to a block.

335

6864

            debug_assert!(

336

6864

                !marked.contains(&false),

337

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

338

);

339

340

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

341

2709519

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

342

2709519

                debug_assert!(

343

2709519

                    self.blocks[block_index.value()]

344

2709519

                        .iter(&self.elements)

345

4934769

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

346

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

347

);

348

349

2709519

                let index = self.element_offset[current_element];

350

2709519

                debug_assert_eq!(

351

2709519

                    self.elements[index], current_element,

352

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

353

);

354

355

356

357

6864

        true

358

6864

359

360

361

#[derive(Default)]

362

pub struct BlockPartitionBuilder {

363

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

364

    index_to_block: Vec<BlockIndex>,

365

366

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

367

    block_sizes: Vec<usize>,

368

369

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

370

    old_elements: Vec<StateIndex>,

371

372

373

impl Partition for BlockPartition {

374

410530

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

375

410530

        self.element_to_block[element.value()]

376

410530

377

378

200

    fn num_of_blocks(&self) -> usize {

379

200

        self.blocks.len()

380

200

381

382

2592

    fn len(&self) -> usize {

383

2592

        self.elements.len()

384

2592

385

386

387

impl fmt::Display for BlockPartition {

388

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

389

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

390

            let elements = block

391

                .iter_unmarked(&self.elements)

392

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

393

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

394

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

395

                    if marked {

396

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

397

                    } else {

398

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

399

400

});

401

402

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

403

});

404

405

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

406

407

408

409

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

410

///

411

/// # Details

412

///

413

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

414

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

415

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

416

/// split off new blocks cheaply.

417

///

418

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

419

#[derive(Clone, Copy, Debug)]

420

pub struct Block {

421

    begin: usize,

422

    marked_split: usize,

423

    end: usize,

424

425

426

impl Block {

427

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

428

402

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

429

402

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

430

431

402

        Block {

432

402

            begin,

433

402

            marked_split: begin,

434

402

            end,

435

402

436

402

437

438

18937

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

439

18937

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

440

441

18937

        Block {

442

18937

            begin,

443

18937

            marked_split: end,

444

18937

            end,

445

18937

446

18937

447

448

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

449

4641657

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

450

4641657

        BlockIter {

451

4641657

            elements,

452

4641657

            index: self.begin,

453

4641657

            end: self.end,

454

4641657

455

4641657

456

457

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

458

4603

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

459

4603

        BlockIter {

460

4603

            elements,

461

4603

            index: self.marked_split,

462

4603

            end: self.end,

463

4603

464

4603

465

466

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

467

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

468

        BlockIter {

469

            elements,

470

            index: self.begin,

471

            end: self.marked_split,

472

473

474

475

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

476

148570

    pub fn has_marked(&self) -> bool {

477

148570

        self.assert_consistent();

478

479

148570

        self.marked_split < self.end

480

148570

481

482

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

483

19643

    pub fn has_unmarked(&self) -> bool {

484

19643

        self.assert_consistent();

485

486

19643

        self.begin < self.marked_split

487

19643

488

489

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

490

39735

    pub fn len(&self) -> usize {

491

39735

        self.assert_consistent();

492

493

39735

        self.end - self.begin

494

39735

495

496

    /// Returns true iff the block is empty.

497

    pub fn is_empty(&self) -> bool {

498

        self.assert_consistent();

499

500

        self.begin == self.end

501

502

503

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

504

4603

    pub fn len_marked(&self) -> usize {

505

4603

        self.assert_consistent();

506

507

4603

        self.end - self.marked_split

508

4603

509

510

    /// Unmark all elements in the block.

511

16200

    fn unmark_all(&mut self) {

512

16200

        self.marked_split = self.end;

513

16200

514

515

    /// Returns true iff the block is consistent.

516

2247709

    fn assert_consistent(self) {

517

2247709

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

518

519

2247709

        debug_assert!(

520

2247709

            self.begin <= self.marked_split,

521

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

522

);

523

524

2247709

        debug_assert!(

525

2247709

            self.marked_split <= self.end,

526

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

527

);

528

2247709

529

530

531

pub struct BlockIter<'a> {

532

    elements: &'a Vec<StateIndex>,

533

    index: usize,

534

    end: usize,

535

536

537

impl Iterator for BlockIter<'_> {

538

    type Item = StateIndex;

539

540

9666947

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

541

9666947

        if self.index < self.end {

542

7715875

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

543

7715875

            self.index += 1;

544

7715875

            Some(element)

545

        } else {

546

1951072

            None

547

548

9666947

549

550

551

#[cfg(test)]

552

mod tests {

553

    use super::*;

554

555

    use test_log::test;

556

557

    #[test]

558

    fn test_block_partition_split() {

559

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

560

561

10

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

562

563

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

564

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

565

            assert!(element < 3);

566

567

568

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

569

            assert!(element >= 3);

570

571

572

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

573

            partition.mark_element(i);

574

575

576

7

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

577

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

578

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

579

580

581

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

582

            assert!(element >= 7);

583

584

585

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

586

3

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

587

588

589

    #[test]

590

    fn test_block_partition_partitioning() {

591

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

592

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

593

        let mut builder = BlockPartitionBuilder::default();

594

595

10

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

596

10

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

597

8

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

598

3

            _ => BlockIndex::new(2),

599

10

});

600

601

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

602

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

603

2

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

604

1

            7 => BlockIndex::new(0),

605

1

            8 => BlockIndex::new(1),

606

            _ => BlockIndex::new(2),

607

2

});

608

609