5.12 Module graphs
Module graphs are one of the core data structures used by Deno. A module graph is a simple graph that is built to cover all the dependencies from the root module. It takes a number of steps to build a module graph. Let's go over them in detail.
For all the modules that are used in the application, Deno uses module graphs to fetch, parse, and maintain modules. It's a simple graph where modules are added based on their specifiers and then modules or graph nodes are visited. For more details about graphs, check the standard graph data structure.
In our example, we have a main module without any additional imports. So, the graph in our case is expected to consist of a single node. In the next chapter, we'll go over a program with modules.
There are two major steps in building a graph:
- Add the main module
- Fetch it
- Fetch the module
- Add it to graph
- Add it to the pending module list
- Loop over pending modules
- Visit pending module
- Parse module
- Loop through dependencies
- Fetch them
At the start, the main module is fetched and added to the graph. Then the graph is visited starting from the main module. The visit of a module involves parsing and fetching dependencies. This is recursive.
First, we'll go over the core functions like add, fetch, and visit. After that, we'll use our example and see how these functions work out.
GraphBuilder.add() is the function to add the root module and all the dependencies, if there are any. In practical applications, there'd be a lot of dependencies. The graph would be quite complicated. However, in our simple hello world example, the graph is going to very simple, with just one node.
Here is the code of the add function:
pub async fn add(
&mut self,
specifier: &ModuleSpecifier,
is_dynamic: bool,
) -> Result<(), AnyError> {
self.fetch(specifier, &None, is_dynamic);
loop {
match self.pending.next().await {
Some(Err((specifier, err))) => {
self
.graph
.modules
.insert(specifier, ModuleSlot::Err(Rc::new(err)));
}
Some(Ok(cached_module)) => {
let is_root = &cached_module.specifier == specifier;
self.visit(cached_module, is_root)?;
}
_ => {}
}
if self.pending.is_empty() {
break;
}
}
if !self.graph.roots.contains(specifier) {
self.graph.roots.push(specifier.clone());
self.graph.roots_dynamic = self.graph.roots_dynamic && is_dynamic;
if self.graph.maybe_tsbuildinfo.is_none() {
let handler = self.graph.handler.borrow();
self.graph.maybe_tsbuildinfo = handler.get_tsbuildinfo(specifier)?;
}
}
Ok(())
}
It's not that the add() function is used only to add the root or main module. The add function is used to add any ES module. The root of the graph will be set to the main module, while any general ES module will go inside the graph as a dependency.
Here are the steps in the add function:
- Fetch root module
- Loop till there is an item in the pending list
- Visit pending item
The loop present in the add function will finish when the pending list is empty. An empty pending list means that all the dependencies have been recursively processed and added to the graph. When the add function ends, the graph is ready with all the modules.
Fetch is the next core function in building a module graph. The fetch function takes the following steps:
- Checks for the module in graph's modules
- If present
- return
- If not present
- Insert the module in modules as pending
- Use FetchHandler future to fetch module
- Add future to the pending list
fn fetch(
&mut self,
specifier: &ModuleSpecifier,
maybe_referrer: &Option<Location>,
is_dynamic: bool,
) {
if !self.graph.modules.contains_key(&specifier) {
self
.graph
.modules
.insert(specifier.clone(), ModuleSlot::Pending);
let future = self.graph.handler.borrow_mut().fetch(
specifier.clone(),
maybe_referrer.clone(),
is_dynamic,
);
self.pending.push(future);
}
}
Visit is the next core function that is useful in building the module graph. Visit is bigger than add or fetch. Visit is called for a module. It gets called for each module from the add function. It gets called till the pending list gets empty. Visit processes a fetched module.
Here is the flowchart showing how visit works:
Let's go over the steps:
- Visit starts with a fetched module
- Parse module
- Iterate through dependencies
- Fetch dependency
This is where it gets recursive. Visit will fetch all the dependencies. The fetch adds the future to the pending list. The loop in the add function will continue till the pending list gets empty. The loop in the add function will end only when all the nodes in the graph have been visited.
Here is the source code of the visit function:
fn visit(
&mut self,
cached_module: CachedModule,
is_root: bool,
) -> Result<(), AnyError> {
let specifier = cached_module.specifier.clone();
let requested_specifier = cached_module.requested_specifier.clone();
let mut module =
Module::new(cached_module, is_root, self.maybe_import_map.clone());
match module.media_type {
MediaType::Json
| MediaType::SourceMap
| MediaType::TsBuildInfo
| MediaType::Unknown => {
return Err(
GraphError::UnsupportedImportType(
module.specifier,
module.media_type,
)
.into(),
);
}
_ => (),
}
if !module.is_parsed {
let has_types = module.maybe_types.is_some();
module.parse()?;
if self.maybe_import_map.is_none() {
let mut handler = self.graph.handler.borrow_mut();
handler.set_deps(&specifier, module.dependencies.clone())?;
if !has_types {
if let Some((types, _)) = module.maybe_types.clone() {
handler.set_types(&specifier, types)?;
}
}
}
}
for (_, dep) in module.dependencies.iter() {
let maybe_referrer = Some(dep.location.clone());
if let Some(specifier) = dep.maybe_code.as_ref() {
self.fetch(specifier, &maybe_referrer, dep.is_dynamic);
}
if let Some(specifier) = dep.maybe_type.as_ref() {
self.fetch(specifier, &maybe_referrer, dep.is_dynamic);
}
}
if let Some((_, specifier)) = module.maybe_types.as_ref() {
self.fetch(specifier, &None, false);
}
if specifier != requested_specifier {
self
.graph
.redirects
.insert(requested_specifier, specifier.clone());
}
self
.graph
.modules
.insert(specifier, ModuleSlot::Module(Box::new(module)));
Ok(())
}
All the three functions i.e. add, fetch, and visit works till they finish all dependencies. Now that we know the core functions, let's go over the hello world example and see how the graph gets built.
Parsing of the module should not be confused with converting Typescript code to Javascript code. Latter is called transpiling. Transpiling happens after the graph is completely built. Parsing happens for each visit of a graph node.
Now that we know about add, fetch, and visit, it's time to see how they apply to our hello world example. We'll see step by step how the graph gets built for our program.
The function add is called with the main module.
Module specifier is
file:///Users/mayankc/Work/source/deno-vs-nodejs/helloLog.ts.The function fetch is called with the main module specifier.
A future is created for fetching the specifier. This future would resolve when fetching is done. The future is added to the pending list.
pending list = [ main module fetch future ]The function add goes in the loop and waits for the next future to resolve in the pending list. The next and only future is the main module fetch future.
The main module's future is resolved. The main module specifier has been fetched and cached.
The visit function is called for the cached main module. Note that the visit function takes the cached module as input. It doesn't take specifier
The cached module is parsed. There are no dependencies i.e. no imports. It doesn't perform more fetching. Visitation of the main module is done.
The loop present in the add function breaks as the pending list is now empty.
--
Graph with a single module or node is now ready.
Just to recall, when the graph is built, it means the following:
- The main module is fetched, cached, and parsed
- All the dependencies are fetched, cached, and parsed
Typescript to Javascript conversion is not yet done. This conversion happens in the next stage which is check or transpilation.