Category Archives: development

Parsing files using Groovy closures

At work I recently created a Groovy automation script that parsed FTP log files and generated a web based report. This script was then added as a scheduled job in the open-source Jenkins continuous integration server. Groovy support is built in to Jenkins.

Groovy certainly made this very easy (from a Java perspective). The script used the Groovy GDK (extensions to Java’s classes) and iteration via closures, first of the target folder, and then on each file’s lines. A regexp was used to grab the info. Finally a Groovy Builder was used to create the HTML page.

After looking at the solution I thought it could be simplified if there was support for this pattern in some kind of template or API. A sample approach is shown below. Of course, this is only applicable for line oriented data files. When data spans multiple lines one must use more stateful approaches or parsing tools.

Updates

  • Sep 23, 2013: Version of this code at a Gist here.
  • Sep 23, 2013: Changed method signature of gather at folder. But, perhaps, the gather at file level does not need the filter closure.

References

  1. Groovy
  2. Closures in Groovy
  3. Builders in Groovy
  4. File in Groovy JDK
  5. Regular Expressions in Groovy
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Predictive Automotive Apps

In a previous post, “Synergistic Social Agent Network Cloud” I argued for more proactive apps. I was just reading something that is related to that topic: “Ford Hybrid’s EV+ Feature Learns and Automatically Adjusts Powertrain to Deliver More Electric-Only Driving” Also see “Proactive Agents.”

And, today I see this new product: MEMS tackles contextual awareness. The “future” may arrive one day.

The company Omron has been researching technological progress. They came up with SINIC:

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

List sorting using topological ordering of a digraph

By creating a pseudo weighted directed graph on a list of elements, it is possible to apply graph algorithms to the sorting problem. This offers an alternative to approaches such as QuickSort or Merge sort. As an experiment a Java program implementation is shown.

Terms: topological sorting, directed acyclic graph, Java, JUnit, algorithm

This subject is continued in Linear list sorting using weighted digraph possible?

Pseudo weighted DAG
Given a set of numbers, for example, [9, 2, 12, 40, 12, 3, 1], we can create a directed acyclic graph (DAG) where each number is a vertex and an outgoing edge points to all other elements greater then it. “9” will have an edge to 12 and 40. “12” will have an edge to 40 and also to the other “12” element. This latter edge will be a special ‘equal’ edge and indicates duplicates. If this were an ordinary edge, the graph would have cycles.

Transforming this list into a DAG yields:

list converted to digraph
list transform

Note that once this transformation is complete we essentially know the order of vertices, we just don’t have a linear arrangement yet. We don’t have to revisit any element and compare it with another as in some other sorting algorithms. Of course, this initial step is not efficient, O(n^2).

Topological sorting
A topological sorting (toposort) of a directed graph is a linear ordering of its vertices. An advantage of a toposort is that it runs in linear time. To this time must be added the graph construction phase, and in this implementation, a final step is inserting duplicate elements into the result.

A toposort of a complex graph can have many solutions. As applied here, there is only one solution. But, this remains to be proven or is already known to be true in Graph Theory. See uniqueness.

Implementation

Listing one below contains the Java implementation that sorts the list of elements given above. The program contains an embedded JUnit test. In the test the method loadDag(map, data) creates the DAG. While creating the edges, if a source and sink have values that are equal the ‘equal’ edge is created. The sink vertex is then marked as a duplicate.

The modified toposort in the program will skip vertices that are marked as duplicate. The resulting list is sorted, but is missing the duplicate vertices. In the final step each node in the result set is visited and if it has any outgoing equal edges these destination nodes are inserted into the final result list.

The resultant outputs of the program is:

Sort with dupes: [one:1, two:2, three:3, nine:9, twelve:12, twelve2:12, forty:40]
Sort with unique: [one:1, two:2, three:3, nine:9, twelve:12, forty:40]

Nested JUnit test classes
Though not part of the topic, the programming example used a nested JUnit test class, an interesting approach.

Summary
Presented was a possible approach to list sorting by use of graph algorithms. A Java programming language based example implementation was given.

Listing 1, source available here.

GraphSort.java
package com.octodecillion.sort;

import static org.hamcrest.core.Is.is;
import static org.hamcrest.core.IsEqual.equalTo;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/**
 * 
 * Sorting using directed graph embedding based topological ordering.
 * 
 * @author Josef Betancourt
 * @since 20120101T1212
 * 
 * 
 *        Example code based on code created from M. Jessup's *
 *        {@link "http://stackoverflow.com/questions/2739392/sample-directed-graph-and-topological-sort-code"}
 *        Which itself is an implementation of one presented in Wikipedia
 *        article: {@link "http://en.wikipedia.org/wiki/Topological_sort"}
 * 
 * 
 */
public class GraphSort {

	/**
	 * Modification of algorthim presented in Wikipedia article.
	 * 
	 * {@link "http://en.wikipedia.org/wiki/Topological_sort"}
	 * 
	 * <pre>
	 * 		L ? Empty list that will contain the sorted elements
	 * 		S ? Set of all nodes with no incoming edges
	 * 		while S is non-empty do
	 * 		    remove a node n from S
	 * 		    insert n into L
	 * 		    for each node m with an edge e from n to m do
	 * 		        remove edge e from the graph
	 * 		        if m has no other incoming edges then
	 * 		            insert m into S
	 * 		if graph has edges then
	 * 		    return error (graph has at least one cycle)
	 * 		else 
	 * 		    return L (a topologically sorted order)
	 * </pre>
	 * 
	 * See also: Algorithm presented in "Algorithms", 4th Edition by R.
	 * Sedgewick and K. Wayne.
	 * {@link "http://algs4.cs.princeton.edu/42directed/Topological.java.html"}
	 * *
	 * 
	 * @param <T>
	 * @param allNodes
	 * @return sorted list or empty list if not possible
	 * @throws IllegalArgumentException
	 *             if graph has cycles
	 */
	public static <T> ArrayList<Node<T>> topoSort(final Node<T>[] allNodes) {

		ArrayList<Node<T>> workList = new ArrayList<Node<T>>();

		HashSet<Node<T>> sinks = new HashSet<Node<T>>();
		for (Node<T> n : allNodes) {
			if (n.inEdges.size() == 0) { // indegree zero? Or source?
				sinks.add(n);
			}
		}

		while (!sinks.isEmpty()) {
			Node<T> nextNode = sinks.iterator().next();
			sinks.remove(nextNode);

			if (nextNode.duplicate) {
				continue;
			}

			workList.add(nextNode);

			for (Iterator<Edge<T>> it = nextNode.outEdges.iterator(); it
					.hasNext();) {

				Edge<T> outNode = it.next();
				Node<T> dest = outNode.to;
				it.remove();
				dest.inEdges.remove(outNode);

				if (dest.inEdges.isEmpty()) {
					sinks.add(dest);
				}
			}
		}

		// All edges are removed? If not, we have a cycle.
		for (Node<T> n : allNodes) {
			if (!n.inEdges.isEmpty()) {
				throw new IllegalArgumentException("Cycle present. Node, "
						+ n.name
						+ " has inEdges. Topological sort not possible");
			}
		}

		ArrayList<Node<T>> resultList = new ArrayList<Node<T>>();
		for (Node<T> node : workList) {
			resultList.add(node);

			if (!node.equiEdges.isEmpty()) {
				for (Iterator<Edge<T>> iterator = node.equiEdges.iterator(); iterator
						.hasNext();) {
					Edge<T> edge = iterator.next();
					resultList.add(edge.to);
				}
			}

		}

		return resultList;
	} // topoSort

	/**
	 * A node.
	 * 
	 * @param <T>
	 */
	static class Node<T> {
		public final String name;
		public final T value;
		public final HashSet<Edge<T>> inEdges;
		public final HashSet<Edge<T>> outEdges;
		public final HashSet<Edge<T>> equiEdges;
		public boolean duplicate;

		public Node(final String name, final T value) {
			this.name = name;
			this.value = value;
			this.duplicate = false;
			inEdges = new HashSet<Edge<T>>();
			outEdges = new HashSet<Edge<T>>();
			equiEdges = new HashSet<Edge<T>>();
		}

		public Node<T> addEdge(final Node<T> node) {
			Edge<T> e = new Edge<T>(this, node);
			outEdges.add(e);
			node.inEdges.add(e);
			return this;
		}

		@SuppressWarnings("unchecked")
		public Node<T> addEdges(final Node<T>... nodes) {
			for (int i = 0; i < nodes.length; i++) {
				Node<T> node = nodes[i];
				Edge<T> e = new Edge<T>(this, node);
				outEdges.add(e);
				node.inEdges.add(e);
			}

			return this;
		}

		public Node<T> addEquiEdge(final Node<T> node) {
			Edge<T> e = new Edge<T>(this, node);
			equiEdges.add(e);
			// node.equiEdges.add(e);
			node.duplicate = true;
			return this;
		}

		@Override
		public String toString() {
			return String.format("%s:%s", name, value);
		}
	} // Node<T>

	/**
	 * A directed edge.
	 */
	static class Edge<T> {
		public final Node<T> from;
		public final Node<T> to;

		public Edge(final Node<T> from, final Node<T> to) {
			this.from = from;
			this.to = to;
		}

		@Override
		public boolean equals(final Object obj) {
			@SuppressWarnings("unchecked")
			Edge<T> e = (Edge<T>) obj;
			return (e.from == from) && (e.to == to);
		}

		@Override
		public int hashCode() {
			return super.hashCode();
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return String.format("%s->%s", from, to);
		}
	} // Edge<T>

	// ====================================================================
	// Nested JUnit test.
	// ====================================================================

	/**
	 * 
	 * Tests {@link GraphSort}.
	 * 
	 * Uses nested JUnit testing approach advocated by Ben J. Christensen in <a
	 * href=
	 * "http://benjchristensen.com/2011/10/23/junit-tests-as-inner-classes/"
	 * >"JUnit Tests as Inner Classes"</a>
	 * 
	 * @author jbetancourt
	 * 
	 */
	@RunWith(JUnit4.class)
	public static class GraphSortTest {
		@SuppressWarnings("unchecked")
		private Node<Integer>[] allNodes = new Node[0];

		/**
		 * Sort list with no duplicate nodes.
		 */
		@SuppressWarnings("boxing")
		@Test
		public void should_sort_without_duplicates() {
			uniqueList();
			ArrayList<Node<Integer>> result = GraphSort.topoSort(allNodes);

			assertFalse("empty result", result.isEmpty());
			assertThat(Integer.valueOf(result.size()), is(equalTo(6)));
			assertTrue("result not sorted", inOrder(result));

			System.out.println("Sort with unique: "
					+ Arrays.toString(result.toArray()));
		}

		/**
		 * Sort list with no duplicate nodes.
		 */
		@SuppressWarnings("boxing")
		@Test
		public void should_sort_with_duplicates() {
			dupeList();
			ArrayList<Node<Integer>> result = GraphSort.topoSort(allNodes);

			assertFalse("empty result", result.isEmpty());

			System.out.println("Sort with dupes: "
					+ Arrays.toString(result.toArray()));

			assertThat(Integer.valueOf(result.size()), is(equalTo(7)));
			assertTrue("result not sorted", inOrder(result));

		}

		@SuppressWarnings("unchecked")
		private void uniqueList() {
			String nodeData = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;";
			String dagData = "one,three;one,twelve;one,forty;one,two;one,nine;two,twelve;two,forty;two,three;two,nine;three,nine;three,forty;three,twelve;nine,twelve;nine,forty;twelve,forty";

			Map<String, Node<Integer>> nodes = loadNodes(nodeData);
			loadDag(nodes, dagData);

			List<Node<Integer>> list = new ArrayList<Node<Integer>>();

			for (Entry<String, Node<Integer>> entry : nodes.entrySet()) {
				list.add(entry.getValue());
			}

			allNodes = list.toArray(new Node[list.size()]);

		}

		@SuppressWarnings("unchecked")
		private void dupeList() {
			String nodeData = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;twelve2,12";
			String dagData = "one,three;one,twelve;twelve,twelve2,one,forty;one,two;one,nine;two,twelve;two,forty;two,three;two,nine;three,nine;three,forty;three,twelve;nine,twelve;nine,forty;twelve,forty;twelve2,forty";

			Map<String, Node<Integer>> nodes = loadNodes(nodeData);
			loadDag(nodes, dagData);

			List<Node<Integer>> list = new ArrayList<Node<Integer>>();

			for (Entry<String, Node<Integer>> entry : nodes.entrySet()) {
				list.add(entry.getValue());
			}

			allNodes = list.toArray(new Node[list.size()]);

		}

		/**
		 * 
		 * @param nodes
		 * @param dagData
		 */
		private void loadDag(final Map<?, ?> nodes, final String dagData) {
			String[] dagStrings = dagData.split(";");

			for (int i = 0; i < dagStrings.length; i++) {
				String[] spec = dagStrings[i].split(",");

				@SuppressWarnings("unchecked")
				Node<Integer> source = (Node<Integer>) nodes.get(spec[0]);
				@SuppressWarnings("unchecked")
				Node<Integer> sink = (Node<Integer>) nodes.get(spec[1]);

				if (!sink.duplicate || (source.value != sink.value)) {
					source.addEdge(sink);
				} else {
					source.addEquiEdge(sink);
				}

			}

		}

		/**
		 * 
		 * @param nodeData
		 * @return
		 */
		private Map<String, Node<Integer>> loadNodes(final String nodeData) {
			Map<String, Node<Integer>> nodeMap = new HashMap<String, Node<Integer>>();

			String[] nodeSpec = nodeData.split(";");

			for (int i = 0; i < nodeSpec.length; i++) {
				String[] string = nodeSpec[i].split(",");
				String name = string[0];
				String value = string[1];

				@SuppressWarnings("boxing")
				Node<Integer> node = new Node<Integer>(name,
						Integer.parseInt(value.trim()));

				nodeMap.put(name, node);
			}

			return nodeMap;

		}

		/**
		 * Check that list is sorted.
		 * 
		 * @param nodes
		 * @return
		 */
		@SuppressWarnings("boxing")
		private boolean inOrder(final ArrayList<Node<Integer>> nodes) {
			boolean result = true;
			Iterator<Node<Integer>> iterator = nodes.iterator();
			Node<Integer> prev = iterator.next();

			while (iterator.hasNext()) {
				Node<Integer> current = iterator.next();

				// in order?
				if (!(current.value >= prev.value)) {
					result = false;
					break;
				}
			}

			return result;
		}
	}

} // End class GraphSort.java

The graph was created with GraphViz using the input:

## File: listDAG.gv
## Command to generate: dot -Tpng -o listDAG.png listDAG.gv 
digraph {
	
	rankdir=LR
	
	
	A [label="9"];      
	B [label="2"];     
	C [label="12"];      
	D [label="40"];      
	E [label="12"];      
	F [label="3"];     
	G [label="1"];      
	G->B
	G->F
	G->A
	G->C
	G->D
	G->E
	B->F
	B->A
	B->C
	B->E
	B->D
	F->A
	F->C
	F->E
	F->D
	A->C
	A->D
	A->E
	C->D
	C->E [label="equi", fontcolor=darkgreen]
	
	label="\nlist: [9, 2, 12, 40, 12, 3, 1] transformed to DAG by Josef Betancourt";
}

Genesis of this idea
One day I was wondering if randomness could be used to sort. The idea I had was, as it turns out, a “better” Bozosort. Instead of swapping indiscriminately, I would swap elements if they were out of order. I had other ideas. But, then I started drawing some diagrams, and it led to other ideas based on graph construction.

I gave up the use of randomization. Is the technique presented using graphs unique? Does it work? Can it scale? Or Does it add to the list of bozo sorts?

Funny xkcd comic: “Ineffective Sorts

Updates
20130104:

  • Recreated the image using LR ranking in GraphViz.
  • Fixed algorithm which broke when I added missing arc from second 12 to 40. TG for Unit tests.

Further reading

  1. Weighted graphs and networks
  2. M. Jessup’s sample code on StackOverflow
  3. Topological.java
  4. topological_sort
  5. 4.2 Directed Graphs
  6. Directed graph
  7. “JUnit Tests as Inner Classes”
  8. Bogosort
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Nested CSS Grid Hello World!

CSS based grids are a powerful approach to creating HTML web interfaces. There are now hundreds of CSS Frameworks that support Grid layouts.

I’ve used the 1KB grid system before, but have yet to really understand how to use grid systems well. Recently I was taking another look at this topic. One thing is very obvious, the documentation and examples of many of these are not very good. What if there were an example that all framework would implement that would showcase their use? In programming we usually would do a “Hello World!” program and extend that to say the same thing using the technologies in question, like JMS, for example.

So a solution would have to exercise the core feature set or solution set of a generic grid, and be easy to implement. One should not have to be a high-order expert in CSS to understand the solution. Below I created a simple ‘Hello world!’ that shows nested columns in use. Of course, it would need expansion to show more features and difficulties in using a CSS Grid. It would also need a real designer to create something that also looks good.

Example of nested columns using BluCSS. I just took the demo page as an example and changed it to do what I wanted. The BluCSS stylesheet includes media queries to help toward a “responsive” design. Note that I changed the “container” to 100% width. Why have large monitors if pages won’t use the space?

Screen capture of my example rendered in FireFox’s Responsive Design View. In this tool a 1200 x 800 viewport correctly allows rotate, however, on a real smartphone, Samsung Note, the vertical view is stacked. Hmm.

screen capture snippet

<!DOCTYPE html>
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; 
		charset=ISO-8859-1">
	<meta charset="utf-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">	
	<meta name="viewport" content="width=device-width, initial-scale=1.0">	
	<title>BluCSS - Nested Grid Demo</title>
	<!-- Author: Josef Betancourt; Date: 20121221T1840	 -->
	<link rel="stylesheet" href="css/blucss.css">
	<link rel="stylesheet" href="css/myStyle.css">
	<script 
		src="https://ajax.googleapis.com/ajax/libs/jquery/1.8.3/jquery.min.js">
	</script>
	<script 
		src="js/ndhw.js">
	</script>
	<script>
		$(document).ready(function(){  	});		  
	</script>		
</head>
<body style="margin:1em;">
  <div class="container">
	<div class="blu_8">
	
		<!-- ########################## -->	
		<div class="blu_10 header">
			<h2 class="">CSS Grid Hello World!</h2>
		</div>		
		<!-- ########################## -->	
	
		<!-- ########################## -->	
		<div class="blu_1 test">a</div><div class="blu_1 test">b</div>
		<div class="blu_1 test">c</div><div class="blu_1 test">d</div>
		<div class="blu_1 test">e</div><div class="blu_1 test">f</div>
		<div class="blu_1 test">g</div><div class="blu_1 test">h</div>
		<div class="blu_1 test">i</div><div class="blu_1 test">j</div>
		<!-- ########################## -->	
	
		<!-- ########################## -->	
		<div class="blu_1 test">k</div>	
		<div class="blu_1 test">l</div>
		<div class="blu_5 test ">
			<div class="blu_10 box">5</div>
			<div class="blu_10">nested columns</div>
			<div class="blu_2 color1">2</div>
			<div class="blu_3 color1">3</div>
			<div class="blu_3 color1">3</div>
			<div class="blu_2 color1">2</div>			
		</div>	
		<div class="blu_1 test">m</div>
		<div class="blu_1 test">n</div>
		<div class="blu_1 test">o</div>
		<!-- ########################## -->
		<div class="clear">
			<div class="blu_1 test">1</div><div class="blu_1 test">2</div>
			<div class="blu_1 test">3</div><div class="blu_1 test">4</div>
			<div class="blu_1 test">5</div><div class="blu_1 test">6</div>
			<div class="blu_1 test">7</div><div class="blu_1 test">8</div>
			<div class="blu_1 test">9</div><div class="blu_1 test">10</div>
		</div>	
		
		<div class="blu_10">
			<a id="showBT" href="#" class="buttonCls" onclick="getSource()">source</a>
			<a id="hideBT" href="#" class="buttonCls" style="display:none;">hide</a>		
		</div>
		<div class="blu_10 color2">
			<pre class="box" id="theSrc" style="display:none;"></pre>		
		</div>		
	</div>
	
	<div class="blu_2 omega color2">	
		<div id="rs">rs</div>
	</div>	
			
	<!-- ########################## -->	
	<div class="blu_8 test color2">8</div>
	<!-- ########################## -->
	<div class="blu_1 test color2">1</div>	
	<div class="blu_1 test color2">1</div>
	
	<div class="blu_8">&nbsp;</div>	
	<div class="blu_2" style="font-size:.5em;">
			20121221T1840, J.Betancourt	
  	</div>	
	<!-- ########################## -->	
  	
 </div>
</html>

Summary
Created an example ‘hello world’ CSS Grid use. The example also includes the use of AJAX with JQuery to show the HTML source. Not part of the topic but was an interesting thing to get to work. I wonder if that technique can be used to show other things like log files.

Question: Since CSS Grids rely on horizontal flow, how are they a grid? Maybe they should be called CSS sliding rows that sometimes align into columns. 🙂

Related reading

  • CSSButtonGenerator
  • Responsive Design View
  • Responsive web design
  • Grids CSS, as bad as HTML markup abuse, or worse
  • BluCSS
  • The 1KB CSS Grid, http://www.1kbgrid.com/
  • The Semantic Grid System
  • My (current) take on CSS Preprocessors
  • 45+ CSS Grid Layout Generators
  • ” Which Is Right for Me? 22 Responsive CSS Frameworks and Boilerplates Explained “, http://designshack.net/articles/css/which-is-right-for-me-22-responsive-css-frameworks-and-boilerplates-explained/
  • ” Which CSS Grid Framework Should You Use for Web Design?”, http://net.tutsplus.com/tutorials/html-css-techniques/which-css-grid-framework-should-you-use-for-web-design/
  • “Grid System Generator”, gridsystemgenerator.com
  • “Designing With Grid-Based Approach”, http://www.smashingmagazine.com/2007/04/14/designing-with-grid-based-approach/
  • The Ultimate Collection of 50+ Resources for Grid Lovers, http://designshack.net/articles/layouts/the-ultimate-collection-of-50-resources-for-grid-lovers/
  • “Grids Are Good (Right?)”, M. Boulton, Khoi Vinh. http://www.subtraction.com/pics/0703/grids_are_good.pdf
  • “Rethinking CSS Grids”, http://www.markboulton.co.uk/journal/rethinking-css-grids
  • ” Rolling Your Own Grid Layouts on the Fly Without a Framework”, http://designshack.net/articles/css/rolling-your-own-grid-layouts-on-the-fly-without-a-framework/
  • “Design By Grid”, http://www.designbygrid.com/
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Synergy now easier to configure

Just updated Synergy to version 1.4.10 which uses a GUI to help layout the different screen relationships. Nice. Took about two minutes to install and share the keyboard and mouse between a PC and laptop.

Synergy lets you easily share your mouse and keyboard between multiple computers on your desk, and it’s Free and Open Source. Just move your mouse off the edge of one computer’s screen on to another. You can even share all of your clipboards. All you need is a network connection. Synergy is cross-platform (works on Windows, Mac OS X and Linux).

Basically, it is a software Keyboard Video Mouse (KVM) switch.

Links

  1. Synergy
  2. How To Control Multiple Computers With A Single Keyboard And Mouse
  3. Synergy for Mac: SynergyKM
  4. KVM Switch
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

application security using a copy-on-write virtual machine

An architecture is possible that uses a lightweight VM for use as an application sandbox. Instead of the duplication of an OS plus a run-time environment, this virtual machine uses the host environment as a read-only resource. This allows the VM to serve as a Sandbox that allows reads and writes to the file system, but only the VM address space is modified. Since the host OS environment is supplying a-prior values, the total VM footprint is minimal. This architecture is able to serve as a base for secure application solutions.

In practice an application is installed into a host OS and via installation and use it creates a cache mirror of changed OS data and resources that it would normally have modified in the traditional installation. This application and the ‘cache’ is then versioned and mirrored. If the application is compromised it is deleted or the cache is rolled back to the period before the compromise.

There are many types of virtual machines. Two examples are the system VM types such as VMWare or Oracle VirtualBox, another is the focused process VM such as the Java Virtual Machine, Dalvik VM, or the Common Language Runtime. The former are complex and since they must “dupe” an OS are large and complex. The latter application level VMs are smaller and optimized for a single runtime environment. Each of these have corresponding security issues.

A virtual machine is usually a sandbox in implementation and provides a level of security. However, the cost is that it must duplicate OS resources. In contrast the sandboxed process VM type being discussed here depends on a real OS host and does as little duplication of the environment as possible. It is not generic, but integral to a specific application program or system.

Though this may possibly help in making an application survive destruction by protecting the storage address space, there is still the issue of active infiltration and use of system resources such as networks accessible to the application. Perhaps this type of VM will make conventional security practices and tools more useful?

Summary
Just an idea off the top of my head. Haven’t looked to see if is unique or even remotely makes sense.

Updates
June 12, 2013: “Security Anti-Pattern – Mobile Hypervisors (for user facing VM’s)
August 31, 2013: Was just reading about Docker which uses the LXC (LinuX Containers). Maybe that is what I had in mind.

Further reading

  1. Android Application Sandbox
  2. Virtual Machine
  3. Sandbox
  4. Pushing The Limits of Web Browsers … or Why Speed Matters
  5. Sandboxing Java Code
  6. Security Anti-Pattern – Mobile Hypervisors (for user facing VM’s)
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Use Groovy to find path of a file in a directory tree

Find the path of a file according to its name and possible partial path within a directory tree.

I was working on a program that could be executed from a few possible locations in a project. The program had to load a data file. So, there had to be a configured way to locate that file. I had a thought, why not just find it in the project location hierarchy. It would have to search both up and down the tree, and to avoid finding the incorrect file, allow the use of a partial path. That is, you can search for “foo.dat” or “data\foo.dat”, and it would find, for example, “resources\data\foo.dat”.

I used Groovy 2.0 and the Eclipse plugin. Both are great! The static type checker is a very welcome addition to this language.

Notes:

  • This may be a bad idea.
  • Not intended to be a general purpose “Find” as in the the Linux utility of that name.
  • Source also available as a gist:
    git clone git://gist.github.com/3076035.git gist-3076035
import groovy.transform.TypeChecked

/**
 * search file according to its name in directory 
 * and subdirectories
 */
@TypeChecked
class FindFile {
	String basePath; // for unit testing		

	/**
	 * 
	 * Find a file within a hierarchy given a path.
	 * 
	 * @param basePath  which folder to start the search
	 * @param targetPath the name or a sub path
	 * @return the path where the file was found
	 */
	public String find(String basePath, String targetPath){
		def result = ''
		String curPath = basePath + File.separator + targetPath
		
		if(new File(curPath).exists()){
			result = curPath;
		}else{
			result = searchUp(basePath, targetPath)			
			if(!result){
				result = searchDown(basePath, targetPath)				
			}			
		}
		
		result
	}
	
	/**
	 * 
	 * @param targetPath the name or a sub path
	 * @return the path where the file was found
	 */
	public String find(String targetPath){
		def result = ''
		String curDir = getCurrentPath()		
		find(curDir, targetPath)		
	}	
	
	/** depth first recursive search of sub directories */
	def searchDown(String startDir, String targetPath){
		def result = "";
		File curDir = new File("$startDir")
		
		try{
		   curDir.eachDirRecurse { File cur ->				
			def fp = new File(cur.path + 
                                  File.separator + targetPath)				
			if(fp.exists()){
			  result = fp
			  throw BREAK
		        }
		   }
		}catch(BreakClosureException ex){
			// 
		}

		result		
	}
	
	/** Search for path in parent directories  */
	def searchUp(String startDir, String targetPath){
		def result = "";
		
		File lastDir = new File(startDir)
		def up = File.separator + '..'
		File curDir = new File("$startDir$up")
		
		try{
			while(curDir.getCanonicalPath() != 
                          lastDir.getCanonicalPath()){
				def fp = new File(curDir.path + 
                                     File.separator + targetPath)
	
				if(fp.exists()){
					result = fp
					throw BREAK
				}
				
				lastDir = curDir
				curDir =  new File("${curDir.path}$up")				
			}	
		}catch(BreakClosureException ex){
			//
		}

		result
		
	}
	
	protected String getCurrentPath(){
		//return basePath ? basePath : new File(".").path
		new File(".").path
	}	

        // for exit out of closures
	final static BREAK = new BreakClosureException() 	

	static class BreakClosureException extends Throwable {

		public BreakClosureException() {
			super()
		}

	}

}

That wasn’t so bad. Worse was the JUnit test used to create it. I had to use a little Groovy AOP to intercept the SUT’s getCurrentDir() method. But, then I just added the basePath field which made testing much easier. The interception is left in for my future reference on how to do this.

import static org.junit.Assert.*;

import groovy.mock.interceptor.MockFor
import org.junit.Before
import org.junit.After
import org.junit.Test
import static org.hamcrest.CoreMatchers.*

/**
 * 
 * @author jbetancourt
 *
 */
class FindFileTest {
	ProxyMetaClass proxy
	MethodInterceptor theInterceptor = new MethodInterceptor()
	//def BASEPATH = System.properties.get("java.io.tmpdir")
	def BASEPATH = "c:\temp\"
	def hierarchy = "\one\two\three\four"
	
	@Test
	void should_find_in_sub_directory(){
		File tempFile = createTempFile("${BASEPATH}one\two\three\four")
		
		println("Testing:  BASEPATH=$BASEPATH, tempFile=$tempFile, 
                   tempFile name=${tempFile.getName()}")
		def actual = findAtFolder(BASEPATH, tempFile, tempFile.getName())
		def expected = "${BASEPATH}one\two\three\four\${tempFile.name}"			
		assertThat(normalize(actual), is(normalize(expected)))		
	}
	
	@Test
	void should_find_in_higher_level(){
		File tempFile = createTempFile("$BASEPATH\one\")
		
		def actual = findAtFolder("$BASEPATH\one\two\three\four", 
                     tempFile, tempFile.getName())
		def expected = "$BASEPATH\one\${tempFile.name}"			
		assertThat(normalize(actual), is(normalize(expected)))		
	}
	
	@Test
	void should_not_find(){
		def tempFile = new File("$BASEPATH\x.y")
		def actual = findAtFolder("$BASEPATH\one\two\three\four", 
                       tempFile, "$BASEPATH\one\abc.tmp")
		def expected = ""			
		assertThat(normalize(actual), is(normalize(expected)))		
	}
	
	@Test
	void should_find_subpath(){
		File tempFile = createTempFile("$BASEPATH\one\two\three")
		
		def actual = findAtFolder("$BASEPATH\one\two\three\four", 
                        tempFile, "\two\three\" + tempFile.getName())
		def expected = "$BASEPATH\one\two\three\${tempFile.name}"
		assertThat(normalize(actual), is(normalize(expected)))		
	}

	/** test helper */
	private String findAtFolder(String folder, File tempFile, targetSubPath){						
		theInterceptor.basePath = folder		
		def found 
		
		proxy.use {
			def ff = new FindFile()
			found = ff.find(targetSubPath)
		}		
		
		found
	}

	@Before // each test runs
	void setUp(){
		createHierarchy()
		proxy = ProxyMetaClass.getInstance(FindFile.class)
		proxy.interceptor = theInterceptor
	}
	
	@After  // each test runs
	void destroy(){
		if(!deleteHierarchy(BASEPATH, hierarchy)){
			println "Could not delete [$BASEPATH]"
		}			
	} 
	
	/**
	 *  Allow override of getCurrentPath method 
	 * 
	 */
	private class MethodInterceptor implements groovy.lang.Interceptor{
		public basePath

		@Override
		public Object afterInvoke(Object object, String methodName,
				Object[] arguments, Object result) {
			
				if(methodName == "getCurrentPath"){
					result = basePath 
				}
				
				result;
		}
				
		@Override
		public Object beforeInvoke(Object object, String methodName,
				Object[] arguments) {
			
			return null;
		}
	

		@Override
		public boolean doInvoke() {
			return true;
		}
		
	}

	def createHierarchy(){
		def path = "$BASEPATH$hierarchy"		
		
		new File(path.toString()).mkdirs()
	}
	
	/**
	 * 
	 * Can this really be done well.
	 * 
	 * What if there are soft links, etc.
	 * 
	 * @see http://stackoverflow.com/questions/779519/delete-files-recursively-in-java
	 * @see http://commons.apache.org/io/api-release/org/apache/commons/io/FileUtils.html 
	 * 
	 * @param base
	 * @param dest
	 * @return
	 */
	boolean deleteHierarchy(String base, String dest){
		def result
		List list = dest.split("\"+File.separator)
		list = list - [""]
		def f = new File(base + File.separator + list[0])
		result =f.deleteDir()		
		result
	}
	
	String normalize(path){
		return new File(path).getCanonicalPath()
	}

	/** create a temp file at a directory */
	private File createTempFile(String folder) {
		File tempFile =File.createTempFile("xyz",".tmp", 
                         new File(folder))
		tempFile.deleteOnExit()
		return tempFile
	}
	
} // FindFileTest
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

How to use multiple views in Notepad++

Good editors always have some support for showing multiple editor windows. This is supported in many ways. See this for a comparison of the available document interfaces.

Multiple Views
NotePad++
I was happily surprised to find that Notepad++ also supports this. The trick is to right click on an edit window’s tab and choose “Move to other view” or “Clone to other view”.

Eclipse IDE
By the way, Eclipse IDE also supports multiple docking of edit views. You can even open two views into the same file. However, Notepad++ allows you to synchronize this. Which, afaik, Eclipse does not.

Multiple instances
While the above is great, sometimes you want two Notepad++ instances to, for example, open them each in their own display monitor. For that you just have to add to the notepad exe startup: -multiInst. For example on my Windows 7 instance my Notepad++ shortcut has:
“C:Program Files (x86)Notepad++notepad++.exe” -multiInst

References
Comparison of document interfaces
Managing two views in a single Notepad++ instance

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

What is Cloud Computing?

Someone from the non-technical business side asked me what is this Cloud computing all about. If you search for the term you find a bunch of definitions and descriptions. For example, on Wikipedia:

“Cloud computing refers to the delivery of computing and storage capacity as a service to a heterogeneous community of end-recipients.”
http://en.wikipedia.org/wiki/Cloud_computing.

That doesn’t sound like anything new. We had similar things even in the sixties. You have to read more of the above article to see the differences. But, to see what it really means a blog post, “Startups are Creating a New System of the World for IT“, puts it in context.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Groovy script to bootstrap a Gradle Project

I took Ted Naleid’s “Quick Shell Function to Bootstrap a Gradle Groovy Project” example code and converted it to a Groovy script.

Updates
1. Fixed. This was not running. I was using triple quoted string, when I should have used the triple single-quoted string for the HEREDOC like usage below.
2. Gradle now includes (since 1.6) a Build Init Plugin that will create a project. This should be used and not the code in this blog post.
In Gradle 1.9 this works:

    gradle init --type java-library
    

3. Gradle IDE plugins have the ability to create Gradle based project.
4. Would be nice to be able to reuse Maven style “archetypes”.


Deprecated
But, may serve as a Groovy code example.
Listing 1.

// NewGradle.groovy
// Author: Josef Betancourt
// Based on T. Naleid's shell script 

println "Creating files for new Gradle project ..."

new File(".gitignore").withPrintWriter{ w ->
     "*.un~,*.iml,*.ipr,*.iws,build,.gradle".split(",").each{ 
         w.println(it)
     }
}

new File("build.gradle") << '''
apply plugin: 'groovy'
apply plugin: 'idea'
apply plugin: 'eclipse'
 
repositories {
    mavenCentral()
}
 
dependencies {
    groovy 'org.codehaus.groovy:groovy:1.8.6'
    compile 'org.apache.ivy:ivy:2.2.0'
}
 
task createSourceDirs(description : 
   'Create empty source directories for all defined sourceSets') 
   << {
        sourceSets*.allSource.srcDirs.flatten().each { 
            File sourceDirectory ->        
            if (!sourceDirectory.exists()) {
                println "Making $sourceDirectory"
                sourceDirectory.mkdirs()
            }
        }
}
 
idea {
    project {
        jdkName = '1.6'
    }
}

''' // end content

"cmd /c gradle createSourceDirs".execute()

"cmd /c git init".execute()

Thread.start{
	sleep 5000 // allow time for all files to be created
	new File(".").eachFile{
		println it
	}
}

Not expert Groovy, but was easy to do. The bulk of it is the creation of a “here” doc using Groovy’s triple quote string. I didn’t duplicate the last line of Naleid’s script: “ls -a1 && find src # list all created assets”.

This script is not fully cross-platform. The invocation of shell commands at the end are in the Windows format. Left as an exercise to reader is the use of inline AntBuilder to reuse Ant’s exec task. 🙂

Updates
2012-03-09: Tweaked the source. Removed use of two temp variables.
2012-03-09: Added the Eclipse plugin. Now after creating the Gradle project executing eclipse will create the eclipse project: gradle eclipse
Or instead generate the Idea project: gradle idea.

Further Reading

  1. Groovy (Programming language)
  2. Groovy
  3. Gradle
  4. Quick Shell Function to Bootstrap a Gradle Groovy Project
  5. Strings and GString
  6. Groovy JDK extensions
  7. Executing External Processes
  8. Using Gradle to Bootstrap your Legacy Ant Builds

Off Topic

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.