Não sei se você se lembra, mas já comentamos sobre algumas estruturas de dados em outros posts por aqui. Falamos de árvores e renderização recursiva de componentes em React e também falamos de pilhas e filas quando comentamos sobre o V8.

Particularmente, gosto bastante de alinhar esses conceitos que podem parecer um pouco mais teóricos com algumas soluções práticas que estão presentes no dia-a-dia de todo mundo.

Recentemente, numa conversa sobre Git com um amigo, percebi que seria interessante simular seu comportamento com JavaScript e que abriria possibilidades pra comentar um pouco sobre outra estrutura de dados: a lista ligada.

#Antes de tudo, vamos comentar um pouco sobre como o Git funciona

Se você já tem costume de trabalhar com Git, já deve ter se deparado com algumas imagens e algumas estruturas de como fica um histórico de commits, mais ou menos assim:

Outra forma de visualizar esse histórico é com algumas ferramentas mais visuais como a "Visualizing Git" que exibe de forma clara o que iremos implementar hoje.

Todos os commits que realizamos ao executar o comando git commit são organizados de maneira sequencial. Essa organização acontece através da referência de um objeto chamado HEAD. A cada novo commit, esse objeto HEAD é "apontado" pro commit que acabou de ser criado mas também armazena uma referência ao commit anterior.

Essa estrutura assemelha-se muito com uma estrutura de dados chamada de lista ligada (ou linked list) onde, um dado elemento possui uma referência (como, por exemplo, uma chave "next") para um elemento seguinte. A única diferença é que, ao invés de manter uma referência à um próximo elemento, o comportamento é o inverso: HEAD está sempre atualizada com o commit mais recente e possui referências para commits anteriores.

Para entender tudo isso de forma mais prática, nada melhor do que simular esse comportamento! Ao final desse post, teremos uma pequena imitação de como o Git funciona usando somente JavaScript.

Implementaremos os métodos mais básicos como add, commit, log e status de forma bem resumida mas com as devidas tratativas para simular um repositório. Dessa forma, podemos entender um pouquinho mais como essa estrutura de dados é trabalhada.

Ao final do post, nossa API será mais ou menos assim:

const repo = git.init();
repo
  .status()
  .log()
  .commit()
  .add('index.html')
  .add('style.css')
  .add('bundle.js')
  .status()
  .commit('iniciando o projeto')
  .status()
  .add('index2.html')
  .commit('inserindo segundo arquivo HTML')
  .add('style.css')
  .commit('ajustando CSS')
  .status()
  .log();

#Vamos pro código!

Para começar, vamos criar a estrutura do objeto que vai implementar a API que acabamos de comentar, com um rascunho de seus métodos e campos que vamos precisar.

#Estrutura inicial

Vamos criar um objeto chamado git que vai possuir os métodos init, add, commit, log e status.

// criamos estrutura inicial do objeto git
const git = {
  init() {},
  add() {},
  commit() {},
  log() {},
  status() {}
};

Os métodos add e commit devem receber, cada um deles, um parâmetro, sendo um arquivo (ou file) para o método add e uma mensagem (ou message) para o método commit. Vamos adicioná-los nas assinaturas das funções:

const git = {
  init() {},
  // adicionamos o parâmetro file
  add(file) {},
  // adicionamos o parâmetro message
  commit(message) {},
  log() {},
  status() {}
};

Como simularemos uma lista ligada ao manipular o valor de HEAD, vamos criar essa propriedade com um valor nulo, inicialmente:

const git = {
  // criamos head com o valor null
  head: null,
  init() {},
  add(file) {},
  commit(message) {},
  log() {},
  status() {}
};

O que nos falta agora é apenas definir a área de preparação dos commits do Git, também conhecida como staging area. Essa área de preparação é utilizada quando adicionamos arquivos para realizar um commit através do comando add e é justamente por isso que possui esse nome.

No nosso caso, como apenas simularemos o comportamento do Git, podemos criar um simples array para manter o nome dos "arquivos" salvos:

const git = {
  head: null,
  // criamos stage como um array vazio
  stage: [],
  init() {},
  add(file) {},
  commit(message) {},
  log() {},
  status() {}
};

Para que possamos encadear as chamadas dos métodos e atingir o modelo de API que especificamos anteriormente é necessário que todos os métodos retornem uma referência ao próprio objeto do Git. Podemos atingir isso de uma forma bem fácil retornando o próprio objeto em cada uma das funções:

// adicionamos o retorno do próprio objeto em todos os métodos
const git = {
  head: null,
  stage: [],
  init() {
    return this;
  },
  add(file) {
    return this;
  },
  commit(message) {
    return this;
  },
  log() {
    return this;
  },
  status() {
    return this;
  }
};

Com isso já temos uma estrutura inicial pronta e podemos começar a pensar na implementação de cada um dos métodos. O método init por si só já está pronto. Usaremos ele apenas para nos aproximarmos da API que é implementada pelo próprio Git e não precisaremos de mais nada.

#Método add

Como comentamos anteriormente, o método add está ligado à área onde os arquivos e modificações são preparados para, futuramente, um commit ser realizado.

Em nossa implementação essa área é simulada pelo array stage. Como esse array apenas conterá os nomes dos "arquivos" que devem entrar no próximo commit, a implementação do método add será bem simples. Tudo que precisaremos fazer é dar um push e adicionar o arquivo recebido como parâmetro nesse mesmo array:

const git = {
  head: null,
  stage: [],
  init() {
    return this;
  },
  add(file) {
    // adicionamos o item no array de stage
    this.stage.push(file);

    return this;
  },
  commit(message) {
    return this;
  },
  log() {
    return this;
  },
  status() {
    return this;
  }
};

Para nossa pequena implementação isso já é o suficiente!

#Métodos de status

Esse método em nossa solução também será bem simples. Tudo que ele precisará realizar é exibir uma mensagem de log com as alterações que serão adicionadas no próximo commit caso haja algum valor na nossa "stage area". Caso não tenha nada por lá, podemos exibir a mensagem uma mensagem como Nothing to commmit:

const git = {
  head: null,
  stage: [],
  init() {
    return this;
  },
  add(file) {
    this.stage.push(file);

    return this;
  },
  commit(message) {
    return this;
  },
  log() {
    return this;
  },
  status() {
    // criamos uma variável status que verifica
    // se existe álgo na "stage area"
    // caso exista, exibe os arquivos
    // caso não exista, exibe uma mensagem padrão
    const status = this.stage.length ? `Changes to commit ${this.stage}` : 'Nothing to commit'
    console.log(status);

    return this;
  }
};

Tire alguns segundos para brincar com esses dois métodos através de git.add('arquivo-qualquer') e git.status(). Você verá que nossa simulação de Git já está começando a tomar sua forma!

Agora vamos para os métodos mais "complicados" de nossa implementação: commit e log.

#Realizando commits e a referência de HEAD

Para iniciar o método de commit, vamos começar fazendo uma validação. Caso a nossa stage area esteja vazia, mostraremos uma mesma mensagem de Nothing to commit como fizemos anteriormente.

Para facilitar a leitura, a partir de agora irei omitir os campos e os demais métodos desse objeto, dessa forma podemos focar somente em nas funções que estamos desenvolvendo, ok?

Vamos lá:

const git = {
  commit(message) {
    // caso o array de stage esteja vazio
    if (!this.stage.length) {
      // exibimos a mensagem
      console.log('Nothing to commit');
    } else {
      // nossa lógica de commit entrará aqui
    }

    return this;
  },
};

Agora vamos pra criação do commit! A cada vez que um commit é realizado, a stage area deve ser apagada. Sabemos que o valor de head também será alterado pra um novo commit a cada vez que isso acontecer.

Podemos começar com isso então: vamos "limpar" nossa stage area, criar um objeto commit vazio e apontar nossa referência de head para esse novo commit.

const git = {
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      // criamos nosso commit vazio
      const commit = {};
      // apontamos head para o novo commit
      this.head = commit;
      // limpamos a stage area
      this.stage = [];
    }


    return this;
  },
};

Agora precisamos fazer a lógica para construir o objeto do commit com os valores necessários. Precisamos inserir os seguintes valores em um commit:

• um identificador (simulando o hash utilizado pelo Git);
• a mensagem recebida;
• os arquivos da nossa stage area;
• a data atual;
• criar uma referência ao commit anterior.

Vamos fazer isso por partes:

#Criando um identificador

Poderíamos criar um hash para cada commit mas, para facilitar nossa vida, vamos adotar uma convenção aqui e deixar as coisas mais simples. Nossos commits serão sequenciais compostos por apenas um número.

Por exemplo:

• nosso primeiro commit será #1;
• o segundo será #2;
• o terceiro será #3;
• e assim por diante.

Com isso, podemos dizer que o prefixo do nosso commit é um jogo da velha (#) e descobrir o "hash" do commit atual. Após isso, podemos somar + 1 ao commit atual para gerar o identificador do próximo commit.

Podemos fazer isso da seguinte forma:

const git = {
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      // criamos uma variável com o prefixo #
      const prefix = '#';
      // descobrimos o hash atual, caso exista algum valor me head
      // caso não exista, iniciamos com 0
      const currentHash = this.head ? this.head.hash.replace(prefix, '') : 0;
      // concatenamos o prefixo com a somatória (+ 1) do "hash" atual
      const hash = `${prefix}${Number(currentHash) + 1}`;
      const commit = {};

      this.head = commit;
      this.stage = [];
    }


    return this;
  },
};

Feito isso, podemos adicionar esse "hash" no objeto de commit que criamos:

const git = {
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      const prefix = '#';
      const currentHash = this.head ? this.head.hash.replace(prefix, '') : 0;
      const hash = `${prefix}${Number(currentHash) + 1}`;
      const commit = {
        // adicionamos o hash no commit criado
        hash,
      };

      this.head = commit;
      this.stage = [];
    }


    return this;
  },
};

#Adicionando a mensagem, os arquivos e a data atual

Para adicionar esses valores, podemos apenas passar o parâmetro message recebido, além de utilizarmos os valores presentes na nossa stage area. Para nos ajudar com a data atual, podemos construir um objeto com new Date() que já será o suficiente:

const git = {
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      const prefix = '#';
      const currentHash = this.head ? this.head.hash.replace(prefix, '') : 0;
      const hash = `${prefix}${Number(currentHash) + 1}`;
      const commit = {
        hash,
        // adicionamos a mensagem recebida
        message,
        // adicionamos o valor atual da nossa stage area
        files: this.stage,
        // criamos um novo objeto de data
        date: new Date(),
      };

      this.head = commit;
      this.stage = [];
    }


    return this;
  },
};

Com isso, só nos resta referenciar o commit anterior para começarmos a trabalhar com nossa estrutura de lista ligada.

#Referenciando o commit anterior

Embora possa parecer um pouco confuso, tudo que precisaremos agora é armazenar uma referência ao objeto do commit que estava em "head" antes desse novo commit que estamos gerando. É através dessa referência que a lista de commits poderá ser acessada futuramente: a cada vez que um novo commit é criado, ele possuirá uma referência "apontando" para o commit anterior.

Faremos isso criando um campo previous (que significa "anterior") e atribuindo à ele o próprio valor que existia em "head" anteriormente. Simples assim:

const git = {
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      const prefix = '#';
      const currentHash = this.head ? this.head.hash.replace(prefix, '') : 0;
      const hash = `${prefix}${Number(currentHash) + 1}`;
      const commit = {
        hash,
        message,
        files: this.stage,
        date: new Date(),
        // criamos um valor previous apontando
        // para o commit anterior
        previous: this.head
      };

      this.head = commit;
      this.stage = [];
    }


    return this;
  },
};

Como já havíamos atualizado o valor de head com o novo commit, tudo já está pronto nesse método.

#Método de log percorrendo toda a lista de commits

Agora, para poder exibir nosso histórico de commits, vamos trabalhar no método log.

Vamos começar criando uma pequena validação e exibindo uma mensagem No commits yet caso ainda não exista nenhum commit. Podemos verificar se algum commit já existe através do valor que estamos armazenando em head.

const git = {
  log() {
    // caso não exista nenhum commit
    if (!this.head) {
      // exibimos uma mensagem
      console.log('No commits yet');
    } else {
    }

    return this;
  },
};

Caso existam commits, precisaremos exibí-los do mais recente ao mais antigo. Como podemos exibir bastante informação em nosso log, vamos criar um divisor com apenas alguns traços (-). Vamos criar uma variável log que será um array com todas as mensagens de log formatadas antes de serem exibidas:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      // criamos um divisor com um traço (-) repetido 100 vezes
      const divider = '-'.repeat(100);
      // criamos um array que irá armazenar as mensagens de log
      const log = [];
    }

    return this;
  },
};

Para percorrer nossa lista de commits precisaremos de uma variável que nos auxilie, igual já estamos acostumados a realizar um laço de repetição (como o for) e uma variável que nos ajuda com um índice. Vamos chamar essa variável de cursor, pois ela será responsável por conter a referência de cada um dos commits ao longo do nosso laço de repetição.

O valor da variável cursor será, inicialmente, a referência que temos em head:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      const log = [];
      // criamos o cursor com a referência de head
      let cursor = this.head;
    }

    return this;
  },
};

O laço while cairá como uma luva aqui. Tudo que precisaremos fazer é executar esse laço de repetição enquanto existir um valor na variável cursor. Ao fim do laço, atribuíremos à essa variável a referência do commit anterior através de sua própria referência com cursor.previous:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      const log = [];
      let cursor = this.head;
      while(cursor) {
        cursor = cursor.previous;
      }
    }

    return this;
  },
};

Agora só nos resta formatar a mensagem de commit que queremos exibir. Vamos exibir algo como:

Commit: ${identificador}
Message: ${mensagem}
Date: ${data}

Podemos usar esse "template" para montar as strings da mensagem que queremos. Como essa mensagem será composta por 4 linhas, vamos criar um array para cada uma de suas partes. Cada uma dessas linhas será um valor nesse array:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      const log = [];
      let cursor = this.head;
      while(cursor) {
        // criamos o array com a mensagem de log do commit
        const message = [
          // seu valor inicial é o identificado do commit
          `Commit: ${cursor.hash}`,
          // seguido por sua mensagem
          `Message: ${cursor.message}`,
          // a data que foi criado
          `Date: ${cursor.date}`,
        ]
        cursor = cursor.previous;
      }
    }

    return this;
  },
};

Agora, podemos juntar esse array de mensagem em uma única string e utilizar a quebra de linha \n para unir seus pedaços com o método .join. Dessa forma, começamos a formatar a mensagem no log como queremos.

Adicionaremos essa nova string gerada no array de log que criamos anteriormente:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      // criamos uma variável com a quebra de linha
      const newline = '\n';
      const log = [];
      let cursor = this.head;
      while (cursor) {
        const message = [
          `Commit: ${cursor.hash}`,
          `Message: ${cursor.message}`,
          `Date: ${cursor.date}`,
          // unimos o array de mensagem usando a quebra de linha
        ].join(newline);

        // realizamos o push no array de log
        log.push(message.join(newline));

        cursor = cursor.previous;
      }
    }

    return this;
  },
};

Para finalizar nosso log, tudo que precisamos fazer é unir todos os seus valores com o método .join também, mas utilizaremos dessa vez nosso divisor e duas quebras de linha (uma antes e uma depois) para que nossa mensagem essa exibida formatada corretamente no console:

const git = {
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      const newline = '\n';
      const log = [];

      let cursor = this.head;
      while (cursor) {
        const message = [
          `Commit: ${cursor.hash}`,
          `Message: ${cursor.message}`,
          `Date: ${cursor.date}`,
        ].join(newline);

        log.push(message);
        cursor = cursor.previous;
      }

      // unimos o array de logs usando uma quebra de linha
      // antes e outra depois do divisor
      const history = log.join(`${newline}${divider}${newline}`);
      // exibimos no log o histórico de commits
      console.log(history);
    }

    return this;
  },
};

E terminamos de desenvolver por aqui! Agora vamos ver como ficou nosso código ao final do processo e ver seu funcionamento.

#Resultado do código

Como omitimos alguns pedaços de código para facilitar a leitura, aqui está o código completo da nossa implementação de Git usando JavaScript:

const git = {
  head: null,
  stage: [],
  init() {
    return this;
  },
  add(file) {
    this.stage.push(file);

    return this;
  },
  commit(message) {
    if (!this.stage.length) {
      console.log('Nothing to commit');
    } else {
      const prefix = '#';
      const currentHash = this.head ? this.head.hash.replace(prefix, '') : 0;
      const hash = `${prefix}${Number(currentHash) + 1}`;
      const commit = {
        hash,
        message,
        files: this.stage,
        date: new Date(),
        previous: this.head
      };

      this.head = commit;
      this.stage = [];
    }

    return this;
  },
  log() {
    if (!this.head) {
      console.log('No commits yet');
    } else {
      const divider = '-'.repeat(100);
      const newline = '\n';
      const log = [];

      let cursor = this.head;
      while (cursor) {
        const message = [
          `Commit: ${cursor.hash}`,
          `Message: ${cursor.message}`,
          `Date: ${cursor.date}`,
        ].join(newline);

        log.push(message);
        cursor = cursor.previous;
      }

      const history = log.join(`${newline}${divider}${newline}`);
      console.log(history);
    }

    return this;
  },
  status() {
    const status = this.stage.length ? `Changes to commit ${this.stage}` : 'Nothing to commit';
    console.log(status);

    return this;
  }
};

Para executá-lo e ver resultado final, podemos rodar aquele exemplo que comentamos inicialmente:

const repo = git.init();
repo
  .status() // Nothing to commit
  .log() // No commits yet
  .commit() // Nothing to commit
  .add('index.html')
  .add('style.css')
  .add('bundle.js')
  .status() // Changes to commit index.html,style.css,bundle.js
  .commit('iniciando o projeto')
  .status() // Nothing to commit
  .add('index2.html')
  .commit('inserindo segundo arquivo HTML')
  .add('style.css')
  .commit('ajustando CSS')
  .status() // Nothing to commit
  .log(); // Exibe histórico de todos os commits

Todas as mensagens de log devem aparecer no seu console como esperado, mais ou menos assim:

Nothing to commit
No commits yet
Nothing to commit
Changes to commit index.html,style.css,bundle.js
Nothing to commit
Nothing to commit
Commit: #3
Message: ajustando CSS
Date: Mon Jul 12 2021 16:11:23 GMT-0300 (Brasilia Standard Time)
----------------------------------------------------------------------------------------------------
Commit: #2
Message: inserindo segundo arquivo HTML
Date: Mon Jul 12 2021 16:11:23 GMT-0300 (Brasilia Standard Time)
----------------------------------------------------------------------------------------------------
Commit: #1
Message: iniciando o projeto
Date: Mon Jul 12 2021 16:11:23 GMT-0300 (Brasilia Standard Time)

#Mais uma estrutura de dados pra conta

Espero que tenha se divertido com a nossa pequena simulação de Git usando JavaScript!

Quando conseguimos enxergar uma estrutura de dados sendo aplicada de forma mais prática, acho que as coisas ficam bem interessantes, né?

Além de tudo, isso anos ajuda a entender e perceber que alguns assuntos, mesmo que pareçam mais teóricos, são extremamente importantes e muitas vezes utilizados (sem que soubéssemos) em ferramentas do nosso cotidiano.