Saltar para o conteúdo
Ridgun
Português
EnglishEspañolPortuguêsSvenskaCatalàGalegoEuskaraItaliano

09 O Livro do Ridgun

A lib str — Manipulação de Texto, Pesquisa e Formatação Tabular

09.1. Por que existe a lib str? (O problema real e a filosofia Ridgun)

«Por que preciso de uma lib str escrita de raiz em Ridgun puro em vez de ligar uma biblioteca C tradicional?»

Essa é a primeira pergunta que qualquer engenheiro de sistemas faz ao chegar à str. E a resposta resume toda a filosofia do ridgun-libs:

Sejamos sinceros: manipular cadeias em C com strtok e strncpy é caminhar num campo de minas de buffer overflows e ponteiros NULL, e noutras linguagens acaba a importar pacotes externos só para alinhar colunas ou repetir um separador em $O(\log N)$.

A lib str fornece todas as primitivas puras e imutáveis para pesquisar, aparar, dividir, juntar, converter maiúsculas/minúsculas, repetir por duplicação binária $O(\log N)$ e preencher cadeias.

Num ecossistema tradicional, resolver as tarefas do domínio STR implica arrastar dependências externas em C, lidar com ponteiros brutos, conversões opacas de tipos, exceções não verificadas ou pausas imprevisíveis do coletor de lixo. Em Ridgun, a lib str (src/main/ridgun/lib/str.rg) aborda o problema com quatro princípios inegociáveis:

  1. Declare import str (ou import str as alias) no início do ficheiro: cada lib define o seu espaço de nomes module :: str e em modo --strict as funções multi-palavra são sempre invocadas com espaços naturais.
  2. Encadeie os seus pipelines da esquerda para a direita com ->: escreva entrada passo um -> passo dois -> resultado, use máscaras (+ _ _ +) para desestruturar sequências e omita _ = em instruções sequenciais (ou descarte com -> ()).
  3. Recursão de cauda com TCO (Tail-Call Optimization): todas as travessias internas da str são compiladas para ciclos nativos em espaço de pilha $O(1)$.
  4. Memória determinística (RMM1 / RMM2): cada estrutura intermédia é libertada no instante exato em que termina a sua última leitura, sem Garbage Collector.

09.2. Artefactos nativos, importação e catálogo completo da API de str

No ridgun-libs, str é uma lib de primeira classe localizada em src/main/ridgun/lib/str.rg (domínio STR). Ao compilar com stable bundle, é empacotada em três formatos nativos:

ArtefactoCaminhoFinalidade
Bundle Ridguntarget/bundles/str.rglibDistribuição e importação direta com import str
Ficheiro compiladotarget/str.rgcArtefacto intermédio verificado pelo ridgunc
Objeto partilhado ELF64target/libstr.soBiblioteca dinâmica nativa sem dependências de C nem libc

Cada lib declara o seu próprio espaço de nomes com module :: str: basta escrever import str (ou import str as alias) no topo e invocar as suas funções com espaços naturais (minha funcao x) e pipelines -> (x minha funcao -> resultado).

09.2.1. Resumo das famílias funcionais da str

Assinatura / Função / TipoO que faz e quando usar
str index of : String -> String -> IntPrimeiro índice da subcadeia (-1 se ausente / 0 se vazia)
str contains / str starts with / str ends withPredicados Bool de subcadeia, prefixo e sufixo
str trim / str trim left / str trim rightRemove espaços em branco ASCII ( , \t, \n, \r)
str split / str lines / str words / str joinDivide em [String] e junta listas com um separador
str replace / str to upper / str to lowerSubstituição sem sobreposição e conversão ASCII de maiúsculas/minúsculas
str repeat / str pad left / str pad rightRepetição em $O(\log N)$ e preenchimento de colunas com largura fixa

09.2.2. Catálogo exaustivo de tipos e assinaturas em src/main/ridgun/lib/str.rg

Abaixo encontra-se o inventário completo de tipos algébricos (type), operadores (op ::) e assinaturas de funções (fn ::) definidos em src/main/ridgun/lib/str.rg (0 tipos, 0 operadores e 42 funções):

#Função / Assinatura (fn ::)Tipo de Retorno
1fn :: is ascii space IntBool
2fn :: is ascii lower IntBool
3fn :: is ascii upper IntBool
4fn :: to upper code IntInt
5fn :: to lower code IntInt
6fn :: str index of from String String Int Int IntInt
7fn :: str index of String StringInt
8fn :: str ends with step String String Int IntBool
9fn :: str ends with String StringBool
10fn :: str is empty StringBool
11fn :: first non space idx String Int IntInt
12fn :: last non space end String IntInt
13fn :: str trim left StringString
14fn :: str trim right StringString
15fn :: str trim slice String Int IntString
16fn :: str trim StringString
17fn :: str is blank StringBool
18fn :: str replace step String String String IntString
19fn :: str replace String String StringString
20fn :: str split chars String Int Int [String][String]
21fn :: str split onech loop String Int Int Int Int [String][String]
22fn :: str split loop String String Int Int Int Int Int [String][String]
23fn :: str split step String String Int Int[String]
24fn :: str split String String[String]
25fn :: str join pair step [String] String [String][String]
26fn :: str join pairs [String] StringString
27fn :: str join [String] StringString
28fn :: upper char code String Int IntString
29fn :: upper char slice String IntString
30fn :: str to upper range String Int IntString
31fn :: str to upper StringString
32fn :: lower char code String Int IntString
33fn :: lower char slice String IntString
34fn :: str to lower range String Int IntString
35fn :: str to lower StringString
36fn :: str repeat loop String Int StringString
37fn :: str repeat String IntString
38fn :: pad fill unit StringString
39fn :: str pad left step String Int String IntString
40fn :: str pad left String Int StringString
41fn :: str pad right step String Int String IntString
42fn :: str pad right String Int StringString

09.3. Explorando a str a fundo: Exemplos passo a passo de cada funcionalidade

Não basta ver a tabela de assinaturas: vamos explorar cada uma das funcionalidades da lib str através de exemplos progressivos e executáveis em Ridgun. Começaremos pelas duas receitas tabulares de uso diário e depois percorreremos em detalhe todos os cenários funcionais, transformações e casos de fronteira verificados em src/test/ridgun/test str.rg.

09.3.1. Exemplo 1: Fluxo principal em estilo tabular com str

Repare como em Ridgun os sinais = e os passos de transformação com str ficam alinhados como uma tabela limpa, sem variáveis mutáveis desnecessárias nem efeitos colaterais ocultos:

import str

fn :: normalizar cabecera String => String
      normalizar cabecera raw =
        raw str trim -> str to lower -> limpia
        limpia str split " " -> partes
        str join partes "-" -> slug
        str pad right slug 24 "."

09.3.2. Exemplo 2: Composição segura e tratamento de casos de fronteira

Todas as funções da lib str foram desenhadas para se comporem com guardas booleanas | e com as restantes 32 libs do ridgun-libs:

import str

fn :: extraer dominio String => String
      extraer dominio correo =
        str index of correo "@" -> pos
        | pos < 0   = "sin-dominio"
        | otherwise =
          correo str to lower -> minusc
          str replace minusc "@" " en "

09.3.3. Exemplo 3: Pesquisa de subcadeias (str index of), sufixos (str ends with) e predicados de vazio/branco

Neste exemplo prático exploramos de forma exaustiva como a str se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test str search and predicates => ()
      test str search and predicates =
        assert equals (str index of "hello world" "world") 6 "AC1: index_of world"
        assert equals (str index of "hello world" "hello") 0 "AC1: index_of hello at 0"
        assert equals (str index of "ababa" "aba") 0 "AC1: index_of returns first occurrence"
        assert equals (str index of "hello" "xyz") (0 - 1) "AC1: index_of missing"
        assert equals (str index of "short" "much_longer_needle") (0 - 1) "AC1: needle longer than haystack -> -1"
        assert equals (str index of "" "a") (0 - 1) "AC1: non-empty needle in empty haystack -> -1"
        assert equals (str index of "" "") 0 "AC1: empty needle in empty haystack -> 0"
        assert equals (str index of "abc" "") 0 "AC1: empty needle -> 0"

        assert true (str ends with "archive.rglib" ".rglib") "AC1: ends_with true"
        assert true (str ends with "exact" "exact") "AC1: ends_with full string"
        assert true (str ends with "any" "") "AC1: ends_with empty suffix true"
        assert false (str ends with "archive.rg" ".rglib") "AC1: ends_with false"
        assert false (str ends with "short" "longer_suffix") "AC1: ends_with suffix longer than string"

        assert true (str is empty "") "AC1: is_empty true"
        assert false (str is empty " ") "AC1: space is not empty"
        assert true (str is blank "") "AC1: empty is blank"
        assert true (str is blank "   \t\n\r ") "AC1: whitespace-only is blank"
        assert false (str is blank "  x ") "AC1: non-whitespace is not blank"
        ()

09.3.4. Exemplo 4: Corte de espaços (trim, trim left, trim right), substituição (str replace), divisão (str split) e junção (str join)

Neste exemplo prático exploramos de forma exaustiva como a str se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test str trim replace and split => ()
      test str trim replace and split =
        assert equals (str trim "  \thi\n\r ") "hi" "AC2: str_trim mixed ASCII whitespace"
        assert equals (str trim "   \t\r\n") "" "AC2: str_trim all whitespace -> empty"
        assert equals (str trim "") "" "AC2: str_trim empty -> empty"
        assert equals (str trim "no_ws") "no_ws" "AC2: str_trim no whitespace"
        assert equals (str trim left "  abc  ") "abc  " "AC2: str_trim_left"
        assert equals (str trim right "  abc  ") "  abc" "AC2: str_trim_right"

        assert equals (str replace "a-b-c" "-" "_") "a_b_c" "AC2: str_replace single char"
        assert equals (str replace "aaaa" "aa" "b") "bb" "AC2: str_replace non-overlapping left-to-right"
        assert equals (str replace "Hello,World" "World" "") "Hello," "AC2: str_replace deletion to empty"
        assert equals (str replace "abc" "" "x") "abc" "AC2: str_replace empty old leaves string unchanged"
        assert equals (str replace "abc" "z" "y") "abc" "AC2: str_replace absent needle"

        assert equals (str split "a,b,c" ",") ["a", "b", "c"] "AC2: str_split comma"
        assert equals (str split "a,,b," ",") ["a", "", "b", ""] "AC2: str_split consecutive and trailing delim"
        assert equals (str split ",a" ",") ["", "a"] "AC2: str_split leading delim"
        assert equals (str split "a::b::c" "::") ["a", "b", "c"] "AC2: str_split multi-char delimiter"
        assert equals (str split "ab" "") ["a", "b"] "AC2: str_split empty delim splits chars"
        assert equals (str split "" "") [] "AC2: str_split empty string with empty delim -> []"

        assert equals (str join [] "::") "" "AC2: str_join empty list"
        assert equals (str join ["only"] "::") "only" "AC2: str_join singleton"
        assert equals (str join ["alpha", "beta", "gamma"] "::") "alpha::beta::gamma" "AC2: str_join 3 items"
        ()

09.3.5. Exemplo 5: Conversão de caixa ASCII (to upper, to lower), repetição binária $O(\log N)$ (str repeat) e preenchimento tabular (pad left, pad right)

Neste exemplo prático exploramos de forma exaustiva como a str se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test str case repeat and padding => ()
      test str case repeat and padding =
        assert equals (str to upper "Abc! 123 xyz") "ABC! 123 XYZ" "AC3: str_to_upper"
        assert equals (str to lower "Abc! 123 XYZ") "abc! 123 xyz" "AC3: str_to_lower"
        assert equals (str to upper "") "" "AC3: str_to_upper empty"

        assert equals (str repeat "ab" 3) "ababab" "AC3: str_repeat 3"
        assert equals (str repeat "ab" 1) "ab" "AC3: str_repeat 1"
        assert equals (str repeat "ab" 0) "" "AC3: str_repeat 0"
        assert equals (str repeat "ab" (0 - 5)) "" "AC3: str_repeat negative -> empty"
        assert equals (str repeat "" 100) "" "AC3: str_repeat empty string -> empty"

        t0 = sys monotonic ms
        r64k = str repeat "x" 65536
        r256k = str repeat "x" 262144
        t1 = sys monotonic ms
        r8m = str repeat "x" 8000000
        assert equals (str len r64k) 65536 "AC3: str_repeat 65536 length"
        assert equals (str len r256k) 262144 "AC3: str_repeat 262144 length"
        assert equals (str len r8m) 8000000 "AC3: RG-052 str_repeat 8000000 exact length without 1 MiB cap"
        assert true ((t1 - t0) < 200) "AC3: LIB-9 str_repeat 64k+256k in < 200 ms"

        assert equals (str pad left "7" 3 "0") "007" "AC3: str_pad_left"
        assert equals (str pad right "7" 3 "0") "700" "AC3: str_pad_right"
        assert equals (str pad left "7" 4 "") "   7" "AC3: str_pad_left empty pad_ch defaults to space"
        assert equals (str pad left "7" 4 "xyz") "xxx7" "AC3: str_pad_left uses first char of pad_ch"
        assert equals (str pad left "1234" 3 "0") "1234" "AC3: str_pad_left already wider than width"
        assert equals (str pad right "1234" 3 "0") "1234" "AC3: str_pad_right already wider than width"
        ()

09.4. Debaixo do capô: como a str é construída em Ridgun puro (src/main/ridgun/lib/str.rg)

Uma das maiores vantagens do ridgun-libs é que não existem caixas-pretas em C. Pode abrir src/main/ridgun/lib/str.rg e ler exatamente como cada operação é implementada usando pattern matching, árvores de guardas | / |. e recursão de cauda (TCO). Vejamos as peças-chave da sua implementação real:

09.4.1. Implementação interna: ASCII Classification Helpers

Observe como str.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

module :: str

fn :: is ascii space Int  => Bool
      is ascii space code =
        code == 32 or code == 9 or code == 10 or code == 13

fn :: is ascii lower Int  => Bool
      is ascii lower code =  code >= 97 and code <= 122

fn :: is ascii upper Int  => Bool
      is ascii upper code =  code >= 65 and code <= 90

fn :: to upper code Int  => Int
      to upper code code =
        | is ascii lower code = code - 32
        | otherwise           = code

fn :: to lower code Int  => Int
      to lower code code =
        | is ascii upper code = code + 32
        | otherwise           = code

09.4.2. Implementação interna: Whitespace Trimming

Observe como str.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

fn :: first non space idx String Int Int => Int
      first non space idx s idx len =
        | idx >= len                         = len
        | is ascii space (str char at s idx) = first non space idx s (idx + 1) len
        | otherwise                          = idx

fn :: last non space end String Int => Int
      last non space end s end =
        | end <= 0                                 = 0
        | is ascii space (str char at s (end - 1)) = last non space end s (end - 1)
        | otherwise                                = end

fn :: str trim left String => String
      str trim left s      =
        s str len -> len
        first non space idx s 0 len -> start
        str slice s start len

fn :: str trim right String => String
      str trim right s      =
        s str len -> len
        last non space end s len -> end
        str slice s 0 end

fn :: str trim slice String Int Int => String
      str trim slice s start end =
        | start >= end = ""
        | otherwise    = str slice s start end

fn :: str trim String => String
      str trim s      =
        s str len -> len
        first non space idx s 0 len -> start
        last non space end s len -> end
        str trim slice s start end

fn :: str is blank String => Bool
      str is blank s      =  s str trim -> str is empty

09.4.3. Implementação interna: String Splitting & Joining

Observe como str.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

fn :: str split chars String Int Int [String] => [String]
      str split chars s idx slen acc =
        | idx >= slen = acc
        | otherwise   = str split chars s (idx + 1) slen (acc :: [str slice s idx (idx + 1)])

fn :: str split onech loop String Int Int Int Int [String] => [String]
      str split onech loop s d0 pos slen seg_start acc =
        | pos >= slen = acc :: [str slice s seg_start slen]
        | (str char at s pos) == d0 =
          seg = str slice s seg_start pos
          str split onech loop s d0 (pos + 1) slen (pos + 1) (acc :: [seg])
        | otherwise =
          str split onech loop s d0 (pos + 1) slen seg_start acc

fn :: str split loop String String Int Int Int Int Int [String] => [String]
      str split loop s delim d0 pos slen dlen seg_start acc =
        | pos + dlen > slen = acc :: [str slice s seg_start slen]
        | (str char at s pos) == d0 and (str slice s pos (pos + dlen)) == delim =
          seg = str slice s seg_start pos
          str split loop s delim d0 (pos + dlen) slen dlen (pos + dlen) (acc :: [seg])
        | otherwise =
          str split loop s delim d0 (pos + 1) slen dlen seg_start acc

fn :: str split step String String Int Int => [String]
      str split step s delim slen dlen =
        | dlen == 0 = str split chars s 0 slen []
        | dlen == 1 = str split onech loop s (str char at delim 0) 0 slen 0 []
        | otherwise = str split loop s delim (str char at delim 0) 0 slen dlen 0 []

fn :: str split String String => [String]
      str split s      delim  =
        str split step s delim (str len s) (str len delim)

fn :: str join pair step [String] String [String] => [String]
      str join pair step []         _   acc =  acc
      str join pair step (a:[])     _   acc =  acc :: [a]
      str join pair step (a:b:rest) sep acc =
        str join pair step rest sep (acc :: [a + sep + b])

fn :: str join pairs [String] String => String
      str join pairs []       _   =  ""
      str join pairs (x:[])   _   =  x
      str join pairs (x:y:[]) sep =  x + sep + y
      str join pairs xs       sep =
        str join pairs (str join pair step xs sep []) sep

fn :: str join [String] String => String
      str join xs       sep    =  str join pairs xs sep

09.4.4. Implementação interna: Repetition & Padding

Observe como str.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

fn :: str repeat loop String Int String => String
      str repeat loop cur n acc =
        | n <= 0       = acc
        | (n % 2) == 1 = str repeat loop (cur + cur) (n / 2) (acc + cur)
        | otherwise    = str repeat loop (cur + cur) (n / 2) acc

fn :: str repeat String Int => String
      str repeat s      n   =
        | n <= 0 or (str len s) == 0 = ""
        | otherwise                  = str repeat loop s n ""

fn :: pad fill unit String => String
      pad fill unit pad_ch =
        | (str len pad_ch) == 0 = " "
        | otherwise             = str slice pad_ch 0 1

fn :: str pad left step String Int String Int => String
      str pad left step s width pad_ch slen =
        | slen >= width = s
        | otherwise     = (str repeat (pad fill unit pad_ch) (width - slen)) + s

fn :: str pad left String Int String => String
      str pad left s width pad_ch =
        str pad left step s width pad_ch (str len s)

fn :: str pad right step String Int String Int => String
      str pad right step s width pad_ch slen =
        | slen >= width = s
        | otherwise     = s + (str repeat (pad fill unit pad_ch) (width - slen))

fn :: str pad right String Int String => String
      str pad right s width pad_ch =
        str pad right step s width pad_ch (str len s)

09.5. Garantias algorítmicas, memória RMM1/RMM2 e as 5 Regras de Ouro da str

  • Garantia algorítmica e de segurança: Repetição em $O(\log N)$ através de duplicação binária de cadeias, predicados seguros perante agulhas vazias e zero mutação local.
  • Complexidade de pilha $O(1)$ com TCO: Todos os ciclos recursivos em src/main/ridgun/lib/str.rg estão em posição de cauda, pelo que o ridgunc os compila para saltos nativos sem crescimento de pilha.
  • Memória determinística (RMM1/RMM2): Zero pausas de coletor de lixo; todas as estruturas intermédias são libertadas de forma determinística à saída do escopo.
  • Verificação contínua: Testada exaustivamente com stable check e pela suite automatizada src/test/ridgun/test str.rg.

As 5 Regras de Ouro ao programar com a str

  1. Declare import str no início do ficheiro e aproveite a equivalência entre espaços e underscores para que o seu código se leia como prosa.
  2. Alinhe os seus pipelines de dados com =: encadeie as chamadas à str em passos nomeados e deixe o stable format alinhar as colunas.
  3. Aproveite as funções totais da str nas suas guardas |: verifique os valores de retorno ou desempacote os ADTs com pattern matching em vez de assumir que a entrada externa é sempre válida.
  4. Evite copiar grandes estruturas se só precisa de consultar um campo: lembre-se de que no RMM2 os argumentos de entrada não incrementam nem decrementam contadores (+0 / -0).
  5. Combine a str com test (import test): escreva sempre asserções com assert equals ou assert true para fixar os invariantes do seu domínio.

No Capítulo 10 passaremos a explorar em profundidade a lib math (A lib math — Aritmética Segura, Teoria dos Números e Estatística).