• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 use codespan_reporting::diagnostic::Diagnostic;
2 use codespan_reporting::files;
3 use codespan_reporting::term;
4 use codespan_reporting::term::termcolor;
5 use std::collections::HashMap;
6 
7 use crate::ast::*;
8 
9 /// Aggregate linter diagnostics.
10 pub struct LintDiagnostics {
11     pub diagnostics: Vec<Diagnostic<FileId>>,
12 }
13 
14 /// Implement lint checks for an AST element.
15 pub trait Lintable {
16     /// Generate lint warnings and errors for the
17     /// input element.
lint(&self) -> LintDiagnostics18     fn lint(&self) -> LintDiagnostics;
19 }
20 
21 /// Represents a chain of group expansion.
22 /// Each field but the last in the chain is a typedef field of a group.
23 /// The last field can also be a typedef field of a group if the chain is
24 /// not fully expanded.
25 #[derive(Clone)]
26 struct FieldPath<'d>(Vec<&'d Field>);
27 
28 /// Gather information about the full grammar declaration.
29 struct Scope<'d> {
30     // Collection of Group, Packet, Enum, Struct, Checksum, and CustomField declarations.
31     typedef: HashMap<String, &'d Decl>,
32 
33     // Collection of Packet, Struct, and Group scope declarations.
34     scopes: HashMap<&'d Decl, PacketScope<'d>>,
35 }
36 
37 /// Gather information about a Packet, Struct, or Group declaration.
38 struct PacketScope<'d> {
39     // Checksum starts, indexed by the checksum field id.
40     checksums: HashMap<String, FieldPath<'d>>,
41 
42     // Size or count fields, indexed by the field id.
43     sizes: HashMap<String, FieldPath<'d>>,
44 
45     // Payload or body field.
46     payload: Option<FieldPath<'d>>,
47 
48     // Typedef, scalar, array fields.
49     named: HashMap<String, FieldPath<'d>>,
50 
51     // Group fields.
52     groups: HashMap<String, &'d Field>,
53 
54     // Flattened field declarations.
55     // Contains field declarations from the original Packet, Struct, or Group,
56     // where Group fields have been substituted by their body.
57     // Constrained Scalar or Typedef Group fields are substitued by a Fixed
58     // field.
59     fields: Vec<FieldPath<'d>>,
60 
61     // Constraint declarations gathered from Group inlining.
62     constraints: HashMap<String, &'d Constraint>,
63 
64     // Local and inherited field declarations. Only named fields are preserved.
65     // Saved here for reference for parent constraint resolving.
66     all_fields: HashMap<String, &'d Field>,
67 
68     // Local and inherited constraint declarations.
69     // Saved here for constraint conflict checks.
70     all_constraints: HashMap<String, &'d Constraint>,
71 }
72 
73 impl std::cmp::Eq for &Decl {}
74 impl<'d> std::cmp::PartialEq for &'d Decl {
eq(&self, other: &Self) -> bool75     fn eq(&self, other: &Self) -> bool {
76         std::ptr::eq(*self, *other)
77     }
78 }
79 
80 impl<'d> std::hash::Hash for &'d Decl {
hash<H: std::hash::Hasher>(&self, state: &mut H)81     fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
82         std::ptr::hash(*self, state);
83     }
84 }
85 
86 impl FieldPath<'_> {
loc(&self) -> &SourceRange87     fn loc(&self) -> &SourceRange {
88         self.0.last().unwrap().loc()
89     }
90 }
91 
92 impl LintDiagnostics {
new() -> LintDiagnostics93     fn new() -> LintDiagnostics {
94         LintDiagnostics { diagnostics: vec![] }
95     }
96 
print( &self, sources: &SourceDatabase, color: termcolor::ColorChoice, ) -> Result<(), files::Error>97     pub fn print(
98         &self,
99         sources: &SourceDatabase,
100         color: termcolor::ColorChoice,
101     ) -> Result<(), files::Error> {
102         let writer = termcolor::StandardStream::stderr(color);
103         let config = term::Config::default();
104         for d in self.diagnostics.iter() {
105             term::emit(&mut writer.lock(), &config, sources, d)?;
106         }
107         Ok(())
108     }
109 
push(&mut self, diagnostic: Diagnostic<FileId>)110     fn push(&mut self, diagnostic: Diagnostic<FileId>) {
111         self.diagnostics.push(diagnostic)
112     }
113 
err_undeclared(&mut self, id: &str, loc: &SourceRange)114     fn err_undeclared(&mut self, id: &str, loc: &SourceRange) {
115         self.diagnostics.push(
116             Diagnostic::error()
117                 .with_message(format!("undeclared identifier `{}`", id))
118                 .with_labels(vec![loc.primary()]),
119         )
120     }
121 
err_redeclared(&mut self, id: &str, kind: &str, loc: &SourceRange, prev: &SourceRange)122     fn err_redeclared(&mut self, id: &str, kind: &str, loc: &SourceRange, prev: &SourceRange) {
123         self.diagnostics.push(
124             Diagnostic::error()
125                 .with_message(format!("redeclaration of {} identifier `{}`", kind, id))
126                 .with_labels(vec![
127                     loc.primary(),
128                     prev.secondary().with_message(format!("`{}` is first declared here", id)),
129                 ]),
130         )
131     }
132 }
133 
bit_width(val: usize) -> usize134 fn bit_width(val: usize) -> usize {
135     usize::BITS as usize - val.leading_zeros() as usize
136 }
137 
138 impl<'d> PacketScope<'d> {
139     /// Insert a field declaration into a packet scope.
insert(&mut self, field: &'d Field, result: &mut LintDiagnostics)140     fn insert(&mut self, field: &'d Field, result: &mut LintDiagnostics) {
141         match field {
142             Field::Checksum { loc, field_id, .. } => {
143                 self.checksums.insert(field_id.clone(), FieldPath(vec![field])).map(|prev| {
144                     result.push(
145                         Diagnostic::error()
146                             .with_message(format!(
147                                 "redeclaration of checksum start for `{}`",
148                                 field_id
149                             ))
150                             .with_labels(vec![
151                                 loc.primary(),
152                                 prev.loc()
153                                     .secondary()
154                                     .with_message("checksum start is first declared here"),
155                             ]),
156                     )
157                 })
158             }
159 
160             Field::Padding { .. } | Field::Reserved { .. } | Field::Fixed { .. } => None,
161 
162             Field::Size { loc, field_id, .. } | Field::Count { loc, field_id, .. } => {
163                 self.sizes.insert(field_id.clone(), FieldPath(vec![field])).map(|prev| {
164                     result.push(
165                         Diagnostic::error()
166                             .with_message(format!(
167                                 "redeclaration of size or count for `{}`",
168                                 field_id
169                             ))
170                             .with_labels(vec![
171                                 loc.primary(),
172                                 prev.loc().secondary().with_message("size is first declared here"),
173                             ]),
174                     )
175                 })
176             }
177 
178             Field::Body { loc, .. } | Field::Payload { loc, .. } => {
179                 if let Some(prev) = self.payload.as_ref() {
180                     result.push(
181                         Diagnostic::error()
182                             .with_message("redeclaration of payload or body field")
183                             .with_labels(vec![
184                                 loc.primary(),
185                                 prev.loc()
186                                     .secondary()
187                                     .with_message("payload is first declared here"),
188                             ]),
189                     )
190                 }
191                 self.payload = Some(FieldPath(vec![field]));
192                 None
193             }
194 
195             Field::Array { loc, id, .. }
196             | Field::Scalar { loc, id, .. }
197             | Field::Typedef { loc, id, .. } => self
198                 .named
199                 .insert(id.clone(), FieldPath(vec![field]))
200                 .map(|prev| result.err_redeclared(id, "field", loc, prev.loc())),
201 
202             Field::Group { loc, group_id, .. } => {
203                 self.groups.insert(group_id.clone(), field).map(|prev| {
204                     result.push(
205                         Diagnostic::error()
206                             .with_message(format!("duplicate group `{}` insertion", group_id))
207                             .with_labels(vec![
208                                 loc.primary(),
209                                 prev.loc()
210                                     .secondary()
211                                     .with_message(format!("`{}` is first used here", group_id)),
212                             ]),
213                     )
214                 })
215             }
216         };
217     }
218 
219     /// Add parent fields and constraints to the scope.
220     /// Only named fields are imported.
inherit( &mut self, scope: &Scope, parent: &PacketScope<'d>, constraints: impl Iterator<Item = &'d Constraint>, result: &mut LintDiagnostics, )221     fn inherit(
222         &mut self,
223         scope: &Scope,
224         parent: &PacketScope<'d>,
225         constraints: impl Iterator<Item = &'d Constraint>,
226         result: &mut LintDiagnostics,
227     ) {
228         // Check constraints.
229         assert!(self.all_constraints.is_empty());
230         self.all_constraints = parent.all_constraints.clone();
231         for constraint in constraints {
232             lint_constraint(scope, parent, constraint, result);
233             let id = constraint.id.clone();
234             if let Some(prev) = self.all_constraints.insert(id, constraint) {
235                 result.push(
236                     Diagnostic::error()
237                         .with_message(format!("duplicate constraint on field `{}`", constraint.id))
238                         .with_labels(vec![
239                             constraint.loc.primary(),
240                             prev.loc.secondary().with_message("the constraint is first set here"),
241                         ]),
242                 )
243             }
244         }
245 
246         // Merge group constraints into parent constraints,
247         // but generate no duplication warnings, the constraints
248         // do no apply to the same field set.
249         for (id, constraint) in self.constraints.iter() {
250             self.all_constraints.insert(id.clone(), constraint);
251         }
252 
253         // Save parent fields.
254         self.all_fields = parent.all_fields.clone();
255     }
256 
257     /// Insert group field declarations into a packet scope.
inline( &mut self, scope: &Scope, packet_scope: &PacketScope<'d>, group: &'d Field, constraints: impl Iterator<Item = &'d Constraint>, result: &mut LintDiagnostics, )258     fn inline(
259         &mut self,
260         scope: &Scope,
261         packet_scope: &PacketScope<'d>,
262         group: &'d Field,
263         constraints: impl Iterator<Item = &'d Constraint>,
264         result: &mut LintDiagnostics,
265     ) {
266         fn err_redeclared_by_group(
267             result: &mut LintDiagnostics,
268             message: impl Into<String>,
269             loc: &SourceRange,
270             prev: &SourceRange,
271         ) {
272             result.push(Diagnostic::error().with_message(message).with_labels(vec![
273                 loc.primary(),
274                 prev.secondary().with_message("first declared here"),
275             ]))
276         }
277 
278         for (id, field) in packet_scope.checksums.iter() {
279             if let Some(prev) = self.checksums.insert(id.clone(), field.clone()) {
280                 err_redeclared_by_group(
281                     result,
282                     format!("inserted group redeclares checksum start for `{}`", id),
283                     group.loc(),
284                     prev.loc(),
285                 )
286             }
287         }
288         for (id, field) in packet_scope.sizes.iter() {
289             if let Some(prev) = self.sizes.insert(id.clone(), field.clone()) {
290                 err_redeclared_by_group(
291                     result,
292                     format!("inserted group redeclares size or count for `{}`", id),
293                     group.loc(),
294                     prev.loc(),
295                 )
296             }
297         }
298         match (&self.payload, &packet_scope.payload) {
299             (Some(prev), Some(next)) => err_redeclared_by_group(
300                 result,
301                 "inserted group redeclares payload or body field",
302                 next.loc(),
303                 prev.loc(),
304             ),
305             (None, Some(payload)) => self.payload = Some(payload.clone()),
306             _ => (),
307         }
308         for (id, field) in packet_scope.named.iter() {
309             let mut path = vec![group];
310             path.extend(field.0.clone());
311             if let Some(prev) = self.named.insert(id.clone(), FieldPath(path)) {
312                 err_redeclared_by_group(
313                     result,
314                     format!("inserted group redeclares field `{}`", id),
315                     group.loc(),
316                     prev.loc(),
317                 )
318             }
319         }
320 
321         // Append group fields to the finalizeed fields.
322         for field in packet_scope.fields.iter() {
323             let mut path = vec![group];
324             path.extend(field.0.clone());
325             self.fields.push(FieldPath(path));
326         }
327 
328         // Append group constraints to the caller packet_scope.
329         for (id, constraint) in packet_scope.constraints.iter() {
330             self.constraints.insert(id.clone(), constraint);
331         }
332 
333         // Add constraints to the packet_scope, checking for duplicate constraints.
334         for constraint in constraints {
335             lint_constraint(scope, packet_scope, constraint, result);
336             let id = constraint.id.clone();
337             if let Some(prev) = self.constraints.insert(id, constraint) {
338                 result.push(
339                     Diagnostic::error()
340                         .with_message(format!("duplicate constraint on field `{}`", constraint.id))
341                         .with_labels(vec![
342                             constraint.loc.primary(),
343                             prev.loc.secondary().with_message("the constraint is first set here"),
344                         ]),
345                 )
346             }
347         }
348     }
349 
350     /// Cleanup scope after processing all fields.
finalize(&mut self, result: &mut LintDiagnostics)351     fn finalize(&mut self, result: &mut LintDiagnostics) {
352         // Check field shadowing.
353         for f in self.fields.iter().map(|f| f.0.last().unwrap()) {
354             if let Some(id) = f.id() {
355                 if let Some(prev) = self.all_fields.insert(id.clone(), f) {
356                     result.push(
357                         Diagnostic::warning()
358                             .with_message(format!("declaration of `{}` shadows parent field", id))
359                             .with_labels(vec![
360                                 f.loc().primary(),
361                                 prev.loc()
362                                     .secondary()
363                                     .with_message(format!("`{}` is first declared here", id)),
364                             ]),
365                     )
366                 }
367             }
368         }
369     }
370 }
371 
372 /// Helper for linting value constraints over packet fields.
lint_constraint( scope: &Scope, packet_scope: &PacketScope, constraint: &Constraint, result: &mut LintDiagnostics, )373 fn lint_constraint(
374     scope: &Scope,
375     packet_scope: &PacketScope,
376     constraint: &Constraint,
377     result: &mut LintDiagnostics,
378 ) {
379     // Validate constraint value types.
380     match (packet_scope.all_fields.get(&constraint.id), &constraint.value) {
381         (
382             Some(Field::Scalar { loc: field_loc, width, .. }),
383             Expr::Integer { value, loc: value_loc, .. },
384         ) => {
385             if bit_width(*value) > *width {
386                 result.push(
387                     Diagnostic::error().with_message("invalid integer literal").with_labels(vec![
388                         value_loc.primary().with_message(format!(
389                             "expected maximum value of `{}`",
390                             (1 << *width) - 1
391                         )),
392                         field_loc.secondary().with_message("the value is used here"),
393                     ]),
394                 )
395             }
396         }
397 
398         (Some(Field::Typedef { type_id, loc: field_loc, .. }), _) => {
399             match (scope.typedef.get(type_id), &constraint.value) {
400                 (Some(Decl::Enum { tags, .. }), Expr::Identifier { name, loc: name_loc, .. }) => {
401                     if !tags.iter().any(|t| &t.id == name) {
402                         result.push(
403                             Diagnostic::error()
404                                 .with_message(format!("undeclared enum tag `{}`", name))
405                                 .with_labels(vec![
406                                     name_loc.primary(),
407                                     field_loc.secondary().with_message("the value is used here"),
408                                 ]),
409                         )
410                     }
411                 }
412                 (Some(Decl::Enum { .. }), _) => result.push(
413                     Diagnostic::error().with_message("invalid literal type").with_labels(vec![
414                         constraint
415                             .loc
416                             .primary()
417                             .with_message(format!("expected `{}` tag identifier", type_id)),
418                         field_loc.secondary().with_message("the value is used here"),
419                     ]),
420                 ),
421                 (Some(decl), _) => result.push(
422                     Diagnostic::error().with_message("invalid constraint").with_labels(vec![
423                         constraint.loc.primary(),
424                         field_loc.secondary().with_message(format!(
425                             "`{}` has type {}, expected enum field",
426                             constraint.id,
427                             decl.kind()
428                         )),
429                     ]),
430                 ),
431                 // This error will be reported during field linting
432                 (None, _) => (),
433             }
434         }
435 
436         (Some(Field::Scalar { loc: field_loc, .. }), _) => {
437             result.push(Diagnostic::error().with_message("invalid literal type").with_labels(vec![
438                 constraint.loc.primary().with_message("expected integer literal"),
439                 field_loc.secondary().with_message("the value is used here"),
440             ]))
441         }
442         (Some(_), _) => unreachable!(),
443         (None, _) => result.push(
444             Diagnostic::error()
445                 .with_message(format!("undeclared identifier `{}`", constraint.id))
446                 .with_labels(vec![constraint.loc.primary()]),
447         ),
448     }
449 }
450 
451 impl<'d> Scope<'d> {
452     // Sort Packet, Struct, and Group declarations by reverse topological
453     // orde, and inline Group fields.
454     // Raises errors and warnings for:
455     //      - undeclared included Groups,
456     //      - undeclared Typedef fields,
457     //      - undeclared Packet or Struct parents,
458     //      - recursive Group insertion,
459     //      - recursive Packet or Struct inheritance.
finalize(&mut self, result: &mut LintDiagnostics) -> Vec<&'d Decl>460     fn finalize(&mut self, result: &mut LintDiagnostics) -> Vec<&'d Decl> {
461         // Auxiliary function implementing BFS on Packet tree.
462         enum Mark {
463             Temporary,
464             Permanent,
465         }
466         struct Context<'d> {
467             list: Vec<&'d Decl>,
468             visited: HashMap<&'d Decl, Mark>,
469             scopes: HashMap<&'d Decl, PacketScope<'d>>,
470         }
471 
472         fn bfs<'s, 'd>(
473             decl: &'d Decl,
474             context: &'s mut Context<'d>,
475             scope: &Scope<'d>,
476             result: &mut LintDiagnostics,
477         ) -> Option<&'s PacketScope<'d>> {
478             match context.visited.get(&decl) {
479                 Some(Mark::Permanent) => return context.scopes.get(&decl),
480                 Some(Mark::Temporary) => {
481                     result.push(
482                         Diagnostic::error()
483                             .with_message(format!(
484                                 "recursive declaration of {} `{}`",
485                                 decl.kind(),
486                                 decl.id().unwrap()
487                             ))
488                             .with_labels(vec![decl.loc().primary()]),
489                     );
490                     return None;
491                 }
492                 _ => (),
493             }
494 
495             let (parent_id, fields) = match decl {
496                 Decl::Packet { parent_id, fields, .. } | Decl::Struct { parent_id, fields, .. } => {
497                     (parent_id.as_ref(), fields)
498                 }
499                 Decl::Group { fields, .. } => (None, fields),
500                 _ => return None,
501             };
502 
503             context.visited.insert(decl, Mark::Temporary);
504             let mut lscope = decl.scope(result).unwrap();
505 
506             // Iterate over Struct and Group fields.
507             for f in fields {
508                 match f {
509                     Field::Group { group_id, constraints, .. } => {
510                         match scope.typedef.get(group_id) {
511                             None => result.push(
512                                 Diagnostic::error()
513                                     .with_message(format!(
514                                         "undeclared group identifier `{}`",
515                                         group_id
516                                     ))
517                                     .with_labels(vec![f.loc().primary()]),
518                             ),
519                             Some(group_decl @ Decl::Group { .. }) => {
520                                 // Recurse to flatten the inserted group.
521                                 if let Some(rscope) = bfs(group_decl, context, scope, result) {
522                                     // Inline the group fields and constraints into
523                                     // the current scope.
524                                     lscope.inline(scope, rscope, f, constraints.iter(), result)
525                                 }
526                             }
527                             Some(_) => result.push(
528                                 Diagnostic::error()
529                                     .with_message(format!(
530                                         "invalid group field identifier `{}`",
531                                         group_id
532                                     ))
533                                     .with_labels(vec![f.loc().primary()])
534                                     .with_notes(vec!["hint: expected group identifier".to_owned()]),
535                             ),
536                         }
537                     }
538                     Field::Typedef { type_id, .. } => {
539                         lscope.fields.push(FieldPath(vec![f]));
540                         match scope.typedef.get(type_id) {
541                             None => result.push(
542                                 Diagnostic::error()
543                                     .with_message(format!(
544                                         "undeclared typedef identifier `{}`",
545                                         type_id
546                                     ))
547                                     .with_labels(vec![f.loc().primary()]),
548                             ),
549                             Some(struct_decl @ Decl::Struct { .. }) => {
550                                 bfs(struct_decl, context, scope, result);
551                             }
552                             Some(_) => (),
553                         }
554                     }
555                     _ => lscope.fields.push(FieldPath(vec![f])),
556                 }
557             }
558 
559             // Iterate over parent declaration.
560             let parent = parent_id.and_then(|id| scope.typedef.get(id));
561             match (decl, parent) {
562                 (Decl::Packet { parent_id: Some(_), .. }, None)
563                 | (Decl::Struct { parent_id: Some(_), .. }, None) => result.push(
564                     Diagnostic::error()
565                         .with_message(format!(
566                             "undeclared parent identifier `{}`",
567                             parent_id.unwrap()
568                         ))
569                         .with_labels(vec![decl.loc().primary()])
570                         .with_notes(vec![format!("hint: expected {} parent", decl.kind())]),
571                 ),
572                 (Decl::Packet { .. }, Some(Decl::Struct { .. }))
573                 | (Decl::Struct { .. }, Some(Decl::Packet { .. })) => result.push(
574                     Diagnostic::error()
575                         .with_message(format!("invalid parent identifier `{}`", parent_id.unwrap()))
576                         .with_labels(vec![decl.loc().primary()])
577                         .with_notes(vec![format!("hint: expected {} parent", decl.kind())]),
578                 ),
579                 (_, Some(parent_decl)) => {
580                     if let Some(rscope) = bfs(parent_decl, context, scope, result) {
581                         // Import the parent fields and constraints into the current scope.
582                         lscope.inherit(scope, rscope, decl.constraints(), result)
583                     }
584                 }
585                 _ => (),
586             }
587 
588             lscope.finalize(result);
589             context.list.push(decl);
590             context.visited.insert(decl, Mark::Permanent);
591             context.scopes.insert(decl, lscope);
592             context.scopes.get(&decl)
593         }
594 
595         let mut context =
596             Context::<'d> { list: vec![], visited: HashMap::new(), scopes: HashMap::new() };
597 
598         for decl in self.typedef.values() {
599             bfs(decl, &mut context, self, result);
600         }
601 
602         self.scopes = context.scopes;
603         context.list
604     }
605 }
606 
607 impl Field {
kind(&self) -> &str608     fn kind(&self) -> &str {
609         match self {
610             Field::Checksum { .. } => "payload",
611             Field::Padding { .. } => "padding",
612             Field::Size { .. } => "size",
613             Field::Count { .. } => "count",
614             Field::Body { .. } => "body",
615             Field::Payload { .. } => "payload",
616             Field::Fixed { .. } => "fixed",
617             Field::Reserved { .. } => "reserved",
618             Field::Group { .. } => "group",
619             Field::Array { .. } => "array",
620             Field::Scalar { .. } => "scalar",
621             Field::Typedef { .. } => "typedef",
622         }
623     }
624 }
625 
626 // Helper for linting an enum declaration.
lint_enum(tags: &[Tag], width: usize, result: &mut LintDiagnostics)627 fn lint_enum(tags: &[Tag], width: usize, result: &mut LintDiagnostics) {
628     let mut local_scope = HashMap::new();
629     for tag in tags {
630         // Tags must be unique within the scope of the
631         // enum declaration.
632         if let Some(prev) = local_scope.insert(tag.id.clone(), tag) {
633             result.push(
634                 Diagnostic::error()
635                     .with_message(format!("redeclaration of tag identifier `{}`", &tag.id))
636                     .with_labels(vec![
637                         tag.loc.primary(),
638                         prev.loc.secondary().with_message("first declared here"),
639                     ]),
640             )
641         }
642 
643         // Tag values must fit the enum declared width.
644         if bit_width(tag.value) > width {
645             result.push(Diagnostic::error().with_message("invalid literal value").with_labels(
646                 vec![tag.loc.primary().with_message(format!(
647                         "expected maximum value of `{}`",
648                         (1 << width) - 1
649                     ))],
650             ))
651         }
652     }
653 }
654 
655 // Helper for linting checksum fields.
lint_checksum( scope: &Scope, packet_scope: &PacketScope, path: &FieldPath, field_id: &str, result: &mut LintDiagnostics, )656 fn lint_checksum(
657     scope: &Scope,
658     packet_scope: &PacketScope,
659     path: &FieldPath,
660     field_id: &str,
661     result: &mut LintDiagnostics,
662 ) {
663     // Checksum field must be declared before
664     // the checksum start. The field must be a typedef with
665     // a valid checksum type.
666     let checksum_loc = path.loc();
667     let field_decl = packet_scope.named.get(field_id);
668 
669     match field_decl.and_then(|f| f.0.last()) {
670         Some(Field::Typedef { loc: field_loc, type_id, .. }) => {
671             // Check declaration type of checksum field.
672             match scope.typedef.get(type_id) {
673                 Some(Decl::Checksum { .. }) => (),
674                 Some(decl) => result.push(
675                     Diagnostic::error()
676                         .with_message(format!("checksum start uses invalid field `{}`", field_id))
677                         .with_labels(vec![
678                             checksum_loc.primary(),
679                             field_loc.secondary().with_message(format!(
680                                 "`{}` is declared with {} type `{}`, expected checksum_field",
681                                 field_id,
682                                 decl.kind(),
683                                 type_id
684                             )),
685                         ]),
686                 ),
687                 // This error case will be reported when the field itself
688                 // is checked.
689                 None => (),
690             };
691             // Check declaration order of checksum field.
692             match field_decl.and_then(|f| f.0.first()) {
693                 Some(decl) if decl.loc().start > checksum_loc.start => result.push(
694                     Diagnostic::error()
695                         .with_message("invalid checksum start declaration")
696                         .with_labels(vec![
697                             checksum_loc
698                                 .primary()
699                                 .with_message("checksum start precedes checksum field"),
700                             decl.loc().secondary().with_message("checksum field is declared here"),
701                         ]),
702                 ),
703                 _ => (),
704             }
705         }
706         Some(field) => result.push(
707             Diagnostic::error()
708                 .with_message(format!("checksum start uses invalid field `{}`", field_id))
709                 .with_labels(vec![
710                     checksum_loc.primary(),
711                     field.loc().secondary().with_message(format!(
712                         "`{}` is declared as {} field, expected typedef",
713                         field_id,
714                         field.kind()
715                     )),
716                 ]),
717         ),
718         None => result.err_undeclared(field_id, checksum_loc),
719     }
720 }
721 
722 // Helper for linting size fields.
lint_size( _scope: &Scope, packet_scope: &PacketScope, path: &FieldPath, field_id: &str, _width: usize, result: &mut LintDiagnostics, )723 fn lint_size(
724     _scope: &Scope,
725     packet_scope: &PacketScope,
726     path: &FieldPath,
727     field_id: &str,
728     _width: usize,
729     result: &mut LintDiagnostics,
730 ) {
731     // Size fields should be declared before
732     // the sized field (body, payload, or array).
733     // The field must reference a valid body, payload or array
734     // field.
735 
736     let size_loc = path.loc();
737 
738     if field_id == "_payload_" {
739         return match packet_scope.payload.as_ref().and_then(|f| f.0.last()) {
740             Some(Field::Body { .. }) => result.push(
741                 Diagnostic::error()
742                     .with_message("size field uses undeclared payload field, did you mean _body_ ?")
743                     .with_labels(vec![size_loc.primary()]),
744             ),
745             Some(Field::Payload { .. }) => {
746                 match packet_scope.payload.as_ref().and_then(|f| f.0.first()) {
747                     Some(field) if field.loc().start < size_loc.start => result.push(
748                         Diagnostic::error().with_message("invalid size field").with_labels(vec![
749                             size_loc
750                                 .primary()
751                                 .with_message("size field is declared after payload field"),
752                             field.loc().secondary().with_message("payload field is declared here"),
753                         ]),
754                     ),
755                     _ => (),
756                 }
757             }
758             Some(_) => unreachable!(),
759             None => result.push(
760                 Diagnostic::error()
761                     .with_message("size field uses undeclared payload field")
762                     .with_labels(vec![size_loc.primary()]),
763             ),
764         };
765     }
766     if field_id == "_body_" {
767         return match packet_scope.payload.as_ref().and_then(|f| f.0.last()) {
768             Some(Field::Payload { .. }) => result.push(
769                 Diagnostic::error()
770                     .with_message("size field uses undeclared body field, did you mean _payload_ ?")
771                     .with_labels(vec![size_loc.primary()]),
772             ),
773             Some(Field::Body { .. }) => {
774                 match packet_scope.payload.as_ref().and_then(|f| f.0.first()) {
775                     Some(field) if field.loc().start < size_loc.start => result.push(
776                         Diagnostic::error().with_message("invalid size field").with_labels(vec![
777                             size_loc
778                                 .primary()
779                                 .with_message("size field is declared after body field"),
780                             field.loc().secondary().with_message("body field is declared here"),
781                         ]),
782                     ),
783                     _ => (),
784                 }
785             }
786             Some(_) => unreachable!(),
787             None => result.push(
788                 Diagnostic::error()
789                     .with_message("size field uses undeclared body field")
790                     .with_labels(vec![size_loc.primary()]),
791             ),
792         };
793     }
794 
795     let field = packet_scope.named.get(field_id);
796 
797     match field.and_then(|f| f.0.last()) {
798         Some(Field::Array { size: Some(_), loc: array_loc, .. }) => result.push(
799             Diagnostic::warning()
800                 .with_message(format!("size field uses array `{}` with static size", field_id))
801                 .with_labels(vec![
802                     size_loc.primary(),
803                     array_loc.secondary().with_message(format!("`{}` is declared here", field_id)),
804                 ]),
805         ),
806         Some(Field::Array { .. }) => (),
807         Some(field) => result.push(
808             Diagnostic::error()
809                 .with_message(format!("invalid `{}` field type", field_id))
810                 .with_labels(vec![
811                     field.loc().primary().with_message(format!(
812                         "`{}` is declared as {}",
813                         field_id,
814                         field.kind()
815                     )),
816                     size_loc
817                         .secondary()
818                         .with_message(format!("`{}` is used here as array", field_id)),
819                 ]),
820         ),
821 
822         None => result.err_undeclared(field_id, size_loc),
823     };
824     match field.and_then(|f| f.0.first()) {
825         Some(field) if field.loc().start < size_loc.start => {
826             result.push(Diagnostic::error().with_message("invalid size field").with_labels(vec![
827                     size_loc
828                         .primary()
829                         .with_message(format!("size field is declared after field `{}`", field_id)),
830                     field
831                         .loc()
832                         .secondary()
833                         .with_message(format!("`{}` is declared here", field_id)),
834                 ]))
835         }
836         _ => (),
837     }
838 }
839 
840 // Helper for linting count fields.
lint_count( _scope: &Scope, packet_scope: &PacketScope, path: &FieldPath, field_id: &str, _width: usize, result: &mut LintDiagnostics, )841 fn lint_count(
842     _scope: &Scope,
843     packet_scope: &PacketScope,
844     path: &FieldPath,
845     field_id: &str,
846     _width: usize,
847     result: &mut LintDiagnostics,
848 ) {
849     // Count fields should be declared before the sized field.
850     // The field must reference a valid array field.
851     // Warning if the array already has a known size.
852 
853     let count_loc = path.loc();
854     let field = packet_scope.named.get(field_id);
855 
856     match field.and_then(|f| f.0.last()) {
857         Some(Field::Array { size: Some(_), loc: array_loc, .. }) => result.push(
858             Diagnostic::warning()
859                 .with_message(format!("count field uses array `{}` with static size", field_id))
860                 .with_labels(vec![
861                     count_loc.primary(),
862                     array_loc.secondary().with_message(format!("`{}` is declared here", field_id)),
863                 ]),
864         ),
865 
866         Some(Field::Array { .. }) => (),
867         Some(field) => result.push(
868             Diagnostic::error()
869                 .with_message(format!("invalid `{}` field type", field_id))
870                 .with_labels(vec![
871                     field.loc().primary().with_message(format!(
872                         "`{}` is declared as {}",
873                         field_id,
874                         field.kind()
875                     )),
876                     count_loc
877                         .secondary()
878                         .with_message(format!("`{}` is used here as array", field_id)),
879                 ]),
880         ),
881 
882         None => result.err_undeclared(field_id, count_loc),
883     };
884     match field.and_then(|f| f.0.first()) {
885         Some(field) if field.loc().start < count_loc.start => {
886             result.push(Diagnostic::error().with_message("invalid count field").with_labels(vec![
887                     count_loc.primary().with_message(format!(
888                         "count field is declared after field `{}`",
889                         field_id
890                     )),
891                     field
892                         .loc()
893                         .secondary()
894                         .with_message(format!("`{}` is declared here", field_id)),
895                 ]))
896         }
897         _ => (),
898     }
899 }
900 
901 // Helper for linting fixed fields.
902 #[allow(clippy::too_many_arguments)]
lint_fixed( scope: &Scope, _packet_scope: &PacketScope, path: &FieldPath, width: &Option<usize>, value: &Option<usize>, enum_id: &Option<String>, tag_id: &Option<String>, result: &mut LintDiagnostics, )903 fn lint_fixed(
904     scope: &Scope,
905     _packet_scope: &PacketScope,
906     path: &FieldPath,
907     width: &Option<usize>,
908     value: &Option<usize>,
909     enum_id: &Option<String>,
910     tag_id: &Option<String>,
911     result: &mut LintDiagnostics,
912 ) {
913     // By parsing constraint, we already have that either
914     // (width and value) or (enum_id and tag_id) are Some.
915 
916     let fixed_loc = path.loc();
917 
918     if width.is_some() {
919         // The value of a fixed field should have .
920         if bit_width(value.unwrap()) > width.unwrap() {
921             result.push(Diagnostic::error().with_message("invalid integer literal").with_labels(
922                 vec![fixed_loc.primary().with_message(format!(
923                     "expected maximum value of `{}`",
924                     (1 << width.unwrap()) - 1
925                 ))],
926             ))
927         }
928     } else {
929         // The fixed field should reference a valid enum id and tag id
930         // association.
931         match scope.typedef.get(enum_id.as_ref().unwrap()) {
932             Some(Decl::Enum { tags, .. }) => {
933                 match tags.iter().find(|t| &t.id == tag_id.as_ref().unwrap()) {
934                     Some(_) => (),
935                     None => result.push(
936                         Diagnostic::error()
937                             .with_message(format!(
938                                 "undeclared enum tag `{}`",
939                                 tag_id.as_ref().unwrap()
940                             ))
941                             .with_labels(vec![fixed_loc.primary()]),
942                     ),
943                 }
944             }
945             Some(decl) => result.push(
946                 Diagnostic::error()
947                     .with_message(format!(
948                         "fixed field uses invalid typedef `{}`",
949                         decl.id().unwrap()
950                     ))
951                     .with_labels(vec![fixed_loc.primary().with_message(format!(
952                         "{} has kind {}, expected enum",
953                         decl.id().unwrap(),
954                         decl.kind(),
955                     ))]),
956             ),
957             None => result.push(
958                 Diagnostic::error()
959                     .with_message(format!("undeclared enum type `{}`", enum_id.as_ref().unwrap()))
960                     .with_labels(vec![fixed_loc.primary()]),
961             ),
962         }
963     }
964 }
965 
966 // Helper for linting array fields.
967 #[allow(clippy::too_many_arguments)]
lint_array( scope: &Scope, _packet_scope: &PacketScope, path: &FieldPath, _width: &Option<usize>, type_id: &Option<String>, _size_modifier: &Option<String>, _size: &Option<usize>, result: &mut LintDiagnostics, )968 fn lint_array(
969     scope: &Scope,
970     _packet_scope: &PacketScope,
971     path: &FieldPath,
972     _width: &Option<usize>,
973     type_id: &Option<String>,
974     _size_modifier: &Option<String>,
975     _size: &Option<usize>,
976     result: &mut LintDiagnostics,
977 ) {
978     // By parsing constraint, we have that width and type_id are mutually
979     // exclusive, as well as size_modifier and size.
980     // type_id must reference a valid enum or packet type.
981     // TODO(hchataing) unbounded arrays should have a matching size
982     // or count field
983 
984     let array_loc = path.loc();
985 
986     if type_id.is_some() {
987         match scope.typedef.get(type_id.as_ref().unwrap()) {
988             Some(Decl::Enum { .. })
989             | Some(Decl::Struct { .. })
990             | Some(Decl::CustomField { .. }) => (),
991             Some(decl) => result.push(
992                 Diagnostic::error()
993                     .with_message(format!(
994                         "array field uses invalid {} element type `{}`",
995                         decl.kind(),
996                         type_id.as_ref().unwrap()
997                     ))
998                     .with_labels(vec![array_loc.primary()])
999                     .with_notes(vec!["hint: expected enum, struct, custom_field".to_owned()]),
1000             ),
1001             None => result.push(
1002                 Diagnostic::error()
1003                     .with_message(format!(
1004                         "array field uses undeclared element type `{}`",
1005                         type_id.as_ref().unwrap()
1006                     ))
1007                     .with_labels(vec![array_loc.primary()])
1008                     .with_notes(vec!["hint: expected enum, struct, custom_field".to_owned()]),
1009             ),
1010         }
1011     }
1012 }
1013 
1014 // Helper for linting typedef fields.
lint_typedef( scope: &Scope, _packet_scope: &PacketScope, path: &FieldPath, type_id: &str, result: &mut LintDiagnostics, )1015 fn lint_typedef(
1016     scope: &Scope,
1017     _packet_scope: &PacketScope,
1018     path: &FieldPath,
1019     type_id: &str,
1020     result: &mut LintDiagnostics,
1021 ) {
1022     // The typedef field must reference a valid struct, enum,
1023     // custom_field, or checksum type.
1024     // TODO(hchataing) checksum fields should have a matching checksum start
1025 
1026     let typedef_loc = path.loc();
1027 
1028     match scope.typedef.get(type_id) {
1029         Some(Decl::Enum { .. })
1030         | Some(Decl::Struct { .. })
1031         | Some(Decl::CustomField { .. })
1032         | Some(Decl::Checksum { .. }) => (),
1033 
1034         Some(decl) => result.push(
1035             Diagnostic::error()
1036                 .with_message(format!(
1037                     "typedef field uses invalid {} element type `{}`",
1038                     decl.kind(),
1039                     type_id
1040                 ))
1041                 .with_labels(vec![typedef_loc.primary()])
1042                 .with_notes(vec!["hint: expected enum, struct, custom_field, checksum".to_owned()]),
1043         ),
1044         None => result.push(
1045             Diagnostic::error()
1046                 .with_message(format!("typedef field uses undeclared element type `{}`", type_id))
1047                 .with_labels(vec![typedef_loc.primary()])
1048                 .with_notes(vec!["hint: expected enum, struct, custom_field, checksum".to_owned()]),
1049         ),
1050     }
1051 }
1052 
1053 // Helper for linting a field declaration.
lint_field( scope: &Scope, packet_scope: &PacketScope, field: &FieldPath, result: &mut LintDiagnostics, )1054 fn lint_field(
1055     scope: &Scope,
1056     packet_scope: &PacketScope,
1057     field: &FieldPath,
1058     result: &mut LintDiagnostics,
1059 ) {
1060     match field.0.last().unwrap() {
1061         Field::Checksum { field_id, .. } => {
1062             lint_checksum(scope, packet_scope, field, field_id, result)
1063         }
1064         Field::Size { field_id, width, .. } => {
1065             lint_size(scope, packet_scope, field, field_id, *width, result)
1066         }
1067         Field::Count { field_id, width, .. } => {
1068             lint_count(scope, packet_scope, field, field_id, *width, result)
1069         }
1070         Field::Fixed { width, value, enum_id, tag_id, .. } => {
1071             lint_fixed(scope, packet_scope, field, width, value, enum_id, tag_id, result)
1072         }
1073         Field::Array { width, type_id, size_modifier, size, .. } => {
1074             lint_array(scope, packet_scope, field, width, type_id, size_modifier, size, result)
1075         }
1076         Field::Typedef { type_id, .. } => lint_typedef(scope, packet_scope, field, type_id, result),
1077         Field::Padding { .. }
1078         | Field::Reserved { .. }
1079         | Field::Scalar { .. }
1080         | Field::Body { .. }
1081         | Field::Payload { .. } => (),
1082         Field::Group { .. } => unreachable!(),
1083     }
1084 }
1085 
1086 // Helper for linting a packet declaration.
lint_packet( scope: &Scope, decl: &Decl, id: &str, loc: &SourceRange, constraints: &[Constraint], parent_id: &Option<String>, result: &mut LintDiagnostics, )1087 fn lint_packet(
1088     scope: &Scope,
1089     decl: &Decl,
1090     id: &str,
1091     loc: &SourceRange,
1092     constraints: &[Constraint],
1093     parent_id: &Option<String>,
1094     result: &mut LintDiagnostics,
1095 ) {
1096     // The parent declaration is checked by Scope::finalize.
1097     // The local scope is also generated by Scope::finalize.
1098     // TODO(hchataing) check parent payload size constraint: compute an upper
1099     // bound of the payload size and check against the encoded maximum size.
1100 
1101     if parent_id.is_none() && !constraints.is_empty() {
1102         // Constraint list should be empty when there is
1103         // no inheritance.
1104         result.push(
1105             Diagnostic::warning()
1106                 .with_message(format!(
1107                     "packet `{}` has field constraints, but no parent declaration",
1108                     id
1109                 ))
1110                 .with_labels(vec![loc.primary()])
1111                 .with_notes(vec!["hint: expected parent declaration".to_owned()]),
1112         )
1113     }
1114 
1115     // Retrieve pre-computed packet scope.
1116     // Scope validation was done before, so it must exist.
1117     let packet_scope = &scope.scopes.get(&decl).unwrap();
1118 
1119     for field in packet_scope.fields.iter() {
1120         lint_field(scope, packet_scope, field, result)
1121     }
1122 }
1123 
1124 // Helper for linting a struct declaration.
lint_struct( scope: &Scope, decl: &Decl, id: &str, loc: &SourceRange, constraints: &[Constraint], parent_id: &Option<String>, result: &mut LintDiagnostics, )1125 fn lint_struct(
1126     scope: &Scope,
1127     decl: &Decl,
1128     id: &str,
1129     loc: &SourceRange,
1130     constraints: &[Constraint],
1131     parent_id: &Option<String>,
1132     result: &mut LintDiagnostics,
1133 ) {
1134     // The parent declaration is checked by Scope::finalize.
1135     // The local scope is also generated by Scope::finalize.
1136     // TODO(hchataing) check parent payload size constraint: compute an upper
1137     // bound of the payload size and check against the encoded maximum size.
1138 
1139     if parent_id.is_none() && !constraints.is_empty() {
1140         // Constraint list should be empty when there is
1141         // no inheritance.
1142         result.push(
1143             Diagnostic::warning()
1144                 .with_message(format!(
1145                     "struct `{}` has field constraints, but no parent declaration",
1146                     id
1147                 ))
1148                 .with_labels(vec![loc.primary()])
1149                 .with_notes(vec!["hint: expected parent declaration".to_owned()]),
1150         )
1151     }
1152 
1153     // Retrieve pre-computed packet scope.
1154     // Scope validation was done before, so it must exist.
1155     let packet_scope = &scope.scopes.get(&decl).unwrap();
1156 
1157     for field in packet_scope.fields.iter() {
1158         lint_field(scope, packet_scope, field, result)
1159     }
1160 }
1161 
1162 impl Decl {
constraints(&self) -> impl Iterator<Item = &Constraint>1163     fn constraints(&self) -> impl Iterator<Item = &Constraint> {
1164         match self {
1165             Decl::Packet { constraints, .. } | Decl::Struct { constraints, .. } => {
1166                 Some(constraints.iter())
1167             }
1168             _ => None,
1169         }
1170         .into_iter()
1171         .flatten()
1172     }
1173 
scope<'d>(&'d self, result: &mut LintDiagnostics) -> Option<PacketScope<'d>>1174     fn scope<'d>(&'d self, result: &mut LintDiagnostics) -> Option<PacketScope<'d>> {
1175         match self {
1176             Decl::Packet { fields, .. }
1177             | Decl::Struct { fields, .. }
1178             | Decl::Group { fields, .. } => {
1179                 let mut scope = PacketScope {
1180                     checksums: HashMap::new(),
1181                     sizes: HashMap::new(),
1182                     payload: None,
1183                     named: HashMap::new(),
1184                     groups: HashMap::new(),
1185 
1186                     fields: Vec::new(),
1187                     constraints: HashMap::new(),
1188                     all_fields: HashMap::new(),
1189                     all_constraints: HashMap::new(),
1190                 };
1191                 for field in fields {
1192                     scope.insert(field, result)
1193                 }
1194                 Some(scope)
1195             }
1196             _ => None,
1197         }
1198     }
1199 
lint<'d>(&'d self, scope: &Scope<'d>, result: &mut LintDiagnostics)1200     fn lint<'d>(&'d self, scope: &Scope<'d>, result: &mut LintDiagnostics) {
1201         match self {
1202             Decl::Checksum { .. } | Decl::CustomField { .. } => (),
1203             Decl::Enum { tags, width, .. } => lint_enum(tags, *width, result),
1204             Decl::Packet { id, loc, constraints, parent_id, .. } => {
1205                 lint_packet(scope, self, id, loc, constraints, parent_id, result)
1206             }
1207             Decl::Struct { id, loc, constraints, parent_id, .. } => {
1208                 lint_struct(scope, self, id, loc, constraints, parent_id, result)
1209             }
1210             // Groups are finalizeed before linting, to make sure
1211             // potential errors are raised only once.
1212             Decl::Group { .. } => (),
1213             Decl::Test { .. } => (),
1214         }
1215     }
1216 
kind(&self) -> &str1217     fn kind(&self) -> &str {
1218         match self {
1219             Decl::Checksum { .. } => "checksum",
1220             Decl::CustomField { .. } => "custom field",
1221             Decl::Enum { .. } => "enum",
1222             Decl::Packet { .. } => "packet",
1223             Decl::Struct { .. } => "struct",
1224             Decl::Group { .. } => "group",
1225             Decl::Test { .. } => "test",
1226         }
1227     }
1228 }
1229 
1230 impl Grammar {
scope<'d>(&'d self, result: &mut LintDiagnostics) -> Scope<'d>1231     fn scope<'d>(&'d self, result: &mut LintDiagnostics) -> Scope<'d> {
1232         let mut scope = Scope { typedef: HashMap::new(), scopes: HashMap::new() };
1233 
1234         // Gather top-level declarations.
1235         // Validate the top-level scopes (Group, Packet, Typedef).
1236         //
1237         // TODO: switch to try_insert when stable
1238         for decl in &self.declarations {
1239             if let Some(id) = decl.id() {
1240                 if let Some(prev) = scope.typedef.insert(id.clone(), decl) {
1241                     result.err_redeclared(id, decl.kind(), decl.loc(), prev.loc())
1242                 }
1243             }
1244             if let Some(lscope) = decl.scope(result) {
1245                 scope.scopes.insert(decl, lscope);
1246             }
1247         }
1248 
1249         scope.finalize(result);
1250         scope
1251     }
1252 }
1253 
1254 impl Lintable for Grammar {
lint(&self) -> LintDiagnostics1255     fn lint(&self) -> LintDiagnostics {
1256         let mut result = LintDiagnostics::new();
1257         let scope = self.scope(&mut result);
1258         if !result.diagnostics.is_empty() {
1259             return result;
1260         }
1261         for decl in &self.declarations {
1262             decl.lint(&scope, &mut result)
1263         }
1264         result
1265     }
1266 }
1267 
1268 #[cfg(test)]
1269 mod test {
1270     use crate::ast::*;
1271     use crate::lint::Lintable;
1272     use crate::parser::parse_inline;
1273 
1274     macro_rules! grammar {
1275         ($db:expr, $text:literal) => {
1276             parse_inline($db, "stdin".to_owned(), $text.to_owned()).expect("parsing failure")
1277         };
1278     }
1279 
1280     #[test]
test_packet_redeclared()1281     fn test_packet_redeclared() {
1282         let mut db = SourceDatabase::new();
1283         let grammar = grammar!(
1284             &mut db,
1285             r#"
1286         little_endian_packets
1287         struct Name { }
1288         packet Name { }
1289         "#
1290         );
1291         let result = grammar.lint();
1292         assert!(!result.diagnostics.is_empty());
1293     }
1294 }
1295