// --------------------------------------------------------------------------
// A fuzzer library  
// used as an introduction to monadic computation in JavaScript.
//
// Copyright Mu Dynamics Research Labs 2009.
// All rights reserved.
//
// http://www.mudynamics.com
// http://labs.mudynamics.com
// http://www.pcapr.net
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
// 
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
// 
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
// 
//     * Neither the name the author nor the names of other
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


// --------------------------------------------------------------------------
// Some helper functions

// map() applies function 'f' on all elements of array 'as'
var map = function(f, as) {
  return (as.length > 1)? [f(as[0])].concat(map(f, as.slice(1))) : [f(as[0])];
};

// Curry function for partial application
// http://ejohn.org/blog/partial-functions-in-javascript/
var curry = function(f) {
  return function() {
    var as = Array.prototype.slice.apply(arguments);
    return function () {
      return f.apply(this, as.concat(Array.prototype.slice.apply(arguments)));
    };
  };
};

// More an inheritance than a copy function
// used to generate different versions of an object
// see mutate() function
var O = function() {};
var copy = function(o) {
  O.prototype = o;
  return new O();
};

// id() just passes input object to the output
var id = function(o) { return o; };


// --------------------------------------------------------------------------
// Monadic operators return() and bind()
// For simplicity we call monads actions.
// This implementation does not carry a state.
// See last section of this file for details
// how to handle state inside computation.

// ret() wraps the value 'v' into an action.
// This action will always return the 
// constant value 'v' when executed.
var ret = function(v) {
  return function (o) { return v; };
};

// bind() for sequencing of action executions
// bind() applies function 'f' on the execution result of action 'a'
// and executes the resulting action to give the final result.
var bind = function(a, f) {
  return function(o) { return f(a(o))(o); };
};


// --------------------------------------------------------------------------
// Some generic functions build on top of ret() and bind()

// seq() executes actions 'as' and combines the results using function 'f'.
// 'f' takes the result of previous executions and the current one
// and returns the combined result.
var seq = function(as, f) {
  var rec = function(as, r) {
    return (as.length > 0)? 
      bind(as[0], function(n) { return rec(as.slice(1), f(r, n)); }) : 
      ret(r);
  };
  return rec(as);
};

// Repeat executes action 'a' 'n'-times and combines
// the results using 'f', similar as seq().
// We use curry to support partial application
// see overflow() or property() function for details.
var repeat = curry(function(a, f, n) {
  return seq(map(ret(a), new Array(n)), f);
});

// Some useful result combination functions for seq() and repeat()

// cons concatenates the result into an array for example:
// seq([ret(1), ret(2)], cons)() => [1,2]
var cons = function(r, n) { return (r || []).concat(n); };

// accumulate result, for example: seq([ret(1), ret(2)], sum)() => 3
var sum  = function(r, n) { return (r || 0) + n; };

// Join results as string
// seq([ret(1), ret(2)], join)() => "12" 
var join = function(r, n) { return (r || "") + n; };

// or is used to return the passed object as result, see update()
var or   = function(r, n) { return r || n; };

// Just a helper function that wraps 'ls' array values to ret() fuzzers
var list = function(ls) { return map(ret, ls); };


// --------------------------------------------------------------------------
// Handling objects

// Property applies action 'a' on an object property with name 'n'
// Using partial application with curry, we can use property()
// as an selector, for example:
// var obj = { name:"John", age:20 };
// var name = property("name");
// name(ret("Mike"))(obj) will return the object { name:"Mike", age:20 }
var property = curry(function(n, a) { 
  return function(o) { o[n] = a(o[n]); return o; };
});

// Runs fuzzers 'as' on the input and returns the resulting object
var update = function(as) { 
  return seq(as, or); 
};

// Same as update, but returns one object variation for every fuzzer in 'as'
var mutate = function(as) {
  var cs = map(function(a) { return function(o) { return a(copy(o)); }; }, as);
  return seq(cs, cons);
};

// Every fuzzer is applied on all results of previous fuzzers
// The result is a permutation over all results
var permutate = function(as) {
  return bind(as[0], function(fs) { 
    return (as.length > 1)?  
      mutate(map(ret, map(permutate(as.slice(1)), fs))) :
      mutate(map(ret, fs));
    });
};


// --------------------------------------------------------------------------
// Let's do some fuzzing

// Overflow fuzzer, for example
// overflow(5) will generate 'AAAAA'
var overflow = repeat(ret('A'), join);

// Prepends string s to the input
var prepend = function(s) {
  return function(o) { return s + o; };
};

// Another prepend() implementation using bind()
var prepend_with_bind = function(s) {
  return bind(id, function(r) { return ret(s + r); });
};

// An example fuzzer from the blog post
// fuzzes on objects of the form:
//   var request_object = {
//     method : 'GET',
//     uri	: 'index.html'
//   };
var blog_fuzzer = function() {
  var method = property('method');
  var uri = property('uri');

  var request_methods = map(ret, ['GET', 'POST', 'HEAD']);
  var requests = mutate(map(method, request_methods));

  var overflows = map(overflow, [1, 2, 4, 8]);
  var uri_overflows = mutate(map(uri, [id].concat(overflows)));

  var updir = update([uri(prepend('../'))]);
  var updirs = mutate(map(repeat(updir, or), [1,2,3]));

  var uris = permutate([uri_overflows, updirs]);

  return permutate([requests, uris]);
};

// --------------------------------------------------------------------------
// Monadic computation with state

// To use state inside a computation we can create 
// a state object that holds the object to fuzz,
// for example:
var state = function(o) { 
  return { o : o /* other properties and functions */ };
};

// To pass the state from one to another computation we
// additionally need to change ret() and bind() as following:

// The result of ret_with_state() is an object that contains
// the value 'v' and the state object
var ret_with_state = function(v) {
  return function (s) { return { v : v, s : s }; };
};

// In bind_with_state() we pass only the value 'v' 
// of the action 'a' result to 'f' and execute the 
// resulting fuzzer on the new state returned by 'a'.
var bind_with_state = function(a, f) {
  return function(s) { 
    var r = a(s);
    return f(r.v)(r.s); 
  };
};

// Any fuzzer we defined above does not need to be changed
// as far it does not use the input object explicitly,
// like prepend.

// To simplify the execution of a fuzzer we can additionally
// define a helper function like
var fuzz = function(f, o) {
  return f(state(o)).v;
};
// and use like fuzz(overflow, obj);