Grcov report - operations.rs

1

use crate::BinaryOperator;

2

use crate::Data;

3

use crate::DataRef;

4

use crate::Ldd;

5

use crate::LddRef;

6

use crate::Storage;

7

use crate::TernaryOperator;

8

use crate::UnaryFunction;

9

use crate::Value;

10

use crate::cache_binary_op;

11

use crate::cache_comm_binary_op;

12

use crate::cache_terniary_op;

13

use crate::cache_unary_function;

14

use crate::iterators::*;

15

16

use std::cmp::Ordering;

17

use std::cmp::{self};

18

19

/// Returns an LDD containing only the given vector, i.e., { vector }.

20

413501

pub fn singleton(storage: &mut Storage, vector: &[Value]) -> Ldd {

21

413501

    let mut root = storage.empty_vector().clone();

22

413501

    let empty_set = storage.empty_set().clone();

23

5001968

    for val in vector.iter().rev() {

24

5001968

        root = storage.insert(*val, &root, &empty_set);

25

5001968

26

27

413501

    root

28

413501

29

30

/// Computes a meta LDD that is suitable for the [project] function from the

31

/// given projection indices.

32

///

33

/// This function is useful to be able to cache the projection LDD instead of

34

/// computing it from the projection array every time.

35

300

pub fn compute_proj(storage: &mut Storage, proj: &[Value]) -> Ldd {

36

    // Compute length of proj.

37

300

    let length = match proj.iter().max() {

38

300

        Some(x) => *x + 1,

39

        None => 0,

40

};

41

42

    // Convert projection vectors to meta information.

43

300

    let mut result: Vec<Value> = Vec::new();

44

2381

    for i in 0..length {

45

2381

        let included = proj.contains(&i);

46

47

2381

        if included {

48

1200

            result.push(1);

49

1200

        } else {

50

1181

            result.push(0);

51

1181

52

53

54

300

    singleton(storage, &result)

55

300

56

57

/// Computes the set of vectors projected onto the given indices, where proj is equal to compute_proj([i_0, ..., i_k]).

58

///

59

/// Formally, for a single vector <x_0, ..., x_n> we have that:

60

///     - project(<x_0, ..., x_n>, i_0 < ... < i_k) = <x_(i_0), ..., x_(i_k)>

61

///     - project(X, i_0 < ... < i_k) = { project(x, i_0 < ... < i_k) | x in X }.

62

///

63

/// Note that the indices are sorted in the definition, but compute_proj

64

/// can take any array and ignores both duplicates and order. Also, it

65

/// follows that i_k must be smaller than or equal to n as x_(i_k) is not

66

/// defined otherwise.

67

1066298

pub fn project(storage: &mut Storage, set: &LddRef, proj: &LddRef) -> Ldd {

68

1066298

    debug_assert_ne!(proj, storage.empty_set(), "proj must be a singleton");

69

70

1066298

    if proj == storage.empty_vector() {

71

        // If meta is not defined then the rest is not in the projection (proj is always zero)

72

109150

        storage.empty_vector().clone()

73

957148

    } else if set == storage.empty_set() {

74

424249

        storage.empty_set().clone()

75

    } else {

76

532899

        debug_assert_ne!(set, storage.empty_vector(), "proj can be at most as high as set");

77

78

532899

        let DataRef(proj_value, proj_down, _) = storage.get_ref(proj);

79

532899

        let DataRef(value, down, right) = storage.get_ref(set);

80

81

532899

        match proj_value {

82

            0 => {

83

236136

                let right_result = project(storage, &right, proj);

84

236136

                let down_result = project(storage, &down, &proj_down);

85

236136

                union(storage, &right_result, &down_result)

86

87

            1 => {

88

296763

                let right_result = project(storage, &right, proj);

89

296763

                let down_result = project(storage, &down, &proj_down);

90

296763

                if down_result == *storage.empty_set() {

91

                    right_result

92

                } else {

93

296763

                    storage.insert(value, &down_result, &right_result)

94

95

96

            x => {

97

                panic!("proj has unexpected value {x}");

98

99

100

101

1066298

102

103

/// Computes a meta LDD from the given read and write projections that is

104

/// suitable for [relational_product].

105

///

106

/// The read and write projections are arrays of indices that are read,

107

/// respectively written, by the corresponding sparse relation.

108

5235

pub fn compute_meta(storage: &mut Storage, read_proj: &[Value], write_proj: &[Value]) -> Ldd {

109

    // Compute length of meta.

110

5235

    let length = cmp::max(

111

5235

        match read_proj.iter().max() {

112

4679

            Some(x) => *x + 1,

113

556

            None => 0,

114

},

115

5235

        match write_proj.iter().max() {

116

4673

            Some(x) => *x + 1,

117

562

            None => 0,

118

},

119

);

120

121

    // Convert projection vectors to meta.

122

5235

    let mut meta: Vec<Value> = Vec::new();

123

51609

    for i in 0..length {

124

51609

        let read = read_proj.contains(&i);

125

51609

        let write = write_proj.contains(&i);

126

127

51609

        if read && write {

128

9925

            meta.push(3);

129

9925

            meta.push(4);

130

41684

        } else if read {

131

11660

            meta.push(1);

132

30024

        } else if write {

133

12140

            meta.push(2);

134

17884

        } else {

135

17884

            meta.push(0);

136

17884

137

138

139

5235

    singleton(storage, &meta)

140

5235

141

142

/// Computes the set of vectors reachable in one step from the given set as defined by the sparse relation rel. Requires that meta = compute_meta(read_proj, write_proj).

143

///

144

/// # Details

145

///

146

/// Formal definition of the function. relational_product(R, S, read_proj, write_proj) = { x[write_proj := y'] | project(x, read_proj) = x' and (x', y') in R and x in S }

147

/// where R is the relation and S the set.

148

///

149

/// meta is a singleton vector where the value indicates the following:

150

///   - 0 = not part the relation.

151

///   - 1 = only in read_proj.

152

///   - 2 = only in write_proj.

153

///   - 3 = in both read_proj and write_proj (read phase).

154

///   - 4 = in both read_proj and write_proj (write phase).

155

5248087

pub fn relational_product(storage: &mut Storage, set: &LddRef, rel: &LddRef, meta: &LddRef) -> Ldd {

156

5248087

    debug_assert_ne!(meta, storage.empty_set(), "proj must be a singleton");

157

158

5248087

    if meta == storage.empty_vector() {

159

        // If meta is not defined then the rest is not in the relation (meta is always zero)

160

105682

        storage.protect(set)

161

5142405

    } else if set == storage.empty_set() || rel == storage.empty_set() {

162

1695129

        storage.empty_set().clone()

163

    } else {

164

3447276

        cache_terniary_op(

165

3447276

            storage,

166

3447276

            TernaryOperator::RelationalProduct,

167

3447276

            set,

168

3447276

            rel,

169

3447276

            meta,

170

2845852

            |storage, set, rel, meta| {

171

2845852

                let DataRef(meta_value, meta_down, _) = storage.get_ref(meta);

172

173

2845852

                match meta_value {

174

                    0 => {

175

                        // Consider all values on this level part of the output and continue with rest.

176

1381440

                        let DataRef(value, down, right) = storage.get_ref(set);

177

178

1381440

                        let right_result = relational_product(storage, &right, rel, meta);

179

1381440

                        let down_result = relational_product(storage, &down, rel, &meta_down);

180

1381440

                        if down_result == *storage.empty_set() {

181

750150

                            right_result

182

                        } else {

183

631290

                            storage.insert(value, &down_result, &right_result)

184

185

186

                    1 => {

187

                        // Read the values present in the relation and continue with these values in the set.

188

312279

                        let DataRef(set_value, set_down, set_right) = storage.get_ref(set);

189

312279

                        let DataRef(rel_value, rel_down, rel_right) = storage.get_ref(rel);

190

191

312279

                        match set_value.cmp(&rel_value) {

192

55980

                            Ordering::Less => relational_product(storage, &set_right, rel, meta),

193

                            Ordering::Equal => {

194

148464

                                let down_result = relational_product(storage, &set_down, &rel_down, &meta_down);

195

148464

                                let right_result = relational_product(storage, &set_right, &rel_right, meta);

196

148464

                                if down_result == *storage.empty_set() {

197

110358

                                    right_result

198

                                } else {

199

38106

                                    storage.insert(set_value, &down_result, &right_result)

200

201

202

107835

                            Ordering::Greater => relational_product(storage, set, &rel_right, meta),

203

204

205

                    2 => {

206

                        // All values in set should be considered.

207

580460

                        let mut combined = storage.empty_set().clone();

208

580460

                        let mut current = storage.protect(set);

209

                        loop {

210

1280022

                            let DataRef(_, set_down, set_right) = storage.get_ref(&current);

211

1280022

                            combined = union(storage, &combined, &set_down);

212

213

1280022

                            if set_right == *storage.empty_set() {

214

580460

                                break;

215

699562

216

699562

                            current = storage.protect(&set_right);

217

218

219

                        // Write the values present in the relation.

220

580460

                        let DataRef(rel_value, rel_down, rel_right) = storage.get_ref(rel);

221

222

580460

                        let down_result = relational_product(storage, &combined, &rel_down, &meta_down);

223

580460

                        let right_result = relational_product(storage, set, &rel_right, meta);

224

580460

                        if down_result == *storage.empty_set() {

225

146242

                            right_result

226

                        } else {

227

434218

                            storage.insert(rel_value, &down_result, &right_result)

228

229

230

                    3 => {

231

443074

                        let DataRef(set_value, set_down, set_right) = storage.get_ref(set);

232

443074

                        let DataRef(rel_value, rel_down, rel_right) = storage.get_ref(rel);

233

234

443074

                        match set_value.cmp(&rel_value) {

235

184160

                            Ordering::Less => relational_product(storage, &set_right, rel, meta),

236

                            Ordering::Equal => {

237

151425

                                let down_result = relational_product(storage, &set_down, &rel_down, &meta_down);

238

151425

                                let right_result = relational_product(storage, &set_right, &rel_right, meta);

239

151425

                                union(storage, &down_result, &right_result)

240

241

107489

                            Ordering::Greater => relational_product(storage, set, &rel_right, meta),

242

243

244

                    4 => {

245

                        // Write the values present in the relation.

246

128599

                        let DataRef(rel_value, rel_down, rel_right) = storage.get_ref(rel);

247

248

128599

                        let down_result = relational_product(storage, set, &rel_down, &meta_down);

249

128599

                        let right_result = relational_product(storage, set, &rel_right, meta);

250

128599

                        if down_result == *storage.empty_set() {

251

68923

                            right_result

252

                        } else {

253

59676

                            storage.insert(rel_value, &down_result, &right_result)

254

255

256

                    x => {

257

                        panic!("meta has unexpected value: {x}");

258

259

260

2845852

},

261

262

263

5248087

264

265

/// Returns the largest subset of 'a' that does not contains elements of 'b', i.e., set difference.

266

558822

pub fn minus(storage: &mut Storage, a: &LddRef, b: &LddRef) -> Ldd {

267

558822

    if a == b || a == storage.empty_set() {

268

156308

        storage.empty_set().clone()

269

402514

    } else if b == storage.empty_set() {

270

14318

        storage.protect(a)

271

    } else {

272

388196

        cache_binary_op(storage, BinaryOperator::Minus, a, b, |storage, a, b| {

273

320000

            let DataRef(a_value, a_down, a_right) = storage.get_ref(a);

274

320000

            let DataRef(b_value, b_down, b_right) = storage.get_ref(b);

275

276

320000

            match a_value.cmp(&b_value) {

277

                Ordering::Less => {

278

17093

                    let right_result = minus(storage, &a_right, b);

279

17093

                    storage.insert(a_value, &a_down, &right_result)

280

281

                Ordering::Equal => {

282

237336

                    let down_result = minus(storage, &a_down, &b_down);

283

237336

                    let right_result = minus(storage, &a_right, &b_right);

284

237336

                    if down_result == *storage.empty_set() {

285

91425

                        right_result

286

                    } else {

287

145911

                        storage.insert(a_value, &down_result, &right_result)

288

289

290

65571

                Ordering::Greater => minus(storage, a, &b_right),

291

292

320000

})

293

294

558822

295

296

/// Returns the union of the given LDDs, i.e., a ∪ b.

297

8348392

pub fn union(storage: &mut Storage, a: &LddRef, b: &LddRef) -> Ldd {

298

8348392

    if a == b {

299

883633

        storage.protect(a)

300

7464759

    } else if a == storage.empty_set() {

301

1210149

        storage.protect(b)

302

6254610

    } else if b == storage.empty_set() {

303

915117

        storage.protect(a)

304

    } else {

305

5339493

        cache_comm_binary_op(storage, BinaryOperator::Union, a, b, |storage, a, b| {

306

4529800

            let DataRef(a_value, a_down, a_right) = storage.get_ref(a);

307

4529800

            let DataRef(b_value, b_down, b_right) = storage.get_ref(b);

308

309

4529800

            match a_value.cmp(&b_value) {

310

                Ordering::Less => {

311

2174595

                    let result = union(storage, &a_right, b);

312

2174595

                    storage.insert(a_value, &a_down, &result)

313

314

                Ordering::Equal => {

315

1704757

                    let down_result = union(storage, &a_down, &b_down);

316

1704757

                    let right_result = union(storage, &a_right, &b_right);

317

1704757

                    storage.insert(a_value, &down_result, &right_result)

318

319

                Ordering::Greater => {

320

650448

                    let result = union(storage, a, &b_right);

321

650448

                    storage.insert(b_value, &b_down, &result)

322

323

324

4529800

})

325

326

8348392

327

328

/// Interleave the vectors of two equal height ldds.

329

3030276

pub fn merge(storage: &mut Storage, a: &LddRef, b: &LddRef) -> Ldd {

330

3030276

    if a == storage.empty_vector() {

331

        storage.protect(b)

332

3030276

    } else if b == storage.empty_vector() {

333

37503

        storage.protect(a)

334

2992773

    } else if a == storage.empty_set() || b == storage.empty_set() {

335

1412788

        storage.empty_set().clone()

336

    } else {

337

1579985

        cache_binary_op(storage, BinaryOperator::Merge, a, b, |storage, a, b| {

338

1515088

            let DataRef(value, down, right) = storage.get_ref(a);

339

340

1515088

            let down_result = merge(storage, b, &down);

341

1515088

            let right_result = merge(storage, &right, b);

342

343

1515088

            storage.insert(value, &down_result, &right_result)

344

1515088

})

345

346

3030276

347

348

/// Appends the given value to every vector in the set represented by the given ldd.

349

58538

pub fn append(storage: &mut Storage, ldd: &LddRef, value: Value) -> Ldd {

350

58538

    if ldd == storage.empty_set() {

351

26119

        storage.empty_set().clone()

352

32419

    } else if ldd == storage.empty_vector() {

353

3200

        singleton(storage, &[value])

354

    } else {

355

        // Traverse the ldd.

356

29219

        let DataRef(val, down, right) = storage.get_ref(ldd);

357

358

29219

        let down_result = append(storage, &down, value);

359

29219

        let right_result = append(storage, &right, value);

360

361

29219

        storage.insert(val, &down_result, &right_result)

362

363

58538

364

365

/// Returns true iff the set contains the vector.

366

129863

pub fn element_of(storage: &Storage, vector: &[Value], ldd: &Ldd) -> bool {

367

129863

    if vector.is_empty() {

368

10836

        ldd == storage.empty_vector()

369

119027

    } else if ldd == storage.empty_vector() {

370

        false

371

    } else {

372

192613

        for Data(value, down, _) in iter_right(storage, ldd) {

373

192613

            match value.cmp(&vector[0]) {

374

                Ordering::Less => {

375

74571

                    continue;

376

377

                Ordering::Equal => {

378

116244

                    return element_of(storage, &vector[1..], &down);

379

380

                Ordering::Greater => {

381

1798

                    return false;

382

383

384

385

386

985

        false

387

388

129863

389

390

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

391

95587

pub fn len(storage: &mut Storage, set: &LddRef) -> usize {

392

95587

    if set == storage.empty_set() {

393

394

95587

    } else if set == storage.empty_vector() {

395

2530

396

    } else {

397

93057

        cache_unary_function(storage, UnaryFunction::Len, set, |storage, a| {

398

60725

            let mut result: usize = 0;

399

400

60725

            let mut current = storage.protect(a);

401

155906

            while current != *storage.empty_set() {

402

95181

                // Progress to the right LDD.

403

95181

                let DataRef(_, down, right) = storage.get_ref(&current);

404

95181

                result += len(storage, &down);

405

95181

                current = storage.protect(&right);

406

95181

407

408

60725

            result

409

60725

})

410

411

95587

412

413

/// Returns the height of the LDD tree.

414

107684720

pub fn height(storage: &Storage, ldd: &LddRef) -> usize {

415

107684720

    if ldd == storage.empty_set() || ldd == storage.empty_vector() {

416

9177448

417

    } else {

418

        // Since all children have the same height we only have to look at the down node.

419

98507272

        let DataRef(_, down, _) = storage.get_ref(ldd);

420

421

98507272

        height(storage, &down) + 1

422

423

107684720

424

425

#[cfg(test)]

426

mod tests {

427

    use super::*;

428

429

    use std::collections::HashSet;

430

    use std::ops::Sub;

431

432

    use rand::RngExt;

433

    use streaming_iterator::StreamingIterator;

434

435

    use merc_utilities::random_test;

436

437

    use crate::LddDisplay;

438

    use crate::test_utility::*;

439

440

    // Compare the LDD element_of implementation for random inputs.

441

    #[test]

442

    #[cfg_attr(miri, ignore)]

443

1

    fn test_random_element_of() {

444

100

        random_test(100, |rng| {

445

100

            let mut storage = Storage::new();

446

447

100

            let length = 10;

448

100

            let set = random_vector_set(rng, 32, length, 10);

449

100

            let ldd = from_iter(&mut storage, set.iter());

450

451

            // All elements in the set should be contained in the ldd.

452

3200

            for expected in &set {

453

3200

                assert!(

454

3200

                    element_of(&storage, expected, &ldd),

455

                    "Did not find expected vector in ldd"

456

);

457

458

459

            // No shorter vectors should be contained in the ldd (try several times).

460

100

            for _ in 0..10 {

461

1000

                let len = rng.random_range(0..length);

462

1000

                let short_vector = random_vector(rng, len, 10);

463

1000

                assert!(

464

1000

                    !element_of(&storage, &short_vector, &ldd),

465

                    "Found shorter vector in ldd."

466

);

467

468

469

            // No longer vectors should be contained in the ldd.

470

100

            for _ in 0..10 {

471

1000

                let len = rng.random_range(length + 1..20);

472

1000

                let short_vector = random_vector(rng, len, 10);

473

1000

                assert!(!element_of(&storage, &short_vector, &ldd), "Found longer vector in ldd");

474

475

476

            // Try vectors of correct size with both the set and ldd.

477

100

            for _ in 0..10 {

478

1000

                let vector = random_vector(rng, length, 10);

479

1000

                assert_eq!(

480

1000

                    set.contains(&vector),

481

1000

                    element_of(&storage, &vector, &ldd),

482

                    "Set contains did not match ldd element_of"

483

);

484

485

100

});

486

1

487

488

    // Compare the HashSet implementation of union with the LDD union implementation for random inputs.

489

    #[test]

490

    #[cfg_attr(miri, ignore)]

491

1

    fn test_random_union() {

492

100

        random_test(100, |rng| {

493

100

            let mut storage = Storage::new();

494

495

100

            let set_a = random_vector_set(rng, 32, 10, 10);

496

100

            let set_b = random_vector_set(rng, 32, 10, 10);

497

100

            let expected = from_iter(&mut storage, set_a.union(&set_b));

498

499

100

            let a = from_iter(&mut storage, set_a.iter());

500

100

            let b = from_iter(&mut storage, set_b.iter());

501

100

            let result = union(&mut storage, &a, &b);

502

503

100

            assert_eq!(result, expected);

504

100

});

505

1

506

507

    #[test]

508

    #[cfg_attr(miri, ignore)]

509

1

    fn test_random_merge() {

510

100

        random_test(100, |rng| {

511

100

            let mut storage = Storage::new();

512

513

100

            let set_a = random_vector_set(rng, 32, 10, 10);

514

100

            let set_b = random_vector_set(rng, 32, 10, 10);

515

516

            // Compute the interleave explicitly.

517

102400

            fn interleave(a: &[u32], b: &[u32]) -> Vec<u32> {

518

102400

                let mut result = vec![];

519

520

102400

                let mut iter = b.iter();

521

1024000

                for value in a {

522

1024000

                    result.push(*value);

523

1024000

                    result.push(*iter.next().unwrap());

524

1024000

525

526

102400

                result

527

102400

528

529

100

            let mut set_result = HashSet::<Vec<u32>>::new();

530

3200

            for a in &set_a {

531

102400

                for b in &set_b {

532

102400

                    set_result.insert(interleave(a, b));

533

102400

534

535

536

100

            let expected = from_iter(&mut storage, set_result.iter());

537

538

100

            let a = from_iter(&mut storage, set_a.iter());

539

100

            let b = from_iter(&mut storage, set_b.iter());

540

100

            let result: Ldd = merge(&mut storage, &a, &b);

541

542

100

            assert_eq!(result, expected);

543

100

});

544

1

545

546

    // Compare the singleton implementation with a random vector used as input.

547

    #[test]

548

    #[cfg_attr(miri, ignore)]

549

1

    fn test_random_singleton() {

550

100

        random_test(100, |rng| {

551

100

            let mut storage = Storage::new();

552

100

            let vector = random_vector(rng, 10, 10);

553

554

100

            let ldd = singleton(&mut storage, &vector[..]);

555

556

            // Check that ldd contains exactly one vector that is equal to the initial vector.

557

100

            let mut it = iter(&storage, &ldd);

558

100

            let result = it.next().unwrap();

559

100

            assert_eq!(vector, *result, "Contained vector did not match expected");

560

100

            assert_eq!(it.next(), None, "The ldd should not contain any other vector");

561

100

});

562

1

563

564

    // Test the len function with random inputs.

565

    #[test]

566

    #[cfg_attr(miri, ignore)]

567

1

    fn test_random_len() {

568

100

        random_test(100, |rng| {

569

100

            let mut storage = Storage::new();

570

571

100

            let set = random_vector_set(rng, 32, 10, 10);

572

100

            let ldd = from_iter(&mut storage, set.iter());

573

574

100

            assert_eq!(set.len(), len(&mut storage, &ldd), "Length did not match expected set");

575

100

});

576

1

577

578

    // Test the minus function with random inputs.

579

    #[test]

580

    #[cfg_attr(miri, ignore)]

581

1

    fn test_random_minus() {

582

100

        random_test(100, |rng| {

583

100

            let mut storage = Storage::new();

584

585

100

            let set_a = random_vector_set(rng, 32, 10, 10);

586

100

            let set_b = {

587

100

                let mut result = random_vector_set(rng, 32, 10, 10);

588

589

                // To ensure some overlap (which is unlikely) we insert some elements of a into b.

590

100

                let mut it = set_a.iter();

591

1600

                for _ in 0..16 {

592

1600

                    result.insert(it.next().unwrap().clone());

593

1600

594

595

100

                result

596

};

597

598

100

            let expected_result = set_a.sub(&set_b);

599

600

100

            let a = from_iter(&mut storage, set_a.iter());

601

100

            let b = from_iter(&mut storage, set_b.iter());

602

100

            let result = minus(&mut storage, &a, &b);

603

604

100

            let expected = from_iter(&mut storage, expected_result.iter());

605

606

100

            println!("{}", LddDisplay::new(&storage, &result));

607

100

            println!("{}", LddDisplay::new(&storage, &expected));

608

609

100

            assert_eq!(result, expected);

610

100

});

611

1

612

613

    // Test the relational product function with read-only inputs.

614

    #[test]

615

    #[cfg_attr(miri, ignore)]

616

1

    fn test_random_readonly_relational_product() {

617

100

        random_test(100, |rng| {

618

100

            let mut storage = Storage::new();

619

100

            let set = random_vector_set(rng, 32, 10, 10);

620

621

100

            let ldd = from_iter(&mut storage, set.iter());

622

623

100

            let read_proj = random_sorted_vector(rng, 4, 9);

624

100

            let meta = compute_meta(&mut storage, &read_proj, &[]);

625

626

100

            let proj_ldd = compute_proj(&mut storage, &read_proj);

627

100

            let relation = project(&mut storage, &ldd, &proj_ldd);

628

629

100

            let result = relational_product(&mut storage, &ldd, &relation, &meta);

630

100

            let read_project = project(&mut storage, &result, &proj_ldd);

631

632

            // relational_product(R, S, read_proj, []) = { x | project(x, read_proj) = x' and (x', <>) in R and x in S }

633

100

            assert_eq!(read_project, relation);

634

100

});

635

1

636

637

    // Test the relational product function with write-only inputs.

638

    #[test]

639

    #[cfg_attr(miri, ignore)]

640

1

    fn test_random_writeonly_relational_product() {

641

100

        random_test(100, |rng| {

642

100

            let mut storage = Storage::new();

643

100

            let set = random_vector_set(rng, 32, 10, 10);

644

645

100

            let ldd = from_iter(&mut storage, set.iter());

646

647

100

            let write_proj = random_sorted_vector(rng, 4, 9);

648

100

            let meta = compute_meta(&mut storage, &[], &write_proj);

649

650

100

            let proj_ldd = compute_proj(&mut storage, &write_proj);

651

100

            let relation = project(&mut storage, &ldd, &proj_ldd);

652

653

100

            let result = relational_product(&mut storage, &ldd, &relation, &meta);

654

100

            let write_project = project(&mut storage, &result, &proj_ldd);

655

656

            // relational_product(R, S, [], write_proj) = { x[write_proj := y'] | (<>, y') in R and x in S }

657

100

            assert_eq!(write_project, relation);

658

100

});

659

1

660

661

    #[test]

662

    #[cfg_attr(miri, ignore)]

663

1

    fn test_random_relational_product() {

664

100

        random_test(100, |rng| {

665

100

            let mut storage = Storage::new();

666

667

100

            let set = random_vector_set(rng, 32, 10, 10);

668

100

            let relation = random_vector_set(rng, 32, 4, 10);

669

670

            // Pick arbitrary read and write parameters in order.

671

100

            let read_proj = random_sorted_vector(rng, 2, 9);

672

100

            let write_proj = random_sorted_vector(rng, 2, 9);

673

674

            // The indices of the input vectors do not match the indices in the relation. The input vector is defined for all values, but the relation only

675

            // for relevant positions.

676

100

            let (read_rel_proj, write_rel_proj) = {

677

100

                let mut read_rel_proj: Vec<Value> = Vec::new();

678

100

                let mut write_rel_proj: Vec<Value> = Vec::new();

679

680

100

                let mut current = 0;

681

1000

                for i in 0..10 {

682

1000

                    if read_proj.contains(&i) {

683

200

                        read_rel_proj.push(current);

684

200

                        current += 1;

685

800

686

687

1000

                    if write_proj.contains(&i) {

688

200

                        write_rel_proj.push(current);

689

200

                        current += 1;

690

800

691

692

693

100

                (read_rel_proj, write_rel_proj)

694

};

695

696

            // Compute LDD result.

697

100

            let ldd = from_iter(&mut storage, set.iter());

698

100

            let rel = from_iter(&mut storage, relation.iter());

699

700

100

            let meta = compute_meta(&mut storage, &read_proj, &write_proj);

701

100

            let result = relational_product(&mut storage, &ldd, &rel, &meta);

702

703

100

            eprintln!("set = {}", LddDisplay::new(&storage, &ldd));

704

100

            eprintln!("relation = {}", LddDisplay::new(&storage, &rel));

705

100

            eprintln!("result = {}", LddDisplay::new(&storage, &result));

706

100

            eprintln!("========");

707

708

100

            eprintln!("meta = {}", LddDisplay::new(&storage, &meta));

709

100

            eprintln!(

710

                "read {:?}, write {:?}, read_rel {:?} and write_rel {:?}",

711

                read_proj, write_proj, read_rel_proj, write_rel_proj

712

);

713

714

100

            let expected = {

715

100

                let mut expected: HashSet<Vec<Value>> = HashSet::new();

716

717

                // Compute relational_product(R, S, read_proj, write_proj) = { x[write_proj := y'] | project(x, read_proj) = x' and (x', y') in R and x in S }

718

3200

                for x in set.iter() {

719

102272

                    'next: for rel in relation.iter() {

720

102272

                        let mut value = x.clone(); // The resulting vector.

721

102272

                        let x_prime = project_vector(rel, &read_rel_proj);

722

102272

                        let y_prime = project_vector(rel, &write_rel_proj);

723

724

                        // Ensure that project(x, read_proj) = x'

725

112489

                        for (i, r) in read_proj.iter().enumerate() {

726

112489

                            if value[*r as usize] != x_prime[i] {

727

101253

                                continue 'next;

728

11236

729

730

731

                        // Compute x[write_proj := y']

732

2038

                        for (i, w) in write_proj.iter().enumerate() {

733

2038

                            value[*w as usize] = y_prime[i];

734

2038

735

736

                        // Print information about the value that we are testing.

737

1019

                        eprintln!("value = {:?}, rel = {:?}", &value, &rel);

738

1019

                        eprintln!("x_prime = {:?}, y_prime = {:?}", &x_prime, &y_prime);

739

740

1019

                        assert!(

741

1019

                            element_of(&storage, &value, &result),

742

                            "Result does not contain vector {:?}.",

743

                            &value

744

);

745

1019

                        expected.insert(value);

746

747

748

749

100

                expected

750

};

751

752

            // Check the other way around

753

100

            let mut iter = iter(&storage, &result);

754

1119

            while let Some(res) = iter.next() {

755

1019

                assert!(expected.contains(res), "Result unexpectedly contains vector {:?}.", res);

756

757

100

});

758

1

759

760

    // Test the project function with random inputs.

761

    #[test]

762

    #[cfg_attr(miri, ignore)]

763

1

    fn test_random_project() {

764

100

        random_test(100, |rng| {

765

100

            let mut storage = Storage::new();

766

767

100

            let set = random_vector_set(rng, 32, 10, 10);

768

100

            let proj = random_sorted_vector(rng, 4, 9);

769

770

100

            let ldd = from_iter(&mut storage, set.iter());

771

100

            let proj_ldd = compute_proj(&mut storage, &proj);

772

100

            let result = project(&mut storage, &ldd, &proj_ldd);

773

774

            // Compute a naive projection on the vector set.

775

100

            let mut expected_result: HashSet<Vec<Value>> = HashSet::new();

776

3200

            for element in &set {

777

3200

                expected_result.insert(project_vector(element, &proj));

778

3200

779

100

            let expected = from_iter(&mut storage, expected_result.iter());

780

100

            assert_eq!(result, expected, "projected result does not match vector projection.");

781

100

});

782

1

783

784

    // Test the append function with random inputs.

785

    #[test]

786

    #[cfg_attr(miri, ignore)]

787

1

    fn test_random_append() {

788

100

        random_test(100, |rng| {

789

100

            let mut storage = Storage::new();

790

791

100

            let set = random_vector_set(rng, 32, 10, 10);

792

100

            let ldd = from_iter(&mut storage, set.iter());

793

100

            let result = append(&mut storage, &ldd, 0);

794

795

100

            let mut expected_result: HashSet<Vec<Value>> = HashSet::new();

796

3200

            for element in &set {

797

3200

                let mut appended = element.to_vec();

798

3200

                appended.push(0 as Value);

799

3200

                expected_result.insert(appended);

800

3200

801

100

            let expected = from_iter(&mut storage, expected_result.iter());

802

803

100

            print_differences(&storage, &result, &expected);

804

100

            assert_eq!(result, expected, "appended result does not match vector append");

805

100

});

806

1

807