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

324892

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

21

324892

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

22

324892

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

23

4117818

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

24

4117818

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

25

4117818

26

27

324892

    root

28

324892

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

2398

    for i in 0..length {

45

2398

        let included = proj.contains(&i);

46

47

2398

        if included {

48

1200

            result.push(1);

49

1200

        } else {

50

1198

            result.push(0);

51

1198

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

715482

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

68

715482

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

69

70

715482

    if proj == storage.empty_vector() {

71

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

72

35005

        storage.empty_vector().clone()

73

680477

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

74

261865

        storage.empty_set().clone()

75

    } else {

76

418612

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

77

78

418612

        cache_binary_op(storage, BinaryOperator::Project, set, proj, |storage, set, proj| {

79

357491

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

80

357491

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

81

82

357491

            match proj_value {

83

                0 => {

84

165042

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

85

165042

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

86

165042

                    union(storage, &right_result, &down_result)

87

88

                1 => {

89

192449

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

90

192449

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

91

192449

                    if down_result == *storage.empty_set() {

92

                        right_result

93

                    } else {

94

192449

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

95

96

97

                x => {

98

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

99

100

101

357491

})

102

103

715482

104

105

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

106

/// suitable for [relational_product].

107

///

108

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

109

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

110

5295

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

111

    // Compute length of meta.

112

5295

    let length = cmp::max(

113

5295

        match read_proj.iter().max() {

114

4721

            Some(x) => *x + 1,

115

574

            None => 0,

116

},

117

5295

        match write_proj.iter().max() {

118

4742

            Some(x) => *x + 1,

119

553

            None => 0,

120

},

121

);

122

123

    // Convert projection vectors to meta.

124

5295

    let mut read_positions = Vec::new();

125

5295

    let mut write_positions = Vec::new();

126

127

5295

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

128

129

5295

    let mut offset = 0;

130

51741

    for i in 0..length {

131

51741

        let read = read_proj.contains(&i);

132

51741

        let write = write_proj.contains(&i);

133

51741

        if read && write {

134

10072

            meta.push(3);

135

10072

            meta.push(4);

136

10072

            read_positions.push(offset);

137

10072

            write_positions.push(offset + 1);

138

10072

            offset += 2;

139

41669

        } else if read {

140

11882

            meta.push(1);

141

11882

            read_positions.push(offset);

142

11882

            offset += 1;

143

29787

        } else if write {

144

12059

            meta.push(2);

145

12059

            write_positions.push(offset);

146

12059

            offset += 1;

147

17728

        } else {

148

17728

            meta.push(0);

149

17728

150

151

152

5295

    (singleton(storage, &meta), read_positions, write_positions)

153

5295

154

155

/// 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).

156

///

157

/// # Details

158

///

159

/// 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 }

160

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

161

///

162

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

163

///   - 0 = not part the relation.

164

///   - 1 = only in read_proj.

165

///   - 2 = only in write_proj.

166

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

167

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

168

7191342

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

169

7191342

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

170

171

7191342

    if meta == storage.empty_vector() {

172

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

173

147557

        storage.protect(set)

174

7043785

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

175

2393755

        storage.empty_set().clone()

176

    } else {

177

4650030

        cache_terniary_op(

178

4650030

            storage,

179

4650030

            TernaryOperator::RelationalProduct,

180

4650030

            set,

181

4650030

            rel,

182

4650030

            meta,

183

3890209

            |storage, set, rel, meta| {

184

3890209

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

185

186

3890209

                match meta_value {

187

                    0 => {

188

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

189

1746661

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

190

191

1746661

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

192

1746661

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

193

1746661

                        if down_result == *storage.empty_set() {

194

870975

                            right_result

195

                        } else {

196

875686

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

197

198

199

                    1 => {

200

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

201

408462

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

202

408462

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

203

204

408462

                        match set_value.cmp(&rel_value) {

205

88830

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

206

                            Ordering::Equal => {

207

179918

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

208

179918

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

209

179918

                                if down_result == *storage.empty_set() {

210

137629

                                    right_result

211

                                } else {

212

42289

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

213

214

215

139714

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

216

217

218

                    2 => {

219

                        // All values in set should be considered.

220

985349

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

221

985349

                        let mut current = storage.protect(set);

222

                        loop {

223

2225703

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

224

2225703

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

225

226

2225703

                            if set_right == *storage.empty_set() {

227

985349

                                break;

228

1240354

229

1240354

                            current = storage.protect(&set_right);

230

231

232

                        // Write the values present in the relation.

233

985349

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

234

235

985349

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

236

985349

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

237

985349

                        if down_result == *storage.empty_set() {

238

280973

                            right_result

239

                        } else {

240

704376

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

241

242

243

                    3 => {

244

577027

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

245

577027

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

246

247

577027

                        match set_value.cmp(&rel_value) {

248

244412

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

249

                            Ordering::Equal => {

250

190608

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

251

190608

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

252

190608

                                union(storage, &down_result, &right_result)

253

254

142007

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

255

256

257

                    4 => {

258

                        // Write the values present in the relation.

259

172710

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

260

261

172710

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

262

172710

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

263

172710

                        if down_result == *storage.empty_set() {

264

92075

                            right_result

265

                        } else {

266

80635

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

267

268

269

                    x => {

270

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

271

272

273

3890209

},

274

275

276

7191342

277

278

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

279

890312

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

280

890312

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

281

260294

        storage.empty_set().clone()

282

630018

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

283

19949

        storage.protect(a)

284

    } else {

285

610069

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

286

503248

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

287

503248

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

288

289

503248

            match a_value.cmp(&b_value) {

290

                Ordering::Less => {

291

32873

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

292

32873

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

293

294

                Ordering::Equal => {

295

382770

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

296

382770

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

297

382770

                    if down_result == *storage.empty_set() {

298

163250

                        right_result

299

                    } else {

300

219520

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

301

302

303

87605

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

304

305

503248

})

306

307

890312

308

309

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

310

9569193

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

311

9569193

    if a == b {

312

1118435

        storage.protect(a)

313

8450758

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

314

1618089

        storage.protect(b)

315

6832669

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

316

820748

        storage.protect(a)

317

    } else {

318

6011921

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

319

4665114

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

320

4665114

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

321

322

4665114

            match a_value.cmp(&b_value) {

323

                Ordering::Less => {

324

1927067

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

325

1927067

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

326

327

                Ordering::Equal => {

328

1946504

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

329

1946504

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

330

1946504

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

331

332

                Ordering::Greater => {

333

791543

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

334

791543

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

335

336

337

4665114

})

338

339

9569193

340

341

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

342

3032768

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

343

3032768

    if a == storage.empty_vector() {

344

        storage.protect(b)

345

3032768

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

346

37207

        storage.protect(a)

347

2995561

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

348

1414034

        storage.empty_set().clone()

349

    } else {

350

1581527

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

351

1516334

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

352

353

1516334

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

354

1516334

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

355

356

1516334

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

357

1516334

})

358

359

3032768

360

361

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

362

58550

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

363

58550

    if ldd == storage.empty_set() {

364

26125

        storage.empty_set().clone()

365

32425

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

366

3200

        singleton(storage, &[value])

367

    } else {

368

        // Traverse the ldd.

369

29225

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

370

371

29225

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

372

29225

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

373

374

29225

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

375

376

58550

377

378

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

379

130241

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

380

130241

    if vector.is_empty() {

381

10873

        ldd == storage.empty_vector()

382

119368

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

383

        false

384

    } else {

385

193390

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

386

193390

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

387

                Ordering::Less => {

388

75005

                    continue;

389

390

                Ordering::Equal => {

391

116591

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

392

393

                Ordering::Greater => {

394

1794

                    return false;

395

396

397

398

399

983

        false

400

401

130241

402

403

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

404

192008

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

405

192008

    if set == storage.empty_set() {

406

407

192008

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

408

4402

409

    } else {

410

187606

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

411

118944

            let mut result: usize = 0;

412

413

118944

            let mut current = storage.protect(a);

414

309925

            while current != *storage.empty_set() {

415

190981

                // Progress to the right LDD.

416

190981

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

417

190981

                result += len(storage, &down);

418

190981

                current = storage.protect(&right);

419

190981

420

421

118944

            result

422

118944

})

423

424

192008

425

426

/// Returns the height of the LDD tree.

427

106460888

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

428

106460888

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

429

9554100

430

    } else {

431

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

432

96906788

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

433

434

96906788

        height(storage, &down) + 1

435

436

106460888

437

438

#[cfg(test)]

439

mod tests {

440

    use super::*;

441

442

    use std::collections::HashSet;

443

    use std::ops::Sub;

444

445

    use rand::RngExt;

446

    use streaming_iterator::StreamingIterator;

447

448

    use merc_utilities::random_test;

449

450

    use crate::LddDisplay;

451

    use crate::test_utility::*;

452

453

    // Compare the LDD element_of implementation for random inputs.

454

    #[test]

455

    #[cfg_attr(miri, ignore)]

456

1

    fn test_random_element_of() {

457

100

        random_test(100, |rng| {

458

100

            let mut storage = Storage::new();

459

460

100

            let length = 10;

461

100

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

462

100

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

463

464

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

465

3200

            for expected in &set {

466

3200

                assert!(

467

3200

                    element_of(&storage, expected, &ldd),

468

                    "Did not find expected vector in ldd"

469

);

470

471

472

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

473

100

            for _ in 0..10 {

474

1000

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

475

1000

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

476

1000

                assert!(

477

1000

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

478

                    "Found shorter vector in ldd."

479

);

480

481

482

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

483

100

            for _ in 0..10 {

484

1000

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

485

1000

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

486

1000

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

487

488

489

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

490

100

            for _ in 0..10 {

491

1000

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

492

1000

                assert_eq!(

493

1000

                    set.contains(&vector),

494

1000

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

495

                    "Set contains did not match ldd element_of"

496

);

497

498

100

});

499

1

500

501

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

502

    #[test]

503

    #[cfg_attr(miri, ignore)]

504

1

    fn test_random_union() {

505

100

        random_test(100, |rng| {

506

100

            let mut storage = Storage::new();

507

508

100

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

509

100

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

510

100

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

511

512

100

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

513

100

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

514

100

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

515

516

100

            assert_eq!(result, expected);

517

100

});

518

1

519

520

    #[test]

521

    #[cfg_attr(miri, ignore)]

522

1

    fn test_random_merge() {

523

100

        random_test(100, |rng| {

524

100

            let mut storage = Storage::new();

525

526

100

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

527

100

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

528

529

            // Compute the interleave explicitly.

530

102400

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

531

102400

                let mut result = vec![];

532

533

102400

                let mut iter = b.iter();

534

1024000

                for value in a {

535

1024000

                    result.push(*value);

536

1024000

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

537

1024000

538

539

102400

                result

540

102400

541

542

100

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

543

3200

            for a in &set_a {

544

102400

                for b in &set_b {

545

102400

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

546

102400

547

548

549

100

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

550

551

100

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

552

100

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

553

100

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

554

555

100

            assert_eq!(result, expected);

556

100

});

557

1

558

559

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

560

    #[test]

561

    #[cfg_attr(miri, ignore)]

562

1

    fn test_random_singleton() {

563

100

        random_test(100, |rng| {

564

100

            let mut storage = Storage::new();

565

100

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

566

567

100

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

568

569

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

570

100

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

571

100

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

572

100

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

573

100

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

574

100

});

575

1

576

577

    // Test the len function with random inputs.

578

    #[test]

579

    #[cfg_attr(miri, ignore)]

580

1

    fn test_random_len() {

581

100

        random_test(100, |rng| {

582

100

            let mut storage = Storage::new();

583

584

100

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

585

100

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

586

587

100

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

588

100

});

589

1

590

591

    // Test the minus function with random inputs.

592

    #[test]

593

    #[cfg_attr(miri, ignore)]

594

1

    fn test_random_minus() {

595

100

        random_test(100, |rng| {

596

100

            let mut storage = Storage::new();

597

598

100

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

599

100

            let set_b = {

600

100

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

601

602

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

603

100

                let mut it = set_a.iter();

604

1600

                for _ in 0..16 {

605

1600

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

606

1600

607

608

100

                result

609

};

610

611

100

            let expected_result = set_a.sub(&set_b);

612

613

100

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

614

100

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

615

100

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

616

617

100

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

618

619

100

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

620

100

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

621

622

100

            assert_eq!(result, expected);

623

100

});

624

1

625

626

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

627

    #[test]

628

    #[cfg_attr(miri, ignore)]

629

1

    fn test_random_readonly_relational_product() {

630

100

        random_test(100, |rng| {

631

100

            let mut storage = Storage::new();

632

100

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

633

634

100

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

635

636

100

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

637

100

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

638

639

100

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

640

100

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

641

642

100

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

643

100

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

644

645

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

646

100

            assert_eq!(read_project, relation);

647

100

});

648

1

649

650

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

651

    #[test]

652

    #[cfg_attr(miri, ignore)]

653

1

    fn test_random_writeonly_relational_product() {

654

100

        random_test(100, |rng| {

655

100

            let mut storage = Storage::new();

656

100

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

657

658

100

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

659

660

100

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

661

100

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

662

663

100

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

664

100

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

665

666

100

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

667

100

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

668

669

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

670

100

            assert_eq!(write_project, relation);

671

100

});

672

1

673

674

    #[test]

675

    #[cfg_attr(miri, ignore)]

676

1

    fn test_random_relational_product() {

677

100

        random_test(100, |rng| {

678

100

            let mut storage = Storage::new();

679

680

100

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

681

100

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

682

683

            // Pick arbitrary read and write parameters in order.

684

100

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

685

100

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

686

687

            // 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

688

            // for relevant positions.

689

100

            let (read_rel_proj, write_rel_proj) = {

690

100

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

691

100

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

692

693

100

                let mut current = 0;

694

1000

                for i in 0..10 {

695

1000

                    if read_proj.contains(&i) {

696

200

                        read_rel_proj.push(current);

697

200

                        current += 1;

698

800

699

700

1000

                    if write_proj.contains(&i) {

701

200

                        write_rel_proj.push(current);

702

200

                        current += 1;

703

800

704

705

706

100

                (read_rel_proj, write_rel_proj)

707

};

708

709

            // Compute LDD result.

710

100

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

711

100

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

712

713

100

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

714

100

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

715

716

100

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

717

100

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

718

100

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

719

100

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

720

721

100

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

722

100

            eprintln!(

723

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

724

                read_proj, write_proj, read_rel_proj, write_rel_proj

725

);

726

727

100

            let expected = {

728

100

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

729

730

                // 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 }

731

3200

                for x in set.iter() {

732

102240

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

733

102240

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

734

102240

                        let x_prime = project_vector(rel, &read_rel_proj);

735

102240

                        let y_prime = project_vector(rel, &write_rel_proj);

736

737

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

738

112580

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

739

112580

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

740

101190

                                continue 'next;

741

11390

742

743

744

                        // Compute x[write_proj := y']

745

2100

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

746

2100

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

747

2100

748

749

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

750

1050

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

751

1050

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

752

753

1050

                        assert!(

754

1050

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

755

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

756

                            &value

757

);

758

1050

                        expected.insert(value);

759

760

761

762

100

                expected

763

};

764

765

            // Check the other way around

766

100

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

767

1150

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

768

1050

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

769

770

100

});

771

1

772

773

    // Test the project function with random inputs.

774

    #[test]

775

    #[cfg_attr(miri, ignore)]

776

1

    fn test_random_project() {

777

100

        random_test(100, |rng| {

778

100

            let mut storage = Storage::new();

779

780

100

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

781

100

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

782

783

100

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

784

100

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

785

100

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

786

787

            // Compute a naive projection on the vector set.

788

100

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

789

3200

            for element in &set {

790

3200

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

791

3200

792

100

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

793

100

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

794

100

});

795

1

796

797

    // Test the append function with random inputs.

798

    #[test]

799

    #[cfg_attr(miri, ignore)]

800

1

    fn test_random_append() {

801

100

        random_test(100, |rng| {

802

100

            let mut storage = Storage::new();

803

804

100

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

805

100

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

806

100

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

807

808

100

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

809

3200

            for element in &set {

810

3200

                let mut appended = element.to_vec();

811

3200

                appended.push(0 as Value);

812

3200

                expected_result.insert(appended);

813

3200

814

100

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

815

816

100

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

817

100

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

818

100

});

819

1

820