Grcov report - aterm

1

use std::hash::Hash;

2

use std::ptr::NonNull;

3

use std::ptr::slice_from_raw_parts_mut;

4

5

use log::debug;

6

use rustc_hash::FxBuildHasher;

7

8

use merc_unsafety::AllocBlock;

9

use merc_unsafety::BlockAllocatorSafe;

10

use merc_unsafety::StablePointer;

11

use merc_unsafety::StablePointerSet;

12

13

use crate::ATermIndex;

14

use crate::ATermRef;

15

use crate::Symb;

16

use crate::SymbolRef;

17

use crate::Term;

18

use crate::storage::SharedTerm;

19

use crate::storage::SharedTermLookup;

20

21

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

22

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

23

/// or not.

24

pub(crate) struct ATermStorage {

25

    /// Stores terms of any arity.

26

    terms: StablePointerSet<SharedTerm, FxBuildHasher>,

27

28

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

29

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

30

31

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

32

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

33

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

34

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

35

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

36

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

37

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

38

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

39

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

40

41

42

/// The initial capacity for the term storage.

43

const INITIAL_CAPACITY: usize = 1024;

44

45

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

46

const BLOCK_SIZE: usize = 1024;

47

48

impl ATermStorage {

49

    /// Creates a new, empty storage.

50

1764

    pub(crate) fn new() -> Self {

51

1764

        Self {

52

1764

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

53

1764

            int_terms: StablePointerSet::with_capacity_and_hasher_in(

54

1764

                INITIAL_CAPACITY,

55

1764

                FxBuildHasher,

56

1764

                AllocBlock::new(),

57

1764

),

58

1764

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

59

1764

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

60

1764

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

61

1764

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

62

1764

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

63

1764

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

64

1764

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

65

1764

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

66

1764

67

1764

68

69

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

70

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

71

    /// inserted.

72

105659004

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

73

105659004

        &'c self,

74

105659004

        symbol: &'b S,

75

105659004

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

76

105659004

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

77

105659004

        debug_assert_eq!(

78

105659004

            symbol.arity(),

79

105659004

            args.len(),

80

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

81

);

82

83

        // SAFETY: the copied argument indices are stored inside the inserted term, and the

84

        // GC marks the arguments of every live term, so each argument stays in the pool at

85

        // least as long as the term referencing it; the copies are dropped when the term

86

        // itself is reclaimed.

87

252853082

        let arg = |i: usize| unsafe { args[i].shared().copy() };

88

89

105659003

        match symbol.arity() {

90

            0 => {

91

7899737

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

92

7899737

                    symbol: SymbolRef::from_symbol(symbol),

93

7899737

                    args: [],

94

7899737

});

95

7899737

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

96

97

            1 => {

98

936235

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

99

936235

                    symbol: SymbolRef::from_symbol(symbol),

100

936235

                    args: [arg(0)],

101

936235

});

102

936235

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

103

104

            2 => {

105

48163196

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

106

48163196

                    symbol: SymbolRef::from_symbol(symbol),

107

48163196

                    args: [arg(0), arg(1)],

108

48163196

});

109

48163196

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

110

111

            3 => {

112

41232194

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

113

41232194

                    symbol: SymbolRef::from_symbol(symbol),

114

41232194

                    args: [arg(0), arg(1), arg(2)],

115

41232194

});

116

41232194

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

117

118

            4 => {

119

6530049

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

120

6530049

                    symbol: SymbolRef::from_symbol(symbol),

121

6530049

                    args: [arg(0), arg(1), arg(2), arg(3)],

122

6530049

});

123

6530049

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

124

125

            5 => {

126

185284

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

127

185284

                    symbol: SymbolRef::from_symbol(symbol),

128

185284

                    args: [arg(0), arg(1), arg(2), arg(3), arg(4)],

129

185284

});

130

185284

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

131

132

            6 => {

133

575094

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

134

575094

                    symbol: SymbolRef::from_symbol(symbol),

135

575094

                    args: [arg(0), arg(1), arg(2), arg(3), arg(4), arg(5)],

136

575094

});

137

575094

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

138

139

            7 => {

140

137214

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

141

137214

                    symbol: SymbolRef::from_symbol(symbol),

142

137214

                    args: [arg(0), arg(1), arg(2), arg(3), arg(4), arg(5), arg(6)],

143

137214

});

144

137214

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

145

146

            _ => {

147

                let shared_term = SharedTermLookup {

148

                    symbol: SymbolRef::from_symbol(symbol),

149

                    arguments: args,

150

};

151

152

                unsafe {

153

                    self.terms

154

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

155

                            SharedTerm::construct(ptr, key)

156

})

157

158

159

160

105659003

161

162

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

163

    /// and whether it was newly inserted.

164

9250344

    pub(crate) unsafe fn insert_int_term(

165

9250344

        &self,

166

9250344

        symbol: SymbolRef<'_>,

167

9250344

        value: usize,

168

9250344

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

169

        unsafe {

170

9250344

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

171

9250344

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

172

9250344

                annotation: value,

173

9250344

});

174

175

9250344

            (cast_to_shared_term_ptr(&result, 0), inserted)

176

177

9250344

178

179

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

180

///

181

    /// # Safety

182

///

183

    /// Removal invalidates every [`StablePointer`] to a removed term; the caller must guarantee

184

    /// that no pointer to a removed term is dereferenced afterwards.

185

558230

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

186

558230

    where

187

558230

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

188

189

        // SAFETY: The caller guarantees that pointers to removed terms are not used again.

190

        unsafe {

191

558230

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

192

193

8238597

            self.int_terms.retain(|term| f(&cast_to_shared_term_ptr(term, 0)));

194

4116707

            self.terms_0.retain(|term| f(&cast_to_shared_term_ptr(term, 0)));

195

629055

            self.terms_1.retain(|term| f(&cast_to_shared_term_ptr(term, 1)));

196

10279814

            self.terms_2.retain(|term| f(&cast_to_shared_term_ptr(term, 2)));

197

8209525

            self.terms_3.retain(|term| f(&cast_to_shared_term_ptr(term, 3)));

198

7221859

            self.terms_4.retain(|term| f(&cast_to_shared_term_ptr(term, 4)));

199

558230

            self.terms_5.retain(|term| f(&cast_to_shared_term_ptr(term, 5)));

200

558230

            self.terms_6.retain(|term| f(&cast_to_shared_term_ptr(term, 6)));

201

558230

            self.terms_7.retain(|term| f(&cast_to_shared_term_ptr(term, 7)));

202

203

204

        // Removes empty blocks after removing entries.

205

558230

        let mut blocks_removed = 0;

206

558230

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

207

558230

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

208

558230

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

209

558230

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

210

558230

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

211

558230

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

212

558230

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

213

558230

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

214

558230

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

215

558230

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

216

558230

217

218

    /// Returns the number of stored terms.

219

1116389

    pub(crate) fn len(&self) -> usize {

220

1116389

        self.int_terms.len()

221

1116389

            + self.terms_0.len()

222

1116389

            + self.terms_1.len()

223

1116389

            + self.terms_2.len()

224

1116389

            + self.terms_3.len()

225

1116389

            + self.terms_4.len()

226

1116389

            + self.terms_5.len()

227

1116389

            + self.terms_6.len()

228

1116389

            + self.terms_7.len()

229

1116389

            + self.terms.len()

230

1116389

231

232

233

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

234

/// [`SharedTerm`].

235

///

236

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

237

/// of the given arity.

238

163476716

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

239

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

240

163476716

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

241

163476716

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

242

163476716

243

244

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

245

///

246

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

247

#[repr(C)]

248

#[derive(Hash, Eq, PartialEq)]

249

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

250

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

251

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

252

253

254

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

255

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

256

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

257

258

/// Storage for integer ATerms.

259

///

260

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

261

#[repr(C)]

262

#[derive(Hash, Eq, PartialEq)]

263

pub(crate) struct SharedTermInt {

264

    symbol: SymbolRef<'static>,

265

266

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

267

    /// and has arity 0.

268

    annotation: usize,

269

270

271

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

272

unsafe impl BlockAllocatorSafe for SharedTermInt {}

273

274

impl SharedTermInt {

275

    /// Returns the value of the integer term.

276

9253771

    pub(crate) fn value(&self) -> usize {

277

9253771

        self.annotation

278

9253771

279

280

281

#[cfg(test)]

282

mod tests {

283

    use std::mem::align_of;

284

    use std::mem::offset_of;

285

    use std::mem::size_of;

286

287

    use crate::ATermIndex;

288

    use crate::ATermRef;

289

290

    use super::SharedTermFixed;

291

    use super::SharedTermInt;

292

293

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

294

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

295

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

296

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

297

298

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

299

    // byte offset.

300

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

301

302

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

303

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

304

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

305

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

306