| 1 | <?php |
| 2 | /* |
| 3 | +--------------------------------------------------------------------+ |
| 4 | | CiviCRM version 4.7 | |
| 5 | +--------------------------------------------------------------------+ |
| 6 | | Copyright CiviCRM LLC (c) 2004-2015 | |
| 7 | +--------------------------------------------------------------------+ |
| 8 | | This file is a part of CiviCRM. | |
| 9 | | | |
| 10 | | CiviCRM is free software; you can copy, modify, and distribute it | |
| 11 | | under the terms of the GNU Affero General Public License | |
| 12 | | Version 3, 19 November 2007 and the CiviCRM Licensing Exception. | |
| 13 | | | |
| 14 | | CiviCRM is distributed in the hope that it will be useful, but | |
| 15 | | WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 16 | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
| 17 | | See the GNU Affero General Public License for more details. | |
| 18 | | | |
| 19 | | You should have received a copy of the GNU Affero General Public | |
| 20 | | License and the CiviCRM Licensing Exception along | |
| 21 | | with this program; if not, contact CiviCRM LLC | |
| 22 | | at info[AT]civicrm[DOT]org. If you have questions about the | |
| 23 | | GNU Affero General Public License or the licensing of CiviCRM, | |
| 24 | | see the CiviCRM license FAQ at http://civicrm.org/licensing | |
| 25 | +--------------------------------------------------------------------+ |
| 26 | */ |
| 27 | |
| 28 | /** |
| 29 | * |
| 30 | * @package CRM |
| 31 | * @copyright CiviCRM LLC (c) 2004-2015 |
| 32 | */ |
| 33 | class CRM_Contact_BAO_GroupNestingCache { |
| 34 | |
| 35 | /** |
| 36 | * Update cache. |
| 37 | * |
| 38 | * @throws \Exception |
| 39 | */ |
| 40 | static public function update() { |
| 41 | // lets build the tree in memory first |
| 42 | |
| 43 | $sql = " |
| 44 | SELECT n.child_group_id as child , |
| 45 | n.parent_group_id as parent |
| 46 | FROM civicrm_group_nesting n, |
| 47 | civicrm_group gc, |
| 48 | civicrm_group gp |
| 49 | WHERE n.child_group_id = gc.id |
| 50 | AND n.parent_group_id = gp.id |
| 51 | "; |
| 52 | |
| 53 | $dao = CRM_Core_DAO::executeQuery($sql); |
| 54 | |
| 55 | $tree = array(); |
| 56 | while ($dao->fetch()) { |
| 57 | if (!array_key_exists($dao->child, $tree)) { |
| 58 | $tree[$dao->child] = array( |
| 59 | 'children' => array(), |
| 60 | 'parents' => array(), |
| 61 | ); |
| 62 | } |
| 63 | |
| 64 | if (!array_key_exists($dao->parent, $tree)) { |
| 65 | $tree[$dao->parent] = array( |
| 66 | 'children' => array(), |
| 67 | 'parents' => array(), |
| 68 | ); |
| 69 | } |
| 70 | |
| 71 | $tree[$dao->child]['parents'][] = $dao->parent; |
| 72 | $tree[$dao->parent]['children'][] = $dao->child; |
| 73 | } |
| 74 | |
| 75 | if (self::checkCyclicGraph($tree)) { |
| 76 | CRM_Core_Error::fatal(ts("We detected a cycle which we can't handle. aborting")); |
| 77 | } |
| 78 | |
| 79 | // first reset the current cache entries |
| 80 | $sql = " |
| 81 | UPDATE civicrm_group |
| 82 | SET parents = null, |
| 83 | children = null |
| 84 | "; |
| 85 | CRM_Core_DAO::executeQuery($sql); |
| 86 | |
| 87 | $values = array(); |
| 88 | foreach (array_keys($tree) as $id) { |
| 89 | $parents = implode(',', $tree[$id]['parents']); |
| 90 | $children = implode(',', $tree[$id]['children']); |
| 91 | $parents = $parents == NULL ? 'null' : "'$parents'"; |
| 92 | $children = $children == NULL ? 'null' : "'$children'"; |
| 93 | $sql = " |
| 94 | UPDATE civicrm_group |
| 95 | SET parents = $parents , |
| 96 | children = $children |
| 97 | WHERE id = $id |
| 98 | "; |
| 99 | CRM_Core_DAO::executeQuery($sql); |
| 100 | } |
| 101 | |
| 102 | // this tree stuff is quite useful, so lets store it in the cache |
| 103 | CRM_Core_BAO_Cache::setItem($tree, 'contact groups', 'nestable tree hierarchy'); |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * @param $tree |
| 108 | * |
| 109 | * @return bool |
| 110 | */ |
| 111 | public static function checkCyclicGraph(&$tree) { |
| 112 | // lets keep this simple, we should probably use a graph algorithm here at some stage |
| 113 | |
| 114 | // foreach group that has a parent or a child, ensure that |
| 115 | // the ancestors and descendants dont intersect |
| 116 | foreach ($tree as $id => $dontCare) { |
| 117 | if (self::isCyclic($tree, $id)) { |
| 118 | return TRUE; |
| 119 | } |
| 120 | } |
| 121 | |
| 122 | return FALSE; |
| 123 | } |
| 124 | |
| 125 | /** |
| 126 | * @param $tree |
| 127 | * @param int $id |
| 128 | * |
| 129 | * @return bool |
| 130 | */ |
| 131 | public static function isCyclic(&$tree, $id) { |
| 132 | $parents = $children = array(); |
| 133 | self::getAll($parent, $tree, $id, 'parents'); |
| 134 | self::getAll($child, $tree, $id, 'children'); |
| 135 | |
| 136 | $one = array_intersect($parents, $children); |
| 137 | $two = array_intersect($children, $parents); |
| 138 | if (!empty($one) || |
| 139 | !empty($two) |
| 140 | ) { |
| 141 | CRM_Core_Error::debug($id, $tree); |
| 142 | CRM_Core_Error::debug($id, $one); |
| 143 | CRM_Core_Error::debug($id, $two); |
| 144 | return TRUE; |
| 145 | } |
| 146 | return FALSE; |
| 147 | } |
| 148 | |
| 149 | /** |
| 150 | * @param int $id |
| 151 | * @param $groups |
| 152 | * |
| 153 | * @return array |
| 154 | */ |
| 155 | public static function getPotentialCandidates($id, &$groups) { |
| 156 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 157 | |
| 158 | if ($tree === NULL) { |
| 159 | self::update(); |
| 160 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 161 | } |
| 162 | |
| 163 | $potential = $groups; |
| 164 | |
| 165 | // remove all descendants |
| 166 | self::invalidate($potential, $tree, $id, 'children'); |
| 167 | |
| 168 | // remove all ancestors |
| 169 | self::invalidate($potential, $tree, $id, 'parents'); |
| 170 | |
| 171 | return array_keys($potential); |
| 172 | } |
| 173 | |
| 174 | /** |
| 175 | * @param $potential |
| 176 | * @param $tree |
| 177 | * @param int $id |
| 178 | * @param $token |
| 179 | */ |
| 180 | public static function invalidate(&$potential, &$tree, $id, $token) { |
| 181 | unset($potential[$id]); |
| 182 | |
| 183 | if (!isset($tree[$id]) || |
| 184 | empty($tree[$id][$token]) |
| 185 | ) { |
| 186 | return; |
| 187 | } |
| 188 | |
| 189 | foreach ($tree[$id][$token] as $tokenID) { |
| 190 | self::invalidate($potential, $tree, $tokenID, $token); |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | /** |
| 195 | * @param $all |
| 196 | * @param $tree |
| 197 | * @param int $id |
| 198 | * @param $token |
| 199 | */ |
| 200 | public static function getAll(&$all, &$tree, $id, $token) { |
| 201 | // if seen before, dont do anything |
| 202 | if (isset($all[$id])) { |
| 203 | return; |
| 204 | } |
| 205 | |
| 206 | $all[$id] = 1; |
| 207 | if (!isset($tree[$id]) || |
| 208 | empty($tree[$id][$token]) |
| 209 | ) { |
| 210 | return; |
| 211 | } |
| 212 | |
| 213 | foreach ($tree[$id][$token] as $tokenID) { |
| 214 | self::getAll($all, $tree, $tokenID, $token); |
| 215 | } |
| 216 | } |
| 217 | |
| 218 | /** |
| 219 | * @return string |
| 220 | */ |
| 221 | public static function json() { |
| 222 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 223 | |
| 224 | if ($tree === NULL) { |
| 225 | self::update(); |
| 226 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 227 | } |
| 228 | |
| 229 | // get all the groups |
| 230 | $groups = CRM_Core_PseudoConstant::group(); |
| 231 | |
| 232 | foreach ($groups as $id => $name) { |
| 233 | $string = "id:'$id', name:'$name'"; |
| 234 | if (isset($tree[$id])) { |
| 235 | $children = array(); |
| 236 | if (!empty($tree[$id]['children'])) { |
| 237 | foreach ($tree[$id]['children'] as $child) { |
| 238 | $children[] = "{_reference:'$child'}"; |
| 239 | } |
| 240 | $children = implode(',', $children); |
| 241 | $string .= ", children:[$children]"; |
| 242 | if (empty($tree[$id]['parents'])) { |
| 243 | $string .= ", type:'rootGroup'"; |
| 244 | } |
| 245 | else { |
| 246 | $string .= ", type:'middleGroup'"; |
| 247 | } |
| 248 | } |
| 249 | else { |
| 250 | $string .= ", type:'leafGroup'"; |
| 251 | } |
| 252 | } |
| 253 | else { |
| 254 | $string .= ", children:[], type:'rootGroup'"; |
| 255 | } |
| 256 | $values[] = "{ $string }"; |
| 257 | } |
| 258 | |
| 259 | $items = implode(",\n", $values); |
| 260 | $json = "{ |
| 261 | identifier:'id', |
| 262 | label:'name', |
| 263 | items:[ $items ] |
| 264 | }"; |
| 265 | return $json; |
| 266 | } |
| 267 | |
| 268 | } |