[import-visualizer] 9. 상대경로 문제와 스택 오버플로우

이때 발생한 문제점으로 상대 경로를 제대로 읽을 수 없다는 것과 스택 오버플로우 문제가 발생했다.

 

이 시리즈의 글은 개발 과정을 작성한 것으로 내용 중 코드 또는 판단이 이상한 부분이 있다면 높은 확률로 뒷부분에서 수정될 것입니다.

상대경로

import './style.css';
import typescriptLogo from './typescript.svg';
import viteLogo from '/vite.svg';
import { setupCounter } from '../counter';
import { test } from './test.ts';

이렇게 생긴 경우 ../counter를 가져올 수 없는 문제가 발생했다.

 

기존의 함수에서는 ../과 같은 상대 경로를 고려하지 않았다.

 

기존 방식의 전체적인 수정이 필요한 상황이므로 타입 정의를 꼼꼼하게 하여 헷갈리지 않도록 주의했다.

 

기존의 방식은 모든 경로를 상대 경로로 다뤘고 함수의 인자, 반환값은 모두 상대경로였다.

 

이 방식에서 절대 경로로 변환하여 보다 정확하게 경로를 찾을 수 있도록 수정했다.

 

바뀐 흐름은 아래와 같다.

1. 루트 경로를 가져옴 (config) → src/App.tsx
2. getAllFiles → ['C:/~/<project>/src/App.tsx', 'C:/~/<project>/src/test/Test.tsx', 'C:/~/<project>/Test2.tsx']
3. generateTree에 루트 경로를 인자로 넣고 실행
   1. 루트 경로를 절대 경로로 바꿈 → C:/~/<project>/src/App.tsx
   2. getImportPathsInFile 실행 → ['./test/Test', '../Test2']
   3. resolveImportPaths 실행 → ['C:/~/<project>/src/test/Test', 'C:/~/<project>/Test2']
   4. appendExtensions 실행 → ['C:/~/<project>/src/test/Test.tsx', 'C:/~/<project>/Test2.tsx']
   5. undefined가 아니라면 상대 경로로 다시 분리 한 후 노드로 생성하여 children에 삽입
   6. 재귀적으로 탐색

import { join } from 'path';

import type { absolutePath, aliasPath, configPath, relativePath } from './types';

function pathMapping(
  aliasPathWithAlias: aliasPath,
  currentFileAbsoluteDir: absolutePath,
  baseUrl: relativePath,
  paths: configPath
): absolutePath {
  // e.g. ./test/TestFile
  if (aliasPathWithAlias.startsWith('./')) return join(currentFileAbsoluteDir, aliasPathWithAlias).replace(/\\/g, '/');
  // e.g. ../test/TestFile
  if (aliasPathWithAlias.startsWith('../')) return join(currentFileAbsoluteDir, aliasPathWithAlias).replace(/\\/g, '/');

  /*
   * baseUrl: "src"
   * paths: { "@/*": ["*"] }
   * aliasPathWithAlias = @/TestFile
   */
  for (const [aliasName, actualPath] of Object.entries(paths)) {
    const aliasPrefix = aliasName.replace('*', ''); // e.g. "@/"

    if (aliasPathWithAlias.startsWith(aliasPrefix)) {
      const targetPrefix = actualPath[0].replace('*', ''); // e.g. ""
      const resolvedPath = aliasPathWithAlias.replace(aliasPrefix, targetPrefix); // e.g. TestFile

      // e.g. join('C:/.../<project>', 'src', "TestFile") => C:/.../<project>/src/TestFile
      return join(process.cwd(), baseUrl, resolvedPath).replace(/\\/g, '/');
    }
  }

  /*
   * baseUrl: "src"
   * aliasPathWithAlias = TestFile
   * join('C:/.../<project>', 'src', "TestFile") => C:/.../<project>/src/TestFile
   */
  return join(process.cwd(), baseUrl, aliasPathWithAlias).replace(/\\/g, '/');
}

export function resolvePathAlias(
  imports: aliasPath[],
  currentFileAbsoluteDir: absolutePath,
  baseUrl: relativePath,
  paths: configPath
): absolutePath[] {
  return imports.map((importPathWithAlias) => pathMapping(importPathWithAlias, currentFileAbsoluteDir, baseUrl, paths));
}

기존과 다르게 중요한 것은 resolveImportPaths에서 상대 경로를 먼저 분기한다는 것이다.

 

스택 오버플로우

결국 스택 오버플로우가 발생했다.

 

기존 코드는 아래와 같다.

private generateTree(node: FileNode) {
    // @babel/parser can't parse css file.
    if (node.name.split('.').pop() === 'css') return;

    // If the node has dir attributes, filePath will be relativePath.
    // If the node does not dir attributes, filePath will be alsolutePath. (e.g. If the file is in the project root.)
    const filePath = `${node.attributes.dir || this.projectDir}/${node.name}`;

    const currentFileAbsolutePath = getAbsolutePath(filePath);
    const currentFileAbsoluteDir = dirname(currentFileAbsolutePath);

    // relativePaths or paths with alias
    const importsWithAlias = getImportPathsInFile(currentFileAbsolutePath);

    const resolvedAbsolutePath = resolvePathAlias(importsWithAlias, currentFileAbsoluteDir, this.baseUrl, this.paths);
    const importedFileAbsolutePaths = appendExtensions(resolvedAbsolutePath, this.allFiles);

    importedFileAbsolutePaths.forEach((importedFileAbsolutePath) => {
      if (importedFileAbsolutePath === undefined) return; // e.g. import npm libraries.

      const [newFileAbsolutePath, newFileName] = splitFilePath(importedFileAbsolutePath);
      const newFileRelativePath = convertToRelativePath(this.projectDir, newFileAbsolutePath);

      const newNode = this.createNode(newFileName, newFileRelativePath);
      node.children.push(newNode);
      this.generateTree(newNode);
    });
}

importedFileAbsolutePaths.forEach((importedFileAbsolutePath) => {
  if (importedFileAbsolutePath === undefined) return; // e.g. import npm libraries.

  const [newFileAbsolutePath, newFileName] = splitFilePath(importedFileAbsolutePath);
  const newFileRelativePath = convertToRelativePath(this.projectDir, newFileAbsolutePath);

  const newNode = this.createNode(newFileName, newFileRelativePath);
  node.children.push(newNode);
  this.generateTree(newNode);
});

아 부분에서 forEach로 순회하는 과정에서 this.generateTree가 호출되고 newNode에 대한 generateTree가 실행된다.

 

하지만 importedAbsolutePaths에 대한 순회는 아직 끝나지 않았기 때문에 콜 스택에 해당 부분의 상태를 갖고 있어야 한다.

1. importedFileAbsolutePaths의 첫 요소에 대해 generateTree를 수행
2. 만약, 첫 요소 안에 다수의 imports가 있다면 그 중 첫번째 imports에 대해 generateTree를 수행
3. 더이상 imports가 없다면 콜 스택에서 제거
4. 직전의 importedFileAbsolutePaths 배열의 다음 요소에 대해 generateTree를 수행
5. 위 과정 반복

이 과정에서 여러개의 importedFileAbsolutePaths에 관한 정보가 콜스택에 쌓이며 스택 오버플로우가 발생하게 된 것이다.

 

예상은 하고 있었으나 우선 빠르게 구현하고 이를 개선할 목적으로 재귀함수를 선택했다.

 

스택 오버플로우란 함수가 실행되면서 스택이 가득차게 되어 메모리를 초과하는 문제를 말한다.

 

이를 해결하기 위해서는 함수의 실행 정보가 스택에 계속해서 쌓이는 것을 막아야 했다.

 

이 과정에서 새롭게 알게된 방식이 "꼬리재귀" 방식이다.

 

꼬리 재귀

꼬리 재귀의 핵심은 재귀 함수 호출이 끝나면 아무 일도 하지 않고 반환하는 것이다.

 

자주 사용되는 예시는 아래와 같다.

function factorial(n) {
  if (n === 1) {
      return 1;
  }
  return n * factorial(n-1);
}

function factorial(n, total = 1){
  if(n === 1){
      return total;
  }
  return factorial(n - 1, n * total);
}

꼬리 재귀는 함수의 반환 과정에서 추가적인 연산이 없이 다음 함수를 호출하게 된다.

 

단, 꼬리 재귀는 아무데서나 사용할 수 있는 것이 아니라 언어 자체적으로 꼬리 재귀에 관한 내용을 지원해야 한다고 한다.

 

결과적으로 프로젝트에 꼬리재귀를 적용하지는 않았다.

 

꼬리재귀를 어떻게 응용해야 할 지 몰랐기 때문이다.

 

예시는 모두 팩토리얼과 같은 단일 값의 순차적인 흐름에 관한 것이었다.

 

지금의 트리는 자식을 여러 개 가질 수 있는 다진 트리의 형태였으며 별다른 반환 값이 없기 때문에 여기에 꼬리 재귀를 적용하기에는 어려움이 있을 것이라 판단했다.

 

따라서 최종적으로 스택 오버플로우 문제를 해결하기 위한 방법으로 큐를 사용했다.

 

큐

private generateTree(rootNode: FileNode): void {
  const queue: FileNode[] = [rootNode];

  while (queue.length > 0) {
    const node = queue.shift()!;

    // @babel/parser can't parse css file.
    if (node.name.split('.').pop() === 'css') continue;

    // If the node has dir attributes, filePath will be relativePath.
    // If the node does not dir attributes, filePath will be alsolutePath. (e.g. If the file is in the project root.)
    const filePath = `${node.attributes.dir || this.projectDir}/${node.name}`;

    const currentFileAbsolutePath = getAbsolutePath(filePath);
    const currentFileAbsoluteDir = dirname(currentFileAbsolutePath);

    // relativePaths or paths with alias
    const importsWithAlias = getImportPathsInFile(currentFileAbsolutePath);

    const resolvedAbsolutePath = resolvePathAlias(importsWithAlias, currentFileAbsoluteDir, this.baseUrl, this.paths);
    const importedFileAbsolutePaths = appendExtensions(resolvedAbsolutePath, this.allFiles);

    for (const importedFileAbsolutePath of importedFileAbsolutePaths) {
      if (importedFileAbsolutePath === undefined) continue; // e.g. import npm libraries.

      const [newFileAbsolutePath, newFileName] = splitFilePath(importedFileAbsolutePath);
      const newFileRelativePath = convertToRelativePath(this.projectDir, newFileAbsolutePath);

      const newNode = this.createNode(newFileName, newFileRelativePath);
      node.children.push(newNode);
      queue.push(newNode);
    }
  }
}

현재 순회하고 있는 노드를 큐에 삽입하게 된다.

 

이후 해당 노드를 꺼내서 자식을 만들고 자식들도 계속해서 큐에 들어가게 된다.

 

이것이 가능한 이유는 프로젝트 처음에 중복 파일은 모두 표현하기로 했기 때문이다.

 

특정 노드를 방문했는지 확인할 필요없이 모든 파일의 중복을 허용하기 때문에 단순히 큐만 사용해도 계층 관계를 표현하는데 문제가 없다.

 

각 파일의 imports들은 모두 큐에 삽입되고 큐에서 요소를 하나씩 꺼내 같은 작업을 계속 반복하는 것이다.

 

이 과정을 통해 스택 오버플로우 문제를 해결할 수 있었다.

 

조금 더 생각해보기

조금만 더 생각해보면 위에서 큐를 활용한 방식이 어떻게 작동하게 되는 것일까?

 

내가 지금 보고 있는 node의 부모는 무엇인지 알지도 못하는데 어떻게 해당 정보 없이도 트리를 구성하게 된 것일까?

 

객체는 원시값과 다르게 주소값을 토대로 데이터를 가져오기 때문에 이것이 가능하다.

root에 child1와 child2가 있었고 이것을 토대로 createNode를 하는 경우 child1 객체와 child2 객체가 생성되어 힙에 저장된다.

 

이 경우 원시값이 아닌 객체를 root의 children에 push 하게 된다면 아래와 같은 모습이 된다.

이 과정에서 아까 만든 큐에 데이터를 넣은 모습도 이와 같다.

여기서 큐의 첫 요소를 꺼낸 뒤 같은 과정을 반복하면 아래와 같은 형태가 될 것이다.

100번지의 node는 102번지와 103번지에 있는 child3과 child4를 children으로 갖게 될 것이다.

 

이를 그림으로 나타내면 아래와 같다.

결론적으로 root에서 객체를 자식에 추가하고 그 자식 객체에 변형이 생기더라도 힙에 저장되는 객체의 특성 상 주소를 바꾸지 않았기 때문에 root의 자식 child1과 큐에서 꺼낸 child1은 같은 객체라고 할 수 있다.

 

따라서 함수가 실행됨에 따라 child1이 변경되어도 root의 자식인 child1과 여전히 동일한 객체가 될 것이고 이 변경 사항은 root에도 적용이 될 것이다.

1. root의 children에 100번지와 101번지에 있는 객체를 넣는다
2. 100번지의 객체에 102번지와 103번지 객체를 children으로 넣는다
3. root 객체의 첫 번째 children은 100번지에 있었고 100번지 children은 102번지와 103번지다

---

[참고자료]

[NODE] 📚 Path 모듈 (경로 제어) (tistory.com)