MS RFC 64-MAPServer表达式分析器大修

日期

2010/11/2

作者

史蒂夫·莱姆

联系

com.net上的石灰

最后编辑

2010-11-2

状态

采用

概述

这是一个草案RFC寻址1）如何实现逻辑表达式的bison/yacc解析器，以及2）在mapserver代码中可以使用解析器的地方。此RFC可能对查询处理产生更广泛的影响，这取决于驱动程序级别的其他更改，特别是RDBMS更改。这些变化不一定非得发生才能成为有用的补充。

这项工作的一个主要动机是以独立于驱动程序的方式在一次传递中支持OGC过滤器表达式。

这里详细介绍的所有工作都是在沙盒中原型化的，请访问：

http://svn.osgeo.org/mapserver/sandbox/sdlime/common-expressions/mapserver <http://svn.osgeo.org/mapserver/sandbox/sdlime/common-expressions/mapserver>

现有表达式分析

MapServer中现有的逻辑表达式处理的工作方式如下：

  1. 重复的表达式字符串[[br]]

  2. 将形状属性替换为字符串（例如，“[名称]”=>“anoka”）[[br]]

  3. 用YYParse（）分析

解析器内部调用YYLEX（）来获取其令牌。标记是表达式中最小的部分。

Advantages

  • 它很简单而且很有效

Disadvantages

  • 受字符串替换的限制，无法处理复杂类型

  • 必须执行替换并标记每个特性的结果字符串

拟议技术变更

本RFC提出了一些技术变更。然而，核心的变化涉及到更新逻辑表达式的工作方式。其他特性利用这个核心变更为MapServer带来更多功能。

核心解析器更新

我建议移动到一个设置，在该设置中，逻辑表达式被标记化一次（通过我们的flex生成的lexer），然后bison/yacc解析器根据每个功能的需要通过标记（通过mapparser.y中定义的自定义版本yylex（））工作。这消除了当前所需的替换和标记化步骤，并为在表达式中支持更复杂的对象打开了可能性。基本上，我们将在ExpressionObj中挂起一个标记列表，将其填充到mslayerwhichitems（）中，并根据解析器中的需要利用这些标记。以下新结构和枚举将添加到mapserver.h中：

enum MS_TOKEN_LOGICAL_ENUM { MS_TOKEN_LOGICAL_AND=100, MS_TOKEN_LOGICAL_OR, MS_TOKEN_LOGICAL_NOT };
enum MS_TOKEN_LITERAL_ENUM { MS_TOKEN_LITERAL_NUMBER=110, MS_TOKEN_LITERAL_STRING, MS_TOKEN_LITERAL_TIME, MS_TOKEN_LITERAL_SHAPE };
enum MS_TOKEN_COMPARISON_ENUM {
  MS_TOKEN_COMPARISON_EQ=120, MS_TOKEN_COMPARISON_NE, MS_TOKEN_COMPARISON_GT, MS_TOKEN_COMPARISON_LT, MS_TOKEN_COMPARISON_LE, MS_TOKEN_COMPARISON_GE, MS_TOKEN_COMPARISON_IEQ,
  MS_TOKEN_COMPARISON_RE, MS_TOKEN_COMPARISON_IRE,
  MS_TOKEN_COMPARISON_IN, MS_TOKEN_COMPARISON_LIKE,
  MS_TOKEN_COMPARISON_INTERSECTS, MS_TOKEN_COMPARISON_DISJOINT, MS_TOKEN_COMPARISON_TOUCHES, MS_TOKEN_COMPARISON_OVERLAPS, MS_TOKEN_COMPARISON_CROSSES, MS_TOKEN_COMPARISON_WITHIN, MS_TOKEN_COMPARISON_CONTAINS,
  MS_TOKEN_COMPARISON_BEYOND, MS_TOKEN_COMPARISON_DWITHIN
};
enum MS_TOKEN_FUNCTION_ENUM { MS_TOKEN_FUNCTION_LENGTH=140, MS_TOKEN_FUNCTION_TOSTRING, MS_TOKEN_FUNCTION_COMMIFY, MS_TOKEN_FUNCTION_AREA, MS_TOKEN_FUNCTION_ROUND, MS_TOKEN_FUNCTION_FROMTEXT };
enum MS_TOKEN_BINDING_ENUM { MS_TOKEN_BINDING_DOUBLE=150, MS_TOKEN_BINDING_INTEGER, MS_TOKEN_BINDING_STRING, MS_TOKEN_BINDING_TIME, MS_TOKEN_BINDING_SHAPE };

typedef union {
  double dblval;
  int intval;
  char *strval;
  struct tm tmval;
  shapeObj *shpval;
  attributeBindingObj bindval;
} tokenValueObj;

typedef struct {
  int token;
  tokenValueObj tokenval;
} tokenObj;

其中一些定义暗示了稍后将详细介绍的其他特性。当我们将表达式字符串转换为一系列标记时，我们还存储了与该标记关联的值（如果需要）。在许多情况下，标记值是一个文本（字符串或数字），在其他情况下，它是对特性属性的引用。在后一种情况下，我们使用MapServer已经使用的attributeBindingObj来封装快速访问正确数据（通常是项目索引值）所需的信息。

我们总是必须通过临时全局变量使表达式数据可供解析器（和lexer）使用。尽管在这个上下文中共享了不同的数据，但在这里情况仍然如此。需要注意的一点是，一旦一个表达式被标记化，我们就不再需要依赖于flex生成的lexer，因此，在理论上，如果我们选择这样做，实现线程安全的解析器应该更容易。

扩展yacc语法以支持空间运算符

上面的mapserver.h定义允许在yacc语法中使用shapeobj（我们还将shapeobj定义为mapparser.y中的新基本令牌类型）。与形状相关的标记有两种类型：1）形状绑定，即对正在计算的几何图形的引用；2）形状文本，表达式字符串中描述为WKT的形状。例如：

In the expression:
  EXPRESSION (fromText('POINT(500000 5000000)') Intersects [shape])

  1) fromText('POINT(500000 5000000)') defines a shape literal (the WKT to shapeObj conversion is done only once)
  2) [shape] is a shape binding

我们可以在语法中使用这些标记来实现所有支持的mapserver（通过geos）逻辑运算符。注意，在上面的示例中，fromText（）显示为对字符串进行操作的函数。在标记化字符串时，这是一种特殊情况，因为我们只想这样做一次。所以我们创建了一个基于WKT字符串的形状文本。

扩展语法以支持空间函数

通过支持使用更复杂的对象，我们可以支持这些对象上的函数。我们可以写：

EXPRESSION (area([shape]) < 100000)

或者更多地依赖全球测地系统操作员。（注意：沙盒中只存在区域函数。）要做到这一点，我们需要以某种方式存储shapeobj的作用域，以便工作副本可以根据需要自由使用。我建议将“int scope”添加到shapeobj结构定义中。在表达式计算过程中创建的形状将被标记为具有有限的范围，而文本或绑定将被单独保留，稍后可能会被销毁。这样就省去了制作昂贵形状的复制品。

上下文敏感分析

我们可以一直这样做，但这将是实现上下文敏感的解析器使用的合适时机。目前，我们期望解析器生成一个正确或错误的结果，但肯定不限于此。其思想是使用解析器在其他情况下计算值。沙盒中有两个地方正在工作，具体如下。

等级 TEXT 参数

目前你可以写：

CLASS
  ...
  TEXT ([area] acres)
END

文本值看起来像是一个表达式(并且它是这样存储的)，但它并没有作为一个表达式进行计算。将其视为一种真实的表达将是非常有用的。这将为那些在其他方面不支持它的驱动程序打开一个格式化选项的世界(例如Shapefile)。车票 2950 <https://github.com/MapServer/MapServer/issues/2950> 就是一个例子，这将派上用场。在沙箱中，我添加了to字符串、ROUND和COMMIFY函数，以便您可以编写：

TEXT (commify(toString([area]*0.000247105381,"%.2f")) + ' ac')

它将面积从平方米转换为英亩，将结果截断为两个小数位，并添加逗号（213324.123455=>213324.12），用于令人愉悦的人群显示。要添加此支持，除了语法更改，我们还将这些声明添加到mapserver.h：

enum MS_PARSE_RESULT_TYPE_ENUM { MS_PARSE_RESULT_BOOLEAN, MS_PARSE_RESULT_STRING, MS_PARSE_RESULT_SHAPE };

typedef union {
  int intval;
  char *strval;
  shapeObj *shpval;
} parseResultObj;

然后在语法中，我们设置一个解析结果类型并相应地设置结果。一个副作用是，我们必须定义一种标准的方法，在字符串上下文中将数字转换为字符串，并且简单地将“%g”用作snprintf的格式字符串，这对输出来说确实是个奇迹。

样式**geomtransform**

在沙盒中，我将geomtransforms作为表达式实现，而不是原始实现。还扩展了解析器以支持GEOS缓冲区运算符。所以你可以写：

STYLE
  GEOMTRANSFORM (buffer([shape], -3))
  ...
END

这会在渲染前在几何体上执行缓冲区（请参见test.buffer.png附件）。因为geomtransform处理发生了这种转换 after 该特征由地图坐标转换为图像坐标，但效果仍然很有价值，缓冲值以像素为单位。将来，我们可能会考虑在层级别上实现一个geomtransform，以便所有类和/或样式都可以使用该转换（因此在查询模式中也是如此）。

表达式在别处使用

当前，逻辑表达式语法还用于Requires/LabelRequires和Raster。在requires/labelrequires的情况下，代码将大部分保持“原样”，我们仍然会根据层状态进行替换，然后显式地标记化和解析。因为每层最多做一次，所以实际上不需要做更多的事情。

拉斯特提出了更多的挑战。当通过定义像素绑定对表达式进行标记化时，我们需要将它们作为特殊情况来处理，然后在评估表达式时将像素传递给解析器。这应该是 much, much 比将每个像素值转换为字符串表示形式（然后再转换回数字）的当前方法更快，特别是考虑到经常计算的像素数。如果可以向geos操作符公开像素位置，也可以使用一些有趣的绘图效果。例如，可以创建一个仅显示特定几何图形中像素的遮罩。

查询影响

这就是事情变得有趣的地方。我建议添加一个新的查询msquerybyfilter（），它可以处理表达式字符串（这在沙盒中工作）。表达式字符串仍必须与扩展参数一起使用。像shapefiles这样的驱动程序仍然需要在应用辅助过滤器之前先应用一个边界框。其他驱动程序可以选择组合范围和表达式字符串（更可能是标记），如果他们这样选择的话。msquerybyfilter（）的工作方式与msquerybyattributes（）非常相似。层API已被扩展为包含一个原型mslayerSupportsCommonFilters（），它允许驱动程序说它是否可以以某种方式（例如，通过filter和mslayerwhichhapes（）/mslayerNextShape（））本地处理该公共表达式格式，或者在重复调用mslayerNextShape（）之后是否需要应用该表达式。shapefile和平铺的shapefile驱动程序将以本机方式工作，任何使用msevelExpression（）的驱动程序也将以本机方式工作。我希望RDBMS驱动程序能够以某种方式（通过令牌）将表达式转换为其本机SQL，但如果不是，我们仍然能够使用这些源代码。

向后兼容性问题

出奇的少。解析器的更改对用户来说都是透明的。真正将文本表达式作为表达式处理是一种回归，尽管是一种正的回归。我还将提出一些表达式级别的更改，特别是在逻辑表达式中不区分大小写的字符串和regex比较周围。我认为简单地定义不区分大小写的运算符（例如，eq和i eq表示直字符串相等，~和~*表示regex（仿照postgres建模），这样做更有意义，也更便于用户使用。

附加的运算符、函数和解析上下文是新的功能。

如果这样做，大量的代码将被废弃。大多数OWS过滤器评估将由msquerybyfilter（）函数和许多相关的枚举、定义等处理。可以走开。

语法摘要（bold表示新的）：

  • 逻辑运算符：and，or，not

  • 比较运算符：=，=*，！=，>，<，>=，<=，~，~，in

  • 空间比较运算符： 相交, 不相交, 触摸, 重叠, 十字架, 在内部, 包含, 超过, *** * * *

  • 功能：长度， 归并, 圆, 字符串

  • 空间功能： 从文本, area, 距离, 缓冲

安全问题

虽然大部分的工作都在MapServer的内部，但是这种规模的任何变化都可能产生意想不到的后果。在这种情况下，我认为最大的风险是与解析器中的字符串运算符相关联的缓冲区溢出和内存泄漏。在开发一组全面的测试用例时需要小心。

Todo

  1. “in”运算符急需优化。

  2. 需要支持所有OGC筛选器操作。尤其是边界框过滤器还没有被研究过。

  3. 需要“like”运算符代码。（例如，Dobbs博士，9/08，“匹配通配符：算法”，第37-39页）

  4. 如何在msquerybyfilter（）中处理层公差？

  5. 管理令牌的最佳方法：数组、列表、树？野牛/yacc需要数组或列表，但弗兰克和保罗都提到过树。（更新：令牌现在作为链接列表进行管理。）

  6. 线程安全…

  7. 解析器错误处理，任何错误基本上都被自动忽略。

臭虫识别码

α3613

投票历史

2010年12月1日通过，Steve L、Steve W、Perry、Assefa、Tamas的A+1。