Grcov report - aterm

1

#![allow(dead_code)]

2

3

use std::hash::Hash;

4

use std::ptr::NonNull;

5

use std::ptr::slice_from_raw_parts_mut;

6

7

use log::debug;

8

use rustc_hash::FxBuildHasher;

9

10

use merc_unsafety::AllocBlock;

11

use merc_unsafety::BlockAllocatorSafe;

12

use merc_unsafety::StablePointer;

13

use merc_unsafety::StablePointerSet;

14

15

use crate::ATermIndex;

16

use crate::ATermRef;

17

use crate::Symb;

18

use crate::SymbolRef;

19

use crate::Term;

20

use crate::storage::SharedTerm;

21

use crate::storage::SharedTermLookup;

22

23

/// The actual storage for [crate::ATerm]. Terms are stored in separate

24

/// `StablePointerSet`s based on their arity, and whether they have annotations

25

/// or not.

26

pub(crate) struct ATermStorage {

27

    /// Stores terms of any arity.

28

    terms: StablePointerSet<SharedTerm, FxBuildHasher>,

29

30

    /// Stores the fixed size [SharedTermInt] integer terms.

31

    int_terms: StablePointerSet<SharedTermInt, FxBuildHasher, AllocBlock<SharedTermInt, BLOCK_SIZE>>,

32

33

    /// Stores terms of fixed arity, see [SharedTermFixed].

34

    terms_0: StablePointerSet<SharedTermFixed<0>, FxBuildHasher, AllocBlock<SharedTermFixed<0>, BLOCK_SIZE>>,

35

    terms_1: StablePointerSet<SharedTermFixed<1>, FxBuildHasher, AllocBlock<SharedTermFixed<1>, BLOCK_SIZE>>,

36

    terms_2: StablePointerSet<SharedTermFixed<2>, FxBuildHasher, AllocBlock<SharedTermFixed<2>, BLOCK_SIZE>>,

37

    terms_3: StablePointerSet<SharedTermFixed<3>, FxBuildHasher, AllocBlock<SharedTermFixed<3>, BLOCK_SIZE>>,

38

    terms_4: StablePointerSet<SharedTermFixed<4>, FxBuildHasher, AllocBlock<SharedTermFixed<4>, BLOCK_SIZE>>,

39

    terms_5: StablePointerSet<SharedTermFixed<5>, FxBuildHasher, AllocBlock<SharedTermFixed<5>, BLOCK_SIZE>>,

40

    terms_6: StablePointerSet<SharedTermFixed<6>, FxBuildHasher, AllocBlock<SharedTermFixed<6>, BLOCK_SIZE>>,

41

    terms_7: StablePointerSet<SharedTermFixed<7>, FxBuildHasher, AllocBlock<SharedTermFixed<7>, BLOCK_SIZE>>,

42

43

44

/// The initial capacity for the term storage.

45

const INITIAL_CAPACITY: usize = 1024;

46

47

/// The number of terms stored in every block of the fixed-size storage.

48

const BLOCK_SIZE: usize = 1024;

49

50

impl ATermStorage {

51

    /// Creates a new, empty storage.

52

959

    pub fn new() -> Self {

53

959

        Self {

54

959

            terms: StablePointerSet::with_capacity_and_hasher(INITIAL_CAPACITY, FxBuildHasher),

55

959

            int_terms: StablePointerSet::with_capacity_and_hasher_in(

56

959

                INITIAL_CAPACITY,

57

959

                FxBuildHasher,

58

959

                AllocBlock::new(),

59

959

),

60

959

            terms_0: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

61

959

            terms_1: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

62

959

            terms_2: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

63

959

            terms_3: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

64

959

            terms_4: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

65

959

            terms_5: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

66

959

            terms_6: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

67

959

            terms_7: StablePointerSet::with_capacity_and_hasher_in(INITIAL_CAPACITY, FxBuildHasher, AllocBlock::new()),

68

959

69

959

70

71

    /// Inserts a term with the given symbol and arguments into the storage,

72

    /// returning a pointer to the stored term and whether it was newly

73

    /// inserted.

74

80303400

    pub fn insert<'a, 'b, 'c, S: Symb<'a, 'b>>(

75

80303400

        &'c self,

76

80303400

        symbol: &'b S,

77

80303400

        args: &'c [ATermRef<'c>],

78

80303400

    ) -> (StablePointer<SharedTerm>, bool) {

79

80303400

        debug_assert_eq!(

80

80303400

            symbol.arity(),

81

80303400

            args.len(),

82

            "The number of arguments does not match the arity of the symbol"

83

);

84

85

80303399

        match symbol.arity() {

86

            0 => {

87

5694062

                let (result, inserted) = self.terms_0.insert(SharedTermFixed {

88

5694062

                    symbol: SymbolRef::from_symbol(symbol),

89

5694062

                    args: [],

90

5694062

});

91

5694062

                unsafe { (cast_to_shared_term_ptr(&result, 0), inserted) }

92

93

            1 => {

94

785912

                let (result, inserted) = self.terms_1.insert(SharedTermFixed {

95

785912

                    symbol: SymbolRef::from_symbol(symbol),

96

785912

                    args: [args[0].shared().copy()],

97

785912

});

98

785912

                unsafe { (cast_to_shared_term_ptr(&result, 1), inserted) }

99

100

            2 => {

101

36755089

                let (result, inserted) = self.terms_2.insert(SharedTermFixed {

102

36755089

                    symbol: SymbolRef::from_symbol(symbol),

103

36755089

                    args: [args[0].shared().copy(), args[1].shared().copy()],

104

36755089

});

105

36755089

                unsafe { (cast_to_shared_term_ptr(&result, 2), inserted) }

106

107

            3 => {

108

31411312

                let (result, inserted) = self.terms_3.insert(SharedTermFixed {

109

31411312

                    symbol: SymbolRef::from_symbol(symbol),

110

31411312

                    args: [

111

31411312

                        args[0].shared().copy(),

112

31411312

                        args[1].shared().copy(),

113

31411312

                        args[2].shared().copy(),

114

31411312

],

115

31411312

});

116

31411312

                unsafe { (cast_to_shared_term_ptr(&result, 3), inserted) }

117

118

            4 => {

119

4974624

                let (result, inserted) = self.terms_4.insert(SharedTermFixed {

120

4974624

                    symbol: SymbolRef::from_symbol(symbol),

121

4974624

                    args: [

122

4974624

                        args[0].shared().copy(),

123

4974624

                        args[1].shared().copy(),

124

4974624

                        args[2].shared().copy(),

125

4974624

                        args[3].shared().copy(),

126

4974624

],

127

4974624

});

128

4974624

                unsafe { (cast_to_shared_term_ptr(&result, 4), inserted) }

129

130

            5 => {

131

141120

                let (result, inserted) = self.terms_5.insert(SharedTermFixed {

132

141120

                    symbol: SymbolRef::from_symbol(symbol),

133

141120

                    args: [

134

141120

                        args[0].shared().copy(),

135

141120

                        args[1].shared().copy(),

136

141120

                        args[2].shared().copy(),

137

141120

                        args[3].shared().copy(),

138

141120

                        args[4].shared().copy(),

139

141120

],

140

141120

});

141

141120

                unsafe { (cast_to_shared_term_ptr(&result, 5), inserted) }

142

143

            6 => {

144

438112

                let (result, inserted) = self.terms_6.insert(SharedTermFixed {

145

438112

                    symbol: SymbolRef::from_symbol(symbol),

146

438112

                    args: [

147

438112

                        args[0].shared().copy(),

148

438112

                        args[1].shared().copy(),

149

438112

                        args[2].shared().copy(),

150

438112

                        args[3].shared().copy(),

151

438112

                        args[4].shared().copy(),

152

438112

                        args[5].shared().copy(),

153

438112

],

154

438112

});

155

438112

                unsafe { (cast_to_shared_term_ptr(&result, 6), inserted) }

156

157

            7 => {

158

103168

                let (result, inserted) = self.terms_7.insert(SharedTermFixed {

159

103168

                    symbol: SymbolRef::from_symbol(symbol),

160

103168

                    args: [

161

103168

                        args[0].shared().copy(),

162

103168

                        args[1].shared().copy(),

163

103168

                        args[2].shared().copy(),

164

103168

                        args[3].shared().copy(),

165

103168

                        args[4].shared().copy(),

166

103168

                        args[5].shared().copy(),

167

103168

                        args[6].shared().copy(),

168

103168

],

169

103168

});

170

103168

                unsafe { (cast_to_shared_term_ptr(&result, 7), inserted) }

171

172

            _ => {

173

                let shared_term = SharedTermLookup {

174

                    symbol: SymbolRef::from_symbol(symbol),

175

                    arguments: args,

176

};

177

178

                unsafe {

179

                    self.terms

180

                        .insert_equiv_dst(&shared_term, SharedTerm::length_for(&shared_term), |ptr, key| {

181

                            SharedTerm::construct(ptr, key)

182

})

183

184

185

186

80303399

187

188

    /// Inserts an integer term into the storage, returning a pointer to the stored term

189

    /// and whether it was newly inserted.

190

6438188

    pub unsafe fn insert_int_term(&self, symbol: SymbolRef<'_>, value: usize) -> (StablePointer<SharedTerm>, bool) {

191

        unsafe {

192

6438188

            let (result, inserted) = self.int_terms.insert(SharedTermInt {

193

6438188

                symbol: SymbolRef::from_index(symbol.shared()),

194

6438188

                annotation: value,

195

6438188

});

196

197

6438188

            (cast_to_shared_term_ptr(&result, 0), inserted)

198

199

6438188

200

201

    /// Retains only the terms for which the given predicate returns `true`.

202

388407

    pub fn retain<F>(&mut self, mut f: F)

203

388407

    where

204

388407

        F: FnMut(&StablePointer<SharedTerm>) -> bool,

205

206

388407

        self.terms.retain(|term| f(term));

207

208

388407

        self.int_terms

209

5730327

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 0) }));

210

388407

        self.terms_0

211

2862967

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 0) }));

212

388407

        self.terms_1

213

458089

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 1) }));

214

388407

        self.terms_2

215

7209573

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 2) }));

216

388407

        self.terms_3

217

5710807

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 3) }));

218

388407

        self.terms_4

219

5023543

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 4) }));

220

388407

        self.terms_5

221

388407

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 5) }));

222

388407

        self.terms_6

223

388407

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 6) }));

224

388407

        self.terms_7

225

388407

            .retain(|term| f(&unsafe { cast_to_shared_term_ptr(term, 7) }));

226

227

        // Removes empty blocks after removing entries.

228

388407

        let mut blocks_removed = 0;

229

388407

        blocks_removed += self.int_terms.allocator_mut().remove_free_blocks();

230

388407

        blocks_removed += self.terms_0.allocator_mut().remove_free_blocks();

231

388407

        blocks_removed += self.terms_1.allocator_mut().remove_free_blocks();

232

388407

        blocks_removed += self.terms_2.allocator_mut().remove_free_blocks();

233

388407

        blocks_removed += self.terms_3.allocator_mut().remove_free_blocks();

234

388407

        blocks_removed += self.terms_4.allocator_mut().remove_free_blocks();

235

388407

        blocks_removed += self.terms_5.allocator_mut().remove_free_blocks();

236

388407

        blocks_removed += self.terms_6.allocator_mut().remove_free_blocks();

237

388407

        blocks_removed += self.terms_7.allocator_mut().remove_free_blocks();

238

388407

        debug!("Removed {} empty blocks from the fixed-size storage", blocks_removed);

239

388407

240

241

    /// Returns the number of stored terms.

242

776814

    pub fn len(&self) -> usize {

243

776814

        self.int_terms.len()

244

776814

            + self.terms_0.len()

245

776814

            + self.terms_1.len()

246

776814

            + self.terms_2.len()

247

776814

            + self.terms_3.len()

248

776814

            + self.terms_4.len()

249

776814

            + self.terms_5.len()

250

776814

            + self.terms_6.len()

251

776814

            + self.terms_7.len()

252

776814

            + self.terms.len()

253

776814

254

255

256

/// Casts a pointer to a term in a fixed-size storage to a pointer to a

257

/// [`SharedTerm`].

258

///

259

/// SAFETY: The caller must ensure that the given pointer points to a valid term

260

/// of the given arity.

261

114106384

unsafe fn cast_to_shared_term_ptr<T>(ptr: &StablePointer<T>, arity: usize) -> StablePointer<SharedTerm> {

262

    // Build a fat pointer for SharedTerm with metadata equal to the term arity.

263

114106384

    let raw = slice_from_raw_parts_mut(ptr.ptr().as_ptr(), arity) as *mut SharedTerm;

264

114106384

    unsafe { StablePointer::from_related_ptr(NonNull::new_unchecked(raw), ptr) }

265

114106384

266

267

/// Storage for ATerms with a fixed number of arguments.

268

///

269

/// Should be the same layout as [`crate::SharedTerm`] for the shared fields.

270

#[repr(C)]

271

#[derive(Hash, Eq, PartialEq)]

272

pub(crate) struct SharedTermFixed<const N: usize> {

273

    pub(crate) symbol: SymbolRef<'static>,

274

    pub(crate) args: [ATermIndex; N],

275

276

277

// Safety: The first field is a heap pointer. Heap pointers are always well above the small alignment value returned by

278

// `std::ptr::dangling_mut()`, so the sentinel can never collide with a live entry.

279

unsafe impl<const N: usize> BlockAllocatorSafe for SharedTermFixed<N> {}

280

281

/// Storage for integer ATerms.

282

///

283

/// Should be the same layout as [`crate::SharedTerm`] for the shared fields.

284

#[repr(C)]

285

#[derive(Hash, Eq, PartialEq)]

286

pub(crate) struct SharedTermInt {

287

    symbol: SymbolRef<'static>,

288

289

    /// The only important aspect is that `symbol` remains in the same position,

290

    /// and has arity 0.

291

    annotation: usize,

292

293

294

// Safety: Same reasoning as `SharedTermFixed` — the first field is a heap pointer.

295

unsafe impl BlockAllocatorSafe for SharedTermInt {}

296

297

impl SharedTermInt {

298

    /// Returns the value of the integer term.

299

6438844

    pub fn value(&self) -> usize {

300

6438844

        self.annotation

301

6438844

302

303

304

#[cfg(test)]

305

mod tests {

306

    use std::mem::align_of;

307

    use std::mem::offset_of;

308

    use std::mem::size_of;

309

310

    use crate::ATermIndex;

311

    use crate::ATermRef;

312

313

    use super::SharedTermFixed;

314

    use super::SharedTermInt;

315

316

    // `symbol` must be at offset 0 in all term representations so that any pointer to a term

317

    // can safely be cast to `*const SymbolRef` to read the header.

318

    const _: () = assert!(offset_of!(SharedTermFixed<1>, symbol) == 0);

319

    const _: () = assert!(offset_of!(SharedTermInt, symbol) == 0);

320

321

    // The args (SharedTermFixed) and annotation (SharedTermInt) fields must start at the same

322

    // byte offset.

323

    const _: () = assert!(offset_of!(SharedTermFixed<1>, args) == offset_of!(SharedTermInt, annotation));

324

325

    // Both element types must have identical size and alignment so that indexing into the

326

    // argument array produces the same byte offsets in both representations.

327

    const _: () = assert!(size_of::<ATermIndex>() == size_of::<ATermRef<'static>>());

328

    const _: () = assert!(align_of::<ATermIndex>() == align_of::<ATermRef<'static>>());

329