Grcov report - symbol

1

//! The symbol table.

2

//!

3

//! See the item documentation for [`SymbolTable`] for more details.

4

5

/// Sentinel for an uncached symbol-table context hash.

6

const NO_CONTEXT_HASH: u64 = 0;

7

8

fn default_context_hash_cache() -> AtomicU64 {

9

    AtomicU64::new(NO_CONTEXT_HASH)

10

11

12

use crate::representation::ReprId;

13

use crate::representation::Representation;

14

use std::any::TypeId;

15

16

use std::collections::BTreeMap;

17

use std::collections::VecDeque;

18

use std::hash::{DefaultHasher, Hash, Hasher};

19

use std::sync::Arc;

20

use std::sync::atomic::{AtomicU32, AtomicU64, Ordering};

21

22

use super::comprehension::Comprehension;

23

use super::declaration::declaration_content_generation;

24

use super::serde::{AsId, DefaultWithId, HasId, IdPtr, ObjId, PtrAsInner};

25

use super::{

26

    DeclarationPtr, DomainPtr, Expression, GroundDomain, Model, Moo, Name, ReturnType, Typeable,

27

};

28

use itertools::{Itertools as _, izip};

29

use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};

30

use serde::{Deserialize, Serialize};

31

use serde_with::serde_as;

32

use tracing::trace;

33

use uniplate::{Biplate, Tree, Uniplate};

34

35

use indexmap::IndexMap;

36

use indexmap::map::Entry;

37

38

/// Global counter of symbol tables.

39

/// Note that the counter is shared between all threads

40

/// Thus, when running multiple models in parallel, IDs may

41

/// be different with every run depending on scheduling order

42

static SYMBOL_TABLE_ID_COUNTER: AtomicU32 = const { AtomicU32::new(0) };

43

44

#[derive(Debug, Clone, PartialEq, Eq, Hash)]

45

pub struct SymbolTablePtr

46

where

47

    Self: Send + Sync,

48

49

    inner: Arc<SymbolTablePtrInner>,

50

51

52

impl SymbolTablePtr {

53

    /// Create an empty new [SymbolTable] and return a shared pointer to it

54

1584894

    pub fn new() -> Self {

55

1584894

        Self::new_with_data(SymbolTable::new())

56

1584894

57

58

    /// Create an empty new [SymbolTable] with the given parent and return a shared pointer to it

59

505263

    pub fn with_parent(symbols: SymbolTablePtr) -> Self {

60

505263

        Self::new_with_data(SymbolTable::with_parent(symbols))

61

505263

62

63

2260413

    fn new_with_data(data: SymbolTable) -> Self {

64

2260413

        let object_id = SYMBOL_TABLE_ID_COUNTER.fetch_add(1, Ordering::Relaxed);

65

2260413

        let id = ObjId {

66

2260413

            object_id,

67

2260413

            type_name: SymbolTablePtr::TYPE_NAME.into(),

68

2260413

};

69

2260413

        Self::new_with_id_and_data(id, data)

70

2260413

71

72

2260413

    fn new_with_id_and_data(id: ObjId, data: SymbolTable) -> Self {

73

2260413

        Self {

74

2260413

            inner: Arc::new(SymbolTablePtrInner {

75

2260413

id,

76

2260413

                value: RwLock::new(data),

77

2260413

}),

78

2260413

79

2260413

80

81

    /// Read the underlying symbol table.

82

    /// This will block the current thread until a read lock can be acquired.

83

///

84

    /// # WARNING

85

///

86

    /// - If the current thread already holds a lock over this table, this may deadlock.

87

3615325493

    pub fn read(&self) -> RwLockReadGuard<'_, SymbolTable> {

88

3615325493

        self.inner.value.read()

89

3615325493

90

91

    /// Mutate the underlying symbol table.

92

    /// This will block the current thread until an exclusive write lock can be acquired.

93

///

94

    /// # WARNING

95

///

96

    /// - If the current thread already holds a lock over this table, this may deadlock.

97

    /// - Trying to acquire any other lock until the write lock is released will cause a deadlock.

98

    /// - This will mutate the underlying data, which may be shared between other `SymbolTablePtr`s.

99

    ///   Make sure that this is what you want.

100

///

101

    /// To create a separate copy of the table, see [SymbolTablePtr::detach].

102

///

103

70225692

    pub fn write(&self) -> RwLockWriteGuard<'_, SymbolTable> {

104

70225692

        self.inner.value.write()

105

70225692

106

107

    /// Create a new symbol table with the same contents as this one, but a new ID,

108

    /// and return a pointer to it.

109

170256

    pub fn detach(&self) -> Self {

110

170256

        Self::new_with_data(self.read().clone())

111

170256

112

113

114

impl Default for SymbolTablePtr {

115

    fn default() -> Self {

116

        Self::new()

117

118

119

120

impl HasId for SymbolTablePtr {

121

    const TYPE_NAME: &'static str = "SymbolTable";

122

123

3336861

    fn id(&self) -> ObjId {

124

3336861

        self.inner.id.clone()

125

3336861

126

127

128

impl DefaultWithId for SymbolTablePtr {

129

    fn default_with_id(id: ObjId) -> Self {

130

        Self::new_with_id_and_data(id, SymbolTable::default())

131

132

133

134

impl IdPtr for SymbolTablePtr {

135

    type Data = SymbolTable;

136

137

3454

    fn get_data(&self) -> Self::Data {

138

3454

        self.read().clone()

139

3454

140

141

    fn with_id_and_data(id: ObjId, data: Self::Data) -> Self {

142

        Self::new_with_id_and_data(id, data)

143

144

145

146

// TODO: this code is almost exactly copied from [DeclarationPtr].

147

//       It should be possible to eliminate the duplication...

148

//       Perhaps by merging SymbolTablePtr and DeclarationPtr together?

149

//       (Alternatively, a macro?)

150

151

impl Uniplate for SymbolTablePtr {

152

291430

    fn uniplate(&self) -> (Tree<Self>, Box<dyn Fn(Tree<Self>) -> Self>) {

153

291430

        let symtab = self.read();

154

291430

        let (tree, recons) = Biplate::<SymbolTablePtr>::biplate(&symtab as &SymbolTable);

155

156

291430

        let self2 = self.clone();

157

158

291430

            tree,

159

291430

            Box::new(move |x| {

160

                let self3 = self2.clone();

161

                *(self3.write()) = recons(x);

162

                self3

163

}),

164

165

291430

166

167

168

impl<To> Biplate<To> for SymbolTablePtr

169

where

170

    SymbolTable: Biplate<To>,

171

    To: Uniplate,

172

173

5887211

    fn biplate(&self) -> (Tree<To>, Box<dyn Fn(Tree<To>) -> Self>) {

174

5887211

        if TypeId::of::<To>() == TypeId::of::<Self>() {

175

            unsafe {

176

291430

                let self_as_to = std::mem::transmute::<&Self, &To>(self).clone();

177

178

291430

                    Tree::One(self_as_to),

179

291430

                    Box::new(move |x| {

180

                        let Tree::One(x) = x else { panic!() };

181

182

                        let x_as_self = std::mem::transmute::<&To, &Self>(&x);

183

                        x_as_self.clone()

184

}),

185

186

187

        } else {

188

            // call biplate on the enclosed declaration

189

5595781

            let decl = self.read();

190

5595781

            let (tree, recons) = Biplate::<To>::biplate(&decl as &SymbolTable);

191

192

5595781

            let self2 = self.clone();

193

194

5595781

                tree,

195

5595781

                Box::new(move |x| {

196

53

                    let self3 = self2.clone();

197

53

                    *(self3.write()) = recons(x);

198

53

                    self3

199

53

}),

200

201

202

5887211

203

204

205

#[derive(Debug)]

206

struct SymbolTablePtrInner {

207

    id: ObjId,

208

    value: RwLock<SymbolTable>,

209

210

211

impl Hash for SymbolTablePtrInner {

212

2591

    fn hash<H: Hasher>(&self, state: &mut H) {

213

        // Identity hash. Symbol table content is mutable and is hashed by `SymbolTable::context_hash`.

214

2591

        self.id.hash(state);

215

2591

216

217

218

impl PartialEq for SymbolTablePtrInner {

219

1

    fn eq(&self, other: &Self) -> bool {

220

1

        self.id == other.id

221

1

222

223

224

impl Eq for SymbolTablePtrInner {}

225

226

/// The global symbol table, mapping names to their definitions.

227

///

228

/// Names in the symbol table are unique, including between different types of object stored in the

229

/// symbol table. For example, you cannot have a letting and decision variable with the same name.

230

///

231

/// # Symbol Kinds

232

///

233

/// The symbol table tracks the following types of symbol:

234

///

235

/// ## Decision Variables

236

///

237

/// ```text

238

/// find NAME: DOMAIN

239

/// ```

240

///

241

/// See [`DecisionVariable`](super::DecisionVariable).

242

///

243

/// ## Lettings

244

///

245

/// Lettings define constants, of which there are two types:

246

///

247

///   + **Constant values**: `letting val be A`, where A is an [`Expression`].

248

///

249

///     A can be any integer, boolean, or matrix expression.

250

///     A can include references to other lettings, model parameters, and, unlike Savile Row,

251

///     decision variables.

252

///

253

///   + **Constant domains**: `letting Domain be domain D`, where D is a [`Domain`].

254

///

255

///     D can include references to other lettings and model parameters, and, unlike Savile Row,

256

///     decision variables.

257

///

258

/// Unless otherwise stated, these follow the semantics specified in section 2.2.2 of the Savile

259

/// Row manual (version 1.9.1 at time of writing).

260

#[serde_as]

261

#[derive(Debug, Serialize, Deserialize)]

262

pub struct SymbolTable {

263

    #[serde_as(as = "Vec<(_,PtrAsInner)>")]

264

    table: IndexMap<Name, DeclarationPtr>,

265

266

    #[serde_as(as = "Option<AsId>")]

267

    parent: Option<SymbolTablePtr>,

268

269

    next_machine_name: i32,

270

271

    #[serde(default, skip_serializing)]

272

    local_bindings_xor: u64,

273

274

    #[serde(default, skip_serializing)]

275

    /// Declaration generation represented by `local_bindings_xor`.

276

    local_bindings_generation: u64,

277

278

    #[serde(default = "default_context_hash_cache", skip_serializing)]

279

    context_hash_cache: AtomicU64,

280

281

    #[serde(default = "default_context_hash_cache", skip_serializing)]

282

    /// Declaration generation represented by `context_hash_cache`.

283

    context_hash_generation: AtomicU64,

284

285

286

impl Clone for SymbolTable {

287

50883162

    fn clone(&self) -> Self {

288

50883162

        Self {

289

50883162

            table: self.table.clone(),

290

50883162

            parent: self.parent.clone(),

291

50883162

            next_machine_name: self.next_machine_name,

292

50883162

            local_bindings_xor: self.local_bindings_xor,

293

50883162

            local_bindings_generation: self.local_bindings_generation,

294

50883162

            context_hash_cache: AtomicU64::new(NO_CONTEXT_HASH),

295

50883162

            context_hash_generation: AtomicU64::new(0),

296

50883162

297

50883162

298

299

300

impl PartialEq for SymbolTable {

301

    fn eq(&self, other: &Self) -> bool {

302

        self.table == other.table

303

            && self.parent == other.parent

304

            && self.next_machine_name == other.next_machine_name

305

306

307

308

impl Eq for SymbolTable {}

309

310

impl SymbolTable {

311

    /// Creates an empty symbol table.

312

46835774

    pub fn new() -> SymbolTable {

313

46835774

        SymbolTable::new_inner(None)

314

46835774

315

316

    /// Creates an empty symbol table with the given parent.

317

505264

    pub fn with_parent(parent: SymbolTablePtr) -> SymbolTable {

318

505264

        SymbolTable::new_inner(Some(parent))

319

505264

320

321

62110792

    fn new_inner(parent: Option<SymbolTablePtr>) -> SymbolTable {

322

62110792

        let id = SYMBOL_TABLE_ID_COUNTER.fetch_add(1, Ordering::Relaxed);

323

62110792

        trace!(

324

224092

            "new symbol table: id = {id}  parent_id = {}",

325

224092

            parent

326

224092

                .as_ref()

327

832

                .map(|x| x.id().to_string())

328

224092

                .unwrap_or(String::from("none"))

329

);

330

62110792

        SymbolTable {

331

62110792

            table: IndexMap::new(),

332

62110792

            next_machine_name: 0,

333

62110792

            parent,

334

62110792

            local_bindings_xor: 0,

335

62110792

            local_bindings_generation: declaration_content_generation(),

336

62110792

            context_hash_cache: AtomicU64::new(NO_CONTEXT_HASH),

337

62110792

            context_hash_generation: AtomicU64::new(0),

338

62110792

339

62110792

340

341

2988875773

    fn binding_contribution(name: &Name, declaration: &DeclarationPtr) -> u64 {

342

2988875773

        let mut hasher = DefaultHasher::new();

343

2988875773

        (name.clone(), declaration.content_hash()).hash(&mut hasher);

344

2988875773

        hasher.finish()

345

2988875773

346

347

2

    fn finalize_context_hash(bindings_xor: u64, binding_count: usize) -> u64 {

348

2

        let mut hasher = DefaultHasher::new();

349

2

        binding_count.hash(&mut hasher);

350

2

        bindings_xor.hash(&mut hasher);

351

2

        hasher.finish()

352

2

353

354

68192470

    fn recompute_local_bindings_xor(&mut self) {

355

1102103252

        self.local_bindings_xor = self.table.iter().fold(0u64, |acc, (name, declaration)| {

356

1102103252

            acc ^ Self::binding_contribution(name, declaration)

357

1102103252

});

358

68192470

        self.local_bindings_generation = declaration_content_generation();

359

68192470

360

361

    /// Recomputes the incremental binding hash after shared declaration mutation.

362

1318860597

    fn ensure_local_binding_hashes_current(&mut self) {

363

1318860597

        if self.local_bindings_generation != declaration_content_generation() {

364

2895868

            self.recompute_local_bindings_xor();

365

1315964729

366

1318860597

367

368

591780

    pub(crate) fn refresh_local_binding_hashes(&mut self) {

369

591780

        self.recompute_local_bindings_xor();

370

591780

        self.invalidate_context_hash_cache();

371

591780

372

373

635670227

    fn xor_binding_in(&mut self, name: &Name, declaration: &DeclarationPtr) {

374

635670227

        self.local_bindings_xor ^= Self::binding_contribution(name, declaration);

375

635670227

376

377

2652560

    fn xor_binding_out(&mut self, name: &Name, declaration: &DeclarationPtr) {

378

2652560

        self.local_bindings_xor ^= Self::binding_contribution(name, declaration);

379

2652560

380

381

789885130

    pub(crate) fn invalidate_context_hash_cache(&mut self) {

382

789885130

        self.context_hash_cache

383

789885130

            .store(NO_CONTEXT_HASH, Ordering::Relaxed);

384

789885130

        self.context_hash_generation.store(0, Ordering::Relaxed);

385

789885130

386

387

    /// Returns a cached hash of all declarations visible from this scope.

388

///

389

    /// This hashes declaration values, not pointer identity, so rewrite caches remain valid across

390

    /// equivalent symbol states.

391

4

    pub fn context_hash(&self) -> u64 {

392

4

        let declaration_generation = declaration_content_generation();

393

4

        let cached_generation = self.context_hash_generation.load(Ordering::Acquire);

394

4

        let cached = self.context_hash_cache.load(Ordering::Relaxed);

395

4

        if cached != NO_CONTEXT_HASH && cached_generation == declaration_generation {

396

            return cached;

397

4

398

399

        loop {

400

4

            let generation_before = declaration_content_generation();

401

4

            let hash = if self.parent.is_none() {

402

2

                let bindings_xor = if self.local_bindings_generation == generation_before {

403

1

                    self.local_bindings_xor

404

                } else {

405

1

                    self.table.iter().fold(0u64, |acc, (name, declaration)| {

406

1

                        acc ^ Self::binding_contribution(name, declaration)

407

1

})

408

};

409

2

                Self::finalize_context_hash(bindings_xor, self.table.len())

410

            } else {

411

2

                self.compute_scoped_context_hash()

412

};

413

4

            let generation_after = declaration_content_generation();

414

4

            if generation_before == generation_after {

415

4

                self.context_hash_cache.store(hash, Ordering::Relaxed);

416

4

                self.context_hash_generation

417

4

                    .store(generation_after, Ordering::Release);

418

4

                break hash;

419

420

421

4

422

423

2

    fn compute_scoped_context_hash(&self) -> u64 {

424

2

        let mut hasher = DefaultHasher::new();

425

2

        let mut declarations: BTreeMap<Name, u64> = BTreeMap::new();

426

427

2

        for (name, declaration) in self.iter_local() {

428

            declarations.insert(name.clone(), declaration.content_hash());

429

430

431

2

        let mut parent = self.parent.clone();

432

4

        while let Some(parent_ptr) = parent.take() {

433

2

            let guard = parent_ptr.read();

434

2

            for (name, declaration) in guard.iter_local() {

435

2

                declarations

436

2

                    .entry(name.clone())

437

2

                    .or_insert_with(|| declaration.content_hash());

438

439

2

            parent.clone_from(guard.parent());

440

441

442

2

        declarations.len().hash(&mut hasher);

443

2

        for declaration in declarations {

444

2

            declaration.hash(&mut hasher);

445

446

2

        hasher.finish()

447

2

448

449

    /// Looks up the declaration with the given name in the current scope only.

450

///

451

    /// Returns `None` if there is no declaration with that name in the current scope.

452

3159120178

    pub fn lookup_local(&self, name: &Name) -> Option<DeclarationPtr> {

453

3159120178

        self.table.get(name).cloned()

454

3159120178

455

456

    /// Looks up the declaration with the given name, checking all enclosing scopes.

457

///

458

    /// Returns `None` if there is no declaration with that name in scope.

459

662556827

    pub fn lookup(&self, name: &Name) -> Option<DeclarationPtr> {

460

662556827

        self.lookup_local(name).or_else(|| {

461

4272062

            self.parent

462

4272062

                .as_ref()

463

723613

                .and_then(|parent| parent.read().lookup(name))

464

4272062

})

465

662556827

466

467

    /// Inserts a declaration into the symbol table.

468

///

469

    /// Returns `None` if there is already a symbol with this name in the local scope.

470

1248449733

    pub fn insert(&mut self, declaration: DeclarationPtr) -> Option<()> {

471

1248449733

        self.ensure_local_binding_hashes_current();

472

1248449733

        let name = declaration.name().clone();

473

1248449733

        let contribution = Self::binding_contribution(&name, &declaration);

474

1248449733

        if let Entry::Vacant(e) = self.table.entry(name) {

475

654177664

            self.local_bindings_xor ^= contribution;

476

654177664

            e.insert(declaration);

477

654177664

            self.invalidate_context_hash_cache();

478

654177664

            Some(())

479

        } else {

480

594272069

            None

481

482

1248449733

483

484

    /// Updates or adds a declaration in the immediate local scope.

485

2718130

    pub fn update_insert(&mut self, declaration: DeclarationPtr) {

486

2718130

        self.ensure_local_binding_hashes_current();

487

2718130

        let name = declaration.name().clone();

488

2718130

        if let Some(existing) = self.table.get(&name).cloned() {

489

2568866

            self.xor_binding_out(&name, &existing);

490

149264

491

2718130

        self.xor_binding_in(&name, &declaration);

492

2718130

        self.table.insert(name, declaration);

493

2718130

        self.invalidate_context_hash_cache();

494

2718130

495

496

    /// Looks up the return type for name if it has one and is in scope.

497

    pub fn return_type(&self, name: &Name) -> Option<ReturnType> {

498

        self.lookup(name).map(|x| x.return_type())

499

500

501

    /// Looks up the return type for name if has one and is in the local scope.

502

    pub fn return_type_local(&self, name: &Name) -> Option<ReturnType> {

503

        self.lookup_local(name).map(|x| x.return_type())

504

505

506

    /// Looks up the domain of name if it has one and is in scope.

507

///

508

    /// This method can return domain references: if a ground domain is always required, use

509

    /// [`SymbolTable::resolve_domain`].

510

    pub fn domain(&self, name: &Name) -> Option<DomainPtr> {

511

        if let Name::WithRepresentation(name, _) = name {

512

            self.lookup(name)?.domain()

513

        } else {

514

            self.lookup(name)?.domain()

515

516

517

518

    /// Looks up the domain of name, resolving domain references to ground domains.

519

///

520

    /// See [`SymbolTable::domain`].

521

    pub fn resolve_domain(&self, name: &Name) -> Option<Moo<GroundDomain>> {

522

        self.domain(name)?.resolve().ok()

523

524

525

    /// Iterates over entries in the LOCAL symbol table.

526

1250544

    pub fn into_iter_local(self) -> impl Iterator<Item = (Name, DeclarationPtr)> {

527

1250544

        self.table.into_iter()

528

1250544

529

530

    /// Iterates over entries in the LOCAL symbol table, by reference.

531

170232440

    pub fn iter_local(&self) -> impl Iterator<Item = (&Name, &DeclarationPtr)> {

532

170232440

        self.table.iter()

533

170232440

534

535

    /// Iterates over entries in the LOCAL symbol table, by reference.

536

168382

    pub fn iter_local_mut(&mut self) -> impl Iterator<Item = (&Name, &mut DeclarationPtr)> {

537

168382

        self.table.iter_mut()

538

168382

539

540

    /// Extends the symbol table with the given symbol table, updating the gensym counter if

541

    /// necessary.

542

67692734

    pub fn extend(&mut self, other: SymbolTable) {

543

67692734

        self.ensure_local_binding_hashes_current();

544

67692734

        self.next_machine_name = self.next_machine_name.max(other.next_machine_name);

545

546

67692734

        for (name, declaration) in &other.table {

547

632952097

            if let Some(existing) = self.table.get(name).cloned() {

548

83694

                self.xor_binding_out(name, &existing);

549

632868403

550

632952097

            self.xor_binding_in(name, declaration);

551

552

67692734

        self.table.extend(other.table);

553

67692734

        self.invalidate_context_hash_cache();

554

67692734

555

556

    /// Retains only local bindings that are new or changed relative to `baseline`.

557

///

558

    /// Rules traditionally build their effects by cloning the model symbol table and mutating the

559

    /// clone. Compacting that snapshot before application turns it into a small effect delta, so

560

    /// impact analysis and `extend` do not repeatedly process every unchanged declaration.

561

64704822

    pub(crate) fn retain_local_changes_from(&mut self, baseline: &SymbolTable) {

562

8241472340

        self.table.retain(|name, declaration| {

563

8241472340

            baseline

564

8241472340

                .table

565

8241472340

                .get(name)

566

7618007728

                .is_none_or(|old| !declaration.content_eq(old))

567

8241472340

});

568

64704822

        self.recompute_local_bindings_xor();

569

64704822

        self.invalidate_context_hash_cache();

570

64704822

571

572

    /// Creates a new [`DeclarationKind::Find`] declaration in this symbol table with a unique name.

573

///

574

    /// Prefer [`Self::gen_find_auxiliary`] for rewriter-introduced auxiliaries that must not be

575

    /// branched on. Use this only when a generated searchable find is intentionally required.

576

2407

    pub fn gen_find(&mut self, domain: &DomainPtr) -> DeclarationPtr {

577

2407

        let decl = DeclarationPtr::new_find(self.gen_sym(), domain.clone());

578

2407

        self.insert(decl.clone());

579

2407

        decl

580

2407

581

582

    /// Creates a new auxiliary find declaration in this symbol table with a unique name.

583

///

584

    /// See [`DeclarationPtr::new_find_auxiliary`].

585

597613893

    pub fn gen_find_auxiliary(&mut self, domain: &DomainPtr) -> DeclarationPtr {

586

597613893

        let decl = DeclarationPtr::new_find_auxiliary(self.gen_sym(), domain.clone());

587

597613893

        self.insert(decl.clone());

588

597613893

        decl

589

597613893

590

591

    // Reserves a unique machine name in the symbol table

592

597617099

    pub fn gen_sym(&mut self) -> Name {

593

597617099

        let num = self.next_machine_name;

594

597617099

        self.next_machine_name += 1;

595

597617099

        Name::Machine(num)

596

597617099

597

598

    /// Gets the parent of this symbol table as a mutable reference.

599

///

600

    /// This function provides no sanity checks.

601

    pub fn parent_mut_unchecked(&mut self) -> &mut Option<SymbolTablePtr> {

602

        &mut self.parent

603

604

605

    /// Gets the parent of this symbol table.

606

4071197

    pub fn parent(&self) -> &Option<SymbolTablePtr> {

607

4071197

        &self.parent

608

4071197

609

610

    /// Gets the representation `representation` for `name`.

611

///

612

    /// # Returns

613

///

614

    /// + `None` if `name` does not exist, is not a decision variable, or does not have that representation.

615

    pub fn get_representation(

616

        &self,

617

        name: &Name,

618

        representation: &[ReprId],

619

    ) -> Option<Vec<Box<dyn Representation>>> {

620

        // TODO: move representation stuff to declaration / variable to avoid cloning? (we have to

621

        // move inside of an rc here, so cannot return borrows)

622

//

623

        // Also would prevent constant "does exist" "is var" checks.

624

//

625

        // The reason it is not there now is because I'm getting serde issues...

626

//

627

        // Also might run into issues putting get_or_add into declaration/variable, as that

628

        // requires us to mutably borrow both the symbol table, and the variable inside the symbol

629

        // table..

630

631

        let decl = self.lookup(name)?;

632

        let var = &decl.as_find()?;

633

634

        var.representations

635

            .iter()

636

            .find(|x| &x.iter().map(|r| r.repr_id()).collect_vec()[..] == representation)

637

            .cloned()

638

639

640

    /// Gets all initialised representations for `name`.

641

///

642

    /// # Returns

643

///

644

    /// + `None` if `name` does not exist, or is not a decision variable.

645

647049668

    pub fn representations_for(&self, name: &Name) -> Option<Vec<Vec<Box<dyn Representation>>>> {

646

647049668

        let decl = self.lookup(name)?;

647

647049668

        decl.as_find().map(|x| x.representations.clone())

648

647049668

649

650

651

impl IntoIterator for SymbolTable {

652

    type Item = (Name, DeclarationPtr);

653

654

    type IntoIter = SymbolTableIter;

655

656

    /// Iterates over symbol table entries in scope.

657

1353651

    fn into_iter(self) -> Self::IntoIter {

658

1353651

        SymbolTableIter {

659

1353651

            inner: self.table.into_iter(),

660

1353651

            parent: self.parent,

661

1353651

662

1353651

663

664

665

/// Iterator over all symbol table entries in scope.

666

pub struct SymbolTableIter {

667

    // iterator over the current scopes' btreemap

668

    inner: indexmap::map::IntoIter<Name, DeclarationPtr>,

669

670

    // the parent scope

671

    parent: Option<SymbolTablePtr>,

672

673

674

impl Iterator for SymbolTableIter {

675

    type Item = (Name, DeclarationPtr);

676

677

647560132

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

678

647560132

        let mut val = self.inner.next();

679

680

        // Go up the tree until we find a parent symbol table with declarations to iterate over.

681

//

682

        // Note that the parent symbol table may be empty - this is why this is a loop!

683

647560132

        while val.is_none() {

684

1353651

            let parent = self.parent.clone()?;

685

686

            let guard = parent.read();

687

            self.inner = guard.table.clone().into_iter();

688

            self.parent.clone_from(&guard.parent);

689

690

            val = self.inner.next();

691

692

693

646206481

val

694

647560132

695

696

697

impl Default for SymbolTable {

698

14769754

    fn default() -> Self {

699

14769754

        Self::new_inner(None)

700

14769754

701

702

703

// TODO: if we could override `Uniplate` impl but still derive `Biplate` instances,

704

//       we could remove some of this manual code

705

impl Uniplate for SymbolTable {

706

    fn uniplate(&self) -> (Tree<Self>, Box<dyn Fn(Tree<Self>) -> Self>) {

707

        // do not recurse up parents, that would be weird?

708

        let self2 = self.clone();

709

        (Tree::Zero, Box::new(move |_| self2.clone()))

710

711

712

713

impl Biplate<SymbolTablePtr> for SymbolTable {

714

291430

    fn biplate(

715

291430

        &self,

716

291430

    ) -> (

717

291430

        Tree<SymbolTablePtr>,

718

291430

        Box<dyn Fn(Tree<SymbolTablePtr>) -> Self>,

719

291430

) {

720

291430

        let self2 = self.clone();

721

291430

        (Tree::Zero, Box::new(move |_| self2.clone()))

722

291430

723

724

725

impl Biplate<Expression> for SymbolTable {

726

8330848

    fn biplate(&self) -> (Tree<Expression>, Box<dyn Fn(Tree<Expression>) -> Self>) {

727

8330848

        let (child_trees, ctxs): (VecDeque<_>, Vec<_>) = self

728

8330848

            .table

729

8330848

            .values()

730

8330848

            .map(Biplate::<Expression>::biplate)

731

8330848

            .unzip();

732

733

8330848

        let tree = Tree::Many(child_trees);

734

735

8330848

        let self2 = self.clone();

736

8330848

        let ctx = Box::new(move |tree| {

737

53

            let Tree::Many(exprs) = tree else {

738

                panic!("unexpected children structure");

739

};

740

741

53

            let mut self3 = self2.clone();

742

53

            let self3_iter = self3.table.iter_mut();

743

53

            for (ctx, tree, (_, decl)) in izip!(&ctxs, exprs, self3_iter) {

744

                // update declaration inside the pointer instead of creating a new one, so all

745

                // things referencing this keep referencing this.

746

24

                *decl = ctx(tree)

747

748

749

53

            self3

750

53

});

751

752

8330848

        (tree, ctx)

753

8330848

754

755

756

impl Biplate<Comprehension> for SymbolTable {

757

29

    fn biplate(

758

29

        &self,

759

29

    ) -> (

760

29

        Tree<Comprehension>,

761

29

        Box<dyn Fn(Tree<Comprehension>) -> Self>,

762

29

) {

763

29

        let (expr_tree, expr_ctx) = <SymbolTable as Biplate<Expression>>::biplate(self);

764

765

29

        let (exprs, recons_expr_tree) = expr_tree.list();

766

767

        let (comprehension_tree, comprehension_ctx) =

768

29

            <VecDeque<Expression> as Biplate<Comprehension>>::biplate(&exprs);

769

770

29

        let ctx = Box::new(move |x| {

771

            // 1. turn comprehension tree into a list of expressions

772

29

            let exprs = comprehension_ctx(x);

773

774

            // 2. turn list of expressions into an expression tree

775

29

            let expr_tree = recons_expr_tree(exprs);

776

777

            // 3. turn expression tree into a symbol table

778

29

            expr_ctx(expr_tree)

779

29

});

780

781

29

        (comprehension_tree, ctx)

782

29

783

784

785

impl Biplate<Model> for SymbolTable {

786

    // walk into expressions

787

    fn biplate(&self) -> (Tree<Model>, Box<dyn Fn(Tree<Model>) -> Self>) {

788

        let (expr_tree, expr_ctx) = <SymbolTable as Biplate<Expression>>::biplate(self);

789

790

        let (exprs, recons_expr_tree) = expr_tree.list();

791

792

        let (submodel_tree, submodel_ctx) =

793

            <VecDeque<Expression> as Biplate<Model>>::biplate(&exprs);

794

795

        let ctx = Box::new(move |x| {

796

            // 1. turn submodel tree into a list of expressions

797

            let exprs = submodel_ctx(x);

798

799

            // 2. turn list of expressions into an expression tree

800

            let expr_tree = recons_expr_tree(exprs);

801

802

            // 3. turn expression tree into a symbol table

803

            expr_ctx(expr_tree)

804

});

805

        (submodel_tree, ctx)

806

807

808

809

#[cfg(test)]

810

mod tests {

811

    use std::hash::{DefaultHasher, Hash, Hasher};

812

813

    use super::*;

814

    use crate::ast::{Domain, Range, Reference};

815

816

    #[test]

817

1

    fn reference_observes_in_place_domain_update() {

818

1

        let old_domain = Domain::int(vec![Range::Bounded(1, 3)]);

819

1

        let new_domain = Domain::int(vec![Range::Bounded(1, 2)]);

820

1

        let mut declaration = DeclarationPtr::new_find(Name::user("x"), old_domain);

821

1

        let reference = Reference::new(declaration.clone());

822

1

        let original_id = reference.id();

823

824

1

        declaration.as_find_mut().unwrap().domain = new_domain.clone();

825

826

1

        assert_eq!(reference.id(), original_id);

827

1

        assert_eq!(reference.domain(), Some(new_domain));

828

1

829

830

    #[test]

831

1

    fn context_hash_observes_shared_declaration_update() {

832

1

        let mut symbols = SymbolTable::new();

833

        let mut declaration =

834

1

            DeclarationPtr::new_find(Name::user("x"), Domain::int(vec![Range::Bounded(1, 3)]));

835

1

        symbols.insert(declaration.clone()).unwrap();

836

1

        let before = symbols.context_hash();

837

838

1

        declaration.as_find_mut().unwrap().domain = Domain::int(vec![Range::Bounded(1, 2)]);

839

840

1

        assert_ne!(symbols.context_hash(), before);

841

1

842

843

    #[test]

844

1

    fn child_context_hash_observes_parent_declaration_update() {

845

1

        let parent = SymbolTablePtr::new();

846

        let mut declaration =

847

1

            DeclarationPtr::new_find(Name::user("x"), Domain::int(vec![Range::Bounded(1, 3)]));

848

1

        parent.write().insert(declaration.clone()).unwrap();

849

1

        let child = SymbolTable::with_parent(parent);

850

1

        let before = child.context_hash();

851

852

1

        declaration.as_find_mut().unwrap().domain = Domain::int(vec![Range::Bounded(1, 2)]);

853

854

1

        assert_ne!(child.context_hash(), before);

855

1

856

857

    #[test]

858

1

    fn symbol_table_pointer_equality_and_hash_are_identity_based() {

859

1

        let left = SymbolTablePtr::new();

860

1

        let right = SymbolTablePtr::new();

861

1

        assert_ne!(left, right);

862

863

1

        let mut left_hasher = DefaultHasher::new();

864

1

        left.hash(&mut left_hasher);

865

1

        let mut clone_hasher = DefaultHasher::new();

866

1

        left.clone().hash(&mut clone_hasher);

867

1

        assert_eq!(left_hasher.finish(), clone_hasher.finish());

868

1

869