5.12 Module graphs

Overview

Module graphs play a crucial role in Deno's underlying framework. To put it simply, a module graph is like a building block puzzle, connecting different pieces together to cover all the parts needed starting from the main module. The creation of this module graph happens step by step, like following a recipe to bake a cake. Let's take a closer look at each of these steps, so we can really grasp how it all comes together.

At its core, a module graph is like a map that shows how different modules depend on each other. Imagine you're planning a trip, and you need to figure out which cities you'll pass through to reach your destination. Similarly, Deno's module graph helps the system understand the journey of dependencies from the starting point, which is the root module.

Module graphs

In Deno, every module utilized within the application follows a process governed by module graphs. These graphs serve to retrieve, interpret, and uphold modules. The concept is quite straightforward: modules are incorporated into the graph based on their unique specifiers, and subsequently, the graph's nodes, representing modules, are traversed.

For an in-depth comprehension of these graphs, one can refer to the standard graph data structure. In our present illustration, we're dealing with a principal module that doesn't involve any additional imports. Thus, our graph is anticipated to comprise just a solitary node. However, our exploration into modules doesn't conclude here; the subsequent chapter goes into programs involving multiple modules.

This graph-building journey involves two fundamental phases:

1. Introduction of the main module:

   • Retrieval of the module

   • Integration into the graph

   • Addition to the list of modules pending processing

2. Iteration through pending modules:

   • Examination of the pending module

   • Parsing of the module

   • Iteration through its dependencies

   • Retrieval of these dependencies

In the beginning, the primary module is obtained and included in the graph. Following that, the graph is explored, beginning with the main module. Exploring a module includes examining its contents and retrieving any dependencies it has. This process occurs in a repeating pattern.

First, we'll explore the basic operations, including add, fetch, and visit. Then, we'll use a concrete example to illustrate how these functions work, providing a clearer understanding of their inner mechanics.

Fill

GraphBuilder.fill() serves the purpose of incorporating both the main module (known as the root module) and any accompanying dependencies into the structure. In real-world scenarios, the number of dependencies could be substantial, leading to the creation of complex graphs. Especially the cases when applications use dependencies from NPM, which in-turn, depends on tens of hundreds of modules/packages. This complexity emerges due to the interconnections among various components.

On the other hand, when we examine our uncomplicated "hello world" illustration, the graph assumes a straightforward form, featuring only a singular node. It's worth noting that as the application's scale and complexity increase, so does the intricacy of the graph, showcasing the interdependency of modules and components.

Here is the code of the fill function:

async fn fill(
    &mut self,
    roots: Vec<ModuleSpecifier>,
    imports: Vec<ReferrerImports>,
  ) {
    let roots = roots
      .into_iter()
      .filter(|r| !self.graph.roots.contains(r))
      .collect::<Vec<_>>();
    let imports = imports
      .into_iter()
      .filter(|r| !self.graph.imports.contains_key(&r.referrer))
      .collect::<Vec<_>>();
    self.graph.roots.extend(roots.clone());
    for root in roots {
      self.load(&root, None, self.in_dynamic_branch, None);
    }

    // Process any imports that are being added to the graph.
    for referrer_imports in imports {
      let referrer = referrer_imports.referrer;
      let imports = referrer_imports.imports;
      let graph_import = GraphImport::new(&referrer, imports, self.resolver);
      for dep in graph_import.dependencies.values() {
        if let Resolution::Ok(resolved) = &dep.maybe_type {
          self.load(
            &resolved.specifier,
            Some(&resolved.range),
            self.in_dynamic_branch,
            None,
          );
        }
      }
      self.graph.imports.insert(referrer, graph_import);
    }

    loop {
      let specifier = match self.pending.next().await {
        Some(PendingInfo {
          specifier,
          maybe_range,
          result,
        }) => match result {
          Ok(Some(response)) => {
            let assert_types =
              self.pending_specifiers.remove(&specifier).unwrap();
            for maybe_assert_type in assert_types {
              self.visit(
                &specifier,
                &response,
                maybe_assert_type,
                maybe_range.clone(),
              )
            }
            Some(specifier)
          }
          Ok(None) => {
            self.graph.module_slots.insert(
              specifier.clone(),
              ModuleSlot::Err(ModuleGraphError::ModuleError(
                ModuleError::Missing(specifier.clone(), maybe_range),
              )),
            );
            Some(specifier)
          }
          Err(err) => {
            self.graph.module_slots.insert(
              specifier.clone(),
              ModuleSlot::Err(ModuleGraphError::ModuleError(
                ModuleError::LoadingErr(
                  specifier.clone(),
                  maybe_range,
                  Arc::new(err),
                ),
              )),
            );
            Some(specifier)
          }
        },
        None => None,
      };
      if let (Some(specifier), Some(reporter)) = (specifier, self.reporter) {
        let modules_total = self.graph.module_slots.len();
        let modules_done = modules_total - self.pending.len();
        reporter.on_load(&specifier, modules_done, modules_total);
      }
      if self.pending.is_empty() {
        // Start visiting queued up dynamic branches. We do this in a separate
        // pass after all static dependencies have been visited because:
        // - If a module is both statically and dynamically imported, we want
        //   the static import to take precedence and only load it with
        //   `is_dynamic: false`.
        // - It's more convenient for tracking whether or not we are currently
        //   visiting a dynamic branch.
        if !self.in_dynamic_branch {
          self.in_dynamic_branch = true;
          for (specifier, (range, maybe_assert_type)) in
            std::mem::take(&mut self.dynamic_branches)
          {
            if !self.graph.module_slots.contains_key(&specifier) {
              self.load(&specifier, Some(&range), true, maybe_assert_type);
            }
          }
        } else {
          break;
        }
      }
    }

    // Enrich with cache info from the loader
    for slot in self.graph.module_slots.values_mut() {
      if let ModuleSlot::Module(ref mut module) = slot {
        match module {
          Module::Json(module) => {
            module.maybe_cache_info =
              self.loader.get_cache_info(&module.specifier);
          }
          Module::Esm(module) => {
            module.maybe_cache_info =
              self.loader.get_cache_info(&module.specifier);
          }
          Module::External(_) | Module::Npm(_) | Module::Node(_) => {}
        }
      }
    }

    // Now resolve any npm package requirements
    NpmSpecifierResolver::fill_builder(self).await;
  }

The role of the fill() function extends beyond simply adding the root or main module. This versatile function serves to incorporate various ES modules or NPM modules into the system. While the primary module establishes the graph's foundation, the fill() function accommodates any general ES module by integrating it as a dependency within the graph's structure.

A sequence of steps defines the fill() function's operation:

1. Commence by fetching/loading the root module.

2. Proceed through a loop until the pending list is devoid of items.

3. Process each pending item during traversal.

The loop contained within the fill() function persists until the pending list has been emptied. An absence of items within the pending list signifies the comprehensive recursive processing and integration of all dependencies into the graph. Consequently, the fill() function's conclusion marks the completion of the graph, encompassing all the incorporated modules. This meticulous process ensures that the graph embodies a coherent and interconnected representation of the modules, ready for utilization.

Visit

The "visit" function is a fundamental building block in constructing the module graph within Deno. Compared to the "fill" function, "visit" is more extensive in its role. Its purpose is to handle modules as they are encountered. This function is invoked for each individual module, a process initiated by the "add" function. This cycle of calling "visit" continues until the pending list of modules becomes empty.

The primary task of the "visit" function is to manage the processing of fetched modules. As modules are fetched and introduced into the workflow, the "visit" function takes charge of orchestrating their integration into the existing graph. This involves understanding their dependencies, connections to other modules, and their position within the broader context of the application. By effectively managing these aspects, the "visit" function contributes significantly to the overall structure and coherence of the module graph.

To provide a visual representation of how the "visit" function operates, a flowchart has been designed. This flowchart visually depicts the step-by-step process through which the "visit" function manages modules. This graphical representation offers insight into the sequential progression of actions undertaken by the "visit" function as it processes modules and integrates them into the module graph.

Let's take a closer look at the process step by step:

• It begins with visiting a module that has been fetched.

• The module is then parsed to understand its contents.

• Dependencies are examined one by one in an iterative manner.

This is where things start to become recursive. During the visiting process, all dependencies are fetched. When a dependency is fetched, it's marked for future consideration and placed in a pending list. The loop within the 'fill' function will keep running as long as there are items in the pending list. This loop ensures that all pending items are processed.

This iterative process continues until every node in the interconnected graph has been visited. In other words, the loop in the 'fill' function only concludes when all nodes in the graph have been covered.

Let's take a look at the source code for the 'visit' function:

fn visit(
    &mut self,
    requested_specifier: &ModuleSpecifier,
    response: &LoadResponse,
    maybe_assert_type: Option<AssertTypeWithRange>,
    maybe_referrer: Option<Range>,
  ) {
    let (specifier, module_slot) = match response {
      LoadResponse::External { specifier } => {
        self.check_specifier(requested_specifier, specifier);
        let module_slot =
          ModuleSlot::Module(Module::External(ExternalModule {
            specifier: specifier.clone(),
          }));
        (specifier, module_slot)
      }
      LoadResponse::Module {
        specifier,
        content,
        maybe_headers,
      } => {
        self.check_specifier(requested_specifier, specifier);
        (
          specifier,
          self.visit_module(
            specifier,
            maybe_headers.as_ref(),
            content.clone(),
            maybe_assert_type,
            maybe_referrer,
          ),
        )
      }
    };
    self
      .graph
      .module_slots
      .insert(specifier.clone(), module_slot);
  }

  /// Visit a module, parsing it and resolving any dependencies.
  fn visit_module(
    &mut self,
    specifier: &ModuleSpecifier,
    maybe_headers: Option<&HashMap<String, String>>,
    content: Arc<str>,
    maybe_assert_type: Option<AssertTypeWithRange>,
    maybe_referrer: Option<Range>,
  ) -> ModuleSlot {
    use std::borrow::BorrowMut;
    let is_root = self.roots_contain(specifier);

    let mut module_slot = match parse_module(
      specifier,
      maybe_headers,
      content,
      maybe_assert_type,
      maybe_referrer,
      self.resolver,
      self.module_analyzer,
      is_root,
      self.in_dynamic_branch,
    ) {
      Ok(module) => ModuleSlot::Module(module),
      Err(err) => ModuleSlot::Err(err),
    };

    if let ModuleSlot::Module(Module::Esm(module)) = module_slot.borrow_mut() {
      if matches!(self.graph.graph_kind, GraphKind::All | GraphKind::CodeOnly)
        || module.maybe_types_dependency.is_none()
      {
        for dep in module.dependencies.values_mut() {
          if matches!(
            self.graph.graph_kind,
            GraphKind::All | GraphKind::CodeOnly
          ) || dep.maybe_type.is_none()
          {
            if let Resolution::Ok(resolved) = &dep.maybe_code {
              let specifier = &resolved.specifier;
              let range = &resolved.range;
              let maybe_assert_type_with_range = dep
                .maybe_assert_type
                .as_ref()
                .map(|assert_type| AssertTypeWithRange {
                  range: range.clone(),
                  kind: assert_type.clone(),
                });
              if dep.is_dynamic && !self.in_dynamic_branch {
                self.dynamic_branches.insert(
                  specifier.clone(),
                  (range.clone(), maybe_assert_type_with_range),
                );
              } else {
                self.load(
                  specifier,
                  Some(range),
                  self.in_dynamic_branch,
                  maybe_assert_type_with_range,
                );
              }
            }
          } else {
            dep.maybe_code = Resolution::None;
          }

          if matches!(
            self.graph.graph_kind,
            GraphKind::All | GraphKind::TypesOnly
          ) {
            if let Resolution::Ok(resolved) = &dep.maybe_type {
              let specifier = &resolved.specifier;
              let range = &resolved.range;
              let maybe_assert_type_with_range = dep
                .maybe_assert_type
                .as_ref()
                .map(|assert_type| AssertTypeWithRange {
                  range: range.clone(),
                  kind: assert_type.clone(),
                });
              if dep.is_dynamic && !self.in_dynamic_branch {
                self.dynamic_branches.insert(
                  specifier.clone(),
                  (range.clone(), maybe_assert_type_with_range),
                );
              } else {
                self.load(
                  specifier,
                  Some(range),
                  self.in_dynamic_branch,
                  maybe_assert_type_with_range,
                );
              }
            }
          } else {
            dep.maybe_type = Resolution::None;
          }
        }
      } else {
        module.dependencies.clear();
      }

      if matches!(self.graph.graph_kind, GraphKind::All | GraphKind::TypesOnly)
      {
        if let Some(Resolution::Ok(resolved)) = module
          .maybe_types_dependency
          .as_ref()
          .map(|d| &d.dependency)
        {
          self.load(&resolved.specifier, Some(&resolved.range), false, None);
        }
      } else {
        module.maybe_types_dependency = None;
      }
    }
    module_slot
  }
}

The functions, such as 'fill' and 'visit', continue to operate until all dependencies have been processed. Now that we've understood the basic functions, let's explore the 'hello world' example and see how the graph is constructed.

It's important to differentiate between parsing a module and transforming TypeScript code into JavaScript code. The latter process is referred to as transpiling and occurs after the graph has been fully constructed. On the other hand, parsing takes place during each visit to a node in the graph. This ensures that the structure and contents of the modules are properly understood and processed.

Graph building for hello-world

With a grasp of the "fill" and "visit" concepts, let's see how they're applied in our "hello world" example. We'll break it down step by step, examining how these processes build the program's graph.

Step 1

The fill function is invoked using the main module as its argument.

Module specifier is file:///Users/mayankc/Work/source/deno-vs-nodejs/helloLog.ts.

Step 2

The main module is loaded.

Step 3

A new process is initiated to retrieve the specifier in Deno. This process involves setting up a future that will be responsible for keeping track of the fetching procedure. Once the fetching task is completed, this future will reach a resolution point. This accomplished task is then incorporated into the list of pending operations, awaiting its turn to be processed further.

pending list = [ main module fetch future ]

Step 4

The "fill" function is placed within the loop, where it patiently awaits the resolution of the upcoming futures in the pending list. At this point, there's just one future in line, which happens to be the future responsible for fetching the main module. This fetch future holds the key to the next steps in our process.

Step 5

Deno has successfully retrieved and stored the main module's specifier in its cache for future use.

Step 6

The visit function gets triggered for the cached main module. It's important to note that the visit function receives the cached module as its input, without requiring a specifier to be provided. This means that when the visit function is invoked, it works with the already cached main module and doesn't need additional information like a specifier to do its job.

Step 7

The cached module undergoes parsing. This means that the module's code is carefully examined and understood. In this case, the module doesn't rely on any other pieces of code, so there are no dependencies or imports to worry about. This also means that there's no need to fetch additional information from other sources. Once the parsing is complete and it's confirmed that no external code is needed, the main module is then visited and processed.

Step 8

The loop within the "fill" function stops running because the list of pending items is now empty. This means that there are no more tasks left for the loop to process. As a result, the loop concludes its execution.

--

The graph containing just a single module or node is now prepared and operational.

Let's take a moment to review. When the graph is constructed, it entails the following steps:

• The primary module is obtained, stored in memory, and analyzed.

• All the associated requirements are obtained, stored in memory, and analyzed.

However, we still need to explore the process of converting TypeScript to JavaScript and how it takes place.