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

253856

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

21

253856

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

22

253856

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

23

3485363

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

24

3485363

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

25

3485363

26

27

253856

    root

28

253856

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

2410

    for i in 0..length {

45

2410

        let included = proj.contains(&i);

46

47

2410

        if included {

48

1200

            result.push(1);

49

1210

        } else {

50

1210

            result.push(0);

51

1210

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

1118862

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

68

1118862

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

69

70

1118862

    if proj == storage.empty_vector() {

71

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

72

112193

        storage.empty_vector().clone()

73

1006669

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

74

447488

        storage.empty_set().clone()

75

    } else {

76

559181

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

77

78

559181

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

79

559181

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

80

81

559181

        match proj_value {

82

            0 => {

83

258512

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

84

258512

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

85

258512

                union(storage, &right_result, &down_result)

86

87

            1 => {

88

300669

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

89

300669

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

90

300669

                if down_result == *storage.empty_set() {

91

                    right_result

92

                } else {

93

300669

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

94

95

96

            x => {

97

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

98

99

100

101

1118862

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

377

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

109

    // Compute length of meta.

110

377

    let length = cmp::max(

111

377

        match read_proj.iter().max() {

112

277

            Some(x) => *x + 1,

113

100

            None => 0,

114

},

115

377

        match write_proj.iter().max() {

116

277

            Some(x) => *x + 1,

117

100

            None => 0,

118

},

119

);

120

121

    // Convert projection vectors to meta.

122

377

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

123

3447

    for i in 0..length {

124

3447

        let read = read_proj.contains(&i);

125

3447

        let write = write_proj.contains(&i);

126

127

3447

        if read && write {

128

180

            meta.push(3);

129

180

            meta.push(4);

130

3267

        } else if read {

131

637

            meta.push(1);

132

2630

        } else if write {

133

618

            meta.push(2);

134

2012

        } else {

135

2012

            meta.push(0);

136

2012

137

138

139

377

    singleton(storage, &meta)

140

377

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

864089

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

156

864089

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

157

158

864089

    if meta == storage.empty_vector() {

159

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

160

41938

        storage.protect(set)

161

822151

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

162

315610

        storage.empty_set().clone()

163

    } else {

164

506541

        cache_terniary_op(

165

506541

            storage,

166

506541

            TernaryOperator::RelationalProduct,

167

506541

            set,

168

506541

            rel,

169

506541

            meta,

170

451776

            |storage, set, rel, meta| {

171

451776

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

172

173

451776

                match meta_value {

174

                    0 => {

175

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

176

189938

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

177

178

189938

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

179

189938

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

180

189938

                        if down_result == *storage.empty_set() {

181

31838

                            right_result

182

                        } else {

183

158100

                            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

50515

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

189

50515

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

190

191

50515

                        match set_value.cmp(&rel_value) {

192

10354

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

193

                            Ordering::Equal => {

194

16039

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

195

16039

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

196

16039

                                if down_result == *storage.empty_set() {

197

3154

                                    right_result

198

                                } else {

199

12885

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

200

201

202

24122

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

203

204

205

                    2 => {

206

                        // All values in set should be considered.

207

202992

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

208

202992

                        let mut current = storage.protect(set);

209

                        loop {

210

246711

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

211

246711

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

212

213

246711

                            if set_right == *storage.empty_set() {

214

202992

                                break;

215

43719

216

43719

                            current = storage.protect(&set_right);

217

218

219

                        // Write the values present in the relation.

220

202992

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

221

222

202992

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

223

202992

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

224

202992

                        if down_result == *storage.empty_set() {

225

16180

                            right_result

226

                        } else {

227

186812

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

228

229

230

                    3 => {

231

6340

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

232

6340

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

233

234

6340

                        match set_value.cmp(&rel_value) {

235

1559

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

236

                            Ordering::Equal => {

237

1053

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

238

1053

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

239

1053

                                union(storage, &down_result, &right_result)

240

241

3728

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

242

243

244

                    4 => {

245

                        // Write the values present in the relation.

246

1991

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

247

248

1991

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

249

1991

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

250

1991

                        if down_result == *storage.empty_set() {

251

1568

                            right_result

252

                        } else {

253

423

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

254

255

256

                    x => {

257

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

258

259

260

451776

},

261

262

263

864089

264

265

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

266

8871

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

267

8871

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

268

2622

        storage.empty_set().clone()

269

6249

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

270

466

        storage.protect(a)

271

    } else {

272

5783

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

273

5783

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

274

5783

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

275

276

5783

            match a_value.cmp(&b_value) {

277

                Ordering::Less => {

278

1008

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

279

1008

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

280

281

                Ordering::Equal => {

282

2988

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

283

2988

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

284

2988

                    if down_result == *storage.empty_set() {

285

1536

                        right_result

286

                    } else {

287

1452

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

288

289

290

1787

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

291

292

5783

})

293

294

8871

295

296

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

297

3638245

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

298

3638245

    if a == b {

299

213057

        storage.protect(a)

300

3425188

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

301

562615

        storage.protect(b)

302

2862573

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

303

484086

        storage.protect(a)

304

    } else {

305

2378487

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

306

2317801

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

307

2317801

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

308

309

2317801

            match a_value.cmp(&b_value) {

310

                Ordering::Less => {

311

1527758

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

312

1527758

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

313

314

                Ordering::Equal => {

315

564489

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

316

564489

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

317

564489

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

318

319

                Ordering::Greater => {

320

225554

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

321

225554

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

322

323

324

2317801

})

325

326

3638245

327

328

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

329

3024028

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

330

3024028

    if a == storage.empty_vector() {

331

        storage.protect(b)

332

3024028

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

333

37302

        storage.protect(a)

334

2986726

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

335

1409664

        storage.empty_set().clone()

336

    } else {

337

1577062

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

338

1511964

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

339

340

1511964

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

341

1511964

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

342

343

1511964

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

344

1511964

})

345

346

3024028

347

348

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

349

58604

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

350

58604

    if ldd == storage.empty_set() {

351

26152

        storage.empty_set().clone()

352

32452

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

353

3200

        singleton(storage, &[value])

354

    } else {

355

        // Traverse the ldd.

356

29252

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

357

358

29252

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

359

29252

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

360

361

29252

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

362

363

58604

364

365

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

366

130066

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

367

130066

    if vector.is_empty() {

368

10856

        ldd == storage.empty_vector()

369

119210

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

370

        false

371

    } else {

372

192348

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

373

192348

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

374

                Ordering::Less => {

375

74072

                    continue;

376

377

                Ordering::Equal => {

378

116438

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

379

380

                Ordering::Greater => {

381

1838

                    return false;

382

383

384

385

386

934

        false

387

388

130066

389

390

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

391

26843

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

392

26843

    if set == storage.empty_set() {

393

394

26843

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

395

1087

396

    } else {

397

25756

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

398

23643

            let mut result: usize = 0;

399

400

23643

            let mut current = storage.protect(a);

401

50386

            while current != *storage.empty_set() {

402

26743

                // Progress to the right LDD.

403

26743

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

404

26743

                result += len(storage, &down);

405

26743

                current = storage.protect(&right);

406

26743

407

408

23643

            result

409

23643

})

410

411

26843

412

413

/// Returns the height of the LDD tree.

414

73951149

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

415

73951149

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

416

4977018

417

    } else {

418

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

419

68974131

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

420

421

68974131

        height(storage, &down) + 1

422

423

73951149

424

425

#[cfg(test)]

426

mod tests {

427

    use super::*;

428

    use crate::fmt_node;

429

    use crate::test_utility::*;

430

431

    use merc_utilities::random_test;

432

    use rand::Rng;

433

    use std::collections::HashSet;

434

    use std::ops::Sub;

435

436

    // Compare the LDD element_of implementation for random inputs.

437

    #[test]

438

    #[cfg_attr(miri, ignore)]

439

1

    fn test_random_element_of() {

440

100

        random_test(100, |rng| {

441

100

            let mut storage = Storage::new();

442

443

100

            let length = 10;

444

100

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

445

100

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

446

447

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

448

3200

            for expected in &set {

449

3200

                assert!(

450

3200

                    element_of(&storage, expected, &ldd),

451

                    "Did not find expected vector in ldd"

452

);

453

454

455

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

456

100

            for _ in 0..10 {

457

1000

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

458

1000

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

459

1000

                assert!(

460

1000

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

461

                    "Found shorter vector in ldd."

462

);

463

464

465

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

466

100

            for _ in 0..10 {

467

1000

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

468

1000

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

469

1000

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

470

471

472

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

473

100

            for _ in 0..10 {

474

1000

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

475

1000

                assert_eq!(

476

1000

                    set.contains(&vector),

477

1000

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

478

                    "Set contains did not match ldd element_of"

479

);

480

481

100

});

482

1

483

484

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

485

    #[test]

486

    #[cfg_attr(miri, ignore)]

487

1

    fn test_random_union() {

488

100

        random_test(100, |rng| {

489

100

            let mut storage = Storage::new();

490

491

100

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

492

100

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

493

100

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

494

495

100

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

496

100

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

497

100

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

498

499

100

            assert_eq!(result, expected);

500

100

});

501

1

502

503

    #[test]

504

    #[cfg_attr(miri, ignore)]

505

1

    fn test_random_merge() {

506

100

        random_test(100, |rng| {

507

100

            let mut storage = Storage::new();

508

509

100

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

510

100

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

511

512

            // Compute the interleave explicitly.

513

102400

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

514

102400

                let mut result = vec![];

515

516

102400

                let mut iter = b.iter();

517

1024000

                for value in a {

518

1024000

                    result.push(*value);

519

1024000

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

520

1024000

521

522

102400

                result

523

102400

524

525

100

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

526

3200

            for a in &set_a {

527

102400

                for b in &set_b {

528

102400

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

529

102400

530

531

532

100

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

533

534

100

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

535

100

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

536

100

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

537

538

100

            assert_eq!(result, expected);

539

100

});

540

1

541

542

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

543

    #[test]

544

    #[cfg_attr(miri, ignore)]

545

1

    fn test_random_singleton() {

546

100

        random_test(100, |rng| {

547

100

            let mut storage = Storage::new();

548

100

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

549

550

100

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

551

552

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

553

100

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

554

100

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

555

100

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

556

100

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

557

100

});

558

1

559

560

    // Test the len function with random inputs.

561

    #[test]

562

    #[cfg_attr(miri, ignore)]

563

1

    fn test_random_len() {

564

100

        random_test(100, |rng| {

565

100

            let mut storage = Storage::new();

566

567

100

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

568

100

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

569

570

100

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

571

100

});

572

1

573

574

    // Test the minus function with random inputs.

575

    #[test]

576

    #[cfg_attr(miri, ignore)]

577

1

    fn test_random_minus() {

578

100

        random_test(100, |rng| {

579

100

            let mut storage = Storage::new();

580

581

100

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

582

100

            let set_b = {

583

100

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

584

585

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

586

100

                let mut it = set_a.iter();

587

1600

                for _ in 0..16 {

588

1600

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

589

1600

590

591

100

                result

592

};

593

594

100

            let expected_result = set_a.sub(&set_b);

595

596

100

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

597

100

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

598

100

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

599

600

100

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

601

602

100

            println!("{}", fmt_node(&storage, &result));

603

100

            println!("{}", fmt_node(&storage, &expected));

604

605

100

            assert_eq!(result, expected);

606

100

});

607

1

608

609

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

610

    #[test]

611

    #[cfg_attr(miri, ignore)]

612

1

    fn test_random_readonly_relational_product() {

613

100

        random_test(100, |rng| {

614

100

            let mut storage = Storage::new();

615

100

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

616

617

100

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

618

619

100

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

620

100

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

621

622

100

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

623

100

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

624

625

100

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

626

100

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

627

628

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

629

100

            assert_eq!(read_project, relation);

630

100

});

631

1

632

633

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

634

    #[test]

635

    #[cfg_attr(miri, ignore)]

636

1

    fn test_random_writeonly_relational_product() {

637

100

        random_test(100, |rng| {

638

100

            let mut storage = Storage::new();

639

100

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

640

641

100

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

642

643

100

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

644

100

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

645

646

100

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

647

100

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

648

649

100

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

650

100

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

651

652

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

653

100

            assert_eq!(write_project, relation);

654

100

});

655

1

656

657

    #[test]

658

    #[cfg_attr(miri, ignore)]

659

1

    fn test_random_relational_product() {

660

100

        random_test(100, |rng| {

661

100

            let mut storage = Storage::new();

662

663

100

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

664

100

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

665

666

            // Pick arbitrary read and write parameters in order.

667

100

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

668

100

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

669

670

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

671

            // for relevant positions.

672

100

            let (read_rel_proj, write_rel_proj) = {

673

100

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

674

100

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

675

676

100

                let mut current = 0;

677

1000

                for i in 0..10 {

678

1000

                    if read_proj.contains(&i) {

679

200

                        read_rel_proj.push(current);

680

200

                        current += 1;

681

800

682

683

1000

                    if write_proj.contains(&i) {

684

200

                        write_rel_proj.push(current);

685

200

                        current += 1;

686

800

687

688

689

100

                (read_rel_proj, write_rel_proj)

690

};

691

692

            // Compute LDD result.

693

100

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

694

100

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

695

696

100

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

697

100

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

698

699

100

            eprintln!("set = {}", fmt_node(&storage, &ldd));

700

100

            eprintln!("relation = {}", fmt_node(&storage, &rel));

701

100

            eprintln!("result = {}", fmt_node(&storage, &result));

702

100

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

703

704

100

            eprintln!("meta = {}", fmt_node(&storage, &meta));

705

100

            eprintln!(

706

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

707

                read_proj, write_proj, read_rel_proj, write_rel_proj

708

);

709

710

100

            let expected = {

711

100

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

712

713

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

714

3200

                for x in set.iter() {

715

102144

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

716

102144

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

717

102144

                        let x_prime = project_vector(rel, &read_rel_proj);

718

102144

                        let y_prime = project_vector(rel, &write_rel_proj);

719

720

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

721

112460

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

722

112460

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

723

101116

                                continue 'next;

724

11344

725

726

727

                        // Compute x[write_proj := y']

728

2056

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

729

2056

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

730

2056

731

732

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

733

1028

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

734

1028

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

735

736

1028

                        assert!(

737

1028

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

738

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

739

                            &value

740

);

741

1028

                        expected.insert(value);

742

743

744

745

100

                expected

746

};

747

748

            // Check the other way around

749

1028

            for res in iter(&storage, &result) {

750

1028

                assert!(

751

1028

                    expected.contains(&res),

752

                    "Result unexpectedly contains vector {:?}.",

753

res

754

);

755

756

100

});

757

1

758

759

    // Test the project function with random inputs.

760

    #[test]

761

    #[cfg_attr(miri, ignore)]

762

1

    fn test_random_project() {

763

100

        random_test(100, |rng| {

764

100

            let mut storage = Storage::new();

765

766

100

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

767

100

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

768

769

100

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

770

100

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

771

100

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

772

773

            // Compute a naive projection on the vector set.

774

100

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

775

3200

            for element in &set {

776

3200

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

777

3200

778

100

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

779

100

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

780

100

});

781

1

782

783

    // Test the append function with random inputs.

784

    #[test]

785

    #[cfg_attr(miri, ignore)]

786

1

    fn test_random_append() {

787

100

        random_test(100, |rng| {

788

100

            let mut storage = Storage::new();

789

790

100

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

791

100

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

792

100

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

793

794

100

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

795

3200

            for element in &set {

796

3200

                let mut appended = element.to_vec();

797

3200

                appended.push(0 as Value);

798

3200

                expected_result.insert(appended);

799

3200

800

100

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

801

802

100

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

803

100

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

804

100

});

805

1

806