tag:blogger.com,1999:blog-64947659340880147612024-03-14T03:08:51.331-04:00Entropy ReductionFinding order and meaning in code.Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6494765934088014761.post-65520660025535547122016-12-07T16:21:00.000-05:002016-12-07T16:25:30.391-05:00Heimdall, He Who Watches the Event Log<p>I have a tiny server, sitting in the cloud, running cygwin’s OpenSSH. Logging in requires an SSH key, but this doesn't stop people from trying all sorts of ways to get in.</p><p>Normally, this does nothing whatsoever, other than fill up my event logs with “invalid user” messages. However, I thought it might be nice to filter these users out at the firewall level. That’s what this program does: it monitors the event log for invalid SSH connection attempts, and adds the offending IP to the Windows Firewall list of blocked IP addresses.</p><p>Since my server is named Bifröst, I've named this program Heimdall. Heimdall is designed to be run from the command line, or as a scheduled task. While Heimdall is not a terribly complex program, I did learn a few things as I wrote it. This post is both to document what I found, and to serve as a reminder to me, should I ever need this information again.</p><p>The first thing Heimdall does is scan through the event log, looking for events matching a specific pattern. This is done using the <a href="https://msdn.microsoft.com/en-us/library/system.diagnostics.eventing.reader.eventlogreader.aspx">EventLogReader</a> and <a href="https://msdn.microsoft.com/en-us/library/system.diagnostics.eventing.reader.eventlogquery.aspx">EventLogQuery</a> classes. In my case, the relevant code followed this pseudo-code:</p><pre class="brush: csharp">public static IEnumerable<EventEntry> GetEvents(int entriesToScan)
{
const string queryString = "*[System[Provider[@Name='sshd'] and EventID=0]]";
var eventsQuery =
new EventLogQuery("Application", PathType.LogName, queryString)
{
ReverseDirection = true
};
// The "EventEntry" class is just a model for holding information about this
// a single event. Keep reading for further details.
var events = new List<EventEntry>();
entriesToScan = Math.Max(entriesToScan, 1);
try
{
using (var logReader = new EventLogReader(eventsQuery))
{
EventRecord eventInstance;
int currentEvent;
for (
eventInstance = logReader.ReadEvent(), currentEvent = 1;
eventInstance != null && currentEvent <= entriesToScan;
eventInstance = logReader.ReadEvent(), currentEvent += 1)
{
EventEntry entry;
try
{
entry = EventEntry.From(eventInstance);
}
finally
{
eventInstance.Dispose();
}
if (entry != null)
{
events.Add(entry);
}
}
eventInstance?.Dispose();
}
}
catch (EventLogNotFoundException e)
{
Console.Write("Failed to query the log!", e);
return null;
}
return events;
}</pre><p>I learned that the event log messages emitted from logReader.ReadEvent() implement <span class="keyword1">IDisposable</span> and should be disposed of.</p><p>I did not find any way to limit the number of items returned by the query, other than manually counting them. Since the every query looks like a standard xpath query, I tried experimenting with <code>position()</code>, but I could not make it work.</p><p>In my case, I needed information out of the <code>EventData</code> section of the event object. I could not find a way to access this information using any of the conveinance methods, but fortunately, the complete event information is available as XML. I was able to access the <code>EventData</code> by parsing the XML from the <code>EventRecord</code> object:</p><pre class="brush: csharp">public static string GetData(EventRecord eventInstance)
{
const string namespaceName =
"http://schemas.microsoft.com/win/2004/08/events/event";
var eventDataName = XName.Get("EventData", namespaceName);
var dataName = XName.Get("Data", namespaceName);
return XDocument.Parse(eventInstance.ToXml())
.Descendants(eventDataName).FirstOrDefault()?
.Descendants(dataName).FirstOrDefault()?
.Value;
}</pre><p>Once I had the event data, I was able to parse it using a regular expression, looking for a username and IP address. The username gets compared to a white-list of allowed usernames, and the IP address is checked to make sure it isn't coming from a private block. This is partially for my own protection: I figure that if I ever accidentally lock myself out, I can always try again from a private IP address.</p><p>If the attempted username is not on the white-list, and if the IP address is not private, then Heimdall adds the IP address to the list of addresses blocked by the Windows Firewall. Working with the Windows Firewall is done by way of the <a href="https://msdn.microsoft.com/en-us/library/windows/desktop/aa365309.aspx"><code>INetFwPolicy2</code></a> interface.</p><p>For the purposes of this program, I make no attempt to create new firewall rules. Instead, I modify an existing Firewall rule, which I manually created beforehand. A useful additional to Heimdall would be the ability to create its own rule, to reduce the amount of manual configuration necessary. However, as of right now, Heimdall assumes that this rule already exists:</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaLpQAKp8c08E0PGYr2vRLTVri3MpYs30yJQnLxMXWuz2_Sx0oR3BeJ8fzmqeyICdJ39xp_QPrsvnAZ2LsPf_68msHQHqJ-xZT8j9sJYNQcKonmA6622jiLiWv1kBjKVeZOkjdfIFslMRm/s1600/BlockSpecificIPs.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaLpQAKp8c08E0PGYr2vRLTVri3MpYs30yJQnLxMXWuz2_Sx0oR3BeJ8fzmqeyICdJ39xp_QPrsvnAZ2LsPf_68msHQHqJ-xZT8j9sJYNQcKonmA6622jiLiWv1kBjKVeZOkjdfIFslMRm/s320/BlockSpecificIPs.png" width="243" /></a></div><p>This is a simple blocking rule, which Heimdall is able to access by name:</p><pre class="brush: csharp">private static INetFwRule GetBlockingRule() =>
((INetFwPolicy2)
Activator.CreateInstance(Type.GetTypeFromProgID("HNetCfg.FwPolicy2")))
.Rules
.OfType<INetFwRule>()
.FirstOrDefault(r => r.Name == "Block Specific IPs");
</pre><p>Once we have a reference to the firewall rule, we just need to add the target IP address to the list of remote addresses affected by this rule.</p><p>I took some care to handle ranges of IP addresses; that is, if two or more adjacent IP addresses are blocked, they are added to the firewall as a range, instead of individual entries. I found the <a href="https://github.com/jsakamoto/ipaddressrange">IPAddressRange</a> project to be very useful in assisting with this.</p><pre class="brush: csharp">public static void BlockIp(IPAddress ip)
{
var rule = GetBlockingRule();
var addresses = rule.RemoteAddresses
.Split(',')
.Where(s => string.IsNullOrWhiteSpace(s) == false)
.Select(IPAddressRange.Parse)
.ToList();
addresses.Add(new IPAddressRange(ip));
// Details of ConsolidateRanges are not relevant to this post; check the
// source on BitBucket if you are curious.
addresses = ConsolidateRanges(addresses);
rule.RemoteAddresses = string.Join(",", addresses.Select(r => r.ToString()));
}</pre><p>Finally, Heimdall sends me an email whenever a new IP address is blocked. I've had this program running for about a week now, and I've enjoyed seeing some of the creative usernames that people try to log in with. Over the past week alone, there have been 35 separate IP addresses blocked, which have attempted 205 unique usernames.</p><p>If you are curious enough to have read this far, you may be interested in seeing the <a href="https://bitbucket.org/ChrisNielsen/heimdall">source code for Heimdall</a>!</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-17541594789126448162013-10-23T19:00:00.000-04:002013-10-23T19:00:57.364-04:00Visual Studio as a Diffing Tool<p>I have recently learned how to make use of Visual Studio 2012's built-in diffing tool. I'm happy to report that it does a reasonably decent job at this. While diffing, you have access to Visual Studio's superior syntax highlighting and intellisense capabilities. Also, it reuses existing windows, which can be handy if your target file is already open in your IDE. I have always used external diffing tools in the past, but there is a certain appeal to having an integrated tool. Just being able to diff and edit in a consistent color scheme is nice.</p>
<p>Sadly, Visual Studio does <strong>not</strong> support three-way merging or directory comparison, so I won't be putting KDiff3 down just yet. Also, unless you have set up a Team Foundation source control server, this capability is rather obscure and difficult to invoke. It involves some command line incantations:</p>
<pre><code>devenv.exe /Diff Source Target [SourceName] [TargetName]</code></pre>
<p>That isn't too bad, as command line arguments go. Still, I do not want to specify the complete path for every source and target file that I want to compare. Fortunately, it is quite possible to set up Visual Studio as a merge tool option for TortoiseHg. To do so, edit your global mercurial.ini file, and add this to your [merge-tools] section (go ahead and create that section if it does not exist):</p>
<pre><code style="white-space: nowrap;">[merge-tools]<br />
vs.executable = ${ProgramFiles(x86)}/Microsoft Visual Studio 11.0/Common7/IDE/devenv.exe<br />
vs.gui = True<br />
vs.diffargs = /diff $parent $child "$plabel1" "$clabel"<br />
vs.priority = 1
</code></pre>
<p>Now go up to your [tortoisehg] section. Create or edit your vdiff setting to point to your newly defined merge tool. It should look like this (along with whatever other items you have in that section):</p>
<pre><code>[tortoisehg]
vdiff = vs</code></pre>
<p>Restart TortoiseHg. Now, when you ask TortoiseHg to diff a single file for you, it should open that file in Visual Studio. If you ask for a three-way merge or a directory diff, TortoiseHg is smart enough to know that Visual Studio can't handle it, and will pick a different tool.</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-4738059950155859802011-10-11T22:50:00.000-04:002016-12-07T16:17:54.988-05:00Introducing MinCat for MSBuild / Visual Studio<p>I am happy to release a new project today. Introducing <a href="https://bitbucket.org/ChrisNielsen/mincat">MinCat</a>: the JavaScript and CSS minimizer and concatenation utility for MSBuild and (optionally) Microsoft MVC.</p><h3>The Problem</h3><p>JavaScript presents an interesting problem to many web developers. As a client-side scripting language, it is very forgiving about how it is used, and how it is included in the context of a larger web document. There is a sloppy way to serve JavaScript, and a professional way to serve JavaScript.</p><p>The "sloppy" method covers many possibilities: inline amongst the HTML, buried inside the href of an anchor, or heaped into the <code><head></code> in a stack of script-tags that comes up to your eyeballs. All of these methods work, but they also have issues.</p><p>The current best practice recommends a different approach. Instead of including HTML inline, we should serve it as external files. Moreover, these files should be minimized to reduce the page load time. If multiple files are necessary, we should concatenate them to reduce the number of HTTP requests required to load them.</p><p>However beneficial this is to the end-user, the act of minimizing and concatenating script files adds an additional burden to the developer. Fortunately, it is quite possible to automate this process, and numerous tools exist to facilitate this. MinCat is such a tool.</p><h3>The Solution</h3><p>MinCat exists to address exactly the problem described above. It is a small, simple tool that lets you control the <b>min</b>imization and con<b>cat</b>enation of your JavaScript files. It is designed to integrate directly with MSBuild. Because Visual Studio uses MSBuild under the hood, this means it provides easy integration with your existing Visual Studio web projects.</p><p>It's usage is simple and straightforward. By adding <Minimize> or <Concatenate> commands to your project file, you can control how your JavaScript is prepared for your source files. For instance, this command would minimize all of the JavaScript files in your "Scripts" folder, placing the resulting files in "Scripts\min": <p><pre class="brush: xml"><Minimize Input="Scripts\*.js" Outpath="Scripts\min\" /></pre></p><p>For MVC projects, MinCat also provides an MVC Script helper extension. At a basic level, this extension will facilitate the switch between the minimized or development version of a particular file. However, it really begins to shine when combined with the new "directives" that MinCat offers (more on those later!)</p><p><pre class="csharp">@Html.Script(Url.Content("~/Scripts/MyScript.js"))</pre></p><p>Since minimizing JavaScript is not always a quick operation, MinCat will only re-minimize files if they have changed since the last time they were minimized. It accomplishes this by comparing the last modified date of the source files with the corresponding date on the minimized files. This helps keep the overall build time down to a minimum.</p><p>MinCat comes bundled with the excellent <a href="http://developer.yahoo.com/yui/compressor/">YUICompressor</a>. However, it is designed so that the compressor is a modular component, and it could easily be reworked to use a different compression engine.</p><h3>New JavaScript Directives</h3><p>As if all that weren't enough, MinCat additionally provides support for a number of directives, designed to be placed in the actual source of individual JavaScript files. These provide further control over how each file is treated by the minimization process. Because these directives are fully supported by the (optional) MinCat MVC Script helper extension, they provide some exciting new ways to organize and structure your JavaScript.</p><dl><dt>/* @skip minimize */</dt>
<dd>This directive will cause the source file to never be minimized, even if it is otherwise included by a wildcard in the input path. This has no effect when used with the MVC helper extension.</dd>
<dt>/* @require "filename.js" */</dt>
<dd>This directive instructs the minimizer that the current file depends on code from another file. When this file is minimized, all required external files will be collected (recursively, so a required file can also require a file), sorted into the correct order, reduced to a distinct list, and concatenated in front of the file that specifies them. Therefore, the resulting minimized file will contain everything it needs to function. When used with the MVC Script helper extension, each required file will be loaded in its own <code><script /></code> tag, in the correct order, before the <code><script /></code> tag that contains your target file.</dd>
<dt>/* @include "filename.js" */</dt>
<dd>This directives causes the minimizer to include the complete contents of the specified file directly inline, wherever that directive is found. When used with the MVC Script helper extension, the loaded <code><script /></code> file will also include the desired content directly inline.</dd> </dl><p>Note the differences between <code>@require</code> and <code>@include</code>. The <code>@include</code> directive is primarily exciting because it allows you to create assembly-like structures:</p><br />
<pre class="brush: js">var Global = (function () {
"use strict";
var internal = {};
function Global() {
var instance = {};
/* @include "Access to Internal, Instance, and Global Variables.js" */
}
/* @include "Access to Internal and Global Variables.js" */
/* @require "Access to Global Variables Only.js" */
return Global;
}());</pre><h3>Learn More!</h3><p>MinCat is open source software, released under a BSD License. It is <a href="https://bitbucket.org/ChrisNielsen/mincat">available on BitBucket</a>, and as a NuGet package.</p><p>Complete documentation is available on its <a href="https://bitbucket.org/ChrisNielsen/mincat/wiki/Home">wiki page</a>.</p><p>As always, I am excited to learn how people are using my tools. If you try this out, please feel free to drop me a note with your impressions. And of course, always let me know if you <a href="https://bitbucket.org/ChrisNielsen/mincat/issues?status=new&status=open">find a bug</a>!</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-60005028250400418562011-07-20T10:27:00.000-04:002011-07-20T10:27:38.553-04:00JSLint, Licensing, and JSON Visualization<p>The <a href="https://github.com/douglascrockford/JSLint/blob/1ebebf3313cfeede287120a79fd652df0d70af35/jslint.js">JSLint license</a> specifies that it should be used for Good, not Evil.</p>
<p>Suppose I construct some program that I believe to be Good, and use JSLint to improve the quality of that program. Further suppose that I release my code under a permissive license, such as a <a href="http://en.wikipedia.org/wiki/BSD_licenses">BSD license</a>. Now suppose that somebody else takes my program and uses it for Evil.</p>
<p>In this case, the evil-doer has not actually violated their license agreement with me, since BSD licenses permit Evil. However, the evil-doer has now profited from the increased code quality gained from using JSLint.</p>
<p>Is the evil-doer now in violation of the JSLint license, despite never actually using JSLint themselves? Alternatively, perhaps I am now in violation of the JSLint license? Does the JSLint license require me to use the "Good" clause in my license as well, to prevent this scenario?</p>
<p>These are the questions that trouble me this morning. By the way, I've released the <a href="http://chris.photobooks.com/json/default.js">source</a> to my <a href="http://chris.photobooks.com/json/">JSON visualizer</a> under a BSD license.Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com1tag:blogger.com,1999:blog-6494765934088014761.post-10756205258389936702010-12-29T09:59:00.001-05:002010-12-29T10:03:40.482-05:00Notes on GetSchemaTable<p>I recent found myself using the <a href="http://msdn.microsoft.com/en-us/library/system.data.sqlclient.sqldatareader.getschematable.aspx">SqlDataReader.GetSchemaTable</a> method. I made some notes detailing what it will return for various data types in SQL Server 2005.</p>
<table border="1" cellspacing="0" cellpadding="2">
<caption>Notes on GetSchemaTable</caption>
<thead>
<tr><td colspan="3"> </td><th colspan="2">Numeric</th><td> </td></tr>
<tr><th>ColumnName</th><th>DataType</th><th>ColumnSize</th><th>Precision</th><th>Scale</th><th>Notes</th></tr>
</thead>
<tbody>
<tr><td>bigint</td><td>Int64</td><td align="right">8</td><td align="right">19</td><td align="right">255</td><td> </td></tr>
<tr><td>bit</td><td>Boolean</td><td align="right">1</td><td align="right">255</td><td align="right">255</td><td> </td></tr>
<tr><td>decimal</td><td>Decimal</td><td align="right">17</td><td align="right">18</td><td align="right">0</td><td> </td></tr>
<tr><td>int</td><td>Int32</td><td align="right">4</td><td align="right">10</td><td align="right">255</td><td> </td></tr>
<tr><td>money</td><td>Decimal</td><td align="right">8</td><td align="right">19</td><td align="right">255</td><td> </td></tr>
<tr><td>numeric</td><td>Decimal</td><td align="right">17</td><td align="right">18</td><td align="right">0</td><td> </td></tr>
<tr><td>smallint</td><td>Int16</td><td align="right">2</td><td align="right">5</td><td align="right">255</td><td> </td></tr>
<tr><td>smallmoney</td><td>Decimal</td><td align="right">4</td><td align="right">10</td><td align="right">255</td><td> </td></tr>
<tr><td>tinyint</td><td>Byte</td><td align="right">1</td><td align="right">3</td><td align="right">255</td><td> </td></tr>
<tr><td>float</td><td>Double</td><td align="right">8</td><td align="right">15</td><td align="right">255</td><td> </td></tr>
<tr><td>real</td><td>Single</td><td align="right">4</td><td align="right">7</td><td align="right">255</td><td> </td></tr>
<tr><td>datetime</td><td>DateTime</td><td align="right">8</td><td align="right">23</td><td align="right">3</td><td> </td></tr>
<tr><td>smalldatetime</td><td>DateTime</td><td align="right">4</td><td align="right">16</td><td align="right">0</td><td> </td></tr>
<tr><td>char</td><td>String</td><td align="right">20</td><td align="right">255</td><td align="right">255</td><td> </td></tr>
<tr><td>varchar</td><td>String</td><td align="right">20</td><td align="right">255</td><td align="right">255</td><td> </td></tr>
<tr><td>text</td><td>String</td><td align="right">2147483647</td><td align="right">255</td><td align="right">255</td><td>isLong</td></tr>
<tr><td>nchar</td><td>String</td><td align="right">20</td><td align="right">255</td><td align="right">255</td><td> </td></tr>
<tr><td>nvarchar</td><td>String</td><td align="right">20</td><td align="right">255</td><td align="right">255</td><td> </td></tr>
<tr><td>varchar(max)</td><td>String</td><td align="right">2147483647</td><td align="right">255</td><td align="right">255</td><td>isLong</td></tr>
<tr><td>nvarchar(max)</td><td>String</td><td align="right">2147483647</td><td align="right">255</td><td align="right">255</td><td>isLong</td></tr>
<tr><td>ntext</td><td>String</td><td align="right">1073741823</td><td align="right">255</td><td align="right">255</td><td>isLong</td></tr>
<tr><td>timestamp</td><td>Byte[]</td><td align="right">8</td><td align="right">255</td><td align="right">255</td><td>IsRowVersion</td></tr>
<tr><td>xml</td><td>String</td><td align="right">2147483647</td><td align="right">255</td><td align="right">255</td><td>isLong</td></tr>
</tbody>
</table>
<p>I created these notes through the simple method of creating a table with every possible data type. Or rather, every data type that I am interested in, which is very nearly the same thing--I mean, who uses varbinary, really? I then used the GetSchemaTable method on my new table, and inspected the results.</p>
<p>There is a <a href="http://msdn.microsoft.com/en-us/library/ms131092(v=SQL.90).aspx">page on MSDN</a> that appears to contain this information, but upon closer inspection, it must be talking about something else entirely. For instance, it claims that the SQL Server data type "varchar" has no mapping whatsoever, not even as a System.String.</p>
<p>Certainly, this makes sense upon further reflection: it's possible to put any varchar value into a string, but not the other way around. Still, it's not terribly useful if you just want to know what sort of data type you can reasonably expect to get out of a given column.</p>
<p>I further note that the MSDN documentation states that the NumericPrecision column should be null for non-numeric data types, but this is simply not true.</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-65901583764706540972010-07-10T13:09:00.001-04:002016-12-07T16:13:12.302-05:00Conditional Operators and Bracket Notation<p>Did you know it is valid JavaScript to use conditional operators inside bracket notation to access object properties? For whatever reason, I have only just now realized this.</p><p>In other words, this is a perfectly valid fragment:</p><pre class="brush: js">var obj = {
valid: [],
invalid: []
};
items.forEach(function (item) {
obj[item.isValid() ? "valid" : "invalid"].push(item);
});</pre><p>The conditional operator, which takes the form <code>condition ? ifTrue : ifFalse</code>, is a shorthand version of an if statement. In this case, it results in the name of the object property that I wish to access.</p><p>I am yet undecided on whether this is more or less readable than the verbose version:</p><pre class="brush: js">items.forEach(function (item) {
if (item.isValid()) {
obj.valid.push(item);
} else {
obj.invalid.push(item);
}
});</pre><p>Perhaps I will look back on this post in a few months and marvel at how obvious it all seems in hindsight. In the meantime, it is nice that I am still learning new things about JavaScript.</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-31520554770851042832010-02-12T20:34:00.002-05:002016-12-07T16:11:25.843-05:00Wacky Code<p>This has got to be the most wacky code I have written all week:</p><pre class="brush: js">range1.setEndPoint('StartToStart', range2);
range1.setEndPoint('StartToStart', range2);</pre><p>Yes, the same line is there twice, and yes, it is supposed to be like that. The ranges in question are IE-only <a href="http://msdn.microsoft.com/en-us/library/ms535872%28VS.85%29.aspx">TextRange</a> objects, which I am using to manage the position of the cursor within a rich text editor. The line has to be repeated because the first execution doesn't quite work, but the second one does:</p><pre class="brush: xml"><p>widget{cursor}</p> <-- position after first line -->
<p>{cursor}gadget</p> <-- requested position,
                          position after second setting --></pre><p>Wacky. Sadly, this is just one of many TextRange eccentricities that I've run into.</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-25995830011873175232010-02-09T16:42:00.001-05:002016-12-07T16:02:40.526-05:00Spell Checking in HTML<p>I recently completed a spell checking module as part of a larger project for an HTML-based editor. Some of the challenges of the project were interesting; here are my experiences, the problems I encountered, and how I solved them.</p><p>The first step of spell checking a block of text is determining what the text actually is. For a simple text document, this is quite easy: it's no more than a string of characters. However, for an HTML document, it is not so simple. Markup introduces a lot of extra items to deal with: we want to check the text as it would appear to a human, not to a computer.</p><p>In other words, it is one thing to detect the word "html" in a string of words: "blah blah blah, html, blah blah blah," but quite another thing to detect the same word as it would appear to a human if embedded in a complex DOM structure: <code><p><b>h</b><i>t</i><em>m</em><strong>l</strong></p></code>.</p><p>One obvious way of solving this problem is to derive the textual value of a given parent element. This is quite easy: innerText works in IE, and textContent works in Mozilla. Thus, a human version of the text of a DOM element can be obtained thusly:</p><pre class="brush: js">var parent = document.body;
var text = parent.textContent; // for Mozilla
if (text === undefined) {
text = parent.innerText; // for IE
}</pre><p>However, this leaves a more significant problem to deal with: once we determine which words are misspelled, how will we re-associate those words with the correct DOM structures? If "html" comes back as being incorrect, we will need to know which text nodes originally produced the word, for how else will we correct it? I have a suspicion that this could be solved with a clever application of TextRange objects in IE and Range objects in Mozilla, but that isn't the route I took (working with IE's TextRange is a headache all by itself anyway).</p><p>My basic strategy is to walk through the DOM and derive two simultaneous structures that represent each text node: one version contains the text as it would appear to a user, and the other version contains a map between the "human" version and the original DOM.</p><p>Rendering the HTML as text is not exactly straightforward either; one cannot simply concatenate the values of each individual text node. There are a number of HTML elements which introduce white space for humans, such as <code><p></code> or <code><div></code> or even some inline ones, like <code><br></code>. Similarly, there are some HTML elements which do not introduce white space, such as <code><b></code>, or <code><i></code>, or <code><em></code>. Other rules apply as well: if you have <code><b style="display: block;"></code> then you have a <code><b></code> that adds white space even when <code><b></code> normally wouldn't.</p><p>To resolve this, I spent some time empirically testing each suspicious HTML element to determine whether it would cause visible white space to be inserted inside a word. Using this list and a variety of other rules (floating nodes always make white space, display: block nodes always make white space, etc), I construct a text string out of the DOM that more-or-less resembles the words as a human would see them. Notably, it is not necessary to obtain an exact representation of white space; I don't particularly need to render tables as tables, I just need to know that a <code></td><td></code> causes a break in a word but a <code></span><span></code> doesn't.</p><p>As I construct this string, I keep track of each text node that I encounter in the DOM, and meticulously record the starting and ending indices of that node's textual content in my generated string.</p><p>As an example, consider the following DOM fragment, with text nodes shown explicitly:</p><pre class="brush: html"><p>
<b>
<textNode 1>h</textNode 1>
</b>
<i>
<textNode 2>t</textNode 2>
</i>
<em>
<textNode 3>m</textNode 3>
</em>
<strong>
<textNode 4>l</textNode 4>
</strong>
<textNode 5> is complex</textNode 5>
</p></pre><p>After parsing the above, I would end up with a structure similar to this:</p><pre class="brush: js">result = {
html: [
{ node: <textNode 1>, start: 0, end: 1 },
{ node: <textNode 2>, start: 1, end: 2 },
{ node: <textNode 3>, start: 2, end: 3 },
{ node: <textNode 4>, start: 3, end: 4 },
{ node: <textNode 5>, start: 4, end: 15 }
],
text: 'html is complex'
}</pre><p>Once this process is complete, I split the <code>result.text</code> value into a list of unique individual words. Locating each word is easily accomplished through regular expressions, although special provisions must be made for hyphenated words and contractions. Unicode "smart quote" characters and their brethren are also normalized into regular ASCII quotes. This list is finally sent up to the server, where all the real work happens.</p><p>Given any list of words, there are several methods to perform spell checking upon it. For my purposes, I've implemented a dictionary-based approach, as this gives me a greater sense of confidence and considerably more control than statistical analysis. Locating misspelled words is therefore a trivial matter of determining whether each provided word is in the dictionary or not.</p><p>However, it is not enough to know which words are incorrect: I must also offer spelling suggestions. I accomplished this through implementing the Damerau-Levenshtein Distance algorithm, which has been more fun than I have had in code in quite some time. While an in-depth explanation can be found on Wikipedia, put simply, the algorithm can compare any two words and generate a numeric score that indicates how similar those two words are.</p><p>Armed with this capability, I am able to generate spelling suggestions by calculating the <a href="http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">Damerau-Levenshtein Distance</a> between each misspelled word, and each word in the dictionary. The algorithm is quite speedy, but as the dictionary is quite large, some optimizations are in order: for instance, only words of a comparable length to the original word are tested.</p><p>While I am given to understand that a relational database is not ideal for this, I have implemented this algorithm as a C# assembly on SQL Server 2005. Although I feel that additional optimizations are no doubt possible, I am already able to process comparatively large documents in under a second using this method.</p><p>As a result of all this, the server sends back a list of misspelled words. The JavaScript code takes these words and locates each one within the <code>result.text</code> string that it previously constructed. For each word's matching indices in result.text, it scans through the list of nodes in result.html until it finds the text node or nodes that made up that word.</p><p>Finally! The code now knows which words are misspelled AND which nodes correspond to those words. From here, it is a relatively simple matter of presenting this information to the user and letting them decide how to handle it. For the time being, I've chosen to provide a dialog box, similar to how MS Word's spellchecker operates. This gives the user familiar buttons for things like "Ignore, Ignore All, Add to Dictionary, etc." I am rather tempted to go back and implement a Google-style interface, wherein the incorrect words are highlighted and the user is given a context menu instead. However, there are many more features left to complete, and I have to move on at some point.</p><p>As soon as the user decides on a new spelling for a word, I alter each text node that composed the original word, updating it to contain the new values instead. Should a word be split across multiple text nodes, I fill in the letters one at a time, from left to right, letting the final node be the one to expand or contract if there is a difference in the number of letters.</p><p>And that's all there is to it!</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-32471142245927309042009-12-31T20:45:00.005-05:002016-12-07T15:55:41.965-05:00XPath Axis Selectors Implemented in JavaScript<p>Here is a quick implementation of the XPath axis selectors in JavaScript. Each function accepts a context node as a parameter, a filtering function, and a stop function. The two function arguments are optional and may be omitted.</p><p>If the filter function is present, it will be executed for each node encountered along the requested axis. It must return true for the node to be included in the output.</p><p>If the stop function is present, it will also be executed for each node encountered. When and if it returns true, the search along the axis will stop, and whatever nodes have been accumulated up to (and including) that point will be returned.</p><p><a href="http://chris.photobooks.com/Other/blog/axis.js">Here it is for download</a>. <a href="http://chris.photobooks.com/Other/blog/axis-min.js">Here is a minified version</a>, only 2k!</p><p>This would be used like so:</p><pre class="brush: js">var node = document.getElementById('myTable'), results;
// Find all descendant nodes
results = AXIS.descendant(node);
// Find all descendant text nodes
results = AXIS.descendant(node, function (n) {
return (n.nodeType === 3);
});
// Find the closest FORM ancestor:
function isForm(n) {
return (n.nodeName.toLowerCase() === 'form');
}
results = AXIS.ancestor(node, isForm, isForm)[0];
// Locate all H1 items between this node and the next table:
results = AXIS.following(node, function (n) {
return (n.nodeName.toLowerCase() === 'h1');
}, function (n) {
return (n.nodeName.toLowerCase() === 'table');
});</pre><br />
<p>These are specifically written to operate on nodes, not elements. In other words, text nodes will be included as potential return values. This is great for me, as my first use for these is to assist in determining what text the user has selected. If the inclusion of text nodes were not a requirement, then one might consider optimizing the "descendant" axis to use querySelectorAll('*') instead--at least, in modern browsers.</p><p>This should work in all browsers. I did run into one snag with IE6. Apparently, if you have a <code><base></code> tag in the source, then the resulting tree structure ends up looking something like this:</p><pre class="brush: xml"><html>
<head>
<base>
<body>...</body> <-- Same body element!
</base>
</head>
<body>...</body> <-- Same body element!
</html></pre><br />
<p>That <code><body></code> tag there is not a duplicate; it's really the same element, just included in two places in the DOM. It is both a descendant and a sibling of the <code><head></code> element. This causes an infinite loop when crawling the "following" axis, as the code crawls out of the <code><body></code> into the <code><base></code>, then into the <code><head></code>, then enters the <code><body></code> again.</p><p>Conditional compilation is used to fix this specifically for IE6, so the performance of other browsers should not be affected.</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-57354471683062900482009-12-07T21:41:00.005-05:002016-12-07T15:49:30.761-05:00Flattening recursive XML data in SQL Server 2005<p>I recently had to flatten an XML data set that looked something like this:</p><br />
<pre class="brush: xml"><topic id="1" name="planets">
<topicList>
<topic id="2" name="jupiter">
<topicList>
<topic id="3" name="ganymede" />
<topic id="18" name="callisto" />
<topic id="92" name="io">
<topicList>
<topic id="21" name="europa" />
</topicList>
</topic>
</topicList>
</topic>
<topic id="7" name="saturn">
<topicList>
<topic id="11" name="titan" />
</topicList>
</topic>
</topicList>
</topic></pre><br />
<p>I needed to produce a result set that preserved the parent/child relationship between each topic. In other words, I needed to know that Callisto belonged to Jupiter when I finished. At first, I thought this was clearly a job for recursion. I envisioned leaping deftly from each topic to each of its children in turn. Indeed, with SQL Server 2005 and common table expressions, this is quite possible:</p><br />
<pre class="brush: sql">Declare @xml XML;
Set @xml = '.... (see above) ....';
With topics (id, parent, name, children)
As (
Select
@xml.value('/topic[1]/@id', 'integer') As id,
Cast(null As integer) As parent,
@xml.value('/topic[1]/@name', 'varchar(50)') As name,
@xml.query('/topic/topicList') As children
Union All
Select
child.node.value('@id', 'integer') As id,
topics.id As parent,
child.node.value('@name', 'varchar(50)') As name,
child.node.query('topicList') As children
From topics
Cross Apply topics.children.nodes('/topicList/topic') As child(node))
Select id, parent, name
From topics;</pre><br />
<p>As with all recursive <abbr title="Common Table Expressions">CTEs</abbr>, this one is broken into two parts. The rows returned by the first half are used as starting points for the recursion in the second half. In this case, the first half returns only a single row:</p><br />
<pre class="brush: sql">Select
@xml.value('/topic[1]/@id', 'integer') As id,
Cast(null As integer) As parent,
@xml.value('/topic[1]/@name', 'varchar(50)') As name,
@xml.query('/topic/topicList') As children</pre><br />
<table><caption>Result:</caption><thead><tr><th>id</th><th>parent</th><th>name</th><th>children</th></tr>
</thead><tbody><tr><td>1</td><td><i>NULL</i></td><td>planets</td><td><i>{xml}</i></td></tr></tbody></table><br />
<p>The second half handles the recursion part. The secret here is in the final column. Each topic row includes a reference to its own children. The recursive portion of the CTE works on each of these children, one by one. Each child further includes a reference to its own children, and so the cycle continues. Thus, each recursion builds on the rows produced by the previous recursion.</p><br />
<table><caption>Results:</caption><thead>
<tr><th>cycle</th><th>id</th><th>parent</th><th>name</th></tr>
</thead><tbody>
<tr><td>1</td><td>1</td><td><i>NULL</i></td><td>planets</td></tr>
<tr><td>2</td><td>2</td><td>1</td><td>jupiter</td></tr>
<tr><td>2</td><td>7</td><td>1</td><td>saturn</td></tr>
<tr><td>3</td><td>18</td><td>2</td><td>callisto</td></tr>
<tr><td>3</td><td>3</td><td>2</td><td>ganymede</td></tr>
<tr><td>3</td><td>92</td><td>2</td><td>io</td></tr>
<tr><td>3</td><td>11</td><td>7</td><td>titan</td></tr>
<tr><td>4</td><td>21</td><td>92</td><td>europa</td></tr>
</tbody></table><br />
<p>As interesting as this is, it is not terribly performant. But fear not: a better solution exists! Recall that each XML node contains information concerning its position within its document; it has references to its children, siblings, and parent nodes. Rather than trying to recursively walk the XML tree, then, it is possible to simply get a list of all "topic" nodes and derive the parent information from the node itself. This results in a much simpler query:</p><br />
<pre class="brush: sql">Select
topics.topic.value('@id', 'integer') As id,
topics.topic.value('../../@id', 'integer') As parent,
topics.topic.value('@name', 'varchar(50)') As name
From @xml.nodes('//topic') As topics(topic)</pre><br />
<p>Yup, that's all. The <code>@xml.nodes('//topic')</code> finds every <code><topic/></code> node, no matter how deeply nested it is. Then the parent id is found simply by looking at each topic's ancestors: <code>topics.topic.value('../../@id', 'integer')</code>.</p><p>Quick, easy, and simple!</p>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0tag:blogger.com,1999:blog-6494765934088014761.post-62027943311103574132009-08-12T10:10:00.003-04:002009-08-12T10:20:33.571-04:00XML VisualizationI've created a new tool to assist with developing in XML. This is capable of taking an arbitrary XML document, and performing a variety of tasks on it.<br /><br />At the moment, it can beautify, or pretty-print, a file, apply an arbitrary xPath and show the results, and apply an arbitrary XSL transformation.<br /><br />All processing is done by the browser (there is no server-side component to this at all). Because of this, results will vary slightly by browser, since each browser flavor has idiosyncrasies involving their respective XML / XSL engines.<br /><br />It works in IE6+, Firefox, Opera, Safari, and Chrome. It was quite fun to make, and I'd love to hear suggestions for future improvements!<br /><br />The tool itself can be found here: <a href="http://chris.photobooks.com/xml/default.htm">http://chris.photobooks.com/xml/default.htm</a>Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com1tag:blogger.com,1999:blog-6494765934088014761.post-57209134439155501002009-06-10T15:13:00.008-04:002016-12-07T15:39:40.281-05:00SQL Server Subquery QuirkHere's an interesting quirk of SQL Server 2005 that bit me today.<br />
<br />
Consider this fictional query:<br />
<br />
<pre class="brush: sql">Select pageID, givenName
From phy.Contacts
Where pageID In (
Select pageID
From (
Select id
From oth.Pages
Where [Hidden] = 0) As [subquery])</pre><br />
Here there are two levels of subqueries here. The innermost level returns a set of <code>[id]</code> values. The next level up is asking the innermost level for a set of <code>[pageID]</code> values. Alas, the innermost query does not contain a <code>[pageID]</code> column.<br />
<br />
However, this query executes anyway, without any errors, and appears to return decent results. This surprised me: the middle-level query is looking for a column that doesn't exist. I would have expected an error message in this case, not a result set.<br />
<br />
This behavior is explained in a tiny "Caution" box in <a href="http://msdn.microsoft.com/en-us/library/ms178050.aspx">MSDN</a>:<br />
<br />
<blockquote class="tr_bq">If a column is referenced in a subquery that does not exist in the table referenced by the subquery's FROM clause, but exists in a table referenced by the outer query's FROM clause, the query executes without error. SQL Server implicitly qualifies the column in the subquery with the table name in the outer query.</blockquote><br />
So apparently, the middle-level query is pulling the pageID column from the OUTER query instead. Fascinating.Anonymoushttp://www.blogger.com/profile/16784290449277155558noreply@blogger.com0