Departamento de Ciência da Computação - IME - USP

MAC0328 Algoritmos em Grafos

Tarefa 4       Entrega: até 15 de maio de 2011

Este projeto foi originalmente elaborado
pelo professor Francisco Reverbel

Make II

OK, let's be straight about it,
the syntax of make is really stupid.
If you use spaces where you're supposed to use tabs or vice versa,
your makefile blows up. And the error messages are really confusing.

Fonte: Running Linux, Matt Welsh and Lar Kaufman


Objetivos

  1. Manipulação da representação de um digrafo através de vetor de listas de adjacência.
  2. Implementar um algoritmo que percorre um digrafo através de busca em profundidade.
  3. Uso de busca em profundidade para procurar ciclos em digrafos ou obter uma ordenação topológica de um digrafo acíclico.

Descrição

Introdução

      Neste tarefa você estenderá o programa Make.c feito na Tarefa 3. O programa utilizará as estruturas de dados das notas de aulas do professor Paulo Feofiloff para a representação de um "digrafo de dependência".

      O seu programa deverá chamar-se Make. O 'M' maiúsculo em Make é para diferenciar o seu programa do utilitário make do UNIX. Da mesma maneira que o make, o seu programa, ao ser chamado na linha de comando sem opção alguma, lerá um arquivo de nome MakeFile contendo informações de dependência e comandos para reconstrução (rebuilding commands) de objetos. O F maiúsculo em MakeFile server para não confundirmos a entrada do Make com o arquivo Makefile; que vocês muito provavelmente estarão utilizando.

Formato de um MakeFile

Um MakeFile consiste de uma seqüência de "regras" com o seguinte formato:
  <target> :  <dependências>
         <comando1>
         <comando2>
         ...

      Um target é usualmente o nome de um arquivo que é gerado por um programa; exemplos de targets são arquivos executáveis (bin ou .o). Um target também pode ser o nome de uma ação, tal como "clean".

      Uma dependência é um arquivo que é usado para criar o target. Um target pode depender de vários arquivos.

      Um comando é uma ação que Make pode mandar que seja executada. Um regra pode ter mais que um comando, cada um em uma linha. Deve existir um caractere TAB ('\t') no início de cada linha que possui um comando.

Exemplo de um MakeFile

      A seguir está um exemplo típico de um arquivo MakeFile que seu programa Make deve ser capaz de tratar (os números das linhas foram colocada apenas para efeito de referência, eles não fazem parte do MakeFile):

1   meuprog: meuprog.o  fila.o  etc.o
2         gcc meuprog.o fila.o etc.o -o meuprog 
3
4   meuprog.o:  meuprog.c  minhasdefs.h  fila.h   etc.h
5         gcc -c meuprog.c
6
7   fila.o:  fila.c minhasdefs.h  fila.h
8         gcc -c fila.c
9
10  etc.o: etc.c  minhasdefs.h  etc.h
11        gcc -c etc.c
12
13  clean:
14        rm -f meuprog.o fila.o etc.o
15        cp meuprog.c ../ultimo/meuprog-salvo.c
16        cp fila.c  ../ultimo/fila-sava.c
Este exemplo ilustra o formato do arquivo MakeFile que o seu programa deve tratar:

Linhas 1, 4, 7, 10 e 13 fornecem informações de dependência. Em uma linha de dependência o nome de um target file aparece primeiro, seguido por dois pontos (':'). Depois dos dois pontos segue-se uma lista (possivelmente vazia) de arquivos dos quais o target depende. A Linha 7, por exemplo, diz que o target file fila.o depende dos arquivos fila.c, minhasdefs.h e fila.h.

Uma linha de dependência é seguida por uma ou mais linhas com comandos (rebuild commands) que criam ou atualizam o target file especificado na linha de dependência. O primeiro caractere de um linha contendo um comando deve ser um TAB (`\t'); uma, aparentemente idêntica, seqüência de espaços não pode ser usada no lugar do TAB. Linhas 2, 5, 8, 11 e 14 contêm comandos. A Linha 8, por exemplo, diz que o comando
meu_prompt> gcc -c fila.c
deverá ser executado para reconstruir o target fila.o a partir dos arquivos fila.c, minhasdefs.h e fila.h. Seu programa, entretanto, deve ser capaz de tratar o caso em que várias linhas de comando seguem uma linha de dependência.

As linhas em branco (linhas 3, 6, 9 e 12) são ignoradas. Estas linhas podem estar presente apenas para facilitar a legibilidade do MakeFile, mas elas não são necessária. Um Makefile similar, mas sem linhas em branco, também deve ser aceito pelo seu Make.

Digrafo de dependências

      As linhas de dependências em um MakeFile (ou Makefile) definem um digrafo de dependências: um digrafo onde os vértices correspondem a targets e arquivos de dependências, e os arcos representam a dependência entre estes targets e arquivos. Sempre que um arquivo arquivo1 depende de um arquivo arquivo2 o correspondente digrafo de dependências deve conter um arco do vértice de nome arquivo1 ao vértice de nome arquivo2. A Linha 7 do nosso exemplo de MakeFile acima diz que o respectivo digrafo de dependências contém arcos do vértice de nome fila.o ao vértice de nome fila.c, ao vértice de nome minhasdefs.h, e ao vértice fila.h.

      Um ciclo em um digrafo é caminho "fechado". Mais precisamente, um ciclo é uma seqüência de vértices v0-v1-v2-...-vk tal que

existe um arco de vi a vi+1 (i=0,1,...,k-1) e v0=vk.

      Um digrafo de depêndencias não deve conter ciclos. Isto, entretanto, não é obstácute para que um digrafo correspondente a um arquivo MakeFile tenha circuitos. Isto apenas significa que o Make deverá ser capaz de verificar a presença ou não de ciclos no digrafo. A existência de ciclos deve ser considerada pelo Make como um erro na especificação do MakeFile. Detecção de ciclos é um dos objetos desta da tarefa.

Representação do digrafo

O seu programa deve usar a estruturas de dados e vetor de listas de adjacência das notas de aulas do professor Paulo Feofiloff para a representação do digrafo de dependências. Considere, além de outras estrutura comuns aos programa que temos visto, as seguintes declarações:
typedef enum {FALSE,TRUE} Boolean;
static char  *nome[maxV];
static char  *comandos[maxV];
int           mod_time[maxV];
Boolean       up_to_date[maxV];

      Para cada vértice v o seu programa deve manter em:

Acho que é só. De resto, sugestões são bem-vindas.

Comportamento do Make

O programa Make poderá ser chamado em uma linha de comando do shell de duas maneiras diferentes:
meu_prompt> Make [-s | <goals>] 
Inicialmente, Make deverá procura no diretório corrente um arquivo de nome MakeFile e
  1. (Contrói o digrafo de dependências) Make lê o arquivo MakeFile, que tem o formato descrito acima, e contrói uma representação do digrafo de dependência através de vetor de listas de adjacência
Chamado com a opção -s, Make deverá procura no diretório corrente um arquivo de nome MakeFile e processá-lo da seguinte forma:
  1. (Salva o digrafo) Após a criação do digrafo de dependência na representação descrita, Make percorre o digrafo e cria no diretório corrente um arquivo de nome MakeFile.dg. Este arquivo MakeFile.dg é parecido com o exemplo de MakeFile, possivelmente sem as linhas em branco ou trocando alguma das regras de lugar; esta ordem é irrelevante, ela depende de como o seu Make gerou o grafo.

    Observação. Isto já foi feito na Tarefa 3.

Um objetivo (= goal) é o nome de um target que Make deve atualizar. Objetivos serão especificados como argumentos para o Make, assim <goals> pode conter o nome de qualquer target do MakeFile que originou o grafo de dependências. Se <goals> não for especificado, então 'by default' o primeiro target do MakeFile será o objetivo. Se vários objetivos forem especificados, então Make processa um após o outro, na ordem que eles aparecem como argumentos.

      Para atualizar um objetivo Make deve percorrer o digrafo de dependências, a partir de um vértice que corresponde a um objetivo que foi especificado ou ao primeiro target em Makefile (caso nenhum objetivo (goal) seja especificado como argumento). Ao percorrer o digrafo, Make deve:

  1. verificar a existência de ciclos nesta parte do digrafo; e
  2. executar os comandos (rebuilding commands) associados com cada vértice, caso o correspondente arquivo não exista ou se este for mais velho do que algum dos arquivos do qual ele depende. Sugestão. Isto pode ser feito adaptando-se a função DIGRAPHcycle da AULA 8.
Se um ciclo é encontrado então o reconstrução do correspondente objetivo deve ser interrompida e uma mensagem de erro deve ser enviada para a saída padrão de erro (stderr).

      Antes de executar os comandos (rebuilding commands) para criar ou atualizar um target, Make deve certificar-se que todos os arquivos dos quais este target depende existam e estejam atualizados (up to date). Logo, Make deve executar comandos de uma maneira, digamos, 'bottom-up'. Para este fim, Make deve percorrer em pós-ordem o digrafo de dependências através de uma busca em profundidade.

Execução de comandos do shell

Make executa comandos para reconstruir um targets que não existem ou estão desatualizado. Logo Make deve ser capaz de executar comandos de um shell, como por exemplo o comando
gcc -g -Wall -ansi -pedantic -O2 -lgb -c Make.c
A função
int system(const char *string)
da biblioteca padrão do C, executa os comandos contidos na cadeia de caracteres string e depois continua a execução do programa corrente. Tudo se passa como se string tivesse sido digitada e executada como um comando de um shell. O header da função system está em <stdlib.h>.

      O conteúdo de string depende muito do sistema operacional local, que no caso de vocês é Linux. Como exemplo trivial o comando

system("date");
faz com que o programa date seja executado; ele devolve a data e hora correntes na saída-padrão. system retorna um valor de estado, dependente do sistema, a partir do comando executado. No sistema UNIX é o valor indicado por exit ou return.

      O seu Make fará freqüentemente a chamada

  if (system(comandos[v]) != 0)
    {
      fprintf(sterr,"%s: erro na reconstrução do target %s.\n", argv[0], nome[v]);
    }
Um exemplo simples do uso de system está em system.c.

Instante da última modificação de um arquivo

      O sistema operacional UNIX fornece seus serviços por meio de um conjunto de chamadas do sistema (system calls), que são funções dentro do sistema operacional que podem ser chamadas por programas usuários.

      O instante da última modificação de um arquivo (file modification time), expresso como o número de segundos desde a zero horas de 1o. de janeiro de 1970 GMT (Greenwich Mean Time) atá o momento da modificação pode ser obtida através da função (system call) stat (Hmmm, acho que este negócio vai estourar alguma hora... Vocês já ouviram falar do bug do ano 2037 ou coisa do tipo?). Usando esta chamada do sistema não é difícil implementar a função

long mtime (const char *filename); 
que retorna o instante da última modificação do arquivo filename ou -1 se o arquivo não existe.

      A função

int stat(const char *filename, struct stat *stbuf);
recebe um nome-de-arquivo através de um apontador filename e retorna toda a informação contida no inode para esse arquivo, ou -1 se houver um erro. O inode para um arquivo é onde toda a informação sobre o arquivo (exceto seu nome) é mantida. Um entrada em um diretório geralmente consiste em somente dois itens, o nome do arquivo e um número de inodes.) Assim,
struct stat stbuf;
Vertex v;
[...]
stat (nome[v], &stbuf);
[...]
preenche a estrutura stbuf com a informação do inode para o nome-de-arquivo nome[v]. A estrutura descrevendo o valor retornado por stat está em <sys/stat.h>, e se "parece" com (veja /usr/include/bits/stat.h)
/* Expanded stat structure */
 
struct  stat {
        dev_t   st_dev;       /* dispositivo do inode */
        long    st_pad1[3];   /* reserve for dev expansion, */
                              /* sysid definition */
        ino_t   st_ino;       /* número do inode */
        mode_t  st_mode;      /* bits de modo */
        nlink_t st_nlink;     /* número de ligações do arquivo */
        uid_t   st_uid;       /* id. do usuário dono */
        gid_t   st_gid;       /* id. do grupo do dono   */
        dev_t   st_rdev;      /* para arquivos especiais */ 
        long    st_pad2[2];  
        off_t   st_size;      /* tamanho arq. em caracteres */
        long    st_pad3;      /* reserve pad for future off_t expansion */
        timestruc_t st_atime; /* instante do último acesso */
        timestruc_t st_mtime; /* instante da última modificação */
        timestruc_t st_ctime; /* instante da criação */
        long    st_blksize;
        long    st_blocks;
        char    st_fstype[_ST_FSTYPSZ];
        long    st_pad4[8];     /* expansion area */
};
Os tipos como dev_t e ino_t são definidos em <sys/types.h>, que também deve ser incluído em seu programa. Veja um exemplo besta do uso desta função em statsys.c.

      Assim, a função mtime pode ser implementada da seguinte maneira:

long
mtime (const char *filename)
{
   struct stat bufst;

   if (stat(filename, &bufst) == -1) return -1;
   return bufst.st_mtime;
}

Busca por um vértice

O seu programa fará várias vezes a busca por um vértice, dado o seu nome. As seguintes rotinas podem ser usadas para isto. Elas fazem parte do módulo GB_GRAPH do SGB.

      Este esquema é usado pelo SGB:

The lookup scheme is quite simple. We compute a more-or-less random value h based on the vertex name, where |0 <= h < n|, assuming that the graph has n vertices. There is a list of all vertices whose hash address is h, starting at hash_head[h] and linked together in the hash_link fields.

      The hash code for a string c[1..k] of lenght k is a nonlinear function of the characters; this function appears to produce reasonably random results between 0 and the number of vertices in the current graph. Simpler approaches were noticeable poorer in the author's tests.

      Caution: This hash coding scheme is system-dependent, because it uses the system's character codes. If you create a graph on a machine with ASCII code and save it with GB_SAVE, and if you subsequently ship the resulting text file to some friend whose machine does not use ASCII code, your friend will have to rebuild the hash structure with hash_setup before being able to use hash_lookup successfully.

      O código a seguir é uma adaptação do código do Knuth usando o SGB para a estrutura de dados do Sedgewick que está nas notas de aulas do professor Paulo Feofiloff.

#define HASH_MULT  314159 /* random multiplier */
#define HASH_PRIME 516595003 /* the 27182818th prime; it's less than $2^{29}$ */

static Vertex hash_head[maxV];
static Vertex hash_link[maxV];

void
hash_setup(Digraph G)
{
   if (G && G->V > 0) 
     {
        register Vertex v;
        for (v = 0; v < G->V; v++) hash_head[v] = -1;
        for (v = 0; v < G->V; v++) hash_in(v,G);
     }
}

void
hash_in(Vertex v, Digraph G)
{
  register char *t=nome[v];
  register Vertex u;
  register long h;
  
  /*Find vertex u, whose location is the hash code for string t;*/
  for (h = 0; *t; t++) 
    {
      h += (h^(h>>1)) + HASH_MULT*(unsigned char)*t;
      while (h >= HASH_PRIME) h-=HASH_PRIME;
    }
  u = h % G->V;

  hash_link[v]=hash_head[u];
  hash_head[u]=v;
}


Vertex
hash_out(char *s, Digraph G)
{
   register char*t= s;
   register Vertex  u;
   register long h;

   /*Find vertex u, whose location is the hash code for string t;*/
   for (h = 0; *t; t++)
     {
        h += (h^(h>>1)) + HASH_MULT*(unsigned char)*t;
        while (h >= HASH_PRIME) h-= HASH_PRIME;
     }
   u = h%G->V;

   for (u = hash_head[u]; u != -1; u = hash_link[u])
     if (strcmp(s,nome[u]) == 0) return u;

   return -1;
}


Vertex
hash_lookup(char *s, Digraph G)
{
   if (G && G->V > 0)
     {
        register Vertex v;
        v = hash_out(s,G);
        return v;
     }
   else return -1;
}

Problema com alocação dinâmica de vértices

      Como devemos alocar o digrafo já que o número de vértices não é fixado logo de cara? Uma possibilidade é fazermos um realloc. Outras sugestões?


Entrega

  1. Junto com o seu programa você deve entregar um Makefile de tal forma que
    meu_prompt> make Make
    
    produza o executável de nome Make correspondente a sua Tarefa 4.
  2. O Paca não costuma aceitar a entrega de vários arquivos. Por isto, você deve depositar um arquivo tarefa4.tgz com todo o seu trabalho. Espera-se que
    meu_prompt>tar -xvf tarefa4.tgz 
    crie um diretório que tenha o seu login na rede Linux como nome. Neste diretório devem estar todos os arquivos da sua Tarefa 4, inclusive o Makefile que você usou. Se você achar necessário coloque junto um arquivo 00-leia-me, onde você descreve algo que achar necessário: como limitações e bugs no seu programa

Last modified: Mon Mar 31 07:58:55 BRT 2011