--- /dev/null
+[submodule "combstruct"]
+ path = combstruct
+ url = http://genal.algo-prog.info/repo/boltzoc
--- /dev/null
+all:
+ (cd test; make)
+
+clean:
+ (cd test; make clean)
--- /dev/null
+Subproject commit bc9436dca2821c3664b0ea0a260de76e2988d464
--- /dev/null
+module Srnggen
+ module Comb
+ module Aliased
+ def to_sys
+ "ref(" + @alias[7..-1] + ")"
+ end
+ end
+
+ module Epsilon
+ def to_sys
+ "epsilon()"
+ end
+ end
+
+ module Atom
+ def to_sys
+ if weight==1 then
+ "atom()"
+ else
+ (["atom()"]*weight).inject {|s, n| "sum(#{s}, #{n})"}
+ end
+ end
+ end
+
+ class Mark
+ include Atom
+ end
+
+ module Sequence
+ def to_sys
+ e = elem.to_sys
+ "prod(#{e}, seq(#{e}))"
+ end
+ end
+
+ module Product
+ def to_sys
+ elems.collect {|e| e.to_sys}.inject {|p, e| "prod(#{p}, #{e})"}
+ end
+ end
+
+ module Union
+ def to_sys
+ elems.collect {|e| e.to_sys}.inject {|s, e| "sum(#{s}, #{e})"}
+ end
+ end
+
+ module Reference
+ def to_sys
+ "ref(" + ref[7..-1] + ")"
+ end
+ end
+ end
+
+ class Document
+ def to_sys f
+ reste = @defs.keys - @eq
+ eq = (@eq+reste).sort{|n,m| n[7..-1].to_i <=> m[7..-1].to_i}
+ f.puts <<"EOF"
+#include <stdio.h>
+#include <stdlib.h>
+#include "../src/combstruct.h"
+
+int main(int argc, char **argv)
+{
+ comb_sys sys;
+ double z, *y;
+
+ sys = empty_sys();
+#{eq.collect {|n| " add_sys(sys, #{@defs[n].to_sys}); // #{n}"}.join("\n")}
+ add_sys(sys, #{root.to_sys});
+ y = malloc(sys_len(sys)*sizeof(double));
+ z = sing_sys(sys, 10e-8, 10e-5, y);
+ printf(\"start=%.10lf\\n\", y[#{eq.size}]);
+ printf(\"x=%.10lf\\n\", z);
+#{eq.collect {|n| " printf(\"#{n}=%.10lf\\n\", y[#{n[7..-1].to_i - 1}]);"}.join("\n")}
+ free(y);
+ free_sys(sys);
+ return 0;
+}
+EOF
+ end
+ end
+end
--- /dev/null
+module Srnggen
+ #TODO implement datatypes from xsd http://books.xmlschemata.org/relaxng/relax-CHP-19.html
+ class Callbacks
+ @@gen = {}
+ @@weight = {}
+
+ def Callbacks.gen type, xml
+ if @@gen.has_key? type
+ @@gen[type].call(xml)
+ else
+ type.to_s
+ end
+ end
+
+ def Callbacks.weight type, xml
+ if @@weight.has_key? type
+ @@weight[type].call(xml)
+ else
+ 1
+ end
+ end
+
+ @@texts = []
+
+ def Callbacks.gen_text xml
+ @@texts[rand(@@texts.length)]
+ end
+
+ def Callbacks.weight_text xml
+ 1
+ end
+
+ def Callbacks.add type, gen, weight
+ @@gen[type] = gen
+ @@weight[type] = weight
+ end
+
+ def Callbacks.add_array type, a
+ n = a.length
+ @@gen[type] = proc {|xml| a.[] rand(n)}
+ @@weight[type] = proc {|xml| n}
+ end
+
+ Callbacks.add_array "integer", [0, 1, 42]
+ Callbacks.add_array "float", [0.0, 0.5, 4.2]
+ Callbacks.add_array "Name", ["x", "y", "z"]
+
+ @@texts.concat [
+ "foo", "bar", "baz"]
+#"Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.",
+#"Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium doloremque laudantium, totam rem aperiam, eaque ipsa quae ab illo inventore veritatis et quasi architecto beatae vitae dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur magni dolores eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci velit, sed quia non numquam eius modi tempora incidunt ut labore et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure reprehenderit qui in ea voluptate velit esse quam nihil molestiae consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla pariatur?",
+#"But I must explain to you how all this mistaken idea of denouncing pleasure and praising pain was born and I will give you a complete account of the system, and expound the actual teachings of the great explorer of the truth, the master-builder of human happiness. No one rejects, dislikes, or avoids pleasure itself, because it is pleasure, but because those who do not know how to pursue pleasure rationally encounter consequences that are extremely painful. Nor again is there anyone who loves or pursues or desires to obtain pain of itself, because it is pain, but because occasionally circumstances occur in which toil and pain can procure him some great pleasure. To take a trivial example, which of us ever undertakes laborious physical exercise, except to obtain some advantage from it? But who has any right to find fault with a man who chooses to enjoy a pleasure that has no annoying consequences, or one who avoids a pain that produces no resultant pleasure?"]
+ end
+end
--- /dev/null
+module Srnggen
+ # generic module representing a primitive in the combstruct language
+ module Comb
+ # make all the necessary pre-calculations for the sampling
+ def compile
+ elems.each {|e| e.compile}
+ compile_self
+ end
+
+ # store in @oracle the value for this node. This method is generally
+ # overridden by subclasses.
+ def compile_self
+ end
+
+ def indets h
+ elems.each {|e| h = e.indets h}
+ h
+ end
+
+ def to_sys
+ elem.to_sys
+ end
+
+ module Grammar
+ include Comb
+ end
+
+ # empty unary construction
+ module Marker
+ include Comb
+ def compile_self
+ @oracle = elem.oracle
+ end
+ end
+
+ module Def
+ include Comb
+ end
+
+ module Aliased
+ def set_content x
+ @alias = x
+ end
+
+ def indets h
+ h[@alias] = nil
+ h
+ end
+
+ def replace n, v
+ if @alias == n
+ extend Dereferenced
+ set_content v
+ end
+ end
+ end
+
+ module Dereferenced
+ def set_content x
+ @elems << x
+ @to_sys = nil
+ end
+
+ def to_sys
+ @to_sys ||= elem.to_sys
+ end
+
+ def indets h
+ elem.indets h
+ end
+
+ def replace n, v
+ elem.replace n, v
+ end
+ end
+
+ def replace n, v
+ elems.each {|e| e.replace n, v}
+ end
+
+ # An element not contributing to the size of the object
+ module Epsilon
+ include Comb
+ end
+
+ # An element contributing <tt>weight</tt> to the size of the object
+ module Atom
+ include Comb
+ NAME = "x"
+ def weight
+ 1
+ end
+
+ def compile_self
+ @oracle = doc.oracle[NAME]*weight
+ end
+ end
+
+ class Mark < Node
+ include Atom
+ def initialize doc
+ super nil, doc
+ end
+ end
+
+ # A sequence of one or more constructions
+ module Sequence
+ include Comb
+ def Sequence.geom i
+ (Math.log(rand)/Math.log(i)).ceil
+ end
+
+ def compile_self
+ @oracle = elem.oracle/(1 - elem.oracle)
+ @magic = elem.oracle
+ end
+ end
+
+ # The product of two constructions
+ module Product
+ include Comb
+ def compile_self
+ @oracle = 1
+ elems.each {|e| @oracle *= e.oracle}
+ end
+ end
+
+ # The union of two constructions
+ module Union
+ include Comb
+ def compile_self
+ @oracle, t, @magic = 0, 0, []
+ elems.each {|e| @oracle += e.oracle}
+ elems.each do |e|
+ t += e.oracle
+ @magic << t/oracle
+ end
+ end
+ end
+
+ # a reference to an element defined elsewhere
+ module Reference
+ include Comb
+ def indets h
+ h[ref] = nil
+ h
+ end
+
+ def replace n, v
+ if ref == n
+ extend(v.kind_of?(Def) ? Dereferenced : Aliased)
+ set_content v
+ end
+ end
+
+ def compile_self
+ @oracle = doc.oracle[ref]
+ end
+ end
+ end
+end
--- /dev/null
+# File containing the classes corresponding to each construction of the
+# simple syntax of RELAX NG
+require 'callbacks'
+module Srnggen
+ class Document
+ def def_class
+ Node::Define
+ end
+ def root_class
+ Node::Start
+ end
+ end
+
+ class Node
+ #class representing a RELAX NG grammar.
+ class Grammar < Node
+ include Comb::Grammar
+ def initialize xml, doc
+ super
+ xml.each_element {|e| @elems << Node.parse(e, doc)}
+ end
+
+ def gen
+ elem.gen
+ end
+ end
+
+ class Start < Node
+ include Comb::Marker
+ def name; "start" end
+ def gen
+ elem.gen
+ end
+ end
+
+ class Define < Node
+ # each element contributes 1 to the size. A definition may concern a set
+ # of names or a class of names, we must thus take that in account for the
+ # weight of the definition.
+ include Comb::Def
+ include Comb::Marker
+ def initialize xml, doc
+ super
+ @name = xml.attributes["name"]
+ end
+ attr :name
+ def gen
+ elem.gen
+ end
+ end
+
+ class Element < Node
+ include Comb::Product
+ def initialize xml, doc
+ super
+ @elems << Comb::Mark.new(doc)
+ end
+
+ def gen
+ Res.new [elem(2).gen.to_e(elem(1).gen.to_s)]
+ end
+ end
+
+ class Notallowed < Node
+ include Comb::Epsilon
+ def initialize xml, doc
+ super nil, doc
+ end
+ #TODO
+ end
+
+ class Except < Node
+ include Comb::Epsilon
+ def initialize xml, doc
+ super nil, doc
+ end
+ #TODO
+ end
+
+ class Param < Node
+ include Comb::Epsilon
+ def initialize xml, doc
+ super nil, doc
+ end
+ #TODO
+ end
+
+ class Empty < Node
+ include Comb::Epsilon
+ def gen
+ Res.new
+ end
+ end
+
+ class Text < Node
+ #TODO parametrer la longueur du texte produit
+ #TODO donner le choix de peser x ou len*x
+ include Comb::Atom
+
+ def weight
+ Callbacks.weight_text @xml
+ end
+
+ def gen
+ Res.new [Callbacks.gen_text(@xml)]
+ end
+ end
+
+ class Data < Node
+ include Comb::Atom
+ def initialize xml, doc
+ super
+ @type = xml.attributes["type"]
+ @lib = xml.attributes["datatypeLibrary"]
+ end
+
+ def weight
+ Callbacks.weight(@type, @xml)
+ end
+
+ def gen
+ Res.new [Callbacks.gen(@type, @xml)]
+ end
+ end
+
+ class Value < Node
+ include Comb::Atom
+ def initialize xml, doc
+ super
+# @lib = xml.attributes["datatypeLibrary"]
+# @type = xml.attributes["type"]
+# @ns = xml.attributes["ns"]
+ @val = xml.text
+ end
+
+ def gen
+ Res.new [@val]
+ end
+ end
+
+ class List < Node
+ include Comb::Marker
+ # res should only contain strings
+ def gen
+ Res.new [elem.gen.compact]
+ end
+ end
+
+ class Attribute < Node
+ include Comb::Product
+ def initialize xml, doc
+ super
+ @elems << Comb::Mark.new(doc)
+ end
+
+ def gen
+ Res.new [], {elem(1).gen.to_s => elem(2).gen.to_s}
+ end
+ end
+
+ class Ref < Node
+ include Comb::Reference
+ attr_reader :ref
+ def initialize xml, doc
+ super
+ @ref = xml.attributes["name"]
+ end
+
+ def gen
+ @doc.defs[@ref].gen
+ end
+ end
+
+ class Oneormore < Node
+ include Comb::Sequence
+ def gen
+ r = Res.new
+ Sequence.geom(@magic).times {r.join elem.gen}
+ r
+ end
+ end
+
+ class Choice < Node
+ include Comb::Union
+ def gen
+ elem(rand < @magic[0] ? 1 : 2).gen
+ end
+ end
+
+ class Group < Node
+ include Comb::Product
+ def gen
+ elem(1).gen.join elem(2).gen
+ end
+ end
+
+ #TODO this is not really a product but a union of the attributes
+ #and an interleaving of the elements of the children
+ class Interleave < Node
+ include Comb::Product
+ def gen
+ elem(1).gen.interleave elem(2).gen
+ end
+ end
+
+ class Anyname < Node
+ include Comb::Epsilon
+ def gen
+ Res.new ["anyname"]
+ end
+ end
+
+ class Nsname < Node
+ include Comb::Epsilon
+ def initialize xml, doc
+ super
+ @ns = xml.attributes["ns"]
+ end
+
+ def gen
+ Res.new ["nsname"]
+ end
+ end
+
+ class Name < Node
+ include Comb::Epsilon
+ def initialize xml, doc
+ super
+# @ns = xml.attributes["ns"]
+ @name = xml.text
+ end
+
+ def gen
+ Res.new [@name]
+ end
+ end
+ end
+end
--- /dev/null
+module Srnggen
+ # generic class for nodes of a grammar.
+ #
+ # Subclasses inherit from class Node. They include one of the modules in
+ # Comb to specify the combinatorial construction to which they
+ # correspond.
+ class Node
+ # parse a grammar
+ def Node.parse xml, doc
+ const_get(xml.name.capitalize).new xml, doc
+ end
+
+ attr_reader :doc, :oracle, :elems
+
+ def elem x=1
+ @elems[x-1]
+ end
+
+ def initialize xml, doc
+ @xml, @doc, @oracle, @elems = xml, doc, 1, []
+ xml.each_element {|e| @elems << Node.parse(e, doc)} if xml
+ end
+
+ def inspect
+ "#{self.class}(#{@elems.join(",")})"
+ end
+
+ def to_s
+ inspect
+ end
+ end
+end
--- /dev/null
+module Srnggen
+ # Class representing a hash table of the values of the oracle for each element
+ class Oracle
+ # source must be the name of a file containing name=value pairs for each
+ # element or a Grammar for which the oracle will be calculated using Maple
+ def initialize source
+ source = calculate source if source.class == Document
+ @values, @comments = {}, []
+ IO.foreach source do |s|
+ s.chomp!
+ if s =~ /^#/
+ @comments << s
+ else
+ k, v = s.split '='
+ @values[k] = v.to_f
+ end
+ end
+ end
+
+ def to_s
+ (@comments + @values.collect {|k, v| "#{k}=#{v}"}).join "\n"
+ end
+
+ # get the value of the oracle on a given element
+ def [] x
+ @values[x]
+ end
+ end
+end
--- /dev/null
+module Srnggen
+ class Res
+ def initialize seq=[], att={}
+ @seq, @att = seq, att
+ end
+
+ attr_reader :att, :seq
+
+ def to_e name
+ res = REXML::Element.new name
+ @seq.each do |e|
+ case e
+ when REXML::Element
+ res << e
+ when String
+ res.add_text e
+ end
+ end
+ res.add_attributes @att
+ res
+ end
+
+ def join r
+ @att.update r.att
+ @seq += r.seq
+ self
+ end
+
+ def compact
+ @seq = [ @seq.join(" ") ]
+ self
+ end
+
+ def interleave r
+ @att.update r.att
+ res, pos = [], []
+ s1, s2 = @seq.length, r.seq.length
+ 1.upto(s1+s2) {|i| pos << i}
+ s1.times {pos.delete_at rand(pos.length)}
+ 1.upto(s1+s2) do |i|
+ if pos.include? i
+ res << r.seq.shift
+ else
+ res << @seq.shift
+ end
+ end
+ @seq = res
+ self
+ end
+
+ def to_s
+ @seq.join("")
+ end
+
+ def element
+ #TODO verify that there is only one element in @seq
+ @seq.first
+ end
+ end
+end
--- /dev/null
+#!/usr/bin/ruby
+
+# :main: srnggen.rb
+#
+# = SrngGen - Simple RELAX NG Generation
+#
+# This package contains a simple and flexible sampler for XML documents respecting
+# a given
+# {RELAX NG}[http://www.oasis-open.org/committees/relax-ng/spec-20011203.html]
+# grammar. It can be used as a standalone application or as a
+# library.
+#
+# The RELAX NG grammar given must use the
+# {simple syntax}[http://www.oasis-open.org/committees/relax-ng/spec-20011203.html#simple-syntax].
+# You can transform any RELAX NG grammar into its equivalent simplified syntax
+# using the rng2srng[http://www.kohsuke.org/relaxng/rng2srng/] tool.
+#
+# To calculate values needed for the sampling Maple[http://www.maplesoft.com/] is
+# used as a co-routine. The program thus expects that <tt>maple</tt> is in the
+# path. There is however a way, explained further, to invoke Maple manually.
+#
+# == Overview
+#
+# This package is intended as a prototype to demonstrate how we can easily apply
+# recent developments in random sampling provided by combinatory theory to
+# generate random inputs of good quality for testing computer programs.
+#
+# In this prototype we focus on programs that read XML documents respecting a
+# given RELAX NG grammar. A RELAX NG grammar can easily be translated to the
+# combinatorial description of a class of trees. From there we can automatically
+# derive a random sampler for objects in that class.
+#
+# == Summary
+#
+# You can generate 10 random XML documents respecting a given grammar
+# % ruby srnggen.rb -n 10 grammar.srng
+# The resulting XML will be placed in the files <tt>result*.xml.</tt>
+#
+# If you plan to sample many times using the same grammar, you can keep the result
+# of the Maple invocation in a file
+# % ruby srnggen.rb -c grammar.srng > oracle
+# and later use this file for the sampling
+# % ruby srnggen.rb -O oracle grammar.srng
+#
+# If Maple is not installed on your machine, you can get the Maple program in a
+# file to execute it elsewhere
+# % ruby srnggen.rb -m grammar.srng > program.mpl
+# % maple -q program.mpl > oracle
+#
+# == Usage
+#
+# srnggen.rb [OPTION] ... grammar.srng [oracle]
+#
+# Options are:
+#
+# [<tt>-h, --help</tt>]
+# show help
+#
+# [<tt>--compile, -c</tt>]
+# calculate oracle values
+#
+# [<tt>--n</tt> <i>N</i>]
+# number of xml documents to produce
+#
+# [<tt>--oracle, -O</tt>]
+# file containing oracle values
+#
+# [<tt>--maple, -m</tt>]
+# output maple programm to calculate oracle values
+#
+# [<tt>--precision</tt> <i>N</i>, <tt>-p</tt> <i>N</i>]
+# precision for the calculation of the singularity
+#
+# [<tt>--callbacks</tt> <i>File</i>, <tt>-C</tt> <i>File</i>]
+# file containing callbacks definitions
+
+require 'rexml/document'
+require 'tmpdir'
+require 'node'
+require 'comb'
+require 'res'
+require 'oracle'
+
+module Srnggen
+ class Document
+ def initialize source
+ @defs, @oracle = {}, {}
+ @doc = REXML::Document.new source
+ @node = Node.parse @doc.root, self
+ @node.elems.each do |e|
+ case e
+ when def_class:
+ @defs[e.name] = e
+ when root_class:
+ @root = e
+ end
+ end
+ @eq = @defs.keys
+ end
+
+ # Definition objects for all the elements except root
+ attr :defs
+ attr :root
+ # The Oracle object containing the values needed for the sampling
+ attr :oracle
+
+ # generate one random XML document
+ def gen
+ @node.gen.element
+ end
+
+ # use the values in an Oracle to calculate all the intermediate values
+ # needed for the sampling
+ def compile oracle
+ @oracle = oracle
+ @node.compile
+ end
+
+ def inspect
+ "<#{self.class} #{defs.size + 1} definitions>"
+ end
+
+ def simplify
+ h, eq = {}, []
+ # group definitions by value
+ @defs.each_pair do |k,v|
+ e = v.to_sys
+ h[e] = [] unless h.has_key? e
+ h[e] << k
+ end
+ # keep one definitions for each value
+ h.each_value do |a|
+ t = a.shift
+ eq << t
+ a.each do |n|
+ @defs[n].extend Comb::Aliased
+ @defs[n].set_content t
+ @node.elems.each {|e| e.replace n, t}
+ end
+ end
+ # remove definitions with no indets in value
+ tmp = eq.collect do |n|
+ n if @defs[n].indets(Hash.new).keys.empty?
+ end.compact
+ tmp.each do |n|
+ eq.each {|v| @defs[v].replace n, @defs[n]}
+ root.replace n, @defs[n]
+ eq.delete tmp
+ end
+ # remove non-recursive definitions
+ loop do
+ tmp = eq.collect do |n|
+ n unless @defs[n].indets(Hash.new).keys.include? n
+ end.compact.first
+ break unless tmp
+ eq.each {|v| @defs[v].replace tmp, @defs[tmp]}
+ root.replace tmp, @defs[tmp]
+ eq.delete tmp
+ end
+ @eq = eq
+ end
+ end
+end
+
+if __FILE__ == $0
+ require 'getoptlong'
+
+ opts = GetoptLong.new(
+ [ '--help', '-h', GetoptLong::NO_ARGUMENT ],
+ [ '--compile', '-c', GetoptLong::NO_ARGUMENT ],
+ [ '--system', '-s', GetoptLong::NO_ARGUMENT ],
+ [ '--backend', '-b', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '--language', '-l', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '--oracle', '-O', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '-n', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '--precision', '-p', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '--callbacks', '-C', GetoptLong::REQUIRED_ARGUMENT ],
+ [ '--no-simplify', GetoptLong::NO_ARGUMENT ]
+ )
+ compile, system, backend, language, n, oracle_file, precision, d, callbacks, nosimplify =
+ false, false, "c", "relaxng", 1, nil, "5", nil, nil, false
+ opts.each do |opt, arg|
+ case opt
+ when '--help': RDoc::usage
+ when '--compile': compile = true
+ when '--system': system = true
+ when '--backend': backend = arg
+ when '--language': language = arg
+ when '-n': n = arg.to_i
+ when '--oracle': oracle_file = arg
+ when '--precision': precision = arg
+ when '--callbacks': callbacks = arg
+ when '--no-simplify': nosimplify = true
+ end
+ end
+ if ARGV.length != 1 then
+ require 'rdoc/usage'
+ RDoc::usage(0, 'Usage')
+ end
+ require "backend/" + backend
+ require "language/" + language
+ File.open(ARGV.shift) {|f| d = Srnggen::Document.new f}
+ Srnggen.module_eval IO.readlines(callbacks).join if callbacks
+ d.simplify unless nosimplify or oracle_file
+ if system then d.to_sys $stdout; exit 0 end
+ oracle = Srnggen::Oracle.new(oracle_file ? oracle_file : d)
+ if compile then puts oracle; exit 0 end
+ d.compile oracle
+ writer = REXML::Formatters::Pretty.new
+ writer.width = 8096
+ 1.upto n do |i|
+ File.open("result#{i}.xml", "w") {|f| writer.write d.gen, f; f.puts}
+ end
+end
--- /dev/null
+CFLAGS=-Wall
+LDFLAGS=-L../combstruct/src -lm -lcombstruct -Wl,-rpath ../combstruct/src
+PROGS=$(basename $(wildcard *.c))
+
+all: $(PROGS)
+
+%: %.c
+ $(CC) $(LDFLAGS) -o $@ $<
+
+clean:
+ rm -f $(PROGS) *.o
projects / xmlgen / commitdiff