Use of CSS constants in script.

In Sciter you can define CSS constants using @const declarations like this:

<style>
  @const TEST_STR:"test";
  @const TEST_COLOR: rgb(128,0,0);
  @const TEST_NUMBER: 128;
</style>

and use them not only in CSS ( as @TEST_COLOR for example ) but also in script using accessor like this:

var test_str = self.style.constant("TEST_STR");

If you think that self.style.constant is too narrative then you can define short “stringizer” function for it:

  function $const( name ) { return self.style.constant(name) || ""; }

and later use it as:

var t1 = $const(TEST_STR); // "test" string
var t2 = $const(TEST_COLOR); // object of type Color, color(128,0,0)
var t3 = $const(TEST_NUMBER); // integer, 128

What does “::” construction mean in TIScript?

Got this question in one of emails…

One of forms to declare anonymous function in TIScript is so called single statement lambda function:

':' [param-list] ':' <statement>;

Let’s say we have this JavaScript code:

var counter = 0;
var inc = function() { counter++; }

So each time when you call inc() the counter will be incremented.

By using TIScript’s lightweight syntax we can do exactly the same by declaring:

var counter = 0;
var inc = :: counter++; 

So first “:” here is exactly “function(” and second “:” is “)” in JS declaration.

You of course can use standard JS way of declaring functions in TIScript too, I just think that sometimes shorter forms are better. Like here:

var accounts = [...]; // list of accounts
accounts.sort( :a,b: a.balance - b.balance );

Instead of quite noisy:

accounts.sort( function(a,b){ return a.balance - b.balance });

Ruby has similar lightweight approach of declaring similar entity:

[1,2,3,4,5].each {|i| print "#{i} "}

That in JS will be

[1,2,3,4,5].each(function(i){ println("#",i);});

Comments in source code considered harmful

In the file ResourceFontFileLoader.h (offical Windows SDK samples) you can see variable declared as:

static IDWriteFontFileLoader* instance_;

As you see it is a raw pointer here.

And in the file ResourceFontFileLoader.cpp it is initialized with this:

// Smart pointer to singleton instance of the font file loader.
IDWriteFontFileLoader* ResourceFontFileLoader::instance_(
    new(std::nothrow) ResourceFontFileLoader()
    );

Note the comment. “Smart pointer” there is just a good wish. I believe someone reviewed that code and according to the comment all this passed code review. But the code leaks memory. So that comment does quite opposite to what it supposed to do actually – it is not helpful but rather harmful.

Question on interview: diameter of binary tree.

I got a task on interview to calculate diameter of given binary tree.
While I don’t like to solve abstract problems ( I have a lot of problems to solve in my projects already) I’ve found this one particularly interesting as it actually has practical value in one of algorithms on DOM tree (that is non-binary tree but still). So I’ve decided to investigate it.

Let’s define the problem this way:
The diameter (or width) of binary tree is the number of tree edges on the longest path between two leaves in the tree.
The task is to write function that returns the width for any given binary tree.

Nodes in a tree are defined as {left:nodeOrNull,right:nodeOrNull} (I am using JavaScript here for brevity).
The function looks like this:
function treeWidth(treeRootNode) {} // returns max distance found in the tree.

So for the tree:

      a
     / \
    b   c
       / \
      d   e
           \
            f

the function shall return 4 as longest path is b-a-c-e-f

I shall admit that I’ve spent something around one hour to find the solution. Good this timing or bad – I don’t know, programming is not a sport really. I did it at the end and that’s enough. The algorithm has computational complexity of O(N) as each node of the tree is visited exactly once. Memory consumption is expressed as O(h) where h is max depth of the tree.

If you want you can test yourself finding the solution, mine is under the cut below.

Continue reading “Question on interview: diameter of binary tree.”

boost.coroutine vs my $generator.

Today I saw discussion about boost.coroutine on gmane:

Generators and coroutines are conceptually the same feature and I have implementation of $generator thing that can be used to implement coroutines.

My implementation is of 15 lines of code and does not require any threads/fibers and so context switches – pure C++ with macro magic, pretty straightforward though.

Anyway, here is an example how coroutine can be implemented using that $generator thing.
First, let’s define coroutine (or generator) that will establish connection with some server and will supply (yield) data chunks read from socket:

$generator(net_reader)
{
   socket_t     sock;
   byte         buffer[2048];

   net_reader(const char* addr) { sock.connect(addr); }
   
   // from $emit to $stop is a body of our coroutine:
    
   $emit(slice<byte>) // Coroutine will emit slice<byte> values. Start of coroutine body.

      while( sock.valid() )
      {
          slice<byte> r(buffer,0);
          r.length = sock.read(buffer,sizeof(buffer));
          if(r.length)
            $yield( r ); 
          else 
            break; 
      }

   $stop; // stop. End of coroutine body.
};

Having this we can write code that will read data chunk by chunk and store it in some array.


array<byte> data;
net_reader  get("data.example.com:4002");

for(slice<byte> chunk; get(chunk);)
  data.push(chunk);

That’s easy, no?

Yes, $generator thing is not free from problems (e.g. you cannot use switch() inside its body) but other than that and in 99% of coroutine cases you will get what is needed from generators/coroutines. And without those tons of code.

The KiTE – template engine for JavaScript


Preface

Modern Web applications frequently use AJAX kind of client/server interaction. They receive data from the server in pure JSON format. That means instead of generating markup on the server such applications are composing HTML inside the browser (on client side).

Straightforward approach is to use string concatenation spagetti like : "<b>" + data + "</b>".  But this almost always will end up in non-maintainable mess. Real Jedi use markup templates. Typical PHP page is a script with embedded HTML – typical template the gets "instantiated" for the particular GET request/data/user.

PHP or plain old ASP are not only possible template formats. There are a lot of template engines and template languages in the wild. All of them fall into four major groups:

  1. Minimalistic, logic-less: {{mustache}} and (probably) PURE;
  2. Still simple TDLs but with some simple logic like if/else construcs: jQuery.tmpl() and the KiTE,
  3. PHP or ASP alike templates: JavaScript constructs embedded in HTML using <% %> brackets: jQote, John Resig’s Micro Templates, EJS, etc.
  4. Group of template engines based on #haml/Ruby ideas – they use special non-HTML markup.

In general: as simple language, less syntax noise it creates – as better. Easier to comprehend and so easier to maintain. The worst case from this perspective is actually PHP (group #3) – mix of two different syntaxes in single source (script and markup) can easily become not readable.  

Speed of template instantiation is on other axis of "templates space". Implementation of PHP alike templating (group #3) is relatively straightforward with JavaScript. Basic idea is to replace all text between
"%> ... some markup... <%"  
by something like
 out += "... some markup...";  
and wrap the template into
 compiled = new Function(transformed_template).

Template instantiation in this case is a matter of calling such function. This approach potentially is as fast as JavaScript itself. But as I said the template source is too "dirty" even in simple cases. I believe that code from this article http://blog.futtta.be/2011/01/18/how-to-do-jquery-templates-with-jqote2/ is a good example of how messy it can be with just few if/else’s.

On other side {{mustache}} templates are pretty clean but current {{mustache}} implementation is extremely slow. According to jsperf.com/dom-vs-innerhtml-based-templating/96 it is 150 times slower than the most effective jQote2. Too bad to be honest.

Another problem with the {{mustache}} is its logic-less nature. I understand the motivation but in reality some simple logic is required. Something like "if fieldA > 10 then render the record one way otherwise in some other".

So I came up with …

The KiTE.

KiTE is lightweight (180 lines of code) and fast JavaScript template engine. It uses template defintion language (TDL) that is close to {{mustache}} but with few additions: conditional sections and custom formatting functions.

Here is an example of KiTE template that emits simple list of contacts:

<ul>
  {{#contacts}}
    <li><b>{{firstName}}</b> <i>{{lastName}}</i></li>
  {{/contacts}}
</ul>

When given by JS data in following format:

{ contacts:
  [ { firstName: "Ernest", lastName:"Hemingway" },
    { firstName: "Scott", lastName:"Fitzgerald" } ]
}

the template will be instantiated as this list:

  • Ernest Hemingway
  • Scott Fitzgerald

KiTE templates can be placed in

<script type="text/x-kite">
  ...
</script>

sections on the page so they will not polute JavaScript code.

You can use this document http://terrainformatica.com/kite/test-kite.htm to get a feeling of the KiTE templates.

Idea behind KiTE implementation, defintion of TDL and the kite() function are all explained here code.google.com/p/kite/

And the last: the name "KiTE" is an acronym of "KiTE is a Template Engine".

C++0x: Running code in GUI thread from worker threads.

One of topics in design of multi-threading GUI applications is to choose method of calling GUI code from so called worker threads – threads that do some work in background. At some point they need to report results to the GUI. But GUI is a shareable resource so some form of synchronization is required. One approach is to use some global lock/mutex and capture it each time when any thread need to access tree of GUI objects.

Another method is to enqueue update tasks to the GUI thread. GUI thread will execute them when it can. This approach does not require synchronization code to be spread across whole application. The whole system will work faster and probability of deadlocks/synchronization issues is almost zero in this case.

The only problem: for each action that you need to do in GUI thread you will need to create separate task/object for deferred execution (or to use some other mechanism like marshalling in COM).

With new features of C++0x we can accomplish this with almost zero overhead. In particular we will need lambdas.

Here is how our code of worker thread function may look like:

void worker_thread()
{
  dom::element some_el = ...; 
  string html_to_set = ...;
  int result;
  ...
  auto gui_code_block = [some_el,html_to_set,&result] () 
  { // executed in GUI thread
    if(some.children() > 10)
      some.set_html(html_to_set);
    result = 20; // report some result if needed.
  };
  gui_exec(gui_code_block); 
  ...
  if( result == 20 ) ...;
  ...
}

As you see here I am declaring inline code block that will be
executed in GUI thread while the rest of the function body will run in its own thread.

The key point here is the gui_exec() function that may look like as:

void gui_exec( std::function<void()> gui_block )
{
  event evt;
  PostMessage(hwnd, WM_NULL, WPARAM(&evt),LPARAM(&gui_block));
  evt.wait(); // suspend worker thread until GUI will execute the block.
}

It posts the message to the GUI with address of synchronization object and
address of our GUI code block (function in fact). It is simple as you see.

And the last piece – we need message handler in GUI thread that will actually execute that code block. The best place for it is inside so called “GUI message pump” – Get/DispatchMessage loop that exist in any GUI application:

typedef std::function<void(void)> gui_block;

while (GetMessage(&msg, NULL, 0, 0))
{
    if( msg.message == WM_NULL )
    {
      gui_block* pf = reinterpret_cast<gui_block*>(msg.lParam);
      event* pe = reinterpret_cast<event*>(msg.wParam);
      (*pf)();  // execute the block
      pe->signal(); // signal that we've done with it
                        // this will resume execution of worker thread.
    }
    else 
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
}

And that is it.

The only note: I am using WM_NULL message here but in reality you should use some other not that popular message for it. RegisterWindowMessage() will help to get that message number.

Behaviors, simple jQuery extension.

Behaviors as an entity is a declarative way to assign/bind scripting methods to DOM elements.

We can think that browsers have following declarations in their default CSS declarations:

input[type=text]   { binding: TextEditorImpl; }
input[type=button] { binding: ButtonImpl; }
select             { binding: SelectImpl; }
...

So when we define <input type="text" /> in our markup we declare that the element will behave as a text editor – it will have set of all needed methods and will generate all associated events.  

It would be nice if in script we would be able to define our own behaviors for classes of DOM elements too.

As an example: blog article may have hyperlinks inside and particular blog engine may require some special behavior/reaction assigned to all hyperlinks in the article. Ideally such declaration should like this:

#content div.article a[href][title] 
{
  color: orange; // ui style
  behavior: LinkWithSmartTooltip; // behavioral style
}

In Sciter [1] that is an embeddable HTML/CSS/TIScript engine I have a luxury to step beyond W3C specifications so I’ve implemented the Behaviors in the way as I think they should be:

Behaviors in the Sciter engine

I have added the prototype attribute to my implementation of CSS:

some-CSS-selector 
{
   prototype: SomeBehaviorClass [ url(of a script file) ];
   ...
}

When the engine assignes CSS styles to elements it also tries to find class named SomeBehaviorClass. If such class is found then the element gets "subclassed" by the class. Technically the subclassing means that for all DOM elements that satisfy some-CSS-selector both these statements are true:

element instanceof SomeBehaviorClass; 
element instanceof Element; // Element is a super class of all DOM elements.

The SomeBehaviorClass looks in TIScript like this:

class SomeBehaviorClass: Behavior
{
   function attached() {} // constructor, sort of
   ...
}

The attached method plays a role of a constructor function in realm of Behaviors. It is called when particular element gets the behavior with this variable referring to the element. All this is I would say is pretty human readable an transparent.

Ok, back to the reality of the Web. Below is my attempt to define similar functionality using jQuery:

Behaviors for conventional browsers,  jQuery extension.

First of all here is my initial implementation of the behavior functionality: jquery-behaviors.js. It is pretty simple – near 75 lines of code.

It allows to declare behaviors on elements by using (a) class DOM attribute like this (purely in markup):

<span class="behavior uix-slider" /> 
<input class="behavior uix-date" />

and/or by (b) declaration of selector rules in script code:

$.behaviors.selector("ul.ext-list > li", MyExtListItem );

Later case allows to add behaviors non-intrusively – to any existing markup.

The Behaviors implementation above introduces three methods:

  1. $.behaviors.add( name, behaviorObj ) – add named behavior that can be used in "a" case above – in class names.
  2. $.behaviors.selector( selectorStr, behaviorObj ) – add "CSS selector -> behavior" association – case (b) above.
  3. $.fn.behaviors() – that is a plug-in that extends jQuery object wrapping set of elements. It used after calls of DOM mutating methods to assign behaviors to DOM elements:
    $("#update-panel").html("....").behaviors();

The behaviorObj above is the behavior implementation per se. It is a plain JavaScript object that defines set of methods and properties that will be mixed into the DOM element property map.

Here is a typical structure of some behavior named "x-checkbox" (see it’s demo here …) :

$.behaviors.add( "x-checkbox", 
{
  $attached: function(params) { ... },
  $value: function(v) { ... },
  $clear: function() { ... }
});

Function $attached here has special meaning – it gets called by the Behaviors engine when the element gets this behavior attached. The params here is a parsed version of the params DOM attribute that allows to parametrize instance of the behavior for the element. For example particular instances of a slider may have different initial settings:

<span id="first" class="behavior uix-slider" 
     params="min:0, max:100, values:[15,50]" />
<span id="second" class="behavior uix-slider" 
     params="min:10, max:200, value:50" />

Input behaviors, concept of the value. The "x-form" behavior.

In principle there are two distinct types of behaviors:

  • input behaviors – behaviors of elements that have a concept of the value. Input elements have at least these two methods:
    • method $value(v) – getter/setter of the value.
    • method $clear() – clear the value – revert it to the initial, markup declared state.
  • UI behaviors – behaviors implementing various UI effects like "click here – expand/collapse there".

The $value and $clear methods are used by the x-form behavior for gathering and setting values of input elements it contains. The x-form element is by itself is an input element (compound one). Its value is a map of name/value pairs – values of standard inputs and elements that have input behaviors attached. Behavior x-form can be assigned to any container that has inputs and call of its method $("#my-form")[0].$value() will give collection of values that are e.g. ready to be send over the AJAX.

The x-form and individual input behaviors may also implement concept of $validate() – that is not implemented yet but planned.

Demos

Here is couple of demonstrations of the approach:

  • jq-ui.htm – demo of jQuery-UI widgets wrapped into input and UI behaviors (implementation: jquery-ui-behaviors.js).  Also demonstrates use of x-form to gather/set/clear form data and dynamic html loading with behavior assignment.
  • std-behaviors.htm – purely declarative sample. Demonstrates x-checkbox behavior – is a input and UI element that can be bound declaratively with show/hide of "buddy" elements. Uses std-behaviors.js – implementation of the x-form and x-checkbox.

References

  1. The Sciter – an embeddable HTML/CSS/Scripting engine;
  2. TIScript language – JavaScript++ if you wish. Used in Sciter.
  3. Behaviors in Sciter, part I, part II and part III

C++, how to change class of object in runtime.

There is a nice feature in TIScript that allows to change class of already instantiated object.
Let’s say we have two classes:

class MyWidget : Behavior { ... }
class MyWidgetReadonly : Behavior { ... }

that handle user interaction with some widget on the screen. This widget can operate in two distinct modes: normal and read-only.
These modes share the same widget state but have substantially different behavioral characteristic. So it makes sense to split these two sets of methods into two classes to avoid pollution of our code by the crowd of if(readonly) ... else ....
When needed we can switch class of the object like this:

var widget = new MyWidget();
....
if( needReadOnlyMode )
  widget.prototype = MyWidgetReadonly; // changing class of the object.
...

Pretty much all dynamic languages allow to do such things. E.g. in Python you can modify obj.__bases__.

Surprisingly you can do the same in C++ too and without any “hack”. We can use so called placement new operator to do the trick. Here is how.

Let’s define our class hierarchy as this:

class MyWidget 
{
public:
  int data;  // state variables here
  virtual void on_mouse() { printf("normal on_mouse, data=%d\n",data); }
  virtual void on_key() { printf("normal on_key\n"); }
};
class MyWidgetReadOnly: public MyWidget   
{
  // no data at all here, sic!
  virtual void on_mouse() { printf("read-only on_mouse, data=%d\n",data); }
  virtual void on_key() { printf("read-only on_key\n"); }
};

And we will switch class of our object using this helper template function:

// turn_to(A* obj) changes class of the object 
// that means it just replaces VTBL of the object by VTBL of another class.
// NOTE: these two classes has to be ABI compatible!
template <typename TO_T, typename FROM_T>
  inline void turn_to(FROM_T* p) 
  { 
    assert( sizeof(FROM_T) == sizeof(TO_T));
    ::new(p) TO_T(); // use of placement new
  }

Note: This will work if our class has default constructor that does not initialize any member variables.

Let’s try this small sample ( test.cpp ):

#include <new>
#include <assert.h>
// turn_to(A* obj) changes class of the object 
// that means it just replaces VTBL of the object by VTBL of another class.
// NOTE: these two classes has to be ABI compatible!
template <typename TO_T, typename FROM_T>
  inline void turn_to(FROM_T* p) 
  { 
    assert( sizeof(FROM_T) == sizeof(TO_T));
    ::new(p) TO_T(); // use of placement new
  }

class MyWidget 
{
public:
  int data;  // state variables here
  virtual void on_mouse() { printf("normal on_mouse, data=%d\n",data); }
  virtual void on_key() { printf("normal on_key\n"); }
};
class MyWidgetReadOnly: public MyWidget   
{
  // no data at all here, sic!
  virtual void on_mouse() { printf("read-only on_mouse, data=%d\n",data); }
  virtual void on_key() { printf("read-only on_key\n"); }
};

int main(int argc, char* argv[])
{
  MyWidget *w = new MyWidget();
  w->data = 123;
  w->on_mouse();
  turn_to<MyWidgetReadOnly>(w); // turning the instance to MyWidgetReadOnly class.
  w->on_mouse();
	return 0;
}

After compiling and running it we should see in console output like this:

normal on_mouse, data=123
read-only on_mouse, data=123

So it works – we are able to transform existing instance of some class to the instance of other class.

DISCLAIMER:

Be warned that this is a Jedi Sword feature. Use it responsibly, only if you know why you need it. And what are the consequences. Even mentioning of this approach in some software development companies (that usually are on the Dark Side) may damage your reputation.