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

363100

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

21

363100

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

22

363100

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

23

4503421

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

24

4503421

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

25

4503421

26

27

363100

    root

28

363100

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

2395

    for i in 0..length {

45

2395

        let included = proj.contains(&i);

46

47

2395

        if included {

48

1200

            result.push(1);

49

1200

        } else {

50

1195

            result.push(0);

51

1195

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

1060766

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

68

1060766

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

69

70

1060766

    if proj == storage.empty_vector() {

71

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

72

110304

        storage.empty_vector().clone()

73

950462

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

74

420329

        storage.empty_set().clone()

75

    } else {

76

530133

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

77

78

530133

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

79

530133

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

80

81

530133

        match proj_value {

82

            0 => {

83

236315

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

84

236315

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

85

236315

                union(storage, &right_result, &down_result)

86

87

            1 => {

88

293818

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

89

293818

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

90

293818

                if down_result == *storage.empty_set() {

91

                    right_result

92

                } else {

93

293818

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

94

95

96

            x => {

97

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

98

99

100

101

1060766

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

3735

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

109

    // Compute length of meta.

110

3735

    let length = cmp::max(

111

3735

        match read_proj.iter().max() {

112

3329

            Some(x) => *x + 1,

113

406

            None => 0,

114

},

115

3735

        match write_proj.iter().max() {

116

3317

            Some(x) => *x + 1,

117

418

            None => 0,

118

},

119

);

120

121

    // Convert projection vectors to meta.

122

3735

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

123

37125

    for i in 0..length {

124

37125

        let read = read_proj.contains(&i);

125

37125

        let write = write_proj.contains(&i);

126

127

37125

        if read && write {

128

7268

            meta.push(3);

129

7268

            meta.push(4);

130

29857

        } else if read {

131

8077

            meta.push(1);

132

21780

        } else if write {

133

8155

            meta.push(2);

134

13625

        } else {

135

13625

            meta.push(0);

136

13625

137

138

139

3735

    singleton(storage, &meta)

140

3735

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

5063039

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

156

5063039

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

157

158

5063039

    if meta == storage.empty_vector() {

159

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

160

101403

        storage.protect(set)

161

4961636

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

162

1613245

        storage.empty_set().clone()

163

    } else {

164

3348391

        cache_terniary_op(

165

3348391

            storage,

166

3348391

            TernaryOperator::RelationalProduct,

167

3348391

            set,

168

3348391

            rel,

169

3348391

            meta,

170

2737568

            |storage, set, rel, meta| {

171

2737568

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

172

173

2737568

                match meta_value {

174

                    0 => {

175

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

176

1380901

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

177

178

1380901

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

179

1380901

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

180

1380901

                        if down_result == *storage.empty_set() {

181

730328

                            right_result

182

                        } else {

183

650573

                            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

292405

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

189

292405

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

190

191

292405

                        match set_value.cmp(&rel_value) {

192

53174

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

193

                            Ordering::Equal => {

194

143315

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

195

143315

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

196

143315

                                if down_result == *storage.empty_set() {

197

109571

                                    right_result

198

                                } else {

199

33744

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

200

201

202

95916

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

203

204

205

                    2 => {

206

                        // All values in set should be considered.

207

526516

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

208

526516

                        let mut current = storage.protect(set);

209

                        loop {

210

1146594

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

211

1146594

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

212

213

1146594

                            if set_right == *storage.empty_set() {

214

526516

                                break;

215

620078

216

620078

                            current = storage.protect(&set_right);

217

218

219

                        // Write the values present in the relation.

220

526516

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

221

222

526516

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

223

526516

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

224

526516

                        if down_result == *storage.empty_set() {

225

133525

                            right_result

226

                        } else {

227

392991

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

228

229

230

                    3 => {

231

415791

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

232

415791

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

233

234

415791

                        match set_value.cmp(&rel_value) {

235

171733

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

236

                            Ordering::Equal => {

237

141687

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

238

141687

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

239

141687

                                union(storage, &down_result, &right_result)

240

241

102371

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

242

243

244

                    4 => {

245

                        // Write the values present in the relation.

246

121955

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

247

248

121955

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

249

121955

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

250

121955

                        if down_result == *storage.empty_set() {

251

66477

                            right_result

252

                        } else {

253

55478

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

254

255

256

                    x => {

257

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

258

259

260

2737568

},

261

262

263

5063039

264

265

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

266

538232

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

267

538232

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

268

148431

        storage.empty_set().clone()

269

389801

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

270

13181

        storage.protect(a)

271

    } else {

272

376620

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

273

311091

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

274

311091

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

275

276

311091

            match a_value.cmp(&b_value) {

277

                Ordering::Less => {

278

21127

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

279

21127

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

280

281

                Ordering::Equal => {

282

225805

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

283

225805

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

284

225805

                    if down_result == *storage.empty_set() {

285

89139

                        right_result

286

                    } else {

287

136666

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

288

289

290

64159

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

291

292

311091

})

293

294

538232

295

296

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

297

7867821

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

298

7867821

    if a == b {

299

813700

        storage.protect(a)

300

7054121

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

301

1140051

        storage.protect(b)

302

5914070

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

303

840100

        storage.protect(a)

304

    } else {

305

5073970

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

306

4303833

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

307

4303833

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

308

309

4303833

            match a_value.cmp(&b_value) {

310

                Ordering::Less => {

311

2033474

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

312

2033474

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

313

314

                Ordering::Equal => {

315

1639197

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

316

1639197

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

317

1639197

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

318

319

                Ordering::Greater => {

320

631162

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

321

631162

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

322

323

324

4303833

})

325

326

7867821

327

328

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

329

3036268

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

330

3036268

    if a == storage.empty_vector() {

331

        storage.protect(b)

332

3036268

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

333

37316

        storage.protect(a)

334

2998952

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

335

1415784

        storage.empty_set().clone()

336

    } else {

337

1583168

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

338

1518084

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

339

340

1518084

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

341

1518084

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

342

343

1518084

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

344

1518084

})

345

346

3036268

347

348

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

349

58518

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

350

58518

    if ldd == storage.empty_set() {

351

26109

        storage.empty_set().clone()

352

32409

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

353

3200

        singleton(storage, &[value])

354

    } else {

355

        // Traverse the ldd.

356

29209

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

357

358

29209

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

359

29209

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

360

361

29209

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

362

363

58518

364

365

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

366

129841

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

367

129841

    if vector.is_empty() {

368

10862

        ldd == storage.empty_vector()

369

118979

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

370

        false

371

    } else {

372

192190

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

373

192190

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

374

                Ordering::Less => {

375

74175

                    continue;

376

377

                Ordering::Equal => {

378

116224

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

379

380

                Ordering::Greater => {

381

1791

                    return false;

382

383

384

385

386

964

        false

387

388

129841

389

390

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

391

96885

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

392

96885

    if set == storage.empty_set() {

393

394

96885

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

395

2427

396

    } else {

397

94458

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

398

61012

            let mut result: usize = 0;

399

400

61012

            let mut current = storage.protect(a);

401

157491

            while current != *storage.empty_set() {

402

96479

                // Progress to the right LDD.

403

96479

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

404

96479

                result += len(storage, &down);

405

96479

                current = storage.protect(&right);

406

96479

407

408

61012

            result

409

61012

})

410

411

96885

412

413

/// Returns the height of the LDD tree.

414

104253915

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

415

104253915

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

416

8865166

417

    } else {

418

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

419

95388749

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

420

421

95388749

        height(storage, &down) + 1

422

423

104253915

424

425

#[cfg(test)]

426

mod tests {

427

    use super::*;

428

    use crate::LddDisplay;

429

    use crate::test_utility::*;

430

431

    use merc_utilities::random_test;

432

    use rand::Rng;

433

    use streaming_iterator::StreamingIterator;

434

    use std::collections::HashSet;

435

    use std::ops::Sub;

436

437

    // Compare the LDD element_of implementation for random inputs.

438

    #[test]

439

    #[cfg_attr(miri, ignore)]

440

1

    fn test_random_element_of() {

441

100

        random_test(100, |rng| {

442

100

            let mut storage = Storage::new();

443

444

100

            let length = 10;

445

100

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

446

100

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

447

448

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

449

3200

            for expected in &set {

450

3200

                assert!(

451

3200

                    element_of(&storage, expected, &ldd),

452

                    "Did not find expected vector in ldd"

453

);

454

455

456

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

457

100

            for _ in 0..10 {

458

1000

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

459

1000

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

460

1000

                assert!(

461

1000

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

462

                    "Found shorter vector in ldd."

463

);

464

465

466

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

467

100

            for _ in 0..10 {

468

1000

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

469

1000

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

470

1000

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

471

472

473

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

474

100

            for _ in 0..10 {

475

1000

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

476

1000

                assert_eq!(

477

1000

                    set.contains(&vector),

478

1000

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

479

                    "Set contains did not match ldd element_of"

480

);

481

482

100

});

483

1

484

485

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

486

    #[test]

487

    #[cfg_attr(miri, ignore)]

488

1

    fn test_random_union() {

489

100

        random_test(100, |rng| {

490

100

            let mut storage = Storage::new();

491

492

100

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

493

100

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

494

100

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

495

496

100

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

497

100

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

498

100

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

499

500

100

            assert_eq!(result, expected);

501

100

});

502

1

503

504

    #[test]

505

    #[cfg_attr(miri, ignore)]

506

1

    fn test_random_merge() {

507

100

        random_test(100, |rng| {

508

100

            let mut storage = Storage::new();

509

510

100

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

511

100

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

512

513

            // Compute the interleave explicitly.

514

102400

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

515

102400

                let mut result = vec![];

516

517

102400

                let mut iter = b.iter();

518

1024000

                for value in a {

519

1024000

                    result.push(*value);

520

1024000

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

521

1024000

522

523

102400

                result

524

102400

525

526

100

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

527

3200

            for a in &set_a {

528

102400

                for b in &set_b {

529

102400

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

530

102400

531

532

533

100

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

534

535

100

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

536

100

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

537

100

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

538

539

100

            assert_eq!(result, expected);

540

100

});

541

1

542

543

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

544

    #[test]

545

    #[cfg_attr(miri, ignore)]

546

1

    fn test_random_singleton() {

547

100

        random_test(100, |rng| {

548

100

            let mut storage = Storage::new();

549

100

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

550

551

100

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

552

553

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

554

100

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

555

100

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

556

100

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

557

100

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

558

100

});

559

1

560

561

    // Test the len function with random inputs.

562

    #[test]

563

    #[cfg_attr(miri, ignore)]

564

1

    fn test_random_len() {

565

100

        random_test(100, |rng| {

566

100

            let mut storage = Storage::new();

567

568

100

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

569

100

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

570

571

100

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

572

100

});

573

1

574

575

    // Test the minus function with random inputs.

576

    #[test]

577

    #[cfg_attr(miri, ignore)]

578

1

    fn test_random_minus() {

579

100

        random_test(100, |rng| {

580

100

            let mut storage = Storage::new();

581

582

100

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

583

100

            let set_b = {

584

100

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

585

586

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

587

100

                let mut it = set_a.iter();

588

1600

                for _ in 0..16 {

589

1600

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

590

1600

591

592

100

                result

593

};

594

595

100

            let expected_result = set_a.sub(&set_b);

596

597

100

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

598

100

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

599

100

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

600

601

100

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

602

603

100

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

604

100

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

605

606

100

            assert_eq!(result, expected);

607

100

});

608

1

609

610

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

611

    #[test]

612

    #[cfg_attr(miri, ignore)]

613

1

    fn test_random_readonly_relational_product() {

614

100

        random_test(100, |rng| {

615

100

            let mut storage = Storage::new();

616

100

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

617

618

100

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

619

620

100

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

621

100

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

622

623

100

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

624

100

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

625

626

100

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

627

100

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

628

629

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

630

100

            assert_eq!(read_project, relation);

631

100

});

632

1

633

634

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

635

    #[test]

636

    #[cfg_attr(miri, ignore)]

637

1

    fn test_random_writeonly_relational_product() {

638

100

        random_test(100, |rng| {

639

100

            let mut storage = Storage::new();

640

100

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

641

642

100

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

643

644

100

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

645

100

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

646

647

100

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

648

100

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

649

650

100

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

651

100

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

652

653

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

654

100

            assert_eq!(write_project, relation);

655

100

});

656

1

657

658

    #[test]

659

    #[cfg_attr(miri, ignore)]

660

1

    fn test_random_relational_product() {

661

100

        random_test(100, |rng| {

662

100

            let mut storage = Storage::new();

663

664

100

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

665

100

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

666

667

            // Pick arbitrary read and write parameters in order.

668

100

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

669

100

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

670

671

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

672

            // for relevant positions.

673

100

            let (read_rel_proj, write_rel_proj) = {

674

100

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

675

100

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

676

677

100

                let mut current = 0;

678

1000

                for i in 0..10 {

679

1000

                    if read_proj.contains(&i) {

680

200

                        read_rel_proj.push(current);

681

200

                        current += 1;

682

800

683

684

1000

                    if write_proj.contains(&i) {

685

200

                        write_rel_proj.push(current);

686

200

                        current += 1;

687

800

688

689

690

100

                (read_rel_proj, write_rel_proj)

691

};

692

693

            // Compute LDD result.

694

100

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

695

100

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

696

697

100

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

698

100

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

699

700

100

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

701

100

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

702

100

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

703

100

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

704

705

100

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

706

100

            eprintln!(

707

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

708

                read_proj, write_proj, read_rel_proj, write_rel_proj

709

);

710

711

100

            let expected = {

712

100

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

713

714

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

715

3200

                for x in set.iter() {

716

102208

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

717

102208

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

718

102208

                        let x_prime = project_vector(rel, &read_rel_proj);

719

102208

                        let y_prime = project_vector(rel, &write_rel_proj);

720

721

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

722

112465

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

723

112465

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

724

101191

                                continue 'next;

725

11274

726

727

728

                        // Compute x[write_proj := y']

729

2034

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

730

2034

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

731

2034

732

733

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

734

1017

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

735

1017

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

736

737

1017

                        assert!(

738

1017

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

739

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

740

                            &value

741

);

742

1017

                        expected.insert(value);

743

744

745

746

100

                expected

747

};

748

749

            // Check the other way around

750

100

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

751

1117

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

752

1017

                assert!(

753

1017

                    expected.contains(res),

754

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

755

res

756

);

757

758

100

});

759

1

760

761

    // Test the project function with random inputs.

762

    #[test]

763

    #[cfg_attr(miri, ignore)]

764

1

    fn test_random_project() {

765

100

        random_test(100, |rng| {

766

100

            let mut storage = Storage::new();

767

768

100

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

769

100

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

770

771

100

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

772

100

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

773

100

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

774

775

            // Compute a naive projection on the vector set.

776

100

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

777

3200

            for element in &set {

778

3200

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

779

3200

780

100

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

781

100

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

782

100

});

783

1

784

785

    // Test the append function with random inputs.

786

    #[test]

787

    #[cfg_attr(miri, ignore)]

788

1

    fn test_random_append() {

789

100

        random_test(100, |rng| {

790

100

            let mut storage = Storage::new();

791

792

100

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

793

100

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

794

100

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

795

796

100

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

797

3200

            for element in &set {

798

3200

                let mut appended = element.to_vec();

799

3200

                appended.push(0 as Value);

800

3200

                expected_result.insert(appended);

801

3200

802

100

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

803

804

100

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

805

100

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

806

100

});

807

1

808