1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

// Copyright Materialize, Inc. and contributors. All rights reserved.
//
// Use of this software is governed by the Business Source License
// included in the LICENSE file.
//
// As of the Change Date specified in that file, in accordance with
// the Business Source License, use of this software will be governed
// by the Apache License, Version 2.0.

//! Definition and helper structs for the [`SubtreeSize`] attribute.

use mz_expr::MirRelationExpr;

use crate::attribute::{Attribute, DerivedAttributes, DerivedAttributesBuilder};

/// Compute the number of MirRelationExpr in each subtree in a bottom-up manner.
#[derive(Default)]
#[allow(missing_debug_implementations)]
pub struct SubtreeSize {
    /// A vector of results for all nodes in the visited tree in
    /// post-visit order.
    pub results: Vec<usize>,
}

impl Attribute for SubtreeSize {
    type Value = usize;

    fn derive(&mut self, expr: &MirRelationExpr, _deps: &DerivedAttributes) {
        use MirRelationExpr::*;
        let n = self.results.len();
        match expr {
            Constant { .. } => {
                self.results.push(1);
            }
            Get { .. } => {
                self.results.push(1);
            }
            Let {
                value: _, body: _, ..
            } => {
                let body = self.results[n - 1];
                let value = self.results[n - 1 - body];
                self.results.push(body + value + 1);
            }
            LetRec { values, .. } => {
                let body = self.results[n - 1];
                let mut total = body;
                for _ in 0..values.len() {
                    total += self.results[n - 1 - total];
                }
                self.results.push(total + 1);
            }
            Project { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Map { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            FlatMap { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Filter { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Join { inputs, .. } => {
                let mut offset = 1;
                for _ in 0..inputs.len() {
                    offset += &self.results[n - offset];
                }
                self.results.push(offset);
            }
            Reduce { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            TopK { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Negate { input: _ } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Threshold { input: _ } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
            Union { base: _, inputs } => {
                let mut offset = 1;
                for _ in 0..inputs.len() {
                    offset += &self.results[n - offset];
                }
                offset += &self.results[n - offset]; // add base size
                self.results.push(offset);
            }
            ArrangeBy { input: _, .. } => {
                let input = self.results[n - 1];
                self.results.push(input + 1);
            }
        }
    }

    fn add_dependencies(_builder: &mut DerivedAttributesBuilder)
    where
        Self: Sized,
    {
    }

    fn get_results(&self) -> &Vec<Self::Value> {
        &self.results
    }

    fn get_results_mut(&mut self) -> &mut Vec<Self::Value> {
        &mut self.results
    }

    fn take(self) -> Vec<Self::Value> {
        self.results
    }
}