Buscando multiplicaciones y divisiones

Desde hace unos meses mi trabajo es hacer auditorías de smart contracts escritos en solidity. Como parte de este trabajo, tengo que buscar multiplicaciones y divisiones en código que no conozco, generalmente usando VSCode.

El tema es que las búsqueda de "*" y "/" dan bocha de falsos positivos porque estos caracteres se usan para marcar comentarios, aparte de las operaciones aritméticas. Por eso uso unas regex para buscarlos, que aunque no son perfectas, me sirven para acotar la cantidad de lugares que tengo que mirar. Quizás les sirvan a ustedes también, así que se las dejo acá abajo:

Multiplicación: [^\s].*[^/*]\*[^/*]

División: [^/*]/[^/*]

Probablemente también puedan serles útiles en otros lenguajes como Python, Java o C++.

Patch en Regexp para poder usarlas como clave en un Hash

Siguiendo mi proyecto de hacer mi wiki en Ruby, encontré un comportamiento muy raro.
Generé un hash (que se llama @rules) que no tiene un elemento que tiene. O sea, @rules[@rules.keys[2]] da nil, pero @rules.values[2] devuelve el objeto asociado a la clave @rules.keys[2]. Como este hash tiene como claves un montón de expresiones regulares, me imaginé que había un problema con el hash y el eql? de Regexp, así que los implementé de nuevo y monkeypatchié.
Este es el código:

class Regexp
 alias_method :old_rapidito_inspect, :inspect

 def inspect
   @inspect = old_rapidito_inspect if @inspect.nil?
   @inspect
 end

 def eql?( other )
   false if other.class != Regexp
   self.inspect == other.inspect
 end

 alias_method :"==", :eql?

 def hash
   self.inspect.hash
 end
end

Esta corrección me anduvo con la siguiente versión de ruby:

$ ruby --version
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]

Espero que les sirva.
Happy hacking,
Aureliano.

Upcase con acentos

En ruby no se calculan los cambios minúscula mayúscula para las letras acentuadas. Por ejemplo:

irb(main):002:0> puts "áa".upcase
áA
=> nil

Para que ande un poco mejor (y tome las letras acentuadas de un montón de lenguajes), encontré un hack que en 10 líneas de código hace que puedan pasarse a mínusculas y mayúsculas los caracteres acentuados. Usando que todas las letras minúsculas y mayúsculas acentuadas están todas juntas, armé un par de gsubs que resuelven el problema.

class String
  alias_method :old_rapidito_upcase, :upcase
  def upcase
    self.gsub( /\303[\240-\277]/ ) do
      |match|
      match[0].chr + (match[1] - 040).chr
    end.old_rapidito_upcase
  end
  
  alias_method :old_rapidito_downcase, :downcase
  def downcase
    self.gsub( /\303[\200-\237]/ ) do
      |match|
      match[0].chr + (match[1] + 040).chr
    end.old_rapidito_downcase
  end
end

Lo que hago acá es reemplazar las funciones upcase y downcase para que manejen los acentos, sumando o restando 32 (40 en octal) al segundo byte. Pongo este código en lang_hacks.rb y sale todo con fritas. Mirando el irb

irb(main):001:0> require 'lang_hacks'
=> true
irb(main):002:0> "aÁ".upcase
=> "A\303\201"
irb(main):003:0> puts "aÁ".upcase
AÁ
=> nil

Espero que les sirva.
Happy hacking,
Aureliano.

Más rapidito

Como les estuve contando, sigo escribiendo mi wiki. Ya parsea un subconjunto interesante del lenguaje definido por trac.
Siguiendo la tradición, les cuento como está avanzando el tokenizer. Al tokenizer lo simplifiqué para que devuelva la expresión regular que matcheo junto con el match (en vez del "tipo"). Esto hizo que la interfase para definir las reglas para tokenizar sea más simple. Si no hay ninguna regla que matchee sigue devolviendo ["string", :text].
Sin más, acá el código:

module Rapidito
  class Tokenizer
  
    def initialize( *delimiters )
      @delimiter_list = delimiters +  [/\z/]
      @match_cache = nil
    end
    
    def source
      valid_cache? ? @match_cache[0].to_s + @source : @source
    end
    
    def source=(s)
      @match_cache = nil
      @source = s
    end
    
    def has_next?
      !@source.empty? || valid_cache?
    end
    
    def valid_cache?
      (!@match_cache.nil?) && (@match_cache[0].to_s.length > 0)
    end
    
    def next_match
      @delimiter_list.map {|regex| [regex.match(@source),regex]}.reject {|p| p[0].nil?}.inject do
        |better,new|
        better_pos = better[0].pre_match.length
        new_pos = new[0].pre_match.length
        
        if better_pos < new_pos
          better
        elsif new_pos < better_pos
          new
        elsif better[0].to_s.length > new[0].to_s.length
          better
        else
          new
        end
      end
    end
    
    def next_token
      if @match_cache #cached delimiter
        rv = @match_cache
        @match_cache = nil
        return rv
      end
      
      match = next_match
      p = match[0].pre_match.length
      @source = @source[p + match[0].to_s.length, @source.length]
      
      if p == 0 #delimiter
        match
      else #text
        @match_cache = match
        [match[0].pre_match, :text]
      end
    end
    
    def all_tokens
      tokens = []
      while has_next?
        tokens << next_token
      end
      tokens
    end
  end
end

Y si miran los tests de unidad, van a ver que también quedaron más lindos:

require 'test/unit'
require 'rapidito/tokenizer'

include Rapidito

class TokenizerTest < Test::Unit::TestCase
  
  def test_no_token
    tok = Tokenizer.new
    tok.source = "aaaa"
    assert_equal true, tok.has_next?
    assert_equal ["aaaa", :text], tok.next_token
    assert_equal false, tok.has_next?
  end
  
  def assert_all_tokens( expected, tokenizer )
    assert_equal expected, 
      tokenizer.all_tokens.map { |token, kind| [token.to_s, kind] }
  end
  
  def test_two_delimiters
    tok = Tokenizer.new( 
      /\|/, /;;/ 
    )
    
    tok.source = "aa|bbb;;;;cccc"
    assert_all_tokens \
      [ ["aa", :text], ["|", /\|/], ["bbb", :text], 
        [";;", /;;/], [";;", /;;/], ["cccc", :text] ], 
      tok
    
    tok.source = "aa;;bbb||cccc"
    assert_all_tokens \
      [ ["aa", :text], [";;", /;;/], ["bbb", :text], 
        ["|", /\|/], ["|", /\|/], ["cccc", :text] ], 
      tok
  end
  
  def test_choose_longest_match
    tok = Tokenizer.new( 
      /aa/, /aaa/
    )
    tok.source = "aaaa"
    assert_all_tokens [ ["aaa", /aaa/], ["a", :text ] ], tok
  end
  
  def test_reset_precache
    tok = Tokenizer.new( 
      /\|/, /,/
    )
    tok.source = "original start|original end"
    tok.next_token
    tok.source = "new start,new end"
    assert_equal ["new start", :text], tok.next_token
  end
  
  def test_almost_finished
    tok = Tokenizer.new( /!/ )
    tok.source = "bang!"
    tok.next_token
    assert_equal true, tok.has_next?
    tok.next_token
    assert_equal false, tok.has_next?
  end
  
  def test_carriage_return_ending
    tok = Tokenizer.new( /!/ )
    tok.source = "bang!\n"
    tok.next_token
    assert_equal true, tok.has_next?
    tok.next_token
    assert_equal true, tok.has_next?
    assert_equal "\n", tok.next_token[0].to_s
    assert_equal false, tok.has_next?
  end
  
  def test_transparent_caching
    tok = Tokenizer.new( /!/ )
    tok.source = "bang!pum"
    tok.next_token
    
    assert_equal "!pum", tok.source
  end
  
  def test_match_klass
    tok = Tokenizer.new( /!/ )
    tok.source = "!bang!pum"
    
    assert_equal \
      [MatchData, String, MatchData, String], 
      tok.all_tokens.map { |tok, kind| tok.class }
  end
end

Happy hacking,
Aureliano.

Pequeñas delicias de las expresiones regulares

Como les conté acá y acá, estoy escribiendo un tokenizador para un wiki que estoy programando. Y hoy me encontré con una cosa muy extraña de las expresiones regulares.
En ruby la función match sirve para buscar el primer match de una regex dentro de un string. Por ejemplo (usando el irb):

irb(main):001:0> m = /a/.match "babab"
=> #<MatchData "a">
irb(main):002:0> m.pre_match
=> "b"
irb(main):003:0> m[0]
=> "a"

En particular, el pre_match es lo que está antes del match en el string. También según había entendido (mal) /\Z/ matchea con el final del string. Por ejemplo:

irb(main):004:0> m = /\Z/.match "hola"
=> #<MatchData "">
irb(main):005:0> m.pre_match
=> "hola"

Pero, /\Z/ tiene un comportamiento muy extraño, aunque documentado, cuando el último caracter antes del final es un \n. Lo que pasa es que el pre_match queda ¡sin el \n del final!. Lo muestro en el irb:

irb(main):006:0> m = /\Z/.match "\n"
=> #<MatchData "">
irb(main):007:0> m.pre_match
=> ""

Para que no se manduque el \n, hay que usar /\z/ (¡en minúscula!):

irb(main):008:0> m = /\z/.match "\n"
=> #<MatchData "">
irb(main):009:0> m.pre_match
=> "\n"

Por lo tanto tuve que tocar el tokenizer, ahora la función de initialize quedó así (miren el cambio de la "Z" a "z"):

    def initialize( delimiters )
      @delimiter_list = [[/\z/, :finish]] + 
        delimiters.to_a.map { |k,arr| arr.map { |re| [re, k] } }.inject([]) { |ac,ps| ac + ps }
      @match_cache = nil
    end

Y el test que captura el problema que genera usar \Z en vez de \z quedó así:

  def test_carriage_return_ending
    tok = Tokenizer.new( :a_kind => [/!/] )
    tok.source = "bang!\n"
    tok.next_token
    assert_equal true, tok.has_next?
    tok.next_token
    assert_equal true, tok.has_next?
    assert_equal "\n", tok.next_token[0].to_s
    assert_equal false, tok.has_next?
  end

Happy hacking,
Aureliano.

Tokenizer de rapidito, segunda versión

Como les conté hace un par de posts, estoy haciendo un wiki y blogueando sobre el tokenizer
Hoy les cuento de la segunda versión del tokenizer. A esta versión (que no es compatible con la anterior) le agregué la posibilidad de asociar un tipo (kind) a cada regexp que define un token. Por lo tanto, el método next_match ahora devuelve un par [match, kind]. Los matches de texto común (no delimitadores) tienen kind :text. Los matches de los delimitadores vienen con la MatchData entera, para poder usarla si interesan partes del match a la hora de procesar el token. También dejé de usar =~ para matchear regexps, ya que el
Me quedaron un par de cosas con dudas después de implementar esto.

1. ¿Se puede hacer en ruby que busque un match de una regexp en un string a partir de una posición? Hacer una regexp del tipo /.{34,}(regex de verdad)/ no vale.
2. ¿Puedo forzar a la unión de expresiones regulares a buscar el match más largo (en vez del primero que matchee)?

A pesar de las dudas, igual tengo una versión que creo que es significativamente mejor que la versión anterior.
Así que como la otra vez dejo el código:

module Rapidito
  class Tokenizer
  
    attr_reader :source
  
    def initialize( delimiters )
      @delimiter_list = [[/\Z/, :finish]] + 
        delimiters.to_a.map { |k,arr| arr.map { |re| [re, k] } }.inject([]) { |ac,ps| ac + ps }
      @match_cache = nil
    end
    
    def source=(s)
      @match_cache = nil
      @source = s
    end
    
    def has_next?
      !@source.empty? || valid_cache?
    end
    
    def valid_cache?
      (!@match_cache.nil?) && (@match_cache[0].to_s.length > 0)
    end
    
    def next_match
      @delimiter_list.map {|p| [p[0].match(@source), p[1]]}.reject {|p| p[0].nil?}.inject do
        |better,new|
        better_pos = better[0].pre_match.length
        new_pos = new[0].pre_match.length
        
        if better_pos < new_pos
          better
        elsif new_pos < better_pos
          new
        elsif better[0].to_s.length > new[0].to_s.length
          better
        else
          new
        end
      end
    end
    
    def next_token
      if @match_cache #cached delimiter
        rv = @match_cache
        @match_cache = nil
        return rv
      end
      
      match = next_match
      p = match[0].pre_match.length
      @source = @source[p + match[0].to_s.length, @source.length]
      
      if p == 0 #delimiter
        [match[0].to_s, match[1]]
      else #text
        @match_cache = match
        [match[0].pre_match, :text]
      end
    end
    
    def all_tokens
      tokens = []
      while has_next?
        tokens << next_token
      end
      tokens
    end
  end
end

Y los tests de unidad:

require 'test/unit'
require 'rapidito/tokenizer'

include Rapidito

class TokenizerTest < Test::Unit::TestCase
  
  def test_no_token
    tok = Tokenizer.new( {} )
    tok.source = "aaaa"
    assert_equal true, tok.has_next?
    assert_equal ["aaaa", :text], tok.next_token
    assert_equal false, tok.has_next?
  end
  
  def assert_all_tokens( expected, tokenizer )
    assert_equal expected, 
      tokenizer.all_tokens.map { |token, kind| [token.to_s, kind] }
  end
  
  def test_two_delimiters
    tok = Tokenizer.new( 
      :a_kind => [/\|/, /;;/] 
    )
    
    tok.source = "aa|bbb;;;;cccc"
    assert_all_tokens \
      [ ["aa", :text], ["|", :a_kind], ["bbb", :text], 
        [";;", :a_kind], [";;", :a_kind], ["cccc", :text] ], 
      tok
    
    tok.source = "aa;;bbb||cccc"
    assert_all_tokens \
      [ ["aa", :text], [";;", :a_kind], ["bbb", :text], 
        ["|", :a_kind], ["|", :a_kind], ["cccc", :text] ], 
      tok
  end
  
  def test_choose_longest_match
    tok = Tokenizer.new( 
      :a_kind => [/aa/, /aaa/] 
    )
    tok.source = "aaaa"
    assert_equal [ ["aaa", :a_kind], ["a", :text ] ], tok.all_tokens
  end
  
  def test_reset_precache
    tok = Tokenizer.new( 
      :a_kind => [/\|/, /,/]
    )
    tok.source = "original start|original end"
    tok.next_token
    tok.source = "new start,new end"
    assert_equal ["new start", :text], tok.next_token
  end
  
  def test_almost_finished
    tok = Tokenizer.new( :a_kind => [/!/] )
    tok.source = "bang!"
    tok.next_token
    assert_equal true, tok.has_next?
    tok.next_token
    assert_equal false, tok.has_next?
  end
end

Happy hacking,
Aureliano.

Tokenizer de rapidito

Después de mirar un rato el estado de las bibliotecas para hacer wikis en Ruby, y descubrir que ninguna me servía, Decidí que tenía que poner cartas en el asunto y hacer la mía. Mi idea es implementar el markup de Trac, haciéndolo extensible, y agregarle un par de cositas que por ahora son un secreto :-p.

Lo importante del asunto es que puse manos en el asunto. Al final, después de un intento fallido de hackear mi camino al andar, decidí que lo mejor es armar un tokenizer y un parser que use esos tokens para generar el árbol del que extraeré el HTML.

Así que me puse a programar. Como no encontré ningún tokenizer en ruby, programé uno. El tokenizer se contruye con un montón de expresiones regulares que definen cada delimitador. Después se le setea una fuente de caracteres (un string) y separa el string en los delimitadores de arriba (que se devuelven como símbolos) y cadenas que no matchean con ninguno de los delimitadores (que devuelve como strings).

Bueno, basta de cháchara, acá tá el código:

module Rapidito
  class Tokenizer
  
    def initialize( *delimiters )
      @regexp = Regexp.union( *delimiters  + [/$/] )
    end
    
    attr_accessor :source
    
    def has_next?
      ! @source.empty?
    end
    
    def next_token
      p = (@source =~ @regexp)
      if p == 0 #delimiter
        token = nil
        @source.sub!( @regexp ) { |match| token=match.to_sym; "" }
        token
      else #text
        token = @source[0,p]
        @source = @source[p,@source.length]
        token
      end
    end
    
    def all_tokens
      tokens = []
      while has_next?
        tokens << next_token
      end
      tokens
    end
    
  end
end

Y, acá abajo la única documentación que hice hasta ahora, o sea los tests de unidad:

require 'test/unit'
require 'rapidito/tokenizer'

include Rapidito

class TokenizerTest < Test::Unit::TestCase
  
  def test_no_token
    tok = Tokenizer.new
    tok.source = "aaaa"
    assert_equal true, tok.has_next?
    assert_equal "aaaa", tok.next_token
    assert_equal false, tok.has_next?
  end
  
  def test_two_delimiters
    tok = Tokenizer.new( /\|/, /;;/ )
    tok.source = "aa|bbb;;;;cccc"
    assert_equal [ "aa", :"|", "bbb", :";;", :";;", "cccc" ], tok.all_tokens
    
    tok.source = "aa;;bbb||cccc"
    assert_equal [ "aa", :";;", "bbb", :"|", :"|", "cccc" ], tok.all_tokens
  end
  
  def test_choose_first_match
    tok = Tokenizer.new( /aa/, /aaa/ )
    tok.source = "aaa"
    assert_equal [ :aa, "a" ], tok.all_tokens
  end
  
end

Happy hacking,
Aureliano.

PD: ¿Prefieren que ponga el código con syntax highlighting?