Merge pull request #127 from glyptodon/filter-token
GUAC-1138: Add filter pattern tokenizer.
diff --git a/guacamole/src/main/webapp/app/list/types/FilterPattern.js b/guacamole/src/main/webapp/app/list/types/FilterPattern.js
index 82fdfc2..fa42e2d 100644
--- a/guacamole/src/main/webapp/app/list/types/FilterPattern.js
+++ b/guacamole/src/main/webapp/app/list/types/FilterPattern.js
@@ -23,8 +23,16 @@
/**
* A service for defining the FilterPattern class.
*/
-angular.module('list').factory('FilterPattern', ['$parse',
- function defineFilterPattern($parse) {
+angular.module('list').factory('FilterPattern', ['$injector',
+ function defineFilterPattern($injector) {
+
+ // Required types
+ var FilterToken = $injector.get('FilterToken');
+ var IPv4Network = $injector.get('IPv4Network');
+ var IPv6Network = $injector.get('IPv6Network');
+
+ // Required services
+ var $parse = $injector.get('$parse');
/**
* Object which handles compilation of filtering predicates as used by
@@ -70,6 +78,138 @@
});
/**
+ * Determines whether the given object contains properties that match
+ * the given string, according to the provided getters.
+ *
+ * @param {Object} object
+ * The object to match against.
+ *
+ * @param {String} str
+ * The string to match.
+ *
+ * @returns {Boolean}
+ * true if the object matches the given string, false otherwise.
+ */
+ var matchesString = function matchesString(object, str) {
+
+ // For each defined getter
+ for (var i=0; i < getters.length; i++) {
+
+ // Retrieve value of current getter
+ var value = getters[i](object);
+
+ // If the value matches the pattern, the whole object matches
+ if (String(value).toLowerCase().indexOf(str) !== -1)
+ return true;
+
+ }
+
+ // No matches found
+ return false;
+
+ };
+
+ /**
+ * Determines whether the given object contains properties that match
+ * the given IPv4 network, according to the provided getters.
+ *
+ * @param {Object} object
+ * The object to match against.
+ *
+ * @param {IPv4Network} network
+ * The IPv4 network to match.
+ *
+ * @returns {Boolean}
+ * true if the object matches the given network, false otherwise.
+ */
+ var matchesIPv4 = function matchesIPv4(object, network) {
+
+ // For each defined getter
+ for (var i=0; i < getters.length; i++) {
+
+ // Test value against IPv4 network
+ var value = IPv4Network.parse(String(getters[i](object)));
+ if (value && network.contains(value))
+ return true;
+
+ }
+
+ // No matches found
+ return false;
+
+ };
+
+ /**
+ * Determines whether the given object contains properties that match
+ * the given IPv6 network, according to the provided getters.
+ *
+ * @param {Object} object
+ * The object to match against.
+ *
+ * @param {IPv6Network} network
+ * The IPv6 network to match.
+ *
+ * @returns {Boolean}
+ * true if the object matches the given network, false otherwise.
+ */
+ var matchesIPv6 = function matchesIPv6(object, network) {
+
+ // For each defined getter
+ for (var i=0; i < getters.length; i++) {
+
+ // Test value against IPv6 network
+ var value = IPv6Network.parse(String(getters[i](object)));
+ if (value && network.contains(value))
+ return true;
+
+ }
+
+ // No matches found
+ return false;
+
+ };
+
+
+ /**
+ * Determines whether the given object matches the given filter pattern
+ * token.
+ *
+ * @param {Object} object
+ * The object to match the token against.
+ *
+ * @param {FilterToken} token
+ * The token from the tokenized filter pattern to match aginst the
+ * given object.
+ *
+ * @returns {Boolean}
+ * true if the object matches the token, false otherwise.
+ */
+ var matchesToken = function matchesToken(object, token) {
+
+ // Match depending on token type
+ switch (token.type) {
+
+ // Simple string literal
+ case 'LITERAL':
+ return matchesString(object, token.value);
+
+ // IPv4 network address / subnet
+ case 'IPV4_NETWORK':
+ return matchesIPv4(object, token.value);
+
+ // IPv6 network address / subnet
+ case 'IPV6_NETWORK':
+ return matchesIPv6(object, token.value);
+
+ // Unsupported token type
+ default:
+ return false;
+
+ }
+
+ };
+
+ /**
* The current filtering predicate.
*
* @type Function
@@ -92,26 +232,20 @@
return;
}
- // Convert to lower case for case insensitive matching
- pattern = pattern.toLowerCase();
+ // Tokenize pattern, converting to lower case for case-insensitive matching
+ var tokens = FilterToken.tokenize(pattern.toLowerCase());
// Return predicate which matches against the value of any getter in the getters array
- filterPattern.predicate = function matchAny(object) {
+ filterPattern.predicate = function matchesAllTokens(object) {
- // For each defined getter
- for (var i=0; i < getters.length; i++) {
-
- // Retrieve value of current getter
- var value = getters[i](object);
-
- // If the value matches the pattern, the whole object matches
- if (String(value).toLowerCase().indexOf(pattern) !== -1)
- return true;
-
+ // False if any token does not match
+ for (var i=0; i < tokens.length; i++) {
+ if (!matchesToken(object, tokens[i]))
+ return false;
}
- // No matches found
- return false;
+ // True if all tokens matched
+ return true;
};
diff --git a/guacamole/src/main/webapp/app/list/types/FilterToken.js b/guacamole/src/main/webapp/app/list/types/FilterToken.js
new file mode 100644
index 0000000..915f072
--- /dev/null
+++ b/guacamole/src/main/webapp/app/list/types/FilterToken.js
@@ -0,0 +1,232 @@
+/*
+ * Copyright (C) 2015 Glyptodon LLC
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+/**
+ * A service for defining the FilterToken class.
+ */
+angular.module('list').factory('FilterToken', ['$injector',
+ function defineFilterToken($injector) {
+
+ // Required types
+ var IPv4Network = $injector.get('IPv4Network');
+ var IPv6Network = $injector.get('IPv6Network');
+
+ /**
+ * An arbitrary token having an associated type and value.
+ *
+ * @constructor
+ * @param {String} consumed
+ * The input string consumed to produce this token.
+ *
+ * @param {String} type
+ * The type of this token. Each legal type name is a property within
+ * FilterToken.Types.
+ *
+ * @param {Object} value
+ * The value of this token. The type of this value is determined by
+ * the token type.
+ */
+ var FilterToken = function FilterToken(consumed, type, value) {
+
+ /**
+ * The input string that was consumed to produce this token.
+ *
+ * @type String
+ */
+ this.consumed = consumed;
+
+ /**
+ * The type of this token. Each legal type name is a property within
+ * FilterToken.Types.
+ *
+ * @type String
+ */
+ this.type = type;
+
+ /**
+ * The value of this token.
+ *
+ * @type Object
+ */
+ this.value = value;
+
+ };
+
+ /**
+ * All legal token types, and corresponding functions which match them.
+ * Each function returns the parsed token, or null if no such token was
+ * found.
+ *
+ * @type Object.<String, Function>
+ */
+ FilterToken.Types = {
+
+ /**
+ * An IPv4 address or subnet. The value of an IPV4_NETWORK token is an
+ * IPv4Network.
+ */
+ IPV4_NETWORK: function parseIPv4(str) {
+
+ var pattern = /^\S+/;
+
+ // Read first word via regex
+ var matches = pattern.exec(str);
+ if (!matches)
+ return null;
+
+ // Validate and parse as IPv4 address
+ var network = IPv4Network.parse(matches[0]);
+ if (!network)
+ return null;
+
+ return new FilterToken(matches[0], 'IPV4_NETWORK', network);
+
+ },
+
+ /**
+ * An IPv6 address or subnet. The value of an IPV6_NETWORK token is an
+ * IPv6Network.
+ */
+ IPV6_NETWORK: function parseIPv6(str) {
+
+ var pattern = /^\S+/;
+
+ // Read first word via regex
+ var matches = pattern.exec(str);
+ if (!matches)
+ return null;
+
+ // Validate and parse as IPv6 address
+ var network = IPv6Network.parse(matches[0]);
+ if (!network)
+ return null;
+
+ return new FilterToken(matches[0], 'IPV6_NETWORK', network);
+
+ },
+
+ /**
+ * A string literal, which may be quoted. The value of a LITERAL token
+ * is a String.
+ */
+ LITERAL: function parseLiteral(str) {
+
+ var pattern = /^"([^"]*)"|^\S+/;
+
+ // Validate against pattern
+ var matches = pattern.exec(str);
+ if (!matches)
+ return null;
+
+ // If literal is quoted, parse within the quotes
+ if (matches[1])
+ return new FilterToken(matches[0], 'LITERAL', matches[1]);
+
+ // Otherwise, literal is unquoted
+ return new FilterToken(matches[0], 'LITERAL', matches[0]);
+
+ },
+
+ /**
+ * Arbitrary contiguous whitespace. The value of a WHITESPACE token is
+ * a String.
+ */
+ WHITESPACE: function parseWhitespace(str) {
+
+ var pattern = /^\s+/;
+
+ // Validate against pattern
+ var matches = pattern.exec(str);
+ if (!matches)
+ return null;
+
+ // Generate token from matching whitespace
+ return new FilterToken(matches[0], 'WHITESPACE', matches[0]);
+
+ }
+
+ };
+
+ /**
+ * Tokenizes the given string, returning an array of tokens. Whitespace
+ * tokens are dropped.
+ *
+ * @param {String} str
+ * The string to tokenize.
+ *
+ * @returns {FilterToken[]}
+ * All tokens identified within the given string, in order.
+ */
+ FilterToken.tokenize = function tokenize(str) {
+
+ var tokens = [];
+
+ /**
+ * Returns the first token on the current string, removing the token
+ * from that string.
+ *
+ * @returns FilterToken
+ * The first token on the string, or null if no tokens match.
+ */
+ var popToken = function popToken() {
+
+ // Attempt to find a matching token
+ for (var type in FilterToken.Types) {
+
+ // Get matching function for current type
+ var matcher = FilterToken.Types[type];
+
+ // If token matches, return the matching group
+ var token = matcher(str);
+ if (token) {
+ str = str.substring(token.consumed.length);
+ return token;
+ }
+
+ }
+
+ // No match
+ return null;
+
+ };
+
+ // Tokenize input until no input remains
+ while (str) {
+
+ // Remove first token
+ var token = popToken();
+ if (!token)
+ break;
+
+ // Add token to tokens array, if not whitespace
+ if (token.type !== 'WHITESPACE')
+ tokens.push(token);
+
+ }
+
+ return tokens;
+
+ };
+
+ return FilterToken;
+
+}]);
\ No newline at end of file
diff --git a/guacamole/src/main/webapp/app/list/types/IPv4Network.js b/guacamole/src/main/webapp/app/list/types/IPv4Network.js
new file mode 100644
index 0000000..6ee8ff1
--- /dev/null
+++ b/guacamole/src/main/webapp/app/list/types/IPv4Network.js
@@ -0,0 +1,129 @@
+/*
+ * Copyright (C) 2015 Glyptodon LLC
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+/**
+ * A service for defining the IPv4Network class.
+ */
+angular.module('list').factory('IPv4Network', [
+ function defineIPv4Network() {
+
+ /**
+ * Represents an IPv4 network as a pairing of base address and netmask,
+ * both of which are in binary form. To obtain an IPv4Network from
+ * standard CIDR or dot-decimal notation, use IPv4Network.parse().
+ *
+ * @constructor
+ * @param {Number} address
+ * The IPv4 address of the network in binary form.
+ *
+ * @param {Number} netmask
+ * The IPv4 netmask of the network in binary form.
+ */
+ var IPv4Network = function IPv4Network(address, netmask) {
+
+ /**
+ * Reference to this IPv4Network.
+ *
+ * @type IPv4Network
+ */
+ var network = this;
+
+ /**
+ * The binary address of this network. This will be a 32-bit quantity.
+ *
+ * @type Number
+ */
+ this.address = address;
+
+ /**
+ * The binary netmask of this network. This will be a 32-bit quantity.
+ *
+ * @type Number
+ */
+ this.netmask = netmask;
+
+ /**
+ * Tests whether the given network is entirely within this network,
+ * taking into account the base addresses and netmasks of both.
+ *
+ * @param {IPv4Network} other
+ * The network to test.
+ *
+ * @returns {Boolean}
+ * true if the other network is entirely within this network, false
+ * otherwise.
+ */
+ this.contains = function contains(other) {
+ return network.address === (other.address & other.netmask & network.netmask);
+ };
+
+ };
+
+ /**
+ * Parses the given string as an IPv4 address or subnet, returning an
+ * IPv4Network object which describes that address or subnet.
+ *
+ * @param {String} str
+ * The string to parse.
+ *
+ * @returns {IPv4Network}
+ * The parsed network, or null if the given string is not valid.
+ */
+ IPv4Network.parse = function parse(str) {
+
+ // Regex which matches the general form of IPv4 addresses
+ var pattern = /^([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})(?:\/([0-9]{1,2}))?$/;
+
+ // Parse IPv4 address via regex
+ var match = pattern.exec(str);
+ if (!match)
+ return null;
+
+ // Parse netmask, if given
+ var netmask = 0xFFFFFFFF;
+ if (match[5]) {
+ var bits = parseInt(match[5]);
+ if (bits > 0 && bits <= 32)
+ netmask = 0xFFFFFFFF << (32 - bits);
+ }
+
+ // Read each octet onto address
+ var address = 0;
+ for (var i=1; i <= 4; i++) {
+
+ // Validate octet range
+ var octet = parseInt(match[i]);
+ if (octet > 255)
+ return null;
+
+ // Shift on octet
+ address = (address << 8) | octet;
+
+ }
+
+ return new IPv4Network(address, netmask);
+
+ };
+
+ return IPv4Network;
+
+}]);
diff --git a/guacamole/src/main/webapp/app/list/types/IPv6Network.js b/guacamole/src/main/webapp/app/list/types/IPv6Network.js
new file mode 100644
index 0000000..e2b4004
--- /dev/null
+++ b/guacamole/src/main/webapp/app/list/types/IPv6Network.js
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2015 Glyptodon LLC
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+/**
+ * A service for defining the IPv6Network class.
+ */
+angular.module('list').factory('IPv6Network', [
+ function defineIPv6Network() {
+
+ /**
+ * Represents an IPv6 network as a pairing of base address and netmask,
+ * both of which are in binary form. To obtain an IPv6Network from
+ * standard CIDR notation, use IPv6Network.parse().
+ *
+ * @constructor
+ * @param {Number[]} addressGroups
+ * Array of eight IPv6 address groups in binary form, each group being
+ * 16-bit number.
+ *
+ * @param {Number[]} netmaskGroups
+ * Array of eight IPv6 netmask groups in binary form, each group being
+ * 16-bit number.
+ */
+ var IPv6Network = function IPv6Network(addressGroups, netmaskGroups) {
+
+ /**
+ * Reference to this IPv6Network.
+ *
+ * @type IPv6Network
+ */
+ var network = this;
+
+ /**
+ * The 128-bit binary address of this network as an array of eight
+ * 16-bit numbers.
+ *
+ * @type Number[]
+ */
+ this.addressGroups = addressGroups;
+
+ /**
+ * The 128-bit binary netmask of this network as an array of eight
+ * 16-bit numbers.
+ *
+ * @type Number
+ */
+ this.netmaskGroups = netmaskGroups;
+
+ /**
+ * Tests whether the given network is entirely within this network,
+ * taking into account the base addresses and netmasks of both.
+ *
+ * @param {IPv6Network} other
+ * The network to test.
+ *
+ * @returns {Boolean}
+ * true if the other network is entirely within this network, false
+ * otherwise.
+ */
+ this.contains = function contains(other) {
+
+ // Test that each masked 16-bit quantity matches the address
+ for (var i=0; i < 8; i++) {
+ if (network.addressGroups[i] !== (other.addressGroups[i]
+ & other.netmaskGroups[i]
+ & network.netmaskGroups[i]))
+ return false;
+ }
+
+ // All 16-bit numbers match
+ return true;
+
+ };
+
+ };
+
+ /**
+ * Generates a netmask having the given number of ones on the left side.
+ * All other bits within the netmask will be zeroes. The resulting netmask
+ * will be an array of eight numbers, where each number corresponds to a
+ * 16-bit group of an IPv6 netmask.
+ *
+ * @param {Number} bits
+ * The number of ones to include on the left side of the netmask. All
+ * other bits will be zeroes.
+ *
+ * @returns {Number[]}
+ * The generated netmask, having the given number of ones.
+ */
+ var generateNetmask = function generateNetmask(bits) {
+
+ var netmask = [];
+
+ // Only generate up to 128 bits
+ bits = Math.min(128, bits);
+
+ // Add any contiguous 16-bit sections of ones
+ while (bits >= 16) {
+ netmask.push(0xFFFF);
+ bits -= 16;
+ }
+
+ // Add remaining ones
+ if (bits > 0 && bits <= 16)
+ netmask.push(0xFFFF & (0xFFFF << (16 - bits)));
+
+ // Add remaining zeroes
+ while (netmask.length < 8)
+ netmask.push(0);
+
+ return netmask;
+
+ };
+
+ /**
+ * Splits the given IPv6 address or partial address into its corresponding
+ * 16-bit groups.
+ *
+ * @param {String} str
+ * The IPv6 address or partial address to split.
+ *
+ * @returns Number[]
+ * The numeric values of all 16-bit groups within the given IPv6
+ * address.
+ */
+ var splitAddress = function splitAddress(str) {
+
+ var address = [];
+
+ // Split address into groups
+ var groups = str.split(':');
+
+ // Parse the numeric value of each group
+ angular.forEach(groups, function addGroup(group) {
+ var value = parseInt(group || '0', 16);
+ address.push(value);
+ });
+
+ return address;
+
+ };
+
+ /**
+ * Parses the given string as an IPv6 address or subnet, returning an
+ * IPv6Network object which describes that address or subnet.
+ *
+ * @param {String} str
+ * The string to parse.
+ *
+ * @returns {IPv6Network}
+ * The parsed network, or null if the given string is not valid.
+ */
+ IPv6Network.parse = function parse(str) {
+
+ // Regex which matches the general form of IPv6 addresses
+ var pattern = /^([0-9a-f]{0,4}(?::[0-9a-f]{0,4}){0,7})(?:\/([0-9]{1,3}))?$/;
+
+ // Parse rudimentary IPv6 address via regex
+ var match = pattern.exec(str);
+ if (!match)
+ return null;
+
+ // Extract address and netmask from parse results
+ var unparsedAddress = match[1];
+ var unparsedNetmask = match[2];
+
+ // Parse netmask
+ var netmask;
+ if (unparsedNetmask)
+ netmask = generateNetmask(parseInt(unparsedNetmask));
+ else
+ netmask = generateNetmask(128);
+
+ var address;
+
+ // Separate based on the double-colon, if present
+ var doubleColon = unparsedAddress.indexOf('::');
+
+ // If no double colon, just split into groups
+ if (doubleColon === -1)
+ address = splitAddress(unparsedAddress);
+
+ // Otherwise, split either side of the double colon and pad with zeroes
+ else {
+
+ // Parse either side of the double colon
+ var leftAddress = splitAddress(unparsedAddress.substring(0, doubleColon));
+ var rightAddress = splitAddress(unparsedAddress.substring(doubleColon + 2));
+
+ // Pad with zeroes up to address length
+ var remaining = 8 - leftAddress.length - rightAddress.length;
+ while (remaining > 0) {
+ leftAddress.push(0);
+ remaining--;
+ }
+
+ address = leftAddress.concat(rightAddress);
+
+ }
+
+ // Validate length of address
+ if (address.length !== 8)
+ return null;
+
+ return new IPv6Network(address, netmask);
+
+ };
+
+ return IPv6Network;
+
+}]);