bind/compiler/
symbol_table.rs

1// Copyright 2021 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::compiler::{CompilerError, dependency_graph};
6use crate::parser::common::{CompoundIdentifier, Include};
7use crate::parser::{self, bind_library};
8use crate::{linter, make_identifier};
9use std::collections::HashMap;
10use std::fmt;
11use std::ops::Deref;
12
13pub type SymbolTable = HashMap<CompoundIdentifier, Symbol>;
14
15#[derive(Debug, Clone, PartialEq, Eq, Hash, serde::Deserialize, serde::Serialize)]
16pub enum Symbol {
17    DeprecatedKey(u32),
18    Key(String, bind_library::ValueType),
19    NumberValue(u64),
20    StringValue(String),
21    BoolValue(bool),
22    EnumValue(String),
23}
24
25impl fmt::Display for Symbol {
26    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27        match self {
28            Symbol::DeprecatedKey(key) => write!(f, "DeprecatedKey({})", key),
29            Symbol::Key(key, _) => write!(f, "Key({})", key),
30            Symbol::NumberValue(value) => write!(f, "{}", value),
31            Symbol::StringValue(value) => write!(f, "\"{}\"", value),
32            Symbol::BoolValue(value) => write!(f, "{}", value),
33            Symbol::EnumValue(value) => write!(f, "Enum({})", value),
34        }
35    }
36}
37
38// This struct contains bind library declaration data that's used for inserting symbol
39// table entries.
40struct SymbolTableDeclaration {
41    pub declaration: bind_library::Declaration,
42
43    // Key-value qualified identifiers that are namespaced to the highest dependency that
44    // defined the declaration.
45    pub qualified_k: CompoundIdentifier,
46    pub qualified_v: CompoundIdentifier,
47
48    // Key-value qualified identifiers that are namespaced to the library that defined the
49    // declaration.
50    pub local_qualified_k: CompoundIdentifier,
51    pub local_qualified_v: CompoundIdentifier,
52}
53
54pub fn get_symbol_table_from_libraries<'a>(
55    using: &Vec<Include>,
56    libraries: &[String],
57    lint: bool,
58) -> Result<SymbolTable, CompilerError> {
59    let library_asts: Vec<bind_library::Ast> = libraries
60        .iter()
61        .map(|lib| {
62            let ast = bind_library::Ast::try_from(lib.as_str())
63                .map_err(CompilerError::BindParserError)?;
64            if lint {
65                linter::lint_library(&ast).map_err(CompilerError::LinterError)?;
66            }
67            Ok(ast)
68        })
69        .collect::<Result<_, CompilerError>>()?;
70
71    let dependencies = resolve_dependencies(using, library_asts.iter())?;
72    let aliases = get_aliases(using);
73    construct_symbol_table(dependencies.into_iter(), aliases)
74}
75
76fn get_aliases(using: &Vec<Include>) -> HashMap<CompoundIdentifier, String> {
77    return using
78        .iter()
79        .filter_map(|using| match &using.alias {
80            Some(alias) => Some((using.name.clone(), alias.clone())),
81            None => None,
82        })
83        .collect::<HashMap<_, _>>();
84}
85
86pub fn resolve_dependencies<'a>(
87    using: &Vec<Include>,
88    libraries: impl Iterator<Item = &'a bind_library::Ast> + Clone,
89) -> Result<Vec<&'a bind_library::Ast>, CompilerError> {
90    (|| {
91        let mut graph = dependency_graph::DependencyGraph::new();
92
93        for library in libraries.clone() {
94            graph.insert_node(library.name.clone(), library);
95        }
96
97        for Include { name, .. } in using {
98            graph.insert_edge_from_root(name)?;
99        }
100
101        for library in libraries.clone() {
102            graph.insert_edge_from_root(&library.name)?;
103        }
104
105        for from in libraries {
106            for to in &from.using {
107                graph.insert_edge(&from.name, &to.name)?;
108            }
109        }
110
111        graph.resolve()
112    })()
113    .map_err(CompilerError::DependencyError)
114}
115
116/// Find the namespace of a qualified identifier from the library's includes. Or, if the identifier
117/// is unqualified, return the local qualified identifier.
118fn find_qualified_identifier(
119    declaration: &bind_library::Declaration,
120    using: &Vec<parser::common::Include>,
121    library_names: &std::collections::HashSet<CompoundIdentifier>,
122    local_qualified: &CompoundIdentifier,
123) -> Result<CompoundIdentifier, CompilerError> {
124    if let Some(namespace) = declaration.identifier.parent() {
125        // A declaration of a qualified (i.e. non-local) key must be an extension.
126        if !declaration.extends {
127            return Err(CompilerError::MissingExtendsKeyword(declaration.identifier.clone()));
128        }
129
130        // Special case for deprecated symbols (currently in the fuchsia namespace), return the
131        // declaration as-is.
132        if namespace == make_identifier!["fuchsia"] {
133            return Ok(declaration.identifier.clone());
134        }
135
136        // Find the fully qualified name from the included libraries.
137        let include = using.iter().find(|include| {
138            namespace == include.name || Some(namespace.to_string()) == include.alias
139        });
140
141        if let Some(include) = include {
142            return Ok(include.name.nest(declaration.identifier.name.clone()));
143        }
144
145        // Check if the namespace exists in the compiled library names
146        if library_names.contains(&namespace) {
147            return Ok(namespace.nest(declaration.identifier.name.clone()));
148        }
149
150        return Err(CompilerError::UnresolvedQualification(declaration.identifier.clone()));
151    }
152
153    // It is not valid to extend an unqualified (i.e. local) key.
154    if declaration.extends {
155        return Err(CompilerError::InvalidExtendsKeyword(local_qualified.clone()));
156    }
157
158    // An unqualified/local key is scoped to the current library.
159    Ok(local_qualified.clone())
160}
161
162// Insert entries from |declaration_data| into |symbol_table|.
163fn insert_symbol_entries(
164    symbol_table: &mut SymbolTable,
165    declaration_data: SymbolTableDeclaration,
166) -> Result<(), CompilerError> {
167    let SymbolTableDeclaration {
168        declaration,
169        qualified_k,
170        qualified_v,
171        local_qualified_k,
172        local_qualified_v,
173    } = declaration_data;
174
175    // Type-check the qualified name against the existing symbols, and check that extended
176    // keys are previously defined and that non-extended keys are not.
177    match symbol_table.get(&qualified_k) {
178        Some(Symbol::Key(_, value_type)) => {
179            if !declaration.extends {
180                return Err(CompilerError::DuplicateIdentifier(qualified_k));
181            }
182            if declaration.value_type != *value_type {
183                return Err(CompilerError::TypeMismatch(qualified_k));
184            }
185        }
186        Some(Symbol::DeprecatedKey(_)) => (),
187        Some(_) => {
188            return Err(CompilerError::TypeMismatch(qualified_k));
189        }
190        None => {
191            if declaration.extends {
192                return Err(CompilerError::UndeclaredKey(qualified_k));
193            }
194            symbol_table
195                .insert(qualified_k, Symbol::Key(qualified_v.to_string(), declaration.value_type));
196        }
197    }
198
199    // Insert each value associated with the declaration into the symbol table, taking care
200    // to scope each identifier under the locally qualified identifier of the key. We don't
201    // need to type-check values here since the parser has already done that.
202    for value in &declaration.values {
203        let qualified_value_k = local_qualified_k.nest(value.identifier().to_string());
204        let qualified_value_v = local_qualified_v.nest(value.identifier().to_string());
205        if symbol_table.contains_key(&qualified_value_k) {
206            return Err(CompilerError::DuplicateIdentifier(qualified_value_k));
207        }
208
209        let value_symbol = match value {
210            bind_library::Value::Number(_, value) => Symbol::NumberValue(*value),
211            bind_library::Value::Str(_, value) => Symbol::StringValue(value.clone()),
212            bind_library::Value::Bool(_, value) => Symbol::BoolValue(*value),
213            bind_library::Value::Enum(_) => Symbol::EnumValue(qualified_value_v.to_string()),
214        };
215        symbol_table.insert(qualified_value_k, value_symbol);
216    }
217    Ok(())
218}
219
220/// Construct a map of every key and value defined by `libraries`. The identifiers in the symbol
221/// table will be fully qualified, i.e. they will contain their full namespace. A symbol is
222/// namespaced according to the name of the library it is defined in. If a library defines a value
223/// by extending a previously defined key, then that value will be namespaced to the current library
224/// and not the library of its key.
225pub fn construct_symbol_table(
226    libraries: impl Iterator<Item = impl Deref<Target = bind_library::Ast>>,
227    aliases: HashMap<CompoundIdentifier, String>,
228) -> Result<SymbolTable, CompilerError> {
229    let mut symbol_table: HashMap<CompoundIdentifier, Symbol> = get_deprecated_symbols();
230
231    let libs = libraries.collect::<Vec<_>>();
232    let library_names =
233        libs.iter().map(|lib| lib.name.clone()).collect::<std::collections::HashSet<_>>();
234
235    // Cache extended declarations and insert them into the symbol table after we resolve all
236    // library declarations.
237    let mut extended_declarations: Vec<SymbolTableDeclaration> = vec![];
238
239    for lib in libs {
240        let bind_library::Ast { name, using, declarations } = &*lib;
241
242        let aliased_name = match aliases.get(name) {
243            Some(alias) => Some(make_identifier!(alias)),
244            None => None,
245        };
246
247        for declaration in declarations {
248            // Construct a qualified identifier for this key that's namespaced to the current
249            // library, discarding any other qualifiers. This identifier is used to scope values
250            // defined under this key. We have separate entries for symbol table keys (k) and
251            // values (v) because the key might be aliased.
252            let local_qualified_id = name.nest(declaration.identifier.name.clone());
253
254            // Attempt to match the namespace of the key to an include of the current library, or if
255            // it is unqualified use the local qualified name. Also do a first pass at checking
256            // whether the extend keyword is used correctly. Once again keep separate entries for
257            // symbol table keys (k) and values (v) because the key might be aliased.
258            let qualified_id =
259                find_qualified_identifier(declaration, using, &library_names, &local_qualified_id)?;
260
261            if let Some(alias) = aliased_name.as_ref() {
262                let alias_local_qualified_id = alias.nest(declaration.identifier.name.clone());
263                let alias_qualified_id = find_qualified_identifier(
264                    declaration,
265                    using,
266                    &library_names,
267                    &alias_local_qualified_id,
268                )?;
269
270                let entry_data = SymbolTableDeclaration {
271                    declaration: declaration.clone(),
272                    qualified_k: alias_qualified_id,
273                    qualified_v: qualified_id.clone(),
274                    local_qualified_k: alias_local_qualified_id,
275                    local_qualified_v: local_qualified_id.clone(),
276                };
277
278                if declaration.extends {
279                    extended_declarations.push(entry_data);
280                } else {
281                    insert_symbol_entries(&mut symbol_table, entry_data)?;
282                }
283            }
284
285            let entry_data = SymbolTableDeclaration {
286                declaration: declaration.clone(),
287                qualified_k: qualified_id.clone(),
288                qualified_v: qualified_id,
289                local_qualified_k: local_qualified_id.clone(),
290                local_qualified_v: local_qualified_id,
291            };
292
293            if declaration.extends {
294                extended_declarations.push(entry_data);
295            } else {
296                insert_symbol_entries(&mut symbol_table, entry_data)?;
297            }
298        }
299    }
300
301    for declaration in extended_declarations.into_iter() {
302        insert_symbol_entries(&mut symbol_table, declaration)?;
303    }
304
305    Ok(symbol_table)
306}
307
308#[allow(clippy::vec_init_then_push, reason = "mass allow for https://fxbug.dev/381896734")]
309/// Hard code these symbols during the migration from macros to bind rules. Eventually these
310/// will be defined in libraries and the compiler will emit strings for them in the bytecode.
311fn deprecated_keys() -> Vec<(String, u32)> {
312    let mut keys = Vec::new();
313
314    keys.push(("BIND_PROTOCOL".to_string(), 0x0001));
315
316    keys.push(("BIND_AUTOBIND".to_string(), 0x0002));
317
318    keys.push(("BIND_COMPOSITE".to_string(), 0x0003));
319
320    keys.push(("BIND_PLATFORM_DEV_VID".to_string(), 0x0300));
321    keys.push(("BIND_PCI_VID".to_string(), 0x0100));
322
323    keys.push(("BIND_PCI_DID".to_string(), 0x0101));
324    keys.push(("BIND_PCI_CLASS".to_string(), 0x0102));
325    keys.push(("BIND_PCI_SUBCLASS".to_string(), 0x0103));
326    keys.push(("BIND_PCI_INTERFACE".to_string(), 0x0104));
327    keys.push(("BIND_PCI_REVISION".to_string(), 0x0105));
328    keys.push(("BIND_PCI_TOPO".to_string(), 0x0107));
329
330    // usb binding variables at 0x02XX
331    // these are used for both ZX_PROTOCOL_USB_INTERFACE and ZX_PROTOCOL_USB_FUNCTION
332    keys.push(("BIND_USB_VID".to_string(), 0x0200));
333    keys.push(("BIND_USB_PID".to_string(), 0x0201));
334    keys.push(("BIND_USB_CLASS".to_string(), 0x0202));
335    keys.push(("BIND_USB_SUBCLASS".to_string(), 0x0203));
336    keys.push(("BIND_USB_PROTOCOL".to_string(), 0x0204));
337    keys.push(("BIND_USB_INTERFACE_NUMBER".to_string(), 0x0205));
338
339    // Platform bus binding variables at 0x03XX
340    keys.push(("BIND_PLATFORM_DEV_VID".to_string(), 0x0300));
341    keys.push(("BIND_PLATFORM_DEV_PID".to_string(), 0x0301));
342    keys.push(("BIND_PLATFORM_DEV_DID".to_string(), 0x0302));
343    keys.push(("BIND_PLATFORM_DEV_INSTANCE_ID".to_string(), 0x0304));
344    keys.push(("BIND_PLATFORM_DEV_INTERRUPT_ID".to_string(), 0x0305));
345
346    // ACPI binding variables at 0x04XX
347    keys.push(("BIND_ACPI_BUS_TYPE".to_string(), 0x0400));
348    keys.push(("BIND_ACPI_ID".to_string(), 0x0401));
349
350    // Intel HDA Codec binding variables at 0x05XX
351    keys.push(("BIND_IHDA_CODEC_VID".to_string(), 0x0500));
352    keys.push(("BIND_IHDA_CODEC_DID".to_string(), 0x0501));
353
354    // Serial binding variables at 0x06XX
355    keys.push(("BIND_SERIAL_CLASS".to_string(), 0x0600));
356
357    // NAND binding variables at 0x07XX
358    keys.push(("BIND_NAND_CLASS".to_string(), 0x0700));
359
360    // SDIO binding variables at 0x09XX
361    keys.push(("BIND_SDIO_VID".to_string(), 0x0900));
362    keys.push(("BIND_SDIO_PID".to_string(), 0x0901));
363    keys.push(("BIND_SDIO_FUNCTION".to_string(), 0x0902));
364
365    // Init step binding variables at 0x0A6X.
366    keys.push(("BIND_INIT_STEP".to_string(), 0x0A60));
367
368    keys
369}
370
371fn get_deprecated_symbols() -> SymbolTable {
372    let mut symbol_table = HashMap::new();
373    for (key, value) in deprecated_keys() {
374        symbol_table.insert(make_identifier!("fuchsia", key), Symbol::DeprecatedKey(value));
375    }
376    symbol_table
377}
378
379pub fn get_deprecated_key_identifiers() -> HashMap<u32, String> {
380    let mut key_identifiers = HashMap::new();
381    for (key, value) in deprecated_keys() {
382        key_identifiers.insert(value, make_identifier!("fuchsia", key).to_string());
383    }
384    key_identifiers
385}
386
387pub fn get_deprecated_key_identifier(key: u32) -> Option<String> {
388    get_deprecated_key_identifier_str(key).map(str::to_string)
389}
390
391pub fn get_deprecated_key_identifier_str(key: u32) -> Option<&'static str> {
392    match key {
393        0x0001 => Some("fuchsia.BIND_PROTOCOL"),
394        0x0002 => Some("fuchsia.BIND_AUTOBIND"),
395        0x0003 => Some("fuchsia.BIND_COMPOSITE"),
396
397        // PCI binding variables at 0x01XX.
398        0x0100 => Some("fuchsia.BIND_PCI_VID"),
399        0x0101 => Some("fuchsia.BIND_PCI_DID"),
400        0x0102 => Some("fuchsia.BIND_PCI_CLASS"),
401        0x0103 => Some("fuchsia.BIND_PCI_SUBCLASS"),
402        0x0104 => Some("fuchsia.BIND_PCI_INTERFACE"),
403        0x0105 => Some("fuchsia.BIND_PCI_REVISION"),
404        0x0107 => Some("fuchsia.BIND_PCI_TOPO"),
405
406        // USB binding variables at 0x02XX.
407        0x0200 => Some("fuchsia.BIND_USB_VID"),
408        0x0201 => Some("fuchsia.BIND_USB_PID"),
409        0x0202 => Some("fuchsia.BIND_USB_CLASS"),
410        0x0203 => Some("fuchsia.BIND_USB_SUBCLASS"),
411        0x0204 => Some("fuchsia.BIND_USB_PROTOCOL"),
412        0x0205 => Some("fuchsia.BIND_USB_INTERFACE_NUMBER"),
413
414        // Platform bus binding variables at 0x03XX.
415        0x0300 => Some("fuchsia.BIND_PLATFORM_DEV_VID"),
416        0x0301 => Some("fuchsia.BIND_PLATFORM_DEV_PID"),
417        0x0302 => Some("fuchsia.BIND_PLATFORM_DEV_DID"),
418        0x0304 => Some("fuchsia.BIND_PLATFORM_DEV_INSTANCE_ID"),
419        0x0305 => Some("fuchsia.BIND_PLATFORM_DEV_INTERRUPT_ID"),
420
421        // ACPI binding variables at 0x04XX.
422        0x0400 => Some("fuchsia.BIND_ACPI_BUS_TYPE"),
423        0x0401 => Some("fuchsia.BIND_ACPI_ID"),
424
425        // Intel HDA Codec binding variables at 0x05XX.
426        0x0500 => Some("fuchsia.BIND_IHDA_CODEC_VID"),
427        0x0501 => Some("fuchsia.BIND_IHDA_CODEC_DID"),
428
429        // Serial binding variables at 0x06XX.
430        0x0600 => Some("fuchsia.BIND_SERIAL_CLASS"),
431
432        // NAND binding variables at 0x07XX.
433        0x0700 => Some("fuchsia.BIND_NAND_CLASS"),
434
435        // SDIO binding variables at 0x09XX.
436        0x0900 => Some("fuchsia.BIND_SDIO_VID"),
437        0x0901 => Some("fuchsia.BIND_SDIO_PID"),
438        0x0902 => Some("fuchsia.BIND_SDIO_FUNCTION"),
439
440        // Init step binding variables at 0x0A6X.
441        0x0A60 => Some("fuchsia.BIND_INIT_STEP"),
442
443        _ => None,
444    }
445}
446
447pub fn get_deprecated_key_value(key: &str) -> Option<u32> {
448    match key {
449        "fuchsia.BIND_PROTOCOL" => Some(0x0001),
450        "fuchsia.BIND_AUTOBIND" => Some(0x0002),
451        "fuchsia.BIND_COMPOSITE" => Some(0x0003),
452
453        // PCI binding variables at 0x01XX.
454        "fuchsia.BIND_PCI_VID" => Some(0x0100),
455        "fuchsia.BIND_PCI_DID" => Some(0x0101),
456        "fuchsia.BIND_PCI_CLASS" => Some(0x0102),
457        "fuchsia.BIND_PCI_SUBCLASS" => Some(0x0103),
458        "fuchsia.BIND_PCI_INTERFACE" => Some(0x0104),
459        "fuchsia.BIND_PCI_REVISION" => Some(0x0105),
460        "fuchsia.BIND_PCI_TOPO" => Some(0x0107),
461
462        // USB binding variables at 0x02XX.
463        "fuchsia.BIND_USB_VID" => Some(0x0200),
464        "fuchsia.BIND_USB_PID" => Some(0x0201),
465        "fuchsia.BIND_USB_CLASS" => Some(0x0202),
466        "fuchsia.BIND_USB_SUBCLASS" => Some(0x0203),
467        "fuchsia.BIND_USB_PROTOCOL" => Some(0x0204),
468        "fuchsia.BIND_USB_INTERFACE_NUMBER" => Some(0x0205),
469
470        // Platform bus binding variables at 0x03XX
471        "fuchsia.BIND_PLATFORM_DEV_VID" => Some(0x0300),
472        "fuchsia.BIND_PLATFORM_DEV_PID" => Some(0x0301),
473        "fuchsia.BIND_PLATFORM_DEV_DID" => Some(0x0302),
474        "fuchsia.BIND_PLATFORM_DEV_INSTANCE_ID" => Some(0x0304),
475        "fuchsia.BIND_PLATFORM_DEV_INTERRUPT_ID" => Some(0x0305),
476
477        // ACPI binding variables at 0x04XX
478        "fuchsia.BIND_ACPI_BUS_TYPE" => Some(0x0400),
479        "fuchsia.BIND_ACPI_ID" => Some(0x0401),
480
481        // Intel HDA Codec binding variables at 0x05XX
482        "fuchsia.BIND_IHDA_CODEC_VID" => Some(0x0500),
483        "fuchsia.BIND_IHDA_CODEC_DID" => Some(0x0501),
484
485        // Serial binding variables at 0x06XX
486        "fuchsia.BIND_SERIAL_CLASS" => Some(0x0600),
487
488        // NAND binding variables at 0x07XX
489        "fuchsia.BIND_NAND_CLASS" => Some(0x0700),
490
491        // SDIO binding variables at 0x09XX
492        "fuchsia.BIND_SDIO_VID" => Some(0x0900),
493        "fuchsia.BIND_SDIO_PID" => Some(0x0901),
494        "fuchsia.BIND_SDIO_FUNCTION" => Some(0x0902),
495
496        // Init step binding variables at 0x0A6X.
497        "fuchsia.BIND_INIT_STEP" => Some(0x0A60),
498
499        _ => None,
500    }
501}
502
503#[cfg(test)]
504mod test {
505    use super::*;
506    use crate::make_identifier;
507    use crate::parser::bind_library;
508    use crate::parser::common::Include;
509
510    mod symbol_table {
511        use super::*;
512
513        #[test]
514        fn simple_key_and_value() {
515            let libraries = vec![bind_library::Ast {
516                name: make_identifier!("test"),
517                using: vec![],
518                declarations: vec![bind_library::Declaration {
519                    identifier: make_identifier!["symbol"],
520                    value_type: bind_library::ValueType::Number,
521                    extends: false,
522                    values: vec![(bind_library::Value::Number("x".to_string(), 1))],
523                }],
524            }];
525
526            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
527            assert_eq!(
528                st.get(&make_identifier!("test", "symbol")),
529                Some(&Symbol::Key("test.symbol".to_string(), bind_library::ValueType::Number))
530            );
531            assert_eq!(
532                st.get(&make_identifier!("test", "symbol", "x")),
533                Some(&Symbol::NumberValue(1))
534            );
535        }
536
537        #[test]
538        fn all_value_types() {
539            let libraries = vec![bind_library::Ast {
540                name: make_identifier!("hummingbird"),
541                using: vec![],
542                declarations: vec![
543                    bind_library::Declaration {
544                        identifier: make_identifier!["sunbeam"],
545                        value_type: bind_library::ValueType::Number,
546                        extends: false,
547                        values: vec![(bind_library::Value::Number("shining".to_string(), 1))],
548                    },
549                    bind_library::Declaration {
550                        identifier: make_identifier!["mountaingem"],
551                        value_type: bind_library::ValueType::Bool,
552                        extends: false,
553                        values: vec![
554                            (bind_library::Value::Bool("white-bellied".to_string(), false)),
555                        ],
556                    },
557                    bind_library::Declaration {
558                        identifier: make_identifier!["brilliant"],
559                        value_type: bind_library::ValueType::Enum,
560                        extends: false,
561                        values: vec![(bind_library::Value::Enum("black-throated".to_string()))],
562                    },
563                    bind_library::Declaration {
564                        identifier: make_identifier!["woodnymph"],
565                        value_type: bind_library::ValueType::Str,
566                        extends: false,
567                        values: vec![
568                            (bind_library::Value::Str(
569                                "fork-tailed".to_string(),
570                                "sabrewing".to_string(),
571                            )),
572                        ],
573                    },
574                ],
575            }];
576
577            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
578            assert_eq!(
579                st.get(&make_identifier!("hummingbird", "sunbeam", "shining")),
580                Some(&Symbol::NumberValue(1))
581            );
582            assert_eq!(
583                st.get(&make_identifier!("hummingbird", "mountaingem", "white-bellied")),
584                Some(&Symbol::BoolValue(false))
585            );
586            assert_eq!(
587                st.get(&make_identifier!("hummingbird", "brilliant", "black-throated")),
588                Some(&Symbol::EnumValue("hummingbird.brilliant.black-throated".to_string()))
589            );
590            assert_eq!(
591                st.get(&make_identifier!("hummingbird", "woodnymph", "fork-tailed")),
592                Some(&Symbol::StringValue("sabrewing".to_string()))
593            );
594        }
595
596        #[test]
597        fn extension() {
598            let libraries = vec![
599                bind_library::Ast {
600                    name: make_identifier!("lib_a"),
601                    using: vec![],
602                    declarations: vec![bind_library::Declaration {
603                        identifier: make_identifier!["symbol"],
604                        value_type: bind_library::ValueType::Number,
605                        extends: false,
606                        values: vec![(bind_library::Value::Number("x".to_string(), 1))],
607                    }],
608                },
609                bind_library::Ast {
610                    name: make_identifier!("lib_b"),
611                    using: vec![Include { name: make_identifier!("lib_a"), alias: None }],
612                    declarations: vec![bind_library::Declaration {
613                        identifier: make_identifier!["lib_a", "symbol"],
614                        value_type: bind_library::ValueType::Number,
615                        extends: true,
616                        values: vec![(bind_library::Value::Number("y".to_string(), 2))],
617                    }],
618                },
619            ];
620
621            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
622            assert_eq!(
623                st.get(&make_identifier!("lib_a", "symbol")),
624                Some(&Symbol::Key("lib_a.symbol".to_string(), bind_library::ValueType::Number))
625            );
626            assert_eq!(
627                st.get(&make_identifier!("lib_a", "symbol", "x")),
628                Some(&Symbol::NumberValue(1))
629            );
630            assert_eq!(
631                st.get(&make_identifier!("lib_b", "symbol", "y")),
632                Some(&Symbol::NumberValue(2))
633            );
634        }
635
636        #[test]
637        fn extension_with_dependency_defined_after_library() {
638            let libraries = vec![
639                bind_library::Ast {
640                    name: make_identifier!("lib_b"),
641                    using: vec![Include { name: make_identifier!("lib_a"), alias: None }],
642                    declarations: vec![bind_library::Declaration {
643                        identifier: make_identifier!["lib_a", "symbol"],
644                        value_type: bind_library::ValueType::Number,
645                        extends: true,
646                        values: vec![(bind_library::Value::Number("y".to_string(), 2))],
647                    }],
648                },
649                bind_library::Ast {
650                    name: make_identifier!("lib_a"),
651                    using: vec![],
652                    declarations: vec![bind_library::Declaration {
653                        identifier: make_identifier!["symbol"],
654                        value_type: bind_library::ValueType::Number,
655                        extends: false,
656                        values: vec![(bind_library::Value::Number("x".to_string(), 1))],
657                    }],
658                },
659            ];
660
661            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
662            assert_eq!(
663                st.get(&make_identifier!("lib_a", "symbol")),
664                Some(&Symbol::Key("lib_a.symbol".to_string(), bind_library::ValueType::Number))
665            );
666            assert_eq!(
667                st.get(&make_identifier!("lib_a", "symbol", "x")),
668                Some(&Symbol::NumberValue(1))
669            );
670            assert_eq!(
671                st.get(&make_identifier!("lib_b", "symbol", "y")),
672                Some(&Symbol::NumberValue(2))
673            );
674        }
675
676        #[test]
677        fn aliased_extension() {
678            let libraries = vec![
679                bind_library::Ast {
680                    name: make_identifier!("lib_a"),
681                    using: vec![],
682                    declarations: vec![bind_library::Declaration {
683                        identifier: make_identifier!["symbol"],
684                        value_type: bind_library::ValueType::Number,
685                        extends: false,
686                        values: vec![(bind_library::Value::Number("x".to_string(), 1))],
687                    }],
688                },
689                bind_library::Ast {
690                    name: make_identifier!("lib_b"),
691                    using: vec![Include {
692                        name: make_identifier!("lib_a"),
693                        alias: Some("alias".to_string()),
694                    }],
695                    declarations: vec![bind_library::Declaration {
696                        identifier: make_identifier!["alias", "symbol"],
697                        value_type: bind_library::ValueType::Number,
698                        extends: true,
699                        values: vec![(bind_library::Value::Number("y".to_string(), 2))],
700                    }],
701                },
702            ];
703
704            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
705            assert_eq!(
706                st.get(&make_identifier!("lib_a", "symbol")),
707                Some(&Symbol::Key("lib_a.symbol".to_string(), bind_library::ValueType::Number))
708            );
709            assert_eq!(
710                st.get(&make_identifier!("lib_a", "symbol", "x")),
711                Some(&Symbol::NumberValue(1))
712            );
713            assert_eq!(
714                st.get(&make_identifier!("lib_b", "symbol", "y")),
715                Some(&Symbol::NumberValue(2))
716            );
717        }
718
719        #[test]
720        fn aliased_extension_with_library_alias() {
721            let libraries = vec![
722                bind_library::Ast {
723                    name: make_identifier!("lib_a"),
724                    using: vec![],
725                    declarations: vec![bind_library::Declaration {
726                        identifier: make_identifier!["symbol"],
727                        value_type: bind_library::ValueType::Number,
728                        extends: false,
729                        values: vec![(bind_library::Value::Number("x".to_string(), 1))],
730                    }],
731                },
732                bind_library::Ast {
733                    name: make_identifier!("lib_b"),
734                    using: vec![Include {
735                        name: make_identifier!("lib_a"),
736                        alias: Some("alias".to_string()),
737                    }],
738                    declarations: vec![
739                        bind_library::Declaration {
740                            identifier: make_identifier!["alias", "symbol"],
741                            value_type: bind_library::ValueType::Number,
742                            extends: true,
743                            values: vec![(bind_library::Value::Number("y".to_string(), 2))],
744                        },
745                        bind_library::Declaration {
746                            identifier: make_identifier!["enum_symbol"],
747                            value_type: bind_library::ValueType::Enum,
748                            extends: false,
749                            values: vec![(bind_library::Value::Enum("the_val".to_string()))],
750                        },
751                    ],
752                },
753            ];
754
755            // The symbol table will be constructed with 'lib_b' aliased as 'opaque'.
756            let st = construct_symbol_table(
757                libraries.iter(),
758                HashMap::from([(make_identifier!("lib_b"), "opaque".to_string())]),
759            )
760            .unwrap();
761
762            assert_eq!(
763                st.get(&make_identifier!("lib_a", "symbol")),
764                Some(&Symbol::Key("lib_a.symbol".to_string(), bind_library::ValueType::Number))
765            );
766            assert_eq!(
767                st.get(&make_identifier!("lib_a", "symbol", "x")),
768                Some(&Symbol::NumberValue(1))
769            );
770            assert_eq!(
771                st.get(&make_identifier!("opaque", "symbol", "y")),
772                Some(&Symbol::NumberValue(2))
773            );
774            assert_eq!(
775                st.get(&make_identifier!("lib_b", "symbol", "y")),
776                Some(&Symbol::NumberValue(2))
777            );
778            assert_eq!(
779                st.get(&make_identifier!("opaque", "enum_symbol")),
780                Some(&Symbol::Key("lib_b.enum_symbol".to_string(), bind_library::ValueType::Enum))
781            );
782            assert_eq!(
783                st.get(&make_identifier!("lib_b", "enum_symbol")),
784                Some(&Symbol::Key("lib_b.enum_symbol".to_string(), bind_library::ValueType::Enum))
785            );
786            assert_eq!(
787                st.get(&make_identifier!("opaque", "enum_symbol", "the_val")),
788                Some(&Symbol::EnumValue("lib_b.enum_symbol.the_val".to_string()))
789            );
790            assert_eq!(
791                st.get(&make_identifier!("lib_b", "enum_symbol", "the_val")),
792                Some(&Symbol::EnumValue("lib_b.enum_symbol.the_val".to_string()))
793            );
794        }
795
796        #[test]
797        fn deprecated_key_extension() {
798            let libraries = vec![bind_library::Ast {
799                name: make_identifier!("lib_a"),
800                using: vec![],
801                declarations: vec![bind_library::Declaration {
802                    identifier: make_identifier!["fuchsia", "BIND_PCI_DID"],
803                    value_type: bind_library::ValueType::Number,
804                    extends: true,
805                    values: vec![(bind_library::Value::Number("x".to_string(), 0x1234))],
806                }],
807            }];
808
809            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
810            assert_eq!(
811                st.get(&make_identifier!("lib_a", "BIND_PCI_DID", "x")),
812                Some(&Symbol::NumberValue(0x1234))
813            );
814        }
815
816        #[test]
817        fn duplicate_key() {
818            let libraries = vec![bind_library::Ast {
819                name: make_identifier!("test"),
820                using: vec![],
821                declarations: vec![
822                    bind_library::Declaration {
823                        identifier: make_identifier!["symbol"],
824                        value_type: bind_library::ValueType::Number,
825                        extends: false,
826                        values: vec![],
827                    },
828                    bind_library::Declaration {
829                        identifier: make_identifier!["symbol"],
830                        value_type: bind_library::ValueType::Number,
831                        extends: false,
832                        values: vec![],
833                    },
834                ],
835            }];
836
837            assert_eq!(
838                construct_symbol_table(libraries.iter(), HashMap::new()),
839                Err(CompilerError::DuplicateIdentifier(make_identifier!("test", "symbol")))
840            );
841        }
842
843        #[test]
844        fn duplicate_value() {
845            let libraries = vec![bind_library::Ast {
846                name: make_identifier!("test"),
847                using: vec![],
848                declarations: vec![bind_library::Declaration {
849                    identifier: make_identifier!["symbol"],
850                    value_type: bind_library::ValueType::Number,
851                    extends: false,
852                    values: vec![
853                        bind_library::Value::Number("a".to_string(), 1),
854                        bind_library::Value::Number("a".to_string(), 2),
855                    ],
856                }],
857            }];
858
859            assert_eq!(
860                construct_symbol_table(libraries.iter(), HashMap::new()),
861                Err(CompilerError::DuplicateIdentifier(make_identifier!("test", "symbol", "a")))
862            );
863        }
864
865        #[test]
866        fn keys_are_qualified() {
867            // The same symbol declared in two libraries should not collide.
868            let libraries = vec![
869                bind_library::Ast {
870                    name: make_identifier!("lib_a"),
871                    using: vec![],
872                    declarations: vec![bind_library::Declaration {
873                        identifier: make_identifier!["symbol"],
874                        value_type: bind_library::ValueType::Number,
875                        extends: false,
876                        values: vec![],
877                    }],
878                },
879                bind_library::Ast {
880                    name: make_identifier!("lib_b"),
881                    using: vec![],
882                    declarations: vec![bind_library::Declaration {
883                        identifier: make_identifier!["symbol"],
884                        value_type: bind_library::ValueType::Number,
885                        extends: false,
886                        values: vec![],
887                    }],
888                },
889            ];
890
891            let st = construct_symbol_table(libraries.iter(), HashMap::new()).unwrap();
892            assert_eq!(
893                st.get(&make_identifier!("lib_a", "symbol")),
894                Some(&Symbol::Key("lib_a.symbol".to_string(), bind_library::ValueType::Number))
895            );
896            assert_eq!(
897                st.get(&make_identifier!("lib_b", "symbol")),
898                Some(&Symbol::Key("lib_b.symbol".to_string(), bind_library::ValueType::Number))
899            );
900        }
901
902        #[test]
903        fn missing_extend_keyword() {
904            // A library referring to a previously declared symbol must use the "extend" keyword.
905            let libraries = vec![
906                bind_library::Ast {
907                    name: make_identifier!("lib_a"),
908                    using: vec![],
909                    declarations: vec![bind_library::Declaration {
910                        identifier: make_identifier!["symbol"],
911                        value_type: bind_library::ValueType::Number,
912                        extends: false,
913                        values: vec![],
914                    }],
915                },
916                bind_library::Ast {
917                    name: make_identifier!("lib_b"),
918                    using: vec![],
919                    declarations: vec![bind_library::Declaration {
920                        identifier: make_identifier!["lib_a", "symbol"],
921                        value_type: bind_library::ValueType::Number,
922                        extends: false,
923                        values: vec![],
924                    }],
925                },
926            ];
927
928            assert_eq!(
929                construct_symbol_table(libraries.iter(), HashMap::new()),
930                Err(CompilerError::MissingExtendsKeyword(make_identifier!("lib_a", "symbol")))
931            );
932        }
933
934        #[test]
935        fn invalid_extend_keyword() {
936            // A library cannot declare an unqualified (and therefore locally namespaced) symbol
937            // with the "extend" keyword.
938            let libraries = vec![bind_library::Ast {
939                name: make_identifier!("lib_a"),
940                using: vec![],
941                declarations: vec![bind_library::Declaration {
942                    identifier: make_identifier!["symbol"],
943                    value_type: bind_library::ValueType::Number,
944                    extends: true,
945                    values: vec![],
946                }],
947            }];
948
949            assert_eq!(
950                construct_symbol_table(libraries.iter(), HashMap::new()),
951                Err(CompilerError::InvalidExtendsKeyword(make_identifier!("lib_a", "symbol")))
952            );
953        }
954
955        #[test]
956        fn unresolved_qualification() {
957            // A library cannot refer to a qualified identifier where the qualifier is not in its
958            // list of includes.
959            let libraries = vec![bind_library::Ast {
960                name: make_identifier!("lib_a"),
961                using: vec![],
962                declarations: vec![bind_library::Declaration {
963                    identifier: make_identifier!["lib_b", "symbol"],
964                    value_type: bind_library::ValueType::Number,
965                    extends: true,
966                    values: vec![],
967                }],
968            }];
969
970            assert_eq!(
971                construct_symbol_table(libraries.iter(), HashMap::new()),
972                Err(CompilerError::UnresolvedQualification(make_identifier!("lib_b", "symbol")))
973            );
974        }
975
976        #[test]
977        fn undeclared_key() {
978            let libraries = vec![
979                bind_library::Ast {
980                    name: make_identifier!("lib_a"),
981                    using: vec![],
982                    declarations: vec![],
983                },
984                bind_library::Ast {
985                    name: make_identifier!("lib_b"),
986                    using: vec![Include { name: make_identifier!("lib_a"), alias: None }],
987                    declarations: vec![bind_library::Declaration {
988                        identifier: make_identifier!["lib_a", "symbol"],
989                        value_type: bind_library::ValueType::Number,
990                        extends: true,
991                        values: vec![],
992                    }],
993                },
994            ];
995
996            assert_eq!(
997                construct_symbol_table(libraries.iter(), HashMap::new()),
998                Err(CompilerError::UndeclaredKey(make_identifier!("lib_a", "symbol")))
999            );
1000        }
1001
1002        #[test]
1003        fn type_mismatch() {
1004            let libraries = vec![
1005                bind_library::Ast {
1006                    name: make_identifier!("lib_a"),
1007                    using: vec![],
1008                    declarations: vec![bind_library::Declaration {
1009                        identifier: make_identifier!["symbol"],
1010                        value_type: bind_library::ValueType::Str,
1011                        extends: false,
1012                        values: vec![],
1013                    }],
1014                },
1015                bind_library::Ast {
1016                    name: make_identifier!("lib_b"),
1017                    using: vec![Include { name: make_identifier!("lib_a"), alias: None }],
1018                    declarations: vec![bind_library::Declaration {
1019                        identifier: make_identifier!["lib_a", "symbol"],
1020                        value_type: bind_library::ValueType::Number,
1021                        extends: true,
1022                        values: vec![],
1023                    }],
1024                },
1025            ];
1026
1027            assert_eq!(
1028                construct_symbol_table(libraries.iter(), HashMap::new()),
1029                Err(CompilerError::TypeMismatch(make_identifier!("lib_a", "symbol")))
1030            );
1031        }
1032    }
1033}
bind/compiler/symbol_table.rs

bind/compiler/
symbol_table.rs
