Change match order to avoid inefficient comparisons

[octogonz]

I encountered the problem #111 today, where ESLint crashes due to TypeScript node types that are unrecognized by esquery. But it raises a different question about query strategy:

In my case, the selector Program > :first-child is trying to match the very first node in the AST tree. I was surprised to find that the crash was happening when this code is trying to find the :first-child of a TSTypeAnnotation very deep in the AST tree:

https://github.com/estools/esquery/blob/e27e73d8cde63a2eb1aba3424510ce1b714d207e/esquery.js#L301-L317

Why should this comparison be performed at all? I expected for Program to trivially fail to match TSTypeAnnotation, and the :first-child would never even get tested.

It seems that the query evaluation for > ('child') compares the right side :first-child BEFORE comparing the left side Program: https://github.com/estools/esquery/blob/e27e73d8cde63a2eb1aba3424510ce1b714d207e/esquery.js#L131-L135

Is there a good reason for that?

Logically it is like: "Is there a tire? --> Is the tire on a wheel? --> Is the wheel on a vehicle? --> Is the vehicle a motorcycle?"

Wouldn't it be better to first check for a motorcycle, before we go inspecting every tire?

The error goes away if I reorder the tests like this:

 case 'child': 
     if (matches(ancestry[0], selector.left, ancestry.slice(1))) { 
         return matches(node, selector.right, ancestry);
     } 
     return false; 

Should we make this change? Is there any downside?

[urugator]

Wouldn't it be better to first check for a motorcycle, before we go inspecting every tire?

I assume, similar to CSS handling in browsers, it's not optimized for individual searches, but for checking which nodes of AST matches possibly large set of selectors: https://stackoverflow.com/a/5813672